《数据结构教学资料》实验三

《《数据结构教学资料》实验三》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、本科实验报告课程名称：数据结构实验项口：图结构实验地点：逸夫楼502专业班级：软件1211学号：2012005267学生姓名：杨园园指导教师：梁美丽2013/12/6实验项目（居中）一、实验目的和要求目的与要求二、实验内容和原理简述题目要解决的问题是什么，并说明输入和输出数据的形式。简述存储结构和算法的基本思想。三、主要仪器设备使用的计算机：硕件配置、软件环境列出调试通过的源程序。例题：#includeintnumber;typedefstruct{intq[20];intf,r;}queue;intnode

2、list[20][20];queueQ;intz[20];inta,b,n,i,j,x,y;intfinished;voidenq(queue*Q,intx){Q->q[Q->r]=x;if(Q->r==19)Q->r=0;elseQ->r++;if(Q->r==Q->f)printf(”Overflow!“);}front(queue*Q){if(Q->r==Q->f)printf("Underflow!");elseretum(Q->q[Q->f]);}voiddeq(queue*Q){if(Q->r==Q->f)

3、printf(nUnderflow!n);else{if(Q->f==19)Q->f=O;elseQ・>f++;}}intqempty(queueQ){if(Q.f==Q.r)return1;elsereturn0;)voidreadgraph(){printf(MPleasei叩utn:");scanf(”％d”,&n);printf("Pleaseinputnodelist[i][j]:");for(i=l;i<=n;i++){for(j=l；j<=n;j++)scanf("%d",&nodelist[i][j

4、]);}printf(””);printfC'List-linkisbulit");for(i=l;i<=n;i++){for(j=l;j<=n;j++)printf("%3dM,nodelist[i][j]);printf(MM);}}voidshortest(inta,intb){if(a==b)nodelist[a][a]=2;clsc{enq(&Q,a);nodelist[aj[a]=2;finished=O;while(!qempty(Q)&&!finished)}a=front(&Q);deq(&Q);

5、j=l；whilc((j<=n)&&!finishcd){if((nodelist[a][j]==l)&&(nodelist[j][j]!=2)){enq(&Q,j);nodelist[j][j]=2;z[j]二a;if(j==b)/*&&(nodelist[a][j]==1))*/finished=l;}if(!finished)j++；}}if(Jfinished)printf(uThereisnopath.'*);voidwritepath(inta,intb){i=b;while(i!=a){printf(M%d<-”

6、,i);i=z[i];)printf(”％d”,a);Imain(){rcadgraph();printf("Pleaseinputa:");scanf(H%d",&a);printf("Pleaseinputb:”)；scanf(”％d“,&b);Q.仁0;Q.r=0;shortest(a,b);if(finished)writepath(a,b);}试基于图的深度优先搜索策略编写一程序，判別以邻接表方式存储的有向图中是否存在有顶点Vi到比顶点的路径(i^j)o#include#include

7、.h>#includeintn;〃定义全局变量，表示所构造的图中的总的顶点个数〃川于构造结点之间联系关系的弧结点typedefstructarcNodeIintposition;〃用来存放毎点的标号structarcNode*next;〃用來存放结点的下一个弧的信息}ArcNode,*ArcNode_;//zE义用来构造元索的结点typedefstructvNode{intmark;〃在程序屮用来标识是否被访问过ArcNode*first;//存储连接到该结点的第一个弧信息的地址}VNode,*VNode

8、_;〃函数声明部分VNode_Structure();//构造一个图voidDFS(VNode_Chart,intt);〃递归方法实现链表深度探索voidInitializc(VNodc_Chart);//初始化所构造的顶点信息voidEnd(VNode_Chart);//收