1、1第9章 程序設計基礎9.1 程序和程序設計語言9.2 程序設計9.3 算法9.4 數(shù)據(jù)結(jié)構21、計算機程序的概念 指用某種程序設計語言編寫的為解決某個實際問題或完成某項任務的指令序列。9.1 程序和程序設計語言3Private Sub p_Click() Rem 計算圓的面積 Dim r As Single，Area As Single r= Val(txtInput1.Text) Area = 3.14159 * r * r txtCircle.Text = Str(Area)End Sub例:用VB編寫的能實現(xiàn)輸入圓的半徑，計算圓的 面積。程序代碼：42、程序設計語言及分類 計算機語言是

2、編寫計算機程序所用的語言, 是人與計算機進行交流的工具。 常用語言: Visual Basic 、C語言、Visual C+、 Visual Foxpro、Java、Delphi（1）程序設計語言的定義5（2）計算機語言的分類按照計算機語言的發(fā)展過程，分為：機器語言匯編語言低級語言高級語言6低級語言 高級語言計算機語言機器語言匯編語言PASCALCBASICFORTRAN依賴于機器獨立于機器7機器語言 第一代語言，由0、1代碼組成，計算機(機器)能直接執(zhí)行的語言。 為了解決某一特定問題，需要選用指令系統(tǒng)中的某些指令，這些指令按照要求組織起來就組成程序。8例如，計算15+10的機器代碼程序如下：

3、 10110000 00001111 00101100 00001010 111101009匯編語言 第二代語言，也稱符號語言，便于識別記憶，用助記符表示一條機器指令。 如： ADD 表示加法 MOV 將數(shù)據(jù)送寄存器10例如，計算15+10的匯編程序代碼： MOV A，15ADD A，10HLT11高級語言 第三代語言：面向過程語言。與人們?nèi)粘Ｊ煜さ淖匀徽Z言和數(shù)學語言更接近。 如：FORTRAN、 BASIC、PASCAL、C等。 第四代語言：面向?qū)ο蟪绦蛟O計語言。 如：VB、VC+、VFP、Delphi、JAVA等 其他：LISP（用于人工智能） PROLOG（人工智能）、Ada（用于軍事）

4、 12 例如，要計算15+10，并輸出結(jié)果，用Visual Basic編寫的程序段： Dim A As Integer A=15+10 Print A 133、語言處理程序 （1）語言處理系統(tǒng) 語言處理系統(tǒng)的作用是將匯編語言程序或高級語言程序變換成可在計算機上運行的程序,或最終的計算結(jié)果，或其他中間形式。14語言處理系統(tǒng)包括：語言處理程序（翻譯程序）：用于將匯編語言程序或高級語言程序翻譯成目標程序。正文編輯程序：用于建立和修改源程序。連接程序：用于將多個分別編譯或匯編過的目標程序和庫文件進行組合。裝入程序：用于將目標程序裝入內(nèi)存執(zhí)行。15正文編輯編譯連接裝入執(zhí)行結(jié)果程序模塊1程序模塊n源程序1

5、源程序n目標程序1目標程序n庫文件可執(zhí)行的目標程序語言處理系統(tǒng)16 概念 語言處理程序是指預先編制好的起翻譯作用的翻譯程序。 作用 將匯編語言和高級語言編制的程序(源程序)翻譯成機器語言程序(目標程序)。（2）語言處理程序17源程序語言處理程序（翻譯程序）目標程序源程序：用源語言（匯編語言或高級語言） 寫的有待翻譯的程序。目標程序：也稱為結(jié)果程序，是源程序通過 翻譯程序加工以后所生成的程序。翻譯程序：是指一個把源程序翻譯成等價的 目標程序的程序。語言處理程序的作用:18匯編程序：編譯程序 解釋程序匯編語言源程序機器語言目標程序高級語言源程序機器語言目標程序語言處理程序的分類 根據(jù)所處理的語言和

