數(shù)據(jù)結(jié)構(gòu)和算法講義

1、關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法講義第一張，PPT共一百二十三頁，創(chuàng)作于2022年6月1. 基本數(shù)據(jù)結(jié)構(gòu)與算法第二張，PPT共一百二十三頁，創(chuàng)作于2022年6月1.1 算法1.1.1 算法(algorithm)基本概念對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。它是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法具有有窮性、確定性、可行性、擁有足夠的情報(輸入和輸出) 等個重要特性。第三張，PPT共一百二十三頁，創(chuàng)作于2022年6月1.1.2 算法的基本要素 1、對數(shù)據(jù)對象的運算和操作算術(shù)運算邏輯運算關(guān)系運算數(shù)據(jù)傳輸

2、2、算法的控制結(jié)構(gòu)算法中各操作之間的執(zhí)行順序描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語言等一個算法一般可以用順序、選擇、循環(huán)三種基本機構(gòu)組合而成。第四張，PPT共一百二十三頁，創(chuàng)作于2022年6月1.2 算法復(fù)雜度1.2.1 時間復(fù)雜度 依據(jù)算法編制的程序在計算機上運行時所消耗的時間來度量。通常有事后統(tǒng)計法和事前分析估算法。 一個算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)）和原操作構(gòu)成的，算法時間取決于兩者的綜合效果。 算法中基本操作重復(fù)執(zhí)行次數(shù)n和算法執(zhí)行時間同步增長，稱作算法的時間復(fù)雜度。第五張，PPT共一百二十三頁，創(chuàng)作于2022年6月1.2.2 算法的空間復(fù)雜度 一般是指執(zhí)

3、行這個算法所需要的內(nèi)存空間一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間 一個上機執(zhí)行的程序除了需要存儲空間來寄存本身所用指令、常數(shù)、變量和輸入數(shù)據(jù)外，也需要一些對數(shù)據(jù)進行操作的工作單元和存儲一些為實現(xiàn)計算所需信息的輔助空間。第六張，PPT共一百二十三頁，創(chuàng)作于2022年6月例題講解第七張，PPT共一百二十三頁，創(chuàng)作于2022年6月 算法的時間復(fù)雜度是指A) 執(zhí)行算法程序所需要的時間 B) 算法程序的長度C) 算法執(zhí)行過程中所需要的基本運算次數(shù) D) 算法程序中的指令條數(shù)算法的基本特征是可行性、確定性、 【1】 和擁有足夠的情報

4、。算法的空間復(fù)雜度是指 A) 算法程序的長度 B) 算法程序中的指令條數(shù) C) 算法程序所占的存儲空間 D) 執(zhí)行過程中所需要的存儲空間在計算機中，算法是指 A) 加工方法B) 解題方案的準確而完整的描述 C) 排序方法D) 查詢方法第八張，PPT共一百二十三頁，創(chuàng)作于2022年6月算法分析的目的是 A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 找出算法中輸入和輸出之間的關(guān)系 C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改進算法的工作量大小和實現(xiàn)算法所需的存儲單元多少分別稱為算法的 【1】 。第九張，PPT共一百二十三頁，創(chuàng)作于2022年6月1.2 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)

5、構(gòu)數(shù)據(jù)結(jié)構(gòu)的圖形表示線性結(jié)構(gòu)與非線性結(jié)構(gòu)第十張，PPT共一百二十三頁，創(chuàng)作于2022年6月特點： l每個學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號順序依次排列構(gòu)成一張表格； l表中每個學(xué)生的信息依據(jù)學(xué)號的大小存在著一種前后關(guān)系，這就是我們所說的線性結(jié)構(gòu)； l對它的操作通常是插入某個學(xué)生的信息，刪除某個學(xué)生的信息，更新某個學(xué)生的信息，按條件檢索某個學(xué)生的信息等等。 應(yīng)用舉例2輸出n個對象的全排列 輸出n個對象的全排列可以使用下圖1-1所示的形式描述。第十一張，PPT共一百二十三頁，創(chuàng)作于2022年6月圖 1-1 3個對象的全排列過程第十二張，PPT共一百二十三頁，創(chuàng)作于2022年6月特點： l在求

6、解過程中，所處理的數(shù)據(jù)之間具有層次關(guān)系，這是我們所說的樹形結(jié)構(gòu)； l對它的操作有：建立樹形結(jié)構(gòu)，輸出最低層結(jié)點內(nèi)容等等。 應(yīng)用舉例3制定教學(xué)計劃 在制定教學(xué)計劃時，需要考慮各門課程的開設(shè)順序。有些課程需要先導(dǎo)課程，有些課程則不需要，而有些課程又是其他課程的先導(dǎo)課程。比如，計算機專業(yè)課程的開設(shè)情況如下表1-2所示：第十三張，PPT共一百二十三頁，創(chuàng)作于2022年6月第十四張，PPT共一百二十三頁，創(chuàng)作于2022年6月課程先后關(guān)系的圖形描形式：c1c9c4c2c12c10c11c5c3c6c7c8圖 1-2 計算機專業(yè)必修課程開設(shè)先后關(guān)系第十五張，PPT共一百二十三頁，創(chuàng)作于2022年6月特點 l

