PPT模板下載：第三章數(shù)據(jù)的組織與管理浙江大學(xué)城市學(xué)院計(jì)算機(jī)基礎(chǔ)教研組大學(xué)計(jì)算機(jī)應(yīng)用基礎(chǔ)目錄3.2數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)是如何組織的3.3文件：數(shù)據(jù)是如何保存的3.4數(shù)據(jù)庫(kù)：數(shù)據(jù)管理的利器3.1引言圖書館里書籍的組織書籍如何擺放查找速度快？書籍如何擺放空間利用高？對(duì)于解決非數(shù)值計(jì)算的問題首要考慮：相關(guān)的各種信息如何表示、組織和存儲(chǔ)？3.2數(shù)據(jù)結(jié)構(gòu):數(shù)據(jù)是如何組織的1.什么是數(shù)據(jù)結(jié)構(gòu)？2.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)3.數(shù)據(jù)的基本結(jié)構(gòu)有哪些？1.什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)：是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)操作對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)三要素：數(shù)據(jù)集：要處理的數(shù)據(jù)元素的集合數(shù)據(jù)元素(DataElement)：是數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)是對(duì)客觀事物某一方面特性的數(shù)據(jù)描述。關(guān)系：數(shù)據(jù)元素之間的相互關(guān)系操作：對(duì)數(shù)據(jù)施加的操作一個(gè)數(shù)據(jù)元素2.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的聯(lián)系，即邏輯關(guān)系,稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，可以看作是從具體問題抽象出來的數(shù)學(xué)模型。集合結(jié)構(gòu)線性結(jié)構(gòu)

樹形結(jié)構(gòu)

圖狀結(jié)構(gòu)2.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)2.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，實(shí)際上就是數(shù)據(jù)的存放方式，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。2.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)

鏈?zhǔn)酱鎯?chǔ)索引存儲(chǔ)散列存儲(chǔ)

圖：順序存儲(chǔ)結(jié)構(gòu)圖2.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

索引存儲(chǔ)3.數(shù)據(jù)的基本結(jié)構(gòu)有哪些？

線性表

特種線性表：棧與隊(duì)列樹形結(jié)構(gòu)

最基本的樹——二叉樹圖結(jié)構(gòu)什么是線性表？線性表是一個(gè)序列，元素之間是有順序的，而且每個(gè)元素都有且只有一個(gè)前趨和后繼，除了第一個(gè)元素只有后繼沒有前趨，最后一個(gè)元素只有前趨沒有后繼。線性表的順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)：①線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；②線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中順序與邏輯結(jié)構(gòu)順序相同。如第一個(gè)元素的存儲(chǔ)地址為adr（a1），每個(gè)元素占k個(gè)字節(jié)，則線性表中第i個(gè)元素ai在存儲(chǔ)空間中的地址為：adr(ai)=adr(a1)+(i-1)k線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：①線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)使用一組不連續(xù)的、任意的存儲(chǔ)單元來存放線性表的各個(gè)元素；②為了表示邏輯次序，每個(gè)元素除了保存本身的值之外，還需要保存后繼（或前趨）元素的地址信息，稱為指針.硬盤中一個(gè)文件的數(shù)據(jù)不一定存放在一個(gè)連續(xù)的硬盤空間中，會(huì)被拆分成多個(gè)數(shù)據(jù)塊，這些數(shù)據(jù)塊隨硬盤的空余位置而定，不一定是相鄰的，因此要用指針把它們串聯(lián)起來。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)應(yīng)用：【例3-2】?jī)蓚€(gè)一元多項(xiàng)式求和問題。(2X10+4X+1)+(3X5-4X+2)每個(gè)節(jié)點(diǎn)包括3個(gè)域：系數(shù)、指數(shù)和指針。特種線性表：棧1．棧棧（stack）是只能在尾端進(jìn)行插入和刪除操作的線性表。特點(diǎn)：“先進(jìn)后出”或“后進(jìn)先出”圖3.12進(jìn)棧示意圖圖3.13出棧示意圖零錢罐特種線性表：棧棧的應(yīng)用：“撤消”功能的實(shí)現(xiàn)。特種線性表：棧棧的應(yīng)用：進(jìn)制的轉(zhuǎn)換，例如(159)10=(237)8，其運(yùn)算過程如下:(159)10=(237)81598198280237余7余3余2toptop7top73top732特種線性表：棧與隊(duì)列2．隊(duì)列隊(duì)列本質(zhì)上是一個(gè)線性表，只是插入元素在一端進(jìn)行，而刪除元素在另一端進(jìn)行。

