(3)--lecture3数据结构数据结构.ppt

《(3)--lecture3数据结构数据结构.ppt》由会员分享，可在线阅读，更多相关《(3)--lecture3数据结构数据结构.ppt（127页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第第3章章栈和队栈和队列列 栈栈和和队队列是列是对线对线性表的某些操作加以限定而派生出性表的某些操作加以限定而派生出的的结结构。它构。它们们的操作本身并不的操作本身并不难难掌握，掌握，难难点是理解点是理解栈栈和和队队列的列的应应用思想、掌握其算法的用思想、掌握其算法的设计设计技巧。技巧。2 通常称，栈和队列是限定插入插入和删除除只只能能在表的“端点端点”进行的线性表。线性表性表 栈 队列列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1 Delete(L,i)Delete(S,n)Delete(Q,1)1in栈和队列是两种常用的数据类型3v 3

2、.1 栈v 3.2 栈的的应用用举例例v 3.3 队列列v 3.4 队列列应用用举例例43.1 栈栈一、一、栈的的结构特点和操作构特点和操作二、二、栈的表示和操作的的表示和操作的实现5一、一、栈的的结构特点和操作构特点和操作6栈栈(Stack)的定义的定义a2a1a4a3栈底底栈顶 栈(stack)是限定只能在表的一端进行插入和删除的线性表。在栈中,允许插入和删除的一端称为“栈顶”(top),不允许插入和删除的一端称为“栈底底”(bottom)。7InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetT

3、op(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S)栈的的基本操作：基本操作：8InitStack(&S)操作结果：构造一个空栈 S。DestroyStack(&S)初始条件：栈 S 已存在。操作结果：栈 S 被销毁。9 StackEmpty(S)初始条件：栈 S 已存在操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。10 StackLength(S)初始条件：栈 S 已存在。操作结果：返回 S 的元素个数，即栈的长度。11 GetTop(S,&e)初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。a1a2an 12 Cle

4、arStack(&S)初始条件：栈 S 已存在。操作结果：将 S 清为空栈。13 Push(&S,e)初始条件：栈 S 已存在。操作结果：插入元素 e 为 新的栈顶元素。a1a2ane 14 Pop(&S,&e)初始条件：栈 S 已存在且非空。操作结果：删除 S 的栈顶元素，并用 e 返回其值。a1a2 anan-1 15v 顺序序栈v 链栈二、二、栈的表示和操作的的表示和操作的实现16v顺序序栈 类似于线性表的顺序表示法，指向表尾的指针可以作为栈顶指针。/-栈的顺序存储表示栈的顺序存储表示-#define STACK_INIT_SIZE 100;#define STACKINCREMENT

5、10;typedef struct SElemType *base;SElemType *top;int stacksize;SqStack;类似于似于线性表的性表的顺序映象序映象实现，指向表尾的指指向表尾的指针可以作可以作为栈顶指指针。Status InitStack(SqStack&S)/构造一个空构造一个空栈S S.base=(ElemType*)malloc(STACK_INIT_SIZE *sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存存储分配失分配失败 S.top=S.base;S.stacksize=STACK_INIT_SIZE;re

6、turn OK;Status Push(SqStack&S,SElemType e)/若若栈不不满，则将元素将元素 e 插入插入栈顶，并返回，并返回 OK;/否否则返回返回 OVERFLOW if(S.top-S.base=S.stacksize)return OVERFLOW;else *S.top+=e;return OK;Status Pop(SqStack&S,SElemType&e)/若若栈不空，不空，则删除除S的的栈顶元素，元素，/用用 e 返回其返回其值，并返回，并返回OK；/否否则返回返回ERROR if(S.top=S.base)return ERROR;e=*-S.top;

7、return OK;21栈顶指指针a1an注意注意:链栈中中指指针的方向的方向an-1v链栈top223.2 栈的应用举例栈的应用举例 栈在算法设计中占有重要的地位，运用的技巧也性也较高，本节安排五个例子来讨论栈的使用。23例一例一 数制数制转换例二例二 括号匹配的括号匹配的检验例三例三 背包求解背包求解例六例六 表达式求表达式求值例七例七 递归函数的函数的实现例四例四 编辑文本文本例五例五 迷迷宫问题24例一、数制转换算法基于数制转换公式：算法基于数制转换公式：N=(N div d)d+N mod d 25例如：（1348)10=(2504)8 其运算过程如下：N N div 8 N mod

