計算機二級公共基礎知識-【考試必備

1、二級共公基礎知識第一章數(shù)據(jù)結構與算法1.1 算法算法：是指解題方案的準確而完整的描述。算法不等于程序，也不等計算機方法，程序的編制不可能優(yōu)于算法的設計。算法的基本特征：是一組嚴謹?shù)囟x運算順序的規(guī)則，每一個規(guī)則都是有效的，是明確的，此順序將在有限的次數(shù)下終止。特征包括：（1）可行性；（2）確定性，算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性；（3）有窮性，算法必須能在有限的時間內做完，即能在執(zhí)行有限個步驟后終止，包括合理的執(zhí)行時間的含義；（4）擁有足夠的情報。算法的基本要素：一是對數(shù)據(jù)對象的運算和操作；二是算法的控制結構。指令系統(tǒng)：一個計算機系統(tǒng)能執(zhí)行的所有指令的集合

2、?；具\算和操作包括：算術運算、邏輯運算、關系運算、數(shù)據(jù)傳輸。算法的控制結構：順序結構、選擇結構、循環(huán)結構。算法基本設計方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術、回溯法。算法復雜度：算法時間復雜度和算法空間復雜度。算法時間復雜度是指執(zhí)行算法所需要的計算工作量。算法空間復雜度是指執(zhí)行這個算法所需要的內存空間。1.2 數(shù)據(jù)結構的基本基本概念數(shù)據(jù)結構研究的三個方面：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關系，即數(shù)據(jù)的邏輯結構；（2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關系，即數(shù)據(jù)的存儲結構；（3）對各種數(shù)據(jù)結構進行的運算。數(shù)據(jù)結構是指相互有關聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)的邏輯結構包含

3、：（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的前后件關系。數(shù)據(jù)的存儲結構有順序、鏈接、索引等。線性結構條件：（1）有且只有一個根結點；（2）每一個結點最多有一個前件，也最多有一個后件。非線性結構：不滿足線性結構條件的數(shù)據(jù)結構。13 線性表及其順序存儲結構線性表由一組數(shù)據(jù)元素構成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。在復雜線性表中，由若干項數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄，而由多個記錄構成的線性表又稱為文件。非空線性表的結構特征：（1）且只有一個根結點a1，它無前件；（2）有且只有一個終端結點an，它無后件；（3）除根結點與終端結點外，其他所有結點有且只有一個前件

4、，也有且只有一個后件。結點個數(shù)n稱為線性表的長度，當n=0時，稱為空表。線性表的順序存儲結構具有以下兩個基本特點：（1）線性表中所有元素的所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。ai的存儲地址為：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)為第一個元素的地址，k代表每個元素占的字節(jié)數(shù)。順序表的運算：插入、刪除。 （詳見14-16頁）14 棧和隊列棧是限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧按照“先進后出”（FILO）或“后進先出”（LIFO）組織數(shù)據(jù)，棧具有記憶作用。用to

5、p表示棧頂位置，用bottom表示棧底。棧的基本運算：（1）插入元素稱為入棧運算；（2）刪除元素稱為退棧運算；（3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。Rear指針指向隊尾，front指針指向隊頭。隊列是“先進行出”（FIFO）或“后進后出”（LILO）的線性表。隊列運算包括（1）入隊運算：從隊尾插入一個元素；（2）退隊運算：從隊頭刪除一個元素。循環(huán)隊列：s=0表示隊列空，s=1且front=rear表示隊列滿15 線性鏈表數(shù)據(jù)結構中的每一個結點對應于一個存儲單元，這種存儲單元稱為存儲結點，簡稱結點。

6、結點由兩部分組成：（1）用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；（2）用于存放指針，稱為指針域，用于指向前一個或后一個結點。在鏈式存儲結構中，存儲數(shù)據(jù)結構的存儲空間可以不連續(xù)，各數(shù)據(jù)結點的存儲順序與數(shù)據(jù)元素之間的邏輯關系可以不一致，而數(shù)據(jù)元素之間的邏輯關系是由指針域來確定的。鏈式存儲方式即可用于表示線性結構，也可用于表示非線性結構。線性鏈表，HEAD稱為頭指針，HEAD=NULL（或0）稱為空表，如果是兩指針：左指針（Llink）指向前件結點，右指針（Rlink）指向后件結點。線性鏈表的基本運算：查找、插入、刪除。16樹與二叉樹一、樹的基本概念在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的

7、結點只有一個，稱為樹的根結點，簡稱為樹的根。在樹結構中，每一個結點可以有多個后件，它們都稱為該結點的子結點。沒有后件的結點稱為葉子結點。在樹結構中，一個結點所擁有的后件個數(shù)稱為該結點的度。葉子結點的度為0。樹的最大層次稱為樹的深度。在一個算術表達式中，有運算符和運算對象。一個運算符可以有若干個運算對象。例職，取正（+）等只有一個運算對象，稱為單目運算符；二個運算對象稱為雙目運算符，三目運算符。用樹來表示算術表達式的原則如下：表達式中的每一個運算符在樹中對應一個結點，稱為運算符結點。運算符的每一個運算對象在樹中為該運算符結點的子樹（在樹中的順序為從左到右）。運算對象中的單變量均為葉子結點。二、二

