【整理】有序单链表的去重

有序单链表的去重

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 
  4 typedef int Elemtype;
  5 typedef struct Node
  6 {
  7     Elemtype data;
  8     struct Node *next;
  9 }Node, *LinkedList;
 10 
 11 //单链表的初始化
 12 LinkedList LinkedListInit()
 13 {
 14     Node *L;
 15     L = (Node*)malloc(sizeof(Node));
 16     if (L == NULL)
 17     {
 18         printf("申请内存空间失败
");
 19     }
 20     L->next = NULL;
 21     return L;
 22 }
 23 
 24 //单链表的创建一：头插法建立单链表
 25 LinkedList LinkedListCreatH()
 26 {
 27     Node *L;
 28     L = (Node *)malloc(sizeof(Node));
 29     L->next = NULL;
 30 
 31     Elemtype x;
 32     while (scanf("%d", &x) != EOF)
 33     {
 34         Node *p;
 35         p = (Node *)malloc(sizeof(Node));
 36         p->data = x;
 37         p->next = L->next;
 38         L->next = p;
 39     }
 40     return L;
 41 }
 42 
 43 //单链表的创建二：尾插法建立单链表
 44 LinkedList LinkedListCreatT()
 45 {
 46     Node *L;
 47     L = (Node *)malloc(sizeof(Node));
 48     L->next = NULL;
 49     Node *r;
 50     r = L;
 51     Elemtype x;
 52     while (scanf("%d", &x) != EOF)
 53     {
 54         Node *p;
 55         p = (Node *)malloc(sizeof(Node));
 56         p->data = x;
 57         //p->next = NULL;
 58         r->next = p;
 59         r = p;
 60     }
 61     r->next = NULL;
 62     return L;
 63 }
 64 
 65 //单链表的插入，在链表的第i个位置插入x的元素
 66 //要在第i个位置插入，就得先找到第(i-1)个位置，插在它后面
 67 LinkedList LinkedListInsert(LinkedList L, int i, Elemtype x)
 68 {
 69     Node *pre;
 70     pre = L;
 71     int tempi = 0;
 72     for (tempi = 1; tempi < i; tempi++)
 73         pre = pre->next;
 74     Node *p;
 75     p = (Node *)malloc(sizeof(Node));
 76     p->data = x;
 77     p->next = pre->next;
 78     pre->next = p;
 79     return L;
 80 }
 81 
 82 //单链表的删除，在链表中删除第一个值为x的元素
 83 LinkedList LinkedListDelete(LinkedList L, Elemtype x)
 84 {
 85     Node *pre, *p;
 86     p = L->next;
 87     while (p->data != x)
 88     {
 89         pre = p;
 90         p = p->next;
 91     }
 92     pre->next = p->next;
 93     free(p);
 94     return L;
 95 }
 96 
 97 //单链表的反转
 98 LinkedList LinkedListReverse(LinkedList L)
 99 {
100 
101     Node *rhead = NULL;
102     Node *prev = NULL;
103     Node *p = L->next;//如果原链表的头是一个结点，结点的内容为任意值，p要指向头的下一个结点才是链表的第一个值
104                       //Node *p = L;//如果原链表的头是一个指针，p直接等于Lj就可以了，L指的就是链表的第一个值
105     Node *pnext = NULL;
106     while (p != NULL)
107     {
108         pnext = p->next;
109         if (pnext == NULL)
110             rhead = p;
111         p->next = prev;
112         prev = p;
113         p = pnext;
114     }
115     free(L);
116     return rhead;
117 }
118 
119 //有序单链表的去重一
120 //输入1->2->2->3,输出1->2->3
121 LinkedList DeleteDuplicates_1(LinkedList L)
122 {
123     if (L == NULL || L->next == NULL||L->next->next==NULL)
124         return L;
125     //if (L == NULL || L->next == NULL)//如果不存在哨兵结点
126     //    return L;
127     Node *pre;
128     Node *p;
129     Node *pnext;
130     pre = L->next;//因为第一个结点L是哨兵结点,所以指向L的下一个结点
131     p = L->next->next;
132     //pre = L;//如果不存在哨兵结点
133     //p = L->next;
134     while (p != NULL)
135     {
136         pnext = p->next;
137         if (pre->data == p->data)
138         { 
139             pre->next = pnext;
140             free(p);
141         }
142         else
143             pre = p;
144         p = pnext;
145     }
146     return L;
147 }
148 
149 //有序单链表的去重二
150 //输入1->2->2->3,输出1->3
151 //输入1->1->2->3,输出2->3
152 LinkedList DeleteDuplicates_2(LinkedList L)//如果存在哨兵结点
153 {
154     if (L == NULL || L->next == NULL || L->next->next == NULL)
155         return L;
156     Node *prere;
157     Node *pre;
158     Node *p;
159     Node *pnext;
160     int flag = 0;
161     prere = L;
162     pre = L->next;//因为第一个结点是哨兵结点
163     p = L->next->next;
164     //pre = L;//如果不存在哨兵结点
165     //p = L->next;
166     while (p != NULL)
167     {
168         pnext = p->next;
169         if (pre->data == p->data)
170         {
171             pre->next = pnext;
172             free(p);
173             flag = 1;
174         }
175         else
176         {
177             if (flag == 1)
178             {
179                 prere->next = p;
180                 free(pre);
181                 pre = p;
182                 flag = 0;
183             }
184             else
185             {
186                 prere = pre;
187                 pre = p;
188             }
189         }
190         p = pnext;
191     }
192     return L;
193 }
194 
195 LinkedList DeleteDuplicates_3(LinkedList L)//如果不存在哨兵结点
196 {
197     if (L == NULL || L->next == NULL)
198         return L;
199     Node *prere;
200     Node *pre;
201     Node *p;
202     Node *pnext;
203     int flag = 0;
204     pre = L;//如果不存在哨兵结点
205     prere = L;
206     prere--;
207     p = L->next;
208     while (p != NULL)
209     {
210         pnext = p->next;
211         if (pre->data == p->data)
212         {
213             pre->next = pnext;
214             free(p);
215             flag = 1;
216         }
217         else
218         {
219             if (flag == 1)
220             {
221                 if (pre == L)
222                 {
223                     L = p;
224                     free(pre);
225                     pre = p;
226                     prere = p;
227                     prere--;
228                 }
229                 else
230                 {
231                     prere->next = p;
232                     free(pre);
233                     pre = p;
234                 }
235                 flag = 0;
236             }
237             else
238             {
239                 prere = pre;
240                 pre = p;
241             }
242         }
243         p = pnext;
244     }
245     if (flag == 1)
246     {
247         if (pre == L)
248         {
249             L = p;
250             free(pre);
251             pre = p;
252             prere = p;
253             prere--;
254         }
255         else
256         {
257             prere->next = p;
258             free(pre);
259             pre = p;
260         }
261         flag = 0;
262     }
263     return L;
264 }
265 
266 int main()
267 {
268     LinkedList list, start;
269     
270     //单链表的创建一：头插法建立单链表
271     printf("请输入单链表的数据：");
272     list = LinkedListCreatH();
273     for (start = list->next; start != NULL; start = start->next)
274         printf("%d", start->data);
275     printf("
");
276     
277     //单链表的创建二：尾插法建立单链表
278     printf("请输入单链表的数据：");
279     list = LinkedListCreatT();
280     for (start = list->next; start != NULL; start = start->next)
281         printf("%d", start->data);
282     printf("
");
283     
284     //单链表的插入，在链表的第i个位置插入x的元素
285     int i, x;
286     printf("请输入插入数据的位置：");
287     scanf("%d", &i);
288     printf("请输入插入数据的值：");
289     scanf("%d", &x);
290     LinkedListInsert(list, i, x);
291     for (start = list->next; start != NULL; start = start->next)
292         printf("%d", start->data);
293     printf("
");
294 
295     //单链表的删除，在链表中删除第一个值为x的元素
296     printf("请输入要删除的元素的值：");
297     scanf("%d", &x);
298     LinkedListDelete(list, x);
299     for (start = list->next; start != NULL; start = start->next)
300         printf("%d", start->data);
301     printf("
");
302 
303     //单链表的反转
304     LinkedList rhead;
305     rhead = LinkedListReverse(list);
306     for (start = rhead; start != NULL; start = start->next)
307         printf("%d", start->data);
308     printf("
");
309     
310 
311     /*************************************************************/
312     //单链表的创建二：尾插法建立单链表
313     printf("请输入单链表的数据：");
314     list = LinkedListCreatT();
315     for (start = list->next; start != NULL; start = start->next)
316         printf("%d", start->data);
317     printf("
");
318     
319     //有序单链表的去重一
320     //输入1->2->2->3,输出1->2->3
321     DeleteDuplicates_1(list);
322     for (start = list->next; start != NULL; start = start->next)
323         printf("%d", start->data);
324     printf("
");
325     
326 
327     //有序单链表的去重二
328     //输入1->2->2->3,输出1->3
329     //输入1->1->2->3,输出2->3
330     DeleteDuplicates_2(list);//如果存在哨兵结点
331     for (start = list->next; start != NULL; start = start->next)
332         printf("%d", start->data);
333     printf("
");
334     
335     rhead=DeleteDuplicates_3(list);//如果不存在哨兵结点
336     for (start = rhead; start != NULL; start = start->next)
337         printf("%d", start->data);
338     printf("
");
339 
340     system("pause");
341     return 0;
342 }
343 //注意：结束输入的时候连续输入三个ctrl+z