數(shù)據(jù)結(jié)構(gòu)與算法分析：第一章 緒論

1DataStructuresandAlgorithmsAnalysis數(shù)據(jù)結(jié)構(gòu)與算法分析2

第一章緒論

1.1

引言

1.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)基本概念；

1.3算法及算法分析（算法評價(jià)）

3數(shù)據(jù)結(jié)構(gòu)的發(fā)展概況和地位《數(shù)據(jù)結(jié)構(gòu)》作為一門獨(dú)立的課程在國外是從1968年才開始的。《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)中一門綜合性的專業(yè)基礎(chǔ)課。4程序=算法+數(shù)據(jù)結(jié)構(gòu)程序是對所要解決問題的各個(gè)對象和處理規(guī)則的描述，或者說是數(shù)據(jù)結(jié)構(gòu)和算法的描述（NiklausWirth1984）5課程地位計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科生的專業(yè)基礎(chǔ)課程之一計(jì)算機(jī)專業(yè)本科生必修的學(xué)位課程計(jì)算機(jī)專業(yè)研究生入學(xué)考試必考科目計(jì)算機(jī)軟件技術(shù)資格和水平考試內(nèi)容全國計(jì)算機(jī)等級考試（三級、四級）內(nèi)容6課程地位（續(xù)）為操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)、編譯原理、計(jì)算機(jī)網(wǎng)絡(luò)等后續(xù)課程提供了必要的知識基礎(chǔ)為提高程序設(shè)計(jì)能力、邏輯思維能力和分析問題、解決問題的能力提供了必要的技能訓(xùn)練7本課程研究的問題數(shù)據(jù)：數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識別和處理的符號的集合。數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)數(shù)值問題—對以數(shù)學(xué)方式表示的問題求數(shù)值解。例如，代數(shù)方程計(jì)算、矩陣計(jì)算、線性方程組求解、數(shù)值積分、微分方程求解等；非數(shù)值問題—求非數(shù)值解。例如，排序查找、模式匹配等。數(shù)據(jù)結(jié)構(gòu)的研究問題：非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，及如何表示，如何存儲，如何處理8

數(shù)值問題與非數(shù)值問題1）數(shù)值問題例1已知：游泳池的長len和寬wide，求面積area◆設(shè)計(jì)求解問題的方法◆編程main(){ intlen,wide,area;

scanf(“%d%d%\n”,&l,&w);

area=len*wide;

printf(“area=%d”,area);}◆

建模型：

問題涉及的對象：游泳池的長len寬wide，面積area；

對象之間的關(guān)系：area=lenwide9例3多叉路口交通燈管理問題CEDABABACADBABCBDDADBDCEAEBECED圖10學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的必要性數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)的組織 更有效的程序計(jì)算機(jī)功能越強(qiáng)大嘗試更復(fù)雜的問題（應(yīng)用）更復(fù)雜的問題需要更大的計(jì)算量工作越復(fù)雜就越偏離人們的日常經(jīng)驗(yàn)11數(shù)據(jù)的組織對于任意組織的一組數(shù)據(jù)項(xiàng)能夠查找出指定的數(shù)據(jù)項(xiàng)，將這些數(shù)據(jù)項(xiàng)處理成任何期望得到的順序，或者更改任何特定數(shù)據(jù)項(xiàng)的值。同一個(gè)程序，選擇不同的數(shù)據(jù)結(jié)構(gòu)和算法可能會產(chǎn)生很大的差異，有的可能在幾秒鐘就運(yùn)行完畢，也有可能需要幾天時(shí)間才能完成。12效率Efficiency一種解決方案如果能在所要求的資源限制（resourceconstraints）內(nèi)將問題解決好，則稱該算法是有效率的（efficient）空間Space時(shí)間Time一種算法的代價(jià)（cost）是指這種算法消耗的資源量13數(shù)據(jù)結(jié)構(gòu)的選擇選擇數(shù)據(jù)結(jié)構(gòu)的步驟：分析問題，以確定解決方案會遇到的資源限制確定必須支持的基本操作，并度量每種操作的資源限制選擇最適合這些需求的數(shù)據(jù)結(jié)構(gòu)14考慮的問題開始時(shí)是將所有數(shù)據(jù)都插入數(shù)據(jù)結(jié)構(gòu)，還是與其它操作混合在一起插入?數(shù)據(jù)是否要刪除?所有數(shù)據(jù)是按一些定義明確的順序來處理，還是允許隨機(jī)訪問?15數(shù)據(jù)結(jié)構(gòu)的原則每個(gè)數(shù)據(jù)結(jié)構(gòu)都將代價(jià)與效益聯(lián)系在一起很少有一個(gè)數(shù)據(jù)結(jié)構(gòu)在所有情況下都比其它算法好一個(gè)數(shù)據(jù)結(jié)構(gòu)需要：一定的空間存儲它的每一個(gè)數(shù)據(jù)項(xiàng)，一定的時(shí)間來執(zhí)行單個(gè)基本操作，一定的程序設(shè)計(jì)工作。16數(shù)據(jù)結(jié)構(gòu)的原則(cont)每一個(gè)問題都有可利用空間和時(shí)間的約束只有對問題的特性進(jìn)行仔細(xì)分析之后，才能得到執(zhí)行這項(xiàng)任務(wù)最好的數(shù)據(jù)結(jié)構(gòu)。一個(gè)銀行業(yè)務(wù)的例子：新開帳戶：花費(fèi)幾分鐘交易：幾秒鐘注銷帳戶：整夜17課程的目的加強(qiáng)一個(gè)概念：每一個(gè)數(shù)據(jù)結(jié)構(gòu)都有其相關(guān)的代價(jià)和效益學(xué)會常用的數(shù)據(jù)結(jié)構(gòu)這些數(shù)據(jù)結(jié)構(gòu)形成了一個(gè)程序員的基本數(shù)據(jù)結(jié)構(gòu)工具箱了解如何評價(jià)一個(gè)數(shù)據(jù)結(jié)構(gòu)或算法的代價(jià)（cost）這些技術(shù)也使得程序員能夠判斷自己或別人發(fā)明的新數(shù)據(jù)結(jié)構(gòu)的價(jià)值。18教學(xué)目的學(xué)會分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的算法，并初步掌握算法的時(shí)間分析和空間分析技術(shù)本課程的學(xué)習(xí)過程也是復(fù)雜程序設(shè)計(jì)的訓(xùn)練過程，要求學(xué)生編寫的程序結(jié)構(gòu)清楚和正確易讀，符合軟件工程的規(guī)范。為今后的程序設(shè)計(jì)作一些鋪墊19

