图的遍历2 数据结构实验报告
南昌航空大学实验报告
课程名称：数据结构实验名称：实验八图的遍历
班级：学生姓名：学号：
指导教师评定：签名:
题目：假设无向图采用邻接表结构表示。编程分别实现图的深度优先搜索算法和广度优先搜索算法。
一、需求分析
1.用户可以根据自己的需求进行输入所需的图（可以是非连通图也可以是连通图），其中1
表示创建一个有向图，2表示创建一个无向图。
2.用户进入菜单页面选择输入图的状态（1表示创建一个有向图，2表示创建一个无向图，
3表示输出已创建的图，4表示深度优先遍历已有的图，5表示广度优先遍历已有的图，6表示退出程序状态）。
3.程序执行的命令包括：
（1）输入图的结点和弧构造图（2）输出图（2）广度优先遍历图（3）深度优先遍历图
二、概要设计
⒈为实现上述算法，需要链表的抽象数据类型：
ADT Graph {
数据对象V：V是具有相同特征的数据元素的集合，称为顶点集。
数据关系R：
R={VR}
VR={
基本操作P:
Creatgraph(&G,V,VR)
初始条件：V是图的顶点集，VR是图中弧的集合。
操作结果：按V和VR的定义构造图G。
destroygraph(&G)
初始条件：图G存在。
操作结果：销毁图G。
displaygraph（G）
初始条件：图G存在。
操作结果：显示图G。
locatevex(G,u)
初始条件：图G存在，u和G中的顶点有相同的特征。
操作结果：若G中存在顶点u，则返回该顶点在图中位置，否则返回
其他信息。
getvex(G,v)
初始条件：图G存在，v是G中的某个顶点。
操作结果：返回v的值。
DFStraverse (G)
初始条件：图G存在。
操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点访问一
次。
BFStraverse (&S,e)
初始条件：图G存在。
操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点访问一
次。
}ADT Graph
2. 本程序有三个模块：
⑴主程序模块
main(){
初始化；
Switch（参数）{
Case 1 ：接受命令（用户创建一个有向图）；
Case 2 ：接受命令（用户创建一个无向图）；
Case 3 ：接受命令（输出已创建的图）；
Case 4 ：接受命令（深度优先遍历已有的图）；
Case 5 ：接受命令（广度优先遍历已有的图）；
Case 6 ：接受命令（退出程序）；
｝
｝
⑵创建图的模块：主要建立一个图；
⑶广度优先遍历和深度优先遍历模块：输出这两种遍历的结果；
(4)输出图模块：显示已创建的图。
三、详细设计
⒈元素类型，结点类型
struct arcnode
{ int adjvex; /*该弧所指向的顶点的位置*/
int info;
struct arcnode *nextarc; /*指向下一条弧的指针*/
};
struct vexnode
{ int data; /*顶点的信息*/
struct arcnode *firstarc; /*指向第一条依附该顶点的弧的指针*/
};
struct graph
{ struct vexnode *vexpex;
int vexnum,arcnum; /*图的当前的顶点数和弧数*/
}；
/*定义队列*/
struct queue
{
int *elem;
int front;
int rear;
};
/*全局变量*/
int n; /*图的顶点数*/
int visit[100]; /*标志数组*/
struct queue Q;
2.对抽象数据类型中的部分基本操作的伪码算法如下：/*创建一个空队列*/
struct queue initqueue()
{ struct queue q;
q.elem=(int *)malloc(maxsize*sizeof(int)); if(!q.elem) exit(0);
q.front=q.rear=0;
return q;
}
/*入队列*/
struct queue enqueue(struct queue q,int v ) { if((q.rear+1)%maxsize==q.front)
printf("the queue is full！！！\n");
else
{ q.elem[q.rear]=v;
q.rear=(q.rear+1)%maxsize;
}
return q;
}
/*出队列*/
int dequeue(struct queue q)
{ int cur;
if(q.rear==q.front)
{ printf("the queue is null!!\n");
exit(0);
}
else
{ cur=q.elem[q.front];
q.front=(q.front+1)%maxsize;
return cur;
}
}
/*判断队列是否为空*/
int emptyqueue(struct queue q)
{ if(q.front==q.rear)
return 1;
else
return 0;
}
/*创建有向图*/
struct graph creatgraph1()
{ int e,i,s,d;
int a;
struct graph g;
struct arcnode *p;
printf("the number of vex(n) and arc(e):");
scanf("%d%d",&n,&e);
g.vexnum=n;
g.arcnum=e;
for(i=0;i { printf("di %d vex's information:",i); scanf("%d",&a); g.vexpex[i].data=a; g.vexpex[i].firstarc=NULL; } for(i=0;i { printf("di %d arc's start,end:",i+1); scanf("%d%d",&s,&d); p=(struct arcnode *)malloc(sizeof(struct arcnode)); p->adjvex=d; p->info=g.vexpex[d].data; p->nextarc=g.vexpex[s].firstarc; g.vexpex[s].firstarc=p; } return g; } /*创建无向图*/ struct graph creatgraph2() { int e,i,s,d; int a; struct graph g; struct arcnode *p,*q; printf("the number of vex(n) and arc(e):"); scanf("%d%d",&n,&e); g.vexnum=n; g.arcnum=e; for(i=0;i { printf("di %d vex's information:",i); scanf("%d",&a); g.vexpex[i].data=a; g.vexpex[i].firstarc=NULL; } for(i=0;i { printf("di %d arc's start,end:",i+1); scanf("%d%d",&s,&d); p=(struct arcnode *)malloc(sizeof(struct arcnode)); p->adjvex=d; p->info=g.vexpex[d].data; p->nextarc=g.vexpex[s].firstarc; g.vexpex[s].firstarc=p; q=(struct arcnode *)malloc(sizeof(struct arcnode)); q->adjvex=s; q->info=g.vexpex[s].data; q->nextarc=g.vexpex[d].firstarc; g.vexpex[d].firstarc=q; } return g; } /*显示有向图*/ void displaygraph(struct graph g,int n) { int i; struct arcnode *p; printf("diaplay the graph;\n"); for(i=0;i { printf(" [%d,%d]->",i,g.vexpex[i].data); p=g.vexpex[i].firstarc; while(p!=NULL) { printf("(%d,%d)->",p->adjvex,p->info); p=p->nextarc; } printf("^\n"); } } /*连通图广度优先遍历*/ void BFSsearch(struct graph g,int v) { int i; struct arcnode *p; Q=initqueue(); printf("%5d",g.vexpex[v].data); enqueue(Q,v); visit[v]=TURE; while(!emptyqueue(Q)) { i=dequeue(Q); p=g.vexpex[i].firstarc; while(p!=NULL) { enqueue(Q,p->adjvex); if(visit[p->adjvex]==FALSE) { printf("%5d",p->info); visit[p->adjvex]=TURE; } p=p->nextarc; } } } /*非连通图广度优先遍历*/ void BFS(struct graph g) { int i; printf("BFS result:\n"); for(i=0;i visit[i]=FALSE; for(i=0;i if(visit[i]==FALSE) BFSsearch(g,i); printf("\n\n"); } /*连通图深度优先遍历*/ void DFSsearch(struct graph g,int v) { struct arcnode *p; printf("%5d",g.vexpex[v].data); visit[v]=TURE; p=g.vexpex[v].firstarc; while(p!=NULL) { if(!visit[p->adjvex]) DFSsearch(g,p->adjvex); p=p->nextarc; } } /*非连通图深度优先遍历*/ void DFS(struct graph g) { int i; printf("DFS result:\n"); for(i=0;i for(i=0;i if(visit[i]==FALSE) DFSsearch(g,i); printf("\n\n"); } /*-----主菜单定义-----*/ int menu_select() { char s[80]; int c; gotoxy(1,25); /*将光标定在第25行第1列*/ printf("press any key enter menu ......\n"); /*提示按任意键继续*/ getch(); /*读入任意字符*/ clrscr(); /*清屏*/ gotoxy(1,1); printf("***************MENU***************\n\n"); printf(" 1. Make a digraph by youself!\n"); printf(" 2. Make a undigraph by youself!\n"); printf(" 3. Ontput your graph!\n"); printf(" 4. Depth_first search your graph!\n"); printf(" 5. Bredth_first search your graph!\n"); printf(" 6. Quit!\n"); printf("**********************************\n"); do{ printf("\n Enter you choice (1~6):\n"); /*提示输入选项*/ scanf("%s",s); /*输入选择项*/ c=atoi(s); /*将输入的字符串转化为整型*/ }while(c<1||c>6); return c; } 3.主函数和其他函数的伪码算法 void main() { struct graph g; int i; clrscr(); /*清屏*/ for(;;) { switch(menu_select()) { case 1: { clrscr(); g=creatgraph1(); break; } case 2: { clrscr(); g=creatgraph2(); break; } case 3: { clrscr(); printf("diaplay the graph;\n"); displaygraph(g,n); break; } case 4: { clrscr(); printf("DFS result:\n"); DFS(g); break; } case 5: { clrscr(); printf("BFS result:\n"); BFS(g); break; } case 6: exit(0); } } } 4 函数调用关系 main creatgraph displaygraph BFS DFS BFSsearch DFSsearch initqueue dequeue enqueue 四、调试分析 ⒈本来想将图的顶点元素的类型定义为字符型的，但是在运行的时候发现在输入顶点数和弧 数后，总是会在有字符没有输入就直接运行下一个语句了，改变了很多的方法，最后只 有将顶点的类型定义为才解决了上述的问题。 ⒉在写程序的时候，开始creatgraph函数的部分代码为 for(i=0;i { printf("di %d vex's information:",i); scanf("%d",&a); g.vexpex[i].data=a; g.vexpex[i].firstarc=NULL; } g.vexnum=n; g.arcnum=e; 总是会有这样的提示“可能在‘g’定义以前已经使用了在creatgraph函数中”，经过多 次的调试，最后代码改为 g.vexnum=n; g.arcnum=e; for(i=0;i { printf("di %d vex's information:",i); scanf("%d",&a); g.vexpex[i].data=a; g.vexpex[i].firstarc=NULL; } 就解决了问题，但是我还是不清楚原因。 3.在编写BFSsearch函数的时候，用指针入队还是用下标值入队，由于对指针的掌握不够， 最后选择了比较容易的用下标值作为队列的类型int。 4.在调试的时候，选择选项3、4、5的时候总是没有执行printf语句，最后分别在主函数和要调用的函数中都加上同一printf语句就解决了问题，能够显示printf中的信息。 5. 算法的时空分析 各操作的算法时间复杂度比较合理 initqueue，emptyqueue，enqueue，dequeue，visit为O(1)；creatgraph ，displaygraph1， displaygraph2BFSsearch，DFS，DFSsearch，BFS为O(n), 注：n为图的顶点数。 6.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使调 试也较顺利，各模块有较好的可重用性。 五、用户手册 ⒈本程序的运行环境为windows xp操作系统，并且在TC2.0中运行，执行文件为Exp8.c； ⒉.在输入有向图的信息的时候，注意输入的顺序，这关系到顶点的位置，否则就会与你想 要的图就不一样了。如你的图为 18 22 20 21 若你输入的顶点的顺序是20,18 ，21，22则它们对应的数值的下标为0,1,2，3。因此表示的弧（起点，终点）就应该为（0,2），（1,0），（2,1），（3,0），（3,2），但是弧输入的顺序没有要求。而创建无向图的时候就没有这个要求了，只要输入能表示该边的两个正确的端点即可。 3.按任意键进入主菜单如图： 注：1：表示创建一个有向图； 2：表示创建一个无向图； 3：表示输出已创建的图； 4：表示深度优先遍历已有的图； 5：表示广度优先遍历已有的图； 6：表示退出程序状态。 4. 进入演示程序后，完成编译，再点击超级工具集里的中文DOS环境运行选项，进入DOS 环境中，用户根据需求键入相应的数据，可以看到相应的结果。 六、测试结果 若想创建一个无向图（在主菜单选择2）： 56 57 10 18 19 11 12 20 13 则在主菜单选择2输入的图如图所示： 按任意键进入主菜单选择3，输出图为： 按任意键进入主菜单选择4，输出DFS的结果： 按任意键进入主菜单选择5，输出BFS的结果: 按任意键进入主菜单选择6，退出程序。 七、附录：源程序 #include #include #include #include #include #define NULL 0 #define FALSE 0 #define TURE 1 #define maxsize 100 struct arcnode { int adjvex; /*该弧所指向的顶点的位置*/ int info; struct arcnode *nextarc; /*指向下一条弧的指针*/ }; struct vexnode { int data; /*顶点的信息*/ struct arcnode *firstarc; /*指向第一条依附该顶点的弧的指针*/ }; struct graph { struct vexnode *vexpex; int vexnum,arcnum; /*图的当前的顶点数和弧数*/ }; /*定义队列*/ struct queue { int *elem; int front; int rear; }; int n; /*图的顶点数*/ int visit[100]; /*标志数组*/ struct queue Q; /*创建一个空队列*/ struct queue initqueue() { struct queue q; q.elem=(int *)malloc(maxsize*sizeof(int)); if(!q.elem) exit(0); q.front=q.rear=0; return q; } /*入队列*/ struct queue enqueue(struct queue q,int v ) { if((q.rear+1)%maxsize==q.front) printf("the queue is full！！！\n"); else { q.elem[q.rear]=v; q.rear=(q.rear+1)%maxsize; } return q; } /*出队列*/ int dequeue(struct queue q) { int cur; if(q.rear==q.front) { printf("the queue is null!!\n"); exit(0); } else { cur=q.elem[q.front]; q.front=(q.front+1)%maxsize; return cur; } } /*判断队列是否为空*/ int emptyqueue(struct queue q) { if(q.front==q.rear) return 1; else return 0; } /*创建有向图*/ struct graph creatgraph1() { int e,i,s,d; int a; struct graph g; struct arcnode *p; printf("the number of vex(n) and arc(e):"); scanf("%d%d",&n,&e); g.vexnum=n; g.arcnum=e; for(i=0;i { printf("di %d vex's information:",i); scanf("%d",&a); g.vexpex[i].data=a; g.vexpex[i].firstarc=NULL; } for(i=0;i { printf("di %d arc's start,end:",i+1); scanf("%d%d",&s,&d); p=(struct arcnode *)malloc(sizeof(struct arcnode)); p->adjvex=d; p->info=g.vexpex[d].data; p->nextarc=g.vexpex[s].firstarc; g.vexpex[s].firstarc=p; } return g; } /*创建无向图*/ struct graph creatgraph2() { int e,i,s,d; int a; struct graph g; struct arcnode *p,*q; printf("the number of vex(n) and arc(e):"); scanf("%d%d",&n,&e); g.vexnum=n; g.arcnum=e; for(i=0;i { printf("di %d vex's information:",i); scanf("%d",&a); g.vexpex[i].data=a; g.vexpex[i].firstarc=NULL; } for(i=0;i { printf("di %d arc's start,end:",i+1); scanf("%d%d",&s,&d); p=(struct arcnode *)malloc(sizeof(struct arcnode)); p->adjvex=d; p->info=g.vexpex[d].data; p->nextarc=g.vexpex[s].firstarc; g.vexpex[s].firstarc=p; q=(struct arcnode *)malloc(sizeof(struct arcnode)); q->adjvex=s; q->info=g.vexpex[s].data; q->nextarc=g.vexpex[d].firstarc; g.vexpex[d].firstarc=q; } return g; } /*显示图*/ void displaygraph(struct graph g,int n) { int i; struct arcnode *p; printf("diaplay the graph;\n"); for(i=0;i { printf(" [%d,%d]->",i,g.vexpex[i].data); p=g.vexpex[i].firstarc; while(p!=NULL) { printf("(%d,%d)->",p->adjvex,p->info); p=p->nextarc; } printf("^\n"); } } /*连通图广度优先遍历*/ void BFSsearch(struct graph g,int v) { int i; struct arcnode *p; Q=initqueue(); printf("%5d",g.vexpex[v].data); enqueue(Q,v); visit[v]=TURE; while(!emptyqueue(Q)) { i=dequeue(Q); p=g.vexpex[i].firstarc; while(p!=NULL) { enqueue(Q,p->adjvex); if(visit[p->adjvex]==FALSE) { printf("%5d",p->info); visit[p->adjvex]=TURE; } p=p->nextarc; } } } /*非连通图广度优先遍历*/ void BFS(struct graph g) { int i; printf("BFS result:\n"); for(i=0;i visit[i]=FALSE; for(i=0;i if(visit[i]==FALSE) BFSsearch(g,i); printf("\n\n"); } /*连通图深度优先遍历*/ void DFSsearch(struct graph g,int v) { struct arcnode *p; printf("%5d",g.vexpex[v].data); visit[v]=TURE; p=g.vexpex[v].firstarc; while(p!=NULL) { if(!visit[p->adjvex]) DFSsearch(g,p->adjvex); p=p->nextarc; } } void DFS(struct graph g) /*非连通图深度优先遍历*/ { int i; printf("DFS result:\n"); for(i=0;i visit[i]=FALSE; for(i=0;i if(visit[i]==FALSE) DFSsearch(g,i); printf("\n\n"); } int menu_select() /*主菜单定义*/ { char s[80]; int c; gotoxy(1,25); /*将光标定在第25行第1列*/ printf("press any key enter menu ......\n"); /*提示按任意键继续*/ getch(); /*读入任意字符*/ clrscr(); /*清屏*/ gotoxy(1,1); printf("***************MENU***************\n\n"); printf(" 1. Make a digraph by youself!\n"); printf(" 2. Make a undigraph by youself!\n"); printf(" 3. Ontput your graph!\n"); printf(" 4. Depth_first search your graph!\n"); printf(" 5. Bredth_first search your graph!\n"); printf(" 6. Quit!\n"); printf("**********************************\n"); do{ printf("\n Enter you choice (1~6):\n"); /*提示输入选项*/ scanf("%s",s); /*输入选择项*/ c=atoi(s); /*将输入的字符串转化为整型*/ }while(c<1||c>6); return c; } /*主函数*/ void main() { struct graph g; int i; clrscr(); /*清屏*/ for(;;) { switch(menu_select()) { case 1: { clrscr(); g=creatgraph1(); break; } case 2: { clrscr(); g=creatgraph2(); break; } case 3: { clrscr(); printf("diaplay the graph;\n"); displaygraph(g,n); break; } case 4: { clrscr(); printf("DFS result:\n"); DFS(g); break; } case 5: { clrscr(); printf("BFS result:\n"); BFS(g); break; } case 6: exit(0); } } } . .. . .. .. 实验三、图的遍历操作 一、目的 掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。 二、要求 采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS 和BFS操作。 三、DFS和BFS 的基本思想 深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。 广度优先算法BFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，……，Vt；再依次访问与V1，V2，……，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。 四、示例程序 1．邻接矩阵作为存储结构的程序示例 #include"stdio.h" #include"stdlib.h" #define MaxVertexNum 100 //定义最大顶点数 typedef struct{ char vexs[MaxVertexNum]; //顶点表 int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表int n,e; //图中的顶点数n和边数e }MGraph; //用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G) { int i,j,k; char a; printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数 scanf("%c",&a); printf("Input Vertex string:"); for(i=0;i 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 南昌航空大学 数学与信息科学学院 实验报告 课程名称：数学实验 实验名称： MATLAB基本操作 实验类型：验证性■综合性□ 设计性□ 实验室名称：数学实验室 班级学号： 10 学生姓名：钟 X 任课教师（教师签名）： 成绩： 实验日期： 2011-１０- 1０ 一、实验目的 1、熟悉MATLAB基本命令与操作 2、熟悉MATLAB作图的基本原理与步骤 3、学会用matlab软件做图 二、实验用仪器设备、器材或软件环境 计算机MATLAB软件 三、实验原理、方案设计、程序框图、预编程序等 问题1：在区间【0,2π】画sinx 实验程序: >> x=linspace(0,2*pi,30); >> y=sin(x); >> plot(x,y) 问题2：在【0,2π】用红线画sinx,用绿圈画cosx,实验程序: >> x=linspace(0,2*pi,30); >> y=sin(x); >> z=cos(x); >> plot(x,y,'r',x,z,'co') >> 问题3：在【0，π】上画y=sinx的图形。 实验程序: >> ezplot('sin(x)',[0,pi]) >> 问题4：在【0，π】上画x=cos3t,y=sin3t星形图形。 实验程序: >> ezplot('cos(t).^3','sin(t).^3',[0,pi]) >> 问题5：[-2,0.5]，[0,2]上画隐函数 实验程序: >> ezplot('exp(x)+sin(x*y)',[-2,0.5,0,2]) >> 问题6：在[－２，２]范围内绘制tanh的图形。实验程序: >> fplot('tanh',[-2,2]) 数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"< 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 实验四：图的遍历 题目：图及其应用——图的遍历 班级：姓名：学号：完成日期： 一.需求分析 1.问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。 2.基本要求：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 3.测试数据：教科书图7.33。暂时忽略里程，起点为北京。 4.实现提示：设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,…,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制，注意，生成树的边是有向边，端点顺序不能颠倒。 5.选作内容： （1）.借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。 （2）.以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。 二.概要设计 1.为实现上述功能，需要有一个图的抽象数据类型。该抽象数据类型的定义为： ADT Graph { 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R={VR} VR={ 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 实验名称：Windows的基本操作 一、实验目的 1.掌握桌面主题的设置。 2.掌握快捷方式的创建。 3.掌握开始菜单的组织。 4.掌握多任务间的数据传递——剪贴板的使用。 5.掌握文件夹和文件的创建、属性查看和设置。 6.掌握文件夹和文件的复制、移动和删除与恢复。 7.熟悉文件和文件夹的搜索。 8.熟悉文件和文件夹的压缩存储和解压缩。 二、实验环境 1.中文Windows 7操作系统。 三、实验内容及步骤 通过上机完成实验4、实验5所有内容后完成该实验报告 1.按“实验4--范例内容(1)”的要求设置桌面，将修改后的界面复制过来。 注：没有桌面背景图“Autumn”的，可选择其它背景图。 步骤：在桌面空白区域右击，选择菜单中的“个性化”，在弹出的窗口中点击“桌面背景”，在背景栏内选中“某一张图片”，单击“确定”。 修改后的界面如下图所示： 2.将画图程序添加到“开始”菜单的“固定项目列表”上。 步骤：右击“开始/所有程序/附件”菜单中的画图程序项，在弹出的快捷菜单中选“附到「开始」菜单”命令。 3.在D盘上建立以“自己的学号+姓名”为名的文件夹（如01108101刘琳）和其子文件 夹sub1，然后： 步骤：选定D:\为当前文件夹，选择“文件/新建/文件夹”命令，并将名字改为“学号+姓名”；选定“ D:\学号+姓名”为当前文件夹，选择“文件/新建/文件夹”命令，并将名字改为“sub1” ①在C:\WINDOWS中任选2个TXT文本文件，将它们复制到“学号+姓名”文件夹中；步骤：选定“C:\WINDOWS”为当前文件夹，随机选取2个文件, CTRL+C复制，返回“D:\学号+姓名”的文件夹，CTRL+V粘贴 ②将“学号+姓名”文件夹中的一个文件移到其子文件夹sub1中； 步骤：选定“ D:\学号+姓名”为当前文件夹，选中其中任意一个文件将其拖拽文件到subl ③在sub1文件夹中建立名为“”的空文本文档； 步骤：选定“ D:\学号+姓名\ sub1”为当前文件夹，在空白处单击右键，选择“新建\文本文档”，把名字改为test，回车完成。 ④删除文件夹sub1，然后再将其恢复。 步骤：选定“ D:\学号+姓名”为当前文件夹，右键单击“sub1”文件夹，选择“删除”，然后打开回收站，右键单击“sub1”文件夹，在弹出的快捷菜单中选择“还原”。 4.搜索C:\WINDOWS\system文件夹及其子文件夹下所有文件名第一个字母为s、文件长 度小于10KB且扩展名为exe的文件，并将它们复制到sub1文件夹中。 步骤：选定“ C:\WINDOWS\system”为当前文件夹，单击“搜索”按钮，在左侧窗格选择“所有文件和文件夹”，在“全部或部分文件名”中输入“s*.exe”，在“大小”中，选择“0~10KB”。 5.用不同的方法，在桌面上创建名为“计算器”、“画图”和“剪贴板”的三个快捷方式， 它们应用程序分别为：、和。并将三个快捷方式复制到sub1文件夹中。 步骤：①在"开始"菜单的"所有程序"子菜单中找到"计算器"，单击右键，在弹出的快捷菜单中选择“发送到\桌面快捷方式”。 ②在"开始"菜单的"所有程序"子菜单中找到"画图"，将其拖至桌面空白处。 ③在桌面上单击右键，在弹出的快捷菜单中选择“新建\快捷方式”，在“创建快捷方式” 实验项目名称：图的遍历 一、实验目的 应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。 二、实验容 问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机，Code::Blocks。 四、实验原理 用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;i 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 浙江大学城市学院实验报告 课程名称数据结构 实验项目名称实验十三/十四图的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期2014/06/09 一.实验目的和要求 1、掌握图的主要存储结构。 2、学会对几种常见的图的存储结构进行基本操作。 二.实验内容 1、图的邻接矩阵定义及实现： 建立头文件test13_AdjM.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test13.cpp（以下图为例），编译并调试程序，直到正确运行。 2、图的邻接表的定义及实现： 建立头文件test13_AdjL.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数文件test13.cpp中调用这些函数进行验证（以下图为例）。 3、填写实验报告，实验报告文件取名为report13.doc。 4、上传实验报告文件report13.doc到BB。 注: 下载p256_GraphMatrix.cpp(邻接矩阵)和 p258_GraphAdjoin.cpp(邻接表)源程序，读懂程序完成空缺部分代码。 三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路） 四. 实验结果与分析 （包括运行结果截图、结果分析等） 五.心得体会 程序比较难写，但是可以通过之前的一些程序来找到一些规律 （记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。） 【附录----源程序】 256: //p-255 图的存储结构以数组邻接矩阵表示, 构造图的算法。 #include 目录 实验一：数字图像的基本处理操作 (4) ：实验目的 (4) ：实验任务和要求 (4) ：实验步骤和结果 (5) ：结果分析 (8) 实验二：图像的灰度变换和直方图变换 (9) ：实验目的 (9) ：实验任务和要求 (9) ：实验步骤和结果 (9) ：结果分析 (13) 实验三：图像的平滑处理 (14) ：实验目的 (14) ：实验任务和要求 (14) ：实验步骤和结果 (14) ：结果分析 (18) 实验四：图像的锐化处理 (19) ：实验目的 (19) ：实验任务和要求 (19) ：实验步骤和结果 (19) ：结果分析 (21) 实验一：数字图像的基本处理操作 ：实验目的 1、熟悉并掌握MATLAB、PHOTOSHOP等工具的使用； 2、实现图像的读取、显示、代数运算和简单变换。 3、熟悉及掌握图像的傅里叶变换原理及性质，实现图像的傅里叶变换。：实验任务和要求 1.读入一幅RGB图像，变换为灰度图像和二值图像，并在同一个窗口内分 成三个子窗口来分别显示RGB图像和灰度图像，注上文字标题。 2.对两幅不同图像执行加、减、乘、除操作，在同一个窗口内分成五个子窗口来分 别显示，注上文字标题。 3.对一幅图像进行平移，显示原始图像与处理后图像，分别对其进行傅里叶变换， 显示变换后结果，分析原图的傅里叶谱与平移后傅里叶频谱的对应关系。 4.对一幅图像进行旋转，显示原始图像与处理后图像，分别对其进行傅里 叶变换，显示变换后结果，分析原图的傅里叶谱与旋转后傅里叶频谱的 对应关系。 ：实验步骤和结果 1.对实验任务1的实现代码如下： a=imread('d:\'); i=rgb2gray(a); I=im2bw(a,; subplot(1,3,1);imshow(a);title('原图像'); subplot(1,3,2);imshow(i);title('灰度图像'); subplot(1,3,3);imshow(I);title('二值图像'); subplot(1,3,1);imshow(a);title('原图像'); 结果如图所示： 附录A 实验报告 课程：数据结构（c语言）实验名称：图的建立、基本操作以及遍历系别：数字媒体技术实验日期： 12月13号 12月20号 专业班级：媒体161 组别：无 姓名：学号： 实验报告内容 验证性实验 一、预习准备： 实验目的： 1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围； 2、熟练掌握几种常见图的遍历方法及遍历算法； 实验环境：Widows操作系统、VC6.0 实验原理： 1.定义： 基本定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(V ertex)的非空有限集E(G)是边(Edge)的有限集合，边是顶点的无序对(即：无方向的，（v0,v2）)或有序对（即：有方向的, 无向图中顶点V i的度TD(V i)是邻接矩阵A中第i行元素之和有向图中， 顶点V i的出度是A中第i行元素之和 顶点V i的入度是A中第i列元素之和 邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧） 特点: 无向图中顶点Vi的度为第i个单链表中的结点数有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。 图的遍历 从图中某个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次过程.。遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。图的遍历有两条路径：深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需要时间为O（n2），n为图中顶点数；而当以邻接表作图的存储结构时，找邻接点所需时间为O（e），e 为无向图中边的数或有向图中弧的数。 实验内容和要求： 选用任一种图的存储结构，建立如下图所示的带权有向图： 要求：1、建立边的条数为零的图； 目录 实验一：数字图像的基本处理操作....................................................................... 错误!未定义书签。：实验目的 .............................................................................................................. 错误!未定义书签。：实验任务和要求..................................................................................................... 错误!未定义书签。：实验步骤和结果..................................................................................................... 错误!未定义书签。：结果分析................................................................................................................. 错误!未定义书签。实验二：图像的灰度变换和直方图变换............................................................... 错误!未定义书签。：实验目的 .............................................................................................................. 错误!未定义书签。：实验任务和要求..................................................................................................... 错误!未定义书签。：实验步骤和结果..................................................................................................... 错误!未定义书签。：结果分析................................................................................................................. 错误!未定义书签。实验三：图像的平滑处理....................................................................................... 错误!未定义书签。：实验目的 .............................................................................................................. 错误!未定义书签。：实验任务和要求..................................................................................................... 错误!未定义书签。：实验步骤和结果..................................................................................................... 错误!未定义书签。：结果分析................................................................................................................. 错误!未定义书签。实验四：图像的锐化处理......................................................................................... 错误!未定义书签。：实验目的 .............................................................................................................. 错误!未定义书签。：实验任务和要求..................................................................................................... 错误!未定义书签。：实验步骤和结果..................................................................................................... 错误!未定义书签。：结果分析................................................................................................................. 错误!未定义书签。 《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。 ◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。 一、需求分析 1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。 3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出（3）以广度优先遍历输出（4）结束 5.测试数据： 顶点数和边数：6,5 顶点信息：a b c d e f 边的顶点对应序号： 0,1 0,2 0,3 2,4 3,4 深度优先遍历输出： a d e c b f 广度优先遍历输出： a d c b e f 二概要设计 为了实现上述操作，应以邻接链表为存储结构。 1.基本操作： void createalgraph(algraph &g) 创建无向图的邻接链表存储 void dfstraverseal(algraph &g,int v) 以深度优先遍历输出 void bfstraverseal(algraph &g,int v) 以广度优先遍历输出 2.本程序包含四个模块： （1）主程序模块 （2）无向图的邻接链表存储模块 （3）深度优先遍历输出模块 （4）广度优先遍历输出模块 3.模块调用图： 三详细设计 1.元素类型，结点类型和指针类型：typedef struct node { int adjvex; struct node *next; }edgenode; typedef struct vnode { char vertex; edgenode *firstedge; }vertxnode; typedef vertxnode Adjlist[maxvernum]; typedef struct { Adjlist adjlist; int n,e; }algraph; edgenode *s; edgenode *stack[maxvernum],*p; 2.每个模块的分析： （1）主程序模块 int main() 实验五图的基本操作 一、实验目的 1、使学生可以巩固所学的有关图的基本知识。 2、熟练掌握图的存储结构。 3、熟练掌握图的两种遍历算法。 二、实验内容 [问题描述] 对给定图，实现图的深度优先遍历和广度优先遍历。 [基本要求] 以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。 【测试数据】 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握图的相关概念。 2、掌握图的逻辑结构和存储结构。 3、掌握图的两种遍历算法的实现。 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果，对程序进行分析。 五、算法设计 1、程序所需头文件已经预处理宏定义和结构体定义如下 #include 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方法及其基本思想。 二、实验内容： 1.建立无向图的邻接矩阵 2.图的xx优先搜索 3.图的xx优先搜索 三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "stdio.h" #include "stdlib.h" #define MAXSIZE 30 typedefstruct{charvertex[MAXSIZE];//顶点为字符型且顶点表的长度小于MAXSIZE intedges[MAXSIZE][MAXSIZE];//边为整形且edges为邻近矩阵 }MGraph;//MGraph为采用邻近矩阵存储的图类型 voidCreatMGraph(MGraph *g,inte,int n) {//建立无向图的邻近矩阵g->egdes，n为顶点个数，e为边数inti,j,k; printf("Input data of vertexs(0~n-1): \n"); for(i=0;i图的遍历操作实验报告
数据结构实验十一：图实验
MATLAB基本操作实验报告
(完整版)数据结构实验报告全集
数据结构实验报告图实验
图的遍历实验报告
数据结构实验报告图实验
实验报告1windows的基本操作范例
数据结构图的遍历实验报告
数据结构实验
数据结构实验图的基本操作
数字图像处理实验报告
数据结构实验报告(图)
数字图像处理实验报告
数据结构实验报告无向图
图的基本操作 实验报告
数据结构图实验报告