笔记|顺序表的实现 c#|数据结构|链表|linq

目录
1.顺序表的概念
2.静态顺序表
分析：
3.动态顺序表
分析：
4.顺序表初始化
5.顺序表尾部操作
5.1尾插
空间检查函数实现
分析：
5.2尾删
分析：
6.顺序表的头部操作
6.1头插
分析：
6.2头删
分析：
7.固定位置操作
7.1固定位置插入
分析：
7.2固定位置删除
分析：
8.查找及打印
9.销毁顺序表
10.我的菜单及主函数
直接上代码：

1.顺序表的概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：静态顺序表和动态顺序表
2.静态顺序表使用定长数组存储元素
分析：

文章图片

3.动态顺序表 【笔记|顺序表的实现】使用动态开辟的数组存储
分析：

文章图片

函数接口基于动态顺序表来实现
4.顺序表初始化通过分析，我们知道顺序表中有起始地址，数据个数，及空间大小，一个顺序表刚开始当然应该为空，那么数据个数和空间大小应为0，起始地址应置空。
操作是对整个顺序表进行操作，函数参数应传顺序表地址，形参接收用指针。

//初始化 void SLInit(SL* p) { assert(p); //暴力判断，断言指针是否为空 p->a = NULL; p->size = 0; p->capacity = 0; }

5.顺序表尾部操作 5.1尾插

顾名思义，从顺序表的末尾插入数据，顺序表空间是固定的，插入的时候我们要检查空间是否足够，不够则要进行扩容，足够则插入。

void SLPushBack(SL* p, SLDataType x) { assert(p); //检查空间,是否扩容 SLcheckCapacity(p); //插入 p->a[p->size] = x; //尾数的下一个位置插入数据 p->size++; //有效数据个数加一 }

空间检查函数实现

//检查空间 void SLcheckCapacity(SL* p) { assert(p); //检查是否需要扩容 if (p->size == p->capacity) { size_t newCapacity = p->capacity == 0 ? 4 : p->capacity * 2; SLDataType* tmp = realloc(p->a, sizeof(SLDataType)*newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { p->a = tmp; p->capacity = newCapacity; } } }

分析：

我们要知道当数据个数=空间数时，空间已满，那么就要改变空间大小，这里我们设新的空间大小newCapacity为原capacity的二倍。
接下来就是扩容空间为新空间大小，用realloc开辟空间，记着要判断是否开辟成功，详细用法：动态内存管理分析理解_i跑跑的博客-CSDN博客
开辟成功后，记得将令新空间指向原顺序表地址，空间大小=新空间大小。

5.2尾删分析：
删除的时候并不是将最后一个数给置为0，或者‘\n’，这些，不对数据进行任何需要将操作。而是只有效个数减一就可以。注意不可以对要删除数得空间进行释放，这是不可取得，动态开辟出的空间是一起开辟，一起释放的，在这里不可以实现。

//尾删 void SLPopBack(SL* p) { assert(p); //size不能一直-- if (p->size > 0) { p->size--; } }

有效个数不能为负数，这里要进行判断。
6.顺序表的头部操作 6.1头插分析：
从头部插入数据，那么就需要将原数据从最后一个数据开始向后移动一位，这里必然要进行空间检查。

文章图片

//头插 void SLPushFront(SL* p, SLDataType x) { assert(p); SLcheckCapacity(p); for (int i = p->size; i>0; i--) { p->a[i] = p->a[i-1]; } p->a[0] = x; p->size++; }

记得插入后有效数据个数加一。
6.2头删分析：
与头插相反，头插是将从最后一个数开始向后覆盖，头删是不要第一个数，从第一个数开始，第一个=第二个；第二个=第三个 ... ... 这样覆盖，覆盖原有效数据-1次。

文章图片

//头删 void SLPopFront(SL* p) { assert(p); if (p->size>0) { for (int j = 0; jsize - 1; j++) { p->a[j] = p->a[j + 1]; } } p->size--; }

7.固定位置操作 7.1固定位置插入固定位置为下标，从0开始
分析：
思想与头插相似，先要判断空间是否足够。再进行插入，例如从下标x的位置开始，那么从最后一个数向后挪动，挪动size-x次，在x位置插入数据。

文章图片

判断位置大小是否大于size，越界。

//在固定位置插入,pos为下标 void SLInsert(SL* p, size_t pos, SLDataType x) { assert(p); //注意要判断pos的大小 if (pos>p->size) { printf("pos 越界:%d\n",pos); return; } SLcheckCapacity(p); for (int i = p->size; i>pos; i--) { p->a[i] = p->a[i - 1]; } p->a[pos] = x; p->size++; }

7.2固定位置删除分析：
操作与头删相似，从pos位置开始；第一个=第二个；第二个=第三个 ... ... ，覆盖到pos=尾数的上一个数，顺便也防了个越界。

文章图片

//在固定位置删除,pos为下标 void SLErase(SL* p, size_t pos) { assert(p); if (possize) { for (int j = (int)pos; jsize-1; j++) { p->a[j] = p->a[j + 1]; } } p->size--; }

8.查找及打印依次遍历，找到则返回位置下标，

//查找 int SLFind(SL* p,SLDataType x) { assert(p); for (int i = 0; isize; i++) { if (p->a[i]==x) { return i; } } return -1; }

也是遍历，打印每一个数据。

//打印 void SLPrintf(SL* p) { assert(p); for (int i = 0; isize; i++) { printf("%d ",p->a[i]); } printf("\n"); }

9.销毁顺序表注意要释放掉内存

//销毁 void SLDestory(SL* p) { assert(p); free(p->a); p->a = NULL; p->capacity = p->size = 0; }

10.我的菜单及主函数直接上代码：

void menu() { printf("******************************\n"); printf("** 1.尾插数据 ** 2.头插数据 **\n"); printf("** 3.尾删数据 ** 4.头删数据 **\n"); printf("** 5.固定插入 ** 6.固定删除 **\n"); printf("** 7.查找数据 ** 8.打印数据 **\n"); printf("**0.退出**\n"); printf("******************************\n"); } int main() { SL s; SLInit(&s); int input = 0; do { int val = 0; size_t pos = 0; menu(); printf("请输入选项->:"); scanf("%d", &input); switch (input) { case 1: printf("请输入你要尾插的数据:"); scanf("%d",&val); SLPushBack(&s,val); break; case 2: printf("请输入你要头插的数据:"); scanf("%d", &val); SLPushFront(&s, val); break; case 3: SLPopBack(&s); break; case 4: SLPopFront(&s); break; case 5: printf("请输入你要插入的位置和数据:"); scanf("%d %d",&pos ,&val); SLInsert(&s,pos,val); break; case 6: printf("请输入你要删除的位置:"); scanf("%d", &pos); SLErase(&s, pos); break; case 7: printf("请输入要查找的数据:"); scanf("%d",&val); int num=SLFind(&s,val); printf("%d\n",num); break; case 8: SLPrintf(&s); break; case 0: SLDestory(&s); break; default: printf("请重新输入\n"); break; } } while (input); return 0; }

这样一个顺序表的定义，函数及功能就建立完成了。
看到这啦，点个赞呗，关注不迷路噢，欢迎大家评论指正。