社會(huì)網(wǎng)絡(luò)分析系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)1

1、上海電力學(xué)院數(shù)據(jù)結(jié)構(gòu)（c+）課程設(shè)計(jì)題目: 綜合實(shí)驗(yàn)16 社會(huì)網(wǎng)絡(luò)分析系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)(*)目 錄一、 設(shè)計(jì)題目1二、需求分析11）運(yùn)行環(huán)境（軟、硬件環(huán)境）12）輸入的形式和輸入值的范圍13）輸出的形式描述14）功能描述15）測試數(shù)據(jù)2三、概要設(shè)計(jì)21）抽象數(shù)據(jù)類型定義描述22）功能模塊設(shè)計(jì)（如主程序模塊設(shè)計(jì)）53）模塊層次調(diào)用關(guān)系圖5四、詳細(xì)設(shè)計(jì)6五、調(diào)試分析12 問題&改進(jìn)&補(bǔ)充12 算法的時(shí)間空間復(fù)雜性分析14 心得體會(huì)14六、測試結(jié)果15七 、附錄：程序設(shè)計(jì)源代碼161、 設(shè)計(jì)題目社會(huì)網(wǎng)絡(luò)分析系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)二、需求分析1）運(yùn)行環(huán)境（軟、硬件環(huán)境）軟件：microsoft visual

2、 c+ 6.0硬件：能運(yùn)行microsoft visual c+ 6.0的硬件平臺(tái)如cpu:intel 酷睿i3 3217u；內(nèi)存4g；操作系統(tǒng)windows 72）輸入的形式和輸入值的范圍數(shù)據(jù)類型： 整型（int）、字符型(char) 范圍：1. 總?cè)藬?shù)（1100）2. 人員名稱（az）3. 人員數(shù)字代碼（1100）4. 關(guān)系總數(shù)（1100）5. 某條關(guān)系（人員數(shù)字代碼 人員數(shù)字代碼 權(quán)值）注：權(quán)值（1100）即email數(shù)據(jù)舉例：總?cè)藬?shù)8個(gè)、人員名稱abcdefgh、人員數(shù)字代碼12345678、關(guān)系總數(shù)15條、具體某一條關(guān)系1 2 9。3）輸出的形式描述1. 該社會(huì)網(wǎng)絡(luò)的鄰接矩陣2. 該

3、社會(huì)網(wǎng)絡(luò)中的核心人物、活躍人物、邊緣人物3. 該社會(huì)網(wǎng)絡(luò)中的小團(tuán)體、橋接人物4. 查找任何人的交往圈子4）功能描述 1. 對(duì)email數(shù)據(jù)進(jìn)行預(yù)處理，利用數(shù)據(jù)結(jié)構(gòu)課程中圖中的理論，建立社會(huì)網(wǎng)絡(luò)的鄰接矩陣。2. 利用度的概念，找出社會(huì)網(wǎng)絡(luò)中核心人物、活躍人物和邊緣人物。3. 利用子圖概念，分析社會(huì)網(wǎng)絡(luò)的結(jié)構(gòu)，找出小團(tuán)體和聯(lián)系小團(tuán)體的橋接人物。4. 能查找任何人的交往圈子。5）測試數(shù)據(jù)三、概要設(shè)計(jì)1）抽象數(shù)據(jù)類型定義描述（對(duì)各類的成員及成員函數(shù)進(jìn)行抽象描述，參見書或ppt及實(shí)驗(yàn)）adtmgraphisdata存放圖中社會(huì)網(wǎng)絡(luò)人物的一維數(shù)組vertexmaxsize存放圖中社會(huì)網(wǎng)絡(luò)人物的關(guān)系的二維數(shù)

4、組arcmaxsizemaxsize圖中人物總數(shù)vertexnum和關(guān)系總數(shù),arcnum標(biāo)志數(shù)組visitedoperationu mgraph （構(gòu)造函數(shù)）初始化值：社會(huì)網(wǎng)絡(luò)中 a人員名稱，n總?cè)藬?shù)，e總關(guān)系數(shù)；標(biāo)志頂點(diǎn)訪問的數(shù)組visitedi置0。 動(dòng)作：將鍵盤輸入的值帶入，調(diào)用有向網(wǎng)的創(chuàng)建函數(shù)createhw。u createhw（創(chuàng)建有向網(wǎng)）輸入：圖的人數(shù)和關(guān)系數(shù)、存放圖中人的數(shù)組、存放圖中關(guān)系的數(shù)組前置條件：構(gòu)造函數(shù)調(diào)用功能：創(chuàng)建有向網(wǎng)輸出：無后置條件：有向網(wǎng)建立u printgraph（輸出鄰接矩陣）輸入：無前置條件：有向網(wǎng)已經(jīng)建立功能：輸出鄰接矩陣輸出：鄰接矩陣后置條件：無u

