《公共基礎(chǔ)知識(shí)》PPT課件.pptVIP

第1章 數(shù)據(jù)與算法 第2章 程序設(shè)計(jì)基礎(chǔ) 第3章 軟件工程基礎(chǔ) 第4章 數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ),1,公共基礎(chǔ)知識(shí),全國(guó)計(jì)算機(jī)等級(jí)考試,分值：10分，題型：選擇題,1.1 算法 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念 1.3 線性表及其順序存儲(chǔ)結(jié)構(gòu) 1.4 棧和隊(duì)列 1.5 線性鏈表 1.6 樹與二叉樹 1.7 查找技術(shù) 1.8 排序技術(shù),2,第1章 數(shù)據(jù)結(jié)構(gòu)與算法,重點(diǎn)掌握：概念和基本知識(shí)點(diǎn)； 難點(diǎn)內(nèi)容：二叉樹的計(jì)算和遍歷，常用算法的時(shí)間復(fù)雜度等,算法是指解題方案的準(zhǔn)確而完整的描述。 算法是一組明確的可執(zhí)行步驟的有序集合。算法的概念要求步驟集是有序的，這就要求算法中的各個(gè)步驟必須擁有定義完好的順序執(zhí)行結(jié)構(gòu)。 算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。 比如：做一道菜的方法，解一道數(shù)學(xué)題的方法，譜一首歌曲等，都可稱為算法。,3,1.1 算法,1.1.1 算法的基本概念,1.算法的特征： (1) 可行性； (2) 確定性，算法的每一步驟必須有確定的含義，不會(huì)產(chǎn)生二義性； (3) 有窮性，算法必須在有限的時(shí)間完成，步驟是有限的； (4) 有足夠的情報(bào)（數(shù)據(jù)的輸入和輸出）。 由此得到： 算法是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。,4,算法的基本要素： 對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作；算法的控件結(jié)構(gòu) (1)對(duì)數(shù)據(jù)的運(yùn)算和操作 一般的計(jì)算機(jī)系統(tǒng)中，基本的運(yùn)算和操作有： 算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸 (2)算法的控制結(jié)構(gòu) 算法中的操作執(zhí)行的順序 三種基礎(chǔ)結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu),5,2. 算法基本要素,計(jì)算機(jī)解題的過程實(shí)際上是在實(shí)施某種算法，稱為計(jì)算機(jī)算法，常用的計(jì)算機(jī)算法有： （1）列舉法:如，求10000以內(nèi)所有素?cái)?shù)的個(gè)數(shù)。 （2）歸納法：從特殊 一般。比如在買水果的時(shí)候我們往往先嘗一嘗，如果都很甜，就歸納出所要買的水果都很甜的。 （3）遞推法：如求fibonacci(斐波那契)數(shù)列。 （4）遞歸法：如漢諾塔問題。 （5）減半遞推技術(shù)： （6）回溯法 ：,6,3. 算法設(shè)計(jì)的基本方法,評(píng)價(jià)一個(gè)算法一般從正確性、運(yùn)行時(shí)間、占用空間和簡(jiǎn)單性4個(gè)方面進(jìn)行。 算法的運(yùn)行時(shí)間通常用時(shí)間復(fù)雜度表示； 算法占用的空間用空間復(fù)雜度表示。 1.算法的時(shí)間復(fù)雜度（漸近時(shí)間復(fù)雜度）: 為了便于比較同一問題的不同算法，通常是從算法中選取一種對(duì)于所研究的問題來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度。 記作：T(n)=O(f(n) 表示：隨問題規(guī)模N的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率真和f(n)的增長(zhǎng)率相同。,7,1.1.2 算法復(fù)雜度,在同一個(gè)問題規(guī)模下，如果算法執(zhí)行所需的基本運(yùn)算次數(shù)取決于某一特定輸入，可以用以下兩種方法來分析算法的工作量： （1）平均性態(tài):A(n); （2）最壞情況復(fù)雜性：W(n);,8,是對(duì)一個(gè)算法在運(yùn)行過程中所需要的內(nèi)存空間，它是問題規(guī)模n的函數(shù) 。 記作S(n)=O(f(n) 其n為問題的規(guī)模大小。 一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間，包括存儲(chǔ)算法程序本身所占用的存儲(chǔ)空間，算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法在執(zhí)行過程中臨時(shí)占用的存儲(chǔ)空間這三個(gè)方面。,9,2.空間復(fù)雜度,數(shù)據(jù)結(jié)構(gòu)是指： 按照某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的存儲(chǔ)方式把它存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合。即相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 數(shù)據(jù)元素：現(xiàn)實(shí)世界中客觀存在的一切個(gè)體都可以是數(shù)據(jù)元素。如春、夏、秋、冬，字母表字母等。 在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡(jiǎn)單地用前后件關(guān)系（或直接前驅(qū)與直接后繼關(guān)系）來描述。,10,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念,1.2.1什么是數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容： （1）數(shù)據(jù)的邏輯結(jié)構(gòu):數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系； （2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))：各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系； （3）對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。 研究數(shù)據(jù)結(jié)構(gòu)的目的： 提高數(shù)據(jù)處理的效率：一是提高數(shù)據(jù)處理的速度；二是盡量節(jié)省處理過程中所占用的計(jì)算機(jī)存儲(chǔ)空間。,1.數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合，結(jié)構(gòu)實(shí)際上就是指數(shù)據(jù)元素之間的前后件關(guān)系，即數(shù)據(jù)元素的邏輯關(guān)系，而與數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)位置無關(guān)。 一個(gè)數(shù)據(jù)結(jié)構(gòu)包含以下兩個(gè)方面的信息： （1）表示數(shù)據(jù)元素的信息； （2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。 一個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯關(guān)系可表示成： B=(D,R) 其中：B表示數(shù)據(jù)結(jié)構(gòu)，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。 如：一年四季的數(shù)據(jù)結(jié)構(gòu)。 表示為：Season=(D,R) D=春，夏，秋，冬 R=(春，夏),(夏，秋),(秋，冬),12,13,1.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)也稱為數(shù)據(jù)的物理結(jié)構(gòu)。 在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系。 注意：數(shù)據(jù)的邏輯關(guān)系與其存儲(chǔ)結(jié)構(gòu)不同。（如學(xué)號(hào)與入座次序） 常用的存儲(chǔ)結(jié)構(gòu)有：順序、鏈接、索引等。,14,(數(shù)據(jù)結(jié)構(gòu)的表示方法：二元組、圖形表示) 1.2.2數(shù)據(jù)結(jié)構(gòu)的圖形表示 方框：結(jié)點(diǎn) 有向線段：關(guān)系 基本概念： 什么是根結(jié)點(diǎn)，終端結(jié)點(diǎn)，內(nèi)部結(jié)點(diǎn)？,15,1.2.3 線性結(jié)構(gòu)與非線性結(jié)構(gòu) 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間的前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。 如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足以下兩個(gè)條件： 1、有且只有一個(gè)根結(jié)點(diǎn)； 2、每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。 則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，又稱為線性表。,線性結(jié)構(gòu),非線性結(jié)構(gòu),16,1.3 線性表及其順序存儲(chǔ)結(jié)構(gòu),1.3.1線性表的基本概念 （略，P15） 1.3.2線性表的順序存儲(chǔ)結(jié)構(gòu) 在計(jì)算機(jī)中存放線性表，一種最簡(jiǎn)單的方法是順序存儲(chǔ)，也稱為順序分配。 線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)： 1、線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的； 2、線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。,1.4.1 棧及其基本運(yùn)算 1. 什么是棧? 棧一種特殊的線性表，其插入與刪除運(yùn)算只在線性表的一端進(jìn)行,后進(jìn)先出線性表，簡(jiǎn)稱LIFO，棧具有記憶作用。),17,1.4 棧和隊(duì)列,2. 棧的順序存儲(chǔ)及其運(yùn)算 與一般的線性表一樣，用一維數(shù)組S(1：m)作為棧的順序存儲(chǔ)空間，其中m為棧的最大容量。 通常，棧底指針指向?？臻g的低地址一端，在棧的順序存儲(chǔ)空間s(1：m)中，s(bottom)通常為棧底元素，s(top)為棧頂元素。 top=0表示棧空， top=m表示棧滿。 棧的基本運(yùn)算有三種：入棧、退棧、讀棧頂元素。 注意： 什么是“上溢”？什么是“下溢”？,18,迷宮求解是數(shù)據(jù)結(jié)構(gòu)中一個(gè)經(jīng)典的程序設(shè)計(jì)題，一般情況下采用”窮舉求解”的方法，即從迷宮的入口出發(fā)，沿著某一方向前進(jìn)，若能走通則繼續(xù)前進(jìn)，若不通需原路退回后改變方向繼續(xù)前進(jìn)，直到找到出口為止，為了保證在任何位置都可以原路退回，自然使用“?！本褪呛茏匀坏牧恕?19,棧的應(yīng)用：迷宮求解，從入口到出口所有路徑。,1.4.2. 隊(duì)列及其運(yùn)算 1. 什么是隊(duì)列 隊(duì)列是指允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線性表。允許插入的一端為隊(duì)尾，通常用一個(gè)稱為尾指針（Rear)的指針指向隊(duì)尾元素；允許刪除的一端為排頭，通常用一個(gè)排頭指針(Front)指向排頭元素的前一個(gè)位置。 一種運(yùn)算受限的線性表，簡(jiǎn)稱FIFO,如排隊(duì)) 隊(duì)列的先進(jìn)先出示意圖,20,2. 循環(huán)隊(duì)列及其運(yùn)算 在實(shí)際應(yīng)用中，隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式 （P22,略）,21,22,隊(duì)列應(yīng)用：如操作系統(tǒng)中的作業(yè)隊(duì)列 隊(duì)列實(shí)現(xiàn)：,23,1.5 線性鏈表,1.5.1 線性鏈表的基本概念 1. 線性鏈表 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。 為適應(yīng)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，計(jì)算機(jī)存儲(chǔ)空間被劃分為一個(gè)一個(gè)小塊，每一小塊占有若干個(gè)字節(jié)，通常稱為存儲(chǔ)結(jié)點(diǎn)。 為存儲(chǔ)線性表中的每一個(gè)元素，存儲(chǔ)空間中的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分：一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存放下一入數(shù)據(jù)元素的存儲(chǔ)序號(hào)（地址），即指向后件結(jié)點(diǎn)，稱為指針域。,展覽數(shù)據(jù) 后件地址,數(shù)據(jù) 域 指針域,“存儲(chǔ)結(jié)點(diǎn)”圖,24,在線性鏈表中，用一個(gè)專門的指針HEAD指向線性鏈表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。線性鏈表中最后一個(gè)元素沒有后件，因此，線性鏈表中最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭?，用NULL或0表示，表示鏈表終止。 注意： HEAD稱為頭指針，當(dāng)HEAD=NULL（或0）時(shí)稱為空表，如圖所示：,25,31,頭指針H,26,結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映象，包括兩個(gè)域，即數(shù)據(jù)域，指針域。 數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)元素信息。 指針域：存儲(chǔ)的信息為指針或鏈,27,1.5.2 線性鏈表的基本運(yùn)算 1. 在線性鏈表中查找指定元素 2. 線性鏈表的插入 3. 線性鏈表的刪除,28,1.5.3 循環(huán)鏈表及其基本運(yùn)算 1. 什么是循環(huán)鏈表？ 2. 循環(huán)鏈表有什么特點(diǎn)？ 3. 循環(huán)鏈表的好處是什么？,樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次性。 樹(tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集，在任意一棵樹中：(1)有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；(2)當(dāng)n1時(shí)，其余的結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集T1,T2,Tm，其中每一個(gè)集合本身又是一棵樹，稱為根的子樹(Sub Tree) 樹在計(jì)算機(jī)中通常用多重鏈表來表示。,29,1.6 樹與二叉樹,1.6.1 樹的基本概念,30,A,B,C,D,E,F,G,H,I,J,M,L,K,樹的示例,(1)樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干個(gè)指向其子樹的分支。 (2)結(jié)點(diǎn)的度：指結(jié)點(diǎn)擁有的子樹的數(shù)。 (3)葉子或終端結(jié)點(diǎn)：度為0的結(jié)點(diǎn)。 (4)非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)。 (5)內(nèi)部結(jié)點(diǎn)：除根結(jié)點(diǎn)之外的結(jié)點(diǎn)。 (6)樹的度：指樹內(nèi)各結(jié)點(diǎn)的度的最大值。 (7)父結(jié)點(diǎn)：每個(gè)結(jié)點(diǎn)的前件。根結(jié)點(diǎn)：沒有前件的結(jié)點(diǎn)。子結(jié)點(diǎn)：每個(gè)結(jié)點(diǎn)的后件。 (8)兄弟：同一個(gè)雙親的孩子之間互為兄弟。 (9)結(jié)點(diǎn)的層次從根開始定義起，根為第一層，根的孩子為第二層。 (10)堂兄弟：其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。 (11)樹的深度（高度）:樹中結(jié)點(diǎn)的最大層次 (12)如果將樹中結(jié)點(diǎn)的各子樹看成從左到右是有次序的，則該樹為有序樹。 (13)森林：是m(m0)棵互不相交的樹的集合。,31,相關(guān)術(shù)語(yǔ),二叉樹存儲(chǔ)的示意圖,32,1.6.2二叉樹及其基本性質(zhì) 1. 什么是二叉樹 二叉樹是另外一種樹型結(jié)構(gòu)，它的特點(diǎn)是:(1)非空二叉樹只有一個(gè)根結(jié)點(diǎn)；(2)每個(gè)結(jié)點(diǎn)至多只有二棵子樹，分別稱為二叉樹的左子樹和右子樹，其次序不能任意顛倒。,(1)在二叉樹的第k層上至多有2(k-1)個(gè)結(jié)點(diǎn)(k1)。 (2)深度為m的二叉樹至多有2m-1個(gè)結(jié)點(diǎn)(m1)。 (3)對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。 (4)具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為 log2n +1。,33,2.二叉樹的性質(zhì),34,（1）滿二叉樹： 一棵深度為k，且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。 （2）完全二叉樹： 如果從根結(jié)點(diǎn)起，對(duì)二叉樹的結(jié)點(diǎn)自上而下，自左至右用自然數(shù)進(jìn)行連續(xù)編號(hào)，則深度為m的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為m的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹 。 若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹。 如圖所示：,3.滿二叉樹與完全二叉樹質(zhì),35,1,2,3,4,5,6,7,8,10,11,9,12,14,15,13,滿二叉樹,36,1,2,3,4,5,6,7,8,10,11,9,12,完全二叉樹,37,38,1.6.3 二叉樹的存儲(chǔ)結(jié)構(gòu) 在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。也稱為二叉鏈表。 1.6.4 二叉樹的遍歷 二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。 根據(jù)訪問根結(jié)點(diǎn)的次序，二叉樹的遍歷可以分為三種：前序遍歷、中序遍歷、后序遍歷。 1、前序遍歷（DLR）：先根，再左，后右 2、中序遍歷（LDR）：先左，再根，后右 3、后序遍歷（LRD）：先左，再右，后根,39,例：設(shè)一棵完全二叉樹共有700個(gè)結(jié)點(diǎn)，則該二叉樹中有_個(gè)葉子結(jié)點(diǎn)？ 假設(shè)n0是度為0的結(jié)點(diǎn)總數(shù)（即葉子結(jié)點(diǎn)數(shù)），n1是度為1的結(jié)點(diǎn)總數(shù)，n2是度為2的結(jié)點(diǎn)總數(shù)，由二叉樹的性質(zhì)可知：n0n21，則n= n0n1n2（其中n為完全二叉樹的結(jié)點(diǎn)總數(shù)），由上述公式把n2消去得：n= 2n0+n11，由于完全二叉樹中度為1的結(jié)點(diǎn)數(shù)只有兩種可能0或1，由此得到n0（n1）/2或n0n/2，合并成一個(gè)公式：n0?（n1）/2 ?，就可根據(jù)完全二叉樹的結(jié)點(diǎn)總數(shù)計(jì)算出葉子結(jié)點(diǎn)數(shù)。,40,前序遍歷：F，C，A，D，B，E，G，H，P 中序遍歷：A，C，B，D，F(xiàn)，E，H，G，P 后序遍歷：A，B，D，C，H，P，G，E，F(xiàn),41,題目：已知先序遍歷，中序遍歷 建立二叉樹，然后求后序遍歷。 先序：a b d e i j c f g 中序：d b i e j a f c g 后序：?d i j e b f g c a 解法：先序中的首元素a 必為該二叉樹的根結(jié)點(diǎn)，在中序序列里a之前的元素一定是a的左子樹部分，a之后的元素一定為a的右子樹部分。 所以，可以看作，先序： root | 左子樹 | 右子樹 中序： 左子樹 | root | 右子樹,42,1.7 查找技術(shù),1.7.1 順序查找 順序查找又稱順序搜索，一般是指在線性表中查找指定的元素。 順序查找的基本方法：P39（略）； 順序查找次數(shù)：平均情況下約為