数据结构-单链表详解_写出单链表数据结点结构体的定义

数据结构-单链表详解

线性表的链式存储结构称为单链表，借助指针来反映数据元素之间的逻辑关系。

（1）单链表中结点定义：

/**
 * 定义结点类型结构体，有一个data域和一个next域
 */
typedef struct LNode {
	int data;  // 数据域
	struct LNode* next;  // 指向相同结点类型的指针，存放后继结点的地址
}LNode, * LinkList;
1
2
3
4
5
6
7

使用LNode *L;或LinkList L;定义一个指向头结点的指针，即头指针，L是用来指单链表的头指针，习惯上称为单链表L。（这两种定义方式是一样的，但通常用第二种）

• 注意区别：

  • 带头结点的单链表：（这里的Head相当于上面的L）
    
    判空：Head->next == NULL为真
  • 不带头结点的单链表：
    
    判空：Head == NULL为真

• 注：

  • 不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，且该结点内的数据通常不存储信息。
  • 引入头结点的优点：链表中所有位置的操作是一致的；无论链表是否为空，其头指针都指向了头结点，所以头指针始终是非空指针，因此，空表和非空表的处理也得到了统一。

初始化带头结点的链表

/**
 * 初始化，生成带有头结点的单链表
 * @param L 引用类型，头指针
 */
