數(shù)據(jù)結(jié)構(gòu)與算法分析期末復(fù)習(xí)課件

“數(shù)據(jù)結(jié)構(gòu)”復(fù)習(xí)指導(dǎo)2010.6“數(shù)據(jù)結(jié)構(gòu)”復(fù)習(xí)指導(dǎo)2010.61考試說明本課程為閉卷考試考試時間為120分鐘。考試題型為：選擇題（20分）填空題（20分）判斷題（10分）應(yīng)用題（20分）（選做）算法題（20分）（選做）附加題考試說明本課程為閉卷考試2一、各章節(jié)主要知識點講解二、對相關(guān)知識點的要求和舉例三、習(xí)題選講數(shù)據(jù)結(jié)構(gòu)與算法分析期末復(fù)習(xí)課件3第1部分緒論 1.數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu):是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，數(shù)據(jù)元素間的關(guān)系稱為結(jié)構(gòu)邏輯結(jié)構(gòu)：數(shù)據(jù)元素間的邏輯（抽象）關(guān)系，與計算機(jī)無關(guān)，同一種邏輯結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu)（物理結(jié)構(gòu)例：鏈?zhǔn)巾樞颍┪锢斫Y(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示（數(shù)據(jù)元素的表示和關(guān)系的表示）第1部分緒論 4第1部分緒論 4種基本的邏輯結(jié)構(gòu)：集合線性（一對一）樹形（一對多）圖形（多對多）4種基本的物理結(jié)構(gòu)：順序結(jié)構(gòu) 鏈?zhǔn)浇Y(jié)構(gòu) 散列結(jié)構(gòu) 索引結(jié)構(gòu)習(xí)題集P21.8（1，2，3）第1部分緒論 4種基本的邏輯結(jié)構(gòu)：5第1部分緒論 2.算法的基本概念算法的5個特性:（有窮性、確定性、可行性、零個或多個輸入、一個或多個輸出）時間復(fù)雜度：評估算法的重要標(biāo)準(zhǔn)之一，能較好的體現(xiàn)算法本身的時間效率，與計算機(jī)硬件無關(guān)（基本操作、問題的規(guī)模、基本操作的頻度是問題規(guī)模的函數(shù)）例:n個數(shù)中找最大的習(xí)題集P11.7（2，3）1.8（6，7）第1部分緒論 2.算法的基本概念6第2部分線性表1.線性表的邏輯結(jié)構(gòu)前驅(qū)、后繼一對一的關(guān)系2.線性表的順序存儲結(jié)構(gòu)（使用連續(xù)的存儲空間）順序表特點：可以隨機(jī)訪問插入:若有n個元素的順序表，在第i個元素之前插入，也即插入元素作為第i個元素i=n+1時移動元素次數(shù)為0；i=1時移動元素次數(shù)為n；一般情況n-i+1；

第2部分線性表1.線性表的邏輯結(jié)構(gòu)7第2部分線性表刪除i=1時移動元素次數(shù)為n-1；i=n時移動元素次數(shù)為0；一般情況移動次數(shù)n-i；插入、刪除的基本操作為元素移動時間復(fù)雜度為O(n)習(xí)題集P42.7（1，2）當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用（）存儲結(jié)構(gòu)。第2部分線性表刪除8順序表相關(guān)算法順序查找、折半查找線性表中某個元素x，返回其位置查找順序表中某個元素x的個數(shù)線性表的插入和刪除算法順序表相關(guān)算法順序查找、折半查找線性表中某個元素x，返回其位9第2部分線性表3.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)（存儲空間可以連續(xù)也可以不連續(xù)）鏈表（結(jié)點、頭指針、尾結(jié)點、帶頭結(jié)點的鏈表）特點：不能隨機(jī)訪問第2部分線性表10第2部分線性表4.單向鏈表靜態(tài)法（說明變量）建立鏈表尾插法建立鏈表（頭指針、q始終指向尾結(jié)點、p生成新結(jié)點）頭插法建立鏈表（頭指針、q始終指向頭結(jié)點、p生成新結(jié)點）插入（在第i個結(jié)點前插入新結(jié)點，p生成新結(jié)點，q指向第i-1個結(jié)點…）刪除（刪除第i個結(jié)點，q指向第i個結(jié)點的前驅(qū)（第i-1個結(jié)點），p指向第i個結(jié)點）四種操作都必須知道操作位置結(jié)點的前驅(qū)結(jié)點的指針第2部分線性表4.單向鏈表11第2部分線性表5.單向循環(huán)鏈表特點：從任一結(jié)點開始可以訪問到表中其它結(jié)點，但不能隨機(jī)訪問由單向鏈表構(gòu)造單向循環(huán)鏈表如何判斷單向循環(huán)鏈表6.雙向循環(huán)鏈表存儲結(jié)構(gòu)特點插入、刪除習(xí)題集P42.7（4，5，6）第2部分線性表5.單向循環(huán)鏈表12（單）鏈表的相關(guān)算法查找單鏈表中的最大值、最小值查找單鏈表中元素x的個數(shù)（單）鏈表的相關(guān)算法查找單鏈表中的最大值、最小值13分析以下語句的正誤線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。線性表采用順序存儲，便于進(jìn)行插入和刪除操作。線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。線性表采用鏈接存儲，便于插入和刪除操作。鏈表對于數(shù)據(jù)元素的插入和刪除不需移動結(jié)點，只需改變相關(guān)結(jié)點的指針域的值。

