C语言数据结构之顺序表

1.线性表

线性表式n个具有相同特性的数据元素的有限序列。应用广泛，常见的有：顺序表、链表 、栈、队列、字符串……。 线性性表在逻辑上是一条连续的条线；但在内存中是不一定是连续存储的，在存储的时候通常以数组和链式 形式存储。

2.顺序表

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

2.1.静态顺序表

#define N 10 typedef int SLDataType;//此时定义的存储数据类型是int，也可以定义结构体 //等等数据类型 int 也可以换成 double char //静态顺序表 内存空间固定，申请空间少了，不够用，多了用不完 struct SeqList { SLDataType a[N]; //定长数组 int size; //有效数据个数 };

静态的通讯录和其相似，但是通讯录存储的数据类型是一种结构体；静态的特点是：开辟空间完全依靠经验，后续无法自主调整 。

2.2.动态顺序表

typedef int SLDataType; //动态顺序表 按需申请空间 struct SeqList { SLDataType* a; //开始存储的起始地址，可以看作为数组名 int size; //有效数据个数 int capacity; //空间容量 }; 动态顺序表可以自主调整空间大小，空间不足的情况下，可以realloc向堆区申请内存空间，当然动态顺序表初始换使用malloc函数申请空间。

2.2.1.初始化

最开始的初始化思想是，所空间容量和有效数据数置为0，指针置为NULL（空指针）。 void SeqInit(SL* pc) { assert(pc); pc->a = NULL; pc->size = 0; pc->capacity = 0; printf(“初始化成功”); } 但是动态顺序表必须自带点儿空间，使用malloc函数向内存申请空间。INIT_CAPACITY暂定为3。 void SeqInit2(SL* pc)//形参是实参的拷贝；形参的修改无法作用在实参上，因此要用地址传值 { assert(pc); //其SL结构体数个整体， (SLDataType*)pc = (SLDataType*)malloc(sizeof(SLDataType)*INIT_CAPACITY); if (pc->a == NULL) { perror(“malloc fail”); return; } pc->capacity = INIT_CAPACITY;//使用#define 定义任意大小 pc->size = 0; printf(“初始化成功”); }

2.2.2.清空顺序表

