数据结构:单链表
最近学习了数据结构中的链表。
关于链表，个人整理笔记如下:
什么是链表？
链表是物理存储单元上非连续、非顺序的存储结构。与我们之前学习过的数组同为存储结构，区别是数组是连续的、顺序的存储结构。
在链表这种非连续、非顺序的存储结构中，每个元素以结点的形式存储。而每个结点都由数据域和指针域构成,如下图所示。
关于头结点：
链表可以有头结点也可以没有，区别在于链表有头结点虽浪费空间，但易理解，边界好处理，不易出错，代码简单，相反无头结头节省空间，难理解，边界不易处理，代码稍复杂。
有头结点的引入是为了对链表删除、逆向、建立的时候操作更统一，不用专门对第一个元素或最后一个元素进行单独处理。
可能讲述得不是那么清楚，更多详情请参阅此博文 http://blog.csdn.net/21aspnet/article/details/160019
为什么要使用链表呢？
首先，数组是物理内存上连续的、顺序的空间，那么要是数组大小太大或没有连续大小的空间时就尬尴了，此时就需要用到链表了。
其次，我们如果我们对一组数据进行删除操作时，用数组的话，我们就需要将要删除的那个数据所在的位置后边的所有数据都得向前移动一个位置，而当我们添加数据时，同样也是这样的操作。
那么使用链表的话，就是把那个结点的指针域所指向地址指向下一个结点的地址就 ok 了。而添加数据呢，也是类似的指针操作。
当然数组仍然存在肯定是还有链表不能替代的地方，使用链表的时候呢，我们要查找某个数据时就必需得从第一个结点开始依次的查找，
还有当我们要打印出链表中最后一个数据时，用数组直接使用下标地址就可以打印出来了，然而链表还在一个接一个地跟着指针往下传，
同样的我们用数组打印某个指定序列内的数据时直接用标法可以解决，而链表就比较麻烦了。
那么综上所述，可以知道为什么要用到链表，数组和链表存在的意义了。
那什么又是单向链表？什么又是循环链表？就用一个结构图来表明它们的关系吧。
线性表：一种最简单、常用的数据结构，数据元素之间是一对一的关系。
那么，怎样建立一个单链表呢？
首先定义单链表的存储结构
// 为 int 类型创建 ElemType 别名
typedef int ElemType;
// 定义链表储结构
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
此处定义单链表每个结点的存储结构，包括 存储结点的数据域 data 和 存储后继结点位置的指针域 next 。
为了方便阅读使用别名 ElemType 表示 int 型，同时也为了提高程序可读性，对同一结构体指针类型命了两个名 LinkList 、LNode * ，两者本质上是等价的。
通常习惯用 LinkList 定义单链表，表示某单链表的头指针；用LNode *定义指向单链表中任意结点的指针变量。
如: 定义LinkList L ，则L为单链表的头指针; 定义LNode *p ，则p为指向单链表中某个结点的指针，用 *p 表示该结点。
单链表由表头指针唯一确定，因此单链表可以用头指针的名字来命名，如头指针名为 L ,则简称该链表为为表 L。
注意区分指针变量和结点变量两个不同概念，若定义 LinkList p 或 LNode *p ，则p为指向某结点的指针变量，表示该结点的地址；而*p为对应结点的变量，表示该结点的名称。
此处为了 便于首元结点的处理 便于空表和非空表的统一处理 为链表增加头结点。
初始化单链表
1.生成一个新结点作为头结点 ，用头指针 L 指向头结点。
2.头结点的指针域置空。
此处: 可以使用关键字 new 为结点分配内存，也可以用头文件 stdlib.h 中的 malloc 分配内存。
void InitList(LinkList &L)
{
L = new LNode; // 分配内存
//L = (struct LNode *)malloc(sizeof(struct LNode)); // 调用头文件 stdlib.h 中的 malloc 分配内存
L->next = NULL;
}
创建单链表
初始化操作是创建一个只有头结点的空链表，那么如何创建包括若干结点的链表呢？
创建链表时根据结点插入位置不同，链表的创建方法可分为前插法和后插法。
- 前插法
前插法通过将新结点逐个插入链表的头部(头结点之后)来创建链表，每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后 。
1.创建一个只有头结点的空链表。
2.根据创建链表结点元素个数 n ，循环n次执行以下操作:
（1）生成一个新结点 *p ；
（2）将输入元素赋新结点 *p 的数据域中；
（3）将新结点 *p 插入到头结点之后。
// 前插法插入
void CreateList_H(LinkList &L, int n)
{
LNode *p;
for(int i = 0; i < n; i++)
{
p = new LNode;
cin>>p->data;
p->next = L->next;
L->next = p;
}
}
- 后插法
后插法通过将新结点逐个插入到链表的尾部来创建链表。同前插法，每次申请一个新结点，读入相应的数据元素值。不同的是，为了使新结点能够插入到单链表尾部，需要增加一个尾指针 tailNode 指向链表的尾结点。
1.创建一个只有头结点的空链表。
2.尾指针 tailNode 初始化，指向头结点。
3.根据创建链表结点元素个数 n，循环n次执行以下操作:
（1）生成一个新结点 *p ；
（2）输入元素值赋给新结点 *p 的数据域；
（3）将新结点 *p 插入到 *tailNode 之后；
（4）尾指针tailNode指向新的尾结点 *p。
// 尾插法插入
void CreateList_R(LinkList &L, int n)
{
LNode *p, *tailNode;
tailNode = L;
for(int i = 0; i < n; i++)
{
p = new LNode;
cin>>p->data;
p->next = NULL;
tailNode->next = p; // 将新结点*p插入尾结点*tailNode后的数据域
tailNode = p; // tailNode 指向新的尾结点 *p
}
}
单链表的插入
创建了含若干个结点的单链表，就可能根据需求对链表进行新结点的插入操作。
将数据域为 e 的新结点插入到单链表的第 i 个结点位置上，即插入到结点 Ni-1 和 Ni 之间。
1.查找结点 Ni-1，并由指针 p 指向该结点；
2.生成一个新的结点 *newNode ；
3.将新结点 *newNode 数据域置为 e，指针域指向结点 Ni；
4.将结点 *p 的指针域指向新结点 *newNode。
// 单链表插入新结点
int InsertLinkList(LinkList &L, int i, ElemType e)
{
LNode *p = L, *newNode;
int j = 0;
while(p && j < i-1) // 查找第 i-1 个结点 p指向该结点
{
p = p->next;
j++;
}
if(!p || j > i-1)
return -1;
// 类似前插法
newNode = new LNode; // 生成新结点 newNode
newNode->data = e;
newNode->next = p->next;
p->next = newNode;
return 1;
}
单链表的删除
单链表对其中某个结点的删除也是基本操作，同单链表插入元素一样，将某个结点上从链表中删除，首先查找结点 Ni-1然后删除该位置结点。
1.查找结点 Ni-1 位置，并由指针 p 指向该结点；
2.临时保存待删除结点 Ni 地址在 tempNode 中，以备释放结点空间；
3.将结点 *p 指针域指向结点 Ni 的的后继结点；
4.释放结点 Ni 的空间。
// 删除单链表元素
int LinkListDelete(LinkList &L, int i)
{
int j = 0;
LNode *p, *tempNode;
p = L;
while((p->next) && (j < i-1)) // 查找第 i-1 个元素 p指向该结点
{
p = p->next;
j++;
}
if(!(p->next) || j > i-1) // 判断插入位置是否合理
return -1;
tempNode = p->next; // 临时保存被删除结点的地址以备释放
p->next = tempNode->next; // 改变删除结点前驱结点的指针域
delete tempNode; // 释放删除结点空间
return 1;
}
单链表打印输出
如果要查看单链表中元素，怎么做呢？
1.生成新结点 *p,其指单链表首元结点；
2从首元结点开始依次顺着链表指针域 next 向下访问，只要当前结点的指针 p 不为空（NULL）则执行以下操作:
（1）打印输出当前结点数据域值；
（2）p 指向下一个结点；
// 打印输出单链表元素
void PrintLinkList(LinkList &L)
{
LNode *p;
p = L->next;
while(p != NULL)
{
cout<<p->data<<" ";
p = p->next;
}
cout<<endl;
}
单链表的取值
和顺序表不同，链表中逻辑相邻的结点并没有存储在物理相邻的单元中，这样根据给定结点位置序号 i,在链表中获取该结点数据域的值时不能像顺序表那样随机访问，只能从链表的首元结点出发，顺着链表指针域next 逐个结点向下访问。
1.用指针 p 指向首元结点， 用 j 做计数器初值赋为 1；
2.从首元结点开始依次顺着链表指针域 next 向下访问，只要指向当前结点的指针 p 不为空（NULL) ，并且没有到达序号为 i 的结点，则循环执行以下操作:
（1）p 指向下一个结点 ；
（2）计数器 j 相应加 1；
3.退出循环时，如果指针 p 为空，或者计数器 j 大于 i，则说明指定的序号 i 值不合法（i 大于表长 n 或 i 小于等于 0），取值失败提示信息 返回 -1 ；否则取值成功，此时 j = i 时，p 所指的结点就是要找的第 i 个结点，可以输出此结点数据域中元素值，返回 1。
// 单链表取值
int getElem(LinkList &L, int i)
{
LNode *p;
int j = 1; // 计数器 j 初值赋为 1
p = L->next; // 初始化 p 指向首元结点
while(p && j < i) // 顺链表指针域向后扫描 直到 p 为空或指向第 i 个元素
{
p = p->next;
j++;
}
if(!p || j > i) // i 值不合法 i > n 或 i <= 0
{
cout<<"No the Node"<<endl;
return -1;
}
cout<<p->data;
return 1;
}
单链表的查找
链表的查找过程和顺序表类似，从链表的首元结点出发，依次将结点数据域中的值与给定值 e 进行比较，返回查找结果。
1.用指针 p 指向首元结点 ；
2.从首元结点开始依次顺着链表指针域向下查找，只要指向当前结点的指针 p 不为空，并且 p 所指结点的数据域与给定值 e 不等时，则执行以下操作:
(1) p 指向下一个结点。
3.判断 p 是否为空（NULL），如为空，则链表中没有结点数据域值为所给定的 e ，给出提示信息；如不为空，则打印输出其所在位置。
// 单链表的查找
void LocationElem(LinkList L, ElemType e)
{
LNode *p;
int j = 1;
p = L->next; // 初始化 p 指向首元结点
while(p && p->data != e) // 顺着链表指针域向下扫描 直到 p 为空或所指结点的数据域等于 e
{
j++;
p = p->next;
}
if(p != NULL) // 判断是否查找到结点数据域为 e 的结点
cout<<"The element of "<<e<<" local "<<j<<endl;
else
cout<<"No the element"<<endl;
}
最后,完整代码如下 :
1 #include <iostream>
2
3 using namespace std;
4
5 // 为 int 类型创建 ElemType 别名
6 typedef int ElemType;
7
8 // 定义链表储结构
9 typedef struct LNode
10 {
11 ElemType data;
12 struct LNode *next;
13 }LNode, *LinkList;
14
15
16 // 初始化链表
17 void InitList(LinkList &L)
18 {
19 L = new LNode; // 分配内存
20 //L = (struct LNode *)malloc(sizeof(struct LNode)); // 调用头文件 stdlib.h 中的 malloc 分配内存
21 L->next = NULL;
22 }
23
24 // 单链表插入新结点
25 int InsertLinkList(LinkList &L, int i, ElemType e)
26 {
27 LNode *p = L, *newNode;
28 int j = 0;
29 while(p && j < i-1) // 查找第 i-1 个结点 p指向该结点
30 {
31 p = p->next;
32 j++;
33 }
34 if(!p || j > i-1)
35 return -1;
36 // 类似前插法
37 newNode = new LNode; // 生成新结点 newNode
38 newNode->data = e;
39 newNode->next = p->next;
40 p->next = newNode;
41 return 1;
42 }
43
44
45 // 打印输出链表
46 void PrintList(LinkList &L)
47 {
48 LNode* p;
49 p = L->next;
50 while(p != NULL)
51 {
52 cout<<p->data<<" ";
53 p = p->next;
54 }
55 cout<<endl;
56 }
57
58 // 单链表取值
59 int getElem(LinkList &L, int i)
60 {
61 LNode *p;
62 int j = 1; // 计数器 j 初值赋为 1
63 p = L->next; // 初始化 p 指向首元结点
64 while(p && j < i) // 顺链表指针域向后扫描 直到 p 为空或指向第 i 个元素
65 {
66 p = p->next;
67 j++;
68 }
69 if(!p || j > i) // i 值不合理 i > n 或 i <= 0
70 {
71 cout<<"所给定 i 值不合理"<<endl;
72 return -1;
73 }
74 cout<<p->data;
75 return 1;
76 }
77
78 // 单链表的查找
79 void LocationElem(LinkList L, ElemType e)
80 {
81 LNode *p;
82 int j = 1;
83 p = L->next; // 初始化 p 指向首元结点
84 while(p && p->data != e) // 顺着链表指针域向下扫描 直到 p 为空或所指结点的数据域等于 e
85 {
86 j++;
87 p = p->next;
88 }
89 if(p != NULL) // 判断是否查找到结点数据域为 e 的结点
90 cout<<"链表中与 "<<e<<" 等值的数据元素所在结点位于 "<<j<<endl;
91 else
92 cout<<"链表中没有数据元素和 "<<e<<" 等值 "<<endl;
93 }
94
95 // 删除单链表元素
96 int LinkListDelete(LinkList &L, int i)
97 {
98 int j = 0;
99 LNode *p, *tempNode;
100 p = L;
101 while((p->next) && (j < i-1)) // 查找第 i-1 个元素 p指向该结点
102 {
103 p = p->next;
104 j++;
105 }
106 if(!(p->next) || j > i-1) // 判断插入位置是否合理
107 return -1;
108 tempNode = p->next; // 临时保存被删除结点的地址以备释放
109 p->next = tempNode->next; // 改变删除结点前驱结点的指针域
110 delete tempNode; // 释放删除结点空间
111 return 1;
112 }
113
114 // 前插法插入
115 void CreateList_H(LinkList &L, int n)
116 {
117 LNode *p;
118 // LinkList p;
119 for(int i = 0; i < n; i++)
120 {
121 p = new LNode;
122 cin>>p->data;
123 p->next = L->next;
124 L->next = p;
125 }
126 }
127
128 // 尾插法插入
129 void CreateList_R(LinkList &L, int n)
130 {
131 LNode *p, *tailNode;
132 tailNode = L;
133 for(int i = 0; i < n; i++)
134 {
135 p = new LNode;
136 cin>>p->data;
137 p->next = NULL;
138 tailNode->next = p; // 将新结点*p插入尾结点*tailNode后的数据域
139 tailNode = p; // tailNode 指向新的尾结点 *p
140 }
141 }
142
143 int main()
144 {
145 // 定义链表 L
146 LinkList L;
147 // 初始化链表
148 InitList(L);
149
150 cout<<"前插法创建有5个元素的单链表"<<endl;
151 CreateList_H(L, 5);
152 cout<<"打印链表数据"<<endl;
153 PrintList(L);
154
155 cout<<"后插法创建有5个元素的单链表"<<endl;
156 CreateList_R(L, 5);
157 cout<<"打印链表数据"<<endl;
158 PrintList(L);
159
160 cout<<"在链表第三个位置插入数值为 100 的结点"<<endl;
161 InsertLinkList(L, 3, 100);
162 cout<<"打印插入元素后的链表数据"<<endl;
163 PrintList(L);
164
165 cout<<"删除第六个结点"<<endl;
166 LinkListDelete(L, 6);
167 cout<<"打印删除结点后链表数据"<<endl;
168 PrintList(L);
169
170 cout<<"查找元素数据为 100 所在链表中位置"<<endl;
171 LocationElem(L, 100);
172
173 }
本文参考:
《数据结构》（C语言版|第2版） 严蔚梅 李冬梅 吴伟民 编著