5、 centre（核心人物）輸入：無前置條件：有向網(wǎng)已經(jīng)建立，設(shè)定核心人物的域值yu=20功能：找出社會(huì)網(wǎng)絡(luò)的核心人物（計(jì)算每個(gè)頂點(diǎn)的入度，找度數(shù)大于域值的人物）輸出：若找到則輸出社會(huì)網(wǎng)絡(luò)的核心人物，沒有找到則輸出“無”。后置條件：無u huoyue（活躍人物）輸入：無前置條件：有向網(wǎng)已經(jīng)建立，設(shè)定活躍人物的域值yu=10功能：找出社會(huì)網(wǎng)絡(luò)的活躍人物（計(jì)算每個(gè)頂點(diǎn)的出度，找度數(shù)大于域值的人物）輸出：若找到則輸出社會(huì)網(wǎng)絡(luò)的活躍人物，沒有找到則輸出“無”。后置條件：無u bianyuan（邊緣人物）輸入：無前置條件：有向網(wǎng)已經(jīng)建立，設(shè)定邊緣人物的域值yu=5功能：找出社會(huì)網(wǎng)絡(luò)的邊緣人物（計(jì)算每個(gè)頂點(diǎn)

6、的出入度之和，找度數(shù)小于域值的人物）輸出：若找到則輸出社會(huì)網(wǎng)絡(luò)的邊緣人物，沒有找到則輸出“無”。后置條件：無u quanzi（交往圈子）輸入：輸入一個(gè)人員的數(shù)字代碼（用于查找該人員的交往圈子）前置條件：有向網(wǎng)已經(jīng)建立功能：查找交往圈子（與指定人物之間有邊的人物就是與該人物有聯(lián)系的，這些人就構(gòu)成了一個(gè)交往圈子）。輸出：輸出指定人物的交往圈子后置條件：無u add（計(jì)算人員兩兩間的關(guān)系數(shù)）輸入：無前置條件：有向網(wǎng)已經(jīng)建立，給出兩個(gè)人物的數(shù)字代碼功能：計(jì)算指定人員兩兩間的聯(lián)系數(shù)并返回（為查找小團(tuán)體、橋接人做準(zhǔn)備）輸出：返回指定人員兩兩間的聯(lián)系數(shù)后置條件：無u by（返回邊緣人物數(shù)字代碼）輸入：無前置

7、條件：有向網(wǎng)已經(jīng)建立功能：找邊緣人物并返回該人物數(shù)字代碼（為查找小團(tuán)體、橋接人做準(zhǔn)備）輸出：返回邊緣人物的數(shù)字代碼后置條件：無u dfs（小團(tuán)體）輸入：無前置條件：有向網(wǎng)、add函數(shù)、by函數(shù)都已經(jīng)建立，初始化頂點(diǎn)標(biāo)記矩陣（全部置0）功能：查找小團(tuán)體，從指定的頂點(diǎn)開始進(jìn)行深度優(yōu)先遍歷（如果當(dāng)前人物沒有被訪問過，并且也不是邊緣人物，輸出該人物；再從該人物開始進(jìn)行深度遍歷，如果找到與該人物交往密切的人物則輸出，繼續(xù)找下一個(gè)）輸出：輸出小團(tuán)體后置條件：對(duì)訪問過的頂點(diǎn)置1u dfs2（橋接人）輸入：無前置條件：有向網(wǎng)、add函數(shù)、by函數(shù)都已經(jīng)建立功能：查找橋接人，從指定的頂點(diǎn)開始進(jìn)行深度優(yōu)先遍歷輸出

