数据结构 单链表

Posted on Edited on In Views: Word count in article: 3.8k Reading time ≈ 38 mins.

一、单链表定义

 单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
 根据第一个节点是否存放数据：分为带头节点(带哨兵位)的单链表与不带头节点（不带哨兵位）的单链表两种

在这里插入图片描述

二、不带头节点的单链表

2.1 单链表结构及接口定义

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
typedef int ElemType;

typedef struct Node
{
	ElemType data;
	struct Node* next;
}ListNode;


ListNode* CreateNode(); // 创建一个单链表节点

void SinListHeadInsert(ListNode **ppHead, ElemType elem); // 头部插入元素

void SinListHeadDelete(ListNode** ppHead); // 头部删除元素

void SinListTailInsert(ListNode** ppHead, ElemType elem); //尾部插入元素

void SinListTailDelete(ListNode** ppHead); //尾部删除元素

void SinListInsert(ListNode** ppHead, int pos, ElemType elem); //插入元素到pos位置,位置从1开始

void SinListDelete(ListNode** ppHead, int pos); //删除pos位置元素,位置从1开始

void SinListPrint(ListNode* pHead); //打印单链表 

int SinListFind(ListNode* pHead, ElemType value); //查找指定值在单链表第一次出现位置，位置从1开始，未找到返回-1 

void Destory(ListNode** ppHead); // 销毁单链表

2.2 创建节点

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* CreateNode(ElemType elem)
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	if (newNode == NULL)  // 开辟空间失败，终止程序
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newNode->data = elem;
	newNode->next = NULL;
	return newNode;
}

2.3 头插元素

在这里插入图片描述

1
2
3
4
5
6
void SinListHeadInsert(ListNode** ppHead, ElemType elem)
{
	ListNode* newNode = CreateNode(elem);
	newNode->next = *ppHead;
	*ppHead = newNode; // 头指针指向新节点
}

2.4 头删元素

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
void SinListHeadDelete(ListNode** ppHead)
{
	if (*ppHead == NULL) // 单链表为空
	{
		printf("单链表为空，头删失败\n");
	}
	else
	{
		ListNode* next = (*ppHead)->next; // 先保存第二个节点地址，防止第一个节点释放后找不到后续节点
		free(*ppHead); // 释放第一个节点空间
		*ppHead = next; // 头指针指向原来第二个节点，当作第一个节点
	}
}

2.5 尾插元素

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void SinListTailInsert(ListNode** ppHead, ElemType elem)
{
	ListNode* newNode = CreateNode(elem);
	if (*ppHead == NULL) // 单链表为空
	{
		*ppHead = newNode;
	}
	else
	{
		ListNode* tail = *ppHead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newNode;
	}
}

2.6 尾删元素

在这里插入图片描述

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
void SinListTailDelete(ListNode** ppHead)
{
	if (*ppHead == NULL) // 单链表为空
	{
		printf("单链表为空，尾删失败\n");
	}
	else  //单链表至少有一个节点以上
	{
		if ((*ppHead)->next == NULL) // 单链表只有1个节点
		{
			free(*ppHead);
			*ppHead = NULL;
		}
		else // 单链表有2个及以上节点
		{
			ListNode* prev = NULL;
			ListNode* tail = *ppHead;
			while (tail->next != NULL) 
			{
				prev = tail;
				tail = tail->next;
			}
			free(tail); 
			prev->next = NULL; // 将原单链表倒数第二个节点的next置为NULL，作为新链表的尾节点
		}
	}
}

2.7 指定位置插入元素

位序（位置）从1开始，即第一个节点位序为1
在这里插入图片描述

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
void SinListInsert(ListNode** ppHead, int pos, ElemType elem)
{
	if (pos <= 0)
	{
		printf("位置不合法，插入失败\n");
	}
	else if (pos == 1) // 头部插入
	{
		ListNode* newNode = CreateNode(elem);
		newNode->next = *ppHead;
		*ppHead = newNode; // 头指针指向新节点
	}
	else
	{
		int i = 1;
		ListNode* prev = NULL;
		ListNode* cur = *ppHead;
		while (cur != NULL && i < pos)
		{
			prev = cur;
			cur = cur->next;
			i++;
		}
		if (i == pos)
		{
			ListNode* newNode = CreateNode(elem);
			newNode->next = cur;
			prev->next = newNode;
		}
		else
		{
			printf("位置不合法，插入失败\n");
		}
	}
}

