基本數(shù)據(jù)結(jié)構(gòu)與算法

1、基本數(shù)據(jù)結(jié)構(gòu)與算法第1頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法本章主要內(nèi)容算法 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容 基本概念和術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu)類型 線性結(jié)構(gòu)和非線性結(jié)構(gòu) 順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ) 線性表 棧和隊(duì)列 線性鏈表 樹(shù)與二叉樹(shù) 查找和排序 圖 第2頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法3.1 算法算法的基本概念 算法：解題方案的準(zhǔn)確而完整的描述。 算法的基本特征：是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，每一個(gè)規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法不等于程序，程序不可能優(yōu)于算法。

2、基本特性 可行性：根據(jù)實(shí)際問(wèn)題設(shè)計(jì)的算法，執(zhí)行得到滿意結(jié)果 確定性：每一步驟必須有明確定義，不允許有多義性。 有窮性：算法必須能在有限的時(shí)間內(nèi)做完。 輸入和輸出：擁有足夠的情報(bào)，方可執(zhí)行。第3頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法3.1 算法算法的基本要素 1.對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作 算術(shù)運(yùn)算：、等 邏輯運(yùn)算：、=、1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為INT(k/2)。 若2kn，則結(jié)點(diǎn)k的左子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)（顯然也沒(méi)有右子結(jié)點(diǎn)）。 若2k+1n，則結(jié)點(diǎn)k的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。二叉樹(shù)的基本性質(zhì)42 3

3、 16 78910 11 12 13 14 15 53.3.6 樹(shù)與二叉樹(shù)例如結(jié)點(diǎn)6，其父結(jié)點(diǎn)為3，左子結(jié)點(diǎn)為12，左子結(jié)點(diǎn)為13第52頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法3.3.6 樹(shù)與二叉樹(shù)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu) 用一組連續(xù)的存儲(chǔ)單元存放二叉樹(shù)的數(shù)據(jù)元素。結(jié)點(diǎn)在數(shù)組中的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。 用數(shù)組存儲(chǔ)時(shí)，若父結(jié)點(diǎn)在數(shù)組中i下標(biāo)處，其左孩子在2*i處，右孩子在2*i+1處。 順序存儲(chǔ)二叉樹(shù)必須按完全二叉樹(shù)的形式存儲(chǔ)，將造成存儲(chǔ)的浪費(fèi)。第53頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，

4、星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu) T1611 A B c F E D 1 2 4 8 910 5 6 3 7121314152h-1=24-1 = 150000FE00 0DC0BA 151413121110987654321003.3.6 樹(shù)與二叉樹(shù)第54頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法3.3.6 樹(shù)與二叉樹(shù)二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 在順序存儲(chǔ)結(jié)構(gòu)中，對(duì)于非完全二叉樹(shù)，需要將空缺的位置用特定的符號(hào)填補(bǔ)，若空缺結(jié)點(diǎn)較多，勢(shì)必造成空間利用率的下降。在這種情況下，就應(yīng)該考慮使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。常見(jiàn)的二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu)如下所

5、示：LchilditemRchildparentAB第55頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法3.3.6 樹(shù)與二叉樹(shù)G H D E F B C A G H D E F B C A BT 二叉樹(shù)的鏈接存儲(chǔ)結(jié)構(gòu) 第56頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法二叉樹(shù)的遍歷 遍歷是指按某條搜索路線尋訪樹(shù)中每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)只被訪問(wèn)一次。 按先左后右的原則，一般使用三種遍歷： 先序遍歷(D L R): 訪問(wèn)根結(jié)點(diǎn)，按先序遍歷左子樹(shù)，按先序遍歷右子樹(shù)。 中序遍歷(L D R): 按中序遍歷左子樹(shù)，

