算法方案与分析实验指导书

1、算法设计与分析实验指导书信息科学技术学院目录实验一常见简单算法的设计、实现与分析实验目的1掌握单链表的建立插入及删除的算法；2进一步熟悉指针的用法；预习要求1. 认真阅读教材或参考书，掌握线性表算法的基本思想;2. 写出求解本实验的程序；3. 设计好相应的测试用例。类型定义typedef struct Lnodeint data 。struct Lnode *next 。Lno de,*li nklist。实验提示void create(l ink *h,i nt n/创建单链表link p,q 。int i 。p=(li nkmalloc(sizeof( no de。p-n ext=n ul

2、l。*h=p。q=p。for(i=1 。 ip=(l in kmalloc(sizeof( no de。scan f(%d,&p-data 。p-next=null。 q-next=p 。 q=p。void prin t(l ink h/输出单链表li nk p 。p=h-next 。while(ppri ntf(%d ,p-data 。p=p-next。void in sertlist(l in klist *L,i nt i,i nt e/在单链表的第i个元素之前插入元素值为e的结点void dellist(linklist *L,int i,int *e/删除单链表的第i个结点，被删结点

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

4、struct Lnodeint coef,exp 。struct Lnode *next 。Lno de,*li nklist 。实验提示void create(l ink *h,i nt n/创建一元多项式link p,q 。int i 。p=(li nkmalloc(sizeof( no de。p-n ext=n ull。*h=p。q=p。for(i=1 。 ip=(l in kmalloc(sizeof( no de。scan f(%d%d,&p-coef,&p-exp。p-next=null。 q-next=p 。 q=p。void prin t(l ink h/输出单链表li nk

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

6、，报 m出圈，输出最后一个报m的人。实验三集合的表示与操作算法设计实验目的1 . 了解集合的不同表示方法，掌握集合的树结构表示方法。2. 掌握树结构表示下集合的并运算与查找算法。3. 编程实现集合的表示与操作算法 预习要求2. 设计和编制实验程序参考数据类型或变量typedef ElemType int /*实型或任意其它元素类型*/typedef struct ElemType tag。/*根节点为负的整数 表示该集合的基数的负值，否则为父节点索引指针*/NODE。NODE *set。 /*用动态存储分配实现集合的树表示与存储*/参考子程序接口与功能描述void In it

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

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

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

10、条件，在迷宫外面套上一圈，其元素值均为1。NWI-1，J-1)NI-1，J)NE I-1，J+1)W+EI，J-1)I，J)I，J+1)SWSSEI+1，J-1)I+1，J)I+1，J+1)为了简化算法，根据上图所示的位置i,j )与其相邻的八个位置的坐标关系，建立一个下图所示的表move,表中给出相对于位置l,j )的八个方向上的i与j的增量值。Move-10-11011r 1 101-10-1-1-1若老鼠在点，则由该增量值表来修改坐标。g=i+move50。h=j+move51。例如：若i,j )为3，4)，则SW的相邻点的坐标为int mazem+2 n+2。int move82。in

11、t top=0。int i,j,k,pf=O 。for(i=0。 ifor(j=0。 jscanf( “ d ，&mazeijmaze11=2。stop0=1。stop1=1。stop2=0。+top。while (top!=0&f=0-top。i= stop0。j= stop1。k= stop2。while(kg=i+movek0。h=j+movek1。if (g=m&h=n&mazegh=0for(p=0。pprin tf(spO,sp1 。printf(i,j 。printf(m,n 。f=1。/if if(mazegh=Omazegh=2 。 stop0=i。stop

12、1=j。stop2=k 。+top。i=g。j=h。k=0。/if k=k+1 。/while/whileif(f=0printf(“ no pialh/path实验步骤1. 先设计好迷宫，并测试你的程序，直至正确为止；2. 将你的程序和实录的界面存盘备用。实验报告要求1. 阐述实验目的和实验内容；2. 提交模块化的实验程序源代码；3. 简述程序的测试过程，提交实录的输入、输出文件;4. 提交思考与练习题的代码和测试结果。思考与练习写出用队列求解迷宫问题的算法。实验五树的建立及遍历实验目的1. 进一步掌握指针变量的含义。2. 掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。3. 掌握用

13、指针类型描述、访问和处理二叉树的运算。预习要求1. 认真阅读教材或参考书，掌握树的三种遍历方法算法的基本思想；2. 写出求解本实验的程序；3. 设计好相应的测试用例。类型定义typedef struct Bit nodeint coef,exp 。struct Bit node *n ext。Bit node,*Bitree。实验提示按先序次序输入二叉树中结点的值/创建二叉树void preorder(Bitree t/二叉树的先序遍历void ino rder(Bitree t/二叉树的中序遍历void ino rder(Bitree t/二叉树的后序遍历实验步骤1. 先用先序次序输入二叉树

14、中结点的值建立二叉树，并测试你的程序，直至正确为止;2. 用递归方法进行三种不同的遍历；3. 用非递归方法进行三种不同的遍历；。实验报告要求1阐述实验目的和实验内容；2 提交模块化的实验程序源代码；3简述程序的测试过程，提交实录的输入、输出文件；4提交思考与练习题的代码和测试结果。思考与练习1 写出一个算法统计树的叶子结点个数。2 不用栈不用递归写一算法求树的后序遍历的第一个结点。实验六图的遍历的演示实验目的1. 熟练掌握图的邻接表存储方法和邻接表的建立算法；2 掌握图的图的深度和广度遍历算法思想；预习要求1. 认真阅读教材或参考书，掌握图的深度和广度遍历算法思想;2. 写出求解本实验的程序；

15、3. 设计好相应的测试用例。类型定义/*邻接点及顶点的定义*/typedef struct nodeint adjvex 。struct node *next。 node。/*顶点的定义*/typedef structint vex 。node *firstadj 。vertex 。/*邻接表的定义*/typedef struct vertex m 。/*m表示图中顶点的个数 */ adjlist 。实验提示void creategraph(adjlist *gint n,e 。 /*n表示图中的顶点个数,e表示边的条数*/int j,i,k 。node *p,*q。/

16、*由键盘输入图的顶点个数及边的条数*/prin tf(i nput n=。scan f(%d, &n。prin tf(i nput e=。scan f(%d, &e。/*初始化邻接表*/g-m=n 。for(j=0 。jg-dataj.firstadj=NULL。g-dataj.vex=j 。for(j=0 。 j/*由键盘输入一对边*/prin tf( in put i,k:。scanf (%d%d,&i,&k。/*申请一个邻结点*/p=(node *malloc(sizeof( no de。p-adjvex=k 。p-next=NULL。 if(g-datai.firstadj=NULL

17、g-datai.firstadj=p 。 elseq=g-datai.firstadj。while(q- next q=q-next。q-next=p。/*向图的深度优先遍历*/void dfs(adjlist g, int v node *p 。prin tf(%3d,v。visitedv=1 。p= g.datav.firstadj。while(pif(visitedp-adjvex=0 dfs(g , p-adjvex p=p-next 。/*图的广度优先遍历程序*/*void bfs(adjlist g, i nt v */*定义空队列*/*int Q100。int fron t=0,

18、rear=0。node *p 。visitedv=1 。prin tf(%3d,v。Qrear+=v 。while(fr on t!=rearv=Qfro nt+。p= g.datav.firstadj while(p if(visitedp-adjvex=O visitedp-adjvex=1 printf(%3d, p-adjvex Qrear+= p-adjvex p=p-n ext。 */void prin t(adjlist gint i 。node *p 。for(i=0 。 ip=g.datai.firstadjwhile(ppri ntf(%d-%d,i,p-adjvex。p=

19、p-n ext。prin tf(n。实验步骤1 先建立图的邻接表，并将邻接表输出，并测试你的程序，直至正确为止;3. 进行深度优先遍历和广度优先遍历；4. 将你的程序和实录的界面存盘备用。实验报告要求1. 阐述实验目的和实验内容；2. 提交模块化的实验程序源代码；3. 简述程序的测试过程，提交实录的输入、输出文件；4. 提交思考与练习题的代码和测试结果。思考与练习写出图的邻接矩阵表示法的定义，并实现求最短路径的算法。实验七哈希表的设计实验目的1. 掌握的哈希表定义和存储2. 掌握查找常用方法及过程3. 实现哈希表的综合操作预习要求1. 认真阅读和掌握本实验的算法。2. 上机将本算法实现。3.

20、保存和打印出程序的运行结果，并结合程序进行分析。类型定义#defi ne MAXSIZE 12 /哈希表的最大容量，与所采用的哈希函数有关enum BOOLFalse,True。enum HAVEORNOTNULLKEY,HAVEKEY,DELKEY/哈希表元素的三种状态，没有记录、有记录、有过记录但已被删除typedef struct /定义哈希表的结构int elemMAXSIZE 。/ 数据元素体HAVEORNOT elemflagMAXSIZE。/元素状态标志，没有记录、有记录、有过记录但已被删除 int count 。 /哈希表中当前元素的个数HashTable 。typedef s

21、tructint key num 。/记录的数据域，只有关键字一项Record 。实验提示void InitialHash(HashTable &H/哈希表初始化void Prin tHash(HashTable H/显示哈希表所有元素及其所在位置BOOL SearchHash(HashTable H,i nt k,i nt &p/在开放定址哈希表 H中查找关键字为k的数据元素，若查找成功，以p指示/待查数据元素在表中的位置，并返回True ;否则，以p指示插入位置，并/ 返回 FalseBOOL In sertHash(HashTable & H,Record e/查找不成功时插入元素e到开放定址哈希表 H中，并返回True，否则返回FalseBOOL DeleteHash(HashTable & H,Record e/在查找成功时删除待删元素e,并返回True，否则返回Falseint Hash(i nt kn/ 哈希函数：H(key=key MOD 11return (k n%11。实验步骤1. 先将哈希表初始化并显示哈希表所有元素及其所在位置，并测试你的程序，直至正确为止；2. 在开放定址哈希表中查找关键字为