2.7 指定位置删除元素

在这里插入图片描述

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
void SinListDelete(ListNode** ppHead, int pos)
{
	if (pos <= 0)
	{
		printf("位置不合法，删除失败\n");
	}
	else if (*ppHead == NULL)
	{
		printf("单链表为空，删除失败\n");
	}
	else if(pos == 1)
	{
		ListNode* next = (*ppHead)->next; // 先保存第二个节点地址，防止第一个节点释放后找不到后续节点
		free(*ppHead); // 释放头节点
		*ppHead = next; // 头指针指向原来第二个节点，当作第一个节点
	}
	else
	{
		int i = 1;
		ListNode* prev = NULL;
		ListNode* cur = *ppHead;
		while (cur != NULL && i < pos)
		{
			prev = cur;
			cur = cur->next;
			i++;
		}
		if (cur == NULL)
		{
			printf("位置不合法，删除失败\n");
		}
		else
		{
			prev->next = cur->next;
			free(cur);
		}
	}
}

2.8 打印单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void SinListPrint(ListNode* pHead)
{
	if (pHead == NULL)
	{
		printf("单链表为空\n");
	}
	else
	{
		ListNode* cur = pHead;
		while (cur != NULL)
		{
			printf("%d->", cur->data);
			cur = cur->next;
		}
		printf("NULL\n");
	}
}

2.9 查找指定元素位置

查找指定值在单链表第一次出现位置，位置从1开始，未找到返回-1 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int SinListFind(ListNode* pHead, ElemType value)
{
	ListNode* cur = pHead;
	int i = 1;
	while (cur != NULL)
	{
		
		if (cur->data == value)
		{
			return i;
		}
		cur = cur->next;
		i++;
	}
	return -1;
}

2.10 销毁单链表

1
2
3
4
5
6
7
8
9
10
11
12
void Destory(ListNode** ppHead)
{
	ListNode* cur = *ppHead;
	ListNode* next = NULL;
	while (cur != NULL)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	*ppHead = NULL;
}

2.11 源代码

头文件SinList.h内容：

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
#pragma once

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

typedef int ElemType;

typedef struct Node
{
	ElemType data;
	struct Node* next;
}ListNode;


ListNode* CreateNode(); // 创建一个单链表节点

void SinListHeadInsert(ListNode **ppHead, ElemType elem); // 头部插入元素

void SinListHeadDelete(ListNode** ppHead); // 头部删除元素

void SinListTailInsert(ListNode** ppHead, ElemType elem); //尾部插入元素

void SinListTailDelete(ListNode** ppHead); //尾部删除元素

void SinListInsert(ListNode** ppHead, int pos, ElemType elem); //插入元素到pos位置,位置从1开始

void SinListDelete(ListNode** ppHead, int pos); //删除pos位置元素,位置从1开始

void SinListPrint(ListNode* pHead); //打印单链表 

int SinListFind(ListNode* pHead, ElemType value); //查找指定值在单链表第一次出现位置，位置从1开始，未找到返回-1 

void Destory(ListNode** ppHead); // 销毁单链表

源文件SinList.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
201
202
203
204
205
206
#include "SinList.h"

ListNode* CreateNode(ElemType elem)
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	if (newNode == NULL)  // 开辟空间失败，终止程序
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newNode->data = elem;
	newNode->next = NULL;
	return newNode;
}

void SinListHeadInsert(ListNode** ppHead, ElemType elem)
{
	ListNode* newNode = CreateNode(elem);
	newNode->next = *ppHead;
	*ppHead = newNode; // 头指针指向新节点
}

void SinListHeadDelete(ListNode** ppHead)
{
	if (*ppHead == NULL) // 单链表为空
	{
		printf("单链表为空，头删失败\n");
	}
	else
	{
		ListNode* next = (*ppHead)->next; // 先保存第二个节点地址，防止第一个节点释放后找不到后续节点
		free(*ppHead); // 释放第一个节点空间
		*ppHead = next; // 头指针指向原来第二个节点，当作第一个节点
	}
}

