实现图的遍历算法
1.需求分析
对于下图G,编写一个程序输出从顶点0开始的深度优先遍历序列(非递归算法)和广度优先遍历序列(非递归算法)。
2.系统设计
1.用到的抽象数据类型的定义
图的抽象数据类型定义:
ADT Graph{
数据对象V:V是具有相同特性的数据元素的集合,称为顶点集
数据关系R:
R={VR}
VR={
谓词P(v,w)定义了弧
基本操作P:
CreatGraph(&G,V,VR)
初始条件:V是图的顶点集,VR是图中弧的集合
操作结果:按V和VR的定义构造图G
DestroyGraph(&G)
初始条件:图G存在
操作结果:销毁图G
InsertVex(&G,v)
初始条件:图G存在,v和图中顶点有相同特征
操作结果:在图G中增添新顶点v
……
InsertArc(&G,v,w)
初始条件:图G存在,v和w是G中两个顶点
操作结果:在G中增添弧
……
DFSTraverse(G,Visit())
初始条件:图G存在,Visit是顶点的应用函数
操作结果:对图进行深度优先遍历,在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit()失败,则操作失败
BFSTraverse(G,Visit())
初始条件:图G存在,Visit是顶点的应用函数
操作结果:对图进行广度优先遍历,在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit()失败,则操作失败
}ADT Graph
栈的抽象数据类型定义:
ADT Stack{
数据对象:D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系:R1={
约定an端为栈顶,ai端为栈底
基本操作:
InitStack(&S)
操作结果:构造一个空栈S
DestroyStack(&S)
初始条件:栈S已存在
操作结果:将S清为空栈
StackEmpty(S)
初始条件:栈S已存在
操作结果:若栈S为空栈,则返回TRUE,否则FALSE
……
Push(&S,e)
初始条件:栈S已存在
操作结果:插入元素e为新的栈顶元素
Pop(&S,&e)
初始条件:栈S已存在且非空
操作结果:删除S的栈顶元素,并用e返回其值
StackTraverse(S,visit())
初始条件:栈S已存在且非空
操作结果:从栈底到栈顶依次对S的每个数据元素调用函数visit(),一旦visit()失败,则操作失效
}ADT Stack
队列的抽象数据类型定义:
ADT Queue{
数据对象:D={a i|a i∈ElemSet,i=1,2,…,n,n≥0}
数据关系:Rl={|a i-1,a i∈D,i=2,…,n}
约定其中a i端为队列头,a n端为队列尾。
基本操作:
InitQueue(&Q)
操作结果:构造一个空队列Q
DestroyQueue(&Q)
初始条件:队列Q已存在
操作结果:队列Q被销毁,不再存在
QueueEmpty(Q)
初始条件:队列Q已存在
操作结果:若Q为空队列,则返回TRUE,否则FALSE
……
EnQueue(&Q,e)
初始条件:队列Q已存在
操作结果:插入元素e为Q的新的队尾元素
DeQueue(&Q,&e)
初始条件:Q为非空队列
操作结果:删除Q的队头元素,并用e返回其值
}ADT Queue
2.主程序的流程:
调用CreateDN函数创建图的邻接表G;
调用PrintDN函数输出邻接表G;
调用DFSTraverse函数深度优先遍历图;
调用BFSTraverse函数广度优先遍历图
3.函数关系调用图:
主程序
3.调试分析
(1)书上给出了图的广度优先非递归遍历算法,主要是要实现里面的FirstAdjVex(G,u)和NextAdjVex(G,u,w)函数。我刚开始编写的这两个函数分别为:
int FirstAdjVex(ALGraph G,int u){
return LocateVex(G,G.vertices[u].firstarc->adjvex);
}
int NextAdjVex(ALGraph G,int u,int w){
ArcNode *p=G.vertices[u].firstarc;
while(LocateVex(G,p->adjvex)!=w)p=p->nextarc;
p=p->nextarc;
if(!p)return -1;
return LocateVex(G,p->adjvex);
}
对于书上给出的BFSTraverse函数这样没有问题。但当我仿照BFSTraverse函数编出了DFSTraverse函数后就有问题了。经过分析我把以上两个函数稍作了改动:
int FirstAdjVex(ALGraph G,int u){
if(!G.vertices[u].firstarc)return -1;
return LocateVex(G,G.vertices[u].firstarc->adjvex);
}
int NextAdjVex(ALGraph G,int u,int w){
ArcNode *p=G.vertices[u].firstarc;
while(p&&LocateVex(G,p->adjvex)!=w)p=p->nextarc;
if(!p)return FirstAdjVex(G,u);
p=p->nextarc;
if(!p)return -1;
return LocateVex(G,p->adjvex);
}
(2)算法的时间复杂度分析:
遍历图的过程实质上是对每个顶点查找其邻接点的过程,其耗费的时间取决于所采用的存储结构。当以邻接表作图的存储结构时,找邻接点所需时间为O(e),其中e为无向图的边数或有向图的弧数。由此,当以邻接表作存储结构时,深度优先搜索遍历图的时间复杂度为O(n+e)广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同,两者不同之处仅仅在于对顶点访问的顺序不同。
4.测试结果
用需求分析中的测试数据
输入:
输出:
5、用户手册
(1)输入顶点数和弧数;(2)输入顶点内容;
(3)输入弧,弧尾/弧头/权值
(4)回车输出深度优先遍历序列和广度优先遍历序列
6、附录
源程序:
#include
#include
#define MAX_VERTEX_NUM 20
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define TRUE 1
#define OK 1
#define FALSE 0
#define ERROR 0
#define OVERFLOW -2
typedef int InfoType;
typedef int VertexType;
typedef int Status;
typedef int QElemType;
typedef int SElemType;
typedef enum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网} bool visited[MAX_VERTEX_NUM];
typedef struct ArcNode{
int adjvex;//该弧所指向的顶点在数组中的下标
struct ArcNode *nextarc;
InfoType *info;//该弧相关信息的指针
}ArcNode;
typedef struct VNode{
VertexType data;//顶点信息
ArcNode *firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum,arcnum;//图的当前顶点数和弧数
int kind;//图的种类标志
}ALGraph;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
int LocateVex(ALGraph G,VertexType v){//返回数组下标值
int i;
for(i=0;i if(G.vertices[i].data==v)return i; return -1; } void CreateDN(ALGraph &G){ //采用邻接表存储表示,构造有向图G(G.kind=DN) int i,j,k;ArcNode *p;VertexType v1,v2; G.kind=DN; printf("输入顶点数:"); scanf("%d",&G.vexnum); printf("输入弧数:"); scanf("%d",&G.arcnum); printf("输入顶点:\n"); for(i=0;i scanf("%d",&G.vertices[i].data); G.vertices[i].firstarc=NULL;//初始化指针 } for(k=0;k printf("第%d条弧:\n",k+1); scanf("%d",&v1); scanf("%d",&v2);//输入一条弧的始点和终点 i=LocateVex(G,v1);j=LocateVex(G,v2);//确定v1和v2在G中位置 p=(ArcNode*)malloc(sizeof(ArcNode));//假定有足够空间 p->adjvex=j;p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; scanf("%d",&p->info); }//for } Status 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(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; } Status InitStack(SqStack &S) {S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } Status Pop(SqStack &S,SElemType &e) {if(S.top==S.base)return ERROR; e=*--S.top; return OK; } Status GetTop(SqStack S,SElemType &e){ if(S.top==S.base)return ERROR; e=*(S.top-1); return OK; } Status StackEmpty(SqStack S) {if(S.top==S.base)return TRUE; return FALSE; } Status InitQueue(LinkQueue &Q){ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW); Q.front->next=NULL; return OK; } Status EnQueue(LinkQueue &Q,QElemType e){ QueuePtr p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p; return OK; } Status DeQueue(LinkQueue &Q,QElemType &e){ if(Q.front==Q.rear)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; } Status QueueEmpty(LinkQueue Q){ if(Q.front==Q.rear)return TRUE; return FALSE; } int FirstAdjVex(ALGraph G,int u){ if(!G.vertices[u].firstarc)return -1; return LocateVex(G,G.vertices[u].firstarc->adjvex); } int NextAdjVex(ALGraph G,int u,int w){ ArcNode *p=G.vertices[u].firstarc; while(p&&LocateVex(G,p->adjvex)!=w)p=p->nextarc; if(!p)return FirstAdjVex(G,u); p=p->nextarc; if(!p)return -1; return LocateVex(G,p->adjvex); } void Visit(ALGraph G,int v){ printf("%2d",G.vertices[v].data); } void DFSTraverse(ALGraph G){ //按深度优先非递归遍历图G,使用辅助栈S和访问标志数组visited int v,w;SqStack S; for(v=0;v InitStack(S); for(v=0;v if(!visited[v]){//v尚未被访问 visited[v]=TRUE; Visit(G,v); Push(S,v);//v进栈 while(!StackEmpty(S)){ for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){ if(!visited[w]){ Visit(G,w); visited[w]=TRUE; Push(S,w); GetTop(S,v); }//if }//for Pop(S,v); GetTop(S,v); }//while }//if printf("\n"); } void BFSTraverse(ALGraph G){ //按广度优先非递归遍历图G,使用辅助队列Q和访问标志数组visited int v,u,w;LinkQueue Q; for(v=0;v InitQueue(Q); for(v=0;v if(!visited[v]){//v尚未被访问 visited[v]=TRUE; Visit(G,v); EnQueue(Q,v);//v入队列 while(!QueueEmpty(Q)){ DeQueue(Q,u);//队头元素出队并置为u for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)) if(!visited[w]){//w为u的尚未访问的邻接顶点 visited[w]=TRUE;Visit(G,w); EnQueue(Q,w); }//if }//while }//if printf("\n"); } void PrintDN(ALGraph G){ int i;ArcNode *p; printf("顶点:\n"); for(i=0;i printf("%2d",G.vertices[i].data); printf("\n弧:\n"); for(i=0;i p=G.vertices[i].firstarc; if(p){ while(p){ printf("%d→%d(%d)\t",i,p->adjvex,p->info); p=p->nextarc; } printf("\n"); }//if }//for } void main(){ ALGraph G; CreateDN(G); PrintDN(G); printf("深度优先遍历:"); DFSTraverse(G); printf("广度优先遍历:"); BFSTraverse(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 南昌航空大学 数学与信息科学学院 实验报告 课程名称:数学实验 实验名称: MATLAB基本操作 实验类型:验证性■综合性□ 设计性□ 实验室名称:数学实验室 班级学号: 10 学生姓名:钟 X 任课教师(教师签名): 成绩: 实验日期: 2011-10- 10 一、实验目的 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:在[-2,2]范围内绘制tanh的图形。实验程序: >> fplot('tanh',[-2,2]) 实验四:图的遍历 题目:图及其应用——图的遍历 班级:姓名:学号:完成日期: 一.需求分析 1.问题描述:很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序,演示在连通的无向图上访问全部结点的操作。 2.基本要求:以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 3.测试数据:教科书图7.33。暂时忽略里程,起点为北京。 4.实现提示:设图的结点不超过30个,每个结点用一个编号表示(如果一个图有n个结点,则它们的编号分别为1,2,…,n)。通过输入图的全部边输入一个图,每个边为一个数对,可以对边的输入顺序作出某种限制,注意,生成树的边是有向边,端点顺序不能颠倒。 5.选作内容: (1).借助于栈类型(自己定义和实现),用非递归算法实现深度优先遍历。 (2).以邻接表为存储结构,建立深度优先生成树和广度优先生成树,再按凹入表或树形打印生成树。 二.概要设计 1.为实现上述功能,需要有一个图的抽象数据类型。该抽象数据类型的定义为: ADT Graph { 数据对象V:V是具有相同特性的数据元素的集合,称为顶点集。 数据关系R: R={VR} VR={ 实验名称: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文件夹中。 步骤:①在"开始"菜单的"所有程序"子菜单中找到"计算器",单击右键,在弹出的快捷菜单中选择“发送到\桌面快捷方式”。 ②在"开始"菜单的"所有程序"子菜单中找到"画图",将其拖至桌面空白处。 ③在桌面上单击右键,在弹出的快捷菜单中选择“新建\快捷方式”,在“创建快捷方式” 数据结构B实验报告 一、实验内容 图的生成、图的遍历 二、实验目的 掌握图的基本存储结构 掌握图的相关算法 掌握图的两种遍历方法 三、功能 本实验要求实现以下功能: 1.以邻接矩阵或者邻接表作为存储结构建立一个无向图。 2.深度优先搜索该无向图,输出遍历序列。 3.广度优先搜索该无向图,输出遍历序列。 四、主要代码 #include 数据结构实验报告 实验:图的遍历 一、实验目的: 1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表 2、掌握图的构造方法 3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法 4、掌握图的深度优先遍历和广度优先原理 二、实验内容: 1、输入顶点数、边数、每个顶点的值以及每一条边的信息,构造一个无向图G,并用邻接矩阵存储改图。 2、输入顶点数、边数、每个顶点的值以及每一条边的信息,构造一个无向图G,并用邻接表存储该图 3、深度优先遍历第一步中构造的图G,输出得到的节点序列 4、广度优先遍历第一部中构造的图G,输出得到的节点序列 三、实验要求: 1、无向图中的相关信息要从终端以正确的方式输入; 2、具体的输入和输出格式不限; 3、算法要具有较好的健壮性,对错误操作要做适当处理; 4、程序算法作简短的文字注释。 四、程序实现及结果: 1、邻接矩阵: #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. 实验目的 (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 目录 实验一:数字图像的基本处理操作 (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('原图像'); 结果如图所示: 武汉东湖学院 实验报告 学院:计算机科学学院—专业计算机科学与技术2016年11月18日 1.实验目的 (1)了解邻接矩阵存储法和邻接表存储法的实现过程。 (2)了解图的深度优先遍历和广度优先遍历的实现过程。 2.实验内容 1.采用图的邻接矩阵存储方法,实现下图的邻接矩阵存储,并输出该矩阵 2.设计一个将第1小题中的邻接矩阵转换为邻接表的算法,并设计一个在屏幕上显示邻接表的算法 3.实现基于第2小题中邻接表的深度优先遍历算法,并输出遍历序列 4.实现基于第2小题中邻接表的广度优先遍历算法,并输出遍历序列 3.实验环境Visual C++ 6.0 4 .实验方法和步骤(含设计) 我们通过二维数组中的值来表示图中节点与节点的关系。通过上图可 知, 其邻接矩阵示意图为如下: V0 v1 v2 v3 v4 v5 V0 1 0 1 0 1 V1 1 0 1 1 1 0 V2 0 1 0 0 1 0 V3 1 1 0 0 1 1 V4 0 1 1 1 0 0 V5 1 1 此时的 “1 ” 表示这两个节点有关系,“ 0”表示这两个节点无关系 我们通过邻接表来在计算机中存储图时,其邻接表存储图如下: 5.程序及测试结果 #include 一.实验目的 熟悉图的存储结构,掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法,并能运用图的深度优先搜索遍历一个图,对其输出。 二.实验原理 深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问,则深度优先搜索可从图中某个顶点v出发,访问此顶点,然后依次从v的未被访问的邻接点出发深度优先遍历图,直至图中所有与v有路径相通的顶点都被访问到;若此时图有顶点未被访问,则另选图中一个未曾访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。 图的邻接表的存储表示: #define MAX_VERTEX_NUM 20 #define MAXNAME 10 typedef char VertexType[MAXNAME]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 三.实验容 编写LocateVex函数,Create函数,print函数,main函数,输入要构造的图的相关信息,得到其邻接表并输出显示。 四。实验步骤 1)结构体定义,预定义,全局变量定义。 #include"stdio.h" #include"stdlib.h" #include"string.h" #define FALSE 0 #define TRUE 1 #define MAX 20 typedef int Boolean; #define MAX_VERTEX_NUM 20 目录 实验一:数字图像的基本处理操作....................................................................... 错误!未定义书签。:实验目的 .............................................................................................................. 错误!未定义书签。:实验任务和要求..................................................................................................... 错误!未定义书签。:实验步骤和结果..................................................................................................... 错误!未定义书签。:结果分析................................................................................................................. 错误!未定义书签。实验二:图像的灰度变换和直方图变换............................................................... 错误!未定义书签。:实验目的 .............................................................................................................. 错误!未定义书签。:实验任务和要求..................................................................................................... 错误!未定义书签。:实验步骤和结果..................................................................................................... 错误!未定义书签。:结果分析................................................................................................................. 错误!未定义书签。实验三:图像的平滑处理....................................................................................... 错误!未定义书签。:实验目的 .............................................................................................................. 错误!未定义书签。:实验任务和要求..................................................................................................... 错误!未定义书签。:实验步骤和结果..................................................................................................... 错误!未定义书签。:结果分析................................................................................................................. 错误!未定义书签。实验四:图像的锐化处理......................................................................................... 错误!未定义书签。:实验目的 .............................................................................................................. 错误!未定义书签。:实验任务和要求..................................................................................................... 错误!未定义书签。:实验步骤和结果..................................................................................................... 错误!未定义书签。:结果分析................................................................................................................. 错误!未定义书签。 实验五图的基本操作 一、实验目的 1、使学生可以巩固所学的有关图的基本知识。 2、熟练掌握图的存储结构。 3、熟练掌握图的两种遍历算法。 二、实验内容 [问题描述] 对给定图,实现图的深度优先遍历和广度优先遍历。 [基本要求] 以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列。 【测试数据】 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握图的相关概念。 2、掌握图的逻辑结构和存储结构。 3、掌握图的两种遍历算法的实现。 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果,对程序进行分析。 五、算法设计 1、程序所需头文件已经预处理宏定义和结构体定义如下 #include 精品文档数据结构 实 验 报 告 目的要求 1.掌握图的存储思想及其存储实现。 2.掌握图的深度、广度优先遍历算法思想及其程序实现。 3.掌握图的常见应用算法的思想及其程序实现。 实验内容 1.键盘输入数据,建立一个有向图的邻接表。 2.输出该邻接表。 3.在有向图的邻接表的基础上计算各顶点的度,并输出。 4.以有向图的邻接表为基础实现输出它的拓扑排序序列。 5.采用邻接表存储实现无向图的深度优先递归遍历。 6.采用邻接表存储实现无向图的广度优先遍历。 7.在主函数中设计一个简单的菜单,分别调试上述算法。 源程序: 主程序的头文件:队列 #include 数字图像处理实验报告实验一数字图像基本操作及灰度调整 一、实验目的 1)掌握读、写图像的基本方法。 2)掌握MATLAB语言中图像数据与信息的读取方法。 3)理解图像灰度变换处理在图像增强的作用。 4)掌握绘制灰度直方图的方法,理解灰度直方图的灰度变换及均衡化的方法。 二、实验内容与要求 1.熟悉MATLAB语言中对图像数据读取,显示等基本函数 特别需要熟悉下列命令:熟悉imread()函数、imwrite()函数、size()函数、Subplot()函数、Figure()函数。 1)将MA TLAB目录下work文件夹中的forest、tif图像文件读出、用到imread,imfinfo 等文件,观察一下图像数据,了解一下数字图像在MA TLAB中的处理就就是处理一个矩阵。将这个图像显示出来(用imshow)。尝试修改map颜色矩阵的值,再将图像显示出来,观察图像颜色的变化。 2)将MA TLAB目录下work文件夹中的b747、jpg图像文件读出,用rgb2gray()将其转化为灰度图像,记为变量B。 2.图像灰度变换处理在图像增强的作用 读入不同情况的图像,请自己编程与调用Matlab函数用常用灰度变换函数对输入图像进行灰度变换,比较相应的处理效果。 3.绘制图像灰度直方图的方法,对图像进行均衡化处理 请自己编程与调用Matlab函数完成如下实验。 1)显示B的图像及灰度直方图,可以发现其灰度值集中在一段区域,用imadjust函 数将它的灰度值调整到[0,1]之间,并观察调整后的图像与原图像的差别,调整后的灰度直方图与原灰度直方图的区别。 2)对B进行直方图均衡化处理,试比较与源图的异同。 3)对B进行如图所示的分段线形变换处理,试比较与直方图均衡化处理的异同。 实验三、图的遍历操作 一、目的 掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握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"" #include"" ertex); irstedge; irstedge; } } }//endwhile } //==========主函数=========== void main() { ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph)); CreatALGraph(G); printf("Print Graph DFS: "); DFS(G); printf("\n"); printf("Print Graph BFS: "); BFS(G,3); printf("\n"); } 五、实验内容 1调试程序。设计一个有向图和一个无向图,任选一种存储结构,完成有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。 邻接矩阵作为存储结构的运行结果: 邻接链表作为存储结构的运行结果: 六、实验报告要求 画出你所设计的图,写出两种方法的遍历序列。 实验一图像的基本操作和基本统计指标计算 一、实验目的 熟悉MATLAB图像处理工具箱,在掌握MATLAB基本操作的基础上,本课程主要依靠图像处理工具箱验证和设计图像处理算法。对于初学者来说,勤学多练、熟悉MATLAB图像处理工具箱也是学号本课程的必经之路。 了解计算图像的统计指标的方法及其在图像处理中的意义。 了解图像的几何操作,如改变图像大小、剪切、旋转等。 二、实验主要仪器设备 (1)台式计算机或笔记本电脑 (2)MATLAB(安装了图像处理工具箱,即Image Processing Toolbox(IPT)) (3)典型的灰度、彩色图像文件 三、实验原理 (1)将一幅图像视为一个二维矩阵。 < (2)利用MATLAB图像处理工具箱读、写和显示图像文件。 ①调用imread函数将图像文件读入图像数组(矩阵)。例如“I=imread(‘’);”。其基本格式为:“A=imread(‘’)”,其中,A为二维矩阵,filename.为文件名,fmt为图像文件格式的扩展名。 ②调用imwrite函数将图像矩阵写入图像文件。例如“imwrite(A,’’);”。其基本格式为“imwrite(a,”。 ③调用imshow函数显示图像。例如“imshow(‘’);”。其基本格式为:I为图像矩阵,N 为显示的灰度级数,默认时为256。 (3)计算图像有关的统计参数。 四、实验内容 (1)利用MATLAB图像处理工具箱和Photoshop读、写和显示图像文件。 (2)利用MATLAB计算图像有关的统计参数。 五、实验步骤 (1)利用“读图像文件I/O”函数读入图像。 (2)利用“读图像文件I/O”的iminfo函数了解图像文件的基本信息:主要包括Filename(文件名)、FileModDate(文件修改时间)、Filesize(文件尺寸)、Format(文件格式)、FormatVersion(格式版本)、Width(图像宽度)、Height(图像高度)、BitDepth(每个像素的位深度)、ColorType(彩色类型)、CodingMethod(编码方法)等。 ' (3)利用“像素和统计处理”函数计算读入图像的二维相关系数(corr2函数)、确定像素颜色值(impixel函数)、确定像素的平均值(mean2函数)、显示像素信息(pixval函数)、计算像素的标准偏移(std2函数)等。 要求:参照例题,对图像J加均值为0、方差为的高斯白噪声形成有噪图像J1,即图的遍历操作实验报告
MATLAB基本操作实验报告
图的遍历实验报告
实验报告1windows的基本操作范例
图的生成、图的遍历
数据结构实验报告-图的遍历
数据结构实验图的基本操作
数据结构实验报告图实验
数字图像处理实验报告
实验报告:图的存储结构和遍历
图的深度优先遍历实验报告
数字图像处理实验报告
图的基本操作 实验报告
数据结构实验—图实验报告
数字图像处理实验报告
图的遍历操作实验报告
数字图像处理实验一图像的基本操作和基本统计指标计算实验报告