(完整版)計算機二級公共基礎知識(全)(完整版)計算機二級公共基礎知識(全)(完整版)計算機二級公共基礎知識(全)1.1算法考點1算法的基本概念計算機解題的過程實際上是在實施某種算法，這種算法稱為計算機算法。算法（algorithm）是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，同時是明確的；此順序?qū)⒃谟邢薜拇螖?shù)后終止。算法是對特定問題求解步驟的一種描述,它是指令的有限序列，其中每一條指令表示一個或多個操作。1算法的基本特征（1)可行性(effectiveness）:針對實際問題而設計的算法，執(zhí)行后能夠得到滿意的結(jié)果。(2）確定性(definiteness)：算法中的每一個步驟都必須有明確的定義，不允許有模棱兩可的解釋和多義性.（3）有窮性(finiteness)：算法必需在有限時間內(nèi)做完，即算法必需能在執(zhí)行有限個步驟之后終止。(4)擁有足夠的情報:要使算法有效必需為算法提供足夠的情報當算法擁有足夠的情報時，此算法才最有效的；而當提供的情報不夠時，算法可能無效。2算法的基本要素（1)算法中對數(shù)據(jù)的運算和操作:每個算法實際上是按解題要求從環(huán)境能進行的所有操作中選擇合適的操作所組成的一組指令序列。計算機可以執(zhí)行的基本操作是以指令的形式描述的.一個計算機系統(tǒng)能執(zhí)行的所有指令的集合，稱為該計算機系統(tǒng)的指令系統(tǒng)。計算機程序就是按解題要求從計算機指令系統(tǒng)中選擇合適的指令所組成的指令序列在一般的計算機系統(tǒng)中，基本的運算和操作有以下4類：①算術運算：主要包括加、減、乘、除等運算;②邏輯運算：主要包括“與”、“或”、“非”等運算；③關系運算：主要包括“大于”、“小于”、“等于"、“不等于"等運算;④數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。(2）算法的控制結(jié)構(gòu)：一個算法的功能不僅僅取決于所選用的操作，而且還與各操作之間的執(zhí)行順序有關。算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。算法的控制結(jié)構(gòu)給出了算法的基本框架,它不僅決定了算法中各操作的執(zhí)行順序,而且也直接反映了算法的設計是否符合結(jié)構(gòu)化原則.描述算法的工具通常有傳統(tǒng)流程圖、N—S結(jié)構(gòu)化流程圖、算法描述語言等。一個算法一般都可以用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)組合而成。（3)算法設計的基本方法計算機算法不同于人工處理的方法，下面是工程上常用的幾種算法設計，在實際應用時,各種方法之間往往存在著一定的聯(lián)系。(1)列舉法列舉法是計算機算法中的一個基礎算法.列舉法的基本思想是，根據(jù)提出的問題,列舉所有可能的情況,并用問題中給定的條件檢驗哪些是需要的,哪些是不需要的。列舉法的特點是算法比較簡單。但當列舉的可能情況較多時，執(zhí)行列舉算法的工作量將會很大。因此，在用列舉法設計算法時,使方案優(yōu)化，盡量減少運算工作量，是應該重點注意的.（2)歸納法歸納法的基本思想是,通過列舉少量的特殊情況，經(jīng)過分析,最后找出一般的關系。從本質(zhì)上講，歸納就是通過觀察一些簡單而特殊的情況，最后總結(jié)出一般性的結(jié)論。(3)遞推遞推是指從已知的初始條件出發(fā),逐次推出所要求的各中間結(jié)果和最后結(jié)果。其中初始條件或是問題本身已經(jīng)給定,或是通過對問題的分析與化簡而確定。遞推本質(zhì)上也屬于歸納法，工程上許多遞推關系式實際上是通過對實際問題的分析與歸納而得到的,因此，遞推關系式往往是歸納的結(jié)果。對于數(shù)值型的遞推算法必須要注意數(shù)值計算的穩(wěn)定性問題。（4）遞歸人們在解決一些復雜問題時，為了降低問題的復雜程度(如問題的規(guī)模等），一般總是將問題逐層分解，最后歸結(jié)為一些最簡單的問題.這種將問題逐層分解的過程，實際上并沒有對問題進行求解,而只是當解決了最后那些最簡單的問題后，再沿著原來分解的逆過程逐步進行綜合，這就是遞歸的基本思想.遞歸分為直接遞歸與間接遞歸兩種。(5）減半遞推技術實際問題的復雜程度往往與問題的規(guī)模有著密切的聯(lián)系。因此，利用分治法解決這類實際問題是有效的。工程上常用的分治法是減半遞推技術.所謂“減半”，是指將問題的規(guī)模減半，而問題的性質(zhì)不變；所謂“遞推",是指重復“減半”的過程。(6）回溯法在工程上，有些實際問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，并且也不能進行無限的列舉。對于這類問題,一種有效的方法是“試”.通過對問題的分析,找出一個解決問題的線索，然后沿著這個線索逐步試探，若試探成功，就得到問題的解，若試探失敗,就逐步回退，換別的路線再逐步試探。4算法設計的要求通常一個好的算法應達到如下目標：(l)正確性（correctness)正確性大體可以分為以下4個層次：①程序不含語法錯誤；②程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；③程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果;④程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。(2）可讀性(readability）算法主要是為了方便入的閱讀與交流，其次才是其執(zhí)行?？勺x性好有助于用戶對算法的理解；晦澀難懂的程序易于隱藏較多錯誤,難以調(diào)試和修改。（3)健壯性(robustness）當輸入數(shù)據(jù)非法時，算法也能適當?shù)刈龀龇磻蜻M行處理，而不會產(chǎn)生莫名其妙的輸出結(jié)果。（4)效率與低存儲量需求效率指的是程序執(zhí)行時，對于同一個問題如果有多個算法可以解決，執(zhí)行時間短的算法效率高;存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間考點2算法的復雜度1算法的時間復雜度算法的時間復雜度，是指執(zhí)行算法所需要的計算工作量。同一個算法用不同的語言實現(xiàn)，或者用不同的編譯程序進行編譯，或者在不同的計算機上運行，效率均不同。這表明使用絕對的時間單位衡量算法的效率是不合適的。撇開這些與計算機硬件、軟件有關的因素，可以認為一個特定算法“運行工作量”的大小,只依賴于問題的規(guī)模（通常用整數(shù)n表示)，它是問題的規(guī)模函數(shù)。即算法的工作量=f(n）例如，在N×N矩陣相乘的算法中,整個算法的執(zhí)行時間與該基本操作（乘法)重復執(zhí)行的次數(shù)n3成正比，也就是時間復雜度為n3,即f（n)=O(n3)在有的情況下，算法中的基本操作重復執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。例如在起泡排序的算法中，當要排序的數(shù)組a初始序列為自小至大有序時,基本操作的執(zhí)行次數(shù)為氏當初始序列為自大至小有序時,基本操作的執(zhí)行次數(shù)為n(n—1）/2。對這類算法的分析,可以采用以下兩種方法來分析。(1）平均性態(tài)（AverageBehavior）所謂平均性態(tài)是指各種特定輸入下的基本運算次數(shù)的加權平均值來度量算法的工作量。設x是所有可能輸入中的某個特定輸入，p（x）是x出現(xiàn)的概率(即輸入為x的概率）,t(x）是算法在輸入為x時所執(zhí)行的基本運算次數(shù)，則算法的平均性態(tài)定義為其中Dn表示當規(guī)模為n時，算法執(zhí)行的所有可能輸入的集合。(2)最壞情況復雜性(Worst—caseComplexity）所謂最壞情況分析，是指在規(guī)模為n時,算法所執(zhí)行的基本運算的最大次數(shù)。2算法的空間復雜度算法的空間復雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行中所需要的額外空間.其中額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間。如果額外空間量相對于問題規(guī)模來說是常數(shù)，則稱該算法是原地（inplace）工作的。在許多實際問題中，為了減少算法所占的存儲空間，通常采用壓縮存儲技術，以便盡量減少不必要的額外空間?？键c3數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)（datastructure)是指相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合，即數(shù)據(jù)的組織形式。數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學科，主要研究和討論以下三個方面:（l)數(shù)據(jù)集合中個數(shù)據(jù)元素之間所固有的邏輯關系,即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2)在對數(shù)據(jù)元素進行處理時，各數(shù)據(jù)元素在計算機中的存儲關系，即數(shù)據(jù)的存儲結(jié)構(gòu)；(3)對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。討論以上問題的日的是為了提高數(shù)據(jù)處理的效率，所謂提高數(shù)據(jù)處理的效率有兩個方面:(l)提高數(shù)據(jù)處理的速度；(2）盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計算機存儲空間.數(shù)據(jù)（data）:是對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(shù)據(jù)元素(dataelement)：是數(shù)據(jù)的基本單位,在計算機程序中通常作為一個整體進行考慮和處理.數(shù)據(jù)對象（dataobject）:是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集.在一般情況下,在具有相同特征的數(shù)據(jù)元素集合中，各個數(shù)據(jù)元素之間存在有某種關系(即連續(xù)），這種關系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。在數(shù)據(jù)處理領域中,通常把數(shù)據(jù)元素之間這種固有的關系簡單地用前后件關系(或直接前驅(qū)與直接后繼關系）來描述。前后件關系是數(shù)據(jù)元素之間的一個基本關系，但前后件關系所表示的實際意義隨具體對象的不同而不同。一般來說,數(shù)據(jù)元素之間的任何關系都可以用前后件關系來描述。1數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指反映數(shù)據(jù)元素之間的關系的數(shù)據(jù)元素集合的表示.更通俗地說，數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。所謂結(jié)構(gòu)實際上就是指數(shù)據(jù)元素之間的前后件關系.一個數(shù)據(jù)結(jié)構(gòu)應包含以下兩方面信息：(1)表示數(shù)據(jù)元素的信息；（2)表示各數(shù)據(jù)元素之間的前后件關系。數(shù)據(jù)的邏輯結(jié)果是對數(shù)據(jù)元素之間的邏輯關系的描述.它可以用一嘎數(shù)據(jù)元素的集合和定義在此集合中的若干關系來表示。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖形結(jié)構(gòu)四種。線性結(jié)構(gòu)：數(shù)據(jù)元素之間構(gòu)成一種順序的線性關系。樹型結(jié)構(gòu)：數(shù)據(jù)元素之間形成一種樹型的關系數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素：一是數(shù)據(jù)元素的集合,通常記為D;二是D上的關系，它反映了數(shù)據(jù)元素之間的前后件關系，通常記為R。一個數(shù)據(jù)結(jié)構(gòu)可以表示成B=（C,R）其中B表示數(shù)據(jù)結(jié)構(gòu).為了反映D中各元素之間的前后件關系，一般用二元組來表示.例如，復數(shù)是一種數(shù)據(jù)結(jié)構(gòu)，在計算機科學中，復數(shù)可取如下定義：B=（C,R）其中，C是含有兩個實數(shù)的集合{c1,c2｝;R是定義在集合C上的一種關系{〈c1,c2〉｝,其中有序偶{〈c1,c2>｝表示c1是復數(shù)的實部，c2是復數(shù)的虛部.2數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式，稱為數(shù)據(jù)的存儲結(jié)構(gòu)（也稱為數(shù)據(jù)的物理結(jié)構(gòu)）。由于數(shù)據(jù)元素在計算機存儲空間中的位置關系可能與邏輯關系不同，因此，為了表示存放在計算機存儲空間中的各數(shù)據(jù)元素之間的邏輯關系（即前后件關系），在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關系的信息。一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu),常用的結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)而采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在進行數(shù)據(jù)處理是，選擇合適的存儲結(jié)構(gòu)是很重要的?？键c4數(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é)點。在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點稱為根結(jié)點；沒有后件的結(jié)點稱為終端結(jié)點(也稱為葉子結(jié)點)。一個數(shù)據(jù)結(jié)構(gòu)中的結(jié)點可能是在動態(tài)變化的.根據(jù)需要或在處理過程中，可以在一個數(shù)據(jù)結(jié)構(gòu)中增加一個新結(jié)點(稱為插入運算），也可以刪除數(shù)據(jù)結(jié)構(gòu)中的某個結(jié)點(稱為刪除運算）。插入與刪除是對數(shù)據(jù)結(jié)構(gòu)的兩種基本運算.除此之外,對數(shù)據(jù)結(jié)構(gòu)的運算還有查找、分類、合并、分解、復制和修改等.考點5線性結(jié)構(gòu)與非線性結(jié)構(gòu)如果在一個數(shù)據(jù)結(jié)構(gòu)中一個數(shù)據(jù)元素都沒有，則稱該數(shù)據(jù)結(jié)構(gòu)為空的數(shù)據(jù)結(jié)構(gòu)。根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關系的復雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。非空數(shù)據(jù)結(jié)構(gòu)滿足:(l)有且只有一個根結(jié)點;(2）每一個結(jié)點最多有一個前件，也最多有一個后件.則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱為線性表。一個線性表是n個數(shù)據(jù)元素的有限序列。至于每個元素的具體含義,在不同的情況下各不相同，它可以是一個數(shù)或一個符號，也可以是一頁書,甚至其他更復雜的信息。如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，稱之為非線性結(jié)構(gòu)。線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。對于空的數(shù)據(jù)結(jié)構(gòu)，如果對該數(shù)據(jù)結(jié)構(gòu)的運算是按線性結(jié)構(gòu)的規(guī)則來處理的，則屬于線性結(jié)構(gòu)；否則屬于非線性結(jié)構(gòu)。1.3線性表及順序存儲結(jié)構(gòu)考點6線性表的定義線性表是n（n≥0）個元素構(gòu)成的有限序列(a1，a2，…，an）.表中的每一個數(shù)據(jù)元素，除了第一個外,有且只有一個前件,除了最后一個外，有且只有一個后件。即線性表是一個空表，或可以表示為（a1，a2，…，an）其中ai(i=1，2,…，n）是屬于數(shù)據(jù)對象的元素，通常也稱其為線性表中的一個結(jié)點。其中，每個元素可以簡單到是一個字母或是一個數(shù)據(jù)，也可能是比較復雜的由多個數(shù)據(jù)項組成的。在復雜的線性表中,由若干數(shù)據(jù)項組成的數(shù)據(jù)元素稱為記錄(record)，而由多個記錄構(gòu)成的線性表又稱為文件（file）。在非空表中的每個數(shù)據(jù)元素都有一個確定的位置，如a1是第一個元素,an是最后一個數(shù)據(jù)元素，ai是第i個數(shù)據(jù)元素，稱i為數(shù)據(jù)元素ai在線性表中的位序。非空線性表有如下一些結(jié)構(gòu)特征：（1）有且只有一個根結(jié)點a1，它無前件；(2）有且只有一個終端結(jié)點an,它無后件；(3）除根結(jié)點與終端結(jié)點外，其他所有結(jié)點有且只有一個前件，也有且只有一個后件。線性表中結(jié)點的個數(shù)n稱為線性表的長度。當n=0時稱為空表。考點7線性表的順序存儲結(jié)構(gòu)線性表的順序表指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。線性表的順序存儲結(jié)構(gòu)具備如下兩個基本特征:(l）線性表中的所有元素所占的存儲空間是連續(xù)的；(2)線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的.假設線性表的每個元素需要占用k個存儲單元，并以所占的存儲位置ADR(ai+1）和第i個數(shù)據(jù)元素的存儲位置ADR(ai）之間滿足下列關系：ADR（ai+1）=ADR(ai)+k線性表第i個元素ai的存儲位置為ADR(ai)=ADR（a1）+(i-1)×k式中ADR(ai)是線性表的第一個數(shù)據(jù)元素a，的存儲位置，通常稱做線性表的起始位置或基址。線性表的這種表示稱做線性表的順序存儲結(jié)構(gòu)或順序映像，這種存儲結(jié)構(gòu)的線性表為順序表。表中每一個元素的存儲位置都和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的位序成正比例的常數(shù)。如圖1-4所示。由此只要確定了存儲線性表的起始位置，線性表中任一數(shù)據(jù)元素都可以隨機存取,所以線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)。在程序設計語言中,通常定義一個一維數(shù)組來表示線性表的順序存儲空間。在用一維數(shù)組存放線性表時，該一維數(shù)組的長度通常要定義得比線性表的實際長度大一些，以便對線性表進行各種運算，特別是插入運算。在線性表的順序存儲結(jié)構(gòu)下，可以對線性表做以下運算：(l)在線性表的指定位置處加入一個新的元素（即線性表的插入)；（2)在線性表中刪除指定的元素(即線性表的刪除)；（3）在線性表中查找某個（或某些）特定的元素（即線性表的查找)；(4)對線性表中的元素進行整序（即線性表的排序）;(5）按要求將一個線性表分解成多個線性表(即線性表的分解)；（6）按要求將多個線性表合并成一個線性表（即線性表的合并）；(7)復制一個線性表（即線性表的復制）；（8)逆轉(zhuǎn)一個線性表（即線性表的逆轉(zhuǎn)）等?？键c8順序表的插入運算線性表的插入運算是指在表的第i（1≤i≤n+l）個位置上，插入一個新結(jié)點x，使長度為n的線性表（a1,…，ai—1，ai，…,an）變成長度為n+1的線性表（a1，…,ai-1，x，ai，…,an）現(xiàn)在分析算法的復雜度。這里的問題規(guī)模是表的長度，設它的值為n。該算法的時間主要花費在循環(huán)結(jié)點后移語句上,該語句的執(zhí)行次數(shù)(即移動結(jié)點的次數(shù))是n—i+1。由此可看出，所需移動結(jié)點的次數(shù)不僅依賴于表的長度，而且還與插入位置有關.當i=n+1時,由于循環(huán)變量的終值大于初值，結(jié)點后移語句將不進行；這是最好情況，其時間復雜度O(1)；當i=1時,結(jié)點后移語句,將循環(huán)執(zhí)行n次，需移動表中所有結(jié)點，這是最壞情況，其時間復雜度為O(n）.由于插入可能在表中任何位置上進行，因此需分析算法的平均復雜度。在長度為n的線性表中第i個位置上插入一個結(jié)點，令Eis(n)表示移動結(jié)點的期望值(即移動的平均次數(shù)），則在第i個位置上插入一個結(jié)點的移動次數(shù)為n-i+1。故不失一般性，假設在表中任何位置（1≤i≤n+1)上插入結(jié)點的機會是均等的，則p1=p2=p3=…=pn+1=1/(n+1)因此，在等概率插入的情況下，也就是說，在順序表上做插入運算,平均要移動表上一半的結(jié)點。當表長n較大時,算法的效率相當?shù)汀ｋm然Eis(n)中n的的系數(shù)較小，但就數(shù)量級而言，它仍然是線性級的。因此算法的平均時間復雜度為O(n）?？键c9順序表的刪除運算線性表的刪除運算是指將表的第i（1≤i≤n)個結(jié)點刪除，使長度為n的線性表：（a1,…,ai-1，ai，ai+1，…，an)變成長度為n—l的線性表(a1，…，ai-1,ai+1，…,an)該算法的時間分析與插入算法相似,結(jié)點的移動次數(shù)也是由表長n和位置i決定。若i=n，則由于循環(huán)變量的初值大于終值，前移語句將不執(zhí)行，無需移動結(jié)點；若i=1，則前移語句將循環(huán)執(zhí)行n一1次,需移動表中除開始結(jié)點外的所有結(jié)點。這兩種情況下算法的時間復雜度分別為O（1)和O(n）。刪除算法的平均性能分析與插入算法相似。在長度為n的線性表中刪除一個結(jié)點,令Ede（n)表示所需移動結(jié)點的平均次數(shù)，刪除表中第i個結(jié)點的移動次數(shù)為n—i，故式子中，pi表示刪除表中第i個結(jié)點的概率。在等概率的假設下，p1=p2=p3=…=pn=1/n由此可得:即在順序表上做刪除運算，平均要移動表中約一半的結(jié)點，平均時間復雜度也是O(n）。1.4棧和隊列考點10棧及其基本運算1什么是棧棧實際也是線性表，只不過是一種特殊的線性表。棧（Stack)是只能在表的一端進行插入和刪除運算配線性表，通常稱插入、刪除的這一端為棧頂(Top），另一端為棧底（Bottom)。當表中沒有元素時稱為空棧(棧頂元素總是后被插入的元素，從而也是最先被刪除的元素;棧底元素總是最先被插入的元素,從而也是最后才能被刪除的元素.假設棧S=(al，a2,a3，…，an）,則a1，稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3,…,an的次序進棧，退棧的第一個元素應為棧頂元素。換句話說，棧的修改是按后進先出的原則進行的.因此,棧稱為先進后出表（FILO，F(xiàn)irstInLastOut)，或“后進先出”表（LIFO，LastInFirstOut），如圖1—7所示。2棧的順序存儲及其運算（l)入棧運算：入棧運算是指在棧頂位置插入一個新元素.首先將棧頂指針加一(即top加1）,然后將元素插入到棧頂指針指向的位置。當棧頂指針已經(jīng)指向存儲空間的最后一個位置時,說明棧空間已滿,不可能再進行入棧操作.這種情況稱為?！吧弦?錯誤。如圖1-8所示。（2)退棧運算:退棧是指取出棧頂元素并賦給一個指定的變量。首先將棧頂元素（棧頂指針指向的元素)賦給一個指定的變量，然后將棧頂指針減一(即t叩減1）。當棧頂指針為。時，說明?？?不可進行退棧操作。這種情況稱為棧的“下溢”錯誤。(3）讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個指定的變量.這個運算不刪除棧頂元素，只是將它賦給一個變量，因此棧頂指針不會改變。當棧頂指針為0時,說明棧空，讀不到棧頂元素?？键c11隊列及其基本運算1什么是隊列隊列(queue)是只允許在一端刪除,在另一端插入的順序表,允許刪除的一端叫做隊頭（front)，允許插入的一端叫做隊尾(rear），當隊列中沒有元素時稱為空隊列。在空隊列中依次加入元素a1,a2，…，an之后,a1是隊頭元素，an是隊尾元素。顯然退出隊列的次序也只能是a1，a2，…，an也就是說隊列的修改是依先進先出的原則進行的。因此隊列亦稱作先進先出（FIFO，F(xiàn)irstInFirstOut)的線性表，或后進后出(LILO，LastInLastOut）的線性表。往隊列隊尾插入一個元素稱為入隊運算，從隊列的排頭刪除一個元素稱為退隊運算，如圖1-10所示。一個隊列幣。刪除個兒素后的隊列間插入元素E后的隊列2循環(huán)隊列及其運算在實際應用中，隊列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊列的形式.所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置。因此，從排頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間所有的元素均為隊列中的元素。可以將向量空間想象為一個首尾相接的圓環(huán),如圖1—12所示，并稱這種向量為循環(huán)向量，存儲在其中的隊列稱為循環(huán)隊列（CireularQueue)。在循環(huán)隊列中進行出隊、入隊操作時，頭尾指針仍要加1，朝前移動。只不過當頭尾指針指向向量上界（Queuesize-l)時，其加1操作的結(jié)果是指向向量的下界0。由于入隊時尾指針向前追趕頭指針,出隊時頭指針向前追趕尾指針，故隊空和隊滿時頭尾指針均相等。因此,我們無法通過front=rear來判斷隊列“空”還是“滿”。在實際使用循環(huán)隊列時,為了能區(qū)分隊列滿還是隊列空，通常還需增加一個標志、，、值的定義如下：當s=0時表示隊列空；當s=1時表示隊列非空。(l)入隊運算入隊運算是指在循環(huán)隊列的隊尾加入一個新元素。首先將隊尾指針進一(即rear=rear+1)，并當rear=m+l時置rear=1;然后將新元素插入到隊尾指針指向的位置。當循環(huán)隊列非空(s=l)且隊尾指針等于隊頭指針時，說明循環(huán)隊列已滿，不能進行入隊運算,這種情況稱為“上溢”.(2)退隊運算退隊運算是指在循環(huán)隊列的隊頭位置退出一個元素并賦給指定的變量.首先將隊頭指針一進一(即from=front+1)，并當front=m+1時，置front=1然后將排頭指針指向的元素賦給指定的變量。當循環(huán)隊列為空（s=0）時，不能進行退隊運算，這種情況稱為“下溢”。轉(zhuǎn)貼于:計算機二級考試_考試大【責編：daiy糾錯】1.5線性鏈表考點12線性單鏈表的結(jié)構(gòu)及其基本運算1什么是線性鏈表(l）線性表順序存儲的缺點①在一般情況下，要在順序存儲的線性表中插入一個新元素或刪除一個元素時，為了保證插入或刪除后的線性表仍然為順序存儲，則在插入或刪除過程中需要移動大量的數(shù)據(jù)元素。因此采用順序存儲結(jié)構(gòu)進行插入或刪除的運算效率很低；②當為一個線性表分配順序存儲空間后，如果出現(xiàn)線性表的存儲空間已滿,但還需要插入新的元素時棧會發(fā)生“上溢”錯誤；③計算機空間得不到充分利用，并且不便于對存儲空間的動態(tài)分配。（2）線性表鏈式的基本概念在定義的鏈表中，若只含有一個指針域來存放下一個元素地址，稱這樣的鏈表為單鏈表或線性鏈表。在鏈式存儲方式中，要求每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域。其中指針用于指向該結(jié)點的前一個或后一個結(jié)點（即前件或后件）。如圖1-13所示.2線性單鏈表的存儲結(jié)構(gòu)用一組任意的存儲單元來依次存放線性表的結(jié)點,這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點間的邏輯關系，在存儲每個結(jié)點值的同時，還必須存儲指示其后件結(jié)點的地址（或位置）信息，這個信息稱為指針（pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點結(jié)構(gòu)，鏈表正是通過每個結(jié)點的鏈域?qū)⒕€性表的n個結(jié)點按其邏輯次序鏈接在一起。由于上述鏈表的每一個結(jié)點只有一個鏈域，故將這種鏈表稱為單鏈表（SingleLinked）。顯然,單鏈表中每個結(jié)點的存儲地址是存放在其前驅(qū)結(jié)點Next域中，而開始結(jié)點無前驅(qū)，故應設頭指針HEAD指向開始結(jié)點。同時，由于終端結(jié)點無后件，故終端結(jié)點的指針域為空，即NULL。3帶鏈的棧與隊列（1)棧也是線性表，也可以采用鏈式存儲結(jié)構(gòu)。在實際應用中,帶鏈的?？梢杂脕硎占嬎銠C存儲空間中所有空閑的存儲結(jié)點,這種帶鏈的棧稱為可利用棧（2)隊列也是線性表，也可以采用鏈式存儲結(jié)構(gòu),考點13線性鏈表的基本運算線性鏈表的運算主要有以下幾個：（l）在線性鏈表中包含指定元素的結(jié)點之前插入一個新元素；(2）在線性鏈表中刪除包含指定元素的結(jié)點；（3)將兩個線性鏈表按要求合并成一個線性表；（4)將一個線性鏈表按要求進行分解;（5）逆轉(zhuǎn)線性鏈表;(6）復制線性鏈表；（7)線性鏈表的排序；（8）線性鏈表的查找。1在線性鑊表中查找指定元素在對線性鏈表進行插入或刪除的運算中，總是首先需要找到插入或刪除的位置，這就需要對線性鏈表進行掃描查找，在線性鏈表中尋找包含指定元素的前一個結(jié)點。在線性鏈表中，即使知道被訪問結(jié)點的序號a，也不能像順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā),順鏈域Next逐個結(jié)點往下搜索，直到搜索到第i個結(jié)點為止。因此，鏈表不是隨機存取結(jié)構(gòu)。在鏈表中，查找是否有結(jié)點值等于給定值x的結(jié)點,若有的話，則返回首次找到的其值為x的結(jié)點的存儲位置；否則返回NULL。查找過程從開始結(jié)點出發(fā)，順著鏈表逐個將結(jié)點的值和給定值x作比較。2線性鏈表的插入線性鏈表的插入是指在鏈式存儲結(jié)構(gòu)下的線性鏈表中插入一個新元素。插入運算是將值為X的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai—1，與ai之間.因此，我們必須首先找到ai—1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點＊p，并令結(jié)點，p的指針域指向新結(jié)點，新結(jié)點的指針域指向結(jié)點ai由線性鏈表的插入過程可以看出,由于插入的新結(jié)點取自于可利用棧，因此,只要可利用棧不空,在線性鏈表插入時總能取到存儲插入元素的新結(jié)點,不會發(fā)生“上溢”的情況。而且,由于可利用棧是公用的，多個線性鏈表可以共享它，從而很方便地實現(xiàn)了存儲空間的動態(tài)分配.另外，線性鏈表在插入過程中不發(fā)生數(shù)據(jù)元素移動的現(xiàn)象，只要改變有關結(jié)點的指針即可,從而提高了插入的效率。3多線性鏈表的刪除線性鏈表的刪除是指在鏈式存儲結(jié)構(gòu)下的線性鏈表中刪除包含指定元素的結(jié)點.刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點a的存儲地址是在其直接前趨結(jié)點ai-1，的指針域Next中，所以我們必須首先找到ai-1的存儲位置p.然后令p-〉Next指向ai的直接后件結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點a的空間.從線性鏈表的刪除過程可以看出，從線性鏈表中刪除一個元素后，不需要移動表中的數(shù)據(jù)元素，只要改變被刪除元素所在結(jié)點的前一個結(jié)點的指針域即可。另外，由于可利用棧是用于收集計算機中所有的空閑結(jié)點，因此，當從線性鏈表中刪除一個元素后，該元素的存儲結(jié)點就變?yōu)榭臻e，應將空閑結(jié)點送回到可利用棧。考點14線性雙向鏈表的結(jié)構(gòu)及其基本運算1什么是雙向鏈表在單鏈表中，從某個結(jié)點出發(fā)可以直接找到它的直接后件,時間復雜度為O(1），但無法直接找到它的互接前件；在單循環(huán)鏈表中，從某個結(jié)點出發(fā)可以直接找到它的直接后件，時間復雜度仍為O(1)，直接找到它的直接前件,時間復雜度為O(n)。有時，希望能快速找到一個結(jié)點的直接前件，這時，可以在單鏈表中的結(jié)點中增加一個指針域指向它的直接前件，這樣的鏈表，就稱為雙向鏈表(一個結(jié)點中含有兩個指針)。如果每條鏈構(gòu)成一個循環(huán)鏈表，則會得到雙向循環(huán)鏈表2雙向鏈表的基本運算(l）插入:在HEAD為頭指針的雙向鏈表中，在值為Y的結(jié)點之后插入值為X的結(jié)點，插入結(jié)點的指針變化。如圖1—20所示(若改為在值為Y的結(jié)點之前插入值為X的結(jié)點,可以做類似分析）。（2)刪除:在以HEAD為頭指針的雙向鏈表中刪除值為X的結(jié)點,刪除算法的指針變化，如圖1—21所示?？键c15循環(huán)鏈表的結(jié)構(gòu)及其基本運算單鏈表上的訪問是一種順序訪問，從其中的某一個結(jié)點出發(fā)，可以找到它的直接后件，但無法找到它的直接前件。在前面所討論的線性鏈表中，其插入與刪除的運算雖然比較方便，但還存在一個問題，在運算過程中對于空表和對第一個結(jié)點的處理必須單獨考慮,使空表與非空表的運算不統(tǒng)一。因此,我們可以考慮建立這樣的鏈表,具有單鏈表的特征，但又不需要增加額外的存貯空間，僅對表的鏈接方式稍做改變，使得對表的處理更加方便靈活。從單鏈表可知,最后一個結(jié)點的指針域為NULL，表示單鏈表已經(jīng)結(jié)束。如果將單鏈表最后一個結(jié)點的指針域改為存放鏈表中頭結(jié)點(或第一個結(jié)點)的地址，就使得整個鏈表構(gòu)成一個環(huán)，又沒有增加額外的存儲空間循環(huán)鏈表具有以下兩個特點：(1）在循環(huán)鏈表中增加了一個表頭結(jié)點，其數(shù)據(jù)域為任意或者根據(jù)需要來設置，指針域指向線性表的第一個元素的結(jié)點。循環(huán)鏈表的頭指針指向表頭結(jié)點；(2）循環(huán)鏈表中最后一個結(jié)點的指針域不是空，而是指向表頭結(jié)點。即在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈。在循環(huán)鏈表中,只要指出表中任何一個結(jié)點的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點，而線性單鏈表做不到這一點.由于在循環(huán)鏈表中設置了一個表頭結(jié)點，因此，在任何情況下，循環(huán)鏈表中至少有一個結(jié)點存在，從而使空表的運算統(tǒng)一。1。6樹與二叉樹考點16樹的定義樹是由n(n≥0）個結(jié)點組成的有限集合。若n=0,稱為空樹；若n>0，則：(1）有一個特定的稱為根（root）的結(jié)點。它只有直接后件，但沒有直接前件；(2）除根結(jié)點以外的其他結(jié)點可以劃分為m（m≥0)個互不相交的有限集合T0，T1，…，Tm—1，每個集合Ti(i=0，1，…，m—l）又是一棵樹，稱為根的子樹，每棵子樹的根結(jié)點有且僅有一個直接前件，但可以有0個或多個直接后件。樹型結(jié)構(gòu)具有如下特點:（1）助每個結(jié)點只有一個前件，稱為父結(jié)點,沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點,簡稱為樹的根；（2)每一個結(jié)點可以有多個后件,它們都稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點;(3)一個結(jié)點所擁有的后件個數(shù)稱為樹的結(jié)點度；（4)樹的最大層次稱為樹的深度。在計算機中，可以用樹結(jié)構(gòu)來表示算術表達式，用樹來表示算術表達式的原則是：(1）表達式中的每一個運算符在樹中對應一個結(jié)點，稱為運算符結(jié)點；（2）運算符的每一個運算對象在樹中為該運算符結(jié)點的子樹（在樹中的順序為從左到右)；（3)運算對象中的單變量均為葉子結(jié)點。樹在計算機中通常用多重鏈表表示.考點17二叉樹的定義及其基本性質(zhì)1什么是二叉樹二叉樹（binarytree）是由n(≥0)個結(jié)點的有限集合構(gòu)成，此集合或者為空集,或者由一個根結(jié)點及兩棵互不相交的左右子樹組成,并且左右子樹都是二叉樹.二叉樹可以是空集合，根可以有空的左子樹或空的右子樹。二叉樹不是樹的特殊情況,它們是兩個概念。二叉樹具有如下兩個特點：（1)非空二叉樹只有一個根結(jié)點；(2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。二叉樹的每個結(jié)點最多有兩個孩子,或者說，在二叉樹中,不存在度大于2的結(jié)點，并且二叉樹是有序樹(樹為無序樹)，其子樹的順序不能顛倒,因此,二叉樹有5種不同的形態(tài)在二叉樹中,一個結(jié)點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。當一個結(jié)點既沒有左子樹也沒有右子樹時,該結(jié)點即是葉子結(jié)點）2二叉樹的基本性質(zhì)性質(zhì)1：在二叉樹的第入層上至多有2k—1個結(jié)點（k≥1)。性質(zhì)2：深度為m的二叉樹至多有2m-1個結(jié)點。深度為m的二叉樹的最大的結(jié)點數(shù)是為二叉樹中每層上的最大結(jié)點數(shù)之和，由性質(zhì)1得到最大結(jié)點數(shù).性質(zhì)3:對任何一棵二叉樹，度為0的結(jié)點(即葉子結(jié)點）總是比度為2的結(jié)點多一個.如果葉子結(jié)點n0，度為2的結(jié)點數(shù)為n2，則n0=n2+l。設二叉樹中度為1的結(jié)點數(shù)為n1，二叉樹中總結(jié)點數(shù)為N，因為二叉樹中所有結(jié)點均小于或等于2，所以有N=n0+n1+n（1)再看二叉樹中的分支數(shù)，除根結(jié)點外,其余結(jié)點都有一個進入分支，設m為二叉樹中的分支總數(shù),則有N=m+1(2）又由于二叉樹中這m個分支是分別由非葉子結(jié)點射出的。其中度為1的每個結(jié)點射出1個分支，度為2的每個結(jié)點射出2個分支。因此，二叉樹中所有度為1與度為2的結(jié)點射出的分支總數(shù)為n1+2n2，而在二叉樹中，總的射出分支數(shù)應與總的進入分支數(shù)相等，即m=n1+2n2(3）將（3）代入（2）式有N=n1+2n2+1比較(1）和（4）并化簡得n0=n2+1性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度至少為［log2n]+1，其中［log2n]表示log2n的整數(shù)部分。3滿二叉樹與完全二叉樹（l)滿二叉樹滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。深度為k的二叉樹具有2k—1個結(jié)點。即在滿二叉樹的第k層上有2k-1個結(jié)點。從上面滿二叉樹定義可知,必須是二叉樹的每一層上的結(jié)點數(shù)都達到最大，否則就不是滿二叉樹。深度為m的滿二叉樹有2m—1個結(jié)點。（2)完全二叉樹完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；在最后一層上只缺少右邊的若干結(jié)點。轉(zhuǎn)貼于:計算機二級考試_考試大【責編：daiy糾錯】如果一棵具有n個結(jié)點的深度為k的二叉樹,它的每一個結(jié)點都與深度為k的滿二叉樹中編號為1～n的結(jié)點一一對應。為滿二叉樹和完全二叉樹的結(jié)構(gòu)比較。從完全二叉樹定義可知，結(jié)點的排列順序遵循從上到下、從左到右的規(guī)律。所謂從上到下，表示本層結(jié)點數(shù)達到最大后,才能放入下一層。從左到右，表示同一層結(jié)點必須按從左到右排列，若左邊空一個位置時不能將結(jié)點放入右邊.完全二叉樹除最后一層外每一層的結(jié)點數(shù)都達到最大值，最后一層只缺少右邊的若干結(jié)點。滿二叉樹也是完全二叉樹，反之完全二叉樹不一定是滿二叉樹。性質(zhì)5：具有n個結(jié)點的完全二叉樹深度為［log2n]+1或[log2（n+1）]。性質(zhì)6：如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號(從第1層到第［log2n］+1層，每層從左到右），則對任一結(jié)點i(1≤i≤n），有:(1)如果i=1，則結(jié)點i無雙親，是二叉樹的根；如果i>1，則其雙親是結(jié)點[i/2］；（2)如果2i≤n，則結(jié)點i為葉子結(jié)點，無左孩子；否則，其左孩子是結(jié)點2i；(3）如果2i+1≤n，則結(jié)點i無右孩子；否則，其右孩子是結(jié)點2i+1。4二叉樹的存儲結(jié)構(gòu)在計算機中，二叉樹通常采用鏈式存儲結(jié)構(gòu)。用于存儲二叉樹中各元素的存儲結(jié)點由兩部分組成：數(shù)據(jù)域與指針域.但在二叉樹中，由于每一個元素可以有兩個后件(兩個子結(jié)點），因此，用于存儲二叉樹的存儲結(jié)點的指針域有兩個：一個用于指向該結(jié)點的左子結(jié)點的存儲地址，稱為左指針域；另一個用于指向該結(jié)點的右子結(jié)點的存儲地址,稱為右指針域.考點18二叉樹的遍歷所謂遍歷二叉樹,就是遵從某種次序，訪問二叉樹中的所有結(jié)點，使得每個結(jié)點僅被訪問一次.1前序遍歷前序遍歷是指在訪問根結(jié)點、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。前序遍歷描述為：若二叉樹為空，則執(zhí)行空操作。否則：①訪問根結(jié)點；②前序遍歷左子樹；③前序遍歷右子樹。2中序遍歷中序遍歷是指在訪問根結(jié)點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后訪間根結(jié)點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。中序遍歷描述為：若二叉樹為空，則執(zhí)行空操作。否則：①中序遍歷左子樹；②訪問根結(jié)點；③中序遍歷右子樹。3后序遍歷后序遍歷是指在訪問根結(jié)點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點，并且,在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。后序遍歷描述為：若二叉樹為空,則執(zhí)行空操作。否則:①后序遍歷左子樹；②后序遍歷右子樹;③訪問根結(jié)點第2章程序設計基礎2．1程序設計方法與風格就程序設計方法和技術的發(fā)展而言,主要經(jīng)過了結(jié)構(gòu)化程序設計和面向?qū)ο蟮某绦蛟O計階段。一般來講。程序設計風格是指編寫程序時所表現(xiàn)出的特點、習慣和邏輯思路。程序是由人來編寫的，為了測試和維護程序，往往還要新聞記者和跟蹤程序，因此程序設計的風格總體而言應該強調(diào)得意和清晰,程序必須是可以理解的。要形成良好的程序設計風格，主要應注重和考慮下述一些因素。1、源程序文檔化2、源程序文檔化應考慮如下幾點:（1）符號名的命名：符號名的命名應具有一定的實際含義，以便于對程序功能的理解.（2)程序注釋：下克的注釋能夠幫助讀者理解程序。（3）禮堂組織：為使程序的結(jié)構(gòu)一目了然，可以在程序中利用空格、空行、縮進待技巧使程序?qū)哟吻逦?、數(shù)據(jù)說明的方法在編寫程序時，需要注意數(shù)據(jù)說明的風格，以便使程序中的數(shù)據(jù)說明更易于理解和維護.一般應注意如下幾點：（1）數(shù)據(jù)說明的次序規(guī)范化鑒于程序理解、新聞記者和維護的需要,使數(shù)據(jù)說明次序固定，可以使數(shù)據(jù)的發(fā)生容易查找，也有利于測試、排錯和維護。(2）說明語句中變量安排有序化。當一個說明語句說明多個變量時,變量按照字母順序為好。（3）使用注釋來說明復雜數(shù)據(jù)的結(jié)構(gòu)。3、語句的結(jié)構(gòu)程序應該簡單易懂，語句構(gòu)造應該簡單直接，不應該為提高效率而把語句復雜化。一般應注意如下：（1）在一行內(nèi)只寫一條語句；（2)程序編寫應優(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)不要修補不好的程序，要重新編寫；4、輸入和輸出無論是批處理的輸入和輸出方式,還是交互式的輸入和輸出方式,在設計和編程時都應該考慮如下原則：(1)對所有的輸入數(shù)據(jù)都要檢驗數(shù)據(jù)的合法性；（2）檢查輸入項的各種重要組合的合理性；（3）輸入格式要簡單,以使得輸入的步驟和操作盡可能簡單;（4）輸入數(shù)據(jù)時，應允許使用自由格式；（5)應允許缺省值；(6）輸入一批數(shù)據(jù)時，最好使用輸入結(jié)束標志；（7)在以交互式輸入/輸出方式進行輸入時，要在屏幕上使用提示符明確提示輸入的請求,同時在數(shù)據(jù)輸入過程中的輸入結(jié)束時，應在屏幕上給出狀態(tài)信息。（8）當程序設計語言對輸入格式有嚴格要求時,應保持輸入格式與輸入語句的一致性;給所有的輸入出加注釋,并設計輸出報表格式。2．2結(jié)構(gòu)化程序設計一、結(jié)構(gòu)化程序設計的原則結(jié)構(gòu)化程序設計方法的主要原則可以概括為自頂向下，逐步求精,模塊化,限制使用goto語句。1、自頂向下：程序設計時，應先考慮總體，后考慮細節(jié)；先考慮全局目標，后考慮局部目標。不要一開始就過多追求眾多的細節(jié)，先從最上層總目標開始設計,逐步使問題具體化.2、逐步求精:對復雜問題,應設計一些子目標作過渡，逐步細化。3、模塊化：一個復雜問題，肯定是由若干稍簡單的問題構(gòu)成。模塊化是把程序要解決的總目標分解為分目標，再進一步分解為具體的小目標，把每個小目標稱為一個模塊.4、限制使用goto語句使用goto語句經(jīng)實驗證實：（1)濫用GOTO語句確實有害，應晝避免；（2)完全避免使用GOTO語句也并非是個明智的方法，有些地方使用GOTO語句,會使程序流程更清楚、效率更高；（3）爭論的焦點不應該放在是否取消GOTO語句，而應該放在用什么樣的程序結(jié)構(gòu)上。其中最關鍵的是，肯定以提高程序清晰性為目標的結(jié)構(gòu)化方法。二、結(jié)構(gòu)化程序的基本結(jié)構(gòu)與特點1、順序結(jié)構(gòu)：順序結(jié)構(gòu)是簡單的程序設計，它是最基本、最常用的結(jié)構(gòu)，所謂順序執(zhí)行，就是按照程序語句行的自然順序,一條語句一條語句地執(zhí)行程序程序.2、選擇結(jié)構(gòu)：選擇結(jié)構(gòu)又稱為分支結(jié)構(gòu)，它包括簡單選擇和多分支選擇結(jié)構(gòu)，這種結(jié)構(gòu)可以根據(jù)設定的條件，判斷應該選擇哪一條分支來執(zhí)行相應的語句序列。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)化程序設計原則和方法的應用要注意把握如下要素：1、使用程序設計語言中的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯。2、選用的控制結(jié)構(gòu)只準許有一個入口和一個出口；3、程序語句組成容易識別的塊，每塊只有一個入口和一個出口；4、復雜結(jié)構(gòu)應該嵌套的基本控制結(jié)構(gòu)進行組合嵌套來實現(xiàn)；5、語言中所沒有的控制結(jié)構(gòu)，應該采用前后一致的方法來模擬;6、嚴格控制GOTO語句的使用。其意思是指:（1）用一個非結(jié)構(gòu)化的程序設計語言去實現(xiàn)一個結(jié)構(gòu)化的構(gòu)造；（2）若不使用GOTO語句會使功能模糊;（3）在某種可以改善而不損害程序可讀性的情況下。2．3面向?qū)ο蟮某绦蛟O計一、關于面向?qū)ο蠓椒嫦驅(qū)ο蠓椒ǖ谋举|(zhì)，就是主張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，提倡用人類在現(xiàn)實生活中常用的思維方法來認識、理解和描述客觀事物，強調(diào)最終建立的系統(tǒng)能夠映射問題域，也就是說，系統(tǒng)中的對象以及對象之間的關系能夠如實地反映問題域中固有事物及其關系.優(yōu)點：1、與人類習慣的思維方法一致面向?qū)ο蠓椒ê图夹g以對象為核心.對象是由數(shù)據(jù)和容許的操作組成的封裝體，與客觀實體有直接的關系.對象之間通過傳遞消息互相聯(lián)系，以模擬現(xiàn)實世界中不同事物彼此之間的聯(lián)系。面向?qū)ο蟮脑O計方法與傳統(tǒng)的面向過程的方法有本質(zhì)不同，這種方法的基本原理是：使用現(xiàn)實世界的概念抽象地思考問題從而自然地解決問題。它強調(diào)模擬現(xiàn)實世界中的概念而不強調(diào)算法,它鼓勵開發(fā)者在軟件開發(fā)的絕大部分過程中都用應用領域的要領去思考。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ū)ο蠓椒ㄖ凶罨镜母拍?對象可以用來表示客觀世界中的任何實體，也就是說，應用領域中有意義的、與所要解決的問題有關系的任何事物都可以作為對象，它既可以是具體的物理實體的抽象，也可以是人為的概念，或者是任何有明確邊界的意義的東西?？傊瑢ο笫菍栴}域中某個實體的抽象，設立某個對象就反映軟件系統(tǒng)保存有關它的信息并具有與它進行交互的能力。面向?qū)ο蟮某绦蛟O計方法中涉及的對象是系統(tǒng)中用來描述客觀事物的一個實體,是構(gòu)成系統(tǒng)的一個基本單位，它由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。對象可以做的操作表示它的動態(tài)行為，在面向?qū)ο蠓治龊兔嫦驅(qū)ο笤O計中，通常把對象的操作也稱為方法或服務.屬性即對象所包含的信息,它在設計對象時確定，一般只能通過掛靠對象的操作來改變。操作描述了對象執(zhí)行的功能，若通過消息傳遞，還可以為其他對象使用。操作的過程對外是封閉的，即用戶只能看到這一操作實施后的結(jié)果.這相當于事先已經(jīng)設計好的各種過程,只需要調(diào)用就可以了，用戶不必去關心這一過程是如何編寫的。事實上,這個過程已經(jīng)封裝在對象中,用戶也看不到.對的這一特性即是對象的封裝性。對象有如下一些基本特點：(1）標識惟一性。指對象是可區(qū)分的，并且由對象有的內(nèi)在本質(zhì)來區(qū)分，而不是通過描述來區(qū)分.（2)分類性.指可以將具有相同屬性的操作的對象抽象成類。（3）多太性.指同一個操作可以是不同對象的行為。（4)封裝性.從外面看只能看到對象的外部特性，即只需知道數(shù)據(jù)的取值范圍和可以對該數(shù)據(jù)施加的操作，根本無需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實現(xiàn)操作的算法.對象的內(nèi)部，即處理能力的實行和內(nèi)部狀態(tài)，對外是不可見的。從外面不能直接使用對象的處理能力，也不能直接修改其內(nèi)部狀態(tài)，對象的內(nèi)部狀態(tài)只能由其自身改變。（5）模塊獨立性好。對象是面向?qū)ο蟮能浖幕灸K,它是由數(shù)據(jù)及可以對這些數(shù)據(jù)施加的操作所組成的統(tǒng)一體，而且對象是以數(shù)據(jù)為中心的，操作圍繞對其數(shù)據(jù)所需做的處理來設置，沒有無關的操作從模塊的獨立性考慮，對象內(nèi)部各種元素彼此結(jié)合得很緊密，內(nèi)聚性強。2、類（Class）和實例（Instance）將屬性、操作相似的對象歸為類，也就是說，類是具有共同屬性、共同方法的對象的集合。所以,類是對象的抽象，它描述了屬于該對象類型的所有對象的性質(zhì)，而一個對象則是其對應類的一個實例。要注意的是，當使用“對象”這個術語時，既可以指一個具體的對象，也可以泛指一般的對象，但是，當使用“實例”這個術語時，必然是指一個具體的對象。例如:Integer是一個整數(shù)類，它描述了所有整數(shù)的性質(zhì).因此任何整數(shù)都是整數(shù)類的對象，而一個具體的整數(shù)“123”是類Integer的實例。由類的定義可知，類是關于對象性質(zhì)的描述,它同對象一樣,包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。3、消息（Message）面向?qū)ο蟮氖澜缡峭ㄟ^對象與對象間彼此的相互合作來推動的,對象間的這種相互合作需要一個機制協(xié)助進行，這樣的機制稱為“消息”.消息是一個實例與另一個實例之間傳遞信息，它請示對象執(zhí)行某一處理或回答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流的控制流。消息的使用類似于函數(shù)調(diào)用，消息中指定了某一個實例,一個操作名和一個參數(shù)表（可空)。接收消息的實例執(zhí)行消息中指定的操作，并將形式參數(shù)數(shù)與參數(shù)表中相應的值結(jié)合起來。消息傳遞過程中,由發(fā)送消息的對象(發(fā)送對象）的觸發(fā)操作產(chǎn)生輸出結(jié)果，作為消息傳送至接受消息的對象（接受對象)，引發(fā)接受消息的對象一系列的操作.所傳送的消息實質(zhì)上是接受對象所具有的操作/方法名稱，有時還包括相應參數(shù)。消息中只包含傳遞者的要求，它告訴接受者需要做哪些處理，但并不指示接受者應該怎樣完成這些處理。消息完全由接受者解釋,接受者獨立決定采用什么方式完成所需的處理，發(fā)送者對接受者不起任何控制作用。一個對象能夠接受不同形式、不同內(nèi)容的多個消息；相同形式的消息可以送往不同的對象,不同的對象對于形式相同的消息可以有不同的解釋，能夠做出不同的反映。一個對象可以同時往多個對象傳遞信息，兩個對象也可以同時向某個對象傳遞消息。例如，一個汽車對象具有“行駛"這項操作，那么要讓汽車以時速50公里行駛的話，需傳遞給汽車對象“行駛”及“時速50公里”的消息。通常，一個消息由下述三部分組成:（1)接收消息的對象的名稱；（2)消息標識符（也稱為消息名）；(3）零個或多個參數(shù)。4、繼承（Inheritance)繼承是面向?qū)ο蟮姆椒ǖ囊粋€主要特征.繼承是使用己有的類定義作為基礎建立新類的定義技術。已有的類可當作基類來引用，則新類相應地可當作派生類來引用。廣義地說，繼承是指能夠直接獲得已有的性質(zhì)和特征,而不必重復定義它們。面向?qū)ο筌浖夹g的許多強有力的功能和突出的優(yōu)點，都來源于把類組成一個層次結(jié)構(gòu)的系統(tǒng)：一個類的上層可以有父類,下層可以有子類。這種層次結(jié)構(gòu)系統(tǒng)的一個重要性質(zhì)是繼承性，一個類直接繼承其父類的描述（數(shù)據(jù)和操作）或特性，子類自動地共享基類中定義的數(shù)據(jù)和方法。繼承具有傳遞性,如果類C繼承類B，類B繼承類A，則類C繼承類A.因此一個類實際上繼承了它上層的全部基類的特性,也就是說,屬于某類的對象除了具有該類所定義的特性外，還具有該類上層全部基類定義的特性。繼承分為單繼承與多重繼承。單繼承是指，一個類只允許有一個父類,即類等級為樹形結(jié)構(gòu)。多重繼承是指,一個類允許有多個父類。多重繼承的類可以組合多個父類的性質(zhì)構(gòu)成所需要的性質(zhì)。因此，功能更強，使用更方便；便是，使用多重繼承時要注意避免二義性。繼承性的優(yōu)點是,相似的對象可以共享程序代碼和數(shù)據(jù)結(jié)構(gòu)，從而大大減少了程序中的冗余信息，提高軟件的可重用性，便于軟件個性維護。此外，繼承性便利用戶在開發(fā)新的應用系統(tǒng)時不必完全從零開始，可以繼承原有的相似系統(tǒng)的功能或者從類庫中選取需要的類,再派生出新的類以實現(xiàn)所需要的功能.5、多太性（Polymorphism）對象根據(jù)所接受的消息而做出動作，同樣的消息被不同的對象接受時可導致完全不同的行動,該現(xiàn)象稱為多態(tài)性。在面向?qū)ο蟮能浖夹g中，多態(tài)性是指類對象可以像父類對象那樣使用，同樣的消息既可以發(fā)送給父類對象也可以發(fā)送給子類對象。多態(tài)性機制不僅增加了面向?qū)ο筌浖到y(tǒng)的靈活性，進一步減少了信息冗余,而且顯著地提高了軟件的可重用性和可擴充性。當擴充系統(tǒng)功能增加新的實體類型時,只需派生出與新實體類相應的新的子類，完全無需修改原有的程序代碼，甚至不需要重新編譯原有的程序。利用多態(tài)性，用戶能夠發(fā)送一般形式的消息，而將所有的實現(xiàn)細節(jié)都留給接受消息的對象。軟件工程（SoftwareEngineering，簡稱為SE）是一門研究用工程化方法構(gòu)建和維護有效的、實用的和高質(zhì)量的軟件的學科。它涉及到程序設計語言，數(shù)據(jù)庫，軟件開發(fā)工具，系統(tǒng)平臺,標準，設計模式等方面。在現(xiàn)代社會中，軟件應用于多個方面。典型的軟件比如有電子郵件，嵌入式系統(tǒng)，人機界面，辦公套件，操作系統(tǒng)，編譯器,數(shù)據(jù)庫，游戲等。同時，各個行業(yè)幾乎都有計算機軟件的應用,比如工業(yè)，農(nóng)業(yè),銀行，航空，政府部門等。這些應用促進了經(jīng)濟和社會的發(fā)展，使得人們的工作更加高效，同時提高了生活質(zhì)量.軟件工程師是對應用軟件創(chuàng)造軟件的人們的統(tǒng)稱，軟件工程師按照所處的領域不同可以分為系統(tǒng)分析員,軟件設計師，系統(tǒng)架構(gòu)師，程序員,測試員等等。人們也常常用程序員來泛指各種軟件工程師。軟件工程（SoftWareEngineering)的框架可概括為:目標、過程和原則。(1）軟件工程目標:生產(chǎn)具有正確性、可用性以及開銷合宜的產(chǎn)品.正確性指軟件產(chǎn)品達到預期功能的程度?？捎眯灾杠浖窘Y(jié)構(gòu)、實現(xiàn)及文檔為用戶可用的程度。開銷合宜是指軟件開發(fā)、運行的整個開銷滿足用戶要求的程度。這些目標的實現(xiàn)不論在理論上還是在實踐中均存在很多待解決的問題，它們形成了對過程、過程模型及工程方法選取的約束.(2)軟件工程過程：生產(chǎn)一個最終能滿足需求且達到工程目標的軟件產(chǎn)品所需要的步驟。軟件工程過程主要包括開發(fā)過程、運作過程、維護過程。它們覆蓋了需求、設計、實現(xiàn)、確認以及維護等活動.需求活動包括問題分析和需求分析.問題分析獲取需求定義,又稱軟件需求規(guī)約。需求分析生成功能規(guī)約。設計活動一般包括概要設計和詳細設計。概要設計建立整個軟件系統(tǒng)結(jié)構(gòu)，包括子系統(tǒng)、模塊以及相關層次的說明、每一模塊的接口定義.詳細設計產(chǎn)生程序員可用的模塊說明，包括每一模塊中數(shù)據(jù)結(jié)構(gòu)說明及加工描述。實現(xiàn)活動把設計結(jié)果轉(zhuǎn)換為可執(zhí)行的程序代碼。確認活動貫穿于整個開發(fā)過程，實現(xiàn)完成后的確認,保證最終產(chǎn)品滿足用戶的要求。維護活動包括使用過程中的擴充、修改與完善。伴隨以上過程，還有管理過程、支持過程、培訓過程等。（3)軟件工程的原則是指圍繞工程設計、工程支持以及工程管理在軟件開發(fā)過程中必須遵循的原則.一、軟件工程概述概念：應需而生軟件工程是一類工程。工程是將理論和知識應用于實踐的科學。就軟件工程而言,它借鑒了傳統(tǒng)工程的原則和方法,以求高效地開發(fā)高質(zhì)量軟件。其中應用了計算機科學、數(shù)學和管理科學.計算機科學和數(shù)學用于構(gòu)造模型與算法,工程科學用于制定規(guī)范、設計范型、評估成本及確定權衡，管理科學用于計劃、資源、質(zhì)量和成本的管理。軟件工程這一概念,主要是針對20世紀60年代“軟件危機”而提出的.它首次出現(xiàn)在1968年NATO（北大西洋公約組織）會議上。自這一概念提出以來，圍繞軟件項目，開展了有關開發(fā)模型、方法以及支持工具的研究。其主要成果有：提出了瀑布模型，開發(fā)了一些結(jié)構(gòu)化程序設計語言(例如PASCAL語言，Ada語言）、結(jié)構(gòu)化方法等。并且圍繞項目管理提出了費用估算、文檔復審等方法和工具.綜觀60年代末至80年代初,其主要特征是，前期著重研究系統(tǒng)實現(xiàn)技術，后期開始強調(diào)開發(fā)管理和軟件質(zhì)量.70年代初，自“軟件工廠”這一概念提出以來，主要圍繞軟件過程以及軟件復用，開展了有關軟件生產(chǎn)技術和軟件生產(chǎn)管理的研究與實踐。其主要成果有：提出了應用廣泛的面向?qū)ο笳Z言以及相關的面向?qū)ο蠓椒?，大力開展了計算機輔助軟件工程的研究與實踐。尤其是近幾年來，針對軟件復用及軟件生產(chǎn),軟件構(gòu)件技術以及軟件質(zhì)量控制技術、質(zhì)量保證技術得到了廣泛的應用。目前各個軟件企業(yè)都十分重視資質(zhì)認證,并想通過這些工作進行企業(yè)管理和技術的提升.軟件工程所涉及的要素可概括如下：根據(jù)這一框架,可以看出：軟件工程涉及了軟件工程的目標、軟件工程原則和軟件工程活動。目標：我的眼里只有“產(chǎn)品”軟件工程的主要目標是：生產(chǎn)具有正確性、可用性以及開銷合宜的產(chǎn)品.正確性意指軟件產(chǎn)品達到預期功能的程度?？捎眯灾杠浖窘Y(jié)構(gòu)、實現(xiàn)及文檔為用戶可用的程度.開銷合宜性是指軟件開發(fā)、運行的整個開銷滿足用戶要求的程度。這些目標的實現(xiàn)不論在理論上還是在實踐中均存在很多問題有待解決,它們形成了對過程、過程模型及工程方法選取的約束。軟件工程活動是“生產(chǎn)一個最終滿足需求且達到工程目標的軟件產(chǎn)品所需要的步驟”。主要包括需求、設計、實現(xiàn)、確認以及支持等活動。需求活動包括問題分析和需求分析。問題分析獲取需求定義,又稱軟件需求規(guī)約.需求分析生成功能規(guī)約。設計活動一般包括概要設計和詳細設計。概要設計建立整個軟件體系結(jié)構(gòu),包括子系統(tǒng)、模塊以及相關層次的說明、每一模塊接口定義。詳細設計產(chǎn)生程序員可用的模塊說明，包括每一模塊中數(shù)據(jù)結(jié)構(gòu)說明及加工描述.實現(xiàn)活動把設計結(jié)果轉(zhuǎn)換為可執(zhí)行的程序代碼.確認活動貫穿于整個開發(fā)過程，實現(xiàn)完成后的確認，保證最終產(chǎn)品滿足用戶的要求。支持活動包括修改和完善。伴隨以上活動，還有管理過程、支持過程、培訓過程等。框架：四項基本原則是基石軟件工程圍繞工程設計、工程支持以及工程管理，提出了以下四項基本原則：第一，選取適宜開發(fā)范型.該原則與系統(tǒng)設計有關。在系統(tǒng)設計中，軟件需求、硬件需求以及其他因素之間是相互制約、相互影響的，經(jīng)常需要權衡。因此，必須認識需求定義的易變性，采用適宜的開發(fā)范型予以控制，以保證軟件產(chǎn)品滿足用戶的要求。第二，采用合適的設計方法.在軟件設計中，通常要考慮軟件的模塊化、抽象與信息隱蔽、局部化、一致性以及適應性等特征.合適的設計方法有助于這些特征的實現(xiàn)，以達到軟件工程的目標。第三,提供高質(zhì)量的工程支持?！肮び破涫拢叵壤淦?.在軟件工程中，軟件工具與環(huán)境對軟件過程的支持頗為重要。軟件工程項目的質(zhì)量與開銷直接取決于對軟件工程所提供的支撐質(zhì)量和效用。第四,重視開發(fā)過程的管理.軟件工程的管理，直接影響可用資源的有效利用,生產(chǎn)滿足目標的軟件產(chǎn)品,提高軟件組織的生產(chǎn)能力等問題。因此，僅當軟件過程得以有效管理時，才能實現(xiàn)有效的軟件工程。這一軟件工程框架告訴我們，軟件工程的目標是可用性、正確性和合算性;實施一個軟件工程要選取適宜的開發(fā)范型，要采用合適的設計方法，要提供高質(zhì)量的工程支撐，要實行開發(fā)過程的有效管理；軟件工程活動主要包括需求、設計、實現(xiàn)、確認和支持等活動，每一活動可根據(jù)特定的軟件工程，采用合適的開發(fā)范型、設計方法、支持過程以及過程管理。根據(jù)軟件工程這一框架，軟件工程學科的研究內(nèi)容主要包括：軟件開發(fā)范型、軟件開發(fā)方法、軟件過程、軟件工具、軟件開發(fā)環(huán)境、計算機輔助軟件工程（CASE)及軟件經(jīng)濟學等。作用:高效開發(fā)高質(zhì)量軟件自從軟件工程概念提出以來，經(jīng)過30多年的研究與實踐，雖然“軟件危機”沒得到徹底解決,但在軟件開發(fā)方法和技術方面已經(jīng)有了很大的進步。尤其應該指出的是，自80年代中期，美國工業(yè)界和政府部門開始認識到，在軟件開發(fā)中，最關鍵的問題是軟件開發(fā)組織不能很好地定義和管理其軟件過程，從而使一些好的開發(fā)方法和技術都起不到所期望的作用。也就是說，在沒有很好定義和管理軟件過程的軟件開發(fā)中,開發(fā)組織不可能在好的軟件方法和工具中獲益.根據(jù)調(diào)查,中國的現(xiàn)狀幾乎和美國10多年前的情況一樣，軟件開發(fā)過程沒有明確規(guī)定,文檔不完整,也不規(guī)范，軟件項目的成功往往歸功于軟件開發(fā)組的一些杰出個人或小組的努力.這種依賴于個別人員上的成功并不能為全組織的軟件生產(chǎn)率和質(zhì)量的提高奠定有效的基礎，只有通過建立全組織的過程改善,采用嚴格的軟件工程方法和管理，并且堅持不懈地付諸實踐，才能取得全組織的軟件過程能力的不斷提高.這一事實告訴我們，只有堅持軟件工程的四條基本原則，既重視軟件技術的應用，又重視軟件工程的支持和管理，并在實踐中貫徹實施，才能高效地開發(fā)出高質(zhì)量的軟件。二、軟件工程的七條基本原理自從1968年提出“軟件工程”這一術語以來，研究軟件工程的專家學者們陸續(xù)提出了100多條關于軟件工程的準則或信條。美國著名的軟件工程專家Boehm綜合這些專家的意見，并總結(jié)了TRW公司多年的開發(fā)軟件的經(jīng)驗，于1983年提出了軟件工程的七條基本原理。Boehm認為,著七條原理是確保軟件產(chǎn)品質(zhì)量和開發(fā)效率的原理的最小集合。它們是相互獨立的，是缺一不可的最小集合；同時,它們又是相當完備的。人們當然不能用數(shù)學方法嚴格證明它們是一個完備的集合，但是可以證明，在此之前已經(jīng)提出的100多條軟件工程準則都可以有這七條原理的任意組合蘊含或派生。下面簡要介紹軟件工程的七條原理：1用分階段的生命周期計劃嚴格管理這一條是吸取前人的教訓而提出來的。統(tǒng)計表明，50%以上的失敗項目是由于計劃不周而造成的。在軟件開發(fā)與維護的漫長生命周期中，需要完成許多性質(zhì)各異的工作。這條原理意味著，應該把軟件生命周期分成若干階段，并相應制定出切實可行的計劃，然后嚴格按照計劃對軟件的開發(fā)和維護進行管理。Boehm認為,在整個軟件生命周期中應指定并嚴格執(zhí)行6類計劃：項目概要計劃、里程碑計劃、項目控制計劃、產(chǎn)品控制計劃、驗證計劃、運行維護計劃。2堅持進行階段評審統(tǒng)計結(jié)果顯示：大部分錯誤是在編碼之前造成的，大約占63%;<2〉錯誤發(fā)現(xiàn)的越晚，改正它要付出的代價就越大，要差2到3個數(shù)量級。因此，軟件的質(zhì)量保證工作不能等到編碼結(jié)束之后再進行,應堅持進行嚴格的階段評審,以便盡早發(fā)現(xiàn)錯誤.3實行嚴格的產(chǎn)品控制開發(fā)人員最痛恨的事情之一就是改動需求。但是實踐告訴我們，需求的改動往往是不可避免的。這就要求我們要采用科學的產(chǎn)品控制技術來順應這種要求.也就是要采用變動控制，又叫基準配置管理。當需求變動時，其它各個階段的文檔或代碼隨之相應變動，以保證軟件的一致性。4采納現(xiàn)代程序設計技術從六、七時年代的結(jié)構(gòu)化軟件開發(fā)技術,到最近的面向?qū)ο蠹夹g，從第一、第二代語言，到第四代語言，人們已經(jīng)充分認識到：方法大似氣力。采用先進的技術即可以提高軟件開發(fā)的效率,又可以減少軟件維護的成本.5結(jié)果應能清楚地審查軟件是一種看不見、摸不著的邏輯產(chǎn)品。軟件開發(fā)小組的工作進展情況可見性差，難于評價和管理。為更好地進行管理,應根據(jù)軟件開發(fā)的總目標及完成期限,盡量明確地規(guī)定開發(fā)小組的責任和產(chǎn)品標準，從而使所得到的標準能清楚地審查。6開發(fā)小組的人員應少而精開發(fā)人員的素質(zhì)和數(shù)量是影響軟件質(zhì)量和開發(fā)效率的重要因素,應該少而精.這一條基于兩點原因:高素質(zhì)開發(fā)人員的效率比低素質(zhì)開發(fā)人員的效率要高幾倍到幾十倍，開發(fā)工作中犯的錯誤也要少的多；當開發(fā)小組為N人時，可能的通訊信道為N（N-1)/2,可見隨著人數(shù)N的增大,通訊開銷將急劇增大。7承認不斷改進軟件工程實踐的必要性遵從上述六條基本原理，就能夠較好地實現(xiàn)軟件的工程化生產(chǎn).但是，它們只是對現(xiàn)有的經(jīng)驗的總結(jié)和歸納，并不能保證趕上技術不斷前進發(fā)展的步伐.因此，Boehm提出應把承認不斷改進軟件工程實踐的必要性作為軟件工程的第七條原理。根據(jù)這條原理，不僅要積極采納新的軟件開發(fā)技術，還要注意不斷總結(jié)經(jīng)驗，收集進度和消耗等數(shù)據(jù),進行出錯類型和問題報告統(tǒng)計。這些數(shù)據(jù)既可以用來評估新的軟件技術的效果，也可以用來指明必須著重注意的問題和應該優(yōu)先進行研究的工具和技術。面向方面的編程(AspectOrientedProgrammi