分析以下語句的正誤14第3部分棧和隊列1.棧棧是運算受限的線性表插入、刪除限定在表的尾部進(jìn)行（棧頂）棧頂、棧底、空棧、棧頂元素順序棧（連續(xù)的存儲空間）用結(jié)構(gòu)體變量實現(xiàn)的順序棧結(jié)構(gòu)體變量規(guī)定：棧底為數(shù)組下標(biāo)為0的一端溢出：棧頂指針（下標(biāo)）為-1時為空，棧頂為MaxSize-1時棧滿上溢（滿）、下溢（空）數(shù)組（棧元素）整型變量（棧頂指針）第3部分棧和隊列1.棧數(shù)組（棧元素）15第3部分棧和隊列鏈棧（用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)的棧）（了解）可以用不帶頭結(jié)點的單向鏈表實現(xiàn)鏈棧存儲結(jié)構(gòu)structnode*top；基本操作：初始化、判?？?、進(jìn)棧、出棧（與不帶頭結(jié)點的單向鏈表的頭部插入、頭部刪除相同）鏈棧只有空和非空兩種狀態(tài)，沒有棧滿的情況第3部分棧和隊列鏈棧（用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)的棧）（了解）16相關(guān)練習(xí)習(xí)題集P53.13.2-23.5（1，3）

3.33.43.6（15，16）相關(guān)練習(xí)習(xí)題集P53.13.2-23.5（1，3）17第3部分棧和隊列2.隊列隊列是運算受限的線性表允許在隊尾插入，在隊頭刪除隊頭、隊尾、空隊列順序隊列（順序存儲的隊列）用結(jié)構(gòu)體變量實現(xiàn)的順序隊列結(jié)構(gòu)體變量數(shù)組（隊元素）整型變量1:front（隊頭指針）整型變量2:rear（隊尾指針）第3部分棧和隊列2.隊列數(shù)組（隊元素）18第3部分棧和隊列隊列初始化：隊頭指針、隊尾指針均置為0隊頭指針front指向隊頭元素隊尾指針rear指向隊尾元素的下一個位置隊列為空時front=rear隊列滿時rear==MaxSize上溢：隊列已滿進(jìn)行入隊操作假上溢：隊列未滿，但尾指針已超越存儲空間上界下溢：隊列已空，要進(jìn)行出隊操作操作：初始化、判隊空、入隊、出隊、取隊頭元素第3部分棧和隊列隊列初始化：隊頭指針、隊尾指針均置為019第3部分棧和隊列3.循環(huán)隊列為解決“假上溢”問題設(shè)想隊列為一個首尾相接的圓環(huán)為了區(qū)別循環(huán)隊列的隊滿和隊空規(guī)定少用一個存儲空間尾指針加1等于頭指針時為隊滿即：（rear+1）%MaxSize==front當(dāng)front==rear時為隊空第3部分棧和隊列3.循環(huán)隊列20第3部分棧和隊列4.鏈隊列（了解）可以用一個帶頭結(jié)點的單向鏈表存儲隊元素，在表頭刪除，在表尾插入存儲結(jié)構(gòu)：structnode*front，*rear；基本操作初始化、判隊空、入隊、出隊第3部分棧和隊列4.鏈隊列（了解）21相關(guān)練習(xí)P63.5（8）棧和隊列的特征棧和隊列的異同點棧和隊列的存儲方式：順序存儲和鏈?zhǔn)酱鎯ο嚓P(guān)練習(xí)P63.5（8）22第4部分樹和二叉樹1.樹的基本術(shù)語葉結(jié)點（終端結(jié)點）、分支結(jié)點（非葉結(jié)點）結(jié)點的度（引出結(jié)點的個數(shù)）孩子結(jié)點、雙親結(jié)點、兄弟結(jié)點結(jié)點的層數(shù)、樹的深度2.樹的性質(zhì)性質(zhì)1-性質(zhì)5ABCDEFGHI第4部分樹和二叉樹1.樹的基本術(shù)語ABCDEFGHI23第4部分樹和二叉樹性質(zhì)1二叉樹上第i層至多有2i-1個結(jié)點性質(zhì)2深度為h的二叉樹最多有2h-1個結(jié)點

1+2+4+8=24-1=15第4部分樹和二叉樹性質(zhì)124第4部分樹和二叉樹性質(zhì)3二叉樹上終端結(jié)點數(shù)等于雙分支結(jié)點數(shù)加1（n0=n2+1）要求：在結(jié)點總數(shù)、葉結(jié)點數(shù)、雙分支結(jié)點數(shù)、單分支結(jié)點數(shù)之間能進(jìn)行相關(guān)計算ABCDE第4部分樹和二叉樹ABCDE25第4部分樹和二叉樹性質(zhì)4含有n個結(jié)點的完全二叉樹，其深度為︳log2n」+1術(shù)語：滿二叉樹完全二叉樹第4部分樹和二叉樹性質(zhì)426第4部分樹和二叉樹性質(zhì)5二叉樹中順序編號為i的結(jié)點左孩子：2i右孩子：2i+1父結(jié)點：i/2術(shù)語：滿二叉樹完全二叉樹第4部分樹和二叉樹性質(zhì)527相關(guān)練習(xí)習(xí)題集P105.23（5-16）