6、訪問(wèn)根結(jié)點(diǎn)，按中序遍歷右子樹(shù)。 后序遍歷(L R D): 按后序遍歷左子樹(shù)，按后序遍歷右子樹(shù)，訪問(wèn)根結(jié)點(diǎn)。 二叉樹(shù)為空時(shí)，執(zhí)行空操作，即空二叉樹(shù)已遍歷完。3.3.6 樹(shù)與二叉樹(shù)第57頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法遍歷算法先序遍歷：D L R 中序遍歷：L D R 后序遍歷：L R DADBCT1 T2 T3 D L RAD L RD L RBDCD L R以先序遍歷D L R為例演示遍歷過(guò)程 ABDCBDAC DBCA3.3.6 樹(shù)與二叉樹(shù)第58頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與

7、算法查找：在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中，根據(jù)給定的條件找到滿足條件的結(jié)點(diǎn)。不同的數(shù)據(jù)結(jié)構(gòu)采用不同的查找方法。查找的效率直接影響數(shù)據(jù)處理的效率。 平均查找長(zhǎng)度：查找過(guò)程中比較的次數(shù) 查找的結(jié)果 查找成功：找到滿足條件的結(jié)點(diǎn) 查找失?。赫也坏綕M足條件的結(jié)點(diǎn)。3.3.7 查找和排序第59頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法順序查找（線性查找） 對(duì)給定的一關(guān)鍵字K，從線性表的一端開(kāi)始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和K的比較，直到找到關(guān)鍵字等于K的記錄或到達(dá)表的另一端。 可以采用從前向后查，也可采用從后向前查的方法。 在平均情況下，大約要與表中一半以上元素進(jìn)行比

8、較，效率較低。平均查找長(zhǎng)度=(n+1)/2。 時(shí)間復(fù)雜度O(n) 在下面兩種情況下只能采取順序查找： 線性表為無(wú)序表（元素排列是無(wú)序的）； 即使是有序線性表，但采用的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3.3.7 查找和排序第60頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法折半查找（二分法查找）思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。 前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。 分三種情況： 若中間項(xiàng)的值等于x,則說(shuō)明已查到。 若x小于中間項(xiàng)的值，則在線性表的前半部分查找； 若x大于中間項(xiàng)的值，則在線性表的后半部分查找。

9、 特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較 log2n次。3.3.7 查找和排序第61頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二折半查找（二分法查找）算法 假設(shè)查找表存放在數(shù)組a的a1an中，且升序，查找關(guān)鍵字值為k。折半查找的主要步驟為： （1）置初始查找范圍：low=1，high=n; （2）求查找范圍中間項(xiàng)：mid=(low+high)/2 （3）將指定的關(guān)鍵字值k與中間項(xiàng)amid.key比較。 若相等，查找成功，找到的數(shù)據(jù)元素為此時(shí)mid 指向的位置； 若小于，查找范圍的低端數(shù)據(jù)元素指針low不變，高端數(shù)據(jù)元素指針high更新為mid-1; 若大于，查找范圍的

