谭浩强c语言第五版第9章的习题10，本文主题如下：

1.对参考答案代码进行解析和勘误；

2.提出一种更准确的算法（原来的链表可为无序），给出代码；

1.对参考答案代码进行解析和勘误：

首先给出参考答案源代码：

#include #include struct Student{long num;int score;struct Student *next;};struct Student lista, listb;int n, sum = 0;int main(){struct Student *creat();struct Student *insert(struct Student *, struct Student *);void print(struct Student *);struct Student *ahead, *bhead, *abh;printf("input list a:\n");ahead = creat();sum = sum + n;printf("input list b:\n");bhead = creat();sum = sum + n;abh = insert(ahead, bhead);print(abh);return 0;}struct Student *creat(){struct Student *p1, *p2, *head;n = 0;p1 = p2 = (struct Student *)malloc(sizeof(struct Student));printf("input number & scores of student:\n");printf("if number is 0,stop inputing.\n");scanf_s("%ld %d", &p1->num, &p1->score);head = NULL;while (p1->num!=0){n = n + 1;if (n == 1)head = p1;elsep2->next = p1;p2 = p1;p1 = (struct Student *)malloc(sizeof(struct Student));scanf_s("%ld %d", &p1->num, &p1->score);}p2->next = NULL;return head;}struct Student *insert(struct Student *ah, struct Student *bh){struct Student *pa1, *pa2, *pb1, *pb2;pa2 = pa1 = ah;pb2 = pb1 = bh;do{while ((pb1->num>pa1->num)&&(pa1->next!=NULL)){pa2 = pa1;pa1 = pa1->next;}if (pb1->num num){if (ah == pa1)ah = pb1;elsepa2->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);}void print(struct Student *head){struct Student *p;printf("There are %d records:\n", sum);p = head;if(p!=NULL)do{printf("%ld %d\n", p->num, p->score);p = p->next;} while (p != NULL);}

主函数中：调用创建链表函数creat()建立了a,b链表（在命令行窗口输入链表内容），然后调用函数insert()，将a,b的头指针ahead,bhead传递给insert()函数，在insert()函数中完成合并并排序，最后返回合并后的链表的头指针abh，最后调用函数print()，打印输出合并后的链表。

insert()函数中：

struct Student *pa1, *pa2, *pb1, *pb2;pa2 = pa1 = ah;pb2 = pb1 = bh;

定义Student结构体变量类型的指针，pa1,pa2,pb1,pb2，将链表a的头指针赋给pa1,pa2，将链表b的头指针赋给pb1,pb2。在程序中pa1,pa2指向链表a的节点，pb1,pb2指向链表b的节点。

do{while ((pb1->num>pa1->num)&&(pa1->next!=NULL)){pa2 = pa1;pa1 = pa1->next;}if (pb1->num num){if (ah == pa1)ah = pb1;elsepa2->next = pb1;pb1 = pb1->next;pb2->next = pa1;pa2 = pb2;pb2 = pb1;}} while ((pa1->next != NULL) || (pa1 == NULL && pb1 != NULL));

这个循环体是实现合并+排序的主体算法部分，大致功能是：不断的判断当前链表b的节点编号（num变量）是否小于当前链表a的节点编号，如果小于，则将当前链表b的节点插入到当前链表a的节点之前（升序排列），然后将当前链表a的节点的下一个节点接到当前链表b的节点之后，即完成了一次插入，反复执行这个循环，知道将所有b的节点都插入到a的节点中，并且可保证是按照升序排列的。下面详细讲解此段代码：

while ((pb1->num>pa1->num)&&(pa1->next!=NULL)){pa2 = pa1;pa1 = pa1->next;}

刚开始时，pa2,pa1指向链表a的头节点，pb2,pb1指向链表b的头节点，这个循环表示，如果pb1指向的节点num大于pa1指向的节点num并且pa1指向的节点next（即下一个节点的地址）不为NULL，则反复执行此循环：将当前的链表a的节点的地址存起来（给pa2），然后让pa1指向下一个节点，即保证pa2指向相邻的前一个节点，pa1指向相邻的后一个节点。

直到pb1->numnum时或者pa1->next==NULL，退出此循环，第一种情况表示也就是说我在链表b里找到比链表a里当前的节点小的编号了，那么我需要退出此循环，执行后面的插入操作，第二种情况表示pa1已经指向了链表a的最后一个节点，如果还执行此循环，那么pa1==NULL，再将pb1->num和pa1->num做比较没有意义。

if (pb1->num num){if (ah == pa1)ah = pb1;elsepa2->next = pb1;pb1 = pb1->next;pb2->next = pa1;pa2 = pb2;pb2 = pb1;}

这是插入操作的代码：

当找到pb1->numnum后，如果ah==pa1,表示这是pa1还指向第一个节点，即pa1没有往后移，即b的第一个节点num小于a的第一个节点num，那么把pb1赋给ah，即让ah指向pb1(算法是以链表a为主体不断向其中插入b的节点，形成合并后的链表，最后返回ah也就是新链表的头指针)。然后让pb1 = pb1->next;即pb1指向链表b的下一个节点，然后pb2->next = pa1;即把链表a中pa1后面的一串接到pb2的后面，然后pa2 = pb2;即让pa2指向pa1的前一个节点。最后pb2 = pb1;即完成一个b节点插入后，让pb2和pb1都指向新的链表b的第一个节点。如果ah!=pa1，表示pa1已往后移，即b的第一个节点num小于a后面的某个节点num（pa1->num），此时将该节点插入当pa1之前pa2之后即pa2->next = pb1;

