第5章程設計知識

1、 計算機導論（計算機導論（20142014）第第5 5章章 程序設計知識程序設計知識5.1 5.1 程序設計語言程序設計語言5.2 c5.2 c語言程序設計語言程序設計5.3 5.3 數(shù)據(jù)結構數(shù)據(jù)結構5.4 5.4 編譯原理編譯原理 計算機導論（計算機導論（20142014）5.1 5.1 程序設計語言程序設計語言機器語言機器語言匯編語言匯編語言高級語言高級語言結構化程序設計語言結構化程序設計語言 面向對象程序設計語言面向對象程序設計語言可視化程序設計語言可視化程序設計語言 人工智能程序設計語言人工智能程序設計語言學習語言是設計程序的基礎 計算機導論（計算機導論（20142014）5.1.1

2、5.1.1 機器語言機器語言機器語言的特點機器語言的特點 由二進制編碼指令構成的語言由二進制編碼指令構成的語言。是一種依附于機器硬件的語言。是一種依附于機器硬件的語言。機器語言程序可以直接執(zhí)行。機器語言程序可以直接執(zhí)行。機器語言程序片段機器語言程序片段 0001 0101 01101100 /把地址為把地址為01101100的內存單元中的數(shù)裝入的內存單元中的數(shù)裝入0101號寄存器號寄存器 0001 0110 01101101 /把地址為把地址為01101101的內存單元中的數(shù)裝入的內存單元中的數(shù)裝入0110號寄存器號寄存器 0101 0000 01010110 /把把01101100和和011

3、01101中的數(shù)相加中的數(shù)相加,結果存入結果存入0000號寄存器號寄存器 0011 0000 01101110 /把把0000號寄存器中的數(shù)存入地址為號寄存器中的數(shù)存入地址為01101110的內存單元中的內存單元中 計算機導論（計算機導論（20142014）5.1.2 5.1.2 匯編語言匯編語言匯編語言的特點匯編語言的特點 由助記符指令構成的語言由助記符指令構成的語言。也是一種依附于機器硬件的語言。也是一種依附于機器硬件的語言。匯編語言源程序需要匯編后才能執(zhí)行。匯編語言源程序需要匯編后才能執(zhí)行。匯編語言程序片段匯編語言程序片段 mov r5, x /把內存單元把內存單元x中的數(shù)裝入中的數(shù)裝入

4、r5寄存器寄存器 add r5, y /把把r5中的數(shù)與中的數(shù)與y單元中的數(shù)相加，結果存入單元中的數(shù)相加，結果存入r5 mov z, r5 /把把r5中的數(shù)存入中的數(shù)存入z單元中單元中 計算機導論（計算機導論（20142014）5.1.3 5.1.3 高級語言高級語言高級語言的特點高級語言的特點 由自然語言和數(shù)學公式表示的語言由自然語言和數(shù)學公式表示的語言。是一種獨立于機器硬件的語言。是一種獨立于機器硬件的語言。高級語言程序需要編譯后才能執(zhí)行。高級語言程序需要編譯后才能執(zhí)行。高級語言程序片段高級語言程序片段 z=x + y /把內存單元把內存單元x中的數(shù)與中的數(shù)與y中的數(shù)相加，結果存入中的數(shù)相

5、加，結果存入z單元單元 計算機導論（計算機導論（20142014）5.1.3 5.1.3 高級語言高級語言常用高級語言常用高級語言 fortran語言語言 fortran是是formula translator（公式翻譯器）的縮寫。（公式翻譯器）的縮寫。 主要用于復雜的科學計算領域。主要用于復雜的科學計算領域。algol語言語言 algol是是algorithm language（算法語言）的縮寫。（算法語言）的縮寫。 主要用于數(shù)學與科學計算。主要用于數(shù)學與科學計算。 計算機導論（計算機導論（20142014）5.1.3 5.1.3 高級語言高級語言常用高級語言常用高級語言 cobol語言語言

6、 cobol是是common business-oriented language（面向商業(yè)的（面向商業(yè)的通用語言）的縮寫。通用語言）的縮寫。 主要用于企業(yè)管理和事務處理。主要用于企業(yè)管理和事務處理。basic語言語言 basic是是beginners all-purpose symbolic instruction code（初（初學者通用符號指令碼）的縮寫。學者通用符號指令碼）的縮寫。 主要用于初學者和較小規(guī)模的程序開發(fā)。主要用于初學者和較小規(guī)模的程序開發(fā)。 計算機導論（計算機導論（20142014）5.1.4 5.1.4 結構化程序設計語言結構化程序設計語言早期程序設計方法的不足早期程序

