|
在講解堆棧之前，我們先要來說說其實我們常說的堆棧是兩種數(shù)據(jù)結(jié)構(gòu)。那么什么是堆什么又是棧呢? 棧，是硬件。主要作用表現(xiàn)為一種數(shù)據(jù)結(jié)構(gòu)，是只能在某一端插入和刪除的特殊線性表。它按照后進(jìn)先出的原則存儲數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)(最后一個數(shù)據(jù)被第一個讀出來)。棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom);棧底固定，而棧頂浮動;棧中元素個數(shù)為零時稱為空棧。插入一般稱為進(jìn)棧(PUSH)，刪除則稱為退棧(POP)。 棧也稱為先進(jìn)后出表。棧可以用來在函數(shù)調(diào)用的時候存儲斷點，做遞歸時要用到棧! 以上定義是在經(jīng)典計算機科學(xué)中的解釋。 在計算機系統(tǒng)中，棧則是一個具有以上屬性的動態(tài)內(nèi)存區(qū)域。程序可以將數(shù)據(jù)壓入棧中，也可以將數(shù)據(jù)從棧頂彈出。在i386機器中，棧頂由稱為esp的寄存器進(jìn)行定位。壓棧的操作使得棧頂?shù)牡刂窚p小，彈出的操作使得棧頂?shù)牡刂吩龃蟆?br /> 棧在程序的運行中有著舉足輕重的作用。最重要的是棧保存了一個函數(shù)調(diào)用時所需要的維護(hù)信息，這常常稱之為堆棧幀或者活動記錄。堆棧幀一般包含如下幾方面的信息： 1. 函數(shù)的返回地址和參數(shù) 2. 臨時變量：包括函數(shù)的非靜態(tài)局部變量以及編譯器自動生成的其他臨時變量。 堆，是一種動態(tài)存儲結(jié)構(gòu)，實際上就是數(shù)據(jù)段中的自由存儲區(qū)，它是C語言中使用的一種名稱，常常用于動態(tài)數(shù)據(jù)的存儲分配。堆中存入一數(shù)據(jù)，總是以2字節(jié)的整數(shù)倍進(jìn)行分配，地址向增加方向變動。堆可以不斷進(jìn)行分配直到?jīng)]有堆空間為止，也可以隨時進(jìn)行釋放、再分配，不存在次序問題。 堆和棧在使用時相向生長，棧向上生長，即向小地址方向生長，而堆向下增長，即向大地址方向，其間剩余部分是自由空間。使用過程中要防止增長過度而導(dǎo)致覆蓋。 一般的程序我們都是使用小內(nèi)存模式。 明白了堆和棧的概念之后我們來看一個面試的c語言題目。代碼要相關(guān)要求如下所示： #include using namespace std; void print() { //這里進(jìn)行打印arr數(shù)組，print不準(zhǔn)傳參數(shù) } int main() { int s=0; int ss=0; char *str="fdsafdsafdsafdsafdsafdsafdsa"; char fdsa='f'; char srt[8]; int arr[]={32,43,3,567,987,21,56};//數(shù)值隨即 print(); return 0; } 剛剛一開始看到這個題目時，你可能有點發(fā)懵，心想可能在不傳遞參數(shù)的情況下打印arr數(shù)組的內(nèi)容，但是看看我們的標(biāo)題就應(yīng)該知道該題跟棧有關(guān)系，在做之前我們先來回顧幾個知識點。 push操作先修改指針，后將信息入棧。 ESP為堆棧指針，棧頂有ESP寄存器來定位。壓棧的操作使得棧頂?shù)牡刂窚p小，彈出的操作使得棧頂?shù)牡刂吩龃蟆?br /> EBP是32位的BP，EBP是基址指針，EBP與BP的關(guān)系就像AX與AL、AH的關(guān)系一樣。BP為基指針寄存器，用它課直接存取堆棧中的數(shù)據(jù)，他的作用在調(diào)用函數(shù)時保存ESP，使函數(shù)結(jié)束時可以正確返回。 c的默認(rèn)函數(shù)壓棧操作為： 參數(shù)是從右向左壓棧的，默認(rèn)四字節(jié)對齊，函數(shù)里面定義的變量是默認(rèn)對齊方式----變量首地址是自身結(jié)構(gòu)體里邊最大標(biāo)準(zhǔn)數(shù)據(jù)類型字節(jié)的整數(shù)倍。 我們先來看看上面這段代碼的匯編語句： //*******************************************start*********************************************// .file "push.c" .text .globl print .type print, @function print: pushl %ebp movl %esp, %ebp popl %ebp ret .size print, .-print .section .rodata .LC0: .string "fdsafdsafdsafdsafdsafdsafdsa" .text .globl main .type main, @function main: pushl %ebp movl %esp, %ebp andl $-16, %esp subl $64, %esp movl %gs:20, %eax movl %eax, 60(%esp) xorl %eax, %eax movl $0, 44(%esp) movl $0, 40(%esp) movl $.LC0, 36(%esp) movb $102, 51(%esp) movl $32, 8(%esp) movl $43, 12(%esp) movl $3, 16(%esp) movl $567, 20(%esp) movl $987, 24(%esp) movl $21, 28(%esp) movl $56, 32(%esp) call print movl $0, %eax movl 60(%esp), %edx xorl %gs:20, %edx je .L3 call __stack_chk_fail .L3: leave ret .size main, .-main .ident "GCC: (Ubuntu/Linaro 4.5.2-8ubuntu4) 4.5.2" .section .note.GNU-stack,"",@progbits //*******************************************end*********************************************// 看看上面的匯編代碼，我們的重點放在紅色字體部分，在函數(shù)的開頭部分都有這么兩行代碼： pushl %ebp --------------------------->保存上一個函數(shù)的棧底 movl %esp, %ebp --------------------------->用來保存當(dāng)前堆棧指針的值 ebp存放當(dāng)前函數(shù)棧低的地址，就是說ebp可以看做一個指針，指向棧頂，而其實棧頂存放的數(shù)據(jù)就是上一個函數(shù)的ebp的值，即就是main函數(shù)的棧底。 明白了上面的內(nèi)容，那么我們就可以實現(xiàn)題目的要求了。代碼如下所示： #include using namespace std; void print() { //這里進(jìn)行排序，print不準(zhǔn)傳參數(shù) unsigned int _ebp; __asm{ mov _ebp,ebp } int *p=(int *)(*(int *)_ebp-4-4-4-4-8-7*4); for(int i=0;i 為了強調(diào)默認(rèn)的字節(jié)對齊概念，我們再來修改下代碼得到的運行結(jié)果可以上面得做一個比較。 代碼如下，紅色部分為修改代碼。 #include using namespace std; void print() { //這里進(jìn)行排序，print不準(zhǔn)傳參數(shù) unsigned int _ebp; __asm{ mov _ebp,ebp } int *p=(int *)(*(int *)_ebp-4-4-4-4-8-7*4); for(int i=0;i 如果我們修改了 char srt[6];之后去把int *p=(int *)(*(int *)_ebp-4-4-4-4-8-7*4);修改為int *p=(int *)(*(int *)_ebp-4-4-4-4-6-7*4);，注意紅色部分的對比，運行結(jié)果就變?yōu)榱耍?br /> 顯然對比可知運行結(jié)果出錯了。在此多次一舉的給出對比無非是為了大家能夠?qū)ψ止?jié)的對齊方式加以重視。當(dāng)然以上內(nèi)容難免有錯，畢竟c語言博大精深，如果有不正確的地方，請糾正。 |
