《大學(xué)計(jì)算機(jī)基礎(chǔ)》第3章-程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)(2014_11_29)【amj】【OK】

1、大學(xué)計(jì)算機(jī)基礎(chǔ)大學(xué)計(jì)算機(jī)基礎(chǔ)北京航空航天大學(xué)計(jì)算機(jī)學(xué)院2課程目錄第6章求解顯示，交互 （2學(xué)時(shí)）求解效率，優(yōu)化和限制 （2學(xué)時(shí)）第5章求解的工程思維，規(guī)范 （2學(xué)時(shí)）第7章程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu) （6學(xué)時(shí)）第3章計(jì)算機(jī)與計(jì)算思維 （6學(xué)時(shí)）第1章第2章問(wèn)題的抽象與建模 （4學(xué)時(shí)）問(wèn)題的求解，算法及實(shí)現(xiàn) （4學(xué)時(shí)）第4章3第3章 程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)程序與程序設(shè)計(jì)語(yǔ)言3.4 程序控制結(jié)構(gòu)3.3 Python的基本構(gòu)成及操作3.5 函數(shù)、模塊及文件3.6 Python中類(lèi)的定義3.7 Python實(shí)現(xiàn)典型數(shù)據(jù)結(jié)構(gòu)4本 章 重 點(diǎn) n了解如何設(shè)計(jì)程序：程序結(jié)構(gòu)n掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)的概

2、念n了解數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)概念上的聯(lián)系與區(qū)別n掌握數(shù)據(jù)結(jié)構(gòu)的定義及其三個(gè)組成部分n掌握使用Python的基礎(chǔ)操作，對(duì)象、類(lèi)型、表達(dá)式、程序控制結(jié)構(gòu)，如何構(gòu)建較大規(guī)模的程序n掌握如何在Python中定義“類(lèi)”n掌握典型數(shù)據(jù)結(jié)構(gòu)的定義，抽象數(shù)據(jù)類(lèi)型及實(shí)現(xiàn)方法53.1 程序與程序設(shè)計(jì)語(yǔ)言u(píng)3.1.1 引例引例u3.1.2 程序與程序與程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言u(píng)3.1.3 Python語(yǔ)言簡(jiǎn)介語(yǔ)言簡(jiǎn)介63.1.1 引例 n方法1：積分法 u在平面坐標(biāo)系中有一個(gè)圓心在原點(diǎn)、半徑r為1的圓，用矩形法計(jì)算第一象限的面積S，4*S就是整個(gè)圓的面積u圓面積也可以通過(guò)r2來(lái)求，因此可得=4*Su嘗試不同的小

3、矩形寬度，以得到不同精度的值 【例例3.1】如何計(jì)算圓周率？方法2：隨機(jī)法44正方形面積圓面積22rr正方形的面積倍的圓面積4122 yxu可以通過(guò)如下的方式計(jì)算的近似值u假設(shè)圓的半徑為1，產(chǎn)生0到1之間的兩個(gè)隨機(jī)實(shí)數(shù)x和y。則（x,y）這個(gè)點(diǎn)是正方形中的一個(gè)點(diǎn)u如果 ，則點(diǎn)落在圓內(nèi)u重復(fù)n次上述動(dòng)作，并記錄點(diǎn)落在圓內(nèi)的次數(shù)mu通過(guò) ，可得的近似值 122yxnm4n方法2： 隨機(jī)法7兩種方法的源程序及運(yùn)行 方法1：源程序及運(yùn)行方法2： 源程序及運(yùn)行8什么是軟件？n什么是軟件？u國(guó)標(biāo)中對(duì)軟件（Software）的定義：與計(jì)算機(jī)系統(tǒng)操作有關(guān)的計(jì)算機(jī)程序、規(guī)程、規(guī)則，以及可能有的文件、文檔及數(shù)據(jù)u

4、硬件是計(jì)算機(jī)系統(tǒng)的物質(zhì)基礎(chǔ)，軟件則是計(jì)算機(jī)系統(tǒng)的靈魂u軟件是用戶與硬件之間的接口界面。用戶主要是通過(guò)軟件與計(jì)算機(jī)進(jìn)行交流u軟件是計(jì)算機(jī)系統(tǒng)設(shè)計(jì)的重要依據(jù)。為了方便用戶，為了使計(jì)算機(jī)系統(tǒng)具有較高的總體效用，在設(shè)計(jì)計(jì)算機(jī)系統(tǒng)時(shí)，必須全局考慮軟件與硬件的結(jié)合，以及用戶的要求和軟件的要求1運(yùn)行時(shí)，能夠提供所要求功能和性能的指令或計(jì)算機(jī)程序集合 2程序能夠滿意地處理信息的數(shù)據(jù)結(jié)構(gòu) 3描述程序功能需求以及程序如何操作和使用所要求的文檔 9軟件=程序+數(shù)據(jù)+文檔3.1.2 程序與程序設(shè)計(jì)語(yǔ)言n如何讓計(jì)算機(jī)理解我們的意圖，自動(dòng)進(jìn)行計(jì)算？ 我們需要事先編寫(xiě)程序，輸入計(jì)算機(jī)中n什么是程序？u程序（Program）

5、是軟件開(kāi)發(fā)人員根據(jù)用戶需求開(kāi)發(fā)的，用程序設(shè)計(jì)語(yǔ)言描述的，適合計(jì)算機(jī)執(zhí)行的指令（語(yǔ)句）序列 10算法數(shù)據(jù)結(jié)構(gòu)程序解決問(wèn)題的方法和步驟數(shù)據(jù)的組織形式u第一種結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言Pascal的發(fā)明者尼克勞斯沃爾斯（Niklaus Wirth）認(rèn)為算法、語(yǔ)言與計(jì)算機(jī)程序11算法算法解決問(wèn)題的方法和步驟程序程序計(jì)算機(jī)能夠理解與執(zhí)行的解決問(wèn)題的步驟程序設(shè)計(jì)語(yǔ)程序設(shè)計(jì)語(yǔ)言言步驟書(shū)寫(xiě)的規(guī)范、語(yǔ)法規(guī)則、標(biāo)準(zhǔn)的集合是人和計(jì)算機(jī)都能理解的語(yǔ)言12程序設(shè)計(jì)語(yǔ)言n程序設(shè)計(jì)語(yǔ)言u(píng)程序設(shè)計(jì)語(yǔ)言（Programming Language）（或編程語(yǔ)言）是用于書(shū)寫(xiě)計(jì)算機(jī)程序的語(yǔ)言。它是軟件的基礎(chǔ)和組成u程序設(shè)計(jì)語(yǔ)言由單詞、語(yǔ)句、

6、函數(shù)和程序文件等組成機(jī)器語(yǔ)言直接用二進(jìn)制 無(wú)需翻譯 效率高u使用繁瑣匯編語(yǔ)言使用助記符 較易掌握u需要翻譯u通用性差高級(jí)語(yǔ)言最接近人類(lèi)語(yǔ)言 容易使用 易于移植u需要翻譯u效率較低程序設(shè)計(jì)語(yǔ)言的鴻溝13計(jì)算機(jī)自然語(yǔ)言面向?qū)ο笳Z(yǔ)言結(jié)構(gòu)化描述語(yǔ)言匯編語(yǔ)言機(jī)器語(yǔ)言客觀世界（問(wèn)題域）語(yǔ)言的鴻溝n程序設(shè)計(jì)語(yǔ)言的鴻溝不同的程序設(shè)計(jì)階段的問(wèn)題計(jì)算機(jī)自然語(yǔ)言：需求分析結(jié)構(gòu)圖：概要設(shè)計(jì)流程圖/PDL：詳細(xì)設(shè)計(jì)匯編語(yǔ)言：編碼？：測(cè)試客觀世界（問(wèn)題域） 分析與設(shè)計(jì)的鴻溝 設(shè)計(jì)的鴻溝 設(shè)計(jì)與實(shí)現(xiàn)的鴻溝高級(jí)程序設(shè)計(jì)語(yǔ)言：代碼實(shí)現(xiàn)？：檢驗(yàn)？：驗(yàn)證n不同的程序設(shè)計(jì)階段的問(wèn)題14程序設(shè)計(jì)方法n程序設(shè)計(jì)方法分為兩大類(lèi)u面向過(guò)程的

7、結(jié)構(gòu)化程序設(shè)計(jì)方法 u面向?qū)ο蟮某绦蛟O(shè)計(jì)方法 151、面向過(guò)程的結(jié)構(gòu)化程序設(shè)計(jì)方法u1969年，荷蘭科學(xué)家EWDijkstra提出了結(jié)構(gòu)化程序設(shè)計(jì)（Structured Programming）的概念強(qiáng)調(diào)從程序的結(jié)構(gòu)和風(fēng)格上來(lái)研究程序設(shè)計(jì)方法提倡利用三種基本結(jié)構(gòu)（順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)）進(jìn)行規(guī)范化程序設(shè)計(jì)，使程序具有模塊化特征從程序要實(shí)現(xiàn)的功能出發(fā)進(jìn)行程序設(shè)計(jì)，目的是使程序具有良好的結(jié)構(gòu)框架1、面向過(guò)程的結(jié)構(gòu)化程序設(shè)計(jì)方法16u1971年，瑞士聯(lián)邦技術(shù)學(xué)院的Niklaus Wirth（尼克勞斯沃爾斯）教授推出了Pascal結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言，在計(jì)算機(jī)軟件開(kāi)發(fā)與編程人員中，興起了學(xué)用Pas

