算法和算法分析

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

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

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

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

4、算機(jī)的，對(duì)數(shù)據(jù)元素之間的邏輯關(guān)系的描述。從集合的觀點(diǎn)，它們可以形式地用一個(gè)二元組B=（D，R）表示，其中D是數(shù)據(jù)元素的集合，R是D上關(guān)系的集合。?按集合的觀點(diǎn)，數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：一是數(shù)據(jù)元素；二是關(guān)系。HuoHongwei71.2基本概念和術(shù)語(yǔ)通常分為四類基本結(jié)構(gòu)：–集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無(wú)其它關(guān)系。–線性結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。–樹(shù)型結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。–圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。HuoHongwei81.2基本概念和術(shù)語(yǔ)數(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)線性表樹(shù)型結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)一般線性表特殊線性表線性表推廣樹(shù)二叉樹(shù)有向圖無(wú)向圖線性表?xiàng)：完?duì)串?dāng)?shù)組廣義表HuoHongwei91.2基本概念和術(shù)語(yǔ)?數(shù)據(jù)的物理結(jié)構(gòu)–是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的映象，即存儲(chǔ)表示。映象包括數(shù)據(jù)元素的映象和數(shù)據(jù)關(guān)系的映象。數(shù)據(jù)元素的映象是結(jié)點(diǎn)，即在計(jì)算機(jī)內(nèi)用一結(jié)點(diǎn)表示一個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)是數(shù)據(jù)結(jié)構(gòu)討論的基本單位）。關(guān)系的映象有兩種，順序映象和非順序映象。HuoHongwei101.2基本概念和術(shù)語(yǔ)?數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu)?順序存儲(chǔ)結(jié)構(gòu)與非順序存儲(chǔ)結(jié)構(gòu)–順序存儲(chǔ)機(jī)構(gòu)是邏輯上相鄰的數(shù)據(jù)元素存鍺在物理位

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

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