數(shù)據(jù)結(jié)構(gòu)培訓(xùn)資料課件

第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法和算法分析第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)電子計(jì)算機(jī)的主要用途：早期：主要用于數(shù)值計(jì)算。解決問題的步驟：數(shù)學(xué)模型→解題算法→選擇計(jì)算機(jī)語言編程→測試→最終解答關(guān)鍵：如何得出數(shù)學(xué)模型當(dāng)今：擴(kuò)大到非數(shù)值計(jì)算領(lǐng)域。計(jì)算機(jī)的操作對象的關(guān)系更加復(fù)雜，數(shù)據(jù)元素間的相互關(guān)系有時(shí)無法用數(shù)學(xué)方程來描述。所處理的數(shù)據(jù)量大且具有一定的關(guān)系；而對其的操作也不再是單純的數(shù)值計(jì)算，更多地是對其進(jìn)行組織、管理和檢索等。電子計(jì)算機(jī)的主要用途：例1：學(xué)籍檔案管理假設(shè)一個(gè)學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表所示的學(xué)生信息：例1：學(xué)籍檔案管理假設(shè)一個(gè)學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下特點(diǎn)：每個(gè)學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號(hào)順序依次排列構(gòu)成一張表格；每列的數(shù)據(jù)類型一樣；表中每個(gè)學(xué)生的信息依據(jù)學(xué)號(hào)的大小存在著一種前后關(guān)系，這就是我們所說的線性結(jié)構(gòu)；對它的操作通常是插入、刪除、更新、按條件檢索某個(gè)學(xué)生的信息等等。特點(diǎn)：每個(gè)學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號(hào)順序依次排例2：輸出n個(gè)對象的全排列輸出3個(gè)對象的全排列可以使用下圖所示的形式描述：例2：輸出n個(gè)對象的全排列輸出3個(gè)對象的全排列可以使特點(diǎn)：在求解過程中，所處理的數(shù)據(jù)之間具有層次關(guān)系，這是我們所說的樹形結(jié)構(gòu)；對它的操作有：建立樹形結(jié)構(gòu)，輸出最低層結(jié)點(diǎn)內(nèi)容等等。特點(diǎn)：在求解過程中，所處理的數(shù)據(jù)之間具有層次關(guān)系，這是我們所例3：制定教學(xué)計(jì)劃制定教學(xué)計(jì)劃時(shí)，需考慮各門課程的開設(shè)順序。有些課程需要先導(dǎo)課程，有些課程則不需要，而有些課程又是其他課程的先導(dǎo)課程。比如，計(jì)算機(jī)專業(yè)課程的開設(shè)情況如下表所示：

例3：制定教學(xué)計(jì)劃制定教學(xué)計(jì)劃時(shí)，需考慮各門課程的開課程先后關(guān)系如圖：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6c7c8c11課程先后關(guān)系如圖：c1c9c4c2c12c10c11c5c3特點(diǎn)：課程之間的先后關(guān)系用圖結(jié)構(gòu)描述；通過實(shí)施創(chuàng)建圖結(jié)構(gòu)，按要求將圖結(jié)構(gòu)中的頂點(diǎn)進(jìn)行線性排序。特點(diǎn)：課程之間的先后關(guān)系用圖結(jié)構(gòu)描述；結(jié)論要使計(jì)算機(jī)能夠更有效地進(jìn)行這些非數(shù)值性處理，就必須弄清楚這些操作對象的特點(diǎn)、之間的關(guān)系，在計(jì)算機(jī)中的表示方式及各種操作的具體實(shí)現(xiàn)手段。因此，《數(shù)據(jù)結(jié)構(gòu)》研究的主要內(nèi)容是：數(shù)據(jù)元素之間的邏輯關(guān)系數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)采用何種操作實(shí)現(xiàn)算法的效率更高結(jié)論要使計(jì)算機(jī)能夠更有效地進(jìn)行這些非數(shù)值性處理，就必程序設(shè)計(jì)：為計(jì)算機(jī)處理問題編制一組指令集。算法：處理問題的策略。數(shù)據(jù)結(jié)構(gòu)：問題的數(shù)學(xué)模型。程序設(shè)計(jì)的實(shí)質(zhì)是對確定的問題選擇一種好的結(jié)構(gòu)，加上設(shè)計(jì)一種好的算法。程序=算法+數(shù)據(jù)結(jié)構(gòu)“Programs=Algorithm+DataStructures”瑞士學(xué)者NiklausWirth于1976年出版的書名。程序設(shè)計(jì)：為計(jì)算機(jī)處理問題編制一組指令集。程序=算課程任務(wù)：1.討論現(xiàn)實(shí)世界中數(shù)據(jù)的各種邏輯結(jié)構(gòu)及在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)；

2.進(jìn)行各種非數(shù)值運(yùn)算的算法。課程目的：掌握數(shù)據(jù)組織、存儲(chǔ)和處理的常用法，為進(jìn)行軟件開發(fā)或后續(xù)專業(yè)課程學(xué)習(xí)打下良好的基礎(chǔ)。課程內(nèi)容：數(shù)據(jù)結(jié)構(gòu)的基本概念、線性表、棧和隊(duì)列、串和數(shù)組、樹形結(jié)構(gòu)、圖結(jié)構(gòu)、查找、排序和文件等內(nèi)容。課程任務(wù)：1.討論現(xiàn)實(shí)世界中數(shù)據(jù)的各種邏輯結(jié)構(gòu)及在計(jì)算機(jī)中的第1章緒論

1.1什么是數(shù)據(jù)結(jié)構(gòu)

1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法和算法分析第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.數(shù)據(jù)是對客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)處理的符號(hào)的總稱。計(jì)算機(jī)程序加工的“原料”。1.數(shù)據(jù)例：一個(gè)利用數(shù)值分析方法解代數(shù)方程的程序，其處理對象是整數(shù)和實(shí)數(shù)；一個(gè)編譯程序或文字處理程序的處理對象是字符串。還有聲音、圖象、視頻等等通過編碼都屬于數(shù)據(jù)的范疇。例：一個(gè)利用數(shù)值分析方法解代數(shù)方程的程序，其處理對象2.數(shù)據(jù)元素

是數(shù)據(jù)的基本單位。數(shù)據(jù)中的一個(gè)“個(gè)體”，數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。2.數(shù)據(jù)元素例：一個(gè)整數(shù)“5”；一個(gè)字符“N”；圖中的一個(gè)頂點(diǎn)等。

復(fù)雜型數(shù)據(jù)元素由多個(gè)數(shù)據(jù)項(xiàng)組成，它通常攜帶著一個(gè)概念的多方面信息。例：一個(gè)學(xué)生的基本信息就是一個(gè)數(shù)據(jù)元素，其中的學(xué)號(hào)、姓名等被稱為“數(shù)據(jù)項(xiàng)”。

因此數(shù)據(jù)項(xiàng)是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。例：一個(gè)整數(shù)“5”；一個(gè)字符“N”；圖中的一個(gè)頂點(diǎn)等3.數(shù)據(jù)對象

性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的子集。例：整數(shù)數(shù)據(jù)對象是集合N={0，±1，±2，…}。英文字母數(shù)據(jù)對象是集合

C={‘A’，……，‘Z’}。如何選定數(shù)據(jù)對象將依問題而定！譬如，在學(xué)生管理系統(tǒng)中，可能以一個(gè)班級(jí)的學(xué)生記錄作為數(shù)據(jù)對象，也可能以一個(gè)年級(jí)的學(xué)生記錄作為數(shù)據(jù)對象。3.數(shù)據(jù)對象例：4.數(shù)據(jù)的邏輯結(jié)構(gòu)討論計(jì)算機(jī)系統(tǒng)中數(shù)據(jù)的組織形式及其相互關(guān)系。即相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)邏輯結(jié)構(gòu)的形式定義：數(shù)據(jù)邏輯結(jié)構(gòu)是一個(gè)二元組：

Data_structure={D,R}

其中，D是數(shù)據(jù)元素的有限集，R是D上的關(guān)系的集合。4.數(shù)據(jù)的邏輯結(jié)構(gòu)例：在計(jì)算機(jī)科學(xué)中，復(fù)數(shù)可取如下定義：復(fù)數(shù)數(shù)據(jù)的邏輯結(jié)構(gòu)

Complex=(C,R)