8、叉樹及其基本性質1、什么是二叉樹二叉樹是一種很有用的非線性結構。二就樹具有以下兩個特點：非空二叉樹只有一個根結點；每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。由以上特點可以看出，在二叉樹中，每一個結點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結構中的每一個結點的度可以是任意的。另外，二叉樹中的每一個結點的子樹被明顯地分為左子樹與右子樹?？梢詻]有其中的一個，也可以全沒有。二叉樹的基本性質性質1：在二叉樹的第K層上，最多有（K1）個結點。性質2：濃度為M的二叉樹最多有2m-1 個結點。深度為m 的二叉樹是指二叉樹共有m層。性質3：在任意一棵二叉樹中度為0的結點（即

9、葉子結點）總是比度為2的結點多一個。性質4：具有n個結點的二叉樹，其深度至少為 log2n+1,其中 log2n表示取的整數(shù)部分。滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹是兩種特殊形態(tài)的二叉樹。滿二叉樹所謂滿二叉樹是指這樣的一種二叉樹；除最后一層外，每一層上的所有結點都有兩個子結點。這就是說，在滿二叉樹中，每一層上的結點數(shù)都達到最大值，即在滿二叉樹的第K層上有2K-1個結點，且深度為m的滿二叉樹有2m-1個結點。完全二叉樹所謂完全二叉樹是指這樣的二叉樹，除最后一層外，每一層上的結點數(shù)均達的最大值；在最后一層上只缺少右邊的若干結點。列確切地說，如果從根結點起，對二叉樹的結點自上而下、自左至右用自

10、然數(shù)進行邊疆編號，則深度為m、且有n 個結點的二叉樹，當且僅當其每一個結點都與深度為m的滿二叉樹中編號從1到n的結點一一對應時，稱之為完全二叉樹。對于完全二叉樹來說，葉子結點只可能在層次最大的兩層上出現(xiàn)；對于任何一個結點，若其右分支下的子孫結點的最大層次為p，則其左分支下的子孫結點的最大層次或為p，或為p+1。由滿二叉樹與完全二叉樹的特點可以看出，滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。完全二叉樹還具有以下兩個性質：性質5：具有n個結點的完全二叉樹的深度為 log2n+1。性質6：設完全二叉樹共有n個結點。如果從根結點開始，按層序（每一層從左到右）用自然數(shù)1，2，n給結點進行編號

11、，則對于編號為k （k=1,2,n）的結點有以下結論：若k=1，則該結點為根結點，它沒有父結點；若k1，則該結點的父結點編號為INT(k/2)。若2kn，則編號為k 的結點的左子結點編號為2k ；否則該結點無左子結點（顯然也沒有右子結點）。若2k+1n，則編號為k 的結點的右子結點編號為2k+1；否則該結點無右子結點。三、二叉樹的存儲結構二叉樹的遍歷二叉樹的遍歷是指不重復地訪問二叉樹的所有結點。在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。1、前序遍歷（DLR）所謂前序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷

12、左、右子樹時，仍然先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。F，C，A，D，B，E，G，H，P2、中序遍歷（LDR）所謂中序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。A，C，B，D，F(xiàn)，E，H，G，P3、后序遍歷（LRD）所謂中序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。A，B，D，C，H，P，G，E，F(xiàn)1.7查找技術一、

13、順序查找順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法如下：從線性表的第一個元素開始，依次將線性表中的元素與被查元素進行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查元素進行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失?。?。順序查找的效率是很低的。以下兩種情況只能采用順序查找：如果線性表無序表（即表中元素的排列是無序的），則不管是順序存儲結構還是鏈式存儲結構，都只能用順序查找。即使是有序線性表，如果采用鏈式存儲結構，也只能用順序查找。二、二分法查找二分法查找只適用于存儲的有序表。在此所說的有序表是指線性表的中元素按值非遞減排列（即從小

14、到大，但允許相鄰元素值相等）。設有序線性表的長度為n，被查元素為x，則對分查找的方法如下：將x與線性表的中間項進行比較：若中間項的值等于x，則說明查到，查找結束；若x小于中間項的值，則在線性表的前半部分（即中間項以前的部分）以相同的方法進行查找；若x大于中間項的值，則在線性表的后半部分（即中間項以后的部分）以相同的方法進行查找。這個過程一直進行到查找成功或子表長度為0（說明線性表中沒有這個元素）為止。顯然，當有序線性表為順序存儲時才能采用二分查找，并且，二分查找的效率要比順序查找高得多?？梢宰C明，對于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，而順序查找需要比較n次。1

15、.8排序技術一、交換類排隊序法所謂交換類排序法是指借助數(shù)據(jù)元素之間的互相交換進行排序的一種方法。冒泡排序法與快速排序法都屬于交換類的排序方法。1、 冒泡排序法基本過程如下：首先，從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個元素的大小。若相鄰兩個元素中，前面的元素大于后面的元素，則將它們互換，稱之為消去了一個逆序。放最大值然后，從后到前掃描剩下的線性表，同樣，在掃描過程中逐次比較相鄰兩個元素的大小。若相鄰兩個元素中，后面的元素大于前面的元素，則將它們互換，這樣就又消去了一個逆序。放最小值。重復上述過程，直到剩下的線性有變空為止，此時的線性表已經變?yōu)橛行?。假設線性表的長為n，則在最壞情況

