計算機基礎(chǔ)與C語言程序設(shè)計第12章_數(shù)據(jù)結(jié)構(gòu)與算法

數(shù)據(jù)結(jié)構(gòu)與算法 公共基礎(chǔ)知識考試大綱 一、數(shù)據(jù)結(jié)構(gòu)與算法 二、程序設(shè)計基礎(chǔ) 三、軟件工程基礎(chǔ) 四、數(shù)據(jù)庫設(shè)計基礎(chǔ) 包含四部分內(nèi)容： 公共基礎(chǔ)知識考試大綱 1. 掌握算法的基本概念。 2. 掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。 3. 掌握基本排序和查找算法。 4. 掌握逐步求精的結(jié)構(gòu)化程序設(shè)計方法。 5. 掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力。 6. 掌握數(shù)據(jù)庫的基本知識，了解關(guān)系數(shù)據(jù)庫的設(shè)計。 基本要求： 公共基礎(chǔ)知識考試大綱 1. 算法的基本概念；算法復(fù)雜度的概念和意義。 2. 數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。 3. 線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入與刪除運算。 4. 棧和隊列的定義；棧和隊列的順序存儲結(jié)構(gòu)及其基本運算。 數(shù)據(jù)結(jié)構(gòu)與算法考試內(nèi)容： 公共基礎(chǔ)知識考試大綱 5. 線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運算。 6. 樹的基本概念；二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。 7. 順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。 數(shù)據(jù)結(jié)構(gòu)與算法考試內(nèi)容： 一、數(shù)據(jù)結(jié)構(gòu)與算法 用計算機解決實際問題，需要編寫程序。 一個程序應(yīng) 包括兩個方面 ： 數(shù)據(jù)結(jié)構(gòu)（ ，對數(shù)據(jù)的描述，即在程序中要指定 數(shù)據(jù)的類型 和 數(shù)據(jù)的組織形式 ； 算法（ 是對操作的描述，即操作步驟。 這就是著名計算機科學(xué)家沃思（ 出的一個公式： 程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法 一、數(shù)據(jù)結(jié)構(gòu)與算法 考點 1 算法的基本概念 算法（ 是指解題方案的準(zhǔn)確而完整的描述。 算法的基本特征： （ 1）有窮性（ 一個算法應(yīng)包含有限的操作步驟而不能是無限的。 （ 2）確定性（ 算法中的每一個步驟都應(yīng)該是確定的，而不應(yīng)當(dāng)是含糊的、模棱兩可的。 （ 3）可行性（ 一個算法應(yīng)該可以有效地執(zhí)行，即算法描述的每一步都可通過已實現(xiàn)的基本運算執(zhí)行有限次來完成。 法 算法（ 是指解題方案的準(zhǔn)確而完整的描述。 算法的基本特征： （ 4）輸入（ 是指在執(zhí)行算法時需要從外界取得必要的信息。 （ 5）輸出（ 算法的目的是為了求解，“解”就是輸出。一個算法可以有一個或多個輸出。 （ 4）擁有足夠的情報。算法中各種運算總是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點或依據(jù)。 法 考點 1 算法的基本概念 算法的基本要素： 一個算法有 兩個基本要素 ：一個是 對數(shù)據(jù)對象的運算和操作 ，另一個是 算法的控制結(jié)構(gòu) 。 對數(shù)據(jù)對象的運算和操作： 算術(shù)運算： 主要包括加、減、乘、除等運算。 邏輯運算： 主要包括“邏輯與”、“邏輯或”、“邏輯非”等運算。 關(guān)系運算： 主要包括 “大于”、“大于或等于”、“小于”、“小于或等于”、“等于”、“不等于”等運算。 數(shù)據(jù)傳輸： 主要包括賦值、輸入、輸出等操作。 考點 1 算法的基本概念 算法的基本要素： 一個算法有 兩個基本要素 ：一個是 對數(shù)據(jù)對象的運算和操作 ，另一個是 算法的控制結(jié)構(gòu) 。 算法的控制結(jié)構(gòu)： 算法中各種操作之間的執(zhí)行順序稱為 算法的控制結(jié)構(gòu) 。 算法的控制結(jié)構(gòu)給出了算法的基本框架。 描述算法的工具通常有： 傳統(tǒng)流程圖、 N 法描述語言等。 一個算法一般都可以用 順序結(jié)構(gòu) 、 選擇結(jié)構(gòu) 和 循環(huán)結(jié)構(gòu)這三種基本控制結(jié)構(gòu)組合而成。 考點 1 算法的基本概念 算法設(shè)計基本方法： （ 1）列舉法 列舉法就是根據(jù)所要解決的問題，把所有可能的情況都一一列舉出來，并用問題中給定的條件來檢驗?zāi)男┦切枰?，哪些是不需要的?（ 2）歸納法 歸納法的基本思想是通過列舉少量的特殊情況，經(jīng)過分析最后找出一般的關(guān)系。 （ 3）遞推法 遞推法是指從已知的初始條件出發(fā)，逐步推出所要求的結(jié)果。 考點 1 算法的基本概念 算法設(shè)計基本方法： （ 4）遞歸法 在解決某些復(fù)雜問題時，為了降低問題的復(fù)雜程度（如問題的規(guī)模等），可以將問題逐層分解，最后歸結(jié)為一些最簡單的問題。 （ 5）減半遞推法 有些問題的復(fù)雜程度與問題本身的規(guī)模大小有關(guān)。 “減半” 是指將問題的規(guī)模減半，而問題的性質(zhì)不變； “遞推” 是指重復(fù)“減半”的過程。 減半遞推法又稱為 二分法 。 考點 1 算法的基本概念 考點 2 算法復(fù)雜度 算法的復(fù)雜度： （是一個經(jīng)常考查的內(nèi)容，在筆試考試中出現(xiàn)的幾率為70%，此考點為重點識記內(nèi)容。） （ 1）算法的時間復(fù)雜度 算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。 同一個算法用不同的語言實現(xiàn)，或者用不同的編譯程序進(jìn)行編譯，或者在不同的計算機上運行，效率均不同。這表明使用絕對的時間單位衡量算法的效率是不合適的。 算法的時間復(fù)雜度可表示為： 其中 O 表示數(shù)量級， f (n) 是算法的工作量。 O ( f ( n ) )T( n ) 算法的復(fù)雜度： （是一個經(jīng)常考查的內(nèi)容，在筆試考試中出現(xiàn)的幾率為70%，此考點為重點識記內(nèi)容） （ 2）算法的空間復(fù)雜度 算法的空間復(fù)雜度是指執(zhí)行算法所需要的內(nèi)存空間。 一個算法所占用的存儲空間包括算法程序所占用的空間、輸入的初始數(shù)據(jù)所占用的存儲空間以及算法執(zhí)行過程中所需要的額外空間。其中額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間 （例如，在鏈?zhǔn)浇Y(jié)構(gòu)中，除了要存儲數(shù)據(jù)本身外，還需要存儲鏈接信息）。在許多實際問題中，為了減少算法所占的存儲空間，通常采用壓縮存儲技術(shù)，以便盡量減少不必要的額外空間。 考點 2 算法復(fù)雜度 練習(xí) 1： 算法的時間復(fù)雜度是指 _。 A) 執(zhí)行算法程序所需要的時間 B) 算法程序的長度 C) 算法執(zhí)行過程中所需要的基本運算次數(shù) D) 算法程序中的指令條數(shù) 練習(xí) 2： 算法的空間復(fù)雜度是指 _。 A) 算法程序的長度 B) 算法程序中的指令條數(shù) C) 算法程序所占的存儲空間 D) 算法執(zhí)行過程中所需要的存儲空間 C D 考點 2 算法復(fù)雜度 考點 3 數(shù)據(jù)結(jié)構(gòu)的定義 數(shù)據(jù)結(jié)構(gòu) 作為計算機的一門學(xué)科，主要研究和討論以下三個方面： （ 1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的 邏輯結(jié)構(gòu)（ （ 2）在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的 存儲結(jié)構(gòu)（ （ 3）對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的 運算。 數(shù)據(jù)（ 是計算機可以保存和處理的信息。 數(shù)據(jù)元素（ 是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體。有時也把數(shù)據(jù)元素稱作 結(jié)點 、 記錄 等。 據(jù)結(jié)構(gòu)的基本概念 數(shù)據(jù)處理， 是指對數(shù)據(jù)集合中的各元素以各種方式進(jìn)行運算，包括 插入 、 刪除 、 查找 、 更改 等運算，也包括 對數(shù)據(jù)元素進(jìn)行分析 。 數(shù)據(jù)結(jié)構(gòu)（ 是指相互有關(guān)聯(lián)的 數(shù)據(jù)元素 的集合。 例如，向量和矩陣就是數(shù)據(jù)結(jié)構(gòu)，在這兩個數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間有著位置上的關(guān)系。 數(shù)據(jù)元素 的含義非常廣泛，現(xiàn)實世界中存在的一切個體都可以是數(shù)據(jù)元素。 例如，描述一年四季的季節(jié)名“春、夏、秋、冬”，可以作為季節(jié)的數(shù)據(jù)元素；表示家庭成員的名字“父親、兒子、女兒”，可以作為家庭成員的數(shù)據(jù)元素。 考點 3 數(shù)據(jù)結(jié)構(gòu)的定義 數(shù)據(jù)對象： 是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。 1. 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)： 是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述，它可以用一個數(shù)據(jù)元素的集合和定義在此集合中的若干關(guān)系來表示。 數(shù)據(jù)的邏輯結(jié)構(gòu)與它們在計算機中的存儲位置無關(guān) 。 數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素： 一是數(shù)據(jù)元素的集合，通常記為 D； 二是 反映了數(shù)據(jù)元素之間的前后件關(guān)系，通常記為 R。 考點 3 數(shù)據(jù)結(jié)構(gòu)的定義 一個數(shù)據(jù)結(jié)構(gòu)可以表示成 B=（ D， R） 其中 B 表示數(shù)據(jù)結(jié)構(gòu)。為了反映 D 中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。 例 一年四季的數(shù)據(jù)結(jié)構(gòu)可以表示成 B =（ D， R） D = 春，夏，秋，冬 R = （春，夏），（夏，秋），（秋，冬） 例 家庭成員數(shù)據(jù)結(jié)構(gòu)可以表示成 B =（ D， R） D = 父親，兒子，女兒 R = （父親，兒子），（父親，女兒） 考點 3 數(shù)據(jù)結(jié)構(gòu)的定義 2數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)， 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)（也稱 數(shù)據(jù)的物理結(jié)構(gòu) ）。 由于數(shù)據(jù)元素在計算機存儲空間中的位置關(guān)系可能與邏輯關(guān)系不同，因此，為了表示存放在計算機存儲空間中的各數(shù)據(jù)元素之間的邏輯關(guān)系（即前后件關(guān)系），在數(shù)據(jù)的存儲結(jié)構(gòu)中， 不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息 。 考點 3 數(shù)據(jù)結(jié)構(gòu)的定義 2數(shù)據(jù)的存儲結(jié)構(gòu) 一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有， 順序 、 鏈接 、索引 等存儲結(jié)構(gòu)。 順序存儲 ，它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為 順序存儲結(jié)構(gòu) 。 鏈接存儲 ，它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲表示稱為 鏈?zhǔn)酱鎯Y(jié)構(gòu) 。 索引存儲 ，除建立存儲結(jié)點信息外，還建立附加的索引表來標(biāo)識結(jié)點的地址。 考點 3 數(shù)據(jù)結(jié)構(gòu)的定義 3. 數(shù)據(jù)結(jié)構(gòu)的圖形表示 春 冬秋夏父親女兒兒子在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對于數(shù)據(jù)集合 之為數(shù)據(jù)結(jié)點，簡稱 結(jié)點 。 對于關(guān)系 一條有向線段從前件結(jié)點指向后件結(jié)點。 在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點稱為 根結(jié)點 ； 沒有后件的結(jié)點稱為 終端結(jié)點 （也稱為 葉子 結(jié)點）。 考點 3 數(shù)據(jù)結(jié)構(gòu)的定義 考點 4 線性結(jié)構(gòu)與非線性結(jié)構(gòu) 4. 線性結(jié)構(gòu)與非線性結(jié)構(gòu) 一個數(shù)據(jù)結(jié)構(gòu)可以是空的，即一個數(shù)據(jù)元素都沒有，稱為 空的數(shù)據(jù)結(jié)構(gòu) 。 一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類： 線性結(jié)構(gòu) 與 非線性結(jié)構(gòu) 。 線性結(jié)構(gòu)， 如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下面兩個條件： （ 1）有且只有一個根結(jié)點；（ 2）每個結(jié)點最多有一個前件，也最多有一個后件。則稱該數(shù)據(jù)結(jié)構(gòu)為 線性結(jié)構(gòu) 。 線性結(jié)構(gòu)又稱 線性表 。 4. 線性結(jié)構(gòu)與非線性結(jié)構(gòu) 如一年四季這個數(shù)據(jù)結(jié)構(gòu)屬于線性結(jié)構(gòu)。 需要說明的是，在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還應(yīng)是線性結(jié)構(gòu)。 非線性結(jié)構(gòu) ，如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱為非線性結(jié)構(gòu)。 如 家庭成員之間輩分關(guān)系的數(shù)據(jù)結(jié)構(gòu)是非線性結(jié)構(gòu)。 考點 4 線性結(jié)構(gòu)與非線性結(jié)構(gòu) 考點 5 線性表的基本概念 線性表（ 由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。 線性表是由 n(n0) 個數(shù)據(jù)元素組成的一個有限序列， 表中的每一個數(shù)據(jù)元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。 線性表中數(shù)據(jù)元素的個數(shù)稱為 線性表的長度 。 線性表可以為空表。 線性表及其順序存儲結(jié)構(gòu) 線性表的順序存儲結(jié)構(gòu)， 用順序存儲結(jié)構(gòu)來存儲的線性表也稱為順序表。其特點如下： （ 1）順序表中所有元素所占的存儲空間是連續(xù)的； （ 2）順序表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。 在順序表中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面。 線性表及其順序存儲結(jié)構(gòu) 考點 5 線性表的基本概念 順序表的插入、刪除運算 （ 1）順序表的插入運算： 在一般情況下，要在第 i（ 1in）個元素之前插入一個新元素時，首先要從最后一個（即第 素開始，直到第 i 個元素之間共 個元素依次向后移動一個位置，移動結(jié)束后，第 i 個位置就被空出，然后將新元素插入到第 i 項。插入結(jié)束后，線性表的長度就增加了 1。 順序表的插入運算時需要移動元素，在等概率情況下，平均需要移動 n/2 個元素。 考點 5 線性表的基本概念 順序表的插入、刪除運算 （ 2）順序表的刪除運算： 在一般情況下，要刪除第 i（ 1in）個元素時，則要從第 i+1個元素開始，直到第 元素依次向前移動一個位置。刪除結(jié)束后，線性表的長度就減小了 1。 進(jìn)行順性表的刪除運算時也需要移動元素，在等概率情況下，平均需要移動 （ 。 順序表的插入、刪除運算效率很低。 考點 5 線性表的基本概念 1棧的基本概念 棧（ 是一種特殊的線性表，它是限定僅在一端進(jìn)行插入和刪除運算的線性表。 其中，允許插入與刪除的一端稱為 棧頂（ 而不允許插入與刪除的另一端稱為 棧底（ 棧頂元素總是最后被插入的那個元素，從而也是最先能被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。 棧是按照“ 先進(jìn)后出”（ n “ 后進(jìn)先出”（ n 原則操作數(shù)據(jù)的。由此可以看出， 棧具有記憶作用 。 考點 6 棧和隊列 棧和隊列 2棧的順序存儲及基本運算 棧的順序存儲結(jié)構(gòu)是利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，并設(shè)有指針 向棧頂元素的位置。 用一維數(shù)組 S（ 1 m）作為棧的順序存儲空間，其中 在棧的順序存儲空間 S（ 1 m）中， S（ 棧底元素， S（ 棧頂元素。 0表示棧空； m 表示棧滿。 棧的基本運算有三種： 入棧 、 退棧 與 讀棧頂元素 。 考點 6 棧和隊列 棧和隊列 （ 1）入棧運算 ：入棧運算是指在棧頂位置插入一個新元素。首先將棧頂指針加一（即 ），然后將新元素插入到棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲空間的最后一個位置時，說明?？臻g已滿，不可能再進(jìn)行入棧操作。這種情況稱為棧 上溢 錯誤。 （ 2）退棧運算： 退棧是指取出棧頂元素并賦給一個指定的變量。首先將棧頂元素（棧頂指針指向的元素）賦給一個指定的變量，然后將棧頂指針減一（即 ）。當(dāng)棧頂指針為 0時，說明?？眨豢蛇M(jìn)行退棧操作。這種情況稱為棧的 下溢 錯誤。 （ 3）讀棧頂元素： 讀棧頂元素是指將棧頂元素賦給一個指定的變量。這個運算不刪除棧頂元素，只是將它賦給一個變量，因此棧頂指針不會改變。當(dāng)棧頂指針為 0時，說明棧空，讀不到棧頂元素。 考點 6 棧和隊列 3隊列的基本概念 隊列（ 是一種特殊的線性表，它是限定僅在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除的線性表。 在隊列中，允許插入的一端稱為 隊尾 ，允許刪除的一端稱為 隊頭 。 隊列是按照 “先進(jìn)先出”（ n “ 后進(jìn)后出”（ n 原則操作數(shù)據(jù)的，因此，隊列也被稱為“先進(jìn)先出”表或“后進(jìn)后出”表。 在隊列中，通常用指針 向隊頭 ，用 考點 6 棧和隊列 3隊列的基本概念 隊列的基本運算有兩種： 往隊列的隊尾插入一個元素稱為 入隊運算 ，從隊列的隊頭刪除一個元素稱為出隊運算 。 在隊列的末尾插入一個元素（ 入隊運算 ）只涉及隊尾指針 變化，而要刪除隊列中的隊頭元素（ 出隊運算） 只涉及隊頭指針 與棧類似，在程序設(shè)計語言中，用一維數(shù)組作為隊列的順序存儲空間。 用順序存儲結(jié)構(gòu)存儲的隊列稱為 順序隊列 。 考點 6 棧和隊列 4循環(huán)隊列及其運算 循環(huán)隊列（ 為了充分利用存儲空間，在實際應(yīng)用中，隊列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊列的形式，將順序存儲的隊列的最后一個位置指向第一個位置，從而使順序隊列形成邏輯上的環(huán)狀空間，稱為 循環(huán)隊列（ 在循環(huán)隊列中，用隊尾指針 向隊列中的隊尾元素，用排頭指針 向排頭元素的前一個位置，因此，從頭指針 有的元素均為隊列中的元素。 循環(huán)隊列中元素的個數(shù) = 考點 6 棧和隊列 4循環(huán)隊列及其運算 循環(huán)隊列主要有兩種基本運算： 入隊運算 與 出隊運算 。 每進(jìn)行一次 出隊運算 ，隊頭指針就加 1。當(dāng)隊頭指針 n+1時，則設(shè)置 。 每進(jìn)行一次 入隊運算 ，隊尾指針就加 1。當(dāng)隊尾指針 n+1時，則設(shè)置 。 隊列空與隊列滿的條件： 隊列空的條件為 ； 隊列滿的條件為 l，且 考點 6 棧和隊列 1 線性鏈表的基本概念 在鏈?zhǔn)酱鎯Ψ绞街?，要?每個結(jié)點由兩部分組成 ：一部分用于存放數(shù)據(jù)元素值，稱為 數(shù)據(jù)域 ，另一部分用于存放指針，稱為 指針域 。其中指針用于指向該結(jié)點的前一個或后一個結(jié)點（即前件或后件）。 鏈?zhǔn)酱鎯Ψ绞郊瓤捎糜诒硎揪€性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。 （ 1）線性鏈表 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為 線性鏈表 。 考點 7 線性鏈表的基本概念 線性鏈表 在線性鏈表中，一般用一個專門的指針 用 在線性表中，最后一個元素沒有后件，所以，線性鏈表中最后一個結(jié)點的指針域為空（用 0表示）， 表示鏈表終止 。 考點 7 線性鏈表的基本概念 線性鏈表 線性鏈表的存儲結(jié)構(gòu) 設(shè)有 4個學(xué)生的某門功課的成績分別是 4 個數(shù)據(jù)在內(nèi)存中的存儲單元地址分別是 1248、 1488、1366 和 1522，其鏈表結(jié)構(gòu)如圖 a 所示。實際上，常用圖 b 來表示它們的邏輯關(guān)系。 1248a 1148813661366a 315221522a 4 線性鏈表的基本概念 圖 a 線性鏈表的物理狀態(tài) 圖 b 線性鏈表的邏輯狀態(tài) a 1a 2 a 3 雙向鏈表 的存儲結(jié)構(gòu) 在一些應(yīng)用中，對線性鏈表中的每個結(jié)點 設(shè)置兩個指針域 ，一個指向其前件結(jié)點，稱為 前件指針或 左指針 ；另一指向其后件結(jié)點，稱為 后件指針 或右指針 。 這樣的線性鏈表稱為 雙向鏈表 ，其邏輯狀態(tài)如圖所示。 考點 7 線性鏈表的基本概念 圖 雙向線性鏈表的物理狀態(tài) （ 2） 帶鏈的棧 用鏈?zhǔn)酱鎯Y(jié)構(gòu)來存儲的棧，稱為 帶鏈的棧 ，簡稱為 鏈棧。 考點 7 線性鏈表的基本概念 圖 棧在鏈?zhǔn)酱鎯r的邏輯狀態(tài)示意圖 a a （ 3） 帶鏈的隊列 用鏈?zhǔn)酱鎯Y(jié)構(gòu)來存儲的隊列，稱為 帶鏈的隊列 ，簡稱為 鏈隊列 。 考點 7 線性鏈表的基本概念 圖 隊列在鏈?zhǔn)酱鎯r的邏輯狀態(tài)示意圖 在鏈?zhǔn)浇Y(jié)構(gòu)中，存儲空間位置關(guān)系與邏輯關(guān)系是什么？ 在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。 考點 7 線性鏈表的基本概念 考點 7 線性鏈表的基本概念 2 線性鏈表的基本運算 （ 1）在線性鏈表中包含指定元素的結(jié)點之前 插入一個新元素 。 在線性鏈表中插入元素時，不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點指針即可，也不會出現(xiàn)“上溢”現(xiàn)象。 例 假設(shè)線性鏈表如圖（ a）所示?，F(xiàn)在要在線性鏈表中包含元素 a 的結(jié)點之前插入一個包含新元素 插入過程如下： 考點 7 線性鏈表的基本概念 a a a）原來的線性鏈表 （ b）申請一個由 （ d）將新結(jié)點插入到指定結(jié)點之前 （ c）在線性鏈表中找到由 a 線性鏈表的基本概念 2 線性鏈表的基本運算 （ 2）在線性鏈表中刪除包含指定元素的結(jié)點。 在線性鏈表中刪除元素時，也不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點指針即可。 （ 3）將兩個線性鏈表按要求合并成一個線性鏈表。 （ 4）將一個線性鏈表按要求進(jìn)行分解。 （ 5）逆轉(zhuǎn)線性鏈表。 （ 6）復(fù)制線性鏈表。 考點 7 線性鏈表的基本概念 2 線性鏈表的基本運算 （ 7）線性鏈表的排序。 （ 8）線性鏈表的查找。 注：線性鏈表不能隨機存取。 在鏈表中，即使知道被訪問結(jié)點的序號 i，也不能像順序表中那樣直接按序號 i 訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順著鏈域逐個結(jié)點往下搜索，直至搜索到第 i 個結(jié)點為止。 因此， 鏈表不是隨機存儲結(jié)構(gòu) 。 考點 7 線性鏈表的基本概念 3循環(huán)鏈表 循環(huán)鏈表（ 結(jié)構(gòu)具有下面兩個特點： （ 1）在循環(huán)鏈表中 增加了一個表頭結(jié)點 。表頭結(jié)點的數(shù)據(jù)域為任意或者根據(jù)需要來設(shè)置，指針域指向線性表的第一個元素的結(jié)點。 循環(huán)鏈表的頭指針指向表頭結(jié)點 。 （ 2）循環(huán)鏈表中 最后一個結(jié)點的指針域不是空的，而是指向表頭結(jié)點 。即在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈 考點 7 線性鏈表的基本概念 3循環(huán)鏈表 下圖為循環(huán)鏈表的邏輯狀態(tài)示意圖，圖（ a）是一個非空的循環(huán)鏈表，圖（ b）是一個空的循環(huán)鏈表。 a a 1表頭結(jié)點（ a）非空循環(huán)鏈表 （ b）空循環(huán)鏈表 樹與二叉樹及其基本性質(zhì) 1 樹的基本概念 樹 ( 是一種簡單的非線性結(jié)構(gòu)。 在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為 父結(jié)點 ，沒有前件的結(jié)點只有一個，稱為樹的 根結(jié)點 。 每一個結(jié)點可以有多個后件，它們稱為該結(jié)點的 子結(jié)點 。沒有后件的結(jié)點稱為 葉子結(jié)點 。 一個結(jié)點所擁有的后件個數(shù)稱為該 結(jié)點的度 。 葉子結(jié)點的度為 0。 在樹中，所有結(jié)點中的最大的度稱為樹的度 。樹的最大層次稱為 樹的深度。 樹與二叉樹 在筆試考試中，一般是一個必考的內(nèi)容，出現(xiàn)的幾率為100%，此考點為重點掌握內(nèi)容。重點識記樹及二叉樹的性質(zhì)。 考點 8 樹與二叉樹及其基本性質(zhì) 根結(jié)點 : 父結(jié)點 : 除根結(jié)點外，每個結(jié)點只有一個前件，稱為該結(jié)點的父結(jié)點。 葉子結(jié)點 : 節(jié)點的度數(shù)： 根結(jié)點 ； ； ； ；葉子結(jié)點的度為 0。 樹的度： G H I 樹的結(jié)構(gòu)圖 A E、 F、 G、 H、 I、 J 3。 3。 樹的深度： 考點 8 樹與二叉樹及其基本性質(zhì) 2 二叉樹及其基本運算 二叉樹（ 是一種非常有用的非線性數(shù)據(jù)結(jié)構(gòu)。 二叉樹與前面介紹的樹結(jié)構(gòu)不同，但它與樹結(jié)構(gòu)很相似，并且，有關(guān)樹結(jié)構(gòu)的所有術(shù)語都可以用到二叉樹上。 二叉樹的特點： 非空二叉樹只有一個根結(jié)點； 每個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的 左子樹 與 右子樹 。 考點 8 樹與二叉樹及其基本性質(zhì) 在二叉樹中，每個結(jié)點的度最大為 2，而樹結(jié)構(gòu)中的每一個結(jié)點的度可以是任意的。另外，二叉樹中的每一個結(jié)點的子樹要區(qū)分為左子樹與右子樹。 例如，下圖中所示的是 4 顆不同的二叉樹。 樹與二叉樹及其基本性質(zhì) 滿二叉樹與完全二叉樹： （ 1）滿二叉樹 在一顆二叉樹中，如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子結(jié)點都在同一層上，這樣的二叉樹稱為滿二叉樹。下圖分別是深度為 2、 3的滿二叉樹。 樹與二叉樹及其基本性質(zhì) 滿二叉樹與完全二叉樹： （ 2） 完全二叉樹 完全二叉樹是指除最后一層外，每一層上的結(jié)點數(shù)均達(dá)到最大值，而在最后一層上只缺少右邊的若干結(jié)點。 下圖是兩顆深度為 3的完全二叉樹。 考點 8 樹與二叉樹及其基本性質(zhì) 二叉樹的基本性質(zhì)： 性質(zhì) 1 在二叉樹中，第 i1）。 性質(zhì) 2 在深度為 點總數(shù)最多為 2k1）。 性質(zhì) 3 對任意一棵二叉樹，度為 0的結(jié)點（即葉子結(jié)點）總是比度為 2的結(jié)點多一個。 性質(zhì) 4 （ 1）具有 深度至少為1，其中 示取 （ 2）具有 1。 考點 8 樹與二叉樹及其基本性質(zhì) 二叉樹的基本性質(zhì)： 性質(zhì) 5 如果對一棵有 到 一層從左到右）編號，則 對任一結(jié)點 i(1in)，有 （ 1）如果 i=1，則結(jié)點 沒有父結(jié)點；如果 i1，則其父結(jié)點編號為 i/2。 （ 2）如果 2in，則結(jié)點 點 否則，其左子結(jié)點是結(jié)點 2i。 （ 3）如果 2i+1n，則結(jié)點 則，其右子結(jié)點是結(jié)點 2i+1。 根據(jù)完全二叉樹的這個性質(zhì)，如果按從上到下、從左到右順序存儲完全二叉樹的各結(jié)點，則很容易確定每一個結(jié)點的父結(jié)點、左子結(jié)點和右子結(jié)點的位置。 考點 8 樹與二叉樹及其基本性質(zhì) 3 二叉樹的存儲結(jié)構(gòu) 在計算機中， 二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu) 。 與線性鏈表類似，用于存儲二叉樹中各元素的存儲結(jié)點也 由兩部分組成 ： 數(shù)據(jù)域 和 指針域 。 但在二叉樹中，由于每一個元素可以有兩個后件（即兩個子結(jié)點），因此，用于存儲二叉樹的存儲結(jié)點的指針域有兩個： 一個用于指向該結(jié)點的左子結(jié)點的存儲地址，稱為 左指針域 ；另一個用于指向該結(jié)點的右子結(jié)點的存儲地址，稱為 右指針域 。 考點 8 樹與二叉樹及其基本性質(zhì) 3 二叉樹的存儲結(jié)構(gòu) 下圖是二叉樹存儲結(jié)點的示意圖。其中： L(i)是結(jié)點 即 L(i)為結(jié)點 R(i)是結(jié)點 即 R(i)為結(jié)點 V(i)是數(shù)據(jù)域 。 L(i) V(i) R(i) 樹與二叉樹及其基本性質(zhì) 3 二叉樹的存儲結(jié)構(gòu) 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)也稱為二叉鏈表。下圖表示二叉鏈表的存儲示意圖。 0 0 0 E 0頭指針對于滿二叉樹與完全二叉樹來說，可按層序進(jìn)行順序存儲。 這樣，不僅節(jié)省存儲空間，又方便確定每個結(jié)點的父結(jié)點與左右子結(jié)點的位置，但順序存儲結(jié)構(gòu)對于一般的二叉樹不適用。 考點 8 樹與二叉樹及其基本性質(zhì) 4 二叉樹的遍歷 二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點。 在遍歷二叉樹的過程中，通常規(guī)定： 先遍歷左子樹，然后再遍歷右子樹 。 在先左后右的原則下，根據(jù) 訪問根結(jié)點的次序，二叉樹的遍歷可以分為三種： 前序遍歷 、 中序遍歷 、 后序遍歷 。 用 D、 L、 “ 訪問根結(jié)點 ”、“ 遍歷根結(jié)點的左子樹 ” 和 “ 遍歷根結(jié)點的右子樹 ”。 考點 8 樹與二叉樹及其基本性質(zhì) 4 二叉樹的遍歷 （ 1）前序遍歷（ 若二叉樹為空，則結(jié)束返回。否則：首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。 H 則遍歷的結(jié)果為： 考點 8 樹與二叉樹及其基本性質(zhì) 4 二叉樹的遍歷 （ 2）中序遍歷（ 若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。 H 則遍歷的結(jié)果為： 考點 8 樹與二叉樹及其基本性質(zhì) 4 二叉樹的遍歷 （ 3）后序遍歷（ 若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。 H 則遍歷的結(jié)果為： 考點 9 順序查找 1 順序查找 順序查找 又稱為 順序搜索 ，基本方法是： 從線性表的第一個元素開始，依次與被查找元素進(jìn)行比較，若相等則查找成功；若所有的元素都與被查元素進(jìn)行了比較，都不相等，則查找失敗。 在下列兩種情況下也只能采用順序查找： （ 1）如果線性表為無序表，則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，只能用順序查找。 （ 2）即使是有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用順序查找。 順序查找一個 平均復(fù)雜度為 O（ n）。 查找技術(shù) 考點 10 二分法查找 2 二分法查找 二分法 只適用于順序存儲的，按非遞減排列的有序表，其方法如下： 設(shè)有序線性表的長度為 n，被查找的元素為 i， （ 1）將 i 與線性表的中間項進(jìn)行比較； （ 2）若 i 與中間項的值相等，則查找成功； （ 3）若 i