數(shù)據(jù)結(jié)構(gòu)全套完整課件

1、數(shù) 據(jù) 結(jié) 構(gòu)DATA STRUCTURE,引言 基本概念和術(shù)語 數(shù)據(jù)類型、C語言的數(shù)據(jù)類型 算法的描述和分析,第一章 緒論,1.1 什么是數(shù)據(jù)結(jié)構(gòu)？ 一、討論范疇 思考:計算機的工作過程？ 對輸入的數(shù)據(jù)進(jìn)行各種處理，最后得到運算結(jié)果的過程。 所以計算機科學(xué)是研究數(shù)據(jù)表示和數(shù)據(jù)處理的科學(xué)。 程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法 程序: 為計算機處理問題編制一組指令集。 算法：為解決問題而采取的方法、步驟。 數(shù)據(jù)結(jié)構(gòu): 問題的數(shù)學(xué)模型。反映數(shù)據(jù)的內(nèi)部構(gòu)成，即有哪些成分構(gòu)成，各成分之間關(guān)系，呈現(xiàn)的結(jié)構(gòu)狀態(tài)。 例1：數(shù)據(jù)庫中的表結(jié)構(gòu)； 例2：操作系統(tǒng)中文件系統(tǒng)結(jié)構(gòu)：目錄樹 以非數(shù)值計算為主的應(yīng)用中，算法與數(shù)

2、據(jù)的重要性關(guān)系發(fā)生變化。 二、數(shù)據(jù)結(jié)構(gòu)在計算機科學(xué)中的地位,學(xué)生”表格,特點：由一條條學(xué)生記錄組成，各記錄按學(xué)號大小遞增排列，形成一對一線性關(guān)系，稱為線性表,UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖,特點：采用多級目錄的目錄樹形式組織文件。 具有一對多層次關(guān)系,6,引言 基本概念和術(shù)語 數(shù)據(jù)類型、C語言的數(shù)據(jù)類型 算法的描述和分析,第一章 緒論,1.2 基本概念和術(shù)語 一、 幾個概念 1.數(shù)據(jù)：數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機中，被計算機程序識別和處理的符號的集合。分為：數(shù)值性數(shù)據(jù)和非數(shù)值性數(shù)據(jù)，如字符、圖象、語音等。 2.數(shù)據(jù)元素（記錄、結(jié)點）：是數(shù)據(jù)處理的最小單位，有

3、時一個數(shù)據(jù)元素由若干數(shù)據(jù)項（是數(shù)據(jù)不可分割的最小單位）組成，如一個學(xué)生記錄由學(xué)號、姓名等數(shù)據(jù)項組成。 數(shù)據(jù)對象：是具有相同性質(zhì)的數(shù)據(jù)數(shù)據(jù)元素的集合。 如：整數(shù)數(shù)據(jù)對象 N = 0, 1, 2,3.數(shù)據(jù)結(jié)構(gòu) (狹義、廣義概念) 狹義：數(shù)據(jù)元素之間的相互關(guān)系稱為結(jié)構(gòu)；相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的集合稱為數(shù)據(jù)結(jié)構(gòu)。 記為：Data-Structure = D, R 其中，D：性質(zhì)相同（同類型）的數(shù)據(jù)元素的集合；R：各元素之間邏輯關(guān)系的有限集合（一種或多種關(guān)系）。 廣義：研究非數(shù)值計算的程序設(shè)計問題中，計算機的操作對象、它們之間的關(guān)系以及在計算機中的存儲和操作的學(xué)科,二、數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容,

4、1.邏輯結(jié)構(gòu): 數(shù)據(jù)元素之間邏輯關(guān)系的描述。 從解決問題的需要出發(fā)，為實現(xiàn)必要的功能所建立的 數(shù)據(jù)結(jié)構(gòu)，是面向用戶的視圖。 分為兩大類：線性結(jié)構(gòu)、非線性結(jié)構(gòu)。 四種基本結(jié)構(gòu)：線性表、樹、圖、集合。 常用關(guān)系圖表示： 2.物理結(jié)構(gòu)（存儲結(jié)構(gòu)）：是數(shù)據(jù)在計算機中的實現(xiàn) （存儲映像），不僅存放數(shù)據(jù)本身，還要體現(xiàn)元素之 間的關(guān)系。是面向計算機的視圖。 四種基本結(jié)構(gòu)：順序、鏈接、索引、散列存儲結(jié)構(gòu),3.定義在DS上的操作 數(shù)據(jù)結(jié)構(gòu)不僅要研究數(shù)據(jù)邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，還包括定義在數(shù)據(jù)結(jié)構(gòu)上的運算。即對數(shù)據(jù)的操作運算也是DS的研究內(nèi)容。 說明：算法與DS密不可分。一方面，好的算法建立在好的數(shù)據(jù)結(jié)構(gòu)之上；另一方

5、面，好的數(shù)據(jù)結(jié)構(gòu)體現(xiàn)在算法中。即使邏輯結(jié)構(gòu)相同，但定義的操作不同，則是不同的數(shù)據(jù)結(jié)構(gòu)，如棧和隊列。 基本操作：插入、刪除、更新、查找、排序等。 說明：操作種類和數(shù)量無限制。但操作結(jié)果不能改變原結(jié)構(gòu),3.定義在DS上的操作,數(shù)據(jù)結(jié)構(gòu)不僅要研究數(shù)據(jù)邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，還 包括定義在數(shù)據(jù)結(jié)構(gòu)上的運算。即對數(shù)據(jù)的操作運 算，也是DS的研究內(nèi)容。說明： 算法與DS密不可分。一方面，好的算法建 立在好的數(shù)據(jù)結(jié)構(gòu)之上；另一方面，好的數(shù)據(jù)結(jié)構(gòu) 體現(xiàn)在算法中。即使邏輯結(jié)構(gòu)相同，但定義的操 作不同，則是不同的數(shù)據(jù)結(jié)構(gòu)，如棧和隊列。 基本操作：插入、刪除、更新、查找、排序等。 說明：操作種類和數(shù)量無限制。但操作結(jié)果

