最小生成树和最短路径 数据结构实验

实验报告June 18 2015

姓名：陈斌学号：E11314079 专业：13计算机科学与技术数据结构第八次实验

学号E11314079专业计算机科学与技术姓名陈斌

实验日期2015.06.18教师签字成绩

实验报告

【实验名称】最小生成树和最短路径

【实验目的】

(1)掌握最小生成树以及最短路径的相关概念；

(2)掌握Prim算法和Kruskal算法；

(3)掌握Dijkstra算法

【实验内容】

采用普里姆算法求最小生成树

(1)编写一个算法，对于教材图7.16(a)所示的无向带权图G采用普里姆算法输出从

顶点V1出发的最小生成树。图的存储结构自选。

(2)对于上图，采用克鲁斯卡尔算法输出该图的最小生成树。（提示：a.先对边按

权值从小到大排序，得有序边集E；为所有顶点辅设一个数组Vset，标记各顶

点所处的连通分量，初始时各不相同。b. 依次从E中取出一条边(i,j)，检查顶点i和j是否属于同一连通分量，如是，则重取下一条边；否则，该边即为生成树的一条边，输出该边，同时将所有与j处于同一连通分量的顶点的Vset值都修改为与i的相同。c.重复b步直至输出n-1条边。）

源代码：

head.h:

#include

#include

#include //malloc( )

#include // INT ,MAX

#include //EOF,NULL

#include //atoi( )

#include //eof( )

#include //floor( ),ceil( ),abs( )

#include //exit( )

#include //cout,cin

//函数结果状态代码

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

//OVERFLOW 在math.h 中已定义为3

typedef int Status;

typedef int Boolean; // 布尔类型

main.cpp:

#include"head.h"

typedef int VRType;

typedef char InfoType;

#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */

#define MAX_INFO 20 /* 相关信息字符串的最大长度+1 */

typedef char VertexType[MAX_NAME];

/*图的数组(邻接矩阵)存储表示*/

#define INFINITY INT_MAX /* 用整型最大值代替∞*/

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

typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */ typedef struct

