C语言解决顺序表扩大表容量含测试源码

大家好，我是执念斩长河，一个在学习数据结构的学渣。

题目再现

设计一个算法，当顺序表元素个数超过表容量的80%时将顺序表的容量扩大一倍；当顺序表元素个数少于其容量的25%时将其容量缩减一半。

测试结果

解题核心

只有动态存储分配的顺序表才可以扩大或缩小其存储空间。根据题目要求先判断size然后使用malloc重新分配，重新数组赋值

核心源码

void reallocate(SeqList& L) {
    //输入：顺序表 输出：重构的顺序表L
    int newSize;
    DataType *newArray;
    if(L.n > 0.8*L.maxSize)
        newSize = 2*L.maxSize;
    else if(L.n < 0.25*L.maxSize)
        newSize = L.maxSize/2;
    else
        return ;
    newArray = (DataType *)malloc(newSize*sizeof(DataType));
    for(int i =0;i<L.n;i++)
        newArray[i] = L.data[i];
    L.data = newArray;
    L.maxSize = newSize;

}

完整源码

#include<stdio.h>
#include<stdlib.h>
#define initSize 100
typedef int DataType;
typedef struct{
    DataType *data;
    int maxSize,n;
}SeqList;


void initList(SeqList& L) {
    //调用方式initList(L),输入:未初始化的顺序表L;输出；已初始化的顺序表L
    L.data = (DataType *) malloc(initSize*sizeof(DataType));
    if(!L.data) {
        printf("分配有误....\n");
        exit(1);
    }
    L.maxSize = initSize;
    L.n = 0;
}



void createList(SeqList &L,DataType A[],int n) {
    initList(L);
    for(int i = 0;i<n;i++)
        L.data[i] = A[i];
    L.n = n;
}

void printList(SeqList& L) {
    for(int i =0;i<L.n;i++)
        printf("%d ",L.data[i]);
    printf("\n");

}

//插入新元素
bool Insert(SeqList &L,int i,DataType x) {
    if (L.n == L.maxSize) return false;
    if(i < 1 || i > L.n+1)
        return false;
    for(int j=L.n;j>=i;j--)
        L.data[j] = L.data[j-1];
    L.data[i-1] = x;
    L.n++;
    return true;

}



void reallocate(SeqList& L) {
    //输入：顺序表 输出：重构的顺序表L
    int newSize;
    DataType *newArray;
    if(L.n > 0.8*L.maxSize)
        newSize = 2*L.maxSize;
    else if(L.n < 0.25*L.maxSize)
        newSize = L.maxSize/2;
    else
        return ;
    newArray = (DataType *)malloc(newSize*sizeof(DataType));
    for(int i =0;i<L.n;i++)
        newArray[i] = L.data[i];
    L.data = newArray;
    L.maxSize = newSize;

}

int main()
{

    SeqList A,B;
    //模拟1的情况
    int arr1[5] = {5,8,9,2,1};
    createList(A,arr1,sizeof(arr1)/sizeof(int));
    printList(A);
    printf("Length:%d ",A.maxSize);
    printf("\nrealloced:...\n");
    reallocate(A);
    printList(A);
    printf("Length:%d ",A.maxSize);

    return 0;
}

参考书籍

殷人昆著.数据结构与算法解析.北京：清华大学出版社，2021.4