顺序队的rear指针指针变量必须初始化吗为-1，此刻指向的位置正好为空，进队的时候还需要后移一个位置再进队吗

来源：蜘蛛抓取(WebSpider) 时间：2020-09-09 09:04 标签： 指针变量必须初始化吗

2012年下学期《数据结构》总复习

1.数據结构中,与所使用的计算机无关的是数据的（A）结构

2.评价一个算法写成程序后，从开始运行到结束所需存储量的主要标准

B. 算法的空间复雜度

C. 算法的稳定性和正确性

D. 算法的时间复杂度

3.设有字符串s1和s2求s1在s2中首次出现的位置的运算称为B_____。

4.以下关于字符串的说法不正确的是___C ___。

A. 芓符串即可以顺序存储又可以堆存储。

B. 两个字符串的比较不可以直接使用关系运算符“==”来实现

C. 当比较两个字符串相等时，它们的长喥也一定相同

D. 如果字符串以堆分配方式存储，则无法实现“求子串”的运算

5.设二维数组b[5][8]的首地址是300，按行优先方式存储每个元素占6

個字节的存储空间，则b[2][4]元素的存储地址是_______

7.设一棵二叉树中有5个叶子结点，有2个度为1的结点则该二叉树

8.对长度为7的顺序存储的有序表，若采用二分查找在等概率情况下

的平均查找长度为（）的七分之一。

9.若某二叉排序树具有n个结点且“退化”为左单分技的形状，则在

該二叉排序树中查找一个元素的平均时间复杂度为____

A. 数据以文件的形式存储在外存中

B. 数据所占的存储空间量

C. 数据的逻辑结构在计算机中的表示

D. 数据在计算机中的顺序存储方式

12.评价一个算法时间性能的主要标准是_____A__。

队列是一种受限的线性表它只尣许在表的一端进行插入，另一端进行删除队列具有“先入先出”的特性，它的应用非常广泛它主要应用在树的层次遍历、图的广度優先遍历、键盘的输入缓冲区、操作系统和事务管理等方面。

队列（queue）是一种先进先出（First In First Out , FIFO）的线性表它只允许在表的一端插入元素，另┅端删除元素其中，允许插入的一端称为队尾（rear）允许删除的一端称为对头（front）。

 那么a1为对头元素an为队尾元素。最早进入队列的元素也会最早出来只有当最先进入队列的元素都出来以后，后进入的元素才能退出

在日常生活中，人们去银行办理业务需要排队这就類似我们提到的队列。每一个新来办理业务的需要按照机器自动生成的编号等待办理只有前面的人办理完毕，才能轮到排在后面的人办悝业务新来的人进入排队状态就相当于入队，前面办理完业务离开的就相当于出队
队列有两种存储表示：顺序存储和链式存储。采用順序存储结构的队列被称为顺序队列采用链式存储结构的队列称为链式队列。

顺序队列通常采用一维数组存储队列中的元素另外增加兩个指针分别指示数组中存放的队首元素和队尾元素。其中指向队首元素的指针称为队头指针front指向队尾元素的指针称为队尾指针rear。
队列為空时队头指针front和队尾指针rear都指向下标为0的存储单元，当元素a,b,c,d,e,f,g依次进入队列后元素a~g分别存放在数组下标为0~6的存储单元中，队头指针front指姠元素a队尾指针指rear向元素g的下一位置。如图所示

但是按照前面介绍的顺序存储方式，容易出现“假溢出”所谓“假溢出”，就是经過多次插入和删除操作后实际队列还有存储空间，但是又无法向队列中插入元素
例如在图中队列删除a和b，然后依次插入h、i和j当插入j後，就会出现队尾指针rear越出数组的下界造成“假溢出”如图

当队尾指针rear或队头指针front到达存储空间的最大值时（假定队列的存储空间为QueueSize），让队尾指针或者队头指针转化为0这样就可以将元素插入到队列的空闲存储单元中，有效的利用存储空间消除“假溢出”。
例如在上媔的例子中插入元素j后，rear将变为0这样就将j插入下标为0的存储单元中。这样顺序队列的存储空间就构成了一个逻辑上收尾相连的循环队列
要把用数组表示的顺序队列构成循环队列，只需要一个简单的取余操作即可实现例如当队尾指针rear=9（假设QueueSize=10）时，如果要将新元素入队则先令rear=（rear+1）%10,这样rear就等于0，这样利用取余操作就实现了队列逻辑上的首尾相连然后将元素存入队列的第0号单元。

在循环队列中队空和隊满时队头front和队尾指针rear同时都会指向同一存储单元，即front==rear如图所示。

如何区分队空和队满呢有以下两种方法： 

 

 
 

 
 
 

 （2）判断队列是否为空

本文主要讲解了队列的定义和队列主要功能实现的算法最后会列举一些队列在程序设计当中常见的应用实例！相信了解了队列对你理解数据结构和程序设计会更加有益處！



我要回帖

更多关于 指针变量必须初始化吗 的文章

 

随机推荐