在顺序表使用完，需要将开辟的空间释放，返还给操作系统，使用free函数释放申请的空间；我们申请的内存空间只有使用权。 void SLDestroy(SL* pc) { assert(pc); free(pc->a);//开的空间必须整体释放，不能一块儿一块释放 pc->a = NULL; pc->size = pc->capacity = 0; if(pc->a == NULL) printf(“清除成功”); } free函数在使用时出现问题

• 指针是野指针，不指向任何空间。
• fres释放指针不是起始位置指针，如果对开辟的指针进行处理之后
• pc->a[i]数组指向的空间越界,申请的空间不足且不扩容；
• size的大小超过了capacity（容量）就是越界，若是size越界了，说明空间开辟少了。

2.2.3.扩容＋尾插

**** 在输入数据之前，要先检查顺序表的容量是否已满，若空间满了就使用realloc扩容；若没有满就输入数据就可以。这里每次扩容将会把空间扩大二倍。

将X放入下面数据的尾部就是尾插 void SLPushBack(SL* pc, SLDataType x) { //扩容 if (pc->capacity == pc->size) { SLDataType* tmp = (SLDataType*)realloc(pc->a, sizeof(SLDataType)*INIT_CAPACITY * 2);//扩充二倍 if (pc->a == NULL) { perror(“realloc fail”); return ; } pc->a = tmp； pc->capacity *= 2; printf(“扩容成功\n”); } pc->a[pc->size++] = x; } realloc函数的使用如果没有 pc->a = tmp；可能会出错，realloc只会申请连续函数的使用权，若后续的内存不够，realloc将会重新申请一块儿内存，然后将新的地址赋给tmp，那么pc->a指向的位置，再次访问就是非法访问了；若是直接开辟，则问题还不明显，若是异地开辟，则会直接报错。

2.2.4.尾出函数

**** 尾出函数较为简单，只需要将size（有效数据个数）减去1就可以了；当然在进行删除之前就要判断顺序表中书否有数据（size是否为0） ； //尾出 void SLPopBack(SL* pc) { assert(pc->size > 0);//方式1报错 if (pc->size == 0) //方式2 return; pc->size–; }

在使用方式1：assert函数判断size是否大于0；如果大于0为真，执行下一步；若小于0为假，报错，而且会有具体的位置。assert函数会让程序维护更加简单。 若使用方式二报错，程序运行窗口会闪烁，一会儿会自动结束进程。

2.2.5.头插函数

头插函数在输入数据之前，要先检测是否要进行扩容，因此可以将扩容另写一个函数，再复用扩容函数；然后对位于最后的数据开始依次向后一个位置挪动。 void SLPushFront(SL* pc, SLDataType x) { assert(pc); //检查空间 SLCheckCapacity(pc); //挪动数据 int end = pc->size - 1; while (end >= 0) { pc->a[end + 1] = pc->a[end]; end–; } //赋值 pc->a[0] = x; //有效数据+1 pc->size++; }

2.2.6.头出函数

将第二个数据覆盖第一个数据，第三个数据覆盖第二个数据，然后有效数据减去一。 void SLPopFront(SL* pc) { assert(pc); assert(pc->size > 0); int i = 0; for (i = 0; i < pc->size; i++) { pc->a[i] = pc->a[i + 1]; } pc->size–; }

2.2.7.在中间位置插入

中间位置的插入就是确定位置pos在哪里，确定pos变量是否合规；判断是否有多余的空间；然后将最后一个数据向后再移动一个位置，依次移动。 //在某个位置插入 void SLInsert(SL* pc, int pos, SLDataType x) { //判断指针和位置是否有效 assert(pc); assert(pos >= 0 && pos <= pc->size); //判断是否扩容 SLCheckCapacity(pc); //挪动数据 int end = pc->size - 1; while (pos <= end) { pc->a[end + 1] = pc->a[end]; end–; } //插入数据 pc->a[pos] = x; pc->size++; } 我们可以根据这个函数对尾插和头插函数进行修改，复用上述函数。 头插函数 头插函数的位置就是0 pc->a[0]. void SLPushFront(SL* pc, SLDataType x) { assert(pc); //检查空间 SLCheckCapacity(pc); //挪动数据 SLInsert(pc, 0, x); } 尾插函数 void SLPushBack(SL* pc, SLDataType x) { assert(pc); SLInsert(pc, pc->size, x); }

2.2.8.删除中间位置数据

//删除某一个位置的数据 void SLErase(SL* pc, int pos) { assert(pc); assert(pos >= 0 && pos < pc->size); int begin = pos + 1; while (begin < pc->size) { pc->a[begin-1] = pc->a[begin]; begin++; } pc->size–; }

确定位置后，我们将其后面的数据依次递进，程序中的pos是数组的下标，从0开始。 当然上面的函数也可以复用 头出函数 void SLPopFront(SL* pc) { SLErase(pc,0); } 尾出函数 void SLPopBack(SL* pc) { SLErase(pc, pc->size-1); }

2.2.9.查找函数

将顺序表中的元素遍历一边，就可以找到了。 //查找函数 int SLFind(SL* pc, SLDataType x) { assert(pc); int i = 0; for (i = 0; i < pc->size; i++) { if (pc->a[i] == x) { return i + 1; } } return -1; }

2.2.10.总结

在插入和删除一组数据的情况下，按照最坏的时间复杂度来说，尾插和尾出的时间复杂度是O(1)；头插和头出的时间复杂度是O(N);中间插入和删除的时间复杂度也是O(N);因此在处理数据的时候，在好用的还是的尾插和尾出。

3.OJ例题

3.1.合并两个有序数组

[88 合并两个有序数组 - 力扣（LeetCode）]( array/description/ “88. 合并两个有序数组 - 力扣（LeetCode）”) void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int end1 = m - 1; int end2 = n -1; int dst = m + n -1; while(end1 >= 0&& end2 >= 0) { if(nums1[end1]>nums2[end2]) { nums1[dst–]=nums1[end1–]; } else { nums1[dst–]=nums2[end2–]; } } while(end2>=0) { nums1[dst–]=nums2[end2–]; } }

题解思路：

目标将两个数组合并成有序的数组，比较大小，nums1中有效数有m个元素，而长度为m+n个，足够容下nums2；数组nums1中的前面不能覆盖，所以就倒叙排列了。

3.2.删除有序数组中的重复项

[26 删除有序数组中的重复项 - 力扣（LeetCode）]( duplicates-from-sorted-array/description/ “26. 删除有序数组中的重复项 - 力扣（LeetCode）”) int removeDuplicates(int* nums, int numsSize) { int src = 1; int dst = 0; while(src < numsSize) { if(nums[src] == nums[dst]) { src++; } else { dst++; nums[dst] = nums[src++]; } } return dst+1; }

使用双指针，这里的双指针指的是两个下边；dst为目标指针，src为递进指针，src中的数组复制到src中；首先判断两个指针指向的数据是否一样，不一样复制；注意的是dst要增加一位；因为原来指向的位置不一样的；一样的话，src指针++，寻找下一个不一样的数据。

3.3.移除数组元素

[27 移除元素 - 力扣（LeetCode）]( element/description/ “27. 移除元素 - 力扣（LeetCode）”) int removeElement(int* nums, int numsSize, int val) { int src = 0; int dst = 0; while(src < numsSize) { if(nums[src] != val) { nums[dst++] = nums[src++]; } else { src++; } } return dst; }

使用双指针，从数组起始位置开始，和原来项相等便src++，dst保持不动，不相等的时候直接将val所占据的位置覆盖。

4.代码

4.1 SeqList.h文件

#pragma once #include #include #include //#define N 10 //typedef int SLDataType;//此时定义的存储数据类型是int，也可以定义结构体 等等数据类型 int 也可以换成 double char 静态顺序表 内存空间固定，申请空间少了，不够用，多了用不完 //struct SeqList //{ // SLDataType a[N]; //定长数组 // int size; //有效数据个数 //}; #define INIT_CAPACITY 3 typedef int SLDataType; //动态数组 struct SeqList { SLDataType* a; //开始存储的起始地址，可以看作为数组名 int size; //有效数据个数 int capacity; //空间容量 }; typedef struct SeqList SL; //初始化 void SeqInit(SL* pc); //扩容+初始化 void SeqInit2(SL* pc); //清空函数 void SLDestroy(SL* pc); //尾插函数 void SLPushBack(SL* pc, SLDataType x); //输出函数 void SLPrint(SL* pc); //尾出函数 void SLPopBack(SL* pc); //扩容函数 void SLCheckCapacity(SL* pc); //前插函数 void SLPushFront(SL* pc, SLDataType x); //头删函数 void SLPopFront(SL* pc); //在某个位置插入 void SLInsert(SL* pc, int pos, SLDataType x); //删除某一个位置的数据 void SLErase(SL* pc, int pos); //查找函数 int SLFind(SL* pc, SLDataType x);

4.2.SeqList.c文件

#include “SeqList.h” //初始化 void SeqInit(SL* pc) { pc->a = NULL; pc->size = 0; pc->capacity = 0; printf(“初始化成功”); } //初始化开辟空间 void SeqInit2(SL* pc)//形参是实参的拷贝；形参的修改无法作用在实参上，因此要用地址传值 { //其SL结构体数个整体， assert(pc); (SLDataType*)pc->a = (SLDataType*)malloc(sizeof(SLDataType)INIT_CAPACITY); if (pc->a == NULL) { perror(“malloc fail”); return; } pc->capacity = INIT_CAPACITY; pc->size = 0; printf(“初始化成功\n”); } //清除函数 void SLDestroy(SL pc) { assert(pc); free(pc->a); pc->a = NULL; pc->size = pc->capacity = 0; if(pc->a == NULL) printf("\n清除成功"); } //尾插函数 void SLPushBack(SL* pc, SLDataType x) { assert(pc); //扩容 SLInsert(pc, pc->size, x); //SLCheckCapacity(pc); //pc->a[pc->size++] = x; } //输出函数 void SLPrint(SL* pc) { int i = 0; for (i = 0; i < pc->size; i++) { printf("%d “,pc->a[i]); } printf("\n”); } //尾出函数 void SLPopBack(SL* pc) { SLErase(pc, pc->size-1); } //扩容函数 void SLCheckCapacity(SL* pc) { if (pc->capacity == pc->size) { SLDataType* tmp = (SLDataType*)realloc(pc->a, sizeof(SLDataType)INIT_CAPACITY * 2);//扩充二倍 if (pc->a == NULL) { perror(“realloc fail”); return; } pc->a = tmp; pc->capacity = 2; printf(“扩容成功\n”); } } //头插函数 void SLPushFront(SL pc, SLDataType x) { assert(pc); //检查空间 SLCheckCapacity(pc); //挪动数据 SLInsert(pc, 0, x); } //头出函数 void SLPopFront(SL pc) { SLErase(pc,0); } //在某个位置插入 void SLInsert(SL* pc, int pos, SLDataType x) { //判断指针和位置是否有效 assert(pc); assert(pos >= 0 && pos <= pc->size); //判断是否扩容 SLCheckCapacity(pc); //挪动数据 int end = pc->size - 1; while (pos <= end) { pc->a[end + 1] = pc->a[end]; end–; } //插入数据 pc->a[pos] = x; pc->size++; } //删除某一个位置的数据 void SLErase(SL* pc, int pos) { assert(pc); assert(pos >= 0 && pos < pc->size); int begin = pos + 1; while (begin < pc->size) { pc->a[begin-1] = pc->a[begin]; begin++; } pc->size–; } //查找函数 int SLFind(SL* pc, SLDataType x) { assert(pc); int i = 0; for (i = 0; i < pc->size; i++) { if (pc->a[i] == x) { return i + 1; } } return -1; }