計算機導論（第5版） 課件 第6章-程序設計知識

計算機導論第6章程序設計知識目錄CONTENTS03算法與程序設計01程序設計語言02Python語言程序設計0405數(shù)據結構與程序設計編譯原理與程序設計程序設計語言機器語言；匯編語言；早期高級語言；結構化程序設計語言；面向對象程序設計語言/01程序設計語言程序設計語言的定義簡單說法：程序設計語言是用來編寫計算機程序的語言。規(guī)范描述：程序設計語言是一種讓人與計算機之間進行交流，讓計算機理解人的意圖并按照人的意圖完成工作的符號系統(tǒng)。目前常用的高級程序設計語言主要有Python、C++、Java等。程序設計語言機器語言機器語言（machinelanguage）是由二進制編碼的機器語言指令構成的語言，是一種依附于機器硬件的語言。每種處理器（CPU）都有自己專用的機器語言指令集合，這些指令能夠被計算機直接執(zhí)行。每條機器語言指令完成一個簡單任務。一條機器語言指令由兩個部分組成：操作碼和操作數(shù)，操作碼用于說明指令的功能，操作數(shù)用于說明參與操作的數(shù)據或數(shù)據所在的寄存器編號或數(shù)據所在內存單元的地址。操作碼和操作數(shù)都是以二進制的形式表示。程序設計語言機器語言程序示例把兩個內存單元中的數(shù)據相加，并將結果存入另外一個單元。用機器語言編寫程序，編程人員必須要記住每條指令對應的二進制編碼是什么，編寫出來的程序就是由0和1組成的數(shù)字串。這樣就存在幾個方面的困難：指令難以準確記憶、程序代碼容易寫錯、程序難以理解和修改。程序設計語言匯編語言匯編語言（assemblylanguage）是由助記符指令構成的語言，也是一種依附于機器硬件的語言。在匯編語言中，使用助記符（類英文單詞）來表示指令的操作碼，使用存儲單元或寄存器的名字表示操作數(shù)。這樣，相對于機器語言，記憶匯編語言的指令就容易多了，編寫出的程序也比較容易理解。程序設計語言匯編語言匯編語言程序示例（把兩個內存單元中的數(shù)據相加，并將結果存入另外一個單元）實際上，計算機只能直接執(zhí)行由機器語言編寫的程序。用匯編語言編寫的程序稱為匯編語言源程序，需要首先翻譯成機器語言程序(目標程序)，才能被計算機執(zhí)行，完成這種翻譯工作的程序稱為匯編程序或匯編器。程序設計語言早期高級語言機器語言中的指令用二進制編碼表示，匯編語言中的指令用英文助記符表示。高級語言（highlevellanguage）中的語句用英文和數(shù)學公式表示，更容易被編程人員理解和掌握。使用高級語言編寫出的程序稱為高級語言源程序，也需要先翻譯成目標程序，才能為計算機理解和執(zhí)行。翻譯模式由2種：編譯模式和解釋模式。程序設計語言代表性早期高級語言FORTRAN語言：FORTRAN是公式翻譯器（FORmula

TRANslator）的縮寫，是第一個高級語言。FORTRAN語言用于數(shù)學公式的表達和科學計算，1957年FORTRAN的第一個版本研發(fā)成功，其編譯程序由25000行機器語言代碼組成。以后又陸續(xù)推出多個版本，包括結構化程序設計語言版本和面向對象的程序設計語言版本。ALGOL語言：ALGOL是算法語言（ALGOrithmLanguage）的縮寫。AIGOL語言也是用于科學計算，其最早版本是1958年出現(xiàn)的ALGOL58，后續(xù)版本有ALGOL60和ALGOL68，這兩個版本曾經在我國得到廣泛的學習和使用，其后繼語言Pascal出現(xiàn)后，ALGOL逐漸被淘汰。程序設計語言代表性早期高級語言COBOL語言：COBOL是面向商業(yè)的通用語言（COmmon

