《數(shù)據(jù)結(jié)構(gòu)課件(清華版).ppt》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)課件(清華版).ppt（539頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)Data Structure 河南大學(xué)計算機與信息工程學(xué)院 83,學(xué) 分： 5 教 材：嚴(yán)蔚敏等，數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社，1997年4月 參考書： 1 殷人昆等，數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+描述），清華大學(xué)出版社，1999年7月。￥26 2 殷人昆等，數(shù)據(jù)結(jié)構(gòu)習(xí)題解析，清華大學(xué)出版社，2002年4月。￥26 3 李春葆，數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析（C語言篇），清華大學(xué)出版社，2001年1月。￥28 4 嚴(yán)蔚敏等，數(shù)據(jù)結(jié)構(gòu)題集(C語言版)，清華大學(xué)出版社， 1997年4月。￥16,內(nèi) 容 安 排,注：本學(xué)期共85學(xué)時，機動5學(xué)時。,第1章 序 論,1.1 什么是數(shù)據(jù)結(jié)構(gòu) 1.2

2、基本概念和術(shù)語 1.3 抽象數(shù)據(jù)類型的表示和實現(xiàn) 1.4 算法和算法分析,作業(yè),5,1.1 什么是數(shù)據(jù)結(jié)構(gòu),Q1 如何采用計算機解決問題？ Q2 數(shù)據(jù)結(jié)構(gòu)解決什么樣的問題？ Q3 數(shù)據(jù)結(jié)構(gòu)課程介紹,6,Q1：如何采用計算機解決問題？,答：,尋求數(shù)學(xué)模型的實質(zhì)： 分析問題，從中提取操作的對象，并找出這些 操作對象之間含有的關(guān)系，然后用數(shù)學(xué)的語言加以 描述。,(2) 設(shè)計解此數(shù)學(xué)模型的算法；,(1) 從具體問題抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型；,(3) 編程，測試、調(diào)整直至得到最終解答。,7,Q2：數(shù)據(jù)結(jié)構(gòu)解決什么樣的問題？,答：,數(shù)據(jù)結(jié)構(gòu)研究非數(shù)值計算的程序設(shè)計問 題中計算機的操作對象以及它們之間的關(guān)系

3、 和操作等的學(xué)科。,8,介于數(shù)學(xué)、計算機硬件和計算機軟件三者之間的一門核心課程,關(guān)系,對象 關(guān)系 操作,對象 關(guān)系 操作,Q3：數(shù)據(jù)結(jié)構(gòu)課程介紹,1.2 基本概念和術(shù)語,Q1 什么是數(shù)據(jù)結(jié)構(gòu)？ Q2 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用？ Q3 數(shù)據(jù)結(jié)構(gòu)涵蓋的主要內(nèi)容？,討論：,Q1：什么是數(shù)據(jù)結(jié)構(gòu)？,答: (見教材P5) 是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，表示為：,（數(shù)值或非數(shù)值）,Data_Structure=（D, S）,或：是指同一數(shù)據(jù)元素類中各元素之間存在的關(guān)系。,亦可表示為：S（D, R） 或 B=（K, R）,元素有限集,關(guān)系有限集,術(shù)語：數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項,（見教材P4定義

4、）： 數(shù)據(jù)(data)所有能被計算機識別、存儲和處理的符號的集合（包括數(shù)字、字符、聲音、圖像等信息 ）。 數(shù)據(jù)元素(data element)是數(shù)據(jù)的基本單位，具有完整確定的實際意義(又稱元素、結(jié)點，頂點、記錄等）。 數(shù)據(jù)項(Data item)構(gòu)成數(shù)據(jù)元素的項目。是具有獨立含義的最小標(biāo)識單位（又稱字段、域、屬性 等）。,三者之間的關(guān)系：數(shù)據(jù) 數(shù)據(jù)元素 數(shù)據(jù)項,例：班級通訊錄 個人記錄 姓名、年齡,Q2：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用？,答：計算機內(nèi)的數(shù)值運算依靠方程式，而非數(shù)值運算（如表、樹、圖等）則要依靠數(shù)據(jù)結(jié)構(gòu)。 這是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等等的

5、學(xué)科。,程序設(shè)計實質(zhì)好算法好結(jié)構(gòu),同樣的數(shù)據(jù)對象，用不同的數(shù)據(jù)結(jié)構(gòu)來表示，運算效率可能有明顯的差異。,Q3：數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容？,解釋1： 什么叫數(shù)據(jù)的邏輯結(jié)構(gòu)？,答：指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。邏輯結(jié)構(gòu)可細(xì)分為4類：,集合結(jié)構(gòu)： 僅同屬一個集合 線性結(jié)構(gòu): 一對一（1:1) 樹 結(jié) 構(gòu): 一對多（1:n) 圖 結(jié) 構(gòu): 多對多 (m:n),非線性,線 性,例：用圖形表示下列數(shù)據(jù)結(jié)構(gòu)，并指出它 們是屬于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)。,（1） S=(D, R) D= a, b, c, d, e, f R=(a,e), (b,c), (c,a)

6、, (e,f), (f,d),解： 上述表達(dá)式可用圖形表示為：,b c a e f d,此結(jié)構(gòu)為線性的。,（2） S=(D, R) D=di | 1i5 R=(di , dj ), ij,d1 d5 d2 d4 d3,該結(jié)構(gòu)是非線性的。,解：上述表達(dá)式可用圖形表示為：,解釋2：什么叫數(shù)據(jù)的物理結(jié)構(gòu)？,答：物理結(jié)構(gòu)亦稱存儲結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器內(nèi)的表示（或映像）。它依賴于計算機。,存儲結(jié)構(gòu)可分為4大類：,例：（見教材P6）復(fù)數(shù)3.02.3i 的兩種存儲方式：,順序、鏈?zhǔn)?、索引、散?法1：地址 內(nèi)容,法2：地址 內(nèi)容,2字節(jié),解釋3：什么是數(shù)據(jù)的運算？,答：在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的

7、操作算法。 它在數(shù)據(jù)的存儲結(jié)構(gòu)上實現(xiàn)。,最常用的數(shù)據(jù)運算有5種：,插入、刪除、修改、查找、排序,1.3 抽象數(shù)據(jù)類型的表示和實現(xiàn),Q1 數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別？ Q2 抽象數(shù)據(jù)類型如何定義？ Q3 抽象數(shù)據(jù)類型如何表示和實現(xiàn)？,討論：,提示：教材中例1-6和例1-7分別給出了抽象數(shù)據(jù)類型“三元組”的定義、表示和實現(xiàn)，請試閱讀。,Q1 數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別？,數(shù)據(jù)類型：是一個值的集合和定義在該值上 的一組操作的總稱。,抽象數(shù)據(jù)類型：由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。它由基本的數(shù)據(jù)類型構(gòu)成，并包括一組相關(guān)的服務(wù)（或稱操作）,它與數(shù)據(jù)類型實質(zhì)上是一個概念，但其特征是使用與實現(xiàn)分離

