《数据结构与算法 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)递归
递归是程序设计中最为重要的方法之一,递归程序结构清晰,形式简洁。常见的递归有“定义是递归的”、“数据结构是递归的”、“问题的解法是递归的”三种情况。递归的内部实现是通过一个工作栈保存调用过程中的参数、局部变量和返回地址的。根据是否使用栈,可将递归消除分为简单递归消除和基于栈的递归消除两类。
学完本章后,要求掌握栈和队列的特点,熟练掌握顺序栈和链栈的进栈和出栈算法,循环队列和链队列的入队和出队算法,特别注意栈满和栈空、队满和队空的条件。要求能够灵活运用栈和队列解决实际应用问题,掌握数制转换、表达式(前缀、中缀、后缀三种表达方式)求值算法,深刻理解递归算法执行过程中栈的状态变化过程,便于更好地使用递归算法。

相关文章
|
5月前
|
机器学习/深度学习 算法
数据结构与算法之时间复杂度和空间复杂度(C语言版)
数据结构与算法之时间复杂度和空间复杂度(C语言版)
数据结构与算法之时间复杂度和空间复杂度(C语言版)
|
20天前
|
存储 机器学习/深度学习 算法
C语言代码实现数据结构与算法
以上代码中,哈希表使用链表解决哈希冲突,每个链表节点包含一个键值对。hash函数用于计算键值对应的哈希值,insert函数用于向哈希表中插入一个键值对,若当前位置为空,则直接插入;否则,将新节点插入到链表末尾。search函数用于在哈希表中查找指定键值的值,若存在则返回其值,否则返回-1。
32 1
|
8月前
|
存储 算法 NoSQL
[数据结构与算法(严蔚敏 C语言第二版)]第1章 绪论(章节题库+答案解析)
[数据结构与算法(严蔚敏 C语言第二版)]第1章 绪论(章节题库+答案解析)
|
8月前
|
存储 算法 C语言
[数据结构与算法(严蔚敏 C语言第二版)]第1章 绪论(课后习题+答案解析)
[数据结构与算法(严蔚敏 C语言第二版)]第1章 绪论(课后习题+答案解析)
|
算法 Java C语言
【数据结构与算法】十大经典排序(c语言&Java)(5)
【数据结构与算法】十大经典排序(c语言&Java)(5)
95 0
【数据结构与算法】十大经典排序(c语言&Java)(5)
|
存储 算法 搜索推荐
【数据结构与算法】十大经典排序(c语言&Java)(4)
【数据结构与算法】十大经典排序(c语言&Java)(4)
129 0
【数据结构与算法】十大经典排序(c语言&Java)(4)
|
移动开发 算法 搜索推荐
【数据结构与算法】十大经典排序(c语言&Java)(3)
【数据结构与算法】十大经典排序(c语言&Java)(3)
96 0
【数据结构与算法】十大经典排序(c语言&Java)(3)
|
算法 搜索推荐 Java
【数据结构与算法】十大经典排序(c语言&Java)(2)
【数据结构与算法】十大经典排序(c语言&Java)(2)
120 0
【数据结构与算法】十大经典排序(c语言&Java)(2)
|
算法 搜索推荐 Java
【数据结构与算法】十大经典排序(c语言&Java)(1)
【数据结构与算法】十大经典排序(c语言&Java)(1)
138 0
【数据结构与算法】十大经典排序(c语言&Java)(1)
|
人工智能 算法 BI
《数据结构与算法》C语言 实验报告 哈夫曼树实现
《数据结构与算法》C语言 实验报告 哈夫曼树实现
284 0
《数据结构与算法》C语言 实验报告 哈夫曼树实现