本帖最后由 niuniu 于 2015-6-9 03:26 編輯
前言
首先，本人非常承認(rèn)用匯編語言實現(xiàn)二叉堆是很白癡的做法，也是非常吃力不討好的做法。不過貌似俺自己覺得接近了發(fā)燒友的程度了，所以有時發(fā)燒，這次寫了幾個匯編程序，包括二叉堆、快速排序、計數(shù)排序。然后就告一段落了，因為實在有多余覺得，不過有興趣的同學(xué)可以來討論一下呢，我是非常歡迎的。
目錄 第一章 什么是二叉堆4 1.1 二叉堆的結(jié)構(gòu)和存儲4 1.2 二叉堆的操作4 第二章 關(guān)鍵匯編指令5 2.1 數(shù)據(jù)傳送5 2.1.1 MOV5 2.1.2 LDR5 2.1.3 STR5 2.2 算數(shù)和邏輯運(yùn)算6 2.2.1 ADD6 2.2.2 LSL6 2.3 跳轉(zhuǎn)6 2.3.1 B6 2.3.2 BL7 第三章 匯編與C語言相互調(diào)用7 3.1 C語言調(diào)用匯編7 3.1.1 匯編子程序的返回7 3.1.2 匯編子程序的參數(shù)8 3.2 匯編調(diào)用C語言8 第四章 匯編實現(xiàn)二叉堆9 4.1、二叉堆最大化 - ASM_BiHeap_Maxify9 4.1.1 二叉堆最大化的作用9 4.1.2 二叉堆最大化的偽代碼9 4.1.3 二叉堆最大化C語言原形和解釋10 4.1.4 二叉堆最大化匯編語言描述10 4.2、二叉堆建立 - ASM_BiHeap_Build12 4.2.1 二叉堆建立的作用12 4.2.2 二叉堆建立的偽代碼12 4.2.3 二叉堆建立的C語言原形和解釋12 4.2.4 二叉堆建立的匯編語言描述13 4.3、二叉堆排序 - ASM_BiHeap_Sort13 4.3.1 二叉堆排序的作用13 4.3.2 二叉堆排序的偽代碼13 4.3.3 二叉堆最大化的C語言原形和解釋14 4.3.4 二叉堆最大化的匯編語言描述14 4.4、二叉堆鍵值增加 - ASM_BiHeap_KeyInc15 4.4.1 二叉堆鍵值增加的作用15 4.4.2 二叉堆鍵值增加的偽代碼15 4.4.3 二叉堆鍵值增加的C語言原形和解釋16 4.4.4 二叉堆鍵值增加的匯編語言描述16 4.5、二叉堆元素插入 - ASM_BiHeap_Insert17 4.5.1 二叉堆元素插入的作用17 4.5.2 二叉堆元素插入的偽代碼17 4.5.3 二叉堆元素插入的C語言原形和解釋17 4.5.4 二叉堆元素插入的匯編語言描述18 4.6、二叉堆最大元素 - ASM_BiHeap_Maximum18 4.6.1 二叉堆最大元素的作用18 4.6.2 二叉堆最大元素的偽代碼18 4.6.3 二叉堆最大元素的C語言原形和解釋19 4.6.4 二叉堆最大元素的匯編語言描述19 4.7、二叉堆出隊最大元素 - ASM_BiHeap_ExtraMax19 4.7.1 二叉堆出隊最大元素的作用19 4.7.2 二叉堆出隊最大元素的偽代碼19 4.7.3 二叉堆出隊最大元素的C語言原形和解釋20 4.7.4 二叉堆出隊最大元素的匯編語言描述20 第五章 測試21 5.1 匯編文件的包裝21 5.2 C語言頭文件22 5.3 測試23 5.4 測試結(jié)果24 附錄24 參考文獻(xiàn)24
第一章 什么是二叉堆 數(shù)據(jù)結(jié)構(gòu)方面的知識，可以參考有關(guān)數(shù)據(jù)結(jié)構(gòu)的書，我這里參考的是《算法導(dǎo)論》第二版，大家有興趣的話也可以參考一下。這一章介紹的是二叉堆。 1.1 二叉堆的結(jié)構(gòu)和存儲 有很多數(shù)據(jù)結(jié)構(gòu)，從鏈表到樹到圖，二叉堆算是樹的一種吧，這里我們討論的是最大堆，需要借用《算法導(dǎo)論》的原文來說明什么是二叉堆。先看圖： 
左圖 二叉堆的結(jié)構(gòu) 右圖 二叉堆的存儲。 我們先看看結(jié)構(gòu)，是層次型的。處在上層的節(jié)點(diǎn)的值大于下面節(jié)點(diǎn)的值，比如1（16）大于2（14）和3（10），這樣的堆我們稱為最大堆。 存儲的話，編號為1點(diǎn)節(jié)點(diǎn)存儲在第1個位置，編號為2的節(jié)點(diǎn)存儲在第2個位置，以此類推。屬于順序存儲。 我們存儲在計算機(jī)上的二叉堆是類似于C語言的數(shù)組，并且本人編程實現(xiàn)時（C語言和匯編語言）是將第0號位置用于存儲二叉堆的大小，即存儲的是二叉堆有多少個元素。比如上面的第0號位置存儲的是10，因為有10個元素。 了解了二叉堆的結(jié)構(gòu)和存儲，我們來看一下二叉堆支持什么操作。 1.2 二叉堆的操作二叉堆這種數(shù)據(jù)結(jié)構(gòu)需要支持的操作分別有： 1、二叉堆最大化 - ASM_BiHeap_Maxify 2、二叉堆建立 - ASM_BiHeap_Build 3、二叉堆排序 - ASM_BiHeap_Sort 4、二叉堆鍵值增加 - ASM_BiHeap_KeyInc 5、二叉堆元素插入 - ASM_BiHeap_Insert 6、二叉堆最大元素 - ASM_BiHeap_Maximum 7、二叉堆出隊最大元素 - ASM_BiHeap_ExtraMax 對應(yīng)的這些操作在具體實現(xiàn)的時候會具體說明，當(dāng)然，我們使用的是Cortex-M3匯編語言實現(xiàn)的。 需要注意的是，我們是用C語言調(diào)用這些操作的。也就是說源代碼用匯編寫，但是留出C語言接口，讓C語言調(diào)用這些函數(shù)，這里我們初步了解一下，具體實現(xiàn)下面再做介紹。 接下來因為是使用匯編語言，所以也大概介紹一下關(guān)鍵的匯編指令。
第二章 關(guān)鍵匯編指令 匯編語言可能大家不是很熟悉，不過本人的話，從大二第二學(xué)期到大四第一學(xué)期，上課的話，每個學(xué)期都有涉及匯編指令，匯編程序。具體是從微機(jī)原理 -> 單片機(jī)原理 -> DSP原理 -> 嵌入式系統(tǒng)，呵呵，接觸了兩年多的會匯編，也該有點(diǎn)感覺了吧。這章介紹一點(diǎn)匯編指令，具體是參考《Cortex M3權(quán)威指南》。有一點(diǎn)要注意的是，對于匯編語言來說，在分號（;）后面是注釋，類似于C語言的行注釋（//）。 2.1 數(shù)據(jù)傳送 這里的數(shù)據(jù)傳送包括寄存器與寄存器之間的數(shù)據(jù)傳送和寄存器與存儲器之間的數(shù)據(jù)傳送，介紹三個指令MOV，LDR，STR。 2.1.1 MOV 可以說最經(jīng)典的匯編指令就是MOV了，因為貌似連助記符都沒有變過，在眾多的微處理器中都是采用助記符MOV。下面舉個例子： MOV R0, R1 ;將R1寄存器的值復(fù)制到R0 相當(dāng)簡單的匯編指令，看注釋就知道是什么意思了（分號后面的內(nèi)容是注釋）。 2.1.2 LDR 這個算數(shù)據(jù)加載吧，跟存儲器相關(guān)的數(shù)據(jù)傳送。本人理解為LoaD Register，大寫字母組成縮寫LDR，就是將存儲器ROM或者RAM的數(shù)據(jù)傳送到寄存器，舉個例子： LDR R0, [R1] ;相當(dāng)于C語言的R0 = *(unsigned int *)R1; 就是把R1當(dāng)成地址，將R1指向的那個地址對應(yīng)的數(shù)據(jù)傳送到R0。需要引起注意的是，這個指令一般是操作RAM或者ROM數(shù)據(jù)。 2.1.3 STR 這個算數(shù)據(jù)存儲吧，也是跟存儲器相關(guān)的數(shù)據(jù)傳送，只不過方向跟LDR相反。本人理解為STore Register，大寫字母組成縮寫STR，就是將寄存器的數(shù)據(jù)存儲到RAM或者ROM里面（現(xiàn)在的ROM很多都支持在線編程，比如Flash）。舉個例子： STR R0, [R1] ;相當(dāng)于C語言的*(unsigned int *)R1 = R0; 就是把R1當(dāng)成地址，將R0的內(nèi)容存儲到R1所指向的那個地址的存儲器上。同樣需要引起注意的是，這個指令一般也是操作RAM或者ROM數(shù)據(jù)。
2.2 算數(shù)和邏輯運(yùn)算 算數(shù)包括基本的加減乘除，邏輯運(yùn)算是與或非位移等，這里介紹兩個最簡單的ADD和LSL。其他指令類似。 2.2.1 ADD 加法指令，實現(xiàn)兩個數(shù)據(jù)相加，結(jié)果存儲到寄存器中。對應(yīng)的還有減法指令SUB，乘法指令MUL，除法指令DIV。例子： ADD R0, R1 ;相當(dāng)于C語言的R0 = R0 + R1或者R0 += R1 實現(xiàn)將R0 + R1兩個值相加，結(jié)果放在R0。
2.2.2 LSL 邏輯左移指令，實現(xiàn)數(shù)據(jù)的邏輯左移。本人的理解為Logic Shift Left，大寫字母對應(yīng)的縮寫為LSL。對應(yīng)的有邏輯右移LSR，算數(shù)右移ASR等，這里只介紹LSL，例子： LSL R0, #2 ;相當(dāng)于C語言的R0 = R0 << 2 或者R0 <<= 2; 實現(xiàn)將R0左移兩位，結(jié)果存放在R0，當(dāng)然一般情況下會與LDR配合使用，可能稍微有一點(diǎn)點(diǎn)復(fù)雜了，例子： LDR R0, [R1, R2, LSL #2] ;相當(dāng)于C語言R0 = *(unsigned int *)(R1 + ( R2 << 2 ) ); 將R1與R2左移兩位的值相加，作為地址，取該地址的數(shù)據(jù)傳送到R0。 2.3 跳轉(zhuǎn) 跳轉(zhuǎn)實現(xiàn)與PC相關(guān)的操作，改變程序的流程，這里介紹到是B，BL。 2.3.1 B 這個指令的助記符就一個字母B，Branch，分支的意思，就是程序有兩個方向可以執(zhí)行，選擇其中一個分支。例子： B ASM_Loop ;跳轉(zhuǎn)到ASM_Loop那里，ASM_Loop是一個標(biāo)號 也就是程序的跳轉(zhuǎn)，并且是無條件跳轉(zhuǎn)，對應(yīng)的有條件跳轉(zhuǎn)，再舉個條件跳轉(zhuǎn)到例子，對應(yīng)的指令是BEQ，本人理解Branch EQual，大寫字母對應(yīng)的縮寫為BEQ。 BEQ ASM_Loop ;在執(zhí)行該指令前，一般執(zhí)行CMP比較兩個數(shù)據(jù) 如果上一次比較兩個數(shù)據(jù)相等，就跳轉(zhuǎn)到ASM_Loop那里，如果不相等，不跳轉(zhuǎn)，也就是這條指令執(zhí)行完后，程序流程沒有改變，依然是順序執(zhí)行。跳轉(zhuǎn)與不跳轉(zhuǎn)對應(yīng)的是兩個分支，也就應(yīng)驗了Branch是分支的意思了。 2.3.2 BL 這個是Branch and Link，其中的Branch與上個指令的Branch是一樣的，分支，但是多了一個Link。意思是跳轉(zhuǎn)前，保存了PC+4到LR寄存器。LR是Link Register，其中LR的L與BL的L是同個意思，Link。 多了這一步保存PC+4到LR的作用是可以實現(xiàn)程序返回，相當(dāng)于C語言的子程序返回，比如我們有個C語言函數(shù)func，那么函數(shù)調(diào)用func()操作，在func函數(shù)執(zhí)行完后可以返回調(diào)用該函數(shù)的程序那里繼續(xù)執(zhí)行，這就是BL發(fā)揮了作用。例子： BL ASM_My_Func ;相當(dāng)于C語言的ASM_My_Func()，函數(shù)調(diào)用，調(diào)用完會返回。 其中ASM_My_Func是一個匯編標(biāo)號，或者是C語言函數(shù)，根本上來說就是一個地址。
介紹了這些基本的指令，當(dāng)然是遠(yuǎn)遠(yuǎn)不夠的，還是要看看《Cortex M3權(quán)威指南》才能有更深入的了解。有興趣的同學(xué)可以閱讀這個資料。接下來介紹匯編語言與C語言的混合編程。
第三章 匯編與C語言相互調(diào)用 一般情況下我們都是用C語言編程的，但是也有不得不用到匯編的時候，就出現(xiàn)了C語言程序調(diào)用匯編子程序的問題。然而我們這里也會再介紹一下，相反的過程，就是匯編程序調(diào)用C語言子程序。 3.1 C語言調(diào)用匯編 模仿C語言的函數(shù)，將匯編程序?qū)懗深愃朴?/font>C語言的函數(shù)，也就是需要返回，繼續(xù)執(zhí)行前面的程序。并且有時候還需要帶有參數(shù)，帶有返回值，與C語言交互。下面一一介紹。 3.1.1 匯編子程序的返回 指令B和BL都能實現(xiàn)跳轉(zhuǎn)，其中BL保存了下一條指令地址（PC+4）到LR，所以我們根據(jù)LR可以返回，返回操作指令具體是BX LR。指令將LR值賦給PC，實現(xiàn)程序的返回，看下面的例子： ASM_Func MOV R0, R1 BX LR ASM_Func_End 這就是一個匯編子程序了，只有兩條指令。第一條指令將R1復(fù)制到R0，第二條指令就是實現(xiàn)子程序的返回了。想要在C語言中調(diào)用這個匯編子程序，還需要做一些工作。 1、將標(biāo)號ASM_Func聲明為外部的 2、C語言的頭文件聲明ASM_Func函數(shù) 3、C語言的源文件調(diào)用ASM_Func函數(shù) 具體怎么做分別如下： 1、在匯編文件中添加 EXPORT ASM_Func 2、C語言頭文件添加 void ASM_Func(void); 3、C語言源文件添加 ASM_Func(); （實現(xiàn)程序調(diào)用） 這樣做就可以了，當(dāng)然還有其他一些小工作，比如匯編文件末尾要有END，要聲明匯編文件的段啊什么的，具體后面介紹。上面的程序是沒有參數(shù)的，也就是C語言沒有傳遞參數(shù)給匯編子程序，匯編子程序也沒有返回參數(shù)給函數(shù)調(diào)用者。下面看看C語言怎么傳遞參數(shù)給匯編子程序，也就是準(zhǔn)備函數(shù)間的通信啦。 3.1.2 匯編子程序的參數(shù) 這一小節(jié)需要參考的是ATPCS，是ARM官方資料，講的是匯編與C語言之間參數(shù)的傳遞，我這里只是簡單介紹。 首先傳進(jìn)匯編子程序的參數(shù)，按照C語言函數(shù)調(diào)用是參數(shù)從左到右分別放在R0，R1，R2，R3，再到棧，如果有這么多參數(shù)的話，當(dāng)然如果沒有這么多參數(shù)，比如只有兩個參數(shù)，就分別放在R0，R1了，以此類推。 然后是返回給C語言的返回值，有返回值的話放在R0，沒有的話就不管R0是什么值了，因為C語言并不會用到。下面舉個簡單的例子： ASM_Add ADD R0, R1 BX LR ASM_Add_End 這個函數(shù)實現(xiàn)兩個數(shù)相加，返回相加的結(jié)果，類似于C語言的函數(shù)： Int ASM_Add(int a, int b) { Return a + b; } 也就是匯編函數(shù)和C語言函數(shù)實現(xiàn)的是同樣的功能，只不過用不同編程語言實現(xiàn)而已。跟上面介紹的沒有參數(shù)的函數(shù)一樣，也是要做一些工作C語言才能順利調(diào)用這個函數(shù)的，老樣子列出來： 1、將標(biāo)號ASM_Add聲明為外部的 2、C語言的頭文件聲明ASM_Add函數(shù) 3、C語言的源文件調(diào)用ASM_Add函數(shù) 具體怎么做分別如下： 1、在匯編文件中添加 EXPORT ASM_Add 2、C語言頭文件添加 void ASM_Add(int a, int b); 3、C語言源文件添加 ASM_Func(3, 2); 這樣的話我們就可以實現(xiàn)在C語言中靈活的調(diào)用匯編子程序了，接下來是相反的過程，匯編程序調(diào)用C語言子程序。 3.2 匯編調(diào)用C語言 如果我們用匯編實現(xiàn)類似于C語言的malloc函數(shù)，那真的是更加的吃力不討好了，所以有時候我們也可以在匯編中調(diào)用已有的C語言函數(shù)，方便我們的程序開發(fā)。下面也通過一個例子介紹： 匯編語言調(diào)用一個C語言函數(shù)func()，比如func()函數(shù)是這樣子的 Int func(int a, int b) { Return a + b; } 那么匯編語言調(diào)用時的參數(shù)從R0，R1，R2，R3到棧傳遞，返回值也是在R0取。調(diào)用實例如下： MOV R1, #2 MOV R2, #3 BL Func ;調(diào)用C語言函數(shù) ... ;這時候R0已經(jīng)是5了 當(dāng)然，為了讓匯編程序能知道Func標(biāo)號，需要在文件前面添加IMPORT Func才能成功編譯鏈接。
可以看到匯編語言和C語言編程也是比較方便等，有了上面這些基礎(chǔ)知識，下面我們開始介紹具體怎么用匯編語言實現(xiàn)二叉堆了，測試程序的話用C語言編寫，因為我們重點(diǎn)是實現(xiàn)匯編子程序而不是整個工程。 第四章 匯編實現(xiàn)二叉堆 我們實現(xiàn)的幾個接口函數(shù)在第一章講過，函數(shù)原形也是在第一章就給出了，這一章是具體實現(xiàn)了。這里分別給出操作的作用，然后給出偽代碼，再給出C語言的函數(shù)原形和解釋，最后給出Cortex-M3的匯編語言描述。再次說明，本人參考的是《算法導(dǎo)論》第二版，所以偽代碼是來自算法導(dǎo)論的。 4.1、二叉堆最大化 - ASM_BiHeap_Maxify4.1.1 二叉堆最大化的作用 二叉堆最大化是一個子程序，被其他二叉堆操作調(diào)用。其作用是保持二叉堆的性質(zhì)，即父節(jié)點(diǎn)的值大于子節(jié)點(diǎn)的值，然后遞歸下去。 4.1.2 二叉堆最大化的偽代碼 需要注意的是這個函數(shù)是遞歸的，也就是第10行調(diào)用的函數(shù)就是本函數(shù)，具體看截圖： 
4.1.3 二叉堆最大化C語言原形和解釋 C語言原形：void ASM_BiHeap_Maxify( uint32_t *BiHeap, uint32_t i ); 其中BiHeap是指向二叉堆的指針，也就是二叉堆的首地址，我們這里是一個數(shù)組的首地址，i是二叉堆元素的位置，該操作實現(xiàn)將二叉堆中以i為根的二叉堆保持二叉堆的性質(zhì)（父節(jié)點(diǎn)的值大于子節(jié)點(diǎn)的值）。 再次說明，二叉堆的大�。ǘ娑言氐膫�數(shù)）是存儲在BiHeap數(shù)組的第0個位置，也就是heap-size[BiHeap]相當(dāng)于C語言的BiHeap[0]。 偽代碼的意思是： 1、找到第i個節(jié)點(diǎn)的值，比較其與左右子節(jié)點(diǎn)的值的大小 2、獲取最大值的位置存放在largest 3、比較largest與i 不同：交換largest與i對應(yīng)位置的元素值，遞歸調(diào)用本函數(shù)最大化largest 相同：不需要操作，退出 這樣就實現(xiàn)而二叉堆的最大化，還不明白的同學(xué)請網(wǎng)上找資料，我們這里的重點(diǎn)是用匯編語言實現(xiàn)上面的偽代碼。 4.1.4 二叉堆最大化匯編語言描述 匯編語言也是根據(jù)偽代碼編寫出來的，所以先理解偽代碼才對，具體代碼如下： ;***************************** ******************************* ; 函數(shù)名 : ASM_BiHeap_Maxify ; 描述 : 二叉堆最大化 ; 輸入 : R0 --- 二叉堆首地址 ; R1 --- 二叉堆父節(jié)點(diǎn)偏移 ; 輸出 : 無 ; 寄存器 : 使用R1 ~ R8 ; 調(diào)用 : 內(nèi)部調(diào)用 ;***************************** ******************************* ASM_BiHeap_Maxify PUSH {LR}
MOV R2, R1 ;R1為父節(jié)點(diǎn)偏移 ADD R2, R2 ;R2為左孩子偏移 ADD R3, R2, #1 ;R3為右孩子偏移 MOV R4, R1 ;R4為最大節(jié)偏移 LDR R5, [R0, R1, LSL #2] ;R5為最大節(jié)點(diǎn)值 LDR R6, [R0] ;R6為二叉堆大小
CMP R2, R6 ;判斷是否有左孩子 BGT AMS_BiHeap_Maxify_Exit ;沒有左孩子, 退出
LDR R7, [R0, R2, LSL #2] ;R7為左孩子節(jié)點(diǎn) CMP R7, R5 ;比較節(jié)點(diǎn)大小 ITT GT ;如果違反最大堆規(guī)則 MOVGT R4, R2 ;左孩子值大于父節(jié)點(diǎn)值, 更新R4 MOVGT R5, R7 ;更新最大值R5
CMP R3, R6 ;判斷是否有右孩子 BGT ASM_BiHeap_Maxify_Judge ;沒有右孩子, 退出
LDR R7, [R0, R3, LSL #2] ;R7為右孩子節(jié)點(diǎn) CMP R7, R5 ;比較節(jié)點(diǎn)大小 IT GT ;如果違反最大堆規(guī)則 MOVGT R4, R3 ;右孩子值大于父節(jié)點(diǎn)值, 更新R4 MOVGT R5, R7 ;更新最大值R5
ASM_BiHeap_Maxify_Judge CMP R1, R4 ;如果父節(jié)是, 不違反二叉堆規(guī)則 BEQ AMS_BiHeap_Maxify_Exit ;退出
ASM_BiHeap_Maxify_Exchange LDR R7, [R0, R1, LSL #2] ;取父節(jié)點(diǎn)值 STR R5, [R0, R1, LSL #2] ;交換 STR R7, [R0, R4, LSL #2] ;交換
MOV R1, R4 ;R1作為父節(jié)點(diǎn), 遞歸二叉堆最大化 BL ASM_BiHeap_Maxify ;遞歸
AMS_BiHeap_Maxify_Exit POP {PC} ;退出 ASM_BiHeap_Maxify_End
本人非常承認(rèn)偽代碼確實也有點(diǎn)長，比起C語言編寫的函數(shù)，實在是吃力不討好，連本人自己看著注釋都有點(diǎn)覺得難懂，不過如果想看懂匯編語言的話先要非常清楚的知道幾個寄存器存放的是什么，再次羅列出來： ;R1為父節(jié)點(diǎn)偏移 ;R2為左孩子偏移 ;R3為右孩子偏移 ;R4為最大節(jié)偏移 ;R5為最大節(jié)點(diǎn)值 ;R6為二叉堆大小 只要清楚的認(rèn)識這幾個寄存器的作用就好多了，不會很暈。參考偽代碼和寄存器作用的注釋，就比較容易看懂這個匯編了。在這里先告訴大家一個好消息是，這個函數(shù)是最復(fù)雜的，下面的幾個操作調(diào)用這個函數(shù)的話，就顯得很簡潔易懂了。 4.2、二叉堆建立 - ASM_BiHeap_Build4.2.1 二叉堆建立的作用 我們把一個普通的數(shù)組構(gòu)建成一個二叉堆，調(diào)用的就是二叉堆建立函數(shù)，可見，二叉堆的建立不改變數(shù)據(jù)的存儲，仍然是一個數(shù)組，但是改變了數(shù)據(jù)的結(jié)構(gòu)，變成層次型了。 4.2.2 二叉堆建立的偽代碼 可以看到非常簡潔的偽代碼，驗證了剛才說的，調(diào)用二叉堆最大化子程序，可以把二叉堆其他操作的實現(xiàn)變得很簡潔。 
4.2.3 二叉堆建立的C語言原形和解釋 C語言原形：void ASM_BiHeap_Build( uint32_t *BiHeap ); 老樣子，BiHeap是二叉堆首地址，調(diào)用該函數(shù)實現(xiàn)二叉堆的建立，把一個普通的數(shù)組建立成一個二叉堆，之后我們就可以對二叉堆實現(xiàn)二叉堆特有的各種操作了。 偽代碼解釋： 1、獲取二叉堆的大小，保存在heap-size[A]中 2、把數(shù)組平均劃分成兩個部分，前半部分和后半部分 3、對前半部分，從Length[A]/2到1，循環(huán)調(diào)用MAX_Heapify，也就是我們上節(jié)實現(xiàn)的二叉堆最大化。 這樣就實現(xiàn)了二叉堆的建立。通俗一點(diǎn)，舉個例子是數(shù)組有10個元素，我們從5（一半）到1，循環(huán)調(diào)用二叉堆最大化，至于為什么這么做能實現(xiàn)二叉堆最大化，大家如果不明白的話網(wǎng)上找資料吧。 4.2.4 二叉堆建立的匯編語言描述;***************************** ******************************* ; 函數(shù)名 : ASM_BiHeap_Build ; 描述 : 二叉堆構(gòu)建 ; 輸入 : R0 --- 二叉堆首地址 ; 輸出 : 無 ; 寄存器 : 無 ; 調(diào)用 : 外部調(diào)用 ;***************************** ******************************* ASM_BiHeap_Build PUSH {R1, LR}
LDR R1, [R0] ;R1為二叉堆大小 LSR R1, #1 ;二叉堆需要最大化個數(shù)
ASM_BiHeap_Build_Loop PUSH {R1-R8} ;入棧 BL ASM_BiHeap_Maxify ;二叉堆最大化 POP {R1-R8} ;出棧
SUB R1, #1 ;遞減二叉堆最大化個數(shù) CMP R1, #0 ;判斷是否為零 BNE ASM_BiHeap_Build_Loop ;不為零, 繼續(xù)循環(huán)
POP {R1, PC} ;返回 ASM_BiHeap_Build_End
老樣子先看懂偽代碼，再順著代碼，看注釋是比較容易理解的，接下來繼續(xù)其他操作。 4.3、二叉堆排序 - ASM_BiHeap_Sort4.3.1 二叉堆排序的作用 二叉堆的排序算是二叉堆的一個附加操作了，因為排序后二叉堆就已經(jīng)不是二叉堆的結(jié)構(gòu)了，而是一個按值的大小排序的數(shù)組了。 4.3.2 二叉堆排序的偽代碼 偽代碼依然是這么的簡潔，同樣也調(diào)用了二叉堆最大化子程序。 
4.3.3 二叉堆最大化的C語言原形和解釋 C語言原形：void ASM_BiHeap_Sort( uint32_t *BiHeap ); 偽代碼解釋： 1、建立二叉堆 2、循環(huán)執(zhí)行Length[A]-1次，每次的操作包含以下： 3、改變循環(huán)變量i，從Length[A]到2 4、交換第一個元素（最大值）與第i個元素的值（交換后最后一個元素是最大值） 5、二叉堆元素個數(shù)減一 6、最大化二叉堆，保持二叉堆性質(zhì)（因為交換了第一個元素和第i個元素值，父節(jié)點(diǎn)可能不是最大值） 4.3.4 二叉堆最大化的匯編語言描述;***************************** ******************************* ; 函數(shù)名 : ASM_BiHeap_Sort ; 描述 : 二叉堆排序 ; 輸入 : R0 --- 二叉堆首地址 ; 輸出 : 無 ; 寄存器 : 無 ; 調(diào)用 : 外部調(diào)用 ;***************************** ******************************* ASM_BiHeap_Sort PUSH {R1-R4, LR}
BL ASM_BiHeap_Build ;建立二叉堆
LDR R1, [R0] ;R1存放二叉堆大小 PUSH {R1}
ASM_BiHeap_Sort_Loop LDR R3, [R0, #4] ;R2為二叉堆首元素 LDR R4, [R0, R1, LSL #2] ;R3為二叉堆最后一個元素
STR R3, [R0, R1, LSL #2] ;最大元素放在二叉堆末尾 STR R4, [R0, #4] ;二叉堆末尾元素放在二叉堆首
SUB R1, #1 ;二叉堆元素個數(shù)減一 STR R1, [R0] ;保存二叉堆元素個數(shù)
PUSH {R1-R8} ;入棧 MOV R1, #1 ;R1為待最大化二叉堆元素 BL ASM_BiHeap_Maxify ;二叉堆最大化 POP {R1-R8} ;出棧
CMP R1, #0 ;比較二叉堆元素是否為零 BNE ASM_BiHeap_Sort_Loop ;不為零, 繼續(xù)排序
POP {R1} ;出棧二叉堆大小 STR R1, [R0] ;重新賦值二叉堆大小
POP {R1-R4, PC} ;返回 ASM_BiHeap_Sort_End
也是從偽代碼到匯編代碼和注釋這樣看。進(jìn)入下一個操作。 4.4、二叉堆鍵值增加 - ASM_BiHeap_KeyInc4.4.1 二叉堆鍵值增加的作用 二叉堆鍵值增加實現(xiàn)二叉堆元素值增加，可以實現(xiàn)優(yōu)先級隊列，算是優(yōu)先級隊列的一個操作吧，增加對應(yīng)的優(yōu)先級。 4.4.2 二叉堆鍵值增加的偽代碼 也是很簡潔，但是這次沒有調(diào)用二叉堆最大化子程序。 
4.4.3 二叉堆鍵值增加的C語言原形和解釋 C語言原形： void ASM_BiHeap_KeyInc( uint32_t *BiHeap, uint32_t Pos, uint32_t NewKey ); 偽代碼解釋： 1、如果鍵值小于原來的鍵值 2、退出 3、賦值新的鍵值（有可能破壞二叉堆結(jié)構(gòu)，新鍵值可能大于父節(jié)點(diǎn)值） 4、循環(huán)保持二叉堆性質(zhì) 5、循環(huán)條件為i大于根節(jié)點(diǎn)位置，并且父節(jié)點(diǎn)值小于子節(jié)點(diǎn)值 6、交換父節(jié)點(diǎn)值與子節(jié)點(diǎn)值 7、修改i的位置為父節(jié)點(diǎn)位置（繼續(xù)循環(huán)，回到4，因為有可能二叉堆性質(zhì)被破壞）, 4.4.4 二叉堆鍵值增加的匯編語言描述;***************************** ******************************* ; 函數(shù)名 : ASM_BiHeap_KeyInc ; 描述 : 二叉堆指定元素鍵值更新 ; 輸入 : R0 --- 二叉堆首地址 ; R1 --- 指定元素偏移 ; R2 --- 新鍵值 ; 輸出 : 無 ; 寄存器 : 無 ; 調(diào)用 : 外部調(diào)用 ;***************************** ******************************* ASM_BiHeap_KeyInc PUSH {R3-R4, LR}
LDR R3, [R0, R1, LSL #2] ;R3為指定元素值 CMP R3, R2 ;比較指定元素與新元素大小 BGT ASM_BiHeap_KeyInc_Exit ;指定元素更大, 退出
STR R2, [R0, R1, LSL #2] ;保存新元素到指定元素
MOV R3, R1, LSR #1 ;R3為父節(jié)點(diǎn)偏移 CMP R3, #0 ;如果父節(jié)點(diǎn)是否大于零 BEQ ASM_BiHeap_KeyInc_Exit ;為零, 退出
ASM_BiHeap_KeyInc_Loop LDR R4, [R0, R3, LSL #2] ;R4為父節(jié)點(diǎn)元素 CMP R4, R2 ;比較父節(jié)點(diǎn)元素與新元素 BGT ASM_BiHeap_KeyInc_Exit ;父節(jié)點(diǎn)大, 滿足二叉堆規(guī)則, 退出
STR R4, [R0, R1, LSL #2] ;小元素放在子節(jié)點(diǎn) STR R2, [R0, R3, LSL #2] ;大元素放在父節(jié)點(diǎn)
MOV R4, R2 ;更新子節(jié)點(diǎn)偏移 MOV R1, R3 ; LSR R3, #1 ;更新父節(jié)點(diǎn)偏移
CMP R3, #0 ;如果父節(jié)點(diǎn)是否大于零 BGT ASM_BiHeap_KeyInc_Loop ;大于零, 繼續(xù)循環(huán)
ASM_BiHeap_KeyInc_Exit POP {R3-R4, PC} ;返回 ASM_BiHeap_KeyInc_End
看懂程序 == 偽代碼 + 匯編代碼 + 注釋，接下來進(jìn)入下一個操作。 4.5、二叉堆元素插入 - ASM_BiHeap_Insert4.5.1 二叉堆元素插入的作用 插入新元素是一種非常常見的操作，二叉堆當(dāng)然也支持這種操作，可以理解為添加一個新成員吧。 4.5.2 二叉堆元素插入的偽代碼 調(diào)用了二叉堆鍵值增加子程序，代碼更加簡潔了。 
4.5.3 二叉堆元素插入的C語言原形和解釋 C語言原形：void ASM_BiHeap_KeyInsert (uint32_t *BiHeap, uint32_t Key) ; 偽代碼解釋： 1、二叉堆元素個數(shù)加一（因為插入了一個新元素） 2、新元素賦值為負(fù)無窮，實際我們用一個很小的數(shù)代替 3、調(diào)用鍵值增加子程序?qū)崿F(xiàn)對應(yīng)元素的賦值（保持了二叉堆的性質(zhì)） 4.5.4 二叉堆元素插入的匯編語言描述;***************************** ******************************* ; 函數(shù)名 : ASM_BiHeap_KeyInsert ; 描述 : 二叉堆元素插入 ; 輸入 : R0 --- 二叉堆首地址 ; R1 --- 新元素鍵值 ; 輸出 : 無 ; 寄存器 : 無 ; 調(diào)用 : 外部調(diào)用 ;***************************** ******************************* ASM_BiHeap_KeyInsert PUSH {R2-R3, LR}
LDR R2, [R0] ;二叉堆大小 ADD R2, #1 ;二叉堆大小加一 STR R2, [R0] ;更新二叉堆大小
MOV R3, #0 ;R3為0 STR R3, [R0, R2, LSL #2] ;新元素值為0
MOV R3, R2 ;R3為新元素位置 MOV R2, R1 ;R2為新元素值 MOV R1, R3 ;R1為新元素位置 BL ASM_BiHeap_KeyInc ;調(diào)用二叉堆指定元素鍵值更新
POP {R2-R3, PC} ;返回 ASM_BiHeap_KeyInsert_End
看懂程序 == 偽代碼 + 匯編代碼 + 注釋，接下來進(jìn)入下一個操作。 4.6、二叉堆最大元素 - ASM_BiHeap_Maximum4.6.1 二叉堆最大元素的作用 查詢二叉堆中最大的元素使用的操作，比較簡單。 4.6.2 二叉堆最大元素的偽代碼
4.6.3 二叉堆最大元素的C語言原形和解釋 C語言原形：uint32_t ASM_BiHeap_Maximum( uint32_t *BiHeap ); 偽代碼解釋：直接返回位置為1的元素 4.6.4 二叉堆最大元素的匯編語言描述 可以說這是最簡單的操作了，代碼： ;***************************** ******************************* ; 函數(shù)名 : ASM_BiHeap_Maximum ; 描述 : 二叉堆返回最大元素 ; 輸入 : R0 --- 二叉堆首地址 ; 輸出 : uint32_t --- 二叉堆最大元素 ; 寄存器 : 無 ; 調(diào)用 : 外部調(diào)用 ;***************************** ******************************* ASM_BiHeap_Maximum LDR R0, [R0, #4] ;獲取二叉堆首元素
BX LR ;返回 ASM_BiHeap_Maximum_End
接下來下一個操作，也是最后一個操作了。 4.7、二叉堆出隊最大元素 - ASM_BiHeap_ExtraMax4.7.1 二叉堆出隊最大元素的作用 出隊實現(xiàn)了返回最大元素的功能，同時將元素從二叉堆移除，也就是出隊后二叉堆就沒有了這個元素。 4.7.2 二叉堆出隊最大元素的偽代碼 還是調(diào)用了二叉堆最大化子程序，變得很簡潔了。 
4.7.3 二叉堆出隊最大元素的C語言原形和解釋 C語言原形：uint32_t ASM_BiHeap_ExtracMax( uint32_t *Arr ); 偽代碼解釋： 1、如果二叉堆元素個數(shù)小于1，返回錯誤 2、把第1個元素（最大元素）放在max 3、最后一個元素放在第1個元素位置（覆蓋了第一個位置的值） 4、二叉堆元素個數(shù)減一（因為出隊） 5、調(diào)用二叉堆最大化子程序保持二叉堆性質(zhì)（最后一個元素放在第一個，可能破壞二叉堆性質(zhì)） 6、返回max（返回最大元素，同時最大元素也已經(jīng)出隊了） 4.7.4 二叉堆出隊最大元素的匯編語言描述;***************************** ******************************* ; 函數(shù)名 : ASM_BiHeap_ExtracMax ; 描述 : 二叉堆返回最大元素 ; 輸入 : R0 --- 二叉堆首地址 ; 輸出 : uint32_t --- 二叉堆最大元素 ; 寄存器 : 無 ; 調(diào)用 : 外部調(diào)用 ;***************************** ******************************* ASM_BiHeap_ExtracMax PUSH {R1-R2, LR}
LDR R1, [R0, #4] ;R1二叉堆最大元素 PUSH {R1} ;入棧保護(hù)最大元素
LDR R1, [R0] ;R1為二叉堆大小 LDR R2, [R0, R1, LSL #2] ;R2為二叉堆最后一個元素 STR R2, [R0, #4] ;最后一個元素放在首元素, 破壞二叉堆結(jié)構(gòu)
SUB R1, #1 ;二叉堆元素個數(shù)減一 STR R1, [R0] ;保存二叉堆元素個數(shù)
PUSH {R2-R8} MOV R1, #1 ;二叉堆待最大化元素 BL ASM_BiHeap_Maxify ;二叉堆最大化 POP {R2-R8}
POP {R0} ;最大元素放在R0 POP {R1-R2, PC} ;返回 ASM_BiHeap_ExtracMax_End
看懂程序 == 偽代碼 + 匯編代碼 + 注釋，最后一個操作也完了。
實現(xiàn)了這些操作之后，我們就開始編寫程序測試這些操作是否正確了，測試程序是用C語言編寫的，也就是用C語言調(diào)用匯編子程序。 第五章 測試5.1 匯編文件的包裝 我們在上一章編寫的只是子程序，對一個匯編文件來說，跟C語言一樣也要包括其他偽指令啊宏定義啊什么的，這一節(jié)我們來看看這么做。需要的操作有： 1、代碼段聲明 2、聲明標(biāo)號為外部的 3、添加END 具體整個文件應(yīng)該是對應(yīng)的一下形式： ;***************************** 接口函數(shù)聲明 ******************************* EXPORT ASM_BiHeap_Build ;二叉堆構(gòu)建 EXPORT ASM_BiHeap_Sort ;二叉堆排序 EXPORT ASM_BiHeap_Maximum ;二叉堆返回最大元素 EXPORT ASM_BiHeap_ExtracMax ;二叉堆返回最大元素 EXPORT ASM_BiHeap_KeyInc ;二叉堆指定元素鍵值更新 EXPORT ASM_BiHeap_KeyInsert ;二叉堆元素插入 ;***************************** *******************************
;***************************** 代碼段聲明 ******************************* AREA |.text|, CODE, READONLY, ALIGN=2 THUMB REQUIRE8 PRESERVE8 ;***************************** *******************************
;***************************** 代碼 ******************************* 匯編子程序 ;***************************** *******************************
END ;**************************************文件結(jié)束****************************
以上格式就是我們的匯編源文件，分別對應(yīng)四個部分。 1、標(biāo)號聲明 2、代碼段聲明 3、代碼段 4、END 其中的匯編子程序就是上一章我們所實現(xiàn)的二叉堆的操作了。 5.2 C語言頭文件 本人為了讓C語言能調(diào)用這些匯編函數(shù)，對應(yīng)編寫了一個C語言的頭文件，聲明這些函數(shù)，具體實現(xiàn)如下：
#ifndef __BIHEAP_H #define __BIHEAP_H
#include "stm32f10x.h"
void ASM_BiHeap_Maxify(uint32_t *Arr, uint32_t Len); //二叉堆最大化 void ASM_BiHeap_Build(uint32_t *Arr); //二叉堆建立 void ASM_BiHeap_Sort(uint32_t *Arr); //二叉堆排序 void ASM_BiHeap_KeyInc(uint32_t *Arr, uint32_t Pos, uint32_t NewKey); //二叉堆鍵值增加 void ASM_BiHeap_KeyInsert(uint32_t *Arr, uint32_t Key); //二叉堆元素插入 uint32_t ASM_BiHeap_Maximum(uint32_t *Arr); //二叉堆最大元素 uint32_t ASM_BiHeap_ExtracMax(uint32_t *Arr); //二叉堆出對最大元素
#endif //#ifndef __BIHEAP_H
5.3 測試 對應(yīng)的C語言測試源文件，這個函數(shù)并沒有測試所有的匯編子程序，不過本人自己都測試過了，這里只是舉個例子：
#include "data_struc.h"
#if BI_HEAP_TEST_EN //如果使能二叉堆測試 static uint32_t Arr[20] = {15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}; //二叉堆, 首元素為二叉堆的元素個數(shù) #endif //#if BI_HEAP_TEST_EN
#if BI_HEAP_TEST_EN //如果使能二叉堆測試 FStat BiHeap_Test(void) { ASM_BiHeap_Build( Arr ); //構(gòu)建二叉堆函數(shù) ASM_BiHeap_KeyInsert( Arr, 10); //添加元素 ASM_BiHeap_KeyInc( Arr, 2, 16 ); //指定元素鍵值增加 printf("%d\n", ASM_BiHeap_ExtracMax( Arr ) );//打印出對元素
return FuncOK; } #endif //#if BI_HEAP_TEST_EN
5.4 測試結(jié)果 測試結(jié)果是本人認(rèn)為是正確的，這里也不貼出來了，畢竟文章也比較長了。如果那里有錯誤歡迎大家指出來，感謝大家啦。 附錄1、C語言的主函數(shù) 
參考文獻(xiàn)[1] 《算法導(dǎo)論》第二版 機(jī)械工業(yè)出版社 [2] 《Cortex-M3權(quán)威指南》 Joseph Yiu 著 宋巖 譯 | 
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