8、cal語(yǔ)言進(jìn)行結(jié)構(gòu)化編程的高潮n結(jié)構(gòu)化程序設(shè)計(jì)方法是一種傳統(tǒng)的程序設(shè)計(jì)方法n由結(jié)構(gòu)化分析、結(jié)構(gòu)化設(shè)計(jì)和結(jié)構(gòu)化編碼三部分組成n其本質(zhì)是功能的分解u將系統(tǒng)按功能分解為若干模塊，每個(gè)模塊是實(shí)現(xiàn)系統(tǒng)某一功能的程序單元。每個(gè)模塊都具有輸入、輸出和過(guò)程等基本特性結(jié)構(gòu)化程序設(shè)計(jì)方法的特點(diǎn)17u程序?qū)哟畏置?、邏輯清晰、功能?dú)立u降低了開(kāi)發(fā)程序的復(fù)雜性，增加了程序的可靠性u(píng)便于團(tuán)隊(duì)合作，快速而高效地完成項(xiàng)目開(kāi)發(fā)u增強(qiáng)了系統(tǒng)的可維護(hù)性，使程序設(shè)計(jì)更加規(guī)范化 n結(jié)構(gòu)化程序設(shè)計(jì)方法的特點(diǎn)u自頂向下、逐步求精復(fù)雜問(wèn)題逐步分解為簡(jiǎn)單的子問(wèn)題u劃分功能模塊整個(gè)程序由相對(duì)獨(dú)立的、分層次的功能模塊組成u結(jié)構(gòu)化編程任何程序或算法

9、均以三種基本控制結(jié)構(gòu)或嵌套基本結(jié)構(gòu)實(shí)現(xiàn)面向過(guò)程的程序設(shè)計(jì)方法的不足18n面向過(guò)程的程序設(shè)計(jì)方法的不足u基于功能的設(shè)計(jì)方法難以適應(yīng)系統(tǒng)需求的變化，功能變化則程序必須重新設(shè)計(jì)u數(shù)據(jù)和處理數(shù)據(jù)的過(guò)程分離為相互獨(dú)立的實(shí)體，它只是封裝了各個(gè)功能模塊，而每個(gè)功能模塊可以隨意修改未加封裝的數(shù)據(jù)。使得數(shù)據(jù)可靠性、安全性難以得到保障，不利于對(duì)程序的維護(hù)u當(dāng)數(shù)據(jù)結(jié)構(gòu)改變時(shí)，所有相關(guān)的處理過(guò)程都要進(jìn)行相應(yīng)修改，程序的可重用性差n新時(shí)期的新問(wèn)題，以及軟件產(chǎn)業(yè)的更高要求，迫使人們尋求更加科學(xué)、更加先進(jìn)的程序設(shè)計(jì)方法 2、面向?qū)ο蟮某绦蛟O(shè)計(jì)方法 192、面向?qū)ο蟮某绦蛟O(shè)計(jì)方法 u面向?qū)ο蟪绦蛟O(shè)計(jì)（ Object-Orie

10、nted Programming，OOP）方法出現(xiàn)在20世紀(jì)80年代中后期 uOOP是建立在結(jié)構(gòu)化程序設(shè)計(jì)基礎(chǔ)上的u但它不再是從功能入手，而是從對(duì)象入手u面向?qū)ο笏枷胧菍F(xiàn)實(shí)世界中客觀存在的事物即客體（如人、事物、地方等）視作為對(duì)象，而對(duì)象與對(duì)象之間的通信是通過(guò)發(fā)送消息和接收消息完成的面向?qū)ο蟮某绦蛟O(shè)計(jì)方法的核心概念 20nOOP采用的是一種結(jié)構(gòu)模擬的方法，軟件開(kāi)發(fā)過(guò)程始終圍繞建立問(wèn)題域的對(duì)象模型來(lái)進(jìn)行u用“類(lèi)”描述具有相同屬性特征的一組對(duì)象u用“封裝”將對(duì)象的屬性和行為分別用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和方法來(lái)描述，并將它們綁定在一起形成一個(gè)可供訪問(wèn)的基本邏輯單元u利用“繼承”實(shí)現(xiàn)類(lèi)與類(lèi)之間的數(shù)據(jù)和方法的

11、共享n面向?qū)ο蟮某绦蛟O(shè)計(jì)方法的核心概念u對(duì)象（Object）u類(lèi) （Class）u消息（Message）u方法（Method）（1）對(duì)象（Object） 21n面向?qū)ο蟪绦蛟O(shè)計(jì)中的對(duì)象現(xiàn)實(shí)世界中的客體在應(yīng)用程序中的具體體現(xiàn)，其中封裝了客體的屬性信息和行為方式，并用數(shù)據(jù)表示屬性，用方法表示行為方式 n對(duì)象中的數(shù)據(jù)記錄了客體的屬性狀態(tài)，方法決定了客體所能夠?qū)嵤┑牟僮餍袨楹团c其它對(duì)象進(jìn)行通信的接口方式n對(duì)象并非孤立存在，消息傳遞是對(duì)象之間相互聯(lián)系的唯一途徑。發(fā)送者發(fā)送消息，接收者通過(guò)調(diào)用相應(yīng)的方法響應(yīng)消息，這個(gè)過(guò)程被不斷地重復(fù)，從而驅(qū)動(dòng)整個(gè)程序的運(yùn)轉(zhuǎn) 對(duì)象概念的通俗示例22n現(xiàn)實(shí)世界（或者說(shuō)系統(tǒng)）是

12、由“對(duì)象”構(gòu)成的，對(duì)象之間是可相互區(qū)分的，每一對(duì)象都有唯一的標(biāo)識(shí)（如用名字作為唯一標(biāo)識(shí)）u例如一個(gè)個(gè)人n對(duì)象之間是相互獨(dú)立的，對(duì)象有自己的狀態(tài)，對(duì)象自己執(zhí)行自身的動(dòng)作而無(wú)需其他對(duì)象干預(yù)u 例如每個(gè)人都可以長(zhǎng)高、行動(dòng)、說(shuō)話 n對(duì)象可為其他對(duì)象服務(wù)，或接受其他對(duì)象服務(wù)u例如當(dāng)有人問(wèn)其身高時(shí)，他可回答身高；問(wèn)其體重時(shí)，他可回答體重；當(dāng)他想問(wèn)其他人事情時(shí)，他可向其他對(duì)象請(qǐng)求服務(wù)；. n 對(duì)象只有在接收到需服務(wù)的請(qǐng)求時(shí)，才去服務(wù)張三李四王五（2）類(lèi)（Class） 23n人類(lèi)在認(rèn)知客觀世界時(shí)，將眾多的事物歸納、劃分成一些類(lèi)，這是經(jīng)常采用的思維方法。分類(lèi)所依據(jù)的原則是抽象 n類(lèi)是具有相同屬性和行為方式的一組

13、對(duì)象的集合，或者說(shuō)，類(lèi)是指對(duì)一組具有相同特征（包括屬性、操作、方法、關(guān)系、行為）的對(duì)象的抽象描述。任何對(duì)象都是某個(gè)類(lèi)的實(shí)例 n對(duì)象是系統(tǒng)運(yùn)行時(shí)將類(lèi)作為生成對(duì)象實(shí)例的模板，通過(guò)分配私有存儲(chǔ)空間，然后對(duì)相應(yīng)的屬性賦初始值而創(chuàng)建的。這個(gè)過(guò)程在面向?qū)ο蟪绦蛟O(shè)計(jì)中稱(chēng)為“實(shí)例化”n類(lèi)與對(duì)象的關(guān)系猶如模具與鑄件之間的關(guān)系 類(lèi)與對(duì)象概念的通俗示例24n類(lèi)和對(duì)象?u有些對(duì)象具有相似的特性描述，組成一個(gè)“類(lèi)”u類(lèi)是對(duì)象的抽象或者稱(chēng)對(duì)象的“類(lèi)型”，對(duì)象是類(lèi)的實(shí)例u共性的內(nèi)容 類(lèi)（對(duì)象）名，類(lèi)（對(duì)象）的唯一標(biāo)識(shí) 類(lèi)（對(duì)象）的屬性 類(lèi)（對(duì)象）的功能或者稱(chēng)函數(shù)各自獨(dú)立運(yùn)行的類(lèi)的實(shí)例：對(duì)象同類(lèi)對(duì)象的共性形式或者說(shuō)對(duì)象的類(lèi)型

14、：類(lèi)王五張三各自獨(dú)立運(yùn)行的類(lèi)的實(shí)例：對(duì)象對(duì)象（3）消息（Message） 25n消息：一個(gè)對(duì)象要求另一個(gè)對(duì)象實(shí)施某項(xiàng)操作的請(qǐng)求 n在一條消息中，需要包含消息的接收者和要求接收者執(zhí)行某項(xiàng)操作的請(qǐng)求。但具體的操作過(guò)程由接收者自行決定，這樣可以很好地保證系統(tǒng)的模塊性n消息傳遞是對(duì)象之間相互聯(lián)系的唯一途徑。發(fā)送者發(fā)送消息，接收者通過(guò)調(diào)用相應(yīng)的方法響應(yīng)消息，這個(gè)過(guò)程被不斷地重復(fù)，從而驅(qū)動(dòng)整個(gè)程序的運(yùn)轉(zhuǎn)消息概念的通俗示例26n消息?u消息：消息是對(duì)象之間傳遞的內(nèi)容，如指示、打聽(tīng)、請(qǐng)求 .。u消息是對(duì)象之間交互的唯一的內(nèi)容u消息是 “對(duì)象.函數(shù)()”的調(diào)用和執(zhí)行張三王五請(qǐng)問(wèn).(消息)您問(wèn)的解答是(消息)Ca