6、處理方法的不同分為三種類型：19 編譯方式 （相當于“筆譯”） 效率高，高級語言大多采用。實現(xiàn)算法較為復雜?？梢砸淮涡缘禺a(chǎn)生高效運行的目標程序，并把它保存在外存上，以備多次執(zhí)行。適合于翻譯規(guī)模大、結(jié)構復雜、運行時間長的大型應用程序。 如： PASCAL、C、BASIC、FORTRAN等。 20高級語言源程序編譯程序目標程序可執(zhí)行程序執(zhí)行結(jié)果連接程序（編譯）（執(zhí)行）編譯方式的工作過程為：21源程序分析綜合符號表、常數(shù)表中間語言程序目標程序編譯程序工作過程22 解釋方式 （相當于“口譯”） 工作過程為：邊翻譯邊執(zhí)行，即逐句掃描、逐句翻譯、逐句執(zhí)行。 解釋程序結(jié)構簡單、易于實現(xiàn)，便于實現(xiàn)人機對話。但

7、效率較低。 如：BASIC等。解釋程序高級語言源程序執(zhí)行結(jié)果逐句解釋并執(zhí)行234、常用計算機語言介紹 FORTRAN C、C+、Visual C+ Java Basic、Visual Basic Delphi end of 9.1241、程序設計的步驟（1）分析問題和建立模型（2）算法設計（3）編制程序（4）調(diào)試運行程序（5）編寫程序文檔 9.2 程序設計252、程序設計的方法（1）結(jié)構化程序設計 是一種結(jié)構分解，模塊化設計的方法，它采用自頂向下、逐步求精的方法，將整個系統(tǒng)功能逐層分解，直到每個模塊具有明確的功能和適當?shù)膹碗s度，有三種基本結(jié)構：順序、選擇和循環(huán)。262、程序設計的方法（2）面向

8、對象的程序設計 面向?qū)ο蟮某绦蛟O計是以對象為中心來分析問題和解決問題的。其對象是指將數(shù)據(jù)和操作數(shù)據(jù)的方法封裝在一起而形成的一種實體，它具有獨立的功能，并隱藏了實現(xiàn)這些功能的復雜性。273、程序的基本組成（1）數(shù)據(jù)成分 數(shù)據(jù)是程序操作的對象，具有名稱、類型、作用域等特征。數(shù)據(jù)是有類型的，如：整型、單精度類型等. 例如有定義語句： Dim x as single 283、程序的基本組成（2）控制成分 程序的三種基本結(jié)構：順序結(jié)構、選擇結(jié)構、循環(huán)結(jié)構，其流程圖分別為：29三種基本結(jié)構：語句1語句2T語句塊條件表達式F表達式語句塊1語句塊2TF基本結(jié)構的特點：每個結(jié)構只有一個入口和一個出口；結(jié)構內(nèi)的每

9、一個部分都有機會被執(zhí)行到；順序結(jié)構中的語句序列可以包含三種基本結(jié)構；循環(huán)結(jié)構中沒有死循環(huán)。303、程序的基本組成（3）三種基本結(jié)構的實現(xiàn) 賦值語句； if語句； for語句和while語句。end of 9.2311、算法的概念 算法是為解決某個問題而采用的一組明確的、有一定順序的步驟。 例如： （1）輸入兩個數(shù)，將大數(shù)存于X，小數(shù)存于Y； （2）判斷m是否為素數(shù)； （3）求a和b的最大公約數(shù)。9.3 算 法322、算法的特征確定性有窮性可行性有0個或多個輸入有1個或多個輸出333、算法的描述自然語言傳統(tǒng)流程圖 P257N-S流程圖偽代碼344、算法的評價end of 9.3時間復雜度 （計算

