demo002.链表操作

链表逆序：
https://blog.csdn.net/ljyljyok/article/details/77996029
  1 //链表操作:该示例中，链表头节点不存储数据
  2 //1.链表创建
  3 //2.链表遍历，打印
  4 //3.链表节点长度统计
  5 //4.链表删除
  6 //5.插入节点
  7 //6.删除节点
  8 //7.拼接链表
  9 //8.倒序
 10 //9.排序
 11 
 12 #include <stdio.h>
 13 #include <stdlib.h>
 14 #include <string.h>
 15 //declaration of node
 16 //一个链表节点定义Node，链表节点指针定义PNode
 17 typedef struct node
 18 {
 19     int value;
 20     struct node* pNext;
 21 }Node,*PNode;
 22 //operations of list
 23 PNode list_creat(void);
 24 void list_free(PNode pHead);
 25 void list_display(PNode    pHead);
 26 int list_len(PNode pHead);
 27 void list_delete(PNode pHead, int num);
 28 void list_insert(PNode pHead, int num);
 29 PNode list_splice(PNode pHead1, PNode pHead2);
 30 void list_reverse(PNode pHead);
 31 void list_sort_bubble(PNode pHead);
 32 
 33 int main()
 34 {
 35     int n=0;
 36     PNode p = list_creat();
 37     list_display(p);
 38     
 39     list_sort_bubble(p);
 40     printf("sorted:
");
 41     list_display(p);
 42     //n = list_len(p);
 43     //printf("len of list p=%d
",n);
 44     //list_insert( p,  3); list_display(p);
 45     //list_delete( p,  2); list_display(p);
 46     /*PNode p2 = list_creat();
 47     list_display(p2);
 48     p=list_splice(p, p2);
 49     list_display(p);*/
 50     //list_reverse(p); list_display(p);
 51     list_free(p);
 52     return 0;
 53 }
 54 //1.根据输入创建链表
 55 PNode list_creat(void)
 56 {
 57     int i;
 58     int len;
 59     int value;
 60     PNode pHead =(PNode)malloc(sizeof(Node));
 61     pHead->pNext = NULL;
 62     PNode pTail = pHead;
 63     printf("Please input nums of nodes:
");
 64     scanf_s("%d",&len);
 65     for (i = 0; i < len; i++)
 66     {
 67         PNode pNew = (PNode)malloc(sizeof(Node));
 68         printf("Please input value of the current node:
");
 69         scanf_s("%d", &value);
 70         pNew->value = value;
 71         pTail->pNext = pNew;
 72         pNew->pNext = NULL;
 73         pTail = pNew;
 74     }
 75     return pHead;
 76 }
 77 //删除链表
 78 void list_free(PNode pHead)
 79 {
 80     PNode p = pHead;
 81     PNode pb = NULL;
 82     while (p!= NULL)
 83     {
 84         pb = p->pNext;
 85         free(p);
 86         p = pb;
 87     }
 88     printf("current list deleted!!!
");
 89 }
 90 //打印链表
 91 void list_display(PNode    pHead)
 92 {
 93     PNode p = pHead->pNext;
 94     printf("list display:
");
 95     while (p != NULL)
 96     {
 97         printf("%d
", p->value);
 98         p = p->pNext;
 99     }
100 }
101 //遍历，统计长度
102 int list_len(PNode pHead)
103 {
104     int len = 0;
105     PNode p = pHead->pNext;
106     while (p != NULL)
107     {
108         p = p->pNext;
109         len++;
110     }
111     return len;
112 }
113 
114 //指定位置插入节点
115 void list_insert(PNode pHead,int num)
116 {
117     PNode p = pHead->pNext;
118     int i = 1;int value;
119     while (i != num )
120     {
121         p = p->pNext;
122         i++;
123     }//i==num
124     PNode pNew = (PNode)malloc(sizeof(Node));
125     printf("Please input value of the current node:
");
126     scanf_s("%d", &value);
127     pNew->value = value;
128     pNew->pNext = p->pNext;
129     p->pNext = pNew;
130 }
131 //指定位置删除节点
132 void list_delete(PNode pHead,int num)
133 {
134     PNode p = pHead->pNext;
135     PNode pb = NULL;
136     int i = 1;
137     while (i != (num - 1))
138     {
139         p = p->pNext;
140         i++;
141     }//i==num-1
142     pb = p->pNext->pNext;
143     free(p->pNext);
144     p->pNext = pb;
145 }
146 //拼接链表
147 PNode list_splice(PNode pHead1, PNode pHead2)
148 {
149     PNode p = pHead1->pNext;
150     while (p->pNext != NULL)
151     {
152         p = p->pNext;
153     }
154     p->pNext = pHead2->pNext;
155     free(pHead2);
156     return pHead1;
157 }
158 void list_reverse(PNode pHead)
159 {
160     PNode p=pHead->pNext;//指向第一个节点
161     PNode pa=NULL;
162     PNode pb;
163     while (p != NULL)
164     {
165         pb = p->pNext;
166         p->pNext = pa;
167         pa = p;
168         p = pb;
169         //执行一次循环后，反转一个节点，并把指针pa，p，pb向后移动一个节点
170         //执行一次后，至此，p=pb同时指向下一个待反转节点
171     }
172     pHead->pNext = pa;
173 }
174 //排序
175 void list_sort_bubble(PNode pHead)
176 {
177     int i, j;
178     PNode pa = pHead;
179     PNode p = pHead->pNext;
180     PNode pb; 
181     PNode pc;
182     PNode pend;
183     pend = NULL;//pend 初始值指向链表尾节点
184     p = pHead->pNext;
185     while (pend!=pHead->pNext)
186     {
187         pa = pHead;
188         p = pHead->pNext;
189         while (p->pNext != pend)
190         {
191             pb = p->pNext;//更新pb（待比较节点）
192             pc = pb->pNext;//更新pc    
193             if (p->value > pb->value)
194             {
195                 pa->pNext = pb;
196                 pb->pNext = p;
197                 p->pNext = pc;//swap 
198                 pa = pb;//更新pa
199             }
200             else
201             {
202                 pa = p;
203                 p = p->pNext;    
204             }
205         }
206         pend = p;//排序终结点前移一个节点
207     }
208 }