BusinessOrientedLanguage）的縮寫。COBOL語言用于企業(yè)管理和事務處理，1960年4月正式公布第一個COBOL文本，后續(xù)推出多個版本。BASIC語言：BASIC是初學者通用符號指令碼（Beginner′sAllpurposeSymbolicInstructionCode）的英文縮寫，1964年BASIC第1版發(fā)布。BASIC確實簡單、易學，一經推出，很快流行起來。BASIC語言在我國也曾經廣泛流行。程序設計語言結構化程序設計思想沿用編寫小程序的方法編寫中大規(guī)模的程序是不行的，往往導致編寫出的程序可靠性差、錯誤多且難以發(fā)現(xiàn)和修改。1969年，埃德斯加·狄克斯特拉提出了結構化程序設計的概念，強調從程序結構和風格上來研究程序設計，注重程序結構的清晰性，注重程序的可理解性和可修改性。經過幾年的探索和實踐，結構化程序設計方法的應用確實取得了成效，遵循結構化程序設計方法編寫出來的程序，不僅結構良好、容易理解和閱讀，而且容易發(fā)現(xiàn)和改正其中的錯誤。程序設計方法要有相應的程序設計語言支持。程序設計語言結構化程序設計語言Pascal語言：Pascal是一種通用的高級語言，是在ALGOL語言的基礎上發(fā)展起來的，以法國著名物理學家、數(shù)學家帕斯卡（BlaisePascal）的名字命名。帕斯卡不僅發(fā)現(xiàn)了帕斯卡定律，還在1642年曾經發(fā)明了齒輪式、能進行加減運算的機械式計算機，這是第一臺能進行加減運算的機械計算機。Pascal的第一個版本出現(xiàn)在1971年，20世紀70~90年代，Pascal語言有很大的影響，在我國也曾廣泛流行。程序設計語言結構化程序設計語言C語言：1963年，英國劍橋大學在ALGOL60的基礎上添加了硬件處理功能，推出了CPL語言，1967年推出了簡化版的CPL（BCPL）。1970年美國貝爾實驗室以BCPL為基礎，設計出更簡單且更接近硬件的B語言。但B語言過于簡單，功能有限。1972~1973年，貝爾實驗室在B語言的基礎上設計出了C語言。C語言既保持了BCPL和B語言精練、接近硬件的優(yōu)點，又彌補了它們過于簡單、無數(shù)據類型的不足。1973年，貝爾實驗室將用匯編語言編寫的UNIX操作系統(tǒng)用C語言改寫成UNIX第5版，C語言代碼占90%以上。1975年，用C語言編寫的UNIX第6版公布后，C語言的優(yōu)點引起人們的關注，隨著UNIX的日益廣泛使用，C語言也迅速得以推廣和廣泛應用。程序設計語言面向對象程序設計思想結構化程序設計方法在一定程度上保證了編寫較大規(guī)模程序的質量，但隨著時間的推移，也逐漸暴露了其在編寫大規(guī)模程序時的不足。面向對象方法不再將問題分解為過程，而是將問題分解為對象，對象將自己的屬性和方法封裝成一個整體，供編程人員使用，對象之間的相互作用則通過消息傳遞來實現(xiàn)。使用面向對象的程序設計方法，可以使人們對復雜系統(tǒng)的認識過程與程序設計過程盡可能一致，能夠更好地保證大程序的質量。面向對象的程序設計方法也要有面向對象程序設計語言支持。程序設計語言面向對象程序設計語言Simula67和Smalltalk：Simula67發(fā)布于1967年，被公認為是面向對象語言的鼻祖。20世紀80年代美國施樂帕羅奧多研究中心推出了Smalltalk，它完整地體現(xiàn)并進一步豐富了面向對象的概念。但由于當時人們已經接受并廣泛應用結構化程序設計方法，一時還難以完全接受面向對象的程序設計思想，這類純面向對象語言沒有能夠廣泛流行起來。C++語言：C++語言由貝爾實驗室的本賈尼·斯特勞斯特盧普在20世紀80年代初設計并實現(xiàn)的，它是以C語言為基礎、支持數(shù)據抽象和面向對象思想的通用程序設計語言。C++是C語言的擴充，借助于C語言的普及基礎，C++得到廣泛應用。

UNIXCC++程序設計語言面向對象程序設計語言Java語言是由SunMicrosystems公司于1995年5月推出的一個支持網絡計算的面向對象程序設計語言。Java語言吸收了Smalltalk語言和C++語言的優(yōu)點，并增加了并發(fā)程序設計、網絡通信和多媒體數(shù)據控制等特性，也是目前得到廣泛應用的一種面向對象程序設計語言。C#語言：C#語言是微軟公司發(fā)布的一種面向對象的、運行于.NETFramework之上的高級程序設計語言。C#在語法規(guī)則與系統(tǒng)結構上與Java有著很多的相似之處，比如它包括了單繼承機制、界面以及與Java幾乎相同的語法，是微軟公司基于.NET網絡框架進行系統(tǒng)開發(fā)的主角。程序設計語言面向對象程序設計語言Python語言：Python是一種完全面向對象的、解釋型的程序設計語言，1991年發(fā)布了第一個公開版本。由于Python語言易學易用以及有大量的內置庫和第三方庫可用，使得它成為一種得到廣泛應用的程序設計語言。本書以Python為例簡要介紹編程知識，詳細介紹可查閱袁方、肖勝剛、齊鴻志編寫的《Python語言程序設計（第2版）》一書。Python語言程序設計Python語言的特點；Python程序的執(zhí)行：Python的基礎語法；Python的基本數(shù)據類型Python的類型轉換；順序結構程序設計；分支結構程序設計；Python程序實例/02Python語言的特點易學易用Python語言的語法很多來自于C語言，但比C語言更為簡潔。相對于其他常用的程序設計語言，Python可以用更少的代碼實現(xiàn)相同的功能，更容易學習和使用，使編程人員更多地關注數(shù)據處理邏輯，而不是語法細節(jié)。庫函數(shù)豐富Python解釋器提供了幾百個內置庫，還有十幾萬個第三方庫可用，幾乎覆蓋了計算機應用的各個領域。在一定程度上說，使用Python編寫程序，是基于大量的現(xiàn)有內置庫和第三方庫中的函數(shù)（代碼）來組裝程序，大大簡化了編程工作，提高了編程效率和代碼質量。近幾年，人工智能（AI）得到快速發(fā)展和廣泛應用。由于有大量的AI庫可用和具備強大的數(shù)據處理能力，Python已成為人工智能領域的首選編程語言。Python程序的執(zhí)行命令行方式命令行方式是一種人機交互方式，用戶輸入一條Python語句或一個Python表達式，計算機就執(zhí)行語句或計算表達式的結果。IDLE實際上是一個Python的外殼，它提供了交互式的命令執(zhí)行方式，可以在提示符“>>>”后面輸入想要執(zhí)行的語句或表達式，回車后可以立即顯示執(zhí)行結果。命令行方式示例>>>print(“HelloWorld.”) >>>311**(1/3)Python程序的執(zhí)行程序文件方式在IDLE界面中，選擇菜單File→NewFile（新建文件），打開程序編輯窗口，可以輸入若干條語句，組成一個Python源程序。選擇菜單File→Save可以把程序代碼存盤，選擇菜單File→SaveAs…可以另存為…，選擇菜單File→Open可以打開已有文件，選擇Run→RunModule可以執(zhí)行程序文件，等等。Python的基礎語法Python標識符Python語言規(guī)定：標識符是由字母、數(shù)字和下畫線三種字符構成的，且第一個字符必須是字母或下畫線的字符序列。Python語言的變量、函數(shù)、文件等各種實體的名字都需要用標識符來表示。定義標識符時要注意如下幾點：必須以字母或下畫線作為開始符號，數(shù)字不能作為開始符號，但以下畫線開始的標識符一般都有特定含義，所以盡量不用以下畫線開始的自定義標識符。標識符中只能出現(xiàn)字母、數(shù)字和下畫線，不能出現(xiàn)其他符號。同一字母的大寫和小寫被認為是兩個不同的字符。關鍵字有特定的含義，不能用作用戶自定義標識符使用。盡可能做到見名知義，增加程序的可理解性。Python的基礎語法常量與變量常量：是指在整個程序的執(zhí)行過程中其值不能被改變的量，也就是所說的常數(shù)。在用Python語言編寫程序時，常量可以直接使用，常量的類型是由常量值本身決定的。例如,12是整型常量、34.56是浮點型常量、′a′和"Python"是字符串常量等。變量：是指在程序的執(zhí)行過程中其值可以被改變的量。變量要先定義（賦值），后使用。變量定義就是給變量賦值，格式如下：

