《数据结构C》习题集解与算法分析

需积分: 16 114 浏览量更新于2024-07-31 收藏 258KB PDF 举报

"这是一份关于数据结构习题集答案的文档，主要针对严蔚敏《数据结构(C语言版)习题集》中的算法设计题目，由kaoyan.com计算机版版主编写，并得到了多位网友的修订和建议。文档采用类C语言描述算法，但不保证程序可直接运行。解答中包含源代码、注释，部分难题会有分析说明，还有未解决的问题等待读者探讨。作者鼓励读者在独立思考后参考解答以提高学习效果，并欢迎发现和指出错误。文档的第一章涉及绪论，包含1.16和1.17两道习题的解答，分别是按降序输出三个数的函数和求斐波那契序列的函数。1.16题用冒泡排序实现，1.17题利用动态规划优化时间复杂度至O(m^2)。" 这篇文档是关于数据结构学习的辅助资料，特别关注C语言实现的数据结构算法。首先，文档的目的是提供严蔚敏《数据结构(C语言版)习题集》中算法设计题目的解答，由一位版主主笔，并得到多位网友的贡献和修正。这个答案集强调了面向理解和阅读的算法描述，而非直接可执行的程序代码，因此，它更像是一种学习工具，帮助读者理解算法的设计思路。文档中提到了两个具体的问题解答。第一个问题是1.16题，它要求设计一个函数，按照从大到小的顺序输出三个整数。这个问题通过简单的冒泡排序方法得以解决，使用了交换操作符<->进行数值的互换。第二个问题，1.17题，是求k阶斐波那契序列的第m项的值。这个问题使用了一个动态规划的方法，通过一个数组temp存储已计算出的斐波那契序列，避免了重复计算，从而大大提高了效率，使得时间复杂度降低到O(m^2)。这个算法首先对序列进行初始化，然后逐步计算出第k至第m个元素的值。文档还鼓励读者在尝试解决问题并进行充分思考后再查阅解答，以提升学习效果。同时，作者明确表示解答中可能存在错误，欢迎读者指出并共同改进，这体现了开放和协作的学习精神。这份资料是数据结构学习者的重要参考资料，它不仅提供了具体问题的解答，还展示了如何运用数据结构和算法去解决实际问题，对于提升编程思维和技能具有积极的指导作用。

}

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

huangfeishu

粉丝: 1
资源: 25

《数据结构C》习题集解与算法分析

数据结构习题集答案（C语言版）

数据结构 习题集 答案

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

浙江大学数据结构习题集

数据结构严蔚敏习题集

数据结构习题集第九章

浙大数据结构课后习题c语言何越

数据结构课后习题答案

数据结构严蔚敏习题集pdf

数据结构与算法分析 c语言描述(原书第2版)课后习题参考答案

最新资源

数据结构习题集答案