社会网络分析系统的设计和实现数据结构课程设计

1、上海电力学院数据结构（C+课程设计题 目：综合实验16社会网络分析系统的设计和实现（*） TOC o 1-5 h z HYPERLINK l bookmark0 o Current Document 一、设计题目1. HYPERLINK l bookmark2 o Current Document 二、需求分析1.1）运行环境（软、硬件环境） 12）输入的形式和输入值的范围 13）输出的形式描述 1.4）功能描述1.5）测试数据2. HYPERLINK l bookmark4 o Current Document 三、概要设计2.1）抽象数据类型定义描述2.2）功能模块设计（如主程序模块设计）

2、 53）模块层次调用关系图 5. HYPERLINK l bookmark36 o Current Document 四、详细设计6. HYPERLINK l bookmark58 o Current Document 五、调试分析12问题&改进&补充12算法的时间空间复杂性分析14心得体会.14六、测试结果15 HYPERLINK l bookmark68 o Current Document 七、附录：程序设计源代码 .16 、设计题目社会网络分析系统的设计和实现二、需求分析1）运行环境（软、硬件环境）软件：Microsoft Visual C+ 6.0硬件：能运行 Microsoft V

3、isual C+ 6.0 的硬件平台如 CPU:Intel 酷睿 i3 3217U ;内存 4G;操作系统 Windows 72）输入的形式和输入值的范围数据类型：整型（int ）、字符型（char）范围：总人数（1100）人员名称（AZ）人员数字代码（1100）关系总数（1100）某条关系（人员数字代码人员数字代码 权值）注：权值（1100）即email数据举例：总人数 8个、人员名称 ABCDEFGH、人员数字代码12345678、关系总数15条、具体某一条关系129。3）输出的形式描述该社会网络的邻接矩阵该社会网络中的核心人物、活跃人物、边缘人物该社会网络中的小团体、桥接人物查找任何人的

4、交往圈子4）功能描述对email数据进行预处理，利用数据结构课程中图中的理论，建立社会网络的邻接矩阵。利用度的概念，找出社会网络中核心人物、活跃人物和边缘人物。利用子图概念，分析社会网络的结构，找出小团体和联系小团体的桥接人物。能查找任何人的交往圈子。5）测试数据三、概要设计1）抽象数据类型定义描述（对各类的成员及成员函数进行抽象描述，参见书或ppt及实验）ADT Mgraph isData存放图中社会网络人物的一维数组vertexmaxsize存放图中社会网络人物的关系的二维数组arcmaxsizemaxsize图中人物总数 vertex num和关系总数,arcnum标志数组visited

5、Operati onMgraph （构造函数）初始化值：社会网络中 a人员名称，n总人数，e总关系数；标志顶点访问的数组visitedi 置 0。动作：将键盘输入的值带入，调用有向网的创建函数CreateHW。CreateHW （创建有向网）输入：图的人数和关系数、存放图中人的数组、存放图中关系的数组前置条件：构造函数调用功能：创建有向网输出：无后置条件：有向网建立Prin tGraph （输出邻接矩阵）输入：无前置条件：有向网已经建立功能：输出邻接矩阵输出：邻接矩阵后置条件：无Centre （核心人物）输入：无前置条件：有向网已经建立，设定核心人物的域值yu=20功能：找出社会网络的核心人物

6、（计算每个顶点的入度，找度数大于域值的人物）输出：若找到则输出社会网络的核心人物，没有找到则输出“无”。后置条件：无Huoyue （活跃人物）输入：无前置条件：有向网已经建立，设定活跃人物的域值yu=10功能：找出社会网络的活跃人物（计算每个顶点的出度，找度数大于域值的人物）输出：若找到则输出社会网络的活跃人物，没有找到则输出“无”。后置条件：无Bianyuan （边缘人物）输入：无前置条件：有向网已经建立，设定边缘人物的域值yu=5功能：找出社会网络的边缘人物 （计算每个顶点的出入度之和，找度数小于域值的人物）输出：若找到则输出社会网络的边缘人物，没有找到则输出“无”。后置条件：无quanz

