程序設(shè)計(jì)知識(shí)課件

第5章程序設(shè)計(jì)知識(shí)5.1程序設(shè)計(jì)語(yǔ)言5.2C語(yǔ)言程序設(shè)計(jì)5.3數(shù)據(jù)結(jié)構(gòu)5.4編譯原理第5章程序設(shè)計(jì)知識(shí)5.1程序設(shè)計(jì)語(yǔ)言5.1程序設(shè)計(jì)語(yǔ)言機(jī)器語(yǔ)言匯編語(yǔ)言高級(jí)語(yǔ)言結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言可視化程序設(shè)計(jì)語(yǔ)言人工智能程序設(shè)計(jì)語(yǔ)言學(xué)習(xí)語(yǔ)言是設(shè)計(jì)程序的基礎(chǔ)5.1程序設(shè)計(jì)語(yǔ)言機(jī)器語(yǔ)言學(xué)習(xí)語(yǔ)言是設(shè)計(jì)程序的基礎(chǔ)5.1.1機(jī)器語(yǔ)言機(jī)器語(yǔ)言的特點(diǎn)

由二進(jìn)制編碼指令構(gòu)成的語(yǔ)言。是一種依附于機(jī)器硬件的語(yǔ)言。機(jī)器語(yǔ)言程序可以直接執(zhí)行。機(jī)器語(yǔ)言程序片段

0001

0101

01101100

//把地址為01101100的內(nèi)存單元中的數(shù)裝入0101號(hào)寄存器

0001

0110

01101101

//把地址為01101101的內(nèi)存單元中的數(shù)裝入0110號(hào)寄存器

0101

0000

01010110

//把01101100和01101101中的數(shù)相加,結(jié)果存入0000號(hào)寄存器

0011

0000

01101110

//把0000號(hào)寄存器中的數(shù)存入地址為01101110的內(nèi)存單元中5.1.1機(jī)器語(yǔ)言機(jī)器語(yǔ)言的特點(diǎn)5.1.2匯編語(yǔ)言匯編語(yǔ)言的特點(diǎn)

由助記符指令構(gòu)成的語(yǔ)言。也是一種依附于機(jī)器硬件的語(yǔ)言。匯編語(yǔ)言源程序需要匯編后才能執(zhí)行。匯編語(yǔ)言程序片段

MOVR5,X//把內(nèi)存單元X中的數(shù)裝入R5寄存器

ADDR5,Y//把R5中的數(shù)與Y單元中的數(shù)相加，結(jié)果存入R5

MOVZ,R5//把R5中的數(shù)存入Z單元中

5.1.2匯編語(yǔ)言匯編語(yǔ)言的特點(diǎn)5.1.3高級(jí)語(yǔ)言高級(jí)語(yǔ)言的特點(diǎn)

由自然語(yǔ)言和數(shù)學(xué)公式表示的語(yǔ)言。是一種獨(dú)立于機(jī)器硬件的語(yǔ)言。高級(jí)語(yǔ)言程序需要編譯后才能執(zhí)行。高級(jí)語(yǔ)言程序片段

Z=X+Y

//把內(nèi)存單元X中的數(shù)與Y中的數(shù)相加，結(jié)果存入Z單元

5.1.3高級(jí)語(yǔ)言高級(jí)語(yǔ)言的特點(diǎn)5.1.3高級(jí)語(yǔ)言常用高級(jí)語(yǔ)言

FORTRAN語(yǔ)言FORTRAN是FORmulaTRANslator（公式翻譯器）的縮寫(xiě)。主要用于復(fù)雜的科學(xué)計(jì)算領(lǐng)域。ALGOL語(yǔ)言ALGOL是ALGOrithmLanguage（算法語(yǔ)言）的縮寫(xiě)。主要用于數(shù)學(xué)與科學(xué)計(jì)算。5.1.3高級(jí)語(yǔ)言常用高級(jí)語(yǔ)言5.1.3高級(jí)語(yǔ)言常用高級(jí)語(yǔ)言

COBOL語(yǔ)言

COBOL是COmmonBusiness-OrientedLanguage（面向商業(yè)的通用語(yǔ)言）的縮寫(xiě)。主要用于企業(yè)管理和事務(wù)處理。BASIC語(yǔ)言

BASIC是Beginner’sAll-purposeSymbolicInstructionCode（初學(xué)者通用符號(hào)指令碼）的縮寫(xiě)。主要用于初學(xué)者和較小規(guī)模的程序開(kāi)發(fā)。5.1.3高級(jí)語(yǔ)言常用高級(jí)語(yǔ)言5.1.4結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言早期程序設(shè)計(jì)方法的不足注重功能的實(shí)現(xiàn)/注重內(nèi)存的節(jié)省/注重執(zhí)行效率的提高。不注重程序結(jié)構(gòu)的清晰性。不注重程序的可理解性和可修改性。結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言的特點(diǎn)

注重程序結(jié)構(gòu)的清晰性。注重程序的可理解性和可修改性。采用模塊化程序設(shè)計(jì)方法。5.1.4結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言早期程序設(shè)計(jì)方法的不足5.1.4結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言常用結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言

PASCAL語(yǔ)言

是在ALGOL語(yǔ)言的基礎(chǔ)上發(fā)展起來(lái)的。以法國(guó)著名科學(xué)家帕斯卡的名字命名。嚴(yán)格的語(yǔ)法格式與結(jié)構(gòu)化形式。C語(yǔ)言

是在ALGOL60語(yǔ)言的基礎(chǔ)上發(fā)展起來(lái)的。兼具低級(jí)語(yǔ)言和高級(jí)語(yǔ)言的特點(diǎn)。是最為流行的程序設(shè)計(jì)語(yǔ)言之一。5.1.4結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言常用結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言5.1.5面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言結(jié)構(gòu)化程序設(shè)計(jì)方法的不足

面向過(guò)程的設(shè)計(jì)方法與人們習(xí)慣的思維方式仍然存在一定的距離，所以很難自然、準(zhǔn)確地反映真實(shí)世界，因而用編寫(xiě)出來(lái)的程序，特別是規(guī)模比較大的程序，其質(zhì)量是難以保證的。強(qiáng)調(diào)了要實(shí)現(xiàn)功能的操作方法（模塊），而被操作的數(shù)據(jù)（變量）處于實(shí)現(xiàn)功能的從屬地位，即程序模塊和數(shù)據(jù)結(jié)構(gòu)是松散地耦合在一起，當(dāng)程序復(fù)雜度較高時(shí)，容易出錯(cuò)，而且錯(cuò)誤難以查找和修改。5.1.5面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言結(jié)構(gòu)化程序設(shè)計(jì)方法的不足5.1.5面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言的特點(diǎn)

將問(wèn)題分解為對(duì)象。對(duì)象將自己的屬性和方法封裝成一個(gè)整體，供程序設(shè)計(jì)者使用。對(duì)象之間的相互作用則通過(guò)消息傳遞來(lái)實(shí)現(xiàn)。使人們對(duì)復(fù)雜系統(tǒng)的認(rèn)識(shí)過(guò)程與程序設(shè)計(jì)過(guò)程盡可能一致。能夠更好地保證程序的質(zhì)量和開(kāi)發(fā)效率。5.1.5面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言的特點(diǎn)5.1.5面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言常用面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言

Simula67

發(fā)布于1967年，是面向?qū)ο笳Z(yǔ)言的鼻祖。C++

發(fā)布于1983年，是在C語(yǔ)言的基礎(chǔ)上發(fā)展起來(lái)的。C++是得到廣泛應(yīng)用的一種面向?qū)ο笳Z(yǔ)言。目前常用的版本有VisualC++,C#,VisualC++.Net等。Java發(fā)布于1995年，適合于網(wǎng)絡(luò)程序設(shè)計(jì)。也是目前得到廣泛應(yīng)用的一種面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言。5.1.5面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言常用面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言5.1.6可視化程序設(shè)計(jì)語(yǔ)言可視化程序設(shè)計(jì)語(yǔ)言的特點(diǎn)

