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

《計算機科學(xué)導(dǎo)論》PPT配套課件,計算機科學(xué)導(dǎo)論,計算機科學(xué),導(dǎo)論,PPT,配套,課件 第第1212章章 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型本章內(nèi)容安排本章內(nèi)容安排&背景背景&棧棧&隊列隊列&廣義線性表廣義線性表&樹樹&二叉樹二叉樹&二叉搜索樹二叉搜索樹&圖圖2背景背景&處理數(shù)據(jù)時，需要定義處理數(shù)據(jù)時，需要定義數(shù)據(jù)類型數(shù)據(jù)類型和在數(shù)據(jù)上進行和在數(shù)據(jù)上進行的的操作操作。&數(shù)據(jù)類型的定義和應(yīng)用于數(shù)據(jù)的操作定義是抽象數(shù)據(jù)類型的定義和應(yīng)用于數(shù)據(jù)的操作定義是抽象數(shù)據(jù)類型數(shù)據(jù)類型ADTADT的重要概念。的重要概念。&ADTADT向用戶向用戶隱藏隱藏數(shù)據(jù)類型之上的操作是如何實現(xiàn)數(shù)據(jù)類型之上的操作是如何實現(xiàn)的，用戶只需要知道針對數(shù)據(jù)的一組操作，而不用的，用戶只需要知道針對數(shù)據(jù)的一組操作，而不用關(guān)心具體實現(xiàn)細節(jié)。關(guān)心具體實現(xiàn)細節(jié)。31、簡單抽象數(shù)據(jù)類型、簡單抽象數(shù)據(jù)類型&編程語言會定義一些簡單的抽象數(shù)據(jù)類型做為語編程語言會定義一些簡單的抽象數(shù)據(jù)類型做為語言的構(gòu)成部分言的構(gòu)成部分。&如如C C語言中定義了整數(shù)。該語言中定義了整數(shù)。該ADTADT定義了預(yù)定義范定義了預(yù)定義范圍的整數(shù)，同時定義了可在這種數(shù)據(jù)類型上執(zhí)行的圍的整數(shù)，同時定義了可在這種數(shù)據(jù)類型上執(zhí)行的操作（加、減、乘、除等）。操作（加、減、乘、除等）。&程序員只需要知道數(shù)據(jù)類型及其相關(guān)的運算，不程序員只需要知道數(shù)據(jù)類型及其相關(guān)的運算，不用關(guān)心具體運算是如何實現(xiàn)的。用關(guān)心具體運算是如何實現(xiàn)的。42、復(fù)雜抽象數(shù)據(jù)類型、復(fù)雜抽象數(shù)據(jù)類型&簡單抽象數(shù)據(jù)類型（整數(shù)、實數(shù)、字符、指針）簡單抽象數(shù)據(jù)類型（整數(shù)、實數(shù)、字符、指針）已經(jīng)在編程語言中實現(xiàn)。我們需要定義復(fù)雜的抽象已經(jīng)在編程語言中實現(xiàn)。我們需要定義復(fù)雜的抽象數(shù)據(jù)類型，如數(shù)據(jù)類型，如表、棧、隊列表、棧、隊列等。等。&對于表、棧等抽象數(shù)據(jù)類型的使用者，只需要知對于表、棧等抽象數(shù)據(jù)類型的使用者，只需要知道該抽象數(shù)據(jù)類型所支持的操作，無需知道這些操道該抽象數(shù)據(jù)類型所支持的操作，無需知道這些操作是如何實現(xiàn)的。作是如何實現(xiàn)的。5抽象抽象&在抽象數(shù)據(jù)類型之上，用戶不用關(guān)心任務(wù)是如何在抽象數(shù)據(jù)類型之上，用戶不用關(guān)心任務(wù)是如何完成，只用關(guān)心它能做什么，這種不需要詳細說明完成，只用關(guān)心它能做什么，這種不需要詳細說明實現(xiàn)過程的泛化操作被稱為抽象。實現(xiàn)過程的泛化操作被稱為抽象。抽象的概念意味著：抽象的概念意味著：1 1、知道一個數(shù)據(jù)類型、知道一個數(shù)據(jù)類型能做什么能做什么；2 2、如何去做是隱藏的。、如何去做是隱藏的。63、定義、定義&抽象數(shù)據(jù)類型是將對特定數(shù)據(jù)類型有意義的操作抽象數(shù)據(jù)類型是將對特定數(shù)據(jù)類型有意義的操作封裝在一起的數(shù)據(jù)聲明。封裝在一起的數(shù)據(jù)聲明。數(shù)據(jù)定義數(shù)據(jù)定義數(shù)據(jù)定義數(shù)據(jù)定義 操作定義操作定義操作定義操作定義 封裝數(shù)據(jù)與操作封裝數(shù)據(jù)與操作封裝數(shù)據(jù)與操作封裝數(shù)據(jù)與操作74、抽象數(shù)據(jù)類型模型、抽象數(shù)據(jù)類型模型8抽象數(shù)據(jù)類型模型抽象數(shù)據(jù)類型模型&抽象數(shù)據(jù)類型包含：抽象數(shù)據(jù)類型包含：數(shù)據(jù)結(jié)構(gòu)和操作函數(shù)數(shù)據(jù)結(jié)構(gòu)和操作函數(shù)（公有（公有的和私有的）。的和私有的）。&應(yīng)用程序只能通過應(yīng)用程序只能通過接口接口訪問公有操作。私有操作訪問公有操作。私有操作供內(nèi)部使用。供內(nèi)部使用。&數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)位于抽象數(shù)據(jù)類型內(nèi)部，被公有和私有位于抽象數(shù)據(jù)類型內(nèi)部，被公有和私有操作使用。操作使用。&公有操作和接口應(yīng)該獨立于實現(xiàn)。公有操作和接口應(yīng)該獨立于實現(xiàn)。95、實現(xiàn)、實現(xiàn)&計算機語言通常不提供復(fù)雜抽象數(shù)據(jù)類型的實現(xiàn)。計算機語言通常不提供復(fù)雜抽象數(shù)據(jù)類型的實現(xiàn)。&要使用抽象數(shù)據(jù)類型，首先需要實現(xiàn)它們，存儲要使用抽象數(shù)據(jù)類型，首先需要實現(xiàn)它們，存儲在庫中，在需要的地方使用它們。在庫中，在需要的地方使用它們。10本章內(nèi)容安排本章內(nèi)容安排&背景背景&棧棧&隊列隊列&廣義線性表廣義線性表&樹樹&二叉樹二叉樹&二叉搜索樹二叉搜索樹&圖圖11棧棧&棧是一種棧是一種限制線性列表，對列表的添加和刪除只限制線性列表，對列表的添加和刪除只能在能在“棧頂棧頂”進行進行。&任何只能在頂部添加或移除物體的情況都是棧，任何只能在頂部添加或移除物體的情況都是棧，如果想移除任何不是頂部的物體，首先必須移除其如果想移除任何不是頂部的物體，首先必須移除其上面的所有物體。上面的所有物體。&棧遵循棧遵循后入先出后入先出，如果插入一系列數(shù)據(jù)到棧中，如果插入一系列數(shù)據(jù)到棧中，再移走它們，那么數(shù)據(jù)的順序?qū)⒈坏罐D(zhuǎn)。再移走它們，那么數(shù)據(jù)的順序?qū)⒈坏罐D(zhuǎn)。&棧被稱為后進先出棧被稱為后進先出(LIFO)(LIFO)的數(shù)據(jù)結(jié)構(gòu)。的數(shù)據(jù)結(jié)構(gòu)。12棧的圖示棧的圖示13棧的操作棧的操作&棧可以有很多操作，但基本操作有四個：棧可以有很多操作，但基本操作有四個：建棧：建棧：建棧：建棧：stackstack 入棧：入棧：入棧：入棧：pushpush 出棧：出棧：出棧：出棧：poppop 是否為空：是否為空：是否為空：是否為空：emptyempty141、建棧、建棧&創(chuàng)建一個空棧。創(chuàng)建一個空棧。stack(stackName)stack(stackName)152、入棧、入棧push&入棧入棧在棧頂添加新的元素在棧頂添加新的元素，入棧后，新的元素成，入棧后，新的元素成為棧頂。為棧頂。push(stackName,dataItem)push(stackName,dataItem)163、出棧、出棧pop&出棧將棧頂元素移走。出棧將棧頂元素移走。pop(stackName,dataItem)pop(stackName,dataItem)174、是否空棧、是否空棧empty&檢驗棧是否為空檢驗棧是否為空。如果棧中沒有元素，表示棧為。如果棧中沒有元素，表示棧為空，返回真；否則返回假?？眨祷卣妫环駝t返回假。Empty(stackName)Empty(stackName)18棧的抽象數(shù)據(jù)類型棧的抽象數(shù)據(jù)類型19示例：棧操作及狀態(tài)示例：棧操作及狀態(tài)20棧的應(yīng)用棧的應(yīng)用&棧的應(yīng)用分為棧的應(yīng)用分為4 4大類：倒轉(zhuǎn)數(shù)據(jù)、配對數(shù)據(jù)、數(shù)據(jù)大類：倒轉(zhuǎn)數(shù)據(jù)、配對數(shù)據(jù)、數(shù)據(jù)延遲和回溯延遲和回溯 倒轉(zhuǎn)數(shù)據(jù)倒轉(zhuǎn)數(shù)據(jù)倒轉(zhuǎn)數(shù)據(jù)倒轉(zhuǎn)數(shù)據(jù)：給定一組數(shù)據(jù)，逆序重新排列：給定一組數(shù)據(jù)，逆序重新排列：給定一組數(shù)據(jù)，逆序重新排列：給定一組數(shù)據(jù)，逆序重新排列 配對數(shù)據(jù)配對數(shù)據(jù)配對數(shù)據(jù)配對數(shù)據(jù)：處理表達式中的一些字符配對，如括號的配：處理表達式中的一些字符配對，如括號的配：處理表達式中的一些字符配對，如括號的配：處理表達式中的一些字符配對，如括號的配對，常用于編譯器的語法檢查對，常用于編譯器的語法檢查對，常用于編譯器的語法檢查對，常用于編譯器的語法檢查 數(shù)據(jù)延遲：數(shù)據(jù)延遲：數(shù)據(jù)延遲：數(shù)據(jù)延遲：回溯步驟：即回到以前的步驟，是棧在應(yīng)用程序回溯步驟：即回到以前的步驟，是棧在應(yīng)用程序回溯步驟：即回到以前的步驟，是棧在應(yīng)用程序回溯步驟：即回到以前的步驟，是棧在應(yīng)用程序(計算機計算機計算機計算機游戲、決策分析、專家系統(tǒng)游戲、決策分析、專家系統(tǒng)游戲、決策分析、專家系統(tǒng)游戲、決策分析、專家系統(tǒng))中的應(yīng)用。中的應(yīng)用。中的應(yīng)用。中的應(yīng)用。21倒轉(zhuǎn)數(shù)據(jù)示例：倒轉(zhuǎn)數(shù)據(jù)示例：10進制轉(zhuǎn)二進制進制轉(zhuǎn)二進制22倒轉(zhuǎn)數(shù)據(jù)示例：倒轉(zhuǎn)數(shù)據(jù)示例：10進制轉(zhuǎn)二進制進制轉(zhuǎn)二進制23倒轉(zhuǎn)數(shù)據(jù)示例：倒轉(zhuǎn)數(shù)據(jù)示例：10進制轉(zhuǎn)二進制進制轉(zhuǎn)二進制24配對數(shù)據(jù)示例：括號配對檢查配對數(shù)據(jù)示例：括號配對檢查25配對數(shù)據(jù)示例：括號配對檢查配對數(shù)據(jù)示例：括號配對檢查26棧的實現(xiàn)棧的實現(xiàn)&在抽象數(shù)據(jù)類型層次上，我們使用棧及其在抽象數(shù)據(jù)類型層次上，我們使用棧及其4 4個操作，個操作，解決我們的應(yīng)用問題解決我們的應(yīng)用問題&在實現(xiàn)層次上，需要選擇數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)棧，棧在實現(xiàn)層次上，需要選擇數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)棧，?？梢杂每梢杂脭?shù)組或鏈表數(shù)組或鏈表實現(xiàn)。實現(xiàn)。&數(shù)組實現(xiàn)數(shù)組實現(xiàn) 數(shù)組數(shù)組數(shù)組數(shù)組 輔助記錄：包含輔助記錄：包含輔助記錄：包含輔助記錄：包含2 2個域，個域，個域，個域，1 1個于用于計數(shù)，說明棧內(nèi)數(shù)據(jù)個于用于計數(shù)，說明棧內(nèi)數(shù)據(jù)個于用于計數(shù)，說明棧內(nèi)數(shù)據(jù)個于用于計數(shù)，說明棧內(nèi)數(shù)據(jù)項數(shù)，項數(shù)，項數(shù)，項數(shù)，1 1個域指示棧頂位置（對應(yīng)數(shù)組元素的下標）個域指示棧頂位置（對應(yīng)數(shù)組元素的下標）個域指示棧頂位置（對應(yīng)數(shù)組元素的下標）個域指示棧頂位置（對應(yīng)數(shù)組元素的下標）&鏈表實現(xiàn)鏈表實現(xiàn) 鏈表的頭指針包含鏈表的頭指針包含鏈表的頭指針包含鏈表的頭指針包含2 2個域，個域，個域，個域，1 1個指針指向棧頂元素，個指針指向棧頂元素，個指針指向棧頂元素，個指針指向棧頂元素，1 1個個個個域用于棧內(nèi)元素的計數(shù)；入棧時向表頭插入元素，出棧域用于棧內(nèi)元素的計數(shù)；入棧時向表頭插入元素，出棧域用于棧內(nèi)元素的計數(shù)；入棧時向表頭插入元素，出棧域用于棧內(nèi)元素的計數(shù)；入棧時向表頭插入元素，出棧時從表頭刪除元素。時從表頭刪除元素。時從表頭刪除元素。時從表頭刪除元素。27棧的實現(xiàn)棧的實現(xiàn)28本章內(nèi)容安排本章內(nèi)容安排&背景背景&棧棧&隊列隊列&廣義線性表廣義線性表&樹樹&二叉樹二叉樹&二叉搜索樹二叉搜索樹&圖圖29隊列隊列&隊列是一種隊列是一種線性列表線性列表。數(shù)據(jù)只能在稱為。數(shù)據(jù)只能在稱為“尾部尾部”的一端插入，只能從稱為的一端插入，只能從稱為“頭部頭部”的一端刪除。的一端刪除。&隊列確保了數(shù)據(jù)在隊列中只能按照它們存入的順隊列確保了數(shù)據(jù)在隊列中只能按照它們存入的順序被處理，隊列是先進先出序被處理，隊列是先進先出(FIFO)(FIFO)結(jié)構(gòu)。結(jié)構(gòu)。30隊列的圖示隊列的圖示31隊列的操作隊列的操作&隊列的操作有很多，但基本的操作有隊列的操作有很多，但基本的操作有4 4種：種：建隊列：建隊列：建隊列：建隊列：queuequeue 入列：入列：入列：入列：enqueueenqueue 出列：出列：出列：出列：dequeuedequeue 是否為空：是否為空：是否為空：是否為空：emptyempty321、建隊列、建隊列&創(chuàng)建一個空隊列。創(chuàng)建一個空隊列。quenue(queueName)quenue(queueName)332、入列、入列&入列操作將數(shù)據(jù)插入隊尾，新元素成為隊尾。入列操作將數(shù)據(jù)插入隊尾，新元素成為隊尾。enqueue(queueName,dataItem)enqueue(queueName,dataItem)343、出列、出列&出列操作刪除隊列前端的數(shù)據(jù)項。出列操作刪除隊列前端的數(shù)據(jù)項。dequeue(quenueName,dataItem)dequeue(quenueName,dataItem)354、是否為空、是否為空empty&檢驗隊列是否為空。如果隊列中沒有數(shù)據(jù)，隊列檢驗隊列是否為空。如果隊列中沒有數(shù)據(jù)，隊列為空，返回真；否則返回假。為空，返回真；否則返回假。empty(quenueName)empty(quenueName)36隊列的抽象數(shù)據(jù)類型隊列的抽象數(shù)據(jù)類型37示例：隊列操作及狀態(tài)示例：隊列操作及狀態(tài)38隊列的應(yīng)用隊列的應(yīng)用&隊列的應(yīng)用非常廣泛，在操作系統(tǒng)、網(wǎng)絡(luò)等領(lǐng)域隊列的應(yīng)用非常廣泛，在操作系統(tǒng)、網(wǎng)絡(luò)等領(lǐng)域中都有應(yīng)用。中都有應(yīng)用。隊列應(yīng)用于在線電子商務(wù)應(yīng)用，如處理用戶需求、任務(wù)隊列應(yīng)用于在線電子商務(wù)應(yīng)用，如處理用戶需求、任務(wù)隊列應(yīng)用于在線電子商務(wù)應(yīng)用，如處理用戶需求、任務(wù)隊列應(yīng)用于在線電子商務(wù)應(yīng)用，如處理用戶需求、任務(wù)和指令。和指令。和指令。和指令。在計算機系統(tǒng)中，使用隊列完成對作業(yè)或系統(tǒng)設(shè)備的排在計算機系統(tǒng)中，使用隊列完成對作業(yè)或系統(tǒng)設(shè)備的排在計算機系統(tǒng)中，使用隊列完成對作業(yè)或系統(tǒng)設(shè)備的排在計算機系統(tǒng)中，使用隊列完成對作業(yè)或系統(tǒng)設(shè)備的排隊處理。隊處理。隊處理。隊處理。39隊列用于數(shù)據(jù)分類隊列用于數(shù)據(jù)分類&如要對一組數(shù)進行分組，如分成小于如要對一組數(shù)進行分組，如分成小于10001000和大于和大于10001000，可以先讀取數(shù)據(jù)，然后創(chuàng)建，可以先讀取數(shù)據(jù)，然后創(chuàng)建2 2個隊列，判斷個隊列，判斷某個數(shù)并將其插入到合適的隊列中，分類的同時保某個數(shù)并將其插入到合適的隊列中，分類的同時保持了原始順序持了原始順序40隊列用于數(shù)據(jù)分類隊列用于數(shù)據(jù)分類41隊列用于數(shù)據(jù)分類隊列用于數(shù)據(jù)分類42隊列用于速度匹配隊列用于速度匹配&隊列可用于調(diào)節(jié)數(shù)據(jù)快速生成和數(shù)據(jù)緩慢消費之隊列可用于調(diào)節(jié)數(shù)據(jù)快速生成和數(shù)據(jù)緩慢消費之間的平衡間的平衡 假設(shè)假設(shè)假設(shè)假設(shè)CPUCPU和打印機相連，和打印機相連，和打印機相連，和打印機相連，CPUCPU速度非?？?，造成速度非?？欤斐伤俣确浅？欤斐伤俣确浅？欤斐蒀PUCPU等等等等待打印的緩慢輸出，造成待打印的緩慢輸出，造成待打印的緩慢輸出，造成待打印的緩慢輸出，造成CPUCPU的空閑和浪費的空閑和浪費的空閑和浪費的空閑和浪費 CPUCPU生成隊列能容納的數(shù)據(jù)塊，將數(shù)據(jù)保存到隊列中，生成隊列能容納的數(shù)據(jù)塊，將數(shù)據(jù)保存到隊列中，生成隊列能容納的數(shù)據(jù)塊，將數(shù)據(jù)保存到隊列中，生成隊列能容納的數(shù)據(jù)塊，將數(shù)據(jù)保存到隊列中，CPUCPU轉(zhuǎn)向執(zhí)行其他任務(wù)，打印機從隊列中緩慢去除數(shù)據(jù)轉(zhuǎn)向執(zhí)行其他任務(wù)，打印機從隊列中緩慢去除數(shù)據(jù)轉(zhuǎn)向執(zhí)行其他任務(wù)，打印機從隊列中緩慢去除數(shù)據(jù)轉(zhuǎn)向執(zhí)行其他任務(wù)，打印機從隊列中緩慢去除數(shù)據(jù)并打印輸出，稱為并打印輸出，稱為并打印輸出，稱為并打印輸出，稱為“假脫機隊列假脫機隊列假脫機隊列假脫機隊列”。43隊列的實現(xiàn)隊列的實現(xiàn)&隊列可以用隊列可以用數(shù)組或鏈表數(shù)組或鏈表實現(xiàn)。實現(xiàn)。&數(shù)組實現(xiàn)數(shù)組實現(xiàn) 數(shù)組數(shù)組數(shù)組數(shù)組 輔助記錄：包含輔助記錄：包含輔助記錄：包含輔助記錄：包含3 3個域，個域，個域，個域，1 1個域用于記錄隊列內(nèi)的數(shù)據(jù)項個域用于記錄隊列內(nèi)的數(shù)據(jù)項個域用于記錄隊列內(nèi)的數(shù)據(jù)項個域用于記錄隊列內(nèi)的數(shù)據(jù)項數(shù)，數(shù)，數(shù)，數(shù)，2 2個域分別指示隊首和隊尾在數(shù)組中的位置個域分別指示隊首和隊尾在數(shù)組中的位置個域分別指示隊首和隊尾在數(shù)組中的位置個域分別指示隊首和隊尾在數(shù)組中的位置&鏈表實現(xiàn)鏈表實現(xiàn) 鏈表鏈表鏈表鏈表 輔助記錄：包含輔助記錄：包含輔助記錄：包含輔助記錄：包含3 3個域，個域，個域，個域，1 1個于用于記錄數(shù)據(jù)項數(shù)，個于用于記錄數(shù)據(jù)項數(shù)，個于用于記錄數(shù)據(jù)項數(shù)，個于用于記錄數(shù)據(jù)項數(shù)，1 1個個個個指向鏈表表頭的指針和指向鏈表表頭的指針和指向鏈表表頭的指針和指向鏈表表頭的指針和1 1個指向鏈表表尾的指針。入列個指向鏈表表尾的指針。入列個指向鏈表表尾的指針。入列個指向鏈表表尾的指針。入列時從表頭插入元素，出列時從表尾刪除元素（或反之）。時從表頭插入元素，出列時從表尾刪除元素（或反之）。時從表頭插入元素，出列時從表尾刪除元素（或反之）。時從表頭插入元素，出列時從表尾刪除元素（或反之）。44隊列的實現(xiàn)隊列的實現(xiàn)45本章內(nèi)容安排本章內(nèi)容安排&背景背景&棧棧&隊列隊列&廣義線性表廣義線性表&樹樹&二叉樹二叉樹&二叉搜索樹二叉搜索樹&圖圖46廣義線性表廣義線性表&棧和隊列屬于棧和隊列屬于限制線性表限制線性表。廣義線性表是插入和。廣義線性表是插入和刪除等操作可以在表中任意地方進行的表。刪除等操作可以在表中任意地方進行的表。&廣義線性表是具有如下特性的元素集合廣義線性表是具有如下特性的元素集合 元素具有相同的類型；元素具有相同的類型；元素具有相同的類型；元素具有相同的類型；元素按順序排列，存在第一個元素和最后一個元素；元素按順序排列，存在第一個元素和最后一個元素；元素按順序排列，存在第一個元素和最后一個元素；元素按順序排列，存在第一個元素和最后一個元素；除第一個元素外每個元素都有唯一的除第一個元素外每個元素都有唯一的除第一個元素外每個元素都有唯一的除第一個元素外每個元素都有唯一的前驅(qū)前驅(qū)前驅(qū)前驅(qū)；除最后一個；除最后一個；除最后一個；除最后一個元素外每個元素都有元素外每個元素都有元素外每個元素都有元素外每個元素都有后繼后繼后繼后繼元素；元素；元素；元素；每個元素是一個帶有每個元素是一個帶有每個元素是一個帶有每個元素是一個帶有關(guān)鍵字關(guān)鍵字關(guān)鍵字關(guān)鍵字字段的記錄；字段的記錄；字段的記錄；字段的記錄；元素按關(guān)鍵字值排序。元素按關(guān)鍵字值排序。元素按關(guān)鍵字值排序。元素按關(guān)鍵字值排序。47廣義線性表的操作廣義線性表的操作&可以為廣義線性表定義許多操作。此處僅討論可以為廣義線性表定義許多操作。此處僅討論6 6種種常用的操作：常用的操作：建表：建表：建表：建表：listlist 插入：插入：插入：插入：insertinsert 刪除：刪除：刪除：刪除：deletedelete 檢索：檢索：檢索：檢索：retrieveretrieve 遍歷：遍歷：遍歷：遍歷：traversetraverse 是否為空：是否為空：是否為空：是否為空：emptyempty481、建表、建表&創(chuàng)建一個空表。創(chuàng)建一個空表。list(listName)list(listName)492、插入、插入&多數(shù)情況下，要將數(shù)據(jù)插入在多數(shù)情況下，要將數(shù)據(jù)插入在有序列表有序列表中間，保中間，保持持按鍵值排序按鍵值排序。此種情況下，需要使用搜索算法確。此種情況下，需要使用搜索算法確定插入位置。定插入位置。insert(listName,element)insert(listName,element)503、刪除、刪除&執(zhí)行刪除操作，首先要執(zhí)行刪除操作，首先要定位定位到要刪除的目標。刪到要刪除的目標。刪除線性表中關(guān)鍵字值與除線性表中關(guān)鍵字值與targettarget相等的元素，刪除的相等的元素，刪除的元素通過元素通過elementelement返回。返回。修改元素通過刪除，修改值并重新插入實現(xiàn)。修改元素通過刪除，修改值并重新插入實現(xiàn)。修改元素通過刪除，修改值并重新插入實現(xiàn)。修改元素通過刪除，修改值并重新插入實現(xiàn)。delete(listName,target,element)delete(listName,target,element)514、檢索、檢索&檢索是對單個元素的存取，在列表中檢索是對單個元素的存取，在列表中定位數(shù)據(jù)定位數(shù)據(jù)然然后得到數(shù)據(jù)的副本。后得到數(shù)據(jù)的副本。關(guān)鍵字匹配關(guān)鍵字匹配關(guān)鍵字匹配關(guān)鍵字匹配targettarget的元素，被復(fù)制到的元素，被復(fù)制到的元素，被復(fù)制到的元素，被復(fù)制到elementelement中并返回，中并返回，中并返回，中并返回，原始表中的元素保持不變。原始表中的元素保持不變。原始表中的元素保持不變。原始表中的元素保持不變。retrieve(listName,target,element)retrieve(listName,target,element)525、遍歷、遍歷&遍歷是對線性表表中所有元素遍歷是對線性表表中所有元素順序逐一進行處理順序逐一進行處理的操作。的操作。按順序存取表中元素，對每個元素執(zhí)行按順序存取表中元素，對每個元素執(zhí)行按順序存取表中元素，對每個元素執(zhí)行按順序存取表中元素，對每個元素執(zhí)行actionaction指定的動指定的動指定的動指定的動作，如打印、某些數(shù)學(xué)運算作，如打印、某些數(shù)學(xué)運算作，如打印、某些數(shù)學(xué)運算作，如打印、某些數(shù)學(xué)運算traverse(listName,action)traverse(listName,action)536、是否為空、是否為空&檢查表的狀態(tài)，若表是空的返回真，否則返回假。檢查表的狀態(tài)，若表是空的返回真，否則返回假。empty(listName)empty(listName)54廣義線性表的抽象數(shù)據(jù)類型廣義線性表的抽象數(shù)據(jù)類型55示例：廣義線性表操作及狀態(tài)示例：廣義線性表操作及狀態(tài)56廣義線性表的應(yīng)用廣義線性表的應(yīng)用&廣義線性表常應(yīng)用于元素被隨機存取或順序存取廣義線性表常應(yīng)用于元素被隨機存取或順序存取的情況。的情況。&如使用廣義線性表存儲入學(xué)的學(xué)生信息。如使用廣義線性表存儲入學(xué)的學(xué)生信息。每個數(shù)據(jù)包含每個數(shù)據(jù)包含每個數(shù)據(jù)包含每個數(shù)據(jù)包含3 3個域：個域：個域：個域：IDID、NameName和和和和GradeGrade，IDID為關(guān)鍵為關(guān)鍵為關(guān)鍵為關(guān)鍵字字字字 修改成績：先刪除元素，修改返回值，插入元素修改成績：先刪除元素，修改返回值，插入元素修改成績：先刪除元素，修改返回值，插入元素修改成績：先刪除元素，修改返回值，插入元素 打印所有學(xué)生成績：打印所有學(xué)生成績：打印所有學(xué)生成績：打印所有學(xué)生成績：57修改成績算法修改成績算法58打印成績算法打印成績算法59廣義線性表的實現(xiàn)廣義線性表的實現(xiàn)&廣義線性表常可以應(yīng)用數(shù)組或鏈表實現(xiàn)廣義線性表?？梢詰?yīng)用數(shù)組或鏈表實現(xiàn)&數(shù)組實現(xiàn)數(shù)組實現(xiàn) 數(shù)組數(shù)組數(shù)組數(shù)組 輔助記錄：包含輔助記錄：包含輔助記錄：包含輔助記錄：包含2 2個域，個域，個域，個域，1 1個域用于計數(shù)，個域用于計數(shù)，個域用于計數(shù)，個域用于計數(shù)，1 1個域指示表個域指示表個域指示表個域指示表中首個元素在數(shù)組中的下標中首個元素在數(shù)組中的下標中首個元素在數(shù)組中的下標中首個元素在數(shù)組中的下標&鏈表實現(xiàn)鏈表實現(xiàn) 鏈表鏈表鏈表鏈表 輔助記錄：包含輔助記錄：包含輔助記錄：包含輔助記錄：包含2 2個域，個域，個域，個域，1 1個域用于計數(shù)，個域用于計數(shù)，個域用于計數(shù)，個域用于計數(shù)，1 1個域為指向個域為指向個域為指向個域為指向鏈表首節(jié)點的指針鏈表首節(jié)點的指針鏈表首節(jié)點的指針鏈表首節(jié)點的指針60廣義線性表的實現(xiàn)廣義線性表的實現(xiàn)61本章內(nèi)容安排本章內(nèi)容安排&背景背景&棧棧&隊列隊列&廣義線性表廣義線性表&樹樹&二叉樹二叉樹&二叉搜索樹二叉搜索樹&圖圖62樹樹&樹包括一組有限的元素，這些元素稱為樹包括一組有限的元素，這些元素稱為節(jié)點（或節(jié)點（或頂點）頂點）；同時包括一組；同時包括一組有向線段有向線段，用來連接節(jié)點，用來連接節(jié)點，稱為稱為弧弧。&頂點分類：根、葉子和內(nèi)部節(jié)點頂點分類：根、葉子和內(nèi)部節(jié)點 如果樹是非空的，有一個節(jié)點沒有進入的弧，稱為如果樹是非空的，有一個節(jié)點沒有進入的弧，稱為如果樹是非空的，有一個節(jié)點沒有進入的弧，稱為如果樹是非空的，有一個節(jié)點沒有進入的弧，稱為根根根根 沒有外出弧的節(jié)點為沒有外出弧的節(jié)點為沒有外出弧的節(jié)點為沒有外出弧的節(jié)點為葉子葉子葉子葉子節(jié)點節(jié)點節(jié)點節(jié)點 其他節(jié)點稱為其他節(jié)點稱為其他節(jié)點稱為其他節(jié)點稱為內(nèi)部內(nèi)部內(nèi)部內(nèi)部節(jié)點節(jié)點節(jié)點節(jié)點&路徑路徑 除了根以外的節(jié)點，具有從根開始唯一到達的除了根以外的節(jié)點，具有從根開始唯一到達的除了根以外的節(jié)點，具有從根開始唯一到達的除了根以外的節(jié)點，具有從根開始唯一到達的路徑路徑路徑路徑，路，路，路，路徑是一系列相鄰連接的節(jié)點序列。徑是一系列相鄰連接的節(jié)點序列。徑是一系列相鄰連接的節(jié)點序列。徑是一系列相鄰連接的節(jié)點序列。63樹的示意樹的示意64不同節(jié)點弧的數(shù)量不同節(jié)點弧的數(shù)量65術(shù)語術(shù)語&從任意給定節(jié)點可以直接到達的節(jié)點稱為其從任意給定節(jié)點可以直接到達的節(jié)點稱為其子節(jié)子節(jié)點點；出發(fā)節(jié)點為對應(yīng)子節(jié)點的；出發(fā)節(jié)點為對應(yīng)子節(jié)點的雙親雙親&具有相同雙親的節(jié)點稱為具有相同雙親的節(jié)點稱為兄弟節(jié)點兄弟節(jié)點&從某個節(jié)點出發(fā)，可以到達的節(jié)點為其從某個節(jié)點出發(fā)，可以到達的節(jié)點為其子孫子孫；出；出發(fā)節(jié)點為對應(yīng)子孫的發(fā)節(jié)點為對應(yīng)子孫的祖先祖先。&樹中每個節(jié)點都有可能包含樹中每個節(jié)點都有可能包含子樹子樹，某個節(jié)點的子，某個節(jié)點的子樹是它的一個子節(jié)點及其子孫構(gòu)成的整體。樹是它的一個子節(jié)點及其子孫構(gòu)成的整體。節(jié)點包含的子樹數(shù)量為其出弧的數(shù)量（子節(jié)點的數(shù)量）節(jié)點包含的子樹數(shù)量為其出弧的數(shù)量（子節(jié)點的數(shù)量）節(jié)點包含的子樹數(shù)量為其出弧的數(shù)量（子節(jié)點的數(shù)量）節(jié)點包含的子樹數(shù)量為其出弧的數(shù)量（子節(jié)點的數(shù)量）66術(shù)語術(shù)語67樹的應(yīng)用樹的應(yīng)用&樹在計算機科學(xué)中的應(yīng)用非常廣泛，如索引文件，樹在計算機科學(xué)中的應(yīng)用非常廣泛，如索引文件，其細節(jié)超出本門課程的范疇。其細節(jié)超出本門課程的范疇。&下面學(xué)習(xí)特殊的樹下面學(xué)習(xí)特殊的樹二叉樹二叉樹68本章內(nèi)容安排本章內(nèi)容安排&背景背景&棧棧&隊列隊列&廣義線性表廣義線性表&樹樹&二叉樹二叉樹&二叉搜索樹二叉搜索樹&圖圖69二叉樹二叉樹&二叉樹是一種樹，樹中沒有一個節(jié)點包含兩個以二叉樹是一種樹，樹中沒有一個節(jié)點包含兩個以上子樹。任何一個節(jié)點只能有上子樹。任何一個節(jié)點只能有0 0、1 1或或2 2棵子樹。節(jié)棵子樹。節(jié)點的子樹分別被稱為點的子樹分別被稱為左子樹左子樹和和右子樹右子樹。70二叉樹的遞歸定義二叉樹的遞歸定義&定義：定義：二叉樹是一棵空樹，或由二叉樹是一棵空樹，或由1 1個根節(jié)點和個根節(jié)點和2 2棵棵子樹構(gòu)成，而每棵子樹也是二叉樹子樹構(gòu)成，而每棵子樹也是二叉樹。71二叉樹的操作二叉樹的操作&二叉樹的操作二叉樹的操作 建樹建樹建樹建樹 插入插入插入插入 刪除刪除刪除刪除 檢索檢索檢索檢索 是否為空是否為空是否為空是否為空 遍歷遍歷遍歷遍歷&本課程只討論二叉樹的遍歷本課程只討論二叉樹的遍歷72二叉樹的遍歷二叉樹的遍歷&二叉樹的遍歷是按照預(yù)定的順序處理每一個節(jié)點二叉樹的遍歷是按照預(yù)定的順序處理每一個節(jié)點且僅處理一次。常用的遍歷次序有兩種：且僅處理一次。常用的遍歷次序有兩種：深度優(yōu)先遍歷深度優(yōu)先遍歷深度優(yōu)先遍歷深度優(yōu)先遍歷：又可分為：又可分為：又可分為：又可分為6 6種方式，其中的三種標準方種方式，其中的三種標準方種方式，其中的三種標準方種方式，其中的三種標準方式是前序遍歷、中序遍歷和后序遍歷式是前序遍歷、中序遍歷和后序遍歷式是前序遍歷、中序遍歷和后序遍歷式是前序遍歷、中序遍歷和后序遍歷 廣度優(yōu)先廣度優(yōu)先廣度優(yōu)先廣度優(yōu)先遍歷遍歷遍歷遍歷731、深度優(yōu)先、深度優(yōu)先&前序遍歷前序遍歷：根首先被訪問：根首先被訪問左子樹左子樹右子樹右子樹&中序遍歷中序遍歷：先處理左子樹：先處理左子樹根根右子樹右子樹&后序遍歷后序遍歷：先處理左子樹：先處理左子樹右子樹右子樹根根74示例：前序遍歷示例：前序遍歷&寫出下面的樹按照前序遍歷的訪問順序?qū)懗鱿旅娴臉浒凑涨靶虮闅v的訪問順序752、廣度優(yōu)先、廣度優(yōu)先&廣度優(yōu)先遍歷先處理當前層所有節(jié)點，再處理下廣度優(yōu)先遍歷先處理當前層所有節(jié)點，再處理下一層所有節(jié)點。一層所有節(jié)點。&寫出下面的樹按照廣度優(yōu)先遍歷的訪問順序?qū)懗鱿旅娴臉浒凑諒V度優(yōu)先遍歷的訪問順序76二叉樹的應(yīng)用二叉樹的應(yīng)用&二叉樹在計算機科學(xué)中應(yīng)用廣泛二叉樹在計算機科學(xué)中應(yīng)用廣泛 霍夫曼編碼：是一種壓縮技術(shù)，使用二叉樹生成一個符霍夫曼編碼：是一種壓縮技術(shù)，使用二叉樹生成一個符霍夫曼編碼：是一種壓縮技術(shù)，使用二叉樹生成一個符霍夫曼編碼：是一種壓縮技術(shù)，使用二叉樹生成一個符號串的可變長度二進制編碼，實現(xiàn)數(shù)據(jù)壓縮。號串的可變長度二進制編碼，實現(xiàn)數(shù)據(jù)壓縮。號串的可變長度二進制編碼，實現(xiàn)數(shù)據(jù)壓縮。號串的可變長度二進制編碼，實現(xiàn)數(shù)據(jù)壓縮。表達式樹：表達式由遵循描述規(guī)則的一系列記號構(gòu)成，表達式樹：表達式由遵循描述規(guī)則的一系列記號構(gòu)成，表達式樹：表達式由遵循描述規(guī)則的一系列記號構(gòu)成，表達式樹：表達式由遵循描述規(guī)則的一系列記號構(gòu)成，有有有有3 3種格式：中綴、后綴、前綴種格式：中綴、后綴、前綴種格式：中綴、后綴、前綴種格式：中綴、后綴、前綴11中綴：操作符位于兩個操作數(shù)之間中綴：操作符位于兩個操作數(shù)之間11后綴：操作符位于兩個操作數(shù)之后后綴：操作符位于兩個操作數(shù)之后11前綴：操作符位于兩個操作數(shù)之前前綴：操作符位于兩個操作數(shù)之前77表達式樹表達式樹&編程語言中常使用中綴表達式，而編譯程序通常在計算表達式之前將它們轉(zhuǎn)換為后綴表達式。&建立表達式樹 根和內(nèi)部節(jié)點是操作符根和內(nèi)部節(jié)點是操作符根和內(nèi)部節(jié)點是操作符根和內(nèi)部節(jié)點是操作符 葉子節(jié)點是操作數(shù)葉子節(jié)點是操作數(shù)葉子節(jié)點是操作數(shù)葉子節(jié)點是操作數(shù)&三種遍歷產(chǎn)生三種不同的表達式 前序遍歷前序遍歷前序遍歷前序遍歷中綴表達式中綴表達式中綴表達式中綴表達式 中序遍歷中序遍歷中序遍歷中序遍歷后綴表達式后綴表達式后綴表達式后綴表達式 后序遍歷后序遍歷后序遍歷后序遍歷前綴表達式前綴表達式前綴表達式前綴表達式78表達式樹表達式樹79二叉樹的實現(xiàn)二叉樹的實現(xiàn)&二叉樹可以使用數(shù)組和鏈表來實現(xiàn)二叉樹可以使用數(shù)組和鏈表來實現(xiàn)&對于刪除和插入操作，鏈表效率更高，二叉樹更對于刪除和插入操作，鏈表效率更高，二叉樹更多使用鏈表實現(xiàn)。多使用鏈表實現(xiàn)。80本章內(nèi)容安排本章內(nèi)容安排&背景背景&棧棧&隊列隊列&廣義線性表廣義線性表&樹樹&二叉樹二叉樹&二叉搜索樹二叉搜索樹&圖圖81二叉搜索樹二叉搜索樹&二叉搜索樹二叉搜索樹(BST)(BST)是一具有額外特性的二叉樹，每是一具有額外特性的二叉樹，每個節(jié)點的個節(jié)點的關(guān)鍵字關(guān)鍵字值大于左子樹中的所有的關(guān)鍵字值，值大于左子樹中的所有的關(guān)鍵字值，而小于右子樹中所有節(jié)點的關(guān)鍵字值。而小于右子樹中所有節(jié)點的關(guān)鍵字值。82示例：二叉搜索樹示例：二叉搜索樹&整棵樹符合二叉搜索樹，同時每棵子樹也符合二整棵樹符合二叉搜索樹，同時每棵子樹也符合二叉搜索樹，才是一棵完整的搜索二叉樹。叉搜索樹，才是一棵完整的搜索二叉樹。83二叉搜索樹特性二叉搜索樹特性&生成有序列表生成有序列表 如果對二叉搜索樹應(yīng)用中序遍歷，則遍歷的元素以升序如果對二叉搜索樹應(yīng)用中序遍歷，則遍歷的元素以升序如果對二叉搜索樹應(yīng)用中序遍歷，則遍歷的元素以升序如果對二叉搜索樹應(yīng)用中序遍歷，則遍歷的元素以升序排列。對排列。對排列。對排列。對BSTBST的中序遍歷可以創(chuàng)建一個升序列表。的中序遍歷可以創(chuàng)建一個升序列表。的中序遍歷可以創(chuàng)建一個升序列表。的中序遍歷可以創(chuàng)建一個升序列表。&折半查找折半查找 對二叉搜索樹，可實現(xiàn)元素的折半查找對二叉搜索樹，可實現(xiàn)元素的折半查找對二叉搜索樹，可實現(xiàn)元素的折半查找對二叉搜索樹，可實現(xiàn)元素的折半查找84二叉搜索樹的折半查找二叉搜索樹的折半查找85二叉搜索樹的抽象數(shù)據(jù)類型二叉搜索樹的抽象數(shù)據(jù)類型&二叉搜索樹抽象數(shù)據(jù)類型與廣義線性表抽象數(shù)據(jù)二叉搜索樹抽象數(shù)據(jù)類型與廣義線性表抽象數(shù)據(jù)類型定義的操作相同類型定義的操作相同 BSTBST比廣義線性表更為常見比廣義線性表更為常見比廣義線性表更為常見比廣義線性表更為常見 BSTBST的搜索效率比廣義線性表高，廣義線性表中只能使的搜索效率比廣義線性表高，廣義線性表中只能使的搜索效率比廣義線性表高，廣義線性表中只能使的搜索效率比廣義線性表高，廣義線性表中只能使用順序查找，用順序查找，用順序查找，用順序查找，BSTBST可以使用折半查找可以使用折半查找可以使用折半查找可以使用折半查找86二叉搜索樹的實現(xiàn)二叉搜索樹的實現(xiàn)&二叉搜索樹可通過數(shù)組或鏈表實現(xiàn)，鏈表實現(xiàn)更二叉搜索樹可通過數(shù)組或鏈表實現(xiàn)，鏈表實現(xiàn)更常見并高效常見并高效&鏈表部分：節(jié)點包含兩個指針域鏈表部分：節(jié)點包含兩個指針域 左指針：指向左子樹左指針：指向左子樹左指針：指向左子樹左指針：指向左子樹 右指針：指向右子樹右指針：指向右子樹右指針：指向右子樹右指針：指向右子樹&輔助記錄：含輔助記錄：含2 2個域個域 1 1個域記錄節(jié)點數(shù)量（計數(shù)）個域記錄節(jié)點數(shù)量（計數(shù)）個域記錄節(jié)點數(shù)量（計數(shù)）個域記錄節(jié)點數(shù)量（計數(shù)）1 1個域為指向根的指針個域為指向根的指針個域為指向根的指針個域為指向根的指針87二叉搜索樹的實現(xiàn)二叉搜索樹的實現(xiàn)88本章內(nèi)容安排本章內(nèi)容安排&背景背景&棧棧&隊列隊列&廣義線性表廣義線性表&樹樹&二叉樹二叉樹&二叉搜索樹二叉搜索樹&圖圖89圖圖&圖由一組節(jié)點（稱為圖由一組節(jié)點（稱為頂點頂點）和一組頂點間的連線）和一組頂點間的連線（邊或弧邊或?。?gòu)成的一種抽象數(shù)據(jù)類型。）構(gòu)成的一種抽象數(shù)據(jù)類型。&樹定義成層次結(jié)構(gòu)樹定義成層次結(jié)構(gòu)，節(jié)點最多只能有，節(jié)點最多只能有1 1個雙親，而個雙親，而圖中每個節(jié)點可以有多個雙親。圖中每個節(jié)點可以有多個雙親。90圖的示例圖的示例&有向圖和無向圖有向圖和無向圖 有向圖：連接頂點的邊具有方向（用箭頭表示）有向圖：連接頂點的邊具有方向（用箭頭表示）有向圖：連接頂點的邊具有方向（用箭頭表示）有向圖：連接頂點的邊具有方向（用箭頭表示）無向圖：邊沒有方向無向圖：邊沒有方向無向圖：邊沒有方向無向圖：邊沒有方向91圖的應(yīng)用圖的應(yīng)用&城市交通問題城市交通問題 可以使用無向圖表示城市及連接它們的道路可以使用無向圖表示城市及連接它們的道路可以使用無向圖表示城市及連接它們的道路可以使用無向圖表示城市及連接它們的道路 城市是城市是城市是城市是頂點頂點頂點頂點，無向的，無向的，無向的，無向的邊邊邊邊是連接城市的道路是連接城市的道路是連接城市的道路是連接城市的道路 若要顯示城市之間的距離，可以使用加權(quán)圖，為每條邊若要顯示城市之間的距離，可以使用加權(quán)圖，為每條邊若要顯示城市之間的距離，可以使用加權(quán)圖，為每條邊若要顯示城市之間的距離，可以使用加權(quán)圖，為每條邊賦予權(quán)重，表示城市之間的距離賦予權(quán)重，表示城市之間的距離賦予權(quán)重，表示城市之間的距離賦予權(quán)重，表示城市之間的距離92圖的應(yīng)用圖的應(yīng)用&計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò) 頂點代表節(jié)點或集線器，邊代表路由頂點代表節(jié)點或集線器，邊代表路由頂點代表節(jié)點或集線器，邊代表路由頂點代表節(jié)點或集線器，邊代表路由 每條邊有一個權(quán)重，表示從一個集線器到相鄰集線器的每條邊有一個權(quán)重，表示從一個集線器到相鄰集線器的每條邊有一個權(quán)重，表示從一個集線器到相鄰集線器的每條邊有一個權(quán)重，表示從一個集線器到相鄰集線器的代價代價代價代價 路由器通過圖的算法，找到它與最終目的地的最短路徑路由器通過圖的算法，找到它與最終目的地的最短路徑路由器通過圖的算法，找到它與最終目的地的最短路徑路由器通過圖的算法，找到它與最終目的地的最短路徑93