單元4 程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

1單元

4程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)程序設(shè)計是設(shè)計和構(gòu)建可執(zhí)行的程序，以完成特定數(shù)值計算和數(shù)據(jù)處理的過程，是軟件開發(fā)過程的重要組成部分。熟悉和掌握程序設(shè)計的基礎(chǔ)知識，是在現(xiàn)代信息社會中生存和發(fā)展應(yīng)具備的基本技能之一。計算機系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)與數(shù)學(xué)、計算機硬件和軟件有十分密切的關(guān)系，數(shù)據(jù)結(jié)構(gòu)技術(shù)也被廣泛應(yīng)用于信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)、工程技術(shù)等領(lǐng)域。計算長方形面積的流程圖如圖4-1所示22算法初步4.1程序設(shè)計基礎(chǔ)4.24.34.44.5目錄Python語言程序設(shè)計數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)概述典型的數(shù)據(jù)結(jié)構(gòu)3圖4-1計算長方形面積的流程圖4計算長方形面積一般步驟的文字描述如下。第1步：輸入長方形的長度和寬度。即設(shè)置num1和num2兩個變量，接收用戶輸入的長度和寬度，并存儲到num1和num2兩個變量中。第2步：判斷輸入長方形的長度和寬度是否大于0，如果長度和寬度大于0，執(zhí)行第3步，否則執(zhí)行第5步。即判斷num1和num2是否大于0，如果大于0，執(zhí)行第3步，否則執(zhí)行第5步。第3步：計算長度和寬度的乘積。即計算num1和num2的乘積，并將乘積結(jié)果存儲到result變量。第4步：輸出長方形的面積。即顯示result變量的值到屏幕并退出。第5步：顯示輸入錯誤。即提示用戶輸入的長度和寬度有誤。根據(jù)計算長方形面積一般步驟的文字描述和圖4-1所示的流程圖，猜測一下圖4-2所示圖例的作用是什么？圖4-2流程圖的圖例5某洗衣機不啟動的故障排除步驟的文字描述如下。第1步：檢查電源是否接通，如果電源有問題，則解決電源問題后，故障排除。如果電源沒有問題，則進入第2步。第2步：檢查洗衣機門是否關(guān)嚴，如果洗衣機門沒有關(guān)嚴，則關(guān)嚴洗衣機門，故障排除。如果洗衣機門已關(guān)嚴，則進入第3步。第3步：檢查洗衣機進水部分，查看水龍頭是否打開，如果水龍頭沒有打開，則打開水龍頭，故障排除。如果水龍頭已打開且有水壓，則進入第4步。第4步：檢查是否按下了啟動鍵并有蜂鳴聲，如果沒有按下啟動鍵，則按下啟動鍵，故障排除。如果已按下啟動鍵且有蜂鳴聲，則需要給售后服務(wù)打電話報修。使用圖4-2所示的圖例嘗試繪制洗衣機不啟動故障排除流程圖，明確排除使用不當(dāng)而造成洗衣機不啟動故障的排查方法和流程。4.