以圖形化的編程方式將面向?qū)ο蠹夹g(shù)的特性體現(xiàn)出來(lái)。使開(kāi)發(fā)軟件這一原本枯燥、難以理解的工作變得相對(duì)輕松快捷。常用可視化程序設(shè)計(jì)語(yǔ)言VisualC++功能強(qiáng)大，比較適合專(zhuān)業(yè)人員使用。VisualBasic易于學(xué)習(xí)和掌握，比較適合非專(zhuān)業(yè)人員和初學(xué)者使用。5.1.6可視化程序設(shè)計(jì)語(yǔ)言可視化程序設(shè)計(jì)語(yǔ)言的特點(diǎn)5.1.7人工智能程序設(shè)計(jì)語(yǔ)言人工智能程序設(shè)計(jì)語(yǔ)言的特點(diǎn)

適合于知識(shí)表示和邏輯推理。

常用人工智能程序設(shè)計(jì)語(yǔ)言

LISP

LISP是LIStProcessing（表處理）的縮寫(xiě)。可以解決人工智能中的符號(hào)處理問(wèn)題。

PROLOG

是PROgramminginLOGic（邏輯程序設(shè)計(jì)）的縮寫(xiě)。自動(dòng)實(shí)現(xiàn)模式匹配、自動(dòng)回溯這兩種人工智能中常用的基本操作。5.1.7人工智能程序設(shè)計(jì)語(yǔ)言人工智能程序設(shè)計(jì)語(yǔ)言的特點(diǎn)5.2C語(yǔ)言程序設(shè)計(jì)C語(yǔ)言的主要特點(diǎn)簡(jiǎn)潔、緊湊、靈活。語(yǔ)法限制不太嚴(yán)格，使用方便靈活；數(shù)據(jù)結(jié)構(gòu)描述能力及表達(dá)式能力強(qiáng)；程序書(shū)寫(xiě)形式自由。模塊化、結(jié)構(gòu)化。用Ｃ語(yǔ)言編寫(xiě)程序?qū)哟吻逦?，便于按模塊組織程序，易于實(shí)現(xiàn)程序的結(jié)構(gòu)化。

功能強(qiáng)大。C語(yǔ)言除了能實(shí)現(xiàn)一般的高級(jí)語(yǔ)言的功能外，還能實(shí)現(xiàn)匯編語(yǔ)言的大部分功能，兼具高級(jí)語(yǔ)言和低級(jí)語(yǔ)言的特點(diǎn)?？梢浦残院谩語(yǔ)言程序可以容易地移植到不同型號(hào)計(jì)算機(jī)、不同操作系統(tǒng)環(huán)境下執(zhí)行。5.2C語(yǔ)言程序設(shè)計(jì)C語(yǔ)言的主要特點(diǎn)5.2C語(yǔ)言程序設(shè)計(jì)C語(yǔ)言的基本要素C語(yǔ)言的數(shù)據(jù)類(lèi)型C語(yǔ)言的運(yùn)算符及表達(dá)式C語(yǔ)言語(yǔ)句C語(yǔ)言程序的三種基本結(jié)構(gòu)及實(shí)現(xiàn)程序設(shè)計(jì)風(fēng)格算法設(shè)計(jì)與分析5.2C語(yǔ)言程序設(shè)計(jì)C語(yǔ)言的基本要素5.2.1C語(yǔ)言的基本要素C語(yǔ)言的基本詞法字符集英文字母/數(shù)字/特殊字符/轉(zhuǎn)義字符。標(biāo)識(shí)符C語(yǔ)言中各種對(duì)象的名字用標(biāo)識(shí)符表示。標(biāo)識(shí)符是由字母、數(shù)字和下劃線三種字符構(gòu)成的且第一個(gè)字符必須是字母或下劃線的字符序列。標(biāo)識(shí)符分為三類(lèi)關(guān)鍵字/預(yù)定義標(biāo)識(shí)符/用戶(hù)標(biāo)識(shí)符。5.2.1C語(yǔ)言的基本要素C語(yǔ)言的基本詞法5.2.1C語(yǔ)言的基本要素常量在程序的執(zhí)行過(guò)程中其值不能被改變的量。數(shù)值型常量整型常量/浮點(diǎn)型常量（實(shí)型常量）。字符型常量字符常量/字符串常量。變量在程序運(yùn)行過(guò)程中，其值可以被改變的量。一般要先定義，再使用，變量定義的一般形式為：

數(shù)據(jù)類(lèi)型名變量名；5.2.1C語(yǔ)言的基本要素常量5.2.2C語(yǔ)言的數(shù)據(jù)類(lèi)型基本數(shù)據(jù)類(lèi)型整型整型變量的定義形式為：int變量名；實(shí)型實(shí)型變量的定義形式為：float變量名；字符型字符型變量的定義格式為：char變量名；構(gòu)造數(shù)據(jù)類(lèi)型數(shù)組/結(jié)構(gòu)體/共用體/枚舉類(lèi)型/用戶(hù)自定義類(lèi)型。指針類(lèi)型在動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用中有著不可替代的作用。5.2.2C語(yǔ)言的數(shù)據(jù)類(lèi)型基本數(shù)據(jù)類(lèi)型5.2.3C語(yǔ)言的運(yùn)算符及表達(dá)式算術(shù)運(yùn)算符＋,－,*,/,%（求余數(shù)）。

賦值運(yùn)算符在C語(yǔ)言中，＝稱(chēng)為賦值運(yùn)算符，其使用形式為：

變量名＝表達(dá)式自增、自減運(yùn)算符++是自增運(yùn)算符，其功能是使變量的值增1。--是自減運(yùn)算符，其功能是使變量的值減1。關(guān)系運(yùn)算符大小判斷＞（大于）/＞＝（大于等于）/＜（小于）/＜＝（小于等于）。相等判斷＝＝（等于）/!＝（不等于）。

5.2.3C語(yǔ)言的運(yùn)算符及表達(dá)式算術(shù)運(yùn)算符5.2.4C語(yǔ)言語(yǔ)句控制語(yǔ)句

用于實(shí)現(xiàn)一定的控制功能。條件語(yǔ)句：用于實(shí)現(xiàn)程序執(zhí)行過(guò)程中的條件轉(zhuǎn)移。循環(huán)語(yǔ)句：用于實(shí)現(xiàn)程序中重復(fù)進(jìn)行某些操作。 復(fù)合語(yǔ)句由一對(duì)花括號(hào){}括起來(lái)的一組語(yǔ)句。如果要在只執(zhí)行一條語(yǔ)句的地方執(zhí)行多條語(yǔ)句，那么這多條語(yǔ)句要寫(xiě)成一條復(fù)合語(yǔ)句。5.2.4C語(yǔ)言語(yǔ)句控制語(yǔ)句5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)順序結(jié)構(gòu)程序的執(zhí)行按照語(yǔ)句出現(xiàn)的先后次序順序進(jìn)行。程序中的每個(gè)語(yǔ)句都會(huì)被執(zhí)行到。程序示例：通過(guò)鍵盤(pán)輸入一個(gè)三角形的底和高，計(jì)算其面積并輸出。

main(){floatwidth,height,area; /*定義變量*/printf("\nEnterwidthandheight:");/*輸出提示信息*/scanf("%f,%f",&width,&height); /*通過(guò)鍵盤(pán)輸入底和高*/area=(width*height)/2.0; /*計(jì)算面積*/printf("\nThearaeis:%f",area); /*輸出面積的值*/}5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)順序結(jié)構(gòu)5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)分支結(jié)構(gòu)根據(jù)邏輯條件的成立與否，分別選擇執(zhí)行不同的處理。if語(yǔ)句：if（表達(dá)式）語(yǔ)句if-else語(yǔ)句：if（表達(dá)式）語(yǔ)句1else語(yǔ)句25.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)分支結(jié)構(gòu)5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)分支結(jié)構(gòu)程序示例：根據(jù)輸入的學(xué)生成績(jī)對(duì)其進(jìn)行判斷處理，如果成績(jī)及格，則輸出Passed，否則輸出Failed。

main(){floatscore; /*定義變量*/printf("\nEnterascore:"); /*顯示提示信息*/scanf("%f",&score); /*通過(guò)鍵盤(pán)輸入一個(gè)成績(jī)*/if(score>=60.0)printf("\nPassed"); /*大于等于60輸出Passed*/else printf("\nFailed"); /*小于60輸出Failed*/}5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)分支結(jié)構(gòu)5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)循環(huán)結(jié)構(gòu)根據(jù)循環(huán)條件的變化，決定是否繼續(xù)重復(fù)執(zhí)行某些語(yǔ)句。for循環(huán)語(yǔ)句的格式為：