其中：C是含兩個(gè)實(shí)數(shù)的集合{c1,c2};R={P}，而P是定義在集合C上的一種關(guān)系{<c1,c2>}，其中有序偶<c1,c2>表示c1是復(fù)數(shù)的實(shí)部，c2是復(fù)數(shù)的虛部。

例：在計(jì)算機(jī)科學(xué)中，復(fù)數(shù)可取如下定義：復(fù)數(shù)數(shù)據(jù)的邏輯結(jié)構(gòu)4數(shù)據(jù)的邏輯結(jié)構(gòu)例：list=(D,S1),tree=(D,S2),graph=(D,S3)D={a,b,c,d,e}S1={<a,b>,<b,c>,<c,d>,<d,e>}S2={<a,b>,<a,c>,<b,d>,<b,e>}S3={<a,b>,<a,c>,<d,a>,<e,c>}4數(shù)據(jù)的邏輯結(jié)構(gòu)例：list=(D,S1),tree=(D邏輯結(jié)構(gòu)示意圖<a,b>,稱a是b的前驅(qū)，b是a的后繼。若某結(jié)點(diǎn)沒有前驅(qū)，則稱該結(jié)點(diǎn)為開始結(jié)點(diǎn)；若某結(jié)點(diǎn)沒有后繼，則稱該結(jié)點(diǎn)為終端結(jié)點(diǎn)；bacdelistaedbcgraphedbcatree（a,b,c,d,e）邏輯結(jié)構(gòu)示4.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)中所說的“關(guān)系”實(shí)際上是指數(shù)據(jù)元素之間的邏輯關(guān)系，又稱此為邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類:

1）集合：數(shù)據(jù)元素之間除“同屬于一個(gè)集合”的關(guān)系外無其它關(guān)系。2）線性結(jié)構(gòu)：數(shù)據(jù)元素間存在一對一的關(guān)系。3）樹形結(jié)構(gòu)：數(shù)據(jù)元素間存在一對多的關(guān)系。4）圖（網(wǎng)）狀結(jié)構(gòu)：數(shù)據(jù)元素間存在多對多的關(guān)系。4.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)：一對一非線性結(jié)構(gòu)樹形結(jié)構(gòu)：一對多圖狀結(jié)構(gòu)：多對多邏輯結(jié)構(gòu)集合線性結(jié)構(gòu)：一對一非線性結(jié)構(gòu)樹形結(jié)構(gòu)：一對多圖狀結(jié)構(gòu)：多對多邏5.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）存儲(chǔ)結(jié)構(gòu)：邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示(又稱映象)稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱存儲(chǔ)結(jié)構(gòu)。包括數(shù)據(jù)元素的表示和關(guān)系的表示。計(jì)算機(jī)中表示信息的最小單位是二進(jìn)制數(shù)的一位(bit)?？捎靡粋€(gè)由若干位組合起來形成的一個(gè)位串表示一個(gè)數(shù)據(jù)元素，通常稱這個(gè)位串為元素(Element)或結(jié)點(diǎn)(Node)。當(dāng)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成時(shí)，位串中對應(yīng)于各個(gè)數(shù)據(jù)項(xiàng)的子位串稱為數(shù)據(jù)域(DataField)。5.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）5.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）存儲(chǔ)的要求：既存儲(chǔ)各結(jié)點(diǎn)的數(shù)值又要存儲(chǔ)結(jié)點(diǎn)與結(jié)點(diǎn)之間的邏輯關(guān)系。四種基本的存儲(chǔ)結(jié)構(gòu)：順序、鏈接、索引、散列存儲(chǔ)。內(nèi)存空間、內(nèi)存地址程序在運(yùn)行期間所需存儲(chǔ)空間都在內(nèi)存中分配.……5.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）存儲(chǔ)的要求：既存儲(chǔ)各結(jié)點(diǎn)的數(shù)值1.順序存儲(chǔ)（用數(shù)組實(shí)現(xiàn)）存儲(chǔ)方法:把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在一組連續(xù)的存儲(chǔ)單元中,其結(jié)點(diǎn)之間的邏輯關(guān)系由存儲(chǔ)單元地址間的關(guān)系隱含表示。例：list的順序存儲(chǔ)結(jié)構(gòu)如下abcde200201202203204優(yōu)點(diǎn)：節(jié)省存儲(chǔ)空間，可實(shí)現(xiàn)對各結(jié)點(diǎn)的隨機(jī)訪問。

loc（i）＝q＋（i－1）×pq是第一個(gè)結(jié)點(diǎn)所占存儲(chǔ)單元的首地址；

p是每個(gè)結(jié)點(diǎn)所占單元數(shù)。1.順序存儲(chǔ)（用數(shù)組實(shí)現(xiàn)）存儲(chǔ)方法:把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在缺點(diǎn)：不便于修改。進(jìn)行插入、刪除運(yùn)算時(shí)可能要移動(dòng)一系列的數(shù)據(jù)元素。例：若刪除list結(jié)構(gòu)中的第三個(gè)結(jié)點(diǎn)c，則list的邏輯結(jié)構(gòu)變成(a,b,d,e)。

若在結(jié)點(diǎn)c前插入一個(gè)新的結(jié)點(diǎn)x，則list的邏輯結(jié)構(gòu)變成(a,b,x,c,d,e)。

邏輯結(jié)構(gòu)發(fā)生變化后，相應(yīng)的存儲(chǔ)結(jié)構(gòu)同樣發(fā)生變化baxdeab缺點(diǎn)：不便于修改。進(jìn)行插入、刪除運(yùn)算時(shí)可能要移動(dòng)一系列的數(shù)據(jù)2.鏈接存儲(chǔ)(用指針實(shí)現(xiàn))存儲(chǔ)方法：給每個(gè)機(jī)結(jié)點(diǎn)附加指針字段，用于存放相鄰結(jié)點(diǎn)的存儲(chǔ)地址。優(yōu)點(diǎn)：便于修改缺點(diǎn)：浪費(fèi)存儲(chǔ)空間例：list（a,b,c,d,e）的存儲(chǔ)結(jié)構(gòu)示意圖如下c208b200a202ed206200202206208204200202206208204b208a202ed206刪除結(jié)點(diǎn)c后(a,b,d,e)x200…c208b100a202ed206200202206208204100插入結(jié)點(diǎn)x后（a,b,x,c,d,e）2.鏈接存儲(chǔ)(用指針實(shí)現(xiàn))存儲(chǔ)方法：給每個(gè)機(jī)結(jié)點(diǎn)附加指針字段3.索引存儲(chǔ)（用數(shù)組實(shí)現(xiàn)）存儲(chǔ)方法：根據(jù)結(jié)點(diǎn)的序號(hào)確定結(jié)點(diǎn)的存儲(chǔ)地址。具體做法：建立索引表和結(jié)點(diǎn)表；將各結(jié)點(diǎn)的數(shù)值按任意順序存放在結(jié)點(diǎn)表中，而將每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址用順序存儲(chǔ)方法存入索引表中。例：list（a,b,c,d,e)的索引存儲(chǔ)結(jié)構(gòu)如下200204202201203200204201203a甲85d丁90c丙67e戊55b乙78100101102103104200201202203204索引表結(jié)點(diǎn)表索引表100101102103104刪除結(jié)點(diǎn)c后刪除結(jié)點(diǎn)c前后無變化3.索引存儲(chǔ)（用數(shù)組實(shí)現(xiàn)）存儲(chǔ)方法：根據(jù)結(jié)點(diǎn)的序號(hào)確定結(jié)點(diǎn)的4.散列存儲(chǔ)(用數(shù)組實(shí)現(xiàn))存儲(chǔ)方法：根據(jù)結(jié)點(diǎn)的值確定結(jié)點(diǎn)的存儲(chǔ)地址。具體做法：以結(jié)點(diǎn)中某個(gè)字段的值為自變量，通過某個(gè)函數(shù)（稱為散列函數(shù)）計(jì)算出對應(yīng)的函數(shù)值i，再把i當(dāng)作結(jié)點(diǎn)的存儲(chǔ)地址。例：假定list結(jié)構(gòu)中的5個(gè)結(jié)點(diǎn)數(shù)值是下列5個(gè)字符‘Wuhan’‘Nanjing’‘Shanghai’‘Xian’‘Beijing’

