数据结构第3章栈和队列ppt课件

《数据结构第3章栈和队列ppt课件》由会员分享，可在线阅读，更多相关《数据结构第3章栈和队列ppt课件（40页珍藏版）》请在装配图网上搜索。

1、 第3章 栈和队列3.1栈的概念 3.2栈的存储构造3.3顺序栈的操作算法 3.4链栈的操作算法 3.5栈的运用举例-表达式求值 第3章 栈和队列3.6队列的概念 3.7队列的存储构造 3.8循环队列的操作算法 3.9链队的操作算法 第三章第三章 栈和队列栈和队列 3.1栈的概念栈的概念1.定义：定义：栈栈(Stack)是限定仅在表的一端进展插入或删是限定仅在表的一端进展插入或删除操作的线性表。除操作的线性表。2.栈的表示图栈的表示图 P443.栈的笼统数据类型定义栈的笼统数据类型定义 P453.2 栈的存储构造栈的存储构造有两种存储构造有两种存储构造:顺序栈常用；顺序栈常用；链栈链栈1、顺序

2、栈、顺序栈 顺序栈的类型定义：顺序栈的类型定义：/-栈的顺序存储表示栈的顺序存储表示-#define STACK_NINT_SIZE 100;/存储空间初始分配量存储空间初始分配量#define STACKINCREMENT 10;/存储空间分配增量存储空间分配增量typedef struct SElemType*base;/在栈构造之前和销毁之后，在栈构造之前和销毁之后，base的值为的值为NULL SElemType*top;/栈顶指针栈顶指针 int stacksize;/当前已分配的存储空间，以元素为单位当前已分配的存储空间，以元素为单位SqStack顺序栈的构造举例顺序栈的构造举例/

3、-根本操作的函数原型阐明根本操作的函数原型阐明-Status InitStack(SqStack&S);/构造一个空栈构造一个空栈SStatus GetTop(SqStack S,SElemType&e);/假设栈不空，那么用假设栈不空，那么用e前往前往S的栈顶元素，并前往的栈顶元素，并前往OK；否那么；否那么前往前往ERRORStatus Push(SqStack&S,SElemType e);/插入元素插入元素e为新的栈顶元素为新的栈顶元素Status Pop(SqStack&S,SElemType&e);/假设栈不空，那么删除假设栈不空，那么删除S的栈顶元素，用的栈顶元素，用e前往其值，

4、并前往前往其值，并前往OK；否那么前往；否那么前往ERROR 2、链栈、链栈 链栈的类型定义：链栈的类型定义：typedef struct LNode/typedef struct LNode/结点类型结点类型 ElemType data;ElemType data;struct LNode struct LNode*next;next;Lnode,Lnode,*Linkstack;Linkstack;Linkstack S;Linkstack S;3.3 顺序栈的操作算法顺序栈的操作算法 1建立一个空栈建立一个空栈Status InitStack(SqStack&S)/构造一个空栈构造一个空

5、栈S S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(overflow);/存储分配失效存储分配失效 S=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStack2.取栈顶元素取栈顶元素Status GetTop(SqStack S,SElemType&e)/假设栈不空，那么用假设栈不空，那么用e前往前往S的栈顶元素，的栈顶元素，并前往并前往OK；否那么前往；否那么前往ERROR if(S=S.base)return ERROR;e=*(

6、S-1);return OK;/GetTop 3.压栈压栈pushStatus Push(SqStack&S,SElemType e)/插入元素插入元素e为新的栈顶元素为新的栈顶元素 if(S-S.base=S.stacksize)/栈满，追加存储空间栈满，追加存储空间 S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)exit(OVERFLOW);/存储分配失败存储分配失败 S=S.base+S.stacksize;S.stacksize+=STACKINCR

7、EMENT;*S+=e;return OK;/push 4.出栈出栈popstatus Pop(SqStack&S,SElemType&e)/假设栈不为空，那么删除假设栈不为空，那么删除S的栈顶元素，用的栈顶元素，用e前往其值，前往其值，并前往并前往OK；否那么前往；否那么前往ERROR if(S=S.base)return ERROR;e=*-S;return OK;/Pop 5 判别栈能否为空判别栈能否为空int Empty(SqStack S)/假 设 栈 为 空，那 么 前 往假 设 栈 为 空，那 么 前 往 0，否 那 么 前 往，否 那 么 前 往 1 i f(s=s.b a s

8、 e)r e t u r n (0);else return(1);6 判别栈能否为满判别栈能否为满int Full(SqStack S)/假 设 栈 为 满，那 么 前 往假 设 栈 为 满，那 么 前 往 0，否 那 么 前 往，否 那 么 前 往 1 i f(s-s.b a s e)=s.s t a c k s i z e r e t u r n (0);else return(1);3.4 链栈的操作算法链栈的操作算法 自学自学1.建立一个空栈不带头结点建立一个空栈不带头结点Status InitLStack(Linkstack&S)S=NULL;return ok;/InitLSta

