目录一、链表介绍二、单链表的实现1.导入头文件并定义链表的结点2.链表打印3.链表插入1链表尾插2链表头插4.链表删除1链表尾删2链表头删5.查找6.指定位置之前插入数据7.在指定位置之后插入数据8.删除pos结点9.删除pos之后的结点10.链表销毁三、完整代码SList.hSList.c一、链表介绍链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。与顺序表不同的是链表是由一个个节点/结点组成的每个结点有两个组成部分当前节点要保存的数据和保存下一个结点的地址指针变量因为链表的每个结点都是独立申请的即需要插入数据时才申请一块结点的空间所以需要通过指针变量保存下一个结点的地址才能从当前结点找到下一个结点。链表的结点也是使用结构体保存假设当前链表保存的数据是整型数据struct SListNode { int data; // 结点数据 struct SListNode* next; // 指针变量用于保存下一个结点的地址 };当我们想保存一个数据时实际上是向操作系统申请了一块内存一般是堆内存每次申请的空间可能连续也可能不连续这个内存不仅要保存整型数据也需要保存下一个结点的地址下一个结点为空时保存的地址为NULL。二、单链表的实现为了养成好习惯我们可以用三个文件来实现链表SList.h定义链表的结点和声明链表的方法、SList.c定义链表的方法、test.c测试链表的方法。1.导入头文件并定义链表的结点先在Slist.h中导入可能使用到的头文件#pragma once #includestdio.h #includestdlib.h #includeassert.h定义链表的结点// 定义结点的结构并给结点中存储的数据类型和结构体起别名 // 存储的数据和下一个结点的指针 typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;2.链表打印在打印链表前需要先创建一个链表所以先在test.c文件中创建几个结点再调用链表打印的方法void SListTest01() { // 链表是由一个一个结点组成先创建几个结点 SLTNode* node1 (SLTNode*)malloc(sizeof(SLTNode)); node1-data 1; SLTNode* node2 (SLTNode*)malloc(sizeof(SLTNode)); node2-data 2; SLTNode* node3 (SLTNode*)malloc(sizeof(SLTNode)); node3-data 3; SLTNode* node4 (SLTNode*)malloc(sizeof(SLTNode)); node4-data 4; // 将四个结点连接起来 node1-next node2; node2-next node3; node3-next node4; node4-next NULL; // 调用链表的打印 SLTNode* plist node1; SLTPrint(plist); }链表打印的方法需要在SList.c中定义并在SList.h中声明。void SLTPrint(SLTNode* phead) { SLTNode* pcur phead; // 定义一个pcur存储链表的结点 while (pcur) // 等价于pcur ! NULL用来判断pcur不为空 { printf(%d-, pcur-data); pcur pcur-next; } printf(NULL\n); }使用pcur保存当前结点判断结点是否为空如果不为空就打印结点中保存的数据并将pcur指向下一个结点直到pcur为空输出NULL换行并结束。3.链表插入和顺序表一样链表的插入也有头插尾插1链表尾插链表尾插有两种情况非空链表和空链表先判断链表是否为空如果是空链表就直接将phead指向新结点如果是非空链表就先找到尾结点再将尾节点和新结点连接起来注意此处传入二级指针才是传址调用**pphead -- *phead 第一个结点*pphead -- plist 指向第一个结点的指针pphead -- plist 指向第一个结点的指针的地址形参 实参实参传入plist代表指向第一个结点的指针的地址对其解引用代表指向第一个结点的指针再次解引用代表第一个结点// 链表插入 void SLTPushBack(SLTNode** pphead, SLTDataType x) // 这里需要用二级指针传入头结点传址 { assert(pphead); // 确保pphead不为空无法对NULL进行解引用 // 申请新结点因为头插和尾插都需要申请结点所以可以将申请结点写成一个函数 SLTNode* newnode SLTBuyNode(x); // 链表尾插存在空链表和非空链表两种情况 // 空链表 if (*pphead NULL) // *pphead代表指向第一个结点的指针为空表示空链表 { *pphead newnode; // 直接将phead指向新结点 } else // 非空链表 { // 找尾结点 SLTNode* ptail *pphead; // 定义一个ptail先指向头结点 while (ptail-next) // 当ptail-next为空时说明ptail是尾节点所以循环条件是ptail-next ! NULL可以省略成ptail-next { ptail ptail-next; } //跳出循环说明ptail指向的结点是尾节点需要将新结点和尾节点连接起来 ptail-next newnode; // ptail-next指向新结点 } }此时需要在test.c文件中测试链表尾插代码是否正确void SListTest02() { SLTNode* plist NULL; SLTPushBack(plist,1); SLTPushBack(plist,2); SLTPushBack(plist,3); SLTPushBack(plist,4); SLTPrint(plist); } int main() { SListTest02(); return 0; }调用几次链表尾插再将链表打印出来结果正确2链表头插头插无需判断是否为空链表直接将新结点的next指针指向第一个结点再将头指针指向新结点即可。void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); // 确保pphead不为空 // 头插无需判断是否为空链表 SListNode* newnode SLTBuyNode(x); // 申请一块新空间用来保存新结点 newnode-next *pphead; // 将新结点的next指针指向当前的头结点 *pphead newnode; // 将头指针指向新结点 }在test.c中测试链表头插void SListTest02() { SLTNode* plist NULL; // 测试头插 SLTPushFront(plist, 1); SLTPushFront(plist, 2); SLTPushFront(plist, 3); SLTPushFront(plist, 4); SLTPrint(plist); } int main() { SListTest02(); return 0; }依次在链表头部插入1、2、3、4打印链表结果正确4.链表删除1链表尾删链表尾删有两种情况链表中只有一个结点和链表中有多个结点。当链表中只有一个结点时直接将链表的一个结点释放并置为空当链表中有多个结点时找到尾结点和尾结点的前一个结点并将尾节点释放并置为空尾节点的前一个结点的next置为空。// 链表删除 void SLTPopBack(SLTNode** pphead) { assert(pphead *pphead); // 因为链表删除时链表中必须有元素所以需要同时判断链表是否为空 // 链表尾删有两种情况链表中只有一个结点和链表有多个结点 if ((*pphead)-next NULL) // -的优先级高于*所以需要加括号。pphead的下一个结点为NULL时说明只有一个结点 { free(*pphead); // 直接将*pphead释放并置为空 *pphead NULL; } else { SLTNode* prev *pphead; // 尾结点的前一个结点 SLTNode* ptail *pphead; // 尾结点 while (ptail-next) // 找尾结点 { prev ptail; // prev指向尾节点当前位置 ptail ptail-next; // 尾节点指向当前结点的后一个结点 } // 跳出循环代表ptail当前指向的结点是尾节点释放尾结点并置为空 free(ptail); ptail NULL; prev-next NULL; // 再将prev-next指向NULL } }在test.c中测试尾删void SListTest02() { SLTNode* plist NULL; SLTPushBack(plist,1); SLTPushBack(plist,2); SLTPushBack(plist,3); SLTPushBack(plist,4); SLTPrint(plist); SLTPopBack(plist); SLTPrint(plist); SLTPopBack(plist); SLTPrint(plist); SLTPopBack(plist); SLTPrint(plist); SLTPopBack(plist); SLTPrint(plist); } int main() { SListTest02(); return 0; }先创建一个链表并插入数据然后执行尾删代码并输出链表结果正确2链表头删void SLTPopFront(SLTNode** pphead) { assert(pphead *pphead); SLTNode* next (*pphead)-next; free(*pphead); *pphead next; }测试头删void SListTest02() { SLTNode* plist NULL; SLTPushBack(plist, 1); SLTPushBack(plist, 2); SLTPushBack(plist, 3); SLTPushBack(plist, 4); SLTPrint(plist); SLTPopFront(plist); SLTPrint(plist); SLTPopFront(plist); SLTPrint(plist); SLTPopFront(plist); SLTPrint(plist); SLTPopFront(plist); SLTPrint(plist); } int main() { SListTest02(); return 0; }运行程序结果正确5.查找定义一个pcur指针存储当前结点的地址当pcur不为空时比较pcur与x的值如果相等就返回pcur;如果不想等pcur就向后移动直到pcur中存储的data与x相等或pcur为空链表遍历结束。如果pcur为空说明当前链表没有要查找的值返回NULL// 查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* pcur phead; while (pcur) { if (pcur-data x) { return pcur; } pcur pcur-next; } return NULL; }测试查找void SListTest02() { SLTNode* plist NULL; SLTPushBack(plist, 1); SLTPushBack(plist, 2); SLTPushBack(plist, 3); SLTPushBack(plist, 4); SLTPrint(plist); SLTNode* find SLTFind(plist, 3); if (find NULL) { printf(没有找到!); } else { printf(找到了!); } } int main() { SListTest02(); return 0; }6.指定位置之前插入数据如果pos和*pphead相等说明是头插直接调用头插的方法如果pos和*pphead不相等就找到pos的前一个指针将newnode与pos连接起来再将pos的前一个指针与newnode连接起来// 在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead *pphead); assert(pos); SLTNode* newnode SLTBuyNode(x); // 若pos *pphead说明是头插 if (pos *pphead) { SLTPushFront(pphead, x); } else { SLTNode* prev *pphead; while (prev-next ! pos) // 当prev-next不等于pos时prev向后移动相等时退出循环 { prev prev-next; } newnode-next pos; prev-next newnode; } }测试void SListTest02() { SLTNode* plist NULL; SLTPushBack(plist, 1); SLTPushBack(plist, 2); SLTPushBack(plist, 3); SLTPushBack(plist, 4); SLTPrint(plist); SLTNode* find SLTFind(plist, 3); SLTInsert(plist, find, 11); SLTPrint(plist); } int main() { SListTest02(); return 0; }在3所在的结点前加一个11编译运行结果正确7.在指定位置之后插入数据首先判断指定位置不为空然后创建一个新结点将新结点与pos之后的结点连接起来再将pos与新结点连接起来// 在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode SLTBuyNode(x); newnode-next pos-next; pos-next newnode; }测试void SListTest02() { SLTNode* plist NULL; SLTPushBack(plist, 1); SLTPushBack(plist, 2); SLTPushBack(plist, 3); SLTPushBack(plist, 4); SLTPrint(plist); SLTNode* find SLTFind(plist, 3); SLTInsertAfter(find, 11); SLTPrint(plist); } int main() { SListTest02(); return 0; }在3所在结点后添加一个结点存储11结果正确8.删除pos结点删除pos结点有两种情况pos结点是头结点或pos结点不是头结点。当pos结点是头结点时直接调用头删方法当pos结点不是头结点时找到pos的前一个结点并将pos的前一个结点与pos后一个结点连接起来再将pos结点释放并置为空即可。// 删除pos结点 void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead *pphead); assert(pos); // pos是头结点时直接调用头删 if (pos *pphead) { SLTPopFront(pphead); } else { SLTNode* prev *pphead; while (prev-next ! pos) { prev prev-next; } prev-next pos-next; free(pos); pos NULL; } }测试void SListTest02() { SLTNode* plist NULL; SLTPushBack(plist, 1); SLTPushBack(plist, 2); SLTPushBack(plist, 3); SLTPushBack(plist, 4); SLTPrint(plist); SLTNode* find SLTFind(plist, 3); SLTErase(plist,find); SLTPrint(plist); } int main() { SListTest02(); return 0; }删除3所在的结点结果正确9.删除pos之后的结点首先确保pos和pos的下一个结点不为空然后定义一个新指针del保存pos下一个结点的地址再将pos与pos的下下个结点连接起来再将del释放并置为空// 删除pos之后的结点 void SLTEraseAfter(SLTNode* pos) { assert(pos pos-next); SLTNode* del pos-next; pos-next pos-next-next; free(del); del NULL; }测试void SListTest02() { SLTNode* plist NULL; SLTPushBack(plist, 1); SLTPushBack(plist, 2); SLTPushBack(plist, 3); SLTPushBack(plist, 4); SLTPrint(plist); SLTNode* find SLTFind(plist, 3); SLTEraseAfter(find); SLTPrint(plist); } int main() { SListTest02(); return 0; }将3所在结点的后一个结点删除结果正确10.链表销毁销毁链表要一个一个结点销毁在销毁第一个结点前先将第一个结点的下一个结点存储到next中使用pcur遍历链表将pcur指向的结点销毁后再将pcur指向next所指的结点循环直到pcur指向空说明链表已经全部销毁// 销毁链表 void SListDestroy(SLTNode** pphead) { assert(pphead *pphead); SLTNode* pcur *pphead; while (pcur) { SLTNode* next pcur-next; free(pcur); pcur next; } *pphead NULL; }测试void SListTest02() { SLTNode* plist NULL; SLTPushBack(plist, 1); SLTPushBack(plist, 2); SLTPushBack(plist, 3); SLTPushBack(plist, 4); SLTPrint(plist); SLTNode* find SLTFind(plist, 3); SListDestroy(plist); SLTPrint(plist); } int main() { SListTest02(); return 0; }将链表销毁打印出来显示链表为NULL成功销毁三、完整代码SList.h#pragma once #includestdio.h #includestdlib.h #includeassert.h // 定义结点的结构并给结点中存储的数据类型和结构体起别名 // 存储的数据和下一个结点的指针 typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; void SLTPrint(SLTNode* phead); // 链表打印 // 链表插入 void SLTPushBack(SLTNode** pphead, SLTDataType x); // 链表尾插 void SLTPushFront(SLTNode** pphead, SLTDataType x); // 链表头插 // 链表删除 void SLTPopBack(SLTNode** pphead); // 链表尾删 void SLTPopFront(SLTNode** pphead);// 链表头删 // 查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); // 在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); // 在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x); // 删除pos结点 void SLTErase(SLTNode** pphead, SLTNode* pos); // 删除pos之后的结点 void SLTEraseAfter(SLTNode* pos); // 销毁链表 void SListDestroy(SLTNode** pphead);SList.c#includeSList.h // 传入链表的头文件 void SLTPrint(SLTNode* phead) { SLTNode* pcur phead; // 定义一个pcur存储链表的结点 while (pcur) // 等价于pcur ! NULL用来判断pcur不为空 { printf(%d-, pcur-data); pcur pcur-next; } printf(NULL\n); } SLTNode* SLTBuyNode(SLTDataType x) { SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode)); //申请结点有两种结果申请成功和申请失败 if (newnode NULL) // malloc申请失败 { perror(malloc fail); // 打印错误信息 exit(1); // 退出程序 } // 程序执行到这里说明申请成功 newnode-data x; newnode-next NULL; return newnode; } // 链表插入 void SLTPushBack(SLTNode** pphead, SLTDataType x) // 这里需要用二级指针传入头结点传址 { assert(pphead); // 确保pphead不为空无法对NULL进行解引用 // 申请新结点因为头插和尾插都需要申请结点所以可以将申请结点写成一个函数 SLTNode* newnode SLTBuyNode(x); // 链表尾插存在空链表和非空链表两种情况 // 空链表 if (*pphead NULL) // *pphead代表指向第一个结点的指针为空表示空链表 { *pphead newnode; // 直接将phead指向新结点 } else // 非空链表 { // 找尾结点 SLTNode* ptail *pphead; // 定义一个ptail先指向头结点 while (ptail-next) // 当ptail-next为空时说明ptail是尾节点所以循环条件是ptail-next ! NULL可以省略成ptail-next { ptail ptail-next; } //跳出循环说明ptail指向的结点是尾节点需要将新结点和尾节点连接起来 ptail-next newnode; // ptail-next指向新结点 } } void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); // 确保pphead不为空 // 头插无需判断是否为空链表 SListNode* newnode SLTBuyNode(x); // 申请一块新空间用来保存新结点 newnode-next *pphead; // 将新结点的next指针指向当前的头结点 *pphead newnode; // 将头指针指向新结点 } // 链表删除 void SLTPopBack(SLTNode** pphead) { assert(pphead *pphead); // 因为链表删除时链表中必须有元素所以需要同时判断链表是否为空 // 链表尾删有两种情况链表中只有一个结点和链表有多个结点 if ((*pphead)-next NULL) // -的优先级高于*所以需要加括号。pphead的下一个结点为NULL时说明只有一个结点 { free(*pphead); // 直接将*pphead释放并置为空 *pphead NULL; } else { SLTNode* prev *pphead; // 尾结点的前一个结点 SLTNode* ptail *pphead; // 尾结点 while (ptail-next) // 找尾结点 { prev ptail; // prev指向尾节点当前位置 ptail ptail-next; // 尾节点指向当前结点的后一个结点 } // 跳出循环代表ptail当前指向的结点是尾节点释放尾结点并置为空 free(ptail); ptail NULL; prev-next NULL; // 再将prev-next指向NULL } } void SLTPopFront(SLTNode** pphead) { assert(pphead *pphead); SLTNode* next (*pphead)-next; free(*pphead); *pphead next; } // 查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* pcur phead; while (pcur) { if (pcur-data x) { return pcur; } pcur pcur-next; } return NULL; } // 在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead *pphead); assert(pos); SLTNode* newnode SLTBuyNode(x); // 若pos *pphead说明是头插 if (pos *pphead) { SLTPushFront(pphead, x); } else { SLTNode* prev *pphead; while (prev-next ! pos) // 当prev-next不等于pos时prev向后移动相等时退出循环 { prev prev-next; } newnode-next pos; prev-next newnode; } } // 在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode SLTBuyNode(x); newnode-next pos-next; pos-next newnode; } // 删除pos结点 void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead *pphead); assert(pos); // pos是头结点时直接调用头删 if (pos *pphead) { SLTPopFront(pphead); } else { SLTNode* prev *pphead; while (prev-next ! pos) { prev prev-next; } prev-next pos-next; free(pos); pos NULL; } } // 删除pos之后的结点 void SLTEraseAfter(SLTNode* pos) { assert(pos pos-next); SLTNode* del pos-next; pos-next pos-next-next; free(del); del NULL; } // 销毁链表 void SListDestroy(SLTNode** pphead) { assert(pphead *pphead); SLTNode* pcur *pphead; while (pcur) { SLTNode* next pcur-next; free(pcur); pcur next; } *pphead NULL; }完