1 #include <stdlib.h>
2 #include <malloc.h>
3 #include <stdio.h>
4
5 typedef struct Node
6 {
7 int data;
8 struct Node *pNext;
9 }NODE,*PNODE;
10
11 PNODE create_list(void);
12 void traverse_list(PNODE);
13 bool is_empty(PNODE pHead);
14 int length_list(PNODE);
15 bool insert_list(PNODE, int, int);
16 bool delete_list(PNODE,int,int*);
17 void sort_list(PNODE);
18
19 int main(void)
20 {
21 PNODE pHead = NULL;
22 int val;
23 pHead = create_list();
24 sort_list(pHead);
25 if (delete_list(pHead, 4, &val))
26 {
27 printf("delete %d ok!\n",val);
28 }
29 else
30 {
31 printf("delete wrong");
32 }
33 traverse_list(pHead);
34 int len = length_list(pHead);
35 if (is_empty(pHead))
36 {
37 printf("list is empty!");
38 }
39 else
40 {
41 printf("list isn't empty！");
42 }
43 return 0;
44 }
45
46 PNODE create_list(void)
47 {
48 int len;
49 int val;//用于存放用户输入的结点的值
50 printf("请输入链表的长度：len=");
51 scanf("%d", &len);
52 PNODE pHead = (PNODE)malloc(sizeof(Node));
53
54 if (NULL == pHead)
55 {
56 printf("分配失败，程序终止!");
57 exit(-1);
58 }
59 PNODE pTail = pHead;
60 pTail->pNext = NULL;
61
62 for (int i = 0; i < len; ++i)
63 {
64 printf("请输入第%d个节点的值", i + 1);
65 scanf("%d", &val);
66 PNODE pNew = (PNODE)malloc(sizeof(Node));
67 if (NULL == pNew)
68 {
69 printf("分配失败，程序终止!");
70 exit(-1);
71 }
72 pNew->data = val;
73 pTail->pNext = pNew;
74 pNew->pNext = NULL;
75 pTail = pNew;
76 }
77 return pHead;
78 }
79
80 void traverse_list(PNODE pHead)
81 {
82 PNODE p = pHead->pNext;
83 while (NULL != p)
84 {
85 printf("%d", p->data);
86 p = p->pNext;
87 }
88 printf("\n");
89 }
90
91 bool is_empty(PNODE pHead)
92 {
93 if (NULL == pHead->pNext)
94 {
95 return true;
96 }
97 return false;
98 }
99
100 int length_list(PNODE pHead)
101 {
102 int length = 0;
103 PNODE p = pHead->pNext;
104 while (NULL != p)
105 {
106 length++;
107 p = p->pNext;
108 }
109 return length;
110 }
111
112 void sort_list(PNODE pHead)
113 {
114 int i, j, t;
115 int len = length_list(pHead);
116 PNODE p, q;
117 for (i = 0, p = pHead->pNext; i < len - 1; ++i, p=p->pNext)
118 {
119 for (j = i + 1, q = p->pNext; j < len; ++j, q = q->pNext)
120 {
121 if (p->data > q->data)
122 {
123 t = p->data;
124 p->data = q->data;
125 q->data = t;
126 }
127 }
128 }
129 return;
130 }
131 //在pHead指向链表的第pos个节点的前面插入一个新的节点，该节点的值为value,pos从1开始
132 bool insert_list(PNODE pHead, int pos, int value)
133 {
134 int i = 0;
135 PNODE p = pHead;
136 while (NULL != p && i < pos - 1)
137 {
138 p = p->pNext;
139 ++i;
140 }
141 if (i > pos - 1 || NULL == p)
142 return false;
143 PNODE pNew = (PNODE)malloc(sizeof(NODE));
144 if (NULL == pNew)
145 {
146 printf("动态分配内存失败！\n");
147 exit(-1);
148 }
149 pNew->data = value;
150 PNODE q = p->pNext;
151 p->pNext = pNew;
152 pNew->pNext = q;
153 return true;
154 }
155
156 bool delete_list(PNODE pHead, int pos, int *pVal)
157 {
158 int i = 0;
159 PNODE p = pHead;
160 while (NULL != p->pNext && i < pos - 1)
161 {
162 p = p->pNext;
163 ++i;
164 }
165 if (i > pos - 1 || NULL == p->pNext)
166 {
167 return false;
168 }
169 PNODE q = p->pNext;
170 *pVal = q->data;
171 //删除p节点后面的节点
172 p->pNext = p->pNext->pNext;
173 free(q);
174 q = NULL;
175 return true;
176 }
177
178
179 /*
180 1.链表的删除，比如删除p后的节点，如何操作？有时很容易遗漏free(r)的操作，导致内存泄漏。
181 可以如下操作：
182 r = p->next;
183 p->next = r->next;
184 free(r);
185 */