数据结构课件-第三章.pptVIP

3.4队列的应用 队列可应用于杨辉三角形的打印。 杨辉三角形的特点是两个腰上的数字都为1，其他位置上的数字是其上一行与之相邻的两个数之和。所以在打印过程中，第i行上的元素由第i-1行中的元素来生成。我们可以利用循环队列实现打印杨辉三角形的过程。在循环队列中依次存放第i-1行上的元素，然后逐个出队列并打印，同时生成第i行元素并入列。 下面给出打印杨辉三角形的前n行元素的具体算法，N为杨辉三角形的行数： void YangHuiTriangle( ) { SeqQueue Q; InitQueue(Q); EnQueue(Q,1); /* 第一行元素入队*/ for(n=2;n=N;n++) /* 产生第n行元素并入队， 同时打印第n-1行的元素*/ { EnQueue(Q,1); /* 第n行的第一个元素入队*/ for(i=1;i=n-2;i++)  /* 利用队中第n-1行元素产生第n行的中间n-2个元素并入队*/ {DeQueue(Q,temp); Printf(″%d″,temp); /* 打印第n-1行的元素*/ GetHead (Q,x); /* 取新的队头元素*/ temp=temp+x; /*利用队中第n-1行元素产生第n行元素*/ EnQueue(Q,temp);  } DeQueue(Q,x);  printf(″%d″,x); /* 打印第n-1行的最后一个元素*/ EnQueue(Q,1) /* 第n行的最后一个元素入队*/ } } 3.5 回到工作场景 通过学习，我们应该已经掌握了栈的创建方法以及栈的基本操作的实现，足以完成工作场景中的任务。下面我们回到第3.1节的工作场景中，完成工作任务。 【工作过程一】问题解析： 【工作过程二】编写代码，实现算法： 【工作过程3】系统运行 3.6应用实践 3.6.1嵌入式系统中断模拟设计 1. 实践内容 单片机或嵌入式系统中断模拟设计。 2. 实践目的 懂得如何使用栈解决问题。 掌握栈在单片机或者嵌入式系统中的简单应用。 3、实践过程 3.6.2学生舞会舞伴配对系统设计 1. 实践内容 舞会舞伴配对系统设计 2. 实践目的 懂得如何使用队列解决问题。 3、实践过程 假设在舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题，先入队的男士或女士亦先出队配成舞伴。 本章小结 本章主要讨论了两种运算受限的线性表：栈和队列。同时给出了它们的基本概念、存储结构以及基本操作的实现，通过例子的讨论来加深对栈和队列的理解。 对于栈来说，它的插入和删除都是在线性表的同一端进行的。存储结构有两种：顺序存储和链式存储。请注意顺序存储结构时的栈空和栈满的判断条件，出栈之前要判断栈是否空，入栈之前要判断栈是否满。 对于队列来说，它的插入运算在表的一端进行，而删除运算却在表的另一端进行。它的存储结构也有两种：顺序存储和链式存储。在使用顺序存储结构时，为了能够重复利用有限的存储空间，提出循环队列，应注意循环队列队空和队满的判断条件。 数据结构 主编 许绘香 段明义 中国水利水电出版社 第三章 栈和队列 栈和队列是两种特殊的线性结构。从数据的结构角度看，它们是线性表，从操作的角度看，它们是操作受限的线性表。在日常生活中经常会遇到栈或队列的实例。例如，停车场车辆的调度要用到栈，排队购物要用到队列。 3.1工作场景导入  【工作场景】 某公司有一个地下停车场如图3-1-1，此停车场是一个可停放n辆汽车的狭长通道,且只有一个大门可供汽车进出.汽车在停车场内按照车辆到达时间的先后顺序, 依次从停车场最里向大门口处停放(最先到达的第一辆车放在停车场的最里面)。 若车场内已停满n辆汽车,则后来的汽车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内的某辆车要开走时,在它之后进入的车辆必须退出车场为它让路,待该辆车开出大门外,其他车辆再按照原次序进入车场,每辆车停放在车场的车在它离开停车场时必须按照它停留的时间长短交纳费用. 如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且