图解：

if (ah == pa1)

else

上述就是一个完整的循环过程，可自行推理。

现在考虑结束此循环的条件，分两种情况考虑，一是链表a的节点为新链表最后一个节点，二是链表b的节点为新链表最后一个节点。

如果链表a的节点为新链表的最后一个节点，那么最后pb1==pb2==NULL；如果链表b的节点为新链表的最后一个节点，也即当前链表b的节点比链表a的最后一个节点要大，那么在这个do…while…循环体中的最后一次循环，先看一下第一个while()语句：

while ((pb1->num>pa1->num)&&(pa1->next!=NULL))

这个语句分两种情况讨论：

1.pa1还没有指向链表a最后一个节点时：

如果pb1->num大于pa1->num，则不断把pa1往后移一个节点，因为链表b的后续节点比链表a的最后一个节点还要大，因此即使pa1指向了链表a中最后一个节点（第一次做指向动作），链表b中将还有节点未插入。

2.pa1已经指向链表a的最后一个节点（第一次做指向动作）时：

由于pa1->next==NULL，因此将不会执行该循环，转入下一个语句：

if (pb1->num num)

因为pb1->num>pa1->num，因此这个if不会执行。

到这里该do…while…循环体就应该时执行最后一次，然后判断退出了，退出之后，直接将此时的pb1赋给pa1->next，就可将链表b的后续节点直接接到已完成前期插入操作的链表a后面，因为链表b的后续节点是排好序且都是比链表a的最后一个节点num大的。

所以退出该do…while…循环体的条件应该是“当pb1==pb2==NULL或者pa1->next==NULL时”。

因此参考答案中的

do{} while ((pa1->next != NULL) || (pa1 == NULL && pb1 != NULL));

是错误的！

我们来看一下这个循环判断条件错在哪里，当pa1->next==NULL时，(pa1->next!=NULL)为假，pa1==NULL为假，因此该循环体可以退出，但是当pb1==pb2==NULL时，只有(pa1==NULL&&pb1!=NULL)为假，(pa1->next!=NULL)无法判断真假，结束不了循环，如果此时，链表a后面还有若干个节点，都是大于链表b的最后一个节点num的，那么可以观察一下，在下一次do…while…循环体中中，while ((pb1->num>pa1->num)&&(pa1->next!=NULL))，(pb1->num>pa1->num)为假，因为pb1==NULL没有意义，因此该while（）语句不会执行，if (pb1->num num)，条件同样为假，不会执行，因此pa1将一直指向链表a的某一节点（比链表b最后一个节点num大的第一个节点，链表a后面可能还会有节点），因此pa1->next!=NULL将一直成立，此do…while…循环体将陷入无限循环！

此错误代码运行结果图示：

当链表b有后续节点比链表a的最后一个节点num还大（即以pa1->next==NULL）结束时，程序可正常运行：

当链表a比链表b的最后一个节点的num还要大的节点有两个及以上时，（即以pb1==pb2==NULL）结束，程序运行会出错：

无法得到合并的新链表。

因此该do…while…循环体的循环判断条件应改为pb1!=NULL&&pa1->next!=NULL

该循环体结束后的下一句：

if ((pb1 != NULL) && (pb1->num > pa1->num) && (pa1->next == NULL))pa1->next = pb1;

这一句是针对”链表b有后续节点比链表a的最后一个节点num还大（即以pa1->next==NULL）结束时，“的情况，此时pb1!=NULL且pb1->num>pa1->num且pa1->next==NULL，此时只用将pb1赋给pa1->next，就把链表b的后续节点一整个挂到了链表a节点的后面。

而“当链表a比链表b的最后一个节点的num还要大的节点有两个及以上时”这种情况，在do…while…循环体中已经由”pb2->next = pa1;”语句将链表a的后续节点一整个挂在了已插入的链表b的最后一个节点的后面，因此不用在循环体外再做处理。

2.提出一种更优的算法，给出代码：

由题意，这是一个将两个链表合成一个有序链表的问题，题干中并没有说明原来的两个链表是有序链表，而参考答案是将两个有序链表合成一个有序链表，不能实现将无序链表合并成有序链表。

下面给出将两个链表（不管是否有序）合并成一个有序链表的代码：

#include #include struct Student{int num;float score;struct Student *next;};int n;int main(){struct Student *creat();struct Student *sort(struct Student *, struct Student *);void print(struct Student *);struct Student *a_head, *b_head, *head;printf("输入链表a：\n");a_head = creat();printf("输入链表b：\n");b_head = creat();head = sort(a_head, b_head);printf("合并后的链表：\n");print(head);return 0;}struct Student *creat(){struct Student *head, *p1, *p2;p1 = p2 = (struct Student *)malloc(sizeof(struct Student));scanf_s("%d %f", &p1->num, &p1->score);n = 0;if(p1->num==0)head = NULL;else{head = p1;while (p1->num != 0){n++;p2 = p1;p1 = (struct Student *)malloc(sizeof(struct Student));p2->next = p1;scanf_s("%d %f", &p1->num, &p1->score);}p2->next = NULL;}return head;}struct Student *sort(struct Student *a_head, struct Student *b_head){struct Student *head, *pa1, *pa2, *pb1, *pb2, *p1, *p2;int min;n = 0;p1 = p2 = head = a_head;while ((a_head!=NULL)||(b_head!=NULL)){pa1 = a_head;pb1 = b_head;if (a_head != NULL)min = a_head->num;elsemin = b_head->num;while (pa1 != NULL){min = min > pa1->num " />