《c程序设计基础》实验指导

《《c程序设计基础》实验指导》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》实验指导实验6图的建立与遍历实验目的1、熟悉图的存储结构。2、掌握有关算法的实现。3、了解图在计算机科学及其他工程技术中的应用。实验6图的建立与遍历实验内容问题描述：给定一个图，设计一个程序，找出一条从某一顶点A到另一顶点B边数最少的一条路径。输入：图的顶点个数N，图中顶点之间的关系及要找的路径的起点A和终点B。输出：若A到B无路径，则输出“Thereisnopath”，否则输出A到B路径上各顶点。存储结构：图采用邻接矩阵的方式存储。实验6图的建立与遍历实验内容算法的基本思想：采用广度优先搜索的

2、方法，从顶点A开始，依次访问与A邻接的顶点VA1,VA2,...,VAK,访问遍之后,若没有访问B，则继续访问与VA1邻接的顶点VA11,VA12,...,VA1M，再访问与VA2邻接顶点...，如此下去，直至找到B，最先到达B点的路径，一定是边数最少的路径。实现时采用队列记录被访问过的顶点。每次访问与队头顶点相邻接的顶点，然后将队头顶点从队列中删去。若队空，则说明到不存在通路。在访问顶点过程中，每次把当前顶点的序号作为与其邻接的未访问的顶点的前驱顶点记录下来，以便输出时回溯。实验6图的建立与遍历实验内容参

3、考源程序：#includeintnumber;typedefstruct{intq[20];intf,r;}queue;intnodelist[20][20];queueQ;intz[20];inta,b,n,i,j,x,y;intfinished;实验6图的建立与遍历实验内容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(

4、queue*Q){if(Q->r==Q->f)printf("Underflow!");elsereturn(Q->q[Q->f]);}实验6图的建立与遍历实验内容voiddeq(queue*Q){if(Q->r==Q->f)printf("Underflow!");else{if(Q->f==19)Q->f=0;elseQ->f++;}}intqempty(queueQ){if(Q.f==Q.r)return1;elsereturn0;}实验6图的建立与遍历实验内容voidreadgraph(){

5、printf("Pleaseinputn:");scanf("%d",&n);printf("Pleaseinputnodelist[i][j]:");for(i=1;i<=n;i++){for(j=1;j<=n;j++)scanf("%d",&nodelist[i][j]);}printf("");printf("List-linkisbulit");for(i=1;i<=n;i++){for(j=1;j<=n;j++)printf("%3d",nodelist[i][j]);printf

6、("");}}实验6图的建立与遍历实验内容voidshortest(inta,intb){if(a==b)nodelist[a][a]=2;else{enq(&Q,a);nodelist[a][a]=2;finished=0;while(!qempty(Q)&&!finished){a=front(&Q);deq(&Q);j=1;while((j<=n)&&!finished){if((nodelist[a][j]==1)&&(nodelist[j][j]!=2)){enq(&Q,j);nodelist

7、[j][j]=2;z[j]=a;实验6图的建立与遍历实验内容if(j==b)/*&&(nodelist[a][j]==1))*/finished=1;}if(!finished)j++;}}if(!finished)printf("Thereisnopath.");}}voidwritepath(inta,intb){i=b;while(i!=a){printf("%d<-",i);i=z[i];}实验6图的建立与遍历实验内容printf("%d",a);}main(){readgraph();printf

8、("Pleaseinputa:");scanf("%d",&a);printf("Pleaseinputb:");scanf("%d",&b);Q.f=0;Q.r=0;shortest(a,b);if(finished)writepath(a,b);