第2章數(shù)據(jù)結(jié)構(gòu)及應(yīng)用概念及順序表-展示頁
2024-08-04 09:18本頁面
【正文】 1 ） O（ n ） O（ n2 ） 下一頁 上一頁 停止放映 [第 23/42頁 ] 空間復(fù)雜度 與時(shí)間復(fù)雜度類似，空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所占用的內(nèi)存開銷規(guī)模。常見的時(shí)間復(fù)雜度有： O（ 1） O（ logn） O（ n ） O（ n2 ） 常數(shù)階 對(duì)數(shù)階 線性階 平方階 空間復(fù)雜度 指算法在計(jì)算機(jī)上運(yùn)行所占用的存儲(chǔ)空間。 算法分析 O(n2) 下一頁 上一頁 停止放映 [第 21/42頁 ] 算法的評(píng)價(jià) 算法評(píng)價(jià)的標(biāo)準(zhǔn)： 時(shí)間復(fù)雜度 指在計(jì)算機(jī)上運(yùn)行該算法所花費(fèi)的時(shí)間。 j=i。 i=n。一個(gè)算法中的時(shí)間復(fù)雜度一般用語句執(zhí)行次數(shù)的數(shù)量級(jí)來衡量。 下一頁 上一頁 停止放映 [第 20/42頁 ] 1． 時(shí)間復(fù)雜度 一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比，哪個(gè)算法中語句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。 ⑷ 確定性 ： 每條指令的含義都必須明確 ， 無二義性 。 更嚴(yán)格地說 ，算法是由若干條指令組成的有窮序列 ， 它必須滿足下述條件 （ 也稱為算法的五大特性 ） ： ⑴ 輸入 ： 具有 0個(gè)或多個(gè)輸入的外界量 （ 算法開始前的初始量 ） ⑵ 輸出 ： 至少有一個(gè)輸出 ， 是算法執(zhí)行完后的結(jié)果 。 常見操作有： – 輸入、檢索、插入、刪除、修改、排序等。 特點(diǎn)： – 數(shù)據(jù)元素間無內(nèi)在聯(lián)系； – 存儲(chǔ)形式不定。 序 號(hào)： 1 2 3 4 5 6 7 數(shù)據(jù)項(xiàng)： 索引號(hào)： 下一頁 上一頁 停止放映 [第 15/42頁 ] 散列存儲(chǔ)結(jié)構(gòu) ? 在數(shù)據(jù)元素與存儲(chǔ)位置之間建立一種存儲(chǔ)關(guān)系 F，根據(jù)這種關(guān)系 F，已知元素 E，就可以得到它的存儲(chǔ)地址，即D=F（ E）。存儲(chǔ)時(shí)分為：數(shù)據(jù)項(xiàng)和索引號(hào)；通過索引表記錄邏輯號(hào)（記錄號(hào)）和物理號(hào)（存儲(chǔ)序號(hào)）之間的對(duì)應(yīng)關(guān)系。 ? 插入、刪除操作簡單，只要修改指針即可； ? 結(jié)構(gòu)較復(fù)雜，需要額外存儲(chǔ)空間。 下一頁 上一頁 停止放映 [第 13/42頁 ] 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 以鏈表形式將數(shù)據(jù)元素存放于任意存儲(chǔ)單元中，可連續(xù)存放，也可以不連續(xù)存放，以指針實(shí)現(xiàn)鏈表間的聯(lián)系。 ? 結(jié)構(gòu)簡單，易實(shí)現(xiàn)。數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu) : d1 d2 …… dn 數(shù)據(jù)域 特點(diǎn) : ? 連續(xù)存放 。 ?任何一個(gè) 算法的設(shè)計(jì) 取決于選定的邏輯結(jié)構(gòu)；而算法的最終實(shí)現(xiàn) 依賴于采用的存儲(chǔ)結(jié)構(gòu)。 數(shù)據(jù)庫中的數(shù)據(jù)存放在計(jì)算機(jī)中的物理位置 下一頁 上一頁 停止放映 [第 10/42頁 ] 邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的關(guān)系 ?數(shù)據(jù)的 邏輯結(jié)構(gòu) 是從邏輯關(guān)系（某種順序）上觀察數(shù)據(jù)，它是獨(dú)立于計(jì)算機(jī)的；可以在理論上、形式上進(jìn)行研究、推理、運(yùn)算等各種操作。 與數(shù)據(jù)在計(jì)算機(jī)中的存放的 物理位置無關(guān) 下一頁 上一頁 停止放映 [第 8/42頁 ] 舉例 ? 課題組由 1名教師、 1~3名研究生、 1~6名本科生組成；成員關(guān)系是：教師指導(dǎo)研究生、研究生指導(dǎo) 1~2名本科生。 下一頁 上一頁 停止放映 [第 7/42頁 ] 數(shù)據(jù)的邏輯結(jié)構(gòu) 它是描述數(shù)據(jù)間的順序（邏輯）關(guān)系，只是抽象地反映數(shù)據(jù)元素的結(jié)構(gòu)，而不管它們在計(jì)算機(jī)中如何存放。 但它還可以分割成若干個(gè)具有不同屬性的項(xiàng) （ 字段 ） ， 故不是組成數(shù)據(jù)的最小單位 下一頁 上一頁 停止放映 [第 6/42頁 ] 數(shù)據(jù)結(jié)構(gòu) （ data structure） 是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素所組成的集合 。 2．?dāng)?shù)據(jù)元素（ data element） 數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位 。下一頁 上一頁 停止放映 第 2章數(shù)據(jù)結(jié)構(gòu)及應(yīng)用 概念及順序表 西安交通大學(xué)計(jì)教中心 下一頁 上一頁 停止放映 [第 2/42頁 ] 思考問題 數(shù)據(jù)結(jié)構(gòu)要研究什么問題？ 什么是線性數(shù)據(jù)結(jié)構(gòu)和線性表？ 如何描述線性表？ 線性表在計(jì)算機(jī)中如何存放？有幾種存儲(chǔ)形式？它們的特點(diǎn)是什么？ 如何處理線性數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)？ …… 下一頁 上一頁 停止放映 [第 3/42頁 ] 數(shù)據(jù)結(jié)構(gòu)問題的由來 計(jì)算機(jī)求解問題的過程步驟： 調(diào)試程序 編制 程序 求解 結(jié)果 運(yùn)行 程序 結(jié)果輸出 用戶 需求 數(shù)據(jù)類型、格式、 邏輯結(jié)構(gòu) 數(shù)據(jù) 邏輯 運(yùn)算 數(shù)據(jù)的物理 操作 分析抽象 實(shí)際問題 模型求解 問題 模型 命令 編程 求解算法 下一頁 上一頁 停止放映 [第 4/42頁 ] 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)的專業(yè)技術(shù)基礎(chǔ)課。它研究的主要問題有： ?分析數(shù)據(jù)（計(jì)算機(jī)加工的對(duì)象）的特征 ?選擇適當(dāng)邏輯存儲(chǔ)結(jié)構(gòu)和物理存儲(chǔ)
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1