8、：兩個(gè)小團(tuán)體中，有聯(lián)系，但沒有達(dá)到域值的人物后置條件：無end adt mgraph2）功能模塊設(shè)計(jì)（如主程序模塊設(shè)計(jì)）1. 主程序模塊：連接各種功能子模塊，完成程序的基本操作實(shí)現(xiàn)功能2. 構(gòu)造社會(huì)網(wǎng)絡(luò)模塊：按照要求構(gòu)建有向網(wǎng)3. 輸出鄰接矩陣模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)，輸出該網(wǎng)絡(luò)圖的鄰接矩陣4. 核心人物模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)，計(jì)算得出該社會(huì)網(wǎng)絡(luò)中的核心人物5. 活躍人物模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)，計(jì)算得出該社會(huì)網(wǎng)絡(luò)中的活躍人物6. 邊緣人物模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)，計(jì)算得出該社會(huì)網(wǎng)絡(luò)中的邊緣人物7. 交往圈子模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)，計(jì)算得出該網(wǎng)絡(luò)中指定人物的交往圈子8.

9、 人物兩兩聯(lián)系數(shù)模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)，返回指定人員兩兩間的聯(lián)系數(shù)9. 判斷邊緣人物模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)，返回邊緣人物的數(shù)字代碼10. 小團(tuán)體模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)，深度優(yōu)先遍歷得出該網(wǎng)絡(luò)中的所有小團(tuán)體11. 橋接人物模塊：根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)，深度優(yōu)先遍歷得出小團(tuán)體間的橋接人物3）模塊層次調(diào)用關(guān)系圖橋接人dfs2 小團(tuán)體dfs 交往圈子quanzi邊緣人物bianyuanmain( )mgraph活躍人物huoyue核心人物centre輸出鄰接矩陣printgraph構(gòu)建有向網(wǎng)createhw人員兩兩聯(lián)系數(shù)add判斷邊緣人物by 4、 詳細(xì)設(shè)計(jì)實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有的

10、類的定義及類中成員函數(shù)，并對(duì)主要的模塊寫出偽碼算法。#include#include#includeconst int maxsize=100;const int infinity=0;/最大值無窮定義一個(gè)mgraph類，用來實(shí)現(xiàn)基本功能：構(gòu)造函數(shù)初始化值，根據(jù)用戶輸入的社會(huì)網(wǎng)絡(luò)圖構(gòu)建有向網(wǎng)（鄰接矩陣存儲(chǔ)形式），查找該社會(huì)網(wǎng)絡(luò)中的核心人物、活躍人物、邊緣人物、小團(tuán)體、橋接人物，查找任何人的交往圈子。templateclass mgraphpublic: mgraph(t a,int n,int e);/構(gòu)造函數(shù)，a結(jié)點(diǎn)數(shù)組，n頂點(diǎn)個(gè)數(shù)，e邊數(shù) void printgraph();/輸出鄰接矩陣

11、 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) ;/計(jì)算人員兩兩間聯(lián)系數(shù) int by(int n) ; void dfs(int v,int n) ; /查找小團(tuán)體函數(shù)（深度優(yōu)先遍歷） void dfs2(int v,int n) ; /查找橋接人函數(shù)（深度優(yōu)先遍歷）private:t vertexmaxsize;/存放頂點(diǎn)int arcmaxsizemaxs

12、ize; /存放邊int vertexnum,arcnum;/頂點(diǎn)數(shù)，邊數(shù)void createhw(t a,int n,int e);/構(gòu)建有向網(wǎng)int *visited;mgraph 構(gòu)造函數(shù)初始化值：社會(huì)網(wǎng)絡(luò)中 a人員名稱，n總?cè)藬?shù)，e總關(guān)系數(shù)；標(biāo)志頂點(diǎn)訪問的數(shù)組visitedi置0；調(diào)用有向網(wǎng)的創(chuàng)建函數(shù)createhw。templatemgraph:mgraph(t a,int n,int e) visited=new intvertexnum; for(int i=0;ivertexnum;i+) visitedi=0; createhw(a,n,e); /創(chuàng)建/createhw 構(gòu)

13、建有向網(wǎng)將用戶輸入的值帶入，并完成存儲(chǔ)：人物名稱放入一維數(shù)組vertexi，人物間的email發(fā)送數(shù)（權(quán)值）放入二維數(shù)組arci-1j-1。template void mgraph:createhw(t a,int n,int e) int w; /權(quán)值 vertexnum=n; /頂點(diǎn)數(shù) arcnum=e; /邊數(shù) int i,j,k;cout注意！請(qǐng)將人名對(duì)應(yīng)到數(shù)字代碼輸入endl;cout輸入格式為：人員1 人員2 權(quán)值endl;for (i=0; ivertexnum; i+) vertexi=ai;/頂點(diǎn)數(shù)組賦初值（放入一維數(shù)組）for (i=0; ivertexnum; i+) /

