数据结构03章

1、1. 栈和队列的定义及运算2. 栈和队列的存储结构3. 压栈(进栈)与弹栈(出栈)操作的算法4. 循环队列栈是限定仅在表尾进行插入和删除操作的线性表(或称栈是一种特殊的线性表，其特殊性在于其运算是线性表运算的子集)，栈在逻辑上是一个下限为常数，上限可变化的向量(或上限为常数，下限可变化的向量)。1. 定义及基本概念定义及基本概念主要用于存放尚未处理而又等待处理的数据项。这些数据项的处理是依据后进先出的原则。因此，栈又称之为后进先出后进先出表(LIFO Last In First Out List)。 栈作为一种特殊的线性表，表尾端有其特殊的含义，我们称其为“栈顶栈顶”(top)，表头为“栈底栈

2、底”(bottom)，表中无元素时称为“空空栈栈”(栈空)。进栈(压栈)：把一个元素存入栈中。出栈(弹栈)：从栈中取出一个元素。如栈S = (a1, a2, an), 则a1为栈底，an为栈顶。 栈底元素：最先进栈的元素 栈顶元素：最后进栈的元素由存放该元素位置的指针变量标记(指示)，称此标记为栈底指针(base)。由存放该元素位置的指针变量标记(指示)，称此标记为栈顶指针(top)。栈的操作均在栈顶进行，如：进栈 a1a2anbasetop出栈栈底出栈进栈栈顶注：非空栈的栈顶指针注：非空栈的栈顶指针top始终在栈顶元素下一个位置上。始终在栈顶元素下一个位置上。2. ADT栈的定义栈的定义 P

3、45构造空栈：InitStack(S) ；判栈空: StackEmpty(S) ；判栈满： StackFull(S) ；进栈： Push(S,x) ；可形象地理解为压入，这时 栈中会多一个元素退栈： Pop(S) ；可形象地理解为弹出，弹出后栈中就无此元素了。取栈顶元素：StackTop(S) ；不同于弹出，只是使用栈顶元素的值，该元素仍在栈顶不会改变。其中栈的基本运算有六种：其中栈的基本运算有六种：3. 栈的存储结构栈的存储结构 线性表的存储结构对栈也适应，即可借用一组地址连续的存储单元描述栈的顺序存储结构，依次存放自栈底到栈顶的数据元素，即：顺序栈顺序栈；也可用链来描述栈的动态结构，即：链

4、式栈链式栈。 顺序存储顺序存储 P46typedef struct SElemType *base ; / 在栈构造前和销毁后为在栈构造前和销毁后为NULLSElemType *top ; / 栈顶指针栈顶指针int stacksize; / 已分配的存储空间已分配的存储空间 SqStack ;/-栈的栈的顺序存储结构顺序存储结构- #define STACK_INIT_SIZE 100 / 初始分配存储量初始分配存储量#define STACKINCREMENT 10 / 存储分配增量存储分配增量其中： top域为栈顶指针，指示栈顶元素的下一个位置，这种结构定义与线性表的顺序存储方式相似。

5、由于在使用过程中，栈的最大容量很难估计，因此，先为栈分配一个基本容量，当空间不够时再扩大。即：STACK_INIT_SIZE(存储空间初始分配量)和STACKINCREMENT(存储空间分配增量)，以随时增加容量。如下列描述的栈，可说明元素与栈顶指针之间的关系：SSSSAAAFEDCBDCBbasebase空 栈压入一个元素的栈栈满时两个元素出栈toptoptoptopbasebase 从上例可见，当S.top = = S.base时，栈空；若此时进行 pop操作，则会发生“下溢”。当S.top S.base = S.stacksize时，栈满；若此时进行push操作，则会发生“上溢”。 栈的