7、課程之間的先后關(guān)系用圖結(jié)構(gòu)描述； l通過實施創(chuàng)建圖結(jié)構(gòu)，按要求將圖結(jié)構(gòu)中的頂點進行線性排序。結(jié)論：數(shù)據(jù)結(jié)構(gòu)主要研究以下三個方面的問題：數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)對各種數(shù)據(jù)結(jié)構(gòu)進行的運算 第十六張，PPT共一百二十三頁，創(chuàng)作于2022年6月 數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學(xué)科。1.2.2 基本概念和術(shù)語第十七張，PPT共一百二十三頁，創(chuàng)作于2022年6月數(shù)據(jù)元素(Data Element) 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體。 有時一個數(shù)據(jù)元素可由若干數(shù)據(jù)項(Data Item)組成。數(shù)據(jù)項是數(shù)據(jù)的最小單位。數(shù)據(jù)元素亦稱節(jié)點或記錄。第十八張，PPT共一百二十三頁，

8、創(chuàng)作于2022年6月數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）有限個數(shù)據(jù)元素的集合有限個節(jié)點間關(guān)系的集合第十九張，PPT共一百二十三頁，創(chuàng)作于2022年6月 1數(shù)據(jù)的邏輯結(jié)構(gòu) 2、數(shù)據(jù)的存儲結(jié)構(gòu) 3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。 A線性結(jié)構(gòu) B非線性結(jié)構(gòu)A 順序存儲 B 鏈式存儲 線性表棧隊樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面 數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）第二十張，PPT共一百二十三頁，創(chuàng)作于2022年6月線性結(jié)構(gòu) A , B , C , ，X ,Y , Z學(xué) 生 成 績 表86胡孝臣986110395劉忠賞9861107100張卓9861109成績姓名學(xué)號線性表結(jié)點間

9、是以線性關(guān)系聯(lián)結(jié)第二十一張，PPT共一百二十三頁，創(chuàng)作于2022年6月元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容Loc(a)=Lo+（i-1)*m順序存儲每個元素所占用的存儲單元個數(shù)第二十二張，PPT共一百二十三頁，創(chuàng)作于2022年6月元素n.元素i.元素2元素1存儲內(nèi)容順序存儲結(jié)構(gòu)常用于線性數(shù)據(jù)結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里。順序存儲結(jié)構(gòu)的三個弱點：1.作插入或刪除操作時，需移動大量元數(shù)。2.長度變化較大時，需按最大空間分配。3.表的容量難以擴充。第二十三張，PPT共一百二十三頁，創(chuàng)作于2022年6月1536元素

10、21400元素11346元素3 元素41345h 鏈式存儲 每個節(jié)點都由兩部分組成：數(shù)據(jù)域和指針域。數(shù)據(jù)域存放元素本身的數(shù)據(jù)，指針域存放指針。數(shù)據(jù)元素之間邏輯上的聯(lián)系由指針來體現(xiàn)。第二十四張，PPT共一百二十三頁，創(chuàng)作于2022年6月1536元素21400元素11346元素3 元素4head 1346 元素3 1536 . . . 1536 元素2 1400 . . . 元素4 1346 1400 元素1 1345 指針 存儲內(nèi)容存儲地址 鏈式存儲 1345第二十五張，PPT共一百二十三頁，創(chuàng)作于2022年6月1536元素21400元素11346元素3 元素41345h 鏈式存儲 1.比順序存

11、儲結(jié)構(gòu)的存儲密度小 (每個節(jié)點都由數(shù)據(jù)域和指針愈組成)。2.邏輯上相鄰的節(jié)點物理上不必相鄰。3.插入、刪除靈活 (不必移動節(jié)點，只要改變節(jié)點中的指針)。鏈接存儲結(jié)構(gòu)特點：第二十六張，PPT共一百二十三頁，創(chuàng)作于2022年6月 線性結(jié)構(gòu)和非線性結(jié)構(gòu)如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件：有且只有一個根結(jié)點；每一個結(jié)點最多有一個前件，也最多有一個后件則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)（線性表）。如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。第二十七張，PPT共一百二十三頁，創(chuàng)作于2022年6月例題講解第二十八張，PPT共一百二十三頁，創(chuàng)作于2022年6月鏈表不具有的特點是A) 不必事先估計存儲空間 B)

12、 可隨機訪問任一元素C) 插入刪除不需要移動元素D) 所需空間與線性表長度成正比數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于 【1】 。 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的 A) 存儲結(jié)構(gòu)B) 物理結(jié)構(gòu) C) 邏輯結(jié)構(gòu)D) 物理和存儲結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和 【1】 兩大類。 第二十九張，PPT共一百二十三頁，創(chuàng)作于2022年6月順序存儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置 【2】 的存儲單元中。 數(shù)據(jù)處理的最小單位是 A) 數(shù)據(jù) B) 數(shù)據(jù)元素 C) 數(shù)據(jù)項D) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進行的運算，以及 A) 數(shù)據(jù)的存儲結(jié)

13、構(gòu) B) 計算方法 C) 數(shù)據(jù)映象 D) 邏輯存儲線性表的順序存儲結(jié)構(gòu)和線性表的鏈式存儲結(jié)構(gòu)分別是 A) 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) B) 隨機存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) C) 隨機存取的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu) D) 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu) 第三十張，PPT共一百二十三頁，創(chuàng)作于2022年6月根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成 A) 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B) 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D) 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 【2】 以及對數(shù)據(jù)的操作運算。數(shù)據(jù)的基本單位是 【

14、5】 。第三十一張，PPT共一百二十三頁，創(chuàng)作于2022年6月下列敘述中，錯誤的是 A) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān) B) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān) C) 數(shù)據(jù)的存儲結(jié)構(gòu)在計算機中所占的空間不一定是連續(xù)的 D) 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)是指A）數(shù)據(jù)所占的存儲空間B）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示C）數(shù)據(jù)在計算機中的順序存儲方式D）存儲在外存中的數(shù)據(jù) 第三十二張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.3 線性表2.3.1 線性表的定義 線性表是n個元素的有限序列，它們之間的關(guān)系可以排成一個線性序列： a1，a2， ，ai， ，an其中n稱作