變量名1,變量名2,…,變量名n=表達式1,表達式2,…,表達式n功能：為各變量在內存中分配相應的內存單元并賦以相應的值。分別計算出賦值號右邊各表達式的值，并依次賦給左邊的變量。Python的基礎語法常量與變量變量定義示例Python的基本數(shù)據類型整型整型就是整數(shù)類型。Python語言中整數(shù)的取值范圍很大，理論上沒有限制，實際取值受限于所用計算機的內存容量，對于一般應用場景足夠了。浮點型浮點型就是實數(shù)類型，表示帶有小數(shù)的數(shù)值。Python要求所有浮點數(shù)都必須帶有小數(shù)，便于和整數(shù)的區(qū)別，如6是整數(shù)，6.0是浮點數(shù)。雖然6和6.0值相同，但兩者在計算機內部的存儲方式和計算處理方式是不一樣的。Python的基本數(shù)據類型浮點型示例Python的基本數(shù)據類型布爾型布爾型也稱為邏輯型，用于表示邏輯數(shù)據。Python語言中，邏輯數(shù)據只有兩個值：False（假）和True（真）。需要注意的是，兩個邏輯值的首字母大寫，其他字母小寫。FALSE、false、TRUE、true等書寫方式都不是正確的Python邏輯值。布爾型示例Python的基本數(shù)據類型字符串型字符串型數(shù)據用于表示字符序列，字符串常量是由一對引號括起來的字符序列。Python語言有三種形式的字符串：一對單引號括起來的字符序列，如，′Python′、′程序設計′；一對雙引號括起來的字符序列，如"Python"、"程序設計"；一對三引號括起來的字符序列，如′′′Python′′′、′′′程序設計′′′。關于字符串的幾點解釋單引號括起來的字符串中可以出現(xiàn)雙引號，雙引號括起來的字符串中可以出現(xiàn)單引號，三引號括起來的字符串中可以出現(xiàn)單引號和雙引號。單引號或雙引號括起來的字符串只能書寫在一行內，三引號括起來的字符串可以書寫多行。Python的基本數(shù)據類型字符串型關于字符串的幾點解釋字符串有兩個特例，一個是單字符字符串，可稱為字符；另一個是不包含任何字符的字符串，稱為空字符串。由三引號括起來的字符序列，如果出現(xiàn)在賦值語句中或print()函數(shù)內，當作字符串處理;如果直接出現(xiàn)在程序中，當作程序注釋。字符串示例Python的基本數(shù)據類型字符串型轉義字符：Python語言中，以Unicode編碼存儲字符串，單個英文字符和單個漢字都被看作一個字符。如果用到控制符，只能寫成編碼值的形式。如09、0A（十六進制數(shù)）分別表示水平制表符、換行等。直接書寫編碼值的方式需要記憶編碼值，也容易寫錯。為此，Python語言給出了一種轉義符的表示形式，以反斜杠（\）開始的符號不再是原來的意義，而是轉換為新的含義。如＼n代表換行符，＼t代表水平制表符等。Python的基本數(shù)據類型字符串型字符串的訪問：對于字符串，除了可以整體使用外，還有兩種常用的訪問方式：索引方式和切片方式。索引訪問方式也稱為單字符訪問方式，語法格式如下：

字符串變量名[索引值]功能：從字符串中取出與索引值對應的一個字符。Python的基本數(shù)據類型字符串型切片訪問：該方式也稱為子串訪問方式，語法格式如下：

字符串變量名[i:j:k]功能：從字符串中取出多個字符。其中，i為開始位置，j為結束位置(但不包括j位置上的字符)，k為步長。參數(shù)i、j、k都可以省略。在步長k的值為正數(shù)時，省略i，其默認值為0；省略j，其默認值為正向最后一個字符的索引值加1。Python的基本數(shù)據類型字符串型字符串運算符Python的類型轉換int(x)函數(shù)int(x)函數(shù)的功能是把x的值轉換為整型數(shù)據，x為浮點數(shù)或由數(shù)字組成的字符串，可以帶正負號。float(x)函數(shù)float(x)函數(shù)的功能是把x的值轉換為浮點型數(shù)據，x為整數(shù)或由數(shù)字與最多一個小數(shù)點組成的字符串，可以帶正負號。Python的類型轉換eval(x)函數(shù)eval(x)函數(shù)把由純數(shù)字組成的字符串(可由正負號開始)轉換為整型，把由數(shù)字和1位小數(shù)點組合成的字符串(可由正負號開始)轉化為浮點型數(shù)據。eval()函數(shù)的語法格式如下：