6、不能改 變原結(jié)構(gòu),總結(jié)：數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容 （本課程的研究內(nèi)容,在解決問題時可能遇到的典型的邏輯結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)） 邏輯結(jié)構(gòu)的存儲映象（存儲實現(xiàn)） 數(shù)據(jù)結(jié)構(gòu)的相關(guān)操作及其實現(xiàn),13,引言 基本概念和術(shù)語 數(shù)據(jù)類型、C語言的數(shù)據(jù)類型 算法的描述和分析,第一章 緒論,1.3 數(shù)據(jù)類型和抽象數(shù)據(jù)類型,1.數(shù)據(jù)類型：是性質(zhì)相同的值的集合, 及定義在此集合上的一組操作的總稱。 說明：規(guī)定了值的取值范圍，和定義在此值上的操 作。是高級語言層次上對數(shù)據(jù)的抽象。 例，C語言中的數(shù)據(jù)類型： 基本數(shù)據(jù)類型(int、float、char)、數(shù)組、指針、結(jié)構(gòu)體類型等。 數(shù)據(jù)類型是高級語言中系統(tǒng)實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，在高級語言

7、層次上討論數(shù)據(jù)結(jié)構(gòu)必須借助其數(shù)據(jù)類型來描述,2.抽象數(shù)據(jù)類型(ADTs: Abstract Data Types,與數(shù)據(jù)類型是一個概念，只是其范疇更廣，主要 指由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型： 由基本的數(shù)據(jù)類型組成, 并包括一組相關(guān)的操作。 即：ADT = 數(shù)據(jù) + 操作 特點：將數(shù)據(jù)與操作的定義封裝在一個模塊中，更能體現(xiàn)數(shù)據(jù)結(jié)構(gòu)與操作是緊密聯(lián)系的整體,16,引言 基本概念和術(shù)語 數(shù)據(jù)類型、C語言的數(shù)據(jù)類型 算法的描述和分析,第一章 緒論,1.4 算法描述和算法分析,一、算法描述 1.算法定義： 是為解決一個問題而采取的方法和步驟。 2.算法的描述:自然語言、偽代碼、程序語言（C+,C

8、,PASCAL等語言）。本書采用C語言描述,二、性能分析與度量,1.評價算法主要考慮的因素：正確性、效率（存儲空間和運行時間開銷）、可讀性 、健壯性等. 一個算法運行所需時間的長短、空間的大小具有 非常重要的意義。 算法效率的度量： 時間復(fù)雜度、空間復(fù)雜度,2、時間復(fù)雜度分析 時間復(fù)雜度：是與問題規(guī)模有關(guān)的量。 算法處理的數(shù)據(jù)元素個數(shù)稱為問題的規(guī)模。如：在有n個學(xué)生記錄的文件中查找名為張三的學(xué)生記錄，則n即為問題規(guī)模。 時間復(fù)雜度計算： 一個算法所耗費的時間，應(yīng)該是該算法中每條語句的執(zhí)行時間之和，而每條語句的執(zhí)行時間又是該語句的執(zhí)行次數(shù)（頻度）與該語句執(zhí)行一次所需時間的乘積。假定每條語句一次執(zhí)

9、行的時間都是相同的,為單位時間。這樣，一個算法的時間耗費就是該算法中所有語句的頻度之和,簡化計算： 一般以關(guān)鍵操作（循環(huán)、遞歸）的執(zhí)行頻度（一般與問題規(guī)模有關(guān)）作為時間復(fù)雜度，時間復(fù)雜度是關(guān)鍵操作執(zhí)行頻度函數(shù)，是關(guān)于n的函數(shù)， T( n )。 當(dāng)問題規(guī)模n 趨于無窮大時，把時間復(fù)雜度T( n )的數(shù)量級（階）稱為算法的漸進(jìn)時間復(fù)雜度（有時簡稱為時間復(fù)雜度）記為：O（n）。 它表示當(dāng)n充分大時，時間復(fù)雜度T( n )的數(shù)量級（最高階），如: O（2n3+4n2+4n+10）O(n3,常用語句階的計算： 1)若算法的執(zhí)行時間是一個與問題規(guī)模n無關(guān)的常數(shù)，如賦值、比較等，則算法的時間復(fù)雜度為常數(shù)階，

10、記作T(n)=O(1)。 2)選擇執(zhí)行的成分，如 if 語句的執(zhí)行時間，決定于then 子句、else 子句耗時較多的部分。 3)一般情況下對循環(huán)語句只考慮循環(huán)體語句的執(zhí)行次數(shù)，而忽略該語句中補長加一、終值判別等成份。 一次循環(huán)，設(shè)循環(huán)次數(shù)n O（n） 嵌套循環(huán)，由最內(nèi)層循環(huán)體語句執(zhí)行頻度決定，設(shè)兩層（外層循環(huán)次數(shù)n，內(nèi)層m） O（mn） 并列循環(huán)，由循環(huán)次數(shù)最大的決定，設(shè)兩并列循環(huán)，循環(huán)次數(shù)分別為n、m O(max(m,n) 4)很多算法的時間復(fù)雜度不僅與問題的規(guī)模有關(guān)，而且還與它所處理的數(shù)據(jù)集的初始狀態(tài)(取值、排列)有關(guān),例1：求兩個方陣的乘積 CA*B define n 自然數(shù) MATR