5.24（1，2，3，4，15-18）

5.25（4，6，7，9，10，）相關(guān)練習(xí)習(xí)題集P105.23（5-16）28第4部分樹和二叉樹4.二叉樹的存儲結(jié)構(gòu)順序存儲樹的序號與一維數(shù)組的下標(biāo)對應(yīng)鏈接存儲結(jié)構(gòu)習(xí)題集P75.2leftdataright第4部分樹和二叉樹4.二叉樹的存儲結(jié)構(gòu)leftdatar29第4部分樹和二叉樹5.二叉樹的遍歷遞歸定義：二叉樹或者是一棵空樹，或者是一棵由一個根結(jié)點和互不相交的分別稱為根的左子樹和右子樹所組成的非空樹（左、右子樹可以為空樹），左、右子樹也同樣是一棵二叉樹習(xí)題集P85.7CBA第4部分樹和二叉樹5.二叉樹的遍歷CBA30第4部分樹和二叉樹遍歷：按照一定次序訪問每個結(jié)點一次且僅一次遍歷規(guī)則：（先左后右，以訪問根的次序區(qū)分遍歷方法）先序：根、左子樹、右子樹中序：左子樹、根、右子樹后序：左子樹、右子樹、根遞歸算法程序（掌握）例后序遍歷：5,4,2,6,9,8,7,3,1123467589第4部分樹和二叉樹遍歷：按照一定次序訪問每個結(jié)點一次且僅31第4部分樹和二叉樹例

中序遍歷：CBDAEGF

先序遍歷：ABCDEFG

后序遍歷：CDBGFEA二叉樹的非遞歸遍歷算法（了解）二叉樹的其它運算（了解）ABECDFG第4部分樹和二叉樹例32第4部分樹和二叉樹6.哈夫曼樹結(jié)點的帶權(quán)路徑長度（路徑長×結(jié)點的權(quán)）樹的帶權(quán)路徑長度

WPL=WiLi所有葉結(jié)點的帶權(quán)路徑長度之和：4x3＋2x2+1x1=…124第4部分樹和二叉樹6.哈夫曼樹12433第4部分樹和二叉樹哈夫曼樹（最優(yōu)樹）n個帶權(quán)葉結(jié)點的所有二叉樹中，WPL最小的樹性質(zhì)：除葉結(jié)點外其余結(jié)點全為雙分支結(jié)點（要求掌握哈夫曼樹總結(jié)點數(shù)、葉結(jié)點數(shù)、分支結(jié)點數(shù)之間的計算）構(gòu)造Huffman樹和Huffman編碼習(xí)題集P85.145.15（總碼數(shù)不要求）第4部分樹和二叉樹哈夫曼樹（最優(yōu)樹）34第4部分樹和二叉樹例：權(quán)重：a,b,c,d,e3,5,6,7,9a:000b:001c:10d:11e:01301713896735000001111第4部分樹和二叉樹例：權(quán)重：a,b,c,d,e335第4部分樹和二叉樹7.由遍歷序列確定二叉樹先序中序（先序確定根結(jié)點，中序劃分左右子樹）后序中序（后序確定根結(jié)點，中序劃分左右子樹）例先序遍歷序列為stuwv，中序遍歷序列為uwtvs

由先序：s是根，由中序：左子樹uwtv，右子樹為空由先序：t是左子樹根，由中序：左子樹uw，右子樹v由先序：u是左子樹根，由中序：左子樹空，右子樹wstuwv第4部分樹和二叉樹7.由遍歷序列確定二叉樹stuwv36第4部分樹和二叉樹例：先序遍歷：bfdec，中序fbedc

由先序：b為根由中序：左子樹f，右子樹edc由先序：d為根由中序：左子樹e，右子樹c

后序：fecdb習(xí)題集P85.13及其類似的題必須掌握bfedc第4部分樹和二叉樹例：先序遍歷：bfdec，中序fbed37第5部分查找1.基本概念平均查找長度查找的基本操作是“比較”ASL=CiPi:Ci是查找到第i個記錄的比較次數(shù)Pi是查找第i個記錄的概率第5部分查找1.基本概念38第5部分查找2.線性表的查找順序查找：等概率條件下

ASL=1/ni=(n+1)/2折半查找和折半查找對應(yīng)的判定樹要求：查找表（順序存儲)中記錄相應(yīng)的關(guān)鍵字值必須有序（升序或降序）例：查找表6,14,20,21,38,56,68,78,85,85,100

序號012345678910第5部分查找2.線性表的查找39第5部分查找（1）畫出折半查找的判定樹（2）查找到68要進(jìn)行多少次元素間的比較（3次）（3）要查32，經(jīng)多少次查找確定查不到（4次）（4）等概率條件下，平均查找長度

ASL=(1X1+2X2+3X4+4X4)/11=…

判定樹：習(xí)題集P136.18036914107382068521688514567810052第5部分查找（1）畫出折半查找的判定樹80369141040第5部分查找3.分塊查找查找表分塊：塊間有序、每塊無序索引表：索引表中一個記錄對應(yīng)一塊查找步驟：折半查找確定塊，塊內(nèi)順序查找

