《数据结构-C语言描述》习题及答案-耿国华

第1章绪论

习题

一、问答题

1.什么是数据结构？

2.四类基本数据结构的名称与含义。

3.算法的定义与特性。

4.算法的时间复杂度.

5.数据类型的概念.

6.线性结构与非线性结构的差别.

7.面向对象程序设计语言的特点。

8.在面向对象程序设计中，类的作用是什么？

9.参数传递的主要方式及特点。

10.抽象数据类型的概念。

二、判断题

1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2.算法就是程序。

3.在高级语言(如C、或PASCAL)中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度

for(i=1;i〈=n;i++)

for(j=1;j〈=i;j++)

for(k=1;k<=j;k++)

x=x+1;

[提示]:

i=1时：1=(1+1)X1/2=(1+12)/2

i=2时：1+2=(1+2)X2/2=(2+2?)/2

i=3时：1+2+3=(1+3)X3/2=(3+32)/2

•••

i=n时：1+2+3+......+n=(1+n)Xn/2=(n+n2)/2

f(n)=[(1+2+3+.....+n)+(1?+2?+3?+..........+n?)]/2

=[(1+n)n/2+n(n+1)(2n+1)/6]/2

=n(n+1)(n+2)/6

=n3/6+n2/2+n/3

区分语句频度和算法复杂度：

0(f(n))=0(n3)

四、试编写算法求一元多项式Pn(x)=ao+aix+a2x2+a3x4…anX，的值Pn(x0),并确定算法中的每一语句的执

行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求取函数。注意：本题

中的输入aMi=0,1,…，n),x和n,输出为*(x0).通常算法的输入和揄出可采用下列两种方式之一：

(1)通过参数表中的参数显式传递；

(2)通过全局变量隐式传递。

试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。

[提示]:floatPolyValue(floata[],floatx,intn){....}

核心语句：

P=1;(x的零次幕)

s=0;

i从0至"n循环

