【正文】 　　線性鏈表的基本運(yùn)算　　(1)在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素。在順序存儲(chǔ)的線性表中，插入或刪除數(shù)據(jù)元素時(shí)需要移動(dòng)大量的數(shù)據(jù)元素?！　￡?duì)列及其基本運(yùn)算　　隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。插入、刪除運(yùn)算不方便。　　線性表的順序存儲(chǔ)結(jié)構(gòu)具有兩個(gè)基本特點(diǎn)：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的?！　。ㄗ⑨?）前后件關(guān)系：一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個(gè)數(shù)據(jù)元素之間存在某種關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)?！　。?）對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)?！　。?）算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。　?。?）擁有足夠的情報(bào)?！　∷惴ǖ幕咎卣鳌　。?）可行性。　　四、數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)　?。簲?shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)?！　《?、程序設(shè)計(jì)基礎(chǔ)　　?！　。私怅P(guān)系數(shù)據(jù)庫(kù)的設(shè)計(jì)。　　。　　、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算?！　。傮w設(shè)計(jì)與詳細(xì)設(shè)計(jì)。換句話說(shuō)，算法是對(duì)特定問(wèn)題求解步驟的一種描述。　?。?）有窮性?！　?：綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止?！　。?）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)?！　?）索引存儲(chǔ)：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來(lái)標(biāo)識(shí)結(jié)點(diǎn)的地址?！　?：常見(jiàn)的線性結(jié)構(gòu)有線性表、棧、隊(duì)列和線性鏈表等。線性表中數(shù)據(jù)元素的個(gè)數(shù)稱(chēng)為線性表的長(zhǎng)度?！　。?）順序表的刪除運(yùn)算：在一般情況下，要?jiǎng)h除第i（1≤i≤n）個(gè)元素時(shí)，則要從第i+1個(gè)元素開(kāi)始，直到第n個(gè)元素之間共ni個(gè)元素依次向前移動(dòng)一個(gè)位置?！　＞哂杏洃涀饔谩Ｔ谘h(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，因此，從頭指針front指向的后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間，所有的元素均為隊(duì)列中的元素。另一部分用于存放指針，稱(chēng)為指針域，用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)(即前件或后件)，如下圖所示：　　線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類(lèi)型?！　?4)將一個(gè)線性鏈表按要求進(jìn)行分解。　　與前面所討論的線性鏈表相比，循環(huán)鏈表具有以下兩個(gè)特點(diǎn)：1)在鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來(lái)設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)，而循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。　　注釋2：在鏈表中，即使知道被訪問(wèn)結(jié)點(diǎn)的序號(hào)i，也不能像順序表中那樣直接按序號(hào)i訪問(wèn)結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順著鏈域逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第i個(gè)結(jié)點(diǎn)為止?！　≡跇?shù)結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱(chēng)為樹(shù)的度?！　⊥耆鏄?shù)：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值?！　、廴?k+1≤n，則編號(hào)為k的右子結(jié)點(diǎn)編號(hào)為2k+1。二叉樹(shù)的遍歷可以分為以下三種：　　(1)前序遍歷(DLR)：若二叉樹(shù)為空，則結(jié)束返回?！　∽⑨?：這樣，不僅節(jié)省了存儲(chǔ)空間，又能方便地確定每一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)與左右子結(jié)點(diǎn)的位置，但順序存儲(chǔ)結(jié)構(gòu)對(duì)于一般的二叉樹(shù)不適用?！　∠铝袃煞N情況下只能采用順序查找：　　1）如果線性表是無(wú)序表（即表中的元素是無(wú)序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。對(duì)于無(wú)序線性表和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能用順序查找?！〉诙驴键c(diǎn)　 程序設(shè)計(jì)風(fēng)格 　　程序設(shè)計(jì)的風(fēng)格主要強(qiáng)調(diào)：“清晰第一，效率第二”（注釋1）。　　3）視覺(jué)組織?！　∽⑨?：“清晰第一，效率第二” 是當(dāng)今主導(dǎo)的程序設(shè)計(jì)風(fēng)格。對(duì)復(fù)雜問(wèn)題，應(yīng)設(shè)計(jì)一些子目標(biāo)作過(guò)渡，逐步細(xì)化?！　?）選擇結(jié)構(gòu)?！　?：面向?qū)ο蟮某绦蛟O(shè)計(jì)主要考慮的是提高軟件的可重用性。　　對(duì)象的基本特點(diǎn)：標(biāo)識(shí)惟一性，分類(lèi)性，多態(tài)性，封裝性，模塊獨(dú)立性好。從外面看只能看到對(duì)象的外部特性，即只需知道數(shù)據(jù)的取值范圍和可以對(duì)該數(shù)據(jù)施加的操作，根本無(wú)需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法。所以類(lèi)是對(duì)象的抽象，對(duì)象是對(duì)應(yīng)類(lèi)的一個(gè)實(shí)例。　　多態(tài)性是指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)的現(xiàn)象。具體的說(shuō)，在軟件開(kāi)發(fā)和維護(hù)過(guò)程中，軟件危機(jī)主要表現(xiàn)在：　　1）軟件需求的增長(zhǎng)得不到滿足。　　總之，可以將軟件危機(jī)可以歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問(wèn)題。　　軟件生命周期分為軟件定義、軟件開(kāi)發(fā)及軟件運(yùn)行維護(hù)三個(gè)階段：　　1）軟件定義階段：包括制定計(jì)劃和需求分析?！　≤浖こ痰哪繕?biāo)和與原則　?。?）軟件工程目標(biāo)：在給定成本、進(jìn)度的前提下，開(kāi)發(fā)出具有有效性、可靠性、可理解性、　　可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶(hù)需求的產(chǎn)品?！　?）確定性：軟件開(kāi)發(fā)過(guò)程中所有概念的表達(dá)應(yīng)是確定、無(wú)歧義且規(guī)范的?！　∮?jì)算機(jī)輔助軟件工程（CASE，Computer Aided Software Engineering）將各種軟件工具、開(kāi)發(fā)機(jī)器和一個(gè)存放開(kāi)發(fā)過(guò)程信息的中心數(shù)據(jù)庫(kù)組合起來(lái)，形成軟件工程環(huán)境?！　?：需求分析一般分為需求獲取、需求分析、編寫(xiě)需求規(guī)格說(shuō)明書(shū)和需求評(píng)審四個(gè)步驟進(jìn)行?！　≡?，潭：表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實(shí)體?！　〗Y(jié)構(gòu)設(shè)計(jì)：定義軟件系統(tǒng)各主要部件之間的關(guān)系?！　?）抽象?！　?：模塊分解的主要指導(dǎo)思想是信息隱蔽和模塊獨(dú)立性?！　】傮w設(shè)計(jì)（概要設(shè)計(jì)）和詳細(xì)設(shè)計(jì)　?。?）總體設(shè)計(jì)（概要設(shè)計(jì)）　　軟件概要設(shè)計(jì)的基本任務(wù)是：1）設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)；2）數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)；3）編寫(xiě)概要設(shè)計(jì)文檔；4）概要設(shè)計(jì)文檔評(píng)審?！　∽儞Q模塊：從上級(jí)模塊取得數(shù)據(jù)，進(jìn)行特定的處理，轉(zhuǎn)換成其他形式，再傳送給上級(jí)模塊?！　∶嫦驍?shù)據(jù)流的設(shè)計(jì)方法定義了一些不同的映射方法，利用這些方法可以把數(shù)據(jù)流圖變換成結(jié)構(gòu)圖表示軟件的結(jié)構(gòu)。　　表格工具：判定表。不實(shí)際運(yùn)行軟件，主要通過(guò)人工進(jìn)行。通常程序中的邏輯表示有判斷、分支、條件等幾種表示方法。其思想和步驟是，根據(jù)軟件過(guò)程性描述中的控制流程確定程序的環(huán)路復(fù)雜性度量，用此度量定義基本路徑集合，并由此導(dǎo)出一組測(cè)試用例，對(duì)每一條獨(dú)立執(zhí)行路徑進(jìn)行測(cè)試。它是對(duì)各種輸入、輸出范圍的邊界情況設(shè)計(jì)測(cè)試用例的方法?！　卧獪y(cè)試的內(nèi)容包括：模塊接口測(cè)試、局部數(shù)據(jù)結(jié)構(gòu)測(cè)試、錯(cuò)誤處理測(cè)試和邊界測(cè)試。首先對(duì)每個(gè)模塊分別進(jìn)行模塊測(cè)試，然后再把所有模塊組裝在一起進(jìn)行測(cè)試，最終得到要求的軟件系統(tǒng)?！　。?）系統(tǒng)測(cè)試　　系統(tǒng)測(cè)試的目的在于通過(guò)與系統(tǒng)的需求定義進(jìn)行比較，發(fā)現(xiàn)軟件與系統(tǒng)定義不符合或與之矛盾的地方。靜態(tài)調(diào)試主要是指通過(guò)人的思維來(lái)分析源程序代碼和排錯(cuò)，是主要的調(diào)試手段，而動(dòng)態(tài)調(diào)試是輔助靜態(tài)調(diào)試。　　1）演繹法?！　”菊聭?yīng)考點(diǎn)撥：本章在筆試中一般占8分左右，約3道選擇題，1道填空題，是公共基礎(chǔ)部分比較重要的一章?！　。?）數(shù)據(jù)庫(kù)（DB）：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲(chǔ)介質(zhì)內(nèi)，是多種應(yīng)用數(shù)據(jù)的集成，并可被各個(gè)應(yīng)用程序所共享。數(shù)據(jù)庫(kù)管理系統(tǒng)為用戶(hù)使用數(shù)據(jù)庫(kù)中的數(shù)據(jù)提供方便，它一般提供如查詢(xún)、插入、修改以及刪除數(shù)據(jù)的功能。在并發(fā)操作中如果不加控制和管理，多個(gè)應(yīng)用程序間就會(huì)相互干擾，從而對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)造成破壞?！　?：數(shù)據(jù)庫(kù)技術(shù)的根本目標(biāo)是解決數(shù)據(jù)的共享問(wèn)題。　　1）物理獨(dú)立性：物理獨(dú)立性即是數(shù)據(jù)的物理結(jié)構(gòu)（包括存儲(chǔ)結(jié)構(gòu)，存取方式等）的改變，如存儲(chǔ)設(shè)備的更換、物理存儲(chǔ)的更換、存取方式改變等都不影響數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)，從而不致引起應(yīng)用程序的變化?！　?）內(nèi)模式：又稱(chēng)物理模式，它給出了數(shù)據(jù)庫(kù)物理存儲(chǔ)結(jié)構(gòu)與物理存取方法?！　∽⑨?：視圖是從一個(gè)或幾個(gè)基本表（或視圖）導(dǎo)出的表，它與基本表不同，是一個(gè)虛表?！　?）數(shù)據(jù)的約束條件：數(shù)據(jù)的約束條件是一組完整性規(guī)則的集合?！　?）屬性：事物的特性?！　?）實(shí)體集與屬性間的聯(lián)接關(guān)系：用無(wú)向線段表示。每個(gè)屬性有一個(gè)取值范圍稱(chēng)為值域。外部關(guān)鍵字取空值或?yàn)橥獠勘碇袑?duì)應(yīng)的關(guān)鍵字值。實(shí)體集也可以轉(zhuǎn)換成關(guān)系?！　。?）關(guān)系中的數(shù)據(jù)約束：　　1）實(shí)體完整性約束：要求關(guān)系的主鍵中屬性值不能為空值，因?yàn)橹麈I是唯一決定元組的，如為空值則其唯一性就成為不可能的了?！?關(guān)系代數(shù) 　　關(guān)系的數(shù)據(jù)結(jié)構(gòu)　　關(guān)系是由若干個(gè)不同的元組所組成，因此關(guān)系可視為元組的集合。每個(gè)元組的前n列來(lái)自R的一個(gè)元組，后m列來(lái)自S的一個(gè)元組，記為RS?！　?：VFP是一種關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)。本章內(nèi)容概括性強(qiáng)，比較抽象，難于理解，因此建議考生在復(fù)習(xí)的時(shí)候，首先熟讀講義，其次對(duì)數(shù)據(jù)庫(kù)系統(tǒng)的基本概念及原理等知識(shí)要注意理解、加強(qiáng)記憶?！　。?）數(shù)據(jù)庫(kù)設(shè)計(jì)的每個(gè)階段都有各自的任務(wù)：　　1）需求分析階段：這是數(shù)據(jù)庫(kù)設(shè)計(jì)的第一個(gè)階段，任務(wù)主要是收集和分析數(shù)據(jù)，這一階段收集到的基礎(chǔ)數(shù)據(jù)和數(shù)據(jù)流圖是下一步設(shè)計(jì)概念結(jié)構(gòu)的基礎(chǔ)?！　±河袃蓚€(gè)關(guān)系R和S，分別進(jìn)行并、差、交和廣義笛卡爾積運(yùn)算?！　￡P(guān)系模型的基本運(yùn)算：1）插入；2）刪除；3)修改；4）查詢(xún)（包括投影、選擇、笛卡爾積運(yùn)算）?！　?）用戶(hù)定義的完整性約束：反映某一具體應(yīng)用所涉及的數(shù)據(jù)必須滿足的語(yǔ)義要求?！　≈鞔a：或稱(chēng)為關(guān)鍵字、主鍵，簡(jiǎn)稱(chēng)碼、鍵，表中的一個(gè)屬性或幾個(gè)屬性的組合、其值能唯一地標(biāo)識(shí)表中一個(gè)元組的，稱(chēng)為關(guān)系的主碼或關(guān)鍵字?！　。?）關(guān)系中的數(shù)據(jù)約束：　　1）實(shí)體完整性約束：要求關(guān)系的主鍵中屬性值不能為空值，因?yàn)橹麈I是唯一決定元組的，如為空值則其唯一性就成為不可能的了。在表框架中按行可以存放數(shù)據(jù)，每行數(shù)據(jù)稱(chēng)為元組，實(shí)際上，一個(gè)元組是由n個(gè)元組分量所組成，每個(gè)元組分量是表框架中每個(gè)屬性的投影值?！　。?）數(shù)據(jù)庫(kù)管理系統(tǒng)常見(jiàn)的數(shù)據(jù)模型有層次模型（注釋1） 、網(wǎng)狀模型和關(guān)系模型三種。實(shí)體集的關(guān)系有一對(duì)一、一對(duì)多、多對(duì)多的聯(lián)系。　?。?）數(shù)據(jù)模型分為概念模型、邏輯數(shù)據(jù)模型和物理模型三類(lèi)：　　1）概念數(shù)據(jù)模型：簡(jiǎn)稱(chēng)概念模型，是對(duì)客觀世界復(fù)雜事物的結(jié)構(gòu)描述及它們之間的內(nèi)在聯(lián)系的刻畫(huà)。　 數(shù)據(jù)模型 　　數(shù)據(jù)模型　?。?）數(shù)據(jù)模型的概念：是數(shù)據(jù)特征的抽象，它從抽象層次上描述了系統(tǒng)的靜態(tài)特征、動(dòng)態(tài)行為和約束條件，為數(shù)據(jù)庫(kù)系統(tǒng)的信息表示與操作提供一個(gè)抽象的框架。內(nèi)模式對(duì)一般用戶(hù)是透明的，但它的設(shè)計(jì)直接影響數(shù)據(jù)庫(kù)的性能?！　。?）數(shù)據(jù)統(tǒng)一管理與控制?！　∠卤硎菙?shù)據(jù)管理三個(gè)階段的比較： 人工管理階段文件系統(tǒng)階段數(shù)據(jù)庫(kù)系統(tǒng)階段背　　景應(yīng)用背景科學(xué)計(jì)算科學(xué)計(jì)算、管理大規(guī)模管理硬件背景無(wú)直接存取存儲(chǔ)設(shè)備磁盤(pán)、磁鼓大容量磁備盤(pán)軟件背景沒(méi)有操作系統(tǒng)有文件系統(tǒng)有數(shù)據(jù)庫(kù)管理系統(tǒng)處理方式批處理聯(lián)機(jī)實(shí)時(shí)處理、批處理聯(lián)機(jī)實(shí)時(shí)處理、分布處理、批處理特　　點(diǎn)數(shù)據(jù)的管理者用戶(hù)（程序員）文件系統(tǒng)數(shù)據(jù)庫(kù)管理系統(tǒng)數(shù)據(jù)面向的對(duì)象某一應(yīng)用程序某一應(yīng)用現(xiàn)實(shí)世界數(shù)據(jù)的共享程度無(wú)共享，冗余度極大共享性差，冗余度大共享性高，冗余度小數(shù)據(jù)的獨(dú)立性不獨(dú)立，完全依賴(lài)于程序獨(dú)立性差具有高度的物理獨(dú)立性和一定的邏輯獨(dú)立性數(shù)據(jù)的結(jié)構(gòu)化無(wú)結(jié)構(gòu)記錄內(nèi)有結(jié)構(gòu)，整體無(wú)結(jié)構(gòu)整體結(jié)構(gòu)化，用數(shù)據(jù)模型描述數(shù)據(jù)控制能力應(yīng)用程序自己控制應(yīng)用程序自己控制由數(shù)據(jù)庫(kù)管理系統(tǒng)提供數(shù)據(jù)安全性、完整性、并發(fā)控制和恢復(fù)能力　　數(shù)據(jù)庫(kù)系統(tǒng)的基本特點(diǎn)　?。?）數(shù)據(jù)的高集成性。數(shù)據(jù)庫(kù)中的數(shù)據(jù)一旦遭到破壞，數(shù)據(jù)庫(kù)管理系統(tǒng)必須有能力及時(shí)進(jìn)行恢復(fù)，這就是數(shù)據(jù)庫(kù)的故障恢復(fù)。　　4）數(shù)據(jù)的完整性、安生性定義與檢查。　?。?）數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫(kù)中的數(shù)據(jù)組織、數(shù)據(jù)操縱、數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫(kù)的核心?！　∽⑨?：注意與軟件測(cè)試區(qū)分?！　?）歸納法。主要方法有：通過(guò)內(nèi)存全部打印來(lái)排錯(cuò)；在程序特定部位設(shè)置打印語(yǔ)句；自動(dòng)調(diào)試工具?！　∠到y(tǒng)測(cè)試的具體實(shí)施一般包括：功能測(cè)試、性能測(cè)試、操作測(cè)試、配置測(cè)試、外部接