計算機科學導論(第2版)第6章 程序設計與算法分析

計算機科學導論 學習計算機專業(yè)的第一門基礎課程 第六章 程序設計與算法分析 本章要點 初步了解程序設計的基礎知識 掌握結構化程序設計和面向對象程序設計的基本方法 掌握數(shù)據(jù)結構中的基本數(shù)據(jù)類型及其實現(xiàn) 掌握程序設計算法的基本思想及幾種經(jīng)典的算法 了解編譯原理的基本知識 程序的概念 程序 就是能夠實現(xiàn)特定功能的一組指令序列的集合。 程序設計 是程序員編寫一系列可存儲的指令以指示計算機完成某些工作的過程。這些指令用程序設計語言寫成。 程序設計語言 是一組專門設計的用來生成一系列可被計算機處理和執(zhí)行的指令的符號集合。 程序設計人員用程序設計語言寫成的指令稱作 代碼 。 程序設計基礎 計算機程序設計語言 分類： 低級語言、高級語言。 1）低級語言包括兩種類型：機器語言和匯編語言。 2） 機器語言 機器語言面向機器，可以由 不同的機器能夠識別的機器語言是不相同的。 機器語言指令都是用一串 0、 1構成的二進制位串來表示的。 指令系統(tǒng)是機器提供的機器指令的集合。 用二進制編碼表示的指令，稱為機器指令，或稱為機器碼。 用機器指令編寫的程序稱為機器語言程序，或稱為目標程序，這是計算機能夠直接執(zhí)行的程序。 機器語言難以閱讀和理解，編寫和修改都比較困難，而且通用性較差。 匯編語言 匯編語言也稱符號語言。 指令助記符是指令英文名稱的縮寫，容易記憶。 所謂匯編語言，就是采用字母、數(shù)字和符號來代替由一個個 0和 1構成的指令操作碼、寄存器、數(shù)據(jù)和存儲地址等，并在程序中用它們代替二進制編碼數(shù)，這樣編寫出來的程序就稱為符號語言程序或匯編語言程序。 大多數(shù)情況下，一條匯編指令直接對應一條機器指令，少數(shù)對應幾條機器指令。 匯編語言具有一個本質上與機器語言一一對應的指令系統(tǒng)。匯編語言的實質和機器語言是相同的。 低級語言的特點 都與特定的計算機硬件系統(tǒng)緊密相關，來自于特定系統(tǒng)的指令系統(tǒng)，可移植性差； 專業(yè)知識要求高，要求對計算機硬件的結構和工作原理非常熟悉； 每條指令的功能很單一，程序員編制源程序時指令比較繁瑣； 由于直接針對特定硬件編程，所以，最終的可執(zhí)行程序代碼精煉，而且執(zhí)行效率非常高。 兩者主要的區(qū)別在于：機器語言無需翻譯或編譯， 匯編語言必須經(jīng)過匯編才能得到目標程序。 匯編 雖然匯編語言比機器語言容易閱讀理解和便于檢查，所以仍然需要一種特殊的程序，該程序能夠將用匯編語言編寫的程序“翻譯”成 實現(xiàn)這種翻譯功能的特殊程序稱為 匯編語言翻譯程序、匯編程序或匯編器 。程序員手工編寫的程序統(tǒng)稱為源程序，用匯編語言編寫的源程序稱為匯編語言源程序，匯編程序將源程序翻譯得到的機器語言程序稱為目標程序，翻譯的過程稱為 匯編 。 反匯編程序 用于將目標代碼程序轉換成相應的匯編語言源程序，這一過程稱為反匯編。反匯編主要用于識別源程序代碼，常用的調試工具程序 高級語言的產(chǎn)生 一個問題：如何解決程序的可移植性，即：程序員編寫的源程序如何可以從一臺計算機很容易地轉到另一臺計算機上工作。為了解決這些問題，人們引入了高級語言來編寫程序。 所謂高級語言是一種由表達各種意義的“詞”和“公式”，按照一定的“語法規(guī)則”來編寫程序的語言，又稱為程序設計語言或算法語言。 高級語言之所以“高級”，就是因為它使程序員可以完全不用與計算機的硬件打交道，可以不必了解機器的指令系統(tǒng)。 程序員可以把硬件上復雜的概念比如存儲空間抽象成一個所謂的變量之類的概念，因而程序員就可以繞開硬件問題而集中精力解決問題本身，編程效率大大提高。 由于高級語言與具體機器無關，那么在一種機器上運行的高級語言程序可以幾乎不經(jīng)改動地移植到另一種機器上運行，大大提高了程序的通用性。 此外，由于高級語言與自然語言 (尤其是英語 )很相似，因此易學、易懂，也易編寫。 高級語言的常見類型 目前已經(jīng)有許多高級語言在流行，并且新的類型還在不斷出現(xiàn)和升級。 用戶在實際應用中進行程序設計時，可根據(jù)情況選擇適合的高級語言。 (1) (2) (3) (4) (5) (6) C+語言 (7) 其他高級語言 基于視窗類操作系統(tǒng)的，如 +、 高級語言的優(yōu)點是語句的功能強，源程序比較短，容易學習，使用方便，通用性較強，便于推廣和交流。 其缺點是編譯程序比匯編程序復雜，而且編譯出來的目標程序往往效率不高，目標程序的長度比有經(jīng)驗的程序員所編的同樣功能的匯編語言程序要長 半以上，運行時間也要長一些。 因此，在很多對時間要求比較高的系統(tǒng)，如某些實時控制系統(tǒng)或者大型計算機控制系統(tǒng)中，低級語言，主要是匯編語言，仍然得到了一定的應用。 高級語言的基本內容 高級程序設計語言依賴于各自特定的語句和語法。一條一條的語句是構成源程序的基本單位。高級語言的一條語句被編譯或解釋時往往會對應多條機器指令。 每一種編程語言都包含一組語句和語法。所謂語法，是指管理語言結構和語句的一組規(guī)則。不論使用何種設計語言，都必須遵循其語法規(guī)則。 以下內容主要描述了大多數(shù)高級語言都共同具備的特性，但不一定是所有高級語言都有的。 1高級語言的基本符號 高級語言都是由所謂的基本符號組成的。基本符號可以分為單字符和多字符兩種情況。單字符基本符號由單個字符組成，在高級語言中通常都有下列幾種單字符基本符號： (1) 字母 大寫英文字母 A Z，小寫英文字母 a z，共 52個符號。 (2) 數(shù)字 0 9，共 10個數(shù)字符號。 (3)特殊字符 (加 )， (減 )， *(乘 )， /(除 )， (乘方 )，(等號 )， (左括號 )， )(右括號 )， (大于 )，(小于 )， (逗號 )， (空格 )等。 在高級語言中的多字符基本符號由兩個或兩個以上的字符組成，例如 移 )、 (小于或等于 )、 )等等。 2高級語言的基本元素 基本元素由基本符號組成，可分為數(shù)、邏輯值、名字、標號和字符串等五大類。 (1) 數(shù) 它由 0 9共 10個基本數(shù)字和其他一些符號 (如小數(shù)點“ .”、正負號“、”及指數(shù)符號“ E”等所構成。 (2) 邏輯值 由真 (假 (個值表示。 (3) 名字 由字符組成，一般約定名字的開頭是字母或者下劃線，其后可為字母或數(shù)字，如 _字可用來定義常量、變量、函數(shù)、過程或子程序的，也被用來定義成某些東西，故也稱為標識符。在高級語言中，一般還規(guī)定了組成名字的字符的長度，即字符個數(shù)。 (4) 標號 是在高級語言中的程序語句前所加的一個名字，主要用來指示程序可能的轉移方向。 (5) 字符串 由一串字符所組成。在不同的高級語言中，字符串中的多個字符放在一對單引號或雙引號中。 3基本的數(shù)據(jù)類型 任何一種高級語言都會定義一些基本的數(shù)據(jù)類型?；镜臄?shù)據(jù)類型通常包括整數(shù)數(shù)據(jù)類型、實數(shù)數(shù)據(jù)類型和字符數(shù)據(jù)類型等。 在程序中，除了值無需改變的常數(shù)外，大部分數(shù)據(jù)的值是可以修改的。在程序中，變量是指代表某個具體數(shù)值，并且所代表的數(shù)值可改變的一個符號名字。 變量必須先定義，然后才能使用，這是 條基本原則。 變量實質上代表了一個特定大小的內存單元空間。 定義變量的實質就是讓程序為該變量分配一個特定的內存空間。 變量的類型實質上反映了該數(shù)據(jù)占用內存空間的大小，即分配給該變量代表的數(shù)據(jù)的所占據(jù)的內存單元的字節(jié)數(shù)目。 4結構數(shù)據(jù)類型 是在基本數(shù)據(jù)類型的基礎上構造出來的數(shù)據(jù)類型。數(shù)組和結構體是大多數(shù)高級語言都支持的兩種最基本的結構數(shù)據(jù)類型。 (1) 數(shù)組類型 數(shù)組是若干個相同類型的數(shù)據(jù)的集合。 (2) 用戶自定義的結構體類型 結構體是隸屬于同一個事物的多個不同類型的數(shù)據(jù)的集合，用來表示具有若干個屬性的一個事物。 除了以上兩種最基本的結構數(shù)據(jù)類型外，許多高級語言還有比如枚舉、集合，以及更復雜的隊列、堆棧等多種數(shù)據(jù)類型。 結構數(shù)據(jù)類型在使用時也必須定義相應類型的“變量”名字。 5運算符與表達式 表達式是由基本符號、基本元素和各種數(shù)據(jù)通過各種運算符連接而成的。按表達式的運算結果可以分為算術表達式、邏輯表達式和字符串表達式等幾種情況。 高級語言中的運算符大致包括以下幾個方面： (1) 邏輯運算： 與、或、非、異或。 (2) 算術運算： 加、減、乘、除、取模。 (3) 數(shù)據(jù)比較： 大于、小于、等于、不等于。 (4) 數(shù)據(jù)傳送； 輸入、輸出、賦值。 (5) 算術表達式： 該表達式的運算結果是數(shù)，它非常近似于日常的數(shù)學公式。 (6) 關系運算表達式： 該表達式的運算結果是邏輯值，常用的運算符包含 (大于 )、 (小于 )、 (等于 )、 (小于等于 )、 (大于等于 )、不等于。 (7) 字符串表達式： 該表達式的運算結果是字符串。 6語句 語句是構成高級語言源程序的基本單位，是由基本元素、運算符、表達式等組成。任何一種高級語言往往都支持賦值、條件判斷、循環(huán)、輸入輸出等語句。程序員利用這些語句的結合，能夠很方便地編制出功能強大的程序。 7庫函數(shù)和用戶自定義的函數(shù) 為了支持用戶編寫出功能強大的源程序，幾乎所有的高級語言都為用戶提供了豐富的庫函數(shù)，這些庫函數(shù)能夠實現(xiàn)某些特定的功能，比如計算一個比較復雜的數(shù)學函數(shù)。 在源程序中，用戶也可以自己定義自己的函數(shù) (子程序或過程 )，以便以后可以反復調用這些代碼集合。 8注釋 任何一種程序設計語言都強調注釋的重要性。源程序所包含的代碼往往比較冗長，添加必要的注釋不僅有助于閱讀程序，更重要的是，在需要對程序功能進行擴充時，注釋可以極大地幫助程序員對原始程序的理解。 經(jīng)常會出現(xiàn)這樣一種情況，程序員自己編寫的程序，經(jīng)過一段時間后，可能就是半年或者幾個月以后，程序員自己也讀不懂自己的程序了。況且，程序不僅要自己看得懂，更重要的是也要讓別人能夠看懂。 9程序設計風格 (1) 編碼格式和編碼約定在整個程序中應保持一致。 (2) 程序中應給出必要的注釋，尤其在變量定義、調用接口、參數(shù)傳遞處，在修改程序時應注明修改人、時間、簡要的修改原因。 (3) 對變量、函數(shù)標識等的命名，采用規(guī)范的命名方法，避免含義不明確的縮寫，從命名最好就可以一目了然讀出命名標識的含義和數(shù)據(jù)類型。 (4) 采用縮進格式，突出程序的邏輯層次結構。 (5) 每一行只寫一條語句，使用括號間隔表達式或語句的組成部分，使組成部分清晰； (6) 使用結構化、面向對象的編程技術，提高程序可重用性、可擴充性。 (7) 除非完全必要，應盡量避免多任務和多重處理。 (8) 盡量避免使用復雜的算術和邏輯表達式。 (9) 提高程序健壯性，預防用戶的操作錯誤，做到廢進廢出。 10高級語言程序的運行 使用高級語言編制程序的一般過程可以歸納為以下幾個步驟： (1) 使用文本編輯工具，逐條編寫源程序的語句。存儲源程序文件時文件的后綴名與所用的高級語言有關。 (2) 編譯源程序文件，生成目標文件，文件后綴名通常為 (3) 鏈接目標文件，生成可執(zhí)行文件，文件后綴名通常為 (4) 在計算機上執(zhí)行可執(zhí)行程序文件，進 步調試和維護。 結構化程序設計方法 采用 自頂向下、逐步求精 的設計方法和單入口單出口的控制結構。 1. 結構化程序設計思想 . . . . . . 二級子問題 二級子問題 二級子問題 需要解決的復雜問題 三級子問題 三級子問題 三級子問題 . . . . . . . . . 最小問題 最小問題 最小問題 結構化程序設計的 原則 是： (1) 使用順序、選擇、循環(huán) 3種基本控制結構表示程序邏輯。 (2)程序語句組織成容易識別的語句模塊，每個模塊都是單入口、單出口。 (3)嚴格控制 (a) 順序結構 (b) 選擇結構 (c) (d) A B 出口 假 真 入口 A B S 假 真 入口 S A 出口 假 真 入口 A S 2模塊 一個復雜的問題可以劃分為多個簡單問題的組合。 在自頂向下、逐步細化的過程中，把復雜問題分解成一個個簡單問題的最基本方法就是模塊化。 模塊化便于問題的分析，模塊體現(xiàn)了信息隱藏的概念。模塊常用子程序加以實現(xiàn)。 1面向對象的思想 向對象的程序設計方法 向對象 )的程序設計把客觀事物看作具有屬性和行為的對象，通過抽象找出同一類對象的共同屬性 (靜態(tài)特征 )和行為 (動態(tài)特征 )，形成類。 2對象和類 對象 是對現(xiàn)實問題的高度概括、分類和抽象。每個對象都只有自己的數(shù)據(jù)和相應的處理函數(shù)，整個程序是由一系列相互作用的對象來構成，不同對象之間是通過發(fā)送消息來實現(xiàn)相互聯(lián)系、相互作用。 方法 在對象內的操作通常叫做方法。 類 定義了一組大體上相似的對象。一個類所包含的方法和數(shù)據(jù)描述一組對象的共同行為和屬性。 對象則是類的具體化，是類的實例。 類通過派生可以有子類，同樣也可以有父類，形成層次結構。 3抽象 抽象 是對具體事物 (即對象 )進行概括，即忽略事物的非本質特征，只注意那些與當前目標有關的本質特征，從而抽象出一類對象的共性并加以描述。 對一個問題的抽象一般來講應該包括兩個方面：數(shù)據(jù)抽象和代碼抽象 (或稱為行為抽象 )。 4封裝性 封裝的兩個含義 ： 第一是，將抽象得到的數(shù)據(jù)成員和代碼成員相結合，形成一個不可分割的整體，即對象，這種數(shù)據(jù)及行為的有機結合也就是封裝。 第二個含義稱為信息隱蔽，即盡可能隱蔽對象的內部細節(jié)。在隱蔽對象內部細節(jié)的同時，對象需要提供與外部世界進行交流的接口，并實現(xiàn)對數(shù)據(jù)訪問權限的合理控制，把整個程序中不同部分的相互影響減少到最低限度。 5繼承性 繼承性 是父類和子類之間共享數(shù)據(jù)和方法的機制。在定義一個類的時候，可以以一個已經(jīng)存在的類為基礎，并把這個已經(jīng)存在的類所包含的屬性和方法作為自身的一部分，然后加入新的屬性和方法以區(qū)別于原來的類。 原有的類稱為 基類或父類 ，產(chǎn)生的新類稱為 派生類 。 6多態(tài)性 多態(tài)性 在收到外部消息時，對象通常要予以響應。不同的對象收到同一消息可能產(chǎn)生完全不同的結果。 1數(shù)據(jù)、數(shù)據(jù)類型 數(shù)據(jù) 是對客觀事物的符號表示。在計算機系統(tǒng)內，數(shù)據(jù)通常是指能夠輸入到計算機中并被計算機進行處理的符號的集合。 數(shù)據(jù)類型 是指具有相同取值范圍和可以實施同種操作的數(shù)據(jù)的集合的總稱。例如，在程序設計中，通常會有字符型、整型、數(shù)組等多種數(shù)據(jù)類型。 基本概念 數(shù)據(jù)結構 2數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象 能夠獨立并完整地描述客觀世界實體的基本數(shù)據(jù)單元稱為 數(shù)據(jù)元素 ，它是組成數(shù)據(jù)的基本單位。 數(shù)據(jù)項 是組成數(shù)據(jù)元素的不可分割的最小單位。最簡單的數(shù)據(jù)元素就是由一個數(shù)據(jù)項構成的。 同類數(shù)據(jù)元素的集合稱為 數(shù)據(jù)對象 。 3數(shù)據(jù)結構 數(shù)據(jù)結構 是指數(shù)據(jù)元素之間的相互關系的集合，包括了數(shù)據(jù)的邏輯結構、物理結構以及數(shù)據(jù)的運算。 數(shù)據(jù)的邏輯結構 數(shù)據(jù)的邏輯結構是指數(shù)據(jù)元素之間的邏輯關系。數(shù)據(jù)之間可以根據(jù)不同的關系組成不同的數(shù)據(jù)結構。 線性結構 數(shù)據(jù)結構中，如果數(shù)據(jù)元素之間存在著前后順序的關系，即除了第一個數(shù)據(jù)元素和最后一個元素外，其他每個元素都有惟一的一個前驅和一個后繼元素，這樣的數(shù)據(jù)元素之間的關系被稱為線性結構。 樹形結構 數(shù)據(jù)結構中，如果數(shù)據(jù)元素之間有順序關系，且除了一個被稱為根節(jié)點的元素外，每個元素都有一個前驅節(jié)點，并且可以有多個后繼節(jié)點，這種邏輯結構稱為樹形結構。 圖形結構 數(shù)據(jù)結構中，如果任何一個數(shù)據(jù)元素都可以有多個前驅節(jié)點和多個后繼節(jié)點，這種邏輯結構稱為圖形結構。 (2) 數(shù)據(jù)的物理結構 數(shù)據(jù)的物理結構是指邏輯結構在計算機存儲器中的表示。數(shù)據(jù)的物理結構不僅要存儲數(shù)據(jù)本身，還要存儲表示數(shù)據(jù)間的邏輯關系。 數(shù)據(jù)的物理結構主要有四種，分別是順序結構、鏈表結構、索引結構及散列結構。 順序結構 把所有元素存放在一片連續(xù)的存儲單元中，邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元中，由此得到的存儲表示稱為順序存儲結構。 順序存儲結構常借助于程序設計語言中的數(shù)組來實現(xiàn)。優(yōu)點是使用方法簡單，缺點是必須預先分析出所需定義數(shù)組的大小。 鏈表結構 對邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關系通過附設的指針域來實現(xiàn)，由此得到的存儲表示稱為鏈式存儲結構。 鏈式存儲結構通常借助于程序設計語言中的指針來實現(xiàn)。 索引結構 針對每個數(shù)據(jù)結構建立一張所謂的索引表，每個數(shù)據(jù)元素占用表中的一項，每個表項包含一個能夠惟一識別一個元素的關鍵字和用以指示該元素的地址指針。 散列結構 通過構造相應的散列函數(shù)，由散列函數(shù)的值來確定元素存放的地址。 (3) 數(shù)據(jù)運算 數(shù)據(jù)操作的集合。常見的數(shù)據(jù)操作有數(shù)據(jù)的插入、刪除、查找、遍歷等。 數(shù)據(jù)操作通常由計算機程序加以實現(xiàn)，通常也叫 算法實現(xiàn) 。 線性表 1定義 線性表 是由有限個相同的數(shù)據(jù)元素構成的序列，元素之間是一對一的線性關系，除了第一個元素只有直接后繼、最后一個元素只有直接前驅外，其余數(shù)據(jù)元素都有一個直接前驅和一個直接后繼，如圖。 元素 1 u a n s u 元素 2 1 元素 3 1 元素 n 1 2運算和實現(xiàn) 線性表通常采用順序和鏈表兩種物理實現(xiàn)。對于經(jīng)常變化的表，通常采取鏈表結構。線性表常用的運算主要有：插入、刪除、查詢和遍歷。 插入 在保持原有的存儲結構的前提下，根據(jù)插入要求，在適當?shù)奈恢貌迦胍粋€元素。插入操作要求線性表要有足夠的存放新元素的空間，如果空間不足，插入操作無法進行，線性表會溢出。 刪除 在線性表中，找到滿足條件的數(shù)據(jù)元素，并刪除。如果線性表為空，刪除就會失敗。 查詢 在線性表中，按照查詢條件，定位數(shù)據(jù)元素的過程就是查詢。查詢的條件一般根據(jù)數(shù)據(jù)元素中的關鍵字進行。實際上，數(shù)據(jù)的插入和刪除都需要首先定位數(shù)據(jù)元素。對于空的線性表是無法查詢的。 遍歷 是指按照某種方式，逐一訪問線性表中的每一個數(shù)據(jù)元素，并執(zhí)行相同處理的操作。這里的處理可以是讀、寫、或查詢等。 棧 1定義 對于由 果只允許在其固定的一端位置插入和刪除一個數(shù)據(jù)元素，那么這種邏輯結構的數(shù)據(jù)結構稱為 堆?；驐?( 允許插入或刪除的這一端稱為 棧項 ，另一個固定端稱為 棧底 。當表中沒有元素時稱為 空棧 。 2運算和實現(xiàn) 棧的基本運算主要有：入棧、出棧和判斷。 入棧 入棧也叫壓棧，是在棧頂添加新元素的操作，新的元素入棧后成為新的棧頂元素。 出棧 出棧也叫退?；驈棗?，是將棧頂元素從棧中退出并傳遞給用戶程序的操作 D C B A 入棧數(shù)據(jù)元素 E E D C B A D C B A 出棧數(shù)據(jù)元素 D C B A 判斷 判斷操作用來檢查棧內數(shù)據(jù)是否為空，返回結果是一個邏輯值：真或假。如果棧頂和棧底重合，說明堆棧為空。 隊列 1定義 對于由 果在其固定的一端只允許插入數(shù)據(jù)元素，且在另一端只允許刪除數(shù)據(jù)元素，則這種邏輯結構的數(shù)據(jù)結構稱為 隊列 ( 把允許插入的一端叫 隊尾 (把只允許刪除的一端叫 隊首 ( 2運算 隊列的基本運算主要有：入隊、出隊和判斷。 入隊 入隊是在隊列中插入一個新數(shù)據(jù)元素的過程，插入在隊尾進行，新的元素成為隊尾，。 出隊 出隊是在隊列中刪除一個數(shù)據(jù)元素的過程，刪除在隊首進行并把出來的數(shù)據(jù)傳遞給用戶程序。 A B C D E 頭指針 尾指針 A B C D E F G 頭指針 尾指針 F ， G 入隊 A B C D E 頭指針 尾指針 D E F G 頭指針 尾指針 A ， B ， C 出隊 判斷： 判斷操作用來檢查隊列是否為空，返回結果是一個邏輯值：真或假，如圖。 頭指針 尾指針 3循環(huán)隊列的實現(xiàn) F G A B C D E 頭指針 尾指針 內存塊第一個存儲單元 內存塊最后一個存儲單元 隊列移動 樹 1定義 樹形數(shù)據(jù)結構中，每個數(shù)據(jù)元素稱為是一個節(jié)點，除了一個惟一的所謂 根節(jié)點 外，其他每個節(jié)點都有且只有一個父節(jié)點，每個元素可以有多個子節(jié)點。 樹主要用在大型、動態(tài)列表的搜索，人工智能系統(tǒng)和編碼算法等問題中。 2運算 樹常見的基本運算有：插入、刪除和遍歷。 插入 在樹中合適的位置，添加一個節(jié)點，通常插入新的節(jié)點后，仍然應該保持該樹本身所具有的性質。 刪除 在樹中找到滿足條件的節(jié)點并刪除。通常刪除節(jié)點后，也要保持該樹本身所具有的性質。 遍歷 按照某種順序或規(guī)則，對樹中的每個節(jié)點逐一進行訪問的過程。 3實現(xiàn) A B C D E F 圖 1定義 在圖形結構中，每個數(shù)據(jù)元素稱為一個頂點，任意兩個頂點之間都可能相關，這種相關性用一條邊來表示，頂點之間的鄰接關系可以是任意的。 圖可以用來描述計算機網(wǎng)絡的拓撲結構，以及圖論中獲得最小生成樹。除此以外，圖在自然科學、社會科學和人文科學等許多領域也都有著非常廣泛的應用。 2運算 常見的基本運算有：添加頂點、刪除頂點、添加邊、刪除邊和遍歷圖。 添加頂點 在圖中添加新的頂點，新添加的頂點通常是孤立的節(jié)點，還沒有邊連接。 刪除頂點 在圖中去掉一個頂點，顯然，在去掉一個頂點的同時還應該刪除與該頂點所連接的邊。 添加邊 根據(jù)指定的頂點，添加相應的邊。 刪除邊 根據(jù)指定的頂點，刪除相應的邊。 遍歷圖 按照一定的規(guī)則，對圖中的每個數(shù)據(jù)頂點逐一進行訪問。 3實現(xiàn) 圖通常用數(shù)組和鏈表兩種結構加以實現(xiàn)。對于各個頂點和頂點之間的關系分別采用鄰接矩陣和鄰接列表來進行描述。 A B C D E A B E B A C E C B D E A B D D C E 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 A B C D E A B C D E ( a ) ( b ) ( c ) 概述 1算法的定義 準確地說，“ 算法 (一組明確的、可以執(zhí)行的步驟的有序集合，它在有限的時間內終止并產(chǎn)生結果”。 算法和數(shù)據(jù)結構之間存在密切聯(lián)系。數(shù)據(jù)結構是算法的基礎，數(shù)據(jù)結構的不同，通常的采用的算法也會不同；當問題的求解算法一旦確定，也可以選擇合適的數(shù)據(jù)結構加以實現(xiàn)，合理的數(shù)據(jù)結構能夠簡化算法。 算法分析基礎 (1) 有窮性 (可終止性 ) 一個算法必須在有限個操作步驟內以及合理的時間內執(zhí)行完成。 (2) 確定性 算法中的每一個操作步驟都必須有明確的含義，不允許存在二義性。 (3) 有效性 (可執(zhí)行性 ) 算法中描述的操作步驟都是可執(zhí)行的，并能最終得到確定的結果。 (4) 輸入及輸出 一個算法應該有零個或多個輸入數(shù)據(jù)、有 1個或多個輸出數(shù)據(jù)。 2算法的特性 3算法的描述 (1) 自然語言表示 自然語言就是人們日常使用的語言，可以是中文、英文等。 例如，求三個數(shù)中最大值的問題，可以描述為： 比較前兩個數(shù)； 將中較大的數(shù)與第三個數(shù)進行比較； 步驟中較大的數(shù)即為所求。 (2) 流程圖表示 流程圖是用規(guī)定的一組圖形符號、流程線和文字說明來表示算法的一種表示方法。 (3) 偽碼 偽碼用一種介于自然語言與計算機語言之間的文字和符號來描述算法。比計算機語言形式靈活，格式緊湊，沒有嚴格的語法。 (4) 程序設計語言形式 算法也可以用某種具體的計算機程序設計語言來表示，如， C、 C+、 例如，求兩個數(shù)的較大者。用偽代碼描述算法如下： s:a,b 1. a is or to b) a b 常用算法介紹 1遞歸算法 如果一個過程直接或間接地調用它本身，則稱該過程是遞歸的。 例如，數(shù)學階乘運算，可以用遞歸算法定義函數(shù) f (n)如下： 1!( 1 ) ! 遞歸的情況包括所謂的遞推法和分治法。 遞推 是從已知的初始條件出發(fā)，逐次推導出最后所求的值。遞推是利用問題本身所具有的一種遞推關系求解問題的一種方法。 分治法 也是一種廣泛使用的算法設計方法。其基本思想是把大問題分解成一些較小的問題。然后由小問題的解方便地構造出大問題的解。 2迭代算法 所謂迭代是指重復執(zhí)行一組指令或操作步驟，在每次執(zhí)行這組指令時，都從原來的解值的基礎上推出一個新的解值。新的解值比原來的解值更加接近真實的解。這個過程不斷重復，直到計算得到的解與真實解的誤差滿足實際要求。 迭代常常用于科學計算領域對某些無法直接求解的數(shù)值問題。 例如：現(xiàn)欲求解方程 f(x)=0的解。首先用某種數(shù)學方法導出等價的形式 x=g(x)，然后按以下步驟執(zhí)行： (1)選一個方程的近似根，賦給變量 (2)將 后計算 g(并將結果存于變量 (3)若 復步驟 (2)的計算。 如果方程有解，并且按照上述方法計算出來的近似根序列數(shù)學上收斂，則按上述方法求得的 3窮舉算法 亦稱枚舉法，該算法首先根據(jù)問題的部分條件確定問題解的大致范圍，然后在此范圍內對所有可能的情況逐一進行驗證，直到全部情況驗證完畢。 4貪婪算法 貪婪算法通常具有 貪婪選擇性 和 最優(yōu)子結構性 。 貪婪選擇性 指的是所求解問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪婪選擇來達到。 最優(yōu)子結構性 指的是一個問題的最優(yōu)解往往包含著它的子問題的最優(yōu)解。 現(xiàn)在我們假設顧客同樣希望找回總額為 16的硬幣。但是銀行發(fā)行的硬幣面額是分別變成了 1、5和 12單位的硬幣。按照上述的貪婪法，應該選擇 1枚面額 12的硬幣，然后選擇 4枚面額為 1的硬幣，硬幣總數(shù)為 5。而最優(yōu)解應該是選擇 3枚面額為 5的硬幣，然后選擇 1枚面額為 1的硬幣，總數(shù)為 4。此時，貪婪法的結果就不等于最優(yōu)解了。 算法的評價 對于一個算法的評價，通常要從 正確性、可理解性、健壯性、時間復雜性及空間復雜性 等多個方面加以衡量。相比而言，人們更關心的是與計算機系統(tǒng)資源密切相關的時間復雜性和空間復雜性。 在計算機系統(tǒng)內，求解問題的算法耗費的資源主要包括時間和空間，可以從分析算法的時間開銷和空間開銷入手，來分析算法的時間復雜性及空間復雜性。 1算法的時間復雜度 時間復雜度 (度量時間復雜性、即算法的時間效率的指標。時間復雜度是與求解問題規(guī)模、算法輸入相關的函數(shù)，該函數(shù)表示算法運行所花費的時間。 為了簡化問題，通常，用算法運行某段核心代碼的 次數(shù) 來代替準確的執(zhí)行時間，記為 T(n)，其中， 般是指待處理的數(shù)據(jù)量的大小。 引入符號“ O”，以此簡化時間復雜度 T(n)與求解問題規(guī)模 化后的關系是一種數(shù)量級關系。 時間復雜度最好的算法是常數(shù)數(shù)量級的算法。常數(shù)數(shù)量級的算法表示為 O (c)，其中 例如，如果某個算法的時間復雜度為 T(n)=n，那么，當求解規(guī)模趨于 T(n)/ ，表示算法的時間復雜度與 為T(n)=O( 多項式函數(shù)的時間復雜度有 O (n)， O ( O ( O (等，以及數(shù)量級介于上述數(shù)量級之間的 O ( O (n* O (n2*等。 2算法的空間復雜度 算法的 空間復雜度 (用來度量算法的空間復雜性、即執(zhí)行算法的程序在計算機中運行時所占用空間的大小。 簡單講，空間復雜度也是與求解問題規(guī)模、算法輸入相關的函數(shù)。記為 S(n)，其中 符號“ O”同樣被用來表示空間復雜度 S(n)與求解問題規(guī)模 例如，如果 S(n)= O(表示算法的空間復雜度與 為 S(n)=O( 空間復雜度的分析方法與時間復雜度的分析也是類似的，往往希望算法有常數(shù)數(shù)量級或多項式數(shù)量級的空間復雜度。 題，是非確定型多項式問題。所謂的非確定型，簡單講就是指算法無法直接計算出結果，只能通過進行一些有選擇的“猜算”來得到結果。 對于這類問題給出的算法并不能直接計算出結果，但可以檢驗某個可能的結果是正確的還是錯誤的。這個可以檢驗“猜算”的答案正確與否的算法，如果可以在多項式時間內解出，就是非確定型多項式 (題。 例如，找一個大的質數(shù)的問題。并不存在一個公式可以用來推算并找到這個大的質數(shù)，但是，如果事先給定一個數(shù)，程序卻可以在多項式時間內判斷出它是否滿足要求。 檢驗一個問題是否屬于 果在多項式時間內能夠證明該問題的任意“是”的實例是正確的，則該問題即為 目前關于 為典型的有裝箱問題、背包問題、著色問題等等。 這些問題的研究結果有兩種可能，一種是找到了求解問題的算法；另外一種就是求解問題的算法是不存在的，那么就要從數(shù)學理論上證明它為什么不存在。 編譯程序概述 語言處理的過程如圖所示。 編譯原理 匯編器 絕對機器碼 裝配連接編輯 編譯器 目標匯編程序 可重定位機器代碼 預處理器 骨架程序 源程序 可重定位目標文件庫 編譯程序的功能如圖所示。 編譯程序 低級語言程序 高級語言程序 解釋程序在處理源程序時，執(zhí)行方式類似于日常生活中的“同聲翻譯”。 解釋一句、執(zhí)行一句，立即產(chǎn)生運行結果。解釋程序不產(chǎn)生目標代碼，不能脫離其語言環(huán)境獨立執(zhí)行。 解釋程序對源程序的解釋執(zhí)行比編譯程序產(chǎn)生的目標代碼程序的執(zhí)行速度要慢。 編譯程序是把高級語言程序 (源程序 )作為一個整體來處理，首先將程序源代碼“翻譯”成目標代碼 (機器語言 )，編譯后與系統(tǒng)提供的代碼庫鏈接，形成 個完整的可執(zhí)行的機器語言程序 (目標程序代碼 )。 目標程序可以脫離其語言環(huán)境獨立執(zhí)行，使用比較方便、效率較高。相應地，由于每次執(zhí)行之前必須通過編譯得到可執(zhí)行程序，所以，可執(zhí)行程序一旦需要修改，必須先修改源代碼，再重新編譯生成新的目標文件 (*能執(zhí)行。 詞法分析器語法分析器語義分析器中間代碼生成優(yōu)化目標代碼生成源程序 目標代碼 表格管理 出錯處理 詞法分析 其任務是從左到右一個字符、一個字符地對源程序進行掃描，讀入源程序，對構成源程序的字符流進行掃描和分解，通過詞法分析從而識別出一個個單詞 (也稱單詞符號或符號 )。 例 對表達式： = 100；進行詞法分析。 對其進行詞法分析后得到以下結果： 單詞類型 單詞值 標識符 1( 算符 (賦值 ) := 標識符 2( 算符 (加 ) + 標識符 3( 算符 (乘 ) * 整數(shù) 100 分號 ； 語法分析 語法分析是編譯過程的第二個階段，任務是在詞法分析的基礎上將單詞序列分解成各類語法短語，如“程序”、“語句”、“表達式”等等。一般這種語法短語也稱為語法單位。 例 按照例 表達式： = 100；進行語法分析。 語法規(guī)則： :=“:=” :=“+” :=“*” :=“(”