14、初始化鄰接矩陣for (j=0; jvertexnum; j+)arcij=0; for (k=0; karcnum; k+) /依次輸入每一條邊，并修改鄰接矩陣的相應(yīng)元素cout請(qǐng)輸入第k+1ijw; /邊依附的兩個(gè)頂點(diǎn)的序號(hào)arci-1j-1=w; /置有邊標(biāo)志，存放權(quán)值/printgraph 輸 出通過二重循環(huán)輸出社會(huì)網(wǎng)絡(luò)對(duì)應(yīng)的鄰接矩陣存儲(chǔ)圖template void mgraph:printgraph()/輸出鄰接矩陣int i,j;for(i=0;ivertexnum;i+) for(j=0;jvertexnum;j+) coutarcijt;coutendl;/centre核心人物

15、若人物收到的email總數(shù)大于20封，我認(rèn)為就是核心人物，所以我設(shè)置了域?yàn)?0，centre函數(shù)要完成的功能是找入度大于域值的人物，并輸出。 templatevoid mgraph:centre(int n) vertexnum=n;int i,j,count=0;int xmaxsize=0;for(i=0;ivertexnum;i+)for(j=0;jvertexnum;j+)/計(jì)算每個(gè)頂點(diǎn)的入度xi+=arcji;/xj存放入度數(shù)cout核心人物是：; int yu=20; /找度數(shù)大于域值的人物, 域=20for(i=0;iyu)coutvertexi ; count+ ;if(cou

16、nt=0) cout無;coutendl;/huoyue活躍人物若人物發(fā)出的email總數(shù)大于10封，我認(rèn)為就是活躍人物，所以我設(shè)置了域?yàn)?0，huoyue函數(shù)要完成的功能是找出度大于域值的人物，并輸出。 templatevoid mgraph:huoyue(int n) vertexnum=n;int i,j,count=0;int ymaxsize=0;for(i=0;ivertexnum;i+)/計(jì)算每個(gè)頂點(diǎn)的出度for( j=0;jvertexnum;j+)yi+=arcij;/yi存放出度數(shù)cout活躍人物是：;int yu=10; /找度數(shù)大于域值的人物, 域=10for (i=0

17、; iyu) coutvertexi ; count+ ;if(count=0) cout無;coutendl;/bianyuan邊緣人物若人物收到和發(fā)出的email總數(shù)小于5封，我認(rèn)為就是邊緣人物，所以我設(shè)置了域?yàn)?，bianyuan函數(shù)要完成的功能是找入度與出度之和小于域值的人物，并輸出。 templatevoid mgraph:bianyuan(int n) vertexnum=n;int i,j,count=0;int zmaxsize=0;for(i=0;ivertexnum;i+)/計(jì)算每個(gè)頂點(diǎn)的度數(shù)for(j=0;jvertexnum;j+)zi=zi+arcij+arcji;

18、/zi存放入度+出度之和 cout邊緣人物是：;int yu=5; /找度數(shù)小于域值的人物, 域=5for (i=0; ivertexnum; i+) if(ziyu) coutvertexi ; count+ ;if(count=0) cout無;coutendl;/quanzi查找交往圈子根據(jù)用戶輸入的一個(gè)人員的數(shù)字代碼，查找該人員的交往圈子，我認(rèn)為與指定人物之間有邊的人物就是與該人物有聯(lián)系的，這些人就構(gòu)成了一個(gè)交往圈子。template void mgraph:quanzi(int v) int count=0;coutvertexv-1的交往圈子是:;for (int j=0; jve

19、rtexnum; j+) if (arcv-1j!=infinity|arcjv-1!=infinity) /交往圈子：與指定人物之間有邊就算 coutvertexj ; count+; if(count=0) cout無;coutendl;/add 計(jì)算人員間兩兩間聯(lián)系數(shù)計(jì)算指定人員兩兩間的聯(lián)系數(shù)并返回（為查找小團(tuán)體、橋接人做準(zhǔn)備）template int mgraph:add(int s,int t) int temp;if(st) temp=s; s=t; t=temp; else return (arcst+arcts);/by 查找小團(tuán)體中用來判斷邊緣人物找邊緣人物并返回該人物數(shù)字代

