數(shù)據(jù)結構實驗報告-無向圖的鄰接矩陣存儲結構

數(shù)學與計算機學院課程設計說明書課程名稱:數(shù)據(jù)結構與算法課程設計課程代碼:6014389題目:無向圖的鄰接矩陣存儲結構年級/專業(yè)/班:2010級軟件4班學生姓名:吳超學號:開始時間:2011年12月9日完成時間:2011年12月30日課程設計成績：學習態(tài)度及平時成績〔30〕技術水平與實際能力〔20〕創(chuàng)新〔5〕說明書〔計算書、圖紙、分析報告〕撰寫質量〔45〕總分〔100〕指導教師簽名：年月日數(shù)據(jù)結構課程設計任務書學院名稱：數(shù)學與計算機學院課程代碼：__6014389______專業(yè)：軟件工程年級：2010一、設計題目無向圖的鄰接矩陣存儲結構主要內容圖是無向帶權圖，對以下各題，要求寫一算法實現(xiàn)。能從鍵盤上輸入各條邊和邊上的權值；構造圖的鄰接矩陣和頂點集。輸出圖的各頂點和鄰接矩陣插入一條邊刪除一條邊求出各頂點的度判斷該圖是否是連通圖，假設是，返回1；否那么返回0.8〕使用深度遍歷算法，輸出遍歷序列。三、具體要求及應提交的材料用C/C++語言編程實現(xiàn)上述內容，對每個問題寫出一個算法實現(xiàn)，并按數(shù)學與計算機學院對課程設計說明書標準化要求，寫出課程設計說明書，并提交以下材料：1)課程設計說明書打印稿一份2)課程設計說明書電子稿一份；3)源程序電子文檔一份。四、主要技術路線提示用一維數(shù)組存放圖的頂點信息，二維數(shù)組存放各邊信息。五、進度安排按教學方案規(guī)定，數(shù)據(jù)結構課程設計為2周，其進度及時間大致分配如下：序號設計內容天數(shù)1分析問題，給出數(shù)學模型，選擇數(shù)據(jù)結構22設計算法，給出算法描述13給出源程序清單24編輯、編譯、調試源程序25編寫課程設計報告3總計10六、推薦參考資料[1]嚴蔚敏，吳偉民.數(shù)據(jù)結構.清華大學出版社出版。[2]嚴蔚敏，吳偉民.數(shù)據(jù)結構題集(C語言版).清華大學出版社.2003年5月。[3]唐策善，李龍澎.數(shù)據(jù)結構(作C語言描述)[4]朱戰(zhàn)立.數(shù)據(jù)結構(C++語言描述)〔第二版本〕.高等出版社出版.2004年4月[5]胡學鋼.數(shù)據(jù)結構(C語言版).高等教育出版社.2004年8月指導教師簽名日期年月日系主任審核日期年月日目錄TOC\o"1-2"\h\z\u引言 51需求分析 6任務與分析 6測試數(shù)據(jù) 62概要設計 72.1ADT描述 7程序模塊結構 8各功能模塊 103詳細設計 11類的定義 113.2初始化 123.3圖的構建操作 123.4輸出操作 133.5get操作 133.6插入操作 143.7刪除操作 143.8求頂點的度操作 153.10判斷連通操作 163.11主函數(shù) 174調試分析 204.1測試數(shù)據(jù) 20調試問題 204.3算法時間復雜度 204.4經(jīng)驗和心得體會 215用戶使用說明 216 測試結果 216.1創(chuàng)立圖 21插入節(jié)點 226.3深度優(yōu)先遍歷 226.4求各頂點的度 236.5輸出圖 236.6判斷是否連通 246.7求邊的權值 246.8插入邊 256.9刪除邊 25結論 27致謝 28摘要隨著計算機的普及，涉及計算機相關的科目也越來越普遍，其中數(shù)據(jù)結構是計算機專業(yè)重要的專業(yè)根底課程與核心課程之一，為適應我國計算機科學技術的開展和應用，學好數(shù)據(jù)結構非常必要，然而要掌握數(shù)據(jù)結構的知識非常難，所以對“數(shù)據(jù)結構”的課程設計比不可少。本說明書是對“無向圖的鄰接矩陣存儲結構”課程設計的說明。首先是對需求分析的簡要闡述，說明系統(tǒng)要完成的任務和相應的分析，并給出測試數(shù)據(jù)。其次是概要設計，說明所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次關系，以及ADT描述。然后是詳細設計，描述實現(xiàn)概要設計中定義的根本功操作和所有數(shù)據(jù)類型，以及函數(shù)的功能及代碼實現(xiàn)。再次是對系統(tǒng)的調試分析說明，以及遇到的問題和解決問題的方法。然后是用戶使用說明書的闡述，然后是測試的數(shù)據(jù)和結果的分析，最后是對本次課程設計的結論。關鍵詞：網(wǎng)絡化；計算機；對策；圖；儲存。引言數(shù)據(jù)結構是計算機存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結構是指相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結構可以帶來更高的運行或者存儲效率。數(shù)據(jù)結構往往同高效的檢索算法和索引技術有關。選擇了數(shù)據(jù)結構，算法也隨之確定，是數(shù)據(jù)而不是算法是系統(tǒng)構造的關鍵因素。這種洞見導致了許多種軟件設計方法和程序設計語言的出現(xiàn)，面向對象的程序設計語言就是其中之一。此次課程設計根據(jù)課堂講授內容，下發(fā)任務書，要求學生完成相應系統(tǒng)，以消化課堂所講解的內容；通過調試典型例題或習題積累調試C++程序從而獲得數(shù)據(jù)結構的編程經(jīng)驗；通過完成此項課程設計，逐漸培養(yǎng)學生的編程能力、用計算機解決實際問題的能力，并充分理解圖的矩陣儲存方法。此次課程設計題目為《無向圖的鄰接矩陣存儲結構》，所利用工具為Microsoftvisualstudio2008.1需求分析隨著計算機的普及,信息的存儲逐漸和我們的日常生活變得密切起來，而數(shù)據(jù)的存儲方式也多種多樣，比方樹、鏈表、數(shù)組、圖等等。為了充分表達圖的矩陣儲存結構的優(yōu)勢與功能，要求本系統(tǒng)應到達以下要求：圖是無向帶權圖能從鍵盤上輸入各條邊和邊上的權值；構造圖的鄰接矩陣和頂點集。輸出圖的各頂點和鄰接矩陣插入一條邊刪除一條邊求出各頂點的度判斷該圖是否是連通圖，假設是，返回1；否那么返回0.使用深度遍歷算法，輸出遍歷序列。鄰接矩陣是表示圖形中頂點之間相鄰關系的矩陣。設G=(V,E)是具有n個頂點的圖，那么G的鄰接矩陣是n階方陣。為了實現(xiàn)此算法，用一維數(shù)組a[]存放圖的頂點信息，二維數(shù)組b[][]存放各邊信息。頂點或者邊存在，那么該數(shù)組應有值，通過此來進行建立、插入、刪除。其余方法也將能通過數(shù)組的特性來實現(xiàn)。1.2測試數(shù)據(jù)建立圖的矩陣存儲結構，第一次建立連通圖A1，第二次建立非連通圖A2。如下：圖1.1測試數(shù)據(jù)選擇輸出圖選擇插入節(jié)點，插入4選擇插入邊，在3,4節(jié)點中插入邊，權值為55選擇深度優(yōu)先搜索選擇判斷是否連通選擇求最小生成樹選擇求各頂點的度選擇退出，重新運行，此次建立A2的圖，再次進行測試。2概要設計2.1ADT描述ADTGlist{{VR}={圖的頂點和邊}VR={<v,w>|v,w∈V,<v,w>表示頂點v和w間的邊；}根本操作：初始化空圖；輸入建立圖；深度優(yōu)先遍歷圖；確定圖中的頂點數(shù)目；確定圖中邊的數(shù)目；在圖中插入一個頂點；在圖中插入一條邊；刪除圖中一個頂點刪除圖中的一條邊；求頂點的度；求最小生成樹；}ADTGraph;2.2程序模塊結構圖2.1：模塊結構2.2.1結構體定義本系統(tǒng)未采用結構體方法，類的定義如下：定義頂點:nodecount，edgecount邊：已經(jīng)分別存放頂點和邊的兩個數(shù)組：a[MaxNode]和b[MaxNode][MaxNode];其余成員函數(shù)均以public形式聲明。在鄰接矩陣表示的圖中，頂點信息用一維數(shù)組表示a[]。在簡單情況下可省略，僅以下標值代表頂點序號。假設需要，頂點信息更加豐富。邊〔或弧〕信息用二維數(shù)組表示b[][]，這也是鄰接矩陣。包含邊的權值。在類中數(shù)據(jù)成員有4個，重要的是鄰接矩陣Edge[][]、總邊數(shù)edgecount和頂點數(shù)nodecount。classGraph1{private:intnodecount;//節(jié)點intedgecount;//邊inta[MaxNode];//頂點信息組//set<int>a;intb[MaxNode][MaxNode];//權值信息組public:Graph1(int);//構造函數(shù)intgetNodeCount();//當前的節(jié)點數(shù)intgetEdgeCount();//當前的邊數(shù)voidinsertNode(int);//插入一個節(jié)點voidisertEdge(int,int,int);//插入一條邊voiddeleteEdge(int,int);//刪除一條邊boolisliantong();//判斷是否連通intgetWeight(int,int);//獲得某條邊的權值intDepth(int);//深度遍歷準備，用于建立頂點訪問數(shù)組和記錄所訪問頂點個數(shù) voidDepth(intv,intvisited[],int&n);//深度遍歷 voidoutDu(Graph1G);//輸出節(jié)點個數(shù) voidPrintOut(Graph1G);//輸出圖 voidCreatG(intn,inte); //建立圖};2.3各功能模塊以下將以注釋形式為每個函數(shù)的功能進行聲明：構造函數(shù)：Graph1(int)用于初始化圖get函數(shù)：intgetNodeCount();得到當前的節(jié)點數(shù)get函數(shù)：intgetWeight(int,int);獲得某條邊的權值get函數(shù)：intgetEdgeCount();得到當前的邊數(shù)插入函數(shù)：voidinsertNode(int);插入一個節(jié)點插入函數(shù)：voidisertEdge(int,int,int);插入一條邊刪除函數(shù)：voiddeleteEdge(int,int);刪除一條邊判斷函數(shù)：boolisliantong();判斷是否連通遍歷函數(shù)1：intDepth(int);//深度遍歷準備，用于建立頂點訪問數(shù)組和記錄所訪問頂點個數(shù)遍歷函數(shù)2：voidDepth(intv,intvisited[],int&n);//深度遍歷求度函數(shù)：voidoutDu(Graph1G);輸出節(jié)點個數(shù)輸出函數(shù)：voidPrintOut(Graph1G);輸出圖構建函數(shù)：voidCreatG(intn,inte);建立圖3詳細設計類的定義classGraph1{private:intnodecount;//節(jié)點intedgecount;//邊inta[MaxNode];//頂點信息組//set<int>a;intb[MaxNode][MaxNode];//權值信息組public:Graph1(int);//構造函數(shù)intgetNodeCount();//當前的節(jié)點數(shù)intgetEdgeCount();//當前的邊數(shù)voidinsertNode(int);//插入一個節(jié)點voidisertEdge(int,int,int);//插入一條邊voiddeleteEdge(int,int);//刪除一條邊voidprim(int);//生成最小樹boolisliantong();//判斷是否連通intgetWeight(int,int);//獲得某條邊的權值intDepth(int);//深度遍歷準備，用于建立頂點訪問數(shù)組和記錄所訪問頂點個數(shù) voidDepth(intv,intvisited[],int&n);//深度遍歷 voidoutDu(Graph1G);//輸出節(jié)點個數(shù) voidPrintOut(Graph1G);//輸出圖 voidCreatG(intn,inte); //建立圖};初始化初始化鄰接矩陣以及有關參數(shù)，通過for循環(huán)將數(shù)組的值都初始化為0，使之成為一個空圖。Graph1::Graph1(ints=MaxNode)//構造函數(shù){for(inti=0;i<=s-1;i++)for(intj=0;j<=s-1;j++)b[i][j]=0;nodecount=0;for(intk=0;k<=s-1;k++)a[k]=-1;}3.3圖的構建操作在主函數(shù)中要求輸入需要構建的圖的頂點數(shù)和邊數(shù)，調用構建函數(shù)，分別用兩個for語句來構建圖〔即輸入頂點的值和邊的權值〕，此處要求輸入有一定的順序，不能隨意輸入。voidGraph1::CreatG(intn,inte){inti,vi,vj,w;edgecount=e;nodecount=n;cout<<endl<<"輸入頂點的信息〔暫設為整型〕：";for(i=0;i<nodecount;i++){cout<<"\n"<<i+1<<":";cin>>a[i];}for(i=0;i<edgecount;i++)//輸入兩個頂點編號和邊權值{cout<<endl<<"輸入邊的信息〔vi,vj,w〕："<<endl;;cin>>vi>>vj>>w;b[vi-1][vj-1]=w;b[vj-1][vi-1]=w;}}3.4輸出操作本函數(shù)通過傳過來的對象G得到相關數(shù)組，通過for循環(huán)來分別輸出頂點數(shù)組和邊的權值數(shù)組〔鄰接矩陣〕。voidGraph1::PrintOut(Graph1G){inti;cout<<"\n輸出頂點的信息："<<endl;for(i=0;i<G.getNodeCount();i++)cout<<G.a[i]<<"";cout<<endl<<"\n輸出鄰接矩陣：";for(i=0;i<G.getNodeCount();i++){cout<<endl<<i+1<<":";for(intj=0;j<G.getNodeCount();j++)cout<<G.b[i][j]<<"";cout<<endl;}}3.5get操作用于得到圖的頂點數(shù)、邊數(shù)、權值intGraph1::getNodeCount()//當前的節(jié)點數(shù){returnnodecount;}intGraph1::getEdgeCount()//當前的邊數(shù){returnedgecount;}intGraph1::getWeight(intx,inty)//獲得某條邊的權值{returnb[x-1][y-1];}3.6插入操作插入頂點：通過將傳來的值〔頂點值〕賦到一個當前頂點數(shù)下一個的數(shù)組元素中實現(xiàn)插入功能，此時頂點樹加1。插入邊：原理與插入頂點相同，通過傳過來的兩個頂點信息與權值進行相應賦值，不過此時應該注意表示同一條邊的兩個數(shù)組都該賦值。voidGraph1::insertNode(intit)//插入一個節(jié)點{a[nodecount++]=it;cout<<"當前節(jié)點數(shù)為："<<nodecount<<endl;}voidGraph1::isertEdge(intx,inty,intw)//插入一條邊{b[x-1][y-1]=w;b[y-1][x-1]=w;cout<<"該邊插入成功!"<<endl;edgecount++;}3.7刪除操作將相應的數(shù)組值賦為0從而到達刪除目的。voidGraph1::deleteEdge(intx,inty)//刪除一條邊{b[x-1][y-1]=0;b[y-1][x-1]=0;cout<<"邊("<<x<<","<<y<<")已經(jīng)成功刪除!";edgecount--;}3.8求頂點的度操作通過兩個for循環(huán)來查找各頂點，判斷其是否有邊〔權值〕，有邊的話又有幾條邊，每找到一條邊那么度數(shù)加一，記錄到存放頂點的度數(shù)的數(shù)組M[]中，搜索完成后輸出各頂點的度。voidGraph1::outDu(Graph1G)//輸出各點的度{intm[Max]={0},k,i;for(k=0;k<G.getNodeCount();k++)for(i=0;i<G.getNodeCount();i++){ if(G.b[k][i]!=0) m[k]++;}cout<<"各點的度："<<endl;for(i=0;i<G.getNodeCount();i++){cout<<"頂點"<<i<<"的度："<<m[i]<<endl;}}3.9深度遍歷操作圖的深度優(yōu)先遍歷DFS算法是沿著某初始頂點出發(fā)的一條路徑，盡可能深入地前進，即每次在訪問完當前頂點后，首先訪問當前頂點的一個未被訪問過的鄰接頂點，然后去訪問這個鄰接點的一個未被訪問過的鄰接點，這是一個遞歸算法。其中第一個遍歷函數(shù)Depth(intnode)其主要作用是構建訪問數(shù)組intv[]，以及調用核心遍歷函數(shù)Depth(intv,intvisited[],int&n)，其中的n是用來記錄訪問的頂點數(shù)目，用于判斷圖的連通性。intGraph1::Depth(intnode){intn=0; intv[MaxNode];for(inti=0;i<=nodecount-1;i++)v[i]=0;Depth(node,v,n);returnn;//n記錄訪問節(jié)點數(shù)，用于判斷是否連通}voidGraph1::Depth(intv,intvisited[],int&n){cout<<""<<v+1<<"";//訪問頂點vvisited[v]=1;//標記頂點v已訪問 n++;//n記錄訪問節(jié)點數(shù) for(intcol=0;col<nodecount;col++){if(b[v][col]==0||b[v][col]==Max)continue; //找v一個鄰接點colif(!visited[col])Depth(col,visited,n);//調用深度遞歸遍歷}}3.10判斷連通操作通過調用遍歷函數(shù)得到所能訪問的頂點數(shù)n，然后判斷n與當前頂點數(shù)是否相等來確認是否連通。boolGraph1::isliantong()//判斷是否連通{intn=0;n=Depth(0);cout<<"該圖的總節(jié)點數(shù)為:"<<nodecount<<"!"<<endl;cout<<"其中一個連通分量連通的節(jié)點數(shù)為:"<<n<<"!"<<endl;if(n==nodecount)//訪問到的節(jié)點數(shù)與頂點數(shù)是否相等return1;elsereturn0;}3.11主函數(shù)主函數(shù)的主要功能是引導構建新圖的鄰接矩陣存儲結構，并且制作菜單、調用各個相應的功能函數(shù)。intmain(){Graph1G(10);intx,y,w;intnode;cout<<"你好,請問你向圖添加幾個節(jié)點?幾條邊?請依次從鍵盤輸入!"<<endl;intn;cin>>n;inte;cin>>e;G.CreatG(n,e);cout<<"恭喜你!你的圖已經(jīng)建立成功!"<<endl;//system("pause");while(true){ //system("cls");cout<<"***********************"<<endl;cout<<"*請選擇你要進行的操作:*"<<endl;cout<<"*1--輸出圖!*"<<endl;cout<<"*2--判斷圖是否連通!*"<<endl;cout<<"*3--表示深度優(yōu)先搜索!*"<<endl;cout<<"*4--表示求各頂點的度!*"<<endl;cout<<"*5--表示插入新節(jié)點!*"<<endl;cout<<"*6--表示刪除邊!*"<<endl;cout<<"*7--求邊的權值*"<<endl;cout<<"*8--插入新的邊!*"<<endl;cout<<"*0--表示結束操作!*"<<endl;cout<<"***********************"<<endl;intchoice;cout<<endl;cout<<"請你做出選擇!"<<endl;cin>>choice;switch(choice){case1:G.PrintOut(G);break;case2:if(G.isliantong())cout<<"該圖是連通的!"<<endl;elsecout<<"該圖不是連通的!"<<endl;break;case3: intnode;cout<<"請輸入你選擇的起始節(jié)點!"<<endl; cin>>node;cout<<"深度優(yōu)先搜索結果為:"<<endl;G.Depth(node-1);cout<<endl;break;case4:G.outDu(G);break;case5:cout<<"請輸入你要插入的新節(jié)點!"<<endl;cin>>node;G.insertNode(node);cout<<endl;break;case6:cout<<"請輸入你要刪除的邊!"<<endl;cin>>x>>y;G.deleteEdge(x,y);cout<<endl;break;case7: cout<<"請輸入你要查詢的邊的兩個頂點"<<endl; cin>>x>>y; cout<<G.getWeight(x,y)<<endl; break;case8:cout<<"請輸入你要添加的"<<e<<"條邊以及邊上對應的權值!"<<endl;cin>>x>>y>>w;G.isertEdge(x,y,w);break;case0:cout<<"感謝使用！"<<endl;return0;}//system("pause");}4調試分析4.1測試數(shù)據(jù)測試數(shù)據(jù)詳見圖1具體功能方面，在遍歷函數(shù)中，由于訪問節(jié)點數(shù)組visit[]構建問題，無法到達遍歷目的，后新增另一遍歷功能函數(shù)，用于構建vi