數據結構講義

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

DonaldErvinKnuth《TheArtofComputerProgramming》

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

組合項年月日學號姓名班號性別出生日期入學成績原子項基本術語2數據對象是性質相同的數據元素的集合，是數據的一個子集。

學號姓名班號性別出生日期入學成績

001劉影01女19840417623002李恒01男19831211679003陳誠02男19840910638………………數據結構具有結構的數據元素的集合。它包括數據元素的邏輯結構、存儲結構和相適應的運算。數據元素數據元素之間的邏輯關系，與計算機無關。可用一個二元組表示：Data_Structure=(D,R)D：數據元素的有窮集合，R：集合D上關系的有窮集合。

[例]設有數據結構B=(D,R)，其中D={d1,d2,d3,d4,d5,d6}，

R={r}，

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

a1a2...ai...an

(2)鏈式存儲：在存儲結點中增加若干指針域，記錄后繼或者相關結點的地址（指針）。

a11220...a3

1342...a21072...10001004

100010041072107612201224指針結點結點順序存儲和鏈式存儲運算（操作）：在數據邏輯結構上定義的一組數據被使用的方式，其具體實現(xiàn)要在存儲結構上進行。幾種常用的運算有：

(1)建立數據結構(6)檢索*

(2)清除數據結構(7)更新

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

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

(5)排序

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

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

抽象數據類型名{

數據對象：〈數據對象的定義〉

數據關系：〈數據關系的定義〉

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

抽象數據類型名基本操作名（參數表）

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

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

存在正的常數c和n0，使得當nn0時，

0T(n)

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

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

T(n)=2

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

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

}

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

算法的時間復雜度為：O(n)---線性階時間復雜度計算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算法的時間復雜度：O(n3)時間復雜度計算3在難以精確計算基本操作執(zhí)行次數的情況下，只求出關于n的增長率即可。例4:for(i=2;i<=n;++i) for(j=2;j<=i-1;++j) { ++x; a[i][j]=x; }算法的時間復雜度：O(n2)時間復雜度計算4算法中基