for（表達(dá)式1；表達(dá)式2；表達(dá)式3）循環(huán)體語(yǔ)句

5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)循環(huán)結(jié)構(gòu)5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)循環(huán)結(jié)構(gòu)程序示例：從鍵盤(pán)上輸入10個(gè)整數(shù)，求其累加和并輸出。

main(){inti,num,sum; /*定義變量*/sum=0; /*累加變量清零*/for(i=1;i<=10;i++) /*循環(huán)次數(shù)為10*/

{printf("Enteradata:\n"); /*顯示提示信息*/ scanf("%d",&num); /*通過(guò)鍵盤(pán)輸入一個(gè)整數(shù)*/ sum=sum+num; /*累加求和*/

}printf(“\nsum=%d,sum); /*輸出累加結(jié)果*/}

5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)循環(huán)結(jié)構(gòu)5.2.6程序設(shè)計(jì)風(fēng)格主要體現(xiàn)在5個(gè)方面標(biāo)識(shí)符的命名要風(fēng)格統(tǒng)一、見(jiàn)名知義。一般一行寫(xiě)一條語(yǔ)句，一條長(zhǎng)語(yǔ)句可以寫(xiě)在多行上，但盡量不要把多條語(yǔ)句寫(xiě)在一行上。采用縮進(jìn)格式，即同一層次的語(yǔ)句要對(duì)齊，低層次的語(yǔ)句要縮進(jìn)若干個(gè)字符，增加程序的可讀性。適當(dāng)書(shū)寫(xiě)注釋信息，有助于閱讀者對(duì)程序的理解。盡量少用goto語(yǔ)句，否則容易導(dǎo)致程序結(jié)構(gòu)混亂。5.2.6程序設(shè)計(jì)風(fēng)格主要體現(xiàn)在5個(gè)方面5.2.7算法設(shè)計(jì)與分析用計(jì)算機(jī)解決問(wèn)題的步驟分析問(wèn)題、設(shè)計(jì)算法。選定語(yǔ)言、編寫(xiě)源程序。對(duì)源程序進(jìn)行編譯生成目標(biāo)文件。對(duì)目標(biāo)文件進(jìn)行連接操作，生成可執(zhí)行的程序。調(diào)試執(zhí)行可執(zhí)行程序。5.2.7算法設(shè)計(jì)與分析用計(jì)算機(jī)解決問(wèn)題的步驟5.2.7算法設(shè)計(jì)與分析程序與算法算法是指為解決某一問(wèn)題而采取的方法和步驟。程序是程序設(shè)計(jì)人員編寫(xiě)的、計(jì)算機(jī)能夠理解并執(zhí)行的命令集合，是算法在計(jì)算機(jī)中的實(shí)現(xiàn)。算法的特點(diǎn)有窮性/確定性/有效性/輸入及輸出。算法的表示自然語(yǔ)言/流程圖/偽碼。算法的評(píng)價(jià)標(biāo)準(zhǔn)正確性/時(shí)間復(fù)雜度/空間復(fù)雜度/可理解性。5.2.7算法設(shè)計(jì)與分析程序與算法5.3數(shù)據(jù)結(jié)構(gòu)概念和術(shù)語(yǔ)線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖狀結(jié)構(gòu)5.3數(shù)據(jù)結(jié)構(gòu)概念和術(shù)語(yǔ)5.3.1概念和術(shù)語(yǔ)數(shù)據(jù)信息的載體，能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。數(shù)據(jù)項(xiàng)數(shù)據(jù)不可分割的最小單位。數(shù)據(jù)元素?cái)?shù)據(jù)的基本單位，具有完整、確定的實(shí)際意義。一般由若干數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)對(duì)象具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。5.3.1概念和術(shù)語(yǔ)數(shù)據(jù)5.3.1概念和術(shù)語(yǔ)數(shù)據(jù)的邏輯結(jié)構(gòu)描述的是數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)在計(jì)算機(jī)中的表示，包括數(shù)據(jù)元素的表示及數(shù)據(jù)元素間關(guān)系的表示。5.3.1概念和術(shù)語(yǔ)數(shù)據(jù)的邏輯結(jié)構(gòu)5.3.1概念和術(shù)語(yǔ)順序存儲(chǔ)邏輯上相鄰的元素存儲(chǔ)在物理位置也相鄰的存儲(chǔ)單元中。鏈?zhǔn)酱鎯?chǔ)邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過(guò)附設(shè)的指針字段來(lái)表示。5.3.1概念和術(shù)語(yǔ)順序存儲(chǔ)5.3.2線性結(jié)構(gòu)線性結(jié)構(gòu)的特點(diǎn)數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系。每個(gè)元素有且只有一個(gè)前驅(qū)（第一個(gè)元素除外）。每個(gè)元素有且只有一個(gè)后繼（最后一個(gè)元素除外）。應(yīng)用示例一維數(shù)組二維數(shù)組5.3.2線性結(jié)構(gòu)線性結(jié)構(gòu)的特點(diǎn)5.3.2線性結(jié)構(gòu)一維數(shù)組應(yīng)用示例

main(){inti,g,sum,ave;/*定義變量，每一變量代表一內(nèi)存單元*/inta[50];/*定義數(shù)組，代表50個(gè)內(nèi)存單元*/for(i=1;i<=50;i++)/*循環(huán)執(zhí)行下面大括號(hào)中的語(yǔ)句50次*/{printf(“\nEnteragrade:”);/*在屏幕上顯示提示信息*/scanf(“%d”,&g); /*通過(guò)鍵盤(pán)輸入一個(gè)學(xué)生的成績(jī)給變量g*/a[i-1]=g; /*把g單元中的成績(jī)存入數(shù)組的相應(yīng)位置*/}sum=0; /*作為累加器的單元初值清零*/for(i=1;i<=50;i++) /*循環(huán)執(zhí)行下面的累加語(yǔ)句40次*/sum=sum+a[i-1]; /*把第i個(gè)學(xué)生的成績(jī)加到累加器*/ave=sum/50; /*求平均成績(jī)*/printf(“\nave=%d”,ave); /*輸出平均成績(jī)*/}5.3.2線性結(jié)構(gòu)一維數(shù)組應(yīng)用示例5.3.3樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu)的特點(diǎn)數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。樹(shù)的定義樹(shù)是n（≥0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)，稱(chēng)為空樹(shù)。在一棵非空樹(shù)T中：

有一個(gè)特定的結(jié)點(diǎn)稱(chēng)為樹(shù)的根結(jié)點(diǎn)；當(dāng)n>1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m（m≥1）個(gè)互不相交的集合T1，T2，…，Tm，其中每一個(gè)集合Ti（1≤i≤m）本身又是一棵樹(shù)，樹(shù)T1，T2，…，Tm稱(chēng)為這個(gè)根結(jié)點(diǎn)的子樹(shù)。5.3.3樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu)的特點(diǎn)5.3.3樹(shù)形結(jié)構(gòu)二叉樹(shù)的定義二叉樹(shù)是有限個(gè)結(jié)點(diǎn)的集合，該集合或者為空、或者由一個(gè)稱(chēng)為根的結(jié)點(diǎn)及兩個(gè)不相交的、被分別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。當(dāng)集合為空時(shí)，稱(chēng)該二叉樹(shù)為空二叉樹(shù)。滿二叉樹(shù)：在二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的一棵二叉樹(shù)稱(chēng)作滿二叉樹(shù)。完全二叉樹(shù)：一棵深度為k的有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，對(duì)樹(shù)中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，如果編號(hào)為i（1≤i≤n）的結(jié)點(diǎn)與滿二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中的位置相同，則這棵二叉樹(shù)稱(chēng)為完全二叉樹(shù)。

