数据结构导论第三章

数据结构导论第三章第三章栈、队列和数组3.1栈3.2队列3.3数组3.4应用举例3.1栈3.1.1栈的基本概念1、定义栈——限制在表的一端进行插入和删除运算的线性表栈顶（Top）：允许插入和删除的一段栈底（Bottom）：栈的另一端空栈：不含任何数据元素的栈栈顶元素：处于栈顶位置的数据元素例：叠盘子、盒装薯片出栈：在栈顶插入元素入栈：在栈顶删除元素anan-1a2a1……栈顶栈底出栈(pop)进栈(push)栈的特点——后进先出栈中元素按a1，a2，a3，…an的次序进栈，出栈的第一个元素为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出线性表（LIFO）。练习一个栈的入栈序列是a,b,c,d,e,则出栈的可能的顺序是()AcdabeBcabdeCdabecDdecba2、栈的基本运算（1）初始化InitStack(S)：构造一个空栈S（2）判栈空EmptyStack(S):若栈S为空栈，则结果为1，否则结果为0（3）进栈Push(S,x)：将元素x插入栈S中，使x成为栈S的栈顶元素（4）出栈Pop(S)：删除栈顶元素（5）取栈顶GetTop(S)：返回栈顶元素3.1.2栈的顺序实现1、顺序栈及常用名词●顺序栈——即栈的顺序实现；●栈容量——栈中可存放的最大元素个数；●栈顶指针top——指示当前栈顶元素在栈中的位置；●栈空——栈中无元素时，表示栈空；●栈满——数组空间已被占满时，称栈满；●下溢——当栈空时，再要求作出栈运算，则称“下溢”；●上溢——当栈满时，再要求作进栈运算，则称“上溢”；#definemaxsize5typedefstructseqstack{DataTypedata[maxsize];inttop;}SeqStk;SeqStk*s;/*定义一顺序栈s*/约定栈的第1个元素存在data[1]中,则：s-top==0代表顺序栈s为空；s-top==maxsize-1代表顺序栈s为满；top顺序栈类型2102、顺序栈的运算1）初始化intInitstack(SeqStk*stk){stk-top=0;return1;}2)判栈空intEmptyStack(SeqStk*stk){if(stk-top==0)return1;elsereturn0;}栈空时返回值为1，否则返回值为0。210top3)进栈intPush(SeqStk*stk,DataTypex){/*数据元素x进顺序栈stk*/if（stk-top==maxsize-1)/*判是否上溢*/{error(“栈满”);return0;}/*上溢*/else{stk-top++；/*修改栈顶指针，指向新栈顶*/stk-data[stk-top]=x;/*元素x插入新栈顶中*/return1;}}intPop(SeqStk*stk){/*顺序栈stk的栈顶元素退栈*/if（stk-top==0）/*判是否下溢*/{error(“栈空”);return0;}/*下溢*/else{stk-top--；/*修改栈顶指针，指向新栈顶*/return1;}}4)出栈5)取栈顶元素DataTypeGetTop(SeqStk*stk){if(EmptyStack(stk))returnNULLData;//栈空，返回NULLDataelsereturnstk-data[stk-top];//返回栈顶数据元素}1、链式栈的定义栈的链式存储结构称为链栈，它是运算受限的单链表，插入和删除操作仅限制在表头位置上进行。栈顶指针LS-next。…∧链式栈的类型说明如下：typedefstructnode{DataTypedata;structnode*next}LkStk;头指针LS栈顶栈底下溢条件：LS-next==NULL上溢：可不考虑栈满现象3.1.3栈的链式实现—链栈链栈类型1)初始化voidInitStack(LkStk*LS){LS=(LkStk*)malloc(sizeof(LkStk));LS-next=NULL;}2）判栈空intEmptyStack(LkStk*LS){if(LS-next==NULL)return1;elsereturn0;}2、链栈的基本运算2、链栈的基本运算3）进栈——在栈顶插入一元素x●生成新结点（链栈不会有上溢情况发生）●将新结点插入链栈中并使之成为新的栈顶结点a1a2a3a4^topxP×voidPush(LkStk*LS,DataTypex){LkStk*temp;temp=(LkStk*)malloc(sizeof(LkStk));temp-data=x;temp-next=LS-next;LS-next=temp;}4）出栈——在栈顶删除一元素，并返回●考虑下溢问题●不下溢，则取出栈顶元素，从链栈中删除栈顶结点并将结点回归系统。a1a2a3a4^top×intPop(LkStk*LS){LkStk*temp;if(!EmptyStack(LS)){temp=LS-next;LS-next=temp-next;free(temp);return1;}elsereturn0;}练习设一个链栈的输入序列为A、B、C，试写出所得到的所有可能的输出序列，即输出出栈操作得到的数据元素排列。5）取栈顶元素DataTypeGetTop(LkStk*LS){if(!EmptyStack(LS))returnLS-next-data;elsereturnNULLData;}3.1.3栈的应用举例1、栈的基本应用实例：设栈的输入序列依次为1,2,3,4，则所得的输出序列不可能是________。a1,2,3,4b4,2,3,1c1,3,2,4d3,4,2,1例14321？b例2阅读程序片段，写出运行结果。（见P66）例3写一个算法，借助栈将下图所示的带头结点的单链表逆置。(见P67)a1an^head…头结点2、递归与递归的阅读：(1)递归的定义：如果一个函数在完成之前又调用自身，则称之为递归函数。例求整数n的阶乘函数1当n=0时n!=n*(n-1)!当n0时程序实现：intf(intn){if(n==0)return(1);elsereturn(n*f(n-1));}队列(Queue)也是一种运算受限的线性表。▲队列——是只允许在表的一端进行插入，而在另一端进行删除的线性表。其中：允许删除的一端称为队头(front)，允许插入的另一端称为队尾(rear)。队列Q=(a1，a2，a3，…an)▲示意图：出队入队队头队尾a1，a2，…，an（在队头删一元素）（在队尾插一元素）3.2队列3.2.1队列的基本概念例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(FirstInFirstOut)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an，也就是说队列的修改是依先进先出的原则进行的。▲队列特点：先进先出（FIFO）队列的用途——常用于暂时保存有待处理的数据。队列初始化InitQueue(Q):设置一个空队列Q；判队列空EmptyQueue(Q):若队列Q为空，则返回值为1，否则返回值为0；入队列EnQueue(Q,x):将数据元素x从队尾一端插入队列，使其成为队列的新尾元素；出队列OutQueue(Q):删除队列首元素；取队列首元素GetHead(Q):返回队列首元素的值。▲队列的基本操作3.2.2队列的顺序实现—循环队列用一维数组作为队列的存储结构..maxsize-110队列容量—队列中可存放的最大元素个数约定：初始：front=rear=0进队：rear增1，元素插入尾指针所指位置出队：front增1，取头指针所指位置元素队头指针front——队尾指针rear——始终指向实际队头元素的前一位置始终指向实际队尾元素#definemaxsize20typedefstructseqqueue{DataTypedata[maxsize];intfront,rear;}SeqQue;SeqQuesq;入队列操作：sq.rear=sq.rear+1;sq.data[sq.rear]=x;出队列操作：sq.front=sq.front+1;205040302060543210543210543210543210543210sqsq.rearsq.frontsq.rearsq.frontsq.rearsq.frontsq.rearsq.frontsq.rearsq.fronta)e)c)d)b)图a为空队列，sq.rear=0,sq.front=0。图b为20入队列后，sq.rear=1,sq.front=0。图c为30,40,50依次入队列后，sq.rear=4,sq.front=0。图d为20,30,40,50依次出队列后，sq.rear=4,sq.front=4。图e为60入队列后，sq.rear=5,sq.front=4。1、顺序队列——只能从数组的一头插入、另一头删除。SeqQuesq；·上溢条件：sq.rear==maxsize-1(队满)·下溢条件：sq.rear==sq.front(队列空)●假溢出：sq.rear==maxsize-1，但队列中实际容量并未达到最大容量的现象。极端现象：队列中的项不多于1,也导致“上溢”浪费空间为克服“假溢出”引入了循环队列2、循环队列：(1)定义——为队列分配一块存储空间(数组表示)，并将这一块存储空间看成头尾相连接的。·示意图：43210想象成01234循环队列frontrear●头指针front——顺时针方向落后于实际队头元素一个位置●尾指针rear——指向实际队尾元素●循环队列循环的实现sq.rear=(sq.rear+1)%maxsize▲对插入即入队：队尾指针增1sq.front=(sq.front+1)%maxsize▲对删除即出队：队头指针增1●循环队列类型定义：typedefstructCycqueue{DataTypedata[maxsize];intfront,reat;}CycQue;CycQueCQ;01234fr初始front=rear=0J1,J2,J3进队01234fJ1rJ2rJ3rJ1,J2,J3出队01234rf队空J4进队01234J4frJ5,J6进队01234fJ4rJ5J7,J8进队01234fJ4J5J6rJ7rJ9进队队满上溢J2J3fJ1ff例：J6rJ8当队列为空或者为满时，均有front=rear，因此规定如下★规定：循环队列CQ下溢条件即队列空：CQ.front==CQ.rear上溢条件即队列满：尾指针从后面追上头指针即：(CQ.rear+1)%maxsize==CQ.front（尾赶头）（队满时实际队容量=maxsize-1）（2）循环队列运算▲入队——在队尾插入一新元素x●判上溢否？是，则上溢返回；●否则修改队尾指针（增1），新元素x插入队尾。▲出队——删除队头元素，并返回●判下溢否？是，则下溢返回；●不下溢，则修改队头指针，取队头元素。1.队列的初始化2.判队列空3.入队列▲循环队列的基本运算：voidInitQueue(CycQueCQ){CQ.front=0;CQ.rear=0;}intEmptyQueue(CycQueCQ){if(CQ.rear==CQ.front)return1;elsereturn0;}intEnQueue(CycQueCQ,DataTypex){if((CQ.rear+1)%maxsize==CQ.front){error(“队列满”);return0;}//入队列失败else{CQ.rear=(CQ.rear+1)%maxsize;CQ.data[CQ.rear]=x;return1;}//入队列成功}4