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

《社会网络分析系统的设计和实现数据结构课程设计.doc》由会员分享，可在线阅读，更多相关《社会网络分析系统的设计和实现数据结构课程设计.doc（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流社会网络分析系统的设计和实现数据结构课程设计.精品文档.上海电力学院数据结构（C+）课程设计题目: 综合实验16 社会网络分析系统的设计和实现(*)姓 名： XXX 学 号： 2012XXXX 院系： 计算机科学与技术学院 专业年级： 信息安全 2012XXX 2014年 07月 08日目 录一、 设计题目1二、需求分析11）运行环境（软、硬件环境）12）输入的形式和输入值的范围13）输出的形式描述14）功能描述15）测试数据2三、概要设计21）抽象数据类型定义描述22）功能模块设计（如主程序模块设计）53）模块层次调用关系图5四、详细设计6

2、五、调试分析12 问题&改进&补充12 算法的时间空间复杂性分析14 心得体会14六、测试结果15七 、附录：程序设计源代码16一、 设计题目社会网络分析系统的设计和实现二、需求分析1）运行环境（软、硬件环境）软件：Microsoft Visual C+ 6.0硬件：能运行Microsoft Visual C+ 6.0的硬件平台如CPU:Intel 酷睿i3 3217U；内存4G；操作系统Windows 72）输入的形式和输入值的范围数据类型： 整型（int）、字符型(char) 范围：1. 总人数（1100）2. 人员名称（AZ）3. 人员数字代码（1100）4. 关系总数（1100）5.

3、某条关系（人员数字代码 人员数字代码 权值）注：权值（1100）即email数据举例：总人数8个、人员名称ABCDEFGH、人员数字代码12345678、关系总数15条、具体某一条关系1 2 9。3）输出的形式描述1. 该社会网络的邻接矩阵2. 该社会网络中的核心人物、活跃人物、边缘人物3. 该社会网络中的小团体、桥接人物4. 查找任何人的交往圈子4）功能描述 1. 对email数据进行预处理，利用数据结构课程中图中的理论，建立社会网络的邻接矩阵。2. 利用度的概念，找出社会网络中核心人物、活跃人物和边缘人物。3. 利用子图概念，分析社会网络的结构，找出小团体和联系小团体的桥接人物。4. 能查

4、找任何人的交往圈子。5）测试数据三、概要设计1）抽象数据类型定义描述（对各类的成员及成员函数进行抽象描述，参见书或ppt及实验）ADTMgraphisData存放图中社会网络人物的一维数组vertexmaxsize存放图中社会网络人物的关系的二维数组arcmaxsizemaxsize图中人物总数vertexnum和关系总数,arcnum标志数组visitedOperationu Mgraph （构造函数）初始化值：社会网络中 a人员名称，n总人数，e总关系数；标志顶点访问的数组visitedi置0。 动作：将键盘输入的值带入，调用有向网的创建函数CreateHW。u CreateHW（创建有向

5、网）输入：图的人数和关系数、存放图中人的数组、存放图中关系的数组前置条件：构造函数调用功能：创建有向网输出：无后置条件：有向网建立u PrintGraph（输出邻接矩阵）输入：无前置条件：有向网已经建立功能：输出邻接矩阵输出：邻接矩阵后置条件：无u Centre（核心人物）输入：无前置条件：有向网已经建立，设定核心人物的域值yu=20功能：找出社会网络的核心人物（计算每个顶点的入度，找度数大于域值的人物）输出：若找到则输出社会网络的核心人物，没有找到则输出“无”。后置条件：无u Huoyue（活跃人物）输入：无前置条件：有向网已经建立，设定活跃人物的域值yu=10功能：找出社会网络的活跃人物（

6、计算每个顶点的出度，找度数大于域值的人物）输出：若找到则输出社会网络的活跃人物，没有找到则输出“无”。后置条件：无u Bianyuan（边缘人物）输入：无前置条件：有向网已经建立，设定边缘人物的域值yu=5功能：找出社会网络的边缘人物（计算每个顶点的出入度之和，找度数小于域值的人物）输出：若找到则输出社会网络的边缘人物，没有找到则输出“无”。后置条件：无u quanzi（交往圈子）输入：输入一个人员的数字代码（用于查找该人员的交往圈子）前置条件：有向网已经建立功能：查找交往圈子（与指定人物之间有边的人物就是与该人物有联系的，这些人就构成了一个交往圈子）。输出：输出指定人物的交往圈子后置条件：无

