高中 Scratch 課件：08-鏈表簡介

本節(jié)目標(biāo)鏈表及其操作常見數(shù)據(jù)結(jié)構(gòu)本節(jié)目標(biāo)鏈表及其操作鏈表及其操作2-1手工方式新建和刪除導(dǎo)入和導(dǎo)出數(shù)據(jù)添加刪除元素顯示和隱藏改變顯示大小命令方式見下頁鏈表及其操作2-1手工方式鏈表及其操作2-2鏈表及其操作2-2鏈表應(yīng)用練習(xí)2-1新建鏈表chengji，通過程序清空鏈表所有元素提示用戶輸入5個數(shù)字，并將數(shù)字保存到鏈表計(jì)算輸出所有鏈表元素的和、最大值、最小值和平均值鏈表應(yīng)用練習(xí)2-1新建鏈表chengji，通過程序鏈表應(yīng)用練習(xí)2-2鏈表元素輸入查找計(jì)算鏈表應(yīng)用練習(xí)2-2鏈表元素輸入查找計(jì)算數(shù)據(jù)結(jié)構(gòu)3-1數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。數(shù)據(jù)結(jié)構(gòu)3-1數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)3-2一個數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的。對數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)必須在計(jì)算機(jī)內(nèi)存儲，數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)形式，是其在計(jì)算機(jī)內(nèi)的表示；討論一個數(shù)據(jù)結(jié)構(gòu)必須同時討論在該類數(shù)據(jù)上執(zhí)行的運(yùn)算才有意義。數(shù)據(jù)結(jié)構(gòu)3-2一個數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織數(shù)據(jù)結(jié)構(gòu)3-3常見數(shù)據(jù)結(jié)構(gòu)集合數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系線性結(jié)構(gòu)線性結(jié)構(gòu)中元素之間存在一對一關(guān)系樹形結(jié)構(gòu)樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系圖形結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系數(shù)據(jù)結(jié)構(gòu)3-3常見數(shù)據(jù)結(jié)構(gòu)集合性質(zhì)由一組相同數(shù)據(jù)類型的成員組成同一集合的成員必須互不相同集合中的成員一般是無序的，沒有先后次序關(guān)系應(yīng)用舉例實(shí)現(xiàn)一個生字本，記錄不熟悉的英語單詞，同一單詞只記錄一次集合性質(zhì)線性結(jié)構(gòu)6-1性質(zhì)除起始元素外,線性表中的其他元素僅有一個直接前驅(qū)元素除終端元素外,線性表中的其他元素僅有一個直接后繼元素應(yīng)用舉例輸入并保存班級英語成績，計(jì)算平均成績線性結(jié)構(gòu)6-1性質(zhì)線性結(jié)構(gòu)6-2分類1、數(shù)組(Array)在程序設(shè)計(jì)中，為了處理方便，把具有相同類型的若干變量按有序的形式組織起來。這些按序排列的同類數(shù)據(jù)元素的集合稱為數(shù)組數(shù)組大小一般是“靜態(tài)”的，插入、刪除操作比較困難線性結(jié)構(gòu)6-2分類線性結(jié)構(gòu)6-3分類2、棧(Stack)是只能在某一端插入和刪除的特殊線性表它按照后進(jìn)先出的原則存儲數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）插入刪除只能從一端進(jìn)行線性結(jié)構(gòu)6-3分類線性結(jié)構(gòu)6-4線性結(jié)構(gòu)6-4線性結(jié)構(gòu)6-5分類3、隊(duì)列(Queue)一種特殊的線性表，它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列中沒有元素時，稱為空隊(duì)列先進(jìn)先出插入從一端進(jìn)行，刪除從另一端進(jìn)行線性結(jié)構(gòu)6-5分類線性結(jié)構(gòu)6-6分類鏈表(LinkedList)是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時動態(tài)生成。每個結(jié)點(diǎn)包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點(diǎn)地址的指針域。插入、刪除可從任意位置進(jìn)行線性結(jié)構(gòu)6-6分類樹形結(jié)構(gòu)樹(Tree)包含n（n>0）個結(jié)點(diǎn)的有窮集合K，且在K中：（1）有且僅有一個結(jié)點(diǎn)k0，沒有前驅(qū)，稱K0為樹的根結(jié)點(diǎn)。簡稱為根（root）（2）除k0外，k中的每個結(jié)點(diǎn)，有且僅有一個前驅(qū)（3）K中各結(jié)點(diǎn)，可以有m個后繼（m>=0）C盤下所有文件夾和文件構(gòu)成一棵樹樹形結(jié)構(gòu)樹(Tree)C盤下所有文件夾和文件構(gòu)成一棵樹圖（網(wǎng)狀結(jié)構(gòu)）圖(Graph)圖是由結(jié)點(diǎn)的有窮集合V和邊的集合E組成其中，為了與樹形結(jié)構(gòu)加以區(qū)別，在圖結(jié)構(gòu)中常常將結(jié)點(diǎn)稱為頂點(diǎn)邊是頂點(diǎn)的有序偶對，若兩個頂點(diǎn)之間存在一條邊，就表示這兩個頂點(diǎn)具有相鄰關(guān)系簡單圖：不含多重邊和自環(huán)的圖應(yīng)用舉例：多個城市，道路相連，最短路徑選擇圖（網(wǎng)狀結(jié)構(gòu)）圖(Graph)數(shù)據(jù)結(jié)構(gòu)的操作不同的數(shù)據(jù)結(jié)構(gòu)其操作集不同，但下列操作必不可缺：1.結(jié)構(gòu)的生成2.結(jié)構(gòu)的銷毀3.在結(jié)構(gòu)中查找滿足規(guī)定條件的數(shù)據(jù)元素4.在結(jié)構(gòu)中插入新的數(shù)據(jù)元素5.刪除結(jié)構(gòu)中已經(jīng)存在的數(shù)據(jù)元素6.遍歷數(shù)據(jù)結(jié)構(gòu)的操作不同的數(shù)據(jù)結(jié)構(gòu)其操作集不同，但下列操作必不可缺總結(jié)鏈表及其操作常見數(shù)據(jù)結(jié)構(gòu)總結(jié)鏈表及其操作本節(jié)目標(biāo)鏈表及其操作常見數(shù)據(jù)結(jié)構(gòu)本節(jié)目標(biāo)鏈表及其操作鏈表及其操作2-1手工方式新建和刪除導(dǎo)入和導(dǎo)出數(shù)據(jù)添加刪除元素顯示和隱藏改變顯示大小命令方式見下頁鏈表及其操作2-1手工方式鏈表及其操作2-2鏈表及其操作2-2鏈表應(yīng)用練習(xí)2-1新建鏈表chengji，通過程序清空鏈表所有元素提示用戶輸入5個數(shù)字，并將數(shù)字保存到鏈表計(jì)算輸出所有鏈表元素的和、最大值、最小值和平均值鏈表應(yīng)用練習(xí)2-1新建鏈表chengji，通過程序鏈表應(yīng)用練習(xí)2-2鏈表元素輸入查找計(jì)算鏈表應(yīng)用練習(xí)2-2鏈表元素輸入查找計(jì)算數(shù)據(jù)結(jié)構(gòu)3-1數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。數(shù)據(jù)結(jié)構(gòu)3-1數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)3-2一個數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的。對數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)必須在計(jì)算機(jī)內(nèi)存儲，數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)形式，是其在計(jì)算機(jī)內(nèi)的表示；討論一個數(shù)據(jù)結(jié)構(gòu)必須同時討論在該類數(shù)據(jù)上執(zhí)行的運(yùn)算才有意義。數(shù)據(jù)結(jié)構(gòu)3-2一個數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織數(shù)據(jù)結(jié)構(gòu)3-3常見數(shù)據(jù)結(jié)構(gòu)集合數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系線性結(jié)構(gòu)線性結(jié)構(gòu)中元素之間存在一對一關(guān)系樹形結(jié)構(gòu)樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系圖形結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系數(shù)據(jù)結(jié)構(gòu)3-3常見數(shù)據(jù)結(jié)構(gòu)集合性質(zhì)由一組相同數(shù)據(jù)類型的成員組成同一集合的成員必須互不相同集合中的成員一般是無序的，沒有先后次序關(guān)系應(yīng)用舉例實(shí)現(xiàn)一個生字本，記錄不熟悉的英語單詞，同一單詞只記錄一次集合性質(zhì)線性結(jié)構(gòu)6-1性質(zhì)除起始元素外,線性表中的其他元素僅有一個直接前驅(qū)元素除終端元素外,線性表中的其他元素僅有一個直接后繼元素應(yīng)用舉例輸入并保存班級英語成績，計(jì)算平均成績線性結(jié)構(gòu)6-1性質(zhì)線性結(jié)構(gòu)6-2分類1、數(shù)組(Array)在程序設(shè)計(jì)中，為了處理方便，把具有相同類型的若干變量按有序的形式組織起來。這些按序排列的同類數(shù)據(jù)元素的集合稱為數(shù)組數(shù)組大小一般是“靜態(tài)”的，插入、刪除操作比較困難線性結(jié)構(gòu)6-2分類線性結(jié)構(gòu)6-3分類2、棧(Stack)是只能在某一端插入和刪除的特殊線性表它按照后進(jìn)先出的原則存儲數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）插入刪除只能從一端進(jìn)行線性結(jié)構(gòu)6-3分類線性結(jié)構(gòu)6-4線性結(jié)構(gòu)6-4線性結(jié)構(gòu)6-5分類3、隊(duì)列(Queue)一種特殊的線性表，它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列中沒有元素時，稱為空隊(duì)列先進(jìn)先出插入從一端進(jìn)行，刪除從另一端進(jìn)行線性結(jié)構(gòu)6-5分類線性結(jié)構(gòu)6-6分類鏈表(LinkedList)是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時動態(tài)生成。每個結(jié)點(diǎn)包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點(diǎn)地址的指針域。插入、刪除可從任意位置進(jìn)行線性結(jié)構(gòu)6-6分類樹形結(jié)構(gòu)樹(Tree)包含n（n>0）個結(jié)點(diǎn)的有窮集合K，且在K中：（1）有且僅有一個結(jié)點(diǎn)k0，沒有前驅(qū)，稱K0為樹的根結(jié)點(diǎn)。簡稱為根（root）（2）除k0外，k中的每個結(jié)點(diǎn)，有且僅有一個前驅(qū)（3）K中各結(jié)點(diǎn)，可以有m個后繼（m>=0）C盤下所有文件夾和文件構(gòu)成一棵樹樹形結(jié)構(gòu)樹(Tree)C盤下所有文件夾和文件構(gòu)成一棵樹圖（網(wǎng)狀結(jié)構(gòu)）圖(Graph)圖是由結(jié)點(diǎn)的有窮集合V和邊的集合E組成其中，為了與樹形結(jié)構(gòu)加以區(qū)別，在圖結(jié)構(gòu)中常常將結(jié)點(diǎn)稱為頂點(diǎn)邊是頂點(diǎn)的有序偶對，若兩個頂點(diǎn)之間存在一條邊，就表示這兩個頂點(diǎn)具有相鄰關(guān)系簡單圖：不含多重邊和自環(huán)的圖應(yīng)用舉例：多個城市，道路相