引入：
很多c语言初学者对数据结构中的链表一块感到有心无力，因为他们不清楚链表的实现原理，以及使用方法，接下来我将对我写的单链表的实现和简单的链表操作的代码进行解读，希望这篇博客对不了解单链表的你有所帮助
一、代码实现所需要的头文件
#include <stdio.h> ? ? ? ?//c语言标准头文件
#include <stdlib.h> ? ? ? //包含为指针申请内存空间的malloc函数的头文件
#include <assert.h> ? ? ? ?//assert断言函数所需头文件
#include <time.h> ? ? ? ? ?//设置随机函数种子所需头文件
?
二、单链表的实现代码
1、单链表的节点
//单链表节点
typedef struct Node? ? ? ? ? ? ? ??
{
?? ?int data;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //链表数据成员
?? ?struct Node* next;? ? ? ? ? ? ? ? //指针域（保存下一个节点的首地址）
}NODE,*NODELINK;
使用typedef起别名的方法的用法有助于我们简化我们的代码，这里的typedef的效果就相当于把struct Node用NODE替换掉，struct Node* 用NODELINK替换掉，当然在下面的代码中也可以继续使用struct Node和struct Node*
2、创建表头
//创建表头
NODELINK creatHeadnode()
{
?? ?NODELINK headnode = (NODELINK)malloc(sizeof(NODE));? ? ? ? ? ? ? ??
?? ?assert(headnode);
?? ?headnode->next = NULL;
?? ?return headnode;
}
我们这里采用有头链表的形式，所谓的有头链表就是头结点为一个没有数据的节点，我们在初始化 的时候不对数据进行初始化就可以了。我们使用malloc函数为结构体指针申请内存，使之能变成一个节点，为新申请的内存空间进行断言处理是一个编程好习惯，它的作用就是当无法为这个指针申请空间的时候，assert函数的这条语句会形成一个断点导致程序中断
3、创建节点
//创建节点
NODELINK creatnode(int data)
{
?? ?NODELINK newnode = (NODELINK)malloc(sizeof(NODE));
?? ?assert(newnode);
?? ?newnode->data = data;
?? ?newnode->next = NULL;
?? ?return newnode;
}
?创建节点和创建表头唯一的不同点就是创建节点对数据进行了初始化
至此，单链表的实现工作就算完成了，我们在主函数只需要创建一个表头，然后为需要插入的数据创建节点，通过下面的插入函数完成节点的插入操作即可
三、单链表的简单操作
对于链表操作而言，想理解的最好方法就是画图，建议大家不理解的地方多画图，把赋值关系理清楚，注意节点的移动，像下面的代码应该就很好理解了
1、头插法插入节点
//头插法插入节点
void insertDataByHead(NODELINK list, int data)
{
?? ?NODELINK newnode = creatnode(data);? ? ? ? ? ? ? ? //创建新节点
?? ?newnode->next = list->next;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //插入操作
?? ?list->next = newnode;
?? ?
}
2、表尾法插入节点?
//表尾法插入
void insertDataByBack(NODELINK list, int data)
{
?? ?
?? ?NODELINK pmove = list;
?? ?while (pmove->next != NULL)? ? ? ? ? ? ? ? ? ? ? ? //要实现表尾插入，必须找到最后一个节点
?? ?{
?? ??? ?pmove = pmove->next;
?? ?}
?? ?NODELINK newnode = creatnode(data);? ? ? ? ? ? ? ? ? ? ? ? //创建新节点
?? ?pmove->next = newnode;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //插入操作的一行代码
}
?3、指定位置插入
//指定位置插入(在postion前面插入data)
void insertDataByAppoin(NODELINK list, int data,int postion)
{
?? ?NODELINK frontnode = list;? ? ? ? ? ? ? ? ? ? ? ? //我们要插入新节点必须知道前后的两个节点
?? ?NODELINK pmove = list->next;
?? ?while (pmove != NULL && pmove->data != postion)
?? ?{
?? ??? ?frontnode = pmove;
?? ??? ?pmove = pmove->next;
?? ?}
?? ?if (pmove == NULL)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //未找到指定位置，无法插入
?? ?{
?? ??? ?printf("未找到指定数据，无法插入！\n");
?? ?}
?? ?else
?? ?{
?? ??? ?NODELINK newnode = creatnode(data);? ? ? ? ? ? ? ? ? ? ? ? //创建新节点
?? ??? ?frontnode->next = newnode;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //实现插入的两行代码
?? ??? ?newnode->next = pmove;?? ?
?? ?}
}??
4、表头删除
//表头删除
void deleteNodeByHead(NODELINK list)
{
?? ?NODELINK deletenode = list->next;? ? ? ? ? ? ? ? //用deletenode保存表头的下一个节点
?? ?if (deletenode == NULL)? ? ? ? ? ? ? ? ? ? ? ? ? ?? //当deletenode为空时，表示表头后面没有节点
?? ?{
?? ??? ?printf("链表为空，无法删除！\n");? ? ? ? ? ? ? ??
?? ??? ?return;
?? ?}
?? ?else
?? ?{
?? ??? ?list->next = deletenode->next;? ? //将表头的下一个节点改为删除节点的下一个节点
?? ??? ?free(deletenode);? ? ? ? ? ? ? ? ? ? ? ? //记得释放掉要删除节点的内存
?? ??? ?deletenode = NULL;? ? ? ? ? ? ? ? ? ? ? ? //将释放后的节点置为空，这也是一个编程好习惯
?? ?}
?? ??
}
?5、表尾法删除
//表尾法删除
void deleteNodeByBack(NODELINK list)
{
?? ?NODELINK frontnode = list;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //定义两个移动的指针
?? ?NODELINK pmove = list->next;
?? ?if (pmove == NULL)? ? ? ? ? ? ? ? ? ? ? ? ? ? //链表为空，无法删除
?? ?{
?? ??? ?printf("链表为空，无法删除！\n");
?? ?}
?? ?else
?? ?{
?? ??? ?while (pmove->next != NULL)? ? ? ? ? ? ? ? //移动指针，寻找表尾节点
?? ??? ?{
?? ??? ??? ?frontnode = pmove;? ? ? ? ? ? ? ? ? ? ? ??
?? ??? ??? ?pmove = pmove->next;
?? ??? ?}
?? ??? ?free(pmove);? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //释放表尾节点
?? ??? ?pmove = NULL;
?? ??? ?frontnode->next = NULL;? ? ? ? ? ? ? ? //将原先的表尾的上一个节点的next指针置为空
?? ?}
}
6、指定位置删除?
//指定位置删除（删除postion数据）
void deleteNodeByAppoin(NODELINK list, int postion)
{
?? ?NODELINK frontnode = list;
?? ?NODELINK backnode = list->next;
?? ?while (backnode != NULL && backnode->data != postion)? ? ? ? ? ? ? ? //寻找指定位置
?? ?{
?? ??? ?frontnode = backnode;
?? ??? ?backnode = backnode->next;
?? ?}
?? ?if (backnode == NULL)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //未找到指定位置，无法删除
?? ?{
?? ??? ?printf("未找到指定位置，无法删除！\n");
?? ?}
?? ?else? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //找到指定位置并完成删除操作
?? ?{
?? ??? ?frontnode->next = backnode->next;
?? ??? ?free(backnode);
?? ??? ?backnode = NULL;
?? ?}
?? ?
}
7、合并两个链表?
//合并两个链表
NODELINK catList(NODELINK L1, NODELINK L2)
{
?? ?NODELINK pmove = L2->next;????????????????????????
?? ?while (pmove)
?? ?{
?? ??? ?insertDataByBack(L1, pmove->data);
?? ??? ?pmove = pmove->next;
?? ?}
?? ?return L1;
}
合并两个链表就是在其中一个链表的后面插入另一个链表的节点（返回值也可以为void）?
8、查找两个链表里面的相同元素
//查找两个链表里面的相同元素
void findSameNumber(NODELINK L1, NODELINK L2, NODELINK L3)
{
?? ?NODELINK pmove1 = L1->next;
?? ?while (pmove1 != NULL)
?? ?{
?? ??? ?NODELINK pmove2 = L2->next;
?? ??? ?while (pmove2 != NULL)
?? ??? ?{
?? ??? ??? ?if (pmove1->data == pmove2->data)
?? ??? ??? ?{
?? ??? ??? ??? ?insertDataByBack(L3, pmove1->data);
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ??? ?pmove2 = pmove2->next;
?? ??? ?}
?? ??? ?pmove1 = pmove1->next;
?? ?}
?? ?
}
用第三个链表保存我们找到的有相同数据的节点（找到后记得用break跳出循环，避免在第三个链表中出现相同的节点）?
9、翻转链表
//翻转链表
void reveseList(NODELINK *list)
{
?? ?NODELINK templist=creatHeadnode();
?? ?NODELINK pmove = (*list)->next;
?? ?while (pmove)
?? ?{
?? ??? ?insertDataByHead(templist,pmove->data);
?? ??? ?pmove = pmove->next;
?? ?}
?? ?*list = templist;
}
?实现原理就是遍历链表，用表头法插入另一个链表，然后用二级指针修改原先链表指针的指向
10、创建有序链表
//创建有序链表
void insertDataBySort(NODELINK list, int data)
{
?? ?NODELINK frontnode = list;
?? ?NODELINK pmove = list->next;
?? ?NODELINK newnode = creatnode(data);
?? ?while (pmove&&pmove->data<data)
?? ?{
?? ??? ?frontnode = pmove;
?? ??? ?pmove = pmove->next;
?? ?}
?? ?if (pmove == NULL)
?? ?{
?? ??? ?frontnode->next = newnode;
?? ?}
?? ?else
?? ?{
?? ??? ?frontnode->next = newnode;
?? ??? ?newnode->next = pmove;?? ?}
}
创建有序链表还是需要定义两个移动的指针，我们这里实现的功能是将节点里面的数据从小到大排列，当我们插入节点遍历链表的时候，当找到第一个大于我们新插入节点的数据的时候停止遍历，然后就可以进行有序插入啦
四、功能测试?
1、测试主函数代码
int main()
{
?? ?srand((unsigned int)time(NULL));?? ??? ?//设置随机数种子，有序插入时要用
?? ?NODELINK list = creatHeadnode();?? ??? ?//创建list链表
?? ?//测试头插法
?? ?for (int i = 1; i < 9; i++)
?? ?{
?? ??? ?insertDataByHead(list, i);
?? ??? ?
?? ?}
?? ?printList(list);
?? ?//测试指定位置插入
?? ?insertDataByAppoin(list, 2, 2);
?? ?printList(list);
?? ?//测试表头法删除
?? ?deleteNodeByHead(list);
?? ?printList(list);
?? ?//测试表尾法删除
?? ?deleteNodeByBack(list);
?? ?printList(list);
?? ?/*测试指定位置删除*/
?? ?deleteNodeByAppoin(list, 5);
?? ?printList(list);
?? ?
?? ?NODELINK list1 = creatHeadnode();?? ??? ?//创建以list1为头结点的链表
?? ?//测试表尾法插入
?? ?for (int i = 4; i < 13; i++)
?? ?{
?? ??? ?insertDataByBack(list1, i);
?? ?}
?? ?printList(list1);?? ?NODELINK list2=creatHeadnode();?? ??? ??? ?//创建以list2为头结点的链表
?? ?//测试找出公用元素
?? ?findSameNumber(list, list1, list2);
?? ?printList(list2);
?? ?//测试链接两个链表
?? ?printList(catList(list, list1));
?? ?//测试反转链表
?? ?reveseList(&list);
?? ?printList(list);
?? ?
?? ?NODELINK list3 = creatHeadnode();?? ??? ?//创建以list3为头结点的链表
?? ?//测试有序插入
?? ?int i = 9;
?? ?while (i != 0)
?? ?{
?? ??? ?insertDataBySort(list3, rand() % 100+1);?? ??? ?//插入九个1到101的随机数
?? ??? ?i--;
?? ??? ?
?? ?}
?? ?printList(list3);
?? ?return 0;
}
2、测试结果
?
理解了的小伙伴不难发现我们的测试结果全部正确，需要借鉴的小伙伴参考上面的代码，建议多画图，多动手，时间一久，你对链表这种数据结构就会变得得心应手了
喜欢c语言和C++的小伙伴欢迎关注我，我们一起学习，一起进步，求关注，求点赞，求评论?
?
?
?
?