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

1、上海电力学院数据结构（C+）课程设计题目：综合实验16社会网络分析系统的设计和实现（*）姓名：XXX学号：2012XXXX院系：计算机科学与技术学院专业年级：信息安全2012XXX2014年07月08日一、设计题目Q.二、需求分析Q.1）运行环境（软、硬件环境）Q2）输入的形式和输入值的范围错误！未定义书签。3）输出的形式描述0.4）功能描述Q.5）测试数据Q.三、概要设计错误！未定义书签。1）抽象数据类型定义描述0.2）功能模块设计（如主程序模块设计）33）模块层次调用关系图3.四、详细设计6.五、调试分析12问题&改进&补充10算法的时间空间复杂性分析11心得体会.12六、

2、测试结果12七、附录：程序设计源代码.12一、设计题目社会网络分析系统的设计和实现二、需求分析1）运行环境（软、硬件环境）软件：MicrosoftVisualC+6.0硬件：能运行MicrosoftVisualC+6.0的硬件平台如CPU:Intel酷睿i33217U;内存4G;操作系统Windows72）输入的形式和输入值的范围数据类型：整型（int）、字符型（char）范围：1 .总人数（1100）2 .人员名称（AZ）3 .人员数字代码（1100）4 .关系总数（1100）5 .某条关系（人员数字代码人员数字代码权值）注：权值（1100）即email数据举例：总、人数8个、人员名称ABC

3、DEFGH、人员数字代码12345678、关系总数15条、具体某一条关系129。3）输出的形式描述1 .该社会网络的邻接矩阵2 .该社会网络中的核心人物、活跃人物、边缘人物3 .该社会网络中的小团体、桥接人物4 .查找任何人的交往圈子4）功能描述1 .对email数据进行预处理，利用数据结构课程中图中的理论，建立社会网络的邻接矩阵。2 .利用度的概念，找出社会网络中核心人物、活跃人物和边缘人物。3 .利用子图概念，分析社会网络的结构，找出小团体和联系小团体的桥接人物。4 .能查找任何人的交往圈子。5）测试数据三、概要设计1）抽象数据类型定义描述ppt及实验）（对各类的成员及成员函数进行抽象描述

4、，参见书或ADTMgraphisData存放图中社会网络人物的一维数组vertexmaxsize存放图中社会网络人物的关系的二维数组arcmaxsizemaxsize图中人物总数vertexnum和关系总数,arcnum标志数组visitedOperationMgraph（构造函数）初始化值：社会网络中a口人员名称，n总人数，e总关系数；标志顶点访问的数组visitedi置0。动作：将键盘输入的值带入，调用有向网的创建函数CreateHW。CreateHW（创建有向网）输入：图的人数和关系数、存放图中人的数组、存放图中关系的数组前置条件：构造函数调用功能：创建有向网输出：无后置条件：有向网建立

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

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

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

8、有向网、ADD®数、BY函数都已经建立功能：查找桥接人，从指定的顶点开始进行深度优先遍历输出：两个小团体中，有联系，但没有达到域值的人物后置条件：无endADTMgraph2）功能模块设计（如主程序模块设计）1,主程序模块：连接各种功能子模块，完成程序的基本操作实现功能2.构造社会网络模块：按照要求构建有向网3,输出邻接矩阵模块：根据用户输入的社会网络，输出该网络图的邻接矩阵4 .核心人物模块：根据用户输入的社会网络，计算得出该社会网络中的核心人物5 .活跃人物模块：根据用户输入的社会网络，计算得出该社会网络中的活跃人物6 .边缘人物模块：根据用户输入的社会网络，计算得出该社会网络中

9、的边缘人物7 .交往圈子模块：根据用户输入的社会网络，计算得出该网络中指定人物的交往圈子8 .人物两两联系数模块：根据用户输入的社会网络，返回指定人员两两间的联系数9 .判断边缘人物模块：根据用户输入的社会网络，返回边缘人物的数字代码10 .小团体模块：根据用户输入的社会网络，深度优先遍历得出该网络中的所有小团体11 .桥接人物模块：根据用户输入的社会网络，深度优先遍历得出小团体间的桥接人物实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。#include<iostream.h>#include<stdlib.h>#include<st

