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

1、嵌入式设计报告题目 : 数据排序过程演示黄志君通信 0607 06221066谢克强通信 0607 06221026指导老师：闻跃2009 年 5 月 11 日23一、 设计题目：数据排序演示过程用键盘随机输入 6 个数值为 0-9 的数字，用冒泡排序法将它们按从小到大的 方式排序，并显示排序过程和最终结果。二、 设计要求和目标(1 )在LCD屏幕上提示用户用矩阵键盘输入 6个数字，输入过程显示在屏幕上， 同时从左 到右显示在扩展版的数码管上。输入完成后，屏幕提示按“确认”键开始排序过程。一定要 输满 6 个数字才能排序；输入过程中若按“取消”键则清除所有输入结果，回到待机状态。( 2)当输入

2、完 6 个数字，按下“确认”键后，程序开始排序；在排序过程中在数码管上显 示中间结果， 每当数字顺序发生变化时， 显示在数码管上停留 3 秒或有按键按下后才进行下 一步计算。(3)排序结束后，在数码管上应该从左到右显示数值从小到大排列的6 个数字，同时 LED发光管闪烁表示排序完成。按取 “消键”清除结果显示回到待机状态，提示下一次输入和排 序操作过程。( 4)在排序过程中，若按下“取消”键，在LCD 屏幕上提示是否要取消排序操作，按“确定”减中断排序，清除显示；按其他键继续排序过程。(5) 在屏幕上显示出排序的所有中间结果，统计位置交换次数。(6) 用 LCD 屏幕上的图形菜单，让使用者在几

3、种排序方法中选择一种进行排序过程演示。三、排序算法说明1、冒泡排序已知一组无序数据a1、a2、an,需将其按升序排列。首先比较a1与a2的值,若 a1 大于 a2 则交换两者的值，否则不变。再比较 a2 与 a3 的值，若 a2 大于 a3 则交换两者的值， 否则不变。 再比较 a3 与 a4 ，以此类推， 最后比较 an-1 与 an 的值。 这样处理一轮后， an 的值一定是这组数据中最大的。再对 a1an-1 以相同方法处理一 轮，则 an-1 的值一定是 a1an-1 中最大的。再对 a1an-2 以相同方法处理一轮， 以此类推。共处理 n-1 轮后 a1 、 a2 、 an 就以升序

4、排列了。优点：稳定，比较次数已知； 缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。2、选择排序已知一组无序数据 a1 、 a2 、 an ，需将其按升序排列。 首先比较 a1 与 a2 的值， 若a1大于a2则交换两者的值，否则不变。再比较 a1与a3的值，若a1大于a3 则交换两者的值，否则不变。再比较 a1 与 a4 ，以此类推，最后比较 a1 与 an 的值。 这样处理一轮后， a1 的值一定是这组数据中最小的。 再将 a2 与 a3an 以相同方法比 较一轮， 则 a2 的值一定是 a2an 中最小的。 再将 a3 与 a4an 以相同方法比较一 轮，以此类推。共处理 n-1

5、轮后 a1 、 a2 、 an 就以升序排列了。优点：稳定，比较次数与冒泡排序一样，数据移动次数比冒泡排序少； 缺点：相对之下还是慢。3、插入排序已知一组升序排列数据a1、a2、an，组无序数据 b1、b2、bm，需将二者合并成一个升序数列。首先比较 b1 与 a1 的值， 若 b1 大于 a1 ，则跳过，比较 b1与a2的值，若b1仍然大于a2，则继续跳过，直到b1小于a数组中某一数据ax ，则将 axan 分别向后移动一位，将 b1 插入到原来 ax 的位置这就完成了 b1 的插入。b2bm用相同方法插入。(若无数组a，可将b1当作n=1的数组a)优点：稳定，快；缺点： 比较次数不一定，

6、比较次数越少， 插入点后的数据移动越多，特别是当数据总量庞大 的时候，但用链表可以解决这个问题。4、希尔排序已知一组无序数据a1、a2、an，需将其按升序排列。发现当n不大是，插入排序的效果很好。首先取一增量 d(d<n) ，将 a1 、 a1+d 、 a1+2d 列为第一组， a2 、 a2+d 、 a2+2d 列为第二组， ad 、 a2d 、 a3d 列为最后一组以次类推， 在各组内用插入排序，然后取 d'<d ，重复上述操作，直到 d=1。优点：快，数据移动少；缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。四、原理说明和模块1、主

