- 浏览: 286568 次
- 性别:
- 来自: 武汉
文章分类
最新评论
-
zh1159007904:
大侠,你这个程序的递归部分看不懂,能不能麻烦解释一下递归的思路 ...
求21位水仙花数(C语言实现) -
shenma_IT:
我是一楼的神马_CS哦 再次表示感谢!!
求21位水仙花数(C语言实现) -
shenma_IT:
好 万分感谢 !!
求21位水仙花数(C语言实现) -
Touch_2011:
shenma_CS 写道你好! 我看了你的代码 有好多让我佩服 ...
求21位水仙花数(C语言实现) -
Touch_2011:
乘法是模拟数学上两个数相乘,但在处理进位方面可能有点不同。比如 ...
求21位水仙花数(C语言实现)
/* * 邻接表存储的有向图的基本操作 */ #include<stdio.h> #include<stdlib.h> #define MAX_VERTEX 20 typedef char VertexType; //用数组vertex按序存放遍历的各个顶点,广度遍历时看成队列,深度遍历时看成栈 VertexType vertex[MAX_VERTEX]; //图的边的定义 typedef struct EdgeNode { int nextToVertex; //相邻顶点 struct EdgeNode * nextEdge; //下一条边 }EdgeNode,*PEdgeNode; //图的顶点的定义 typedef struct { VertexType vertex; //顶点信息 PEdgeNode firstEdge; //第一条边(出度) }VertexNode,*PVertexNode; //图的定义 typedef struct { int vertexNum; //顶点个数 int edgeNum; //边的个数 VertexNode vertexNode[MAX_VERTEX]; //顶点信息数组 }GraphList,*PGraphList; //建立有向图 void createGraph(PGraphList pGraph) { int i,from,to; PEdgeNode p,pEdge; printf("请输入有向图顶点个数:\n"); scanf("%d",&pGraph->vertexNum); for(i=0;i<pGraph->vertexNum;i++){ pGraph->vertexNode[i].vertex='a'+i; pGraph->vertexNode[i].firstEdge=NULL; } printf("请输入有向图边的个数:\n"); scanf("%d",&pGraph->edgeNum); printf("请输入有向图边的信息:\n"); printf("起始点 终点\n"); for(i=0;i<pGraph->edgeNum;i++){ scanf("%d%d",&from,&to); pEdge=(PEdgeNode)malloc(sizeof(EdgeNode)); pEdge->nextEdge=NULL; pEdge->nextToVertex=to; p=pGraph->vertexNode[from].firstEdge; if(!p) pGraph->vertexNode[from].firstEdge=pEdge; else{ while(p->nextEdge){ p=p->nextEdge; } p->nextEdge=pEdge; } } } //求指定顶点 VertexType getVertexByIndex(PGraphList pGraph,int index) { return pGraph->vertexNum==0?'0':pGraph->vertexNode[index].vertex; } //求第一个顶点 VertexType getFirstVertex(PGraphList pGraph) { return pGraph->vertexNum==0?'0':pGraph->vertexNode[0].vertex; } //求图中顶点index的下一个顶点 VertexType getVertexAfterIndex(PGraphList pGraph,int index) { return (index>=0 && index+1 < pGraph->vertexNum) ? pGraph->vertexNode[index+1].vertex : '0'; } //求第一个与顶点index相邻的顶点 VertexType getVertexNextIndex(PGraphList pGraph,int index) { if(index>=0&&index<pGraph->vertexNum){ if(pGraph->vertexNode[index].firstEdge) return pGraph->vertexNode[pGraph->vertexNode[index].firstEdge->nextToVertex].vertex; } return '0'; } //根据顶点信息寻返回顶点在图中的位置 int findVertex(PGraphList pGraph,VertexType vertex) { int i; for(i=0;i<pGraph->vertexNum;i++) if(pGraph->vertexNode[i].vertex==vertex) return i; return -1; } //返回任一顶点的出度 int getArcsNum(PGraphList pGraph,int index) { int k=0; PEdgeNode p=pGraph->vertexNode[index].firstEdge; if(index>=0&&index<pGraph->vertexNum){ while(p){ k++; p=p->nextEdge; } return k; } return -1; } //判断任意两个顶点之间是否有边 int connected(PGraphList pGraph,int from,int to) { PEdgeNode p=pGraph->vertexNode[from].firstEdge; if((from<0 || from>=pGraph->vertexNum) || (to<0 && to>=pGraph->vertexNum)) return 0; while(p){ if(p->nextToVertex==to) return 1; p=p->nextEdge; } return 0; } //广度优先遍历 void breadthTraverse(PGraphList pGraph) { int i,k; int flag[MAX_VERTEX];//记录顶点的下标 int front,rear; PEdgeNode p; front=rear=0; for(i=0;i<MAX_VERTEX;i++) flag[i]=-1; //从第一个顶点开始 front=rear=0; vertex[rear++]=pGraph->vertexNode[0].vertex; flag[0]=0; while(front<rear){ i=flag[front]; p=pGraph->vertexNode[i].firstEdge; while(p){ for(k=0;k<rear;k++)//判断此顶点是否在队列中 if(flag[k]==p->nextToVertex) break; if(k==rear){ vertex[rear]=pGraph->vertexNode[p->nextToVertex].vertex; flag[rear++]=p->nextToVertex; } p=p->nextEdge; } front++; } } //深度优先遍历 void depthTraverse(PGraphList pGraph) { int i,top=0,k,m; int flag[MAX_VERTEX];//记录顶点的下标 PEdgeNode p; for(i=0;i<MAX_VERTEX;i++) flag[i]=-1; //从第一个顶点开始 vertex[top++]=pGraph->vertexNode[0].vertex; flag[0]=0; while(top>0 && top<pGraph->vertexNum){ if(!p)//退栈,从上一个顶点开始 i=flag[--m]; else m=i=flag[top-1]; p=pGraph->vertexNode[i].firstEdge; while(p){ for(k=0;k<top;k++) if(flag[k]==p->nextToVertex) break; if(k==top){ vertex[top]=pGraph->vertexNode[p->nextToVertex].vertex; flag[top++]=p->nextToVertex; break; } p=p->nextEdge; } } } //测试 void main() { int i; GraphList graph; createGraph(&graph); printf("指定顶点:%c\n",getVertexByIndex(&graph,0)); printf("第一个顶点:%c\n",getFirstVertex(&graph)); printf("index的下一个顶点:%c\n",getVertexAfterIndex(&graph,0)); printf("第一个与顶点index相邻的顶点:%c\n",getVertexNextIndex(&graph,0)); printf("根据顶点信息寻返回顶点在图中的位置:%d\n",findVertex(&graph,'b')); printf("返回任一顶点的出度:%d\n",getArcsNum(&graph,0)); printf("判断任意两个顶点之间是否有边:%d\n",connected(&graph,0,1)); printf("-----------广度优先遍历-----------------\n\n"); breadthTraverse(&graph); for(i=0;i<graph.vertexNum;i++) printf("%-3c",vertex[i]); printf("\n\n-------深度优先遍历------------------\n\n"); depthTraverse(&graph); for(i=0;i<graph.vertexNum;i++) printf("%-3c",vertex[i]); printf("\n\n"); }
- 源代码.zip (1.9 KB)
- 下载次数: 15
发表评论
-
二叉查找树(二叉排序树)的详细实现
2011-10-22 13:18 1303博客地址: http://blog.csdn.net/tou ... -
确定参赛者名单(C语言实现)
2011-07-10 10:39 1572/* 2011第二届国信蓝点 ... -
整数划分(C语言实现)
2011-07-10 10:35 4967/* 整数的划分问题。 如,对于正整数n=6,可以分划为 ... -
几种全排列的算法(C语言实现)
2011-07-07 00:14 6312/* * 几种排列组合的算法 */ #incl ... -
Playfire加密算法(C语言实现)
2011-07-06 10:13 2975这是C语言选拔赛最后一题,题目如下: /* ... -
浅析贪心算法
2011-07-05 17:46 13701.基本思路: a.顾名思义,贪心算法总是作出在当前看来最好 ... -
浅析动态规划算法
2011-07-05 15:30 17781、 ... -
浅析递归
2011-07-02 20:40 20401.递归的思想: 设计一个递归函数,明确这个递归函数的定义, ... -
浅析分治法
2011-07-02 13:54 22621、分治法思想: 将一个难以直接解决的大问题,分割成一些规模 ... -
浅析回溯算法
2011-06-29 22:48 29021、回溯法的基本思想 (1)在确定解空间的组织结构 ... -
高精度计算
2011-06-27 14:06 10301.大整数加法 2.大整数减法 3.大整数乘法 4.大整 ... -
浅析模拟算法
2011-06-27 07:58 18651.描述 有些问题难以找到公式或规律来解决,可以按 ... -
农夫过河的四种解法
2011-06-25 14:21 6918/* * 题目描述:有一个农夫,带着一只狼、一只羊、一颗白 ... -
各种排序算法的实现(C语言实现)
2011-06-17 22:31 1707/* * 各种基本排序算法实现(以由小到大为例) */ ... -
二叉查找树(C语言实现)
2011-06-15 23:47 2563/* * 构造一颗二叉查找树,实现树的插入、删除等基本操作 ... -
哈希表查找(C语言实现)
2011-06-15 13:38 11425/* * 题目:给定一个全部由字符串组成的字典,字符串全部 ... -
索引查找之英语词典(C语言实现)
2011-06-14 22:48 5512/* * 题目:英语词典。所有的单词存放在dictionary ... -
求最短路径的两种算法(C语言实现)
2011-06-11 11:23 28384求这个有向网中任意两点的最短路径 /* ... -
拓扑排序(C语言实现)
2011-06-10 23:09 3150对这个有向图进行拓扑排序 /* * 拓扑排序(采用邻 ... -
最小生成树(C语言实现)
2011-06-10 21:30 8836求这个网的最小生成树 /* * 普里姆算法和克鲁斯卡 ...
相关推荐
c语言写的有向图的邻接表的实现,通过使用图的邻接表实现图的存储结构存储。
里面有数据结构的一些详细信息,有关邻接表的广度和深度的测试以及怎么用C语言编写邻接表
无向图的邻接矩阵存储及输出无向图的邻接矩阵存储及输出
一学期数据结构的代码作业,基本上涵盖了课本上面所有算法的C语言代码实现,压缩包无密码 2019/11/03 21:43 1,478 BF_KMP.cpp 2019/11/03 21:22 2,664 KMP.cpp 2019/10/24 18:49 3,956 LinkStack.cpp 2019/11/21 ...
该算法是用C#实现的,要用Visual Studio2005
判别以邻接表方式存储的有向图中是否存在由顶 点vi到顶点vj的路径(i≠j)。 注意:算法中涉及 的图的基本操作必须在此存储结构上实现。 7.23③ 同7.22题要求。试基于图的广度优先搜索策略写一算法。 7.24③ 试利用栈...
要求采用邻接矩阵作为无向图的存储结构,邻接表作为有向图的存储结构,完成无向图和有向图的建立,并对建立好的图进行深度和广度优先遍历。具体实现要求: 1. 通过键盘输入图的顶点和边信息,分别构造一个无向图的...
本文实例讲述了C++实现图的邻接表存储和广度优先遍历方法。分享给大家供大家参考。具体如下: 示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6...
我做这个作业的时候发现没有可以参考的代码,于是把自己写的发出来咯。这是一个完整的程序,包括结构定义、初始化存储空间、构造邻接表和输入控制
实现有向图的数据结构,有向图的邻接表存储结构
以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 [实现提示] 设图的结点不超过30个,每个结点用一个编号表示(如果...
c代码-邻接矩阵建立图
7.4.2 有向图的强连通分量 7.4.3 最小生成树 7.4.4 关节点和重连通分量 7.5 有向无环图及其应用 7.5.1 拓扑排序 7.5.2 关键路径 7.6 最短路径 7.6.1 从某个源点到其余各顶点的最短路径 7.6.2 每一对顶点之间的最短...
1.7.3 邻接表的定义 1.7.4.图的创建 1.7.5 图的遍历(1)——深度优先搜索 1.7.6 图的遍历(2)——广度优先搜索 1.7.7 实例与分析 第2章 常用的查找与排序方法 2.1 顺序查找 2.2 折半查找 2.3 排序的概述 2.4 直接...
7.4.2 有向图的强连通分量 7.4.3 最小生成树 7.4.4 关节点和重连通分量 7.5 有向无环图及其应用 7.5.1 拓扑排序 7.5.2 关键路径 7.6 最短路径 7.6.1 从某个源点到其余各项点的最短路径 7.6.2 每一对顶点之间的最短...
7.4.2 有向图的强连通分量 7.4.3 最小生成树 7.4.4 关节点和重连通分量 7.5 有向无环图及其应用 7.5.1 拓扑排序 7.5.2 关键路径 7.6 最短路径 7.6.1 从某个源点到其余各顶点的最短路径 7.6.2 每一对顶点之间的最短...
7.4.2 有向图的强连通分量 7.4.3 最小生成树 7.4.4 关节点和重连通分量 7.5 有向无环图及其应用 7.5.1 拓扑排序 7.5.2 关键路径 7.6 最短路径 7.6.1 从某个源点到其余各顶点的最短路径 7.6.2 每一对顶点之间的最短...
一、单选题(每题1分,共16分) ( C )1. 在一个图中,所有顶点的度数之和等于图的边数...2. 有向图G用邻接表矩阵存储,其第i行的所有元素之和等于顶点i的 出度 。 3. 如果n个顶点的图是一个环,则它有 n 棵生成树。
*3.4.1 输入流与输出流的基本操作 *3.4.2 在输入流与输出流中使用控制符 3.4.3 用getchar和putchar函数进行字符的输入和输出 3.4.4 用scanf和printf函数进行输入和输出 3.5 编写顺序结构的程序 3.6 关系运算和逻辑...