eval(字符串)功能：將字符串的內容，即去掉界定符（引號）之后的表達式看作一個Python表達式，并計算出表達式的值作為函數(shù)的結果。順序結構程序設計賦值語句賦值語句的語法格式：

變量名1,變量名2,…,變量名n=表達式1,表達式2,…,表達式n功能：先計算出各表達式的值，然后依次賦給賦值運算符左邊的變量。一個賦值語句可以只給一個變量賦值，也可以同時給多個變量賦值。對于一些先進行運算再賦值的操作，Python語言還提供了7個常用的復合賦值運算符：+=、-=、*=、/=、%=、//=、**=。

順序結構程序設計用input()函數(shù)輸入數(shù)據使用input()函數(shù)輸入數(shù)據的語法格式如下：

變量=input("提示信息")功能：從鍵盤輸入數(shù)據并賦給變量，Python解釋器把用戶的輸入看作字符串。

順序結構程序設計用print()函數(shù)輸出數(shù)據使用print()函數(shù)輸出數(shù)據的語法格式如下：print(表達式1,表達式2,…,表達式n)功能：依次輸出n個表達式的值，表達式的值可以是整數(shù)、實數(shù)和字符串，也可以是一個動作控制符，如“\n”表示換行等。其中的表達式可以有一個，也可以有多個，多個表達式之間用逗號（,）分開，如果沒有任何表達式，print()函數(shù)的功能是實現(xiàn)一個換行動作。

順序結構程序設計結構化程序設計思想結構化程序設計方法強調程序結構的清晰性，結構化程序由3種基本結構組成：順序結構、分支結構和循環(huán)結構。順序結構是最簡單的一種程序結構。在順序結構程序中，程序的執(zhí)行是按照語句塊出現(xiàn)的先后次序順序執(zhí)行的，并且每個語句塊都會被執(zhí)行到。順序結構程序設計示例通過鍵盤輸入直角三角形的兩個直角邊邊長，計算斜邊邊長并輸出。分支結構程序設計if語句if語句用來實現(xiàn)單分支選擇，語法格式為：

if表達式:

語句塊if語句的執(zhí)行過程是：先計算表達式的值，若值為True（真），則執(zhí)行if子句（表達式后面的語句塊），然后執(zhí)行if結構后面的語句；否則，跳過if子句，直接執(zhí)行if結構后面的語句。分支結構程序設計if-else語句if-else語句用來實現(xiàn)雙分支選擇，其語法格式為：

if表達式:語句塊1else:語句塊2iif-else語句的執(zhí)行過程是：先計算表達式的值，若結果為True，則執(zhí)行if子句（語句塊1），否則執(zhí)行else子句（語句塊2）。循環(huán)結構程序設計for語句for循環(huán)語句的語法格式為：

for循環(huán)變量in遍歷結構:語句塊for循環(huán)語句的執(zhí)行過程是：循環(huán)變量從遍歷結構中取值，如果能取到值，就執(zhí)行循環(huán)體語句塊，然后再返回遍歷結構取值，如果能取到值，再次執(zhí)行循環(huán)體語句塊，直至遍歷結構中的數(shù)據取完為止。遍歷結構是指包含多個數(shù)據元素的復合數(shù)據。循環(huán)結構程序設計for循環(huán)程序示例從鍵盤輸入若干個以正整數(shù)表示的考試成績，計算總成績和平均成績并輸出。循環(huán)結構程序設計for語句中的range()函數(shù)range()函數(shù)的一般格式如下：range(start,end,step)功能：生成若干個整數(shù)值，初始數(shù)值為start，結束數(shù)值為end-1或end+1（注意,不包括end）,步長為step。當步長step為正數(shù)時，結束數(shù)值為end-1；當步長step為負數(shù)時，結束數(shù)值為end+1。其中,start和step都可以省略，省略時默認值分別為0和1。循環(huán)結構程序設計while循環(huán)語句while循環(huán)語句的語法格式為：

while表達式:語句塊

while語句的執(zhí)行過程是：先計算表達式的值，若表達式的值為True，則執(zhí)行循環(huán)體語句塊；然后再次計算表達式的值，若結果仍為True，再次執(zhí)行循環(huán)體語句塊；如此繼續(xù)下去，直至表達式的值變?yōu)镕alse，則結束while循環(huán)語句的執(zhí)行。

循環(huán)結構程序設計while循環(huán)程序示例從鍵盤上輸入若干個以正整數(shù)表示的考試成績，計算總成績和平均成績并輸出。與前面示例不同的是，不知道成績的個數(shù)，用輸入-1作為結束。循環(huán)結構程序設計帶else的循環(huán)語句帶else的for循環(huán)語句和while循環(huán)語句格式如下：

