數(shù)據(jù)結(jié)構(gòu) 第1章

數(shù)據(jù)結(jié)構(gòu)與算法分析（C++版）夏艷2010年秋前言教材：數(shù)據(jù)結(jié)構(gòu)與算法分析（C++版）（第二版）CliffordA.Shaffer著，張銘等譯，電子工業(yè)出版社，2010年1月考核方式：平時成績（40%）+期末考試（60%）其中，平時成績=課堂考勤10%

+日常作業(yè)10%

+課程實驗20%

第一章數(shù)據(jù)結(jié)構(gòu)和算法1.1引言1.2數(shù)據(jù)結(jié)構(gòu)的基本概念1.3問題、算法和程序1.4數(shù)學(xué)預(yù)備知識數(shù)據(jù)結(jié)構(gòu)的發(fā)展及地位《數(shù)據(jù)結(jié)構(gòu)》在計算機科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)的地位計算機專業(yè)本科生必修的學(xué)位課程計算機專業(yè)研究生入學(xué)考試必考科目計算機軟件技術(shù)資格和水平考試內(nèi)容全國計算機等級考試（三級、四級）內(nèi)容為操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)、編譯原理、計算機網(wǎng)絡(luò)等后續(xù)課程提供了必要的知識基礎(chǔ)為提高程序設(shè)計能力、邏輯思維能力和分析問題、解決問題的能力提供了必要的技能訓(xùn)練數(shù)據(jù)結(jié)構(gòu)討論的范疇NiklausWirthAlgorithm+DataStructures=programs程序設(shè)計：為計算機處理問題編制一組指令集算法：處理問題的策略數(shù)據(jù)結(jié)構(gòu)：問題的數(shù)學(xué)模型例1書目自動檢索系統(tǒng)

登錄號：書名：作者名：分類號：出版單位：出版時間：價格：書目卡片書目文件按書名按作者名按分類號索引表線性表例2人機對奕問題樹……..……..…...…...…...…...例3.旅行商問題---圖烏魯木齊蘭州西安成都武漢鄭州北京沈陽上海長沙廣州1892676511659841900534842貴陽昆明1100902學(xué)習數(shù)據(jù)結(jié)構(gòu)的必要性信息處理計算機功能越強大

嘗試更復(fù)雜的問題

需要更高效的程序

研究數(shù)據(jù)結(jié)構(gòu)和算法成為計算機科學(xué)的核心問題數(shù)據(jù)結(jié)構(gòu)的選擇算法效率：一種算法能在所要求的資源限制內(nèi)將問題解決好，則稱該算法是有效率的。資源限制：空間、時間算法代價：算法消耗的資源量。數(shù)據(jù)結(jié)構(gòu)的選擇步驟：分析問題，確定任何算法會遇到的資源限制確定必須支持的基本操作，并度量每種操作所受到資源限制選擇最適合這些需求的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的選擇考慮的問題開始時將所有數(shù)據(jù)項都插入數(shù)據(jù)結(jié)構(gòu)，or與其他操作混合一起插入？數(shù)據(jù)項能否刪除？所有數(shù)據(jù)項是否按一個已定義好的順序排列，是否允許其他查找方式？數(shù)據(jù)結(jié)構(gòu)的選擇效益、代價與數(shù)據(jù)結(jié)構(gòu)每一個問題都有時間和空間約束，分析問題，尋找最優(yōu)數(shù)據(jù)結(jié)構(gòu)例子1.1第一章數(shù)據(jù)結(jié)構(gòu)和算法

1.1引言1.2數(shù)據(jù)結(jié)構(gòu)的基本概念1.3問題、算法和程序1.4數(shù)學(xué)預(yù)備知識1.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)(data)：是描述客觀事物的數(shù)字、字符以及其他能輸入到計算機中并可被計算機程序處理的符號的集合。數(shù)據(jù)項：數(shù)據(jù)的不可分割的最小單位。類型（type）：一組值的集合。例如,布爾類型由兩個值TRUE和FALSE組成;整數(shù)也構(gòu)成一個類型。數(shù)據(jù)類型：一種類型和定義在該類型上的一組操作。例如整數(shù)類型是某個區(qū)間上的整數(shù)集合(區(qū)間大小依賴于不同的計算機),定義在其上的操作為加、減、乘、除和取模等算術(shù)運算。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型（ADT）：是對數(shù)據(jù)類型的邏輯形式的規(guī)范化描述。一個ADT的定義并不涉及它的實現(xiàn)細節(jié),這些實現(xiàn)細節(jié)對于ADT的用戶是隱藏的。隱藏實現(xiàn)細節(jié)的過程稱為封裝(encapsulation)。數(shù)據(jù)結(jié)構(gòu):

