Data Structure - 基于realloc可自动扩展的顺序表 By C

因为考研需要，所以现在开始复习数据结构；

后续会持续更新整个数据结构，内容如下： 也是因为考研，很久没有更新博客，也没有写代码了。一时还有点小激动。hhh具体实现见代码注释吧。不得不说，c语言自是有其迷人之处的。

---

总结一下

关于对地址，与数组的进一步理解 对于使用基地址的形式，可以理解为数组，即基地址的首地址，即为数组的首地址，又因为对其的类型，进行了定义，故当取到首地址的指针（q）时，进行q++，系统会在已知，此类型占多少空间的情况下，跳到下一块地址即下一个元素，即如数组这些之前也有写过，不过因为时间久了，又记不清了，所以再写一次，以求加深记忆欢迎交流指正 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define INIT_SIZE 100 //空间初始容量 #define INCREMENT 10 //增量 #include <stdio.h> #include <stdlib.h> typedef int Status; typedef int ElemType; typedef struct { ElemType *elem; //存储空间的基址 int length; // 当前长度(元素个数) int listsize; //存储容量 }Sqlist; Status InitList_sq(Sqlist &L) { L.elem = (ElemType*)malloc(INIT_SIZE * sizeof(ElemType)); if (!L.elem) { return OVERFLOW; } L.length = 0; L.listsize = INIT_SIZE; return OK; } Status ListInsert_sq(Sqlist &L,int i,ElemType x) { if (i<1||i>L.length+1) //判断是否越界 { return ERROR; } if (L.length>=L.listsize) //查询是否已满，考虑下一步扩容 { /* extern void *realloc(void *mem_address, unsigned int newsize); 改变mem_address所指向内存区域的大小为newsize； if 当初区域后方有足够闲置的内存空间， 则会在原内存地址基础上，进行扩展。 else 将会在内存堆中，找一块新的连续内存空间，进行分配，并将之前的内容复制过去。 返回值： void类型指针：即操作成功，可进行下一步类型强制转换； NULL: 1.即无空间可分配 2.传入newsize参数为0，导致当前地址空间free */ ElemType* newbase = (ElemType*)realloc(L.elem, (L.listsize + INCREMENT) * sizeof(ElemType)); if (!newbase) { exit(OVERFLOW); } L.elem = newbase; L.listsize += INCREMENT; } ElemType *q = &(L.elem[i - 1]); //获取需要插入位置的元素地址 for (ElemType *p=&(L.elem[L.length-1]);p>=q;--p)//（最后一位元素的地址） { //将从插入位置起的元素，统一往后移一位 *(p + 1) = *p; } *q = x; //赋值 L.length++; //元素个数++ return OK; } Status ListDelete_sq(Sqlist& L, int i, ElemType &x) { if (i<1||i>L.length) { return ERROR; } ElemType* p = &(L.elem[i - 1]); //取到欲删除地址的值 x = *p; //将欲删除值赋给x 予以返回 for (ElemType* q=&(L.elem[L.length-1]);p+1<=q;p++) //批量前移 { *p = *(p + 1); } L.length--; return OK; } Status ListPrintf_sq(Sqlist& L) { ElemType* p = L.elem; int length = L.length; while (length--) { printf("%d\t", *(p++)); } return OK; } int main() { Sqlist sq; InitList_sq(sq); for (int i = 1; i <= 110; i++) { ListInsert_sq(sq, i, i); } ElemType a=0; ListDelete_sq(sq, 20, a); ListPrintf_sq(sq); printf("\n\n已删除元素，其值为：%d", a); printf("\n顺序表当前元素个数：%d\t", sq.length); printf("\n顺序表当前最大容量：%d", sq.listsize); return OK; }

添加了从1-120 120个数删除了第二十个数