9、ck2.2.取栈顶元素取栈顶元素Status GettopLStack(Linkstack&S,SElemType&e)Status GettopLStack(Linkstack&S,SElemType&e)/假设栈不为空，那么用假设栈不为空，那么用e e前往前往S S的栈顶元素，并前往的栈顶元素，并前往OK,OK,否那么前往否那么前往ERROR.ERROR.i f(S=N U L L)r e t u r n E R R O R;i f(S=N U L L)r e t u r n E R R O R;e=S-data;e=S-data;return(OK);return(OK);/Gettop

10、LStack/GettopLStack 3.3.压栈压栈PushPushStatus PushLStack(Linkstack&S,SElemType e)Status PushLStack(Linkstack&S,SElemType e)/插 入 元 素插 入 元 素 e e 为 新 的 栈 顶 元 素为 新 的 栈 顶 元 素Lnode Lnode*p;p;p=(Lnode p=(Lnode*)malloc(sizeof(Lnode);)malloc(sizeof(Lnode);p-data=e;p-data=e;p-next=S;p-next=S;S=p;S=p;/PushLStack/

11、PushLStack 4.4.出栈出栈PopPopStatus PopLStack(Linkstack&S,SElemType&e)Status PopLStack(Linkstack&S,SElemType&e)/假设栈不为空，那么删除假设栈不为空，那么删除S S的栈顶元素，的栈顶元素，用用e e前往其值，并前往前往其值，并前往OKOK，否那么前往，否那么前往ERROR ERROR i f(s=N U L L)r e t u r n E R R O R;i f(s=N U L L)r e t u r n E R R O R;e=S-data;e=S-data;S=S-link;S=S-lin

12、k;return OK;return OK;/PopLStack/PopLStack 5.判别栈能否为空判别栈能否为空int link_empty(Linkstack&S)/假设栈为空那么前往假设栈为空那么前往1，否那么前往，否那么前往0 if(S=NULL)return(1);else retrun(0);3.5 3.5 栈的运用举例栈的运用举例1-1-数制转换数制转换l非负十进制整数转换非负十进制整数转换为八进制数为八进制数l 1348D 2504ON N DIV 8N MOD 81348168416821021252023.5 3.5 栈的运用举例栈的运用举例2-2-表达式求值表达式求值

13、算法的根本思想是：算法的根本思想是：1 1首先置操作数栈为空栈，表达式起始符首先置操作数栈为空栈，表达式起始符“#为为运算符的栈底元素；运算符的栈底元素；2 2依次读入表达式中每个字符，假设是操作数那么进依次读入表达式中每个字符，假设是操作数那么进OPNDOPND栈，假设是运算符，那么和栈，假设是运算符，那么和OPTROPTR栈的栈顶运算符栈的栈顶运算符比较优符后作相应操作，直至整个表达式求值终了比较优符后作相应操作，直至整个表达式求值终了即即OPTROPTR栈的栈顶元素和当前读入的字符均为栈的栈顶元素和当前读入的字符均为“#。算法描画：算法描画：p53-54 p53-54 算法算法3.4 3

14、.4 表达式求值举例：计算表达式求值举例：计算3 3*(7-2)(7-2)步骤步骤OPTR栈栈OPND栈栈输入字符输入字符主要操作主要操作说明说明13*(7-2)#push(opnd,3)323*(7-2)#push(optr,*)3 *3*3 (7-2)#push(optr,()*(4*(3 7-2)#push(opnd,7)7为操作数为操作数5*(37 -2)#push(optr,-)()8*(35 )#pop(optr)(=)9*35#operate(3,*,5)*#1015#返回返回15 3.63.6队列的概念队列的概念1 1、定义：队列是一种先进先出、定义：队列是一种先进先出FIFO

15、FIFO：First First In First Out)In First Out)的线性表。它只允许在表的一端的线性表。它只允许在表的一端进展插入，而在另一端删除元素。进展插入，而在另一端删除元素。2 2、表示图、表示图 3、队列的笼统数据类型定义、队列的笼统数据类型定义 队列的笼统数据类型定义：队列的笼统数据类型定义：ADT Queue 数据对象：数据对象：D=ai|aiElemSet,i=1,2,.,n,n0 数据关系：数据关系：R1=|ai-1,aiD,i=2,.,n 商定其中商定其中a1端为队列头端为队列头,an为队列尾。为队列尾。根本操作：根本操作：InitQueue(&Q)操作

