【说明】
以下【C程序】完成从指定数据文件中读入职工的工号和他完成产品个数的数据信息，对同一职工多次完成的产品个数进行累计，最后按如表5-11所示的格式输出职工完成产品数量的名次(ORDER)，该名次是按每位职工完成的产品数量(QUANTITY)排序，之后是同一名次的职工人数(COUNT)和他们的职工号(NUMBER，同一名次的职工号以从小到大的顺序输出)。
表5-11 职工完成产品数量名次输出格式表
| ORDER | QUANTITY | COUNT | NUMBER | ||
| 1 | 398 | 3 | 10 | 20 | 21 |
| 4 | 256 | 2 | 3 | 5 | |
| 6 | 192 | 1 | 9 | ||
| 7 | 167 | 2 | 11 | 14 | |
| … | … | … | … | ||
【C程序】
#include＜stdio. h＞
typedef struct ele{
int no, q;
struct ele * next;
}elem;
main(int argc, char ** argv){
FILE *fp; elem *h, *u, *proc();
if(argc==2 &&(fp=fopen(argv[1], "r"))!=NULL){
h=proc(fp);
fclose(fp);
output(h);
while(h I=NULL){
u=h→*next; free(h); h=u;
}
}
}
elem * proc(FILE *fp){
int n, m; elem *u, *v, *p, *base;
base=NULL;
fscanf(fp, "%d’, &m);
while(!feof(fp)){
fscanf(fp, ’%d’, &m);
for(v=base; v!=NULL && v-＞no !=n; u=v, v=v-＞next);
if( (1) )
if( (2) )
base=v-＞next;
else
u-＞next=v-next;
v-＞q+=m;
else
v=(elem *)malloc(Sizeof)elem));
v-＞no=n; v-＞q=m; p=base;
while(p !=NULL)
if( (3) )break;
else {
u=p; p=p-＞next;
}
if( (4) )
base=v;
else
u-＞next=v;
(5) ;
Fscanf(fp, "%d", &n);
}
return base;
}
Output(elem *head){
int count, order; elem *u, *v;
printf("ORDER QUANTITY COUNT NUMBER\n");
u=head; order=1;
while(u !=NULL){
for(count=1, v=u-＞next; (6) ;count++, v=v-＞next);
printf("%4d%9d%6d", order, u-＞q, count);
order+=count;
for(; (7) ;printf("%4d", u-＞no), u=u-＞next);
printf("\n");
}
}
参考答案：
解析：(1)v!=NULL&&v-＞no==n，或其他等价形式 (2)v==base，或其他等价形式 (3)p-＞q＜v-＞q || p-＞q==v-＞q && p-＞no＞n-＞no，或其他等价形式 (4)p==base，或其他等价形式 (5)v-＞next=p，或其他等价形式 (6)v!=NULL && v-＞q==u-＞q，或其他等价形式 (7)count--!=0，或u!=v，或其他等价形式[要点解析] 这是一道要求读者掌握有序链表的特点及其如何在有序链表上实现插入、删除和查找的操作的程序分析题。本题的解答思路如下。 仔细阅读【C程序】可知，该程序代码采用链表结构存储有关信息，链表中的每个节点对应一位职工。在数据输入时，形成一个有序链表(按完成的产品数量和工号排序)。当一个职工有新的数据输入，在累计该职工的完成数量时会改变原来链表的有序性，因此需要对链表中的节点重新进行排序。而对程序的排序操作可以看成是一组查找、删除和插入操作的组合操作，这组操作又和链表的特点密切相关。 链表是用一组任意的存储空间来依次存放线性表中的数据元素及其元素之间关系的存储结构。由于链表的存储空间是在程序运行的过程中动态分配的，需要一个个分配存储空间，因此无须事先估计存储空间大小，也不会出现存储空间的浪费，并能够使存储器中的碎片得到充分的利用，但是存储空间的地址不一定连续。 用链表表示一个数据结构时，为了表示数据元素之间的逻辑关系，每个数据元素的存储空间都包括数据域和指针域两个部分。数据域用来存放数据元素本身的值，指针域用来存放和该数据元素存在某种逻辑关系的其他元素的地址(或对应数组的下标)，从而通过指针域中的指针指示数据元素之间的逻辑关系。 在链表结构中进行插入和删除运算不需要移动数据元素，只需修改数据元素的指针域的地址就可以建立元素之间新的逻辑关系。由于这种结构失去了随机存取的特性，只能依照链接顺序访问，存取效率不高，因此不适合进行查找运算。 本试题函数proc()完成的功能是从给定的数据文件中输入职工的工号(即fscanf(fp, "%d", &n);)和该职工完成的产品数量信息(即fscanf(fp, "%d", &m);)，从而形成一个按照产品数量和工号排序的职工有序链表。例如输入一个工号为n的职工的全部信息后，就利用指针v从链表的首节点开始顺序搜索满足条件(即工号等于n)的节点，这个过程依赖for循环语句(即for(v=base; v !=NuLL && v-＞no !=n;u=v,v=v-＞next);)的实现。当循环条件v!=NULL且v-＞no!=n为真时，说明指针v指向的当前节点存在但却不是满足条件的节点，所以指针v通过语句u=v，v=v-＞next实现向后移动，继而指向下一个节点，然后再重复上述的判断、移动过程，直到找到满足条件的节点或确定链表中根本不存在这样的节点为止。由于这两种结果不能同时发生，所以for循环后的if... else条件语句，先要对上述查找过程可能产生的两种结果做出选择，然后再决定继续执行的操作。又由于在if条件为真的情况下，要执行的复合语句中包含累计产品数量的语句(即v-＞q+=m;)，所以可判断出程序首先是对链表中存在的刚输入职工的工号的情况进行处理，因此(1)空缺处所填写的内容是“v!=NULL&&v-＞no==n”或其他等价形式。 根据上述链表中存在刚输入职工工号的情况，需要重新对该工号职工进行产品数量的累计，从而改变原来链表的有序性，为此应该对链表中的节点重新进行排序。那么，该程序的排序操作可以看成是一组删除、查找和插入操作的组合操作。 首先，将链表中满足条件(即工号为n)的节点v删除。删除分为两种情况：当删除的节点是链表的首节点，即v与base同指向一个节点时，需改变链表的头指针，让它指向首节点的直接后继节点，因此(2)空缺处所填写的内容是“v==base”或其他等价形式；当删除的节点是链表中的其他节点时，需改变链表中要删除节点的直接前驱节点的后继指针。 其次，在有序链表中为上述被删除的节点v寻找合适的插入位置。插入位置是根据待插入的节点(即上述被删除的节点)中产品累计数量的多少及工号的大小与链表中现存节点进行比较确定的。根据它们的比较结果，插入位置可以有以下3种情况(令指针p指向链表中正在与待插入节点进行比较的节点，而指针u用来指向其直接前驱节点)。 1)指针p所指向节点的q值(即产品累计数量)小于待插入节点v的q值(即产品累计数量)，于是将节点v插入到p所指向的节点之前。 ②指针p所指向节点的q值与待插入节点v的q值相等，但前者的no值(即工号)大于后者的no值，于是将节点v插入到p所指向的节点之前。 ③指针p所指向节点的q值比待插入节点v的q值都大，于是一直向后寻找，直到p==NULL为止，这时指针u指向链表中的最后一个节点，因而将节点v插入到链表的尾部，即成为节点U的直接后继。 由以上分析可知，(3)空缺处所填写的内容是“p-＞q＜v-＞q || p-＞q==v-＞q && p-＞no＞n-＞no”或其他等价形式。由于以上分析中前两种情况都属于在指针p所指向节点之前插入节点v，因此要考虑一个关键的插入位置，以及是否在首节点之前插入，即(4)空缺处所填写的内容是“p==base”或其他等价形式，(5)空缺处所填写的内容是“v-＞next=p”或其他等价形式。 函数output()完成的功能是按照指定的格式输出。(6)空缺处所在的for循环实现了相同q值的节点个数的统计，这些节点按照工号从小到大的顺序形成一个有序链表段。为了使表达式正确计算，(6)空缺处需要填入“v!=NULL && v-＞q==u-＞q”或其他等价形式。 由于(7)空缺处所在的for循环实现了有相同产品个数的职工工号的顺序输出，因此(7)空缺处所填写的内容是“count--!=0(或u!=v)”或其他等价形式。