嵌入式課程設(shè)計(jì)報(bào)告之?dāng)?shù)據(jù)排序

1、1嵌入式設(shè)計(jì)報(bào)告題目:數(shù)據(jù)排序過程演示黃志君 通信0607 06221066謝克強(qiáng) 通信0607 06221026指導(dǎo)老師：聞躍2009 年 5 月 11 日2一、 設(shè)計(jì)題目：數(shù)據(jù)排序演示過程用鍵盤隨機(jī)輸入6個數(shù)值為0-9的數(shù)字，用冒泡排序法將它們按從小到大的 方式排序，并顯示排序過程和最終結(jié)果。二、 設(shè)計(jì)要求和目標(biāo)(1 )在 LCD 屏幕上提示用戶用矩陣鍵盤輸入 6 個數(shù)字，輸入過程顯示在屏幕上， 同時從左 到右顯示在擴(kuò)展版的數(shù)碼管上。輸入完成后，屏幕提示按“確認(rèn)”鍵開始排序過程。一定要 輸滿 6 個數(shù)字才能排序；輸入過程中若按“取消”鍵則清除所有輸入結(jié)果，回到待機(jī)狀態(tài)。( 2)當(dāng)輸入完 6

2、 個數(shù)字，按下“確認(rèn)”鍵后，程序開始排序；在排序過程中在數(shù)碼管上顯 示中間結(jié)果， 每當(dāng)數(shù)字順序發(fā)生變化時， 顯示在數(shù)碼管上停留 3 秒或有按鍵按下后才進(jìn)行下 一步計(jì)算。(3)排序結(jié)束后，在數(shù)碼管上應(yīng)該從左到右顯示數(shù)值從小到大排列的6 個數(shù)字，同時 LED發(fā)光管閃爍表示排序完成。按取 “消鍵”清除結(jié)果顯示回到待機(jī)狀態(tài)，提示下一次輸入和排 序操作過程。( 4)在排序過程中，若按下“取消”鍵，在LCD 屏幕上提示是否要取消排序操作，按“確定”減中斷排序，清除顯示；按其他鍵繼續(xù)排序過程。(5)在屏幕上顯示出排序的所有中間結(jié)果，統(tǒng)計(jì)位置交換次數(shù)。(6)用 LCD 屏幕上的圖形菜單，讓使用者在幾種排序方法

3、中選擇一種進(jìn)行排序過程演示。3三、排序算法說明1、冒泡排序已知一組無序數(shù)據(jù) a1、a2、an,需將其按升序排列。首先比較 a1與 a2的值,若 a1 大于 a2 則交換兩者的值，否則不變。再比較 a2 與 a3 的值，若 a2 大于 a3 則交換兩者的值， 否則不變。 再比較 a3 與 a4 ，以此類推， 最后比較 an-1 與 an 的值。 這樣處理一輪后， an 的值一定是這組數(shù)據(jù)中最大的。再對 a1an-1 以相同方法處理一 輪，則 an-1 的值一定是 a1an-1 中最大的。再對 a1an-2 以相同方法處理一輪， 以此類推。共處理 n-1 輪后 a1 、a2 、 an 就以升序排列

4、了。優(yōu)點(diǎn)：穩(wěn)定，比較次數(shù)已知； 缺點(diǎn)：慢，每次只能移動相鄰兩個數(shù)據(jù)，移動數(shù)據(jù)的次數(shù)多。2、選擇排序已知一組無序數(shù)據(jù) a1 、 a2 、 an ，需將其按升序排列。 首先比較 a1 與 a2 的值， 若 a1大于 a2 則交換兩者的值，否則不變。再比較 a1 與 a3 的值，若 a1 大于 a3 則交換兩者的值，否則不變。再比較 a1 與 a4 ，以此類推，最后比較 a1 與 an 的值。 這樣處理一輪后， a1 的值一定是這組數(shù)據(jù)中最小的。 再將 a2 與 a3an 以相同方法比 較一輪， 則 a2 的值一定是 a2an中最小的。 再將 a3 與 a4an 以相同方法比較一 輪，以此類推。共處