散列函數(shù)：Loc(key)=asc(left(key,1))mod8KeyWuhanNanjingShanghaiXianBeijingasc(key)8778838866Loc(key)76302XianBeijingShanghaiNanjingWuhan012345674.散列存儲(chǔ)(用數(shù)組實(shí)現(xiàn))存儲(chǔ)方法：根據(jù)結(jié)點(diǎn)的值確定結(jié)點(diǎn)

數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的兩個(gè)方面，在后面的課程中我們會(huì)看到，任何一個(gè)算法的設(shè)計(jì)取決于選定的數(shù)據(jù)（邏輯）結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于所采用的存儲(chǔ)結(jié)構(gòu)。

完整的數(shù)據(jù)結(jié)構(gòu)概念可認(rèn)為是由數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操作集三個(gè)部分組成：

Data_Structure＝（D，R，P）其中D是數(shù)據(jù)元素的有限集合；R是D集上關(guān)系的有限集合，P是對D的基本操作集。數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容完整的數(shù)據(jù)結(jié)構(gòu)概念可認(rèn)為是由數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操數(shù)據(jù)的邏輯結(jié)構(gòu)非線性結(jié)構(gòu)集合圖狀結(jié)構(gòu)有向圖無向圖樹形結(jié)構(gòu)一般樹二叉樹線性結(jié)構(gòu)一般線性表線性表推廣廣義表數(shù)組串受限線性表?xiàng)：完?duì)列

數(shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)系圖

邏輯結(jié)構(gòu)與所采用的存儲(chǔ)結(jié)構(gòu)線性表樹圖順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)復(fù)合存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)非線性結(jié)構(gòu)集合圖狀結(jié)構(gòu)有向圖無向圖樹形結(jié)構(gòu)一般6.數(shù)據(jù)類型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個(gè)概念，它最早出現(xiàn)在高級(jí)程序語言中，用以刻畫（程序）

操作對象的特性。

數(shù)據(jù)類型：是一組性質(zhì)相同的值的集合及定義于這個(gè)值集合上的一組操作的總稱。6.數(shù)據(jù)類型通用的計(jì)算機(jī)高級(jí)語言常見的有整數(shù)、實(shí)數(shù)（浮點(diǎn)數(shù)）、枚舉、字符、字符串、指針、數(shù)組、記錄文件等數(shù)據(jù)類型。譬如：整數(shù)類型通常用兩個(gè)字節(jié)或四個(gè)字節(jié)表示，分別表示范圍：-215～215-1、-231～231-1。對其允許施加的操作通常有：單目和雙目，分別是取正或取負(fù)運(yùn)算；加、減、乘、除、取模、等于、不等于、大于等關(guān)系（比較）運(yùn)算。通用的計(jì)算機(jī)高級(jí)語言常見的有整數(shù)、實(shí)數(shù)（浮點(diǎn)數(shù)）、枚依據(jù)“值”的不同特性，高級(jí)語言中數(shù)據(jù)類型可分為兩類：1）原子類型

原子類型的值是不可分解。如：C語言中的基本類型（整型、實(shí)型、字符型和枚舉型），指針型。2）結(jié)構(gòu)類型結(jié)構(gòu)類型的值是由若干成分按某種結(jié)構(gòu)組成，因此可以分解，且它的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。如：數(shù)組類型。依據(jù)“值”的不同特性，高級(jí)語言中數(shù)據(jù)類型可分為兩類：7.抽象數(shù)據(jù)類型（簡稱ADT）指一個(gè)數(shù)學(xué)模型及定義在此數(shù)學(xué)模型上的一組操作?！俺橄蟆钡囊饬x在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。

為提高軟件復(fù)用率，近代程序設(shè)計(jì)方法學(xué)指出，一個(gè)軟件系統(tǒng)的框架應(yīng)建立在數(shù)據(jù)之上，而不是操作之上（后者是傳統(tǒng)的軟件設(shè)計(jì)方法所為）。即在構(gòu)成軟件系統(tǒng)的每個(gè)相對獨(dú)立的模塊上，定義一組數(shù)據(jù)和施于這些數(shù)據(jù)上的一組操作，并在模塊內(nèi)部給出這些數(shù)據(jù)的表示及其操作細(xì)節(jié)，而在模塊外部使用的只是抽象的數(shù)據(jù)和操作。7.抽象數(shù)據(jù)類型（簡稱ADT）ADT有兩個(gè)重要特征:1）數(shù)據(jù)抽象

用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。2）數(shù)據(jù)封裝

將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。ADT有兩個(gè)重要特征:抽象數(shù)據(jù)類型的描述方法：三元組表示（D，S，P）其中，D是數(shù)據(jù)對象，

S是D上的關(guān)系集，

P是對D的基本操作集。抽象數(shù)據(jù)類型的描述方法：ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉

數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉

基本操作：〈基本操作的定義〉

}ADT抽象數(shù)據(jù)類型名其中，數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼描述，

