线性表的数据结构是栈初始化 使用宏定义栈的长度100，分配地址时报错

来源：蜘蛛抓取(WebSpider) 时间：2020-11-24 09:07 标签： 线性表的数据结构是

在介绍了的两种形式：顺序表和鏈表后我们接下来学习两种特殊的受限制的线性表：栈（LIFO线性表）和队列（FIFO线性表）。

栈是限定仅在一端进行插入或删除操作的线性表虽然这个限制减小了栈的灵活性，但是也使得栈更有效更容易实现。栈还有一个名字称为LIFO（后进先出）线性表，意味着栈存储和删除元素的顺序与元素到达的顺序相反习惯上我们称栈的可访问元素为栈顶元素(top)，元素插入栈称为入栈(push)删除元素称为出栈(pop)。由于栈是一種特殊的线性表所以栈的实现形式也有以下两种：顺序栈和链式栈，下文将对这两种实现分别论述

根据前面栈的简介，我们很方便定義出栈的ADT：

顺序栈的实现本质上是顺序表实现的简化。唯一重要的是确定应该用数组的哪一端表示栈顶，显然为了减少栈操作的时間消耗，我们应该当栈中有n个元素时把位置n-1作为栈顶即选用线性表的末尾作为栈顶。具体实现中我们将top定义为表示栈中的第一个空闲位置，因此空栈的top为0。根据top的定义我们的push首先把一个值插入到栈顶位置，然后把top加1同样，pop首先把top减1然后删除栈顶元素。

下面给出順序栈类的实现：

如何类比顺序栈和顺序表呢我们可以发现，顺序栈中的top简直和顺序表中的curr一毛一样元素的增删查都要通过它。事实仩这是因为top和curr的定义均为当前元素指针，理所当然我们要当前位置指针来进行对象操作了由于数组是固定大小的，我们的增删查操作進行前要分别进行判满和判空处理还有一点需要注意，由于是顺序栈所以在对象的销毁和表的复原操作上非常简单，销毁我们只需要delete掉给listArray分配的数组空间clear我们仅需要将top指针指向0号位置即可。包括删除操作我们并不需要真正去修改要删除结点的存储内容，反正我们有棧顶封着上面那些元素只是单纯的内存单元，存储的是啥不干我们的顺序栈的事

顺便一提，当需要实现多个栈时可以充分利用顺序棧单向延伸的特性。因此可以使用一个数组来存储两个栈，每个栈从各自的端点向中间延伸如下图，这样浪费的空间就会减少但是，只有当两个栈的空间需求有相反的关系时这种方法才奏效。即最好一个栈增长时另一个栈缩短当需要从一个栈中取出元素放入另一個栈中时，这种方法非常有效

相应的，链式栈的实现是对链表实现的简化我们之前介绍过的实际上就是一个链式栈的实例。其元素只能在表头进行插入和删除由于空栈或只有一个元素的栈都不需要特殊情形的结点，所以它不需要表头结点

下面我们给出链式栈的实现：

void clear() // 这里本人有些不解，咋复原和销毁成一样了呢

这里我们做一个小小的总结：类的形式实现线性表的数据结构是极大的方便了我们将线性表的数据结构是进行类比以及对线性表的数据结构是组件的统一管理，我们编写每一个操作时只要思考private修饰符下方的成员属性如何维护鉯及判空和判满即可十分方便记忆和编写。我们同时采用继承ADT类的形式规范了线性表的数据结构是的接口，使得编写的代码既不会遗漏什么关键操作又符合一定的规范，方便用户使用

另外我们可以看到，链式栈的增删查操作的具体代码简直就是链表的复刻对此我們可以对比学习，统一记忆

注：我们本例代码中使用到的Link类沿用了之前我们在单链表定义时Link类的定义，如果读者有疑问请点击

大多数情況下我们看不到栈的最广泛应用，这就是大多数程序设计语言运行环境都有的子程序调用子程序调用是通过把有关子程序的必要信息(包括返回地址、参数、局部变量)存储到一个栈中实现的，这块信息称为活动记录(activation record)；子程序调用把活动记录压入栈每次从子程序中返回时，就从栈中弹出一个活动记录下面从编译器的角度，以递归阶乘函数为例解释这一过程（如果学过汇编或者计算机组成原理PC指针与寄存器这块，下面这段话将不难理解）

考虑用4来调用fact：用来表示程序调用fact的指令所在的地址因此，在第一次调用fact时必须把地址存放到栈Φ，并且把4传递给fact程序接下来再对fact进行一次递归调用，这次参数值变为3把做这次调用的指令地址记为，该地址连同n的当前值(4)被保存到棧中此时调用函数fact所用的输入参数3。

利用类似的方式程序递归调用直至到达了fact的初始状态(n=1)，此时将不会有活动记录入栈将开始展开遞归：每一次从fact返回都将弹出栈所保存的n的当前值，以及函数调用所返回的地址通过存储n的当前值，使得fact的返回值逐次累积并且返回朂后结果。（对这一问题的深刻理解有助于递归程序的设计因为递归程序设计中最难的部分就是思考如何保存和返回结果——刘汝佳紫書）

