【文章內(nèi)容簡介】 要指： 數(shù)據(jù)庫的實施和維護 分三個步驟： 數(shù)據(jù)的載入和應用程序的調(diào)試 數(shù)據(jù)庫的試運行 數(shù)據(jù)庫的運行和維護 數(shù)據(jù)庫的維護 在數(shù)據(jù)庫運行階段，對數(shù)據(jù)庫經(jīng)常性的維護工作主要是由 DBA完成的。包括： 數(shù)據(jù)庫的存儲和恢復 數(shù)據(jù)庫的安全性、完整性控制 數(shù)據(jù)庫性能的監(jiān)督、分析和改進 數(shù)據(jù)庫的重組織與重構(gòu)造 數(shù)據(jù)結(jié)構(gòu)與算法 ? 算法 ? 數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語 ? 線性表 ? 棧 ? 隊列 ? 樹與二叉樹 ? 查找與排序 算法 ?定義： 是對特定問題求解步驟的一種描述?；蛘哒f，是為求解某問題而設(shè)計的步驟序列 ?特征： 有窮性 確定性 有效性 輸入 輸出 算法復雜度 評價一個算法優(yōu)劣的主要標準是： 算法的執(zhí)行效率與存儲需求 算法的效率： 指的是時間復雜度（ Time Complexity） 存儲需求： 指的是空間復雜度（ Space Complexity ） 一般情況下，算法中的基本操作重復操作執(zhí)行的次數(shù)是問題規(guī)模 n的某個函數(shù) f(n),算法的時間復雜度記做 T(n)=O(f(n)) 數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語 ?數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù) 是描述客觀事物的數(shù)、字符以及所有能輸入到計算機中并被計算機程序加工處理的符號的集合 數(shù)據(jù)元素 是數(shù)據(jù)的基本元素，即數(shù)據(jù)集合中的個體 數(shù)據(jù)項 具有獨立意義的最小數(shù)據(jù)單位 數(shù)據(jù)對象 具有相同特性的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集 結(jié)構(gòu) 被計算機加工的數(shù)據(jù)元素之間存在的關(guān)系 數(shù)據(jù)結(jié)構(gòu) 帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的集合 ?數(shù)據(jù)的邏輯結(jié)構(gòu) ? 集合 ? 線性結(jié)構(gòu) ? 樹形結(jié)構(gòu) ? 圖狀或網(wǎng)狀結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語 ?數(shù)據(jù)的存儲結(jié)構(gòu) 一、順序存儲結(jié)構(gòu) 主要特點： ? 結(jié)點中只有自身信息域，沒有連接信息域，因此存儲密度大，存儲空間利用率高 ? 可以通過計算直接確定數(shù)據(jù)結(jié)構(gòu)中第 i個結(jié)點的存儲地址 Li，計算公式： L0+（ i1） m。（其中L0為第一個結(jié)點的存儲地址， m為每個結(jié)點所占用的存儲單元個數(shù) ? 插入、刪除運算不便，會引起大量結(jié)點的移動 數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語 二、鏈式存儲結(jié)構(gòu) 主要特點： ? 結(jié)點中除自身信息之外，還有表示連接信息的指針域，因此比順序存儲密度小，存儲空間利用率低 ? 邏輯上相鄰的結(jié)點物理上不必鄰接，可用于線性表、樹、圖等多種邏輯結(jié)構(gòu)的存儲表示 ? 插入、刪除操作靈活方便，不必移動結(jié)點，只要改變結(jié)點中的指針值即可 ? 數(shù)據(jù)的運算 ?檢索： 在數(shù)據(jù)結(jié)構(gòu)里查找滿足一定條件的結(jié)點 ?插入： 往數(shù)據(jù)結(jié)構(gòu)里增加新的結(jié)點 ?刪除： 把指定的結(jié)點從數(shù)據(jù)結(jié)構(gòu)里去掉 ?更新： 改變指定結(jié)點的一個或多個域的值 ?排序： 保持線性結(jié)構(gòu)的結(jié)點序列里結(jié)點數(shù)不變，把結(jié)點按某種指定的順序重新排列 數(shù)據(jù)結(jié)構(gòu)的基本概念及術(shù)語 線性表 線性表 是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表的邏輯結(jié)構(gòu)是 n個數(shù)據(jù)元素的有限序列（ a1,a2,…,a n） ? 順序表： 指用順序存儲結(jié)構(gòu)存儲的線性表 ? 鏈表： 用鏈式存儲結(jié)構(gòu)存儲的線性表 ? 棧和隊列 ——是對線性表的插入、刪除運算可以發(fā)生的位置加以限制的兩種特殊的線性表 順序表和一維數(shù)組 各種高級語言里的一維數(shù)組就是用順序方式存儲的線性表，因此常用 一維數(shù)組稱呼順序表 若順序表中結(jié)點個數(shù)為 n，則： 插入 一個結(jié)點平均需要移動之結(jié)點個數(shù)為 n/2，算法的時間復雜度是 O(n)； 刪除 一個結(jié)點平均需移動結(jié)點個數(shù)為（ n1） /2，算法的時間復雜度是 O(n) 鏈 表 線性鏈表（單鏈表）： 刪除算法的時間復雜度為 O(n)，其主要執(zhí)行時間是搜索刪除位置 循環(huán)鏈表： 指鏈表的最后一個結(jié)點的指針值指向第一個結(jié)點，整個鏈表形成一個環(huán)（如下圖） … 結(jié)點 1 結(jié)點 2 結(jié)點 n 棧 棧： 是一種特殊的線性表，是限定僅在表尾進行插入和刪除運算的線性表，表尾稱為棧頂（ top），表頭稱為棧底（ bottom）。 空棧： 指表中無元素 ? 棧中有元素 a1,a2,…,a n，如 下頁圖 所示，稱 a1為棧底元素。新元素進棧要置于 an之上，刪除或退棧先對 an進行，即 “后進先出”（ LIFO） 的操作原則 ? 棧的物理存儲可以用 順序存儲結(jié)構(gòu)或鏈式存儲結(jié)構(gòu) ? 棧的運算還有取棧頂元素，檢查棧是否為空，清除等。 棧的插入和刪除 A B A C B A B A F E B A A TOP TOP TOP TOP TOP TOP an … a2 a1 進棧 出棧 棧底 棧結(jié)構(gòu) (3) (1) (2) (5) (4) (6) 隊列 隊列： 是限定所有的插入都在表的一端進行，所有的刪除都在表的另一端進行的線性表。進行刪除的一端叫 隊列的頭 ，進行插入的一端叫 隊列的尾 ，如 下頁圖 所示。 在隊列中，新元素總是加入到隊尾，每次刪除的總是對頭元素，即當前“最老的”元素，這就是 “先進先出”（ FIFO）的操作原則 隊列的物理存儲可以用： 順序存儲結(jié)構(gòu)，也可用鏈式存儲結(jié)構(gòu) 隊列的示意（如下圖） 出隊列 a1 a2 a3 …an 入隊列 頭 尾 隊列的插入和刪除示例 初態(tài) 插入A 插入B 刪除A 插入C 插入D 刪除B 插入E F R A F R R R R R R F F F F F F B A B B B C C C C D D D 溢出 樹與二叉樹 ?樹形結(jié)構(gòu) 是一類重要的非線性結(jié)構(gòu)，樹和二叉樹是最常見的樹形結(jié)構(gòu) ?樹（ Tree） :是一個或多個結(jié)點組成的有限集合 T，有一個特定的結(jié)點稱為根（ Root），其余的結(jié)點分為 m（ m≥0 ）個不相交的集合 T1， T2， … ， Tm，每個集合又是一棵樹，稱作這個根的子樹（ Subtree) 樹形結(jié)構(gòu)的常用術(shù)語 ? 結(jié)點的度（ Degree）： 一個結(jié)點的子樹的個數(shù) ? 樹的度： 樹中各結(jié)點的度的最大值 ? 樹葉（ Leaf） ： 度為 0的結(jié)點 ? 分支結(jié)點： 度不為 0的結(jié)點 ? 雙親（ Parent）、子女（ Child）： 結(jié)點的各子樹的根稱作該結(jié)點的子女；相應的該結(jié)點稱作其子女的雙親 ? 兄弟（ Sibling）： 具有相同雙親的結(jié)點互為兄弟 ? 結(jié)點的層數(shù)（ Level）樹的深度（ Depth） ? 森林（ Forest） 二 叉 樹 ?二叉樹