数据结构第二次课程设计

《数据结构第二次课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计课题名称用户对电影偏好的系统的设计和实现小组成员：林泓涛201225032余力鹏201225035宋勤宇201225018刘建悦201236050俄力哈力•加尔恒201225041提交日期2013.12.25一、课程设计背景介绍对电影的偏好调查可以看出消费者对电影消费的倾向，从而有利于各个网站根据用户的偏好进行调整定位。现抽取一定时间内有关用户对电影评价的数据，包含用户ID、电影名称、用户偏好以及评价日期。根据现有数据，构建无向图的连接矩阵，用无向图的边代表两点间的联系，并利用度的概念

2、，判断用户对电影的偏好，在图中找出连通子图，凡是属于不同连通子图的公共点都是桥接点，从而找出用户喜欢的电影类型。二、设计题目用户对电影偏好的系统的设计和实现2）输入的形式和输入值的范围1.以字符数据代表用户ID2.以整形数据代表用户观看的电影和偏好3.输入数值范围（1-100）3）输出的形式描述1.输出构建的邻接矩阵2.输出4）功能描述1.根据输入的数据构建无向图的连接矩阵，以无向图的边代表两点之间的联系2．利用度的概念，找出用户对电影的偏好（规定度数大于所有顶点数一半的为用户关注的电影，小于一半定点

3、数的为用户不关注的电影）3．利用子图，找出用户喜欢的电影类型。即在图中找出连通子图，凡是属于不同连通子图的公共点都是桥接点。三、概要设计1）抽象数据类型定义描述ADTGraphisData存放图中顶点（用户ID）的数组存放图中各顶点之间的边（用户关注的电影）的数组图中用户总数和电影总数标记数组OperationGraph初始化值：图中的用户/存放图中的数组/标志顶点访问的数组动作：选择操作类型，调用图的创建函数。createUG输入：图中的顶点数（图中的用户数），图中的顶点的边（用户的电影偏好的相互联

4、系）前置条件：构造函数调用功能：创建无向图输出：无后置条件：无向图建立Center输入：无前置条件：无向图已经建立功能：找出用户最关注的电影输出：用户最关注的电影后置条件：无Border输入：无前置条件：无向图的建立功能：找出用户不关注的电影输出：用户不关注的电影后置条件：无PrintGraph输入：无前置条件：无向图建立功能：输出邻接矩阵输出：输出邻接矩阵后置条件：无DFSTraverse输入：无前置条件：无向图的建立，对标志数组进行初始化为0功能：从指定的顶点开始深度遍历输出：深度遍历序列，找出指

5、定点的用户和电影的范围后置条件：无DFS输入：无前置条件：无向图的建立，重新对数组进行置0处理功能：从指定的顶点开始进行深度遍历输出：输出连通图的序列后置条件：对访问过的顶点置1Group输入：无前置条件：无向图的建立，已对访问过的顶点功能：从指定的顶点开始进行深度遍历输出：已标记为1的顶点后置条件：无2）功能模块设计（如主程序模块设计）1.主程序模块：连接各种功能的子模块，完成需要的操作和实现的功能。2.用户电影构建模块：按照相关步骤和要求构建无向图。3.用户最关注的电影模块：根据用户的输入，构建的

6、相关的无向图，由度的概念程序计算出用户最关注的电影。4.用户不关注的电影模块：根据用户的输入，构建相关的无向图，由度的概念程序计算出用户不关注的电影。3）模块层次调用关系图Main（）centerborderDFSDFSTraverseprintGraphGraph四、详细设计实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。1）对类的定义：templateclassGraph{public:Graph(Ta[],intn,inte);//构造函数，a[]表

7、示数组，表示顶点的个数，e表示边数voidcenter(intn);//声明用户最关注的电影函数voidprintGraph();//输出邻接矩阵voidDFSTraverse(intv);//对图进行深度优先遍历，找出某一点与电影的关系voidborder(intn);//用户不关注的电影函数函数voidDFS(intv);//对图的连通子图进行深度优先遍历，找出某一点与电影的关系private:Tvertex[maxsize];//顶点数组intarc[maxsize][maxsize];//边数

8、intvertexNum,arcNum;//定点数，边数voidcreateUG(Ta[],intn,inte);//构建无向图int*visited;//设置标志数组};成员函数：1）用户最关注的电影、用户不关注的电影templatevoidGraph::center(intn){vertexNum=n;inti,j;intk=0;intdm[maxsize]={0};for(i=0;i