15、ll 王五.回答身高()Execute 王五.回答身高() and Return “1.80m”（4）方法（Method） 27n面向?qū)ο蠹夹g(shù)中的方法：針對(duì)對(duì)象的屬性的各種操作n方法是能執(zhí)行特定功能的程序語(yǔ)句塊，即過(guò)程或函數(shù)n方法是響應(yīng)消息或事件的程序，或者說(shuō)，是類(lèi)或?qū)ο蠓庋b的函數(shù)的實(shí)現(xiàn)體，即程序段落n在OOP中，通常將一些通用的過(guò)程或函數(shù)編寫(xiě)好并封裝起來(lái)，作為方法直接提供給用戶調(diào)用面向?qū)ο蟪绦蛟O(shè)計(jì)n 面向?qū)ο蟪绦蛟O(shè)計(jì)計(jì)算機(jī)(OO)自然語(yǔ)言：?jiǎn)栴}描述OOA：需求模型OOD：設(shè)計(jì)模型OOP：編碼OOT：測(cè)試客觀世界（問(wèn)題域）OOV：驗(yàn)證面向?qū)ο蠼７椒?8程序設(shè)計(jì)語(yǔ)言要素n程序設(shè)計(jì)語(yǔ)言要素u一組

16、編程結(jié)構(gòu)原語(yǔ) Python原語(yǔ)：文字literal （如數(shù)字4.9以及字符串xyz）以及中綴運(yùn)算符infix operator（如+及/）等u語(yǔ)法 定義哪些字符串以及符號(hào)可以組合表示一定的含義 如4.9 + 4.9是正確的語(yǔ)法，4.9 4.9則不是u靜態(tài)語(yǔ)義 定義哪些語(yǔ)法正確的串具有含義 如序列4.9/xyz符合的語(yǔ)法，但是該序列的靜態(tài)語(yǔ)義是錯(cuò)誤的，因?yàn)樽址龜?shù)字沒(méi)有含義u語(yǔ)義 語(yǔ)義是語(yǔ)法正確且無(wú)靜態(tài)語(yǔ)義錯(cuò)誤的字符串所關(guān)聯(lián)的含義 編程語(yǔ)言要求每個(gè)合法的語(yǔ)句僅有唯一的含義29學(xué)習(xí)編程易犯的錯(cuò)誤n語(yǔ)法錯(cuò)誤u嚴(yán)謹(jǐn)?shù)木幊陶Z(yǔ)言均會(huì)進(jìn)行語(yǔ)法錯(cuò)誤檢查，如果含有任何語(yǔ)法錯(cuò)誤，用戶都無(wú)法執(zhí)行程序n靜態(tài)語(yǔ)義錯(cuò)誤

17、u在允許執(zhí)行程序前需要進(jìn)行很多靜態(tài)語(yǔ)義檢查。而C和Python，則僅是做少量的靜態(tài)語(yǔ)義檢查n程序的執(zhí)行并不是創(chuàng)建者的意圖u它可能崩潰，也就是停止運(yùn)行，給出示意u它可能繼續(xù)運(yùn)行，持續(xù)運(yùn)行而不停止u它也可能完成運(yùn)行，產(chǎn)生不正確的結(jié)果，甚至有可能是看似正確的結(jié)果30程序設(shè)計(jì)語(yǔ)言分類(lèi)n低級(jí)語(yǔ)言與高級(jí)語(yǔ)言u(píng)前者（如機(jī)器語(yǔ)言、匯編語(yǔ)言）采用指令以及機(jī)器級(jí)別的數(shù)據(jù)對(duì)象進(jìn)行編程，后者（如C、C+、Java、Python）采用語(yǔ)言設(shè)計(jì)者提供的抽象操作進(jìn)行編程n通用編程語(yǔ)言與特定領(lǐng)域編程語(yǔ)言u(píng)看編程語(yǔ)言的原語(yǔ)操作是廣泛可被使用還是面向特定的領(lǐng)域u如Adobe Flash可用于向網(wǎng)頁(yè)頁(yè)面添加動(dòng)畫(huà)和交互，但是我們不會(huì)

18、使用它構(gòu)建股票投資分析程序n解釋型編程語(yǔ)言與編譯型編程語(yǔ)言u(píng)用解釋型編程語(yǔ)言（如BASIC、 Python ）書(shū)寫(xiě)的程序由解釋程序?qū)υ闯绦蛑鹁浞g、逐句執(zhí)行。效率相對(duì)較低，執(zhí)行速度慢u用編譯型編程語(yǔ)言（如C、C+、Java）編寫(xiě)的程序通過(guò)編譯程序（一種翻譯程序）將源程序整個(gè)編譯成目標(biāo)程序，然后通過(guò)鏈接程序?qū)⒛繕?biāo)程序鏈接成可執(zhí)行程序，即可脫離源程序和編譯程序，單獨(dú)執(zhí)行，故效率高，執(zhí)行速度快31常用程序設(shè)計(jì)語(yǔ)言n常用程序設(shè)計(jì)語(yǔ)言u(píng)FORTRAN 科學(xué)計(jì)算語(yǔ)言，第一個(gè)高級(jí)編譯語(yǔ)言，主要用于科學(xué)計(jì)算（或稱(chēng)數(shù)值計(jì)算）uPascal 語(yǔ)言 第一個(gè)結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言， 1971年，瑞士聯(lián)邦技術(shù)學(xué)院的Nikl

19、aus Wirth（尼克勞斯沃爾斯）教授推出語(yǔ)法非常嚴(yán)謹(jǐn)，類(lèi)型豐富，層次分明，易讀易寫(xiě)適于結(jié)構(gòu)化程序設(shè)計(jì)教學(xué)uC 語(yǔ)言1972年，美國(guó)貝爾實(shí)驗(yàn)室的Kenneth Lane Thompson（肯湯普遜）和Dennis MacAlistair Ritchie（丹尼斯麥卡利斯泰爾里奇，C語(yǔ)言之父，UNIX之父）（兩人于1983年獲得圖靈獎(jiǎng)）開(kāi)發(fā)32常用程序設(shè)計(jì)語(yǔ)言（Cont.1）優(yōu)點(diǎn)兼有匯編語(yǔ)言（面向硬件）和高級(jí)語(yǔ)言（面向用戶）的優(yōu)點(diǎn)；結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言，適合于自頂向下，易開(kāi)發(fā)，易理解，易維護(hù)；適于多種操作系統(tǒng)，如Windows、DOS、UNIX等，也適用于多種機(jī)型；小型，關(guān)鍵字少，有很多輸入輸出功

20、能以及豐富的標(biāo)準(zhǔn)庫(kù)函數(shù)；有先進(jìn)的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類(lèi)型；可直接訪問(wèn)內(nèi)存地址，能進(jìn)行二進(jìn)制位的操作；與硬件無(wú)關(guān)，可移植性強(qiáng)缺點(diǎn)運(yùn)算符極為靈活，數(shù)目多、優(yōu)先次序復(fù)雜，不利于初學(xué)者；類(lèi)型檢驗(yàn)較弱、類(lèi)型轉(zhuǎn)換也較隨便，編譯時(shí)難以發(fā)現(xiàn)編程錯(cuò)誤；是面向過(guò)程的語(yǔ)言，不易代碼復(fù)用，數(shù)據(jù)安全性無(wú)保障，很難控制大規(guī)模程序的復(fù)雜性33常用程序設(shè)計(jì)語(yǔ)言（Cont.2）uC+ 語(yǔ)言1980年，Bjarne Stroustrup（本賈尼斯特勞斯特盧普）博士（1993年獲得了ACM Grace Murray Hopper獎(jiǎng)）在貝爾實(shí)驗(yàn)室開(kāi)始研究從C到C+的開(kāi)發(fā)， 1985年推出了第一個(gè)可以實(shí)現(xiàn)的C+ 1.0版本C+支持過(guò)程化程序

21、設(shè)計(jì)、數(shù)據(jù)抽象、面向?qū)ο蟪绦蛟O(shè)計(jì)、泛型程序設(shè)計(jì)等多種程序設(shè)計(jì)風(fēng)格C+ 是C語(yǔ)言的超集，很好地支持OOP思想uJava 語(yǔ)言Java是Sun Microsystems公司在1995年推出的一種編程語(yǔ)言Java是一種簡(jiǎn)單、面向?qū)ο?、平臺(tái)無(wú)關(guān)（能運(yùn)行于不同的計(jì)算機(jī)或不同的操作系統(tǒng)）、分布式、解釋型、安全可靠、性能優(yōu)異、多線程、動(dòng)態(tài)的高級(jí)程序設(shè)計(jì)語(yǔ)言，特別適合在網(wǎng)絡(luò)環(huán)境下的編程使用34常用程序設(shè)計(jì)語(yǔ)言（Cont.3）uC# 語(yǔ)言 C#（讀作C sharp）是一種為生成在.NET Framework上運(yùn)行的多種應(yīng)用程序而設(shè)計(jì)的面向?qū)ο蟮木幊陶Z(yǔ)言簡(jiǎn)單、功能強(qiáng)大、類(lèi)型安全語(yǔ)法表現(xiàn)力強(qiáng)，不到90個(gè)關(guān)鍵字，簡(jiǎn)單