8、，實行封裝和信息隱蔽（獨立于計算機）。,Q2 抽象數(shù)據(jù)類型如何定義？,抽象數(shù)據(jù)類型可以用以下的三元組來表示： ADT = （D，S，P） 數(shù)據(jù)對象 D上的關(guān)系集 D上的操作集,ADT抽象數(shù)據(jù)類型名 數(shù)據(jù)對象： 數(shù)據(jù)關(guān)系： 基本操作 ： ADT抽象數(shù)據(jù)類型名,ADT常用定義格式,例：給出自然數(shù)(Natural Number )的抽象數(shù)據(jù)類型定義。,ADT Natural_Number is objects: 一個整數(shù)的有序子集合，它開始于0，結(jié)束于機器能表示的最大整數(shù) (MAX INT) functions: 對于所有的 x, y Natural_Number； TRUE, FALSE Bool

9、ean； +, -, , = = ,=等都是可用的服務(wù)。 Zero ( )： Natural Number 返回 0 IsZero(x)： Boolean if (x=0) 返回TRUE else 返回 FALSE Add(x, y)： Natural Number if (x+y = MAX INT)返回 x+y else 返回MAX INT Subtract(x,y): Natural Number if (xy)返回0 else 返回x-y Equal(x,y): Boolean if (x= y)返回TRUE else 返回FALSE Successor(x) : Natural Nu

10、mber if (x = MAX INT)返回x else 返回x+1 end Natural_Number,Q3 抽象數(shù)據(jù)類型如何表示和實現(xiàn)？,抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型 （如整型、實型、字符型等）來表示和實現(xiàn)。 即利用處理器中已存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實現(xiàn)的操作來組合新的操作。,注 ：教材中用的是類C語言（介于偽碼和C語言之間） 作為描述工具。其描述語法見P10-11。,但上機時要用具體語言實現(xiàn)，如C或C+等,1.4 算法和算法分析,Q1. 什么是算法？ Q2. 算法設(shè)計的要求？ Q3. 時間復(fù)雜度如何表示？ Q4. 空間復(fù)雜度如何表示？,討論：,答：算法是解決某一特定

11、類型問題的有限運算 序列。是一系列輸入轉(zhuǎn)換為輸出的計算步 驟。,Q1. 什么是算法？,算法有5個基本特性：,有窮性、確定性、可行性、輸入和輸出,26,Q2. 算法設(shè)計的要求？,答：,(1) 正確性,(2) 可讀性,(3) 健壯性,(4) 效率與低存儲需求,時間復(fù)雜度T(n)按數(shù)量級遞增順序為：,注1 O（）為漸近符號。 注2 空間復(fù)雜度S(n)按數(shù)量級遞增順序也與上表類同。,復(fù)雜度高,復(fù)雜度低,Q3. 時間復(fù)雜度如何表示？,漸進(jìn)符號（O）的定義：當(dāng)且僅當(dāng)存在一個正的常數(shù) C，使得對所有的 n n0 ，有 f(n) Cg(n)， 則f(n) = O(g(n),3n+2=O(n) /* 3n+24

12、n for n2 */ 3n+3=O(n) /* 3n+34n for n3 */ 100n+6=O(n) /* 100n+6101n for n10 */ 10n2+4n+2=O(n2) /* 10n2+4n+211n2 for n5 */ 6*2n+n2=O(2n) /* 6*2n+n2 7*2n for n4 */,例：,例：分析以下程序段的時間復(fù)雜度。,i=1; while(i=n) i=i*2; ,該算法的運行時間由算法中所有語句的頻度（即該語句重復(fù)執(zhí)行的次數(shù)）之和構(gòu)成。,解：,分析：顯然，語句的頻度是1。設(shè)語句2的頻度是f(n)，則有：,即f(n)log2n，取最大值f(n)=lo

13、g2n,所以該程序段的時間復(fù)雜度T(n)=1+f(n)=1+ log2n= O( log2n),算法的時間復(fù)雜度是由嵌套最深層語句的頻度決定的。,30,Q4. 空間復(fù)雜度如何表示？,S(n) = O(f(n),一個上機執(zhí)行的程序除了需要存儲空間來寄存本身所用指令、常數(shù)、變量和輸入數(shù)據(jù)外，也需要一些對數(shù)據(jù)進(jìn)行操作的工作單元和存儲一些為實現(xiàn)計算所需信息的輔助空間。,原地工作：若額外空間相對于輸入數(shù)據(jù)量來說是常 數(shù)，則稱此算法為原地工作。,注：若額外空間所占空間量依賴于特定的輸入，則除 特別指明外，均按最壞情況來分析。,作業(yè)：,思考:數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型的區(qū)別 算法與程序的區(qū)別 2. 請

14、試做配套習(xí)題集(P10_16)。 3. 復(fù)習(xí)C+語言。,32,上堂課要點回顧,數(shù)據(jù)結(jié)構(gòu)課程涉及數(shù)學(xué)、計算機硬件和計算機軟件 數(shù)據(jù)結(jié)構(gòu)定義指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合，用D_S=( D, S ) 或 S=( D, R) 表示。 數(shù)據(jù)結(jié)構(gòu)內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算 算法效率指標(biāo)時間效率和空間效率,33,數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容,邏輯結(jié)構(gòu)唯一 存儲結(jié)構(gòu)不唯一 運算的實現(xiàn)依賴于存儲結(jié)構(gòu),34,近3周上課內(nèi)容,第2章 線性表 第3章 棧和隊列 第4章 串 第5章 數(shù)組和廣義表,線性結(jié)構(gòu),若結(jié)構(gòu)是非空有限集，則有且僅有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個直接后繼。,可表示

15、為：（a1 , a2 , , an）,線性結(jié)構(gòu)的定義：,（邏輯、存儲和運算）,35,線性結(jié)構(gòu)的特點：, 只有一個首結(jié)點和尾結(jié)點； 除首尾結(jié)點外，其他結(jié)點只有一個直接前驅(qū)和一個直接后繼。,線性結(jié)構(gòu)表達(dá)式：（a1 , a2 , , an）,線性結(jié)構(gòu)包括線性表、堆棧、隊列、字符串、數(shù)組等等，其中，最典型、最常用的是-,線性表,簡言之，線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是 一對一 的,見第2章,36,第2章 線性表,2.1 線性表的邏輯結(jié)構(gòu) 2.2 線性表的順序表示和實現(xiàn) 2.3 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn) 2.4 應(yīng)用舉例 （一元多項式的表示及相加）,作業(yè),37,（a1, a2, ai-1，ai, ai1 ，

16、, an）,2.1 線性表的類型定義,一. 線性表的定義：用數(shù)據(jù)元素的有限序列表示,n=0時稱為,數(shù)據(jù)元素,線性起點,ai的直接前趨,ai的直接后繼,下標(biāo)，是元素的序號，表示元素在表中的位置,n為元素總個數(shù)，即表長,空表,線性終點,38,例1 分析26 個英文字母組成的英文表,（ A, B, C, D, , Z）,例2 分析學(xué)生情況登記表,數(shù)據(jù)元素都是記錄; 元素間關(guān)系是線性,數(shù)據(jù)元素都是字母; 元素間關(guān)系是線性,同一線性表中的元素必定具有相同特性,39,練：判斷下列敘述的正誤：,1. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的。 2. 線性表的邏輯結(jié)構(gòu)定義是唯一的，不依

17、賴于計算機。 3. 線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對一的。 4. 一維向量是線性表，但二維或N維數(shù)組不是。 5. “同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性”是指數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)都相等。,40,二.線性表的類型定義（詳見課本P19）,對線性表的有關(guān)操作舉例請大家看課本P20例2-1，例2-2,41,2.2 線性表的順序表示和實現(xiàn),2.2.1 順序表的表示 2.2.2 順序表的實現(xiàn) 2.2.3 順序表的運算效率分析,本節(jié)小結(jié),作 業(yè),42,2.2.1 順序表的表示,用一組地址連續(xù)的存儲單元依次存儲線性表的元素，可通過數(shù)組Vn來實現(xiàn)。,把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的