{

VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；*/ /* 对带权图，c则为权值类型*/

InfoType *info; /* 该弧相关信息的指针(可无) */

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct

{

VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量*/

AdjMatrix arcs; /* 邻接矩阵*/

int vexnum,arcnum; /* 图的当前顶点数和弧数*/

GraphKind kind; /* 图的种类标志*/

}MGraph;

int LocateVex(MGraph G,VertexType u)

{ /* 初始条件:图G存在,u和G中顶点有相同特征*/

/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int i;

for(i=0;i

if(strcmp(u,G.vexs[i])==0)

return i;

return -1;

}

Status CreateAN(MGraph &G)

{ /* 采用数组(邻接矩阵)表示法,构造无向网G*/

int i,j,k,w;

VertexType va,vb;

printf("请输入无向网G的顶点数边数(用逗号隔开):");

scanf("%d,%d",&G.vexnum,&G.arcnum);

printf("请输入%d个顶点的值(<%d个字符;用空格隔

开):\n",G.vexnum,MAX_NAME);

for(i=0;i

scanf("%s",G.vexs[i]);

for(i=0;i

for(j=0;j

{

G.arcs[i][j].adj=INFINITY; /* 网*/

}

printf("请输入%d条边的顶点1 顶点2 权值(用空格隔开): \n",G.arcnum);

for(k=0;k

{

scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回车符*/

i=LocateVex(G,va);

j=LocateVex(G,vb);

G.arcs[i][j].adj=G.arcs[j][i].adj=w; /* 无向*/

}

G.kind=AN;

return OK;

}

typedef struct

{ /* 记录从顶点集U到V-U的代价最小的边的辅助数组定义*/

VertexType adjvex;

VRType lowcost;

}minside[MAX_VERTEX_NUM];

int minimum(minside SZ,MGraph G)

{ /* 求closedge.lowcost的最小正值*/

int i=0,j,k,min;

while(!SZ[i].lowcost)

i++;

min=SZ[i].lowcost; /* 第一个不为0的值*/

k=i;

for(j=i+1;j

if(SZ[j].lowcost>0)

if(min>SZ[j].lowcost)

{

min=SZ[j].lowcost;

k=j;

}

return k;

}

void MiniSpanTree_PRIM(MGraph G,VertexType u)

{ /* 用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边算法7.9 */

int i,j,k;

minside closedge;

k=LocateVex(G,u);

for(j=0;j

{

if(j!=k)

{

strcpy(closedge[j].adjvex,u);

closedge[j].lowcost=G.arcs[k][j].adj;

}

}

closedge[k].lowcost=0; /* 初始,U={u} */

printf("最小代价生成树的各条边为:\n");

for(i=1;i

{ /* 选择其余G.vexnum-1个顶点*/

k=minimum(closedge,G); /* 求出T的下一个结点：第K顶点*/

printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]); /* 输出生成树的边*/

closedge[k].lowcost=0; /* 第K顶点并入U集*/

for(j=0;j

if(G.arcs[k][j].adj

{ /* 新顶点并入U集后重新选择最小边*/

strcpy(closedge[j].adjvex,G.vexs[k]);

closedge[j].lowcost=G.arcs[k][j].adj;

}

}

}

typedef struct node

{

int va; //边的起始顶点

int vb; //边的终止顶点

int w; //边的权值}Edge;

int Vset[MAX_VERTEX_NUM];

void Initialize(MGraph &G)

{

for(int i=0;i

Vset[i] = i;

}

int Sizearray(MGraph G)

{

return 2*G.arcnum-1;

}

void Switch(Edge &b,Edge a)

{

b.va=a.va;

b.vb=a.vb;

b.w=a.w;

}

void HeapAdjust(Edge a[],int low,int high)

{//建大顶堆

int i=low;

Edge temp;

Switch(temp,a[i]); //先将堆顶存入temp for(int j=2*i+1;j<=high;j=2*j+1)

{

if(j

j++;

if(temp.w

{ //若不满足大顶堆条件，则需进行调准Switch(a[i],a[j]);

i=j;

}

else

break;

}

Switch(a[i],temp); //最后确定a[i]的位置}

void Heapsort(Edge a[],MGraph G)

{

Edge temp;

for(int i=Sizearray(G)/2;i>=0;--i)

HeapAdjust(a,i,Sizearray(G));

for(i=Sizearray(G);i>0;--i)

{

Switch(temp,a[0]);

Switch(a[0],a[i]);

Switch(a[i],temp);

HeapAdjust(a,0,i-1);

}

}

void MiniSpanTree_Kruskal(MGraph G)

{

Edge E[MAX_VERTEX_NUM];

int k=0;

for (int i=0;i

{

for (int j=0;j

{

if (G.arcs[i][j].adj!=INFINITY)

{

E[k].va=i;

E[k].vb=j;

E[k].w=G.arcs[i][j].adj;

k++;

}

}

}

Heapsort(E,G);

Initialize(G); //初始化辅助数组k=1; //生成的边数，最后要刚好为总边数

int j=0; //E中的下标 printf("最小代价生成树的各条边及相应权值为:\n");

while (k

{

int sn1=Vset[E[j].va];

int sn2=Vset[E[j].vb]; //得到两顶点属于的集合编号

if (sn1!=sn2) //不在同一集合编号内的话，把边加入最小生成树

{

printf("(%s-%s):%d\n",G.vexs[E[j].va],G.vexs[E[j].vb],E[j].w);

k++;

for (i=0;i

if (Vset[i]==sn2)

Vset[i]=sn1;

}

j++;

}

}

void main()

{

MGraph G;

CreateAN(G);

cout<<"--------普里姆算法输出从顶点V1出发的最小生成树--------\n"<

MiniSpanTree_PRIM(G,G.vexs[0]);

cout<<"------------------------------------------------------\n"<

cout<<"--------克鲁斯卡尔算法输出从顶点V1出发的最小生成树----\n"<

MiniSpanTree_Kruskal(G);

cout<<"------------------------------------------------------"<

}

运行结果：

采用迪杰斯特拉算法求单源最短路径

编写一个算法，采用迪杰斯特拉算法，输出如下图所示的有向带权图G 中从顶点a到其他各顶点的最短路径长度和最短路径。图的存储结构自

源代码：

head.h:

#include

#include

#include //malloc( )

#include // INT ,MAX

#include //EOF,NULL

#include //atoi( )

#include //eof( )

#include //floor( ),ceil( ),abs( )

#include //exit( )

#include //cout,cin

//函数结果状态代码

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

//OVERFLOW 在math.h 中已定义为3

typedef int Status;

typedef int Boolean; // 布尔类型

main.cpp:

#include"head.h"

#define MAX_NAME 5 /* 顶点字符串的最大长度+1 */

#define MAX_INFO 20 /* 相关信息字符串的最大长度+1 */

typedef int VRType;

typedef char InfoType;

typedef char VertexType[MAX_NAME];

/*图的数组(邻接矩阵)存储表示*/

#define INFINITY INT_MAX /* 用整型最大值代替∞*/

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

typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */ typedef struct

{

VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；*/ /* 对带权图，c则为权值类型*/

InfoType *info; /* 该弧相关信息的指针(可无) */

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct

{

VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量*/

AdjMatrix arcs; /* 邻接矩阵*/

int vexnum,arcnum; /* 图的当前顶点数和弧数*/

GraphKind kind; /* 图的种类标志*/

}MGraph;

typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef int ShortPathTable[MAX_VERTEX_NUM];

int LocateVex(MGraph G,VertexType u)

{ /* 初始条件:图G存在,u和G中顶点有相同特征*/

/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int i;

for(i=0;i

if(strcmp(u,G.vexs[i])==0)

return i;

return -1;

}

Status CreateDN(MGraph *G)

{ /* 采用数组(邻接矩阵)表示法,构造有向网G */

int i,j,k,w;

VertexType va,vb;

printf("请输入有向网G的顶点数,弧数: ");

scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);

printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);

for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量*/

scanf("%s",(*G).vexs[i]);

for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵*/

for(j=0;j<(*G).vexnum;++j)

{

(*G).arcs[i][j].adj=INFINITY; /* 网*/

}

printf("请输入%d条弧的弧尾弧头权值(以空格作为间隔): \n",(*G).arcnum);

for(k=0;k<(*G).arcnum;++k)

{

scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回车符*/

i=LocateVex(*G,va);

j=LocateVex(*G,vb);

(*G).arcs[i][j].adj=w; /* 有向网*/

}

(*G).kind=DN;

return OK;

}

typedef int QElemType;

/*单链队列－－队列的链式存储结构*/

typedef struct QNode

{

QElemType data;

struct QNode *next;

}QNode,*QueuePtr;

typedef struct

{

QueuePtr front,rear; /* 队头、队尾指针*/

}LinkQueue;

LinkQueue Q;

Status InitQueue(LinkQueue *Q)

{ /* 构造一个空队列Q */

(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));

if(!(*Q).front)

exit(OVERFLOW);

(*Q).front->next=NULL;

return OK;

}

Status QueueEmpty(LinkQueue Q)

{ /* 若Q为空队列,则返回TRUE,否则返回FALSE */

if(Q.front==Q.rear)

return TRUE;

else

return FALSE;

}

Status EnQueue(LinkQueue *Q,QElemType e)

{ /* 插入元素e为Q的新的队尾元素*/

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)

{ /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */ QueuePtr p;

if((*Q).front==(*Q).rear)

return ERROR;

p=(*Q).front->next;

*e=p->data;

(*Q).front->next=p->next;

if((*Q).rear==p)

(*Q).rear=(*Q).front;

free(p);

return OK;

}

void ShortestPath_DIJ(MGraph G,int v0,PathMatrix *P,ShortPathTable *D)

{ /* 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度*/ /* D[v]。若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。*/ /* final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径算法7.15 */ int v,w,i,j,min;

Status final[MAX_VERTEX_NUM];

for(v=0;v

{

final[v]=FALSE;

(*D)[v]=G.arcs[v0][v].adj;

for(w=0;w

(*P)[v][w]=FALSE; /* 设空路径*/

if((*D)[v]

{

(*P)[v][v0]=TRUE;

(*P)[v][v]=TRUE;

}

}

(*D)[v0]=0;

final[v0]=TRUE; /* 初始化,v0顶点属于S集*/

for(i=1;i

{ /* 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集*/

min=INFINITY; /* 当前所知离v0顶点的最近距离*/

for(w=0;w

if(!final[w]) /* w顶点在V-S中*/

if((*D)[w]

{

v=w;

min=(*D)[w];

} /* w顶点离v0顶点更近*/

final[v]=TRUE; /* 离v0顶点最近的v加入S集*/

EnQueue(&Q,v);

for(w=0;w

{

if(!final[w]&&min

{ /* 修改D[w]和P[w],w∈V-S */

(*D)[w]=min+G.arcs[v][w].adj;

for(j=0;j

(*P)[w][j]=(*P)[v][j];

(*P)[w][w]=TRUE;

}

}

}

}

void main()

{

InitQueue(&Q);

int i,j,e,v0=0; /* v0为源点*/

MGraph g;

PathMatrix p;

ShortPathTable d;

CreateDN(&g);

ShortestPath_DIJ(g,v0,&p,&d);

printf("最短路径数组p[i][j]如下:\n");

for(i=0;i

{

for(j=0;j

printf("%2d",p[i][j]);

printf("\n");

}

printf("%s到各顶点的最短路径长度为：\n",g.vexs[0]);

for(i=1;i

printf("%s-%s:%d\n",g.vexs[0],g.vexs[i],d[i]);

int t[6];//用来存放最短路径的终点的序号(来自队列Q)

for(i=0;i<6;i++)

DeQueue(&Q,&t[i]);

printf("%s到各顶点的最短路径为：\n",g.vexs[0]);

for(i=1;i

{

cout<

for(j=1;j

if(p[i][t[j-1]])

{

cout<

}

cout<

}

}

运行结果：

【小结或讨论】

(1)通过本次实验，掌握了最小生成树以及最短路径的相关概念，并且会实现Prim

算法、Kruskal算法以及Dijkstra算法。

(2)在实现Prim算法时需附设一个辅助数组closedge，以记录从U到V-U具有最小

代价的边。

(3)在实现Kruskal算法时为所有顶点附设一个数组Vset，标记各顶点所处的连通

分量，还附设了一个结构体变量存放各边的起点、终点和边的权值；在对各边

按权值大小进行排序时，采用的是堆排序，初始建的是大顶堆，最终排完序后

就是按边权值从小到大的有序序列。排序过程中注意双亲结点和左右孩子结点

的序号问题，因为序号是从0开始的，所以结点i的孩子结点是2*i+1。

(4)在实现Dijkstra算法时附设了二维数组P记录从V0到各顶点的最短路径上包含

的顶点，用数组D记录各最短路径的长度，此外还附设了一个队列Q，将每次

找到的最短路径的终点入队，最后输出最短路径时根据当时入队的顺序依次输

出，这里队列可以用一维数组代替，用队列可以更好地体现算法的思想。

(5)从时间复杂度上看，Prim算法的时间复杂度为O(n^2)，与边数无关，适用于求

边稠密的网的最小生成树；Kruskal算法的时间复杂度为O(eloge)(e为网中边的

数目)，适用于边稀疏的网的最小生成树。Dijkstra算法的时间复杂度为O(n^2)。

数据结构实验报告格式

《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时）

生成树的发展历程

生成树（STP）技术的部署与调试案例 8.1 生成树（STP）技术与实现原理 在一个包含有交换机与网桥的网络中，消除环路对于获得可靠通信与防止流量在网络中不停循环必不可少。生成树协议（Spanning-tree Protocol，STP），工作在ISO七层模型中第二层，其应用能够使交换机或者网桥通过构成“生成树”，在网络拓扑中动态执行“环路遍历”，通过逻辑判断网络的链路，达到网络无环路和链路冗余的目的。 8.1.1 生成树的发展历程 网络发展过程中，以太网设备由Hub发展到透明网桥到智能交换机。透明网桥比Hub 智能，Hub收到数据包后，向除自己外的其他所有端口进行广播，而透明网桥则记录物理端口上连接设备的MAC，收到数据帧后按照记录的MAC地址向该端口发送数据帧，这样大大减少数据帧冲突。 但是透明网桥由于他的透明性，一旦网络中存在环路，一台透明网桥收到的数据帧，又会在环路中返回，这样数据帧不停在网络中增生，最终形成广播风暴，导致整个网络瘫痪；一种阻止网络环路的协议——生成树协议（STP），IEEE 802.1D标准，生成树模拟自然界树的生长规律，从树根到树梢不会形成环路，生成树协议通过对比环路网络中的设备属性的优先级、链路的开销、端口优先级等来判断环路中链路的优先级，从而逻辑上阻断优先级低的网络链路。 生成树从阻断到转发状态需要经过阻断、监听、学习、转发延迟等阶段，这个阶段大约需要30~50s的时间，对于要求高可靠性的网络来，这是不允许的。快速生成树协议（RSTP）IEEE 802.1W按结构需求产生，RSTP将阻断的端口设置备用端口，一旦检测到主链路中断，备用端口直接进入转发状态，大大加大收敛速度。 上一章介绍了VLAN在园区网中的应用与划分，很多企业在网络中都会规划多个VLAN。STP和RSTP只支持一个VLAN，对于只有一个VLAN的网络非常适用，但现在网络中全部是多VLAN的结构，每VLAN生成树和多VLAN生成树协议被提上议程。其中，每VLAN生成树 PVST 为Cisco专有的协议，该协议不兼容其他厂家的生成树协议。同时，如果VLAN多的话，过多的生成树可能导致交换机CPU、内存过载，而IEEE 802.1S 制定的多生成树协议（MSTP）通过划分域的概念，解决了CPU过度运算的问题，同时向下兼容STP、RSTP协议。本章的后续案例将分别介绍各种生成树技术的应用。

数据结构-第六章-图-练习题及答案详细解析(精华版)

图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度

⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。

数据结构二叉树实验报告

实验三二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。 二、实验环境 运行Ｃ或VC++的微机。 三、实验内容 1、依次输入元素值，以链表方式建立二叉树，并输出结点的值。 2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。 四、设计思路 1. 对于这道题，我的设计思路是先做好各个分部函数，然后在主函数中进行顺序排列，以此完成实验要求 2．二叉树采用动态数组 3.二叉树运用9个函数，主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数，关键在于访问节点 五、程序代码 #include #include #include #define OK 1 #define ERROR 0 typedef struct TNode//结构体定义 {

int data; //数据域 struct TNode *lchild,*rchild; // 指针域包括左右孩子指针 }TNode,*Tree; void CreateT(Tree *T)//创建二叉树按,依次输入二叉树中结点的值 { int a; scanf("%d",&a); if(a==00) // 结点的值为空 *T=NULL; else // 结点的值不为空 { *T=(Tree)malloc(sizeof(TNode)); if(!T) { printf("分配空间失败！！TAT"); exit(ERROR); } (*T)->data=a; CreateT(&((*T)->lchild)); // 递归调用函数，构造左子树 CreateT(&((*T)->rchild)); // 递归调用函数，构造右子树 } } void InitT(Tree *T)//构建空二叉树 { T=NULL; } void DestroyT(Tree *T)//销毁二叉树 { if(*T) // 二叉树非空 { DestroyT(&((*T)->lchild)); // 递归调用函数，销毁左子树 DestroyT(&((*T)->rchild)); // 递归调用函数，销毁右子树 free(T); T=NULL; } } void visit(int e)//访问结点 { printf("%d ",e); }

数据结构实验报告

数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

最小生成树数据结构课程设计报告

河北科技大学 课程设计报告 学生姓名：白云学号：Z110702301 专业班级：计算机113班 课程名称：数据结构课程设计 学年学期： 2 01 3—2 014学年第2学期指导教师：郑广 2014年6月

课程设计成绩评定表

目录 一、需求分析说明 (1) 1.1最小生成树总体功能要求 (1) 1.2基本功能 (1) 1.3 模块分析 (1) 二、概要设计说明 (1) 2.1设计思路 (1) 2.2模块调用图 (2) 2.3数据结构设计 (2) 2.3.1.抽象数据类型 (2) 2.3.2方法描述 (2) 三、详细设计说明 (3) 3.1主函数模块 (3) 3.2邻接表输出子模块 (3) 3.3邻接矩阵输出子模块 (3) 3.4创建邻接矩阵子模块 (3) 3.5创建邻接表子模块 (3) 3.6 Prim子模块 (3) 3.7 Kruscal子模块 (4) 四、调试分析 (4) 4.1实际完成情况说明 (4) 4.2 出现的问题及解决方案 (4) 4.3程序中可以改进的地方 (4) 六、课程设计总结 (7) 七、测试数据 (7) 八、参考书目 (7)

一、需求分析说明 1.1最小生成树总体功能要求 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 1.2基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 1.3 模块分析 主模块：用于生成界面和调用各个子模块。 Kruscal模块：以kruscal算法实现最小生成树。 Prim模块：以prim算法实现最小生成树。 邻接表模块：用邻接表方式存储图。 邻接表输出模块：输出邻接表。 邻接矩阵模块：用邻接矩阵方式存储图。 邻接矩阵模块：输出邻接矩阵。 二、概要设计说明 2.1设计思路 问题的解决分别采用普利姆算法以及克鲁斯卡尔算法。 1) 普利姆算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合V中。然后选择该顶点与V中顶点之间权值最小的一条边，以此类推，如果达到最后一个则返回上一个顶点。 2) 克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，以此类推，最终要有一个判断是否生成环，不生成则得到克鲁斯卡尔的最小生成树。

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include//库头文件-----动态分配内存空间 typedef int elemtype;//定义数据域的类型 typedef struct linknode//定义结点类型 { elemtype data;//定义数据域 struct linknode *next;//定义结点指针 }nodetype; 2）创建单链表

nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"<> d; if(d==0) break;//以0表示输入结束 if(i==1)//建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));//表示指针h h->data=d;h->next=NULL;t=h;//h是头指针 } else//建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t始终指向生成的单链表的最后一个节点

最小生成树实验报告

数据结构课程设计报告题目：最小生成树问题 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 指导教师: 2011—2012年度第 2 学期 一、需求分析 1.问题描述：

在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 2.基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 3.输入输出 以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。 二、概要设计 1.设计思路： 因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。 2.数据结构设计： 图状结构： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR} VR={|v,w∈V且P(v,w)，表示从v到w的弧， 谓词P(v,w)定义了弧的意义或信息} 基本操作： CreateGraph( &G, V, VR ) 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。 DestroyGraph( &G )

初始条件：图G存在。 操作结果：销毁图G。 LocateVex( G, u ) 初始条件：图G存在，u和G中顶点有相同特征。 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返 回其它信息。 GetVex( G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的值。 PutVex( &G, v, value ) 初始条件：图G存在，v是G中某个顶点。 操作结果：对v赋值value。 FirstAdjVex( G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点， 则返回“空”。 NextAdjVex( G, v, w ) 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。 操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的 最后一个邻接点，则返回“空”。 InsertVex( &G, v ) 初始条件：图G存在，v和图中顶点有相同特征。 操作结果：在图G中增添新顶点v。 DeleteVex( &G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及其相关的弧。 InsertArc( &G, v, w )

数据结构实验报告-二叉树的实现与遍历

《数据结构》第六次实验报告 学生姓名 学生班级 学生学号 指导老师

一、实验内容 1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序 以及按层次遍历的操作，求所有叶子及结点总数的操作。 2) 输出树的深度，最大元，最小元。 二、需求分析 遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。 递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。 下面重点来讲述非递归方法： 首先介绍先序遍历： 先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。 再次介绍中序遍历： 中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。 最后介绍后序遍历： 后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。 三、详细设计 源代码：

数据结构实验报告模板

2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList&List) //单链表排序 ListClear(&L); //将单链表L中的所有元素删除，使单链表变为空表 ListDestroy(&L);//将单链表销毁 }ADT List 其他函数： 主函数； 结点类; 约瑟夫函数 2.1 存储结构

[内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template class CirList;//声明单链表类 template class ListNode{//结点类定义； friend class CirList;//声明链表类LinkList为友元类； Type data;//结点的数据域； ListNode*next;//结点的指针域； public: ListNode():next(NULL){}//默认构造函数； ListNode(const Type &e):data(e),next(NULL){}//构造函数 Type & GetNodeData(){return data;}//返回结点的数据值； ListNode*GetNodePtr(){return next;}//返回结点的指针域的值； void SetNodeData(Type&e){data=e;}//设置结点的数据值； void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值； }; 单循环链表类： templateclass CirList { ListNode*head;//循环链表头指针 public: CirList(){head=new ListNode();head->next=head;}//构造函数，建立带头节点的空循环链表 ~CirList(){CirListClear();delete head;}//析构函数，删除循环链表 void Clear();//将线性链表置为空表 void AddElem(Type &e);//添加元素 ListNode *GetElem(int i)const;//返回单链表第i个结点的地址 void CirListClear();//将循环链表置为空表 int Length()const;//求线性链表的长度 ListNode*ListNextElem(ListNode*p=NULL);//返回循环链表p指针指向节点的直接后继，若不输入参数，则返回头指针 ListNode*CirListRemove(ListNode*p);//在循环链表中删除p指针指向节点的直接后继，且将其地址通过函数值返回 CirList&operator=(CirList&List);//重载赋

数据结构实验-二叉树的操作

******************************* 实验题目：二叉树的操作 实验者信息：班级13007102，姓名庞文正，学号1300710226 实验完成的时间3:00 ****************************** 一、实验目的 1,掌握二叉树链表的结构和二叉树的建立过程。 2,掌握队列的先进先出的运算原则在解决实际问题中的应用。 3,进一步掌握指针变量、指针数组、动态变量的含义。 4,掌握递归程序设计的特点和编程方法。 二、实验内容 已知以二叉链表作存储结构，试编写按层次遍历二叉树的算法。（所谓层次遍历，是指从二叉树的根结点开始从上到下逐层遍历二叉树，在同一层次中从左到右依次访问各个节点。）调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。 三、算法设计与编码 1.本实验用到的理论知识 总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，最好能加上自己的解释。 本算法要采用一个循环队列que，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉的目的。2.算法概要设计 给出实验的数据结构描述，程序模块、功能及调用关系 #include #include #define M 100 typedef struct node //二叉链表节点结构 {int data; //数据域 struct node *lchild,*rchild; //左孩子右孩子链 }bitree; bitree *que[M]; //定义一个指针数组，说明队列中的元素bitree 指针类型 int front=0, rear=0; //初始化循环列队 bitree *creat() //建立二叉树的递归算法 {bitree *t; int x; scanf("%d",&x); if(x==0) t=NULL; //以x=0 表示输入结束 else {t=malloc(sizeof(bitree)); //动态生成节点t，分别给节点t 的数据域，t->data=x; //左右孩子域赋值，给左右孩子赋值时用到 t->lchild=creat(); // 了递归思想 t->rchild=creat(); }

数据结构实验报告之树与二叉树

学生实验报告 学院：软通学院 课程名称：数据结构与算法 专业班级：软件142 班 姓名：邹洁蒙 学号： 0143990

学生实验报告 （二） 一、实验综述 1、实验目的及要求 目的：1）掌握树与二叉树的基本概念； 2）掌握二叉树的顺序存储，二叉链表的先序遍历中序遍历和后序遍历算法； 3）掌握树的双亲表示法。 要求：1）编程：二叉树的顺序存储实现； 2）编程：二叉链表的先序遍历中序遍历和后序遍历实现； 3）编程：树的双亲表示法实现。 2、实验仪器、设备或软件 设备：PC 软件：VC6 二、实验过程(编程，调试，运行；请写上源码，要求要有注释) 1.编程：二叉树的顺序存储实现 代码： BiTree::BiTree()//建立存储空间 { data = new int[MAXSIZE]; count = 0; } void BiTree::AddNode(int e)//加结点 { int temp = 0; data[count] = e; count++;//从编号0开始保存 }

运行截图： 2.编程：二叉链表的先序遍历中序遍历和后序遍历实现代码： void InOrderTraverse(BiTree* Head)//中序遍历 { if (Head) { InOrderTraverse(Head->LeftChild); cout << Head->data<<" "; InOrderTraverse(Head->RightChild); } } void PreOrderTraverse(BiTree* Head)//先序遍历 { if (Head) { cout << Head->data << " "; PreOrderTraverse(Head->LeftChild); PreOrderTraverse(Head->RightChild); } } void PostOrderTraverse(BiTree* Head)//后序遍历 { if (Head) { PostOrderTraverse(Head->LeftChild); PostOrderTraverse(Head->RightChild); cout << Head->data << " "; } } 运行截图：

数据结构课程设计最小生成树的构建实验报告

《数据结构课程设计》题目二：最小生成树的构建 学院：XXXXXXXXXXX 班级：XXXXXXXXXXX 学号：XXXXXXXXXXX 姓名：XXXXXXXXXXX 设计时间：XXXXXXXXXXX

目录： 1.需求分析--------------------------------------------- 1 2.课题设计内容--------------------------------------- 1 (1)课程设计基本流程------------------------------------------ 1 (2)详细设计说明------------------------------------------------1 (3)界面操作流程图：----------------------------------------- 2 (4)主要程序------------------------------------------------------3 (5)运行结果截图----------------------------------------------- 5 3.得意之处--------------------------------------------- 6 4.设计实践过程中的收获与体会------------------ 6 5.设计目前存在的问题------------------------------ 7 6.主要参考文献-------------------------------------- 7

一、需求分析 本课程主要是完成一个最小生成树的构建，要求用克鲁斯卡尔算法或者普利姆算法求网的最小生成树（此程序我用的是 普利姆算法），并输出各条边及他们的权值。要求用户在使用 时可以准确输入顶点及每个顶点的关系，运算出可以建立的关 系网，最后利用普利姆算法准确输出最短路径。 二、课程设计内容 1、课程设计基本流程： 关于此课程的设计，是从设计要求入手的。根据对知识的掌握程度，我选择了用普利姆算法进行设计。 根据实验要求，我定义了一个prims类，在类中定义一个私有成员函数和一个公有成员函数。定义相关变 量和相关函数，并完善程序。 2、详细设计说明： 首先在私有成员private中定义节点个数n、图中边的个数g，树的边的个数t，源节点s。定义二维数组 graph_edge[99][4]和tree_edge[99][4]，分别为图的边 和树的边。因为普利姆算法是把图分为两部分进行运算， 所以我定义了T1[50],t1为第一部分， T2[50],t2为第 二部分。在公有成员public中定义输入函数input()、 算法函数algorithm()、输出函数output()。 1

数据结构实验报告—二叉树

算法与数据结构》课程实验报告

一、实验目的 1、实现二叉树的存储结构 2、熟悉二叉树基本术语的含义 3、掌握二叉树相关操作的具体实现方法 二、实验内容及要求 1. 建立二叉树 2. 计算结点所在的层次 3. 统计结点数量和叶结点数量 4. 计算二叉树的高度 5. 计算结点的度 6. 找结点的双亲和子女 7. 二叉树前序、中序、后序遍历的递归实现和非递归实现及层次遍历 8. 二叉树的复制 9. 二叉树的输出等 三、系统分析 （1）数据方面：该二叉树数据元素采用字符char 型，并且约定“ #”作为二叉树输入结束标识符。并在此基础上进行二叉树相关操作。 （2）功能方面：能够实现二叉树的一些基本操作，主要包括： 1. 采用广义表建立二叉树。 2. 计算二叉树高度、统计结点数量、叶节点数量、计算每个结点的度、结点所在层次。 3. 判断结点是否存在二叉树中。 4. 寻找结点父结点、子女结点。 5. 递归、非递归两种方式输出二叉树前序、中序、后序遍历。 6. 进行二叉树的复制。 四、系统设计 （1）设计的主要思路 二叉树是的结点是一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。根据实验要求，以及课上老师对于二叉树存储结构、基本应用的讲解，同时课后研究书中涉及二叉树代码完成二叉树模板类，并将所需实现各个功能代码编写完成，在建立菜单对功能进行调试。 （2）数据结构的设计 二叉树的存储结构有数组方式和链表方式。但用数组来存储二叉树有可能会消耗大量的存储空间，故在此选用链表存储，提高存储空间的利用率。根据二叉树的定义，二叉

数据结构实验报告及心得体会

2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨

实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。

三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1; } for(i=0;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1;

生成树实验

2.当次小组成员成绩只计学号、姓名登录在下表中的。 3.在规定时间内未上交实验报告的，不得以其他方式补交，当次成绩按0 分计。 4.实验报告文件以PDF格式提交。 【实验题目】生成树协议 路的产生，避免广播风暴等。 【实验内容】 (1)完成实验教程实例3-8的实验，回答实验提出的问题及实验思考。（P117） (2)抓取生成树协议数据包，分析桥协议数据单元（BPDU）。 (3)在实验设备上查看VLAN生成树，并学会查看其它相关重要信息。 【实验要求】 一些重要信息需给出截图。 注意实验步骤的前后对比！ 【实验记录】(如有实验拓扑请自行画出,要求自行画出拓扑图) (1)实例3-8 实验拓扑图如下： 步骤0： 将PC1和PC2配置好IP地址和掩码后按照拓扑图连接实验设备。 在PC1上启动Wireshark 软件观察包的数量变化如下： 此时已经产生了广播风暴。 两台交换机此时的生成树配置信息如下： 无生成树配置信息。 用PC1pingPC2时包增长情况如下： 可见此时包增长的更快，已经产生广播风暴，但是PC并未发生死锁。 步骤1： 配置交换机A： 步骤2： 配置交换机B： 步骤3: 配置两交换机的快速生成树协议：

再按照拓扑图连接实验设备，此时包增长情况如下： 此时两PC间可以相互ping通，且无广播风暴。由此可见生成树协议的作用为避免网络中存在交换环路的时候产生广播风暴，确保在网络中有环路时自动切断环路。 步骤4：验证测试 SwitchA的生成树信息： SwitchB的生成树信息： SwitchB中RootCost和RootPort值都为0，因此SwitchB为根交换机。 根端口为G0/1。 步骤5：设置交换机的优先级 将SwitchA的优先级设置为4096 步骤6: 验证SwitchA的优先级 当两个端口都连在一个共享介质上，交换机会选择一个高优先级的端口进入forwarding状态，低优先级的端口进入discarding状态。 步骤7：验证交换机SwitchB的G0/1，G0/2，端口的状态 由上图可知，SwitchB的G0/1端口处于转发状态，G0/2端口处于组阻塞状态。 步骤8： 步骤7后每个交换机的信息如下： 两交换机G0/1端口链路down之后SwitchB的端口2信息如下：

数据结构实验二叉树

实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f 三、实验要求 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树； 2、设计求叶子结点个数算法和树的深度算法； 3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。 六、测试数据 1、输入数据：2.2*（3.1+1.20）-7.5/3 正确结果：6.96 2、输入数据：(1+2)*3+(5+6*7); 正确输出：56 七、表达式求值 由于表达式求值算法较为复杂，所以单独列出来加以分析： 1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。 例如有如下的中缀表达式： a+b-c 转换成后缀表达式为： ab+c- 然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。如上述的后缀表达式先将a 和b 放入栈中，然后碰到操作符“+”，则从栈中弹出a 和b 进行a+b 的运算，并将其结果d（假设为d）放入栈中，然后再将c 放入栈中，最后是操作符“-”，所以再弹出d和c 进行d-c 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。

数据结构实验报告图实验

图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif #include using namespace std; #include "" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0;