1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 typedef struct student //声明结构体
5 {
6 int num;
7 struct student *pnext;
8 }stu,*pstu;
9 void link_sort_insert(pstu *,pstu *,int); //建立有序链表
10 void link_show(pstu );
11 void link1_merge_link2(pstu *phead1,pstu *ptail1,pstu *phead2,pstu *ptail2); //把链表2合并到1
12 void main(){
13 pstu phead1,ptail1,phead2,ptail2;
14 int i;
15 phead1 = NULL;
16 ptail1 = NULL;
17 phead2 = NULL;
18 ptail2 = NULL;
19 while(scanf("%d",&i) != EOF){ //建立链表1
20 link_sort_insert(&phead1,&ptail1,i);
21
22 }
23 link_show(phead1);
24 while(scanf("%d",&i) != EOF){ //建立链表2
25 link_sort_insert(&phead2,&ptail2,i);
26
27 }
28 link_show(phead2);
29 link1_merge_link2(&phead1,&ptail1,&phead2,&ptail2); //合并
30 link_show(phead1);
31 system("pause");
32
33 }
34 void link_sort_insert(pstu *phead,pstu *ptail,int i){ //建立有序链表
35 pstu pnew,pcur,ppre;
36 pnew = (pstu)malloc(sizeof(stu));
37 memset(pnew,0,sizeof(stu));
38 pnew->num = i;
39 if(*phead == NULL){
40 *phead = pnew;
41 *ptail = pnew;
42 }
43 else if((*phead)->num > i){
44 pnew->pnext = *phead;
45 *phead = pnew;
46
47 }
48 else{
49 pcur = *phead;
50 ppre = *phead;
51 while(pcur != NULL){
52 if(pcur->num > i){
53 pnew->pnext = ppre->pnext;
54 ppre->pnext = pnew;
55 break;
56 }
57 ppre = pcur;
58 pcur = pcur->pnext;
59 }
60 if(pcur == NULL){
61 (*ptail)->pnext = pnew;
62 *ptail = pnew;
63 }
64 }
65
66 }
67 void link1_merge_link2(pstu *phead1,pstu *ptail1,pstu *phead2,pstu *ptail2){ //把链表2合并到1
68 pstu i,ppre,pcur;
69 pcur = *phead1; //pcur ppre 指向链表1头结点
70 ppre = *phead1;
71 while(*phead2 != NULL){
72 i = *phead2; //记录链表2头结点的当前位置
73 *phead2 = (*phead2)->pnext; //链表头结点指向下1个结点
74 if((*phead1)->num > i->num){ //判断链表1头结点是否大于i
75 i->pnext = *phead1; //如果大于，插入头结点
76 *phead1 = i;
77 pcur = *phead1; //pcur ppre 重新指向链表1头结点
78 ppre = *phead1;
79 }
80 else{ //链表1头结点不大于i
81 while(pcur != NULL){
82 if(pcur->num > i->num){ //判断链表1当前节点pcur是否大于i
83 i->pnext = ppre->pnext; //若大于i 则插入，循环结束，pcur不动
84 ppre->pnext = i;
85 break;
86 }
87 ppre = pcur; //若cur <=i 记录当前pcur，pcur指向下一个位置
88 pcur = pcur->pnext;
89 }
90 if(pcur == NULL){ //如果链表1达到尾结点，i插入到链表1尾节点
91 (*ptail1)->pnext = i;
92 *ptail1 = i;
93 }
94 }
95 }
96 *phead2 = NULL; //释放
97 *ptail2 = NULL;
98 }
99 void link_show(pstu phead){
100 pstu pshow;
101 pshow = phead;
102 if(phead == NULL)
103 {
104 printf("no exsit\n");
105 return;
106 }
107 while(pshow != NULL){
108 printf("%d ",pshow->num);
109 pshow = pshow->pnext;
110 }
111 putchar('\n');
112 }