塊內(nèi)最大關(guān)鍵字塊中第一個記錄的位置（地址指針）索引表記錄第5部分查找3.分塊查找塊內(nèi)最大關(guān)鍵字索引表記錄41靜態(tài)查找方法比較ASL最大最小兩者之間表結(jié)構(gòu)有序表/無序表有序表分塊有序表存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表順序查找折半查找分塊查找靜態(tài)查找方法比較ASL最大最小兩者之間表結(jié)構(gòu)有序表/無序表有42第5部分查找4.動態(tài)查找二叉排序樹三要素：（a）根結(jié)點大于左子樹上所有結(jié)點的值（或等于）（b）根結(jié)點小于右子樹上所有結(jié)點的值（或等于）（c）左、右子樹也分別是一棵二叉排序樹例：二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值（x）3565124第5部分查找4.動態(tài)查找356512443第5部分查找二叉排序樹的插入操作（也可用來構(gòu)造二叉排序樹）例:(1)給定序列{9,18,6,10,22,11,8,20,7},依次取序列中的數(shù)構(gòu)造一棵二叉排序樹(2)給出中序遍歷的序列6,7,8,9,10,11,18,20,2261822810911207第5部分查找二叉排序樹的插入操作（也可用來構(gòu)造二叉排序樹44第5部分查找對二叉排序樹進(jìn)行中序遍歷所得的序列是有序序列(由小到大）二叉排序樹的刪除操作（分4種情況，了解）刪除原則是刪除后使得到的樹是二叉排序樹習(xí)題集P136.3

第5部分查找對二叉排序樹進(jìn)行中序遍歷所得的序列是有序序列45第5部分查找平衡二叉樹（AVL樹）平衡因子的絕對值小于等于1四種旋轉(zhuǎn)方式習(xí)題集P136.5以及以前的作業(yè)題

第5部分查找平衡二叉樹（AVL樹）46第5部分查找5.哈希表及其查找相關(guān)名詞哈希函數(shù)：記錄的關(guān)鍵字存儲地址哈希表：存放查找表中記錄的序列，存儲位置是以關(guān)鍵字為自變量由哈希函數(shù)計算所得到的數(shù)值哈希查找（散列查找）原理：在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立確定的對應(yīng)關(guān)系哈希函數(shù)構(gòu)造法、處理沖突的方法除留余數(shù)法開放定址法和鏈地址法第5部分查找5.哈希表及其查找47哈希查找的練習(xí)題散列查找法的特點是（）。A、通過關(guān)鍵字的比較進(jìn)行B、通過關(guān)鍵字計算元素的存儲地址進(jìn)行查找C、通過關(guān)鍵字計算元素的存儲地址并進(jìn)行一定的比較進(jìn)行查找D、以上都不是習(xí)題集P136.86.11（17，20）哈希查找的練習(xí)題散列查找法的特點是（）。48練習(xí)題以前做過的題目，如練習(xí)題以前做過的題目，如49第6部分排序1.基本概念排序穩(wěn)定的排序方法關(guān)鍵字相等的記錄經(jīng)排序后保持它們原來的前后關(guān)系不穩(wěn)定的排序方法關(guān)鍵字相等的記錄經(jīng)排序后可能改變它們原來的前后關(guān)系第6部分排序1.基本概念50第6部分排序2.插入類排序直接插入排序：每一趟從無序子表中將一個待排的記錄按其關(guān)鍵字大小放到已排好序的子序列的適當(dāng)位置例

47,83,41,53,684747,8341478341475383

4147536883第6部分排序2.插入類排序51第6部分排序例：65，49，116，43，26，92，80，55，100用直接插入排序，當(dāng)要把第7個元素80插入到已排好序的子表時，需進(jìn)行多少次元素的比較

2643496592116||80

3次第6部分排序例：65，49，116，43，26，92，52第6部分排序折半插入排序利用折半查找尋找插入位置第6部分排序53第6部分排序希爾排序按照一定的增量逐步縮小范圍進(jìn)行排序在增量范圍內(nèi)進(jìn)行直接插入排序即可要求能夠?qū)懗鱿柵判虻拿恳惶说?部分排序54第6部分排序3.交換類排序冒泡排序n個元素，從左到右兩兩比較，必要時交換共需要n-1趟冒泡第i趟要進(jìn)行n-i次元素間比較若某一趟冒泡中沒有進(jìn)行元素的交換（0次交換），則序列已排好序第6部分排序3.交換類排序55第6部分排序快速排序選取劃分元素，i，j分別指向序列起、止位置，從后向前(j)掃描找到小于分割元素的元素，占位(i),i=i+1;從前向后(i)掃描找到大于分割元素的元素，占位(j),j=j-1;

i等于j時完成一趟快速排序要求寫出快速排序的第一趟第6部分排序快速排序56第6部分排序例55,50,75,53,45,1055555，50，75，53，45，10545，50，75，53，45，105從后向前45，50，75，53，75，105從前向后45，50，53，53，75，105從后向前45，50，53，55，75，105(55歸位)第6部分排序例55,50,75,53,457第6部分排序4.選擇類排序直接選擇排序第1趟：讓a[1]與a[2]…a[n]比較找到最小元素的下標(biāo)k1，讓a[1]與a[k1]交換第2趟：讓a[2]與a[3]…a[n]比較找到最小元素的下標(biāo)k2，……共進(jìn)行n-1趟選擇第6部分排序4.選擇類排序58第6部分排序堆排序堆和特殊性質(zhì)完全二叉樹的對應(yīng)例：堆{14,40,30,50,80,65,50,100}

