邻接表表示的图的基本操作的实现

邻接表表示的图的基本操作的实现

//采用邻接表完成无权无向及有向图的"建立、输出、深度遍历、广度遍历"操作

#include

#include

#define OK 1

#define ERROR -1

typedef int Status;

typedef int ElemType; //此例中设元素为单值元素，类型为整型

#define MAX_VERTEX_NUM 20 //最大顶点个数

typedef int ElemType; //图顶点数据类型

typedef int QueueElemType;//队列结点数据类型

//链表结点类型定义

typedef struct Qnode

{

QueueElemType data;

struct Qnode *next;

}QNode;

//队列类型定义：

typedef struct Linkqueue

{

QNode *front,*rear;

}LinkQueue;

//图的数据类型定义

typedef struct Tablenode//表结点结构

{

int adjVex;//邻接点域，存放与vi相邻接的顶点vj的序号j

struct Tablenode *next;//指针域，将邻接表的所有表结点链在一起

float weight;//对于带权图，表示权值，对于无权图则可省略此数据域

}TableNode;

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;

p=(QNode*)malloc(sizeof(QNode));

if(p==NULL)

return ERROR;//申请新结点空间失败，返回错误标志

else

{

p->data=e;//存入新结点数据

p->next=NULL;

Q->rear->next=p;//新结点插入到队尾

Q->rear=p;//新插入结点成为新的队尾

return OK;

}

}

//链式队列的出队操作，取第一个数据结点的数据后删除该结点

Status DeleteLinkQueue(LinkQueue *Q,ElemType *e)

{

QNode *p;

if(Q->front==Q->rear)//可改为：if(Q->front->next==NULL)

return ERROR;//队空

else

{

p=Q->front->next;//取队首结点

*e=p->data;

Q->front->next=p->next;//修改队首指针

if(p==Q->rear)//条件成立说明只有一个数据结点

Q->rear=Q->front;//当队列只有一个数据结点时应防止丢失队尾指针

free(p);

Q->rear->next=NULL;

return OK;

}

}

//判断队列是否为空

Status IsEmptyLinkQueue(LinkQueue *Q)

{

if(Q->front==Q->rear)

return OK;

else

return ERROR;

}

//释放队列

void DestroyLinkQueue(LinkQueue *Q)

{

QNode *p,*q;

p=Q->front;//指向链表第一个结点，即整个链表的第一个结点while(p!=NULL)

{

q=p->next;//保存链表后半段首地址以防丢失

free(p);

p=q;

}

}

/**************以下为图的操作************/

//顶点在顶点向量中的定位，找到返回OK，否则返回ERROR

//G为的数据结构，v为待查顶点，n用于返回找到的顶点下标Status LocateVex(MGraph G,ElemType v,int *n)