1算法初步在計算機發(fā)展的初期，人們使用計算機的主要目的是處理數(shù)值計算問題。使用計算機解決具體問題一般需要經(jīng)過以下幾個步驟：首先從具體問題抽象出適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計或選擇求解此數(shù)學(xué)模型的算法，接著編寫程序并進行調(diào)試、測試，直至得到最終的解答。計算機解決問題的一般過程是：分析問題、設(shè)計算法、編寫程序、調(diào)試運行、檢測結(jié)果。64.1.1算法的概念做任何事情都有一定的步驟和方法，廣義地講，為解決某個問題而設(shè)計的確定的方法和有限的步驟，稱為算法。算法是一個基本的概念，但也是一門深奧的學(xué)問，小到如何輸出九九乘法表，如何對一組數(shù)據(jù)進行排序，大到如何控制飛行器的姿態(tài)，如何讓無人機避障等。我們先分析如何求1×2×3×4×5的值。原始的算法如下。步驟1：先求1乘以2，得到結(jié)果2。步驟2：將2乘以3，得到結(jié)果6。步驟3：將6乘以4，得到結(jié)果24。步驟4：將24乘以5，得到結(jié)果120。這樣的算法雖然正確，但有些煩瑣。改進的算法如下。S1：使t=1。S2：使i=2。S3：求t×i，乘積仍然放在變量t中，可表示為t×i→t。S4：求i+1的值，即i+1→i。S5：如果i≤5，返回重新執(zhí)行S3以及其后的S4和S5；否則，算法結(jié)束。如果要計算100！只需將S5的“i≤5”改成“i≤100”即可。如果改成求1×3×5×7×9×11，算法也只需做很少的改動，如下所示。S1：1→t。S2：3→i。S3：t×i→t。S4：i+2→i。S5：若i≤11，返回S3以及其后的S4和S5；否則，算法結(jié)束。該算法不僅正確，而且是便于計算機處理的算法，因為計算機是高速運算的自動機器，實現(xiàn)循環(huán)輕而易舉。7算法設(shè)計具有以下特點。①解決同一個問題可以有不同的解題方法和步驟。②算法有優(yōu)劣之分，有的算法只需要很少的步驟。同一個問題，計算機根據(jù)一種好的算法編寫的程序只需運行很短的時間（幾秒或幾分鐘）就能得到正確的解，而根據(jù)一種差的算法編寫的程序可能需要運行很長的時間（幾小時或幾天）才能得到最終的解?？梢妰?yōu)秀的算法可以帶來高效率。③設(shè)計算法時，不僅要保證算法正確，還要考慮算法的質(zhì)量。最優(yōu)的算法應(yīng)該實現(xiàn)計算次數(shù)最少，所需存儲空間最小，但兩者很難兼得。④不是所有的算法都能在計算機上實現(xiàn)。有些算法設(shè)計思路很巧妙，但計算機可能無法實現(xiàn)，不具有可行性。計算機算法分為數(shù)值運算算法和非數(shù)值運算算法。（1）數(shù)值運算算法數(shù)值運算的目的是求數(shù)值解，如求方程的根、求一個函數(shù)的定積分等。數(shù)值運算算法有現(xiàn)成的模型，各種數(shù)值運算都有比較成熟的算法可供選用。（2）非數(shù)值運算算法非數(shù)值運算算法主要用于處理非數(shù)值型的數(shù)據(jù)和問題，其應(yīng)用范圍廣泛，種類繁多，要求各異，難以規(guī)范化。目前，計算機在非數(shù)值運算方面的應(yīng)用遠遠超過了在數(shù)值運算方面的應(yīng)用。84.1.2算法的特性算法（Algorithm）是對特定問題求解步驟的一種描述，是求解步驟（指令）的有限序列。其中每一條指令表示一個或多個操作。不同的問題需要用不同的算法來解決，同一問題也可能有不同的算法，一個算法應(yīng)該具有下列特性。（1）有窮性（Finiteness）一個算法必須在執(zhí)行有窮步驟之后正常結(jié)束，即必須在有限時間內(nèi)完成。（2）確定性（Definiteness）算法中的每一個步驟都應(yīng)該是確定的，而不是含糊或模棱兩可的，對于相同的輸入必須得出相同的執(zhí)行結(jié)果。（3）可行性（Effectiveness）算法中執(zhí)行的任何計算步驟都可以被分解為基本的可執(zhí)行的操作步驟，即算法中的每個計算步驟都應(yīng)當(dāng)能有效地被執(zhí)行，并得到確定的結(jié)果，也稱之為有效性。例如：若b=0，則a/b是不能被有效執(zhí)行的。（4）輸入（Input）一個算法具有零個或多個輸入。所謂的輸入，是指在執(zhí)行算法時需要從外界取得的必要信息，這些輸入取自特定的數(shù)據(jù)對象集合。一個算法也可以沒有輸入。94.1.3比較算法和程序（5）輸出（Output）一個算法具有一個或多個輸出，這些輸出同輸入之間存在某種特定的關(guān)系。算法的目的是求“解”，“解”就是輸出。輸出反映對輸入數(shù)據(jù)加工后的結(jié)果，沒有輸出的算法是毫無意義的。101．算法和程序的區(qū)別算法與程序十分相似，但又有區(qū)別。一個程序不一定滿足有窮性。如操作系統(tǒng)，只要整個系統(tǒng)不遭破壞，它將永遠不會停止，即使沒有作業(yè)需要處理，它仍處于動態(tài)等待中。因此，操作系統(tǒng)不是一個算法。另外，程序中的指令必須是計算機可執(zhí)行的，而算法中的指令無此限制。算法代表了對問題的求解，而程序是算法在計算機上的特定的實現(xiàn)。一個算法若用程序設(shè)計語言來描述，那它就是一個程序。（1）兩者的定義不同算法是對特定問題求解步驟的描述，它是有限序列指令。（2）兩者的書寫規(guī)定不同程序必須用規(guī)定的程序設(shè)計語言來寫，而算法描述方法多樣。2．算法與程序的聯(lián)系算法是程序的核心，程序是算法在計算機上的具體實現(xiàn)。4.1.4算法的描述方法算法設(shè)計者必須將自己設(shè)計的算法清楚、正確地按步驟記錄下來，這個過程就叫描述算法。算法可以使用各種不同的方法來描述，常見的有自然語言、流程圖、N-S圖、偽代碼、計算機語言等。最簡單的方法是使用自然語言進行描述，也可以用以上的其他方法描述，還可以直接使用某種程序設(shè)計語言來描述算法，不過直接使用程序設(shè)計語言并不容易，而且不太直觀。1．用自然語言描述算法例如，任意輸入3個數(shù)，求這3個數(shù)中的最大數(shù)，用自然語言描述的算法如下。S1：定義4個變量，分別為x、y、z以及max。S2：輸入大小不同的3個數(shù)，分別賦給x、y、z。S3：判斷x是否大于y，如果大于，則將x的值賦給max，否則將y的值賦給max。S4：判斷max是否大于z，如果大于，則執(zhí)行S5，否則將z的值賦給max。S5：將max的值輸出。112．用流程圖描述算法流程圖是一種傳統(tǒng)的算法表示法，它用一些圖框來代表各種不同性質(zhì)的操作，用流程線來指示算法的執(zhí)行方向，直觀地描述算法的處理步驟。由于流程圖具有直觀、形象、容易理解的特點，所以應(yīng)用廣泛。但流程圖表示控制的箭頭過于靈活，且只描述執(zhí)行過程而不能描述有關(guān)數(shù)據(jù)。常用的流程圖的基本圖例如圖4-3所示。12圖4-3常用的流程圖的基本圖例其中，起止框是用來標(biāo)識算法開始和結(jié)束的；輸入/輸出框表示數(shù)據(jù)的輸入和輸出操作；判斷框的作用是對一個給定的條件進行判斷，并根據(jù)給定的條件是否成立來決定如何執(zhí)行后面的操作；處理框表示完成某種操作，如初始化或運算等；流程線用箭頭表示程序執(zhí)行的流向。例如，有40個學(xué)生，要求輸出不及格的學(xué)生的學(xué)號和成績。ni代表第i個學(xué)生的學(xué)號，gi代表第i個學(xué)生的成績，用流程圖描述算法，如圖4-4所示。13圖4-4輸出不及格的學(xué)生的姓名和成績的流程圖3．用N-S圖描述算法例如，計算10！，用N-S圖描述算法，如圖4-5所示。14圖4-5計算10！的N-S圖4．用偽代碼描述算法例如，計算10！，用偽代碼描述算法。用偽代碼表示的算法如下。15begin10→n1→sum1→numberwhilenumber<=nsum×number→sumnumber+1→numberendwhileprintsumend5．用計算機語言描述算法計算機無法識別流程圖和偽代碼，只有用計算機語言編寫的程序才能被計算機執(zhí)行。在用流程圖或偽代碼描述出一個算法后，要將其轉(zhuǎn)換成計算機語言程序。用計算機語言描述算法必須嚴格遵循所用語言的語法規(guī)則。例如，計算10！，用Python語言描述算法。Python程序如下。16n=10sum=1number=1whilenumber<=n:sum=sum*numbernumber+=1print("1到{}階乘為:{}".format(n,sum))4.1.5算法優(yōu)劣的評價標(biāo)準(zhǔn)使用計算機解決問題的關(guān)鍵是算法的設(shè)計，對于同一個問題，可以設(shè)計出不同的算法，如何評價算法優(yōu)劣是算法分析、比較、選擇的基礎(chǔ)?？梢詮囊韵聨讉€方面對算法優(yōu)劣進行評價。1．正確性算法能正確地實現(xiàn)預(yù)定的功能，滿足具體問題的需求。正確性的具體要求如下。?不含語法錯誤。?對輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果。?對一切合法輸入，都可以得到符合要求的解。172．可讀性一個算法應(yīng)當(dāng)思路清晰、層次分明，易于閱讀、理解和交流，便于調(diào)試、修改和擴充。寫出的算法，能讓人看明白，能讓人明白算法的邏輯。如果算法通俗易懂，則在系統(tǒng)調(diào)試和修改或者功能擴充的時候更為便捷。3．健壯性算法應(yīng)具有容錯能力。輸入非法數(shù)據(jù)，算法能適當(dāng)?shù)刈龀龇磻?yīng)并進行處理，不會產(chǎn)生預(yù)料不到的運行結(jié)果。數(shù)據(jù)的形式多種多樣，算法可能面臨著接收各種各樣的數(shù)據(jù)，當(dāng)算法接收到不適合算法處理的數(shù)據(jù)時，算法本身該如何處理呢？如果算法能夠處理異常數(shù)據(jù)，則處理能力越強，健壯性越好。4．穩(wěn)定性穩(wěn)定性主要指算法在噪聲、干擾等不利因素下仍能保持穩(wěn)定的性能輸出。185．時空性算法的時空性是指該算法的時間復(fù)雜度和空間復(fù)雜度，主要是說算法在執(zhí)行過程中的時間長短和空間占用問題。算法處理數(shù)據(jù)過程中，不同的算法耗費的時間和內(nèi)存空間是不同的。（1）時間復(fù)雜度算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。一般來說，計算機算法是問題規(guī)模n的函數(shù)f(n)，算法的重復(fù)執(zhí)行次數(shù)用T(n)表示，時間復(fù)雜度記作O(f(n))。問題的規(guī)模n趨近于無窮大時，T(n)/f(n)的極限值為不等于0的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)，即T(n)=O(f(n))稱作漸進時間復(fù)雜度（AsymptoticTimeComplexity）。（2）空間復(fù)雜度算法的空間復(fù)雜度是指算法需要消耗的內(nèi)存空間。其計算和表示方法與時間復(fù)雜度的類似，一般都用復(fù)雜度的漸進性來表示。同時間復(fù)雜度相比，空間復(fù)雜度的分析要簡單得多?？臻g復(fù)雜度記作S(n)=O(f(n))。例如，直接插入排序的時間復(fù)雜度是O(n2)，空間復(fù)雜度是O(1)。而一般的遞歸算法就有O(n)的空間復(fù)雜度了，因為每次遞歸都要存儲返回信息。194.1.6經(jīng)典算法簡介雖然設(shè)計算法，尤其是設(shè)計好的算法是一項困難的工作，但是設(shè)計算法也不是沒有規(guī)律可循。人們經(jīng)過幾十年的探討，總結(jié)和積累了許多行之有效的方法，了解和掌握這些方法會給我們解決問題提供一些思路。經(jīng)常采用的算法設(shè)計方法有迭代法、窮舉搜索法、遞推法、遞歸法、回溯法、貪婪法等，了解和借鑒這些算法設(shè)計的方法，有助于解決類似程序的設(shè)計問題。這里簡單介紹迭代法、窮舉搜索法、遞推法、遞歸法、回溯法、貪婪法這6種算法。1．迭代法迭代法是用來解決數(shù)值計算問題中的非線性方程（組）求解或求最優(yōu)解的一種算法，以求方程（組）的近似根。迭代法的基本思想是：從某個點出發(fā)，通過某種方式求出下一個點，此點應(yīng)該離要求解的點（方程的解）更進一步，當(dāng)兩者之差接近到可以接受的精度范圍時，就認為找到了問題的解。簡單迭代法每次只能求出方程的一個解，需要人工先給出近似初值。202．窮舉搜索法窮舉搜索法又稱為枚舉法，按某種順序?qū)λ械目赡芙庵饌€進行驗證，從中找出符合條件要求的作為問題的解。此算法通常用多重循環(huán)實現(xiàn)，對每個變量的每個值都測試是否滿足所給定的條件，以找到問題的一個解。這種算法簡單、易行，但只能用于變量個數(shù)有限的場合。3．遞推法遞推法是利用問題本身具有的遞推性質(zhì)或遞推公式求得問題的解的一種算法，從初始條件出發(fā)，逐步推出所需的結(jié)果。但是有些問題很難歸納出一組簡單的遞推公式。4．遞歸法遞歸法的思想是：將N=n時不能得出解的問題，設(shè)法遞歸轉(zhuǎn)化為求n－1,n－2,…的問題，一直到N=0或1，由于初始情況的解比較容易給出或方便得到，因此可逐層得到N=2,3,…,n時的解，得到最終結(jié)果。用遞歸法寫出的程序簡單、易讀，但效率不如遞推法的高。任何可以用遞推法解決的問題，都可以很方便地用遞歸法解決，但是許多能用遞歸法解決的問題，卻不能用遞推法解決。215．回溯法回溯法又稱為試探法，在用某種方法找出解的過程中，若中間項結(jié)果滿足所解問題的條件，則一直沿這個方向搜索下去，直到無路可走或無結(jié)果，則開始回溯，改變其前一項的方向或繼續(xù)搜索。若其前一項的方向或值都已經(jīng)測試過，還是無路可走或無結(jié)果，則繼續(xù)回溯到其前一項，改變其方向或值繼續(xù)搜索。若找到了一個符合條件的解，則停止或輸出這個結(jié)果后繼續(xù)搜索；否則繼續(xù)回溯下去，直到回溯到問題的開始處（不能再回溯），仍沒有找到符合條件的解，則表示此問題無解或已經(jīng)找到了全部的解。用回溯法可以求得問題的一個解或全部解。6．貪婪法貪婪法又稱為登山法，指從問題的初始解出發(fā)，一步步接近給定的目標(biāo)，并盡可能快地去逼近更好的解。貪婪法是一種不追求最優(yōu)解，只希望最快得到較為滿意解的方法。貪婪法不需要回溯，只能求出問題的某個解，不能求出所有的解。22平時購物找零時，為使找回的貨幣數(shù)量最少，不考慮找零錢的所有方案，而是從最大面額的貨幣開始，按遞減的順序考慮各貨幣，先盡量用大面額的貨幣，當(dāng)不足大面額貨幣的金額時才去考慮下一種較小面額的貨幣，這就使用了貪婪法。例如，50元找成20元、20元、10元。234.

