首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
admin
2017-01-04
72
问题
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
选项
答案
本题要求用链接结构实现一个队列,可用链表结构来实现。一般说,由于队列的先进先出性质,所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针p”,且要求入队和出队操作的时间复杂性是O(1),因此用只设尾指针的循环链表来实现队列。 (1)proc addq(var p:linkedlist,x:elemtp); //p是数据域为data、链域为link的用循环链表表示的队列的尾指针 new(s); //申请新结点。假设有内存空间,否则系统给出出错信息 s ↑.datal.=x;s ↑.link:=p ↑.link; //将s结点入队 p ↑.link:=s;p::s; //尾指针p移至新的队尾 endp; (2)proc deleq(var p:linkedlist,Var x:elemtp); //p是数据域为data、链域为link的用循环链表表示的队列的尾指针,本算法实 //现队列元素的出队,若出队成功,返回出队元素,否则给出失败信息 if(p ↑.link==p)then{writeln(”空队列”);return(0);} //带头结点的循环队列 else{s:=p↑.link ↑.link; //找到队头元素 p ↑.link ↑.link:=s↑.link; //删队头元素 x:=s ↑.data; //返回出队元素 if(p==s)then p:=p ↑.link; //队列中只有一个结点,出队后成为空队列 dispose(s); //回收出队元素所占存储空间 } endp; 提示:上述入队算法中,因链表结构,一般不必考虑空间溢出问题,算法简单。在出队算法中,首先要判断队列是否为空,另外,对出队元素,要判断是否因出队而成为空队。否则,可能导致因删除出队结点而将尾指针删掉成为“悬挂变量”。
解析
转载请注明原文地址:https://kaotiyun.com/show/oLRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
近代自然科学产生的条件及其发展情况。
试析凡尔赛一华盛顿体系的实质及其对一战后国际关系的影响。
继承并发展德谟克利特和伊壁鸠鲁的“原子论”,认为宇宙万物都是由原子构成的,并按照物质本身所特有的规律发展的罗马共和国时期的哲学家()。
诸侯国的国君如何用人呢?有人主张:“左右皆曰不可,勿听;诸大夫皆曰不可,勿听;国人皆曰不可,然后察之,见不可焉,然后去之。”这种主张最终可能出自下列哪位思想家之口()。
白虎观会议是由汉()帝主持的。
1543年发表解剖学专著《人体结构论》的是()。
有研究者提出,1850年以后的34年中,流人中国的白银是之前34年的两倍。出现这一现象的原因是()
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:(1)请说明系统处于不安全状态;(2
在下列排序方法中不需要对排序码进行比较就能进行排序的是()。
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
随机试题
A.Miles手术B.Hartmann手术C.乙状结肠造口术D.Dixon手术E.拉下式直肠癌切除术距肛门口7~10cm之间的直肠癌多采用
失神发作(以往称小发作)见于
二尖瓣狭窄的主要诊断依据是
“君主之官”是()。
土不足时,木对土的过度制约。属于
盘盈的固定资产,按其市价或同类、类似固定资产的市场价格确定其成本。()
阅读下列材料,回答问题。材料一:17世纪,整个欧洲大陆处于宗教的迫害之中,反映自由、民主和科学的新思想,被当作“异端”“邪说”而受压制,不少有发明创造的科技人才被处刑罚。与此同时,战争也连绵不断,法国处于内战和向外扩张的连年战争中。意大利四分五裂
教育教学过程是教师直接用自身的知识、智慧、品德影响学生的过程。这反映了教师劳动的特点是()
设A3×3=[α1,α2,α3],方程组Ax=β有通解kξ+η=kE1,2,一3]T+[2,一1,1]T,其中k是任意常数.证明:方程组[α1+α2+α3+β,α1,α2,α3]x=β有无穷多解,并求其通解.
Eleven-year-oldAngelawasstrickenwithadebilitating(衰弱的)diseaseinvolvinghernervoussystem.Shewasunabletowalkandh
最新回复
(
0
)