單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,2019/11/17,東莞理工學院機電系田君,?#?,2024/11/19,東莞理工學院機電系田君,1,3.1,數(shù)據(jù)結構,,數(shù)據(jù)結構是數(shù)據(jù)之間的結構和關系。,數(shù)據(jù)結構的基本概念包括數(shù)據(jù)結構的定義以及數(shù)據(jù)的,邏輯結構,和,物理結構,概念，常見的數(shù)據(jù)結構主要包括,線性表,、,棧,、,隊列,、,數(shù)組,、,串,、,樹,與,二叉樹,、,圖,與,網,等相關內容。,,數(shù)據(jù)結構的基本概念,(,一,),,在數(shù)據(jù)處理中，首先應將現(xiàn)實世界轉化為信息世界，然后將信息世界轉化為數(shù)據(jù)世界。這就包含幾個層次概念：,第,1,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,2,,,,,,實體,客觀存在的并可互相區(qū)分的事物,,屬性,實體的特征,,屬性值,每個屬性所能測量或紀錄的值,,域,屬性值的變化范圍,,數(shù)據(jù),描述實體的數(shù)值、字符及其它的各種物理符號,,,字符,是數(shù)據(jù)的最小單位,,數(shù)據(jù)項,是數(shù)據(jù)中最基本的、不可分的并有命名的數(shù)據(jù)單位,,組合項,由若干個數(shù)據(jù)項組成,,記錄,相關組合項和數(shù)據(jù)項的集合構成一個記錄，是描述某個實體屬性的集合,,文件,相同性質的記錄的集合就是文件,,數(shù)據(jù)庫,非單純性、有結構文件的集合,第,2,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,3,數(shù)據(jù)結構的基本概念,(,二,),數(shù)據(jù)結構理論,研究數(shù)據(jù)元素之間的抽象化關系，并不涉及數(shù)據(jù)元素的具體內容。以車床為例：,車床零部件關系示意圖,第,3,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,4,數(shù)據(jù)結構,包括數(shù)據(jù)的,邏輯結構,和,物理結構,。,數(shù)據(jù)結構的基本概念,:,數(shù)據(jù)的邏輯結構,數(shù)據(jù)的邏輯結構描述的是數(shù)據(jù)之間的邏輯關系，它從客觀的角度組織和表達數(shù)據(jù)。,線性結構,在這種結構中，每一個數(shù)據(jù)元素僅與它前面的一個和后面的一個數(shù)據(jù)元素相聯(lián)系，因而只能表達數(shù)據(jù)間的簡單順序關系。下圖就表示了一個線性結構：,,線性結構示意圖,第,4,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,5,非線性結構,包括,樹狀結構,和,網狀結構,等。如下面的工藝路線方案圖即是一種網狀結構,第,5,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,6,數(shù)據(jù)結構的基本概念,:,數(shù)據(jù)的物理結構,數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機內部的存儲方式，它從物理存儲的角度來描述數(shù)據(jù)以及數(shù)據(jù)間的關系。,順序存儲結構,利用連續(xù)的存儲單元依次存放各數(shù)據(jù)元素。如將,G1(12),G2(12)...G5(12),一維數(shù)組存入計算機，則各數(shù)據(jù)在存儲器中的存儲順序與邏輯順序一致，也為依次排列。,順序存儲結構占用存儲單元少，簡單易行，結構緊湊。但數(shù)據(jù)結構缺乏柔性，若要增刪數(shù)據(jù)，必須重新分配存儲單元，因而不適合需要頻繁修改、補充、刪除數(shù)據(jù)的場合。,,第,6,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,7,鏈接存儲結構,即把數(shù)據(jù)的地址分散存放在其他有關的數(shù)據(jù)中，并按照存取路徑進行鏈接。    在鏈接存儲結構中，一個數(shù)據(jù)元素項由信息字段（,INFO,）和指針字段,(POINT),組成：,信息字段,,指針字段,,,鏈接存儲有以下幾種形式：,鏈接存儲結構在不改變原來存儲結構的條件下，增刪記錄十分方便，只要控制指針即可,第,7,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,8,常見的數(shù)據(jù)結構,,,,,,,,線性結構,非線性結構,,線性表,,,樹,與,二叉樹,,棧,,圖與網,,隊列,,,,數(shù)組,,,串,,第,8,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,9,常見的數(shù)據(jù)結構,:,線性表,線性表是一個由,n,（,n≥0,）個數(shù)據(jù)元素,a1,a2,a3...an,組成的有限序列，表中的每一個數(shù)據(jù)元素，除了第一個和最后一個，僅有一個直接前驅和直接后繼。當,n=0,，稱為空表。,線性表邏輯結構,,[a(1),a(2),a(3),…,a(k-1),a(k),a(k+1),…,a(n)],,例如：光軸軸徑系列值表示成線性表形式：                      （,3,，,6,，,10,，,14,，,18,，,...,）,線性表物理結構,既可以采用順序存儲，也可以采用鏈接存儲結構。,第,9,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,10,常見的數(shù)據(jù)結構,:,棧,棧是一種特殊的線性表，它的插入與刪除操作只能在表的一端進行。,棧頂,在棧里，允許插入和刪除操作的一端稱為棧頂。,棧底,不允許插入和刪除操作的一端稱為棧底。,棧的操作,是按照后進先出的原則進行的。,,第,10,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,11,棧的順序存儲結構,第,11,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,12,常見的數(shù)據(jù)結構,:,隊列,隊列也是一種特殊的線性表，它限定只能在表的一端插入，在表的另一端刪除。,隊尾,允許插入的一端叫隊尾。,隊頭,允許刪除的一端叫隊頭。,操作,第一個進隊的數(shù)據(jù)元素也將會第一個出隊。所以，隊列也叫先進先出（,FIFO,）表。,,第,12,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,13,常見的數(shù)據(jù)結構,:,數(shù)組與串,數(shù)組,數(shù)組是一組按一定順序排列的具有相同類型的數(shù)據(jù)。    數(shù)組與線性表的存儲方式相同，用,順序存儲結構,存放在存儲器中，數(shù)組都是按一維排列存儲的。,串,串是一種字符型的線性表，通常記為：,A="a1a2...an",其中，,A,是串名，,a1a2a3...,為,A,的值。,ai(1≤i≤n),為字符型常量。    串可以用一個字符型數(shù)組來順序存儲，也可以,鏈接存儲,,第,13,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,14,常見的數(shù)據(jù)結構,:,樹,樹表示了元素之間的層次關系，這種關系就仿佛一棵倒長的樹，故得名。,第,14,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,15,樹中只有一個沒有前驅的結點稱為樹根，其它結點僅有一個直接前驅結點；樹中結點的最大層次稱為樹的深度；結點的子樹的個數(shù)稱為度；度數(shù)是,0,的結點稱為樹葉。,實例,樹是一種常見的數(shù)據(jù)結構。例如一張普通的校,-,系行政單位分類表，這就是一個樹狀結構。,樹的物理結構,樹中的各數(shù)據(jù)可以連續(xù)存儲，也可以分散存儲，通過指針來建立元素間的聯(lián)系和存取路徑。,第,15,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,16,常見的數(shù)據(jù)結構,:,二叉樹,特點與形態(tài),a.,二叉樹可以是空的，樹則必須至少有一個根結點。,b.,二叉樹的度數(shù)不能超過,2,，樹則無此限制。,c.,二叉樹的子樹有左、右之分，不能顛倒，樹的子樹則可以交換位置。,,第,16,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,17,物理結構,通常采用鏈接結構，每個結點設兩個指針，左指針指向左子樹的地址；右指針指向右子樹的地址。,常見的數(shù)據(jù)結構,:,二叉樹,第,17,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,18,二叉樹的遍歷,即按一定規(guī)律，不重復地訪問樹中的每一個結點。,前序遍歷：按從上到下，先左后右的原則。,中序遍歷：按從左向上，先上后下的原則。,第,18,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,19,后序遍歷：按從左到右，先下后上的原則。,第,19,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,20,常見的數(shù)據(jù)結構,:,圖與網圖,圖是比樹更為復雜的一種非線性結構。圖由頂點和邊組成，設圖,G=,（,V,E,）其中,V,是頂點的集合；,E,是邊的集合。邊由確定該邊的兩頂點表示。若兩頂點是有序的，則從,Vi,到,Vj,用一帶箭頭的線段相連，并用尖括號表示,〈Vi,Vj〉,,這樣的圖稱為有向圖。若兩頂點是無序的，則邊不帶箭頭，用圓括號表示為,(Vi,Vj),，這樣的圖稱為無向圖。    通常用,N,階方陣表示,N,個頂點的圖的邏輯結構。每個元素滿足：,V,（,i,j,）,=1,若（,Vi,Vj,）∈,E(G),即,Vi,Vj,有邊連接,V,（,i,j,）,=0,若,Vi,Vj,無邊連接,,第,20,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,21,第,21,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,22,網,當圖的邊具有和它相關的權時，這樣的圖稱為網。權可以代表從一個頂點到另一個頂點的距離、時間、所耗代價等等。網同樣可采用鄰接矩陣的形式表示,,,只是矩陣元素的取值為相應的權值。,,V,（,i,j,）,=Wij,若（,Vi,Vj,）∈,E(G),即,Vi,Vj,有邊連接,V,（,i,j,）,=0,若,Vi,Vj,無邊連接,,第,22,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,23,3.2,工程數(shù)據(jù)的程序化處理,,在,CAD/CAM,中，需要將相關資料先期以數(shù)據(jù)庫或文件的形式加以管理，以便在設計時由計算機按要求自動檢索和調用；或在程序編制過程中融于其中，將其程序化，隨著程序的運行自動選擇，加工處理。,,數(shù)值的程序化,(,一）,數(shù)值程序化是將要使用的各個參數(shù)及其函數(shù)關系，用一種合理編制的程序存入計算機，以便運行使用。,用數(shù)組形式存儲數(shù)據(jù),當要使用的數(shù)據(jù)是單一、嚴格、無規(guī)律可循的數(shù)列，通常的方法是用數(shù)組形式存儲數(shù)據(jù)，程序運行時，直接檢索使用。,第,23,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,24,,例,:,將表中的齒輪標準模數(shù)值編入程序。要求程序運行時，輸入模數(shù)計算值后，能輸出適合的標準模數(shù)值。,齒輪標準模數(shù)（部分）,第一系列,2,,2.5,,3,,,第二系列,,2.75,,2.75,,(3.25),3.5,第一系列,,4,,5,,6,,第二系列,3.75,,4.5,,,5.5,,(6.5),第一系列,,8,,10,,12,,第二系列,7,,9,,(11),,14,第,24,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,25,解題分析：,考察表中數(shù)據(jù)及實際使用情況，有如下特點：所列齒輪標準模數(shù)是一組取值嚴格，而從總體上看又無統(tǒng)一規(guī)律的的數(shù)列。標準規(guī)定：第一系列為優(yōu)先采用模數(shù)；第二系列中不帶括號的數(shù)值為可以采用的模數(shù)；而帶括號的為盡可能不采用的模數(shù)，程序中應能反映這一標準規(guī)定。通常，根據(jù)模數(shù)的計算值取較大的標準值選取。但對于比標準值大得有限的一類計算值（如：計算值為,3.01mm,，標準值為,3mm,），若選用高一檔的模數(shù)值或許并不適合，編程中應考慮這一情況。,,第,25,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,26,第,26,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,27,第,27,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,28,數(shù)值程序化（二）,用數(shù)學公式計算數(shù)據(jù),當使用的數(shù)據(jù)是一組單一、嚴格、但能找到某種規(guī)律的數(shù)列，則不必定義數(shù)組逐項賦值，將反映這種規(guī)律的數(shù)學公式編入程序，通過計算即可快速、準確地達到目的。     例：將,60,，,70,，,80,，,90,，,100,，,110,，,120,這一標準直徑系列編入程序。,解題分析,：這組數(shù)值是按,10,遞增的，導出數(shù)學公式，問題就迎刃而解了。          公式：,D=INT,（,Dc/10.02,）*,10+10,其中,Dc,為計算所得直徑；,D,為所選標準直徑,第,28,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,29,第,29,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,30,數(shù)表程序化,數(shù)表程序化是用程序完整準確地描述不同函數(shù)關系的數(shù)表，以便在運行過程中迅速有效地檢索和使用數(shù)表中的數(shù)據(jù)。,,屏幕直觀輸出法,,數(shù)組存儲法,,公式計算法,,第,30,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,31,屏幕直觀輸出法,例,:,將齒輪傳動強度計算中的使用系數(shù),KA,數(shù)表程序化。要求根據(jù)原動機工作特性和工作載荷特性確定適宜的使用系數(shù),KA,,,使用系數(shù),KA,,原動機工作特性,工作機械載荷特性,,,,平穩(wěn),中等沖擊,較大沖擊,平穩(wěn),1.00,1.25,1.75,輕度沖擊,1.25,1.50,2.00,或更大,中等沖擊,1.50,1.75,2.25,或更大,解題分析,縱觀表格，雖然幅面不大、數(shù)據(jù)有限，但因,KA,是經驗值，實際應用允許根據(jù)情況綜合考慮，選取中間數(shù)值，僅憑程序中的簡單的條件判斷難以正確選取。此時，可采用屏幕直觀顯示整個數(shù)表的方法，讓用戶憑經驗自行選取,KA,。,第,31,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,32,數(shù)組存儲法：,例：將平鍵和鍵槽與軸徑的尺寸關系表程序化。要求輸入軸徑后，能輸出相應的鍵和鍵槽的剖面尺寸。在滿足傳遞所需轉矩條件下，允許用較小剖面的鍵，但應使鍵側與軸槽及輪槽接觸高度各為,h/2,。 平鍵和鍵槽的剖面尺寸（部分）,,,軸徑,d,鍵,,鍵槽,,,,b,,h,t,t,1,>17-22,6,6,3.5,2.8,>22-30,8,7,4.0,3.3,>30-38,10,8,5.0,3.3,>38-44,12,8,5.5,3.3,>44-50,14,9,6.0,3.8,>50-58,16,10,6.5,4.3,>58-65,18,11,7.0,4.4,>65-75,20,12,7.5,4.9,>75-85,22,14,9.0,5.4,>85-95,25,14,9.0,5.4,>95-110,28,16,10.0,6.4,>110-130,32,18,11.0,7.4,第,32,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,33,解題分析：,表中數(shù)據(jù)有如下特點：,項目多、確定而無規(guī)律。,每組鍵槽尺寸要適應一定范圍尺寸的軸徑使用。,標準附注功能應在程序中予以體現(xiàn)。為此，編程前需推導出鍵的剖面尺寸,b,、,h,與軸徑,d,的幾何關系式，從中算出,t,和,t1,。,,第,33,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,34,數(shù)表程序化,:,公式計算法,插值法,設法構造某個簡單的函數(shù),Y=P(x),作為列表函數(shù),f(x),的近似表達式，然后，計算,P(x),值以得到,f(x),的近似值。并且使,f(x)=P(xi) i=1,，,2,，,3....,，,n,成立。,P(xi),就稱為,f(x),的插值函數(shù)，點,x1,x2,x3...,xn,稱為插值節(jié)點。,線性插值,,,拉格朗日插值,曲線擬合,在這種方法中構造出若干曲線，此曲線并不是嚴格通過所有節(jié)點，而是盡可能反映所給數(shù)據(jù)的趨勢。,具體方法請參照,線圖程序化,。,第,34,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,35,線性插值,原理,即兩點插值。已知插值點,P,的相鄰兩點：,y1=f(x1),，,y2=f(x2),，如圖所示。近似認為在此區(qū)域，函數(shù)呈線性變化，根據(jù)幾何關系可求的插值點,P,對應于,x,的函數(shù)值。,線性插值舉例,,第,35,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,36,拉格朗日插值,從幾何示意圖顯示，,線性插值,的誤差比較大，需要的情況下，可采用多次插值公式，提高插值精度。,原理,將線性插值公式整理得,:,第,36,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,37,線圖的程序化,工程手冊中的線圖可能來源于某已知的復雜理論公式，也可以根據(jù)經驗數(shù)據(jù)制作出來，對于前者，查閱其原始公式編程即可。對于后者，可采用經驗公式處理，建立這種經驗公式的過程稱為曲線擬合。,曲線擬合的方法,常用的典型方法是最小二乘法。,線性方程擬合,,對數(shù)方程擬合,,指數(shù)方程擬合,,對數(shù)指數(shù)方程擬合,,多項式擬合,,第,37,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,38,線圖程序化的步驟：,線圖數(shù)表化。要注意：弄清線圖坐標的含義，確切掌握坐標的比例性質、大小和量綱；讀準數(shù)值，尤其是特征點,--,起點、終點、峰點、谷點、轉折點、中點等。,確定合理的精度，控制誤差在允許的范圍之內。,正確運用分段原則。按曲線走向，相似部分作為一段，分段擬合，使方程簡化并且可提高精度。,選擇合適的擬合方程。采用多種方程分別擬合，從中選出最佳方案。,根據(jù)建立的擬合方程編程。,,第,38,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,39,線性方程擬合,原理,有,N,組實驗數(shù)據(jù),xi,yi,，設線性方程的形式是：,y=a+bx,根據(jù)最小二乘法定義，為了達到最好擬合，應使各節(jié)點的最小偏差平方和為最小。設,S(a,b),為偏差平方和，則,:,對上式求偏導并使之為零，得,第,39,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,40,線性擬合舉例,將,Z,型帶長度系數(shù),KL,與基準長度,Ld,之間關系數(shù)據(jù)用線性方程擬合。,第,40,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,41,第,41,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,42,對數(shù)方程擬合,原理,設有實驗數(shù)據(jù),xi,yi,，設對數(shù)方程形式為：,y=a+blnx,,采用變量代換的方法，使之回歸為線性方程形式。令,X=lnx,,同,線性方程擬合,可求出系數(shù),a,，,b,值。    注意：這里,Xi=lnxi,，其偏差平方和：,,第,42,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,43,對數(shù)方程擬合舉例,將,Z,型帶長度系數(shù),KL,與基準長度,Ld,之間關系數(shù)據(jù)用對數(shù)方程擬合。,第,43,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,44,第,44,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,45,數(shù)據(jù)資料文件化,數(shù)據(jù)資料文件化通常采用兩種類型文件,,第,45,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,46,第,46,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,47,3.3,數(shù)據(jù)的存儲與管理,,文件,,是數(shù)據(jù)管理的一種形式，它能獨立于應用程序單獨存儲。具體地說，文件是記錄的集合。,·,,文件的組織方法,,·,,文件的,查找,和,排序,,數(shù)據(jù)庫,,是一種能較好地解決共享問題的數(shù)據(jù)處理方法。,·,,數(shù)據(jù)庫的特點,,·,,數(shù)據(jù)庫管理系統(tǒng),,·,,數(shù)據(jù)庫的數(shù)據(jù)模型,,·,,工程數(shù)據(jù)庫,,·,,新一代數(shù)據(jù)庫,,,第,47,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,48,文件的組織方法,,同一文件的邏輯結構可以有多種物理組織方法。,,組織方法,,,概念,,,說明,,,,順序文件,,,,,物理順序與邏輯順序一致的文件。,,,,,,磁帶就是典型的順序存儲器。,,,,索引文件,,,,,帶有一包括關鍵字和存放地址索引表的文件。,,,,,索引文件的索引項必須按關鍵字順序排列，文件本身可以按順序排列或不按順序排列，前者稱為索引順序文件，后者稱為非索引順序文件。,,,直接存取文件 （隨機文件）,,,,,,采用一種算法將記錄的關鍵字轉化為一個近乎隨機的數(shù)，根據(jù)這個數(shù)確定記錄在存儲器上的位置，以便存取。,,,,,直接存取文件通常是利用,雜湊法,組織的。,,,,第,48,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,49,文件的查找,順序查找法,從第一條記錄開始，逐個查詢，若找到欲查數(shù)值，則查找成功；否則查找失敗。該法簡單，但效率低。,折半查找法（二分查找法）,·,,,先將文件記錄按關鍵字順序排列。,·,,,再將查找范圍中點處關鍵字,K,M,與,K,待查記錄關鍵字比較，應為下列三種情況：,,a)K<K,M,，確定待查記錄在文件前半?yún)^(qū)域。,,b)K=K,M,，確定該記錄就是待查記錄。,,c)K>K,M,，確定待查記錄在文件后半?yún)^(qū)。,·,,,若為情況,b),，則查找成功；若為情況,c),或,a),，則在確定的區(qū)域中再次順序查找，或逐次折半查找。,,第,49,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,50,分塊查找法,,與折半查找法類似，只是要先將按關鍵字排好順序的文件劃分為大于,2,的若干塊；再將待查關鍵字依次與各塊的最大關鍵字比較，確定查找范圍；然后順序查找。,文件的排序,選擇排序,,以升序排列為例，在所有的記錄中選出關鍵字最小的記錄，將它與第一個記錄交換，然后，在第二個記錄到最后一個記錄中重復上述的操作。,冒泡排序,,以升序排列為例，順序比較相鄰記錄的關鍵值，若后者比前者小，則交換位置。否則，位置不變。經過數(shù)輪比較和交換，較小的數(shù)向前移動，較大的數(shù)向后移動，就像水中的氣泡一點點冒出水面，故而得名。,插入排序,,仍以升序為例，首先假定第一個記錄的位置是適合的，然后取出第二個記錄與第一個記錄進行關鍵字比較。若小于，則插到前面，否則，位置不變；再取第三個數(shù)據(jù)與前面的各記錄進行關鍵字比較，將其插入到前面有序記錄的適合位置上；依此類推，直到完成排序。,,第,50,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,51,數(shù)據(jù)庫的特點,數(shù)據(jù)庫技術是三種數(shù)據(jù)管理技術之一，是在人工管理，,文件管理,技術上發(fā)展起來的數(shù)據(jù)管理技術。,,特點,,,說明,,,復雜的數(shù)據(jù)模型,,,,,即在描述數(shù)據(jù)的同時，也描述數(shù)據(jù)之間的聯(lián)系，即數(shù)據(jù)結構化。,,,數(shù)據(jù)共享性好，冗余度低,,,,,數(shù)據(jù)庫從整體觀點處理數(shù)據(jù)，面向系統(tǒng)，因而彈性大，使用靈活，實現(xiàn)了數(shù)據(jù)共享。,,,數(shù)據(jù)具有獨立性,,,,,數(shù)據(jù)可獨立于程序存在，應用程序也不必隨數(shù)據(jù)結構的變化而修改。,,,數(shù)據(jù)具有安全性和完整性,,,,,數(shù)據(jù)庫系統(tǒng)提供數(shù)據(jù)的控制功能，保護數(shù)據(jù)，防止不合理使用；保證數(shù)據(jù)的確定性、有效性和相容性，即數(shù)據(jù)的完整性,。,,,,第,51,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,52,數(shù)據(jù)庫系統(tǒng)構成,,組成部分,,,功能,,,硬件,,,,,支持數(shù)據(jù)庫管理系統(tǒng)、應用程序運行的設備環(huán)境。,,,軟件,,,,,支持數(shù)據(jù)庫管理系統(tǒng)運行的軟件環(huán)境。包括支持,DBMS,的操作系統(tǒng)、宿主語言系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)以及應用程序。（數(shù)據(jù)庫軟件系統(tǒng)層次如下圖）,,,數(shù)據(jù)庫管理員（,Data Base Administrator,，簡稱,DBA,）,,,,,負責數(shù)據(jù)庫系統(tǒng)的建成，維護和協(xié)調工作的專門人員。,,,數(shù)據(jù)庫,,,,,是由,DBMS,建立、運用、管理及維護的通用化的、綜合性的數(shù)據(jù)集合。,,,,第,52,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,53,第,53,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,54,數(shù)據(jù)庫管理系統(tǒng)（二）,數(shù)據(jù)庫管理系統(tǒng)的功能,,第,54,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,55,數(shù)據(jù)庫管理系統(tǒng)的組成,,第,55,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,56,數(shù)據(jù)庫管理系統(tǒng)（三）,模型,,在數(shù)據(jù)庫系統(tǒng)中，用戶看到的數(shù)據(jù)與計算機中存放的數(shù)據(jù)并不是一一映像的關系，而是存在著三個層次：,層次,,,說明,,,外模型,,,,,用戶使用的數(shù)據(jù)視圖。這是一種局部的邏輯數(shù)據(jù)視圖，它表示用戶所理解的實體、實體屬性和實體間的聯(lián)系。外模型有多個，處于系統(tǒng)的外部。,,,概念模型,,,,,數(shù)據(jù)庫系統(tǒng)的全局邏輯視圖。它代表了整個系統(tǒng)的抽象實體、實體屬性和實體間的聯(lián)系。概念模型只有一個，屬于系統(tǒng)的概念層。,,,內模型,,,,,物理數(shù)據(jù)存儲的模型。亦只有一個，處于系統(tǒng)的內層，也是最低層 。,,,,第,56,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,57,數(shù)據(jù)模式,,用,DBMS,中的,DDL,精確定義上述模型就成為模式。對于不同層次的模型，也有相應的模式：,外模式（子模式）；概念模式（模式）；內模式（物理模式）,,,請參看：,DBMS,各模式之間的關系圖,,第,57,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,58,第,58,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,59,數(shù)據(jù)庫管理系統(tǒng)（四）,數(shù)據(jù)庫的層次,以子模式為框架的數(shù)據(jù)庫是用戶數(shù)據(jù)庫； 以模式為框架的數(shù)據(jù)庫是概念數(shù)據(jù)庫； 以物理模式為框架的數(shù)據(jù)庫是物理數(shù)據(jù)庫。,不同層次數(shù)據(jù)庫之間的關系：,第,59,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,60,第,60,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,61,數(shù)據(jù)庫的數(shù)據(jù)模型（一）,層次模型,,,,用樹性結構表示實體之間連系的模型稱為層次模型，它能描述一對多的關系。,,層次模型必須滿足兩個條件：,只有一個根結點。,根以外的其他節(jié)點有且只有一個父節(jié)點。,,第,61,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,62,網狀模型,,網狀模型必須滿足兩個條件：,·,,,可以有兩個以上結點無父點。,·,,,至少有一個結點有多于一個父結點。,第,62,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,63,數(shù)據(jù)庫的數(shù)據(jù)模型（二）,關系模型,,這是一種用二維表結構表示實體之間聯(lián)系的模型，能描述多對多的關系。一個二維表就成為一個,關系,：,,第,63,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,64,作為一個,“,關系,”,的二維表，必須滿足如下條件：,·,,,表中每一列必須是基本數(shù)據(jù)項，而不是組合項。,·,,,表中每一列必須具有相同的數(shù)據(jù)類型。,·,,,表中的每一列必須有一個唯一的屬性名。,·,,,表中不應有內容相同的行。,·,,,行與列的順序均不影響表中所表示的信息含義。,,第,64,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,65,工程數(shù)據(jù)庫（一）,工程數(shù)據(jù)庫管理系統(tǒng),,簡稱,EDBMS(Engineering Data Base Management System),，其功能是針對工程數(shù)據(jù)的特點而設置的。,工程數(shù)據(jù)庫管理系統(tǒng)功能特點,·,,,能描述復雜的數(shù)據(jù)模型，保存相關語義信息。,·,,,支持模式的動態(tài)定義和修改，不需重新編譯和數(shù)據(jù)重載。,·,,,支持工程長事務的處理。,·,,,能存儲和管理各種類型數(shù)據(jù)，并支持圖形標準件的相互轉化，具有多庫協(xié)調管理能力。,·,,,具有版本管理功能。,·,,,支持程序控制和交互操作兩種工作方式。,·,,,具有分布式數(shù)據(jù)庫處理能力，支持多用戶工作環(huán)境。,,第,65,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,66,工,程數(shù)據(jù)庫（二）,工程數(shù)據(jù)庫管理系統(tǒng)的開發(fā)方法,,,·,,,以商用,DBMS,為底層支撐環(huán)境，使用數(shù)據(jù)操縱語言嵌入宿主語言，建立更加簡潔、良好的人機界面和外圍管理結構，擴充所需的各種功能，從而達到適用于,CAD/CAM,工程環(huán)境的目的。,,·,,,分析、拆解商用,DBMS,原代碼，按,EDBMS,要求修改原組織結構、概念模式、擴充強化功能。,,·,,,開發(fā)通用的工程數(shù)據(jù)庫管理系統(tǒng)，按,EDBMS,的規(guī)范化設計標準，將工程應用的特殊需求融于,DBMS,內部，從無到有地開發(fā),EDBMS,。,工程數(shù)據(jù)庫的發(fā)展趨勢,,,,新型化 智能化 巨型化 工具化 分布式 集成化,,第,66,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,67,新一代數(shù)據(jù)庫技術,分布式數(shù)據(jù)庫,,數(shù)據(jù)庫技術與分布處理技術相結合產生了分布式數(shù)據(jù)庫（,Distribute Database,）。它是由一組分布在不同場地計算機中的數(shù)據(jù)組成，這組數(shù)據(jù)具有物理分布性、邏輯整體性、分布獨立性和場地自制能力。,,所謂物理分布性，即數(shù)據(jù)庫中的數(shù)據(jù)分布在計算機網絡的不同場地計算機上。所謂邏輯整體性，即數(shù)據(jù)庫中的數(shù)據(jù)雖然物理分布，但邏輯相關，是相互聯(lián)系的整體。所謂獨立分布，即分布透明性，在用戶來看，整個數(shù)據(jù)庫系統(tǒng)仍是一個集中的數(shù)據(jù)庫，不關心數(shù)據(jù)物理位置分布的細節(jié)，分布的實現(xiàn)完全由系統(tǒng)完成。所謂場地自制能力，即系統(tǒng)網絡中的每個節(jié)點具有獨立處理能力，可以執(zhí)行局部應用，同時也能通過網絡執(zhí)行全局應用。,,,分布式數(shù)據(jù)庫能夠適應部門分布的組織結構，降低通信代價，提高響應速度；能提高系統(tǒng)的可靠性和可用性，一個場地的故障不會引起整個系統(tǒng)崩潰；有利于充分利用數(shù)據(jù)庫資源，提高現(xiàn)有集中式數(shù)據(jù)庫的利用率；便于擴展處理能力和系統(tǒng)規(guī)模,,第,67,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,68,主動數(shù)據(jù)庫,,數(shù)據(jù)庫技術和人工智能技術相結合產生了主動數(shù)據(jù)庫（,Active Database,）。它是相對傳統(tǒng)數(shù)據(jù)庫的被動性而言的，能根據(jù)應用系統(tǒng)的當前狀況，主動適時地作出反應，執(zhí)行某些操作向用戶提供相關信息。,,主動數(shù)據(jù)庫強調主動性、快速性和智能性，其主要目標是提供對緊急情況的及時反應能力，同時提高數(shù)據(jù)庫管理系統(tǒng)的模塊化程度。通常采用的方法是在數(shù)據(jù)庫系統(tǒng)中嵌入,ECA,（事件,-,條件,-,動作）規(guī)則，設置觸發(fā)器，在某一事件發(fā)生時引發(fā)數(shù)據(jù)庫管理系統(tǒng)檢測數(shù)據(jù)庫當前狀態(tài)，只要條件滿足，就觸發(fā)規(guī)定動作的執(zhí)行。,,第,68,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,69,多媒體數(shù)據(jù)庫,,數(shù)據(jù)庫技術與多媒體技術相結合產生了多媒體數(shù)據(jù)庫技術（,Multi-media Database,）。它支持管理復雜的多媒體數(shù)據(jù)。,,多媒體數(shù)據(jù)庫在數(shù)據(jù)對象、數(shù)據(jù)類型、數(shù)據(jù)結構、數(shù)據(jù)模型、應用對象以及處理方式上都與傳統(tǒng)數(shù)據(jù)庫有較大差異，它存儲處理的是現(xiàn)實世界中復雜的多媒體表現(xiàn)形式，包括動態(tài)的視頻；它面向應用，強調媒體間的獨立性，重視媒體對象的物理表現(xiàn)和交付方式。,,多媒體數(shù)據(jù)庫是計算機技術以及相關技術發(fā)展的結果，尤其是在數(shù)據(jù)表現(xiàn)形式空前豐富的情況下，多媒體數(shù)據(jù)的管理與應用就變得越來越迫切。,,第,69,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,70,面向對象數(shù)據(jù)庫,,數(shù)據(jù)庫技術與面向對象程序設計的結合產生了面向對象數(shù)據(jù)庫（,Object Oriented Database,）。它是指對象的集合、行為、狀態(tài)和聯(lián)系均以面向對象數(shù)據(jù)模型來定義。,,面向對象數(shù)據(jù)庫為定義和操作對象間的聯(lián)系提供了用戶界面，應用程序員無須顯示編程后管理這些聯(lián)系。它支持如：,Oid,、實例、類、層次、繼承、封裝及消息傳遞等面向對象概念。,,第,70,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,71,3.4,軟件開發(fā)與軟件工程,,,CAD/CAM,軟件開發(fā)是一項高難度、高智力的工作。為了保障所開發(fā)軟件的質量，必須研究和采用科學的開發(fā)方法。,,,軟件開發(fā)的演化過程,,,軟件工程的概念,,,軟件工程的規(guī)范,,,軟件的開發(fā)方法,,第,71,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,72,軟件開發(fā)的演化過程,,第,72,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,73,軟件工程的概念,軟件工程,,指借鑒從事工程項目所積累的行之有效的原理、概念、技術和方法來開發(fā)和維護軟件，把正確的管理和科學的技術結合起來。這是一門指導計算機軟件開發(fā)和維護的工程學科。,軟件的生存周期,,軟件從形成概念開始，經過開發(fā)、使用和不斷補增修正，直到最終被淘汰的整個過程。,,,,軟件工程強調使用生存周期方法學，即將生存周期分為若干個既相互區(qū)別又相互聯(lián)系的階段,,第,73,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,74,軟件工程設計階,段,可行性研究與計劃階段,,需求分析階段,,設計階段,,實現(xiàn)階段,,測試階段,,運行與維護階段,,總結,,,,軟件工程利用生存周期方法學，在每個階段都采用科學的管理手段和良好的技術方法，使軟件開發(fā)全過程以一種有條不紊的方式進行，保證了軟件的質量，提高了軟件開發(fā)的成功率和生產率,,第,74,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,75,軟件工程規(guī)范（一）,軟件工程規(guī)范國家標準,第,75,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,76,軟件工程規(guī)范（二）,軟件文檔,,按照,《,計算機軟件產品開發(fā)文件編制指南,》,（,GB8567-88,）規(guī)定，整個軟件生存周期應該提供十四種標準文檔。小型軟件所需的五種文檔,軟件需求與開發(fā)計劃,,/,軟件設計說明書,,/,使用說明書,,/,測試分析報告,,/,項目開發(fā)總結,,第,76,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,77,第,77,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,78,軟件開發(fā)方法,對軟件的基本要求,第,78,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,79,軟件開發(fā)方法舉例,·,,,瀑布型,這是一種按軟件生存階段而順序工作的單項、單鏈的開發(fā)方法。,·,,,快速原型法,盡快向用戶提供原型系統(tǒng)，試通原理和路子，讓用戶使用，得到反饋信息，再按實用性、經濟性、可靠性要求進一步修改設計，解決原型系統(tǒng)暴露出來的問題。,·,,,平行進程法,該方法認為軟件開發(fā)是三個進程組相互平行，相輔相成，齊頭并進的團隊行為。,,第,79,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,80,各進程組的作用如下：,·,,,項目管理進程組,負責項目初始化，項目監(jiān)督控制和軟件管理。,·,,,開發(fā)進程組,分為三個組：,,,開發(fā)前進程組,負責概念探討、系統(tǒng)分析。,,,開發(fā)進程組,負責需求確定、設計和實現(xiàn)。,,,開發(fā)后進程組,負責安裝、運行支持、維護和淘汰。,集成進程組,負責驗收確認、配置管理、文檔開發(fā)和人員培訓。,,第,80,頁,/,共,81,頁,2024/11/19,東莞理工學院機電系田君,81,思考題,1.,說明數(shù)據(jù)資料程序化處理的目的及方法。,2.,簡述曲線擬合的理論基礎。,3.,數(shù)據(jù)結構的基本概念有哪些？,4.,說明常用邏輯結構和物理結構的類型、特點。,5.,論述文件的基本概念和作用，文件的組織形式、基本操作。,6.,結合文件管理說明數(shù)據(jù)庫系統(tǒng)的特點。,7.,數(shù)據(jù)庫系統(tǒng)在,CAD/CAM,集成系統(tǒng)中的作用是什么？,8.,說明數(shù)據(jù)庫管理系統(tǒng)的作用和功能。,9.,何謂數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)模型？各種模型有哪些特點？,10.,針對工程數(shù)據(jù)的特點，分析工程數(shù)據(jù)庫的功能需求。,,第,81,頁,/,共,81,頁,