《特殊线性表课件》由会员分享，可在线阅读，更多相关《特殊线性表课件（65页珍藏版）》请在金锄头文库上搜索。
1、1,第三章 特殊线性表,2,本章目录,3,3.1 栈,4,栈 ( Stack )的定义,定义:限制只能在表的一端进行插入和删除的线性表。 允许插入和删除的一端,称为栈顶(top)。 不允许插入和删除的另一端，称为栈底(bottom)。 把一个元素从栈顶放入栈中的操作，称为进栈、入栈或压栈 (push) 从栈顶取出一个元素的操作称为出栈或弹出(pop)。,5,a1,a2,a3,入栈,出栈,插入：入栈、进栈、压栈 删除：出栈、弹栈,入 栈,6,栈的操作特性：后进先出,a1,a2,a3,入栈,出栈,插入：入栈、进栈、压栈 删除：出栈、弹栈,出 栈,7,ADT Stack 数据对象： D ai | a
2、i ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。,基本操作：, ADT Stack,栈的抽象数据类型定义,.,8,InitStack( basetop-元素,basetop出 top-;,11,定义： template class SqStack private： T *base； /栈底指针 int top； /栈顶 int stacksize； /栈容量 public： ；,顺序栈的定义与实现, ,12,SqStack (int m)； /构建函数 SqStack ( )； /析构函数 voi
3、d Push (T x)； /入栈 T Pop ( )； /出栈 T GetTop ( )； /获取栈顶元素 int StackEmpty ( )； /测栈空 void ClearStack ( )； /清空栈 void StackTop ( )； /返回栈顶指针 void StackTranverse ( )； /显示栈中元素,顺序栈成员函数,13,创建顺序栈,算法3.1,操作步骤： / 创建栈 /S1:申请栈空间,template SqStack：SqStack(int m) base = new Tm； if (base = = NULL) exit(1)； stacksize = m；
4、 top=-1； ,算法描述,/S2：申请成功，给栈属性赋初值,/申请失败，退出,m,stacksize,初始化工作可在构造函数中实现。,14,顺序栈入栈算法,算法3.2,操作步骤： /入栈,template void SqStack：Push (T x ) if (top = = stacksize-1) throw 栈满，无法入栈； top+； basetop=x； ,算法描述：,/S3：元素入栈顶,/ S2：栈顶指针增1,/S1：栈满，不能入栈,X,15,顺序栈出栈算法,算法3.3,操作步骤： / 出栈,template T Sq_Stack：Pop() if ( top = = -1)
5、 throw “栈空，不能出栈”； x = basetop-； return x； ,/S4：返回出栈元素,/S2：栈顶元素出栈 /S3：栈顶指针减一,算法描述：,X,/S1：空栈，不能出,16,取栈顶元素算法,取栈顶元素操作是取出栈顶元素，但不改变栈。,算法3.4,X,操作步骤：,算法描述： template T SqStack：GetTop() if ( top = = -1 ) throw 栈空，栈顶无元素； return basetop； ,/ S2：返回栈顶元素,/ S1：栈空，栈顶没有元素,/获取栈顶元素,17,栈的链式存储及实现,栈的链式存储结构称为链栈(linked stack
6、)。,a. 链栈结构示意,b. 入栈,c.出栈,18,栈顶,栈底,链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 适合于多栈操作,链栈特点,an,an-1,a1,19,链栈的结点定义,链表的结点结构与单链表的结点相同 template struct Node T data； Node *next；/此处T可以省略 ；,20,链栈入栈算法,操作步骤： /入栈 / S1：创建一个值为入栈元素的新结点s； / S2：新结点s插入表头； / S3：栈顶指针指向s,template void LinkStack：Push(T x) s=new Node； s-data=x；
7、s-next=top； top=s； ,算法描述：,s,x,Q:为什么没有判断栈满 ？,21,链栈出栈,链栈出栈即删除链表的首元素结点。 操作步骤： T LinkStack：Pop() Step 1：如果栈空，则下溢； if(top = = NULL) throw下溢； Step 2：暂存栈顶结点，取该结点值； x = top-data； Step 3：栈顶指针后移； top = top-next； Step 4：删除原栈顶结点，返回其值。 delete p； return x;,an,an-1,a1,Q: top+可以吗？,22,链栈出栈,操作步骤： /出栈 / S1：如果栈空，则下溢； /
8、 S2：暂存栈顶结点，取该结点值； / S3：栈顶指针后移； / S4：删除原栈顶结点，返回其值。,算法描述： template T LinkStack：Pop() if (top = = NULL) throw下溢； p = top； x = top-data； top = top-next； delete p； return x； / LinkStack,.,23,顺序栈和链栈的比较,时间：出、入栈均是常数级。 空间：顺序栈容量受限 链 栈因指针需额外存储空间,元素个数多且变化较大时，适宜用链栈； 反之，宜采用顺序栈,24,栈的应用举例,1. 数制转换,2. 表达式求值,25,算法基于原理
9、： N = (N div d)d + N mod d,例1：数制转换,单击右键，选择“播放”,26,10_8 数制转换类算法,/把十进制整数N转化为八进制数输出 / S1：构造一个空栈 / S2：当N0，求八进制数各数字位 2.1 N % 8 入栈 2.2 NN / 8 / S3：如果栈不空, 输出八进制数各数制位 3.1 出栈 3.2 输出,void conversion10_8(int N) Stack s ； while (N) s.Push (N%8 )； N = N/8； while (!s.StackEmpty() e = s.Pop( )； coute； / conversion
10、10_8,27,OP + S1 + S2,S1 + OP + S2,S1 + S2 + OP,表达式的三种标识方法,1 + 2 * (7 4 ) / 3,1 2 7 4 * 3 / +,+ 1 / * 2 7 4 3,中缀表示法,前缀表示法,后缀表示法,28,中缀表达式后缀表达式,单击右键，选择“播放”,29,中缀表达式转换为后缀表达式,Step 1：创建一个操作符栈 Step 2：从左到右扫描读取表达式，执行下列运算， 直至表达式结束符 2.1 如果是操作数，输出； 2.2 如果是操作符2，把操作符栈栈顶的算符1与2 进行比较 2.2.1 12 ，从操作符栈输出所有比2优先 级高的算符，直至
11、栈顶算符优先级小于 2，2入操作符栈,30,运算符优先级定义,31,先找运算符，再找操作数,a b c d e / f +,ab,d/e,c-d/e,(c-d/e)f,ab+(c-d/e)f,后缀式求值,32,后缀表达式计算,Step 1：创建一个栈，作为操作数栈 Step 2：执行下列操作，直到表达式结束 2.1 读取表达式 2.2 如果是操作数，入操作数栈 2.3 如果是操作符t，从操作数栈退出两个操作数b、a，进行运算a t b，并把运算结果入操作数栈 Step 3：栈顶元素即为表达式的值,33,例3：递归,long int Fact(int n) if(n0) exit(0)；/参数非
12、法 if(n= = 0) y = 1； / 递归的边界 else y = n * Fact(n-1)；/递归调用 #: retrun y； ,main() . y = Fact(3)； *: . ,34,调用过程,返回过程,递归程序执行,35,3.2 队列,36,队列的逻辑结构,定义:只允许在表的一端进行插入，而在另一端删除元素的线性表。,特点：先进先出 (FIFO),队列,37,ADT Queue 数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头， an 端为队列尾,基本操作：,
13、ADT Queue,队列的抽象数据类型定义,.,38,InitQueue( rear+;,basefront出 front+;,44,假溢出,假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。,解决方法：将存储队列的数组头尾相接。,a3,a4,a5,a6,循环队列,45,单击右键，选择“播放”,46,队列初始化：front = rear = 0; 队头指针进1: front = (front+1) %maxsize; 队尾指针进1: rear = (rear+1) % maxsize; 队空条件：front = rear;
14、 队满条件：(rear+1) % maxsize = front;,循环队列状态及指针调整,一般,空队,满队,47,循环队列的类定义,template / class CirQueue private： T *base； / 存储空间基址 int front； / 队头指针 int rear； / 队尾指针 int queuesize；/ 队容量 public： ,queuesize,A,B,front,rear,48,循环队列成员函数定义,CirQueue(int m)； /构造空队列 CirQueue()； / 析构函数，释放队列存储空间 void EnQueue(T x)； /入队 T
15、DeQueue()； /出队 T GetHead()； / 取队头元素 T GetLast()； /取队尾元素 int QueueEmpty()； / 判队空 int QueueFull()； /判队满 void ClearQueue()； /清空队 void QueueTranverse()；/遍历队，输出队列元素,49,循环队列创建,算法描述： template CirQueue:CirQueue(int m) base = new Tm； if(base = = NULL) cout队创建失败，退出!” endl； exit(1)； front = rear = 0； / S2：队属性赋值 queuesize = m； ,m,front,rear,操作步骤：,/创建一个空队 / S1：申请一组连续内存空间,50,循环队列入队算法,算
