1. 顺序表的概念及结构
顺序表是用一段物理地址连续的存储单元以此存储数据的线性结构，一般情况下用数组存储。在数组上完成数据的增删查改~
1. 静态顺序表:用指定长度数组存储元素~
2. 动态顺序表:用动态开辟的数组存储~
2. 接口的实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空 间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间 大小，所以下面我们实现动态顺序表。
我们创建一个Test.h里面包含了所有的接口函数声明和各种头文件的声明~
这样我们一个一个实现，正所谓天下难事必做于细~
#define _CRT_SECURE_NO_WARNINGS #pragma once//避免头文件的多次包含 #include<stdio.h> #include<assert.h> #include<stdlib.h> typedef int SLDataType;//便于类型的改动 //定义一个动态顺序表的结构体变量 typedef struct SeqList { SLDataType* arr; size_t num;//记录有效数据的个数 size_t capacity;//该顺序表的容量大小 }SL;//将该结构体类型重命名为SL //加入增删查改接口 //1. 顺序表初始化 void SeqListInit(SL* p); //2. 检查顺序表容量是否已满 void CheckSeqList(SL* p); //3. 顺序表的尾插 void SeqListPushBack(SL* p, SLDataType x); //4. 顺序表的尾删 void SeqListPopBack(SL* p); //5. 顺序表的头插 void SeqListPushFront(SL* p, SLDataType x); //6. 顺序表的头删 void SeqListPopFront(SL* p); //7. 顺序表在pos位置插入 void SeqListInsert(SL* p, size_t pos,SLDataType x); //8. 顺序表在pos位置删除 void SeqListErase(SL* p, size_t pos); //9. 顺序表的查找 int SeqListFind(SL* p,SLDataType x);//如果该数字存在则返回该数字的下标，否则返回-1 //10 顺序表的销毁 void SeqListDestory(SL* p); //11. 顺序表的打印 void SeqListPrint(SL* p);
我们将所有函数的实现放在SeqList.c文件中~
2.1 顺序表的初始化
(1) 代码实现
//1. 顺序表初始化 void SeqListInit(SL* p) { assert(p);//判断指针的有效性 p->arr = NULL; p->capacity = 0; p->num = 0; }
(2) 复杂度分析
- 时间复杂度：由于没有其他未知数的引入，所以所需时间是个常数，也就是O(1)。
- 空间复杂度：动态开辟N个空间，所以空间复杂度为O(N)。
注意我们这里一定要传址调用~
2.2 检查顺序表容量是否已满
(1) 代码实现
注释写的很详细了，这里就不做过多的解释~
//2. 检查顺序表容量是否已满 void CheckSeqList(SL* p) { assert(p);//判断指针的有效性 if (p->num == p->capacity) { size_t newcapacity=p->capacity == 0 ? p->capacity = 4 : p->capacity * 2; //如果原来没有空间，就给上4，有的话就扩大为原来的两倍 SLDataType* ptr = (SLDataType*)realloc(p->arr, newcapacity * sizeof(SLDataType));//动态扩容 if (ptr == NULL) { perror("realloc fail;"); return; } //也可以用assert断言一下 p->arr = ptr;//开辟成功将地址传给arr p->capacity = newcapacity;//更新容量 } }
2.3 顺序表的尾插
(1) 代码实现
//3. 顺序表的尾插 void SeqListPushBack(SL* p, SLDataType x) { assert(p);//判断指针的有效性 CheckSeqList(p);//尾插前先判断有没有容量或容量够不够 p->arr[p->num] = x;//尾部插入数据 p->num++;//有效数加一 }
(2) 复杂度分析
- 时间复杂度：没有变量影响时间，时间复杂度为O(1)。
- 空间复杂度：以最坏的情况考虑，会进行扩容，空间复杂度为O(N)。
2.4 顺序表的尾删
(1) 代码实现
//4. 顺序表的尾删 void SeqListPopBack(SL* p) { assert(p);//判断指针的有效性 assert(p->num > 0);//断言存在有效数据 p->num--;//尾删一个数据 }
(2) 复杂度分析
- 时间复杂度：没有变量影响时间，时间复杂度为O(1)。
- 空间复杂度：没有变量影响空间，空间复杂度为O(1)。
2.5 顺序表的头插
(1) 代码实现
//5. 顺序表的头插 void SeqListPushFront(SL* p, SLDataType x) { assert(p);//判断指针的有效性 CheckSeqList(p);//先判断容量是否满了 size_t end = p->num; while (end) { p->arr[end] = p->arr[end - 1];//整体向后移动 end--; } p->arr[0] = x;//头插 p->num++;//有效数据加一 }
(2) 复杂度分析
- 时间复杂度：因为从头部插入数据，后续数据需要依次覆盖，所以时间复杂度为O(N)。
- 空间复杂度：因为可能会进行扩容，按最坏的情况来算，空间复杂度为O(N)。
2.6 顺序表的头删
(1) 代码实现
//6. 顺序表的头删 void SeqListPopFront(SL* p) { assert(p);//判断指针的有效性 assert(p->num > 0);//有数据才删除 size_t begin = 1; while (begin<p->num) { p->arr[begin - 1] = p->arr[begin];//整体向前移动 begin++; } p->num--;// 有效数据减一 }
整体往前挪，把头覆盖~
(2) 复杂度分析
- 时间复杂度：因为需要往前覆盖数据，所以时间复杂度自然为O(N)。
- 空间复杂度：因为并没有开辟其他空间，所以空间复杂度为O(1)。
2.7 顺序表在pos位置插入
(1) 代码实现
//7. 顺序表在pos位置插入 void SeqListInsert(SL* p, size_t pos, SLDataType x) { assert(p);//判断指针的有效性 assert(pos >= 0 && pos < p->num);//pos必须小于num并且大于等于0 CheckSeqList(p);//判断容量是否满了 for (int i = p->num; i >pos-1 ; i--) { p->arr[i] = p->arr[i - 1];//将pos后面的元素往后挪 } p->arr[pos - 1] = x;//在pos位置加入数据 p->num++;//有效个数加一 }
(2) 复杂度分析
- 时间复杂度：需要依次覆盖，时间复杂度为O(N)。
- 空间复杂度：可能需要扩容，空间复杂度为O(N)。
2.8 顺序表在pos位置删除
(1) 代码实现
//8. 顺序表在pos位置删除 void SeqListErase(SL* p, size_t pos) { assert(p);//判断指针的有效性 assert(pos>=0&&pos<p->num );//pos必须小于num并且大于等于0 assert(p->num > 0);//有数据才能删除 for (int i = pos; i <p->num; i++) { p->arr[i-1] = p->arr[i];//将pos后面的元素往后挪 } p->num--;//有效个数减一 }
(2) 复杂度分析
- 时间复杂度：需要依次覆盖，时间复杂度为O(N)。
- 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。
2.9 顺序表的查找
(1) 代码实现
遍历数组查找~
//9. 顺序表的查找 int SeqListFind(SL* p, SLDataType x)//如果该数字存在则返回该数字的下标，否则返回-1 { assert(p);//断言 for (int i = 0; i < p->num; i++) { if (p->arr[i] == x) { return i;//查到返回下标 } } return -1;//没有查到 }
(2) 复杂度分析
- 时间复杂度：以最坏的情况分析，时间复杂度为O(N)。
- 空间复杂度：并没有格外的空间消耗，空间复杂度为O(1)。
2.10 顺序表的销毁
(1) 代码实现
//10 顺序表的销毁 void SeqListDestory(SL* p) { assert(p);//判断指针的有效性 free(p->arr );//释放动态内存开辟的空间 p->arr = NULL; p->capacity = 0;//容量置为0 p->num = 0;//有效个数置为0 }
(2) 复杂度分析
- 时间复杂度：没有额外的时间消耗，时间复杂度为O(1)。
- 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。
2.11 顺序表的打印
(1) 代码实现
//11. 顺序表的打印 void SeqListPrint(SL* p) { assert(p);//判断指针的有效性 if (p->num == 0) { printf("顺序表为空！\n"); return; } for (int i = 0; i < p->num; i++) { printf("%d ", p->arr[i]);//打印数据 } printf("\n"); }
(2) 复杂度分析
- 时间复杂度：因为会打印顺序表中的所有数据，所以时间复杂度为O(N)。
- 空间复杂度：打印顺序表并不需要开辟格外的空间，所以空间复杂度为O(1)。
3. 完整代码
SeqList.c
#define _CRT_SECURE_NO_WARNINGS #include"Test.h" //接口函数的实现 //1. 顺序表初始化 void SeqListInit(SL* p) { assert(p);//判断指针的有效性 p->arr = NULL; p->capacity = 0; p->num = 0; } //2. 检查顺序表容量是否已满 void CheckSeqList(SL* p) { assert(p);//判断指针的有效性 if (p->num == p->capacity) { size_t newcapacity=p->capacity == 0 ? p->capacity = 4 : p->capacity * 2; //如果原来没有空间，就给上4，有的话就扩大为原来的两倍 SLDataType* ptr = (SLDataType*)realloc(p->arr, newcapacity * sizeof(SLDataType));//动态扩容 if (ptr == NULL) { perror("realloc fail;"); return; } //也可以用assert断言一下 p->arr = ptr;//开辟成功将地址传给arr p->capacity = newcapacity;//更新容量 } } //3. 顺序表的尾插 void SeqListPushBack(SL* p, SLDataType x) { assert(p);//判断指针的有效性 CheckSeqList(p);//尾插前先判断有没有容量或容量够不够 p->arr[p->num] = x;//尾部插入数据 p->num++;//有效数加一 } //4. 顺序表的尾删 void SeqListPopBack(SL* p) { assert(p);//判断指针的有效性 assert(p->num > 0);//断言存在有效数据 p->num--;//尾删一个数据 } //5. 顺序表的头插 void SeqListPushFront(SL* p, SLDataType x) { assert(p);//判断指针的有效性 CheckSeqList(p);//先判断容量是否满了 size_t end = p->num; while (end) { p->arr[end] = p->arr[end - 1];//整体向后移动 end--; } p->arr[0] = x;//头插 p->num++;//有效数据加一 } //6. 顺序表的头删 void SeqListPopFront(SL* p) { assert(p);//判断指针的有效性 assert(p->num > 0);//有数据才删除 size_t begin = 1; while (begin<p->num) { p->arr[begin - 1] = p->arr[begin];//整体向前移动 begin++; } p->num--;// 有效数据减一 } //7. 顺序表在pos位置插入 void SeqListInsert(SL* p, size_t pos, SLDataType x) { assert(p);//判断指针的有效性 assert(pos >= 0 && pos < p->num);//pos必须小于num并且大于等于0 CheckSeqList(p);//判断容量是否满了 for (int i = p->num; i >pos-1 ; i--) { p->arr[i] = p->arr[i - 1];//将pos后面的元素往后挪 } p->arr[pos - 1] = x;//在pos位置加入数据 p->num++;//有效个数加一 } //8. 顺序表在pos位置删除 void SeqListErase(SL* p, size_t pos) { assert(p);//判断指针的有效性 assert(pos>=0&&pos<p->num );//pos必须小于num并且大于等于0 assert(p->num > 0);//有数据才能删除 for (int i = pos; i <p->num; i++) { p->arr[i-1] = p->arr[i];//将pos后面的元素往后挪 } p->num--;//有效个数减一 } //9. 顺序表的查找 int SeqListFind(SL* p, SLDataType x)//如果该数字存在则返回该数字的下标，否则返回-1 { assert(p);//断言 for (int i = 0; i < p->num; i++) { if (p->arr[i] == x) { return i;//查到返回下标 } } return -1;//没有查到 } //10 顺序表的销毁 void SeqListDestory(SL* p) { assert(p);//判断指针的有效性 free(p->arr );//释放动态内存开辟的空间 p->arr = NULL; p->capacity = 0;//容量置为0 p->num = 0;//有效个数置为0 } //11. 顺序表的打印 void SeqListPrint(SL* p) { assert(p);//判断指针的有效性 if (p->num == 0) { printf("顺序表为空！\n"); return; } for (int i = 0; i < p->num; i++) { printf("%d ", p->arr[i]);//打印数据 } printf("\n"); }