11、IXMLT(float Ann,float Bnn,float Cnn) int i,j,k; for(i=0;in;i+) for(j=0;jn;j+) Cij=0; /n*n for( k=0;kn;k+) Cij+=Aik*Bkj /n*n*n 時間復(fù)雜度為,例2： x=0;y=0; for (k=1;k=n;k+) x+; /n for (i=1;i=n;i+) for (j=1;j=m;j+) y+; /n*m 時間復(fù)雜度為,例3： temp = i; i = j; j = temp,例4： i=n-1; while (i=0,此問題不僅與規(guī)模 n 有關(guān)，而且與數(shù)組A中各元素的取值有

12、關(guān),問題與規(guī)模 n 無關(guān),常數(shù)階 對數(shù)階 線性階 線性對數(shù)階 平方階 立方階 K次方階 指數(shù)階,常見的時間復(fù)雜度，按數(shù)量級遞增排列(越小越好,空間復(fù)雜度分析,空間復(fù)雜度:描述算法消耗的存儲空間。 一般只考慮輔助空間，忽略程序與輸入數(shù)據(jù)所占空間。輔助空間一般與問題規(guī)模有關(guān)，通常在遞歸算法中考慮空間復(fù)雜度分析。 原地操作：輔助空間消耗是常量階，O（1）。 由于存儲技術(shù)的飛速發(fā)展，空間復(fù)雜度分析所以重要性降低，另外，空間復(fù)雜度分析只對某些特殊算法（遞歸算法）重要,數(shù)據(jù)結(jié)構(gòu),李 凱,2013年11月,第二章 線性表,Page 28,2.1 線性表定義和運算 2.2 順序表 2.3 鏈表（單鏈表） 2.

13、4 其他形式鏈表,內(nèi)容 設(shè)置,Page 29,2.1 線性表定義與運算,定義,定義：線性表L是由n個元素a1, a2, , an組成的有限序列，記作L=(a1, a2, , an)，其中n0為表長度；當(dāng)n=0時L為空表，記作L=( )。 表結(jié)構(gòu)。由于線性表是一組元素的序列，因此每個元素最多有一個直接前驅(qū)，最多有一個直接后繼。 例如：( , ai-1, ai, ai+1 ) 元素個數(shù)。即表長度。取值為一個有限數(shù)。 表中元素在不同場合可以有不同含義與類型。 例如：大寫字母表(A, B, , Z)；數(shù)字表(0,1,2, 9)；成績表(張三, 100), (李四,90), ) 【ai是一個結(jié)構(gòu)體記錄,

14、Page 30,2.1 線性表定義與運算,基本 運算,初始化線性表List_Initial (L)： 構(gòu)造一個空的線性表L。 求表長度List_Length(L)： 求表中元素的個數(shù)。 按照序號取元素List_GetElement(L,i)： 取出表中序號為i的元素。 按值查詢List_Locate (L,x)： 在線性表L中查找值為x的元素。若存在，則返回其地址；否則，返回一個不存在的地址值或標(biāo)記,Page 31,2.1 線性表定義與運算,基本 運算,插入元素List_Insert(L,i,x)： 在線性表L的第i個位置插入值為x的元素。如果表長度為n，則i應(yīng)滿足1in+1。 刪除元素Lis

15、t_Delete(L,i)： 刪除線性表L中序號為i的元素。 1in。 說明： 線性表更復(fù)雜的運算可以由基本運算組合。 例如：刪除表中值為x的元素，可以通過+實現(xiàn)。 對于基本運算中，在確定為某種具體數(shù)據(jù)時也可能存在差異,Page 32,2.2 順序表,概念,順序表：假設(shè)有一個足夠大的連續(xù)的存儲空間，則可將線性表中元素按照其邏輯次序依次存儲到該存儲空間，稱由此得到的線性表為順序表。 （線性表的順序存儲方法） 順序表在具體實現(xiàn)時，一般用數(shù)組來對應(yīng)一個連續(xù)的存儲空間。設(shè)最多可存放maxlen個元素，則可用數(shù)值datamaxlen來存儲數(shù)據(jù)。 （注：maxlen的取值需要自己預(yù)判） 由于線性表中數(shù)據(jù)元

16、素個數(shù)可能會發(fā)生變化，及表長度變化，因此線性表只占據(jù)了data的一部分，因此需設(shè)置一個變量記錄順序表元素個數(shù),Page 33,2.2 順序表,概念,define maxlen 100 /假設(shè)元素個數(shù)最大為100 typedef struct Element_Type datemaxlen; /定義存儲數(shù)值 int listlen; /定義表長度 seqlist; seqlist L, L1; seqlist,Page 34,2.2 順序表,基本 運算,初始化線性表： void List_Initial (seqlist *L) L-listlen=0; 求表長度： int List_Lengt

17、h(seqlist L) return L .listlen;,Page 35,2.2 順序表,基本 運算,按照序號取元素（取出的元素放在變量x里）： void List_GetElement(seqlist L, int i, Element_Type x) if (iL.listlen) error(“超出范圍”); else x=L .datai-1;,Page 36,2.2 順序表,基本 運算,按值查詢： int List_Locate (seqlist L, Element_Type x) int i; for (i=0; iL.listlen; i+) if (L.datai=x)

18、 return (i+1); /C語言中數(shù)組元素下標(biāo)比序號少1 return (0);,Page 37,2.2 順序表,基本 運算,插入元素： 在順序表L的第i個元素ai前插入一個元素x時，如果能插入，則需要依次執(zhí)行下列操作： 將aian向后移動一個元素的位置。 將x插入到第i個位置上，實現(xiàn)插入。 修改表的長度：因為表長度是順序表一個不可分割的分量。 注意： 第步移動時需要從an開始，依次倒退直到將ai向后移動一個元素位置,Page 38,2.2 順序表,基本 運算,插入元素： void List_Insert(seqlist *L,int i,Element_Type x) int j; i

19、f (L-listlen=maxlen) error(“overflow”); else if (iL-listlen-1) error(“position error”); else for (j=L-listlen-1; j=i-1; j-) L-dataj+1=L-dataj;/向后整體移動 L-datai-1=x; /在第i個位置插入內(nèi)容 L-listlen+; /修改表長,Page 39,2.2 順序表,基本 運算,刪除元素List_Delete(L,i)： 如果能從順序表L中刪除第i個元素ai，則需要依次執(zhí)行下列操作： 將ai+1an依次向前移動一個元素的位置，從而將ai“擠掉”。

20、 修改表的長度（表長度減1）。 注意： 第步移動時需要從ai+1開始，依次向后操作直到將an向前移動一個元素位置。移動過程與插入元素時移動方向恰好相反,Page 40,2.2 順序表,基本 運算,刪除元素List_Delete(L,i)： void List_Delete(seqlist *L, int i) int j; if (L-listlenL-listlen) error(“position error”); else for (j=i; jlistlen-1; j+) L-dataj-1=L-dataj;/向前整體移動 L-listlen-; /修改表長,Page 41,2.2 順

21、序表,應(yīng)用,例1：假設(shè)線性表L元素遞增有序，設(shè)計算法在該表中插入元素x，要求插入后L仍遞增有序。從后往前找 void List_Insert_1(seqlist *L, Element_Type x) int i=L-listlen-1; if (i=maxlen-1) error(“overflow”); else while (i=0,Page 42,2.2 順序表,應(yīng)用,例2：假設(shè)線性表L元素遞增有序，設(shè)計算法在該表中刪除重復(fù)的元素。 求解方法分析：設(shè)變量i從頭開始依次指示表中各元素以搜索其后繼中的同值元素。每當(dāng)i指向一個元素時，可能會有如下幾種操作： 若該元素已經(jīng)到了表尾，無后繼，則求

22、解結(jié)束。 若datai=datai+1，則應(yīng)刪除datai+1中的元素。 否則，當(dāng)前元素的同值元素搜索結(jié)束，需要轉(zhuǎn)向下一個元素的搜索,Page 43,2.2 順序表,應(yīng)用,例2：假設(shè)線性表L元素遞增有序，設(shè)計算法在該表中刪除重復(fù)的元素。 void List_Delete_1(seqlist *L) int i=1, j; while (ilistlen-1) /第i個元素還有后繼 if (L-datai=L-datai+1) for (j=i+2; jlistlen-1; j+) L-dataj-1=L-dataj;/向前整體移動 L-listlen-; /修改表長 else i+; /轉(zhuǎn)入下

23、一個元素的同值元素搜索,Page 44,2.2 順序表,應(yīng)用,練習(xí)1. 上述例2中，若順序表元素不是遞增的，如何設(shè)計算法實現(xiàn)同值元素刪除？ 練習(xí)2. 上述例2也可以采用另一種方法：將每一個搜索到需要保留的元素放到表的左邊連續(xù)空間中。自己實現(xiàn)。 練習(xí)3. 假設(shè)線性表A、B分別表示一個集合，設(shè)計算法判斷集合A是不是集合B的子集。若是，返回1；否則返回0. 練習(xí)4. 設(shè)計算法將遞增有序的順序表A和B中的元素合并為一個遞增有序的順序表C。 練習(xí)5. 結(jié)合教材內(nèi)容，思考上述算法的時間復(fù)雜度,Page 45,2.3 鏈表,概念,鏈表：線性表的鏈接存儲方式。 結(jié)點結(jié)構(gòu)示意圖： 結(jié)點由兩部分組成，即存放元素值

24、的部分和存放后繼元素地址的部分，從而使得物理位置不相鄰的元素邏輯上具有先后次序關(guān)系。由于通過地址將元素鏈接起來，因此將這種線性表稱為鏈表,Page 46,2.3 鏈表,概念,靜態(tài)鏈表：用數(shù)組來存儲元素的值和地址。在程序執(zhí)行過程中數(shù)組元素個數(shù)固定，因此成為靜態(tài)鏈表。后繼next中存放數(shù)組下標(biāo)即可,Page 47,2.3 鏈表,概念,動態(tài)鏈表：在事先難以估計線性表中元素個數(shù)或為了節(jié)省空間，可以根據(jù)實際問題需要臨時、動態(tài)地分配存儲空間，即每個結(jié)點都是程序運行時所產(chǎn)生的動態(tài)變量，因此稱為動態(tài)鏈表。 typedef struct Element_Type data; /存放數(shù)據(jù)的字段 struct no

25、de *next; /指向后繼元素的指針 node,Page 48,2.3 鏈表,概念,把指向表頭結(jié)點的指針稱為頭指針。從而可以定義動態(tài)鏈表變量： node *head; 例如：*head; (*head).next也可寫作head-next,Page 49,2.3 鏈表,概念,第i元素位置插入：s-next=p-next; p-next=s; 表頭(第1個元素位置插入)：s-next=head; head=s; 帶頭結(jié)點的單鏈表： 優(yōu)點：各結(jié)點操作統(tǒng)一。 【不做特殊說明，一般指帶頭結(jié)點的單鏈表,Page 50,2.3 鏈表,基本 運算,初始化線性表： void List_Initial (n

26、ode *head) head=(node *) malloc(size of (node); /產(chǎn)生頭結(jié)點 head-next=NULL; /設(shè)置后繼指針為空,Page 51,2.3 鏈表,基本 運算,求表長度： 在鏈表中，求表長度需要逐一數(shù)出元素個數(shù)。 int List_Length(node *head) int n=0; node *p=head-next; while (p!=NULL) n+; p=p-next; return (n);,Page 52,2.3 鏈表,基本 運算,按照序號取元素（取出的元素放在變量x里）： node *List_GetElement(node *he

27、ad, int i) node *p=head; int j=0; while (j!=i,Page 53,2.3 鏈表,基本 運算,按值查詢： node *List_Locate (node *head, Element_Type x) node *p=head-next; while (p!=NULL,Page 54,2.3 鏈表,基本 運算,插入元素： void List_Insert(node *head, int i, Element_Type x) node *p=head; int k=0; node *s; while (k!=i-1,Page 55,2.3 鏈表,基本 運算,

28、刪除元素List_Delete(L,i)： void List_Delete(node *head, int i) node *u,*p; p=List_GetElement(head, i-1); if (p=NULL | p-next=NULL) error(“序號錯誤”); else u=p-next; p-next=u-next; free(u);,Page 56,2.3 鏈表,應(yīng)用,例1. 設(shè)計算法判斷鏈表中元素是否遞增。若遞增，則返回1，否則，返回值0。 int dzpd( node *head) node *p=head-next; if (p=NULL) return (1);

29、 while (p-next!=NULL) if (p-datanext-data) p=p-next; else return (0); return (1);,Page 57,2.3 鏈表,應(yīng)用,例2. 設(shè)遞增有序的鏈表head表示一個集合，插入值為x的元素結(jié)點，仍保持遞增有序。(假設(shè)無重復(fù)元素) void List_Insert_2( node *head, Element_Type x) node *u, *p=head; while (p-next!=NULL,Page 58,2.3 鏈表,應(yīng)用,例3. 設(shè)計算法復(fù)制鏈表A中的內(nèi)容到B表中。 void List_Copy( node

30、*A, node *B) node *p=A-next, *r,*u; B=(node *)malloc(size of (node); r=B; /設(shè)置B的尾指針 while (p!=NULL) u=(node *) malloc(size of (node); u-data=p-data; r-next=u; r=u; p=p-next; r-next=NULL; /尾結(jié)點的后繼指針置NULL,Page 59,2.3 鏈表,應(yīng)用,練習(xí)1. 將鏈表A中的元素復(fù)制到鏈表B中，使得B表元素與A表元素次序相反。 練習(xí)2.將鏈表A中的元素復(fù)制到鏈表B中，使得B表元素遞增有序。 練習(xí)3. 假設(shè)鏈表A、

31、B分別表示一個集合，設(shè)計算法判斷集合A是不是集合B的子集。若是，返回1；否則返回0. 練習(xí)4. 設(shè)遞增有序的鏈表A和B中分別表示一個集合，設(shè)計算法實現(xiàn)C=AB。 練習(xí)5. 設(shè)遞增有序的鏈表A和B中分別表示一個集合，設(shè)計算法實現(xiàn)C=AB,Page 60,2.4 其他形式的鏈表,其他 鏈表,單循環(huán)鏈表 注意： 單循環(huán)鏈表可以不帶頭結(jié)點； 尾結(jié)點的變化導(dǎo)致算法設(shè)計的改變：注意尾結(jié)點的判斷。 在單循環(huán)鏈表中，可以從任一結(jié)點出發(fā)搜索到其他結(jié)點,Page 61,2.4 其他形式的鏈表,其他 鏈表,帶尾指針的單循環(huán)鏈表 注意： 帶尾指針的單循環(huán)鏈表可以不帶頭結(jié)點； 設(shè)置尾指針，方便地搜索到表頭和表尾指針。

32、思考：將帶尾指針的單循環(huán)鏈表A和B合并的算法,Page 62,2.4 其他形式的鏈表,其他 鏈表,雙鏈表結(jié)構(gòu) 注意： 如果要求能夠盡快求出任一結(jié)點的前趨，則應(yīng)采用雙鏈表； 每個結(jié)點除了有后繼指針，增設(shè)一個前趨指針。 思考：雙鏈表的插入和刪除操作,Page 63,2.4 其他形式的鏈表,其他 鏈表,雙鏈表結(jié)構(gòu) typedef struct Element_Type data; dulnode *prior; dulnode *next; dulnode,Page 64,2.4 其他形式的鏈表,其他 鏈表,雙鏈表結(jié)構(gòu)刪除結(jié)點 void del_dulist(dulnode *L,dulnode *

33、p) p-prior-next=p-next ; p-next-prior=p-prior ; delete p ;,Page 65,2.4 其他形式的鏈表,其他 鏈表,雙鏈表結(jié)構(gòu)插入結(jié)點（前插） DInsert_B (dulnode *L, dulnode *p, Element_type x) dulnode *s; s=(dulnode *) malloc(size of (dulnode); s-data=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; /*注意此句位置，結(jié)點信息不能丟*/,Page 66,謝謝大家,數(shù)據(jù)

34、結(jié)構(gòu),李 凱,2013年11月,第四章 棧和隊列,Page 68,4.1 棧 4.2 隊列 4.3 遞歸,內(nèi)容 設(shè)置,Page 69,4.1 棧,定義,定義：棧是一種只能在一端插入或刪除的線性表。 （棧是一種運算受限的線性表）。 若棧中無元素，則稱之為空棧。 棧的特點：先進(jìn)后出（或后進(jìn)先出）。 稱插入、刪除的一端叫棧頂（TOP），另一端叫棧底（BOTTOM,Page 70,4.1 棧,基本 操作,置棧為空setnull(S)。 判斷是否為空empty(S)。 取棧頂top(S,x) 。注：棧頂未刪。 入棧push(S,x)：將值為x的元素插到棧S中。 出棧pop(S,x)：注：棧頂刪。 刪除棧

35、S的棧頂元素，將此元素放到變量x中去。 判斷棧是否滿full(S),Page 71,4.1 棧,順序棧,define maxlen 100 /假設(shè)元素個數(shù)最大為100 typedef struct Element_Type datemaxlen; /定義存儲數(shù)值 int top; /定義棧頂位置 seqstack; seqstack S, S1; S,Page 72,4.1 棧,順序棧 運算,置棧為空setnull(S)。 void setnull(seqstack S) S.top=-1; 判斷是否為空empty(S)。 int empty(seqstack S) if (S.top=-1)

36、 return (1); else return (0);,Page 73,4.1 棧,順序棧 運算,取棧頂top(S,x) 。 void top(seqstack S, Element_Type x) if empty(S) error(“棧為空！”); else x=S.dataS.top; 入棧push(S,x)： void push(seqstack S, Element_Type x) if (S.top=maxlen-1) error(“溢出”); else S.data+S.top=x;,Page 74,4.1 棧,順序棧 運算,出棧pop(S,x)： void pop(seqs

37、tack S, Element_Type x) if empty(S) error(“?？铡?; else x=S.dataS.top-; 判斷棧是否滿full(S) 。 int full(seqstack S) if (S.top=maxlen-1) return (1); else return (0);,Page 75,4.1 棧,鏈棧,typedef struct Element_Type data; /存放數(shù)據(jù)的字段 struct stacknode *next; /指向后繼元素的指針 stacknode; 思考：采用不帶頭結(jié)點的單鏈表結(jié)構(gòu)實現(xiàn)鏈棧，棧頂位置應(yīng)放在鏈頭還是鏈尾,Pag

38、e 76,4.1 棧,鏈?；具\算,置棧為空setnull(S)。 判斷是否為空empty(S)。 取棧頂top(S,x) 。 入棧push(S,x)：將值為x的元素插到棧S中。 出棧pop(S,x)。 刪除棧S的棧頂元素，將此元素放到變量x中去。 判斷棧是否滿full(S) 。 【作為練習(xí)題，自己實現(xiàn),Page 77,4.2 隊列,定義,定義：隊列是一種只能在一端插入，在另一端刪除的線性表。 （隊列也是一種運算受限的線性表）。 若隊列中無元素，則稱之為空隊列。 隊列的特點：先進(jìn)先出(FIFO, First In First Out)。 稱允許刪除的一端叫隊頭(front)，另一端叫隊尾(re

39、ar,Page 78,4.2 隊列,基本 操作,置隊列為空setnull(Q)。 判斷是否為空empty(Q)。 取隊頭元素front(Q,x) 。注：隊頭未刪。 入隊EnQueue(Q,x)： 將值為x的元素插到隊列Q中。 出隊OutQueue(Q,x)：注：隊頭刪。 刪除隊列Q的隊頭元素，將此元素放到變量x中去。 判斷隊列是否滿full(Q),Page 79,4.2 隊列,順序 隊列,順序隊列存儲方式的思考： 假溢出的現(xiàn)象：rear=maxlen-1，但是前面還有一些已經(jīng)出隊的空間，從而使得后來的元素?zé)o法入隊。 循環(huán)隊列：把數(shù)組設(shè)想成首尾相接的環(huán)形， 存儲在其中的隊列稱循環(huán)隊列。 讓sq0

40、接在sqM-1之后,Page 80,4.2 隊列,循環(huán)隊列的問題,Page 81,4.2 隊列,順序 隊列,循環(huán)隊列的實現(xiàn)要點： (1)存儲隊列的數(shù)組設(shè)想當(dāng)作首尾相接的數(shù)組,可以用求余運算實現(xiàn)。指針有變化，就要求余。 (2)為區(qū)別隊空、隊滿，占用一個存儲空間. 隊頭指針進(jìn)1: front = (front + 1) % maxlen; 隊尾指針進(jìn)1: rear = (rear + 1) % maxlen; 隊列初始化： front = rear = 0; 隊空條件： front = rear; 隊滿條件： (rear + 1) % maxlen = front,Page 82,4.2 隊列,順

41、序 隊列,define maxlen 100 /假設(shè)元素個數(shù)最大為100 typedef struct Element_Type datemaxlen; /定義存儲數(shù)值 int front, rear; /定義隊頭和隊尾 seqqueue; seqqueue Q, Q1; Q,Page 83,4.2 隊列,順序隊列運算,置隊列為空setnull(seqqueue Q)。 void setnull(seqqueue Q) Q.front=0; Q.rear=0; 判斷是否為空empty(Q)。 int empty(seqqueue Q) if (Q.front=Q.rear) return (1

42、); else return (0);,Page 84,4.2 隊列,順序隊列運算,取隊頭front(Q,x) 。 void front(seqqueue Q, Element_Type x) if (empty(Q) error(“隊列為空！”); else x=Q.dataQ.front; 入隊EnQueue(Q,x)： void EnQueue(seqqueue Q, Element_Type x) if (full(Q) error(“溢出”); else Q.dataQ.rear=x; Q.rear=(Q.rear+1)%maxlen;,Page 85,4.2 隊列,順序隊列運算,出

43、隊OutQueue(Q,x)： void OutQueue(seqqueue Q, Element_Type x) if (empty(Q) error(“隊列空”); else x=Q.dataQ.front; Q.front=(Q.front+1)%maxlen; 判斷隊列是否滿full(Q) 。 int full(seqqueue Q) if (Q.rear+1)%maxlen=Q.front) return (1); else return (0);,Page 86,4.2 隊列,鏈隊列,思考：隊列的入隊和出隊操作分別在隊尾和隊頭進(jìn)行，因此有必要為隊尾添加一個指針，從而使得在隊頭實現(xiàn)刪

44、除，而在隊尾實現(xiàn)插入,Page 87,4.2 隊列,鏈隊列,typedef struct Element_Type data; /存放數(shù)據(jù)的字段 struct node *next; /下一個結(jié)點 node; typedef struct node *front, *rear; linkqueue,Page 88,4.2 隊列,鏈隊列運算,置隊列為空setnull(linkqueue *Q)。 void setnull(linkqueue *Q) Q-front=(node *) malloc( size of (node); Q-rear=Q-front; Q-front-next=NULL

45、; 判斷是否為空empty(Q)。 int empty(linkqueue *Q) return (Q-front=Q-rear);,Page 89,4.2 隊列,鏈隊列運算,取隊頭front(Q,x) 。 void front(linkqueue *Q, Element_Type x) if (empty(Q) error(“隊列為空！”); else x=Q-front-next-data; 入隊EnQueue(Q,x)： void EnQueue(linkqueue *Q, Element_Type x) node *p=(node *) malloc(size of (node); p

46、-data=x; p-next=NULL; Q-rear-next=p; Q-rear=p;,Page 90,4.2 隊列,鏈隊列運算,出隊OutQueue(Q,x)： void OutQueue(linkqueue *Q, Element_Type x) if (empty(Q) error(“隊列空”); else x=Q-front-next-data; node *u=Q-front-next; Q-front-next=u-next; free(u); if (Q-front-next=NULL) Q-rear=Q-front; /若刪除僅有的一個結(jié)點，則應(yīng)修改rear指針,Page

47、 91,4.3 遞歸,概念,遞歸的定義：若一個對象的組成包含了自身,或?qū)τ谝粋€對象的描述又用到該對象自身的現(xiàn)象,稱遞歸；在程序設(shè)計中,一個函數(shù)在其函數(shù)體內(nèi)直接或間接地調(diào)用自身, 稱遞歸函數(shù)。 在以下情況下，常常用到遞歸方法: 數(shù)學(xué)問題的定義，如求階乘 數(shù)據(jù)結(jié)構(gòu)的定義，如鏈表、樹的定義 某些實際問題的解法,Page 92,4.3 遞歸,概念,遞歸是一種重要算法,可使問題的描述和求解簡潔、清晰。 遞歸算法設(shè)計一般有兩步：首先，將大（規(guī)模）問題分解成多個較小的（求解過程、環(huán)境）相似的子問題；然后確定一個或多個可直接求解的最小子問題（遞歸結(jié)束條件）。 即兩個要點： 設(shè)計子問題，使其規(guī)模逐漸減小（經(jīng)有限

48、次遞歸后）逐漸接近遞歸終止條件； 設(shè)置遞歸結(jié)束條件，結(jié)束遞歸,Page 93,4.3 遞歸,例題,例1. 階乘函數(shù) （結(jié)束條件） （遞歸體） 求解階乘函數(shù)的遞歸算法 long Factorial ( long n ) long temp; if ( n = 0 ) return 1; else temp= n * Factorial (n-1); return temp;,規(guī)模減小,RetLoc2,Page 94,4.3 遞歸,分析,分析：當(dāng)調(diào)用函數(shù)時，系統(tǒng)為調(diào)用者構(gòu)造一個由參數(shù)表和返回地址組成的活動記錄（工作記錄），并將其壓入工作棧中，當(dāng)有多個嵌套調(diào)用時，每調(diào)用一次產(chǎn)生一個工作記錄，并依次壓

49、入工作棧中。當(dāng)函數(shù)返回時，彈出棧頂記錄。按照先調(diào)用后返回原則，將工作記錄依次彈出。 對于遞歸調(diào)用，由于調(diào)用與被調(diào)函數(shù)是同一個函數(shù)，因此與調(diào)用相關(guān)的概念是“層次”。 工作記錄,Page 95,4.3 遞歸,分析,計算Factorial時活動記錄的內(nèi)容,void main( ) long x; x=Factorial(4);,棧頂,RetLoc2,Page 96,謝謝大家,數(shù)據(jù)結(jié)構(gòu),李 凱,2013年11月,第五章 數(shù)組和廣義表,Page 98,5.1 數(shù)組 5.2 矩陣的壓縮存儲 5.3 廣義表,內(nèi)容 設(shè)置,Page 99,5.1 數(shù)組,定義,一維數(shù)組：具有相同類型的一組元素的有限序列。 二維數(shù)

50、組：元素為一維數(shù)組的一維數(shù)組。 N維數(shù)組是元素為（N-1）維數(shù)組的一維數(shù)組。 數(shù)組是一個靜態(tài)變量，無插入、刪除運算。 常見運算：計算元素地址、存取元素的值。 數(shù)組也是一種特殊的線性表（長度固定）。 二維數(shù)組中每個元素aij均屬于兩個向量：行、列向量，除邊界外,每個元素有兩個直接前趨和兩個直接后繼。同樣，三維數(shù)組中每個元素amnt均屬于三個向量，除邊界外,每個元素有三個直接前趨和三個直接后繼。依次類推，m維數(shù)組an1n2nm屬于m個向量，有m個直接前趨和m個直接后繼。(從這一點看，數(shù)組又不是一種線性表,Page 100,5.1 數(shù)組,存儲 結(jié)構(gòu),順序存儲結(jié)構(gòu)： (1) 行優(yōu)先：逐行存儲（E.g.

51、 PASCAL、C語言等）； (2) 列優(yōu)先：逐列存儲（E.g. Fortran語言等,Page 101,5.1 數(shù)組,存儲 結(jié)構(gòu),1) 行優(yōu)先：逐行存儲（E.g. PASCAL、C語言等,Page 102,5.1 數(shù)組,存儲 結(jié)構(gòu),2) 列優(yōu)先：逐列存儲（E.g. Fortran語言等,Page 103,5.2 矩陣的壓縮存儲,特殊 矩陣,當(dāng)矩陣中非零元素呈某種規(guī)律分布(特殊矩陣)，或出現(xiàn)大量零元素(稀疏矩陣)情況下，若用一般順序存儲(二維數(shù)組)會造成浪費。 方法： 為多個相同的元素只分配一個存儲單元; 對零元素不分配存儲空間,Page 104,5.2 矩陣的壓縮存儲,特殊 矩陣,對稱矩陣：

52、 滿足: a ij=a ji (0i, jn -1) 按行序為主序、存儲元素總數(shù): 為訪問元素,必須找到i,j與k的關(guān)系,Page 105,5.2 矩陣的壓縮存儲,特殊 矩陣,三角矩陣：矩陣的上(下)三角(不含對角線)中的元素均為常數(shù)的n階矩陣。 按行序為主序、存儲元素總數(shù): 為訪問元素,必須找到i,j與k的關(guān)系,Page 106,5.2 矩陣的壓縮存儲,稀疏 矩陣,定義：元素大部分為0,且分布沒有一定規(guī)律的矩陣。 壓縮存儲原則：只存矩陣的行列維數(shù)和每個非零元的行列下標(biāo)及其值(三元組)。 M由(0,1,12), (0,2,9), (2,0,-3), (2,5,14), (3,2,24), (4

53、,1,18), (5,01,15), (5,3,-7) 和矩陣維數(shù) (6,7)唯一確定,Page 107,5.2 矩陣的壓縮存儲,稀疏 矩陣,稀疏矩陣的壓縮存儲方法三元組表 將三元組按行優(yōu)先順序排列，則得到結(jié)點為三元組的線性表,Page 108,5.2 矩陣的壓縮存儲,稀疏 矩陣,稀疏矩陣的壓縮存儲方法：三元組表 typedef struct int i, j; /行、列下標(biāo) Element_Type v; /對應(yīng)元素值 tuple; Typedef struct int mu, nu, tu; /行數(shù)、列數(shù)、非零元素個數(shù) tuple datamaxnum; spmatrix,Page 109

54、,5.3 廣義表,定義,定義：廣義表L是由n個元素a1, a2, , an組成的有限序列，記作L=(a1, a2, , an)，其中n0為表長度；當(dāng)n=0時L為空表，記作L=( )；元素ai(i=1,2,n)可以是不可分割的原子(用小寫字母表示)，也可以是廣義表(用大寫字母表示)。 例如： 深度 長度 A=(a, b, c) 1 3 B=(A, (c, d) 2 2 C=(A, B) 3 2 D=(d, D) ? 2 (遞歸表) E=( ) 0 0 (空表,Page 110,5.3 廣義表,基本 運算,取表頭head(L): 取出廣義表A的第一個元素。 例如： A=(a, b, c); hea

55、d(A)=a 取表尾(去表頭)tail(L): 去掉表頭元素后得到的廣義表。 例如：tail(A)=(b, c) 說明： 其他操作可由此兩個基本操組合來實現(xiàn)： 例如：取第2個元素：去表頭+取表頭,Page 111,5.3 廣義表,鏈接存儲方式,不帶頭結(jié)點的單鏈表 第1個域里用0表示原子元素，用1表示廣義表元素。 缺點： 如果A最前面插 入一個元素，而 C表的內(nèi)容沒有 變化，此時，C 表內(nèi)容出現(xiàn)錯誤,Page 112,5.3 廣義表,鏈接存儲方式,帶頭結(jié)點的單鏈表 第1個域里用0表示原子元素，用1表示廣義表元素,Page 113,5.3 廣義表,練習(xí),head(p, h, w) tail(b,

56、k, p, h) head(a, b), (c, d) tail(a, b), (c, d) head(tail(a, b), (c, d) tail(head(a, b), (c, d) head(tail(head(a, b), (c, d,Page 114,謝謝大家,第五章 樹和二叉樹,樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。 5.1 樹的概念和基本術(shù)語 一、樹的定義 1.定義：樹(tree)是n(n0)個結(jié)點的有限集T；當(dāng)n=0時稱為空樹。在任一非空樹（n0）中： （1）有且僅有一個特定的結(jié)點，稱為樹的根(root)； （2）其余結(jié)點可分為m(m0)個互不相交的有限集：T1,T2,Tm，其中每一

57、個集合本身又是一棵樹，稱為根的子樹(subtree)。 說明：樹的定義中又用到樹的概念，即定義是遞歸的。 2.特點： 結(jié)點之間具有層次關(guān)系；某個元素最多只與上一層的一個元素有直接關(guān)系，而可以與其下一層的多個元素有直接關(guān)系,A,B,C,D,E,F,G,H,I,J,K,L,M,有子樹的樹,根,子樹的子樹,子樹,3.樹的表示樹形表示法（關(guān)系圖）、嵌套集合、廣義表表示、凹入表示,A(B(E, F(K,L), C(G), D(H, I, J,A* B* E* F* K* L* C* G* D* H* I* J,G,C,A,B,D,H,I,J,E,K,F,L,二、基本術(shù)語 結(jié)點(node)表示樹中的元素，

58、包括數(shù)據(jù)項及若干指向其子樹的分支 結(jié)點的度(degree)結(jié)點擁有的子樹數(shù) 葉子(leaf)度為0的結(jié)點 孩子(child)結(jié)點子樹的根稱為該結(jié)點的孩子 雙親(parents)孩子結(jié)點的上層結(jié)點叫該結(jié)點的 兄弟(sibling)同一雙親的孩子 樹的度一棵樹中最大的結(jié)點度數(shù) 結(jié)點的層次(level)從根結(jié)點算起，根為第一層，它的孩子為第二層 深度(depth)樹中結(jié)點的最大層次數(shù) 森林(forest)m(m0)棵互不相交的樹的集合 有序樹樹中結(jié)點的各子樹看成是從左到右有次序的，不能互換。反之，稱為無序樹,結(jié)點A的度：3 結(jié)點B的度：2 結(jié)點M的度：0,葉子：K，L，F(xiàn)，G，M，I，J,結(jié)點A的孩

59、子：B，C，D 結(jié)點B的孩子：E，F(xiàn),結(jié)點I的雙親：D 結(jié)點L的雙親：E,結(jié)點B，C，D為兄弟 結(jié)點K，L為兄弟,樹的度：3,結(jié)點A的層次：1 結(jié)點M的層次：4,樹的深度：4,結(jié)點F，G為堂兄弟 結(jié)點A是結(jié)點F，G的祖先,三、樹的基本操作,1、初始化 2、樹的遍歷 3、求指定結(jié)點所在樹的根結(jié)點 4、求指定結(jié)點的雙親結(jié)點 5、求指定結(jié)點的某一孩子結(jié)點 6、求指定結(jié)點的最右邊兄弟結(jié)點 7、將一棵樹插入到另一樹的指定結(jié)點下作為其子樹 8、刪除指定結(jié)點的某一子樹,5.2 二叉樹,一、定義與基本操作 1.定義：二叉樹是n(n0)個結(jié)點的有限集，它或 為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱為左子樹和

60、右子樹的互不相交的二叉樹構(gòu)成。 2.特點 二叉樹結(jié)點的度最大為2; 二叉樹的子樹有左、右之分，且其次序不能任意顛倒,即便是一個子樹,也必須分出左右. 3.基本形態(tài)(5種,A,只有根結(jié)點 的二叉樹,空二叉樹,右子樹為空,左子樹為空,左、右子樹 均非空,二、二叉樹性質(zhì) 性質(zhì)1：二叉樹的第i層至多有 2i-1 個結(jié)點(i 1,證明：用歸納法證明之： i=1時，只有一個根結(jié)點， 是對的 假設(shè)對所有j(1ji)命題成立，即第j層上至多有 個結(jié)點 那么，第i-1層至多有 個結(jié)點 又二叉樹每個結(jié)點的度至多為2 第i層上最大結(jié)點數(shù)是第i-1層的2倍，即 故命題得證,性質(zhì)2：深度為k的二叉樹至多有2k -1個結(jié)