没有合适的资源?快使用搜索试试~ 我知道了~
首页中南大学数据结构与算法课后习题答案全解:逻辑结构与存储示例
在中南大学数据结构与算法课程中,第一章主要探讨了数据结构的基本概念。首先,数据是计算机处理的基本信息单元,它可以是数字、文字、图像等各种形式。数据元素是构成数据的基本单位,有时也被称作结点或记录,它们可以包含多个数据项。数据类型定义了一组特定值和针对这些值的操作,是编程语言中预先定义的数据结构。 数据结构则是对数据的组织方式,它涉及三个方面:逻辑结构、存储结构和运算。逻辑结构描述了数据元素之间的关系,比如线性结构和非线性结构。线性结构如栈、队列和串,特点是每个结点只有一个直接前驱和后继;而非线性结构如数组、广义表、树和图,结点间的关系更为复杂,可以有多重连接。 举例来说,学生体检情况登记表就是一个数据结构实例,其逻辑结构为线性,每个学生的体检信息形成一条线性的记录链。存储结构关注如何在计算机内存中表示这些关系,可能是顺序存储(相邻记录占用相邻存储空间)或链式存储(使用指针链接各个节点)。运算方面,涉及到对数据结构的查询、修改和删除等操作的设计与实现。 常用的存储表示方法有顺序存储和链式存储。顺序存储强调连续的内存空间,适合于访问速度快但插入和删除效率较低的情况。链式存储则通过指针连接节点,提供较高的插入和删除效率,但查找可能较慢,因为需要逐个节点遍历。 总结来说,第一章概述了数据结构的核心概念,并通过实例展示了如何理解逻辑结构、存储结构以及数据运算,为后续章节深入学习数据结构奠定了基础。理解和掌握这些基本概念,是后续解决更复杂算法问题的关键。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/11193265/bg10.jpg)
(1)程序段的功能是将一栈中的元素按反序重新排列,也就是原来在栈顶的元素放到栈底,栈底的元素放到栈顶。此栈中元素个数限制在 64 个以内。
(2)程序段的功能是利用 tmp 栈将一个非空栈 s1 的所有元素按原样复制到一个栈 s2 当中去。
(3)程序段的功能是利用栈 T,将一个非空栈 S 中值等于 m 的元素全部删去。
(4)程序段的功能是将一个循环队列 Q 经过 S 栈的处理,反向排列,原来的队头变成队尾,原来的队尾变成队头。
(5)这段程序的功能是将队列 1 的所有元素复制到队列 2 中去,但其执行过程是先把队列 1 的元素全部出队,进入队列 2,然后再把队列 2 的元素复制到队
列 1 中。
3.6 回文是指正读反读均相同的字符序列,如"abba"和"abdba"均是回文,但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示:将一半
字符入栈)
解:
根据提示,算法可设计为:
//以下为顺序栈的存储结构定义
#define StackSize 100 //假定预分配的栈空间最多为 100 个元素
typedef char DataType;//假定栈元素的数据类型为字符
typedef struct{
DataType data[StackSize];
int top;
}SeqStack;
int IsHuiwen( char *t)
{//判断 t 字符向量是否为回文,若是,返回 1,否则返回 0
SeqStack s;
int i , len;
char temp;
InitStack( &s);
len=strlen(t); //求向量长度
for ( i=0; i<len/2; i++)//将一半字符入栈
Push( &s, t[i]);
while( !EmptyStack( &s))
{// 每弹出一个字符与相应字符比较
temp=Pop (&s);
if( temp!=S[i]) return 0 ;// 不等则返回 0
else i++;
}
return 1 ; // 比较完毕均相等则返回 1
}
3.7 利用栈的基本操作,写一个将栈 S 中所有结点均删去的算法 void ClearStack( SeqStack *S),并说明 S 为何要作为指针参数?
解:
算法如下
void ClearStack (SeqStack *S)
{ // 删除栈中所有结点
![](https://csdnimg.cn/release/download_crawler_static/11193265/bg11.jpg)
S->Top = -1; //其实只是将栈置空
}
因为要置空的是栈 S,如果不用指针来做参数传递,那么函数进行的操作不能对原来的栈产生影响,系统将会在内存中开辟另外的单元来对形参进行函数操
作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话,就只能用指针来做参数传递了。
3.8 利用栈的基本操作, 写一个返回 S 中结点个数的算法 int StackSize( SeqStack S),并说明 S 为何不作为指针参数?
解:
算法如下:
int StackSize (SeqStack S)
{//计算栈中结点个数
int n=0;
if(!EmptyStack(&S))
{
Pop(&S);
n++;
}
return n;
}
上述算法的目的只要得到 S 栈的结点个数就可以了。并不能改变栈的结构。所以 S 不用指针做参数,以避免对原来的栈中元素进行任何改变。系统会把原
来的栈按值传递给形参,函数只对形参进行操作,最后返回元素个数。
3.9 设计算法判断一个算术表达式的圆括号是否正确配对。 (提示: 对表达式进行扫描,凡遇到'('就进栈,遇')'就退掉栈顶的'(',表达式被扫描完毕,栈
应为空。
解:
根据提示,可以设计算法如下:
int PairBracket( char *SR)
{//检查表达式 ST 中括号是否配对
int i;
SeqStack S; //定义一个栈
InitStack (&s);
for (i=0; i<strlen(SR) ; i++)
{
if ( S[i]=='(' ) Push(&S, SR[i]); //遇'('时进栈
if ( S[i]==')' ) //遇')'
if (!StackEmpty(S))//栈不为空时,将栈顶元素出栈
Pop(&s);
else return 0;//不匹配,返回 0
}
if EmptyStack(&s) return 1;// 匹配,返回 1
else return 0;//不匹配,返回 0
}
![](https://csdnimg.cn/release/download_crawler_static/11193265/bg12.jpg)
3.10 一个双向栈 S 是在同一向量空间内实现的两个栈,它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化 InitStack ( S ) 、入栈 Push( S , i ,
x) 和出栈 Pop( S , i )等算法, 其中 i 为 0 或 1, 用以表示栈号。
解:
双向栈其实和单向栈原理相同,只是在一个向量空间内,好比是两个头对头的栈放在一起,中间的空间可以充分利用。双向栈的算法设计如下:
//双向栈的栈结构类型与以前定义略有不同
#define StackSize 100 // 假定分配了 100 个元素的向量空间
#define char DataType
typedef struct{
DataType Data[StackSize]
int top0; //需设两个指针
int top1;
}DblStack
void InitStack( DblStack *S )
{ //初始化双向栈
S->top0 = -1;
S->top1 = StackSize; //这里的 top2 也指出了向量空间,但由于是作为栈底,因此不会出错
}
int EmptyStack( DblStack *S, int i )
{ //判栈空(栈号 i)
return (i == 0 && S->top0 == -1|| i == 1 && S->top1== StackSize) ;
}
int FullStack( DblStack *S)
{ //判栈满,满时肯定两头相遇
return (S->top0 == S-top1-1);
}
void Push(DblStack *S, int i, DataType x)
{ //进栈(栈号 i)
if (FullStack( S ))
Error("Stack overflow");//上溢、退出运行
if ( i == 0) S->Data[ ++ S->top0]= x; //栈 0 入栈
if ( i == 1) S->Data[ -- S->top1]= x; // 栈 1 入栈
}
DataType Pop(DblStack *S, int i)
{ //出栈(栈号 i)
if (EmptyStack ( S,i) )
Error("Stack underflow");//下溢退出
if( i==0 )
return ( S->Data[ S->top0--] );//返回栈顶元素,指针值减 1
if( i==1 )
![](https://csdnimg.cn/release/download_crawler_static/11193265/bg13.jpg)
return ( S->Data[ S->top1++] ); //因为这个栈是以另一端为底的,所以指针值加 1。
}
3.11 Ackerman 函数定义如下:请写出递归算法。
┌ n+1 当 m=0 时
AKM ( m , n ) = │ AKM( m-1 ,1) 当 m≠0 ,n=0 时
└ AKM( m-1, AKM( m,n-1)) 当 m≠0, n ≠ 0 时
解:
算法如下
int AKM( int m, int n)
{
if ( m== 0) return n+1;
if ( m<>0 && n==0 ) return AKM( m-1, 1);
if ( m<>0 && n<>0 ) return AKM( m-1, AKM( m, n-1));
}
3.12 用第二种方法 ,即少用一个元素空间的方法来区别循环队列的队空和队满,试为其设计置空队,判队空,判队满、出队、入队及取队头元素等六个基本
操作的算法。
解:
算法设计如下:
//循环队列的定义
#define QueueSize 100
typedef char Datatype ; //设元素的类型为 char 型
typedef struct {
int front;
int rear;
DataType Data[QueueSize];
}CirQueue;
(1)置空队
void InitQueue ( CirQueue *Q)
{ // 置空队
Q->front=Q->rear=0;
}
(2)判队空
int EmptyQueue( CirQueue *Q)
{ //判队空
return Q->front==Q->rear;
}
(3)判队满
int FullQueue( CirQueue *Q)
{ // 判队满//如果尾指针加 1 后等于头指针,则认为满
![](https://csdnimg.cn/release/download_crawler_static/11193265/bg14.jpg)
return (Q->rear+1)%QueueSize== Q->front;
}
(4)出队
DataType DeQueue( CirQueue *Q)
{ //出队
DataType temp;
if(EmptyQueue(Q))
Error("队已空,无元素可以出队");
temp=Q->Data[Q->front] ;//保存元素值
Q->front= ( Q->front+1 ) %QueueSize;//循环意义上的加 1
return temp; //返回元素值
}
(5)入队
void EnQueue (CirQueue *Q, DataType x)
{ // 入队
if( FullQueue( Q))
Error ("队已满,不可以入队");
Q->Data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize; //rear 指向下一个空元素位置
}
(6)取队头元素
DataType FrontQueue( CirQueue *Q)
{ //取队头元素
if (EmptyQueue( Q))
Error( "队空,无元素可取");
return Q->Data[Q->front];
}
3.13 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素站点(注意不设头指针) ,试编写相应的置空队、判队空 、入队和出队等算法。
解:
算法如下:
//先定义链队结构:
typedef struct queuenode{
Datatype data;
struct queuenode *next;
}QueueNode; //以上是结点类型的定义
typedef struct{
queuenode *rear;
}LinkQueue; //只设一个指向队尾元素的指针
(1)置空队
剩余118页未读,继续阅读
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/7ab3864cf5254b8888203cbd8fa94117_u012654205.jpg!1)
清澈希望
- 粉丝: 9
- 资源: 20
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测:静态代码分析与数据流方法
- 青苔数据CEO程永:技术生态与阿里云开放创新
- 制造业转型: HyperX引领企业上云策略
- 赵维五分享:航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛:AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器:设计与实现
- 猩便利工程师仲小玉:Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享:高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会:阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)