20、碼（為查找小團(tuán)體、橋接人做準(zhǔn)備）templateint mgraph:by(int n)int i,j,count=0;int zmaxsize=0;for(i=0;in;i+)/計(jì)算每個(gè)頂點(diǎn)的度數(shù)for(j=0;jn;j+)zi=zi+arcij+arcji; /zi存放入度+出度之和int yu=5; / 域=5for (i=0; in; i+) if(ziyu) return(i); count+ ;if(count=0) return(99);/dfs 查找小團(tuán)體查找小團(tuán)體，從指定的頂點(diǎn)（我設(shè)置的是0也就是第一個(gè)人）開始進(jìn)行深度優(yōu)先遍歷（如果當(dāng)前人物a沒有被訪問過，并且也不是邊緣人物，

21、輸出該人物a；再從該人物a開始進(jìn)行深度遍歷，如果找到與該人物交往密切的人物b則輸出，再從b開始繼續(xù)找下一個(gè)），并且在查找過程中輸出小團(tuán)體成員。template void mgraph:dfs(int v,int n) /v控制遞歸 n為總?cè)藬?shù) if (v=0)/如果是第一次使用for (int k=0;kn;k+)visitedk=0; /初始化頂點(diǎn)標(biāo)記矩陣（全部置0 代表沒有訪問過）dfs(v+1,n); /利用遞歸算法重復(fù)調(diào)用深度優(yōu)先遍歷dfselseif (visitedv-1=0)/如果當(dāng)前人物沒有被訪問過if(v-1!=by(n)/并且也不是邊緣人物 int yu=10; /域值co

22、utvertexv-1 ;/輸出該結(jié)點(diǎn)的值visitedv-1=1;/將該結(jié)點(diǎn)置為訪問過！for (int k=0;kyu)/如果兩個(gè)結(jié)點(diǎn)之間交往 密切dfs(k+1,n); /找下一個(gè)cout,;dfs(v+1,n);else dfs(v+1,n);/dfs2 查找橋接人查找橋接人，兩個(gè)小團(tuán)體中，有聯(lián)系，但沒有達(dá)到域值的人物。從指定的頂點(diǎn)開始進(jìn)行深度優(yōu)先遍歷template void mgraph:dfs2(int v,int n) /v控制遞歸 n為總?cè)藬?shù)int yu=10; /域值for (int k=v-1;k0 & add(v-1,k)yu & v-1!=by(n)& k!=by(n

23、)/如果兩個(gè)結(jié)點(diǎn)之間有邊但交往不密切，并且分別屬于兩個(gè)小團(tuán)體coutvertexv-1 vertexk ;/輸出橋接人結(jié)點(diǎn)的值dfs2(k+1,n); /找下一個(gè)if (v=n)dfs2(v+1,n); /主函數(shù)測試剛剛的mgraph類中的各種成員函數(shù)是否編寫正確，完成要求的功能。void main() cout| 歡迎使用社會(huì)網(wǎng)絡(luò)分析系統(tǒng) |endl;int n,e,m; /n總?cè)藬?shù)，e總關(guān)系數(shù)，m某個(gè)人員的數(shù)字代碼coutn; char *a=new charn; /a是指針，a的值是新建數(shù)組的首地址，a0,a1等 cout請(qǐng)依次輸入人員名稱：; for(int i=0;iai; cout

24、e;mgraph g(a,n,e);cout以下是該社會(huì)網(wǎng)絡(luò)對(duì)應(yīng)的鄰接矩陣：endl;g.printgraph();cout*社會(huì)網(wǎng)絡(luò)分析中*：endl;g.centre(n);g.huoyue(n);g.bianyuan(n);cout小團(tuán)體是：;g.dfs(0,n);coutendl; cout聯(lián)系小團(tuán)體的橋接人物是：; g.dfs2(1,n);coutendl; coutm;g.quanzi(m);五、調(diào)試分析 （包括調(diào)試過程中遇到的問題及解決的方法、算法的時(shí)間空間復(fù)雜性分析、經(jīng)驗(yàn)體會(huì)） 問題&改進(jìn)&補(bǔ)充：【問題1】：小團(tuán)體和橋接人的理解與定義小團(tuán)體：小團(tuán)體就是由交往比較密切的一群人構(gòu)成

25、的，因此要設(shè)一個(gè)域值，email數(shù)據(jù)（權(quán)值）超過這個(gè)域值才能算交往密切；一個(gè)人不能單獨(dú)構(gòu)成一個(gè)小團(tuán)體，小團(tuán)體至少要2個(gè)成員組成。橋接人：橋接人就是聯(lián)系兩個(gè)小團(tuán)體的中間人，也就是說一個(gè)小團(tuán)體可以通過對(duì)應(yīng)的橋接人和另外一個(gè)小團(tuán)體取得聯(lián)系，橋接人分屬于兩個(gè)不同的團(tuán)體?！締栴}2】：參數(shù)傳遞問題 目的是在一個(gè)成員函數(shù)里調(diào)用另一個(gè)成員函數(shù)中的數(shù)據(jù)，一開始想到的是將代碼段直接復(fù)制，但考慮到效率的問題，沒有使用；然后想到了利用全局變量，但又覺得不妥；后來問了老師，老師建議我使用參數(shù)傳遞的方法，將需要的數(shù)據(jù)帶回。于是做了如下修改：主函數(shù)中，增加char team2020; 并將g.dfs(0); 改成g.dfs

