kechengsheji.zip_系统的设计

#include<stdlib.h> #include<stdio.h> #include "GraphSave.h" #include<iostream> using namespace std; CGraphSave::CGraphSave(CMenuBase*p) { Parent = p; } CGraphSave::~CGraphSave() { } void CGraphSave::OnArray() { cout << "数组存储图\n"; cout << "*******************************\n"; MGraph Graph = BuildGraph(); } void CGraphSave::OnAdjList() { cout << "邻接表存储图\n"; cout << "*******************************\n"; LGraph Graph = BuildGraph1(); } void CGraphSave::OnOrthList() { cout << "十字链表存储有向图\n"; cout << "*******************************\n"; OLGraph Graph = BuildOLGraph(); } void CGraphSave::OnAdjMList() { cout << "邻接多重表存储无向图\n"; cout << "*******************************\n"; AMLGraph Graph = BuildAMLGraph(); } void CGraphSave::Show() { cout << "**************图的存储********************\n"; cout << "*\t1、数组存储\t\t2、邻接表存储\n*\t3、有向图的十字链表\t4、无向图多重邻接表\n\t0、退出\n"; cout << "****************************************\n"; } void CGraphSave::DoEvent(int ID) { switch (ID) { case ID_Array: OnArray(); break; case ID_AdjList: OnAdjList(); break; case ID_OrList: OnOrthList(); break; case ID_AdjMList: OnAdjMList(); break; case ID_EXIT: OnExit(); break; default: OnInvilidate(); break; } } /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ /*函数定义部分*/ /*数组存储图的函数定义*/ MGraph CreatGraph(int VertexNum) { Vertex V, W; MGraph Graph; Graph = (MGraph)malloc(sizeof(GNode)); Graph->Nv = VertexNum; Graph->Ne = 0; /*初始化邻接矩阵*/ for (V = 0; V <= Graph->Nv-1; V++) for (W = 0; W <= Graph->Nv - 1; W++) Graph->G[V][W] = 0; return Graph; } MGraph BuildGraph() { MGraph Graph; Edge E; Vertex V; int Nv, i, t; printf("请输入要存储的图为有向图还是无向图\n*\t1有向图\t\t2无向图\n"); scanf_s("%d", &t); /*创建无边顶点*/ printf("请输入顶点个数：\n"); scanf_s("%d", &Nv); Graph = CreatGraph(Nv); /*插入边*/ printf("请输入边的个数：\n"); scanf_s("%d", &(Graph->Ne)); if (Graph->Ne != 0) { E = (Edge)malloc(sizeof(ENode));//建立边结点； printf("请按照“起点 终点 权重”依次输入边的数据\n"); for (i = 0; i <= Graph->Ne - 1; i++) { scanf_s("%d%d%d", &E->V1, &E->V2, &E->Weight); if(t==1)InsertEdge1(Graph, E); if (t == 2)InsertEdge2(Graph, E); } } /*写入顶点数据*/ printf("顶点是否存储数据\n*\t1存储\t\t2不存储\n"); scanf_s("%d", &t); if (t == 1) { printf("请依次输入顶点的数据\n"); for (V = 0; V <= Graph->Nv - 1; V++) scanf_s("%c", &(Graph->Data[V])); printf("存储图成功！\n"); return Graph; } return Graph; } void InsertEdge1(MGraph Graph, Edge E) { Graph->G[E->V1-1][E->V2-1] = E->Weight;/*有向图插入边*/ } void InsertEdge2(MGraph Graph, Edge E) { /*无向图插入边*/ Graph->G[E->V1-1][E->V2-1] = E->Weight; Graph->G[E->V2-1][E->V1-1] = E->Weight; } /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ /*邻接表存储图函数定义*/ LGraph CreatGraph1(int VertexNum) { Vertex V; LGraph Graph; Graph = (LGraph)malloc(sizeof(GNode1)); Graph->Nv = VertexNum; Graph->Ne = 0; /*初始化邻接表头指针*/ for (V = 0; V <= Graph->Nv - 1; V++) Graph->G[V].FirstEdge = NULL; return Graph; } void InsertEdge3(LGraph Graph, Edge1 E) { PtrToAdjVNode NewNode; /*插入边V1，V2*/ /*为V2建立新节点*/ NewNode = (PtrToAdjVNode)malloc(sizeof(AdjVNode)); NewNode->AdjV = E->V2; NewNode->Next = Graph->G[E->V1].FirstEdge; Graph->G[E->V1].FirstEdge = NewNode; } void InsertEdge4(LGraph Graph, Edge1 E) { PtrToAdjVNode NewNode; /*插入边V1，V2*/ /*为V2建立新节点*/ NewNode = (PtrToAdjVNode)malloc(sizeof(AdjVNode)); NewNode->AdjV = E->V2; NewNode->Next = Graph->G[E->V1].FirstEdge; Graph->G[E->V1].FirstEdge = NewNode; /*为V1建立新节点*/ NewNode = (PtrToAdjVNode)malloc(sizeof(AdjVNode)); NewNode->AdjV = E->V1; NewNode->Next = Graph->G[E->V2].FirstEdge; Graph->G[E->V2].FirstEdge = NewNode; } LGraph BuildGraph1() { LGraph Graph; Edge1 E; Vertex V; int Nv, i, t; printf("请输入要存储的图为有向图还是无向图\n*\t1有向图\t\t2无向图\n"); scanf_s("%d", &t); printf("请输入顶点个数：\n"); scanf_s("%d", &Nv); Graph = CreatGraph1(Nv); printf("请输入边的数量：\n"); scanf_s("%d",&(Graph->Ne)); if(Graph->Ne != 0) { E = (Edge1)malloc(sizeof(ENode1)); printf("请依次输入边的“起点，终点，权值”\n"); for (i = 0; i <= Graph->Ne - 1; i++) { scanf_s("%d%d%d", &E->V1, &E->V2, &E->Weight); if (t == 1)InsertEdge3(Graph, E); if (t == 2)InsertEdge4(Graph, E); } } /*如果顶点有数据则依次输入数据*/ printf("请依次输入结点的数据\n每输入一个数据按一次回车\n"); for (V = 0; V <Graph->Nv; V++) { scanf_s("%c", &Graph->G[V].Data); if(V==Graph->Nv-1)printf("存储结点完成！\n"); } printf("存储图完成！\n"); return Graph; } /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ /**有向图十字链表函数定义**/ OLGraph CreatOLGraph(int VexNum) { Vertex V; OLGraph Graph = (OLGraph)malloc(sizeof(OLGNode)); Graph->vexnum = VexNum; Graph->arcnum = 0; for (V = 0; V <= Graph->vexnum - 1; V++) Graph->G[V].firstin = Graph->G[V].firstout = NULL; return Graph; } void OLGraphInsert(OLGraph Graph, PtrToANode E) { PtrToANode NewNode; NewNode = (PtrToANode)malloc(sizeof(ANode)); NewNode->tailvex = E->tailvex; NewNode->headvex = E->headvex; NewNode->hlink = Graph->G[NewNode->tailvex].firstin; NewNode->tlink = Graph->G[NewNode->headvex].firstout; Graph->G[NewNode->headvex].firstin = Graph->G[NewNode->tailvex].firstout; } OLGraph BuildOLGraph() { OLGraph Graph; PtrToANode E; Vertex V; int Nv, i; printf("请输入顶点个数：\n"); scanf_s("%d", &Nv); Graph = CreatOLGraph(Nv); printf("请输入边的数量：\n"); scanf_s("%d", &(Graph->arcnum)); if (Graph->arcnum != 0) { E = (PtrToANode)malloc(sizeof(ANode)); for (i = 0; i <= Graph->arcnum - 1; i++) { printf("请依次输入弧的起点，终点，权值\n"); scanf_s("%d%d%d", &E->tailvex, &E->headvex, &E->Weight); OLGraphInsert(Graph, E); } } printf("请依次输入结点的数据\n每输入一个数据按一次回车\n"); for (V = 0; V <= Graph->vexnum - 1; V++) scanf_s("%c", &Graph->G[V].Data); printf("存储图完成！\n"); return Graph; } /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ /***************************************************************************/ //**邻接多重表函数实现部分**// AMLGraph CreatAMLGraph(int VerNum) { int i; AMLGraph Graph = (AMLGraph)malloc(sizeof(AdjMNode)); Graph->vexnum = VerNum; Graph->edgenum = 0; for (i = 0; i <= Graph->vexnum - 1; i++) (Graph->G[i]).firstedge = NULL; return Graph; } void AMLGraphInsert(AMLGraph Graph, AMLGraphArc E) { AMLGraphArc NewNode = (AMLGraphArc)malloc(sizeof(ArcNode)); NewNode->mark = unvisited; NewNode->ivex = E-