文档库

最新最全的文档下载
当前位置:文档库 > 数据结构图的实验报告

数据结构图的实验报告

图的实验报告

班级:电子091 学号:0908140620 姓名:何洁编号:19

(一)实验要求

创建一个图。能够实现图的输入,插入顶点和边,利用队列进行深度和广度遍历。

(二)需求分析

功能:1,输入图的信息;2,插入一个顶点;3插入一个边;4,删除一个顶点;5,删除一个边;6,深度优先遍历;7,广度优先遍历;8退出。

(三)概要设计

本程序采用的是模板类,抽象数据类型有:T,E。

类:

template

class Graphmtx {

friend istream & operator>>(istream& in,Graphmtx& G);

friend ostream & operator<<(ostream& out, Graphmtx& G);//输出

public:

Graphmtx(int sz=30, E max=0); //构造函数

~Graphmtx () //析构函数

{ delete []VerticesList; delete []Edge; }

T getValue (int i) {

//取顶点i 的值, i 不合理返回0

return i >= 0 && i <= numVertices ?

V erticesList[i] : NULL;

}

E getWeight (int v1, int v2) { //取边(v1,v2)上权值

return v1 != -1 && v2 != -1 ? Edge[v1][v2] : 0;

}

int NumberOfEdges(){return numEdges;} //返回当前边数

int NumberOfVertices(){return numVertices;} //返回当前顶点

int getFirstNeighbor (int v);

//取顶点v 的第一个邻接顶点

int getNextNeighbor (int v, int w);

//取v 的邻接顶点w 的下一邻接顶点

bool insertVertex (const T& vertex);

//插入顶点vertex

bool insertEdge (int v1, int v2, E cost);

//插入边(v1, v2),权值为cost

bool removeVertex (int v);

//删去顶点v 和所有与它相关联的边

bool removeEdge (int v1, int v2);

//在图中删去边(v1,v2)

int getVertexPos (T vertex) {

//给出顶点vertex在图中的位置

for (int i = 0; i < numVertices; i++)

if (VerticesList[i] == vertex) return i;

return -1;

}

//int numVertexPos(T vertex);

private:

int maxVertices;

int numEdges;

int numVertices;

T *VerticesList; //顶点表

E **Edge; //邻接矩阵

const E maxWeight;

};

(四)详细设计

函数通过调用图类中的函数实现一些功能。

头文件:

#include

#include

const int maxSize=50;

const int DefaultVertices=30; //最大顶点数(=n) const int maxWeight=50;

其中顺序队列的实现:

template

class SeqQueue

{

//循环队列的类的定义

public:

SeqQueue(int sz=10); //构造函数

~SeqQueue(){delete[] elements;} //析构函数

bool EnQueue(const T& x);

//若队列不满,则将X进队,否则队溢出处理

bool DeQueue(T& x);

//若队列不为空,则函数返回TRUE及对头元素的值,否则返回FALSE

void makeEmpty(){front=rear=0;}

//置空操作:对头指针和队尾指针置0

bool IsEmpty()const{return(front==rear)?true:false;}

//判队列空否,若队列空,则函数返回TRUE,否则返回FALSE

bool IsFull()const

{return((rear+1)%maxSize==front)?true:false;}

//判队列满否,若队列满,则函数返回TRUE,否则返回FALSE protected:

int rear,front; //对头和队尾指针

T *elements; //存放队列元素的数组

int maxSize; //队列最大可容纳元素个数

};

template

SeqQueue::SeqQueue(int sz):front(0),rear(0),maxSize(sz)

{

//建立最大具有Maxsize个元素的空队列

elements=new T[maxSize]; //创建队列空间

assert(elements!=NULL); //断言:动态存储分配成功与否

}

template

bool SeqQueue::EnQueue(const T& x)

{

//若队列不满,则将元素X插入到该队列的队尾,否则出错处理

if(IsFull()==true)return false; //队列满则插入失败,返回

elements[rear]=x; //按照队尾指针指示位置插入

rear=(rear+1)%maxSize; //队尾指针加1

return true; //插入成功

}