18、存儲單元中的存儲結(jié)構(gòu)。,線性表的順序表示又稱為順序存儲結(jié)構(gòu)或順序映像。,順序存儲定義：,順序存儲方法：,簡言之，邏輯上相鄰，物理上也相鄰,1.順序表示,43,2.線性表順序存儲特點：,1） 邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰； 2）若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出（利用數(shù)組下標(biāo)）。計算方法是（參見存儲結(jié)構(gòu)示意圖）： 設(shè)首元素a1的存放地址為LOC(a1)（稱為首地址）， 設(shè)每個元素占用存儲空間（地址長度）為L字節(jié)， 則表中任一數(shù)據(jù)元素的存放地址為： LOC(ai) = LOC(a1) + L *（i-1） LOC(ai+1) = LOC(ai)+L,注意：C語言中

19、的數(shù)組的下標(biāo)從0開始， 即：Vn的有效范圍是V0Vn-1,44,線性表的順序存儲結(jié)構(gòu)示意圖,地址 內(nèi)容 元素在表中的位序,1,i,2,n,空閑區(qū),i+1,L,b=LOC(a1),b + L,b +(i-1)L,b +(n-1)L,b +(max-1)L,45,一個一維數(shù)組，下標(biāo)的范圍是到，每個數(shù)組元素用相鄰的個字節(jié)存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素的第一個字節(jié)的地址是，則的第一個字節(jié)的地址是,113,因此：LOC( M3 ) = 98 + 5 (3-0) =113,解：地址計算通式為：,LOC(ai) = LOC(a1) + L *（i-1）,例1,46,3.線性表的動態(tài)分配順序存儲結(jié)構(gòu),

20、# define LIST_INIT_SIZE 100 / 線性表存儲空間的初始分配量 # define LISTINCREMENT 10 / 線性表存儲空間的分配增量 Typedef struct /若后面不再用，可省略結(jié)構(gòu)名 ElemType *elem; /表基址 int length; /表長（特指元素個數(shù)） int listsize; /表當(dāng)前存儲容量（字節(jié)數(shù)） SqList;,47,問1：自定義結(jié)構(gòu)類型變量test的長度m是多少？ msizeof(test) 問2：結(jié)構(gòu)變量test的首地址(指針p）是多少？ p(test*)malloc(m) 問3：怎樣刪除結(jié)構(gòu)變量test？只能借