5.3.3樹(shù)形結(jié)構(gòu)二叉樹(shù)的定義5.3.3樹(shù)形結(jié)構(gòu)二叉樹(shù)示例滿二叉樹(shù)完全二叉樹(shù)非完全二叉樹(shù)5.3.3樹(shù)形結(jié)構(gòu)二叉樹(shù)示例滿二叉樹(shù)完全二叉樹(shù)非完全二叉樹(shù)5.3.3樹(shù)形結(jié)構(gòu)圖5.7滿二叉樹(shù)8DHIEJKFLGBCA2345679101112M13OP1415圖5.8完全二叉樹(shù)18DHIEJKFLGBCA2345679101112二叉樹(shù)的存儲(chǔ)

順序存儲(chǔ)結(jié)構(gòu)用一組連續(xù)的存儲(chǔ)單元（數(shù)組）存放二叉樹(shù)中的結(jié)點(diǎn)。一般是按照二叉樹(shù)結(jié)點(diǎn)從上至下、從左到右的順序存儲(chǔ)。完全二叉樹(shù)和滿二叉樹(shù)采用順序存儲(chǔ)比較合適，樹(shù)中結(jié)點(diǎn)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系，這樣既能夠最大可能地節(jié)省存儲(chǔ)空間，又可以利用數(shù)組元素的下標(biāo)值確定結(jié)點(diǎn)在二叉樹(shù)中的位置以及結(jié)點(diǎn)之間的關(guān)系。5.3.3樹(shù)形結(jié)構(gòu)圖5.7滿二叉樹(shù)8DHIEJKFLGB5.3.3樹(shù)形結(jié)構(gòu)圖5.7滿二叉樹(shù)8DHIEJKFLGBCA2345679101112M13OP1415圖5.8完全二叉樹(shù)18DHIEJKFLGBCA2345679101112二叉樹(shù)的存儲(chǔ)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用鏈表來(lái)表示一棵二叉樹(shù)。鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，除了數(shù)據(jù)域外，還有兩個(gè)指針域，分別用來(lái)給出該結(jié)點(diǎn)的左子結(jié)點(diǎn)和右子結(jié)點(diǎn)所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址。非完全二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)5.3.3樹(shù)形結(jié)構(gòu)圖5.7滿二叉樹(shù)8DHIEJKFLGB5.3.3樹(shù)形結(jié)構(gòu)樹(shù)的應(yīng)用用于分類(lèi)的決策樹(shù)用于各種比賽的博弈樹(shù)5.3.3樹(shù)形結(jié)構(gòu)樹(shù)的應(yīng)用5.3.4圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)的特點(diǎn)數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系。圖的定義

G＝（V，E）;其中V＝{vi|vi∈dataobject}；E＝{(vi,vj)|vi,vj∈V∧P(vi,vj)}。G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，頂點(diǎn)集合構(gòu)成數(shù)據(jù)對(duì)象（dataobject），頂點(diǎn)就代表數(shù)據(jù)元素，E是圖G中邊的集合，集合E中P(vi,vj)表示頂點(diǎn)vi和頂點(diǎn)vj之間有一條直接連線，即偶對(duì)(vi,vj)表示圖中的一條邊。

5.3.4圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)的特點(diǎn)5.3.4圖狀結(jié)構(gòu)圖的示例圖的存儲(chǔ)鄰接矩陣用矩陣表示圖中各頂點(diǎn)之間的鄰接關(guān)系，有邊相連對(duì)應(yīng)的矩陣元素值為1，否則為0。5.3.4圖狀結(jié)構(gòu)圖的示例5.3.4圖狀結(jié)構(gòu)圖的存儲(chǔ)鄰接表一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合的存儲(chǔ)方法。對(duì)于圖G中的每個(gè)頂點(diǎn)vi，將所有鄰接于vi的頂點(diǎn)vj鏈成一個(gè)單鏈表，這個(gè)單鏈表就稱(chēng)為頂點(diǎn)vi的鄰接表，再將所有頂點(diǎn)的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表。5.3.4圖狀結(jié)構(gòu)圖的存儲(chǔ)5.3.4圖狀結(jié)構(gòu)圖的應(yīng)用求最短路徑網(wǎng)絡(luò)性能分析社會(huì)網(wǎng)絡(luò)分析5.3.4圖狀結(jié)構(gòu)圖的應(yīng)用5.4編譯原理編譯程序概述詞法分析語(yǔ)法分析中間代碼生成中間代碼優(yōu)化目標(biāo)代碼生成編譯程序的開(kāi)發(fā)5.4編譯原理編譯程序概述5.4.1編譯程序概述高級(jí)語(yǔ)言的特點(diǎn)簡(jiǎn)單易學(xué)，易于編寫(xiě)和修改程序。編寫(xiě)出的源程序不能直接執(zhí)行。編譯程序把用高級(jí)語(yǔ)言編寫(xiě)的源程序翻譯成等價(jià)的機(jī)器語(yǔ)言程序的翻譯程序。學(xué)習(xí)編譯知識(shí)的作用深入理解高級(jí)語(yǔ)言程序設(shè)計(jì)。有助于提高程序設(shè)計(jì)能力和培養(yǎng)程序設(shè)計(jì)思維。5.4.1編譯程序概述高級(jí)語(yǔ)言的特點(diǎn)5.4.2詞法分析詞法分析的主要任務(wù)從源程序中識(shí)別出單詞。發(fā)現(xiàn)詞法錯(cuò)誤并指出錯(cuò)誤位置。以某種機(jī)內(nèi)符的形式表示單詞。單詞種類(lèi)基本字：也稱(chēng)關(guān)鍵字，如C語(yǔ)言中的for、do、while等；標(biāo)識(shí)符：用來(lái)表示各種名字的符號(hào)串，如變量名、函數(shù)名等；常數(shù)：各種類(lèi)型的常數(shù)，如整數(shù)、實(shí)數(shù)、字符串等；運(yùn)算符：各種算術(shù)運(yùn)算、關(guān)系運(yùn)算符，如+、-、<、>、<=、>=等；界限符：如逗號(hào)（，）、分號(hào)（；）等。5.4.2詞法分析詞法分析的主要任務(wù)5.4.3語(yǔ)法分析語(yǔ)法分析的主要任務(wù)確認(rèn)作為詞法分析結(jié)果的單詞序列是否為給定語(yǔ)言的一個(gè)正確程序。給定語(yǔ)言用文法表示，如果給定的單詞串能夠識(shí)別成該文法的句子，則認(rèn)為程序是正確的，否則認(rèn)為程序是錯(cuò)誤的。自頂向下分析方法/自底向上分析方法。調(diào)用語(yǔ)義子程序進(jìn)行語(yǔ)義處理。審查每個(gè)語(yǔ)法結(jié)構(gòu)的靜態(tài)語(yǔ)義，即確認(rèn)語(yǔ)法結(jié)構(gòu)合法的程序是否真正有意義。5.4.3語(yǔ)法分析語(yǔ)法分析的主要任務(wù)5.4.4中間代碼生成中間代碼生成的主要任務(wù)以某種便于計(jì)算機(jī)處理的形式表示程序。引入中間代碼的優(yōu)點(diǎn)使編譯程序結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確。可以將與機(jī)器相關(guān)的某些實(shí)現(xiàn)細(xì)節(jié)置于代碼生成階段仔細(xì)處理。使得計(jì)算和代碼優(yōu)化比較容易實(shí)現(xiàn)。常用的中間代碼形式逆波蘭式/三元式/四元式。5.4.4中間代碼生成中間代碼生成的主要任務(wù)5.4.4中間代碼生成逆波蘭式計(jì)算的優(yōu)點(diǎn)a+b＊c的逆波蘭式形式為abc＊+。對(duì)于逆波蘭式abc＊+，計(jì)算機(jī)先掃描到運(yùn)算對(duì)象a、b和c，然后掃描到運(yùn)算符＊，先計(jì)算b＊c（假定結(jié)果為t），繼續(xù)掃描到運(yùn)算符+，再計(jì)算a+t，從而完成a+b＊c的計(jì)算。無(wú)論表達(dá)式多復(fù)雜，只一遍掃描就能完成表達(dá)式的計(jì)算。對(duì)于一般表達(dá)式a+b＊c，計(jì)算機(jī)先掃描到運(yùn)算對(duì)象a，然后掃描到運(yùn)算符+和運(yùn)算對(duì)象b，由于不知道后面的運(yùn)算符是什么，不能決定是否先完成+的運(yùn)算，繼續(xù)掃描到運(yùn)算符＊和運(yùn)算對(duì)象c，知道＊的優(yōu)先級(jí)高，先計(jì)算b＊c（假定結(jié)果為t），再往回掃描計(jì)算a+t。對(duì)于比較復(fù)雜的表達(dá)式，可能需要多次來(lái)回掃描表達(dá)式，才能完成計(jì)算，這會(huì)很浪費(fèi)時(shí)間。5.4.4中間代碼生成逆波蘭式計(jì)算的優(yōu)點(diǎn)5.4.5中間代碼優(yōu)化中間代碼優(yōu)化的主要任務(wù)對(duì)中間代碼進(jìn)行等價(jià)變換。變換后的代碼運(yùn)行結(jié)果與變換前運(yùn)行結(jié)果相同。運(yùn)行效率提高（速度提高或/和占用存儲(chǔ)空間減少）。常用的優(yōu)化技術(shù)刪除多余運(yùn)算/代碼外提/強(qiáng)度削弱。變換循環(huán)控制條件/合并已知量與復(fù)寫(xiě)傳播。刪除無(wú)用賦值。5.4.5中間代碼優(yōu)化中間代碼優(yōu)化的主要任務(wù)5.4.6目標(biāo)代碼生成目標(biāo)代碼生成的主要任務(wù)把經(jīng)過(guò)優(yōu)化后的中間代碼轉(zhuǎn)換成特定機(jī)器的機(jī)器語(yǔ)言程序或匯編語(yǔ)言程序。由于一個(gè)高級(jí)語(yǔ)言源程序的目標(biāo)代碼需多次使用，因此代碼生成器的設(shè)計(jì)要著重考慮目標(biāo)代碼的質(zhì)量。目標(biāo)代碼的質(zhì)量主要從占用空間和執(zhí)行時(shí)間兩個(gè)方面綜合考慮。

