山东大学数据结构课程设计报告样本.doc

数据构造课程设计报告

---构件标记系统

学院：软件学院
专业：软件工程
年级 ***
姓名：***
学号：***

一、系统开发平台
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算法，从输入遍历顶点开始，应用队列和数组实现图构造；并且在图中编辑框中显示构件个数和各构件构成元素（顶点）。
开始界面

依照错误类型弹出相应提示对话框
输入错误

输入图中边顶点和边

输入对的
将输入顶点存入数组中
输入对的

将输入边存入链表构造中，边顶点指向此顶点第一条边，此边作为此顶点第一条边

将图中各顶点初始化标记为0， m初始化为0

从开始顶点起按照输入顺序进入队列

是
该顶点标记否？

否

标记该顶点，m加一，如果m>1,CString类型shuju+= “;” ,变化本来画笔颜色，拟定本次循环源坐标位置，将位置存入数组中，画出矩形并将该数据写入框中

删除队列第一种数据，设为u； shuju+= u；得到与该顶点相连下一条边顶点

该顶点与否标记？

否
是

进入队列，标记该顶点，并变化坐标位置画图，与本次循环源坐标连线
不进入队列，得到此顶点坐标位置，与源坐标连线

是
队列与否为空？

否

图形化显示输入图，不同构件用不同颜色展示，并显示构件个数和各构件构成元素

结束演示

七、功能模块
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);
/*销毁队列,释放其占用空间*/

}