數(shù)據(jù)結(jié)構(gòu)講義

數(shù)據(jù)結(jié)構(gòu)講義第一章緒論本章主要內(nèi)容學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》的意義基本概念和術(shù)語算法的描述和分析1.1什么是數(shù)據(jù)結(jié)構(gòu)圖書的基本信息登記號，書名，作者，分類編號，出版單位，出版時(shí)間作者簡介，內(nèi)容簡介，等等。操作檢索，排序，等等數(shù)據(jù)之間的關(guān)系線性關(guān)系數(shù)據(jù)表示和算法操作的設(shè)計(jì)與需求有關(guān)數(shù)據(jù)的邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)，算法操作邏輯結(jié)構(gòu)是客觀事物特性的一種抽象存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)的計(jì)算機(jī)實(shí)現(xiàn)算法操作是基于存儲結(jié)構(gòu)的操作，反映客觀事物的變化問題1：圖書檢索自動(dòng)化問題2：井子棋問題2：井子棋（續(xù)）如何表示一個(gè)棋局?jǐn)?shù)據(jù)之間的邏輯結(jié)構(gòu)表示棋局之間的演化關(guān)系樹型結(jié)構(gòu)算法如何設(shè)計(jì)基于數(shù)據(jù)表示的基礎(chǔ)上算法設(shè)計(jì)拼盤游戲：空盤拼盤游戲：拼件拼盤游戲：拼出的一種方案拼盤游戲：指定動(dòng)作的習(xí)題問題3：鋪設(shè)通信管線，投資最少邏輯結(jié)構(gòu)：圖狀結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)課程的主要任務(wù)研究和解決非數(shù)值數(shù)據(jù)的組織和處理描述非數(shù)值計(jì)算問題的數(shù)學(xué)模型，不再是數(shù)學(xué)方程例如：前述的三個(gè)例子：數(shù)據(jù)的線性結(jié)構(gòu)，樹型結(jié)構(gòu)，圖算法+數(shù)據(jù)結(jié)構(gòu)=程序算法和數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系軟件系統(tǒng)的框架應(yīng)當(dāng)建立在數(shù)據(jù)之上，而不是建立在操作之上數(shù)據(jù)結(jié)構(gòu)的作用范疇抽象數(shù)據(jù)對象的數(shù)學(xué)模型（邏輯結(jié)構(gòu)）例：圖狀結(jié)構(gòu)明確操作（運(yùn)算的定義）例：查找、插入、……在存儲結(jié)構(gòu)上映射數(shù)據(jù)（存儲結(jié)構(gòu)）例：順序存儲實(shí)現(xiàn)操作數(shù)據(jù)結(jié)構(gòu)課程的發(fā)展1968年斯坦福的Knuth教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，在他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》中第一次較系統(tǒng)地闡述了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作。

DonaldErvinKnuth《TheArtofComputerProgramming》

ArtEvans數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課，也是計(jì)算機(jī)專業(yè)的必修課，是其它許多課程的先修課程，是設(shè)計(jì)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)等系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。1.2基本概念和術(shù)語基本術(shù)語數(shù)據(jù)被計(jì)算機(jī)加工處理的對象。數(shù)據(jù)元素（記錄、表目）數(shù)據(jù)的基本單位，是數(shù)據(jù)集合中的一個(gè)有意義的個(gè)體。數(shù)據(jù)項(xiàng)一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。

組合項(xiàng)年月日學(xué)號姓名班號性別出生日期入學(xué)成績原子項(xiàng)基本術(shù)語2數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。

學(xué)號姓名班號性別出生日期入學(xué)成績

001劉影01女19840417623002李恒01男19831211679003陳誠02男19840910638………………數(shù)據(jù)結(jié)構(gòu)具有結(jié)構(gòu)的數(shù)據(jù)元素的集合。它包括數(shù)據(jù)元素的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和相適應(yīng)的運(yùn)算。數(shù)據(jù)元素?cái)?shù)據(jù)元素之間的邏輯關(guān)系，與計(jì)算機(jī)無關(guān)?？捎靡粋€(gè)二元組表示：Data_Structure=(D,R)D：數(shù)據(jù)元素的有窮集合，R：集合D上關(guān)系的有窮集合。

