首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是D(1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是D(1)(不计new和dispose时间)。
admin
2019-08-15
52
问题
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是D(1)(不计new和dispose时间)。
选项
答案
本题要求用链接结构实现一个队列,可用链表结构来实现。一般说,由于队列的先进先出性质,所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针p”,且要求入队和出队操作的时间复杂性是O(1),因此用只设尾指针的循环链表来实现队列。 (1)proc addq(var p:linkedlist,x:elemtp); //p是数据域为data、链域为link的用循环链表表示的队列的尾指针 new(s); //申请新结点。假设有内存空间,否则系统给出出错信息 s ↑.data:=x;s ↑.link:=p ↑.1ink; //将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 ↑.1ink ↑.1ink:=s ↑.1ink; //删队头元素 x:=s ↑.data; //返回出队元素 if(p==s)then p:=p ↑.link; //队列中只有一个结点,出队后成为空队列 dispose(s); //回收出队元素所占存储空间 } endp; 提示:上述入队算法中,因链表结构,一般不必考虑空间溢出问题,算法简单。在出队算法中,首先要判断队列是否为空,另外,对出队元素,要判断是否因出队而成为空队。否则,可能导致因删除出队结点而将尾指针删掉成为“悬挂变量”。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/5OCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1628年出版了《心血运动论》一书,论证了血液在全身的循环运动,使生理学发展为科学的是()。
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
编写判定给定的二叉树是否是二叉排序树的函数。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
在一个双链表中,在*p结点之前插入*q结点的操作是()。
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:(1)请说明系统处于不安全状态;(2
设算术表达式由字符串b表示,其中可以包括三种括号:圆括号、方括号以及花括号,嵌套的顺序随意,如:“{[()]()}”。试编写算法,实现判定给定表达式中所含括号是否正确配对的出现。
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为请设计一个时间上尽可能高效的算法,找出
已知操作符包括‘+’、‘-’、…、‘/’‘(’和‘)’。将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时,用栈来存放暂时还不能确定运算次序的操作符,若栈初始时为空,则转换过程中同时保存在栈中的操作符的
随机试题
甲到银行自动取款机提款后,忘了将借记卡退出便匆忙离开。该银行工作人员乙对自动取款机进行检查时,发现了甲未退出的借记卡,便从该忙中取出5000元,并将卡中剩余的3万元转入自己的借记卡。对乙的行为的定性,下列哪些选项是错误的?()(2006/2/58)
在行政组织结构中,人、目标和权责三者的最初结合,就是()
王某,50岁,腰麻下手术,穿刺注入麻药后即刻血压下降。该药的用量是
问卷调查中,开放式问题与封闭式问题本质区别在于
建筑高度不超过100m的高层建筑,其电缆井、管道并应()在楼板处用相当于楼板耐火极限的不燃烧体作防火分隔;建筑高度超过100m的高层建筑,应在每层楼板处用相当于楼板耐火极限的不燃烧体作防火分隔。
工程对象是整体的,文件内容是全面的,发挥作用是全方位的,这个说法指的是施工组织设计的()。
土工网是港口与航道工程常用的土工织物之一,其具有()功能。
甲公司主张乙公司违约,乙公司则主张合同未成立,其理由是自己向甲公司发出的要约已经撤销。在甲公司提出的以下理由中,可以被法院认定为乙公司撤销要约不能成立的是()。
THERISEOFMOSCOW(1)TheriseofMoscowduringmedievaltimeswasafundamentaldevelopmentinRussianhistory.Moscowbeg
Businessmenoftenthinkthatfluencyandcommunicationtake______overgrammarwhenspeaking.
最新回复
(
0
)