发布时间 : 星期一 文章C语言典例解析更新完毕开始阅读
绩中置应聘实际成绩，录取志愿号预置0等。每个应聘者的基本信息构成链表的一个结点，程序应将该结点插入到应聘者的有序队列中。用一个C语句插入一个队列的结点，只能调用函数来实现。由程序可知，可调用函数insert（）来实现。该函数有两个参数，由参数所给的类型可知，第一个参数是一个指向队列首结点指针的指针，第二个参数是指向应聘者结点的指针，所以（5）空的答案为insert（&head，p）。
程序接着是一个录取循环，为了简便，程序假定不会发生有工种没有人应聘的情况，只要有工种未招满，且还有应聘者，则该工种总能招收到应聘者。这样录取工作的循环条件是公司还未招聘满，且还有应聘者未录取。在录取时，首先从应聘队列中取下一个应聘者，根据该应聘者的志愿，检查该志愿的工种是否还未招满，即实际招收人数还未到计划招收人数。将该条件写成C代码为rz[p－>z[p－>zi]].count
函数insert（STU **p，STU *u）的参数p是指向已知队列的首指针的指针，参数u是要插入的新结点的指针。插入结点*u前，先寻找插入位置。寻找循环从队列首结点开始顺序向后寻找，令*q为寻找时的当前结点，在还有结点情况下（q!=NULL），当*q结点的排队成绩小于*u结点的排队成绩时，应结束寻找循环，新结点插在当前*q之前。反之，应继续向前寻找插入点。为能将*u结点插入在结点*q之前，还需要知道*q结点的前趋结点的指针。因此，此处采用了双指针搜索。即在准备继续向前寻找，修改q之前，先将原当前结点的指针q保护到变量v，然后才更新q。这样，当找到插入位置时（在链表首结点之后），使指针v指向当前结点q的前趋结点。要使q指向当前q结点的后继结点，可用代码q=q－>next实现。因此，（1）空的答案是q=q－>next。完成具体插入操作要区分以下两种情况：第一种情况是插入操作后，*u结点将成为队列的首结点。这种情况要更改队列的首指针。第二种情况是插在队列首结点之后，*q结点之前。这种情况下，只需要插入在结点*v之后即可实现。前者是当指针变量与队列首指针的值相等的情况下，需用新结点指针更改队列首指针；后者用新结点指针更改结点*v结点的后继指针，然后将插入结点的后继指针置为q，即可完成全部插入工作。所以（2）空和（3）空的答案分别为*p＝u和v－>next=u。
13.链表应用2
〔程序说明〕
本系统由n个部件组成，这些部件被物理地分成若干个分离的部件组。同一组内的两个部件i和j，它们或直接相连，或间接相连（部件i和部件j间接相连是指在这两个部件之间有一个部件相连序列，其中部件i和j分别与这相连序列中的某个部件直接相连）。系统的n个部件被统一编号为0，1，?，n-1。本程序输入所有直接相连的部件号对，分别求出系统
各分离部件组中的部件号并输出。
程序根据输入的直接相连的两个部件号，建立n个链表，其中第 i 个链表的首指针为s[i]，其结点是与部件号i直接相连的所有部件号。
程序按下述方法顺序处理各链表：设处理第i个链表，将该链表移至由指针top所指的工作链表。对top链表的各结点作如下处理：从top链表上取出一个结点，根据该结点所指出的相连部件j，将第j 个链表也移至top链表中，并将所取出的结点按部件号从小到大的顺序重新构造第i个链表（该链表中只保留不相同的结点），如此重复，直至top链表为空，第i个链表的重新构造也结束。所有链表处理完毕后，重新构造好的各非空链表即对应系统中的一个部件组。 〔程序〕
# include
typedef struct node{ int data;
struct node * link; }NODE; NODE * s[N]; int i,j,n,t;
NODE * q,* p,* x,* y, * top; void main（）
{ printf（\）; scanf（\）;
for（i=0;i { /* 输入相连部件对，生成相连部件结点键表 */ scanf（\）; /* 输入的部件号小于0结束 */ if（i<0 ││ j<0） break; p=（NODE *）malloc（sizeof（NODE））; p－>data=j;p－>link=s[i];s[i]=p; p=（NODE *）malloc（sizeof（NODE））; p－>data=i;p－>link=s[j];s[j]=p; } for（i=0;i { /* 将第i链表移如top 工作链表，并顺序处理工作链表的各结点 */ q=top; ___（2）___ ; if（s[j=q－>data]!=NULL && j!=i） {/* 将j链表也移入工作链表 */ for（p=s[j]; ___（3）___ ;p=p－>link）; p－>link=top;top=s[j]; ___（4）___ ; } /* 在重新生成的第i 链表中寻找当前结点的插入点 */ for（y=s[i];___（5）___;x=y,y=y－>link）; if（y!=NULL && y－>data==q－>data） free（q）;/* 因重新生成的第i 链表已有当前结点，当前结点删除 */ else { /* 当前结点插入新生成的第i 链表 */ ___（6）___ ; if（___（7）___）s[i]=q; else x－>link=q; } } for（i=0;i { printf（\－>data）; q=p－>link; free（p）; p=q; } printf （\）; } } 答案： （1）top!= NULL （2）top=top－>link （3）p－>link!=NULL （4）s[j]=NULL （5）y!=NULL && y－>datadata （6）q－>link=y （7）y==s[i] 分析： 这是一道考察考生对链表操作掌握程度的试题。程序的工作分为三步：建立链表、处理链表、输出并释放链表空间。建立链表的过程就是依次读入一组组部件号，为每个部件建立一个链表的过程。用指针数组s[ ]存放每个链表的首指针，其中首指针为s[i]的链表存放着与部件号i直接相连的所有部件号。如输入的部件号组为：（0，1），（1，2），（3，4），则以s[0]为首指针的链表中有一个值为1结点，而以s[1]为首指针的链表中有两个值分别为2和0的结点，以s[2]为首指针的链表中有一个值为1结点，以s[3]为首指针的链表中有一个值为4结点，以s[4]为首指针的链表中有一个值为3结点。其余的s[i]均为空。 处理链表的过程是由上面的链表生成分离部件组的过程。分离部件组链表中各结点按部件号由小到大排列。以上面数据为例，最后形成的链表应为：以s[0]为首指针的链表中有三个值，分别为0、1、2的结点，而以s[3]为首指针的链表中有两个值，分别为3、4的结点。原来有值的以s[1]、s[2]、s[4] 为首指针的链表都为空。其中以s[0]、s[3]为首指针的链表就是所求分离部件组的链表。 根据程序说明，处理各链表的过程为：对第i个链表，将该链表移至由指针top所指 的工作链表中。对top链表的各结点进行依次处理：首先从top链表上取出一个结点，然后根据该结点所指示的相连部件j，将第j个链表也移入top链中，最后将取出的结点按部件号从小到大的顺序重新构造第j个链表，如此重复，直到top链表为空。这样第i个链表的重新构造就结束了。所有链表都处理完后，重新构造好的各非空链表即为对应系统中的各分离部件组。 利用上面的程序说明来分析题中所给程序。建立链表后的for（i=0；i 对所取出的结点q的处理分为两步：第一步是将q结点指出的相连部件所对应（链表首指在s[q－>data]中）的链表也加入到top链表中；第二步是将q结点按部件号递增的顺序插入到s[i]中，实现重新构造链表s[i]。 第一步的做法只需将s[q－>data]链表插到top链表首部，程序中用循环语句for（p=s[j]; （3） ；p=p－>link）；找s[j]链表的尾，因此（3）空答案为p－>link!=NULL。在s[j]已插入到top中后，就必须将s[j]赋为空，否则将导致以后会重复移入top链表和重复处理该链表中的结点。因此（4）空的答案为s[j]=NULL。 第二步将q结点插入到链表s[i]中，先在s[i]链表中为q寻找合适的插入位置。程序中采用了双指针搜索方法来查找q的插入位置，其中指针x指向插入位置的前一结点，指针y指向插入位置的后一结点，而（5）空所在位置为判断是否已找到插入位置的判断语句。循环继续的条件是还未找到链表尾（即y非空），并且q所指结点的部件号大于y所指结点的部件号。因此，（5）空的答案为y!=NULL && y－>data if（y==s[i]） s[i]=q; else x－>link=q; 因此，（6）空的答案为q－>link=y。（7）空的答案为y==s[i]。 14.递推实例