第一章緒論

1.1

引言

1.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)基本概念

1.3算法及算法分析（算法評價(jià)）

20術(shù)語類型（type）是一組值的集合數(shù)據(jù)項(xiàng)（dataitemorelement）是一條信息或者一個(gè)記錄數(shù)據(jù)類型（datatype）是指一種類型和定義在該類型上的一組操作數(shù)據(jù)項(xiàng)又稱為數(shù)據(jù)類型的成員簡單數(shù)據(jù)項(xiàng)不包含子結(jié)構(gòu)復(fù)雜數(shù)據(jù)項(xiàng)可能包含多項(xiàng)信息21抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（ADT）：根據(jù)一組值的集合定義的數(shù)據(jù)類型和該數(shù)據(jù)類型上的一組操作集每個(gè)ADT操作由它的輸入和輸出定義。封裝：隱藏實(shí)現(xiàn)細(xì)節(jié)22數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是ADT的實(shí)際實(shí)現(xiàn)與ADT聯(lián)系在一起的每個(gè)操作由一個(gè)或多個(gè)子程序來實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)通常涉及數(shù)據(jù)在內(nèi)存中的組織方式文件結(jié)構(gòu)是指在外存儲器（如磁盤驅(qū)動器）上數(shù)據(jù)的組織23抽象化ADT：復(fù)雜問題的抽象化：隱喻標(biāo)志的層次化Ex:晶體管門電路CPU.ADT在程序中通過特定的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，然而在設(shè)計(jì)使用ADT的那部分程序時(shí)，我們只關(guān)心數(shù)據(jù)類型上的操作，而不關(guān)心數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)24邏輯vs.物理形式數(shù)據(jù)項(xiàng)有邏輯形式和物理形式。邏輯形式：用ADT來給出數(shù)據(jù)項(xiàng)的定義Ex:數(shù)學(xué)意義上的integers：+,-物理形式：數(shù)據(jù)結(jié)構(gòu)中對數(shù)據(jù)項(xiàng)的實(shí)現(xiàn)。Ex:16/32bitintegers,overflow.25數(shù)據(jù)類型ADT:類型操作數(shù)據(jù)項(xiàng):

邏輯形式數(shù)據(jù)項(xiàng):

物理形式數(shù)據(jù)結(jié)構(gòu):存儲空間子程序26問題問題：一個(gè)需要完成的工作。即一組輸入就有一組相應(yīng)的輸出。問題的定義將包含對任何可行方案所需資源的限制。問題數(shù)學(xué)的函數(shù)函數(shù)是輸入（domain

）和輸出（range）之間的一種映射關(guān)系。函數(shù)的輸入可以是一個(gè)值，或者是一個(gè)信息的集合。這些值組成的輸入稱為函數(shù)的參數(shù)。每一個(gè)特定的輸入，每次函數(shù)計(jì)算得到的輸出就必然相同。27算法與程序算法：解決問題的一種方法或者一個(gè)過程。如果將問題看做函數(shù)，那么算法就是把輸入轉(zhuǎn)換為輸出一個(gè)輸入到輸出