算法與數(shù)據(jù)結(jié)構(gòu)

AlgorithmsandDataStructures

第八章動(dòng)態(tài)存儲(chǔ)管理算法與數(shù)據(jù)結(jié)構(gòu)

AlgorithmsandDataSt1第八章動(dòng)態(tài)存儲(chǔ)管理8.1概述內(nèi)存是很重要的、很昂貴的資源，如何合理高效地使用這一資源是一個(gè)比較復(fù)雜的問題。早期使用低級(jí)語言編程，內(nèi)存管理是由程序員自己負(fù)責(zé)。程序員負(fù)擔(dān)重，管理水平因人而異，管理效率低，容易出錯(cuò)。隨著操作系統(tǒng)和高級(jí)語言的發(fā)展，情況不斷改善。內(nèi)存管理分別由操作系統(tǒng)、高級(jí)語言的編譯系統(tǒng)和程序員分工合作管理。通常編譯系統(tǒng)負(fù)責(zé)靜態(tài)儲(chǔ)存管理，操作系統(tǒng)負(fù)責(zé)整個(gè)內(nèi)存管理和動(dòng)態(tài)儲(chǔ)存管理。

第八章動(dòng)態(tài)存儲(chǔ)管理8.1概述2程序員級(jí)的管理：用戶程序中所用的儲(chǔ)存結(jié)構(gòu)有兩種，靜態(tài)結(jié)構(gòu)

：空間量在編譯后，即可確定動(dòng)態(tài)結(jié)構(gòu)：程序運(yùn)行中申請空間，編譯時(shí)無法確定。靜態(tài)儲(chǔ)存由編譯系統(tǒng)管理。動(dòng)態(tài)儲(chǔ)存由程序員和操作系統(tǒng)管理，但程序員的管理非常簡單。程序員的工作就是在需要的時(shí)候向系統(tǒng)申請空間，在不需要時(shí)釋放要來的動(dòng)態(tài)儲(chǔ)存空間：C語言中：malloc(size),申請size字節(jié)的內(nèi)存； free(p),釋放p，歸還給系統(tǒng)；C++中：newobjectType(),申請空間；free(p),釋放p，歸還給系統(tǒng)；程序員級(jí)的管理：3Java語言中：newobjectType(),申請空間；用戶程序：#includeiostd.lib……Intmain(){…*r=newint[100];…free(r);…}操作系統(tǒng)分配OS_AllocMemory(r,size,flags)回收OS_ReclaimMemory(r)FreeMemFreeMemrFreeMemJava語言中：newobjectTyp4編譯系統(tǒng)級(jí)管理在編譯中，編譯系統(tǒng)為程序設(shè)置了一個(gè)虛擬空間，它管理的是虛擬空間。用戶程序：…intx,y;floatr,s;charstr[10];………虛擬空間：x:4bytesy:4bytesstr:10bytesr:4bytess:4bytes048121626內(nèi)存程序裝入時(shí)，重定位編譯原理與技術(shù)中將做介紹。編譯系統(tǒng)級(jí)管理用戶程序：虛擬空間：x:4bytesy:45操作系統(tǒng)級(jí)管理：

存儲(chǔ)管理是操作系統(tǒng)的重要部分之一，操作系統(tǒng)對(duì)儲(chǔ)存的管理是才是真實(shí)的管理，而且這一管理是很復(fù)雜的。操作系統(tǒng)的存儲(chǔ)管理為程序代碼和靜態(tài)數(shù)據(jù)分配空間為程序動(dòng)態(tài)分配空間回收不用的動(dòng)態(tài)空間回收空間程序代碼和靜態(tài)數(shù)據(jù)空間分配回收執(zhí)行程序執(zhí)行完畢或撤消執(zhí)行程序程序NewOtype()Free(p)操作系統(tǒng)級(jí)管理：操作系統(tǒng)的存儲(chǔ)管理分回執(zhí)行程序執(zhí)行完畢或撤消6從外部來看，操作系統(tǒng)存儲(chǔ)管理系統(tǒng)就是提供存儲(chǔ)空間分配和回收服務(wù)，但內(nèi)部實(shí)現(xiàn)方法卻十分復(fù)雜，不同的操作系統(tǒng)采用不同的策略和方法，這些問題將在后續(xù)課程操作系統(tǒng)中詳細(xì)介紹。這里我們只是站在數(shù)據(jù)結(jié)構(gòu)的角度來討論動(dòng)態(tài)存儲(chǔ)管理的基本方法，即存儲(chǔ)空間的分配和回收基礎(chǔ)技術(shù)、存儲(chǔ)空間的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。

