計算機等級考試二級基礎(chǔ)知識

計算機等級考試二級基礎(chǔ)知識第一章數(shù)據(jù)結(jié)構(gòu)與算法一、算法1、算法：是指解題方案的準確而完整的描述。2、算法不等于程序，也不等計算機方法，程序的編制不可能優(yōu)于算法的設(shè)計。3、算法的基本特征：是一組嚴謹?shù)囟x運算順序的規(guī)則，每一個規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。特征包括：（1）可行性；（2）確定性，算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性；（3）有窮性，算法必須能在有限的時間內(nèi)做完，即能在執(zhí)行有限個步驟后終止，包括合理的執(zhí)行時間的含義；（4）擁有足夠的情報。4、算法的基本要素：一是對數(shù)據(jù)對象的ADR(a1)為第一個元素的地址，k代表每個元素占的字節(jié)數(shù)。5、順序表的運算：插入、刪除。（詳見14--16頁）四、棧和隊列1、棧是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。2、棧按照“先進后出”（FILO）或“后進先出”（LIFO）組織數(shù)據(jù)，棧具有記憶作用。用top表示棧頂位置，用bottom表示棧底。3、棧的基本運算：（1）插入元素稱為入棧運算；（2）刪除元素稱為退棧運算；（3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。4、隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。Rear指針指向隊尾，front指針指向隊頭。5、隊列是“先進行出”（FIFO）或“后進后出”（LILO）的線性表。隊列運算包括（1）入隊運算：從隊尾插入一個元素；（2）退隊運算：從隊頭刪除一個元素。6、循環(huán)隊列：s=0表示隊列空，s=1且front=rear表示隊列滿五、線性鏈表1、數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應(yīng)于一個存儲單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。結(jié)點由兩部分組成：（1）用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；（2）用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點。2、在鏈式存儲結(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。3、鏈式存儲方式即可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。4、線性鏈表，HEAD稱為頭指針，HEAD=NULL（或0）稱為空表，如果是兩指針：左指針（Llink）指向前件結(jié)點，右指針（Rlink）指向后件結(jié)點。線性鏈表的基本運算：查找、插入、刪除。六、樹與二叉樹1、樹的基本概念在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱為樹的根。在樹結(jié)構(gòu)中，每一個結(jié)點可以有多個后件，它們都稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件個數(shù)稱為該結(jié)點的度。葉子結(jié)點的度為0。樹的最大層次稱為樹的深度。2、在一個算術(shù)表達式中，有運算符和運算對象。一個運算符可以有若干個運算對象。例職，取正（+）等只有一個運算對象，稱為單目運算符；二個運算對象稱為雙目運算符，三目運算符。用樹來表示算術(shù)表達式的原則如下：表達式中的每一個運算符在樹中對應(yīng)一個結(jié)點，稱為運算符結(jié)點。運算符的每一個運算對象在樹中為該運算符結(jié)點的子樹（在樹中的順序為從左到右）。運算對象中的單變量均為葉子結(jié)點。3、二叉樹及其基本性質(zhì)（1）什么是二叉樹二叉樹是一種很有用的非線性結(jié)構(gòu)。二就樹具有以下兩個特點：非空二叉樹只有一個根結(jié)點；每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。由以上特點可以看出，在二叉樹中，每一個結(jié)點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結(jié)構(gòu)中的每一個結(jié)點的度可以是任意的。另外，二叉樹中的每一個結(jié)點的子樹被明顯地分為左子樹與右子樹?？梢詻]有其中的一個，也可以全沒有。（2）二叉樹的基本性質(zhì)性質(zhì)1：在二叉樹的第K層上，最多有（K≥1）個結(jié)點。性質(zhì)2：濃度為M的二叉樹最多有2m-1個結(jié)點。深度為m的二叉樹是指二叉樹共有m層。性質(zhì)3：在任意一棵二叉樹中度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點多一個。性質(zhì)4：具有n個結(jié)點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取的整數(shù)部分。(3)滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹是兩種特殊形態(tài)的二叉樹。滿二叉樹所謂滿二叉樹是指這樣的一種二叉樹；除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。這就是說，在滿二叉樹中，每一層上的結(jié)點數(shù)都達到最大值，即在滿二叉樹的第K層上有2K-1個結(jié)點，且深度為m的滿二叉樹有2m-1個結(jié)點。(4)完全二叉樹所謂完全二叉樹是指這樣的二叉樹，除最后一層外，每一層上的結(jié)點數(shù)均達的最大值；在最后一層上只缺少右邊的若干結(jié)點。確切地說，如果從根結(jié)點起，對二叉樹的結(jié)點自上而下、自左至右用自然數(shù)進行邊疆編號，則深度為m、且有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為m的滿二叉樹中編號從1到n的結(jié)點一一對應(yīng)時，稱之為完全二叉樹。對于完全二叉樹來說，葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)；對于任何一個結(jié)點，若其右分支下的子孫結(jié)點的最大層次為p，則其左分支下的子孫結(jié)點的最大層次或為p，或為p+1。由滿二叉樹與完全二叉樹的特點可以看出，滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。完全二叉樹還具有以下兩個性質(zhì)：性質(zhì)5：具有n個結(jié)點的完全二叉樹的深度為[log2n]+1。性質(zhì)6：設(shè)完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始，按層序（每一層從左到右）用自然數(shù)1，2，…，n給結(jié)點進行編號，則對于編號為k（k=1,2,…n）的結(jié)點有以下結(jié)論：若k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k>1，則該結(jié)點的父結(jié)點編號為INT(k/2)。若2k≤n，則編號為k的結(jié)點的左子結(jié)點編號為2k；否則該結(jié)點無左子結(jié)點（顯然也沒有右子結(jié)點）。若2k+1≤n，則編號為k的結(jié)點的右子結(jié)點編號為2k+1；否則該結(jié)點無右子結(jié)點。(5)二叉樹的存儲結(jié)構(gòu)(6)二叉樹的遍歷二叉樹的遍歷是指不重復地訪問二叉樹的所有結(jié)點。在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。前序遍歷（DLR）所謂前序遍歷是指在訪問根結(jié)點、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。F，C，A，D，B，E，G，H，P中序遍歷（LDR）所謂中序遍歷是指在訪問根結(jié)點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。A，C，B，D，F(xiàn)，E，H，G，P后序遍歷（LRD）所謂中序遍歷是指在訪問根結(jié)點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。A，B，D，C，H，P，G，E，F(xiàn)七、查找技術(shù)1、順序查找順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法如下：從線性表的第一個元素開始，依次將線性表中的元素與被查元素進行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查元素進行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失?。?。順序查找的效率是很低的。以下兩種情況只能采用順序查找：如果線性表無序表（即表中元素的排列是無序的），則不管是順序存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，都只能用順序查找。即使是有序線性表，如果采用鏈式存儲結(jié)構(gòu)，也只能用順序查找。2、二分法查找二分法查找只適用于存儲的有序表。在此所說的有序表是指線性表的中元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。設(shè)有序線性表的長度為n，被查元素為x，則對分查找的方法如下：將x與線性表的中間項進行比較：若中間項的值等于x，則說明查到，查找結(jié)束；若x小于中間項的值，則在線性表的前半部分（即中間項以前的部分）以相同的方法進行查找；若x大于中間項的值，則在線性表的后半部分（即中間項以后的部分）以相同的方法進行查找。這個過程一直進行到查找成功或子表長度為0（說明線性表中沒有這個元素）為止。顯然，當有序線性表為順序存儲時才能采用二分查找，并且，二分查找的效率要比順序查找高得多?？梢宰C明，對于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，而順序查找需要比較n次。八、排序技術(shù)1、交換類排隊序法所謂交換類排序法是指借助數(shù)據(jù)元素之間的互相交換進行排序的一種方法。冒泡排序法與快速排序法都屬于交換類的排序方法。（1）冒泡排序法基本過程如下：首先，從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個元素的大小。若相鄰兩個元素中，前面的元素大于后面的元素，則將它們互換，稱之為消去了一個逆序。放最大值然后，從后到前掃描剩下的線性表，同樣，在掃描過程中逐次比較相鄰兩個元素的大小。若相鄰兩個元素中，后面的元素大于前面的元素，則將它們互換，這樣就又消去了一個逆序。放最小值。重復上述過程，直到剩下的線性有變空為止，此時的線性表已經(jīng)變?yōu)橛行颉＜僭O(shè)線性表的長為n，則在最壞情況下，冒泡排序需要經(jīng)過n/2遍的蔥馨往后的掃描和n/2遍的從后往前的掃描，需要的比較的次數(shù)為n(n-1)/2。（2）快速排序法快速排序法也是種互換類的排序法，但由于它比冒泡排序法的速度快，因此稱之為快速排序法。基本思想如下：從線性表中選取一個元素，設(shè)T，將線性表后面小于T的元素移到前，而前大于T的元素移支后面，結(jié)果就將線性表分成了兩部分（稱為兩個子表），T插入到其分界線的位置處，這個過程稱為線性表的分割。通過對線性表的一次分割，就以T為分界線，將線性表分成了前后兩個子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。如此反復，則此時的線性表就變成了有序表。步驟：首先，在表的第一個，中間一個與最后一個元素中選取中項，設(shè)為P（K），并將P（K）賦給T，再將表中的第一個元素移到P（K）的位置上。然后設(shè)置兩個指針i和j分別指向表的起始與最后的位置。反復操作以下兩步：（4）將j逐漸減小，并逐次比較P（j）與T，直到發(fā)現(xiàn)一個P(j)<T為止，將P(j)移到P(i)位置上。（5）將i逐漸減小，并逐次比較P（i）與T，直到發(fā)現(xiàn)一個P(i)>T為止，將P(i)移到P(j)位置上。上述兩個操作交替進行，直到指針i與j指向同一個位置（即i=j）為止，此時將P(i)的位置上。分割需要記憶，用棧來實現(xiàn)。2、插入類排序法（1）簡單插入排序法所謂插入排序，是指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中。一般來說，假設(shè)線性中前j-1元素已經(jīng)有序，現(xiàn)在要將線性表中第j個元素插入到前面的有序子表中，插入過程如下：將第j個元素放到一個變量T中，然后從有序子表的最后一個元素（即線性表中第j-1個元素）開始，往前逐個與T進行比較，將大于T的元素均依次向后移動一個位置，直到發(fā)現(xiàn)一個元素不大于T為止，此時就將T（即原線性表中的第j個元素）插入到剛移出的空位置上，有序子表的長度就變?yōu)閖了。效率與冒泡法相同在最壞情況下，簡單插入排序需要n(n-1)/2次比較。（2）希爾排序法基本思想如下：將整個無序序列分割成若干小的子序列分別進行插入排序。子序列的分割方法如下：將相隔某個增量H的元素構(gòu)成一個子序列。在排序過程中，逐次減小這個增量，最后當H減到1時，進行一次插入排序，排序就完成。增量序列一般取h=n/2k(k=1,2,…[log2n],其中n為待排序序列的長度。其效率與增量序列有關(guān)。在最壞情況下，需要的比較次數(shù)為O（N1.5）。3、選擇類排序法（1）簡單選擇排序法基本思想：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面；然后對剩下的子表采用同樣的方法，直到子表空為止。簡單選擇排序法在最壞情況下需要比較n(n-1)/2/次。（2）堆排序法方法：首先將一個無序序列建成堆。然后將堆頂元素（序列中的最大項）與堆中最后一個元素交換（最大項應(yīng)該在序列的最后）。不考慮已經(jīng)換到最后的那個元素，只考慮前n-1個元素構(gòu)成的子序，顯然，該子序列已不是堆，但左、右子樹仍為堆，可以將該子序列調(diào)事為堆。反復做第（2）步，真到剩下的子序列為空為止。適用規(guī)模較大的線性表，在最壞情況下，堆排序需要比較的次數(shù)為O（nlog2n）。第2章程序設(shè)計基礎(chǔ)一、程序設(shè)計方法與風格就程序設(shè)計方法和技術(shù)的發(fā)展而言，主要經(jīng)過了結(jié)構(gòu)化程序設(shè)計和面向?qū)ο蟮某绦蛟O(shè)計階段。（一）程序設(shè)計風格一般來講，程序設(shè)計風格是指編寫程序時所表現(xiàn)出的特點、習慣和邏輯思路。程序是由人來編寫的，為了測試和維護程序，往往還要新聞記者和跟蹤程序，因此程序設(shè)計的風格總體而言應(yīng)該強調(diào)得意和清晰，程序必須是可以理解的。要形成良好的程序設(shè)計風格，主要應(yīng)注重和考慮下述一些因素。1、源程序文檔化2、源程序文檔化應(yīng)考慮如下幾點：（1）符號名的命名：符號名的命名應(yīng)具有一定的實際含義，以便于對程序功能的理解。（2）程序注釋：下克的注釋能夠幫助讀者理解程序。（3）禮堂組織：為使程序的結(jié)構(gòu)一目了然，可以在程序中利用空格、空行、縮進待技巧使程序?qū)哟吻逦＃ǘ?shù)據(jù)說明的方法在編寫程序時，需要注意數(shù)據(jù)說明的風格，以便使程序中的數(shù)據(jù)說明更易于理解和維護。一般應(yīng)注意如下幾點：（1）數(shù)據(jù)說明的次序規(guī)范化鑒于程序理解、新聞記者和維護的需要，使數(shù)據(jù)說明次序固定，可以使數(shù)據(jù)的發(fā)生容易查找，也有利于測試、排錯和維護。（2）說明語句中變量安排有序化。當一個說明語句說明多個變量時，變量按照字母順序為好。（3）使用注釋來說明復雜數(shù)據(jù)的結(jié)構(gòu)。(三)語句的結(jié)構(gòu)程序應(yīng)該簡單易懂，語句構(gòu)造應(yīng)該簡單直接，不應(yīng)該為提高效率而把語句復雜化。一般應(yīng)注意如下：（1）在一行內(nèi)只寫一條語句；（2）程序編寫應(yīng)優(yōu)先考慮清晰性；（3）除非對效率有特殊要求，程序編寫要做清晰第一，效率第二；（4）首先要保證程序正確，然后才要求提高速度；（5）避免使用臨時變量而使程序的可讀性下降；（6）避免不必要的轉(zhuǎn)移；（7）盡可能使用庫函數(shù)；（8）避免采用復雜的條件語句；（9）盡量減少使用“否定”條件的條件語句；（10）數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化；（11）要模塊化，使模塊功能盡可能單一化；（12）確保每一個模塊的獨立性；（13）從數(shù)據(jù)出發(fā)去構(gòu)造程序；（14）不要修補不好的程序，要重新編寫；（四）輸入和輸出無論是批處理的輸入和輸出方式，還是交互式的輸入和輸出方式，在設(shè)計和編程時都應(yīng)該考慮如下原則：（1）對所有的輸入數(shù)據(jù)都要檢驗數(shù)據(jù)的合法性；（2）檢查輸入項的各種重要組合的合理性；（3）輸入格式要簡單，以使得輸入的步驟和操作盡可能簡單；（4）輸入數(shù)據(jù)時，應(yīng)允許使用自由格式；（5）應(yīng)允許缺省值；（6）輸入一批數(shù)據(jù)時，最好使用輸入結(jié)束標志；（7）在以交互式輸入/輸出方式進行輸入時，要在屏幕上使用提示符明確提示輸入的請求，同時在數(shù)據(jù)輸入過程中的輸入結(jié)束時，應(yīng)在屏幕上給出狀態(tài)信息。（8）當程序設(shè)計語言對輸入格式有嚴格要求時，應(yīng)保持輸入格式與輸入語句的一致性；給所有的輸入出加注釋，并設(shè)計輸出報表格式。二、結(jié)構(gòu)化程序設(shè)計（一）構(gòu)化程序設(shè)計的原則結(jié)構(gòu)化程序設(shè)計方法的主要原則可以概括為自頂向下，逐步求精，模塊化，限制使用goto語句。1、自頂向下：程序設(shè)計時，應(yīng)先考慮總體，后考慮細節(jié)；先考慮全局目標，后考慮局部目標。不要一開始就過多追求眾多的細節(jié)，先從最上層總目標開始設(shè)計，逐步使問題具體化。2、逐步求精：對復雜問題，應(yīng)設(shè)計一些子目標作過渡，逐步細化。3、模塊化：一個復雜問題，肯定是由若干稍簡單的問題構(gòu)成。模塊化是把程序要解決的總目標分解為分目標，再進一步分解為具體的小目標，把每個小目標稱為一個模塊。4、限制使用goto語句（二）結(jié)構(gòu)化程序的基本結(jié)構(gòu)與特點1、順序結(jié)構(gòu)：順序結(jié)構(gòu)是簡單的程序設(shè)計，它是最基本、最常用的結(jié)構(gòu)，所謂順序執(zhí)行，就是按照程序語句行的自然順序，一條語句一條語句地執(zhí)行程序程序。2、選擇結(jié)構(gòu)：選擇結(jié)構(gòu)又稱為分支結(jié)構(gòu)，它包括簡單選擇和多分支選擇結(jié)構(gòu)，這種結(jié)構(gòu)可以根據(jù)設(shè)定的條件，判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)的語句序列。3、重復結(jié)構(gòu)：重復結(jié)構(gòu)又稱為循環(huán)結(jié)構(gòu)，它根據(jù)給定的條件，判斷是否需要重復執(zhí)行某一相同的或類似的程序段，利用重復結(jié)構(gòu)可簡化大量的程序行。分為兩類：一是先判斷后執(zhí)行，一是先執(zhí)行后判斷。優(yōu)點：一是程序易于理解、使用和維護。二是編程工作的效率，降低軟件開發(fā)成本。（三）結(jié)構(gòu)化程序設(shè)計原則和方法的應(yīng)用要注意把握如下要素：1、使用程序設(shè)計語言中的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯。2、選用的控制結(jié)構(gòu)只準許有一個入口和一個出口；3、程序語句組成容易識別的塊，每塊只有一個入口和一個出口；4、復雜結(jié)構(gòu)應(yīng)該嵌套的基本控制結(jié)構(gòu)進行組合嵌套來實現(xiàn)；5、語言中所沒有的控制結(jié)構(gòu)，應(yīng)該采用前后一致的方法來模擬；6、嚴格控制GOTO語句的使用。其意思是指：（1）用一個非結(jié)構(gòu)化的程序設(shè)計語言去實現(xiàn)一個結(jié)構(gòu)化的構(gòu)造；（2）若不使用GOTO語句會使功能模糊；（3）在某種可以改善而不損害程序可讀性的情況下。三、面向?qū)ο蟮某绦蛟O(shè)計（一）關(guān)于面向?qū)ο蠓椒嫦驅(qū)ο蠓椒ǖ谋举|(zhì)，就是主張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，提倡用人類在現(xiàn)實生活中常用的思維方法來認識、理解和描述客觀事物，強調(diào)最終建立的系統(tǒng)能夠映射問題域，也就是說，系統(tǒng)中的對象以及對象之間的關(guān)系能夠如實地反映問題域中固有事物及其關(guān)系。優(yōu)點：1、與人類習慣的思維方法一致2、穩(wěn)定性好3、可重用性好軟件重用是指在不同的軟件開發(fā)過程中重復作用相同或相似軟件元素的過程。重用是提高軟件生產(chǎn)率的最主要的方法。4、易于開發(fā)大型軟件產(chǎn)品5、可維護性好（1）用面向?qū)ο蟮姆椒ㄩ_發(fā)的軟件穩(wěn)定性比較好（2）用面向?qū)ο蟮姆椒ㄩ_發(fā)的軟件比較容易修改；（3）用面向?qū)ο蟮姆椒ㄩ_發(fā)的軟件比較容易理解。（4）易于測試和調(diào)試。（二）面向?qū)ο蠓椒ǖ幕靖拍?、對象（object）對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍睢ο笫菍栴}域中某個實體的抽象，設(shè)立某個對象就反映軟件系統(tǒng)保存有關(guān)它的信息并具有與它進行交互的能力。對象可以做的操作表示它的動態(tài)行為，在面向?qū)ο蠓治龊兔嫦驅(qū)ο笤O(shè)計中，通常把對象的操作也稱為方法或服務(wù)。屬性即對象所包含的信息，它在設(shè)計對象時確定，一般只能通過掛靠對象的操作來改變。操作描述了對象執(zhí)行的功能，若通過消息傳遞，還可以為其他對象使用。操作的過程對外是封閉的，即用戶只能看到這一操作實施后的結(jié)果。這相當于事先已經(jīng)設(shè)計好的各種過程，只需要調(diào)用就可以了，用戶不必去關(guān)心這一過程是如何編寫的。事實上，這個過程已經(jīng)封裝在對象中，用戶也看不到。對的這一特性即是對象的封裝性。2、類（Class）和實例(Instance)類是具有共同屬性、共同方法的對象的集合。所以，類是對象的抽象，它描述了屬于該對象類型的所有對象的性質(zhì)，而一個對象則是其對應(yīng)類的一個實例。例如：Integer是一個整數(shù)類，它描述了所有整數(shù)的性質(zhì)。因此任何整數(shù)都是整數(shù)類的對象，而一個具體的整數(shù)“123”是類Integer的實例。由類的定義可知，類是關(guān)于對象性質(zhì)的描述，它同對象一樣，包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。3、消息（Message）消息是一個實例與另一個實例之間傳遞信息，它請示對象執(zhí)行某一處理或回答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流的控制流。消息的使用類似于函數(shù)調(diào)用，消息中指定了某一個實例，一個操作名和一個參數(shù)表（可空）。接收消息的實例執(zhí)行消息中指定的操作，并將形式參數(shù)數(shù)與參數(shù)表中相應(yīng)的值結(jié)合起來。消息傳遞過程中，由發(fā)送消息的對象（發(fā)送對象）的觸發(fā)操作產(chǎn)生輸出結(jié)果，作為消息傳送至接受消息的對象（接受對象），引發(fā)接受消息的對象一系列的操作。所傳送的消息實質(zhì)上是接受對象所具有的操作/方法名稱，有時還包括相應(yīng)參數(shù)。通常，一個消息由下述三部分組成：（1）接收消息的對象的名稱；（2）消息標識符（也稱為消息名）；（3）零個或多個參數(shù)。4、繼承（Inheritance）繼承是面向?qū)ο蟮姆椒ǖ囊粋€主要特征。廣義地說，繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復定義它們。繼承具有傳遞性，如果類C繼承類B，類B繼承類A，則類C繼承類A。因此一個類實際上繼承了它上層的全部基類的特性，也就是說，屬于某類的對象除了具有該類所定義的特性外，還具有該類上層全部基類定義的特性。繼承分為單繼承與多重繼承。單繼承是指，一個類只允許有一個父類，即類等級為樹形結(jié)構(gòu)。多重繼承是指，一個類允許有多個父類。多重繼承的類可以組合多個父類的性質(zhì)構(gòu)成所需要的性質(zhì)。5、多態(tài)性（Polymorphism）對象根據(jù)所接受的消息而做出動作，同樣的消息被不同的對象接受時可導致完全不同的行動，該現(xiàn)象稱為多態(tài)性。第3章軟件工程基礎(chǔ)一、軟件工程基本概念（一）軟件定義與軟件特點計算機軟件是計算機系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合?；校绦蚴擒浖_發(fā)人員根據(jù)用戶需求開發(fā)的用程序設(shè)計語言描述的、適合計算機執(zhí)行的指令（語句）序列。數(shù)據(jù)是使程序能正常操縱信息的數(shù)據(jù)結(jié)構(gòu)。文檔是與程序開發(fā)、維護和使用有關(guān)的圖文資料?？梢娷浖蓛刹糠纸M成：一是機器可執(zhí)行的程序和數(shù)據(jù)；二是機器不可執(zhí)行的，與軟件開發(fā)、運行、維護、使用等有關(guān)的文檔。軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。應(yīng)用軟件：為解決特定領(lǐng)域的應(yīng)用而開發(fā)的軟件。系統(tǒng)軟件：計算機管理自身資源，提高計算機使用效率并為計算機用戶提供各種服務(wù)的軟件。支撐軟件：介于系統(tǒng)軟件和應(yīng)用軟件之間，協(xié)助用戶開發(fā)軟件的工具性軟件，包括輔助和支持開發(fā)和維護應(yīng)用軟件的工具軟件。（二）軟件危機與軟件工程軟件工程概念的出現(xiàn)源自軟件危機。所謂有軟件危機四伏是泛指在計算機軟件開發(fā)和維護過程中所遇到的嚴重問題。具體地說，在軟件開發(fā)和維護過程中，軟件危機主要表現(xiàn)在：（1）軟件需求的增長得不到滿足。用戶對系統(tǒng)不滿意的情況經(jīng)常發(fā)生。（2）軟件開發(fā)成本和進度無法控制。開發(fā)成本超出預(yù)算，開發(fā)周期大大超過規(guī)定日期的情況經(jīng)常發(fā)生。（3）軟件質(zhì)量難以保證。（4）軟件不可維護或護程度非常低。（5）軟件的成本不斷提高。（6）軟件開發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長?？傊?，可以將軟件危機歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問題。軟件工程就是試圖用工程、科學和數(shù)學的大批量與方法研制、維護計算機軟件的有關(guān)技術(shù)及管理方法。軟件工程包括3個要素：即方法、工具和過程。方法是完成軟件工程項目的技術(shù)手段；工具支持軟件的開發(fā)、管理、文檔生成；過程支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理。軟件工程的核心思想是把軟件產(chǎn)品看作是一個工程產(chǎn)品來處理。（三）軟件生命周期通常，將軟件產(chǎn)品從提出、實現(xiàn)、使用維護到停止使用退役的過程稱為軟件生命周期。軟件生命周期分為軟件定義、軟件開發(fā)及軟件運行維護三個階段。軟件生命周期的主要活動階段是：（1）可行性研究與計劃制定。確定待開發(fā)軟件系統(tǒng)的開發(fā)目標和總的要求，給出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成開發(fā)任務(wù)的實施計劃。（2）需求分析。對待開發(fā)軟件提出的需求進行分析并給出詳細定義。編寫軟件規(guī)格說明書及初步的用戶手冊，提交評審。（3）軟件設(shè)計。系統(tǒng)設(shè)計人員和程序設(shè)計人員應(yīng)該在反復理解軟件需求的基礎(chǔ)上，給出軟件的結(jié)構(gòu)、模塊和劃分、功能的分配及處理流程。在系統(tǒng)比軟件復雜的情況下，設(shè)計階段可分解成概要設(shè)計階段和詳細設(shè)計階段。編寫概要設(shè)計說明書、詳細設(shè)計說明書和測試計劃初稿，提交評審。（4）軟件實現(xiàn)。把軟件設(shè)計轉(zhuǎn)換成計算機可以接受的程序代碼。即完成源程序的編碼，編寫用戶手冊、操作手冊等面向用戶的文檔，編寫單元測試計劃。（5）軟件測試。在設(shè)計測試用例的基礎(chǔ)上，檢驗軟件的各個組成部分。編寫測試分析報告。（6）運行和維護。將已交付的軟件投入運行，并在運行使用中不斷地維護，根據(jù)新進出的需求進行必要而且可能的擴充和刪改。（四）軟件工程的目標與原則1、軟件工程的目標軟件工程的目標是，在給定成本、進度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。軟件工程需要達到的基本目標應(yīng)是：付出較低的開發(fā)成本；達到要求的軟件功能；取得較好的軟件性能；開發(fā)的軟件易于移植；需要較低的維護費用；能按時完成開發(fā)，及時交付使用。2、軟件工程的原則為了達到上述的軟件工程目標，在軟件開發(fā)過程中，必須遵循軟件工程的基本原則。這些基本原則包括抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗證性。（1）抽象。抽取事物最基本的特性和行為，忽略非本質(zhì)細節(jié)。采用分層次抽象，自頂向下，逐層細化的辦法控制軟件開發(fā)過程的復雜性。（2）信息隱蔽。采用封閉技術(shù)，將程序模塊的實現(xiàn)細節(jié)隱藏起來，使模塊接口盡量簡單。（3）模塊化。模塊是程序中相對獨立的成分，一個獨立的編程單位，應(yīng)有良好的接口定義。模塊的大小要適中，模塊過大會使模塊內(nèi)部的復雜性增加，不得對模塊的理解和個性也不得模塊的調(diào)試和重用。模塊太小會導致整個系統(tǒng)表示過于復雜，不利于控制系統(tǒng)的復雜性。（4）局部化。要求在一個物理模塊內(nèi)集中邏輯上相互關(guān)聯(lián)的計算資源，保證模塊間具有松散的耦合關(guān)系，模塊內(nèi)部有較強的內(nèi)驟性，這有助于控制角的復雜性。（5）確定性軟件開發(fā)過程中所有概念的表達應(yīng)是確定的、無歧義且規(guī)范的。這有助于人與人的交互不會產(chǎn)生誤解和遺漏，以保證整個開發(fā)工作的協(xié)調(diào)一致。（6）一致性。指程序、數(shù)據(jù)和文檔的整個軟件系統(tǒng)的各模塊應(yīng)使用已知的概念、符號和術(shù)語；程序內(nèi)外部接口應(yīng)保持一致，系統(tǒng)規(guī)格說明與系統(tǒng)行為應(yīng)保持一致。（7）完備性。軟件系統(tǒng)不丟失任何重要成分，完全實現(xiàn)系統(tǒng)所需的功能。（8）可驗證性。開發(fā)大型軟件系統(tǒng)需要對系統(tǒng)自頂向下，逐層分解。系統(tǒng)分解應(yīng)遵循容易檢查、測評、評審的原則，以確保系統(tǒng)的正確性。二、結(jié)構(gòu)化分析方法1、關(guān)于結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計理論在軟件需求分析階段的運用。對于面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法，按照DeMarco的定義，“結(jié)構(gòu)化分析就是使用數(shù)據(jù)流圖（DFD）、數(shù)據(jù)字典（DD）、結(jié)構(gòu)化英語、判定表和羊定樹等工具，來建立一種新的、稱為結(jié)構(gòu)化規(guī)格說明的目標文檔。”結(jié)構(gòu)化分析方法的實質(zhì)是著眼于數(shù)據(jù)流、自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具建立系統(tǒng)的邏輯模型。2、結(jié)構(gòu)化分析的常用工具(1)數(shù)據(jù)流圖（DFD—DataFlowDiagram）數(shù)據(jù)流圖是描述數(shù)據(jù)處理過程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)的功能建模。數(shù)據(jù)流圖從數(shù)據(jù)傳遞和加工的角度，來刻畫數(shù)據(jù)流從輸入到輸出的移動變換過程。數(shù)據(jù)流圖中的主要圖形元素與說明如下：加工（轉(zhuǎn)換）。輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。（2）數(shù)據(jù)字典（DD—DataDictionary）數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。數(shù)據(jù)字典是對所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個有組織的列表，以及精確的、嚴格的定義，使得用戶和系統(tǒng)分析員對于輸入、輸出、存儲成分和中間計算結(jié)果有共同的理解。數(shù)據(jù)字典中有4中類型的條目：數(shù)據(jù)流、數(shù)據(jù)項、數(shù)據(jù)存儲和加工（3）判定樹使用判定樹進行描述時，應(yīng)先從問題定義的文字描述中分清哪些是判定的條件，哪些是判定的結(jié)論，根據(jù)模仿材料中的連接詞找出判定條件之間的從屬關(guān)系、并列關(guān)系、選擇關(guān)系，根據(jù)它們構(gòu)造判定樹。（4）判定表判定表與判定樹相似，當數(shù)據(jù)流圖中的加工要依賴于多個邏輯條件的聯(lián)歡會，即完成該加工的一組動作是由于某一組條件聯(lián)歡會的組合而引發(fā)的，使用判定表描述比較適宜。判定表由四部分組成，基本條件，條件項，基本動作，動作項（三）軟件需求規(guī)格說明書軟件需求規(guī)格說明書（SRS,softwareRequirementSpecification）是需求分析階段的最后成果，是軟件開發(fā)中的文檔之一。軟件需求規(guī)格說明書的特點①正確性。體現(xiàn)待開發(fā)系統(tǒng)的真實要求。②無歧義性。對每一個需求只有一種解釋，其陳述具有惟一性。③完整性。包括全部有意義的需求，功能的、性能的、設(shè)計的、約束的，屬性或外部接口等方面的需求。④可驗證性。描述的每一個需求都是可以驗證的，即存在有限代價的有效過程驗證確認。⑤一致性。各個需求的描述不能矛盾。⑥可理解性。需求說明書必須簡明易懂，盡量少包含計算機的要領(lǐng)和術(shù)語，以便用戶和軟件人員都能接受它。⑦可修改性和課追蹤性。每一個需求的來源、流向是清晰的，當產(chǎn)生和改變文件編制時，可以方便地引證每一個需求。三、軟件設(shè)計（一）軟件設(shè)計的基本概念1、軟件設(shè)計的基礎(chǔ)軟件設(shè)計是軟件工程的重要階段，軟件設(shè)計是確定系統(tǒng)的物理模型。從技術(shù)觀點來看，軟件設(shè)計包括軟件結(jié)構(gòu)設(shè)計、數(shù)據(jù)設(shè)計、接口設(shè)計、過程設(shè)計。結(jié)構(gòu)設(shè)計是定義軟件系統(tǒng)各主要部件之間的關(guān)系；數(shù)據(jù)設(shè)計是將分析時創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義；接口設(shè)計是描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信；過程設(shè)計則是把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程性描述。2、從工程管理角度來看，軟件設(shè)計分兩步完成：概要設(shè)計和詳細設(shè)計。概要設(shè)計（又稱結(jié)構(gòu)設(shè)計）將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)、確定系統(tǒng)級接口、全局數(shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫模式；詳細設(shè)計確立每個模塊的實現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當方法表示算法和數(shù)據(jù)結(jié)構(gòu)的細節(jié)。（二）軟件設(shè)計的基本原理1、軟件設(shè)計遵循軟件工程的基本目標和原則，建立了適用于在軟件設(shè)計中應(yīng)該遵循的基本原理和與軟件設(shè)計有關(guān)的概念。（1）抽象軟件設(shè)計中考慮模塊化解決方案時，可以定出多個抽象級別。抽象的層次從概要設(shè)計到詳細設(shè)計逐步降低。（2）模塊化模塊化是指把一個待開發(fā)的軟件分解成若干個小的簡單的部分。模塊化是指解決一個復雜問題時自頂向下逐層把軟件系統(tǒng)劃分成若干模塊的過程。（3）信息隱蔽信息隱蔽是指，在一個模塊內(nèi)包含的信息（過程或數(shù)據(jù)），對于不需要這些信息的其他模塊來說是不能訪問的。（4）模塊獨立性模塊獨立性是指，每個模塊只完成系統(tǒng)要求的獨立的子功能，并且與其他模塊的聯(lián)系最少且接口簡單。是評價設(shè)計好壞的重要度量標準。2、衡量軟件的模塊獨立性作用耦合性和內(nèi)聚性兩個定性的度量標準（1）內(nèi)聚性：內(nèi)聚性是一個模塊內(nèi)部各個元素間彼此結(jié)合的緊密程度的度量。內(nèi)聚是從功能角度來度量模塊內(nèi)的聯(lián)系。內(nèi)聚有如下的種類，它們之間的內(nèi)聚性由弱到強排列為：偶然內(nèi)聚邏輯內(nèi)聚時間內(nèi)聚過程通信內(nèi)聚順序內(nèi)聚功能內(nèi)聚（2）耦合性：耦合性是模塊間互相連接的緊密程度的度量。耦合性取決于各個模塊之間接口的復雜度、調(diào)用方式以及哪些信息通過接口。耦合可以分為下列幾種，它們之間的耦合度由高到低排列為：內(nèi)容耦合公共耦合外部耦合控制耦合標記耦合數(shù)據(jù)耦合非直接耦合在程序結(jié)構(gòu)中，各模塊的內(nèi)聚性越強，則耦合性越弱。一般較優(yōu)秀的軟件設(shè)計，應(yīng)盡量做到高內(nèi)聚，低耦合，即減弱模塊之間的耦合性和提高模塊內(nèi)的內(nèi)聚性，有得提高模塊的獨立性。四、軟件測試（一）軟件測試的目的GrenfordJ.Myers給出了軟件測試的目的：軟件測試是為了發(fā)現(xiàn)程序中的錯誤而執(zhí)行程序的過程；一個好的測試用例子指很可能找到迄今為止尚未發(fā)現(xiàn)的錯誤的用例；一個成功的測試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯誤的測試。Myers的觀點告訴人們測試要以查找錯誤為中心，而不是為了演示軟件的正確功能。（二）軟件測試的準則1、所有測試都應(yīng)追溯到需求軟件測試的目的是發(fā)現(xiàn)錯誤，而最嚴懲的錯誤不外乎是導致程序無法滿足用戶需求的錯誤。2、嚴格執(zhí)行測試計劃，排除測試的隨意性。軟件測試應(yīng)當制定明確的測試計劃并按照計劃執(zhí)行。測試計劃應(yīng)包括：所測軟件的功能、輸入和輸出、測試內(nèi)容、各項測試的目的和進度安排、測試資料、測試工具測試用例的選擇、資源要求、測試的控制方式和過程等。3、充分注意測試中的群集現(xiàn)象經(jīng)驗表明，程序中存在錯誤的概率與該程序中已發(fā)現(xiàn)的錯誤數(shù)成正比。這一現(xiàn)象說明，為了提高測試效率，測試人員應(yīng)該集中對付那些錯誤群集的程序。4、程序員應(yīng)避免檢查自己的程序為了達到好的測試效果，應(yīng)該由獨立的第三方來構(gòu)造測試。因為從心理學角度講，程序人員或設(shè)計方在測試自己的程序，要采取客硯的態(tài)度是程序不同地存在障礙的。5、窮舉測試不可能所謂窮舉測試是指把程序所有可能的執(zhí)行路徑都進行檢查的測試。但是，即使規(guī)模較小的程序，其路徑排列數(shù)也是相當大的，在實際測試過程中不可能窮盡每一種組合。這說明，測試只能證明程序中有錯誤，不能證明程序中沒有錯誤。6、妥善保存測試計劃、測試用例、出錯統(tǒng)計和最終分析報告，為維護提供方便。（三）軟件測試技術(shù)與方法綜述若從是否需要執(zhí)行被測軟件的角度，可以分為靜態(tài)測試和動態(tài)測試方法。若按照功能劃分可以分為白盒測試和黑盒測試方法1、靜態(tài)測試與動態(tài)測試（1）靜態(tài)測試靜態(tài)測試包括代碼檢查、表態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量等。代碼檢查包括代碼審查、代碼走查、桌面檢查、靜態(tài)分析等具體方式。（2）動態(tài)測試靜態(tài)測試不實際運行軟件，主要通過人工進行。動態(tài)測試是基于計算機的測試，是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程。設(shè)計高效、合理的測試用例是動態(tài)測試的關(guān)鍵。測試用例是為測試設(shè)計的數(shù)據(jù)。測試用例由測試輸入數(shù)據(jù)和與之對應(yīng)的預(yù)期輸出結(jié)果兩部分組成。測試用例的格式為：[（輸入值集），（輸出值集）]2、白盒測試方法白盒測試方法也稱結(jié)構(gòu)測試或邏輯驅(qū)動測試。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過程，檢查內(nèi)部萬分，以確認每種內(nèi)部操作符合設(shè)計規(guī)格要求。白盒測試把測試對象看作一個打開的盒子，允許測試人員利用程序內(nèi)部的邏輯結(jié)構(gòu)及有送信息來設(shè)計或選擇測試用例，對程序所有的邏輯路徑進行測試。通過在不同點檢查程序的狀態(tài)來了解實際的運行狀態(tài)是否與預(yù)期的一致。所以，白盒測試是在程序內(nèi)部進行，主要用于完成軟件內(nèi)部操作的驗證。白盒測試的基本原則是：保證所測模塊中每一獨立路徑至少執(zhí)行一次；保證所測模塊所有判斷的每一分支至少執(zhí)行一次；保證所測模塊每一循環(huán)都在邊界條件和一般條件下至少各執(zhí)行一次；驗證所有內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性。白盒測試的主要方法有邏輯覆蓋、基本路徑測試等。3．黑盒測試方法與測試用例設(shè)計黑盒測試方法也稱功能測試或數(shù)據(jù)驅(qū)動測試。黑盒測試是對軟件已經(jīng)實現(xiàn)的功能是否滿足需求進行測試和驗證。黑盒測試完全不考慮程序內(nèi)部的邏輯結(jié)構(gòu)和內(nèi)部特性，只依據(jù)程序的需求和功能規(guī)格說明，檢查程序的功能是否