7、設計方法的不足注重功能的實現(xiàn)注重功能的實現(xiàn)/注重內存的節(jié)省注重內存的節(jié)省/注重執(zhí)行效率的提高。注重執(zhí)行效率的提高。不注重程序結構的清晰性。不注重程序結構的清晰性。不注重程序的可理解性和可修改性。不注重程序的可理解性和可修改性。 結構化程序設計語言的特點結構化程序設計語言的特點 注重程序結構的注重程序結構的清晰性清晰性。注重程序的注重程序的可理解性可理解性和和可修改性可修改性。采用采用模塊化程序設計方法模塊化程序設計方法。 計算機導論（計算機導論（20142014）5.1.4 5.1.4 結構化程序設計語言結構化程序設計語言常用結構化程序設計語言常用結構化程序設計語言 pascal語言語言 是在

8、是在algol語言的基礎上發(fā)展起來的。語言的基礎上發(fā)展起來的。 以法國著名科學家帕斯卡的名字命名。以法國著名科學家帕斯卡的名字命名。 嚴格的語法格式與結構化形式嚴格的語法格式與結構化形式。c語言語言 是在是在algol60語言的基礎上發(fā)展起來的。語言的基礎上發(fā)展起來的。 兼具低級語言和高級語言的特點兼具低級語言和高級語言的特點。 是最為流行的程序設計語言之一。是最為流行的程序設計語言之一。 計算機導論（計算機導論（20142014）5.1.5 5.1.5 面向對象程序設計語言面向對象程序設計語言結構化程序設計方法的不足結構化程序設計方法的不足 面向過程的設計方法與人們習慣的思維方式仍然存在一面

9、向過程的設計方法與人們習慣的思維方式仍然存在一定的距離，所以很難自然、準確地反映真實世界，因而定的距離，所以很難自然、準確地反映真實世界，因而用編寫出來的程序，特別是規(guī)模比較大的程序，其質量用編寫出來的程序，特別是規(guī)模比較大的程序，其質量是難以保證的。是難以保證的。強調了要實現(xiàn)功能的操作方法（模塊），而被操作的數(shù)強調了要實現(xiàn)功能的操作方法（模塊），而被操作的數(shù)據(jù)（變量）處于實現(xiàn)功能的從屬地位，即據(jù)（變量）處于實現(xiàn)功能的從屬地位，即程序模塊和數(shù)程序模塊和數(shù)據(jù)結構是松散地耦合在一起據(jù)結構是松散地耦合在一起，當程序復雜度較高時，容，當程序復雜度較高時，容易出錯，而且錯誤難以查找和修改。易出錯，而且錯

10、誤難以查找和修改。 計算機導論（計算機導論（20142014）5.1.5 5.1.5 面向對象程序設計語言面向對象程序設計語言面向對象程序設計語言的特點面向對象程序設計語言的特點 將問題分解為對象。將問題分解為對象。對象將自己的屬性和方法封裝成一個整體對象將自己的屬性和方法封裝成一個整體，供程序設計，供程序設計者使用。者使用。對象之間的相互作用則通過消息傳遞來實現(xiàn)。對象之間的相互作用則通過消息傳遞來實現(xiàn)。使人們對復雜系統(tǒng)的認識過程與程序設計過程盡可能一致。使人們對復雜系統(tǒng)的認識過程與程序設計過程盡可能一致。能夠更好地保證程序的質量和開發(fā)效率能夠更好地保證程序的質量和開發(fā)效率。 計算機導論（計算

11、機導論（20142014）5.1.5 5.1.5 面向對象程序設計語言面向對象程序設計語言常用面向對象程序設計語言常用面向對象程序設計語言 simula 67 發(fā)布于發(fā)布于1967年，是面向對象語言的鼻祖。年，是面向對象語言的鼻祖。c+ 發(fā)布于發(fā)布于1983年，是在年，是在c語言的基礎上發(fā)展起來的。語言的基礎上發(fā)展起來的。 c+c+是得到廣泛應用的一種面向對象語言是得到廣泛應用的一種面向對象語言。 目前常用的版本有目前常用的版本有visual c+, c#, visual c+ .net等。等。java 發(fā)布于發(fā)布于1995年，適合于年，適合于網(wǎng)絡程序設計網(wǎng)絡程序設計。 也是目前得到廣泛應用的

12、一種面向對象程序設計語言。也是目前得到廣泛應用的一種面向對象程序設計語言。 計算機導論（計算機導論（20142014）5.1.6 5.1.6 可視化程序設計語言可視化程序設計語言可視化程序設計語言的特點可視化程序設計語言的特點 以圖形化的編程方式將面向對象技術的特性體現(xiàn)出來。以圖形化的編程方式將面向對象技術的特性體現(xiàn)出來。使開發(fā)軟件這一原本枯燥、難以理解的工作變得相對輕使開發(fā)軟件這一原本枯燥、難以理解的工作變得相對輕松快捷。松快捷。常用可視化程序設計語言常用可視化程序設計語言visual c+ 功能強大，比較適合專業(yè)人員使用。功能強大，比較適合專業(yè)人員使用。visual basic 易于學習和

