devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】线性表（二）：链表 之 单向非循环链表_单向循环相对于我们的非循环链表的有点

作者：盐析白兔 | 2024-07-17 02:14:18

赞

踩

单向循环相对于我们的非循环链表的有点

单向非循环链表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

链表

  • 链式存储：用一组任意的存储单元来存储线性表
  • 链表：采用链式存储方法的线性表称为链表
  • 节点间的逻辑关系由存储节点中的指针实现
  • 链表的结点由两部分构成：数据域和链域 链表的分类

链表的分类
在这里插入图片描述

单链表

1. 单链表相关概念

单链表的两种形式
在这里插入图片描述

1.无头结点示意图

在这里插入图片描述

2.有头结点示意图
在这里插入图片描述

  • 头指针：指向链表中第一个结点（头结点或者首元结点）
  • 头结点：是在首元结点之前附设的一个结点；数据域内可存放链表长度等信息，它不计入表长度
  • 首元结点：是指链表中第一个结点

结点结构
在这里插入图片描述

图示法表示单链表
在这里插入图片描述

需要明白的链表中结点间的逻辑关系
在这里插入图片描述

这里的p指针代表的就是首元结点，q指针代表的是首元结点的直接后继

空表如何表示？

无头结点

当头指针的值为空时，表示空表

在这里插入图片描述

有头结点

头结点的指针域为空时表示空表

在这里插入图片描述

2. 单链表实现

2.1 表结点的设计
typedef int ET;
typedef struct Node
{
	ET data;		//用于存储数据
	Node* next;		//用于存储下个节点的地址
}Node;
typedef Node* List;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
2.2 建立单链表

从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域,然后将新结点插入当前链表中,直到结束。

有头结点情况下
(1).头插法

头插法建表：将新结点插入到当前链表的表头结点之后

在这里插入图片描述
参考源码

