构建链表并排序

Ranbo_

建立一个链表。将链表排序并输出。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct Node
   
5. {
   
6.     int data;
   
7.     struct Node *next;
   
8. }LNode;
   
9. 
   
10. int main()
    
11. {
    
12.     int n;
    
13.     while(scanf("%d", &n) != EOF)
    
14.     {
    
15.         int i;
    
16.         int input;
    
17.         LNode *L;
    
18.         L = (LNode *)malloc(sizeof(LNode));
    
19.         L -> next = NULL;
    
20.         LNode *pre = L;
    
21.         LNode *p;
    
22.         for(i = 0; i < n; i++)
    
23.         {
    
24.             scanf("%d ", &input);
    
25.             p = (LNode *)malloc(sizeof(LNode));
    
26.             p -> next = NULL;
    
27.             p -> data = input;
    
28.             pre -> next = p;
    
29.             pre = p;
    
30.         }//创建链表
    
31.         
    
32.         //直接插入排序
    
33.         pre = L -> next;p = pre -> next;//pre指向p的前面
    
34.         LNode *ppre = L;//插入时与pre用于定位
    
35.         while(p != NULL)
    
36.         {
    
37.             if(p -> data >= pre -> data)
    
38.             {
    
39.                 pre = p; p = p -> next;
    
40.             }
    
41.             else
    
42.             {
    
43.                 LNode *t = pre;
    
44.                 pre = ppre -> next;
    
45.                 while(p -> data >= pre -> data)
    
46.                 {
    
47.                     ppre = pre; pre = pre -> next;
    
48.                 }
    
49.                 t -> next = p -> next;
    
50.                 p -> next = pre;
    
51.                 ppre -> next = p;
    
52.                 p = t -> next;
    
53.                 pre = t;
    
54.                 ppre = L;
    
55.             }
    
56.         }
    
57.         p = L -> next;
    
58.         for(i = 0; i < n; i++)
    
59.         {
    
60.             printf("%d ", p -> data);
    
61.             p = p -> next;
    
62.         }
    
63.         printf("\n");
    
64.     }
    
65. }
    

复制代码

一定要给头结点也分配一个空间，否则会有非法访问的问题。