《2022年算法方案与分析实验指导书》由会员分享，可在线阅读，更多相关《2022年算法方案与分析实验指导书（12页珍藏版）》请在金锄头文库上搜索。
1、个人资料整理仅限学习使用算法设计与分析实验指导书信息科学技术学院目录精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 12 页个人资料整理仅限学习使用实验一常见简单算法的设计、实现与分析 实验目的 1掌握单链表的建立插入及删除的算法；2进一步熟悉指针的用法； 预习要求 1. 认真阅读教材或参考书, 掌握线性表算法的基本思想；2. 写出求解本实验的程序；3. 设计好相应的测试用例。 类型定义 typedef struct Lnodeint data。struct Lnode *next。Lnode,*linklist。 实验提示 精选学习资
2、料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 12 页个人资料整理仅限学习使用void create(link *h,int n /创建单链表link p,q。int i。p=(linkmalloc(sizeof(node。p-next=null。*h=p。q=p。for(i=1。i p=(linkmalloc(sizeof(node。scanf(%d,&p-data。p-next=null。q-next=p 。q=p。 void print(link h /输出单链表link p。p=h-next 。while(p printf(%d ,p-
3、data。p=p-next 。 void insertlist(linklist *L,int i,int e /在单链表的第i 个元素之前插入元素值为e 的结点 void dellist(linklist *L,int i,int *e /删除单链表的第i 个结点，被删结点通过 e 返回 实验步骤 1.先用插表头或插表尾的方法建立单链表并输出，并测试你的程序，直至正确为止；2.再进行插入和删除程序的设计；3.将你的程序和实录的界面存盘备用。 实验报告要求 1.阐述实验目的和实验内容；2.提交模块化的实验程序源代码；3.简述程序的测试过程，提交实录的输入、输出文件；4.提交思考与练习题的代码和
4、测试结果。 思考与练习 怎样用链表实现循环队列。实验二多项式加法 实验目的 1熟练掌握在单链表中进行结点的插入和删除操作；2进一步熟悉指针的用法； 预习要求 1. 认真阅读教材或参考书, 掌握线性表算法的基本思想；2. 写出求解本实验的程序；3. 设计好相应的测试用例。 类型定义 typedef struct Lnode精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 12 页个人资料整理仅限学习使用int coef,exp。struct Lnode *next。Lnode,*linklist。 实验提示 void create(link
5、 *h,int n /创建一元多项式link p,q。int i。p=(linkmalloc(sizeof(node。p-next=null。*h=p。q=p。for(i=1。i p=(linkmalloc(sizeof(node。scanf(%d%d,&p-coef,&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=p-next 。 void addlist(linklist *A, linklist B /将 A和 B
6、相加并通过A返回 实验步骤 1 先用插表尾的方法建立一元多项式，并将一元多项式输出，并测试你的程序，直至正确为止；2 进行一元多项式相加程序的设计；3 将你的程序和实录的界面存盘备用。 实验报告要求 1阐述实验目的和实验内容；2提交模块化的实验程序源代码；3简述程序的测试过程，提交实录的输入、输出文件；4提交思考与练习题的代码和测试结果。 思考与练习 写出约瑟夫问题的求解算法，即n 个人坐成一圈，报m出圈，输出最后一个报m的人。实验三集合的表示与操作算法设计实验目的 . 了解集合的不同表示方法,掌握集合的树结构表示方法。. 掌握树结构表示下集合的并运算与查找算法。. 编程实现集合的表示与操作算
7、法. 预习要求 1.认真阅读教材内容, 熟悉树结构表示的原理和操作算法。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 12 页个人资料整理仅限学习使用2.设计和编制实验程序. 参考数据类型或变量 typedef ElemType int /* 实型或任意其它元素类型 */ typedef struct ElemType elem。int tag。 /* 根节点为负的整数,表示该集合的基数的负值,否则为父节点索引指针 */ NODE 。NODE *set 。 /* 用动态存储分配实现集合的树表示与存储 */ 参考子程序接口与功能描述 v
8、oid InitSet(NODE *set 功能 : 根据集合的基数动态分配存储, 输入各元素 , 初始化子集森林. int Find(NODE *set, ElemType elem 功能 : 在数组 set中顺序查找元素elem,如果不成功 , 返回 -1。 否则 ,使用带压缩规则的查找算法,返回所在子集的根节点索引 .int Union(NODE *set, ElemType elem1, ElemType elem2功能 : 应用 Find 算法首先找到elem1 和 elem2 所在的子集 , 然后应用带加权规则的并运算算法合并两个子集 . 不成功时 , 返回 -1。 否则 , 返回
9、并集的根节点索引.实验步骤 . 设计 Find 的测试方案和程序,输入测试数据 ,修改并调试程序,直至正确为止。. 设计 Union 的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止。. 待各功能子程序调试完毕,去掉测试程序,将你的程序整理成功能模块存盘备用. 实验报告要求 . 阐述实验目的和实验内容。. 提交实验程序的功能模块。. 记录最终测试数据和测试结果。思考题 试用 C 语言实现集合的位向量表示, 并设计相应的并、交与查找运算算法. 实验四迷宫问题求解 实验目的 1熟悉栈用法；2掌握回朔法及试探法的程序设计； 预习要求 1. 认真阅读教材或参考书, 掌握栈用法的用法；2.
10、写出求解本实验的程序；3. 设计好相应的测试用例。 实验提示 设迷宫中数组的元素为1 表示该点道路主的阻塞，为0 表示可通。设 maze11为入口， mazemn 为出口。在 maze11和 mazemn 的元素值必为0。在任意时刻，老鼠在迷宫中的位置可以用所在点的行下标与列下标i,j）来表示，这样，老鼠在迷宫中的某点mazeij时，其可能的运动方向有八个。下图+表示某时刻老鼠所在的位置i,j）, 相邻的八个位置分别标以N、NE 、 E、SE、S、 SW 、 W 、NW 分别代表 +点的北、东北、东、东南、南、西南、西、西北方向）；同时，相对于i,j），这八个相邻位置的坐标的值都可以计算出来。
11、精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 12 页个人资料整理仅限学习使用但是，并非迷宫中的每一个点都有八个方向可走，四个角上就只有三个方向可供选择，边上只有五个方向可供选择。为了不在算法中每次都去检查这些边界条件，在迷宫外面套上一圈，其元素值均为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,表
12、中给出相对于位置I,j）的八个方向上的i 与 j 的增量值。Move -1 0 -1 1 0 1 1 1 1 0 1 -1 0 -1 -1 -1 若老鼠在 点，则由该增量值表来修改坐标。 g=i+move50。 h=j+move51。例如：若 i,j）为 3，4），则 SW 的相邻点的坐标为 int mazem+2n+2 。 int move82 。 int s543 。 int top=0 。int i,j,k,pf=0 。for(i=0 。 i for(j=0 。 j scanf(“ %d ” ,&mazeij。maze11=2 。 stop0=1 。 stop1=1 。stop2=0 。
13、+top。while (top!=0&f=0 -top 。i= stop0 。 j= stop1 。k= stop2 。 while(k g=i+movek0 。 h=j+movek1 。 if (g=m&h=n&mazegh=0 for(p=0 。p printf(sp0,sp1。 printf(i,j 。 printf(m,n 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 12 页个人资料整理仅限学习使用 f=1。/if if(mazegh=0 mazegh=2 。stop0=i 。 stop1=j 。stop2=k 。+top
14、。i=g。j=h。k=0。/if k=k+1 。/while /while if(f=0 printf(“ no pathn” 。/path 实验步骤 1 先设计好迷宫，并测试你的程序，直至正确为止；2 将你的程序和实录的界面存盘备用。 实验报告要求 1 阐述实验目的和实验内容；2 提交模块化的实验程序源代码；3 简述程序的测试过程，提交实录的输入、输出文件；4 提交思考与练习题的代码和测试结果。 思考与练习 写出用队列求解迷宫问题的算法。实验五树的建立及遍历 实验目的 1 进一步掌握指针变量的含义。2 掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。3 掌握用指针类型描述、访问和处理
15、二叉树的运算。 预习要求 1. 认真阅读教材或参考书, 掌握树的三种遍历方法算法的基本思想；2. 写出求解本实验的程序；3. 设计好相应的测试用例。 类型定义 typedef struct Bitnodeint coef,exp。struct Bitnode *next。Bitnode,*Bitree。 实验提示 按先序次序输入二叉树中结点的值 /创建二叉树 void preorder(Bitree t 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 12 页个人资料整理仅限学习使用/二叉树的先序遍历 void inorder(Bitr
16、ee t /二叉树的中序遍历 void inorder(Bitree t /二叉树的后序遍历 实验步骤 1 先用先序次序输入二叉树中结点的值建立二叉树，并测试你的程序，直至正确为止；2 用递归方法进行三种不同的遍历；3 用非递归方法进行三种不同的遍历；。 实验报告要求 1阐述实验目的和实验内容；2提交模块化的实验程序源代码；3简述程序的测试过程，提交实录的输入、输出文件；4提交思考与练习题的代码和测试结果。 思考与练习 1写出一个算法统计树的叶子结点个数。2不用栈不用递归写一算法求树的后序遍历的第一个结点。实验六图的遍历的演示 实验目的 1熟练掌握图的邻接表存储方法和邻接表的建立算法；2掌握图
17、的图的深度和广度遍历算法思想； 预习要求 1. 认真阅读教材或参考书, 掌握图的深度和广度遍历算法思想；2. 写出求解本实验的程序；3. 设计好相应的测试用例。 类型定义 /* 邻接点及顶点的定义*/ typedef struct node int adjvex。struct node *next。node 。/* 顶点的定义 */ typedef struct int vex。 node *firstadj。vertex。/* 邻接表的定义 */ typedef struct vertex data100。 int m 。/*m 表示图中顶点的个数*/ adjlist。 实验提示 void
18、creategraph(adjlist *g int n,e。 /*n表示图中的顶点个数,e 表示边的条数*/ int j,i,k。 node *p,*q。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 12 页个人资料整理仅限学习使用/* 由键盘输入图的顶点个数及边的条数*/ printf(input n=。 scanf(%d,&n。 printf(input e=。 scanf(%d,&e。/* 初始化邻接表 */ g-m=n 。 for(j=0。 j g-dataj.firstadj=NULL。 g-dataj.vex=j。 fo
19、r(j=0。j /* 由键盘输入一对边*/ printf(input i,k:。 scanf (%d%d,&i,&k。/* 申请一个邻结点*/ p=(node *malloc(sizeof(node。p-adjvex=k 。p-next=NULL 。if(g-datai.firstadj=NULL g-datai.firstadj=p。else q=g-datai.firstadj。while(q-next q=q-next 。q-next=p 。 /* 向图的深度优先遍历*/ void dfs(adjlist g, int v node *p 。 printf(%3d,v。 visitedv
20、=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 。visitedv=1。printf(%3d,v。Qrear+=v。while(front!=rear v=Qfront+。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 12 页个人
21、资料整理仅限学习使用 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。 i p=g.datai.firstadj。 while(p printf(%d-%d,i,p-adjvex。 p=p-next。 printf(n。 实验步骤 1先建立图的邻接表，并将邻接表输出，并测试你的程序，直至正确为止；3 进行深度优
22、先遍历和广度优先遍历；4 将你的程序和实录的界面存盘备用。 实验报告要求 1 阐述实验目的和实验内容；2 提交模块化的实验程序源代码；3 简述程序的测试过程，提交实录的输入、输出文件；4提交思考与练习题的代码和测试结果。 思考与练习 写出图的邻接矩阵表示法的定义，并实现求最短路径的算法。实验七哈希表的设计 实验目的 1掌握的哈希表定义和存储2掌握查找常用方法及过程3实现哈希表的综合操作 预习要求 1认真阅读和掌握本实验的算法。2上机将本算法实现。3保存和打印出程序的运行结果，并结合程序进行分析。 类型定义 #define MAXSIZE 12 /哈希表的最大容量，与所采用的哈希函数有关精选学习
23、资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 12 页个人资料整理仅限学习使用enum BOOLFalse,True 。enum HAVEORNOTNULLKEY,HAVEKEY,DELKEY。/ 哈希表元素的三种状态，没有记录、有记录、有过记录但已被删除typedef struct /定义哈希表的结构int elemMAXSIZE。 /数据元素体HAVEORNOT elemflagMAXSIZE 。 /元素状态标志，没有记录、有记录、有过记录但已被删除int count。 /哈希表中当前元素的个数HashTable 。typedef st
24、ruct int keynum。 /记录的数据域，只有关键字一项Record 。实验提示 void InitialHash(HashTable &H / 哈希表初始化 void PrintHash(HashTable H / 显示哈希表所有元素及其所在位置 BOOL SearchHash(HashTable H,int k,int &p / 在开放定址哈希表H中查找关键字为k 的数据元素，若查找成功，以p 指示/ 待查数据元素在表中的位置，并返回True；否则，以p 指示插入位置，并/ 返回 False BOOL InsertHash(HashTable &H,Record e / 查找不成功
25、时插入元素e 到开放定址哈希表H中，并返回True ，否则返回False BOOL DeleteHash(HashTable &H,Record e / 在查找成功时删除待删元素e，并返回True ，否则返回False int Hash(int kn / 哈希函数： H(key=key MOD 11 return (kn%11。 实验步骤 1. 先将哈希表初始化并显示哈希表所有元素及其所在位置，并测试你的程序，直至正确为止；2. 在开放定址哈希表中查找关键字为的数据元素；3. 查找不成功时插入元素到开放定址哈希表中。 实验报告要求 1. 阐述实验目的和实验内容；2. 提交模块化的实验程序源代码
26、；3. 简述程序的测试过程，提交实录的输入、输出文件；4提交思考与练习题的代码和测试结果。 思考与练习 写出约瑟夫问题的求解算法，即n 个人坐成一圈，报m出圈，输出最后一个报m的人。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 12 页个人资料整理仅限学习使用实验八 Kruskal 算法的设计实验目的 . 根据算法设计需要, 掌握连通网的灵活表示方法。. 掌握最小生成树的Kruskal 算法。. 基本掌握贪心算法的一般设计方法。. 进一步掌握集合的表示与操作算法的应用. 预习要求 . 认真阅读算法设计教材和数据结构教材内容, 熟习连
27、通网的不同表示方法和最小生成树算法。. 设计 Kruskal 算法实验程序. 参考数据类型或变量 typedef NodeNumber int 。 /* 节点编号 */ typedef CostType int。 /* 成本值类型 */ typedef ElemType NodeNumber /* 实型或任意其它元素类型 */ typedef struct int ElemType 。 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 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 12 页
