数据结构设计无向图
数据结构课程设计
——无向图
学校
专业班级
姓名
学号
任课教师
题目3：以邻接链表的方式确定一个无向网，完成：
⑴建立并显示出它的邻接矩阵；
⑵对该图进行广度优先遍历，显示遍历的结果，（并随时显示队列的入、出情况）；
⑶普里姆算法构造其最小生成树，随时显示其构造的过程；
⑷用克鲁斯卡尔算法构造其最小生成树，随时显示其构造的过程。
一、需求分析
1.运行环境：
Microsoft Visual Studio 2012
2.程序所实现的功能：
a)建立并显示图的邻接矩阵；
b)广度优先遍历该图，显示遍历结果；
c)用普里姆算法构造该图的最小生成树，显示构造过程；
d)用克鲁斯卡尔算法构造该图的最小生成树，显示构造过程。
3.程序的输入，包含输入的数据格式和说明：
a)输入顶点数，及各顶点信息(数据格式为整形)；
b)输入弧以及其权值(数据格式为整形)。
1.程序的输出，程序输出的形式：
a)输出图的邻接矩阵；
b)广度优先遍历结果；
c)普里姆算法构造最小生成树的结果；
d)克鲁斯卡尔算法构造最小生成树的结果。
2.测试数据，如果输入的数据量较大，需要给出测试数据：
a)顶点个数：5
b)各个顶点为：A B C D E
c)输入所有的弧（格式为“顶点顶点权值”）为：
A B 10 A C 4 B D 3 C D 5 B E 6 D E 9
二、设计说明
算法设计的思想：
建立图类，建立相关成员函数。最后在主函数中实现。具体成员函数的实现请参看源程序。在本次的设计中，我采用的是多文件的编程方式。每个类写成了一个头文件。这样有助于阅读和查看源程序。
1.邻接链表:
邻接链表是一种链式存储结构。在邻接链表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。每个结点由3个域组成，其中邻接点域指示与顶点Vi邻接的点在图中的位置，链域指示下一条边或弧的结点；数据域存储和边或弧相关的信息，如权值等。
所以一开始必须先定义邻接链表的边结点类型以及邻接链表类型，并对邻接链表进行初始化，然后根据所输入的相关信息，包括图的顶点数、边数、是否为有向，以及各条边的起点与终点序号，建立图的邻接链表。
2.邻接矩阵:
图的邻接矩阵存储表示即是数组存储表示，在邻接矩阵中，我们定义两个数组分别存储数据元素的信息和数据元素之间的关系（边或弧）的信息，以二维数组表示有n个顶点的图时，需存放n个顶点信息和n的平方个弧信息的存储量。借助于邻接矩阵容易判定任意两个顶点之间是否有边或弧相连，并容易求得各个顶点的度。故在建立邻接矩阵之前，必须先定义顶点关系类型和相关指针指示弧的信息。3.广度优先遍历:
假设从图总某顶点出发，在访问了v之后依次访问v的各个未曾访问到的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的邻接点”先于“后被访问的邻接点”被访问，直至图中所有已被访问的邻接点都被访问到。若此时图中尚有顶点未被访问到，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以v为起始点，由近及远，依次访问饿v有路径相通且路径长度为1,2….的顶点。和深度优先搜索类似，在遍历过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2,3…的顶点，需附设队列以存储已被访问的路径长度为1,2….的顶点。
所以要实现算法必须先建立一个元素类型为整形的空队列，并定义队首与队尾指针，同时也要定义一个标志数组以标记结点是否被访问。同样，也是从初始点出发开始访问，访问初始点，标志其已被访问，并将其入队。当队列非空时进行循环处理。当结点被访问时对其
进行标志，并入队列。通过while（）循环，并以是否被访问为控制条件，访问所有结点，完成图的广度优先遍历。
4.普里姆算法:
假设N=(V,{E})是连通网，TE是N上最小生成数中边的集合。算法从U={U0}，TE={}开始，重复执行如下操作；在所有的边（u,v）中找一条代价最小的边（u0,v0）并入集合TE,同时V0并入U,直到U=V为止。此时TE中必有n-1条边，则，T=(V,{TE})为N 的最小生成树。
5.克鲁斯卡尔算法:
假设连通网N=(V,{E}),则令最小生成树的初始状态为只有n个顶点且无边的非连通图T=(V,{}),图中每个顶点自成一个连通分量。在E 中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直到T中的所有顶点都在同一个连通分量上为止。
主要的数据结构设计说明：
图的邻接矩阵、邻接表的建立。图的广度优先遍历以及分别用普里姆算法和克鲁斯卡尔算法构造最小生成树。
程序的主要流程图：
程序的主要模块，要求对主要流程图中出现的模块进行说明：用邻接链表的方式确定一个无向图，以邻接矩阵的方式输出，再进行图的广度优先遍历以及分别用普里姆算法和克鲁斯卡尔算法构造最小生成树并输出。
程序的主要函数说明：
intlocatepoint( string );定位节点位置
voidBreadth_traversal();广度优先遍历
voidprintgragh();邻接矩阵的输出
void prim();普里姆算法
void ktus();克鲁斯卡尔算法
三、上机结果及体会
1.上机过程中出现的问题及其解决方案。
问题：刚开始编译没有错误，但结果有问题。在其中的普里姆算法和克鲁斯卡尔算法的循环过程中，对循环控制变量设置不当，导致程序陷入死循环之中。解决方案：调整改变循环控制变量。
2.程序中可以改进的地方说明
?程序中的广度优先遍历，可以考虑用循环来做，也可以用栈
来实现。
?在本程序中，两个没有联系的顶点之间的权值的无穷大我是
用“0”来表示的。可以考虑用一个特殊字符来实现。
四、实验源程序
*******************************************************************************头文件node_linklist.h
#ifndefNODE_LINKLIST
#defineNODE_LINKLIST
classnode_array;
//邻接链表链结点
classnode_linklist
{
public:
intposition;
intweight;
node_linklist*next;
node_linklist(inta,intb){position=a;weight=b;next=NULL;}
node_linklist(){position=NULL;weight=NULL;next=NULL;}
~node_linklist(){}
};
#endif
*******************************************************************************头文件node_array.h
#ifndefNODE_ARRAY
#defineNODE_ARRAY
//邻接链表数组结点
classnode_array
{
public:
node_linklist*next;
stringdata;
node_array(){data='\0';next=NULL;}
~node_array(){}
};
#endif
*******************************************************************************头文件tu_matrix.h
#ifndefTU_MA TRIX
#defineTU_MATRIX
//图类
classtu_matrix
{
private:
intmatrix[MAX][MAX];
stringtoppoint[MAX];
intnumpoint;
node_arrayvertices[MAX];
public:
tu_matrix(){}
voidcreat();
intlocatepoint(string);//返回这个顶点的位置
voidBreadth_traversal();
voidprintgragh();
voidprim();
voidktus();
};
inttu_matrix::locatepoint(stringb)
{
inti=0;
for(;i { if(toppoint[i]==b)returni; } return-1; } voidtu_matrix::creat() { stringdata,data1,data2; intn,m,num; //输入顶点个数 cout<<"请输入您要创建的无向图的顶点个数："<<'\t'; cin>>numpoint; //输入顶点 cout<<"请依次输入该无向图的各个顶点："< for(inti=0;i { cin>>toppoint[i]; } //以邻接链表确定无向网 node_linklist*(*end)=newnode_linklist*[numpoint];//指向数组链表的最后一个节点指针数组 int*pp=newint[numpoint];//辅助数组，当其中的值不为0时，表示该数组节点后面已经有至少一个链表节点，否则表示没有链表节点 for(inti=0;i pp[i]=0; node_linklist*ppp=NULL; cout<<"输入该无向图所有的弧，格式为:“顶点顶点权值”，输入“0 0 0”结束"< do { cin>>data1>>data2>>num; n=locatepoint(data1); m=locatepoint(data2); if((n!=-1)&&(m!=-1)) { if(!pp[n])//如果该数组节点后面没有链表节点 { ppp=newnode_linklist(m,num); end[n]=vertices[n].next=ppp; pp[n]=1; } else { end[n]->next=newnode_linklist(m,num); end[n]=end[n]->next; } if(!pp[m])//如果该数组节点后面没有链表节点 { ppp=newnode_linklist(n,num); end[m]=vertices[m].next=ppp; pp[m]=1; } else { end[m]->next=newnode_linklist(n,num); end[m]=end[m]->next; } } }while((data1!="0")&&(data2!="0")&&(num!=0)); //根据邻接链表建立邻接矩阵 node_linklist*p; for(inti=0;i for(intj=0;j matrix[i][j]=0; for(inti=0;i { p=vertices[i].next; while(p) { n=p->position; m=p->weight; p=p->next; matrix[i][n]=m; }; } deleteend; } voidtu_matrix::printgragh()//打印无向网的邻接矩阵 { cout<<"该图的邻接矩阵为："<< "\n--------------------------------------------------------------------------------"< inti,j; for(i=0;i { for(j=0;j { cout< } cout< } cout<<"--------------------------------------------------------------------------------"< } voidtu_matrix::Breadth_traversal() { int*flag=newint[numpoint];//记录顶点访问状态 int*queue=newint[numpoint+1];//记录未广度遍历的顶点数 intfront,rear; front=rear=0; inti; cout<<"该图的广度优先遍历为："<< "\n--------------------------------------------------------------------------------"< for(i=0;i flag[i]=0;//状态初始化 do { for(i=0;i if(flag[i]==0) break; if(i!=numpoint) { cout<<"---->\t"< rear=(rear+1)%(numpoint+1); queue[rear]=i; cout<<"入队列\t"< flag[i]=1; do { front=(front+1)%(numpoint+1); cout<<"出队列\t"< for(intj=0;j { if((matrix[queue[front]][j]!=0)&&(flag[j]!=1)) { cout<<"---->\t"< rear=(rear+1)%(numpoint+1); queue[rear]=j; cout<<"入队列\t"< flag[j]=1; } } }while(((rear+1)%(numpoint+1)!=front)&&(rear!=front));//队列结束条件，队列满或空} }while(i!=numpoint); cout<<"--------------------------------------------------------------------------------"< } voidtu_matrix::prim() { intflag[MAX],point[MAX],n,m,x,p=0;//flag[]标志结点所属树,p表示已访问过的结点个数intmatrixone[MAX][MAX];//辅助矩阵 for(inti=0;i for(intj=0;j matrixone[i][j]=matrix[i][j]; for(inti=0;i flag[i]=0;//标志位初始化 cout<<"用普里姆算法构造的最小生成树为："<< "\n--------------------------------------------------------------------------------"< //先找到最小的一个弧 x=m=n=0; for(inti=0;i { for(intj=i;j if(matrixone[i][j]!=0) { x=matrixone[i][j]; break; } if(x!=0) break; }//预先给x一个没有被访问过的，且不是0的权值 for(inti=0;i for(intj=i;j { if((matrixone[i][j]!=0)&&(matrixone[i][j]<=x)) { x=matrixone[i][j]; m=i;n=j; } } p+=2; point[0]=m;point[1]=n; flag[m]=flag[n]=1; cout< while(p { x=m=n=0; for(inti=0;i { 数学与计算机学院 课程设计说明书 课程名称: 数据结构与算法课程设计 课程代码: 6014389 题目: 图的遍历和生成树求解实现 年级/专业/班: 学生姓名: 学号: 开始时间: 2012 年 12 月 09 日 完成时间: 2012 年 12 月 26 日 课程设计成绩： 指导教师签名：年月日 目录 摘要 (3) 引言 (4) 1 需求分析 (5) 1.1任务与分析 (5) 1.2测试数据 (5) 2 概要设计 (5) 2.1 ADT描述 (5) 2.2程序模块结构 (7) 软件结构设计： (7) 2.3各功能模块 (7) 3 详细设计 (8) 3.1结构体定义 (19) 3.2 初始化 (22) 3.3 插入操作（四号黑体） (22) 4 调试分析 (22) 5 用户使用说明 (23) 6 测试结果 (24) 结论 (26) 摘要 《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。 因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。 关键词：计算机；图；算法。 交通标志牌设计说明 设计说明 概述采用的主要技术规范 公路工程技术标准》JTG B01-2003 道路交通标志和标线》GB5768-1999 公路工程基本建设项目设计文件编制办法》 设计要点 ( 一) 交通标志 1. 设计原理 交通标志指应用图形符号和文字符号传递特定信息，对交通进行导向、警规定 和指示，用以管理交通安全的设施。 (1) 标志及牌面信息以《道路交通标志和标线》GB5768-1999为基 础，参考河南省地方标准《公路设计技术要求》DB41/419-2005。 根据实际需要，尽量做到各类标志完善、齐全。 (2) 标志内容应准确、醒目，以便引导司机正确行驶，应避免标志 遗漏或内容模糊等现象。 (3) 标志的结构设计应合理，牌面设计应以庄重、美观为原则。 2. 标志牌面设计 标志牌面设计以司机在公路上60km/h 速度下行驶能及时辨认标志 内容为基本原则。根据《道路交通标志和标线》GB5768-1999的有关规定设置标志牌。标志汉字高度采用30厘米，高宽比为1:1 ，字间 距不小于3 厘米，行距不小于1 0厘米，汉字笔划粗为3 厘米，标志 采用中英文对照，英文字高为汉字高度的一半。 牌面反光材料的选择，既要考虑各类反光膜的反光特性、使用功 能、应用场合和使用年限，又要分清牌面中不同内容部分的主次关系， 这样才能使牌面交通信息在夜间有较好的视认效果; 标志牌面采用 3M工程7年级反光膜。 3. 标志结构设计 根据标志牌面尺寸大小及设置位置的需要，采用悬臂式安装。标志下缘净空 4.5米;标志板采用2mn后铝合金板制作。 4. 标志技术要求 (1) 交通标志的形状、图案、颜色应严格按照《道路交通标志和标线》GB5768- 1999标准或设计图的规定执行。 (2) 交通标志的边框外缘，应有衬底色。衬底色规定为指路、指示标志为蓝色，警告标志为黄色; 禁令标志为红色。标志板与滑动铝槽、卷边加固件连接，在保证连接强度和标志板面平整，不影响贴反光膜的前提下，可采用铆接或点焊。 5. 标志的设置原则 在十字路口和被交道路交叉处设置方向、地点标志，标志上地点名称应是交通流的主要生成源。 6. 施工主要事项 (1)路侧设置的柱式标志，标志板内缘距土路肩边缘距离不小于25cm;悬臂式标志，标志板下缘距路面的净空高度不得小于 4.5m。 (2) 所有标志立柱和横梁都应焊接柱帽和横梁帽，柱帽和横梁帽用钢板冲压成型。 (3) 标志板在运输、吊装过程中应小心，避免对标志板、反光膜产生损坏。 (4) 标志支撑结构(包括: 立柱、横梁、法兰盘)应按照规定进行热镀锌处理。镀 锌量为600g/?. (5) 螺栓、螺母、垫圈采用镀锌处理。如采用热镀锌，必须清理螺方或作离心处理。 (6) 铝合金板、与钢材接触的部位，应采用相应的防锈措施。镀锌层在运输、安装过程中造成损坏，应及时采取补救措施。 数据结构实验报告 实验：图的遍历 一、实验目的： 1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表 2、掌握图的构造方法 3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法 4、掌握图的深度优先遍历和广度优先原理 二、实验内容： 1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。 2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图 3、深度优先遍历第一步中构造的图G，输出得到的节点序列 4、广度优先遍历第一部中构造的图G，输出得到的节点序列 三、实验要求： 1、无向图中的相关信息要从终端以正确的方式输入； 2、具体的输入和输出格式不限； 3、算法要具有较好的健壮性，对错误操作要做适当处理； 4、程序算法作简短的文字注释。 四、程序实现及结果： 1、邻接矩阵： #include #include 悬臂式标志牌结构设计计算书 1 设计资料 1.1 板面数据 板面高度：H = 2.00(m) 板面宽度：W = 8.00(m) 板面单位重量：W1 = 13.26(kg/m^2) 1.2 横梁数据 边长:0.18(m) 横梁长度：L = 7.8(m) 横梁壁厚：T = 0.008(m) 横梁间距：D1 = 1.0(m) 横梁单位重量：W1 = 45.22(kg/m) 1.3 立柱数据 边长: 0.35(m) 立柱高度：L = 7.40(m) 立柱壁厚：T = 0.014(m) 立柱单位重量：W1 = 153.86(kg/m) 2 荷载计算 2.1 永久荷载 各计算式中系数1.1系考虑有关连接件及加劲肋等的重量而添加。2.1.1 板面重量计算 标志版单位重量为13.26(kg/m2) 标志版重量： G1 = 13.26×16×9.8×1.1(N) = 2.2871(KN) 2.1.2 横梁重量计算 G2 = 2×45.22×7.8×9.8×1.1(N) = 7.6046(KN) 2.1.3 立柱重量计算 G3 = 153.86×7.8×9.8×1.1(N) = 12.9372(KN) 2.1.4 计算上部总重量 G = G1 + G2 + G3 = 22.8289(KN) 3 风荷载计算 3.1 标志版风力 F1 = βz×μs×μz×ω0×(W ×H) = 12.944(KN) 3.2 立柱风力 F2 =βz×μs×μz×ω0×(W ×H) = 2.096(KN) 4 横梁设计计算 说明：由于单根横梁材料、规格相同，根据基本假设，可认为每根横梁所受的荷载为总荷载的一半。 对单根横梁所受荷载计算如下： 4.1 荷载计算 竖直荷载G4 = γ0×γG×G1 / 2 = 1.372(KN) 均布荷载ω1 = γ0×γG×G2 / (2 ×H) = 0.585(KN/m) 水平荷载F wb = F1 / 2 =6.472(KN) 4.2 强度验算 计算横梁跟部由重力引起的剪力 Q y1 = G4+ ω1 ×H = 5.935(KN) 计算由重力引起的弯矩 M y1 = G4×(l2 + l3) + ω1 ×l12 / 2 = 45.393(KN*m) 计算横梁跟部由风力引起的剪力 Q x1 = F1 = 6.472(KN) 计算由风力引起的弯矩 M x1 = F1×(l2 + l3) = 30.0948(KN*m) 4.3 横梁截面信息 横梁截面积 A = 5.504 ×10-3 (m2) 横梁截面惯性矩I = 2.72 ×10-5 (m4) 第七章图：习题 习题 一、选择题 1．设完全无向图的顶点个数为n，则该图有( )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 2016.1.7 实验名称： 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 V0 V1 V2 V3 V4 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 数据结构C语言版无向图的邻接多重表存储表示和实现.txt只要你要，只要我有，你还外边转什么阿老实在我身边待着就行了。听我的就是,问那么多干嘛，我在你身边,你还走错路!跟着我!不能给你幸福是我的错，但谁让你不幸福，我TMD去砍了他/* 数据结构C语言版无向图的邻接多重表存储表示和实现 P166 编译环境：Dev-C++ 4.9.9.2 日期：2011年2月15日 */ #include 交通标识技术要求-标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII 施工组织设计 第一章总体施工组织布置及规划 若我公司中标，即按照本投标文件中的承诺，派遣强有力的领导班子，组建项目经理部。并由项目经理率领由各部门负责人、施工队负责人及部分劳动力组成的先遣队，迅速完成承包人驻地建设及施工临时设施布设，尽早全面展开施工。项目经理部挂牌办公，代表公司全面履行合同。一、项目管理机构 根据本项目具体情况，结合我司施工经验，项目经理部设项目经理、技术负责人，下按“四部一室”(工程技术部、质安部、物资设备部、计财部、综合办公室)的编制设置。实行项目经理负责制，并按项目法实行统一组织、统一管理、统一协调，做到精心组织、科学管理、合理安排，确保本工程安全、质量、工期、环保及文明施工等各项目标的实现。 二、施工临建 1、驻地建设 合同段项目经理部及施工队营地设置在建设单位提供的场所，或租用民房并完善办公、生产生活设施，施工营地内设标志标牌加工制作棚和仓库。详见临建设施集中布置图。 2、施工用水 本工程所在区域水系较发达，施工驻地内生产、生活用水分开设蓄水池，自附近居民用水点接入，施工现场用水采用水车供应。 3、施工用电 用电与地方电力部门协商接入，并自备30kw发电机组确保施工用电连续性，施工现场用电采用自发电。 4、通讯联络 当地通信条件较完善，所有人员配备移动电话，项目经理部配备固定电话一部，传真机一部，电脑1台并接入因特网。三、施工任务划分及机械设备、劳动力配置 根据本合同段具体工程量及工期要求，拟设1个标志标牌专业施工队及1个交通安全维护巡查组，分别承担本合同段的施工任务及交通安全畅通维护。因施工工期紧，作业面广，应投入劳动力及设备多开工作面同步施工。 标识标牌施工队：配备氧割设备、切割机、吊车、砼拌合设备、自卸汽车及其他小型机具等，劳动力26人，负责全线标志板、倒水尺安装等施工。 交通安全维护巡查组：配置交通车1台，人员2人，负责本合同段施工区的交通安全畅通维护工作。 四、设备、人员动员周期和设备、人员、材料运到施工现场的方法 1、施工准备组织及工期计划安排 本工程工期100天，我方拟定施工准备期为3天，根据招标文件要求，暂预定2011年9月3日开工(具体按业主要求执行)，2011年12月10日前完成全部施工。 2、劳动力进场计划及到场方法 ⑴第一批：接到中标通知书后2天内，施工先遣队在项目经理部组织及施工队长的带领下进场，进行施工准备及临时驻地建设。 ⑵第二批：签订合同后2天内，施工队劳动力全部进场，并全面展开施工。 3、机械设备动员周期及运到现场的方法 投标“资审文件”所列的施工机械设备及仪器，公司均已准备到位，开工前可全部提前进场，施工机械设备采用动态管理，满足服务周期和监理工程师、业主的要求。 4、材料运到现场的方法 经现场调查，初步拟订材料来源和运输方法如下： /* *题目：编写按键盘输入的数据建立图的邻接矩阵存储 * 编写图的深度优先遍历程序 * 编写图的广度优先遍历程序 * 设计一个选择式菜单形式如下： * 图子系统 * *********************************** * * 1------更新邻接矩阵* * * 2------深度优先遍历* * * 3------广度优先遍历* * * 0------ 返回* * *********************************** * 请选择菜单号（0--3）： */ #include #include"stdlib.h" #include"stdio.h" #include"malloc.h" #define INFINITY 32767 #define MAX_VERTEX_NUM 20 typedef enum{FALSE,TRUE}visited_hc; typedef enum{DG,DN,UDG,UDN}graphkind_hc; typedef struct arccell_hc {int adj; int*info; }arccell_hc,adjmatrix_hc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {char vexs[MAX_VERTEX_NUM]; adjmatrix_hc arcs; int vexnum,arcnum; graphkind_hc kind; }mgraph_hc; typedef struct arcnode_hc {int adjvex; struct arcnode_hc *nextarc; int*info; }arcnode_hc; typedef struct vnode_hc {char data; arcnode_hc *firstarc; }vnode_hc,adjlist_hc[MAX_VERTEX_NUM]; typedef struct {adjlist_hc vertices; int vexnum,arcnum; graphkind_hc kind; }algraph_hc; int locatevex_hc(mgraph_hc*g,char v) {int i,k=0; for(i=0;i ##大学 数据结构课程设计报告题目：图的遍历和生成树求解 院（系）：计算机工程学院 学生: 班级：学号: 起迄日期: 2011.6.20 指导教师: 2010—2011年度第 2 学期 一、需求分析 1.问题描述： 图的遍历和生成树求解实现 图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。 生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。 2.基本功能 1) 先任意创建一个图； 2) 图的DFS,BFS的递归和非递归算法的实现 3) 最小生成树（两个算法）的实现，求连通分量的实现 4) 要求用邻接矩阵、邻接表等多种结构存储实现 3.输入输出 输入数据类型为整型和字符型，输出为整型和字符 二、概要设计 1.设计思路： a.图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中元素全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用1表示，无边用0表示；有全图的边为权值表示，无边用∞表示。 b.图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。 c.图的广度优先遍历：假设从图中的某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的重复以上步骤，是一个非递归过程。 d.图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的过程。 e.图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。 2.数据结构设计： ADT Queue{ 数据对象：D={a i | a i ∈ElemSet,i=1,2,3……，n,n≥0} 数据关系：R1={| a i-1 ,a i ∈D,i=1,2,3,……，n} 基本操作： InitQueue(&Q) 操作结果：构造一个空队列Q。 QueueEmpty(Q) 初始条件：Q为非空队列。 操作结果：若Q为空队列，则返回真，否则为假。 EnQueue(&Q,e) 初始条件：Q为非空队列。 操作结果：插入元素e为Q的新的队尾元素。 DeQueue(&Q,e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。}ADT Queue 悬臂式标志牌结构设计计算 书 1设计资料 1.1板面数据 板面高度：H = 2.00(m) 板面宽度：W = 8.00(m) 板面单位重量：W1 = 13.26(kg/m^2) 边长:0.18(m) 横梁长度：L = 7.8(m) 横梁壁厚：T = 0.008(m) 横梁间距：D1 = 1.0(m) 横梁单位重量：W1 = 45.22(kg/m) 1.3立柱数据 边长: 0.35(m) 立柱高度：L = 7.40(m) 立柱壁厚：T = 0.014(m) 立柱单位重量：W1 = 153.86(kg/m) 2荷载计算 2.1永久荷载 各计算式中系数 1.1 系考虑有关连接件及加劲肋等的重量而 添加。 2.1.1板面重量计算 标志版单位重量为13.26(kg/m 2) 标志版重量： G1 = 13.26× 16× 9.8× 1.1(N) = 2.2871(KN) 2.1.2横梁重量计算 G2 = 2× 45.22× 7.8× 9.8× 1.1(N) = 7.6046(KN) 2.1.3立柱重量计算 G3 = 153.86× 7.8× 9.8× 1.1(N) = 12.9372(KN) G = G1 + G2 + G3 = 22.8289(KN) 3风荷载计算 3.1标志版风力 F1 = βz × μs × μz ×ω 0× (W × H) = 12.944(KN) 3.2立柱风力 F2 = βz × μs × μz ×ω 0× (W × H) = 2.096(KN) 4横梁设计计算 说明：由于单根横梁材料、规格相同，根据基本假设，可认为每根横梁所受 的荷载为总荷载的一半。 对单根横梁所受荷载计算如下： 4.1荷载计算 竖直荷载G4 = γ 0 × γ G × G1 / 2 = 1.372(KN) 均布荷载ω1 = γ 0 × γ G × G2 / (2 × H) = 0.585(KN/m) 水平荷载F wb = F1 / 2 =6.472(KN) 4.2强度验算 计算横梁跟部由重力引起的剪力 Q y1 = G4 + ω1 × H = 5.935(KN) 计算由重力引起的弯矩 实验四图的存储、遍历与应用姓名：班级： 学号：日期：一、实验目的： 二、实验内容： 三、基本思想，原理和算法描述: 四、源程序： （1）邻接矩阵的存储： #include 《数据结构》实验报告 1 2 实验题目：第四次实验《无向图的应用》 3 姓名：刘创学号：132054137 班级：1320541 4 系名：计算机工程系专业：计算机科学与技术5 指导老师：刘海静 6 实验时间：2015年6月18日星期四实验地点：软件实验室 【实验概述】 1.实验目的及要求 目的：掌握图的有关知识 要求：用图的邻接表存储无向图； 实现图的遍历等操作 2.实验原理 图的遍历 图的存储 3.实验环境（使用的软件） VC++6.0/VS2013 【实验内容】 1.实验算法设计 实验：存储图使用图的邻接表进行存储； 用深度优先排序进行遍历图 2.实验过程（源代码及描述、调试过程及分析） 调试过程中，两个实验没有出现太大的问题，理论联系实际，多时间去实践方可等心应手。 实验代码: GraphTraverse.cpp #include #define MaxVertexNum 40 //最大顶点数 using namespace std; typedef struct node //表结点 { int adjvertex; //邻接点域 InfoType info; //与边相关信息（权值） struct node *next; //指向下一个领节点的指针域 }EdgeNode; typedef struct vnode { VertexType vertex; //顶点域信息 EdgeNode *firstedge; //边表头指针 }VertexNode; typedef struct { VertexNode adjlist[MaxVertexNum];//邻接表 int vertexNum, edgeNum;//顶点数和边数 }ALGraph; //以邻接表存储的图 int visited[MaxVertexNum]; int e; void CreatAdjList(ALGraph* G) //创建无向图（邻接表） { int i, j, k; EdgeNode * p1; //因为是无向图，所以有两次建立边表的过程EdgeNode * p2; EdgeNode * p3; EdgeNode * p4; cout << "请输入无向图的顶点数和边数:"; 悬臂式标志的结构设计计算 1.计算简图如下图所示 2.荷载计算 (1) 永久荷载 各计算式中系数1.1系考虑有关连接件及加劲肋等的重力而添加的。 标志板单位面积质量为8.037kg/m 2,其重力为： G 1=4.4?2.4?8.037?9.8?1.1=0.9149(kN) 横梁拟采用0.62032?Φ钢管，单位面积质量为29.15kg/m 2,其总重力为: G 2=2?29.15?5.076?9.8?1.1=3.1901(kN) 立柱拟采用0.9377?Φ钢管，单位面积质量为81.68kg/m 2,其总重为: G 3=81.68?7.9?9.8?1.1=6.956(kN) 标志上部结构的总重力为: G=G 1+G 2+G 3=0.9149+3.1901+6.956=11.061(kN) 有关系数将视永久荷载效应对结构构件或连接的承重能力是否有利而选取。 (2)风荷载 标志板： 211101 ()()/1000 2 1.0 1.4[(0.5 1.2258 1.240^2)(4.4 2.4)]/100017.397()wb Q b h F CV W W KN γγρ=?=???????= 横梁： 2101 ()()/1000 211.0 1.4( 1.22580.840^2)(0.6760.2032)/100020.301() Q WH B hni F CV W H KN γγρ=??? =???????????? =∑ 立柱： 21101 [()()/1000 2 1.0 1.4[(0.5 1.22580.840^2)(7.90.377)]/10003.271()WP Q p P F CV W H KN γγρ=?=???????= 3．横梁的设计计算 由于两根横梁材料，规格相同，根据基本假设，可认为每根横梁所受的荷载为总荷载之半，其受力如图6.2。 图6.2 横梁受力图（尺寸单位：mm ） 单根横梁所承受荷载为： 实践四：图及图的应用 1.实验目的要求 理解图的基本概念，两种主要的存储结构。掌握在邻接链表存储结构下的图的深度优先递归遍历、广度优先遍历。通过选做题"最短路径问题"认识图及其算法具有广泛的应用意义。 实验要求：正确调试程序。写出实验报告。 2.实验主要内容 2.1 在邻接矩阵存储结构下的图的深度优先递归遍历、广度优先遍历。 2.1.1 要完成图的两种遍历算法，首先需要进行图的数据初始化。为把时间主要花在遍历算法的实现上，图的初始化采用结构体声明时初始化的方法。示例代码如下： #include "stdio.h" typedef int Arcell; typedef int AdjMatrix[5][5]; typedef struct { char vexs[5]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; void main(){ MGraph g={ {'a','b','c','d','e'}, {{0,1,0,1,0}, {1,0,0,0,1}, {1,0,0,1,0}, {0,1,0,0,1}, {1,0,0,0,0}} ,5,9}; } 2.1.2 深度优先遍历算法7.5中FirstAdjVex方法和NextAdjVex方法需要自己实现。 2.2 拓扑排序，求图的拓扑序列 2.3 "最短路径问题"，以校园导游图为实际背景进行设计。（选做） 程序代码如下： #include #include 第8章 图 8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n 个顶点的无向完全图中，边的条数为n(n-1)/2。 【解答】 【证明】 在有n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有 n-1条边与其他n-1个顶点相连，总计n 个顶点有n(n-1)条边。但在无向图中，顶点i 到顶点j 与顶点j 到顶点i 是同一条边，所以总共有n(n-1)/2条边。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。 【解答】 点，它不是强连通的有向图。各个顶点自成强连通分量。 所谓简单路径是指该路径上没有重复的顶点。 从顶点A 出发，到其他的各个顶点的简单路径有A →B ，A →D →B ，A →B →C ，A →D →B →C ，A →D ，A →B →E ，A →D →E ，A →D →B →E ，A →B →C →F →E ，A →D →B →C →F →E ，A →B →C →F ，A 1个顶点的 无向完全图 2个顶点的 无向完全图 3个顶点的 无向完全图 4个顶点的 无向完全图 5个顶点的 无向完全图 A D ????????? ?????? ?????=01 00000001001010000 010*********Edge →D →B →C →F 。 从顶点B 出发，到其他各个顶点的简单路径有B →C ，B →C →F ，B →E ，B →C →F →E 。 从顶点C 出发，到其他各个顶点的简单路径有C →F ，C →F →E 。 从顶点D 出发，到其他各个顶点的简单路径有D →B ，D →B →C ，D →B →C →F ，D →E ，D →B →E ，D →B →C →F →E 。 从顶点E 出发，到其他各个顶点的简单路径无。 从顶点F 出发，到其他各个顶点的简单路径有F →E 。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。 【解答】 (1) 邻接矩阵 A D 实习报告 题目：图遍历的演示 编译环 境： Microsoft Visual Studio 2010 功能实现： 以邻接表为存储结构，演示在连通无向图上访冋全部节点的操作； 实现连通无向图的深度优先遍历和广度优先遍历； 建立深度优先生成树和广度优先生成树，按凹入表或树形打印生成树。 1.以邻接表为存储结构，演示在连通无向图上访问全部节点的操作。 该无向图为 一个交通网络，共25个节点，30条边，遍历时需要以用户指定的节点为起点， 建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。 2.程序的测试数据：graph.txt 文件所表示的无向交通图。 //边表结点 //邻接点域，即邻接点在顶点表中的下标 //顶点表结点 //数据域 struct TNode // 树结点 { stri ng data; struct TNode *fristchild, * nextchild; }; 2.邻接表类设计： class GraphTraverse { public: 需求分析 二、概要设计 1.主要数据结构设计: struct ArcNode { int vex In dex; ArcNode* n ext; }; struct VertexNode { stri ng vertex; ArcNode* firstArc; }; 三、详细设计 1. 主要操作函数的实现： (1) 建立深度优先生成树函数： TNode* GraphTraverse::DFSForest(i nt v) { int i,j; TNode *p,*q,*DT; j=v; for(i=O;i数据结构课程设计图的遍历和生成树求解
交通标志牌设计说明
数据结构实验报告-图的遍历
数据结构(有-无向网-图)
交通标志牌结构验算
数据结构图习题
数据结构实验---图的储存与遍历
数据结构C语言版 无向图的邻接多重表存储表示和实现
交通标识技术要求
数据结构：图子系统
数据结构图的遍历
数据结构课程设计之图的遍历和生成树求解
交通标志牌结构验算
数据结构 图的存储、遍历与应用 源代码
数据结构实验四：无向图的应用
交通标志 结构设计
数据结构 图的遍历(初始化图)
数据结构-图习题
数据结构_图遍历的演示