數(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算法及算法分析（算法評(píng)價(jià)）

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

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

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

area=len*wide;

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

建模型：

問(wèn)題涉及的對(duì)象：游泳池的長(zhǎng)len寬wide，面積area；

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

第一章緒論

1.1

引言

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

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

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

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

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

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