第 3 章 栈、队列、数组 本章为栈和队列部分,首先给出本章学习目标、知识点导图,使读者对本章内 容有整体了解;接着,介绍栈和队列;然后,围绕栈给出栈的定义、栈的存储结构 (顺序栈、链栈、共享栈) 、不同存储结构的基本操作以及栈的常见应用;之后,围绕 队列给出队列的定义、队列的存储结构(循环队列、链队列、双端队列)、不同存储 结构的基本操作以及队列的常见应用;最后一部分为特殊矩阵,包括对称矩阵、三 角矩阵、三对角矩阵(带状矩阵)、稀疏矩阵。 本教材在每章各个需要讲解的部分配有微课视频和配套课件,读者可根据需 要扫描对应部分的二维码获取;同时,考研真题部分也适当配有真题解析微课讲 解,可根据需求扫描对应的二维码获取。 栈、队列、数组(一) 栈、队列、数组(二) ..3.1 本章学习目标 (1)学习栈和队列的基本概念。 (2)掌握栈的存储结构(顺序栈、链栈、共享栈)、不同存储结构的基本操作。 (3)掌握队列的存储结构(循环队列、链队列、双端队列)、不同存储结构的基 本操作。 (4)掌握栈和队列的常见应用。 (5)学习多维数组的存储和特殊矩阵的压缩存储。 ..3.2 知识点导图 栈、队列、数组知识点导图如图3-1所示。 70数据结构知识点与习题精讲(微课版)———专业课学习与考研辅导 图3-1知识点导图 ..3.3知识点归纳 3.1 栈 3. 1.栈概述 3.1栈的概述 3. 1)栈的定义 栈(是限定仅在表尾进行插入或删除操作的线性表。因此,对栈来说,表尾端有其特 stack) tobo 殊含义,称为栈顶(p),相应地,表头端称为栈底( tom )。不含元素的空表称为空栈。 向栈顶插入元素的操作常称为“入栈”,删除栈顶元素的操作称为“出栈”。 如图3-2所示,分别为栈中只有一个元素、栈空和栈满状态(这里假定栈顶指针指向栈 顶元素,要注意栈顶指针是指向栈顶元素还是栈顶元素的下一个位置)。由于在栈顶进行插 2(c) d,c,b, 入和删除操作,因此对应于图3.栈满,出栈序列为e,a。栈中访问结点时遵循后 图3- 2 栈示意图 第3章 栈、队列、数组 71 进先出(LastInFirstOut,LIFO)的原则。 2)栈的基本操作 从线性表角度总结归纳出栈的基本操作如下。 (1)构造一个空栈S,其基本操作为InitStack(&S)。 (2)销毁栈S,S不再存在,其基本操作为DestroyStack(&S)。 (3)判断栈是否为空,若栈S为空栈,则返回1,否则返回0,其基本操作为StackEmpty(S)。 (4)取栈顶元素,若栈不空,则用e返回S的栈顶元素,否则提示为“栈空”,其基本操作 为GetTop(S,&e)。 (5)入栈操作,插入元素e为新的栈顶元素,其基本操作为Push(&S,e)。 (6)出栈操作,若栈不空,则删除S的栈顶元素,并返回其值,否则提示为“栈空”,其基 本操作为Pop(&S,&e)。 其中,栈的存储方式包括顺序栈和链栈两种。下面分别给出不同存储结构下对应的基 本操作的算法实现。 2.存储结构 1)顺序栈及其基本操作 3.3.1顺序栈及其基本操作 (1)顺序栈的定义。栈的顺序存储结构称为顺序栈,顺序栈通常由一个一维数组和一 个记录栈顶元素的变量(或两个变量,一个指向栈底,另一个指向栈顶)组成。 (2)顺序栈的实现。顺序栈的存储结构描述如下。 #define LIST_INIT_SIZE 100 //初始存储空间 typedef char ElemType; //数据元素类型 typedef struct{ ElemType data[LIST_INIT_SIZE]; //存放栈中元素 int top; //用于栈顶指针 //int base; //用于栈底指针 }SqStack; //顺序栈类型 由于栈在使用过程中所需的大小空间很难估计,一般在初始化时不应限定栈的最大容 量,较合理的做法是先为栈分配基本容量,在应用过程中,当空间不足时再扩大,可再设一个 STACKINCREMENT(存储空间分配增量)。 (3)顺序栈的基本操作算法实现。需要特别说明的是,这里假定栈顶指针指向栈顶元 素,要注意栈顶指针是指向栈顶元素还是栈顶元素的下一个位置。顺序栈的存储结构示意 图如图3-2所示。 ① 初始化栈。构造一个空栈S,其基本操作为InitSqStack(SqStack&S)。 void InitSqStack(SqStack &S){ S.top=-1; } 72 数据结构知识点与习题精讲(微课版)———专业课学习与考研辅导 ② 判断栈是否为空。若栈S为空栈,则返回1,否则返回0,其基本操作为StackEmpty (SqStackS)。 int SqStackEmpty(SqStack S){ if(S.top!=-1) return 0; //非空 else return 1; //空 } ③ 取栈顶元素。若栈不空,则用e返回S的栈顶元素,否则返回FALSE,其基本操作 为GetTop(SqStackS,ElemType&e)。 bool GetTop(SqStack S,ElemType &e){ if(S.top==-1) return FALSE; //栈空 else e=S.data[top]; //非空,用e 返回S 的栈顶元素 return TRUE; } ④ 入栈操作。插入元素e 为新的栈顶元素,其基本操作为Push(SqStack &S, ElemTypee)。 bool Push(SqStack &S, ElemType e){ if(S.top== LIST_INIT_SIZE-1) //判满 return FALSE; else S.data[++top]=e; //先自增,再入栈 return TRUE; } ⑤ 出栈操作。若栈不空,则删除S的栈顶元素,并返回其值,否则返回FALSE,其基本 操作为Pop(SqStack&S,ElemType&e)。 bool Pop(SqStack &S, ElemType &e){ if(S.top== -1) //判空 return FALSE; else e= S.data[top--]; //先出栈,再自减 return TRUE; } 2)链栈及其基本操作 3.3.1链栈及其基本操作 (1)链栈的定义。采用链式存储的栈称为链栈。链栈示意图如图3-3所示。通常采用 单链表实现,不存在溢出问题,所有操作均在表头进行。注意,链栈中指针的方向。 第3章 栈、队列、数组 73 图3-3 栈的链式(链栈)存储示意图 (2)链栈的实现。栈的链式存储结构描述如下。 typedef char ElemType; //数据元素类型 typedef struct StackNode { ElemType data; //数据域 struct StackNode *next; //指针域 }StackNode; //结点类型 typedef struct { struct StackNode * top; //栈顶指针 int length; //栈中元素个数 } LStack; //链栈类型 (3)链栈的基本操作算法实现。 栈的链式存储上的操作与链表相似,其入栈和出栈对应于链表的插入和删除,需要注意 的是均在表头进行。栈的链式存储便于插入和删除。这里,链栈可以带头结点也可以不带 头结点,审题时需要注意,具体操作的实现会有所不同。以下基本操作假定不带头结点。 ① 初始化栈。构造一个空栈S,其基本操作为InitLStack(LStack&S)。 void InitLStack(LStack &S){ //构造一个空栈S S.top = NULL; //设栈顶指针的初值为"空" S.length = 0; //空栈中元素的个数为0 } ② 入栈操作。插入元素e 为新的栈顶元素,其基本操作为Push(LStack &S, ElemTypee)。 bool Push(LStack &S, ElemType e){ //在栈顶之上插入元素e,e 为新的栈顶元素 p=new LNode; //建新的结点 if(!p) return FALSE; //存储分配失败 p->data=e; p->next=S.top; //链接到原来的栈顶 S.top = p; //移动栈顶指针 ++S.length; //栈的长度增1 } ③ 出栈操作。若栈不空,则删除S的栈顶元素,并返回其值,否则返回FALSE,其基本 操作为Pop(LStack&S,ElemType&e)。 bool Pop ( LStack &S, ElemType &e ) { if (!S.top) //判空 return FALSE; else { e=S.top->data; //返回栈顶元素 q=S.top; S.top=S.top -> next; //修改栈顶指针 74 数据结构知识点与习题精讲(微课版)———专业课学习与考研辅导 --S.length; //栈的长度减1 delete q; //释放被删除的结点空间 return TRUE; } } 3)共享栈 3.3.1共享栈 由于栈只有一端的地址随入栈操作动态变化,而另外一端不变,这一特点可以让两个栈 共享一个连续空间,如图3-4所示,两个栈的栈底分别位于这段连续空间的两端,在执行入 栈操作时,两个栈顶均向连续空间的中间位置移动,出栈操作时,栈顶则向连续空间的两端 移动。 图3-4 共享栈示意图 判空条件:top1==-1,top2== LIST_INIT_SIZE。 判满条件:top2-top1==1。 入栈:top1先自增再赋值,top2先自减再赋值。 出栈:top1先得到值再自减,top2先得到值再自增。 优点:两个栈的数据元素个数之和不大于连续的存储空间即可执行入栈操作;在满足 入栈条件的前提下,两个栈共享空间,且两个栈的最大长度可变,空间利用率更高。 3.栈的应用 3.3.1栈的应用数制转换和括号匹配应用 1)数制转换的应用 以十进制数转换为八进制数为例,给出进制转换的算法,其他进制转换与其相似。基本 的算法思路为:即将需要转换的数除以8,得到余数,余数的倒序输出即为所求结果,即对应 的八进制数,因需倒序输出,故可采用栈作为辅助存储结构。 void func(int num){ SqStack S; InitSqStack(S); int temp; 第3章 栈、队列、数组 75 while(num) { temp=num%8; Push(S,temp); num=num/8; }w hile(!SqStackEmpty(S)) { Pop(S,temp); printf("%d",temp); }} 2)括号匹配的应用 表达式中可能包含多种类型的括号,如()、[]、{}等,需要对应地去匹配。 基本思想为:每扫描一个左括号,将其入栈。若扫描到右括号,则取栈顶元素,判断其 是否与其匹配,匹配即可出栈;若不匹配则为不合法情况,程序结束。若是左括号,则入栈, 以此类推。最后,当算法结束时,栈为空,则序列括号匹配,否则为序列括号不匹配。 3)表达式求值的应用 3.3.1栈的应用表达式求值的应用 (1)中缀表达式转后缀表达式的方法。中缀表达式需要关注运算符的优先级和括号, 后缀表达式的运算符在操作数的后面、无括号,下面以一个例子说明中缀表达式转为后缀表 达式和由后缀表达式求值的过程。 例题,将中缀表达式a+b/(c+d)-e*f 转换为后缀表达式(手动和计算机计算)。 ① 方法一:手动模拟方法。 第一步,首先需要确定中缀表达式中各运算符的运算顺序: a +b/(c+d)-e*f 顺序标号 32 1 5 4 这里,可以观察到,运算符排序可以不唯一,可约定采用“靠左”的运算符排在前的原则, 如果左边的运算符能先计算就将左边的运算符排在相对右边的运算符前面计算。 第二步,选择计算的运算符,组合为“左操作数右操作数运算符”后可作为新的操作 数,直至所有运算符均处理完毕。 过程1为:cd+作为一个整体操作数,即c+d 的结果为新的操作数,变为a+b/“cd +”-e*f。 过程2为:bcd+/作为一个整体操作数,即b/(c+d)的结果为新的操作数,变为a+ “bcd+/”-e*f。 过程3为:abcd+/+作为一个整体操作数,即a+b/(c+d)的结果为新的操作数,变 为“abcd+/+”-e*f。 76数据结构知识点与习题精讲(微课版)———专业课学习与考研辅导 过程4为:ef*作为一个整体操作数,即e*f的结果为新的操作数,变为“ abcd+/+” -“ ef*”。 过程5为:abcd+/+ef*-作为一个整体操作数,即“ abcd+/+” -“ ef*”的结果为 最后结果,因此得到后缀表达式abcd+/+ef*-。 ②方法二:计算机计算方法。设置运算符栈。 初始化栈,用于保存暂时不能确定运算顺序的运算符。从左至右依次处理如下。 第一步,当遇到操作数时,则加入后缀表达式。 第二步,当遇到括号时,左括号入栈,右括号依次弹出栈内运算符,加入到后缀表达式, 直至弹出左括号,并且需要注意的是括号的匹配性和括号不加入到后缀表达式中。 第三步,当遇到操作符时,弹出运算符栈中优先级高于或等于当前运算符的所有运算 符,同时需要加入到后缀表达式中,如果碰到左括号或栈空则停止,然后当前运算符入栈,最 后可以认为有一个优先级最低的运算符#(为了清空运算符栈), 不需要入栈。其中,关于优 先级,“*”和“/”高于“ +”和“ -”,“*”和“/”相等,“ +”和“ -”相等。可自行采用上述原则 模拟计算机重新计算后缀表达式。 以a+b/(c+d)-e*f为例,过程为:遇到a加入后缀表达式,遇到“ +”入栈,遇到b 加入后缀表达式,遇到“/”入栈,遇到“(”入栈,遇到c加入后缀表达式,遇到“ +”入栈,遇到 d加入后缀表达式,遇到“)”后“ +”出栈并加入后缀表达式,“(”出栈,此时的后缀表达式为 abcd+,栈中运算符为“ +”和“/”。接着,遇到“ -”,依次弹出“/”和“ +”并加入后缀表达 式,“-”入栈,遇到 e 加入后缀表达式,遇到“*”入栈,此时栈中元素为“-”和“*”,遇到 f 加入后缀表达式,最后栈中运算符与“#”比较优先级,依次弹出“*”和“-”,则最后的后缀 表达式可得为abd+/+ef*-。 (2)后缀表式的计算方法。分为手动模拟和计算机计算两种方法。达(c) ①方法一:手动模拟方法。从左至右依次扫描,遇到运算符时,取出运算符前面的两 个操作数执行运算,合为一个操作数,需要注意两个操作数的左右顺序。 例如,bf*-, 再计算b/(然后a+b/(再计算 d+/+e先计算c+d, c+d), c+d), e*f,最后a(a) +(c) c+d) b/(e*f。 ②方法二:计算机计算方法。设置操作数栈。 第一步,从左至右依次扫描,若遇到操作数则入栈,否则执行第二步。 第二步,若为运算符,则依次弹出栈顶两个元素,执行运算,结果重新入栈,这里需要注 意弹出的操作数的顺序,先弹出的为右操作数,后弹出的为左操作数。 (3)中缀表达式的计算。手动模拟方法较简单,可自行完成,本部分主要介绍计算机计 算方法。需要操作数栈和运算符栈。 第一步,若扫描到操作数,则入操作数栈。 第二步,扫描到运算符或括号,则按照中缀转为后缀的方法压入运算符,每当弹出运算符时, 同时需要弹出两个栈顶的操作数,执行运算后再将结果作为操作数压入操作数栈,直至结束。 (4)中缀表达式转前缀表达式。 第一步,确定中缀表达式中运算符的顺序,采用靠右原则,如果右边的运算符能先计算 就将右边的运算符排在相对左边的运算符前面计算。 第二步,按顺序选择运算符,以“运算符左操作数右操作数”的组合计算作为一个新的 第3章栈、队列、数组77 操作数整体,继续处理,直到没有新的操作数为止。例如: a+b/(c+d)-e*f 顺序标号: 5 3 2 4 1 过程为:首先,*ef为一个整体,作为新的操作数;然后+cd为一个整体,作为新的操 作数;接着是/b+cd,再接着是-/b+cd*ef,最后得到+a-/b+cd*ef。 (5)前缀表达式的计算。通过栈(存放操作数)实现前缀表达式的计算。 从右往左扫描,当元素为操作数时,入栈,继续扫描,当元素为运算符时,弹出两个栈顶 元素,执行运算符的运算,结果再入栈,继续扫描,分类处理,直至结束。 栈的应用除了以上提及的3类应用外,还有在递归方面的应用,可查阅程序设计语言 (如C语言程序设计)相关书籍,这里不再赘述。 3.3.2队列 1.队列概述 3.3.2队列概述 1)队列的定义 队列(queue)是限定只能在表的一端进行插入并在另一端进行删除操作的线性表。在 表中,允许插入的一端称为“队列尾(rear),(”) 允许删 除的另一端称为“队列头(front)”。队列示意图如 图3-5所示。当队列中没有任何元素时,称为队空。图3- 5 队列示意图 与栈相反,队列是一种先进先出(FirstInFirstOut,FIFO)的线性表。这和我们日常生 活中的排队是一致的,最早进入队列的元素最早离开。 2)队列的基本操作 总结归纳出队列的基本操作如下。 (1)构造一个空队列Q,其基本操作为InitQueue(&Q )。 (2)销毁队列Q,Q不再存在,其基本操作为DestroyQueue(&Q )。 (3)判断队列是否为空,若队列Q为空队列,则返回1,否则返回0,可由调用它的函数 根据返回值判断当前队列的状态,其基本操作为QueueEmpty(Q); (4)求队列的长度,其基本操作为QueueLength(Q)。 (5)取队头元素,若队列不为空,则用e返回Q的队头元素,否则提示为“队空”,其基本 操作为GetHead(Q,&e )。 (6)入队操作,入队一个元素e为Q的新的元素,其基本操作为EnQueue(&Q,e)。 (7)出队操作,若队列不空,则出队一个元素,用e返回其值,其基本操作为DeQueue (&Q,&e )。 其中,队列的存储方式有顺序队列和链队列。下面分别给出不同存储结构下对应的基 本操作的算法实现。 78 数据结构知识点与习题精讲(微课版)———专业课学习与考研辅导 2.存储结构 1)顺序队列 3.3.2顺序队列及其基本操作 (1)顺序队列的定义。顺序队列利用地址连续的存储空间,依次存放从队头到队尾的 所有元素,即队列的顺序存储。顺序队列由一个一维数组、两个分别指示队头和队尾的变量 组成,分别称为队头指针和队尾指针。这里,可以有两种方式:队头指针指向队头元素,队 尾指针指向队尾元素的下一个位置;或者队头指针指向队头元素,队尾指针指向队尾元素。 需要注意二者的区别。 (2)顺序队列的实现。队列的顺序存储结构描述如下。 #define MaxSize 100 typedef struct { ElemType elem[MaxSize]; //存储队列元素 int rear; //队尾指针 int front; //队头指针 }SqQueue; (3)顺序队列的基本操作。如图3-6所示为空队列和当前队列状态,在非空队列中,队 头指针始终指向队头元素,而队尾指针指向队尾元素的“下一个”位置。 图3-6 顺序队列示意图 初始状态Q.front==Q.rear&&Q.front==0,入队操作时,由于头指针始终指向队头 元素,而尾指针指向队尾元素的“下一个”位置,因此需要先入队,再执行Q.rear++;出队操 作时,需要先获取队头,再执行Q.front++。 2)循环队列及其基本操作 3.3.2循环队列及其基本操作 第3章 栈、队列、数组 79 (1)循环队列的定义。如图3-6所示,如果在这之后又有g、h入队列,而队列中的c、d 出队列,此时队头指针指向e,队尾指针则指到数组外面的位置,即指针越界。当下一个元 素再入队时,入队操作无法进行,但是队列空间并未满,我们称这种现象为假溢出。 由此,可设想数组存储空间是个“环”,7后的下一个位置是0,首尾相接,由此引入了循 环队列的概念,如图3-7和图3-8所示。 图3-7 循环队列的提出示意图 图3-8 循环队列示意图 一般对于循环队列有3种设定方式,需要注意不同设定方式时队列空和队列满的判定 条件。第 一种:为通常采用的方法,牺牲一个单元。约定在入队时少用一个单元,则当队头指 针在队尾指针的下一位置时队列为满。在该种方法下,队列判空的条件为Q.front==Q. rear,队列判满的条件为(Q.rear+1)%MaxSize==Q.front,计算当前队列中的元素个数为 (Q.rear-Q.front+MaxSize)%MaxSize。 第二种:增加标记变量tag,并约定每次删除成功时,tag=0;每次插入成功时,tag=1。 这样tag=0时,若因删除导致Q.front==Q.rear,则队列为空;tag=1时,若因插入导致 Q.front==Q.rear,则队列为满。 第三种:类型中增设表示元素个数的数据成员,可以区分队列满还是队列空。则队列 空的条件为Q.length==0,队列满的条件为Q.length==MaxSize。 (2)循环队列的实现。循环队列的存储结构描述如下。 #define MaxSize 100 typedef struct { ElemType *elem; //存储队列元素 int rear; //队尾指针 int front; //队头指针 }SqQueue; (3)循环队列的基本操作算法实现。假设在非空队列中,头指针始终指向队头元素,而 尾指针指向队尾元素的“下一个”位置。 ① 初始化队列。构造一个空队列Q,其基本操作为InitQueue(SqQueue&Q)。 void InitQueue(SqQueue &Q) { Q.elem = new ElemType[MaxSize]; //分配存储空间 80 数据结构知识点与习题精讲(微课版)———专业课学习与考研辅导 if (!Q.elem) exit(1); //分配失败 Q.front=Q.rear=0; } ② 求队列长度。返回队列Q 中元素的个数,即队列的长度,其基本操作为 QueueLength(SqQueueQ)。 int QueueLength(SqQueue Q) { return ((Q.rear-Q.front+MaxSize)% MaxSize); } ③ 入队操作。若队列不满,入队一个元素e,e为Q 的新的元素,其基本操作为 EnQueue(SqQueue&Q,ElemTypee)。 bool EnQueue(SqQueue &Q,ElemType e) { if ((Q.rear + 1) % MaxSize==Q.front ) return FALSE; Q.elem[Q.rear] = e; Q.rear = (Q.rear+1) % MaxSize; return TRUE; } ④ 出队操作。若队列不空,则出队一个元素,用e 返回其值,其基本操作为 DeQueue(SqQueue&Q,ElemType&e)。 bool DeQueue (SqQueue &Q, ElemType &e) { if (Q.front == Q.rear) return FALSE; e = Q.elem[Q.front]; Q.front = (Q.front+1) % MaxSize; return TRUE; }//DeQueue 3)链队列及其基本操作 3.3.2链队列及其基本操作 (1)链队列的定义。队列的链式存储结构称为链队列。它是一个带有队头指针和队尾 指针的单链表,队头指针指向队头结点,队尾指针指向队尾结点,即单链表的最后一个结点。 队头指针和队尾指针结合起来构成链队结点,如图3-9所示。注意示意图中链队列带头结 点。通常为方便处理,链队列设置头结点。 (2)链队列的实现。队列的链式存储结构描述如下。 typedef struct QNode{ ElemType data; //数据域 struct QNode *next; //指针域 } QNode; //链队列结点类型 typedef struct{ 第3章 栈、队列、数组 81 QNode *front; //指向队列头 QNode *rear; //指向队列尾 } LinkQueue; //链队列类型 图3-9 链队列示意图 (3)链队列的基本操作算法实现。需要特别说明的是,为方便处理,这里假定的链队列 为带有头结点的链队列。不带头结点的链队列相关操作可参看本章重难点解析部分。 ① 初始化队列。构造一个空队列Q,其基本操作为InitLinkQueue(LinkQueue &Q)。 InitLinkQueue(LinkQueue &Q) { //构造一个空队列Q Q.front=Q.rear=new QNode; if (!Q.front) exit(1); //存储空间分配失败 Q.front->next=NULL; } ② 判断队列是否为空。若队列Q 为空队列,则返回1,否则返回0,可由调用它的函数 根据返回值判断当前队列的状态,其基本操作为QueueLinkEmpty(LinkQueue&Q)。 int QueueLinkEmpty(LinkQueue &Q){ if(Q.front==Q.rear) return 1; //队列空 else return 0; //队列非空 } ③ 入队操作。入队一个元素e 为Q 的新的元素,其基本操作为EnLinkQueue (LinkQueue&Q,ElemTypee)。 void EnLinkQueue(LinkQueue &Q,ElemType e) { s = new QNode; if (!s) exit(1); //存储空间分配失败 s->data=e; s->next = NULL; Q.rear->next=s; //修改尾结点指针 Q.rear=s; //移动队尾指针 } ④ 出队操作,若队列不空,则出队一个元素,用e 返回其值,其基本操作为 DeLinkQueue(LinkQueue&Q,ElemType&e)。 82 数据结构知识点与习题精讲(微课版)———专业课学习与考研辅导 bool DeLinkQueue(LinkQueue &Q, ElemType &e) { QNode *p; //若队列不空,则删除当前队头元素 if(Q.front==Q.rear)//链队列中只有一个头结点 return FALSE; p=Q.front->next; e=p->data; //返回被删元素 Q.front->next=p->next; //修改头结点指针 if(Q.rear==p) Q.rear=Q.front; //修改队尾指针 delete p; //释放被删结点 return TRUE; } 4)双端队列 3.3.2双端队列 双端队列指队列的两端均可以进行入队和出队的特殊队列,如图3-10所示。 图3-10 双端队列示意图 一般常见的还有输出受限的双端队列和输入受限的双端队列,如图3-11和图3-12所 示。分别为一端可进行插入和删除,另一端只允许插入的双端队列;以及一端可进行插入和 删除,另一端只允许删除的双端队列。如果再限定从一端插入的元素只能在这一端删除,则 双端队列就变为两个栈底相邻的栈。 图3-11 输出受限的双端队列 图3-12 输入受限的双端队列 3.队列的应用 3.3.2队列的应用 1)队列在计算机系统中的应用 例如,为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区, 第3章栈、队列、数组83 主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。再如,操作 系统中多用户引起的资源竞争问题,需要时可查阅相关资料,这里仅简要提及,不再赘述。 2)队列在树的层次遍历和在图的搜索中的应用 队列在树的层次遍历和在图的搜索中均有应用,可参见后续树和图相关章节的具体内 容,这里不再赘述。 3.3.3数组和特殊矩阵 1.数组 3.3.3数组 矩阵是在科学工程计算中较常见的数学模型之一,数据结构中经常考虑如何使用较小 的存储空间存放一组数据,如将m×n矩阵(m行n列)更有效地存储在内存中,并且能够方 便地获取元素。由于计算机的存储空间是线性的,因此通常程序设计语言使用一维数组存 放二维的矩阵。这里,数组的概念可查阅相关程序设计语言教材,这里不再赘述。本部分主 要关注数组的存储。 数组类型不做插入和删除的操作,因此只需通过顺序映像得到它的存储结构,可以借助 数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 一个数组的所有元素在内存中占用一段连续的存储空间,一维数组的存储结构关系以 a[为例:lc(=oa0)ief(emType)( n]oai)lc(+i×szoEln>i≥0 )。 注意数组的下标范围为n>i≥0,ElemType为数组元素类型,sizeof(ElemType)为数 组元素所占用的存储单元。 1)多维数组的存储 通常有两种映像方法,即“按行优先”展开的映像方法和“按列优先”展开的映像方法。 以下以二维数组为例说明两种方法。 (1)按行优先。行为主序,先行后列,将数组元素按行优先关系排列,先存储行号较小的 元素,行号相等时先存储列号较小的元素,即同一行中的元素以列下标次序排列,如图3-13 所 示,第i+1 行的元素紧跟在第i行元素的后面。 图3-13 按行优先 (2)按列优先。列为主序,先列后行,将数组元素按列优先关系排列,先存储列号较小 的元素,列号相等的时候先存储行号较小的元素,即同一列中的元素以行下标次序排列,如 图3-14 所示,第i+1 列的元素紧跟在第 i 列元素的后面。 图3-14 按列优先 84数据结构知识点与习题精讲(微课版)———专业课学习与考研辅导 2)多维数组存储地址的计算 设每个数组元素需要sizeof(ElemType)个存储单元存放;并记第一个数组元素的存储 地址为loc(a11), 即存储区间的起始地址,也称为数组的基地址。 (1)行为主序优先存储。aij是第i行第j列的数组元素,其前面已存放i-1行共(i- 1)×n个元素,在第j行中前面已经存放了j-1个元素。 地址计算公式为 loc(aij)=loc(a11)+((i-1)×n+j-1)×sizeof(ElemType) 或者按照C语言数组下标,即 loc(aij)=loc(a00)+(i×n+j)×sizeof(ElemType) (2)列为主序优先存储。以列为主序优先存储的地址计算公式为 loc(aij)=loc(a11)+((j-1)×m+i-1)×sizeof(ElemType) 或者按照C语言数组下标,即 loc(aij)=loc(a00)+(j×m+i)×sizeof(ElemType) 2.特殊矩阵的压缩存储 3.3特殊矩阵的压缩存储 3. 对于m×n 阶矩阵,当 m 和 n 较大时,需要占用大量的连续存储空间。通常用二维数 组表示矩阵,则矩阵中的元素均可在二维数组中找到对应的存储位置。一些有下列特性的 高阶矩阵,其元素值的分布具有规律性,矩阵中有很多值相同的元素或零值元素,为了节省 存储空间,需要对它们进行“压缩存储”,不存或者少存这些值相同的元或零值元素,以降低 矩阵对存储容量的需求。 常见的特殊矩阵包括对称矩阵、三角矩阵(上三角矩阵和下三角矩阵)和三对角矩阵(带 状矩阵)等。 1)对称矩阵 i, n≥j≥1, n][中, n 阶方阵,满足aij =aj其中n≥i≥1,存储于二维数组a[n] 这种方 阵被称为对称矩阵。可以将方阵划分为3个区域,分别为 上三角区、主对角线和下三角区。如图3-15 所示,以虚线 为界分为3个区域。 其中,上三角区元素ij。因对称矩阵的上三角区元素与下三角区 元素相同,因此可只存放上三角区和主对角元素或者下三 角区和主对角元素在长度为n( n+1)/2的一维数组中。 以只存放下三角部分为例:第一行存放1个元素,第图3-15 矩阵示意图 二行2个元素,…, 第i-1行i-1个元素,第 i 行j-1个元素,则假设aij 在一维数组中的 下标为k(下标从0开始), 则k=i(1)/2+j-1。 1+2+…+i-1+j-1=i 得到下标对应关系如下 : 第3章 栈、队列、数组 85 k=i×(i-1)/2+j-1 (i≥j)下三角区和主对角线元素 j×(j-1)/2+i-1 (ij)下三角区元素{ 注意,下标从0开始。 下三角矩阵,矩阵的主对角线以上的所有元素均为同一常数或0的n 阶矩阵。 下三角矩阵的压缩存储方法。如图3-17所示,处在下三角的元素aij,其前i-1行共 有i×(i-1)/2个元素,在第i 行它处于第j 个位置,则aij 处于存储分配区的第i×(i- 1)/2+j 个。 图3-17 下三角矩阵的压缩存储示意图 有 k=i×(i-1)/2+j-1 (i≥j)下三角区和主对角线元素 n×(n+1)/2 (i