数据结构矩阵处理

1、算法与数据结构课程设计 班 级: 姓 名:指导老师：2015年6月222015年7月3日 目录1设计方案.32实现过程33测试34使用说明.135难点与收获.136实现代码.137可改进的地方.25一 设计方案能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，选择相应的存储结构，设计出解决问题的有效算法，实现图的一些基本操作，此次设计主要需要解决对无向图，无向网，有向图，有向网的一些基本操作和应用，因此可以设计一个基于VC或VS的应用程序，数据可以从键盘输入，然后设计程序利用多级菜单实现各种功能。二 实现过程实现过程的主函数为：void main( )1 对无向图的基本操作及应

2、用的实现 创建无向图的邻接矩阵（void creat_mg(Mgraph G)） 创建无向图的邻接表 （void CreatAdjList(Graph* G)） 无向图的深度优先遍历 （void DFS(Graph *G, int i, int visited)） 无向图的广度优先遍历 （void BFS(Graph* G,int v,int visited)）2 对无向网的基本操作及应用的实现 创建无向网的邻接矩阵 （CreateNDNGraphics(Graphics &G)） 创建无向网的邻接表（CreateUDN(ALGraph &G)） 求最小生成树（Prim(int

3、 graphMAX, int n)）3 对有向图的基本操作及应用的实现 创建有向图的邻接矩阵（CreateDGraphics(Graphics &G)） 创建有向图的邻接表（CreateDG(ALGraph &G)） 拓扑排序（TopSort(Graphaa& g)）4 对有向网的基本操作及应用的实现 创建有向网的邻接矩阵（CreateDNGraphics(Graphics &G)） 创建有向网的邻接表（CreateUDN(ALGraphh &G, indegree indegree)） 关键路径 （CriticalPath(ALGraphh &

4、g, indegree indegree)） 单源最短路径（myDijstra(n,1)）三 测试 数据输入：从键盘输入操作对应的序号1. 最初入口界面2. 无向图：无向图的邻接矩阵：无向图的邻接表：无向图的深度优先遍历：无向图的广度优先遍历：3. 无向网的基本操作及应用无向网的邻接矩阵：无向网的邻接表：最小生成树：4. 有向图的基本操作及应用创建有向图的邻接矩阵：创建有向图的连接表有向图的拓扑排序;5. 有向网的基本操作及应用有向网的邻接矩阵：创建有向网的邻接表;有向网的关键路径：4.单源顶点路径最短问题：四 使用说明 总共有三级选择菜单，根据需要从键盘输入对应菜单序号，进入相应输入界面，输

5、入待测数据，对图或网进行相应的操作五 难点与收获用代码实现各种操作时，代码容易出现逻辑上的错，个人觉得这种错误易发现但比较难修改，比如，在实现图的深度优先遍历时，利用了递归函数（DFS(G,i,visited)），通过查找资料和看书，多次调试，在程序中实现调用，实现了对图的深度优先遍历。这次通过上机实习，我更加深入的学习了图和网的相关内容和掌握了图和网的一些基本操作，也学会有效利用基本调试方法，会找出程序代码中的错误并且修改，提高了自己发现问题和解决问题的能力，受益匪浅。六实现代码无向图：/=创建无向图（邻接表）=/void CreatAdjList(Graph* G) int i,j,k;e

6、dgenode * p1;edgenode * p2;cout<<"请输入无向图的顶点数和边数(如：2 1):"<<endl;cin>>G->vexnum>>G->arcnum;cout<<endl;cout<<"开始输入顶点表（如：1 2）"<<endl;for (i=1;i<=G->vexnum;i+)cin>>G->adjlistsi.vertex;G->adjlistsi.edgelink=NULL;cout<

7、<endl;cout<<"开始输入边表信息:"<<endl; cout<<endl;for (k=1;k<=G->arcnum;k+)cout<<"请输入边<Vi,Vj>对应的顶点序号（如：2 3）:"cin>>i>>j; cout<<endl;p1=new edgenode;p1->endver=j;p1->edgenext=G->adjlistsi.edgelink;G->adjlistsi.edgelink=p1

8、;p2=new edgenode;p2->endver=i;p2->edgenext=G->adjlistsj.edgelink;G->adjlistsj.edgelink=p2;/因为是无向图，所以有两次建立边表的过程void creat_mg(Mgraph G) int i,j,k; printf ("n请输入无向图的顶点数和边数，如(6,5)每次回车键输入："); scanf ("%d,%d",&n,&e); for (i=1;i<=n;i+) for (j=1;j<=n;j+)Gij=0; /将

9、邻接矩阵初始化 for (k=1;k<=e;k+) printf ("n请输入每条边的两个顶点编号，如(2,5)每次回车键输入:"); scanf ("%d,%d",&i,&j); Gij=1; Gji=1; int a,b; for (a=1;a<=n;a+) printf ("n"); for (b=1;b<=n;b+) printf ("%5d",Gab); printf ("n"); /-广度优先遍历-/void BFS(Graph* G,int v,i

10、nt visited)/从第v个顶点出发非递归地广度优先搜索遍历无向图G。QueueList *Q=new QueueList;Q->front=Q->rear=NULL; /初始化队列QEnQueue(Q,v); /V入队列while(Q->rear!=NULL)int e;DeQueue(Q, &e); /队头(指定的)元素出队并置值为ecout<<G->adjlistse.vertex<<" " /输出顶点信息visitede=1; edgenode* p=new edgenode;p=G->adjlist