template

bool SeqQueue::DeQueue(T& x)

{

//若队列不空则函数推掉一个对头元素并返回TRUE,否则函数返回FALSE if(IsEmpty()==true)return false; //若队列空则删除失败,返回

x=elements[front];

front=(front+1)%maxSize; //对头指针加1

return true; //删除成功

}

类的实现:

template

Graphmtx::Graphmtx(int sz, E max):maxWeight(max){ //构造函数maxVertices=sz;

numVertices=0;

numEdges=0;

int i, j;

VerticesList = new T[maxVertices]; //创建顶点表

Edge = (int **) new int *[maxVertices];

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

Edge[i] = new int[maxVertices]; //邻接矩阵

for (i = 0; i < maxVertices; i++) //矩阵初始化

for (j = 0; j < maxVertices; j++)

Edge[i][j]=(i==j)?0:maxWeight;

}

template

int Graphmtx::getFirstNeighbor (int v) {

//给出顶点位置为v的第一个邻接顶点的位置,

//如果找不到, 则函数返回-1

if (v != -1) {

for (int col = 0; col < numVertices; col++)

if (Edge[v][col] && Edge[v][col] < maxWeight)

return col;

}

return -1;

}

template

int Graphmtx::getNextNeighbor (int v, int w) {

//给出顶点v 的某邻接顶点w 的下一个邻接顶点

if (v != -1 && w != -1) {

for (int col = w+1; col < numVertices; col++)

if (Edge[v][col] && Edge[v][col] < maxWeight)

return col;

}

return -1;

}

界面:

cout<<" =================================="<

cout<<" |1、输入一个图2、插入一个顶点| "<

cout<<" |3、插入一个边4、删除一个顶点|"<

cout<<" |5、删除一个边6、深度优先遍历|"<

cout<<" |7、广度优先遍历8、退出|"<

cout<<" =================================="<

数据结构图的实验报告

然后进入循环进行功能操作

Case1中,输入一个图:

其中有操作符的重载,使图的信息直接输入:

template

istream& operator >> (istream& in,Graphmtx& G){

//通过从输入流in输入n个顶点信息和e条无向边的信息建立用邻接矩阵的图G。

//邻接矩阵初始化的工作已经在构造函数中完成、

int i,j,k,n,m;

T e1,e2;

E weight;

in>>n>>m;

for(i=0;i

in>>e1;

G.insertVertex(e1);

}

i=0;

while(i

in>>e1>>e2>>weight;

j=G.getVertexPos(e1);k=G.getVertexPos(e2);

if(j==-1||k==-1)

cout<<"边两端信息有误,重新输入!"<

else{

G.insertEdge(j,k,weight);i++;

}

}

return in;

}

cout<<"请输入图的信息:"<

cin>>g1;cout<

break;

数据结构图的实验报告

Case2中,是插入顶点,需要调用的函数有:

template

bool Graphmtx::insertVertex(const T& vertex){ //插入顶点vertex

if(numVertices==maxVertices)return false; //顶点表满,不插入

VerticesList[numVertices++]=vertex;

return true;

}

case 2:

cout<<"请输入要插入的顶点:";

cin>>v1;

g1.insertV ertex (v1);

cout<

cout<<"插入成功"<

break;

出现界面:

数据结构图的实验报告

Case3中,是实现插入边的操作,需要调用的函数有:

template

bool Graphmtx::insertEdge (int v1,int v2,E cost){

//插入边(v1,v2),权值为cost

if(v1>-1&&v1-1&&v2

numEdges++;

return true;

}

else return false;

}

然后执行调用:

case 3:

cout<<"请输入插入边的两个顶点的序号:";

cin>>e1>>e2;

cout<

cout<<"请输入权值:";

cin>>cost;

g1.insertEdge (e1,e2,cost);

cout<

break;

出现界面:

数据结构图的实验报告

Case 6是进行深度优先遍历:

利用了队列,调用的函数有:

template

