首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
admin
2017-11-14
28
问题
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
选项
答案
本题要求用链接结构实现一个队列,可用链表结构来实现。一般说,由于队列的先进先出性质,所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针p”,且要求入队和出队操作的时间复杂性是O(1),因此用只设尾指针的循环链表来实现队列。 (1)proc addq(var p:l。inkedlist,x:elemtp); //p是数据域为data、链域为link的用循环链表表示的队列的尾指针 new(s); //申请新结点。假设有内存空间,否则系统给出出错信息 s ↑.data:=x;s ↑.1ink:=p ↑.link; //将s结点入队 p ↑.1ink:=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/YxRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
同济血案
在社会主义民主政治建设方面,毛泽东提出的“六又”政治局面是()。
中华人民共和国恢复了在联合国合法席位的时间是()。
下列城市:①南京②厦门③天津④杭州,按其在近代历史上开放为商埠的时间先后顺序排列应该是()
简述希波战争过程及其意义。
詹天佑自主设计修建了中国第一条铁路是在()。
电子计算机的发展经过了:①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。
为了限制三帅的权力过大,宋代在中央设立()机构,主管全国的军队调动、训练、供给等事宜。
给定序列{3,5,7,9,11,13,15,17),(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情
设结点x和y是二叉树中任意的两个结点,在该二叉树的先序遍历序列中x在y之前,而在其后序遍历序列中x在y之后,则x和y的关系是()。
随机试题
ThenativeAmericana,thepeoplewecallthe"Indians",hadbeeninAmericaformanythousandsofyearsbeforeChristopherColu
下列关于劳动者权益的叙述中,正确的有()。若吴小姐请求劳动争议仲裁委员会维护其权益,而A公司在法定期间不起诉又不履行仲裁裁决,则吴小姐可以()。
参演人员所承担的具体任务主要包括()。
下列费用中,在进行国民经济评价时不计为项目费用的是()。
AS公司为上市公司,系增值税一般纳税人,适用的增值税税率为17%。所得税采崩资产负债表债务法核算,所得税税率为25%,2015年的财务报告于2016年4月30日经批准对外报出。2015年所得税汇算清缴于2016年4月30日完成。该公司按净利润的10%计提盈
下列说法错误的是()
领导与群众进行亲切交流。参加一活动。但活动层层设防,许多群众因为想看。和警察冲突起来。如果你是执勤民警。你该怎么办?
丁晓兵,武警驻无锡某团政委。他曾在丛林中冒着炮火艰难前行,创造了感天动地的英雄事迹;他更在平凡工作中朝着新的目标执著前进,诠释着“时代先锋”的深刻内涵。面对身体残疾和工作压力,丁晓兵乐观豁达,积极向上,昂扬奋斗,迎难克难。不论职务怎样变化,丁晓兵始终把为人
简述债券筹资的优缺点。
下列选项中,应当以单位犯罪处罚的有()。(2008年多选24)
最新回复
(
0
)