算法和算法分析

《算法和算法分析》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)第一章緒論Introduction計算機(jī)學(xué)院霍紅衛(wèi)第一章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法和算法分析1.4.1算法1.4.2算法設(shè)計的要求1.4.3算法效率的度量1.4.4算法的存儲空間的需求HuoHongwei21.1什么是數(shù)據(jù)結(jié)構(gòu)例1圖書館的書目檢索系統(tǒng)自動化問題001高等數(shù)學(xué)樊映川S01…002理論力學(xué)羅遠(yuǎn)祥L01…003高等數(shù)學(xué)華羅庚S01…004線性代數(shù)灤如書S02…!!!!!高等數(shù)學(xué)001,003,…樊映川001,…L002,…理論力學(xué)002,…華羅庚003,…S001,003,…線性代數(shù)004,…灤如書004,…

2、!!!!!!圖書目錄文件示例HuoHongwei31.1什么是數(shù)據(jù)結(jié)構(gòu)例2計算機(jī)和人對弈問題?×?×?××?(a)?×?×???××××××××?×?×?×?×?×(b)井字棋對弈樹(a)井字棋對弈樹(b)對弈樹的局部HuoHongwei41.1什么是數(shù)據(jù)結(jié)構(gòu)例3多叉路口交通燈的管理問題ABC1ACAD11DBABCBDB122EDADBDCA331EA2EB(a)4ECED41(b)五叉路口交通管理示意圖(a)五叉路口(b)表示通路的圖HuoHongwei51.2基本概念和術(shù)語?數(shù)據(jù)(Data):是對信息的一種符號表示。在計算機(jī)科學(xué)中是指所有能輸入到計算機(jī)中并被計算機(jī)程序處理的符號

3、的總稱。?數(shù)據(jù)元素(DataElement):是數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。?一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。?數(shù)據(jù)對象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。?數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個二元組：Data-Structure=(D，S)其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。HuoHongwei61.2基本概念和術(shù)語?數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。?數(shù)據(jù)的邏輯結(jié)構(gòu)是獨(dú)立于計

4、算機(jī)的，對數(shù)據(jù)元素之間的邏輯關(guān)系的描述。從集合的觀點(diǎn)，它們可以形式地用一個二元組B=（D，R）表示，其中D是數(shù)據(jù)元素的集合，R是D上關(guān)系的集合。?按集合的觀點(diǎn)，數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素：一是數(shù)據(jù)元素；二是關(guān)系。HuoHongwei71.2基本概念和術(shù)語通常分為四類基本結(jié)構(gòu)：–集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。–線性結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。–樹型結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。–圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。HuoHongwei81.2基本概念和術(shù)語數(shù)據(jù)的邏輯結(jié)構(gòu)按關(guān)系分為線性結(jié)構(gòu)（關(guān)系是線性的）和非線性結(jié)構(gòu)（

5、關(guān)系是非線性的）。數(shù)據(jù)的邏輯結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)文件結(jié)構(gòu)線性表樹型結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)一般線性表特殊線性表線性表推廣樹二叉樹有向圖無向圖線性表棧和隊串?dāng)?shù)組廣義表HuoHongwei91.2基本概念和術(shù)語?數(shù)據(jù)的物理結(jié)構(gòu)–是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的映象，即存儲表示。映象包括數(shù)據(jù)元素的映象和數(shù)據(jù)關(guān)系的映象。數(shù)據(jù)元素的映象是結(jié)點(diǎn)，即在計算機(jī)內(nèi)用一結(jié)點(diǎn)表示一個數(shù)據(jù)元素（結(jié)點(diǎn)是數(shù)據(jù)結(jié)構(gòu)討論的基本單位）。關(guān)系的映象有兩種，順序映象和非順序映象。HuoHongwei101.2基本概念和術(shù)語?數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu)?順序存儲結(jié)構(gòu)與非順序存儲結(jié)構(gòu)–順序存儲機(jī)構(gòu)是邏輯上相鄰的數(shù)據(jù)元素存鍺在物理位

6、置上相毗鄰的存儲單元里，元素的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。–非順序存儲結(jié)構(gòu)是數(shù)據(jù)元素可以在計算機(jī)內(nèi)任意位置上存放（它不要求邏輯上相鄰的元素在物理位置上也相鄰)，它們的邏輯關(guān)系用指針來鏈接。所以非順序存儲結(jié)構(gòu)又叫鏈?zhǔn)酱鎯Y(jié)構(gòu)。鏈?zhǔn)酱鎯Y(jié)構(gòu)將數(shù)據(jù)元素存放的存儲單元分為兩個部分，分別存放數(shù)據(jù)和指針，稱為數(shù)據(jù)域和指針域。HuoHongwei111.4算法和算法分析?算法：是對特定問題求解步驟的一種描述。算法是指令的有限序列，其中每一條指令表示一個或多個操作。算法具有以下五個特性：–有窮性一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。–確定性算法中每一條指令必須有確切的

7、含義。不存在二義性。且算法只有一個入口和一個出口。–可行性一個算法是可行的。即算法描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。–輸入一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。–輸出一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關(guān)系的量。HuoHongwei121.4算法和算法分析?算法評價標(biāo)準(zhǔn)–正確性——合理的數(shù)據(jù)輸入下，在有限的運(yùn)行時間內(nèi)得出正確的結(jié)果。–健壯性——對不合理的數(shù)據(jù)輸入的反應(yīng)和處理能力。–可讀性——