第一章概述這一章，我們重點概述數(shù)據(jù)結(jié)構(gòu)中一些基本概念和基本方法，是以后各章的重要基礎(chǔ)。2020/12/171ppt課件1.1數(shù)據(jù)結(jié)構(gòu)的興起與發(fā)展

數(shù)據(jù)結(jié)構(gòu)問題起源于程序設(shè)計的發(fā)展。程序設(shè)計現(xiàn)在已經(jīng)歷了三個階段：無結(jié)構(gòu)階段結(jié)構(gòu)化程序設(shè)計階段面向?qū)ο箅A段2020/12/172ppt課件精品資料你怎么稱呼老師？如果老師最后沒有總結(jié)一節(jié)課的重點的難點，你是否會認(rèn)為老師的教學(xué)方法需要改進(jìn)？你所經(jīng)歷的課堂，是講座式還是討論式？教師的教鞭“不怕太陽曬，也不怕那風(fēng)雨狂，只怕先生罵我笨，沒有學(xué)問無顏見爹娘……”“太陽當(dāng)空照，花兒對我笑，小鳥說早早早……”計算機應(yīng)用系統(tǒng)中有兩個關(guān)鍵問題：表示：對象/實體及其關(guān)系在計算機中的表示。只有對象及其相互關(guān)系已存儲（表示）在計算機中，才能被進(jìn)一步處理；操作：對對象/實體進(jìn)行處理、訪問2020/12/175ppt課件[例]解一元二次方程ax2+bx+c=0.利用計算機解此方程，第一個問題就是如何在計算機中表示該方程。分析該方程，可知決定方程的是方程的三個系數(shù)值：a、b、c（在a≠0情況下，實際上只決定于一次項系數(shù)和常數(shù)項），而它們的次序表示它們分別屬于那一項，其他符號是為增加可讀性而引入的，因此，可用這三個系數(shù)的線性排列在計算機中表示該方程。例如，3x2-x+1=0表示為（3,-1,1）x2-3=0表示為(1,0,-3)2020/12/176ppt課件[例]計算機管理家譜。家譜管理主要實現(xiàn)家庭成員的登記、查詢及變更處理等。為突出主題，我們這里假定只考慮家庭中的父子關(guān)系。在這個問題中，實體對象是人（家庭成員），關(guān)系是父子關(guān)系。每個實體用一個記錄（元素）表示，包含姓名、出生日期、性別、死亡日期等。為了表示父子關(guān)系，在實體記錄中可增加若干字段，每個字段用于指示一個兒子/女兒，這樣，一個家族就構(gòu)成了一個層次結(jié)構(gòu)。在數(shù)據(jù)結(jié)構(gòu)中，該層次結(jié)構(gòu)稱為樹。圖1?1給出了一個具體的例子，其中，位于某結(jié)點下方的與其相連的各個結(jié)點，表示該結(jié)點的子女。2020/12/177ppt課件W1W12W121W122 W111W11W131W132W133W13W1112W1221W1111圖?一個家族結(jié)構(gòu)的樹表示2020/12/178ppt課件歸納起來，數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容為：為了在計算機上實現(xiàn)具體問題，所需的表示數(shù)據(jù)/信息及其關(guān)系應(yīng)如何組織（組織起來的數(shù)據(jù)就具有了結(jié)構(gòu)關(guān)系），以及如何對它們進(jìn)行基本操作。簡言之，研究數(shù)據(jù)的組織方式（結(jié)構(gòu)）及相應(yīng)的抽象操作。2020/12/179ppt課件1.3數(shù)據(jù)結(jié)構(gòu)的概念（1）數(shù)據(jù)：數(shù)據(jù)是描述客觀事物的信息的符號化，是計算機系統(tǒng)可加工處理的對象（2）數(shù)據(jù)類型：數(shù)據(jù)類型定義為：一個值的集合和定義在這個值集上的一組操作的總稱。（3）數(shù)據(jù)元素、數(shù)據(jù)項：能獨立、完整地描述問題世界中的實體的最小數(shù)據(jù)單位稱為數(shù)據(jù)元素（也稱記錄）。構(gòu)成數(shù)據(jù)元素的不可分割的數(shù)據(jù)單位，稱為數(shù)據(jù)項。（4）數(shù)據(jù)對象：同類數(shù)據(jù)元素的集合稱為數(shù)據(jù)對象。有了上面幾個概念，我們就可以給出數(shù)據(jù)結(jié)構(gòu)的概念了。（5）數(shù)據(jù)結(jié)構(gòu)：我們把數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)。進(jìn)一步地，我們稱相互之間存在著一定關(guān)系的數(shù)據(jù)元素的集合及定義在其上的基本操作（運算）為數(shù)據(jù)結(jié)構(gòu)。為了與后面要介紹的存儲結(jié)構(gòu)區(qū)別，有時也強調(diào)地稱數(shù)據(jù)結(jié)構(gòu)為數(shù)據(jù)的邏輯結(jié)構(gòu)。2020/12/1710ppt課件如果不考慮定義在數(shù)據(jù)結(jié)構(gòu)上的操作，則數(shù)據(jù)結(jié)構(gòu)也可借助集合論述語定義為：數(shù)據(jù)結(jié)構(gòu)是一個二元組（D,S），其中D是數(shù)據(jù)元素的有限集，S是D上的關(guān)系的有限集。在這個定義中，數(shù)據(jù)元素之間的關(guān)系采用集合論中關(guān)系的形式化描述方法來定義。型為<d1,d2>的二元關(guān)系中，我們稱d1為關(guān)系的前件，d2為后件。稱d2為d1的后繼，而d1為d2的前驅(qū)。2020/12/1711ppt課件1.4數(shù)據(jù)結(jié)構(gòu)的圖示