13、掌握，比較適合非專業(yè)人員和初學者使用。易于學習和掌握，比較適合非專業(yè)人員和初學者使用。 計算機導論（計算機導論（20142014）5.1.7 5.1.7 人工智能程序設計語言人工智能程序設計語言人工智能程序設計語言的特點人工智能程序設計語言的特點 適合于知識表示和邏輯推理。適合于知識表示和邏輯推理。 常用人工智能程序設計語言常用人工智能程序設計語言 lisp lisp是是list processing（表處理）的縮寫。（表處理）的縮寫。 可以解決人工智能中的符號處理問題?？梢越鉀Q人工智能中的符號處理問題。 prolog 是是programming in logic（邏輯程序設計）的縮寫。（邏輯

14、程序設計）的縮寫。 自動實現(xiàn)模式匹配、自動回溯這兩種人工智能中常用的基本操作。自動實現(xiàn)模式匹配、自動回溯這兩種人工智能中常用的基本操作。 計算機導論（計算機導論（20142014）5.2 c5.2 c語言程序設計語言程序設計c c語言的主要特點語言的主要特點簡潔、緊湊、靈活。簡潔、緊湊、靈活。語法限制不太嚴格，使用方便靈活；數(shù)據(jù)結語法限制不太嚴格，使用方便靈活；數(shù)據(jù)結構描述能力及表達式能力強；程序書寫形式自由。構描述能力及表達式能力強；程序書寫形式自由。模塊化、結構化。模塊化、結構化。用語言編寫程序層次清晰，便于按模塊組織用語言編寫程序層次清晰，便于按模塊組織程序，易于實現(xiàn)程序的結構化。程序，

15、易于實現(xiàn)程序的結構化。 功能強大。功能強大。c語言除了能實現(xiàn)一般的高級語言的功能外，還能實語言除了能實現(xiàn)一般的高級語言的功能外，還能實現(xiàn)匯編語言的大部分功能，兼具高級語言和低級語言的特點?，F(xiàn)匯編語言的大部分功能，兼具高級語言和低級語言的特點。可移植性好?？梢浦残院?。c語言程序可以容易地移植到不同型號計算機、不語言程序可以容易地移植到不同型號計算機、不同操作系統(tǒng)環(huán)境下執(zhí)行。同操作系統(tǒng)環(huán)境下執(zhí)行。 計算機導論（計算機導論（20142014）5.2 c5.2 c語言程序設計語言程序設計c c語言的基本要素語言的基本要素c c語言的數(shù)據(jù)類型語言的數(shù)據(jù)類型 c c語言的運算符及表達式語言的運算符及表達式

16、 c c語言語句語言語句 c c語言程序的三種基本結構及實現(xiàn)語言程序的三種基本結構及實現(xiàn) 程序設計風格程序設計風格 算法設計與分析算法設計與分析 計算機導論（計算機導論（20142014）5.2.1 c5.2.1 c語言的基本要素語言的基本要素c c語言的基本詞法語言的基本詞法字符集字符集 英文字母英文字母/數(shù)字數(shù)字/ 特殊字符特殊字符/ 轉義字符。轉義字符。標識符標識符 c語言中各種對象的名字用標識符表示。語言中各種對象的名字用標識符表示。 標識符是由字母、數(shù)字和下劃線三種字符構成的且第標識符是由字母、數(shù)字和下劃線三種字符構成的且第一個字符必須是字母或下劃線的字符序列。一個字符必須是字母或下

17、劃線的字符序列。 標識符分為三類標識符分為三類 關鍵字關鍵字/ 預定義標識符預定義標識符/ 用戶標識符。用戶標識符。 計算機導論（計算機導論（20142014）5.2.1 c5.2.1 c語言的基本要素語言的基本要素常量常量在程序的執(zhí)行過程中其值不能被改變的量。在程序的執(zhí)行過程中其值不能被改變的量。 數(shù)值型常量數(shù)值型常量 整型常量整型常量/ 浮點型常量（實型常量）。浮點型常量（實型常量）。 字符型常量字符型常量 字符常量字符常量/字符串常量。字符串常量。變量變量在程序運行過程中，其值可以被改變的量。在程序運行過程中，其值可以被改變的量。一般要先定義，再使用，變量定義的一般形式為：一般要先定義，

18、再使用，變量定義的一般形式為： 數(shù)據(jù)類型名數(shù)據(jù)類型名 變量名；變量名； 計算機導論（計算機導論（20142014）5.2.2 c5.2.2 c語言的數(shù)據(jù)類型語言的數(shù)據(jù)類型基本數(shù)據(jù)類型基本數(shù)據(jù)類型整型整型 整型變量的定義形式為：整型變量的定義形式為：int int 變量名；變量名；實型實型 實型變量的定義形式為：實型變量的定義形式為：float float 變量名；變量名；字符型字符型 字符型變量的定義格式為：字符型變量的定義格式為：char char 變量名；變量名；構造數(shù)據(jù)類型構造數(shù)據(jù)類型數(shù)組數(shù)組/結構體結構體/共用體共用體/枚舉類型枚舉類型/用戶自定義類型。用戶自定義類型。指針類型指針類型