void SinListTailInsert(ListNode** ppHead, ElemType elem)
{
	ListNode* newNode = CreateNode(elem);
	if (*ppHead == NULL) // 单链表为空
	{
		*ppHead = newNode;
	}
	else
	{
		ListNode* tail = *ppHead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newNode;
	}
}

void SinListTailDelete(ListNode** ppHead)
{
	if (*ppHead == NULL) // 单链表为空
	{
		printf("单链表为空，尾删失败\n");
	}
	else  //单链表至少有一个节点以上
	{
		if ((*ppHead)->next == NULL) // 单链表只有1个节点
		{
			free(*ppHead);
			*ppHead = NULL;
		}
		else // 单链表有2个及以上节点
		{
			ListNode* prev = NULL;
			ListNode* tail = *ppHead;
			while (tail->next != NULL) 
			{
				prev = tail;
				tail = tail->next;
			}
			free(tail); 
			prev->next = NULL; // 将原单链表倒数第二个节点的next置为NULL，作为新链表的尾节点
		}
	}
}


void SinListInsert(ListNode** ppHead, int pos, ElemType elem)
{
	if (pos <= 0)
	{
		printf("位置不合法，插入失败\n");
	}
	else if (pos == 1) // 头部插入
	{
		ListNode* newNode = CreateNode(elem);
		newNode->next = *ppHead;
		*ppHead = newNode; // 头指针指向新节点
	}
	else
	{
		int i = 1;
		ListNode* prev = NULL;
		ListNode* cur = *ppHead;
		while (cur != NULL && i < pos)
		{
			prev = cur;
			cur = cur->next;
			i++;
		}
		if (i == pos)
		{
			ListNode* newNode = CreateNode(elem);
			newNode->next = cur;
			prev->next = newNode;
		}
		else
		{
			printf("位置不合法，插入失败\n");
		}
	}
}

void SinListDelete(ListNode** ppHead, int pos)
{
	if (pos <= 0)
	{
		printf("位置不合法，删除失败\n");
	}
	else if (*ppHead == NULL)
	{
		printf("单链表为空，删除失败\n");
	}
	else if(pos == 1)
	{
		ListNode* next = (*ppHead)->next; // 先保存第二个节点地址，防止第一个节点释放后找不到后续节点
		free(*ppHead); // 释放头节点
		*ppHead = next; // 头指针指向原来第二个节点，当作第一个节点
	}
	else
	{
		int i = 1;
		ListNode* prev = NULL;
		ListNode* cur = *ppHead;
		while (cur != NULL && i < pos)
		{
			prev = cur;
			cur = cur->next;
			i++;
		}
		if (cur == NULL)
		{
			printf("位置不合法，删除失败\n");
		}
		else
		{
			prev->next = cur->next;
			free(cur);
		}
	}
}


void SinListPrint(ListNode* pHead)
{
	if (pHead == NULL)
	{
		printf("单链表为空\n");
	}
	else
	{
		ListNode* cur = pHead;
		while (cur != NULL)
		{
			printf("%d->", cur->data);
			cur = cur->next;
		}
		printf("NULL\n");
	}
}

int SinListFind(ListNode* pHead, ElemType value)
{
	ListNode* cur = pHead;
	int i = 1;
	while (cur != NULL)
	{
		
		if (cur->data == value)
		{
			return i;
		}
		cur = cur->next;
		i++;
	}
	return -1;
}

void Destory(ListNode** ppHead)
{
	ListNode* cur = *ppHead;
	ListNode* next = NULL;
	while (cur != NULL)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	*ppHead = NULL;
}

源文件main.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
#include "SinList.h"

void menu()
{
	printf("------------------------------\n");
	printf("-- H. 头插元素  h. 头删元素 --\n");
	printf("-- T. 尾插元素  t. 尾删元素 --\n");
	printf("-- I. 插入元素  D. 删除元素 --\n");
	printf("-- F. 查找元素  P. 打印元素 --\n");
	printf("---------    Q. 退出  --------\n");
	printf("------------------------------\n\n");
}