21、助其指針刪除！ free(p),補充：介紹三個有用的庫函數(shù)（都在 中）： sizeof(x)計算變量x的長度； malloc(m) 開辟m字節(jié)長度的地址空間，并返回這段空間的首地址； free(p) 釋放指針p所指變量的存儲空間，即徹底刪除一個變量。,48,2.2.2 順序表的實現(xiàn)（或操作）,回憶：數(shù)據(jù)結(jié)構(gòu)基本運算操作有： 修改、插入、刪除、查找、排序,1.修改 通過數(shù)組的下標(biāo)便可訪問某個特定 元素并修改之。,核心語句: Vi=x;,顯然，順序表修改操作的時間效率是T(n)=O(1),49,2.建立 Status InitList_Sq( SqList / InitList_Sq,50,3.插

22、入 在線性表的第i個位置前插入一個元素,實現(xiàn)步驟：(n為表長） 將第n至第i 位的元素向后移動一個位置； 將要插入的元素寫到第i個位置； 表長加1。 注意：事先應(yīng)判斷: 插入位置i 是否合法?表是否已滿? 應(yīng)當(dāng)有1in+1 或 i=1,n+1,for (p=,/ 元素后移一個位置,/ 插入e,/ 表長加1,核心語句：,51,在線性表的第i個位置前插入一個元素的示意圖如下：,插入25,52,實現(xiàn)步驟：(n為表長） 將第i +1至第n 位的元素向前移動一個位置； 表長減1。 注意：事先需要判斷，刪除位置i 是否合法? 應(yīng)當(dāng)有1in 或 i=1, n,4.刪除 刪除線性表的第i個位置上的元素,for

23、 (+p;p=q;+p) *(p-1)=*p; -n;,/ 元素前移一個位置,/ 表長減1,核心語句：,53,刪除順序表中某個指定的元素的示意圖如下：,54,2.2.3 順序表的運算效率分析,算法時間主要耗費在移動元素的操作上，因此 計算時間復(fù)雜度的基本操作（最深層語句頻度） T(n)= O (移動元素次數(shù)) 移動元素的個數(shù)取決于插入或刪除元素的位置.,思考：若插入在尾結(jié)點之后，則根本無需移動（特別快）； 若插入在首結(jié)點之前，則表中元素全部要后移（特別慢）； 若要考慮在各種位置插入（共n+1種可能）的平均移動次數(shù)，該如何計算？,討論1：若在長度為 n 的線性表的第 i 位前 插入一 元素，則向

24、后移動元素的次數(shù)f(n)為: f(n) =,n i + 1,時間效率分析:,55,證明：假定在每個元素位置上插入x的可能性都一樣（即概率P相同），則應(yīng)當(dāng)這樣來計算平均執(zhí)行時間： 將所有位置的執(zhí)行時間相加，然后取平均。 若在首結(jié)點前插入，需要移動的元素最多，后移n次； 若在a1后面插入，要后移n-1個元素，后移次數(shù)為n-1; 若在an-1后面插入，要后移1個元素； 若在尾結(jié)點an之后插入，則后移0個元素； 所有可能的元素移動次數(shù)合計： 0+1+n = n(n+1)/2,共有多少種插入形式?連頭帶尾有n+1種,所以平均移動次數(shù)為：n(n+1)/2（n+1）n/2O(n),同理可證：順序表刪除一元素

25、的時間效率為: T（n)=(n-1)/2 O(n),56,討論2：若在長度為n的線性表上刪除第i位元素，向前移動元素的次數(shù)f(n)為：f(n)=,思考：若刪除尾結(jié)點，則根本無需移動（特別快）； 若刪除首結(jié)點，則表中元素全部要前移（特別慢）； 若要考慮在各種位置刪除（共n種可能）的平均移動次數(shù)，該如何計算？,n i,可以證明： 插入、刪除操作平均需要移動一半元素(n/ 2) 插入、刪除算法的平均時間復(fù)雜度為：O(n),顯然，順序表的空間復(fù)雜度S(n)=O(1) （沒有占用輔助空間）,57,教材P25算法2.5也是對執(zhí)行效率的推導(dǎo)：,假定在表中任意位置插入、刪除元素都是等概率的， 插入概率p(i)

26、=1/(n+1) ，刪除概率q(i)=1/n ，則：,插入操作時間效率（平均移動次數(shù)）,刪除操作時間效率（平均移動次數(shù)）,58,本節(jié)小結(jié),線性表順序存儲結(jié)構(gòu)特點：邏輯關(guān)系上相鄰的兩個元素在物理存儲位置上也相鄰； 優(yōu)點：可以隨機存取表中任一元素； 缺點：在插入，刪除某一元素時，需要移動大量元素。 為克服這一缺點，我們引入另一種存儲形式：,鏈?zhǔn)酱鎯Y(jié)構(gòu),見2.3節(jié),59,作業(yè)：,實驗： P181 實驗一: 集合的交并和差運算的實現(xiàn),60,第2章 線性表,2.1 線性表的邏輯結(jié)構(gòu) 2.2 線性表的順序表示和實現(xiàn) 2.3 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn) 2.4 應(yīng)用舉例,作業(yè),61,上堂課要點回顧,線性結(jié)構(gòu)(

27、包括表、棧、隊、數(shù)組）的定義和特點： 僅一個首、尾結(jié)點，其余元素僅一個直接前驅(qū)和 一個直接后繼。,2. 線性表,邏輯結(jié)構(gòu)：“一對一” 或 1:1 存儲結(jié)構(gòu)：順序、鏈?zhǔn)?運 算 ：修改、插入、刪除,3.順序存儲,特征：邏輯上相鄰，物理上也相鄰； 優(yōu)點：隨機查找快 O(1) 缺點：插入、刪除慢 O(n),62,2.3 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn),2.3.1 鏈表的表示 2.3.2 鏈表的實現(xiàn)線性鏈表，循環(huán)鏈表，雙向鏈表 2.3.3 鏈表的運算效率分析,本節(jié)小結(jié),作 業(yè),(續(xù)上堂課）,63,2.3.1 鏈表的表示,鏈?zhǔn)酱鎯μ攸c 與鏈?zhǔn)酱鎯τ嘘P(guān)的術(shù)語 線性表的單鏈表存儲結(jié)構(gòu),64,1. 鏈?zhǔn)酱鎯μ攸c：邏輯

28、上相鄰，物理上不一定相鄰,鏈表存放示意圖如下：,討論1：每個存儲結(jié)點都包含兩部分：數(shù)據(jù)和 。,討論2：在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置 由 指示。,其直接前驅(qū)結(jié)點的鏈域的值,指針域(鏈域),65,2. 與鏈?zhǔn)酱鎯τ嘘P(guān)的術(shù)語,1) 結(jié)點: 數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組成； 2）鏈表： n 個結(jié)點由指針鏈組成一個鏈表。它是線性表的鏈?zhǔn)?存儲映像，稱為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。 3）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表： 結(jié)點只有一個指針域的鏈表，稱為單鏈表或線性鏈表； 有兩個指針域的鏈表，稱為雙鏈表； 有多個指針域的鏈表，稱為多鏈表； 首尾相接的鏈表稱為循環(huán)鏈表。,4）頭指針

29、、頭結(jié)點和首元結(jié)點,以教材P27 圖2.5和圖2.6內(nèi)容為例說明。,66,何謂頭指針、頭結(jié)點和首元結(jié)點？,頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針。 單鏈表可由一個頭指針唯一確定。 頭結(jié)點是在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息; 首元結(jié)點是指鏈表中存儲線性表第一個數(shù)據(jù)元素a1的結(jié)點。,67,一個線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲結(jié)構(gòu)用單鏈表表示如下，請問其頭指針的值是多少？,例：,答：頭指針是指向鏈表中第一個結(jié)點的指針，因此關(guān)鍵是要尋找第一個結(jié)點的地址。,31,頭指針的值是3

30、1,68,上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：,區(qū)別： 無頭結(jié)點 有頭結(jié)點,69,Typedef struct Lnode ElemType data; /數(shù)據(jù)域 struct Lnode *next; /指針域 Lnode, *LinkList; / *LinkList為Lnode類型的指針,3. 線性表的單鏈表存儲結(jié)構(gòu),70,2.3.2 鏈表的實現(xiàn),1. 單鏈表的建立 2. 單鏈表的查找 3. 單鏈表的插入 4. 單鏈表的刪除 5. 其它鏈表形式,71,1. 單鏈表的建立,難點分析：每個數(shù)據(jù)元素在內(nèi)存中是“零散”存放的，其首地址怎么找？又怎么一一鏈接？,實現(xiàn)思路：先開辟頭指針，然后陸續(xù)

