第11章數(shù)據(jù)結(jié)構(gòu)

第11章數(shù)據(jù)結(jié)構(gòu)

本章內(nèi)容安排數(shù)組記錄鏈表2數(shù)據(jù)結(jié)構(gòu)的概念在程序設(shè)計中，我們可以使用變量來存儲單個實體，變量的使用非常廣泛，但變量不能解決復(fù)雜問題。數(shù)據(jù)結(jié)構(gòu)是相關(guān)變量的集合，這些變量能夠單獨或作為整體被訪問。數(shù)據(jù)結(jié)構(gòu)代表了有特殊關(guān)系的數(shù)據(jù)的集合。3初步方案：定義100個變量，每個使用不同的名字。逐個變量讀入數(shù)據(jù)，逐個變量進(jìn)行處理。引入問題有100個分?jǐn)?shù)，需要讀入這些數(shù)，處理并打印，同時將這些數(shù)據(jù)保存在內(nèi)存中？4獨立變量的處理5數(shù)組的概念數(shù)組是固定大小，相同數(shù)據(jù)類型元素的順序集合。每個元素在數(shù)組中有一個固定的位置。將100個數(shù)放入數(shù)組中，假設(shè)數(shù)組的名稱為scores，可以稱數(shù)組中第一個元素為scores[1]，第二個元素為scores[2]……索引表明元素在數(shù)組中的順序號。現(xiàn)代語言（C、Java等）從0開始索引。6數(shù)組元素7循環(huán)的方式訪問數(shù)組元素8獨立變量和數(shù)組實現(xiàn)的比較編寫語句數(shù)量比較獨立變量：100條語句讀，100語句寫，100條語句處理，共需要編寫300條語句數(shù)組配合循環(huán)：每個循環(huán)體2條語句，加上初始化索引，總共需要編寫12條語句執(zhí)行的機(jī)器周期數(shù)使用數(shù)組和循環(huán)，所需要執(zhí)行的機(jī)器周期數(shù)沒有減少，反而有所增加，需要初始化、遞增循環(huán)變量和測試循環(huán)條件等負(fù)擔(dān)更應(yīng)該關(guān)心所編寫的程序行數(shù)。91、數(shù)組名與元素名數(shù)組名是整個結(jié)構(gòu)的名字，代表整個結(jié)構(gòu)；元素名是對某個特定元素的標(biāo)識。如數(shù)組的名稱為scores，元素名為數(shù)組名加索引，如scores[1]。102、二維數(shù)組在程序中二維數(shù)組的需求也非常多，如表格包括行和列，需要二維數(shù)組表示。二維數(shù)組需要兩個索引下標(biāo)，前面的下標(biāo)表示元素所在行，后面的下標(biāo)表示元素所在的列。假設(shè)二維數(shù)組名為scores，有5行4列，則a[1][2]表示第1行第2列的元素；a[2][3]表示第2行第3列的元素。11二維數(shù)組123、存儲配置一維數(shù)組以線性方式進(jìn)行存儲，數(shù)組中第一個元素存儲在內(nèi)存的低地址處，后面的元素依次連續(xù)存儲。二維數(shù)組采用多數(shù)情況下采用行主序存儲，“逐行”存儲，先存儲第一行元素(第一行的首個元素在低地址處，后面的元素依次存儲)，存完第一行之后，接著存儲第二行元素……13行主序存儲和列主序存儲14例題Students是一個100×4的二維數(shù)組（100行和4列），假定元素students[1][1]存儲地址為1000，每個元素占用1個存儲地址，求元素students[5][3]的地址，假定使用行主序存儲，索引下標(biāo)從1開始解答

y=1000+4*(5-1)+(3-1)=1018154、數(shù)組操作查找元素：查找匹配元素值的對應(yīng)元素的序號。對未排序的數(shù)組采用順序查找，對有序的數(shù)組采用折半查找。元素的插入尾部插入：新數(shù)據(jù)直接插入原數(shù)組的尾部開始或中間插入：需要將插入位置之后的所有元素向后移動，最后插入指定元素。16數(shù)組操作元素的刪除：刪除某個元素后，后續(xù)的元素需要向前移動。檢索元素：隨機(jī)存取一個元素，直接通過下標(biāo)索引的方式進(jìn)行訪問，如scores[9]數(shù)組的遍歷：應(yīng)用與數(shù)組中每個元素的操作。17求數(shù)組元素的平均值185、數(shù)組應(yīng)用數(shù)組適合于插入和刪除操作較少，而需要大量的查找和檢索操作的場合。在需要大量插入和刪除操作情況下，不適宜使用數(shù)組。19本章內(nèi)容安排數(shù)組記錄鏈表20記錄記錄(結(jié)構(gòu)體)是一組相關(guān)元素的集合，它們可能是不同的類型，整個記錄有一個名稱。記錄中的每個元素稱為域。域是具有含義的命名數(shù)據(jù)的最小元素。數(shù)組中所有元素必須是同一種類型，記錄中的元素可以是相同或不同類型。211、記錄的示例22記錄記錄中多個元素可以是相同或不同類型，但記錄中的所有元素必須是相關(guān)的。記錄中的數(shù)據(jù)往往和一個對象關(guān)聯(lián)，如第二個例子中的數(shù)據(jù)都與一個學(xué)生關(guān)聯(lián)；不要將不相關(guān)的數(shù)據(jù)組合到一起。注意:23記錄名與域名記錄的名稱是整個結(jié)構(gòu)的名字，域的名字允許我們存取特定的域。右圖中，記錄的名字為student，域名字分別為：

