存儲(chǔ)管理中分區(qū)分配算法的模擬

沈陽(yáng)理工大學(xué)課程設(shè)計(jì)專(zhuān)用紙PAGE沈陽(yáng)理工大學(xué)PAGE7成績(jī)?cè)u(píng)定表學(xué)生姓名班級(jí)學(xué)號(hào)專(zhuān)業(yè)計(jì)算機(jī)科學(xué)與技術(shù)課程設(shè)計(jì)題目1存儲(chǔ)管理中分區(qū)分配算法的模擬2已知二叉樹(shù)的中序和先序序列，求后序序列評(píng)語(yǔ)組長(zhǎng)簽字:成績(jī)?nèi)掌?012年12月２5日課程設(shè)計(jì)任務(wù)書(shū)學(xué)院信息科學(xué)與工程學(xué)院專(zhuān)業(yè)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)生姓名班級(jí)學(xué)號(hào)課程設(shè)計(jì)題目1存儲(chǔ)管理中分區(qū)分配算法的模擬2已知二叉樹(shù)的中序和先序序列，求后序序列實(shí)踐教學(xué)要求與任務(wù):課程設(shè)計(jì)任務(wù)當(dāng)作業(yè)運(yùn)行時(shí),由操作系統(tǒng)將內(nèi)存空間分配給作業(yè)。已知二叉樹(shù)的中序和先序序列,求后序序列2課程設(shè)計(jì)要求１）分區(qū)管理是內(nèi)存管理的一種方式,模擬分區(qū)分配算法采用最佳適應(yīng)、最先適應(yīng)等方式分配內(nèi)存。選擇不同的算法，對(duì)作業(yè)分配所需要的空間。當(dāng)空間回收時(shí),將空閑空間與被回收空間相連的部分連接成一塊較大的空間。2)完成需求分析，建立數(shù)學(xué)模型,編寫(xiě)程序,調(diào)試。工作計(jì)劃與進(jìn)度安排:第１7周:設(shè)計(jì)任務(wù)分析和總體設(shè)計(jì)，軟件算法和流程設(shè)計(jì),軟件編碼實(shí)現(xiàn)。第18周：軟件總體調(diào)試，交課程設(shè)計(jì)報(bào)告、答辯、驗(yàn)收程序.指導(dǎo)教師:２01年月日專(zhuān)業(yè)負(fù)責(zé)人：2０1年月日學(xué)院教學(xué)副院長(zhǎng)：201年月日目錄１需求分析……………………４１。１存儲(chǔ)管理中分區(qū)分配算法的模擬…………4１.2已知二叉樹(shù)的中序和先序序列,求后序序列……………62概要設(shè)計(jì)………42.1存儲(chǔ)管理中分區(qū)分配算法的模擬…………42．１。１概述…………………42。1。2結(jié)構(gòu)設(shè)計(jì)說(shuō)明………42。1.3算法流程圖…………6２.2已知二叉樹(shù)的中序和先序序列,求后序序列……………6２。２．1概述…………………62。2。2結(jié)構(gòu)說(shuō)明……………62.2．3算法流程圖…………7３詳細(xì)設(shè)計(jì)………８3.1存儲(chǔ)管理中分區(qū)分配算法的模擬…………８3.2已知二叉樹(shù)的中序和先序序列，求后序序列……………１24調(diào)試分析………16４．1存儲(chǔ)管理中分區(qū)分配算法的模擬…………１64.２已知二叉樹(shù)的中序和先序序列,求后序序列……………１95課設(shè)總結(jié)………206參考文獻(xiàn)………21１需求分析１．1存儲(chǔ)管理中分區(qū)分配算法的模擬當(dāng)作業(yè)運(yùn)行時(shí)，由操作系統(tǒng)將內(nèi)存空間分配給作業(yè).分區(qū)管理是內(nèi)存管理的一種方式，模擬分區(qū)分配算法采用最佳適應(yīng)、最先適應(yīng)等方式分配內(nèi)存。選擇不同的算法，對(duì)作業(yè)分配所需要的空間.當(dāng)空間回收時(shí)，將空閑空間與被回收空間相連的部分連接成一塊較大的空間。１。2已知二叉樹(shù)的中序和先序序列,求后序序列。２概要設(shè)計(jì)2.1存儲(chǔ)管理中分區(qū)分配算法的模擬2．1。１概述模擬分區(qū)分配算法采用最佳適應(yīng)、最先適應(yīng)等方式分配內(nèi)存。選擇不同的算法，對(duì)作業(yè)分配所需要的空間.當(dāng)空間回收時(shí)，將空閑空間與被回收空間相連的部分連接成一塊較大的空間。2.1．2結(jié)構(gòu)設(shè)計(jì)說(shuō)明．空閑分區(qū)表的設(shè)計(jì)，該空閑分區(qū)表記錄內(nèi)存中未使用的各個(gè)分區(qū)，記錄內(nèi)容有未使用分區(qū)的大小、首地址，用鏈表就行管理；相關(guān)代碼如下：Tｙｐedefstrｕctfｒee｛Ｉntsize；／/分區(qū)大小Ｉntaｄｄresｓ;／/首地址free＊nｅｘt；};②內(nèi)存分區(qū)表設(shè)計(jì),用以表示當(dāng)前內(nèi)存的使用情況，記錄內(nèi)容已使用分區(qū)的大小、首地址，用鏈表進(jìn)行管理,相關(guān)數(shù)據(jù)結(jié)構(gòu)如下:Tyｐeｄeｆｓｔructｍap{Ｉntsize;//分區(qū)大?。蒼ｔａddｒess；／/首地址map*nexｔ;｝；③進(jìn)程申請(qǐng)隊(duì)列的設(shè)計(jì)，用作進(jìn)程到達(dá)的緩沖隊(duì)列，記錄各進(jìn)程的相關(guān)信息，如進(jìn)程的所需內(nèi)存的大小、進(jìn)程名,相關(guān)數(shù)據(jù)結(jié)構(gòu)如下:Ｔｙpedefsｔruｃtpro｛Intsｉzｅ；//分區(qū)大小ｓｒiｎgnaｍｅ；prｏ*nｅxt；｝;2。1．３算法流程圖選取部分核心流程圖如下：2.2已知二叉樹(shù)的中序和先序序列，求后序序列2。2。1概述已知二叉樹(shù)的前序后序遍歷和中序遍歷求后序２。２.2結(jié)構(gòu)設(shè)計(jì)及說(shuō)明1、確定樹(shù)的根節(jié)點(diǎn)。樹(shù)根是當(dāng)前樹(shù)中所有元素在前序遍歷中最先出現(xiàn)的元素。?2、求解樹(shù)的子樹(shù)。找出根節(jié)點(diǎn)在中序遍歷中的位置,根左邊的所有元素就是左子樹(shù)，根右邊的所有元素就是右子樹(shù).若根節(jié)點(diǎn)左邊或右邊為空,則該方向子樹(shù)為空；若根節(jié)點(diǎn)左邊和右邊都為空，則根節(jié)點(diǎn)已經(jīng)為葉子節(jié)點(diǎn)。３、遞歸求解樹(shù)。將左子樹(shù)和右子樹(shù)分別看成一棵二叉樹(shù),重復(fù)1、2、3步，直到所有的節(jié)點(diǎn)完成定位。舉例說(shuō)明:假設(shè)前序遍歷為adbgｃefh,中序遍歷為dgbaechf前序遍歷是先訪問(wèn)根節(jié)點(diǎn),然后再訪問(wèn)子樹(shù)的，而中序遍歷則先訪問(wèn)左子樹(shù)再訪問(wèn)根節(jié)點(diǎn)而中序遍歷則先訪問(wèn)左子樹(shù)再訪問(wèn)根節(jié)點(diǎn)那么把前序的ａ取出來(lái)，然后查找a在中序遍歷中的位置就得到ｄｇｂaｅｃｈf然后查找那么我們就知道ｄgb是左子樹(shù)echｆ是右子樹(shù),因?yàn)閿?shù)量要吻合所以前序中相應(yīng)的dｂg是左子樹(shù)cｅfh是右子樹(shù)然后就變成了一個(gè)遞歸的過(guò)程。開(kāi)始２．2。3算法流程圖開(kāi)始定義倆個(gè)棧類(lèi)型定義倆個(gè)棧類(lèi)型structsnodestructsnode1主函數(shù)voidmain()主函數(shù)voidmain()子函數(shù)一創(chuàng)建二叉樹(shù)子函數(shù)一創(chuàng)建二叉樹(shù)子函數(shù)二后序遍歷出二叉樹(shù)子函數(shù)二后序遍歷出二叉樹(shù)結(jié)束結(jié)束3詳細(xì)設(shè)計(jì)3。１存儲(chǔ)管理中分區(qū)分配算法的模擬程序：1。有大小恰好合適的空閑塊ｉｆ(p-〉daｔa．staｔｅ＝=Frｅｅ＆&p->datａ。ｓize==requeｓt)｛p－〉dａｔa.ｓｔａt(yī)e=Busy；ｐ—>daｔａ.ＩD=ID;reｔuｒｎＯＫ;ｂreaｋ;｝２.有空閑塊能滿足需求且有剩余if（ｐ—>dａt(yī)a．stａt(yī)e==Ｆreｅ&＆p-＞daｔa。ｓｉze＞requｅｓt)｛ｔeｍｐ—〉prｉor＝p-〉ｐrｉor；temｐ—〉ｎext＝p；temp—＞data.ａddreｓs＝p—〉dａt(yī)a。aｄdｒｅss;p－>prior->ｎｅxt=ｔemp；p－＞pｒior＝tｅｍｐ；ｐ—＞daｔa．a(chǎn)dｄｒess=ｔemp－＞dａt(yī)ａ．a(chǎn)ｄdresｓ+temp－〉ｄａt(yī)a。sｉze;ｐ—>data.size—=rｅｑueｓt;retuｒnＯK;}3．回收內(nèi)存ｉf（ｐ－〉ｄａt(yī)a.ＩＤ＝=ＩD）p->ｄata.stａt(yī)ｅ=Ｆｒｅe(cuò);p－>dａt(yī)ａ．ID=Fｒeｅ;if（p—〉pｒior—＞data．ｓtaｔe==Fｒee）//與前面的空閑塊相連｛ｐ—〉priｏr—＞data。size+=p-〉daｔa．siｚe；p—＞prioｒ－〉next=p—〉ｎeｘt；ｐ—〉nｅxｔ->prｉｏr=p—＞ｐrior;｝if(ｐ—>neｘt-〉data.ｓｔａｔe==Frｅe(cuò)）//與后面的空閑塊相連｛ｐ-〉dａt(yī)a.sｉｚe＋=ｐ－>neｘt－〉dａt(yī)ａ。siｚe；p—＞ｎext－>ｎｅxt－〉prioｒ=p；ｐ－＞ｎｅxｔ=p—〉nｅｘt-＞nｅxｔ;｝另外若檢查到有“等于"的情況，就可以直接分配,若沒(méi)有，則繼續(xù)檢查是否有“大于”的情況:iｆ（ｆreｅblｏｃk［ｉ］.ｓｔatｅ==1＆＆freeｂｌock［i］。sｉze==apｐｌyarｅa） ?｛ ?freｅblocｋ[ｉ］。ｓtatｅ=0;? taｇ＝１;?? ??ｒeｔurnｆｒeebloｃk［i].starｔａddresｓ；? ? }檢查“大于”的情況：先把所有大于所要求的空閑區(qū)放入數(shù)組，ｆor(i=0;i〈Ｎ;ｉ＋+）｛iｆ(ｆｒeeblock［i]。ｓtaｔe=＝1＆＆frｅe(cuò)blｏcｋ［ｉ]。sｉze〉aｐplyａｒeａ）a［j＋＋]=i；}再?gòu)臄?shù)組中挑出最小的那個(gè)：果數(shù)組中的元素大于一個(gè),則需要一個(gè)個(gè)比較過(guò)去，然后取出最小的那個(gè)分配給作業(yè):iｆ（j〉1)｛?ｈ＝ａ[0]；?min=frｅｅblock[ｈ];??for(ｋ＝1；ｋ<j;k+＋）? {ｈ=a［k］；if（fｒｅe(cuò)blｏｃｋ[h].siｚｅ<mｉn．size){ ??ｍid。size=frｅe(cuò)bloｃk[h］．siｚe； ???mid．stａt(yī)e＝ｆreｅblｏck[ｈ]。ｓtaｔe；? ??ｍid。starｔadｄrｅss＝frｅe(cuò)bｌock［ｈ］。sｔａｒｔaｄdresｓ;????fｒｅe(cuò)bｌoｃk［h］．size＝ｍｉn。size;? ? frｅe(cuò)ｂlocｋ[h]．stａt(yī)e=mｉn．stａt(yī)e；??? freeblｏcｋ[ｈ]．stａrｔaｄｄress＝min。sｔartaｄdreｓs； ??min.ｓize=miｄ。ｓize;????ｍin.ｓｔａt(yī)ｅ＝ｍｉd。state；????mｉn．staｒtadｄress=mｉd。startaddreｓs;}｝ｍin．starｔaｄｄｒeｓs=ｍin.starｔaｄｄrｅss+aｐｐlｙａｒｅa；ｍｉn．size=miｎ。sｉzｅ-apｐlyａreａ；tａｇ=1;??ｒｅturｎｍiｎ.ｓtartadｄｒess-applｙａrｅａ;｝如果數(shù)組中只有一個(gè)元素,則直接分配給作業(yè)：if(j==1）{h=a[０］;ｍｉn=frｅe(cuò)blｏck[h];ｍin．ｓｔａrｔaddｒｅｓs＝miｎ.sｔａｒtaｄdress+appｌyaｒea;min。size＝ｍin．siｚe-ａppｌyaｒｅa;? tag=1;??reｔｕrnmｉn.ｓtａｒtaｄｄrｅsｓ-aｐplyareａ；｝如果沒(méi)有滿足條件的空閑區(qū)，分配不成功，返回－1iｆ（ｔag==0)retｕｒn—1；3.２已知二叉樹(shù)的中序和先序序列，求后序序列1.定義二叉樹(shù)節(jié)點(diǎn)類(lèi)型strｕctｎoｄe｛cｈaｒdatａ;stｒuctnｏｄｅ＊lchｉｌd;structnoｄe＊rchｉlｄ;}ＢTｒｅe(cuò)；2．定義兩個(gè)棧的類(lèi)型ｓtructｓｎｏｄe{ｉｎtｔｏｐ;ｉｎta[ＭAX］；｝；ｓｔruｃｔsnodｅ1{intｔoｐ;structｎｏｄｅ*c［MAX］;};3.主函數(shù)ｖｏiｄｍaｉn（）｛ｃｈaｒa[ＭＡＸ]={0｝；ｃｈａrb［ＭＡX]＝{0};cｈａrc＝0,d＝０;iｎti＝０,j=0；stｒｕcｔｎode*g；ｓnodｅs;snoｄe1s4,s1；Initstack(&s）；Initsｔacｋ1(＆s４）;Iｎｉｔstack１（&ｓ１)；printｆ（＂請(qǐng)輸入先序序列：\ｎ＂）；wｈｉｌe（c!='\ｎ'）｛ｃ＝ｇeｔchar（）；ａ［ｉ］＝c;i＋+；}prｉntf（＂請(qǐng)輸入中序序列：＼ｎ”)；while(d!='\ｎ'){d=ｇetchａr（)；b[j]＝d；j+＋；｝g=ｃreate（&ｓ,＆s1，a,b)；ｐriｎtf(”遍歷輸出后序序列：\n")；visiｔ（&s4,g）;printf("\n”）;}4.子函數(shù)一，創(chuàng)建二叉樹(shù)sｔrｕcｔｎoｄe*creatｅ（sｎoｄｅ＊s，sｎｏde１*s１，ｃｈara[ＭAX]，ｃharb［MAX］){?inti＝1,ｎuｍ,ｘ;ｓtrucｔnｏde＊p，*ｑ,*r,*ｒｏｏt;p＝（struｃｔｎｏdｅ＊)malloｃ（sizeof(BＴreｅ));?p－＞lchild＝ＮUＬL;p->rchilｄ=NULL；p—>ｄatａ=a［０］；ｒoot＝p;x=ｓｅｅk（ａ［0］，b）；pusｈ（ｓ,x）；puｓh1（s１,p);ｗhｉｌe（a［ｉ］！=＇＼n＇）{num＝sｅe(cuò)k（ａ［i]，b）;p=（ｓｔｒｕctｎｏdｅ*)maｌｌoc（ｓizeof（BTree)）；p-＞lｃhiｌｄ＝ＮULＬ;p-＞rchild=NUＬL；p-＞data＝a［i］；ｉｆ（nuｍ〈gettoｐ（ｓ））｛ｑ=gｅｔ(s1）；ｑ－>ｌchｉld=ｐ；puｓh（ｓ，num);pusｈ1（s1，p)；}ｅｌseif（ｎum＞ｇettop（s））{whｉlｅ(s－>tｏｐ！=—１&&ｎum〉gettop（s））｛r=ｐｏp1（s１）；pｏｐ（ｓ)；}ｒ－>rchilｄ=p;ｐusｈ（s，ｎum)；pｕsh１（s１,p）;}i+＋；}rｅturnrｏｏt；｝5。子函數(shù)二，后序遍歷輸出二叉樹(shù)ｖoｉdｖiｓiｔ(snｏdｅ１＊s，sｔructnｏde＊ｒｏｏt）{stｒuｃtnoｄe*p；p＝root;?dｏ{whilｅ(p!=NＵLL）｛pｕsｈ１(ｓ,p)；p=p－〉lcｈild；｝wｈilｅ（s->ｔop!＝—1＆＆giｖe（s)—〉rchild＝=p)｛p=ｐｏp1（ｓ);prinｔf（＂％c"，ｐ-＞dａt(yī)ａ）；｝ｉｆ（s—〉top!=—１)p=gｉve(s）-＞rｃhiｌd；}while（s-〉toｐ!=—1）;}4調(diào)試分析4.1存儲(chǔ)管理中分區(qū)分配算法的模擬實(shí)現(xiàn)了設(shè)計(jì)的所有要求，選取部分運(yùn)行示意圖。1)。輸入選擇１首次適應(yīng)法并選擇1分配內(nèi)存，過(guò)程如下：圖4－12)。輸入選擇3查看分別配,過(guò)程如下:圖4－2３）.輸入選擇２最佳適應(yīng)算法并選擇1分配內(nèi)存，過(guò)程如下：圖4—34）。輸入選擇２回收內(nèi)存后選擇3查看分配，過(guò)程如下:圖４—45)．輸入選擇3循環(huán)首次適應(yīng)法并選擇１分配內(nèi)存,過(guò)程如下：圖4－56)．菜單界面下輸入選擇回收內(nèi)存并選擇3查看分配,過(guò)程如下：圖４－64.２已知二叉樹(shù)的中序和先序序列,求后序序列輸入前序和中序序列得到結(jié)果５課程總結(jié)不知不覺(jué)期末的腳步已悄悄逼近，我們結(jié)束了一科又一科的緊張復(fù)習(xí)，迎接著一次又一次別開(kāi)生面的考試，這段時(shí)間給我最大的體會(huì)就是好累,好枯燥！本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是由老師提供電子框架，由我們獨(dú)立完成,通過(guò)對(duì)課程設(shè)計(jì)的制作，發(fā)現(xiàn)了自身許許多多的不足,同時(shí)也學(xué)到許許多多的東西。是我們每一個(gè)同學(xué)都受益匪淺！通過(guò)對(duì)本次課程設(shè)計(jì)的深入了解,我發(fā)現(xiàn)了程序中的一些問(wèn)題，和一些優(yōu)缺點(diǎn)，現(xiàn)在就舉出幾個(gè)簡(jiǎn)單的例子吧：優(yōu)點(diǎn);實(shí)現(xiàn)了多個(gè)作業(yè)或進(jìn)程對(duì)內(nèi)存的共享,有助于多道程序設(shè)計(jì),從而提高了系統(tǒng)利用率。該方法要求的硬件支持少，管理算法簡(jiǎn)單，因而實(shí)現(xiàn)容易。缺點(diǎn)：內(nèi)存利用率仍然不高。和單一連續(xù)分配算法一樣,存儲(chǔ)器中可能含有從未用過(guò)的信息。而且，還存在著