用小圓圈代表數(shù)據(jù)元素，用小圓圈之間的連線代表小圓圈對應(yīng)的數(shù)據(jù)元素之間的關(guān)系，如果強調(diào)關(guān)系的方向性，可用帶箭頭的線段表示關(guān)系。具體地講，若d1和d2表示兩個數(shù)據(jù)元素，它們具有關(guān)系＜d1,d2＞，則表示為d1d22020/12/1712ppt課件1.5數(shù)據(jù)結(jié)構(gòu)的分類1.5.1集合如果數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間不考慮關(guān)系問題（無前驅(qū)/后繼之分），則稱這種結(jié)構(gòu)為集合。在集合中，各元素是“平等”的，它們的共同關(guān)系是：都屬于同一個集合。2020/12/1713ppt課件1.5.2線性結(jié)構(gòu)如果數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間只存在前后順序關(guān)系（每個元素都有唯一前趨和后繼，第一個元素可以沒有前驅(qū)，最后一個可以沒有后繼），則稱這種結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)是一種最常見的數(shù)據(jù)結(jié)構(gòu)。線性表、棧、隊列、串等均為線性結(jié)構(gòu)。下圖表示的數(shù)據(jù)結(jié)構(gòu)可表示為：DS=(D,S)D={d1,d2,…,dn}S={r}r={<d1,d2>,<d2,d3>,…,<dn-1,dn>}

