數(shù)據(jù)結(jié)構(gòu)第二版-在線瀏覽
2024-08-29 17:54本頁(yè)面
【正文】 各種運(yùn)算； ? 設(shè)計(jì)出相應(yīng)的算法； ? 分析算法的效率。 數(shù)據(jù)結(jié)構(gòu)與問(wèn)題求解 1. 在計(jì)算機(jī)中建立一個(gè)與實(shí)際問(wèn)題有比較密切對(duì)應(yīng)關(guān)系的 模型 ； 2. 計(jì)算機(jī)內(nèi)部的 數(shù)據(jù) 表示了需要被處理的實(shí)際對(duì)象，包括其內(nèi)在的性質(zhì)和關(guān)系； 3. 處理這些數(shù)據(jù)的 程序 則模擬對(duì)象領(lǐng)域中的實(shí)際過(guò)程； 4. 將計(jì)算機(jī)程序的運(yùn)行 結(jié)果 在實(shí)際領(lǐng)域中給予解釋，便得到實(shí)際問(wèn)題的解。 在書(shū)目自動(dòng)檢索系統(tǒng)中，有一張按登錄號(hào)順序排列的書(shū)目文件和 三張分別按書(shū)名、作者名和分類號(hào)順序排列的索引表。 001 高等數(shù)學(xué) 樊映川 S 01 ...002 理論力部 羅遠(yuǎn)祥 L 0 1 ...003 高等數(shù)學(xué) 華羅庚 S 01 ...004 線性代數(shù) 欒汝書(shū) S 02 ...高等數(shù)學(xué) 001 ， 003 ， ...理論力學(xué) 002 ， ...線性代數(shù) 004 ， ...樊映川 001 ， ...華羅庚 003 ， ...欒汝書(shū) 004 ， ...L 002 ,...S 00 1,0 03 ,...（書(shū)目文件） （書(shū)名索引） （作者索引） （分類索引） 例 酒店管理系統(tǒng)中的客房分配問(wèn)題。 對(duì)這一問(wèn)題可用數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列來(lái)解決；將酒店所有空閑 客房排成一個(gè)隊(duì)列，有客人入住則從隊(duì)頭分配客房，客人結(jié)帳 離店則將空出的客房插入隊(duì)尾。 201 302 107 ... 405 606 721隊(duì)頭 隊(duì)尾 出租隊(duì)頭客房 客人離店，空出客房插入隊(duì)尾 注：例 例 2都屬于線性數(shù)據(jù)結(jié)構(gòu) 例 計(jì)算機(jī)和人對(duì)弈問(wèn)題。對(duì)弈的過(guò)程是在一定規(guī)則下隨機(jī)進(jìn)行， 計(jì)算機(jī)操作對(duì)象是對(duì)弈過(guò)程中可能出現(xiàn)的棋盤(pán)狀態(tài) 稱為格局。 O╳╳ OO╳ ╳╳ O╳ O╳╳ O╳ O╳╳ OO╳ ╳╳ OO╳╳ O ╳目前我們所接觸的象棋軟件、圍棋軟件的實(shí)現(xiàn)原理和井字棋是 一樣的。 我們用圖來(lái)表示這類問(wèn)題。 8 1 4 2 9 6 7 5 3 (A、 費(fèi)用核算） 1 4 2 9 3 5 6 7 8 （ B、 鋪設(shè)方案） 問(wèn)題求解例子 五叉路口交通管理系統(tǒng)設(shè)計(jì) B A C D E 對(duì)車輛可能行駛方向進(jìn)行分組，要求任一組中各個(gè)方向行駛的車輛可以同時(shí)安全行駛。 有 13個(gè)可能通行的方向： AB， AC， AD， BA， BC， BD， DA， DB， DC， EA， EB， EC， ED。要解決的問(wèn)題已借助圖的 模型 清楚而嚴(yán)格地表達(dá)出來(lái)。 求解方法（求著色問(wèn)題的近似解） 1. 選出未著色的結(jié)點(diǎn)，并用該新顏色上色； 2. 尋找仍未著色的結(jié)點(diǎn)，如果某結(jié)點(diǎn)與新顏色結(jié)點(diǎn)沒(méi)有邊相連，則將該結(jié)點(diǎn)用該顏色上色。又設(shè)每個(gè) 人都會(huì)劃船。 解： 模型構(gòu)造： 用一個(gè)三元組（ x,y,t)表示渡河過(guò)程中的某個(gè) 狀態(tài)。合法狀態(tài)所對(duì)應(yīng)的三元組（ x,y,t)必須滿 足： x=0 或 x=n 或 x=y. 于是，渡河方案的求解就轉(zhuǎn)換成一個(gè)圖的搜索問(wèn)題 找出從起始頂點(diǎn)（ n,n,1)到目的頂點(diǎn) (0,0,0)的一 條包含邊數(shù)最少的通路。 例如，當(dāng) n=2,c=2時(shí)，各合法狀態(tài)及其間的變 換如圖： （ 2， 2， 1） （ 0， 2， 0） （ 2， 0， 0） （ 1， 1， 0） （ 2， 1， 0） （ 2， 1， 1） （ 0， 1， 0） （ 0， 2， 1） （ 1， 1， 1） （ 0， 0， 0） 基本術(shù)語(yǔ) ? 數(shù)據(jù) （ Data)： 所有能被 計(jì)算機(jī)處理 的 符號(hào) 的集合。 設(shè)給定數(shù)據(jù)集合為： D={d1， d2，．．．， dn} 則 di屬于 D， 并稱 di為 數(shù)據(jù)元素。 基本術(shù)語(yǔ) ? 數(shù)據(jù)對(duì)象 （ Data Object） : 具有相同特性的數(shù)據(jù)元素的集合。 ? 集合 ? 線性結(jié)構(gòu) ? 樹(shù)型結(jié)構(gòu) ? 圖型結(jié)構(gòu) 基本概念和術(shù)語(yǔ) 基本術(shù)語(yǔ) ? 數(shù)據(jù)結(jié)構(gòu) （ Data Structure）： 是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。 用集合的形式描述，數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組： DS=(D， R) 其中： D是數(shù)據(jù)元素的集合， R是 D上 關(guān)系的集合。 基本概念和術(shù)語(yǔ) 例７、假設(shè)學(xué)校的每個(gè)課題小組由一位教師，一至三名研究生 及一至六名本科生組成，小組
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1