2程序設(shè)計基礎(chǔ)程序設(shè)計是指編寫程序的過程。程序設(shè)計是一門技術(shù)，需要相應(yīng)的理論、技術(shù)、方法和工具支持。程序設(shè)計不僅要保證設(shè)計的程序能正確地解決問題，還要求程序具有可讀性、可維護性。244.2.1程序設(shè)計概述程序的概念非常普遍，一般來說，人們在完成一項復(fù)雜的任務(wù)時，需要進行一系列的具體工作，這些按一定的順序安排的工作就是完成該任務(wù)的程序。但在計算機領(lǐng)域，“程序”一詞特指計算機程序，即計算機為完成某任務(wù)所執(zhí)行的一系列有序的指令集合。程序設(shè)計是為解決特定問題而使用某種程序設(shè)計語言編寫程序的過程，程序設(shè)計過程應(yīng)當(dāng)包括分析、設(shè)計、編碼、測試、排錯等不同階段。專業(yè)的程序設(shè)計人員常被稱為程序員。4.2.2應(yīng)用軟件程序設(shè)計離不開程序設(shè)計語言，程序設(shè)計語言是人類用來和計算機溝通的工具。最早的程序設(shè)計語言是機器語言，用0和1兩種符號組成的二進制數(shù)表示，計算機只能直接執(zhí)行機器語言編寫的程序，但直接用機器語言編寫程序非常困難，效率也非常低。為了解決這個問題，誕生了各種各樣的程序設(shè)計語言，這些程序設(shè)計語言更加接近人類的語言和思維。4.2.3程序設(shè)計語言的基本類型人和計算機交流信息使用的語言稱為計算機語言或程序設(shè)計語言，計算機語言通常分為機器語言、匯編語言和高級語言3類。從程序設(shè)計語言的發(fā)展歷程來看，程序設(shè)計語言可以分為以下5代。1．第一代程序設(shè)計語言：機器語言機器語言（MachineLanguage）是一種用“0”和“1”兩個二進制符號表示的，能被計算機直接識別和執(zhí)行的語言，是早期的程序設(shè)計語言。它是一種低級語言，用機器語言編寫的程序不便于記憶、閱讀和書寫，通常不用機器語言直接編寫程序。用機器語言編寫的程序，稱為計算機機器語言程序。任何程序或語言在執(zhí)行前都必須轉(zhuǎn)換為機器語言。機器語言是面向計算機的語言，其中的每一條語句就是一段二進制指令代碼。用機器語言編程不僅工作量大，而且難學(xué)、難記、難修改，因此它只適合專業(yè)人員使用。而且不同品牌和型號的計算機的指令系統(tǒng)有差異，因此機器語言所編寫的程序只能在相同的硬件環(huán)境下使用，可移植性差。但機器語言也有編寫的程序代碼不需要翻譯、占用空間少、執(zhí)行速度快等優(yōu)點。252．第二代程序設(shè)計語言：匯編語言匯編語言（AssemblyLanguage）是一種用助記符表示的面向計算機的程序設(shè)計語言。匯編語言的每條指令對應(yīng)一條機器語言代碼，不同類型的計算機系統(tǒng)一般有不同的匯編語言。用匯編語言編制的程序稱為匯編語言程序，計算機不能直接識別和執(zhí)行，必須由“匯編程序”（或匯編系統(tǒng)）翻譯成機器語言程序才能運行。這種“匯編程序”就是匯編語言的翻譯程序。匯編語言適用于編寫直接控制計算機操作的底層程序，它與計算機密切相關(guān)，不容易使用。匯編語言在一定程度上克服了機器語言難學(xué)、難記、難修改的缺點，同時保持了編程質(zhì)量高、占用空間少、執(zhí)行速度快的優(yōu)點。但與機器語言一樣，匯編語言也是面向計算機的語言，使用匯編語言編寫的程序的通用性和可讀性都較差。3．第三代程序設(shè)計語言：高級語言高級語言（HighLevelLanguage）是一種比較接近自然語言和數(shù)學(xué)表達式的計算機程序設(shè)計語言，并且高級語言完全與計算機的硬件無關(guān)，程序員在編寫程序時，無須了解計算機的指令系統(tǒng)。因此，程序員在編寫程序時就不用考慮計算機硬件的差異，因而編程效率大大提高。由于高級語言與具體的計算機硬件無關(guān)，因此使用高級語言編寫的程序通用性強、可移植性高，易學(xué)、易讀、易修改，被廣泛應(yīng)用于商業(yè)、科學(xué)、教育、娛樂等眾多領(lǐng)域。26一般用高級語言編寫的程序稱為“源程序”，計算機不能識別和執(zhí)行，要把用高級語言編寫的源程序翻譯成機器指令，通常有編譯和解釋兩種方式。編譯是指將源程序整個編譯成目標(biāo)程序，然后通過鏈接程序?qū)⒛繕?biāo)程序鏈接成可執(zhí)行程序。解釋是指將源程序逐句翻譯，翻譯一句執(zhí)行一句，邊翻譯邊執(zhí)行，不產(chǎn)生目標(biāo)程序，這個過程由計算機的執(zhí)行解釋程序自動完成，如JavaScript、Python、Basic語言采用的就是這種方式。常用的高級語言有Python、Java、C#、C++、C、Fortran等。4．第四代程序設(shè)計語言：非過程語言非過程語言（NonproceduralLanguage）的特點是程序員不必關(guān)心問題的解法和處理問題的具體過程，只需說明所要完成的目標(biāo)和條件，就能得到想要的結(jié)果，而其他的工作都由系統(tǒng)來完成。數(shù)據(jù)庫的結(jié)構(gòu)查詢語言（StructureQueryLanguage，SQL）就是非過程語言頗具代表性的例子。例如，“Selectname,sex,ageFromstudentWhereclass=1”這一語句就可以直接從student數(shù)據(jù)表中查詢出class為1的學(xué)生的name、sex和age信息。而讀取數(shù)據(jù)、比較數(shù)據(jù)、顯示數(shù)據(jù)等一系列具體操作都由系統(tǒng)自動完成。相比于高級語言，非過程語言使用起來更加方便，但是非過程語言目前只適用于部分領(lǐng)域，其通用性和靈活性不如高級語言。275．第五代程序設(shè)計語言：人工智能語言人工智能語言目前剛剛起步，也是未來程序設(shè)計語言的發(fā)展方向。人工智能語言是一類適用于人工智能和知識工程領(lǐng)域的、具有符號處理和邏輯推理能力的程序設(shè)計語言。人工智能語言可以用于解決非數(shù)值計算、知識處理、推理、規(guī)劃、決策等各種復(fù)雜問題。284.2.4常見的高級程序設(shè)計語言自20世紀(jì)60年代以來，世界上公布的程序設(shè)計語言已有上千種之多，但是只有很小一部分得到了廣泛的應(yīng)用。目前主流的程序設(shè)計語言主要包括以下幾種。1．PythonPython是一種跨平臺、交互式、面向?qū)ο?、解釋型的計算機程序設(shè)計語言，它具有語法簡潔、清晰的特點，具有豐富和強大的庫，能夠把用其他語言開發(fā)的各種模塊很輕松地聯(lián)結(jié)在一起，因此常被稱為“膠水語言”。Python主要應(yīng)用于Web和互聯(lián)網(wǎng)開發(fā)、科學(xué)計算和統(tǒng)計、人工智能、大數(shù)據(jù)處理、網(wǎng)絡(luò)爬蟲、游戲開發(fā)、圖形處理、界面開發(fā)等領(lǐng)域。Python支持廣泛的應(yīng)用程序開發(fā)，從簡單的文字處理到Web開發(fā)再到游戲開發(fā)，并且簡單、易學(xué)。2．JavaJava是一種面向?qū)ο蟮某绦蛟O(shè)計語言，它不僅吸收了C++的各種優(yōu)點，還摒棄了C++中難以理解的多繼承、指針等概念。因此，Java具有功能強大和簡單易用兩個優(yōu)勢，并且具有封裝、繼承、多態(tài)等面向?qū)ο笳Z言的基本特征，以及穩(wěn)定、安全、可移植性強、與平臺無關(guān)、支持網(wǎng)絡(luò)編程、支持多線程等許多優(yōu)良特性，是目前使用十分廣泛的編程語言。Java可以用于編寫桌面應(yīng)用程序、Web應(yīng)用程序、分布式系統(tǒng)和嵌入式系統(tǒng)應(yīng)用程序等。3．JavaScriptJavaScript是一種直譯式腳本編程語言，可以與超文本標(biāo)記語言（HypertextMarkupLanguage，HTML）一起實現(xiàn)網(wǎng)頁中的動態(tài)交互功能，彌補HTML的不足，使網(wǎng)頁變得更加生動。JavaScript是一種基于對象和事件驅(qū)動的腳本語言，是一種輕量級的編程語言，現(xiàn)代瀏覽器都可以通過嵌入或調(diào)用JavaScript代碼在標(biāo)準(zhǔn)的HTML中實現(xiàn)其功能。JavaScript的基本語法與C語言的類似，但在運行過程中不需要單獨編譯，而是逐行解釋執(zhí)行，運行快。JavaScript具有跨平臺性，與操作環(huán)境無關(guān)，只依賴于瀏覽器本身，只要是支持JavaScript的瀏覽器就能正確執(zhí)行。294．C語言C語言是一種優(yōu)秀的面向過程的結(jié)構(gòu)化程序設(shè)計語言，被廣泛應(yīng)用于底層開發(fā)。它具有結(jié)構(gòu)嚴謹、數(shù)據(jù)類型完整、語句簡練靈活、運算符豐富等特點。同時，C語言面向硬件的底層編程能力很強，在硬件驅(qū)動程序開發(fā)和嵌入式應(yīng)用程序設(shè)計等方面應(yīng)用較多。C語言主要用于開發(fā)系統(tǒng)軟件、應(yīng)用軟件、設(shè)備驅(qū)動程序、嵌入式軟件等。5．C#C#是微軟公司發(fā)布的一種面向?qū)ο蟮?、運行于.NETFramework環(huán)境的高級程序設(shè)計語言。C#是一種強大而靈活的編程語言，借鑒了Java、C語言和C++的一些特點。它可以用來開發(fā)Windows應(yīng)用、企業(yè)級業(yè)務(wù)應(yīng)用、開發(fā)軟件等。6．C++C++是C語言的繼承，它既可以進行C語言的過程化程序設(shè)計，又可以進行以抽象數(shù)據(jù)類型為特點的基于對象的程序設(shè)計，還可以進行以繼承和多態(tài)為特點的面向?qū)ο蟮某绦蛟O(shè)計。C++是一種面向?qū)ο蟮挠嬎銠C程序設(shè)計語言，支持靜態(tài)數(shù)據(jù)類型檢查和多重編程范式。它還支持泛型程序設(shè)計等多種程序設(shè)計風(fēng)格。304.2.5程序設(shè)計的基本過程計算機解決問題的過程也是程序設(shè)計的過程。程序設(shè)計是運用計算機解決問題的一種方式，數(shù)值、邏輯等問題適合通過程序設(shè)計的方式解決，通過對實際問題的分析，設(shè)計算法，把所要解決的問題轉(zhuǎn)化成程序輸入計算機，經(jīng)調(diào)試后讓計算機執(zhí)行這個程序，最終達到利用計算機解決問題的目的。程序設(shè)計往往以某種程序設(shè)計語言為工具，給出用這種語言編寫的程序。1．分析問題分析問題也就是分析編寫該程序的目的、要解決的實際問題，并將實際問題抽象為計算機可以處理的模型。對于接受的程序設(shè)計任務(wù)要進行認真的分析，研究所給定的條件，分析最后應(yīng)達到的目標(biāo)，找出解決問題的規(guī)律，選擇解題的方法，完成實際問題求解。分析問題主要需要明確以下5點。①要解決的問題是什么？②問題的輸入是什么，已知什么，還要添加什么，使用什么格式？③期望的輸出是什么，需要什么類型的報告、圖表或信息？④數(shù)據(jù)具體的處理過程和要求是什么？⑤要建立什么樣的計算模型？312．建立模型建立模型是指從現(xiàn)實項目的真實情境中提煉出核心的要素并加以確定或假設(shè)，最終定義出一個有明確已知條件和求解目標(biāo)的問題，并用數(shù)學(xué)符號描述解決該問題的計算模型。3．設(shè)計算法設(shè)計算法即設(shè)計出解題的方法和具體步驟。在這一階段可以使用偽代碼描述算法，在描述整個模型的實現(xiàn)過程時，每一句偽代碼即對應(yīng)一個簡單的程序操作。對簡單的程序來說，可以直接按順序列出程序需要執(zhí)行的操作，從而產(chǎn)生偽代碼。但對復(fù)雜一些的程序來說，則需要先將整個模型分割成幾個大的模塊，必要時還需要將這些模塊分割為多個子模塊，然后用偽代碼來描述每個模塊的實現(xiàn)過程。4．編寫程序要讓計算機按照預(yù)先設(shè)計的算法進行處理，需要對該算法用計算機程序設(shè)計語言進行描述，形成計算機程序，并對源程序進行編輯、編譯和連接。5．運行程序，分析結(jié)果運行可執(zhí)行程序，得到運行結(jié)果。能得到運行結(jié)果并不意味著程序正確，要對結(jié)果進行分析，看它是否合理。不合理則要對程序進行調(diào)試，即排除程序中的故障。32程序難免會有各種錯誤和漏洞，因此，為了驗證程序的正確性，還需要對程序進行測試。測試程序的目的是找出程序中的錯誤，具體操作是在沒有語法和連接上的錯誤的基礎(chǔ)上，讓程序試運行多組數(shù)據(jù)，查看程序是否能達到預(yù)期的結(jié)果。這些測試數(shù)據(jù)應(yīng)是以“任何程序都是有錯誤的”假設(shè)為前提精心設(shè)計出來的。6．編寫程序文檔許多程序是提供給別人使用的，如同正式的產(chǎn)品應(yīng)當(dāng)提供產(chǎn)品說明書一樣，正式提供給用戶使用的程序，必須向用戶提供程序文檔。程序文檔相當(dāng)于產(chǎn)品說明書，對程序的使用、維護、更新都有很重要的作用，主要包括程序使用說明書和程序技術(shù)說明書。（1）程序使用說明書程序使用說明書是為了讓用戶清楚該程序的使用方法而編寫的，其內(nèi)容包括程序運行需要的軟件和硬件環(huán)境，程序的安裝和啟動的方法，程序的功能，需要輸入的數(shù)據(jù)類型、格式和取值范圍，涉及文件的數(shù)量、名稱、內(nèi)容，以及存放的路徑等。（2）程序技術(shù)說明書程序技術(shù)說明書是為了便于程序員今后對程序進行維護而編寫的，其內(nèi)容包括程序中各模塊的描述，程序使用硬件的有關(guān)信息，主要算法的解釋和描述，各變量的名稱、作用，程序代碼清單等。334.2.6程序設(shè)計的基本方法1．結(jié)構(gòu)化程序設(shè)計早期的計算機編程是面向過程的方法，如算術(shù)運算1+1+2=4，可以通過設(shè)計一個算法來解決。（1）結(jié)構(gòu)化程序設(shè)計的基本思路結(jié)構(gòu)化程序設(shè)計的程序結(jié)構(gòu)：按功能劃分為若干個基本模塊；各模塊之間的關(guān)系盡可能簡單，在功能上相對獨立；每一模塊內(nèi)部由順序、選擇和循環(huán)3種基本結(jié)構(gòu)組成；其模塊化實現(xiàn)的具體方法是使用子程序。結(jié)構(gòu)化程序設(shè)計采用了模塊分解與功能抽象，自頂向下、分而治之的方法，從而能有效地將一個較復(fù)雜的程序系統(tǒng)設(shè)計任務(wù)分解成許多易于控制和處理的子任務(wù)，便于開發(fā)和維護。雖然結(jié)構(gòu)化程序設(shè)計方法具有很多的優(yōu)點，但它仍是一種面向過程的程序設(shè)計方法，它把數(shù)據(jù)和處理數(shù)據(jù)的過程分離為相互獨立的實體。當(dāng)數(shù)據(jù)結(jié)構(gòu)改變時，相關(guān)的處理過程都要進行相應(yīng)的修改，每一種相對于老問題的新方法都要帶來額外的開銷，程序的可重用性差。由于圖形用戶界面的應(yīng)用，程序運行由順序運行演變?yōu)槭录?qū)動，使軟件使用起來越來越方便，但開發(fā)起來卻越來越困難，對于這種軟件的功能很難用過程來描述和實現(xiàn)，使用面向過程的方法來開發(fā)和維護都將非常困難。34（2）結(jié)構(gòu)化程序設(shè)計的主要原則①自頂向下。程序設(shè)計時，應(yīng)先考慮總體，后考慮細節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。不要一開始就過多追求眾多的細節(jié)，應(yīng)先從最上層總目標(biāo)開始設(shè)計，逐步使問題具體化。②逐步求精。對于復(fù)雜問題，應(yīng)設(shè)計一些子目標(biāo)作為過渡，逐步細化。③模塊化。一個復(fù)雜問題，肯定是由若干稍簡單的問題構(gòu)成的。模塊化是指把程序要解決的總目標(biāo)分解為子目標(biāo)，再進一步分解為具體的小目標(biāo)，把每一個小目標(biāo)稱為一個模塊。④限制使用goto語句。goto語句是程序設(shè)計語言中的一種無條件轉(zhuǎn)移語句，一般用在模塊中改變程序執(zhí)行的順序。在程序中過多地使用goto語句，會使程序變得難以理解。從提高程序清晰度考慮，一般建議不使用goto語句。（3）結(jié)構(gòu)化程序設(shè)計的基本結(jié)構(gòu)面向過程的結(jié)構(gòu)化程序設(shè)計采用3種基本結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。①順序結(jié)構(gòu)是指程序按照語句先后順序進行執(zhí)行，這是開發(fā)過程中十分簡單的程序結(jié)構(gòu)，設(shè)計好順序執(zhí)行的語句即可。②選擇結(jié)構(gòu)是指在程序設(shè)計的過程中出現(xiàn)了分支語句，它根據(jù)判斷條件結(jié)果選擇執(zhí)行其中的一個分支。選擇結(jié)構(gòu)包含單分支、雙分支和多分支3種表現(xiàn)形式。35③循環(huán)結(jié)構(gòu)是指程序反復(fù)地執(zhí)行同一個操作，直到某個表達式的條件為真或者為假則中止循環(huán)，否則繼續(xù)執(zhí)行對應(yīng)的循環(huán)操作。循環(huán)結(jié)構(gòu)可分為兩種形式：當(dāng)型循環(huán)和直到型循環(huán)。a．當(dāng)型循環(huán)：先判斷表達式的條件是否成立，成立的情況下進行循環(huán)，直到循環(huán)條件不成立，則跳出循環(huán)。b．直到型循環(huán)：先執(zhí)行一遍循環(huán)語句，然后進行條件判斷，如果條件不成立，循環(huán)不再執(zhí)行；如果條件成立，繼續(xù)執(zhí)行循環(huán)體里的內(nèi)容。2．面向?qū)ο蟪绦蛟O(shè)計面向?qū)ο螅∣bject-Oriented，OO）是一種軟件開發(fā)方法，面向?qū)ο笫且环N理解和抽象現(xiàn)實世界的方法，是計算機編程技術(shù)發(fā)展到一定階段的產(chǎn)物。面向?qū)ο蠓椒梢杂行岣呔幊绦?，通過封裝技術(shù)和消息機制，可以像搭積木一樣快速開發(fā)出全新的系統(tǒng)。面向?qū)ο蠓椒ǜ欣陂_發(fā)人員以可理解的方式對復(fù)雜系統(tǒng)進行分析、設(shè)計和編程。面向?qū)ο缶幊谈子诰S護、重用和擴展。由于面向?qū)ο缶哂蟹庋b性、繼承性和多態(tài)性的特點，因此可以設(shè)計出低耦合的系統(tǒng)，使得系統(tǒng)更加靈活，更易于維護。面向?qū)ο蟮母拍詈蛻?yīng)用已經(jīng)超越了程序設(shè)計和軟件開發(fā)，擴展到數(shù)據(jù)庫系統(tǒng)、交互界面、應(yīng)用結(jié)構(gòu)、應(yīng)用平臺、分布式系統(tǒng)、網(wǎng)絡(luò)管理結(jié)構(gòu)、計算機輔助設(shè)計技術(shù)、人工智能等領(lǐng)域。364.2.7良好的程序設(shè)計風(fēng)格為了提高程序的可閱讀性，要形成良好的程序設(shè)計風(fēng)格。風(fēng)格就是一種好的規(guī)范，我們所說的程序設(shè)計風(fēng)格應(yīng)是一種好的程序設(shè)計規(guī)范，包括良好的代碼設(shè)計、函數(shù)模塊、接口功能以及可擴展性等。更重要的是，程序設(shè)計過程中代碼的風(fēng)格包括縮進、注釋、變量及函數(shù)的命名等。374.2.8程序設(shè)計質(zhì)量評價評價一個程序設(shè)計質(zhì)量如何，首先看該設(shè)計是否能滿足程序的功能需求。除具有正確性之外，程序設(shè)計質(zhì)量的評估指標(biāo)還應(yīng)當(dāng)包含正確性、可讀性、可靠性、可復(fù)用性、可擴展性、可維護性、規(guī)范性、適應(yīng)性、內(nèi)聚度、耦合度等。1．正確性①程序中沒有語法錯誤。②程序運行時沒有發(fā)現(xiàn)明確的運行錯誤。③程序中沒有不適當(dāng)?shù)恼Z句。④用有效的測試數(shù)據(jù)，程序能得到正確的結(jié)果。38⑤用無效的測試數(shù)據(jù)，程序能得到的正確結(jié)果。⑥用任何可能的數(shù)據(jù)，程序在運行時能得到正確的結(jié)果。2．可讀性程序的內(nèi)容清晰、明了，便于閱讀和理解，沒有太多繁雜的技巧。對于大規(guī)模、工程化開發(fā)軟件而言，可讀性指標(biāo)具有非常重要的作用。為提高程序的可讀性，可在程序中插入解釋型語句，以對程序中的變量、功能、特殊處理細節(jié)等進行解釋，為今后他人閱讀該段程序提供方便?？勺x性好的程序設(shè)計文檔容易被其他程序員理解，可讀性差的設(shè)計會給大型軟件的開發(fā)和維護過程帶來嚴重的危害。3．可靠性可靠性指標(biāo)可分解為兩個方面的內(nèi)容。一方面是程序或系統(tǒng)的安全、可靠性，這些工作一般都要在系統(tǒng)分析和設(shè)計時嚴格定義。另一方面是程序運行的可靠性，這只能靠調(diào)試時的嚴格把關(guān)來保證編程工作的質(zhì)量，程序的功能必須按照規(guī)定的要求實現(xiàn)，以滿足預(yù)期的需求。規(guī)范性指系統(tǒng)的劃分、書寫的格式、變量的命名等都按統(tǒng)一的規(guī)范進行，這對于程序今后的閱讀、修改和維護都是十分必要的。394．可復(fù)用性可復(fù)用性指程序的架構(gòu)、類、組件等單元能否很容易被本項目的其他部分或者其他項目復(fù)用。5．可擴展性可擴展性指程序面對需求變化時，功能或性能擴展的難易程度。6．可維護性可維護性指程序各部分相互獨立，程序之間只有數(shù)據(jù)聯(lián)系。也就是說不會發(fā)生那種在維護時牽一發(fā)而動全身的連鎖反應(yīng)。一個規(guī)范性、可讀性、結(jié)構(gòu)劃分都很好的程序模塊，它的可維護性也是比較好的?？删S護性好的程序，其錯誤的修改、遺漏功能的添加也較容易。7．規(guī)范性規(guī)范性指系統(tǒng)的劃分、書寫的格式、變量的命名等都按統(tǒng)一的規(guī)范進行，這對于程序今后的閱讀、修改和維護都是十分必要的。8．適應(yīng)性適應(yīng)性指程序交付使用后，若應(yīng)用問題或外界環(huán)境有變化，調(diào)整和修改程序比較簡便、易行。409．內(nèi)聚度好的軟件設(shè)計應(yīng)該做到高內(nèi)聚。內(nèi)聚度表示一個應(yīng)用程序的單個單元所負責(zé)的任務(wù)數(shù)量和多樣性，內(nèi)聚與單個類或者單個方法單元相關(guān)。10．耦合度耦合度表示類之間關(guān)系的緊密程度，它決定了變更一個應(yīng)用程序的難易程度。概括起來，較低的耦合度和較高的內(nèi)聚度，即我們常說的“高內(nèi)聚、低耦合”，是所有優(yōu)秀程序的共同特征。4.

