第一章緒論

基本概念和術(shù)語

一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)：所有能輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)程序處理的符號(hào)的總稱。是計(jì)算機(jī)操作的對象的總稱。是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。

數(shù)據(jù)元素：是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”，是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位?？捎扇舾蓚€(gè)數(shù)據(jù)項(xiàng)組成。

數(shù)據(jù)項(xiàng)：是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。數(shù)據(jù)元素可以是數(shù)據(jù)項(xiàng)的集合。

數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。

數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”。

數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。

數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為一下四類：

線性結(jié)構(gòu)：有唯一前驅(qū)和后繼

樹形結(jié)構(gòu)：一對多

圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：多對多

集合結(jié)構(gòu)：無關(guān)系

特殊的集合結(jié)構(gòu)：鍵值對

數(shù)據(jù)結(jié)構(gòu)的形式定義為：

數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組：Data_Structures = (D,S)

其中D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：邏輯結(jié)構(gòu)在存儲(chǔ)器中的映像。

關(guān)系的映像方法：（表示<x, y>的方法）

順序映像：以相對的存儲(chǔ)位置表示后繼關(guān)系。整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息。

鏈?zhǔn)接诚瘢阂愿郊有畔ⅲㄖ羔槪┍硎竞罄^關(guān)系。需要用一個(gè)和x在一起的附加信息指示y的存儲(chǔ)位置。

在不同的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)可有不同的描述方法。當(dāng)用高級(jí)程序設(shè)計(jì)語言進(jìn)行編程時(shí)，通常可用高級(jí)編程語言中提供的數(shù)據(jù)類型描述之。

二、數(shù)據(jù)類型

不同類型的變量，所能取的值的范圍不同，所能進(jìn)行的操作也不同

三、抽象數(shù)據(jù)類型（Abstract Data Type簡稱ADT）

是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。

ADT有兩個(gè)重要特征：

數(shù)據(jù)抽象：用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）

數(shù)據(jù)封裝：將實(shí)體的外部特征和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。

抽象數(shù)據(jù)類型的描述方法：

抽象數(shù)據(jù)類型可用（D,S,P）三元組表示。D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集。

多形數(shù)據(jù)類型：是指其值成分不確定的數(shù)據(jù)類型。

抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)

抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型（高級(jí)程序設(shè)計(jì)語言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)類型來實(shí)現(xiàn)）

四、算法和算法分析

算法是為了解決某類問題而規(guī)定的一個(gè)有限長的操作序列。一個(gè)算法必須滿足以下五個(gè)重要特性：

1. 有窮性：

對于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束。即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成。

1. 確定性

對于某種情況下所執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑，不允許有二義性。

1. 可行性

算法中的所有操作必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。

1. 有輸入

作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。

1. 有輸出

它是一組與輸入有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。

算法設(shè)計(jì)的原則：

1. 正確性

滿足以特定“規(guī)格說明”方式給出的需求

1. 不含語法錯(cuò)誤
2. 輸出滿足要求的結(jié)果
3. 精心選擇、典型、苛刻且刁難性樣例給出結(jié)果
4. 一切樣例給出結(jié)果

C是衡量算法是否合格標(biāo)準(zhǔn)

1. 可讀性

易于人的理解

1. 健壯性

輸入數(shù)據(jù)非法，能給出相應(yīng)的處理。處理出錯(cuò)的方法不應(yīng)只是中斷程序的執(zhí)行，而是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值。

1. 高效率與低存儲(chǔ)量需求

效率是指算法執(zhí)行時(shí)間，存儲(chǔ)量是指所需最大存儲(chǔ)空間。

算法效率的度量

事后統(tǒng)計(jì)法：

缺點(diǎn)：1.必須執(zhí)行程序2.其他因素掩蓋算法本質(zhì)

事前分析估算法

和算法執(zhí)行時(shí)間相關(guān)的因素：

1. 算法選用的策略
2. 問題的規(guī)模
3. 編寫的語言
4. 編譯質(zhì)量
5. 計(jì)算機(jī)速度

一個(gè)特定算法“運(yùn)行工作量”只依賴于問題的規(guī)模（通常用n表示）它是問題規(guī)模的函數(shù)。

算法執(zhí)行時(shí)間增長率和f(n)的增長率隨n增長相同。T(n) = O(f(n))。

T(n)為算法（漸進(jìn)）時(shí)間復(fù)雜度

如何估算算法的時(shí)間復(fù)雜度？

算法=控制結(jié)構(gòu) 原操作

算法執(zhí)行時(shí)間=Σ原操作執(zhí)行時(shí)間x原操作執(zhí)行次數(shù)

從算法中選取一種對于所研究的問題來說是基本操作的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。

冒泡排序可優(yōu)化到nlogn

多項(xiàng)式時(shí)間問題P問題

算法的存儲(chǔ)空間需求

S(n)=O(g(n))表示隨著問題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長率與g(n)的增長率一樣

算法的存儲(chǔ)量包括：

1. 輸入數(shù)據(jù)2.程序本身3.輔助變量

若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。

若所需額外空間相對于輸入數(shù)據(jù)量來說是常熟，則稱此算法為原地工作。

若所需存儲(chǔ)量依賴于特定的輸入，則通常按最壞情況考慮。