10、ring.h>constintmaxsize=100;constintINFINITY=0;最大值无穷定义一个Mgraph类，用来实现基本功能：构造函数初始化值，根据用户输入的社会网络图构建有向网(邻接矩阵存储形式)，查找该社会网络中的核心人物、活跃人物、边缘人物、小团体、桥接人物，查找任何人的交往圈子。template<classT>classMgraphpublic:Mgraph(Ta,intn,inte);/构造函数，a口结点数组，n顶点个数，e边数voidPrintGraph();输出邻接矩阵voidcentre(intn);/核心人物成员函数voidhuoyue(i

11、ntn);/活跃人物成员函数voidbianyuan(intn);/边缘人物成员函数voidquanzi(intv);查找交往圈子函数intADD(ints,intt);计算人员两两间联系数intBY(intn);voidDFS(intv,intn);/查找小团体函数(深度优先遍历)voidDFS2(intv,intn);/查找桥接人函数(深度优先遍历)private:Tvertexmaxsize;/存放顶点intarcmaxsizemaxsize;/存放边intvertexnum,arcnum;/顶点数，边数voidCreateHW(Ta,intn,inte);/构建有向网int*visit

12、ed;);Mgraph构造函数初始化值：社会网络中a口人员名称，n总人数，e总关系数；标志顶点访问的数组visitedi置0;调用有向网的创建函数CreateHW。template<classT>Mgraph<T>:Mgraph(Ta,intn,inte)visited=newintvertexnum;for(inti=0;i<vertexnum;i+)visitedi=0;CreateHW(a,n,e);/创建)/CreateHW构建有向网将用户输入的值带入，并完成存储：人物名称放入一维数组vertexi,人物问的Email发送数(权值)放入二维数组arci-1

13、j-1。template<classT>voidMgraph<T>:CreateHW(Ta口,intn,inte)intw;/权值vertexnum=n;顶点数arcnum=e;边数inti,j,k;cout<<"注意！请将人名对应到数字代码输入"<<endl;cout<<"输入格式为：人员1人员2权值"<<endl;for(i=0;i<vertexnum;i+)vertexi=ai;/顶点数组赋初值(放入一维数组)for(i=0;i<vertexnum;i+)初始化邻接

14、矩阵for(j=0;j<vertexnum;j+)arcij=0;for(k=0;k<arcnum;k+)/依次输入每一条边，并修改邻接矩阵的相应元素cout<<"请输入第"<<k+1<<"条边:"；cin>>i>>j>>w;/边依附的两个顶点的序号arci-1j-1=w;/置有边标志，存放权值)/PrintGraph输出通过二重循环输出社会网络对应的邻接矩阵存储图template<classT>voidMgraph<T>:PrintGraph()

15、输出邻接矩阵inti,j;for(i=0;i<vertexnum;i+)for(j=0;j<vertexnum;j+)cout<<arcij<<'t'cout<<endl;)/centre核心人物若人物收到的Email总数大于20封，我认为就是核心人物，所以我设置了域为20,centre函数要完成的功能是找入度大于域值的人物，并输出。template<classT>voidMgraph<T>:centre(intn)vertexnum=n;inti,j,count=0;intxmaxsize=0;for(i

16、=0;i<vertexnum;i+)for(j=0；j<vertexnum；j+)/计算每个顶点的入度xi+=arcji;/xj存放入度数cout<<">核心人物是："intyu=20;找度数大于域值的人物，域=20for(i=0;i<vertexnum;i+)if(xi>yu)cout<<vertexi<<""count+;if(count=0)cout<<"无"cout<<endl;/huoyue活跃人物若人物发出的Email总数大于10封，

17、我认为就是活跃人物，所以我设置了域为10,huoyue函数要完成的功能是找出度大于域值的人物，并输出。template<classT>voidMgraph<T>:huoyue(intn)vertexnum=n;inti,j,count=0;intymaxsize=0;for(i=0;i<vertexnum;i+)/计算每个顶点的出度for(j=0;j<vertexnum;j+)yi+=arcij;/yi存放出度数cout<<">活跃人物是："intyu=10;找度数大于域值的人物，域=10for(i=0;i<ver

18、texnum;i+)if(yi>yu)cout<<vertexi<<""count+;if(count=0)cout<<"无"cout<<endl;/bianyuan边缘人物若人物收到和发出的Email总数小于5封，我认为就是边缘人物，所以我设置了域为5,bianyuan函数要完成的功能是找入度与出度之和小于域值的人物，并输出。template<classT>voidMgraph<T>:bianyuan(intn)vertexnum=n;inti,j,count=0;intzm

