数据结构第三次实验报告

2013-2014学年第1 学期 任课老师： 刘安丰

课程名称 数据结构 实验名称 实验环境 C++ 实验目的和内容要求 实验三 图的操作算法 班级 学号 姓名 实验时间 12月5号 实验三 图的操作算法 一、实验要求与内容 实现图的常用操作算法：包括建立图的存储结构、深度优先搜索和广度优先搜索，求图的最小生成树、拓扑排序、最短路径等。 二、实验目的 1．掌握图的基本存储方法。 2．掌握有关图的操作算法并用高级语言实现。 3．熟练掌握图的两种搜索路径的遍历方法。 4. 掌握图的有关应用。 实验过程记录 1、最小生成树 Prim\\Kruskal算法 #include #include #include #define MAX_VERTEX_NUM 20 #define OK 1 #define ERROR 0 #define MAX 1000 using namespace std; typedef struct Arcell { double adj; }Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM]; //节点数组 AdjMatrix arcs; //邻接矩阵 int vexnum, arcnum; //图的当前节点数和弧数 }MGraph; typedef struct Pnode //用于普利姆算法 { char adjvex; //节点 double lowcost; //权值 }Pnode,Closedge[MAX_VERTEX_NUM]; //记录顶点集U到V-U的代价最小的边的辅助数组定义 typedef struct Knode //用于算法中存储一条边及其对应的2个节点 { char ch1; //节点1 char ch2; //节点2 double value;//权值 }Knode,Dgevalue[MAX_VERTEX_NUM]; //----------------------------------------------------------------------------------- int CreateUDG(MGraph & G,Dgevalue & dgevalue); int LocateVex(MGraph G,char ch); int Minimum(MGraph G,Closedge closedge); void MiniSpanTree_PRIM(MGraph G,char u); void Sortdge(Dgevalue & dgevalue,MGraph G); //----------------------------------------------------------------------------------- int CreateUDG(MGraph & G,Dgevalue & dgevalue) //构造无向加权图的邻接矩阵 { int i,j,k; cout<<\"请输入图中节点个数和边/弧的条数：\"; cin>>G.vexnum>>G.arcnum; cout<<\"请输入节点：\"; for(i=0;i>G.vexs[i]; for(i=0;i> dgevalue[k].ch1 >> dgevalue[k].ch2 >> dgevalue[k].value; i = LocateVex(G,dgevalue[k].ch1 ); j = LocateVex(G,dgevalue[k].ch2 ); G.arcs[i][j].adj = dgevalue[k].value; G.arcs[j][i].adj = G.arcs[i][j].adj; } return OK; } int LocateVex(MGraph G,char ch) //确定节点ch在图G.vexs中的位置 { int a ; for(int i=0; i dgevalue[j].value) { temp = dgevalue[i].value; dgevalue[i].value = dgevalue[j].value; dgevalue[j].value = temp; ch1 = dgevalue[i].ch1; dgevalue[i].ch1 = dgevalue[j].ch1; dgevalue[j].ch1 = ch1; ch2 = dgevalue[i].ch2; dgevalue[i].ch2 = dgevalue[j].ch2; dgevalue[j].ch2 = ch2; } } } } void main() { int i,j; MGraph G; char u; Dgevalue dgevalue; CreateUDG(G,dgevalue); cout<<\"图的邻接矩阵为：\"<>u; cout<<\"构成最小代价生成树的边集为：\\n\"; MiniSpanTree_PRIM(G,u); cout<<\"============克鲁斯科尔算法=============\\n\"; cout<<\"构成最小代价生成树的边集为：\\n\"; MiniSpanTree_KRSL(G,dgevalue); } 2、拓扑排序 #include \"stdio.h\" #define MAX_VERTEX_NUM 20 #include \"conio.h\" #include \"stdlib.h\" #define STACK_INIT_SIZE 16 #define STACKINCREMENT 5 typedef int SElemType; typedef char VertexType; typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; //我们依然用邻接表来作图的存储结构 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; int info; }ArcNode; //表结点类型 typedef struct VNode{ VertexType data; int count; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; //头结点 typedef struct{ AdjList vertices; //邻接表 int vexnum,arcnum; }ALGraph; int InitStack(SqStack &S) { S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(-1); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return 1; }//InitStack int Push(SqStack &S,SElemType e) { if((S.top-S.base)>=S.stacksize) { S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) exit(-1); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; }//if *(S.top)=e; S.top++; return 1; }//Push int Pop(SqStack &S,SElemType &e) { if(S.top==S.base) return 0; --S.top; e=*S.top; return 1; }//Pop int StackEmpty(SqStack &S) { if(S.top==S.base) return 1; else return 0; }//StackEmpty int LocateVex(ALGraph G,char u) { int i; for (i=0;iadjvex=j; //p->info = w; p->nextarc=G.vertices[i].firstarc; //前插法,即每次都插入到头结点的后面 G.vertices[i].firstarc=p; printf(\"Next\\n\"); }//for return; }//CreateALGraph_adjlist void FindInDegree(ALGraph &G) { int i,j; for(i=0;inextarc) G.vertices[p->adjvex].count++; }//for }//FindInDegree int TopoSort(ALGraph &G) { SqStack S; FindInDegree(G); InitStack(S); for(int i=0;inextarc) { int k; k=p->adjvex; if(!(--G.vertices[k].count)) Push(S,k); }//for }//while if(countt #include #include #define MAX_VERTEX_NUM 20 typedef struct ArcNode{ int adjvex; struct ArcNode* nextarc; //InfoType* info; }ArcNode; /********************************* *链表结点的结构用于创建栈或是队列 ********************************/ typedef struct LinkNode{ ArcNode* parc; //存储指针地址 struct LinkNode* next; //指向一下个结点 }LinkNode; typedef struct VNode{ char cData; //顶点元素值 ArcNode* firstarc; //指向第一条依附于该点的边 }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum; //图的当前顶点数和弧数 int arcnum; }ALGraph; int Visited[MAX_VERTEX_NUM]; /********************************* *将生成的图打印出来以便确认正确性 ********************************/ int PrintCheck(ALGraph* pag) { int i; ArcNode* p; printf(\"\\nCheck the Graph!\\n\"); printf(\"No\\tdata\\tnext\\tnext\\t.....\\n\"); for(i=0; ivexnum; i++) { printf(\"%d\\t%c\\t\ p = pag->vertices[i].firstarc; while(p) { printf(\"%d\\t\ p = p->nextarc; } printf(\"\\n\"); } return 1; } /************************** *采用前插法创建邻接表 *************************/ int CreateGraph(ALGraph* pag,int start,int end) { ArcNode* arcNodes = (ArcNode*)malloc(sizeof(ArcNode)); ArcNode* arcNodee = (ArcNode*)malloc(sizeof(ArcNode)); ArcNode* p; if(!arcNodes || !arcNodee) return 0; //从start->end生成关系 arcNodes->adjvex = end; //下一结点的位置 p = pag->vertices[start].firstarc; if(!p) //第一个结点单独构造 { arcNodes->nextarc = pag->vertices[start].firstarc; pag->vertices[start].firstarc = arcNodes; } else{ while(p->nextarc) p = p->nextarc; p->nextarc = arcNodes; arcNodes->nextarc = NULL; } //end->start 的关系生成 arcNodee->adjvex = start; //下一结点的位置 p = pag->vertices[end].firstarc; if(!p) //第一个结点单独构造 { arcNodee->nextarc = pag->vertices[end].firstarc; pag->vertices[end].firstarc = arcNodee; } else{ while(p->nextarc) p = p->nextarc; p->nextarc = arcNodee; arcNodee->nextarc = NULL; } return 1; } /**************************************** *深度优先遍历,非递归方式 *结点先访问再入栈 *栈的存储结构直接采用了LinkNode构成的链表 *采用前插法进行插入与删除，从而也可以完成栈的功能 *栈空条件 Stack->next == NULL ***************************************/ void DFSTraverse(ALGraph ag,int start) { LinkNode* Stack = (LinkNode*)malloc(sizeof(LinkNode)); //链表头结点，用做栈 LinkNode* pStack = (LinkNode*)malloc(sizeof(LinkNode)); //对栈操作的指针 LinkNode* temp; //临时存储 ArcNode* p; int i; if(!pStack||!Stack) return; Stack->next = NULL; p = ag.vertices[start].firstarc; Visited[start]=1; //Flag printf(\"\\n输出深度优先遍历顺序:\"); printf(\" %c \ //访问第一个点 while(1) //正常情况下执行一次，为了打印孤立结点 { //push stack pStack->parc = p; pStack->next = Stack->next; //将p接入链式栈中 Stack->next = pStack; //push over while(p && (Stack->next)) //当并且栈不为空时 { while(p) { if(Visited[p->adjvex]) p = p->nextarc; else { Visited[p->adjvex]=1; printf(\" %c \//Visit Function //push stack pStack = (LinkNode*)malloc(sizeof(LinkNode)); if(!pStack) return; //结点建立不成功 pStack->parc = p; pStack->next = Stack->next; Stack->next = pStack; //push over p = ag.vertices[p->adjvex].firstarc; } } //pop stack temp = Stack->next; Stack->next = temp->next; p = temp->parc->nextarc; free(temp); //pop over } for(i=0; inext == NULL ***************************************/ void BFSTraverse(ALGraph ag,int start) { LinkNode* Queue = (LinkNode*)malloc(sizeof(LinkNode)); //链表头结点，用做队列 LinkNode* pQueue = (LinkNode*)malloc(sizeof(LinkNode)); //对队列操作的指针 LinkNode* temp; //临时存储 LinkNode* last; //指向最后一个元素的指针 ArcNode* p; int i; if(!Queue || !pQueue) return; printf(\"\\n输出广度优先遍历次序:\"); printf(\" %c \p = ag.vertices[start].firstarc; Visited[start] = 1; while(1) //正常情况下执行一次循环 { //EnQueue pQueue->parc = p; Queue->next = pQueue; pQueue->next = NULL; last = pQueue; //指向最后一个元素的指针 //EnQueue over while(p && Queue->next) { while(p) { if(!Visited[p->adjvex]) { Visited[p->adjvex] = 1; printf(\" %c \//Visit Function //EnQueue pQueue = (LinkNode*)malloc(sizeof(LinkNode)); if(!pQueue) return; pQueue->parc = p; pQueue->next = NULL; last->next = pQueue; last = last->next; //指向最后一个元素的指针 //EnQueue over } p = p->nextarc; } //DeQueue temp = Queue->next; p = ag.vertices[temp->parc->adjvex].firstarc; Queue ->next = temp->next; //DeQueue over } for(i=0; i0) break; else printf(\"\\n请注意结点个数不能大于20,并且不能为0!\\n\"); } ag.vexnum = n; printf(\"\\n初始化图的结点，输入字符并回车:\\n\"); for(i=0; i=0) break; else printf(\"\\n请注意边的数量不能大于%d,并且不能小于1!\\n\} ag.arcnum = i; printf(\"\\n初始化图的边，结点从0开始计，最大为%d\\n\for(i=1; i<=ag.arcnum; i++) { while(1) //起点有效性验证 { printf(\"第<%d>条边的起点: \ fflush(stdin); scanf(\"%d\ if(start=0) break; else printf(\"重新输入 \"); } while(1) //终点有效性验证 { printf(\"第<%d>条边的终点: \ fflush(stdin); scanf(\"%d\ if(end=0 && end!=start) break; else printf(\"重新输入 \"); } printf(\"\\n\"); CreateGraph(&ag,start,end); } PrintCheck(&ag); //打印出生成的图 printf(\"\\n开始进行图的遍历!\\n\"); while(1) //起始点有效性验证 { printf(\"请输入深度优先遍历的开始结点:\"); fflush(stdin); scanf(\"%d\ if(choose>=0 && choose=0 && choose #include #define MAX 100 #define MAXINT 1000 /*typedef struct node{ int number; struct node *next; }edgeNode;*/ typedef struct { int vexnum; int arcnum; int arcs[MAX][MAX]; }Mgragh; int creat_mgragh(Mgragh &mg) { int i=0; int j=0; int k=0; int weight; cout<<\"输入顶点数\"<>mg.vexnum; cout<<\"输入边数\"<>mg.arcnum; for(i=0;i>i; if(i<=mg.vexnum) { cout<<\"输入边的终点：\"<>j; if(j<=mg.vexnum) { cout<<\"输入权值\"<>weight; mg.arcs[i-1][j-1]=weight; mg.arcs[j-1][i-1]=weight; break; } else cout<<\"重新输入！\"<附：实验源程序代码