14403050806550100第6部分排序堆排序1440305080655010059第6部分排序小根堆：任意非葉結(jié)點的值小于等于左、右孩子結(jié)點的值大根堆：任意非葉結(jié)點的值大于等于左、右孩子結(jié)點的值篩選法建堆例：序列{47,87,72,107,21,37,62,57}47107213762577287475721726210737874757877262107372121578772621073747（初始樹）（堆）第6部分排序小根堆：任意非葉結(jié)點的值小于等于左、右孩子60第6部分排序堆排序：用篩選法建n個元素的堆，交換堆頂元素和最后一個元素，再用篩選法建n-1個元素的堆…能畫出初始堆和最大、小堆如何排序，排出第一、二個第6部分排序61第6部分排序5.歸并排序歸并兩個有序的序列（指針法）一趟歸并排序歸并排序歸并排序原理（1，1）歸并得到若干長度為2的有序序列（2，2）歸并得到若干長度為4的有序序列……第6部分排序5.歸并排序62第6部分排序例40,35,55,25,70,100,30,75[35,40][25,55][70,100][30,75][25,35,40,55][30,70,75,100][25,30,35,40,55,70,75,100]習(xí)題集P157.2P167.9（10，15）7.10（9-11，24，26）第6部分排序例40,35,55,25,70,100,63

祝同學(xué)們?nèi)〉煤贸煽儯?/p>

64“數(shù)據(jù)結(jié)構(gòu)”復(fù)習(xí)指導(dǎo)2010.6“數(shù)據(jù)結(jié)構(gòu)”復(fù)習(xí)指導(dǎo)2010.665考試說明本課程為閉卷考試考試時間為120分鐘。考試題型為：選擇題（20分）填空題（20分）判斷題（10分）應(yīng)用題（20分）（選做）算法題（20分）（選做）附加題考試說明本課程為閉卷考試66一、各章節(jié)主要知識點講解二、對相關(guān)知識點的要求和舉例三、習(xí)題選講數(shù)據(jù)結(jié)構(gòu)與算法分析期末復(fù)習(xí)課件67第1部分緒論 1.數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu):是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，數(shù)據(jù)元素間的關(guān)系稱為結(jié)構(gòu)邏輯結(jié)構(gòu)：數(shù)據(jù)元素間的邏輯（抽象）關(guān)系，與計算機(jī)無關(guān)，同一種邏輯結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu)（物理結(jié)構(gòu)例：鏈?zhǔn)巾樞颍┪锢斫Y(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示（數(shù)據(jù)元素的表示和關(guān)系的表示）第1部分緒論 68第1部分緒論 4種基本的邏輯結(jié)構(gòu)：集合線性（一對一）樹形（一對多）圖形（多對多）4種基本的物理結(jié)構(gòu)：順序結(jié)構(gòu) 鏈?zhǔn)浇Y(jié)構(gòu) 散列結(jié)構(gòu) 索引結(jié)構(gòu)習(xí)題集P21.8（1，2，3）第1部分緒論 4種基本的邏輯結(jié)構(gòu)：69第1部分緒論 2.算法的基本概念算法的5個特性:（有窮性、確定性、可行性、零個或多個輸入、一個或多個輸出）時間復(fù)雜度：評估算法的重要標(biāo)準(zhǔn)之一，能較好的體現(xiàn)算法本身的時間效率，與計算機(jī)硬件無關(guān)（基本操作、問題的規(guī)模、基本操作的頻度是問題規(guī)模的函數(shù)）例:n個數(shù)中找最大的習(xí)題集P11.7（2，3）1.8（6，7）第1部分緒論 2.算法的基本概念70第2部分線性表1.線性表的邏輯結(jié)構(gòu)前驅(qū)、后繼一對一的關(guān)系2.線性表的順序存儲結(jié)構(gòu)（使用連續(xù)的存儲空間）順序表特點：可以隨機(jī)訪問插入:若有n個元素的順序表，在第i個元素之前插入，也即插入元素作為第i個元素i=n+1時移動元素次數(shù)為0；i=1時移動元素次數(shù)為n；一般情況n-i+1；

