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

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