大家好,我是执念斩长河,一个在学习数据结构的学渣。
题目再现
设计一个算法,当顺序表元素个数超过表容量的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