5、理 n-1 輪后 a1 、 a2 、 an 就以升序排列了。優(yōu)點(diǎn)：穩(wěn)定，比較次數(shù)與冒泡排序一樣，數(shù)據(jù)移動次數(shù)比冒泡排序少； 缺點(diǎn)：相對之下還是慢。3、插入排序已知一組升序排列數(shù)據(jù)a1、a2、an，組無序數(shù)據(jù) b1、b2、bm，需將二者合并成一個升序數(shù)列。首先比較 b1 與 a1 的值， 若 b1 大于 a1 ，則跳過，比較 b1 與a2 的值，若 b1 仍然大于 a2 ，則繼續(xù)跳過，直到 b1 小于 a 數(shù)組中某一數(shù)據(jù) ax ，則將 axan分別向后移動一位，將 b1 插入到原來 ax 的位置這就完成了 b1 的插入。b2bm用相同方法插入。(若無數(shù)組a，可將 b1當(dāng)作 n=1 的數(shù)組 a)優(yōu)

6、點(diǎn)：穩(wěn)定，快；缺點(diǎn)： 比較次數(shù)不一定， 比較次數(shù)越少， 插入點(diǎn)后的數(shù)據(jù)移動越多，特別是當(dāng)數(shù)據(jù)總量龐大 的時候，但用鏈表可以解決這個問題。4、希爾排序已知一組無序數(shù)據(jù) a1 、 a2 、 an ，需將其按升序排列。發(fā)現(xiàn)當(dāng) n 不大是，插入排 序的效果很好。 首先取一增量 d(dn) ， 將 a1 、 a1+d 、 a1+2d 列為第一組， a2 、 a2+d 、 a2+2d 列為第二組， ad 、 a2d 、 a3d 列為最后一組以次類推， 在各組內(nèi)用插入排序，然后取d LCD 提示輸入數(shù)據(jù)掃描鍵盤將數(shù)據(jù)輸入緩存是否取消輸入*選擇排序方法插入法冒泡法選擇法希爾法返回返回待機(jī)下一次循環(huán)排序LCD

7、顯示LCD 顯示交換IIJ X是否開始排序數(shù)據(jù)是否延時*查詢到有取消鍵按下記錄交換次數(shù)排序是否完成結(jié)束排序rrLCD 提示是否結(jié)束1 F耳r卩 1返回排序程序rr返回待機(jī)狀態(tài)1_-JLCD 顯示排序次數(shù)LED 顯示最后結(jié)果LED 閃燈查詢按鍵有鍵按下返回7五、源程序1、主程序部分#include 71x_lib.h #include ledkey.h #include lcdlib.h#include rt_fp.h#include stdlib.h#include stdio.h#pragma import(_use_no_semihosting_swi)(*(volatile u16 *)

8、0 x6C000000)(*(volatile u16 *)0 x6C000004)(*(volatile u16 *)0 x6C000008)(*(volatile u16 *)0 x6C00000C)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

9、tch64;u32 pts64=10,0, 16,7, 30,4, 23,13, 27,25, 20,20,8,29, 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;#define EMI_BCON0#define EMI_BCON1#define EMI_BCON2#define EMI_BCON38char

10、 s2=0,0;#ifdef DEBUG debug();#endifEMI_BCON0 = 0 x803D;EMI_BCON2 = 0 x803D;EMI_BCON3 = 0 x803D;GPIO_Config(GPIO2, 0 x00FF, GPIO_AF_PP); /enable CS0-CS3/config the gpio0,LED58GPIO_Config(GPIO0, 0 x00F0, GPIO_OUT_PP); /turn on all 4 led lightsGPIO_WordWrite(GPIO0, GPIO_WordRead(GPIO0) | (0 x0f4);Enabl

11、eLedKey();_fp_init();for(i=0;i6;i+)SetLedDigit(i, 0);/ LCD初始化LCD_Init();/ test 2-D graphst0:gClearScreen(0); gSetColor(LCD_YELLOW); gSetBkColor(LCD_GREEN);gTextOut(數(shù)據(jù)排序過程演示,70,80); gTextOut(黃志君06221066,70,150);gTextOut(謝克強(qiáng)06221026,70,230); gTextOut(任課老師 聞躍,70,310);s0=0;s1=0;for(i=0;i10;i+)for(j=0;j=

12、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);/初始化浮點(diǎn)運(yùn)算,在rt_fp.h中聲明9gTextOut(請您輸入要排序的數(shù)據(jù),45,70);for(i=0;i6;i+) datai=20; in_count=0;while(in_count6)re