3

Python語言程序設(shè)計Python是一種跨平臺、交互式、面向?qū)ο?、解釋型的計算機程序設(shè)計語言，它具有豐富和強大的庫，能夠把用其他語言開發(fā)的各種模塊很輕松地聯(lián)結(jié)在一起。Python支持廣泛的應(yīng)用程序開發(fā)，從文字處理到Web開發(fā)再到游戲開發(fā)，并且簡單易學(xué)。414.3.1Python程序的運行1．Python程序的運行方式（1）交互式運行方式交互式是利用Python內(nèi)置的集成開發(fā)環(huán)境IDLE（IntegratedDevelopmentandLearningEnvironment）來運行程序，適合入門Python、編寫功能簡單的程序的初學(xué)者使用。首先打開命令提示符窗口，在窗口命令提示符“>”后輸入“python”命令并執(zhí)行來啟動Python解釋器，這樣就進入了交互式編程，并且會出現(xiàn)Python提示符“>>>”。在Python提示符“>>>”后輸入以下語句，然后按“Enter”鍵查看運行結(jié)果。print("Hello,Python!")以上命令運行結(jié)果如下。Hello,Python!沒有提示符“>>>”的行表示程序運行結(jié)果。輸入“exit()”或“quit()”則可以退出IDLE。42（2）腳本式運行方式我們先把Python語句寫好，并將其保存在擴展名為“py”的文件里，然后從外部調(diào)用這個文件。例如，將如下代碼輸入hello.py文件中。print("Hello,Python!")輸出結(jié)果如下。Hello,Python!2．Python程序常用的開發(fā)與運行環(huán)境Python程序常用的開發(fā)與運行環(huán)境主要有以下幾個。①IDLE：Python內(nèi)置的集成開發(fā)環(huán)境，IDLE隨Python安裝包提供。②PyCharm：由JetBrains公司開發(fā)，帶有一整套可以幫助用戶在使用Python語言開發(fā)時提高效率的工具，例如，項目管理、程序調(diào)試、語法高亮、代碼跳轉(zhuǎn)、智能提示、單元測試以及版本控制。此外，PyCharm提供了一些高級功能，用于支持Django框架下的專業(yè)Web應(yīng)用開發(fā)。Python主要有兩個版本，即2.x版（簡稱為Python2）和3.x版（簡稱為Python3）。打開命令提示符窗口，然后在窗口命令提示符“>”后輸入以下命令并執(zhí)行以運行該腳本。pythonD:\Test\hello.py4.3.2Python的基礎(chǔ)語法1．Python的保留字保留字即關(guān)鍵字，是Python本身的專用單詞，不能把它們用作任何標(biāo)識符名稱。如果嘗試使用關(guān)鍵字作為變量名，Python解釋器會報錯。Python3包含表4-1所示的35個關(guān)鍵字。43FalseNoneTrueandasassertasyncawaitbreakclasscontinuedefdelelifelseexceptfinallyforfromglobalifimportinislambdanonlocalnotorpassraisereturntrywhilewithyield