15、表的長度，當(dāng)n=0時，稱作空表。第三十三張，PPT共一百二十三頁，創(chuàng)作于2022年6月線性表的特點：1.線性表中所有元素的性質(zhì)相同。2.除第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素有且僅有一個前驅(qū)和一個后繼。第一個數(shù)據(jù)元素?zé)o前驅(qū)，最后一個數(shù)據(jù)元素?zé)o后繼。3.數(shù)據(jù)元素在表中的位置只取決于它自身的序號。在線性表上常用的運算有：初始化、求長度、取元素、修改、前插、刪除、檢索、排序。第三十四張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.3.2 線性表的順序存儲結(jié)構(gòu)及其插入與刪除操作特點： 1、線性表中數(shù)據(jù)元素類型一致，只有數(shù)據(jù)域，存儲空間利用率高。 2、所有元素所占的存儲空間是連續(xù)的 3、各數(shù)據(jù)元

16、素在存儲空間中是按邏輯順序依次存放的 4. 做插入、刪除時需移動大量元素。 5. 空間估計不明時，按最大空間分配。第三十五張，PPT共一百二十三頁，創(chuàng)作于2022年6月元素an.元素ai.元素a2元素a1bb+mb+(i-1)*m b+(maxlen-1)*m存儲地址內(nèi)存狀態(tài)Loc(元素i)=b +（i-1)*m順序存儲結(jié)構(gòu)示意圖(順序表)：首地址起始地址基地址每個元素所占用的存儲單元個數(shù)第三十六張，PPT共一百二十三頁，創(chuàng)作于2022年6月元素a1元素a2.元素ai+1. 01i線性表的順序存儲結(jié)構(gòu)可用VB語言中的一維數(shù)組來描述.Dim VM As integer; /*V是數(shù)組的名字，M是

17、數(shù)組大小，假設(shè)數(shù)組中的元素是整型類型*/第i個元素的ai存儲地址：Loc(ai)=Loc(a1)+(i-1)*mVVViVm-1第三十七張，PPT共一百二十三頁，創(chuàng)作于2022年6月.a2a1an.ai+1ai01i-1in-1 1- 1插入運算ai-1.a2a1alength ai+1ai x ai-1. a2 a1 ai ai+1 alength alength ai+1 ai x第三十八張，PPT共一百二十三頁，創(chuàng)作于2022年6月 插入算法的分析 假設(shè)線性表中含有n個數(shù)據(jù)元素，在進行插入操作時，若假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數(shù)為：第三十九張，PPT共一百

18、二十三頁，創(chuàng)作于2022年6月 刪除算法的分析 在進行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數(shù)為： 分析結(jié)論 順序存儲結(jié)構(gòu)表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對其做插入或刪除操作時，這一點需要值得考慮。第四十張，PPT共一百二十三頁，創(chuàng)作于2022年6月例題講解第四十一張，PPT共一百二十三頁，創(chuàng)作于2022年6月順序存儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置 【2】 的存儲單元中。長度為n的順序存儲線性表中，當(dāng)在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為 【1】 。第四十

19、二張，PPT共一百二十三頁，創(chuàng)作于2022年6月線性表L=(a1,a2,a3,ai，an)，下列說法正確的是 A) 每個元素都有一個直接前件和直接后件 B) 線性表中至少要有一個元素 C) 表中諸元素的排列順序必須是由小到大或由大到小 D) 除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件線性表的順序存儲結(jié)構(gòu)和線性表的鏈式存儲結(jié)構(gòu)分別是 A) 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) B) 隨機存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) C) 隨機存取的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu) D) 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu) 第四十三張，PPT共一百二十三頁，創(chuàng)作于202

20、2年6月根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成 A) 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B) 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D) 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)當(dāng)線性表采用順序存儲結(jié)構(gòu)實現(xiàn)存儲時，其主要特點是 【1】 。線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址 A) 必須是連續(xù)的 B) 部分地址必須是連續(xù)的 C) 一定是不連續(xù)的 D) 連續(xù)不連續(xù)都可以第四十四張，PPT共一百二十三頁，創(chuàng)作于2022年6月下列敘述中，錯誤的是 A) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān) B) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān) C) 數(shù)據(jù)的存儲結(jié)構(gòu)在計算機中所占的空間不

21、一定是連續(xù)的 D) 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu) 第四十五張，PPT共一百二十三頁，創(chuàng)作于2022年6月數(shù)據(jù)結(jié)構(gòu)定義：是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。包含三個方面： 1 邏輯結(jié)構(gòu) 2 存儲結(jié)構(gòu) 3 各類操作第四十六張，PPT共一百二十三頁，創(chuàng)作于2022年6月數(shù)據(jù)的邏輯結(jié)構(gòu) （1）表示數(shù)據(jù)元素的信息 （2）表示數(shù)據(jù)元素之間的前后關(guān)系它不關(guān)心計算機如何去實現(xiàn)，與具體計算機實現(xiàn)無關(guān)。數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)在計算機中的標識（映像），稱為數(shù)據(jù)的物理結(jié)構(gòu)，或稱存儲結(jié)構(gòu)。它所研究的是數(shù)據(jù)結(jié)構(gòu)在計算機中的實現(xiàn)方法。第四十七張，PPT共一百二十三頁，創(chuàng)作于2022年6月數(shù)據(jù)的存儲結(jié)

