数据结构课后习题答案（修订版）(3)

{

q->data=malloc（maxsize*sizeof（datatype））; q->front=q->rear= -1; q->flag= 0; }

（2） 入队列算法

insertseq（sequeue*q,int x） {

if（q->flag= =1）return NULL; else if（（q->rear+1）%maxsize = =q->front） {

q->rear=（q->rear+1）%maxsize; q->data[q->rear]=x; q->flag=1; return 1; } else {

q->rear=（q->rear+1）%maxsize; q->data[q->rear]=x; } }

（3） 出队列算法

datatype delqueue（sequeue*q） {

if（q->flag= =0）return NULL; else {

q->front=（q>front-1）%maxsize; if（q->front= =q->rear）{q->flag=0;} return（q->data[q->front]）; } }

12．参考答案,算法提示

int G（int m,int n） {

if（m= =0&&n>=0）return 0; else return G（m-1,2n）; }

栈变化示意图略。

13．算法提示： /*栈*/

datatype Pop（seqstack *s） {

datatype p;

p=s->data[s->top-2];

s->data[s->top-2]=s->data[s->top-1];

--s->top;/*栈顶指针指向栈顶元素的下一个位置*/ return p;/*用P返回其值*/ }

/*队列*/

datatype Pop（sequeue*q） {

datatype p;

p=q->data[q->front-2];

q->data[q->front-2]=q->data[q->front-1];

--q->front;/*队头指针指向队头元素的下一个位置*/ return p;/*用P返回其值*/ }

习题四答案

1．参考答案：递归是软件设计中一个重要的算法设计方法和技术，递归子程序是通过调用自身来完成与自身要求相同的子问题的求解，并利用系统内部功能自动实现调用过程中信息的保存与恢复。

2．算法提示：1*2+2*3+3*4+……+（n-1）*n

int Count（int n） {

if（n==2）return 2；

return（n*（n-1）+Count（n-1））； }

3．参考答案：功能为计算0+1+2+3+……+n;改为非递归算法如下：

int func （int n） {

int max=0; int i;

for（i=n;i>=0;i--） {

max+=i; }

return max; }

#define maxlen 200 struct st {

int no,ns; char x,y,z; }stack[maxlen];

4．参考算法：利用递归工作栈的工作原理，算法如下：

其中no存放一个标识，为0时表示直接移动一个圆盘，为1时表示需进一步分解；ns存放当前圆盘数；x,y和z表示三个塔座，由此得到如下函数：

void hanoi（n,a,b,c） int n;

{

int top=1,n1,a1,b1,c1;

stack[top].no=1;/*初值入栈*/ stack[top].ns=n; stack[top].x=a; stack[top].y=b; stack[top].z=c; while（top>0） {

if（stack[top].no==1） {

n1=stack[top].ns; a1=stack[top].x; b1=stack[top].y; c1=stack[top].z; stack[top].no=1; stack[top].ns=n1-1; stack[top].x=b1; stack[top].y=a1; stack[top].z=c1; top++;

stack[top].no=0; stack[top].ns=n1; stack[top].x=a1; stack[top].y=c1; top++;

stack[top].no=1; stack[top].ns=n1-1; stack[top].x=a1; stack[top].y=c1; stack[top].z=b1; }

while（top>0&&（stack[top].no= =0||stack[top].ns= =1）） {

if（top>0&&stack[top].no= =0）/*将第n个圆盘从x移到z退栈*/

{

printf（”\\t将第%d个盘子从%d移动到%c\\n”,stack[top].ns,

stack[top].x,stack[top].y）; top--; }

if（top>0&&stack[top].ns= =1）/*退栈*/ {

printf（”\\t将第%d个盘子从%c移动到%c\\n”,stack[top].ns,

}

}

stack[top].x,stack[top].z）； top--; } }

5．参考算法：

（1）datatype akm（datatype m,datatype n）

{

if（m= =0）return n+1;

else if（m!=0&&n= =0）return akm（m-1,1）; else return akm（m-1,akm（m,n-1））; }

（2）同样可以利用递归工作栈的工作原理将上面的递归算法进行改写，具体算法略。 6．参考答案：

（1）函数功能：打印“a/b”的结果。 （2）int p（int a,int b） { if（a

习题五答案

1． 判断题

（1）╳ （2）╳ （3）╳ （4）√ （5）√

2．选择题

（1）D （2）D （3）D （4）C （5）B （6）B

3．(1)空白串与空串有何区别？字符串中的空白符号有何意义？

参考答案：空白串（空格串）是由一个或多个空格组成的串。它不等于空串，它的长度是串中包含的空格数。空串是由零个字符组成的串，空串中不包含任何字符，它的长度是0。字符串中的空白符号表示这个位置是一个空格字符。

3．(2)假定串采用块链接表示，试写出删除一个子串的算法。

参考答案：由于采用块链接存储结构的串对于字符或者子串的插入删除运算存在着极大的不方便性，所以这里我们将问题简化：即删除的子串恰好是该串中的一个接点（该结点中存放着主串的一个子串），这样就把问题简化为删除链表中一个结点的问题，大大简化了操作。

/*定义一个块结点*/

typedef struct StrNode

{

char ch[maxOfNode]; /* maxOfNode 为一个接点存放子串的最大长度*/ struct StrNode *next; /*next指向下一个接点*/

}StringNode;

/*在一个头结点为head的块链接存储结构的串string中查找子串str的算法如下*/

StringNode * Delete(StringNode *head, char *str) {

StringNode *q,*p=head;

q=p;p=p->next; /*从第一个结点开始查找*/ while(strcmp(str,p->ch)!=0) /*开始查找合适的结点*/ {

q=p;

p=p->next; }

q->next=p->next; free(p);

return head; }

3．(3)比较串的三种存储方式的优点和缺点。

参考答案：（1）顺序存储结构——优点：存储密度高（不需要存储指针变量），可以随机存取串中的字符；缺点：存取字符时要移动大量的元素，由于事先不知道存储字符的最大数目，所以应该分配尽可能大的静态存储空间，从而造成了空间浪费！ （2）单链表式存储结构——优点：插入删除一个结点不需要移动大量的元素，只需要修改有限的指针变量，可以随机分配和释放结点空间，避免了空间浪费；缺点：结点的存储密度低（因为每个结点要存储指向下一个结点的指针变量），查找结点要从头开始顺序查找，不具备随即存取的机制！为此人们设计了一种叫做块链结点的存储结构，虽然在结点的存储密度上较以前有了改进，但是却给插入删除字符元素或者子串带来了意想不到的麻烦！

（3）堆结构的存储方式——优点：动态分配存储空间，避免了空间浪费。 3.(4)已知：s=?xyz*?，t=?(x+y)*z?。试利用联接、求子串和置换等基本运算，将s转换为t。

参考答案：

t=Concation(“(”,SubString(sub1,s,1,1),“+”，SubString(sub2,s,2,1),“)”,swap(SubString(sub3 …… 此处隐藏：2008字，全部文档内容请下载后查看。喜欢就下载吧 ……