《計(jì)算機(jī)科學(xué)導(dǎo)論》PPT配套課件

《計(jì)算機(jī)科學(xué)導(dǎo)論》PPT配套課件,計(jì)算機(jī)科學(xué)導(dǎo)論,計(jì)算機(jī)科學(xué),導(dǎo)論,PPT,配套,課件 第第1111章章 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)本章內(nèi)容安排本章內(nèi)容安排&數(shù)組數(shù)組&記錄記錄&鏈表鏈表2數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念&在程序設(shè)計(jì)中，我們可以使用變量來(lái)存儲(chǔ)單個(gè)實(shí)在程序設(shè)計(jì)中，我們可以使用變量來(lái)存儲(chǔ)單個(gè)實(shí)體，變量的使用非常廣泛，但變量不能解決復(fù)雜問(wèn)體，變量的使用非常廣泛，但變量不能解決復(fù)雜問(wèn)題。題。&數(shù)據(jù)結(jié)構(gòu)是相關(guān)變量的集合數(shù)據(jù)結(jié)構(gòu)是相關(guān)變量的集合，這些變量能夠單獨(dú)，這些變量能夠單獨(dú)或作為整體被訪問(wèn)。數(shù)據(jù)結(jié)構(gòu)代表了有或作為整體被訪問(wèn)。數(shù)據(jù)結(jié)構(gòu)代表了有特殊關(guān)系特殊關(guān)系的的數(shù)據(jù)的集合。數(shù)據(jù)的集合。3初步方案：初步方案：初步方案：初步方案：定義定義定義定義100100100100個(gè)個(gè)個(gè)個(gè)變量變量變量變量，每個(gè)使用不同，每個(gè)使用不同，每個(gè)使用不同，每個(gè)使用不同的名字。逐個(gè)變量讀的名字。逐個(gè)變量讀的名字。逐個(gè)變量讀的名字。逐個(gè)變量讀入數(shù)據(jù)，逐個(gè)變量進(jìn)入數(shù)據(jù)，逐個(gè)變量進(jìn)入數(shù)據(jù)，逐個(gè)變量進(jìn)入數(shù)據(jù)，逐個(gè)變量進(jìn)行處理。行處理。行處理。行處理。引入問(wèn)題引入問(wèn)題&有有100100個(gè)分?jǐn)?shù)，需要讀入這些數(shù)，處理并打印，同個(gè)分?jǐn)?shù)，需要讀入這些數(shù)，處理并打印，同時(shí)將這些數(shù)據(jù)保存在內(nèi)存中？時(shí)將這些數(shù)據(jù)保存在內(nèi)存中？4獨(dú)立變量的處理獨(dú)立變量的處理5數(shù)組的概念數(shù)組的概念&數(shù)組是固定大小，相同數(shù)據(jù)類型元素的順序集合數(shù)組是固定大小，相同數(shù)據(jù)類型元素的順序集合。每個(gè)元素在數(shù)組中有一個(gè)固定的位置。每個(gè)元素在數(shù)組中有一個(gè)固定的位置。&將將100100個(gè)數(shù)放入數(shù)組中，假設(shè)數(shù)組的名稱為個(gè)數(shù)放入數(shù)組中，假設(shè)數(shù)組的名稱為scoresscores，可以稱數(shù)組中第一個(gè)元素為，可以稱數(shù)組中第一個(gè)元素為scores1scores1，第二個(gè)元，第二個(gè)元素為素為scores2scores2&索引索引表明元素在數(shù)組中的順序號(hào)表明元素在數(shù)組中的順序號(hào)?，F(xiàn)代語(yǔ)言（?，F(xiàn)代語(yǔ)言（C C、JavaJava等）從等）從0 0開(kāi)始索引。開(kāi)始索引。6數(shù)組元素?cái)?shù)組元素7循環(huán)的方式訪問(wèn)數(shù)組元素循環(huán)的方式訪問(wèn)數(shù)組元素8獨(dú)立變量和數(shù)組實(shí)現(xiàn)的比較獨(dú)立變量和數(shù)組實(shí)現(xiàn)的比較&編寫(xiě)語(yǔ)句數(shù)量比較編寫(xiě)語(yǔ)句數(shù)量比較 獨(dú)立變量：獨(dú)立變量：獨(dú)立變量：獨(dú)立變量：100100條語(yǔ)句讀，條語(yǔ)句讀，條語(yǔ)句讀，條語(yǔ)句讀，100100語(yǔ)句寫(xiě)，語(yǔ)句寫(xiě)，語(yǔ)句寫(xiě)，語(yǔ)句寫(xiě)，100100條語(yǔ)句處理，條語(yǔ)句處理，條語(yǔ)句處理，條語(yǔ)句處理，共需要編寫(xiě)共需要編寫(xiě)共需要編寫(xiě)共需要編寫(xiě)300300條語(yǔ)句條語(yǔ)句條語(yǔ)句條語(yǔ)句 數(shù)組配合循環(huán)：每個(gè)循環(huán)體數(shù)組配合循環(huán)：每個(gè)循環(huán)體數(shù)組配合循環(huán)：每個(gè)循環(huán)體數(shù)組配合循環(huán)：每個(gè)循環(huán)體2 2條語(yǔ)句，加上初始化索引，條語(yǔ)句，加上初始化索引，條語(yǔ)句，加上初始化索引，條語(yǔ)句，加上初始化索引，總共需要編寫(xiě)總共需要編寫(xiě)總共需要編寫(xiě)總共需要編寫(xiě)1212條語(yǔ)句條語(yǔ)句條語(yǔ)句條語(yǔ)句&執(zhí)行的機(jī)器周期數(shù)執(zhí)行的機(jī)器周期數(shù) 使用數(shù)組和循環(huán)，所需要執(zhí)行的機(jī)器周期數(shù)沒(méi)有減少，使用數(shù)組和循環(huán)，所需要執(zhí)行的機(jī)器周期數(shù)沒(méi)有減少，使用數(shù)組和循環(huán)，所需要執(zhí)行的機(jī)器周期數(shù)沒(méi)有減少，使用數(shù)組和循環(huán)，所需要執(zhí)行的機(jī)器周期數(shù)沒(méi)有減少，反而有所增加，需要初始化、遞增循環(huán)變量和測(cè)試循環(huán)反而有所增加，需要初始化、遞增循環(huán)變量和測(cè)試循環(huán)反而有所增加，需要初始化、遞增循環(huán)變量和測(cè)試循環(huán)反而有所增加，需要初始化、遞增循環(huán)變量和測(cè)試循環(huán)條件等負(fù)擔(dān)條件等負(fù)擔(dān)條件等負(fù)擔(dān)條件等負(fù)擔(dān) 更應(yīng)該關(guān)心所編寫(xiě)的程序行數(shù)。更應(yīng)該關(guān)心所編寫(xiě)的程序行數(shù)。更應(yīng)該關(guān)心所編寫(xiě)的程序行數(shù)。更應(yīng)該關(guān)心所編寫(xiě)的程序行數(shù)。91、數(shù)組名與元素名、數(shù)組名與元素名&數(shù)組名數(shù)組名是整個(gè)結(jié)構(gòu)的名字，代表整個(gè)結(jié)構(gòu)；是整個(gè)結(jié)構(gòu)的名字，代表整個(gè)結(jié)構(gòu)；元素元素名名是對(duì)某個(gè)特定元素的標(biāo)識(shí)。是對(duì)某個(gè)特定元素的標(biāo)識(shí)。&如數(shù)組的名稱為如數(shù)組的名稱為scoresscores，元素名為數(shù)組名加索引，元素名為數(shù)組名加索引，如如scores1scores1。102、二維數(shù)組、二維數(shù)組&在程序中二維數(shù)組的需求也非常多，如在程序中二維數(shù)組的需求也非常多，如表格表格包括包括行和列，需要行和列，需要二維數(shù)組二維數(shù)組表示。表示。&二維數(shù)組需要二維數(shù)組需要兩個(gè)索引下標(biāo)兩個(gè)索引下標(biāo)，前面的下標(biāo)表示元，前面的下標(biāo)表示元素所在行，后面的下標(biāo)表示元素所在的列。素所在行，后面的下標(biāo)表示元素所在的列。&假設(shè)二維數(shù)組名為假設(shè)二維數(shù)組名為scoresscores，有，有5 5行行4 4列，則列，則a12a12表表示第示第1 1行第行第2 2列的元素；列的元素；a23a23表示第表示第2 2行第行第3 3列的元列的元素。素。11二維數(shù)組二維數(shù)組123、存儲(chǔ)配置、存儲(chǔ)配置&一維數(shù)組以線性方式進(jìn)行存儲(chǔ)一維數(shù)組以線性方式進(jìn)行存儲(chǔ)，數(shù)組中第一個(gè)元，數(shù)組中第一個(gè)元素存儲(chǔ)在內(nèi)存的低地址處，后面的元素依次連續(xù)存素存儲(chǔ)在內(nèi)存的低地址處，后面的元素依次連續(xù)存儲(chǔ)。儲(chǔ)。&二維數(shù)組采用多數(shù)情況下采用行主序存儲(chǔ)，二維數(shù)組采用多數(shù)情況下采用行主序存儲(chǔ)，“逐逐行行”存儲(chǔ)存儲(chǔ)，先存儲(chǔ)第一行元素，先存儲(chǔ)第一行元素(第一行的首個(gè)元素第一行的首個(gè)元素在低地址處，后面的元素依次存儲(chǔ)在低地址處，后面的元素依次存儲(chǔ))，存完第一行，存完第一行之后，接著存儲(chǔ)第二行元素之后，接著存儲(chǔ)第二行元素13行主序存儲(chǔ)和列主序存儲(chǔ)行主序存儲(chǔ)和列主序存儲(chǔ)14例題例題&StudentsStudents是一個(gè)是一個(gè)10041004的二維數(shù)組（的二維數(shù)組（100100行和行和4 4列），列），假定元素假定元素students11students11存儲(chǔ)地址為存儲(chǔ)地址為10001000，每個(gè)元，每個(gè)元素占用素占用1 1個(gè)存儲(chǔ)地址，求元素個(gè)存儲(chǔ)地址，求元素students53students53的地址，的地址，假定使用行主序存儲(chǔ)，索引下標(biāo)從假定使用行主序存儲(chǔ)，索引下標(biāo)從1 1開(kāi)始開(kāi)始&解答解答 y=1000+4*(5-1)+(3-1)=1018y=1000+4*(5-1)+(3-1)=1018154、數(shù)組操作、數(shù)組操作&查找元素查找元素：查找匹配元素值的對(duì)應(yīng)元素的序號(hào)。：查找匹配元素值的對(duì)應(yīng)元素的序號(hào)。對(duì)未排序的數(shù)組采用順序查找，對(duì)有序的數(shù)組采用對(duì)未排序的數(shù)組采用順序查找，對(duì)有序的數(shù)組采用折半查找。折半查找。&元素的插入元素的插入 尾部插入：新數(shù)據(jù)直接插入原數(shù)組的尾部尾部插入：新數(shù)據(jù)直接插入原數(shù)組的尾部尾部插入：新數(shù)據(jù)直接插入原數(shù)組的尾部尾部插入：新數(shù)據(jù)直接插入原數(shù)組的尾部 開(kāi)始或中間插入：需要將插入位置之后的所有元素向后開(kāi)始或中間插入：需要將插入位置之后的所有元素向后開(kāi)始或中間插入：需要將插入位置之后的所有元素向后開(kāi)始或中間插入：需要將插入位置之后的所有元素向后移動(dòng)，最后插入指定元素。移動(dòng)，最后插入指定元素。移動(dòng)，最后插入指定元素。移動(dòng)，最后插入指定元素。16數(shù)組操作數(shù)組操作&元素的刪除元素的刪除：刪除某個(gè)元素后，后續(xù)的元素需要：刪除某個(gè)元素后，后續(xù)的元素需要向前移動(dòng)。向前移動(dòng)。&檢索元素檢索元素：隨機(jī)存取一個(gè)元素，直接通過(guò)下標(biāo)索：隨機(jī)存取一個(gè)元素，直接通過(guò)下標(biāo)索引的方式進(jìn)行訪問(wèn)，如引的方式進(jìn)行訪問(wèn)，如scores9scores9&數(shù)組的遍歷數(shù)組的遍歷：應(yīng)用與數(shù)組中每個(gè)元素的操作。：應(yīng)用與數(shù)組中每個(gè)元素的操作。17求數(shù)組元素的平均值求數(shù)組元素的平均值185、數(shù)組應(yīng)用、數(shù)組應(yīng)用&數(shù)組適合于插入和刪除操作較少，而需要大量的數(shù)組適合于插入和刪除操作較少，而需要大量的查找和檢索操作的場(chǎng)合。查找和檢索操作的場(chǎng)合。&在需要大量插入和刪除操作情況下，不適宜使用在需要大量插入和刪除操作情況下，不適宜使用數(shù)組。數(shù)組。19本章內(nèi)容安排本章內(nèi)容安排&數(shù)組數(shù)組&記錄記錄&鏈表鏈表20記錄記錄&記錄記錄(結(jié)構(gòu)體結(jié)構(gòu)體)是是一組相關(guān)元素的集合一組相關(guān)元素的集合，它們可能是，它們可能是不同的類型，整個(gè)記錄有一個(gè)名稱。記錄中的每個(gè)不同的類型，整個(gè)記錄有一個(gè)名稱。記錄中的每個(gè)元素稱為元素稱為域域。域是具有含義的命名數(shù)據(jù)的最小元素。域是具有含義的命名數(shù)據(jù)的最小元素。&數(shù)組中所有元素必須是同一種類型，數(shù)組中所有元素必須是同一種類型，記錄中的元記錄中的元素可以是相同或不同類型素可以是相同或不同類型。211、記錄的示例、記錄的示例22記錄記錄記錄中多個(gè)元素可以是相同或不同類型，但記錄中記錄中多個(gè)元素可以是相同或不同類型，但記錄中記錄中多個(gè)元素可以是相同或不同類型，但記錄中記錄中多個(gè)元素可以是相同或不同類型，但記錄中的的的的所有元素必須是相關(guān)的所有元素必須是相關(guān)的所有元素必須是相關(guān)的所有元素必須是相關(guān)的。記錄中的數(shù)據(jù)往往和一個(gè)記錄中的數(shù)據(jù)往往和一個(gè)記錄中的數(shù)據(jù)往往和一個(gè)記錄中的數(shù)據(jù)往往和一個(gè)對(duì)象對(duì)象對(duì)象對(duì)象關(guān)聯(lián)，如第二個(gè)例子關(guān)聯(lián)，如第二個(gè)例子關(guān)聯(lián)，如第二個(gè)例子關(guān)聯(lián)，如第二個(gè)例子中的數(shù)據(jù)都與一個(gè)學(xué)生關(guān)聯(lián)；不要將不相關(guān)的數(shù)據(jù)中的數(shù)據(jù)都與一個(gè)學(xué)生關(guān)聯(lián)；不要將不相關(guān)的數(shù)據(jù)中的數(shù)據(jù)都與一個(gè)學(xué)生關(guān)聯(lián)；不要將不相關(guān)的數(shù)據(jù)中的數(shù)據(jù)都與一個(gè)學(xué)生關(guān)聯(lián)；不要將不相關(guān)的數(shù)據(jù)組合到一起。組合到一起。組合到一起。組合到一起。注意注意注意注意:23記錄名與域名記錄名與域名&記錄的名稱是整個(gè)結(jié)構(gòu)的名字，記錄的名稱是整個(gè)結(jié)構(gòu)的名字，域的名字允許我們存取特定的域。域的名字允許我們存取特定的域。&右圖中，記錄的名字為右圖中，記錄的名字為studentstudent，域名字分別為：，域名字分別為：studentstudent.ididstudentstudent.namenamestudentstudent.gradegrade242、記錄與數(shù)組、記錄與數(shù)組&數(shù)組定義了數(shù)組定義了相同類型元素的集合相同類型元素的集合，常用于描述多，常用于描述多個(gè)同類對(duì)象的信息，如定義一個(gè)班級(jí)的學(xué)生成績(jī)個(gè)同類對(duì)象的信息，如定義一個(gè)班級(jí)的學(xué)生成績(jī)（4040個(gè)同學(xué)）。個(gè)同學(xué)）。&記錄常用于定義記錄常用于定義同一個(gè)對(duì)象的屬性集合同一個(gè)對(duì)象的屬性集合，如描述，如描述某個(gè)學(xué)生的學(xué)號(hào)、姓名、成績(jī)等，域的數(shù)據(jù)類型往某個(gè)學(xué)生的學(xué)號(hào)、姓名、成績(jī)等，域的數(shù)據(jù)類型往往不同。往不同。253、記錄數(shù)組、記錄數(shù)組&一種特殊的數(shù)組，本身是數(shù)組，包含多個(gè)元素。一種特殊的數(shù)組，本身是數(shù)組，包含多個(gè)元素。數(shù)組中的每個(gè)元素是一個(gè)記錄數(shù)組中的每個(gè)元素是一個(gè)記錄。&記錄數(shù)組往往用于定義多個(gè)對(duì)象的屬性信息。如記錄數(shù)組往往用于定義多個(gè)對(duì)象的屬性信息。如班級(jí)中有班級(jí)中有3030名同學(xué)，可以定義一個(gè)記錄的數(shù)組，每名同學(xué)，可以定義一個(gè)記錄的數(shù)組，每個(gè)記錄描述一位學(xué)生的信息。個(gè)記錄描述一位學(xué)生的信息。26記錄數(shù)組記錄數(shù)組訪問(wèn)第訪問(wèn)第2個(gè)學(xué)生的姓名：個(gè)學(xué)生的姓名：(student2).name27示例：訪問(wèn)記錄數(shù)組中的每個(gè)記錄域示例：訪問(wèn)記錄數(shù)組中的每個(gè)記錄域28示例：循環(huán)訪問(wèn)記錄數(shù)組示例：循環(huán)訪問(wèn)記錄數(shù)組29本章內(nèi)容安排本章內(nèi)容安排&數(shù)組數(shù)組&記錄記錄&鏈表鏈表30鏈表鏈表&鏈表鏈表也是一個(gè)也是一個(gè)有序數(shù)據(jù)的集合有序數(shù)據(jù)的集合，但每個(gè)元素包含，但每個(gè)元素包含下一個(gè)元素的地址。每個(gè)元素包含兩部分：下一個(gè)元素的地址。每個(gè)元素包含兩部分：數(shù)據(jù)和數(shù)據(jù)和鏈鏈(鏈?zhǔn)谴鎯?chǔ)下一個(gè)元素地址的指針鏈?zhǔn)谴鎯?chǔ)下一個(gè)元素地址的指針)。&此處只討論此處只討論單鏈表單鏈表，每個(gè)，每個(gè)節(jié)點(diǎn)節(jié)點(diǎn)僅有一個(gè)指向后繼僅有一個(gè)指向后繼節(jié)點(diǎn)的鏈。通常使用一個(gè)指針變量指向第一個(gè)元素，節(jié)點(diǎn)的鏈。通常使用一個(gè)指針變量指向第一個(gè)元素，稱為鏈表的稱為鏈表的頭指針頭指針。鏈表的最后一個(gè)元素包含一個(gè)。鏈表的最后一個(gè)元素包含一個(gè)空指針，標(biāo)識(shí)鏈表的結(jié)束。空指針，標(biāo)識(shí)鏈表的結(jié)束。31鏈表示意鏈表示意32節(jié)點(diǎn)節(jié)點(diǎn)&鏈表中的元素習(xí)慣上被稱為鏈表中的元素習(xí)慣上被稱為節(jié)點(diǎn)節(jié)點(diǎn)，節(jié)點(diǎn)是至少包，節(jié)點(diǎn)是至少包含含兩個(gè)域的記錄兩個(gè)域的記錄。一個(gè)域用于保存數(shù)據(jù)部分，另一。一個(gè)域用于保存數(shù)據(jù)部分，另一個(gè)域包含指向下一個(gè)節(jié)點(diǎn)的地址。個(gè)域包含指向下一個(gè)節(jié)點(diǎn)的地址。33數(shù)組與列表數(shù)組與列表&數(shù)組元素在內(nèi)存中數(shù)組元素在內(nèi)存中連續(xù)存儲(chǔ)連續(xù)存儲(chǔ)，通過(guò)索引下標(biāo)可對(duì)，通過(guò)索引下標(biāo)可對(duì)某個(gè)元素直接存取。某個(gè)元素直接存取。&鏈表中的節(jié)點(diǎn)在內(nèi)存中是鏈表中的節(jié)點(diǎn)在內(nèi)存中是分散存儲(chǔ)分散存儲(chǔ)的，通過(guò)節(jié)點(diǎn)的，通過(guò)節(jié)點(diǎn)中的指針域鏈在一起。中的指針域鏈在一起。&在鏈表中插入、刪除節(jié)點(diǎn)方便高效，但需要額外在鏈表中插入、刪除節(jié)點(diǎn)方便高效，但需要額外的域存儲(chǔ)地址；此外鏈表查詢需要遍歷鏈表。的域存儲(chǔ)地址；此外鏈表查詢需要遍歷鏈表。34數(shù)組與鏈表數(shù)組與鏈表35鏈表名與節(jié)點(diǎn)名鏈表名與節(jié)點(diǎn)名&鏈表通常有一個(gè)鏈表通常有一個(gè)頭指針頭指針，指向第一個(gè)元素，指向第一個(gè)元素，頭指頭指針標(biāo)識(shí)整個(gè)鏈表針標(biāo)識(shí)整個(gè)鏈表，做為鏈表的名字。，做為鏈表的名字。&節(jié)點(diǎn)節(jié)點(diǎn)在鏈表中沒(méi)有明顯的名字，存在隱含的名字。在鏈表中沒(méi)有明顯的名字，存在隱含的名字。以以C C語(yǔ)言為例，某個(gè)節(jié)點(diǎn)的名字通過(guò)指向它的指針語(yǔ)言為例，某個(gè)節(jié)點(diǎn)的名字通過(guò)指向它的指針間接獲得。間接獲得。&如如p p指向某個(gè)節(jié)點(diǎn)，則節(jié)點(diǎn)名字為指向某個(gè)節(jié)點(diǎn)，則節(jié)點(diǎn)名字為(*p)(*p)。36節(jié)點(diǎn)名字節(jié)點(diǎn)名字37鏈表的操作鏈表的操作&對(duì)鏈表的操作很多，在此我們只給出幾種基本操對(duì)鏈表的操作很多，在此我們只給出幾種基本操作：作：搜索鏈表搜索鏈表搜索鏈表搜索鏈表 插入節(jié)點(diǎn)插入節(jié)點(diǎn)插入節(jié)點(diǎn)插入節(jié)點(diǎn) 刪除節(jié)點(diǎn)刪除節(jié)點(diǎn)刪除節(jié)點(diǎn)刪除節(jié)點(diǎn) 檢索鏈表檢索鏈表檢索鏈表檢索鏈表 遍歷鏈表遍歷鏈表遍歷鏈表遍歷鏈表381、搜索鏈表、搜索鏈表&鏈表的搜索只能是鏈表的搜索只能是順序搜索順序搜索，鏈表中節(jié)點(diǎn)沒(méi)有特，鏈表中節(jié)點(diǎn)沒(méi)有特定的名字。定的名字。&搜索鏈表時(shí)，通過(guò)一個(gè)標(biāo)識(shí)變量表示是否搜索到搜索鏈表時(shí)，通過(guò)一個(gè)標(biāo)識(shí)變量表示是否搜索到目標(biāo)。當(dāng)搜索到時(shí)，將該標(biāo)識(shí)變量置為目標(biāo)。當(dāng)搜索到時(shí)，將該標(biāo)識(shí)變量置為truetrue，同時(shí)，同時(shí)用指針變量指向含有目標(biāo)值的節(jié)點(diǎn)。用指針變量指向含有目標(biāo)值的節(jié)點(diǎn)。39鏈表搜索示意圖鏈表搜索示意圖4041鏈表搜索算法鏈表搜索算法422、插入節(jié)點(diǎn)、插入節(jié)點(diǎn)&鏈表通常按照關(guān)鍵字有序排列，不允許插入重復(fù)鏈表通常按照關(guān)鍵字有序排列，不允許插入重復(fù)值。值。&插入新節(jié)點(diǎn)前，插入新節(jié)點(diǎn)前，先搜索鏈表先搜索鏈表，只有當(dāng)插入的目標(biāo)，只有當(dāng)插入的目標(biāo)值不存在時(shí)才允許執(zhí)行插入操作值不存在時(shí)才允許執(zhí)行插入操作&要考慮幾種不同的情況要考慮幾種不同的情況 向空表插入節(jié)點(diǎn)向空表插入節(jié)點(diǎn)向空表插入節(jié)點(diǎn)向空表插入節(jié)點(diǎn) 向表的開(kāi)始處插入節(jié)點(diǎn)向表的開(kāi)始處插入節(jié)點(diǎn)向表的開(kāi)始處插入節(jié)點(diǎn)向表的開(kāi)始處插入節(jié)點(diǎn) 向表尾插入節(jié)點(diǎn)向表尾插入節(jié)點(diǎn)向表尾插入節(jié)點(diǎn)向表尾插入節(jié)點(diǎn) 在表中插入節(jié)點(diǎn)在表中插入節(jié)點(diǎn)在表中插入節(jié)點(diǎn)在表中插入節(jié)點(diǎn)43表頭插入節(jié)點(diǎn)表頭插入節(jié)點(diǎn)44表尾插入節(jié)點(diǎn)表尾插入節(jié)點(diǎn)45表中插入節(jié)點(diǎn)表中插入節(jié)點(diǎn)46插入節(jié)點(diǎn)的算法插入節(jié)點(diǎn)的算法473、刪除節(jié)點(diǎn)、刪除節(jié)點(diǎn)&刪除節(jié)點(diǎn)之前，刪除節(jié)點(diǎn)之前，先搜索鏈表先搜索鏈表，只有當(dāng)搜索的目標(biāo)，只有當(dāng)搜索的目標(biāo)存在時(shí)才能刪除。存在時(shí)才能刪除。&刪除節(jié)點(diǎn)要考慮兩種情況刪除節(jié)點(diǎn)要考慮兩種情況 刪除首節(jié)點(diǎn)刪除首節(jié)點(diǎn)刪除首節(jié)點(diǎn)刪除首節(jié)點(diǎn) 刪除其他節(jié)點(diǎn)（中間或尾節(jié)點(diǎn)）刪除其他節(jié)點(diǎn)（中間或尾節(jié)點(diǎn)）刪除其他節(jié)點(diǎn)（中間或尾節(jié)點(diǎn)）刪除其他節(jié)點(diǎn)（中間或尾節(jié)點(diǎn)）48刪除首節(jié)點(diǎn)刪除首節(jié)點(diǎn)49刪除中間或尾節(jié)點(diǎn)刪除中間或尾節(jié)點(diǎn)50刪除節(jié)點(diǎn)的算法刪除節(jié)點(diǎn)的算法514、檢索鏈表、檢索鏈表&檢索檢索是為了檢查或復(fù)制節(jié)點(diǎn)中所含數(shù)據(jù)，而隨機(jī)是為了檢查或復(fù)制節(jié)點(diǎn)中所含數(shù)據(jù)，而隨機(jī)訪問(wèn)節(jié)點(diǎn)，檢索之前，首先需要通過(guò)搜索鏈表定位訪問(wèn)節(jié)點(diǎn)，檢索之前，首先需要通過(guò)搜索鏈表定位目標(biāo)節(jié)點(diǎn)。目標(biāo)節(jié)點(diǎn)。&找到目標(biāo)節(jié)點(diǎn)后，通常會(huì)返回目標(biāo)節(jié)點(diǎn)的數(shù)據(jù)。找到目標(biāo)節(jié)點(diǎn)后，通常會(huì)返回目標(biāo)節(jié)點(diǎn)的數(shù)據(jù)。52檢索鏈表的算法檢索鏈表的算法535、遍歷鏈表、遍歷鏈表&從第一個(gè)節(jié)點(diǎn)開(kāi)始，依次檢查并處理每個(gè)節(jié)點(diǎn)直從第一個(gè)節(jié)點(diǎn)開(kāi)始，依次檢查并處理每個(gè)節(jié)點(diǎn)直到最后一個(gè)節(jié)點(diǎn)。遍歷在各種算法中被廣泛使用，到最后一個(gè)節(jié)點(diǎn)。遍歷在各種算法中被廣泛使用，如修改節(jié)點(diǎn)的值、打印列表、計(jì)算某個(gè)域的和、計(jì)如修改節(jié)點(diǎn)的值、打印列表、計(jì)算某個(gè)域的和、計(jì)算平均值等。算平均值等。&遍歷鏈表需要一個(gè)遍歷鏈表需要一個(gè)步進(jìn)指針步進(jìn)指針，配合循環(huán)結(jié)構(gòu)，指，配合循環(huán)結(jié)構(gòu)，指針從一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)，直到處理完最后針從一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)，直到處理完最后一個(gè)節(jié)點(diǎn)，步進(jìn)指針變成空指針從而結(jié)束循環(huán)。一個(gè)節(jié)點(diǎn)，步進(jìn)指針變成空指針從而結(jié)束循環(huán)。54遍歷的示意遍歷的示意55遍歷鏈表的算法遍歷鏈表的算法56鏈表的應(yīng)用鏈表的應(yīng)用&優(yōu)點(diǎn)：優(yōu)點(diǎn)：當(dāng)需要對(duì)存儲(chǔ)數(shù)據(jù)執(zhí)行許多插入和刪除操作時(shí)，鏈表非當(dāng)需要對(duì)存儲(chǔ)數(shù)據(jù)執(zhí)行許多插入和刪除操作時(shí)，鏈表非當(dāng)需要對(duì)存儲(chǔ)數(shù)據(jù)執(zhí)行許多插入和刪除操作時(shí)，鏈表非當(dāng)需要對(duì)存儲(chǔ)數(shù)據(jù)執(zhí)行許多插入和刪除操作時(shí)，鏈表非常高效，鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。常高效，鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。常高效，鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。常高效，鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。開(kāi)始時(shí)鏈表中沒(méi)有節(jié)點(diǎn)，需要新節(jié)點(diǎn)時(shí)，逐漸增長(zhǎng)，節(jié)開(kāi)始時(shí)鏈表中沒(méi)有節(jié)點(diǎn)，需要新節(jié)點(diǎn)時(shí)，逐漸增長(zhǎng)，節(jié)開(kāi)始時(shí)鏈表中沒(méi)有節(jié)點(diǎn)，需要新節(jié)點(diǎn)時(shí)，逐漸增長(zhǎng)，節(jié)開(kāi)始時(shí)鏈表中沒(méi)有節(jié)點(diǎn)，需要新節(jié)點(diǎn)時(shí)，逐漸增長(zhǎng)，節(jié)點(diǎn)也很容易被刪除，不影響其他節(jié)點(diǎn)。點(diǎn)也很容易被刪除，不影響其他節(jié)點(diǎn)。點(diǎn)也很容易被刪除，不影響其他節(jié)點(diǎn)。點(diǎn)也很容易被刪除，不影響其他節(jié)點(diǎn)。&鏈表的不足鏈表的不足 每個(gè)節(jié)點(diǎn)需要增加額外的域，保存下一個(gè)節(jié)點(diǎn)的地址每個(gè)節(jié)點(diǎn)需要增加額外的域，保存下一個(gè)節(jié)點(diǎn)的地址每個(gè)節(jié)點(diǎn)需要增加額外的域，保存下一個(gè)節(jié)點(diǎn)的地址每個(gè)節(jié)點(diǎn)需要增加額外的域，保存下一個(gè)節(jié)點(diǎn)的地址 搜索鏈表的效率較低。搜索鏈表的效率較低。搜索鏈表的效率較低。搜索鏈表的效率較低。57