【C语言】单链表

wangy

1. #include <stdio.h>
   
2. #include <malloc.h>
   
3. #include <stdbool.h>
   
4. typedef int DataType;
   % q' q6 n& d, |4 P  ?. E
5. typedef struct  linknode
   : ^2 {0 n0 J$ t* u
6. {
   
7.         DataType data;
     F7 f+ W; x; ~; }% q
8.         struct linknode *next;//deference
   7 J" o4 A$ U$ `& R. M5 q2 Q4 Q
9. 
   - X9 |% u3 V% v5 `! Z
10. }Linklist;
    
11. //初始化链表
    + _; ]- c# {! v( |7 P# s4 T
12. Linklist * InitLinklist()
    
13. {
    
14.         Linklist *head; //定义一个结点类型的指针head
    6 V+ _/ f7 Z: K/ j: r
15.         head = (Linklist*)malloc(sizeof(Linklist));//为head动态分配空间
    
16.         (*head).data = NULL;//让head的next（指针域为NULL）
    
17.         return head;
    
18. 
    1 \* {& L( o2 ?. F1 u
19. }
    2 |4 L8 B( o  _" M$ L* [
20. //头插法存放数据
    4 |- e0 g. o0 d5 l2 r+ W/ E/ j
21. void CreateLinklistH(Linklist *head, int n)
    
22. {
      q7 D! ]5 }7 ?' F+ v
23.         Linklist *s;
    
24.         printf("请输入%d个整数:", n);
    
25.         for (int i = 0; i != n; ++i)
    
26.         {
    
27.                 s = (Linklist *)malloc(sizeof(Linklist));
    
28.                 scanf("%d", &((*s).data));
    ) O7 h2 a6 s2 A: G  J2 _3 o0 F
29.                 (*s).next = (*head).next;
    
30.                 (*head).next = s;
    
31.         }
    
32.         printf("创建链表操作成功");
    $ G# B5 n& D+ {
33. }
    
34. //尾插法创建链表
    
35. void CreateLinklistL(Linklist *head, int n)
    % X# k( N+ p, ?8 R: @1 I
36. {
    
37.         Linklist *s, *last;
    
38.         last = head;
    
39.         printf("请输入%d个整数：", n);
    3 [0 u% K* N! ]( `; U
40.         for (int i = 0; i != n; ++i)
    " T" G- g- Y  A  t* \
41.         {
    
42.                 s = (Linklist*)malloc(sizeof(Linklist));
    2 l5 R# @' S& W. ^( d$ Q% e# \
43.                 scanf("%d", &((*s).data));
    $ @& V7 O; u  M0 M1 `* q5 v) e/ j
44.                 (*last).next = s;
    6 X4 A$ C- ], @* h5 d& \1 I
45.                 (*s).next = NULL;
    
46.                 last = s;
    
47. 
    . z5 \7 F* O" n* E( [0 [- g
48.         }
    
49.         printf("建立链表操作成功！");
    
50. }
    
51. //链表长度
    
52. int LengthList(Linklist *head)
    
53. {
    ) g+ J+ O% a3 N2 |
54.         int i;
    
55.         Linklist *p = head;
    ; v' u+ }$ F, ^3 Z
56.         for (i = 0; (*p).next != NULL; ++i)
    
57.         {
    5 j9 S) V* i% {8 u9 z
58.                 p = (*p).next;
    
59.         }
    
60.         return i;
    
61. }
    
62. //查找位置
    1 |; w: A% T+ r" I' G
63. void Locate(Linklist *head, DataType x)
    
64. {
    
65.         int j = 1;
    ; j$ e9 d: j5 t* S2 E1 m* v
66.         Linklist *p = (*head).next;
    " X( }+ f( }$ E. z9 q! T* s* j
67.         while ((*p).next != NULL && (*p).data != x)
    
68.         {
    
69.                 p = (*p).next;
    
70.                 ++j;
    
71.         }
    
72.         if ((*p).next == NULL)
    # S$ s( X- q# s: P" {) i9 @
73.         {
    # e! k9 R" n4 t& S+ V. Z
74.                 printf("为找到值为%d的结点！", x);
    + S/ q$ R2 Y! u) y) D/ |* k9 z
75.         }
    
76.         else printf("在表中第%d位找到值为%d的结点！", j, x);
    
77. }
    
78. 
    
79. //在链表中按照为止查找元素
    
80. void SearchList(Linklist *head, int i)
    ; l  O! I. m8 H. F4 k
81. {
    
82.         if (i > LengthList(head) && i <= 0)
    ' R% Q/ b. k% U" [
83.                 printf("位置越界！");
    4 m" J: d# I# f- q( U# P
84.         else
    + g- E1 C% n7 Z7 d  O
85.         {
    
86.                 Linklist *p = head;
    * e' z) L- U4 B4 D$ [
87.                 for (int j = 0; j != i; ++j)
    $ G# z- u2 S( M, P8 b
88.                 {
    - U" e( ?/ v6 L+ ?1 x% ~
89.                         p = (*p).next;
    ( ?; C" b- T, z3 [8 f8 J3 I0 H
90.                 }
    ) s0 H8 H! ^9 t, u
91.                 printf("在%d位上的元素值为%d。", i, (*p).data);
    
92.         }
    % M; p* @. G- f; i8 O
93. 
    
94. }
    1 j& M& K9 U# r3 V: ?; j5 \8 f0 u
95. 
    8 s  d1 Y: e; F9 H1 c# @
96. //判断链表是否为空表
    + |, `) }$ J  x( ^0 U
97. bool isLinklistNULL(Linklist *head)
    * V  s* m1 ?7 C! D3 a; s# f: M7 [
98. {
    5 u3 Q1 h7 O5 C" J) d
99.         return (*head).next != NULL ? true: false;
    
100. 
     
101. }
     
102. //按位置查入元素
     - @5 O( O$ z( X8 H/ R6 t/ Y& X
103. void InsList(Linklist *head, int i, DataType x)
     ; ~! @# O# z8 k2 C2 f
104. {
     
105.         int j = 0;
     # h+ o0 L9 s& `  i: O! j0 b% a: _' b
106.         Linklist *p, *s;
     1 D: H9 U% A( L0 R/ G
107.         p = head;
     
108.         while ((*p).next != NULL&&j < i - 1)
     + Y0 }3 J7 z! |1 F0 X( _. X7 K
109.         {
     
110.                 p = (*p).next;
     
111.                 ++j;
     
112.         }
     ) t$ {* {  n  g, h  `1 m8 s
113.         if (p != NULL)
     
114.         {
     $ n, L3 ^  J& G5 `* O7 D. }
115.                 s = (Linklist*)malloc(sizeof(Linklist));
     . y' V) m/ Z  u  D
116.                 (*s).data = x;
     9 u4 J* F/ I, b1 k7 U7 b6 I
117.                 (*s).next = (*p).next;
     
118.                 (*p).next = s;
     
119.                 printf("插入元素成功！");
     
120.         }
     " W6 \% s9 k* N; ]; D
121.         else printf("插入元素失败！");
     
122. }
     
123. 
     * V& f1 i& G4 z' S5 ]5 `! b7 ?
124. //按位置删除元素
     $ K. q/ b3 g+ \2 y& j  D! _
125. void DelList(Linklist *head, int i)
     
126. {
     
127.         int j = 0;
     
128.         DataType x;
     
129.         Linklist *s, *p = head;
     
130.         while ((*p).next != NULL&&j < i - 1)
     
131.         {
     + Z" ]; u6 A" y# ?* U
132.                 p = (*p).next;
     
133.                 ++j;
     
134.         }
     
135.         if ((*p).next != NULL&&j == i-1)
     
136.         {
     - p! I9 H" y3 n0 z
137.                 s = (*p).next;
     
138.                 x = (*s).data;
     9 i" e- O. F6 M. D# ?
139.                 (*p).next = (*s).next;
     
140.                 free(s);
     
141.                 printf("删除第%d位上的元素%d成功！", i, x);
     
142.         }
     
143.         else printf("删除操作失败！");
     
144. }
     3 }; a/ v* H1 S
145. void DispList(Linklist *head)
     0 L1 R- H. V* x: V+ Z4 a7 r
146. {
     * ~( m" V5 Q& \  ~' {8 W$ z6 N
147.         Linklist *p = (*head).next;
     
148.         while (p != NULL)
     
149.         {
     , @, V, M: ]+ _( A
150.                 printf("%3d", (*p).data);
     
151.                 p = (*p).next;
     + f& m* q# d& c- _/ ~) V; J
152.         }
     
153. }
     
154. //显示链表
     
155. 
     ; c' \) L! A; R) o" {4 X3 B
156. 
     
157. //菜单显示
     
158. void MenuLine()
     - F/ `" |4 _- i
159. {
     6 O6 ^0 J7 \8 m
160.         printf("\t\t线性表子系统   ");
     
161.         printf("\n==================================\n");
     
162.         printf("\n|             1--建立             |\n");
     
163.         printf("\n|             2--插入             |\n");
     
164.         printf("\n|             3--删除             |\n");
     ( A# R* L1 |, T6 m1 O' h0 E/ [  P% E  l
165.         printf("\n|             4--按位置查找       |\n");
     - h: t6 b' T, c2 {' _
166.         printf("\n|             5--按元素值查找     |\n");
     
167.         printf("\n|             6--求表长           |\n");
     7 d9 m  O$ K% T; O: W7 m$ ^0 T$ B
168.         printf("\n|             7--是否为空表       |\n");
     
169.         printf("\n|             0--退出             |\n");
     2 \- A! l4 T3 a0 m) X  P4 i
170.         printf("\n请输入菜单号:");
     5 ?  E* U; h& }5 H/ j8 Q3 S
171.        
     
172. }
     
173. int main()
     
174. {
     
175.         Linklist *head;
     + s7 \- J; g' u3 ^5 R# R9 h2 J2 w
176.         DataType x;
     3 G3 _$ d, s( V  L: S, t9 k  L
177.         int i, n;
     . E: d- j. m6 e( O1 G# r. u6 `5 u
178.         char ch1='y', ch2,a;
     
179.        
     
180.         while (ch1 == 'y' || ch1== 'Y')
     
181.         {
     ) l& Y8 ]" J0 z& v6 ~0 s
182.                 MenuLine();
     
183.                 scanf("%c", &ch2);
     
184.                 getchar();
     - e3 _2 h- U8 i* c4 S: Z
185.                 switch (ch2)
     1 R9 y4 a6 i, H4 _1 s8 m
186.                 {
     
187.                 case '1':
     
188.                         head = InitLinklist();
     
189.                         printf("请输入要建立线性表的长度：");
     ( B, y8 E) v" {
190.                         scanf("%d",&n);
     
191.    getchar();
     8 w: m; z/ s2 e6 y. {. @1 s
192.                         CreateLinklistL(head,n);
     
193.    getchar();
     7 B/ d/ }! B3 B6 B2 F
194.                         printf("建立后的线性表为：\n");
     
195.                         DispList(head);
     + _1 @  }$ G& ]
196.                         break;
     
197.                 case '2':
     
198.                         printf("请输入要插入元素的位置：");
       a, d; P( _) m) J) ?