16、结果：构造一个空队列操作结果：构造一个空队列Q。DestroyQueue(&Q)ADT Queue4、双端队列a 定义：双端队列是限定插入和删除操作在表的两端进展的线性表。b 双端队列的表示图3.7队列的存储构造队列的存储构造3.8循环队列的操作算法循环队列的操作算法 1、循环队列的根本思想：、循环队列的根本思想：在顺序队列中，头指针在顺序队列中，头指针front一一直指向队列头元素，而尾指针直指向队列头元素，而尾指针rear一直指向队列尾元素的下一个位置，一直指向队列尾元素的下一个位置，随着进队、出队操作的进展，有能随着进队、出队操作的进展，有能够会出够会出rear指针已到达队列存储空指针已

17、到达队列存储空间的终点，而队列的实践可用空间间的终点，而队列的实践可用空间并未占满景象。为了防止这种景象并未占满景象。为了防止这种景象的发生，一个巧妙的方法是将顺序的发生，一个巧妙的方法是将顺序队列臆造为一个环状空间，称之为队列臆造为一个环状空间，称之为循环队列。循环队列。如下图：如下图：2、循环队列的队空队满条件、循环队列的队空队满条件 为了方便起见，商定：初始化建空队时，令为了方便起见，商定：初始化建空队时，令 front=rear=0,当队空时：当队空时：front=rear 当队满时：当队满时：front=rear 亦成立亦成立 因此只凭等式因此只凭等式front=rear无法判别队空

18、还是队满。无法判别队空还是队满。有两种方法处置上述问题：有两种方法处置上述问题：1另设一个标志位以区别队列是空还是满。另设一个标志位以区别队列是空还是满。2少用一个元素空间，商定以少用一个元素空间，商定以“队列头指针队列头指针 front在队尾指针在队尾指针rear的下一个位置上作为队列的下一个位置上作为队列“满形状的标志。即：满形状的标志。即：队空时：队空时：front=rear 队满时：队满时：(rear+1)%maxsize=front 3、循环队列的类型定义：、循环队列的类型定义：/-循环队列循环队列-队列的顺序存储构造队列的顺序存储构造-#define MAXQSIZE 100/最大

19、队列长度最大队列长度typedef struct QELemType*base;/初始化的动态分配存储空初始化的动态分配存储空间间 int front;/头指针头指针(下标下标)，假设队列不空，假设队列不空，指向队列头元素指向队列头元素 int rear;/尾指针尾指针(下标下标)，假设队列不空，假设队列不空，指向队列尾元素的下一个位置指向队列尾元素的下一个位置SqQueue;4、建立空的循环队列的算法、建立空的循环队列的算法Status InitQueue(SqQueue&Q)/构造一个空队列构造一个空队列Q Q.base=(QElemType*)malloc(MAXQSIZE *sizeo

20、f(QElemType);if(!Q.base)exit(OVERFLOW);/存储分配失败存储分配失败 Q.front=Q.rear=0;return OK;5、求循环队列中元素的个数、求循环队列中元素的个数int QueueLength(SqQueue Q)/前往前往Q的元素个数，即队列的长度的元素个数，即队列的长度 return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;求循环队列中元素的个数举例求循环队列中元素的个数举例(参考图参考图3.14Q.REAR Q.FRONT队列长度队列长度MAXSIZE00063456152610166、进队算法、进队算法Sta

21、tus EnQueue(SqQueue&Q,QElemType e)/插入元素为插入元素为Q的新的队尾元素的新的队尾元素 if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;/队列满队列满 Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;7、出队算法、出队算法Status DeQueue(SqQueue&Q,QElemType&e)/假设队列不空，那么删除假设队列不空，那么删除Q的队头元素，的队头元素，用用e前往其值，并前往前往其值，并前往OK；否那么前往；否那么前往ERROR if(Q.front=Q.

22、rear)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;3、9 链队的操作算法链队的操作算法 1、链队的类型定义、链队的类型定义/-单链队列单链队列-队列的链式存储构造队列的链式存储构造-typedef struct QNode QElemType data;struct QNode*next;QNode,*QueuePtr;typedef struct QueuePtr front;/队头指针队头指针 QueuePtr rear;/队尾指针队尾指针LinkQueue;2、建立空的链队、建立空的链队Sta

23、tus InitQueue(LinkQueue&Q)/构造一个空队列构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;return OK;3、进队算法、进队算法Status EnQueue(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;return OK;4、出队算法、出队算法Status DeQueue(LinkQueue&Q,QElemType&e)/假设队列不空，那么删除假设队列不空，那么删除Q的队头元素，的队头元素，用用e前往其值，并前往前往其值，并前往OK；否那么前往；否那么前往ERROR if(Q.front=Q.rear)return ERROR;p=Q.front-nxet;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;