《大學(xué)計(jì)算機(jī)基礎(chǔ)》課件第4章

4.1數(shù)據(jù)結(jié)構(gòu)4.2文件結(jié)構(gòu)4.3數(shù)據(jù)庫(kù)

4.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念

1．?dāng)?shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

2．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)

3．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

4．?dāng)?shù)據(jù)的運(yùn)算

5．線性結(jié)構(gòu)與非線性結(jié)構(gòu)

4.1數(shù)據(jù)結(jié)構(gòu)

4.1.2線性表

1．線性表的定義和邏輯特征

2．線性表的順序存儲(chǔ)結(jié)構(gòu)

4.1.3棧

1．棧的定義

如圖4-1所示，棧中有元素a1，a2，…，an，a1稱為棧底元素。新元素進(jìn)棧要置于an之上，刪除或出棧必須先對(duì)an進(jìn)行操作。圖4-1棧結(jié)構(gòu)2．棧的順序存儲(chǔ)方式

3．棧的基本運(yùn)算

4.1.4隊(duì)列

1．隊(duì)列的定義

隊(duì)列(Queue)是允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線性表，如圖4-2所示。

2．循環(huán)隊(duì)列

為了克服“假溢出”現(xiàn)象采用循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供循環(huán)隊(duì)列使用，如圖4-3所示。

3．循環(huán)隊(duì)列的基本運(yùn)算

圖4-2隊(duì)列的示意圖圖4-3循環(huán)隊(duì)列存儲(chǔ)空間示意圖4.1.5線性鏈表

1．結(jié)點(diǎn)結(jié)構(gòu)

在鏈?zhǔn)酱鎯?chǔ)方式中，每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域，用于指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針，如圖4-4所示。圖4-4結(jié)點(diǎn)的結(jié)構(gòu)

2．單鏈表

用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的線性表稱作鏈表。圖4-5所示的就是一個(gè)單鏈表。

3．雙向鏈表

在單鏈表中，每一個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由這個(gè)指針只能找到其后繼結(jié)點(diǎn)，而不能找到其前趨結(jié)點(diǎn)。因此，在某些應(yīng)用中，對(duì)于線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱為左指針(llink)，指向其前趨結(jié)點(diǎn)；另一個(gè)稱為右指針(rlink)，指向其后繼結(jié)點(diǎn)，這種鏈表稱為雙向鏈表，其結(jié)點(diǎn)結(jié)構(gòu)如圖4-6所示，邏輯結(jié)構(gòu)如圖4-7所示。圖4-5單鏈表示意圖圖4-6雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)圖4-7雙向鏈表示意圖

4．循環(huán)鏈表

5．鏈?zhǔn)綏?/p>

6．鏈?zhǔn)疥?duì)列

7．線性鏈表主要基本運(yùn)算

線性鏈表的插入過程是先向系統(tǒng)申請(qǐng)一個(gè)新結(jié)點(diǎn)(由指針q指向)，并賦值，然后利用查找算法找到待插入位置的前一結(jié)點(diǎn)的指針p并修改兩個(gè)指針即可：先將結(jié)點(diǎn)q的指針域內(nèi)容改為結(jié)點(diǎn)p的原后繼結(jié)點(diǎn)，再將結(jié)點(diǎn)p的指針域內(nèi)容改為指向結(jié)點(diǎn)q，線性鏈表的插入如圖4-8所示。

圖4-8線性鏈表的插入

(3)刪除結(jié)點(diǎn)。先判斷線性鏈表是否為空，然后對(duì)非空表利用查找算法找到待刪除位置的前一結(jié)點(diǎn)的指針p，用另一指針q暫時(shí)保存結(jié)點(diǎn)p的后繼結(jié)點(diǎn)(即待刪除結(jié)點(diǎn))，再把p結(jié)點(diǎn)的后繼直接鏈接在q結(jié)點(diǎn)的后繼結(jié)點(diǎn)上，最后釋放q結(jié)點(diǎn)所分配的內(nèi)存空間，如圖4-9所示。

8．循環(huán)鏈表及基本運(yùn)算

圖4-9線性鏈表的刪除4.1.6樹與二叉樹

樹形結(jié)構(gòu)是一種簡(jiǎn)單的非線性結(jié)構(gòu)，在樹這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性，它體現(xiàn)了數(shù)據(jù)元素之間的“一對(duì)多”的聯(lián)系。樹和二叉樹是最常用的樹形結(jié)構(gòu)。

1．樹的基本概念

在圖4-10中，結(jié)點(diǎn)A為根結(jié)點(diǎn)。圖4-10樹的表示

2．二叉樹的基本概念

因此，二叉樹具有五種基本形態(tài)，分別是空二叉樹，只有一個(gè)根結(jié)點(diǎn)的二叉樹，只有左子樹的二叉樹，只有右子樹的二叉樹，左、右子樹都有的二叉樹，如圖4-11所示。圖4-11二叉樹的五種形態(tài)(a)空二叉樹；(b)只有一個(gè)根結(jié)點(diǎn)的二叉樹；、(c)只有左子樹的二叉樹；(d)只有右子樹的二叉樹；(e)左、右子樹都有的二叉樹

3．二叉樹的性質(zhì)

4．二叉樹的存儲(chǔ)

二叉樹的存儲(chǔ)常采用鏈接方式，它是指用鏈表來表示的一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，除了數(shù)據(jù)域外，還有兩個(gè)指針域，分別用來給出該結(jié)點(diǎn)左子樹和右子樹所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址。二叉樹結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)如圖4-12所示。圖4-12二叉樹結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)

