LAB05队列的操作及应用.doc

算法与数据结构实验报告Lab05队列的操作及应用【实验目的和要求】1掌握队列的顺序表示和链表表示下的基本操作；2深入理解深度优先搜索和广度优先搜索的思想并能正确描述其算法；3会应用广度优先搜索算法解决较复杂的问题。【实验内容】1编写一个C源程序，其中包含顺序表示的空队列的创建、判断队列是否为空、进队、出队、取队列头部元素等操作。2编写一个C源程序，其中包含链表表示的空队列的创建、判断队列是否为空、进队、出队、取队列头部元素等操作。3. 简述深度优先搜索和广度优先搜索的思想，并给出具体的算法步骤。4应用广度优先搜索算法求解农夫过河问题。【实验仪器与软件】1CPU主频在1GHz以上，内存在512Mb以上的PC；2VC6.0，Word 2003及以上版本。实验讲评：实验成绩： 评阅教师：2012 年 月 日 - 20 -Lab05队列的操作及应用一、顺序表示的队列基本操作1顺序表示的队列操作基本源程序#include #include typedef int DataType;#define MAXNUM 100/*队列中最大元素个数*/struct SeqQueue/*顺序队列类型定义*/int f,r;DataType*q;/*为了算法设计上的方便：f指出实际队头元素所在的位置，r指出实际队尾元素所在位置的下一个位置。*/typedef struct SeqQueue*PSeqQueue;/*顺序队列类型的指针类型*/创建空队列PSeqQueue createEmptyQueue_seq(int m) PSeqQueue paqu;paqu= (PSeqQueue)malloc(sizeof(struct SeqQueue);if (paqu!=NULL) paqu-f = NULL;paqu-r = NULL;else printf(Out of space! n);return paqu;判断队列是否为空int isEmptyQueue_seq( PSeqQueue paqu )return (paqu-f = NULL);进队运算void enQueue_seq( PSeqQueue paqu, DataType x ) /* 在队尾插入元素x */if( (paqu-r + 1) % MAXNUM = paqu-f )printf( Full queue.n );else paqu-qpaqu-r = x;paqu-r = (paqu-r + 1) % MAXNUM;出队运算void deQueue_seq( PSeqQueue paqu ) /* 删除队列头部元素*/if( paqu-f = paqu-r )printf( Empty Queue.n );else paqu-f = (paqu-f + 1) % MAXNUM;取队列头部元素运算DataType frontQueue_seq( PSeqQueue paqu ) if( paqu-f = paqu-r )printf( Empty Queue.n );else return (paqu-qpaqu-f);int main() /主函数 PSeqQueue pp; int n,m; printf(n please input the values(100) of n = ); scanf(%d, &n); printf( please input the values of m = ); scanf(%d, &m); pp =createEmptyQueue_seq(n); / 创建顺序表示的空队列 二、链表表示的队列基本操作1链表表示的队列基本操作源程序#include #include typedef int DataType;structNode;typedef struct Node*PNode;struct Node/*结点结构*/DataType info;PNode link;struct LinkQueue/*链接队列类型定义*/PNode f;/*头指针*/PNode r;/*尾指针*/;typedef struct LinkQueue *PLinkQueue;/*链接队列类型的指针类型*/创建链接表示的空队列PLinkQueue createEmptyQueue_link( int m ) PLinkQueue plqu;plqu= (PLinkQueue)malloc(sizeof(struct LinkQueue);if (plqu!=NULL) plqu-f = NULL;plqu-r = NULL;else printf(Out of space! n);return plqu;判断队列是否为空int isEmptyQueue_link( PLinkQueue plqu ) return (plqu-f = NULL);进队运算void enQueue_link( PLinkQueue plqu, Datatype x) PNode p;p = (PNode )malloc( sizeof( struct Node ) ); /*申请新结点空间*/if ( p = NULL )printf(Out of space!); /*申请新结点失败*/else p-info = x;p-link = NULL; /*填写新结点信息*/if (plqu-f = NULL) plqu-f = p; /*插入前是空队列*/else plqu-r-link = p; /*将新结点插入*/plqu-r = p; /*修改队尾指针*/出队运算void deQueue_link( PLinkQueueplqu) PNodep;if( plqu-f = NULL ) printf( Empty queue.n );/*队列已空*/else p = plqu-f;plqu-f = p -link; /*修改队头指针*/free(p); /*释放已经删除结点空间*/取队列头部元素运算Datatype frontQueue_link( PLinkQueue plqu ) if( plqu-f = NULL ) printf( Empty queue.n );/*队列已空*/else return (plqu-f-info);int main() /主函数 PLinkQueue pp; int n,m; printf(n please input the values(foot; 队列为空表明再无结点可扩展五、农夫过河问题求解1农夫过河问题一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。2问题需求分析他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。另外，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和白菜或者狼和羊单独在河的一边，自己离开。请问农夫该采取什么方案才能将所有的东西运过河呢？3抽象数据类型设计求解这个问题的最简单的方法是一步一步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。用计算机实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first) 搜索，另一种是深度优先(depth_first) 。广度优先：广度优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。要实现广度优先搜索，一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来，放在这个队列中，然后顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里。由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。4算法与数据结构的设计(1)安全状态的判断函数int safe(int location) / 若状态安全则返回true if (goat(location) = cabbage(location) & (goat(location) != farmer (location) return (0); / 羊吃白菜 if (goat(location) = wolf(location) & (goat(location) != farmer (location) return (0); / 狼吃羊 return (1); / 其他状态是安全的(2)个体状态判断函数int farmer(int location) /判断农夫的位置 return (0 != (location &0x08); int wolf(int location) /判断狼的位置 return (0 != (location &0x04); int cabbage(int location) /判断白菜的位置 return (0 != (location &0x02); int goat(int location) /判断羊的位置 return (0 != (location &0x01);5 算法的精化与程序的实现 精化:要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用0表示农夫或者某东西在河的南岸，1表示在河的北岸。因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。实现:完成了上面的准备工作，现在的问题变成：从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸) 为最终目标，并且在序列中的每一个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。为避免不必要的瞎费功夫，要求在序列中不应该出现重复的状态。为了实现广度优先搜索，算法中需要使用了一个整数队列moveTo，它的每个元素表示一个可以安全到达的中间状态。另外还需要一个数据结构记录已被访问过的各个状态，以及已被发现的能够到达当前这个状态的路径。由于在这个问题的解决过程中需要列举的所有状态(二进制0000 1111)一共16种，所以可以构造一个包含16个元素的整数顺序表来满足以上的要求。用顺序表的第i个元素记录状态i是否已被访问过，若已被访问过则在这个顺序表元素中记入前驱状态值，算法中把这个顺序表叫做route。route的每个分量初始化值均为-1，每当我们在队列中加入一个新状态时，就把顺序表中以该状态作下标的元素的值改为达到这个状态的路径上前一状态的下标值。route的一个元素具有非负值表示这个状态已访问过，或是正被考虑。最后我们可以利用route顺序表元素的值建立起正确的状态路径。6程序的调试与计算结果的分析用队列解决农夫过河问题#include #include typedef int DataType; 顺序队列：类型和界面函数声明 struct SeqQueue 顺序队列类型定义 int MAXNUM; / 队列中最大元素个数 int f, r; DataType *q;typedef struct SeqQueue *PSeqQueue; / 顺序队列类型的指针类型 PSeqQueue createEmptyQueue_seq(int m) 创建一个空队列 PSeqQueue queue = (PSeqQueue)malloc(sizeof(struct SeqQueue); if (queue != NULL) queue-q = (DataType*)malloc(sizeof(DataType) *m); if (queue-q) queue-MAXNUM = m; queue-f = 0; queue-r = 0; return (queue); else free(queue); printf(Out of space!n); / 存储分配失败 return NULL; int isEmptyQueue_seq(PSeqQueue queue) 判断队列是否为空 return (queue-f = queue-r); void enQueue_seq(PSeqQueue queue, DataType x)/ 在队尾插入元素x if (queue-r + 1) % queue-MAXNUM = queue-f) printf(Full queue.n); else queue-qqueue-r = x; queue-r = (queue-r + 1) % queue-MAXNUM; void deQueue_seq(PSeqQueue queue)/ 删除队列头部元素 if (queue-f = queue-r) printf(Empty Queue.n); else queue-f = (queue-f + 1) % queue-MAXNUM; DataType frontQueue_seq(PSeqQueue queue) if (queue-f = queue-r) printf(Empty Queue.n); else return (queue-qqueue-f); 个体状态判断函数int farmer(int location) /判断农夫的位置 return (0 != (location &0x08); int wolf(int location) /判断狼的位置 return (0 != (location &0x04); int cabbage(int location) /判断白菜的位置 return (0 != (location &0x02); int goat(int location) /判断羊的位置 return (0 != (location &0x01); 安全状态的判断函数int safe(int location) / 若状态安全则返回true if (goat(location) = cabbage(location) & (goat(location) != farmer (location) return (0); / 羊吃白菜 if (goat(location) = wolf(location) & (goat(location) != farmer (location) return (0); / 狼吃羊 re