11、se.edgelink; /指向第一条依附于该顶点的边的指针if(p)int m=p->endver; /该边所指向的顶点的位置if(m=0)EnQueue(Q,m); while(visitedm=0) p=p->edgenext; if(p=NULL)break;m=p->endver;EnQueue(Q,m);有向网，无向网，无向图的邻接矩阵构造;int CreateDGraphics(Graphics &G) / 构造一个有向图 printf("分别输入弧数、顶点数（用空格）:"); Info info = NULL; / 这里忽略info

12、信息 scanf("%d%d", &G.arcnum, &G.vexnum); / 先把邻接矩阵中的adj设置为0 for(int i = 0; i < G.vexnum; +i) for(int j = 0; j < G.vexnum; +j) G.arcij.adj = 0; / 扫描进入顶点元素 for(i = 0; i < G.vexnum; +i) printf("请依次输入顶点元素值:n"); scanf("%d", &G.vexsi); printf("输入完毕!n&q

13、uot;); / 输入弧信息 for(i = 0; i < G.arcnum; +i) printf("请输入具有邻接关系的顶点:n"); DataType d1, d2; scanf("%d%d", &d1, &d2); int p1 = LocateVex(G, d1); int p2 = LocateVex(G, d2); G.arcp1p2.adj = 1; printf("该有向图的邻接矩阵构造完毕"); return 1; / CreateDGraphics int CreateNDNGraphics

14、(Graphics &G) / 构造一个无向网 printf("分别输入弧数、顶点数（用空格）:n"); Info info = NULL; / 这里忽略info信息 scanf("%d%d", &G.arcnum, &G.vexnum); / 先把邻接矩阵中的adj设置为0 for(int i = 0; i < G.vexnum; +i) for(int j = 0; j < G.vexnum; +j) G.arcij.adj = 0; / 借用改值为最大值 / 扫描进入顶点元素 for(i = 0; i <

15、G.vexnum; +i) printf("请依次输入顶点元素值:n"); scanf("%d", &G.vexsi); printf("输入完毕!n"); / 输入弧信息 for(i = 0; i < G.arcnum; +i) printf("请输入具有邻接关系的顶点,以及他们的权重（如2 1 3）:n"); DataType d1, d2, d3; scanf("%d%d%d", &d1, &d2, &d3); int p1 = LocateVex(G

16、, d1); int p2 = LocateVex(G, d2); G.arcp1p2.adj = d3; / 因为是无向，所以对称设置 G.arcp2p1.adj = d3; printf("该无向网的邻接矩阵构造完毕"); return 1; / CreateNDNGraphics int CreateDNGraphics(Graphics &G) / 构造一个有向网 printf("分别输入弧数、顶点数（用空格）:n"); Info info = NULL; / 这里忽略info信息 scanf("%d%d", &

17、;G.arcnum, &G.vexnum); / 先把邻接矩阵中的adj设置为0 for(int i = 0; i < G.vexnum; +i) for(int j = 0; j < G.vexnum; +j) G.arcij.adj = 0; / 借用改值为最大值 / 扫描进入顶点元素 for(i = 0; i < G.vexnum; +i) printf("请依次输入顶点元素值:n"); scanf("%d", &G.vexsi); printf("输入完毕"); / 输入弧信息 for(i =

18、 0; i < G.arcnum; +i) printf("请输入具有邻接关系的顶点,以及他们的权重:n"); DataType d1, d2, d3; scanf("%d%d%d", &d1, &d2, &d3); int p1 = LocateVex(G, d1); int p2 = LocateVex(G, d2); G.arcp1p2.adj = d3; printf("该有向网的邻接矩阵构造完毕"); return 1; / CreateDNGraphics /邻接表建立无向网int Creat

