《數(shù)據(jù)結(jié)構(gòu)》嚴(yán)蔚敏版教材PPT講義

《《數(shù)據(jù)結(jié)構(gòu)》嚴(yán)蔚敏版教材PPT講義》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)系第一章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語(yǔ)1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法和算法分1.4.1算法1.4.2算法設(shè)計(jì)的要求1.4.3算法效率的度量1.4.4算法的存儲(chǔ)空間的需求第一章緒論計(jì)算機(jī)是一門研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。這里面涉及到兩個(gè)問題：信息的表示信息的處理而信息的表示和組又直接關(guān)系到處理信息的程序的效率。隨著計(jì)算機(jī)的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，為了編寫出一個(gè)“好”的程序，必須分析待處理的對(duì)象的特征及

2、各對(duì)象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題.1.1什么是數(shù)據(jù)結(jié)構(gòu)眾所周知，計(jì)算機(jī)的程序是對(duì)信息進(jìn)行加工處理。在大多數(shù)情況下，這些信息并不是沒有組織，信息（數(shù)據(jù)）之間往往具有重要的結(jié)構(gòu)關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。那么，什么是數(shù)據(jù)結(jié)構(gòu)呢？先看以下幾個(gè)例子。例1、電話號(hào)碼查詢系統(tǒng)設(shè)有一個(gè)電話號(hào)碼薄，它記錄了N個(gè)人的名字和其相應(yīng)的電話號(hào)碼，假定按如下形式安排：(a1，b1)(a2，b2)…(an，bn)其中ai，bi(i=1，2…n)分別表示某人的名字和對(duì)應(yīng)的電話號(hào)碼要求設(shè)計(jì)一個(gè)算法，當(dāng)給定任何一個(gè)人的名字時(shí)

3、，該算法能夠打印出此人的電話號(hào)碼，如果該電話簿中根本就沒有這個(gè)人，則該算法也能夠報(bào)告沒有這個(gè)人的標(biāo)志。算法的設(shè)計(jì)，依賴于計(jì)算機(jī)如何存儲(chǔ)人的名字和對(duì)應(yīng)的電話號(hào)碼，或者說依賴于名字和其電話號(hào)碼的結(jié)構(gòu)。數(shù)據(jù)的結(jié)構(gòu)，直接影響算法的選擇和效率。上述的問題是一種數(shù)據(jù)結(jié)構(gòu)問題。可將名字和對(duì)應(yīng)的電話號(hào)碼設(shè)計(jì)成：二維數(shù)組、表結(jié)構(gòu)、向量。假定名字和其電話號(hào)碼邏輯上已安排成N元向量的形式，它的每個(gè)元素是一個(gè)數(shù)對(duì)(ai，bi)，1≤i≤n數(shù)據(jù)結(jié)構(gòu)還要提供每種結(jié)構(gòu)類型所定義的各種運(yùn)算的算法。例2、圖書館的書目檢索系統(tǒng)自動(dòng)化問題例3、教師資料

4、檔案管理系統(tǒng)例4、多叉路口交通燈的管理問題P3通過以上幾例可以直接地認(rèn)為：數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系，并對(duì)這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算，而且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。1.2基本概念和術(shù)語(yǔ)數(shù)據(jù)(Data):是對(duì)信息的一種符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)元素(DataElement):是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位

5、。數(shù)據(jù)對(duì)象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu)數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。通常分為四類基本結(jié)構(gòu)：一、集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。二、線性結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。三、樹型結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。四、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組

6、：Data-Structure=(D，S)其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。例復(fù)數(shù)的數(shù)據(jù)結(jié)構(gòu)定義如下：Complex=(C，R)其中：C是含兩個(gè)實(shí)數(shù)的集合﹛C1，C2﹜，分別表示復(fù)數(shù)的實(shí)部和虛部。R={P}，P是定義在集合上的一種關(guān)系{〈C1，C2〉}。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)對(duì)象可以是有限的，也可以是無限的。數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對(duì)象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對(duì)象，而且要描述數(shù)據(jù)對(duì)象各元素之間的相互關(guān)系。抽象數(shù)據(jù)類型：一個(gè)數(shù)學(xué)模型以及定義在該

7、模型上的一組操作。抽象數(shù)據(jù)類型實(shí)際上就是對(duì)該數(shù)據(jù)結(jié)構(gòu)的定義。因?yàn)樗x了一個(gè)數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組算法。用三元組描述如下：（Ｄ，Ｓ，Ｐ）數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中有兩種不同的表示方法：順序表示和非順序表示由此得出兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu):用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放地址的指針（），用此指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)類型：在一種程序設(shè)計(jì)語(yǔ)言中，變量所具有的數(shù)據(jù)種類。例1、在FORTRAN語(yǔ)言中，變

8、量的數(shù)據(jù)類型有整型、實(shí)型、和復(fù)數(shù)型例2、在C語(yǔ)言中數(shù)據(jù)類型：基本類型和構(gòu)造類型基本類型：整型、浮點(diǎn)型、字符型構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義數(shù)據(jù)對(duì)象：某種數(shù)據(jù)類型元素的集合。例3、整數(shù)的數(shù)據(jù)對(duì)象是{…-3，-2，-1，0，1，2，3，…}英文字符類型的數(shù)據(jù)對(duì)象是{A，B，C，D，E，F(xiàn)，…}1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)P111.4算法和算法