基本数据结构--单链表的实现。并尝试实现一种重要操作：将给定链表反序。
基本数据结构实现--单链表
链表是线性表的另一种实现方式。与顺序表不同，链表中逻辑上相邻的数据元素在物理上未必相邻，而是通过一个指针指明下一个元素的
物理地址。单链表中节点类型的描述如下：
1 struct LNode {
2 ElemType data; //节点数据域
3 LNode* next; //指向下一个节点的指针
4 };
5 typedef LNode* LinkList; 单链表的优点：与顺序表相比，单链表的优点在于插入和删除操作：虽然单链表的插入和删除操作与顺序表一样时间复杂度都是O(n),但是对于单链表来说，
插入和删除时的基本操作主要是“比较”（对于按位插入删除，比较是否到了第i位；对于按值操作，比较值是否相等），而顺序表插入和删除时
的基本操作主要是“移动”。从硬件的角度讲，做一次比较运算的时间是远小于赋值运算的。因此，链表的插入和删除操作要高效得多。
单链表的缺点：由于单链表中逻辑上相邻的元素在物理上未必相邻，故不能根据第一个元素的地址立即计算出第i个元素的地址。于是单链表不支持随机访问。
（所谓随机访问是指：根据起始地址加上元素序号就可以立即找到任意一个元素。）要在单链表中访问第i个元素，必须一个一个访问链表中每一个元素直到
第i个。
以下代码实现一个带头节点的单链表，并尝试实现一种重要操作：将链表反序
1 /* 带头节点的单链表
2
3 实现操作：
4 *1 判空
5 *2 求表长
6 *3 按位序查找
7 *4 按值查找
8 *5 前插操作
9 *6 后插操作
10 *7 按位插入
11 *8 删除指定节点
12 *9 按位删除
13 *10 单链表的建立-头插和尾插
14 */
15 #include <iostream>
16 #include <cstdio>
17 using namespace std;
18
19 typedef int ElemType;
20 typedef struct LNode {
21 ElemType data; //节点数据域
22 LNode* next; //指向下一个节点的指针
23 } * LinkList;
24
25 bool Empty(LinkList& L)
26 {
27 if( L->next == NULL )
28 return true;
29 return false;
30 }
31
32 //求表的长度
33 int Length(LinkList L)
34 {
35 int len = 0;
36 LNode* p = L;
37 //始终让p指向第j个节点，当p没有下一个节点时，j就是表的长度
38 while( p->next != NULL ) {
39 len++;
40 p = p->next;
41 }
42 return len;
43 }
44
45 //按位序查找，返回指向第i个节点的指针
46 //查找失败时返回的是NULL
47 LNode* GetElem(LinkList L,int i)
48 {
49 if( i < 0 )
50 return NULL;
51 int j = 0;
52 LNode* p = L;
53 while( j < i && p != NULL ) {
54 j++;
55 p = p->next;
56 }
57 return p; //i=0时返回的是头节点,i值大于表长是返回的是空指针
58 }
59
60 //按值查找，找到数据域为e的节点,返回其指针
61 LNode* LocateElem(LinkList L,ElemType e)
62 {
63 LNode* p = L->next; //注意不是LNode* p = L :因为指向头节点，数据域是未知的
64 while( p != NULL && p->data != e ) {
65 p = p->next;
66 }
67 return p; //若e不存在，返回空指针
68 }
69
70 //前插操作：在p节点之前插入元素e
71 bool InsertPriorNode(LNode* p,ElemType e)
72 {
73 if( p == NULL )
74 return false;
75
76 //偷天换日
77 LNode* s = new LNode;
78 s->next = p->next;
79 p->next = s;
80 s->data = p->data;
81 p->data = e;
82 return true;
83 }
84
85 //后插操作：在p节点之后插入元素e
86 bool InsertNextNode(LNode* p,ElemType e)
87 {
88 if( p == NULL )
89 return false;
90 LNode* s = new LNode;
91 s->data = e;
92 s->next = p->next;
93 p->next = s;
94 return true;
95 }
96
97 //按位插入：在单链表L的第i个位置插入元素e
98 bool ListInsert(LinkList& L,int i,ElemType e)
99 {
100 if( i < 1 )
101 return false; //位序最小是1
102
103 //先拿到指向第i-1个节点的指针，然后在他后面插入元素e
104 LNode* p = GetElem(L,i-1);
105 return InsertNextNode(p,e);
106 }
107
108 //删除指定节点p
109 bool DeleteNode(LNode* p)
110 {
111 if( p == NULL )
112 return false;
113 //偷天换日
114 LNode* s = p->next;
115 //有bug：当p是最后一个节点时，无法删除(无法从p->next获取data)
116 //非要删除最后一个节点的话，可以传L头节点指针进来
117 p->data = s->data;
118 p->next = s->next;
119 delete s;
120
121 return true;
122 }
123
124 //按位删除：删除单链表L的位序为i的元素，并用e返回
125 bool ListDelete(LinkList& L, int i,int& e)
126 {
127 if( i < 1 )
128 return false;
129 LNode* p = GetElem(L,i-1);
130
131 if( p == NULL ) //没有第i-1个节点，更没有第i个节点
132 return false;
133 if( p->next == NULL ) //找到了第i-1个节点，但是没有第i个节点
134 return false;
135 LNode* t = p->next;
136 e = t->data;
137 p->next = t->next;
138 delete t;
139 return true;
140 }
141
142 //头插法建立单链表(假设所给数据从键盘输入)
143 LinkList List_HeadInsert(LinkList& L)
144 {
145 //假设元素为int型
146 int x;
147 L = new LNode;
148 L->next = NULL;
149 while( cin >> x ) {
150 InsertNextNode(L,x);
151 }
152 return L;
153 }
154
155 //尾插法建立单链表(假设所给数据从键盘输入)
156 LinkList List_TailInsert(LinkList& L)
157 {
158 //假设元素为int型
159 int x;
160 L = new LNode;
161 L->next = NULL;
162 LNode* r = L;
163 while( cin >> x ) {
164 LNode* s = new LNode;
165 s->data = x;
166 r->next = s;
167 r = s; //创建过程中不必将尾节点的next置空，因为后面还会有节点
168 }
169 r->next = NULL; //链表创建结束，最后一个节点的下一个节点置空
170 return L;
171 }
172
173 //按顺序输出单链表中所有元素
174 void Print(LinkList L)
175 {
176 if( L == NULL )
177 return ;
178 LNode* iterater = L->next;
179 while( iterater != NULL ) {
180 cout << iterater->data << endl;
181 iterater = iterater->next;
182 }
183 }
184
185 void test1()
186 {
187 //*测试使用a[i]=2*i的100个元素建立链表
188 int a[100];
189 for( int i=0; i<100; i++ ) {
190 a[i] = 2*i;
191 }
192 LinkList L = new LNode;
193 L->next = NULL;
194 //使用尾插法将以上数组插入链表L
195 LNode* r = L;
196 for( int i=0; i<100; i++ ) {
197
198 LNode* s = new LNode;
199 s->data = a[i];
200 r->next = s;
201 r = s;
202 }
203 r->next = NULL;
204
205 //*测试在值为20的元素后插入元素985211
206 LNode* t = LocateElem(L,20); //按值查找
207 InsertNextNode(t,985211);
208
209 //*测试删除位序为15的元素(值应该是26)
210 LNode* tt = GetElem(L,15); //按位序查找
211 if( tt != NULL ) {
212 DeleteNode(tt);
213 }
214
215 //*测试按位序删除位序为100的元素
216 int ttt = 0;
217 if( ListDelete(L,100,ttt) )
218 cout << "按位序删除成功，删除的元素是：" << ttt << endl;
219 Print(L);
220 cout << "-------------------------------" << endl;
221
222
223 //下面尝试将L反序 *****重要*****
224 //抓住链表中的第一个数据元素,一个一个往后进行头插,表头结点指针还是L
225 LNode* it = L->next;
226 L->next = NULL; //*****第一个数据已经抓住了;不加这句会导致表尾自己指向自己(而非指向NULL)
227
228 //从链表的第一个节点开始，一个一个地在将表中所有节点重新插在表头
229 while( it != NULL ) {
230 LNode* nxt = it->next;
231 it->next = L->next;
232 L->next = it; //头插法重构链表，即可将链表反序
233 it = nxt;
234 }
235 Print(L);
236
237 //*测试查找不存在的元素返回空指针
238 if( LocateElem(L,999) == NULL ) {
239 cout << endl << "999不存在" << endl;
240 }
241
242 }
243
244 //测试头插法
245 void test2()
246 {
247 LinkList L;
248 List_HeadInsert(L);
249 Print(L);
250 }
251
252 int main()
253 {
254 // test1();
255 // test2();
256 return 0;
257 }