进击的小白——知识点：手把手学链表（C语言）

看了挺多关于链表的文章，但都感觉写的不够详细，主要是不够具象，今天自己来写一个图文并茂的，图片主要是对每句代码执行后链表状态的直观反映。

先来介绍关于链表的几个概念：

首节点：存放第一个有效数据的节点。
尾节点：存放最后一个有效数据的节点。
头指针：头节点的数据类型与首节点的数据类型相同，并且头节点是首节点前面那个节点，并不存放数据，头节点的存在只是为了方便链表的操作。
头指针：指向头节点的指针。
尾指针：指向尾节点的指针。

链表操作

节点的构造

typedef struct node
{
	int data;  //数据域，用来存放数据
	struct node *pNext;  //指针域，指向下一个节点
}NODE, *PNODE;  //NODE等价于struct node，PNODE等价于struct node *，用大写是为了与变量区分

链表的创建

int data = 0;
PNODE pHead = (PNODE)malloc(sizeof(NODE));
PNODE pTail = pHead;
pTail->pNext = NULL;
PNODE pNew = (PNODE)malloc(sizeof(NODE));
pNew->data = data;
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;

上面一段代码是链表某个节点的创建过程，下面一句一句来分析（序号对应行数）：

int data = 0;虚拟一个数据域，实际情况下可以用scanf或者已有数据来代替。
PNODE pHead = (PNODE)malloc(sizeof(NODE));定义一个头节点，要用malloc来申请一块内存，详见“进击的小白——知识点：指针和malloc”。
PNODE pTail = pHead;定义一个尾指针（注意是尾指针不是尾节点，区别见开篇），让其指向头节点，当我们需要插入多个节点时，我们需要头节点始终指向链表最开始，那么就需要一个移动的指针始终指向链表的尾部，来指示新节点的插入位置，尾指针就起到这样的作用。
pTail->pNext = NULL;让头节点的pNext指向NULL。这里也可以成pHead->pNext = NULL;。此时链表状态图如下。
PNODE pNew = (PNODE)malloc(sizeof(NODE));定义一个节点用来存放要插入的新节点，用malloc申请一块内存，这边需要注意，每创建一个新节点，都要malloc一次。
pNew->data = data;对新节点的数据域进行赋值。
pTail->pNext = pNew;这段代码最原始的写法应该是pHead->pNext = pNew;，意思是让头节点的pNext指向新节点，但在3中我们说过，头节点需要始终指向链表头部，因此定义了一个移动指针pTail，始终指向链表尾部，来指示新节点的插入位置，因此pTail此时本质上就是pHead。此时链表状态如下。
pNew->pNext = NULL;新节点的pNext指向NULL。
pTail = pNew;让尾指针移动到pNew，pNew成为新的尾节点，此时由于链表中有有效数据的节点只有pNew，因此pNew既是首节点也是尾节点，而pHead是头节点，指向首节点pNew。此时链表的状态如下。

写一个连续的多节点链表的创建：

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
	int num;
	struct node*pNext;
}NODE, *PNODE;

PNODE creat(void)
{
	int n = 1;
	PNODE pHead = NULL, pTail = NULL, pNew = NULL;
	PNODE p = NULL;

	pHead = (PNODE)malloc(sizeof(NODE));
	pTail = pHead;
	pTail->pNext = NULL;    
	
	while (n <= 5)  //创建拥有五个节点的链表
	{
		pNew = (PNODE)malloc(sizeof(NODE));  //这边需要注意，每创建一个新节点，都要malloc一次
		scanf("%d", &pNew->num);
		pTail->pNext = pNew;
		pNew->pNext = NULL;
		pTail = pNew;
		n++;
	}
	
	return pHead;  //将创建好的链表的头指针通过函数返回值的方式返回到主函数
}

void main(void)
{
	......
}

遍历链表

遍历很好理解，先看代码：

/*
include以及链表结构体的定义，同上
*/

PNODE creat(void)
{
	......
}

void traver(PNODE pHead)
{
	PNODE p = pHead->pNext;
	while (p != NULL)
	{
		printf("%d ", p->num);
		p = p->pNext;
	}
}

void main(void)
{
	......
}

10行：遍历函数traver的形参为链表的头指针。
12行：PNODE p = pHead->pNext;定义一个链表指针p，让p指向头节点所指向的首节点（即含有第一个有效数据的节点）。
16行：while循环对节点数据进行遍历，每遍历一个节点，p = p->pNext;p向后移动一个节点的位置。
13行：while的条件p != NULL使p到达尾节点的位置时停止遍历（因为尾节点的pNext指向NULL）。

插入节点

代码实现，后又详细讲解：

/*
include以及链表结构体的定义，同上
*/

