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

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

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

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

n個結點的左右孩子結點可以在第

2n

個存儲單元和第

2n+1

個存儲單元中找到。第

n個結點的雙親結點可以在第

n/2

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

返回失敗

elseBegin

按照不同的情況執行下列語句

case1:TargetValue與根結點的值相等 返回成功

case2:TargetValue<根結點的值 將ProcedureSearch應用于根結點的左子樹，并且返回查找結果

case3:TargetValue>根結點的值 將ProcedureSearch應用于根結點的右子樹，并且返回查找結果

End

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

將包含NewValue設置為根結點的一個新的葉結點；

elseBegin

按照不同情況執行下列語句：

case1:TargetValue與根結點的值相等 不執行任何操作；

case2:TargetValue<根結點的值

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

將包含NewValue設置為根結點的一個新的葉結點；

else

使用ProcedureInsert將NewValue插入左子樹的適當位置；

case3:TargetValue>根結點的值

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

將包含NewValue設置為根結點的一個新的葉結點；

else

使用ProcedureInsert將NewValue插入右子樹的適當位置；

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