計算機基礎(chǔ)與C語言程序設(shè)計第12章_數(shù)據(jù)結(jié)構(gòu)與算法_第1頁
計算機基礎(chǔ)與C語言程序設(shè)計第12章_數(shù)據(jù)結(jié)構(gòu)與算法_第2頁
計算機基礎(chǔ)與C語言程序設(shè)計第12章_數(shù)據(jù)結(jié)構(gòu)與算法_第3頁
計算機基礎(chǔ)與C語言程序設(shè)計第12章_數(shù)據(jù)結(jié)構(gòu)與算法_第4頁
計算機基礎(chǔ)與C語言程序設(shè)計第12章_數(shù)據(jù)結(jié)構(gòu)與算法_第5頁
已閱讀5頁,還剩66頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

數(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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論