s=s+a[i-I*p：

p=p*x;

或：

p=x;(x的一次赛)

s=a[0]:

i从1至"n循环

s=s+a[i]*p;

p=p*x;

实习题

设计实现抽象数据类型“有理教”。基本操作包括有理教的加法、减法、乘法、除法，以及求有理教的

分子、分母。

第一章答案

1.3计算下列程序中XK+1的语句频度

for（i=1;i〈二n;i++）

for（j=1；j<=i；j++）

for（k=1；k<=j；k++）

x=x+1;

【解答】x=x+1的语句频唐为:

T(n)=1+(1+2)+(1+2+3)+……+(1+2+……+n)=n(n+1)(n+2)/6

1o4试编写算法，求pn(x)=ao+aix+a2x?++anX”的值p。(xo),并确定算法中每一语句的执行次数和整个算

法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求寐函数。注意：本题中的输入为

a.(i=0,1,-n).x和n,输出为匕(x。)。算法的输入和输出采用下列方法(1)通过参数表中的参数显式传

递(2)通过全局变量隐式传递.讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。

【解答】

(1)通过参数表中的参数显式传递

优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。

缺点：形参须与实参对应，且返回值数量有限。

(2)通过全局变量隙式传递

优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗

缺点：函数通用性降低，移植性差

算法如下：通过全局变量隐式传递参数

PolyValueO

{inti,n;

floatx,a[],p;

printf("\nn二");

scanf("％f"，&n);

printf(“\nx二”);

scanf("％f”，&x);

for(i=0;i(n;i++)

scanf(4<%f”，&a[i])：/*执行次数:n次*/

p-a[0]；

for(i=1;i<=n;i++)

{p=p+a[i]*x;/*执行次数：n次*/

x=x*x;}

printf(u%f",p);

)

笄法的时间复杂度：T(n)=0(n)

通过参数表中的参数显式传递

floatPolyValue(floata[],fIoatx,intn)

{

floatp,s;

inti;

P=x;

(8)whiIe(P-)next!=Q)P=P—〉next;

(9)whiIe(P->next!二NULL)P=P->next:

(10)P二Q;

(11)P二L;

(12)L=S;

(13)L=P;

2.4已知线性表L递增有序。试写一算法，将X插入到L的适当位置上，以保持线性表L的有序性。

［提示］:voidinsert(SeqList*L;EIemTypex)

<方法1〉

(1)找出应插入位置i,(2)移位，(3)……

〈方法2〉参P。229

2.5写一算法，从顺序表中删除自第i个元素开始的k个元素。

［提示］:注意检查i和k的合法性。(集体搬迁，“新房”、“旧房”)

(方法1>以待移动元素下标m(“旧房号”)为中心，

计算应移入位置(“新房号”)：

for(m=i-1+k;m〈二L-〉Iast;m++)

L—>eIem［m—k］=L->elem［m］;

<方法2>同时以待移动元素下标m和应移入位置j为中心：

<方法3〉以应移入位置j为中心，计算待移动元素下标：

2.6已知线性表中的元素(整数)以值递增有序排列，并以单链表作存储结构.试写一高效算法，删除表中所

有大于mink且小于maxk的元素(若裴中存在这样的元素)，分析你的算法的时间复杂度(注意：mink和maxk

是给定的两个参变量，它们的值为任意的整数).

［提示］:注意检查mink和maxk的合法性：mink〈maxk

不要一个一个的删除(多次修改next域).

(1)找到第一个应删结点的前驱pre

pre=L;p=L—〉next;

while(p!=NULL&&p->data<=mink)

{pre=p;p=p—>next;}

⑵找到最后一个应删结点的后继s,边找边释放应删结点

s二p;

while(s!=NULL&&s—>data<maxk)

{t=s;s=s—>next;free(t);}

(3)pre—)next=s;

2.7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表⑶，a2...,an)

J更直■为(an,a(i—i,oootai).

(1)以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。

(2)以单链表作存储结构。

［方法1］:在原头结点后重新头插一遍

［方法2］:可设三个同步移动的指针p,q,r,将q的后继r改为p

2O8假设两个按元素值递增有序排列的线性表A和B,均以单链表作为存储结构，请编写算法，将A表和B

表归并成一个按元素值递减有序的排列的线性表C,并要求利用原表(即A表和B表的)结点空间存放表C.

［提示］:参P.28W2-1

<方法1〉

voidmerge(LinkListA;LinkListB;LinkList*C)

{••••••

pa=A—)next;pb=B-)next;

*C=A;(*C)—〉next=NULL;

whiIe(pa!二NULL&&pb!二NULL)

{

if(pa-〉data<=pb-〉data)

(

smaIler=pa;pa=pa—>next;

smaIler—>next=(*C)—〉next;/*头插法*/

(*C)—)next=smaIler;

)

else

(

smaIler=pb;pb=pb-)next；

smaIler—>next=(*C)—>next;

(*C)—>next=smaIler;

)

)

whiIc(pa!:NULL)

(

smaIler=pa;pa=pa->next;

smaIler—>next=(*C)—>next;

(*C)—>next=smaIler;

1

whiIe(pb!=NULL)

smaIler=pb;pb=pb->next;

smaIler—>next=(*C)—>next;

(*C)—〉next=smaIler;

)

(方法2>

LinkListmerge(LinkListA;LinkListB)

LinkListC;

pa二A-〉next;pb=B->next;

C=A;C->next=NULL;

returnC;

2.9假设有一个循环链表的长度大于1,且表中既无头结点也无头指针.已知s为指向链表某个结点的指针，

试编写算法在链表中删除指针s所指结点的前趋结点.

［提示］:设指针P指向S结点的前趋的前趋，则P与S有何关系？

2.10已知有单链表表示的线性表中含有三类字符的数据元素(如字母字符、数字字符和其它字符)，试编写

算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这

三个表的结点空间，头结点可另辟空间.

2。11设线性表A二(aba2,…，a。，B=(b,,必…，b.),试写一个按下列规则合并A、B为戡性表C的算法,

使得：

C二(ai,bi,…，amibm,bz,…，bn)当mWn时；

或者C=(ai,bi,…，an,bn,an*i,…，aj当m>n时。

线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的

长度值m和n均未显式存储.

［提示］:voidmerge(LinkListA；LinkListB;LinkList*C)

或：LinkListmerge(LinkListA；LinkListB)

2O12将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，

并要求利用原链表中的结点空间来构成这两个链表。

［提示］:注明用头指针还是尾指针。

2.13建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制

位。并在此链表上实现对二进制数加1的运算。

［提示］:可将低位放在前面。

2O14设多项式P(x)采用课本中所述链接方法存储.写一算法，对给定的x值，求P(x)的值。

［提示］:floatPolyValue(PolyIistp;floatx){....}

实习题

1.将若干城市的信息存入一个带头结点的单链表，结点中的城市信息包括城市名、城市的位置坐标.要求：

(1)给定一个城市名，返回其位置坐标；

(2)给定一个位置坐标P和一个距离D,返回所有与P的距离小于等于D的城市。

2.约瑟夫环问题。

约宓夫问题的--种描述是：编号为1,2,…，n的n个人按顺时针方向围坐一图，每人持有一个密码(正

整数)。一开始任选一个整数作为报数上限值叫从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，

直至所有的人全部出列为止。试设计一个程序，求出出列顺序。

利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。

例如m的初值为20；H7,7个人的密码依次是：3,1,7,2,4,8,4,出列的顺序为6,1,4,7,2,3,

5O

第二章答案

实习题二：约瑟夫环问题

约瑟夫问题的一种描述为：编号1,2,…，n的n个人按顺酎针方向围坐一圈，每个人持有一个密码(正整

数).一开始任选一个报数上限值叫从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人

出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的

人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺

序打印出各人的编号。

例如,m的初值为20；n=7,7个人的密码依次是：3,1,7,2,4,8,4,出列顺序为6,1,4,7,2,3,5。

【解答】算法如下：

typedefstructNode

(

intpassword;

intnum;

structNode*next;

}Node,*LinkIist;

voidJosephus()

LinklistL;

Node*p,*r,*q;

intm,n,C,j;

L=(Node*)maIIoc(sizeof(Node));/*初始化单向循环链表*/

if(L二二NULL){printf(”\n链表申请不到空间！")；return：}

L->next=NULL;

r=L;

printf(”请输入数据n的值(n>0):");

scanf("%dv,&n);

for(j=1;j<=n;j++)/*建立链表

*/

(

p=(Node*)maIIoc(sizeof(Node));

if(p!=NULL)

1

printf("请输入第%d个人的密码：”，j);

scanf("%d",&C):

p->password=C;

p->num=j;

r-〉next=p;

r=P；

)

)

r-)next=L->next;

printf("请输入第一个报数上限值m(m>0):;

scanf("%d",&m);

printf("*****************************************\n")；

printf(”出列的顺序为：\n”);

q二L;

p=L->next;

whiIc(n!=1)/*计算出列的顺序*/

(

j=1；

while(j〈m)/*计算当前出列的人选p*/

q=P；/*q为当前结点p的前驱结点大/

p=p-)next;

j++；

)

printf(n%d->”,p—>num);

m=p-〉password;/*获得新密码*/

n-

q->next=p->next;/*p出列*/

r=P；

p=p—〉next;

free(r);

)

printf("%d\n",p-〉num);

)

2.7试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表（a］，a2,…，aj逆

置为(an,an-i,•,,,ai)0

【解答】(1)用一维数组作为存储结构

voidinvert(SeqList*L,int*num)

{

intj;

ElemTypetmp;

for(j=0;j〈二/2;j++)

(

tmp=L[j];

L[j]=L[*num-j-1]；

L[*num—j-1]=tmp;}

)

1

(2)用单链表作为存储结构

voidinvert(LinkListL)

(

Node*p,*q,*r；

if(L->next==NULL)return;/*链表为空*/

p=L->next;

q=p-)next;

p—>next=NULL;/*摘下第一个结点，生成初始逆置表*/

while(q!=NULL)/*从第二个结点起依次头插入当前逆置表*/

r=q——>next;

q->next=L—〉next;

L->next=q;

q二r；

)

)

2O11将线性表A=(a1,a2,...am),B=(b1,b2,...bn)合并成线性表C,C=(a1,b1,...am,bm,

bm+1,....bn)当m〈二n时，或C=(a1,b1,...an,bn,an+1,...am)当m)n时，线性表A、B、C

以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式

存储。

【解答】算法如下：

LinkListmerge(LinkListA,LinkListB,LinkListC)

(

Node*pa,*qa,*pb,*qb,*p;

pa=A-〉next;/*pa表示A的当前结点*/

pb=B-)next;

p=A;/*利用p来指向新连接的表的表尾，初始值指向表A的头结点*/

whiIe(pa!二NULL&&pb!二NULL)/*利用尾指法建立连接之后的链表*/

(

qa=pa-〉next;

qb=qb-)next;

p—>next=pa;/*交替选择表A和表B中的结点连接到新链表中；*/

p二pa：

p->next=pb;

P二pb;

pa=qa;

pb=qb：

1

if(pa!=NULL)p—〉next=pa;/*A的长度大于B的长度大/

if(pb!=NULL)p—>next=pb；/*B的长度大于A的长度*/

C=A;

return(C);

)

第3章限定性线性表-栈和队列

习题

1.按图3.1(b)所示铁道(两侧铁道均为单向行驶道)进行车屏I调度，回答：

⑴如进站的车厢序列为123,则可能得到的出站车厢1序列是什么？123、213、132、231、321(312)

(2)如进站的车厢序列为123456,能否得到435612和135426的出站序列，并说明原因。(即写出以“S”

表示进栈、以“X”表示出栈的栈操作序列)。

SXSSXSSXXXSX或S1X1S2S3X3S4S5X5X4X2S6X6

2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4步操作：

(1)输出队首元素；

(2)把队首元素值插入到队尾；

(3)删除队首元素；

(4)再次删除队首元素。

直到队列成为空队列为止，则是否可能得到输出序列：

(1)A、C、E、C、C(2)A、C、E

(3)A、C、E、C、C、C(4)A、C、E、C

［提示］:

A、B、C、D、E(输出队首元素A)

A、B、C、D、E、A(把队首元素A插入到队尾)

B、C、D、E、A(删除队首元素A)

C、D、E、A(再次删除队首元素B)

C、D、E、A(输出队首元素C)

C、D、E、A、C(把队首元素C插入到队尾)

D、E、A、C(删除队首元素C)

E、A、C(再次删除队首元素D)

3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？

4.按照四则运算加、减、乘、除和寐运算(T)优先关系的惯例，画出对下列算术表达式求值时操作数栈和

运算符栈的变化过程：

A—B*C/D+ETF

5.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如，序列1&序列2'模式的

字符序列。其中序列1和序列2中都不含字符,且序列2是序列1的逆序列。例如，4a+b&b+a,

是属该模式的字符序列，而'1+3&3—1'则不是。

［提示］:

(1)边读边入栈，直到&

(2)边读边出栈边比较，直到……

6.假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式(中缀)且书写

正确的表达式转换为逆波兰式(后缀)。

［提示］:

例：

中缀表达式：a+b后缀表达式：ab+

中缀表达式：a+bXc后缀表达式：abcX+

中缀表达式:a+bXc-d后缀表达式：abcX+d—

中缀表达式：a+bXc—d/e后缀表达式：abcX+de/-

中缀表达式：a+bX(c—d)-e/f后缀表达式：abed—X+ef/-

•后缀表达式的计算过程：(简便)

顺序扫描表达式，

(1)如果是操作数，直接入栈；

(2)如果是操作符op,则连续退栈两次，得操作数X,Y,计算XopY,并将结果入栈。

•如何将中缀表达式转换为后缀表达式？

顺序扫描中缀表达式，

(1)如果是操作数，直接输出；

(2)如果是操作符op2,则与栈顶操作符opi比较：

如果OP2>OPl,则op2入栈；

如果0P2=opi,则脱括号;

如果op2Vop”则输出op〕;

7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写

相应的队列初始化、入队列和出队列的算法。

［提示］:参P。56Po70先画图。

typedefLinkListCLQueue;

intInitQueue(CLQueue*Q)

intEntcrQucuc(CLQucucQ,QucucEIcmcntTypcx)

intDeIeteQueue(CLQueueQ,QueueEIementType*x)

8.要求循环队列不损失一个空间全部都能得到利用，设置一个标志域tag,以tag为。或1来区分头尾指

针和同时的队列状态的空与满，请编写与此结构相应的入队与出队算法.

［提示］:

初始状态：front=0,rear==0,tag==0

队空条件：front==rear,tag-0

队满条件：front=rear,tag==1

其它状态：front!=rear,tag二二0(或1、2)

入队操作：

•••

…(入队)

if(front二二rear)tag=1;(或直接tag二1)

出队操作：

•••

…(出队)

tag=0;

[问题]:如何明确区分队空、队满、非空非满三种情况？

9.简述以下算法的功能(其中栈和队列的元素类型均为int):

(1)voidproc_1(StackS)

{i

inti,n,A[255];

n=0：

while(!EmptyStack(S))

(

n++;

Pop(&S,&A[n]);

)

for(i=1;i〈二n;i++)

Push(&S,A[i]);

)

将栈S逆序。

(2)voidproc_2(StackS,inte)

{

StackT；intd;

InitStack(&T);

whiIe(!EmptyStack(S))

(

Pop(&S,&d);

if(d!二e)Push(&T,d);

)

while(!EmptyStack(T))

Pop(&T,&d)；

Push(&S,d);

}

)

删除栈S中所有等于e的元素。

(3)voidproc_3(Queue*Q)

(

StackS;intd;

InitStack(&S);

whiIe(!EmptyQueue(*Q))

(

DeIeteQueue(Q,&d);

Push(&S,d);

)

while(!EmptyStack(S))

(

Pop(&S,&d);

EnterQueue(Q,d)

)

)

将队列Q逆序。

实习题

1.回文判断。称正读与反读都相同的字符序列为“回文”序列。

试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如'序列1&序列才模式的字

符序列。其中序列1和序列2中都不含字符且序列2是序列1的逆序列。例如，匕+b&b+a'是属

该模式的字符序列，而'1+3&3——则不是。

2.停车场管理。

设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场内，汽车按到达的

先后次序，由北向南依次排列（假设大门在最南端）。若车场内已停满n辆车，则后来的汽车需在门外的便

道上等候，当有车开走时，便道上的第一辆车即可开入.当停车场内某辆车要离开时，在它之后进入的车辆必

须先退出车场为它让路，待该辆车开出大门后，其它车辆再按原次序返回车场。每辆车离开停车场时，应按

其停留时间的长短交费（在便道上停留的时间不收费）.

试编写程序，模拟上述管理过程。要求以顺序栈模拟停车场，以链队列模拟便道。从终端读入汽车到达

或离去的数据，每组数据包括三项：①是“到达”还是“离去”；②汽车牌照号码；③“到达”或“离去”6勺

时刻。与每组输入信息相应的输出信息为：如果是到达的车辆，则输出其在停车场中或便道上的位置；如果

是离去的车辆，则输出其在停车场中停留的时间和应交的费用。(提示：需另设一个栈，临时停放为让路而从

车场退出的车。)

车库

暂时退车道分'--N便it

3.商品货架管理。

商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近.上货时，需要倒货架，

以保证生产日期较近的商品在较下的位置。用队列和栈作为周转，实现上述管理过程。

第三章答案

301按3。1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度，回答：

(1)如进站的车厢序列为123,则可能得到的出站车厢序列是什么?

⑵如进站的车厢序列为123456,能否得到435612和135426的出站序列,并说明原因(即写出以“S”表示

进栈、“X”表示出栈的栈序列操作)。

【解答】

(1)可能得到的出站车厢I序列是：123、132、213、231、3210

(2)不能得到435612的出站序列。

因为有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6),此时按照“后进先出”的原则,出栈的

顺序必须为X(2)X(1)o

能得到135426的出站序列。因为有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(Do

3.3给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？

【解答】

(1)顺序栈(top用来存放栈顶元素的下标)

判断栈S空：如果s—>top=7表示栈空.

判断栈S满:如果S—>top==Stack_Size-1表示栈满.

(2)链栈(top为栈顶指针，指向当前栈顶元素前面的头结点)

判断栈空：如果top—>next二二NULL表示栈空。

判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。

3.4照四则运算加、减、乘、除和幕运算的优先惯例，画出对下列表达式求值时操作数栈和运算符栈的变

化过程：A—B*C/D+ETF

【解答】

305写一个算法，判断依次读入的一个以@为结束符的字母序列，是否形如，序列1&序列2'的字符序列.序

列1和序列2中都不含&,且序列2是序列1的逆序列。例如，'a+b&b+a'是属于该模式的字符序列，

而'1+3&3-V则不是。

【解答】算法如下：

intIsHuiWen()

(

Stack*S：

Charch,temp;

InitStack(&S);

Printf("\n请输入字符序列：”);

Ch=getchar();

While(ch!=&)/*序列1入栈*/'

Push(&S,ch);

ch=getchar();

)

do/*判断序列2是否是序列1的逆序列*/

ch=getchar();

Pop(&S,&tcmp)；

if(ch!=temp)/*序列2不是序列1的逆序列大/

(

return(FALSE);printf(u\nN0");

)

}while(ch!二@&&!IsEmpty(&S))

if(ch==@&&IsEmpty(&S))

{return(TRUE);printf("\nYES");}/中序列2是序列1的逆序列大/

eIse

{return(FALSE)；printf(u\nNO");}

}/*IsHuiWen()*/

308要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以tag为0或1来区分头尾指针

相同时的队列状态的空与满，请编写与此相应的入队与出队算法.

【解答】入队算法：

intEnterQueue(SeqQueue*Q,QueueEIementTypex)

{/大将元素x入队*/

if(Q->front==Q-)front&&tag=二1)/*队满*/

return(FALSE);

if(Q-)front~Q->front&&tag=二0)/大x入队前队空，x入队后重新设置标志*/

tag=1;

0—>elememt[Q-)rear]=x;

Q—>rear=(Q—>rear+1)%MAXSIZE;/*设置队尾指针*/

Return(TRUE);

)

