目录1.线性表2. 顺序表顺序表的结构定义静态版顺序表的结构定义动态版初始化销毁检查容量并扩容尾插头插指定位置插入(在pos处插入x删除指定位置的元素查找返回下标找不到返回 -1打印完整测试示例3. 链表3.1单链表带哨兵位结构定义初始化销毁查找求长度打印插入头插中间插尾插删除头删中间删尾删测试代码3.2单链表不带哨兵位插入删除其他3.3 经典题目练习不带哨兵位3.3.1链表的中间结点3.3.2返回倒数第k个结点3.3.3移除链表所有目标元素3.3.4反转链表3.3.5合并两个有序链表本文概括1、讲述了线性表中顺序表与单链表的基本概念、语法、代码。2、单链表中带哨兵位和不带哨兵位单链表的对比与优劣。3、单链表经典题目练习。1.线性表含义线性表是n个元素的有限序列“线性”表示元素之间是“一对一”的关系像排队一样每个元素最多有一个前驱和一个后继。线性表是逻辑结构物理上通常用两种方式实现实现方式存储结构特点顺序表数组顺序存储内存连续支持随机访问插入删除麻烦链表指针链式存储内存不连续访问慢插入删除方便顺序表示例数组int arr[5] {1,2,3,4,5};链表示例单链表struct Node{ int data; struct Node* next; };注意1.线性表 ≠ 数组。线性表是逻辑结构数组是存储方式之一。2.线性表 ≠ 链表。链表只是实现线性表的一种方式。2. 顺序表概念顺序表是线性表的一种物理存储方式用一段连续的内存空间数组按顺序存储元素。顺序表的结构定义静态版#includestdlib.h typedef int Datatype; #define MXA 10; typedef struct Seqlist{ SLDataType arr[MAX]; //存储数据的静态数组 int size; //存储元素个数 }SL;上述是静态数组一般应用较少主要使用下面讲的动态数组顺序表的结构定义动态版#includestdlib.h typedef int SLDatatype; typedef struct SeqList{ SLDataType* a; // 指向动态开辟的数组 int size; // 实际存放的元素个数 int capacity; // 当前空间最大容量 }t_t;初始化void SLInit(t_t* ps) { ps-a NULL; ps-size 0; ps-capacity 0; }销毁void SLDestory(t_t* ps) { free(ps-a); ps-a NULL; ps-size ps-capacity 0; }检查容量并扩容void SLCheckCapacity(t_t* ps) { if(ps-size ps-capacity) { int new_capacity ps-capacity 0 ? 4 : ps-capacity*2; SLDataType* tmp (SLDataType*)realloc(ps-a,new_capacity * szieof(SLDataType)); if(tmp NULL) { perror(realloc); exit(1); } ps-a tmp; ps-capacity new_capacity; }尾插void SLPushBack(t_t* ps , SLDataType x) { SLCheckCapacity(ps); ps-a[ps-size] x; }头插void SLPushBack(t_t* ps , SLDataType x) { SLCheckCapacity(ps); //从后往前移腾出一个位置 for(int i ps-size;i 0;i--) { ps-a[i] ps-a[i - 1]; } ps-a[0] x; ps-size; }指定位置插入(在pos处插入xvoid SLInsert(t_t* ps , int pos , SLDataType x) { if(pos 0 || pos ps-size) { printf(插入位置非法\n); return; } SLCheckCapacity(ps); for(int i ps-size;i pos;i--) { ps-a[i] ps-a[i - 1]; } ps-a[pos] x; ps-size; }删除指定位置的元素void SLErase(t_t* ps , int pos) { if(pos 0 || pos ps-size) { printf(删除位置非法\n); return; } for(int i pos ; i ps-size - 1;i) { ps-a[i] ps-a[i 1]; } ps-size--; }查找返回下标找不到返回 -1int SLFind(t_t* ps , SLDataType x) { for(int i 0 ; i ps-size ; i) { if(ps-a[i] x) return i; } return -1; }打印void SLDPrint(t_t* ps) { for(int i 0 ; i ps-size ; i) { printf(%d ,ps-a[i]); } printf(\n); }完整测试示例int main() { t_t s; SLInit(s); SLPushBack(s, 1); SLPushBack(s, 2); SLPushFront(s, 0); SLInsert(s, 2, 99); SLPrint(s); // 0 1 99 2 SLErase(s, 1); SLPrint(s); // 0 99 2 printf(find 99: %d\n, SLFind(s, 99)); // 1 SLDestroy(s); return 0; }注意1. 顺序表就是数组数组是物理存储顺序表是逻辑结构用数组实现而已。2. size 等于 capacitysize 是实际元素个数capacity 是容量 size capacity3. 扩容直接用 ps-a realloc(...)覆盖原指针必须使用临时指针接收失败保留原指针防止内存泄漏。3. 链表3.1单链表带哨兵位含义链表是一种物理上不连续、逻辑上连续的线性数据结构。它通过指针把一个个结点串起来每个结点存数据同时存指向下一个结点的地址。结构定义#includestdio.h #includestdlib.h #includeassert.h typedef int LDataType; typedef struct ListNode { LDataType* data; struct ListNode* next; }LNode;两种单链表如图所示有无哨兵位头结点哨兵位头指针代码复杂度有不会因插入删除而改变低边界统一无可能改变需要二级指针或返回值高头插/头删要特判初始化LNode* ListNode_Init(LDataType data) { LNode* Newnode (LNode*)malloc(sizeof(LNode)); if (Newnode NULL) { printf(内存开辟失败\n); exit(-1); } Newnode-data data; Newnode-next NULL; return Newnode; }销毁void ListNode_Destory(LNode* L) { assert(L); // 释放有效结点 LNode* cur L-next; while (cur) { LNode* tmp cur-next; free(cur); cur tmp; } // 释放哨兵位 free(L); }查找LNode* ListNode_Find(LNode* L, LDataType val) { assert(L); LNode* cur L-next; while (cur) { if (cur-data val) return cur; cur cur-next; } return NULL; }求长度// 求长度 int ListNode_Length(LNode* L) { assert(L); LNode* cur L-next; int count 0; while (cur) { count; cur cur-next; } return count; }打印void ListNode_Print(LNode* L) { assert(L); printf(头结点-); LNode* cur L-next; while (cur) { printf(%d-, cur-data); cur cur-next; } printf(NULL); printf(\n); }插入头插中间插尾插// 在下标 i 的位置插入元素 x void ListNode_Insert(LNode* L, int i, LDataType x) { assert(L); assert(i 0); // 找 i-1 结点 LNode* cur L; int j -1; while (j i - 1 cur) { j; cur cur-next; } // 插入位置不合法结束 if (cur NULL) return; LNode* New_Node ListNode_Init(x); New_Node-next cur-next; cur-next New_Node; }删除头删中间删尾删// 删除下标为 i 的结点 void ListNode_Delete(LNode* L, int i) { assert(L); assert(i 0); // 找 i-1 结点 LNode* cur L; int j -1; while (j i - 1 cur) { j; cur cur-next; } // 删除位置不合法结束 if (cur NULL || cur-next NULL) return; LNode* tmp cur-next; cur-next cur-next-next; free(tmp); }测试代码int main() { LNode* L ListNode_Init(-1); ListNode_Insert(L, 0 , 0); ListNode_Insert(L, 1 , 1); ListNode_Insert(L, 2 , 2); ListNode_Insert(L, 3 , 3); ListNode_Insert(L, 4 , 4); printf(--创建单链表--\n); ListNode_Print(L); printf(--查找元素2--\n); LNode* Find ListNode_Find(L, 2); printf(%d\n, Find-data); printf(--求链表长度--\n); printf(%d\n, ListNode_Length(L)); printf(--插入元素5--\n); ListNode_Insert(L, 5, 5); ListNode_Print(L); printf(--删除元素5--\n); ListNode_Delete(L , 5); ListNode_Print(L); printf(--销毁链表--\n); ListNode_Destory(L); printf(链表已销毁\n); return 0; }对应输出结果如下3.2单链表不带哨兵位插入由于插入需要找下标为 i - 1 的结点当头插时不带哨兵位的单链表的头结点没有前驱因此头插需要单独判断并且改变单链表的头结点。// 插入 // 在下标 i 的位置插入元素 x void ListNode_Insert(LNode* L, int i, LDataType x) { assert(L); assert(i 0); LNode* cur L; if (i 0) { // 头插 LNode* New_Node ListNode_Init(x); New_Node-next cur; L New_Node; }else { // 中间插 尾插 int j 0; while (j i - 1 cur) { // 找 i-1 结点 j; cur cur-next; } // 插入位置不合法结束 if (cur NULL) return; LNode* New_Node ListNode_Init(x); New_Node-next cur-next; cur-next New_Node; } }删除删除的理由同上删除时需要找到下标为 i - 1的结点当头删时不带哨兵位的单链表的头结点没有前驱因此头删需要单独判断并且改变单链表的头结点。// 删除下标为 i 的结点 void ListNode_Delete(LNode* L, int i) { assert(L); assert(i 0); LNode* cur L; if (i 0) {// 头删 L L-next; free(cur); return; }else {// 找 i-1 结点 int j 0; while (j i - 1 cur) { j; cur cur-next; } // 删除位置不合法结束 if (cur NULL || cur-next NULL) return; LNode* tmp cur-next; cur-next cur-next-next; free(tmp); } }其他初始化销毁查找求长度打印等不带哨兵位的单链表与带的单链表代码整体思路与写法基本一致不过要注意起始操作的结点可能不同注意区分。3.3 经典题目练习不带哨兵位操作的单链表结构// 不带哨兵位的单链表 struct ListNode { int val; struct ListNode *next; };3.3.1链表的中间结点方法快慢指针快指针一次走两步慢指针一次走一步。struct ListNode* middleNode(struct ListNode* head) { // 排查空链表 if(head NULL) { return NULL; } // 快慢指针 struct ListNode* Slow head; struct ListNode* Fast head; // Fast ! NULL 和 Fast-next ! NULL 的顺序不能对调 while(Fast ! NULL Fast-next ! NULL) { Slow Slow-next; Fast Fast-next-next; } return Slow; }3.3.2返回倒数第k个结点方法快慢指针快的指针先走差距步然后快慢指针再同时走。int kthToLast(struct ListNode* head, int k) { // 排查空指针 if(head NULL) { return -1; } struct ListNode* Slow head; struct ListNode* Fast head; int tmp k; // 让块指针先走 k 步 while(tmp--) { Fast Fast-next; } // 同时走 while(Fast) { Slow Slow-next; Fast Fast-next; } return Slow-val; }3.3.3移除链表所有目标元素方法创建头结点双指针struct ListNode* removeElements(struct ListNode* head, int val) { // 排查空链表 if(head NULL) { return NULL; } // 创建头结点 struct ListNode* pos (struct ListNode*)malloc(sizeof(struct ListNode)); pos-next head; struct ListNode* prev pos; // cur 的前驱 struct ListNode* cur head; while(cur) { if(cur-val val) { prev-next cur-next; free(cur); cur prev-next; }else{ cur cur-next; prev prev-next; } } struct ListNode* New_head pos-next; free(pos); // pos可以不用置空因为出了函数生命周期就结束 return New_head; }3.3.4反转链表方法不断取原链表的头结点头插到新结点。struct ListNode* reverseList(struct ListNode* head) { // 排查空链表 if(head NULL) { return NULL; } // 创建新的链表 struct ListNode* new_head (struct ListNode*)malloc(sizeof(struct ListNode)); new_head-next NULL; struct ListNode* cur head; while(cur) { // 拷贝结点 struct ListNode* tmp cur; // cur 先走 cur cur-next; // 再把先前拷贝的结点头插到新链表 tmp-next new_head-next; new_head-next tmp; } return new_head-next; }3.3.5合并两个有序链表方法派空表比大小插入剩余尾插struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1 NULL) return list2; if(list2 NULL) return list1; // 创建新链表 头结点 尾结点 struct ListNode* head NULL,*tail NULL; while(list1 list2) { // 按从小到大顺序插入 if(list1-val list2-val) { if(tail NULL) { head tail list1; }else { tail-next list1; tail tail-next; } list1 list1-next; }else{ if(tail NULL) { head tail list2; }else { tail-next list2; tail tail-next; } list2 list2-next; } } // 剩余的尾插 if(list1) { tail-next list1; } if(list2) { tail-next list2; } return head; }最后感谢阅读欢迎大家交流与指正。
目录1.线性表2. 顺序表顺序表的结构定义静态版顺序表的结构定义动态版初始化销毁检查容量并扩容尾插头插指定位置插入(在pos处插入x删除指定位置的元素查找返回下标找不到返回 -1打印完整测试示例3. 链表3.1单链表带哨兵位结构定义初始化销毁查找求长度打印插入头插中间插尾插删除头删中间删尾删测试代码3.2单链表不带哨兵位插入删除其他3.3 经典题目练习不带哨兵位3.3.1链表的中间结点3.3.2返回倒数第k个结点3.3.3移除链表所有目标元素3.3.4反转链表3.3.5合并两个有序链表本文概括1、讲述了线性表中顺序表与单链表的基本概念、语法、代码。2、单链表中带哨兵位和不带哨兵位单链表的对比与优劣。3、单链表经典题目练习。1.线性表含义线性表是n个元素的有限序列“线性”表示元素之间是“一对一”的关系像排队一样每个元素最多有一个前驱和一个后继。线性表是逻辑结构物理上通常用两种方式实现实现方式存储结构特点顺序表数组顺序存储内存连续支持随机访问插入删除麻烦链表指针链式存储内存不连续访问慢插入删除方便顺序表示例数组int arr[5] {1,2,3,4,5};链表示例单链表struct Node{ int data; struct Node* next; };注意1.线性表 ≠ 数组。线性表是逻辑结构数组是存储方式之一。2.线性表 ≠ 链表。链表只是实现线性表的一种方式。2. 顺序表概念顺序表是线性表的一种物理存储方式用一段连续的内存空间数组按顺序存储元素。顺序表的结构定义静态版#includestdlib.h typedef int Datatype; #define MXA 10; typedef struct Seqlist{ SLDataType arr[MAX]; //存储数据的静态数组 int size; //存储元素个数 }SL;上述是静态数组一般应用较少主要使用下面讲的动态数组顺序表的结构定义动态版#includestdlib.h typedef int SLDatatype; typedef struct SeqList{ SLDataType* a; // 指向动态开辟的数组 int size; // 实际存放的元素个数 int capacity; // 当前空间最大容量 }t_t;初始化void SLInit(t_t* ps) { ps-a NULL; ps-size 0; ps-capacity 0; }销毁void SLDestory(t_t* ps) { free(ps-a); ps-a NULL; ps-size ps-capacity 0; }检查容量并扩容void SLCheckCapacity(t_t* ps) { if(ps-size ps-capacity) { int new_capacity ps-capacity 0 ? 4 : ps-capacity*2; SLDataType* tmp (SLDataType*)realloc(ps-a,new_capacity * szieof(SLDataType)); if(tmp NULL) { perror(realloc); exit(1); } ps-a tmp; ps-capacity new_capacity; }尾插void SLPushBack(t_t* ps , SLDataType x) { SLCheckCapacity(ps); ps-a[ps-size] x; }头插void SLPushBack(t_t* ps , SLDataType x) { SLCheckCapacity(ps); //从后往前移腾出一个位置 for(int i ps-size;i 0;i--) { ps-a[i] ps-a[i - 1]; } ps-a[0] x; ps-size; }指定位置插入(在pos处插入xvoid SLInsert(t_t* ps , int pos , SLDataType x) { if(pos 0 || pos ps-size) { printf(插入位置非法\n); return; } SLCheckCapacity(ps); for(int i ps-size;i pos;i--) { ps-a[i] ps-a[i - 1]; } ps-a[pos] x; ps-size; }删除指定位置的元素void SLErase(t_t* ps , int pos) { if(pos 0 || pos ps-size) { printf(删除位置非法\n); return; } for(int i pos ; i ps-size - 1;i) { ps-a[i] ps-a[i 1]; } ps-size--; }查找返回下标找不到返回 -1int SLFind(t_t* ps , SLDataType x) { for(int i 0 ; i ps-size ; i) { if(ps-a[i] x) return i; } return -1; }打印void SLDPrint(t_t* ps) { for(int i 0 ; i ps-size ; i) { printf(%d ,ps-a[i]); } printf(\n); }完整测试示例int main() { t_t s; SLInit(s); SLPushBack(s, 1); SLPushBack(s, 2); SLPushFront(s, 0); SLInsert(s, 2, 99); SLPrint(s); // 0 1 99 2 SLErase(s, 1); SLPrint(s); // 0 99 2 printf(find 99: %d\n, SLFind(s, 99)); // 1 SLDestroy(s); return 0; }注意1. 顺序表就是数组数组是物理存储顺序表是逻辑结构用数组实现而已。2. size 等于 capacitysize 是实际元素个数capacity 是容量 size capacity3. 扩容直接用 ps-a realloc(...)覆盖原指针必须使用临时指针接收失败保留原指针防止内存泄漏。3. 链表3.1单链表带哨兵位含义链表是一种物理上不连续、逻辑上连续的线性数据结构。它通过指针把一个个结点串起来每个结点存数据同时存指向下一个结点的地址。结构定义#includestdio.h #includestdlib.h #includeassert.h typedef int LDataType; typedef struct ListNode { LDataType* data; struct ListNode* next; }LNode;两种单链表如图所示有无哨兵位头结点哨兵位头指针代码复杂度有不会因插入删除而改变低边界统一无可能改变需要二级指针或返回值高头插/头删要特判初始化LNode* ListNode_Init(LDataType data) { LNode* Newnode (LNode*)malloc(sizeof(LNode)); if (Newnode NULL) { printf(内存开辟失败\n); exit(-1); } Newnode-data data; Newnode-next NULL; return Newnode; }销毁void ListNode_Destory(LNode* L) { assert(L); // 释放有效结点 LNode* cur L-next; while (cur) { LNode* tmp cur-next; free(cur); cur tmp; } // 释放哨兵位 free(L); }查找LNode* ListNode_Find(LNode* L, LDataType val) { assert(L); LNode* cur L-next; while (cur) { if (cur-data val) return cur; cur cur-next; } return NULL; }求长度// 求长度 int ListNode_Length(LNode* L) { assert(L); LNode* cur L-next; int count 0; while (cur) { count; cur cur-next; } return count; }打印void ListNode_Print(LNode* L) { assert(L); printf(头结点-); LNode* cur L-next; while (cur) { printf(%d-, cur-data); cur cur-next; } printf(NULL); printf(\n); }插入头插中间插尾插// 在下标 i 的位置插入元素 x void ListNode_Insert(LNode* L, int i, LDataType x) { assert(L); assert(i 0); // 找 i-1 结点 LNode* cur L; int j -1; while (j i - 1 cur) { j; cur cur-next; } // 插入位置不合法结束 if (cur NULL) return; LNode* New_Node ListNode_Init(x); New_Node-next cur-next; cur-next New_Node; }删除头删中间删尾删// 删除下标为 i 的结点 void ListNode_Delete(LNode* L, int i) { assert(L); assert(i 0); // 找 i-1 结点 LNode* cur L; int j -1; while (j i - 1 cur) { j; cur cur-next; } // 删除位置不合法结束 if (cur NULL || cur-next NULL) return; LNode* tmp cur-next; cur-next cur-next-next; free(tmp); }测试代码int main() { LNode* L ListNode_Init(-1); ListNode_Insert(L, 0 , 0); ListNode_Insert(L, 1 , 1); ListNode_Insert(L, 2 , 2); ListNode_Insert(L, 3 , 3); ListNode_Insert(L, 4 , 4); printf(--创建单链表--\n); ListNode_Print(L); printf(--查找元素2--\n); LNode* Find ListNode_Find(L, 2); printf(%d\n, Find-data); printf(--求链表长度--\n); printf(%d\n, ListNode_Length(L)); printf(--插入元素5--\n); ListNode_Insert(L, 5, 5); ListNode_Print(L); printf(--删除元素5--\n); ListNode_Delete(L , 5); ListNode_Print(L); printf(--销毁链表--\n); ListNode_Destory(L); printf(链表已销毁\n); return 0; }对应输出结果如下3.2单链表不带哨兵位插入由于插入需要找下标为 i - 1 的结点当头插时不带哨兵位的单链表的头结点没有前驱因此头插需要单独判断并且改变单链表的头结点。// 插入 // 在下标 i 的位置插入元素 x void ListNode_Insert(LNode* L, int i, LDataType x) { assert(L); assert(i 0); LNode* cur L; if (i 0) { // 头插 LNode* New_Node ListNode_Init(x); New_Node-next cur; L New_Node; }else { // 中间插 尾插 int j 0; while (j i - 1 cur) { // 找 i-1 结点 j; cur cur-next; } // 插入位置不合法结束 if (cur NULL) return; LNode* New_Node ListNode_Init(x); New_Node-next cur-next; cur-next New_Node; } }删除删除的理由同上删除时需要找到下标为 i - 1的结点当头删时不带哨兵位的单链表的头结点没有前驱因此头删需要单独判断并且改变单链表的头结点。// 删除下标为 i 的结点 void ListNode_Delete(LNode* L, int i) { assert(L); assert(i 0); LNode* cur L; if (i 0) {// 头删 L L-next; free(cur); return; }else {// 找 i-1 结点 int j 0; while (j i - 1 cur) { j; cur cur-next; } // 删除位置不合法结束 if (cur NULL || cur-next NULL) return; LNode* tmp cur-next; cur-next cur-next-next; free(tmp); } }其他初始化销毁查找求长度打印等不带哨兵位的单链表与带的单链表代码整体思路与写法基本一致不过要注意起始操作的结点可能不同注意区分。3.3 经典题目练习不带哨兵位操作的单链表结构// 不带哨兵位的单链表 struct ListNode { int val; struct ListNode *next; };3.3.1链表的中间结点方法快慢指针快指针一次走两步慢指针一次走一步。struct ListNode* middleNode(struct ListNode* head) { // 排查空链表 if(head NULL) { return NULL; } // 快慢指针 struct ListNode* Slow head; struct ListNode* Fast head; // Fast ! NULL 和 Fast-next ! NULL 的顺序不能对调 while(Fast ! NULL Fast-next ! NULL) { Slow Slow-next; Fast Fast-next-next; } return Slow; }3.3.2返回倒数第k个结点方法快慢指针快的指针先走差距步然后快慢指针再同时走。int kthToLast(struct ListNode* head, int k) { // 排查空指针 if(head NULL) { return -1; } struct ListNode* Slow head; struct ListNode* Fast head; int tmp k; // 让块指针先走 k 步 while(tmp--) { Fast Fast-next; } // 同时走 while(Fast) { Slow Slow-next; Fast Fast-next; } return Slow-val; }3.3.3移除链表所有目标元素方法创建头结点双指针struct ListNode* removeElements(struct ListNode* head, int val) { // 排查空链表 if(head NULL) { return NULL; } // 创建头结点 struct ListNode* pos (struct ListNode*)malloc(sizeof(struct ListNode)); pos-next head; struct ListNode* prev pos; // cur 的前驱 struct ListNode* cur head; while(cur) { if(cur-val val) { prev-next cur-next; free(cur); cur prev-next; }else{ cur cur-next; prev prev-next; } } struct ListNode* New_head pos-next; free(pos); // pos可以不用置空因为出了函数生命周期就结束 return New_head; }3.3.4反转链表方法不断取原链表的头结点头插到新结点。struct ListNode* reverseList(struct ListNode* head) { // 排查空链表 if(head NULL) { return NULL; } // 创建新的链表 struct ListNode* new_head (struct ListNode*)malloc(sizeof(struct ListNode)); new_head-next NULL; struct ListNode* cur head; while(cur) { // 拷贝结点 struct ListNode* tmp cur; // cur 先走 cur cur-next; // 再把先前拷贝的结点头插到新链表 tmp-next new_head-next; new_head-next tmp; } return new_head-next; }3.3.5合并两个有序链表方法派空表比大小插入剩余尾插struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1 NULL) return list2; if(list2 NULL) return list1; // 创建新链表 头结点 尾结点 struct ListNode* head NULL,*tail NULL; while(list1 list2) { // 按从小到大顺序插入 if(list1-val list2-val) { if(tail NULL) { head tail list1; }else { tail-next list1; tail tail-next; } list1 list1-next; }else{ if(tail NULL) { head tail list2; }else { tail-next list2; tail tail-next; } list2 list2-next; } } // 剩余的尾插 if(list1) { tail-next list1; } if(list2) { tail-next list2; } return head; }最后感谢阅读欢迎大家交流与指正。