26、(0,n,team); 使dfs查找小團(tuán)體的函數(shù)中，可以使用主函數(shù)中的數(shù)據(jù)n總?cè)藬?shù)；使橋接人的函數(shù)中，可以使用dfs查找小團(tuán)體的函數(shù)中的二維數(shù)組：team2020【問題3】：遞歸調(diào)用中的數(shù)據(jù)存儲(chǔ)為了實(shí)現(xiàn)橋接人的查找，要將小團(tuán)體儲(chǔ)存到一個(gè)二維數(shù)組中，在遞歸調(diào)用中存入數(shù)組真的不是一件簡單的事，初始化數(shù)組的下標(biāo)就是一件很麻煩的事情，因?yàn)檫f歸調(diào)用每一次都會(huì)調(diào)用函數(shù)本身，若在函數(shù)體里面初始化數(shù)組下標(biāo)的話，每調(diào)用一次，就會(huì)歸零。解決方法：使用參數(shù)傳遞，將數(shù)組下標(biāo)作為兩個(gè)參數(shù)，每次調(diào)用時(shí)都將其傳回，這樣可以保證數(shù)組下標(biāo)有效完成計(jì)數(shù)的功能。主函數(shù)中，將g.dfs(0,n,team)； 改成g.dfs(0,n,

27、team,0,0)頭文件中，改成void dfs(int v,int n,char team2020,int i,int j)【改進(jìn)1】：createhw 構(gòu)建有向網(wǎng)中，原本老師ppt上演示的是：arcij=1; arcji=1; 之后改進(jìn)為 ：arci-1j-1=1; arcj-1i-1=1; 改進(jìn)原因：按照原來的寫法，輸入兩個(gè)人員之間的關(guān)系（頂點(diǎn)與頂點(diǎn)之間的邊）要從0開始，由于和日常生活的數(shù)數(shù)習(xí)慣不同，因此加以改進(jìn)，使之從1開始，方便使用?！靖倪M(jìn)2】：查找交往圈子中，原本應(yīng)該是：if (arcvj!=infinity|arcjv!=infinity) 需要改為：if (arcv-1j!=i

28、nfinity|arcjv-1!=infinity) 改進(jìn)原因：由于改進(jìn)1的影響，主函數(shù)中要求用戶輸入一個(gè)人員的數(shù)字代碼，查找該人員的交往圈子時(shí)，用戶也是從1開始數(shù)的，為了使程序顯示正確，需要將下標(biāo)v改成v-1?！靖倪M(jìn)3】：存放小團(tuán)體的數(shù)組其實(shí)不是必要的之前一直在糾結(jié)遞歸調(diào)用中存放數(shù)組的問題，但突然7號(hào)早上想到另一個(gè)更省事兒的方法，用排除法找橋接人！換個(gè)角度來看橋接人，就是分屬于兩個(gè)小團(tuán)體，之間有聯(lián)系但是聯(lián)系不密切，另外，橋接人也不能是邊緣人物。于是做了如下簡化改進(jìn)：主函數(shù)中，將g.dfs(0,n,team,0,0)； 改成g.dfs(0,n)；頭文件中，改成void dfs(int v,in

29、t n)【補(bǔ)充1】：補(bǔ)充沒有核心人物或者沒有活躍人物或者沒有邊緣人物的情況。一開始也沒有想的這么全面，經(jīng)過多次測試后發(fā)現(xiàn)這幾種情況也是存在的，原來的程序在這種情況下顯示的是空白，因此加以改進(jìn)了一下增加了count計(jì)數(shù)器，如果一個(gè)人物都沒有的話，就輸出“無”。 算法的時(shí)間空間復(fù)雜性分析1. 本設(shè)計(jì)中算法的時(shí)間復(fù)雜度分為三類：o(1)add 計(jì)算人員間兩兩間聯(lián)系數(shù)o(n)mgraph 構(gòu)造函數(shù)o(n2)createhw 構(gòu)建有向網(wǎng)、printgraph 輸出鄰接矩陣、centre核心人物 、huoyue活躍人物、bianyuan邊緣人物、quanzi查找交往圈子、by 判斷邊緣人物、dfs 查找小

