数据结构第三章栈.ppt

* * * * * * * * * 这个问题的程序可以有很多种写法，一种最直接的想法是利用两个数组，其中一个存放已经计算得到的第 k 行的值，然后输出第 k 行的值同时计算第 k+1行的值。如此写得的程序显然结构清晰，但需要两个辅助数组的空间，并且这两个数组在计算过程中需相互交换。如若引入"循环队列"，则可以省略一个数组的辅助空间，而且可以利用队列的操作将一"琐碎操作"屏蔽起来，使程序结构变得清晰，容易被人理解。 * * * * * 1.错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。 2. 对 3. 对 4. 错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。 * 对 错，先进先出 * C * D * C * * 2、由于栈的操作仅限制在栈顶进行，也即元素的插入和删除都是在表的同一端进行的，因此不必设置头结点，头指针也就是栈顶指针， 4、由于出栈的输出序列即为队的输入和输出序列，故可不考虑队； 栈的容量至少为3 * 5、因出队在对头，入队在队尾，则对只设头指针的循环链表，查找对头只需一次，而查找队尾需要n次；对只设尾指针的循环链表，查找对头只需二次，查找队尾只需一次，故时间复杂度分别为O(1),O(n),O(1),O(1)。所以若用单链表表示队列，则应该选用带尾指针的循环链表。 打印杨辉三角 打印第k行，同时计算第k+1行的内容 处理每一行的程序为： do { DeQueue(Q, s); GetHead(Q, e); if (e!=0) printf (“%d”, e); EnQueue(Q, s+e); } while (e!=0); 利用循环队列计算二项式的过程： 假设只计算到第3行，则队列的最大容量为 。 1 1 0 0 q.front q.rear 1 1 0 0 1 q.front q.rear 1 1 0 2 1 q.front q.rear 1 1 0 2 1 q.front q.rear 1 0 0 2 1 q.front q.rear 1 0 1 2 1 q.front q.rear 5 1 0 1 2 1 q.front q.rear 1 0 1 2 3 q.front q.rear 1 0 1 3 3 q.front q.rear 1 0 1 3 3 q.front q.rear do { DeQueue(Q, s); GetHead(Q, e); if (e!=0) printf (“%d”, e); EnQueue(Q, s+e); } while (e!=0); 处理多行的程序： k=1; while?( k < n )?{　　//?通过循环队列输出前 n-1 行的值?EnQueue ( Q,0 );?　//?行界值“0”入队列?do {　　　 　　　 //?输出第 k 行，计算第 k+1 行? Dequeue( Q,s );?　 GetHead( Q,e );? if (e!=0) printf (“%d”, e); else printf(“\r\n”); 　　　EnQueue(Q,s+e);? }?while?(e!=0);?k++;? }?//?while 思考题: 为运动会比赛安排日程，即划分无冲突子集问题 问题描述：某运动会设立N个比赛项目，每个运动员可以参加1~3个项目。试问如何安排比赛日程，既可以使同一运动员参加的项目不安排在同一单位时间进行，又使总的竞赛日程尽可能短。 复习 栈 队列 ---------------- 顺序表 链表 ---------------- 应用 练习 判断对错： 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 栈和链表是两种不同的数据结构。 1.错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。 2. 对 3. 对 4. 错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。 练习 判断对错 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 对 错，先进先出 练习 单选题 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为( )。? A．i； B．n-i ； C．n-i+1； D．不确定? C 练习 假设顺序栈的定义为：?typ