链表中。

【算法源代码】

void InsertSort (LinkList la)

{if(la->next!=NULL) /*链表不为空表*/

{p=la->next->next; /*p指向第一结点的后继*/ la->next->next=NULL;

/*直接插入原则认为第一元素有序，然后从第二元素起依次插入*/ while(p!=NULL)

{r=p->next;/*暂存p的后继*/ q=la;

while(q->next!=NULL&&q->next->datadata)q=q->next;/*查找插入位置*/ p->next=q->next;/*将p结点链入链表*/ q->next=p; p=r; }

12．设有一个双向循环链表，每个结点中除有 prior，data和 next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次LOCATE（L，X）的操作后，被访问的结点（元素值等于X的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的 LOCATE操作的算法。

【算法分析】

1）在双向链表中查找数据值为x的结点，由指针p指向，若找不到，直接返回，否则执行第2步；

2）修改x结点的访问频度freq，并将结点从链表上摘下；

3）顺结点的前驱链查找该结点的位置，即找到一个结点的访问频度大于x结点的访问频度，由指针q指向；若q和p不是相邻结点，调整位置，把p插在q之后。 【算法源代码】

DuLNode * Locate_DuList(DuLinkList *L,int x) { p=(*L)->next;

while(p.data!=x&&p!= (*L)) p=p->next;

if(p==(*L)) return NULL; /*没找到x结点*/ p->freq++;

p->pre->next=p->next;p->next->pre=p->pre; /*将x结点从链表上摘下*/ q=p->pre;

while(q->freq<=p->freq&&p!= (*L)) q=q->pre; /*查找插入位置*/

if(q!=p->pre) /*将x结点插入*/

{q->next->pre=p;p->next=q->next;

q->next=p;p->pre=q; /*调整位置*/ }

return p;

}/*Locate_DuList */

13．已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n和p分别为三个表的长度。

【算法分析】留下三个链表中公共数据，首先查找两表A和B中公共数据，再去C中找有无该数据。要消除重复元素，应记住前驱，要求时间复杂度O（m+n+p），在查找每个链表时，指针不能回溯。 【算法源代码】

9

LinkList Common(LinkList A, LinkList B, LinkList C)

{pa=A->next;pb=B->next; pc=C->next; /*pa，pb和pc是工作指针*/ pre=A;

while(pa && pb && pc) /*当三表均不空时，查找共同元素*/ { while(pa && pb)

if(pa->datadata) /*处理pa结点，后移指针*/ {u=pa;pa=pa->next;free(u);}

else if(pa->data> pb->data)pb=pb->next;

else if (pa && pb) /*处理A和B表元素值相等的结点*/ {while(pc && pc->datadata)pc=pc->next; if(pc)

{if(pc->data>pa->data) /*处理pa结点，后移指针*/ {u=pa;pa=pa->next;free(u);} else

{if(pre==A) /*结果表中第一个结点*/ { pre->next=pa;pre=pa;pa=pa->next}

else if(pre->data==pa->data) /*重复结点不链入A表*/ {u=pa;pa=pa->next;free(u);} else

{pre->next=pa;pre=pa;pa=pa->next;}/*将新结点链入A表 */ pb=pb->next;pc=pc->next; /* 链表的工作指针后移*/ } } else

if(pa==NULL)pre->next=NULL; /*若A表已结束，置A表表尾*/ else /*处理原A表未到尾而B或C到尾的情况*/ {pre->next=NULL; /*置A表表尾标记*/

while(pa!=NULL) /*删除原A表剩余元素。*/ {u=pa;pa=pa->next;free(u);} } }

14．设 head为一单链表的头指针，单链表的每个结点由一个整数域data和指针域next组成，整数在单链表中是无序的。编一函数，将 head链中结点分成一个奇数链和一个偶数链，分别由p，q指向，每个链中的数据按由小到大排列。程序中不得使用malloc申请空间。

【算法分析】本题要求将一个链表分解成两个链表，两个链表都要有序，两链表建立过程中不得使用malloc申请空间，这就是要利用原链表空间，随着原链表的分解，新建链表随之排序。

【算法源代码】

discreat(LinkList p, LinkList q, LinkList head)

{ p=NULL; q=NULL;/*p和q链表初始化为空表*/ s=head;

while(s!=NULL)

{r=s->next; /*暂存s的后继*/ if(s->data%2==0) /*处理偶数*/

if (p==NULL) {p=s;p->next=NULL;} /*第一个偶数结点*/ else { pre=p;

if(pre->data>s->data)

{s->next=pre;p=s;}/*插入当前最小值结点*/ else

{while (pre->next!=NULL)

if (pre->next->datadata) pre=pre->next;/*查找插入位置*/

s->next=pre->next; /*链入结点*/

10

pre->next=s;} }

else/*处理奇数链

if (q==NULL) {q=s;q->next=NULL;} /*第一奇数结点*/ else

{pre=q;

if (pre->data>s->data) {s->next=pre; q=s;} /*修改头指针*/ else

{while (pre->next!=NULL) /*查找插入位置*/ if (pre->next->datadata) pre=pre->next; s->next=pre->next; /*链入结点*/ pre->next=s; } }/*结束奇数链结点*/ s=r; /*s指向新的待排序结点*/ } }

第3章 桟和队列

3.1 选择题

1．一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1≤i≤n）个元素是（ ）

A）不确定 B）n-i+1 C）i D）n-i 【答案】B

【解析】根据栈的性质（LIFO），若输出的第一个元素是n，则表明所有的元素已经入栈，则出栈顺序为n，n-1， ?，3，2，1。

2．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是（ ）

A）6 B）4 C）3 D）2 【答案】C

【解析】根据栈的性质（LIFO）得，e2出栈前，栈中存有e1和e2两个元素，e4出栈前，栈中存有e1、e3和e4三个元素，e4和e3出栈以后，e5和e6入栈，栈中同样存在e1、e5和e6三个元素，然后三个元素依次出栈，所以栈的容量至少应该为3。

3．若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是（ ） A）top=top+1; V[top]=x B）V[top]=x; top=top+1 C）top=top-1; V[top]=x D）V[top]=x; top=top-1 【答案】C 【解析】栈式运算受限的线性表，只允许在栈顶进行插入和删除操作。本题中栈顶指针为n+1，该数组将栈顶放在了下标大的一端，所以在进行入栈操作时top指针应该进行减一操作。通常元素进栈的操作为：先移动栈顶指针后存入元素。

4．如果我们用数组A[1..100]来实现一个大小为100的栈，并且用变量top来指示栈顶，top的初值为0，表示栈空。请问在top为100时，再进行入栈操作，会产生（ ） A）正常动作 B）溢出 C）下溢 D）同步 【答案】B

【解析】当top为100时，表示栈已经满了，此时再进行入栈操作，则会造成溢出。

5．栈在（ ）中应用。

11

A）递归调用 B）子程序调用 C）表达式求值 D）A，Ｂ，Ｃ 【答案】D

7．用链接方式存储的队列，在进行删除运算时（ ） A）仅修改头指针 B）仅修改尾指针

C）头、尾指针都要修改 D）头、尾指针可能都要修改 【答案】D

【解析】若队列中的元素多于一个，删除队列中的队尾元素，只需修改队尾指针；若队列中只有一个元素，删除该元素后，队头队尾指针都需要修改。

8．循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )

A）(rear-front+m)%m B）rear-front+1 C）rear-front-1 D）rear-front 【答案】A

【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的求元素个数的运算可以利用求模运算。

9．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A）1和 5 B）2和4 C）4和2 D）5和1 【答案】B

【解析】循环队列是解决假溢出的问题，通常把一维数组看成首尾相接。在循环意义下的加1运算通常用求模运算来实现。所以入队和出队时的操作分别为：rear=(rear+1)%m，front=(front+1)%m。

10．栈和队列的共同点是（ ）

A）都是先进先出 B）都是先进后出 C）只允许在端点处插入和删除元素 D）没有共同点 【答案】C

【解析】栈和队列都是运算受限的线性表，只允许在表端点处进行操作。 11．在一个链队列中，假定front和rear分别为队头和队尾指针，则插入*s结点的操作为（ ） A）front->next=s;front=s; B）s->next=rear;rear=s; C）rear->next=s;rear=s; D）s->next=front;front=s; 【答案】C

【解析】队列是运算受限的线性表（FIFO），插入元素只能插在队尾，所以需修改队尾指针。

12．判定一个栈S（元素个数最多为MAXSIZE）为空和满的条件分别为（ ） A）S->top!=-1 S->top!=MAXSIZE-1 B）S->top=-1 S->top=MAXSIZE-1 C）S->top=-1 S->top!=MAXSIZE-1 D）S->top!=-1 S->top=MAXSIZE-1 【答案】B

3.2 填空题

1．栈是_____________的线性表，其运算遵循_____________的原则。 【答案】（1）操作受限（或限定仅在表尾进行插入和删除操作） （2）后进先出

2．设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_____________，而栈顶指针值

12