數(shù)據(jù)在計(jì)算機(jī)內(nèi)部的組織-下

第九章（下）數(shù)據(jù)在計(jì)算機(jī)內(nèi)部的組織本部分將主要討論：將以恰當(dāng)?shù)男问綄?duì)在內(nèi)存中擁有獨(dú)立地址且物理上相互獨(dú)立的存儲(chǔ)單元進(jìn)行組織，并考慮如何模擬這種抽象數(shù)據(jù)組織。目的是讓用戶以抽象的組織形式來考慮數(shù)據(jù)，并不關(guān)心數(shù)據(jù)在計(jì)算機(jī)內(nèi)存中的實(shí)際組織方式。學(xué)生信息管理計(jì)算機(jī)和人對(duì)弈問題交通燈管理問題數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)抽象：將用戶從實(shí)際數(shù)據(jù)存儲(chǔ)的細(xì)節(jié)中抽象出來，允許用戶以更方便的方法訪問信息。靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu)：取決于結(jié)構(gòu)的外形與大小是否隨時(shí)間變化；指針：就是包含有其他存儲(chǔ)單元地址的一個(gè)存儲(chǔ)單元，用來記錄存儲(chǔ)數(shù)據(jù)的位置。數(shù)組數(shù)組：將數(shù)據(jù)按照矩形排列存儲(chǔ)到一個(gè)同質(zhì)數(shù)組中。0點(diǎn)1點(diǎn)2點(diǎn)3點(diǎn)……22點(diǎn)23點(diǎn)如果第一個(gè)讀數(shù)所在的位置為x，則第n條數(shù)據(jù)在x+(n-1)的存儲(chǔ)單元中。數(shù)組（2）行優(yōu)先；列優(yōu)先；人員周一周二周三周四周五A10001200110015002000B8001300120021001700CDE某公司一周銷售量二維數(shù)組的行優(yōu)先存儲(chǔ)數(shù)組（3）在二維數(shù)組中，假設(shè)一個(gè)數(shù)組中列的數(shù)目為c，第一行第一列所在的單元地址為x，則數(shù)組中第i行第j列所在的位置為：地址多項(xiàng)式xx+5x+10x+13x+15x+13=x+(3-1)*5+(4-1)表結(jié)構(gòu)——鄰接表（contiguouslist）在計(jì)算機(jī)內(nèi)存中存儲(chǔ)姓名表時(shí)，一種策略是將它保存在一片獨(dú)立的地址連續(xù)的存儲(chǔ)空間中。假設(shè)每一個(gè)名字最多有8個(gè)字符組成，可以把整個(gè)一大塊空間劃分為一組子塊，每一塊子塊包含8個(gè)存儲(chǔ)單元。缺點(diǎn)：刪除與添加時(shí)的處理方法；表結(jié)構(gòu)——鏈接表（linkedlist）適用于：表中的不同單元存儲(chǔ)在內(nèi)存的不同位置而非一大塊連續(xù)的空間。姓名1指針姓名2指針姓名3NIL頭指針姓名1姓名2姓名3姓名1指針姓名2指針姓名3NIL頭指針表結(jié)構(gòu)——鏈接表（2）鏈接表的刪除姓名1指針姓名2指針姓名3NIL頭指針表結(jié)構(gòu)——鏈接表（3）鏈接表的插入表結(jié)構(gòu)——抽象概念表（1）確定選用鄰接表還是鏈接表；（2）寫出通用過程：插入新條目、刪除舊條目、搜索條目、輸出條目等；姓名1指針姓名2指針姓名3NIL頭指針CurrentPointer←頭指針；While(CurrentPointer不是NIL)doBegin

輸出指針指向的條目的名字；將當(dāng)前結(jié)點(diǎn)的指針域的值賦給CurrentPointer；End順序輸出鏈表中的姓名序列堆棧特點(diǎn)：插入和刪除操作均在表結(jié)構(gòu)的同一端進(jìn)行。其中，可以進(jìn)行操作的端稱為棧頂，另一端稱為棧底。向堆棧中插入元素稱為入棧，從棧中刪除元素稱為出棧。姓名1指針姓名2指針姓名3NIL頭指針CurrentPointer←頭指針；While(CurrentPointer不是NIL)doBegin

指針指向的條目的名字入棧；將當(dāng)前結(jié)點(diǎn)的指針域的值賦給CurrentPointer；EndWhile(棧非空)do