[例]設(shè)有數(shù)據(jù)結(jié)構(gòu)B=(D,R)，其中D={d1,d2,d3,d4,d5,d6}，

R={r}，

r={<d1,d2>,<d1,d3>,<d1,d4>,<d3,d5>,<d3,d6>}，試畫出其邏輯結(jié)構(gòu)圖。d1d2d3d4d5d6邏輯結(jié)構(gòu)（以班級學(xué)生關(guān)系為例）(1)集合結(jié)構(gòu)數(shù)據(jù)元素除了“屬于同一集合”的聯(lián)系之外，沒有其它的關(guān)系。(2)線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對一的關(guān)系。(3)樹型結(jié)構(gòu)數(shù)據(jù)元素之間存在一對多的關(guān)系。(4)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)元素之間存在多對多的關(guān)系。成員關(guān)系長幼關(guān)系管理關(guān)系朋友關(guān)系四種基本的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)存儲結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中如何表示。數(shù)據(jù)元素的映象用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素。每個(gè)數(shù)據(jù)元素的映象稱為結(jié)點(diǎn)每個(gè)數(shù)據(jù)項(xiàng)的映象稱為數(shù)據(jù)域關(guān)系的映象兩種基本方法及其組合使用。順序映象：以相對的存儲位置表示關(guān)系鏈?zhǔn)接诚螅阂愿郊有畔?指針)表示關(guān)系在不同的編程環(huán)境下，存儲結(jié)構(gòu)有不同的描述方式。用高級程序語言編程時(shí)，直接用其提供的數(shù)據(jù)類型描述。存儲結(jié)構(gòu)(1)順序存儲：數(shù)據(jù)元素依次放在連續(xù)的存儲單元中。

a1a2...ai...an

(2)鏈?zhǔn)酱鎯Γ涸诖鎯Y(jié)點(diǎn)中增加若干指針域，記錄后繼或者相關(guān)結(jié)點(diǎn)的地址（指針）。

a11220...a3

1342...a21072...10001004

100010041072107612201224指針結(jié)點(diǎn)結(jié)點(diǎn)順序存儲和鏈?zhǔn)酱鎯\(yùn)算（操作）：在數(shù)據(jù)邏輯結(jié)構(gòu)上定義的一組數(shù)據(jù)被使用的方式，其具體實(shí)現(xiàn)要在存儲結(jié)構(gòu)上進(jìn)行。幾種常用的運(yùn)算有：

(1)建立數(shù)據(jù)結(jié)構(gòu)(6)檢索*

(2)清除數(shù)據(jù)結(jié)構(gòu)(7)更新

(3)插入數(shù)據(jù)元素(8)判空和判滿*

(4)刪除數(shù)據(jù)元素(9)求長*

(5)排序

*操作為引用型操作，即數(shù)據(jù)值不發(fā)生變化；其它為加工型操作。數(shù)據(jù)運(yùn)算抽象數(shù)據(jù)類型ADT（AbstractDataType）：

數(shù)據(jù)類型概念的引伸。指一個(gè)數(shù)學(xué)模型以及在其上定義的操作集合，與計(jì)算機(jī)無關(guān)。數(shù)據(jù)類型：一組值的集合和定義在其上的一組操作的總稱。ADT的特點(diǎn)：將它的使用和實(shí)現(xiàn)分離，提高軟件復(fù)用程度。原子類型固定聚合類型：值由確定數(shù)目的成分構(gòu)成結(jié)構(gòu)類型可變聚合類型：值的成分?jǐn)?shù)目不確定抽象數(shù)據(jù)類型數(shù)據(jù)的邏輯結(jié)構(gòu)+運(yùn)算的定義-------面向用戶，需求分析（抽象數(shù)據(jù)類型）概念層數(shù)據(jù)的存儲結(jié)構(gòu)+運(yùn)算的實(shí)現(xiàn)-------面向計(jì)算機(jī)實(shí)現(xiàn)層數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)其中基本操作的定義格式為:ADT

