軟件技術(shù)基礎(chǔ)實驗二報告

1.采用鄰接表存儲結(jié)構(gòu)，編寫一個求無向圖的連通分量個數(shù)的算法。#include<stdio.h>#include<malloc.h>intn;structVNode{//頂點intposition;structVNode*next;};structArcNode{//弧intmark;structVNode*first;};voidDFS(structArcNode*v,structArcNode*w){//深度優(yōu)先搜索structVNode*L;w->mark=1;L=w->first;while(L!=NULL){if((v+(L->position))->mark==0){DFS(v,(v+L->position));//遞歸調(diào)用}L=L->next;}}intmain(){inti,j,k;intnum=0;structArcNode*p;structVNode*temp;structVNode*flag;printf("\n請輸入頂點個數(shù)n：");scanf("%d",&n);while(n<1){printf("你輸入的值不合理，請重新輸入：\n");scanf("%d",&n);}p=(structArcNode*)malloc(n*sizeof(structArcNode));/*說明：1.Vi表示第i個頂點，它在表中的位置為i-1，如V3在表中的位置為2;2.如果輸入以V1為弧尾的所有弧(假設(shè)存在弧<V1,V3>和<V1,V2>)則輸入：21-1(只需輸入弧頭的位置，并用-1表示結(jié)束)*/for(i=0;i<n;i++){//創(chuàng)建無向圖printf("\n請輸入以V%d為弧尾的所有弧，并以-1結(jié)束輸入\n",i+1);scanf("%d",&k);if(k==-1){p[i].mark=0;p[i].first=NULL;}else{temp=(structVNode*)malloc(sizeof(structVNode));temp->position=k;temp->next=NULL;p[i].first=temp;p[i].mark=0;flag=temp;scanf("%d",&k);while(k!=-1){temp=(structVNode*)malloc(sizeof(structVNode));temp->position=k;temp->next=NULL;flag->next=temp;flag=temp;scanf("%d",&k);}}}i=0;while(p[i].mark==0){//計算連通分量的個數(shù)DFS(p,(p+i));num++;i=0;while(p[i].mark!=0&&i<n){i++;}}printf("此圖的連通分量個數(shù)為：%d\n",num);return0;}

2.試基于圖的深度優(yōu)先搜索策略編寫一程序，判別以鄰接表方式存儲的有向圖中是否存在有頂點Vi到Vj頂點的路徑(i≠j)。#include"stdio.h"#include"malloc.h"#include"conio.h"typedefstructArcNode{intadjvex;//該弧指向的頂點structArcNode*nextarc;//下一個弧intin;//判斷是否遍歷過該頂點}ArcNode;typedefstructVNode{intdata;//頂點信息ArcNode*firstarc;//指向第一條弧}VNode,AdjList[20];typedefstructALGraph{AdjListvertices;intvexnum,arcnum;//頂點數(shù)和弧數(shù)intkind;//圖的種類標志感覺沒什么用}ALGraph;intn,i,j;intm=0;ints=1;ALGraph*graph;voidread(ArcNode*firstarc){intx;chary;scanf("%c",&y);while(y=='')scanf("%c",&y);firstarc->nextarc=NULL;if(y=='\n'){return;}else{x=(int)y-48;ArcNode*t;t=newArcNode;t->nextarc=NULL;t->in=0;t->adjvex=x;firstarc->nextarc=t;read(firstarc->nextarc);}}//輸入該頂點出發(fā)的弧直到回車voidmkgraph(ALGraph*graph){charrub;ArcNode*t;VNode*list;scanf("%c",&rub);for(;s<=n;s++){printf("%d",s);t=newArcNode;graph->vertices[s].firstarc=t;read(graph->vertices[s].firstarc);}}//用循環(huán)控制輸入每個頂點的信息voidrun(ArcNode*firstarc){ArcNode*t;t=firstarc;if(t->adjvex==j){m=1;//若找到則m=1return;}if(t->in==0&&m==0&&t->adjvex>0&&t->adjvex<=n&&graph->vertices[t->adjvex].firstarc->nextarc!=NULL){t->in=1;run(graph->vertices[t->adjvex].firstarc->nextarc);}if(m==0&&t->nextarc!=NULL)run(t->nextarc);}//深度優(yōu)先搜索voidmain(){graph=newALGraph;printf("圖中有幾個頂點:");scanf("%d",&n);printf("請以鄰接表方式依次輸入各頂點的關(guān)系以回車作為結(jié)束標志:\n");mkgraph(graph);printf("已為您生成圖.\n\n請輸入您要尋找路徑的起點i和終點j(i!=j):");scanf("%d%d",&i,&j);while(i==j||i<=0||i>n||j<=0||j>n){printf("對不起,您輸入的數(shù)據(jù)有誤,請重新輸入:");scanf("%d%d",&i,&j);}//控制輸入的數(shù)據(jù)run(graph->vertices[i].firstarc->nextarc);if(m==1)printf("存在從%d到%d的路徑.",i,j);elseprintf("不存在從%d到%d的路徑.",i,j);getch();}