進(jìn)隊(duì)：在隊(duì)尾插入元素；出隊(duì)：在隊(duì)頭刪除元素；特種線性表：隊(duì)列隊(duì)列應(yīng)用舉例:①鍵盤輸入處理。②操作系統(tǒng)中的進(jìn)程調(diào)度。③文檔打印管理。④醫(yī)院中的門診掛號(hào)系統(tǒng)。⑤營(yíng)業(yè)服務(wù)廳排隊(duì)叫號(hào)系統(tǒng)。

樹型結(jié)構(gòu)樹形結(jié)構(gòu)：是因?yàn)樗雌饋硐褚豢玫箳斓臉?，處于最頂端的是樹根，最底端的是樹葉。根結(jié)點(diǎn)沒有前趨結(jié)點(diǎn)，葉結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)數(shù)可以是一個(gè)也可以是多個(gè)。樹結(jié)構(gòu)在現(xiàn)實(shí)生活中普遍存在。員工4員工5員工6最基本的樹—二叉樹每個(gè)結(jié)點(diǎn)最多含有兩個(gè)子樹的樹稱為二叉樹。二叉樹是有序樹,任意結(jié)點(diǎn)的左、右子樹不能顛倒。二叉樹具有存儲(chǔ)簡(jiǎn)單的優(yōu)點(diǎn)（順序存儲(chǔ)結(jié)構(gòu)）樹的應(yīng)用樹的應(yīng)用十分廣泛:首先，分層分類方法是科學(xué)研究的基本方法，對(duì)于一個(gè)較大的問題，人們習(xí)慣把它分成幾個(gè)子問題，子問題下又可分成更小的問題，從而形成樹，這樣就便于問題的解決。如系統(tǒng)功能菜單、文件目錄結(jié)構(gòu)等等。其次，利用樹可以設(shè)計(jì)快速檢索（查找）數(shù)據(jù)的算法?，F(xiàn)在的索引一般都要用到各種樹，例如，數(shù)據(jù)庫(kù)的索引大多用B+樹實(shí)現(xiàn)。再者，在處理語法解析的時(shí)候，各種語言解析之后都是生成語法樹，再做后續(xù)處理。另外，赫夫曼樹又稱最優(yōu)二叉樹，是一類帶權(quán)路徑長(zhǎng)度最短的二叉樹，我們平時(shí)所用的壓縮和解壓縮技術(shù)就是從這個(gè)基礎(chǔ)發(fā)展而來的。二叉樹的應(yīng)用斐波那契數(shù)列：0，1，2，3，5，8，13，21，34，55，89，...F(n)=F(n-1)+F(n-2)F(1)=1F(0)=0F（6）F（4）F（2）F（1）F（1）F（5）F（3）F（4）F（3）F（2）F（3）F（2）F（2）F（1）F（1）F（0）F（2）F（1）F（0）F（1）F（0）F（1）F（0）F（1）F（0）多對(duì)多關(guān)系：圖結(jié)構(gòu)圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，每一結(jié)點(diǎn)可以有多個(gè)前趨、多個(gè)后繼，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能關(guān)聯(lián)。佛山惠州廣州中山東莞深圳珠海圖1-2

網(wǎng)狀結(jié)構(gòu)圖的應(yīng)用圖1-2

