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