严蔚敏《数据结构C语言版》习题集完整解

1星需积分: 8 91 浏览量更新于2024-07-23 收藏 258KB PDF 举报

"严蔚敏《数据结构(c语言版)习题集》全答案，包含所有算法设计题目的解决方案，采用类C语言描述，部分题目提供思路分析和简要说明，部分未解题目进行讨论。" 这篇内容是针对严蔚敏教授编写的《数据结构(c语言版)习题集》的完整答案集，由kaoyan.com计算机版版主及多位网友共同完成和修订。解答中所有的算法用类C语言编写，旨在便于理解和交流，但并不保证程序能直接上机运行。解答通常只提供源代码和必要的注释，对于复杂或独特的题目会有简单的分析说明。作者鼓励读者在尝试解决或深入思考后再参考答案，以提升学习效果，并欢迎读者指出错误和不足，共同完善解答。在提供的部分习题答案中，例如1.16题，是一个简单的冒泡排序实现，用于按降序输出三个整数。1.17题则涉及斐波那契序列的计算，通过保存已计算的结果优化了时间复杂度，使其达到O(m^2)，这是一种动态规划的应用。从这些内容中，我们可以提炼出以下几个重要的数据结构和算法知识点： 1. **冒泡排序**：是一种简单的排序算法，通过重复遍历要排序的数列，比较相邻元素并交换位置来逐步让元素趋于有序。在这个例子中，它被用于将三个数按降序排列。 2. **斐波那契序列**：一个数列，其中每个数字是前两个数字的和。第0项是0，第1项是1。斐波那契序列在许多数学和计算机科学问题中都有应用，如动态规划问题。 3. **动态规划**：是一种解决问题的方法，通过将大问题分解成子问题，并存储子问题的解以避免重复计算，从而提高效率。在1.17题中，利用动态规划减少了计算斐波那契序列的复杂性。 4. **算法设计原则**：面向交流和阅读，意味着代码应该易于理解，即使它可能不适用于实际的执行环境。 5. **错误检测与改进**：学习过程中的一个重要环节是自我检查和批判性思维，这有助于发现和修复错误，提升算法的效率和质量。 6. **时间复杂度分析**：对算法性能的评估，1.17题中的时间复杂度分析表明，通过保存已计算的序列元素，可以显著减少计算时间。这些知识点是数据结构和算法学习的基础，对于计算机科学专业的学生或程序员来说，理解和掌握这些概念对于解决问题至关重要。同时，通过解决和讨论习题，可以加深对这些概念的理解，提高编程能力。

}

}//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页未读，继续阅读

乔克sw

粉丝: 44
资源: 5

严蔚敏《数据结构C语言版》习题集完整解

数据结构(c语言版)习题集》答案

计算机网络 谢仁希 第七版 2017

数据结构(C语言版)第2版习题答案—严蔚敏

严蔚敏数据结构c语言版习题集全答案.doc

严蔚敏数据结构c语言版习题集答案

严蔚敏数据结构C语言版 习题集答案WORD版

严蔚敏数据结构C语言版习题集答案解析

严蔚敏数据结构c语言版习题集答案串.pdf

严蔚敏《数据结构C语言版习题集》答案

严蔚敏《数据结构c语言版习题集》答案

最新资源

计算机网络谢仁希第七版 2017

严蔚敏数据结构C语言版习题集答案WORD版