【正文】 這一點(diǎn)。為了克服線性鏈表的這個(gè)缺點(diǎn)，可以采用另一種鏈接方式，即循環(huán)鏈表?！　?7)線性鏈表的排序。　　(3)將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表。另一個(gè)稱為右指針，指向其后件結(jié)點(diǎn)，這種鏈表稱為雙向鏈表，如下圖所示：　　線性鏈表的基本運(yùn)算　　(1)在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素。因此，在鏈?zhǔn)酱鎯?chǔ)方式中，每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域。在順序存儲(chǔ)的線性表中，插入或刪除數(shù)據(jù)元素時(shí)需要移動(dòng)大量的數(shù)據(jù)元素?！　⊙h(huán)隊(duì)列及其運(yùn)算：所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。　　隊(duì)列及其基本運(yùn)算　　隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。即棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。插入、刪除運(yùn)算不方便?！　?：順性表的插入運(yùn)算時(shí)需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)n/2個(gè)元素。　　線性表的順序存儲(chǔ)結(jié)構(gòu)具有兩個(gè)基本特點(diǎn)：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。線性表是由n(n≥0)個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件?！　。ㄗ⑨?）前后件關(guān)系：一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個(gè)數(shù)據(jù)元素之間存在某種關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)?！　。?）線性結(jié)構(gòu)（非空的數(shù)據(jù)結(jié)構(gòu)）條件：1）有且只有一個(gè)根結(jié)點(diǎn)（注釋2）；2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前驅(qū)，也最多有一個(gè)后繼?！　。?）對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)?！　?shù)據(jù)的邏輯結(jié)構(gòu)包含：　　1）表示數(shù)據(jù)元素的信息；　　2）表示各數(shù)據(jù)元素之間的前后件關(guān)系（注釋1）?！　。?）算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。一般說來，當(dāng)算法擁有足夠的情報(bào)時(shí)，此算法才是有效的；而當(dāng)提供的情報(bào)不夠時(shí)，算法可能無效。　?。?）擁有足夠的情報(bào)。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出?！　∷惴ǖ幕咎卣鳌　。?）可行性。　　◆ 考試方式　　公共基礎(chǔ)知識(shí)有10道選擇題和5道填空題共三十分　第一章 數(shù)據(jù)結(jié)構(gòu)與算法 　　 算法　　算法是指解題方案的準(zhǔn)確而完整的描述?！　∷?、數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)　?。簲?shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)?！　?，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書?！　《⒊绦蛟O(shè)計(jì)基礎(chǔ)　　。　?。粭：完?duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算?！　。私怅P(guān)系數(shù)據(jù)庫的設(shè)計(jì)?！　　！　　！　　?考試內(nèi)容　　一、基本數(shù)據(jù)結(jié)構(gòu)與算法　??；算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）?！　?、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算?！　?。　　，總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。　　，實(shí)體聯(lián)系模型及ER圖，從ER圖導(dǎo)出關(guān)系數(shù)據(jù)模型。換句話說，算法是對(duì)特定問題求解步驟的一種描述。針對(duì)實(shí)際問題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。　?。?）有窮性。算法中各種運(yùn)算總是要施加到各個(gè)運(yùn)算對(duì)象上，而這些運(yùn)算對(duì)象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點(diǎn)或依據(jù)。　　*：綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止?！　。ㄗ⑨?）這是因?yàn)椋涸诰帉懗绦驎r(shí)要受到計(jì)算機(jī)系統(tǒng)運(yùn)行環(huán)境的限制，程序通常還要考慮很多與方法和分析無關(guān)的細(xì)節(jié)問題。　?。?）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)?！　?）索引存儲(chǔ)：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識(shí)結(jié)點(diǎn)的地址。　　數(shù)據(jù)結(jié)構(gòu)的圖形表示　　一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。　　*：常見的線性結(jié)構(gòu)有線性表、棧、隊(duì)列和線性鏈表等。在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡單地用前后件關(guān)系（即直接前驅(qū)與直接后繼關(guān)系）來描述。線性表中數(shù)據(jù)元素的個(gè)數(shù)稱為線性表的長度。　　*：由此可以看出，在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲(chǔ)空間中是緊鄰的，且前件元素一定存儲(chǔ)在后件元素的前面，可以通過計(jì)算機(jī)直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址。　?。?）順序表的刪除運(yùn)算：在一般情況下，要?jiǎng)h除第i（1≤i≤n）個(gè)元素時(shí)，則要從第i+1個(gè)元素開始，直到第n個(gè)元素之間共ni個(gè)元素依次向前移動(dòng)一個(gè)位置。 棧和隊(duì)列　　棧及其基本運(yùn)算　　棧是限定在一端進(jìn)行插入與刪除運(yùn)算的線性表?！　＞哂杏洃涀饔谩Ｎ仓羔槪≧ear）指向隊(duì)尾元素，頭指針（front）指向排頭元素的前一個(gè)位置（隊(duì)頭）。在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，因此，從頭指針front指向的后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間，所有的元素均為隊(duì)列中的元素。(2)線性表的順序存儲(chǔ)結(jié)構(gòu)下，線性表的存儲(chǔ)空間不便于擴(kuò)充。另一部分用于存放指針，稱為指針域，用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)(即前件或后件)，如下圖所示：　　線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。　　*：在線性鏈表中插入元素時(shí)，不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可，也不會(huì)出現(xiàn)“上溢（注釋1）”現(xiàn)象。　　(4)將一個(gè)線性鏈表按要求進(jìn)行分解。　　(8)線性鏈表的查找?！　∨c前面所討論的線性鏈表相比，循環(huán)鏈表具有以下兩個(gè)特點(diǎn)：1)在鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)，而循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。二是由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，在任何情況下，循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在，從而使空表與非空表的運(yùn)算統(tǒng)一?！　∽⑨?：在鏈表中，即使知道被訪問結(jié)點(diǎn)的序號(hào)i，也不能像順序表中那樣直接按序號(hào)i訪問結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順著鏈域逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第i個(gè)結(jié)點(diǎn)為止?！　≡跇浣Y(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)?！　≡跇浣Y(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度?！　⌒再|(zhì)2 深度為m的二叉樹最多有個(gè)2m1個(gè)結(jié)點(diǎn)?！　⊥耆鏄洌撼詈笠粚油?，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值。　　性質(zhì)6 設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)，如果從根結(jié)點(diǎn)開始，按層序(每一層從左到右)用自然數(shù)1，2，…，n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k(k=1，2，…，n)的結(jié)點(diǎn)有以下結(jié)論：　?、偃鬹=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)?！　、廴?k+1≤n，則編號(hào)為k的右子結(jié)點(diǎn)編號(hào)為2k+1。但在二叉樹中，由于每一個(gè)元素可以有兩個(gè)后件(即兩個(gè)子結(jié)點(diǎn))，因此，用于存儲(chǔ)二叉樹的存儲(chǔ)結(jié)點(diǎn)的指針域有兩個(gè)：一個(gè)用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)地址，稱為左指針域。二叉樹的遍歷可以分為以下三種：　　(1)前序遍歷(DLR)：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹?！　∽⑨?：這樣，不僅節(jié)省了存儲(chǔ)空間，又能方便地確定每一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)與左右子結(jié)點(diǎn)的位置，但順序存儲(chǔ)結(jié)構(gòu)對(duì)于一般的二叉樹不適用?！　№樞虿檎摇　』舅枷耄簭谋碇械牡谝粋€(gè)元素開始，將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行比較，直到兩者相符，查到所要找的元素為止。　　下列兩種情況下只能采用順序查找：　　1）如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。　　查找過程：　　1）若中間項(xiàng)（中間項(xiàng)mid=(n1)/2，mid的值四舍五入取整）的值等于x，則說明已查到；　　2）若x小于中間項(xiàng)的值，則在線性表的前半部分查找；　　3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。對(duì)于無序線性表和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能用順序查找?！　〗粨Q類排序法（方法：冒泡排序，快速排序）?！〉诙驴键c(diǎn)　 程序設(shè)計(jì)風(fēng)格 　　程序設(shè)計(jì)的風(fēng)格主要強(qiáng)調(diào)：“清晰第一，效率第二”（注釋1）?！　?）程序的注釋?！　?）視覺組織?！　。?）語句的結(jié)構(gòu)。　　注釋1：“清晰第一，效率第二” 是當(dāng)今主導(dǎo)的程序設(shè)計(jì)風(fēng)格?！　。?）自頂向下。對(duì)復(fù)雜問題，應(yīng)設(shè)計(jì)一些子目標(biāo)作過渡，逐步細(xì)化?！　。?）限制使用goto語句?！　?）選擇結(jié)構(gòu)?！　H僅使用順序、選擇和循環(huán)三種基本控制結(jié)構(gòu)就足以表達(dá)各種其他形式結(jié)構(gòu)，從而實(shí)現(xiàn)任何單入口/單出口的程序?！　?：面向?qū)ο蟮某绦蛟O(shè)計(jì)主要考慮的是提高軟件的可重用性?！　傩约磳?duì)象所包含的信息，它在設(shè)計(jì)對(duì)象時(shí)確定，一般只能通過執(zhí)行對(duì)象的操作來改變?！　?duì)象的基本特點(diǎn)：標(biāo)識(shí)惟一性，分類性，多態(tài)性，封裝性，模塊獨(dú)立性好。指可以將具有相同屬性的操作的對(duì)象抽象成類。從外面看只能看到對(duì)象的外部特性，即只需知道數(shù)據(jù)的取值范圍和可以對(duì)該數(shù)據(jù)施加的操作，根本無需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法?！　。?）模塊獨(dú)立性好。所以類是對(duì)象的抽象，對(duì)象是對(duì)應(yīng)類的一個(gè)實(shí)例?！　±^承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。　　多態(tài)性是指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)的現(xiàn)象?！?軟件工程基本概念 　　軟件的相關(guān)概念　　計(jì)算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。具體的說，在軟件開發(fā)和維護(hù)過程中，軟件危機(jī)主要表現(xiàn)在：　　1）軟件需求的增長得不到滿足?！　?）軟件質(zhì)量難以保證。　　總之，可以將軟件危機(jī)可以歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問題。　　軟件工程的主要思想是將工程化原則運(yùn)用到軟件開發(fā)過程，它包括3個(gè)要素：方法、工具和過程。　　軟件生命周期分為軟件定義、軟件開發(fā)及軟件運(yùn)行維護(hù)三個(gè)階段：　　1）軟件定義階段：包括制定計(jì)劃和需求分析?！　≤浖?shí)現(xiàn)：把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼?！　≤浖こ痰哪繕?biāo)和與原則　　（1）軟件工程目標(biāo)：在給定成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理解性、　　可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。　　2）信息隱蔽：采用封裝技術(shù)，將程序模塊的實(shí)現(xiàn)細(xì)節(jié)隱蔽起來，使模塊接口盡量簡單?！　?）確定性：軟件開發(fā)過程中所有概念的表達(dá)應(yīng)是確定、無歧義且規(guī)范的?！　≤浖_發(fā)工具與軟件開發(fā)環(huán)境　　(1)軟件開發(fā)工具　　軟件開發(fā)工具的完善和發(fā)展將促使軟件開發(fā)方法的進(jìn)步和完善，促進(jìn)軟件開發(fā)的高速度和高質(zhì)量?！　∮?jì)算機(jī)輔助軟件工程（CASE，Computer Aided Software Engineering）將各種軟件工具、開發(fā)機(jī)器和一個(gè)存放開發(fā)過程信息的中心數(shù)據(jù)庫組合起來，形成軟件工程環(huán)境?！　∽⑨?：許多軟件的開發(fā)和運(yùn)行涉及軟件用戶的機(jī)構(gòu)設(shè)置，體制問題以及管理方式等，甚至涉及到人們的觀念和心理，軟件知識(shí)產(chǎn)權(quán)及法律等問題。　　*：需求分析一般分為需求獲取、需求分析、編寫需求規(guī)格說明書和需求評(píng)審四個(gè)步驟進(jìn)行?！　?shù)據(jù)流圖以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動(dòng)和處理的過程，它反映了系統(tǒng)必須完成的邏輯功能，是結(jié)構(gòu)化分析方法中用于表示系統(tǒng)邏輯模型的一種工具。　　源，潭：表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實(shí)體。　　*：數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。　　結(jié)構(gòu)設(shè)計(jì)：定義軟件系統(tǒng)各主要部件之間的關(guān)系。　　從工程角度來看，軟件設(shè)計(jì)分兩步完成，即概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)?！　?）抽象?！　?）信息隱蔽?！　?：模塊分解的主要指導(dǎo)思想是信息隱蔽和模塊獨(dú)立性?！　●詈闲裕菏悄K間互相連接的緊密程度的度量?！　】傮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ù)庫設(shè)計(jì)；3）編寫概要設(shè)計(jì)文檔；4）概要設(shè)計(jì)文檔評(píng)審。還可用帶實(shí)心圓的箭頭表示傳遞的是控制信息，空心圓箭心表示傳遞的是數(shù)據(jù)信息。　　變換模塊：從上級(jí)模塊取得數(shù)據(jù)，進(jìn)行特定的處理，轉(zhuǎn)換成其他形式，再傳送給上級(jí)模塊。　　寬度：整體控制跨度（最大模塊數(shù)的