数据结构
课程设计报告设计题目:图的基本操作与实现
专业
班级
学生
学号
指导教师
起止时间
年学期
目录
1.问题描述:实现图的一些基本操作 (3)
2.基本要求: (3)
(2)求每个顶点的度,输出结果; (3)
3.测试数据: (3)
4.算法思想: (3)
(1)自选存储结构创建一个图: (3)
(2)求每个顶点的度: (3)
(3)图的深度优先遍历: (4)
(4)图的广度优先遍历: (4)
(5)判断有向图的强连通性: (4)
(6)用邻接矩阵的信息生成邻接表: (5)
6.数据结构: (6)
7.功能模块图 (7)
8.源程序: (8)
9.心得体会: (29)
1.问题描述:实现图的一些基本操作
2.基本要求:
(1)自选存储结构,输入含n个顶点(用字符表示顶点)和e条边的图G;
(2)求每个顶点的度,输出结果;
(3)指定任意顶点x为初始顶点,对图G作DFS遍历,输出DFS顶点序列(提示:使用一个栈实现DFS);
(4)指定任意顶点x为初始顶点,对图G作BFS遍历,输出BFS顶点序列(提示:使用一个队列实现BFS);
(5)输入顶点x,查找图G:若存在含x的顶点,则删除该结点及与之相关连的边,并作DFS遍历(执行操作3);否则输出信息“无x”;
(6)判断图G是否是连通图,输出信息“YES”/“NO”;
(7)如果选用的存储结构是邻接矩阵,则用邻接矩阵的信息生成图G的邻接表,即复制图G,然再执行操作(2);反之亦然。
3.测试数据:
有向图的顶点数n和有向图的边数e由用户从键盘敲入
4.算法思想:
(1)自选存储结构创建一个图:通过用户从键盘敲入的两个数值分别确定图的顶点数和边数,选择邻接矩阵存储结构将图的结点信息存储在一个顺序表中,图的边信息存储在一个二维数组中。
(2)求每个顶点的度:
1.邻接矩阵存储结构下求每个顶点的度:利用图的邻接矩阵,每个顶点所在行
和所在列的边的权值如果存在则该顶点的度+1,依次算出每个顶点的度,并且记录在一个数组中输出。
2.邻接表存储结构下求每个顶点的度:定义一个邻接边指针循环指向顶点的邻接边单链表头结点,当结点不空时,该顶点的出度+1,邻接边弧头结点的入度+1,依次求出每个顶点的出度和入度之和就为该顶点的度。
(3)图的深度优先遍历:采取邻接矩阵结构,指定任意顶点x为初始顶点
1.访问结点v并标记结点v已访问;
2.查找结点v的第一个邻接结点w;
3.若结点v的邻接结点w存在,则继续执行,否则算法结束;
4.若结点w尚未被访问,则递归访问结点w;
5.查找结点v的w邻接结点的下一个邻接结点w,转到步骤3。
(4)图的广度优先遍历:采取邻接矩阵结构,指定任意顶点x为初始顶点,利用顺序循环队列以保持访问过的结点的顺序
1.首先访问初始结点v并标记结点v为已访问;
2.结点v入队列;
3.当队列非空时则继续执行,否则算法结束;
4.出队列取得队头结点u;
5.查找u的第一个邻接结点w;
6.若u的邻接结点w不存在则转到步骤3,否则循环执行下列步骤:
6.1若结点w尚未被访问,则访问结点w并标记结点w为已访问;
6.2结点w入队列;
6.3查找结点u的w邻接结点的下一个邻接结点w,转到步骤6 。
(5)判断有向图的强连通性:采取邻接表结构,在图中寻找一个包含所有顶点
且首尾相连的环,若这样的环存在,则该图为强连通图,否则不为强连通图。
(6)用邻接矩阵的信息生成邻接表:定义一个邻接表的边信息结构体,将邻接矩阵的边信息转换成邻接表的边信息存储到邻接边的单链表中。
5.模块划分:
mian():主函数模块。在主函数模块中调用以下函数:
(1)void CreatGraph(AdjMGraph *G,DataType v[],int
n,RowColWeight E[],int e):创建一个邻接矩阵存储结构的图;
(2)void Print(AdjMGraph *G):输出图的邻接矩阵;
(3)void MVertices(AdjMGraph *G,DataType a[]):求出邻接矩阵存
储结构下图的每个顶点的度;
(4)void CreatLGraph(AdjLGraph *G,DataType v[],int n,RowCol
d[],int e):用邻接矩阵的信息生成邻接表;
(5)void LVertices(AdjLGraph *G,DataType a[]):求出邻接表存储结
构下图的每个顶点的度;
(6)int LianTong(AdjLGraph *G,DataType a[]):判断有向图的强连通
性;
(7)void DepthFirstSearch(AdjMGraph G,void Visit(DataType
item)):对图作DFS遍历,输出DFS顶点序列;
(8)void BroadFirstSearch(AdjMGraph G,void Visit(DataType
item)):对图作BFS遍历,输出BFS顶点序列;
(9)int ChaZhao(AdjMGraph *G,int v):查找顶点v;
(10)void MDelete(AdjMGraph *G,int v):删除查找到的结点v并删除
该结点及与之相关的边;
6.数据结构:
(1)有向图顶点的数据类型DataType 定义如下:typedef int DataType ;
(2)邻接矩阵存储结构下图的结构体定义如下:
typedef struct
{
SeqList Vertices;//存放结点的顺序表
int edge[MaxVertices][MaxVertices];//存放边的邻接矩阵int numOfEdges;//边的条数
}AdjMGraph;//边的结构体定义
(3)邻接矩阵存储结构下图的边信息结构体定义如下:
typedef struct
{
int row;//行下标
int col;//列下标
int weight;//权值
}RowColWeight;//边信息结构体定义
(4)邻接表存储结构下图的结构体定义如下:
typedef struct Node
{
int dest;//邻接边的弧头结点序号
struct Node *next;
}Edge;//邻接边单链表的结点结构体
typedef struct
{
DataType data;//结点数据元素
int sorce;//邻接边的弧尾结点序号
Edge *adj;//邻接边的头指针
}AdjLHeight;//数组的数据元素类型结构体
typedef struct
{
AdjLHeight a[MaxVertices];//邻接表数组
int numOfVerts;//结点个数
int numOfEdges;//边个数
}AdjLGraph;//邻接表结构体
(5)邻接表存储结构下图的边信息结构体定义如下:
typedef struct
{
int row;//行下标
int col;//列下标
}RowCol;//边信息结构体定义
(6)顺序循环队列的结构体定义如下:
typedef struct
{
DataType queue[MaxQueueSize];
int rear;
int front;
int count;
}SeqCQueue;
(7)顺序表的结构体定义如下:
typedef struct
{
DataType list[MaxSize];
int size;
}SeqList;
7.功能模块图:
8.源程序:
源程序存放在八个文件夹中,文件SeqList.h是顺序表的结构体定义和操作函数,文件SeqCQueue.h是顺序循环队列的结构体定义和操作函数,文件AdjMGraph.h是邻接矩阵存储结构下图的结构体定义和操作函数,文件AdjMGraphCreate.h是邻接矩阵存储结构下图的创建函数,文件AdjLGraph.h是邻接表存储结构下图的结构体定义和操作函数,文件AdjLGraphCreate.h是邻接表存储结构下图的创建函数,文件AdjMGraphTraverse.h是邻接矩阵存储结构下图的深度优先遍历和广度优先遍历操作函数,文件图的基本操作与实现.c是主函数。
(1)/* 文件SeqList.h */
typedef struct
. .. . .. .. 实验三、图的遍历操作 一、目的 掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握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])
邻接表表示的图的基本操作的实现 //采用邻接表完成无权无向及有向图的"建立、输出、深度遍历、广度遍历"操作 #include
typedef struct Headnode//头结点结构 { ElemType vertex;//顶点域vertex,存放顶点vi的信息 struct Tablenode *firstEdge;//vi的邻接表的头指针 }HeadNode; typedef struct Mgraph { struct Headnode vector[MAX_VERTEX_NUM]; //顶点向量 int vexnum; //图中当前顶点数 } MGraph; //队列初始化 Status InitLinkQueue(LinkQueue *Q) { QNode *p; p=(QNode*)malloc(sizeof(QNode));//开辟头结点空间 if(p!=NULL) { p->next=NULL; Q->front=Q->rear=p; return OK; } else return ERROR; } //链式队列的入队操作,在已知队列的队尾插入一个元素e,修改队尾指针rear。 Status InsertLinkQueue(LinkQueue *Q,ElemType e) { QNode *p;
实验五图的遍历及其应用实现 一、实验目的 1.熟悉图常用的存储结构。 2.掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。 3.会用图的遍历解决简单的实际问题。 二、实验内容 [题目一] :从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。 提示: 输入示例 上图的顶点和边的信息输入数据为: 5 7 DG A B C D E AB AE BC CD DA DB EC [题目二]:在图G中求一条从顶点 i 到顶点 s 的简单路径 [题目三]:寻求最佳旅游线路(ACM训练题) 在一个旅游交通网中,判断图中从某个城市A到B是否存在旅游费用在s1-s2元的旅游线路,为节省费用,不重游故地。若存在这样的旅游线路则并指出该旅游线路及其费用。 输入: 第一行:n //n-旅游城市个数 第2行:A B s1 s2 //s1,s2-金额数 第3行---第e+2行 ( 1≤e≤n(n-1)/2 ) 表示城市x,y之间的旅行费用,输入0 0 0 表示结束。
输出: 第一行表示 A到B的旅游线路景点序列 第二行表示沿此线路,从A到B的旅游费用 设计要求: 1、上机前,认真学习教材,熟练掌握图的构造和遍历算法,图的存储结 构也可使用邻接矩阵等其他结构. 2、上机前,认真独立地写出本次程序清单,流程图。图的构造和遍历算法 分别参阅讲义和参考教材事例 图的存储结构定义参考教材 相关函数声明: 1、/* 输入图的顶点和边的信息,建立图*/ void CreateGraph(MGraph &G) 2、/* 深度优先搜索遍历图*/ void DFSTraverse(Graph G, int v) 3、/*广度优先搜索遍历图 */ void BFSTraverse(Graph G, int v)4、 4、/* 其他相关函数 */…… 三、实验步骤 ㈠、数据结构与核心算法的设计描述 ㈡、函数调用及主函数设计 (可用函数的调用关系图说明) ㈢程序调试及运行结果分析 ㈣实验总结 四、主要算法流程图及程序清单 1、主要算法流程图: 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文件夹中。 步骤:①在"开始"菜单的"所有程序"子菜单中找到"计算器",单击右键,在弹出的快捷菜单中选择“发送到\桌面快捷方式”。 ②在"开始"菜单的"所有程序"子菜单中找到"画图",将其拖至桌面空白处。 ③在桌面上单击右键,在弹出的快捷菜单中选择“新建\快捷方式”,在“创建快捷方式”
浙江大学城市学院实验报告 课程名称数据结构 实验项目名称实验十三/十四图的基本操作 学生姓名专业班级学号 实验成绩指导老师(签名)日期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 第一课:工具的使用 一、Photoshop 简介: Adobe 公司出品的Photoshop 是目前最广泛的图像处理软件,常用于广告、艺术、平面设计等创作。也广泛用于网页设计和三维效果图的后期处理,对于业余图像爱好者,也可将自己的照片扫描到计算机,做出精美的效果。总之,Photoshop 是一个功能强大、用途广泛的软件,总能做出惊心动魄的作品。 二、认识工具栏 1、 选框工具:用于选取需要的区域 ----选择一个像素的横向区域 ----选择一个像素的竖向区域 属性栏: 注:按shift 键+ 框选,可画出正方形或正圆形区域 2、 移动工具 : -----用于移动图层或选区里的图像 3、套索工具: ----用于套索出选区 ----用于套索出多边形选区 ----可根据颜色的区别而自动产生套索选区 4、魔术棒工具: ----根据颜色相似原理,选择颜色相近的区域。 注:“容差”,定义可抹除的颜色范围,高容差会抹除范围更广的像素。 5、修复工具: 且是 ----类似于“仿制图工具”,但有智能修复功能。 ----用于大面积的修复 一新 ----用采样点的颜色替换原图像的颜色 注:Alt+鼠标单击,可拾取采样点。 6、仿制图章工具----仿制图章工具从图像中取样,然后您可将样本应用到其它图像或同一图像的其它部分。 ----仿制图章工具从图像中取样,然后将样本应用到其它图像或同 一图像的其它部分(按Alt键,拾取采样点)。 ----可先自定义一个图案,然后把图案复制到图像的其它区域或其它图像上。 三、小技巧: ①、取消选区:【Ctrl +D 】 ②、反选选区:【Shif+F7】 ③、复位调板:窗口—工作区—复位调板位置。 ④、ctrl+[+、-]=图像的缩放 ⑤空格键:抓手工具 ⑥Atl+Delete = 用前景色填充 Ctrl+Delete = 用背景色填充 第二课:工具的使用二 一、工具栏 自由变换工具:【 Ctrl +T 】 2、使用框选工具的时候,按【Shift 】后再框选,则框选出正圆或正方形。 按【Alt 】后再框选,则选区以鼠标点为中心 使用ENVI进行图像处理 主要介绍利用envi进行图像处理的基本操作,主要分为图像合成、图像裁减、图像校正、图像镶嵌、图像融合、图像增强。 分辨率:空间分辨率、波谱分辨率、时间分辨率、辐射分辨率。咱们平时所说的分辨率是指?怎么理解? 1、图像合成 对于多光谱影像,当我们要得到彩色影像时,需要进行图像合成,产生一个与自然界颜色一致的真彩色(假彩色)图像。 对于不同类型的影像需要不同的波段进行合成,如中巴CCD影像共5个波段,一般选择2、4、3进行合成。(为什么不选择其他波段?重影/不是真彩色)。SOPT5影像共7个波段,一般选择7、4、3三个波段。 操作过程以中巴资源卫星影像为例 中巴资源卫星影像共有五个波段,选择2、4、3三个波段对R、G、B赋值进行赋值。 在ENVI中的操作如下: (1)file→open image file→打开2、3、4三个波段,选择RGB,分别将2、4、3赋予RGB。(2)在#1窗口file---〉save image as-→image file。 (3)在主菜单中将合成的文件存为tiff格式(file-→save file as-→tiff/geotiff) 即可得到我们需要的彩色图像。 2、图像裁减 有时如果处理较大的图像比较困难,需要我们进行裁减,以方便处理。如在上海出差时使用的P6、SOPT5,图幅太大不能直接校正需要裁减。 裁减图像,首先制作AOI文件再根据AOI进行裁减。一般分为两种:指定范围裁减、不指定范围裁减。 不指定范围裁减在ENVI中的操作如下: (1)首先将感兴趣区存为AOI文件 file→open image file打开原图像→选择IMAGE窗口菜单overlay→region of interesting 选择划定感兴趣区的窗口如scroll,从ROI_Type菜单选择ROI的类型如Rectangle,在窗口中选出需要选择的区域。在ROI窗口file→Save ROIs将感兴趣区存为ROI文件。 邻接矩阵的实现 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('原图像'); 结果如图所示: 标头.h #include 目录 实验一:数字图像的基本处理操作....................................................................... 错误!未定义书签。:实验目的 .............................................................................................................. 错误!未定义书签。:实验任务和要求..................................................................................................... 错误!未定义书签。:实验步骤和结果..................................................................................................... 错误!未定义书签。:结果分析................................................................................................................. 错误!未定义书签。实验二:图像的灰度变换和直方图变换............................................................... 错误!未定义书签。:实验目的 .............................................................................................................. 错误!未定义书签。:实验任务和要求..................................................................................................... 错误!未定义书签。:实验步骤和结果..................................................................................................... 错误!未定义书签。:结果分析................................................................................................................. 错误!未定义书签。实验三:图像的平滑处理....................................................................................... 错误!未定义书签。:实验目的 .............................................................................................................. 错误!未定义书签。:实验任务和要求..................................................................................................... 错误!未定义书签。:实验步骤和结果..................................................................................................... 错误!未定义书签。:结果分析................................................................................................................. 错误!未定义书签。实验四:图像的锐化处理......................................................................................... 错误!未定义书签。:实验目的 .............................................................................................................. 错误!未定义书签。:实验任务和要求..................................................................................................... 错误!未定义书签。:实验步骤和结果..................................................................................................... 错误!未定义书签。:结果分析................................................................................................................. 错误!未定义书签。 第一课:工具的使用 、 Photoshop 简介: Adobe 公司出品的 Photoshop 是目前最广泛的图像处理软件,常用于广告、艺术、平面 设计等创作。也广泛用于网页设计和三维效果图的后期处理,对于业余图像爱好者,也 可将自己的照片扫描到计算机,做出精美的效果。总之, Photoshop 是一个功能强大、 用途广泛的软件,总能做出惊心动魄的作品。 、认识工具栏 1、 选框工具 :用于选取需要的区域 选择一个像素的横向区域 选择一个像素的竖向区域 注:按 shift 键 +框选,可画出正方形或正圆形区域 可根据颜色的区别而自动产生套索选区 根据颜色相似原理,选择颜色相近的区域。 5、 修复工具 : 类似于“仿制图工具” ,但有智能修复功能。 用于大面积的修复 用采样点的颜色替换原图像的颜色 注: Alt+ 鼠标单击,可拾取采样点。 6、仿制图章工具 仿制图章工具从图像中取样, 然后您可将样本应用到其它图像或同一 图像的其它部分。 - 仿制图章工具从图像中取样,然后将样本应用到其它图像或同 一图像的其它部分(按 Alt 键,拾取采样点) 。 区域或其 它图像上。 2、 移动工具 : 3、 套索工具 : 用于移动图层或选区里的图像 - - 用于套索出选区 用于套索出多边形选 区 属性栏: 选区相交 单个选区 选区相加 选区相减 4、魔术棒工具 ,定义可抹除的颜色范围,高容差会抹除范围更广的像素。 且是 --------- - 三、小技巧: ①、取消选 区: 【Ctrl +D】 ②、反选选 区: 【Shif+F7 】 ③、 复位调 板: 窗口—工作区—复位调板位置。 ④、 ctrl+[+ 、 -]= 图像的缩放 ⑤空格键:抓手工具 ⑥ Atl+Delete = 用前景色填充 Ctrl+Delete = 用背景色填充 第二课:工具的使用二 模1、糊自工由具变换工具:【Ctrl +T】减淡工具 模糊工具 2、使用框选工具的时候,按【Shift 】后再框选,则框选出正圆或正方形。 实验五图的基本操作 一、实验目的 1、使学生可以巩固所学的有关图的基本知识。 2、熟练掌握图的存储结构。 3、熟练掌握图的两种遍历算法。 二、实验内容 [问题描述] 对给定图,实现图的深度优先遍历和广度优先遍历。 [基本要求] 以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列。 【测试数据】 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握图的相关概念。 2、掌握图的逻辑结构和存储结构。 3、掌握图的两种遍历算法的实现。 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果,对程序进行分析。 五、算法设计 1、程序所需头文件已经预处理宏定义和结构体定义如下 #include 图的基本操作与实现的课程设计报 告 中国矿业大学徐海学院计算机系 《软件认知实践》报告 姓名:_学号: 专业:___________________ 设计题目:_______________ 指导教师:____________________________ 2013年12月30日 第1章题目概述 第1.1节题目要求. 第1.2节主要难点 第2章系统流程 第3章数据结构和算法 第4章核心代码分析.. 第5章复杂度分析 参考文献 第一章题目概述 第1.1节题目要求 (1) 自选存储结构,输入含n 个顶点(用字符表示顶点)和e 条边的图G ; (2) 求每个顶点的度,输出结果; (3) 指定任意顶点x 为初始顶点,对图G 作DFS 遍历,输出DFS 顶点序列(提示:使用一个栈 实 现 DFS); ⑷指定任意顶点x 为初始顶点,对图G 作BFS 遍历,输出BFS 顶点序列(提示:使用一个队列 实现BFS); (5) 输入顶点x,查找图G:若存在含x 的顶点,则删除该结点及与之相关连的边,并作DFS 遍 历(执行操作3);否则输出信息“无x” ; (6) 判断图G 是否是连通图,输出信息“YES” / “NO”; (7) 如果选用的存储结构是邻接矩阵,则用邻接矩阵的信息生成图G 的邻接表,即复制图G, 然再执行操作(2);反之亦然。 .2 .2 .3 .4 .5 .6 25 25 第1. 2节主要难点 (1)自选存储结构创建一个图:通过用户从键盘敲入的两个数值分别确定图的顶点数和边数,选择邻接矩阵存储结构将图的结点信息存储在一个顺序表中,图的边信息存储在一个二维数组中。 (2)求每个顶点的度: 一.实验目的 熟悉图的存储结构,掌握用单链表存储数据元素信息和数据元素之间的 关系的信息的方法,并能运用图的深度优先搜索遍历一个图,对其输出。 二.实验原理 深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶 点未曾访问,则深度优先搜索可从图中某个顶点 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)掌握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进行如图所示的分段线形变换处理,试比较与直方图均衡化处理的异同。Photoshop基本操作介绍(图文介绍)
envi图像处理基本操作
数据结构实验报告图实验
数字图像处理实验报告
图的基本操作(邻接表)
数字图像处理实验报告
Photoshop基本操作介绍(图文介绍)
图的基本操作 实验报告
图的基本操作与实现的课程设计报告
图的深度优先遍历实验报告.doc
数字图像处理实验报告