大學計算機基礎教程（第三版）課件第7章 程序設計基礎

第7章程序設計基礎第7章程序設計基礎第7章程序設計基礎本章學習要求掌握逐步求精的結構化程序設計方法掌握基本數(shù)據(jù)結構及其操作掌握算法的基本概念及基本排序和查找算法掌握軟件工程的基本方法，具有初步應用相關技術進行軟件開發(fā)的能力掌握數(shù)據(jù)庫的基本知識，了解關系數(shù)據(jù)庫的設計2第7章程序設計基礎本章大綱7.1程序設計基本概念7.2軟件工程基礎7.3數(shù)據(jù)結構基礎7.4思維與算法7.5數(shù)據(jù)庫設計基礎3第7章程序設計基礎7.1程序設計基本概念初始程序程序設計方法程序設計語言412/23/2023第7章程序設計基礎7.2軟件工程基礎7.2.1軟件工程的基本概念7.2.2軟件開發(fā)過程7.2.3結構化分析方法7.2.4結構化設計方法7.2.5軟件測試第7章程序設計基礎7.1.1初始程序1．程序計算機程序或者軟件程序（簡稱程序）是指一組指示計算機每一步動作的指令，用某種程序設計語言編寫，運行于某種目標體系結構上。2．程序設計6第7章程序設計基礎7.1.2程序設計方法1．程序設計方法結構化程序設計方法面向對象的程序設計方法2.程序設計風格主要應注重和考慮以下幾個因素：源程序文檔化；數(shù)據(jù)說明方法化；語句的結構；輸入和輸出。712/23/2023第7章程序設計基礎7.1.3程序設計語言第一代機器語言第二代匯編語言第三代高級語言第四代非過程化語言12/23/2023第7章程序設計基礎7.2.1軟件工程的基本概念1．軟件的定義軟件（software）是與計算機系統(tǒng)操作有關的計算機程序、規(guī)程、規(guī)則，以及可能有的文件、文檔及數(shù)據(jù)的集合。2．軟件的特點3．軟件危機與軟件工程12/23/2023第7章程序設計基礎7.2.2軟件開發(fā)過程圖7-3軟件開發(fā)過程圖12/23/2023第7章程序設計基礎7.2.3結構化分析方法需求分析軟件需求分析是指用戶對目標軟件系統(tǒng)在功能、行為、性能、設計約束等方面的期望。結構化分析方法結構化分析方法結構化分析的常用工具軟件需求規(guī)格說明書12/23/2023第7章程序設計基礎7.2.4結構化設計方法1．軟件設計的基本概念軟件設計的基礎軟件設計的基本原理結構化設計方法2．概要設計概要設計的任務包括：設計軟件系統(tǒng)結構、數(shù)據(jù)結構及數(shù)據(jù)庫設計、編寫概要設計文檔、概要設計文檔評審。面向數(shù)據(jù)流的設計方法結構化設計的準則3．詳細設計常用的設計工具有：圖形工具：程序流程圖，N-S，PAD，HIPO；表格工具：判定表；語言工具：PDL（偽碼）。12/23/2023第7章程序設計基礎7.3數(shù)據(jù)結構基礎7.3.1數(shù)據(jù)結構的概念7.3.2線性表7.3.3棧和隊列7.3.4樹與二叉樹12/23/2023第7章程序設計基礎7.2.5軟件測試1．軟件測試的目的及準則包括需求定義階段的需求測試、編碼階段的單元測試、集成測試以及其后的確認測試、系統(tǒng)測試，驗證軟件是否合格、能否交付用戶使用等。2．軟件測試技術和方法綜述靜態(tài)測試與動態(tài)測試白盒測試方法與測試用例設計黑盒測試方法與測試用例設計軟件測試的實施軟件測試的實施過程主要有4個步驟：單元測試、集成測試、系統(tǒng)測試、驗收測試。12/23/2023第7章程序設計基礎7.3.1數(shù)據(jù)結構的概念數(shù)據(jù)結構的含義數(shù)據(jù)結構是數(shù)據(jù)的組織，存儲和運算的總和。它是信息的一種組織方式，是以數(shù)據(jù)按某種組織關系起來的一批數(shù)據(jù)，其目的是為了提高算法的效率，然后用一定的存儲方式存儲到計算機中，并且它通常與一組算法的集合相對應，通過這組算法集合可以對數(shù)據(jù)結構中的數(shù)據(jù)進行某種操作。數(shù)據(jù)結構的基本術語數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)對象數(shù)據(jù)結構數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構數(shù)據(jù)的存儲結構數(shù)據(jù)類型抽象數(shù)據(jù)類型12/23/2023第7章程序設計基礎7.3.2線性表線性表的邏輯結構線性表是由n(n>=0)個具有相同性質(zhì)的數(shù)據(jù)元素組成的有限序列。記為：List=(a0,a1,a2...,an)線性表的運算線性表的順序表示及實現(xiàn)線性表在計算機內(nèi)的存儲結構一般有兩種方式：一種是順序（靜態(tài)）存儲一種是鏈式（動態(tài)）存儲。12/23/2023第7章程序設計基礎7.3.3棧和隊列1．棧（1）棧的定義12/23/2023第7章程序設計基礎（2）棧的順序存儲一般地說，棧有兩種實現(xiàn)方法：順序存儲和鏈接存儲，12/23/2023第7章程序設計基礎其中：（a）表示順序棧為?？?，這也是初始化運算得到的結果。此時棧頂指針Top=0。此時如果作退棧運算，則產(chǎn)生“下溢”。（b）表示棧中只含一個元素A，在（a）基礎上用進棧運算PUSH（sq，A），可以得到這種狀態(tài)。此進棧頂指針Top=1。（c）表示在（b）基礎上又有二個B，C先后進棧，此進棧頂指針Top=3。（d）表示在（c）狀態(tài)下棧頂元素C退棧，這可執(zhí)行一次POP（sq）運算得到。此時（新）棧頂指針Top=2。故B為當前的棧頂元素（注意，數(shù)據(jù)元素C雖并未"擦去"，但已不起作用）。（e）表示棧中有5個元素，這種狀態(tài)可在（d）的基礎上通過連續(xù)執(zhí)行PUSH（sq，D），PUSH（sq，E），PUSH（sq，F(xiàn)）得到。這種狀態(tài)稱為棧滿。如果此時再作進棧運算，由于棧中已無空閑空間，因而發(fā)生“上溢”。12/23/2023第7章程序設計基礎2．隊列（1）隊列的定義包括5種基本運算：隊列初始化INIQUEUE（Q）、入隊列INQUEUE（Q，X）、出隊列OUTQUEUE（Q）、判隊列空EMPTY（Q）、讀隊頭GETHEAD（Q）。（2）隊列的順序實現(xiàn)兩種實現(xiàn)方法，即順序實現(xiàn)和鏈接實現(xiàn)。12/23/2023第7章程序設計基礎7.3.4樹與二叉樹樹的定義樹是n（n>0）個結點的有窮集合，滿足：⑴有且僅有一個稱為根的結點；⑵其余結點分為m(m≥0)個互不相交的非空集合T1，T2，...，Tm，這些集合中的每一個都是一棵樹，稱為根的子樹。12/23/2023第7章程序設計基礎2．二叉樹（1）二叉樹的定義二叉樹是n(n>=0)個結點的有限集，它或為空樹(n=0)，或由一個根結點和兩棵分別稱為左子樹和右子樹，且互不相交的二叉樹構成。（2）二叉樹的特點每個結點至多有二棵子樹(即不存在度大于2的結點)；二叉樹的子樹有左、右之分，且其次序不能任意顛倒。12/23/2023第7章程序設計基礎（3）滿二叉樹和完全二叉樹滿二叉樹：除最后一層外，每一層上的所有結點都有兩個子結點。特點：每一層上的結點數(shù)都是最大結點數(shù)，第ｋ層上有2k-1個結點；深度為ｍ的滿二叉樹有2m-1個結點。完全二叉樹：除最后一層外，每一層上的結點數(shù)均達到最大值；在最后一層上只缺少右邊的若干結點。特點：葉子結點只可能在層次最大的兩層上出現(xiàn)；對任一結點，若其右分支下子孫的最大層次為L，則其左分支下子孫的最大層次必為L或L+1。12/23/2023第7章程序設計基礎（4）二叉樹的主要性質(zhì)①在二叉樹的第i層上至多有2i-1個結點。(i≥1)②深度為k的二叉樹上至多含2k-1個結點（k≥1）。③對任何一棵二叉樹，度為0的葉子結點總是比度為2的結點多一個，則必存在關系式：n0=n2+1。12/23/2023第7章程序設計基礎（5）二叉樹的遍歷二叉樹的遍歷有三種方式，如下：①前序遍歷（DLR），首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。簡記根-左-右。②中序遍歷（LDR），首先遍歷左子樹，然后訪問根結點，最后右子樹。簡記左-根-右。③后序遍歷（LRD），首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。簡記左-右-根。12/23/2023第7章程序設計基礎7.4思維與算法7.4.1計算思維的內(nèi)容7.4.2計算思維的特性7.4.3算法的思想7.4.4算法的概念和復雜度7.4.5查找技術12/23/2023第7章程序設計基礎7.4.1計算思維的內(nèi)容計算思維是一種遞歸思維它是并行處理。它是把代碼譯成數(shù)據(jù)又把數(shù)據(jù)譯成代碼。它是由廣義量綱分析進行的類型檢查。對于別名或賦予人與物多個名字的做法，它既知道其益處又了解其害處。對于間接尋址和程序調(diào)用的方法，它既知道其威力又了解其代價。它評價一個程序時，不僅僅根據(jù)其準確性和效率，還有美學的考量，而對于系統(tǒng)的設計，還考慮簡潔和優(yōu)雅。12/23/2023第7章程序設計基礎7.4.2計算思維的特性1．根本的，不是刻板的技能2．是人的，不是計算機的思維方式3．數(shù)學和工程思維的互補與融合4．是思想，不是人造物12/23/2023第7章程序設計基礎7.4.3算法的思想算法的基本思想就是我們分析問題時的想法。由于想法不同思考的角度不同，著手點不一樣，同一問題存在不同的算法，算法有優(yōu)劣之分。從熟悉的問題出發(fā)，體會算法的程序化思想，學會用自然語言來描述算法。算法的特征包括：有窮性確切性輸入輸出可行性12/23/2023第7章程序設計基礎7.4.4算法的概念和復雜度算法的定義廣義地說，算法就是為解決問題而采取的步驟和方法，在程序設計中，算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的指令序列，通俗的講算法，就是計算機解題的過程。每條指令表示一個或多個操作。在這個過程中，無論是形成解題思路還是編寫程序，都是在實施某種算法，前者是算法實現(xiàn)的邏輯推理，后者是算法實現(xiàn)的具體操作。算法的表示為了表示一個算法，可以用多種不同的應運實現(xiàn)。常用的有自然語言，傳統(tǒng)流程圖，結構化流程圖，N-S圖，偽代碼，計算機語言表示法等。12/23/2023第7章程序設計基礎算法的時間復雜度分析算法運算時間的度量事后統(tǒng)計方法事前分析估算方法算法運行時間的分析規(guī)則算法的空間復雜度分析空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度。算法在計算機存儲器內(nèi)占用的存儲空間主要分為三部分：算法源代碼本身占用的存儲空間、算法輸入輸出數(shù)據(jù)所占用的存儲空間和算法運行過程中臨時占用的存儲空間。12/23/2023第7章程序設計基礎7.4.5查找技術1．順序查找一般是在線性表中查找指定的元素?；静僮鞣椒ㄊ牵簭木€性表的第一個元素開始，與被查元素進行比較，相等則查找成功，否則繼續(xù)向后查找。如果所有的元素均查找完畢后都不相等，則該元素在指定的線性表中不存在。順序查找的最好情況是要查找的元素在線性表的第一個元素，則查找效率最高；最差情況是如果要查找的元素在線性表的最后或根本不存在，則查找需要搜索所有的線性表元素。12/23/2023第7章程序設計基礎【例7-1】現(xiàn)有線性表：7、2、1、5、9、4，要在序列中查找元素6，查找的過程是：整個線性表的長度為5查找計次n=1，將元素6與序列的第一個7元素進行比較，不等，繼續(xù)查找n=2，將6與第二個元素2進行比較，不等，繼續(xù)n=3，將6與第三個元素1進行比較，不等，繼續(xù)n=4，將6與第四個元素5進行比較，不等，繼續(xù)n=5，將6與第五個元素9進行比較，不等，繼續(xù)n=6，將6與第六個元素4進行比較，不等，繼續(xù)n=7，超出線性表的長度，查找結束，則該表中不存在要查找的元素。12/23/2023第7章程序設計基礎2．二分查找二分查找只適用于順序存儲的有序表。此處所述的有序表是指線性中的元素按值非遞減排列（即由小到大，但允許相鄰元素值相等）。二分查找的過程如下：將要查找的元素與有序序列的中間元素進行比較：如果該元素比中間元素大，則繼續(xù)在線性表的后半部分（中間項以后的部分）進行查找；如果要查找的元素的值比中間元素的值小，則繼續(xù)在線性表的前半部分（中間項以前的部分）進行查找。這個查找過程一直按相同的順序進行下去，一直到查找成功或子表長度為0（說明線性表中沒有要查找的元素）。12/23/2023第7章程序設計基礎【例7-2】有非遞減有序線性表：1、2、4、5、7、9，要查找元素6。二分查找的過程：序列長度為n=6，中間元素的序號m=[(n+1)/2]=3查找計次k=1，將元素6與中間元素即元素4進行比較，不等，6>4查找計次k=2，查找繼續(xù)在后半部分進行，后半部分子表的長度為3，計算中間元素的序號：m=3+[(3+1)/2]=5，將元素與后半部分的中間項進行比較，即第5個元素中的7進行比較，不等，6<7查找計次k=3，繼續(xù)查找在后半部分序列的前半部分子序列中查找，子表長度為1，則中間項序號即為m=3+[(1+1)/2]=4，即與第4個元素5進行比較，不相等，繼續(xù)查找的子表長度為0，則查找結束。12/23/2023第7章程序設計基礎7.4.6排序技術1．交換類排序法交換類排序法，即是借助于數(shù)據(jù)元素之間的互相交換進行排序的方法。（1）冒泡排序法冒泡排序法即是利用相鄰數(shù)據(jù)元素之間的交換逐步將線性表變成有序序列的操作方法。操作過程如下所述：從表頭開始掃描線性表，在掃描過程中逐次比較相鄰兩個元素的大小，若相鄰兩個元素中前一個元素的值比后一個元素的值大，將兩個元素位置進行交換，當掃描完成一遍時，則序列中最大的元素被放置到序列的最后。再繼續(xù)對序列從頭進行掃描，這一次掃描的長度是序列長度減1，因為最大的元素已經(jīng)就位了，采用與前相同的方法，兩兩之間進行比較，將次大數(shù)移到子序列的末尾。按相同的方法繼續(xù)掃描，每次掃描的子序列的長度均比上一次減1，直至子序列的長度為1時，排序結束。12/23/2023第7章程序設計基礎【例7-3】有序列5、2、9、4、1、7、6，將該序列從小到大進行排列。采用冒泡排序法，具體操作步驟如下：序列長度n=7，如下圖7-12所示。12/23/2023第7章程序設計基礎2．插入類排序法（1）簡單插入排序插入排序，是指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中。插入排序操作的思路：在線性表中，只包含1個元素的子表，作為該有序表。從線性表的第2個元素開始直到最后一個元素，逐次將其中的每一個元素插入到前面的有序的子表中。該方法與冒泡排序方法的效率相同，最壞的情況下需要n(n-1)/2次比較。12/23/2023第7章程序設計基礎例如，有序列5、2、9、4、1、7、6，將該序列從小到大進行排列。采用簡單插入排序法，具體操作步驟如下：序列長度n=7，如圖7-13所示。12/23/2023第7章程序設計基礎（2）希爾排序法希爾排序法的基本思想：將整個無序序列分割成若干小的子序列分別進行插入排序。子序列的分割方法：將相隔某個增量h的元素構成一個子序列，在排序的過程中，逐次減小這個增量，最后當h減小到1時，再進行一次插入排序操作，即完成排序。增量序列一般取ht=n/2k(k=1,2,…,[log2n])，其中n為待排序序列的長度。12/23/2023第7章程序設計基礎（3）選擇類排序法①簡單選擇排序法基本思路：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面，然后對后面的子表采用相同的方法，直到子表為空為止。對于長度為n的序列，需要掃描n-1次，每一次掃描均找出剩余的子表中最小的元素，然后將該最小元素與子表的第一個元素進行交換。【例7-4】有序列5、2、9、4、1、7、6，將該序列從小到大進行排列。采用簡單選擇排序法，具體操作步驟如圖7-14所示：12/23/2023第7章程序設計基礎②堆排序法堆排序法屬于選擇類排序方法。堆的定義：具有n個元素的序列（h1,h2,…,hn），當且僅當滿足時稱之為堆。本節(jié)只討論滿足前者條件的堆。由堆的定義看，堆頂元素（即第一個元素）必為最大項。可以用一維數(shù)組或完全二叉樹來表示堆的結構。用完全二叉樹表示堆時，樹中所有非葉子結點值均不小于其左右子樹的根結點的值，因此堆頂（完全二叉樹的根結點）元素必須為序列的n個元素中的最大項。12/23/2023第7章程序設計基礎【例7-5】有序列5、2、9、4、1、7、6，將該序列從小到大進行排列。利用堆排序法將該序列進行排序。操作方式即：先將無序堆的根結點5與左右子樹的根結點2、9進行比較，5<9，將5與9進行交換；整后，對左右子樹進行堆調(diào)整，左子樹的根結點2小于其左葉子結點5，調(diào)整；右子樹的根結點5小于其左右子結點7和6，根據(jù)堆的要求，將5與7進行調(diào)整。如圖7-15所示。根據(jù)堆的定義，可以得到堆排序的方法：首先將一個無序序列建成堆然后將堆頂元素（序列中的最大項）與堆中最后一個元素交換（最大項應該在序列的最后）。無序堆調(diào)整根結點調(diào)整子樹的根節(jié)點12/23/2023第7章程序設計基礎7.5數(shù)據(jù)庫設計基礎7.5.1數(shù)據(jù)系統(tǒng)的基本概念7.5.2數(shù)據(jù)模型7.5.3關系代數(shù)7.5.4數(shù)據(jù)庫設計與管理12/23/2023第7章程序設計基礎7.5.1數(shù)據(jù)系統(tǒng)的基本概念數(shù)據(jù)、數(shù)據(jù)庫、數(shù)據(jù)庫系統(tǒng)和數(shù)據(jù)庫管理系統(tǒng)是與數(shù)據(jù)庫技術密切相關的四個基本概念。數(shù)據(jù)數(shù)據(jù)是描述事物的符號記錄。數(shù)據(jù)與其語義是不可分的數(shù)據(jù)庫所謂數(shù)據(jù)庫就是長期儲存在計算機內(nèi)、有組織的、可共享的數(shù)據(jù)集合。數(shù)據(jù)庫中的數(shù)據(jù)按一定的數(shù)據(jù)模型組織、描述和儲存，具有較小的冗余度，較高的數(shù)據(jù)獨立性和易擴展性，并可為各種用戶共享。12/23/2023第7章程序設計基礎數(shù)據(jù)庫管理系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)使用戶能方便地定義數(shù)據(jù)和操縱數(shù)據(jù)，并能夠保證數(shù)據(jù)的安全性、完整性，多用戶對數(shù)據(jù)的并發(fā)使用及發(fā)生故障后的系統(tǒng)恢復。數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)庫系統(tǒng)是指在計算機系統(tǒng)中引入數(shù)據(jù)厙后的系統(tǒng)構成，一般由數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)(及其開發(fā)工具)、應用系統(tǒng)、數(shù)據(jù)庫管理員和用戶構成。應當指出的是，數(shù)據(jù)庫的建立、使用和維護等工作只靠一個DBMS遠遠不夠，還要有專門人員來完成，這些人稱為數(shù)據(jù)庫管理員(databaseadministrator。簡稱DBA)。12/23/2023第7章程序設計基礎2．數(shù)據(jù)庫系統(tǒng)的發(fā)展數(shù)據(jù)庫系統(tǒng)的發(fā)展人工管理文件系統(tǒng)數(shù)據(jù)庫系統(tǒng)背景應用背景科學計算科學計算、管理大規(guī)模管理硬件背景無直接存取存儲設備磁盤、磁鼓大容量磁盤軟件背景沒有操作系統(tǒng)有文件系統(tǒng)有數(shù)據(jù)庫管理系統(tǒng)處理方式批處理聯(lián)機實時處理、批處理聯(lián)機實時處理、分布處理、批處理特點數(shù)據(jù)的管理者人文件系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)數(shù)據(jù)面向的對象某一應用程序某一應用程序整個問題域數(shù)據(jù)的共享程度無共享，冗余度極大共享性差，冗余度大共享性高，冗余度小數(shù)據(jù)的獨立性不獨立，完全依賴于程序獨立性差具有高度的物理獨立性和邏輯獨立性數(shù)據(jù)的結構化無結構文件內(nèi)部有結構，整體無結構整體結構化，用數(shù)據(jù)模型描述數(shù)據(jù)控制能力應用程序自己控制應用程序自己控制由數(shù)據(jù)庫管理系統(tǒng)提供數(shù)據(jù)安全性、完整性、并發(fā)控制和恢復能力12/23/2023第7章程序設計基礎3．數(shù)據(jù)庫系統(tǒng)的體系結構從數(shù)據(jù)庫管理系統(tǒng)角度看，數(shù)據(jù)庫系統(tǒng)通常采用三級模式結構；從數(shù)據(jù)庫最終用戶角度看，數(shù)據(jù)庫系統(tǒng)的結構分為單用戶結構、主從式結構、分布式結構和客戶／服務器結構。（1）數(shù)據(jù)庫系統(tǒng)的模式結構數(shù)據(jù)庫系統(tǒng)的三級模式結構是指數(shù)據(jù)庫系統(tǒng)是由外模式、模式和內(nèi)模式三級構成12/23/2023第7章程序設計基礎（2）數(shù)據(jù)庫系統(tǒng)的特點數(shù)據(jù)的獨立性一般分為物理獨立性與邏輯獨立性兩種。①物理獨立性：當數(shù)據(jù)的物理結構（包括存儲結構、存取方式等）改變時，如存儲設備的更換、物理存儲的更換、存取方式改變等，應用程序都不用改變。②邏輯獨立性：數(shù)據(jù)的邏輯結構改變了，如修改數(shù)據(jù)模式、增加新的數(shù)據(jù)類型、改變數(shù)據(jù)間聯(lián)系等，用戶程序都可以不變。12/23/2023第7章程序設計基礎（3）數(shù)據(jù)庫系統(tǒng)的體系結構從數(shù)據(jù)庫管理系統(tǒng)角度來看，數(shù)據(jù)庫系統(tǒng)是一個三級模式結構，但數(shù)據(jù)庫的這種模式結構對最終用戶和程序員是透明的，他們見到的僅是數(shù)據(jù)庫的外模式和應用程序。從最終用戶角度來看，數(shù)據(jù)庫系統(tǒng)分為單用戶結構、主從式結構、分布式結構和客戶／服務器結構。12/23/2023第7章程序設計基礎單用戶數(shù)據(jù)庫系統(tǒng)主從式數(shù)據(jù)庫系統(tǒng)分布式數(shù)據(jù)庫系統(tǒng)客戶／服務器結構的數(shù)據(jù)庫系統(tǒng)12/23/2023第7章程序設計基礎7.5.2數(shù)據(jù)模型數(shù)據(jù)模型及其三要素數(shù)據(jù)模型通常由數(shù)據(jù)結構、數(shù)據(jù)操作和數(shù)據(jù)的完整性約束三部分組成。數(shù)據(jù)結構數(shù)據(jù)結構是研究存儲在數(shù)據(jù)庫中的對象類型的集合，這些對象類型是數(shù)據(jù)庫的組成部分。數(shù)據(jù)操作數(shù)據(jù)操作是指對數(shù)據(jù)庫中各種對象的實例允許執(zhí)行的操作的集合，包括操作和有關的操作的規(guī)則。數(shù)據(jù)的完整性約束數(shù)據(jù)的約束條件是完整性規(guī)則的集合，用以限定符合數(shù)據(jù)模型的數(shù)據(jù)庫狀態(tài)以及狀態(tài)的變化，以保證數(shù)據(jù)的正確、有效和相容。數(shù)據(jù)模型中的數(shù)據(jù)及其聯(lián)系都要遵循完整性規(guī)則的制約。12/23/2023第7章程序設計基礎7.5.3關系代數(shù)關系代數(shù)用到的運算符有：集合運算符：∪(并)、一(差)、∩(交)、×(廣義笛卡爾積)專門的關系運算符：