31、為每個數(shù)據(jù)元素開辟存儲空間并賦值，并及時將地址送給前面的指針。,72,Void CreateList_L (LinkList / 插入到表頭 / CreateList_L,73,2. 單鏈表的查找,思路：要修改第i個數(shù)據(jù)元素，關(guān)鍵是要先找到該結(jié) 點的指針p，然后用p-data=new_value 即可。,難點：單鏈表中想取得第i個元素，必須從頭指針出 發(fā)尋找（順藤摸瓜），不能隨機存取 。,核心語句：見教材P29的GetElem_L函數(shù)說明,74,Status GetElem_L(LinkList L, int i, ElemType / GetElem_L,討論：要統(tǒng)計鏈表中數(shù)據(jù)元素的個數(shù)，該

32、如何改寫？,75,3. 單鏈表的插入,在鏈表中插入一個元素的示意圖如下：,插入步驟（即核心語句）：,Step 1：s-next=p-next; Step 2：p-next=s ；,p-next,s-next,思考：步驟1和2能互換么？,元素x結(jié)點應(yīng)預(yù)先生成： S=(test*)malloc(m); S-data=x; S-next=p-next,76,4. 單鏈表的刪除,在鏈表中刪除某元素的示意圖如下：,刪除步驟（即核心語句）：,q = p-next; /保存b的指針，靠它才能指向c p-next=q-next; /a、c兩結(jié)點相連 free(q) ； /刪除b結(jié)點，徹底釋放,p-next,思

33、考： 省略free(q)語句行不行？,(p-next) - next,77,應(yīng)用舉例：兩個鏈表的歸并（教材P31）,算法要求： 已知：線性表 A、B，分別由單鏈表 LA , LB 存儲，其中數(shù)據(jù)元素按值非遞減有序排列， 要求：將 A ，B 歸并為一個新的線性表C , C 的數(shù)據(jù)元素仍按值非遞減排列 。設(shè)線性表 C 由單鏈表 LC 存儲。 假設(shè)：A=（3，5，8，11），B=（2，6，8，9，11） 預(yù)測：合并后 C =（ 2 , 3 , 5 , 6 , 8 , 8 , 9 , 11，11 ）,78,用鏈表可表示為：,頭結(jié)點,79,算法分析：,算法主要包括：搜索、比較、插入三個操作： 搜索：需要

34、兩個指針?biāo)阉鲀蓚€鏈表； 比較：比較結(jié)點數(shù)據(jù)域中數(shù)據(jù)的大??； 插入：將兩個結(jié)點中數(shù)據(jù)小的結(jié)點插入新鏈表。,80,La,Pa、Pb用于搜索La和Lb， Pc指向新鏈表當(dāng)前結(jié)點,81,算法實現(xiàn)：,Void MergeList_L(LinkList /釋放Lb的頭結(jié)點 /MergeList_L,pc-next = pa?pa:pb ; /插入剩余段,while(pa pb=pb-next ,pa=La-next; pb=Lb-next; Lc=pc=La； /初始化,82,思考：,1、不用Lc，直接把La表插到Lb表中；或者把Lb表 插到La表中，如何編程？,2、要求不能有重復(fù)的數(shù)據(jù)元素，如何編程？,

35、83,5. 其它鏈表形式,1) 循環(huán)鏈表：將表中最后一個結(jié)點的指針域指向頭結(jié) 點(P-next=head;)，整個鏈表形成一個環(huán)。 （示例見課本P35 圖2.12） A.特點：從任一結(jié)點出發(fā)均可找到表中其他結(jié)點。 B. 與單鏈表的區(qū)別：循環(huán)條件 單鏈表 - p = NULL 或 p -next =NULL 循環(huán)鏈表- p= head 或 p-next = head C. 設(shè)立尾指針：可以使鏈表合并簡化（課本P35-圖2.13）。,84,2）雙向鏈表：有兩個指針域的鏈表，稱為雙鏈表。 (示例見課本P36圖2.14) A.結(jié)點結(jié)構(gòu)： B.特點：可以雙向查找表中結(jié)點。 C.運算： 插入課本P36算法

36、2.18，圖2.16。 刪除課本P37算法2.19，圖2.15。 注：雙向鏈表在非線性結(jié)構(gòu)（如樹結(jié)構(gòu)）中將大量使用。,85,2.3.3 鏈表的運算效率分析,時間效率分析 1. 查找 因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復(fù)雜度為 O(n)。 2. 插入和刪除 因線性鏈表不需要移動元素，只要修改指針，一般情況下時間復(fù)雜度為 O(1)。 但是，如果要在單鏈表中進(jìn)行前插或刪除操作，由于 要從頭查找前驅(qū)結(jié)點，所耗時間復(fù)雜度為 O(n)。,86,練習(xí)： 在n個結(jié)點的單鏈表中要刪除已知結(jié)點*P，需找到它的前驅(qū)結(jié)點的地址，其時間復(fù)雜度為 O(n) 。 空間效率分析 鏈表中每個結(jié)點都要增

37、加一個指針空間，相當(dāng)于總共增加了n 個整型變量，空間復(fù)雜度為 O(n)。,87,2.4 應(yīng)用舉例,一元多項式的數(shù)學(xué)通式？ 用抽象數(shù)據(jù)類型如何描述它的定義？ 用C語言如何描述它的定義？ 如何編程實現(xiàn)兩個一元多項式相加？,一元多項式的表示及相加 (參見教材P39 43),討論：,88,1. 一元多項式的數(shù)學(xué)通式？,一元多項式的通式可表示為：,分析：一元多項式在計算機內(nèi)存儲時，既可用順序表存儲，又可用鏈表存儲。但當(dāng)多項式的次數(shù)很高且零系數(shù)項很多時，則更適于用鏈表存儲（通常設(shè)計兩個數(shù)據(jù)域和一個指針域）。,順序表,鏈表,或,89,2. 用抽象數(shù)據(jù)類型如何定義一元多項式？,（參見P40）,ADT Poly

38、nomial 數(shù)據(jù)對象：D=ai|aiTermSet,i=1,2,m, m0 TermSet中的每個元素包含一個表示系數(shù)的實數(shù)和表示指數(shù)的整數(shù) 數(shù)據(jù)關(guān)系：R1=| ai-1, ai D, 且ai-1中的指數(shù)值ai中的指數(shù)值, i=1,2,n 基本操作： CreatPolyn( typedef struct poly_node int coef; int expon; poly_pointer link; ; poly_pointer a, b, c;,93,實現(xiàn)思路：,依次比較Pa和Pb所指結(jié)點中的指數(shù)項，依 Pa-expon =、Pb-expon等情況，再決定是將兩系數(shù)域的數(shù)值相加（并判其和

39、是否為0），還是將較高指數(shù)項的結(jié)點插入到新表c中。,+,94,具體編程（用C語言）,利用建表操作CreatPolyn( hb =GetHead(Pb); /取二表頭指針(指向頭結(jié)點） qa=NextPos(Pa,ha); qb = NextPos(Pb,hb); /指向二表首元結(jié)點 while (qa ,96,elseDelFirst(ha,qa); FreeNode(qa);/若系數(shù)為0，則兩結(jié)點都刪 DelFirst(hb,qb); FreeNode(qb); qa=NextPos(Pa,ha); qb=NextPos(Pb,hb); break; case 1: / 若a的指數(shù)值大于b，

40、應(yīng)前插b（保持升序） DelFirst(hb,qb); InsFirst(ha,qb); qb=NextPos(Pb,hb); ha=NextPos(Pa,ha); break; /a表大結(jié)點后移 /switch /while If(!List Empty(Pb) Append(Pa,qb); / 若a表空，則b表剩余項全部 /鏈接到a表中；而b表空時無需動作，因為a表本身就是求和結(jié)果。 FreeNode(hb); /無論什么結(jié)局，最終b表都是要廢掉的。 / AddPolyn,97,運算效率分析:,(1)系數(shù)相加 0 加法次數(shù) min(m, n) 其中 m和n分別表示表A和表B的結(jié)點數(shù)。 (2

41、)指數(shù)比較 極端情況是表A和表B 沒有一項指數(shù)相同，比較次數(shù)最多為m+n-1 (3)新結(jié)點的創(chuàng)建 極端情況是產(chǎn)生m + n 個新結(jié)點 合計時間復(fù)雜度為 O(m+n),98,本章小結(jié)（討論題形式）,問1：線性表的邏輯結(jié)構(gòu)特點是什么？其順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是什么？ 答：線性表邏輯結(jié)構(gòu)特點是，只有一個首結(jié)點和尾結(jié)點；除首尾結(jié)點外其他結(jié)點只有一個直接前驅(qū)和一個直接后繼。簡言之，線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對一（1:1）的。 順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。 鏈?zhǔn)酱鎯r，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，

42、一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針。,99,問2：順序存儲和鏈?zhǔn)酱鎯Ω饔心男﹥?yōu)缺點？,答：順序存儲的優(yōu)點是存儲密度大(1)，存儲空間利用率高。缺點是插入或刪除元素時不方便。 鏈?zhǔn)酱鎯Φ膬?yōu)點是插入或刪除元素時很方便，使用靈活。缺點是存儲密度?。?），存儲空間利用率低。 事實上，鏈表插入、刪除運算的快捷是以空間代價來換取時間。,100,問3：在什么情況下用順序表比鏈表好？,答：順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。 若線性表的長度變化不大，且其主要操作是查找，則采用順序表； 若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。,101,

43、作業(yè)：,請試做配套題集.,102,數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容,103,3.1 棧（Stack）,第三章 棧和隊列,3.2 隊列（Queue）,1. 定義 2. 邏輯結(jié)構(gòu) 3. 存儲結(jié)構(gòu) 4. 運算規(guī)則 5. 實現(xiàn)方式,1. 定義 2. 邏輯結(jié)構(gòu) 3. 存儲結(jié)構(gòu) 4. 運算規(guī)則 5. 實現(xiàn)方式,104,1. 定義,3.1 棧,與同線性表相同，仍為一對一關(guān)系。,用順序棧或鏈棧存儲均可，但以順序棧更常見,只能在棧頂運算，且訪問結(jié)點時依照后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）的原則。,關(guān)鍵是編寫入棧和出棧函數(shù)，具體實現(xiàn)依順序棧或鏈棧的不同而不同。 基本操作有入棧、出棧、讀棧頂元素值、建棧、或判斷棧滿、?？?/p>

44、等。,限定只能在表的一端進(jìn)行插入和刪除運算的線性表（只能在棧頂操作）,105,問：堆棧是什么？它與一般線性表有什么不同？,3.1 棧,答：堆棧是一種特殊的線性表，它只能在表的一端（即棧頂）進(jìn)行插入和刪除運算。 與一般線性表的區(qū)別：僅在于運算規(guī)則不同。,一般線性表 堆棧 邏輯結(jié)構(gòu)：一對一 邏輯結(jié)構(gòu)：一對一 存儲結(jié)構(gòu)：順序表、鏈表 存儲結(jié)構(gòu)：順序棧、鏈棧 運算規(guī)則：隨機存取 運算規(guī)則：后進(jìn)先出(LIFO),“進(jìn)” 壓入=PUSH（x) “出” 彈出=POP ( y ),106,棧 是僅在表尾進(jìn)行插入、刪除操作的線性表。 表尾(即 an 端)稱為棧頂 top ; 表頭(即 a1 端)稱為棧底base

45、,例如： 棧 s= (a1 , a2 , a3 , .,an-1 , an ),a1 稱為 棧底元素 an 稱為 棧頂元素,插入元素到棧頂（即表尾）的操作，稱為入棧。 從棧頂（即表尾）刪除最后一個元素的操作，稱為出棧。,教材P44對棧有更詳細(xì)定義：,強調(diào)：插入和刪除都只能在表的一端（棧頂）進(jìn)行！,107,順序棧示意圖,108,表和棧的操作區(qū)別對線性表 s= (a1 , a2 , . , an-1 , an ),寫入：vi= ai 讀出： x= vi,壓入：PUSH (an+1) 彈出： POP (x),前提：一定要預(yù)設(shè)棧頂指針top！,an+1,109,入棧操作例如用堆棧存放（A，B，C，D）

46、 （注意要遵循“后進(jìn)先出” 原則）,A,A,C B A,B A,核心語句： top=L;,順序棧中的PUSH函數(shù) status Push(ElemType x) if(topM)上溢 else vtop+=x; ,Push (B);,Push (C);,Push (D);,低地址L,Push (A);,高地址M,B,C,D,110,出棧操作例如從棧中取出B （注意要遵循“后進(jìn)先出” 原則）,核心語句： Pop ( ); Pop ( ); Printf( Pop () );,順序棧中的POP函數(shù) status Pop( ) if(top=L) 下溢 else y=v-top; return(y)

47、; ,111,例1：一個棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實現(xiàn)嗎？12345的輸出呢？,43512不可能實現(xiàn)，主要是其中的12順序不能實現(xiàn)； 12345的輸出可以實現(xiàn)，只需壓入一個立即彈出一個即可。,435612中到了12順序不能實現(xiàn)； 135426可以實現(xiàn)。,例2：如果一個棧的輸入序列為123456，能否得到435612和135426的出棧序列？,答：,答：,112,例3（嚴(yán)題集3.1）一個棧的輸入序列為123，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？,答：,可以通過窮舉所有可能性來求解： 1入1出， 2入2出，3入3出， 即123

48、； 1入1出， 2、3入3、2出， 即132； 1、2入，2出， 3入3出， 即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出， 即321； 合計有5種可能性。,113,補充1： 若入棧動作使地址向高端增長，稱為“向上生成”的棧； 若入棧動作使地址向低端增長，稱為“向下生成”的棧； 對于向上生成的棧 入?？谠E：堆棧指針top先壓后加（vtop+=x）； 出?？谠E：堆棧指針top先減后彈（y=v-top) 。,3.1 棧,補充2： 棧不存在的條件： base=NULL; 棧為空 的條件 ： base=top; 棧滿的條件 ： top-base=stacksize

