嵌入式课程设计报告之数据排序.docx
- 文档编号:14301137
- 上传时间:2023-06-22
- 格式:DOCX
- 页数:25
- 大小:97.33KB
嵌入式课程设计报告之数据排序.docx
《嵌入式课程设计报告之数据排序.docx》由会员分享,可在线阅读,更多相关《嵌入式课程设计报告之数据排序.docx(25页珍藏版)》请在冰点文库上搜索。
嵌入式课程设计报告之数据排序
嵌入式设计报告
题目:
数据排序过程演示
黄志君通信060706221066
谢克强通信060706221026
指导老师:
闻跃
2009年5月11日
一、设计题目:
数据排序演示过程
用键盘随机输入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 优点: 快,数据移动少; 缺点: 不稳定,d的取值是多少,应取多少个不同的值,都无法确切知道,只能凭经验来取。 四、原理说明和模块 1、主要用到的模块 ●数据输入模块: 主要完成要排序数据的输入; ●LED显示模块: 主要完成数据的输入以及排序过程在数码过程上的显示; ●LCD显示模块: 主要完成数据排序过程,操作提示等内容的显示; ●扫描键盘模块: 主要完成对键盘的扫描,通过得到不的按键转到相应的处理程序; ●排序及主控制模块: 主要完成数据排序以及显示控制; ●延时及动态刷新模块: 主要用来去除键盘抖动和刷新数码管显示. 2、程序各部分模块关系 3、操作说明 ●从键盘输入六个数,A键清除,重新输入 ●输入后提示选择排序方法 ●在排序过程中可以按A键可以取消当前排序 ●排序完成后LED灯闪,LCD提示排序完成,按任意键继续下一次排序过程. 4、流程图与各模块代码说明 五、源程序 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); //floatingpointsupporting void__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,astar u32pts1[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-Dgraph st0: 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 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=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 { 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[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+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)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 嵌入式 课程设计 报告 数据 排序
![提示](https://static.bingdoc.com/images/bang_tan.gif)