7、要用到的模块数据输入模块：主要完成要排序数据的输入；LED显示模块:主要完成数据的输入以及排序过程在数码过程上的显示 ；LCD显示模块:主要完成数据排序过程,操作提示等内容的显示；扫描键盘模块：主要完成对键盘的扫描，通过得到不的按键转到相应的处理 程序；排序及主控制模块：主要完成数据排序以及显示控制；延时及动态刷新模块：主要用来去除键盘抖动和刷新数码管显示.2、程序各部分模块关系初始化硬件资源数据输入按键扫描排序以及显示控制LCD显示LED显示动态刷新3、操作说明从键盘输入六个数 ,A 键清除 , 重新输入 输入后提示选择排序方法 在排序过程中可以按 A 键可以取消当前排序 排序完成后LED灯

8、闪丄CD提示排序完成,按任意键继续下一次排序过程4、流程图与各模块代码说明开始硬件初始化> LCD提示输入数据扫描键盘是否取消输入将数据输入缓存选择排序方法*插入法冒泡法选择法希尔法返回是否开始排序返回待机下一次循环排序LCD显示LCD显示数据是否交换IIJ X延时*查询到有取消键按下记录交换次数排序是否完成结束排序rrLCD提示是否结束1 F耳r卩 1返回排序程序rr返回待机状态1_-JLCD显示排序次数LED显示最后结果LED闪灯查询按键有键按下返回五、源程序1、主程序部分 #include "71x_lib.h" #include "ledkey.h&

9、quot; #include "lcdlib.h"#include "rt_fp.h"#include "stdlib.h"#include "stdio.h"#pragma import(_use_no_semihosting_swi)#define EMI_BCON0#define EMI_BCON1#define EMI_BCON2#define EMI_BCON3(*(volatile u16 *)0x6C000000)(*(volatile u16 *)0x6C000004)(*(volatile u16

10、 *)0x6C000008) (*(volatile u16 *)0x6C00000C)extern void _delay(u32); void refresh(void);void wait(void);void lcd_disp(int,int,int);void over(void);/floating point supporting void _rt_raise(int sig, int type) static int a,b;a=sig; b=type;/char tch64;u32 pts64=10,0, 16,7, 30,4, 23,13, 27,25, 20,20,8,2

11、9, 10,20, 0,16, 11,13, 10,0; /np=11, a star u32 pts164;int data6;int label=0;void Main(void)int i=0,j,n,k,tem1,tem2,method;int in_count,count=0,tmp,min,index,increment,d;char s2=0,0;#ifdef DEBUG debug();#endifEMI_BCON0 = 0x803D;EMI_BCON2 = 0x803D;EMI_BCON3 = 0x803D;GPIO_Config(GPIO2, 0x00FF, GPIO_AF

12、_PP); /enable CS0-CS3EMI_Config(0, EMI_ENABLE | /enable bank 1 >=4 waitsEMI_Config(1, EMI_ENABLE | /enable bank 1 >=4 waitsEMI_Config(3, EMI_ENABLE | /enable bank 1 >=4 waitsEMI_WAITSTATE(3)EMI_WAITSTATE(2)EMI_WAITSTATE(3)| EMI_SIZE_16);| EMI_SIZE_16);| EMI_SIZE_16);/config the gpio0,LED58G

13、PIO_Config(GPIO0, 0x00F0, GPIO_OUT_PP); /turn on all 4 led lightsGPIO_WordWrite(GPIO0, GPIO_WordRead(GPIO0) | (0x0f<<4);EnableLedKey();/ 初始化浮点运算 , 在 rt_fp.h 中声明_fp_init();for(i=0;i<6;i+)SetLedDigit(i, 0);/ LCD 初始化LCD_Init();/ test 2-D graphst0:gClearScreen(0); gSetColor(LCD_YELLOW); gSetBkC

14、olor(LCD_GREEN); gTextOut(" 数据排序过程演示 ",70,80); gTextOut(" 黄志君 06221066",70,150); gTextOut(" 谢克强 06221026",70,230); gTextOut(" 任课老师 闻跃 ",70,310); s0=0;s1=0;for(i=0;i<10;i+)for(j=0;j<100;j+)_delay(200);st1:gClearScreen(0);gTextOut(" 请您输入要排序的数据 ",

15、45,70);for(i=0;i<6;i+) datai=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) goto st1;else datain_count=n; in_c

