未讲分校C课件第18讲队列栈树__自编

1、栈栈队列队列树树程序设计举例程序设计举例2/221.1. 你见过餐馆中一叠一叠的盘子吗？如果它们是按你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,1,2,n ,n 的次序往上叠的，那么使用时候的次序应是什的次序往上叠的，那么使用时候的次序应是什么样的？么样的？2.2. 在日常生活中，为了维持正常的社会秩序而出现的常见在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？现象是什么？18.1 栈栈课前思考课前思考 通常称，栈和队列是限定插入和删除只能在表的通常称，栈和队列是限定插入和删除只能在表的“端点端点”进行的线性表。进行的线性表。栈和队列是两种常用的数据类型栈和队列是两种常用的数

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) 1in3/2218.1 栈栈一、定义一、定义栈栈(Stack)(Stack)是一种特殊的线性表是一种特殊的线性表，其其插入和删除插入和删除操作均操作均在在表的一端表的一端进行，是一种进行，是一种运算受限运算受限的线性表。的线性表。栈顶栈顶(top)(top)允许插入和删除的一端允许插入和删除的一端。栈底栈底(bottom)(bottom)栈的另一端栈的另一端。二、栈的

3、特点二、栈的特点栈的修改是按后进先出的原则进行的。栈的修改是按后进先出的原则进行的。因此，栈又称为因此，栈又称为后进先出后进先出(Last In (Last In First Out)First Out)的线性表的线性表，简称，简称LIFOLIFO结构。结构。假设栈假设栈S= ai | ai ElemSet, i=1,2,.,n, n0 ，则称则称a1为栈底元素，为栈底元素，an为栈顶元素，栈中元素按为栈顶元素，栈中元素按a1,a2,an的次序进栈，退栈的第一个元素应为栈的次序进栈，退栈的第一个元素应为栈顶元素。顶元素。4/22三、栈的抽象数据型基本操作：三、栈的抽象数据型基本操作： (1)M

4、AKENULL(S)/(1)MAKENULL(S)/SETNULL(S);SETNULL(S); (2)EMPTY(S); (2)EMPTY(S); (3)PUSH(x,S); (3)PUSH(x,S); (4)POP(S); (4)POP(S); (5)TOP(S); (5)TOP(S);另外还有：另外还有： (6)STACKLENGTH(S);(6)STACKLENGTH(S); (7)DISPLAY(S) (7)DISPLAY(S)。18.1 栈栈#四、栈的顺序存储的概念四、栈的顺序存储的概念( (栈的数组实现栈的数组实现) ) 栈的顺序存储是利用一块连续的存储单元依次存放栈中栈的顺序存

5、储是利用一块连续的存储单元依次存放栈中的数据元素，并附一个指针的数据元素，并附一个指针toptop指示当前指示当前栈顶栈顶。 采用顺序存储方式存储的栈称为采用顺序存储方式存储的栈称为顺序栈。顺序栈。18.1.1 栈的数组实现栈的数组实现顺序栈顺序栈5/22数据对象：数据对象：D=ai| aiElemSet, i=1,2,n, n0数据关系：数据关系：R1=|ai-1, aiD, i=1,2,n 约定约定a an n端为栈顶，端为栈顶，a a1 1 端为栈底端为栈底基本操作：基本操作： InitStack(InitStack(&S)S) 操作结果操作结果：构造一个空栈：构造一个空栈 S S。 D

6、estroyStack(DestroyStack(&S)S) 初始条件初始条件：栈：栈 S S 已存在。已存在。 操作结果操作结果：栈：栈 S S 被销毁。被销毁。 ADT Stack 1、栈的、栈的抽象数据类型定义：抽象数据类型定义：6/22 StackEmpty(S) StackEmpty(S)初始条件初始条件：栈：栈 S S 已存在。已存在。操作结果操作结果：若栈：若栈 S S 为空栈，则返为空栈，则返TRUETRUE，否则，否则 FALEFALE。 StackLength(S)StackLength(S)初始条件初始条件：栈：栈 S S 已存在。已存在。操作结果操作结果：返回：返回 S

