《数据结构》上机实验报告 3.docx

《数据结构》上机实验报告 3.docx

《《数据结构》上机实验报告 3.docx》由会员分享，可在线阅读，更多相关《《数据结构》上机实验报告 3.docx（23页珍藏版）》请在冰点文库上搜索。

《数据结构》上机实验报告3

西华数学与计算机学院上机实践报告

课程名称：

数据结构

年级：

2011

上机实践成绩：

指导教师：

唐剑梅

姓名：

蒋俊

上机实践名称：

图

学号：

1118

上机实践日期：

2012-12-4

上机实践编号：

3

上机实践时间：

8:

00-9:

30

一、实验目的

1．熟悉图的两种常用的存储结构，以及在这两种存储结构上的两种遍历图的方法，即深度优先遍历和广度优先遍历。

进一步掌握递归算法的设计方法。

2．关于各种典型著名的复杂算法，在上机实验方面不做基本要求。

更适合于安排大型课程设计。

二、实验内容

1.设计一个程序，建立有向图的邻接矩阵，进行深度优先遍历，并利用广度优先遍历算法判断有向图中是否存在顶点vi到顶点vj的路径（i≠j）。

2.设计一个程序，建立无向图的邻接链表，进行广度优先遍历，并利用深度优先遍历算法判断无向图中是否存在顶点vi到顶点vj的路径（i≠j）。

三、实验环境

硬件:

微型计算机P4

软件:

WindowsXP+MicrosoftVisualC++6.0

四、程序源码及调试过程

第一题源代码：

1.cpp

#include

#include

#include"3.h"

#include"2.h"

constintMaxVertices=10;

constintMaxWeight=10000;

structMinSpanTree//带权边的三个参数

{intbegin,end;//边的起点与终点

intlength;//边的权值

};

classAdjMWGraph

{private:

intVertices[10];//顶点信息的数组

intEdge[MaxVertices][MaxVertices];//边的权信息的矩阵

intnumE;//当前的边数

intnumV;//当前的顶点数

public:

AdjMWGraph（）;//构造函数

voidCreatG（intn,inte）;//建立一个图的邻接矩阵

voidDepthF（）;

voidBoradF（）;

voidPrintOut（）;

private:

voidBorad（intv,intvisited[]）;//广度优先遍历

voidDepth（intv,intvisited[]）;//深度优先遍历

};

AdjMWGraph:

:

AdjMWGraph（）//构造函数

{for（inti=0;i

for（intj=0;j

{if（i==j）Edge[i][j]=0;

elseEdge[i][j]=MaxWeight;//MaxWeight表示无穷大

}

numE=0;//当前边个数初始为0

numV=0;

}

voidAdjMWGraph:

:

CreatG（intn,inte）

{intvi,vj,w,i;

numE=e;numV=n;

cout<<"\n输入顶点的信息（整型）：

";

for（i=0;i

{cout<<"\n"<

";

cin>>Vertices[i];

}

for（i=0;i

{cout<<"\n输入边的信息（vi,vj,W）：

";

cin>>vi>>vj>>w;

Edge[vi-1][vj-1]=w;

}

}

voidAdjMWGraph:

:

Depth（intv,intvisited[]）//深度优先遍历

{

cout<<"\n顶点"<

visited[v]=1;

for（intcol=0;col

{

if（Edge[v][col]==0||Edge[v][col]==MaxWeight）continue;

if（!

visited[col]）Depth（col,visited）;

}

}

voidAdjMWGraph:

:

DepthF（）

{

intvisit[MaxVertices];

for（inti=0;i

for（intj=0;j

if（visit[j]==0）{Depth（j,visit）;

cout<

}

}

voidAdjMWGraph:

:

Borad（intvi,intvisited[]）//广度优先遍历

{

intvj;

intv;

v=vi;

SqQueueq;

cout<

visited[vi]=1;

q.EnQueue（vi）;

while（!

q.IsEmpty（））

{

vi=q.DeQueue（）;

for（intcol=0;col

if（Edge[vi][col]>0&&Edge[vi][col]

{

cout<

visited[col]=1;

q.EnQueue（col）;

}

}

cout<

cout<<"请输入顶点vj"<

cin>>vj;

if（visited[vj-1]==1）cout<

else

cout<

}

voidAdjMWGraph:

:

BoradF（）

{

intvi,v;

intvisit[MaxVertices];

for（inti=0;i

cout<<"请输入顶点vi"<

cin>>vi;

v=vi-1;

if（visit[v]==0）{Borad（v,visit）;

cout<

}

}

voidAdjMWGraph:

:

PrintOut（）

