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

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

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

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

2n

個存儲單元和第

2n+1

個存儲單元中找到。第

n個結(jié)點的雙親結(jié)點可以在第

n/2

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

返回失敗

elseBegin

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

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

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

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

End

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

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

elseBegin

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

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

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

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

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

else

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

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

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

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

else

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

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