出队算法：

intDeIeteQueue(SeqQueue*Q,QueueEIementType*x)

{/大删除队头元素，用x返回其值*/

if(Q->front-Q—>rear&&tag=二0)/*队空*/

return(FALSE);

*x=Q")eIement[Q—〉front];

Q—>front=(Q->front+1)%MAXSIZE;/*重新设置队头指针*/

if(Q一)front==Q->rear)tag=0;/*队头元素出队后队列为空，重新设置标志域*/

Return(TUUE);

)

编写求解Hanoi问题的算法，并给由三个盘子搬动时的递归调用过程。

【解答】算法：

voidhanoi(intn,charx,chary,charz)

{/*将塔座X上按直径由小到大且至上而下编号为1到n的n个圆盘按规则搬到塔座Z上，Y可用做辅

助塔座*/

if(n==1)

move(x,1,z);

se

{Hanoi(n-1,x,z,y);

move(x,n,z);

Hanoi(n-1,y,x,z);

)

}

Hanoi(3tA,B,C)的递归调用过程:

Hanoi(2,A,C,B):

Hanoi(1,A,B,C)move(A-)C)1号搬到C

Move(A-〉B)2号搬到B

Hanoi(1,C,A,B)move(C—>B)1号搬到B

Move(A—>C)3号搬到C