49、;,114,補充3：鏈棧 鏈棧示意圖,115,鏈棧的入棧函數(shù)、出棧函數(shù)（以頭指針為棧頂，在頭指針處插入或刪除?。?公共說明部分： typedef struct snode SElemType data; struct snode *link; NODE; NODE *st, *p; int m=sizeof(NODE);,116,Push (SElemType x) p=(NODE*)malloc(m); if(!p)上溢 else p-data=x; p-link=st; st=p; ,Status pop( ) if(st=NULL)下溢 elsey=st-data;p=st;st=st-

50、link; free(p); return(y); ,鏈棧 入棧函數(shù),鏈棧 出棧函數(shù),插入表頭,從表頭刪除,117, 鏈棧不必設(shè)頭結(jié)點，因為棧頂（表頭）操作頻繁； 采用鏈棧存儲方式，可使多個棧共享空間；當(dāng)棧中元素個數(shù)變化較大，且存在多個棧的情況下，鏈棧是棧的首選存儲方式。,說 明,118,問：為什么要設(shè)計堆棧？它有什么獨特用途？,調(diào)用函數(shù)或子程序非它莫屬； 遞歸運算的有力工具； 用于保護現(xiàn)場和恢復(fù)現(xiàn)場； 簡化了程序設(shè)計的問題。,答：,119,數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N） P48 設(shè)計思路：用棧暫存低位值 例2：括號匹配的檢驗P49 設(shè)計思路：用棧暫存左括號 例3 ：表達(dá)式求值 -P52 設(shè)計思路：用棧暫

