/* 单链表反转/逆序 */
Status ListReverse(LinkList L)
{
LinkList current,pnext,prev;
if(L == NULL || L->next ==
NULL)
return L;
current = L->next;
/* p1指向链表头节点的下一个节点 */
pnext = current->
next;
current->next =
NULL;
while(pnext)
{
prev = pnext->
next;
pnext->next =
current;
current =
pnext;
pnext =
prev;
printf("交换后：current = %d,next = %d \n",current->data,current->next->
data);
}
//printf("current = %d,next = %d \n",current->data,current->next->data);
L->next = current;
/* 将链表头节点指向p1 */
return L;
}
1 #include
"stdio.h"
2
3 #define OK 1
4 #define ERROR 0
5 #define TRUE 1
6 #define FALSE 0
7
8 #define MAXSIZE 20 /* 存储空间初始分配量 */
9
10 typedef
int Status;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
11 typedef
int ElemType;
/* ElemType类型根据实际情况而定，这里假设为int */
12
13 typedef
struct Node
14 {
15 ElemType data;
16 struct Node *
next;
17 }Node;
18 /* 定义LinkList */
19 typedef
struct Node *
LinkList;
20
21 /* 初始化顺序线性表 */
22 Status InitList(LinkList *
L)
23 {
24 *L=(LinkList)malloc(
sizeof(Node));
/* 产生头结点,并使L指向此头结点 */
25 if(!(*L))
/* 存储分配失败 */
26 {
27 return ERROR;
28 }
29 (*L)->next=NULL;
/* 指针域为空 */
30
31 return OK;
32 }
33
34 /* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
35 int ListLength(LinkList L)
36 {
37 int i=
0;
38 LinkList p=L->next;
/* p指向第一个结点 */
39 while(p)
40 {
41 i++
;
42 p=p->
next;
43 }
44 return i;
45 }
46
47 /* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
48 Status ClearList(LinkList *
L)
49 {
50 LinkList p,q;
51 p=(*L)->next;
/* p指向第一个结点 */
52 while(p)
/* 没到表尾 */
53 {
54 q=p->
next;
55 free(p);
56 p=
q;
57 }
58 (*L)->next=NULL;
/* 头结点指针域为空 */
59 return OK;
60 }
61
62 /* 初始条件：顺序线性表L已存在 */
63 /* 操作结果：依次对L的每个数据元素输出 */
64 Status ListTraverse(LinkList L)
65 {
66 LinkList p=L->
next;
67 while(p)
68 {
69 visit(p->
data);
70 p=p->
next;
71 }
72 printf(
"\n");
73 return OK;
74 }
75
76 Status visit(ElemType c)
77 {
78 printf(
"-> %d ",c);
79 return OK;
80 }
81
82 /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
83 /* 操作结果：用e返回L中第i个数据元素的值 */
84 Status GetElem(LinkList L,
int i,ElemType *
e)
85 {
86 int j;
87 LinkList p;
/* 声明一结点p */
88 p = L->next;
/* 让p指向链表L的第一个结点 */
89 j =
1;
/* j为计数器 */
90 while (p && j < i)
/* p不为空或者计数器j还没有等于i时，循环继续 */
91 {
92 p = p->next;
/* 让p指向下一个结点 */
93 ++
j;
94 }
95 if ( !p || j>
i )
96 return ERROR;
/* 第i个元素不存在 */
97 *e = p->data;
/* 取第i个元素的数据 */
98 return OK;
99 }
100
101 /* 初始条件：顺序线性表L已存在 */
102 /* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
103 /* 若这样的数据元素不存在，则返回值为0 */
104 int LocateElem(LinkList L,ElemType e)
105 {
106 int i=
0;
107 LinkList p=L->
next;
108 while(p)
109 {
110 i++
;
111 if(p->data==e)
/* 找到这样的数据元素 */
112 return i;
113 p=p->
next;
114 }
115
116 return 0;
117 }
118
119 /* 随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
120 void CreateListHead(LinkList *L,
int n)
121 {
122 LinkList p;
123 int i;
124 srand(time(
0));
/* 初始化随机数种子 */
125 *L = (LinkList)malloc(
sizeof(Node));
126 (*L)->next = NULL;
/* 先建立一个带头结点的单链表 */
127 for (i=
0; i < n; i++
)
128 {
129 p = (LinkList)malloc(
sizeof(Node));
/* 生成新结点 */
130 p->data = rand()%
100+
1;
/* 随机生成100以内的数字 */
131 p->next = (*L)->
next;
132 (*L)->next = p;
/* 插入到表头 */
133 }
134 }
135
136 /* 随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
137 void CreateListTail(LinkList *L,
int n)
138 {
139 LinkList p,r;
140 int i;
141 srand(time(
0));
/* 初始化随机数种子 */
142 *L = (LinkList)malloc(
sizeof(Node));
/* L为整个线性表 */
143 r=*L;
/* r为指向尾部的结点 */
144 for (i=
0; i < n; i++
)
145 {
146 p = (Node *)malloc(
sizeof(Node));
/* 生成新结点 */
147 p->data = rand()%
100+
1;
/* 随机生成100以内的数字 */
148 r->next=p;
/* 将表尾终端结点的指针指向新结点 */
149 r = p;
/* 将当前的新结点定义为表尾终端结点 */
150 }
151 r->next = NULL;
/* 表示当前链表结束 */
152 }
153
154 /* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
155 /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
156 Status ListInsert(LinkList *L,
int i,ElemType e)
157 {
158 int j;
159 LinkList p,s;
160 p = *L;
/* 声明一个结点 p，指向头结点 */
161 j =
1;
162 while (p && j < i)
/* 寻找第i个结点 */
163 {
164 p = p->
next;
165 ++
j;
166 }
167 if (!p || j >
i)
168 return ERROR;
/* 第i个元素不存在 */
169 s = (LinkList)malloc(
sizeof(Node));
/* 生成新结点(C语言标准函数) */
170 s->data =
e;
171 s->next = p->next;
/* 将p的后继结点赋值给s的后继 */
172 p->next = s;
/* 将s赋值给p的后继 */
173 return OK;
174 }
175
176 /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
177 /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
178 Status ListDelete(LinkList *L,
int i,ElemType *
e)
179 {
180 int j;
181 LinkList p,q;
182 p = *
L;
183 j =
1;
184 while (p->next && j < i)
/* 遍历寻找第i个元素 */
185 {
186 p = p->
next;
187 ++
j;
188 }
189 if (!(p->next) || j >
i)
190 return ERROR;
/* 第i个元素不存在 */
191 q = p->
next;
192 p->next = q->next;
/* 将q的后继赋值给p的后继 */
193 *e = q->data;
/* 将q结点中的数据给e */
194 free(q);
/* 让系统回收此结点，释放内存 */
195 return OK;
196 }
197
198 /* 单链表反转/逆序 */
199 Status ListReverse(LinkList L)
200 {
201 LinkList current,pnext,prev;
202 if(L == NULL || L->next ==
NULL)
203 return L;
204 current = L->next;
/* p1指向链表头节点的下一个节点 */
205 pnext = current->
next;
206 current->next =
NULL;
207 while(pnext)
208 {
209 prev = pnext->
next;
210 pnext->next =
current;
211 current =
pnext;
212 pnext =
prev;
213 }
214 //printf("current = %d,next = %d \n",current->data,current->next->data);
215 L->next = current;
/* 将链表头节点指向p1 */
216 return L;
217 }
218
219 Status ListReverse2(LinkList L)
220 {
221 LinkList current, p;
222
223 if (L ==
NULL)
224 {
225 return NULL;
226 }
227 current = L->
next;
228 while (current->next !=
NULL)
229 {
230 p = current->
next;
231 current->next = p->
next;
232 p->next = L->
next;
233 L->next =
p;
234 ListTraverse(L);
235 printf(
"current = %d, \n", current ->
data);
236 }
237 return L;
238 }
239
240 int main()
241 {
242 LinkList L;
243 Status i;
244 int j,k,pos,value;
245 char opp;
246 ElemType e;
247
248 i=InitList(&
L);
249 printf(
"链表L初始化完毕，ListLength(L)=%d\n",ListLength(L));
250
251 printf(
"\n1.整表创建（头插法） \n2.整表创建（尾插法） \n3.遍历操作 \n4.插入操作");
252 printf(
"\n5.删除操作 \n6.获取结点数据 \n7.查找某个数是否在链表中 \n8.置空链表");
253 printf(
"\n9.链表反转逆序");
254 printf(
"\n0.退出 \n请选择你的操作：\n");
255 while(opp !=
'0'){
256 scanf(
"%c",&
opp);
257 switch(opp){
258 case '1':
259 CreateListHead(&L,
10);
260 printf(
"整体创建L的元素(头插法)：\n");
261 ListTraverse(L);
262 printf(
"\n");
263 break;
264
265 case '2':
266 CreateListTail(&L,
10);
267 printf(
"整体创建L的元素(尾插法)：\n");
268 ListTraverse(L);
269 printf(
"\n");
270 break;
271
272 case '3':
273 ListTraverse(L);
274 printf(
"\n");
275 break;
276
277 case '4':
278 printf(
"要在第几个位置插入元素？");
279 scanf(
"%d",&
pos);
280 printf(
"插入的元素值是多少？");
281 scanf(
"%d",&
value);
282 ListInsert(&
L,pos,value);
283 ListTraverse(L);
284 printf(
"\n");
285 break;
286
287 case '5':
288 printf(
"要删除第几个元素？");
289 scanf(
"%d",&
pos);
290 ListDelete(&L,pos,&
e);
291 printf(
"删除第%d个元素成功，现在链表为：\n", pos);
292 ListTraverse(L);
293 printf(
"\n");
294 break;
295
296 case '6':
297 printf(
"你需要获取第几个元素？");
298 scanf(
"%d",&
pos);
299 GetElem(L,pos,&
e);
300 printf(
"第%d个元素的值为：%d\n", pos, e);
301 printf(
"\n");
302 break;
303
304 case '7':
305 printf(
"输入你需要查找的数：");
306 scanf(
"%d",&
pos);
307 k=
LocateElem(L,pos);
308 if(k)
309 printf(
"第%d个元素的值为%d\n",k,pos);
310 else
311 printf(
"没有值为%d的元素\n",pos);
312 printf(
"\n");
313 break;
314
315 case '8':
316 i=ClearList(&
L);
317 printf(
"\n清空L后：ListLength(L)=%d\n",ListLength(L));
318 ListTraverse(L);
319 printf(
"\n");
320 break;
321
322 case '9':
323 ListReverse2(L);
324 printf(
"\n反转L后\n");
325 ListTraverse(L);
326 printf(
"\n");
327 break;
328
329 case '0':
330 exit(
0);
331 }
332 }
333
334 }
View Code
代码转载自简明魔法http://www.nowamagic.net/librarys/veda/detail/2241
转载于:https://www.cnblogs.com/CoolRandy/p/4315200.html
相关资源：JAVA上百实例源码以及开源项目