第2部分線性表1.線性表的邏輯結(jié)構(gòu)71第2部分線性表刪除i=1時移動元素次數(shù)為n-1；i=n時移動元素次數(shù)為0；一般情況移動次數(shù)n-i；插入、刪除的基本操作為元素移動時間復(fù)雜度為O(n)習(xí)題集P42.7（1，2）當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用（）存儲結(jié)構(gòu)。第2部分線性表刪除72順序表相關(guān)算法順序查找、折半查找線性表中某個元素x，返回其位置查找順序表中某個元素x的個數(shù)線性表的插入和刪除算法順序表相關(guān)算法順序查找、折半查找線性表中某個元素x，返回其位73第2部分線性表3.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)（存儲空間可以連續(xù)也可以不連續(xù)）鏈表（結(jié)點、頭指針、尾結(jié)點、帶頭結(jié)點的鏈表）特點：不能隨機(jī)訪問第2部分線性表74第2部分線性表4.單向鏈表靜態(tài)法（說明變量）建立鏈表尾插法建立鏈表（頭指針、q始終指向尾結(jié)點、p生成新結(jié)點）頭插法建立鏈表（頭指針、q始終指向頭結(jié)點、p生成新結(jié)點）插入（在第i個結(jié)點前插入新結(jié)點，p生成新結(jié)點，q指向第i-1個結(jié)點…）刪除（刪除第i個結(jié)點，q指向第i個結(jié)點的前驅(qū)（第i-1個結(jié)點），p指向第i個結(jié)點）四種操作都必須知道操作位置結(jié)點的前驅(qū)結(jié)點的指針第2部分線性表4.單向鏈表75第2部分線性表5.單向循環(huán)鏈表特點：從任一結(jié)點開始可以訪問到表中其它結(jié)點，但不能隨機(jī)訪問由單向鏈表構(gòu)造單向循環(huán)鏈表如何判斷單向循環(huán)鏈表6.雙向循環(huán)鏈表存儲結(jié)構(gòu)特點插入、刪除習(xí)題集P42.7（4，5，6）第2部分線性表5.單向循環(huán)鏈表76（單）鏈表的相關(guān)算法查找單鏈表中的最大值、最小值查找單鏈表中元素x的個數(shù)（單）鏈表的相關(guān)算法查找單鏈表中的最大值、最小值77分析以下語句的正誤線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。線性表采用順序存儲，便于進(jìn)行插入和刪除操作。線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。線性表采用鏈接存儲，便于插入和刪除操作。鏈表對于數(shù)據(jù)元素的插入和刪除不需移動結(jié)點，只需改變相關(guān)結(jié)點的指針域的值。

分析以下語句的正誤78第3部分棧和隊列1.棧棧是運算受限的線性表插入、刪除限定在表的尾部進(jìn)行（棧頂）棧頂、棧底、空棧、棧頂元素順序棧（連續(xù)的存儲空間）用結(jié)構(gòu)體變量實現(xiàn)的順序棧結(jié)構(gòu)體變量規(guī)定：棧底為數(shù)組下標(biāo)為0的一端溢出：棧頂指針（下標(biāo)）為-1時為空，棧頂為MaxSize-1時棧滿上溢（滿）、下溢（空）數(shù)組（棧元素）整型變量（棧頂指針）第3部分棧和隊列1.棧數(shù)組（棧元素）79第3部分棧和隊列鏈棧（用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)的棧）（了解）可以用不帶頭結(jié)點的單向鏈表實現(xiàn)鏈棧存儲結(jié)構(gòu)structnode*top；基本操作：初始化、判?？铡⑦M(jìn)棧、出棧（與不帶頭結(jié)點的單向鏈表的頭部插入、頭部刪除相同）鏈棧只有空和非空兩種狀態(tài)，沒有棧滿的情況第3部分棧和隊列鏈棧（用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)的棧）（了解）80相關(guān)練習(xí)習(xí)題集P53.13.2-23.5（1，3）

3.33.43.6（15，16）相關(guān)練習(xí)習(xí)題集P53.13.2-23.5（1，3）81第3部分棧和隊列2.隊列隊列是運算受限的線性表允許在隊尾插入，在隊頭刪除隊頭、隊尾、空隊列順序隊列（順序存儲的隊列）用結(jié)構(gòu)體變量實現(xiàn)的順序隊列結(jié)構(gòu)體變量數(shù)組（隊元素）整型變量1:front（隊頭指針）整型變量2:rear（隊尾指針）第3部分棧和隊列2.隊列數(shù)組（隊元素）82第3部分棧和隊列隊列初始化：隊頭指針、隊尾指針均置為0隊頭指針front指向隊頭元素隊尾指針rear指向隊尾元素的下一個位置隊列為空時front=rear隊列滿時rear==MaxSize上溢：隊列已滿進(jìn)行入隊操作假上溢：隊列未滿，但尾指針已超越存儲空間上界下溢：隊列已空，要進(jìn)行出隊操作操作：初始化、判隊空、入隊、出隊、取隊頭元素第3部分棧和隊列隊列初始化：隊頭指針、隊尾指針均置為083第3部分棧和隊列3.循環(huán)隊列為解決“假上溢”問題設(shè)想隊列為一個首尾相接的圓環(huán)為了區(qū)別循環(huán)隊列的隊滿和隊空規(guī)定少用一個存儲空間尾指針加1等于頭指針時為隊滿即：（rear+1）%MaxSize==front當(dāng)front==rear時為隊空第3部分棧和隊列3.循環(huán)隊列84第3部分棧和隊列4.鏈隊列（了解）可以用一個帶頭結(jié)點的單向鏈表存儲隊元素，在表頭刪除，在表尾插入存儲結(jié)構(gòu)：structnode*front，*rear；基本操作初始化、判隊空、入隊、出隊第3部分棧和隊列4.鏈隊列（了解）85相關(guān)練習(xí)P63.5（8）棧和隊列的特征棧和隊列的異同點棧和隊列的存儲方式：順序存儲和鏈?zhǔn)酱鎯ο嚓P(guān)練習(xí)P63.5（8）86第4部分樹和二叉樹1.樹的基本術(shù)語葉結(jié)點（終端結(jié)點）、分支結(jié)點（非葉結(jié)點）結(jié)點的度（引出結(jié)點的個數(shù)）孩子結(jié)點、雙親結(jié)點、兄弟結(jié)點結(jié)點的層數(shù)、樹的深度2.樹的性質(zhì)性質(zhì)1-性質(zhì)5ABCDEFGHI第4部分樹和二叉樹1.樹的基本術(shù)語ABCDEFGHI87第4部分樹和二叉樹性質(zhì)1二叉樹上第i層至多有2i-1個結(jié)點性質(zhì)2深度為h的二叉樹最多有2h-1個結(jié)點