51、存運算符 例4：漢諾儀（Hanoi）塔-P55 設(shè)計思路：用棧實現(xiàn)遞歸調(diào)用,例1：,120,例3 表達(dá)式求值 ( 這是棧應(yīng)用的典型例子 ) 這里，表達(dá)式求值的算法是 “算符優(yōu)先法”。,例如：3*（7 2 ） （1）要正確求值，首先了解算術(shù)四則運算的規(guī)則： a. 從左算到右 b. 先乘除，后加減 c. 先括號內(nèi)，后括號外 由此，此表達(dá)式的計算順序為： 3*（7 2 ）= 3 * 5 = 15,121,（2）根據(jù)上述三條運算規(guī)則，在運算的每一步中，對任意相繼出現(xiàn)的算符1和2 ，都要比較優(yōu)先權(quán)關(guān)系。 算符優(yōu)先法所依據(jù)的算符間的優(yōu)先關(guān)系見教材P53表3.1 （是提供給計算機用的表！） 由表可看出，右括

52、號 ) 和井號 # 作為2時級別最低； 由c 規(guī)則得出： * ，/， + ，-為1時的優(yōu)先權(quán)低于（，高于） 由a規(guī)則得出：（=） 表明括號內(nèi)運算，已算完。 # = # 表明表達(dá)式求值完畢。,棧的應(yīng)用（表達(dá)式求值）,122,（3）算法思想： 設(shè)定兩棧：操作符棧 OPTR ，操作數(shù)棧 OPND 棧初始化：設(shè)操作數(shù)棧 OPND 為空；操作符棧 OPTR 的棧底元素為表達(dá)式起始符 #； 依次讀入字符：是操作數(shù)則入OPND棧，是操作符則要判斷： if 操作符 棧頂元素，壓入OPTR棧。,棧的應(yīng)用（表達(dá)式求值）,123,棧的應(yīng)用（表達(dá)式求值）,124,Status EvaluateExpression(

53、OperandType /EvaluateExpression,此函數(shù)在哪里？,125,定 義,3.2 隊列,與同線性表相同，仍為一對一關(guān)系。,順序隊或鏈隊，以循環(huán)順序隊更常見。,只能在隊首和隊尾運算，且訪問結(jié)點時依照先進(jìn)先出（FIFO）的原則。,關(guān)鍵是掌握入隊和出隊操作，具體實現(xiàn)依順序隊或鏈隊的不同而不同。 基本操作有入隊或出隊，建空隊列，判隊空或隊滿等操作。,只能在表的一端進(jìn)行插入運算，在表的另一端進(jìn)行刪除運算的線性表 （頭刪尾插）,126,隊列 （Queue）是僅在表尾進(jìn)行插入操作，在表頭進(jìn)行刪除操作的線性表。 表尾即 an 端，稱為 隊尾 ； 表頭即 a1 端，稱為隊頭。 它是一種先進(jìn)

54、先出（）的線性表。,例如：隊列 Q= (a1 , a2 , a3 , .,an-1 , an ),插入元素稱為入隊；刪除元素稱為出隊。,隊頭,隊尾,教材P59對隊列有更詳細(xì)定義：,隊列的抽象數(shù)據(jù)類型定義見教材5960 隊列的存儲結(jié)構(gòu)為鏈隊或順序隊 （常用循環(huán)順序隊）,127,鏈隊列示意圖,討論： 空隊列的特征？, 怎樣實現(xiàn)入隊和出隊操作？ 入隊（尾部插入）：rear-next=S; rear=S; 出隊（頭部刪除）：front-next=p-next;,完整動作設(shè)計參見教材P61-62, 隊列會滿嗎？,front=rear,一般不會，因為刪除時有free動作。除非內(nèi)存不足！,128,構(gòu)造一個空