void linkedListCreateWithHeadNodeFromHead(List* phead){
	assert(phead != NULL);
	*phead = (Node*)malloc(sizeof(Node));
	assert(phead != NULL);

	(*phead)->data = -1;
	(*phead)->next = NULL;

	int i = 1;
	for (; i <= 10; i++)
	{
		Node* s = (Node*)malloc(sizeof(Node));
		assert(s != NULL);
		s->data = i;

		s->next = (*phead)->next;
		(*phead)->next = s;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

(2).尾插法

尾插法建表：将新结点插入到当前链表的表尾

在这里插入图片描述

参考源码

void linkedListCreateWithHeadNodeFromTail(List* phead){
	assert(phead != NULL);
	*phead = (Node*)malloc(sizeof(Node));
	assert(phead != NULL);
	(*phead)->data = -1;
	(*phead)->next = NULL;

	Node *p = *phead;
	int i = 1;
	for (; i <= 10; i++)
	{
		Node* s = (Node*)malloc(sizeof(Node));
		assert(s != NULL);
		s->data = i;
		s->next = NULL;
		
		p->next = s;
		p = s;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

无头结点情况下
(1).头插法参考源码

void linkedListCreateWithoutHeadNodeFromHead(List* phead){
	assert(phead != NULL);
	*phead = (Node*)malloc(sizeof(Node));
	assert(phead != NULL);
	(*phead)->data = 1;
	(*phead)->next = NULL;
	int i = 2;
	for (; i <= 10; i++){
		Node* s = (Node*)malloc(sizeof(Node));
		assert(s != NULL);
		s->data = i;

		s->next = *phead;
		*phead = s;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

(2).尾插法参考源码

void linkedListCreateWithoutHeadNodeFromTail(List* phead){
	assert(phead != NULL);
	*phead = (Node*)malloc(sizeof(Node));
	assert(*phead != NULL);
	(*phead)->data = 1;
	(*phead)->next = NULL;

	Node* p = *phead;
	for (int i = 2; i <= 10; i++)
	{
		Node* s = (Node*)malloc(sizeof(Node));
		assert(s != NULL);
		s->data = i;
		s->next = NULL;

		p->next = s;
		p = s;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
2.3 单向链表具体操作

下面的源码中一共实现了以下功能：
【1】初始化链表
【2】头插数据
【3】尾插数据
【4】获取首元结点
【5】获取末尾结点
【6】获取表长度
【7】删除首元结点
【8】删除末尾结点
【9】排序
【10】按值得大小插入数据
【11】按位置插入数据
【12】按值删除第一个数据
【13】按位置删除数据
【14】反转链表
【15】展示数据
【16】清空链表
【17】摧毁链表
【18】全表彻底删除某一个值

方法声明

void  linkedListInitial(List* phead);											//初始化链表
void  linkedListWithoutHeadNodeAddFromHead(List* phead, ET val);				//头插法
void  linkedListWithoutHeadNodeAddFromTail(List* phead, ET val);				//尾插法
Node* linkedLIstWithoutHeadNodeGetHead(List* phead);							//获取头结点
Node* linkedListWithoutHeadNodeGetTail(List* phead);							//获取尾结点
int   linkedListWithoutHeadNodeGetLength(List* phead);							//获取表长度
void  linkedListWithoutHeadNodeDropHead(List* phead);							//删除头结点
void  linkedListWithoutHeadNodeDropTail(List* phead);							//删除尾节点
void  linkedListWithoutHeadNodeSortByValue(List* phead);						//排序
void  linkedListWithoutHeadNodeInsertByValue(List* phead, ET val);				//按值插入
void  linkedListWithoutHeadNodeInsertByPosition(List* phead, int pos, ET val);	//按位置插入
void  linkedListWithoutHeadNodeDropByValue(List* phead, ET val);				//按值删除
void  linkedListWithoutHeadNodeDropByPosition(List* phead, int pos, ET val);	//按位置删除
void  linkedListWithoutHeadNodeReverseList(List* phead);						//反转链表
void  linkedListWithoutHeadNodeShowData(List* phead);							//展示数据
void  linkedListWithoutHeadNodeClearList(List* phead);							//清空链表
void  linkedListWithoutHeadNodeDestroyList(List* phead);						//摧毁链表
void  linkedListWithoutHeadNodeEraseByValue(List* phead, ET val);				//全表彻底删除某一个值

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

方法实现

void  linkedListInitial(List* phead){
	assert(phead != NULL);
	*phead = NULL;
}
void  linkedListWithoutHeadNodeAddFromHead(List* phead, ET val){
	assert(phead != NULL);

	Node* s = (Node*)malloc(sizeof(Node));
	assert(s != NULL);
	s->data = val;

	s->next = *phead;
	*phead = s;

}
void  linkedListWithoutHeadNodeAddFromTail(List* phead, ET val){
	assert(phead != NULL);
	Node* p = *phead;

	if (p == NULL){	//表为空时 
		*phead = (Node*)malloc(sizeof(Node));
		assert(*phead != NULL);
		(*phead)->data = val;
		(*phead)->next = NULL;
	}
	else{			//表非空时 
		Node* s = (Node*)malloc(sizeof(Node));
		assert(s != NULL);
		s->data = val;
		s->next = NULL;

		while (p->next != NULL){
			p = p->next;
		}
		p->next = s;
	}
}
Node* linkedLIstWithoutHeadNodeGetHead(List* phead)		
{
	assert(phead != NULL);
	if ((*phead) == NULL){
		return NULL;
	}
	else{
		return (*phead);
	}
}
Node* linkedListWithoutHeadNodeGetTail(List* phead){
	assert(phead != NULL);
	if ((*phead) == NULL){
		return NULL;
	}
	else{
		Node* p = *phead;
		while (p->next != NULL){
			p = p->next;
		}
		return p;
	}
}
int   linkedListWithoutHeadNodeGetLength(List* phead){
	assert(phead != NULL);
	if ((*phead) == NULL) return 0;

	int length = 1;
	Node* p = *phead;
	while (p->next != NULL){
		length++;
		p = p->next;
	}
	return length;
}
void  linkedListWithoutHeadNodeDropHead(List* phead){
	assert(phead != NULL);
	if ((*phead) == NULL){
		printf("表已空！无法删除！\n");
		return;
	}
	Node *p = *phead;
	if (p->next == NULL){
		(*phead) = NULL;
		free(p);
	}
	else{
		(*phead) = p->next;
		free(p);
	}
	printf("首元结点已删除！\n");
}
void  linkedListWithoutHeadNodeDropTail(List* phead){
	assert(phead != NULL);
	if ((*phead) == NULL){
		printf("表已空！无法删除！\n");
		return;
	}
	Node *p = *phead;
	if (p->next == NULL){
		(*phead) = NULL;
		free(p);
	}
	else{
		while (p->next->next != NULL){
			p = p->next;
		}
		Node *q = p->next;
		free(q);
		p->next = NULL;
	}
	printf("末尾结点已删除！\n");
}
void  linkedListWithoutHeadNodeSortByValue(List* phead){
	assert(phead != NULL);
	if ((*phead) == NULL){
		printf("表已空！无法排序！\n");
		return;
	}
	if ((*phead)->next == NULL)	return; 	//一个结点
	Node* p = (*phead)->next;
	Node* q = (*phead)->next;
	(*phead)->next = NULL;
	while (q != NULL){
		q = q->next;
		if ((*phead)->data < p->data){
			Node* temp = *phead;
			while (temp->next != NULL && temp->next->data < p->data){
				temp = temp->next;
			}
			p->next = temp->next;
			temp->next = p;

		}
		else{
			p->next = *phead;
			*phead = p;
		}
		p = q;
	}
}
void  linkedListWithoutHeadNodeInsertByValue(List* phead, ET val)				
{
	assert(phead != NULL);
	if ((*phead) == NULL){	//表空时
		linkedListWithoutHeadNodeAddFromHead(phead, val);
		printf("按值插入数据完成！\n");
		return;
	}
	linkedListWithoutHeadNodeSortByValue(phead);

	Node* s = (Node*)malloc(sizeof(Node));
	s->data = val;
	s->next = NULL;

	if ((*phead)->next == NULL && (*phead)->data > val){	//表中只有一个大于val的结点时
		s->next = *phead;
		*phead = s;
		printf("按值插入数据完成！\n");
		return;
	}
	Node* p = *phead;
	while (p->next != NULL && p->next->data < val){
		p = p->next;
	}
	s->next = p->next;
	p->next = s;
	printf("按值插入数据完成！\n");
}
void  linkedListWithoutHeadNodeInsertByPosition(List* phead, int pos, ET val){
	assert(phead != NULL);
	int len = linkedListWithoutHeadNodeGetLength(phead);
	if (pos <= 0 || pos > len){
		printf("插入位置不合法！\n");
		return;
	}
	int position = pos;
	position--;

	Node* s = (Node*)malloc(sizeof(Node));
	s->data = val;
	s->next = NULL;

	if (position == 0){
		linkedListWithoutHeadNodeAddFromHead(phead, val);
		printf("已在%d位置上插入%d\n", pos, val);
		return;
	}
	Node* p = *phead;
	while (position != 1){
		p = p->next;
		position--;
	}
	s->next = p->next;
	p->next = s;
	printf("已在%d位置上插入%d\n", pos, val);
}
void  linkedListWithoutHeadNodeDropByValue(List* phead, ET val){
	assert(phead != NULL);
	if ((*phead) == NULL){
		printf("空表无法删除\n");
		return;
	}
	linkedListWithoutHeadNodeSortByValue(phead);

	Node* p = *phead;
	if (p->data == val){
		*phead = p->next;
		free(p);
		printf("第一次出现的%d这个数据已被删除!\n", val);
		return;
	}
	while (p->next != NULL){
		if (p->next->data == val){
			Node* q = p->next;
			p->next = q->next;
			free(q);
			printf("第一次出现的%d这个数据已被删除!\n", val);
			return;
		}
		p = p->next;
	}
	printf("没有%d这个数据!\n", val);
}
void  linkedListWithoutHeadNodeDropByPosition(List* phead, int pos){
	assert(phead != NULL);
	int len = linkedListWithoutHeadNodeGetLength(phead);
	if (pos <= 0 || pos > len){
		printf("删除位置不合法！\n");
		return;
	}
	int position = pos;
	position--;

	if (position == 0){
		linkedListWithoutHeadNodeDropHead(phead);
		printf("已删除%d位置上的数据！\n", pos);
		return;
	}
	if (position == len){
		linkedListWithoutHeadNodeGetTail(phead);
	}

	Node* p = *phead;
	while (position != 1){
		p = p->next;
		position--;
	}
	Node* s = p->next;
	p->next = s->next;
	free(s);
	printf("已删除%d位置上的数据！\n", pos);
}
void  linkedListWithoutHeadNodeReverseList(List* phead){	
	assert(phead != NULL);
	if ((*phead)->next == NULL){
		printf("逆置完成！\n");
		return;
	}

	Node* p = (*phead)->next;
	Node* q = (*phead)->next;

	(*phead)->next = NULL;

	while (q != NULL){
		q = q->next;

		p->next = *phead;
		*phead = p;
		p = q;
	}
	printf("逆置完成！\n");
}
void  linkedListWithoutHeadNodeShowData(List phead){
	Node *p = phead;
	while (p != NULL){
		printf("%d--->", p->data);
		p = p->next;
	}
	printf("Over\n");
}
void linkedListWithoutHeadNodeClearList(List* phead){
	assert(phead != NULL);

	Node* p = *phead;
	while ((*phead) != NULL){
		*phead = p->next;
		free(p);
		p = *phead;
	}
}
void linkedListWithoutHeadNodeDestroyList(List* phead){
	assert(phead != NULL);

	Node* p = *phead;
	while ((*phead) != NULL){
		*phead = p->next;
		free(p);
		p = *phead;
	}
}
void linkedListWithoutHeadNodeEraseByValue(List* phead, ET val){
	assert(phead != NULL);
	if ((*phead) == NULL){
		printf("表空，无法删除！\n");
		return;
	}
	linkedListWithoutHeadNodeSortByValue(phead);

	Node* p = *phead;
	Node* q = *phead;

	while (p != NULL){
		if (p->next->data == val){
			break;
		}
		p = p->next;
	}

	q = p->next;

	while (q != NULL){
		if (q->data != val){
			break;
		}
		q = q->next;
	}

	p->next = q;

	if (p->data == val){
		linkedListWithoutHeadNodeDropHead(phead);
	}

}


  • 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
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256
  • 257
  • 258
  • 259
  • 260
  • 261
  • 262
  • 263
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • 275
  • 276
  • 277
  • 278
  • 279
  • 280
  • 281
  • 282
  • 283
  • 284
  • 285
  • 286
  • 287
  • 288
  • 289
  • 290
  • 291
  • 292
  • 293
  • 294
  • 295
  • 296
  • 297
  • 298
  • 299
  • 300
  • 301
  • 302
  • 303
  • 304
  • 305
  • 306
  • 307
  • 308
  • 309
  • 310
  • 311
  • 312
  • 313
  • 314
  • 315
  • 316
  • 317
  • 318
  • 319
  • 320
  • 321
  • 322
  • 323
  • 324
  • 325
  • 326
  • 327
  • 328
  • 329
  • 330
  • 331
  • 332
  • 333
  • 334
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/837433
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号