d1d2dn2020/12/1714ppt課件1.5.3樹形結(jié)構(gòu)如果除一個特殊元素沒有前驅(qū)外，其他每個元素都有唯一的前驅(qū)（后繼個數(shù)不限），則稱該結(jié)構(gòu)為樹型結(jié)構(gòu)（簡稱樹）。其中，將無前驅(qū)的元素稱為樹根。用圖表示樹時，通常習(xí)慣將樹根畫在最上面。某元素的各后繼畫在該元素的下面，且連線不帶箭頭，隱含著從上到下。這樣，樹型結(jié)構(gòu)就象用一棵倒立的樹。圖1?1就是一個樹的例子，它代表的結(jié)構(gòu)的形式描述為：DS=(D,S)D={W1,W11,W12,W13,W111,W121,W122,W131,W132,W133,W1111,W1112,W1221}S={r}r={<W1,W11>,<W1,W12>,<W1,W13>,<W11,W111>,<W12,W121>,<W12,W122>,<W13,W131>,<W13,W132,>,<W13,W133>,<W111,W1111>,<W111,W1112>,<W122,W1221>}2020/12/1715ppt課件1.5.4圖狀結(jié)構(gòu)在圖狀結(jié)構(gòu)中，任一數(shù)據(jù)元素，均可有多個前趨和多個后繼。該種結(jié)構(gòu)也稱網(wǎng)狀結(jié)構(gòu)。圖狀結(jié)構(gòu)表達(dá)能力最強，它可表達(dá)任意復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。例如，交通圖就是一種圖狀結(jié)構(gòu)，結(jié)點代表城市，連線（關(guān)系）代表城市間的道路。樹形結(jié)構(gòu)與圖狀結(jié)構(gòu)均稱為非線性結(jié)構(gòu)。

