第2章數據結構與

算法概述前言計算機是一門研究用計算機進行信息表示和處理的科學。這里面涉及到兩個問題：信息的表示，信息的處理。信息的表示和組織又直接關系到處理信息的程序的效率。

隨著應用問題的不斷復雜，使許多系統程序和應用程序的規模很大，結構又相當復雜。因此，必須分析待處理問題中的對象的特征及各對象之間存在的關系，這就是數據結構這門課所要研究的問題。

數據結構與算法是介于數學、計算機硬件、計算機軟件三者之間的核心技術，不僅是一般程序設計的基礎，而且是設計和實現編譯程序、操作系統、數據庫系統及其他系統程序和大型應用程序的重要基礎。2.1數據結構基本知識2.1.1數據結構的概念2.1.2數據結構的邏輯結構與存儲結構4數據結構的例子姓名電話號碼陳四。。。。。例1：電話號碼查詢系統

設有一個電話號碼薄，它記錄了N個人的名字和其相應的電話號碼，假定按如下形式安排：(a1,b1)，(a2,b2)，…(an,bn)，其中ai,bi(i=1，2…n)

分別表示某人的名字和電話號碼。本問題是一種典型的表格問題。如表1-1，數據與數據成簡單的一對一的線性關系。表1-1

線性表結構例2：磁盤目錄文件系統

磁盤根目錄下有很多子目錄及文件，每個子目錄里又可以包含多個子目錄及文件，但每個子目錄只有一個父目錄，依此類推：本問題是一種典型的樹型結構問題，如圖1-1

，數據與數據成一對多的關系，是一種典型的非線性關系結構—樹形結構。圖1-1

樹形結構例3：交通網絡圖

從一個地方到另外一個地方可以有多條路徑。本問題是一種典型的網狀結構問題，數據與數據成多對多的關系，是一種非線性關系結構。佛山惠州廣州中山東莞深圳珠海圖1-2

網狀結構數據結構主要研究諸如線性結構，樹形結構及圖形結構等非數值性數學模型在計算機中的表示及操作。82.1.1數據結構的基本概念數據數據元素數據對象數據結構9

數據(Data)

數據是信息的載體對客觀事物的符號表示能輸入到計算機中能被計算機加工處理數據的形式可以是整數,實數,字符,圖像,聲音…10數據元素(dataelement)數據元素(DataElement)

：是數據的基本單位，在程序中通常作為一個整體來進行考慮和處理。一個數據元素可由若干個數據項(DataItem)組成。數據項是數據的不可分割的最小單位。數據項是對客觀事物某一方面特性的數據描述。11數據項學號姓名性別出生日期聯系電話入學成績數據元素數據對象(DataObject)是性質相同的數據元素的集合，是數據的一個子集。如字符集合C={‘A’,’B’,’C,…}。12數據、數據元素與數據對象關系13數據數據元素數據對象2.1.2

數據結構的邏輯結構與物理結構數據結構指同一數據對象中各個數據元素間存在的一種或多種特定關系的集合主要研究：數據元素之間固有的邏輯關系——數據邏輯結構；數據元素及關系在計算機內的表示——數據物理結構；對數據結構的操作——算法。14

數據元素之間的關系可以是元素之間代表某種含義的自然關系，也可以是為處理問題方便而人為定義的關系，這種自然或人為定義的“關系”稱為數據元素之間的邏輯關系，相應的結構稱為邏輯結構。數據元素之間的邏輯結構有四種基本類型①

集合：結構中的數據元素除了“同屬于一個集合”外，沒有其它關系。②線性結構：結構中的數據元素之間存在一對一的關系。③

樹型結構：結構中的數據元素之間存在一對多的關系。④圖狀結構或網狀結構：結構中的數據元素之間存在多對多的關系。15物理結構-存儲結構數據結構在計算機內存中的存儲包括數據元素的存儲和元素之間的關系的表示。元素之間的關系在計算機中有兩種不同的表示方法：順序表示和非順序表示。由此得出兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。順序存儲結構：用數據元素在存儲器中的相對位置來表示數據元素之間的邏輯結構(關系)。