6、主要基本操作算法如下： P47构造空栈运算：构造空栈运算：P47Status InitStack (SqStack &S ) / 构造一个空栈构造一个空栈S.top = S.base ; S.stacksize = STACK_INIT_SIZE ;S.base = (SElemType *) malloc ( STACK_INIT_SIZE * sizeof(SElemType); return OK; / InitStackif (! S.base) exit(OVERFLOW); /存储分配失败存储分配失败求栈顶元素运算：求栈顶元素运算：P47Status GetTop (SqS

7、tack S, SElemType &e) / 若栈不空，则用若栈不空，则用e返回返回S的栈顶元素的栈顶元素 / 并返回并返回OK；否则返回；否则返回ERROR；return OK; if (S.top = = S.base) return ERROR; / GetTope = * ( S.top1 );进栈运算：进栈运算：P47Status Push(SqStack &S, SElemType e) / 插入元素插入元素e为新的栈顶元素为新的栈顶元素S.top = S.base + S.stacksize; S.stacksize + = STACKINCREMENT;S.b

8、ase = (SElemType *) realloc (S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType); return OK; if (S.top S.base = S.stacksize) / 栈满追加存储空间栈满追加存储空间 / Push* S.top + + = e;if (! S.base) exit(OVERFLOW); /存储分配失败存储分配失败 / if出栈运算：出栈运算：P47Status Pop(SqStack &S, SElemType &e) / 若栈不空，删除若栈不空，删除S的栈顶元

9、素，用的栈顶元素，用e返回其值返回其值 / 并返回并返回OK；否则返回；否则返回ERROR；return OK; if (S.top = = S.base) return ERROR; / Pope = * S.top;1. 基本概念基本概念 和栈类似，队列是线性表的另一种特例，它限定在表的一端插入，在另一端删除。插入端称为表尾表尾(队尾)，删除端称表头表头(队头)。队列也是用来存放尚未处理而有待处理的数据项，但在处理时必须遵循“先进先出”规则(First In First Out)。因此，队列也称之为“先进先出先进先出表表”(FIFO List)。在一个队列中，设立：队头指针(front)：

10、指向队头元素。队尾指针(rear)：指向队尾元素。例： q=(a1, a2, a3, , an) 的线性表，用队列描述如下图a1, a2, a3, , an出队进队队头front队尾rear2. ADT队列的定义及基本操作队列的定义及基本操作 P59置空队 ：InitQueue(Q) ；判队空： QueueEmpty(Q) ；判队满： QueueFull(Q) ；入队 ： EnQueue(Q,x) ；出队 ： DeQueue(Q) ；取队头元素： QueueFront(Q) ；不同于出队，队头元素仍然保留其中队列的基本运算也有六种：其中队列的基本运算也有六种：3. 队列的存储结构队列的存储结构

11、 (链队列和顺序队列 )1) 链式存储 单链队列 QNode ，*QueuePtr;/-单链队列单链队列队列队列的链式的链式存储结构存储结构- typedef struct QNode QElemType data ; struct QNode *next ; LinkQueue ;typedef struct QueuePtr front ; / 队头指针队头指针QueuePtr rear ; / 队尾指针队尾指针 队列实例(图示)：图中阴影结点为头结点，且Q.front指针指向头结点。单向队列空队列Q.frontQ.rear Q.front = Q.rear单向循环队列Q.frontQ.r

12、earQ.rearnext = Q.front Q.rearQ.front队头队头队尾队尾元素元素x入队列：入队列： Q.rearQ.frontxQ.rearQ.front yx元素元素y入队列：入队列：Q.rearQ.front yx元素元素x出队列：出队列： 注：链队列的操作就是单链表的插入和删除操作注：链队列的操作就是单链表的插入和删除操作的特殊情况，只是尚需修改尾指针或头指针。的特殊情况，只是尚需修改尾指针或头指针。 构造空队列运算：构造空队列运算：P62Status InitQueue (LinkQueue &Q ) / 构造一个空队列构造一个空队列Q.frontnext =

