《社会网络分析系统的设计和实现数据结构课程设计》由会员分享，可在线阅读，更多相关《社会网络分析系统的设计和实现数据结构课程设计（23页珍藏版）》请在金锄头文库上搜索。
1、上海电力学院数据结构（C+）课程设计题目: 综合实验16 社会网络分析系统的设计和实现(*)姓 名： XXX 学 号： 2012XXXX 院系： 计算机科学与技术学院 专业年级： 信息安全 2012XXX 2014年 07月 08日目 录一、 设计题目1二、需求分析11）运行环境（软、硬件环境）12）输入的形式和输入值的范围13）输出的形式描述14）功能描述15）测试数据2三、概要设计21）抽象数据类型定义描述22）功能模块设计（如主程序模块设计）53）模块层次调用关系图5四、详细设计6五、调试分析12 问题&改进&补充12 算法的时间空间复杂性分析14 心得体会14六、测试结果15七 、附录
2、：程序设计源代码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. 某条关系（人员数字代码 人员数字代码 权值）注：权值（1100）即email数据举例：总人数8个、人员名称A
3、BCDEFGH、人员数字代码12345678、关系总数15条、具体某一条关系1 2 9。3）输出的形式描述1. 该社会网络的邻接矩阵2. 该社会网络中的核心人物、活跃人物、边缘人物3. 该社会网络中的小团体、桥接人物4. 查找任何人的交往圈子4）功能描述 1. 对email数据进行预处理，利用数据结构课程中图中的理论，建立社会网络的邻接矩阵。2. 利用度的概念，找出社会网络中核心人物、活跃人物和边缘人物。3. 利用子图概念，分析社会网络的结构，找出小团体和联系小团体的桥接人物。4. 能查找任何人的交往圈子。5）测试数据三、概要设计1）抽象数据类型定义描述（对各类的成员及成员函数进行抽象描述，参
4、见书或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（交往圈子）输入：输入一个人员的数字代码（用于查找该人员的交往圈子）前置条件：有向网已经建立功能：查找交往圈子（与指定人物之间有边的人物就是与该人物有联系的，这些人就构成了一个交往圈子）。输出：输出指定人物的交往圈子后置条件：无u ADD（计算人员两两间的关系数）输入：无前置条件：有向网已经建立，给出两个人物的数字代码功能：计算指定人
7、员两两间的联系数并返回（为查找小团体、桥接人做准备）输出：返回指定人员两两间的联系数后置条件：无u BY（返回边缘人物数字代码）输入：无前置条件：有向网已经建立功能：找边缘人物并返回该人物数字代码（为查找小团体、桥接人做准备）输出：返回边缘人物的数字代码后置条件：无u DFS（小团体）输入：无前置条件：有向网、ADD函数、BY函数都已经建立，初始化顶点标记矩阵（全部置0）功能：查找小团体，从指定的顶点开始进行深度优先遍历（如果当前人物没有被访问过，并且也不是边缘人物，输出该人物；再从该人物开始进行深度遍历，如果找到与该人物交往密切的人物则输出，继续找下一个）输出：输出小团体后置条件：对访问过的
8、顶点置1u DFS2（桥接人）输入：无前置条件：有向网、ADD函数、BY函数都已经建立功能：查找桥接人，从指定的顶点开始进行深度优先遍历输出：两个小团体中，有联系，但没有达到域值的人物后置条件：无end ADT Mgraph2）功能模块设计（如主程序模块设计）1. 主程序模块：连接各种功能子模块，完成程序的基本操作实现功能2. 构造社会网络模块：按照要求构建有向网3. 输出邻接矩阵模块：根据用户输入的社会网络，输出该网络图的邻接矩阵4. 核心人物模块：根据用户输入的社会网络，计算得出该社会网络中的核心人物5. 活跃人物模块：根据用户输入的社会网络，计算得出该社会网络中的活跃人物6. 边缘人物模
9、块：根据用户输入的社会网络，计算得出该社会网络中的边缘人物7. 交往圈子模块：根据用户输入的社会网络，计算得出该网络中指定人物的交往圈子8. 人物两两联系数模块：根据用户输入的社会网络，返回指定人员两两间的联系数9. 判断边缘人物模块：根据用户输入的社会网络，返回边缘人物的数字代码10. 小团体模块：根据用户输入的社会网络，深度优先遍历得出该网络中的所有小团体11. 桥接人物模块：根据用户输入的社会网络，深度优先遍历得出小团体间的桥接人物3）模块层次调用关系图桥接人DFS2 小团体DFS 交往圈子quanzi边缘人物bianyuanMain( )Mgraph活跃人物huoyue核心人物cent
10、re输出邻接矩阵PrintGraph构建有向网CreateHW人员两两联系数ADD判断边缘人物BY 四、 详细设计实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。#include#include#includeconst int maxsize=100;const int INFINITY=0;/最大值无穷定义一个Mgraph类，用来实现基本功能：构造函数初始化值，根据用户输入的社会网络图构建有向网（邻接矩阵存储形式），查找该社会网络中的核心人物、活跃人物、边缘人物、小团体、桥接人物，查找任何人的交往圈子。templateclass Mgraphpublic: M
11、graph(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 DFS(int v,int n) ; /查找小团体函数（深度优先遍历） void DFS2(int v,in
12、t 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。templateMgraph:Mgraph(T a,int n,int e) visited=new intvertexnum;
13、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注意！请将人名对应到数字代码输入endl;cout输入格式为：人员1 人员2 权值endl;for (i=0; ivertexnum; i+) vertexi=ai;/顶点数组赋初值（放入一维数组）for (i=0; ivertexnum; i+) /初始化邻接矩阵for (j=0; jvertexnum; j+)arcij=0;