10、機等級考試知識點） P25835（1）數(shù)據(jù)結(jié)構的概念（2）數(shù)據(jù)的邏輯結(jié)構（3）數(shù)據(jù)的存儲結(jié)構（4）數(shù)據(jù)的運算1、數(shù)據(jù)結(jié)構概述9.4 數(shù)據(jù)結(jié)構36 數(shù)據(jù)結(jié)構研究對象是程序設計中計算機操作對象以及它們之間的關系和運算，也就是研究如何在計算機中組織數(shù)據(jù)，如何處理數(shù)據(jù)。數(shù)據(jù)結(jié)構研究的內(nèi)容包括三部分： 數(shù)據(jù)的邏輯結(jié)構 數(shù)據(jù)的存儲結(jié)構 數(shù)據(jù)的運算（1）數(shù)據(jù)結(jié)構的概念37數(shù)據(jù)結(jié)構的定義： 指相互間存在一種或多種特定關系的數(shù)據(jù)元素的集合?；蛲ㄋ椎卣f，數(shù)據(jù)結(jié)構是帶有結(jié)構的數(shù)據(jù)元素的集合。 這里，數(shù)據(jù)元素是是指計算機操作對象的個體。它是數(shù)據(jù)的基本單位。結(jié)構是指數(shù)據(jù)元素之間的相互關系。 38 數(shù)據(jù)元素具有廣泛的含義

11、。一般來說，現(xiàn)實世界中各觀存在的一切個體都可以是數(shù)據(jù)元素。 如：描述一年四季的季節(jié)名： 春、夏、秋、冬 表示作為數(shù)值的各個數(shù)： 18、11、35、23、16 表示家庭成員的各成員： 父親、兒子、女兒39 一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個元素之間存在某種關系（即聯(lián)系）。通常把數(shù)據(jù)元素之間這種固有的關系簡單地用前趨和后繼關系來描述。如一年四季中，“春”是“夏”的前趨，“夏”是“春”的后繼。40數(shù)據(jù)的邏輯結(jié)構的定義 數(shù)據(jù)的邏輯結(jié)構是數(shù)據(jù)間關系的描述。它抽象地反映數(shù)據(jù)元素間的邏輯關系。數(shù)據(jù)的邏輯結(jié)構的分類 根據(jù)各元素之間的前趨和后繼關系的不同特性，可將數(shù)據(jù)的邏輯結(jié)構分為線性結(jié)構和非線性

12、結(jié)構兩大類。（2）數(shù)據(jù)的邏輯結(jié)構41 線性結(jié)構：每個元素最多有一個前趨、一個后繼，如線性表、堆棧、隊列等。其結(jié)構描述如下：42 非線性結(jié)構：如果一個數(shù)據(jù)結(jié)構不是線性結(jié)構，則稱為非線性結(jié)構，如樹、圖等。其結(jié)構描述如下： 43 集合 結(jié)構中的數(shù)據(jù)元素間除了“同屬于一個集合”的關系外，別無其他關系。如 1，3，5 。 線性結(jié)構 線性結(jié)構的數(shù)據(jù)元素只按先后次序連接，數(shù)據(jù)元素間存在一對一的關系。 線性結(jié)構在程序設計中應用最為廣泛。 常用的線性結(jié)構有： 線性表、堆棧、隊列 基本的數(shù)據(jù)結(jié)構44 線性表是最常用、最簡單的一類線性邏輯結(jié)構，它由n（n0）個具有相同類型的數(shù)據(jù)元素構成的有限序列。 假設某線性表由a

13、1，a2，an個元素序列構成，該線性表結(jié)構如下圖所示。線性表中元素的數(shù)據(jù)類型可以為任意已知的數(shù)據(jù)類型。a1a2a3aian線性表45說明： 在一個稍復雜的線性表中，一個元素可以由若干個數(shù)據(jù)項組成。例如，一個班級的學生成績表中，表的每一行可看作一個數(shù)據(jù)元素，可以把這個表格理解為一個線性表的邏輯結(jié)構。46 堆棧是一種操作上受限的線性表，它只允許在一端進行插入和刪除操作。允許進行操作的一端稱為棧頂，棧頂?shù)奈恢檬请S插入和刪除操作動態(tài)變化的。不允許操作的一端稱為棧底。這種結(jié)構的特點是“后進先出”，因此堆棧也被稱為“后進先出表”。 堆 棧47數(shù)據(jù)入棧次序為： a1，a2，an。數(shù)據(jù)出棧次序為： an，an