{inti;

cout<<"\n输出顶点的信息（整型）：

\n";

for（i=0;i

cout<<"\n输出邻接矩阵：

";

for（i=0;i

{cout<<"\n"<

";

for（intj=0;j

cout<

cout<

}

}

intmain（intargc,char*argv[]）

{AdjMWGraphG;intn,e;

cout<<"\n请输入图的总顶点数（n=?

）：

";cin>>n;

cout<<"\n请输入图的总边数（e=?

）：

";cin>>e;

G.CreatG（n,e）;

G.PrintOut（）;

cout<<"深度优先遍历的结果"<

G.DepthF（）;

cout<<"用广度优先遍历算法判断有向图中是否存在顶点vi到顶点vj的路径（i≠j）。

"<

G.BoradF（）;

return0;

}

2.h

//---------------------------------------------------------------------------

//栈的顺序存储结构，顺序栈类

#include

#include

//------------------------------栈的顺序存储结构-----------------------------

//typedefintElemType;//数据元素的类型

//constintMAXSIZE=100;//数组的容量

templateclassSqStack

{private:

T*elem;

intmaxSize;

inttop;

public:

SqStack（ints=30）;

~SqStack（）{delete[]elem;}

voidpush（Titem）;

Tpop（）;

voidPrintOut（）;

intIsEmpty（）{returntop==-1;}

intIsFull（）{returntop==maxSize-1;}

};

//-------------------------------------------------------------

templateSqStack:

:

SqStack（ints）{

top=-1;

maxSize=s;

elem=newT[maxSize];

for（inti=0;i

}

templatevoidSqStack:

:

push（Titem）

{if（!

IsFull（））{top++;

elem[top]=item;}

}

templateTSqStack:

:

pop（）

{Tx;

if（!

IsEmpty（））{x=elem[top];top--;

}

returnx;

}

templatevoidSqStack:

:

PrintOut（）

{intt;

if（!

IsEmpty（））cout<<"栈已空"<

else{i=top;

while（i!

=-1）{cout<<"data="<

i--;

}

}

}

3.h

#include

templateclassSqQueue

{

public:

SqQueue（intsz=30）;

~SqQueue（）{delete[]elem;}

voidEnQueue（Titem）;

TDeQueue（）;

TGetFront（）;

intIsEmpty（）{returnfront==rear;}

intIsFull（）{return（rear+1）%maxSize==front;}

intLength（）{return（rear-front+maxSize）%maxSize;}

voidPrintOut（）;

private:

intfront,rear;

T*elem;

intmaxSize;

};

templateSqQueue:

:

SqQueue（intsz）

{

front=rear=0;maxSize=sz;

elem=newT[maxSize];

for（inti=0;i

}

templatevoidSqQueue:

:

EnQueue（Titem）

{

if（!

IsFull（））{rear=（rear+1）%maxSize;

elem[rear]=item;

}

}

templateTSqQueue:

:

DeQueue（）

{

if（!

IsEmpty（））{front=（front+1）%maxSize;

returnelem[front];

}

}

templateTSqQueue:

:

GetFront（）

{

if（!

IsEmpty（））returnelem[（front+1）%maxSize];

}

templatevoidSqQueue:

:

PrintOut（）

{

inti;

if（!

IsEmpty（））cout<<"队列已空"<

else{i=rear;

while（i!

=front）{

cout<<"data="<

i=（i-1）%maxSize;

}

}

}

第二题源代码：

2.cpp

#include

#include

#include"3.h"

constintMaxVertices=100;

typedefintVerT;

typedefintDistT;

structEdge{

intdest;

DistTweight;

Edge*next;

};

structitem{

VerTdata;

Edge*adj;

};

classAdjTWGraph

{private:

itemVertices[MaxVertices];//表头向量

intnumE;//当前的边数

intnumV;//当前的顶点数

public:

AdjTWGraph（）;//构造函数

~AdjTWGraph（）;//析构函数

voidCreatG（intn,inte）;//建立一个图的邻接表

voidDepthF（）

{

intvi,visit[MaxVertices];

for（inti=0;i

cout<<"请输入顶点vi"<

cin>>vi;

Depth（vi,visit）;

}

voidBoradF（）{

intv0,visit[MaxVertices];

for（inti=0;i

cout<<"\n请输入遍历起始顶点号:

";

cin>>v0;

cout<<"\n广度优先遍历:

";

Borad（v0,visit）;

cout<<"\n广度优先遍历结果。

";

}

voidPrintOut（）;

private:

voidBorad（intv,intvisited[]）;//广度优先遍历

voidDepth（intv,intvisited[]）;//深度优先遍历

};

AdjTWGraph:

:

AdjTWGraph（）

