1 #include <stdio.h>
2 #include <stdlib.h>
3
4 typedef
int datatype;
5
6 typedef
struct node
7 {
8 datatype data;
9 //定义结构体类型指针，指向结构体中的元素
10 struct node *
next;
11 }linklist,*linklist_p;
//等价为typedef struct node * linklist_p,用linklist_p代替struct node *
12 //给链表开辟空间,链表的第一个位置的元素指向空指针
13 linklist_p create_linked();
14 //头插入
15 int insert_head(linklist_p L,datatype value);
16 //输出打印链表
17 void show_list(linklist_p L);
18 //头删除
19 int del_head(linklist_p L);
20 //判断链表是否为空，空返回1，非空返回0
21 int empty_list(linklist_p L);
22 //根据给定的value值，插入元素
23 int insert_order(linklist_p L,datatype value);
24 //根据给定的value值删除链表元素
25 int del_order(linklist_p L,datatype value);
26 //更改链表元素
27 void exch_list(linklist_p L, datatype old,datatype
new);
28 //查找链表元素
29 int find_list(linklist_p L,datatype value);
30 //对链表元素进行反转。输出1234反转为4321
31 void reverse_list(linklist_p L);
32 int main(
int argc,
const char *
argv[])
33 {
34 //给链表开辟空间，首地址为L
35 linklist_p L =
create_linked();
36 //判断函数是否调用成功
37 if(NULL ==
L)
38 {
39 printf(
"函数调用失败\n");
40 return -
1;
41 }
42 //依据value值插入数据
43 insert_order(L,
2);
44 insert_order(L,
3);
45 insert_order(L,
4);
46 insert_order(L,
3);
47 show_list(L);
48 //删除数据
49 del_order(L,
4);
50 show_list(L);
51 exch_list(L,
3,
4);
52 show_list(L);
53 printf(
"%d\n",find_list(L,
3));
54 //链表反转
55 reverse_list(L);
56 show_list(L);
57 return 0;
58 }
59
60 linklist_p create_linked()
61 {
62 linklist_p L =(linklist_p) malloc(
sizeof(linklist));
63 if(NULL ==
L)
64 {
65 printf(
"内存开辟失败\n");
66 return NULL;
67 }
68 //链表的第一个位置指向空指针
69 L->next =
NULL;
70 return L;
71 }
72 //头插入，新开辟一块内存空间，地址为p，其中p->next指向L->next（第一次为空），L->next地址为p，指向新开辟的内存空间
73 int insert_head(linklist_p L,datatype value)
74 {
75 linklist_p p = (linklist_p)malloc(
sizeof(linklist));
76 if(p ==
NULL)
77 {
78 printf(
"内存开辟失败\n");
79 return -
1;
80 }
81 p->next = L->
next;
82 L->next =
p;
83 p->data =
value;
84 return 0;
85 }
86 //打印输出链表空间，判断条件是链表的最后一个元素指向空指针NULL
87 void show_list(linklist_p L)
88 {
89 linklist_p p = L->
next;
90 while(p->next!=
NULL)
91 {
92 printf(
"%d",p->
data);
93 p = p->
next;
94 }
95 printf(
"%d\n",p->
data);
96 }
97 //头删除，将L->next赋值给p，即删除第一个有data值的元素，将其下一位的地址即p->next赋值给L->next
98 int del_head(linklist_p L)
99 {
100 linklist_p p = L->
next;
101 if(empty_list(L))
102 {
103 printf(
"链表为空，无法删除\n");
104 return -
1;
105 }
106 L->next = p->
next;
107 free(p);
108 p = NULL;
//记得将删除的元素地址指向空指针
109 return 0;
110 }
111
112 int empty_list(linklist_p L)
113 {
114 return L->next == NULL?
1:
0;
115 }
116
117 //依据value值大小对链表进行插入
118 int insert_order(linklist_p L,datatype value)
119 {
120 //定义两个结构体指针：q用来遍历链表，p作为开辟的内存空间的地址，开辟空间之前首先指向空指针进行初始化
121 linklist_p p =NULL, q =
L;
122 //遍历链表，比较q的下一个元素与value的大小，当其值不大于value值时，继续遍历数组，并且遍历之后发现value最大，满足q->next为NULL
123 while(q->next != NULL && q->next->data <=
value)
124 {
125 q = q->
next;
126 }
127 //当q的下一个元素大于value时，需将存储在新开辟的内存空间的地址为p的元素插入到q之后
128 if((p=(linklist_p)malloc(
sizeof(linklist))) ==
NULL)
129 {
130 printf(
"分配地址失败\n");
131 return -
1;
132 }
133 //给p这个元素赋值value
134 p->data =
value;
135 //先将p指向q的下一个元素
136 p->next = q->
next;
137 //q指向p，完成插入
138 q->next =
p;
139 return 0;
140
141 }
142
143 //删除指定元素（按照指定alue值进行）只删除第一个元素
144 int del_order(linklist_p L,datatype value)
145 {
146 linklist_p p = L,q =
NULL;
147 while(p->next != NULL&&p->next->data !=
value)
148 {
149 p = p->
next;
150 }
151 if(p->next !=
NULL)
152 {
153 q = p->
next;
154 p->next = q->
next;
155 free(q);
156 q =
NULL;
157 }
158 return 0;
159 }
160
161 //替换
162 void exch_list(linklist_p L, datatype old,datatype
new)
163 {
164 linklist_p p =
L;
165 while(p->next != NULL && p->next->data !=
old)
166 {
167 p = p->
next;
168 }
169 p->next->data =
new;
170 }
171
172 //查找
173 int find_list(linklist_p L,datatype value)
174 {
175 while(L->next !=
NULL)
176 {
177 if(L->next->data ==
value)
178 return 1;
179 L = L->
next;
180 }
181 return 0;
182 }
183
184 //倒转链表,假设链表为123，倒转之后为321
185 void reverse_list(linklist_p L)
186 {
187 //定义两个结构体指针，p指向头元素之后的一个元素，q指向空指针
188 linklist_p p = L->next,q =
NULL;
189 //将头元素拿出并指向空指针
190 L->next =
NULL;
191 //对剩余的元素进行遍历，从头元素之后的一个元素开始
192 while(p !=
NULL)
193 {
194 //将头元素之后的第一个元素拿出，将其地址赋值给q
195 q =
p;
196 //此时p指向头元素之后的第二个元素
197 p = p->
next;
198 //此时q（即拿出的头元素之后的第一个元素）指向空指针（原头元素所指向位置）
199 q ->next = L->
next;
200 //头元素指向q（拿出的头元素之后的第一个元素）
201 L->next =
q;
202 //此后继续遍历，头元素之后的第二个元素放在头元素和第一个元素之间
203 }
204 }
转载于:https://www.cnblogs.com/billcharint/p/10724537.html
