算法设计与分析实验.docx

《算法设计与分析实验.docx》由会员分享，可在线阅读，更多相关《算法设计与分析实验.docx（40页珍藏版）》请在第一文库网上搜索。

1、算法设计与分析选做实验实验一单链表的建立插入及删除实验目的1 .掌握单链表的建立插入及删除的算法；2 .进一步熟悉指针的用法；预习要求1 .认真阅读教材或参考书，掌握线性表算法的基本思想;2 .写出求解本实脸的程序；3 .设计好相应的测试用例。类型定义typedefstruct1nodeintdata;struct1nOde*next;1node,*1ink1ist;实验提示voidcreate(1ink*h,intn)创建单链表1inkp,q;inti;p=(1ink)ma11oc(sizeof(node);p-next=nu11;*h=pjq=p;for(i=1;idata);p-next

2、=nu11;q-next=p;q=p;)voidprint(1inkh)输出单链表1inkp;p=h-next;whi1e(p)printf(*%d,p-data);p=p-next;)voidinsert1ist(1ink1ist*1,inti,inte)在单链表的第i个元素之前插入元素值为e的结点voidde11ist(1ink1ist*1,inti,int*e)删除单链表的第i个结点，被删结点通过e返回实验步骤1. 先用插表头或插表尾的方法建立单链表并输出，并测试你的程序，直至正确为止;2. 再进行插入和删除程序的设计；3. 将你的程序和实录的界面存盘备用。实验报告要求1 .阐述实验目的

3、和实脸内容；2 .提交模块化的实验程序源代码；3 .简述程序的测试过程，提交实录的输入、输出文件:4 .提交思考与练习题的代码和测试结果。思考与练习怎样用链表实现循环队列。实验二多项式加法实验目的1 .熟练掌握在单链表中进行结点的插入和删除操作；2 .进一步熟悉指针的用法；预习要求1 .认真阅读教材或参考书，掌握线性表算法的基本思想；2 .写出求解本实脸的程序；3 .设计好相应的测试用例。类型定义typedefstruct1nodeintcoef,exp;struct1nOde*next;1node,*1ink1ist;实验提示voidcreate(1ink*h,intn)创建一元多项式1in

4、kp,q;inti;p=(1ink)ma11oc(sizeof(node);p-next=nu11;*h=pjq=p;for(i=1;icoef,p-exp);p-next=nu11;q-next=p;q=p;)voidprint(1inkh)输出单链表1inkp;p=h-next;whi1e(p)printf(/%d1%d”,p-coef,p-exp);p=p-next;)voidadd1ist(1ink1ist*,1ink1istB)/将A和B相力口并通过A返回实验步骤1 .先用插表尾的方法建立一元多项式，并将一元多项式输出，并测试你的程序，直至正确为止；2 .进行一元多项式相加程序的设计

5、：3 .将你的程序和实录的界面存盘备用。实验报告要求1. 阐述实验目的和实脸内容；2. 提交模块化的实脸程序源代码：3. 简述程序的测试过程，提交实录的输入、输出文件；4. 提交思考与练习题的代码和测试结果。思考与练习写出约瑟夫问题的求解算法，即n个人坐成一圈，报m出国，输出最后一个报m的人。实验三集合的表示与操作算法设计实验目的11 .了解集合的不同表示方法,掌握集合的树结构表示方法；2 .掌握树结构表示下集合的并运算与查找算法；3 .编程实现集合的表示与操作算法.预习要求1. 认真阅读教材内容，熟悉树结构表示的原理和操作算法；2. 设计和编制实脸程序.参考数据类型或变量ItypedefE1

6、emTypeint/*实型或任意其它元素类型*/Iypedefstruct)E1emTypee1em;inttag;/*根节点为负的整数,表示该集合的基数的负值,否则为父节点索引指针*/NODE;NODE*set;/*用动态存储分配实现集合的树表示与存储*/参考子程序接口与功能描述voidInitSet(NODE*set)功能：根据集合的基数动态分配存储，输入各元素，初始化子集森林.intFind(NODE*set,E1emTypee1em)功能：在数组Se1中顺序查找元素e1em,如果不成功，返回-1;否则,使用带压缩规则的查找算法,返回所在子集的根节点索引.intUnion(NODE*se

7、t,E1emTyPee1emi,E1emTypee1em2)功能：应用Find算法首先找到e1emi和e1em2所在的子集，然后应用带加权规则的并运算算法合并两个子集.不成功时，返回-1;否则，返回并集的根节点索引.实验步骤1 .设计Find的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止；2 .设计Union的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止；3 .待各功能子程序调试完毕,去掉测试程序,将你的程序整理成功能模块存盘备用.实验报告要求1 .阐述实脸目的和实验内容；2 .提交实验程序的功能模块；3 .记录最终测试数据和测试结果。思考题试用C语言实现集合的位向

