【正文】 分 程 序 B 1 。 (2) var x:integer。 a[j]:=x (5) end。 (4) var temp:integer。 (10)begin (11) a:=1。writeln(‘ b=‘ ,b) (14)end. 帶有過(guò)程 swap的 PASCAL程序 ? 傳地址（變量參數(shù)） 例如：過(guò)程 swap(var x,y:integer)。 swap(a,b）； 其結(jié)果： a,b調(diào)用前的值不改變。 procedure swap( x,y:integer)。 其結(jié)果等價(jià)于執(zhí)行下列運(yùn)算： x :=a； y :=b； temp :=x； x :=y； y :=temp 傳地址 的實(shí)現(xiàn) （ call by reference )(callbyaddress)(callbylocation) 把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形參，即 調(diào)用過(guò)程把一個(gè)指向?qū)崊⒌拇鎯?chǔ)地址的指針傳遞給被調(diào)用過(guò)程相應(yīng)的形參： 1實(shí)在參數(shù)是一個(gè)名字，或具有左值的表達(dá)式 傳遞左值 2實(shí)在參數(shù)是無(wú)左值的表達(dá)式 計(jì)算值，放入一存儲(chǔ)單元，傳此存儲(chǔ)單元地址 3目標(biāo)代碼中，被調(diào)用過(guò)程對(duì)形參的引用變成對(duì)傳遞給被調(diào)用過(guò)程的指針的間接引用 procedure swap( x,y:integer)。) a1所指單元的內(nèi)容置為 a2所指單元值 4( y :=temp) a2所指單元的內(nèi)容置為 temp的值 (1)swap(x,y) (2)int *x,*y。 *y=temp。 (10)} 在一個(gè)值調(diào)用過(guò)程中使用指針的 C程序 在 C程序中無(wú)傳地址所以用指針實(shí)現(xiàn)。 procedure b(function h(n:integer):integer)。 procedure c。 begin m:=0。 ? (4)procedure c。 ? (8)begin m := 0。 值結(jié)果傳遞與引用傳遞的唯一區(qū)別在于別名的表現(xiàn)不同 。 p(a,a)。 由于名字傳遞的思想是直到在被調(diào)用的程序真正使用了自變量 （ 作為一個(gè)參數(shù) ） 之后才對(duì)這個(gè)自變量賦值 ， 所以它還稱作延盡賦值 （ delayed evaluation） 。因此，若在 p中使用 x之前改變 i，那么它的結(jié)果就與在引用傳遞或在值結(jié)果傳遞中的不同 int i。 } main () {i=1。 return 0。 建立內(nèi)情向量，分配內(nèi)存的目標(biāo)代碼 （ n維可變數(shù)組 , type每個(gè)元素占一個(gè)字） begin k:=1。 m:=m*di。把 n,c,type ,a填進(jìn)內(nèi)情 向量表區(qū) end 賦值中數(shù)組元素的翻譯 A ? V:=E V ? id[elist] | id elist ? elist,E | E V ? elist] | id elist ? elist, E | id [E 結(jié)構(gòu)（記錄），抽象數(shù)據(jù)類型對(duì)象 類實(shí)例變量的存儲(chǔ)結(jié)構(gòu) (CIR) class parent { | class parent{ public int a,b,c。 | ... class child:public parent{ | public d,e。 Ptr=new int(5)； Int *ptr= new int [10] Delete ptr Delete[ ] ptr 堆變量是可以在程序運(yùn)行時(shí)根據(jù)需要隨時(shí)創(chuàng)建或刪除的變量 C++的堆對(duì)象 include Class Myclass{ Public: Myclass()。} ?Myclass()。 CoutDefaultendl。 } 使用 new和 delete的示例 include Int main() { Cout“ one” endl。 Ptr1=new Myclass(5,10)。// default size Class IntArray{ Public: //operations performed on arrays IntArray(int sz=ArraySize)。 int operator[] (int)。 }。isz。 C語(yǔ)言中有這些操作的若干個(gè)版本 ， 但最基本的是 m a l l o c和 f r e e， 它們都是標(biāo)準(zhǔn)庫(kù)（ ） 的一部分 堆式動(dòng)態(tài)存儲(chǔ)分配 需求： 一個(gè)程序語(yǔ)言允許用戶自由地申請(qǐng)數(shù)據(jù)空間和退還數(shù)據(jù)空間 ， 或者不僅有過(guò)程而且有進(jìn)程 （ process）的程序結(jié)構(gòu) ， 操作： 堆提供兩個(gè)操作 ， 分配操作和釋放操作 情況 : 經(jīng)一段運(yùn)行時(shí)間之后，這個(gè)大空間就必定被分劃成許多塊塊，有些占用，有些無(wú)用（空閑） 碎片問(wèn)題 堆式動(dòng)態(tài)儲(chǔ)分配 當(dāng)運(yùn)行程序要求一塊體積為 N的空間時(shí)，我們應(yīng)該分配哪一塊給它呢？ 運(yùn)行程序要求一塊體積為 N的空間，但發(fā)現(xiàn)沒(méi)有比 N大的空閑塊了，然而所有空閑塊的總和卻要比 N大得多 如果運(yùn)行程序要求一塊積為 N的空間，但所有空閑塊的總和也不夠 N，那又應(yīng)怎么辦呢？有的管理系統(tǒng)采用一種叫做垃圾回收的辦法來(lái)對(duì)付這種局面。 歸還時(shí) ， 把所歸還的塊插入鏈表 。按照用戶的需要，分配時(shí)先是從一個(gè)整塊里分割出滿足需要的一小塊，以后，歸還時(shí)，如果新歸還的塊和現(xiàn)有的空間能合并，則合并成一塊；如果不能和任何空閑塊合并，則可以把空閑塊鏈成一個(gè)鏈表。 （ 1） 首次滿足法：只要在空閑塊鏈表中找到滿足需要的一塊 ，就進(jìn)行分配 。 只需從鏈表中刪除第一個(gè)結(jié)點(diǎn) ， 并將其中一部分分配給用戶 ， 而其它部分作為一個(gè)新的結(jié)點(diǎn)插入到空閑塊表的適當(dāng)置上去 。 unsigned freesize。//數(shù)據(jù)類型 Header保存每個(gè)存儲(chǔ)塊的簿記信息 static Header mem [MEMSIZE]。 nunits= (nbytes+sizeof (Header)1/ sizeof (Header)+1。 } for (p=memptr。 /* no block big enough */ newp = p+ps. usedsize。 ps. freesize=0。 } void free (void *ap) {Header * bp, *p, *prev。 prev=p, p=ps. next)。 memptr = prev。 垃圾回收 垃圾回收程序 尋找可被引用的所有存儲(chǔ)器并釋所有未引用的存儲(chǔ)器。 存儲(chǔ)塊格式： 塊長(zhǎng)度 訪問(wèn)計(jì)數(shù)標(biāo)記 指針 用戶使用空間 回收過(guò)程 分為兩個(gè)階段 。 面向?qū)ο蟮恼Z(yǔ)言中的動(dòng)態(tài)存儲(chǔ)器 面向?qū)ο蟮恼Z(yǔ)言在運(yùn)行時(shí)環(huán)境中要求特殊的機(jī)制以完成其增添的特性：對(duì)象 、 方法 、繼承以及動(dòng)態(tài)聯(lián)編 。 另外一種方法是在執(zhí)行時(shí)將類結(jié)構(gòu)的一個(gè)完整的描述保存在每個(gè)點(diǎn)的存儲(chǔ)器中，并由超類指針維護(hù)繼承性（有時(shí)這也稱作繼承圖（ inheritance graph））。其缺 在于：雖然實(shí)例變量具有可預(yù)測(cè)的偏移量（正如在標(biāo)準(zhǔn)環(huán)境中的局部變量一樣），方法卻沒(méi)有，而且它們必須由帶有查詢功能的符號(hào)表結(jié)構(gòu)中的名字維護(hù)。 現(xiàn)在每個(gè)對(duì)象都包括了一個(gè)指向相應(yīng)的虛擬函數(shù)表而不是類結(jié)構(gòu)的指針 （ 當(dāng)然 ，這個(gè)指針的位置必須也有可預(yù)測(cè)的偏移量 ） 。 }。 }。 void f()。 void f()。 C++中選擇的方法 將整個(gè)類結(jié)構(gòu)保存在環(huán)境中 ， 計(jì)算出每個(gè)類的可用方法的代碼指針列表 ， 并將其作為一個(gè)虛擬函數(shù)表 （ virtual function table） 而存放在（ 靜態(tài) ） 存儲(chǔ)器 。此時(shí)，只記錄一次方法指針（在類結(jié)構(gòu)中），而且對(duì)于每個(gè)對(duì)象并不將其復(fù)制到存儲(chǔ)器中。 Smalltalk要求與 LISP相似的完全動(dòng)態(tài)環(huán)境 C＋＋則保持 C的基于棧的環(huán)境 實(shí)現(xiàn)對(duì)象 實(shí)現(xiàn)對(duì)象的一個(gè)簡(jiǎn)單機(jī)制是，初始化代碼將所有當(dāng)前的繼承特征（和方法）直接地復(fù)制到記錄結(jié)構(gòu)中（將方法當(dāng)作代碼指針）。 如果某個(gè)塊被訪問(wèn)過(guò) ， 就給這個(gè)塊加一個(gè)標(biāo)記 。 方法 對(duì) malloc的調(diào)用失敗，激活垃圾回收程序 垃圾回收算法 mark and sweep 隱式存儲(chǔ)回收 —mark and sweep算法 隱式存儲(chǔ)回收要求用戶程序和支持運(yùn)行的回收子程序并行工作，因?yàn)榛厥粘绦蛐枰婪峙浣o用戶程序的存儲(chǔ)塊何時(shí)不再使用。 自動(dòng)存儲(chǔ)器管理涉及到了前面分配的但不再使用的存儲(chǔ)器的回收 ， 可能是在它被分配的很久以后 ，而沒(méi)有明確的對(duì) free的調(diào)用 。 /* corrupted list, do nothing */ prevs. freesize += ps. usedsize + ps. freesize。 for (prev= memptr, p=memptrs. next。 memptr=newp。 newps. freesize = ps. freesizenunits。 p=ps. next)。 memptrs. usedsize = 1。 void *malloc (unsigned nbytes) {Header *p, *newp。 Align a。 typedef union header {struct {union header *next。 （ 3） 最差滿足法：將空閑塊表中不小于申請(qǐng)塊且是最大的空閑的一部全分配給用戶 。若空閑塊表中有若干個(gè)滿足需要的空閑塊時(shí)，該分配哪一塊呢？通常有三種不同的分配策略 不同的情況應(yīng)采用不同的方法。 2 變長(zhǎng)塊管理 除了按定長(zhǎng)塊進(jìn)行分配之外，還可以根據(jù)需要分配長(zhǎng)度不同的存儲(chǔ)塊，可以隨要求而變。初始化時(shí) ， 將堆存儲(chǔ)空間分成長(zhǎng)度相等的若干塊 ， 每塊中指定一個(gè)鏈域 ， 按照鄰塊的順序把所有塊鏈成一個(gè)鏈表 ， 用指針 available指向鏈表中的第一塊 。 } C++語(yǔ)言中 new操作符施加在一個(gè)類型標(biāo)識(shí)符上 （ 包括類名 ） Pascal語(yǔ)言中 ， 標(biāo)準(zhǔn)過(guò)程 new能夠動(dòng)態(tài)建立存儲(chǔ)空間并相應(yīng)地置上指針 。 // allocate an integ