student.id student.grade242、記錄與數(shù)組數(shù)組定義了相同類型元素的集合，常用于描述多個同類對象的信息，如定義一個班級的學(xué)生成績（40個同學(xué)）。記錄常用于定義同一個對象的屬性集合，如描述某個學(xué)生的學(xué)號、姓名、成績等，域的數(shù)據(jù)類型往往不同。253、記錄數(shù)組一種特殊的數(shù)組，本身是數(shù)組，包含多個元素。數(shù)組中的每個元素是一個記錄。記錄數(shù)組往往用于定義多個對象的屬性信息。如班級中有30名同學(xué)，可以定義一個記錄的數(shù)組，每個記錄描述一位學(xué)生的信息。26記錄數(shù)組訪問第2個學(xué)生的姓名：(student[2]).name27示例：訪問記錄數(shù)組中的每個記錄域28示例：循環(huán)訪問記錄數(shù)組29本章內(nèi)容安排數(shù)組記錄鏈表30鏈表鏈表也是一個有序數(shù)據(jù)的集合，但每個元素包含下一個元素的地址。每個元素包含兩部分：數(shù)據(jù)和鏈(鏈?zhǔn)谴鎯ο乱粋€元素地址的指針)。此處只討論單鏈表，每個節(jié)點僅有一個指向后繼節(jié)點的鏈。通常使用一個指針變量指向第一個元素，稱為鏈表的頭指針。鏈表的最后一個元素包含一個空指針，標(biāo)識鏈表的結(jié)束。31鏈表示意32節(jié)點鏈表中的元素習(xí)慣上被稱為節(jié)點，節(jié)點是至少包含兩個域的記錄。一個域用于保存數(shù)據(jù)部分，另一個域包含指向下一個節(jié)點的地址。33數(shù)組與列表數(shù)組元素在內(nèi)存中連續(xù)存儲，通過索引下標(biāo)可對某個元素直接存取。鏈表中的節(jié)點在內(nèi)存中是分散存儲的，通過節(jié)點中的指針域鏈在一起。在鏈表中插入、刪除節(jié)點方便高效，但需要額外的域存儲地址；此外鏈表查詢需要遍歷鏈表。34數(shù)組與鏈表35鏈表名與節(jié)點名鏈表通常有一個頭指針，指向第一個元素，頭指針標(biāo)識整個鏈表，做為鏈表的名字。節(jié)點在鏈表中沒有明顯的名字，存在隱含的名字。以C語言為例，某個節(jié)點的名字通過指向它的指針間接獲得。如p指向某個節(jié)點，則節(jié)點名字為(*p)。36節(jié)點名字37鏈表的操作對鏈表的操作很多，在此我們只給出幾種基本操作：搜索鏈表插入節(jié)點刪除節(jié)點檢索鏈表遍歷鏈表381、搜索鏈表鏈表的搜索只能是順序搜索，鏈表中節(jié)點沒有特定的名字。搜索鏈表時，通過一個標(biāo)識變量表示是否搜索到目標(biāo)。當(dāng)搜索到時，將該標(biāo)識變量置為true，同時用指針變量指向含有目標(biāo)值的節(jié)點。39鏈表搜索示意圖4041鏈表搜索算法422、插入節(jié)點鏈表通常按照關(guān)鍵字有序排列，不允許插入重復(fù)值。插入新節(jié)點前，先搜索鏈表，只有當(dāng)插入的目標(biāo)值不存在時才允許執(zhí)行插入操作要考慮幾種不同的情況向空表插入節(jié)點向表的開始處插入節(jié)點向表尾插入節(jié)點在表中插入節(jié)點43表頭插入節(jié)點44表尾插入節(jié)點45表中插入節(jié)點46插入節(jié)點的算法473、刪除節(jié)點刪除節(jié)點之前，先搜索鏈表，只有當(dāng)搜索的目標(biāo)存在時才能刪除。刪除節(jié)點要考慮兩種情況刪除首節(jié)點刪除其他節(jié)點（中間或尾節(jié)點）48刪除首節(jié)點49刪除中間或尾節(jié)點50刪除節(jié)點的算法514、檢索鏈表檢索是為了檢查或復(fù)制節(jié)點中所含數(shù)據(jù)，而隨機(jī)訪問節(jié)點，檢索之前，首先需要通過搜索鏈表定位目標(biāo)節(jié)點。找到目標(biāo)節(jié)點后，通常會返回目標(biāo)節(jié)點的數(shù)據(jù)。52檢索鏈表的算法535、遍歷鏈表從第一個節(jié)點開始，依次檢查并處理每個節(jié)點直到最后一個節(jié)點。遍歷在各種算法中被廣泛使用，如修改節(jié)點的值、打印列表、計算某個域的和、計算平均值等。遍歷鏈表需要一個步進(jìn)指針，配合循環(huán)結(jié)構(gòu)，指針從一個節(jié)點移動到另一個節(jié)點，直到處理完最后一個節(jié)