19、在動態(tài)數(shù)據(jù)結構及其應用中有著不可替代的作用。在動態(tài)數(shù)據(jù)結構及其應用中有著不可替代的作用。 計算機導論（計算機導論（20142014）5.2.3 c5.2.3 c語言的運算符及表達式語言的運算符及表達式算術運算符算術運算符, , *, /, %（求余數(shù)）。（求余數(shù)）。 賦值運算符賦值運算符在在c語言中，語言中，稱為賦值運算符，其使用形式為：稱為賦值運算符，其使用形式為： 變量名變量名 表達式表達式自增、自減運算符自增、自減運算符+是自增運算符是自增運算符，其功能是使變量的值增，其功能是使變量的值增1。- - -是自減運算符是自減運算符，其功能是使變量的值減，其功能是使變量的值減1。關系運算符關系

20、運算符大小判斷大小判斷 （大于）（大于）/（大于等于）（大于等于）/（小于）（小于）/（小于等于）。（小于等于）。相等判斷相等判斷 （等于）（等于）/!（不等于）。（不等于）。 計算機導論（計算機導論（20142014）5.2.4 c5.2.4 c語言語句語言語句控制語句控制語句 用于實現(xiàn)一定的控制功能。用于實現(xiàn)一定的控制功能。 條件語句：用于實現(xiàn)程序執(zhí)行過程中的條件轉移。條件語句：用于實現(xiàn)程序執(zhí)行過程中的條件轉移。 循環(huán)語句：用于實現(xiàn)程序中重復進行某些操作。循環(huán)語句：用于實現(xiàn)程序中重復進行某些操作。 復合語句復合語句由一對花括號由一對花括號 括起來的一組語句。括起來的一組語句。如果要在只執(zhí)行

21、一條語句的地方執(zhí)行多條語句，那么這如果要在只執(zhí)行一條語句的地方執(zhí)行多條語句，那么這多條語句要寫成一條復合語句。多條語句要寫成一條復合語句。 計算機導論（計算機導論（20142014）5.2.5 c5.2.5 c語言程序的三種基本結構語言程序的三種基本結構順序結構順序結構程序的執(zhí)行按照語句出現(xiàn)的先后次序順序進行。程序的執(zhí)行按照語句出現(xiàn)的先后次序順序進行。程序中的每個語句都會被執(zhí)行到。程序中的每個語句都會被執(zhí)行到。程序示例程序示例：通過鍵盤輸入一個三角形的底和高，計算其面積并輸出。通過鍵盤輸入一個三角形的底和高，計算其面積并輸出。 main( ) float width,height,area;

22、/*定義變量定義變量*/ printf(nenter width and height:); /*輸出提示信息輸出提示信息*/ scanf(%f,%f,&width,&height); /*通過鍵盤輸入底和高通過鍵盤輸入底和高*/ area=(width*height)/2.0; /*計算面積計算面積*/ printf(nthe arae is :%f ,area); /*輸出面積的值輸出面積的值*/ 計算機導論（計算機導論（20142014）5.2.5 c5.2.5 c語言程序的三種基本結構語言程序的三種基本結構分支結構分支結構根據(jù)邏輯條件的成立與否，分別選擇執(zhí)行不同的處理。

23、根據(jù)邏輯條件的成立與否，分別選擇執(zhí)行不同的處理。 if語句：語句：ifif（表達式）（表達式） 語句語句 if-else語句：語句：if if （表達式）語句（表達式）語句1 1 else else 語句語句2 2 計算機導論（計算機導論（20142014）5.2.5 c5.2.5 c語言程序的三種基本結構語言程序的三種基本結構分支結構分支結構程序示例程序示例：根據(jù)輸入的學生成績對其進行判斷處理，如果成績根據(jù)輸入的學生成績對其進行判斷處理，如果成績及格，則輸出及格，則輸出passed，否則輸出，否則輸出failed。 main( ) float score; /*定義變量定義變量*/ prin

24、tf(nenter a score :);/*顯示提示信息顯示提示信息*/ scanf(%f,&score);/*通過鍵盤輸入一個成績通過鍵盤輸入一個成績*/ if (score=60.0) printf(npassed );/*大于等于大于等于60輸出輸出passed*/ else printf(nfailed );/*小于小于60輸出輸出failed*/ 計算機導論（計算機導論（20142014）5.2.5 c5.2.5 c語言程序的三種基本結構語言程序的三種基本結構循環(huán)結構循環(huán)結構根據(jù)循環(huán)條件的變化，決定是否繼續(xù)重復執(zhí)行某些語句。根據(jù)循環(huán)條件的變化，決定是否繼續(xù)重復執(zhí)行某些語句。