8、 8 1348 168 4 168 21 0 21 2 5 2 0 2计算算顺序序输出出顺序序26void conversion()1.InitStack(S);2.cin N;3.while(N)4.Push(S,N%8);5.N=N/8;6.7.while(!StackEmpty(S)8.Pop(S,e);9.cout 0&k=0)/第k件物品可以进栈4.Push(S,k);T=wk;5.6.k+;7.8.if(T=0)StackTraverse(S);/输出一个解9.Pop (S,k);T+=wk;/退出栈顶物品10.k+;11.while(!StackEmpty(S)|k-/（#nex

9、t=NULL;return OK;79 Status EnQueue_L(LinkQueue&Q,QElemType e)/插入元素e为Q的新的队尾元素 p=(QueuePtr)malloc(sizeof(Qnode);if(!p)exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;80 Status DeQueue_L(LinkQueue&Q,QElemType&e)/若队列不空，则删除Q的队头元素，/用 e 返回其值,并返回TRUE；否则返回FALSE if(Q.front=Q.rear)return ERROR;p=Q.f

10、ront-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;#define MAXQSIZE 100 /最大最大队列列长度度 typedef struct QElemType *base;/动态分配存分配存储空空间 int front;/头指指针，若，若队列不空，列不空，/指向指向队列列头元素元素 int rear;/尾指尾指针，若，若队列不空，指向列不空，指向 /队列尾元素列尾元素 的下一个位置的下一个位置 SqQueue;循循环队列列顺序映象序映象82abc dQ.elemQ.fro

11、nteQ.rearQ.front:指向队头元素Q.rear:指向队尾下一元素队列的入队和出队操作：83e0 1 2 3 4 5 6 7Q.frontQ.rear初初态（空（空队）:Q.frontQ.rear队空空:当头尾指针重合时:队为空840 1 2 3 4 5 6 7acbQ.frontQ.rear队满状态的约定:acbQ.rear0 1 2 3 4 5 6 7Q.rearQ.fronta b c defg假满真满Q.rearQ.rear队满时还富裕一个富裕一个单元的空元的空间以区以区别“队空空”和和“队满”的的条件条件8501234567abcQ.rearQ.frontQ.reard循循

12、环队列列（按循环机制使用顺序空间）front和和rear都按都按逆逆时针操作操作86Q.rear=(Q.rear+1)Q.front=(Q.front+1)通过头尾指针的循环使用,顺序空间即可当循环空间来使用，称循环队。循环使用指针在技术上是由取模实现的：%MAXQSIZE;%MAXQSIZE;Status InitQueue(SqQueue&Q)/构造一个空构造一个空队列列Q Q.base=(ElemType*)malloc (MAXQSIZE*sizeof(ElemType);if(!Q.base)exit(OVERFLOW);/存存储分配失分配失败 Q.front=Q.rear=0;re

13、turn OK;Status EnQueue(SqQueue&Q,ElemType e)/插入元素插入元素e为Q的新的的新的队尾元素尾元素 if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;/队列列满 Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;Status DeQueue(SqQueue&Q,ElemType&e)/若若队列不空，列不空，则删除除Q的的队头元素，元素，/用用e返回其返回其值，并返回，并返回OK;否否则返回返回ERROR if(Q.front=Q.rear)return ERROR;

14、e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;903.4 队列的应用举例队列的应用举例利用循利用循环队列求列求二二项式系数式系数（杨辉三角）三角）91第第 1 行行 1 1第第 2 行行 1 2 1 第第 3 行行 1 3 3 1第第 4 行行 1 4 6 4 1二二项式系数式系数值（杨辉三角）三角）设第 i-1行的值：(a0=0)a1.ai(ai+1=0)则第 i 行的值：bj=aj-1+aj,j=1,2,i+100循循环队列使用例列使用例921 3 3 100 1 4 6 4 1展转相加求二项式系数0利用循环队列可以在有限的空

15、间里实现EnQueue(Q,e);DeQueue(Q,s);GetHead(Q,e);使用以下三个操作93do /输出一行 DeQueue(Q,s);GetHead(Q,e);if(e!=0)cout e;EnQueue(Q,s+e);while(e!=0);while(kn)/控制n行 EnQueue(Q,0);/插入分界符0 k+;coutendl;InitQueue(Q);EnQueue(Q,0);EnQueue(Q,1);EnQueue(Q,1);k=1;/行值初始化 94利用循环队列计算二项式的过程：假设只计算四行，则队列的最大容量为 6。1 1 00q.frontq.rear1 1

16、 001q.frontq.rear1 1 001q.frontq.rear1 1 011q.frontq.rear1 0 102q.frontq.rear1 0 102q.frontq.rear2211951 3 102q.frontq.rear1 3 302q.frontq.rear1 3 301q.frontq.reardo DeQueue(Q,s);GetHead(Q,e);if(e!=0)coute;EnQueue(Q,s+e);while(e!=0);11196本章学习要点本章学习要点97 1.掌掌握握栈和和队列列类型型的的特特点点，并并能能在在相相应的的应用用问题中正确中正确选用它

17、用它们。2.熟熟练掌握掌握栈类型型的两种的两种实现方法，特方法，特别应注意注意栈满和和栈空空的条件以及它的条件以及它们的描述方的描述方法。法。4.熟熟练掌握掌握循循环队列列和和链队列列的基本操作的基本操作实现算法，特算法，特别注意注意队满和和队空空的描述方法。的描述方法。3.理解理解递归算法算法执行行过程中程中栈的状的状态变化化过程。程。98迷宫问题迷宫问题栈的应用栈的应用v迷宫问题迷宫问题w是一个实验心理学的经典案例是一个实验心理学的经典案例w经过多次尝试老鼠找到一条最佳路径吃到经过多次尝试老鼠找到一条最佳路径吃到cheese99RatInAMaze100vMoveorderis:right

18、,down,left,upvBlockpositionstoavoidrevisit.RatInAMaze101vMoveorderis:right,down,left,upvBlockpositionstoavoidrevisit.RatInAMaze102vMovebackwarduntilwereachasquarefromwhichaforwardmoveispossible.RatInAMaze103vMovedown.RatInAMaze104vMoveleft.RatInAMaze105vMovedown.RatInAMaze106vMovebackwarduntilwereac

19、hasquarefromwhichaforwardmoveispossible.RatInAMaze107vMovebackwarduntilwereachasquarefromwhichaforwardmoveispossible.Move downward.RatInAMaze108vMoveright.Backtrack.RatInAMaze109vMovedownward.RatInAMaze110vMoveright.RatInAMaze111vMoveonedownandthenright.RatInAMaze112vMoveoneupandthenright.RatInAMaze

20、113vMovedowntoexitandeatcheese.vPathfrommazeentrytocurrentpositionoperatesasastack.RatInAMaze114迷宫问题迷宫问题v映射迷宫映射迷宫w用一个二维数组用一个二维数组mazeij来映射这个来映射这个迷宫迷宫w“1”代表一个不能通代表一个不能通过的墙过的墙w“0”代表可以通过代表可以通过的门的门v老鼠的行走方向老鼠的行走方向w已知老鼠的位置已知老鼠的位置Xij，下一步可走，下一步可走8个方向个方向，如右图。，如右图。114114115迷宫问题迷宫问题v为了避免查询边界条件，可为了避免查询边界条件，可以声明一

21、个以声明一个mazem+2p+2数组数组116迷宫问题迷宫问题v另一个方法另一个方法w预先将可能的方向定义在预先将可能的方向定义在表表move中，中，老鼠的移动标志表，如右图老鼠的移动标志表，如右图.w则需要定义一个结构体则需要定义一个结构体offsetsStructoffsetsinta,b;/坐标坐标y,xEnumdirections(N,NE,E,SE,S,SW,W,NW);Offsetsmove8;如如SW方向：方向：gh坐标：坐标：g=i+moveSW.a;h=j+moveSW.b117迷宫问题算法实现迷宫问题算法实现v设三个数组设三个数组wMazempwMarkm+2p+2-防止进

22、入防止进入同一条两次，初始为所有元素同一条两次，初始为所有元素为为“0”，当到达某位置设为，当到达某位置设为“1”wMove8-存放下步移动的徧存放下步移动的徧移量移量v定义一个三元组的定义一个三元组的items的的栈结构栈结构structitemsintx,y,dir;118templateclassStack/Bobjects:Afiniteorderedlistwithzeroormoreelements.friendostream&operator(ostream&,Stack&);public:Stack(intMaxStackSize=DefaultSize);BooleanIsF

23、ull();voidAdd(constKeyType&item);BooleanIsEmpty();KeyType*Delete(KeyType&);voidStackEmpty()coutemptyendl;voidStackFull()coutfullendl;voidOutput();private:inttop;KeyType*stack;intMaxSize;迷宫问题算法实现迷宫问题算法实现119templateostream&operator(ostream&os,Stack&s)ostop=s.topendl;for(inti=0;i=s.top;i+)osi:s.stackie

24、ndl;returnos;structoffsetsinta,b;enumdirectionsN,NE,E,SE,S,SW,W,NW;offsetsmove8;迷宫问题算法实现迷宫问题算法实现structitemsintx,y,dir;ostream&operator(ostream&os,items&item)returnositem.x,item.y,item.dir;120intmaze100100;intmark100100;voidpath(intm,intp)/Outputapath(ifany)inthemaze;maze0,i=mazem+1,i=/mazej,0=mazej,

25、p+1=1,0(=i(=p+1,0(=j(=m+1.ofstreamoutFile(stack.pos,ios:out);if(!outFile)cerrcannotopenstack.posforoutputendl;return;/startat(1,1)mark11=1;Stackstack(m*p);itemstemp;temp.x=1;temp.y=1;temp.dir=E;stack.Add(temp);迷宫问题算法实现迷宫问题算法实现121while(!stack.IsEmpty()/stacknotemptytemp=*stack.Delete(temp);/unstackin

26、ti=temp.x;intj=temp.y;intd=temp.dir;while(d8)/moveforwardoutFileijdendl;intg=i+moved.a;inth=j+moved.b;if(g=m)&(h=p)/reachedexit/outputpathcoutstack;coutijendl;coutmpendl;return;.迷宫问题算法实现迷宫问题算法实现if(!mazegh)&(!markgh)/newpositionmarkgh=1;temp.x=i;temp.y=j;temp.dir=d+1;stack.Add(temp);/stackiti=g;j=h;d

27、=N;/moveto(g,h)elsed+;/trynextdirectioncoutnopathinmazeendl;122voidmain()ifstreaminFile(maze.in,ios:in);if(!inFile)cerrcannotopenmaze.inforinputendl;return;moveN.a=-1;moveN.b=0;moveNE.a=-1;moveNE.b=1;moveE.a=0;moveE.b=1;moveSE.a=1;moveSE.b=1;moveS.a=1;moveS.b=0;moveSW.a=1;moveSW.b=-1;moveW.a=0;moveW

28、.b=-1;moveNW.a=-1;moveNW.b=-1;迷宫问题算法实现迷宫问题算法实现charch;for(inti=0;i14;i+)for(intj=0;jch;mazeij=ch-0;markij=0;for(inti=0;i=13;i+)for(intj=0;j=16;j+)coutmazeij;coutendl;path(12,15);123v时间复杂度：时间复杂度：最多为：最多为：O(mp)迷宫问题迷宫问题path算法分析算法分析124/-栈的的顺序存序存储表示表示-#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;t

29、ypedef struct SElemType *elem;int top;int stacksize;int increment;SqStack;125 void InitStack_Sq(SqStack&S)/构造一个空栈S S.elem=new SElemTypemaxsize;S.top=-1;S.stacksize=maxsize;S.incrementsize=incresize;126void Push_Sq(SqStack&S,SElemType e)if(S.top=S.stacksize-1)incrementStacksize(S);/如果顺序栈的空间已满，应为栈扩容 S.elem+S.top=e;/在栈顶插入数据元素127bool Pop_Sq(SqStack&S,SElemType&e)/若栈不空，则删除S的栈顶元素，/用e返回其值，并返回TRUE；/否则返回FALSE。if(S.top=-1)return FALSE;e=S.elemS.top-;return TRUE;