文章目录
一、线性表
线性表(linear list )是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表:顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
二、顺序表
💦 顺序表的概念和结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
静态顺序表：使用定长数组存储
缺点就是小了不够用，大了浪费
动态顺序表：使用动态开辟的数组存储
可根据自己的需要调整大小
💦 顺序表各接口实现 (动图分析)
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N固定了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表以及增删查改等功能
这里新建三个文件：
1️⃣ SeqList.h文件，用于函数声明
2️⃣ SeqList.c文件，用于函数的定义
3️⃣ Test.c文件，用于测试函数
⭕ 接口1：定义结构体SLT
typedef int SQDataType; typedef struct SeqList { SQDataType* a;//指向动态开辟的空间 int size;//有效数据个数 int capacity;//当前容量 }SLT;
⭕ 接口2：初始化结构体 (SeqListInit)
函数原型：
函数实现：
void SeqListInit(SLT* psl) { assert(psl); psl->a = NULL; psl->size = psl->capacity = 0; }
📐 测试
⭕ 接口3：检查容量 (SeqListCheckCapcity)
函数原型：
函数实现：
void SeqListCheckCapcity(SLT* psl) { //一般情况为了避免频繁插入数据而增容，或者一下开辟很大的空间，我们一般是每次增容2倍 assert(psl); if (psl->size == psl->capacity) { //第一次是增容4*sizeof(SQDataType) size_t newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2; int* temp = (SQDataType*)realloc(psl->a, newcapacity * sizeof(SQDataType)); if (temp != NULL) psl->a = temp; else return; psl->capacity = newcapacity; } }
📐 测试
⭕ 接口4：指定位置插入数据 (SeqListInser)
函数原型
函数实现
void SeqListInser(SLT* psl, size_t pos, SQDataType x) { assert(psl); //因为pos是size_t类型的，所以不用断言它是否小于0了，不过还是建议加上 assert(pos > 0 && pos <= psl->size + 1); //判断是否要增容 SeqListCheckCapcity(psl); int start = pos - 1; int end = psl->size - 1; while (start <= end) { psl->a[end + 1] = psl->a[end]; end--; } psl->a[pos - 1] = x; psl->size++; }
📐 测试
⭕ 接口5：输出数据 (SeqListPrint)
函数原型
函数实现
void SeqListPrint(SLT* psl) { assert(psl); int i = 0; for (i = 0; i < psl->size; i++) { printf("%d ", psl->a[i]); } printf("\n"); }
📐 测试
⭕ 接口6：尾插 (SeqListPushBack)
函数原型
函数实现
void SeqListPushBack(SLT* psl, SQDataType x) { assert(psl); //根据分析尾部插入的话，传size+1吻合SeqListInser函数 SeqListInser(psl, psl->size + 1, x); }
📐 测试
⭕ 接口7：头插 (SeqListPushFront)
函数原型
函数实现
void SeqListPushFront(SLT* psl, SQDataType x) { assert(psl); SeqListInser(psl, 1, x);//根据分析头部插入的话，传1吻合SeqListInser函数 }
📐 测试
⭕ 接口8：指定位置删除数据 (SeqListErase)
函数原型
函数实现
void SeqListErase(SLT* psl, size_t pos) { assert(psl); //因为pos是size_t类型的，所以不用断言它是否小于0了，不过还是建议加上 assert(pos > 0 && pos <= psl->size); size_t start = pos - 1; while (start < psl->size - 1) { psl->a[start] = psl->a[start + 1]; start++; } psl->size--; }
📐 测试
⭕ 接口9：尾删 (SeqListPopBack)
函数原型
函数实现
void SeqListPopBack(SLT* psl) { assert(psl); SeqListErase(psl, psl->size); }
📐 测试
⭕ 接口10：头删 (SeqListPopFront)
函数原型
函数实现
void SeqListPopFront(SLT* psl) { assert(psl); SeqListErase(psl, 1); }
📐 测试
⭕ 接口11：查找 (SeqListFind)
函数原型
函数实现
//找到返回下标，找不到返回-1 int SeqListFind(SLT* psl, SQDataType x) { assert(psl); int i = 0; for (i = 0; i < psl->size; i++) { if (psl->a[i] == x) { return i; } } return -1; }
📐 测试
⭕ 接口12：统计 (SeqListSize)
函数原型
函数信息
size_t SeqListSize(SLT* psl) { assert(psl); return psl->size; }
📐 测试
⭕ 接口13：修改 (SeqListAt)
函数原型
函数实现
size_t SeqListAt(SLT* psl, size_t pos, SQDataType x) { assert(psl); assert(pos > 0 && pos <= psl->size); psl->a[pos - 1] = x; }
📐 测试
⭕ 接口14：销毁 (SeqListDestory)
函数原型
函数实现
void SeqListDestory(SLT* psl) { assert(psl); if (psl->a) { free(psl->a); psl->a = NULL; } psl->size = psl->capacity = 0; }
📐 测试
📝 完整代码
SeqList.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SQDataType; typedef struct SeqList { SQDataType* a;//指向动态开辟的空间 int size;//有效数据个数 int capacity;//当前容量 }SLT; //初始化 void SeqListInit(SLT* psl); //检查容量 void SeqListCheckCapcity(SLT* psl); //尾部插入 void SeqListPushBack(SLT* psl, SQDataType x); //头部插入 void SeqListPushFront(SLT* psl, SQDataType x); //尾部删除 void SeqListPopBack(SLT* psl); //头部删除 void SeqListPopFront(SLT* psl); //显示 void SeqListPrint(SLT* psl); //查找 int SeqListFind(SLT* psl, SQDataType x); //从某个值的位置插入 void SeqListInser(SLT* psl, size_t pos, SQDataType x); //从某个值的位置删除 void SeqListErase(SLT* psl, size_t pos); //统计当前有多少数据 - 不要认为这样没必要，这是规范的操作 size_t SeqListSize(SLT* psl); //修改 size_t SeqListAt(SLT* psl, size_t pos, SQDataType x); //销毁 void SeqListDestory(SLT* psl);
SeqList.c
#include"SeqList.h" //初始化 void SeqListInit(SLT* psl) { assert(psl); psl->a = NULL; psl->size = psl->capacity = 0; } //检查容量 void SeqListCheckCapcity(SLT* psl) { assert(psl); //检查容量以决定要不要增容 - 2倍增容(一般情况为了避免频繁插入数据增容，或者一下开辟很大的空间，我们一般是每次增容2倍 if (psl->size == psl->capacity) { size_t newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2; int* temp = (SQDataType*)realloc(psl->a, newcapacity * sizeof(SQDataType)); if (temp != NULL) psl->a = temp; else return; psl->capacity = newcapacity; } } //尾部插入 void SeqListPushBack(SLT* psl, SQDataType x) { /*assert(psl); SeqListCheckCapcity(psl); psl->a[psl->size] = x; psl->size++;*/ assert(psl); SeqListInser(psl, psl->size + 1, x);//根据分析尾部插入的话，传size+1吻合SeqListInser函数 } //头部插入 void SeqListPushFront(SLT* psl, SQDataType x) { //assert(psl); //SeqListCheckCapcity(psl); 挪动数据 //int end = psl->size - 1; //while (end >= 0) //{ // psl->a[end + 1] = psl->a[end]; // --end; //} //psl->a[0] = x; //psl->size++; assert(psl); SeqListInser(psl, 1, x);//根据分析头部插入的话，传1吻合SeqListInser函数 } //尾部删除 void SeqListPopBack(SLT* psl) { //assert(psl); //assert(psl->size > 0);//如果没有数据就报错 //psl->size--; assert(psl); SeqListErase(psl, psl->size); } //头部删除 void SeqListPopFront(SLT* psl) { //assert(psl); //assert(psl->size > 0);//如果没有数据就报错 //int start = 0; //while (start < psl->size - 1) //{ // psl->a[start] = psl->a[start + 1]; // start++; //} //psl->size--; assert(psl); SeqListErase(psl, 1); } //显示数据 void SeqListPrint(SLT* psl) { assert(psl); int i = 0; for (i = 0; i < psl->size; i++) { printf("%d ", psl->a[i]); } printf("\n"); } //销毁 void SeqListDestory(SLT* psl) { assert(psl); if (psl->a) { free(psl->a); psl->a = NULL; } psl->size = psl->capacity = 0; } //查找 - 找到返回下标，找不到返回-1 int SeqListFind(SLT* psl, SQDataType x) { assert(psl); int i = 0; for (i = 0; i < psl->size; i++) { if (psl->a[i] == x) { return i; } } return -1; } //从某个位置插入，但是区间只能在第1个元素之前1个元素到最后1个元素之后1个元素 void SeqListInser(SLT* psl, size_t pos, SQDataType x) { assert(psl); assert(pos > 0 && pos <= psl->size + 1);//因为pos是size_t类型的，所以不用断言它是否小于0了，不过还是建议加上 SeqListCheckCapcity(psl); int start = pos - 1; int end = psl->size - 1; while (start <= end) { psl->a[end + 1] = psl->a[end]; end--; } psl->a[pos - 1] = x; psl->size++; } //从某个位置的值删除 void SeqListErase(SLT* psl, size_t pos) { assert(psl); assert(pos > 0 && pos <= psl->size);//因为pos是size_t类型的，所以不用断言它是否小于0了，不过还是建议加上 size_t start = pos - 1; while (start < psl->size - 1) { psl->a[start] = psl->a[start + 1]; start++; } psl->size--; } //统计当前有多少数据 - 其实不要认为这样没必要，这是一些规范的基本操作 size_t SeqListSize(SLT* psl) { assert(psl); return psl->size; } //修改 size_t SeqListAt(SLT* psl, size_t pos, SQDataType x) { assert(psl); assert(pos > 0 && pos <= psl->size); psl->a[pos - 1] = x; }
Test.c
#include"SeqList.h" void TestSeqList1() { SLT s; //初始化 SeqListInit(&s); //尾插 SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPushBack(&s, 5); SeqListPushBack(&s, 6); SeqListPrint(&s);//显示数据 //头插 SeqListPushFront(&s, -1); SeqListPushFront(&s, -2); SeqListPushFront(&s, -3); SeqListPrint(&s);//显示数据 //从某个值的位置插入 SeqListInser(&s, 1, -4); SeqListPrint(&s);//显示数据 //尾删 SeqListPopBack(&s); SeqListPrint(&s);//显示数据 //头删 SeqListPopFront(&s); SeqListPrint(&s);//显示数据 从某个值的位置删除 SeqListErase(&s, 8); SeqListPrint(&s);//显示数据 //修改 SeqListAt(&s, 1, 3); SeqListPrint(&s);//显示数据 //查找 - 找到返回下标，找不到返回-1 printf("%d\n", SeqListFind(&s, 2)); //统计 printf("%d\n", SeqListSize(&s)); //销毁 SeqListDestory(&s); } int main() { //当然也可以写一个菜单，这里就不写了。但这里有几个注意的点：建议先写函数模块，测试完后没有问题再写菜单是最合适的 TestSeqList1(); return 0; }
💨 结果
⚠ 关于数组越界有几个注意的点
#include<stdio.h> int main02() { int a[10] = { 0 }; a[9] = 10; //a[10] = 10;//err //a[11] = 10;//err a[12] = 10;//ok a[20] = 10;//ok return 0; }
▶ 从以上就可以知道越界不一定报错，系统对越界的检查是抽查的形式，越界读一般是无法检查的；越界写也有可能无法检查，但是如果修改到标志位就会被检查出来
▶ 所谓标志位，就是如果越界写把标志位修改了，它就会报错，但是它不可能把后面的数据都设为标志位并检查，这也是为什么后面的数据无法检查的原因
❓❔ 为什么有了顺序表，还需要有链表这样的数据结构
其实不难想象顺序表一定有一些缺陷，而链表恰恰可以优化缺陷
1️⃣ 中间或头部的插入和删除，需要挪动数据，时间复杂度为O(N)
2️⃣ 增容需要申请空间，拷贝数据，释放旧空间，会有不少的消耗
3️⃣ 增容一般是以2倍的形式进行增长，势必会有一定的空间浪费。例如当前容量为100，增容后容量为200，我们只需要再继续插入5个数据，后面就没有数据了，那么将会浪费95个空间
接下了链表就上场了