void DFS(Graphmtx& G, const T& v) {

//从顶点v出发对图G进行深度优先遍历的主过程

int i, loc,n;

n=G.NumberOfVertices(); //顶点个数

bool *visited=new bool[n]; //创建辅助数组

for (i = 0; i < n; i++) visited [i] = false;

//辅助数组visited初始化

loc = G.getVertexPos(v);

DFS (G, loc, visited); //从顶点0开始深度优先搜索

delete [] visited; //释放visited

}

template

void DFS(Graphmtx& G, int v, bool visited[]) {

cout << G.getValue(v) << ' '; //访问顶点v

visited[v] = true; //作访问标记

int w = G.getFirstNeighbor (v); //第一个邻接顶点

while (w != -1) { //若邻接顶点w存在

if ( !visited[w] ) DFS(G, w, visited);

//若w未访问过, 递归访问顶点w w = G.getNextNeighbor (v, w); //下一个邻接顶点

}

}

主函数中:

case 6:

cout<<"请输入一个顶点:";

cin>>v1;

cout<<"图的深度优先搜索为:"<

DFS(g1,v1);

cout<

break;

界面出现:

数据结构图的实验报告

Case7是现实广度优先遍历的操作,也需要利用到队列,

其函数体为:

template

void BFS(Graphmtx& G, const T& v) {

int i,w;

int n = G.NumberOfVertices();

//图中顶点个数

bool *visited = new bool[n];

for (i = 0; i < n; i++) visited[i] = false;

int loc = G.getVertexPos (v); //取顶点号

cout << G.getValue (loc) << ' '; //访问顶点v

visited[loc] = true; //做已访问标记

SeqQueue Q; Q.EnQueue (loc); //顶点进队列, 实现分层访问

while (!Q.IsEmpty() ) { //循环, 访问所有结点

Q.DeQueue (loc);

w = G.getFirstNeighbor (loc); //第一个邻接顶点

while (w != -1) { //若邻接顶点w存在

if (!visited[w]) { //若未访问过

cout << G.getValue (w) << ' '; //访问

visited[w] = true;

Q.EnQueue (w); //顶点w进队列

}

w = G.getNextNeighbor (loc, w); //找顶点loc的下一个邻接顶点

}

} //外层循环,判队列空否

delete [] visited;

}

主函数中的调用:

case 7:

cout<<"请输入一个顶点:";

cin>>v1;

cout<<"图的广度优先搜索为:"<

BFS(g1,v1);

cout<

break;

界面显示:

数据结构图的实验报告

Case4中式删除顶点的操作;

函数的实现:

template

bool Graphmtx::removeVertex (int v){

//删去顶点v和所有与它相关的边

if(v<0||v>=numVertices)return false;

if(numVertices==1)return false;

int i,j;

VerticesList[v]=VerticesList[numVertices-1];

for(i=0;i

if(Edge[i][v]<0&&Edge[i][v]

for(i=0;i

Edge[i][v]=Edge[i][numVertices-1];

numVertices--;

for(j=0;j

Edge[v][j]=Edge[numVertices][j];

return true;

}

主函数中:

case 4:

cout<<"请输入要删除的顶点序号:";

cin>>e1;

g1.removeVertex(e1);

cout<

break;

界面显示:

数据结构图的实验报告

Case5的操作是删除一条边:要调用的函数:

template

bool Graphmtx::removeEdge (int v1,int v2){

//在图中删除边(v1,v2)

if(v1>-1&&v1-1&&v20&&Edge[v1][ v2]

Edge[v1][v2]=Edge[v2][v1]=maxWeight;

numEdges--;

return true;

}

else return false;

}

在主函数中:

case 5:

cout<<"请输入要删除边的两个顶点序号:";

cin>>e1>>e2;

g1.removeEdge(e1,e2);

cout<

break;

界面显示:

数据结构图的实验报告

Case8 的操作是退出

case 8:

return 0;

break;

界面显示:

数据结构图的实验报告

(五)调试与测试

在调试过程中遇到很多问题,在定义变量的时候遇到一些问题,对于全局变量还是局部变量要区分一下。还有,对于出现某种错误,如函数重载等,都可以解决了。