for循環(huán)變量in遍歷結構:while表達式:語句塊1語句塊1else:else:語句塊2語句塊2執(zhí)行過程：當循環(huán)語句正常結束時，執(zhí)行else對應的語句塊；當循環(huán)語句提前結束時，不執(zhí)行else對應的語句塊。帶else的循環(huán)語句一般要和break語句配合使用。循環(huán)結構程序設計break語句break語句的語法格式如下:breakbreak語句用于循環(huán)結構中，其功能是提前結束整個循環(huán)，轉去執(zhí)行循環(huán)結構后面的語句。continue語句continue語句的語法格式如下:continuecontinue語句也是用于循環(huán)結構中，其功能是提前結束本次循環(huán)，轉回到循環(huán)的開始判斷是否執(zhí)行下一次循環(huán)。循環(huán)結構程序設計帶break語句的循環(huán)程序示例從鍵盤上輸入一個大于1的正整數(shù)，判斷其是否為素數(shù)。帶else的for語句和break配合使用，使程序更為簡潔、邏輯清晰。循環(huán)結構程序設計Python程序實例從鍵盤輸入一個字符串，把字符串中的數(shù)字字符分離出來并組成一個整數(shù)，再乘以數(shù)字字符的個數(shù)后輸出，如果輸入“a23TY78hy”，則輸出數(shù)值9512(2378乘以4)。循環(huán)結構程序設計Python程序實例找出100～999中的所有水仙花數(shù)，所謂水仙花數(shù)是指該數(shù)的各位數(shù)字的立方和等于該數(shù)本身，如153=13+53+33。循環(huán)結構程序設計Python程序實例下面的程序畫出圓形螺旋線。循環(huán)結構程序設計Python程序實例下面的程序畫出正方形螺旋線。需要說明的是，正方形圖不是若干個正方形套在一起，而是一條線畫出來的。算法與程序設計算法的作用；算法的特性；算法的評價標準/03算法的作用用計算機解決問題的幾個主要階段分析問題、設計算法：認真分析要解決的問題及要實現(xiàn)的功能，給出解決問題的明確步驟，即設計出針對要解決問題的算法。選定語言、編寫程序：根據問題的性質，選定一種合適的程序設計語言（及相應的開發(fā)環(huán)境），依據算法編寫源程序。執(zhí)行程序：對編寫出的源程序進行編譯執(zhí)行或解釋執(zhí)行，程序中如果沒有語法錯誤，則會完成編譯或解釋并執(zhí)行程序，如果程序中存在語法錯誤，則編譯器或解釋器會給出提示信息，包括錯誤的位置及錯誤的性質等，可根據提示信息找到錯誤并且改正。算法的作用用計算機解決問題的幾個主要階段程序調試測試：沒有語法錯誤，并不能說明程序完全無錯，可能還存在語義（邏輯）錯誤。程序通過編譯或解釋后，要選用一些有代表性的數(shù)據對程序進行測試，經過一定的測試，如果沒有發(fā)現(xiàn)錯誤，程序就可以交付使用了。如果在測試中發(fā)現(xiàn)錯誤，就要分析錯誤的性質，根據錯誤的性質修改算法或修改程序（程序排錯），對于較大規(guī)模的程序，程序排錯是一項困難的工作，既需要經驗，也需要一定的方法和工具支持。初學編程者感覺難點在于語言基本要素和語法規(guī)則的掌握，而實際上編寫高質量、高性能程序的難點是良好的算法設計，相對于算法設計，編寫程序是比較簡單的。算法的作用算法與程序設計示例（從鍵盤輸入40個數(shù)，找出其中的最大值并輸出）。思路1：通過鍵盤輸入40個數(shù)并分別存入40個變量a1、a2、a3、……、a40中，之后首先找出變量a1、a2中的較大者存入maxi，然后把變量maxi的值依次與變量a3、a4、a40中的值比較，如果maxi中的值小，則替換maxi的值，最后保留在maxi中的值就是40個數(shù)中的最大值。按思路1把程序代碼完整寫出來，一共會有121行代碼。這才有40個數(shù)據，如果是400個數(shù)據、4000個數(shù)據，更多的數(shù)據呢？很顯然，用這種思路編寫程序不是一個好方法，即這種找最大值的算法不好。算法的作用算法與程序設計示例（從鍵盤輸入40個數(shù)，找出其中的最大值并輸出）?；谒悸?的程序代碼算法的作用算法與程序設計示例（從鍵盤輸入40個數(shù)，找出其中的最大值并輸出）。思路2：假定第1個數(shù)就是最大值，存入maxi變量；然后第2個數(shù)和maxi中的值進行比較，如果第2個數(shù)大，則用其替換掉maxi中的值，否則保持maxi中的值不變；這樣第3個數(shù)，第4個數(shù)，……，第40個數(shù)，一直比較下去，maxi中總是保存比較過的數(shù)的最大值。按思路2編寫的程序只有6行代碼，而且，即使有400個數(shù)據、4000個數(shù)據，或更多的數(shù)據，用這6行代碼同樣能夠把其中的最大值找出來。算法的作用算法設計與程序設計示例（從鍵盤輸入40個數(shù)，找出其中的最大值并輸出）。按思路2編寫的程序代碼。好的算法對于高效率編寫高質量程序是多么的重要。實際上，包括人臉識別、機器翻譯、智能問答等人工智能應用在內的很多應用，我們看到的是在計算機或手機上運行的程序（軟件），而程序（軟件）的背后是高水平、巧妙的算法設計。

