嵌入式课程设计报告之数据排序

PAGEPAGE16嵌入式设计报告题目:数据排序过程演示黄志君通信060706221066谢克强通信060706221026指导老师：闻跃2009设计题目：数据排序演示过程用键盘随机输入6个数值为0-9的数字，用冒泡排序法将它们按从小到大的方式排序，并显示排序过程和最终结果。设计要求和目标（1）在LCD屏幕上提示用户用矩阵键盘输入6个数字，输入过程显示在屏幕上，同时从左到右显示在扩展版的数码管上。输入完成后，屏幕提示按“确认”键开始排序过程。一定要输满6个数字才能排序；输入过程中若按“取消”键则清除所有输入结果，回到待机状态。（2）当输入完6个数字，按下“确认”键后，程序开始排序；在排序过程中在数码管上显示中间结果，每当数字顺序发生变化时，显示在数码管上停留3秒或有按键按下后才进行下一步计算。（3）排序结束后，在数码管上应该从左到右显示数值从小到大排列的6个数字，同时LED发光管闪烁表示排序完成。按取“消键”清除结果显示回到待机状态，提示下一次输入和排序操作过程。（4）在排序过程中，若按下“取消”键，在LCD屏幕上提示是否要取消排序操作，按“确定”减中断排序，清除显示；按其他键继续排序过程。(5)在屏幕上显示出排序的所有中间结果，统计位置交换次数。(6)用LCD屏幕上的图形菜单，让使用者在几种排序方法中选择一种进行排序过程演示。三、排序算法说明1、冒泡排序

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比较a[3]与a[4]，以此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。

优点：稳定，比较次数已知；

缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。2、选择排序

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[1]与a[3]的值，若a[1]大于a[3]则交换两者的值，否则不变。再比较a[1]与a[4]，以此类推，最后比较a[1]与a[n]的值。这样处理一轮后，a[1]的值一定是这组数据中最小的。再将a[2]与a[3]~a[n]以相同方法比较一轮，则a[2]的值一定是a[2]~a[n]中最小的。再将a[3]与a[4]~a[n]以相同方法比较一轮，以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。

优点：稳定，比较次数与冒泡排序一样，数据移动次数比冒泡排序少；

缺点：相对之下还是慢。3、插入排序

已知一组升序排列数据a[1]、a[2]、……a[n]，一组无序数据b[1]、b[2]、……b[m]，需将二者合并成一个升序数列。首先比较b[1]与a[1]的值，若b[1]大于a[1]，则跳过，比较b[1]与a[2]的值，若b[1]仍然大于a[2]，则继续跳过，直到b[1]小于a数组中某一数据a[x]，则将a[x]~a[n]分别向后移动一位，将b[1]插入到原来a[x]的位置这就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若无数组a，可将b[1]当作n=1的数组a）

优点：稳定，快；

缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。4、希尔排序

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n不大是，插入排序的效果很好。首先取一增量d(d<n)，将a[1]、a[1+d]、a[1+2d]……列为第一组，a[2]、a[2+d]、a[2+2d]……列为第二组……，a[d]、a[2d]、a[3d]……列为最后一组以次类推，在各组内用插入排序，然后取d'<d，重复上述操作，直到d=1。

优点：快，数据移动少；

缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。原理说明和模块主要用到的模块数据输入模块:主要完成要排序数据的输入;LED显示模块:主要完成数据的输入以及排序过程在数码过程上的显示;LCD显示模块:主要完成数据排序过程,操作提示等内容的显示;扫描键盘模块:主要完成对键盘的扫描,通过得到不的按键转到相应的处理程序;排序及主控制模块:主要完成数据排序以及显示控制;延时及动态刷新模块:主要用来去除键盘抖动和刷新数码管显示.程序各部分模块关系初始化硬件资源初始化硬件资源数据输入选择排序方法排序以及显示控制LED显示LCD显示按键扫描动态刷新操作说明从键盘输入六个数,A键清除,重新输入输入后提示选择排序方法在排序过程中可以按A键可以取消当前排序排序完成后LED灯闪,LCD提示排序完成,按任意键继续下一次排序过程.流程图与各模块代码说明查询按键有键按下返回开始查询按键有键按下返回开始硬件初始化LCD提示输入数据是否取消输入将数据输入缓存选择排序方法冒泡法选择法插入法希尔法返回扫描键盘是否开始排序数据是否需要交换返回待机下一次循环排序LCD显示LCD显示延时记录交换次数排序是否完成结束排序LCD显示排序次数LED显示最后结果LED闪灯查询到有取消键按下LCD提示是否结束返回排序程序返回待机状态五、源程序1、主程序部分#include"71x_lib.h"#include"ledkey.h"#include"lcdlib.h"#include"rt_fp.h"#include"stdlib.h"#include"stdio.h"#pragmaimport(__use_no_semihosting_swi)#defineEMI_BCON0(*(volatileu16*)0x6C000000)#defineEMI_BCON1(*(volatileu16*)0x6C000004)#defineEMI_BCON2(*(volatileu16*)0x6C000008)#defineEMI_BCON3(*(volatileu16*)0x6C00000C)externvoid_delay(u32);voidrefresh(void);voidwait(void);voidlcd_disp(int,int,int);voidover(void);//floatingpointsupportingvoid__rt_raise(intsig,inttype){ staticinta,b; a=sig; b=type;}//chartch[64];u32pts[64]={10,0,16,7,30,4,23,13,27,25,20,20, 8,29,10,20,0,16,11,13,10,0};//np=11,astaru32pts1[64];intdata[6];intlabel=0;voidMain(void){inti=0,j,n,k,tem1,tem2,method; intin_count,count=0,tmp,min,index,increment,d; chars[2]={0,0}; #ifdefDEBUG debug();#endif EMI_BCON0=0x803D; EMI_BCON2=0x803D; EMI_BCON3=0x803D; GPIO_Config(GPIO2,0x00FF,GPIO_AF_PP); //enableCS0-CS3 EMI_Config(0,EMI_ENABLE|EMI_WAITSTATE(3)|EMI_SIZE_16); //enablebank1>=4waits EMI_Config(1,EMI_ENABLE|EMI_WAITSTATE(2)|EMI_SIZE_16); //enablebank1>=4waits EMI_Config(3,EMI_ENABLE|EMI_WAITSTATE(3)|EMI_SIZE_16); //enablebank1>=4waits//configthegpio0,LED5~8 GPIO_Config(GPIO0,0x00F0,GPIO_OUT_PP); //turnonall4ledlights GPIO_WordWrite(GPIO0,GPIO_WordRead(GPIO0)|(0x0f<<4)); EnableLedKey(); _fp_init(); //初始化浮点运算,在rt_fp.h中声明 for(i=0;i<6;i++) SetLedDigit(i,0); //LCD初始化 LCD_Init();//test2-Dgraphst0:gClearScreen(0); gSetColor(LCD_YELLOW); gSetBkColor(LCD_GREEN); gTextOut("数据排序过程演示",70,80); gTextOut("黄志君06221066",70,150); gTextOut("谢克强06221026",70,230); gTextOut("任课老师闻跃",70,310); s[0]=0; s[1]=0; for(i=0;i<10;i++) for(j=0;j<100;j++) _delay(200); st1:gClearScreen(0); gTextOut("请您输入要排序的数据",45,70); for(i=0;i<6;i++) data[i]=20; in_count=0; while(in_count<6) { refresh(); n=GetKey(); if(n<0){ //如果没有按键 k=-1; //清除上一次按键值 continue; //下一个循环 } if(n==k) continue; //若与上次按键相同，不做处理 k=n; if(n>9&&n!=10)continue; gTextOut("如果需要重新输入请按A",40,100); if(n==10)gotost1; else{ data[in_count]=n; in_count++; for(i=0;i<in_count;i++) lcd_disp(in_count,88,130); } } gSetColor(LCD_BLUE); gSetBkColor(LCD_WHITE); gTextOut("数据输入完毕",75,60); gTextOut("冒泡法排序请按1",70,90); gTextOut("选择法排序请按2",70,120); gTextOut("插入法排序请按3",70,150); gTextOut("希尔法排序请按4",70,180); gTextOut("若要取消操作按A",70,210); do { n=GetKey(); if(n==10) {gotost0;} elseif(n==1|n==2|n==3|n==4|n==5) {method=n; break; } elserefresh(); }while(1);gClearScreen(0);/*冒泡法排序*/if(method==1){gTextOut("冒泡法排序开始，A键退出排序",15,30);gTextOut("您输入的原始数据为：",20,60); for(i=0;i<6;i++) { s[0]=data[i]+48; gTextOut(s,10*i+155,60); } gTextOut("以下是中间结果，其他任意键加速显示",2,90);count=0;for(i=0;i<6;i++)//冒泡法排序，外层循环 for(j=0;j<6-i;j++)//冒泡法排序，内层循环 { if(data[j]>data[j+1])//相邻比较若大则交换 { wait();//延时 tmp=data[j];//交换 data[j]=data[j+1]; data[j+1]=tmp; if(label==1)//扫描程序发现取消键被按下 { gTextOut("您确定要退出程序么？",50,250);gTextOut("按A退出程序，其他键继续",30,280);while(1){refresh();//动态刷新六位数码管显示，以保证数码管能动态显示交换的数据 n=GetKey();//获取按键值 if(n<0) { //如果没有按键 k=-1; //清除上一次按键值 continue; //下一个循环 } if(n==k) continue; //若与上次按键相同，不做处理 k=n; if(n==10)gotost0;//用户确定退出程序，返回待机状态 else//用户要求继续排序 { gRectFill(0,150,240,320,0);//背景填充，清除语言提示 label=0; _delay(50000); break;//返回，继续排序 }} } count++;//计数值加一 if(count<=6) lcd_disp(6,10,count*20+100);//调用LCD显示程序，分栏显示 elseif(count>6&&count<=12) lcd_disp(6,90,(count-6)*20+100); elselcd_disp(6,170,(count-12)*20+100); } }}if(count>9){tem1=1;tem2=count-10;s[0]=tem1+48;s[1]=tem2+48;}else{s[0]=count+48;s[1]=0;}if(count>6)count=6;gTextOut("排序结束,交换了",50,count*20+130);gTextOut(s,160,count*20+130);gTextOut("次。",180,count*20+130);gTextOut("按任意键返回待机状态，再次排序",15,count*20+160);over();gotost0;/*选择法排序*/if(method==2){label=0;gTextOut("选择法排序开始，A键退出排序",15,30);gTextOut("您输入的原始数据为：",20,60); for(i=0;i<6;i++) { s[0]=data[i]+48; gTextOut(s,10*i+155,60); } gTextOut("以下是中间结果，其他任意键加速显示",2,90);count=0;for(i=0;i<6;i++)//选择法排序，外层循环{ min=data[i]; index=i; for(j=i+1;j<6;j++)//选择法排序，内层循环 { if(data[j]<min)//找出本次循环中最小的数，标记位置 { min=data[j]; index=j; } } if(index!=i)//找到当前最小的数 { wait();//延时 tmp=data[i];//交换 data[i]=data[index]; data[index]=tmp; if(label==1)//扫描程序发现取消键被按下 { gTextOut("您确定要退出程序么？",50,250);gTextOut("按A退出程序，其他键继续",30,280);while(1){refresh();//动态刷新六位数码管显示，以保证数码管能动态显示交换的数据 n=GetKey();//获取按键值 if(n<0) { //如果没有按键 k=-1; //清除上一次按键值 continue; //下一个循环 } if(n==k) continue; //若与上次按键相同，不做处理 k=n; if(n==10)gotost0;//用户确定退出程序，返回待机状态 else//用户要求继续排序 { gRectFill(0,150,240,320,0);//背景填充，清除语言提示 label=0; _delay(50000); break;//返回，继续排序 }}} count++;//计数值加一lcd_disp(6,88,count*20+100);//调用LCD显示程序 }}gTextOut("排序结束,交换了",50,count*20+130);gTextOut(s,160,count*20+130);gTextOut("次。",180,count*20+130);gTextOut("按任意键返回待机状态，再次排序",15,count*20+160);over();gotost0;}/*插入法排序*/if(method==3){gTextOut("插入法排序开始，A键退出排序",15,30);gTextOut("您输入的原始数据为：",20,60); for(i=0;i<6;i++) { s[0]=data[i]+48; gTextOut(s,10*i+155,60); }gTextOut("以下是中间结果，其他任意键加速显示",2,90);count=0;for(i=1;i<n;i++){tmp=data[i];//用tmp记录data[i]for(j=i-1;j>=0;j--)//逐个向前寻找插入点{if(tmp>data[j])//找到,跳出循环break;else//没找到,将前一个数据后移data[j+1]=data[j];}data[j+1]=tmp;}if(label==1)//扫描程序发现取消键被按下 { gTextOut("您确定要退出程序么？",50,250);gTextOut("按A退出程序，其他键继续",30,280);while(1){refresh();//动态刷新六位数码管显示，以保证数码管能动态显示交换的数据 n=GetKey();//获取按键值 if(n<0) { //如果没有按键 k=-1; //清除上一次按键值 continue; //下一个循环 } if(n==k) continue; //若与上次按键相同，不做处理 k=n; if(n==10)gotost0;//用户确定退出程序，返回待机状态 else//用户要求继续排序 { gRectFill(0,150,240,320,0);//背景填充，清除语言提示 label=0; _delay(50000); break;//返回，继续排序 }}} count++;//计数值加一 if(count<=6) lcd_disp(6,10,count*20+100);//调用LCD显示程序，分栏显示 elseif(count>6&&count<=12) lcd_disp(6,90,(count-6)*20+100); elselcd_disp(6,170,(count-12)*20+100);}/*希尔排序*/if(method==4){gTextOut("插入法排序开始，A键退出排序",15,30);gTextOut("您输入的原始数据为：",20,60); for(i=0;i<6;i++) { s[0]=data[i]+48; gTextOut(s,10*i+155,60); }gTextOut("以下是中间结果，其他任意键加速显示",2,90);count=0;increment=n;/*增量初值，不妨设n>0*/do{increment=increment/3+1;/*求下一增量*/for(i=d+1;i<=n;i++)/*将R[d+1．．n]分别插入各组当前的有序区*/if(data[i]<data[i-d]){data[0]=data[i];j=i-d;/*R[0]只是暂存单元，不是哨兵*/do{/*查找R[i]的插入位置*/data[j+d]=data[j];/*后移记录*/j=j-d;/*查找前一记录*/}while(j>0&&data[0]<data[j]);data[j+d]=data[0];/*插入R[i]到正确的位置上*/}}while(increment>1);if(label==1)//扫描程序发现取消键被按下 { gTextOut("您确定要退出程序么？",50,250);gTextOut("按A退出程序，其他键继续",30,280);while(1){refresh();//动态刷新六位数码管显示，以保证数码管能动态显示交换的数据 n=GetKey();//获取按键值 if(n<0) { //如果没有按键 k=-1; //清除上一次按键值 continue; //下一个循环 } if(n==k) continue; //若与上次按键相同，不做处理 k=n; if(n==10)gotost0;//用户确定退出程序，返回待机状态 else//用户要求继续排序 { gRectFill(0,150,240,320,0);//背景填充，清除语言提示 label=0; _delay(50000); break;//返回，继续排序 }}} count++;//计数值加一 if(count<=6) lcd_disp(6,10,count*20+100);//调用LCD显示程序，分栏显示 elseif(count>6&&count<=12) lcd_disp(6,90,(count-6)*20+100); elselcd_disp(6,170,(count-12)*20+100);}}2、子程序部分/*延时子程序*/voidwait(void){ inti,n,k; for(i=0;i<80;i++)//循环用来延时 { refresh();//刷新数码管显示，使数码管可以动态显示 n=GetKey();//获取按键值 if(n<0){k=-1; continue; } if(n==k) continue; k=n; if(n==10)//取消键被按下，修改标志位 { label=1; return;}//返回 else//用户不想取消排序，操作继续进行 return; } return;}/*LED动态显示程序*/voidrefresh(void){ inti=0; for(i=0;i<6;i++)//将排序中间过程数据显示 { LedCodeDisp(5-i,data[i]); _delay(200); SetLedDigit(5-i,0); }}/*lcd显示子程序*/voidlcd_disp(intn,intm,intpos){ inti; chars[10]; for(i=0;i<n;i++)//将排序中间结果在LCD上分行显示 { s[0]=data[i]+48; gTextOut(s,10*i+m,pos); }} /*排序结束后处理函数*/voidover(void){inti,k,n=0;inttemp=0; while(1) { GPIO_WordWrite(GPIO0,0xffff);//使LED全亮 for(i=0;i<10;i++)//延时 { refresh(); n=GetKey();//获取按键信息 if(n<0){ k=-1; contin