25、for循環(huán)語句的格式為：循環(huán)語句的格式為： for for （表達式（表達式1 1；表達式；表達式2 2；表達式；表達式3 3） 循環(huán)體語句循環(huán)體語句 計算機導論（計算機導論（20142014）5.2.5 c5.2.5 c語言程序的三種基本結構語言程序的三種基本結構循環(huán)結構循環(huán)結構程序示例程序示例：從鍵盤上輸入從鍵盤上輸入10個整數(shù)，求其累加和并輸出。個整數(shù)，求其累加和并輸出。 main( ) int i, num, sum;/*定義變量定義變量*/ sum=0;/*累加變量清零累加變量清零*/ for (i=1; i=10;i+)/*循環(huán)次數(shù)為循環(huán)次數(shù)為10*/ printf(enter a

26、 data:n );/*顯示提示信息顯示提示信息*/ scanf(%d ,&num); /*通過鍵盤輸入一個整數(shù)通過鍵盤輸入一個整數(shù)*/ sum=sum+num;/*累加求和累加求和*/ printf(“nsum=%d,sum);/*輸出累加結果輸出累加結果*/ 計算機導論（計算機導論（20142014）5.2.6 5.2.6 程序設計風格程序設計風格主要體現(xiàn)在主要體現(xiàn)在5 5個方面?zhèn)€方面標識符的命名要風格統(tǒng)一標識符的命名要風格統(tǒng)一、見名知義。、見名知義。一般一行寫一條語句，一條長語句可以寫在多行上，但一般一行寫一條語句，一條長語句可以寫在多行上，但盡量不要把多條語句寫在一行上。盡量不

27、要把多條語句寫在一行上。采用縮進格式采用縮進格式，即同一層次的語句要對齊，低層次的語，即同一層次的語句要對齊，低層次的語句要縮進若干個字符，增加程序的可讀性。句要縮進若干個字符，增加程序的可讀性。適當書寫注釋信息，有助于閱讀者對程序的理解。適當書寫注釋信息，有助于閱讀者對程序的理解。盡量少用盡量少用goto語句，否則容易導致程序結構混亂。語句，否則容易導致程序結構混亂。 計算機導論（計算機導論（20142014）5.2.7 5.2.7 算法設計與分析算法設計與分析用計算機解決問題的步驟用計算機解決問題的步驟分析問題、設計算法。分析問題、設計算法。選定語言、編寫源程序。選定語言、編寫源程序。對源

28、程序進行編譯生成目標文件。對源程序進行編譯生成目標文件。對目標文件進行連接操作，生成可執(zhí)行的程序。對目標文件進行連接操作，生成可執(zhí)行的程序。調試執(zhí)行可執(zhí)行程序。調試執(zhí)行可執(zhí)行程序。 計算機導論（計算機導論（20142014）5.2.7 5.2.7 算法設計與分析算法設計與分析程序與算法程序與算法算法是指為解決某一問題而采取的方法和步驟算法是指為解決某一問題而采取的方法和步驟。程序是程序設計人員編寫的、計算機能夠理解并執(zhí)行的程序是程序設計人員編寫的、計算機能夠理解并執(zhí)行的命令集合，是命令集合，是算法在計算機中的實現(xiàn)算法在計算機中的實現(xiàn)。算法的特點算法的特點 有窮性有窮性/確定性確定性/有效性有效

29、性/輸入及輸出。輸入及輸出。算法的表示算法的表示 自然語言自然語言/流程圖流程圖/偽碼。偽碼。算法的評價標準算法的評價標準 正確性正確性/時間復雜度時間復雜度/空間復雜度空間復雜度/可理解性?？衫斫庑?。 計算機導論（計算機導論（20142014）5.3 5.3 數(shù)據(jù)結構數(shù)據(jù)結構概念和術語概念和術語線性結構線性結構樹形結構樹形結構圖狀結構圖狀結構 計算機導論（計算機導論（20142014）5.3.1 5.3.1 概念和術語概念和術語數(shù)據(jù)數(shù)據(jù)信息的載體，能夠被計算機識別、存儲和加工處理。信息的載體，能夠被計算機識別、存儲和加工處理。數(shù)據(jù)項數(shù)據(jù)項數(shù)據(jù)不可分割的最小單位。數(shù)據(jù)不可分割的最小單位。數(shù)據(jù)元

30、素數(shù)據(jù)元素數(shù)據(jù)的基本單位，具有完整、確定的實際意義。一般由數(shù)據(jù)的基本單位，具有完整、確定的實際意義。一般由若干數(shù)據(jù)項組成。若干數(shù)據(jù)項組成。數(shù)據(jù)對象數(shù)據(jù)對象具有相同性質的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。具有相同性質的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結構數(shù)據(jù)結構互相之間存在著一種或多種關系的數(shù)據(jù)元素的集合?；ハ嘀g存在著一種或多種關系的數(shù)據(jù)元素的集合。 計算機導論（計算機導論（20142014）5.3.1 5.3.1 概念和術語概念和術語數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構描述的是描述的是數(shù)據(jù)元素之間的邏輯關系數(shù)據(jù)元素之間的邏輯關系。數(shù)據(jù)的物理結構數(shù)據(jù)的物理結構數(shù)據(jù)在計算機中的表示數(shù)據(jù)在計算機中的

