单链表

发表于

标题：单链表的基本功能实现

链表实现下面功能

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
39
40
41
//初始化链表   
void InitLinkList(pList* pplist);
//销毁链表
void DestroyLinkList(pList* pplist);
//销毁节点
void Destroy(pList* pplist);
//打印
void PrintList(pList plist);
//尾插
void PushBack(pList* pplist, DataType d);
//尾删
void PopBack(pList* pplist);
//头插
void PushFront(pList* pplist, DataType d);
//头删
void PopFront(pList* pplist);
//查找
pNode Find(pList plist, DataType d);
//指定位置插入
void Insert(pList* pplist, pNode pos, DataType d);
//指定位置删除
void Erase(pList* pplist, pNode pos);
//删除指定元素
void Remove(pList* pplist, DataType d);
//删除所有指定元素
void RemoveAll(pList* pplist, DataType d);
//删除无头单链表的非尾节点（不能遍历链表）
void EraseNotTailNode(pNode pos);
//链表长度
int GetListLength(pList plist);
//递归方法从尾到头打印
void PrintTailToHeadRec(pList plist);
//非递归从尾到头打印
void PrintTailToHead(pList plist);
//在无头单链表的一个节点前插入一个节点（不能遍历链表）
void InsertNotTailNode(pNode pos, int num);
//单链表实现约瑟夫环
pNode JosephCircle(pList* pplist, int num);
//逆置反转单链表
void TailToHeadListWayOne(pList* pplist);
void TailToHeadListWayTwo(pList* pplist);
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 #ifndef __LINKLIST_H__
 #define __LINKLIST_H__
 #include <stdio.h>
 #include <stdlib.h>
 #include <assert.h>
 #include <windows.h>
//定义元素类型
typedef int DataType;	
//链表的定义 
typedef struct Node
{
	DataType data;			//存放数据
	struct Node* next;		//定义一个struct Node类型的指针记录下一个节点的地址
}Node,*pNode,List,*pList;
//初始化链表
void InitLinkList(pList* pplist);
//销毁链表
void DestroyLinkList(pList* pplist);
//销毁节点
void Destroy(pList* pplist);
//打印
void PrintList(pList plist);
//尾插
void PushBack(pList* pplist, DataType d);
//尾删
void PopBack(pList* pplist);
//头插
void PushFront(pList* pplist, DataType d);
//头删
void PopFront(pList* pplist);
//查找
pNode Find(pList plist, DataType d);
//指定位置插入
void Insert(pList* pplist, pNode pos, DataType d);
//指定位置删除
void Erase(pList* pplist, pNode pos);
//删除指定元素
void Remove(pList* pplist, DataType d);
//删除所有指定元素
void RemoveAll(pList* pplist, DataType d);
//删除无头单链表的非尾节点（不能遍历链表）
void EraseNotTailNode(pNode pos);
//链表长度
int GetListLength(pList plist);
//递归方法从尾到头打印
void PrintTailToHeadRec(pList plist);
//非递归从尾到头打印
void PrintTailToHead(pList plist);
//在无头单链表的一个节点前插入一个节点（不能遍历链表）
void InsertNotTailNode(pNode pos, int num);
//单链表实现约瑟夫环
pNode JosephCircle(pList* pplist, int num);
//逆置反转单链表
void TailToHeadListWayOne(pList* pplist);
void TailToHeadListWzyTwo(pList* pplist);
 #endif __LINKLIST_H__

约瑟夫环：约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

  • 关于约瑟夫： Josephus有过的故事：39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓。于是决定了自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀。然后下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
  • 题解如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//单链表实现约瑟夫环
pNode JosephCircle(pList* pplist, int count)
{
	//pre记录被删节点的上一个节点
	pNode pre = NULL;
	//cur记录被删节点
	pNode cur = NULL;
	int ret = 0;
	assert(pplist);
    cur = *pplist;
	while ((*pplist)->next != *pplist)
	{	
		ret = count;
		while (--ret)
		{
			pre = cur;
			cur = cur->next;
		}
		pre->next = cur->next;
		Destroy(&cur);
		cur = pre->next;
	}
	return cur;
}

逆置翻转单链表：

