C语言数据结构解析与算法实现

需积分: 44 62 浏览量更新于2024-07-24 收藏 258KB PDF 举报

"C语言数据结果" 这篇资料是关于C语言实现数据结构的习题解答，主要参考了严蔚敏《数据结构(c语言版)习题集》，由kaoyan.com计算机版版主一具编写，并且得到了多位网友的修订和完善。解答中采用类C语言编写算法，旨在促进交流和阅读理解，而不是保证程序可以直接上机运行。解答内容包括源代码和必要注释，对于部分难题会有分析说明。未解出的题目有5.20和10.40，作者鼓励读者先尝试解决问题后再参考解答，以提高学习效果。在第一章的两个示例中，展示了两种不同的算法实现： 1.16 示例是一个简单的冒泡排序，用于按从大到小的顺序输出三个整数。它使用了交换操作符 `<->` 来交换变量的值，通过两轮比较和交换确保了输入的三个数按照降序排列。 1.17 示例是求斐波那契序列的第m项值的函数。函数`fib`采用了一种优化的方法，通过保存已计算的结果来减少计算时间，使得时间复杂度降低到O(m^2)。当k小于2或m小于0时，函数返回错误状态。对于不同情况，如m小于k-1时，直接返回0；m等于k-1时，返回1。其余情况下，通过循环计算出k至m之间的斐波那契序列，并将结果存储在temp数组中，最后返回temp[m]作为结果。这个习题解答集是一个进阶学习C语言和数据结构的好工具，适合已经有一定基础的读者，通过阅读和实践来提升自己的编程能力和对数据结构的理解。同时，作者鼓励读者在阅读中发现并纠正错误，积极思考，提升自己的编程技能。如果发现错误或有改进建议，可以联系作者yi-ju@263.net。

}

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

rfjs2010

粉丝: 0
资源: 1

C语言数据结构解析与算法实现

C语言数据结构专升本备考总结文档

C语言数据结构实现学生信息管理系统

C语言数据结构课后习题解答详解

c语言数据结构 数据结构

C语言数据类型

c语言数据结构

C语言 数据类型

c语言数据类型

c语言 数据结构

C语言数据结构

最新资源

c语言数据结构数据结构

C语言数据类型

c语言数据结构