算法设计与分析实验指导.doc

1、算法设计与分析实验指导书目 录实验一 单链表的建立插入及删除3实验二 多项式加法5实验三 集合的表示与操作算法设计7实验四 迷宫问题求解8实验五 树的建立及遍历11实验六 图的遍历的演示12实验七 哈希表的设计15实验八 Kruskal算法的设计17实验九 归并排序的分治策略设计19实验十 哈夫曼编码的贪心算法设计21实验十一 递归与迭代程序设计22实验十二 多段图问题的动态规划算法设计24实验十三 作业调度问题26实验十四 回溯算法设计28实验十五 搜索顺序的选择29实验十六 蛇和梯子31实验十七 游戏中寻址算法的设计34实验十八 旅行商问题36实验十九 骑士游历算法设计38实验二十 输油管

2、道问题的设计与实现40实验二十一 邮局选址问题的设计与实现42实验二十二 会场安排问题的设计与实现44实验二十三 目录树打印程序的设计46实验二十四 最少演员问题48附：实验（设计）报告参考格式50实验一 单链表的建立插入及删除实验目的1掌握单链表的建立插入及删除的算法；2进一步熟悉指针的用法； 预习要求1.认真阅读教材或参考书, 掌握线性表算法的基本思想；2.写出求解本实验的程序；3.设计好相应的测试用例。类型定义typedef struct Lnodeint data;struct Lnode *next;Lnode,*linklist;实验提示void create(link *h,in

3、t n)/创建单链表link p,q;int i;p=(link)malloc(sizeof(node);p-next=null;*h=p;q=p;for(i=1;idata);p-next=null;q-next=p;q=p;void print(link h)/输出单链表link p;p=h-next;while(p)printf(%d ,p-data);p=p-next;void insertlist(linklist *L,int i,int e)/在单链表的第i个元素之前插入元素值为e的结点void dellist(linklist *L,int i,int *e)/删除单链表的第i

4、个结点，被删结点通过 e返回实验步骤1. 先用插表头或插表尾的方法建立单链表并输出，并测试你的程序，直至正确为止；2. 再进行插入和删除程序的设计；3. 将你的程序和实录的界面存盘备用。 实验报告要求1. 阐述实验目的和实验内容；2. 提交模块化的实验程序源代码；3. 简述程序的测试过程，提交实录的输入、输出文件；4. 提交思考与练习题的代码和测试结果。思考与练习怎样用链表实现循环队列。实验二 多项式加法实验目的1熟练掌握在单链表中进行结点的插入和删除操作；2进一步熟悉指针的用法； 预习要求1.认真阅读教材或参考书, 掌握线性表算法的基本思想；2.写出求解本实验的程序；3.设计好相应的测试用例

5、。类型定义typedef struct Lnodeint coef,exp;struct Lnode *next;Lnode,*linklist;实验提示void create(link *h,int n)/创建一元多项式link p,q;int i;p=(link)malloc(sizeof(node);p-next=null;*h=p;q=p;for(i=1;icoef,&p-exp);p-next=null;q-next=p;q=p;void print(link h)/输出单链表link p;p=h-next;while(p)printf(%d,%d ,p-coef,p-exp);p=

6、p-next;void addlist(linklist *A, linklist B)/将A和B相加并通过A返回实验步骤1 先用插表尾的方法建立一元多项式，并将一元多项式输出，并测试你的程序，直至正确为止；2 进行一元多项式相加程序的设计；3 将你的程序和实录的界面存盘备用。 实验报告要求1 阐述实验目的和实验内容；2 提交模块化的实验程序源代码；3 简述程序的测试过程，提交实录的输入、输出文件；4提交思考与练习题的代码和测试结果。思考与练习写出约瑟夫问题的求解算法，即n个人坐成一圈，报m出圈，输出最后一个报m的人。实验三 集合的表示与操作算法设计实验目的. 了解集合的不同表示方法,掌握集合

7、的树结构表示方法;. 掌握树结构表示下集合的并运算与查找算法;. 编程实现集合的表示与操作算法.预习要求1. 认真阅读教材内容, 熟悉树结构表示的原理和操作算法;2. 设计和编制实验程序.参考数据类型或变量typedef ElemType int /* 实型或任意其它元素类型 */typedef struct ElemType elem; int tag; /* 根节点为负的整数,表示该集合的基数的负值,否则为父节点索引指针 */NODE;NODE *set; /* 用动态存储分配实现集合的树表示与存储 */参考子程序接口与功能描述void InitSet(NODE *set)功能: 根据集合

8、的基数动态分配存储, 输入各元素, 初始化子集森林.int Find(NODE *set, ElemType elem)功能: 在数组set中顺序查找元素elem,如果不成功, 返回-1; 否则,使用带压缩规则的查找算法,返回所在子集的根节点索引. int Union(NODE *set, ElemType elem1, ElemType elem2)功能: 应用Find算法首先找到elem1和elem2所在的子集, 然后应用带加权规则的并运算算法合并两个子集. 不成功时, 返回-1; 否则, 返回并集的根节点索引.实验步骤. 设计Find的测试方案和程序,输入测试数据,修改并调试程序,直至正

9、确为止;. 设计Union的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;. 待各功能子程序调试完毕,去掉测试程序,将你的程序整理成功能模块存盘备用.实验报告要求. 阐述实验目的和实验内容;. 提交实验程序的功能模块;. 记录最终测试数据和测试结果。思考题试用C语言实现集合的位向量表示, 并设计相应的并、交与查找运算算法.实验四 迷宫问题求解实验目的1熟悉栈用法；2掌握回朔法及试探法的程序设计； 预习要求1.认真阅读教材或参考书, 掌握栈用法的用法；2.写出求解本实验的程序；3.设计好相应的测试用例。实验提示设迷宫中数组的元素为1表示该点道路主的阻塞，为0表示可通。设maze11

10、为入口，mazemn 为出口。在maze11和mazemn的元素值必为0。在任意时刻，老鼠在迷宫中的位置可以用所在点的行下标与列下标（i,j）来表示，这样，老鼠在迷宫中的某点mazeij时，其可能的运动方向有八个。下图+表示某时刻老鼠所在的位置（i,j）,相邻的八个位置分别标以N、NE、E、SE、S、SW、W、NW（分别代表+点的北、东北、东、东南、南、西南、西、西北方向）；同时，相对于（i,j），这八个相邻位置的坐标的值都可以计算出来。但是，并非迷宫中的每一个点都有八个方向可走，四个角上就只有三个方向可供选择，边上只有五个方向可供选择。为了不在算法中每次都去检查这些边界条件，在迷宫外面套上一

11、圈，其元素值均为1。 NW（I-1，J-1） N（I-1，J） NE（I-1，J+1） W（I，J-1）+（I，J）E（I，J+1）SW（I+1，J-1） S（I+1，J） SE（I+1，J+1）为了简化算法，根据上图所示的位置（i,j）与其相邻的八个位置的坐标关系，建立一个下图所示的表move,表中给出相对于位置（I,j）的八个方向上的i与j的增量值。Move -10-110111101-10-1-1-1 若老鼠在（i,j）位置，要进入SW方向(g,h)点，则由该增量值表来修改坐标。 g=i+move50; h=j+move51;例如：若（i,j）为（3，4），则SW的相邻点的坐标为（3+1

12、，4-1）。在每个位置上都从N方向试起，若不通，则顺时针方向试NE方向，其余类推。当选定一个可通的方向后，要把目前所在的位置以及所选的方向记录下来，以便往下走时可依次一点一点退回来，每退一步后接着试在该点未试过的方向。为了避免走回到已经进入过的点，mazeij=2.为了记录当前位置以及该位置上所选择的方向数需设一个堆栈。#define m 6#defing n 9void path()int mazem+2n+2 ; int move82; int s543; int top=0;int i,j,k,pf=0;for(i=0;im+2;+i)for(j=0;jn+2;+j)scanf(“%d”

13、,&mazeij);maze11=2; stop0=1; stop1=1;stop2=0;+top;while (top!=0&f=0)-top;i= stop0; j= stop1;k= stop2; while(k8) g=i+movek0; h=j+movek1; if (g=m&h=n&mazegh=0) for(p=0;pm=n; for(j=0;jdataj.firstadj=NULL; g-dataj.vex=j; for(j=0;jadjvex=k; p-next=NULL;if(g-datai.firstadj=NULL)g-datai.firstadj=p;else q=g

14、-datai.firstadj;while(q-next)q=q-next;q-next=p;/* 向图的深度优先遍历*/void dfs(adjlist g, int v )node *p; printf(%3d,v); visitedv=1; p= g.datav.firstadj; while(p)if(visitedp-adjvex=0) dfs(g , p-adjvex); p=p-next; /*图的广度优先遍历程序*/*void bfs(adjlist g, int v )*/*定义空队列*/*int Q100;int front=0,rear=0;node *p;visited

15、v=1;printf(%3d,v);Qrear+=v;while(front!=rear)v=Qfront+; p= g.datav.firstadj; while(p) if(visitedp-adjvex=0) visitedp-adjvex=1; printf(%3d, p-adjvex); Qrear+= p-adjvex; p=p-next; */void print(adjlist g)int i; node *p; for(i=0;iadjvex); p=p-next; printf(n); 实验步骤1先建立图的邻接表，并将邻接表输出，并测试你的程序，直至正确为止；3 进行深度优

16、先遍历和广度优先遍历；4 将你的程序和实录的界面存盘备用。 实验报告要求1 阐述实验目的和实验内容；2 提交模块化的实验程序源代码；3 简述程序的测试过程，提交实录的输入、输出文件；4提交思考与练习题的代码和测试结果。思考与练习写出图的邻接矩阵表示法的定义，并实现求最短路径的算法。实验七 哈希表的设计实验目的1掌握的哈希表定义和存储2掌握查找常用方法及过程3实现哈希表的综合操作 预习要求1认真阅读和掌握本实验的算法。2上机将本算法实现。3保存和打印出程序的运行结果，并结合程序进行分析。类型定义#define MAXSIZE 12 /哈希表的最大容量，与所采用的哈希函数有关enum BOOLFa

17、lse,True;enum HAVEORNOTNULLKEY,HAVEKEY,DELKEY; /哈希表元素的三种状态，没有记录、有记录、有过记录但已被删除typedef struct /定义哈希表的结构int elemMAXSIZE; /数据元素体HAVEORNOT elemflagMAXSIZE; /元素状态标志，没有记录、有记录、有过记录但已被删除int count; /哈希表中当前元素的个数 HashTable;typedef structint keynum; /记录的数据域，只有关键字一项Record;实验提示void InitialHash(HashTable &H)/哈希表初始化

18、void PrintHash(HashTable H)/显示哈希表所有元素及其所在位置BOOL SearchHash(HashTable H,int k,int &p)/在开放定址哈希表H中查找关键字为k的数据元素，若查找成功，以p指示/待查数据元素在表中的位置，并返回True；否则，以p指示插入位置，并/返回FalseBOOL InsertHash(HashTable &H,Record e)/查找不成功时插入元素e到开放定址哈希表H中，并返回True，否则返回FalseBOOL DeleteHash(HashTable &H,Record e)/在查找成功时删除待删元素e，并返回True，

19、否则返回Falseint Hash(int kn)/哈希函数：H(key)=key MOD 11return (kn%11); 实验步骤1.先将哈希表初始化并显示哈希表所有元素及其所在位置，并测试你的程序，直至正确为止；2. 在开放定址哈希表中查找关键字为的数据元素；3. 查找不成功时插入元素到开放定址哈希表中。 实验报告要求1.阐述实验目的和实验内容；2.提交模块化的实验程序源代码；3.简述程序的测试过程，提交实录的输入、输出文件；4提交思考与练习题的代码和测试结果。思考与练习写出约瑟夫问题的求解算法，即n个人坐成一圈，报m出圈，输出最后一个报m的人。实验八 Kruskal算法的设计实验目的

20、. 根据算法设计需要, 掌握连通网的灵活表示方法;. 掌握最小生成树的Kruskal算法;. 基本掌握贪心算法的一般设计方法;. 进一步掌握集合的表示与操作算法的应用.预习要求. 认真阅读算法设计教材和数据结构教材内容, 熟习连通网的不同表示方法和最小生成树算法;. 设计Kruskal算法实验程序.参考数据类型或变量typedef NodeNumber int; /* 节点编号 */typedef CostType int; /* 成本值类型 */typedef ElemType NodeNumber /* 实型或任意其它元素类型 */typedef struct int ElemType;

21、int tag; NODE;typedef struct CostType cost; NodeNumber node1, node2; EDGE;NODE set=1,-1,n,-1; /* 节点集, n为连通网的节点数 */ EDGE es =values of e1, values of em; /* 边集, m为连通网的边数 */EDGE stn-1; /* 最小生成树的边集 */参考子程序接口与功能描述int Find(NODE *set, ElemType elem)功能: 在数组set中顺序查找元素elem, 如果不成功, 返回-1; 否则, 使用带压缩规则的查找算法,返回所在子

22、集的根节点索引. int Union(NODE *set, ElemType elem1, ElemType elem2)功能: 应用Find算法首先找到elem1和elem2所在的子集, 然后应用带加权规则的并运算算法合并两个子集. 不成功时, 返回-1; 否则, 返回并集的根节点索引.void Sort(EDGE *es, int n)功能: 用任意分类算法将连通图的边集按成本值的非降次序分类.void Kruskal(EDGE *es, int m, NODE *set, int n, EDGE *st)功能: 对有n个节点, m条边的连通网, 应用Kruskal算法生成最小生成树, 最

23、小生成树的边存储在数组st中.void Output(EDGE *st, int n)功能: 输出最小生成树的各条边.实验步骤1. 设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止;2. 待各功能子程序调试完毕, 去掉测试程序, 将你的程序整理成功能模块存盘备用.实验报告要求1. 阐述实验目的和实验内容;2. 阐述Kruskal算法的原理方法;3. 提交实验程序的功能模块;4. 提供测试数据和相应的最小生成树.思考与练习1. 设计由连通网初始边集数组生成最小堆的算法;2. 设计输出堆顶元素, 并将剩余元素调整成最小堆的算法;3. 针对连通网初始边集最小堆表示, 设计Kru

24、skal算法;4. 采用成本邻接矩阵表示连通网时, 在剩余边中如何实现最小成本边的查找?采用成本邻接矩阵表示连通网时, 用C语言实现Prim算法.实验九 归并排序的分治策略设计实验目的. 熟悉二分检索问题的线性结构表示和二分检索树表示;. 熟悉不同存储表示下求解二分检索问题的递归算法设计;. 通过实例转换, 掌握将递归算法转换成迭代算法的方法;. 掌握应用递归或迭代程序设计实现分治法求解问题的抽象控制策略.预习要求. 认真阅读算法设计教材和数据结构教材内容, 熟悉不同存储表示下求解二分检索问题的原理或方法;. 针对线性结构表示和二分检索树表示设计递归算法;. 参考教材和课堂教学内容, 根据将递

25、归算法转换成迭代算法的一般步骤将二分检索递归算法转换成相应的迭代算法.算法或程序设计参考线性结构int data10= /* 10个互异的、无序的原始整数 */ ;typedef struct int s100; int top; STACK;int Partition(int *data, int low, int high)功能: 将datalow, high进行快速分类划分, 返回枢轴记录关键字的位置索引.int QSort1(int *data, int low, int high)功能: 将datalow, high进行快速分类的递归算法.int QSort2(int *data,

26、int low, int high)功能: 将datalow, high进行快速分类的迭代算法.int BSearch1(int *data, int key)功能: 在data数组中检索key的二分检索递归算法, 成功时返回位置索引, 否则返回-1.int BSearch2(int *data, int key)功能: 在data数组中检索key的二分检索迭代算法, 成功时返回位置索引, 否则返回-1.树结构typedef struct NODE int key; struct NODE *lch, *rch; TNODE, *BT;typedef struct Parameters BT

27、*t; int key; BT f; BT *p PARA;typedef struct PARA s100; int top; STACK;int InsertBT(BT *t, int key)功能: 在二分检索树t中插入关键字为key的元素, 成功时返回1, 否则返回0.int TSearch1(BT *t, int key, BT f, BT *p)功能: 用递归算法在二分检索树t中查找关键字为key的元素, 成功时返回1, p指向该元素节点, 否则p指向查找路径上最后一个节点并返回0, f指向t的双亲, 其初始调用值为NULL.int TSearch2(BT *t, int key,

28、 BT f, BT *p)功能: 用迭代算法在二分检索树t中查找关键字为key的元素, 成功时返回1, p指向该元素节点, 否则p指向查找路径上最后一个节点并返回0, f指向t的双亲, 其初始调用值为NULL.实验步骤1. 调试线性结构表示下的快速分类与二分检索递归程序, 直至正确为止;2. 调试线性结构表示下的快速分类与二分检索迭代程序, 直至正确为止;3. 待各功能子程序调试完毕, 去掉测试程序, 将程序整理成功能模块存盘备用.实验报告要求1. 阐述实验目的和实验内容;2. 提交实验程序的功能模块;3. 阐述将递归算法改写成迭代算法的一般方法;4. 用类C语言阐述分治法递归与迭代实现抽象控

29、制策略. 思考与练习1. 怎样优化由递归程序改写的迭代程序?2. 设计二分检索树的构造与检索递归程序, 并将其改写成相应的迭代算法.实验十 哈夫曼编码的贪心算法设计实验目的. 根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法;. 编程实现哈夫曼编译码器;. 掌握贪心算法的一般设计方法。预习要求1. 认真阅读数据结构教材和算法设计教材内容, 熟悉哈夫曼编码的原理;2. 设计和编制哈夫曼编译码器。参考数据类型或变量typedef ElemType char；typedef struct node int w; int flag; ElemType c; struct node *plink,*

30、llink,*rlink; char codem;Node;Node *numn, *root;参考子程序接口与功能描述void SetTree( NODE *root )功能: 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树void EnCode( Node *p )功能: 利用已建好的哈夫曼树，对输入的正文进行编码 void DeCode( void )功能: 利用已建好的哈夫曼树，将输入的代码进行译码实验步骤1. 设计SetTree的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;2. 设计EnCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止

31、;3. 设计DeCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;4. 将你的程序整理成功能模块存盘备用。实验报告要求1. 阐述实验目的和实验内容;2. 提交实验程序的功能模块;3. 记录最终测试数据和测试结果。思考题1. 试证明哈夫曼问题具有贪心选择性质；2. 试证明哈夫曼问题具有最优子结构性质。实验十一 递归与迭代程序设计实验目的. 熟悉二分检索问题的线性结构表示和二分检索树表示;. 熟悉不同存储表示下求解二分检索问题的递归算法设计;. 通过实例转换, 掌握将递归算法转换成迭代算法的方法;. 掌握应用递归或迭代程序设计实现分治法求解问题的抽象控制策略.预习要求. 认真阅

32、读算法设计教材和数据结构教材内容, 熟悉不同存储表示下求解二分检索问题的原理或方法;. 针对线性结构表示和二分检索树表示设计递归算法;. 参考教材和课堂教学内容, 根据将递归算法转换成迭代算法的一般步骤将二分检索递归算法转换成相应的迭代算法.算法或程序设计参考线性结构int data10= /* 10个互异的、无序的原始整数 */ ;typedef struct int s100; int top; STACK;int Partition(int *data, int low, int high)功能: 将datalow, high进行快速分类划分, 返回枢轴记录关键字的位置索引.int QS

33、ort1(int *data, int low, int high)功能: 将datalow, high进行快速分类的递归算法.int QSort2(int *data, int low, int high)功能: 将datalow, high进行快速分类的迭代算法.int BSearch1(int *data, int key)功能: 在data数组中检索key的二分检索递归算法, 成功时返回位置索引, 否则返回-1.int BSearch2(int *data, int key)功能: 在data数组中检索key的二分检索迭代算法, 成功时返回位置索引, 否则返回-1.树结构typedef

34、 struct NODE int key; struct NODE *lch, *rch; TNODE, *BT;typedef struct Parameters BT *t; int key; BT f; BT *p PARA;typedef struct PARA s100; int top; STACK;int InsertBT(BT *t, int key)功能: 在二分检索树t中插入关键字为key的元素, 成功时返回1, 否则返回0.int TSearch1(BT *t, int key, BT f, BT *p)功能: 用递归算法在二分检索树t中查找关键字为key的元素, 成功时

35、返回1, p指向该元素节点, 否则p指向查找路径上最后一个节点并返回0, f指向t的双亲, 其初始调用值为NULL.int TSearch2(BT *t, int key, BT f, BT *p)功能: 用迭代算法在二分检索树t中查找关键字为key的元素, 成功时返回1, p指向该元素节点, 否则p指向查找路径上最后一个节点并返回0, f指向t的双亲, 其初始调用值为NULL.实验步骤1. 调试线性结构表示下的快速分类与二分检索递归程序, 直至正确为止;2. 调试线性结构表示下的快速分类与二分检索迭代程序, 直至正确为止;3. 待各功能子程序调试完毕, 去掉测试程序, 将程序整理成功能模块存

36、盘备用.实验报告要求1. 阐述实验目的和实验内容;2. 提交实验程序的功能模块;3. 阐述将递归算法改写成迭代算法的一般方法;4. 用类C语言阐述分治法递归与迭代实现抽象控制策略. 思考与练习1. 怎样优化由递归程序改写的迭代程序?2. 设计二分检索树的构造与检索递归程序, 并将其改写成相应的迭代算法. 实验十二 多段图问题的动态规划算法设计实验目的1. 掌握有向网的成本邻接矩阵表示法;2. 能用程序设计语言实现多段图问题的动态规划递推算法;3. 基本掌握动态规划法的原理方法.预习要求1. 认真阅读数据结构教材和算法设计教材, 熟习有向网的成本邻接矩阵表示法和动态规划求解多段图问题的递推原理;2. 设计用动态规划算法求解多段图问题的数据结构和递