单链表的详解实现

单链表

结构

单链表结构中有两个数据，一个是存储数据的，还有一个指针指向下一个节点。

该图就是一个简单单链表的结构图。

接口实现

SLNode* CreateNode(SLNDataType x);//申请节点
void SLTprint(SLNode* head);//打印链表
void SLTPushBack(SLNode** pphead, SLNDataType x);//尾插
void SLTPushFront(SLNode** pphead, SLNDataType x);//头插
void SLTPopBack(SLNode** pphead);//尾删
void SLTPopFront(SLNode** pphead);//头删
SLNode* SLTFind(SLNode* phead, SLNDataType x);//查找
SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);//任意位置插入
void SLTErase(SLNode** pphead, SLNode* pos);//任意位置删除
void SLTDestroy(SLNode** pphead);//销毁链表

结构体的定义

typedef int SLNDataType;
typedef struct SListNode
{SLNDataType val;struct SList* next;
}SLNode;

首先，我们需要定义这样一个结构体，用来实现链表。本章禁用数字来实现，想用链表写一些学生信息的朋友们可以参考一下。

申请节点

SLNode* CreateNode(SLNDataType x)
{SLNode* newnode=(SLNode*)malloc(sizeof(SLNode));//动态申请内存SLNode大小即可，存放到SLNode* 的指针中去if (newnode == NULL)//如果申请失败，则提醒一下{perror("malloc fail");exit("-1");}newnode->val = x;//申请成功后，将该数据存放到该指针指向的val中去newnode->next = NULL;//将下一个节点设置为空指针return newnode;//返回值为该节点
}

首先，我们插入一个数据的时候，必须要开辟一个空间，也就是申请一个节点用来存放数据，所以单独封装这个函数来实现这个功能。

链表的打印

void SLTprint(SLNode* head)
{assert(head);//断言保证传入指针非空SLNode* cur = head;while (cur!=NULL)//打印循环{printf("%d->", cur->val);//打印当前指针指向的val值cur = cur->next;//将该指针指向的下一个指针的地址赋给该指针，实现链表的遍历}printf("NULL\n");
}

我们接受该指针，之后检查是否为空，把该指针重新赋给一个SLNode* 类型的cur进入打印循环，循环结束条件为尾指针指向的指针不为空指针即可。

尾插

我们插入删除数据时候，需要注意的一点是，我们需要遍历修改的时一级指针，那么我们就要用二级指针去接受这个参数了。

void SLTPushBack(SLNode** pphead, SLNDataType x)
{assert(pphead);//断言非空SLNode* newnode = CreateNode(x);//将新开辟的节点赋给newnodeif (*pphead == NULL)//链表为空{*pphead = newnode;//直接将newnode赋给头节点}else{SLNode* tmp = *pphead;//将头节点给一个临时变量while (tmp->next != NULL)//遍历循环{tmp = tmp->next;//可实现链表移动从而遍历}tmp->next = newnode;//让最后一个节点指向newnode即可}
}

我们实现尾部插入，有两种情况，首先就是如果该链表为空，也就是头节点指向的是空指针，那么我们直接将新开辟的节点赋给头节点即可，其他的情况，首先需要遍历链表到最后一个节点，然后让最后一个节点指向新开辟的节点即可实现尾部插入。

头插

void SLTPushFront(SLNode** pphead, SLNDataType x)
{assert(pphead);//断言非空SLNode* newnode = CreateNode(x);//将新开辟的节点赋给newnode节点newnode->next = *pphead;//新开辟的节点指向的是pphead节点*pphead = newnode;//newnode成为新的头节点
}

实现头插是十分简单的，直接看代码注释即可

尾删

void SLTPopBack(SLNode** pphead)
{assert(*pphead);//保证头节点不为空指针if ((*pphead)->next == NULL)//仅有一个节点的情况{free(*pphead);//释放掉头节点*pphead = NULL;//并将其赋值为空指针即可}else//多个节点的情况{SLNode* prev = NULL;//双指针移动之实际指针SLNode* tail = *pphead;//双指针移动之遍历指针while (tail->next!= NULL)//遍历循环，结束条件为tail的下一个节点不为空指针{prev = tail;//将遍历指针赋值给实际指针tail = tail->next;//遍历指针向后移动}
//循环结束，此时实际指针指向倒数第二个节点，而遍历指针指向最后一个节点free(tail);//释放掉此时指向最后一个节点的遍历节点tail = NULL;//将释放后的遍历指针赋值为空指针prev->next = NULL;//实际指针变成最后一个指针，最后一个指针指向的是空指针}
}

