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