从上述过程可以看出，由于需要生成一个活动记录并把它压入栈中，一个递归程序的时空开销是十分巨大的所以多数情况下，我們在享用递归程序带来的代码简洁性清晰性的同时还要思考这种递归的设计与我们设计程序的目标是否相符。

ps：最后附上两道比较经典嘚栈的基础题分别考察了栈的后进先出特性，以及栈在解析表达式中的应用

同栈一样，队列也是一种受限的线性表它又被称作FIFO(先进先出)线性表，对应的基本操作为入队(enqueue)和出队(dequeue)这一点我们可以很直观的和真实生活中的排队现象做类比，话不多说上ADT定义：

同样的对于隊列，我们也有顺序队列和链式队列出于操作方便，对于队列我们需要两个指针front和rear分别指示队列和队尾

顺序队列的实现我们与常规的線性结构略微有些不同。物理上其存储仍为一个数组，逻辑上则体现为环形队列（其具体原因涉及到队列的移动问题为了减少每次入隊出队时带来的不必要的移动时间成本，故我们采用这种形式）

所幸的是，有些数论基础的人会发现环形队列的数组下标的循环可以對应到数的循环问题，在数论中就是将数取模所以我们使用取模操作，可以很容易实现顺序队列逻辑上的循环（在这种方法中，数组Φ的位置编号从0到size-1size-1被定义为位置0，即等价于位置size%size的前驱）

和所有顺序线性表类似我们还需要考虑的是顺序队列的判空和判满问题。我們不妨假设front存储队列中队首元素的位置号rear存储队尾元素的位置号。如果front和rear位置相同则表示队列中只有一个元素；当rear比front小1则表示队列为涳。那么我们在来考虑队满的情况当一个有n个可用位置的队列含有n个元素，如果队首元素在位置0则队尾元素一定在位置size-1。我们发现這种定义下我们并不能区分队满和队空的情况。那么是不是修改定义就可以解决问题呢我们吃惊的发现，无论我们如何修改front和rear的定义嘟不能解决这一问题。这就涉及到鸽笼原理了如果数组有n个位置，则队列中最多可以存储n个元素(可以定义为front和rear之差)但队列却可以有n+1种鈈同的状态(有0到n个元素)。也就是说如果我们用front的rear的相对值来定义队列的状态，则必然有两种不能区分

ps：这一问题让博主联想到动态规劃问题求解中状态的定义问题，求解一个动态规划问题的关键首先在于能不能设计出一种能不重不漏描述解状态空间的状态定义

对于环形队列的矛盾，我们可以采用以下两种解决方案：

1.用一个布尔变量来指示队列是否为空

2.设置数组的大小为n+1但是只需存储n个元素。

本篇给絀的代码示例采用第二种形式

// 输入是用户想要的队列最大长度size，maxSize则是实际开的数组大小十分人性化

链式队列的实现不过是对链表实现莋了简单的修改，为了简化实现方式和相关操作我们同样可以使用一个头结点。在初始化的时候front和rear同时指向头结点，之后front总是指向头結点而rear指向队列的尾结点。enqueue和dequeue分别使用的是rear和front指针(脑补一下排队场景就不会弄混)下面是代码是实现：

// 删除的是第一个队列元素，而front是頭结点不为任何元素

注：链式队列的实现中，clear和dequeue函数可以关注一下略微有些不同寻常。

ps：对于队列及其应用还想加深一下的读者可以看一下这道题用到了双端队列以及队列在管理进程方面的作用。

课程名称：线性表的数据结构是A 學时： 56 考核方式：笔试闭卷

一、单项选择题：1－20小题每小题2分，共40分在每小题给出的四个选项中，请选出一项最符合题目要求的选项

1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（ D ）

2.若某线性表最常用的操作是存取任意指定序号的元素和在表尾进行插入和删

除运算，则利用（ A ）存储方式最节省时间

C.带头结点的双循环链表

3.某线性表中最常用的操作是在表尾插入一个元素和删除第一个え素，则采用

（ D ）存储方式最节省运算时间

B.仅有头指针的单循环链表

D.仅有尾指针的单循环链表

4.若进栈序列为123456，且进栈和出栈可以交替进荇则不可能出现的出栈序

5.若用数组A[60]存放循环队列的元素，已知头指针值为35当前队列中有40

个元素，则队列的尾指针值为( C )约定头指针指姠队头元素的前一个位置。

6.深度为6的完全二叉树（根结点的深度为0）至少有（B ）个结点

7.将一棵森林F转换为孩子兄弟链表表示的二叉树T，則F的后根遍历是T 的

8.假设使用图的深度优先搜索DFS算法从根开始遍历一棵二叉树先访问左子

树再访问右子树，则访问结点的顺序相当于二叉樹的（ A ）序列

9.下列线索二叉树中（用虚线表示线索），符合后序线索二叉树定义的是

我要回帖

更多关于 线性表的数据结构是 的文章

 

随机推荐