(選擇)、П(投影)、∞(連接)、÷(除)算數(shù)比較符

={>，≥，<，≤，=，≠}邏輯運算符：邏輯“與”(and)運算符∧、邏輯“或”(or)運算符∨和邏輯“非”(not)運算符--

。12/23/2023第7章程序設計基礎1．傳統(tǒng)的集合運算傳統(tǒng)的集合運算都是二目運算。設關系R和關系S具有相同的目n=3，即有相同的屬性個數(shù)3，且相應的屬性取自同一個域，如表7-2和表7-3所示。則傳統(tǒng)的集合運算如圖7-22所示。圖7-22傳統(tǒng)的集合運算12/23/2023第7章程序設計基礎（1）并(Union)運算設關系R和關系S具有相同的目n(即兩個關系都有n個屬性)，且相應的屬性取自同一個域，則關系R與關系S的并由屬于R或屬于S的元組組成。其結果關系仍為n目關系。記作：R∪S={t|t∈R∨t∈S}其中t代表元組。【例7-6】利用表7-2和表7-3中所示的數(shù)據(jù)做并運算，得到的結果如表7-4所示。12/23/2023第7章程序設計基礎（2）差(Difference)運算設關系R和關系S具有相同的目n，且相應的屬性取自同一個域，則關系R與關系S的差由屬于R而不屬于S的所有元組組成。其結果關系仍為n目關系。記作：R-S={t|t∈R∧t∈S}【例7-7】利用表7-2和表7-3中所示的數(shù)據(jù)做差運算，得到的結果如表7-5所示

