严蔚敏《数据结构》习题详解与C语言代码

需积分: 8 100 浏览量更新于2024-07-30 收藏 258KB PDF 举报

《数据结构（严蔚敏版）》习题答案是一份针对严蔚敏所著的《数据结构（C语言版）》教材中所有算法设计题目的详细解答。这份文档由考研吧计算机版版主整理，并得到了网友siice、龙抬头、iamkent、zames、birdthinking等人的贡献与修订，以面向交流和阅读的方式呈现。解答内容主要采用类C语言描述，注重理解和分享，但并不保证所有程序可以直接上机运行。章节1.16的"print_descending"函数旨在按从大到小的顺序输出三个整数，通过冒泡排序算法实现。该函数首先接收输入的三个数，然后进行比较和交换操作，最终按照降序打印。 1.17的"fib"函数则涉及斐波那契数列的计算，它接受参数k（阶数）、m（要查询的项）和一个引用变量f（存储结果）。如果k小于2或m小于0，函数返回错误；当m小于k-1时，f设为0；当m等于k-1时，f设为1。若m大于等于k-1，通过两个嵌套循环，利用之前计算的结果逐步求出第m项的值。这种方法的时间复杂度优化到了O(m^2)，相较于传统的递归方法效率更高。值得注意的是，解答中并未提供所有题目的完整代码，而是重点在算法的设计思路和关键部分，对于较难或特殊题目仅提供简要分析。对于尚未解决的问题，如5.20和10.40，提示读者在深入思考后再参考答案。同时，作者强调了在阅读解答过程中应积极思考、发现并修正可能存在的错误，鼓励读者参与到问题的讨论中，共同提升对数据结构的理解。这份习题答案不仅适用于考研备考者，也适合任何学习者在掌握数据结构理论的同时，提高实际编程能力。通过阅读和实践这里的解题策略，读者可以深化对数据结构概念和技术的理解，为未来的学习和工作打下坚实的基础。

}

}//for

if(!StackEmpty(s)) return ERROR;

return OK;

}//AllBrackets_Test

3.20

typedef struct {

. int x;

int y;

} coordinate;

void Repaint_Color(int g[m][n],int i,int j,int color)// 把点 (i,j )

相邻区域的颜色置换为 color

{

old=g[i][j];

InitQueue(Q);

EnQueue(Q,{I,j});

while(!QueueEmpty(Q))

{

DeQueue(Q,a);

x=a.x;y=a.y;

if(x>1)

if(g[x-1][y]==old)

{

g[x-1][y]=color;

EnQueue(Q,{x-1,y}); // 修改左邻点的颜色

}

if(y>1)

if(g[x][y-1]==old)

{

g[x][y-1]=color;

EnQueue(Q,{x,y-1}); // 修改上邻点的颜色

}

if(x<m)

if(g[x+1][y]==old)

{

g[x+1][y]=color;

EnQueue(Q,{x+1,y}); // 修改右邻点的颜色

}

if(y<n)

if(g[x][y+1]==old)

{

g[x][y+1]=color;

EnQueue(Q,{x,y+1}); // 修改下邻点的颜色

}

}//while

}//Repaint_Color

分析 : 本算法采用了类似于图的广度优先遍历的思想 , 用两个队列保存相

邻同色点的横坐标和纵坐标 . 递归形式的算法该怎么写呢 ?

3.21

void NiBoLan(char *str,char *new)// 把中缀表达式 str 转换成逆波兰

式 new

{

p=str;q=new; // 为方便起见 , 设 str 的两端都加上了优先级最低的特殊

符号

InitStack(s); //s 为运算符栈

while(*p)

{

if(*p 是字母 )) *q++=*p; // 直接输出

else

{

c=gettop(s);

if(*p 优先级比 c 高 ) push(s,*p);

else

{

while(gettop(s) 优先级不比 *p 低 )

{

pop(s,c);*(q++)=c;

}//while

push(s,*p); // 运算符在栈内遵循越往栈顶优先级越高的原则

}//else

p++;

}//while

}//NiBoLan // 参见编译原理教材

3.22

int GetValue_NiBoLan(char *str)// 对逆波兰式求值

{

p=str;InitStack(s); //s 为操作数栈

while(*p)

{

if(*p 是数 ) push(s,*p);

else

{

pop(s,a);pop(s,b);

r=compute(b,*p,a); // 假设 compute 为执行双目运算的过程

push(s,r);

}//else

p++;

}//while

pop(s,r);return r;

}//GetValue_NiBoLan

3.23

Status NiBoLan_to_BoLan(char *str,stringtype &new)// 把逆波兰表

达式 str 转换为波兰式 new

{

p=str;Initstack(s); //s 的元素为 stringtype 类型

while(*p)

{

if(*p 为字母 ) push(s,*p);

else

{

if(StackEmpty(s)) return ERROR;

pop(s,a);

if(StackEmpty(s)) return ERROR;

pop(s,b);

c=link(link(*p,b),a);

push(s,c);

}//else

p++;

}//while

pop(s,new);

if(!StackEmpty(s)) return ERROR;

return OK;

}//NiBoLan_to_BoLan

分析 : 基本思想见书后注释 . 本题中暂不考虑串的具体操作的实现 , 而将其

看作一种抽象数据类型 stringtype, 对其可以进行连接操作 :c=link(a,b) .

3.24

