計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第1章 概述課件

第1章概述12/10/20221Longman數(shù)據(jù)結(jié)構(gòu)概述主要參考書嚴(yán)蔚敏、吳偉民《數(shù)據(jù)結(jié)構(gòu)C語言版》清華大學(xué)出版社譚浩強(qiáng)《C程序設(shè)計(jì)》清華大學(xué)出版社12/10/20222Longman主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)的概念12/10/20223Longman計(jì)算機(jī)的用途早期：主要用于數(shù)值計(jì)算。數(shù)值計(jì)算解決問題的一般步驟：數(shù)學(xué)模型→選擇計(jì)算機(jī)語言→編出程序→測(cè)試→最終解答。數(shù)值計(jì)算的關(guān)鍵是：如何得出數(shù)學(xué)模型(方程)？程序設(shè)計(jì)人員比較關(guān)注程序設(shè)計(jì)的技巧。12/10/20225Longman計(jì)算機(jī)的用途后來：處理逐漸擴(kuò)大到非數(shù)值計(jì)算領(lǐng)域(能處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù))。非數(shù)值計(jì)算問題：數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程加以描述。例1.1電話號(hào)碼查詢問題：（1）按順序存儲(chǔ)方式：須遍歷表（2）按姓氏索引方式：索引要寫出好的查找算法，取決于這張表的結(jié)構(gòu)及存儲(chǔ)方式。電話號(hào)碼表的結(jié)構(gòu)和存儲(chǔ)方式?jīng)Q定了查找（算法）的效率。12/10/20226Longman非數(shù)值計(jì)算問題例1.2

田徑賽的時(shí)間安排問題(無向圖的著色問題)：設(shè)有六個(gè)比賽項(xiàng)目，規(guī)定每個(gè)選手至多可參加三個(gè)項(xiàng)目，有五人報(bào)名參加比賽（如下表所示）設(shè)計(jì)比賽日程表，使得在盡可能短的時(shí)間內(nèi)完成比賽。姓名項(xiàng)目1項(xiàng)目2項(xiàng)目3趙一跳高跳遠(yuǎn)100米錢二標(biāo)槍鉛球/孫三標(biāo)槍100米200米李四鉛球200米跳高陳五跳遠(yuǎn)200米/12/10/20227Longman田徑賽的時(shí)間安排(1)設(shè)用如下六個(gè)不同的代號(hào)代表不同的項(xiàng)目：跳高跳遠(yuǎn)標(biāo)槍鉛球100米200米AB CDE F(2)用頂點(diǎn)代表比賽項(xiàng)目不能同時(shí)進(jìn)行比賽的項(xiàng)目之間連上一條邊。(3)某選手比賽項(xiàng)目必定有邊相連(不能同時(shí)比賽)。12/10/20228Longman田徑賽的時(shí)間安排根據(jù)給定的數(shù)據(jù)(如課本表1.2所示)以及數(shù)據(jù)之間的約束關(guān)系(也可以說是數(shù)據(jù)之間的邏輯關(guān)系)，我們建立了連線圖(建立數(shù)據(jù)模型)，用它來描述數(shù)據(jù)之間已經(jīng)定義的各種關(guān)系。這是一種非線性的圖形結(jié)構(gòu)。這里的原始數(shù)據(jù)以及最終結(jié)果都不是數(shù)值數(shù)據(jù)，而是一些廣義數(shù)據(jù)及其之間的關(guān)系。他們反映了數(shù)據(jù)結(jié)構(gòu)豐富的內(nèi)涵。

12/10/202210Longman基本概念和術(shù)語數(shù)據(jù)(data)信息的符號(hào)表示對(duì)計(jì)算機(jī)而言就是處理的對(duì)象數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)數(shù)據(jù)元素(dataelement)是數(shù)據(jù)結(jié)構(gòu)中的基本單位，是數(shù)據(jù)集合中的個(gè)體也可叫做元素、結(jié)點(diǎn)、頂點(diǎn)、記錄由若干數(shù)據(jù)項(xiàng)(dataitem)組成12/10/202212Longman基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)定義1：數(shù)據(jù)元素之間的相互關(guān)系稱為結(jié)構(gòu)，帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合稱為數(shù)據(jù)結(jié)構(gòu)。定義2：按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)(或稱帶結(jié)構(gòu)的數(shù)據(jù)元素的集合)應(yīng)用計(jì)算機(jī)語言并按一定的存儲(chǔ)表示方式把它們存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，并在其上定義了一個(gè)運(yùn)算的集合。12/10/202214Longman數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面的含義：邏輯結(jié)構(gòu)(LogicStructure)