12/23/2023第7章程序設計基礎（3）交(Intersection)運算設關系R和關系S具有相同的目n，且相應的屬性取自同一個域，則關系R與關系S的交由既屬于R又屬于S的元組組成。其結果關系仍為n目關系。記作：R∩S={t|t∈R∧t∈S}【例7-8】利用表7-2和表7-3中所示的數(shù)據(jù)做交運算，得到的結果如表7-6所示。關系的交運算可以用差運算表示：R∩S=R-(R-S)12/23/2023第7章程序設計基礎（4）廣義笛卡爾乘積(ExtendedCartesianproduct)關系R為n目，關系S為m目，則關系R和關系S的廣義笛卡爾積為(n+m)元組的集合，記作：R×S={trts|tr∈R∧ts∈S}元組的前n個分量是關系R的一個元組，后m個分量是關系S的一個元組。【例7-9】利用表7-2和表7-3中所示的數(shù)據(jù)做廣義笛卡爾積，其結果如表7-7所示。12/23/2023第7章程序設計基礎專門的關系運算專門的關系運算包括選擇運算、投影運算、連接運算、除運算等。（1）選擇(Selection)運算選擇運算又稱為限制運算(Restriction)，選擇運算是關系上的一元運算，簡記為SL，它根據(jù)給定的條件對關系進行水平分解，在關系R中選擇滿足條件的元組組成一個新的關系。這個關系是關系R的一個子集，如果選擇條件用F表示，則選擇可以記為

