




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
3.1
链栈中为何不设置头结点?
3.2循环队列的优点是什么?如何判别它的空和满?3.3设长度为n的链队用单循环链表表示,若设头指针,则入队出队操作的时间为何?若只设尾指针呢?
3.4回文是指正读反读均相同的字符序列,如“abba”和“abdba”均是回文,但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示:将一半字符入栈)3.5设计算法判断一个算术表达式的圆括号是否正确配对。(提示:
对表达式进行扫描,凡遇到'('就进栈,遇')'就退掉栈顶的'(',表达式被扫描完毕,栈应为空。
3.6一个双向栈S是在同一向量空间内实现的两个栈,它们的栈底分别设在向量空间的两端。
试为此双向栈设计初始化InitStack(S)、入栈Push(S,i,x)和出栈Pop(S,i)等算法,
其中i为0或1,
用以表示栈号。
3.7假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素站点(注意不设头指针),试编写相应的置空队、判队空、入队和出队等算法。链栈中为何不设置头结点?
答:链栈不需要在头部附加头结点,因为栈都是在头部进行操作的,如果加了头结点,等于要对头结点之后的结点进行操作,反而使算法更复杂,所以只要有链表的头指针就可以了。循环队列的优点是什么?如何判别它的空和满?
循环队列的优点是:它可以克服顺序队列的"假上溢"现象,能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定,一般是通过以下几种方法:一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是否会重合,如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数,不仅可判别空或满,还可以得到队列中元素的个数。
设长度为n的链队用单循环链表表示,若设头指针,则入队出队操作的时间为何?若只设尾指针呢?
答:当只设头指针时,出队的时间为1,而入队的时间需要n,因为每次入队均需从头指针开始查找,找到最后一个元素时方可进行入队操作。若只设尾指针,则出入队时间均为1。因为是循环链表,尾指针所指的下一个元素就是头指针所指元素,所以出队时不需要遍历整个队列。
回文是指正读反读均相同的字符序列,如"abba"和"abdba"均是回文,但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示:将一半字符入栈)一个双向栈S是在同一向量空间内实现的两个栈,它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack(S)、入栈Push(S,i,x)和出栈Pop(S,i)等算法,其中i为0或1,用以表示栈号。假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素站点(注意不设头指针),试编写相应的置空队、判队空、入队和出队等算法。提示:对表达式进行扫描,凡遇到'('就进栈,遇')'就退掉栈顶的'(',表达式被扫描完毕,栈应为空。
根据提示,可以设计算法如下:
#include<string.h>
#include"stack.h"
intPairBracket(char*S)
{
//检查表达式中括号是否配对
inti;
SeqStackT;//定义一个栈
InitStack(&T);
for(i=0;i<strlen(S);i++)
{
if(S[i]=='(')Push(&T,S[i]);//遇'('时进栈
if(S[i]==')')Pop(&
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 教育领域中技术伦理的挑战及实践应对
- 基层项目部管理办法
- 压铆机模具管理办法
- 合肥无校级管理办法
- 建立完善的社会化、国际化终学平台构想
- 加油站动火管理办法
- 服饰类课件教学课件
- 2025全国青少年禁毒知识竞赛小学组题库(附答案)
- 2025年河南省专技人员公需课考试参考答案
- 2025一建《水利水电工程管理与实务》模拟试卷7带答案与解析
- 2025西藏山南旅游文化投资有限责任公司招聘15人笔试历年参考题库附带答案详解
- 食品快检培训 课件
- 2025年萍乡卫生职业学院单招(语文)测试题库附答案
- 学习解读《水利水电建设工程验收规程》SLT223-2025课件
- 财务部安全隐患自查表
- GB/T 7409.3-1997同步电机励磁系统大、中型同步发电机励磁系统技术要求
- GB/T 28799.2-2020冷热水用耐热聚乙烯(PE-RT)管道系统第2部分:管材
- 金属学及热处理练习题答案
- 抖音号代运营合同范本
- 河北省秦皇岛市各县区乡镇行政村居民村民委员会明细及行政区划代码
- 全国地下水超采区评价技术大纲
评论
0/150
提交评论