16、下，冒泡排序需要經過n/2遍的蔥馨往后的掃描和n/2遍的從后往前的掃描，需要的比較的次數(shù)為n(n-1)/2。2、 快速排序法快速排序法也是種互換類的排序法，但由于它比冒泡排序法的速度快，因此稱之為快速排序法?；舅枷肴缦拢簭木€性表中選取一個元素，設T，將線性表后面小于T的元素移到前，而前大于T的元素移支后面，結果就將線性表分成了兩部分（稱為兩個子表），T插入到其分界線的位置處，這個過程稱為線性表的分割。通過對線性表的一次分割，就以T為分界線，將線性表分成了前后兩個子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。如此反復，則此時的線性表就變成了有序表。步驟：首先，在表的

17、第一個，中間一個與最后一個元素中選取中項，設為P（K），并將P（K）賦給T，再將表中的第一個元素移到P（K）的位置上。然后設置兩個指針i和j分別指向表的起始與最后的位置。反復操作以下兩步：（4） 將j逐漸減小，并逐次比較P（j）與T，直到發(fā)現(xiàn)一個P(j)T為止，將P(i)移到P(j)位置上。上述兩個操作交替進行，直到指針i與j 指向同一個位置（即i=j）為止，此時將P(i)的位置上。分割需要記憶，用棧來實現(xiàn)。二、 插入類排序法1、 簡單插入排序法所謂插入排序，是指將無序序列中的各元素依次插入到已經有序的線性表中。一般來說，假設線性中前j-1元素已經有序，現(xiàn)在要將線性表中第j個元素插入到前面的有

18、序子表中，插入過程如下：道德將第j個元素放到一個變量T中，然后從有序子表的最后一個元素（即線性表中第j-1個元素）開始，往前逐個與T進行比較，將大于T的元素均依次向后移動一個位置，直到發(fā)現(xiàn)一個元素不大于T為止，此時就將T（即原線性表中的第j個元素）插入到剛移出的空位置上，有序子表的長度就變?yōu)閖了。效率與冒泡法相同在最壞情況下，簡單插入排序需要n(n-1)/2次比較。2、 希爾排序法基本思想如下：將整個無序序列分割成若干小的子序列分別進行插入排序。子序列的分割方法如下：將相隔某個增量H的元素構成一個子序列。在排序過程中，逐次減小這個增量，最后當H減到1時，進行一次插入排序，排序就完成。增量序列一

19、般取h=n/2k(k=1,2,log2n,其中n為待排序序列的長度。其效率與增量序列有關。在最壞情況下，需要的比較次數(shù)為O（.）。三、 選擇類排序法、 簡單選擇排序法基本思想：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面；然后對剩下的子表采用同樣的方法，直到子表空為止。簡單選擇排序法在最壞情況下需要比較n(n-1)/2/次。、 堆排序法方法：（1）首先將一個無序序列建成堆。（2）然后將堆頂元素（序列中的最大項）與堆中最后一個元素交換（最大項應該在序列的最后）。不考慮已經換到最后的那個元素，只考慮前n-1個元素構成的子序，顯然，該子序列已不是堆，但左、右子樹仍為堆，可以將該子序列調事

20、為堆。反復做第（2）步，真到剩下的子序列為空為止。適用規(guī)模較大的線性表，在最壞情況下，堆排序需要比較的次數(shù)為O（nlog2n）。 1.7查找技術一、順序查找順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法如下：從線性表的第一個元素開始，依次將線性表中的元素與被查元素進行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查元素進行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失?。?。順序查找的效率是很低的。以下兩種情況只能采用順序查找：如果線性表無序表（即表中元素的排列是無序的），則不管是順序存儲結構還是鏈式存儲結構，都只能用順序查找。即使是有序線

21、性表，如果采用鏈式存儲結構，也只能用順序查找。二、二分法查找二分法查找只適用于存儲的有序表。在此所說的有序表是指線性表的中元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。設有序線性表的長度為n，被查元素為x，則對分查找的方法如下：將x與線性表的中間項進行比較：若中間項的值等于x，則說明查到，查找結束；若x小于中間項的值，則在線性表的前半部分（即中間項以前的部分）以相同的方法進行查找；若x大于中間項的值，則在線性表的后半部分（即中間項以后的部分）以相同的方法進行查找。這個過程一直進行到查找成功或子表長度為0（說明線性表中沒有這個元素）為止。顯然，當有序線性表為順序存儲時才能采用二分查找，

22、并且，二分查找的效率要比順序查找高得多?？梢宰C明，對于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，而順序查找需要比較n次。1.8排序技術一、交換類排隊序法所謂交換類排序法是指借助數(shù)據(jù)元素之間的互相交換進行排序的一種方法。冒泡排序法與快速排序法都屬于交換類的排序方法。1、 冒泡排序法基本過程如下：首先，從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個元素的大小。若相鄰兩個元素中，前面的元素大于后面的元素，則將它們互換，稱之為消去了一個逆序。放最大值然后，從后到前掃描剩下的線性表，同樣，在掃描過程中逐次比較相鄰兩個元素的大小。若相鄰兩個元素中，后面的元素大于前面的元素

23、，則將它們互換，這樣就又消去了一個逆序。放最小值。重復上述過程，直到剩下的線性有變空為止，此時的線性表已經變?yōu)橛行颉＜僭O線性表的長為n，則在最壞情況下，冒泡排序需要經過n/2遍的蔥馨往后的掃描和n/2遍的從后往前的掃描，需要的比較的次數(shù)為n(n-1)/2。2、 快速排序法快速排序法也是種互換類的排序法，但由于它比冒泡排序法的速度快，因此稱之為快速排序法?；舅枷肴缦拢簭木€性表中選取一個元素，設T，將線性表后面小于T的元素移到前，而前大于T的元素移支后面，結果就將線性表分成了兩部分（稱為兩個子表），T插入到其分界線的位置處，這個過程稱為線性表的分割。通過對線性表的一次分割，就以T為分界線，將線性

