【正文】 函數(shù)中的數(shù)據(jù)，一開始想到的是將代碼段直接復(fù)制，但考慮到效率的問題，沒有使用；然后想到了利用全局變量，但又覺得不妥；后 13 來問了老師，老師建議我使用參數(shù)傳遞的方法，將需要的數(shù)據(jù)帶回。于是做了如下修改： 主函數(shù)中，增加 char team[20][20]。 并將 (0)。 改成 (0,n,team)。 使 DFS查找小團體的函數(shù)中，可以使用主函數(shù)中的數(shù)據(jù) n總?cè)藬?shù)；使橋接人的函數(shù)中，可以使用 DFS 查找小團體的函數(shù)中的二維數(shù)組： team[20][20] 【問題 3】：遞歸調(diào) 用中的數(shù)據(jù)存儲 為了實現(xiàn)橋接人的查找，要將小團體儲存到一個二維數(shù)組中，在遞歸調(diào)用中存入數(shù)組真的不是一件簡單的事，初始化數(shù)組的下標就是一件很麻煩的事情，因為遞歸調(diào)用每一次都會調(diào)用函數(shù)本身，若在函數(shù)體里面初始化數(shù)組下標的話，每調(diào)用一次，就會歸零。 解決方法：使用參數(shù)傳遞，將數(shù)組下標作為兩個參數(shù)，每次調(diào)用時都將其傳回，這樣可以保證數(shù)組下標有效完成計數(shù)的功能。 主函數(shù)中，將 (0,n,team)； 改成 (0,n,team,0,0) 頭文件中，改成 void DFS(int v,int n,char team[20][20],int i,int j) 【改進 1】： createHW 構(gòu)建有向網(wǎng)中， 原本老師 PPT上演示的是： arc[i][j]=1。 arc[j][i]=1。 之后改進為 ： arc[i1][j1]=1。 arc[j1][i1]=1。 改進原因：按照原來的寫法，輸入兩個人員之間的關(guān)系（頂點與頂點之間的邊）要從 0 開始，由于和日常生活的數(shù)數(shù)習(xí)慣不同，因此加以改進，使之從 1開始，方便使用。 【改進 2】：查找交往圈子中， 原本應(yīng)該是： if (arc[v][j]!=INFINITY||arc[j][v]!=INFINITY) 需要改為： if (arc[v1][j]!=INFINITY||arc[j][v1]!=INFINITY) 改進原因：由于改進 1 的影響，主函數(shù)中要求用戶輸入一個人員的數(shù)字代碼，查找該人員的交往圈子時，用戶也是從 1 開始數(shù)的，為了使程序顯示正確，需要將下標 v 改成 v1。 【改進 3】：存放小團體的數(shù)組其實不是必要的 之前一直在糾結(jié)遞歸調(diào)用中存放數(shù)組的問題，但突然 7號早上想到另一個更省事兒的方法，用排除法找橋接人！換個角度來看橋接人，就是分屬于兩個小團體，之間有聯(lián) 系但是聯(lián)系不密切，另外，橋接人也不能是邊緣人物。于是做了如下簡化改進： 主函數(shù)中，將 (0,n,team,0,0)； 改成 (0,n)； 14 頭文件中，改成 void DFS(int v,int n) 【補充 1】：補充沒有核心人物或者沒有活躍人物或者沒有邊緣人物的情況。 一開始也沒有想的這么全面，經(jīng)過多次測試后發(fā)現(xiàn)這幾種情況也是存在的，原來的程序在這種情況下顯示的是空白，因此加以改進了一下 —— 增加了 count計數(shù)器，如果一個人物都沒有的話，就輸出“無”。 ? 算法的時間空間復(fù)雜性分析 1. 本設(shè)計 中算法的時間復(fù)雜度分為三類： O(1)—— ADD 計算人員間兩兩間聯(lián)系數(shù) O(n)—— Mgraph 構(gòu)造函數(shù) O(n2)—— CreateHW 構(gòu)建有向網(wǎng)、 PrintGraph 輸出鄰接矩陣、 centre核心人物 、 huoyue活躍人物、 bianyuan邊緣人物、 quanzi查找交往圈子、 BY 判斷邊緣人物、 DFS 查找小團體、 DFS2 查找橋接人 2. 本設(shè)計中算法的空間復(fù)雜度為： O(1) ? 心得體會： 一開始選題的時候，就覺得這個題目很有趣，盡管它的難度系數(shù)比較高，但我還是義無反顧地選擇了它 —— 社會網(wǎng)絡(luò)分 析系統(tǒng)的設(shè)計和實現(xiàn)。圖這一章老師講的沒有單鏈表和二叉樹那樣細致，因為快到期末了課時很緊張，但做相關(guān)實驗的時候，我就對圖這部分的內(nèi)容產(chǎn)生了濃厚的興趣，因為社交網(wǎng)絡(luò)和我們的生活比較貼切，圖的應(yīng)用在類似人人、微信朋友圈的社交網(wǎng)絡(luò)中都會用到。 自從我做完了上一個大作業(yè)，多余的兩天半時間我就開始著手做這個課程設(shè)計了，一開始選擇了使用無向圖，成功完成了除小團體和橋接人之外的所有功能，但等到第一次課程設(shè)計上課的時候，和老師探討了小團體和橋接人的查找方法后，發(fā)現(xiàn)一開始就選錯了圖的模型，應(yīng)該選擇有向網(wǎng)！之前的代碼也要全部推翻 重來，頓時覺得壓力好大。好在回到寢室后的一整個下午加上一整個晚上的效率很高，終于將實現(xiàn)對 數(shù)據(jù)的預(yù)處理、建立社會網(wǎng)絡(luò)的鄰接矩陣、找出社會網(wǎng)絡(luò)中核心人物、活躍人物和邊緣人物的函數(shù)都完成了。但對于小團體和橋接人的定義還是比較模糊的，于是第二次上課程設(shè)計的時候，詳細咨詢了老師。之后大量的時間都花在設(shè)計小團體和橋接人上了。 期間也碰到了很多問題，通過自己調(diào)試修改、上網(wǎng)查閱資料、課上課下咨詢老師，都 15 得到了解決。通過這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，我對之前學(xué)習(xí)的 C++內(nèi)容更加熟悉了，更好地掌握與理解了模板的使用、二維數(shù)組 、參數(shù)傳遞、函數(shù)調(diào)用等內(nèi)容；對數(shù)據(jù)結(jié)構(gòu)這門課程也有了更進一步的學(xué)習(xí)與掌握，處理問題的思路與方法也有所拓寬，能理解與運用圖的相關(guān)知識解決實際問題??在老師的指導(dǎo)下，不僅獨立完成了社會網(wǎng)絡(luò)分析系統(tǒng)的設(shè)計和實現(xiàn)，還從老師那里學(xué)到了很多書上沒有的技巧，比如 C++程序調(diào)試中所使用“斷點”調(diào)試方法，之前我是完全不知道的。通過這次課程設(shè)計，在這短短的 5天中，我感覺收獲頗多！ 六、測試結(jié)果 16 七 、附錄：程序設(shè)計源代碼 include include include const int maxsize=100。 const int INFINITY=0。//最大值無窮 templateclass T class Mgraph { public: Mgraph(T a[],int n,int e)。//構(gòu)造函數(shù)， a[]結(jié)點數(shù)組， n頂點個數(shù)， e邊數(shù) void PrintGraph()。//輸出鄰接矩陣 void centre(int n)。 //核心人物成員函數(shù) void huoyue(int n)。//活 躍人物成員函數(shù) void bianyuan(int n)。//邊緣人物成員函數(shù) void quanzi(int v)。 //查找交往圈子函數(shù) int ADD(int s,int t) 。//計算人員兩兩間聯(lián)系數(shù) int BY(int n) 。 void DFS(int v,int n) 。 //查找小團體函數(shù)（深度優(yōu)先遍歷） void DFS2(int v,int n) 。 //查找橋接人函數(shù)（深度優(yōu)先遍歷） private: T vertex[maxsize]。//存放頂點 int arc[maxsize][maxsize]。 //存放邊 int vertexnum,arum。//頂點數(shù)，邊數(shù) void CreateHW(T a[],int n,int e)。//構(gòu)建無向圖 int *visited。 }。 //———————— Mgraph 構(gòu)造函數(shù) ———————— templateclass T MgraphT::Mgraph(T a[],int n,int e) { visited=new int[vertexnum]。 for(int i=0。ivertexnum。i++) visited[i]=0。 CreateHW(a,n,e)。 //創(chuàng)建 } //———————— CreateHW 構(gòu)建有向網(wǎng) ———————— template class T void MgraphT::CreateHW(T a[],int n,int e) { int w。//權(quán)值 vertexnum=n。 //頂點數(shù) arum=e。 //邊數(shù) int i,j,k。 17 cout 注意！請將人名對應(yīng)到數(shù)字代碼輸入 endl。 cout 輸入格式為：人員 1 人員 2 權(quán)值 endl。 for (i=0。 ivertexnum。 i++) vertex[i]=a[i]。//頂點數(shù)組賦初值（放入一維數(shù)組） for (i=0。 ivertexnum。 i++) //初始化鄰接矩陣 for (j=0。 jvertexnum。 j++) arc[i][j]=0。 for (k=0。 karum。 k++) { //依次輸入每一條邊，并修改鄰接矩陣的相應(yīng)元素 cout請輸入第 k+1條邊 :。 cinijw。 //ij 邊依附的兩個頂點的序號， w權(quán)值 arc[i1][j1]=w。 //置有邊標志，存放權(quán)值 } } //——————— PrintGraph 輸 出 ————————— template class T void MgraphT::PrintGraph() { int i,j。 for(i=0。ivertexnum。i++) { for(j=0。jvertexnum。j++) cout