數(shù)據(jù)元素間抽象化的相互關(guān)系（簡(jiǎn)稱為數(shù)據(jù)結(jié)構(gòu)）。與數(shù)據(jù)的存儲(chǔ)無關(guān)，獨(dú)立于計(jì)算機(jī)，它是從具體問題抽象出來的數(shù)學(xué)模型；數(shù)據(jù)的約束條件，等等。存儲(chǔ)結(jié)構(gòu)(StorageStructure)也稱為物理結(jié)構(gòu)(PhysicalStructure)數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式。是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)，它依賴于計(jì)算機(jī)語言。運(yùn)算(Operation)定義在數(shù)據(jù)集合上的一組運(yùn)算12/10/202215Longman邏輯結(jié)構(gòu)

邏輯結(jié)構(gòu)指數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系(主要指先后、層次等關(guān)系，而非數(shù)值大小關(guān)系)，是從具體問題抽象出來的數(shù)學(xué)模型邏輯結(jié)構(gòu)獨(dú)立于計(jì)算機(jī)，獨(dú)立于存儲(chǔ)器元素之間關(guān)系的分類集合結(jié)構(gòu)——元素之間無關(guān)系

線性結(jié)構(gòu)——元素之間一對(duì)一關(guān)系樹型結(jié)構(gòu)——元素之間一對(duì)多關(guān)系圖形結(jié)構(gòu)——元素之間多對(duì)多關(guān)系12/10/202216Longman線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)的邏輯特征是：有且僅有一個(gè)開始數(shù)據(jù)元素和一個(gè)終點(diǎn)數(shù)據(jù)元素，并且所有的數(shù)據(jù)元素都最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。非線性結(jié)構(gòu)的邏輯特征是：該結(jié)構(gòu)中一個(gè)數(shù)據(jù)元素的直接前驅(qū)或直接后繼不止一個(gè)。若任何一個(gè)數(shù)據(jù)元素的直接前驅(qū)和直接后繼的個(gè)數(shù)不作任何限制，該結(jié)構(gòu)被稱為圖(Graph)結(jié)構(gòu)；若該結(jié)構(gòu)數(shù)據(jù)元素的直接前驅(qū)和直接后繼作如下的限制：有且僅有一個(gè)稱為根的元素?zé)o直接前驅(qū)，其它元素有且僅有一個(gè)直接前驅(qū)，所有數(shù)據(jù)元素(除根元素)都存在一條從根元素到該元素的路徑，該結(jié)構(gòu)被稱為樹(Tree)結(jié)構(gòu)。

12/10/202217Longman邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)線性表樹形結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)集合

一般線性表(如線性表)

特殊線性表(如棧和隊(duì)列)

線性表推廣(如串和數(shù)組)一般樹二叉樹無向圖有向圖12/10/202218Longman存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)元素的集合和關(guān)系的集合的另外一種表示形式。用存儲(chǔ)單元地址的連續(xù)或存儲(chǔ)單元存放的地址表示出數(shù)據(jù)元素的邏輯關(guān)系。存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素自身值——存儲(chǔ)單元的內(nèi)容結(jié)點(diǎn)與其它結(jié)點(diǎn)關(guān)系——地址的順序或指向關(guān)系12/10/202220Longman存儲(chǔ)結(jié)構(gòu)四種基本存儲(chǔ)方式：(1)順序存儲(chǔ)(Sequential)；(2)鏈?zhǔn)酱鎯?chǔ)(Linked)；(3)索引存儲(chǔ)(Index)；(4)散列存儲(chǔ)(Hash)12/10/202221Longman鏈?zhǔn)酱鎯?chǔ)數(shù)據(jù)元素的值——存放在存儲(chǔ)單元中數(shù)據(jù)元素之間的關(guān)系——通過指定的地址指向來描述(指針，鏈)存儲(chǔ)單元的位置是隨機(jī)的，但在存放元素值的同時(shí)必須存放相鄰元素的地址通常借助于程序設(shè)計(jì)語言中的指針類型來實(shí)現(xiàn)12/10/202223Longman索引存儲(chǔ)方法和散列存儲(chǔ)

索引存儲(chǔ)通常是在存儲(chǔ)元素信息的同時(shí)，還建立附加的索引表，索引表中的每一項(xiàng)稱為索引項(xiàng)。通過索引項(xiàng)中的關(guān)鍵字能唯一標(biāo)識(shí)該數(shù)據(jù)元素。散列存儲(chǔ)也叫作哈希(Hash)存儲(chǔ)，其基本思想是根據(jù)元素的關(guān)鍵字直接計(jì)算出該元素的存儲(chǔ)地址。12/10/202224Longman描述算法的偽碼——類C語言單行注釋：//文字序列

申請(qǐng)內(nèi)存單元函數(shù)malloc(n)//申請(qǐng)n個(gè)內(nèi)存單元，并返回起始地址。當(dāng)為自定義的數(shù)據(jù)元素類型申請(qǐng)內(nèi)存單元時(shí)，我們可能并不清楚一個(gè)元素占有多大的內(nèi)存空間，此時(shí)可以通過si