嵌入式linux实验报告-通信0701-李春元.doc

嵌入式linux设计实验报告组号：5姓名：李春元 学号：U200713569 同组同学：李红 专业班级：通信0701 指导老师：鄢舒 项目概要名称：三种排序算法的在linux和arm上执行速度比较具体内容和实验要求：三种或三种以上排序算法在ARM Linux上执行速度的比较：例如可以随机产生1000个数，在排序过程开始前计下系统时间，结束后再计下系统时间，算出时间差即为算法执行时间，每种算法需要多重复几次取平均值。 项目分工需求分析：共同完成概要设计和详细设计：（李春元）负责整个程序的框架设计和具体函数的实现即代码注释；调试和改进：（李红）代码调试，包括调试实例的设计，功能的扩展和补充；实现：（共同完成）从visual c+调试成功，移植到linux系统下的相关改进（库的变化等等），挂载到arm9上的过程，比较三种环境下运行时间的差异。 项目需求分析由实验要求可知，首先是确定三种排序算法，这个容易解决，我们选择的是快速排序，冒泡排序，简单排序；接着是随机数的产生；然后是怎样计下系统时间，最后是怎样用系统时间来计算多次排序的平均值，这里又会涉及到数据类型的强制转换。所以要实现这些要求，包括的函数主要有：main函数，冒泡排序函数，简单排序函数，快速排序函数，排序时间计算函数。代码的框架和具体的实验代码（概要设计和详细设计）由李春元同学完成。 概要设计包括系统整体软硬件流程图，各个功能子模块的划分和描述；产生随机数快速排序冒泡排序简单排序时间统计 调试结果与改进方案工程框架/main主程序完成题目要求main/产生随即数randomnumberbeforesort=randomnumber/根据题目要求计算所需时间并比较cost1=./ TimeCost(int beforesort, int mode)cost2=.cost3=./运行时间计算double TimeCost(int beforesort, int mode)记住系统时间 Current0for iteration=1:N /N 为排序算法多次执行的次数case mode=1 sort1(int beforesort)case mode=2 sort2(int beforesort)case mode=3sort3(int beforesort)end记住系统时间 Current1cost = (Current1-Current0)/N;return cost;/排序算法，任意找三种sort1(int beforesort)/algorithm1sort2(int beforesort)/algorithm2sort3(int beforesort)/algorithm3代码完成 第一步：测试随即数函数是否正确，随机数产生由函数srand(unsigned)time( NULL ) )实现，在这代码后添加显示函数printf(thousand random numbers from 0 to 2000nn);for(i=0;iN;) /*输出显示格式的设置,每行显示14个数，共1000个数*/ for(j=0;j（冒泡排序，简单排序）。后两者基本相同。 第五步：为了更好的体现个排序算法的优劣，还加入了记录移动次数和比较次数的变量，当待排序数很多和排序次数很大时影响也会很大，所以要验证移动次数和比较次数，这个和第三步共同进行。 第六步：在linux系统上运行时要注意两者的兼容性，开始时李春元同学用了c+的输出输入流来显示输出，这在linux的编译环境下是不支持的，最后都改成了c中的printf语句以及main函数返回值不能为void。还要注意的是文件的后缀是.c。在linux上实现后，挂载到arm上再通过终端显示。实验结果同1000个数经100次排序后的平均数据A） Window 上运行结果：B） Linux上运行结果：运行时间（s）数据移动次数比较次数简单排序0.028049450500292605冒泡排序0.03004945050010838124快速排序0.019042276168218790C） （arm）终端上运行结果：运行时间（s）数据移动次数比较次数简单排序10.460049450500292605冒泡排序12.15004945050010838124快速排序7.330042276539218741存在的问题和改进的方法； 程序中并没有涉及到判断排序是否是稳定的，这是需要改进的地方，这在前面也提到了，在设计结构体typedef struct keytype key; /*定义关键字类型*/elemtype data; /*定义元素中其他数据项*/recdtype; /*定义元素结点类型*/想到了这点，但没有深入下去，其实到这里也算是做到了，只需在初始化时对data赋初始值，标记每个数据的位置，移动时整个节点一起移动，最后每个节点完整输出，看key相同但data值不同的节点相对位置是变化了，没变则是稳定的，反之不稳定。参考文献【1】数据结构（C语言版） 严蔚敏 吴伟明 编著，清华大学出版社；【2】C语言程序设计 谭浩强 著 清华大学出版社；【3】嵌入式设计及Linux驱动开发指南基于ARM 9处理器 孙天泽，袁文菊，张海峰，北京：电子工业出版社；【4】 嵌入式linux应用开发详解孙琼等 北京：人民邮电出版社；源代码#include #include #include const int N=1000; /*待排序的数据个数常量*/typedef int keytype; /*关键字数据类型定义*/typedef int elemtype;/*元素节点其他数据项数据类型定义*/typedef struct keytype key; /*定义关键字类型*/elemtype data; /*定义元素中其他数据项*/recdtype; /*定义元素结点类型*/typedef structlong int cp; /*记录比较次数*/long int mv; /*记录移动次数*/cpmv;/*r为待排序列的数组*/*n为待排序列元素的个数*/*cm用于记录关键字的比较和移动次数*/void simplesort(recdtype r,int n,cpmv * cm) /*简单选择排序法:由小到大排列*/ int i,j,k; recdtype t; for(i=0;in-1;i+) k=i; for(j=i+1;jn;j+) if(rj.keycp+;/*比较一次，比较次数加一*/ if(k!=i) t=ri;ri=rk;rk=t; cm-mv+=3;/*交换次数加3*/ int BubbleSort(recdtype r,int n,cpmv * cm) /*冒泡排序*/int i,j,count=0;int flag; for(i=1;i=i+1)if(rj.keymv+=3; /*关键字移动次数加3*/cm-cp+; /*执行if语句，比较次数加1*/j-;/*如果无记录交换发生，则退出循环*/ count+; return count;/*s为排序区间的起始点*/*t为排序区间的终止点*/void QuickSort(recdtype r,int s,int t,cpmv * cm) /*快速排序*/int low=s;int high=t;r0=rs; /*将基准记录移至r0中*/while(lowhigh)while(lowhigh & r0.keycp+; /*循环执行一次，计较次数加1*/cm-cp+; /*最后一次比较，次数加1*/if(lowmv+; /*关键字移动次数加1*/low+;while(lowhigh & rlow.keycp+; /*循环执行一次，比较次数加1*/if(low!=high) cm-cp+; /*比较次数加1*/if(lowmv+;high-; /*high指针继续向前搜索*/rlow=r0; /*low=high，将r0移动到它的终结位置*/cm-mv+;if(slow)QuickSort(r,s,high-1,cm); /*对rs到rhigh-1区间进行快速排序*/if(lowt)QuickSort(r,high+1,t,cm); /*对rhigh+1到rt区间进行快速排序*/void Restore(recdtype r,recdtype r1,int n) /*恢复原始数据,用于每次排序后*/int i;for(i=1;i=n;i+)ri=r1i;float TimeCost(recdtype* r,recdtype* r1,int N,cpmv* cm,int mode)int k=0;float cost; /程序运行所需时间 int KK=100;int i=mode;clock_t start,finish;switch(i)case 1: start=clock(); /开始时间/cout以下进行插入排序:endl;/coutendl;for(k=1;kKK;k+) simplesort(r,N,cm);Restore(r,r1,N);finish=clock(); /cost=(float)(finish-start)/KK;break;case 2:start=clock(); int count;for(k=1;kKK;k+)count=BubbleSort(r,N,cm);Restore(r,r1,N);finish=clock(); cost=(float)(finish-start)/KK; break;case 3:start=clock(); for(k=1;kKK;k+)QuickSort(r,1,N,cm);Restore(r,r1,N);finish=clock(); /终止时间 cost=(float)(finish-start)/KK; /通过终止和起始时间计算得出运行所需时间，原始单位为秒break;default:printf(* ); return cost;int main()int i,j;float cost;printf(thousand random numbers from 0 to 2000nn);for(i=0;iN;) /*输出显示格式的设置,每行显示14个数，共1000个数*/ for(j=0;j13;j+) rj+i.key=rand()%2000; r1i.key=ri.key; printf(%-6d,rj+i.key);printf(n);i=i+13; cpmv cm3;cpmv * p;/*cmpv类型指针,中间变量,记录排序的比较次数移动次数的平均值*/ srand(unsigned)time( NULL ) ); /*初始化随机发生器*/printf(thousand random numbers from 0 to 2000nn);for(i=0;iN;) /*输出显示格式的设置,每行显示14个数，共1000个数*/ for(j=0;j13;j+) rj+i.key=rand()%2000; r1i.key=ri.key; printf(%-6d,rj+i.key);printf(n);i=i+13;for(i=0;i3;i+) cmi.cp=0;cmi.mv=0;p=cm;printf(Simple Sort cost:);cost = TimeCost(r,r1,N,p,1)/10000;printf(%f,cost); /显示运行时间printf(s); printf(simple sort data:n);printf(compare number:%ld,move number:%ldn,cm0.cp,cm0.mv);Restore(r,r1,N); printf(n);p+;printf(bubble sort cost:);cost = TimeCost(r,r1,N,p,2)/10000;printf(%f,cost); /显示运行时间printf(s);printf(bubble sort data:n);printf(compare number:%ld,move num