int main()
{
	ListNode* pHead = NULL;
	char choose = 'Q';
	do
	{
		menu();
		printf("请选择：");
		choose = getchar(); //接接收用户选择
		ElemType elem; //待插入（或查找）元素值
		int position = -1; //待插入（删除、查找）元素位序，位序从1开始
		getchar(); //从输入缓冲区读取回车符，避免影响下次输入
		switch (choose)
		{
		case 'H':
			printf("请输入待插入元素值：");
			scanf("%d", &elem);
			SinListHeadInsert(&pHead, elem);
			getchar();
			break;
		case 'h':
			SinListHeadDelete(&pHead);
			break;
		case 'T':
			printf("请输入待插入元素值：");
			scanf("%d", &elem);
			SinListTailInsert(&pHead,elem);
			getchar();
			break;
		case 't':
			SinListTailDelete(&pHead);
			break;
		case 'I':
			printf("请输入待插入元素位序及值,例：2 5  >"); //位序：单链表的第几个元素，从1开始
			scanf("%d %d", &position, &elem);
			SinListInsert(&pHead, position, elem);
			getchar();
			break;
		case 'D':
			printf("请输入待删除元素位序：");
			scanf("%d", &position);
			SinListDelete(&pHead, position);
			getchar();
			break;
		case 'F':
			printf("请输入待查找元素的值：");
			scanf("%d", &elem);
			position = SinListFind(pHead, elem);
			getchar();
			if (position == -1)
			{
				printf("元素：%d 不在单链表中\n", elem);
			}
			else
			{
				printf("元素：%d 的位序为：%d\n", elem, position);
			}
			break;
		case 'P':
			SinListPrint(pHead);
			break;
		case 'Q':
			Destory(&pHead);
			printf("退出成功\n");
			break;
		default:
			printf("选择错误，请重新选择!!!\n");
			break;
		}
	} while (choose != 'Q');

	return 0;
}

三、带头节点的单链表

3.1 单链表结构及接口定义

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
typedef int ElemType;

typedef struct Node
{
	ElemType data;
	struct Node* next;
}ListNode;


ListNode* CreateNode(); // 创建一个节点

void SinListHeadInsert(ListNode *pHead, ElemType elem); // 头部插入元素

void SinListHeadDelete(ListNode *pHead); // 头部删除元素

void SinListTailInsert(ListNode *pHead, ElemType elem); //尾部插入元素

void SinListTailDelete(ListNode *pHead); //尾部删除元素

void SinListInsert(ListNode *pHead, int pos, ElemType elem); // 插入元素到pos位置,位置从1开始

void SinListDelete(ListNode *pHead, int pos); // 删除pos位置元素,位置从1开始

void SinListPrint(ListNode *pHead); // 打印单链表 

int SinListFind(ListNode *pHead, ElemType value); // 查找指定值在单链表第一次出现位置，位置从1开始，未找到返回-1 

ListNode* Destory(ListNode* pHead); // 销毁单链表

3.2 创建节点

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* CreateNode(ElemType elem)
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	if (newNode == NULL)  // 开辟空间失败，终止程序
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newNode->data = elem;
	newNode->next = NULL;
	return newNode;
}

3.3 头插元素

1
2
3
4
5
6
void SinListHeadInsert(ListNode* pHead, ElemType elem)
{
	ListNode* newNode = CreateNode(elem);
	newNode->next = pHead->next;
	pHead->next = newNode;
}

3.3 头删元素

1
2
3
4
5
6
7
8
9
10
11
12
13
void SinListHeadDelete(ListNode* pHead)
{
	if (pHead->next == NULL)
	{
		printf("单链表为空，头删失败\n");
	}
	else
	{
		ListNode* Node = pHead->next;
		pHead->next = pHead->next->next;
		free(Node);
	}
}

3.4 尾插元素

1
2
3
4
5
6
7
8
9
10
void SinListTailInsert(ListNode* pHead, ElemType elem)
{
	ListNode* tail = pHead;
	while (tail->next != NULL)
	{
		tail = tail->next;
	}
	ListNode* newNode = CreateNode(elem);
	tail->next = newNode;
}

