中北大学
数据结构
课程设计说明书
20##年12月19日
1 设计目的：
《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的：
n 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；
n 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
n 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
2设计内容和要求
设计内容：
(1) 采用合适的存储结构来创建图，并实现图的遍历；
（2）计算图的最小生成树，求联通分量
设计要求：
（1）先任意创建一个图；
（2) 图的DFS,BFS的递归和非递归算法的实现
（3) 最小生成树（两个算法）的实现，求连通分量的实现
（4) 要求用邻接矩阵、邻接表、十字链表多种结构存储实现
3．本设计所采用的数据结构：
本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先遍历。
4.1 详细设计思想
这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。
因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。
4.3 核心代码
#include <iostream>
#include <malloc.h>
using namespace std;
#define int_max 10000
#define inf 9999
#define max 20
//…………………………………………邻接矩阵定义……………………
typedef struct ArcCell22
{
int adj;
char *info;
}ArcCell,AdjMatrix[20][20];
typedef struct
{char vexs[20];
AdjMatrix arcs;
int vexnum,arcnum; //有向图的当前顶点数和弧数
}MGraph_L;
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int localvex(MGraph_L G,char v)//返回V的位置
{int i=0;
while(G.vexs[i]!=v)
{ ++i;
}
return i;}
int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表示
{char v1,v2;
int i,j,w;
cout<<"…………创建无向图…………"<<endl<<"请输入图G顶点和弧的个数:(4 6)不包括"<<endl;
cin>>G.vexnum>>G.arcnum;
for(i=0;i!=G.vexnum;++i)
{cout<<"输入顶点"<<i<<endl;
cin>>G.vexs[i];}
for(i=0;i!=G.vexnum;++i)
for(j=0;j!=G.vexnum;++j)
{ G.arcs[i][j].adj=int_max;
G.arcs[i][j].info=NULL;
}
for(int k=0;k!=G.arcnum;++k)
{ cout<<"输入一条边依附的顶点和权:(a b 3)不包括"<<endl;
cin>>v1>>v2>>w;//输入一条边依附的两点及权值
i=localvex(G,v1);//确定顶点V1和V2在图中的位置
j=localvex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=w;
}
cout<<"图G邻接矩阵创建成功！"<<endl;
return G.vexnum;
}
void ljjzprint(MGraph_L G)
{ int i,j;
for(i=0;i!=G.vexnum;++i)
{
for(j=0;j!=G.vexnum;++j)
cout<<G.arcs[i][j].adj<<" ";
cout<<endl;
}
}
int visited[max];//访问标记
int we;
typedef struct arcnode//弧结点
{int adjvex;//该弧指向的顶点的位置
struct arcnode *nextarc;//弧尾相同的下一条弧
char *info;//该弧信息
}arcnode;
typedef struct vnode//邻接链表顶点头接点
{ char data;//结点信息
arcnode *firstarc;//指向第一条依附该结点的弧的指针
}vnode,adjlist;
typedef struct//图的定义
{ adjlist vertices[max];
int vexnum,arcnum;
int kind;
}algraph;
//…………………………………………队列定义……………………
typedef struct qnode
{int data;
struct qnode *next;
}qnode,*queueptr;
typedef struct
{ queueptr front;
queueptr rear;
}linkqueue;
//………………………………………………………………………
typedef struct acr
{ int pre;//弧的一结点
int bak;//弧另一结点
int weight;//弧的权
}edg;
int creatadj(algraph &gra,MGraph_L G)//用邻接表存储图
{ int i=0,j=0;
arcnode *arc,*tem,*p;
for(i=0;i!=G.vexnum;++i)
{ gra.vertices[i].data=G.vexs[i];
gra.vertices[i].firstarc=NULL;
}
for(i=0;i!=G.vexnum;++i)
{ for(j=0;j!=G.vexnum;++j)
{ if(gra.vertices[i].firstarc==NULL)
{ if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
{ arc=(arcnode *)malloc(sizeof(arcnode));
arc->adjvex=j;
gra.vertices[i].firstarc=arc;
arc->nextarc=NULL;
p=arc;
++j;
while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
{ tem=(arcnode *)malloc(sizeof(arcnode));
tem->adjvex=j;
gra.vertices[i].firstarc=tem;
tem->nextarc=arc;
arc=tem;
++j;
}
--j;
}
}
else
{ if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
{
arc=(arcnode *)malloc(sizeof(arcnode));
arc->adjvex=j;
p->nextarc=arc;
arc->nextarc=NULL;
p=arc;
}
}
}
}
gra.vexnum=G.vexnum;
gra.arcnum=G.arcnum;
/*for(i=0;i!=gra.vexnum;++i)
{ arcnode *p;
cout<<i<<" ";
p=gra.vertices[i].firstarc;
while(p!=NULL)
{ cout<<p->adjvex;
p=p->nextarc;
}
cout<<endl;
}*/
cout<<"图G邻接表创建成功！"<<endl;
return 1;
}
void adjprint(algraph gra)
{ int i;
for(i=0;i!=gra.vexnum;++i)
{ arcnode *p;
cout<<i<<" ";
p=gra.vertices[i].firstarc;
while(p!=NULL)
{ cout<<p->adjvex;
p=p->nextarc;
}
cout<<endl;
}
}
int firstadjvex(algraph gra,vnode v)//返回依附顶点V的第一个点
//即以V为尾的第一个结点
{ if(v.firstarc!=NULL)
return v.firstarc->adjvex;
}
int nextadjvex(algraph gra,vnode v,int w)//返回依附顶点V的相对于W的下一个顶点
{ arcnode *p;
p=v.firstarc;
while(p!=NULL&&p->adjvex!=w)
{ p=p->nextarc;
}
if(p->adjvex==w&&p->nextarc!=NULL)
{ p=p->nextarc;
return p->adjvex;
}
if(p->adjvex==w&&p->nextarc==NULL)
return -10;
}
int initqueue(linkqueue &q)//初始化队列
{ q.rear=(queueptr)malloc(sizeof(qnode));
q.front=q.rear;
if(!q.front)
return 0;
q.front->next=NULL;
return 1;
}
int enqueue(linkqueue &q,int e)//入队
{ queueptr p;
p=(queueptr)malloc(sizeof(qnode));
if(!p)
return 0;
p->data=e;
p->next=NULL;
q.rear->next=p;
q.rear=p;
return 1;
}
int dequeue(linkqueue &q,int &e)//出队
{ queueptr p;
if(q.front==q.rear)
return 0;
p=q.front->next;
e=p->data;
q.front->next=p->next;
if(q.rear==p)
q.rear=q.front;
free(p);
return 1;
}
int queueempty(linkqueue q)//判断队为空
{ if(q.front==q.rear)
return 1;
return 0;
}
void bfstra(algraph gra)//广度优先遍历
{ int i,e;
linkqueue q;
for(i=0;i!=gra.vexnum;++i)
visited[i]=0;
initqueue(q);
for(i=0;i!=gra.vexnum;++i)
if(!visited[i])
{ visited[i]=1;
cout<<gra.vertices[i].data;
enqueue(q,i);
while(!queueempty(q))
{ dequeue(q,e);
// cout<<" "<<e<<" ";
for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.vertices[e],we))
{ if(!visited[we])
{
visited[we]=1;
cout<<gra.vertices[we].data;
enqueue(q,we);
}
}
}
}
}
int dfs(algraph gra,int i);//声明DFS
int dfstra(algraph gra)
{ int i,j;
for(i=0;i!=gra.vexnum;++i)
{ visited[i]=0;
}
for(j=0;j!=gra.vexnum;++j)
{ if(visited[j]==0)
dfs(gra,j);
}
return 0;
}
int dfs(algraph gra,int i)
{ visited[i]=1;
int we1;
// cout<<i<<visited[i]<<endl;
cout<<gra.vertices[i].data;
// cout<<endl;
for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we))
{
// cout<<we<<visited[we]<<endl;
we1=we;
// cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;
if(visited[we]==0)
// cout<<
dfs(gra,we);//<<endl;
// cout<<i<<we1<<endl;
we=we1;
// cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;
}
return 12;
}
int bfstra_fen(algraph gra)//求连通分量
{ int i,j;
for(i=0;i!=gra.vexnum;++i)
{ visited[i]=0;
}
for(j=0;j!=gra.vexnum;++j)
{ if(visited[j]==0)
{
dfs(gra,j);
cout<<endl;
}
}
return 0;
}
typedef struct
{ int adjvex;
int lowcost;
}closedge;
/*int minimum(closedge *p);
int minispantree(MGraph_L G,char u)
{ int k,j,i;
closedge closedge_a[20];
k=localvex(G,u);
// cout<<k<<endl;
for(j=0;j!=G.vexnum;++j)
{ if(j!=k)
{ closedge_a[j].adjvex=u;
closedge_a[j].lowcost=G.arcs[k][j].adj;
}
for(i=1;i!=G.vexnum;++i)
{ k=minimum(closedge_a);
cout<<k;
cout<<closedge_a[k].adjvex<<" "<<G.vexs[k]<<endl;
closedge_a[k].lowcost=0;
for(j=0;j!=G.vexnum;++j)
if(G.arcs[k][j].adj<closedge_a[j].lowcost)
{ closedge_a[j].adjvex=G.vexs[k];
closedge_a[j].lowcost=G.arcs[k][j].adj;
}
}
}
return 0;
}
int minimum(closedge *p)
{ int s=10000;
for(;p!=NULL;++p)
{ if(s>p->lowcost)
s=p->lowcost;
}
return s;
}*/
int prim(int g[][max],int n) //最小生成树PRIM算法
{ int lowcost[max],prevex[max]; //LOWCOST[]存储当前集合U分别到剩余结点的最短路径
//prevex[]存储最短路径在U中的结点
int i,j,k,min;
for(i=2;i<=n;i++) //n个顶点，n-1条边
{ lowcost[i]=g[1][i]; //初始化
prevex[i]=1; //顶点未加入到最小生成树中
}
lowcost[1]=0; //标志顶点1加入U集合
for(i=2;i<=n;i++) //形成n-1条边的生成树
{min=inf;
k=0;
for(j=2;j<=n;j++) //寻找满足边的一个顶点在U,另一个顶点在V的最小边
if((lowcost[j]<min)&&(lowcost[j]!=0))
{min=lowcost[j];
k=j;
}
printf("(%d,%d)%d\t",prevex[k]-1,k-1,min);
lowcost[k]=0; //顶点k加入U
for(j=2;j<=n;j++) //修改由顶点k到其他顶点边的权值
if(g[k][j]<lowcost[j])
{lowcost[j]=g[k][j];
prevex[j]=k;
}
printf("\n");
}
return 0;
}
int acrvisited[100];//kruscal弧标记数组
int find(int acrvisited[],int f)
{while(acrvisited[f]>0)
f=acrvisited[f];
return f;
}
void kruscal_arc(MGraph_L G,algraph gra)
{ edg edgs[20];
int i,j,k=0;
for(i=0;i!=G.vexnum;++i)
for(j=i;j!=G.vexnum;++j)
{if(G.arcs[i][j].adj!=10000)
{edgs[k].pre=i;
edgs[k].bak=j;
edgs[k].weight=G.arcs[i][j].adj;
++k;
}
}
int x,y,m,n;
int buf,edf;
for(i=0;i!=gra.arcnum;++i)
acrvisited[i]=0;
for(j=0;j!=G.arcnum;++j)
{m=10000;
for(i=0;i!=G.arcnum;++i)
{if(edgs[i].weight<m)
{ m=edgs[i].weight;
x=edgs[i].pre;
y=edgs[i].bak;
n=i;
}
}
// cout<<x<<y<<m;
// cout<<endl;
buf=find(acrvisited,x);
edf=find(acrvisited,y);
// cout<<buf<<" "<<edf<<endl;
edgs[n].weight=10000;
if(buf!=edf)
{acrvisited[buf]=edf;
cout<<"("<<x<<","<<y<<")"<<m;
cout<<endl;
}
}
}
void main()
{ algraph gra;
MGraph_L G;
int i,d,g[20][20];
char a='a';
d=creatMGraph_L(G);
creatadj(gra,G);
vnode v;
cout<<endl<<"……####注意：若该图为非强连通图(含有多个连通分量)时"<<endl
<<" 最小生成树不存在,则显示为非法值。"<<endl<<endl;
cout<<"…………………菜单……………………"<<endl<<endl;
cout<<"0、显示该图的邻接矩阵……………………"<<endl;
cout<<"1、显示该图的邻接表……………………"<<endl;
cout<<"2、深度优先遍历…………………………"<<endl;
cout<<"3、广度优先遍历…………………………"<<endl;
cout<<"4、最小生成树PRIM算法…………………"<<endl;
cout<<"5、最小生成树KRUSCAL算法………………"<<endl;
cout<<"6、该图的连通分量………………………"<<endl<<endl;
int s;
char y='y';
while(y='y')
{cout<<"请选择菜单："<<endl;
cin>>s;
switch(s)
{case 0:
cout<<"邻接矩阵显示如下："<<endl;
ljjzprint(G);
break;
case 1:
cout<<"邻接表显示如下："<<endl;
adjprint(gra);
break;
case 2:
cout<<"广度优先遍历：";
bfstra(gra);
cout<<endl;
break;
case 3:
for(i=0;i!=gra.vexnum;++i)
{visited[i]=0;
}
cout<<"深度优先遍历：";
dfstra(gra);
cout<<endl;
break;
case 4:
for(i=0;i!=G.vexnum;++i)
for(int j=0;j!=G.vexnum;++j)
g[i+1][j+1]=G.arcs[i][j].adj;
cout<<"prim:"<<endl;
prim(g,d);
break;
case 5:
cout<<"kruscal:"<<endl;
kruscal_arc(G,gra);
break;
case 6:
cout<<"连通分量:";
bfstra_fen(gra);
break;
}
cout<<endl<<"是否继续？y/n:";
cin>>y;
if(y=='n')
break;
}
}
5．编译运行
6.课程设计心得及存在问题
课程设计的过程是艰辛的，但是收获却是很大的。这次课程设计我主要是应用以前学习的数据结构与面向对象程序设计知识，综合起来才完成了这个程序，虽然程序很小，但是付出却是艰辛的。
首先，综合课程设计让我把以前学习到的知识得到巩固和进一步的提高认识，对已有知识有了更进一步的理解和认识，再次，我在课程设计中碰到了很多的问题，我通过查阅相关书籍，资料，通过自己钻研，以及周围同学的帮助使问题得以逐一解决，在此过程中让我认识到了自己对以前所学知识的不足方面。
图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（即其孩子节点）相关，但只能和上一层中一个元素（即其双亲节点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，图的应用极为广泛，特别是近年来的迅速发展，已深入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先遍历。
当然，通过这次课程设计，我也发现了自身的很多不足之处，在以后的学习中，我会不断的完善自我，不断进取，能使自己在编程这方面有一个大的发展。