2020/12/1716ppt課件1.6數(shù)據(jù)結(jié)構(gòu)的存儲----存儲結(jié)構(gòu)1.6.1存貯器表示問題本課程中，數(shù)據(jù)結(jié)構(gòu)的存儲問題，除最后一章外，都針對內(nèi)存。最后一章將集中討論外存的數(shù)據(jù)結(jié)構(gòu)存儲。大多數(shù)高級語言支持的訪問存貯器的方式是相當(dāng)高級的，隱蔽了存貯器的許多特性，不利于表示數(shù)據(jù)的存貯結(jié)構(gòu)。不過，許多高級語言都提供按數(shù)組訪問存貯器的方式。數(shù)組很接近存貯器，所以我們決定用高級語言中的數(shù)組模擬計算機存貯器。另外，C/C++中的指針的概念相當(dāng)接近內(nèi)存的地址，所以，使用C/C++，可用簡單的方式，近乎得到機器指令的效果。2020/12/1717ppt課件1.6.2存貯映象(存儲結(jié)構(gòu))問題數(shù)據(jù)結(jié)構(gòu)的存貯映象，是指數(shù)據(jù)結(jié)構(gòu)在計算機中的存儲方式/方法，是數(shù)據(jù)結(jié)構(gòu)的另一種表示方式，稱為數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)/方式。將一個邏輯上的數(shù)據(jù)結(jié)構(gòu)存儲在計算機中，必需滿足下列兩點：內(nèi)容存儲：數(shù)據(jù)結(jié)構(gòu)中的各數(shù)據(jù)元素的內(nèi)容（數(shù)據(jù)），都分別存貯在一個獨立的可訪問的存貯區(qū)中;關(guān)系存儲：數(shù)據(jù)元素的存放方式方法，必須能顯示地或隱式地體現(xiàn)數(shù)據(jù)元素間的邏輯關(guān)系。這兩點是存貯映象所應(yīng)有的必要條件。在滿足上述必要條件的基礎(chǔ)上，存貯映象還應(yīng)考慮存貯使用效率（空間復(fù)雜度）及數(shù)據(jù)結(jié)構(gòu)的操作的實現(xiàn)的方便性等。2020/12/1718ppt課件1.6.3基本存儲方法一、順序存儲這是一種主要面向線性關(guān)系的存貯方法。對線性數(shù)據(jù)結(jié)構(gòu)，可將其數(shù)據(jù)元素，按相應(yīng)的線性關(guān)系下的前后次序，存貯在物理存貯器中，使得數(shù)據(jù)元素在此線性關(guān)系下的邏輯次序與它們在存貯器中的存放次序一致。這種存貯方式稱為順序方法（也稱連續(xù)方法）。為了能使存貯次序表達(dá)邏輯次序，顯然，在存貯器中，任意相鄰兩數(shù)據(jù)元素之間的存貯單元數(shù)目應(yīng)相等。2020/12/1719ppt課件[例]設(shè)有數(shù)據(jù)結(jié)構(gòu)DS=（D,S），其中，D={d1,d2,d3,d4}，S={r}，r={<d1,d2>，<d2,d3>，<d3,d4>}D中每個元素需占用兩個存貯單元，則該結(jié)構(gòu)的順序存貯結(jié)構(gòu)如下圖所示（稱存貯結(jié)構(gòu)圖）.d1d2d3d4……2020/12/1720ppt課件二、鏈?zhǔn)浇Y(jié)構(gòu)每個數(shù)據(jù)元素的存儲區(qū)分兩大部分，第一部分為數(shù)據(jù)區(qū)，存貯元素的內(nèi)容，第二部分為指針區(qū)，存放該數(shù)據(jù)元素與其它數(shù)據(jù)元素之間的關(guān)系信息，這種關(guān)系信息一般為地址（與此數(shù)據(jù)元素相關(guān)的其他數(shù)據(jù)元素的存貯地址）。對于線性結(jié)構(gòu)，指針區(qū)中可以只設(shè)一個地址；對非線性關(guān)系，可能需多個地址。另外需指出的是，數(shù)據(jù)元素的存貯區(qū)之間，可以是連續(xù)的，也可不連續(xù)。[例]對上例中的數(shù)據(jù)結(jié)構(gòu)，它的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)如表1?1所示。在該表中，假定每個元素占2個存儲單元，第一個存儲元素內(nèi)容，第二個存儲關(guān)系。這里，關(guān)系用后繼地址描述，元素x的“關(guān)系指示”中存放x的后繼的地址。2020/12/1721ppt課件地址數(shù)據(jù)關(guān)系指示A+02d384d11068d4010d22………2020/12/1722ppt課件[例]設(shè)數(shù)據(jù)結(jié)構(gòu)為DS=（D,S），其中D={d1,d2,d3,d4,d5,d6}，S={r1,r2}，r1={<d1,d3>，<d3,d4>,<d2,d6>}r2={<d1,d2>，<d3,d5>}它的一種鏈?zhǔn)酱尜A映象下表所示地址數(shù)據(jù)關(guān)系1關(guān)系2A+04d228812d124416D52024d3321628d632d4…………2020/12/1723ppt課件三、索引存儲索引存儲主要針對集合和線性表，面向檢索（查找）操作。它主要是在數(shù)據(jù)結(jié)構(gòu)的存儲區(qū)（稱數(shù)據(jù)區(qū)）外，增加一個（或若干個）索引區(qū)。索引區(qū)本身也是個線性表或其他數(shù)據(jù)結(jié)構(gòu)，結(jié)構(gòu)中每個元素用于記錄數(shù)據(jù)區(qū)中一個（對稠密索引）或一組（對非稠密索引）元素的存儲位置（起始位置）。索引存儲并不強調(diào)對關(guān)系的存儲，而主要針對數(shù)據(jù)內(nèi)容，所以，一般只適合集合結(jié)構(gòu)或線性結(jié)構(gòu)。2020/12/1724ppt課件三、散列存儲散列存儲（也稱雜湊法）是一種按元素內(nèi)容存儲元素的方法。其基本思想是：設(shè)置一個函數(shù)，稱為散列函數(shù)：元素內(nèi)容地址；規(guī)定元素內(nèi)容到存儲地址的映射；存儲時，通過散列函數(shù)求出元素的應(yīng)存儲的地址，按此地址存儲；讀取時，通過散列函數(shù)求出元素的存儲地址，按此地址讀??；與索引存儲類似，散列存儲也是面向內(nèi)容存儲，不適合存儲復(fù)雜數(shù)據(jù)結(jié)構(gòu)2020/12/1725ppt課件1.7數(shù)據(jù)結(jié)構(gòu)訪問接口