22、構(gòu) 包括數(shù)據(jù)結(jié)構(gòu)中元素的表示及元素間關(guān)系的表示。數(shù)據(jù)結(jié)構(gòu)的存儲方式有： 順序存儲方法、 鏈式存儲方法、 索引存儲方法、 散列存儲方法。第四十八張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.4 棧和隊列2.4.1 棧和隊列的定義 棧和隊列是兩種特殊的線性表，它們是運算時要受到某些限制的線性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。第四十九張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.4.1.1棧的定義棧：限定只能在表的一端進行插入和刪除的特殊的線性表,此種結(jié)構(gòu)稱為后進先出設(shè)棧s=（a1，a2，. . . ,ai，. . . ，an），其中a1是棧底元素， an是棧頂元素。棧頂（top)：允許插入和刪

23、除的一端； 約定top始終指向新數(shù)據(jù)元素將存放的位置。棧底（bottom):不允許插入和刪除的一端。 a1 a2 . an進棧出棧棧頂棧底第五十張，PPT共一百二十三頁，創(chuàng)作于2022年6月隊列的主要運算（1）設(shè)置一個空隊列；（2）插入一個新的隊尾元素，稱為進隊；（3）刪除隊頭元素，稱為出隊；（4）讀取隊頭元素；2.4.1.2 隊列的定義定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進行插入，在表的另一端進行刪除的線性表 。此種結(jié)構(gòu)稱為先進先出（FIFO）表。 a1 , a2 , a3 , a4 , an-1 , an 隊 列 示 意 圖隊頭隊尾第五十一張，PPT共一百二十三頁，創(chuàng)作于2022年

24、6月2.4.2 棧的順序存儲結(jié)構(gòu)及其基本運算 a2 a1 a1 a2 top 用順序存儲結(jié)構(gòu)表示的棧。 順序棧用一組連續(xù)的存儲單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組表示，設(shè)置一個簡單變量top指示棧頂位置，稱為棧頂指針，它始終指向待插入元素的位置?；具\算：壓（進）棧：PUSH出棧：POP第五十二張，PPT共一百二十三頁，創(chuàng)作于2022年6月 3 2 1 0 (a)rear=front=-1(隊空） e3 e4 (c)e1,e2出隊，e4入隊 隊 滿rear =4front e1 e2 e3 (b)rearfront(b)e1,e2,e3入隊隊空時， 令rear=front=-1，當(dāng)有

25、新元素入隊時，尾指針加1，當(dāng)有元素出隊時，頭指針加1。故在非空隊列中，頭指針始終指向隊頭元素前一個位置，而尾指針始終指向隊尾元素的位置2.4.3 隊列的順序存儲結(jié)構(gòu)及其基本運算第五十三張，PPT共一百二十三頁，創(chuàng)作于2022年6月例題講解第五十四張，PPT共一百二十三頁，創(chuàng)作于2022年6月棧和隊列的共同特點是 A)都是先進先出 B) 都是先進后出 C) 只允許在端點處插入和刪除元素 D) 沒有共同點如果進棧序列為e1,e2,e3,e4，則可能的出棧序列是 A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2D) 任意順序一些重要的程序語言(如C語言和Pas

26、cal語言) 允許過程的遞歸調(diào)用。而實現(xiàn)遞歸調(diào)用中的存儲分配通常用 A) 棧B) 堆 C) 數(shù)組 D) 鏈表第五十五張，PPT共一百二十三頁，創(chuàng)作于2022年6月棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是 A) ABCED B) DCBEA C) DBCEA D) CDABE 棧通常采用的兩種存儲結(jié)構(gòu)是 A) 線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)B) 散列方式和索引方式 C) 鏈表存儲結(jié)構(gòu)和數(shù)組 D) 線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)棧和隊列通常采用的存儲結(jié)構(gòu)是 【1】 。下列數(shù)據(jù)結(jié)構(gòu)中，按先進后出原則組織數(shù)據(jù)的是 A) 線性鏈表 B) 棧 C) 循環(huán)鏈表

27、 D) 順序表第五十六張，PPT共一百二十三頁，創(chuàng)作于2022年6月當(dāng)循環(huán)隊列非空且隊尾指針等于隊頭指針時，說明循環(huán)隊列已滿，不能進行入隊運算。這種情況稱為 【2】 上溢。 由兩個棧共享一個存儲空間的好處是 A) 減少存取時間，降低下溢發(fā)生的機率 B) 節(jié)省存儲空間，降低上溢發(fā)生的機率 C) 減少存取時間，降低上溢發(fā)生的機率 D) 節(jié)省存儲空間，降低下溢發(fā)生的機率下列關(guān)于棧的敘述中正確的是）在棧中只能插入數(shù)據(jù) B）在棧中只能刪除數(shù)據(jù)C）棧是先進先出的線性表 D）棧是后進先出的線性表下列關(guān)于隊列的敘述中正確的是）在隊列中只能插入數(shù)據(jù) B）在隊列中只能刪除數(shù)據(jù)C）隊列是先進先出的線性表 D）隊列是

28、后進先出的線性表第五十七張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.5 鏈表線性單鏈表雙向鏈表循環(huán)鏈表結(jié)構(gòu)及其基本運算第五十八張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.5.1 線性表的鏈式存儲結(jié)構(gòu) 將線性表的元素放到一個具有頭指針的鏈表中，鏈表中每個結(jié)點包含數(shù)據(jù)域和指針域。 數(shù)據(jù)域存放數(shù)據(jù)，指針域存放后繼結(jié)點的地址，最后一個結(jié)點的指針域為空。邏輯上相鄰的數(shù)據(jù)元素在內(nèi)存中的物理存儲空間不一定相鄰。第五十九張，PPT共一百二十三頁，創(chuàng)作于2022年6月上圖的線性表為ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG第六十張，PPT共一百二十三頁，創(chuàng)作于2022年6