網(wǎng)狀結(jié)構(gòu)求最短路徑問題，著名的有迪杰斯特拉算法和弗洛伊德算法。3.3文件：數(shù)據(jù)是如何保存的1.文件有什么用？2.文件的結(jié)構(gòu)與存儲(chǔ)3.用目錄結(jié)構(gòu)管理文件4.如何使用文件1.文件有什么用？文件是存儲(chǔ)在計(jì)算機(jī)外部存儲(chǔ)器上的信息集合；是數(shù)據(jù)在外存中的存儲(chǔ)方式；文件屬性是一組描述與計(jì)算機(jī)文件相關(guān)的信息。文件名由主名和擴(kuò)展名兩部分組成。常見的擴(kuò)展名有：Rar壓縮包、html網(wǎng)頁、exe、pdf、rm視頻文件、avi視頻文件、xls工作表、txt、doc、docx、log日志文件bmp、gif、jpg、pic、png、tif：圖形文件wav、aif、au、mp3、ram：聲音文件文件名大小創(chuàng)建時(shí)間作者屬性1.文件有什么用？文件名通過擴(kuò)展名分類，不同類型的文件有不同的圖標(biāo)。2.文件的結(jié)構(gòu)與存儲(chǔ)文件的邏輯結(jié)構(gòu)有:記錄式文件：是指由若干個(gè)相關(guān)的記錄組成的文件。流式文件：是一串無結(jié)構(gòu)的連續(xù)字符序列；如源程序、流媒體等文件。文件的結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)二種。邏輯結(jié)構(gòu)指一個(gè)文件在用戶面前所呈現(xiàn)的形式；而物理結(jié)構(gòu)指文件在外存儲(chǔ)器上的存儲(chǔ)形式。2.文件的結(jié)構(gòu)與存儲(chǔ)文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu)：文件的物理結(jié)構(gòu)又稱文件的存儲(chǔ)結(jié)構(gòu)，與存儲(chǔ)介質(zhì)的存儲(chǔ)性能有關(guān)。有順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)。2.文件的結(jié)構(gòu)與存儲(chǔ)文件的物理結(jié)構(gòu)順序結(jié)構(gòu)鏈接結(jié)構(gòu)索引結(jié)構(gòu)3.用目錄結(jié)構(gòu)管理文件由一個(gè)根、子目錄、文件組成的結(jié)構(gòu)就稱為樹形目錄結(jié)構(gòu)，它像一棵倒置的樹。絕對(duì)路徑:

\usr\bin\man相對(duì)路徑:設(shè)當(dāng)前目錄是usr,訪問man的路徑\bin\manC:4.如何使用文件文件的管理和操作是由操作系統(tǒng)完成的。程序是如何操作文件的呢？文件是存放在外存上的，而內(nèi)存與外存的訪問速度相差很大，并且文件的數(shù)據(jù)量往往很大，一下子全部調(diào)入內(nèi)存顯然不現(xiàn)實(shí)，所以在內(nèi)存中建立一個(gè)文件緩沖區(qū)，程序與文件的數(shù)據(jù)交換一律通過這個(gè)緩沖區(qū)進(jìn)行。4.如何使用文件常用的文件基本操作：創(chuàng)建文件刪除文件打開文件讀、寫文件關(guān)閉文件3.4數(shù)據(jù)庫(kù)：數(shù)據(jù)管理的利器1.身邊的數(shù)據(jù)庫(kù)2.數(shù)據(jù)管理技術(shù)的產(chǎn)生和發(fā)展3.數(shù)據(jù)庫(kù)系統(tǒng)中的幾個(gè)概念4.小型數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)1.身邊的數(shù)據(jù)庫(kù)你的身份證或戶籍信息存儲(chǔ)在居民信息管理中心的數(shù)據(jù)庫(kù)中；你的手機(jī)信息及通訊信息存儲(chǔ)在對(duì)應(yīng)的通信公司的信息管理中心的數(shù)據(jù)庫(kù)中；你的銀行（信用）卡信息存儲(chǔ)在銀行信息管理中心的數(shù)據(jù)庫(kù)中；你上網(wǎng)購(gòu)物交易的信息存儲(chǔ)在各個(gè)網(wǎng)站的后臺(tái)信息管理中心的數(shù)據(jù)庫(kù)中；如果你是學(xué)生，你的學(xué)籍信息存儲(chǔ)在學(xué)校學(xué)籍信息管理中心的數(shù)據(jù)庫(kù)中；……大數(shù)據(jù)價(jià)值發(fā)現(xiàn):華爾街金融家利用電腦程序分析全球3.4億微博賬戶的留言，根據(jù)民眾情緒拋售股票;銀行根據(jù)求職網(wǎng)站的崗位數(shù)量，推斷就業(yè)率;投資機(jī)構(gòu)搜集并分析上市企業(yè)聲明，從中尋找破產(chǎn)的蛛絲馬跡；美國(guó)總統(tǒng)奧巴馬的競(jìng)選團(tuán)隊(duì)依據(jù)選民的微博，實(shí)時(shí)分析選民對(duì)總統(tǒng)競(jìng)選人的喜好，基于數(shù)據(jù)對(duì)競(jìng)選議題的把握，成功贏得總統(tǒng)大選。中國(guó)網(wǎng)民發(fā)動(dòng)的“人肉搜索”，已成功地使若干“表哥”“表叔”“房叔”“房妹”等腐敗官員落入法網(wǎng)。1.身邊的數(shù)據(jù)庫(kù)2.數(shù)據(jù)管理技術(shù)的產(chǎn)生和發(fā)展

