新聞中心

EEPW首頁(yè) > 嵌入式系統(tǒng) > 牛人業(yè)話 > C語(yǔ)言的那些小秘密之堆棧

C語(yǔ)言的那些小秘密之堆棧

作者: 時(shí)間:2015-03-02 來(lái)源:網(wǎng)絡(luò) 收藏
編者按:何為堆棧?首先要明確堆棧是兩種數(shù)據(jù)結(jié)構(gòu)。棧是硬件,堆是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu),但是它們倆個(gè)又是如何共存的呢?  

  在講解之前,我們先要來(lái)說(shuō)說(shuō)其實(shí)我們常說(shuō)的是兩種數(shù)據(jù)結(jié)構(gòu)。那么什么是堆什么又是棧呢?

本文引用地址:http://m.butianyuan.cn/article/270300.htm

  棧,是硬件。主要作用表現(xiàn)為一種數(shù)據(jù)結(jié)構(gòu),是只能在某一端插入和刪除的特殊線性表。它按照后進(jìn)先出的原則存儲(chǔ)數(shù)據(jù),先進(jìn)入的數(shù)據(jù)被壓入棧底,最后的數(shù)據(jù)在棧頂,需要讀數(shù)據(jù)的時(shí)候從棧頂開(kāi)始彈出數(shù)據(jù)(最后一個(gè)數(shù)據(jù)被第一個(gè)讀出來(lái))。棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top),另一端為棧底(bottom);棧底固定,而棧頂浮動(dòng);棧中元素個(gè)數(shù)為零時(shí)稱為空棧。插入一般稱為進(jìn)棧(PUSH),刪除則稱為退棧(POP)。 棧也稱為先進(jìn)后出表。棧可以用來(lái)在函數(shù)調(diào)用的時(shí)候存儲(chǔ)斷點(diǎn),做遞歸時(shí)要用到棧!

  以上定義是在經(jīng)典計(jì)算機(jī)科學(xué)中的解釋。

  在計(jì)算機(jī)系統(tǒng)中,棧則是一個(gè)具有以上屬性的動(dòng)態(tài)內(nèi)存區(qū)域。程序可以將數(shù)據(jù)壓入棧中,也可以將數(shù)據(jù)從棧頂彈出。在i386機(jī)器中,棧頂由稱為esp的寄存器進(jìn)行定位。壓棧的操作使得棧頂?shù)牡刂窚p小,彈出的操作使得棧頂?shù)牡刂吩龃蟆?/p>

  棧在程序的運(yùn)行中有著舉足輕重的作用。最重要的是棧保存了一個(gè)函數(shù)調(diào)用時(shí)所需要的維護(hù)信息,這常常稱之為幀或者活動(dòng)記錄。堆棧幀一般包含如下幾方面的信息:

  1. 函數(shù)的返回地址和參數(shù)

  2. 臨時(shí)變量:包括函數(shù)的非靜態(tài)局部變量以及編譯器自動(dòng)生成的其他臨時(shí)變量。

  堆,是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu),實(shí)際上就是數(shù)據(jù)段中的自由存儲(chǔ)區(qū),它是中使用的一種名稱,常常用于動(dòng)態(tài)數(shù)據(jù)的存儲(chǔ)分配。堆中存入一數(shù)據(jù),總是以2字節(jié)的整數(shù)倍進(jìn)行分配,地址向增加方向變動(dòng)。堆可以不斷進(jìn)行分配直到?jīng)]有堆空間為止,也可以隨時(shí)進(jìn)行釋放、再分配,不存在次序問(wèn)題。

  堆和棧在使用時(shí)相向生長(zhǎng),棧向上生長(zhǎng),即向小地址方向生長(zhǎng),而堆向下增長(zhǎng),即向大地址方向,其間剩余部分是自由空間。使用過(guò)程中要防止增長(zhǎng)過(guò)度而導(dǎo)致覆蓋。

  一般的程序我們都是使用小內(nèi)存模式。

  明白了堆和棧的概念之后我們來(lái)看一個(gè)面試的c語(yǔ)言題目。代碼要相關(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;

  }

  剛剛一開(kāi)始看到這個(gè)題目時(shí),你可能有點(diǎn)發(fā)懵,心想可能在不傳遞參數(shù)的情況下打印arr數(shù)組的內(nèi)容,但是看看我們的標(biāo)題就應(yīng)該知道該題跟棧有關(guān)系,在做之前我們先來(lái)回顧幾個(gè)知識(shí)點(diǎn)。

  push操作先修改指針,后將信息入棧。

  ESP為堆棧指針,棧頂有ESP寄存器來(lái)定位。壓棧的操作使得棧頂?shù)牡刂窚p小,彈出的操作使得棧頂?shù)牡刂吩龃蟆?/p>

  EBP是32位的BP,EBP是基址指針,EBP與BP的關(guān)系就像AX與AL、AH的關(guān)系一樣。BP為基指針寄存器,用它課直接存取堆棧中的數(shù)據(jù),他的作用在調(diào)用函數(shù)時(shí)保存ESP,使函數(shù)結(jié)束時(shí)可以正確返回。

  c的默認(rèn)函數(shù)壓棧操作為:

  參數(shù)是從右向左壓棧的,默認(rèn)四字節(jié)對(duì)齊,函數(shù)里面定義的變量是默認(rèn)對(duì)齊方式----變量首地址是自身結(jié)構(gòu)體里邊最大標(biāo)準(zhǔn)數(shù)據(jù)類型字節(jié)的整數(shù)倍。

  我們先來(lái)看看上面這段代碼的匯編語(yǔ)句:

  //*******************************************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*********************************************//

  看看上面的匯編代碼,我們的重點(diǎn)放在紅色字體部分,在函數(shù)的開(kāi)頭部分都有這么兩行代碼:

 pushl %ebp --------------------------->保存上一個(gè)函數(shù)的棧底

  movl %esp, %ebp --------------------------->用來(lái)保存當(dāng)前堆棧指針的值

  ebp存放當(dāng)前函數(shù)棧低的地址,就是說(shuō)ebp可以看做一個(gè)指針,指向棧頂,而其實(shí)棧頂存放的數(shù)據(jù)就是上一個(gè)函數(shù)的ebp的值,即就是main函數(shù)的棧底。

c語(yǔ)言相關(guān)文章:c語(yǔ)言教程



上一頁(yè) 1 2 下一頁(yè)

關(guān)鍵詞: C語(yǔ)言 堆棧

評(píng)論


相關(guān)推薦

技術(shù)專區(qū)

關(guān)閉