5.4.6目標(biāo)代碼生成目標(biāo)代碼生成的主要任務(wù)5.4.7編譯程序的開(kāi)發(fā)編譯程序的特點(diǎn)一個(gè)相當(dāng)復(fù)雜的系統(tǒng)軟件。編譯程序的自動(dòng)生成主要是語(yǔ)義分析和代碼優(yōu)化問(wèn)題。完全自動(dòng)生成編譯程序，目前還不現(xiàn)實(shí)。5.4.7編譯程序的開(kāi)發(fā)編譯程序的特點(diǎn)GNUC/C++編譯,匯編、鏈接器編譯程序gcc參數(shù)含義-o<file>Placetheoutputinto<file>-cCompileandassemble,butdonotlink-ggdbProducedebugginginformationforusebyGDB.-S編譯到匯編語(yǔ)言，不進(jìn)行匯編和鏈接-c編譯、匯編到目標(biāo)代碼，不進(jìn)行鏈接鏈接程序ldGNUC/C++編譯,匯編、鏈接器編譯程序gcc參數(shù)含義5.5本章小結(jié)程序設(shè)計(jì)能力、程序設(shè)計(jì)思維是計(jì)算機(jī)專(zhuān)業(yè)學(xué)生應(yīng)具備的基本能力和素質(zhì)。計(jì)算機(jī)專(zhuān)業(yè)人員要想發(fā)揮專(zhuān)業(yè)特長(zhǎng)，在工作中有競(jìng)爭(zhēng)力，較強(qiáng)的程序設(shè)計(jì)能力和軟件開(kāi)發(fā)能力是堅(jiān)實(shí)的基礎(chǔ)。與提高程序設(shè)計(jì)能力相關(guān)的知識(shí)有程序設(shè)計(jì)語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)、編譯原理和算法設(shè)計(jì)與分析。熟悉一種程序設(shè)計(jì)語(yǔ)言和基本的程序設(shè)計(jì)方法是編寫(xiě)程序的基礎(chǔ)。對(duì)于數(shù)據(jù)量比較大或數(shù)據(jù)之間關(guān)系比較復(fù)雜的程序，要選用合適的數(shù)據(jù)結(jié)構(gòu)合理地組織數(shù)據(jù)。計(jì)算機(jī)專(zhuān)業(yè)學(xué)生重點(diǎn)還是要培養(yǎng)和提高算法設(shè)計(jì)能力。用高級(jí)語(yǔ)言編寫(xiě)的源程序需要翻譯成機(jī)器語(yǔ)言程序，才能被計(jì)算機(jī)執(zhí)行。編譯原理就是介紹如何把高級(jí)語(yǔ)言源程序翻譯成機(jī)器語(yǔ)言程序的。5.5本章小結(jié)程序設(shè)計(jì)能力、程序設(shè)計(jì)思維是計(jì)算機(jī)專(zhuān)業(yè)學(xué)生應(yīng)第5章程序設(shè)計(jì)知識(shí)5.1程序設(shè)計(jì)語(yǔ)言5.2C語(yǔ)言程序設(shè)計(jì)5.3數(shù)據(jù)結(jié)構(gòu)5.4編譯原理第5章程序設(shè)計(jì)知識(shí)5.1程序設(shè)計(jì)語(yǔ)言5.1程序設(shè)計(jì)語(yǔ)言機(jī)器語(yǔ)言匯編語(yǔ)言高級(jí)語(yǔ)言結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言可視化程序設(shè)計(jì)語(yǔ)言人工智能程序設(shè)計(jì)語(yǔ)言學(xué)習(xí)語(yǔ)言是設(shè)計(jì)程序的基礎(chǔ)5.1程序設(shè)計(jì)語(yǔ)言機(jī)器語(yǔ)言學(xué)習(xí)語(yǔ)言是設(shè)計(jì)程序的基礎(chǔ)5.1.1機(jī)器語(yǔ)言機(jī)器語(yǔ)言的特點(diǎn)

由二進(jìn)制編碼指令構(gòu)成的語(yǔ)言。是一種依附于機(jī)器硬件的語(yǔ)言。機(jī)器語(yǔ)言程序可以直接執(zhí)行。機(jī)器語(yǔ)言程序片段

0001

0101

01101100

//把地址為01101100的內(nèi)存單元中的數(shù)裝入0101號(hào)寄存器

0001

0110

01101101

//把地址為01101101的內(nèi)存單元中的數(shù)裝入0110號(hào)寄存器

0101

0000

01010110

//把01101100和01101101中的數(shù)相加,結(jié)果存入0000號(hào)寄存器

0011

0000

01101110

//把0000號(hào)寄存器中的數(shù)存入地址為01101110的內(nèi)存單元中5.1.1機(jī)器語(yǔ)言機(jī)器語(yǔ)言的特點(diǎn)5.1.2匯編語(yǔ)言匯編語(yǔ)言的特點(diǎn)

由助記符指令構(gòu)成的語(yǔ)言。也是一種依附于機(jī)器硬件的語(yǔ)言。匯編語(yǔ)言源程序需要匯編后才能執(zhí)行。匯編語(yǔ)言程序片段

MOVR5,X//把內(nèi)存單元X中的數(shù)裝入R5寄存器

ADDR5,Y//把R5中的數(shù)與Y單元中的數(shù)相加，結(jié)果存入R5

MOVZ,R5//把R5中的數(shù)存入Z單元中

5.1.2匯編語(yǔ)言匯編語(yǔ)言的特點(diǎn)5.1.3高級(jí)語(yǔ)言高級(jí)語(yǔ)言的特點(diǎn)

由自然語(yǔ)言和數(shù)學(xué)公式表示的語(yǔ)言。是一種獨(dú)立于機(jī)器硬件的語(yǔ)言。高級(jí)語(yǔ)言程序需要編譯后才能執(zhí)行。高級(jí)語(yǔ)言程序片段

Z=X+Y

//把內(nèi)存單元X中的數(shù)與Y中的數(shù)相加，結(jié)果存入Z單元

5.1.3高級(jí)語(yǔ)言高級(jí)語(yǔ)言的特點(diǎn)5.1.3高級(jí)語(yǔ)言常用高級(jí)語(yǔ)言

FORTRAN語(yǔ)言FORTRAN是FORmulaTRANslator（公式翻譯器）的縮寫(xiě)。主要用于復(fù)雜的科學(xué)計(jì)算領(lǐng)域。ALGOL語(yǔ)言ALGOL是ALGOrithmLanguage（算法語(yǔ)言）的縮寫(xiě)。主要用于數(shù)學(xué)與科學(xué)計(jì)算。5.1.3高級(jí)語(yǔ)言常用高級(jí)語(yǔ)言5.1.3高級(jí)語(yǔ)言常用高級(jí)語(yǔ)言