13、 NULL ; Q.front = Q.rear = (QueuePtr ) malloc (sizeof(QNode); return OK; / InitQueueif (! Q.front ) exit(OVERFLOW); /存储分配失败存储分配失败 队列的主要基本操作算法如下： P62插入运算：插入运算：P62Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素插入元素e为为Q的新的队尾元素的新的队尾元素pdata = e; pnext = NULL;p = (QueuePtr ) malloc ( sizeof(QNode);

14、return OK; / EnQueueif (! p) exit(OVERFLOW); /存储分配失败存储分配失败Q.rear = p ;Q.rearnext = p;删除运算：删除运算：P62Status DeQueue (LinkQueue &Q, QElemType &e) / 若队列不空，则删除若队列不空，则删除Q的队头元素，用的队头元素，用e返回其值返回其值 / 并返回并返回OK；否则返回；否则返回ERRORp = Q.frontnext ; e = pdata ;free(p) ; / DeQueueif (Q.front = = Q.rear) return E

15、RROR ;if (Q.rear = = p) Q.rear = Q.front ;Q.frontnext = pnext ;return OK; 销毁队列运算：销毁队列运算：P62Status DestroyQueue (LinkQueue &Q) / 销毁队列销毁队列Q / while while (Q.front) / DestroyQueueQ.rear = Q.frontnext ;free (Q.front) ;Q.front = Q.rear ;return OK; 2) 顺序存储 游标的位置：初始化建空队列时，令front =rear=0。每当插入新的队尾元素时，“尾指

16、针增1”；每当删除队头元素时，“头指针增1”。因而，在非空队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一个位置。（如下图） 游标的设置：除了用一组地址连续的存储单元依次存放从队头到队尾的元素之外，还需设两个指针(游标)front和rear，分别指示队头元素和队尾元素的位置。例：J1, J2 , J3入队入队J1, J2 出队出队(a)512340Q.rearQ.frontJ3J2J1Q.frontQ.frontQ.rearJ3Q.rearQ.frontQ.rearJ4, J5 入队入队J3J5J4J3, J4 出队，出队， J6入队入队Q.frontQ.rearJ5J6(b)(

17、c)(d)(e) 在上图中，当前为队列分配的最大空间为6，则当队列处于(e)的状态时，不可再继续插入新的队尾元素，否则会因数组越界而导致程序代码被破坏。 假上溢：如果再将J7入队，则会产生“上溢”，而实际上队列的实际可用空间并未占满，我们称这种情况为“假上溢假上溢”(或“假溢出假溢出”)。 当出现假溢出的情形下，如何使 得入队运算仍然可以执行？在不改变存储结构的情况下，可将队列中的元素朝front方向移动一个元素，即可加入新的元素。如上图(e)中，移动后如下所示：J7入队入队J5J6Q.rearQ.front512340512340J5J6J7Q.frontQ.rear 注：这种方法有很大的局

18、限性，若队列中的元素注：这种方法有很大的局限性，若队列中的元素很多的情况下，势必移动大量元素，显然不大适宜。很多的情况下，势必移动大量元素，显然不大适宜。因此，我们不仿改变一下队列的结构。因此，我们不仿改变一下队列的结构。建立循环队列 避免假溢出的有效且实用的方法 基本思想：将队列的两头相接，形成下图所示的环形队列，其中指针和队列元素之间的关系并不变 ：501234Q.rearQ.front 存储结构：P64/-循环循环队列队列队列队列的顺序的顺序存储结构存储结构- typedef struct QElemType *base ; / 初始化的动态分配空间初始化的动态分配空间int front

19、 ; / 头指针，若队列不空，指向队头元素头指针，若队列不空，指向队头元素 SqQueue ;#define MAXQSIZE 100 / 最大队列长度最大队列长度int rear ; / 尾指针，若队列不空，指向队尾元素的下一位置尾指针，若队列不空，指向队尾元素的下一位置 入队与出队：假设当前队列Q分配的最大空间为m(下标0.m1)，则初始时：Q.front = Q.rear = 0；若令Q.base为动态分配的空间，则：元素e入队：Q.baseQ.rear = e ; Q.rear + = 1 ;若Q.rear m1，则只须令Q.rear = 0，即：Q.rear = (Q.rear +

20、1) % m 。元素e出队：只须将Q.front前移一位即可；若Q.front m1，则只须令Q.front = 0，即：Q.front = (Q.front + 1) % m 。见下图：J1, J2出队入队J4, J5 501234J3J2J1Q.rearQ.front6J6, J7 , J8 J9入队队满队满501234J36Q.rearQ.front501234J3J4 J5 6Q.rearQ.front501234J3J4 J5 6J6J7J8J9Q.frontQ.rear(a)(b)(c)(d)501234Q.front6Q.rear队空队空 从上图可见，当队满和队空时，都有Q.re