31、表示，包括數(shù)據(jù)元素的表示及，包括數(shù)據(jù)元素的表示及數(shù)據(jù)元素間關系的表示。數(shù)據(jù)元素間關系的表示。 計算機導論（計算機導論（20142014）5.3.1 5.3.1 概念和術語概念和術語順序存儲順序存儲邏輯上相鄰的元素存儲在物理位置也相鄰的存儲單元中邏輯上相鄰的元素存儲在物理位置也相鄰的存儲單元中。鏈式存儲鏈式存儲邏輯上相鄰的元素不要求其物理位置相鄰邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏，元素間的邏輯關系通過附設的指針字段來表示。輯關系通過附設的指針字段來表示。 計算機導論（計算機導論（20142014）5.3.2 5.3.2 線性結構線性結構線性結構的特點線性結構的特點數(shù)據(jù)元素之間存在著

32、一對一的關系數(shù)據(jù)元素之間存在著一對一的關系。每個元素有且只有一個前驅（第一個元素除外）。每個元素有且只有一個前驅（第一個元素除外）。每個元素有且只有一個后繼（最后一個元素除外）。每個元素有且只有一個后繼（最后一個元素除外）。應用示例應用示例一維數(shù)組一維數(shù)組二維數(shù)組二維數(shù)組 計算機導論（計算機導論（20142014）5.3.2 5.3.2 線性結構線性結構一維數(shù)組應用示例一維數(shù)組應用示例 main() int i, g, sum, ave; /*定義變量，每一變量代表一內存單元定義變量，每一變量代表一內存單元*/ int a50; /*定義數(shù)組，代表定義數(shù)組，代表50個內存單元個內存單元*/ f