7、u ADD（计算人员两两间的关系数）输入：无前置条件：有向网已经建立，给出两个人物的数字代码功能：计算指定人员两两间的联系数并返回（为查找小团体、桥接人做准备）输出：返回指定人员两两间的联系数后置条件：无u BY（返回边缘人物数字代码）输入：无前置条件：有向网已经建立功能：找边缘人物并返回该人物数字代码（为查找小团体、桥接人做准备）输出：返回边缘人物的数字代码后置条件：无u DFS（小团体）输入：无前置条件：有向网、ADD函数、BY函数都已经建立，初始化顶点标记矩阵（全部置0）功能：查找小团体，从指定的顶点开始进行深度优先遍历（如果当前人物没有被访问过，并且也不是边缘人物，输出该人物；再从该人

8、物开始进行深度遍历，如果找到与该人物交往密切的人物则输出，继续找下一个）输出：输出小团体后置条件：对访问过的顶点置1u DFS2（桥接人）输入：无前置条件：有向网、ADD函数、BY函数都已经建立功能：查找桥接人，从指定的顶点开始进行深度优先遍历输出：两个小团体中，有联系，但没有达到域值的人物后置条件：无end ADT Mgraph2）功能模块设计（如主程序模块设计）1. 主程序模块：连接各种功能子模块，完成程序的基本操作实现功能2. 构造社会网络模块：按照要求构建有向网3. 输出邻接矩阵模块：根据用户输入的社会网络，输出该网络图的邻接矩阵4. 核心人物模块：根据用户输入的社会网络，计算得出该社

9、会网络中的核心人物5. 活跃人物模块：根据用户输入的社会网络，计算得出该社会网络中的活跃人物6. 边缘人物模块：根据用户输入的社会网络，计算得出该社会网络中的边缘人物7. 交往圈子模块：根据用户输入的社会网络，计算得出该网络中指定人物的交往圈子8. 人物两两联系数模块：根据用户输入的社会网络，返回指定人员两两间的联系数9. 判断边缘人物模块：根据用户输入的社会网络，返回边缘人物的数字代码10. 小团体模块：根据用户输入的社会网络，深度优先遍历得出该网络中的所有小团体11. 桥接人物模块：根据用户输入的社会网络，深度优先遍历得出小团体间的桥接人物3）模块层次调用关系图桥接人DFS2 小团体DFS

10、 交往圈子quanzi边缘人物bianyuanMain( )Mgraph活跃人物huoyue核心人物centre输出邻接矩阵PrintGraph构建有向网CreateHW人员两两联系数ADD判断边缘人物BY四、 详细设计实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。#include#include#includeconst int maxsize=100;const int INFINITY=0;/最大值无穷定义一个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 quanzi(int v); /查找交往圈子函数 int ADD(int s,int t) ;/计算人员两两间联系数 int BY(int n) ; void D

