2. 考研
  3. 设结点结构为(data，link)，试用一个全局指针p和某种链接结构实现一个队列，画出示意图，并给出入队addq和出队deleq过程，要求它们的时间复杂性都是D(1)(不计new和dispose时间)。

设结点结构为(data，link)，试用一个全局指针p和某种链接结构实现一个队列，画出示意图，并给出入队addq和出队deleq过程，要求它们的时间复杂性都是D(1)(不计new和dispose时间)。

admin2019-08-15  68
问题 设结点结构为(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

学硕统考专业

相关试题推荐
随机试题
最新回复(0)