[数据结构与算法]C语言单链表详解（附加强练习）

c语言的单链表画图理解起来很简单，但是新手往往在代码实现这一块会卡很久，今天系统地整理了单链表基础操作的知识，记下这一篇笔记希望能够对刚开始学链表的人起到一些帮助。

单链表图形化大概长这样：相信很多小伙伴已经看过大概这样子的图了，图形很好理解，就是跟一列火车一样，每个车厢就像是结点，一个连着一个。但要实现到代码里面还是有一点点难入手。

?

链表跟数组很像，就是存储数据的一块地方，不同的是链表内存空间利用率高，各方面更加灵活，而且他的插入删除不需要移动元素，只要改变指针。所以首先来看看链表是什么，其实就是一个结构体，然后里面有数据域和指针域，数据域放东西，指针域指向下一个结构体，以此来把各个结构体连起来成一个链表。

即像这样子定义的结构体：

struct Node
{
?? ?int data;?? ??? ??? ??? ?//数据域?
?? ?struct Node* next;?? ?//指针域?
};

在程序中，链表可以看作就是表头加上许多个结点，因此创建链表首先创建表头，然后创建结点，再将他们连起来就可以了。

那单链表的创建需要什么？我们只需要创建一个表头即是创建了一条链表，所以我们把单链表的创建模块化成一个函数如下：

struct Node* CreatLink()?? ?????????????????//创建一个链表就是创建一个表头?
{
?? ?struct Node* HeadNode=(struct Node*)malloc(sizeof(struct Node));? ? ? ? //动态内存申请
?? ?HeadNode->next=NULL;?? ??? ??? ????????????????//对指针进行初始化，养成习惯?
?? ?return HeadNode;
}

在这里可能会有小伙伴有疑问说为什么这里要用到malloc动态申请内存，我直接定义一个结构体不好吗？当然可以，那样子得到的我们叫静态链表，比如这样

struct Node Node1={data1,NULL};

struct Node Node2={data2,NULL};

struct Node Node3={data3,NULL};

然后我们再让 Node1的指针域指向Node2 ，Node2的指针域指向Node3....一张单链表就这么完成了！这么一看静态链表就很简单，完全不用什么动态申请内存然后结构体指针指来指去的，那为什么我们还要像上面那样做？其实仔细一想就知道了，链表最大的特色就是内存空间利用率高，有多少数据就占多少内存，所以内存是需要的时候实时申请来的，而不是像静态链表这样先全部定义好的；并且链表还要能很容易地增加、删除结点等等，而如果做成静态链表那就没办法很容易地删除结点了（因为结点的删除是靠free()函数来释放掉申请的内存来实现的）。

因此，我们创建链表需要用到动态申请内存。

创建完表头后，我们还需要创建结点，因为链表其实就是表头加上结点来组成的，所以我们把创建结点的函数模块化，如下：

//创建一个结点? ?，参数：结点中的数据

struct Node* CreatNode(int data)
{
?? ?struct Node* NewNode=(struct Node*)malloc(sizeof(struct Node));
?? ?NewNode->data=data;? ? ? ? ? ? ? ? ? ? //数据域为传入的数据
?? ?NewNode->next=NULL;? ? ? ? ? ? ? ? //指针域初始化
?? ?return NewNode;? ? ? ? ? ? ? ? ? ? ? ? //将这个结构体指针返回出去
}?

其中传入这个函数的参数应该为这个结点的数据域，默认情况下结点的指针域指向NULL(初始化)。

接下来我们就来写如何往这个链表里头插入一个结点，这里介绍的叫头插法，就是插到表头后的第一个位置，我们先看一个很简单的示意图：

①----③------②-----④------NULL

其中①是表头，③、②、④都是结点，这就是一个单链表，现在假设我们有一个结点⑤，要插到这个单链表里面，应该怎么做？我们可以这样，把表头指针域指向⑤，然后⑤的指针域指向③，便变成①------⑤-------③------②-----④------NULL这样就完成了一个结点的插入。想必理解这一点，你自己也能写出这个函数了吧，如下所示：

//往链表中插入一个结点， 参数：要插入的那个链表? ?插入结点的数据域

void InsertNode(struct Node* HeadNode,int data)
{
?? ?struct Node* NewNode=CreatNode(data);? ? ? ? ? ? ? ? //创建一个新的结点，数据域从入口参数获得
?? ?NewNode->next=HeadNode->next;? ? ? ? ? ? ? ? ? ? ? ? ? ?//将这个结点指针域指向原本表头后面的第一个结点
?? ?HeadNode->next=NewNode;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //将表头指针域指向这个结点
}