24、表分成了前后兩個子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。如此反復，則此時的線性表就變成了有序表。步驟：首先，在表的第一個，中間一個與最后一個元素中選取中項，設為P（K），并將P（K）賦給T，再將表中的第一個元素移到P（K）的位置上。然后設置兩個指針i和j分別指向表的起始與最后的位置。反復操作以下兩步：（4） 將j逐漸減小，并逐次比較P（j）與T，直到發(fā)現(xiàn)一個P(j)T為止，將P(i)移到P(j)位置上。上述兩個操作交替進行，直到指針i與j 指向同一個位置（即i=j）為止，此時將P(i)的位置上。分割需要記憶，用棧來實現(xiàn)。二、 插入類排序法1、 簡單插入排序法所

25、謂插入排序，是指將無序序列中的各元素依次插入到已經有序的線性表中。一般來說，假設線性中前j-1元素已經有序，現(xiàn)在要將線性表中第j個元素插入到前面的有序子表中，插入過程如下：道德將第j個元素放到一個變量T中，然后從有序子表的最后一個元素（即線性表中第j-1個元素）開始，往前逐個與T進行比較，將大于T的元素均依次向后移動一個位置，直到發(fā)現(xiàn)一個元素不大于T為止，此時就將T（即原線性表中的第j個元素）插入到剛移出的空位置上，有序子表的長度就變?yōu)閖了。效率與冒泡法相同在最壞情況下，簡單插入排序需要n(n-1)/2次比較。2、 希爾排序法基本思想如下：將整個無序序列分割成若干小的子序列分別進行插入排序。子

