《数据结构》大作业.docx
《《数据结构》大作业.docx》由会员分享，可在线阅读，更多相关《《数据结构》大作业.docx（19页珍藏版）》请在冰点文库上搜索。
《数据结构》大作业
2012－2013第1学期
数据结构大作业
名称：
基于聚类思想的数据划分
组长：
学号：
姓名：
专业：
信息管理与信息系统
成员：
学号：
姓名：
专业：
信息管理与信息系统
学号：
姓名：
专业：
信息管理与信息系统
学号：
姓名：
专业：
信息管理与信息系统
选课班级：
任课教师：
成绩：
评语：
教师签名：
批阅日期：
组长学号
姓名
班级
同组人
郑嘉豪、江根青、涂春潮
项目名称
基于聚类思想的数据划分
指导教师
李圣宏
完成日期
2012年12月19日
一、小组成员及其分工
1.XXX
需求分析、代码实现。
2.XXX
概要设计、调试分析。
3.XXX
需求分析、调试分析
4.XXX
详细设计、测试结果。
二、需求分析
2.1程序目标及项目介绍
本程序设计主要为解决科研项目财务指标区间划分问题。
该科研项目借用数据挖掘中关联分析技术来挖掘财务指标与舞弊之间所隐含的规则，从而达到预测企业财务报表舞弊与否的目的。
所以，指标区间的划分决定了最终所产生的规则的预测质量。
常用的区间划分技术有：
硬划分（如等区间划分）和软划分（如：
拐点划分、聚类划分等）。
其中，硬划分不需要考虑数据本身波动情况，简单方便；软划分则需依据数据自身特征进行划分，操作起来较硬划分复杂。
考虑到某些财务数据的对财务舞弊非常敏感，所以硬划分在该项目中显得先天不足。
因此，该科研项目选择软划分来进行指标区间的划分。
最常用的软划分技术是拐点划分，该技术依据数据整体的趋势（增减情况）来进行划分，但由于某些指标在很长一段区间内无拐点，所以对财务数据（某些对财务舞弊非常敏感）仅仅使用拐点划分也将存在一定的不足。
聚类划分是依据某一数据对象同其他数据对象之间的相似度来进行划分的，采用的是局部最优的思想，主要处理离散值。
所以，仅使用聚类来处理财务指标区间很显然不足。
正是基于以上两点考虑，此研究项目中采用拐点划分与聚类划分相结合的思想来处理财务数据，最终实现指标区间的合理划分。
2.2程序具体任务
此聚类划分程序主要功能是根据数据自身特征（波动情况,根据方差来判断）对给定的样本（某一财务指标下的N个样本数据）进行合理的离散化划分。
具体任务如下：
（1）对输入的数据进行排序（由小到大）；
（2）计算该组数据的方差；
（3）根据数据特征对数据进行分类（建立数组二叉树）；
（4）遍历该数组二叉树，并输出每个节点的数据元素。
考虑到0元素会占用空间，且不对区间划分不起任何作用，本程序将对0元素做单独处理（将其置后）。
输入要求：
本程序通过VisualC++I/O输入流输入“txt”格式文件。
输出要求：
输出最终划分类（树的节点）的个数，每个类里的具体元素。
三、概要设计
3.1此程序设计中所用到的数据类型
本程序根据需求最终建立了一棵数组二叉树（树的每个节点有一个数组组成），该树每个节点表示一个类，每个节点包含若干个数据元素，一个左孩子节点，一个右孩子节点。
节点结构如下：
typedefstructLnode{//定义本程序所需的节点类型
elemtypeelem[N];//该节点包括N个数据元素
intlog;//状态变量（该节点数据元素是否已排好序）
structLnode*min;//该节点的左孩子
structLnode*max;//该节点的右孩子
}Lnode,*linklist;
3.2主程序流程
分析该程序需要实现的功能，主程序流程如图3-1所示：
图3-1聚类划分流程图
3.3模块关系
3.3.1主函数对应关系
3.3.2minmax（）函数对应关系
3.3.3bianli（）函数对应关系
3.4各模块功能
3.4.1主函数模块
该模块实现文件的输入，并将输入的元素由小到大排序，同时将其中的0元素全部放到后面；然后，输出此时的节点并统计其元素个数；最后，对该类进行划分（即建立左右孩子树），并输出每一个节点以及统计每个节点元素个数。
3.4.2minmax（）模块
该模块主要功能是完成类的划分，通过判断该节点的方差来将其第一个元素或最后一个元素分别放到其左孩子树或者右孩子树中，然后又分别对其左右孩子做同样的处理，直到每一节点的方差都符合要求。
3.4.3bianli（）模块
该模块的功能是先序遍历该数组二叉树，并输出每个节点上的数据及其方差，同时统计其元素个数。
四、详细设计
4.1函数实现
（1）main（）伪代码：
============================================================================
输入输入“txt”格式的文件
Step1将其数据进行排序，并存储到根节点Q的数组data[N]中
Step2计算Q→data[N]的方差variance（Q→data）以及均值Mean（Q→data）
do
If（Mean（Q→data）-Q→data[0]>Q→data[Q→length-1]-Mean（Q→data））
Q→data[0]→Q→childl→data;//将Q中第一个元素投入其左孩子中
Else
Q→data[length-1]→Q→childr→data;//将Q中第一个元素投入其右孩子节点中
Adjustment（Q→data）//调整数组中数据为去除影响方差最大元素后数据
Q→length-=1;
while（variance（Q→data）<=Variance）;
step3（Q→childl）;//对节点左孩子节点进行步骤2的操作
step4（Q→childr）;//对节点右孩子节点进行步骤2的操作
step5bianli（Q）;//先序遍历树中节点,将聚类结果存放于数据库中
============================================================================
（2）init（）伪代码：
=====================================
Step1给链表分配Lnode个大小的空间
Step2分别置空左右孩子
Step3初始化数据元素，使其全部为0
======================================
（3）paixu（）伪代码：
==========================================================
Step1fori=1to最后一个元素do
Step2fori+1to最后一个元素do
Step3与第i个元素做比较，始终保持i位置元素最小
Step4endfor
Step5endfor
===========================================================
（4）fun（）伪代码：
=======================================================
Step1repeat
Step2从该节点的第一个元素开始寻找0元素
Step3for数值为0的元素开始to倒数第二个元素do
Step4用后一个元素覆盖前一个
Step5endfor
Step6until从该元素起，其后全部为0元素
=======================================================
（5）func（）伪代码：
==============================================
Step1repeat
Step2从该节点的第P个元素开始寻找0元素
Step3遇到非0退出循环，否则一直寻找
Step4untilP移到最后一个元素上
Step5判断P是否为最后一个元素序号
Step6是，则返回0
Step7否则，返回1
===============================================
（6）show（）伪代码：
=============================================
Step1处理该节点中的0元素
Step2repeat
Step3从该节点的第1个元素开始输出其值
Step4until遇到0元素
Step5统计该节点元素个数（即输出元素的个数）
Step6输出该节点的方差
=============================================
（7）E（）伪代码：
============================
Step1将数据由小到大排序
Step2对所有元素求和
Step3除以非0元素个数
Step4返回均值
============================
（8）SEE（）伪代码：
============================
Step1处理0元素
Step2利用公式求方差
Step3返回该组数据的方差
============================
（9）minmax（）伪代码：
====================================================
Step1判断该节点的方差与给定方差的大小关系
Step2do
Step3判断第一个数和最后一个数对方差的影响程度
Step4If第一个元素影响大
Step5将第一个元素投入其左孩子节点中
Step6Else
Step7将最后一个元素投入其右孩子节点中
Step8调整该组数据的方差
Step9数据长度减1
Step10while（variance（Q→data）<=Variance）;
Step11跳到其左孩子节点，从Step1开始处理其左孩子
Step12跳到其右孩子节点，从Step1开始处理其左孩子
=====================================================
（10）bianli（）伪代码：
==============================================
Step1输出根节点数组元素，包括统计其元素个数
Step2跳到其左孩子节点
Step3bianli（L->min）
Step4跳到其左孩子节点
Step5bianli（L->max）
==============================================
4.2函数调用关系
五、调试分析
5.1fun（）设计
在fun（）一开始的设计中，我们没有加判断条件funcc（a,p）==1，结果发现会陷入死循环，主要原因是当移到全是0元素的时候，a[p]==0总是满足。
于是我们便考虑设计一个判断其后是否全为0元素的函数，这样不仅克服了是循环，而且当数据中0元素非常多的时候，可以减少循环次数，提高程序效率。
5.2求方差
一开始，在方差SEE（）函数设计中，我们并没有单独构造求均值的函数，而是在循环中直接求该节点数组的均值，当测试指标数据为234份（全部实验数据）时，结果十分缓慢，主要原因是重复求了多次均值。
加入求均值的函数E（）时，只对该数组数据求了一次均值，所以速度提高了很多。
5.3划分的类的个数统计
在一开始设计输出指标区间被划分成多少时，将计数语句放在“cout<<"处理完毕"<对同一个节点处理N次被划分成N+1个区间段，但是当跳到对其孩子节点执行时，又增加了一次，每跳跃一次对增加一个区间段。
分析清楚后，将计数语句放到“minmax（L->min/max）”后边得到了正确结果。
5.4show（）中方差的计算及输出
一开始，输出语句直接写成“cout<<"，方差为：
"<考虑到以上几点，将语句写成“if（n==0）cout<<"，方差不存在"<0"<"<"<六、测试结果
6.1未经划分处理的数据输出
6.2基于方差的聚类划分处理
6.3先序遍历并输出该数组二叉树中的每一个节点
共得到：
21个类，其中17个节点（即类）有元素，4个节点（即类）没有元素。
七、大作业的认识
7.1对该大作业的认识
该次大作业程序设计来源于科研课题，其功能是实现数据区间的划分，采用的是数据挖掘中的聚类思想。
虽然，给程序设计代码不多，但其充分应用了数据结构的思想，将数据结构中的链表、树的构建及遍历思想充分的应用进来。
当然，由于该程序设计的函数较多，同时处理的数据量不是很大，所以并没有对每个函数进行优化，如其中的paixu（）函数，可以将其改成快速排序以提高运行效率。
快速排序的思想如下：
通过一趟排序将待排序记录分割成两个部分，其中一部分记录的关键字均比另一部分记录的关键字小，这可分别对这两部分记录继续进行排序，以达到整体序列有序。
7.1对数据结构课程的认识
通过这次大作业，我对数据结构有了新的认识，以前在学习《数据结构》这门课程时，老是觉得很难，也很缺少对它的兴趣。
但现在我觉得也不是很难了。
如果要想在《数据结构》方面有成就，必须多想多练习，同时多巩固巩固自己学到的C系列语言的知识。
当然这个过程也加强了我对学习C系列语言的热情，记得大一刚接触到C语言时，感觉有点枯燥，学完了感觉就没用到过，可是在完成此次任务的过程中突然又培养了自己对C系列语言的好奇，特别是对C++语言，这也让我决定在以后的学习中要更深入的去了解C语言，充分使其与数据结构相联系，从而提高自己的编程实力。
八、附录
程序文件名清单：
（1）输入文件:
“带划分数据1.txt”.
（2）intfuncc（elemtype*,int）;//判断数组第n位后（包含n）数据是否都是0
（3）voidshow（linklist）;//输出类中数据并计数
（4）voidinit（linklist&）;//初始化链表,并将数组元素全部置为0,同时修改状态变量为0（表示节点未处理）
（5）voidpaixu（linklist&）;//对节点数组中数据由小到大排序
（6）voidfun（elemtype*）;//将数组中0全部移到数组最后
（7）intfuncc（elemtype*a,intp）//判断数组第n位后（包含n）数据是否都是0
（8）elemtypeE（linklist）;//求均值，返回数组均值
（9）elemtypeSEE（linklist）;//求方差，返回数组方差
（10）voidminmax（linklist&）;//借用递归思想，建立数组二叉树
（11）voidbianli（linklist）;//先序遍历数组二叉树，并输出每个节点的数据
升级会员 