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

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

2、; 。p->next=null 。*h=p。 q=p。for(i=1 。 i<=n。 +i>p=(link>malloc(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->data> 。p=p->next 。void insertlis

3、t(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 Lnodeint coef,exp 。 struct Lnode *next Lnode,*linklist实验提小void create(link *h,int n>/创建一元多项式link p,q 。int i 。p=(linkmalloc(sizeof(node>> 。p->next=null 。*h=p。 q=p。f

5、or(i=1 。 i<=n。 +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(linkli

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

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

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

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

10、emn 为出口。在maze11和mazemn的元素值必为 0。在任意时刻，老鼠在迷宫中的位置可以用所在点的行下标与列下标<i,j )来表示，这样，老鼠在迷宫中的某点mazeij 时，其可能的运动方向有八个。下图+表示某时刻老鼠所在的位置<i,j ),相邻的八个位置分别标以 N、NE E、SE、S、SW W NW分别彳t表+点的北、东北、东、东南、南、西南、西、西北方 向)；同时，相对于<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-11011r 1 1101-10-1-1-1若老鼠在<i,j )位置，要进入 SW方向(g,h>点，则由

12、该增量值表来修改坐标。 g=i+move50。h=j+move51。例如：若<i,j )为<3, 4),则SW勺相邻点白向坐标为<3+1, 4-1 )。在每个位置上都从N方向试起，若不通，则顺时针方向试NE方向，其余类推。当选定一个可通的方向后，要把目前所在的位置以及所选的方向记录下来，以便往下走时可依次一点一点退回来，每退一步后接着试在该点未试过的方向。为了避免走回到已经进入过的点，mazeij=2.为了记录当前位置以及该位置上所选择的方向数需设一个堆栈。#define m 6#defing n 9 void path(> int mazem+2n+2。int mov

13、 top=0。int i,j,k,pf=0 。for(i=0。 i<m+2。 +i>for(j=0。 j<n+2。 +j> scanf(" %d' ,&mazeij>maze11=2 。stop0=1 。stop1=1 。stop2=0 。+top。while (top!=0&&f=0> -top。i= stop0。j= stop1。k= stop2。while(k<8>g=i+movek0。h=j+movek1。if (g=m&&h=n&&

14、mazegh=0>for(p=0 。 p<top。+p>printf(sp0,sp1> 。printf(i,j> 。printf(m,n> 。f=1。/ifif(mazegh=0>mazegh=2 。stop0=i。stop1=j。stop2=k 。+top。i=g。j=h。k=0。/ifk=k+1 。/while/whileif(f=0>printf("no 磔th%/path实验步骤1 .先设计好迷宫，并测试你的程序，直至正确为止；2 .将你的程序和实录的界面存盘备用。实验报告要求3 .阐述实验目的和实验内容；4 .提交模块化的实验

15、程序源代码；5 .简述程序的测试过程，提交实录的输入、输出文件；6 .提交思考与练习题的代码和测试结果。思考与练习写出用队列求解迷宫问题的算法。实验五树的建立及遍历实验目的1 .进一步掌握指针变量的含义。2 .掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。3 .掌握用指针类型描述、访问和处理二叉树的运算。预习要求1 .认真阅读教材或参考书，掌握树的三种遍历方法算法的基本思想；2 .写出求解本实验的程序；3 .设计好相应的测试用例。类型定义typedef struct Bitnodeint coef,exp 。struct Bitnode *next 。Bitnode,*Bitree

16、。实验提小按先序次序输入二叉树中结点的值<一个字符)，'0'表示空树，生成二叉树的二叉链表存储结构，t为指向根结点的指针。然后按先序、中序及后序等方法遍历二叉树。void create(Bitree *t>/创建二叉树void preorder(Bitree t>/二叉树的先序遍历void inorder(Bitree t>/二叉树的中序遍历void inorder(Bitree t>/二叉树的后序遍历实验步骤1 .先用先序次序输入二叉树中结点的值建立二叉树，并测试你的程序，直至正确为止;2 .用递归方法进行三种不同的遍历；3 .用非递归方法进行三

17、种不同的遍历；。实验报告要求1 .阐述实验目的和实验内容；2 .提交模块化的实验程序源代码；3 .简述程序的测试过程，提交实录的输入、输出文件；4 .提交思考与练习题的代码和测试结果。思考与练习1 .写出一个算法统计树的叶子结点个数。2 .不用栈不用递归写一算法求树的后序遍历的第一个结点。实验六图的遍历的演示实验目的1 .熟练掌握图的邻接表存储方法和邻接表的建立算法；2 .掌握图的图的深度和广度遍历算法思想；预习要求1 .认真阅读教材或参考书，掌握图的深度和广度遍历算法思想;2 .写出求解本实验的程序；3 .设计好相应的测试用例。类型定义/*邻接点及顶点的定义*/typedef struct

18、nodeint adjvex 。struct node *next 。 node。/*顶点的定义*/typedef structint vex 。node *firstadj 。vertex 。/*邻接表的定义*/typedef struct vertex m 。/*m表示图中顶点的个数 */ adjlist 。实验提小void creategraph(adjlist *g>int n,e 。 /*n表示图中的顶点个数,e表示边的条数*/int j,i,k 。node *p,*q。/*由键盘输入图的顶点个数及边的条数*/printf("input n=&

19、quot;>。scanf("%d",&n> 。printf("input e=">。scanf("%d",&e> 。/*初始化邻接表*/g->m=n 。for(j=0 。 j<=n-1 。 +j>g->dataj.firstadj=NULL 。g->dataj.vex=j 。for(j=0 。 j<e 。 +j>/*由键盘输入一对边*/printf("input i,k:">。scanf ("%d%d",&a

20、mp;i,&k>。/*申请一个邻结点*/p=(node *>malloc(sizeof(node>> 。p->adjvex=k 。p->next=NULL。if(g->datai.firstadj=NULL>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 。printf("%3d

21、",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 。visitedv=1 。printf("%3d",v> 。Qrear+=v 。while(front!=rear>v=Qfron

22、t+。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<g.m。 +i> p=g.datai.firstadjwhile(p>printf("%d-%d,",i,p->adjvex

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

24、真阅读和掌握本实验的算法。2 .上机将本算法实现。3 .保存和打印出程序的运行结果，并结合程序进行分析。类型定义#define MAXSIZE 12 / 哈希表的最大容量，与所采用的哈希函数有关enum BOOLFalse,True。enum HAVEORNOTNULLKEY,HAVEKEY,DELKEY哈希表元素的三种状态，没有记录、有记录、有过记录但已被删除typedef struct /定义哈希表的结构int elemMAXSIZE 。 / 数据元素体HAVEORNOT elemflagMAXSIZE= /元素状态标志，没有记录、有记录、有过记录但已被删除 int count 。 /哈希

25、表中当前元素的个数HashTable 。typedef structint keynum 。 /记录的数据域，只有关键字一项Record 。实验提布void InitialHash(HashTable &H>/哈希表初始化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 ,否则返回Falseint Hash(int kn