數(shù)據(jù)結(jié)構(gòu)課件緒論(編輯修改稿)
2024-08-28 15:06 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 抽象數(shù)據(jù)類型 —— ADT ? 定義：是指基于一個(gè)邏輯類型的數(shù)據(jù)模型以及定義在該模型上的一組操作。每一個(gè)操作由它的輸入和輸出定義。 ? 抽象的與具體的相對(duì)應(yīng) ? 示例： int a,b。 則 a和 b可以進(jìn)行 +、 、 *、 /的運(yùn)算 2和 6則是具體的 int數(shù)據(jù) 算法和算法分析 1. 算法 p13 定義：指一系列確定的而且是在有限步驟內(nèi) 能完成的操作。 算法的重要特性 P13 (1) 有窮性 ：能執(zhí)行結(jié)束 (2) 確定性 ：對(duì)于相同的輸入執(zhí)行相同的路徑 (3) 0至多個(gè)輸入 (4) 1至多個(gè)輸出 (5) 有效性 (可行性 ) （用于描述算法的操作都是 足夠基本的） ? 問(wèn)題：程序是不是算法？ ? 如操作系統(tǒng)，只要系統(tǒng)不遭破壞，它就永遠(yuǎn)不會(huì)停止，即使沒(méi)有作業(yè)要處理，仍處于一個(gè)等待循環(huán)中，等待新作業(yè)的進(jìn)入。因此操作系統(tǒng)程序不是一個(gè)算法。 2. 算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系 ? 計(jì)算機(jī)科學(xué)家沃斯（ ）提出的 : “算法 +數(shù)據(jù)結(jié)構(gòu) =程序 ” 揭示了程序設(shè)計(jì)的本質(zhì)：對(duì)實(shí)際問(wèn)題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，加上設(shè)計(jì)一個(gè)好的算法，而好的算法很大程度上取決于描述實(shí)際問(wèn)題的數(shù)據(jù)結(jié)構(gòu)。算法與數(shù)據(jù)結(jié)構(gòu)是互相依賴、互相聯(lián)系的。 ? 一個(gè)算法總是建立在一定數(shù)據(jù)結(jié)構(gòu)上的；反之，算法不確定，就無(wú)法決定如何構(gòu)造數(shù)據(jù)。 —— p6圖 2行 算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系舉例 例 1：編寫(xiě)程序查詢某城市某人的電話號(hào)碼 建立一張登記表，存放 2個(gè)數(shù)據(jù)項(xiàng)： 姓名 +Tel 好的算法取決于這張表的結(jié)構(gòu)及存儲(chǔ)方式： ?將表中結(jié)點(diǎn)按照姓名順序地存儲(chǔ)在計(jì)算機(jī)中，依次查找，可能遍歷整個(gè)表都找不到。 ?建立一張姓氏索引表：姓 +表中的起始地址 則不需查找其他姓氏，查找效率得到提高。 算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系舉例 例 2: 設(shè)計(jì)一個(gè)考試日程安排表，使在盡可能短的時(shí)間內(nèi)安排完考試，要求同一個(gè)學(xué)生選修的幾門(mén)課程不能安排在同一個(gè)時(shí)間內(nèi)。 姓名 選修 1 選修 2 選修 3 A B E C D C E
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1