3.在上述例題中，如改用鄰接表的方式存儲圖，試編一程序?qū)崿F(xiàn)上述算法。頂點表nodelist的每個元素包含四個字段：infomarkpreout其中mark為布爾類型，用來標記頂點是否被訪問過。開始時，所有元素的mark字段為false，每訪問過一個頂點，則mark字段置為true。info為頂點值，pre為訪問路徑上該頂點的前驅(qū)頂點的序號，out指向該頂點的出邊表。#include<stdio.h>#include<stdlib.h>#defineMAXV100typedefstruct//鄰接矩陣存儲結(jié)構(gòu){intno;intinfo;}VertexType;typedefstruct{intedges[MAXV][MAXV];intn,e;VertexTypevexs[MAXV];}MGraph;typedefstructANode//鄰接表存儲結(jié)構(gòu){intadjvex;structANode*nextarc;intinfo;}ArcNode;typedefstructVnode{intdata;ArcNode*firstarc;}VNode;typedefVNodeAdjList[MAXV];typedefstruct{AdjListadjlist;intn,e;}ALGraph;typedefstructnode{intdata;structnode*next;}List;voidMatToList(MGraphg,ALGraph*&G){inti,j,n=g.n;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<n;i++)G->adjlist[i].firstarc=NULL;for(i=0;i<n;i++)for(j=n-1;j>=0;j--)if(g.edges[i][j]!=0){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;}G->n=n;G->e=g.e;}staticints1=0;voidFind(ALGraph*G,intx,intl,intk,intvisited[],intpath[],intd){inti,node;ArcNode*r;visited[x]=1;d++;path[d]=x;if(x==l&&d==k){s1++;if(s1==1)printf("\n給定的兩個頂點%d,%d之間存在長度為%d的簡單路徑.\n所有路徑為：\n",path[0],l,k);for(i=0;i<=k;i++)printf("%d",path[i]);printf("\n");}r=G->adjlist[x].firstarc;while(r!=NULL){node=r->adjvex;if(visited[node]==0)Find(G,node,l,k,visited,path,d);r=r->nextarc;}visited[x]=0;d--;}intmain(){intpath[MAXV],visited[MAXV],A[MAXV][MAXV],i,j,m,l,k;MGraphg;ALGraph*G;printf("請輸入頂點個數(shù)：");scanf("%d",&g.n);g.e=0;//printf("\n請輸入路徑條數(shù)：");//scanf("%d",&g.e);printf("\n請輸入鄰接矩陣：（若(vi,vj)屬于E(G),A[i][j]=1；其他，A[i][j]=0）\n\n");for(i=0;i<g.n;i++){for(j=0;j<g.n;j++)scanf("%d",&A[i][j]);getchar();}for(i=0;i<g.n;i++)for(j=0;j<g.n;j++){g.edges[i][j]=A[i][j];if(A[i][j]==1)g.e++;}MatTo