数据结构 用C语言描述 课后答案(6)

}

9、母牛问题：

有一头母牛从第4年起开始每年生一头小母牛，每头小母牛也从第4年起每年生一头小母牛，依此类推，问N年后共有多少头母牛？ 【解答】

年份 1 2 3 4 5 6 7 8 9 10 头数 1 1 1 2 3 4 6 9 13 19 归纳出数学模型

1 (N<=3)

F(N)= F(N-1)+F(N-3) (N>3) 其中F(N-1)为上一年母牛头数F(N-3)第N年能生养出小母牛的母牛头数. INT F(INT N)

{ IF (N<=3) RETURN(1); ELSE

RETURN(F(N-1)+F(N-3)); }

课后练习

一、按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： ⑴ 如进站的车厢序列为123，则可能得到的出站车厢序列是什么？

⑵ 如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。 【解答】

（1）可能得到的出站车厢序列是：123、132、213、231、321。 (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)。 能得到135426的出站序列。

因为有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。

二、设队列中有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＊Ｃ／Ｄ＋Ｅ↑Ｆ

【解答】

五、假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写

形式且书写正确的表达式转换为逆波兰式。

六、要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或

1区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。 【解答】入队算法：

int EnterQueue(SeqQueue *Q, QueueElementType x) { /*将元素x入队*/

if(Q->front==Q->front && tag==1) /*队满*/ return(FALSE);

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

Q->elememt[Q->rear]=x;

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

}

出队算法：

int DeleteQueue( SeqQueue *Q , QueueElementType *x) { /*删除队头元素，用x返回其值*/

if(Q->front==Q->rear && tag==0) /*队空*/ return(FALSE);

*x=Q->element[Q->front];

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

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

第四章 串 数组和广义表

课堂习题

1、编写算法，求静态串中所含不同字符的种类数和每种字符的个数。 【解答】

#DEFINE MAXSTRLEN 255

TYPEDEF UNSIGNED CHAR SSTRING[MAXSTRLEN+1]; TYPEDEF STRUCT LNODE {CHAR DATA; INT SUM;

STRUCT LNODE *NEXT; }LNODE,*LINKLIST;

STATUS TOTAL(SSTRING S) {

LINKLIST L;

L=(LINKLIST)MALLOC(SIZEOF(LNODE)); L->NEXT=NULL; FOR(I=1;I<=S[0];I++) {P=L->NEXT;

WHILE(P&&P->DATA!=S[I]) P=P->NEXT; IF(P) P->SUM++ ELSE

{Q=(LINKLIST )MALLOC(SIZEOF(LNODE)); Q->DATA=S[I]; Q->SUM=1;

Q->NEXT=L->NEXT; L->NEXT=Q; } } }

2、编写算法：在静态串S中删除所有和串T相同的子串。 【解答】

STATUS DELETE(SSTRING &S,SSTRING T) { I=1;

WHILE(I<=S[0]-T[0]+1)

{SUBSTIRNG(SUB,S,I,T[0]); IF EQUAL(SUB,T)

STRDELETE(S,I,T[O]);

ELSE I++; } }

3、假设以定长顺序表存储结构来表示串，试设计一算法，求串S中出现的第一个最长重复子串及其位置。 【解答】

INT MAXSUBSTR(SSTRING S,SSTRING &SUB) {LEN=S[0]-1; WHILE(LEN>0) {I=1;

WHILE(I<=S[0]-LEN)

{SUBSTRING(TEMP,S,I,LEN); IF INDEX(S,TEMP,I+1)

{STRCOPY(SUB,TMEP);RETURN(I);} ELSE I++; } LEN--; } }

4、已知静态串S和T，求所有包含在S中而不包含在T中的字符构成的新串R，以及新串R中每个字符在S中第一次出现的位置。 【解答】

#DEFINE MAXSTRLEN 255 TYPEDEF STRUCT

{CHAR CH[MAXSTRLEN]; INT POS[MAXXSTRLEN]; INT LEN;} STRING;

VOID CREATER(SSTRING S,SSTRING T,STRING &R) {K=1;

IF INDEX(T,S[1],1)==0 {R.CH[K]=S[1]; R.POS[K]=1; K++; } I=2;

WHILE(I<=S[0])

{J=1;

WHILE(J<=I-1)

{IF(S[J]==S[I]) BREAK ELSE J++;} IF J<=I-1 I++ ELSE {L=1;

WHILE(L<=T[0])

{IF S[I]==T[L] BREAK ELSE L++; }

IF L>T[0]

{R.CH[K]=S[I]; R.POS[K]=I; K++;} } I++; } }

5、假设稀疏矩阵A和B均以三元组表作为存储结构，试写出矩阵相加的算法（另设三元组表C存储结果矩阵）。 【解答】

#DEFINE MAXSIZE 12500 TYPEDEF STRUCT {INT I,J;

ELEMTYPE E;} TRIPLE; TYPEDEF STRUCT

{TRIPLE DATA[MAXSIZE+1]; INT MU,NU,TU; }TXMATRIX;

STATUS SMATRIX_ADD(TSMATRIX A,TSMATRIX B,TSMATRIX &C) {

IF (A.MU<>B.MU||A.NU<>B.NU) RETURN ERROR; C.MU=A.MU;C.NU=A.NU; PA=1;PB=1;PC=1;

WHILE(PA<=A.TU AND PB<=B.TU) {IF A.DATA[PA].I