数据结构实验-图的基本操作
浙江大学城市学院实验报告
课程名称数据结构
实验项目名称实验十三/十四图的基本操作
学生姓名专业班级学号
实验成绩指导老师（签名）日期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
#include
#include
#include
typedef char VertexType; //顶点的名称为字符
const int MaxVertexNum=10; //图的最大顶点数
const int MaxEdgeNum=100; //边数的最大值
typedef int WeightType; //权值的类型
const WeightType MaxValue=32767; //权值的无穷大表示
typedef VertexType Vexlist[MaxVertexNum]; //顶点信息，定点名称
typedef WeightType AdjMatrix[MaxVertexNum][MaxVertexNum]; //邻接矩阵typedef enum{DG,DN,AG,AN} GraphKind; //有向图,有向网,无向图,无向网typedef struct{
Vexlist vexs; // 顶点数据元素
AdjMatrix arcs; // 二维数组作邻接矩阵
int vexnum, arcnum; // 图的当前顶点数和弧数
GraphKind kind; // 图的种类标志
} MGraph;
void CreateGraph(MGraph &G, GraphKind kd)// 采用数组邻接矩阵表示法，构造图G
{//构造有向网G
int i,j,k,q;
char v, w;
G.kind=kd; //图的种类
printf("输入要构造的图的顶点数和弧数：\n");
scanf("%d,%d",&G.vexnum,&G.arcnum);
getchar();//过滤回车
printf("依次输入图的顶点名称ABCD...等等：\n");
for (i=0; i getchar();//过滤回车 for (i=0; i for (j=0; j if(kd==DN||kd==AN) G.arcs[i][j]=MaxValue; //网，初始值为无穷大 else G.arcs[i][j]=0; //图，初始为0 if(kd==DN||kd==AN) printf("按照：尾顶点名->头顶点名，权值输入数据:如A->B,23 \n"); else printf("按照：尾顶点名->头顶点名输入数据:A->B\n"); for (k=0; k if(kd==DN||kd==AN) scanf("%c->%c,%d",&v,&w,&q); //输入弧的两个定点及该弧的权重else scanf("%c->%c",&v,&w); getchar(); for(i=0;i if(G.vexs[i]==v) break;//查找出v在vexs[]中的位置i if(i==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} for(j=0;j if(G.vexs[j]==w) break;//查找出v在vexs[]中的位置j if(j==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} if(kd==AN)//无向网 { G.arcs[i][j]=q; //邻接矩阵对应位置置权值 G.arcs[j][i]=q; //无向图为对称矩阵 } else if(kd==DN)//有向网 G.arcs[i][j]=q; else if(kd==AG)//无向图 { G.arcs[i][j]=1; //对称矩阵 G.arcs[j][i]=1; } else //有向图 G.arcs[i][j]=1; // getchar(); } }//CreateGraph /* 注意输入格式,按以下方式输入 构造有向网 输入要构造的网的顶点数和弧数： 4,5 依次输入网的顶点名称ABCD...等等： abcd 按照：尾顶点名->头顶点名，权值输入数据:如A->B,23 a->b,5 a->c,8 c->b,7 a->d,4 d->c,3 输出邻接矩阵 ∞| 5 | 8 | 4 | ∞| ∞| ∞| ∞| ∞| 7 | ∞| ∞| ∞| ∞| 3 | ∞| Press any key to continue */ void PrintMGraph(MGraph &G) { int i,j; switch(G.kind) { case DG: for (i=0; i { for (j=0; j printf(" %2.d | ",G.arcs[i][j]); printf("\n"); } break; case DN: for (i=0; i { for (j=0; j if(G.arcs[i][j]!=MaxValue) printf(" %2.d | ",G.arcs[i][j]); else printf(" ∞| "); } printf("\n"); } break; case AG: for (i=0; i { for (j=0; j printf(" %2.d | ",G.arcs[i][j]); } printf("\n"); } break; case AN: //********完成构造无向网**************** /* 请模仿编写无向网*/ for (i=0; i { for (j=0; j if(G.arcs[i][j]!=MaxValue) printf(" %2.d | ",G.arcs[i][j]); else printf(" ∞| "); } printf("\n"); } break; } } //*****************完成函数********************************** void countdig(MGraph G) //请完成计算图的入度或初度 { if(G.kind==DG||G.kind==DN) { //计算有向图或网的各个顶点的入度与出度 int outD,inD; int i,j; for(i=0;i outD=inD=0; for(j=0;j if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MaxValue) outD++; } for(j=0;j if(G.arcs[j][i]!=0&&G.arcs[j][i]!=MaxValue) inD++; } printf("%c：出度是%d,入度是%d\n",G.vexs[i],outD,inD); } } else { // 计算无向图或网的度 int i,j; int Du; for(i=0;i Du=0; for(j=0;j if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MaxValue) Du++; } printf("%c的度是%d\n",G.vexs,Du); } } } //************参照p265设计深度有限搜索*********** void DFSMatrix(MGraph G,int i,int n,bool*visited) { cout< visited[i]=true; for(int j=0;j if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MaxValue&& !visited[j]) DFSMatrix(G,j,n,visited); } //************参照p268设计广度有限搜索*********** void BFSMatrix(MGraph G,int i, int n , bool*visited) { const int MaxSize=30; int q[MaxSize]={0}; int front=0,rear=0; cout< visited[i]=true; q[++rear]=i; while(front!=rear){ front=(front+1)%MaxSize; int k=q[front]; for(int j=0;j if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MaxValue&& !visited[j]){ cout< visited[j]=true; rear=(rear+1)%MaxSize; q[rear=j]; } } } } void main() { MGraph G; int k; printf("请选择图的种类：0:有向图,1:有向网,2:无向图,3:无向网. 请选择："); scanf("%d",&k); switch(k) { //DG,DN,AG,AN case 0: printf("构造有向图\n"); CreateGraph(G,DG); // 采用数组邻接矩阵表示法，构造有向图 break; case 1: printf("构造有向网\n"); CreateGraph(G,DN); // 采用数组邻接矩阵表示法，构造有向网AGG break; case 2: printf("构造无向图\n"); CreateGraph(G,AG); // 采用数组邻接矩阵表示法，构造无向图AGG break; case 3: printf("构造无向网\n"); CreateGraph(G,AN); // 采用数组邻接矩阵表示法，构造无向网AGG break; } PrintMGraph(G); //打印图的邻接矩阵 bool*visited=new bool[G.vexnum]; int i; cout<<"按图的邻接矩阵得到的深度优先遍历序列"< for(i=0;i DFSMatrix(G,0,G.vexnum,visited); cout<<"按图的邻接矩阵得到的广度优先遍历序列"< for(i=0;i BFSMatrix(G,0,G.vexnum,visited); cout<<"度："< countdig(G); } 258: //p-258 图的存储结构以邻接表表示, 构造图的算法。 //已完成若干函数，对尚未完成的请补全 //请注意输入格式，按以下方式构建一个图 /* 请选择图的种类：0:有向图,1:有向网,2:无向图,3:无向网. 请选择：0 构造有向图 输入要构造的有向图的顶点数和弧数： 4,5 依次输入图的顶点名称ABCD...等等： abcd 按照：尾顶点名->头顶点名输入数据:如A->B a->b a->c a->d c->b d->c */ #include #include #include #include typedef char VertexType; //顶点的名称为字符 const int MaxVertexNum =10; //图的最大顶点数 const int MaxEdgeNum =100; //边数的最大值 typedef int WeightType; //权值的类型 const WeightType MaxValue =32767; //权值的无穷大表示 typedef VertexType Vexlist [MaxVertexNum]; //顶点信息，定点名称 //邻接矩阵 typedef enum {DG,DN,AG,AN} GraphKind; //有向图,有向网,无向图,无向网struct EdgeNode{ //链表边结点，表示弧 int adjvex; //存放与头结点顶点有关的另一个顶点在邻接表(数组)中的下标。 EdgeNode *next; //指向链表下一个结点 WeightType info; // 权重值，或为该弧相关信息 }; typedef struct VNode{ //邻接表，表示顶点 VertexType data; // 顶点数据，顶点名称 EdgeNode *firstarc; // 指向边结点链表第一个结点 } VNode, AdjList[MaxVertexNum]; typedef struct{ AdjList vertices; int vexnum, arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 } ALGraph; void CreateGraph_DG(ALGraph &G){//构造有向图G EdgeNode *p; int i,j,k; char v,w; G.kind=DG; //图的种类 printf("输入要构造的有向图的顶点数和弧数：\n"); scanf("%d,%d",&G.vexnum,&G.arcnum); getchar();//过滤回车 printf("依次输入图的顶点名称ABCD...等等：\n"); for (i=0; i scanf("%c",&G.vertices[i].data);//构造顶点数据 G.vertices[i].firstarc=NULL; //初始化指向链表指针 } getchar();//过滤回车 printf("按照：尾顶点名->头顶点名输入数据:如A->B \n"); for (k=0; k scanf("%c->%c",&v,&w); getchar(); for(i=0;i if(G.vertices[i].data==v) break;//查找出v在vertices[]中的位置i if(i==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} for(j=0;j if(G.vertices[j].data==w) break;//查找出w在vertices[]中的位置i if(j==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} p=(EdgeNode *)malloc(sizeof(EdgeNode));//申请弧结点 p->adjvex=j; //置入弧尾顶点号 p->info =MaxValue; //图的权值默认为无穷大 p->next=G.vertices[i].firstarc; //插入链表 G.vertices[i].firstarc=p; } } //////////////////////////////////////////////////////////////////////////////////////////////// void CreateGraph_DN(ALGraph &G)//构造有向网G { EdgeNode *p; int i,j,k; char v,w; WeightType q; G.kind=DN; //图的种类 printf("输入要构造的有向网的顶点数和弧数：\n"); scanf("%d,%d",&G.vexnum,&G.arcnum); getchar();//过滤回车 printf("依次输入图的顶点名称ABCD...等等：\n"); for (i=0; i scanf("%c",&G.vertices[i].data);//构造顶点数据 G.vertices[i].firstarc=NULL; //初始化指向链表指针 } getchar();//过滤回车 printf("按照：尾顶点名->头顶点名,权值输入数据:如A->B,8 \n"); for (k=0; k scanf("%c->%c,%d",&v,&w,&q); getchar(); for(i=0;i if(G.vertices[i].data==v) break;//查找出v在vertices[]中的位置i if(i==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} for(j=0;j if(G.vertices[j].data==w) break;//查找出w在vertices[]中的位置i if(j==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} p=(EdgeNode *)malloc(sizeof(EdgeNode));//申请弧结点 p->adjvex=j; //置入弧尾顶点号 p->info =q; //图的权值默认为无穷大 p->next=G.vertices[i].firstarc; //插入链表 G.vertices[i].firstarc=p; } } void CreateGraph_AG(ALGraph &G)//构造无向图G { EdgeNode *p; int i,j,k; char v,w; G.kind=AG; //图的种类 printf("输入要构造的有向图的顶点数和弧数：\n"); scanf("%d,%d",&G.vexnum,&G.arcnum); getchar();//过滤回车 printf("依次输入图的顶点名称ABCD...等等：\n"); for (i=0; i scanf("%c",&G.vertices[i].data);//构造顶点数据 G.vertices[i].firstarc=NULL; //初始化指向链表指针 } getchar();//过滤回车 printf("按照：尾顶点名->头顶点名输入数据:如A->B \n"); for (k=0; k scanf("%c->%c",&v,&w); getchar(); for(i=0;i if(G.vertices[i].data==v) break;//查找出v在vertices[]中的位置i if(i==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} for(j=0;j if(G.vertices[j].data==w) break;//查找出w在vertices[]中的位置i if(j==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} p=(EdgeNode *)malloc(sizeof(EdgeNode));//申请弧结点 p->adjvex=j; //置入弧尾顶点号 p->info =MaxValue; //图的权值默认为无穷大 p->next=G.vertices[i].firstarc; //插入链表 G.vertices[i].firstarc=p; //无向图和网的边结点依附于i,j两个顶点,两方均应添加边 p=(EdgeNode *)malloc(sizeof(EdgeNode));//申请弧结点 p->adjvex=i; //置入弧尾顶点号 p->info =MaxValue; //图的权值默认为无穷大 p->next=G.vertices[j].firstarc; //插入链表 G.vertices[j].firstarc=p; } } /////////////////////////////////////////////////////////////////////////////////////////// void CreateGraph_AN(ALGraph &G)//构造无向网G { EdgeNode *p; int i,j,k; char v,w; WeightType q; G.kind=AN; //图的种类 printf("输入要构造的无向网的顶点数和弧数：\n"); scanf("%d,%d",&G.vexnum,&G.arcnum); getchar();//过滤回车 printf("依次输入图的顶点名称ABCD...等等：\n"); for (i=0; i scanf("%c",&G.vertices[i].data);//构造顶点数据 G.vertices[i].firstarc=NULL; //初始化指向链表指针 } getchar();//过滤回车 printf("按照：尾顶点名--头顶点名,权值输入数据:如A--B,8 \n"); for (k=0; k scanf("%c--%c,%d",&v,&w,&q); getchar(); for(i=0;i if(G.vertices[i].data==v) break;//查找出v在vertices[]中的位置i if(i==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} for(j=0;j if(G.vertices[j].data==w) break;//查找出w在vertices[]中的位置i if(j==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} p=(EdgeNode *)malloc(sizeof(EdgeNode));//申请弧结点 p->adjvex=j; //置入弧尾顶点号 p->info =q; //图的权值默认为无穷大 p->next=G.vertices[i].firstarc; //插入链表 G.vertices[i].firstarc=p; //无向图和网的边结点依附于i,j两个顶点,两方均应添加边 p=(EdgeNode *)malloc(sizeof(EdgeNode));//申请弧结点 p->adjvex=i; //置入弧尾顶点号 p->info =q; //图的权值默认为无穷大 p->next=G.vertices[j].firstarc; //插入链表 G.vertices[j].firstarc=p; } } void dfsAdjoin(ALGraph G,int i,bool *visited) //深度优先搜索p266 { cout< visited[i]=true; EdgeNode *p=G.vertices[i].firstarc ; while(p!=NULL) { int j=p->adjvex; if(visited[j]==false) dfsAdjoin(G,j,visited); p=p->next ; } } void bfsAdjoin(ALGraph G,int i,bool *visited) //广度优先搜索p268 { const int MSize=30; int q[MSize]={0}; int front=0,rear=0; cout< visited[i]=true; q[++rear]=i; while(front!=rear){ front=(front+1)%MSize; int k=q[front]; EdgeNode *p=G.vertices[k].firstarc; while(p!=NULL){ int j=p->adjvex; if(!visited[j]){ cout< visited[j]=true; rear=(rear+1)%MSize; q[rear]=j; } p=p->next; } } } //*****************完成函数********************************** void countdig(ALGraph G) //请完成计算图的入度或初度 { if(G.kind==DG||G.kind==DN) { //计算有向图或网的个顶点的入度与初度 int outD,inD; EdgeNode *p,*k; int i,j; for(i=0;i outD=0; inD=0; p=G.vertices[i].firstarc; for(;p!=NULL;p=p->next){ outD++; } for(j=0;j k=G.vertices[j].firstarc; for(;k!=NULL;k=k->next){ if(G.vertices[k->adjvex].data==G.vertices[i].data) inD++; } } printf("%c：出度是%d,入度是%d\n",G.vertices[i].data,outD,inD); } } else { // 计算无向图或网的度 int Du; EdgeNode *p,*k; int i,j; for(i=0;i Du=0; p=G.vertices[i].firstarc; for(;p!=NULL;p=p->next){ Du++; } printf("%c：度是%d\n",G.vertices[i].data,Du); } } } void PrintALGraph(ALGraph &G){//打印邻接表 EdgeNode *p; int i; for (i=0; i { if(G.vertices[i].firstarc!=NULL) //输出顶点名称 printf("%d | %c =>",i,G.vertices[i].data); else printf("%d | %c ^",i,G.vertices[i].data); p=G.vertices[i].firstarc; //输出依附上面顶点的各条边 while(p) { printf(" %d ",p->adjvex); //另一顶点序号 if(p->info!=MaxValue) //若有权重输出，网 printf("| %d",p->info ); if(p->next!=NULL) //输出指针 printf(" ->"); else printf(" ^"); p=p->next; //下一条边 } printf("\n"); } } void main() { ALGraph G; int k; printf("请选择图的种类：0:有向图,1:有向网,2:无向图,3:无向网. 请选择："); scanf("%d",&k); switch(k) { //DG,DN,AG,AN case 0: printf("构造有向图\n"); CreateGraph_DG(G); // 采用邻接表，构造有向图 break; case 1: printf("构造有向网\n"); CreateGraph_DN(G); // 采用邻接表，构造有向网 break; case 2: printf("构造无向图\n"); CreateGraph_AG(G); // 采用邻接表，构造无向图 break; case 3: printf("构造无向网\n"); CreateGraph_AN(G); // 采用邻接表，构造无向网 break; } PrintALGraph(G); //打印图的邻接表 //下面完成图的邻接表结构的深度优先和广度优先搜索 bool visited[MaxVertexNum]; int i; cout<<"邻接表存储的图G，深度优先搜索序列："; for(i=0;i visited[i]=false; //初始化visited数组 for(i=0;i if(visited[i]==false) dfsAdjoin(G,i,visited); //深度优先搜索 cout< cout<<"邻接表存储的图G，广度优先搜索序列："; for(i=0;i visited[i]=false; //初始化visited数组 for(i=0;i if(visited[i]==false) bfsAdjoin(G,i,visited); //广度优先搜索 cout< cout<<"度"< countdig(G); } . .. . .. .. 实验三、图的遍历操作 一、目的 掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握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. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现； 2. 掌握稀疏矩阵的加法、转置、乘法等基本运算； 3. 加深对线性表的顺序存储和链式结构的理解。 第一节知识准备 矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。 一、特殊矩阵的压缩存储 1. 对称矩阵和上、下三角阵 若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。 问题已经转化为：已知二维矩阵A[i，j]，如图5-1， 我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。 任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里： k=i(i+1)/2+j (i≥j) 图5-1 下三角矩阵 a00 a10 a11 a20 … an-1,0 … an-1,n-1 k= 0 1 2 3 …n(n- 1)/2 …n(n+1)/2-1 图5-2下三角矩阵的压缩存储 反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。这里，i=d-1，（d是使sum= > k的最小整数），j= 。 2. 三对角矩阵 在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。 图5-3 三对角矩阵A 与下三角矩阵的存储一样，我们也可以用一个一维数组ma[0..3n-2]来存放三对角矩阵A，其对应关系见图5-4。 a00 a01 a10 a11 a12 … an-1,n-2 an-1,n-1 k= 0 1 2 3 4 … 3n-3 3n-2 图5-4下三角矩阵的压缩存储 A中的一对下标(i,j)与ma中的下标k之间有如下的关系： 公式中采用了C语言的符号，int()表示取整，‘%’表示求余。 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 数据结构实验五图子系统 实验五 实验题目:图子系统 指导老师:王春红 专业班级:计算机科学与技术系1105班姓名:李慧2011100521杜丽20111005122 白莹2011100523王媛2011100529 2013年 5月23日 实验类型综合实验室_软件实验室一__ 一、实验题目 1 图子系统 二、实验目的和要求 ,(掌握图的存储思想及其存储实现 ,(掌握图的深度、广度优先遍历算法思想及其程序实现 ,(掌握图的常见应用算法的思想及其程序实现。三、实验内容 实验内容二:所有顶点对的最短路径 1(设置4个村庄之间的交通，村庄之间的距离用各边上的权值来表示。现在要求从这4个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。 2(设计分析 用有向加权图表示的交通图中，有向边 实验四：图的遍历 题目：图及其应用——图的遍历 班级：姓名：学号：完成日期： 一.需求分析 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文件夹中。 步骤：①在"开始"菜单的"所有程序"子菜单中找到"计算器"，单击右键，在弹出的快捷菜单中选择“发送到\桌面快捷方式”。 ②在"开始"菜单的"所有程序"子菜单中找到"画图"，将其拖至桌面空白处。 ③在桌面上单击右键，在弹出的快捷菜单中选择“新建\快捷方式”，在“创建快捷方式” 实验报告五查找（学科：数据结构） 姓名单位班级学号实验日期成绩评定教师签名批改日期 实验名称：实验五查找 5.1 折半查找 【问题描述】 某班学生成绩信息表中，每个学生的记录已按平均成绩由高到低排好序，后来发现某个学生的成绩没有登记到信息表中，使用折半查找法把该同学的记录插入到信息表中，使信息表中的记录仍按平均成绩有序。 【基本信息】 （1）建立现有学生信息表，平均成绩已有序。 （2）输入插入学生的记录信息。 （3）用折半查找找到插入位置，并插入记录。 【测试数据】 自行设计。 【实验提示】 （1）用结构数组存储成绩信息表。 （2）对记录中的平均成绩进行折半查找。 【实验报告内容】 设计程序代码如下: #include low=1; hight=n; strcpy(y,s[0].name ); x=s[0].avg ; while(low<=hight) { mid=(low+hight)/2; if(x>s[mid].avg ) hight=mid-1; else low=mid+1; } for(k=0;k 实验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 实验五 查找算法实现 1、实验目的 熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法，比较它们的平均查找长度。 2、问题描述 查找表是数据处理的重要操作，试建立有100个结点的二叉排序树进行查找，然后用原数据建立AVL树，并比较两者的平均查找长度。 3、基本要求 （1）以链表作为存储结构，实现二叉排序树的建立、查找和删除。 （2）根据给定的数据建立平衡二叉树。 4、测试数据 随即生成 5、源程序 #include<> #include<> #include<> #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)>(b)) typedef int Keytype; typedef struct { Keytype key; //关键字域 }ElemType; typedef struct BSTnode { ElemType data; int bf; struct BSTnode *lchild,*rchild; }BSTnode,*BSTree; void InitBSTree(BSTree &T) {T=NULL; } void R_Rotate(BSTree &p) {BSTnode *lc; lc=p->lchild; p->lchild=lc->rchild; lc->rchild=p; p=lc; } void L_Rotate(BSTree &p) {BSTnode *rc; rc=p->rchild; p->rchild=rc->lchild; 目录 实验一：数字图像的基本处理操作 (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、建立边的条数为零的图； 目录 实验一：数字图像的基本处理操作....................................................................... 错误!未定义书签。：实验目的 .............................................................................................................. 错误!未定义书签。：实验任务和要求..................................................................................................... 错误!未定义书签。：实验步骤和结果..................................................................................................... 错误!未定义书签。：结果分析................................................................................................................. 错误!未定义书签。实验二：图像的灰度变换和直方图变换............................................................... 错误!未定义书签。：实验目的 .............................................................................................................. 错误!未定义书签。：实验任务和要求..................................................................................................... 错误!未定义书签。：实验步骤和结果..................................................................................................... 错误!未定义书签。：结果分析................................................................................................................. 错误!未定义书签。实验三：图像的平滑处理....................................................................................... 错误!未定义书签。：实验目的 .............................................................................................................. 错误!未定义书签。：实验任务和要求..................................................................................................... 错误!未定义书签。：实验步骤和结果..................................................................................................... 错误!未定义书签。：结果分析................................................................................................................. 错误!未定义书签。实验四：图像的锐化处理......................................................................................... 错误!未定义书签。：实验目的 .............................................................................................................. 错误!未定义书签。：实验任务和要求..................................................................................................... 错误!未定义书签。：实验步骤和结果..................................................................................................... 错误!未定义书签。：结果分析................................................................................................................. 错误!未定义书签。 实验三的实验报告 学期： 2010 至_2011 第 2 学期 2011年 3月 27日课程名称: 数据结构专业:信息与计算科学 09 级5班实验编号： 03 实验项目：栈和队列实验指导教师 _冯山_姓名：朱群学号： 2009060548 实验成绩： 一实验目的： (1)熟练掌握栈和队列的抽象数据类型及其结构特点； (2)实现基本的栈和队列的基本操作算法程序。 二实验内容：(类C算法的程序实现，任选其一) (1) 设计与实现基本的堆栈和队列结构下的各种操作（如堆栈的PUSH、POP 等操作）(必做)； (2)以表达式计算为例，完成一个可以进行算术表达式计算功能的算法设计 与实现（选做）； (3)以迷宫问题为例，以堆栈结构完成迷宫问题的求解算法和程序（选做）。三实验准备： 1) 计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分 析与代码设计与分析准备。 四实验步骤： 1.录入程序代码并进行调试和算法分析； 2.编写实验报告。 五实验过程 一设计与实现基本的堆栈结构下的各种操作（如堆栈的PUSH、POP等操作）（1）问题描述 实现堆栈各种基本操作，如Pop,Push,GetTop等操作，即输入数据，通过Push入栈，再通过Pop操作输出出栈的元素,即入栈a,b,c,d,出栈d,c,b,a （2）算法实现及基本思想 堆栈是后进先出的线性表，由Push输入元素，Pop输出元素，堆栈的Push 操作思想,即插入元素e为新的的栈顶元素，先判断栈满与否，追加存储空间，然后将e值赋给栈顶指针Top。输入数据时用for循环 堆栈的Pop操作思想，先判断栈是否为空，若栈不空，则删除栈的栈顶元素，用e返回其值， （3）数据结构 栈的顺序存储结构 Typedef struct {图的遍历操作实验报告
数据结构实验十一：图实验
MATLAB基本操作实验报告
数据结构实验五矩阵的压缩存储与运算学习资料
数据结构实验报告图实验
数据结构实验五图子系统
图的遍历实验报告
数据结构实验报告图实验
实验报告1windows的基本操作范例
数据结构实验报告5(电大)
数据结构实验
数据结构实验图的基本操作
数据结构实验——查找算法的实现
数字图像处理实验报告
数据结构实验报告(图)
数字图像处理实验报告
数据结构 实验报告三