数据结构课程设计报告
---构件标识系统
学院：软件学院专业：软件工程年级 *** 姓名：学号：
*** *** 一、系统开发平台
1.1题目： 构件标识 1.2开发工具：VC++6.0 1.3语言：C++
1.3操作系统：Windows XP 或 Windows7系统
二、系统规划
2.1任务陈述：图是由非连通图和连通图构成的，非连通图又由几个独立的子连通图构成，每个子连通图称为一个构件，本系统需要将非连通图的子连通图进行标记构件，并图形化演示构件标识的过程。 2.2任务目标：
（1）根据所输入数据构造图，形成直观的图形；
（2）运用BFS算法将所输入数据构成的图进行标识，演示标识过程，并将不同构件的顶点标识成不同的颜色；
（3）输入错误弹出对话框提示； （4）使用多组测试数据证明结果正确。
三、系统定义
3.1系统边界：
显示组成各个不同的构件的顶点 只输入一个开始遍历的顶点 图形显示无向图 显示构件的个数，即图中子连通图的个数 输入不同的顶点数且不超过11个 按照输入的顶点数，输入正确个数的边 子连通图的颜色不同 3.2系统描述：
本系统是一个实现实际应用性很强的功能的系统。实际生活中，有很多方面需要对
一个大的系统按照其相互关联的关系进行小的分类，这需要建立一个模型，本系统抽象其为无向图的模型，实现对子连通图的标识。其中通过输入图中顶点数和边数以及开始遍历的顶点进行图的构造，图形显示无向图，并显示图的构件的个数及各不同构件的元素组成。
四、需求分析
4.1 数据结构需求： 输入为图中各顶点和各边（不用逗号和空格隔开，直接连接输入
为一行即可），还需要输入开始进行遍历的顶点；输出为输入数据所构成的无向图（即是根据BFS算法所输出的不同颜色标识的构件图）和构件的个数以及各构件的元素组成。
4.2 操作需求：首先输入顶点数，边数和各个顶点各个边以及开始遍历的顶点，输入完
成后点击BFS按钮将所输入的数据生成构件图在下边的图形界面显示，可以点击上一步或下一步按钮浏览生成过程。
4.3 系统需求说明:
（1）可供11个顶点以及最多55条边存储的空间； （2）以秒为单位的响应速度；
（3）能对数据输入的各种不同序列做出相应的响应。
五、数据结构设计
5.1 逻辑结构:
非线性结构，无向图由顶点和边构成，分为连通图和非连通图，非连通图又由几个小的子连通图构成，进行构件时，分别对图中的子连通图进行标识。
5.2 存储结构:
采用邻接多重链表结构存储数据，如下图所示：
六、算法设计
6.1抽象数据类型
ADT AMLGraph(无向图) {
数据对象: 具有相同特征的无向图中的顶点集和边；
typedef struct EBox{
VisitIf mark; (访问标记)
int ivex,jvex; (该边依附的两个顶点的位置 )
struct EBox *ilink,*jlink; (分别指向依附这两个顶点的下一条边 ) }EBox;
typedef struct{ VertexType data;
EBox *firstedge; ( 指向第一条依附该顶点的边 ) }VexBox;
typedef struct{
VexBox adjmulist[MAX_VERTEX_NUM];(存储顶点及其指针的数组)
int vexnum,edgenum; ( 无向图的当前顶点数和边数) }AMLGraph; 基本操作：
CreatGragh( CString X， CString Y) 操作结果：构造无向图；
int LocateVex(AMLGraph G,VertexType u)
操作结果：寻找顶点在图中的位置；
VertexType& GetVex(AMLGraph G,int v) 操作结果：返回v的顶点值
int FirstAdjVex(AMLGraph G,VertexType v) 操作结果：寻找v的第一个邻接顶点；
int NextAdjVex(AMLGraph G,VertexType v,VertexType w) 操作结果：返回v的(相对于w的)下一个邻接顶点； int MarkUnvisited(AMLGraph &G) 操作结果：标记边为unvisited；
int DeleteVex(AMLGraph &G,VertexType v) 操作结果：删除G中顶点v及其相关的边； void DestroyGraph(AMLGraph &G) 操作结果：销毁一个图；
}ADT抽象数据类型名称
6.2 算法思想流程图
运用邻接多重链表的存储方式，存储图的顶点和边，根据所输入的数据构成所需要的无向图，然后根据BFS算法，从输入的遍历顶点开始，应用队列和数组实现图的构造；并且在图中的编辑框中显示构件的个数和各构件的组成元素（顶点）。
输入错误 输入图中的边顶点和边 根据错误类型弹出相应的提示对话框 开始界面