抽象數(shù)據(jù)類型名{

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

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

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

抽象數(shù)據(jù)類型名基本操作名（參數(shù)表）

初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉抽象數(shù)據(jù)類型的描述方法參數(shù)賦值參數(shù)只為操作提供輸入值。引用參數(shù)除可提供輸入值外，還將返回該參數(shù)值在操作后的變化結(jié)果初始條件描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。操作結(jié)果說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。抽象數(shù)據(jù)類型的描述方法（續(xù)）1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法和算法分析算法的概念建立在數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上的、求解問題的一系列確切的步驟。一個(gè)算法必須滿足以下五個(gè)重要特性有窮性：對任何合法輸入執(zhí)行有窮步后能結(jié)束。確定性：每條指令必須有確切的含義?？尚行裕核惴ǖ拿恳粭l指令均能執(zhí)行。輸入：有零個(gè)或多個(gè)輸入。輸出：有一個(gè)或多個(gè)輸出。算法的概念和特性正確性(Correctness)算法應(yīng)滿足具體問題的需求對于典型的、苛刻而帶有刁難性的一組有效輸入得到正確的結(jié)果可讀性(Readability)算法應(yīng)該好讀。以有利于閱讀者對程序的理解。健壯性(Robustness)算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)生莫名其妙或隨機(jī)的輸出結(jié)果。高效性(Efficiency)算法效率的度量時(shí)間復(fù)雜度空間復(fù)雜度評價(jià)算法優(yōu)劣的基本標(biāo)準(zhǔn)算法效率的度量時(shí)間復(fù)雜度空間復(fù)雜度算法執(zhí)行的時(shí)間事后統(tǒng)計(jì)的方法先運(yùn)行依據(jù)算法的程序所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件、軟件等環(huán)境因素收集此算法的執(zhí)行時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料事前分析估算的方法求出該算法的一個(gè)時(shí)間界限函數(shù)；時(shí)間復(fù)雜度n問題規(guī)模，一般為數(shù)據(jù)的輸入量f(n)算法中基本操作重復(fù)執(zhí)行的次數(shù)—頻度是問題規(guī)模n的某個(gè)函數(shù)算法的時(shí)間量度、時(shí)間復(fù)雜度算法中各語句的頻度之和T(n)T(n)=O(f(n))隨問題規(guī)模的增大，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同O的含義

存在正的常數(shù)c和n0，使得當(dāng)nn0時(shí)，

0T(n)

c*f(n)時(shí)間復(fù)雜度計(jì)算例1：x++;s=0;

將x++看成是基本操作，語句頻度為１

T(n)=2

算法的時(shí)間復(fù)雜度：O(1)---常量階例2:for(i=0;i<n;i++){ //執(zhí)行n+1次x++;//語句頻度為：n

s+=x;//語句頻度為：n

}

T(n)=2n+n+1=3n+1

算法的時(shí)間復(fù)雜度為：O(n)---線性階時(shí)間復(fù)雜度計(jì)算2例3:矩陣相乘C=AxB

for(i=0;i<n;i++) //n+1for(j=0;j<n;j++){//n*(n+1)c[i][j]=0; // n2for(k=0;k<n;k++)//n2*(n+1)c[i][j]+=a[i][k]*b[k][j];//n3}T(n)=2n3+3n2+2n+1算法的時(shí)間復(fù)雜度：O(n3)時(shí)間復(fù)雜度計(jì)算3在難以精確計(jì)算基本操作執(zhí)行次數(shù)的情況下，只求出關(guān)于n的增長率即可。例4:for(i=2;i<=n;++i) for(j=2;j<=i-1;++j) { ++x; a[i][j]=x; }算法的時(shí)間復(fù)雜度：O(n2)時(shí)間復(fù)雜度計(jì)算4算法中基