数据结构：第3章栈和队列C

1、实验一小结实验一小结人多、后半场积极；人多、后半场积极； 但容错方案单一，时间效率低，盲目拷贝但容错方案单一，时间效率低，盲目拷贝常见问题常见问题用字符量测试整型量时崩溃用字符量测试整型量时崩溃 或用负数作为元素个数输入时系统崩溃或用负数作为元素个数输入时系统崩溃 普遍欠缺普遍欠缺UIUI设计意识设计意识 （UIUI指用户界面指用户界面 user interface user interface ）提示：提示：请细查请细查scanf(“%dscanf(“%d”, &m)”, &m)，非法输入将使，非法输入将使m m为大负数，为大负数，可用来判别。可用来判别。但可能出现输入的回车

2、符被第二次输入操作所捕捉，可紧跟但可能出现输入的回车符被第二次输入操作所捕捉，可紧跟scanf(“%c”,&cscanf(“%c”,&c) )；或或用用fflush(stdinfflush(stdin) )函数来清空缓冲区。函数来清空缓冲区。一班曾中、四班叶永盛自命题，有创意一班曾中、四班叶永盛自命题，有创意3.1 栈（栈（Stack） 3.2 队列（队列（Queue） 第三章第三章 栈和队列栈和队列1. 定义定义2. 逻辑结构逻辑结构3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式1. 定义定义2. 逻辑结构逻辑结构3. 存储结构存储结构4. 运算规则运算规

3、则5. 实现方式实现方式第第3 3章作业章作业: : 与线性表相同，仍为一对一关系。与线性表相同，仍为一对一关系。顺序队顺序队或或链队链队，以，以循环顺序队循环顺序队更常见。更常见。只能在队首和队尾运算，且访问结点时依照只能在队首和队尾运算，且访问结点时依照先进先出（先进先出（FIFOFIFO）的原则。的原则。关键是掌握关键是掌握入队入队和和出队出队操作，具体实现依顺操作，具体实现依顺序队或链队的不同而不同。序队或链队的不同而不同。只能在表的一端进行插入运算，在表的另一只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。端进行删除运算的线性表。基本操作基本操作：入队或出队，建空队列，

4、判队空或队满等操作。入队或出队，建空队列，判队空或队满等操作。尾部插入尾部插入首部删除首部删除队列队列 （Queue）是仅在是仅在表尾表尾进行插入操作，在进行插入操作，在表头表头进行删除操进行删除操作的线性表。它是一种先进先出作的线性表。它是一种先进先出（）（）的线性表。的线性表。例如：队列例如：队列 Q= (a1 , a2 , a3 , .,an-1 , an )在队尾插入元素称为在队尾插入元素称为；在队首删除元素称为；在队首删除元素称为。队首队首队尾队尾问：为什么要设计队列？它有什么独特用途？问：为什么要设计队列？它有什么独特用途？1. 离散事件的模拟离散事件的模拟（模拟事件发生的先后顺序

5、（模拟事件发生的先后顺序, ,例如例如 CPUCPU芯片中的指令译码队列）芯片中的指令译码队列）；2. 操作系统中的作业调度操作系统中的作业调度（一个（一个CPUCPU执行多个作业）执行多个作业）；3. 简化程序设计。简化程序设计。答：答：关键是掌握关键是掌握入队入队和和出队出队操作。操作。具体实现依具体实现依存储结构存储结构（链队或顺序队链队或顺序队）的不同而不同。）的不同而不同。 2. 队的抽象数据类型定义队的抽象数据类型定义：ADT Queue数据对象：数据对象：D=数据关系：数据关系：R=基本操作：基本操作： ADT Queue建队、入队或出队、判队空建队、入队或出队、判队空或队满等，

6、教材或队满等，教材P59-60罗列罗列了了9 9种基本操作种基本操作。重点是循环重点是循环顺序队顺序队链链队列队列类型定义：类型定义： typedef struct QueuePtr front ; /队首指针队首指针 QueuePtr rear ; /队尾指针队尾指针 LinkQueue;结点结点类型定义：类型定义： typedef Struct QNode QElemType data; /元素元素 Struct QNode *next; /指向下一结点的指针指向下一结点的指针 Qnode , * QueuePtr ;关于整个链队的关于整个链队的总体描述总体描述链队中任一链队中任一结点的结

7、构结点的结构因简单而先介绍因简单而先介绍讨论：讨论： 空链队的特征？空链队的特征？Q(队尾队尾)(队首队首)fronta1a2a3rearpfrontrear 怎样实现链队的怎样实现链队的入队和出队操入队和出队操作？作？ 链队会满吗？链队会满吗？front=rear一般不会，因为删除时有一般不会，因为删除时有free动作。除非内存不足！动作。除非内存不足！入队（尾部插入）：入队（尾部插入）：rear-next=S; rear=S;出队（头部删除）：出队（头部删除）：front-next=p-next;SD链队示意图：链队示意图：完整操作函数完整操作函数见教材见教材P62P62下下课堂练习：课堂