10、高端數(shù)據(jù)元素指針high不變，低端數(shù)據(jù)元素指針low更新為mid+1; （4）重復(fù)步驟（2）、（3）直到查找成功或查找范圍空（lowhigh），即查找失敗為止。 （5）如果查找成功，返回找到元素的存放位置，即當(dāng)前的中間項(xiàng)位置指針mid；否則返回查找失敗標(biāo)志。 第62頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二查找23和79的過(guò)程如下圖：9元素mid=(low+high)/2不進(jìn)位取整( 08, 14, 23, 37, 46, 55, 68, 79, 91 )( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23,

11、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第63頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法 排序的功能：將一個(gè)數(shù)據(jù)元

12、素（或記錄）的任意序列，重新排成一個(gè)按關(guān)鍵字有序的序列。 排序過(guò)程的組成步驟 1、首先比較兩個(gè)關(guān)鍵字的大??； 2、然后將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。 3.3.7 查找和排序堆排序起泡排序排序方法插入排序選擇排序交換排序歸并排序直接、折半插入排序希爾排序簡(jiǎn)單選擇排序快速排序第64頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法該算法適合于n 較小的情況，時(shí)間復(fù)雜度為O(n2).待排元素序列：53 27 36 15 69 42 第一次排序： 27 53 36 15 69 42 第二次排序： 27 36 53 15 69 42 第三次排序： 15 27

13、 36 53 69 42 第四次排序： 15 27 36 53 69 42 第五次排序： 15 27 36 42 53 69 直接插入排序示例對(duì)于有n個(gè)數(shù)據(jù)元素的待排序列，插入操作要進(jìn)行n-1次3.3.7 直接插入排序 從數(shù)組的第2號(hào)元素開(kāi)始，順序取出后續(xù)元素，并將該元素插入到其左端已排好序數(shù)組的適當(dāng)位置。需比較n(n-1)/2次第65頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法例：有6個(gè)記錄，前5 個(gè)已排序的基礎(chǔ)上，對(duì)第6個(gè)記錄排序。 15 27 36 53 69 42 low mid high 15 27 36 53 69 42 low hi

14、gh mid 15 27 36 53 69 42 high low 15 27 36 42 53 69 (high36 ) ( 4253 ) 3.3.7 折半插入排序 折半插入排序在尋找插入位置時(shí)，不是逐個(gè)比較而是利用折半查找的原理尋找插入位置 。待排序元素越多，改進(jìn)效果越明顯。第66頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二 思想：首先從1n個(gè)元素中選出關(guān)鍵字最小的記錄交換到第一個(gè)位置上。然后再?gòu)牡? 個(gè)到第n個(gè)元素中選出次小的記錄交換到第二個(gè)位置上，依次類推。 時(shí)間復(fù)雜度為O(n2)，最壞情況下需要比較 n(n-1)/2次 適用于待排序元素較少的情況。3.3.7 簡(jiǎn)單選擇排

15、序初態(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第三趟第67頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法 交換排序的特點(diǎn)在于交換，有冒泡和快速排序兩種。 冒泡排序（起泡排序） 思想：小的浮起，大的沉底。從左端開(kāi)始比較。 第一趟：第1個(gè)與第2個(gè)比較，大則交換；第2個(gè)與第3個(gè)比較，大則交換，關(guān)鍵字最大的記錄交換到最后一個(gè)位置上； 第二趟：對(duì)前n-1個(gè)記錄進(jìn)行同樣的操作，關(guān)

16、鍵字次大的記錄交換到第n-1個(gè)位置上； 依次類推，則完成排序。 正序：時(shí)間復(fù)雜度為O(n) 逆序：時(shí)間復(fù)雜度為O(n2) 排序n個(gè)記錄的文件最多需要n-1趟冒泡排序。3.3.7 交換排序第68頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法第 六 趟 排 序 后 第 五 趟 排 序 后 第 四 趟 排 序 后 第 三 趟 排 序 后 第 二 趟 排 序 后 第 一 趟 排 序 后初 始 關(guān) 鍵 字 4936416511 7836 653641 56364165 413641561178363641491156492525251149495611111

17、1252525253.3.7 交換排序示例第69頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法各種排序法比較第70頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法3.3.8 圖圖的基本概念 圖：節(jié)點(diǎn)(圖中稱頂點(diǎn))間的連接是任意的。 圖的分類：有向圖、無(wú)向圖V1 V3 V2 V4 在有向圖中，表示從V1到V3的一條弧。 V1為弧尾或初始點(diǎn)，V3為弧頭或終端點(diǎn)。V1 V3 V2 V4 在無(wú)向圖中，(V1，V3)表示V1和V3之間的一條邊。第71頁(yè)，共73頁(yè)，2022年，5月20日，12點(diǎn)28分，星期二二級(jí)ACCESS基本數(shù)據(jù)結(jié)構(gòu)與算法V1 V3 V2 V4 頂點(diǎn)集合V=V1 ， V2 ， V3 ， V4 邊的集合E=(V1, V3), (V1, V2), (V1, V4),(V2, V4) 頂點(diǎn)(V1, V3)與 (V3, V1)表示同一條邊頂點(diǎn)集合V=V1 ， V2 ， V3 ， V4 弧的集合G=, , , V1 V3 V2 V4 3.3.8 圖圖的表示:G=(V,E) 第72頁(yè)，共73