c语言 | 单链表的实现
今天分享的是单链表。准确的说，单链表不算是C语言中的内容，而是属于数据结构的内容，因为它没有新的知识点，只是利用了结构体和指针等的知识。但是它在C语言中应用还是很广泛的，在RTOS中，也是非常多的地方使用到了链表。今天暂时说一下单链表的实现和简单应用，下一节当中再介绍双链表。
首先，要对单链表有个概念。单链表其实是对数组的扩展，数组是为了存储很多个数据而产生的，但是它有两个缺陷，第一个缺陷就是数组里面所有的元素都是同样的类型，为了解决这个问题，产生了结构体。另一个缺陷就是数组的大小在初始后就决定了，并且在后面都不允许改变，为了解决这个问题，于是产生了链表。链表可以认为是长度可变的数组，灵活性比较大。链表是由一个个节点构成，每个节点之间用指针的方式连接起来，有一个头指针用来找到链表中的第一个节点，然后根据指针就可以找到每一个节点。
说明：在本次实验中，使用的是vscode编辑器，编译环境是gcc，不建议使用VC6.0，因为VC6.0使用的c语言标准太老了，很多语法都不支持，并且，VC6.0使用体验极差，没有代码高亮功能等等。所以，推荐使用vscode编辑器，也可以使用windows自带的编译器，打开cmd终端，使用gcc命令编译.c文件，生成.exe可执行文件后执行即可。不过，需要自己先去搭建编译环境，这个可以自行百度。
一、创建节点
struct node
{
int data;
struct node * pNext;
};
struct node* creat_node(int data)
{
struct node*p =(struct node*)malloc(sizeof(struct node));
if(p==NULL)
{
printf("创建节点失败\n");
return NULL;
}
bzero(p,sizeof(struct node));
p->pNext=NULL;
p->data=data;
return p;
}
先定义一个结构体类型，里面有两个成员变量，第一个是要存放的数据，第二个是指向下一个节点的指针。
二、插入节点
创建好节点之后，这个节点还是孤立的节点，并没有连起来，所以我们可以采用插入节点的方法来扩展，同时将节点连起来。节点的插入可以是从头部插入，也可以是从尾部插入，一般不会从中间插入，没有意义，因为插入主要是扩展链表的，没有理由从中间插入。
1、尾部插入
void insert_tail(struct node*pH,struct node*new)
{
struct node*p=pH;
while(p->pNext!=NULL)
{
p=p->pNext;
}
p->pNext=new;
pH->data+=1;
}
尾部插入其实并不难，只要将原来最后的节点连上新插入的节点即可。
2、头部插入
void insert_head(struct node*pH,struct node*new)
{
struct node*p;
p=pH;
new->pNext=p->pNext;
p->pNext=new;
pH->data+=1;
}
头部插入就多一个步骤，首先应该将新节点连上原来的第一个节点，然后让原来的头指针指向新的节点。这个顺序是不能颠倒的。如果你先将头指针与新节点相连，那么原来的第一个节点就被丢掉了，你的新节点就没办法去连接原来的第一个节点了。
三、遍历
通过前面插入节点，已经可以形成一条链表了。那么，如果我想访问这个链表里面每个节点的数据，那么该怎么办呢？这个时候就需要遍历。
void traverse(struct node*pH) //遍历
{
struct node*p;
p=pH;
printf("开始遍历\n");
while(p->pNext!=NULL)
{
printf("%d\n",p->pNext->data);
p=p->pNext;
}
printf("遍历结束\n");
}
遍历就是使用while循环来判断是否找到最后一个节点，在找到最后一个节点之前，依次取出每个节点里的数据，每次循环后，指针p都指向下一个节点。这里有一个小问题就是，如果你取出的是当前指针指向的那个节点的数据，那么当p指向最后一个节点的时候，就会退出while循环，导致丢失了最后一个数据。为了解决这个问题，有两种方法，第一种方法是退出while循环之后再单独处理一下最后这个节点的数据，这种方法可行，但是影响程序的优美，让人觉得是一种补丁，另一种方法就是我总是取当前指针的下一个节点的数据，这样在倒数第二个节点的时候，就已经把最后一个节点的数据取出来了。但是这样又会有一个新问题，就是第一个数据不是取不出了吗？不用担心，我们通常让第一个节点成为“头节点”，不是用户的有效节点，这个头节点可以用来存放这个链表中一共有几个数据，所以，这个头节点还是挺有用的，但是是非必要的。
四、删除节点
前面有插入节点，自然就应该有删除节点。删除节点是会比较麻烦一点，而且根据用户不同的需求，也是不一样的，这里我们只考虑删除指定的数据的节点，可以只删除一个，也可以删除所有。比如希望把链表中值为5的节点全部删除等等。
void delete_node(struct node*pH,int data,int option) //删除指定数据的节点
{
struct node*p=pH;
struct node*pBack=p;
int flag=0;
if(p->pNext==NULL)
{
printf("没有可以删除的有效节点");
}
else
{
pBack=pBack->pNext;
switch (option)
{
case SINGLE_DELETE:
while(p->pNext!=NULL)
{
while (p->pNext->data==data) //找到第一个数据
{
flag=1;
if(p->pNext->pNext==NULL) //该节点是尾节点
{
p->pNext=NULL;
}
else
{
p->pNext=p->pNext->pNext; //重新连线
}
free(pBack);
pH->data-=1;
break;
}
p=pBack;
if(pBack->pNext!=NULL)
{
pBack=pBack->pNext;
}
else
{
if(flag==0)
{
printf("不存在 这样的节点\n");
}
}
}
break;
case MULTIPLE_DELETE:
while (p->pNext!=NULL )
{
while (p->pNext->data==data)
{
flag=1;
if(p->pNext->pNext==NULL) //该节点是尾节点
{
p->pNext=NULL;
pH->data-=1;
break;
}
else
{
p->pNext=p->pNext->pNext; //重新连线
}
free(pBack);
pBack=p->pNext;
pH->data-=1;
}
p=pBack;
if(pBack->pNext!=NULL)
{
pBack=pBack->pNext;
}
else
{
if(flag==0)
{
printf("不存在这样的节点\n");
}
}
}
break;
default:
break;
}
}
}
这个函数花费我的时间是最多的，从构思到编写，然后调试。
这里简要说一下我的思路吧。在这个函数当中，有三个参数，第一个是头指针，用来定位链表，第二个是用户待删除的数据，第三个是选项，用来选择是删除一个还是删除所有。
先来考虑删除一个的情况，同样是使用while循环来判断是否到了最后一个节点，如果不是的话，再判断当前指针的下一个节点的数据是否满足要求，如果满足要求，就改变它们的“连线”，这一部分主要是指针的操作，还得考虑下一个节点是不是尾节点，因为普通节点和尾节点的连线方式是不一样的。找到之后就退出循环。而删除所有就是找到之后不退出循环，继续寻找下一个。另外，还需要注意的是删除节点之后最好释放内存，避免内存泄漏。
简单的理解就是先遍历，然后找数据，找到就改变“连线”。
五、逆序
链表的逆序就是将链表中的数据颠倒一下。
void reverse_linkedlist(struct node *pH)
{
struct node *p=pH->pNext;
struct node *pBack=p;
if ((NULL ==p) || (NULL == p->pNext))
return;
while (p->pNext!=NULL)
{
pBack=p->pNext; //先保存好p后面的值
if(p==pH->pNext) //第一个节点
{
p->pNext=NULL;
}
else
{
p->pNext=pH->pNext; //连上前一个
pH->pNext=p;
}
p=pBack;
}
p->pNext=pH->pNext;
pH->pNext=p;
}
这个可能不是那么好理解。
大致的思路就是，指针p先指向头节点的后一个节点，然后进入while循环遍历。如果是第一个节点，就让它指向NULL，因为第一个节点最终会成为最后一个节点。然后p向移动一个节点，让那个节点指向头指针所连的那个节点，再让头指针指向p。如此循环，
画了一个草图如下
其实，在整个过程当中，头指针总是指向p前一个节点，比如p当前指向了2节点，那么头指针就指向1节点，本来1节点是指向2节点的，但是第一步操作让1节点指向了NULL。然后让2节点指向1节点，头指针再指向p所在位置，也就是2节点，之后p再往后移动一格，重复这样的动作，就能把前面n-1个节点倒序连接起来，但是同样存在一个问题就是当p指向最后一个节点的时候，退出while循环，导致最后一个节点没有连上倒数第二个节点，头指针也没有连上最后一个节点，这就需要自己再添加最后两句代码了。
最后我们可以看一下最终的效果
我们先是创建了5个有效节点，排序为1，2，3，4，5。然后遍历一次，可以正常显示，再把数据为1的节点删除，之后再逆序，最终遍历后输出结果，没有问题。再测试其他的情况，也都没有问题，说明我们的代码实现了预定目标。
总结：其实要写出这样的一个代码框架都是不难的，关键在于调试，没有人可以一遍就写出完美的、符合要求的代码，代码都是调出来的，俗话说三分写，七分调。只要有思路，耐心的去调试，逐渐就能写出符合要求的代码。另外，代码的规范性，可读性也是要注意的。