COBOL語(yǔ)言

COBOL是COmmonBusiness-OrientedLanguage（面向商業(yè)的通用語(yǔ)言）的縮寫(xiě)。主要用于企業(yè)管理和事務(wù)處理。BASIC語(yǔ)言

BASIC是Beginner’sAll-purposeSymbolicInstructionCode（初學(xué)者通用符號(hào)指令碼）的縮寫(xiě)。主要用于初學(xué)者和較小規(guī)模的程序開(kāi)發(fā)。5.1.3高級(jí)語(yǔ)言常用高級(jí)語(yǔ)言5.1.4結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言早期程序設(shè)計(jì)方法的不足注重功能的實(shí)現(xiàn)/注重內(nèi)存的節(jié)省/注重執(zhí)行效率的提高。不注重程序結(jié)構(gòu)的清晰性。不注重程序的可理解性和可修改性。結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言的特點(diǎn)

注重程序結(jié)構(gòu)的清晰性。注重程序的可理解性和可修改性。采用模塊化程序設(shè)計(jì)方法。5.1.4結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言早期程序設(shè)計(jì)方法的不足5.1.4結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言常用結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言

PASCAL語(yǔ)言

是在ALGOL語(yǔ)言的基礎(chǔ)上發(fā)展起來(lái)的。以法國(guó)著名科學(xué)家帕斯卡的名字命名。嚴(yán)格的語(yǔ)法格式與結(jié)構(gòu)化形式。C語(yǔ)言

是在ALGOL60語(yǔ)言的基礎(chǔ)上發(fā)展起來(lái)的。兼具低級(jí)語(yǔ)言和高級(jí)語(yǔ)言的特點(diǎn)。是最為流行的程序設(shè)計(jì)語(yǔ)言之一。5.1.4結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言常用結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言5.1.5面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言結(jié)構(gòu)化程序設(shè)計(jì)方法的不足

面向過(guò)程的設(shè)計(jì)方法與人們習(xí)慣的思維方式仍然存在一定的距離，所以很難自然、準(zhǔn)確地反映真實(shí)世界，因而用編寫(xiě)出來(lái)的程序，特別是規(guī)模比較大的程序，其質(zhì)量是難以保證的。強(qiáng)調(diào)了要實(shí)現(xiàn)功能的操作方法（模塊），而被操作的數(shù)據(jù)（變量）處于實(shí)現(xiàn)功能的從屬地位，即程序模塊和數(shù)據(jù)結(jié)構(gòu)是松散地耦合在一起，當(dāng)程序復(fù)雜度較高時(shí)，容易出錯(cuò)，而且錯(cuò)誤難以查找和修改。5.1.5面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言結(jié)構(gòu)化程序設(shè)計(jì)方法的不足5.1.5面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言的特點(diǎn)

將問(wèn)題分解為對(duì)象。對(duì)象將自己的屬性和方法封裝成一個(gè)整體，供程序設(shè)計(jì)者使用。對(duì)象之間的相互作用則通過(guò)消息傳遞來(lái)實(shí)現(xiàn)。使人們對(duì)復(fù)雜系統(tǒng)的認(rèn)識(shí)過(guò)程與程序設(shè)計(jì)過(guò)程盡可能一致。能夠更好地保證程序的質(zhì)量和開(kāi)發(fā)效率。5.1.5面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言的特點(diǎn)5.1.5面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言常用面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言

Simula67

發(fā)布于1967年，是面向?qū)ο笳Z(yǔ)言的鼻祖。C++

發(fā)布于1983年，是在C語(yǔ)言的基礎(chǔ)上發(fā)展起來(lái)的。C++是得到廣泛應(yīng)用的一種面向?qū)ο笳Z(yǔ)言。目前常用的版本有VisualC++,C#,VisualC++.Net等。Java發(fā)布于1995年，適合于網(wǎng)絡(luò)程序設(shè)計(jì)。也是目前得到廣泛應(yīng)用的一種面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言。5.1.5面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言常用面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言5.1.6可視化程序設(shè)計(jì)語(yǔ)言可視化程序設(shè)計(jì)語(yǔ)言的特點(diǎn)

以圖形化的編程方式將面向?qū)ο蠹夹g(shù)的特性體現(xiàn)出來(lái)。使開(kāi)發(fā)軟件這一原本枯燥、難以理解的工作變得相對(duì)輕松快捷。常用可視化程序設(shè)計(jì)語(yǔ)言VisualC++功能強(qiáng)大，比較適合專(zhuān)業(yè)人員使用。VisualBasic易于學(xué)習(xí)和掌握，比較適合非專(zhuān)業(yè)人員和初學(xué)者使用。5.1.6可視化程序設(shè)計(jì)語(yǔ)言可視化程序設(shè)計(jì)語(yǔ)言的特點(diǎn)5.1.7人工智能程序設(shè)計(jì)語(yǔ)言人工智能程序設(shè)計(jì)語(yǔ)言的特點(diǎn)

適合于知識(shí)表示和邏輯推理。

常用人工智能程序設(shè)計(jì)語(yǔ)言

LISP

LISP是LIStProcessing（表處理）的縮寫(xiě)。可以解決人工智能中的符號(hào)處理問(wèn)題。

PROLOG

是PROgramminginLOGic（邏輯程序設(shè)計(jì)）的縮寫(xiě)。自動(dòng)實(shí)現(xiàn)模式匹配、自動(dòng)回溯這兩種人工智能中常用的基本操作。5.1.7人工智能程序設(shè)計(jì)語(yǔ)言人工智能程序設(shè)計(jì)語(yǔ)言的特點(diǎn)5.2C語(yǔ)言程序設(shè)計(jì)C語(yǔ)言的主要特點(diǎn)簡(jiǎn)潔、緊湊、靈活。語(yǔ)法限制不太嚴(yán)格，使用方便靈活；數(shù)據(jù)結(jié)構(gòu)描述能力及表達(dá)式能力強(qiáng)；程序書(shū)寫(xiě)形式自由。模塊化、結(jié)構(gòu)化。用Ｃ語(yǔ)言編寫(xiě)程序?qū)哟吻逦?，便于按模塊組織程序，易于實(shí)現(xiàn)程序的結(jié)構(gòu)化。

功能強(qiáng)大。C語(yǔ)言除了能實(shí)現(xiàn)一般的高級(jí)語(yǔ)言的功能外，還能實(shí)現(xiàn)匯編語(yǔ)言的大部分功能，兼具高級(jí)語(yǔ)言和低級(jí)語(yǔ)言的特點(diǎn)。可移植性好。C語(yǔ)言程序可以容易地移植到不同型號(hào)計(jì)算機(jī)、不同操作系統(tǒng)環(huán)境下執(zhí)行。5.2C語(yǔ)言程序設(shè)計(jì)C語(yǔ)言的主要特點(diǎn)5.2C語(yǔ)言程序設(shè)計(jì)C語(yǔ)言的基本要素C語(yǔ)言的數(shù)據(jù)類(lèi)型C語(yǔ)言的運(yùn)算符及表達(dá)式C語(yǔ)言語(yǔ)句C語(yǔ)言程序的三種基本結(jié)構(gòu)及實(shí)現(xiàn)程序設(shè)計(jì)風(fēng)格算法設(shè)計(jì)與分析5.2C語(yǔ)言程序設(shè)計(jì)C語(yǔ)言的基本要素5.2.1C語(yǔ)言的基本要素C語(yǔ)言的基本詞法字符集英文字母/數(shù)字/特殊字符/轉(zhuǎn)義字符。標(biāo)識(shí)符C語(yǔ)言中各種對(duì)象的名字用標(biāo)識(shí)符表示。標(biāo)識(shí)符是由字母、數(shù)字和下劃線三種字符構(gòu)成的且第一個(gè)字符必須是字母或下劃線的字符序列。標(biāo)識(shí)符分為三類(lèi)關(guān)鍵字/預(yù)定義標(biāo)識(shí)符/用戶(hù)標(biāo)識(shí)符。5.2.1C語(yǔ)言的基本要素C語(yǔ)言的基本詞法5.2.1C語(yǔ)言的基本要素常量在程序的執(zhí)行過(guò)程中其值不能被改變的量。數(shù)值型常量整型常量/浮點(diǎn)型常量（實(shí)型常量）。字符型常量字符常量/字符串常量。變量在程序運(yùn)行過(guò)程中，其值可以被改變的量。一般要先定義，再使用，變量定義的一般形式為：

