数据结构课程设计--烟台大学.doc

《数据结构课程设计--烟台大学.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、atToList(MGraphg,ALGraph*&G){inti,j;ArcNode*p;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));//创建一个节点*p

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

4、>adjlist[v].firstarc;while(p!=NULL){if(visited[p->adjvex]==0)//p->adjvex顶点未访问，递归访问它{DFS(G,p->adjvex);}p=p->nextarc;//p指向顶点V的下一个邻接点}}//------广度优先遍历-----//i既是他的顶点编号voidBFS(ALGraph*G,intv){ArcNode*p;intqueue[MAXV],front=0,rear=0;//定义循环队列并初始化队头队尾intvisited[MA

5、XV];//定义存放顶点的访问标志的数组intw,i;for(i=0;i<=G->n;i++)//访问标志数组初始化{visited[i]=0;}cout<<"被访问的顶点编号："<adj

6、list[w].firstarc;//找顶点W的第一个邻接点while(p!=NULL){if(visited[p->adjvex]==0)//若当前邻接顶点未被访问{cout<<"被访问的顶点编号："<adjvex<adjvex]=1;//置顶点已被访问的标志为1rear=(rear+1)%MAXV;//该顶点进队queue[rear]=p->adjvex;}p=p->nextarc;//找顶点W的下一个邻接点}}cout<

7、-----增加站点------//voidADD(MGraphg){cout<<"增加1个站点数：";intn=1;g.n=g.n+n;cout<<"请输入增加的站点边数：";intm;cin>>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)

8、;MatToList(g,G);//-----深度优先遍历-----//for(intk=0;k<=G->n;k++)//初始化访问标记数组{visited[k]=0;}intstart=0;//从哪开始遍历cout<<"输入从哪个节点开始遍历：";cin>>start;cout<<"执行深度优先遍历。。。。。。"<