數(shù)據(jù)結(jié)構(gòu)第一章-展示頁(yè)
2024-08-19 16:53本頁(yè)面
【正文】 構(gòu)（ 4學(xué)時(shí)） 遞歸與樹(shù)（ 4學(xué)時(shí)） 圖（ 8學(xué)時(shí)） 查找（ 4學(xué)時(shí)） 排序（ 4學(xué)時(shí)） 算法設(shè)計(jì)策略（ 6學(xué)時(shí)） 使用教材 教材 ： 《 數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言版） 》 ， 嚴(yán)蔚敏 吳偉民編著，清華大學(xué)出版社 參考書(shū) ： 《 計(jì)算機(jī)算法設(shè)計(jì)與分析 》 ，王曉東編著， 電子工業(yè)出版社 聯(lián)系方式 ? Email : ? Address：礦電樓 102 ? Office Tel： 83683048 第一章 數(shù)據(jù)結(jié)構(gòu)和算法概述 本章內(nèi)容 問(wèn)題的求解 數(shù)據(jù)結(jié)構(gòu)及抽象數(shù)據(jù)類型 算法的概念和特性 算法的效率度量 漸進(jìn)表示法和漸進(jìn)記號(hào) 問(wèn)題求解 ? 階段和步驟 ? 獲取需求（問(wèn)題），以保證解決的問(wèn)題正是需要的（ solve the right problem）； ? 分析問(wèn)題，將其分解為粒度更小的部分； ? 針對(duì)問(wèn)題（子問(wèn)題）給出相應(yīng)的解決方案，易于理解和修改； ? 估算解決方案的開(kāi)銷，以事先判斷其可行性； ? 維護(hù)和演化 問(wèn)題求解 ? 通過(guò) ? 問(wèn)題抽象 ? 數(shù)據(jù)抽象 ? 算法抽象 分析問(wèn)題，應(yīng)用數(shù)據(jù)結(jié)構(gòu)和算法來(lái)設(shè)計(jì)和實(shí)現(xiàn)高效的程序 問(wèn)題求解 ? 例子 ? 從一組人中找出最高、最矮，及身高最適中的人。 ? 有 12個(gè)外表完全相同的球，只有一個(gè)不標(biāo)準(zhǔn)，或輕或重，要求用天平以最少的次數(shù)找出該球，并判定其輕重 。 ? 問(wèn)題抽象 、數(shù)據(jù)抽象、算法抽象 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)結(jié)構(gòu) 是相互之間存在一種或多種特定 關(guān)系 的數(shù)據(jù) 元素 的集合 ? 數(shù)據(jù)的 邏輯結(jié)構(gòu) ? 圖 ?樹(shù) ?二叉樹(shù) ?線性表 ? 數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu) ? 順序方法、鏈接方法 ? 數(shù)據(jù)的 運(yùn)算 ? 增、刪、查、改 ? 排序、檢索 存儲(chǔ) 數(shù)據(jù)結(jié)構(gòu) 邏輯 運(yùn)算 ? 數(shù)據(jù)的邏輯結(jié)構(gòu) ? 數(shù)據(jù)的邏輯結(jié)構(gòu)可以用一組數(shù)據(jù)（表示為結(jié)點(diǎn)集合 D），以及這些數(shù)據(jù)之間的一組二元關(guān)系（關(guān)系集合 S）來(lái)表示： ( D ， S ) ? 其中 ? D 是數(shù)據(jù)元素的有限集， 是由有限個(gè)結(jié)點(diǎn)組成的集合，每一個(gè)結(jié)點(diǎn)都代表一個(gè)數(shù)據(jù)或一組有明確結(jié)構(gòu)的數(shù)據(jù) ? S 是 D上關(guān)系的有限集， 是定義在集合 D上的一組關(guān)系，用它描述結(jié)點(diǎn)數(shù)據(jù)之間的邏輯關(guān)系 Data_Structures = (D, S) 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)的邏輯結(jié)構(gòu) ? 元素的數(shù)據(jù)類型 ? 高級(jí)語(yǔ)言中指數(shù)據(jù)的取值范圍及其上可進(jìn)行的操作的總稱 ? 例 C語(yǔ)言中 ? 基本數(shù)據(jù)類型： int, char, float等 ? 構(gòu)造數(shù)據(jù)類型：數(shù)組、結(jié)構(gòu)體、共用體、枚舉 ? 指針、空 (void)類型 ? 用戶也可用 typedef 自己定義數(shù)據(jù)類型 ? 結(jié)點(diǎn)的類型可以是基本數(shù)據(jù)類型，也可以根據(jù)應(yīng)用的需要來(lái)靈活定義 typedef struct { int num。 float score。 STUDENT stu, *pstu。 ? “關(guān)系”的映象 ? 每一個(gè)關(guān)系元組（ d1 ,d2） ∈ S（其中 d1, d2∈ D是結(jié)點(diǎn)）， d1 ,d2的邏輯后繼關(guān)系應(yīng)映射為存儲(chǔ)單元的地址順序關(guān)系（或鏈接關(guān)系） 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu) ? 順序存儲(chǔ)結(jié)構(gòu) ? 用一塊無(wú)空隙的存儲(chǔ)區(qū)域存儲(chǔ)數(shù)據(jù)稱為順序存儲(chǔ) ? 借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系 ? 元素間的邏輯后繼關(guān)系用存儲(chǔ)單元的自然順序關(guān)系來(lái)表達(dá) ? 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ? 借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系 ? 兩個(gè)結(jié)點(diǎn)的邏輯后繼關(guān)系可以用指針的指向來(lái)表達(dá) 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu) Lo Lo+m Lo+(i1)*m Lo+（ n1)*m 存儲(chǔ)地址 存儲(chǔ)內(nèi)容 Loc(元素 i)=Lo+（ i1)*m 順序存儲(chǔ) 元素 1 元素 2 元素 i 元素 n head ^ 數(shù)據(jù)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ) ? 抽象 的本質(zhì) ? 簡(jiǎn)化 ? 忽略非本質(zhì)的部分 ? 高級(jí)語(yǔ)言中的數(shù)據(jù)類型實(shí)現(xiàn)了數(shù)據(jù)和操作的抽象化，但對(duì) 數(shù)據(jù)關(guān)系和操作能力 的抽象不強(qiáng) ? 抽象數(shù)據(jù)類型 （ Abstra
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1