基本操作的定義格式為：基本操作名（參數(shù)表）初始條件：〈初始條件描述〉操作結(jié)果：〈操作結(jié)果描述〉A(chǔ)DT抽象數(shù)據(jù)類型名{基本操作有兩種參數(shù)：1）賦值參數(shù)：只為操作提供輸入值2）引用參數(shù)：以&打頭，除可提供輸入值外，還將返回操作結(jié)果。“初始條件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息?！安僮鹘Y(jié)果”說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則將其省略?；静僮饔袃煞N參數(shù)：例：抽象數(shù)據(jù)類型——

復(fù)數(shù)的定義

ADTComplex{

數(shù)據(jù)對象：D＝{e1,e2｜e1,e2∈RealSet}

數(shù)據(jù)關(guān)系：R＝{<e1,e2>|e1是復(fù)數(shù)的實(shí)數(shù)部分,

e2是復(fù)數(shù)的虛數(shù)部分}

基本操作：

InitComplex(&Z,v1,v2)

操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。

DestroyComplex(&Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。例：抽象數(shù)據(jù)類型——復(fù)數(shù)的定義

GetReal(Z,&realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。

GetImag(Z,&ImaPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImgPart返回復(fù)數(shù)Z的虛部值。

Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。}ADTComplexGetReal(Z,&realPart)第1章緒論

1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語

1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法和算法分析第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型可通過固有數(shù)據(jù)類型來表示和實(shí)現(xiàn)，即利用處理器中已存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實(shí)現(xiàn)的操作來組合新的操作。本課程在高級(jí)程序設(shè)計(jì)語言的虛擬層次上討論抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)，采用介于偽碼和Ｃ語言之間的類Ｃ語言作為描述工具，下面我們對其作一下簡要說明。抽象數(shù)據(jù)類型可通過固有數(shù)據(jù)類型來表示和實(shí)現(xiàn)，即利用處（1）預(yù)定義常量和類型：

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2Typedefintstatus

//status是函數(shù)的類型，

//其值是函數(shù)結(jié)果狀態(tài)代碼（1）預(yù)定義常量和類型：（2）數(shù)據(jù)結(jié)構(gòu)的表示（存儲(chǔ)結(jié)構(gòu)）

用類型定義（typedef）描述。數(shù)據(jù)元素類型約定為ElemType，由用戶在使用該數(shù)據(jù)類型時(shí)自行定義。（3）基本操作的算法

用以下形式的函數(shù)描述：函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）

{//算法說明語句序列

}//函數(shù)名（2）數(shù)據(jù)結(jié)構(gòu)的表示（存儲(chǔ)結(jié)構(gòu)）說明：除了函數(shù)的參數(shù)需要說明類型外，算法中使用的輔助變量可以不作變量說明，必要時(shí)對其作用給予注釋。當(dāng)函數(shù)返回值為函數(shù)結(jié)果狀態(tài)碼時(shí)，函數(shù)定義為status類型。為了便于算法描述，除了值調(diào)用方式之外，增添了C++語言的引用調(diào)用的參數(shù)傳遞方式。在形參表中，以&打頭的參數(shù)即為引用參數(shù)。說明：（4）賦值語句

簡單賦值變量名=表達(dá)式；

串聯(lián)賦值變量名1=變量名2=…變量名K=表達(dá)式；

成組賦值（變量名1，變量名2，…變量名K）=

（表達(dá)式1，表達(dá)式2，…表達(dá)式K）；（4）賦值語句

結(jié)構(gòu)名=結(jié)構(gòu)名；結(jié)構(gòu)名=（值1，值2，…，值K）；變量名[]=表達(dá)式；變量名[起始下標(biāo)..終止下標(biāo)]=

變量名[起始下標(biāo)..終止下標(biāo)]；

交換賦值變量名←→變量名；

條件賦值

變量名=條件表達(dá)式？表達(dá)式T：表達(dá)式F；結(jié)構(gòu)名=結(jié)構(gòu)名；（5）選擇語句

條件語句1if（表達(dá)式）語句；

條件語句2if（表達(dá)式）語句;else語句；（5）選擇語句

開關(guān)語句1

switch（表達(dá)式）{case值1:語句序列1；break；

…case值n:語句序列n；break；

default:語句序列n+1；}

開關(guān)語句2

switch{case條件1:語句序列1；break；

…case條件n:語句序列n；break；

default:語句序列n+1；}開關(guān)語句1（6）循環(huán)語句

For語句

for（賦初值表達(dá)式序列；條件；修改表達(dá)式序列）語句序列；

While語句

while（條件）語句序列；

Do-While語句

do{語句序列；

}while（條件）（6）循環(huán)語句（7）結(jié)束語句

函數(shù)結(jié)束語句

return表達(dá)式；

return；

Case結(jié)束語句

break；

異常結(jié)束語句

exit（異常代碼）；（7）結(jié)束語句（8）輸入輸出語句

輸入語句

scanf（[格式串]，變量1，…，變量n）；

輸出語句

printf（[格式串]，表達(dá)式1，…，表達(dá)式n）；通常省略格式串。（8）輸入輸出語句（9）注釋

單行注釋

//文字序列；（10）邏輯運(yùn)算約定

與運(yùn)算&&

：

如：A&&B，當(dāng)A的值為0時(shí)，不再對B求值。

或運(yùn)算||：如：A||B，當(dāng)A的值為非0時(shí)，不再對B求值。（9）注釋（11）基本函數(shù)

求最大值

max（表達(dá)式1，…，表達(dá)式n）；

求最小值

min（表達(dá)式1，…，表達(dá)式n）；

求絕對值

abs（表達(dá)式）；

求不足整數(shù)值

floor（表達(dá)式）；

求進(jìn)位整數(shù)值

ceil（表達(dá)式）；

判定文件結(jié)束

eof（文件變量）或eof；

判定行結(jié)束

eoln（文件變量）或eoln（11）基本函數(shù)第1章緒論

1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)

1.4算法和算法分析第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.算法定義

算法(Algorithm)是對特定問題求解步驟的一種描述，是為解決一個(gè)或一類問題給出的一個(gè)確定的、有限長的操作序列。計(jì)算機(jī)對數(shù)據(jù)的操作可分為數(shù)值性和非數(shù)值性兩種類型。在數(shù)值性操作中主要進(jìn)行的是算術(shù)運(yùn)算；而在非數(shù)值性操作中主要進(jìn)行的是檢索、排序、插入、刪除等。

1.算法定義2.設(shè)計(jì)算法的基本過程1)通過對問題進(jìn)行詳細(xì)地分析，抽象出相應(yīng)的數(shù)學(xué)模型；2)確定使用的數(shù)據(jù)結(jié)構(gòu)，并在此基礎(chǔ)上設(shè)計(jì)對此數(shù)據(jù)結(jié)構(gòu)實(shí)施各種操作的算法；3)選用某種語言將算法轉(zhuǎn)換成程序；4)調(diào)試并運(yùn)行這些程序。

2.設(shè)計(jì)算法的基本過程1）有窮性：對任何合法輸入值，算法總是在有窮步內(nèi)結(jié)束，且每一步都可在有窮的時(shí)間內(nèi)完成；2）確定性：每條指令有確切的含義，不會(huì)產(chǎn)生二義性；只有一條執(zhí)行路徑，即對于相同的輸入，只能得到相同的輸出；3）可行性：算法中的操作都可以通過已實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)；4）有輸入：有零個(gè)或多個(gè)輸入；5）有輸出：有一個(gè)或多個(gè)輸出。這里所說的輸出是指與輸入有某種特定關(guān)系的量。3.算法的重要特性1）有窮性：對任何合法輸入值，算法總是在有窮步內(nèi)結(jié)束，且每一1）正確性：算法應(yīng)當(dāng)滿足具體問題的需求。

“正確”一詞的含義在通常的用法中有很大差別，大體可分4層次：a.程序不含語法錯(cuò)誤；b.程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；

c.程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能得出滿足規(guī)格說明要求的結(jié)果；通常以此作為衡量一個(gè)程序是否正確的標(biāo)準(zhǔn)；d.程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。4.算法設(shè)計(jì)的要求1）正確性：算法應(yīng)當(dāng)滿足具體問題的需求。4.算法設(shè)計(jì)的要求2）可讀性：為了便于理解、測試和修改算法，算法應(yīng)該具有良好的可讀性。3）健壯性：當(dāng)輸入數(shù)據(jù)非法時(shí)，算法也能適當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫明其妙的輸出結(jié)果。4）高效率與低存儲(chǔ)量需求：

通俗地說，效率指的是算法執(zhí)行時(shí)間。對于同一個(gè)問題如果有多個(gè)算法可以解決，執(zhí)行時(shí)間短的算法效率高。存儲(chǔ)量需求指算法執(zhí)行過程中所需要的最大存儲(chǔ)空間。效率與低存儲(chǔ)量需求這兩者都與問題的規(guī)模有關(guān)。4.算法設(shè)計(jì)的要求2）可讀性：為了便于理解、測試和修改算法，算法應(yīng)該具有良好的5.一般書寫算法的4種形式：1）條列式的步驟以條列式的步驟來描述解決問題的方法2）流程圖/可讀性以圖形符號(hào)來描述解決問題的方法。3）偽碼

以夾雜程序語法和自然語言（如：中文、英文）的形式描述解決問題的方法。4）程序語句

直接以程序語法來描述解決問題的方法。5.一般書寫算法的4種形式：6.算法效率的衡量方法和準(zhǔn)則事后統(tǒng)計(jì)法計(jì)算機(jī)內(nèi)部都有計(jì)時(shí)功能，不同算法的程序可通過一組或若干組相同的統(tǒng)計(jì)數(shù)據(jù)以分辨優(yōu)劣。缺陷：一是必須先運(yùn)行依據(jù)算法編制的程序；二是所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件、軟件等環(huán)境因素，有時(shí)容易掩蓋算法本身的優(yōu)劣。因此常采用事前分析估算法。事前分析估算法6.算法效率的衡量方法和準(zhǔn)則與算法執(zhí)行時(shí)間相關(guān)的因素：

1．算法選用的策略2．問題的規(guī)模3．編寫程序的語言4．編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5．計(jì)算機(jī)執(zhí)行指令的速度顯然，同一個(gè)算法用不同的語言實(shí)現(xiàn)，或者用不同的編譯程序進(jìn)行編譯，或者在不同的計(jì)算機(jī)上運(yùn)行時(shí)，效率均不相同。這表明使用絕對的時(shí)間單位衡量算法的效率是不合適的。與算法執(zhí)行時(shí)間相關(guān)的因素：一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。假如，隨著問題規(guī)模n的增長，算法執(zhí)行時(shí)間的增長率和f（n）的增長率相同，則可記作：

T（n）=O（f（n））稱T（n）為算法的(漸近)時(shí)間復(fù)雜度一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。

一個(gè)算法的執(zhí)行時(shí)間可以看成是所有語句的執(zhí)行時(shí)間之和T=∑(語句(i)的執(zhí)行次數(shù)×語句的執(zhí)行時(shí)間)

假設(shè)每條語句執(zhí)行的時(shí)間相等

算法的語句頻度f(n):算法中基本操作重復(fù)執(zhí)行的次數(shù)之和。

算法的漸近時(shí)間復(fù)雜度T（n）=O(f(n))

這種衡量效率的辦法所得出的不是時(shí)間量，而是一種增長趨勢的量度。

漸近時(shí)間復(fù)雜度（AsymptoticTimeComplexity）一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通如何估算算法的時(shí)間復(fù)雜度？算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間=原操作(i)的執(zhí)行次數(shù)

×原操作(i)的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間與原操作執(zhí)行次數(shù)之和成正比如何估算算法的時(shí)間復(fù)雜度？所以