33、or (i=1; i=50; i+) /*循環(huán)執(zhí)行下面大括號中的語句循環(huán)執(zhí)行下面大括號中的語句50次次*/ printf(“nenter a grade:”); /*在屏幕上顯示提示信息在屏幕上顯示提示信息*/ scanf(“%d”,&g); /*通過鍵盤輸入一個學生的成績給變量通過鍵盤輸入一個學生的成績給變量g*/ ai-1=g; /*把把g單元中的成績存入數(shù)組的相應位置單元中的成績存入數(shù)組的相應位置*/ sum=0; /*作為累加器的單元初值清零作為累加器的單元初值清零*/ for (i=1; i1時，除根結點之外的其余結點被分成時，除根結點之外的其余結點被分成m（m1）個互不相）

34、個互不相交的集合交的集合t1，t2，tm，其中每一個集合，其中每一個集合ti（1im）本身）本身又是一棵樹，樹又是一棵樹，樹t1，t2，tm稱為這個根結點的子樹。稱為這個根結點的子樹。 計算機導論（計算機導論（20142014）5.3.3 5.3.3 樹形結構樹形結構二叉樹的定義二叉樹的定義二叉樹是有限個結點的集合，該集合或者為空、或者由二叉樹是有限個結點的集合，該集合或者為空、或者由一個稱為根的結點及兩個不相交的、被分別稱為左子樹一個稱為根的結點及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成。當集合為空時，稱該二叉樹為和右子樹的二叉樹組成。當集合為空時，稱該二叉樹為空二叉樹?？斩鏄?。

35、 滿二叉樹滿二叉樹：在二叉樹中，如果所有分支結點都存在左子樹和右子：在二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子結點都在同一層上，這樣的一棵二叉樹稱作滿樹，并且所有葉子結點都在同一層上，這樣的一棵二叉樹稱作滿二叉樹。二叉樹。 完全二叉樹完全二叉樹：一棵深度為：一棵深度為k的有的有n個結點的二叉樹，對樹中的結點個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編號，如果編號為按從上至下、從左到右的順序進行編號，如果編號為i（1in）的結點與滿二叉樹中編號為的結點與滿二叉樹中編號為i的結點在二叉樹中的位置相同，則的結點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。這棵

36、二叉樹稱為完全二叉樹。 計算機導論（計算機導論（20142014）5.3.3 5.3.3 樹形結構樹形結構二叉樹示例二叉樹示例滿二叉樹滿二叉樹完全二叉樹完全二叉樹非完全二叉樹非完全二叉樹 計算機導論（計算機導論（20142014）5.3.3 5.3.3 樹形結構樹形結構圖5.7 滿二叉樹8dhiejkflgbca2345679101112m13op1415圖5.8 完全二叉樹18dhiejkflgbca2345679101112二叉樹的存儲二叉樹的存儲 順序存儲結構順序存儲結構 用一組連續(xù)的存儲單元（數(shù)組）存放二叉樹中的結點用一組連續(xù)的存儲單元（數(shù)組）存放二叉樹中的結點。一般是按。一般是按照二

37、叉樹結點從上至下、從左到右的順序存儲。照二叉樹結點從上至下、從左到右的順序存儲。 完全二叉樹和滿二叉樹采用順序存儲比較合適，樹中結點的序號完全二叉樹和滿二叉樹采用順序存儲比較合適，樹中結點的序號可以唯一地反映出結點之間的邏輯關系，這樣既能夠最大可能地可以唯一地反映出結點之間的邏輯關系，這樣既能夠最大可能地節(jié)省存儲空間，又可以利用數(shù)組元素的下標值確定結點在二叉樹節(jié)省存儲空間，又可以利用數(shù)組元素的下標值確定結點在二叉樹中的位置以及結點之間的關系。中的位置以及結點之間的關系。 計算機導論（計算機導論（20142014）5.3.3 5.3.3 樹形結構樹形結構圖5.7 滿二叉樹8dhiejkflgbc

38、a2345679101112m13op1415圖5.8 完全二叉樹18dhiejkflgbca2345679101112二叉樹的存儲二叉樹的存儲 鏈式存儲結構鏈式存儲結構 用鏈表來表示一棵二叉樹。鏈表中每個結點由三個域組成，除了用鏈表來表示一棵二叉樹。鏈表中每個結點由三個域組成，除了數(shù)據(jù)域外，還有兩個指針域，分別用來給出該結點的左子結點和數(shù)據(jù)域外，還有兩個指針域，分別用來給出該結點的左子結點和右子結點所在的鏈結點的存儲地址。右子結點所在的鏈結點的存儲地址。非完全二叉樹的鏈式存儲非完全二叉樹的鏈式存儲 計算機導論（計算機導論（20142014）5.3.3 5.3.3 樹形結構樹形結構樹的應用樹的

39、應用用于分類的用于分類的決策樹決策樹用于各種比賽的用于各種比賽的博弈樹博弈樹 計算機導論（計算機導論（20142014）5.3.4 5.3.4 圖狀結構圖狀結構圖狀結構的特點圖狀結構的特點數(shù)據(jù)元素之間存在著多對多的關系數(shù)據(jù)元素之間存在著多對多的關系。圖的定義圖的定義 g（v，e）; 其中其中vvi| vidataobject； e( vi,vj)| vi, vj v p(vi, vj)。g表示一個圖，表示一個圖，v是圖是圖g中頂點的集合，頂點集合構成數(shù)據(jù)對象中頂點的集合，頂點集合構成數(shù)據(jù)對象（dataobject），頂點就代表數(shù)據(jù)元素，），頂點就代表數(shù)據(jù)元素，e是圖是圖g中邊的集合，集合中邊的

40、集合，集合e中中p(vi,vj)表示頂點表示頂點vi和頂點和頂點vj之間有一條直接連線，即偶對之間有一條直接連線，即偶對(vi,vj)表示表示圖中的一條邊。圖中的一條邊。 計算機導論（計算機導論（20142014）5.3.4 5.3.4 圖狀結構圖狀結構圖的示例圖的示例圖的存儲圖的存儲鄰接矩陣鄰接矩陣 用矩陣表示圖中各頂點之間的鄰接關系，有邊相連對應的矩陣元用矩陣表示圖中各頂點之間的鄰接關系，有邊相連對應的矩陣元素值為素值為1，否則為，否則為0。 計算機導論（計算機導論（20142014）5.3.4 5.3.4 圖狀結構圖狀結構圖的存儲圖的存儲鄰接表鄰接表 一種順序存儲與鏈式存儲結合的存儲方法

41、。對于圖一種順序存儲與鏈式存儲結合的存儲方法。對于圖g中的每個頂中的每個頂點點vi，將所有鄰接于，將所有鄰接于vi的頂點的頂點vj鏈成一個單鏈表，這個單鏈表就稱鏈成一個單鏈表，這個單鏈表就稱為頂點為頂點vi的鄰接表，再將所有頂點的鄰接表表頭放到數(shù)組中，就的鄰接表，再將所有頂點的鄰接表表頭放到數(shù)組中，就構成了圖的鄰接表。構成了圖的鄰接表。 計算機導論（計算機導論（20142014）5.3.4 5.3.4 圖狀結構圖狀結構圖的應用圖的應用求最短路徑求最短路徑網(wǎng)絡性能分析網(wǎng)絡性能分析社會網(wǎng)絡分析社會網(wǎng)絡分析 計算機導論（計算機導論（20142014）5.4 5.4 編譯原理編譯原理編譯程序概述編譯程

42、序概述詞法分析詞法分析語法分析語法分析中間代碼生成中間代碼生成中間代碼優(yōu)化中間代碼優(yōu)化目標代碼生成目標代碼生成編譯程序的開發(fā)編譯程序的開發(fā) 計算機導論（計算機導論（20142014）5.4.1 5.4.1 編譯程序概述編譯程序概述高級語言的特點高級語言的特點簡單易學，易于編寫和修改程序。簡單易學，易于編寫和修改程序。編寫出的源程序不能直接執(zhí)行。編寫出的源程序不能直接執(zhí)行。編譯程序編譯程序把用高級語言編寫的源程序翻譯成等價的機器語言程序把用高級語言編寫的源程序翻譯成等價的機器語言程序的翻譯程序的翻譯程序。學習編譯知識的作用學習編譯知識的作用深入理解高級語言程序設計。深入理解高級語言程序設計。有助

43、于提高程序設計能力和培養(yǎng)程序設計思維。有助于提高程序設計能力和培養(yǎng)程序設計思維。 計算機導論（計算機導論（20142014）5.4.2 5.4.2 詞法分析詞法分析詞法分析的主要任務詞法分析的主要任務從源程序中識別出單詞從源程序中識別出單詞。發(fā)現(xiàn)詞法錯誤并指出錯誤位置。發(fā)現(xiàn)詞法錯誤并指出錯誤位置。以某種機內符的形式表示單詞。以某種機內符的形式表示單詞。單詞種類單詞種類基本字：也稱關鍵字，如基本字：也稱關鍵字，如c語言中的語言中的for、do、while等；等；標識符：用來表示各種名字的符號串，如變量名、函數(shù)名等；標識符：用來表示各種名字的符號串，如變量名、函數(shù)名等；常數(shù)：各種類型的常數(shù)，如整數(shù)

44、、實數(shù)、字符串等；常數(shù)：各種類型的常數(shù)，如整數(shù)、實數(shù)、字符串等；運算符：各種算術運算、關系運算符，如運算符：各種算術運算、關系運算符，如+、-、=等；等；界限符：如逗號（，）、分號（；）等。界限符：如逗號（，）、分號（；）等。 計算機導論（計算機導論（20142014）5.4.3 5.4.3 語法分析語法分析語法分析的主要任務語法分析的主要任務確認作為詞法分析結果的確認作為詞法分析結果的單詞序列是否為給定語言的一單詞序列是否為給定語言的一個正確程序個正確程序。給定語言用文法表示，如果給定的單詞串能夠識別成該給定語言用文法表示，如果給定的單詞串能夠識別成該文法的句子，則認為程序是正確的，否則認為

45、程序是錯文法的句子，則認為程序是正確的，否則認為程序是錯誤的。誤的。 自頂向下分析方法自頂向下分析方法/ /自底向上分析方法。自底向上分析方法。調用語義子程序進行語義處理。調用語義子程序進行語義處理。 審查每個語法結構的靜態(tài)語義，即確認語法結構合法的程序是否審查每個語法結構的靜態(tài)語義，即確認語法結構合法的程序是否真正有意義。真正有意義。 計算機導論（計算機導論（20142014）5.4.4 5.4.4 中間代碼生成中間代碼生成中間代碼生成的主要任務中間代碼生成的主要任務以某種以某種便于計算機處理的形式表示程序便于計算機處理的形式表示程序。引入中間代碼的優(yōu)點引入中間代碼的優(yōu)點使編譯程序結構在邏輯

46、上更為簡單明確。使編譯程序結構在邏輯上更為簡單明確?？梢詫⑴c機器相關的某些實現(xiàn)細節(jié)置于代碼生成階段仔可以將與機器相關的某些實現(xiàn)細節(jié)置于代碼生成階段仔細處理。細處理。使得計算和代碼優(yōu)化比較容易實現(xiàn)。使得計算和代碼優(yōu)化比較容易實現(xiàn)。常用的中間代碼形式常用的中間代碼形式逆波蘭式逆波蘭式/ /三元式三元式/ /四元式。四元式。 計算機導論（計算機導論（20142014）5.4.4 5.4.4 中間代碼生成中間代碼生成逆波蘭式計算的優(yōu)點逆波蘭式計算的優(yōu)點a+bc的逆波蘭式形式為的逆波蘭式形式為abc+。 對于逆波蘭式對于逆波蘭式abc+，計算機先掃描到運算對象，計算機先掃描到運算對象a、b和和c，然后，

47、然后掃描到運算符，先計算掃描到運算符，先計算bc（假定結果為（假定結果為t），繼續(xù)掃描到運），繼續(xù)掃描到運算符算符+，再計算，再計算a+t，從而完成，從而完成a+bc的計算。的計算。無論表達式多復雜，無論表達式多復雜，只一遍掃描就能完成表達式的計算。只一遍掃描就能完成表達式的計算。 對于一般表達式對于一般表達式a+bc，計算機先掃描到運算對象，計算機先掃描到運算對象a，然后掃描，然后掃描到運算符到運算符+和運算對象和運算對象b，由于不知道后面的運算符是什么，不能，由于不知道后面的運算符是什么，不能決定是否先完成決定是否先完成+的運算，繼續(xù)掃描到運算符和運算對象的運算，繼續(xù)掃描到運算符和運算對象c，知，知道的優(yōu)先級高，先計算道的優(yōu)先級高，先計算bc（假定結果為（假定結果為t），再往回掃描計），再往回掃描計算算a+t。對于比較復雜的表達式，可能需要多次來回掃描表達式，對于比較復雜的表達式，可能需要多次來回掃描