版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、<p><b> 目 錄</b></p><p><b> 1.需求分析1</b></p><p><b> 1.1問題描述1</b></p><p><b> 1.2系統(tǒng)功能1</b></p><p><b> 2.概
2、要設(shè)計(jì)2</b></p><p><b> 2.1 流程圖2</b></p><p> 2.2結(jié)構(gòu)體、函數(shù)及說明3</p><p><b> 3.詳細(xì)設(shè)計(jì)4</b></p><p> 3.1遍歷函數(shù)設(shè)計(jì)4</p><p> 3.2容錯性方法設(shè)計(jì)
3、4</p><p> 3.3生成鄰接表設(shè)計(jì)5</p><p> 3.4鄰接表遍歷設(shè)計(jì)6</p><p><b> 4.程序源代碼7</b></p><p> 5.調(diào)試分析和測試結(jié)果16</p><p> 5.1調(diào)試分析16</p><p> 5.1調(diào)
4、試案例16</p><p> 5.3測試過程、結(jié)果截圖:17</p><p> 5.3.1容錯性測試:17</p><p> 5.3.2無向圖(案例一)測試:20</p><p> 5.3.3有向圖(案例二)測試:22</p><p> 6.課程設(shè)計(jì)總結(jié)24</p><p>
5、;<b> 參考文獻(xiàn)25</b></p><p><b> 1.需求分析</b></p><p><b> 1.1問題描述 </b></p><p> (1)對任意給定的圖(頂點(diǎn)數(shù)和邊數(shù)自定),建立它的鄰接表并輸出。</p><p> (2)然后利用隊(duì)列的五種基本運(yùn)
6、算(置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空)實(shí)現(xiàn)圖的廣度優(yōu)先搜索遍歷。</p><p> ?。?)畫出搜索順序示意圖。</p><p><b> 1.2系統(tǒng)功能</b></p><p> ?。?)首先輸入圖的類型,有向或無向圖(因?yàn)楸闅v與權(quán)值無關(guān),所以沒有涉及帶權(quán)圖)。然后輸入圖的頂點(diǎn)數(shù)、邊數(shù)和各條邊,之后生成該圖的鄰接表并輸出。</
7、p><p> (2)再輸入要遍歷該圖的起點(diǎn),然后從所輸入的點(diǎn)廣度搜索該圖的鄰接表,并按遍歷順序輸出頂點(diǎn)內(nèi)容。之后決定是否繼續(xù)遍歷該圖或輸入另一個(gè)需要遍歷的圖亦或是結(jié)束程序。2.概要設(shè)計(jì)</p><p><b> 2.1流程圖</b></p><p><b> 是</b></p><p><b
8、> 否</b></p><p><b> 否</b></p><p><b> 是</b></p><p><b> 圖 2-1 流程圖</b></p><p> 2.2結(jié)構(gòu)體、函數(shù)及說明</p><p> typedef
9、struct ArcNode//鄰接表表結(jié)點(diǎn)</p><p><b> {</b></p><p> int adjvex;//該弧所指向的頂點(diǎn)位置</p><p> struct ArcNode *nextarc;//指向下一條弧的指針</p><p> //InfoType *info;//該弧相關(guān)信息指針&
10、lt;/p><p><b> }ArcNode;</b></p><p> typedef struct VNode//鄰接表頭結(jié)點(diǎn)</p><p><b> {</b></p><p> VertexType data;//結(jié)點(diǎn)信息</p><p> ArcNode
11、*firstarc;//指向第一條依附該結(jié)點(diǎn)的弧的指針</p><p> }VNode,AdjList[MAX_VERTEX_NUM];</p><p> typedef struct//圖</p><p><b> {</b></p><p> AdjList Vertices;//鄰接表頭結(jié)點(diǎn)數(shù)組</p
12、><p> int vexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)</p><p> int kind;//圖的種類標(biāo)志(有向圖:0,無向圖:1)</p><p><b> }ALGraph;</b></p><p> void print(int v)//輸出頂點(diǎn)信息</p><p>
13、 int FirstAdjVex(ALGraph G,int u)//在鄰接表G中取第u個(gè)頭結(jié)點(diǎn)</p><p> void NextAdjVex(ALGraph G,int u,int w)// 在鄰接表G中取第u個(gè)頭結(jié)點(diǎn)之后的結(jié)點(diǎn)w的下一結(jié)點(diǎn)</p><p> void BFSTraverse(ALGraph G,queue<int> Q,bool visited[]
14、,int m,int n,void (*Visit)(int))//使用輔助隊(duì)列Q從鄰接表結(jié)點(diǎn)m開始n結(jié)束廣度遍歷鄰接表圖G</p><p><b> 3.詳細(xì)設(shè)計(jì)</b></p><p><b> 3.1遍歷函數(shù)設(shè)計(jì)</b></p><p> void BFSTraverse(ALGraph G,queue<
15、int> Q,bool visited[],int m,int n,void (*Visit)(int))//使用輔助隊(duì)列Q從鄰接表結(jié)點(diǎn)m開始n結(jié)束廣度遍歷鄰接表圖G</p><p> { //按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組visited。</p><p> while(!Q.empty()) Q.pop();//置空的輔助隊(duì)列Q</p>&
16、lt;p> for(int v=m;v<n;++v)</p><p> if(!visited[v])//如果v尚未訪問</p><p><b> {</b></p><p> visited[v]=true;</p><p> Visit(v);//訪問v</p><p>
17、 Q.push(v);//v入隊(duì)列</p><p> while(!Q.empty())</p><p><b> {</b></p><p> int u = Q.front(); </p><p> Q.pop();//對頭元素出隊(duì)并置為u</p><p> for( int w
18、 = FirstAdjVex(G,u); w >= 0; w = NextAdjVex(G,u,w))//從以u為頭結(jié)點(diǎn)的鄰接表開始遍歷到鏈表中的最后一個(gè)結(jié)點(diǎn)</p><p> if(!visited[w])//w為u的尚未訪問的鄰接結(jié)點(diǎn)</p><p><b> {</b></p><p> visited[w]=true;<
19、;/p><p> Visit(w);//訪問w</p><p> Q.push(w);//w入隊(duì)列</p><p><b> }//if</b></p><p><b> }//while</b></p><p><b> }//if</b><
20、;/p><p> }//BFSTraverse*/</p><p> 3.2容錯性方法設(shè)計(jì)</p><p> cout<<"\n請輸入圖的弧數(shù):";</p><p><b> for(;;)</b></p><p><b> {</b>&
21、lt;/p><p> gets_s(s);//以字符串形式接受所輸入的數(shù)據(jù)</p><p> t=atoi(s);//取出字符串中的整型</p><p> n=G.vexnum*(G.vexnum-1)/2;//計(jì)算整型合理范圍</p><p> if(G.kind==1)</p><p> n+=n;//修正整
22、型合理范圍</p><p> if(t>n||t<1)//如果整型不在合理范圍內(nèi)</p><p> cout<<"錯誤!請輸入一個(gè)大于0小于"<<n+1<<"的數(shù):";//程序報(bào)錯并返回循環(huán)重新輸入</p><p> else//如果整型在范圍內(nèi)</p>&l
23、t;p> break;//跳出循環(huán)繼續(xù)</p><p><b> }</b></p><p> G.arcnum=t;//賦值</p><p> 3.3生成鄰接表設(shè)計(jì)</p><p> cout<<"\n請分別輸入圖的"<<G.arcnum<<&qu
24、ot;條弧(弧尾,弧頭):"<<endl;</p><p> for(int i=0;i<G.arcnum;i++)</p><p><b> {</b></p><p> int n1,n2;</p><p><b> for(;;)</b></p>
25、<p><b> {</b></p><p> cout<<"弧"<<i+1<<":\t";</p><p> gets_s(s);//以字符串形式接受所輸入的數(shù)據(jù)</p><p> t=atoi(s); //取出字符串中的整型</p>
26、<p> strcpy_s(c,s+2);//去掉字符串中的前兩個(gè)字符</p><p> n=atoi(c); //取出字符串中的整型</p><p> if(t>G.vexnum||t<1||n>G.vexnum||n<1||t==n) //如果整型不在合理范圍內(nèi)</p><p> cout<<"
27、錯誤!請分別輸入兩個(gè)大于0小于"<<G.vexnum+1<<"的數(shù):\n\n";//程序報(bào)錯并返回循環(huán)重新輸入</p><p> else//如果整型在范圍內(nèi)</p><p> break; //跳出循環(huán)繼續(xù)</p><p><b> }</b></p><p>
28、; n1=t-1;n2=n-1;//修正賦值</p><p> if(!visited[n1])//如果n1后沒有結(jié)點(diǎn)</p><p><b> {</b></p><p> visited[n1]=true; //設(shè)置n1后已有結(jié)點(diǎn)</p><p> G.Vertices[n1].firstarc = new
29、 ArcNode;//在n1后增加新結(jié)點(diǎn)</p><p> G.Vertices[n1].firstarc->adjvex = n2;//結(jié)點(diǎn)賦值為n2</p><p> G.Vertices[n1].firstarc->nextarc= NULL;//設(shè)置n2之后的結(jié)點(diǎn)為空</p><p><b> }</b></p&
30、gt;<p> else//如果n1后已有結(jié)點(diǎn)</p><p><b> {</b></p><p> ArcNode *p = G.Vertices[n1].firstarc;//新建結(jié)點(diǎn)指針</p><p> while((p->nextarc)!=NULL)</p><p> p =
31、p->nextarc;//將指針指向鏈表中最后一個(gè)結(jié)點(diǎn)</p><p> p->nextarc = new ArcNode;//在最后增加一個(gè)新結(jié)點(diǎn)</p><p> p->nextarc->adjvex = n2;//給結(jié)點(diǎn)賦值n2</p><p> p->nextarc->nextarc=NULL; //設(shè)置n2之后的結(jié)
32、點(diǎn)為空</p><p><b> }</b></p><p><b> }</b></p><p> 3.4鄰接表遍歷設(shè)計(jì)</p><p> cout<<"\n\n請輸入遍歷的起點(diǎn):";</p><p><b> for(;
33、;)</b></p><p><b> {</b></p><p> gets_s(s); //以字符串形式接受所輸入的數(shù)據(jù)</p><p> t=atoi(s); //取出字符串中的整數(shù)</p><p> if(t>G.vexnum||t<1) //如果整型不在合理范圍內(nèi)</p&g
34、t;<p> cout<<"錯誤!請輸入一個(gè)大于0小于"<<G.vexnum+1<<"的數(shù):"; //程序報(bào)錯并返回循環(huán)重新輸入</p><p> else//如果整型在范圍內(nèi)</p><p> break; //跳出循環(huán)繼續(xù)</p><p><b> }&l
35、t;/b></p><p><b> t-=1;//賦值</b></p><p> cout<<"\n廣度遍歷順序:\n";</p><p> queue<int> Q;//定義輔助隊(duì)列Q</p><p> for(int j=0;j<G.vexnum;++
36、j)</p><p> visited[j]=false;//訪問標(biāo)志置0</p><p> BFSTraverse(G,Q,visited,t,G.vexnum,print);//從輸入的遍歷起點(diǎn)到最后一個(gè)鄰接表頭結(jié)點(diǎn)遍歷鄰接表</p><p> BFSTraverse(G,Q,visited,0,t,print);//從第一個(gè)鄰接表頭結(jié)點(diǎn)到輸入的鄰接表頭結(jié)
37、點(diǎn)遍歷鄰接表,防止還有連通分量尚未遍歷</p><p><b> 程序源代碼</b></p><p> //題目十一.圖的廣度遍歷</p><p> //問題描述:對任意給定的圖(頂點(diǎn)數(shù)和邊數(shù)自定),建立它的鄰接表并輸出,</p><p> //然后利用隊(duì)列的五種基本運(yùn)算(置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空
38、)實(shí)現(xiàn)圖的廣度優(yōu)先搜索遍歷。</p><p> #include <iostream></p><p> #include <queue></p><p> #define MAX_VERTEX_NUM 101</p><p> #define VertexType int</p><p&g
39、t; using namespace std;</p><p> typedef struct ArcNode//鄰接表表頂點(diǎn)</p><p><b> {</b></p><p> int adjvex;//該弧所指向的頂點(diǎn)位置</p><p> struct ArcNode *nextarc;//指向下一條
40、弧的指針</p><p> //InfoType *info;//該弧相關(guān)信息指針</p><p><b> }ArcNode;</b></p><p> typedef struct VNode//鄰接表頭頂點(diǎn)</p><p><b> {</b></p><p>
41、 VertexType data;//頂點(diǎn)信息</p><p> ArcNode *firstarc;//指向第一條依附該頂點(diǎn)的弧的指針</p><p> }VNode,AdjList[MAX_VERTEX_NUM];</p><p> typedef struct//圖</p><p><b> {</b>&
42、lt;/p><p> AdjList Vertices;//鄰接表頭頂點(diǎn)數(shù)組</p><p> int vexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)</p><p> int kind;//圖的種類標(biāo)志(有向圖:0,無向圖:1)</p><p><b> }ALGraph;</b></p>&l
43、t;p> void print(int v)//輸出頂點(diǎn)信息</p><p><b> {</b></p><p> cout<<v+1<<" ";</p><p><b> }</b></p><p> int FirstAdjVex(
44、ALGraph G,int u)//在鄰接表G中取第u個(gè)頭頂點(diǎn)</p><p><b> {</b></p><p> if(G.Vertices[u].firstarc==NULL)</p><p> return -1;</p><p> return G.Vertices[u].firstarc->a
45、djvex;</p><p><b> }</b></p><p> int NextAdjVex(ALGraph G,int u,int w)// 在鄰接表G中取第u個(gè)頭頂點(diǎn)之后的頂點(diǎn)w的下一頂點(diǎn)</p><p><b> {</b></p><p> ArcNode *p = G.Ver
46、tices[u].firstarc;</p><p> while(w != p->adjvex)</p><p> p = p->nextarc;</p><p> if(p->nextarc==NULL)return -1;</p><p> return p->nextarc->adjvex;<
47、;/p><p><b> }</b></p><p> void BFSTraverse(ALGraph G,queue<int> Q,bool visited[],int m,int n,void (*Visit)(int))//使用輔助隊(duì)列Q從鄰接表頂點(diǎn)m開始n結(jié)束廣度遍歷鄰接表圖G</p><p><b> {&l
48、t;/b></p><p> //按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組visited。</p><p> while(!Q.empty()) Q.pop();//置空的輔助隊(duì)列Q</p><p> for(int v=m;v<n;++v)</p><p> if(!visited[v])//v尚未訪問&l
49、t;/p><p><b> {</b></p><p> visited[v]=true;</p><p><b> Visit(v);</b></p><p> Q.push(v);//v入隊(duì)列</p><p> while(!Q.empty())</p>
50、<p><b> {</b></p><p> int u = Q.front(); </p><p> Q.pop();//對頭元素出隊(duì)并置為u</p><p> for( int w = FirstAdjVex(G,u); w >= 0; w = NextAdjVex(G,u,w))</p>&l
51、t;p> if(!visited[w])//w為u的尚未訪問的鄰接頂點(diǎn)</p><p><b> {</b></p><p> visited[w]=true;</p><p><b> Visit(w);</b></p><p> Q.push(w);</p><
52、;p><b> }//if</b></p><p><b> }//while</b></p><p><b> }//if</b></p><p> }//BFSTraverse*/</p><p> int main()</p><p&g
53、t;<b> {</b></p><p><b> int t,n;</b></p><p> char s[10],c[10];</p><p> ALGraph G;</p><p><b> do</b></p><p><b>
54、; {</b></p><p> system("cls");</p><p> cout<<"請輸入圖的類型(有向圖輸1,無向圖輸2):";</p><p><b> for(;;)</b></p><p><b> {</b&g
55、t;</p><p> gets_s(s);</p><p> t=atoi(s);</p><p> if(t!=1&&t!=2)</p><p> cout<<"錯誤!請輸入半角數(shù)字\"1\"或\"2\":";</p><p
56、><b> else</b></p><p><b> break;</b></p><p><b> }</b></p><p><b> G.kind=t;</b></p><p> cout<<"\n請輸入圖的頂
57、點(diǎn)數(shù):";</p><p><b> for(;;)</b></p><p><b> {</b></p><p> gets_s(s);</p><p> t=atoi(s);</p><p> if(t>99||t<1)</p>
58、<p> cout<<"錯誤!請輸入一個(gè)大于0小于100的數(shù):";</p><p><b> else</b></p><p><b> break;</b></p><p><b> }</b></p><p> G.v
59、exnum=t;</p><p> bool visited[MAX_VERTEX_NUM];</p><p> for(int i=0;i<G.vexnum;i++)</p><p><b> {</b></p><p> visited[i]=false;</p><p> G
60、.Vertices[i].firstarc=NULL;</p><p><b> }</b></p><p> if(G.kind==1)</p><p><b> {</b></p><p> cout<<"\n請輸入圖的弧數(shù):";</p>&
61、lt;p><b> for(;;)</b></p><p><b> {</b></p><p> gets_s(s);</p><p> t=atoi(s);</p><p> n=G.vexnum*(G.vexnum-1)/2;</p><p> if(
62、G.kind==1)</p><p><b> n+=n;</b></p><p> if(t>n||t<1)</p><p> cout<<"錯誤!請輸入一個(gè)大于0小于"<<n+1<<"的數(shù):";</p><p><b&
63、gt; else</b></p><p><b> break;</b></p><p><b> }</b></p><p> G.arcnum=t;</p><p> cout<<"\n請分別輸入圖的"<<G.arcnum<
64、<"條弧(弧尾,弧頭):"<<endl;</p><p> for(int i=0;i<G.arcnum;i++)</p><p><b> {</b></p><p> int n1,n2;</p><p><b> for(;;)</b><
65、;/p><p><b> {</b></p><p> cout<<"弧"<<i+1<<":\t";</p><p> gets_s(s);</p><p> strcpy_s(c,s);</p><p> t=at
66、oi(c);</p><p> strcpy_s(c,s+2);</p><p> n=atoi(c);</p><p> if(t>G.vexnum||t<1||n>G.vexnum||n<1||t==n)</p><p> cout<<"錯誤!請分別輸入兩個(gè)大于0小于"<
67、;<G.vexnum+1<<"的數(shù):\n\n";</p><p><b> else</b></p><p><b> break;</b></p><p><b> }</b></p><p> n1=t-1;n2=n-1;<
68、;/p><p> if(!visited[n1])</p><p><b> {</b></p><p> visited[n1]=true;</p><p> G.Vertices[n1].firstarc = new ArcNode;</p><p> G.Vertices[n1].fi
69、rstarc->adjvex = n2;</p><p> G.Vertices[n1].firstarc->nextarc= NULL;</p><p><b> }</b></p><p><b> else</b></p><p><b> {</b>
70、</p><p> ArcNode *p = G.Vertices[n1].firstarc;</p><p> while((p->nextarc)!=NULL)</p><p> p = p->nextarc;</p><p> p->nextarc = new ArcNode;</p><p
71、> p->nextarc->adjvex = n2;</p><p> p->nextarc->nextarc=NULL;</p><p><b> }</b></p><p><b> }</b></p><p><b> }</b>&
72、lt;/p><p><b> else</b></p><p><b> {</b></p><p> cout<<"\n請輸入圖的邊數(shù):";</p><p><b> for(;;)</b></p><p><
73、b> {</b></p><p> gets_s(s);</p><p> t=atoi(s);</p><p> n=G.vexnum*(G.vexnum-1)/2;</p><p> if(G.kind==1)</p><p><b> n+=n;</b><
74、/p><p> if(t>n||t<1)</p><p> cout<<"錯誤!請輸入一個(gè)大于0小于"<<n+1<<"的數(shù):";</p><p><b> else</b></p><p><b> break;<
75、/b></p><p><b> }</b></p><p> G.arcnum=t;</p><p> cout<<"\n請分別輸入圖的"<<G.arcnum<<"條邊(頂點(diǎn)1,頂點(diǎn)2):"<<endl;</p><p>
76、; for(int i=0;i<G.arcnum;i++)</p><p><b> {</b></p><p> int n1,n2;</p><p><b> for(;;)</b></p><p><b> {</b></p><p&g
77、t; cout<<"邊"<<i+1<<":\t";</p><p> gets_s(s);</p><p> strcpy_s(c,s);</p><p> t=atoi(c);</p><p> strcpy_s(c,s+2);</p>&l
78、t;p> n=atoi(c);</p><p> if(t>G.vexnum||t<1||n>G.vexnum||n<1||t==n)</p><p> cout<<"錯誤!請分別輸入兩個(gè)大于0小于"<<G.vexnum+1<<"的數(shù):\n\n";</p><
79、p><b> else</b></p><p><b> break;</b></p><p><b> }</b></p><p> n1=t-1;n2=n-1;</p><p> if(!visited[n1])</p><p>&l
80、t;b> {</b></p><p> visited[n1]=true;</p><p> G.Vertices[n1].firstarc = new ArcNode;</p><p> G.Vertices[n1].firstarc->adjvex = n2;</p><p> G.Vertices[n1
81、].firstarc->nextarc= NULL;</p><p><b> }</b></p><p><b> else</b></p><p><b> {</b></p><p> ArcNode *p = G.Vertices[n1].firstarc
82、;</p><p> while((p->nextarc)!=NULL)</p><p> p = p->nextarc;</p><p> p->nextarc = new ArcNode;</p><p> p->nextarc->adjvex = n2;</p><p>
83、p->nextarc->nextarc=NULL;</p><p><b> }</b></p><p> if(!visited[n2])</p><p><b> {</b></p><p> visited[n2]=true;</p><p> G
84、.Vertices[n2].firstarc = new ArcNode;</p><p> G.Vertices[n2].firstarc->adjvex = n1;</p><p> G.Vertices[n2].firstarc->nextarc= NULL;</p><p><b> }</b></p>
85、<p><b> else</b></p><p><b> {</b></p><p> ArcNode *p = G.Vertices[n2].firstarc;</p><p> while((p->nextarc)!=NULL)</p><p> p = p->
86、;nextarc;</p><p> p->nextarc = new ArcNode;</p><p> p->nextarc->adjvex = n1;</p><p> p->nextarc->nextarc=NULL;</p><p><b> }</b></p>
87、<p><b> }</b></p><p><b> }</b></p><p><b> do{</b></p><p> cout<<"\n鄰接表:\n";</p><p> for(int j=0;j<G.v
88、exnum;j++)</p><p><b> {</b></p><p> visited[j]=false;</p><p> cout<<j+1;</p><p> ArcNode *p = G.Vertices[j].firstarc;</p><p><b>
89、; while(p)</b></p><p><b> {</b></p><p> cout<<"-->"<<p->adjvex+1;</p><p> p = p->nextarc;</p><p><b> }</b
90、></p><p> cout<<endl;</p><p><b> }</b></p><p> cout<<"\n\n請輸入遍歷的起點(diǎn):";</p><p><b> for(;;)</b></p><p>&l
91、t;b> {</b></p><p> gets_s(s);</p><p> t=atoi(s);</p><p> if(t>G.vexnum||t<1)</p><p> cout<<"錯誤!請輸入一個(gè)大于0小于"<<G.vexnum+1<<
92、"的數(shù):";</p><p><b> else</b></p><p><b> break;</b></p><p><b> }</b></p><p><b> t-=1;</b></p><p>
93、; cout<<"\n廣度遍歷順序:\n";</p><p> queue<int> Q;</p><p> for(int j=0;j<G.vexnum;++j)</p><p> visited[j]=false;</p><p> BFSTraverse(G,Q,visited
94、,t,G.vexnum,print);</p><p> BFSTraverse(G,Q,visited,0,t,print);</p><p> cout<<"\n\n是否繼續(xù)從其他頂點(diǎn)遍歷此圖(Y/N):";</p><p><b> for(;;)</b></p><p>&l
95、t;b> {</b></p><p> gets_s(s);</p><p> if(s[0]!='y'&&s[0]!='Y'&&s[0]!='n'&&s[0]!='N')</p><p> cout<<"錯
96、誤!請輸入半角字母Y或N:";</p><p><b> else</b></p><p><b> break;</b></p><p><b> }</b></p><p> if(s[0]=='Y'||s[0]=='y')
97、system("cls");</p><p> }while(s[0]=='Y'||s[0]=='y');</p><p> cout<<"\n是否繼續(xù)輸入其他圖進(jìn)行遍歷(Y/N):";</p><p><b> for(;;)</b></p>
98、<p><b> {</b></p><p> gets_s(s);</p><p> if(s[0]!='y'&&s[0]!='Y'&&s[0]!='n'&&s[0]!='N')</p><p> cout&l
99、t;<"錯誤!請輸入半角字母Y或N:";</p><p><b> else</b></p><p><b> break;</b></p><p><b> }</b></p><p> }while(s[0]=='Y'||s
100、[0]=='y');</p><p> cout<<endl;</p><p> system("pause");</p><p><b> return 0;</b></p><p><b> }</b></p><p&g
101、t; 5.調(diào)試分析和測試結(jié)果</p><p> 編譯、運(yùn)行及調(diào)試環(huán)境: Microsoft Visual Studio 2010 Ultimate</p><p><b> 5.1調(diào)試分析</b></p><p> 一.在求圖的第u個(gè)頂點(diǎn),與其相鄰的一系列頂點(diǎn)中,第w個(gè)頂點(diǎn)的下一個(gè)頂點(diǎn)點(diǎn)時(shí),若是求最后一個(gè)頂點(diǎn)的下一個(gè)頂點(diǎn)時(shí),因?yàn)槭强罩羔?/p>
102、所以返回值為0,程序誤以為是第一個(gè)頂點(diǎn),再求下一個(gè)頂點(diǎn)時(shí)便報(bào)錯。原因是判斷條件沒有寫好,于是增加判斷,當(dāng)指針為空時(shí)返回-1。修改判斷條件后,函數(shù)正常運(yùn)行。</p><p> 二.在輸入圖信息的時(shí)候,若輸入非法字符,程序會異常終止。例如程序要求輸入一個(gè)整型,用戶卻輸入了一個(gè)字母,這時(shí)候會出現(xiàn)異常。只是程序是否健壯性的一個(gè)體現(xiàn)。</p><p> 先用字符串接收字符,轉(zhuǎn)換成整型后再判斷是否
103、符合要求。如果不符合便提示用戶按要求重新輸入。還有其他一些類似的輸入異常,都是采用類似的處理方法。</p><p> 作為一個(gè)完整的程序,友好的界面是必須的。因次程序中適當(dāng)?shù)夭捎孟到y(tǒng)中的清屏命令,使得界面更加簡潔,明了。</p><p><b> 5.2測試案例:</b></p><p> 圖 5-2-1 案例一
104、 圖 5-2-2 案例二</p><p> 5.3測試過程、結(jié)果截圖:</p><p> 5.3.1容錯性測試:</p><p> 在輸入字母、符號、或不符合要求的數(shù)字時(shí),提示錯誤并要求重新正確輸入。(圖5-3-1-1~圖5-3-1-7)</p><p><b> 圖 5-3-1-1</b>
105、;</p><p><b> 圖 5-3-1-2</b></p><p><b> 圖 5-3-1-3</b></p><p><b> 圖5-3-1-4</b></p><p><b> 圖 5-3-1-5</b></p><
106、p><b> 圖 5-3-1-6</b></p><p><b> 圖 5-3-1-7</b></p><p> 5.3.2無向圖(案例一)測試:</p><p> 將測試案例一的數(shù)據(jù)輸入程序,從第一個(gè)頂點(diǎn)開始遍歷,結(jié)果如圖 5-3-2-1所示。</p><p><b>
107、圖 5-3-2-1</b></p><p> 輸入y表示要繼續(xù)遍歷該圖后,程序清屏,再次打印鄰接表,并要求再次輸入遍歷起點(diǎn),如圖 5-3-2-2所示。</p><p><b> 圖 5-3-2-2</b></p><p> 輸入2后,打印從第二個(gè)頂點(diǎn)遍歷的順序,輸入n停止繼續(xù)遍歷該圖,如圖5-3-2-3所示。</p>
108、;<p><b> 圖 5-3-2-3</b></p><p> 5.3.3有向圖(案例二)測試:</p><p> 輸入y表示繼續(xù)輸入其他圖進(jìn)行遍歷后,程序清屏,并要求再次輸入一個(gè)圖,將測試案例2的數(shù)據(jù)輸入程序后,從第一個(gè)頂點(diǎn)遍歷,如圖 5-3-3-1所示。</p><p><b> 圖5-3-3-1</
109、b></p><p> 輸入y表示要繼續(xù)遍歷該圖后,程序清屏,再次打印鄰接表,并要求再次輸入遍歷起點(diǎn)。</p><p> 輸入4后,打印從第四個(gè)頂點(diǎn)遍歷的順序,輸入n停止繼續(xù)遍歷該圖。</p><p> 再次輸入n停止繼續(xù)輸入其他圖進(jìn)行遍歷,程序結(jié)束,如圖 5-3-3-2所示。</p><p><b> 圖 5-3-3
110、-2</b></p><p><b> 6.總結(jié)</b></p><p> 做此次課程設(shè)計(jì),需要對圖的廣度遍歷有足夠的熟悉與掌握,這樣才能熟練的運(yùn)用,所以這次課程設(shè)計(jì)也使我對所學(xué)的知識進(jìn)行了鞏固和新的理解,而且編程需要對C語言知識的扎實(shí)底子,這就需要復(fù)習(xí)C語言程序設(shè)計(jì)的知識。</p><p> 因此,通過這一個(gè)課程設(shè)計(jì),使我對
111、圖的廣度優(yōu)先遍歷算法有了深度的了解。在編程過程中也遇到了一些問題,在同學(xué)的幫助下基本上都一一解決了。但是由于能力有限,程序中還有一些尚未解決的問題。例如,如何能完全解決輸入異常。這說明今后還需要繼續(xù)努力。</p><p><b> 參 考 文 獻(xiàn)</b></p><p> [1] 譚浩強(qiáng)·C語言程序設(shè)計(jì)·(第2版)·清華大學(xué)出版社,出
112、版年:2009引用部分起止頁碼:50-51,248-258。</p><p> [2] 陳維興,林小茶·C++面向?qū)ο蟪绦蛟O(shè)計(jì)教程·(第3版)·清華大學(xué)出版社,出版年:2009引用部分起止頁碼:260-273。</p><p> [3] 嚴(yán)蔚敏,吳偉民·數(shù)據(jù)結(jié)構(gòu)·(C語言版)·清華大學(xué)出版社,出版年:2010引用部分起止頁碼:
溫馨提示
- 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)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 圖的廣度優(yōu)先遍歷-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 圖遍歷的演示課程設(shè)計(jì)報(bào)告
- 課程設(shè)計(jì)-圖的遍歷
- 圖的遍歷課程設(shè)計(jì)
- 圖的遍歷課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告(圖的遍歷)
- 圖的遍歷實(shí)現(xiàn)課程設(shè)計(jì)--圖的遍歷的實(shí)現(xiàn)
- 課程設(shè)計(jì)論文-圖的遍歷
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-----圖的遍歷
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---圖的遍歷
- 《圖的建立與遍歷》數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)庫課程設(shè)計(jì)---圖的存儲與遍歷
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-圖的遍歷和構(gòu)建
- (7.4.1)--ch7-04-圖的廣度優(yōu)先遍歷
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-- 圖的遍歷和生成樹求解
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---圖的遍歷和生成樹求解
- 遍歷二叉樹課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)-鄰接表存儲及遍歷-課程設(shè)計(jì)-實(shí)驗(yàn)報(bào)告
- 新數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---圖的遍歷和生成樹求解實(shí)現(xiàn)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--二叉樹的遍歷
評論
0/150
提交評論