14、-1，a1。 設有一堆棧S，有一個元素序列a1，a2，an，an所在位置是棧頂，a1所在位置是棧底。棧頂棧底48 隊列也是一種操作上受限的特殊線形表，它和堆棧所受的限制不同，只允許在表的一端進行插入操作，在另一端進行刪除操作。隊列中允許插入的一端稱為隊尾，允許刪除的一端稱為隊首。因此，這樣的隊列又稱為“先進先出表”。 假設有一隊列，元素有a1，a2，an。 隊 列49上圖中隊列入隊次序為：a1，a2，an上圖中隊列出隊次序為：a1，a2，an隊尾隊首50 樹形結(jié)構的數(shù)據(jù)元素是分層次的縱向連接，數(shù)據(jù)元素間存在一對多的關系。樹形結(jié)構根結(jié)點：A兄弟結(jié)點：B、C、D葉子結(jié)點：K、L 基本的數(shù)據(jù)結(jié)構51

15、根結(jié)點：A兄弟結(jié)點：B、C、D葉子結(jié)點：K、L相關術語： 根結(jié)點、子樹、父親結(jié)點、 孩子結(jié)點（子結(jié)點）、兄弟結(jié)點、 葉子結(jié)點52 在樹形結(jié)構中，常用的是二叉樹。它是一種特殊的樹結(jié)構，它只有一個根結(jié)點，它的每個結(jié)點最多有兩個子結(jié)點，且有先后次序。左邊的結(jié)點稱為左孩子，右邊的結(jié)點稱為右孩子。根結(jié)點右孩子左孩子二叉樹53 圖形結(jié)構的數(shù)據(jù)元素有各種各樣的復雜連結(jié)，數(shù)據(jù)元素間存在多對多的關系。圖是由一組數(shù)據(jù)元素（稱為頂點）的有限集和描述頂點間相互關系的邊（或?。┑挠邢藜M成。圖分為：有向圖和無向圖。 圖形結(jié)構 基本的數(shù)據(jù)結(jié)構54有向圖：在有向圖中，頂點與頂點之間的連線 是具有方向的，這樣的連線稱為弧。無

16、向圖：在無向圖中，頂點與頂點間的連線是 沒有方向的，這樣的連線稱為邊。55 數(shù)據(jù)的邏輯結(jié)構在計算機存儲器中的表示（又稱映像）稱為數(shù)據(jù)的存儲結(jié)構（或物理結(jié)構）。 數(shù)據(jù)的存儲結(jié)構包括兩個方面內(nèi)容，即數(shù)據(jù)元素的表示和關系的表示。 數(shù)據(jù)的邏輯結(jié)構通過不同的存儲映像方法（順序映像和非順序映像）可得到不同的存儲結(jié)構。（3）數(shù)據(jù)的存儲結(jié)構56數(shù)據(jù)的存儲結(jié)構分為四種：順序存儲結(jié)構鏈接存儲結(jié)構索引存儲結(jié)構散列存儲結(jié)構 線性結(jié)構可采用順序、鏈接、索引、散列四種存儲結(jié)構，而樹形結(jié)構和圖形結(jié)構等非線性結(jié)構一般采用鏈接存儲結(jié)構。 57 順序存儲結(jié)構 順序存儲結(jié)構是把一組結(jié)點存放在地址相鄰的存儲單元里，結(jié)點間的邏輯關系用

17、存儲單元的自然順序關系來表達的，即用一塊連續(xù)存儲區(qū)域存儲線性數(shù)據(jù)結(jié)構。 因為順序存儲方法的存儲空間除了存儲有用數(shù)據(jù)外，沒有用于存儲其他附加的信息，所以順序存儲結(jié)構一般也被稱為緊湊存儲結(jié)構。 順序存儲結(jié)構的優(yōu)點是結(jié)構簡單，可節(jié)省存儲空間。它的缺點是由于要求連續(xù)的存儲單元，因此可能產(chǎn)生較多的碎片。58線性表的順序存儲結(jié)構： 假設線性表中有n個元素a1，a2，an，第一個元素地址為ADR（a1），每個元素占k個字節(jié)，則線性表中第i個元素的存儲地址為： ADR（ai）=ADR（a1）+（i-1）*k59 鏈接存儲結(jié)構是在結(jié)點的存儲結(jié)構中附加指針字段來存儲結(jié)點間的邏輯關系。 鏈接存儲結(jié)構中數(shù)據(jù)結(jié)點包括兩

