第2章數(shù)據(jù)結(jié)構(gòu)及應(yīng)用概念及順序表-文庫吧
2025-07-05 09:18 本頁面
【正文】 ? 結(jié)構(gòu)較復(fù)雜，需要額外存儲空間。 下一頁 上一頁 停止放映 [第 14/42頁 ] 索引存儲結(jié)構(gòu) 數(shù)據(jù)按索引形式存放。存儲時分為：數(shù)據(jù)項(xiàng)和索引號；通過索引表記錄邏輯號（記錄號）和物理號（存儲序號）之間的對應(yīng)關(guān)系。 數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu) : 12 21 35 2 45 5 10 4 3 2 7 1 6 5 數(shù)據(jù)域 索引順序號 特點(diǎn)： ? 非連續(xù)存放； ? 檢索速度快； ? 增、刪操作簡單。 序 號： 1 2 3 4 5 6 7 數(shù)據(jù)項(xiàng)： 索引號： 下一頁 上一頁 停止放映 [第 15/42頁 ] 散列存儲結(jié)構(gòu) ? 在數(shù)據(jù)元素與存儲位置之間建立一種存儲關(guān)系 F，根據(jù)這種關(guān)系 F，已知元素 E，就可以得到它的存儲地址，即D=F（ E）。 ? 哈希查找中的哈希表就是這樣一種存儲結(jié)構(gòu)。 特點(diǎn)： – 數(shù)據(jù)元素間無內(nèi)在聯(lián)系； – 存儲形式不定。 下一頁 上一頁 停止放映 [第 16/42頁 ] 數(shù)據(jù)運(yùn)算 ? 數(shù)據(jù)運(yùn)算是指對存放在物理結(jié)構(gòu)上的數(shù)據(jù) ,按定義的邏輯結(jié)構(gòu)進(jìn)行的各種操作。 常見操作有： – 輸入、檢索、插入、刪除、修改、排序等。 下一頁 上一頁 停止放映 [第 17/42頁 ] 數(shù)據(jù)結(jié)構(gòu)分類 線性表 堆棧 隊(duì)列 串 數(shù)組 樹 二叉樹 圖 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu) DS 下一頁 上一頁 停止放映 [第 18/42頁 ] 數(shù)據(jù)結(jié)構(gòu)基本類型 ? 線性結(jié)構(gòu) —— 通迅錄、成績單、花名冊 ? 樹形結(jié)構(gòu) —— 電子字典、家譜、目錄 ? 圖狀結(jié)構(gòu) —— 交通線路、通信網(wǎng)絡(luò) 下一頁 上一頁 停止放映 [第 19/42頁 ] 算法（ algorithm） 通俗地講 ， 算法就是一種解題的方法 。 更嚴(yán)格地說 ，算法是由若干條指令組成的有窮序列 ， 它必須滿足下述條件 （ 也稱為算法的五大特性 ） ： ⑴ 輸入 ： 具有 0個或多個輸入的外界量 （ 算法開始前的初始量 ） ⑵ 輸出 ： 至少有一個輸出 ， 是算法執(zhí)行完后的結(jié)果 。 ⑶ 有窮性 ： 每條指令的執(zhí)行次數(shù)必須是有限的 。 ⑷ 確定性 ： 每條指令的含義都必須明確 ， 無二義性 。 ⑸ 可行性 ： 每條指令的執(zhí)行時間都是有限的 。 下一頁 上一頁 停止放映 [第 20/42頁 ] 1． 時間復(fù)雜度 一個算法花費(fèi)的時間與算法中語句的執(zhí)行次數(shù)成正比，哪個算法中語句執(zhí)行次數(shù)多，它花費(fèi)時間就多。 數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素個數(shù) n稱為問題的規(guī)模，當(dāng) n不斷變化時，語句的執(zhí)行次數(shù)也會變化。一個算法中的時間復(fù)雜度一般用語句執(zhí)行次數(shù)的數(shù)量級來衡量。 例如： for(i=1。 i=n。 i++) for(j =1。 j=i。 j++) d[i][j]=data[i][j]+1。 算法分析 O(n2) 下一頁 上一頁 停止放映 [第 21/42頁 ] 算法的評價 算法評價的標(biāo)準(zhǔn)： 時間復(fù)雜度 指在計算機(jī)上運(yùn)行該算法所花費(fèi)的時間。用“ O（數(shù)量級） ” 來表示，稱為 “ 階 ” 。常見的時間復(fù)雜度有： O（ 1） O（ logn） O（ n ） O（ n2 ） 常數(shù)階 對數(shù)階 線性階 平方階 空間復(fù)雜度 指算法在計算機(jī)上運(yùn)行所占用的存儲空間。度量同時間復(fù)雜度。 下一頁 上一頁 停止放映 [第 22/42頁 ] 時間復(fù)雜度舉例 （ a） X： =X+1 ； （ b） FOR I： =1 TO n DO X： = X+1； （ c） FOR I： = 1 TO n DO FOR J： = 1 TO n DO X： = X+1； O（ 1 ） O（ n ） O（ n2 ） 下一頁 上一頁 停止放映 [第 23/42頁 ] 空間復(fù)雜度 與時間復(fù)雜度類似，空間復(fù)雜度是指算法在計算機(jī)內(nèi)執(zhí)行時所占用的內(nèi)存開銷規(guī)模。但我們一般所討論的是除正常占用內(nèi)存開銷外的輔助存儲單元規(guī)模。討論方法與時間復(fù)雜度類似，不再贅述。 下一頁 上一頁 停止放映 [第 24/42頁 ] 線性數(shù)據(jù)結(jié)構(gòu) 線性表是由有限個同類型的數(shù)據(jù)元素組成的有序序列，一般記作 （ a1,a2,… ,an） 。除了 a1和 an之外，任意元素 ai都有一個直接前趨 ai1和一個直接后繼 ai+1。 a1無前趨， an無后繼。
試題試卷相關(guān)推薦
鄂ICP備17016276號-1