8、量表示，并设计相应的并、交与查找运算算法.实验四迷宫问题求解实验目的1 .熟悉栈用法；2 .掌握回朔法及试探法的程序设计；预习要求1 .认真阅读教材或参考书，掌握栈用法的用法：2 .写出求解本实验的程序；3 .设计好相应的测试用例。实验提示设迷宫中数组的元素为1表示该点道路主的阻塞，为O表示可通。设maze11为入口，mazemn为出口。在maze11和mazemn的元素值必为O0在任意时刻，老鼠在迷宫中的位置可以用所在点的行下标与列下标（i,j）来表示，这样，老鼠在迷宫中的某点mazeij时，其可能的运动方向有八个。下图+表示某时刻老鼠所在的位置（i,j）,相邻的八个位置分别标以N、NE、E

9、、SEsS、SW.W、NW（分别代表十点的北、东北、东、东南、南、西南、西、西北方向）；同时，相对于（i,j）,这八个相邻位置的坐标的值都可以计算出来。但是，并非迷宫中的每一个点都有八个方向可走，四个角上就只有三个方向可供选择，边上只有五个方向可供选择。为了不在算法中每次都去检查这些边界条件，在迷宫外面套上一周，其元素值均为1oNW(1-1,J-DN(1-1,J)NE(1-1,J+1)W(I,J-D+(I,J)E(I,J+1)SW(1+1,J-DS(1+1,J)SE(1+1,J+1)为了简化算法，根据上图所示的位置（i,j）与其相邻的八个位置的坐标关系，建立一个下图所示的表move,表中给出相

10、对于位置（1,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,4-1）o在每个位置上都从N方向试起，若不通，则顺时针方向试NE方向，其余类推。当选定一个可通的方向后，要把目前所在的位置以及所选的方向记录下来，以便往下走时可依次一点一点退回来，每退一步后接着试在该点未试过的方向。为了避免走回到已经进入过的点，mazeij=2.为了记录当前位置以及该位置上所选择的方向数需设一个

11、堆栈。#definem6#defingn9voidpath()intmazem+2n+2;intmove8H2;ints543;inttop=0;inti,j,k,pf=O;for(i=0;im+2;+i)for(j=0;jn+2;+j)scanf(M%d,&mazeij);maze1J1=2;stop01=1;stop1=1;stop2=0;+top;whi1e(top!=0&f=0)-top;i=stop0;j=sto1;k=stop2;whi1e(k8)g=i+movek0;h=j+movek1;if(g=m&h=n&mazegh=0)fbr(p=0;ptop;+p)printf(spO

12、,sp1);printf(ij);printf(m,n);f=1；ifif(mazegh=O)mazegh=2;stop0=i;stop1=j;stop2=k;+top;i=g；j=h;k=0;ifk=k+1;whi1e(/whi1eif(f=O)Primfrnopathn,);path实验步骤1 .先设计好迷宫，并测试你的程序，直至正确为止;2 .将你的程序和实录的界面存盘备用。实验报告要求1 .阐述实验目的和实脸内容；2 .提交模块化的实验程序源代码；3 .简述程序的测试过程，提交实录的揄入、榆出文件;4 .提交思考与练习题的代码和测试结果。思考与练习写出用队列求解迷宫问题的算法。实验五树

13、的建立及遍历实验目的1 .进一步掌握指针变量的含义。2 .掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。3 .掌握用指针类型描述、访问和处理二叉树的运算。预习要求1 .认真阅读教材或参考书，掌握树的三种遍历方法算法的基本思想：2 .写出求解本实脸的程序；3 .设计好相应的测试用例。类型定义typedefstructBitnodeintcoef,exp;structBitnode*next;Bitnode,*Bitree;实验提示按先序次序输入二叉树中结点的值(一个字符)，0表示空树，生成二叉树的二叉链表存储结构，t为指向根结点的指针。然后按先序、中序及后序等方法遍历二叉树。voidcreate(Bitree*t)创建二叉树voidpreorder(Bitreet)/二叉树的先序遍历voidinorder(Bitreet)二叉树的中序遍历voidinorder(Bitreet)二叉树的后序遍历实验步骤1 .先用先序次序输入二叉树中结点的值建立二叉树，并测试你的程序，直至正确为止；2 .用递归方法进行三种不同