199.                         scanf("%d",&i);
     
200.                         getchar();
     % u3 @7 W  y/ J0 y+ j" t; o! C+ U
201.                         printf("请输入要插入元素的值：");
     
202.                         scanf("%d",&x);
     
203.    getchar();
     % b- R& ]4 J, z& G4 x. U
204.                         InsList(head,i,x);
     ! L" K: q( L: `- `: h% Z7 B
205.                         printf("插入以后的线性表为：\n");
     
206.                         DispList(head);
     
207.                         break;
     ' B; m4 m2 M: y7 _6 t9 n
208.                 case '3':
     + n, x0 Q  |! R: \. G5 |
209.                         printf("请输入要删除的元素位置：");
     ) U; Y, W. ~! o' V2 j
210.                         scanf("%d", &i);
     
211.    getchar();
     ( D. h3 V  e! u
212.                         DelList(head,i);
     6 I( u( a; u1 o2 x' Y, t1 f% x
213.                         printf("删除以后的线性表为：\n");
     / o3 A5 g& [( ~! X+ W8 X, r
214.                         DispList(head);
     
215.                         break;
     
216.                 case '4':
     
217.                         printf("请输入要查找元素的位置：");
     
218.                         scanf("%d", &i);
     3 R% g0 B, h2 n/ P) I8 P* K8 z
219.    getchar();
     
220.                         SearchList(head, i);
     ' C# B! g/ b- H
221.                         break;
     
222.                 case '5':
     
223.                         printf("请输入要查找的整数：");
     , Y1 R2 ]6 }6 n, C3 c; T0 K* l
224.                         scanf("%d", &x);
     - A- v$ e( k; `. C9 M! a" p4 G. a
225.    getchar();
     
226.                         Locate(head,x);
     ' q  n$ z, I8 b3 B' I6 q
227.                         break;
     * p2 w# B5 f; f0 G: k: g6 s
228.                 case '6':
     + A# |6 X. F4 m) o
229.                         printf("该线性表的长度为%d！",LengthList(head));
     
230.                         break;
     
231.                 case '7':
     
232.                         if (isLinklistNULL(head)) printf("不是空表"); else printf("是空表"); break;
     
233.                 case '0':
     & h, H& x) q3 y/ O9 l) P$ [) U" x
234.                         ch1 = 'n';
     : p/ l; N5 X& K) X  o% r* a# i
235.                         break;
     7 ], Z) p( J  W9 `7 w& M5 \
236.                 default:printf("输入有误，请重新输入！");
     0 ]" l7 N) {0 ?6 Q  X! k8 V0 D* s' J+ x
237.                
     ! U( q- j& \( t9 U: Z4 U6 ?
238.                 }
     
239.                 if (ch2 != '0')
       A' t$ c; f* R/ S
240.                 {
     
241.                         printf("\n按回车继续操作，按任意键加回车结束程序！\n");
     
242.                         a=getchar();
     
243.                         if (a != '\xA')
     
244.                         {
     
245.                                 getchar();
     
246.                                 ch1 = 'n';
     
247.                         }
     : Q- j& W4 L3 f0 d) z& \0 T
248.                 }
     
249.         }
     
250. 
     - o) H+ q5 T4 q* r+ v7 Z1 a
251.        
     * N* j5 q5 @3 {5 r, W# n
252.        
     3 \& s, `; ?: Q5 Q8 n6 Z  m
253. 
     
254.         return 0;
     3 n" @( d9 R% E$ o
255. }

复制代码