22、易學(xué)。語(yǔ)法方面簡(jiǎn)化了C+的諸多復(fù)雜性，同時(shí)提供了很多強(qiáng)大的功能支持泛型方法和類(lèi)型，從而提供了更出色的類(lèi)型安全和性能u標(biāo)記式語(yǔ)言HTMLHTML（Hypertext Markup Language ）即超文本標(biāo)記語(yǔ)言是WWW（World Wide Web ）的描述語(yǔ)言。由Tim Berners-lee提出HTML是由HTML命令組成的描述性文本，HTML命令可以說(shuō)明文字、圖形、動(dòng)畫(huà)、聲音、表格、鏈接等353.1.3 Python語(yǔ)言簡(jiǎn)介n通用的編程語(yǔ)言，可有效構(gòu)建絕大多數(shù)程序，而無(wú)需對(duì)計(jì)算機(jī)硬件進(jìn)行直接的訪問(wèn)n較弱的靜態(tài)語(yǔ)義檢查功能，對(duì)于高可靠性限制要求的程序、由較多人員長(zhǎng)期維護(hù)和構(gòu)建的程序而言

23、，它并不是最佳的選擇n解釋型語(yǔ)言，對(duì)于編程新生而言，Python提供的實(shí)時(shí)反饋非常有幫助，同時(shí)Python提供大量庫(kù)以及擴(kuò)展功能，便于使用36 什么是Python？37nPython是一種解釋型的、面向?qū)ο蟮?、帶有?dòng)態(tài)語(yǔ)義的高級(jí)程序設(shè)計(jì)語(yǔ)言u(píng)Python程序，通常稱(chēng)為腳本script，是定義以及命令行的序列u盡管可能Python不像C或C+編譯型語(yǔ)言一樣快，但它簡(jiǎn)單易學(xué)，編寫(xiě)的程序清晰易懂，特別適于入門(mén)者學(xué)習(xí)nPython簡(jiǎn)單但功能強(qiáng)大u廣泛用于系統(tǒng)管理工作（是許多Linux發(fā)行版的重要組成部分）uNASA在它的幾個(gè)系統(tǒng)中既用Python開(kāi)發(fā)，又將其作為腳本語(yǔ)言u(píng)Yahoo!使用它管理討論組u

24、Google用它實(shí)現(xiàn)Web爬蟲(chóng)和搜索引擎中的許多組件uPython也正應(yīng)用于計(jì)算機(jī)游戲和生物信息等多個(gè)領(lǐng)域1、Python面世n 1989年，由Guido van Rossum（吉多范羅蘇姆）在阿姆斯特丹完成，第一個(gè)公開(kāi)版發(fā)行于1991年n Guido為了打發(fā)圣誕節(jié)的無(wú)趣，決心開(kāi)發(fā)一個(gè)新的腳本解釋程序，作為ABC語(yǔ)言的一種繼承u使用Python作為語(yǔ)言的名字，因?yàn)镚uido是英國(guó)幽默劇團(tuán)Monty Python飛行馬戲團(tuán)的fansuABC是由Guido參加設(shè)計(jì)的一種教學(xué)語(yǔ)言，非常優(yōu)美和強(qiáng)大，是專(zhuān)門(mén)為非專(zhuān)業(yè)程序員設(shè)計(jì)的Guido van Rossum38n目前，Guido在Google，主要從事

25、GAE/Python3.x方面的研究Python的版本nPython 2.0于2000年10月16日發(fā)布，主要是實(shí)現(xiàn)了完整的垃圾回收，并且支持UnicodenPython 3.0于2008年12月3日發(fā)布，此版不完全兼容之前的Python源代碼n目前使用最廣泛的版本是Python 2.7n最新的版本是Python 3.3.5（2014.3.13） 39Python哲學(xué)翻譯與解釋n翻譯與解釋uPython之禪 by Tim Petersu優(yōu)美勝于丑陋（Python 以編寫(xiě)優(yōu)美的代碼為目標(biāo)）u明了勝于晦澀（優(yōu)美的代碼應(yīng)當(dāng)是明了的，命名規(guī)范，風(fēng)格相似）u簡(jiǎn)潔勝于復(fù)雜（優(yōu)美的代碼應(yīng)當(dāng)是簡(jiǎn)潔的，不要有復(fù)

26、雜的內(nèi)部實(shí)現(xiàn)）u復(fù)雜勝于凌亂（如果復(fù)雜不可避免，那代碼間也不能有難懂的關(guān)系，要保持接口簡(jiǎn)潔）u扁平勝于嵌套（優(yōu)美的代碼應(yīng)當(dāng)是扁平的，不能有太多的嵌套）u間隔勝于緊湊（優(yōu)美的代碼有適當(dāng)?shù)拈g隔，不要奢望一行代碼解決問(wèn)題）u可讀性很重要（優(yōu)美的代碼是可讀的）u即便假借特例的實(shí)用性之名，也不可違背這些規(guī)則（這些規(guī)則至高無(wú)上）41翻譯與解釋?zhuān)–ont.）u不要包容所有錯(cuò)誤，除非你確定需要這樣做（精準(zhǔn)地捕獲異常，不寫(xiě) except:pass 風(fēng)格的代碼）u當(dāng)存在多種可能，不要嘗試去猜測(cè)u而是盡量找一種，最好是唯一一種明顯的解決方案（如果不確定，就用窮舉法）u雖然這并不容易，因?yàn)槟悴皇?Python 之父（

27、這里的 Dutch 是指 Guido ）u做也許好過(guò)不做，但不假思索就動(dòng)手還不如不做（動(dòng)手之前要細(xì)思量）u如果你無(wú)法向人描述你的方案，那肯定不是一個(gè)好方案；反之亦然（方案測(cè)評(píng)標(biāo)準(zhǔn)）u命名空間是一種絕妙的理念，我們應(yīng)當(dāng)多加利用（倡導(dǎo)與號(hào)召）422、Python的特色n容易上手u提供交互式環(huán)境u語(yǔ)法簡(jiǎn)潔 高級(jí)數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)潔地表達(dá)復(fù)雜的操作 語(yǔ)句組織依賴(lài)于縮進(jìn) 參數(shù)或變量不需要聲明n火力強(qiáng)大u易學(xué)但不簡(jiǎn)單，從桌面程序，到網(wǎng)絡(luò)互聯(lián)、圖形處理、科學(xué)計(jì)算、實(shí)時(shí)控制，到處都有Python的身影u跨平臺(tái)（Windows, Linux，Unix, Macintosh）u面向?qū)ο?3Python的特色（Cont.1

28、）n快速開(kāi)發(fā)uPython內(nèi)建的高層次數(shù)據(jù)結(jié)構(gòu)，以及動(dòng)態(tài)類(lèi)型和動(dòng)態(tài)綁定，非常適合于快速應(yīng)用開(kāi)發(fā)uPython語(yǔ)法強(qiáng)調(diào)可讀性，降低了程序的維護(hù)費(fèi)用uPython支持模塊和包，并鼓勵(lì)程序模塊化和代碼重用n高效運(yùn)行uPython可以編譯執(zhí)行，其運(yùn)行效率接近C語(yǔ)言的運(yùn)行速度，相同功能的代碼運(yùn)行速度約為C的90%，而同時(shí)Java的運(yùn)行速度卻只能達(dá)到C的50%44Python的特色（Cont.2）n豐富的庫(kù)uPython 標(biāo)準(zhǔn)庫(kù)已經(jīng)很龐大。可幫你處理各種工作：正則表達(dá)式、文檔生成、單元測(cè)試、線程、數(shù)據(jù)庫(kù)、網(wǎng)頁(yè)瀏覽器、CGI、 FTP、電子郵件、XML、XML-RPC、HTML、WAV文件、密碼系統(tǒng)、GUI

29、（圖形用戶界面）、Tk和其他與系統(tǒng)有關(guān)的操作uPython開(kāi)源、免費(fèi)，在“百花齊放”式發(fā)展中，已經(jīng)產(chǎn)生大量的高質(zhì)量庫(kù)，如wxPython、Twisted 、Pygame、 matplotlib 、scipy等45Python的特色（Cont.3）n可擴(kuò)展、可嵌入u如果你需要你的一段關(guān)鍵代碼運(yùn)行得更快或者希望某些算法不公開(kāi)，你可以把你的部分程序用C或C+編寫(xiě)，然后在你的Python程序中使用它們u可以把Python程序嵌入你的C/C+程序中，從而向你的程序用戶提供腳本功能n解釋性 uPython程序不需要編譯成二進(jìn)制代碼，可以直接從源代碼運(yùn)行程序。使得Python程序更加易于移植46Python