算法的特性算法的定義算法（algorithm）就是為解決一個問題而采取的方法和步驟。程序（program）是指為讓計算機完成特定的任務而設計的指令序列或語句序列，一般認為機器語言程序或匯編語言源程序由指令序列構成，而高級語言源程序由語句序列構成。程序設計（programming）是用來溝通算法與計算機的橋梁；程序是程序設計人員編寫的、計算機能夠理解并執(zhí)行的指令序列或語句序列，程序是解決問題的算法在計算機中的具體實現(xiàn)。算法的特性算法的特性有窮性：一個算法必須總是在執(zhí)行有限個操作步驟和可以接受的時間內完成其執(zhí)行過程。即對于一個算法，要求其在時間和空間上均是有窮的。確定性：算法中的每一步都必須有明確的含義，不允許存在二義性?？尚行裕核惴ㄖ忻枋龅拿恳徊讲僮鞫紤撃苡行У貓?zhí)行，并最終得到確定的結果。輸入及輸出：一個算法應該有零個或多個輸入數(shù)據，有一個或多個輸出數(shù)據。執(zhí)行算法的目的是為了求解，而“解”就是輸出，因此沒有輸出的算法是沒有意義的。從這個簡單的例子可以看出，好的算法對于高效率編寫高質量程序是多么的重要。實際上，包括人臉識別、機器翻譯、智能問答等人工智能應用在內的很多應用，我們看到的是在計算機或手機上運行的程序（軟件），而程序（軟件）的背后是高水平、精巧的算法設計 算法的評價標準算法的正確性算法的正確性是指算法能夠正確地求解所要解決的問題，就目前的研究來看，要想通過理論方式證明一個算法的正確性是非常復雜和困難的，一般采用測試的方法，基于算法編寫程序，然后對程序進行測試。針對所要解決的問題，選定一些有代表性的輸入數(shù)據，經程序執(zhí)行后，查看輸出結果是否和預期結果一致，如果不一致，則說明程序中存在錯誤，應予以查找并改正。經過一定范圍的測試和程序修改，不再發(fā)現(xiàn)新的錯誤，程序可以交付使用，在使用過程中仍有可能發(fā)現(xiàn)錯誤，再繼續(xù)修改，這時的修改稱為程序維護。從這個簡單的例子可以看出，好的算法對于高效率編寫高質量程序是多么的重要。實際上，包括人臉識別、機器翻譯、智能問答等人工智能應用在內的很多應用，我們看到的是在計算機或手機上運行的程序（軟件），而程序（軟件）的背后是高水平、精巧的算法設計 算法的評價標準算法的正確性程序測試示例：從鍵盤輸入兩個自然數(shù)并分別賦值給n1和n2（n1<n2），輸出n1～n2之間的所有偶數(shù)。測試此程序時，如果給n1、n2分別輸入1和9，則會輸出4個偶數(shù)：2、4、6、8，結果是正確的，如果據此就認定程序正確，是不行的。實際上，如果給n1、n2分別輸入1和10，輸出結果仍然是4個偶數(shù)：2、4、6、8，這個結果是不正確的，原因在于range(n1,n2)中的n2應為n2+1，因為range(n1,n2+1)的取值范圍才是n1～n2，而range(n1,n2)的取值范圍是n1～n2-1，顯然不符合題目要求。算法的評價標準算法的時間復雜度算法的時間復雜度是指依據算法編寫出程序后，在計算機上運行時所耗費的時間度量。一個程序在計算機上運行的時間取決于程序運行時輸入的數(shù)據量、對源程序編譯所需要的時間、執(zhí)行每條語句所需要的時間以及語句重復執(zhí)行的次數(shù)。其中，最重要的是語句重復執(zhí)行的次數(shù)。通常，把整個程序中語句的重復執(zhí)行次數(shù)之和作為該程序的時間復雜度，記為T(n)，其中n為問題的規(guī)模。算法的時間復雜度T(n)實際上是表示當問題的規(guī)模n充分大時，該程序運行時間的一個數(shù)量級度量，用O表示。算法的評價標準算法的時間復雜度示例百錢買百雞問題：百錢買百雞問題出自于我國古代數(shù)學史上的杰作《張丘建算經》，張丘建是我國南北朝時期北魏數(shù)學家，書中對百錢買百雞問題的描述是：“今有雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。凡百錢買雞百只，問雞翁、母、雛各幾何？”算法的評價標準算法的時間復雜度示例這個程序總的循環(huán)次數(shù)是100萬次（即100×100×100次），即需要驗證100萬種可能的組合，時間復雜度為O(n3)。改寫后程序的循環(huán)次數(shù)為660次，時間復雜度降低為O(n2)。算法的評價標準算法的空間復雜度算法的空間復雜度是指依據算法編寫出程序后，在計算機上運行時所需內存空間大小的度量，也是和問題規(guī)模n有關的度量。算法的可理解性算法主要是為了人們的閱讀與交流，可理解性好的算法有利于人們的正確理解，有利于程序員據此編寫出正確的、易于理解的程序。為增強程序的可理解性，要注重培養(yǎng)良好的編程風格。數(shù)據結構與程序設計概念和術語；線性結構；樹形結構；圖狀結構/04數(shù)據結構概述數(shù)據結構的作用程序要處理的數(shù)據需要存儲在內存單元中，整個內存空間是由連續(xù)編址的一個個內存單元組成的，多么復雜的數(shù)據也只能存放在這樣的一個一維空間內，這是數(shù)據存儲的物理結構。對于矩陣、家族關系表、交通運輸網這樣的數(shù)據，如果編程人員直接使用數(shù)據存儲的物理結構，會大大增加編程的難度和工作量。能否找到一種機制，使得數(shù)據的內部存儲結構（物理結構）是線性連續(xù)的，而其邏輯結構更符合人們習慣的方式，編寫程序時面對的是邏輯結構，程序執(zhí)行時，由支持相應結構的編譯程序自動把邏輯結構映射成物理結構，從而簡化程序的編寫，減輕編程人員的工作量。數(shù)據結構概述數(shù)據結構的概念和術語數(shù)據是信息的載體，它能夠被計算機識別、存儲和加工處理。計算機科學中，所謂數(shù)據就是計算機加工處理的對象，它可以是數(shù)值數(shù)據，也可以是非數(shù)值數(shù)據，如圖像、聲音、文本等。數(shù)據項是數(shù)據不可分割的最小單位。數(shù)據項有名和值之分，數(shù)據項名是數(shù)據項的標識，用變量定義，而數(shù)據項值是它的一個可能取值。年齡就是一個數(shù)據項，在Python中可以定義為變量age，其取值可以是19、20等。數(shù)據元素是數(shù)據的基本單位，具有完整、確定的實際意義。數(shù)據元素一般由若干數(shù)據項組成。學生的基本情況就是一個數(shù)據元素，由學號、姓名、性別、年齡等數(shù)據項組成。數(shù)據結構概述數(shù)據結構的概念和術語數(shù)據對象或稱數(shù)據元素類，是具有相同性質的數(shù)據元素的集合，是數(shù)據的一個子集。在某個具體問題中，數(shù)據元素都具有相同的性質，屬于同一數(shù)據對象，數(shù)據元素是數(shù)據元素類的一個實例。對于一個學生管理系統(tǒng)來說，某大學所有學生的基本情況就是數(shù)據，所有本科生的基本情況、所有碩士研究生的基本情況可以看作是不同的數(shù)據對象。數(shù)據結構（datastructure）指互相之間存在著一種或多種關系的數(shù)據元素的集合。在任何問題中，數(shù)據元素都不是孤立的，它們之間存在著這樣或那樣的關系（聯(lián)系），這種數(shù)據元素之間的關系稱為結構。數(shù)據結構概述三種基本數(shù)據結構線性結構：數(shù)據元素之間存在著一對一的關系，如線性表、棧、隊列和數(shù)組等。按學號排列的學生數(shù)據可以看作是一個線性表，每個學生有且只有一個前驅（第一個學生除外）、有且只有一個后繼（最后一個學生除外）。樹形結構：數(shù)據元素之間存在著一對多的關系，如樹、二叉樹等。一個單位的工作人員之間的關系就可以表示成一棵樹，每個人有一個直接領導（單位的最高領導除外）和多個直接下屬（最基層的工作人員除外）。數(shù)據結構概述三種基本數(shù)據結構圖狀結構：數(shù)據元素之間存在著多對多的關系，圖狀結構也稱網狀結構，如無向圖和有向圖等。鐵路交通圖是一種典型的圖狀結構，任意兩個城市之間可能存在多條路徑連通。數(shù)據結構概述數(shù)據的物理結構與邏輯結構數(shù)據的邏輯結構描述的是數(shù)據元素之間的邏輯關系（如矩陣、樹、圖等）。數(shù)據在計算機中的表示稱為數(shù)據的物理結構或存儲結構，它研究數(shù)據結構在計算機中的實現(xiàn)方法，包括數(shù)據元素的表示及元素間關系的表示。數(shù)據的存儲結構可采用順序存儲或鏈式存儲的方法。順序存儲是把邏輯上相鄰的元素存儲在物理位置也相鄰的存儲單元中，由此得到順序存儲結構，常借助于編程語言中的數(shù)組或列表等來實現(xiàn)。鏈式存儲對邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關系通過附設的指針字段來表示，由此得到鏈式存儲結構。鏈式存儲結構通常借助于編程語言中的指針來實現(xiàn)。線性結構

