谭浩强c语言第五版第9章的习题10，本文主题如下：
1.对参考答案代码进行解析和勘误；
2.提出一种更准确的算法，给出代码；
1.对参考答案代码进行解析和勘误：
首先给出参考答案源代码：
#include <stdio.h>
#include <stdlib.h>
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;
else
p2->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 <= 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);
}
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 <= 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));这个循环体是实现合并+排序的主体算法部分，大致功能是：不断的判断当前链表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->num<=pa1->num时或者pa1->next==NULL，退出此循环，第一种情况表示也就是说我在链表b里找到比链表a里当前的节点小的编号了，那么我需要退出此循环，执行后面的插入操作，第二种情况表示pa1已经指向了链表a的最后一个节点，如果还执行此循环，那么pa1==NULL，再将pb1->num和pa1->num做比较没有意义。
if (pb1->num <= pa1->num)
{
if (ah == pa1)
ah = pb1;
else
pa2->next = pb1;
pb1 = pb1->next;
pb2->next = pa1;
pa2 = pb2;
pb2 = pb1;
}这是插入操作的代码：
当找到pb1->num<=pa1->num后，如果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 <= pa1->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 <= pa1->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 <stdio.h>
#include <stdlib.h>
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;
else
min = b_head->num;
while (pa1 != NULL)
{
min = min > pa1->num ? pa1->num : min;
pa1 = pa1->next;
}
pa1 = pa2 = a_head;
while (pb1 != NULL)
{
min = min > pb1->num ? pb1->num : min;
pb1 = pb1->next;
}
pb1 = pb2 = b_head;
if ((pa1!=NULL)&&(min == pa1->num))
{
a_head = pa1->next;
if (n == 0)
{
head = p1 = pa1;
n++;
}
else
{
p2 = pa1;
p1->next = p2;
p1 = p2;
n++;
}
}
else
{
while ((pa1!=NULL)&&(pa1->num != min) && (pa1->next != NULL))
{
pa2 = pa1;
pa1 = pa1->next;
}
if ((pa1!=NULL)&&(pa1->num == min))
{
pa2->next = pa1->next;
if (n==0)
{
head = p1 = pa1;
n++;
}
else
{
p2 = pa1;
p1->next = p2;
p1 = p2;
n++;
}
}
else
{
if ((pa1!=NULL)&&(pa1->num == min))
{
pa2->next = NULL;
if (n == 0)
{
head = p1 = pa1;
n++;
}
else
{
p2 = pa1;
p1->next = p2;
p1 = p2;
n++;
}
}
else
{
if ((pb1!=NULL)&&(min == pb1->num))
{
b_head = pb1->next;
if (n == 0)
{
head = p1 = pb1;
n++;
}
else
{
p2 = pb1;
p1->next = p2;
p1 = p2;
n++;
}
}
else
{
while ((pb1!=NULL)&&(pb1->num != min) && (pb1->next != NULL))
{
pb2 = pb1;
pb1 = pb1->next;
}
if ((pb1!=NULL)&&(pb1->num == min))
{
pb2->next = pb1->next;
if (n == 0)
{
head = p1 = pb1;
n++;
}
else
{
p2 = pb1;
p1->next = p2;
p1 = p2;
n++;
}
}
else
{
if ((pb1!=NULL)&&(pb1->num == min))
{
pb2->next = NULL;
if (n == 0)
{
head = p1 = pb1;
n++;
}
else
{
p2 = pb1;
p1->next = p2;
p1 = p2;
n++;
}
}
}
}
}
}
}
}
p2->next = NULL;
return head;
}
void print(struct Student *head)
{
while (head!=NULL)
{
printf("%d %f\n", head->num, head->score);
head = head->next;
}
}直接看sort()函数。
a_head指向链表a的头节点，b_head指向链表b的头节点
第53行：
p1 = p2 = head = a_head;先把链表a的头节点当作新链表的头节点（不管它的num是否为最小，这里只是对p2,p1,head赋个初值，以免报错）。
第54行：
while ((a_head!=NULL)||(b_head!=NULL))
{
}该循环体是算法的合并排序算法的主体部分，在"a_head==NULL且b_head==NULL"之前，一直执行该循环（循环体中，a_head和b_head会不断往后移，但都保证分别指向各自的链表，直到把链表a和链表b的所有节点都遍历）。
第56~57行：
pa1 = a_head;
pb1 = b_head;让pa1和pb1分别指向链表a和链表b的头节点（pa1和pa2只用于指向链表a，pb1和pb2只用于指向链表b）。
第58~61行：
if (a_head != NULL)
min = a_head->num;
else
min = b_head->num;当a_head!=NULL时，即链表a中的节点还有剩余的没有插到新链表中去，每次都默认先将a链表的第一个节点为num最小的节点，如果链表a中的节点已经全部都插到新链表中去了，则每次都默认先将b链表的第一个节点为num最小的节点。
第62~66行：
while (pa1 != NULL)
{
min = min > pa1->num ? pa1->num : min;
pa1 = pa1->next;
}在链表a中，找出num最小的那个节点，把num存到min中，
第67行：
pa1 = pa2 = a_head;找完之后，让pa1和pa2指向链表a的头节点。
第68~72行：
while (pb1 != NULL)
{
min = min > pb1->num ? pb1->num : min;
pb1 = pb1->next;
}再在链表b中找num最小的节点，将最小的num存到min中。
第73行：
pb1 = pb2 = b_head;
找完之后，让pb1和pb2指向链表b的头节点。此时就在链表a和链表b中找到了num最小的那个节点，把它作为新链表的头节点。
第74~89行：
if ((pa1!=NULL)&&(min == pa1->num))
{
a_head = pa1->next;
if (n == 0)
{
head = p1 = pa1;
n++;
}
else
{
p2 = pa1;
p1->next = p2;
p1 = p2;
n++;
}
}当num最小的节点刚好是链表a的第一个节点时，我们把下一个节点作为链表a的新的头节点。如果n==0（n为合并后的链表中节点数量计数），表明此时新链表中还没有节点，因此将pa1作为新链表的头节点，并将其赋给p1(p1和p2只用于指向新链表中的节点)。
若n!=0，表明已经有节点了，则将pa1接到最新的一个节点后面，n自增1。
至于为什么判断条件要加上pa1!=NULL，因为当pa1==NULL时，if(min==pa1->num)会出现未知错误，下面的判断条件也都加上了pa1!=NULL或pb1!=NULL。
第90~194行：
else//如果当前num最小的节点不是链表a的第一个节点
{
while ((pa1!=NULL)&&(pa1->num != min) && (pa1->next != NULL))//当前pa1->num!=min且不是链表a的最后一个节点时
{
pa2 = pa1;
pa1 = pa1->next;
}//反复将pa2和pa1后移，直到找到pa1->num==min
if ((pa1!=NULL)&&(pa1->num == min))//如果找到了pa1->num==min
{
pa2->next = pa1->next;//把链表a中num==min的这个节点剔除掉
if (n==0)//如果是第一个节点，把让新链表的头指针指向该节点
{
head = p1 = pa1;
n++;
}
else//如果不是，则将此节点链接到新链表的最新一个节点后面
{
p2 = pa1;
p1->next = p2;
p1 = p2;
n++;
}
}
else//如果没有找到pa1指向了链表a的最后一个节点
{
if ((pa1!=NULL)&&(pa1->num == min))//如果链表a的最后一个节点num为最小
{
pa2->next = NULL;//将链表a的最后一个节点从链表a中剔除
if (n == 0)//如果是第一个节点，把让新链表的头指针指向该节点
{
head = p1 = pa1;
n++;
}
else//如果不是，则将此节点链接到新链表的最新一个节点后面
{
p2 = pa1;
p1->next = p2;
p1 = p2;
n++;
}
}
else//如果找遍链表a的节点，都没有找到num为最小值的节点，则开始遍历b节点
{
if ((pb1!=NULL)&&(min == pb1->num))//在链表b中找num为最小值的节点的方法、代码与上面在链表a中找的一致
{
b_head = pb1->next;
if (n == 0)
{
head = p1 = pb1;
n++;
}
else
{
p2 = pb1;
p1->next = p2;
p1 = p2;
n++;
}
}
else
{
while ((pb1!=NULL)&&(pb1->num != min) && (pb1->next != NULL))
{
pb2 = pb1;
pb1 = pb1->next;
}
if ((pb1!=NULL)&&(pb1->num == min))
{
pb2->next = pb1->next;
if (n == 0)
{
head = p1 = pb1;
n++;
}
else
{
p2 = pb1;
p1->next = p2;
p1 = p2;
n++;
}
}
else
{
if ((pb1!=NULL)&&(pb1->num == min))
{
pb2->next = NULL;
if (n == 0)
{
head = p1 = pb1;
n++;
}
else
{
p2 = pb1;
p1->next = p2;
p1 = p2;
n++;
}
}
}
}
}
}
}第195~197行：
}//插入完一个num为当前最小值的节点之后，再次执行该循环，寻找并插入num为次小值的节点（反复执行该循环，直到a_head==NULL&&b_head==NULL，即链表a和链表b中的节点已经全部插入到了新链表中，成为空表）
p2->next = NULL;//新链表的尾巴赋NULL，新链表到此为止。
return head;//返回新链表的头指针。运行结果：