PNODE creat(void)
{
	......
}

PNODE insert(PNODE pHead)
{
	int i = 1;
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	PNODE p = pHead->pNext, q = p->pNext;
	
	while (p != NULL && i < 2)
	{
		p = p->pNext;
		q = p->pNext;
		i++;
	}
	
	pNew->num = 10;
	pNew->pNext = q;
	p->pNext = pNew;
	
	return pHead;
}

void main(void)
{
	......
}

10行：insert函数的形参是链表的头指针。
12、16-21行：控制链表遍历到需要插入新节点的位置（2节点的后面，3节点的前面插入新节点），每次循环p指针向后移动一个位置，q指针指向p指向节点后面的节点。遍历结束后，p指向2节点，q指向3节点，链表状态如图所示。
13、23行：定义新节点pNew，分配内存，并对数据域进行赋值。
24行：pNew->pNext = q;让新节点pNew的pNext指向3节点（q指针指向的节点）。链表状态如下。
25行：p->pNext = pNew;让2节点（p指针指向的节点）的pNext指向新节点pNew，完成新节点的插入。链表状态如下。
返回插入节点后的链表的头指针。

删除节点

代码实现，后又详细讲解：

/*
include以及链表结构体的定义，同上
*/

PNODE creat(void)
{
	......
}

PNODE _delete(PNODE pHead)
{
	int i = 1;
	PNODE p = pHead->pNext, q = p->pNext;
	
	while (p != NULL && i < 2)
	{
		p = p->pNext;
		q = p->pNext;
		i++;
	}
	
	p->pNext = q->pNext;
	free(q);
	
	return pHead;
}

void main(void)
{
	......
}

10行：_delete函数的形参是链表的头指针。
12-20行：让p、q定位到要删除的节点（3节点为要删除的节点），p指向2节点，q指向3节点。
22行：p->pNext = q->pNext;让2节点（p指向的节点）的pNext指向3节点（q指向的节点）的下一个节点（4节点），相当于跳过了3节点，这就是删除。此时链表状态如下。
23行：free(q);释放3节点占用的内存，防止内存泄漏，详见“进击的小白——知识点：指针和malloc”。
25行：返回插入节点后的链表的头指针。

冒泡排序法

首先说一下，关于p->next = q->next语句的理解：

p->next作为左值，将其看作一个过程，是个动词，理解为“p的下一个节点是XX”；
q->next作为右值，将其看作一个整体，是个名词，代表一个节点，理解为“p的下一个节点”。

一个十位整数的链表，用冒泡排序法进行排序。
贴代码，链表的生成过程就不写了：

/*
include以及链表结构体的定义，同上
*/

PNODE creat(void)
{
	......
}

PNODE sort(PNODE pHead)
{
	int n = 0, i = 0, j = 0;
	PNODE p = pHead->pNext, q = NULL;
	
	while (p != NULL)
	{
		p = p->pNext;
		n++;
	}
	printf("n = %d\n", n);
	
	
	for (i = 0; i < (n - 1); i++)
	{
		p = pHead;
		q = p->pNext;
		
		for (j = 0; j < (n - i - 1); j++)
		{
			if (q->num > q->pNext->num)
			{
				p->pNext = q->pNext;
				q->pNext = q->pNext->pNext;
				p->pNext->pNext = q;
				q = p->pNext;
			}
			p = p->pNext;
			q = q->pNext;
		}
	}
	
	return pHead;
}

void main(void)
{
	......
}

1行：sort函数的形参是链表的头指针。
15-20行：计算链表中有多少个元素。
13、28-31行：定义两个指针变量p、q，如图，假设要交换的是2节点和3节点，则p指向2节点的前一个节点，q指向2节点。
32行：p->pNext = q->pNext;让p的pNext指向q->pNext节点，链表状态如下。
33行：q->pNext = q->pNext->pNext;让q的pNext指向q->pNext->pNext节点，链表状态如下。
34行：p->pNext->pNext = q;让p->pNext节点（注意此处是q->pNext节点而不是q节点）的pNext指向q节点，链表状态如下。
35行：q = p->pNext;让q指向p->pNext节点，相当于做了一个q指针的移位，因为本来定义p和q的时候就要求这两个指针指向的节点是相邻的，在做了节点交换后，同时需要移动q（因为q指向做交换的两个节点之一，而p没有指向这两个节点）。
最终链表的状态如下。
37-38行：p和q各自向下移动一个指针，继续以上操作（即继续执行两个for循环）。
最终返回链表头指针。

进击的小白——知识点：手把手学链表（C语言）

先来介绍关于链表的几个概念：

链表操作

节点的构造

链表的创建

遍历链表

插入节点

删除节点

冒泡排序法

相关推荐