?? graph.cpp
字號:
//graph.cpp
#include<iostream>
#include "graph.h"//引入頭文件
/*
*前置條件：圖不存在
*輸 入：無
*功 能：圖的初始化
*輸 出：無
*后置條件：得到一個有向圖
*/
template <class T>
ALGraph<T>::ALGraph(T a[ ], int n, int e)
{
arcNum = e; //邊數(shù)
vertexNum=n; //頂點(diǎn)數(shù)
int i,j;
for (i=0; i<vertexNum; i++)
{
VertexNode<T> tempvertex;
tempvertex.vertex = a[i];
tempvertex.firstedge = NULL;
adjlist[i] = tempvertex;
}
for (int k=0; k<arcNum; k++) //依次輸入每一條邊，并在相應(yīng)邊表中插入結(jié)點(diǎn)
{
cout<<"請輸入邊所依附的兩個頂點(diǎn)的序號";
cin>>i>>j; //輸入邊所依附的兩個頂點(diǎn)的序號
ArcNode *s=new ArcNode; s->adjvex=j; //生成一個邊表結(jié)點(diǎn)s
s->next=adjlist[i].firstedge; //將結(jié)點(diǎn)s插入到結(jié)點(diǎn)i的邊表的表頭
adjlist[i].firstedge=s;
}
InsertArc(0,1); //插入邊
InsertArc(0,2);
InsertArc(0,3);
InsertArc(1,3);
InsertArc(1,4);
InsertArc(2,0);
InsertArc(2,4);
InsertArc(3,1);
InsertArc(3,4);
InsertArc(4,2);
InsertArc(4,3);
}
/* 前置條件：圖已存在
* 輸 入：無
* 功 能：銷毀圖
* 輸 出：無
* 后置條件：釋放圖所占用的存儲空間
*/
template <class T>
ALGraph<T>::~ALGraph( )
{
for (int i=0; i<vertexNum; i++)
{
ArcNode * p=adjlist[i].firstedge;
while (p!=NULL) //循環(huán)刪除
{
adjlist[i].firstedge=p->next;
delete p; //釋放結(jié)點(diǎn)空間
p=adjlist[i].firstedge;
}
}
}
/*
*前置條件：圖已存在
*輸 入：頂點(diǎn)i
*功 能：輸出圖中頂點(diǎn)i的數(shù)據(jù)信息
*輸 出：圖中頂點(diǎn)i的數(shù)據(jù)信息
*后置條件：圖保持不變
*/
template <class T>
T ALGraph<T>::GetVex(int i)
{
if ( i>vertexNum || i<0 ) throw "輸入頂點(diǎn)的位置不正確"; //頂點(diǎn)i不存在則拋出異常
return adjlist[i].vertex; //返回第i個頂點(diǎn)的數(shù)據(jù)域
}
/*
*前置條件：圖已存在
*輸 入：頂點(diǎn)i
*功 能：將圖中頂點(diǎn)i的數(shù)據(jù)域置為value
*輸 出：無
*后置條件：圖保持不變
*/
template <class T>
void ALGraph<T>::PutVex(int i, T value)
{
if ( i>vertexNum || i<0 ) throw "輸入頂點(diǎn)的位置不正確"; //頂點(diǎn)i不存在則拋出異常
adjlist[i].vertex = value; //第i個頂點(diǎn)的數(shù)據(jù)域置為value
}
/*
*前置條件：圖已存在
*輸 入：頂點(diǎn)value,位置i
*功 能：在圖中i位置插入一個頂點(diǎn)name
*輸 出：如果插入不成功，拋出異常
*后置條件：如果插入成功，圖中增加了一個頂點(diǎn)
*/
template <class T>
void ALGraph<T>::InsertVex(int i, T value)
{
if ( i>vertexNum || i<0 || i>MaxSize ) throw "輸入頂點(diǎn)的位置不正確"; //頂點(diǎn)i不存在則拋出異常
vertexNum++; //頂點(diǎn)數(shù)加1
VertexNode<T> tempvertex;
tempvertex.vertex = value;
tempvertex.firstedge = NULL;
adjlist[i] = tempvertex; //第i個頂點(diǎn)的數(shù)據(jù)域置為value
}
/*
*前置條件：圖已存在
*輸 入：頂點(diǎn)i
*功 能：在圖中刪除頂點(diǎn)i
*輸 出：如果刪除不成功，拋出異常
*后置條件：如果刪除成功，圖中減少了一個頂點(diǎn),相應(yīng)頂點(diǎn)所建立的邊也消去
*/
template <class T>
void ALGraph<T>::DeleteVex(int i)
{
if ( i<0 || i>MaxSize) throw "位置"; //頂點(diǎn)輸入錯誤則拋出異常
int k;
for ( k=0; k<vertexNum; k++) //刪掉入度邊
if(k!=i) DeleteArc(k, i);
ArcNode *s; //生成一個邊表結(jié)點(diǎn)s
if( adjlist[i].firstedge != NULL)
{
ArcNode *s;
s=adjlist[i].firstedge->next;
while(s!=NULL)
{
ArcNode *p;
p = s;
adjlist[i].firstedge->next = s->next;
s=s->next;
delete p; //刪除p結(jié)點(diǎn)
}
s=adjlist[i].firstedge;
adjlist[i].firstedge=NULL;
delete s;
}
for (k=i; k<vertexNum; k++)
{
adjlist[k]=adjlist[k+1]; //存儲頂點(diǎn)信息
}
vertexNum--; //頂點(diǎn)數(shù)減1
for (k=0; k<vertexNum; k++)
if( adjlist[k].firstedge != NULL )
{
s=adjlist[k].firstedge; //將結(jié)點(diǎn)s插入到結(jié)點(diǎn)i的邊表的表頭
while(s!=NULL)
{
if(s->adjvex > i) //搜索i結(jié)點(diǎn)
s->adjvex--;
s = s->next;
}
}
}
/*
*前置條件：圖已存在
*輸 入：頂點(diǎn)i、j
*功 能：在圖中插入頂點(diǎn)i、j及其所依附的邊
*輸 出：如果插入不成功，拋出異常
*后置條件：如果插入成功，圖中增加了一條邊
*/
template <class T>
void ALGraph<T>::InsertArc(int i, int j)
{
if ( i>MaxSize || j>MaxSize) throw "位置";//頂點(diǎn)輸入錯誤則拋出異常
ArcNode *s=new ArcNode; s->adjvex=j; //生成一個邊表結(jié)點(diǎn)s
s->next=adjlist[i].firstedge; //將結(jié)點(diǎn)s插入到結(jié)點(diǎn)i的邊表的表頭
adjlist[i].firstedge=s;
}
/*
*前置條件：圖已存在
*輸 入：頂點(diǎn)i、j
*功 能：在圖中刪除頂點(diǎn)i、j 依附的邊
*輸 出：如果刪除不成功，拋出異常
*后置條件：如果刪除成功，圖中減少了一條邊
*/
template <class T>
void ALGraph<T>::DeleteArc(int i, int j)
{
if ( i>MaxSize|| j>MaxSize) throw "位置"; //頂點(diǎn)輸入錯誤則拋出異常
ArcNode *s;
ArcNode *tempnode;
s = adjlist[i].firstedge;
tempnode = adjlist[i].firstedge;
while(s!=NULL && s->adjvex!=j)
{
tempnode = s;
s = s->next;
}
if(s!=NULL)
{
tempnode->next = s->next;
delete s;
}
}
/*
*前置條件：圖已存在
*輸 入：遍歷的起始頂點(diǎn)v
*功 能：從頂點(diǎn)v出發(fā)深度優(yōu)先遍歷圖
*輸 出：圖中頂點(diǎn)的一個線性排列
*后置條件：圖保持不變
*/
template <class T>
void ALGraph<T>::DFSTraverse(int v)
{
if ( v>vertexNum) throw "位置"; //頂點(diǎn)輸入錯誤則拋出異常
ArcNode * p;
int j;
cout<<adjlist[v].vertex<<" ";
visited[v]=1;
p=adjlist[v].firstedge;
while (p) //依次搜索頂點(diǎn)v的鄰接點(diǎn)j
{
j=p->adjvex;
if (visited[j]==0) DFSTraverse(j);
p=p->next;
}
}
/*
*前置條件：圖已存在
*輸 入：遍歷的起始頂點(diǎn)v
*功 能：從頂點(diǎn)v出發(fā)廣度優(yōu)先遍歷圖
*輸 出：圖中頂點(diǎn)的一個線性排列
*后置條件：圖保持不變
*/
template <class T>
void ALGraph<T>::BFSTraverse(int v)
{
if ( v>vertexNum) throw "位置"; //頂點(diǎn)輸入錯誤則拋出異常
int front,rear,j;
ArcNode * p; //生成一個邊表結(jié)點(diǎn)p
int Q[MaxSize];
front=rear=-1; //初始化隊(duì)列, 假設(shè)隊(duì)列采用順序存儲且不會發(fā)生溢出
cout<<adjlist[v].vertex<<" "; visited[v]=1; Q[++rear]=v; //被訪問頂點(diǎn)入隊(duì)
while (front!=rear)
{
v=Q[++front];
p=adjlist[v].firstedge; //邊表中的工作指針p初始化
while (p)
{
j= p->adjvex;
if (visited[j]==0) {
cout<<adjlist[j].vertex<<" "; visited[j]=1;Q[++rear]=j;
}
p=p->next;
}
}
}?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -