|
楼主 |
发表于 2020-4-2 23:52:36
|
显示全部楼层
加了一些注释
- <font face="Times New Roman">#include<stdio.h>
- #define LEN sizeof(struct Student *)
- struct Student
- {
- int num;
- float score;
- struct Student *next;
- };
-
- int n;
- //从键盘输入链表
- struct Student *creat()
- {
- struct Student *head,*p1,*p2;
-
- p1=p2=(struct student *)malloc(LEN);
- scanf("%d %f",&p1->num,&p1->score);
- head=NULL;
- n=0;
- while(p1->num!=0)
- {
- n++;
- if(n==1) head=p1;
- else p2->next=p1;
- p2=p1;
- p1=(struct student *)malloc(LEN);
- scanf("%d %f",&p1->num,&p1->score);
- }
- p2->next=NULL;
- return head;
- }
- //打印输出链表
- void print(struct Student *p)
- {
- while(p!=NULL)
- {
- printf("%-8d%-8.2f\n",p->num,p->score);
- p=p->next;
- }
- }
- //第一种方法,常规思路
- #if(0)
- struct Student *combine(struct Student *a,struct Student *b)
- {
- struct Student *res,*p;
- res=p;
- while(a!=NULL&&b!=NULL)
- {
- if(a->num>b->num)
- {
- p->next=b;
- b=b->next;
- }
- else
- {
- p->next=a;
- a=a->next;
- }
- p=p->next;
- }
- if(a==NULL) p->next=b;
- if(b==NULL) p->next=a;
-
- return res->next;
- }
- #endif
- //递归方法
- #if(0)
- struct Student *combine(struct Student *a,struct Student *b)
- {
- struct Student *res;
- if(a==NULL) return b;
- if(b==NULL) return a;
-
- if(a->num<b->num)
- {
- res=a;
- res->next=combine(a->next,b);
- }
- else
- {
- res=a;
- res->next=combine(a,b->next);
- }
-
- return res;
- }
- #endif
- //谭浩强代码
- #if(1)
- struct Student *combine(struct Student *ah,struct Student *bh)
- {
- struct Student *pa1,*pa2,*pb1,*pb2;
- pa1=pa2=ah;
- pb1=pb2=bh;
-
- do
- {
- while((pb1->num>pa1->num)&&(pa1->next!=NULL))
- {
- pa2=pa1;
- pa1=pa1->next;
- }
- if(pb1->num<=pa1->num)
- {
- if(ah==pa1) ah=pb1;
- else pa2->next=pb1;
- pb1=pb1->next;
- pb2->next=pa1;//到这里看不懂了
- pa2=pb2;
- pb2=pb1;
- }
- }while((pa1->next!=NULL)||(pa1==NULL&&pb1!=NULL));
- if((pb1!=NULL)&&(pb1->num>pa1->num)&&pa1->next==NULL) pa1->next=pb1;
- return ah;
- }
- #endif
- int main()
- {
- struct Student *a,*b,*pt;
-
- printf("请输入链表a:\n");
- a=creat();
- printf("请输入链表b:\n");
- b=creat();
-
- pt=combine(a,b);//调用合并函数
- print(pt);//打印结果
- return 0;
- }</font>
复制代码 |
|