Status g(int m,int n,int &s)// 求递归函数 g 的值 s

{

if(m==0&&n>=0) s=0;

else if(m>0&&n>=0) s=n+g(m-1,2*n);

else return ERROR;

return OK;

}//g

3.25

Status F_recursive(int n,int &s)// 递归算法

{

if(n<0) return ERROR;

if(n==0) s=n+1;

else

{

F_recurve(n/2,r);

s=n*r;

}

return OK;

}//F_recursive

Status F_nonrecursive(int n,int s)// 非递归算法

{

if(n<0) return ERROR;

if(n==0) s=n+1;

else

{

InitStack(s); //s 的元素类型为 struct {int a;int b;}

while(n!=0)

{

a=n;b=n/2;

push(s,{a,b});

n=b;

}//while

s=1;

while(!StackEmpty(s))

{

pop(s,t);

s*=t.a;

}//while

}

return OK;

}//F_nonrecursive

3.26

float Sqrt_recursive(float A,float p,float e)// 求平方根的递归算

法

{

if(abs(p^2-A)<=e) return p;

else return sqrt_recurve(A,(p+A/p)/2,e);

}//Sqrt_recurve

float Sqrt_nonrecursive(float A,float p,float e)// 求平方根的非

递归算法

{

while(abs(p^2-A)>=e)

p=(p+A/p)/2;

return p;

}//Sqrt_nonrecursive

3.27

这一题的所有算法以及栈的变化过程请参见《数据结构 (pascal 版 ) 》 , 作

者不再详细写出 .

3.28

void InitCiQueue(CiQueue &Q)// 初始化循环链表表示的队列 Q

{

Q=(CiLNode*)malloc(sizeof(CiLNode));

Q->next=Q;

}//InitCiQueue

void EnCiQueue(CiQueue &Q,int x)// 把元素 x 插入循环链表表示的队列

Q,Q 指向队尾元素 ,Q->next 指向头结点 ,Q->next->next 指向队头元素

{

p=(CiLNode*)malloc(sizeof(CiLNode));

p->data=x;

p->next=Q->next; // 直接把 p 加在 Q 的后面

Q->next=p;

Q=p; // 修改尾指针

}

Status DeCiQueue(CiQueue &Q,int x)// 从循环链表表示的队列 Q 头部删

除元素 x

{

if(Q==Q->next) return INFEASIBLE; // 队列已空

p=Q->next->next;

x=p->data;

Q->next->next=p->next;

free(p);

return OK;

}//DeCiQueue

3.29

Status EnCyQueue(CyQueue &Q,int x)// 带 tag 域的循环队列入队算法

{

if(Q.front==Q.rear&&Q.tag==1) //tag 域的值为 0 表示 " 空 ",1 表示 " 满

return OVERFLOW;

Q.base[Q.rear]=x;

Q.rear=(Q.rear+1)%MAXSIZE;

if(Q.front==Q.rear) Q.tag=1; // 队列满

}//EnCyQueue

Status DeCyQueue(CyQueue &Q,int &x)// 带 tag 域的循环队列出队算法

{

if(Q.front==Q.rear&&Q.tag==0) return INFEASIBLE;

Q.front=(Q.front+1)%MAXSIZE;

x=Q.base[Q.front];

if(Q.front==Q.rear) Q.tag=1; // 队列空

return OK;

}//DeCyQueue

分析 : 当循环队列容量较小而队列中每个元素占的空间较多时 , 此种表示

方法可以节约较多的存储空间 , 较有价值 .

3.30

Status EnCyQueue(CyQueue &Q,int x)// 带 length 域的循环队列入队算

法

{

if(Q.length==MAXSIZE) return OVERFLOW;

Q.rear=(Q.rear+1)%MAXSIZE;

Q.base[Q.rear]=x;

Q.length++;

return OK;

}//EnCyQueue

Status DeCyQueue(CyQueue &Q,int &x)// 带 length 域的循环队列出队算

法

{

if(Q.length==0) return INFEASIBLE;

head=(Q.rear-Q.length+1)%MAXSIZE; // 详见书后注释

x=Q.base[head];

Q.length--;

}//DeCyQueue

3.31

int Palindrome_Test()// 判别输入的字符串是否回文序列 , 是则返回 1,

否则返回 0

{

InitStack(S);InitQueue(Q);

while((c=getchar()!='@')

{

Push(S,c);EnQueue(Q,c); // 同时使用栈和队列两种结构

}

while(!StackEmpty(S))

{

Pop(S,a);DeQueue(Q,b));

if(a!=b) return ERROR;

}

return OK;

}//Palindrome_Test

3.32

剩余35页未读，继续阅读

春眠不觉晓小鸟

粉丝: 0
资源: 3

严蔚敏《数据结构》习题详解与C语言代码

数据结构严蔚敏版习题答案

数据结构（C版）-严蔚敏-课后习题答案.pdf

数据结构（C语言版）-严蔚敏-课后习题答案.pdf

数据结构严蔚敏课件习题答案及代码

数据结构严蔚敏版习题册编程题的完整答案

清华大学数据结构严蔚敏版习题集及其答案

数据结构严蔚敏教材习题集答案

数据结构 严蔚敏教材 习题集答案

数据结构严蔚敏版习题全集

数据结构 严蔚敏教材 习题集答案.

最新资源

数据结构严蔚敏教材习题集答案

数据结构严蔚敏教材习题集答案.