從外部來看，操作系統(tǒng)存儲(chǔ)管理系統(tǒng)就是提供存儲(chǔ)78.2可利用空間表初試狀態(tài)OSbootOS占用空間freetagsizelink一個(gè)連續(xù)的存儲(chǔ)空間稱為“塊”[block]Tag：標(biāo)記空間是否分配Size：空間大小Link：指向下一個(gè)空閑塊初試狀態(tài)：除了操作系統(tǒng)占用的空間外，其它空間形成一個(gè)空閑塊。當(dāng)空閑塊多時(shí)，用link鏈成一個(gè)鏈表，該鏈表就是可利用空間表。初試此表中只有一個(gè)空閑塊。表指針是free。8.2可利用空間表OSbootOS占用空間free8經(jīng)過多次分配、回收之后，形成了多個(gè)空閑塊，它們之間不連續(xù)，如圖所示：Freeused1used2used3used4used523456Free1136542經(jīng)過多次分配、回收之后，形成了多個(gè)空閑塊，它們之間不連續(xù)，如9可利用空間表的鏈接順序有：（1）按塊的首地址有低到高鏈接；（2）按塊的大小有小到大鏈接；（3）按塊的大小有大到小鏈接；分配：一般有3種策略，設(shè)申請空間的大小為n（1）首次擬合法：從表頭開始搜索，遇到第一個(gè)尺寸等于大于n的塊進(jìn)行分配；（2）最佳擬合法：搜索整個(gè)表，將最小的等于大于n的塊進(jìn)行分配；（3）最差擬合法：搜索整個(gè)表，將最大塊進(jìn)行分配（等于大于n）；可利用空間表的鏈接順序有：10分配過程：找到合適的空閑塊p；P.size等于n或比n大少許（一般設(shè)定一個(gè)量s），則將p從表中刪除，進(jìn)行分配；若p.size>n+s，從p的下部切割size為n的一塊進(jìn)行分配，如圖所示：n=16k064kp116k48k分配過程：064kp116k48k11回收: 程序釋放空間(如free(p))、程序運(yùn)行結(jié)束后將占用的塊歸還系統(tǒng)，如果收回的塊的相鄰塊是空閑的，需要合并它們?；厥者^程：設(shè)釋放塊是p，大小為size。（1）設(shè)置p.tag=0；（2）判斷p的下相鄰塊q是否空閑 若空閑：從可利用空間表摘出q，置p.size=p.size+q.size(合并)；（3）判斷p的上相鄰塊r是否空閑若空閑：合并r和p，r.size=r.size+p.size否則：將p插入可利用空間表?；厥? 程序釋放空間(如free(p))、程序運(yùn)行結(jié)束后將占12例如：Freeused1used2used3used4used523456Free1136542釋放used104k11knull06k12used104k07knull12used1011k12used1例如：Freeused1used2used3used4us13有時(shí)也不必馬上合并，如果釋放塊p的大小恰好符合下次申請空間的要求，可以將p分配，而不必從可利用空間表中切割分配。Free136542used1有時(shí)也不必馬上合并，如果釋放塊p的大小恰好符14例如，一個(gè)使用單鏈表的程序，它會(huì)不斷地申請和釋放同類型的結(jié)點(diǎn)（塊大小相等），回收時(shí)不進(jìn)行合并，而是放在另一個(gè)鏈表avail中；分配時(shí)首先從avail取一個(gè)塊分配，當(dāng)avail中沒有空閑塊時(shí)在從free表里分配。這樣就省去了不斷地合并切割的麻煩，可以提高效率。對(duì)于一些小的操作系統(tǒng)，內(nèi)存管理相對(duì)簡單些。在許多專用設(shè)備、智能儀表和家用電器等都使用一種小型的、高效的、簡單的操作系統(tǒng)，一般稱之為“嵌入式操作系統(tǒng)”。下面介紹一些實(shí)用而簡單的動(dòng)態(tài)存儲(chǔ)管理系統(tǒng)。例如，一個(gè)使用單鏈表的程序，它會(huì)不斷地申請和釋放同類型的結(jié)點(diǎn)158.3伙伴系統(tǒng)（Buddysystem）特點(diǎn)：（1）分配塊的大小均是2k;（2）分配和回收簡單可利用空間表結(jié)構(gòu)：202122...2k2m0k0k0k^^^內(nèi)存最大空間是2m空閑塊按其大小鏈入各自的鏈表；該數(shù)組是各鏈表的表頭接點(diǎn)同尺寸的空閑塊構(gòu)成雙向循環(huán)鏈表；有4個(gè)域：tag標(biāo)記，0空閑，1占用，k:塊的大小2k,llink:q前驅(qū)指針，rlingk:后繼指針8.3伙伴系統(tǒng)（Buddysystem）200k0k016伙伴系統(tǒng)抽象數(shù)據(jù)類型ADTBoddySystemData:intm //可用內(nèi)存2mFreeHeadList //m個(gè)表頭結(jié)點(diǎn)構(gòu)成的線性表BlockScrpt //塊描述 Memory //整個(gè)內(nèi)存空間opration:BS_malloc(size) //分配內(nèi)存BS_reclaim(BlockScrptbp)//回收內(nèi)存EndBlockSystem伙伴系統(tǒng)抽象數(shù)據(jù)類型17ClassFreeHeadNode{intsizePower;//k2kBlockScrptfirst;//鏈表指針}//ClassFreeHeadNode