1+2+4+8=24-1=15第4部分樹和二叉樹性質(zhì)188第4部分樹和二叉樹性質(zhì)3二叉樹上終端結(jié)點數(shù)等于雙分支結(jié)點數(shù)加1（n0=n2+1）要求：在結(jié)點總數(shù)、葉結(jié)點數(shù)、雙分支結(jié)點數(shù)、單分支結(jié)點數(shù)之間能進(jìn)行相關(guān)計算ABCDE第4部分樹和二叉樹ABCDE89第4部分樹和二叉樹性質(zhì)4含有n個結(jié)點的完全二叉樹，其深度為︳log2n」+1術(shù)語：滿二叉樹完全二叉樹第4部分樹和二叉樹性質(zhì)490第4部分樹和二叉樹性質(zhì)5二叉樹中順序編號為i的結(jié)點左孩子：2i右孩子：2i+1父結(jié)點：i/2術(shù)語：滿二叉樹完全二叉樹第4部分樹和二叉樹性質(zhì)591相關(guān)練習(xí)習(xí)題集P105.23（5-16）

5.24（1，2，3，4，15-18）

5.25（4，6，7，9，10，）相關(guān)練習(xí)習(xí)題集P105.23（5-16）92第4部分樹和二叉樹4.二叉樹的存儲結(jié)構(gòu)順序存儲樹的序號與一維數(shù)組的下標(biāo)對應(yīng)鏈接存儲結(jié)構(gòu)習(xí)題集P75.2leftdataright第4部分樹和二叉樹4.二叉樹的存儲結(jié)構(gòu)leftdatar93第4部分樹和二叉樹5.二叉樹的遍歷遞歸定義：二叉樹或者是一棵空樹，或者是一棵由一個根結(jié)點和互不相交的分別稱為根的左子樹和右子樹所組成的非空樹（左、右子樹可以為空樹），左、右子樹也同樣是一棵二叉樹習(xí)題集P85.7CBA第4部分樹和二叉樹5.二叉樹的遍歷CBA94第4部分樹和二叉樹遍歷：按照一定次序訪問每個結(jié)點一次且僅一次遍歷規(guī)則：（先左后右，以訪問根的次序區(qū)分遍歷方法）先序：根、左子樹、右子樹中序：左子樹、根、右子樹后序：左子樹、右子樹、根遞歸算法程序（掌握）例后序遍歷：5,4,2,6,9,8,7,3,1123467589第4部分樹和二叉樹遍歷：按照一定次序訪問每個結(jié)點一次且僅95第4部分樹和二叉樹例

中序遍歷：CBDAEGF

先序遍歷：ABCDEFG

后序遍歷：CDBGFEA二叉樹的非遞歸遍歷算法（了解）二叉樹的其它運算（了解）ABECDFG第4部分樹和二叉樹例96第4部分樹和二叉樹6.哈夫曼樹結(jié)點的帶權(quán)路徑長度（路徑長×結(jié)點的權(quán)）樹的帶權(quán)路徑長度

WPL=WiLi所有葉結(jié)點的帶權(quán)路徑長度之和：4x3＋2x2+1x1=…124第4部分樹和二叉樹6.哈夫曼樹12497第4部分樹和二叉樹哈夫曼樹（最優(yōu)樹）n個帶權(quán)葉結(jié)點的所有二叉樹中，WPL最小的樹性質(zhì)：除葉結(jié)點外其余結(jié)點全為雙分支結(jié)點（要求掌握哈夫曼樹總結(jié)點數(shù)、葉結(jié)點數(shù)、分支結(jié)點數(shù)之間的計算）構(gòu)造Huffman樹和Huffman編碼習(xí)題集P85.145.15（總碼數(shù)不要求）第4部分樹和二叉樹哈夫曼樹（最優(yōu)樹）98第4部分樹和二叉樹例：權(quán)重：a,b,c,d,e3,5,6,7,9a:000b:001c:10d:11e:01301713896735000001111第4部分樹和二叉樹例：權(quán)重：a,b,c,d,e399第4部分樹和二叉樹7.由遍歷序列確定二叉樹先序中序（先序確定根結(jié)點，中序劃分左右子樹）后序中序（后序確定根結(jié)點，中序劃分左右子樹）例先序遍歷序列為stuwv，中序遍歷序列為uwtvs