12、FS(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总人数，e总关系数；标志顶点访问的数组visitedi置0；调用有向网的创建函数CreateHW。templateMgra

13、ph:Mgraph(T a,int n,int e) visited=new intvertexnum; for(int i=0;ivertexnum;i+) visitedi=0; CreateHW(a,n,e); /创建/CreateHW 构建有向网将用户输入的值带入，并完成存储：人物名称放入一维数组vertexi，人物间的Email发送数（权值）放入二维数组arci-1j-1。template void Mgraph:CreateHW(T a,int n,int e) int w; /权值 vertexnum=n; /顶点数 arcnum=e; /边数 int i,j,k;cout注意！

14、请将人名对应到数字代码输入endl;cout输入格式为：人员1 人员2 权值endl;for (i=0; ivertexnum; i+) vertexi=ai;/顶点数组赋初值（放入一维数组）for (i=0; ivertexnum; i+) /初始化邻接矩阵for (j=0; jvertexnum; j+)arcij=0; for (k=0; karcnum; k+) /依次输入每一条边，并修改邻接矩阵的相应元素cout请输入第k+1ijw; /边依附的两个顶点的序号arci-1j-1=w; /置有边标志，存放权值/PrintGraph 输 出通过二重循环输出社会网络对应的邻接矩阵存储图te

15、mplate void Mgraph:PrintGraph()/输出邻接矩阵int i,j;for(i=0;ivertexnum;i+) for(j=0;jvertexnum;j+) coutarcijt;coutendl;/centre核心人物若人物收到的Email总数大于20封，我认为就是核心人物，所以我设置了域为20，centre函数要完成的功能是找入度大于域值的人物，并输出。 templatevoid Mgraph:centre(int n) vertexnum=n;int i,j,count=0;int xmaxsize=0;for(i=0;ivertexnum;i+)for(j=0

16、;jvertexnum;j+)/计算每个顶点的入度xi+=arcji;/xj存放入度数cout核心人物是：; int yu=20; /找度数大于域值的人物, 域=20for(i=0;iyu)coutvertexi ; count+ ;if(count=0) cout无;coutendl;/huoyue活跃人物若人物发出的Email总数大于10封，我认为就是活跃人物，所以我设置了域为10，huoyue函数要完成的功能是找出度大于域值的人物，并输出。 templatevoid Mgraph:huoyue(int n) vertexnum=n;int i,j,count=0;int ymaxsize

17、=0;for(i=0;ivertexnum;i+)/计算每个顶点的出度for( j=0;jvertexnum;j+)yi+=arcij;/yi存放出度数cout活跃人物是：;int yu=10; /找度数大于域值的人物, 域=10for (i=0; iyu) coutvertexi ; count+ ;if(count=0) cout无;coutendl;/bianyuan边缘人物若人物收到和发出的Email总数小于5封，我认为就是边缘人物，所以我设置了域为5，bianyuan函数要完成的功能是找入度与出度之和小于域值的人物，并输出。 templatevoid Mgraph:bianyuan(

18、int n) vertexnum=n;int i,j,count=0;int zmaxsize=0;for(i=0;ivertexnum;i+)/计算每个顶点的度数for(j=0;jvertexnum;j+)zi=zi+arcij+arcji; /zi存放入度+出度之和 cout边缘人物是：;int yu=5; /找度数小于域值的人物, 域=5for (i=0; ivertexnum; i+) if(ziyu) coutvertexi ; count+ ;if(count=0) cout无;coutendl;/quanzi查找交往圈子根据用户输入的一个人员的数字代码，查找该人员的交往圈子，我认

19、为与指定人物之间有边的人物就是与该人物有联系的，这些人就构成了一个交往圈子。template void Mgraph:quanzi(int v) 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 计算人员间两两间联系数计算指定人员两两间的联系数并返回（为查找小团体、桥接人做准备）template i

20、nt Mgraph:ADD(int s,int t) int temp;if(st) temp=s; s=t; t=temp; else return (arcst+arcts);/BY 查找小团体中用来判断边缘人物找边缘人物并返回该人物数字代码（为查找小团体、桥接人做准备）templateint Mgraph:BY(int n)int i,j,count=0;int zmaxsize=0;for(i=0;in;i+)/计算每个顶点的度数for(j=0;jn;j+)zi=zi+arcij+arcji; /zi存放入度+出度之和int yu=5; / 域=5for (i=0; in; i+) i

21、f(ziyu)return(i); count+ ;if(count=0) return(99);/DFS 查找小团体查找小团体，从指定的顶点（我设置的是0也就是第一个人）开始进行深度优先遍历（如果当前人物A没有被访问过，并且也不是边缘人物，输出该人物A；再从该人物A开始进行深度遍历，如果找到与该人物交往密切的人物B则输出，再从B开始继续找下一个），并且在查找过程中输出小团体成员。template void Mgraph:DFS(int v,int n) /v控制递归 n为总人数 if (v=0)/如果是第一次使用for (int k=0;kn;k+)visitedk=0; /初始化顶点标记矩

22、阵（全部置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(k+1,n); /找下一个cout,;DFS(v+1,n);else DFS(v+1,n);/DFS2 查找桥接人查找桥接人，两个小团体中，有联系，但没有达到域值的人物。从指定的顶点开始进行深度优先

23、遍历template void Mgraph:DFS2(int v,int n) /v控制递归 n为总人数int yu=10; /域值for (int k=v-1;k0 & ADD(v-1,k)yu & v-1!=BY(n)& k!=BY(n)/如果两个结点之间有边但交往不密切，并且分别属于两个小团体coutvertexv-1 vertexk ;/输出桥接人结点的值DFS2(k+1,n); /找下一个if (v=n)DFS2(v+1,n);/主函数测试刚刚的Mgraph类中的各种成员函数是否编写正确，完成要求的功能。void main()cout| 欢迎使用社会网络分析系统 |endl;int

24、 n,e,m; /n总人数，e总关系数，m某个人员的数字代码coutn; char *a=new charn; /a是指针，a的值是新建数组的首地址，a0,a1等 cout请依次输入人员名称：; for(int i=0;iai; coute;Mgraph G(a,n,e);cout以下是该社会网络对应的邻接矩阵：endl;G.PrintGraph();cout*社会网络分析中*：endl;G.centre(n);G.huoyue(n);G.bianyuan(n);cout小团体是：;G.DFS(0,n);coutendl; cout联系小团体的桥接人物是：; G.DFS2(1,n);coute

25、ndl; coutm;G.quanzi(m);五、调试分析 （包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会） 问题&改进&补充：【问题1】：小团体和桥接人的理解与定义小团体：小团体就是由交往比较密切的一群人构成的，因此要设一个域值，email数据（权值）超过这个域值才能算交往密切；一个人不能单独构成一个小团体，小团体至少要2个成员组成。桥接人：桥接人就是联系两个小团体的中间人，也就是说一个小团体可以通过对应的桥接人和另外一个小团体取得联系，桥接人分属于两个不同的团体。【问题2】：参数传递问题 目的是在一个成员函数里调用另一个成员函数中的数据，一开始想到的是将代码段直

26、接复制，但考虑到效率的问题，没有使用；然后想到了利用全局变量，但又觉得不妥；后来问了老师，老师建议我使用参数传递的方法，将需要的数据带回。于是做了如下修改：主函数中，增加char team2020; 并将G.DFS(0); 改成G.DFS(0,n,team); 使DFS查找小团体的函数中，可以使用主函数中的数据n总人数；使桥接人的函数中，可以使用DFS查找小团体的函数中的二维数组：team2020【问题3】：递归调用中的数据存储为了实现桥接人的查找，要将小团体储存到一个二维数组中，在递归调用中存入数组真的不是一件简单的事，初始化数组的下标就是一件很麻烦的事情，因为递归调用每一次都会调用函数本身

27、，若在函数体里面初始化数组下标的话，每调用一次，就会归零。解决方法：使用参数传递，将数组下标作为两个参数，每次调用时都将其传回，这样可以保证数组下标有效完成计数的功能。主函数中，将G.DFS(0,n,team)； 改成G.DFS(0,n,team,0,0)头文件中，改成void DFS(int v,int n,char team2020,int i,int j)【改进1】：createHW 构建有向网中，原本老师PPT上演示的是：arcij=1; arcji=1; 之后改进为 ：arci-1j-1=1; arcj-1i-1=1; 改进原因：按照原来的写法，输入两个人员之间的关系（顶点与顶点之间

28、的边）要从0开始，由于和日常生活的数数习惯不同，因此加以改进，使之从1开始，方便使用。【改进2】：查找交往圈子中，原本应该是：if (arcvj!=INFINITY|arcjv!=INFINITY) 需要改为：if (arcv-1j!=INFINITY|arcjv-1!=INFINITY) 改进原因：由于改进1的影响，主函数中要求用户输入一个人员的数字代码，查找该人员的交往圈子时，用户也是从1开始数的，为了使程序显示正确，需要将下标v改成v-1。【改进3】：存放小团体的数组其实不是必要的之前一直在纠结递归调用中存放数组的问题，但突然7号早上想到另一个更省事儿的方法，用排除法找桥接人！换个角度来

29、看桥接人，就是分属于两个小团体，之间有联系但是联系不密切，另外，桥接人也不能是边缘人物。于是做了如下简化改进：主函数中，将G.DFS(0,n,team,0,0)； 改成G.DFS(0,n)；头文件中，改成void DFS(int v,int n)【补充1】：补充没有核心人物或者没有活跃人物或者没有边缘人物的情况。一开始也没有想的这么全面，经过多次测试后发现这几种情况也是存在的，原来的程序在这种情况下显示的是空白，因此加以改进了一下增加了count计数器，如果一个人物都没有的话，就输出“无”。 算法的时间空间复杂性分析1. 本设计中算法的时间复杂度分为三类：O(1)ADD 计算人员间两两间联系数

30、O(n)Mgraph 构造函数O(n2)CreateHW 构建有向网、PrintGraph 输出邻接矩阵、centre核心人物 、huoyue活跃人物、bianyuan边缘人物、quanzi查找交往圈子、BY 判断边缘人物、DFS 查找小团体、DFS2 查找桥接人2. 本设计中算法的空间复杂度为：O(1) 心得体会：一开始选题的时候，就觉得这个题目很有趣，尽管它的难度系数比较高，但我还是义无反顾地选择了它社会网络分析系统的设计和实现。图这一章老师讲的没有单链表和二叉树那样细致，因为快到期末了课时很紧张，但做相关实验的时候，我就对图这部分的内容产生了浓厚的兴趣，因为社交网络和我们的生活比较贴切，

31、图的应用在类似人人、微信朋友圈的社交网络中都会用到。自从我做完了上一个大作业，多余的两天半时间我就开始着手做这个课程设计了，一开始选择了使用无向图，成功完成了除小团体和桥接人之外的所有功能，但等到第一次课程设计上课的时候，和老师探讨了小团体和桥接人的查找方法后，发现一开始就选错了图的模型，应该选择有向网！之前的代码也要全部推翻重来，顿时觉得压力好大。好在回到寝室后的一整个下午加上一整个晚上的效率很高，终于将实现对email数据的预处理、建立社会网络的邻接矩阵、找出社会网络中核心人物、活跃人物和边缘人物的函数都完成了。但对于小团体和桥接人的定义还是比较模糊的，于是第二次上课程设计的时候，详细咨询

32、了老师。之后大量的时间都花在设计小团体和桥接人上了。期间也碰到了很多问题，通过自己调试修改、上网查阅资料、课上课下咨询老师，都得到了解决。通过这次数据结构课程设计，我对之前学习的C+内容更加熟悉了，更好地掌握与理解了模板的使用、二维数组、参数传递、函数调用等内容；对数据结构这门课程也有了更进一步的学习与掌握，处理问题的思路与方法也有所拓宽，能理解与运用图的相关知识解决实际问题在老师的指导下，不仅独立完成了社会网络分析系统的设计和实现，还从老师那里学到了很多书上没有的技巧，比如C+程序调试中所使用“断点”调试方法，之前我是完全不知道的。通过这次课程设计，在这短短的5天中，我感觉收获颇多！六、测试

33、结果七 、附录：程序设计源代码#include#include#includeconst int maxsize=100;const int INFINITY=0;/最大值无穷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 quanzi(int v); /查

34、找交往圈子函数 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 arcmaxsizemaxsize; /存放边int vertexnum,arcnum;/顶点数，边数void CreateHW(T a,int n,int e);/构建无向图int *visited;/Mgraph 构造函数templateMgraph

35、:Mgraph(T a,int n,int e)visited=new intvertexnum; for(int i=0;ivertexnum;i+) visitedi=0; CreateHW(a,n,e); /创建/CreateHW 构建有向网template void Mgraph:CreateHW(T a,int n,int e) int w;/权值 vertexnum=n; /顶点数 arcnum=e; /边数 int i,j,k;cout注意！请将人名对应到数字代码输入endl;cout输入格式为：人员1 人员2 权值endl;for (i=0; ivertexnum; i+) v

36、ertexi=ai;/顶点数组赋初值（放入一维数组）for (i=0; ivertexnum; i+) /初始化邻接矩阵for (j=0; jvertexnum; j+)arcij=0; for (k=0; karcnum; k+) /依次输入每一条边，并修改邻接矩阵的相应元素cout请输入第k+1ijw; /ij边依附的两个顶点的序号，w权值arci-1j-1=w; /置有边标志，存放权值/PrintGraph 输 出template void Mgraph:PrintGraph()int i,j;for(i=0;ivertexnum;i+)for(j=0;jvertexnum;j+) co

37、utarcijt;coutendl;/centre核心人物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+)/计算每个顶点的入度xi+=arcji;/xj存放入度数cout核心人物是：; int yu=20; /找度数大于域值的人物, 域=20for(i=0;iyu)coutvertexi ; count+ ;if(count=0) cout无;coutendl;/huoyue活跃人物templatevoi

38、d Mgraph:huoyue(int n)vertexnum=n;int i,j,count=0;int ymaxsize=0;for(i=0;ivertexnum;i+)/计算每个顶点的出度for( j=0;jvertexnum;j+)yi+=arcij;/yi存放出度数cout活跃人物是：;int yu=10; /找度数大于域值的人物, 域=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+)/计算每个顶点的度数for(j=0;jvertexnum;j+