




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 电缆外围直径误差标准
- 2024-2025学年九年级物理上册 第十二章 内能与热机 12.4 热机与社会发展教学实录 (新版)粤教沪版
- 水岸带生态维护计划
- 2025年永磁式步进电机项目合作计划书
- 2025年离合器压盘项目发展计划
- 人力资源发展规划计划
- 2025年定金担保合同
- 成功训练-简单算术(教学设计)长春版三年级下册综合实践活动
- 九年级化学下册 第八单元 金属和金属材料课题2 金属的化学性质第2课时 金属活动性顺序教学实录 (新版)新人教版
- 汽车维修行业安全意识培训
- 河北省衡水市阜城实验中学2024-2025学年高二下学期3月月考地理试题(含答案)
- 中医儿科学知到课后答案智慧树章节测试答案2025年春山东中医药大学
- 2024年四川省公务员《申论(县乡)》试题真题及答案
- 2025年度事业单位招聘考试公共基础知识模拟试卷及答案(共四套)
- 创业要点计划月历表书项目策划(25篇)
- 酒店Opera前台操作流程
- 专题07 综合性学习【知识精研】中考语文二轮复习
- 2025年江西陶瓷工艺美术职业技术学院单招职业技能测试题库1套
- 《老年肺炎临床诊断与治疗专家共识(2024年版)》临床解读
- 人教版 八年级英语下册 Unit 2 单元综合测试卷(2025年春)
- 2025年无锡商业职业技术学院高职单招高职单招英语2016-2024历年频考点试题含答案解析
评论
0/150
提交评论