第一篇：湘潭大学 数据结构实验5 实验报告 源代码 图的应用
“数据结构和算法II”课程实验报告
实验名称：图及其应用
班级 姓名 学号 实验日期： 实验机时：2 学时 实验成绩：
-----------------一.实验目的：
1.熟练掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法 2.掌握图的基本运算及应用
3.加深对图的理解，逐步培养解决实际问题的编程能力 二.实验内容：（1）基本实验内容：
采用邻接表或邻接矩阵方式存储图，实现图的深度遍历和广度遍历； 用广度优先搜索方法找出从一顶点到另一顶点边数最少的路径。三.程序及注释：
#include “stdio.h” #include “limits.h” //INT_MAX头文件 #include “windows.h” //boolean头文件 #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 #define OVERFLOW-1 #define OK 1 #define ERROR 0 typedef int Status;typedef enum {DG,DN,UDG,UDN} GraphKind;typedef int VRType;typedef char VertexType;typedef char* InfoType;typedef int QElemType;//边信息
typedef struct ArcCell{ VRType adj;//1或0表示是否邻接,对带权图，则为权值类型 InfoType *info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//图结构 typedef struct {
VertexType vexs[MAX_VERTEX_NUM];//定点向量 AdjMatrix arcs;
//邻接矩阵，为一二维数组 //图的当前顶点数和弧数 int vexnum,arcnum;GraphKind kind;
//图的种类标志
}MGraph;//辅助队列
typedef struct QNode{ QElemType data;//数值域 struct QNode *next;//指针域
}QNode, *QueuePtr;typedef struct{ QueuePtr front;//队头 QueuePtr rear;//队尾
}LinkQueue;//初始化队列
Status InitQueue(LinkQueue &Q){
Q.front = Q.rear =(QueuePtr)malloc(sizeof(QNode));if(!Q.front){ printf(“内存分配失败!”);exit(OVERFLOW);} Q.front->next = NULL;return OK;} //插入元素到队尾
Status EnQueue(LinkQueue &Q,QElemType e){
QueuePtr p =(QueuePtr)malloc(sizeof(QNode));if(!p){printf(“n内存分配失败!”);exit(OVERFLOW);} p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return OK;} //队列判空
Status QueueEmpty(LinkQueue Q){ return Q.front == Q.rear;} //销毁队列
Status DestroyQueue(LinkQueue &Q){
while(Q.front){Q.rear = Q.front->next;free(Q.front);Q.front = Q.rear;} return OK;} //删除队头元素
Status DeQueue(LinkQueue &Q,QElemType &e){
if(QueueEmpty(Q)){printf(“n队列为空！”);return ERROR;} QueuePtr p = Q.front->next;e = p->data;Q.front->next = p->next;if(Q.rear==p)Q.rear = Q.front;free(p);return OK;} //对顶点v定位，返回该顶点在数组的下标索引，若找不到则返回-1 int LocateVex(MGraph G,char v){
for(int i=0;i G.kind = UDN;printf(“输入顶点个数和边数(如：4,3):”);int vexnum,arcnum;scanf(“%d,%d”,&vexnum,&arcnum);G.vexnum=vexnum;G.arcnum=arcnum;//判断是否超过顶点最大个数 while(G.vexnum>MAX_VERTEX_NUM){printf(“最大顶点为20，重新输入(如：4,3):”);scanf(“%d,%d”,&G.vexnum,&G.arcnum);} printf(“n依次输入顶点向量值n”);int i;for(i=0;i //清空缓冲区 fflush(stdin);printf(“第%d个:”,i+1);scanf(“%c”,&G.vexs[i]);} //初始化邻接矩阵 for(i=0;i int values;printf(“n输入依附两个顶点的边及其权值<如，a,b,1>n”);for(i=0;i printf(“第%d条：”,i+1);//清空缓冲区 fflush(stdin);scanf(“%c,%c,%d”,&rear,&front,&values);int m,n;//定位两顶点在vexs数组中的索引 m = LocateVex(G,rear);n = LocateVex(G,front);if(m==-1||n==-1){ printf(“输入顶点或不在此图中，请重新输入！n”);i--;continue;} //赋予对应矩阵位置的权值，以及对称弧的权值 G.arcs[m][n].adj = values;G.arcs[n][m].adj = values;} return OK;} //CreateUDG //矩阵输出 void printArcs(MGraph G){ int i;printf(“ ”);//输出第一行的顶点向量 for(i=0;i for(int j=0;j else printf(“ %d”,G.arcs[i][j].adj);}} printf(“ ∞”); printf(“n”);} //访问顶点v输出 Status printAdjVex(MGraph G,int v){ printf(“%c ”,G.vexs[v]);return OK;} //查找v顶点的第一个邻接点 Status FirstAdjVex(MGraph G,int v){ //查找与顶点v的第一个邻接点，找到后立即返回其索引，若找不到，则返回-1 for(int i=1;i return i;} return-1;} //查找基于v顶点的w邻接点的下一个邻接点 Status NextAdjVex(MGraph G,int v,int w){ //查找基于顶点v的w邻接点的下一个邻接点，找到之后立即返回其索引，若找不到，则返回-1 for(int i=w+1;i boolean visited[MAX_VERTEX_NUM];//函数指针变量 Status(* VisitFunc)(MGraph G,int v);//DFS,从第v个顶点出发递归深度优先遍历图G void DFS(MGraph G,int v){ visited[v] = TRUE;//访问第v个顶点 VisitFunc(G,v);for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){if(!visited[w]) DFS(G,w);}} //深度优先遍历 void DFSTraverse(MGraph G,Status(*Visit)(MGraph G,int v)){ //将函数复制给全局的函数指针变量，待调用DFS时使用 VisitFunc = Visit;int v;//将访问标记初始化为false for(v=0;v void BFSTraverse(MGraph G,Status(*Visit)(MGraph G,int v)){ //按广度优先非递归遍历图G，使用辅助队列Q和访问标志数组Visited int v;int u;//将访问标记数组初始化为false for(v = 0;v //判断顶点V是否被访问 if(!visited[v]){//将第一次访问的顶点对应的访问标记数组位置赋值为TRUE visited[v] = TRUE;//输出顶点v Visit(G,v);EnQueue(Q,v);while(!QueueEmpty(Q)){//按入队序列取出顶点，便于查找此顶点的邻接点 DeQueue(Q,u);//查找当前顶点邻接点 for(int w=FirstAdjVex(G,u);w>=0;w = NextAdjVex(G,u,w)) if(!visited[w]){visited[w] =TRUE;Visit(G,w);EnQueue(Q,w);}}} //销毁队列 DestroyQueue(Q);} int main(){ printf(“====图的创建及其应用====n”);//创建一个图 MGraph G;CreateUDN(G);//用邻接矩阵输出图 printf(“n图的邻接矩阵输出如下:n”);printArcs(G);//深度优先遍历 printf(“n深度优先遍历序列:n”);DFSTraverse(G,printAdjVex);printf(“n”);//广度优先遍历 } printf(“n广度优先遍历序列:n”);BFSTraverse(G,printAdjVex);printf(“n”);四.运行结果： 五.实验心得： 通过本次课程设计，对图的概念有了一个新的认识，在学习离散数学的时候，总觉得图是很抽象的东西，但是在学习了《数据结构与算法》这门课程之后，我慢慢地体会到了其中的奥妙，图能够在计算机中存在，首先要捕捉他有哪些具体化、数字化的信息，比如说权值、顶点个数等，这也就说明了想要把生活中的信息转化到计算机中必须用数字来完整的构成一个信息库，而图的存在，又涉及到了顶点之间的联系。图分为有向图和无向图，而无向图又是有向图在权值双向相等下的一种特例，如何能在计算机中表示一个双向权值不同的图，这就是一件很巧妙的事情。有了这次课程设计的经验和教训，我能够很清楚的对自己定一个合适的水平。 目录 前言..................................................................................................................2 概要设计..................................................................................................................3 1.1 数据结构设计...........................................................................................3 2.1 算法设计...................................................................................................3 2.1.1 建立链表的算法..............................................................................3 2.1.2 链表插入一个元素的算法..............................................................3 2.1.3 链表删除一个元素的算法..............................................................3 3.1 ADT描述..................................................................................................4 4.1 详细设计…………………………………………… ……………………………… 4 4.1.1 数据存储结构……………………………… ……………………………… 4.4.1.2 主要伪代码…… …………………… ……………………………………… 4 软件测试..................................................................................................................7 心得体会................................................................................................................11 源代码...................................................................................................................12 参考文献………………………………………………………………………...21 前言 数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已经成为其他理工专业的热门选修课。 随着计算机科学的技术和发展，计算机的功能和运算速度不断地提高，其应用于信息处理的范围日益扩大。与之相应的，计算机的加工处理对象也从简单的数据发展到一般的符号，进而发展到更复杂的数据结构。数据结构是计算机程序设计的重要理论技术基础，数据结构的表示和操作都涉及到算法，如何描述数据的结构和讨论有关的算法，又涉及到程序设计语言。因此，它不仅是计算机学科的核心课程，而且已经成为其他理工专业的热门选修课。我们通过对这门基础课程的学习，要学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适合的逻辑结构，储存结构及其相应的算法，并初步掌握算法时间分析和空间分析的技术。通过实际操作去了解数据结构原理，练习编写代码的能力，以及抽象能力。 从课程性质上讲，“数据结构”是一门专业技术基础课。它的要求是学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构，存储结构及相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，数据结构的学习过程也是复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读，符合软件工程的规范。 概要设计 1.1 数据结构设计 采用链式储存结构。typedef struct LNode{ ElemType data;struct LNode *next;}LNode,*LinkList;2.1 算法设计 2.1.1 建立链表的算法 （1）算法思想分析 首先从表尾到表头逆向建立单链表,然后再建立的单链表基础上进行对链表上的元素进行查询,删除,插入的操作。（2）要点描述 首先建立一个带头结点的单链表，通过申请内存，先建立一个空链表。然后结点的插入，建立一个有多个结点的链表。在进行查询等操作。（3）时间和空间复杂度分析 程序的时间复杂度为O(n)。 2.1.2 链表插入一个元素的算法 （1）算法思想分析 要生成一个新数据域为X的结点，然后插入在单链表中。（2）要点描述 在链表中插入结点只需要修改指针。若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。 （3）时间和空间复杂度分析 时间复杂度O(n)2.1.3 链表删除一个元素的算法 （1）算法思想分析 要删除一个结点，必须修改指针并且释放空间。（2）要点描述 找到线性表中第i-1个结点，修改其指向后继的指针。 （3）时间和空间复杂度分析 时间复杂度O(n) 3.1 ADT描述 ADT LinkList{ 数据对象：D={ e | e∈LNode } 数据关系：R1={ 基本操作： GreateList_L(&L, n) 操作结果：构造了一个长为n的数据链表 ListDelete_L(&L, i, &e) 初始条件：链表L已存在而且非空 操作结果：删除L的第i个数据，并且用e返回其值 ListInsert_L(&L, i, e) 初始条件：链表L已存在 操作结果： 在L的第i个位置插入数据e GetElem(L, i, e) 初始条件：链表L已存在 操作结果：用e返回L中的第i个数据 }ADT LinkList 4.1 详细设计 4.1.1数据存储结构设计 采用单链式线性表实现 4.1.2 主要伪代码 Status GetElem(LinkList L, int i, ElemType *e){ int j=0;int d;LinkList p = L;while(p&&j } if(!p || j > i)return ERROR;printf(“您要查询的元素是:n”);d=p->data;printf(“%d”,d);printf(“n”);} void InitList(LinkList *L){ *L =(LinkList)malloc(sizeof(struct LNode));if(!*L)exit(OVERFLOW);(*L)->next = NULL;} Status ListInsert(LinkList L, int i, ElemType e){ int j = 0;LinkList p = L, s;while(p && j < i-1){ p = p->next;j++;} if(!p|| j > i-1)return ERROR;s =(LinkList)malloc(sizeof(struct LNode));s->data = e;s->next = p->next;p->next = s;return OK;} Status ListDelete(LinkList L, int i, ElemType *e){ int j = 0;LinkList p = L, q;while(p->next && j < i-1){ p = p->next; j++;} if(!p->next || j > i-1)return ERROR;q = p->next;p->next = q->next;*e = q->data;free(q);return OK;} void ListTraverse(LinkList L, void(*vi)(ElemType)){ LinkList p = L->next;while(p){ vi(p->data);p = p->next;} printf(“n”);} void ListPrint(LinkList L){ LinkList p = L->next;while(p){ printf(“%d ”, p->data);p = p->next;} printf(“n”);} void printInt(int data){ printf(“%d ”, data);}.软件测试 图一(主界面) 图二(插入学生信息) 图三(显示所有学生信息) 图四(查询个人信息) 图五(统计信息) 图六(修改信息) 图七(保存数据) 图八(删除信息) 心得体会 通过本程序的设计，我对数据结构作了以下总结：要解决一道程序题必须先要认真捕捉改程序中的有用信息，找出解决方法。先规划好，程序需要什么样的数据结构，什么函数，对程序有什么要求。然后从整体把握对程序设计进行分工，相应地把程序分成若干模块，具体实现各部分实行相应的功能。一个程序要顺利地进行设计，一是要对程序的功能有全面的了解，如果漏了某些部分，都会使得这个程序调试不出来或者是令该程序没有达到预想的效果。其次，在程序的编译中，必须注重程序设计过程中的细节，像单链表的程序，就要理解链表的概念，理解链表的数据特点，要清楚知道数据域和指针域的作用，否则，很容易会浪费大量时间在检测错误上面。要说到解题的思考方向，如果要总结成规律，我认为要灵活的进行方法的设计，通过不同的方法来实现不同的功能，如通过结点的插入来实现链表的创建。同时应该注意各种语句的选择，要先预想好需要什么样的语句来实现函数定义，尽量简单快捷地完成，避免出错。 要规范面向对象程序设计师的书写协管，在这次课程设计中，我们再次感受到，规范的程序书写，可以更好的进行后期的差错补漏。还应该注意各种面向对象语言语法的运用，例如继承的方法，都要严格按照语法来进行，否则很容易就会出现错误，甚至严重影响课程设计的进度。 源代码 #include “stdio.h” #include “stdlib.h” #include “string.h” int shoudsave=0;// struct student { char num[10];//学号 char name[20]; char sex[4]; int cgrade; int mgrade; int egrade; int totle; int ave; char neartime[10];//最近更新时间 }; typedef struct node { struct student data; struct node *next;}Node,*Link; int menu(){ char m[3]; int n; printf(“ ************************欢迎进入学生成绩管理系统******************************nn”); printf(“t欢迎使用本学生管理系统，本系统将为您提供历史学生信息查询，学生成绩信息管理功能。n”); printf(“********************************************************************************”); printf(“t1输入学生资料ttttt2删除学生资料n”); printf(“t3查询学生资料ttttt4修改学生资料n”); printf(“t5显示学生资料ttttt6统计学生成绩n”); printf(“t7保存学生资料n”); printf(“ttplease choose a operation(1-7):n”); printf(“*********************************************************************** *********n”); scanf(“%s”,m); n=atoi(m); return(n);} void printstart(){ printf(“---------n”);} void Wrong(){ printf(“n=====>提示:输入错误!n”);} void Nofind(){ printf(“n=====>提示:没有找到该学生!n”);} void printc()// 本函数用于输出中文 { printf(“学号t 姓名 性别 英语成绩 数据库成绩 数据结构成绩 总分平均分n”);} void printe(Node *p)//本函数用于输出英文 { printf(“%-12s%stt%st%dtt%dt%dt%dt %dn”,p->data.num,p->data.name,p->data.sex,p->data.egrade,p->data.mgrade,p->data.cgrade,p->data.totle,p->data.ave);} Node* Locate(Link l,char findmess[],char nameornum[])//该函数用于定位连表中符合要求的接点，并返回该指针 { Node *r; if(strcmp(nameornum,“num”)==0)//按学号查询 { r=l->next; while(r!=NULL) { if(strcmp(r->data.num,findmess)==0) return r; r=r->next; } } else if(strcmp(nameornum,“name”)==0)//按姓名查询 { r=l->next; while(r!=NULL) { if(strcmp(r->data.name,findmess)==0) return r; r=r->next; } } return 0;} void Add(Link l)//增加学生 { Node *p,*r,*s; char num[10]; r=l; s=l->next; while(r->next!=NULL) r=r->next;//将指针置于最末尾 while(1) { printf(“请你输入学号(以'0'返回上一级菜单:)”); scanf(“%s”,num); if(strcmp(num,“0”)==0) break; while(s) { if(strcmp(s->data.num,num)==0) { printf(“=====>提示:学号为'%s'的学生已经存在,若要修改请你选择'4 修改'!n”,num); printstart(); printc(); printe(s); printstart(); printf(“n”); return; } s=s->next; } p=(Node *)malloc(sizeof(Node)); strcpy(p->data.num,num); printf(“请你输入姓名:”); scanf(“%s”,p->data.name); getchar(); printf(“请你输入性别:”); scanf(“%s”,p->data.sex); getchar(); printf(“请你输入数据结构成绩:”); scanf(“%d”,&p->data.cgrade); getchar(); printf(“请你输入数据库成绩:”); scanf(“%d”,&p->data.mgrade); getchar(); printf(“请你输入英语成绩:”); scanf(“%d”,&p->data.egrade); getchar(); p->data.totle=p->data.egrade+p->data.cgrade+p->data.mgrade; p->data.ave=p->data.totle / 3; //信息输入已经完成p->next=NULL; r->next=p; r=p; shoudsave=1; } } void Qur(Link l)//查询学生 { char findmess[20]; Node *p; if(!l->next) { printf(“n=====>提示:没有资料可以查询!n”); return; } printf(“请你输入要查找的学号:”); scanf(“%s”,findmess); p=Locate(l,findmess,“num”); if(p) { printf(“tttt查找结果n”); printstart(); printc(); printe(p); printstart(); } else Nofind();} void Del(Link l)//删除 { Node *p,*r; char findmess[20]; if(!l->next) { printf(“n=====>提示:没有资料可以删除!n”); return; } printf(“n=====>确定进行删除操作请按 1，按其他按键退出该操作nnnn”); if(menu()==1) { printf(“请你输入要删除的学号:”); scanf(“%s”,findmess); p=Locate(l,findmess,“num”); if(p) { r=l; while(r->next!=p) r=r->next; r->next=p->next; free(p); printf(“n=====>提示:该学生已经成功删除!n”); shoudsave=1; } else Nofind(); } else exit;} void Modify(Link l)//修改函数 { Node *p; char findmess[20]; if(!l->next) { printf(“n=====>提示:没有资料可以修改!n”); return; } printf(“请你输入要修改的学生学号:”); scanf(“%s”,findmess); p=Locate(l,findmess,“num”); if(p) { printf(“请你输入新学号(原来是%s):”,p->data.num); scanf(“%s”,p->data.num); printf(“请你输入新姓名(原来是%s):”,p->data.name); scanf(“%s”,p->data.name); getchar(); printf(“请你输入新性别(原来是%s):”,p->data.sex); scanf(“%s”,p->data.sex); printf(“请你输入新的数据结构成绩(原来是%d分):”,p->data.cgrade); scanf(“%d”,&p->data.cgrade); getchar(); printf(“请你输入新的数据库成绩(原来是%d分):”,p->data.mgrade); scanf(“%d”,&p->data.mgrade); getchar(); printf(“请你输入新的英语成绩(原来是%d分):”,p->data.egrade); scanf(“%d”,&p->data.egrade); p->data.totle=p->data.egrade+p->data.cgrade+p->data.mgrade; p->data.ave=p->data.totle/3; printf(“n=====>提示:资料修改成功!n”); shoudsave=1; } else Nofind(); } void Disp(Link l)//显示函数 { int count=0; Node *p; p=l->next; if(!p) { printf(“n=====>提示:没有资料可以显示!n”); return; } printf(“tttt显示结果n”); printstart(); printc(); printf(“n”); while(p) { printe(p); p=p->next; } printstart(); printf(“n”);} void Tongji(Link l)//统计函数 { Node *pm,*pe,*pc,*pt,*pa;//用于指向分数最高的接点 Node *r=l->next; if(!r) { printf(“n=====>提示:没有资料可以统计!n”); return; } pm=pe=pc=pt=pa=r; while(r!=NULL) { if(r->data.cgrade>=pc->data.cgrade) pc=r; if(r->data.mgrade>=pm->data.mgrade) pm=r; if(r->data.egrade>=pe->data.egrade) pe=r; if(r->data.totle>=pt->data.totle) pt=r; if(r->data.ave>=pa->data.ave) pa=r; r=r->next; } printf(“------------------------------统计结果-n”); printf(“总分最高者:t%s %d分n”,pt->data.name,pt->data.totle); printf(“平均分最高者:t%s %d分n”,pa->data.name,pa->data.ave); printf(“英语最高者:t%s %d分n”,pe->data.name,pe->data.egrade); printf(“数据库最高者:t%s %d分n”,pm->data.name,pm->data.mgrade); printf(“数据结构最高者:t%s %d分n”,pc->data.name,pc->data.cgrade); printstart();} void Save(Link l)//保存函数 { FILE* fp; Node *p; int flag=1,count=0; fp=fopen(“c:student”,“wb”); if(fp==NULL) { printf(“n=====>提示:重新打开文件时发生错误!n”); exit(1); } p=l->next; while(p) { if(fwrite(p,sizeof(Node),1,fp)==1) { p=p->next; count++; } else { flag=0; break; } } if(flag) { printf(“n=====>提示:文件保存成功.(有%d条记录已经保存.)n”,count); shoudsave=0; } fclose(fp);} void main(){ Link l;//连表 FILE *fp;//文件指针 char ch; char jian; int count=0; Node *p,*r; l=(Node*)malloc(sizeof(Node)); l->next=NULL; r=l; fp=fopen(“C:student”,“rb”); if(fp==NULL) { fp=fopen(“C:student”,“wb”); exit(0); } printf(“n=====>提示:文件已经打开,正在导入记录......n”); while(!feof(fp)) { p=(Node*)malloc(sizeof(Node)); if(fread(p,sizeof(Node),1,fp))//将文件的内容放入接点中 { p->next=NULL; r->next=p; r=p;//将该接点挂入连中 count++; } } fclose(fp);//关闭文件 printf(“n=====>提示:记录导入完毕,共导入%d条记录.n”,count); for(;;) { switch(menu()) { case 1:Add(l);break;//增加学生 case 2:Del(l);break;//删除学生 case 3:Qur(l);break;//查询学生 case 4:Modify(l);break;//修改学生 case 5:Disp(l);break;//显示学生 case 6:Tongji(l);break;//统计学生 case 7:Save(l);break;//保存学生 default: Wrong(); getchar(); break; } } } 参考文献 《数据结构（C语言版）》----------------清华大学出版社 严蔚敏 吴伟民 编著 《C语言程序设计》------------------------中国铁道出版社 丁峻岭 余坚 编著 数据结构上机实验六 实验内容:图的基本操作 实验要求: 1)图的遍历与基本操作要作为函数被调用.2)把自己使用的图结构明确的表达出来.3)基本上实现每个实验题目的要求.分组要求：可单独完成，也可两人一组。 实验目的: 1)熟悉C/C++基本编程,培养动手能力.2)通过实验,加深对图的理解.评分标准： 1)只完成第一和第二题，根据情况得4，5分； 2）完成前3题，根据情况得5至7分； 3）在2）基础上，选做四）中题目，根据情况得8至10分。 题目: 一)建立一个无向图+遍历+插入 (1)以数组表示法作为存储结构，从键盘依次输入顶点数、弧数与各弧信息建立一个无向图； (2)对（1）中生成的无向图进行广度优先遍历并打印结果； (3)向（1）中生成的无向图插入一条新弧并打印结果； 二)建立一个有向图+遍历+插入+删除 (1)以邻接表作为图的存储结构，从键盘输入图的顶点与弧的信息建立一个有向图； (2)对（1）中生成的有向图进行深度优先遍历并打印结果； (3)在（1）中生成的有向图中，分别插入与删除一条弧并打印其结果； (4)在（1）中生成的有向图中，分别插入与删除一个顶点并打印结果； (5)在（1）中生成的有向图中,各顶点的入度与出度并打印结果； 三）基本应用题 （1）编写算法，判断图中指定的两个顶点是否连通。 （2）编写算法，判断图的连通性。如果不连通，求连通分量的个数 （3）编写算法，判断图中任意两个顶点的连通性 （4）编写算法，判断图中是否存在回路。 （5）实现图的广度优先搜索算法。 四）高级应用题 （1）实现Prim算法 （2）实现Kruskal算法 （3）实现迪杰斯特拉算法 （4）实现拓扑排序算法 （5）实现关键路径算法 数据结构实验报告 专业班级： 指导老师：余腊生 姓 名： 学 号： 实验一 单链表的基本操作的实现 一、实验目的 掌握单链表的基本操作：建立、插入、删除、查找等运算。 二、实验仪器 安装VC++的PC机。 三、实验原理 利用线性表的特性以及其链式存储结构特点对线性表进行相关操作。 四、实验内容 程序中演示了单链表的创建、插入、删除和查找。程序如下： #include scanf(“%d”,&x);while(x!=-1){ p=(NODE *)malloc(sizeof(NODE));p->data=x;p->next=head->next;head->next=p;scanf(“%d”,&x);} return(head);} /******************************************/ void Output(NODE *head){ NODE *p;p=head;printf(“Begin to dump the LinkList...n”);while(p->next!=NULL){ printf(“->%d”,p->next->data);p=p->next;} printf(“nThe LinkList ended!n”);} /******************************************/ int Listlen(NODE *head){ int i=0;NODE *p=head;while(p->next!=NULL){ i++;p=p->next;} return(i);} /******************************************/ int Get(NODE *head,int i){ int j=0;NODE *p=head;while(p->next&&j 五、数据记录及处理 1、运行程序,输入下面一组数据: 93 94 12 13 20 14 链表顺序：14 20 13 12 94 93 2、删除第二个数据结点，在第一个位置插入数据20。 运行结果如下: 插入结果：14 13 12 94 93 删除结果：20 14 13 12 94 93 运行结果截图： 实验二 栈和队列的实现 一、目的和要求 1.理解队列和栈的顺序存储结构和链式存储结构。通过本实验，熟悉队列、栈的结构特点； 2.熟悉队列、栈结构上的操作与算法的实现。 二、实验内容 1.队列的基本操作和应用。2.栈的基本操作和应用。 三、仪器、设备和材料 1.适合实验要求的计算机系统。2.VＣ++编程平台。 四、实验原理 队列与栈是一种操作受限制的线性表，在了解线性表的基本原理的基础上，理解与完成此项实验。 五、实验步骤 1.采用队列的顺序存储结构。 2.用菜单的形式完成队列的建立，出队，入队等基本操作。3.采用栈的链式存储结构。 4.用菜单的形式完成栈的出栈、入栈等基本操作。 六、程序算法 #include SElemType *top;}SqStack; SqStack InitStacka()//顺序存储实现栈的初始化 {SqStack S;S.base=(SElemType *)malloc(MAX*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;return(S);} void Pusha(SqStack &S,int x)//顺序存储实现栈的入栈操作 {if(S.top-S.base>=MAX)exit(OVERFLOW);*S.top++=x;} void Popa(SqStack &S)//顺序存储实现栈的出栈操作 {SElemType *p;int x;if(S.top==S.base)return;else {p=S.top;x=*--S.top;printf(“t删除的栈顶元素是%dnt出栈操作完成后的栈为:n”,x);} } void printa(SqStack S)//输出 {SElemType *p;p=S.base;printf(“t”);while(p!=S.top){printf(“%d ”,*(p++));} printf(“n”);} typedef struct SqNode {SElemType data;SqNode *Link;}*Sqptr,NODE;typedef struct {Sqptr top;}Stack; Stack InitStackb()//链式存储实现栈的初始化 {Stack S;S.top=(Sqptr)malloc(sizeof(NODE));if(!S.top)exit(OVERFLOW);S.top->Link=NULL;return(S);} void Pushb(Stack &S,int x)//链式存储实现栈的入栈操作 {Sqptr p;p=(Sqptr)malloc(sizeof(NODE));if(!p)return;p->data=x;p->Link=S.top->Link;S.top->Link=p;} void Popb(Stack &S)//链式存储实现栈的出栈操作 {int x;Sqptr p;if(S.top->Link==NULL)return;else {p=S.top->Link; x=p->data; S.top->Link=p->Link; printf(“t删除的栈顶元素是%dn”,x); free(p);} } typedef struct QNode {QElemType data;struct QNode *next;}*QueuePtr,QNode;typedef struct {QueuePtr front;QueuePtr rear;}LinkQueue;LinkQueue InitQueue()//链式存储实现队列的初始化 {LinkQueue Q;Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL; return(Q);} void EnQueue(LinkQueue &Q,QElemType x)//链式存储实现队列的入队 {QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=x;p->next=NULL;Q.rear->next=p;Q.rear=p;} void DeQueue(LinkQueue &Q)//链式存储实现队列的出队 {int x;if(Q.front==Q.rear)return;QueuePtr p;p=Q.front->next;x=p->data;printf(“t删除的队头元素是：%dn”,x);Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);return;} typedef struct {SElemType *base;int front,rear;}SqQueue;SqQueue InitQueueb()//顺序存储实现队列的初始化 {SqQueue S;S.base=(SElemType *)malloc(MAX*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.front=S.rear=0;return(S);} void EnQueueb(SqQueue &S,int x) //顺序存储实现队列的入队 {if((S.rear+1)%MAX==S.front)return;S.base[S.rear]=x;S.rear=(S.rear+1)%MAX;} void DeQueueb(SqQueue &S)//顺序存储实现队列的出队 {int x;if(S.front==S.rear)return;x=S.base[S.front];S.front=(S.front+1)%MAX;printf(“t删除的队头元素是:%dn”,x);} void main(){int choice;int n,x;printf(“nn”);printf(“t1.采用链式存储实现栈的初始化、入栈、出栈操作n”);printf(“t2.采用顺序存储实现栈的初始化、入栈、出栈操作n”);printf(“t3.采用链式存储实现队列的初始化、入队、出队操作n”);printf(“t4.采用顺序存储实现队列的初始化、入队、出队操作n”);printf(“t请选择:”);scanf(“%d”,&choice);switch(choice){case 1:Stack Sa; printf(“t1.链式存储实现栈的初始化n”); printf(“t2.链式存储实现栈的入栈操作n”); printf(“t3.链式存储实现栈的出栈操作n”); while(1){ printf(“t请选择：”); scanf(“%d”,&n); switch(n) {case 1:Sa=InitStackb(); printf(“t链式存储栈的初始化完成!n”);break; case 2:printf(“t以'0'结束n”);printf(“t”); scanf(“%d”,&x); while(x){ Pushb(Sa,x);scanf(“%d”,&x);} printf(“t链式存储栈的入栈操作完成!n”);break; case 3:Popb(Sa);break;}}break; case 2:SqStack S; printf(“t1.顺序存储实现栈的初始化n”); printf(“t2.顺序存储实现栈的入栈操作n”); printf(“t3.顺序存储实现栈的出栈操作n”); while(1){ printf(“t请选择:”); scanf(“%d”,&n); switch(n) { case 1:S=InitStacka(); printf(“t顺序存储栈的初始化完成!n”);break; case 2:printf(“t以'0'结束n”); printf(“t”); scanf(“%d”,&x); while(x){ Pusha(S,x); scanf(“%d”,&x);} printf(“t顺序存储栈的入栈操作完成!n”); printa(S);break; case 3:Popa(S); printa(S);break;}}break; case 3:LinkQueue Q; printf(“t1.链式存储实现队的初始化n”); printf(“t2.链式存储实现队的入栈操作n”); printf(“t3.链式存储实现队的出栈操作n”); while(1){ printf(“t请选择：”); scanf(“%d”,&n); switch(n) { case 1:Q=InitQueue(); printf(“t链式存储队的初始化完成!n”);break; case 2:printf(“t以'0'结束n”);printf(“t”);scanf(“%d”,&x); while(x){ EnQueue(Q,x);scanf(“%d”,&x);} printf(“t链式存储队的入栈操作完成!n”);break; case 3:DeQueue(Q);break;}}break; case 4:SqQueue Sv; printf(“t1.顺序存储实现队的初始化n”); printf(“t2.顺序存储实现队的入栈操作n”); printf(“t3.顺序存储实现队的出栈操作n”); while(1){ printf(“t请选择：”); scanf(“%d”,&n); switch(n) {case 1:Sv=InitQueueb(); printf(“t链式存储栈的初始化完成!n”);break; case 2:printf(“t以'0'结束n”);printf(“t”);scanf(“%d”,&x); while(x){ EnQueueb(Sv,x);scanf(“%d”,&x);} printf(“t链式存储栈的入栈操作完成!n”);break; case 3: DeQueueb(Sv);break;}}break;} } 程序调试截图： 1.采用链式存储实现栈的初始化、入栈、出栈操作 2.采用顺序存储实现栈的初始化、入栈、出栈操作 3.采用链式存储实现队列的初始化、入队、出队操作 4.采用顺序存储实现队列的初始化、入队、出队操作 七、心得体会 实践才能出真知，在通过了上机操作后，才发现了许多在平时上理论课的时候没有想到的方方面面，编写程序时发现很多语法的错误，以及很多英语单词的记不熟，记错，程序函数错用等等，我想需要在以后多多练习，才能逐步解决这些问题。实验三 二叉树的建立和遍历 一、目的和要求 1、了解二叉树的建立的方法及其遍历的顺序，熟悉二叉树的三种遍历 2、检验输入的数据是否可以构成一颗二叉树 二、实验内容 1.二叉树的建立和遍历 三、仪器、设备和材料 1.适合实验要求的计算机系统。2.VＣ++编程平台。 四、实验的描述和算法 1、实验描述 二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。因为耳熟的每一个左右子树又是一颗二叉树，所以可以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个节点访问完并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句实现。 2、算法 #include //二叉树结点类定义 { T data; //数据域 BinTreeNode //左子女、右子女域 BinTreeNode(T x=T(),BinTreeNode :data(x),leftChild(l),rightChild(r){} //可选择参数的默认构造函数 };//-----------template //非递归前序遍历 { stack while(p!=NULL) { cout< data; //访问根结点 S.push(p); p=p->leftChild; //遍历指针进到左子女结点 } if(!S.empty()) //栈不空时退栈 { p=S.top(); S.pop(); p = p->rightChild; //遍历指针进到右子女结点 } } } //--template //非递归中序遍历 { stack while(p!=NULL) //遍历指针未到最左下的结点，不空 { S.push(p); p=p->leftChild; } if(!S.empty()) //栈不空时退栈 { p=S.top(); S.pop(); cout< data; p=p->rightChild; } } while(p!=NULL ||!S.empty());} //----template while(p!= NULL ||!S.empty()) //左子树经过结点加L进栈 { while(p!=NULL) { S.push(p);//首先将t和tag为入栈，遍历左子树 tag.push(0);//遍历左子树前的现场保护 p=p->leftChild; } while(!S.empty()&& tag.top()==1) { p=S.top(); S.pop(); tag.pop(); cout< data;//最后访问根结点。 } if(!S.empty()) { tag.pop(); tag.push(1);//遍历右子树前的现场保护,修改栈顶tag为，遍历右子树 p=S.top(); // 取栈顶保存的指针 p=p->rightChild; } else break; } } template if(subTree!=NULL) //NULL是递归终止条件 { InOrder_1(subTree->leftChild);//中序遍历根的左子树 cout< //访问根结点 InOrder_1(subTree->rightChild);//中序遍历根的右子树 } } template //递归结束条件 { cout< PreOrder_1(subTree->leftChild); //前序遍历根的左子树 PreOrder_1(subTree->rightChild); //前序遍历根的右子树 } } template if(subTree!=NULL) //NULL是递归终止条件 { PostOrder_1(subTree->leftChild);//后序遍历根的左子树 PostOrder_1(subTree->rightChild);//后序遍历根的右子树 cout< //访问根结点 } } //------------template T item; cin>>item; if(item!=-1) { subTree = new BinTreeNode if(subTree == NULL) { cerr<<“存储分配错！”< exit(1); } subTree->data = item; CreateBinTree(subTree->leftChild);//递归建立左子树 CreateBinTree(subTree->rightChild);//递归建立右子树 } else subTree = NULL; //封闭指向空子树的指针 } int main(){ BinTreeNode cout<<“先序遍历二叉树结果：”; PreOrder_1(Tree); cout< cout<<“后序遍历二叉树结果：”; PostOrder_1(Tree);cout< cout<<“非递归中序遍历二叉树结果：”;InOrder_2(Tree);cout< 3、实验程序运行截图 实验四 散列法查找和排序 一、目的和要求 1.用散列法实现顺序查找，折半查找。 二、仪器、设备和材料 1.适合实验要求的计算机系统。2.VＣ++编程平台。 三、实验步骤 和程序 1、顺序查找 #include #define NULLKEY 0 typedef int KeyType; /* 假设关键字为整型 */ typedef struct { KeyType key;}RecordType;typedef RecordType HashTable[m];int hash(KeyType k)/*除留余数法构造哈希函数*/ { int h;h = k%m;return h;} int HashSearch(HashTable ht, KeyType K)/*哈希查找*/ { int h0;int i;int hi;h0=hash(K);if(ht[h0].key==NULLKEY) return(-1);else if(ht[h0].key==K) return(h0); else /* 用线性探测再散列解决冲突 */ { for(i=1;i<=m-1;i++) { hi=(h0+i)% m; if(ht[hi].key==NULLKEY) return(-1); else if(ht[hi].key==K) return(hi); } return(-1); } } void main(){ int i,j;int n;int p;int hj;int k;int result;HashTable ht;for(i=0;i ht[i].key = NULLKEY;printf(“请输入哈希表的元素个数:”);scanf(“%d”,&n);for(i=1;i<=n;i++){ printf(“请输入第%d个元素:”,i); fflush(stdin); scanf(“%d”,&p); j = hash(p); if(ht[j].key == NULLKEY) ht[j].key = p; else { for(i=1;i<=m-1;i++) { hj=(j+i)% m; if(ht[hj].key==NULLKEY) { ht[j].key = p; } i = m; } } } } printf(“请输入要查找的元素:”);fflush(stdin);scanf(“%d”,&k);result = HashSearch(ht,k);if(result ==-1)printf(“未找到!n”);else printf(“元素位置为%dn”,result);system(“pause”);运行结果如下： 2、折半查找 #include printf(“你输入的数不正确，请重新输入:n”); printf(“你想在多少个数中进行折半查找，请输入(1--20):”); scanf(“%d”,&n);} printf(“请你输入一个整数a[1]:”);scanf(“%d”,&a[1]);i=2;while(i<=n){ printf(“请你输入一个整数a[%d]:”,i); scanf(“%d”,&a[i]); i++;} printf(“n输出表列n”);for(i=1;i<=n;i++){ printf(“%6d”,a[i]);} printf(“n”);printf(“请你输入要查找的数:”);scanf(“%d”,&num);flag=1;top=n;bottom=1;mid=(top+bottom)/2;while(flag){ printf(“top=%d，bottom=%d，mid=%d,a[i]=%dn”,top,bottom,mid,mid,a[mid]);if((num>a[top])||(num loc=-1; flag=0;} else if(a[mid]==num){ loc=mid; printf(“找到数 %6d的位置%2dn”,num,loc); break;} else if(a[mid]>num){ top=mid-1; mid=(top+bottom)/2;} else if(a[mid] bottom=mid+1; mid=(top+bottom)/2;} } if(loc==-1){ printf(“%d这个数在表列中没有找到。n”,num);} } 运行结果如下： 北京邮电大学信息与通信工程学院 数据结构实验报告 实验名称： 实验二——图 学生姓名： 佘晨阳 班 级： 2014211117 班内序号： 20 学 号： 2014210491 日 期： 2015年12月05日 1．实验要求 根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能： 1、图的建立 2、图的销毁 3、深度优先遍历图 4、广度优先遍历图 5、使用普里姆算法生成最小生成树 6、使用克鲁斯卡尔算法生成最小生成树 7、求指定顶点到其他各顶点的最短路径 8、其他：比如连通性判断等自定义操作 编写测试main()函数测试图的正确性 2.程序分析 本实验要求掌握图基本操作的实现方法，了解最小生成树的思想和相关概念，了解最短路径的思想和相关概念，学习使用图解决实际问题的能力。 2.1 存储结构 存储结构：1.不带权值的无向图邻接矩阵 2.带权值的无向图邻接矩阵 3.带权值的有向图邻接矩阵 1．不带权值的无向图邻接矩阵 第1页 北京邮电大学信息与通信工程学院 2带权值的无向图邻接矩阵.3.带权值的有向图邻接矩阵 [备注]： 1.在使用打印元素、BFS、DFS 采用无权值的无向图邻接矩阵存储方式 2.在使用PRIM、KRUSKAL、3.在使用最短路径的算法时采用具有权值的有向图邻接矩阵存储方式 2.2 关键算法分析 第2页 北京邮电大学信息与通信工程学院 一．图的邻接矩阵构造函数： 1.关键算法： template //带权值的图的构造函数 { int i, j, k, height;f s1, s2;vnum = n;arcnum = e;for(k = 0;k < n;k++){ vertex[k] = a[k];} //初始化顶点 for(k = 0;k for(i = 0;i < n;i++) { arc[k][i] =-1; if(i == k)arc[k][i] = 0; //初始化权值的大小 } visited[k] = 0;} cout << endl;for(k = 0;k //初始化边 { cout << “请输入线性链接节点:”; cin >> s1 >> s2 >> height; arc[convert(s1)][convert(s2)] = height; arc[convert(s2)][convert(s1)] = arc[convert(s1)][convert(s2)];//采用无向图带权值的邻接矩阵 } cout << endl;cout << “所得邻接矩阵为：” << endl; for(k = 0;k for(i = 0;i < n;i++) { if(arc[k][i] ==-1) cout << “∞” << “ ”; else cout << arc[k][i] << “ ”; //打印邻接矩阵的格式 } cout << endl; } cout << endl 2.算法的时间复杂度 第3页 北京邮电大学信息与通信工程学院 有构造可知，初始化时其时间复杂度：O(n2) 二．深度优先便利DFS: 1.关键算法 ①从某顶点v出发并访问 ②访问v的第一个未访问的邻接点w，访问w的第一个未访问的邻接点u，…… ③若当前顶点的所有邻接点都被访问过，则回溯，从上一级顶点的下一个未访问过的顶点开始深度优先遍历 ④直到所有和v路径相通的顶点都被访问到； 2.代码图解： 深度优先遍历示意图 3.代码详解： template for(int j = 0;j < vnum;j++) //连通图 if((visited[j] == 0)&&(arc[v][j] >= 1))DFS(j);//当存在回路时，则连通深一层遍历 } 4.时间复杂度 时间复杂度：O(n2) 空间复杂度：栈的深度O(n) 辅助空间O(n) 第4页 北京邮电大学信息与通信工程学院 三．广度遍历BFS 1.关键算法 ①访问顶点v ②依次访问v的所有未被访问的邻接点v1,v2,v3… ③分别从v1,v2,v3…出发依次访问它们未被访问的邻接点 ④反复①②③，直到所有和v路径相通的顶点都被访问到； 2.代码图解 3.代码详解 1.初始化队列Q 2.访问顶点v，visited[v]=1 3.while(队列非空) 3.1 v=队头元素出队 3.2 访问队头元素的所有未访问的邻接点 4.时间复杂度 时间复杂度：O(n2) 空间复杂度：辅助空间O(n) 四.最小生成树——普里姆算法 1,关键思路 一般情况下，假设n个顶点分成两个集合：U(包含已落在生成树上的结点)和V-U(尚未落在生成树上的顶点)，则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。主数据结构： 邻接矩阵 辅助数据结构： int adjvex[MAXSIZE];// U集中的顶点序号 第5页 北京邮电大学信息与通信工程学院 int lowcost[MAXSIZE]; // U(V-U)的最小权值边 2.代码图解 第6页 北京邮电大学信息与通信工程学院 第7页 北京邮电大学信息与通信工程学院 3;代码详解 template //辅助数组存储所有到的V0边 { adjvex[i] = 0;lowcost[i] = arc[0][i]; } lowcost[0] = 0;for(int j = 1;j < vnum;j++) //循环n-1次 { int k = Mininum(lowcost); //求下一个顶点 cout << vertex[adjvex[k]] << “->” << vertex[k] << endl; lowcost[k] = 0; //U=U+{Vk} for(int j = 0;j < vnum;j++) //设置辅助数组 { if((lowcost[j]!= 0 && arc[k][j] < lowcost[j])) { lowcost[j] = arc[k][j]; adjvex[j] = k; } } 第8页 北京邮电大学信息与通信工程学院 } } 4,时间复杂度： 时间复杂度O(n2)，适合稠密图 五.最小生成树----克鲁斯卡尔算法 1,关键思路 先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。2.代码图解： 3.代码详解 template //最小生成树—kruskal算法 { cout<<“Krusal算法结果为：”< int k = 0, j = 0; while(k < vnum-1){ int m = vedgelist[j].fromv, n = vedgelist[j].endv; int sn1 = vset[m]; int sn2 = vset[n]; //两个顶点分属 第9页 北京邮电大学信息与通信工程学院 不同的集合 if(sn1!= sn2) { cout << vertex[m] << “->” << vertex[n] << endl; k++; for(int i = 0;i < vnum;i++) { if(vset[i] == sn2) vset[i] = sn1; //集合sn2全部改成sn1 } } j++;} } 4.时间复杂度 时间复杂度O(nlogn)，适合稀疏图 六．最短路径——Dijkstra算法 1.关键代码 • 按路径长度递增的次序产生源点到其余各顶点的最短路径。• 1)设置集合s存储已求得的最短路径的顶点，• 2)初始状态：s=源点v • 3)叠代算法： • 直接与v相连的最近顶点vi,加入s • 从v经过vi可以到达的顶点中最短的，加入s …… 2.代码图解 第10页 北京邮电大学信息与通信工程学院 3.代码详解 emplate //关于最短路径的初始化 { int v=convert(x); for(int i = 0;i < vnum;i++) //初始化路径和点 { s[i]=0; disk[i] = arc[v][i]; if(disk[i]!= maxs)path[i] = v; else path[i] =-1;} s[v] = 1;disk[v] = 0;path[v]=-1;for(int i = 0;i < vnum;i++) //反复经过从该点到其他点的路径 { if((v = FindMin())==-1)continue; s[v] = 1; for(int j = 0;j < vnum;j++) if(!s[j] &&(disk[j]>arc[v][j] + disk[v])) { 第11页 北京邮电大学信息与通信工程学院 disk[j] = arc[v][j] + disk[v]; path[j] = v; } } Print(); //打印路径长度和遍历 } 4.时间复杂度 时间复杂度为：n^2 七．判断连通图算法 template { cout<<“该图为连通图！*******输入成功！”< return false; } else { cout<<“该图不为连通图！*******请重新输入”< return true; } } 时间复杂度：n^2 3.程序运行结果 1.测试主函数流程： 第12页 北京邮电大学信息与通信工程学院 函数流程图： 1.输入图的连接边并打印 构造下面所示图的邻接矩阵： 第13页 北京邮电大学信息与通信工程学院 2.判断图连通是否成功 3.BFS DFS PRIM算法的实现 第14页 北京邮电大学信息与通信工程学院 4.克鲁斯卡尔算法实现过程 4.有向图邻接矩阵的构建 第15页 北京邮电大学信息与通信工程学院 插入V0位置后打印距离并开始回溯 总结 1.调试时出现的问题及解决的方法 问题一：prim算法中 解决方法：调整循环条件，修正函数体注意有无Next的区别 第16页 北京邮电大学信息与通信工程学院 问题二：BFS和DFS同时在一个类里作用时会输出错误 解决方案：每次BFS/DFS使用时都把visited数组初始化一遍 问题三：在最短路径，经常出现了停止输入的情况 解决方法：改return为continue，并修改打印算法 2.心得体会 通过本次实验，基本熟练掌握了c++基本语句，尤其对图的结构及应用有了较深了解；调试代码时尽量做到完成一个代码段调试一次，可以最快检测出错误所在；类的封装和调用，类的共有成员和私有成员的设置。 3.下一步的改进 第一，设置增加图节点和边的函数 第二，实现图形化输出图的路径的功能 第三，主函数设计简单，不要过于累赘 4.程序中出现的亮点 1)利用dfs算法衍生生成判断是否为连通图的连通算法 2)采用graph类实现所有图的所有算法，所需的数据类型均在私有成员内，封装 3)利用convert函数采取象意输入，采用ABCD的节点输入方式而并非转化成01234再输入。 4)BFS中采用c++标准库的。 5)打印邻接矩阵时，打印出非链接的∞符号和与自身路径的0距离 6)判断图为非连通图后，提示输入错误，重新输入图元素 第17页第二篇：数据结构实验报告(报告+C语言源代码)
第三篇：数据结构上机实验--图
第四篇：中南大学 数据结构实验报告
第五篇：数据结构 实验一 图[推荐]
点击咨询 