5．二叉樹的遍歷

遍歷是樹形結(jié)構(gòu)的一種重要運(yùn)算。遍歷一個(gè)樹形結(jié)構(gòu)就是按一定的次序訪問該結(jié)構(gòu)中的所有結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)恰好被訪問一次?？梢园炊喾N不同的次序遍歷樹形結(jié)構(gòu)，在這里僅介紹三種重要的二叉樹遍歷的方法。

圖4-13樹的結(jié)構(gòu)4.2.1操作系統(tǒng)的文件管理功能

1．計(jì)算機(jī)文件的基本概念

2．文件管理

3．文件的分類

4．文件的結(jié)構(gòu)

4.2文件結(jié)構(gòu)4.2.2順序文件

1．連續(xù)結(jié)構(gòu)順序文件

圖4-14給出了連續(xù)結(jié)構(gòu)文件的圖形說明。圖中，一個(gè)邏輯塊號(hào)為0、1、2、3的文件依次存放在物理塊15、16、17、18中。圖4-14連續(xù)結(jié)構(gòu)文件的示意圖

2．鏈結(jié)構(gòu)順序文件

圖4-15給出了鏈結(jié)構(gòu)文件的物理結(jié)構(gòu)。使用鏈結(jié)構(gòu)時(shí)，不必在文件說明信息中指明文件的長(zhǎng)度，只要指明該文件的第一個(gè)塊號(hào)就可以按鏈指針檢索整個(gè)文件。鏈結(jié)構(gòu)的另一個(gè)特點(diǎn)是文件長(zhǎng)度可以動(dòng)態(tài)地增長(zhǎng)，只要調(diào)整鏈指針就可在任何一個(gè)信息塊之間插入或刪除一個(gè)信息塊。圖4-15鏈結(jié)構(gòu)文件的示意圖4.2.3文本文件

文本文件是一種典型的順序文件，其文件的邏輯結(jié)構(gòu)又屬于流式文件。

4.2.4索引文件

索引結(jié)構(gòu)如圖4-16所示。圖4-16索引結(jié)構(gòu)文件的示意圖通常有的文件很大，文件索引表也就較大。如果索引表的大小超過了一個(gè)物理塊，可以采用間接索引(多重索引)，也就是在索引表所指的物理塊中存放的不是文件信息，而是裝有這些信息的物理塊地址。這樣，如果一個(gè)物理塊可裝下n個(gè)物理塊地址，則經(jīng)過一級(jí)間接索引，可尋址的文件長(zhǎng)度將變?yōu)閚×n塊。如果文件長(zhǎng)度還大于n×n塊，還可以進(jìn)行類似的擴(kuò)充，即二級(jí)間接索引，其原理如圖4-17所示。圖4-17文件的多級(jí)索引結(jié)構(gòu)4.2.5哈希文件

在日常生活和工作中，經(jīng)常會(huì)遇到查找操作，如在列車時(shí)刻表中查找某次列車的開車時(shí)間、在學(xué)生成績(jī)表中查找某位學(xué)生的成績(jī)等。4.3.1數(shù)據(jù)庫(kù)技術(shù)的發(fā)展

計(jì)算機(jī)對(duì)數(shù)據(jù)的管理是指對(duì)數(shù)據(jù)的組織、分類、編碼、存儲(chǔ)、檢索和維護(hù)提供操作手段。

1．人工管理階段

2．文件系統(tǒng)階段

3．?dāng)?shù)據(jù)庫(kù)系統(tǒng)階段

4.3數(shù)據(jù)庫(kù)4.3.2數(shù)據(jù)庫(kù)的基本概念

1．?dāng)?shù)據(jù)庫(kù)系統(tǒng)的基本概念

1)數(shù)據(jù)庫(kù)

2)數(shù)據(jù)庫(kù)管理系統(tǒng)

3)數(shù)據(jù)庫(kù)管理員

4)數(shù)據(jù)庫(kù)系統(tǒng)

5)數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)

圖4-18所示為數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)的組成示意圖。圖4-18數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)的組成示意圖

2．?dāng)?shù)據(jù)庫(kù)管理系統(tǒng)的基本功能

3．?dāng)?shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn)

4.3.3數(shù)據(jù)模型

1．什么是數(shù)據(jù)模型

2．E-R模型

3．關(guān)系數(shù)據(jù)模型

表4-1給出的學(xué)生考試成績(jī)表便是一個(gè)關(guān)系模型。在這張表中，每一列的命名都與學(xué)生的信息有關(guān)系，每一列是同一屬性，每一行稱為一條記錄。

表4-1學(xué)?生?信?息?表4.3.4數(shù)據(jù)庫(kù)的安全

數(shù)據(jù)庫(kù)的安全是數(shù)據(jù)庫(kù)系統(tǒng)的生命。

1)用戶身份認(rèn)證

2)存取控制

3)數(shù)據(jù)加密

4)審計(jì)追蹤與攻擊檢測(cè)4.3.5數(shù)據(jù)庫(kù)設(shè)計(jì)

數(shù)據(jù)庫(kù)設(shè)計(jì)方法中比較著名的有新奧爾良(NewOrleans)方法，它將數(shù)據(jù)庫(kù)設(shè)計(jì)過程分為4個(gè)階段：需求分析、概念結(jié)構(gòu)設(shè)計(jì)、邏輯結(jié)構(gòu)設(shè)計(jì)和物理結(jié)構(gòu)設(shè)計(jì)，如圖4-1