【单向链表】数据结构——单向链表的介绍与代码实现&笔记_用单向链表(首尾为空节点)表示一组数组,

从今天开始将修炼数据结构专栏，将持续更新，分模块学习。

一、数据结构

1、什么是数据结构？

数据结构：计算机存储，组织数据的方式，数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
简单来说：程序 = 数据结构 + 算法

2、逻辑结构和物理结构

1）逻辑结构：研究数据结构之间的逻辑关系
①线性结构
②非线性结构
树状结构、集合结构、图状结构
2）物理结构：数据在物理内存上的存储形式（连续、非连续）

好了概念就介绍到这里，下面我们进入今天的正文——链表的学习

二、链表——线性结构

1、首先介绍下链表和数组的区别

1）数组：

• 数组空间是连续的，每个元素存储的类型都是一样的。
• 通过数组名+下标访问数组成员。
• 数组大小固定，在定义之后不允许重新改变数组大小，对数组的增加元素减少元素比较麻烦，效率低。

2）链表：

• 链表存储空间不连续
• 没有固定的大小，添加节点和删除节点非常方便
  链表的大小不固定，是通过一系列的节点组成，链表节点就是链表用来存放数据的结构，本质是一个结构体。
• 链表的前后成员是通过指针来寻找的,所以想要删除一个链表成员 只要找到它,free掉其空间,前后链式关系上,可以让删除节点前后成员直接连接
  增加成员,除了在堆空间malloc外,在链表成员前后关系,只要处理好成员间的链接关系 即可在链表任意位置上添加新成员-----灵活
• 成员的访问因为是通过指针寻找再访问的，访问速度会很慢（相对于数组来说）
  2、链表的结构示意图
  

2、链表节点——节点本身是一个结构体

节点结构体分为两个区域：
数据域：存放数据
指针域：存放指向下一个成员或上一个成员的地址

例子：
记录图书馆的所有图书信息

typedef struct book
{
//数据域
char bookname[64];//书名
char Author[32];//作者
float  price;//价格

//指针域
struct book *next;//指向下个和当前类型一致的成员
}BOOK,*pBOOK;
1
2
3
4
5
6
7
8
9
10

3、单向链表的一般性结构

4、单向链表节点的添加——插入节点

头插法：新的节点插入到头节点的下一个
尾插法：新的节点插入到最后一个节点的下一个

5、单向链表节点的查找——查找结点

6、单向链表删除节点

步骤：
1）遍历链表，找到需要被删除的节点p以及他的前一个节点q
2）从逻辑上删除节点p：q->next = p->next
3）从物理上删除节点p：free§

7、单向链表节点的销毁

遍历链表，销毁每一个节点
步骤：
1）使用两个指针对链表进行遍历：p（销毁节点）、q（记录p的下一个节点的地址）
2）释放节点空间free（p）

Node *p, *q;
p = head;
q = p->next;
while(q != NULL)	//释放head后面所有节点
{
	p = q;
	q = q->next;
	free(p);
}
free(head);	//最后释放头节点
1
2
3
4
5
6
7
8
9
10

8、最后附上示例代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//0,设计链表节点
typedef struct node{
	int data;			//数据域
	struct node *next;	//指针域
}Node;		//Node 等价于  struct node

//1,创建链表	-->创建一个链表头
Node *List_Create(void)
{
	//1）对链表头结点空间申请 --> malloc
	Node *list = (Node *)malloc(sizeof(Node));
	if ( list == NULL )
	{
		perror("malloc failed ");	//打印出错信息
		return NULL;				//结束函数
	}

	//2）对链表头结点进行赋值
	list->next = NULL;	

	//3）返回链表头结点地址
	return list;	
}

//2,链表节点插入 （头插法）
bool List_Add_Node_Head(Node *head, int data)
{
	//1）给新节点申请堆内存
	Node *newnode = (Node *)malloc(sizeof(Node));
	if (newnode == NULL)
	{
		perror("newnode malloc failed");
		return false;
	}

	//2）新节点赋值
	newnode->data = data;
	newnode->next = NULL;

	//3）头插法插入链表
	newnode->next = head->next;
	head->next = newnode;

	return true;
}
//尾插法
bool List_Add_Node_End(Node *head, int data)
{
	//1）给新节点申请堆内存
	Node *newnode = (Node *)malloc(sizeof(Node));
	if ( newnode == NULL)
	{
		perror("malloc newnode failed");
		return false;
	}

	//2）给新节点赋值
	newnode->data = data;
	newnode->next = NULL;

	//3）尾插法插入链表
		//找到链表的最后一个节点 p (while(p->next !=NULL)p=p->next)
	Node *p = head;
	while(p->next != NULL)		//当这个循环结束时，p节点就是最后一个节点
	{
		p = p->next;
	}
		//新节点插入到p节点的后面
	p->next = newnode;
	return true;
}


//3,链表数据输出
void List_Display(Node *head)
{
	//1）定义一个指针用来遍历链表
	Node *p = head->next;	//头结点不存放数据
	printf("链表数据：");
	//2）遍历链表，输出链表中的每一个节点的数据
	while(p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;		//把p节点下一个节点的地址赋值给p
	}
	printf("\n");
}

//4，链表节点查找
int List_Search(Node *head, int data)
{
	int i = 1;
	Node *p = head->next;		//遍历链表指针
	while(p != NULL)
	{
		if(p->data == data)	//找到这个节点
		{
			printf("Find Node[%d]!\n", i);
			//return i;	//返回序号值
		}
		p = p->next;
		i++;
	}
	//printf("No such Node!\n");
	return 0;
}

//5,链表节点删除 ==>删除节点时只能删除一个节点,思考：如何同时删除多个节点？
bool List_Remove(Node *head, int data)
{
	int i = 1;
	//1）找到需要被删除的节点p和p的前一个节点q
	Node *p = head->next;
	Node *q = head;		//q是p的前一个节点

	while(p != NULL)
	{
		if(p->data == data)//2）找到之后，删除节点p
		{
			q->next = p->next;	//从逻辑上删除p节点
			free(p);
			printf("删除节点[%d]成功！\n", i);
			return true;
		}
		q = q->next;	//遍历链表
		p = q->next;
		i++;
	}
	//3）如果遍历完链表都没有找到，那就说明链表中没有这个节点
	printf("链表中没有这个节点！\n");
	return false;
}
//6,删除链表中所有节点数据 data的节点
bool List_Remove_All(Node *head, int data)
{
	int i = 1;
	//1）找到需要被删除的节点p和p的前一个节点q
	Node *p = head->next;
	Node *q = head;		//q是p的前一个节点

	while(p != NULL)
	{
		if(p->data == data)//2）找到之后，删除节点p
		{
			q->next = p->next;	//从逻辑上删除p节点
			free(p);
			printf("删除节点[%d]成功！\n", i);
			i++;
			p = q->next;
			continue;
			//return true;
		}
		q = q->next;	//遍历链表
		p = q->next;
		i++;
	}
	//3）如果遍历完链表都没有找到，那就说明链表中没有这个节点
	//printf("链表中没有这个节点！\n");
	return false;
}

//7,链表销毁
void List_Destroy(Node *head)
{
	int i = 0;
	Node *p = head;
	Node *q = p->next;

	while(q != NULL)	//释放头结点后面的所有节点
	{
		p = q;
		q = q->next;
		free(p);
		i++;
	}
	free(head);		//最后释放头结点
	printf("成功释放[%d]个节点\n", i);
}








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