{

for（inti=0;i

{

Vertices[i].data=0;

Vertices[i].adj=NULL;

}

numV=0;

numE=0;

}

AdjTWGraph:

:

~AdjTWGraph（）

{

for（inti=0;i

{

Edge*p=Vertices[i].adj,*q;

while（p!

=NULL）{

q=p->next;

deletep;p=q;

}

Vertices[i].adj=NULL;

}

}

voidAdjTWGraph:

:

CreatG（intn,inte）

{

intvi,vj;

DistTw;

numE=e;

numV=n;

cout<<"\n输入顶点信息:

"<

for（inti=0;i

{

cout<<"\n"<

";

cin>>Vertices[i].data;

}

for（intj=0;j

{

cout<<"\n输入边的信息（顶点号vi顶点号vj边的权值w）：

";

cin>>vi>>vj>>w;

if（vi<1||vi>numV||vj<1||vj>numV）cout<<"\nv1或v2越界出错!

"<

Edge*q=newEdge;

q->dest=vj-1;

q->weight=w;

q->next=NULL;

if（Vertices[vi-1].adj==NULL）Vertices[vi-1].adj=q;

else{

Edge*curr=Vertices[vi-1].adj,*pre=NULL;

while（curr!

=NULL&&curr->dest

{

pre=curr;

curr=curr->next;

}

if（pre==NULL）

{

q->next=Vertices[vi-1].adj;

Vertices[vi-1].adj=q;

}

else

{

q->next=pre->next;

pre->next=q;

}

}

Edge*p=newEdge;

p->dest=vi-1;

p->weight=w;

p->next=NULL;

if（Vertices[vj-1].adj==NULL）Vertices[vj-1].adj=p;

else{

Edge*curr=Vertices[vj-1].adj,*pre=NULL;

while（curr!

=NULL&&curr->dest

{

pre=curr;

curr=curr->next;

}

if（pre==NULL）

{

p->next=Vertices[vj-1].adj;

Vertices[vj-1].adj=p;

}

else

{

p->next=pre->next;

pre->next=p;

}

}

}

}

voidAdjTWGraph:

:

PrintOut（）

{

Edge*curr;

for（inti=0;i

{

cout<<"\n输出顶点编号信息，它的邻接点编号和边的权值:

";

cout<<""<

curr=Vertices[i].adj;

while（curr!

=NULL）{

cout<<"v"<dest<<"w"<weight;

curr=curr->next;

}

cout<

}

}

voidAdjTWGraph:

:

Depth（intv,intvisited[]）//深度优先遍历

{

intvj,v0;

Edge*p;

SqQueueQ;

Q.EnQueue（v）;

while（!

Q.IsEmpty（））//队列不空，循环

{

v=Q.DeQueue（）;//出队并且访问顶点v

//cout<

visited[v]=1;

p=Vertices[v].adj;//取v的邻接边结点

while（p!

=NULL）{

v0=p->dest;//取v的邻接点编号vj

if（visited[v0]==0）Q.EnQueue（v0）;//vj未访问，入队

p=p->next;//取下一个邻接边结点

}

}

cout<<"请输入顶点vj"<

cin>>vj;

if（visited[vj]==1）cout<

else

cout<

}

voidAdjTWGraph:

:

Borad（intv,intvisited[]）//广度优先遍历

{

intvj;

Edge*p;

SqQueueQ;

cout<

Q.EnQueue（v）;

while（!

Q.IsEmpty（））

{

v=Q.DeQueue（）;

p=Vertices[v].adj;

while（p!

=NULL）

{

vj=p->dest;

if（visited[vj]==0）

{

cout<

Q.EnQueue（vj）;

}

p->next;

}

}

cout<

}

intmain（intargc,char*argv[]）

{

AdjTWGraphG;

intn,e;

intk;

do{

cout<<"\n\n\n";

cout<<"\n1.建立图的邻接表";

cout<<"\n2.利用深度优先遍历算法判断无向图中是否存在顶点vi到顶点vj的路径（i≠j）。

";

cout<<"\n3.广度优先遍历图";

cout<<"\n4.结束程序运行";

cout<<"\n==================================================";

cout<<"\n请输入你的选择（1，2，3，4）:

";cin>>k;

switch（k）

{

case1:

{cout<<"\n请输入图的总顶点数和总边数:

";

cin>>n>>e;

G.CreatG（n,e）;

G.PrintOut（）;

}break;

case2:

{G.DepthF（）;}break;

case3:

{G.BoradF（）;G.PrintOut（）;}break;

}

}while（k>=1&&k<4）;

cout<<"\n再见!

";

_getch（）;

return0;

}

3.h

#include

templateclassSqQueue

{

public:

SqQueue（intsz=30