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

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

1、#include#include#defineMax20//最大顶点数//顺序存储方式使用的结构体定义typedefstructvexType{chardata;intindegree;}Vex;typedefstructGraph{intvexnum;//顶点数量intarcnum;//边数Vexvex_array[Max];//存放顶点的数组intarc_array[Max][Max];//存放邻接矩阵的二维数组}Graph;//图的定义//链式存储使用的结构体定义typedefstructarcType{charvex1,

2、vex2;//边所依附的两点intarcVal;//边的权值}Arc;//边的定义typedefstructLinkType{intindex;//在顶点表的下标structLinkType*nextarc;//指向下一个顶点结点}LinkNode;//边表定义typedefstructvexNode{chardata;intadd;//在顶点数组的下表位置LinkNode*firstarc;//指向边表的第一个结点intindegree;//入度}VexNode;//顶点边定义typedefstructLGraph{VexNodevex_array[Max];//

3、顶点数组intvexnum;//图中顶点数}LGraph;/*函数功能：图的创建入口参数：图G返回值：无*/voidCreat_G(Graph*G){charv;inti=0;intj=0;G->vexnum=0;printf("输入说明。。。有权值请输入权值，无权值请输入1，无边请输入0");printf("请输入所有顶点(不超过20个，按‘#’结束输入)：");do{printf("输入第%d个顶点：",G->vexnum+1);scanf("%c",&v);G->vex_array[G->vexnum].data=v;G->vexnum++;}wh

4、ile(v!='#');G->vexnum--;printf("输入邻接矩阵（%d*%d）：",G->vexnum,G->vexnum);for(i=0;ivexnum;i++){printf("输入%c到以下各点的权值：",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",&G->arc_array[i][j]);}}printf("构建图的顶点为：");fo

5、r(i=0;ivexnum;i++){printf("%c",G->vex_array[i].data);}printf("构建图的邻接矩阵为：");for(i=0;ivexnum;i++){for(j=0;jvexnum;j++){printf("%d",G->arc_array[i][j]);}printf("");}}/*函数功能：统计各点的入度入口参数：指向图的指针*G返回值：无*/voidCount_indegree(Graph*G){inti;intj;for(j=0;jvexnum;j++){G->vex_a

6、rray[j].indegree=0;for(i=0;ivexnum;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_arra

7、y[]中的下标inttop=0;//栈的指针intbool=1;//弹栈的标准intno;//接收stack[]栈中弹出的顶点下标for(i=0;ivexnum;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->vex_array[no].data;count++;for(j=0;jvexnum;j++){if(G->arc_array[i][j]!=0){G-