Hanoi(2,B,A,C)

Hanoi(1,B,C,A)move(B—〉A)1号搬到A

Move(B->C)2号搬到C

HanoiC)move(A->C)1号搬到C

第4章串

习题

1.设s='lAMASTUDENT*,t='G00D',q='WORKER'.给出下列操作的结果：

StrLength(s);SubString(sub1,s,1,7)；SubString(sub2,s,7,1)；

StrIndex(s,'A',4);StrRepIace(s,'STUDENT',q);

StrCat(StrCat(sub1,t),StrCat(sub2,q));

［参考答案］

StrLength(s)=14;sub1='IAMA_';sub2=';StrIndex(s,'A',4)=6;

StrRepIace(s,'STUDENT',q)='IAMAWORKER';

StrCat(StrCat(sub1,t),StrCat(sub2,q))='IAMAGOODWORKER';

2o编写算法，实现串的基本操作StrReplace(S,T,V)0

30假设以块链结构表示串，块的大小为1,且附设头结点。

试编写算法，实现串的下列基本操作：

StrAsign(S,chars);StrCopy(S,T);StrCompare(S,T);StrLength(S);StrCat(S,T);

SubString(Sub,S,pos,len)o

［说明］:用单链表实现。

4O叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。

5.已知:S=”(xyz)*"，T=”(x+z)*y”.试利用联接、求子串和置换等操作,将S转换为T。