1.7.1訪問接口與邏輯結(jié)構(gòu)數(shù)據(jù)的訪問（也稱操作）是指對數(shù)據(jù)的讀、修改、加工、處理等操作。數(shù)據(jù)存在的目的是進(jìn)行操作。操作的種類很多，隨不同的應(yīng)用而不同。數(shù)據(jù)結(jié)構(gòu)中的一個重要的問題是：對每種數(shù)據(jù)結(jié)構(gòu)，如何設(shè)置一些操作，使得各種應(yīng)用都能通過這些操作就能實現(xiàn)對數(shù)據(jù)結(jié)構(gòu)的各種操作，我們把這類操作稱為數(shù)據(jù)結(jié)構(gòu)的基本操作或運算。操作的調(diào)用形式與規(guī)范，稱為該操作的接口；將針對某一數(shù)據(jù)結(jié)構(gòu)的基本操作的接口的全體，稱為該數(shù)據(jù)結(jié)構(gòu)的訪問接口；2020/12/1726ppt課件基本操作有下列關(guān)鍵點：抽象性：基本性：完備性：支撐性：2020/12/1727ppt課件1.7.2基本操作的種類盡管不同的數(shù)據(jù)結(jié)構(gòu)對應(yīng)不同的基本操作集合，但可按功能歸納為下列幾種基本類型：屬性讀取(Get)：屬性設(shè)置(Set)：查找插入刪除關(guān)系訪問遍歷2020/12/1728ppt課件1.7.2基本操作的實現(xiàn)操作的實體是計算機程序，因此，基本操作的實現(xiàn)，是個針對相應(yīng)的數(shù)據(jù)結(jié)構(gòu)編程的問題。由于程序是算法的實現(xiàn)，所以可以講操作實現(xiàn)也是算法實現(xiàn)問題2020/12/1729ppt課件1.8面向?qū)ο蠓椒ㄔ诿嫦驅(qū)ο蠓椒ㄖ?，將問題世界中所涉及的實體抽象為對象（Objects），每個對象，是對應(yīng)的實體的一個抽象模型，它刻畫實體的狀態(tài)和行為──狀態(tài)稱為對象的屬性或數(shù)據(jù)成員，行為稱為對象的方法或操作或服務(wù)，亦即對象由描述實體的狀態(tài)的屬性與用于改變自身狀態(tài)的操作兩大部分構(gòu)成：對象=屬性+操作類是對象的型，它與數(shù)據(jù)類型的概念是類似的──定義了對象的屬性的取值范圍與一組操作。每個類都是一批屬性與結(jié)構(gòu)類似且操作相同的對象的抽象。由于類中含數(shù)據(jù)與操作兩部分，所以它既可看作類型，又可看作模塊。繼承（下面即將介紹）的引入，會使這點更加明確。2020/12/1730ppt課件一、面向?qū)ο蠓椒ㄒ胤庋b是指將數(shù)據(jù)與相應(yīng)的操作作為一個整體看待。操作主要針對相應(yīng)的數(shù)據(jù)，用于改變對象的狀態(tài)。操作一般只改變相應(yīng)的數(shù)據(jù)，不改變封裝體（對象）外部的數(shù)據(jù)，使用者使用封裝體時，只需知道訪問操作，而無需顧及內(nèi)部實現(xiàn)方法這里的繼承是指對象/類之間的繼承。對兩個對象/類A和B，A的屬性是B的屬性的子集，A的操作在名稱與調(diào)用界面（與實現(xiàn)方法無關(guān)）方面是B的操作的子集，則稱B通過繼承A而來，或曰B由A派生而來（B是A的派生物）。這說明，B可以定義新的屬性和操作，B共享A的所有屬性，B可以重定義A中的操作（不改變名稱與接口），如果沒有重定義，B可以共享A中未被重定義的操作。2020/12/1731ppt課件多態(tài)性譯于Polymorphism一詞，這里Poly是許多的意思，morphus是采用某種格式的意思，這二者合起來的意思是：可采用多種形式的能力。在面向?qū)ο蠓椒ㄖ?，它的意思是：一個名字，多種語義；或相同界面，多種實現(xiàn)。消息：系統(tǒng)實質(zhì)上是一個以對象為狀態(tài)的狀態(tài)自動機，自動機中狀態(tài)的變化，就