表4-1Python3的關(guān)鍵字2．Python標(biāo)識符的命名要求簡單地理解，標(biāo)識符就是一個名字，就像我們每個人都有屬于自己的名字，它的主要作用就是作為變量、函數(shù)、類、模塊以及其他對象的名稱。標(biāo)識符的命名格式必須統(tǒng)一，這樣才會方便不同人閱讀，Python的標(biāo)識符就是用于給程序中變量、類、方法命名的符號（簡單來說，標(biāo)識符就是合法的名字）。標(biāo)識符需要遵守一些規(guī)則，違反這些規(guī)則將引發(fā)錯誤。Python中標(biāo)識符的命名不是隨意的，而要遵守一定的命名規(guī)則，Python語言的標(biāo)識符的命名規(guī)則如下。①標(biāo)識符中的第1個字符必須是字母（A～Z和a～z）或下畫線（_），其后可以是任意數(shù)量的字母、數(shù)字和下畫線。②Python中的標(biāo)識符，不能以數(shù)字開頭，也不能包含空格、@、%以及$等特殊字符。③由于Python3支持UTF-8字符集，因此Python3的標(biāo)識符可以使用UTF-8所能表示的多種語言的字符。在Python3中，非ASCII標(biāo)識符也是允許的，標(biāo)識符中的字母并不局限于26個英文字母，可以包含漢字、日文字符等，但建議盡量不要使用漢字作為標(biāo)識符名稱。44④Python中的標(biāo)識符對大小寫敏感。Python語言的標(biāo)識符字母是嚴格區(qū)分大小寫的，也就是說，兩個同樣的單詞，如果大小寫格式不一樣，所代表的意義也是完全不同的，如abc和Abc是兩個不同的標(biāo)識符。⑤不能將Python關(guān)鍵字和內(nèi)置函數(shù)名作為標(biāo)識符名稱，如print等。但標(biāo)識符名稱中可以包含關(guān)鍵字。⑥變量不要以雙下畫線開頭和結(jié)尾，這是Python專用的標(biāo)識符。另外，避免使用小寫l、大寫O和大寫I作為變量名。454.3.3Python3的基本數(shù)據(jù)類型Python3有6個標(biāo)準(zhǔn)的數(shù)據(jù)類型，其中不可變數(shù)據(jù)有3個，包括Number（數(shù)值）、String（字符串）、Tuple（元組）；可變數(shù)據(jù)有3個，包括List（列表）、Dictionary（字典）、Set（集合）。下面對數(shù)值和字符串類型進行簡要介紹。1．?dāng)?shù)值Python3中數(shù)值有4種類型：int（整型，如3）、float（浮點型，如1.23、3E-2）、complex（復(fù)數(shù)，如1+2j、1.1+2.2j）和bool（布爾型，如True）。（1）整型整型（int）通常被稱為整數(shù)，可以是正整數(shù)、負整數(shù)和0，不帶小數(shù)點。整數(shù)可以使用十進制、十六進制、八進制和二進制來表示。例如：46>>>a,b,c=10,100,-786#十進制>>>a,b,c運行結(jié)果：(10,100,-786)（2）浮點型浮點型（float）由整數(shù)部分與小數(shù)部分組成，常被稱為浮點數(shù)，例如：0.5、1.414、1.732、3.1415926。浮點型也可以使用科學(xué)記數(shù)法表示，例如5e2。（3）復(fù)數(shù)Python還支持復(fù)數(shù)（complex），復(fù)數(shù)由實數(shù)部分和虛數(shù)部分構(gòu)成，虛數(shù)部分使用j或J表示，可以用a+bj或者complex(a,b)表示，復(fù)數(shù)的實部a和虛部b都是浮點型，如2.31+6.98j。2．字符串Python中單引號和雙引號的使用完全相同，使用三引號（'''或"""）可以指定一個多行字符串。Python沒有單獨的字符類型，一個字符就是長度為1的字符串。以下都是正確的字符串表示方式。47word='字符串'sentence="這是一個句子。"paragraph="""這是一個段落，可以由多行組成"""反斜線“\”可以用來轉(zhuǎn)義字符，通過在字符串前加r或R可以讓反斜線不發(fā)生轉(zhuǎn)義。例如，“r"thisisalinewith\n"”，則\n會顯示，并不會換行。Python允許處理Unicode字符串，加前綴u或U即可，如“u"thisisanunicodestring"”。4.3.4Python運算符及其應(yīng)用1．Python的算術(shù)運算符及其應(yīng)用運算符是一些特殊的符號，主要用于數(shù)學(xué)計算、比較運算和邏輯運算等。Python語言支持以下類型的運算符：算術(shù)運算符、賦值運算符、比較（關(guān)系）運算符、邏輯運算符、位運算符、成員運算符、身份運算符。使用運算符將不同類型的數(shù)據(jù)按照一定的規(guī)則連接起來的算式，被稱為表達式。例如，使用算術(shù)運算符連接起來的算式稱為算術(shù)表達式，使用比較（關(guān)系）運算符連接起來的算式稱為比較（關(guān)系）表達式，使用邏輯運算符連接起來的算式稱為邏輯表達式。比較（關(guān)系）表達式和邏輯表達式通常作為選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)的條件語句。（1）Python的算術(shù)運算符Python的算術(shù)運算符及應(yīng)用實例如表4-2所示。4849表4-2Python的算術(shù)運算符及應(yīng)用實例運算符名稱說明實例輸出結(jié)果+加兩個數(shù)相加21+1031-減得到負數(shù)或是一個數(shù)減去另一個數(shù)21－1011*乘兩個數(shù)相乘或是返回一個被重復(fù)若干次的字符串21*10210/除x除以y21/102.1%取余返回除法的余數(shù)，如果除數(shù)（第2個操作數(shù)）是負數(shù)，那么結(jié)果也是一個負值21%10121%(－10)－9**冪返回x的y次冪21**2441//取整除返回商的整數(shù)部分21//21021.0//2.010.0－21//2－11（2）Python算術(shù)運算符的運算優(yōu)先級Python算術(shù)運算符的運算優(yōu)先級由高到低順序排列如下。第1級：**。第2級：*、/、%、//。第3級：+、－。同級運算符從左至右計算，可以使用()調(diào)整運算的優(yōu)先級，加()的部分優(yōu)先運算。（3）Python算術(shù)表達式Python的算術(shù)表達式由數(shù)值類型數(shù)據(jù)與+、－、*、/等算術(shù)運算符組成，括號可以用來為運算分組。包含單一算術(shù)運算符的算術(shù)表達式的實例如圖。50>>>5+4#加法9>>>4.3–2#減法2.3>>>3*7#乘法21>>>2/4#除法，得到一個浮點數(shù)0.5>>>8/4#總是返回一個浮點數(shù)2.0>>>17%3#％操作符表示返回除法的余數(shù)2浮點數(shù)得到Python完全的支持，不同類型的數(shù)值混合運算時，Python會把整數(shù)轉(zhuǎn)換為浮點數(shù)。包含多種算術(shù)運算符的算術(shù)表達式的實例如下。51>>>5*3+217>>>50－5*620>>>(50－5*6)/45.0>>>3*3.75/1.57.52．Python的賦值運算符與變量（1）Python的賦值運算符Python的賦值運算符如表4-3所示，表4-3中變量x的初始值為0。52表4-3Python的賦值運算符運算符描述實例等效形式變量x的值=簡單賦值運算符x=21+10將21+10的運算結(jié)果賦值給x31+=加法賦值運算符x+=10x=x+1041－=減法賦值運算符x－=10x=x－1031*=乘法賦值運算符x*=10x=x*10310/=除法賦值運算符x/=10x=x/1031.0%=取模賦值運算符x%=10x=x%101.0**=冪賦值運算符x**=10x=x**101.0//=取整除賦值運算符x//=10x=x//100.0（2）變量定義及賦值Python中的變量不需要聲明變量名及其類型。每個變量在使用前都必須被賦值，變量被賦值以后該變量才會被創(chuàng)建。在Python中，變量就是變量，變量本身沒有類型的概念，我們所說的“類型”是變量所指的內(nèi)存中對象的類型。①變量賦值的基本語法格式。等號（=）運算符用于給變量賦值，變量賦值的基本語法格式如下。<變量名>=<變量值>等號（=）運算符左邊是一個變量名，等號（=）運算符右邊是存儲在變量中的值。變量命名應(yīng)遵循Python一般標(biāo)識符的命名規(guī)則，變量值可以是任意數(shù)據(jù)類型。變量被賦值之后，Python解釋器不會顯示任何結(jié)果。例如：53>>>width=20>>>height=5*9>>>width*height900②定義變量。程序中當(dāng)變量被指定一個值時，對應(yīng)變量就會被創(chuàng)建。例如：54>>>var1=6>>>var2=10.5>>>print("var1=",var1)>>>print("var2=",var2)運行結(jié)果：var1=6var2=10.5變量在使用前必須先“定義”（即賦予變量一個值），否則會出現(xiàn)錯誤。在Python語言中，除了變量，還有常量的概念，所謂常量就是程序運行過程中值不會發(fā)生改變的量，如數(shù)學(xué)運算中的圓周率，在Python中，沒有提供定義常量的關(guān)鍵字。3．Python的比較運算符及其應(yīng)用比較運算符，也稱為關(guān)系運算符，用于對變量或表達式的結(jié)果進行大小、真假等比較，如果比較結(jié)果為成立，則返回True，如果為不成立，則返回False。Python的比較運算符及應(yīng)用實例如表4-4所示，所有比較運算符的運行結(jié)果返回True表示真，返回False表示假，這分別與Python2中的1和0等價，True和False的首字母必須大寫，實例假設(shè)變量x為21，變量y為10，即x=21，y=10。55運算符名稱說明實例運行結(jié)果==等于比較x和y兩個對象是否相等x==yFalse!=不等于比較x和y兩個對象是否不相等x!=yTrue>

