数据结构算法专题.ppt

《数据结构算法专题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构算法专题实验实验题目：顶点路径内容：利用邻接链表和深度遍历判断两点间是否存在路径？程序：#include"iostream"usingnamespacestd;#include#defineM100//M表示邻接表中可存顶点的最大数目typedefcharVexType;typedefintAdjType;intVisited[M];//判断一个结点是否被访问typedefstructedge//链式存储边信息{intAdjVertex;structedge*nextedge;//指向下一个边结点的链域}EdgeNode;typedefstruct//

2、顺序存储节点信息{VexTypeVertex;EdgeNode*FirstEdge;//指向第一条边}VexNode;typedefVexNodeadjlist[M];结构体定义主函数intmain(intargc,char*argv[]){adjlistGraph;charvi,vj;inti;intn1,n2;intN,E;cout<<"输入顶点数目：";cin>>N;cout<<"输入边数目：";cin>>E;creatAdjlist(Graph,N,E);display(Graph,N);cout<<"输入顶点vi:";cin>>vi;cout<<"输入顶点vj:";c

3、in>>vj;for(i=1;i<=N;i++)if(Graph[i].Vertex==vi){n1=i;break;}for(i=1;i<=N;i++)if(Graph[i].Vertex==vj){n2=i;break;}DFS(Graph,n1,n2);return0;}//程序结果创建邻接链表函数voidcreatAdjlist(adjlistGraph,intN,intE){inti,j,k;EdgeNode*s;charch;cout<<“输入顶点信息:”;for(i=1;i<=N;i++){cin>>ch;Graph[i].Vertex=ch;//输入顶点字符Gr

4、aph[i].FirstEdge=NULL;//初始化令指向边结点的指针FirstEdge为空}cout<<"输入各边信息：";for(k=1;k<=E;k++){cin>>i>>j;s=newedge;//开辟一个边结点s->AdjVertex=j;s->nextedge=Graph[i].FirstEdge;Graph[i].FirstEdge=s;}}深度遍历函数voidDFS(adjlistGraph,inti,intj){EdgeNode*p;*p//邻接表表头指针Visited[i]=1;//表明第i个结点已被访问p=Graph[i].FirstEdge;while

5、(p){if(!Visited[p->AdjVertex]&&p->AdjVertex!=j)DFS(Graph,p->AdjVertex,j);//j一直不动，j是要寻找的结点序号if(p->AdjVertex==j){cout<<"它们之间存在路径！"<nextedge;if(p==NULL){cout<<"它们之间不存在路径!"<

6、h[i].Vertex<<"";cout<