数据结构课程MATCH_
word
word文档格式规范word作业纸小票打印word模板word简历模板免费word简历
_1715938086355_0 数据结构课程设计 课题名称： 图的遍历的实现 学 院： 信息学院 专 业： 08 电子 姓 名： 目 录 一、课程设计内容和要求 ……………………………………2 1.1设计目的 ……………………………………2 1.2设计要求 ……………………………………2 二、总体设计
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
……………………………………2 三、图遍历的程序设计 ……………………………………………2 3.1图的邻接表 ……………………………………………2 3.2图的矩阵 ……………………………………………4 四、运行结果 …………………………………………………9 4.1原图 ………………………………………10 4.2运行界面 ………………………………………10 4.3运行结果 ………………………………………………10 五、总结 ………………………………………………11 六、参考文献 ………………………………………………11 图的遍历的实现 一、课程设计内容和要求 1.1设计目的 学习和巩固数据结构的基本知识； 充分体会在程序设计中数据的重要作用，学会在程序设计中运用数据结构的相关知识解决问题。 1.2设计要求 先任意创建一个图； 图的DFS、BFS的递归和非递归算法的实现； 要求用有向图和无向图分别实现； 要求用邻接矩阵、邻接表多种结构存储实现； 二、总体设计流程 1、图的初始化 定义图并初始化图 2、用邻接表表示连通图的建立 用邻接表遍历输出 1.邻接表的深度优先搜索 连接表的广度优先搜索 3、用邻接矩阵表示连通图的建立 用邻接矩阵遍历输出 1.邻接矩阵的深度优先搜索 2.邻接矩阵的广度优先搜索 三、图遍历的程序设计 3.1邻接表的遍历 #include"stdio.h" #include"stdlib.h" #define MaxVertexNum 50 /*定义最大顶点数*/ typedef struct node /*边表结点*/ { int adjvex; /*邻接点域*/ struct node *next; /*链域*/ }EdgeNode; typedef struct vnode /*顶点表结点*/ { char vertex; /*顶点域*/ EdgeNode *firstedge; /*边表头指针*/ }VertexNode; typedef VertexNode AdjList[MaxVertexNum]; /*AdjList是邻接表类型*/ typedef struct { AdjList adjlist; /*邻接表*/ int n,e; /*图中当前顶点数和边数*/ } ALGraph; /*图类型*/ /* 建立图的邻接表 */ void CreatALGraph(ALGraph *G) { int i,j,k; char a; EdgeNode *s; /*定义边表结点*/ printf("输入顶点数和边数: "); scanf("%d,%d",&G->n,&G->e); /*读入顶点数和边数*/ scanf("%c",&a); printf("输入顶点数值:"); for(i=0;i
n;i++) /*建立边表*/ { scanf("%c",&a); G->adjlist[i].vertex=a; /*读入顶点信息*/ G->adjlist[i].firstedge=NULL; /*边表置为空表*/ } printf("输入边（Vi，Vj）的顶点对序号\n"); for(k=0;ke;k++) { /*建立边表*/ scanf("%d%d",&i,&j); /*读入边（Vi，Vj）的顶点对序号*/ s=(EdgeNode *)malloc(sizeof(EdgeNode)); /*/生成边表结点*/ s->adjvex=j; /*邻接点序号为j*/ s->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=s; /*将新结点*S插入顶点Vi的边表头部*/ s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=i; /*邻接点序号为i*/ s->next=G->adjlist[j].firstedge; G->adjlist[j].firstedge=s; /*将新结点*S插入顶点Vj的边表头部*/ } } /* 定义标志向量，为全局变量 */ typedef enum{FALSE,TRUE} Boolean; Boolean visited[MaxVertexNum]; /* DFS：深度优先遍历的递归算法 */ void DFSM(ALGraph *G,int i) { /*以Vi为出发点对邻接链表表示的图G进行DFS搜索*/ EdgeNode *p; printf("%c ",G->adjlist[i].vertex); /*访问顶点Vi*/ visited[i]=TRUE; /*标记Vi已访问*/ p=G->adjlist[i].firstedge; /*取Vi边表的头指针*/ while(p) { /*依次搜索Vi的邻接点Vj，这里j=p->adjvex*/ if(! visited[p->adjvex]) /*若Vj尚未被访问*/ DFSM(G,p->adjvex); /*则以Vj为出发点向纵深搜索*/ p=p->next; /*找Vi的下一个邻接点*/ } } void DFS(ALGraph *G) { int i; for(i=0;in;i++) visited[i]=FALSE; /*标志向量初始化*/ for(i=0;in;i++) if(!visited[i]) /*Vi未访问过*/ DFSM(G,i); /*以Vi为源点开始DFS搜索*/ } /* BFS：广度优先遍历 */ void BFS(ALGraph *G,int k) { /*以Vk为源点对用邻接链表表示的图G进行广度优先搜索*/ int i,f=0,r=0; EdgeNode *p; int cq[MaxVertexNum]; /*定义FIFO队列*/ for(i=0;in;i++) visited[i]=FALSE; /*标志向量初始化*/ for(i=0;i<=G->n;i++) cq[i]=-1; /*初始化标志向量*/ printf("%c ",G->adjlist[k].vertex); /*访问源点Vk*/ visited[k]=TRUE; cq[r]=k; /*Vk已访问，将其入队。注意，实际上是将其序号入队*/ while(cq[f]!=-1) { // 队列非空则执行 i=cq[f]; f=f+1; /*Vi出队*/ p=G->adjlist[i].firstedge; /*取Vi的边表头指针*/ while(p) { /*依次搜索Vi的邻接点Vj（令p->adjvex=j）*/ if(!visited[p->adjvex]) { /*若Vj未访问过*/ printf("%c ",G->adjlist[p->adjvex].vertex); /*访问Vj*/ visited[p->adjvex]=TRUE; r=r+1; cq[r]=p->adjvex; /*访问过的Vj入队*/ } p=p->next; /*找Vi的下一个邻接点*/ } } /*endwhile*/ } 3.2邻接矩阵的遍历 #define MAXLEN 10 #include #define FALSE 0 #define TRUE 1 #define Error printf #define QueueSize 30 typedef struct { char vexs[MAXLEN]; int edges[MAXLEN][MAXLEN]; int n,e; }MGraph; int visited[10]; void CreateMGraph(MGraph *G); void DFSTraverseM(MGraph *G); void BFSTraverseM(MGraph *G); void DFSM(MGraph *G,int i); void BFSM(MGraph *G,int i); typedef struct { int front; int rear; int count; int data[QueueSize]; }CirQueue; void InitQueue(CirQueue *Q) { Q->front=Q->rear=0; Q->count=0; } int QueueEmpty(CirQueue *Q) { return Q->count=QueueSize; } int QueueFull(CirQueue *Q) { return Q->count==QueueSize; } void EnQueue(CirQueue *Q,int x) { if (QueueFull(Q)) Error("Queue overflow"); else { Q->count++; Q->data[Q->rear]=x; Q->rear=(Q->rear+1)%QueueSize; } } int DeQueue(CirQueue *Q) { int temp; if(QueueEmpty(Q)) { Error("Queue underflow"); return NULL; } else { temp=Q->data[Q->front]; Q->count--; Q->front=(Q->front+1)%QueueSize; return temp; } } /*建立矩阵*/ void CreateMGraph(MGraph *G) { int i,j,k; char ch1,ch2; printf("\t\t请输入顶点数和边数(输入
格式
pdf格式笔记格式下载页码格式下载公文格式下载简报格式下载
为:顶点数,边数):\n\t\t"); scanf("%d,%d",&(G->n),&(G->e)); printf("\t\t请输入顶点信息(顶点号)每个顶点以回车作为结束:\n"); for(i=0;in;i++) { getchar(); printf("\t\t"); scanf("%c",&(G->vexs[i])); } for(i=0;in;i++) for(j=0;jn;j++) G->edges[i][j]=0; printf("\t\t请输入每条边对应的两个顶点的序号(输入格式为:i,j):\n"); for(k=0;ke;k++) { getchar(); printf("\t\t请输入第%d条边的顶点序号：",k+1); scanf("%c,%c",&ch1,&ch2); for(i=0;ch1!=G->vexs[i];i++); for(j=0;ch2!=G->vexs[j];j++); G->edges[i][j]=1; } } /*矩阵DFS搜索*/ void DFSTraverseM(MGraph *G) { int i; for(i=0;in;i++) visited[i]=FALSE; for(i=0;in;i++) if(!visited[i]) DFSM(G,i); } void DFSM(MGraph *G,int i) { int j; printf("\t\t深度优先遍历结点: 结点%c\n",G->vexs[i]); visited[i]=TRUE; for(j=0;jn;j++) if(G->edges[i][j]==1&&!visited[j]) DFSM(G,j); } /*矩阵BFS搜索*/ void BFSTraverseM(MGraph *G) { int i; for (i=0;in;i++) visited[i]=FALSE; for (i=0;in;i++) if (!visited[i]) BFSM(G,i); } void BFSM(MGraph *G,int k) { int i,j; CirQueue Q; InitQueue(&Q); printf("\t\t广度优先遍历结点: 结点%c\n",G->vexs[k]); visited[k]=TRUE; EnQueue(&Q,k); while (!QueueEmpty(&Q)) { i=DeQueue(&Q); for (j=0;jn;j++) if(G->edges[i][j]==1&&!visited[j]) { printf("\t\t广度优先遍历结点:%c\n",G->vexs[j]); visited[j]=TRUE; EnQueue(&Q,j); } } } /*主函数*/ void main() { MGraph *G,a; char ch1; int i,j,ch2; G=&a; ch1='y'; while(ch1=='y'||ch1=='Y') { printf("\n\n\n\n\n\t\t图 子 系 统\n"); printf("\t\t*****************************************\n"); printf("\t\t* 1-------输入邻接矩阵 *\n"); printf("\t\t* 2-------矩阵DFS遍历 *\n"); printf("\t\t* 3-------矩阵BFS遍历 *\n"); printf("\t\t* 0-------退 出 *\n"); printf("\t\t*****************************************\n"); printf("\t\t请选择菜单号(0--3):"); scanf("%d",&ch2); getchar(); switch(ch2) { case 1:CreateMGraph(G); printf("\t\t\t图的邻接矩阵存储建立完毕.\n"); break; case 2:DFSTraverseM(G);break; case 3:BFSTraverseM(G);break; case 0:ch1='n';break; default:printf("\t\t输入错误！请重新输入！\n"); } } } /* 主函数 */ void main() { int i; ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph)); CreatALGraph(G); printf("邻接表DFS遍历: "); DFS(G); printf("\n"); printf("邻接表BFS遍历: "); BFS(G,3); printf("\n"); } 四、结果 4.1 邻接表原图： 矩阵原图： 0 0 0 1 0 1 0 0 0 4.2运行界面： 4.3运行结果 总结 我们选择了图的遍历这个题目，一开始以为蛮简单的，但做起来就不是一回事了。在经过几个礼拜的努力后，尽管还是没有解决所有的问题，可我们对于图的遍历有了更深层次的了解。在编程过程中，我们遇到很多困难，比如，在单个程序运行顺利的情况下，程序合起来就运行出错，这就需要耐心去解决。在此次设计中，最终我们还是不能将两端程序连接起来，对此表示很遗憾，希望老师多多谅解。 参考文献 《数据结构》 作者：田鲁怀
浙公网安备 33021202002483