各种排序算法C语言实现

《各种排序算法C语言实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、#include#include#defineMax20〃最人顶点数〃顺序存储方式使用的结构体定义typedefstructvexType{chardata;intindegree;}Vex;typedefstructGraph{intvexnum;〃顶点数量intarcnum;〃边数Vexvex_array[Max];〃存放顶点的数组intarc_array[Max][Max];〃存放邻接矩阵的二维数组JGraph;〃图的定义〃链式存储使用的结构体定义typedefstructarcType{charvexl,vex2;〃边所依附的两点int

2、arcVaI;〃边的权值}Arc;〃边的定义typedefstructLinkType{intindex;〃在顶点表的下标structUnkType*nextarc;〃指向下一个顶点结点}LinkNode;〃边表定义typedefstructvexNode{chardata;intadd;〃在顶点数组的下表位置LinkNode*firstarc;〃指向边表的第一个结点intindegree;〃入度JVexNode;〃顶点边定义typedefstructLGraph{VexNodevex_array[Max];〃顶点数组intvexnum;〃图中顶点数}LGraph;/*函数功能：图

3、的创建入口参数：图G返回值：无*/voidCreat_G(Graph*G){charv;inti=0;intj=0;G・>vexnum=0;prints输入说明…冇权值请输入权值，无权值请输入1,无边请输入0“);printf(H请输入所有顶点(不超过20个,按’#'结束输入):u);do{printf("输入第%d个顶点：”,G・>vexnum+l);scanff"%c",&v);G->vex_array[G->vexnum].data=v;G・>vexnum++;}while(v!='#');G->vexnum--;printfC*输入邻接矩阵(%d*%d)：“,G

4、・>vexnum,G・>vexnum);for(i=0;ivG・>vexnum;i++){printf("输入%c到以F各点的权值:",G->vex_array[i].data);for(j=0;jvexnum;j++){printf("<%c,%c>:",G->vex_array[i].data,G->vex_array[j].data);scanf("%d"z&G->arc_array[i][j]);printf("构建图的顶点为：H);for(i=0;ivexnum;i++){printf("%c"/G->vex_array[i].data);}p

5、rintf(-构建图的邻接矩阵为:H);for(i=0;ivexnum;i++){for(j=0;jvexnum;j++){printf("%d”,G・>arc_array[i][j]);}pnntf("");}}严函数功能：统计各点的入度入口参数：指向图的指^l*G返回值：无*/voidCountdegree(Graph*G){inti;intj；for(j=0;jvexnum;j++){G・>vex_array[j].indegree=0;for(i=0;ivexnum;i++){if(G->arc_array[i][j]!=O)G-

6、>vex_array[j].indegree++;}}}严函数功能：对邻接矩阵进行拓扑排序入口参数：指向图的指针*G返回值：无*/voidTopol_sort(Graph*G)inti,j；chartopo[Max];//存放拓扑排序的结果intcount=0;〃记录topo[冲的元索个数，便于与vexnum比较，判断是冇环图还是无环图charstack[Max];〃存放indegree=O的顶点所在vex_array[]中的卜•标inttop=0;〃栈的指针intbool=l;〃弹栈的标准intno;〃接收stack[]栈中弹出的顶点-卜•标for(i=0;ivexnum

7、;i++){if(G->vex_array[i].indegree==0){stack[top]=i;top++;}}do{if(top==-l)bool=0;else{top-;no=stack[top];topo[count]=G->vex_array[no].data;count++;for(j=0;jvG・>vexnum;j++){if(G->arc_array[i][j]1=0){G->vex_array[j].indegree--;if(G->vex_ar