從算法中選取一種對于所研究的問題來說是基本操作的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。一般地，常用最深層循環(huán)內(nèi)的語句中的原操作的執(zhí)行頻度(重復(fù)執(zhí)行的次數(shù))來表示。所以例一

矩陣相乘

for(i=1；i<=n；++i)for(j=1；j<=n；++j){c[i，j]=0；

for(k=1；k<=n；++k)c[i，j]+=a[i，k]×b[k，j]；

}基本操作:乘法操作，時(shí)間復(fù)雜度:O（n3）例一

矩陣相乘

例二voidselect_sort(inta[],intn){//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列

for(i=0;i<n-1;++i){j=i;for(k=i+1;k<n;++k)if(a[k]<a[j])j=k;if(j!=i)a[j]←→a[i]}}//select_sort基本操作:比較操作；時(shí)間復(fù)雜度:O(n2)

例二例三

voidbubble_sort(inta[],intn){//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列

for(i=n-1,change=TRUE;i>1&&change;--i){change=FALSE;for(j=0;j<i;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];change=TRUE}}}//bubble_sort基本操作:賦值操作；時(shí)間復(fù)雜度:O（n2）例三

定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(nm)如果算法的執(zhí)行時(shí)間T(n)與問題規(guī)模n無關(guān)，是個(gè)常數(shù)，則記作T(n)=O(1)。 例{++x;s=0;}

將x自增看成是基本操作，則語句頻度為１，即時(shí)間復(fù)雜度為Ｏ(1)。以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的。其關(guān)系為：

O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)指數(shù)時(shí)間的關(guān)系為：

O(2n)<O(n!)<O(nn)

定理：若A(n)=amnm+am-1nm-1數(shù)據(jù)結(jié)構(gòu)培訓(xùn)資料當(dāng)n取得很大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在所需時(shí)間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時(shí)間算法中的任何一個(gè)算法化簡為多項(xiàng)式時(shí)間算法，那就取得了一個(gè)偉大的成就。有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。當(dāng)n取得很大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在所需時(shí)間上非常算法的存儲(chǔ)空間需求空間復(fù)雜度(Spacecomplexity)：是指算法編寫成程序后，在計(jì)算機(jī)中運(yùn)行時(shí)所需存儲(chǔ)空間大小的度量。記作：S(n)=O(g(n))其中：n為問題的規(guī)模(或大小)表示隨著問題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長率與g(n)的增長率相同。算法的存儲(chǔ)量包括:

1．輸入數(shù)據(jù)所占空間

2．程序本身所占空間

3．輔助變量所占空間算法的存儲(chǔ)空間需求例：1.sum=0;for(j=1;j<=n;j++)sum=sum+j;printf(“%d”,sum);T(n)=O(f(n))=O(2n+3)=O(n)1n+1n12.Sum=0;for(I=1;I<=n;I++)for(j=1;j<=n;j++)sum=sum+I*j;Printf(“%d”,sum);1n+1n(n+1)n21T(n)=O(f(n))=O(2n2+2n+3)=O(n2)3.x=n;y=0;while(x>=(y+1)*(y+1))y++;T(n)=O(n?)4.x=n;for(j=1;j<=100;j++) x=x+j;T(n)=O(1)例：1.sum=0;T(n)=O(f(n))=O(2n+3)若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的額外空間。若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。若所需存儲(chǔ)量依賴于特定的輸入，則通常按最壞情況考慮。若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，則只本章小結(jié)1.概念和術(shù)語數(shù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)對象數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)抽象數(shù)據(jù)類型算法2.數(shù)據(jù)結(jié)構(gòu)的研究目的和研究內(nèi)容

目的：尋求有效地組織和處理非數(shù)值數(shù)據(jù)的理論、技術(shù)和方法。內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及相應(yīng)的基本操作運(yùn)算的定義和實(shí)現(xiàn)。3.邏輯結(jié)構(gòu)的四種基本形態(tài)集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)本章小結(jié)1.概念和術(shù)語本章小結(jié)4.數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的基本組織方式順序、鏈?zhǔn)?.數(shù)據(jù)結(jié)構(gòu)引入ADT概念的優(yōu)點(diǎn)

運(yùn)用ADT的概念實(shí)際上是將數(shù)據(jù)結(jié)構(gòu)的討論分成兩部分：一是其概念所涵蓋的數(shù)據(jù)邏輯結(jié)構(gòu)的說明和運(yùn)算的定義，突出的是在某種關(guān)系的數(shù)據(jù)對象上可以做什么；一是在計(jì)算機(jī)中如何存儲(chǔ)這些數(shù)據(jù)并具體實(shí)現(xiàn)定義的運(yùn)算，解決怎樣做的問題。它和面向?qū)ο蠓椒ǖ乃枷胧且恢碌?。本章小結(jié)4.數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的基本組織方式本章小結(jié)6.算法的五個(gè)重要特性確定性、有窮性、可行性、輸入、輸出7.評價(jià)算法優(yōu)劣的基本標(biāo)準(zhǔn)正確性、可讀性、健壯性、效率與低存儲(chǔ)量8.算法分析的目的主要是考察算法的時(shí)間和空間效率，以求改進(jìn)算法或?qū)Σ煌乃惴ㄟM(jìn)行比較。一般情況下，鑒于運(yùn)算空間（內(nèi)存）比較充足，所以把算法的時(shí)間復(fù)雜度作為分析的重點(diǎn)。9.算法的時(shí)間復(fù)雜度、空間復(fù)雜度本章小結(jié)6.算法的五個(gè)重要特性習(xí)題一1簡要回答術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)類型。2數(shù)據(jù)的邏輯結(jié)構(gòu)？數(shù)據(jù)的物理結(jié)構(gòu)？邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的區(qū)別和聯(lián)系是什么？3數(shù)據(jù)結(jié)構(gòu)的主要運(yùn)算包括哪些？4算法分析的目的是什么？算法分析的主要方面是什么？5分析以下程序段的時(shí)間復(fù)雜度，請說明分析的理由或原因。

習(xí)題一1簡要回答術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)作業(yè)6.設(shè)數(shù)據(jù)邏輯結(jié)構(gòu)的二元組表示為s=(D,R),其中

D＝{a,b,c,d,e,f}R={<b,a>,<d,c>,<b,d>,<a,e>,<d,f>}

試畫出這個(gè)邏輯結(jié)構(gòu)的示意圖及類別。7.求下列算法的時(shí)間復(fù)雜度及注釋語句的頻度⑴k=0;for(i=1;i<=n;i++)for(j=i;j<=n;j++)k++;//（2）