尾删，我们需要分为两种情况，首先是该链表只有一个头节点，这种情况直接将头节点释放掉在赋值为空指针即可，另外的就是该链表有多个节点，那么此时我们选哟做到的就是，遍历到最后一个节点，之后将该节点释放掉即可，这里我们用双指针的移动来实现释放节点。

头删

void SLTPopFront(SLNode** pphead)
{assert(*pphead);//保证头节点不为空SLNode* tmp = *pphead;//将头节点赋给临时节点(*pphead) = tmp->next;//临时节点也就是头节点指向的下一个节点赋给头节点成为新的头节点free(tmp);//释放掉已经不是头节点的节点tmp = NULL;//将释放掉的节点赋值为空指针
}

头删十分简单，直接看代码注释即可。

查找

SLNode* SLTFind(SLNode* phead, SLNDataType x)
{if (phead == NULL)//头节点为空指针，也就是链表为空无需打印{printf("链表为空无需查找");return NULL;//返回空指针}else//链表不为空{SLNode* cur = phead;//将头节点赋给临时变量curwhile (cur)//遍历循环{if (cur->val== x)//如果遍历的数据是所需要的数据{return cur;//返沪该指针}cur = cur->next;//如果不是，则移动临时变量cur实现链表的遍历}}return NULL;//找完没有，则返回空指针
}

查找的实现也很简单，如果链表为空，那么我们就无需查找，返回空指针即可，不为空，我们遍历找到需要数据存放的节点，之后返回这个节点就可以了，如果遍历完没有找到，就说明不存在该节点返回空指针即可。

任意位置的插入

SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(pphead);//断言非空if (*pphead == pos)//头插情况{SLTPushFront(pphead,x);}else//非头部插入情况{SLNode* newnode = CreateNode(x);//新开辟的节点赋给newnode指针SLNode* cur = *pphead;//头节点给临时变量curwhile (cur->next != pos)//遍历到pos前一个位置{cur = cur->next;//遍历移动}cur->next = newnode;//此时让pos位置前一个节点指向要插入的节点newnode->next = pos;//要插入的节点指向之后的节点，实现链表的完整}
}

首先，如果插入的位置是头节点，那么也就是头插了，如果是其他位置，那么首先需要遍历到该位置的前一个节点，让该节点指向新插入的节点，新插入的节点在指向原来该位置的节点就实现了该位置的数据插入。

任意位置的删除

void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);//断言非空if (*pphead == pos)//头删情况{SLTPopFront(pphead);}else//非头删情况{SLNode* cur = *pphead;//头节点赋给临时变量curwhile (cur->next != pos)//遍历到pos位置的前一个节点循环{cur = cur->next;//临时变量移动，链表的遍历}cur->next = pos->next;//pos位置的前一个节点直线pos的下一个节点free(pos);//释放pospos = NULL;//pos赋值为空指针}
}

首先，也是如果删除的节点是头节点，直接头删即可，不是则遍历到该位置的前一个位置，跳过该位置指向下一个节点，再将该位置节点释放掉即可。

链表的销毁

void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur = *pphead;while (cur){SLNode* pur = cur;cur = cur->next;free(pur);}printf("链表已经成功销毁！");
}

链表的销毁十分简单，遍历释放即可。

代码参考

鄙人不才，大家可以参考一下链表代码的实现

SList.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLNDataType;
typedef struct SListNode
{SLNDataType val;struct SList* next;
}SLNode;
SLNode* CreateNode(SLNDataType x);//申请节点
void SLTprint(SLNode* head);//打印链表
void SLTPushBack(SLNode** pphead, SLNDataType x);//尾插
void SLTPushFront(SLNode** pphead, SLNDataType x);//头插
void SLTPopBack(SLNode** pphead);//尾删
void SLTPopFront(SLNode** pphead);//头删
SLNode* SLTFind(SLNode* phead, SLNDataType x);//查找
SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);//任意位置插入
void SLTErase(SLNode** pphead, SLNode* pos);//任意位置删除
void SLTDestroy(SLNode** pphead);//销毁链表

SList.c