ClassFreeHeadList{intm;//FreeHeadNode[]list;publicFreeHeadList(intn){m=n;list=newFreeHeadNode[m];}for(k=0;k<=m;k++){list[k].sizePower=k;first=null;}}//ClassFreeHeadList

kfirst0123..m-1m^^^^^ClassFreeHeadNode{kfirst0^^^18塊描述ClassBlockScrpt{intsizePower; booleanused; BlockScrptllink,rlink;intadd;public

BlockScrpt(intk,booleanb,intaddr){sizePower=k;used=b;add=addr;}//BlockScrpt}//ClassBlockScrpt

塊描述19伙伴系統(tǒng)結(jié)構(gòu)ClassBuddySystem{intm; //最大可用內(nèi)存2mBlockHeadListheadList //表頭向量BlockScrptblkScrpt; //塊描述Byte[]mem; //內(nèi)存publicBuddySystem(intk){//構(gòu)造函數(shù)m=k;headList=newBlockHeadList(m);blkScrpt=newBlockScrpt(m,false,0);

伙伴系統(tǒng)結(jié)構(gòu)20blkScrpt.llink=blkscrpt;blkScrpt.rlink=blkscrpt;headList[m].first=blkScrptmem=newByte[2m];}//BlockScrptBS_malloc(intk){……}voidBS_reclaim(BlockScrptbp){……}}//ClassBuddySystem

blkScrpt.llink21初始狀態(tài)012..k..mfalsem00122m-1headListmemBlockScrpt初始狀態(tài)0falsem00headListmemBlockS22分配26之后..67..k.m-1mfalsem-12m-102m-12m-1headListmemfalsek2kfalse727true60false626分配26之后..falsem-12m-10headLis23分配算法思想：申請空間量為2k；從k到m依次搜尋非空鏈表 若無：內(nèi)存不夠，結(jié)束；若有：設(shè)為headList[j]k=<j<=m若j=k:從headList[k]中取一結(jié)點(diǎn)分配，結(jié)束；若j>k:從headList[j]取一結(jié)點(diǎn)bs(1)將bs均分為二，高地址部分插入headList[j-1];j--;(2)重復(fù)（1）直到j(luò)=k；4將bs分配；結(jié)束；分配算法思想：24BlockScrptBS_malloc(intk){

for(j=k;j<=m;j++)//找非空鏈表if(!headList[j].first)break;if(j>m)returnnull;//無非空鏈表，分配失敗bs=headList[j].delet(1);

//從非空鏈表中取第一個(gè)接點(diǎn)；for(s=j;s>k;s--){//將大塊分割；bst=newBlockScrpt(s-1,false,bs.add+2s-1);headList[s-1].insert(bst);bs.sizePower--;}//forbs.used=true;returnbs;//分配bs}//Trues-1Falses-1bstbsBlockScrptBS_malloc(intk){25回收算法思想

伙伴系統(tǒng)的一個(gè)重要特點(diǎn)是：任何塊（除最大塊外）都有唯一的一個(gè)伙伴，所謂伙伴即：大小一樣且相鄰；空閑的相鄰塊是可以合并的；一個(gè)塊的伙伴地址是什么？設(shè)塊的首地址是p，其伙伴的首地址是：

Buddy(p,k)=p+2k(ifpMOD2k+1=0)=p

+2k(ifpMOD2k+1=2k)回收算法思想26設(shè)回收的塊是bsk=bs.sizePower;p=bs.add;計(jì)算伙伴地址q=buddy(p,k);從headList[k]鏈表中找add等于q的塊描述bst，若無：伙伴占用，將bs插入headList[k],結(jié)束；否則：將bs和bst合并，用bs描述。K++;重復(fù)3直到k>m;將bs插入headList[m]。

設(shè)回收的塊是bs278.4一個(gè)小型的動(dòng)態(tài)存儲(chǔ)管理系統(tǒng)8.4一個(gè)小型的動(dòng)態(tài)存儲(chǔ)管理系統(tǒng)28算法6.8:中序遍歷線索二叉樹算法6.8:中序遍歷線索二叉樹29算法6.9:求p的后繼（p在前序序列中的后繼)算法6.9:求p的后繼（p在前序序列中的后繼)30算法6.10:前序遍歷線索二叉樹算法6.10:前序遍歷線索二叉樹316.4森林與二叉樹6.4森林與二叉樹326.5歸并查找集（MergeFindSetMFS）6.5歸并查找集（MergeFindSetMF33改進(jìn)后算法：

改進(jìn)后算法：34算法與數(shù)據(jù)結(jié)構(gòu)課件35Huffman算法：Huffman算法：36算法6.11Huffman編碼算法6.11Huffman編碼37 voidinitiate(charc[],floatw[]){

voidinitiate(charc[],float38voidselectMin(intk,int&s,int&t){

voidselectMin(intk,int39voidgetCode(){voidgetCode(){40算法與數(shù)據(jù)結(jié)構(gòu)課件41算法與數(shù)據(jù)結(jié)構(gòu)

AlgorithmsandDataStructures

第八章動(dòng)態(tài)存儲(chǔ)管理算法與數(shù)據(jù)結(jié)構(gòu)

AlgorithmsandDataSt42第八章動(dòng)態(tài)存儲(chǔ)管理8.1概述內(nèi)存是很重要的、很昂貴的資源，如何合理高效地使用這一資源是一個(gè)比較復(fù)雜的問題。早期使用低級(jí)語言編程，內(nèi)存管理是由程序員自己負(fù)責(zé)。程序員負(fù)擔(dān)重，管理水平因人而異，管理效率低，容易出錯(cuò)。隨著操作系統(tǒng)和高級(jí)語言的發(fā)展，情況不斷改善。內(nèi)存管理分別由操作系統(tǒng)、高級(jí)語言的編譯系統(tǒng)和程序員分工合作管理。通常編譯系統(tǒng)負(fù)責(zé)靜態(tài)儲(chǔ)存管理，操作系統(tǒng)負(fù)責(zé)整個(gè)內(nèi)存管理和動(dòng)態(tài)儲(chǔ)存管理。

第八章動(dòng)態(tài)存儲(chǔ)管理8.1概述43程序員級(jí)的管理：用戶程序中所用的儲(chǔ)存結(jié)構(gòu)有兩種，靜態(tài)結(jié)構(gòu)

：空間量在編譯后，即可確定動(dòng)態(tài)結(jié)構(gòu)：程序運(yùn)行中申請空間，編譯時(shí)無法確定。靜態(tài)儲(chǔ)存由編譯系統(tǒng)管理。動(dòng)態(tài)儲(chǔ)存由程序員和操作系統(tǒng)管理，但程序員的管理非常簡單。程序員的工作就是在需要的時(shí)候向系統(tǒng)申請空間，在不需要時(shí)釋放要來的動(dòng)態(tài)儲(chǔ)存空間：C語言中：malloc(size),申請size字節(jié)的內(nèi)存； free(p),釋放p，歸還給系統(tǒng)；C++中：newobjectType(),申請空間；free(p),釋放p，歸還給系統(tǒng)；程序員級(jí)的管理：44Java語言中：newobjectType(),申請空間；用戶程序：#includeiostd.lib……Intmain(){…*r=newint[100];…free(r);…}操作系統(tǒng)分配OS_AllocMemory(r,size,flags)回收OS_ReclaimMemory(r)FreeMemFreeMemrFreeMemJava語言中：newobjectTyp45編譯系統(tǒng)級(jí)管理在編譯中，編譯系統(tǒng)為程序設(shè)置了一個(gè)虛擬空間，它管理的是虛擬空間。用戶程序：…intx,y;floatr,s;charstr[10];………虛擬空間：x:4bytesy:4bytesstr:10bytesr:4bytess:4bytes048121626內(nèi)存程序裝入時(shí)，重定位編譯原理與技術(shù)中將做介紹。編譯系統(tǒng)級(jí)管理用戶程序：虛擬空間：x:4bytesy:446操作系統(tǒng)級(jí)管理：

存儲(chǔ)管理是操作系統(tǒng)的重要部分之一，操作系統(tǒng)對(duì)儲(chǔ)存的管理是才是真實(shí)的管理，而且這一管理是很復(fù)雜的。操作系統(tǒng)的存儲(chǔ)管理為程序代碼和靜態(tài)數(shù)據(jù)分配空間為程序動(dòng)態(tài)分配空間回收不用的動(dòng)態(tài)空間回收空間程序代碼和靜態(tài)數(shù)據(jù)空間分配回收執(zhí)行程序執(zhí)行完畢或撤消執(zhí)行程序程序NewOtype()Free(p)操作系統(tǒng)級(jí)管理：操作系統(tǒng)的存儲(chǔ)管理分回執(zhí)行程序執(zhí)行完畢或撤消47從外部來看，操作系統(tǒng)存儲(chǔ)管理系統(tǒng)就是提供存儲(chǔ)空間分配和回收服務(wù)，但內(nèi)部實(shí)現(xiàn)方法卻十分復(fù)雜，不同的操作系統(tǒng)采用不同的策略和方法，這些問題將在后續(xù)課程操作系統(tǒng)中詳細(xì)介紹。這里我們只是站在數(shù)據(jù)結(jié)構(gòu)的角度來討論動(dòng)態(tài)存儲(chǔ)管理的基本方法，即存儲(chǔ)空間的分配和回收基礎(chǔ)技術(shù)、存儲(chǔ)空間的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。

從外部來看，操作系統(tǒng)存儲(chǔ)管理系統(tǒng)就是提供存儲(chǔ)488.2可利用空間表初試狀態(tài)OSbootOS占用空間freetagsizelink一個(gè)連續(xù)的存儲(chǔ)空間稱為“塊”[block]Tag：標(biāo)記空間是否分配Size：空間大小Link：指向下一個(gè)空閑塊初試狀態(tài)：除了操作系統(tǒng)占用的空間外，其它空間形成一個(gè)空閑塊。當(dāng)空閑塊多時(shí)，用link鏈成一個(gè)鏈表，該鏈表就是可利用空間表。初試此表中只有一個(gè)空閑塊。表指針是free。8.2可利用空間表OSbootOS占用空間free49經(jīng)過多次分配、回收之后，形成了多個(gè)空閑塊，它們之間不連續(xù)，如圖所示：Freeused1used2used3used4used523456Free1136542經(jīng)過多次分配、回收之后，形成了多個(gè)空閑塊，它們之間不連續(xù)，如50可利用空間表的鏈接順序有：（1）按塊的首地址有低到高鏈接；（2）按塊的大小有小到大鏈接；（3）按塊的大小有大到小鏈接；分配：一般有3種策略，設(shè)申請空間的大小為n（1）首次擬合法：從表頭開始搜索，遇到第一個(gè)尺寸等于大于n的塊進(jìn)行分配；（2）最佳擬合法：搜索整個(gè)表，將最小的等于大于n的塊進(jìn)行分配；（3）最差擬合法：搜索整個(gè)表，將最大塊進(jìn)行分配（等于大于n）；可利用空間表的鏈接順序有：51分配過程：找到合適的空閑塊p；P.size等于n或比n大少許（一般設(shè)定一個(gè)量s），則將p從表中刪除，進(jìn)行分配；若p.size>n+s，從p的下部切割size為n的一塊進(jìn)行分配，如圖所示：n=16k064kp116k48k分配過程：064kp116k48k52回收: 程序釋放空間(如free(p))、程序運(yùn)行結(jié)束后將占用的塊歸還系統(tǒng)，如果收回的塊的相鄰塊是空閑的，需要合并它們?；厥者^程：設(shè)釋放塊是p，大小為size。（1）設(shè)置p.tag=0；（2）判斷p的下相鄰塊q是否空閑 若空閑：從可利用空間表摘出q，置p.size=p.size+q.size(合并)；（3）判斷p的上相鄰塊r是否空閑若空閑：合并r和p，r.size=r.size+p.size否則：將p插入可利用空間表?；厥? 程序釋放空間(如free(p))、程序運(yùn)行結(jié)束后將占53例如：Freeused1used2used3used4used523456Free1136542釋放used104k11knull06k12used104k07knull12used1011k12used1例如：Freeused1used2used3used4us54有時(shí)也不必馬上合并，如果釋放塊p的大小恰好符合下次申請空間的要求，可以將p分配，而不必從可利用空間表中切割分配。Free136542used1有時(shí)也不必馬上合并，如果釋放塊p的大小恰好符55例如，一個(gè)使用單鏈表的程序，它會(huì)不斷地申請和釋放同類型的結(jié)點(diǎn)（塊大小相等），回收時(shí)不進(jìn)行合并，而是放在另一個(gè)鏈表avail中；分配時(shí)首先從avail取一個(gè)塊分配，當(dāng)avail中沒有空閑塊時(shí)在從free表里分配。這樣就省去了不斷地合并切割的麻煩，可以提高效率。對(duì)于一些小的操作系統(tǒng)，內(nèi)存管理相對(duì)簡單些。在許多專用設(shè)備、智能儀表和家用電器等都使用一種小型的、高效的、簡單的操作系統(tǒng)，一般稱之為“嵌入式操作系統(tǒng)”。下面介紹一些實(shí)用而簡單的動(dòng)態(tài)存儲(chǔ)管理系統(tǒng)。例如，一個(gè)使用單鏈表的程序，它會(huì)不斷地申請和釋放同類型的結(jié)點(diǎn)568.3伙伴系統(tǒng)（Buddysystem）特點(diǎn)：（1）分配塊的大小均是2k;（2）分配和回收簡單可利用空間表結(jié)構(gòu)：202122...2k2m0k0k0k^^^內(nèi)存最大空間是2m空閑塊按其大小鏈入各自的鏈表；該數(shù)組是各鏈表的表頭接點(diǎn)同尺寸的空閑塊構(gòu)成雙向循環(huán)鏈表；有4個(gè)域：tag標(biāo)記，0空閑，1占用，k:塊的大小2k,llink:q前驅(qū)指針，rlingk:后繼指針8.3伙伴系統(tǒng)（Buddysystem）200k0k057伙伴系統(tǒng)抽象數(shù)據(jù)類型ADTBoddySystemData:intm //可用內(nèi)存2mFreeHeadList //m個(gè)表頭結(jié)點(diǎn)構(gòu)成的線性表BlockScrpt //塊描述 Memory //整個(gè)內(nèi)存空間opration:BS_malloc(size) //分配內(nèi)存BS_reclaim(BlockScrptbp)//回收內(nèi)存EndBlockSystem伙伴系統(tǒng)抽象數(shù)據(jù)類型58ClassFreeHeadNode{intsizePower;//k2kBlockScrptfirst;//鏈表指針}//ClassFreeHeadNode

ClassFreeHeadList{intm;//FreeHeadNode[]list;publicFreeHeadList(intn){m=n;list=newFreeHeadNode[m];}for(k=0;k<=m;k++){list[k].sizePower=k;first=null;}}//ClassFreeHeadList

kfirst0123..m-1m^^^^^ClassFreeHeadNode{kfirst0^^^59塊描述ClassBlockScrpt{intsizePower; booleanused; BlockScrptllink,rlink;intadd;public

BlockScrpt(intk,booleanb,intaddr){sizePower=k;used=b;add=addr;}//BlockScrpt}//ClassBlockScrpt

塊描述60伙伴系統(tǒng)結(jié)構(gòu)ClassBuddySystem{intm; //最大可用內(nèi)存2mBlockHeadListheadList //表頭向量BlockScrptblkScrpt; //塊描述Byte[]mem; //內(nèi)存publicBuddySystem(intk){//構(gòu)造函數(shù)m=k;headList=newBlockHeadList(m);blkScrpt=newBlockScrpt(m,false,0);

伙伴系統(tǒng)結(jié)構(gòu)61blkScrpt.llink=blkscrpt;blkScrpt.rlink=blkscrpt;headList[m].first=blkScrptmem=newByte[2m];}//BlockScrptBS_malloc(intk){……}voidBS_reclaim(BlockScrptbp){……}}//ClassBuddySystem

blkScrpt.llink62初始狀態(tài)012..k..mfalsem00122m-1headListmemBlockScrpt初始狀態(tài)0falsem00headListmemBlockS63分配26之后..67..k.m-1mfalsem-12m-102m-12m-1headListmemfalsek2kfalse727true60false626分配26之后..falsem-12m-10headLis64分配算法思想：申請空間量為2k；從k到m依次搜尋非空鏈表 若無：內(nèi)存不夠，結(jié)束；若有：設(shè)為headList[j]k=<j<=m若j=k:從headList[k]中取一結(jié)點(diǎn)分配，結(jié)束；若j>k:從headList[j]取一結(jié)點(diǎn)bs(1)將bs均分為二，高地址部分插入headList[j-1];j--;(2)重復(fù)（1）直到j(luò)=k；4將bs分配；結(jié)束；分配算法思想：65BlockScrptBS_malloc(intk){

for(j=k;j<=m;j++)//找非空鏈表if(!headList[j].