26、序列的分割方法如下：將相隔某個增量H的元素構成一個子序列。在排序過程中，逐次減小這個增量，最后當H減到1時，進行一次插入排序，排序就完成。增量序列一般取h=n/2k(k=1,2,log2n,其中n為待排序序列的長度。其效率與增量序列有關。在最壞情況下，需要的比較次數(shù)為O（.）。三、 選擇類排序法、 簡單選擇排序法基本思想：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面；然后對剩下的子表采用同樣的方法，直到子表空為止。簡單選擇排序法在最壞情況下需要比較n(n-1)/2/次。、 堆排序法方法：（1）首先將一個無序序列建成堆。（2）然后將堆頂元素（序列中的最大項）與堆中最后一個元素交換（最

27、大項應該在序列的最后）。不考慮已經換到最后的那個元素，只考慮前n-1個元素構成的子序，顯然，該子序列已不是堆，但左、右子樹仍為堆，可以將該子序列調事為堆。反復做第（2）步，真到剩下的子序列為空為止。適用規(guī)模較大的線性表，在最壞情況下，堆排序需要比較的次數(shù)為O（nlog2n）。習題一一、選擇題1、算法的時間復雜度是指（ ）A）執(zhí)行算法程序所需要的時間 B）算法程序的長度C）算法執(zhí)行過程中所需要的基本運算次數(shù) D）算法程序中的指令條數(shù)2、算法的窨復雜度是指（ ）A、算法程序的長度 B、算法程序中的指令條數(shù)C、算法程序所占的存儲空間 D、算法執(zhí)行過程中所需要的存儲空間3、下列敘述中正確的是（ ）A、

28、線性表是線性結構 B、材與隊列是非線性結構C、線性鏈表是非線性結構 D、二叉樹是線性結構4、數(shù)據(jù)的存儲結構是指（ ）A、數(shù)據(jù)所占的存儲空間量 B、數(shù)據(jù)的邏輯結構在計算機中的表示C、數(shù)據(jù)在計算機中的順序存儲方式 D、存儲在外存中的數(shù)據(jù)5、下列關于隊列的敘述中正確的是（ ）A、在隊列中只能插入數(shù)據(jù) B、在隊列中只能刪除數(shù)據(jù)C、隊列是先進先出的線性表 D、隊列是先進后出的線性表6、下列關于棧的敘述中正確的是（ ）A、在棧中只能插入數(shù)據(jù) B、在棧中只能刪除數(shù)據(jù)C、棧是先進先出的線性表 D、棧是先進后出的線性表7、設有下列二叉樹：對此二叉樹中序遍歷的結果為A、ABCDEF B、DBEAFC C、ABDE

29、CF D、DEBFCA8、在深度為5的滿二叉樹中，葉子結點的個數(shù)為（ ）A、32 B、31 C、16 D、159、對長度為 n的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為（ ）A、 n+1 B、n C、(n+1)/2 D、n/210、設樹T的度為4，其中度為1，2，3，4的結點個數(shù)分別為4，2，1，1。則T中的葉子結點數(shù)為（ ）A、8 B、7 C、6 D、5二、填空題1、在長度為n 的有序線性表中進行二分查找，需要的比較次數(shù)為 。2、設一棵完全二叉共有700個結點，則在該二叉樹中有 個葉子結點。3、設一棵二叉樹中序遍歷結果為DBEAFC ，前序遍歷結果為ABDECF，則后序遍歷結果為

30、。4、在最壞情況下，冒泡排序的時間復雜度為 。5、在一個容量為15的循環(huán)隊列中，若頭指針front=6，尾指針rear=9，則該循環(huán)隊列中共有 個元第2章 程序設計基礎21 程序設計方法與風格就程序設計方法和技術的發(fā)展而言，主要經過了結構化程序設計和面向對象的程序設計階段。一般來講。程序設計風格是指編寫程序時所表現(xiàn)出的特點、習慣和邏輯思路。程序是由人來編寫的，為了測試和維護程序，往往還要新聞記者和跟蹤程序，因此程序設計的風格總體而言應該強調得意和清晰，程序必須是可以理解的。要形成良好的程序設計風格，主要應注重和考慮下述一些因素。1、 源程序文檔化2、 源程序文檔化應考慮如下幾點：（1） 符號名

31、的命名：符號名的命名應具有一定的實際含義，以便于對程序功能的理解。（2） 程序注釋：下克的注釋能夠幫助讀者理解程序。（3） 禮堂組織：為使程序的結構一目了然，可以在程序中利用空格、空行、縮進待技巧使程序層次清晰。2、數(shù)據(jù)說明的方法在編寫程序時，需要注意數(shù)據(jù)說明的風格，以便使程序中的數(shù)據(jù)說明更易于理解和維護。一般應注意如下幾點：（1） 數(shù)據(jù)說明的次序規(guī)范化鑒于程序理解、新聞記者和維護的需要，使數(shù)據(jù)說明次序固定，可以使數(shù)據(jù)的發(fā)生容易查找，也有利于測試、排錯和維護。（2） 說明語句中變量安排有序化。當一個說明語句說明多個變量時，變量按照字母順序為好。（3） 使用注釋來說明復雜數(shù)據(jù)的結構。3、 語句的

32、結構程序應該簡單易懂，語句構造應該簡單直接，不應該為提高效率而把語句復雜化。一般應注意如下：（1） 在一行內只寫一條語句；（2） 程序編寫應優(yōu)先考慮清晰性；（3） 除非對效率有特殊要求，程序編寫要做清晰第一，效率第二；（4） 首先要保證程序正確，然后才要求提高速度；（5） 避免使用臨時變量而使程序的可讀性下降；（6） 避免不必要的轉移；（7） 盡可能使用庫函數(shù)；（8） 避免采用復雜的條件語句；（9） 盡量減少使用“否定”條件的條件語句；（10） 數(shù)據(jù)結構要有利于程序的簡化；（11） 要模塊化，使模塊功能盡可能單一化；（12） 利用住處隱蔽，確保每一個模塊的獨立性；（13） 從數(shù)據(jù)出發(fā)去構造程序

33、；（14） 不要修補不好的程序，要重新編寫；4、輸入和輸出無論是批處理的輸入和輸出方式，還是交互式的輸入和輸出方式，在設計和編程時都應該考慮如下原則：（1） 對所有的輸入數(shù)據(jù)都要檢驗數(shù)據(jù)的合法性；（2） 檢查輸入項的各種重要組合的合理性；（3） 輸入格式要簡單，以使得輸入的步驟和操作盡可能簡單；（4） 輸入數(shù)據(jù)時，應允許使用自由格式；（5） 應允許缺省值；（6） 輸入一批數(shù)據(jù)時，最好使用輸入結束標志；（7） 在以交互式輸入/輸出方式進行輸入時，要在屏幕上使用提示符明確提示輸入的請求，同時在數(shù)據(jù)輸入過程中的輸入結束時，應在屏幕上給出狀態(tài)信息。（8） 當程序設計語言對輸入格式有嚴格要求時，應保持輸

34、入格式與輸入語句的一致性；給所有的輸入出加注釋，并設計輸出報表格式。22結構化程序設計一、結構化程序設計的原則結構化程序設計方法的主要原則可以概括為自頂向下，逐步求精，模塊化，限制使用goto語句。1、 自頂向下：程序設計時，應先考慮總體，后考慮細節(jié)；先考慮全局目標，后考慮局部目標。不要一開始就過多追求眾多的細節(jié)，先從最上層總目標開始設計，逐步使問題具體化。2、 逐步求精：對復雜問題，應設計一些子目標作過渡，逐步細化。3、 模塊化：一個復雜問題，肯定是由若干稍簡單的問題構成。模塊化是把程序要解決的總目標分解為分目標，再進一步分解為具體的小目標，把每個小目標稱為一個模塊。4、 限制使用goto語

35、句使用goto語句經實驗證實：（1）濫用GOTO語句確實有害，應晝避免；（2）完全避免使用GOTO語句也并非是個明智的方法，有些地方使用GOTO語句，會使程序流程更清楚、效率更高；（3）爭論的焦點不應該放在是否取消GOTO語句，而應該放在用什么樣的程序結構上。其中最關鍵的是，肯定以提高程序清晰性為目標的結構化方法。二、結構化程序的基本結構與特點1、順序結構：順序結構是簡單的程序設計，它是最基本、最常用的結構，所謂順序執(zhí)行，就是按照程序語句行的自然順序，一條語句一條語句地執(zhí)行程序程序。2、選擇結構：選擇結構又稱為分支結構，它包括簡單選擇和多分支選擇結構，這種結構可以根據(jù)設定的條件，判斷應該選擇哪

36、一條分支來執(zhí)行相應的語句序列。3、重復結構：重復結構又稱為循環(huán)結構，它根據(jù)給定的條件，判斷是否需要重復執(zhí)行某一相同的或類似的程序段，利用重復結構可簡化大量的程序行。分為兩類：一是先判斷后執(zhí)行，一是先執(zhí)行后判斷。優(yōu)點：一是程序易于理解、使用和維護。二是編程工作的效率，降低軟件開發(fā)成本。三、結構化程序設計原則和方法的應用要注意把握如下要素：1、 使用程序設計語言中的順序、選擇、循環(huán)等有限的控制結構表示程序的控制邏輯。2、 選用的控制結構只準許有一個入口和一個出口；3、 程序語句組成容易識別的塊，每塊只有一個入口和一個出口；4、 復雜結構應該嵌套的基本控制結構進行組合嵌套來實現(xiàn)；5、 語言中所沒有的

37、控制結構，應該采用前后一致的方法來模擬；6、 嚴格控制GOTO語句的使用。其意思是指：（1） 用一個非結構化的程序設計語言去實現(xiàn)一個結構化的構造；（2） 若不使用GOTO語句會使功能模糊；（3） 在某種可以改善而不損害程序可讀性的情況下。 23面向對象的程序設計一、關于面向對象方法面向對象方法的本質，就是主張從客觀世界固有的事物出發(fā)來構造系統(tǒng)，提倡用人類在現(xiàn)實生活中常用的思維方法來認識、理解和描述客觀事物，強調最終建立的系統(tǒng)能夠映射問題域，也就是說，系統(tǒng)中的對象以及對象之間的關系能夠如實地反映問題域中固有事物及其關系。優(yōu)點：1、與人類習慣的思維方法一致面向對象方法和技術以對象為核心。對象是由數(shù)

38、據(jù)和容許的操作組成的封裝體，與客觀實體有直接的關系。對象之間通過傳遞消息互相聯(lián)系，以模擬現(xiàn)實世界中不同事物彼此之間的聯(lián)系。面向對象的設計方法與傳統(tǒng)的面向過程的方法有本質不同，這種方法的基本原理是：使用現(xiàn)實世界的概念抽象地思考問題從而自然地解決問題。它強調模擬現(xiàn)實世界中的概念而不強調算法，它鼓勵開發(fā)者在軟件開發(fā)的絕大部分過程中都用應用領域的要領去思考。2、穩(wěn)定性好3、可重用性好軟件重用是指在不同的軟件開發(fā)過程中重復作用相同或相似軟件元素的過程。重用是提高軟件生產率的最主要的方法。4、易于開發(fā)大型軟件產品5、可維護性好（1）用面向對象的方法開發(fā)的軟件穩(wěn)定性比較好（2）用面向對象的方法開發(fā)的軟件比較

39、容易修改；（3）用面向對象的方法開發(fā)的軟件比較容易理解。（4）易于測試和調試。二、面向對象方法的基本概念1、對象（object）對象是面向對象方法中最基本的概念。對象可以用來表示客觀世界中的任何實體，也就是說，應用領域中有意義的、與所要解決的問題有關系的任何事物都可以作為對象，它既可以是具體的物理實體的抽象，也可以是人為的概念，或者是任何有明確邊界的意義的東西?？傊?，對象是對問題域中某個實體的抽象，設立某個對象就反映軟件系統(tǒng)保存有關它的信息并具有與它進行交互的能力。面向對象的程序設計方法中涉及的對象是系統(tǒng)中用來描述客觀事物的一個實體，是構成系統(tǒng)的一個基本單位，它由一組表示其靜態(tài)特征的屬性和它可

40、執(zhí)行的一組操作組成。對象可以做的操作表示它的動態(tài)行為，在面向對象分析和面向對象設計中，通常把對象的操作也稱為方法或服務。屬性即對象所包含的信息，它在設計對象時確定，一般只能通過掛靠對象的操作來改變。操作描述了對象執(zhí)行的功能，若通過消息傳遞，還可以為其他對象使用。操作的過程對外是封閉的，即用戶只能看到這一操作實施后的結果。這相當于事先已經設計好的各種過程，只需要調用就可以了，用戶不必去關心這一過程是如何編寫的。事實上，這個過程已經封裝在對象中，用戶也看不到。對的這一特性即是對象的封裝性。對象有如下一些基本特點：（1） 標識惟一性。指對象是可區(qū)分的，并且由對象有的內在本質來區(qū)分，而不是通過描述來區(qū)

41、分。（2） 分類性。指可以將具有相同屬性的操作的對象抽象成類。（3） 多太性。指同一個操作可以是不同對象的行為。（4） 封裝性。從外面看只能看到對象的外部特性，即只需知道數(shù)據(jù)的取值范圍和可以對該數(shù)據(jù)施加的操作，根本無需知道數(shù)據(jù)的具體結構以及實現(xiàn)操作的算法。對象的內部，即處理能力的實行和內部狀態(tài)，對外是不可見的。從外面不能直接使用對象的處理能力，也不能直接修改其內部狀態(tài)，對象的內部狀態(tài)只能由其自身改變。（5） 模塊獨立性好。對象是面向對象的軟件的基本模塊，它是由數(shù)據(jù)及可以對這些數(shù)據(jù)施加的操作所組成的統(tǒng)一體，而且對象是以數(shù)據(jù)為中心的，操作圍繞對其數(shù)據(jù)所需做的處理來設置，沒有無關的操作從模塊的獨立性

42、考慮，對象內部各種元素彼此結合得很緊密，內聚性強。2、類（Class）和實例(Instance)將屬性、操作相似的對象歸為類，也就是說，類是具有共同屬性、共同方法的對象的集合。所以，類是對象的抽象，它描述了屬于該對象類型的所有對象的性質，而一個對象則是其對應類的一個實例。要注意的是，當使用“對象”這個術語時，既可以指一個具體的對象，也可以泛指一般的對象，但是，當使用“實例”這個術語時，必然是指一個具體的對象。例如：Integer是一個整數(shù)類，它描述了所有整數(shù)的性質。因此任何整數(shù)都是整數(shù)類的對象，而一個具體的整數(shù)“123”是類Integer的實例。由類的定義可知，類是關于對象性質的描述，它同對象

43、一樣，包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。3、消息（Message）面向對象的世界是通過對象與對象間彼此的相互合作來推動的，對象間的這種相互合作需要一個機制協(xié)助進行，這樣的機制稱為“消息”。消息是一個實例與另一個實例之間傳遞信息，它請示對象執(zhí)行某一處理或回答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流的控制流。消息的使用類似于函數(shù)調用，消息中指定了某一個實例，一個操作名和一個參數(shù)表（可空）。接收消息的實例執(zhí)行消息中指定的操作，并將形式參數(shù)數(shù)與參數(shù)表中相應的值結合起來。消息傳遞過程中，由發(fā)送消息的對象（發(fā)送對象）的觸發(fā)操作產生輸出結果，作為消息傳送至接受消息的對象（接受對象），引發(fā)接受消息的對象一系列的

44、操作。所傳送的消息實質上是接受對象所具有的操作/方法名稱，有時還包括相應參數(shù)。消息中只包含傳遞者的要求，它告訴接受者需要做哪些處理，但并不指示接受者應該怎樣完成這些處理。消息完全由接受者解釋，接受者獨立決定采用什么方式完成所需的處理，發(fā)送者對接受者不起任何控制作用。一個對象能夠接受不同形式、不同內容的多個消息；相同形式的消息可以送往不同的對象，不同的對象對于形式相同的消息可以有不同的解釋，能夠做出不同的反映。一個對象可以同時往多個對象傳遞信息，兩個對象也可以同時向某個對象傳遞消息。例如，一個汽車對象具有“行駛”這項操作，那么要讓汽車以時速50公里行駛的話，需傳遞給汽車對象“行駛”及“時速50公

45、里”的消息。通常，一個消息由下述三部分組成：（1） 接收消息的對象的名稱；（2） 消息標識符（也稱為消息名）；（3） 零個或多個參數(shù)。4、 繼承（Inheritance）繼承是面向對象的方法的一個主要特征。繼承是使用己有的類定義作為基礎建立新類的定義技術。已有的類可當作基類來引用，則新類相應地可當作派生類來引用。廣義地說，繼承是指能夠直接獲得已有的性質和特征，而不必重復定義它們。面向對象軟件技術的許多強有力的功能和突出的優(yōu)點，都來源于把類組成一個層次結構的系統(tǒng)：一個類的上層可以有父類，下層可以有子類。這種層次結構系統(tǒng)的一個重要性質是繼承性，一個類直接繼承其父類的描述（數(shù)據(jù)和操作）或特性，子類自

46、動地共享基類中定義的數(shù)據(jù)和方法。繼承具有傳遞性，如果類C繼承類B，類B繼承類A，則類C繼承類A。因此一個類實際上繼承了它上層的全部基類的特性，也就是說，屬于某類的對象除了具有該類所定義的特性外，還具有該類上層全部基類定義的特性。繼承分為單繼承與多重繼承。單繼承是指，一個類只允許有一個父類，即類等級為樹形結構。多重繼承是指，一個類允許有多個父類。多重繼承的類可以組合多個父類的性質構成所需要的性質。因此，功能更強，使用更方便；便是，使用多重繼承時要注意避免二義性。繼承性的優(yōu)點是，相似的對象可以共享程序代碼和數(shù)據(jù)結構，從而大大減少了程序中的冗余信息，提高軟件的可重用性，便于軟件個性維護。此外，繼承性

47、便利用戶在開發(fā)新的應用系統(tǒng)時不必完全從零開始，可以繼承原有的相似系統(tǒng)的功能或者從類庫中選取需要的類，再派生出新的類以實現(xiàn)所需要的功能。5、 多太性（Polymorphism）對象根據(jù)所接受 的消息而做出動作，同樣的消息被不同的對象接受時可導致完全不同的行動，該現(xiàn)象稱為多態(tài)性。在面向對象的軟件技術中，多態(tài)性是指類對象可以像父類對象那樣使用，同樣的消息既可以發(fā)送給父類對象也可以發(fā)送給子類對象。多態(tài)性機制不僅增加了面向對象軟件系統(tǒng)的靈活性，進一步減少了信息冗余，而且顯著地提高了軟件的可重用性和可擴充性。當擴充系統(tǒng)功能增加新的實體類型時，只需派生出與新實體類相應的新的子類，完全無需修改原有的程序代碼，

48、甚至不需要重新編譯原有的程序。利用多態(tài)性，用戶能夠發(fā)送一般形式的消息，而將所有的實現(xiàn)細節(jié)都留給接受消息的對象。 第3章 軟件工程基礎31軟件工程基本概念一、軟件定義與軟件特點計算機軟件是計算機系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關文檔的完整集合?；?，程序是軟件開發(fā)人員根據(jù)用戶需求開發(fā)的用程序設計語言描述的、適合計算機執(zhí)行的指令（語句）序列。數(shù)據(jù)是使程序能正常操縱信息的數(shù)據(jù)結構。文檔是與程序開發(fā)、維護和使用有關的圖文資料?？梢娷浖蓛刹糠纸M成：一是機器可執(zhí)行的程序和數(shù)據(jù)；二是機器不可執(zhí)行的，與軟件開發(fā)、運行、維護、使用等有關的文檔。國標（GB）中對計算機軟件的定義為：與計算機系

49、統(tǒng)的操作有關的計算機程序、規(guī)程、規(guī)則，以及可能有的文件、文檔及數(shù)據(jù)。軟件在開發(fā)、生產、維護和使用等方面與計算機硬件相比存在明顯的差異。深入理解軟件的定義需要了解軟件的特點：（1） 軟件是一種邏輯實體，而不是物理實體具有抽象性。（2） 軟件的生產與硬件不同，它沒有明顯的制作過程。一旦研制開發(fā)成功，可以大量拷貝同一內容的副本。所以對軟件的控制，必須著重在軟件開發(fā)方面下功夫。（3） 軟件在運行、使用期間不存在磨損、老化問題。（4） 軟件的開發(fā)運行對計算機系統(tǒng)具有依賴性，受計算機系統(tǒng)的限制這導致了軟件移植的問題。（5） 軟件復雜性高，成本昂貴。（6） 軟件開發(fā)涉及諸多的社會因素。軟件按功能可以分為：應

50、用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。應用軟件是為解決特定領域的應用而開發(fā)的軟件。系統(tǒng)軟件是計算機管理自身資源，提高計算機使用效率并為計算機用戶提供各種服務的軟件。支撐軟件是介于系統(tǒng)軟件和應用軟件之間，協(xié)助用戶開發(fā)軟件的工具性軟件，包括輔助和支持開發(fā)和維護應用軟件的工具軟件。二、軟件危機與軟件工程軟件工程概念的出現(xiàn)源自軟件危機。所謂有軟件危機四伏是泛指在計算機軟件開發(fā)和維護過程中所遇到的嚴重問題。實際上，幾科所有的軟件都不同程度地存在這些問題。隨著計算機技術的發(fā)展和應用領域的擴大，計算機硬件性能/價格比和質量穩(wěn)步提高，軟件規(guī)模越來越大，復雜程度不斷增加，軟件成本逐年上升，質量沒有可靠的保證

51、，軟件已成為計算機科學發(fā)展的“瓶頸”。具體地說，在軟件開發(fā)和維護過程中，軟件危機主要表現(xiàn)在：（1） 軟件需求的增長得不到滿足。用戶對系統(tǒng)不滿意的情況經常發(fā)生。（2） 軟件開發(fā)成本和進度無法控制。開發(fā)成本超出預算，開發(fā)周期大大超過規(guī)定日期的情況經常發(fā)生。（3） 軟件質量難以保證。（4） 軟件不可維護或護程度非常低。（5） 軟件的成本不斷提高。（6） 軟件開發(fā)生產率的提高趕不上硬件的發(fā)展和應用需求的增長?？傊?，可以將軟件危機歸結為成本、質量、生產率等問題。軟件工程就是試圖用工程、科學和數(shù)學的大批量與方法研制、維護計算機軟件的有關技術及管理方法。關于軟件工程的定義，國標（GB）中指出，軟件工程是應用

52、于計算機軟件的定義、開發(fā)和維護的一整套方法、工具文檔、實踐標準的工序。1993年IEEE(Institute of Electrical &Electronic Engineers ，電氣和電子工程師學會)給出了一個更加綜合的定義：“將系統(tǒng)化的、規(guī)范的、可度量的方法應用于軟件的開發(fā)、運行和維護的過程，即將工程化應用于軟件中”。軟件工程包括3個要素：即方法、工具和過程。方法是完成軟件工程項目的技術手段；工具支持軟件的開發(fā)、管理、文檔生成；過程支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理。軟件工程的核心思想是把軟件產品看作是一個工程產品來處理。開發(fā)軟件不能只考慮開發(fā)期間的費用，而且應考慮軟件生命周期內的全部費用。因此，軟件生命周期的概念就變得特別重要。在考慮軟件費用時，不僅僅要降低開發(fā)成本，更要降低整個軟件生命周期的總成本。三、軟件工程過程與軟件生命周期1、軟件工程過程（Software Engineering Process）ISO9000定義：軟件工程過程是把輸入轉化為輸出的一組彼此相關的資源和活動。定義支持了軟件工程過程的兩方面內涵。其一，軟件工程過程是指為獲得軟件產品，在軟件工具支持下由軟件工程師完成的一系列軟件工程活動?；谶@個方面，軟件工程過程通常包含4種基本活動：（1） P（plan）軟件規(guī)格說明。規(guī)定軟件的功能及其運行時的限制。（2） D（do）軟件開發(fā)。產生滿足規(guī)