55、隊列 Status InitQuene( LinkQuene ,129,2) 銷毀隊列 Status DestroyQuene ( LinkQuene ,130,3) 入隊 Status EnQuene ( LinkQuene ,131,4) 出隊 Status DeQuene ( LinkQuene ,132,順序隊示意圖,(隊尾),(隊首), 隊列會滿嗎？ 很可能會，因為數(shù)組前端空間無法釋放。因此數(shù)組應(yīng)當(dāng)有長度限制。, 空隊列的特征？ 約定：front=rear,隊尾后地址,入隊(尾部插入)：vrear=e; rear+; 出隊(頭部刪除)：x=vfront; front+;,討論：,假溢

56、出,有缺陷, 怎樣實現(xiàn)入隊和出隊操作？,3.2 隊列,133,問：什么叫“假溢出” ？如何解決？,答：在順序隊中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊操作，但其實數(shù)組中還有空位置，這就叫“假溢出”。,3.2 隊列,解決假溢出的途徑采用循環(huán)隊列,134,循環(huán)隊列（臆造）,順序隊列,新問題：在循環(huán)隊列中，空隊特征是front=rear；隊滿時也會有front=rear；判決條件將出現(xiàn)二義性！ 解決方案有三： 加設(shè)標(biāo)志位，讓刪除動作使其為1,插入動作使其為0,則可識別當(dāng)前 front=rear 使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）； 人為浪費一個單元，令隊滿特征為front=(rear

57、+1)%N；,135,隊空條件 : front = rear (初始化時：front = rear ) 隊滿條件： front = (rear+1) % N (N=maxsize) 隊列長度：L=（Nrearfront）% N,選用空閑單元法：即front和rear之一指向?qū)嵲兀硪恢赶蚩臻e元素。,問3： 在具有n個單元的循環(huán)隊列中，隊滿時共有多少個元素？,n-1個,5,問2：左圖中隊列長度L=？,問1：左圖中隊列容量 maxsize N=？,6,136,注意： 循環(huán)隊列中的“長度”到底是指總長度還是數(shù)據(jù)元素 個數(shù)？ 答：一般情況下的長度（L）是指元素個數(shù)（不含頭結(jié)點或空閑單元），而maxs

58、ize N 才是指所有單元總 數(shù)，即“容量”。,137,例1： 一循環(huán)隊列如下圖所示，若先刪除4個元素，接著再插入4個元素，請問隊頭和隊尾指針分別指向哪個位置?,解：由圖可知，隊頭和隊尾指針的初態(tài)分別為front=1和rear=6。,刪除4個元素后front=5；再插入4個元素后，rear=4。,138,例2 ：數(shù)組n用來表示一個循環(huán)隊列，f 為當(dāng)前隊列頭元素的前一位置，r 為隊尾元素的位置。假定隊列中元素的個數(shù)小于n，計算隊列中元素的公式為:,（） rf （）（nfr）% n （）nrf （） （nrf）% n,4種公式哪種合理？ 當(dāng) r f 時（A）合理； 當(dāng) r f 時（C）合理；,分析

59、 ：,綜合2種情況，以（D）的表達(dá)最為合理,例3：在一個循環(huán)隊列中，若約定隊首指針指向隊首元素的前一個位置。那么，從循環(huán)隊列中刪除一個元素時，其操作是 先 ，后 。,移動隊首指針,取出元素,139,問：為什么要設(shè)計隊列？它有什么獨特用途？,離散事件的模擬（模擬事件發(fā)生的先后順序）； 操作系統(tǒng)中多道作業(yè)的處理（一個CPU執(zhí)行多個作業(yè)）； 3. 簡化程序設(shè)計。,答：,循環(huán)隊列的操作實現(xiàn)見教材P64,140,循環(huán)隊列的操作實現(xiàn),1）初始化一空隊列,算法要求：生成一空隊列 算法操作：為隊列分配基本容量空間 設(shè)置隊列為空隊列， 即 front=rear=0（也可為任意單元，如 2，或 4）;,141,算

60、法：,Status InitQueue ( SqQueue ,新開單元的地址為0則表示內(nèi)存不足,142,算法說明：向循環(huán)隊列的隊尾插入一個元素 分 析： (1) 插入前應(yīng)當(dāng)先判斷隊列是否滿 if ( q . rear + 1 ) % QUEUE_MAXSIZE )=q.front) return ERROR; (2）插入動作 q.base q.rear = e; q.rear = ( q . rear + 1 ) % QUEUE_MAXSIZE;,2） 入隊操作,143,Status EnQueue(SqQueue ,2） 入隊操作（完整函數(shù)）,144,3）出隊操作,算法說明：刪除隊頭元素，返

61、回其值 e 分 析： （1） 在刪除前應(yīng)當(dāng)判斷隊列是否空； if (q.front = q.rear ) return ERROR; （2）插入動作分析； 因為隊頭指針front指向隊頭元素的位置，所以： e = q.base q.front ; q.front = ( q . front + 1 ) % QUEUE_MAXSIZE;,145,Status DeQueue ( SqQueue / DeQueue,算法：,146,討論（代本章小結(jié)）,線性表、棧與隊的異同點 相同點：邏輯結(jié)構(gòu)相同，都是線性的；都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表（只是對插入、刪除運

62、算加以限制）。 不同點： 運算規(guī)則不同，線性表為隨機存取，而棧是只允許在一端進(jìn)行插入和刪除運算，因而是后進(jìn)先出表LIFO；隊列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運算，因而是先進(jìn)先出表FIFO。 用途不同，線性表比較通用；堆棧用于函數(shù)調(diào)用、遞歸和簡化設(shè)計等；隊列用于離散事件模擬、多道作業(yè)處理和簡化設(shè)計等。,147,注：下次課前請完成第3章自測卷全部內(nèi)容，有關(guān)算法設(shè)計題，建議上機驗證。,148,補充：C語言中常用的串運算,串比較，int strcmp(chars1,char s2); / StrCompare(S,T) 求串長， int strlen(char s); / StrLength(

63、S) 串連接，char strcat(char to,char from) / Concat( / Index(S, T, pos) ,Concat concatenation，在字符串處理中,把多個短字符串合成為長字符串的操作。,注：用C處理字符串時，要調(diào)用標(biāo)準(zhǔn)庫函數(shù) #include,149,數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容,150,第4章 串（String）,4.2 串的表示和實現(xiàn) 4.3 串的模式匹配算法,1. 定義 2. 邏輯結(jié)構(gòu) 3. 存儲結(jié)構(gòu) 4. 運算規(guī)則 5. 實現(xiàn)方式,4.1 串類型的定義,151,記為： s = a1 , a2 , . , an (n0 ),串中字符個數(shù)（n0）. n=

64、0 時稱為空串 。 由一個或多個空格符組成的串。 串s中任意個連續(xù)的字符序列叫s的子串; S叫主串。 子串的第一個字符的序號。 字符在串中的序號。 串長度相等，且對應(yīng)位置上字符相等。,串即字符串，是由零個或多個字符組成的有限序列，是數(shù)據(jù)元素為單個字符的特殊線性表。,4.1 串類型的定義,若干術(shù)語： 串長： 空白串： 子串： 子串位置： 字符位置： 串相等：,隱含結(jié)束符/0 ，即ASCII碼NULL,152,練1：串是由 字符組成的序列，一般記為 。,練2：現(xiàn)有以下4個字符串： a =BEI b =JING c = BEIJING d = BEI JING,問： 他們各自的長度？ a是哪個串的子串？在主串中的位置是多少？,a =3，b =4，c = 7，d=8,a是c和d的子串，在c和d中的位置都是1,練