各种排序算法C语言实现.docx

#include<>#include<>#defineMax20//最大顶点数//顺序存储方式使用的结构体定义typedefstructvexType{ chardata; intindegree;}Vex;typedefstructGraph{ intvexnum;//顶点数量 um;//边数 Vexvex_array[Max];//存放顶点的数组 intarc_array[Max][Max];//存放邻接矩阵的二维数组}Graph;//图的定义//链式存储使用的结构体定义typedefstructarcType{ charvex1,vex2;//边所依附的两点 intarcVal;//边的权值}Arc;//边的定义typedefstructLinkType{ intindex;//在顶点表的下标 structLinkType*nextarc;//指向下一个顶点结点}LinkNode;//边表定义typedefstructvexNode{ chardata; intadd;//在顶点数组的下表位置 LinkNode*firstarc;//指向边表的第一个结点 intindegree;//入度}VexNode;//顶点边定义typedefstructLGraph{ VexNodevex_array[Max];//顶点数组intvexnum;//图中顶点数}LGraph;/*函数功能:图的创建入口参数:图G返回值:无*/voidCreat_G(Graph*G){ charv; inti=0; intj=0; G->vexnum=0; printf("输入说明。。。有权值请输入权值,无权值请输入1,无边请输入0\n"); printf("\n请输入所有顶点(不超过20个,按‘#’结束输入):\n"); do{ printf("输入第%d个顶点:",G->vexnum+1); scanf("%c",&v); G->vex_array[G->vexnum].data=v; G->vexnum++; }while(v!='#'); G->vexnum--; printf("输入邻接矩阵(%d*%d):",G->vexnum,G->vexnum); for(i=0;i<G->vexnum;i++) { printf("输入%c到以下各点的权值:\n",G->vex_array[i].data); for(j=0;j<G->vexnum;j++) { printf("<%c,%c>:",G->vex_array[i].data,G->vex_array[j].data); scanf("%d",&G->arc_array[i][j]); } } printf("\n构建图的顶点为:\n"); for(i=0;i<G->vexnum;i++) { printf("%c",G->vex_array[i].data); } printf("\n构建图的邻接矩阵为:\n"); for(i=0;i<G->vexnum;i++) { for(j=0;j<G->vexnum;j++) { printf("%d",G->arc_array[i][j]); } printf("\n"); }}/*函数功能:统计各点的入度入口参数:指向图的指针*G返回值:无*/voidCount_indegree(Graph*G){ inti; intj; for(j=0;j<G->vexnum;j++) { G->vex_array[j].indegree=0; for(i=0;i<G->vexnum;i++) { if(G->arc_array[i][j]!=0) G->vex_array[j].indegree++; } }}/*函数功能:对邻接矩阵进行拓扑排序入口参数:指向图的指针*G返回值:无*/voidTopol_sort(Graph*G){ inti,j; chartopo[Max];//存放拓扑排序的结果 intcount=0;//记录topo[]中的元素个数,便于与vexnum比较,判断是有环图还是无环图 charstack[Max];//存放indegree=0的顶点所在vex_array[]中的下标 inttop=0;//栈的指针 intbool=1;//弹栈的标准 intno;//接收stack[]栈中弹出的顶点下标 for(i=0;i<G->vexnum;i++) { if(G->vex_array[i].indegree==0) { stack[top]=i; top++; } } do{ if(top==-1) bool=0; else { top--; no=stack[top]; topo[count]=G->v