21、ar = Q.front, 这就造成在程序中不易判别队列是空还是满，为此，我们采用下列两种方法解决：J3, J4 , J5 出队(e)(c)(e)a) 留空闲空间留空闲空间 如：如：501234J1Q.rearQ.frontJ2 J3 J4J5队满队满当队尾从后头追上队头时为队满，即(Q.rear + 1) % m = = Q.front ;队空时：Q.rear = = Q.front ；构造空队列运算：构造空队列运算：P64Status InitQueue (SqQueue &Q ) / 构造一个空队列构造一个空队列QQ.front = Q.rear = 0 ; Q.base = (

22、QElemType * ) malloc (MAXQSIZE * sizeof(QElemType); return OK; / InitQueueif (! Q.base ) exit(OVERFLOW); /存储分配失败存储分配失败 循环队列的主要基本操作算法如下： P64求队列的长度运算：求队列的长度运算：P64int QueueLength (SqQueue Q) / 返回返回Q的元素个数，即求队列的长度的元素个数，即求队列的长度return (Q.rearQ.front + MAXQSIZE) % MAXQSIZE ; / QueueLength插入运算：插入运算：P65Status

23、 EnQueue (SqQueue &Q, QElemType e) / 插入元素插入元素e为为Q的新的队尾元素的新的队尾元素return OK; / EnQueueif ( Q.rear + 1 ) % MAXQSIZE = = Q.front ) return ERROR ; / 队列满队列满Q.rear = ( Q.rear + 1 ) % MAXQSIZE ;Q.baseQ.rear = e ;删除运算：删除运算：P65Status DeQueue (SqQueue &Q, QElemType &e) / 若队列不空，则删除若队列不空，则删除Q的队头元素，用的队

24、头元素，用e返回其值返回其值 / 并返回并返回OK；否则返回；否则返回ERRORe = Q.baseQ.front ; / DeQueueif (Q.front = = Q.rear) return ERROR ;Q.front = ( Q.front + 1 ) % MAXQSIZE ;return OK; 如：如：501234J2Q.frontJ3 J4 J5J6Q.rear队满队满J1111111501234Q.frontQ.rear队空队空000000*b) 设置标志位设置标志位对每一位置设置一个标志，即： Q.basei.tag = 1 (第i个单元有元素) 0 (第i个单元无元素)

25、(0i m1)datatag初始状态：Q.basei.tag = 0 (0i m1)每执行一次入队操作，将Q.baseQ.rear.tag = 1 ;每执行一次出队操作，将Q.baseQ.front.tag = 0 ;因此，就有：队满：(Q.front=Q.rear) & (Q.baseQ.rear.tag=1) 此方法需要增加一个额外的标志，占用存储空间，且在时间上也有一定的损失。队空：(Q.front=Q.rear) & (Q.baseQ.front.tag=0) 存储结构：存储结构：/-循环循环队列队列队列队列的顺序的顺序存储结构存储结构- typedef struct

26、QElemType *base ; / 初始化的动态分配空间初始化的动态分配空间int front ; / 头指针，若队列不空，指向队头元素头指针，若队列不空，指向队头元素 SqQueue ;#define MAXQSIZE 100 / 最大队列长度最大队列长度int rear ; / 尾指针，若队列不空，指向队尾元素的下一位置尾指针，若队列不空，指向队尾元素的下一位置typedef struct ElemType data; /存放队列的元素存放队列的元素 int tag; /data域是否有元素的标志域是否有元素的标志QElemType; 主要基本操作算法如下：主要基本操作算法如下：构造空

27、队列运算：构造空队列运算：Status InitQueue (SqQueue &Q ) / 构造一个空队列构造一个空队列QQ.front = Q.rear = 0 ; Q.base = (QElemType * ) malloc (MAXQSIZE * sizeof(QElemType); return OK; / InitQueueif (! Q.base ) exit(OVERFLOW); /存储分配失败存储分配失败for(i=0; i MAXQSIZE; i+) /给每个给每个tag域赋初值域赋初值0 Q.basei.tag = 0;求队列的长度运算：求队列的长度运算：(不变不变)int QueueLength (SqQueue Q) / 返回返回Q的元素个数，即求队列的长度的元素个数，即求队列的长度if (Q.front=Q.rear) & (Q.baseQ.rear.tag=1) retu