目录单链表定义单链表的初始化单链表的头插尾插函数单链表的头删和尾删函数单链表的查找函数单链表的两种插入函数单链表节点的删除函数单链表的销毁函数单链表定义单链表的每个元素都是结构体类型每个结构体都包含一个整形或需要存储的其他数据类型和一个地址。这个地址是用来存储单链表中的下一个元素的地址的这样就把单链表的每个元素连接起来了。单链表的每个元素存储的空间都是用的时候在堆区用malloc开辟的这样的好处主要有两点1.方便管理可以依照自己的意愿增大或缩小链表的空间2.函数如果在栈区创建了单链表的元素在函数结束时这块内存就会被释放导致更难实现一些增添元素的操作。显而易见的单链表在空间结构上是不连续的在逻辑结构上是连续的。typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;单链表的初始化单链表相比顺序表是不需要初始化的函数的。因为从逻辑上讲顺序表的元素是依赖结构体的指针存储的需要初始化一个结构体而单链表的元素每一个都是一个结构体我们只要保证在存储数据时将这个结构体的地址存储到另外一个结构体中就行了。不过每当在编写存储数据的函数时我们都必须要开辟空间初始化一个结构体指针变量。不如就专门定义一个初始化链表元素------结构体指针的函数。它的参数是一个类型数据因为这个函数主要是为在链表中插入元素的函数服务的所以可以把数据在初始化时顺便存储在节点中。SLTNode* SLTBuyNode(SLTDataType x) { SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode)); if (newnode NULL) { perror(malloc); exit(1); } newnode-data x; newnode-next NULL; return newnode; }单链表的头插尾插函数在写插入数据的函数之前我们必须要明确的是当我们用的是数组时我们查找数组元素的手段是数组名加下标而当我们使用单链表想要访问元素时单链表的第一个元素就起到了相当于数组名的作用只要我们获取了单链表的第一个元素我们就可以单向地从第一个元素遍历到最后一个元素当然如果只知道最后一个元素不能从最后一个元素反向遍历到第一个元素这和单链表元素的结构特点有关。void SLTPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode SLTBuyNode(x); if (NULL *pphead) { *pphead newnode; } else { newnode-next *pphead; *pphead newnode; } }void SLTPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* newnode SLTBuyNode(x); if (NULL *pphead) { *pphead newnode; } else { SLTNode* ptail *pphead; while (ptail-next ! NULL) { ptail ptail-next; } ptail-next newnode; } }在传参时我一定要传入第一个节点的地址一个节点就是一个结构体的地址而节点的地址就是二级指针 pphead因为一旦涉及到首元素的改变例如当链表为空时一旦涉及到插入这个链表的首元素地址就会从NULL变为一个结构体的地址。如果不传入节点的地址的话是无法将首节点从空转化为一个结构体的地址的。首插函数比较简单些首先判断这个链表是否为一个空链表如果是的话就把首节点变为要插入的元素原链表中已有元素我们只需要把插入的这个节点的存储的指针赋值为原先的第一个元素的地址就行。尾插函数的if语句和首插函数时一样的else语句稍有不同关键点在于用指针找到最后一个节点并把最后一个节点存储的地址改为SLTBuyNodex函数创建的节点。单链表的头删和尾删函数重点在于删除单链表中的节点时还是有可能会把单链表的元素从1变为0即首节点的地址从有变为NULL所以传参时需要传入首节点的地址是二级指针。void SLTPopFront(SLTNode** pphead) { //链表不能为空 assert(pphead *pphead); SLTNode* next (*pphead)-next; //- 优先级高于* free(*pphead); *pphead next; }void SLTPopBack(SLTNode** pphead) { assert(pphead*pphead); if ((*pphead)-next NULL) { free(*pphead); *pphead NULL; } //想要找到最后一个节点的指针并释放 //把倒数第二个节点的next改为NULL else { SLTNode* ptail *pphead; SLTNode* p ptail; while (ptail-next) { p ptail; ptail ptail-next; } free(ptail); ptail NULL; p-next NULL; } }头删和尾删涉及到的难点和头插和尾插相似不同点在于要释放内存和置空指针不多赘述。单链表的查找函数该查找函数的作用是通过存储的数据来返回存储该数据的节点对应的地址。SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { assert(phead); SLTNode* prev phead; while (prev ! NULL) { if (prev-data x) { return prev; } prev prev-next; } return NULL; }比较简单。单链表的两种插入函数void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//需要传入首节点的原因是如果在第一位插入则首节点改变 { //找到pos的前一项 把newcode-next改成pos把指向pos的改成newcode assert(*pphead pphead); assert(pos); if (*pphead pos)//目的是改变首节点 { SLTPushFront(pphead, x); } else { SLTNode* prev *pphead; SLTNode* newcode SLTBuyNode(x); while (prev-next ! pos) { prev prev-next; } prev-next newcode; newcode-next pos; } }void SLTInsertAfter(SLTNode* pos,SLTDataType x) { assert(pos); SLTNode* newnode SLTBuyNode(x); //pos - newnode - pos-next newnode-next pos-next; pos-next newnode; }前一种代码比较长相比后一种可以理解为在某一项之前插入一个节点。由于单链表只能单向访问这两种函数传参时前一个函数需要多传入一个参数————首节点地址其实传首节点地址还有一个原因前一种函数相比后一种函数多了一点东西如果该链表为空的话需要把首节点地址赋值为首节点。如果只是为了找到目标节点的前一个节点的话传入首节点一级指针而不传入首节点地址的话也是可以的。单链表节点的删除函数void SLTErase(SLTNode** pphead, SLTNode* pos) { //找到指向pos节点 的 next修改为 pos-next然后free(pos)并把POS置空 assert(pphead *pphead pos); if (*pphead pos) { SLTPopFront(pphead); } else { SLTNode* prev *pphead; while (prev-next ! pos) { prev prev-next; } prev-next pos-next; free(pos); pos NULL; } }void SLTEraseAfter(SLTNode* pos) { assert(pos pos-next); //把pos节点 的 下一个节点 改成 下下个节点 SLTNode* temp pos-next-next; free(pos-next); pos-next temp; temp NULL; }这两个函数还是和之前的函数比较类似使用时需要结合查找函数使用还是需要注意每次操作之后首节点是否有变化如果有变化的话传参时肯定要传首节点的地址二级指针。单链表的销毁函数void SLTDestroy(SLTNode** pphead) { //释放所有空间 SLTNode* prev *pphead; SLTNode* next prev; while (prev ! NULL) { next prev-next; free(prev); prev next; } pphead NULL; }注意点是需要传入首节点的地址要遍历所有节点并且释放置空指针。难度较低。