13、fresh();n=GetKey();if(n9&n!=10)continue;gTextOut(如果需要重新輸入請按A,40,100); if(n=10) goto st1;else datain_count=n; in_count+;for(i=0;iin_count;i+)lcd_disp(in_count,88,130);gSetColor(LCD_BLUE); gSetBkColor(LCD_WHITE); gTextOut(數(shù)據(jù)輸入完畢,75,60); gTextOut(冒泡法排序請按1,70,90); gTextOut(選擇法排序請按2,70,120); gTextOut

14、(插入法排序請按3,70,150); gTextOut(希爾法排序請按4,70,180); gTextOut(若要取消操作按A,70,210);do10n=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(您輸入的原始數(shù)據(jù)為：,20,60);for(i=0;i6;i+)s0=datai+48;gTextO

15、ut(s,10*i+155,60);gTextOut(以下是中間結(jié)果，其他任意鍵加速顯示,2,90); count=0;for(i=0;i6;i+)for(j=0;jdataj+1)wait();tmp=dataj;dataj=dataj+1;dataj+1=tmp;if(label=1)gTextOut(gTextOut(while(1)/相鄰比較若大則交換延時交換掃描程序發(fā)現(xiàn)取消鍵被按下您確定要退出程序么？,50,250);按A退出程序，其他鍵繼續(xù),30,280);冒泡法排序，外層循環(huán) 冒泡法排序，內(nèi)層循環(huán)/11refresh(); /能動態(tài)顯示交換的數(shù)據(jù)n=GetKey();if(n0)

16、 k=-1; continue;/ if(n=k) continue; /k=n;動態(tài)刷新六位數(shù)碼管顯示/獲取按鍵值/如果沒有按鍵/清除上一次按鍵值下一個循環(huán)若與上次按鍵相同，不做處理以保證數(shù)碼管if(n=10) goto st0; / else / gRectFill(0,150,240,320,0);/label=0;_delay(50000); break; / count+; / if(count6&count9)tem1=1;tem2=count-10;s0=tem1+48;s1=tem2+48;elses0=count+48;1213s1=0;if(count6) coun

17、t=6;gTextOut(排序結(jié)束,交換了,50,count*20+130);gTextOut(s,160,count*20+130);gTextOut(次。,180,count*20+130);gTextOut(按任意鍵返回待機(jī)狀態(tài)，再次排序,15,count*20+160); over();goto st0;/*選擇法排序*/if (method=2)label=0;gTextOut(選擇法排序開始，A鍵退出排序,15,30);gTextOut(您輸入的原始數(shù)據(jù)為：,20,60);for(i=0;i6;i+)s0=datai+48; gTextOut(s,10*i+155,60);gTex

18、tOut(以下是中間結(jié)果，其他任意鍵加速顯示,2,90);選擇法排序，外層循環(huán)選擇法排序，內(nèi)層循環(huán)找出本次循環(huán)中最小的數(shù)，標(biāo)記位置找到當(dāng)前最小的數(shù)延時交換count=0;for(i=0;i6;i+) /min=datai;index=i;for(j=i+1;j6;j+) /if(datajmin) /min=dataj;index=j;if(index!=i) /wait(); / tmp=datai; /datai=dataindex;dataindex=tmp;14if（label=1） /掃描程序發(fā)現(xiàn)取消鍵被按下gTextOut（您確定要退出程序么？,50,250）;gTextOut（按

19、A退出程序，其他鍵繼續(xù),30,280）;gTextOut(排序結(jié)束,交換了,50,count*20+130);gTextOut(s,160,count*20+130);gTextOut(次。,180,count*20+130);gTextOut(按任意鍵返回待機(jī)狀態(tài)，再次排序,15,count*20+160); over();goto st0;/*插入法排序*/if （method=3）gTextOut（插入法排序開始，A鍵退出排序,15,30）;while(1)refresh(); /動態(tài)顯示交換的數(shù)據(jù)n=GetKey(); /if(n0) / k=-1;continue;if(n=k)co

20、ntinue; k=n;動態(tài)刷新六位數(shù)碼管顯示，以保證數(shù)碼管能獲取按鍵值如果沒有按鍵/清除上一次按鍵值/下一個循環(huán)/若與上次按鍵相同，不做處理if(n=10) goto st0; /用戶確定退出程序，返回待機(jī)狀態(tài)else /用戶要求繼續(xù)排序gRectFill(0,150,240,320,0);/label=0; _delay(50000);break; /count+; /lcd_disp(6,88,count*20+100); /背景填充，清除語言提示返回，繼續(xù)排序計(jì)數(shù)值加一調(diào)用LCD顯示程序15gTextOut(您輸入的原始數(shù)據(jù)為：,20,60);for(i=0;i6;i+)s0=data