for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]+=a[i][k]*b[k][j];//}作業(yè)6.設(shè)數(shù)據(jù)邏輯結(jié)構(gòu)的二元組表示為s=(D,R),其中⑴（(3)Sum1(intn){intp=1,sum=0,m;for(m=1;m<=n;m++){p*=m;sum+=p;}return(sum);}(4)Sum2(intn){intsum=0,m,t;for(m=1;m<=n;m++){p=1;for(t=1;t<=m;t++)p*=t;sum+=p;}return(sum);}(3)(4)i=1;k=0;while(i<=n-1){k=k+10*i;//i++;}i=1;j=0;while(i+j<=n)if(i>j)j++;//elsei++;3.設(shè)一維數(shù)組V中存有n個(gè)整數(shù)，（1）寫一個(gè)算法，將數(shù)組中的非零元素移到前面來，零元素移到后面去，各非零元素間的相對位置不變；（2）分析所寫算法的時(shí)間復(fù)雜度。i=1;演講完畢，謝謝觀看！演講完畢，謝謝觀看！第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法和算法分析第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)電子計(jì)算機(jī)的主要用途：早期：主要用于數(shù)值計(jì)算。解決問題的步驟：數(shù)學(xué)模型→解題算法→選擇計(jì)算機(jī)語言編程→測試→最終解答關(guān)鍵：如何得出數(shù)學(xué)模型當(dāng)今：擴(kuò)大到非數(shù)值計(jì)算領(lǐng)域。計(jì)算機(jī)的操作對象的關(guān)系更加復(fù)雜，數(shù)據(jù)元素間的相互關(guān)系有時(shí)無法用數(shù)學(xué)方程來描述。所處理的數(shù)據(jù)量大且具有一定的關(guān)系；而對其的操作也不再是單純的數(shù)值計(jì)算，更多地是對其進(jìn)行組織、管理和檢索等。電子計(jì)算機(jī)的主要用途：例1：學(xué)籍檔案管理假設(shè)一個(gè)學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表所示的學(xué)生信息：例1：學(xué)籍檔案管理假設(shè)一個(gè)學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下特點(diǎn)：每個(gè)學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號(hào)順序依次排列構(gòu)成一張表格；每列的數(shù)據(jù)類型一樣；表中每個(gè)學(xué)生的信息依據(jù)學(xué)號(hào)的大小存在著一種前后關(guān)系，這就是我們所說的線性結(jié)構(gòu)；對它的操作通常是插入、刪除、更新、按條件檢索某個(gè)學(xué)生的信息等等。特點(diǎn)：每個(gè)學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號(hào)順序依次排例2：輸出n個(gè)對象的全排列輸出3個(gè)對象的全排列可以使用下圖所示的形式描述：例2：輸出n個(gè)對象的全排列輸出3個(gè)對象的全排列可以使特點(diǎn)：在求解過程中，所處理的數(shù)據(jù)之間具有層次關(guān)系，這是我們所說的樹形結(jié)構(gòu)；對它的操作有：建立樹形結(jié)構(gòu)，輸出最低層結(jié)點(diǎn)內(nèi)容等等。特點(diǎn)：在求解過程中，所處理的數(shù)據(jù)之間具有層次關(guān)系，這是我們所例3：制定教學(xué)計(jì)劃制定教學(xué)計(jì)劃時(shí)，需考慮各門課程的開設(shè)順序。有些課程需要先導(dǎo)課程，有些課程則不需要，而有些課程又是其他課程的先導(dǎo)課程。比如，計(jì)算機(jī)專業(yè)課程的開設(shè)情況如下表所示：

例3：制定教學(xué)計(jì)劃制定教學(xué)計(jì)劃時(shí)，需考慮各門課程的開課程先后關(guān)系如圖：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6c7c8c11課程先后關(guān)系如圖：c1c9c4c2c12c10c11c5c3特點(diǎn)：課程之間的先后關(guān)系用圖結(jié)構(gòu)描述；通過實(shí)施創(chuàng)建圖結(jié)構(gòu)，按要求將圖結(jié)構(gòu)中的頂點(diǎn)進(jìn)行線性排序。特點(diǎn)：課程之間的先后關(guān)系用圖結(jié)構(gòu)描述；結(jié)論要使計(jì)算機(jī)能夠更有效地進(jìn)行這些非數(shù)值性處理，就必須弄清楚這些操作對象的特點(diǎn)、之間的關(guān)系，在計(jì)算機(jī)中的表示方式及各種操作的具體實(shí)現(xiàn)手段。因此，《數(shù)據(jù)結(jié)構(gòu)》研究的主要內(nèi)容是：數(shù)據(jù)元素之間的邏輯關(guān)系數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)采用何種操作實(shí)現(xiàn)算法的效率更高結(jié)論要使計(jì)算機(jī)能夠更有效地進(jìn)行這些非數(shù)值性處理，就必程序設(shè)計(jì)：為計(jì)算機(jī)處理問題編制一組指令集。算法：處理問題的策略。數(shù)據(jù)結(jié)構(gòu)：問題的數(shù)學(xué)模型。程序設(shè)計(jì)的實(shí)質(zhì)是對確定的問題選擇一種好的結(jié)構(gòu)，加上設(shè)計(jì)一種好的算法。程序=算法+數(shù)據(jù)結(jié)構(gòu)“Programs=Algorithm+DataStructures”瑞士學(xué)者NiklausWirth于1976年出版的書名。程序設(shè)計(jì)：為計(jì)算機(jī)處理問題編制一組指令集。程序=算課程任務(wù)：1.討論現(xiàn)實(shí)世界中數(shù)據(jù)的各種邏輯結(jié)構(gòu)及在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)；

2.進(jìn)行各種非數(shù)值運(yùn)算的算法。課程目的：掌握數(shù)據(jù)組織、存儲(chǔ)和處理的常用法，為進(jìn)行軟件開發(fā)或后續(xù)專業(yè)課程學(xué)習(xí)打下良好的基礎(chǔ)。課程內(nèi)容：數(shù)據(jù)結(jié)構(gòu)的基本概念、線性表、棧和隊(duì)列、串和數(shù)組、樹形結(jié)構(gòu)、圖結(jié)構(gòu)、查找、排序和文件等內(nèi)容。課程任務(wù)：1.討論現(xiàn)實(shí)世界中數(shù)據(jù)的各種邏輯結(jié)構(gòu)及在計(jì)算機(jī)中的第1章緒論

1.1什么是數(shù)據(jù)結(jié)構(gòu)

1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法和算法分析第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.數(shù)據(jù)是對客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)處理的符號(hào)的總稱。計(jì)算機(jī)程序加工的“原料”。1.數(shù)據(jù)例：一個(gè)利用數(shù)值分析方法解代數(shù)方程的程序，其處理對象是整數(shù)和實(shí)數(shù)；一個(gè)編譯程序或文字處理程序的處理對象是字符串。還有聲音、圖象、視頻等等通過編碼都屬于數(shù)據(jù)的范疇。例：一個(gè)利用數(shù)值分析方法解代數(shù)方程的程序，其處理對象2.數(shù)據(jù)元素

是數(shù)據(jù)的基本單位。數(shù)據(jù)中的一個(gè)“個(gè)體”，數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。2.數(shù)據(jù)元素例：一個(gè)整數(shù)“5”；一個(gè)字符“N”；圖中的一個(gè)頂點(diǎn)等。

復(fù)雜型數(shù)據(jù)元素由多個(gè)數(shù)據(jù)項(xiàng)組成，它通常攜帶著一個(gè)概念的多方面信息。例：一個(gè)學(xué)生的基本信息就是一個(gè)數(shù)據(jù)元素，其中的學(xué)號(hào)、姓名等被稱為“數(shù)據(jù)項(xiàng)”。

因此數(shù)據(jù)項(xiàng)是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。例：一個(gè)整數(shù)“5”；一個(gè)字符“N”；圖中的一個(gè)頂點(diǎn)等3.數(shù)據(jù)對象

性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的子集。例：整數(shù)數(shù)據(jù)對象是集合N={0，±1，±2，…}。英文字母數(shù)據(jù)對象是集合

C={‘A’，……，‘Z’}。如何選定數(shù)據(jù)對象將依問題而定！譬如，在學(xué)生管理系統(tǒng)中，可能以一個(gè)班級(jí)的學(xué)生記錄作為數(shù)據(jù)對象，也可能以一個(gè)年級(jí)的學(xué)生記錄作為數(shù)據(jù)對象。3.數(shù)據(jù)對象例：4.數(shù)據(jù)的邏輯結(jié)構(gòu)討論計(jì)算機(jī)系統(tǒng)中數(shù)據(jù)的組織形式及其相互關(guān)系。即相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)邏輯結(jié)構(gòu)的形式定義：數(shù)據(jù)邏輯結(jié)構(gòu)是一個(gè)二元組：

Data_structure={D,R}

其中，D是數(shù)據(jù)元素的有限集，R是D上的關(guān)系的集合。4.數(shù)據(jù)的邏輯結(jié)構(gòu)例：在計(jì)算機(jī)科學(xué)中，復(fù)數(shù)可取如下定義：復(fù)數(shù)數(shù)據(jù)的邏輯結(jié)構(gòu)

Complex=(C,R)

其中：C是含兩個(gè)實(shí)數(shù)的集合{c1,c2};R={P}，而P是定義在集合C上的一種關(guān)系{<c1,c2>}，其中有序偶<c1,c2>表示c1是復(fù)數(shù)的實(shí)部，c2是復(fù)數(shù)的虛部。

