还剩14页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
实验三图一.目的与要求熟悉图的存储结构,掌握有关算法的实现,了解图在计算机科学及其他工程技术中的应用二.例题[问题描述]给定一个图,设计一个程序,找出一条从某一顶点A到另一顶点B边数最少的一条路径[输入]图的顶点个数N,图中顶点之间的关系及要找的路径的起点A和终点Bo[输出]若A到B无路径,则输出There is no path,否则输出A到B路径上各顶点[存储结构]图采用邻接矩阵的方式存储[算法的基本思想]采用广度优先搜索的方法,从顶点A开始,依次访问与A邻接的顶点访问遍之VM,VA2,...,VAK,后,若没有访问B,则继续访问与V.邻接的顶点,V.UM,再访问与邻接顶点.•.,如此VAU,VA%.・.VA2下去,直至找到B,最先到达B点的路径,一定是边数最少的路径实现时采用队列记录被访问过的顶点每次访问与队头顶点相邻接的顶点,然后将队头顶点从队列中删去若队空,则说明到不存在通路在访问顶点过程中,每次把当前顶点的序号作为与其邻接的未访问的顶点的前驱顶点记录下来,以便输出时回溯[参考源程序]#includestdio.hint number;typedef struct{int q[20];int f,r;}queue;int nodelist[20][20];queue Q;int z
[20];int a,b,n,i,j,x,y;int finished;void enqqueue*Q,int x{Q-q[Q-r]=x;ifQ-r==19Q-r=0;elseQ-r++ifQ-r==Q-fprintfOverflow!\n;front queue*Q{ifQ-r==Q-fprintfUnderflow!\n;elsereturnQ-q[Q-f];void deqqueue*Q{if Q-r=Q-fprintf Underflow!\n;else{ifQ-f=19Q-f=O;elseQ-f++;int qemptyqueueQ{if Q.f==Q.rreturn1;elsereturn0;void readgraph{printf\nPlease inputn:;scanf n;printf^Please inputnodelist[i][j]:\n;fori=l;i=n;i++{forj=l;j=n;j++scanf nodelist[i][j];printf\n;printf ListTinkis bulitn;fori=l;i=n;i++{forj=l;j=n;j++printf r%3dz,,nodelist Ei][j];printf\n;}void shortestint a,int b{ifa==bnodelistEa][a]=2;else{enq Q,a;nodelistEa][a]=2;.finished=O;while!qemptyQ!finished{a=frontQ;deqQ;j=l;whilej=n!finished{if nodelist[a][j]=1nodelist[j][j]!=2{enqQ,j;nodelist[j][j]=2;z[j]=a;if j==b/*nodelist[a][j]=l*/finished=l;if!finished j++;...if!finished printfThere is nopath.;void writepathint a,int b{i=b;whilei!=a{printf%d-,i;i=z[i];printf%d,a;mainOreadgraph;printf^Please inputa:;scanf a;printfPlease inputb:;scanf b;Q.f=0;Q.r=0;shortest a,b;if finishedwritepath a,b;三.实习题
1.采用邻接表存储结构,编写一个求无向图的连通分量个数的算法
2.试基于图的深度优先搜索策略编写一程序,判别以邻接表方式存储的有向图中是否存在有顶点Vi到Vj顶点的路径iWj
3.在上述例题中,如改用邻接表的方式存储图,试编一程序实现上述算法顶点表nodelist的每个元素包含四个字段info markpre out其中mark为布尔类型,用来标记顶点是否被访问过开始时,所有元素的mark字段为false,每访问过一个顶点,则mark字段置为trueinfo为顶点值,pre为访问路径上该顶点的前实验四查找驱顶点的序号,out指向该顶点的出边表一.目的与要求通过本次实验,掌握查找表上的有关查找方法,并分析时间复杂度二.例题[问题描述]将折半查找算法写成完整的程序,并上机通过[输入]有序表12,23,28,35,37,39,50,60,78,90及待查找记录23,58[输出]输入23,表中存在待查找记录,则显示该记录在表中位置2,输入58显示该记录不存在[存储结构]有序表采用顺序方式存储[算法的基本思想]首先用待查找记录与查找区间中间位置记录比较,若相等则查找成功,返回该记录在表中的位置数,若小于中间位置记录,则修改区间上界为中间位置减1,若大于中间位置记录,则修改区间下界为中间位置加1,在新的区间内继续查找当查找区间下界大于上界,则该记录不存在[参考源程序]#include“stdio・h”typedef struct{int a[30];int length;}sqtable;sqtable st;int b=0;void createstintk{int i;printf^Please inputdata:;st.a[0]=-100;for i=l;!bi=k;i++{scanf%d”,st.a[i];if st.a[i]st.a[i-l]{printfInput dataerror.\n;b=l;.}.if!b{st.length=k;printf Thetable isbuilted.\n;void stfindsqtablest,int y{int f,1,h,m;l=l;h=st.length;f=l;while l=hf{m=l+h/2;if y==st.a[m]f=0;else ifyst.a[m]h=m-l;else l=m+l;..if!f printfFind%d inposition%d.\n”,y,m;else printfNot find%d.\n,y mainO{int n,x;printfCXnPlease inputn:;scanf n;createstn;if b==0{printfPlease inputyou wantfind value:;scanf%d,x;stfindst,x;三.实习题
1.编写程序实现下面运算在二叉排序树中查找关键字为key的记录
2.试将折半查找的算法改写成递归算法实验五内排序一.目的与要求通过本次实验,掌握线性表的排序方法,并分析时间复杂度二.例题[问题描述]将快速排序算法写成完整的程序上机通过,并统计递归深度[输入]待排序记录个数n,各待排序记录值[输出]n个记录由小到大排列的结果[存储结构]待排序记录顺序存储[算法的基本思想]快速排序算法每次任取一个记录的关键字为标准,将其余记录分为两组,将所有关键字小于或等于标准的记录都放在它的位置之前,将所有关键字大于标准的记录都放在它的位置之后对这两组再进行快速排序,直到完全有序每递归1次,递归深度加1[参考源程序]#includestdio.htypedef intnode;node afile[20];node x;int d,dl,n;int1,r,i,j;void qint1,int r{int p;d++;ifdlddl=d;printf dl=%d”,dl;printf d=%d\n”,d;ifKr{i=l;j=r;x=afile[i];while i!=j{whileafile[j]xji j—;ifijafile[i++]=afile[j];whileafile[i]xji i++;ifijafiletj-]=afile[i]afileEi]=x;for p=l;p=n;p++.printf%d,,afile[p];printf\n;ql,i-1;qi+l,r;d—;printf**%d**\n,d;mainO{int p;printf/z\nPlease inputn:\n;scanf%d〃,n;printfCPlease inputa string:;for p=l;p=n;p++scanf%d”,afile[p];d=0;dl=0;1=1;r=n;ql,r;for p=l;p=n;p++printf%d,,afiletp];printf\n;printf dl=%d\n”,dl;三.实习题
1.设计一个用链表表示的直接选择排序算法,并用程序实现算法说明已知待排序初始序列用单链表存贮,头指针head指向第一个结点,从这个待排序列中找出最小结点,插入head之后,用r来指示r以前为已排序序列,r以后为未排序序列再从未排序序列中找出最小结点插入r的后面,让r指向这个结点反复执行这个过程,直到排好序
2.对N个关键字取整数的记录进行整序,以使所有关键字为非负数的记录排在关键字为负数的记录之前,要求使用最少的附加空间,且算法的时间复杂度为0NprintfC Inputa linktablea string:;scanf c;if c=\nprintf CThisstring isempty;owhilec!=\n{q=nodelinkmallocsizeofnode;q-a=c;p-link=q;P=q;scanf%c,c;p-link=NULL;void writelinknodelink head{nodelink q;if head-link==NULL printfC Thislink isempty\n;oforq=head-link;q;q=q-linkprintf q-a;printf\n;int insertnodelink head,char kl,char k2{nodelink p,q;p=head-link;whilep-a!=klpp=p-link;if p{q=nodelinkmallocsizeofnode;q-a=k2;q-link=p-link;p-link=q;return1;else{printfThereisno%c\n,kl;return0;int deletenodelinkhead,char k{nodelink p,q;q=head;p=head-link;whilep-a!=kp{q=q-link;p=p-link;if p{q-1ink=p-link;return1;else{printf Thereisno%c\n/z,k;return0;void opsidenodelinkhead{nodelink p,q;p=head-link;whilep-link{q=p-link;p-link=q-link;q-link=head-link;head-link=q;mainchar kl,k2,k3;nodelinkhead;head=nodelinkmallocsizeofnode;head-link=NULL;readlinkhead;if head-link!=NULL{printf Buildlink is;writelinkhead;if head-link!=NULL{printfPlease inputa charyou wantto insertafter:;kl=getch;printf%c\n,kl;printfPlease inputa charyou wantto insert:;k2=getch;printf%c\n,k2;if inserthead,kl,k2{printfAfter%c insert%c,link is:,kl,k2;writelinkhead;printf^Please inputa charyou wantto delete:;k3=getch;printf%c\n,k3;if deletehead,k3{printfafter delete%c,link is:,k3;writelinkhead;if head-link!=NULL{printf,zOpsite resultis;opsidehead;writelinkhead;free head;.三.实习题
1.设顺序表A中的数据元素递增有序,试写一程序,将x插入到顺序表的适当位置上,使该表仍然有序
2.用单链表ha存储多项式A x=a+aixi+a2x2+…+anxn其中ai为非零系数,用单链表hb存储多项式BX=bo+bixUb2x2+…+bmXm其中bj为非零系数,要求计算CX=A x+Bx,结果存到单链表he中试写出程序
3.设有n个人围坐在一个圆桌周围,现从第s个人开始报数,数到第m的人出列,然后从出列的下一个人重新开始报数,数到m的人又出列,如此重复,直到所有的人全部出列为止Josephus问题是对于任意给定的n,m,s,求出按出列次序得到的n个人员的顺序表实验二树一.目的与要求熟悉树的各种表示方法和各种遍历方式,掌握有关算法的实现,了解树在计算机科学及其它工程技术中的应用二.例题[问题描述]任意给定一棵二叉树试设计一个程序,在计算机中构造该二叉树,并对它进行遍历[输入]一棵二叉树的结点若无子树,则可将其子树看作输入时,按照前序序列的顺序输入该结点的内容对下图,其输入序列为ABD..EH.・・CF.I..G..[输出]若为空二叉树,则输出THIS ISA EMPTYBINARY TREE若二叉树不空,按后序序列输出,对上例,输出结果为DHEBIFGCAo[存储结构]采用二叉链表存储[算法的基本思想]采用递归方法建立和遍历二叉树首先建立二叉树的根结点,然后建立其左右子树,直到空子树为止后序遍历二叉树时,先遍历左子树,后遍历右子树,最后访问根结点[参考源程序]#includestdio.h#includealloc.hstruct node{char info;struct node*11ink,*rlink;;typedef structnode NODE;NODE*creat{char x;NODE*p;.scanf x;printf x;ifx!=.{p=NODE*mallocsizeofNODE;p-info=x;p-llink=creatp-rlink=creat;elsep=NULLreturn p;void runNODE*t{ift{run t-llink;run t-rlink;printft-info;}mainONODE*T;printfPLease inputa tree:\n;T=creat;printf〃\n〃;if!TprintfCThis isa emptybinary tree.;else{printfThe resultof posttravese is:\n;runT..printf\n;三.实习题
1.编写递归算法,计算二叉树中叶子结点的数目
2.编写递归算法,在二叉树中求位于先序序列中第K个位置的结点
3.将上述例题用非递归程序实现。