是ADT的實現(xiàn)。按照邏輯關(guān)系組織起來的一批數(shù)據(jù),按一定的存儲方法把它存儲在計算機中,

并在這些數(shù)據(jù)上定義了一個運算的集合。

ADT的例子（1）集合與集合的并、交、差運算可以定義為一個ADT一個ADT包含哪些操作由設(shè)計者根據(jù)需要確定例如，對于集合，如果需要，也可以把判別一個集合是否為空集或兩個集合是否相等作為集合上的操作

ADT的例子（2）駕駛汽車的主要操作包括控制方向、加速和剎車幾乎所有的汽車都通過轉(zhuǎn)動方向盤控制方向，通過踩油門加速，通過踩車閘剎車汽車的這種設(shè)計可以看作是具有“控制方向盤”、“加速”和“剎車”操作的一個ADT兩輛汽車可以用截然不同的方式實現(xiàn)這些操作但是大多數(shù)司機都能夠駕駛許多不同的汽車因為ADT提供了一致的操作方法

邏輯形式和物理形式數(shù)據(jù)項有邏輯形式（logicalform）和物理形式（physicalform）兩個方面邏輯形式：用ADT給出的數(shù)據(jù)項的定義物理形式：數(shù)據(jù)結(jié)構(gòu)中對數(shù)據(jù)項的實現(xiàn)實現(xiàn)一個ADT時，是處理相關(guān)數(shù)據(jù)項的物理形式在程序中其他地方使用ADT時，涉及到相關(guān)數(shù)據(jù)項的邏輯形式數(shù)據(jù)類型ADT：類型操作數(shù)據(jù)項：

邏輯形式數(shù)據(jù)項：

物理形式數(shù)據(jù)結(jié)構(gòu)：存儲空間子程序數(shù)據(jù)項、抽象數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系A(chǔ)DT定義了數(shù)據(jù)類型的邏輯形式數(shù)據(jù)結(jié)構(gòu)是實現(xiàn)數(shù)據(jù)類型的物理形式第一章數(shù)據(jù)結(jié)構(gòu)和算法

1.1引言1.2數(shù)據(jù)結(jié)構(gòu)的基本概念1.3問題、算法和程序1.4數(shù)學(xué)預(yù)備知識1.3問題、算法和程序問題是一個需要完成的任務(wù)對應(yīng)一組輸入有一組相應(yīng)的輸出問題的定義不應(yīng)包含有關(guān)怎樣解決問題的限制問題的定義應(yīng)該包含對任何可行方案所需資源的限制任何計算機程序只能使用可用的主存儲器和磁盤空間必須在合理的時間內(nèi)完成運行問題（續(xù)）可以把問題看作數(shù)學(xué)函數(shù)函數(shù)(function)是輸入(即定義域，domain)和輸出(即值域，range)之間的一種映射關(guān)系函數(shù)的輸入可以是一個值或是一些信息這些值組成的輸入稱為函數(shù)的參數(shù)(parameter)參數(shù)的一組選定值稱為問題的一個實例(instance)不同的實例可能產(chǎn)生相同的輸出，但是對于問題的任何一個實例，只要把它作為給定輸入，每次函數(shù)計算得到的輸出就必然相同算法是指令的有限序列，其中每一條指令表示一個或多個操作如果將問題看作函數(shù)，那么算法就是把輸入轉(zhuǎn)換為輸出把輸入映射到輸出一個問題可以用多種算法來解決算法的基本特性有限性一個算法必須總是在執(zhí)行有限步之后結(jié)束確定性算法中的每一步都必須具有確切的含義，不會產(chǎn)生二義性可行性算法中描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的輸入一個算法有零個或多個輸入，這些輸入取自某個特定的對象集合輸出一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關(guān)系的量程序是使用某種程序設(shè)計語言對一個算法的具體實現(xiàn)不是所有的計算機程序都是算法算法必須可以終止操作系統(tǒng)是一個程序，而不是算法算法的代價是算法運行所需要的計算機資源的量需要的時間資源的量稱為時間代價需要的空間(即存儲器)資源的量稱為空間代價這個量應(yīng)集中反映算法所采用的方法的效率,而與運行該算法的硬件、軟件環(huán)境無關(guān)算法的代價是算法的效率的度量引入算法的代價這個概念是為了比較解決同一問題的不同算法的效率之間的差異第一章數(shù)據(jù)結(jié)構(gòu)和算法

1.1引言1.2數(shù)據(jù)結(jié)構(gòu)的基本概念1.3問題、算法和程序1.4數(shù)學(xué)預(yù)備知識1.4數(shù)學(xué)預(yù)備知識集合和關(guān)系對數(shù)遞歸