1單元

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

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

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

3

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

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

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

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

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

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

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

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