一、单链表是什么二、单链表的应用1.单链表节点的结构2.打印链表函数实现3.头插和尾插的函数实现4.开辟空间函数5尾删链表函数实现6头删函数实现7链表查找函数实现8在指定位置之前或之后插入数据9删除与销毁一、单链表是什么单链表的全称是不代头单向不循环链表。代头也叫哨兵位头节点是一种工具性节点没有实际意义。二、单链表的应用1.单链表节点的结构typedef int SLTDateType;//对节点date类新重命名 typedef struct SListNode { SLTDateType date; //数据的存储 struct SListNode* next; }SLTNode;2.打印链表函数实现//打印函数 void SLTPrint(SLTNode* phead) { SLTNode* pcur phead; while (pcur) { printf(%d - , pcur-date); pcur pcur-next; } printf(NULL); printf(\n); }思路解释*函数接受头节点指针保存到phead形参中*为pcur赋值phead保护phead原始值*利用单链表单向行遍历链表进行打印*跳出while一NULL结尾3.头插和尾插的函数实现//头插 void SLTPushHead(SLTNode** pphead, SLTDateType x) { assert(pphead); SLTNode* node0 SLCreat(x); node0-next *pphead;//给新开拓的链表next连上 *pphead node0;//根据地址改值可以改变实参的内容 //首地址变了 } //尾插 void SLTPushBack(SLTNode** pphead, SLTDateType x) { assert(pphead); //*pphead就是第一个节点的之指针 //空链表和非空链表 SLTNode* nodex SLCreat(x); if (*pphead NULL) { *pphead nodex; }else { //寻找最后的地址 SLTNode* ptail *pphead; while (ptail-next) { ptail ptail-next; } ptail-next nodex;//总之就是让while里的NULL为nodex } }思路解释*头插一定会改变phead的实参的内容传递值才能改变实参*尾插是有空链表和非空链表所以穿二级指针来应对空链表要改变头节点的情况*用ptail找到最后的节点来尾插4.开辟空间函数//开辟地址的函数 SLTNode* SLCreat(SLTDateType x) { SLTNode* nodex (SLTNode*)malloc(sizeof(SLTNode)); nodex-date x; nodex-next NULL; return nodex; }5尾删链表函数实现//尾巴删 void SLTPopBack(SLTNode** pphead) { assert(pphead *pphead); //链表只有一个节点 if ((*pphead)-next NULL) { free(*pphead); *pphead NULL; } else { //链表有多个节点时 SLTNode* ptail *pphead; SLTNode* prev *pphead; while (ptail-next) { prev ptail; ptail ptail-next; } free(ptail); ptail NULL; prev-next NULL; } }注意*free之后要置空*分为有一个节点的链表和有多个链表的两种情况6头删函数实现//头删 void SLTPopFront(SLTNode** pphead) { assert(pphead *pphead); SLTNode* next (*pphead)-next;// free(*pphead); *pphead next; }7链表查找函数实现//查找 SLTNode* SLTFind(SLTNode* phead, SLTDateType x) { assert(phead); SLTNode* pcur phead; while (pcur) { if (pcur-date x) { return pcur; } pcur pcur-next; } return NULL; }注意*x是不一定存在的*while循环里加if判断*if判断完跳出或是直接return总结8在指定位置之前或之后插入数据//在指定位置之前 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x) { //默认指定位置存在 assert(pphead *pphead); assert(pos); if (pos *pphead) { SLTPushHead(pphead, x); } else { SLTNode* new SLCreat(x); SLTNode* prev *pphead; while (prev-next ! pos) { prev prev-next; } prev-next new; new-next pos; } } //在指定位置之后扎入 void SLTInsertAfter(SLTNode* pos, SLTDateType x) { assert(pos); SLTNode* new SLCreat(x); new-next pos-next; pos-next new; } A 在pos指定位置之前插入数据*默认指定pos存在且不知空链表*如果插在首节点的前面则会改变首节点指针---导致改变实参直接头插即可*else的情况无非就是在prev和pos的之间插入数据 B 在之后插入数据*单项链表可以直接找到pos后面的指针pos-next9删除与销毁//删除指定位置的内容 void SLErase(SLTNode** pphead, SLTNode* pos) { assert(pphead *pphead); assert(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 SLEraseAfter(SLTNode* pos) { assert(pos pos-next); SLTNode* del pos-next; pos-next del-next; free(del); del NULL; } //销毁链表 void SLTDestroy(SLTNode** pphead) { assert(pphead); SLTNode* pcur *pphead; while (pcur) { SLTNode* next pcur-next; free(pcur); pcur next; } *pphead NULL; }相似巧思1当中的prev起到的保护实参内容的作用2del是pos-next则del-next就是要与pos链接的节点3pcur起到与prev相似的作用next就是储存盒子free之后再赋值总结这是单链表中函数实现的代码多记多练没事打开练一练注意当中的坑笔记结束