19、eUDN(ALGraph &G) /* 邻接表建立无向网 */ int i,s,d,w; ArcNode *p, *q; printf("输入结点数目和边数（用空格）:"); scanf("%d%d",&G.vexnum,&G.arcnum); /* 输入结点数目和边数 */ getchar(); for(i=1; i<=G.vexnum; i+) /* 输入顶点 */ printf("输入顶点（每一个按回车键):"); scanf("%c",&G.verticesi.data

20、); /* 输入顶点 */ getchar(); G.verticesi.firstarc = NULL; /* 首先初始化为NULL */ for(i=1; i<=G.arcnum; i+) printf("依次输入每条边依附的顶点序号，权值（空格/每一个按回车键):"); scanf("%d%d%d",&s,&d,&w); /* 输入一条边依附的起点序号和终点序号 */ getchar(); p = (struct ArcNode *)malloc(sizeof(struct ArcNode); q = (struct

21、ArcNode *)malloc(sizeof(struct ArcNode); p->info = (InfoType *)malloc(sizeof(InfoType); q->info = (InfoType *)malloc(sizeof(InfoType); p->adjvex = d; /* 保存该弧所指向的顶点位置 */ q->adjvex = s; /* 保存该弧所指向的顶点位置 */ *(p->info) = w; /* 保存权值到一个结点里 */ *(q->info) = w; /* 保存权值到一个结点里 */ p->nextarc

22、 = G.verticess.firstarc; G.verticess.firstarc = p; q->nextarc = G.verticesd.firstarc; G.verticesd.firstarc = q; return OK; /prime算法最小生成树int graphMAXMAX; int Prim(int graphMAX, int n)/* lowcosti记录以i为终点的边的最小权值，当lowcosti=0时表示终点i加入生成树 */int lowcostMAX; /* msti记录对应lowcosti的起点，当msti=0时表示起点i加入生成树 */int

23、mstMAX; int i, j, min, minid, sum = 0; /* 默认选择1号节点加入生成树，从2号节点开始初始化 */for (i = 2; i <= n; i+)/* 最短距离初始化为其他节点到1号节点的距离 */lowcosti = graph1i; /* 标记所有节点的起点皆为默认的1号节点 */msti = 1; /* 标记1号节点加入生成树 */mst1 = 0; /* n个节点至少需要n-1条边构成最小生成树 */for (i = 2; i <= n; i+)min = MAXCOST;minid = 0; /* 找满足条件的最小权值边的节点mini

24、d */for (j = 2; j <= n; j+)/* 边权值较小且不在生成树中 */if (lowcostj < min && lowcostj != 0)min = lowcostj;minid = j;/* 输出生成树边的信息:起点，终点，权值 */printf("%c - %c : %dn", mstminid + 'A' - 1, minid + 'A' - 1, min); /* 累加权值 */sum += min; /* 标记节点minid加入生成树 */lowcostminid = 0; /*

25、更新当前节点minid到其他节点的权值 */for (j = 2; j <= n; j+)/* 发现更小的权值 */if (graphminidj < lowcostj)/* 更新权值信息 */lowcostj = graphminidj; /* 更新最小权值边的起点 */mstj = minid;/* 返回最小权值和 */return sum;/kraskal算法求最小生成树关键代码：for(i=0;i<t;i+) scanf("%d %d %d",&ai.m,&ai.n,&ai.d); /输入每条边的权值 qsort(a,t,s

26、izeof(a0),cmp); min=num=0; for(i=0;i<t && num<n-1;i+) for(k=ai.m;xk!=k;k=xk) /判断线段的起始点所在的集合 xk=xxk; for(g=ai.n;xg!=g;g=xg) /判断线段的终点所在的集合 xg=xxg; if(k!=g) /如果线段的两个端点所在的集合不一样 xg=k; min+=ai.d; num+; printf("最小生成树中加入边：%d %dn",ai.m,ai.n); printf("最小生成树的权值为：%dn",min); sys

27、tem("pause"); 有向图的拓扑排序：void TopSort(Graphaa& g) cout << "The topsort is:" <<endl; for (int i=0; i<g.vertexNum; i+) VertexNode& v = FindZeroIndegree(g); if (v.indegree!=NULL) cout << "The graph has cycle, can not do topsort"<<endl; / pr

28、int graph as topsort. cout<< v.data << " " / for each vertex w adjacent to v, -indegree adjVertexNode* padjv = v.list; while (padjv!=NULL) /！这个算法这里破坏了原图中的入度信息。最后入度均为1 g.VertexNodepadjv->adjVertexPosition.indegree-; padjv = padjv->next; /避免入度信息均为零FindZeroIndegree找到删除的顶点，将删

29、除的顶点入度置为1 v.indegree+; cout << endl;有向网关键路径：/求关键路径void CriticalPath(ALGraphh &g, indegree indegree) /G为有向网，输出G的各项关键活动 ArcNode *q; int gettop,k,j; int ee,el; /活动最早发生时间和最迟发生时间 TopologicalSort(g, indegree); vl=(int *)malloc( g.vexnum*sizeof(int) ); /事件最早发生时间数组 for(int i=0; i<g.vexnum; i+)

30、vli=veg.vexnum-1; /初始化 cout<<"ve:"<<endl; /输出ve for(i=0; i<g.vexnum; i+) cout<<vei<<" " cout<<endl; while(top2!=0) /出栈是求vl gettop=stack2top2-; for(q = g.verticesgettop.firstarc; q; q = q->nextarc) /求各顶点事件的最迟发生时间vl值 k=q->adjvex; if(vlk - q->info1 < vlgettop) vlgettop = vlk - q->info1; /for cout<<"vl:"<<endl; /输出vl for(i=0; i<g.vexnum; i+) cout<<vli<<" " cout<<endl; for(j=0; j<g.vexnum; j+) /求ee,el和关键活动 for(q = g.verticesj.firstarc; q; q = q->nextarc) k=q->adj