大于比較x是否大于yx>yTrue<

小于比較x是否小于yx<yFalse>=大于或等于比較x是否大于等于yx>=yTrue<=小于或等于比較x是否小于等于yx<=yFalse表4-4Python的比較運算符及應(yīng)用實例例如：56>>>x=5>>>y=8>>>print(x==y)>>>print(x!=y)FalseTrue比較運算符與比較對象（變量或表達式）構(gòu)建出比較表達式，也稱為關(guān)系表達式。比較表達式通常用在條件語句和循環(huán)語句中作為“條件表達式”。以上實例的運行結(jié)果：4．Python的邏輯運算符及其應(yīng)用Python語言支持邏輯運算符，邏輯運算符是對True和False兩種布爾值進行運算，運算后的結(jié)果仍是一個布爾值。邏輯運算符也可以對非布爾值進行運算。Python對非布爾值的邏輯運算符及應(yīng)用實例如表4-5所示，實例假設(shè)變量x為21，變量y為10，變量z為0，即x=21，y=10，z=0。57表4-5Python對非布爾值的邏輯運算符及應(yīng)用實例運算符名稱邏輯表達式結(jié)合方向說明實例運算結(jié)果and邏輯與xandy從左到右如果x為False或0，xandy返回False或0，否則返回y的計算值xandy10xandz0zandx0or邏輯或xory從左到右如果x是True，返回x的值，否則返回y的計算值xory21xorz21zorx21not邏輯非notx從右到左如果x為True，返回False，如果x為False，返回TruenotxFalsenotyFalsenot(xandy)Falsenot(xory)FalsenotzTrue4.3.5Python程序流程控制程序的流程控制結(jié)構(gòu)主要包括選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)，選擇結(jié)構(gòu)是根據(jù)條件表達式的結(jié)果選擇運行不同語句的流程結(jié)構(gòu)；循環(huán)結(jié)構(gòu)則是在一定條件下反復(fù)運行某段程序的流程結(jié)構(gòu)，被反復(fù)運行的語句體稱為循環(huán)體，決定循環(huán)是否終止的判斷條件稱為循環(huán)條件。流程控制語句的條件表達式主要為比較（關(guān)系）表達式和邏輯表達式。1．Python的順序結(jié)構(gòu)計算機程序主要有3種基本結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。如果沒有流程控制的話，整個程序都將按照語句的編寫順序（從上至下的順序）來運行，而不能根據(jù)需求決定程序運行的順序。2．Python的流程控制流程控制對任何一門編程語言來說都是非常重要的，因為它提供了控制程序運行的方法。Python3根據(jù)條件語句的運算結(jié)果選擇不同路徑的運行方式。Python條件語句通過一條或多條語句的運行結(jié)果（True或者False）來決定運行的代碼塊?？梢酝ㄟ^圖4-6來簡單了解條件語句的運行過程。如果條件表達式的值為True，則執(zhí)行代碼塊，否則不執(zhí)行代碼塊。5859圖4-6條件語句的運行過程示意3．Python的選擇結(jié)構(gòu)及其應(yīng)用Python的選擇結(jié)構(gòu)是根據(jù)條件表達式的結(jié)果選擇運行不同語句的流程結(jié)構(gòu)，選擇語句也稱為條件語句，即按照條件選擇運行不同的代碼片段，Python中選擇語句主要有3種形式：if語句、if…else語句和if…elif…else語句。Python使用if…elif…else多分支語句或者if語句的嵌套結(jié)構(gòu)實現(xiàn)多重選擇。（1）if語句及其應(yīng)用Python中使用if關(guān)鍵字來構(gòu)成選擇語句，if語句的一般形式如下。60if<條件表達式>:<語句塊>>>>password=input("請輸入密碼：")條件表達式可以是一個單純的布爾值或變量，也可以是比較表達式或邏輯表達式，如果條件表達式的值為True，則運行<語句塊>；如果條件表達式的值為False，就跳過<語句塊>，繼續(xù)運行后面的語句。例如：運行結(jié)果：請輸入密碼：123456>>>ifpassword=="123456":print("輸入的密碼正確")61輸入的密碼正確if<條件表達式>:<語句塊1>else：