到这里我们对链表最最基本的操作已经有个底了，接下来让我们再来写一个链表删除的函数，一般我们删除信息是根据数据域的内容来选择删除的，因此我们需要做的就是遍历链表，看看哪一个结点的数据域是我们要删的，然后把他前面一个结点的指针域改成指向要删的这个结点的下一个结点，再把要删的这个结点free掉就完事了。这里我还是画出一个小示意图：

①------⑤-------③------②-----④------NULL? ?比如对这个单链表，我们要删除数据域为2的结点，那我们就遍历一遍这个单链表，找到②后，将③的指针域改为指向④，然后将②free掉，这样便完成了对结点的删除。那么具体代码实现就需要一个结点和一个前结点，具体代码可参考如下：

//删除链表中的一个结点? 参数：结点所在的链表? 要删的那个结点的数据
void DeletNodebyAppoint(struct Node* HeadNode,int Appoint)
{
?? ?struct Node* PosNode=HeadNode->next;? ? ? ? ? ? ? ? ? ? ? ? //创建一个标志结点，初始为第一个结点
?? ?struct Node* PosNodeFront=HeadNode;? ? ? ? ? ? ? ? ? ? ? ? ? //创建一个标指结点的前一个结点，初始为表头
?? ?if(PosNode==NULL)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//特殊情况：如果链表为空? 那么显示无法删除? ? ? ?
?? ?{
?? ??? ?printf("无法删除\n");
?? ?}else
?? ?while(PosNode->data!=Appoint)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //开始遍历链表，如果不是所要找的结点，则一步一步往后挪
?? ?{
?? ??? ?PosNodeFront=PosNode;
?? ??? ?PosNode=PosNode->next;
?? ??? ?if(PosNode== NULL)?? ??? ??? ?????????????????????????????????//因为在上一步让PosNode=PosNode->next了,所以这里是到表尾了还没有相关信息?
?? ??? ?{
?? ??? ??? ?printf("没有找到相关信息\n");
?? ??? ??? ?return;?
?? ??? ?}
?? ?}
?? ?PosNodeFront->next=PosNode->next;? ? ? ? ? ? ? ? //把他前面一个结点的指针域改成指向要删的这个结点的下一个结点
?? ?free(PosNode);? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//把要删的这个结点free掉
}

至此我们已经学会了链表的一些大致操作，主要是理解了其中的精髓，那么后续更多的延伸用起来也是会比较容易入手一些。

下面我们来实际操作一下，先写一个打印整个链表的函数，然后用一下增加结点和删除结点，实际地演示一遍，打印链表地函数如下：

//打印（遍历）整个链表, 参数：要打印的链表?
void PrintNode(struct Node* HeadNode)
{
?? ?struct Node* PMove=HeadNode->next;? ? ? ? //创建一个结构体让他用于遍历整个链表，从第一个结点开始
?? ?if(HeadNode->next==NULL)? ? ? ? ? ? ? ? ? ? ? ? ?//如果头节点指针域为空那么让其显示“无数据”
?? ?{
?? ??? ?printf("无数据\n");
?? ?} else
?? ?{
?? ??? ?while(PMove)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //否则开始遍历打印链表
?? ??? ?{
?? ??? ??? ?printf("%d\n",PMove->data);
?? ??? ??? ?PMove=PMove->next;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //每次打印完就让结点往下一个结点走
?? ??? ?}
?? ??? ?printf("\n");
?? ?}
}?

写完了打印链表的函数，我们来写个主函数小练一下，我们直接在主函数里调用已经模块化的函数即可，如下：

int main()
{
?? ?struct Node* list=CreatLink();    //创建一个链表叫list
?? ?InsertNode(list,1);                //往链表list里增加结点 数据为1
?? ?InsertNode(list,2);    
?? ?InsertNode(list,3);
?? ?InsertNode(list,100);    
?? ?PrintNode(list);                    //打印链表list
?? ?DeletNodebyAppoint(list,3);        //删除链表list中数据为3的那个结点
?? ?PrintNode(list);                    //再次打印链表list
?? ?return 0;
}

?编译运行后我们得到这样的结果：

?

至此我们就学会了链表最基础的操作了，而在实际运用中，一般链表存储的数据远远不止这么简单地存一个数，最常见的就是存放一个结构体，比如让你将学生的信息（包含姓名、学号、分数）录入存储到一条链表里面，我们应该如何操作呢？