30、團(tuán)體、dfs2 查找橋接人2. 本設(shè)計(jì)中算法的空間復(fù)雜度為：o(1) 心得體會(huì)：一開始選題的時(shí)候，就覺得這個(gè)題目很有趣，盡管它的難度系數(shù)比較高，但我還是義無反顧地選擇了它社會(huì)網(wǎng)絡(luò)分析系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)。圖這一章老師講的沒有單鏈表和二叉樹那樣細(xì)致，因?yàn)榭斓狡谀┝苏n時(shí)很緊張，但做相關(guān)實(shí)驗(yàn)的時(shí)候，我就對(duì)圖這部分的內(nèi)容產(chǎn)生了濃厚的興趣，因?yàn)樯缃痪W(wǎng)絡(luò)和我們的生活比較貼切，圖的應(yīng)用在類似人人、微信朋友圈的社交網(wǎng)絡(luò)中都會(huì)用到。自從我做完了上一個(gè)大作業(yè)，多余的兩天半時(shí)間我就開始著手做這個(gè)課程設(shè)計(jì)了，一開始選擇了使用無向圖，成功完成了除小團(tuán)體和橋接人之外的所有功能，但等到第一次課程設(shè)計(jì)上課的時(shí)候，和老師探討了小團(tuán)

31、體和橋接人的查找方法后，發(fā)現(xiàn)一開始就選錯(cuò)了圖的模型，應(yīng)該選擇有向網(wǎng)！之前的代碼也要全部推翻重來，頓時(shí)覺得壓力好大。好在回到寢室后的一整個(gè)下午加上一整個(gè)晚上的效率很高，終于將實(shí)現(xiàn)對(duì)email數(shù)據(jù)的預(yù)處理、建立社會(huì)網(wǎng)絡(luò)的鄰接矩陣、找出社會(huì)網(wǎng)絡(luò)中核心人物、活躍人物和邊緣人物的函數(shù)都完成了。但對(duì)于小團(tuán)體和橋接人的定義還是比較模糊的，于是第二次上課程設(shè)計(jì)的時(shí)候，詳細(xì)咨詢了老師。之后大量的時(shí)間都花在設(shè)計(jì)小團(tuán)體和橋接人上了。期間也碰到了很多問題，通過自己調(diào)試修改、上網(wǎng)查閱資料、課上課下咨詢老師，都得到了解決。通過這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，我對(duì)之前學(xué)習(xí)的c+內(nèi)容更加熟悉了，更好地掌握與理解了模板的使用、二維數(shù)組、

32、參數(shù)傳遞、函數(shù)調(diào)用等內(nèi)容；對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程也有了更進(jìn)一步的學(xué)習(xí)與掌握，處理問題的思路與方法也有所拓寬，能理解與運(yùn)用圖的相關(guān)知識(shí)解決實(shí)際問題在老師的指導(dǎo)下，不僅獨(dú)立完成了社會(huì)網(wǎng)絡(luò)分析系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)，還從老師那里學(xué)到了很多書上沒有的技巧，比如c+程序調(diào)試中所使用“斷點(diǎn)”調(diào)試方法，之前我是完全不知道的。通過這次課程設(shè)計(jì)，在這短短的5天中，我感覺收獲頗多！六、測試結(jié)果七 、附錄：程序設(shè)計(jì)源代碼#include#include#includeconst int maxsize=100;const int infinity=0;/最大值無窮templateclass mgraphpublic: mgr

