qwe$
全部元素为:qwe
一共有:3个元素
查找节点的内容,元素序号为:2
2:w
查找节点的位置，内容为:e
e:3
删除节点，节点的位置:1
删除内容为：q
剩余元素为:we
在i插入e:2r
全部元素为:wre
排序后元素为:erw
新链表q:ert$
q合并p后:全部元素为:erwert
Press any key to continue

  1 #include "stdio.h"
  2 #include "malloc.h"
  3 #include "string.h"
  4 
  5 typedef struct Node
  6 { 
  7     char data;
  8     struct Node * next;
  9 }Node, *LinkList;/* LinkList为结构指针类型*/
 10 
 11 //创建一个链表
 12 LinkList CreateFromHead();//头插
 13 LinkList CreateFromTail(); //尾插/*将新增的字符追加到链表的末尾*/
 14 
 15 int ListLength(LinkList L); //L为带头结点的链表求长度
 16 //查找
 17 Node * Get2(LinkList L, int i);//按元素序号查找
 18 Node *Locate2(LinkList L,char key);//按元素值查找
 19 void Get1(LinkList L, int i);//按元素序号查找
 20 void Locate1(LinkList L,char key);//按元素值查找
 21 //更改
 22 
 23 //删除
 24 void DelList(LinkList L,int i,char *e);//删除结点 序号
 25 //插入
 26 void InsList(LinkList L,int i,char e);//插入结点
 27 //合并
 28 LinkList Merge(LinkList LA, LinkList LB);
 29 //排序
 30 void sore(LinkList head);
 31 //打印
 32 void printList(LinkList L);
 33 
 34 //合并 有序
 35 LinkList MergeLinkList(LinkList LA, LinkList LB);//两个从小到大有序链表合并成为有序链表 LC
 36 
 37 int main()
 38 {   /* LinkList为结构指针类型*/
 39     Node *p, *q;
 40     char c, e;
 41     int i;
 42 
 43     p = (Node*)malloc(sizeof(Node));
 44     p = CreateFromTail();
 45 
 46     printf("全部元素为:");
 47     printList(p);
 48     printf("\n一共有:%d个元素\n", ListLength(p));
 49 
 50 //查找
 51     printf("查找节点的内容,元素序号为:");
 52     scanf("%d", &i);
 53     Get1(p, i);
 54     printf("查找节点的位置，内容为:");
 55     scanf(" %c", &c);
 56     Locate1(p,c);
 57 //删除
 58     printf("删除节点，节点的位置:");
 59     scanf("%d", &i);
 60     DelList(p,i,&e);
 61     printf("删除内容为：%c\n", e);
 62     printf("剩余元素为:");
 63     printList(p);
 64     printf("\n");
 65 //插入
 66     printf("在i插入e:");
 67     scanf("%d%c", &i, &e);
 68     InsList(p,i,e);
 69     printf("全部元素为:");
 70     printList(p);
 71     printf("\n");
 72 
 73 //排序
 74     sore(p);
 75     printf("排序后元素为:");
 76     printList(p);
 77     printf("\n");
 78 
 79     printf("新链表q:");
 80     q = (Node*)malloc(sizeof(Node));
 81     q = CreateFromTail();
 82 
 83 //合并
 84     printf("q合并p后:");
 85     //q 为NULL  !!
 86     p = Merge(p, q);
 87 
 88     printf("全部元素为:");
 89     printList(p);
 90     printf("\n");
 91 /*
 92 //有序合并
 93     p = MergeLinkList(q, p);
 94     printf("合并后全部元素为:");//(原来的两个链表本来就有序,p长度短)
 95     printList(p);
 96     printf("\n");
 97 */
 98 
 99     return 0;
100 }
101 
102 
103 
104 
105 
106 //头插
107 LinkList CreateFromHead()
108 {
109     int flag=1; 
110     LinkList L;
111     Node *s;
112     char c;
113     L=(LinkList)malloc(sizeof(Node));
114     L->next=NULL;
115 
116     while(flag) //因为flag是1，所以进入循环体执行
117     {
118         scanf("%c", &c); 
119         //c = getchar(); //假设用户输入ab$,首先读入‘a’
120         if(c !='$') //‘a’不等于‘$’,因此判断成立
121         {    
122             s=(Node*)malloc(sizeof(Node)); 
123             s->data=c;
124             s->next=L->next; 
125             L->next=s;  
126         }
127     }
128     return L;
129 }    
130 //尾插
131 LinkList CreateFromTail() /*将新增的字符追加到链表的末尾*/
132 { 
133     char c;
134     LinkList L;
135     Node *r, *s;
136     L=(LinkList)malloc(sizeof(Node));
137     L->next=NULL;
138     r=L; /*r指针始终动态指向链表的当前表尾*/
139     fflush(stdin);
140     c=getchar();
141     while(c!='$')/*输入“$”时flag为0，建表结束*/
142     {     
143         
144         s=(LinkList)malloc(sizeof(Node)); 
145         s->data=c;
146         r->next=s; 
147         r=s;
148         c=getchar();
149     }
150     r->next=NULL; 
151     return L;
152 }
153 //按元素序号查找
154 void Get1(LinkList L, int i)
155 { //假设开始的情况是：
156     Node *p;
157     int j=0;
158     p=L;
159     while((p->next!=NULL)&&(j<i))        
160     { 
161         p=p->next;
162         j++;                             
163     }
164     // p->next是NULL
165     if(i==j)    
166     {
167         printf("%d:%c\n", i,p->data);
168     }
169     else //不满足判断条件，因此执行else部分
170         printf("未找到");
171 }
172 
173 //按元素值查找
174 void Locate1(LinkList L,char key)
175 { 
176     int i = 1;
177     Node *p;
178     p=L->next;
179     while(p !=NULL)
180     {
181         if(p->data != key)    
182         {
183             i++;
184             p=p->next;  
185         }
186         else 
187         {
188             printf("%c:%d\n", key, i);
189             break;
190         }
191     }
192 }
193 
194 
195 //按元素序号查找
196 Node *Get2(LinkList L, int i)
197 { //假设开始的情况是：
198     Node *p;
199     int j=0;
200     p=L;
201     while((p->next!=NULL)&&(j<i))        
202     { //满足条件，因此进入循环体执行
203         p=p->next;
204         j++;                             
205     }
206     // p->next是NULL，不满足条件，因此不再执行循环体
207     if(i==j)    
208     {
209         printf("%d:%c\n", i,p->data);
210         return p;
211     }
212     else //不满足判断条件，因此执行else部分
213         return NULL;
214 }
215 
216 //按元素值查找
217 Node *Locate2(LinkList L,char key)
218 { 
219     int i = 1;
220     Node *p;
221     p=L->next;
222     while(p !=NULL)
223     {
224         if(p->data != key)    
225         {
226             i++;
227             p=p->next;  
228         }
229         else 
230         {
231             printf("%c:%d\n", key, i);
232             break;
233         }
234     }
235     return p;
236 }
237 
238 //删除结点
239 void DelList(LinkList L,int i,char *e)
240 { 
241     Node *p,*r; 
242     int k =0;
243     p=L; 
244     while(p->next != NULL &&  k < i-1) 
245     { 
246         p=p->next; 
247         k=k+1; 
248     }
249     if(k!=i-1)  
250     {
251         printf("无此节点");
252     }
253     else
254     {
255         r=p->next; 
256         p->next=p->next->next;            
257         *e=r->data;//通过变量e返回删掉的元素值
258         free(r);        //r这个变量及值都没有变动，但是不能再使用r指向的那个空间（因为已经释放）。
259     }
260 }
261 //插入结点
262 void InsList(LinkList L,int i,char e)
263 { 
264     Node *pre,*s;
265     int k=0;
266     pre=L; 
267     while(pre!=NULL&&k<i-1) /*先找到第i-1个数据元素的存储位置,使指针pre指向它*/ 
268     { 
269         pre=pre->next;    
270         k=k+1;  
271     }
272     if(k!=i-1)   
273     { 
274         printf("插入位置不合理！"); 
275         return; 
276     }
277     s=(Node*)malloc(sizeof(Node));/*为e申请一个新的结点*/
278     s->data=e;     /*将待插入结点的值e赋给s的数据域*/
279     s->next=pre->next; 
280     pre->next=s;
281 } 
282 
283 
284 
285 //求长度
286 int ListLength(LinkList L) /*L为带头结点的链表*/
287 {  
288     Node *p; 
289      int j=0; /*用来存放链表的长度*/
290     p=L->next;    
291      while(p!=NULL)
292      {    
293         p=p->next; 
294         j++; 
295     }
296      return j;
297 }
298 
299 
300 //合并
301 LinkList Merge(LinkList LA, LinkList LB)
302 {
303     LinkList p;
304     p = LA->next;
305     while(p->next)
306         p = p->next;
307     p->next = LB->next;
308     free(LB);
309     return LA;
310 }
311 //两个从小到大有序链表合并成为有序链表 LC
312 LinkList MergeLinkList(LinkList LA, LinkList LB)
313 {   
314     Node *pa,*pb;
315     LinkList LC;
316     LinkList r;
317 
318     pa=LA->next;
319     pb=LB->next;
320     LC=LA;
321     LC->next=NULL;
322     r=LC;
323     
324     while(pa!=NULL && pb!=NULL) 
325     {
326         if(pa->data <= pb->data)
327         {
328             r->next=pa;
329             r=pa;
330             pa=pa->next;
331         }
332         else
333         {
334             r->next=pb;
335             r=pb;
336             pb=pb->next;
337         }
338     }
339     if(pa != NULL) 
340         r->next=pa;
341         //return NULL;
342     else//
343         r->next=pb;
344     free(LB);
345     return (LC);
346 }
347 /*
348 bcd$
349 新链表q:aef$
350 合并后全部元素为:abcdef
351 bc$
352 新链表q:adef$
353 合并后全部元素为:abcdef
354 acdg$
355 新链表q:be$
356 合并后全部元素为:abcdeg
357   */
358 //排序
359 void sore(LinkList head)
360 {
361     LinkList pre,cur,next,end, temp;
362     end = NULL;
363     while(head->next != end)
364     {
365         //初始化三个指针 ; 判断是否到达结束位置 ; 三个指针集体后移
366         for(pre=head,cur=pre->next,next=cur->next;  next!=end;  pre=pre->next,cur=cur->next,next=next->next)
367         {
368             if(cur->data > next->data) //从小到大
369             {
370                 pre->next=next;
371                 cur->next=next->next;
372                 next->next=cur;
373                 //此时next变前一项，cur变后一项  交换next cur
374                 temp=cur; 
375                 cur=next; 
376                 next=temp;
377             }
378         }
379         //一轮循环结束 最后一项已经排好 end提前一项 (冒泡原理)
380         end = cur;
381     }
382 }
383 
384 void printList(LinkList L)
385 {
386     Node *p = L;
387     while(p->next)
388     {
389         p = p->next;
390         if(p->data >= 'a' || p->data <='z')
391             printf("%c", p->data);
392         //printf(" ", p->data);
393     }
394 }