严蔚敏《数据结构》习题集C语言解答与优化

需积分: 9 168 浏览量更新于2024-08-01 收藏 538KB PDF 举报

数据结构（严蔚敏）习题集答案是针对严蔚敏编写的《数据结构（C语言版）》教材中的算法设计题目提供了解决方案。该习题集由kaoyan.com计算机版版主一具整理，得到了网友siice、龙抬头、iamkent、zames、birdthinking等人的贡献和修订。解答以C语言描述，注重交流性和可读性，但不保证程序能直接上机运行，因为验证程序正确性的实践意义不大。章节一的概述部分，首先介绍了两个函数： 1.16 函数`print_descending`用于按从大到小的顺序打印三个输入整数。通过三重循环进行冒泡排序，时间复杂度为O(n^2)，适用于小型数据集的排序。 1.17 函数`fib`则是求解k阶斐波那契数列的第m项。它采用了动态规划的方法，通过存储中间计算结果避免了重复计算，显著降低了时间复杂度，从原问题的O(2^n)降低到了O(m^2)。这个函数接收参数k（阶数）、m（索引），并返回第m项的值。当k小于2或m小于0时，函数返回错误状态。作者强调了读者在参考解答前应先尝试自己解决题目，以提高复习效果，并鼓励读者发现并纠正解答中的错误，积极反馈至yi-ju@263.net邮箱。由于作者水平限制，解答可能存在错误和不足，这正是一个学习和提升的机会，读者应积极参与思考和实践。这个习题集答案不仅提供了具体代码实现，还包含了解题策略和优化技巧，对学习者理解和掌握数据结构中的算法设计有着重要的辅助作用。

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

void GetFib_CyQueue(int k,int n)//求 k阶斐波那契序列的前 n+1项

{

InitCyQueue(Q); //其MAXSIZE 设置为 k

for(i=0;i<k-1;i++) Q.base[i]=0;

Q.base[k-1]=1; //给前 k项赋初值

fo r(i=0;i<k;i++) printf("%d",Q.base[i]);

for(i=k;i<=n;i++)

{

m=i%k;sum=0;

for(j=0;j<k;j++) sum+=Q.base[(m+j)%k];

Q.base[m]=sum; //求第 i 项的值存入队列中并取代已无用的第一项

printf("%d",sum);

}

}//GetFib_CyQueue

3.33

Status EnDQueue(DQueue &Q,int x)//输出受限的双端队列的入队操作

{

if((Q.rear+1)%MAXSIZE==Q.front) return OVERFLOW; //队列满

avr=(Q.base[Q.rear-1]+Q.base[Q.front])/2;

if(x>=avr) //根据 x的值决定插入在队头还是队尾

{

Q.base[Q.rear]=x;

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

} //插入在队尾

else

{

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

Q.base[Q.front]=x;

} //插入在队头

return OK;

}//EnDQueue

Status DeDQueue(DQueue &Q,int &x)//输出受限的双端队列的出队操作

{

if(Q.front==Q.rear) return INFEASIBLE; //队列空

x=Q.base[Q.front];

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

return OK;

}//DeDQueue

3.34

void Train_Rearrange(char *train)//这里用字符串 train表示火车,'P'表示硬座,'H'表示硬卧,'S'

表示软卧,最终按 PSH 的顺序排列

{

r=train;

InitDQueue(Q);

while(*r)

{

if(*r=='P')

{

printf("E");

printf("D"); //实际上等于不入队列,直接输出 P 车厢

}

else if(*r=='S')

{

printf("E");

EnDQueue(Q,*r,0); //0 表示把 S 车厢从头端入队列

}

else

{

printf("A");

EnDQueue(Q,*r,1); //1 表示把 H 车厢从尾端入队列

}

}//while

while(!DQueueEmpty(Q))

{

printf("D");

DeDQueue(Q);

}//while //从头端出队列的车厢必然是先 S 后 H 的顺序

}//Train_Rearrange

第四章串

4.10

void String_Reverse(Stringtype s,Stringtype &r)//求 s 的逆串 r

{

StrAssign(r,''); //初始化 r 为空串

for(i=Strlen(s);i;i--)

{

StrAssign(c,SubString(s,i,1));

StrAssign(r,Concat(r,c)); //把 s 的字符从后往前添加到 r 中

}

}//String_Reverse

4.11

剩余55页未读，继续阅读

huganle

粉丝: 16
资源: 11

严蔚敏《数据结构》习题集C语言解答与优化

严蔚敏数据结构习题集全面答案解析

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

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

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

数据结构严蔚敏习题集及其答案

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

数据结构 严蔚敏 习题集

数据结构（严蔚敏习题集答案）

数据结构严蔚敏习题集C++实现

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

最新资源

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

数据结构严蔚敏习题集

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