数据结构课程设计报告
---构件标识系统
学院：软件学院
专业：软件工程
年级 ***
姓名：***
学号：***
一、系统开发平台
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系统边界：
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算法，从输入的遍历顶点开始，应用队列和数组实现图的构造；并且在图中的编辑框中显示构件的个数和各构件的组成元素（顶点）。
七、功能模块
7.1功能模块
1.输入数据，包括图的各顶点，各边以及生成图的开始顶点（根据BFS算法开始遍历的顶点）；
2图形显示输入的的数据所构成的图，并用不同的颜色标识子连通图，即图的不同构件；
3.显示图的构件的个数和组成各个构件的顶点。
7.2 界面设计
八、测试和运行
1. 输入顶点数据abcdeae，弹出窗口如下：
2. 输入边为abba，弹出窗口如下：
3.不输入数据， 弹出提示对话框如下：
3. 输入俩个遍历顶点是，弹出窗口如下：
4. 输入顶点：abcde 边为：aa ；开始遍历顶点：a 如下：
开始遍历顶点为b时 如下：
5. 输入正确的数据，顶点为abcd， 边为abacad，遍历顶点为c窗口如下：
开始遍历顶点为a，如下：
6. 输入顶点为abcdef， 边为abacbcdedf 开始遍历的顶点为a如下图形界面：
九、总结
经过不到俩周的紧张的数据结构的课程设计，我学到了许多东西也深深体会到了做程序员的不易。从刚开始对课程的迷茫，不知道要怎么做，感觉无从下手到后来慢慢懂得了如何下手，这个过程是艰难的，但结果却是喜悦的，但是事情总是没有我们想的那样简单，问题接踵而来，对于我做的课程设计来说，那便是在界面上显示图形，查了好多资料都没有实例可供参考，最终不得不自己硬着头皮使劲想，才把代码写出来，可问题又来了，运行时出现了错误，在经过了n多遍的检查后才发现错误，改正错误。可是尽管过程如此艰难，但是当图形显示出来的那一刻，心里的喜悦却是无法言喻的，功夫不负有心人的感觉。同时我也明白了做好一个系统首先要做好的就是需求分析，包括数据需求和系统需求，这关系着你后来的设计功能是否满足要求以及设计的系统的强大性，这些东西我以前是不怎么会提前考虑的，总是直接下手代码，但是实践证明这个分析必不可少，它可以防止你写程序时，误入错误的方向。总之，有付出就有回报，你不逼自己一把，永远不知道自己有多优秀！话说回来，系统还有许多不足之处，这就需要以后学习更多的知识来弥补这个缺憾，争取做到最好！
附：参考文献
Visual C++ 从入门到精通；
Visual C++ 实践指导教程。
附：程序清单(部分)
typedef enum{unvisited,visited}VisitIf;
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;
AMLGraph CreatGraph( CString vex,CString ege)
{
AMLGraph G;
int i,j,k,cur=0; int m=-1;
VertexType va,vb;
G.vexnum= vex.GetLength();
G.edgenum = (ege.GetLength())/2;
EBox *p;
for(i=0;i<G.vexnum;++i)/* 构造顶点向量 */
{
G.adjmulist[i].data = vex.GetAt(i);
G.adjmulist[i].firstedge = 0;
}
for(k=0;k<G.edgenum;k++) /* 构造表结点链表 */
{
va=ege.GetAt(++m);
vb=ege.GetAt(++m);
i=LocateVex(G,va); /* 一端 */
j=LocateVex(G,vb); /* 另一端 */
p=(EBox*)malloc(sizeof(EBox));
p->mark=unvisited; /* 设初值 */
p->ivex=i;
p->jvex=j;
p->ilink=G.adjmulist[i].firstedge; /* 插在表头 */
G.adjmulist[i].firstedge=p;
p->jlink=G.adjmulist[j].firstedge; /* 插在表头 */
G.adjmulist[j].firstedge=p; /*插入j链表尾部*/
}
return G;
}
int Jiucuo( CString vex, CString ege, CString kkd)//判断所输入数据的正确性
{
int dds = vex.GetLength();
int bs = ege.GetLength();
int ksdd = kkd.GetLength();
char * D = new char[dds];
char * B = new char[bs];
for(int i = 0; i<dds; i++ )
D[i]= vex.GetAt(i);
for (int j=0; j< bs; j++)
B[j]= ege.GetAt(j);
if(dds == 0|| bs ==0 || ksdd ==0)
{::MessageBox(NULL,_T("请输入数据"),_T("提示"),MB_OK);return ERROR;}
if(bs%2 !=0)
{::MessageBox(NULL,_T("请输入边的个数为偶数"),_T("提示"),MB_OK);return ERROR;}
if(ksdd >1)
{::MessageBox(NULL,_T("请输入一个遍历顶点"),_T("提示"),MB_OK);return ERROR;}
for(int m= 0; m<dds; m++)
{
char h = D[m];
for(int n= m+1; n<dds; n++)
if(D[n]==h) {::MessageBox(NULL,_T("请输入不同的顶点"),_T("提示"),MB_OK);return ERROR;}
}
for(int mm= 0; mm<bs; mm++)
{
char b = B[mm++];
char k = B[mm];
for(int jj= mm+1; jj<bs; jj++)
{
char a = B[jj] ;
char c = B[++jj];
if(a==b&&c==k || a==k&& c==b ) {::MessageBox(NULL,_T("请输入不同的边"),_T("提示"),MB_OK);return ERROR;}
}
}
for (int ii= 0; ii<bs; ii++)
{
int hh = B[ii];
int js = 0;
for(int xx = 0 ; xx< dds; xx++)
{
if(hh!=D[xx]) js++;
}
if(js ==dds )
{::MessageBox(NULL,_T("输入的边不正确，请输入图中顶点的边"),_T("提示"),MB_OK);return ERROR;}
}
return OK;
}
void Shuchu(AMLGraph &G, char s)//其中s 为图的顶点
{
int v,u,w,z;
int m=-1;
int mm = 0;
LinkQueue Q;
int n = G.vexnum;
for(v=0;v<G.vexnum;v++)
Visited[v]=0;
InitQueue(Q);
z=LocateVex(G,s);
for(v=0;v<G.vexnum;v++)
{ m++;
if(m>=1) {Goujian = Goujian + ";";}
if(!Visited[(v+z)%G.vexnum]) /* v尚未访问 */
{ mm++;
Visited[(v+z)%G.vexnum]=1;/* 设置访问标志为TRUE(已访问) */
Goujian = Goujian + G.adjmulist[(v+z)%G.vexnum].data;
EnQueue(Q,(v+z)%G.vexnum);
while(!QueueEmpty(Q)) /* 队列不空 */
{
DeQueue(Q,u);
for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data))
{
if(!Visited[w])
{
Visited[w]=1;
Goujian = Goujian + G.adjmulist[w].data;
EnQueue(Q,w);
}
}
}
}
}
itoa(mm,&s,10);
Geshu = s;
}
void BFShuatu(AMLGraph G,VertexType start)
{ /*从start顶点起,广度优先遍历图G*/
int v,u,w,z;
int m=-1;
int a = -1;
int b = -1;
LinkQueue Q;
int n = G.vexnum;
int *X= new int[n];
int *Y = new int[n];
int *DX = new int[n];//存放的坐标与每个顶点的位置相对应
int *DY = new int[n];
for(v=0;v<G.vexnum;v++)
Visited[v]=0; /* 置初值 */
InitQueue(Q);
z=LocateVex(G,start);
for(v=0;v<G.vexnum;v++)
{
m++;
CPen pen(PS_SOLID,1,RGB(50*m,0,0));
SelectObject(hdc,pen);
if(!Visited[(v+z)%G.vexnum]) /* v尚未访问 */
{
Visited[(v+z)%G.vexnum]=1;/* 设置访问标志为TRUE(已访问) */
EnQueue(Q,(v+z)%G.vexnum);
x0=660/6+(m*50);
y0=340/5;
x=x0; y=y0;
MoveToEx(hdc,x,y,NULL); //在当前结点和源结点用直线连接
LineTo(hdc,x0,y0);
X[++a]=x;
Y[a]=y;
DX[(v+z)%G.vexnum] = x0;
DY[(v+z)%G.vexnum] = y0;
Rectangle(hdc,x0-1,y0-1,x0+13,y0+19); //画框框
TextOut(hdc,x,y, &G.adjmulist[(v+z)%G.vexnum].data,1); //在当前坐标输出T->data
while(!QueueEmpty(Q)) /* 队列不空 */
{
DeQueue(Q,u);
x0=X[++b];
y0=Y[b];
int q =0;
for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data))
{
q++;
if(!Visited[w])
{
Visited[w] = 1;
EnQueue(Q,w);
if(x<=x0) x+=20*q;
else x-=20*q;
y += 10*q;
MoveToEx(hdc,x,y,NULL); //在当前结点和源结点用直线连接
LineTo(hdc,x0,y0);
X[++a]=x;
Y[a]=y;
DX[w]= x;
DY[w]= y;
Rectangle(hdc,x-1,y-1,x+13,y+19); //画框框
VertexType h = G.adjmulist[w].data;
TextOut(hdc,x,y, &h,1); //在当前坐标输出T->data
}
if(Visited[w])
{
int xz = DX[w];
int yz = DY[w];
MoveToEx(hdc,xz,yz,NULL);
LineTo(hdc,x0,y0);
}
}
}
}
}
DestroyQueue(Q);
/*销毁队列,释放其占用空间*/
}