参考答案： 我们只需将链表结点中的数据域改成我们所需要的结构体，其他的在这个基础上再做修改即可以。这里我们先一个包含学生信息的结构体，然后将结点中的数据域改成这一结构体，如下：

struct student            //包含学生信息的结构体
{
	int Num;              //学号
	long Name[20];        //姓名
	int Score;            //成绩
};

struct Node
{
	struct student data;		//结点中的数据域（换成了包含学生信息的结构体） 
	struct Node* next;	        //指针域 
};

接着我们只需要将刚刚模块化的那些函数，有设计到数据域的改一下就行，第一个是刚刚那个创建结点函数，修改后如下：

//创建结点
struct Node* CreatNode(struct student data)    //将参数类型改为刚刚创建的学生信息结构体
{
	struct Node* NewNode=(struct Node*)malloc(sizeof(struct Node));
	NewNode->data=data;
	NewNode->next=NULL;
	return NewNode;
} 

第二个是刚刚那个插入一个结点的函数，修改后如下：

//插入一个结点，参数：插到哪一条链表，新结点的数据 
void InsertNode(struct Node* HeadNode,struct student data)    //将第二个参数即数据域改成刚刚新建的学生信息结构体
{
	struct Node* NewNode=CreatNode(data);
	NewNode->next=HeadNode->next;
	HeadNode->next=NewNode;	
}

第三个是刚刚那个打印链表的函数，修改后如下：主要是修改了打印的内容

void PrintNode(struct Node* HeadNode)
{
?? ?struct Node* PMove=HeadNode->next;
?? ?printf("号数\t姓名\t分数\n");?
?? ?if(HeadNode->next==NULL)
?? ?{
?? ??? ?printf("该链表中无数据\n");
?? ?} else
?? ?{
?? ??? ?while(PMove)
?? ??? ?{
?? ??? ??? ?printf("%d\t%s\t%d\n",PMove->data.Num,PMove->data.Name,PMove->data.Score);
?? ??? ??? ?PMove=PMove->next;
?? ??? ?}
?? ??? ?printf("\n");
?? ?}
}?

最后一个是删除结点的函数，修改后如下：此处的判断条件是学生学号Num，所以在数据判断那里加多个.Num即可

void DeletNodebyAppoint(struct Node* HeadNode,int Num)
{
	struct Node* PosNode=HeadNode->next;
	struct Node* PosNodeFront=HeadNode;
	if(PosNode==NULL)
	{
		printf("无法删除\n");
	}else
	while(PosNode->data.Num!=Num)
	{
		PosNodeFront=PosNode;
		PosNode=PosNode->next;
		if(PosNode== NULL)			//因为在上一步让PosNode=PosNode->next了 
		{
			printf("没有找到相关信息\n");
			return; 
		}
	}
	PosNodeFront->next=PosNode->next;
	free(PosNode);
}

这样子函数模块化已经修改完成，我们写一个主函数：

int main()
{
	struct Node* list=CreatLink();                    //创建一条链表list
	struct student data;                              //创建一个学生信息结构体
	int i;
	int Num;
	while(1)                                            //写一个循环
	{
	printf("请输入学生的号数 姓名 分数：\n");
	scanf("%d%s%d",&data.Num,data.Name,&data.Score);        //录入学生数据
	InsertNode(list,data);                                  //将录好后的数据导入链表
	printf("继续(Y)Or退出(N)\n");        
	setbuf(stdin,NULL);                //清除一下缓冲区
	i=getchar();                       //接收一个字符，用以判断是继续还是结束
	if(i=='Y' || i=='y')                //如果是Y或者y则继续下一个输入
	{
	}else if(i=='N' || i=='n')            //如果是N或者n则跳出这个循环
	{
		break;	
	}
	}
	PrintNode(list);                    //打印出链表
	printf("输入要删除的学生的号数：\n");
	scanf("%d",&Num);                    //输入要删除的那个学生的号数
	DeletNodebyAppoint(list,Num);	
	PrintNode(list);                    
	return 0;
}

编译运行一下：

?

?我们输入第一个学生的信息，例如：

?当我们输入y则可以继续输入下一个学生信息：
?

?

?当我们完成了所有学生的输入，按下n退出，此时会看到链表中记录的学生信息：

?此时提示你要删除哪一个学生号数，假设我们要删掉4号学生，则输入4得到：

?至此，整个基本功能我们就实现了，通过这个练习，也能够加深对链表一些基本操作的应用。