例：在計(jì)算機(jī)科學(xué)中，復(fù)數(shù)可取如下定義：復(fù)數(shù)數(shù)據(jù)的邏輯結(jié)構(gòu)4數(shù)據(jù)的邏輯結(jié)構(gòu)例：list=(D,S1),tree=(D,S2),graph=(D,S3)D={a,b,c,d,e}S1={<a,b>,<b,c>,<c,d>,<d,e>}S2={<a,b>,<a,c>,<b,d>,<b,e>}S3={<a,b>,<a,c>,<d,a>,<e,c>}4數(shù)據(jù)的邏輯結(jié)構(gòu)例：list=(D,S1),tree=(D邏輯結(jié)構(gòu)示意圖<a,b>,稱a是b的前驅(qū)，b是a的后繼。若某結(jié)點(diǎn)沒有前驅(qū)，則稱該結(jié)點(diǎn)為開始結(jié)點(diǎn)；若某結(jié)點(diǎn)沒有后繼，則稱該結(jié)點(diǎn)為終端結(jié)點(diǎn)；bacdelistaedbcgraphedbcatree（a,b,c,d,e）邏輯結(jié)構(gòu)示4.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)中所說的“關(guān)系”實(shí)際上是指數(shù)據(jù)元素之間的邏輯關(guān)系，又稱此為邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類:

1）集合：數(shù)據(jù)元素之間除“同屬于一個(gè)集合”的關(guān)系外無其它關(guān)系。2）線性結(jié)構(gòu)：數(shù)據(jù)元素間存在一對一的關(guān)系。3）樹形結(jié)構(gòu)：數(shù)據(jù)元素間存在一對多的關(guān)系。4）圖（網(wǎng)）狀結(jié)構(gòu)：數(shù)據(jù)元素間存在多對多的關(guān)系。4.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)：一對一非線性結(jié)構(gòu)樹形結(jié)構(gòu)：一對多圖狀結(jié)構(gòu)：多對多邏輯結(jié)構(gòu)集合線性結(jié)構(gòu)：一對一非線性結(jié)構(gòu)樹形結(jié)構(gòu)：一對多圖狀結(jié)構(gòu)：多對多邏5.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）存儲(chǔ)結(jié)構(gòu)：邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示(又稱映象)稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱存儲(chǔ)結(jié)構(gòu)。包括數(shù)據(jù)元素的表示和關(guān)系的表示。計(jì)算機(jī)中表示信息的最小單位是二進(jìn)制數(shù)的一位(bit)?？捎靡粋€(gè)由若干位組合起來形成的一個(gè)位串表示一個(gè)數(shù)據(jù)元素，通常稱這個(gè)位串為元素(Element)或結(jié)點(diǎn)(Node)。當(dāng)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成時(shí)，位串中對應(yīng)于各個(gè)數(shù)據(jù)項(xiàng)的子位串稱為數(shù)據(jù)域(DataField)。5.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）5.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）存儲(chǔ)的要求：既存儲(chǔ)各結(jié)點(diǎn)的數(shù)值又要存儲(chǔ)結(jié)點(diǎn)與結(jié)點(diǎn)之間的邏輯關(guān)系。四種基本的存儲(chǔ)結(jié)構(gòu)：順序、鏈接、索引、散列存儲(chǔ)。內(nèi)存空間、內(nèi)存地址程序在運(yùn)行期間所需存儲(chǔ)空間都在內(nèi)存中分配.……5.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）存儲(chǔ)的要求：既存儲(chǔ)各結(jié)點(diǎn)的數(shù)值1.順序存儲(chǔ)（用數(shù)組實(shí)現(xiàn)）存儲(chǔ)方法:把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在一組連續(xù)的存儲(chǔ)單元中,其結(jié)點(diǎn)之間的邏輯關(guān)系由存儲(chǔ)單元地址間的關(guān)系隱含表示。例：list的順序存儲(chǔ)結(jié)構(gòu)如下abcde200201202203204優(yōu)點(diǎn)：節(jié)省存儲(chǔ)空間，可實(shí)現(xiàn)對各結(jié)點(diǎn)的隨機(jī)訪問。

loc（i）＝q＋（i－1）×pq是第一個(gè)結(jié)點(diǎn)所占存儲(chǔ)單元的首地址；

p是每個(gè)結(jié)點(diǎn)所占單元數(shù)。1.順序存儲(chǔ)（用數(shù)組實(shí)現(xiàn)）存儲(chǔ)方法:把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在缺點(diǎn)：不便于修改。進(jìn)行插入、刪除運(yùn)算時(shí)可能要移動(dòng)一系列的數(shù)據(jù)元素。例：若刪除list結(jié)構(gòu)中的第三個(gè)結(jié)點(diǎn)c，則list的邏輯結(jié)構(gòu)變成(a,b,d,e)。

若在結(jié)點(diǎn)c前插入一個(gè)新的結(jié)點(diǎn)x，則list的邏輯結(jié)構(gòu)變成(a,b,x,c,d,e)。

邏輯結(jié)構(gòu)發(fā)生變化后，相應(yīng)的存儲(chǔ)結(jié)構(gòu)同樣發(fā)生變化baxdeab缺點(diǎn)：不便于修改。進(jìn)行插入、刪除運(yùn)算時(shí)可能要移動(dòng)一系列的數(shù)據(jù)2.鏈接存儲(chǔ)(用指針實(shí)現(xiàn))存儲(chǔ)方法：給每個(gè)機(jī)結(jié)點(diǎn)附加指針字段，用于存放相鄰結(jié)點(diǎn)的存儲(chǔ)地址。優(yōu)點(diǎn)：便于修改缺點(diǎn)：浪費(fèi)存儲(chǔ)空間例：list（a,b,c,d,e）的存儲(chǔ)結(jié)構(gòu)示意圖如下c208b200a202ed206200202206208204200202206208204b208a202ed206刪除結(jié)點(diǎn)c后(a,b,d,e)x200…c208b100a202ed206200202206208204100插入結(jié)點(diǎn)x后（a,b,x,c,d,e）2.鏈接存儲(chǔ)(用指針實(shí)現(xiàn))存儲(chǔ)方法：給每個(gè)機(jī)結(jié)點(diǎn)附加指針字段3.索引存儲(chǔ)（用數(shù)組實(shí)現(xiàn)）存儲(chǔ)方法：根據(jù)結(jié)點(diǎn)的序號(hào)確定結(jié)點(diǎn)的存儲(chǔ)地址。具體做法：建立索引表和結(jié)點(diǎn)表；將各結(jié)點(diǎn)的數(shù)值按任意順序存放在結(jié)點(diǎn)表中，而將每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址用順序存儲(chǔ)方法存入索引表中。例：list（a,b,c,d,e)的索引存儲(chǔ)結(jié)構(gòu)如下200204202201203200204201203a甲85d丁90c丙67e戊55b乙78100101102103104200201202203204索引表結(jié)點(diǎn)表索引表100101102103104刪除結(jié)點(diǎn)c后刪除結(jié)點(diǎn)c前后無變化3.索引存儲(chǔ)（用數(shù)組實(shí)現(xiàn)）存儲(chǔ)方法：根據(jù)結(jié)點(diǎn)的序號(hào)確定結(jié)點(diǎn)的4.散列存儲(chǔ)(用數(shù)組實(shí)現(xiàn))存儲(chǔ)方法：根據(jù)結(jié)點(diǎn)的值確定結(jié)點(diǎn)的存儲(chǔ)地址。具體做法：以結(jié)點(diǎn)中某個(gè)字段的值為自變量，通過某個(gè)函數(shù)（稱為散列函數(shù)）計(jì)算出對應(yīng)的函數(shù)值i，再把i當(dāng)作結(jié)點(diǎn)的存儲(chǔ)地址。例：假定list結(jié)構(gòu)中的5個(gè)結(jié)點(diǎn)數(shù)值是下列5個(gè)字符‘Wuhan’‘Nanjing’‘Shanghai’‘Xian’‘Beijing’

散列函數(shù)：Loc(key)=asc(left(key,1))mod8KeyWuhanNanjingShanghaiXianBeijingasc(key)8778838866Loc(key)76302XianBeijingShanghaiNanjingWuhan012345674.散列存儲(chǔ)(用數(shù)組實(shí)現(xiàn))存儲(chǔ)方法：根據(jù)結(jié)點(diǎn)的值確定結(jié)點(diǎn)

數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的兩個(gè)方面，在后面的課程中我們會(huì)看到，任何一個(gè)算法的設(shè)計(jì)取決于選定的數(shù)據(jù)（邏輯）結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于所采用的存儲(chǔ)結(jié)構(gòu)。

完整的數(shù)據(jù)結(jié)構(gòu)概念可認(rèn)為是由數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操作集三個(gè)部分組成：

