热门搜索:

  • /?70
  • 下载费用:1 金币 ?

计算机软件基础-第三章_堆栈和队列.ppt

关?键?词:
计算机软件 基础 第三 堆栈 队列
资源描述:
第三章 堆栈和队列,Chapter 3 Stack and Queue,3.1 堆栈(Stack),3.2 队列(Queue),1. 定义2. 逻辑结构3. 存储结构4. 运算规则5. 实现方式,1. 定义2. 逻辑结构3. 存储结构4. 运算规则5. 实现方式,本章内容,3.1 堆栈,一、堆栈的基本概念定义 堆栈是限定只能在表的一端进行插入和删除的线性表。在表中允许插入和删除的一端叫做栈顶(top);表的另一端则叫做栈底(base)。,Last In First Out,一般线性表逻辑结构:一对一存储结构:顺序表、链表运算规则:随机存取,堆栈逻辑结构:一对一存储结构:顺序栈、链栈运算规则:后进先出(LIFO),*堆栈与一般线性表的比较*,,例 一个栈的输入序列为123,若在入栈的过程中允许出栈,则可能得到的出栈序列是什么?,答:,可以通过穷举所有可能性来求解:① 1入1出, 2入2出,3入3出, 即123;② 1入1出, 2、3入,3、2出, 即132;③ 1、2入,2出, 3入3出,1出 即231;④ 1、2入,2、1出,3入3出, 即213;⑤ 1、2、3入,3、2、1出, 即321;合计有5种可能性。,* 不可能产生的输出序列:312,1、初始化2、进栈3、退栈4、取栈顶元素5、判栈是否非空,二、堆栈的操作,三、栈的顺序表示和实现——顺序堆栈,1. 顺序栈的存储结构,出栈或退栈,入栈或进栈,maxlen-1,543210,顺序栈的定义typedef int DataType;#define maxlen 100 /*顺序堆栈数组最大存储单元个数*/typedef struct /*顺序栈定义*/{ DataType stack[maxlen];/*顺序堆栈存放数据元素的数组*/ int top; /*顺序堆栈数组的当前栈顶位置*/} seqstack; /*结构类型名*/,2. 顺序堆栈的操作实现,,a0,,,a1,,a2,,,maxlen个,空栈,a0进栈,a1进栈,a2进栈,,a2出栈,,初始化参数:S是指向结构变量的指针;功能:建一个空栈S;void inistack(seqstack *s){ s->top=-1;},/*顺序堆栈数组的当前栈顶位置*/,判栈空操作参数:S是存放结构体变量的数组;功能:判断S是否为空,为空返回1,否则返回0;int empty(seqstack s){ if(s.top==-1) return 1; else return 0;},入栈功能:将数据元素x压入顺序堆栈S,入栈成功返回1,否则返回0int push(seqstack *s, DataType x){if (s->top==maxlen-1){printf(“\nStack is full”);return 0;}s->top++;s->stack[s->top]=x;return 1;},判栈满?,栈顶下标加1,入栈,s->stack[++s->top]=x;,出栈功能:弹出顺序堆栈s的栈顶数据元素值到参数d,出栈成功返回1,否则返回0,判栈空?,元素出栈,栈顶下标减1,else { *d= s->stack[s->top]; (s->top)- -; return 1; }},int pop(seqstack *s,DataType *d){ if(s->top==-1) { printf("\n Stack is empty!"); return 0; },*d=s->stack[s->top--];,取栈顶元素功能:取顺序堆栈s的当前栈顶数据元素值到参数d,成功返回1,否则返回0,int gettop(seqstack s,DataType *d){ if(s.top==-1) { printf(“\nStack is empty!”); return 0; }else { *d=s.stack[s.top]; return 1; }},堆栈算法练习,顺序栈的C语言描述:,typedef int elemtype;#define maxlen 10typedef struct{ elemtype stack[maxlen]; int top;}SeqStack;,写出堆栈的入栈和出栈算法,两个堆栈共享空间目的:节省空间,扩展知识——堆栈共用问题,两个堆栈共享空间的运算:初始化 进栈 出栈,数据结构定义:,typedef struct { DataType stack[maxlen]; int LeftTop; int RightTop; }dqstack;,初始化算法,void InitiDqstack(dqstack*s); { s->LeftTop=-1; s->RightTop=maxlen; },int PushDqstack(dqstack*s,char WhichStack,DataType x) {if (s->LeftTop>= s->RightTop-1) {printf(“栈满”); return 0;} if (WhichStack!=‘L’},进栈算法,X入左栈,X入右栈,共用堆栈的出栈算法:,自编。,共用堆栈的算法练习:,已知:一个双向堆栈stack[M](M自己定义),编写一个算法:要求从键盘输入数据,若输入的是奇数,则存入左栈;若输入的是偶数,则存入右栈,直到栈满为止。,,四、栈的链式存储结构,链式栈无栈满问题,空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头,链栈的结点定义typedef int DataType;typedef struct snode{ DataType data; struct snode *next;} LSNode;,,,,,,,,,int PushStack(LSNode *head, DataType x){ LSNode *p; if ((p=(LSNode*) malloc(sizeof(LSNode)))==NULL) {printf(“\n失败”); return 0;} p->data=x; p->next=head->next; head->next=p; return 1; },链栈的进栈算法,申请一个新结点,进栈,,x,,,,,,,,,,int PopStack(LSNode *head,DataType *d){ LSNode *p; p=head->next; if (p==NULL) {printf(“under flow\n”); return 0;} *d=p->data; head->next=p->next; free(p); return 1; } },链栈的出栈算法,判栈空,出栈,,*d,,,1:括号匹配问题 (参考P66例3-2) 设计思路:用栈暂存左括号2:数制转换(十转N) 设计思路:用栈暂存低位值3:汉诺(Hanoi)塔 设计思路:用栈实现递归调用4:表达式求值 设计思路:用栈暂存运算符,堆栈的应用,数制转换N = (N div d)×d + N mod d 例如:(1348)10 = (2504)8 ,其运算过程如下:,将余数依次进栈,再出栈,,N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2,汉诺( Hanoi)塔传说在创世纪时,在一个叫Brahma的寺庙里,有三个柱子,其中一柱上有64个盘子从小到大依次叠放,僧侣的工作是将这64个盘子从一根柱子移到另一个柱子上。当工作做完之后,就标志着世界末日到来。 移动时的规则: 每次只能移动一个盘子; 只能小盘子在大盘子上面; 可以使用任一柱子。,分析: 设三根柱子分别为x,y,z,盘子在x柱上,要移到z柱上。 1、当n=1时,盘子直接从x柱移到z柱上; 2、当n>1时,则①设法将前n–1个盘子借助z,从x移到y柱上,把盘子n移到z柱上; ②把n–1个盘子从y移到z柱上。,,,,,,,,,,,,,,,,,,,,,,,,,Y,X,Z,,表达式计算,表达式计算是编译系统中的一个重要问题,其实现方法是堆栈的一个典型应用。,中缀表达式:运算符总是出现在两个操作数之间(除单目运算符外);,后缀表达式:运算符出现在操作数之后。,例:A+B ? AB+,把一个中缀表达式变换成相应的后缀表达式要考虑运算规则。,中缀表达式:A + ( B – C / D) × E后缀表达式:ABCD/-E×+后缀表达式特点1、与相应的中缀表达式中的操作数次序相同2、没有括号,编译系统中表达式的计算分为两个步骤: (1)把中缀表达式变换为相应的后缀表达式; (2)根据后缀表达式计算表达式的值。,中缀表达式转换为后缀表达式的处理规则,1、如为操作数,直接输出到队列;2、如当前运算符高于栈顶运算符,入栈;3、如当前运算符低于栈顶运算符,栈顶运算符退栈,并输出到队列,当前运算符再与栈顶运算符比较;4、如当前运算符等于栈顶运算符,且栈顶运算符为“(”,当前运算符为“)”,则栈顶运算符退栈,继续读下一符号;5、如当前运算符等于栈顶运算符,且栈顶运算符为“#”,当前运算符也为“#”,则栈顶运算符退栈,表示运算结束;,当前运算符(a),,,栈顶运算 符(b),运算符优先级关系,后缀表达式的处理过程,A,B,C,D,,A,B,T1,,A,T2,E,A,T3,T4,,,ABCD/ -E×+,/,top,,,T1=C/D,,ABCD/ -E×+,,-,,T2= B- T1,×,,T3= T2 ×E,+,,T4= A+T2,ABCD/ -E×+,,ABCD/ -E×+,,小 结,理解:堆栈,栈顶,栈底,栈满,栈空,顺序栈,链栈。 掌握:初始化,入栈,出栈,取栈顶元素的算法。(顺序栈,链栈) 应用:表达式求值。,作业:p87 3-6,3-13,补充题:一个双向堆栈stack[M](M自己定义),编写一个算法:要求从键盘输入数据,若输入的是奇数,则存入左栈;若输入的是偶数,则存入右栈,直到栈满为止。,3.2 队列,一、队列的基本概念定义 队列是一种特殊的线性表。在队列中,仅允许在一端进行插入,在另一端进行删除。,队列又称先进先出(First In First Out, FIFO)表。,允许插入的一端叫做队尾(rear);允许删除的一端叫做队头(front)。,二、队列的基本操作,1、初始化队列2、判定队列是否为空3、取队列头元素4、入队列(将新元素插入队尾)5、出队列(队列头元素出队),三、队列的顺序存储结构,顺序队列的定义#define maxlen 100typedef int DataType;typedef struct{ DataType queue[maxlen]; int front , rear ;} sequeue;,队列的进队和出队,空队列,,5,4,3,2,1,0,front==0 && rear==0,A入队列,D,B、C入队列,B,C,A、B出队列,D、E、F入队列,E,F,A,rear==maxlen,此时不能再入队,入队时先将新元素按 rear 指示位置加入,再使队尾指针加一 rear = rear + 1。 出队时先将下标为 front 的元素取出,再使队头指针进一 front = front + 1。 队满时再进队将溢出出错;队空时再出队将队空出错。,顺序队列的假溢出,问:什么叫“假溢出” ?如何解决?,答:在顺序队列中,当尾指针已经超出数组的上界,不能再有入队操作,但其实数组中还有空位置,这就叫“假溢出”。,解决假溢出的途径—采用循环队列,5,4,3,2,1,0,D,C,E,F,,循环队列的表示和实现,1. 基本原理: a.当rear和front达到maxlen-1后,再前进一个位置就自动到0。 b.如何实现: 用求模运算,rear=(rear+1)%maxlen,,顺序队列,,,a2,a1,a0,,,,,,,,,,,,,,,front,rear,0 1 2 3 . .N-1,队头指针进1: front = (front + 1) % maxlen; 队尾指针进1: rear = (rear + 1) % maxlen;队列初始化:front = =0,2. 队空和队满的判断:,队空:front==rear;队满:front==rear;,两种状态怎样区分?,,a.设置一个标志位。队满: front==rear&&tag==1;队空: front==rear&&tag==0; b.设置一个计数器。队满:count>0&& front==rear;队空:count==0;c.少用一个存储单元。队满: (rear+1)%maxlen==front队空:front==rear;,void iniqueue(sequeue *sq){ sq->front=0; sq->rear=0;},循环队列的初始化,/*队头指针*/,/*队尾指针*/,int addqueue(sequeue *sq,DataType x){if (sq->front==(sq->rear+1)%maxlen){printf(“\nQueue is full”);return 0;}sq->queue[sq->rear]=x;sq->rear=(sq->rear+1)%maxlen;return 1; },循环队列的入队列,判断是否队满,队尾指针后移,元素入队,int delqueue(sequeue *sq, DataType *d){if(sq->front==sq->rear){printf("\n Queue is empty!");return 0;}*d=sq->queue[sq->front];sq->front=(sq->front+1)%maxlen;return 1; },循环队列的出队列,队头指针后移,元素出队,判断是否队空,四、队列的链式存储结构,队列的链式存储结构,队头在链头,队尾在链尾。链式队列在进队时无队满问题,但有队空问题。队空条件为 front ->next== NULL 或 front==rear,链队列的结构体定义,typedef struct slnode{ DataType data; struct slnode *next;} LQNode;,typedef struct{ LQNode *front; LQNode *rear;} LQueue;,初始化,int InitiateSLQueue(LQueue *q){ if((q->front=(LQNode*)malloc(sizeof(LQNode)))==NULL) { printf(“\n申请空间失败!”); return 0; } q->rear=q->front; q->front->next=NULL; return 1; },链队列的入队示意,130A,,1475,,,,,,,,,,链队列的入队算法,X,∧,int addq (LQueue *q,DataType x){LQNode *p; if ((p=(LQNode* ) malloc(sizeof(LQNode)))==NULL) {printf (“\n申请空间失败!”); return 0;} p->data=x; p->next=NULL; q->rear->next=p; q->rear=p; return 1; },链队列的出队,,130A,,,,a0,int delqueue (LQueue *q,DataType *d){ LQNode *p; if (q->front->next==NULL) return 0; p=q->front->next; *d=p->data; q->front->next=p->next; free(p);return 1;},链队列的出队算法,,,问题描述:编程序判断一个字符序列是否是回文,基本要求: 1> 字符序列个数 n可由用户自定义. 2> 可连续测试任意多个字符序列,由用户决定退出 3> 字符序列由用户从键盘输入,测试数据:1> abcdcba 2> abcdefg,字符序列先分别入队和进栈,再逐个出队和退栈进行比较,模块划分: 1> Panduan(char str[],int n) 2> EnterStr(char str[],int *n) 3> main(),数据结构: 1> 顺序堆栈抽象数据类型 2> 顺序队列抽象数据类型,算法思想:,#include #include #define MAXNUM 80 typedef char elemtype;,typedef struct{ elemtype stack[MAXNUM]; int top;} qstype;,typedef struct{ elemtype queue[MAXNUM]; int front,rear;} qqtype;,参考源程序:,,,main(){ char ch,str[MAXNUM]; int n; while(1) { EnterStr(str, } },,void EnterStr(char str[],int *n){ printf("输入字符串:"); scanf("%s",str); *n=strlen(str);},,,int Panduan(char str[],int n) { qstype myStack; qqtype myQueue; char x,y; int i; StackInitiate( },,,while(QueueNotEmpty(},StackInitiate(qstype *s) { s->top=-1; } int StackPush (qstype *s,elemtype x) { if(s->top>=MAXNUM-1) return 0; else { s->stack[++(s->top)]=x; return 1; } },,int StackPop (qstype *s,elemtype *y) { *y=s->stack[(s->top)]; (s->top) --; return 1; } int StackNotEmpty (qstype *s) { if(s->top<0) return 0; return 1; },QueueInitiate(qqtype *q){ q->front=0; q->rear= 0;} int QueueAppend (qqtype *q,elemtype x){ if(q->rear>=MAXNUM-1) return 0; q->queue[ (q->rear) ++]=x; return 1;},,int QueueDelete (qqtype *q,elemtype *x){ *x=q->queue[ (q->front) ++]; return 1; }int QueueNotEmpty (qqtype *q){ if(q->rear==q->front) return 0; return 1; },测试结果: abcdcba 是回文! abcdefg 不是回文!,线性表、栈与队列的异同点相同点:逻辑结构相同,都是线性的;都可以用顺序存储或链表存储;栈和队列是两种特殊的线性表,即受限的线性表(只是对插入、删除运算加以限制)。不同点:① 运算规则不同,线性表为随机存取,而栈是只允许在一端进行插入和删除运算,因而是后进先出表LIFO;队列是只允许在一端进行插入、另一端进行删除运算,因而是先进先出表FIFO。② 用途不同,线性表比较通用;堆栈用于元素的保存次序与使用顺序相反的情况;队列用于元素的保存次序与使用顺序相同的情况。,小 结,理解:队列,队头,队尾,顺序队列,链式队列。 掌握:初始化,入队,出队的算法(顺序循环队列,链式队列),队空、队满的判断。 应用:回文判断,医院就诊等。,作业:p88 3-2,3-11,
? 汽车智库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:计算机软件基础-第三章_堆栈和队列.ppt
链接地址:http://www.autoekb.com/p-1561.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2008-2018 mywenku网站版权所有
经营许可证编号:京ICP备12026657号-3?

收起
展开