《ch3栈和队列培训资料》由会员分享，可在线阅读，更多相关《ch3栈和队列培训资料（83页珍藏版）》请在金锄头文库上搜索。
1、2020/8/20,第3章,1,第3章 栈和队列,2020/8/20,第3章,2,上讲主要内容,线性表 顺序表 单链表,循环链表,双链表,2020/8/20,第3章,3,栈和队列内容,3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列,从数据结构的角度 操作受限的线性表 从数据类型的角度 抽象数据类型，不同于线性表,栈的常用运算,置空栈完成对栈的初始化。 判断栈空若栈S为空则返回真，否则返回假。 进栈Push(S，e)，在栈S的栈顶插入数据元素 e。 出栈Pop(S)，删除栈S的栈顶数据元素，并将数据元素返回。 取栈顶元素GetTop(S)，取栈S的栈顶数据元素，并把数据元
2、素返回。该操作完成后，栈的状态不变。,2020/8/20,第3章,6,2. 栈的表示和实现,1）顺序栈栈的顺序存储结构 2）链栈栈的链式存储结构 3）静态分配整型指针,2020/8/20,第3章,7,1）顺序栈栈的顺序存储结构,限定在表尾进行插入和删除操作的顺序表 指针类型定义: (p46) typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; SqStack s;,2020/8/20,第3章,8,说明：,base称为栈底指针，始终指向栈底； 当base = NULL时，表明栈结构不存在。 top为栈顶指
3、针（所指单元为空） a. top的初始值指向栈底，即top=base b. 空栈：当top=base时为栈空的标记 c. 当栈非空时，top的位置：指向当前栈 顶元素的下一个位置 stacksize 当前栈可使用的最大容量,2020/8/20,第3章,9,进栈示例,base,base,base,base,base,stacksize,2020/8/20,第3章,10,退栈示例,base,base,base,base,base,2020/8/20,第3章,11,几点说明：,栈空条件：s. top =s. base 此时不能出栈 栈满条件：s.top-s.base=s.stacksize 进栈操作
4、：*s.top+=e; 或*s.top=e; s.top+; 退栈操作：e=*-s.top； 或s.top-； e=*s.top； 当栈满时再做进栈运算必定产生空间溢出， 简称“上溢”; 当栈空时再做退栈运算也将产生溢出，简 称“下溢”。,2020/8/20,第3章,12,基本操作的实现,栈的初始化操作 p47 Status InitStack(SqStack struct SNode *next; SNode, *LinkStack; LinkStack s;,2020/8/20,第3章,18,链栈示意图 p47 图3.3 栈空条件： s=NULL 栈满条件： 无 / 无Free Memor
5、y可申请,2020/8/20,第3章,19,进栈操作：,Status Push_L (LinkStack ,2020/8/20,第3章,20,退栈操作,Status Pop_L (LinkStack ,2020/8/20,第3章,21,3）静态分配整型指针,定义 #define MAXSIZE 100 typedef struct SElemType baseMAXSIZE; int top; SqStack; SqStack s;,2020/8/20,第3章,22,初始化,status InitStack(SqStack ,2020/8/20,第3章,23,进栈,Status Push(Sq
6、Stack ,2020/8/20,第3章,24,退栈,Status Pop(SqStack ,2020/8/20,第3章,25,取栈顶元素,Status GetTop(SqStack s, SElemType ,2020/8/20,第3章,26,3.2 栈的应用,1. 数制转换 p48 算法3.1 2. 行编辑程序 p50 算法3.2 3. 表达式求值 p52 p54 4. 地图染色问题,2020/8/20,第3章,27,1. 数制转换 p48,十进制N和其它进制数的转换是计算机实现计算 的基本问题，基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod
7、为求余运算) 例如 (1348)10=(2504)8，其运算过程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,低位,高位,2020/8/20,第3章,28,算法3.1,要求：输入一个非负十进制整数，输出任意进制数 void Conversion() InitStack(s); scanf (“%”,n); while(n) push(s,n%8); n=n/8; while(! Stackempty(s) pop(s,e); printf(“%d”,e); ,2020/8/20,第3章,29,2. 行编辑程序 p50 算法3.2（
8、自学）,void lineedit( ) initstack(s); ch=getchar( ); while(ch!=eof) while(ch!=eof ,2020/8/20,第3章,30,3. 表达式求值 p52 p54,算符间的优先级关系 p52 p53 先括弧内后括弧外 左括号：比括号内的算符的优先级低 比括号外的算符的优先级高 右括号：比括号内的算符的优先级低 比括号外的算符的优先级高 #：优先级总是最低 为实现算符优先算法，可使用两个工作栈： OPND栈：存数据或运算结果 OPTR栈：存运算符,2020/8/20,第3章,31,算法思想：,1.初态： 置OPND栈为空；将“#”作
9、为OPTR栈的栈底元素 2.依次读入表达式中的每个字符 1）若是操作数，则进入OPND栈； 2）若是运算符，则与OPTR栈的栈顶运算符进行优先权（级）的比较： 若读入运算符的优先权高，则进入OPTR栈； 若读入运算符的优先权低，则OPTR退栈（退出 原有的栈顶元素），OPND栈退出两个元素 （先退出b，再退出a），中间结果再进入OPND栈； 若读入“）”，OPTR栈的原有栈的栈顶元素若为 “（”，则OPTR退出“（”； 若读入“#”，OPTR栈栈顶元素也为“#”，则OPTR栈退出“#”，结束。,2020/8/20,第3章,32,例：3*（7-2）,地图染色问题,四色定理是指可以用不多于四种颜色
10、对地图着色，使相邻的行政区域不重色。 问题：假设已知地图的行政区如图所示，对每个行政区编号分别是(1)、(2)、(3)、(4)、(5)、(6)、(7)。同时用1#、2#、3#、4#表示各行政区的颜色。,主要数据结构,数据结构 行政区域间的相邻关系矩阵Rnn： 1 行政区域i+1和j+1间是相邻的；Rij= 0 行政区域i+1和j+1间是不相邻的； 记录行政区域的所染颜色的序号栈S ： Si=k 表示行政区域i+1所染颜色的序号为k。,地图染色中的R矩阵和栈S的变化过程,地图染色,void mapcolor (int R, int n, int S) int color，area，k； S0=1
11、; area=1; color=1; while (arean) while (color=4) k=0; while (karea) /* while (color=4) end */,if (color4) area-=1; color=sarea+1; /* area区域找不到合适颜色 */ /* 回溯并修改area-1区域所用颜色 */,2020/8/20,第3章,37,3.4 队列,1. 定义 2. 链队列-队列的链式存储结构 3. 循环队列-队列的顺序存储结构,2020/8/20,第3章,38,1. 定义,是限定在表的一端进行删除，在表的另一端进行插入操作的线性表。 队头(fron
12、t)允许删除的一端 队尾(rear)允许插入的一端 特性：FIFO(First In First Out) 图示 p59,表头,表尾,队列的基本运算,队列的基本运算有： SetNull(Q): 置Q为一个空队列。 Empty(Q): 判队列Q是否为空队列。当Q是空队列时，返回“真”值，否则返回“假”值。 Front(Q): 取队列Q的队头元素，队列中元素保持不变。 Enqueue(Q,X): 将元素X插入队列Q的队尾。简称为入队(列)。 Dequeue(Q): 删除队列Q的队头元素，简称为出队(列)。函数返回原队头元素。,2020/8/20,第3章,40,双端队列（deque） 输出受限（1个
13、端只允许进） 输入受限（1个端只允许出） 从某端进，则只能从该端出 （相当于栈底相邻的栈）,固定？,2020/8/20,第3章,41,2. 链队列队列的链式存储结构,实质是带头结点的线性链表； 两个指针： 队头指针Q.front指向头结点 队尾指针Q.rear指向尾结点 初始态：队空条件 头指针和尾指针均指向头结点 Q.front = Q.rear,2020/8/20,第3章,42,1）链队列的类型定义 p61,typedef struct QNode /元素结点 QElemType data; struct QNode *next; QNode, *QueuePtr; typedef str
14、uct /特殊结点 QueuePtr front; /队头指针 QueuePtr rear;/队尾指针 LinkQueue; LinkQueue Q; Q.front指向头结点 Q.rear 指向链尾结点,2020/8/20,第3章,43,2）链队列示意图 p61图3.10,2020/8/20,第3章,44,队列运算指针变化状况,空队列,2020/8/20,第3章,45,3）基本操作与实现,初始化 p62 Status InitQueue (LinkQueue return FALSE; ,判断链队列是否为空,2020/8/20,第3章,51,Status GetHead(LinkQueue
15、Q,QElemType ,取链队列的第一个元素结点,2020/8/20,第3章,52,3. 循环队列队列的顺序存储结构,顺序队列： 用一组地址连续的存储单元依次存放从队列头到队列尾的元素 设两个指针： Q.front 指向队列头元素； Q.rear 指向队列尾元素的下一个位置 初始状态（空队列）： Q.front = Q.rear=0 队列的真满与假满,2020/8/20,第3章,53,类型定义 p64,#define MAXSIZE 100 typedef struct QElemType *base; int front; int rear; SqQueue; SqQueue Q;,2020/8/20,第3章,54,队列的进队和出队,进队时，将新元素按Q.rear 指示位置加入，再将队尾指针增1， Q.rear = Q.rear + 1 。 出队时，将下标为Q.front 的元素取出，再将队头指针增1， Q.front = Q.front + 1 。 队满时再进队将溢出出错；队空时再出队作队 空处理。上图为“假满”,2020/8/20,第3章,55,存储队列的数组被当作首尾相接的表处理。 队头、队尾指针加1时从maxSize -1直接进到0，可用语言的取模(余数)运算实现。 队头指针进1: Q.front = (Q.front + 1)% M