19、axsize=0;for(i=0;i<vertexnum;i+)/计算每个顶点的度数for(j=0;j<vertexnum;j+)zi=zi+arcij+arcji;/zi存放入度+出度之和cout<<">边缘人物是："intyu=5;找度数小于域值的人物，域=5for(i=0;i<vertexnum;i+)if(zi<yu)cout<<vertexi<<""count+;if(count=0)cout<<"无"cout<<endl;/quanz

20、i查找交往圈子根据用户输入的一个人员的数字代码，查找该人员的交往圈子，我认为与指定人物之间有边的人物就是与该人物有联系的，这些人就构成了一个交往圈子。template<classT>voidMgraph<T>:quanzi(intv)intcount=0;cout<<">"<<vertexv-1<<"的交往圈子是："；for(intj=0;j<vertexnum;j+)if(arcv-1j!=INFINITY|arcjv-1!=INFINITY)交往圈子：与指定人物之间有边就算cou

21、t<<vertexj<<""count+;if(count=0)cout<<"无"cout<<endl;/ADD计算人员问两两间联系数计算指定人员两两间的联系数并返回(为查找小团体、桥接人做准备)template<classT>intMgraph<T>:ADD(ints,intt)inttemp;if(s>t)temp=s;s=t;t=temp;elsereturn(arcst+arcts);/BY查找小团体中用来判断边缘人物找边缘人物并返回该人物数字代码(为查找小团体、桥接人

22、做准备)template<classT>intMgraph<T>二BY(intn)inti,j,count=0;intzmaxsize=0;for(i=0;i<n;i+)计算每个顶点的度数for(j=0;j<n;j+)zi=zi+arcij+arcji;/zi存放入度+出度之和intyu=5;/域=5for(i=0;i<n;i+)if(zi<yu)return(i);count+;if(count=0)return(99);/DFS查找小团体查找小团体，从指定的顶点(我设置的是0也就是第一个人)开始进行深度优先遍历(如果当前人物A没有被访问过，并

23、且也不是边缘人物，输出该人物A;再从该人物A开始进行深度遍历，如果找到与该人物交往密切的人物B则输出，再从B开始继续找下一个)，并且在查找过程中输出小团体成员。template<classT>voidMgraph<T>:DFS(intv,intn)/v控制递归n为总人数if(v=0)/如果是第一次使用for(intk=0;k<n;k+)visitedk=0;初始化顶点标记矩阵(全部置0代表没有访问过)DFS(v+1,n);利用递归算法重复调用深度优先遍历DFSelseif(visitedv-1=0)/如果当前人物没有被访问过if(v-1!=BY(n)/并且也不是边

24、缘人物intyu=10;/域值cout<<vertexv-1<<""/输出该结点的值visitedv-1=1;/将该结点置为访问过！for(intk=0;k<n;k+)(if(ADD(v-1,k)>yu)/如果两个结点之间交往密切DFS(k+1,n);/找下一个cout<<","DFS(v+1,n);elseDFS(v+1,n);/DFS2查找桥接人查找桥接人，两个小团体中，有联系，但没有达到域值的人物。从指定的顶点开始进行深度优先遍历template<classT>voidMgraph<

25、T>:DFS2(intv,intn)/v控制递归n为总人数intyu=10;/域值for(intk=v-1;k<n;k+)if(ADD(v-1,k)>0&&ADD(v-1,k)<yu&&v-1!=BY(n)&&k!=BY(n)如果两个结点之间有边但交往不密切，并且分别属于两个小团体cout<<vertexv-1<<""<<vertexk<<""/输出桥接人结点的值DFS2(k+1,n);/找下一个if(v<=n)DFS2(v+1,

26、n);/王函数测试刚刚的Mgraph类中的各种成员函数是否编写正确，完成要求的功能。voidmain()cout<<"|欢迎使用社会网络分析系统"<<endl;intn,e,m;/n总人数，e总关系数，m某个人员的数字代码cout<<"请输入该社会网络总人数："cin>>n;char*a=newcharn;/a是指针，a的值是新建数组的首地址，a0,a1等cout<<"请依次输入人员名称："for(inti=0;i<n;i+)cin>>ai;cout<

27、<"请输入该社会网络的关系总数："cin>>e;Mgraph<char>G(a,n,e);cout<<"以下是该社会网络对应的邻接矩阵：G.PrintGraph();"<<endl;cout<<"*G.centre(n);G.huoyue(n);G.bianyuan(n);社会网络分析中*:"<<endl;cout<<"G.DFS(0,n);cout<<endl;cout<<"，小团体是："，

28、联系小团体的桥接人物是："G.DFS2(1,n);cout<<endl;n.cout<<"请输入一个人员的数字代码(用于查找该人员的交往圈子)cin>>m;G.quanzi(m);五、调试分析(包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会)问题&改进&补充:【问题1】：小团体和桥接人的理解与定义小团体：小团体就是由交往比较密切的一群人构成的，因此要设一个域值，email数据(权值)超过这个域值才能算交往密切；一个人不能单独构成一个小团体，小团体至少要2个成员组成。桥接人：桥接人就是联系两个小团体

29、的中间人，也就是说一个小团体可以通过对应的桥接人和另外一个小团体取得联系，桥接人分属于两个不同的团体。【问题2】：参数传递问题目的是在一个成员函数里调用另一个成员函数中的数据，一开始想到的是将代码段直接复制，但考虑到效率的问题，没有使用；然后想到了利用全局变量，但又觉得不妥；后来问了老师，老师建议我使用参数传递的方法，将需要的数据带回。于是做了如下修改：主函数中，增加charteam2020;并将G.DFS(0);改成G.DFS(0,n,team);使DFS查找小团体的函数中，可以使用主函数中的数据n总人数；使桥接人的函数中，可以使用DFS查找小团体的函数中的二维数组：team202010【问

30、题3】：递归调用中的数据存储为了实现桥接人的查找，要将小团体储存到一个二维数组中，在递归调用中存入数组真的不是一件简单的事，初始化数组的下标就是一件很麻烦的事情，因为递归调用每一次都会调用函数本身，若在函数体里面初始化数组下标的话，每调用一次，就会归零。解决方法：使用参数传递，将数组下标作为两个参数，每次调用时都将其传回，这样可以保证数组下标有效完成计数的功能。主函数中，将G.DFS(0,n,team);改成G.DFS(0,n,team,0,0)头文件中，改成voidDFS(intv,intn,charteam2020,inti,intj)【改进1】：createHW构建有向网中，原本老师PP

31、T上演示的是：arcij=1;arcji=1;之后改进为：arci-1j-1=1;arcj-1i-1=1;改进原因：按照原来的写法，输入两个人员之间的关系(顶点与顶点之间的边)要从0开始，由于和日常生活的数数习惯不同，因此加以改进，使之从1开始，方便使用。【改进2】：查找交往圈子中，原本应该是：if(arcvj!=INFINITY|arcjv!=INFINITY)需要改为:if(arcv-1j!=INFINITY|arcjv-1!=INFINITY)改进原因：由于改进1的影响，主函数中要求用户输入一个人员的数字代码，查找该人员的交往圈子时，用户也是从1开始数的，为了使程序显示正确，需要将下标v

32、改成v-1。【改进3】：存放小团体的数组其实不是必要的之前一直在纠结递归调用中存放数组的问题，但突然7号早上想到另一个更省事儿的方法，用排除法找桥接人！换个角度来看桥接人，就是分属于两个小团体，之间有联系但是联系不密切，另外，桥接人也不能是边缘人物。于是做了如下简化改进：主函数中，将G.DFS(0,n,team,0,0);改成GDFS(0,n);头文件中，改成voidDFS(intv,intn)【补充1】：补充没有核心人物或者没有活跃人物或者没有边缘人物的情况。一开始也没有想的这么全面，经过多次测试后发现这几种情况也是存在的，原来的程序在这种情况下显示的是空白，因此加以改进了一下一一增加了co

33、unt计数器，如果一个人物都没有的话，就输出“无”。算法的时间空间复杂性分析1 .本设计中算法的时间复杂度分为三类：11O(1)ADD计算人员间两两间联系数O(n)Mgraph构造函数O(n2)CreateHW构建有向网、PrintGraph输出邻接矩阵、centre核心人物、huoyue活跃人物、bianyuan边缘人物、quanzi查找交往圈子、BY判断边缘人物、DFS查找小团体、DFS2查找桥接人2 .本设计中算法的空间复杂度为：O(1)心得体会：一开始选题的时候，就觉得这个题目很有趣，尽管它的难度系数比较高，但我还是义无反顾地选择了它一一社会网络分析系统的设计和实现。图这一章老师讲的没

34、有单链表和二叉树那样细致，因为快到期末了课时很紧张，但做相关实验的时候，我就对图这部分的内容产生了浓厚的兴趣，因为社交网络和我们的生活比较贴切，图的应用在类似人人、微信朋友圈的社交网络中都会用到。自从我做完了上一个大作业，多余的两天半时间我就开始着手做这个课程设计了，一开始选择了使用无向图，成功完成了除小团体和桥接人之外的所有功能，但等到第一次课程设计上课的时候，和老师探讨了小团体和桥接人的查找方法后，发现一开始就选错了图的模型，应该选择有向网！之前的代码也要全部推翻重来，顿时觉得压力好大。好在回到寝室后的一整个下午加上一整个晚上的效率很高，终于将实现对email数据的预处理、建立社会网络的邻

35、接矩阵、找出社会网络中核心人物、活跃人物和边缘人物的函数都完成了。但对于小团体和桥接人的定义还是比较模糊的，于是第二次上课程设计的时候，详细咨询了老师。之后大量的时间都花在设计小团体和桥接人上了。期间也碰到了很多问题，通过自己调试修改、上网查阅资料、课上课下咨询老师，者B得到了解决。通过这次数据结构课程设计，我对之前学习的C+内容更加熟悉了，更好地掌握与理解了模板的使用、二维数组、参数传递、函数调用等内容；对数据结构这门课程也有了更进一步的学习与掌握，处理问题的思路与方法也有所拓宽，能理解与运用图的相关知识解决实际问题在老师的指导下，不仅独立完成了社会网络分析系统的设计和实现，还从老师那里学到

36、了很多书上没有的技巧，比如C+程序调试中所使用“断点”调试方法，之前我是完全不知道的。通过这次课程设计，在这短短的5天中，我感觉收获颇多！六、测试结果七、附录：程序设计源代码#include<iostream.h>#include<stdlib.h>12#include<string.h>constintmaxsize=100;constintINFINITY=0;最大值无穷template<classT>classMgraphpublic:Mgraph(Ta口,intn,inte);/构造函数，a口结点数组，n顶点个数，e边数voidPrint

37、Graph();/输出邻接矩阵voidcentre(intn);/核心人物成员函数voidhuoyue(intn);活跃人物成员函数voidbianyuan(intn);边缘人物成员函数voidquanzi(intv);查找交往圈子函数intADD(ints,intt);计算人员两两间联系数intBY(intn);voidDFS(intv,intn);/查找小团体函数(深度优先遍历)voidDFS2(intv,intn);/查找桥接人函数(深度优先遍历)private:Tvertexmaxsize;存放顶点intarcmaxsizemaxsize;/存放边intvertexnum,arcnum

38、;顶点数，边数voidCreateHW(Ta口,intn,inte);/构建无向图int*visited;/Mgraph构造函数template<classT>Mgraph<T>:Mgraph(Ta,intn,inte)visited=newintvertexnum;for(inti=0;i<vertexnum;i+)visitedi=0;CreateHW(a,n,e);/创建/CreateHW构建有向网template<classT>voidMgraph<T>:CreateHW(Ta,intn,inte)intw;/权值vertexnum

39、=n;顶点数arcnum=e;边数inti,j,k;cout<<"注意！请将人名对应到数字代码输入"<<endl;cout<<"输入格式为：人员1人员2权值"<<endl;for(i=0;i<vertexnum;i+)13vertexi=ai;/顶点数组赋初值(放入一维数组)for(i=0;i<vertexnum;i+)初始化邻接矩阵for(j=0;j<vertexnum;j+)arcij=0;for(k=0;k<arcnum;k+)/依次输入每一条边，并修改邻接矩阵的相应元素w权值

40、cout<<“请输入第"<<k+1<<"条边:"；cin>>i>>j>>w;/ij边依附的两个顶点的序号，arci-1j-1=w;/置有边标志，存放权值/PrintGraph输出template<classT>voidMgraph<T>:PrintGraph()inti,j;for(i=0;i<vertexnum;i+)for(j=0;j<vertexnum;j+)cout<<arcij<<'t'cout<<endl;/centre核心人物temp