目錄全國計算機等級考試一一二級公共基礎知識輔導講義…錯誤！未定義書簽。TOC\o"1-5"\h\z\o"CurrentDocument"第一章數(shù)據(jù)結(jié)構(gòu)與算法 1第二章程序設計基礎 0第三章 軟件工程基礎 5第四章數(shù)據(jù)庫設計基礎 17任課教師：田密作者介紹：田密，男，延安職業(yè)技術學院計算機等級考試二級輔導主講教師。聯(lián)系方式：Email：tianmizr@126.comQQ：6009265歡迎大家多多與我交流，提出你們對課程的意見和建議！全國計算機等級考試一二級公共基礎知識輔導講義第一章數(shù)據(jù)結(jié)構(gòu)與算法算法1、算法是指解題方案的準確而完整的描述。換句話說，算法是對特定問題求解步驟的一種描述。*:算法不等于程序，也不等于計算方法。程序的編制不可能優(yōu)于算法的設計。2、算法的基本特征（1）可行性。針對實際問題而設計的算法，執(zhí)行后能夠得到滿意的結(jié)果。（2）確定性。每一條指令的含義明確，無二義性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。（3）有窮性。算法必須在有限的時間內(nèi)完成。有兩重含義，一是算法中的操作步驟為有限個，二是每個步驟都能在有限時間內(nèi)完成。（4）擁有足夠的情報。算法中各種運算總是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點或依據(jù)。因此，一個算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關，不同的輸入將會有不同的結(jié)果輸出。當輸入不夠或輸入錯誤時，算法將無法執(zhí)行或執(zhí)行有錯。一般說來，當算法擁有足夠的情報時，此算法才是有效的；而當提供的情報不夠時，算法可能無效。*:綜上所述，所謂算法，是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。3、算法復雜度主要包括時間復雜度和空間復雜度。（1）算法時間復雜度是指執(zhí)行算法所需要的計算工作量，可以用執(zhí)行算法的過程中所需基本運算的執(zhí)行次數(shù)來度量。（2）算法空間復雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。數(shù)據(jù)結(jié)構(gòu)的基本概念1、數(shù)據(jù)結(jié)構(gòu)是指相互有關聯(lián)的數(shù)據(jù)元素的集合。2、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個方面的問題：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。全國計算機等級考試一二級公共基礎知識輔導講義數(shù)據(jù)的邏輯結(jié)構(gòu)包含：1）表示數(shù)據(jù)元素的信息；2）表示各數(shù)據(jù)元素之間的前后件關系。（2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關系，即數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。1）順序存儲。它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的邏輯關系由存儲單元的鄰接關系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。2）鏈接存儲。它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈式存儲結(jié)構(gòu)。3）索引存儲：除建立存儲結(jié)點信息外，還建立附加的索引表來標識結(jié)點的地址。:數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關系，數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲結(jié)構(gòu)，但影響數(shù)據(jù)處理效率。（3）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。3、數(shù)據(jù)結(jié)構(gòu)的圖形表示一個數(shù)據(jù)結(jié)構(gòu)除了用二元關系表示外，還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點，并簡稱為結(jié)點；為了進一步表示各數(shù)據(jù)元素之間的前后件關系，對于關系R中的每一個二元組，用一條有向線段從前件結(jié)點指向后件結(jié)點。4、數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（1）線性結(jié)構(gòu)|（非空的數(shù)據(jù)結(jié)構(gòu)）條件:1）有且只有一個根結(jié)點；2）每一個結(jié)點最多有一個前件，也最多有一個后件。:常見的線性結(jié)構(gòu)有線性表、棧、隊列和線性鏈表等。（2）非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。:常見的非線性結(jié)構(gòu)有樹、二叉樹和圖等。線性表及其順序存儲結(jié)構(gòu)1、線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之全國計算機等級考試一二級公共基礎知識輔導講義間的相對位置是線性的。線性表是由n(nN0)個數(shù)據(jù)元素組成的一個有限序列，表中的每一個數(shù)據(jù)元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。線性表中數(shù)據(jù)元素的個數(shù)稱為線性表的長度。線性表可以為空表。:線性表是一種存儲結(jié)構(gòu)，它的存儲方式：順序和鏈式。2、線性表的順序存儲結(jié)構(gòu)具有兩個基本特點：(1)線性表中所有元素所占的存儲空間是連續(xù)的；(2)線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。：由此可以看出，在線性表的順序存儲結(jié)構(gòu)中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面，可以通過計算機直接確定第i個結(jié)點的存儲地址。3、順序表的插入、刪除運算(計算機等級考試培訓稿件)(1)順序表的插入運算：在一般情況下，要在第i(IWiWn)個元素之前插入一個新元素時，首先要從最后一個(即第n個)元素開始，直到第i個元素之間共n-i+1個元素依次向后移動一個位置，移動結(jié)束后，第i個位置就被空出，然后將新元素插入到第i項。插入結(jié)束后，線性表的長度就增加了1。:順性表的插入運算時需要移動元素，在等概率情況下，平均需要移動n/2個元素。(2)順序表的刪除運算：在一般情況下，要刪除第i(1WiWn)個元素時，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結(jié)束后，線性表的長度就減小了1。：進行順性表的刪除運算時也需要移動元素，在等概率情況下，平均需要移動(n-1)/2個元素。插入、刪除運算不方便。棧和隊列1、棧及其基本運算(計算機等級考試培訓稿件)棧是限定在一端進行插入與刪除運算的線性表。在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進后出”或“后進先出”的原則組織數(shù)據(jù)的。全國計算機等級考試一二級公共基礎知識輔導講義棧具有記憶作用。棧的基本運算：1）插入元素稱為入棧運算；2）刪除元素稱為退棧運算；3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。棧的存儲方式和線性表類似，也有兩種，即順序棧和鏈式棧。2、隊列及其基本運算隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。尾指針（Rear）指向隊尾元素，頭指針（front）指向排頭元素的前一個位置（隊頭）。隊列是“先進先出”或“后進后出”的線性表。隊列運算包括：1）入隊運算：從隊尾插入一個元素；2）退隊運算：從隊頭刪除一個元素。循環(huán)隊列及其運算：所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。*:循環(huán)隊列中元素的個數(shù)=rear-front。1.5線性鏈表（計算機等級考試培訓稿件）1、線性表順序存儲的缺點（計算機等級考試培訓稿件）：。）插入或刪除的運算效率很低。在順序存儲的線性表中，插入或刪除數(shù)據(jù)元素時需要移動大量的數(shù)據(jù)元素；（2）線性表的順序存儲結(jié)構(gòu)下，線性表的存儲空間不便于擴充；（3）線性表的順序存儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分配。2、線性鏈表：線性表的鏈式存儲結(jié)構(gòu)稱為線性鏈表，是一種物理存儲單元上韭連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指