16、ount+;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

17、); gTextOut(" 若要取消操作按 A",70,210);don=GetKey();if(n=10)goto st0;else if(n=1|n=2|n=3|n=4|n=5) method=n;break;else refresh();while(1);gClearScreen(0);/* 冒泡法排序 */if (method=1)gTextOut(" 冒泡法排序开始， A 键退出排序 ",15,30);gTextOut(" 您输入的原始数据为： ",20,60);for(i=0;i<6;i+)s0=datai+48;g

18、TextOut(s,10*i+155,60);gTextOut(" 以下是中间结果，其他任意键加速显示 ",2,90); count=0;/冒泡法排序，外层循环 冒泡法排序，内层循环for(i=0;i<6;i+) for(j=0;j<6-i;j+) if(dataj>dataj+1) wait(); tmp=dataj; dataj=dataj+1; dataj+1=tmp; if(label=1)gTextOut("gTextOut("while(1)/相邻比较若大则交换延时交换扫描程序发现取消键被按下您确定要退出程序么？ "

19、;,50,250);按 A 退出程序，其他键继续 ",30,280);refresh(); / 能动态显示交换的数据 n=GetKey(); if(n<0) k=-1; continue; / if(n=k) continue; / k=n;动态刷新六位数码管显示/ 获取按键值/ 如果没有按键/ 清除上一次按键值下一个循环若与上次按键相同，不做处理以保证数码管if(n=10) goto st0; / else / gRectFill(0,150,240,320,0);/ label=0;_delay(50000); break; / count+; / if(count<

20、=6) lcd_disp(6,10,count*20+100); 序，分栏显示用户确定退出程序，返回待机状态用户要求继续排序背景填充，清除语言提示返回，继续排序计数值加一/调用LCD显示程else if(count>6&&count<=12) lcd_disp(6,90,(count-6)*20+100);else lcd_disp(6,170,(count-12)*20+100);if(count>9)tem1=1;tem2=count-10;s0=tem1+48;s1=tem2+48;elses0=count+48;count=0;for(i=0;i<

21、;6;i+) / min=datai;index=i;for(j=i+1;j<6;j+) / if(dataj<min) / min=dataj; index=j;if(index!=i) /wait(); / tmp=datai; / datai=dataindex; dataindex=tmp;s1=0;if(count>6) count=6;gTextOut(" 排序结束 , 交换了 ",50,count*20+130); gTextOut(s,160,count*20+130);gTextOut(" 次。 ",180,count

22、*20+130);gTextOut(" 按任意键返回待机状态，再次排序 ",15,count*20+160); over();goto st0;/* 选择法排序 */if (method=2)label=0;gTextOut(" 选择法排序开始， A 键退出排序 ",15,30);gTextOut(" 您输入的原始数据为： ",20,60);for(i=0;i<6;i+) s0=datai+48; gTextOut(s,10*i+155,60);gTextOut(" 以下是中间结果，其他任意键加速显示 ",2

23、,90);选择法排序，外层循环选择法排序，内层循环找出本次循环中最小的数，标记位置找到当前最小的数延时交换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;动态刷新六位数码管显示，以保证数码管能获取按键值如果没有按键/ 清除上一次按键值