3.5 尾删元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void SinListTailDelete(ListNode* pHead)
{
	if (pHead->next == NULL)
	{
		printf("单链表为空，尾删失败\n");
	}
	else
	{
		ListNode* prev = NULL;
		ListNode* tail = pHead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

3.6 指定位置插入元素

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
void SinListInsert(ListNode* pHead, int pos, ElemType elem)
{
	if (pos <= 0)
	{
		printf("位置不合法，插入失败\n");
	}
	else
	{
		int i = 0;
		ListNode* prev = NULL;
		ListNode* cur = pHead;
		while (cur != NULL && i < pos)
		{
			prev = cur;
			cur = cur->next;
			i++;
		}
		if (i == pos)
		{
			ListNode* newNode = CreateNode(elem);
			newNode->next = cur;
			prev->next = newNode;
		}
		else
		{
			printf("位置不合法，插入失败\n");
		}
	}
}

3.7 指定位置删除元素

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
void SinListDelete(ListNode* pHead, int pos)
{
	if (pos <= 0)
	{
		printf("位置不合法，删除失败\n");
	}
	else if(pHead->next == NULL)
	{
		printf("单链表为空，删除失败\n");
	}
	else
	{
		int i = 0;
		ListNode* prev = NULL;
		ListNode* cur = pHead;
		while (cur != NULL && i < pos)
		{
			prev = cur;
			cur = cur->next;
			i++;
		}
		if (cur == NULL)
		{
			printf("位置不合法，删除失败\n");
		}
		else
		{
			prev->next = cur->next;
			free(cur);
		}
	}
}

3.8 打印单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void SinListPrint(ListNode* pHead)
{
	if (pHead->next == NULL)
	{
		printf("单链表为空\n");
	}
	else
	{
		ListNode* cur = pHead->next;
		while (cur != NULL)
		{
			printf("%d->", cur->data);
			cur = cur->next;
		}
		printf("NULL\n");
	}
}

3.9 查找指定元素位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int SinListFind(ListNode* pHead, ElemType value)
{
	ListNode* cur = pHead->next;
	int i = 1;
	while (cur != NULL)
	{
		
		if (cur->data == value)
		{
			return i;
		}
		cur = cur->next;
		i++;
	}
	return -1;
}

3.10 销毁单链表

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* Destory(ListNode* pHead)
{
	ListNode* cur = pHead;
	ListNode* next = NULL;
	while (cur != NULL)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	return NULL;
}

3.11 源代码

头文件SinList.h内容：

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
#pragma once

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

typedef int ElemType;

typedef struct Node
{
	ElemType data;
	struct Node* next;
}ListNode;


ListNode* CreateNode(); // 创建一个节点

void SinListHeadInsert(ListNode *pHead, ElemType elem); // 头部插入元素

void SinListHeadDelete(ListNode *pHead); // 头部删除元素

void SinListTailInsert(ListNode *pHead, ElemType elem); //尾部插入元素

void SinListTailDelete(ListNode *pHead); //尾部删除元素

void SinListInsert(ListNode *pHead, int pos, ElemType elem); // 插入元素到pos位置,位置从1开始

void SinListDelete(ListNode *pHead, int pos); // 删除pos位置元素,位置从1开始

void SinListPrint(ListNode *pHead); // 打印单链表 

int SinListFind(ListNode *pHead, ElemType value); // 查找指定值在单链表第一次出现位置，位置从1开始，未找到返回-1 

ListNode* Destory(ListNode* pHead); // 销毁单链表

源文件SinList.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
#include "SinList.h"


ListNode* CreateNode(ElemType elem)
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	if (newNode == NULL)  // 开辟空间失败，终止程序
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newNode->data = elem;
	newNode->next = NULL;
	return newNode;
}

void SinListHeadInsert(ListNode* pHead, ElemType elem)
{
	ListNode* newNode = CreateNode(elem);
	newNode->next = pHead->next;
	pHead->next = newNode;
}

void SinListHeadDelete(ListNode* pHead)
{
	if (pHead->next == NULL)
	{
		printf("单链表为空，头删失败\n");
	}
	else
	{
		ListNode* Node = pHead->next;
		pHead->next = pHead->next->next;
		free(Node);
	}
}

void SinListTailInsert(ListNode* pHead, ElemType elem)
{
	ListNode* tail = pHead;
	while (tail->next != NULL)
	{
		tail = tail->next;
	}
	ListNode* newNode = CreateNode(elem);
	tail->next = newNode;
}

void SinListTailDelete(ListNode* pHead)
{
	if (pHead->next == NULL)
	{
		printf("单链表为空，尾删失败\n");
	}
	else
	{
		ListNode* prev = NULL;
		ListNode* tail = pHead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

void SinListInsert(ListNode* pHead, int pos, ElemType elem)
{
	if (pos <= 0)
	{
		printf("位置不合法，插入失败\n");
	}
	else
	{
		int i = 0;
		ListNode* prev = NULL;
		ListNode* cur = pHead;
		while (cur != NULL && i < pos)
		{
			prev = cur;
			cur = cur->next;
			i++;
		}
		if (i == pos)
		{
			ListNode* newNode = CreateNode(elem);
			newNode->next = cur;
			prev->next = newNode;
		}
		else
		{
			printf("位置不合法，插入失败\n");
		}
	}
}

void SinListDelete(ListNode* pHead, int pos)
{
	if (pos <= 0)
	{
		printf("位置不合法，删除失败\n");
	}
	else if(pHead->next == NULL)
	{
		printf("单链表为空，删除失败\n");
	}
	else
	{
		int i = 0;
		ListNode* prev = NULL;
		ListNode* cur = pHead;
		while (cur != NULL && i < pos)
		{
			prev = cur;
			cur = cur->next;
			i++;
		}
		if (cur == NULL)
		{
			printf("位置不合法，删除失败\n");
		}
		else
		{
			prev->next = cur->next;
			free(cur);
		}
	}
}

void SinListPrint(ListNode* pHead)
{
	if (pHead->next == NULL)
	{
		printf("单链表为空\n");
	}
	else
	{
		ListNode* cur = pHead->next;
		while (cur != NULL)
		{
			printf("%d->", cur->data);
			cur = cur->next;
		}
		printf("NULL\n");
	}
}

int SinListFind(ListNode* pHead, ElemType value)
{
	ListNode* cur = pHead->next;
	int i = 1;
	while (cur != NULL)
	{
		
		if (cur->data == value)
		{
			return i;
		}
		cur = cur->next;
		i++;
	}
	return -1;
}

ListNode* Destory(ListNode* pHead)
{
	ListNode* cur = pHead;
	ListNode* next = NULL;
	while (cur != NULL)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	return NULL;
}

源文件main.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
#include "SinList.h"

void menu()
{
	printf("------------------------------\n");
	printf("-- H. 头插元素  h. 头删元素 --\n");
	printf("-- T. 尾插元素  t. 尾删元素 --\n");
	printf("-- I. 插入元素  D. 删除元素 --\n");
	printf("-- F. 查找元素  P. 打印元素 --\n");
	printf("---------    Q. 退出  --------\n");
	printf("------------------------------\n\n");
}

int main()
{
	ListNode* pHead = (ListNode*)malloc(sizeof(ListNode));
	pHead->next = NULL;
	char choose = 'Q';
	do
	{
		menu();
		printf("请选择：");
		choose = getchar(); //接接收用户选择
		ElemType elem; //待插入（或查找）元素值
		int position = -1; //待插入（删除、查找）元素位序，位序从1开始
		getchar(); //从输入缓冲区读取回车符，避免影响下次输入
		switch (choose)
		{
		case 'H':
			printf("请输入待插入元素值：");
			scanf("%d", &elem);
			SinListHeadInsert(pHead, elem);
			getchar();
			break;
		case 'h':
			SinListHeadDelete(pHead);
			break;
		case 'T':
			printf("请输入待插入元素值：");
			scanf("%d", &elem);
			SinListTailInsert(pHead,elem);
			getchar();
			break;
		case 't':
			SinListTailDelete(pHead);
			break;
		case 'I':
			printf("请输入待插入元素位序及值,例：2 5  >"); //位序：单链表的第几个元素，从1开始
			scanf("%d %d", &position, &elem);
			SinListInsert(pHead, position, elem);
			getchar();
			break;
		case 'D':
			printf("请输入待删除元素位序：");
			scanf("%d", &position);
			SinListDelete(pHead, position);
			getchar();
			break;
		case 'F':
			printf("请输入待查找元素的值：");
			scanf("%d", &elem);
			position = SinListFind(pHead, elem);
			getchar();
			if (position == -1)
			{
				printf("元素：%d 不在单链表中\n", elem);
			}
			else
			{
				printf("元素：%d 的位序为：%d\n", elem, position);
			}
			break;
		case 'P':
			SinListPrint(pHead);
			break;
		case 'Q':
			pHead = Destory(pHead);
			printf("退出成功\n");
			break;
		default:
			printf("选择错误，请重新选择!!!\n");
			break;
		}
	} while (choose != 'Q');

	return 0;
}