Data_Structure＝（D，R，P）其中D是數(shù)據(jù)元素的有限集合；R是D集上關(guān)系的有限集合，P是對D的基本操作集。數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容完整的數(shù)據(jù)結(jié)構(gòu)概念可認(rèn)為是由數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操數(shù)據(jù)的邏輯結(jié)構(gòu)非線性結(jié)構(gòu)集合圖狀結(jié)構(gòu)有向圖無向圖樹形結(jié)構(gòu)一般樹二叉樹線性結(jié)構(gòu)一般線性表線性表推廣廣義表數(shù)組串受限線性表?xiàng)：完?duì)列

數(shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)系圖

邏輯結(jié)構(gòu)與所采用的存儲(chǔ)結(jié)構(gòu)線性表樹圖順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)復(fù)合存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)非線性結(jié)構(gòu)集合圖狀結(jié)構(gòu)有向圖無向圖樹形結(jié)構(gòu)一般6.數(shù)據(jù)類型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個(gè)概念，它最早出現(xiàn)在高級(jí)程序語言中，用以刻畫（程序）

操作對象的特性。

數(shù)據(jù)類型：是一組性質(zhì)相同的值的集合及定義于這個(gè)值集合上的一組操作的總稱。6.數(shù)據(jù)類型通用的計(jì)算機(jī)高級(jí)語言常見的有整數(shù)、實(shí)數(shù)（浮點(diǎn)數(shù)）、枚舉、字符、字符串、指針、數(shù)組、記錄文件等數(shù)據(jù)類型。譬如：整數(shù)類型通常用兩個(gè)字節(jié)或四個(gè)字節(jié)表示，分別表示范圍：-215～215-1、-231～231-1。對其允許施加的操作通常有：單目和雙目，分別是取正或取負(fù)運(yùn)算；加、減、乘、除、取模、等于、不等于、大于等關(guān)系（比較）運(yùn)算。通用的計(jì)算機(jī)高級(jí)語言常見的有整數(shù)、實(shí)數(shù)（浮點(diǎn)數(shù)）、枚依據(jù)“值”的不同特性，高級(jí)語言中數(shù)據(jù)類型可分為兩類：1）原子類型

原子類型的值是不可分解。如：C語言中的基本類型（整型、實(shí)型、字符型和枚舉型），指針型。2）結(jié)構(gòu)類型結(jié)構(gòu)類型的值是由若干成分按某種結(jié)構(gòu)組成，因此可以分解，且它的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。如：數(shù)組類型。依據(jù)“值”的不同特性，高級(jí)語言中數(shù)據(jù)類型可分為兩類：7.抽象數(shù)據(jù)類型（簡稱ADT）指一個(gè)數(shù)學(xué)模型及定義在此數(shù)學(xué)模型上的一組操作?！俺橄蟆钡囊饬x在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。

為提高軟件復(fù)用率，近代程序設(shè)計(jì)方法學(xué)指出，一個(gè)軟件系統(tǒng)的框架應(yīng)建立在數(shù)據(jù)之上，而不是操作之上（后者是傳統(tǒng)的軟件設(shè)計(jì)方法所為）。即在構(gòu)成軟件系統(tǒng)的每個(gè)相對獨(dú)立的模塊上，定義一組數(shù)據(jù)和施于這些數(shù)據(jù)上的一組操作，并在模塊內(nèi)部給出這些數(shù)據(jù)的表示及其操作細(xì)節(jié)，而在模塊外部使用的只是抽象的數(shù)據(jù)和操作。7.抽象數(shù)據(jù)類型（簡稱ADT）ADT有兩個(gè)重要特征:1）數(shù)據(jù)抽象

用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。2）數(shù)據(jù)封裝

將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。ADT有兩個(gè)重要特征:抽象數(shù)據(jù)類型的描述方法：三元組表示（D，S，P）其中，D是數(shù)據(jù)對象，

S是D上的關(guān)系集，

P是對D的基本操作集。抽象數(shù)據(jù)類型的描述方法：ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉

數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉

基本操作：〈基本操作的定義〉

}ADT抽象數(shù)據(jù)類型名其中，數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼描述，

基本操作的定義格式為：基本操作名（參數(shù)表）初始條件：〈初始條件描述〉操作結(jié)果：〈操作結(jié)果描述〉A(chǔ)DT抽象數(shù)據(jù)類型名{基本操作有兩種參數(shù)：1）賦值參數(shù)：只為操作提供輸入值2）引用參數(shù)：以&打頭，除可提供輸入值外，還將返回操作結(jié)果?！俺跏紬l件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息?！安僮鹘Y(jié)果”說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則將其省略?；静僮饔袃煞N參數(shù)：例：抽象數(shù)據(jù)類型——

復(fù)數(shù)的定義

ADTComplex{

數(shù)據(jù)對象：D＝{e1,e2｜e1,e2∈RealSet}

數(shù)據(jù)關(guān)系：R＝{<e1,e2>|e1是復(fù)數(shù)的實(shí)數(shù)部分,

e2是復(fù)數(shù)的虛數(shù)部分}

基本操作：

InitComplex(&Z,v1,v2)

操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。

DestroyComplex(&Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。例：抽象數(shù)據(jù)類型——復(fù)數(shù)的定義

GetReal(Z,&realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。

GetImag(Z,&ImaPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImgPart返回復(fù)數(shù)Z的虛部值。

Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。}ADTComplexGetReal(Z,&realPart)第1章緒論

1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語

1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法和算法分析第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型可通過固有數(shù)據(jù)類型來表示和實(shí)現(xiàn)，即利用處理器中已存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實(shí)現(xiàn)的操作來組合新的操作。本課程在高級(jí)程序設(shè)計(jì)語言的虛擬層次上討論抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)，采用介于偽碼和Ｃ語言之間的類Ｃ語言作為描述工具，下面我們對其作一下簡要說明。抽象數(shù)據(jù)類型可通過固有數(shù)據(jù)類型來表示和實(shí)現(xiàn)，即利用處（1）預(yù)定義常量和類型：

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2Typedefintstatus

//status是函數(shù)的類型，

//其值是函數(shù)結(jié)果狀態(tài)代碼（1）預(yù)定義常量和類型：（2）數(shù)據(jù)結(jié)構(gòu)的表示（存儲(chǔ)結(jié)構(gòu)）

用類型定義（typedef）描述。數(shù)據(jù)元素類型約定為ElemType，由用戶在使用該數(shù)據(jù)類型時(shí)自行定義。（3）基本操作的算法

用以下形式的函數(shù)描述：函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）

{//算法說明語句序列

}//函數(shù)名（2）數(shù)據(jù)結(jié)構(gòu)的表示（存儲(chǔ)結(jié)構(gòu)）說明：除了函數(shù)的參數(shù)需要說明類型外，算法中使用的輔助變量可以不作變量說明，必要時(shí)對其作用給予注釋。當(dāng)函數(shù)返回值為函數(shù)結(jié)果狀態(tài)碼時(shí)，函數(shù)定義為status類型。為了便于算法描述，除了值調(diào)用方式之外，增添了C++語言的引用調(diào)用的參數(shù)傳遞方式。在形參表中，以&打頭的參數(shù)即為引用參數(shù)。說明：（4）賦值語句

簡單賦值變量名=表達(dá)式；

串聯(lián)賦值變量名1=變量名2=…變量名K=表達(dá)式；

成組賦值（變量名1，變量名2，…變量名K）=

（表達(dá)式1，表達(dá)式2，…表達(dá)式K）；（4）賦值語句

結(jié)構(gòu)名=結(jié)構(gòu)名；結(jié)構(gòu)名=（值1，值2，…，值K）；變量名[]=表達(dá)式；變量名[起始下標(biāo)..終止下標(biāo)]=

變量名[起始下標(biāo)..終止下標(biāo)]；

交換賦值變量名←→變量名；

條件賦值

變量名=條件表達(dá)式？表達(dá)式T：表達(dá)式F；結(jié)構(gòu)名=結(jié)構(gòu)名；（5）選擇語句

條件語句1if（表達(dá)式）語句；

條件語句2if（表達(dá)式）語句;else語句；（5）選擇語句

開關(guān)語句1

switch（表達(dá)式）{case值1:語句序列1；break；

…case值n:語句序列n；break；

default:語句序列n+1