数测结构（本）辣程帕导与练习一第3章 一、相关术语 栈、战顶、进栈、出栈、栈顾元素、顺序栈，链栈、鲑栈、栈项指针、递自、队头、队 尾、出队、入队、稀环对列、链队列 二、找和队列的存储结构 栈是限定仅在表的一端选行括入成酬除操作的线性表，其特点是后进先出。 风列是只允许在一端进行插入，在另一端进行到除的线性表，其特点是先进先出。 栈和队列的存储与一般的线性表的实现类似，也有两种存储方式，即顺序存储和链式存 储。 1,找的限序存储—顺序栈 顺序找类似于顺序表，要分配一块连铁的存储空间存放栈中的元素，通常用一个足够长 度的一雀数组来实现。栈成位置通常设置在数组下标为0的一璃， 面栈原是随着插入和刷除操作而变化的，因此，需要设置一栈顶指针如叩（整型变量）来指 示当前栈顶的位置。通常将da数组和op封装在一个结构体中 。栈的顺序存储结构定义如下： struct SegStack 中声明一个顺序栈类型/ (Elem Type data[MaxSize叶：伸用da数组存储栈中所有的数据元素 ir威top 件用整型变量p指示栈顶元素的位置/ 柱 struct SegStack 's s为指向SeqStack类型的指针变量 序栈要点： (1)静志分配存储空同 (2)插入和到除等操作仅在栈顶处进行 (3)后进先出规则 《4)存在出现象 顺序栈中栈满和栈空的条件分别为：
数据结构（本）课程辅导与练习－第 3 章 一、相关术语 栈、栈顶、进栈、出栈、栈顶元素、顺序栈、链栈、链栈、栈顶指针、递归、队头、队 尾 、出队、入队、循环对列、链队列 二、栈和队列的存储结构 栈是限定仅在表的一端进行插入或删除操作的线性表，其特点是后进先出。 队列是只允许在一端进行插入，在另一端进行删除的线性表，其特点是先进先出。 栈和队列的存储与一般的线性表的实现类似，也有两种存储方式，即顺序存储和链式存 储。 1．栈的顺序存储——顺序栈 顺序栈类似于顺序表，要分配一块连续的存储空间存放栈中的元素，通常用一个足够长 度的一维数组来实现。栈底位置通常设置在数组下标为 0 的一端， 而栈顶是随着插入和删除操作而变化的，因此，需要设置一栈顶指针 top（整型变量）来指 示当前栈顶的位置。通常将 data 数组和 top 封装在一个结构体中 ，栈的顺序存储结构定义如下： struct SeqStack /*声明一个顺序栈类型*/ { ElemType data[MaxSize]; /*用 data 数组存储栈中所有的数据元素*/ int top; /*用整型变量 top 指示栈顶元素的位置*/ }; struct SeqStack *s /*s 为指向 SeqStack 类型的指针变量*/ 顺序栈要点： （1）静态分配存储空间 （2）插入和删除等操作仅在栈顶处进行 （3）后进先出规则 （4）存在溢出现象 顺序栈中栈满和栈空的条件分别为：
·钱满的条件：top一xSize.】 。栈空的条作：op二 2。找的链式存储—链找 战栈的结点结构与单战表的结点结构相同。由于钱的插入和酬除操作仅限制在表头结点 进行，所以用不带头结点的单链表实现栈的结式存储结构以使链 栈的操作运算更加方便。 钱的链式存销结构定义如下： s威rtno{ 俨链栈的结点类型) ElemType data 严结栈结点的数据域 struct node"next. 产链栈结点的指针域/ struct node "top. 作p定义为指向结点类型的指针变量/ 链栈要点： (1)动志分配存储空间，无栈满问题。空间可扩充。 (2)插入和副除等操作仅在栈顶处进行。 (3)链战的栈项在链头。 (4)后进先出规则。 op-NUL表示空栈 3玉，队列的顺序存储一顺序队列 顺序队列和顺序栈一样，要分配一块连线的存储空间来存放队列里的元素，但由于队列 的队头和队尾都是活动的，因此需要两个指针变量来指示队头和 队尾的位置，这一点和顺序钱不同。本教材约定在飘列初始化时，两个指针均置0值。队头 指针ont指向队头元素。队尾指针e指向队尾元素的下一个位 置。入风时，将新元素插入到re所指位置后，再将r的值加l:出队时，到除（取出） ont所指位置的元素后，再将front值如1并运目被剩除元素
● 栈满的条件：top==MaxSize-1 ●栈空的条件：top=-1 2．栈的链式存储——链栈 链栈的结点结构与单链表的结点结构相同。由于栈的插入和删除操作仅限制在表头结点 进行，所以用不带头结点的单链表实现栈的链式存储结构以使链 栈的操作运算更加方便。 栈的链式存储结构定义如下： struct node { /*链栈的结点类型*/ ElemType data; /*链栈结点的数据域*/ struct node *next; /*链栈结点的指针域*/ }; struct node *top; /* top 定义为指向结点类型的指针变量*/ 链栈要点： （1）动态分配存储空间，无栈满问题，空间可扩充。 （2）插入和删除等操作仅在栈顶处进行。 （3）链栈的栈顶在链头。 （4）后进先出规则。 top=NULL 表示空栈 3．队列的顺序存储——顺序队列 顺序队列和顺序栈一样，要分配一块连续的存储空间来存放队列里的元素。但由于队列 的队头和队尾都是活动的，因此需要两个指针变量来指示队头和 队尾的位置，这一点和顺序栈不同。本教材约定在队列初始化时，两个指针均置 0 值。队头 指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位 置。入队时，将新元素插入到 rear 所指位置后，再将 rear 的值加 1；出队时，删除（取出） front 所指位置的元素后，再将 front 值加 1 并返回被删除元素
风列的顺序存储结构定义如下： struct SeqQucue{ 仲顺序队列的类型定义 ElemType datalMaxSize吐"用一锥数组存储队列中的元素/ int front,rear. 仲队头。队尾指针 的 struct SeqQueue *sq 产飘是指向顺序队列类型的指针变量/ 顺序队列要点： (1)静态分配存储空间 (2)入风操作在队尾进行，出队操作在队头进行· (3)注意顺序队列的道出和假上溢现象，可以用循环队列解读“假上溢问愿。 (4)注意队列空和队列满的月题。 (5)先速先出规则。 和顺序栈一样，顺序队列也有空队，满队和非空非满三种状态。 ·若顺序飘列为空。则rer-fem ·若顺序队列为满。则e=MxSx ·若顺序飘列非空非满，则re>ront 4.循环积列 为了克服顺序队列的假上泄现象，充分利用队列的存储空间，我门可以把以列想象成 一个首尾相接的圆环。即将队列中的第一个元素接在最后一个元素的后面，我们称这样的队 列为循环队列(Circular Queue)。 循环队列中队端和队空的条件分别为： ·队满的条件：《a+1%MSx-m(此时，循环队列中能装入的元素的个数为 MxS优) ·队空的条件：re=front 5,队列的链式存能一链队列
队列的顺序存储结构定义如下： struct SeqQueue { /*顺序队列的类型定义*/ ElemType data[MaxSize]; /*用一维数组存储队列中的元素*/ int front,rear; /*队头、队尾指针*/ }; struct SeqQueue *sq; /*sq 是指向顺序队列类型的指针变量*/ 顺序队列要点： （1）静态分配存储空间 （2）入队操作在队尾进行，出队操作在队头进行。 （3）注意顺序队列的溢出和假上溢现象，可以用循环队列解决“假上溢”问题。 （4）注意队列空和队列满的问题。 （5）先进先出规则。 和顺序栈一样，顺序队列也有空队、满队和非空非满三种状态。 ● 若顺序队列为空，则 rear=front ● 若顺序队列为满，则 rear==MaxSize ● 若顺序队列非空非满，则 rear>front 4．循环队列 为了克服顺序队列的“假上溢”现象，充分利用队列的存储空间，我们可以把队列想象成 一个首尾相接的圆环，即将队列中的第一个元素接在最后一个元素的后面，我们称这样的队 列为循环队列（Circular Queue）。 循环队列中队满和队空的条件分别为： ● 队满的条件：（rear+1)%MaxSize=front（此时，循环队列中能装入的元素的个数为 MaxSize） ● 队空的条件：rear=front 5．队列的链式存储——链队列
链队列是一个仅在表头刷除结点和在表尾插入结点的单链表，在歧队列中需要使用两个 指针：头指针ront和尾指针rem。用ont指向威队列的队头， 用e指向链队列的队尾. 链队列的存销结构定文如下： struct node 伸链队列的结点类型/ ElemType data, 岐队列结点的数据域“ truct node◆ext士 产链队列结点的指针域材 struct node *front,"rear. :fm和rer分别为链队列的头指针和尾折针/ 链队列要点： (1)动态分配存储空间 (2)入风操作是在队尾进行，出队操作是在风头进行。 (3)链队列在入队时无队列满的何愿，们有队列空何愿。注意队空的条件。 (4)先进先出规则。 队空的条件：frcn成-er 三、找和队列的比较 栈 队列 逻辑结构 栈是一种运算受限的线性表 栈是一种运算受限的线形表 与线性表的区别 插入运算在表的一瑞（队尾）进行 插入、刷除操作在表的一端透行 副除操作在表的另一端（风头）进行。 特点 后进先出（山FO) 先进先出(FIFO) 栈韧始化InitStack(s) 风列初始化InitQucuc(Q) 进找Push(S.X) 入队InQucue(Q,x) 运算 逃栈PopS) 出队OutQueue(Q,x 判慢空StackEmp心S) 判队空QEmpty(Q)
链队列是一个仅在表头删除结点和在表尾插入结点的单链表。在链队列中需要使用两个 指针：头指针 front 和尾指针 rear。用 front 指向链队列的队头， 用 rear 指向链队列的队尾。 链队列的存储结构定义如下： struct node { /*链队列的结点类型*/ ElemType data; /*链队列结点的数据域*/ struct node *next; /*链队列结点的指针域*/ }; struct node *front,*rear; /* front 和 rear 分别为链队列的头指针和尾指针 */ 链队列要点： （1）动态分配存储空间 （2）入队操作是在队尾进行，出队操作是在队头进行。 （3）链队列在入队时无队列满的问题，但有队列空问题。注意队空的条件。 （4）先进先出规则。 队空的条件：front=rear 三、栈和队列的比较 栈 队列 逻辑结构 栈是一种运算受限的线性表 栈是一种运算受限的线形表 与线性表的区别 插入、删除操作在表的一端进行 插入运算在表的一端（队尾）进行， 删除操作在表的另一端（队头）进行。 特点 后进先出（LIFO） 先进先出（FIFO） 运算 栈初始化 InitStack(s) 进栈 Push(S,x) 退栈 Pop(S) 判栈空 StackEmpty(S) 队列初始化 InitQueue(Q) 入队 InQueue(Q, x ) 出队 OutQueue(Q，x) 判队空 QEmpty（Q）
判栈满StackFull(S) 判队满QF(Q) 取栈顶元素GToS) 读队头元素ReadFront(C,x) 顺序存储 顺序存储 (1)形式 (1)形式 一推数组（存放数据） 一推数组（存成数据） 风头、风尾指针（整形变量》 存储结陶 栈蹊指针（整形变量） 特点 特点 队头可放在数组下标的低端，也可放 雕序栈的大小需预先定义，习惯上将栈 在数组下标的高端。队尾可收在数组下标 底故在数组下标小的一端。 的高端，也可放在树组下标的低端。顺序 队列常设计成循环队列。 筑式存销 筑式存销 (1)形式 (1)形式 单岐表，栈顶指针 单链表，队头、队尾指针 (2》特点 (2)特点 链栈的大小不需要事先定义。在一定内 链栈的大小不需要事先定义。在一定 存范围内。无活考虑栈清。 内存范围内，无香考虑慢满。 栈和队列的基本操作及应用详见教材。 四，练习题 《一)单项选择题 1一个顺序栈一且被声明，其占用空家的大小()。 A.已周定 B.可以改变 C,不能因定 D.动态变化 2,替栈和顺序栈相比，有一个比较明显的缺点，即(）
判栈满 StackFull(S) 取栈顶元素 GetTop(S) 判队满 QFull（Q） 读队头元素 ReadFront(Q,x) 存储结构 顺序存储 （1）形式 一维数组（存放数据） 栈顶指针（整形变量） 特点 顺序栈的大小需预先定义，习惯上将栈 底放在数组下标小的一端。 顺序存储 （1）形式 一维数组（存放数据） 队头、队尾指针（整形变量） 特点 队头可放在数组下标的低端，也可放 在数组下标的高端。队尾可放在数组下标 的高端，也可放在树组下标的低端。顺序 队列常设计成循环队列。 链式存储 （1）形式 单链表，栈顶指针 （2）特点 链栈的大小不需要事先定义。在一定内 存范围内，无需考虑栈满。 链式存储 （1）形式 单链表，队头、队尾指针 （2）特点 链栈的大小不需要事先定义。在一定 内存范围内，无需考虑栈满。 栈和队列的基本操作及应用详见教材。 四、练习题 （一）单项选择题 1.一个顺序栈一旦被声明，其占用空家的大小（ ）。 A．已固定 B．可以改变 C．不能固定 D．动态变化 2．链栈和顺序栈相比，有一个比较明显的缺点，即（ ）
A。插入操作更如方便 且.通常不会出现栈满的情况 C.不会出现栈空的情况 D.酬除操作更加方便 3.用单链表表示的链式队列的队头在鼓表的()位置。 A。链头 B.链尾 C,链中 D.任意位置 4在解决计算机主机与打印机之间速度不元配饲题时通常设置一个打印数据援冲区，主 机将要输出的数据依次写入缓冲区中，面打印机则从缓冲区中取出数据打印。该缓冲区应该 是一个()结构. A。堆栈 B.队列 C,数组 D.先性表 5.若已知一个栈的入栈序列是1,2,3，…，30，其输出序列是p4,p陆.p队P,若pP向-30， 则pe为(》· A.11 B.20 C,19 D.21 6.循环积列Am存放其元素，用ot和过分别表示Q头及风尾，则循环队列满的 条件是()， A.《re+l%m-front
A．插入操作更加方便 B．通常不会出现栈满的情况 C．不会出现栈空的情况 D．删除操作更加方便 3．用单链表表示的链式队列的队头在链表的（ ）位置。 A．链头 B．链尾 C．链中 D．任意位置 4.在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主 机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该 是一个（ ）结构。 A．堆栈 B．队列 C．数组 D．先性表 5. 若已知一个栈的入栈序列是 1，2，3，…，30，其输出序列是 p1,p2,p3,…pn，若 p1=30， 则 p10 为（ ）。 A．11 B．20 C．19 D．21 6．循环队列 A[m] 存放其元素，用 front 和 rear 分别表示队头及队尾，则循环队列满的 条件是（ ）。 A．（rear+1)%m=front
B,fe国=font+1 C.rear=front D.《remr+I%m-1=tront 7。在一个栈顶指针为0p的链慢中，将一个p指针所指的结点入候，应执行()。 A.top-2next=p. B.p->next-top->next;top->nedt-p; C.p->next=top.top-p: D.p>next-top->next;top-top->next; 8.在一个栈项指针为如叩的链钱中酬除一个结点时，用x保存被则结点的值。则执行 A.x-top;topmtop->next B.x-top->data, C.top=top->next;x=lop->data; D.x-top->data top-top.>next 9.表达式ab+c小d的后拨表达式是()· A.abod+ B.abc+d- C.abe+++d. D。.+*abcd 10.在一个链队中，设ot和re通分别为队首和队尾指针，则插入p所指结点时，应 执行()。 A.front-next-p,front-p. B.rear->next=p.rear-p: C.ponext=rear,rear-p; D.p->next=front.front=p
B．rear =front+1 C．rear=front D．（rear+1)%m-1=front 7．在一个栈顶指针为 top 的链栈中，将一个 p 指针所指的结点入栈，应执行（ ）。 A．top->next=p; B．p->next=top->next; top->next=p; C．p->next=top; top=p; D．p->next=top->next; top=top->next; 8．在一个栈顶指针为 top 的链栈中删除一个结点时，用 x 保存被删结点的值，则执行 （ ）。 A．x=top;top=top->next; B．x=top->data; C．top=top->next; x=top->data; D．x=top->data; top=top->next; 9．表达式 a*(b+c)-d 的后缀表达式是（ ）。 A．abcd*+- B．abc+*d- C．abc*++d- D．-+*abcd 10．在一个链队中，设 front 和 rear 分别为队首和队尾指针，则插入 p 所指结点时，应 执行（ ）。 A．front->next=p;front=p; B．rear->next=p;rear=p; C．p->next=rear;rear=p; D．p->next=front;front=p;
(二)填空题 1.向顺序栈插入新元素分为三步：第一步进行 判断，判断条件 是 一：第二步是修改■ 一：第三步是把新元素从给」 一·同样从 顺序栈刷除元素分为三步：第一步进行 判断，判断条件是 一·第 二步是把 二；第三步 2.履设以S和X分别表示入栈和出栈操作，则对输入序列ab.C.de一系列慢操作 SSXSXSSXXX之后，得到的输出序列为一· 3循环队列的引入，目的是为了克服 4,一个逸归算法必须包括和一· 5,判断一个循环队列U(最多元素为m:》为空的条件是 6.在将中缀表达式转换成后缓表达式和计算后缓表达式的算法中，都需要使用钱。对 于前者，进入栈中的元素为表达式中的，而对于后者，进入栈的元素为 中缓表达式a+be-(fde所对应的后搬表达式是 标习题答案 《一)单项达择四 1.A2.B3.A4.B5.D6.A7.C8.D9.B10.B (二)填空题 I.栈是香满多>p一MAXSIZE-1栈项折针栈项对应的数组元素栈是香 空多opl找项元素 修政栈项指针 2.boeda 3假上溢 4.终止条件递归部分 5.LU->frort==LU->recar 6.运算符操作数ab+cde
（二）填空题 1．向顺序栈插入新元素分为三步：第一步进行 判断，判断条件 是 ；第二步是修改 ；第三步是把新元素赋给 。同样从 顺序栈删除元素分为三步：第一步进行 判断，判断条件是 。第 二步是把 ；第三步 。 2．假设以 S 和 X 分别表示入栈和出栈操作，则对输入序列 a,b,c,d,e 一系列栈操作 SSXSXSSXXX 之后，得到的输出序列为 。 3.循环队列的引入，目的是为了克服 。 4．一个递归算法必须包括 和 。 5．判断一个循环队列 LU（最多元素为 m0）为空的条件是 。 6．在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈，对 于前者，进入栈中的元素为表达式中的 ，而对于后者，进入栈的元素为 ， 中缀表达式(a+b)/c-(f-d/c)所对应的后缀表达式是 。 练习题答案 （一）单项选择题 1．A 2．B 3．A 4．B 5．D 6．A 7．C 8．D 9．B 10．B （二）填空题 1．栈是否满 s->top=MAXSIZE-1 栈顶指针 栈顶对应的数组元素 栈是否 空 s->top=-1 栈顶元素 修改栈顶指针 2．bceda 3.假上溢 4．终止条件 递归部分 5．LU->front==LU->rear 6．运算符 操作数 ab+c/fde/--