7、i （交往圈子）输入：输入一个人员的数字代码（用于查找该人员的交往圈子）前置条件：有向网已经建立功能：查找交往圈子（与指定人物之间有边的人物就是与该人物有联系的，这些人就构成了一个交往圈子）。输出：输出指定人物的交往圈子后置条件：无ADD（计算人员两两间的关系数）输入：无前置条件：有向网已经建立，给出两个人物的数字代码功能：计算指定人员两两间的联系数并返回（为查找小团体、桥接人做准备）输出：返回指定人员两两间的联系数后置条件：无BY （返回边缘人物数字代码）输入：无前置条件：有向网已经建立功能：找边缘人物并返回该人物数字代码（为查找小团体、桥接人做准备）输出：返回边缘人物的数字代码后置条件：无

8、DFS（小团体）输入：无前置条件：有向网、 ADD函数、BY函数都已经建立，初始化顶点标记矩阵（全部置0）功能：查找小团体，从指定的顶点开始进行深度优先遍历（如果当前人物没有被访问过，并且也不是边缘人物， 输出该人物；再从该人物开始进行深度遍历，如果找到与该人物交往密切的人物则输出，继续找下一个）输出：输出小团体后置条件：对访问过的顶点置 1DFS2（桥接人）输入：无前置条件：有向网、 ADD函数、BY函数都已经建立功能：查找桥接人，从指定的顶点开始进行深度优先遍历输出：两个小团体中，有联系，但没有达到域值的人物后置条件：无end ADT Mgraph2）功能模块设计（如主程序模块设计）主程序

9、模块：连接各种功能子模块，完成程序的基本操作实现功能构造社会网络模块：按照要求构建有向网输出邻接矩阵模块：根据用户输入的社会网络，输出该网络图的邻接矩阵核心人物模块：根据用户输入的社会网络，计算得出该社会网络中的核心人物活跃人物模块：根据用户输入的社会网络，计算得出该社会网络中的活跃人物边缘人物模块：根据用户输入的社会网络，计算得出该社会网络中的边缘人物交往圈子模块：根据用户输入的社会网络，计算得出该网络中指定人物的交往圈子人物两两联系数模块：根据用户输入的社会网络，返回指定人员两两间的联系数判断边缘人物模块：根据用户输入的社会网络，返回边缘人物的数字代码小团体模块：根据用户输入的社会网络，深

10、度优先遍历得出该网络中的所有小团体桥接人物模块：根据用户输入的社会网络，深度优先遍历得出小团体间的桥接人物3）模块层次调用关系图Mai n()Mgraph构建有向网输出邻PrintG矩阵K核心centre 物 aph活跃huo人ue物I边缘人bia物ua3交往quar圈in子小DFI桥S.FD人口D两两联系数DA判断边缘人物YB四、详细设计实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算 法。#in clude#in clude#in cludeconst int maxsize=100;con st int INFINITY=O; 最大值无穷定义一个Mgraph类，

11、用来实现基本功能：构造函数初始化值，根据用户输入 的社会网络图构建有向网(邻接矩阵存储形式)，查找该社会网络中的核心人 物、活跃人物、边缘人物、小团体、桥接人物，查找任何人的交往圈子。templateclass Mgraphpublic:Mgraph(T a,int n,int e);构造函数，a结点数组，n顶点个数，e边数void PrintGraph();输出邻接矩阵void centre(int n); /核心人物成员函数void huoyue(int n);活跃人物成员函数void bianyuan(int n);边缘人物成员函数void qua nzi(i nt v);查找交往圈子函

12、数int ADD( int s,i nt t);/计算人员两两间联系数int BY(i nt n);void DFS(int v,int n) ; /查找小团体函数(深度优先遍历)void DFS2(int v,int n) ; /查找桥接人函数(深度优先遍历)private:T vertexmaxsize; 存放顶点int arcmaxsizemaxsize; / 存放边int vertexnum,arcnum;/ 顶点数，边数void CreateHW(T a,int n,int e);/ 构建有向网int *visited;Mgraph 构造函数初始化值：社会网络中a人员名称，n总人数，