30、解釋器nPython是一門(mén)跨平臺(tái)的腳本語(yǔ)言，Python規(guī)定了一個(gè)Python語(yǔ)法規(guī)則，實(shí)現(xiàn)Python語(yǔ)法的解釋程序稱(chēng)為Python解釋器 uCPython（ClassicPython，最原始Python的實(shí)現(xiàn)，需要區(qū)別于其他實(shí)現(xiàn)的時(shí)候才以CPython稱(chēng)呼；或用C語(yǔ)言實(shí)現(xiàn)的的Python）uJython （Java語(yǔ)言實(shí)現(xiàn)的Python ）uIronpython (面向.NET和ECMA CLI的Python實(shí)現(xiàn) )uPyPy (使用Python語(yǔ)言寫(xiě)的Python )uZhpy（支持繁/簡(jiǎn)中文語(yǔ)句編寫(xiě)程序的Python語(yǔ)言） 473、誰(shuí)在用Python？典型幾個(gè)國(guó)外公司48誰(shuí)在用Pyth

31、on？（Cont.1）典型幾個(gè)國(guó)內(nèi)公司49誰(shuí)在用Python？（Cont.2）n豆瓣n新浪SAE （Sina App Engine）u開(kāi)始支持Python了n搜狐郵箱u基于web.pyn游戲公司504、開(kāi)發(fā)環(huán)境nIDLEuPython內(nèi)置IDE（Integrated Development Enviroment），隨Python安裝包提供 nPyCharmu由著名的JetBrains公司開(kāi)發(fā)，帶有一整套可以幫助用戶在使用Python語(yǔ)言開(kāi)發(fā)時(shí)提高其效率的工 具，比如調(diào)試、語(yǔ)法高亮、Project管理、代碼跳轉(zhuǎn)、智能提示、自動(dòng)完成、單元測(cè)試、版本控制。此外，該IDE提供了一些高級(jí)功能，以用于支持

32、Django框架下的專(zhuān)業(yè)Web開(kāi)發(fā)，推薦！nUlipadu功能較全的自由軟件，基于wxPython；作者是中國(guó)Python高手limodou，推薦！開(kāi)發(fā)環(huán)境（Cont.）nEclipse+pydev u 收費(fèi)的nEricu基于PyQt的自由軟件，功能強(qiáng)大。全名是：The Eric Python IDE nPyScripteru使用Delphi開(kāi)發(fā)的輕量級(jí)的開(kāi)源Python IDE n其它編輯器uUltraEdit ，notepad+，editplus525、Python安裝n官網(wǎng)/下載核心upython-2.7.6.msi 推薦！upython-3.3.

33、5.msin常用第三方庫(kù)下載uPython package index (pypi): /pypiunumpy、 scipy 科學(xué)計(jì)算umatplotlib 二維、三維畫(huà)圖upygame 游戲開(kāi)發(fā)uwxpython 圖形用戶界面開(kāi)發(fā)udjango web開(kāi)發(fā)uscikit-learn 數(shù)據(jù)挖掘 53 6、Python程序及結(jié)構(gòu)n一般來(lái)講，一個(gè)Python程序包括了多個(gè)模塊文件。程序是作為一個(gè)主體的、頂層的文件來(lái)構(gòu)造，配合有多個(gè)支持的文件n在Python中，頂層文件包含了程序的主要控制流程，是啟動(dòng)應(yīng)用的文件n模塊文件就是工具的庫(kù)，這些工具用來(lái)收集頂層文

34、件使用的組件。頂層文件使用了模塊文件中定義的工具，而模塊又使用了其他模塊所定義的工具n模塊文件通常在運(yùn)行時(shí)不需直接做任何事情，然后，它們定義的工具會(huì)在其他文件中使用。在Python中，一個(gè)文件通過(guò)導(dǎo)入一個(gè)模塊來(lái)獲得這個(gè)模塊定義的工具的訪問(wèn)權(quán)，這些工具被認(rèn)作是模塊的屬性54 Python程序及結(jié)構(gòu)（Cont.）55n一個(gè)程序是一個(gè)模塊的系統(tǒng)，它有一個(gè)頂層腳本文件a.py（啟動(dòng)后可運(yùn)行的程序）以及多個(gè)模塊文件b.py、c.py（用來(lái)導(dǎo)入工具庫(kù)）n頂層腳本和模塊都包含了自己編寫(xiě)的Python語(yǔ)句。Python標(biāo)準(zhǔn)庫(kù)提供了一系列的預(yù)先編寫(xiě)好的模塊563.2 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)u3.2.1 數(shù)據(jù)類(lèi)型及其本質(zhì)

35、數(shù)據(jù)類(lèi)型及其本質(zhì)u3.2.2 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)u3.2.3 抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型用計(jì)算機(jī)求解問(wèn)題的過(guò)程57n編寫(xiě)解決實(shí)際問(wèn)題的程序的一般過(guò)程u 如何用數(shù)據(jù)形式描述問(wèn)題?即由問(wèn)題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型；u 問(wèn)題所涉及的數(shù)據(jù)量大小及數(shù)據(jù)之間的關(guān)系；u 如何在計(jì)算機(jī)中存儲(chǔ)數(shù)據(jù)及體現(xiàn)數(shù)據(jù)之間的關(guān)系? u 處理問(wèn)題時(shí)需要對(duì)數(shù)據(jù)作何種運(yùn)算?u 所編寫(xiě)的程序的性能是否良好?n上面所列舉的問(wèn)題基本上由數(shù)據(jù)結(jié)構(gòu)這門(mén)課程來(lái)回答3.2.1 數(shù)據(jù)類(lèi)型及其本質(zhì)n什么是數(shù)據(jù)？u在計(jì)算機(jī)世界中，數(shù)據(jù)是所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號(hào)（數(shù)值、字符等）的集合u是計(jì)算機(jī)操作的對(duì)象的總稱(chēng)u是計(jì)算機(jī)處理的信息的某

36、種特定的符號(hào)表示形式n計(jì)算機(jī)中的數(shù)據(jù)是來(lái)自于客觀世界的各種各樣的信息，不僅包含整型、實(shí)型等數(shù)值型數(shù)據(jù)，還包括字符、圖形、圖像、聲音、視頻等非數(shù)值型數(shù)據(jù)n這些數(shù)據(jù)，都是以二進(jìn)制數(shù)的形式存儲(chǔ)在計(jì)算機(jī)中的n計(jì)算機(jī)是怎樣對(duì)這些性質(zhì)、形式各異的數(shù)據(jù)進(jìn)行計(jì)算或處理的呢？58 數(shù)據(jù)類(lèi)型n計(jì)算機(jī)計(jì)算或處理的數(shù)據(jù)，來(lái)源于我們?cè)趯?duì)客觀世界各個(gè)領(lǐng)域里客觀事物的一種認(rèn)知基礎(chǔ)上的觀察和抽象n因此，人們將分類(lèi)的思想引入編程語(yǔ)言，便產(chǎn)生了“數(shù)據(jù)類(lèi)型（Data Type）”的概念u數(shù)據(jù)類(lèi)型是一個(gè)值的集合以及定義在此集合上的一組操作的總稱(chēng)u基本思想：把某種語(yǔ)言所處理的對(duì)象按其屬性的不同，分為不同的子集，對(duì)不同的子集規(guī)定不同的運(yùn)

37、算操作59n人類(lèi)在認(rèn)識(shí)客觀世界的過(guò)程中，采用了分類(lèi)的方法u如：將世界分為生物和非生物兩大類(lèi)，生物又細(xì)分為動(dòng)物、植物、微生物n分類(lèi)是科學(xué)研究的基本方法和途徑，是我們認(rèn)識(shí)世界和改造世界的銳利武器60C語(yǔ)言的數(shù)據(jù)類(lèi)型C語(yǔ)言的數(shù)據(jù)類(lèi)型數(shù)值類(lèi)型基本類(lèi)型指針類(lèi)型（pointer）字符類(lèi)型（char）結(jié)構(gòu)（struct）整型實(shí)型聯(lián)合（union）文件（file）數(shù)組（array）枚舉類(lèi)型（enum）短整型（short）整型（int）長(zhǎng)整型（long）單精度（float）雙精度（double）空類(lèi)型（void）構(gòu)造類(lèi)型 數(shù)據(jù)類(lèi)型的本質(zhì)（1）數(shù)據(jù)類(lèi)型確定了值的范圍u不同的數(shù)據(jù)類(lèi)型有不同的取值范圍u如整型（16

38、bit）的取值范圍是-215（215-1），即-32768+32767；字符型的取值范圍是：-128+128u數(shù)據(jù)若超出指定范圍，計(jì)算就會(huì)出問(wèn)題（溢出）61（2）數(shù)據(jù)類(lèi)型確定了值的操作，不同類(lèi)型有不同的操作u如：整型有取余運(yùn)算，實(shí)型則沒(méi)有u即使是同一種操作，對(duì)不同的類(lèi)型可能內(nèi)涵不同。如：1+2就是對(duì)應(yīng)的二進(jìn)制數(shù)相加；1+2.0先進(jìn)行類(lèi)型轉(zhuǎn)換，然后才進(jìn)行對(duì)階、尾數(shù)相加、規(guī)格化 數(shù)據(jù)類(lèi)型的本質(zhì)（Cont.）（3）數(shù)據(jù)類(lèi)型確定了值存儲(chǔ)空間的大小u不同數(shù)據(jù)類(lèi)型的數(shù)據(jù)占據(jù)的存儲(chǔ)空間大小不同u如整型數(shù)據(jù)通常占據(jù)2Byte；字符型數(shù)據(jù)占據(jù)1Byte；單精度實(shí)型數(shù)據(jù)占據(jù)4Byte；雙精度實(shí)型數(shù)據(jù)占據(jù)8Byte