數(shù)據(jù)類(lèi)型名變量名；5.2.1C語(yǔ)言的基本要素常量5.2.2C語(yǔ)言的數(shù)據(jù)類(lèi)型基本數(shù)據(jù)類(lèi)型整型整型變量的定義形式為：int變量名；實(shí)型實(shí)型變量的定義形式為：float變量名；字符型字符型變量的定義格式為：char變量名；構(gòu)造數(shù)據(jù)類(lèi)型數(shù)組/結(jié)構(gòu)體/共用體/枚舉類(lèi)型/用戶(hù)自定義類(lèi)型。指針類(lèi)型在動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用中有著不可替代的作用。5.2.2C語(yǔ)言的數(shù)據(jù)類(lèi)型基本數(shù)據(jù)類(lèi)型5.2.3C語(yǔ)言的運(yùn)算符及表達(dá)式算術(shù)運(yùn)算符＋,－,*,/,%（求余數(shù)）。

賦值運(yùn)算符在C語(yǔ)言中，＝稱(chēng)為賦值運(yùn)算符，其使用形式為：

變量名＝表達(dá)式自增、自減運(yùn)算符++是自增運(yùn)算符，其功能是使變量的值增1。--是自減運(yùn)算符，其功能是使變量的值減1。關(guān)系運(yùn)算符大小判斷＞（大于）/＞＝（大于等于）/＜（小于）/＜＝（小于等于）。相等判斷＝＝（等于）/!＝（不等于）。

5.2.3C語(yǔ)言的運(yùn)算符及表達(dá)式算術(shù)運(yùn)算符5.2.4C語(yǔ)言語(yǔ)句控制語(yǔ)句

用于實(shí)現(xiàn)一定的控制功能。條件語(yǔ)句：用于實(shí)現(xiàn)程序執(zhí)行過(guò)程中的條件轉(zhuǎn)移。循環(huán)語(yǔ)句：用于實(shí)現(xiàn)程序中重復(fù)進(jìn)行某些操作。 復(fù)合語(yǔ)句由一對(duì)花括號(hào){}括起來(lái)的一組語(yǔ)句。如果要在只執(zhí)行一條語(yǔ)句的地方執(zhí)行多條語(yǔ)句，那么這多條語(yǔ)句要寫(xiě)成一條復(fù)合語(yǔ)句。5.2.4C語(yǔ)言語(yǔ)句控制語(yǔ)句5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)順序結(jié)構(gòu)程序的執(zhí)行按照語(yǔ)句出現(xiàn)的先后次序順序進(jìn)行。程序中的每個(gè)語(yǔ)句都會(huì)被執(zhí)行到。程序示例：通過(guò)鍵盤(pán)輸入一個(gè)三角形的底和高，計(jì)算其面積并輸出。

main(){floatwidth,height,area; /*定義變量*/printf("\nEnterwidthandheight:");/*輸出提示信息*/scanf("%f,%f",&width,&height); /*通過(guò)鍵盤(pán)輸入底和高*/area=(width*height)/2.0; /*計(jì)算面積*/printf("\nThearaeis:%f",area); /*輸出面積的值*/}5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)順序結(jié)構(gòu)5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)分支結(jié)構(gòu)根據(jù)邏輯條件的成立與否，分別選擇執(zhí)行不同的處理。if語(yǔ)句：if（表達(dá)式）語(yǔ)句if-else語(yǔ)句：if（表達(dá)式）語(yǔ)句1else語(yǔ)句25.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)分支結(jié)構(gòu)5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)分支結(jié)構(gòu)程序示例：根據(jù)輸入的學(xué)生成績(jī)對(duì)其進(jìn)行判斷處理，如果成績(jī)及格，則輸出Passed，否則輸出Failed。

main(){floatscore; /*定義變量*/printf("\nEnterascore:"); /*顯示提示信息*/scanf("%f",&score); /*通過(guò)鍵盤(pán)輸入一個(gè)成績(jī)*/if(score>=60.0)printf("\nPassed"); /*大于等于60輸出Passed*/else printf("\nFailed"); /*小于60輸出Failed*/}5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)分支結(jié)構(gòu)5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)循環(huán)結(jié)構(gòu)根據(jù)循環(huán)條件的變化，決定是否繼續(xù)重復(fù)執(zhí)行某些語(yǔ)句。for循環(huán)語(yǔ)句的格式為：

for（表達(dá)式1；表達(dá)式2；表達(dá)式3）循環(huán)體語(yǔ)句

5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)循環(huán)結(jié)構(gòu)5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)循環(huán)結(jié)構(gòu)程序示例：從鍵盤(pán)上輸入10個(gè)整數(shù)，求其累加和并輸出。

main(){inti,num,sum; /*定義變量*/sum=0; /*累加變量清零*/for(i=1;i<=10;i++) /*循環(huán)次數(shù)為10*/

{printf("Enteradata:\n"); /*顯示提示信息*/ scanf("%d",&num); /*通過(guò)鍵盤(pán)輸入一個(gè)整數(shù)*/ sum=sum+num; /*累加求和*/

}printf(“\nsum=%d,sum); /*輸出累加結(jié)果*/}

5.2.5C語(yǔ)言程序的三種基本結(jié)構(gòu)循環(huán)結(jié)構(gòu)5.2.6程序設(shè)計(jì)風(fēng)格主要體現(xiàn)在5個(gè)方面標(biāo)識(shí)符的命名要風(fēng)格統(tǒng)一、見(jiàn)名知義。一般一行寫(xiě)一條語(yǔ)句，一條長(zhǎng)語(yǔ)句可以寫(xiě)在多行上，但盡量不要把多條語(yǔ)句寫(xiě)在一行上。采用縮進(jìn)格式，即同一層次的語(yǔ)句要對(duì)齊，低層次的語(yǔ)句要縮進(jìn)若干個(gè)字符，增加程序的可讀性。適當(dāng)書(shū)寫(xiě)注釋信息，有助于閱讀者對(duì)程序的理解。盡量少用goto語(yǔ)句，否則容易導(dǎo)致程序結(jié)構(gòu)混亂。5.2.6程序設(shè)計(jì)風(fēng)格主要體現(xiàn)在5個(gè)方面5.2.7算法設(shè)計(jì)與分析用計(jì)算機(jī)解決問(wèn)題的步驟分析問(wèn)題、設(shè)計(jì)算法。選定語(yǔ)言、編寫(xiě)源程序。對(duì)源程序進(jìn)行編譯生成目標(biāo)文件。對(duì)目標(biāo)文件進(jìn)行連接操作，生成可執(zhí)行的程序。調(diào)試執(zhí)行可執(zhí)行程序。5.2.7算法設(shè)計(jì)與分析用計(jì)算機(jī)解決問(wèn)題的步驟5.2.7算法設(shè)計(jì)與分析程序與算法算法是指為解決某一問(wèn)題而采取的方法和步驟。程序是程序設(shè)計(jì)人員編寫(xiě)的、計(jì)算機(jī)能夠理解并執(zhí)行的命令集合，是算法在計(jì)算機(jī)中的實(shí)現(xiàn)。算法的特點(diǎn)有窮性/確定性/有效性/輸入及輸出。算法的表示自然語(yǔ)言/流程圖/偽碼。算法的評(píng)價(jià)標(biāo)準(zhǔn)正確性/時(shí)間復(fù)雜度/空間復(fù)雜度/可理解性。5.2.7算法設(shè)計(jì)與分析程序與算法5.3數(shù)據(jù)結(jié)構(gòu)概念和術(shù)語(yǔ)線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖狀結(jié)構(gòu)5.3數(shù)據(jù)結(jié)構(gòu)概念和術(shù)語(yǔ)5.3.1概念和術(shù)語(yǔ)數(shù)據(jù)信息的載體，能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。數(shù)據(jù)項(xiàng)數(shù)據(jù)不可分割的最小單位。數(shù)據(jù)元素?cái)?shù)據(jù)的基本單位，具有完整、確定的實(shí)際意義。一般由若干數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)對(duì)象具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。5.3.1概念和術(shù)語(yǔ)數(shù)據(jù)5.3.1概念和術(shù)語(yǔ)數(shù)據(jù)的邏輯結(jié)構(gòu)描述的是數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)在計(jì)算機(jī)中的表示，包括數(shù)據(jù)元素的表示及數(shù)據(jù)元素間關(guān)系的表示。5.3.1概念和術(shù)語(yǔ)數(shù)據(jù)的邏輯結(jié)構(gòu)5.3.1概念和術(shù)語(yǔ)順序存儲(chǔ)邏輯上相鄰的元素存儲(chǔ)在物理位置也相鄰的存儲(chǔ)單元中。鏈?zhǔn)酱鎯?chǔ)邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過(guò)附設(shè)的指針字段來(lái)表示。5.3.1概念和術(shù)語(yǔ)順序存儲(chǔ)5.3.2線性結(jié)構(gòu)線性結(jié)構(gòu)的特點(diǎn)數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系。每個(gè)元素有且只有一個(gè)前驅(qū)（第一個(gè)元素除外）。每個(gè)元素有且只有一個(gè)后繼（最后一個(gè)元素除外）。應(yīng)用示例一維數(shù)組二維數(shù)組5.3.2線性結(jié)構(gòu)線性結(jié)構(gòu)的特點(diǎn)5.3.2線性結(jié)構(gòu)一維數(shù)組應(yīng)用示例

