1. 线性表1.1 线性表线性表(命名L)是相同类型的n个数据元素的有限序列。第 i 个数据元素称i为数据元素a在线性表中的位序表头无前驱 表尾无后继其它都有前驱后继顺序存储实现是顺序表链式存储实是链表顺序存储逻辑上相邻的数据元素存放在⼀段连续物理存储单元中数据元素之间的逻辑关系由物理存储关系体现链式存储逻辑上相邻的数据元素存储在任意的⼀组物理存储单元中数据元素之间的逻辑关系⽤指针来表⽰1.2类型 引用别名 引用变量给已存在变量取了⼀个别名编译器不会为引用变量开辟内存空间引用在C里面与取地址符号相同 引用在定义时必须初始化一个变量可以有多个引用引用一旦引用一个实体再不能引用其他实体2、静态顺序表2.1 结构定义typedef int SqDataType; typedef struct SequenceList // SequenceList 可以简化 { SqDataType arr[Sq_MAX_SIZE]; // 存储数据的静态数组 int size; // 记录顺序表中已经存⼊的数据个数 }SqList;静态顺序表结构定义2.2 了解静态顺序表用固定大小的静态数组来存储数据优点是实现简单缺点是适⽤场景局限#define Sq_MAX_SIZE 10 顺序表的最⼤存储的数据个数3、动态顺序表3.1 结构定义typedef int SqDataType; // 动态顺序表结构定义 typedef struct SequenceList //SequenceList 可以简化 { SqDataType* arr; // 存储数据的动态数组的指针 int size; // 记录顺序表中已经存⼊的数据个数 int capacity; // 动态数组的容量空间的⼤⼩ }SqList;动态顺序表结构定义3.2了解动态顺序表⽤⼀个堆上动态申请的数组来存储数据空间不够了 扩容处理3.3 动态顺序表实现(简)3.3.1 接口函数定义SqList.h头文件 #includestdio.h #includestdlib.h #includestdbool.h #includeassert.htypedefintSqDataType;重命名 数据元素类型typedef struct{|SqDataType* arr;//存储数据的动态数组的指针|intsize;//记录顺序表中已经存⼊的数据个数|intcapacity;//动态数组的容量空间的⼤⼩} SqList;初始化顺序表void SqListInit(SqList* ps); //书上 void SqListInit (SqList s);销毁顺序表void SqListDestroy(SqList* ps);插入数据插入i位 (头插 尾插)void SqListInsert(SqList* ps, int i, SqDataType x); //i位 void SqListPushFront(SqList* ps, SqDataType x); //头插 void SqListPushBack(SqList* ps, SqDataType x); //尾插删除数据 删除中间 头删 尾删SqDataType SqListDelete(SqList* ps, int i); //i位 void SqListPopFront(SqList* ps); //头删 void SqListPopBack(SqList* ps); //尾删返回i下标的值 第一个 值x 的下标不存在-1SqDataType GetElem(SqList* ps, int i); //i下标的值 int LocateElem(SqList* ps, SqDataType x); //第一个 值x 的下标检查顺序表为空否空作true 不空 false 获取有效元素个数 打印bool EmptysqList(SqList* ps); //顺序表空否 int SqListSize(SqList* ps); //获取有效元素个数 void SqListPrint(SqList* ps); //打印3.3.2 实现 SqList.cpp#include SqList.h初始化接口函数void SqListInit(SqList* ps) { assert(ps); ps-arr (SqDataType*)malloc(sizeof(SqDataType) * 4); if (ps-arr NULL) { perror(SqListInit: malloc failed); return; } ps-size 0; ps-capacity 4; }销毁接口函数void SqListDestroy(SqList* ps) { assert(ps); if (ps-arr) { free(ps-arr); ps-arr NULL; ps-capacity 0; ps-size 0; } }插入接口函数头插尾插void SqListInsert(SqList* ps, int i, SqDataType x) { assert(ps); assert(i 0 i ps-size); if (ps-size ps-capacity) { SqDataType* tmp (SqDataType*)realloc(ps-arr, sizeof(SqDataType) * ps-capacity * 2); if (tmp NULL) { perror(malloc failed);return; } ps-arr tmp; ps-capacity * 2; } // j为下标 i 为位序 for (int j ps-size - 1; j i; j--) { ps-arr[j 1] ps-arr[j]; } ps-arr[i] x; ps-size; } //头插 void SqListPushFront(SqList* ps, SqDataType x) { SqListInsert(ps, 0, x); } //尾插 void SqListPushBack(SqList* ps, SqDataType x) { SqListInsert(ps, ps-size, x); }删除接口函数头删尾删SqDataType SqListDelete(SqList* ps, int i) { assert(ps); assert(i 0 i ps-size); SqDataType x ps-arr[i]; for (int j i 1; j ps-size; j) { ps-arr[j - 1] ps-arr[j]; } ps-size--; return x; } //头删 void SqListPopFront(SqList* ps) { SqListDelete(ps, 0); } //尾删 void SqListPopBack(SqList* ps) { SqListDelete(ps, ps-size-1); }返回i下标的值 第一个 值x 的下标不存在-1//下标i的值 SqDataType GetElem(SqList* ps, int i) { assert(ps); assert(i 0 i ps-size); return ps-arr[i]; } //值i的下标 int LocateElem(SqList* ps, SqDataType x) { assert(ps); for (int i 0; i ps-size; i) { if(ps-arr[i] x) return i; } return -1; }检查顺序表为空否空作true 不空 false 获取有效元素个数 打印顺序表元素//检查顺序表为空否空作true 不空 false bool EmptysqList(SqList* ps) { assert(ps); return ps-size 0; } //获取有效元素个数 int SqListSize(SqList* ps) { assert(ps); return ps-size; } //打印顺序表元素 void SqListPrint(SqList* ps) { assert(ps); for (int i 0; i ps-size; i) { printf(%d , ps-arr[i]); }printf(\n); }3.3.3 测试text.cpp#include SqList.hvoid TestSqList1()(初始化)SqList sl; //SqListInit(sl); //cpp SqListInit(sl);(插入测试// 尾插 SqListInsert(sl, 0, 1); SqListInsert(sl, 1, 2); SqListInsert(sl, 2, 3); SqListInsert(sl, 3, 4); SqListInsert(sl, 4, 5); SqListInsert(sl, 5, 6); SqListPrint(sl); // 头插 SqListInsert(sl, 0, 100); SqListPrint(sl); // 中间插入 SqListInsert(sl, 1, 200); SqListPrint(sl);删除测试//删除顺序表第1个位置上的元素 printf(顺序表中有效元素个数为%d \n, SqListSize(sl)); SqListPrint(sl); // 删除末尾的数据 printf(删除的元素是:%d \n, SqListDelete(sl, SqListSize(sl) - 1)); SqListPrint(sl); // 删除中间的数据 printf(删除的元素是:%d \n, SqListDelete(sl, 2)); SqListPrint(sl);返回测试//i 下标的元素 printf(顺序表中第%d个元素是%d\n, 1, GetElem(sl, 1)); SqListPrint(sl); // x值的下标 printf(40 的下标是%d\n, LocateElem(sl, 40)); SqListPrint(sl); SqListDestroy(sl);4.链表4.1 优势及相关概念可以按需申请空间不再需要扩容插入和删除效率高结点存储数据和下一个结点指针头指针: 指向第⼀个结点的指针;尾结点的指针指向空带头结点不带头结点两种结构。头结点⼀个哨兵位,不存有效数据4.2 单链表实现4.2.1 接口函数实现(List.h)#includestdio.h #includestdlib.h#includestdbool.h #includeassert.h头文件typedef int LDataType;重命名类型创建新结点LNode* BuyListNode(int data);初始化LNode* ListInit(); //书上 void ListInit(LinkList L);i位置插入元素x 头插 尾插void ListInsert(LNode* L, int i, LDataType x); void ListPushFront(LNode* L, LDataType x); void ListPushBack(LNode* L, LDataType x);删除i结点用 x 带出结点值 头删 尾删LDataType ListDelete(LNode* L, int i); LDataType ListPopFront(LNode* L); LDataType ListPopBack(LNode* L);判断链表空否bool ListEmpty(LNode* L);打印void ListPrint(LNode* L); //(LinkList* L)获取有效元素个数int ListSize(LNode* L);返回第一个数据 x结点 的地址 反之回NULLLNode* ListLocateElem(LNode* L, LDataType x);返回下标i的结点LNode* ListGetElem(LNode* L, int i);销毁void ListDestroy(LNode* L);4.2.2 实现List.c包含头文件#includeList.h创建新结点LNode* BuyListNode(int data) { LNode* newNode (LNode*)malloc(sizeof(LNode)); if (newNode NULL) { perror(malloc fail); exit(-1); } newNode-data data; newNode-next NULL; return newNode; }初始化LNode* ListInit() { LNode* node BuyListNode(-1); return node; }打印链表void ListPrint(LNode* L) //(LinkList* L) { assert(L); printf(头结点-); LNode* cur L-next; while (cur) { printf(%d-, cur-data); cur cur-next; //后移指针 } printf(NULL\n); }判空bool ListEmpty(LNode* L) { return L-next NULL; }有效元素个数int ListSize(LNode* L) { assert(L); int size 0; LNode* cur L-next; while (cur) { size; cur cur-next; } return size; }i位置插入void ListInsert(LNode* L, int i, LDataType x) { assert(L i 0);//断言头结点非空插入位置非负 int j -1;//从头结点下标 -1开始 LNode* i_1Node L;//i_1Node 用于定位第 i-1 个结点初始指向头结点 while (i_1Node ! NULL j i - 1) { j; i_1Node i_1Node-next; } assert(i_1Node);//如果循环后 i_1Node 为 NULL说明链表长度不够i 越界 LNode* newNode BuyListNode(x); //先将新结点的 next 指向前驱的 next即原第 i 个结点地址可能为 NULL newNode-next i_1Node-next; //再将前驱的 next 指向新结点完成插入 i_1Node-next newNode; }【头插void ListPushFront(LNode* L, LDataType x) { ListInsert(L, 0, x);//相当于在 0 位置插入即头结点的后面 }尾插void ListPushBack(LNode* L, LDataType x) { assert(L); LNode* cur L; while (cur-next) { cur cur-next; } LNode* newNode BuyListNode(x); //将尾结点的 next 指向新结点新结点自动成为新尾 cur-next newNode; }删除结点返回值LDataType ListDelete(LNode* L, int i) { assert(i 0); int j -1; LNode* i_1Node L; while (i_1Node ! NULL j i - 1) { j; i_1Node i_1Node-next; } //检查前驱和前驱的 next 是否存在任一为空说明 i 非法 assert(i_1Node ! NULL i_1Node-next ! NULL); //iNode 指向待删除的第 i 个结点 LNode* iNode i_1Node-next; //将前驱的 next 指向被删结点的下一个结点从链表中移除 iNode i_1Node-next iNode-next; //取出被删数据释放结点内存 LDataType x iNode-data; free(iNode); return x; }头删LDataType ListPopFront(LNode* L) { return ListDelete(L, 0); }尾删LDataType ListPopBack(LNode* L) { assert(L L-next); LNode* cur L; //cur-next 存在 — 当前有后继 //cur-next-next 存在 — 后继的后继存在说明 cur 还不是倒数第二个 //循环退出时cur-next 为尾结点cur 为倒数第二个结点或头结点 while (cur-next cur-next-next) { cur cur-next; } LNode* del cur-next; LDataType x del-data; free(del); cur-next NULL; return x; }按值查找LNode* ListLocateElem(LNode* L, LDataType x) { assert(L); LNode* cur L-next; while (cur) { if (cur-data x) return cur; cur cur-next; } return NULL; }按位查找LNode* ListGetElem(LNode* L, int i) { assert(L i 0); int j 0; LNode* iNode L-next; //遍历直到 iNode 越界或 j 到达 i while (iNode ! NULL j i) { j; iNode iNode-next; } //如果 iNode 为 NULL说明 i 超出链表长度返回 NULL //否则返回第 i 个结点地址 return iNode; }销毁void ListDestroy(LNode* L) { LNode* cur L-next; while (cur) { LNode* next cur-next; //先保存下一个结点地址否则释放后丢失 free(cur); cur next; } free(L); }4.2.3 测试test.c头文件#include List.h手动链一个CreateListLNode* CreateList() { // 创建头结点 LNode* L BuyListNode(-1); // 先快速构造5个结点⽅便测试 LNode* node1 BuyListNode(1); LNode* node2 BuyListNode(2); LNode* node3 BuyListNode(3); LNode* node4 BuyListNode(4); LNode* node5 BuyListNode(5); // 然后通过⼿动的⽅式将结点链接起来 L-next node1; node1-next node2; node2-next node3; node3-next node4; node4-next node5; return L; }TestList1来测试void TestList1() { LNode* LT NULL; LT CreateList(); // 测试打印⽅法和获取结点个数⽅法 printf(链表LT中总共有%d个结点\n, ListSize(LT)); ListPrint(LT); // 测试按值获取 printf(链表中值%d结点为%p\n, 1, ListLocateElem(LT, 1)); // 测试按下标获取 printf(链表中下标%d的结点的值为%d\n, 0, ListGetElem(LT, 0)-data); ListInsert(LT, 5, 6); // 尾插 ListPrint(LT); ListInsert(LT, 2, 30); // 中间插 ListPrint(LT); ListInsert(LT, 0, 0); // 头插 ListPrint(LT); ListDelete(LT, 0); // 头删 ListPrint(LT); ListDelete(LT, 2); // 中间删 ListPrint(LT); ListDelete(LT, 5); // 尾删 ListPrint(LT); // 销毁链表 ListDestroy(LT); }完~走过路过不要错过有错请指出谢谢