各种排序算法C语言实现_第1页
各种排序算法C语言实现_第2页
各种排序算法C语言实现_第3页
各种排序算法C语言实现_第4页
各种排序算法C语言实现_第5页
已阅读5页,还剩15页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、#include #inelude define Max 20 最大顶点数顺序存储方式使用的结构体定义typedef struct vexTypechar data;int indegree;Vex;typedef struct Graphint vexnum; 顶点数量int arcnum; 边数Vex vex_arrayMax; 存放顶点的数组int arc_arrayMaxMax; 存放邻接矩阵的一.维数组 Graph; 图的定义链式存储使用的结构体定义typedef struct arcTypecharvexl,vex2; 边所依附的两点i nt a rcVa I;边的权值Arc; 边

2、的定义typedef struct LinkTypeint index; 在顶点表的下标struct LinkType * nextarc;指向卞一个顶点结点LinkNode; 边表定义typedef struct vexNodechar data;int add;在顶点数组的下表位置LinkNode *firstarc; 指向边表的第一个结点int indegree; 入度VexNode; 顶点边定义typedef struct LGraphVexNode vex_arrayMax; 顶点数组 i nt vexn um;图中顶点数LGraph;厂函数功能:图的创建入口参数:图G返回值:无*/

3、void Creat_G(Graph *G)char v;int i=0;int j=0;G-vex num=0;printf(输入说明。有权值请输入权值,无权值请输入1,无边请输入0n”); printf(n请输入所有顶点(不超过20个,按#结束输入):n“);doprintf(输入第 %d 个顶点:jGvexnum+l);scanf(H %c,&v);G-vex_arrayG-vexnum.data = v;G-vexnum+;while(v!=#);G-vex num;printf(”输入邻接矩阵(d * %d): ”,Gvexnum,Gvexnum);for(i=0; ivexnum;

4、 i+)printf(输入 %c 到以下各点的权值:n,G-vex_arrayi.data);for(j=0; jvex nu m; j+)printf(: ,G-vex_arrayi.data/G-vex_arrayj.data); scanf(%cT:&Garc_aiTayij);printf(n构建图的顶点为:n); for(i=0; ivexnum; i+)printf(%c ,G-vex_arrayi.data); printf(n构建图的邻接矩阵为:n); for(i=0; ivexnum; i+)for(j=0; jvexnum; j+)printf(%d ”,G-arc_arr

5、ayij);printf(”n”);/*函数功能:统计各点的入度入II参数:指向图的指针*G返回值:无*/void Count_indegree(Graph *G)int i;int j;for(j=0; jvex num; j+)G-vex_arrayj.indegree =0; for(i=0; i vex num; i+) if(G-arc_arrayij!=O)G vex_airayji ndegree+;厂函数功能:对邻接矩阵进行拓扑排序 入口参数:指向图的指针*G 返回值:无*/ void Topol_sort(Graph *G)int ij;chartopoMax; 存放拓扑排序

6、的结果int count=0; 记录topo口中的元素个数,便于与vexnum比较,判断是有环图还是无 环图char stackMax; 存放 indegree=O 的顶点所在 vex_array冲的下标int top=0; 栈的指针int bool=l; 弹栈的标准int no; 接收stack栈中弹出的顶点下标for(i=0; ivexnum; i+)if(G-vex_arrayi.indegree=O)stacktop = i;top+;doif(top=-l)bool=0;elsetop-;no 二 stacktop;topoco unt = G-vex_arrayno.data;co

7、un t+;for(j=0; jvex num; j+)if(G-arc_arrayi j!=0)Gove x_arrayj.i ndegree 一;if(G-vex_arrayj.indegree=O) stacktop = j; top+;while(bool=l);cou nt;if(count vexnum)printf(n结果:原图中有环,无法形成拓扑序列!n); elseprintf(n结果:原图的拓扑序列为:n”);for(i=0; ivex num = 0;printf(n输入说明。有权值请输入权值,无权值请输入1,无边请输入0n“);printf(Hn请输入所有顶点(不超过2

8、0个,按#结束输入)寸);doprintf(输入第 d 个顶点:Jvexnum+l); scanf( %c,&v);T- vex_a r ray T- vexn u m . d at a = v;T- vex_a r ray T- vexn u m .f i rsta rc = NULL;T-vex nu m+;while(v!=,#1);T-vex num;for(i=0; ivexnum; i+)f=l;printf(n 以顶点 %c 为始点是否有边(Y/N): ”,T-vex_arrayi);scanf(H %c:&answer);if(answer=,Y,)printfC输入以%c为始

9、点的所有终点个数:zT-vex_arrayi); scanf(,%d,&count);for(j=0; jnextarc=NULL;printf(”输入第d个顶点:“,j+1);scanf( %c,/&v);for(k=0; kvexnum; k+)if (v=T -vex_a rray k .data)p-index = k; 找到该元素,并记录下标if(f=l) 是第一个结点,放在 T-vex_arrayi.firstarc 上 T-vex_arrayi.firstarc = p;q = p;f = 0;elseqn extarc = p;q = p;phntfC创建链表为:nj;for(

10、i=0; ivexnum; i+)printf(%c ,I/T-vex_a rray i .d ata);p = T- vex_a r ray i .f i rst a rc;while(p!=NULL)printf( %c 一一,T-vex_arrayp-in dex.data); p=p-n extarc;printf(,NULLnH);厂函数功能:统计各个点的入度入II参数:指向图的指针*T返回值:无*/void Count_T_indegree(LGraph *T)int i;LinkNode *p=NULL;for(i=0; ivexnum; i+)T-vex_arrayi.i nd

11、egree = 0;for(i=0; ivexnum; i+)p = T- vex_a r ray i .f i rst a rc; while(p!=NULL)T-vex_arrayp-index.i ndegree+; p=p-n extarc;/*函数功能:拓扑排序入I I参数:指向图的指针*T返回值:无*/void L_Topol_sort(LGraph *T)int i,j;int no;int stackMax;int top=0;int topoMax;int count=O;int bool=l;LinkNode *p=NULL;for(i=0; ivexnum; i+)if(

12、T-vex_arrayi.indegree=O)stacktop = i;top+;doif(top=0) bool=0;elsetop-;no 二 stacktop;topoco unt = T-vex_arrayno.data; coun t+;p = T-vex_arrayno.firstarc; while(p!=NULL)T-vex_arrayp-i ndex.indegree-;if(T-vex_arrayp-i ndexindegree=O) stacktop = pin dex;top+;p = pn extarc;while(bool=l);/printfC 检测n“);if

13、(cou nt vex num)printf(原图有环,无法形成拓扑排序! n); elseprintf(”原图的拓扑排序为:n“);for(i=0; iarrayj+l = L-arrayj;L-arrayj+l = L-arrayj;Lx-arrayi = L-arrayi;default:printf(输入错误! n); break;while(choice=0);/include #include #define Max 20typedef struct listint arrayMax;int length;List;厂数组复制*7void Copy(Ust *L,List *Lx)

14、int i;Lx-length = L-le ngth;for(i=l; ilength; i+)厂创建顺序表拿/void Creat(List *L)int data=O;int i;L-length=l;printf(输入数据,以100为结束输入标志n”);while(data!=-100)printf(输入第%d个元素值:丄-length); scanf(,%d,&data);L-arrayL-le ngth = data;L-le ngth+;L-length = L-length-2;printf(输入的元素值为:);for(i=l; ilength; i+)printf(%d Xa

15、rrayfi);printfCXn11);/*直接插入排序*/void ZhiJieChaRu_sort(List *L)int i;int j;for(i=2; ilength; i+)if(L-arrayi arrayi-l)L-arrayO = L-arrayi;L-arrayi = L-arrayi-l;for(j=i-2; L-arrayO arrayj; j-) L-arrayj+l = L-arrayO;printf(*n直接插入法排序结果为n);for(i=l; ilength; i+)printf(%d丄airayi);printf (”n“);/*二分法排序*/void E

16、rFenFa_sort(List *L)int i;int j;int low;int high;int mid;for(i=2; ilength; i+)low = 1;high = i-1;L-arrayO = L-arrayi;while(low arrayO arraymid)high = mid -1;elselow = mid + 1;for(j=i-l; j=high+l; j_)L-arrayj+l = L-arrayj;L-arrayhigh+l = L-arrayO;printf(Hn二分法排序结果为nH);for(i=l; ilength; i+) printf(%d丄-

17、airayi);printfCV);一次增量下的希尔排序void Shell_pass(List *LJnt d)int i;int j;for(i=d+l; ilength; i+)if(L-arrayi arrayi-d)L-arrayO = L-arrayi;L-arrayi = L-arrayi-d;for(j=i-2*d; j0 & L-array0arrayj; j-)L-arrayj = L-arrayj-d;L-arrayj+d = L-array0;希尔排序void Shell_sort(List *LJnt d)int i;for(i=0; i4; i+) 一次取出d中的增

18、量值 Shell_pass(L,di);printf(n希尔排序结果为n);for(i=l; ilength; i+) printf(%d丄-airayi);printf(,nM);冒泡排序void MaoPao_sort(List *L)int i;int j;int flag=l; 问题:课件上显示为已注销的部分,但是无法排序(没有交换二?二已经 排好了)for(i=l; ilength; i+) 控制趟数/ flag=l;for(j=l; jlength-i; j+)一趟的循环,第i趟结束后就筛选出第i个最小值,所以只需从前length-i个中冒岀最小值if(L-arrayj+l arr

19、ayj)flag=O;L-array0 = L-arrayj+l;L-arrayj+l = L-arrayj; L-arrayj = L-arrayO;/ if(flag=l)/break;printf(n冒泡排序结果为n);for(i=l; ilength; i+)printf(%d丄-arrayi);printf(“n“);快速排序的一次枢轴定位int KuaiSu_sort(List *L, int low, int high) int pivotkey; 枢轴L-arrayO = L-arraylow;每次排序序列的第一个值作为枢轴,即low作为枢轴pivotkey = L-array

20、low;while(low high)while(lowhigh & pivotkeyarrayhigh) 无论是哪种退岀循坏方式,都恰好是high的位置就是枢轴位置high-;if (lowarraylow = L-arrayhigh;low+;while(low=L-arraylow)low+;if (lowarrayhigh = L-arraylow;high-;整个循环退出就得到枢轴在真正序列中的位置为low (也是high)L-arraylow = L-arrayO;/* printf(n分步排序结果为n);for(i=l; ilength; i+)printf(n%d丄-airay

21、i);prin 廿(An);*/return low;完整快速排序void KuaiSuPaiXu_sort(List *LJnt lowjnt high)int pivotloc; 接收一次枢轴定位的位置if(low high)pivotloc = KuaiSu_sort(LJow,high); /也可写为(Ljow,pivotkey-1) KuaiSuPaiXu_sort(L,low;pivotloc-l);KuaiSuPaiXu_sort(L,pivotloc+l,high); 也可写为(Lhigpivotkey-l) 简单选择排序void JianDanXuanZe_sort(List

22、 *L)int i;int j;int min;for(i=l; ilength; i+)冒泡排序的最后一个值不用参与比较min = i;for(j=i+l; jlength; j+)if(L-arrayj arraymin)min = j;if(min!=i)L-arrayO = L-arraymin;L-arraymin = L-arrayi;L-arrayi = L-arrayO;printf(n简单选择排序结果为n);for(i=l; ilength; i+)printf(%d zL-arrayi);printfCXn);2路归并排序一趟合并函数功能:将Ls.m和Lm+l.t和并为Ts

23、.t入II参数:原列表L,合并后的列表T,起始值s,中间值终点值t返回值:无void GuiBing_pass(List *L,List *TJnt s,int m,int t)int i;int j;int k=l;for(i=l,j=m+l; i=mjarrayi arrayj)T-arrayk = L-arrayi+;elseT-arrayk = L-arrayj+;while(i arrayk+ = L-arrayi+;while(jarrayk+ = L-arrayj+;2-归并排序递归分解函数功能:将Ls.t归并为T2s.t,再将T2s.t归并为Tls.tvoid GuiBing_sort(List *L,List *TlJnt sjnt t)int m;List Tx;List *T2 = &Tx;Txength = 6;if(s=t)L-arrays = T2-arrays;elsem = (s+t)/2;GuiBing_sort(L/T2/s/m);GuiBing_sort(L,T2/m+l,t);GuiBing_pass(T2,Tl/s/m/t);*/void main()int choice;int i;int d4 = 7,5,3,1;希尔排序的增量数组List L;List Lx;

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论