KJHの博客

记录&回忆

0%

数据结构单向链表

发表于 更新于 分类于
本文字数： 4.4k 阅读时长 ≈ 4 分钟

链表是一个很重要的数据结构，它由一系列不必在内存中连续存储的结构组成。本文讨论单向链表的基本操作，涉及到链表的创建、尾端添加元素、指定位置插入元素、删除指定单个元素节点、删除指定元素所有节点、删除指定位置节点、顺序，逆序打印节点以及统计结点个数等基础操作。

既然是不连续的内存空间，我们要访问各个元素，就需要通过指针来寻找。链表结构中需要定义数据域和指针域。

1、单向链表的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct _Node
{
	int value;
	struct _Node *pnext;
}Node;
2、创建一个不带表头的单向链表
void createList(Node **ppListNode, int value)
{
	Node *pListNode = NULL;
	pListNode = (Node *)malloc(sizeof(Node));
	assert(pListNode != NULL);

	pListNode->value = value;
	pListNode->pnext = NULL;
	 
	*ppListNode = pListNode;
	 
	return;

}

3、往链表尾端添加元素

3、往链表尾端添加元素 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
异常情况：链表不存在

void addToTail(Node **ppListNode, int value)
{
	Node *pNew = (Node *)malloc(sizeof(Node));
	pNew->value = value;
	pNew->pnext = NULL;

	if (NULL == *ppListNode)  //空链表时，此时创建的是头结点，二重指针
	{
		*ppListNode = pNew;
		return;
	}
	else
	{
		Node *pNode = *ppListNode;
		
		while (pNode->pnext != NULL)
			pNode = pNode->pnext;
	 
		pNode->pnext = pNew;
	}
	return;

}

4、指定位置插入元素
异常情况：

4、指定位置插入元素
异常情况：

1) 链表为空

2) 插入位置为0

3) 插入位置大于链表长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*链表第pos个位置后面插入元素value*/
void insertNode(Node **ppListNode, int pos, int value)
{
	if ((NULL == ppListNode) || (pos < 0))
		return;
	if (NULL == *ppListNode)        //链表为空，直接创建新链表
		createList(ppListNode, value);

	Node *pNode, *pNew;
	pNode = *ppListNode;
	 
	pNew = (Node *)malloc(sizeof(Node));
	pNew->value = value;
	pNew->pnext = NULL;
	 
	/*插入第0个位置，即新元素取代头结点*/
	if (0 == pos)
	{
		pNew->pnext = pNode;
		*ppListNode = pNew;
	 
		return;
	}
	 
	/*寻找第pos个位置的前一个结点pNode*/
	while (--pos)
	{
		pNode = pNode->pnext;
		if (NULL == pNode)
			return;       //插入位置大于链表长度，直接返回
	}
	 
	pNew->pnext = pNode->pnext;
	pNode->pnext = pNew;
	 
	return;

}

5、删除单个指定元素

5、删除单个指定元素

异常情况：

1) 链表为空

2) 待删除元素为头节点元素

3) 元素不存在链表中

需要指出的是，对于单向链表，删除某个节点时，最便捷的方式是先找到该节点的前一个节点，这样有一个异常情况，就是前一个节点已经是链表的尾节点以及链表仅单一非指定删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*删除指定数据结点*/
void deleteValue(Node **ppListNode, int value)
{
	Node *pNode;
	if ((NULL == ppListNode) || (NULL == *ppListNode))
		return;

	if ((*ppListNode)->value == value)     //结点为头结点
	{
		pNode = *ppListNode;
		*ppListNode = pNode->pnext;
		free(pNode);
	 
		return;
	}
	 
	pNode = *ppListNode;
	/*链表仅一个非待删除节点处理，不然下面的while会出错*/
	if (NULL == pNode->pnext)
		return;        
	
	/*寻找该元素的上一个结点pNode*/
	while (pNode->pnext->value != value)
	{
		pNode = pNode->pnext;
		if (NULL == pNode->pnext)
			return;        //没找到，直接返回
	}
	 
	Node *pDel = pNode->pnext;     //pNode的下一节点为待删除节点
	pNode->pnext = pDel->pnext;
	free(pDel);
	 
	return;

}

6、删除链表中所有指定元素

6、删除链表中所有指定元素

上面5只是删除链表中出现的第一个指定元素结点，这里补充删除链表中所有指定元素节点，程序并无多大修改。单次删除元素都需要重新考虑第5点列出的异常情况，所以采用递归来处理，其终止条件就是链表为空或链表遍历结束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*删除链表中所有指定数据结点*/
void deleteAllValue(Node **ppListNode, int value)
{
	Node *pNode;
	if ((NULL == ppListNode) || (NULL == *ppListNode))
		return;

	if ((*ppListNode)->value == value)     //结点为头结点
	{
		pNode = *ppListNode;
		*ppListNode = pNode->pnext;
		free(pNode);
	 
		return deleteAllValue(ppListNode, value);
	}
	 
	pNode = *ppListNode;      
	/*链表仅一个非待删除节点处理，不然下面的while会出错*/
	if (NULL == pNode->pnext)
		return;
	 
	/*寻找该元素的上一个结点pNode*/
	while (pNode->pnext->value != value)
	{
		pNode = pNode->pnext;
		if (NULL == pNode->pnext)
			return;        //没找到，直接返回
	}
	
	Node *pDel = pNode->pnext;     //pNode的下一节点为待删除节点
	pNode->pnext = pDel->pnext;
	free(pDel);
	 
	return deleteAllValue(ppListNode, value);

}

下列测试情况通过：

1) 链表为空

2) 链表仅一个节点，该节点为待删除节点以及为非删除节点

3) 链表中无指定元素

4) 链表所有节点为指定删除元素节点

7、删除指定位置的节点

异常情况：

1) 链表为空

2) 删除位置为头节点位置

3) 删除位置大于链表长度(包含恰好为链表尾节点后面那个节点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*删除指定位置pos的节点*/
void deleteNode(Node **ppListNode, int pos)
{
	if ((NULL == ppListNode) || (NULL == *ppListNode) || (pos < 0))
		return;

	Node *pNode = *ppListNode;
	if (0 == pos)         //头结点位置
	{
		*ppListNode = pNode->pnext;
		free(pNode);
		
		return;
	}
	 
	/*寻找第pos-1位置的节点*/
	while (--pos)
	{
		pNode = pNode->pnext;
		if (NULL == pNode)
			return;    //删除位置大于链表长度
	}
	 
	Node *pDel = pNode->pnext;
	if (NULL == pDel)    //删除位置为链表尾节点后面的那个位置
		return;
	 
	pNode->pnext = pDel->pnext;
	free(pDel);
	 
	return;

}

8、顺序打印链表

/顺序打印链表/
void printNode(Node 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*逆序打印链表*/
void printNodeReverse(Node *pListNode)
{
	if (pListNode)
	{
		printNodeReverse(pListNode->pnext);
		printf("%d\n", pListNode->value);
	}
}
10、返回链表节点个数
int countNode(Node *pListNode)
{
	/*if (NULL == pListNode)
		return 0;
	return 1 + countNode(pListNode->pnext);*/

	int count = 0;
	while (pListNode)
	{
		pListNode = pListNode->pnext;
		++count;
	}
	 
	return count;

}

最后啰嗦几句，实际应用时，并不需要你额外再单独的写一个链表出来，别人已经造好了轮子(STL、Linux以及其他)，我们只管使用就行，最为经典的轮子自然是Linux 内核源码中链表数据结构，简约而不简单。但是我们还是要知道这轮子是怎么转动的，这样我们才能更好地驾驭这些轮子为我们所用。