29、月線性鏈表表示法:第六十一張，PPT共一百二十三頁，創(chuàng)作于2022年6月鏈式存儲結(jié)構(gòu)的特點 插入、刪除靈活方便，不需要移動結(jié)點，只要改變結(jié)點中指針域的值即可。 適合于線性表是動態(tài)變化的,不進行頻繁查找操作、但經(jīng)常進行插入刪除時使用。 鏈表的查找只能從頭指針開始順序查找。 第六十二張，PPT共一百二十三頁，創(chuàng)作于2022年6月a1a2ana3L.線性表的鏈式存儲結(jié)構(gòu)可用C語言中的“結(jié)構(gòu)指針”來描述帶頭結(jié)點的線性鏈表datanexttypedef struct LNode int data; Struct LNode *next; JD;第六十三張，PPT共一百二十三頁，創(chuàng)作于2022年6月bab

30、axPP單鏈表的插入運算S在P所指向的結(jié)點之后插入新的結(jié)點第六十四張，PPT共一百二十三頁，創(chuàng)作于2022年6月babaxanaia1a2PPai-1xL單鏈表的插入運算S第六十五張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.5.2 循環(huán)鏈表: 首尾相接的鏈表。 將最后一個結(jié)點的空指針改為指向頭結(jié)點，從任一結(jié)點出發(fā)均可找到其它結(jié)點。a1a2ana3L.帶頭結(jié)點的單鏈表a1a2ana3L.循環(huán)單鏈表第六十六張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.5.3 雙向鏈表 在每個結(jié)點中設(shè)置兩個指針，一個指向后繼，一個指向前驅(qū)?？芍苯哟_定一個結(jié)點的前驅(qū)和后繼結(jié)點?？商岣咝?。datanextb

31、efore第六十七張，PPT共一百二十三頁，創(chuàng)作于2022年6月線性表的應(yīng)用：應(yīng)用最廣的數(shù)據(jù)結(jié)構(gòu)。高級語言中的數(shù)組；計算機的文件系統(tǒng)；計算機的目錄系統(tǒng)；電話號碼查詢系統(tǒng)（可采用順序表或單鏈表結(jié)構(gòu)）；各種事務(wù)處理（各種表格均采用順序表和線性鏈表結(jié)構(gòu)）第六十八張，PPT共一百二十三頁，創(chuàng)作于2022年6月例題講解第六十九張，PPT共一百二十三頁，創(chuàng)作于2022年6月鏈表不具有的特點是A) 不必事先估計存儲空間 B) 可隨機訪問任一元素C) 插入刪除不需要移動元素D) 所需空間與線性表長度成正比用鏈表表示線性表的優(yōu)點是 A) 便于隨機存取 B) 花費的存儲空間較順序存儲少 C) 便于插入和刪除操作

32、D) 數(shù)據(jù)元素的物理順序與邏輯順序相同長度為n的順序存儲線性表中，當(dāng)在任何位置上插入一個元素概率都相等時，插入一個元素所需移動元素的平均個數(shù)為 【1】 。第七十張，PPT共一百二十三頁，創(chuàng)作于2022年6月線性表L=(a1,a2,a3,ai，an)，下列說法正確的是A) 每個元素都有一個直接前件和直接后件B) 線性表中至少要有一個元素C) 表中諸元素的排列順序必須是由小到大或由大到小D) 除第一個元素和最后一個元素外，其余每個元素都有一個且只有一個直接前件和直接后件 在單鏈表中，增加頭結(jié)點的目的是 A) 方便運算的實現(xiàn) B) 使單鏈表至少有一個結(jié)點 C) 標識表結(jié)點中首結(jié)點的位置 D) 說明單

33、鏈表是線性表的鏈式存儲實現(xiàn)第七十一張，PPT共一百二十三頁，創(chuàng)作于2022年6月非空的循環(huán)單鏈表head的尾結(jié)點(由p所指向) ，滿足 A) p-next=NULLB) p=NULL C) p-next=head D) p=head 循環(huán)鏈表的主要優(yōu)點是 A) 不再需要頭指針了 B) 從表中任一結(jié)點出發(fā)都能訪問到整個鏈表 C) 在進行插入、刪除運算時，能更好的保證鏈表不斷開 D) 已知某個結(jié)點的位置后，能夠容易的找到它的直接前件第七十二張，PPT共一百二十三頁，創(chuàng)作于2022年6月線性表的順序存儲結(jié)構(gòu)和線性表的鏈式存儲結(jié)構(gòu)分別是 A) 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) B) 隨機存取的存

34、儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) C) 隨機存取的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu) D) 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu) 當(dāng)循環(huán)隊列非空且隊尾指針等于隊頭指針時，說明循環(huán)隊列已滿，不能進行入隊運算。這種情況稱為 【2】 。用鏈表表示線性表的突出優(yōu)點是 【1】 。 第七十三張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.6 樹樹的基本概念二叉樹的定義及其存儲結(jié)構(gòu)二叉樹的前序、中序和后序遍歷第七十四張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.6.1 樹的定義 由一個或多個結(jié)點組成的有限集合。僅有一個根結(jié)點，結(jié)點間有明顯的層次結(jié)構(gòu)關(guān)系。 A C G T2D H I T3J M B E L KT