21、i+48; gTextOut(s,10*i+155,60);gTextOut(以下是中間結(jié)果，其他任意鍵加速顯示,2,90); count=0;for(i=1;i=0;j-) / if(tmpdataj) /break;dataj+1=dataj; dataj+1=tmp;gTextOut（您確定要退出程序么？,50,250）; gTextOut（按A退出程序，其他鍵繼續(xù),30,280）;gRectFill(0,150,240,320,0);/ label=0;_delay(50000);break; /返回，繼續(xù)排序 count+; /計(jì)數(shù)值加一if(count6&count=12)

22、Icd_disp(6,90,(count-6)*20+100); eIseIcd_disp(6,170,(count-12)*20+100);用tmp記錄datai逐個向前尋找插入點(diǎn)找到,跳出循環(huán)else /沒找到,將前一個數(shù)據(jù)后移if(label=1) /掃描程序發(fā)現(xiàn)取消鍵被按下while(1)refresh(); /動態(tài)顯示交換的數(shù)據(jù)n=GetKey(); /if(n0) / k=-1;continue;if(n=k)continue; k=n;動態(tài)刷新六位數(shù)碼管顯示，以保證數(shù)碼管能獲取按鍵值如果沒有按鍵/清除上一次按鍵值/下一個循環(huán)/若與上次按鍵相同，不做處理if(n=10) goto

23、st0; /else /用戶確定退出程序，返回待機(jī)狀態(tài)用戶要求繼續(xù)排序背景填充，清除語言提示16/*希爾排序*/if (method=4)gTextOut(插入法排序開始，A鍵退出排序,15,30);gTextOut(您輸入的原始數(shù)據(jù)為：,20,60);for(i=0;i0 */do increment=increment/3+1; /*求下一增量*/for(i=d+1;i=n;i+) /*將Rd+1.n分別插入各組當(dāng)前的有序區(qū)*/if(datai0&data01);if(IabeI=1) /掃描程序發(fā)現(xiàn)取消鍵被按下gTextOut(您確定要退出程序么？,50,250); gTextO

24、ut(按A退出程序，其他鍵繼續(xù),30,280);whiIe(1)17refresh(); /動態(tài)刷新六位數(shù)碼管顯示，以保證數(shù)碼管能動態(tài)顯示交換的數(shù)據(jù)n=GetKey(); /if(n0)獲取按鍵值 /如果沒有按鍵k=-1;/清除上一次按鍵值continue;if(n=k)/下一個循環(huán)continue;k=n;/若與上次按鍵相同，不做處理if(n=10) goto st0; /用戶確定退出程序，返回待機(jī)狀態(tài)else /用戶要求繼續(xù)排序gRectFill(0,150,240,320,0);/背景填充，清除語言提示label=0;_delay(50000);break; /count+; /if(c

25、ount6&count=12)lcd_disp(6,90,(count-6)*20+100);else lcd_disp(6,170,(count-12)*20+100);2、子程序部分/*延時子程序*/ voidwait(void)int i,n,k;for(i=0;i80;i+) /refresh(); /n=GetKey(); /if(n0)k=-1;continue; if(n=k)循環(huán)用來延時刷新數(shù)碼管顯示，使數(shù)碼管可以動態(tài)顯示獲取按鍵值1819continue; k=n; if(n=10) / label=1;return; / else/return;return;/*L

26、ED動態(tài)顯示程序*/void refresh(void)int i=0;for(i=0;i6;i+) /將排序中間過程數(shù)據(jù)顯示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;in;i+)/將排序中間結(jié)果在LCD上分行顯示s0=datai+48; gTextOut(s,10*i+m,pos);/*排序結(jié)束后處理函數(shù)*/void over(void)int i,k,n=0;int temp=0;while(1)GPIO_WordWrite(GPIO0, 0 xffff); /取消鍵被按下，修改標(biāo)志位返回用戶不想取消排序，操作繼續(xù)進(jìn)行使LED全亮20for(i=0;i10;i+) /refresh();n=GetKey(); /if(n0)k=-1; continue;if(n=k)continue;else /temp=1;k=n;break;if(temp=1) goto ov; /狀態(tài)GPIO_WordWrite(GPIO0, 0 xff0f);/for(i=0;i10;i+)