#define  _CRT_SECURE_NO_WARNINGS
#include"SList.h"
SLNode* CreateNode(SLNDataType x)
{SLNode* newnode=(SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("malloc fail");exit("-1");}newnode->val = x;newnode->next = NULL;return newnode;
}
void SLTprint(SLNode* head)
{assert(head);SLNode* cur = head;while (cur!=NULL){printf("%d->", cur->val);cur = cur->next;}printf("NULL\n");
}
void SLTPushBack(SLNode** pphead, SLNDataType x)
{SLNode* newnode = CreateNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLNode* tmp = *pphead;while (tmp->next != NULL){tmp = tmp->next;}tmp->next = newnode;}
}
void SLTPushFront(SLNode** pphead, SLNDataType x)
{SLNode* newnode = CreateNode(x);newnode->next = *pphead;*pphead = newnode;
}
void SLTPopBack(SLNode** pphead)
{assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLNode* prev = NULL;SLNode* tail = *pphead;while (tail->next!= NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}
void SLTPopFront(SLNode** pphead)
{assert(*pphead);SLNode* tmp = *pphead;(*pphead) = tmp->next;free(tmp);tmp = NULL;
}
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{if (phead == NULL){printf("链表为空无需查找");return NULL;}else{SLNode* cur = phead;while (cur){if (cur->val== x){return cur;}cur = cur->next;}}return NULL;
}
SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(pphead);if (*pphead == pos){SLTPushFront(pphead,x);}else{SLNode* newnode = CreateNode(x);SLNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}cur->next = newnode;newnode->next = pos;}
}
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);if (*pphead == pos){SLTPopFront(pphead);}else{SLNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}cur->next = pos->next;free(pos);pos = NULL;}
}
void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur = *pphead;while (cur){SLNode* pur = cur;cur = cur->next;free(pur);}printf("链表已经成功销毁！");
}

test.c

这个文件主要是为了检测链表代码是否有误，用于调试链表。

#define  _CRT_SECURE_NO_WARNINGS
#include"SList.h"
void test1()
{SLNode* S1=NULL;SLTPushBack(&S1, 1);SLTPushBack(&S1, 2);SLTPushBack(&S1, 3);SLTPushBack(&S1, 4);SLTprint(S1);
}
void test2()
{SLNode* S1 = NULL;SLTPushBack(&S1, 1);SLTPushBack(&S1, 2);SLTPushBack(&S1, 3);SLTPushBack(&S1, 4);SLTPushFront(&S1, 4);SLTprint(S1);
}
void test3()
{SLNode* S1 = NULL;SLTPushBack(&S1, 1);SLTPushBack(&S1, 2);SLTPushBack(&S1, 3);SLTPushBack(&S1, 4);SLTPushFront(&S1, 4);SLTPopBack(&S1);SLTprint(S1);
}
void test4()
{SLNode* S1 = NULL;SLTPushBack(&S1, 1);SLTPushBack(&S1, 2);SLTPushBack(&S1, 3);SLTPushBack(&S1, 4);SLTPushFront(&S1, 4);SLTPopBack(&S1);SLTPopFront(&S1);SLTprint(S1);
}
void test5()
{SLNode* S1 = NULL;SLTPushBack(&S1, 1);SLTPushBack(&S1, 2);SLTPushBack(&S1, 3);SLTPushBack(&S1, 4);SLTPushFront(&S1, 5);SLNode* x =SLTFind(S1,3);SLTprint(S1);printf("%d", x->val);}
void test6()
{SLNode* S1 = NULL;SLTPushBack(&S1, 1);SLTPushBack(&S1, 2);SLTPushBack(&S1, 3);SLTPushBack(&S1, 4);SLTPushFront(&S1, 4);SLTInsert(&S1, S1, 5);SLNode* S2 = S1->next;SLTInsert(&S1, S2, 8);SLTprint(S1);
}
void test7()
{SLNode* S1 = NULL;SLTPushBack(&S1, 1);SLTPushBack(&S1, 2);SLTPushBack(&S1, 3);SLTPushBack(&S1, 4);SLTPushFront(&S1, 4);SLTInsert(&S1, S1, 5);SLNode* S2 = S1->next;SLTInsert(&S1, S2, 8);SLTErase(&S1, S1);SLTErase(&S1, S2);SLTprint(S1);
}
void test8()
{SLNode* S1 = NULL;SLTPushBack(&S1, 1);SLTPushBack(&S1, 2);SLTPushBack(&S1, 3);SLTPushBack(&S1, 4);SLTPushFront(&S1, 4);SLTInsert(&S1, S1, 5);SLNode* S2 = S1->next;SLTInsert(&S1, S2, 8);SLTErase(&S1, S1);SLTErase(&S1, S2);SLTprint(S1);SLTDestroy(&S1);
}
int main()
{/*test1();*//*test2();*//*test3();*//*test4();*//*test5();*//*test6();*//*test7();*/test8();return 0;
}

最后谢谢大家观看，以后会奉上更多内容，大家共同进步！