35、1 F現(xiàn)實世界中，能用樹的結(jié)構(gòu)表示的例子：學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。第七十五張，PPT共一百二十三頁，創(chuàng)作于2022年6月介紹幾個概念：結(jié)點（Node）：樹中的元素，包含數(shù)據(jù)項及若干指向其子樹的分支。結(jié)點的度（Degree）：結(jié)點擁有的子樹數(shù)。結(jié)點的層次：從根結(jié)點開始算起，根為第一層。葉子（Leaf）：度為零的結(jié)點，也稱端結(jié)點。孩子（Child）：結(jié)點子樹的根稱為該結(jié)點的孩子結(jié)點。兄弟（Sibling）：同一雙親的孩子。雙親（Parent）：孩子結(jié)點的上層結(jié)點，稱為這些結(jié)點的雙親。深度（Depth)： 樹中結(jié)點的最大層次數(shù)。森林（Forest）：M棵互不相交的樹的集合

36、。 A C G T2D H I T3J M B E L KT1 F第七十六張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.6.2 二叉樹 （Binary Tree）1 、二叉樹的定義及其性質(zhì) (1) 二叉樹的定義二叉樹的五種基本形態(tài)二叉樹一種特殊的樹型結(jié)構(gòu)，特點是樹中每個結(jié)點只有兩棵子樹，且子樹有左右之分，次序不能顛倒。 空二叉樹 僅有根結(jié)點 右子樹為空 左子樹為空左右子樹均非空因為樹的每個結(jié)點的度不同，存儲困難，使對樹的處理算法很復(fù)雜。所以引出二叉樹的討論。第七十七張，PPT共一百二十三頁，創(chuàng)作于2022年6月 二叉數(shù)是n(n0)個結(jié)點的有限集合。它或為空數(shù)(n=0),或由一個根結(jié)點和兩棵

37、分別稱為根的左子樹和右子樹的互不相交的二叉數(shù)組成。 特別要注意：二叉數(shù)不是樹的特殊情況。aabb兩棵不同的二叉數(shù)第七十八張，PPT共一百二十三頁，創(chuàng)作于2022年6月A、 二叉樹的第i層上至多有2 i-1（i 1）個結(jié)點。(2) 二叉樹的基本性質(zhì)423167891011121314155第三層上(i=3)，有23-1=4個節(jié)點。第四層上(i=4)，有24-1=8個節(jié)點。第七十九張，PPT共一百二十三頁，創(chuàng)作于2022年6月A、 二叉樹的第i層上至多有2 i-1（i 1）個結(jié)點。 B、 深度為h的二叉樹中至多含有2h-1個結(jié)點。(2) 二叉樹的基本性質(zhì)423167891011121314155此

38、樹的深度h=4，共有24-1=15個節(jié)點。第八十張，PPT共一百二十三頁，創(chuàng)作于2022年6月A、 二叉樹的第i層上至多有2 i-1（i 1）個結(jié)點。B、 深度為h的二叉樹中至多含有2h-1個結(jié)點。C、 若在任意一棵二叉樹中，有n0個葉子結(jié)點， 有n2個度為2的結(jié)點，則：n0=n2+1(2) 二叉樹的基本性質(zhì)423167891011121314155n0=8n2=7第八十一張，PPT共一百二十三頁，創(chuàng)作于2022年6月（3）滿二叉樹423167891011121314155特點：每一層上都含有最大結(jié)點數(shù)。第八十二張，PPT共一百二十三頁，創(chuàng)作于2022年6月4231678910 11125 非

39、完全二叉樹（4）完全二叉樹4231678910 11125 完全二叉樹特點：除最后一層外，每一層都取最大結(jié)點數(shù)，最后一層結(jié)點都集中在該層最左邊的若干位置。第八十三張，PPT共一百二十三頁，創(chuàng)作于2022年6月（5）樹與二叉樹的區(qū)別A樹的結(jié)點個數(shù)至少為1，而二叉樹的結(jié)點個數(shù)可以為0。B樹中結(jié)點的最大度數(shù)沒有限制，二叉樹結(jié)點最大度數(shù)為2。C樹的結(jié)點無左、右之分，二叉樹的結(jié)點子樹有明確的左、右之分。 樹 二叉樹第八十四張，PPT共一百二十三頁，創(chuàng)作于2022年6月2、二叉樹的存儲結(jié)構(gòu) (2) 鏈式存儲結(jié)構(gòu)T16若父結(jié)點在數(shù)組中i下標處，其左孩子在2*i處，右孩子在2*i+1處。11 A B c F

40、E D 1 2 4 8 910 5 6 3 712131415(1) 順序存儲結(jié)構(gòu)(1) 順序存儲結(jié)構(gòu)2h-1=24-1 = 15用一組連續(xù)的存儲單元存放二叉樹的數(shù)據(jù)元素。結(jié)點在數(shù)組中的相對位置蘊含著結(jié)點之間的關(guān)系。0000FE000DC0BA15141312111098765432100一般二叉樹必須按完全二叉樹的形式存儲，將造成存儲的浪費。第八十五張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.6.3 二叉樹的遍歷 查找某個結(jié)點，或?qū)Χ鏄渲腥拷Y(jié)點進行某種處理，就需要遍歷。（1）遍歷定義及遍歷算法 遍歷是指按某條搜索路線尋訪樹中每個結(jié)點，且每個結(jié)點只被訪問一次。 按先左后右的原則，一般