8、练习：（1 1） 在一个链队中，假设在一个链队中，假设f f和和r r分别为队首和队尾指针，分别为队首和队尾指针，则插入则插入s s所指结点的运算时所指结点的运算时 。A.A. f-next=f-next=s;fs;f=s; B. r-next=s; r=s=s; B. r-next=s; r=s；C. s-next=C. s-next=r;rr;r=s; D. s-next=f; f=s;=s; D. s-next=f; f=s;（2 2） 在一个链队中，假设在一个链队中，假设f f和和r r分别为队首和队尾指针，分别为队首和队尾指针，则删除一个结点的运算时则删除一个结点的运算时 。A.A.

9、 r=f-next; B. r=r-nextr=f-next; B. r=r-next；C. f=f-next; D. f=r-next;C. f=f-next; D. f=r-next;采用动态分配空间的形式采用动态分配空间的形式顺序队类型定义：顺序队类型定义：建队建队核心语句核心语句：q . base=(QElemType *)malloc(sizeof (QElemType ）* QUEUE_MAXSIZE); /分配空间分配空间关于整个顺序关于整个顺序队的总体描述队的总体描述#define QUEUE-MAXSIZE 100 /最大队列长度最大队列长度 typedef struct Q

10、ElemType *base; /队列的基址队列的基址 int front; /队首指针队首指针 int rear; /队尾指针队尾指针 SqQueue顺序队中每个结点的结构描述在此省略，是顺序队中每个结点的结构描述在此省略，是QElemTypeQElemType类型。类型。Q(队尾队尾)(队首队首)front a1 a2 a3data a40.99rear 队列会满吗？队列会满吗？极易装满！极易装满！因为数组通因为数组通常有长度限制，而其前常有长度限制，而其前端空间无法释放。端空间无法释放。 空队列的特征？空队列的特征？ 约定：约定：front=rear队尾后地址队尾后地址入队入队(尾部插入

11、尾部插入)： Qrear=e; rear+ ; 出队出队(头部删除头部删除)： e=Qfront; front+; 讨论：讨论：有有缺缺陷陷 怎样实现入队和出队怎样实现入队和出队操作？操作？核心语句如下核心语句如下：用用base做数组名做数组名e顺序队示意图：顺序队示意图：解决假溢出的途径解决假溢出的途径采用循环队列采用循环队列答：答：在顺序队中，当尾指针已经到了数组的在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还上界，不能再有入队操作，但其实数组中还有空位置，这就叫有空位置，这就叫“假溢出假溢出”。问：什么叫问：什么叫“假溢出假溢出” ？如何解决？如何解决？a3a2

12、a10123N-1rearfront新问题：新问题：在循环队列中，空队特征是在循环队列中，空队特征是front=rear；队满时也会有队满时也会有front=rear；判决条件将出现二义性！判决条件将出现二义性！解决方案有三：解决方案有三：使用一个使用一个计数器计数器记录队列中元素个数（即队列长度）；记录队列中元素个数（即队列长度）；加加设标志位设标志位，删除时置删除时置1,1,插入时置插入时置0,0,则可识别当前则可识别当前front=rear属于何种情况属于何种情况 人为人为浪费一个单元浪费一个单元，则队满特征可改为，则队满特征可改为front=(rear+1)%N；a3a2a1front

13、rear 0 1 2 3 . .N-1队空条件队空条件 : front = rear (初始化时：初始化时：front = rear )队满条件队满条件： front = (rear) % N (N=maxsize)队列长度队列长度（即数据元素个数）（即数据元素个数）：L=（Nrearfront）% N J2 J3J1 J4 J5frontrear 实际中常选用实际中常选用方案方案3（人为人为浪费一个单元浪费一个单元）：即即front和和rear二者之一指向实元素，另一个指向空闲元素。二者之一指向实元素，另一个指向空闲元素。 问问3： 在具有在具有n个单元的循个单元的循环队列中，队满时共有多少

14、环队列中，队满时共有多少个元素？个元素？ N-1个个6 问问1：左图中队列左图中队列maxsize N=？问问2：左图中左图中队列长度队列长度L=？5（）（） rf （）（）（nfr）% n （）（）nrf （）（） （nrf）% n要分析要分析4 4种公式哪种最合理？种公式哪种最合理？当当 r f 时（时（A）合理；）合理；当当 r f 时（时（C）合理；）合理；答：答：综合综合2种情况，以（种情况，以（D）的表达最为合理的表达最为合理例例2：在一个循环队列中，若约定队首指针指向队首元素在一个循环队列中，若约定队首指针指向队首元素的的前一个前一个位置。那么，从循环队列中删除一个元素时，其位置

15、。那么，从循环队列中删除一个元素时，其操作是操作是 先先 移动队首指针移动队首指针取出元素取出元素，后，后。例例1：数组数组n用来表示一个循环队列，用来表示一个循环队列，f 为当前队列头元为当前队列头元素的素的前一前一位置，位置，r 为队尾元素的位置。假定队列中元素的个为队尾元素的位置。假定队列中元素的个数小于数小于n，计算队列中元素的公式为，计算队列中元素的公式为:例例3： 一循环队列如下图所示，若先删除一循环队列如下图所示，若先删除4个元素，接着再个元素，接着再插入插入4个元素，请问队头和队尾指针分别指向哪个位置个元素，请问队头和队尾指针分别指向哪个位置? J2 J3J1 J4 J5fro

16、nt=2rear=1解：解：由图可知，队头和队尾指针的初态分别为由图可知，队头和队尾指针的初态分别为front=2和和rear=1。删除删除4个元素后个元素后， f= (2+4) %6=0再插入再插入4个元素后，个元素后，r=(1+4)%6=5 front=0J6 J5J7J8 J9rear=5rear=1front=0讨论：循环队列的基本操作如何实现？讨论：循环队列的基本操作如何实现？以建队、入队和出队三种基本操作为例以建队、入队和出队三种基本操作为例1）初始化一个空队列）初始化一个空队列算法要求：生成一空队列算法要求：生成一空队列算法操作：算法操作：为队列分配基本容量空间为队列分配基本容量

17、空间 设置队列为设置队列为空队列空队列，其特征即：，其特征即： front=rear=0（也可为任意单元，如（也可为任意单元，如1，2，甚至甚至-1 ）建队的完整算法：建队的完整算法：Status InitQueue ( SqQueue &q ) /初始化空循环队列初始化空循环队列 q q q . base=(QElemType *)malloc(sizeof(QElemType）* QUEUE_MAXSIZE); /分配空间分配空间if (!q.base) exit(OVERFLOW);/内存分配内存分配失败，退出程序失败，退出程序 q.front =q.rear=0; /置空队列置

18、空队列 return OK; /InitQueueInitQueue; ;#define QUEUE-MAXSIZE 100 /最大队列长度最大队列长度 typedef struct QElemType *base; /队列的基址队列的基址 int front; /队首指针队首指针 int rear; /队尾指针队尾指针 SqQueue算法说明：向循环队列的算法说明：向循环队列的队尾插入队尾插入一个元素一个元素分析分析：(1) 插入前应当先判断队列是否满？插入前应当先判断队列是否满？ if ( q . rear + 1 ) % QUEUE_MAXSIZE )=q.front) return E

19、RROR;(2）插入动作插入动作 q.base q.rear = e; q.rear = ( q . rear + 1 ) % QUEUE_MAXSIZE;2） 入队操作入队操作队列尺寸队列尺寸Status EnQueue(SqQueue &q, QElemType e)/向循环队列向循环队列 q q 的队尾加入一个元素的队尾加入一个元素 e e if ( (q.rear+1) % QUEUE_MAXSIZE = = q.front ) return ERROR ; /队满则上溢，无法再入队队满则上溢，无法再入队 q.base q.rear = e; /新元素新元素e e入队入队 q.

20、rear = ( q . rear + 1 ) % QUEUE_MAXSIZE; /指针后移指针后移 return OK; / / EnQueueEnQueue; ;入队操作完整算法入队操作完整算法rearrear指针在元素入队后再加指针在元素入队后再加3）出队操作）出队操作算法说明：删除队首元素，返回其值算法说明：删除队首元素，返回其值 e 分析：分析： （1） 在删除前应当判断队列是否空？在删除前应当判断队列是否空？ if (q.front = q.rear ) return ERROR; （2）删除动作分析；删除动作分析； 前面约定指针前面约定指针frontfront指向队首元素的位置，

21、故指向队首元素的位置，故： e = q.base q.front ; q.front = ( q.front + 1 ) % QUEUE_MAXSIZE; 队列尺寸队列尺寸 front front指针在元素出队后再加指针在元素出队后再加Status DeQueue ( SqQueue &q, QElemType &e) /若队列不空，删除循环队列若队列不空，删除循环队列q q的队头元素的队头元素， /由由 e e 返回其值，并返回返回其值，并返回OKOK if ( q.front = = q.rear ) return ERROR;/队列空队列空 e = q.base q.fr

22、ont ; q.front=(q.front+1) % QUEUE_MAXSIZE ; return OK; / / DeQueueDeQueue出队操作完整算法出队操作完整算法对这对这4 4个数据元素进行的队操作是个数据元素进行的队操作是进队进队2 2次，出队次，出队1 1次，再进次，再进队队2 2次，出队次，出队1 1次次；这时，第；这时，第1 1次出队得到的元素是次出队得到的元素是 ？ ，第第2 2次出队得到的元素是次出队得到的元素是 ？ 。经操作后，最后在队中的。经操作后，最后在队中的元素还有元素还有 ？ 个，队尾指针指向个，队尾指针指向 ？ 。 解：解：此题用此题用V4V4大小数组即可大小数组即可（V0V0V3 4V3