39、u數(shù)據(jù)若超出指定范圍，計(jì)算就會(huì)出問(wèn)題（溢出）62（4）數(shù)據(jù)類(lèi)型確定了值的存儲(chǔ)方式u不同數(shù)據(jù)類(lèi)型的數(shù)據(jù)在內(nèi)存里的存儲(chǔ)方式不同u如整型與實(shí)型值的存儲(chǔ)方式截然不同u如十進(jìn)制數(shù)12 整型數(shù)據(jù)：0000 0000 0000 1100（2個(gè)Byte） 實(shí)型數(shù)據(jù)：0100 0001 0100 0000 0000 0000 0000 0000（4個(gè)Byte） 在編程語(yǔ)言中為什么引入數(shù)據(jù)類(lèi)型？（1）有助于程序設(shè)計(jì)的簡(jiǎn)明性和數(shù)據(jù)的可靠性u(píng)引入數(shù)據(jù)類(lèi)型，明確了變量的取值范圍和其上允許的基本操作，可以防止許多錯(cuò)誤的發(fā)生u編譯系統(tǒng)通過(guò)靜態(tài)類(lèi)型檢查，可以發(fā)現(xiàn)程序中與數(shù)據(jù)類(lèi)型有關(guān)的錯(cuò)誤u也有利于程序員編寫(xiě)程序，理解和調(diào)試程

40、序63（2）有助于數(shù)據(jù)的存儲(chǔ)管理u不同數(shù)據(jù)類(lèi)型的數(shù)據(jù)占據(jù)的存儲(chǔ)空間大小不同u對(duì)數(shù)據(jù)根據(jù)需要事先定義數(shù)據(jù)類(lèi)型，則可以節(jié)約寶貴的存儲(chǔ)資源（3）有利于提高程序運(yùn)行效率u程序在編譯時(shí)對(duì)數(shù)據(jù)的類(lèi)型信息和操作進(jìn)行檢查，可有效避免程序在運(yùn)行時(shí)操作越界和類(lèi)型錯(cuò)誤，提高了程序運(yùn)行的整體效率3.2.2 數(shù)據(jù)結(jié)構(gòu)64n計(jì)算機(jī)要處理的數(shù)據(jù)并不是雜亂無(wú)章的，它們一定存在內(nèi)在的聯(lián)系n只有弄清楚數(shù)據(jù)之間的本質(zhì)的聯(lián)系，才能使用計(jì)算機(jī)對(duì)大量的數(shù)據(jù)進(jìn)行有效的處理【例例3.2】某電信公司的市話用戶信息表。序號(hào)用戶名電話號(hào)碼用戶住址街道名門(mén)牌號(hào)00001萬(wàn)方林3800235北京西路165900002吳金平3800667北京西路209

41、900003王 冬5700123瑤湖大道198700004王三5700567瑤湖大道200800005江 凡8800129學(xué)府大道5035【例3.2】必須弄清楚的3個(gè)問(wèn)題65n使用計(jì)算機(jī)處理用戶信息表中的數(shù)據(jù)時(shí)，必須弄清楚下面3個(gè)問(wèn)題u這些數(shù)據(jù)之間有什么樣的內(nèi)在聯(lián)系？數(shù)據(jù)的邏輯結(jié)構(gòu)u數(shù)據(jù)在計(jì)算機(jī)中怎樣存儲(chǔ)？數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) u對(duì)數(shù)據(jù)進(jìn)行處理時(shí)需要對(duì)數(shù)據(jù)作何種運(yùn)算? 數(shù)據(jù)的運(yùn)算集合n對(duì)于待處理的數(shù)據(jù)，只有分析清楚這3個(gè)問(wèn)題，才能進(jìn)行有效的處理！ 1、什么是數(shù)據(jù)結(jié)構(gòu)？1、什么是數(shù)據(jù)結(jié)構(gòu)？u有一個(gè)特性相同的數(shù)據(jù)元素的集合，如果在數(shù)據(jù)元素之間存在一種或多種特定的關(guān)系，則稱(chēng)之為一個(gè)數(shù)據(jù)結(jié)構(gòu)u數(shù)據(jù)結(jié)構(gòu)就是指

42、按一定的邏輯結(jié)構(gòu)組成的一批數(shù)據(jù)，使用某種存儲(chǔ)結(jié)構(gòu)將這批數(shù)據(jù)存儲(chǔ)于計(jì)算機(jī)中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算集合u數(shù)據(jù)結(jié)構(gòu)是相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合u數(shù)據(jù)結(jié)構(gòu)課程討論計(jì)算機(jī)系統(tǒng)中數(shù)據(jù)的組織形式及其相互關(guān)系66數(shù)據(jù)結(jié)構(gòu)概覽67數(shù)據(jù)結(jié)構(gòu)中的術(shù)語(yǔ)n數(shù)據(jù)結(jié)構(gòu)中的術(shù)語(yǔ)u數(shù)據(jù)項(xiàng)（Data Item ）: 是數(shù)據(jù)的具有獨(dú)立含義的不可分割的最小標(biāo)識(shí)單位，數(shù)據(jù)項(xiàng)是對(duì)客觀事物某一方面特性的數(shù)據(jù)描述 如【例3.2】表中的序號(hào)、用戶名、電話號(hào)碼等u數(shù)據(jù)元素（Data Element ）：是數(shù)據(jù)的基本單位，通常作為一個(gè)整體考慮和進(jìn)行處理（又稱(chēng)結(jié)點(diǎn)、記錄）。一個(gè)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成 如【例3.2】表中的

43、包含序號(hào)、用戶名、電話號(hào)碼等具體數(shù)值的每一行數(shù)據(jù)u 數(shù)據(jù)對(duì)象（Data Object）：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。如【例3.2】表中的所有數(shù)據(jù)元素68【例3.2】中的數(shù)據(jù)項(xiàng)和數(shù)據(jù)元素69序號(hào)用戶名電話號(hào)碼用戶住址街道名門(mén)牌號(hào)00001萬(wàn)方林3800235北京西路165900002吳金平3800667北京西路209900003王 冬5700123瑤湖大道198700004王三5700567瑤湖大道200800005江 凡8800129學(xué)府大道5035u這里序號(hào)、用戶名、電話號(hào)碼等項(xiàng)稱(chēng)為基本項(xiàng)，它是有獨(dú)立意義的最小標(biāo)識(shí)單位，而用戶住址稱(chēng)為組合項(xiàng)，組合項(xiàng)是由一個(gè)或多個(gè)基本項(xiàng)或組合

44、項(xiàng)組成，是有獨(dú)立意義的標(biāo)識(shí)單位u每一行稱(chēng)為一個(gè)結(jié)點(diǎn)（或記錄）記錄），每一個(gè)組合項(xiàng)稱(chēng)為一個(gè)字段1個(gè)數(shù)據(jù)項(xiàng)1個(gè)數(shù)據(jù)元素5個(gè)數(shù)據(jù)元素4個(gè)數(shù)據(jù)項(xiàng)【例3.2】的數(shù)據(jù)結(jié)構(gòu)70n數(shù)據(jù)的邏輯結(jié)構(gòu)u除最前和最后的兩個(gè)結(jié)點(diǎn)之外，表中所有其它的結(jié)點(diǎn)都有且僅有一個(gè)與它相鄰、位于它之前的一個(gè)結(jié)點(diǎn)，也有且僅有一個(gè)與它相鄰、位于它之后的一個(gè)結(jié)點(diǎn)u這些就是用戶信息表的邏輯結(jié)構(gòu)n數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) u將用戶信息表中的所有結(jié)點(diǎn)存入計(jì)算機(jī)時(shí)，若使用C語(yǔ)言設(shè)計(jì)程序，常用一個(gè)結(jié)構(gòu)數(shù)組來(lái)存儲(chǔ)整個(gè)用戶信息表，每一個(gè)數(shù)組元素是一個(gè)結(jié)構(gòu)，它對(duì)應(yīng)于用戶信息表中的一個(gè)結(jié)點(diǎn)u數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式稱(chēng)為存儲(chǔ)結(jié)構(gòu)【例3.2】的數(shù)據(jù)結(jié)構(gòu)（Cont. )71

45、n數(shù)據(jù)的運(yùn)算集合u用戶信息表可以有刪除一個(gè)用戶、增加一個(gè)用戶和查找某個(gè)用戶等操作。應(yīng)該明確指明這些操作的含義。比如刪除操作，是刪除序號(hào)為5的用戶還是刪除用戶名為王三的用戶是應(yīng)該明確定義的，如果需要可以定義兩個(gè)不同的刪除操作u為一批數(shù)據(jù)定義的所有運(yùn)算（或稱(chēng)操作）構(gòu)成一個(gè)運(yùn)算（操作）集合 數(shù)據(jù)結(jié)構(gòu)的例子線性表結(jié)構(gòu)72【例例3.3】電話號(hào)碼查詢(xún)系統(tǒng)。u設(shè)有一個(gè)電話號(hào)碼薄，它記錄了N個(gè)人的名字和其相應(yīng)的電話號(hào)碼，假定按如下形式安排：(a1, b1)，(a2, b2)，(an, bn)，其中ai, bi(i=1，2n) 分別表示某人的名字和電話號(hào)碼u本問(wèn)題是一種典型的線性表問(wèn)題。數(shù)據(jù)與數(shù)據(jù)成簡(jiǎn)單的一對(duì)一