<語句塊2>運行結(jié)果：（2）if…else語句及其應(yīng)用Python中if…else語句的一般形式如下。if…else語句主要解決二選一的問題，使用if…else語句時，條件表達式可以是一個單純的布爾值或變量，也可以是比較表達式或邏輯表達式，如果條件表達式的值為True，則運行if語句后面的<語句塊1>，否則，運行else后面的<語句塊2>。（3）if…elif…else語句及其應(yīng)用Python中if…elif…else語句的一般形式如下。62if<條件表達式1>:<語句塊1>elif<條件表達式2>:<語句塊2>else:<語句塊N>Python中用elif代替了elseif，所以多分支選擇結(jié)構(gòu)的關(guān)鍵字為if…elif…else。if…elif…else語句運行的規(guī)則如下。條件表達式1和條件表達式2可以是一個單純的布爾值或變量，也可以是比較表達式或邏輯表達式。如果<條件表達式1>的值為True，則運行<語句塊1>；如果<條件表達式1>的值為False，將判斷<條件表達式2>，如果<條件表達式2>的值為True，則運行<語句塊2>；如果<條件表達式1>和<條件表達式2>的值都為False，則運行<語句塊N>。Python中if語句每個條件后面要使用冒號“:”，表示接下來是滿足條件后要運行的語句塊。使用縮進來劃分語句塊，相同縮進數(shù)的語句在一起組成一個語句塊。if和elif都需要判斷條件表達式的真假，而else則不需要判斷；另外，elif和else都必須與if一起使用，不能單獨使用。4．for循環(huán)語句及其應(yīng)用循環(huán)結(jié)構(gòu)是在一定條件下反復(fù)運行某段程序的流程結(jié)構(gòu)，被反復(fù)運行的語句體稱為循環(huán)體，決定循環(huán)是否終止的判斷條件稱為循環(huán)條件。Python中的循環(huán)語句有for和while兩種類型。Python中for循環(huán)也稱為計次循環(huán)，其循環(huán)語句可以遍歷各種序列數(shù)據(jù)，如一個列表或者一個字符串。while循環(huán)也稱為條件循環(huán)，可以一直進行循環(huán)，直到條件不滿足時才結(jié)束循環(huán)。for循環(huán)通常適用于枚舉或遍歷序列，以及迭代對象中的元素，一般應(yīng)用于循環(huán)次數(shù)已知的情況。for循環(huán)語句的基本格式如下。63for<循環(huán)變量>in<序列結(jié)構(gòu)>:<語句塊>其中，循環(huán)變量用于保存取出的值，序列結(jié)構(gòu)為要遍歷或迭代的序列對象，如字符串、列表、元組等，語句塊為一組被重復(fù)運行的語句。for循環(huán)語句的運行流程圖如圖4-7所示。64圖4-7for循環(huán)語句的運行流程圖5．while循環(huán)語句及其應(yīng)用Python中的while循環(huán)通過一個條件表達式來控制是否要繼續(xù)反復(fù)運行循環(huán)體中的語句塊。Python中while循環(huán)語句的一般形式如下。65while<條件表達式>:

<語句塊>while循環(huán)語句的條件表達式的值為True時，則運行循環(huán)體的語句塊；運行一次后，重新判斷條件表達式的值，直到條件表達式的值為False時，退出while循環(huán)。while循環(huán)語句的運行流程圖如圖4-8所示。Python中while循環(huán)語句的條件表達式后面要使用冒號“:”，表示接下來是滿足條件后要運行的語句塊。使用縮進來劃分語句塊，相同縮進數(shù)的語句組成一個語句塊。66圖4-8while循環(huán)語句的運行流程圖4.

4數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)概述在計算機發(fā)展的初期，人們使用計算機的目的主要是處理數(shù)值計算問題。隨著計算機應(yīng)用領(lǐng)域的擴大和軟硬件的發(fā)展，非數(shù)值計算問題顯得越來越重要，這類問題涉及的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程式加以描述。因此，解決這類問題的關(guān)鍵不再是數(shù)學(xué)分析和計算方法，而是要設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)。描述這類非數(shù)值計算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。674.4.1數(shù)據(jù)結(jié)構(gòu)的基本概念在系統(tǒng)地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)知識之前，先明確一些基本術(shù)語的確切含義。1．?dāng)?shù)據(jù)計算機應(yīng)用程序處理各種各樣的數(shù)據(jù)，數(shù)據(jù)就是計算機加工處理的對象，它可以是數(shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。數(shù)值數(shù)據(jù)包括實數(shù)和復(fù)數(shù)，主要用于工程計算、科學(xué)計算和商務(wù)處理等，非數(shù)值數(shù)據(jù)包括字符、文字、圖形、圖像、音頻、視頻等。2．?dāng)?shù)據(jù)元素數(shù)據(jù)元素（DataElement）是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素（Element）、節(jié)點（Node）、頂點（Vertex）、記錄（Record）等。有時，一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項（DataItem）組成，例如，學(xué)生管理信息系統(tǒng)中學(xué)生信息表的每一個數(shù)據(jù)元素就是一條學(xué)生記錄，它包括學(xué)生的學(xué)號、姓名、性別、籍貫、出生年月、成績等數(shù)據(jù)項。這些數(shù)據(jù)項可以分為兩種：一種叫作基本項，如學(xué)生的性別、籍貫等，這些數(shù)據(jù)項是在數(shù)據(jù)處理時不能再被分割的最小單位；另一種叫作組合項，如學(xué)生的成績，它可以再被劃分為數(shù)學(xué)成績、物理成績、化學(xué)成績等更小的項。通常，在解決實際應(yīng)用問題時是把每個學(xué)生記錄當(dāng)作一個基本單位進行訪問和處理的。3．?dāng)?shù)據(jù)對象數(shù)據(jù)對象（DataObject）是具有相同性質(zhì)的數(shù)據(jù)元素的集合。在某個具體問題中，數(shù)據(jù)元素都具有相同的性質(zhì)（元素值不一定相等），屬于同一數(shù)據(jù)對象（數(shù)據(jù)元素類），數(shù)據(jù)元素是數(shù)據(jù)對象的一個實例。例如，在交通咨詢系統(tǒng)的交通網(wǎng)中，所有的頂點是一個數(shù)據(jù)對象，頂點A和頂點B各自代表一個城市，是該數(shù)據(jù)對象中的兩個實例，其數(shù)據(jù)元素的值分別為A和B。4．?dāng)?shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（DataStructure）是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。在各種問題中，數(shù)據(jù)元素都不會是孤立的，在它們之間都存在著這樣或那樣的關(guān)系，這種數(shù)據(jù)元素之間的相互關(guān)系稱為結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的關(guān)系，從邏輯關(guān)系角度描述數(shù)據(jù)，可以看作從具體問題抽象出來的數(shù)學(xué)模型，它與數(shù)據(jù)的存儲無關(guān)。數(shù)據(jù)元素及數(shù)據(jù)元素之間的邏輯關(guān)系在計算機存儲器內(nèi)的表示（又稱映像）稱為數(shù)據(jù)的物理結(jié)構(gòu)，或稱存儲結(jié)構(gòu)。它所研究的是數(shù)據(jù)結(jié)構(gòu)在計算機中的實現(xiàn)方法，包括數(shù)據(jù)結(jié)構(gòu)中元素的表示及元素間關(guān)系的表示。68根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通常有下列4種基本的結(jié)構(gòu)。（1）集合結(jié)構(gòu)集合是一種常用的數(shù)據(jù)表示方法，是數(shù)據(jù)元素的有限集合。該結(jié)構(gòu)中，數(shù)據(jù)元素間的關(guān)系是“屬于同一個集合”，集合是元素關(guān)系極為松散的一種結(jié)構(gòu)。對集合可以進行多種操作，假設(shè)集合S由若干個元素組成，可以按照某一規(guī)則把集合S劃分成若干個互不相交的子集合，例如，集合S={1,2,3,4,5,6,7,8,9,10}，可以被分成如下3個互不相交的子集合。S1={1,2,4,7},S2={3,5,8}，S3={6,9,10}。集合{S1,S2,S3}就被稱為集合S的一種劃分。此外，在集合中還有常用的一些運算，如集合的交、并、補、差，以及判定一個元素是否是集合中的元素等。（2）線性結(jié)構(gòu)線性結(jié)構(gòu)指的是數(shù)據(jù)元素的有序集合，該結(jié)構(gòu)中數(shù)據(jù)元素之間存在著一對一的關(guān)系，線性表、棧、隊列、字符串都屬于線性結(jié)構(gòu)。（3）樹形結(jié)構(gòu)樹形結(jié)構(gòu)指的是數(shù)據(jù)元素的層次結(jié)構(gòu)，該結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對多的關(guān)系。（4）圖形結(jié)構(gòu)圖形結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對多的關(guān)系，圖形結(jié)構(gòu)也稱作網(wǎng)狀結(jié)構(gòu)。樹形結(jié)構(gòu)和圖形結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。69704.4.2數(shù)據(jù)的基本運算數(shù)據(jù)的運算即對數(shù)據(jù)施加的操作。數(shù)據(jù)的運算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個運算的集合，只有確定了物理結(jié)構(gòu)，才能具體實現(xiàn)這些運算。數(shù)據(jù)的運算通常包括以下5種操作。①插入：在指定位置上添加一個新節(jié)點。②刪除：刪除指定位置上的節(jié)點。③更新：修改某個節(jié)點的值。④查找：搜索滿足指定條件的節(jié)點及其位置。⑤排序：按指定的順序使節(jié)點重新排列。4.

5典型的數(shù)據(jù)結(jié)構(gòu)典型的數(shù)據(jù)結(jié)構(gòu)有線性表、棧、隊列、樹、圖等。1．線性表線性表是一種線性結(jié)構(gòu)，線性結(jié)構(gòu)的特點是數(shù)據(jù)元素之間存在一種線性關(guān)系，數(shù)據(jù)元素“一個接一個地排列”。在一個線性表中數(shù)據(jù)元素的類型是相同的，或者說線性表是由同一類型的數(shù)據(jù)元素構(gòu)成的線性結(jié)構(gòu)。在實際問題中線性表的例子是很多的，例如，學(xué)生信息表是線性表，表中數(shù)據(jù)元素的類型為學(xué)生類型；一個字符串也是一個線性表，表中數(shù)據(jù)元素的類型為字符型。線性表是具有相同數(shù)據(jù)類型的n（n≥0）個數(shù)據(jù)元素的有限序列，通常記為（a1,a2,…,ai-1,ai,ai+1,…,an）。其中n為表長，n=0時稱為空表，即沒有任何數(shù)據(jù)元素的線性表。線性表中相鄰元素之間存在著順序關(guān)系。將ai-1稱為ai的直接前趨，ai+1稱為ai的直接后繼。對于ai，當(dāng)i=2,…,n時，有且僅有一個直接前趨ai-1，當(dāng)i=1,2,…,n－1時，有且僅有一個直接后繼ai+1，而a1是表中第一個元素，它沒有直接前趨，an是最后一個元素，它沒有直接后繼。712．棧棧是限制在表的一端進行插入和刪除的線性表。允許插入、刪除的這一端稱為棧頂（StackTop），固定端稱為棧底。當(dāng)棧中沒有元素時稱為空棧。向棧中插入元素稱為進棧，從棧中刪除元素稱為出棧。元素的進棧和出棧使得棧頂?shù)奈恢媒?jīng)常變動。如圖4-9所示