开发者社区> 华章计算机> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

《数据结构与算法 C语言版》—— 3.7小结

简介:
+关注继续查看

本节书摘来自华章出版社《数据结构与算法 C语言版》一 书中的第3章,第3.7节,作者:徐凤生,更多章节内容可以访问云栖社区“华章计算机”公众号查看。

3.7小结

本章介绍了两种特殊的线性表:栈和队列,主要内容如下。
(1)栈
栈是限定仅在表尾(栈顶)进行插入(进栈)或删除(出栈)的线性表,又称后进先出的线性表。栈有两种存储表示:顺序表示(顺序栈)和链式表示(链栈)。
栈的主要操作是进栈和出栈。
对于顺序栈的进栈和出栈要注意判断栈满或栈空,栈满和栈空的条件与栈顶指针的指向有关。本书中栈顶指针指向栈顶元素,栈满的条件是Stop>=Sstacksize-1,栈空的条件是Stop=-1。有的教材中栈顶指针指向栈顶的下一个元素时,栈满和栈空的条件会发生变化,需要特别注意。当然,这两种情况下的进栈和出栈操作也会有所不同。
链栈的进栈操作不需要判断栈是否已满,但出栈操作仍需要判断是否为空栈。
(2)队列
队列是一种先进先出的线性表,它只允许在表的一端(队尾)插入元素(入队),而在另一端(队头)删除元素(出队)。队列也有两种存储表示:顺序表示(循环队列)和链式存储表示(链队列)。
队列的主要操作是入队和出队。
对于顺序表示的循环队列的入队和出队操作要注意判断队满或队空。为了区分队满和队空,需牺牲一个存储单元。队满的条件是(Qrear+1)%MAXSIZE=Qfront,队空的条件是Qfront=Qrear。凡是涉及队头或队尾指针的修改都要对其MAXSIZE求模。
链队的入队操作不需要判断队列是否已满,但出队操作仍需要判断是否为空队列。
(3)递归
递归是程序设计中最为重要的方法之一,递归程序结构清晰,形式简洁。常见的递归有“定义是递归的”、“数据结构是递归的”、“问题的解法是递归的”三种情况。递归的内部实现是通过一个工作栈保存调用过程中的参数、局部变量和返回地址的。根据是否使用栈,可将递归消除分为简单递归消除和基于栈的递归消除两类。
学完本章后,要求掌握栈和队列的特点,熟练掌握顺序栈和链栈的进栈和出栈算法,循环队列和链队列的入队和出队算法,特别注意栈满和栈空、队满和队空的条件。要求能够灵活运用栈和队列解决实际应用问题,掌握数制转换、表达式(前缀、中缀、后缀三种表达方式)求值算法,深刻理解递归算法执行过程中栈的状态变化过程,便于更好地使用递归算法。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【数据结构与算法】十大经典排序(c语言&Java)(5)
【数据结构与算法】十大经典排序(c语言&Java)(5)
0 0
【数据结构与算法】十大经典排序(c语言&Java)(4)
【数据结构与算法】十大经典排序(c语言&Java)(4)
0 0
【数据结构与算法】十大经典排序(c语言&Java)(3)
【数据结构与算法】十大经典排序(c语言&Java)(3)
0 0
【数据结构与算法】十大经典排序(c语言&Java)(2)
【数据结构与算法】十大经典排序(c语言&Java)(2)
0 0
【数据结构与算法】十大经典排序(c语言&Java)(1)
【数据结构与算法】十大经典排序(c语言&Java)(1)
0 0
《数据结构与算法》C语言 实验报告 哈夫曼树实现
《数据结构与算法》C语言 实验报告 哈夫曼树实现
0 0
合并二叉树(java数据结构与算法)采用的是递归方法
合并二叉树(java数据结构与算法)采用的是递归方法
0 0
文章
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
为什么要学函数式编程?
立即下载
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载