46、的線性關(guān)系姓名電話號(hào)碼陳四線性表結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的例子樹(shù)形結(jié)構(gòu)73【例例3.4】磁盤(pán)目錄文件系統(tǒng)。u磁盤(pán)根目錄下有很多子目錄及文件，每個(gè)子目錄里又可以包含多個(gè)子目錄及文件，但每個(gè)子目錄只有一個(gè)父目錄，依此類(lèi)推u本問(wèn)題是一種典型的樹(shù)形結(jié)構(gòu)問(wèn)題，數(shù)據(jù)與數(shù)據(jù)成一對(duì)多的關(guān)系，是一種典型的非線性關(guān)系結(jié)構(gòu)樹(shù)形結(jié)構(gòu)計(jì)算機(jī)中的目錄結(jié)構(gòu)74HBCDEFGAHGFECDBA樹(shù)形結(jié)構(gòu)特點(diǎn)結(jié)點(diǎn)間具有分層次的連接關(guān)系數(shù)據(jù)結(jié)構(gòu)的例子網(wǎng)狀結(jié)構(gòu)75【例例3.5】交通網(wǎng)絡(luò)圖。u 從一個(gè)地方到另外一個(gè)地方可以有多條路徑。本問(wèn)題是一種典型的網(wǎng)狀結(jié)構(gòu)（圖狀結(jié)構(gòu)）問(wèn)題，數(shù)據(jù)與數(shù)據(jù)成多對(duì)多

47、的關(guān)系，是一種非線性關(guān)系結(jié)構(gòu)佛山惠州廣州中山東莞深圳珠海網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)76n數(shù)據(jù)結(jié)構(gòu)包括“邏輯結(jié)構(gòu)” 和“存儲(chǔ)結(jié)構(gòu)”兩個(gè)方面（層次）u 數(shù)據(jù)元素之間的關(guān)系可以是元素之間代表某種含義的自然關(guān)系，也可以是為處理問(wèn)題方便而人為定義的關(guān)系，這種自然或人為定義的 “關(guān)系”稱(chēng)為數(shù)據(jù)元素之間的邏輯關(guān)系，相應(yīng)的結(jié)構(gòu)稱(chēng)為邏輯結(jié)構(gòu)u邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素之間的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系來(lái)表示（形式定義）u存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)元素在計(jì)算機(jī)系統(tǒng)中的存儲(chǔ)方式，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示和實(shí)現(xiàn)體現(xiàn)了數(shù)據(jù)元素的物理空間關(guān)系，故又稱(chēng)為物理結(jié)構(gòu) 2、數(shù)據(jù)的邏輯結(jié)構(gòu)77 2、數(shù)

48、據(jù)的邏輯結(jié)構(gòu)n從關(guān)系或結(jié)構(gòu)分，數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下4種基本類(lèi)型線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)（圖狀結(jié)構(gòu)）集合結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類(lèi)型外，別無(wú)其它關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)示例78學(xué)號(hào)姓名語(yǔ)文數(shù)學(xué)C語(yǔ)言14011001張三85549214011002李四92846414011003王五877473. 邏輯結(jié)構(gòu)的形式定義79n數(shù)據(jù)邏輯結(jié)構(gòu)是數(shù)據(jù)元素之間邏輯關(guān)系的描述n有兩種表示方法：描述法和圖示法（1）描述法u數(shù)據(jù)結(jié)構(gòu)的形式定義是一個(gè)二元組： Data-Structure=(D，S)

49、其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集u數(shù)據(jù)元素之間的關(guān)系：一般抽象為前驅(qū)與后繼關(guān)系 即表明結(jié)構(gòu)中，一個(gè)元素的前一個(gè)元素是誰(shuí)，它的后一個(gè)元素又是誰(shuí) （2）圖示法80（2）圖示法u圖形要素：結(jié)點(diǎn)和有向線段結(jié)點(diǎn)：表示一個(gè)數(shù)據(jù)元素，一般以方形框代表 不管多么復(fù)雜的結(jié)點(diǎn)，都看作是一個(gè)結(jié)點(diǎn)有向線段：表示元素之間的關(guān)系 K iK hK jKi的前驅(qū)Ki的后繼箭尾指向的結(jié)點(diǎn)是前驅(qū)箭頭指向的結(jié)點(diǎn)是后繼【例3.6】邏輯結(jié)構(gòu)的表示方法81【例例3.6】邏輯結(jié)構(gòu)的兩種表示方法。u設(shè)某數(shù)據(jù)邏輯結(jié)構(gòu)B=（K，R） K=k1, k2, , k9 R= ， u 畫(huà)出該邏輯結(jié)構(gòu)的圖示，并確定哪些是起點(diǎn)，哪些是終點(diǎn)。

50、它是什么類(lèi)型的邏輯結(jié)構(gòu)？【例3.6】邏輯結(jié)構(gòu)的圖示法82K1K3K4K7K5K6K2K8K9網(wǎng)狀結(jié)構(gòu)833、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)n數(shù)據(jù)的邏輯結(jié)構(gòu)只是描述了數(shù)據(jù)元素之間的邏輯關(guān)系，是獨(dú)立于計(jì)算機(jī)的，它與數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式無(wú)關(guān)n如果將數(shù)據(jù)在計(jì)算機(jī)中無(wú)規(guī)律地存儲(chǔ)，則數(shù)據(jù)元素在內(nèi)存中難以迅速找到，將影響數(shù)據(jù)處理的結(jié)果和速度！n試想一下，如果一本英漢字典中的單詞是隨意編排的，這本字典誰(shuí)會(huì)用！n對(duì)于一個(gè)數(shù)據(jù)結(jié)構(gòu)B=（K，R），必須建立從結(jié)點(diǎn)集合到計(jì)算機(jī)某個(gè)存儲(chǔ)區(qū)域M的一個(gè)映象，這個(gè)映象要直接或間接地表達(dá)結(jié)點(diǎn)之間的關(guān)系Rn數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)方式稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)了解即可3、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)84數(shù)據(jù)存儲(chǔ)結(jié)

51、構(gòu)n數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)包括數(shù)據(jù)元素的存儲(chǔ)和數(shù)據(jù)元素之間的關(guān)系的表示n元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法：順序表示和非順序表示。由此得出兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和非順序存儲(chǔ)結(jié)構(gòu)（鏈接存儲(chǔ)、索引存儲(chǔ)、散列存儲(chǔ)）n一種數(shù)據(jù)結(jié)構(gòu)可以根據(jù)需要采用多種不同的存儲(chǔ)結(jié)構(gòu)n數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)不同，解決問(wèn)題的方法就有所不同，數(shù)據(jù)處理的效率也是不同的n存儲(chǔ)器的特點(diǎn)：由地址連續(xù)的單元構(gòu)成線性關(guān)系85（1）順序存儲(chǔ)結(jié)構(gòu)n順序存儲(chǔ)結(jié)構(gòu)：將邏輯上相鄰的元素存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元中。通常借助于數(shù)組來(lái)實(shí)現(xiàn)n通常用于存儲(chǔ)具有線性結(jié)構(gòu)的數(shù)據(jù)。則數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置正好反映了數(shù)據(jù)元素之間的邏輯結(jié)

52、構(gòu)（關(guān)系）數(shù)據(jù)邏輯結(jié)構(gòu)與物理結(jié)構(gòu)完全統(tǒng)一n連續(xù)存放的數(shù)據(jù)元素在內(nèi)存中容易找到K1K2K3K4邏輯結(jié)構(gòu)030003010302030303040305030603070308K1K2K3K4物理結(jié)構(gòu)物理結(jié)構(gòu)（1）順序存儲(chǔ)結(jié)構(gòu)86（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)n鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：對(duì)邏輯上相鄰的元素不要求其物理地址相鄰，元素之間的邏輯關(guān)系通過(guò)附加的指針字段來(lái)表示。通常借助于指針類(lèi)型實(shí)現(xiàn)（pointer）n元素在內(nèi)存中不一定連續(xù)存放元素指針 結(jié)點(diǎn)元素指針（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)87鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)指針域：存放下一個(gè)結(jié)點(diǎn)的地址存儲(chǔ)單元的地址即物理地址n鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)u每個(gè)結(jié)點(diǎn)由兩部分組成：一部分存放數(shù)據(jù)，另一部分存儲(chǔ)指向

53、前件或后件結(jié)點(diǎn)的指針域u邏輯上相鄰的結(jié)點(diǎn)物理上不必相鄰u數(shù)據(jù)運(yùn)算（插入和刪除等）靈活88（3）索引存儲(chǔ)結(jié)構(gòu)n索引存儲(chǔ)結(jié)構(gòu)：給存儲(chǔ)在內(nèi)存中的數(shù)據(jù)元素建立一個(gè)索引表，表中存儲(chǔ)一串指針，每個(gè)指針指向存放在內(nèi)存中的一個(gè)元素（3）索引存儲(chǔ)結(jié)構(gòu)030003010302030303040305030603070308K1K2K3K41234索引表索引號(hào) 指針n通過(guò)查找索引表找到數(shù)據(jù)元素在內(nèi)存中的位置n元素可以離散存放89（4）散列存儲(chǔ)結(jié)構(gòu)n散列存儲(chǔ)結(jié)構(gòu)：根據(jù)數(shù)據(jù)元素的“特點(diǎn)（關(guān)鍵字）”，按照特定的計(jì)算公式（哈希函數(shù)），計(jì)算出對(duì)應(yīng)的值，然后把數(shù)據(jù)元素存放在以該值（哈希結(jié)果）為存儲(chǔ)地址的存儲(chǔ)單元中n查找時(shí)根據(jù)其