線性結構是最常用、最簡單的數(shù)據結構，包括線性表、隊列、棧等，C語言中的數(shù)組、Python語言中的列表和元組都是線性結構。線性表、隊列、?？梢杂脭?shù)組或列表來實現(xiàn)，本節(jié)以Python語言中的列表為例介紹線性結構的使用。列表(list)是包含0個或多個數(shù)據的有序序列，其中的每個數(shù)據稱為元素，列表的元素個數(shù)(列表長度)和元素內容都是可以改變的。使用列表，能夠靈活方便地對批量數(shù)據進行組織和處理。線性結構創(chuàng)建列表創(chuàng)建列表的語法格式如下：列表名=[值1,值2,值3,…,值n]功能：把一組值放在一對方括號內組織成列表值并賦值給一個列表變量。列表值可以有0個、1個或多個，如果有多個列表值，值與值之間用逗號分隔。線性結構訪問列表訪問列表中元素的語法格式如下：

列表名[索引值]列表是序列類型，其中的元素按所在的位置順序都有一個唯一的索引值(序號)，通過這個索引值可以訪問到指定的元素。Python為列表元素設置了兩套索引：從0開始遞增索的正向引和從-1開始遞減的逆向索引。線性結構增加列表元素增加列表元素的語法格式如下：列表名.append(新增元素值)或

列表名.insert(索引值,新增元素值)其中，append()函數(shù)用于在列表的末尾追加元素，insert()函數(shù)用于在列表的指定位置插入元素。線性結構刪除列表元素刪除列表元素的語法格式如下：列表名.remove(元素值)或