void InitLinkList(LinkList& L) {
	L = (LinkList)malloc(sizeof(LNode));
	if (L) {   //内存分配成功
		L->next = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10

头插法建立单链表

/**
 * 头插法建立单链表
 * @param L 引用类型的头指针
 * @param n 表示需要插入的元素个数
 */
void HeadInsert_LinkList(LinkList& L, int n) {
	LNode* s;   //辅助指针s，用于指向新申请的结点空间，并将输入的数据存入s->data
	for (int i = 1; i <= n; ++i) {
		s = (LNode*)malloc(sizeof(LNode));  //申请新结点空间
		if (s)  //内存分配成功
		{
			/* scanf_s() ——
			此功能特定于Microsoft编译器。它与scanf相同，只是它不会引起缓冲区过载。
			它将输入输入到基于文本的控制台程序中，并将其放入变量中。后面不再重复说明
			 */
			scanf_s("%d", &s->data);  //输入需要插入的值
			/**
			 * 头插法的关键步骤：
			 */
			s->next = L->next;  //让s的next指向已知的L的next（最开始为NULL）
			L->next = s;        //再让头指针L的next指向新插入的结点s
		}
		
	}
}
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

利用头插法建立单链表，输入的数据的顺序与生成的链表中的元素的顺序相反。每个节点插入的时间复杂度为O(1)，总时间复杂度为O(n)。

尾插法建立单链表

/**
 * 尾插法建立单链表
 * @param L 引用类型的头指针
 * @param n 需要插入的元素的个数
 */
void RailInsert_LinkList(LinkList& L, int n) {
	LNode* s, * r;  //s用于指向新申请的节点空间，r用于始终指向尾结点
	r = L;   //r初始指向头结点
	for (int i = 1; i <= n; ++i) {
		s = (LNode*)malloc(sizeof(LNode));
		if (s)
		{
			scanf_s("%d", &s->data);
			/**
			 * 尾插法的关键步骤
			 */
			r->next = s;  //直接让r的next指向新结点s
			r = s;        //再让r重新指向当前的尾结点
		}
		
	}
	r->next = NULL;   //最后，将r的next置空
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

尾插法建立单链表，输入的数据的顺序与生成的链表中的元素的顺序相同。每个结点插入的时间复杂度为O(1)，总时间复杂度为O(n)。

在单链表中插入一个结点

/**
 * 在单链表中插入一个元素
 * @param L        单链表的头指针，代表单链表，使用引用型
 * @param location 在第location个位置插入
 * @param elem     插入的元素值
 */
int InsertElem_LinkList(LinkList& L, int location, int elem) {
	LNode* p, * s;  //p用于遍历单链表，s用于指向新生成的结点空间，并存储插入的数据
	p = L;  //p初始指向头结点
	int j = 1;  //计数，帮助找到要插入的第i个位置
	
	while (p != NULL && j < location) {
		p = p->next;
		++j;
	}
	
	if (!p || j>location)  //插入的位置小于1或者大于表长+1
	{
		return 0;
	}
	s = (LNode*)malloc(sizeof(LNode));
	if (s)
	{
		s->data = elem;
	}

	if (s)
	{
		/*
		插入的关键步骤：顺序不能颠倒
		 */
		s->next = p->next;  //先把第i-1个位置的next给到s的next
		p->next = s;        //再把s给到第i-1个位置的next，即给到第i个位置
	}
	return 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
36

按顺序打印单链表

/**
 * 按顺序输出单链表中元素的值
 * @param L 单链表的头指针
 */
void Print_LinkList(LinkList L) {
	LNode* p = L->next;
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

完整测试代码

#include <stdio.h>
#include <malloc.h>
/**
 * 定义结点类型结构体，有一个data域和一个next域
 */
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * LinkList;

/**
 * 初始化，生成带有头结点的单链表
 * @param L 引用类型，头指针
 */
void InitLinkList(LinkList& L) {
	L = (LinkList)malloc(sizeof(LNode));
	if (L) {   //内存分配成功
		L->next = NULL;
	}
}

/**
 * 头插法建立单链表
 * @param L 引用类型的头指针
 * @param n 表示需要插入的元素个数
 */
void HeadInsert_LinkList(LinkList& L, int n) {
	LNode* s;   //辅助指针s，用于指向新申请的结点空间，并将输入的数据存入s->data
	for (int i = 1; i <= n; ++i) {
		s = (LNode*)malloc(sizeof(LNode));  //申请新结点空间
		if (s)  //内存分配成功
		{
			/* scanf_s() ——
			此功能特定于Microsoft编译器。它与scanf相同，只是它不会引起缓冲区过载。
			它将输入输入到基于文本的控制台程序中，并将其放入变量中。后面不再重复说明
			 */
			scanf_s("%d", &s->data);  //输入需要插入的值
			/**
			 * 头插法的关键步骤：
			 */
			s->next = L->next;  //让s的next已知的L的next（最开始为NULL）
			L->next = s;        //再让头指针L的next指向新插入的结点s
		}
		
	}
}

/**
 * 尾插法建立单链表
 * @param L 引用类型的头指针
 * @param n 需要插入的元素的个数
 */
void RailInsert_LinkList(LinkList& L, int n) {
	LNode* s, * r;  //s用于指向新申请的节点空间，r用于始终指向尾结点
	r = L;   //r初始指向头结点
	for (int i = 1; i <= n; ++i) {
		s = (LNode*)malloc(sizeof(LNode));
		if (s)
		{
			scanf_s("%d", &s->data);
			/**
			 * 尾插法的关键步骤
			 */
			r->next = s;  //直接让r的next指向新结点s
			r = s;        //再让r重新指向当前的尾结点
		}
		
	}
	r->next = NULL;   //最后，将r的next置空
}

/**
 * 在单链表中插入一个元素
 * @param L        单链表的头指针，代表单链表，使用引用型
 * @param location 在第location个位置插入
 * @param elem     插入的元素值
 */
int InsertElem_LinkList(LinkList& L, int location, int elem) {
	LNode* p, * s;  //p用于遍历单链表，s用于指向新生成的结点空间，并存储插入的数据
	p = L;  //p初始指向头结点
	int j = 1;  //计数，帮助找到要插入的第i个位置
	
	while (p != NULL && j < location) {
		p = p->next;
		++j;
	}
	
	if (!p || j>location)  //插入的位置小于1或者大于表长+1
	{
		return 0;
	}
	s = (LNode*)malloc(sizeof(LNode));
	if (s)
	{
		s->data = elem;
	}

	if (s)
	{
		/*
		插入的关键步骤：顺序不能颠倒
		 */
		s->next = p->next;  //先把第i-1个位置的next给到s的next
		p->next = s;        //再把s给到第i-1个位置的next，即给到第i个位置
	}
	return 1;
}

/**
 * 按顺序输出单链表中元素的值
 * @param L 单链表的头指针
 */
void Print_LinkList(LinkList L) {
	LNode* p = L->next;
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

/**
 * 主函数
 * @return 1，结束
 */
int main() {
	LinkList L;
	InitLinkList(L);

	int n;
	
	// 头插法建立单链表
	scanf_s("%d" ,&n);
	HeadInsert_LinkList(L, n);
	Print_LinkList(L);

	InitLinkList(L);

	// 尾插法建立单链表
	scanf_s("%d", &n);
	RailInsert_LinkList(L, n);
	Print_LinkList(L);

	// 插入元素
	int i, elem;
	scanf_s("%d %d", &i, &elem);
	InsertElem_LinkList(L, i, elem);
	Print_LinkList(L);

	return 0;
}
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

创作不易，喜欢的话加个关注点个赞，谢谢谢谢谢谢！