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

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

用小圓圈代表數(shù)據(jù)元素，用小圓圈之間的連線(xiàn)代表小圓圈對(duì)應(yīng)的數(shù)據(jù)元素之間的關(guān)系，如果強(qiáng)調(diào)關(guān)系的方向性，可用帶箭頭的線(xiàn)段表示關(guān)系。具體地講，若d1和d2表示兩個(gè)數(shù)據(jù)元素，它們具有關(guān)系＜d1,d2＞，則表示為d1d22020/12/1712ppt課件1.5數(shù)據(jù)結(jié)構(gòu)的分類(lèi)1.5.1集合如果數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間不考慮關(guān)系問(wèn)題（無(wú)前驅(qū)/后繼之分），則稱(chēng)這種結(jié)構(gòu)為集合。在集合中，各元素是“平等”的，它們的共同關(guān)系是：都屬于同一個(gè)集合。2020/12/1713ppt課件1.5.2線(xiàn)性結(jié)構(gòu)如果數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間只存在前后順序關(guān)系（每個(gè)元素都有唯一前趨和后繼，第一個(gè)元素可以沒(méi)有前驅(qū)，最后一個(gè)可以沒(méi)有后繼），則稱(chēng)這種結(jié)構(gòu)為線(xiàn)性結(jié)構(gòu)。線(xiàn)性結(jié)構(gòu)是一種最常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)。線(xiàn)性表、棧、隊(duì)列、串等均為線(xiàn)性結(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樹(shù)形結(jié)構(gòu)如果除一個(gè)特殊元素沒(méi)有前驅(qū)外，其他每個(gè)元素都有唯一的前驅(qū)（后繼個(gè)數(shù)不限），則稱(chēng)該結(jié)構(gòu)為樹(shù)型結(jié)構(gòu)（簡(jiǎn)稱(chēng)樹(shù)）。其中，將無(wú)前驅(qū)的元素稱(chēng)為樹(shù)根。用圖表示樹(shù)時(shí)，通常習(xí)慣將樹(shù)根畫(huà)在最上面。某元素的各后繼畫(huà)在該元素的下面，且連線(xiàn)不帶箭頭，隱含著從上到下。這樣，樹(shù)型結(jié)構(gòu)就象用一棵倒立的樹(shù)。圖1?1就是一個(gè)樹(shù)的例子，它代表的結(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ù)元素，均可有多個(gè)前趨和多個(gè)后繼。該種結(jié)構(gòu)也稱(chēng)網(wǎng)狀結(jié)構(gòu)。圖狀結(jié)構(gòu)表達(dá)能力最強(qiáng)，它可表達(dá)任意復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。例如，交通圖就是一種圖狀結(jié)構(gòu)，結(jié)點(diǎn)代表城市，連線(xiàn)（關(guān)系）代表城市間的道路。樹(shù)形結(jié)構(gòu)與圖狀結(jié)構(gòu)均稱(chēng)為非線(xiàn)性結(jié)構(gòu)。

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

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