数据结构实验六简单路径Word文档下载推荐.docx
- 文档编号:5906167
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:25
- 大小:190.96KB
数据结构实验六简单路径Word文档下载推荐.docx
《数据结构实验六简单路径Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《数据结构实验六简单路径Word文档下载推荐.docx(25页珍藏版)》请在冰点文库上搜索。
00030004
00010004
00
输出:
两城市间的路径为:
0001000200030004
②.正常的输入:
5
c1
c2
c3
c4
请输入输入城市5名称:
c5
c1c2
c1c5
c5c4
c4c3
c2c4
c2c1c5c4
③.无路径情况:
3
a
b
c
请输入城市间的高速公路:
ab
ac
④.错误的城市个数
-1
输入错误重新输入(大于零的整数)
请输入城市总数2
1
2
12
两城市的路径为12
⑤.存在自返路径
上海
长沙
上海上海
上海长沙
长沙上海
二、概要设计
1.抽象数据类型
因为各个结点之间是网状结构,那么一个结点会和多个结点连接,因此我们使用图来存储各个结点的信息。
同时我们需要一个数据结构来搜索图,该数据结构满足先进后出,所以使用栈来实现。
2.ADT
ADTStack{
数据对象:
D={ai|ai∈binNode,i=1,2,...,n,n≥0
数据关系:
R1={<
ai-1,ai>
|ai-1,ai∈D,i=2,...,n}
约定an端为栈顶,a1端为栈底。
若栈中没有元素,则为空栈。
基本操作:
boolpush(constBinNode&
item);
boolpop(BinNode&
it);
booltopValue(BinNode&
intlength();
const;
}
ADTGraph{
数据对象:
V,R(图是由一个顶点集V和一个弧集R构成的数据结构)
数据关系:
Graph=(V,R)VR={<
v,w>
|v,w∈V且P(v,w)}
基本操作:
intn()=0;
//返回图节点数
inte()=0;
//返回图边数
intfirst(int)=0;
//返回该节点的第一条邻边
voidsetEdge(intv1,intv2)//加边
intnext(int,int)=0;
//返回下一条邻边
intgetMark(int)=0;
//有标记吗
voidsetMark(int,int)=0;
//设置标记}
3.算法的基本思想
使用深度优先搜索DFS对图进行遍历,在搜索过程中,每当访问一个顶点V后,DFS就会递归的访问它的所有未被访问的相邻顶点。
即先访问点v,把所有与v相关联的边存入栈,弹出栈顶元素,栈顶元素代表的边所关联的另一个顶点就是就是要访问的下一个元素,重复对v的操作;
依次类推直到所有元素都被处理完毕。
4程序流程
程序主要由四个步骤组成:
(1)
输入城市总数
(2)
输入正确的城市编号列表
(3)
输入所有的有高速公路直接连接的城市对编号
(4)
循环输入需要寻找路径的城市对的编号寻找它们之间的所有简单路径。
三.详细设计
1.物理数据类型
由于边数目未知,所以对于遍历图的时间效率并不清楚,所以可以用邻接表或者邻接矩阵来实现,本实验中使用邻接矩阵。
栈元素未知,用链表来实现栈。
用string保存输入的城市名信息。
2.算法的具体步骤
图的构建——路径的存储——深度优先搜索——栈元素的打印
图的构建:
创建一个城市数n*城市数n的二阶矩阵,并且给每一个元素赋值为零。
Graph(intnumVert)
{
inti,j;
numVertex=numVert;
numEdge=0;
mark=newPoint[numVert];
//Initializemarkarray
for(i=0;
i<
numVertex;
i++)
mark[i].ViMark=-1;
matrix=(int**)newint*[numVertex];
//Makematrix
matrix[i]=newint[numVertex];
numVertex;
i++)//Edgesstartw/0weight
for(intj=0;
j<
j++)matrix[i][j]=0;
}
路径的存储:
将城市v1到城市v2在矩阵中对应的坐标(v1,v2)赋值为1。
void
setEdge(int
v1,
int
v2)
{
if
(matrix[v1][v2]
==
0)
numEdge++;
matrix[v1][v2]
=
1;
}
深度优先搜索:
在搜索过程中,每当访问一个顶点V后,DFS就会递归的访问它的所有未被访问的相邻顶点。
当弹出栈的元素就是我们需要到达的城市v2时,输出整个栈的元素,再将v2的值设置为-1,表示为未访问状态,将v2弹出栈,重复对v的操作;
voidDFS(Graph*G,intv1,intorigin,intv2,AStack&
b,intM[100][100],intD[100],int&
count)
stringCh;
b.push(G->
getVal(v1));
intv;
G->
setMark(v1,1);
if(G->
getVal(v1)==G->
getVal(v2))
{
for(inti=0;
G->
n();
j++)
G->
setEdge(i,j,M[i][j]);
//将路径进栈
cout<
<
"
两城间的路径为:
;
b.print();
endl;
b.pop(Ch);
//即城市v2出栈
G->
setMark(v2,-1);
//将v2标记为未被访问
count++;
//路线多一条
return;
for(intw=G->
first(v1);
w<
w=G->
next(v1,w))//访问v1所有顶点
setEdge(w,v1,0);
if(G->
getMark(w)==-1||w==5)
{
DFS(G,w,origin,v2,b,M,D,count);
}
b.pop(Ch);
Find(Ch,v);
setMark(v,-1);
栈所有元素的打印:
新建一个和需要打印栈a长度相同的栈b,栈a中每一个元素依次出栈进入栈b,直到栈a为空,栈b依次出栈,并且输出每一个元素的值,同时将这些元素进栈a,直到栈b为空。
voidprint()
stringCh;
AStackb(length());
while(pop(Ch))
b.push(Ch);
while(b.pop(Ch))
cout<
Ch<
push(Ch);
3.算法的时空分析及改进设想
因为图的邻接矩阵是一个|V|×
|V|矩阵,所以邻接矩阵的空间代价为Θ(|V|^2),对于有n个顶点的和E条弧的无向图而言,DFS对每条边分别沿两个方向进行处理,且每个顶点必须被访问一次,所以总的时间代价为Θ(|V|+|E|)。
综上可知,该程序的时间复杂度为Max(Θ(|V|^2),Θ(|V|+|E|))。
4.输入和输出的格式
①.条件的输入
cout<
cin>
>
n;
if(n<
=0)
输入错误重新输入(大于零的整数)"
cin>
Grapha(n);
for(inti=0;
n;
请输入城市"
i+1<
编号:
Ch;
a.setVal(i,Ch);
cout<
请输入城市之间的高速公路(输入两个0结束输入):
Ch1;
Ch2;
while(Ch1!
="
0"
)
a.Find(Ch1,v1);
a.Find(Ch2,v2);
a.setEdge(v1,v2,10);
a.setEdge(v2,v1,10);
请输入城市之间的公路:
②.输入要查找的城市
请输入要查找的两个城市:
Ch1>
③.连通情况路径的输出(即上述算法中的栈元素的打印)
④.不连通时的输出
if(count==0)
两个城市不连通"
4.测试结果
#include<
iostream>
fstream>
string>
iomanip>
usingnamespacestd;
classAStack
private:
intsize;
//栈的大小
inttop;
//栈中元素的多少
string*listArray;
public:
AStack(intsz=0)//构建栈
size=sz;
top=0;
listArray=newstring[sz];
~AStack()//销毁栈
delete[]listArray;
boolpush(conststring&
item)//压栈
if(top==size)returnfalse;
//如果栈已满则returnfalse
else
{
listArray[top++]=item;
returntrue;
}
boolpop(string&
it)//出栈
if(top==0)returnfalse;
//如果栈为空栈,则returnfalse
it=listArray[--top];
intlength()const//获取栈的长度
returntop;
voidprint()
stringCh;
AStackb(length());
while(pop(Ch))
b.push(Ch);
while(b.pop(Ch))
cout<
push(Ch);
};
classPoint
public:
stringLessonName;
intViMark;
};
classGraph
{//Implementadjacencymatrix
private:
intnumVertex,numEdge;
//Storenumberofverticesedges
int**matrix;
//Pointertoadjacencymatrix
Point*mark;
//Pointertomarkarray
Graph(intnumVert)
{//Makegraphw/numVertvertices
matrix=(int**)newint*[numVertex];
matrix[i]=newint[numVertex];
~Graph()
delete[]mark;
delete[]matrix[i];
delete[]matrix;
intn()
returnnumVertex;
inte()
returnnumEdge;
intfirst(intv)
{//Returnv'
sfirstneighbor
inti;
if(matrix[v][i]!
=0&
&
mark[i].ViMark==-1)returni;
returni;
//Returnnifnone
intnext(intv1,intv2)
//Getv1'
sneighborafterv2
for(i=v2+1;
if(matrix[v1][i]!
mark[i].ViMark==-1)
//cout<
此时next的i值是:
v1+1<
i+1<
endl;
returni;
//Setedge(v1,v2)towgt
voidsetEdge(intv1,intv2,intwgt)
if(matrix[v1][v2]==0)numEdge++;
matrix[v1][v2]=wgt;
voiddelEdge(intv1,intv2)
{//Deleteedge(v1,v2)
if(matrix[v1][v2]!
=0)
numEdge--;
matrix[v1][v2]=0;
intweight(intv1,intv2)
returnmatrix[v1][v2];
stringgetVal(intv)
returnmark[v].LessonName;
intgetMark(intv)
returnmark[v].ViMark;
voidsetVal(intv,stringval)
mark[v].LessonName=val;
voidsetMark(intv,intMark)
mark[v].ViMark=Mark;
voidFind(stringsearch,int&
v)
if(mark[i].LessonName==search)
v=i;
return;
路径错误"
voidDFS(Graph*G,intv1,intv2,AStack&
b,int&
//将v1边进栈
getVal(v2))//已经连通的情况
next(v1,w))//访问v1所有边
//访问后G图中此条路径变为0
getMark(w)==-1)
DFS(G,w,v2,b,count);
//访问v1的下一条路径
//出栈并且将v1边的值给ch
//找到v对应的边
//设置为未访问
intmain()
intn;
intv1;
intv2;
stringCh1;
stringCh2;
intcount=0;
a.setEdge(v1,v2,1);
a.setEdge(v2,v1,1);
a.Find(Ch1,v1);
a.Find(Ch2,v2);
AStackb(n);
DFS(&
a,v1,v2,b,count);
//图a查找城市v1查找城市v2栈b
if(count==0)
system("
pause"
);
return0;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 简单 路径