方法一：用三个指针分别为first，second，third分别记录要插入的位置，要插入的节点，要插入节点的下一个节点，用头插将2插在1的前面，然改变first，second，third，继续重复上述操作，直到second指向NULL时结束，再将*pplist = first，逆置结束。
  • 图解：


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
//逆置反转单链表
void TailToHeadListWayOne(pList* pplist)
{
	pNode first = NULL;
	pNode second = NULL;
	pNode third = NULL;
	assert(pplist);
	assert(*pplist);
	if ((*pplist)->next == NULL)
	{
		return;
	}
	first = *pplist;
	second = first->next;
	third = second->next;
	while (second)
	{
		if (first == *pplist)
		{
			first->next = NULL;
		}
		second->next = first;
		first = second;
		second = third;
		if (third != NULL)
		{
			third = third->next;
		}
	}
	*pplist = first;

方法二：相当于创建一个新的链表, 创建一个空指针head，head=NULL, 再用一个cur指针指向pplist，tmp指针指向cur->next；先将cur->next = head，然后更新head = cur，cur = tmp，当tmp不为空时 tmp = tmp->next，直到cur为空时循环结束后再更新pplist, 即 : *pplist = head；
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 TailToHeadListWayTwo(pList* pplist)
{
	pNode head = NULL;
	pNode cur = NULL;
	pNode tmp = NULL;
	assert(pplist);
	assert(*pplist);
	if ((*pplist)->next == NULL)
	{
		return;
	}
	cur = *pplist;
	tmp = cur->next;
	while (cur)
	{
		cur->next = head;
		head = cur;
		cur = tmp;
		if (tmp != NULL)
		{
			tmp = tmp->next;
		}
	}
	*pplist = head;
}

test.c 测试文件

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
 #include "Linklist.h"
void testPushBack()
{
	pList plist;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PopBack(&plist);
	PopBack(&plist);
	PopBack(&plist);
	PopBack(&plist);
	PrintList(plist);
	DestroyLinkList(&plist);
}
void testPushfront()
{
	pList plist;
	InitLinkList(&plist);
	PushFront(&plist, 1);
	PushFront(&plist, 2);
	PushFront(&plist, 3);
	PushFront(&plist, 4);
	PopFront(&plist);
	PopFront(&plist);
	PopFront(&plist);
	PopFront(&plist);
	PrintList(plist);
	DestroyLinkList(&plist);
}
void testInsert()
{
	pNode pos = NULL;
	pList plist;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	pos = Find(plist, 4);
	if (pos != NULL)
	{
		Insert(&plist, pos, 5);
	}
	PrintList(plist);
	DestroyLinkList(&plist);
}
void testErase()
{
	pNode pos = NULL;
	pList plist;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	pos = Find(plist, 2);
	if (pos != NULL)
	{
		Erase(&plist, pos);
	}
	PrintList(plist);
	DestroyLinkList(&plist);
}
void testRemove()
{
	int length = 0;
	pList plist;
	InitLinkList(&plist);
	PushBack(&plist, 2);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PushBack(&plist, 2);
	RemoveAll(&plist, 2);
	length = GetListLength(plist);
	printf("单链表长度为：%d\n", length);
	PrintList(plist);
	DestroyLinkList(&plist);
}
void testEraseNotTailNode()
{
	pList plist;
	pNode newNode = NULL;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PushBack(&plist, 5);
	newNode = Find(plist, 3);
	EraseNotTailNode(newNode);
	PrintList(plist);
	DestroyLinkList(&plist);
}
void testPrintTailToHeadRec()
{
	pList plist;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PushBack(&plist, 5);
	PrintTailToHeadRec(plist);
}
void testPrintTailToHead()
{
	pList plist;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PushBack(&plist, 5);
	PrintTailToHead(plist);
}
void testInsertNotTailNode()
{
	pList plist;
	pNode newNode = NULL;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PushBack(&plist, 5);
	newNode = Find(plist, 3);
	InsertNotTailNode(newNode, 6);
	PrintList(plist);
	DestroyLinkList(&plist);
}
void testJosephCircle()
{
	pList plist;
	pNode head = NULL;
	pNode tail = NULL;
	pNode newNode = NULL;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	head = plist;
	tail = plist;
	while (tail->next && tail)
	{
		tail = tail->next;
	}
	//head = pHead(plist);
	//tail = pTail(plist);
	tail->next = head;
	newNode = JosephCircle(&plist, 3);
	printf("剩余的数字为：%d\n", newNode->data);
	free(plist);
	plist = NULL;
}
void testTailToHeadListWayOne()
{
	pList plist;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PushBack(&plist, 5);
	TailToHeadListWayOne(&plist);
	PrintList(plist);
	DestroyLinkList(&plist);
}
void testTailToHeadListWayTwo()
{
	pList plist;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PushBack(&plist, 5);
	TailToHeadListWayTwo(&plist);
	PrintList(plist);
	DestroyLinkList(&plist);
}
int main()
{
//     testPushBack();
//     testPushfront();
//     testInsert();
//     testErase();
//     testRemove();
//     testEraseNotTailNode();
//     testPrintTailToHead();
//     testPrintTailToHead();
//     testInsertNotTailNode();
//     testJosephCircle();
//     testTailToHeadListWayOne();
//     testTailToHeadListWayTwo();
       system("pause");
    return 0;