6OS和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置.

70S是用结点大小为4的单链表存序的串，分别编写算法在第k个字符后插入串T,及从第k个字符删除len

个字符。

以下算法用定长顺序串：

8.写下列算法：

(1)将顺序串r中所有值为ch1的字符换成ch2的字符。

(2)将顺序串r中所有字符按照相反的次序仍存放在r中。

(3)从顺序串r中删除其值等于ch的所有字符.

(4)从顺序串门中第index个字符起求出首次与串r2相同的子串的起始位置。

(5)从顺序串r中删除所有与串r1相同的子串.

9.写一个函数将顺序串s1中的第i个字符到第J个字符之间的字符用s2串替换。

［提示］:(1)用静态顺序串(2)先移位，后复制

10.写算法，实现顺序串的基本操作StrCompare(s,t)o

11o写算法，实现顺序串的基本操作StrReplace(&s,t,v)。

［提示］:

(1)被替换子串定位(相当于第9题中i)

(2)被替换子串后面的字符左移或右移(为替换子串准备房间)

(3)替换子串入住(复制)

(4)重复上述，直到...

第四章答案

r

401设s='IAMASTUDENT,t='GOOD',q='WORKER'°给出下列操作的结果:

【解答】StrLength(s)=14;

SubString(sub1,s,1,7)sub1='IAMA