{

int i;

for(i=0;((i

*n=i;

if(i

return OK;

else

return ERROR;

}

//建立无向图的邻接表

void CreateGraph(MGraph *G)

{

int i,k;

Status sfjx;

TableNode *p,*q;

ElemType v;

printf("请输入图的顶点数：");

scanf("%d",&(G->vexnum));

printf("请输入%d个顶点信息：\n",G->vexnum);

for(i=0;ivexnum;i++) //输入顶点向量

scanf("%d",&(G->vector[i].vertex));

printf("顶点向量如下：\n"); //输出顶点向量

for(i=0;ivexnum;i++)

printf("%4d",G->vector[i].vertex);

printf("\n请逐个输入无权图各顶点的邻接点(输入不存在的邻接点则表示结束)：\n");

for(k=0;kvexnum;k++) //输入无权图的邻接点

{

printf("请输入顶点%d的邻接点：",G->vector[k].vertex);

G->vector[k].firstEdge=(TableNode

*)malloc(sizeof(TableNode));

q=G->vector[k].firstEdge;

fflush(stdin);

do

{

scanf("%d",&v);

sfjx=LocateVex(*G,v,&i);

if(sfjx==OK)

{

p=(TableNode *)malloc(sizeof(TableNode));

if(p!=NULL)

{

p->adjVex=i;

q->next=p;

q=p;

}

}

}while(sfjx==OK);

q->next=NULL;

}

}

//输出无向图的邻接表

void PrintGraph(MGraph G)

{

int i;

TableNode *p;

printf("图信息如下：\n");

for(i=0;i

{

printf("%4d:",G.vector[i].vertex);

p=G.vector[i].firstEdge->next;

while(p!=NULL)

{

printf("%4d",p->adjVex);

p=p->next;

}

printf("\n");

}

}

//查找顶点v的第一个邻接点，v为当前顶点下标int FirstAdjVex(MGraph G,int v)

{

int p=-1;

TableNode *q;

q=G.vector[v].firstEdge->next;

if(q!=NULL)

p=q->adjVex;

return p;

}

//查找顶点v的下一个邻接点，w为当前邻接点下标int NextAdjVex(MGraph G,int v,int w)

{

int p=-1;

TableNode *q;

q=G.vector[v].firstEdge->next;

while((q!=NULL)&&(q->adjVex!=w))

q=q->next;

if(q!=NULL)

{

q=q->next;

if(q!=NULL)

p=q->adjVex;

}

return p;

}

//深度优先遍历

char visited[MAX_VERTEX_NUM];//访问标志数组

void Dfs(MGraph G,int v)

{

int w;

visited[v]=1;

printf("%4d",G.vector[v]);

for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if(visited[w]==0)

Dfs(G,w);

}

void DfsTraverse(MGraph G)

{

int v;

for(v=0;v

visited[v]=0;

for(v=0;v

if(visited[v]==0)

Dfs(G,v);

}

//广度优先遍历

void BfsTraverse(MGraph G)

{

int v,u,w;

LinkQueue Q;

for(v=0;v

visited[v]=0;

InitLinkQueue(&Q);

for(v=0;v

if(visited[v]==0)

{

visited[v]=1;

printf("%4d",G.vector[v]);

InsertLinkQueue(&Q,v);

while(IsEmptyLinkQueue(&Q)!=OK)

{

DeleteLinkQueue(&Q,&u);

for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))

if(visited[w]==0)

{

visited[w]=1;

printf("%4d",G.vector[w]);

InsertLinkQueue(&Q,w);

}

}

}

DestroyLinkQueue(&Q);

}

//主函数

void main()

{

int xz=1;

MGraph G;

while(xz!=0)

{

printf("1－输入图信息\n");

printf("2－输出图信息\n");

printf("3－图的深度优先遍历\n");

printf("4－图的广度优先遍历\n");

printf("0－退出\n请选择：");

fflush(stdin);

scanf("%d",&xz);

switch(xz)

{

case 1:

CreateGraph(&G);

break;

case 2:

PrintGraph(G);

break;

case 3:

DfsTraverse(G);

printf("\n");

break;

case 4:

BfsTraverse(G);

printf("\n");

break;

case 0:

printf("再见！\n");

break;

default:

printf("输入错误！\n");

break;

}

}

}

图的邻接矩阵存储结构建立汇总

课程名称: 《数据结构》课程设计课程设计题目:图的邻接矩阵存储结构建立 姓名:XXX 院系:计算机学院 专业:计算机科学技术 年级:11级 学号:XXXXXXXX 指导教师:XXX 2013年9月28日

目录 1 课程设计的目的 (3) 2需求分析 (3) 3 课程设计报告内容 (3) 3.1 概要设计 (3) 3.2 详细设计 (4) 3.3 调试分析 (5) 3.4 用户手册 (5) 3.5 程序清单 (5) 3.6 测试结果 (10) 4 小结 (12) 5 参考文献 (12)

1.课程设计的目的 (1) 熟练使用 C 语言编写程序，解决实际问题; (2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力; (3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; (4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 2.需求分析 问题描述:建立图的邻接矩阵存储结构(图的类型可以是有向图或有向网、无向图或无向网，学生可以任选一种类型)，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后给出图的DFS,BFS次序。 要求： ①先任意创建一个图； ②图的DFS,BFS的递归和非递归算法的实现。 3.课程设计报告内容 3.1概要设计 1.函数 ①主函数：main( ) ②创建无向图：CreateGraph( )

③深度优先遍历图：DFS( ) ④广度优先遍历图：BFS( ) 3.2详细设计 1.使用邻接矩阵作为图的存储结构，程序中主要用到的抽象数据类型： typedef struct { char vexs[MAX]; //顶点向量 int arcs[MAX][MAX]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数}Graph; 2.程序流程图：

邻接表存储表示

邻接表存储表示 Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 { InitALGraph(G); scanf("%d",&v); if(v<0) return ERROR; G.vexnum=v; scanf("%d",&a); if(a<0) return ERROR; G.arcnum=a; for(m=0;mnextarc;q=q->nextarc); q->nextarc=p; } p->adjvex=j;p->nextarc=NULL; }//while return OK; }//Build_AdjList 邻接多重表存储表示 Status Build_AdjMulist(AMLGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接多重表 { InitAMLGraph(G); scanf("%d",&v); if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(%d",&a); if(a<0) return ERROR; //边数不能为负 G.arcnum=a; for(m=0;m

邻接表存储结构建立无向图

//算法功能：采用邻接表存储结构建立无向图 #include #include #define OK 1 #define NULL 0 #define MAX_VERTEX_NUM 20 // 最大顶点数 typedef int Status; //函数的类型，其值是函数结果状态代码 typedef char VertexType; typedef int VRType; typedef int InforType; typedef struct ArcNode { int adjvex; //该边所指的顶点的位置 struct ArcNode *nextarc; //指向下一条边的指针 int weight; //边的权 }ArcNode; //表的结点 typedef struct VNode { VertexType data; //顶点信息（如数据等） ArcNode *firstarc; //指向第一条依附该顶点的边的弧指针}VNode, AdjList[MAX_VERTEX_NUM]; //头结点 typedef struct ALGraph { AdjList vertices; int vexnum, arcnum; //图的当前顶点数和弧数 }ALGraph; //返回顶点v在顶点向量中的位置 int LocateVex(ALGraph G, char v) { int i; for(i = 0; v != G.vertices[i].data && i < G.vexnum; i++) ; if(i >= G.vexnum) return -1;

邻接表表示的图的基本操作的实现

邻接表表示的图的基本操作的实现 //采用邻接表完成无权无向及有向图的"建立、输出、深度遍历、广度遍历"操作 #include #include #define OK 1 #define ERROR -1 typedef int Status; typedef int ElemType; //此例中设元素为单值元素，类型为整型 #define MAX_VERTEX_NUM 20 //最大顶点个数 typedef int ElemType; //图顶点数据类型 typedef int QueueElemType;//队列结点数据类型 //链表结点类型定义 typedef struct Qnode { QueueElemType data; struct Qnode *next; }QNode; //队列类型定义： typedef struct Linkqueue { QNode *front,*rear; }LinkQueue; //图的数据类型定义 typedef struct Tablenode//表结点结构 { int adjVex;//邻接点域，存放与vi相邻接的顶点vj的序号j struct Tablenode *next;//指针域，将邻接表的所有表结点链在一起 float weight;//对于带权图，表示权值，对于无权图则可省略此数据域 }TableNode;

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）对于无向图的邻接矩阵的第i 行非零元素的个数正好是第i 个顶点的度()i v TD 。3）对于有向图，邻接矩阵的第i 行非零元素的个数正好是第i 个顶点的出度()i v OD （或入度 ()i v ID ） 。4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所发费得时间代价大。 邻接表是图的一种顺序存储与链式存储相结合的存储方法。若无向图中有n 个顶点、e 条边，则它的邻接表需n 个头结点和2e 个表结点。显然，在边稀疏的情况下，用邻接表表示图比邻接矩阵存储空间。在无向图的邻接表中，顶点i v 的度恰好是第i 个链表中的结点数，而在有向图中，第i 个链表中结点个数是顶点i v 的出度。 在建立邻接表或邻逆接表时，若输入的顶点信息即为顶点的编号，则建立临接表的时间复杂度是)(e n O +；否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为)*(e n O 。在邻接表上容易找到任意一顶点的第一个邻接点和下一个邻接点，但要判断任意两个顶点之间是否有边或弧，则需要搜索第i 个或第j 个链表，因此，不及邻接矩阵方便。 邻接矩阵和邻接表相互转换程序代码如下： #include #define MAX 20 //图的邻接表存储表示 typedef struct ArcNode{ int adjvex; //弧的邻接定点 char info; //邻接点值 struct ArcNode *nextarc; //指向下一条弧的指针 }ArcNode; typedef struct Vnode{ //节点信息 char data; ArcNode *link; }Vnode,AdjList[MAX]; typedef struct{ AdjList vertices; int vexnum; //节点数 int arcnum; //边数

数据结构课程设计-图的邻接矩阵

数据结构 课程设计报告 设计题目：图的邻接矩阵存储结构 院系计算机学院 年级x 级 学生xxxx 学号xxxxxxxxxx 指导教师xxxxxxxxx 起止时间10-6/10-10 2013年10月10日

目录 1 需求分析 (4) 2 概要设计 (4) 2.1 ADT描述 (4) 2.2程序模块结构 (5) 2.3各功能模块 (6) 3详细设计 (7) 3.1类的定义 (7) 3.2 初始化 (8) 3.3 图的构建操作 (8) 3.4 输出操作 (9) 3.5 get操作 (9) 3.6 插入操作 (10) 3.7 删除操作 (100) 3.8 求顶点的度操作 (111) 3.9 深度遍历作 (11) 3.10 判断连通操作 (12) 3.11 主函数 (13) 4 调试分析 (16) 4.1调试问题 (16) 4.2 算法时间复杂度 (16) 5用户手册 (16) 5.1主界面 (16) 5.2 创建图 (17) 5.3插入节点 (17) 5.4 深度优先遍历 (17) 5.5 求各顶点的度 (18) 5.6 输出图 (18) 5.7 判断是否连通 (19) 5.8 求边的权值 (19) 5.9 插入边 (19) 5.10 删除边 (20) 结论 (20) 参考文献 (20)

摘要 随着计算机的普及，涉及计算机相关的科目也越来越普遍，其中数据结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算机科学技术的发展和应用，学好数据结构非常必要，然而要掌握数据结构的知识非常难，所以对“数据结构”的课程设计比不可少。本说明书是对“无向图的邻接矩阵存储结构”课程设计的说明。 首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。 关键词：网络化；计算机；对策；图；储存。

envi图像处理基本操作

使用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文件。

实验十三 图的基本操作—邻接表存储结构

浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验十三图的基本操作—邻接表存储结构 学生姓名专业班级学号 实验成绩指导老师（签名）日期2015-1-15 一.实验目的和要求 1、掌握图的存储结构：邻接表。 2、学会对图的存储结构进行基本操作。 二.实验内容 1、图的邻接表的定义及实现：建立头文件AdjLink.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数文件test5_2.cpp中调用这些函数进行验证。 2、选做：编写图的深度优先遍历函数与广度优先遍历函数，要求把这两个函数添加到头文件AdjLink.h中，并在主函数文件test5_2.cpp中添加相应语句进行测试。 3、填写实验报告，实验报告文件取名为report13.doc。 4、上传实验报告文件report13.doc及源程序文件test5_2.cpp、AdjLink.h到Ftp服务器上自己的文件夹下。 三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路） 邻接表表示法的C语言描述： typedef struct Node { int adjvex; // 邻接点的位置 WeightType weight; //权值域，根据需要设立 struct Node *next; // 指向下一条边（弧） } edgenode; // 边结点 typedef edgenode *adjlist[ MaxVertexNum ];//定义图的邻接表结构类型（没包含顶点信息） typedef struct{ vexlist vexs; //顶点数据元素

数据结构与算法-图的邻接矩阵

实验报告实验日期：数据结构与算法课程： 图的邻接矩阵实验名称： 一、实验目的掌握图的邻接矩阵 二、实验内容必做部分 、给出图的邻接矩阵存储结构的类型定义。1 -1。v，返回其在vexs数组中的下标，否则返回2、实现LocateVex(G,v)操作函数：若找到顶点。、实现算法7.2（构造无向网）3&G) Status CreateUDN(MGraph 设计并实现无向网的输出算法，要求能显示顶点以及顶点之间的邻接关系（方式自定）4、 并进行输出。要求给出至少两组测试数据。在主函数中调用CreateUDN创建一个无向网，5、 选做部分 类型）编写下述操作函数：基于图的邻接矩阵存储结构（即MGraph若找不到这样返回该邻接点在顶点数组中的下标；1个邻接点，1、求下标为v的顶点的第-1。的邻接点，返回int FirstAdjVex(MGraph G,int v) 的顶点的下一个邻接点，返回该邻接点的下标；若w求下标为v的顶点相对于下标为2、找不到这样的邻接点，返回-1。 int NextAdjVex(MGraph G,int v,int w) 在主函数调用上述函数，给出测试结果。 三、实验步骤 必做部分 给出图的邻接矩阵存储结构的类型定义。、 1．

2、实现LocateVex(G,v)操作函数：若找到顶点v，返回其在vexs数组中的下标，否则返回-1。 3、实现算法7.2（构造无向网）。 &G) CreateUDN(MGraph Status

设计并实现无向网的输出算法，要求能显示顶点以及顶点之间的邻接关系（方式自定）、

4． 要求给出至少两组测试数据。并进行输出。、在主函数中调用CreateUDN创建一个无向网，5

Photoshop基本操作介绍(图文介绍)

第一课：工具的使用 一、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 】后再框选，则选区以鼠标点为中心

实现图的邻接矩阵和邻接表存储

实现图的邻接矩阵和邻接表存储 1．需求分析 对于下图所示的有向图G，编写一个程序完成如下功能： 1．建立G的邻接矩阵并输出之 2．由G的邻接矩阵产生邻接表并输出之 3．再由2的邻接表产生对应的邻接矩阵并输出之 2．系统设计 1．图的抽象数据类型定义： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集 数据关系R： R={VR} VR={|v,w∈V且P(v,w),表示从v到w的弧， 谓词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中增添弧，若G是无向的则还增添对称弧 …… DFSTraverse(G,Visit()) 初始条件：图G存在，Visit是顶点的应用函数 操作结果：对图进行深度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅一次。

一旦Visit()失败，则操作失败 BFSTraverse(G,Visit()) 初始条件：图G存在，Visit是顶点的应用函数 操作结果：对图进行广度优先遍历，在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit()失败，则操作失败 }ADT Graph 2．主程序的流程： 调用CreateMG函数创建邻接矩阵M； 调用PrintMatrix函数输出邻接矩阵M 调用CreateMGtoDN函数，由邻接矩阵M创建邻接表G 调用PrintDN函数输出邻接表G 调用CreateDNtoMG函数，由邻接表M创建邻接矩阵N 调用PrintMatrix函数输出邻接矩阵N 3．函数关系调用图： 3．调试分析 （1）在MGraph的定义中有枚举类型 typedef enum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网} 赋值语句G.kind(int)=M.kind(GraphKind);是正确的，而反过来M.kind=G.kind则是错误的，要加上那个强制转换M.kind=GraphKind(G.kind);枚举类型enum{DG,DN,UDG,UDN} 会自动赋值DG=0；DN=1，UDG=2，UDN=3；可以自动从GraphKind类型转换到int型，但不会自动从int型转换到GraphKind类型

用邻接矩阵表示法创建有向图(数据结构)

#include #include #include #define MAX_VERTEX_NUM 20 //定义最多顶点个数 #define INFINITY32768 //定义无穷大 //描述图的类型，用枚举型类型来说明 typedef enum{DG,DN,UDG,UDN}GraphKind; //定义顶点数据类型 typedef char V ertexData; //定义邻接矩阵中元素值(即边信息）的数据类型 typedef int ArcNode; //定义图的邻接矩阵类型：一个顶点信息的一维数组，一个邻接矩阵、当前图中包含的顶点数、边数以及图类型（有向图、有向网、无向图、无向网） typedef struct { V ertexData vertex[MAX_VERTEX_NUM]; ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vertexnum,arcnum; GraphKind kind; } AdjMatrix;//图的邻接矩阵表示类型 int LocateV ertex(AdjMatrix *G,V ertexData v) //求顶点位置函数 { int j=-1,k; for(k=0;kvertexnum;k++) { if(G->vertex[k]==v) { return k; } } return j; } int CreateDN(AdjMatrix *G) //创建一个又向网 { int i,j,k,weight; V ertexData v1,v2; printf("输入图的顶点数和弧数，以逗号分隔\n"); //输入图的顶点数和弧数 scanf("%d,%d",&G->vertexnum,&G->arcnum); for(i=0;ivertexnum;i++) //初始化邻接矩阵（主对角线元素全为零，其余元素为无穷大） {

邻接表表示的带权有向图(网)

===实习报告一“邻接表表示的带权有向图（网）”演示程序=== （一）、程序的功能和特点 1. 程序功能：建立有向图的带权邻接表，能够对建立的邻接表进行添加顶点，添加边和删除顶点，删除边的操作，并能显示输出邻接表。 2. 程序特点：采用java面向对象语言，对边，顶点和邻接表用类进行封装。采用链式存储结构。 （二八程序的算法设计 算法一：“插入一个顶点”算法： 1. 【逻辑结构与存储结构设计】 逻辑结构：线性结构。存储结构：顺序存储与链式存储结合。 邻接表（Adjacency List）是图的一种顺序存储与链式存储结合的存储方法。。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有点的邻接表表头放到数组中，就构成了图的邻接表。如下图就是一个临界表的存储图。 vertex firstedge adjvex n ext 序号vertex firstedge 图的邻接表表示在邻接表表示中有两种结点 结构，如图所示。 邻接矩阵表示的结点结构

顶点域边指针 流程示意图：顶点数据组成的数组 顶点数组表的顺序存储: V0 V1— V2— O 2.【基本操作设计】 文字说明： （1） .首先判断顶点表是否满。 （2） .若满则插入失败，放回false 。 （3） .顶点表若不满，创建新顶点，将新顶点加入顶点表 （4） .插入顶点成功，返回true 。

添加顶点前状态 添加顶点v2后 网图的边表结构 //插入一个顶点 public boolea n In sertVertex ( char vertex ){ if (NumVertices ==MaxVertices ) return false ; // 顶点表满 Vertex t= n ewVertex(); t. data =vertex; t. adj =null ; NodeTable[ NumVertices ]=t; NumVertices++; //注明：企图以下赋值不合Java 语法 〃NodeTable[NumVertices].data=vertex; 〃NodeTable[NumVertices].adj=null; return true ; } 算法二：“插入一条边”算法： 1. 【逻辑结构与存储结构设计】 逻辑结构：线性结构。 存储结构：链式存储结构 网图的边表结构如图所示。 邻接点域 4.【高级语言代码】

图的基本操作(邻接表)

标头.h #include #include #include #include #define TRUE 1 #define FLASE 0 #define OK 1 #define ERROR 0 #define FALSE 0 #define INFINITY INT_MAX//无穷大 typedef int status; #define MAX_VERTEX_NUM 20 #define MAX_NAME 5 #define MAX_INFO 20 typedef int VRType; typedef int InfoType; typedef char VertexType[MAX_NAME]; enum GraphKind{DG,DN,AG,AN};// 有向图，有向网，无向图，无向图 struct ArcNode { int adjvex; //该弧所指向的顶点的位置 ArcNode *nextarc;//指向吓下一条弧的指针 InfoType *info;//网的权值指针 };//表结点 typedef struct { VertexType data;//顶点信息 ArcNode *firstarc;//第一个表结点的地址，指向第一条依附该顶点的弧的指针 }VNode,AdjList[MAX_VERTEX_NUM]; //头结点 struct ALGraph { AdjList vertices; int vexnum,arcnum;//图的当前顶点数和弧数 int kind; //图的种类标志 }; int LocateVex(ALGraph G,VertexType u) {//初始条件：图G存在，u和G中顶点有相同的特征

图的邻接表存储结构实验报告

《图的邻接表存储结构实验报告》1.需解决的的问题 利用邻接表存储结果，设计一种图。 2.数据结构的定义 typedef struct node {//边表结点 int adj;//边表结点数据域 struct node *next; }node; typedef struct vnode {//顶点表结点 char name[20]; node *fnext; }vnode,AList[M]; typedef struct{ AList List;//邻接表 int v,e;//顶点树和边数 }*Graph; 3.程序的结构图

4.函数的功能 1）建立无向邻接表 Graph Create1( )//建立无向邻接表{ Graph G; int i,j,k;

node *s; G=malloc(M*sizeof(vnode)); printf("输入图的顶点数和边数："); scanf("%d%d",&G->v,&G->e);//读入顶点数和边数for(i=0;iv;i++)//建立顶点表 { printf("请输入图第%d个元素:",i+1); scanf("%s",&G->List[i].name);//读入顶点信息 G->List[i].fnext=NULL;//边表置为空表 } for(k=0;ke;k++)//建立边表--建立了2倍边的结点{ printf("请输入边的两顶点序号：（从0考试）"); scanf("%d%d",&i,&j);//读入边（Vi,Vj）的顶点对序号 s=(node *)malloc(sizeof(node));//生成边表结点 s->adj=j; s->next=G->List[i].fnext; G->List[i].fnext=s;//将新结点*s插入顶点Vi的边表头部s=(node *)malloc(sizeof(node)); s->adj=i;//邻接点序号为i s->next=G->List[j].fnext; G->List[j].fnext=s;// 将新结点*s插入顶点Vj的边表头部} return G;

邻接矩阵创建有向网的实现

韩山师范学院 实验题目： 邻接矩阵创建有向网算法实现 班级：2015级软工班作者：黄俊聪 #include using namespace std; #define MaxInt 32767 //表示极大值，即∞ #define MVNum 100 //最大顶点数 #define OK 1 #define ERROR 0; typedef char VerTexType;//假设顶点的数据类型为字符型 typedefintArcType;//假设边的权值类型为整型 typedefint Status; typedefstruct { VerTexTypevexs[MVNum];//顶点表 ArcType arcs[MVNum][MVNum];//邻接矩阵 intvexnum,arcnum;//图的当前点数和边数 }AMGraph; Status LocateVex(AMGraphG,char v) {

for(i=0; i>G.vexnum>>G.arcnum;//输入总定点数，总边数 cout<<"次输入点的信息："<>G.vexs[i]; for(int i=0;i>v1>>v2>>w;//输入一条边依附的顶点及权值 i=LocateVex(G,v1); j=LocateVex(G,v2);//确定v1和v2在G中的位置，即顶点数组的下表 G.arcs[i][j]=w;//边的权值置为w } return OK; } void PrintMatrix(AMGraph&G)//输出邻接矩阵 { inti,j; printf("邻接矩阵为:\n"); for(i=0;i

Photoshop基本操作介绍(图文介绍)

第一课：工具的使用 、 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 】后再框选，则框选出正圆或正方形。

图的邻接表存储方式.

图的邻接表存储方式——数组实现初探 焦作市外国语中学岳卫华在图论中，图的存储结构最常用的就是就是邻接表和邻接矩阵。一旦顶点的个数超过5000，邻接矩阵就会“爆掉”空间，那么就只能用邻接表来存储。比如noip09的第三题，如果想过掉全部数据，就必须用邻接表来存储。 但是，在平时的教学中，发现用动态的链表来实现邻接表实现时，跟踪调试很困难，一些学生于是就觉得邻接表的存储方式很困难。经过查找资料，发现，其实完全可以用静态的数组来实现邻接表。本文就是对这种方式进行探讨。 我们知道，邻接表是用一个一维数组来存储顶点，并由顶点来扩展和其相邻的边。具体表示如下图：

其相应的类型定义如下： type point=^node; node=record v:integer; //另一个顶点 next:point; //下一条边 end; var a:array[1..maxv]of point; 而用数组实现邻接表，则需要定义两个数组：一个是顶点数组，一个 是边集数组。

顶点编号结点相临边的总数s第一条邻接边next 此边的另一邻接点边权值下一个邻接边 对于上图来说，具体的邻接表就是： 由上图我们可以知道，和编号为1的顶点相邻的有3条边，第一条边在边集数组里的编号是5，而和编号为5同一个顶点的下条边的编号为3，再往下的边的编号是1，那么和顶点1相邻的3条边的编号分别就是5，3，1。同理和顶点3相邻的3条边的编号分别是11，8，4。如果理解数组表示邻接表的原理，那么实现就很容易了。 类型定义如下：

见图的代码和动态邻接表类似： 下面提供一道例题 邀请卡分发deliver.pas/c/cpp 【题目描述】

经典代码之图 邻接表转换成邻接矩阵

运行结果是： 请输入节点数和弧数:3 3 第1 个节点信息:5 第2 个节点信息:6 第3 个节点信息:7 第1 条弧的弧尾和弧头的位置:1 2 第2 条弧的弧尾和弧头的位置:2 3 第3 条弧的弧尾和弧头的位置:1 3 图的邻接表表示为： [1,5]-->[3,7]-->[2,6]-->^ [2,6]-->[3,7]-->[1,5]-->^ [3,7]-->[1,5]-->[2,6]-->^ 交换后是:: 图的邻接矩阵表示为： 0 1 1 1 0 1 1 1 0 请按任意键继续. . . 代码是： #include #include #define MAXV 100 typedef struct { int no; int info; }vertextype; typedef struct { int num; int edges[MAXV][MAXV]; // vertextype vexs[MAXV]; }mgraph; struct arcnode { int adjvex; int info;

struct arcnode *nextarc; }; struct vexnode { int data; struct arcnode *firstarc; }; struct graph { int vexnum,arcnum; vexnode vexpex[100]; }; struct graph *creatgraph() { int i,s,d; struct graph *g; struct arcnode *p,*q; g = (struct graph *)malloc(sizeof(struct graph)); printf("请输入节点数和弧数:"); scanf("%d%d", &g->vexnum, &g->arcnum); for(i=1; i<=g->vexnum; i++) { printf("第%d 个节点信息:",i); scanf("%d", &g->vexpex[i].data); g->vexpex[i].firstarc = NULL; } for(i=1; i<=g->arcnum; i++) { p = (struct arcnode *)malloc(sizeof(struct arcnode)); q = (struct arcnode *)malloc(sizeof(struct arcnode)); printf("第%d 条弧的弧尾和弧头的位置:",i); scanf("%d%d",&s,&d); p->adjvex = d; p->info = g->vexpex[d].data; p->nextarc = g->vexpex[s].firstarc; g->vexpex[s].firstarc = p; q->adjvex = s; q->info = g->vexpex[s].data; q->nextarc = g->vexpex[d].firstarc; g->vexpex[d].firstarc = q;