33、aph(t a,int n,int e);/構(gòu)造函數(shù)，a結(jié)點(diǎn)數(shù)組，n頂點(diǎn)個(gè)數(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) ;/計(jì)算人員兩兩間聯(lián)系數(shù) int by(int n) ; void dfs(int v,int n) ; /查找小團(tuán)體函數(shù)（深度優(yōu)先遍歷） void dfs2(int v,int

34、n) ; /查找橋接人函數(shù)（深度優(yōu)先遍歷）private:t vertexmaxsize;/存放頂點(diǎn)int arcmaxsizemaxsize; /存放邊int vertexnum,arcnum;/頂點(diǎn)數(shù)，邊數(shù)void createhw(t a,int n,int e);/構(gòu)建無向圖int *visited;/mgraph 構(gòu)造函數(shù)templatemgraph:mgraph(t a,int n,int e) visited=new intvertexnum; for(int i=0;ivertexnum;i+) visitedi=0; createhw(a,n,e); /創(chuàng)建/createhw

35、 構(gòu)建有向網(wǎng)template void mgraph:createhw(t a,int n,int e) int w;/權(quán)值 vertexnum=n; /頂點(diǎn)數(shù) arcnum=e; /邊數(shù) int i,j,k;cout注意！請(qǐng)將人名對(duì)應(yīng)到數(shù)字代碼輸入endl;cout輸入格式為：人員1 人員2 權(quán)值endl;for (i=0; ivertexnum; i+) vertexi=ai;/頂點(diǎn)數(shù)組賦初值（放入一維數(shù)組）for (i=0; ivertexnum; i+) /初始化鄰接矩陣for (j=0; jvertexnum; j+)arcij=0; for (k=0; karcnum; k+) /

36、依次輸入每一條邊，并修改鄰接矩陣的相應(yīng)元素cout請(qǐng)輸入第k+1ijw; /ij邊依附的兩個(gè)頂點(diǎn)的序號(hào)，w權(quán)值arci-1j-1=w; /置有邊標(biāo)志，存放權(quán)值/printgraph 輸 出template void mgraph:printgraph()int i,j;for(i=0;ivertexnum;i+)for(j=0;jvertexnum;j+) coutarcijt;coutendl;/centre核心人物templatevoid mgraph:centre(int n)vertexnum=n;int i,j,count=0;int xmaxsize=0;for(i=0;ivert

37、exnum;i+)for(j=0;jvertexnum;j+)/計(jì)算每個(gè)頂點(diǎn)的入度xi+=arcji;/xj存放入度數(shù)cout核心人物是：; int yu=20; /找度數(shù)大于域值的人物, 域=20for(i=0;iyu)coutvertexi ; count+ ;if(count=0) cout無;coutendl;/huoyue活躍人物templatevoid mgraph:huoyue(int n)vertexnum=n;int i,j,count=0;int ymaxsize=0;for(i=0;ivertexnum;i+)/計(jì)算每個(gè)頂點(diǎn)的出度for( j=0;jvertexnum;j

38、+)yi+=arcij;/yi存放出度數(shù)cout活躍人物是：;int yu=10; /找度數(shù)大于域值的人物, 域=10for (i=0; iyu) coutvertexi ; count+ ;if(count=0) cout無;coutendl;/bianyuan邊緣人物templatevoid mgraph:bianyuan(int n)vertexnum=n;int i,j,count=0;int zmaxsize=0;for(i=0;ivertexnum;i+)/計(jì)算每個(gè)頂點(diǎn)的度數(shù)for(j=0;jvertexnum;j+)zi=zi+arcij+arcji; /zi存放入度+出度之和

39、cout邊緣人物是：;int yu=5; /找度數(shù)小于域值的人物, 域=5for (i=0; ivertexnum; i+) if(ziyu) coutvertexi ; count+ ;if(count=0) cout無;coutendl;/quanzi查找交往圈子template void mgraph:quanzi(int v) /深度優(yōu)先遍歷圖int count=0;coutvertexv-1的交往圈子是:;for (int j=0; jvertexnum; j+)if (arcv-1j!=infinity|arcjv-1!=infinity) /交往圈子：與指定人物之間有邊就算 coutvertexj ; count+; if(count=0) cout無;coutendl;/add 計(jì)算人員間兩兩間聯(lián)系數(shù)temp