將棧中的名字彈出并且輸出；逆序輸出鏈表中的姓名序列先進(jìn)后出張三指針李四指針王五NIL頭指針張三李四王五堆棧（2）隊(duì)列特點(diǎn)：插入和刪除操作在表結(jié)構(gòu)的兩端進(jìn)行。其中，可以進(jìn)行插入操作的端稱為隊(duì)尾，另一端稱為隊(duì)頭。向隊(duì)列中插入元素稱為入隊(duì)，從隊(duì)列中刪除元素稱為出隊(duì)。先進(jìn)先出頭尾ABC頭尾CDEFGHIJ樹結(jié)點(diǎn)：樹中的一個(gè)位置；根結(jié)點(diǎn)：頂端的結(jié)點(diǎn)；葉結(jié)點(diǎn)：與樹的根結(jié)點(diǎn)相對(duì)應(yīng)的另一終極端結(jié)點(diǎn)，又稱末端結(jié)點(diǎn)；子樹：結(jié)點(diǎn)和它下面的結(jié)點(diǎn)組成的結(jié)構(gòu)；深度：從根結(jié)點(diǎn)到葉結(jié)點(diǎn)經(jīng)過的結(jié)點(diǎn)數(shù)目；二叉樹：樹的每一個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)；二叉樹的存儲(chǔ)包含數(shù)據(jù)的單元左子結(jié)點(diǎn)右子結(jié)點(diǎn)根結(jié)點(diǎn)ABCNILDNILNILENILNILFNILNIL二叉樹的存儲(chǔ)（2）ABCDEF根結(jié)點(diǎn)樹的第二級(jí)結(jié)點(diǎn)樹的第三級(jí)結(jié)點(diǎn)1234567第

n個(gè)結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)可以在第

2n

個(gè)存儲(chǔ)單元和第

2n+1

個(gè)存儲(chǔ)單元中找到。第

n個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)可以在第

n/2

個(gè)存儲(chǔ)單元中找到。二叉樹的存儲(chǔ)（3）ABCD1234567891011121314E15特點(diǎn)：對(duì)空間的利用非常低效。二叉樹包查詢操作當(dāng)數(shù)據(jù)表很長(zhǎng)時(shí)，查詢效率可能會(huì)比較低下。此時(shí)可以采用二分查找法進(jìn)行，當(dāng)然，需要樹滿足適合該算法的特性。二叉排序樹二叉樹包（2）ProcedureSearch(Tree,TargetValue)if(樹的根結(jié)點(diǎn)是NULL)then

返回失敗

elseBegin

按照不同的情況執(zhí)行下列語句

case1:TargetValue與根結(jié)點(diǎn)的值相等 返回成功

case2:TargetValue<根結(jié)點(diǎn)的值 將ProcedureSearch應(yīng)用于根結(jié)點(diǎn)的左子樹，并且返回查找結(jié)果

case3:TargetValue>根結(jié)點(diǎn)的值 將ProcedureSearch應(yīng)用于根結(jié)點(diǎn)的右子樹，并且返回查找結(jié)果

End

endif二叉樹包（3）在二叉排序樹上查找字母J二叉樹包（4）輸出操作（1）輸出根結(jié)點(diǎn)的左子樹；（2）輸出根結(jié)點(diǎn)；（3）輸出根結(jié)點(diǎn)的右子樹；二叉樹包（5）插入操作在二叉排序樹上插入字母M時(shí)的路徑ProcedureInsert(Tree,NewValue)Begin if(Tree的根結(jié)點(diǎn)是NULL)then

將包含NewValue設(shè)置為根結(jié)點(diǎn)的一個(gè)新的葉結(jié)點(diǎn)；

elseBegin

按照不同情況執(zhí)行下列語句：

case1:TargetValue與根結(jié)點(diǎn)的值相等 不執(zhí)行任何操作；

case2:TargetValue<根結(jié)點(diǎn)的值

if(根結(jié)點(diǎn)的左結(jié)點(diǎn)是空)then

將包含NewValue設(shè)置為根結(jié)點(diǎn)的一個(gè)新的葉結(jié)點(diǎn)；

else

使用ProcedureInsert將NewValue插入左子樹的適當(dāng)位置；

case3:TargetValue>根結(jié)點(diǎn)的值

if(根結(jié)點(diǎn)的右結(jié)點(diǎn)是空)then

將包含NewValue設(shè)置為根結(jié)點(diǎn)的一個(gè)新的葉結(jié)點(diǎn)；

else

使用ProcedureInsert將NewValue插入右子樹的適當(dāng)位置；

EndEnd存儲(chǔ)器的分類按存儲(chǔ)介質(zhì)半導(dǎo)體存儲(chǔ)器磁表面存儲(chǔ)器磁盤存儲(chǔ)器磁帶存儲(chǔ)器按存取方式隨機(jī)存儲(chǔ)器只讀存儲(chǔ)器順序存儲(chǔ)器直接存取存儲(chǔ)器按功能寄存器型存儲(chǔ)器主存儲(chǔ)器輔助存儲(chǔ)器高速緩沖存儲(chǔ)器存儲(chǔ)器的存儲(chǔ)容量存儲(chǔ)容量：存儲(chǔ)器有多少個(gè)存儲(chǔ)單元；基本的存儲(chǔ)單元稱為位（bit），在計(jì)算存儲(chǔ)器容量時(shí)常以字節(jié)（byte）或機(jī)器字長(zhǎng)（word）為基本單位，1Byte=8bit，計(jì)算機(jī)字長(zhǎng)與結(jié)構(gòu)有關(guān)，通常是8的倍數(shù)。