41、使用三種遍歷：先序遍歷(D L R): 訪問根結(jié)點，按先序遍歷左子樹，按先序遍歷右子樹。中序遍歷(L D R): 按中序遍歷左子樹，訪問根結(jié)點，按中序遍歷右子樹。后序遍歷(L R D): 按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點。 二叉樹為空時，執(zhí)行空操作，即空二叉樹已遍歷完。第八十六張，PPT共一百二十三頁，創(chuàng)作于2022年6月 （2）遍歷算法先序遍歷：D L R中序遍歷：L D R后序遍歷：L R DADBCT1T2T3D L RAD L RD L RBDCD L R以先序遍歷D L R為例演示遍歷過程 ABDCBDAC DBCA第八十七張，PPT共一百二十三頁，創(chuàng)作于2022年6月

42、例題講解第八十八張，PPT共一百二十三頁，創(chuàng)作于2022年6月已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是 A) acbed B) decab C) deabc D) cedba 已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為 A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHG樹是結(jié)點的集合，它的根結(jié)點數(shù)目是 A) 有且只有1B) 1或多于1 C) 0或1D) 至少2第八十九張，PPT共一百二十三頁，創(chuàng)作于2022年6月在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為 A)

43、 32B) 31 C) 16 D) 15 若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結(jié)點訪問順序是 A) bdgcefha B) gdbecfha C) bdgaechfD) gdbehfca在樹結(jié)構(gòu)中，樹根結(jié)點沒有 【1】 。下列敘述中正確的是 A) 線性表是線性結(jié)構(gòu)B) 棧與隊列是非線性結(jié)構(gòu) C) 線性鏈表是非線性結(jié)構(gòu)D) 二叉樹是線性結(jié)構(gòu)第九十張，PPT共一百二十三頁，創(chuàng)作于2022年6月具有3個結(jié)點的二叉樹有 A) 2種形態(tài) B) 4種形態(tài) C) 7種形態(tài) D) 5種形態(tài) 設(shè)有下列二叉樹： 對此二叉樹前序遍歷的結(jié)果為A) ZBTT

44、CPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT第九十一張，PPT共一百二十三頁，創(chuàng)作于2022年6月設(shè)一棵二叉樹中有3個葉子結(jié)點，有8個度為1的結(jié)點，則該二叉樹中總的結(jié)點數(shù)為 A) 12 B) 13 C) 14D) 15 設(shè)有下列二叉樹：對此二叉樹的中序遍歷的結(jié)果為A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA第九十二張，PPT共一百二十三頁，創(chuàng)作于2022年6月設(shè)樹T的深度為4,其中度為1、2、3、4的結(jié)點個數(shù)分別為4、2、1、1。則T中的葉子結(jié)點數(shù)為A）8 B）7 C）6 D）5設(shè)一棵完全二叉樹共有700個結(jié)點，則該二叉樹中

45、有（ ）個葉子結(jié)點。 在一個容量為15的循環(huán)隊列中，若頭指針front=6，尾指針rear=9，則該循環(huán)隊列中共有（ ）個元素。設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為（ ）。第九十三張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.7 查找和排序順序查找與二分查找算法基本排序算法（交換類排序、選擇類排序、插入類排序）第九十四張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.7.1 查找查找是在一個給定的數(shù)據(jù)結(jié)構(gòu)中，根據(jù)給定的條件查找滿足條件的結(jié)點。不同的數(shù)據(jù)結(jié)構(gòu)采用不同的查找方法。查找的效率直接影響數(shù)據(jù)處理的效率。查找的結(jié)果：查找成功：找到滿足條

46、件的結(jié)點查找失?。赫也坏綕M足條件的結(jié)點。第九十五張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.7.1.1 順序查找（線性查找）查找過程： 對給定的一關(guān)鍵字K，從線性表的一端開始，逐個進行記錄的關(guān)鍵字和K的比較，直到找到關(guān)鍵字等于K的記錄或到達表的另一端?？梢圆捎脧那跋蚝蟛?，也可采用從后向前查的方法。 在平均情況下，大約要與表中一半以上元素進行比較，效率較低。平均查找長度較大。 在下面兩種情況下只能采取順序查找： a. 線性表為無序表（元素排列是無序的）； b. 即使是有序線性表，但采用的是鏈式存儲結(jié)構(gòu)。第九十六張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.7.1.2 折半查找（二分法查

47、找）思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認找不到該記錄為止。前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進行。分三種情況：1）若中間項的值等于x,則說明已查到。2）若x小于中間項的值，則在線性表的前半部分查找；3）若x大于中間項的值，則在線性表的后半部分查找。特點：比順序查找方法效率高。最壞的情況下，需要比較 log2n次。第九十七張，PPT共一百二十三頁，創(chuàng)作于2022年6月查找23和79的過程如下圖：mid=(low+high)/2不進位取整( 08, 14, 23, 37, 46, 55, 68, 79, 91 )( 08, 14, 23, 37, 46, 55,

48、68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhigh=mid-1mid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )low=mid+1highmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid第九十八張，PPT共一百二十三頁，創(chuàng)作于2022年6