18、部分： 數(shù)據(jù)域：存放結(jié)點本身的數(shù)據(jù)。 指針域：存放指向其后繼結(jié)點的指針。即存放與該數(shù)據(jù)元素相鄰接的元素的地址。指針完成了兩個元素的連接，代表了元素間的邏輯關系。鏈接存儲結(jié)構60 鏈接存儲結(jié)構的優(yōu)點: 是不要求連續(xù)的存儲空間，使用較靈活。 它的缺點：是結(jié)點指針要占用額外的存儲空間。61 鏈接存儲結(jié)構舉例1：鏈接存儲結(jié)構的學生表 鏈接表是以指針方式表示的“線性表結(jié)構”。在鏈接表中，每個結(jié)點由兩部分組成，即數(shù)據(jù)域和指針域。 數(shù)據(jù)域：存放數(shù)據(jù)元素自身的信息，包括學號、姓名等。用標識符data表示這些域的全體； 指針域：存放指針，即存放與該數(shù)據(jù)元素相鄰接的元素的地址。用標識符link來表示。62 表中的

19、第n個學生元素的link值為(空指針，或用0表示)，表示它是鏈接表的最后一個元素。頭指針用head來表示。鏈接存儲結(jié)構的“學生表”63結(jié)點的存儲結(jié)構二叉樹的鏈接存儲結(jié)構鏈接存儲結(jié)構舉例2：二叉樹的鏈接存儲結(jié)構64 索引存儲結(jié)構 索引存儲結(jié)構就是用數(shù)據(jù)元素的索引號來確定數(shù)據(jù)元素的存儲地址。 索引號:在線性結(jié)構中，數(shù)據(jù)元素可排成一個有序的序列R1，R2，Rn，每個元素的Ri在序列里都有一個對應的位置碼i，這就是元素的索引號。65 一般索引存儲有兩種實現(xiàn)方法： 一是建立附加的索引表，索引表里第i項的值就是第i個元素的存儲地址。 另一種是當每個元素所占內(nèi)存單元數(shù)相等時，可用地址碼i的線性函數(shù)值來確定元

20、素的存儲地址。 索引存儲結(jié)構的優(yōu)點是檢索速度快，缺點是增加了附加的索引表，會占用較多的存儲空間。66 散列存儲結(jié)構是在數(shù)據(jù)元素與其在存儲器中的存儲位置之間建立一個映像關系。這個映像關系可以用一個稱做散列函數(shù)的函數(shù)來表示。根據(jù)數(shù)據(jù)元素的值，利用散列函數(shù)就可計算出它的地址。 散列存儲結(jié)構的優(yōu)點是檢索、增加、刪除結(jié)點的操作速度快，缺點是采用不好的散列函數(shù)時可能出現(xiàn)結(jié)點單元的碰撞，而需要附加時間和空間開銷。散列存儲結(jié)構67 每一種數(shù)據(jù)結(jié)構都有一個運算的集合。 常用的運算有檢索（查找）、插入、刪除、更新、排序等。 數(shù)據(jù)的運算定義在數(shù)據(jù)的邏輯結(jié)構上，而其運算的具體實現(xiàn)要在其存儲結(jié)構上實現(xiàn)。例如：從學生表中