13、e总关系数；标志顶点访问的数组visitedi置0;调用有向网的创建函数 CreateHW。templateMgraph:Mgraph(T a,i nt n,i nt e)visited=new in tvertex nu m;for(i nt i=0;ivertex nu m;i+)visitedi=O;CreateHW(a ,n, e); / 创建/CreateHW 构建有向网将用户输入的值带入，并完成存储：人物名称放入一维数组vertexi，人物间的Email发送数(权值)放入二维数组arci-1j-1。template void Mgraph:CreateHW(T a,i nt n,i

14、 nt e) int w;/ 权值vertex num=n;/ 顶点数arcnum=e;边数int i,j,k;cout 注意！请将人名对应到数字代码输入e ndl;cout 输入格式为：人员 1人员2权值endl;for (i=0; ivertex num; i+)vertexi=ai;/顶点数组赋初值(放入一维数组)for (i=0; ivertex num; i+)/ 初始化邻接矩阵for (j=0; jvertex nu m; j+)arcij=0;for (k=0; karc num; k+) /依次输入每一条边，并修改邻接矩阵的相应元素cout请输入第k+1ijw; /边依附的两个

15、顶点的序号 arci-1j-1=w;/置有边标志，存放权值/PrintGraph输 出通过二重循环输出社会网络对应的邻接矩阵存储图template void Mgraph:Pri ntGraph()/输出邻接矩阵int i,j;for(i=0;ivertex nu m;i+)for(j=0;jvertex nu m;j+)coutarcijt;coute ndl;/centre核心人物若人物收到的Email总数大于20 封,我认为就是核心人物，所以我设置了域为 20，centre函数要完成的功能是找入度大于域值的人物，并输出。templatevoid Mgraph:ce ntre(i nt n

16、)vertex num=n;int i,j,co un t=0;int xmaxsize=0;for(i=0;ivertex nu m;i+)for(j=0;jvertexnum;j+)计算每个顶点的入度xi+=arcji;/xj存放入度数cout核心人物是：;int yu=20;/找度数大于域值的人物，域=20for(i=0;iyu) coutvertexi;coun t+ ;if(count=O) cout无;coute ndl;/huoyue 活跃人物若人物发出的Email总数大于10封，我认为就是活跃人物，所以我设置了域为 10，huoyue函数要完成的功能是找出度大于域值的人物，并输

17、出。templatevoid Mgraph:huoyue(i nt n)vertex num=n;int i,j,co un t=0;int ymaxsize=0;for(i=0;ivertexnum;i+)计算每个顶点的出度for( j=0;jvertex nu m;j+)yi+=arcij;/yi存放出度数cout活跃人物是：;int yu=10;找度数大于域值的人物，域=10for (i=0; iyu) coutvertexi;coun t+ ;if(count=0) cout无;coute ndl;/bianyuan 边缘人物若人物收到和发出的Email总数小于5封，我认为就是边缘人物

18、，所以我设置 了域为5，bianyuan函数要完成的功能是找入度与出度之和小于域值的人物， 并输出。templatevoid Mgraph:bia nyuan (i nt n) vertex num=n;int i,j,co un t=0;int zmaxsize=0;for(i=0;ivertexnum;i+)计算每个顶点的度数for(j=0;jvertex nu m;j+)zi=zi+arcij+arcji; zi存放入度 + 出度之和cout边缘人物是：;int yu=5;/找度数小于域值的人物，域=5for (i=0; ivertex num; i+) if(ziyu) coutver

19、texi;coun t+ ;if(count=O) cout无;coute ndl;/quanzi 查找交往圈子根据用户输入的一个人员的数字代码，查找该人员的交往圈子，我认为与指定 人物之间有边的人物就是与该人物有联系的，这些人就构成了一个交往圈子。 template void Mgraph:qua nzi (int v)int coun t=0;cout vertexv-1的交往圈子是：；for (int j=0; jvertex nu m; j+) if (arcv-1j!=INFINITY|arcjv-1!=INFINITY) / 交往圈子：与指定人物之间有边 就算 coutvertex