24、/ 下一个循环/ 若与上次按键相同，不做处理if(n=10) goto st0; /用户确定退出程序，返回待机状态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("

25、次。 ",180,count*20+130);gTextOut(" 按任意键返回待机状态，再次排序 ",15,count*20+160); over();goto st0; /* 插入法排序 */if （method=3）gTextOut（" 插入法排序开始， A 键退出排序 ",15,30）;gTextOut(" 您输入的原始数据为： ",20,60);for(i=0;i<6;i+) s0=datai+48; gTextOut(s,10*i+155,60);gTextOut(" 以下是中间结果，其他任意键加

26、速显示 ",2,90); count=0;for(i=1;i<n;i+)用 tmp 记录 datai 逐个向前寻找插入点找到, 跳出循环tmp=datai; / for(j=i-1;j>=0;j-) / if(tmp>dataj) /break;else /没找到, 将前一个数据后移dataj+1=dataj; dataj+1=tmp;if(label=1) /扫描程序发现取消键被按下 gTextOut（" 您确定要退出程序么？ ",50,250）; gTextOut（" 按 A 退出程序，其他键继续 ",30,280）;wh

27、ile(1)refresh(); /动态显示交换的数据n=GetKey(); /if(n<0) / k=-1; continue;if(n=k) continue; k=n;动态刷新六位数码管显示，以保证数码管能获取按键值如果没有按键/ 清除上一次按键值/ 下一个循环/ 若与上次按键相同，不做处理if(n=10) goto st0; / else /用户确定退出程序，返回待机状态用户要求继续排序背景填充，清除语言提示gRectFill(0,150,240,320,0);/ label=0;_delay(50000);break; / 返回，继续排序 count+; / 计数值加一 if(

28、count<=6)Icd_disp(6,10,count*20+100); /调用 LCD显示程序，分栏显示else if(count>6&&count<=12)Icd_disp(6,90,(count-6)*20+100); eIse Icd_disp(6,170,(count-12)*20+100);/* 希尔排序 */if (method=4)gTextOut(" 插入法排序开始， A 键退出排序 ",15,30);gTextOut(" 您输入的原始数据为： ",20,60);for(i=0;i<6;i+)

29、s0=datai+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+) /*将Rd+1. n分别插入各组当前的有序区 */if(datai<datai-d)data0=datai;j=i-d; /* R0只是暂存单元，不是哨兵 */do /*查找 Ri 的插入位置 */dataj+d=dataj

30、;/*后移记录 */j=j-d; /*查找前一记录 */whiIe(j>0&&data0<dataj);dataj+d=data0; /*插入 Ri 到正确的位置上 */ whiIe(increment>1);if(IabeI=1) /扫描程序发现取消键被按下gTextOut(" 您确定要退出程序么？ ",50,250); gTextOut("按 A 退出程序，其他键继续 ",30,280);whiIe(1)refresh(); /动态刷新六位数码管显示，以保证数码管能动态显示交换的数据n=GetKey(); /if(n

31、<0)获取按键值 /如果没有按键k=-1;/ 清除上一次按键值continue;if(n=k)/ 下一个循环continue;k=n;/ 若与上次按键相同，不做处理if(n=10) goto st0; / 用户确定退出程序，返回待机状态 else / 用户要求继续排序gRectFill(0,150,240,320,0);/背景填充，清除语言提示label=0; _delay(50000); break; /count+; /if(count<=6)返回，继续排序计数值加一lcd_disp(6,10,count*20+100); / 序，分栏显示调用LCD显示程else if(cou

32、nt>6&&count<=12)lcd_disp(6,90,(count-6)*20+100);else lcd_disp(6,170,(count-12)*20+100);2、子程序部分/* 延时子程序 */ void wait(void)int i,n,k;for(i=0;i<80;i+) /refresh(); / n=GetKey(); / if(n<0)k=-1;continue; if(n=k)循环用来延时刷新数码管显示，使数码管可以动态显示获取按键值取消键被按下，修改标志位返回用户不想取消排序，操作继续进行continue; k=n; if

33、(n=10) / label=1;return; / else /return;return;/*LED 动态显示程序 */void refresh(void)int i=0;for(i=0;i<6;i+) / 将排序中间过程数据显示 LedCodeDisp(5-i,datai);_delay(200);SetLedDigit(5-i,0);/*lcd 显示子程序 */void lcd_disp(int n,int m,int pos)int i;char s10;for(i=0;i<n;i+)/将排序中间结果在LCD上分行显示s0=datai+48; gTextOut(s,10*i+m,pos);/* 排序结束后处理函数 */void over(void)int i,k,n=0;int temp=0;while(1)使LED全亮GPIO_WordW