del列表名[索引值]其中，remove()函數(shù)用于從列表中刪除指定的值，若有多個值和指定值相同，只刪除第一個。del格式用于刪除和指定索引值對應的列表元素值。線性結構修改列表元素值修改列表元素值的語法格式如下：列表名[索引值]=新元素值通過賦值語句的形式，用新元素值替換指定位置的現(xiàn)有元素值。對于已創(chuàng)建列表，既可以修改某個指定索引值對應的元素值，也可以修改指定索引值范圍內的若干元素值。線性結構修改列表元素值如果給定的新值個數(shù)多于指定范圍內的元素值個數(shù)(如lst2[-1:]=["金融學","二班"])，則相當于增加元素值。如果給定的新值個數(shù)少于指定范圍內的元素值個數(shù)(如lst2[1:3]=[“張明”])，則相當于刪除元素值。線性結構常用列表操作線性結構常用列表操作線性結構列表應用示例統(tǒng)計一批數(shù)據中奇數(shù)的個數(shù)。線性結構列表的元素還是列表（二維列表）如果一個列表中的元素也是列表，其實表示的是二維表或二維數(shù)組。在Python語言中，可以用元素為列表的列表表示其他高級語言中的二維數(shù)組。對于下圖所示的二維表數(shù)據，可以定義為如下列表：data_lst=[[1,2,3,4],[5,6,7,8],[9,10,11,12]]線性結構二維列表應用示例輸出楊輝三角前n行的數(shù)據，n的值由用戶輸入。問題分析6行的楊輝三角數(shù)據如上圖（a）所示，為了便于描述，給出上圖（b）的形式。從圖（b）可以看出，各行數(shù)據的共同特點是：第1列和最后一列的值全為1，從第3行開始，其他位置的值等于其左上方位置值和正上方位置值之和。可以把整個楊輝三角的數(shù)據存入一個列表（yanghui_lst），其中的每個元素（代表三角形中每行的數(shù)據）也是一個列表（row_lst）。第1、2行的數(shù)據可以直接賦值，從第3行開始，逐個生成數(shù)據存入行列表row_lst，再將行列表作為元素值存入三角形列表yanghui_lst中。線性結構二維列表應用示例輸出楊輝三角前n行的數(shù)據，n的值由用戶輸入。樹形結構樹的定義樹（tree）是n（n≥0）個結點的有限集合。

當n=0時，稱為空樹。在一棵非空樹T中：有且僅有一個特定的結點稱為樹的根結點；當n>1時，除根結點之外的其余結點被分成m（m≥1）個互不相交的集合T1，T2，…，Tm，其中每一個集合Ti（1≤i≤m）本身又是一棵樹，并且稱為根結點的子樹。樹中的一個結點可以看作是一個數(shù)據元素。樹形結構可以定義為Python中的字典。樹形結構創(chuàng)建字典創(chuàng)建字典的語法格式如下：

字典名={鍵1:值1,鍵2:值2,鍵3:值3,…,鍵n:值n}功能：字典也是由若干個元素組成，由一對大括號括起來，每個元素是一個“鍵:值”對的形式，“鍵:值”對之間用逗號分開。如果有多個“鍵”相同的“鍵:值”對，只保留最后一個。樹形結構訪問字典訪問字典的語法格式如下：字典名[鍵]功能：字典中的元素沒有對應的索引值，元素的存儲順序可能與創(chuàng)建字典時的書寫順序不一致。對字典的訪問是根據“鍵”來找對應的“值”。樹形結構對字典的操作樹形結構更新字典更新字典的語法格式如下：字典名[鍵]=值使用賦值語句可以增加元素或修改現(xiàn)有元素的值。如果在字典中沒有找到指定的“鍵”，則在字典中增加一個“鍵:值”對，如果找到，則用指定的“值”替換現(xiàn)有值。該語句既能增加元素，又能修改元素值。使用此功能要仔細，否則，本來要進行修改操作，由于“鍵”沒寫對，實際是完成了增加元素的功能。樹形結構字典合并字典合并的語法格式如下：字典名1.update(字典名2)如果兩個字典的“鍵”沒有相同的，則把字典2的“鍵:值”對添加到字典1中(實現(xiàn)兩個字典的合并)，如果有相同的，用字典2中的值修改字典1中相同“鍵”的對應“值”。樹形結構刪除字典元素或字典語法格式如下：

del字典名[鍵]如果在字典中找到指定的“鍵”，則刪除“鍵”和對應的“值”，如果沒有找到指定的“鍵”，則會報錯。如果只有字典名，則刪除整個字典。還可以使用pop()函數(shù)刪除字典元素，語法格式如下：

字典名.pop(鍵,值)如果字典中存在指定的“鍵”，則返回對應的“值”，同時刪除該“鍵:值”對，如果指定的“鍵”不存在，返回函數(shù)中給出的“值”。樹形結構字典應用示例基于字典實現(xiàn)學生信息管理：可以把學生信息組織成一個字典，以學號為“鍵”，其他信息為“值”，但這個“值”又是一個字典，可以實現(xiàn)查找、統(tǒng)計、修改等功能，如下程序實現(xiàn)了根據輸入查找某個專業(yè)的學生信息的功能。樹形結構字典應用示例某單位A有如圖所示的內部機構設置，編寫程序實現(xiàn)某部門上下級部門的查找。樹形結構字典應用示例某單位A有如圖所示的內部機構設置，編寫程序實現(xiàn)某部門上下級部門的查找。把樹形結構的內部機構設置定義為字典樹形結構字典應用示例定義函數(shù)，用于在字典dic中查找結點node的上、下層結點。樹形結構字典應用示例某單位A有如圖所示的內部機構設置，編寫程序實現(xiàn)某部門上下級部門的查找。在主程序中調用函數(shù)，實現(xiàn)查找功能。執(zhí)行程序的輸出結果如下：圖狀結構圖的定義和術語圖是由非空的頂點集合和邊的集合組成的。對于左下圖，其頂點集合V＝{v1,v2,v3,v4,v5}，邊的集合E＝{(v1,v2)，(v1,v4)，(v2,v3)，(v2,v5)，(v3,v4)，(v3,v5)，(v4,v5)}在一個圖中，如果頂點之間的連線（邊）是無向的，稱該圖為無向圖(左下圖)；如果頂點之間的連線是有向的，稱該圖為有向圖(右下圖)。圖狀結構圖的存儲結構對于下