7、 S 的元素个数，即栈的长度。的元素个数，即栈的长度。 ClearStack(ClearStack(&S)S)初始条件初始条件：栈：栈 S S 已存在。已存在。操作结果操作结果：将：将 S S 清为空栈。清为空栈。判定栈是否为空栈是栈判定栈是否为空栈是栈在应用程序中经常使用在应用程序中经常使用的操作，通常以它作为的操作，通常以它作为循环结束的条件。循环结束的条件。7/22 GetTop(S, GetTop(S, &e)e)初始条件初始条件：栈：栈 S S 已存在且非空。已存在且非空。操作结果操作结果：用：用 e e 返返回回 S S 的栈顶元素。的栈顶元素。a1a2an Push( Push(

8、&S, e)S, e) 初始条件初始条件：栈：栈 S S 已存在。已存在。 操作结果操作结果：插入元素：插入元素 e e 为新的栈顶元素。为新的栈顶元素。a1a2ane 8/22 Pop( Pop(&S, S, &e)e)初始条件初始条件：栈：栈 S S 已存在且非空。已存在且非空。操作结果操作结果：删除：删除 S S 的栈顶元素，并用的栈顶元素，并用 e e 返回其值返回其值a1a2anan-1 StackTraverse (S, visit() StackTraverse (S, visit()初始条件初始条件：栈：栈 S S 已存在。已存在。操作结果操作结果：从：从栈底到栈顶栈底到栈顶依

9、次对依次对S S 的每个数据元素调用函数的每个数据元素调用函数visit()visit()。一旦。一旦visit()visit()失败，则操作失败。失败，则操作失败。 ADT Stack9/22 和线性表类似，栈也有两种存储表示，其顺序存储结构简和线性表类似，栈也有两种存储表示，其顺序存储结构简称为顺序栈。称为顺序栈。和顺序表类似，对顺序栈也需要事先为它分配一个可以容和顺序表类似，对顺序栈也需要事先为它分配一个可以容纳最多元素的存储空间，纳最多元素的存储空间，base base 为这个存储空间的基地址，也为这个存储空间的基地址，也即一维数组的地址。即一维数组的地址。同时附设栈顶指针同时附设栈顶

10、指针toptop指示栈顶元素在顺序栈中的位置。指示栈顶元素在顺序栈中的位置。2 2、栈的表示和实现、栈的表示和实现 栈的基本操作集和线性表相比要小的多，但它栈的基本操作集和线性表相比要小的多，但它们在应用程序中都能用到。们在应用程序中都能用到。10/22 typedef struct SElemType *base; /栈底指针 SElemType *top; /栈顶指针 int stacksize; SqStack 其中，其中， stacksizestacksize指示栈的当前可使用的最大指示栈的当前可使用的最大容量。容量。TopTop为栈顶指针，其初值指向栈底，每当插为栈顶指针，其初值指向

11、栈底，每当插入新元素，指针入新元素，指针toptop加加1 1，删除栈顶元素时，指针，删除栈顶元素时，指针toptop减减1 1。非空栈中，。非空栈中，toptop始终指向栈顶元素的下一始终指向栈顶元素的下一个位置。个位置。顺序栈的定义：顺序栈的定义：11/22/-ADT Stack/-ADT Stack的表示与实现的表示与实现-/-/-栈的顺序存储表示栈的顺序存储表示-#define STACK_ INIT_ SIZE 100; /存储空间初始分配存储空间初始分配量量#define STACKINCREMENT 10; /存储空间分配增量存储空间分配增量typedef struct SEle

12、mType *base; /在栈构造之前和销毁之后，在栈构造之前和销毁之后， basebase的值为的值为NULLNULL SElemType *top; /栈顶指针栈顶指针 int stacksize; /当前已分配的存储空间，以元素为单位当前已分配的存储空间，以元素为单位 SqStack以下是顺序栈的模块说明。以下是顺序栈的模块说明。12/22-基本操作的函数原型说明基本操作的函数原型说明-Status InitStack (SqStack &S ); / 构造一个空栈构造一个空栈S S Status DestroyStack (SqStack &S ); / 销毁栈销毁栈S S，S S不

13、再存在不再存在 Status ClearStack (SqStack &S ); / 重置重置S S 为空栈为空栈Status StackEmpty (SqStack S ); /若栈为空栈，则返回若栈为空栈，则返回TRUETRUE，否则，否则 返回返回FALSEFALSEint StackLength (SqStack S ); /返回返回S S的元素个数，即的元素个数，即栈的长度栈的长度 13/22 Status Status GetTopGetTop (SqStack S , SElemType &e ) (SqStack S , SElemType &e )/若栈不空，则用若栈不空，则

14、用e e返回返回S S的栈顶元素，并返回的栈顶元素，并返回OKOK，否则返回，否则返回ERRORERRORStatus Status PushPush (SqStack &S , SElemType e ) (SqStack &S , SElemType e )/ / 插入元素插入元素e e为新的栈顶元素为新的栈顶元素Status Status PopPop (SqStack &S , SElemType &e ) (SqStack &S , SElemType &e )/若栈不空，则删除若栈不空，则删除S S的栈顶元素，并用的栈顶元素，并用e e返回其值，并返回返回其值，并返回OKOK，否则

15、返回，否则返回ERRORERRORStatus Status StackTraverseStackTraverse (SqStack &S , Status( (SqStack &S , Status(* *visit)() );visit)() ); / /从栈底到栈顶依次对栈中每个元素调用函数从栈底到栈顶依次对栈中每个元素调用函数visit()visit()。一。一旦旦visit()visit()失败，则操作失败失败，则操作失败14/22队列的描述可以用如图的方式所描述队列的描述可以用如图的方式所描述。 a1 a2 . an入队队头队尾出队图-队列示意图仅允许在一端进行插入，另一端进行删除

16、的线性表，称为仅允许在一端进行插入，另一端进行删除的线性表，称为队列队列(queue)(queue)。允许插入的一端称为队尾。允许插入的一端称为队尾(rear)(rear)，允许删除，允许删除的一端称为队头（的一端称为队头（frontfront）。）。队列是一种先进先出（队列是一种先进先出（First In First OutFirst In First Out）的特殊线性）的特殊线性表，或称表，或称FIFOFIFO表。表。若队列中没有任何元素，则称为空队列，否则称为非空队若队列中没有任何元素，则称为空队列，否则称为非空队列。列。 1 1、队列的定义、队列的定义类似于日常生活的排队类似于日常生

17、活的排队15/222 2、队列的抽象数据类型描述、队列的抽象数据类型描述其类型定义如下：其类型定义如下：ADT Queue 数据对象：数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：数据关系：R1R1 a | , a| , ai i D, i=2,.,n D, i=2,.,n 约定约定 a1 a1 端为队列头，端为队列头，an an 端为队列尾。端为队列尾。基本操作：基本操作：1 1、InitQueue(&Q)InitQueue(&Q) 操作结果操作结果：构造一个空队列构造一个空队列Q Q。2、DestroyQueue (& Q)初始条件：初始条件：队列队

18、列Q已存在。已存在。操作结果：操作结果：队列队列Q被销毁。被销毁。3、ClearQueue (& Q)初始条件：初始条件：队列队列Q已存在。已存在。操作结果：操作结果：将将Q清为空队列。清为空队列。16/225 5、QueueLength(Q)QueueLength(Q)初始条件：初始条件：队列队列Q Q已存在。已存在。操作结果：操作结果：返回返回Q Q中元素个数，即队列的长度中元素个数，即队列的长度6 6、GetHead(Q, &e)GetHead(Q, &e)初始条件：初始条件：队列队列Q Q已存在且非空。已存在且非空。操作结果：操作结果：用用 e e 返回返回Q Q的队头元素。的队头元素

19、。取队头元素操作，用取队头元素操作，用e e返回队列中当前返回队列中当前的队头元素，但不将它从队列中删除。的队头元素，但不将它从队列中删除。4 4、QueueEmpty(Q)QueueEmpty(Q) 初始条件：初始条件：队列队列Q Q已存在。已存在。操作结果：操作结果：若若Q Q为空队列，则返回为空队列，则返回TRUETRUE， 否则返回否则返回FALSEFALSE17/227 7、EnQueue(&Q, e)EnQueue(&Q, e) 初始条件：初始条件：队列队列Q Q 已存在。已存在。操作结果：操作结果：插入元素插入元素e e为为Q Q的新的队尾元素。的新的队尾元素。入队列操作：在当前

20、的队尾元素之后插入新的队尾元素入队列操作：在当前的队尾元素之后插入新的队尾元素这是出队列操作，用这是出队列操作，用e e返回当前的队返回当前的队头元素，并将它从队列中删除。头元素，并将它从队列中删除。8、DeQueue(&Q, &e) 初始条件：初始条件：队列队列Q 已存在且非空。已存在且非空。操作结果：操作结果：删除删除 Q的队头元素，并用的队头元素，并用e返回其值。返回其值。18/229 9、QueueTraverse(Q, visit( )QueueTraverse(Q, visit( ) 初始条件：初始条件：队列队列Q Q已存在且非空，已存在且非空，visit( )visit( )为元

21、为元 素的访问函数。素的访问函数。 操作结果：操作结果：从队头到队尾依次对从队头到队尾依次对Q Q的每个元素的每个元素 调用函数调用函数visit( )visit( )，一旦，一旦visit( )visit( ) 失败，则操作失败。失败，则操作失败。对队列进行从队头到队尾的对队列进行从队头到队尾的 遍历遍历 操作，应用操作，应用较多的场合是，输出队列中所有数据元素。较多的场合是，输出队列中所有数据元素。 队列类型中的九个基本操作恰好和栈的九个操作是队列类型中的九个基本操作恰好和栈的九个操作是一一对应的。同样要求熟练掌握。一一对应的。同样要求熟练掌握。 ADT Queue19/22链队列链队列:

22、 用链表表示的用链表表示的队列简称为队列简称为链队列。链队列。 一个链队列需要两个分别指示队头和队尾一个链队列需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能惟一的指针（分别称为头指针和尾指针）才能惟一确定。确定。3 3、链队列、链队列队列的链式表示和实现队列的链式表示和实现typedef struct QNode / 结点类型结点类型 QElemType data; struct QNode *next; QNode, *QueuePtr;20/22typedef struct / 链队列类型链队列类型 QueuePtr front; / 队头指针队头指针 QueuePtr r

23、ear; / 队尾指针队尾指针 LinkQueue;a1anQ.frontQ.rearQ.frontQ.rear空队列空队列21/22-基本操作的函数原型说明基本操作的函数原型说明-Status InitQueue(LinkQueue &Q );Status InitQueue(LinkQueue &Q ); / 构造一个空的队列构造一个空的队列Q Status DestroyQueue(LinkQueue &Q );Status DestroyQueue(LinkQueue &Q ); / 销毁队列销毁队列Q Q，Q Q不再存在不再存在 Status ClearQueue(LinkQueue

24、 &Q );Status ClearQueue(LinkQueue &Q ); / 重置重置Q Q为空为空队列队列Status QueueEmpty(LinkQueue Q ); Status QueueEmpty(LinkQueue Q ); /若为空若为空队列队列，则返回，则返回TRUETRUE，否则，否则 返回返回FALSEFALSEStatus QueueLength(LinkQueue Q ); QueueLength(LinkQueue Q ); /返回返回Q Q的元素个数，即队列的元素个数，即队列的长度的长度 22/22 Status GetHead (LinkQueue Q ,

25、 QElemType &e )Status GetHead (LinkQueue Q , QElemType &e )/若队列不空，则用若队列不空，则用e e返回返回Q Q的队头元素，并返回的队头元素，并返回OKOK，否则返，否则返回回ERRORERRORStatus EnQueue (LinkQueue &Q , QElemType e )Status EnQueue (LinkQueue &Q , QElemType e )/ / 插入元素插入元素e e为新的队尾元素为新的队尾元素Status DeQueue (LinkQueue &Q , QElemType &e )Status DeQ

26、ueue (LinkQueue &Q , QElemType &e )/若队列不空，则删除若队列不空，则删除Q Q的队头元素，并用的队头元素，并用e e返回其值，并返返回其值，并返回回OKOK，否则返回，否则返回ERRORERRORStatus QueueTraverse (LinkQueue &Q ,visit() );Status QueueTraverse (LinkQueue &Q ,visit() ); /从队尾到队头依次对队列中每个元素调用函数从队尾到队头依次对队列中每个元素调用函数visit()visit()。一旦一旦visit()visit()失败，则操作失败失败，则操作失败2

27、3/22Status InitQueue (LinkQueue &Q) / 构造一个空队列构造一个空队列 Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit(OVERFLOW);/ 存储分配失败存储分配失败Q.front-next=NULL; return OK; 链队列的基本运算链队列的基本运算（1）初始化链队列）初始化链队列24/22Status EnQueue(Queue &Q,ElemType e) / 在当前队列的尾元素之后，插入元素在当前队列的尾元素之后，插入元素e e为新的为新的 队列尾元素队列尾

28、元素s = (QueuePtr)malloc(sizeof (QNode); s = (QueuePtr)malloc(sizeof (QNode); if (!s) exit(OVERFLOW);if (!s) exit(OVERFLOW);/ / 存储分配失败存储分配失败 s-data=e; s-data=e; s-next = NULL;s-next = NULL;Q.rear-next=s;Q.rear-next=s;/ / 修改尾结点的指针修改尾结点的指针 Q.rear=s; Q.rear=s; / / 移动队尾指针移动队尾指针 return OK;return OK; （2）入队列

29、）入队列25/22Status DeQueue(Queue &Q, ElemType &e) / / 若队列不空，则删除当前队列若队列不空，则删除当前队列Q Q中的头元素，中的头元素， 用用e e返回其值，并返回返回其值，并返回OKOK；否则返回；否则返回ERROR ERROR if ( Q.front = Q.rear ) if ( Q.front = Q.rear ) / / 链队列中只有一个头结点链队列中只有一个头结点return ERROR; return ERROR; p = Q.front-next; p = Q.front-next; e = p-data;e = p-data;

30、/ / 返回被删元素返回被删元素Q.front-next=p-next;Q.front-next=p-next;/ / 修改头结点指针修改头结点指针if(Q.rear = p) Q.rear = Q.front;if(Q.rear = p) Q.rear = Q.front;free(p);free(p);/ / 释放被删结点释放被删结点return TRUE;return TRUE; / DeQueue（3）出队列）出队列26/22解释：解释： 由于一般情况下，出队列的操作只涉及队头元由于一般情况下，出队列的操作只涉及队头元素，因此不需要修改队尾指针，但当链队列中只有素，因此不需要修改队尾指

31、针，但当链队列中只有一个数据元素时，队头元素恰好也是队尾元素，当一个数据元素时，队头元素恰好也是队尾元素，当它被删除之后，队尾指针就它被删除之后，队尾指针就 悬空悬空 了，待下次再做了，待下次再做入队操作时，就要产生指针的入队操作时，就要产生指针的 悬空访问悬空访问 的错误，的错误，因此在这种情况下必须同时修改尾指针。因此在这种情况下必须同时修改尾指针。27/22/-基本操作的算法描述（部分）基本操作的算法描述（部分）- Status InitStack (SqStack &S) / 构造一个空栈构造一个空栈 S S.base = (SElemType*)malloc(STACK_INIT_S

32、IZE*sizeof(SElemType); if (!S.base) exit (OVERFLOW); / 存储分配失败存储分配失败 S.top=S.base; /top=base可以做为栈空的标记可以做为栈空的标记S.stacksize = STACK_INIT_SIZE;return OK;对顺序栈来说，空栈的初始化和顺序表的初始化完全相同。对顺序栈来说，空栈的初始化和顺序表的初始化完全相同。这不奇怪，因为它们的结构是一样的。也就是说，并非对栈这不奇怪，因为它们的结构是一样的。也就是说，并非对栈而言取不到除栈顶之外的元素，而是对栈类型来说，不允许而言取不到除栈顶之外的元素，而是对栈类型来

33、说，不允许这种操作。这种操作。（1）初始化栈）初始化栈28/22Status GetTop (SqStack S, SElemType &e) /* 若栈不空，则用若栈不空，则用 e 返回返回S的栈顶元素，并返回的栈顶元素，并返回OK； 否则返回否则返回ERROR*/if (S.top = S.base) return ERROR;e = * (S.top - 1); / 返回非空栈中栈顶元素返回非空栈中栈顶元素return OK;（2）取栈顶元素）取栈顶元素 Status Pop (SqStack S, SElemType &e) /*若栈不空，则删除若栈不空，则删除S的栈顶元素，用的栈顶元

34、素，用e返回其值，返回其值， 并返回并返回OK,否则返回否则返回ERROR*/if (S.top = = S.base) return ERROR;e=*- - S.top; return OK;（3）出栈）出栈29/22Status Push (SqStack S, SElemType e) /插入元素插入元素e 为新的栈顶元素为新的栈顶元素 if (S.top S.base=S.stacksize) S.base = (SElemType*)realloc(S.base, (STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType); if(!S.b

35、ase) exit (OVERFLOW); S.top = S.base + S.stacksize; S.stacksize + = STACKINCREMENT; *S.top + = e;return OK;（4） 进栈进栈30/2218.1. 栈栈一、定义一、定义栈栈(Stack)(Stack)是一种特殊的线性表是一种特殊的线性表，其其插入插入和删除和删除操作均在操作均在表的一端表的一端进行，是一种进行，是一种运算运算受限受限的线性表。的线性表。栈顶栈顶(top)(top)允许插入和删除的一端允许插入和删除的一端。栈底栈底(bottom)(bottom)栈的另一端栈的另一端。二、栈的特

36、点二、栈的特点后进先出后进先出(Last In First Out(Last In First Out，简称简称LIFOLIFO) )。又称栈为后进先出表。又称栈为后进先出表( (简称简称LIFOLIFO结构结构) )。31/22 三、三、栈的抽象数据型基本操作：栈的抽象数据型基本操作： (1)MAKENULL(S)/(1)MAKENULL(S)/SETNULL(S);SETNULL(S); (2)EMPTY(S); (2)EMPTY(S); (3)PUSH(x,S); (3)PUSH(x,S); (4)POP(S); (4)POP(S); (5)TOP(S); (5)TOP(S);另外还有：

37、另外还有： (6)STACKLENGTH(S);(6)STACKLENGTH(S); (7)DISPLAY(S) (7)DISPLAY(S)。18.1. 栈栈#32/22一、栈的顺序存储的概念一、栈的顺序存储的概念( (栈的数组实现栈的数组实现) ) 栈的顺序存储是利用一块连续的存储栈的顺序存储是利用一块连续的存储单元依次存放栈中的数据元素，并附一个单元依次存放栈中的数据元素，并附一个指针指针toptop指示当前指示当前栈顶栈顶。 采用顺序存储方式存储的栈称为采用顺序存储方式存储的栈称为顺序顺序栈。栈。18.1.1 栈的数组实现栈的数组实现顺序栈顺序栈33/22二、二、C语言描述顺序栈：型语言

38、描述顺序栈：型STACK可如下说明可如下说明:typedef int elementtype;#define maxlength 64struct STACK elementtype elementsmaxlength; int top; ; 18.1.1 栈的数组实现栈的数组实现顺序栈顺序栈elementtype elementsmaxlength;int top;常见用法常见用法34/22 三、三、栈的抽象数据型基本操作：栈的抽象数据型基本操作： (1)MAKENULL(S)/(1)MAKENULL(S)/SETNULL(S);SETNULL(S); (2)EMPTY(S); (2)EMP

39、TY(S); FULL(S);FULL(S); (3)PUSH(x,S); (3)PUSH(x,S); (4)POP(S); (4)POP(S); (5)TOP(S); (5)TOP(S);另外还有：另外还有： (6)STACKLENGTH(S);(6)STACKLENGTH(S); (7)DISPLAY(S) (7)DISPLAY(S)。18.1.1 栈的数组实现栈的数组实现顺序栈顺序栈35/223进栈：进栈：void PUSH(elementtype x, STACK &S) if(S.top=0) error(“stack is full”); else S.top-; S.elemen

40、tsS.top=x; 18.1.1 栈的数组实现栈的数组实现顺序栈顺序栈36/225取栈顶元素：取栈顶元素： elementtype TOP(STACK S) if(EMPTY(S) return null; else return(S.elementsS.top); 18.1.1 栈的数组实现栈的数组实现顺序栈顺序栈37/224出栈出栈 void POP(STACK &S) if(EMPTY(S) error(“stack is emptyn”); else S.top+; elementtype POP(STACK &S) if(EMPTY(S) error(“stack is empty

41、n”); else S.top+; return(S.elementsS.top-1); 18.1.1 栈的数组实现栈的数组实现顺序栈顺序栈#38/22举例举例1、两个栈共享数组空间、两个栈共享数组空间vm，它们的栈，它们的栈底分别设在数组的两端，每个元素占一个分量，底分别设在数组的两端，每个元素占一个分量，试写出两个栈公用栈操作算法：试写出两个栈公用栈操作算法：push(i,x),pop(i)和和top(i),其中其中i为为0和和1，用，用以指示栈号。以指示栈号。 struct STACK elementtype vm; int top2 ; / 栈顶指针栈顶指针;STACK S;18.1.

42、1 栈的数组实现栈的数组实现顺序栈顺序栈39/22void PUSH(elementtype x,int i,STACK &S) if ( S.top1-S.top0)=1) error(“stack is full”); else switch (i) case 0: S.v+(S.top0)=x; break; case 1: S.v-(S.top1)=x; break; default: error(“栈编号输入错误栈编号输入错误”); 18.1.1 栈的数组实现栈的数组实现顺序栈顺序栈40/22入栈与出栈顺序的讨论入栈与出栈顺序的讨论:入栈顺序是入栈顺序是12345判断对错判断对错:(

43、1)出栈顺序是出栈顺序是12345(2)出栈顺序是出栈顺序是21345(3)出栈顺序是出栈顺序是21435(4)出栈顺序是出栈顺序是14235#18.1.1 栈的数组实现栈的数组实现顺序栈顺序栈41/22一、栈的链式存储方式一、栈的链式存储方式 采用链式存储的栈称为链栈。采用链式存储的栈称为链栈。二、链栈的特点：二、链栈的特点： (1)(1)不需预先分配存储空间。不需预先分配存储空间。 (2)(2)是一种特殊的单链表是一种特殊的单链表, ,不存在栈满上不存在栈满上溢的情况。溢的情况。18.1.2 栈的指针实现栈的指针实现链栈链栈42/22(1)(1)链栈结点类型的定义：链栈结点类型的定义：ST

44、RUCT nodeSTRUCT node elementtype elements; elementtype elements; node node * *next;next; ; ;栈底栈底a1 an-1 an栈顶栈顶 topdata next18.1.2 链栈链栈Typedef node Typedef node * *STACK;STACK;Typedef node STACK;Typedef node STACK;43/22 三、三、栈的抽象数据型基本操作：栈的抽象数据型基本操作： (1)NEWSTACK(S); (1)NEWSTACK(S); (2)EMPTY(S); (2)EMPT

45、Y(S); (3)PUSH(x,S); (3)PUSH(x,S); (4)POP(S); (4)POP(S); (5)TOP(S); (5)TOP(S);另外还有：另外还有： (6)STACKLENGTH(S);(6)STACKLENGTH(S); (7)DISPLAY(S) (7)DISPLAY(S)。1、带头结点、带头结点2、不带头结点、不带头结点18.1.2链栈链栈#44/22 13.2 栈的应用举例栈的应用举例一、括号匹配的检验一、括号匹配的检验二、递归的实现二、递归的实现45/22 一、括号匹配的检验一、括号匹配的检验检验表达式中的括号匹配情况检验表达式中的括号匹配情况 假设在一个算

46、术表达式中，可以包含三种假设在一个算术表达式中，可以包含三种括号：圆括号括号：圆括号“（”和和“）”，方括号，方括号“ ”和和“ ”和花括号和花括号“ ”和和“ ”，并且这三种括号可，并且这三种括号可以按任意的合法次序嵌套使用。以按任意的合法次序嵌套使用。 现在需要设计一个算法，用来检验在输入现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。的算术表达式中所使用括号的合法性。 遇到遇到“( (”，“ ”，“ ”进栈，遇到进栈，遇到“）”，“ ”，“ ”出栈。出栈。 46/22 一、括号匹配的检验一、括号匹配的检验 （1 1）当遇到某一个右括号时，栈已空，说）当遇到某一个右括

47、号时，栈已空，说明到目前为止，右括号多于左括号；明到目前为止，右括号多于左括号； （2 2）从栈中弹出的左括号与当前检验的右）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；括号类型不同，说明出现了括号交叉情况； （3 3）算术表达式输入完毕，但栈中还有没）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。有匹配的左括号，说明左括号多于右括号。47/22 一、括号匹配的检验一、括号匹配的检验boolean check( )char ch; STACK S; MAKENULL(S); while (ch=getchar()!=#) switch (ch)

48、 case (ch=(|ch=|ch=):PUSH(S,ch);break; case (ch= ): if (EMPTY(S) retrun FALSE; else if (TOP(S)!= () return FALSE; else POP(S); break;48/22 一、括号匹配的检验一、括号匹配的检验 case (ch=): if (EMPTY(S) retrun FALSE; else if (TOP(S)!= ) return FALSE; else POP(S); break; case (ch= ): if (EMPTY(S) retrun FALSE; else if (

49、TOP(S)!= ) return FALSE; else POP(S); break; default:break;if (EMPTY(S) return TRUE;else return FALSE;49/22例例3.2：用栈实现递归函数：用栈实现递归函数阶乘函数的递归算法如下：阶乘函数的递归算法如下：int FACT(n)int n;if (n=1) return(1); else return(n*FACT(n-1);试编写阶乘函数的非递归算法。试编写阶乘函数的非递归算法。二、递归的实现二、递归的实现50/22阶乘的非递归计算阶乘的非递归计算int norecfact (int n)

50、int res = 1; STACK S; MAKENULL(S); while (n0)PUSH(S, n); - n; while ( !EMPTY(S) )res *=TOP(S);POP(S) DELETE S; return(res); 三、递归的实现三、递归的实现#51/221 1定义定义队列队列(Queue)(Queue)是一种是一种运算受限运算受限的特殊的线性的特殊的线性表，它只允许在表的表，它只允许在表的一端进行插入一端进行插入，而在表的，而在表的另另一端进行删除一端进行删除。队尾队尾(rear)(rear)允许插入的一端。允许插入的一端。队头队头(front)(front)

51、允许删除的一端。允许删除的一端。设一队列设一队列:q=(a:q=(a1 1,a,a2 2, ,a,an n) )，a a1 1为队头元素，为队头元素，a an n为为队尾元素，进入队列的顺序为队尾元素，进入队列的顺序为a a1 1,a,a2 2, ,a,an n 13.4 排队（队列）排队（队列）52/222.2.队列的特点队列的特点先进先出先进先出(First In First Out (First In First Out ，简称，简称FIFOFIFO) )。又称队列为先进先出表。又称队列为先进先出表。13.4 排队（队列）排队（队列）53/22 3. 3.队列的抽象数据型的基本操作：队列

52、的抽象数据型的基本操作： (1)MAKENULL(Q)(1)MAKENULL(Q) (2)EMPTY(Q) (2)EMPTY(Q) (3)FRONT(Q) (3)FRONT(Q) (4)ENQUEUE(x,Q) (4)ENQUEUE(x,Q) (5)DEQUEUE(Q) (5)DEQUEUE(Q) (6)QLENGTH(Q) (6)QLENGTH(Q)13.4 排队（队列）排队（队列）#54/221.1.队列的链式表示和实现队列的链式表示和实现(1)(1)用链式表示的队列简称为链队列。链用链式表示的队列简称为链队列。链队列实际是一个带有头指针队列实际是一个带有头指针(front)(front)

53、和尾和尾指针指针(rear)(rear)的单链表。的单链表。13.4.1链队列链队列在链队列中也可设一个头结点，令头指在链队列中也可设一个头结点，令头指针指向头结点。针指向头结点。空队列的判断条件空队列的判断条件是头指针和尾指针均是头指针和尾指针均指向头结点指向头结点。55/222 2、链队列的、链队列的c c语言描述：语言描述：STRUCT celltypeSTRUCT celltype elementtype element; elementtype element; celltype celltype * *next;next;celltype celltype * *front;fro

54、nt;celltype celltype * *rear;rear;Struct QUEUEStruct QUEUE celltype celltype * *front;front; celltype celltype * *rear;rear; ; ; QUEUE QUEUE * *Q;Q;13.4.1链队列链队列56/22 3. 3.队列的抽象数据型的基本操作：队列的抽象数据型的基本操作： (1)MAKENULL(Q)(1)MAKENULL(Q) (2)EMPTY(Q) (2)EMPTY(Q) (3)FRONT(Q) (3)FRONT(Q) (4)ENQUEUE(x,Q)(4)ENQUE

55、UE(x,Q) (5)DEQUEUE(Q)(5)DEQUEUE(Q) (6)QLENGTH(Q) (6)QLENGTH(Q)13.4.1 排队（队列）排队（队列）57/223、实现的基本操作：、实现的基本操作：a.构造一个空队列构造一个空队列 void MAKENULL(QUEUE &Q) Q.front= new celltype; Q.front-next=NULL; Q.rear=Q.front; 13.4.1链队列链队列58/22b.插入元素插入元素 void ENQUEUE(elementtype x QUEUE &Q) Q.rear-next=new celltype; Q.rea

56、r=Q.rear-next; Q.rear-element=x; Q.rear-next=NULL; 13.4.1链队列链队列59/22 void DEQUEUE(QUEUE &Q) celltype *temp; if(EMPTY(Q) error(“queue is empty”); else temp=Q.front-next; Q.front-next=temp-next; delete temp; if (Q.front-next=NULL) Q.rear=Q.front; 13.4.1链队列链队列(出队出队)#60/22 1 1队列的顺序表示和实现队列的顺序表示和实现 用内存中一组

57、连续的存储单元（数组）用内存中一组连续的存储单元（数组）存放队列中的各元素，简称顺序队列。存放队列中的各元素，简称顺序队列。 13.4.2 顺序队列顺序队列61/22struct QUEUE elementtype elementsmaxlength; int front; /指向队头元素的位置指向队头元素的位置 int rear; /指向队头元素的位置指向队头元素的位置; QUEUE Q;QUEUE *Q; elementtype elementsmaxlength; int front; /指向队头元素的位置指向队头元素的位置 int rear; /指向队尾元素的位置指向队尾元素的位置2、

58、C语言表示语言表示13.4.2 顺序队列顺序队列62/2243210Q-rear=-1Q-front=-1AQ-rear=0Q-front=0BAQ-rear=1Q-front=0EDCBAQ-rear=4Q-front=013.4.2 顺序队列顺序队列63/2243210EDCBAQ-rear=4Q-front=0EDCBQ-rear=4Q-front=1EDCQ-rear=4Q-front=2什么是假上溢现象？什么是假上溢现象？Q-rear=4Q-front=413.4.2 顺序队列顺序队列64/22 4.4.循环队列循环队列 把顺序队列构造成一个首尾相连的循环表。把顺序队列构造成一个首尾

59、相连的循环表。指针和队列元素之间关系不变。指针和队列元素之间关系不变。EDC Q-rear=4Q-front=2EDCFQ-rear=0Q-front=2EDCGFQ-rear=1Q-front=213.4.2 顺序队列顺序队列65/22EDCGFQ-rear=1Q-front=2CQ-rear=1Q-front=1Q-rear=1Q-front=2满队列：尾指针比头指针滞后一个位置；满队列：尾指针比头指针滞后一个位置；EDCFQ-rear=0Q-front=2空队列：尾指针比头指针滞后一个位置；空队列：尾指针比头指针滞后一个位置；13.4.2 顺序队列顺序队列66/22(2)处理循环队列满还

60、空的两种方法处理循环队列满还空的两种方法:a.另设一个标志以区别队列是另设一个标志以区别队列是“空空”还是还是“满满”；b.队满条件为：队满条件为：(Q-rear+2)%maxlength=Q-front队空条件为：队空条件为：(Q-rear+1)%maxlength =Q-frontEDCFQ-rear=0Q-front=213.4.2 顺序队列顺序队列67/22a.置空队列置空队列 MAKENULL(QUEUE &Q) Q.front=0; Q.rear=maxlength-1; 13.4.2 顺序队列顺序队列68/22b.判队空判队空 boolean EMPTY(QUEUE Q) if(