49、月2.7.2 排序2.7.2.1 概述1、排序的功能：將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排成一個按關(guān)鍵字有序的序列。2、排序過程的組成步驟： 首先比較兩個關(guān)鍵字的大??； 然后將記錄從一個位置移動到另一個位置。第九十九張，PPT共一百二十三頁，創(chuàng)作于2022年6月排序方法插入排序選擇排序交換排序歸并排序直接插入排序折半插入排序簡單選擇排序堆排序起泡排序快速排序第一百張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.7.2.2 插入排序 直接插入、折半插入1、直接插入排序: 基本思想：從數(shù)組的第2號元素開始，順序從數(shù)組中取出元素，并將該元素插入到其左端已排好序的數(shù)組的適當(dāng)位置上。 需要n(n

50、-1)/2次比較第一百零一張，PPT共一百二十三頁，創(chuàng)作于2022年6月該算法適合于n 較小的情況，時間復(fù)雜度為O(n2).待排元素序列：53 27 36 15 69 42第一次排序： 27 53 36 15 69 42第二次排序： 27 36 53 15 69 42第三次排序： 15 27 36 53 69 42第四次排序： 15 27 36 53 69 42第五次排序： 15 27 36 42 53 69 直接插入排序示例對于有n個數(shù)據(jù)元素的待排序列，插入操作要進行n-1次第一百零二張，PPT共一百二十三頁，創(chuàng)作于2022年6月2、折半插入排序 折半插入排序在尋找插入位置時，不是逐個比較而

51、是利用折半查找的原理尋找插入位置 。待排序元素越多，改進效果越明顯。折半插入排序的條件： 在有序序列中插入一個關(guān)鍵字。第一百零三張，PPT共一百二十三頁，創(chuàng)作于2022年6月例：有6個記錄，前5 個已排序的基礎(chǔ)上，對第6個記錄排序。 15 27 36 53 69 42 low mid high 15 27 36 53 69 42 low high mid 15 27 36 53 69 42 high low 15 27 36 42 53 69 (high36 )( 4253 )第一百零四張，PPT共一百二十三頁，創(chuàng)作于2022年6月 1、簡單選擇排序 思想：首先從1n個元素中選出關(guān)鍵字最小的記

52、錄交換到第一個位置上。然后再從第2 個到第n個元素中選出次小的記錄交換到第二個位置上，依次類推。 時間復(fù)雜度為O(n2)，最壞情況下需要比較 n(n-1)/2次 適用于待排序元素較少的情況。2.7.2.3 選擇排序 簡單選擇排序、堆排序第一百零五張，PPT共一百二十三頁，創(chuàng)作于2022年6月初態(tài)8 3 9 1 6 8 3 9 1 6 8 3 9 1 6 8 3 9 1 6 ijkijkijkijk1 3 9 8 6 互換ijk1 3 9 8 6 ikj1 3 9 8 6 ikj第一趟第二趟1 3 9 8 6 ikj第三趟第一百零六張，PPT共一百二十三頁，創(chuàng)作于2022年6月2堆排序也是一種選

53、擇排序。是具有特定條件的順序存儲的完全二叉樹，其特定條件是：任何一個非葉子結(jié)點的關(guān)鍵字大于等于（或小于等于）子女的關(guān)鍵字的值。 (1) 堆的示例 897624331510112536497856(a):堆頂元素取最大值(b):堆頂元素取最小值(2) 實現(xiàn)堆排序需解決兩個問題： （1） 如何由一個無序序列建成一個堆？ （2） 輸出堆頂元素后，如何將剩余元素調(diào)整成一個新的堆？ 堆排序需要比較的次數(shù)為O(nlog2n)第一百零七張，PPT共一百二十三頁，創(chuàng)作于2022年6月2.7.2.4 交 換 排 序交換排序的特點在于交換。有冒泡和快速排序兩種。 1、冒泡排序（起泡排序）思想：小的浮起，大的沉底。

54、從左端開始比較。第一趟：第1個與第2個比較，大則交換；第2個與第3個比較， 大則交換，關(guān)鍵字最大的記錄交換到最后一個位置上；第二趟：對前n-1個記錄進行同樣的操作，關(guān)鍵字次大的記錄交換 到第n-1個位置上； 依次類推，則完成排序。正序：時間復(fù)雜度為O(n) 逆序：時間復(fù)雜度為O(n2) 適合于數(shù)據(jù)較少的情況。 排序n個記錄的文件最多需要n-1趟冒泡排序。第一百零八張，PPT共一百二十三頁，創(chuàng)作于2022年6月第六趟排序后第五趟排序后第四趟排序后第三趟排序后第二趟排序后第一趟排序后初始關(guān)鍵字思想：小的浮起，大的沉底。4936416511783665364156364165413641561178

55、363641491156492525251149495611111125252525第一百零九張，PPT共一百二十三頁，創(chuàng)作于2022年6月2、快速排序 (對冒泡排序的改進）思想：通過一趟排序?qū)⒋判蛄蟹殖蓛刹糠?，使其中一部分記錄的關(guān)鍵字均比另一部分小，再分別對這兩部分排序，以達到整個序列有序。關(guān)鍵字通常取第一個記錄的值為基準值。做法：附設(shè)兩個指針low和high ，初值分別指向第一個記錄和最后一個記錄，設(shè)關(guān)鍵字為 key ，首先從 high所指位置起向前搜索，找到第一個小于基準值的記錄與基準記錄交換，然后從low 所指位置起向后搜索，找到第一個大于基準值的記錄與基準記錄交換，重復(fù)這兩步直至low=high為止。時間復(fù)雜度：O(log2n) 第一百一十張，PPT共一百二十三頁，創(chuàng)作于2022年6月快速排序過程示意圖：有序序列 6 18 23 52 67key初始序列 23 52 6 67 18lowhigh一次交換 18 52 6 67 23 lowhigh二次交換 18 23 6 67 52high 三次交換 18 6 23 67 52/ 完成一趟排序后分別進行快速排序lowhigh第一百一十一張，PPT共一百二十三頁