由先序：s是根，由中序：左子樹uwtv，右子樹為空由先序：t是左子樹根，由中序：左子樹uw，右子樹v由先序：u是左子樹根，由中序：左子樹空，右子樹wstuwv第4部分樹和二叉樹7.由遍歷序列確定二叉樹stuwv100第4部分樹和二叉樹例：先序遍歷：bfdec，中序fbedc

由先序：b為根由中序：左子樹f，右子樹edc由先序：d為根由中序：左子樹e，右子樹c

后序：fecdb習(xí)題集P85.13及其類似的題必須掌握bfedc第4部分樹和二叉樹例：先序遍歷：bfdec，中序fbed101第5部分查找1.基本概念平均查找長度查找的基本操作是“比較”ASL=CiPi:Ci是查找到第i個記錄的比較次數(shù)Pi是查找第i個記錄的概率第5部分查找1.基本概念102第5部分查找2.線性表的查找順序查找：等概率條件下

ASL=1/ni=(n+1)/2折半查找和折半查找對應(yīng)的判定樹要求：查找表（順序存儲)中記錄相應(yīng)的關(guān)鍵字值必須有序（升序或降序）例：查找表6,14,20,21,38,56,68,78,85,85,100

序號012345678910第5部分查找2.線性表的查找103第5部分查找（1）畫出折半查找的判定樹（2）查找到68要進(jìn)行多少次元素間的比較（3次）（3）要查32，經(jīng)多少次查找確定查不到（4次）（4）等概率條件下，平均查找長度

ASL=(1X1+2X2+3X4+4X4)/11=…

判定樹：習(xí)題集P136.18036914107382068521688514567810052第5部分查找（1）畫出折半查找的判定樹803691410104第5部分查找3.分塊查找查找表分塊：塊間有序、每塊無序索引表：索引表中一個記錄對應(yīng)一塊查找步驟：折半查找確定塊，塊內(nèi)順序查找

塊內(nèi)最大關(guān)鍵字塊中第一個記錄的位置（地址指針）索引表記錄第5部分查找3.分塊查找塊內(nèi)最大關(guān)鍵字索引表記錄105靜態(tài)查找方法比較ASL最大最小兩者之間表結(jié)構(gòu)有序表/無序表有序表分塊有序表存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表順序查找折半查找分塊查找靜態(tài)查找方法比較ASL最大最小兩者之間表結(jié)構(gòu)有序表/無序表有106第5部分查找4.動態(tài)查找二叉排序樹三要素：（a）根結(jié)點大于左子樹上所有結(jié)點的值（或等于）（b）根結(jié)點小于右子樹上所有結(jié)點的值（或等于）（c）左、右子樹也分別是一棵二叉排序樹例：二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值（x）3565124第5部分查找4.動態(tài)查找3565124107第5部分查找二叉排序樹的插入操作（也可用來構(gòu)造二叉排序樹）例:(1)給定序列{9,18,6,10,22,11,8,20,7},依次取序列中的數(shù)構(gòu)造一棵二叉排序樹(2)給出中序遍歷的序列6,7,8,9,10,11,18,20,2261822810911207第5部分查找二叉排序樹的插入操作（也可用來構(gòu)造二叉排序樹108第5部分查找對二叉排序樹進(jìn)行中序遍歷所得的序列是有序序列(由小到大）二叉排序樹的刪除操作（分4種情況，了解）刪除原則是刪除后使得到的樹是二叉排序樹習(xí)題集P136.3

第5部分查找對二叉排序樹進(jìn)行中序遍歷所得的序列是有序序列109第5部分查找平衡二叉樹（AVL樹）平衡因子的絕對值小于等于1四種旋轉(zhuǎn)方式習(xí)題集P136.5以及以前的作業(yè)題

第5部分查找平衡二叉樹（AVL樹）110第5部分查找5.哈希表及其查找相關(guān)名詞哈希函數(shù)：記錄的關(guān)鍵字存儲地址哈希表：存放查找表中記錄的序列，存儲位置是以關(guān)鍵字為自變量由哈希函數(shù)計算所得到的數(shù)值哈希查找（散列查找）原理：在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立確定的對應(yīng)關(guān)系哈希函數(shù)構(gòu)造法、處理沖突的方法除留余數(shù)法開放定址法和鏈地址法第5部分查找5.哈希表及其查找111哈希查找的練習(xí)題散列查找法的特點是（）。A、通過關(guān)鍵字的比較進(jìn)行B、通過關(guān)鍵字計算元素的存儲地址進(jìn)行查找C、通過關(guān)鍵字計算元素的存儲地址并進(jìn)行一定的比較進(jìn)行查找D、以上都不是習(xí)題集P136.86.11（17，20）哈希查找的練習(xí)題散列查找法的特點是（）。112練習(xí)題以前做過的題目，如練習(xí)題以前做過的題目，如113第6部分排序1.基本概念排序穩(wěn)定的排序方法關(guān)鍵字相等的記錄經(jīng)排序后保持它們原來的前后關(guān)系不穩(wěn)定的排序方法關(guān)鍵字相等的記錄經(jīng)排序后可能改變它們原來的前后關(guān)系第6部分排序1.基本概念114第6部分排序2.插入類排序直接插入排序：每一趟從無序子表中將一個待排的記錄按其關(guān)鍵字大小放到已排好序的子序列的適當(dāng)位置例

47,83,41,53,684747,8341478341475383

4147536