SubString(sub2,s,7,1)sub2=>';

StrIndex(s,4,'A')=6;

StrReplace(s,'STUDENT,,q);s='IAMAWORKER';

StrCat(StrCat(sub1,t),StrCat(sub2,q))sub1=,IAMAGOODWORKER'。

4.2编写算法，实现串的基本操作StrReplace(S,T,V).

【解答】算法如下：

intstrRepIace(SStringS,SStringT,SStringV)

{/大用串V替换S中的所有子串T*/

intpos,i;

pos=strIndex(S,1,T);/*求S中子串T第一次出现的位置*/

if(pos==0)returnCO);

while(pos!=0)/*用串V替换S中的所有子串T*/

(

switch(Tolen-V。len)

(

case0:/*串T的长度等于串V的长度*/

for(i=0;i<=V>len;i++)/*用V替换T*/

S—〉ch[pos+i]=V。ch[i];

case>0:/*串T的长度大于串V的长度*/

for(i=pos+toien;i<S­)Ien;i---)/*将S中子串T后的所有字符

S-)ch[i—toIen+v.Ien]=S->ch[i];前移T。Ien-V«len个位置*/

for(i=0;i<=V.len；i++)/*用V替换T*/

S—>chFpos+i]=V.chFi]:

S->Ien=S-)Ien—T。Ien+VoIen;

case<0:/*串T的长度小于串V的长度*/

if(S—>len-T.Ien+Volen)<=MAXLEN/*插入后串长小于MAXLEN*/

{/*将S中子串T后的所有字符后移V。len—T。len个位置*/

for(i=S->Ien-T.len+V.len;i>=pos+T.len;i---)