Microsoft PowerPoint - 3栈和队列.ppt [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - 3栈和队列.ppt [兼容模式]"

淦瞿
5 years ago
Views:

1 队列的类型定义定义队列是必须在一端删除 ( 队头 front), 在另一端插入 ( 队尾 rear) 的线性表特性先进先出 (FIFO, First In First Out) rear front 117

2 队列的类型定义 ADT Queue{ 数据对象 : 具有线形关系的一组数据操作 : bool EnQueue(Queue &Q, ElemType e); // 入队 bool DeQueue(Queue &Q); // 出队 bool GetFront(Queue Q,ElemType &e);// 取队头 bool IsEmpty(Queue Q); // 空吗? bool Clear(Queue &Q); // 清空 ; 118

3 队列的表示 : 链式表示链式表示和实现 typedef struct qnode{ ElemType data; struct qnode *next; QNode; front rear data next typedef struct{ QNode* front; QNode* rear; LinkQueue;

4 队列的表示 : 链式表示初始化 bool InitQueue(LinkQueue& Q){ Q.front = Q.rear = (QNode*)malloc(sizeof(QNode)); if(!q.front) return false; Q.front->next = NULL; return true; 120

5 队列的表示 : 链式表示入队 bool EnQueue(LinkQueue& Q, ElemType e){ QNode *p = (QNode *) malloc(sizeof(qnode)); if(!p) return false; p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return true; 121

6 bool EnQueue(LinkQueue& Q, ElemType e){ QNode *p = (QNode *)malloc(sizeof(qnode)); if(!p) return false; p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return true; Q.rear p Q.front x e 122

7 队列的表示 : 链式表示出队 bool DeQueue(LinkQueue& Q) { if(q.front = Q.rear) return false; QNode *p = Q.front->next; Q.front->next = p->next; if(q.rear == p) Q.rear = Q.front; free(p); return true; 123

8 bool DeQueue(LinkQueue& Q){ if(q.front == Q.rear) p = Q.front->next; return false; Q.front->next = p->next; if(q.rear == p) Q.rear = Q.front; free(p); 最后一个元素 return true; Q.front p p Q.rear xy x y 124

9 队列的表示 : 顺序表示顺序表示和实现用数组存储数据初始化 :front = rear = 0 入队 :rear ++ 出队 :front Q.rear Q.front 125

10 队列的表示 : 顺序表示插入和删除 J3 J2 J1 Q.rear Q.front 126

11 队列的表示 : 顺序表示指针的指法 front 指向队头元素 rear 指向队尾元素的后一个单元其实也可以如此错开 front 指向队头元素的前一个单元 rear 指向队尾元素为什么如此呢? 3 Q.rear 2 J3 1 J2 Q.front 0 127

12 队列的表示 : 顺序表示原因 1: 方便计算元素个数元素的个数 = rear-front 而不用 = rear-front J3 1 J2 0 Q.rear Q.front 128

13 队列的表示 : 顺序表示原因 2: 便于判别空队列如果不错开, 则空队列和只有一个元素时, 都是 front=rear, 难以区别或者空队列有可能有两种情况 3 2 J3 1 0 J2 J1 Q.rear Q.front 129

14 队列的表示 : 顺序表示线性队列的缺点不论是插入还是删除元素 front 和 rear 都只是 ++ 导致 : 数组空间有限,rear 总有一天会达到数组顶端 front 之前空间再不会被用到 J4 J3 J2 J1 Q.rear Q.front 130

15 队列的表示 : 顺序表示思考既然上面不够, 下面浪费何不利用下面的空间? 循环队列当 rear 向上走到顶的时候, 重新返回到最下端 ( 如果下面有空闲单元 ) J4 J3 J2 J1 J5 Q.rear Q.front 131

16 队列的表示 : 顺序表示循环队列 rear rear J7 J6 J5 J4 J8 J1 J9 J2 J3 0 1 front rear rear 3 2 空队列 rear front 132

17 队列的表示 : 顺序表示如何区别空队列和满队列? rear rear J7 J6 J5 J4 J8 J1 J2 J3 0 1 front rear 3 2 空队列满队列 :front=rear rear 133

18 队列的表示 : 顺序表示如何区别空队列和满队列? 5 4 方法一 : 专门设置一个标记方法二 : 还剩一个单元时就算满空 front rear 5 4 rear 6 7 J7 J6 J5 J4 3 满 J1 J2 J front 134

19 队列的表示 : 顺序表示循环队列类型定义 typedef struct { ElemType *base; int front; int rear; int capacity; SqQueue; 135

20 队列的表示 : 顺序表示初始化 bool InitQueue(SqQueue &Q,int cap) { Q.base = (ElemType*) malloc (cap*sizeof(elemtype)); if(!q.base) return false; Q.front = Q.rear = 0; Q.capacity = cap; return true; 136

21 队列的表示 : 顺序表示得到队列长度即元素个数 bool QueueLength(SqQueue Q) { return (Q.rear - Q.front + Q.capacity) % Q.capacity; 137

22 队列的表示 : 顺序表示得到队列长度 rear rear J7 J6 J5 J4 3 J8 J1 J9 J2 J 空队列 rear front front rear rear rear<front rear>=front 时 : length=rear-front length=(rear-front+8)%8 =7-2=5 =(0-2+8)%8=6 138

23 队列的表示 : 顺序表示入队 bool EnQueue(SqQueue &Q, ElemType e){ if((q.rear+1)%q.capacity== Q.front){ return false; // 队列满 Q.base[Q.rear] = e; Q.rear = (Q.rear + 1)%Q.capacity; return true; 139

24 队列的表示 : 顺序表示注意满队列 :rear 下一个就是 front (rear+1) % MAXQSIZE == front rear 指向下一个单元 rear=(rear+1)%maxqsize 5 4 rear 6 7 J7 J6 J5 J4 3 J1 J2 J3 2 front

25 队列的表示 : 顺序表示出队 bool DeQueue(SqQueue &Q){ if(q.front == Q.rear) return false; // 空队列 Q.front = (Q.front+1)%Q.capacity; return true; 141

26 队列的表示 : 顺序表示取队头 bool Front(SqQueue &Q,ElemType &e){ if(q.front == Q.rear) return false; // 空队列 e = Q.base[Q.front]; return true; 142

27 队列的表示 : 顺序表示注意空队列 :rear==front front 指向下一个单元 front = (front+1)%maxqsize rear J7 J6 J5 J4 3 J1 J2 J3 2 front

28 农夫过河问题一个农夫带着一只狼一只羊和一棵白菜过河如果没有农夫看管, 则狼要吃羊, 羊要吃白菜但是船很小, 只够农夫带一样东西过河问农夫该如何解此难题? 144

29 安全与不安全状态用四位二进制数顺序分别表示农夫狼白菜和羊的当前状态 ( 位置 ) 用 0 表示在河的南岸,1 表示在河的北岸例如整数 5( 其二进制表示为 0101) 表示农夫和白菜在河的南岸, 而狼和羊在北岸安全状态与不安全状态 : 单独留下白菜和羊, 或单独留下狼和羊在某一岸的状态是不安全的 145

30 求解 : 状态空间搜索从初始状态 0(0000) 出发搜索可能正确的安全状态过渡序列, 直到最终状态 16(1111) 广度优先搜索 : 在搜索过程中总是先考虑当前状态的所有状态, 再进一步考虑更后面的各种情况 146

31 数据结构 1). 顺序表 route[]: 状态 i 是否已被访问过, 若已被访问过则在这个顺序表元素中记入前驱状态值 route[i] = -1, 表示未访问过 ; 则 route[i] = pre, 表示状态 i 已经访问过, 且是从安全状态 pre 过渡来的最后可以利用 route 顺序表元素的值建立起正确的状态路径 ) 整数队列 moveto: 每个元素表示可以安全到达的状态 147

32 基于队列的状态遍历

33 基于队列的状态遍历

34 基于队列的状态遍历

35 基于队列的状态遍历

36 基于队列的状态遍历

37 基于队列的状态遍历 Path:15,6,14,2,11,1,9,0 从初始状态 0 到最终状态 15 的动作序列为 :

38 角色状态从四位二进制整数检测每个对象是否在北岸 bool farmer(int location) { return (0!= (location & 0x08)); bool wolf(int location) { return (0!= (location & 0x04)); bool cabbage(int location) { return (0!= (location & 0x02)); bool goat(int location) { return (0!=(location & 0x01));

39 安全状态的判断 int safe(int location){// 状态安全则返回 1 if((goat(location)==cabbage(location)) &&(goat(location)!=farmer(location))) return 0; // 羊吃白菜 if((goat(location)==wolf(location)) &&(goat(location)!=farmer(location))) return 0; // 狼吃羊 return 1; // 其他状态是安全的 155

40 农夫过河算法准备一个数组 route 记录路径准备一个队列 moveto 记录多重选择初始状态 0(0000) 加入 moveto 和 route while( 队列非空 && 还没到终止状态 ){ state = DeQueue(moveTo); // 出队当前状态 for( 每个从 state 可以到达的状态 newstate) 输出结果 if(newstate 安全且未访问过 ) { EnQueue(moveTo, newstate); route[newstate] = state; 156

41 农夫过河算法 { 初始化顺序表 Route 和安全队列 moveto; 初始安全状态 0(0000) 入队列 moveto, Route[0] = 0, while(isempty(moveto)&&(route[15]==-1)){ DeQueue(moveTo,location); // 出队当前安全状态 for( 每个从 location 可以过渡到的状态 newlocation) // 农夫 ( 附带同侧物品 ) 移动 if (newlocation 安全且未访问过 ) EnQueue(moveTo, newlocation); if(route[15]!=-1) // 已经到达终点了, 打印路径 for(location=15;location>=0; location=route[location]){ printf("the location is : %d\n",location); if (location==0) return 1; else printf( 问题无解 \n"); 3 栈与队列 jn.008.net 157

42 int farmerproblem( ){ int movers, i,location, newlocation; int route[16]; /* 记录已考虑的状态路径 */ for(i=0;i<16;i++) route[i]=-1; SqQueue moveto; InitQueue(moveTo); EnQueue(moveTo,0x00); route[0]=0; while(!queueempty(moveto)&&(route[15]==-1)){ 2) OutQueue(moveTo,location);/* 得到现在的状态 */ for(movers=1;movers<8;movers<<=1){ 1) 158

43 for(movers=1;movers<8;movers<<=1){ /* 农夫总是在移动, 随农夫移动的也只能是在农夫同侧的东西 */ if ((0!=(location & 0x08)) { ==(0!=(location & movers))) newlocation=location^(0x08 movers); if(safe(newlocation) &&(route[newlocation]==-1){ route[newlocation]=location; EnQueue(moveTo,newlocation); 159

44 if(route[15]!=-1){ /* 打印出路径 */ printf("the reverse path is : \n"); for(location=15;location>=0;location=route[location]) { printf("the location is : %d\n",location); if(location==0) return 1; else printf("no solution.\n"); return 0; 160

45 队列的应用 : 农夫过河问题思考广度优先搜索换成深度优先搜索呢? 需要一个栈以回退到上级的状态, 以便搜索上级状态的下一个子状态 161

Microsoft PowerPoint - ds-1.ppt [兼容模式]

Microsoft PowerPoint - ds-1.ppt [兼容模式] http://jwc..edu.cn/jxgl/ HomePage/Default.asp 2 说明总学时 : 72( 学时 )= 56( 课时 )+ 16( 实验 ) 行课时间 : 第 1 ~14 周周学时 : 平均每周 4 学时上机安排待定考试时间 : 课程束第 8 11 12 章的内容为自学内容 ; 目录中标有