人工管理階段數(shù)據(jù)不保存，一個(gè)程序中的數(shù)據(jù)無法被其他程序使用；數(shù)據(jù)與程序不可分割，數(shù)據(jù)不具有獨(dú)立性，一組數(shù)據(jù)對(duì)應(yīng)一組程序；程序與程序之間存在大量重復(fù)數(shù)據(jù)，稱為數(shù)據(jù)冗余，數(shù)據(jù)不共享。2.數(shù)據(jù)管理技術(shù)的產(chǎn)生和發(fā)展文件系統(tǒng)階段文件系統(tǒng)階段的特點(diǎn)：數(shù)據(jù)以文件形式可長(zhǎng)期保存下來，程序與數(shù)據(jù)間有一定獨(dú)立性；同一數(shù)據(jù)項(xiàng)可能重復(fù)出現(xiàn)在多個(gè)文件中，數(shù)據(jù)冗余度大、共享性較差；數(shù)據(jù)的獨(dú)立性差；數(shù)據(jù)之間聯(lián)系較弱，易造成數(shù)據(jù)的不一致。2.數(shù)據(jù)管理技術(shù)的產(chǎn)生和發(fā)展數(shù)據(jù)庫(kù)系統(tǒng)階段數(shù)據(jù)結(jié)構(gòu)化數(shù)據(jù)結(jié)構(gòu)化是數(shù)據(jù)庫(kù)系統(tǒng)與文件系統(tǒng)的根本區(qū)別。數(shù)據(jù)共享性高、冗余少數(shù)據(jù)獨(dú)立性高數(shù)據(jù)的獨(dú)立性是指邏輯獨(dú)立性和物理獨(dú)立性。數(shù)據(jù)庫(kù)管理系統(tǒng)教務(wù)管理財(cái)務(wù)管理人事管理宿舍管理學(xué)號(hào)姓名性別系別年齡住址出身學(xué)位學(xué)分學(xué)費(fèi)課程成績(jī)學(xué)校數(shù)據(jù)庫(kù)3.數(shù)據(jù)庫(kù)系統(tǒng)中的幾個(gè)概念

數(shù)據(jù)庫(kù)系統(tǒng)(DBS):DatabaseSystem數(shù)據(jù)庫(kù)(DB):Database數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS):DatabaseManagementSystem數(shù)據(jù)庫(kù)應(yīng)用(DBAP):DataBaseApplication數(shù)據(jù)庫(kù)管理員(DBA):DataBaseAdministrator

計(jì)算機(jī)硬件系統(tǒng)數(shù)據(jù)庫(kù)(DB)數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)相關(guān)軟件（操作系統(tǒng)、軟件開發(fā)工具等）各類人員(DBA、系統(tǒng)分析員、程序員、用戶)DBS4.小型數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)

一個(gè)小型的數(shù)據(jù)庫(kù)系統(tǒng)——“學(xué)生信息管理系統(tǒng)”的建立。數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)的開發(fā)過程：(1)．需求分析 為學(xué)校教務(wù)部建立一個(gè)基于計(jì)算機(jī)的學(xué)生信息管理系統(tǒng)，成績(jī)管理需要處理的信息有哪些？處理的要求是什么？數(shù)據(jù)間有什么關(guān)聯(lián)？(2)．概念模型的建立 E-R圖，即“實(shí)體-聯(lián)系方法”（Entity-RelationshipApproach）。用E-R方法建立的概念結(jié)構(gòu)模型稱為E-R模型。 E-R圖基本成分包含實(shí)體型、屬性和聯(lián)系。①實(shí)體型：用矩形框表示，框內(nèi)標(biāo)注實(shí)體名稱。②屬性：用橢圓形框表示，框內(nèi)標(biāo)注屬性名稱。③聯(lián)系：指實(shí)體之間的聯(lián)系，有一對(duì)一（1：1），一對(duì)多（1：n）或多對(duì)多（m：n）三種聯(lián)系類型。聯(lián)系用菱形框表示，框內(nèi)標(biāo)注聯(lián)系名稱。4.小型數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)

系統(tǒng)的實(shí)體-聯(lián)系圖E—R圖4.小型數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)

(3)．關(guān)系模型的建立 DBMS所支持的數(shù)據(jù)模型：網(wǎng)狀模型、層次模型和關(guān)系模型。關(guān)系模型是目前使用最廣泛的一種數(shù)據(jù)模型。 關(guān)系模型是用“二維表”表示事物及其之間的聯(lián)系。 關(guān)系名（屬性1，屬性2，…，屬性n）專業(yè)(專