54、“特點(diǎn)”就可以計(jì)算出存儲(chǔ)地址n例如欲將十進(jìn)制數(shù)34和52存放在內(nèi)存中，選取哈希函數(shù)為所存數(shù)據(jù)元素mod 10 取余數(shù)作為存儲(chǔ)地址。34 mod 10余4，52 mod 10余2，則34和52分別存入存儲(chǔ)單元4和2中散列存儲(chǔ)結(jié)構(gòu)示意圖（4）散列存儲(chǔ)結(jié)構(gòu)聯(lián)想：通過(guò)書(shū)的名字就能確定書(shū)的位置 數(shù)據(jù)結(jié)構(gòu)的三個(gè)組成部分90n邏輯結(jié)構(gòu)： 數(shù)據(jù)元素之間邏輯關(guān)系的描述 D_S=（D，S）n存儲(chǔ)結(jié)構(gòu)： 數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)及其邏輯關(guān)系的表現(xiàn)稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)或物理結(jié)構(gòu)n數(shù)據(jù)操作： 對(duì)數(shù)據(jù)要進(jìn)行的運(yùn)算邏輯結(jié)構(gòu)與所采用的存儲(chǔ)結(jié)構(gòu)線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖狀結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)復(fù)合存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)邏輯

55、結(jié)構(gòu)的分類(lèi)91n數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類(lèi)數(shù)據(jù)的邏輯結(jié)構(gòu)非線性結(jié)構(gòu)集合圖狀結(jié)構(gòu)有向圖無(wú)向圖樹(shù)形結(jié)構(gòu)一般樹(shù)二叉樹(shù)線性結(jié)構(gòu)一般線性表線性表推廣廣義表數(shù)組串受限線性表?xiàng)：完?duì)列數(shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)系圖 邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的比較92n數(shù)據(jù)邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的比較1、存儲(chǔ)結(jié)構(gòu)是元素在內(nèi)存中的存儲(chǔ)方式，與元素間固有的邏輯關(guān)系是相對(duì)獨(dú)立的兩個(gè)問(wèn)題u存儲(chǔ)結(jié)構(gòu)著眼于結(jié)點(diǎn)在內(nèi)存中的定位2、簡(jiǎn)單的邏輯結(jié)構(gòu)可能與存儲(chǔ)結(jié)構(gòu)一致u例：線性邏輯結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)3、利用存儲(chǔ)結(jié)構(gòu)在內(nèi)存中找到一個(gè)結(jié)點(diǎn)，而為什么要找這個(gè)結(jié)點(diǎn)卻由元素間的邏輯關(guān)系決定4、邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是一個(gè)問(wèn)題密不可分的兩個(gè)方面u任何一個(gè)算法的設(shè)

56、計(jì)取決于選定的數(shù)據(jù)邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴(lài)于采用的存儲(chǔ)結(jié)構(gòu) 4、數(shù)據(jù)結(jié)構(gòu)的運(yùn)算934、數(shù)據(jù)結(jié)構(gòu)的運(yùn)算u建立（Create）一個(gè)數(shù)據(jù)結(jié)構(gòu)u消除（Destroy）一個(gè)數(shù)據(jù)結(jié)構(gòu)u訪問(wèn)（Access）一個(gè)數(shù)據(jù)結(jié)構(gòu)u插入（Insert）：在一個(gè)數(shù)據(jù)結(jié)構(gòu)中增加一個(gè)新的結(jié)點(diǎn)u刪除（Delete）：從一個(gè)數(shù)據(jù)結(jié)構(gòu)中刪除一個(gè)結(jié)點(diǎn)u查找（Search）（檢索）：在一個(gè)數(shù)據(jù)結(jié)構(gòu)中查找滿足條件的結(jié)點(diǎn)u修改（Modify）：對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)（中的數(shù)據(jù)元素）進(jìn)行修改u排序（Sort）：將一個(gè)數(shù)據(jù)結(jié)構(gòu)中所有結(jié)點(diǎn)按某種順序重新排列u輸出（Output）：將一個(gè)結(jié)構(gòu)中所有結(jié)點(diǎn)的值打印、輸出3.2.3 抽象數(shù)據(jù)類(lèi)型n利用計(jì)算機(jī)解

57、決實(shí)際問(wèn)題的重要過(guò)程之一便是“抽象”u在程序設(shè)計(jì)中，數(shù)據(jù)和運(yùn)算是兩個(gè)不可缺少的因素。所有的程序設(shè)計(jì)活動(dòng)都是圍繞著數(shù)據(jù)和其上的相關(guān)運(yùn)算而進(jìn)行的u從機(jī)器指令、匯編語(yǔ)言中的數(shù)據(jù)沒(méi)有類(lèi)型的概念，到現(xiàn)在的面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言中抽象數(shù)據(jù)類(lèi)型概念的出現(xiàn)，程序設(shè)計(jì)中的數(shù)據(jù)經(jīng)歷了一次次抽象，數(shù)據(jù)的抽象經(jīng)歷了三個(gè)發(fā)展階段94 從無(wú)類(lèi)型的二進(jìn)制數(shù)到基本數(shù)據(jù)類(lèi)型的產(chǎn)生 從基本數(shù)據(jù)類(lèi)型到用戶自定義類(lèi)型的產(chǎn)生 從用戶自定義類(lèi)型到抽象數(shù)據(jù)類(lèi)型的出現(xiàn) 什么是抽象數(shù)據(jù)類(lèi)型？n抽象數(shù)據(jù)類(lèi)型（ Abstract Data Type ，ADT ）u抽象數(shù)據(jù)類(lèi)型是與表示無(wú)關(guān)的數(shù)據(jù)類(lèi)型，是一個(gè)數(shù)據(jù)模型及定義在該模型上的一組運(yùn)算uADT的

58、定義僅是一組邏輯特性描述， 與其在計(jì)算機(jī)內(nèi)的表示和實(shí)現(xiàn)無(wú)關(guān)。因此，不論ADT的內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù)學(xué)特性不變，都不影響其外部使用u對(duì)一個(gè)抽象數(shù)據(jù)類(lèi)型進(jìn)行定義時(shí)，必須給出它的名字及各運(yùn)算的運(yùn)算符名，即函數(shù)名，并且規(guī)定這些函數(shù)的參數(shù)性質(zhì)u為什么要有抽象數(shù)據(jù)類(lèi)型？一旦定義了一個(gè)抽象數(shù)據(jù)類(lèi)型及具體實(shí)現(xiàn)，程序設(shè)計(jì)中就可以像使用基本數(shù)據(jù)類(lèi)型那樣，十分方便地使用抽象數(shù)據(jù)類(lèi)型95抽象數(shù)據(jù)類(lèi)型的形式化定義n抽象數(shù)據(jù)類(lèi)型的形式化定義uADT的形式化定義是三元組：ADT=(D，S，P)其中：D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集96n抽象數(shù)據(jù)類(lèi)型是數(shù)據(jù)類(lèi)型的擴(kuò)展和抽象u數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)對(duì)象D及其關(guān)

59、系S）u定義在數(shù)據(jù)結(jié)構(gòu)上的基本操作和算法（P）n抽象數(shù)據(jù)類(lèi)型需要通過(guò)固有數(shù)據(jù)類(lèi)型（高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類(lèi)型）來(lái)實(shí)現(xiàn)抽象數(shù)據(jù)類(lèi)型的一般定義n抽象數(shù)據(jù)類(lèi)型的一般定義形式97ADT 數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系： 基本操作： ADT u其中數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽代碼描述u基本操作的定義是：()初始條件： 操作結(jié)果： 抽象數(shù)據(jù)類(lèi)型的兩個(gè)重要特征98n抽象數(shù)據(jù)類(lèi)型的兩個(gè)重要特征u數(shù)據(jù)抽象：用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征，其所能完成的功能以及它與外部用戶的接口（即外界使用它的方法）u數(shù)據(jù)封裝：將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。如復(fù)數(shù)定義【例3.

60、7】定義抽象數(shù)據(jù)類(lèi)型“復(fù)數(shù)”99ADT Complex 數(shù)據(jù)對(duì)象： De1,e2e1,e2RealSet 數(shù)據(jù)關(guān)系： R1 | e1是復(fù)數(shù)的實(shí)數(shù)部分, | e2 是復(fù)數(shù)的虛數(shù)部分 【例例3.7】定義抽象數(shù)據(jù)類(lèi)型“復(fù)數(shù)”。基本操作：AssignComplex( &Z, v1, v2 )操作結(jié)果：構(gòu)造復(fù)數(shù) Z，其實(shí)部和虛部分別被賦以參數(shù) v1 和 v2 的值?！纠?.7】（Cont.）100DestroyComplex( &Z)操作結(jié)果：復(fù)數(shù)Z被銷(xiāo)毀。 GetReal( Z, &realPart )初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。GetImag( Z, &Imag