《数据结构课件ppt第三章》由会员分享，可在线阅读，更多相关《数据结构课件ppt第三章（40页珍藏版）》请在金锄头文库上搜索。
1、3.3 栈的应用举例,例一、 数制转换 算法基于原理： N = (N div d)d + N mod d,例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,计算顺序,输出顺序,void conversion () InitStack(S); scanf (“%d“, / conversion,ADT Queue 数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头， an
2、端为队列尾,基本操作：,3.4 队列的类型定义, ADT Queue,队列的基本特征,a1,a2,a3,an,. . .,队头,队尾,队尾进行插入操作；队头进行删除操作。 是先进先出线性表。,InitQueue(&Q) 操作结果：构造一个空队列Q。 DestroyQueue(&Q) 初始条件：队列Q已存在。 操作结果：队列Q被销毁， 不再存在。,QueueEmpty(Q) 初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。,QueueLength(Q) 初始条件：队列Q已存在。 操作结果：返回Q的元素个数，即队列的长度。,GetHead(Q, &e) 初始条
3、件：Q为非空队列。 操作结果：用e返回Q的队头元素。,a1,a2,an, ,ClearQueue(&Q) 初始条件：队列Q已存在。 操作结果：将Q清为空队列。,EnQueue(&Q, e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。,a1,a2,an,e, ,DeQueue(&Q, &e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。,a1,a2,an, ,补充知识-结构体,结构体是一种构造类型，满足将不同类型的数据组合成一个整体。 结构体类型一般形式为： struct 结构体名 成员列表; struct student int num; ch
4、ar name20; char sex; ; struct student stu1; /定义变量stu1 struct student *p; /定义指针变量p，指向一个struct student类型 的数据,定义结构体变量 struct student stu1; struct student *p; /p指向一个struct student类型的数据 引用结构体变量中成员的方法 结构体变量名.成员名 stu1.num: stu1变量中的num成员 (*p).num: *p变量中的num成员 为了方便使用和直观， (*p).num改用p-num来代替，表示p所指向的结构体变量中的num成
5、员。,3.5 队列类型的实现,链队列链式映象,循环队列顺序映象,typedef struct QNode / 结点类型 QElemType data; struct QNode *next; QNode, *QueuePtr;,链队列链式映象,typedef struct / 链队列类型 QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;,a1,an,Q.front Q.rear,Q.front Q.rear,空队列,头指针和尾指针都指向头结点,Status InitQueue (LinkQueue ,Status EnQueue (
6、LinkQueue ,Q.front,Q.rear,e,p,Status DeQueue (LinkQueue ,e,p,Q.front,Q.rear,3.5 队列类型的实现,链队列链式映象,循环队列顺序映象,队列的顺序表示,队列的顺序存储结构和顺序栈类似：用一组地址连续的存储单元依次存放从队列头到队列尾的元素外，还附设两个指针front指向队头元素，rear指向队尾元素的下一个位置。 约定空队列：front=rear=0; 插入新队尾元素，rear+1；每删除队头元素，front+1；,Q.front,Q.rear,Q.front,Q.rear,A,B,C,Q.front,Q.rear,C,
7、Q.front,Q.rear,F,图1,图2,图3,图4,1：空队列 2：A,B,C相继入队列 3：删除A,B后 4：不能插入新的元素但队列未满,0,1,2,3,4,5,循环队列顺序映象,为了有效利用存储空间，采用循环队列的形式，指针和队列元素间的关系不变。,Q.rear,a1,a2,a3,0,1,2,4,3,5,Q.front,循环队列示意图,Q.front,Q.rear,队列满,队列空,队列空和队列满的判定条件,队列满：当队列空间都被占满时，Q.rear=Q.front。由于队列空时，也满足条件Q.rear=Q.front，因此Q.rear=Q.front无法判别队列是“空”还是“满”。
8、约定队列满的条件为：队列头指针在队列尾指针的下一位置。 队列空的条件：Q.front=Q.rear=0; 思考：为什么顺序栈不采用循环栈的形式？,#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue;,循环队列的定义,Status InitQueue (SqQueue ,Status EnQueue (SqQueue ,Status DeQue
9、ue (SqQueue ,1. 掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。,2. 熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。,3. 熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。,本章学习要点,课堂习题,设栈的输入序列为（1，2，3，4），则（）不可能是其出栈序列。 1243 2134 1432 4312 3214 答案：D 输入序列1,2,n得到的输出序列P1,P2Pn, 不可能出现ijk时有Pj=Pk=Pi;d项的4312可知：i=2,j=3,k=4，有pi=3,pj=1,pk=2,pjpkpi,故选D。,2.
10、 若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？ 1和5 2和4 4和2 5和1 答案：B,3. 设栈的输入序列是1，2，n，若输出序列的第一个元素是n，则第i个输出元素是（）。 不确定 n-i+1 i n-i 答案：B,4. 假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判队空的条件是（）。 front+1=rear front=rear+1 front=0 front=rear 答案：D,5. 假定一个顺序循环队列存储于数组An中，其队首和队尾指针分别用f
11、ront和rear表示，则判断队满的条件是（） (rear-1)%n=front; (rear+1)%n=front; rear=(front-1)%n; rear=(front+1)%n; 答案：B,6. 已知输入序列为1234，则输入受限（仅由一端输入）但输出不受限（两端均可输出）的双端队列不可以得到（）输出序列。 4231 1324 3214 4213 2341 答案：A,D,栈S的输入元素的顺序为1、2、3、4、5，要在栈S的输出端得到43521，则应进行栈的基本运算表示应为： push(s,1) push(s,2) push(s,3) push(s,4) pop(s) pop(s)
12、push(s,5) pop(s) pop(s) pop(s),写出下列程序段的输出结果（栈的元素类型SElemType为char）,Void main() Stack S; char x,y; InitStack(S); x=c; y=k; Push(S,x); Push(S,a); Push(S,y); Pop(S,x); Push(S,t); Push(S,x); Pop(S,x); Push(S,s); while(!StackEmpty(S) Pop(S,y); printf(y); printf(x); ,已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中
13、删除自第i个元素起共len个元素后，将它们插入到表lb中第j个元素之前。试问此算法是否正确？若有错，则请改正之。,Status DeleteAndInsert Sub(LinkedList la, LinkedList lb, int i, int j, int len if(inext; k+; q=p; while(knext; k+; s=lb; k=1; while(knext; k+; s-next=p; q-next=s-next; return OK; /DeleteAndInsertSub,修改后,Status DeleteAndInsert Sub(LinkedList /DeleteAndInsertSub,
