![社会网络分析系统的设计和实现数据结构课程设计_第1页](http://file4.renrendoc.com/view/60bbf4048a771bf60c365b2481fe9ab8/60bbf4048a771bf60c365b2481fe9ab81.gif)
![社会网络分析系统的设计和实现数据结构课程设计_第2页](http://file4.renrendoc.com/view/60bbf4048a771bf60c365b2481fe9ab8/60bbf4048a771bf60c365b2481fe9ab82.gif)
![社会网络分析系统的设计和实现数据结构课程设计_第3页](http://file4.renrendoc.com/view/60bbf4048a771bf60c365b2481fe9ab8/60bbf4048a771bf60c365b2481fe9ab83.gif)
![社会网络分析系统的设计和实现数据结构课程设计_第4页](http://file4.renrendoc.com/view/60bbf4048a771bf60c365b2481fe9ab8/60bbf4048a771bf60c365b2481fe9ab84.gif)
![社会网络分析系统的设计和实现数据结构课程设计_第5页](http://file4.renrendoc.com/view/60bbf4048a771bf60c365b2481fe9ab8/60bbf4048a771bf60c365b2481fe9ab85.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 《机械常识》(第二版) 课件 -第六章 轴系零部件
- 岗位考试题库(886道)
- 2016年ACOG指南:外倒转术
- 防溺水安全知识
- 哈密地区巴里坤哈萨克自治县2024届三年级数学第二学期期末学业质量监测试题含解析
- 分析天平的构造与使用
- 学前小班上学期科学《上上下下》教学设计
- 哈尔滨道外区2025年初三数学试题第三次质量检测试题试卷含解析
- 石英反应器项目可行性实施报告
- 贵州省遵义市绥阳县2024年五年级数学第二学期期末考试模拟试题含解析
- 立体几何教学中的障碍及对策
- 水果玉米种植加工项目建议书范文
- 单值移动极差图(空白表格)
- 电子汽车衡检定分度数的分析
- 广东省标准建筑地基基础设计规范 DBJ
- 中银保险深圳分公司车险公估招标文件 - 中银保险有限公司
- 糟渣类饲料营养成分表
- 电线电缆挤塑工艺培训学习
- 推拿学及答案
- 全文图解医院《九项准则》学习PPT
- 浅谈实践活动中培养少年队员志愿服务精神
评论
0/150
提交评论