鏈式存儲結構：在每一個數據元素中增加一個存放另一個元素地址的指針(pointer)，用該指針來表示數據元素之間的邏輯結構(關系)。例：設有數據集合A={3.0,2.3,5.0,-8.5,11.0}，兩種不同的存儲結構。順序結構：數據元素存放的地址是連續的；鏈式結構：數據元素存放的地址是否連續沒有要求。數據的邏輯結構和物理結構是密不可分的兩個方面，一個算法的設計取決于所選定的邏輯結構，而算法的實現依賴于所采用的存儲結構。在C語言中，用一維數組表示順序存儲結構；用結構體類型表示鏈式存儲結構。數據結構的三個組成部分：邏輯結構：數據元素之間邏輯關系的描述

D_S=（D，S）存儲結構：數據元素在計算機中的存儲及其邏輯關系的表現稱為數據的存儲結構或物理結構。數據操作：對數據要進行的運算。本課程中將要討論的三種邏輯結構及其采用的存儲結構如圖所示。數據的邏輯結構非線性結構集合圖狀結構有向圖無向圖樹形結構一般樹二叉樹線性結構一般線性表線性表推廣廣義表數組串受限線性表棧和隊列線性表樹圖順序存儲結構鏈式存儲結構復合存儲結構邏輯結構物理結構（3）數據的操作

數據的操作是在數據的邏輯結構上定義的操作算法。數據結構的主要運算包括：⑴建立(Create)一個數據結構；⑵消除(Destroy)一個數據結構；⑶從一個數據結構中刪除(Delete)一個數據元素；⑷把一個數據元素插入(Insert)到一個數據結構中；⑸對一個數據結構進行訪問(Access)；⑹對一個數據結構(中的數據元素)進行修改(Modify)；⑺對一個數據結構進行排序(Sort)；⑻對一個數據結構進行查找(Search)。

202.1.3數據類型與抽象數據類型數據類型抽象數據類型21數據類型是一個值的集合和定義在這個集合上的一組操作的總稱。抽象數據類型(ADT)指一個數學模型以及定義在該模型上的一組操作。特點僅取決于邏輯特性,而與計算機內部如何表示和實現無關。抽象數據類型的分類原子類型：值不可再分固定聚合類型：成分數目固定可變聚合類型：成分數目可變抽象數據類型的定義三元組表示：ADT=(D,S,P)ADT抽象數據類型名{數據對象D：<數據對象的定義>數據關系S：<數據關系的定義>基本操作P：<基本操作的定義>}ADT抽象數據類型名2.2算法與算法分析2.2.1算法的概念2.2.2算法分析262.2.1算法概念為解決特定問題所采用的步驟描述，它是指令的有限序列，其中每條指令表示一個或多個操作。27算法特性有窮性：算法執行有限步后,自動停止確定性：含義確切,無二義性可行性：每個基本操作均可實現輸入：零個或多個輸入輸出：至少一個輸出28算法描述自然語言流程圖類語言高級語言29BEGINi:=1；s:=0；WHILE(i<=10)DO[s:=s+i；i:=i+1;]END類語言流程圖2.2.2時間復雜度和空間復雜度能完成任務不一定是最好的算法,不同算法可能用的時間,空間和效率是不同的。一個算法的優劣可以用時間復雜度與空間復雜度來衡量。算法分析內容時間復雜度空間復雜度算法復雜度的數學表示用數學符號O表示，n為問題規模例：O（1）；O（nk）；O（en）302.2.2時間復雜度和空間復雜度算法的優劣用頻度和時間復雜度衡量語句頻度某語句執行的次數，記作F(n)時間復雜度以語句頻度最大的語句度量31時間復雜度舉例

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]

}32n2n3語句頻度f(n)=n3+n2時間復雜度O(n3)常見的時間復雜度O(1)O(n)O(n2)O(log2n)O(nlog2n)O(2n).....33Tn2nnlogn2a·2n+b·n3+c·n2+d·n·log2(n)+e·n+fa<>0時，時間復雜度就是O(2n);a=0,b<>0時間復雜度就是O(n3);a,b=0,c<>0時間復雜度就是O