21、刪除一個學生元素，向家族樹中 插入一個元素等。（4）數(shù)據(jù)的運算68 (1)線性表的概念 線性表是最常用、最簡單的一類線性邏輯結(jié)構，它是由n個具有相同類型的數(shù)據(jù)元素構成的有限序列。其簡單結(jié)構如圖所示：2、線性表A1A2An-1An69 插入、刪除、排序、查找、分解、合并等。（2） 線性表的運算 順序存儲結(jié)構的線性表的運算 鏈接存儲結(jié)構的線性表的運算70順序存儲結(jié)構的線性表的運算插入運算：在線性表中插入一個新元素。 在一般情況下，要在第i個元素元素之前插入一個新元素時，首先要從最后一個元素開始，直到第n-i+1個元素依次后移一個位置，移動結(jié)束后，第i個位置被空出，然后將新元素插入。插入結(jié)束后，線性

22、表的長度就增加1。71刪除運算：在線性表中刪除一個元素。 在一般情況下，要刪除第i個元素時，首先要從i+1個元素開始，直到第n個元素依次向前移動一個位置，刪除結(jié)束后，線性表的長度就減少1。72（a）長度為8的線性表（b）插入87后的線性表（c）插入14后線性表線性表的插入運算舉例：在下面圖（a）所示的線性表中插入87和14。73線性表的刪除運算舉例：在下面的圖（a ）所示的線性表中刪除29和31（a）長度為8的線性表（b）刪除29后的線性表（c）刪除31后的線性表74插入運算 在鏈表中指定元素前插入新元素。刪除運算 刪除指定的元素。鏈接存儲結(jié)構的線性表的運算75插入運算 查找指定元素。 給新元

23、素分配一個結(jié)點，然后將存放新元素的結(jié)點鏈接到指定的位置。76 例如，在下面的（a）所示的鏈表中值為x的元素前插入值為值為b的元素。77刪除運算查找指定元素。通過改變被刪除元素的所在結(jié)點的前一個結(jié)點的指針域，刪除指定結(jié)點。將被刪除元素送回可利用棧。78 例如，在下面的（a）所示的鏈表中刪除值為x的元素。79（1）棧的概念 棧是一種操作上受限制的線性表，它只允許在一端進行插入和刪除操作，因此又稱為“后進先出表”。其簡單結(jié)構如圖所示：3、棧AnA2A180（2）棧的存儲結(jié)構 ?？梢圆捎庙樞虼鎯Y(jié)構，也可用連接存儲結(jié)構，但是對棧的操作只能在棧頂進行。81（3）棧的基本運算 入棧：在棧頂插入一個元素。步

24、驟為：將棧頂指針加1，然后在棧頂插入新元素。 出棧：從棧頂取出一個元素。步驟為：取出棧頂元素，并賦給一個指定的變量，然后將棧頂指針退1。82 隊列也是一種操作上受限制的線性表，它只允許在一端進行插入操作，另一端進行刪除操作，因此又稱為“先進先出表”。其簡單結(jié)構如圖所示：4、隊列的概念A1 A2 An83（2）隊列的存儲結(jié)構 隊列可以采用順序存儲結(jié)構，也可用連接存儲結(jié)構，但是對隊列的操作只能在隊尾插入新元素和在隊首刪除元素。84（3）隊列的基本運算 入隊：在隊尾插入一個元素。步驟為：將隊尾指針加1，然后將新元素插入到隊尾指針指向的位置。 出隊：在隊首刪除一個元素。步驟為：由于在實際應用中，一般采用循環(huán)隊列，因此先將隊首指針加1，然后將隊首指針指向的元素賦給指定的變量。 讀棧頂運算： 將棧頂元素賦給一個指定的變量。此運算不刪除棧頂元素。85（1）樹的定義 樹是由n個節(jié)點組成的有限集合，如下圖所示：5、樹形結(jié)構86（2）樹形結(jié)構的常用術語 根節(jié)點 子樹 子節(jié)點（孩子節(jié)點） 父節(jié)點（雙親節(jié)點） 兄弟姐妹節(jié)點 葉子節(jié)點87（3）二叉樹的定義 二叉樹是樹形結(jié)構的一種重要類型，它的每個節(jié)點最多有兩個節(jié)點，它或者是空集，或者只有左子樹，或者只有右子樹，或者只有根節(jié)點，