20、j ;coun t+;if(count=O) cout无;coute ndl;/ADD计算人员间两两间联系数计算指定人员两两间的联系数并返回(为查找小团体、桥接人做准备)template int Mgraph:ADD(i nt s,i nt t) int temp;if(st) temp=s; s=t; t=temp; else retur n (arcst+arcts);/BY 查找小团体中用来判断边缘人物找边缘人物并返回该人物数字代码(为查找小团体、桥接人做准备)templateint Mgraph:BY(i nt n) int i,j,co un t=0;int zmaxsize=0;f

21、or(i=0;in;i+)计算每个顶点的度数for(j=0;j n;j+)zi=zi+arcij+arcji; /zi 存放入度 + 出度之和int yu=5;/ 域=5for (i=0; in; i+)if(ziyu)return(i);coun t+ ;if(co un t=0)return(99);/DFS查找小团体查找小团体，从指定的顶点(我设置的是 0也就是第一个人)开始进行深度优 先遍历(如果当前人物A没有被访问过，并且也不是边缘人物，输出该人物A;再从该人物A开始进行深度遍历，如果找到与该人物交往密切的人物B则输出，再从B开始继续找下一个)，并且在查找过程中输出小团体成员。tem

22、plate void Mgraph:DFS(int v,int n)/v 控制递归 n 为总人数if (v=0)/如果是第一次使用for (i nt k=0;k n;k+)visitedk=0;/初始化顶点标记矩阵(全部置0代表没有访问过)DFS(v+1, n); 利用递归算法重复调用深度优先遍历DFSelseif (visitedv-1=0)/如果当前人物没有被访问过if(v-1!=BY(n)并且也不是边缘人物 int yu=10;域值coutvertexv-1 ”; 输出该结点的值visitedv-1=1;将该结点置为访问过！for (int k=0;kyu)如果两个结点之间交往密切DFS

23、(k+1,n); / 找下一个cout,;DFS(v+1, n);else DFS(v+1, n);/DFS2查找桥接人查找桥接人，两个小团体中，有联系，但没有达到域值的人物。从指定的顶点 开始进行深度优先遍历template void Mgraph:DFS2(int v,int n)/v 控制递归 n 为总人数int yu=10;域值for (i nt k=v-1;k 0 & ADD(v-1,k)yu & v-1!=BY( n)& k!=BY( n)/如果两个结点之间有边但交往不密切，并且分别属于两个小团体coutvertexv-1 vertexk;/ 输出桥接人结点的值DFS2(k+1,n

24、); / 找下一个if (v=n)DFS2(v+1, n);/主函数测试刚刚的Mgraph类中的各种成员函数是否编写正确，完成要求的功能。void mai n()cout|欢迎使用社会网络分析系统|e ndl;int n,e,m; /n总人数，e总关系数，m某个人员的数字代码cout请输入该社会网络总人数：;cinn;char *a=new charn; a是指针，a的值是新建数组的首地址，a0,a1等cout请依次输入人员名称：;for（i nt i=0;i ai;cout e;Mgraph G(a,n, e);cout以下是该社会网络对应的邻接矩阵：endl;G.Prin tGraph()

25、;cout社会网络分析中*e ndl;G.cen tre( n);G.huoyue( n);G.bia nyuan(n);cout小团体是：;G.DFS(O, n);coute ndl;cout联系小团体的桥接人物是:G.DFS2（1, n）;coute ndl;cout#include#includeconst int maxsize=100;const int INFINITY=O; 最大值无穷templatevclass T class Mgraph public:e边数Mgraph(T a,int n,int e); 构造函数，a结点数组，n顶点个数, void PrintGraph(

26、);输出邻接矩阵 void centre(int n); /核心人物成员函数 void huoyue(int n);活跃人物成员函数 void bianyuan(int n);边缘人物成员函数 void quanzi(int v);查找交往圈子函数int ADD(int s,int t);/计算人员两两间联系数int BY(int n);void DFS(int v,int n) ; /查找小团体函数(深度优先遍历) void DFS2(int v,int n) ; /查找桥接人函数(深度优先遍历) private:T vertexmaxsize;/ 存放顶点int arcmaxsizemax

27、size; / 存放边int vertexnum,arcnum; 顶点数，边数void CreateHW(T a,int n,int e); 构建无向图 int *visited;/Mgraph 构造函数templatevclass TMgraph:Mgraph(T a,int n,int e)visited=new intvertexnum; for(int i=0;ivoid Mgraph:CreateHW(T a,int n,int e)int w;权值 vertexnum=n;顶点数arcnum=e;/ 边数int i,j,k;coutvv 注意！请将人名对应到数字代码输入vvendl

28、;coutvv输入格式为：人员 1人员2权值vvendl;for (i=0; ivvertexnum; i+)vertexi=ai;顶点数组赋初值(放入一维数组)for (i=0; ivvertexnum; i+)/ 初始化邻接矩阵for (j=0; jvvertexnum; j+)arcij=0;for (k=0; kvarcnum; k+) 依次输入每一条边，并修改邻接矩阵的相应元素coutvv请输入第wk+lvv条边:; cinijw; ij边依附的两个顶点的序号，w权值arci-1j-1=w;置有边标志，存放权值/PrintGraph 输出template vclass Tvoid M

29、graphvT:PrintGraph()int i,j;for(i=0;ivvertexnum;i+)for(j=0;jvvertexnum;j+)coutvvarcijvvt;coutvvendl;/centre核心人物templatevclass Tvoid MgraphvT:centre(int n)vertexnum=n;int i,j,count=0;int xmaxsize=0;for(i=0;ivvertexnum;i+)for(j=O;jvvertexnum;j+)计算每个顶点的入度 xi+=arcji;xj存放入度数 coutvv 核心人物是：;int yu=20; 找度数大

30、于域值的人物，域=20for(i=0;ivvertexnum;i+)if(xiyu) coutvvvertexivv;count+ ; if(count=0) coutvv无; coutvvendl;/huoyue活跃人物templatevclass T void MgraphvT:huoyue(int n)vertexnum=n;int i,j,count=0;int ymaxsize=0; for(i=O;ivvertexnum;i+)计算每个顶点的出度 for( j=0;jyu) coutvvvertexivv;count+ ;if(count=0) coutvv无; coutvvend

31、l;/bianyuan边缘人物templatevclass T void MgraphvT:bianyuan(int n)vertexnum=n;int i,j,count=0;int zmaxsize=0;for(i=O;ivvertexnum;i+)计算每个顶点的度数 for(j=0;jvvertexnum;j+)zi=zi+arcij+arcji; zi存放入度 + 出度之和 coutvv 边缘人物是：;int yu=5; /找度数小于域值的人物，域=5for (i=0; ivvertexnum; i+)if(zivyu)coutvvvertexivv; count+ ;if(count

32、=0) coutvv无; coutvvendl;/quanzi查找交往圈子template vclass Tvoid MgraphvT:quanzi(int v)深度优先遍历图int count=0;coutvv vvvertexv-1vv的交往圈子是:;for (int j=0; jvvertexnum; j+)if (arcv-1j!=INFINITY|arcjv-1!=INFINITY) 交往圈子：与指定人物之间有边就算coutvvvertexjvv;count+;if(count=0) coutvv无;coutvvendl;/ADD计算人员间两两间联系数template vclass

33、Tint MgraphvT:ADD(int s,int t) int temp;if(st)temp=s; s=t; t=temp;else return (arcst+arcts);/BY 查找小团体中用来判断边缘人物templatevclass Tint MgraphvT:BY(int n) int i,j,count=0;int zmaxsize=0;for(i=0;ivn;i+)计算每个顶点的度数for(j=0;jvn;j+) zi=zi+arcij+arcji; zi存放入度 + 出度之和 int yu=5;/ 域=5for (i=0; ivn; i+)if(zivyu)return(i); count+ ;if(count=0) return(99);/DFS查找小团体template vclass Tvoid MgraphvT:DFS(int v,int n)v 控制递归 n 为总人数if (v=0)如果是第一次使用 for (int k=0;kvn;k+)visitedk=O;初始化顶点标记矩阵(全部置0代表没有访问过)DFS(v+1,n);/利用递归算法重复调用深度优先遍历DFSelseif (visitedv-1=0)如果当前人物没有被访问过if(v-1!=BY(n)并且也不是边缘人物 int yu=10;/ 域值coutvyu)如果两个结点之间交往密切DF