main(){inti,g,sum,ave;/*定義變量，每一變量代表一內(nèi)存單元*/inta[50];/*定義數(shù)組，代表50個(gè)內(nèi)存單元*/for(i=1;i<=50;i++)/*循環(huán)執(zhí)行下面大括號(hào)中的語(yǔ)句50次*/{printf(“\nEnteragrade:”);/*在屏幕上顯示提示信息*/scanf(“%d”,&g); /*通過(guò)鍵盤(pán)輸入一個(gè)學(xué)生的成績(jī)給變量g*/a[i-1]=g; /*把g單元中的成績(jī)存入數(shù)組的相應(yīng)位置*/}sum=0; /*作為累加器的單元初值清零*/for(i=1;i<=50;i++) /*循環(huán)執(zhí)行下面的累加語(yǔ)句40次*/sum=sum+a[i-1]; /*把第i個(gè)學(xué)生的成績(jī)加到累加器*/ave=sum/50; /*求平均成績(jī)*/printf(“\nave=%d”,ave); /*輸出平均成績(jī)*/}5.3.2線性結(jié)構(gòu)一維數(shù)組應(yīng)用示例5.3.3樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu)的特點(diǎn)數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。樹(shù)的定義樹(shù)是n（≥0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)，稱(chēng)為空樹(shù)。在一棵非空樹(shù)T中：

有一個(gè)特定的結(jié)點(diǎn)稱(chēng)為樹(shù)的根結(jié)點(diǎn)；當(dāng)n>1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m（m≥1）個(gè)互不相交的集合T1，T2，…，Tm，其中每一個(gè)集合Ti（1≤i≤m）本身又是一棵樹(shù)，樹(shù)T1，T2，…，Tm稱(chēng)為這個(gè)根結(jié)點(diǎn)的子樹(shù)。5.3.3樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu)的特點(diǎn)5.3.3樹(shù)形結(jié)構(gòu)二叉樹(shù)的定義二叉樹(shù)是有限個(gè)結(jié)點(diǎn)的集合，該集合或者為空、或者由一個(gè)稱(chēng)為根的結(jié)點(diǎn)及兩個(gè)不相交的、被分別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。當(dāng)集合為空時(shí)，稱(chēng)該二叉樹(shù)為空二叉樹(shù)。滿二叉樹(shù)：在二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的一棵二叉樹(shù)稱(chēng)作滿二叉樹(shù)。完全二叉樹(shù)：一棵深度為k的有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，對(duì)樹(shù)中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，如果編號(hào)為i（1≤i≤n）的結(jié)點(diǎn)與滿二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中的位置相同，則這棵二叉樹(shù)稱(chēng)為完全二叉樹(shù)。

5.3.3樹(shù)形結(jié)構(gòu)二叉樹(shù)的定義5.3.3樹(shù)形結(jié)構(gòu)二叉樹(shù)示例滿二叉樹(shù)完全二叉樹(shù)非完全二叉樹(shù)5.3.3樹(shù)形結(jié)構(gòu)二叉樹(shù)示例滿二叉樹(shù)完全二叉樹(shù)非完全二叉樹(shù)5.3.3樹(shù)形結(jié)構(gòu)圖5.7滿二叉樹(shù)8DHIEJKFLGBCA2345679101112M13OP1415圖5.8完全二叉樹(shù)18DHIEJKFLGBCA2345679101112二叉樹(shù)的存儲(chǔ)

順序存儲(chǔ)結(jié)構(gòu)用一組連續(xù)的存儲(chǔ)單元（數(shù)組）存放二叉樹(shù)中的結(jié)點(diǎn)。一般是按照二叉樹(shù)結(jié)點(diǎn)從上至下、從左到右的順序存儲(chǔ)。完全二叉樹(shù)和滿二叉樹(shù)采用順序存儲(chǔ)比較合適，樹(shù)中結(jié)點(diǎn)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系，這樣既能夠最大可能地節(jié)省存儲(chǔ)空間，又可以利用數(shù)組元素的下標(biāo)值確定結(jié)點(diǎn)在二叉樹(shù)中的位置以及結(jié)點(diǎn)之間的關(guān)系。5.3.3樹(shù)形結(jié)構(gòu)圖5.7滿二叉樹(shù)8DHIEJKFLGB5.3.3樹(shù)形結(jié)構(gòu)圖5.7滿二叉樹(shù)8DHIEJKFLGBCA2345679101112M13OP1415圖5.8完全二叉樹(shù)18DHIEJKFLGBCA2345679101112二叉樹(shù)的存儲(chǔ)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用鏈表來(lái)表示一棵二叉樹(shù)。鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，除了數(shù)據(jù)域外，還有兩個(gè)指針域，分別用來(lái)給出該結(jié)點(diǎn)的左子結(jié)點(diǎn)和右子結(jié)點(diǎn)所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址。非完全二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)5.3.3樹(shù)形結(jié)構(gòu)圖5.7滿二叉樹(shù)8DHIEJKFLGB5.3.3樹(shù)形結(jié)構(gòu)樹(shù)的應(yīng)用用于分類(lèi)的決策樹(shù)用于各種比賽的博弈樹(shù)5.3.3樹(shù)形結(jié)構(gòu)樹(shù)的應(yīng)用5.3.4圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)的特點(diǎn)數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系。圖的定義

G＝（V，E）;其中V＝{vi|vi∈dataobject}；E＝{(vi,vj)|vi,vj∈V∧P(vi,vj)}。G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，頂點(diǎn)集合構(gòu)成數(shù)據(jù)對(duì)象（dataobject），頂點(diǎn)就代表數(shù)據(jù)元素，E是圖G中邊的集合，集合E中P(vi,vj)表示頂點(diǎn)vi和頂點(diǎn)vj之間有一條直接連線，即偶對(duì)(vi,vj)表示圖中的一條邊。

5.3.4圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)的特點(diǎn)5.3.4圖狀結(jié)構(gòu)圖的示例圖的存儲(chǔ)鄰接矩陣用矩陣表示圖中各頂點(diǎn)之間的鄰接關(guān)系，有邊相連對(duì)應(yīng)的矩陣元素值為1，否則為0。5.3.4圖狀結(jié)構(gòu)圖的示例5.3.4圖狀結(jié)構(gòu)圖的存儲(chǔ)鄰接表一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合的存儲(chǔ)方法。對(duì)于圖G中的每個(gè)頂點(diǎn)vi，將所有鄰接于vi的頂點(diǎn)vj鏈成一個(gè)單鏈表，這個(gè)單鏈表就稱(chēng)為頂點(diǎn)vi的鄰接表，