F(R)或SLF(R)，記作：

F(R)={t|t∈R∧F(t)=‘TRUE’}其中：

表示選擇運算符，R是關系名，F(xiàn)是選擇條件。說明：F是一個邏輯表達式，取值為“真”或“假”；F由邏輯運算符∧(and)、∨(or)、

(not)連接各種算術表達式組成；算術表達式的基本形式為x

Y，

={>，≥，<，≤，=，≠}，x、y可以是屬性名、常量或簡單函數(shù)。表達式既可用屬性名構造，也可用序列號構造。12/23/2023第7章程序設計基礎【例7-10】如條件F為A=a，用表6-5中所示的數(shù)據(jù)作選擇運算

A=a(R)，其結果如表7-8所示?！纠?-11】如條件F為B=2，用表6-5中所示的數(shù)據(jù)作選擇運算

B=2(R)，其結果如表7-9所示。12/23/2023第7章程序設計基礎（2）投影(Projection)運算投影也是關系上的一元運算，簡記為PJ，它是從列的角度進行操作的。設R是一個n目關系，Ai1、Ai2、Ai3、…、Aim是R的第i1、i2、i3、…、im(m≤n)個屬性，關系R在Ai1、Ai2、Ai3、…、Aim上的投影定義為：пi1、i2、i3、…、im(R)={t|t=(ti1、ti2、ti3、…、tim)∧(ti1、ti2、ti3、…、tim∈R)即從關系R中按照i1、i2、i3、…、im的順序取下這m列，構成以i1、i2、i3、…、im為順序的m目關系。其中：n是投影運算符。投影后不僅取消了原關系中的某些列，而且還可能取消某些元組，因為取消某些列后，可能出現(xiàn)重復的元組，應消去這些完全相同的元組。若對表7-2中的關系R作投影運算ПAB、ПBC，其結果如表7-10、表7-11所示12/23/2023第7章程序設計基礎（3）連接(Join)運算連接運算簡記JN，也稱為∞，連接它是從兩個關系的笛卡爾積中選取屬性間滿足一定條件的元組。記為R∞S=

R.A

S.B(R×S)，或A

B。其中A和B分別為R和S上度數(shù)相等且可比的屬性組。

是比較運算符，

可以是>，≥，<，≤，=，≠等符號。連接運算從R和S的笛卡爾積R×S中選取(R關系)在A屬性組上的值與(S關系)在B屬性組上值滿足比較關系

的元組，這些元組構成的關系是R×S的一個子集。

為“=”的連接運算稱為等值連接。它是從關系R與S的笛卡爾積中選取A、B屬性值相等的那些元組。即等值連接為：R∞S，或(R)JNR.C=S.C(S)，如表7-12和7-13所示。12/23/2023第7章程序設計基礎【例7-13】利用表7-12、表7-13中的數(shù)據(jù)做關系R與S的等值連接R∞S，得到的新關系如表7-14所示。除等值連接外，其余的都可稱為不等值連接。12/23/2023第7章程序設計基礎【例7-14】再看一個不等值連接的例子。利用表7-12、表7-13中的數(shù)據(jù)進行(R)JNR.B>T.B(S)運算，其結果如表7-15所示：12/23/2023第7章程序設計基礎（4）自然連接(NaturalJoin)運算自然連接是最常用的連接之一，簡記為NJN，它是指從兩個關系的笛卡爾積中選擇出公共屬性值相等的元組所構成的新的關系。下面看一下從笛卡爾積的角度定義的自然連接。定義：設關系R和關系S具有相同的屬性集U，U={Al，A2，…Ak}從關系R和關系S的笛卡爾積中，取滿足ПR.U=ПS.U的所有元組，且去掉S.Al、S.A2、．．．、S.Ak，所得的新關系R∞S=Пil，i2，i3，．．，ik(

R.Al=S.A1∧R.A2=S.A2∧…∧R.Ak=S.Ak(R×S))記為關系R和關系S的自然連接，也可簡記為(R)NJN(S)。12/23/2023第7章程序設計基礎【例7-15】取表7-12、表7-13中關系R和關系S的數(shù)據(jù)，做自然連接(R)NJN(S)，得到的結果如表7-19所示。12/23/2023第7章程序設計基礎7.5.4數(shù)據(jù)庫設計與管理1．數(shù)據(jù)庫設計概述數(shù)據(jù)庫設計的兩種方法：面向數(shù)據(jù)的方法：以信息需求為主，兼顧處理需求。面向過程的方法：以處理需求為主，兼顧信息需求。數(shù)據(jù)庫設計一般采用生命周期法，分為如下幾個階段：需求分析階、段概念設計階、段邏輯設計階段、物理設計階段、編碼階段、測試階段、運行階段、進一步修改階段。12/23/2023第7章程序設計基礎2.數(shù)據(jù)庫設計的需求分析第一階段：需求收集和分析，收集基本數(shù)據(jù)和數(shù)據(jù)流圖。主要的任務是：通過詳細調(diào)查現(xiàn)實世界要處理的對象（組織、部門、企業(yè)等），充分了解原系統(tǒng)的工作概況，明確用戶的各種需求，在此基礎上確定新系統(tǒng)的功能。對數(shù)據(jù)庫的要求包括：信息要求、處理要求、安全性和完整性的要求。數(shù)據(jù)字典是各類數(shù)據(jù)的集合，它包括五個部分：數(shù)據(jù)項，即數(shù)據(jù)的最小單位數(shù)據(jù)結構，是若干數(shù)據(jù)項有意義的集合數(shù)據(jù)流，可以是數(shù)據(jù)項，也可以是數(shù)據(jù)結構，用來表示某一處理過程的輸入或輸出數(shù)據(jù)存儲，處理過程中存取的數(shù)據(jù)，通常是手工憑證、手工文檔或計算機文件處理過程12/23/2023第7章程序設計基礎3．數(shù)據(jù)庫概念設計（1）概念設計概述①集中