版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、<p><b> 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計</b></p><p> 設(shè)計題目:圖的建立與輸出</p><p> 系 別: 電子與信息工程學(xué)院 </p><p> 專 業(yè): 電子信息工程 </p><p> 班 級: 2009級(1)班 </
2、p><p> 姓 名: </p><p> 學(xué) 號: </p><p> 指導(dǎo)教師: </p><p> 2011年 06 月 20日</p><p><b> 目錄</b></p>
3、;<p> 一、設(shè)計題目(任選其一)…………………………………………3</p><p> 二、運行環(huán)境(軟、硬件環(huán)境)……………………………………3</p><p> 三、算法設(shè)計的思想…………………………………………………3</p><p> 四、算法的流程圖……………………………………………………3</p><p>
4、 五、算法設(shè)計分析……………………………………………………4</p><p> 六、源代碼……………………………………………………………4</p><p> 七、運行結(jié)果分析……………………………………………………14</p><p> 八、收獲及體會………………………………………………………16</p><p> 一、設(shè)計題目(任
5、選其一)</p><p><b> 圖的建立及輸出</b></p><p> 任務(wù):建立圖的存儲結(jié)構(gòu)(圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng),學(xué)生可以任選兩種類型),能夠輸入圖的頂點和邊的信息,并存儲到相應(yīng)存儲結(jié)構(gòu)中,而后輸出圖的鄰接矩陣。 </p><p> 二、運行環(huán)境(軟、硬件環(huán)境)</p><p>&
6、lt;b> 硬件環(huán)境:</b></p><p> CPU:1000MHz以上</p><p> 內(nèi)存:256MB以上</p><p><b> 硬盤:60G以上</b></p><p><b> 軟件環(huán)境:</b></p><p> 系統(tǒng)平臺:
7、Windows 2000 / Windows XP / Windows Vista / Windows 7 </p><p> 運行環(huán)境:TC 3.0 / Microsoft Visual C++ 6.0</p><p><b> 三、算法設(shè)計的思想</b></p><p> 1、存儲結(jié)構(gòu);鄰接矩陣 鄰接表</p><
8、p> 2、遍歷方式:深度優(yōu)先搜索(DFS) 廣度優(yōu)先搜索(BFS) 也可以對鄰接矩陣和臨界表直接輸出:其中DFS算法通過遞歸實現(xiàn),BFS算法通過隊列實現(xiàn)。</p><p> 3、拓撲排序和最小生成樹(Prime算法),具體實現(xiàn)見代碼。</p><p><b> 四、算法的流程圖</b></p><p><b> 五、算法
9、設(shè)計分析</b></p><p> 首先是建圖,圖和網(wǎng)的區(qū)別在于圖沒有權(quán)值(這里以固定值1代替),網(wǎng)有權(quán)值,有向和無向在存儲上的區(qū)別在于對于有向圖,輸入a[i][j],只存儲a[i][j],而對于無向圖還要存儲a[j][i]。</p><p> 其次是功能的實現(xiàn),鄰接表遍歷和鄰接矩陣遍歷都很簡單,按照它的存儲結(jié)構(gòu),依次輸出每個頂點和它鄰接的頂點,時間復(fù)雜度分別為O(n+e)
10、和O(n2);</p><p> 對于DFS算法是通過函數(shù)遞歸實現(xiàn)的,所采用的存儲結(jié)構(gòu)式是鄰接表,找鄰接點所需時間為O(e),其中e為無向圖的邊數(shù)或有向圖的弧數(shù),時間復(fù)雜度為O(n+e)。</p><p> 對于BFS算法是用隊列實現(xiàn)的,每個頂點至多進一次隊列。遍歷圖的過程實質(zhì)上是通過邊或弧找鄰接點的過程,因此廣度優(yōu)先搜索遍歷圖的時間復(fù)雜度和深度優(yōu)先搜索遍歷相同,兩者不同之處僅僅在于對
11、每個頂點訪問的順序不同</p><p> 對于拓撲排序,建立各項頂點的入度的時間復(fù)雜度為O(e),建零入度頂點棧的時間復(fù)雜度為O(n);在拓撲排序過程中,若有向圖無環(huán),則每個頂點進一次棧,出一次棧,入度減1的操作在while語句中總共執(zhí)行e次,所以總的時間復(fù)雜度為O(n+e)。</p><p> 對于Prime算法的最小生成樹,假設(shè)網(wǎng)中有n個頂點,則第一個進行初始化的循環(huán)語句的頻度為n
12、,第二個循環(huán)語句的頻度為n-1。其二是重新選擇具有最小代價的邊,其頻度為n。由此,Prime算法的時間復(fù)雜度為O(n2),與網(wǎng)中的邊數(shù)無關(guān),因此適用于求邊稠密的網(wǎng)的最小生成樹。</p><p><b> 六、源代碼 </b></p><p> #include <stdio.h></p><p> #include <
13、string.h></p><p> #include <stdlib.h></p><p> #include <ctype.h></p><p> #include <queue></p><p> #include <stack></p><p>
14、#include <process.h></p><p> using namespace std;</p><p> #define MAX_VERTEX_NUM 20</p><p> #define MAX 1000</p><p> #define DG 1</p><p> #defin
15、e DN 2</p><p> #define UDG 3</p><p> #define UDN 4</p><p> //typedef enum{DG,DN,UDG,UDN} GraphKind;</p><p> typedef char VertexType;</p><p> typedef
16、int VRType;</p><p> typedef char InfoType;</p><p> struct Close {</p><p> VertexType data;//頂點元素</p><p> VRType lowcost;</p><p><b> int j;</
17、b></p><p> }closedge[MAX_VERTEX_NUM]; //prime算法秋最小生成樹的輔助數(shù)組</p><p> typedef struct ArcNode{</p><p> int adjvex;//該弧所指向的頂點的位置</p><p> struct ArcNode *nextarc;/
18、/指向下一條弧的指針</p><p> int adj;//對于無權(quán)圖為0 或1;對于帶權(quán)圖為權(quán)值</p><p> InfoType *info;//該弧相關(guān)信息的指針</p><p> }ArcNode,AdjMartrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//為簡便起見鄰接矩陣的元素類型,此時部分元素?zé)o用&l
19、t;/p><p> typedef struct VNode{</p><p> int outdegree,indegree;</p><p> VertexType data;//頂點信息</p><p> ArcNode *firstarc;//指向第一條依附該頂點的弧的指針</p><p> }VNode
20、,AdjList[MAX_VERTEX_NUM];</p><p> typedef struct Graph{</p><p> AdjList vertices; //鄰接表</p><p> AdjMartrix arcs; //鄰接矩陣</p><p> int vexnum,arcnum; // 頂點個數(shù)及邊的數(shù)量
21、</p><p> int kind; //圖的類型</p><p><b> }ALGraph;</b></p><p> int cmp(const void *a,const void *b)</p><p><b> {</b></p><p
22、> if( *(char *)a-*(char *)b>=0)</p><p><b> return 1;</b></p><p> return -1;</p><p><b> }</b></p><p> int LocateVex(ALGraph & G,
23、VertexType e ){</p><p> for(int i=1;i<=G.vexnum;i++)</p><p> if(G.vertices[i].data==e) </p><p><b> return i;</b></p><p><b> return 0;</b>
24、</p><p><b> } </b></p><p> void Input_V(AdjList & ver,int n)</p><p><b> {</b></p><p> bool f=false;</p><p> char str[30];&
25、lt;/p><p> memset(str,0,sizeof(str));</p><p> printf("輸入每個頂點:用字母數(shù)字 如 ABCDEF 表示六個頂點:");</p><p> while(!f&&gets(str)){</p><p> int len=strlen(str);&
26、lt;/p><p> if(!len){ printf("\t\t你沒有輸入數(shù)據(jù),請輸入數(shù)據(jù):"); continue;}</p><p> if(len<n){ printf("\t\t輸入長度不夠,請重新輸入:"); continue;}</p><p> for(int i=0;i<n;i++)</p
27、><p> ver[i+1].data=str[i];</p><p> for( i=0;i<len;i++)</p><p> if(!(str[i]>='a'&&str[i]<='z'||str[i]>='A'&&str[i]<='Z'
28、;||str[i]>='0'&&str[i]<='9'))</p><p><b> break;</b></p><p> if(i<len) { printf("\t\t輸入非法字符,請重新輸入:"); continue;}</p><p>
29、qsort(str,len,sizeof(char),cmp);</p><p> for(i=0;i<len-1;i++)</p><p> if(str[i]==str[i+1]) break;</p><p> if(i<len-1){ printf("\t\t不能有兩個相同的字符,請重新輸入:"); continue;
30、} </p><p><b> f=true;</b></p><p> memset(str,0,sizeof(str));</p><p> //puts(str);</p><p><b> }</b></p><p><b> }</b>
31、;</p><p> void initGraph( ALGraph & G) // 初始化圖 包括 輸入頂點和弧的數(shù)目,并初始化鄰接表的數(shù)組</p><p><b> {</b></p><p> int a=-1,b=-1;</p><p> char str[23];</p>&
32、lt;p> printf("\t\t輸入頂點個數(shù)和弧的個數(shù):");</p><p><b> do{</b></p><p> scanf("%d%d%*c",&a,&b);</p><p> if(a==-1||b==-1) {</p><p>
33、gets(str);</p><p> printf("\t\t輸入不合法,請重新輸入:");</p><p><b> }</b></p><p> else break;</p><p> }while(1);</p><p> printf("%d %
34、d \n",a,b);</p><p> G.vexnum=a; G.arcnum=b;</p><p> Input_V(G.vertices,G.vexnum);</p><p> for(int i=1;i<=G.vexnum;i++){</p><p> //scanf("%d",&
35、;(G.vertices[i].data));// 構(gòu)造頂點向量</p><p> for(int j=1;j<=G.vexnum;j++){//初始化矩陣</p><p> G.arcs[i][j].adj=MAX;</p><p> G.arcs[i][j].info=NULL;</p><p><b> }&
36、lt;/b></p><p> G.vertices[i].indegree=0;</p><p> G.vertices[i].outdegree=0;</p><p> G.vertices[i].firstarc=NULL;</p><p><b> }</b></p><p>
37、;<b> }</b></p><p> void Input(char & v1,char & v2,int &d ,ALGraph & G)</p><p><b> {</b></p><p> char str[30];</p><p><b
38、> int i;</b></p><p> bool flag=false;</p><p> memset(str,0,sizeof(str));</p><p> while(!flag&&gets(str)){</p><p> int length =strlen(str);</p&g
39、t;<p> for(i=4;i<length;i++){</p><p> if(!isalnum(str[0])||!isalnum(str[2])) break;</p><p> if(str[1]!=' '||str[3]!=' ') break;</p><p> if(!isdigit(st
40、r[i])) break;</p><p><b> }</b></p><p> if(length<5||i<length) { printf("存在不不合法字符或輸入格式錯誤 請重新輸入\n"); continue;}</p><p> //printf("%d %s\n",le
41、ngth,str);</p><p> for(i=4,d=0;i<length;i++)</p><p> d=d*10+str[i]-'0';</p><p> if((G.kind==1||G.kind==3)&&d!=1) { printf("存在不不合法字符或輸入格式錯誤 請重新輸入\n");
42、 continue;}</p><p> v1=str[0]; v2=str[2];</p><p> flag=true;</p><p> memset(str,0,sizeof(str));</p><p><b> }</b></p><p><b> }</b&
43、gt;</p><p> int CreateDG_DN_UDG_UDN(ALGraph & G){ // 有向圖、有向網(wǎng)、無向圖、無向網(wǎng)以及鄰接矩陣的具體實現(xiàn)</p><p> VertexType v1,v2;</p><p> int weight;</p><p> int flag=G.kind;</p&
44、gt;<p> initGraph(G);</p><p> int tem=G.arcnum;</p><p> printf("每條邊依附的兩個定點及其權(quán)值(>0),無權(quán)輸入1 如 A B 20 和 A B 1 \n");</p><p> while(tem--){</p><p>
45、 Input(v1,v2,weight,G);</p><p> int i=LocateVex(G,v1); // 定位v1 v2在數(shù)組中的位置</p><p> int j=LocateVex(G,v2);</p><p> G.arcs[i][j].adj=flag==1||flag==3?1:weight; // 建立鄰接矩陣</p>
46、;<p> if(flag==3||flag==4){</p><p> G.arcs[j][i].adj=flag==3?1:weight;</p><p><b> }</b></p><p> ArcNode * q=(ArcNode *)malloc(sizeof(ArcNode));</p><
47、;p> q->adj=weight;</p><p> q->adjvex=j;</p><p> q->nextarc=NULL;</p><p> if(G.vertices[i].outdegree==0) </p><p> G.vertices[i].firstarc=q; </p>
48、<p><b> else{</b></p><p> ArcNode *p=G.vertices[i].firstarc;</p><p> while(p->nextarc)</p><p> p=p->nextarc;</p><p> p->nextarc=q;</
49、p><p><b> }</b></p><p> if(flag==3||flag==4){ // 此if 語句是為創(chuàng)建無向圖 及 無向網(wǎng)準(zhǔn)備的</p><p> ArcNode * q=(ArcNode *)malloc(sizeof(ArcNode));</p><p> q->adj=weigh
50、t;</p><p> q->adjvex=i;</p><p> q->nextarc=NULL;</p><p> if(G.vertices[j].outdegree==0&&G.vertices[j].indegree==0) </p><p> G.vertices[j].firstarc=q;&
51、lt;/p><p><b> else{</b></p><p> ArcNode *p=G.vertices[j].firstarc;</p><p> while(p->nextarc)</p><p> p=p->nextarc;</p><p> p->nextar
52、c=q;</p><p><b> }</b></p><p><b> }</b></p><p> G.vertices[i].outdegree++;</p><p> if(flag==3||flag==4) G.vertices[j].outdegree++;</p>
53、<p><b> else </b></p><p> G.vertices[j].indegree++;</p><p><b> }</b></p><p><b> return 0;</b></p><p><b> }</b>
54、;</p><p> void VisitDG_DN_UDG_UDN(ALGraph & G,int f){ // 遍歷鄰接表,</p><p> ArcNode *p;</p><p><b> if(f){</b></p><p> printf("\t\t遍歷鄰接表 :\n");
55、</p><p> for(int i=1;i<=G.vexnum;i++){</p><p> p=G.vertices[i].firstarc;</p><p> printf("\t\t與第%d個頂點%c鄰接頂點有:",i,G.vertices[i].data);</p><p><b>
56、 while(p){</b></p><p> printf("%c ",G.vertices[p->adjvex].data);</p><p> p=p->nextarc;</p><p><b> }</b></p><p> if(G.kind==3||G.ki
57、nd==4) printf("度數(shù)為 %d ",G.vertices[i].outdegree);</p><p> else printf("出度為 %d ,入度為 %d ",G.vertices[i].outdegree,G.vertices[i].indegree);</p><p> printf("\n");<
58、;/p><p><b> }</b></p><p><b> }</b></p><p><b> else{</b></p><p> printf("遍歷鄰接矩陣 :\n\t\t ");</p><p> for(in
59、t i=1;i<=G.vexnum;i++)</p><p> printf("%c %c",G.vertices[i].data,i==G.vexnum?'\n':' ');</p><p> printf("\t\t─┼────────────────\n");</p><p>
60、; //printf("─┼───────\n │\n │");</p><p> for( i=1;i<=G.vexnum;i++){</p><p> printf("\t\t%c │",G.vertices[i].data);</p><p> for(int j=1;j<=G.vexnum;
61、j++)</p><p> //printf("%5d%c",G.arcs[i][j].adj,j==G.vexnum?'\n':' ');</p><p> if(G.arcs[i][j].adj==MAX) printf("∞ %c",j==G.vexnum?'\n':' '
62、);</p><p> else printf("%d %c",G.arcs[i][j].adj,j==G.vexnum?'\n':' ');</p><p><b> }</b></p><p><b> }</b></p><p>&
63、lt;b> }</b></p><p> bool visit[MAX_VERTEX_NUM];//深度優(yōu)先搜索</p><p> void DFS(ALGraph & G,int i){</p><p> visit[i]=true; </p><p> printf("%c ",G
64、.vertices[i].data);</p><p> ArcNode * p;</p><p> for(p=G.vertices[i].firstarc;p;p=p->nextarc){</p><p> if(!visit[p->adjvex]) DFS(G,p->adjvex); </p><p>&
65、lt;b> }</b></p><p><b> } </b></p><p> void DFSTraverse(ALGraph & G){ </p><p><b> int i;</b></p><p> printf("\t\t深度優(yōu)先搜索
66、:");</p><p> for( i=0;i<MAX_VERTEX_NUM;i++)</p><p> visit[i]=false;</p><p> for( i=1;i<=G.vexnum;i++)</p><p> if(!visit[i]) DFS(G,i); </p><p&
67、gt;<b> }</b></p><p> queue <int> Q;</p><p> void BFSTraverse(ALGraph & G) //廣度優(yōu)先搜索</p><p><b> {</b></p><p><b> int i,j;<
68、;/b></p><p> printf("\n\t\t廣度優(yōu)先搜索 :");</p><p> for( i=0;i<MAX_VERTEX_NUM;i++)</p><p> visit[i]=false;</p><p> for(i=1;i<=G.vexnum;i++){</p>
69、<p> if(!visit[i]){</p><p> visit[i]=true; </p><p> printf("%c ",G.vertices[i].data);</p><p> Q.push(i);</p><p> while(!Q.empty()){</p>&l
70、t;p> j=Q.front();</p><p><b> Q.pop();</b></p><p> for(ArcNode *w=G.vertices[j].firstarc;w;w=w->nextarc)</p><p> if(!visit[w->adjvex]){</p><p>
71、 visit[w->adjvex]=true; </p><p> printf("%c ",G.vertices[w->adjvex].data);</p><p> Q.push(w->adjvex);</p><p><b> }</b></p><p><b>
72、; }</b></p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p> void MinSpanTree_PRIM(ALGraph G,VertexType u)// prim算法
73、的最小生成樹</p><p><b> {</b></p><p> if(G.kind!=UDN) {printf("沒有最小成樹\n");return;}</p><p> int i,j,k;</p><p> int mincost=0;</p><p> p
74、rintf("\n\t\tprim算法的最小生成樹 :");</p><p> k=LocateVex(G,u);</p><p> for(i=1;i<=G.vexnum;i++){</p><p> closedge[i].data=G.vertices[i].data;</p><p> closedg
75、e[i].lowcost=G.arcs[k][i].adj;</p><p> closedge[i].j=k;</p><p><b> }</b></p><p> closedge[k].lowcost=0;</p><p> for(i=1;i<=G.vexnum;i++){</p>
76、<p> //for(k=1;k<=G.vexnum;k++)</p><p> //printf("(%d %d) %c",closedge[k].data,closedge[k].lowcost,k==G.vexnum?'\n':' ');</p><p><b> k=0; </b>
77、</p><p> for(j=1;j<=G.vexnum;j++){ //選出T的下一個結(jié)點,第k個頂點</p><p> if(closedge[j].lowcost==0) continue;</p><p> if(k==0){k=j;continue;}</p><p> if(closedge[k].lowcos
78、t>closedge[j].lowcost) </p><p><b> k=j;</b></p><p><b> }</b></p><p> //for(int t=1;t<=G.vexnum;t++)</p><p> //printf("(%d %d %d%
79、c)\t",t,closedge[t].lowcost,closedge[t].j,t==G.vexnum?'\n':' ');</p><p> if(k)printf("(%c %c %d) ",G.vertices[closedge[k].j].data,G.vertices[k].data,closedge[k].lowcost); //最
80、小生成樹的頂點向量、值、及權(quán)</p><p> mincost+=closedge[k].lowcost;</p><p> closedge[k].lowcost=0;</p><p> for(j=1;j<=G.vexnum;j++)</p><p> if(G.arcs[j][k].adj<closedge[j].l
81、owcost){</p><p> closedge[j].data=G.vertices[j].data;</p><p> closedge[j].lowcost=G.arcs[j][k].adj;</p><p> closedge[j].j=k;</p><p><b> }</b></p>
82、<p> }printf("\n\t\t最小代價和為 :%d\n",mincost);</p><p><b> }</b></p><p> int TOpologicalSort(ALGraph & G)//拓撲排序</p><p><b> {</b></p>
83、;<p> stack <int> S;</p><p> int i,j,count=0;</p><p> int indegree[30];</p><p> for(i=1;i<=G.vexnum;i++)</p><p> indegree[i]=G.vertices[i].indegree
84、;</p><p> if(G.kind==3||G.kind==4) {printf("無向圖不能進行拓撲排序\n");return -1;}</p><p> printf("\n拓撲排序:");</p><p> for(i=1;i<=G.vexnum;i++)</p><p> i
85、f(G.vertices[i].indegree==0)S.push(i);</p><p> while(!S.empty()){</p><p> j=S.top(); S.pop();</p><p><b> count++;</b></p><p> printf("(%d %c) &quo
86、t;,j,G.vertices[j].data);</p><p> for(ArcNode *p=G.vertices[j].firstarc;p;p=p->nextarc){</p><p> int k=p->adjvex;</p><p> int d=--(G.vertices[k].indegree);</p><p
87、> if(!d)S.push(k);</p><p><b> }</b></p><p><b> }</b></p><p> for(i=1;i<=G.vexnum;i++)</p><p> G.vertices[i].indegree=indegree[i];<
88、/p><p> if(G.vexnum==count){printf("\n"); return 1;}</p><p> printf("失??!\n");return 0;</p><p><b> } </b></p><p> void Choose(ALGraph
89、&G){</p><p> int choice=G.kind;</p><p> char str[30];</p><p><b> do{</b></p><p> system("cls");</p><p> printf("\n\n\t\
90、t▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄\n");</p><p> printf("\t\t▌?wù)堖x擇操作:\t\t\t\t ▌\n");</p><p> printf("\t\t▌1、用鄰接矩陣遍歷\t4、廣度優(yōu)先搜索\t ▌\n\t\t▌2、用鄰接表遍歷\t5、拓撲排序\t ▌\n");</p><p>
91、; printf("\t\t▌3、深度優(yōu)先搜索\t6、最小生成樹\t ▌\n\t\t▌7、返回\t\t8、退出程序\t\t ▌\n");</p><p> printf("\t\t ▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲▲\n\n");</p><p> printf("\t\t請輸入你的選擇(1-7):");</p&
92、gt;<p><b> do{</b></p><p> memset(str,0,sizeof(str));</p><p> gets(str);</p><p> if(strlen(str)>1) choice=-1;</p><p> else if(str[0]<'
93、;1'||str[0]>'8') choice=-1;</p><p> else choice=str[0]-'0';</p><p> if(choice==-1) printf("\t\t輸入不合法,請重新輸入:");</p><p> else break;</p><
94、;p> }while(1);</p><p> switch(choice){</p><p> case 1: VisitDG_DN_UDG_UDN(G,0); break;</p><p> case 2: VisitDG_DN_UDG_UDN(G,1); break;</p><p> case 3: DFSTraver
95、se(G);break;</p><p> case 4: BFSTraverse(G); break;</p><p> case 5:TOpologicalSort(G); break;</p><p> case 6: MinSpanTree_PRIM(G,G.vertices[1].data);break;</p><p>
96、case 7:return;</p><p> case 8:exit(0);</p><p><b> }</b></p><p> printf("\n\t\t按回車鍵繼續(xù)....."); getchar();</p><p> }while(1);</p><p>
97、;<b> }</b></p><p> void Menu(ALGraph &G){</p><p> bool f=true;</p><p> int choice=-1;</p><p> char str[30];</p><p><b> do{</
98、b></p><p> system("cls");</p><p> printf("\n\n\t\t╔════════════════════╗\n");</p><p> printf("\t\t║\t\t\t\t\t ║\n");</p><p> print
99、f("\t\t║\t\t圖的建立與操作\t\t ║\n");</p><p> printf("\t\t║\t\t\t\t\t ║\n");</p><p> printf("\t\t╚════════════════════╝\n\n");</p><p> printf("\t\t請
100、選擇建圖方式:\n");</p><p> printf("\t\t\t1、有向圖\t2、有向網(wǎng)\n");</p><p> printf("\t\t\t3、無向圖\t4、無向網(wǎng)\n\t\t\t5、退出\n\n");</p><p> printf("\t\t請輸入你的選擇(1-5):");
101、</p><p><b> do{</b></p><p> memset(str,0,sizeof(str));</p><p> gets(str);</p><p> if(strlen(str)>1) choice=-1;</p><p> else if(str[0
102、]<'0'||str[0]>'9') choice=-1;</p><p> else choice=str[0]-'0';</p><p> if(choice<1||choice>5) </p><p> printf("\t\t你的輸入不合法,請重新輸入(1-5):&quo
103、t;);</p><p><b> else</b></p><p><b> break;</b></p><p> }while(1);</p><p> if(choice==5) break;</p><p><b> else{</
104、b></p><p> G.kind=choice;</p><p> CreateDG_DN_UDG_UDN(G);</p><p> system("cls");</p><p> printf("\n\n\n\n\t\t圖已建立,按回車鍵繼續(xù)其他操作...");</p>
105、<p> getchar();</p><p> Choose(G);</p><p><b> }</b></p><p> }while(1);</p><p><b> }</b></p><p> int main()</p>&
106、lt;p><b> {</b></p><p> ALGraph G;</p><p> printf("");</p><p><b> Menu(G); </b></p><p><b> return 0;</b></p>
107、<p><b> }</b></p><p><b> 七、運行結(jié)果分析</b></p><p> 測試數(shù)據(jù)及運行結(jié)果見以下截圖</p><p> 主界面的建立,可以自由選擇建立圖,輸入數(shù)據(jù)應(yīng)嚴(yán)格按照要求,否則,無法建立 </p><p> 鄰接矩陣的遍歷有邊輸出權(quán)值(對于網(wǎng))
108、或1(對于圖),無邊輸出無窮</p><p> 用鄰接表遍歷,依次輸出每個頂點的臨鄰接點,并輸出本點的出度和入度</p><p> 以下四個截圖分別是深度優(yōu)先搜索、廣度優(yōu)先搜索、拓撲排序和最小生成樹的運行結(jié)果,均用字符表示其遍歷或操作的順序</p><p><b> 其他測試數(shù)據(jù):</b></p><p><
109、b> 3</b></p><p><b> 5 8</b></p><p><b> ABCDE</b></p><p> D E 1 C E 1 D C 1 A E 1 B E 1 B A 1 A D 1 B C 1</p><p><b> 2
110、</b></p><p><b> 5 6</b></p><p><b> 12345</b></p><p> 1 2 1 1 3 1 2 3 1 4 5 1 5 2 1 4 3 1</p><p><b> 八、收獲及體會</b></p
111、><p> 在進行這次課程設(shè)計的過程中,我真正學(xué)到了教科書上所沒有或者真正用到了課本上的知識。這樣,既鞏固了舊知識,又掌握了新知識。所以,數(shù)據(jù)結(jié)構(gòu)課程設(shè)計是我們的重中之重,是提高我們專業(yè)知識與實踐相結(jié)合的重要手段。</p><p> 這次課程設(shè)計,對我進行了結(jié)構(gòu)化程序設(shè)計的初步訓(xùn)練,培養(yǎng)了我的數(shù)據(jù)抽象能力。在實際操作過程中,遇到很多問題,通過查書,上網(wǎng)查資料,最后問老師,把問題解決,在這個
112、過程中,把課堂上的知識很好的運用到實際上,還通過解決問題,學(xué)習(xí)到很多課外知識,引導(dǎo)和激發(fā)我對數(shù)據(jù)結(jié)構(gòu)的興趣,同時還要培養(yǎng)我搜索分析信息、查閱幫助文檔、整理經(jīng)驗編寫文檔、合作交流的能力。</p><p> 課程設(shè)計中我遇見了一些難點,比方說 輸入數(shù)據(jù)時錯誤的輸入可能就會讓程序崩潰,經(jīng)過仔細思考,查閱資料,請教同學(xué),最后都圓滿的解決當(dāng)然,這是我收獲比較大一點。除此之外,我覺得一個好程序不僅在于它的功能的實現(xiàn),更重要
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---圖的建立與輸出
- 《圖的建立與遍歷》數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--數(shù)據(jù)結(jié)構(gòu)課程設(shè)計----huffman編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-----圖的遍歷
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---圖的遍歷
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用(算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計)
- 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計
- 算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
評論
0/150
提交評論