数据结构课程设计--站点分布图（二）

《数据结构课程设计--站点分布图（二）》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、烟台大学数据结构课程设计报告站点分布图（二）问题描述：尽可能多的列出烟台的公交站点。用图创建一个站点分布图，包括站点的增加、删除、从一点出发深度优先搜索所有的站点、从一点出发广度优先搜索所有的站点。数据结构与算法的设计：通过分析决定采用无向图结构，采用了深度优先遍历（DFS），广度优先遍历（BFS）等算法。程序实现：实现了深度优先输出所有站点，广度优先输出所有站点，增加站点，删除站点。测试及分析：源代码选摘：//------邻接矩阵转化成邻接表------//voidMatToList(MGraphg,ALGraph&G){i

2、nti,j;ArcNodep;G=(ALGraph)malloc(sizeof(ALGraph));for(i=1;i<=g.n;i++)//给邻接表中所有头结点指针赋初值{G->adjlist[i].firstarc=NULL;}for(i=1;i<=g.n;i++){for(j=g.n;j>=1;j--){if(g.edges[i][j]!=0){p=(ArcNode)malloc(sizeof(ArcNode));//创建一个节点pp->adjvex=j;//该边的终点号p->nextarc=G->adjlist[i].

3、firstarc;//采用头插法插入pG->adjlist[i].firstarc=p;}}}G->n=g.n;G->e=g.e;}//------深度优先遍历-----//intvisited[MAXV];voidDFS(ALGraphG,intv)//v表示顶点{ArcNodep;visited[v]=1;//置已访问标记cout<<"输出访问顶点编号:"<adjlist[v].firstarc;while(p!=NULL){if(visited[p->adjvex]==

4、0)//p->adjvex顶点未访问，递归访问它{DFS(G,p->adjvex);}p=p->nextarc;//p指向顶点V的下一个邻接点}}//------广度优先遍历-----//i既是他的顶点编号voidBFS(ALGraphG,intv){ArcNodep;intqueue[MAXV],front=0,rear=0;//定义循环队列并初始化队头队尾intvisited[MAXV];//定义存放顶点的访问标志的数组intw,i;for(i=0;i<=G->n;i++)//访问标志数组初始化{visited[i]=0;

5、}cout<<"被访问的顶点编号："<adjlist[w].firstarc;//找顶点W的第一个邻接点while(p!=NULL){if(visited[p->adjvex]==0)//若当前邻接顶点未被访问

6、{cout<<"被访问的顶点编号："<adjvex<adjvex]=1;//置顶点已被访问的标志为1rear=(rear+1)%MAXV;//该顶点进队queue[rear]=p->adjvex;}p=p->nextarc;//找顶点W的下一个邻接点}}cout<

7、in>>m;g.e=g.e+m;inti,j;intp=0;while(p>i;cout<<"请输入尾：";cin>>j;g.edges[i][j]=1;g.edges[j][i]=1;p++;}outputLJJZ(g);MatToList(g,G);//-----深度优先遍历-----//for(intk=0;k<=G->n;k++)//初始化访问标记数组{visited[k]=0;}intstart=0;//从哪开始遍历c

8、out<<"输入从哪个节点开始遍历：";cin>>start;cout<<"执行深度优先遍历。。。。。。"<