新編數(shù)據(jù)結(jié)構(gòu)

PAGEPAGE301(shùjùjiéɡòu)概論特別(tèbié)是從事計算機(jī)系統(tǒng)開發(fā)的專業(yè)人員，必須切實(shí)掌握數(shù)據(jù)結(jié)構(gòu)的知數(shù)據(jù)結(jié)構(gòu)難學(xué)嗎？其實(shí)不難，只要仔細(xì)讀書，認(rèn)真思考，就能切實(shí)掌握各種結(jié)構(gòu)的本質(zhì)和它們之間的關(guān)系。有人說數(shù)據(jù)結(jié)構(gòu)太難學(xué)，實(shí)際上是指動手編寫程序難。這個問題是無法回避(huíbì)的，沒有這方面的訓(xùn)練，將來就無法勝任系統(tǒng)開發(fā)的工作。動手能力的提高，需要日常無數(shù)次練習(xí)和總結(jié)。與學(xué)習(xí)任何一門課程一樣，踏踏實(shí)實(shí)地做題和實(shí)驗(yàn)，不斷提高自己的編程能力和算法設(shè)計能力。數(shù)據(jù)結(jié)構(gòu)(shùjùjiéɡòu)的概念數(shù)據(jù)結(jié)構(gòu)(shùjùjiéɡòu)舉例眾所周知，無論是使用計算機(jī)進(jìn)行工程和科學(xué)計算，還是使用計算機(jī)做工業(yè)控制或信息管理，都屬于數(shù)據(jù)處理的范疇。那么，如何在計算機(jī)中組織，存儲，傳遞數(shù)據(jù)，就成為一個必須解決的問題。下面看幾個例子。【例1】在一個學(xué)生選課系統(tǒng)中，有兩個數(shù)據(jù)實(shí)體（現(xiàn)實(shí)世界中的事物），多學(xué)生記錄，它們按照每個學(xué)生學(xué)號遞增的次序，順序存放在“學(xué)生”表格1.1所示?！皩W(xué)生”表格 “課程”表格學(xué)號姓名性別籍貫出生年月課程編號課程名學(xué)時1 98131劉激揚(yáng)男北京1979.121024002程序設(shè)計基礎(chǔ)642 98164衣春生男青島1979.072024010匯編語言483 98165盧聲凱男天津1981.023024016計算機(jī)原理644 98182袁秋慧女廣州1980.104024020數(shù)據(jù)結(jié)構(gòu)645 98203林德康男上海1980.055024021微機(jī)技術(shù)646 98224洪偉男太原1981.016024024操作系統(tǒng)487 98236熊南燕女蘇州1980.037024026數(shù)據(jù)庫原理488 98297宮力男北京1981.019 98310蔡曉莉女昆明1981.021098318陳健男杭州1979.121.1學(xué)生選課系統(tǒng)中的兩個數(shù)據(jù)實(shí)體在“學(xué)生(xuésheng)”表格中，各個學(xué)生(xuésheng)記錄順序排列，形成一個學(xué)生記錄的線性序列，每個記錄在序列中的位置有先后次序，它們之間形成一種線性關(guān)系?！罢n程(kèchéng)”表格(biǎogé)中的情況完全相同。【2】在學(xué)生選課系統(tǒng)中，一個學(xué)生可以選修多門課程，一門(yīmén)課程可以被多個學(xué)生選修，這在“學(xué)生”和“課程”實(shí)體之間形成多對多的關(guān)單，包含有如下的信息：（學(xué)號，課程編號，成績，時間）。此時，在“學(xué)生”實(shí)體、“課程”實(shí)體和“選課”實(shí)體間形成如圖1.2所示的關(guān)系。這是一種網(wǎng)狀關(guān)系。學(xué)生對選課，課程對選課都是一對多的關(guān)系。學(xué)生（學(xué)號，姓名，性別，籍貫）學(xué)生（學(xué)號，姓名，性別，籍貫）1m課程（課程編號，課程名，學(xué)分，課1n選課單（學(xué)號，課程編號，成績，時間）選課單（學(xué)號，課程編號，成績，時間）圖1.2學(xué)生選課系統(tǒng)中實(shí)體構(gòu)成的網(wǎng)狀關(guān)系【3UNIX1.3所示。這是一個層次結(jié)構(gòu)：在此系統(tǒng)結(jié)構(gòu)圖中，頂層結(jié)點(diǎn)代表整個系統(tǒng)，用根目錄“/”表示；它的下一層結(jié)點(diǎn)代表系統(tǒng)的各個子系統(tǒng)，即根的子目錄，如“/bin”、、“/user”等；再下一層結(jié)點(diǎn)代表更小的子目錄，如“/user/yin”、“/bin/ds”，如此類推，直到底層，即為文件，如“/user/yin/queue.cpp”。/(root)bin lib user mathdssw yindengzhulist.cpp stack.cpp tree.cpp圖1.3UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖綜上所述，在應(yīng)用程序中涉及到各種各樣的數(shù)據(jù)，為了存儲它們，組織它統(tǒng)。數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)人們在日常生活中會遇到各種信息，如用語言交流的思想(sīxiǎng)，銀行與商店的商業(yè)交易、在戰(zhàn)爭中用于傳遞命令的旗語等。這些信息必須轉(zhuǎn)換成數(shù)據(jù)才能在計算機(jī)中進(jìn)行處理。因此，可以給數(shù)據(jù)下一個定義：數(shù)據(jù)(shùjù)（data）有能輸入到計算機(jī)中并被計算機(jī)程序識別(shíbié)和處理的符號的集合。數(shù)據(jù)大致可分為兩類，一類是數(shù)值性數(shù)據(jù)，包括整數(shù)、浮點(diǎn)數(shù)、復(fù)數(shù)、雙精度數(shù)等，主要(zhǔyào)用于工程和科學(xué)計算，以及商業(yè)事務(wù)處理；另一類是非數(shù)值數(shù)據(jù)，主要包括字符和字符串，以及文字、圖形、圖像、語音等的數(shù)據(jù)。數(shù)據(jù)的基本(jīběn)單位是數(shù)據(jù)元素（dataelement）。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(xiàng)（dataitem），組成，它是一個數(shù)據(jù)整體中相對獨(dú)立的單位。例如，對于一個學(xué)籍管理文件來說，每個學(xué)生記錄就是它的數(shù)據(jù)元素；對于一個字符串來說，每個字符就是它的數(shù)據(jù)元素；對于一個數(shù)組來說，每一個數(shù)組成份就是它的數(shù)據(jù)元素。在數(shù)據(jù)元素中的數(shù)據(jù)項(xiàng)可以分為兩種，一種叫做初等項(xiàng)，如學(xué)生的性別、籍貫等，這些數(shù)據(jù)項(xiàng)是在數(shù)據(jù)處理時是不能再分割的最小單位；另一種叫做組合項(xiàng)，如學(xué)生的成績，它可以再劃分為物理、化學(xué)等更小的項(xiàng)。通常，在解決實(shí)際應(yīng)用問題時把每個學(xué)生記錄當(dāng)作一個基本單位進(jìn)行訪問和處理。在數(shù)據(jù)處理中所涉及的數(shù)據(jù)元素之間都不會是孤立的，在它們之間都存在nn個網(wǎng)站連1.4(a)所示，這樣，在所有網(wǎng)站之間形成一種樹形關(guān)系；反之，要求1.4(b)所示。① ② ① ②⑤ ③ ⑤ ③④ ④網(wǎng)站之間的網(wǎng)狀關(guān)系 (b)網(wǎng)站之間的樹狀關(guān)系圖1.4n個網(wǎng)站之間的連通關(guān)系由此可以引出數(shù)據(jù)結(jié)構(gòu)的定義：數(shù)據(jù)結(jié)構(gòu)由某一數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關(guān)系組成。記為：Data_Structure={D,R}其中，D是某一數(shù)據(jù)元素的集合，R限集合。注意，有關(guān)數(shù)據(jù)結(jié)構(gòu)的討論主要涉及數(shù)據(jù)元素之間的關(guān)系，不涉及數(shù)據(jù)元素本身的內(nèi)容。關(guān)于數(shù)據(jù)元素的內(nèi)容，在系統(tǒng)開發(fā)時考慮。數(shù)據(jù)結(jié)構(gòu)(shùjùjiéɡòu)的分類依據(jù)數(shù)據(jù)元素之間關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)分為(fēnwéi)兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。1、線性結(jié)構(gòu)(jiégòu)（linearStructure）線性結(jié)構(gòu)(jiégòu)也稱為線性表，在這種結(jié)構(gòu)(jiégòu)中所有數(shù)據(jù)元素都按1.5所示。對于線性結(jié)構(gòu)類中每一數(shù)據(jù)元素binbindevetclibuse圖1.5線性結(jié)構(gòu)中各數(shù)據(jù)成員之間的線性關(guān)系根據(jù)對線性結(jié)構(gòu)中數(shù)據(jù)元素存取方法的不同，又可分為直接存取結(jié)構(gòu)、順序存取結(jié)構(gòu)和字典結(jié)構(gòu)。對于直接存取結(jié)構(gòu)，可以直接存取某一指定項(xiàng)而不須先訪問其前驅(qū)。像數(shù)組、文件都屬于這一類。我們可以按給定下標(biāo)直接存取數(shù)組中某一數(shù)組元素；可以按記錄號直接檢索記錄集合或文件中的某一記錄。對于順序存取結(jié)構(gòu)，只能從序列中第一個數(shù)據(jù)元素起，按序逐個訪問直到指定的元素。像一些限制存取位置在表的一端或兩端的表（如棧、隊(duì)列和優(yōu)先級隊(duì)列等）就是這種情況。字典與數(shù)組有類似之處，但數(shù)組是通過整數(shù)下標(biāo)進(jìn)行索引，而字典是通過關(guān)鍵碼（key）進(jìn)行索引。我們設(shè)定數(shù)據(jù)元素中某一數(shù)據(jù)項(xiàng)或某一組合數(shù)據(jù)項(xiàng)為關(guān)鍵碼，通過關(guān)鍵碼來識別記錄。例如，對于學(xué)生記錄，可設(shè)定學(xué)生的學(xué)號為關(guān)鍵碼，用它來識別是哪一位學(xué)生的記錄。2、非線性結(jié)構(gòu)（nonlinearstructure）在非線性結(jié)構(gòu)中各個數(shù)據(jù)元素不再保持在一個線性序列中，每個數(shù)據(jù)元素可能與零個或多個其他數(shù)據(jù)元素發(fā)生聯(lián)系。根據(jù)關(guān)系的不同，可分為層次結(jié)構(gòu)和群結(jié)構(gòu)。層次結(jié)構(gòu)（hierarchicalstructure）是按層次劃分的數(shù)據(jù)元素的集合，指定1.6所示。112345 6 7 8 9 1011 12圖1.6樹形結(jié)構(gòu)k叉樹（k叉的有序樹）可以是空樹，并因此(yīncǐ)推定“k叉樹不是(bùshi)樹”。本書則對樹與k叉樹不加區(qū)分，在概念上將(shàngjiàng)它們統(tǒng)一起來。群結(jié)構(gòu)（Groupstructure）中所有元素之間無順序關(guān)系。集合(jíhé)就是一種群結(jié)構(gòu)，在集合中沒有重復(fù)的元素。另一種群結(jié)構(gòu)就是圖結(jié)構(gòu)，如圖1.7(a)所示。它是由圖的頂點(diǎn)集合和連接頂點(diǎn)的邊集合組成。還有一種圖的特殊形式，即網(wǎng)絡(luò)結(jié)構(gòu)。它給每條邊賦予(fùyǔ)一個權(quán)值，這個權(quán)值指明了在遍1.7(b)表示兩城市之間的距離2 1

16221 19 56 3 11 6 6 333 1465 4 5 418圖結(jié)構(gòu) (b)網(wǎng)絡(luò)結(jié)構(gòu)圖1.7群結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容機(jī)硬件和計算機(jī)軟件之間的一門計算機(jī)科學(xué)與技術(shù)專業(yè)的核心課程，是高級程序設(shè)計語應(yīng)用于信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)以及各種工程技術(shù)領(lǐng)域。社會的發(fā)展，要求使用計算機(jī)解決更復(fù)雜的問題，而更復(fù)雜的問題需要更大的計算關(guān)設(shè)計（包括數(shù)據(jù)設(shè)計、體系結(jié)構(gòu)設(shè)計、接口設(shè)計和過程設(shè)計）標(biāo)時，選用復(fù)雜的數(shù)據(jù)表示來改進(jìn)這個程序也是沒有道理的。當(dāng)為解決某一問題而選擇數(shù)據(jù)結(jié)構(gòu)時，應(yīng)當(dāng)執(zhí)行以下幾個步驟：1、分析問題，確定算法遇到的資源限制（內(nèi)外存空間限制和執(zhí)行時間限制）；2、確定必須支持的基本運(yùn)算，度量每個運(yùn)算所受到的資源限制?；具\(yùn)算包括向數(shù)據(jù)結(jié)構(gòu)插入一個新數(shù)據(jù)項(xiàng)，從數(shù)據(jù)結(jié)構(gòu)中刪除一個數(shù)據(jù)項(xiàng)和搜索指定的數(shù)據(jù)項(xiàng)；3、選擇最接近這些資源開銷的數(shù)據(jù)結(jié)構(gòu)。根據(jù)這三個步驟選擇數(shù)據(jù)結(jié)構(gòu)，實(shí)際上貫徹了一種以數(shù)據(jù)為中心的設(shè)計觀點(diǎn)。為了構(gòu)造出好的數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)，必須考慮數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)的評價。因此，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容包括三個層次的五個“要素”，如表1.1所示。表1.1數(shù)據(jù)結(jié)構(gòu)(shùjùjiéɡòu)課程內(nèi)容體系層次層次方面數(shù)據(jù)表示數(shù)據(jù)處理抽象邏輯結(jié)構(gòu)存儲結(jié)構(gòu)基本運(yùn)算算法不同數(shù)據(jù)結(jié)構(gòu)的比較及算法分析數(shù)據(jù)(shùjù)結(jié)構(gòu)的核心技術(shù)是分解與抽象。通過分解可以劃分出數(shù)據(jù)的層次（數(shù)據(jù)―數(shù)據(jù)(shùjù)元素―數(shù)據(jù)項(xiàng)）；再通過抽象，舍棄數(shù)據(jù)元素的具體內(nèi)容，就得到數(shù)據(jù)的邏輯(shàngshù)兩個方面的結(jié)合將問題變換為數(shù)據(jù)結(jié)構(gòu)。這是一個從具體（即具體問題）到抽象（即數(shù)據(jù)結(jié)構(gòu)）得到存儲結(jié)構(gòu)和實(shí)現(xiàn)運(yùn)算，從而完成設(shè)計任務(wù)。這是一個從抽象（即數(shù)據(jù)結(jié)構(gòu)）到具體（即具體實(shí)現(xiàn)）的過程。熟練地掌握這兩個過程是數(shù)據(jù)結(jié)構(gòu)課程在專業(yè)技能培養(yǎng)方面的基本目標(biāo)。數(shù)據(jù)的邏輯(luójí)結(jié)構(gòu)，亦簡稱數(shù)據(jù)結(jié)構(gòu)，是指從解決問題的需要出發(fā)，為實(shí)現(xiàn)必要的功能所建立的數(shù)據(jù)結(jié)構(gòu)，它屬于用戶的視圖，是面向問題功能建立，數(shù)據(jù)的物理結(jié)構(gòu)根據(jù)問題所要求的響應(yīng)速度、處理時間、修改時間、存儲空間和單位時間的處理量等建立，是邏輯數(shù)據(jù)的存儲映像。通常在課程中討論數(shù)據(jù)結(jié)構(gòu)，既要討論各種在解決問題時可能遇到的典型的邏輯結(jié)構(gòu)（在本書下文中簡稱為數(shù)據(jù)結(jié)構(gòu)），還要討論這些邏輯結(jié)構(gòu)的存儲映像（在本書下文中簡稱為存儲結(jié)構(gòu)），此外還要討論這種數(shù)據(jù)結(jié)構(gòu)的相關(guān)操作（基本運(yùn)算）及其實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)可以用以下4種基本的存儲方法得到：1、順序存儲方法（SequentialStorage）該方法把邏輯上相鄰的元素存放到物理位置上相鄰的存儲單元中，數(shù)據(jù)元素之間的邏輯關(guān)系由存儲單元的鄰接位置關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)，通常，順序存儲結(jié)構(gòu)可借助程序語言中的一維數(shù)組來描述。2、鏈接存儲方法（LinkedStorage）該方法不要求邏輯上相鄰的元素在物理位置上也相鄰，元素之間的邏輯關(guān)系由附加的指針指示。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)，通常，鏈?zhǔn)酱鎯Y(jié)構(gòu)要借助程序語言中的指針類型來描述。3、索引存儲方法（IndexedStorage）該方法在存儲元素信息的同時，還建立附加的索引表。索引表中每一項(xiàng)稱為索引項(xiàng)，索引項(xiàng)的一般形式是：（關(guān)鍵碼，地址）。關(guān)鍵碼是能夠唯一標(biāo)識一個結(jié)點(diǎn)（即元素）的那些數(shù)據(jù)項(xiàng)。若每個結(jié)點(diǎn)在索引表中都有一個索引項(xiàng)，則該索引表稱為稠密索引（DenseIndex）；若一組相鄰的結(jié)點(diǎn)在索引表中只有一個索引項(xiàng)，則該索引表稱為稀疏索引（SparseIndex）。稠密索引中索引項(xiàng)中的地址指示結(jié)點(diǎn)所在的物理位置，稀疏索引中索引項(xiàng)中的地址指示一組相鄰結(jié)點(diǎn)的起始存儲位置。4、散列存儲方法（HashingStorage）該方法的處理方式是根據(jù)結(jié)點(diǎn)的關(guān)鍵碼通過一個函數(shù)計算直接(zhíjiē)得到該結(jié)點(diǎn)的存儲地址。4種基本的存儲方法既可以單獨(dú)使用，也可以組合起來對數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲映像。同一種邏輯(luójí)結(jié)構(gòu)采用不同的存儲方法，可以得到不同的存儲結(jié)構(gòu)（表示）源要求而定，主要考慮運(yùn)算的時間和空間要求以及算法的簡單性。數(shù)據(jù)結(jié)構(gòu)(shùjùjiéɡòu)的抽象形式數(shù)據(jù)類型類型(lèixíng)是一組值的集合。例如，布爾（boolean）true和false2個字節(jié)，則整數(shù)表示范圍在215～215-1，即-32768～327674個字節(jié)，則整數(shù)(zhěngshù)表示范圍在-231～231-1，即-2147483648～2147483647之間。類型可分為原子類型和結(jié)構(gòu)類型兩種。原子類型中的每個數(shù)據(jù)（即簡單數(shù)據(jù)）都是無法再分割的整體，如一個整數(shù)、浮點(diǎn)數(shù)、字符、指針、枚舉量等都是無法再分割的整體，所以它們所屬的類型均為原子類型。結(jié)構(gòu)類型由原子類型按照一定的規(guī)則構(gòu)造而成，如一個銀行賬戶一般包括姓名、地址、賬號、余額等原子類型。結(jié)構(gòu)類型還可以包含結(jié)構(gòu)類型，如一個學(xué)生的學(xué)籍卡片是一個結(jié)構(gòu)類型，它包含的一個數(shù)據(jù)成份（家庭成員）又是結(jié)構(gòu)類型。所以一種結(jié)構(gòu)類型中的數(shù)據(jù)（即結(jié)構(gòu)數(shù)據(jù)）可以分解為若干個簡單數(shù)據(jù)或結(jié)構(gòu)數(shù)據(jù)，每個結(jié)構(gòu)數(shù)據(jù)仍可再分。數(shù)據(jù)類型是指一種類型，以及定義于這個值集合上的一組操作的總稱。例如在高級程序設(shè)計語言中已實(shí)現(xiàn)了的，或非高級語言直接支持的數(shù)據(jù)結(jié)構(gòu)即為數(shù)據(jù)類型。在程序設(shè)計語言中，一個變量的數(shù)據(jù)類型不僅規(guī)定了這個變量的取值范圍，而且定義了這個變量可用的操作。例如，一個變量K定義為整型，則它可能的取值范圍是-32768～32767（對于32位系統(tǒng)則為-2147483648～2147483647），可用的操作有雙目運(yùn)算符+、-、*、/、%，單目運(yùn)算符+、-，關(guān)系運(yùn)算符<、>、<=、.>=、、!=，賦值運(yùn)算符=CPascal語言組合類型（如數(shù)組型、構(gòu)造型、文件型等）的規(guī)則，程序員可以利用這些規(guī)正確地進(jìn)行相關(guān)計算的有效工具。C語言中對一個數(shù)據(jù)表（DataList）1.1。程序1.1數(shù)據(jù)表（DataList）的構(gòu)造型類型定義#defineListSize100 //表空間的大小，可根據(jù)實(shí)際情況決定typedefintDataType; //表中元素(yuánsù)的數(shù)據(jù)類型，inttypedefstruct{DataTypedata[ListSize];intlength;}DataList;

//存放(cúnfàng)表元素的向量//當(dāng)前(dāngqián)的表長度注意，數(shù)據(jù)類型的邏輯(luójí)概念與其在計算機(jī)程序中的實(shí)現(xiàn)有很重要的區(qū)別。例如，線性表數(shù)據(jù)類型有兩種傳統(tǒng)的實(shí)現(xiàn)方式：基于數(shù)組的順序(shùnxù)表示和基于鏈表的鏈接表示?？梢圆捎面湵砘驍?shù)組作為線性表數(shù)據(jù)類型的存儲表示。但是，“數(shù)組（array）”類型，又可以指一種實(shí)現(xiàn)方式。在計算機(jī)程序設(shè)計中，“數(shù)組”常用來指一塊連續(xù)的內(nèi)存空間，每一個內(nèi)存空間存儲一個固定長度的數(shù)據(jù)項(xiàng)，從這個意義上講，數(shù)組是一個存儲結(jié)構(gòu)。然而，數(shù)組也能夠表示一種由一組結(jié)構(gòu)相同的數(shù)據(jù)項(xiàng)組成的邏輯數(shù)據(jù)類型，每一個數(shù)據(jù)項(xiàng)由一個特定的索引號（即數(shù)組中的下標(biāo)）來標(biāo)識。從這個意義來講，可以采用多種不同的方法來實(shí)現(xiàn)數(shù)組。(ADTs:AbstractDataTypes)在軟件設(shè)計時，常常提到“抽象”和“信息隱蔽”。那么，什么是抽象呢？抽象的本質(zhì)就是抽取反映問題本質(zhì)的東西，忽略非本質(zhì)的細(xì)節(jié)。對于數(shù)數(shù)據(jù)的存儲和運(yùn)算，而在匯編語言中則給出了各種數(shù)據(jù)的自然表示，如15.51.3E10、10等，它們是二進(jìn)制數(shù)據(jù)的抽象，使用者在編程時可以直接使用它據(jù)抽象的層次為設(shè)計者提供了有力的手段，使得設(shè)計者可以從抽象的概念出發(fā)，從整體上進(jìn)行考慮，然后自頂向下，逐步展開，最后得到所需的結(jié)果。抽象數(shù)據(jù)類型通常是指由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型，是將數(shù)據(jù)結(jié)構(gòu)作為一個軟件構(gòu)件的實(shí)現(xiàn)。抽象數(shù)據(jù)類型由基本的數(shù)據(jù)類型組成，并包括一組相關(guān)的服務(wù)（或稱操作）。抽象數(shù)據(jù)類型有些類似于Pascal語言中的記錄（record）類型和C語言中的構(gòu)造（struct）類型，但它增加了相關(guān)的服務(wù)。下面給出自然數(shù)（NaturalNumber）的抽象數(shù)據(jù)類型定義。在C++語言中，使用關(guān)鍵字struct或class定義抽象數(shù)據(jù)類型。例如，自然數(shù)的抽象數(shù)據(jù)類型定義如程序1.2所示。程序1.2自然數(shù)的抽象數(shù)據(jù)類型classNaturalNumber/*objects:自然數(shù)是整數(shù)的有序子集合,它開始于0,結(jié)束于機(jī)器能表示的最大整數(shù)MAXINT。*/{function:對于所有的x,y∈NaturalNumber,+、-、<、==、=等都是可用的服務(wù)。Zero():NaturalNumberIsZero(x):Boolean

返回0;ifx0返回Trueelse返回False;Add(x,y)NaturalNumber ifx+yMAXINT返回xy;else返回MAXINT;Equal(x,y):Boolean if(x==y)返回1;else返回0;Successor(x):NaturalNumber if(x==MAXINT)返回x;elsex+1;Subtract(x,y):NaturalNumber} //NaturalNumber

if(x<y)返回0; else返回x-y;對于一個其數(shù)據(jù)元素完全相同的數(shù)據(jù)類型，如果(rúguǒ)給它賦予不同的語義，即定義具有不同功能的一組，則可形成不同的抽象數(shù)據(jù)類型。例如隊(duì)列和優(yōu)先級隊(duì)列，它們可能都是相同的順序表結(jié)構(gòu)，但其語義不同，隊(duì)列是先進(jìn)先出，優(yōu)先級隊(duì)列是優(yōu)先級高的先出，具有各不相同的服務(wù)，是不同的抽象數(shù)據(jù)類型。為了保證抽象數(shù)據(jù)類型中每一個(yīɡè)操作的正確性，在操作中需要給出前置條件（IF）和后置(hòuzhì)條件（…THEN…ELSE）。前者(qiánzhě)給C++中使用斷言（assert.h）實(shí)現(xiàn)這種機(jī)制(jīzhì)assert(x0)x0則可繼續(xù)執(zhí)行后續(xù)的程序，否則將調(diào)用通用庫“stdlib.h”中的函數(shù)abort，打印出錯行號和文件名，終止程序的執(zhí)行。后續(xù)章節(jié)將引用這種機(jī)制。抽象數(shù)據(jù)類型的特征是使用與實(shí)現(xiàn)分離，實(shí)行封裝和信息隱蔽。就是說，在抽象數(shù)據(jù)類型設(shè)計時，把類型的聲明與其實(shí)現(xiàn)分離開來。首先根據(jù)問題的要求，定義該抽象數(shù)據(jù)類型需要包含哪些信息，并根據(jù)功能確定公共接口中的服務(wù)，使用者可以使用公共接口中的服務(wù)對該抽象數(shù)據(jù)類型進(jìn)行操作。另一方面，抽象數(shù)據(jù)類型的物理實(shí)現(xiàn)作為私有部分封裝在其實(shí)現(xiàn)模塊內(nèi)，使用者不能看到，也不能直接操作該類型所存儲的數(shù)據(jù)，只能通過界面中的服務(wù)來訪問這些數(shù)據(jù)。這樣做的好處是嚴(yán)格區(qū)分了抽象數(shù)據(jù)類型的兩個不同的視圖。從使用者的角度來看，只要了解該抽象數(shù)據(jù)類型的規(guī)格說明，就可以利用以在開發(fā)過程中抓住重點(diǎn)，集中精力考慮如何解決應(yīng)用問題，使問題得到簡慮。從實(shí)現(xiàn)者的角度來看，把抽象數(shù)據(jù)類型的物理實(shí)現(xiàn)封裝起來，有利于編錯誤，其傳播范圍不致于影響其他模塊；如果為了提高效率希望改進(jìn)數(shù)據(jù)結(jié)不變，其他所有使用該抽象數(shù)據(jù)類型的程序都可以不變。從而大大提高系統(tǒng)的穩(wěn)定性。作為(zuòwéi)ADTC++類面向?qū)ο蟮母拍?gàiniàn)什么(shénme)是面向?qū)ο?？CoadYourdon給出如下(rúxià)對象＋類＋繼承(jìchéng)＋消息通信。定義中的對象是指在應(yīng)用問題中出現(xiàn)的各種實(shí)體、事件、規(guī)格說明等，它是由一組屬性值和在這組值上的一組服務(wù)（或稱操作）構(gòu)成。其中，屬性值確定了對象的狀態(tài)。例如，對于一個顯示在計算機(jī)屏幕上的矩形，它作為一個幾何對象，由左上角坐標(biāo)、右下角坐標(biāo)、邊線顏色、內(nèi)部顏色等屬性值確定了它的位置、顏色等狀態(tài)。我們可以通過對象的服務(wù)來改變該對象的屬性值，即對象的狀態(tài)。例如，矩形可以有一個服務(wù)move(x,y)，使用這個服務(wù)可以把矩形移到由整數(shù)x,y指定的新位置上。矩形還可以有兩個服務(wù)setEdgeColor(c)和setInterColor(c)，用以改變矩形的邊和內(nèi)部的著色。在面向?qū)ο蠓椒ㄖ?，把具有相同屬性和服?wù)的對象歸到同一個類(class)，而把一個類中的每一個對象稱為該類的一個實(shí)例(instance)。它們具有相同的服務(wù)。例如，在計算機(jī)屏幕上有大大小小若干個矩形，分別表示各種按鈕和窗幕上顯示的位置、大小、顏色各不相同，所以它們的屬性值也各不相同。引入繼承機(jī)制是面向?qū)ο蠓椒ǖ淖钣刑厣姆矫妗＠?，在繪圖系統(tǒng)二次曲線又可分為橢圓、圓、拋物線、雙曲線。我們以“多邊形”類為基類(baseclass)，建立它的派生類(derivedclass)，如“四邊形”類、“三角形”類復(fù)用?；愑址Q父類、超類或泛化類，派生類又稱為子類或特化類。要求另一個類的對象執(zhí)行某個服務(wù)的指令，指明要求哪一個對象執(zhí)行這個服傳遞，執(zhí)行一系列服務(wù)達(dá)到的。面向?qū)ο箝_發(fā)方法與傳統(tǒng)的開發(fā)方法不同。傳統(tǒng)的開發(fā)方法也叫做面向過程的開發(fā)方法，首先著眼于系統(tǒng)要實(shí)現(xiàn)的功能。從系統(tǒng)的輸入和輸出出發(fā)，分析系統(tǒng)要做那些事情，進(jìn)而考慮如何做這些事情，用自頂向下、逐步進(jìn)行功能分解的方式建立系統(tǒng)的功能結(jié)構(gòu)和相應(yīng)的程序模塊結(jié)構(gòu)。但是，程序因各種各樣的原因需要經(jīng)常修改，這種修改常常涉及到許多模塊，有時因功能改變導(dǎo)致全部模塊都要變更，這樣修改工作量極大，很容易產(chǎn)生新的錯誤，使得程序退化。面向?qū)ο箝_發(fā)方法的出現(xiàn)，彌補(bǔ)了傳統(tǒng)方法的不足。面向?qū)ο箝_發(fā)方法首先著眼于應(yīng)用問題所涉及的對象，包括各種物理實(shí)體、事件、規(guī)格說明，識別為解決問題所需的各種對象、對象的屬性、必須的操作，以及各個對象的實(shí)例之間的關(guān)系，從而建立對象的結(jié)構(gòu)和為解決問題需要執(zhí)行的事件序列（俗稱場景），據(jù)此建立類的繼承層次結(jié)構(gòu)，通過各個類的實(shí)例之間的消息連接，實(shí)現(xiàn)所需的功能。類的定義充分體現(xiàn)了抽象數(shù)據(jù)類型的思想，基于類的體系結(jié)構(gòu)可以把程序的修改局部化。特別是一旦系統(tǒng)功能需要改變(gǎibiàn)，主要修改類中間的某些服務(wù)，類所代表的對象基本不變，整個系統(tǒng)保持穩(wěn)定，確保系統(tǒng)不致因修改而退化。因此，用面向?qū)ο箝_發(fā)方法建立起來的軟件易于修改，與傳統(tǒng)的方法相比，程序具有更好的可靠性、可修改性、可維護(hù)性、可復(fù)用性、可適用性和可理解性。C++對于面向?qū)ο蟪绦蛟O(shè)計的支持，核心部分就是類的定義。類的定義體現(xiàn)了抽象數(shù)據(jù)類型的思想，可用以支持說明與實(shí)現(xiàn)的分離，將抽象數(shù)據(jù)類型的實(shí)現(xiàn)封裝在類的內(nèi)部(nèibù)，使達(dá)到信息隱蔽的原則。為此，對類的成員來說，規(guī)定有三級存?。汗?public)、私有(sīyǒu)(private)和保護(hù)(bǎohù)(protected)。對于(duìyú)public域中聲明的數(shù)據(jù)成員和函數(shù)成員（也叫做成員函數(shù)），privateprotected域中聲明的被聲明為友元（friend）protectedprivate域中聲明的數(shù)據(jù)成員和成員函數(shù)，則不允許該類的派生類訪問它們。1.3pointpublic域聲明的函數(shù)構(gòu)成這個類Point類的實(shí)例執(zhí)行這些共有函數(shù)。例如，Pointget_x，以及加另一個點(diǎn)的命令operator+Point類的用戶可用的private域聲明的成員僅允許該類的成員函數(shù)或友元函數(shù)存取。例如，Point類中一個點(diǎn)的表示由兩個整數(shù)實(shí)例變量x，y組成。類的用戶不能直接privatePoint1.3Point類的定義#ifndefPOINT_H#definePOINT_H //Intheheaderfilepoint.h#include<iostream.h>classPoint{ //類定義public:Point(int,int);Point(Point&);~Point();intget_x();intget_y();voidput_x(inta);voidput_y(intb);

//共有域//構(gòu)造函數(shù)//復(fù)制構(gòu)造函數(shù)//析構(gòu)函數(shù)//存取函數(shù)(hánshù)Pointoperator+(pointp);//重載函數(shù)：當(dāng)前(dāngqián)對象+參數(shù)表中對象pPointoperator*(inti); 重載函數(shù)：當(dāng)前對象(duìxiàng)*參數(shù)表中整數(shù)iintoperator>(Pointp); //重載函數(shù)：判斷當(dāng)前(dāngqián)對象>參數(shù)表中對象p否intoperator<(Pointp); //重載函數(shù)：判斷(pànduàn)當(dāng)前對象<p否intoperator==(Point&p);private:intx;inty;

//重載函數(shù)：判斷當(dāng)前對象=p否

friendistream&operator>>(istream&in,Point&p);friendostream&operator<<(ostream&out,Point&p);};

友元函友元函#endif為了存取一個點(diǎn)的x，y分量，類提供了4個函數(shù)get_x()、get_y()、put_x(inta)、put_y(intb)private關(guān)鍵字來保護(hù)數(shù)據(jù)的表示并提供個點(diǎn)，即使用一個角度theta和一個離開原點(diǎn)的距離rpublic界面的存取函數(shù)使用直角坐標(biāo)。系統(tǒng)開發(fā)的一種方法是把類的聲明放在header文件中，成員函數(shù)的實(shí)現(xiàn)分header在頭文件（point.h）中程序的頭尾放上#ifndefPOINT_H、#definePOINT_H和#endif。Point類的輸出函數(shù)的實(shí)現(xiàn)代碼可以為：ostream&Point::operator<<(ostream&strm,Pointp){returnstrm<<"("<<p.get_x()<<","<<p.get_y()<<")";};p的值以“xystrm指明的輸出流中去。注意，C++CstructC++structclassstructpublic。若struct內(nèi)部自始至終缺省訪問級別，則所有的成員都在公共接口中。而在class中private。除此之外，structclass是等價的。struct一樣,unionC++中，union可包含函數(shù)和變量，還可包含構(gòu)造函數(shù)和析構(gòu)函數(shù)。C++unionC的特性，主要classstruct相比，unionstruct相似，union中默認(rèn)public。C++中的對象(duìxiàng)1、建立(jiànlì)類的對象類與對象的關(guān)系類似于語言程序中的數(shù)據(jù)類型與變量，類可以視為數(shù)據(jù)類型，它一旦定義，在整個程序運(yùn)行過程中是不會變化的；而對象是在程序運(yùn)行過程中建立，并在程序運(yùn)行過程中撤銷，它是有生命周期的。類通過建立屬于該類的對象參加運(yùn)算，對象根據(jù)問題(wèntí)要求有其實(shí)際含義。建立類的對象亦稱為(chēnɡwéi)實(shí)例化，采用的方式類似于定義CPoint類實(shí)例的語句是：Pointp(6,3)；Pointq；

自動地自動地staticPoints(3,4)； 靜態(tài)地Point*t=newPoint(1,1)；通過動態(tài)分配p、qsPointt2、構(gòu)造函數(shù)當(dāng)遇到以上的每一個語句時，將隱式地調(diào)用一個構(gòu)造函數(shù)（constructor），1.3中Point類的定義中聲明了兩個構(gòu)造函數(shù)，構(gòu)造函數(shù)的參數(shù)用于初始化對Pointp(6,3)PointpPoint(int,int)x,y6,3：Point::Point(inta,intb){x=a;y=b;}或 Point::Point(inta,intb):x(a),y(b){}這兩種形式是等效的。構(gòu)造函數(shù)可以定義默認(rèn)值。例如Point::Point(inta=0,intb=0):x(a),y(b){}當(dāng)定義實(shí)例時給定初始值,則該實(shí)例以給定初始值來初始化其數(shù)據(jù)成員。例如，Pointp(6,3)，則用x=a=6,y=b=3。當(dāng)定義實(shí)例時未給出初始值。則該實(shí)例以默認(rèn)值來初始化其數(shù)據(jù)成員，例如，Pointqxa0,yb03、析構(gòu)函數(shù)當(dāng)要撤銷對象時，需要隱式地調(diào)用另一個函數(shù)，叫做析構(gòu)函數(shù)（destructor），它屬于名字相同的類，但在名字前面加上了一個“～”。例如～Point。一個類可以定義幾個構(gòu)造函數(shù)，但只能定義一個析構(gòu)函數(shù)。當(dāng)控制要退出自動(zìdòng)變量的作用域時，或當(dāng)通過delete命令釋放(shìfàng)一個動態(tài)分配的變量時，就要調(diào)用析構(gòu)函數(shù)。當(dāng)main函數(shù)執(zhí)行結(jié)束時，將釋放靜態(tài)(jìngtài)聲明的變量。一個析構(gòu)函數(shù)用于在刪除一個類的對象時做清除(qīngchú)工作。C++的輸入(shūrù)/輸出在C++中執(zhí)行輸入/輸出操作，需要用#include預(yù)處理指令包括一個<iostream.h>C++的流（stream）操作?！傲鳌盋++istreamostream，它們定義了輸入流和輸出流。在C++語言程序中，基本的輸入/輸出方式有兩種：鍵盤屏幕輸入/輸出和文件輸入/輸出。1、鍵盤屏幕輸入/輸出C中有用于定向到鍵盤輸入設(shè)備、屏幕輸出設(shè)備和錯誤文件的命令stdin、stdoutstderrC++cin，coutcerr來定義鍵盤輸入類、屏幕輸出類和錯誤信息輸出類。操作符<<用于寫出類ostream系列輸出對象，可用<<分開。操作符>>istream的一個對象。1.4cinab，并將它們打印到標(biāo)準(zhǔn)輸出設(shè)備上。1.4流操作使用示例#include<iostream.h>voidmain(){inta,b;cin>>a>>b;cout<<”a:"<<n<<"f:"<<f<<endl;}在輸出語句中最后輸出的endl是C++的I/O操作符,它的用途是輸出一個換行符并清空流。C++中的輸入/輸入/輸出項(xiàng)的類型和順序。與其他C++操作符一樣，輸入/輸出操作符能夠被重載。2、文件輸入/輸出C++中的文件輸入/輸出方式如下：·在程序開頭必須用預(yù)處理指令#include包含頭文件<fstream.h>，它定義了類ifstream、ofstream和fstream?！ひ獎?chuàng)建一個輸入流,必須聲明它為ifstream類的實(shí)例；·要創(chuàng)建一個輸出流,必須聲明它為ofstream類的實(shí)例；·執(zhí)行輸入和輸出操作的流必須聲明它為fstream類的實(shí)例。1.5#include<fstream.h>#include<iostream.h>#include<stdlib.h>voidmain(){ifstreaminFile;ofstreamoutFile;

//inFile輸入(shūrù)流對象//outFile為輸出(shūchū)流對象outFile.open("my.dat",ios::out);charuniv[]="Tsinghua",name[10];intcourse=2401,number;

//建立輸出(shūchū)文件"my.dat"outFile<<univendl; //輸出(shūchū)到"my.dat"outFile<<courseendl;inFile.open("my.dat",ios::in|ios::nocreate);//打開(dǎkāi)輸入文件"my.dat"if(!inFile){cerr<<"不能打開my.dat"<<endl;exit(1);}charc;inFile>>name>>c>>number;outFile<<"name:"<<name<<endl;outFile<<"number:"<<number<<endl;}ifstream類、ofstream類和fstream類都是從istream類和ostream類派生出來istreamostreamiosios的所有運(yùn)算。open()時向，函數(shù)返回文件的開始地址。系統(tǒng)在存儲文件時在其末尾添加有文件結(jié)束標(biāo)記。在程序1.5中，如果文件未被打開,則outFile=0；如果文件被成功地打開,則它將代替cout,將輸出引導(dǎo)到文件“my.dat”中。在文件打開的操作中，指定的文件模式有以下幾種：ios::app：把所有對文件的輸出添加在文件尾。它只用于輸出文件。ios::binaryios::nocreate：若文件不存在則將導(dǎo)致打開操作失敗。ios::out：表明該文件用于輸出。此項(xiàng)可缺省。ios::in：表明該文件用于輸入。此項(xiàng)可缺省。C++中的函數(shù)1、C++函數(shù)的概念C++中有兩種函數(shù)：常規(guī)函數(shù)和成員函數(shù)。不論哪一種函數(shù)，其定義都41.6給出給出一個函數(shù)的例子。max是函數(shù)名，intaintb是形式參數(shù)表int是返回類型在花括號內(nèi)括起來的是函數(shù)體，它給出了函數(shù)操作的實(shí)現(xiàn)。程序(chéngxù)1.6求兩個值a與b中的大值intmax(inta,intb){if(a>b)returna;elsereturnb;}在C++中所有函數(shù)(hánshù)都有一個返回值，或者返回計算結(jié)果，或者返回執(zhí)行狀態(tài)。如果函數(shù)不需要返回值，可使用void來表示它的返回(fǎnhuí)類return語句(yǔjù)返回。return一個與返回類型相同類型的值，并中止函數(shù)(hánshù)的執(zhí)行。函數(shù)返回時可以通過引用方式，參看下面的程序1.7，此時在函數(shù)類型后加上一個“&”。程序1.7使用引用的事例#include<iostream.h>char&replace(intm);chars[80]=“HelloThere”;main(){replace(5‘x’; couts; //xHello后面的空格}char&replace(intm){returns[m];}函數(shù)replace()的返回類型說明為返回一個字符的引用類型,在函數(shù)執(zhí)行時返回參數(shù)m指定的s數(shù)組元素的值。main()執(zhí)行時把字符“x”送給s[5]。2、C++中的參數(shù)傳遞函數(shù)調(diào)用時傳送給形參表的實(shí)參必須與形參在類型、個數(shù)、順序上保持一致。參數(shù)傳遞有兩種方式。一種是傳值，這是缺省的參數(shù)傳遞方式；一種是引用類型。使用傳值方式時，把實(shí)參的值傳送給函數(shù)局部工作區(qū)相應(yīng)的副本中，函數(shù)使用這個副本執(zhí)行必要的功能。這樣，函數(shù)修改的是副本的值，實(shí)參的值不變，參看程序1.8中的函數(shù)squareByValue(int)。使用引用類型方式傳遞參數(shù)時需將形參聲明為引用類型，即在參數(shù)名前加一個“&”。當(dāng)一個實(shí)參與一個引用型形參結(jié)合時，被傳遞的不是實(shí)參的值，1.8中的squareByReference(int&)。程序1.8求平方#include<iostream.h>intsquareByValue(int);voidsquareByReference(int&);intmain(){intx=2,z=4;cout求平方(píngfāng)xxendl用squareByValue求平方(píngfāng)值”<<squareByValue(x)<<endl<<“求平方(píngfāng)值后x=”<<x<<endl;//求平方(píngfāng)值前x=2,squareByValue(x)=4,求平方(píngfāng)值后x=2}

coutzzendlsquareByReference求平方”<<endl;squareByReference(z);cout<<“求平方值后z=”<<z<<endl;//求平方值前z=4,求平方值后z=16intsquareByValue(inta){returna*=a;}voidsquareByReference(int&a){a*=a;}當(dāng)一個函數(shù)的返回值多于一個時,其中一個可由return語句返回,其他返回值可使用引用型參數(shù)返回。注意，在使用傳值型參數(shù)時，參數(shù)可以是常數(shù)、常量、變量或表達(dá)式；但在使用引用型參數(shù)時，參數(shù)只能是變量或?qū)ο?。一種特殊的引用調(diào)用方式叫做常值引用,其格式為constType&a，其中Type為參數(shù)的數(shù)據(jù)類型。在函數(shù)體中不能修改常值參數(shù)。數(shù)組參數(shù)的傳遞情況比較特殊。數(shù)組作為形參可按傳值方式聲明，但實(shí)際intR[的形式聲明，因此需要顯式地聲明數(shù)組的大小。1.9a[]n個元素的和intsum(inta[],intn){if(n>0)returna[n-1]+sum(a,n-1);elsereturn0;}若傳送的值參是一個對象（作為類的實(shí)例）時,在函數(shù)中就創(chuàng)建了該對象的一個副本。在創(chuàng)建這個副本時會調(diào)用該對象的復(fù)制構(gòu)造函數(shù)。如果該類沒有顯式定義的復(fù)制構(gòu)造函數(shù)，那么編譯器會自動創(chuàng)建一個默認(rèn)的復(fù)制構(gòu)造函數(shù)，而在函數(shù)結(jié)束前要調(diào)用該副本的析構(gòu)函數(shù)撤消這個副本。需要注意，如果一個類在構(gòu)造函數(shù)中用new為指針成員分配了內(nèi)存空間，并在析構(gòu)函數(shù)中用delete進(jìn)行釋放，那么必須手工定義它的復(fù)制構(gòu)造函數(shù)。因?yàn)榫幾g器自動創(chuàng)建的復(fù)制構(gòu)造函數(shù)只能夠進(jìn)行指針的簡單復(fù)制，并不會分配新的內(nèi)存空間，這樣當(dāng)副本析構(gòu)后，母本占有的動態(tài)空間會被釋放掉，造成錯誤。若采用引用方式傳遞對象，在函數(shù)中不創(chuàng)建該對象的副本，也不存在最后撤消副本的問題。但是，通過引用傳遞的是對象時，函數(shù)對對象的改變將影響調(diào)用的對象。3、成員函數(shù)的返回值當(dāng)成員函數(shù)的返回值為傳值方式時，允許改變該對象的私有數(shù)據(jù)成員。當(dāng)成員函數(shù)的返回值為常值傳值方式時const得該對象的私有成員不能被改變。當(dāng)成員函數(shù)的返回值為引用方式時，該成員函數(shù)的返回值應(yīng)是一個已存在變量（或?qū)ο螅┑膭e名。當(dāng)該成員函數(shù)被重新賦值時，其對應(yīng)變量（或?qū)ο螅┑闹祵⒏淖?。?dāng)成員函數(shù)的返回值為常值引用方式時，其返回值與引用方式的成員函數(shù)返回值類同。但該成員函數(shù)不能改變該對象的私有成員。程序(chéngxù)1.10函數(shù)返回的事例#include<iostream.h>classTemperature{private:floathighTemp,lowTemp;public:Temperature(inthi,intlo){highTemp=hi; lowTemp=lo;}voidUpdateTemp(floattemp);floatGetHighTemp()const;floatGetLowTemp()const;};voidTemperature::UpdateTemp(floattemp){if(temp>highTemp)highTemp=temp;if(temp<LowTemp)lowTemp=temp;}floatTemperature::GetLowTemp()const{returnlowTemp;}

成員構(gòu)造函數(shù)floatTemperature::GetHighTemp()const{returnhighTemp;}當(dāng)成員函數(shù)返回值為常值傳值方式或常值引用方式時，const標(biāo)識符一般放在最后。4、友元函數(shù)在類的聲明中可使用保留字friend定義友元函數(shù)。友元函數(shù)實(shí)際上并不是這個類的成員函數(shù)，它可以是一個常規(guī)函數(shù)，也可以是另一個類的成員函數(shù)。如果想通過這種函數(shù)存取類的私有成員和保護(hù)成員，則必須在類的聲明中給出函數(shù)的原型，并在該函數(shù)原型前面加上一個friend。1.3Point類的聲明>>Point類的友元函數(shù)：friendistream&operator>>(istream&,Point&); //輸入友元函數(shù)friendostream&operator<<(ostream&,Point&); //輸出友元函動態(tài)存儲分配C語言程序中使用(shǐyòng)malloc動態(tài)地為程序變量分配它所需要的空間，并通過(tōngguò)freemallocsizeof提供所需存儲空間的數(shù)量，完成動態(tài)分配后還需要對返回(fǎnhuí)指針做類型的強(qiáng)制轉(zhuǎn)換。C++則為動態(tài)存儲分配提供(tígōng)了兩個新的命令：newdelete，增強(qiáng)(zēngqiáng)了動態(tài)分配的功能。它們操縱屬于可利用空間的存儲并取代了Cmallocfreenew回一個指向新分配空間的指針。此時，返回指針自動根據(jù)類型說明進(jìn)行了類型轉(zhuǎn)換。例如，可以為分配一個整數(shù)或一個點(diǎn)編寫如下語句：int*ip=newint;或 Point*p=newPointC++new分配的存儲必須顯式地使用delete釋放。deletenew100個點(diǎn)的數(shù)組：Point*p=newPoint[100]則通過以下命令釋放該存儲：delete[]p;若釋放時遺漏了“[]p所指示的第一個元素，我們將會“失99個點(diǎn)所占據(jù)空間，以致不能再復(fù)用它們。另一方面，若使用表達(dá)式計算出來的值超出括號中的100newdelete管理存儲時必須仔細(xì)。C++中的繼承繼承性（inheritance）是漸增式地修改已有的類定義以產(chǎn)生新類的技術(shù)。1.111.11(a)Polygon（多邊形1.11(b)Quadrilateral（四邊形）Quadrilateral首部的短語“:publicPolygonQuadrilateralPolygon的子類，而且PolygonQuadrilateral的公有成員。在成員函數(shù)的聲明中記號“=0”指明這個方法的定義應(yīng)由子類提供，記號“=0PolygonPolygon所有操作都沒有實(shí)現(xiàn)代碼。1.11類的繼承關(guān)系舉例classPolygon{public:

classQuadrilateral:publicPolygon{public:Polygon(Point);voidmove(Point);voidisInside(Point);PointgetReferencePoint();virtualvoiddraw()=0;private:PointreferencePoint;};Polygon類的定義

Quadrilateral(Point,Point);voidisInside(Point);voiddraw();private:Pointvertex2;};PolygonQuadrilateral的定義程序(chéngxù)1.12展示了類Quadrilateral的完整定義(dìngyì)，是復(fù)合了程序1.11所定義的Quadrilateral類和Polygon類而得到(dédào)的結(jié)果。注意(zhùyì)，Polygon類的私有(sīyǒu)referencePointQuadrilateralPolygon類中定義的成員函數(shù)getReferencePoint()來進(jìn)行存取。因此，Quadrilateral對象的第一個頂點(diǎn)（即referencePoint）不能在Quadrilateral類中直接存取。程序1.12 Quadrilateral類的實(shí)際定義classQuadrilateral{public:Quadrilateral(Point,Point);PointgetReferencePoint();voidisInside(Point);voidmove(Point);voiddraw();private:Pointvertex2;

//Polygon類繼承的屬性//Polygon類繼承的屬性};現(xiàn)在改變Polygon的聲明，以使其原來被封裝的數(shù)據(jù)成員對它的子類有1.13QuadrilateralPolygon類的方式。使用保留字protected1.11(a)privatePolygon聲明為protected的成員。Quadrilateral類的成員函數(shù)現(xiàn)在就能直接存取在程序1.13中給定的referencePoint了。程序1.13 基類（超類）中被保護(hù)成員的影響classQuadrilateral{public:Quadrilateral(Point,Point);PointreferencePoint();voidisInside(Point);voidmove(Point);voiddraw();protected:PointreferencePoint;Pointvertex2;

//Polygon類繼承的屬性//Polygon類繼承的屬性//Polygon類繼承的屬性};多態(tài)性多態(tài)性（polymorphism）是指允許同一個函數(shù)（或操作符）有不同的版本(bǎnběn)，對于不同的對象執(zhí)行不同的版本。C++支持以下兩種多態(tài)性：編譯時的多態(tài)性，表現(xiàn)(biǎoxiàn)為函數(shù)名（或操作符）的重載。運(yùn)行時的多態(tài)性，通過派生類和虛函數(shù)(hánshù)來實(shí)現(xiàn)。1、C++中的函數(shù)(hánshù)名重載函數(shù)(hánshù)名重載允許C++程序中多個函數(shù)取相同的函數(shù)名，但其形參或返回類型可以不同。例如，C3abs()、labs()和fabs()C中因處理的C++3abs()：intabs(int);longabs(long);doubleabs(double);編譯器能夠比較具有同名的函數(shù)的特征，通過識別實(shí)參的數(shù)目和每個實(shí)參的類型，來標(biāo)識使用于一個特定調(diào)用的是哪一個版本的abs()。2、C++的操作符重載C++clear(int*)，它將一個整數(shù)清零。還可clear(int[])，它把一個整數(shù)數(shù)組清零。C中clearIntArray()clearInt()C++中，編譯器能夠比較同名函數(shù)的特征，通過識別實(shí)參的數(shù)目和每個實(shí)參的clear。為了支持面向?qū)ο?，C++(如‘＋’和‘＜’作可使得程序更可讀、寫得更自然。例如，可定義“點(diǎn)(Point)”的運(yùn)算（作為成員函數(shù)），如：p1+p2(x1,y1)(x2,y2)(x1+x2,y1+y2)p1<p2p1p2的“小于”關(guān)系p1p2(0,。p1／i：一個點(diǎn)p＝(x,y)除以一個整數(shù)i的除法(x/i,y/i)?？梢园匆韵路绞绞褂弥剌d操作：Pointoperator+(constPoint&p);Pointoperator/(inti);intoperator<(constPoint&p);使用這些新的操作的表達(dá)式如:PointmidPoint=(point1+point2)/2;或 if(midPoint<referencePoint)...point1+point2Point的實(shí)例point1調(diào)用該對象的屬性確定第一個操作數(shù)的值；函數(shù)參數(shù)表中指定的Pointpoint2(int，float)那樣來使用用戶自定義類型。與在不允許重載操作的語言中相同的語句比這樣可以改善程序的可讀性。但重載作為非成員函數(shù)的（雙目）操作符時，參加運(yùn)算(yùnsuàn)的兩個操作數(shù)必須都出現(xiàn)在參數(shù)表中。第一個參數(shù)是第一操作數(shù)，第二個參數(shù)是第二操作數(shù)。例如，若用struct定義worker記錄(jìlù)結(jié)構(gòu)如下：structworker{intid;charname[20];floatage;}設(shè)wk是屬于worker的一個對象，可使用如下語句輸入(shūrù)或輸出wk的數(shù)據(jù)：cin>>wk.id>>>>wk.age;cout<<wk.id<<""<<<<""<<wk.age<<endl;(duìxiàng)(chārù)操作符“<<worker“<<”如下：istream&operator>>(istream&istr,worker&x){istr>>x.id>>>>x.age;returnistr;}ostream&operator<<(ostream&ostr,constworker&x){ostr<<x.id<<""<<<<""<<x.wage<<endl;returnostr;}按照上述定義后，可使用如下語句對worker類的對象wk進(jìn)行輸入或輸出：cin>>wk;cout<<wk;執(zhí)行第一條語句時將把實(shí)際參數(shù)cin和wk引用（即按地址方式）傳送給被調(diào)用函數(shù)istrxistrx分別被取代（或稱換名）cinistrxcinwkistr（cin），操作符對多個對象進(jìn)行輸入。注意：當(dāng)在同一行上輸入多個數(shù)據(jù)時，其數(shù)據(jù)之間要用空格隔開。coutwk引用（即按地址方式）ostrxostrxcoutwk，函數(shù)ostrxcoutwkostr（即cout），操作符對多個數(shù)據(jù)進(jìn)行輸出。3、虛函數(shù)與動態(tài)綁定一個虛函數(shù)（virtualfunction）是一個在基類中被聲明為“virtual”，并在一個或多個派生類中被重定義的函數(shù)。如果在基類的聲明中，在一個函數(shù)的函數(shù)特征之前加一個關(guān)鍵字“virtual”，則編譯器將建立一個可由運(yùn)行環(huán)境解釋的特殊結(jié)構(gòu)，并由程序執(zhí)行時而不是編譯時由運(yùn)行環(huán)境來執(zhí)行對這個函數(shù)的調(diào)用。用“virtual”聲明的一個函數(shù)的實(shí)現(xiàn)，可按以下兩種方式來處理：如果(rúguǒ)1.11Polygon類的聲明(shēngmíng)draw()后面沒有“0”，同時代碼(dàimǎ)draw()操作(cāozuò)的默認(rèn)實(shí)現(xiàn)，則所有沒有給出自己特殊的draw()操作的子類將繼承這個(zhège)默認(rèn)實(shí)現(xiàn)。如果像程序1.11(a)中所說明的那樣，不提供draw()的實(shí)現(xiàn)，draw()被設(shè)置為“0”。此時聲明的函數(shù)稱為純虛函數(shù)（purevirtualfunction），如果一個類至少有一個純虛函數(shù)，那么該類就是抽象類（abstractclass）。一個抽象類必須作為基類而被其他類繼承，抽象類自己不能生成實(shí)例，就是說不能由類生成對象，因?yàn)槌橄箢愔兄辽儆幸粋€函數(shù)沒有實(shí)現(xiàn)。如果一個基類中的某個函數(shù)聲明為純虛函數(shù)，則該基類的任何派生類都必須定義自己的實(shí)現(xiàn)。draw()的聲明中記號“virtual態(tài)地確定，而不是在編譯時確定。這種做法就是動態(tài)綁定（dynamicbinding）。為了解這個工作如何進(jìn)行，考慮一個例子，如程序1.14所示的一display：程序1.14動態(tài)綁定的例子voiddisplay(Polygon&p){……p.draw()……}Quadrilateralq(Pointp1(1,1),Pointp2(2,2))……display(q)……display()QuadrilateralqPolygondraw()1.11(a)Polygon類中draw()Quadrilateral這樣，在運(yùn)行時動態(tài)地將要執(zhí)行的成員函數(shù)從Polygondraw()1.8中描述。PolygonvoidPolygonvoiddraw()Trianglevoiddraw()Quadrilateralvoiddraw(voiddisplay(Polygon&aPolygon){aPolygon.draw();…31}Polygonvirtualvoiddraw()Trianglevoiddraw()Quadrilateralvoiddraw(或voiddisplay(Polygon&aPolygon){aPolygon.draw();…}PAGEPAGE41成員(chéngyuán)函數(shù)draw的的靜態(tài)(jìngtài)綁定 (b)虛成員(chéngyuán)函數(shù)draw的動態(tài)(dòngtài)綁定1.8Polygon的靜態(tài)(jìngtài)與動態(tài)綁定在下一章討論線性結(jié)構(gòu)時可知，線性表有兩種存儲表示：基于數(shù)組的存儲表示（順序表）和基于鏈表的存儲表示（單鏈表）。如果將它們定義為抽象基類和兩個具體派生類的關(guān)系：classlinearList…………classseqList:publiclinearList…………classlinkedList:publiclinearList…………

//抽象基類：線性表//派生類：順序表//派生類：單鏈表如果需要定義和使用一個線性表對象，可以如下定義選用某一種存儲表示：linearList*p;seqListseqList_obj;p=&seqList_obj;intadd=p->Locate(5);表…………或

//按順序表使用線性linearList*p;linkedListlinkedList_obj;p=&linkedList_obj;intaddp->Locate(5); //按單鏈表使用線性表…………函數(shù)調(diào)用的動態(tài)綁定方法在解釋性語言中是標(biāo)準(zhǔn)的實(shí)踐，但在編譯性語言沒有廣泛使用。動態(tài)綁定用在編譯性面向?qū)ο笳Z言是為了支持所包含的多態(tài)性。C++(template)C++void*struct。第三種方式不介C++中模板的使用，這種方式已經(jīng)過時。C++中，是想要抽出構(gòu)件的不依賴于數(shù)據(jù)類型的構(gòu)件的輸入／輸出功能上，而不要把精力消耗在放在隊(duì)列中的元素是什么數(shù)據(jù)類型1.3Point類時，x,y值的數(shù)據(jù)類型可能因問題而異，在圖形系統(tǒng)中對于屏幕坐標(biāo)需要整數(shù)值，但在地球坐標(biāo)系統(tǒng)中則需要浮1.3Point類定義，使用模板機(jī)制進(jìn)行重寫。T面或每個成員函數(shù)的實(shí)現(xiàn)程序前面增加一條類型參數(shù)化語句template<classT>在程序內(nèi)部就可以直接使用參數(shù)T定義(dìngyì)相應(yīng)的變量的數(shù)據(jù)類型。如程序1.15所示。程序(chéngxù)1.15PointC++模板(múbǎn)template<classT>classPoint{public:Point(T,T);Point(Pointp);Tget_x();Tget_y();……//其它(qítā)private:Tx;Ty;};這樣定義的類稱為類屬（generic）類，它提供了一個類模板，它既可用于整數(shù)坐標(biāo)值的實(shí)例化對象，也可用于實(shí)數(shù)坐標(biāo)值的實(shí)例化對象。在實(shí)際使用時，用語句：Point<int>a;Pointintx,y值，在執(zhí)行環(huán)境下通過簡單地代換，變成針對int數(shù)據(jù)類型的對象定義或算法。算法定義1、算法的定義什么是算法（Algorithm）？些指令為解決某一特定任務(wù)規(guī)定了一個運(yùn)算序列。一個算法應(yīng)當(dāng)具有以下特性：有輸入0個或多個輸入。它們是算法開始運(yùn)算前外部提供，也可以使用賦值語句在算法內(nèi)給定。有輸出。一個算法應(yīng)有一個或多個輸出，輸出的量是算法計算的結(jié)果。確定性。算法的每一步都應(yīng)確切地、無歧義地定義。對于每一種情況，需要執(zhí)行的動作都應(yīng)嚴(yán)格地、清晰地規(guī)定。有窮性。一個算法無論(wúlùn)在什么情況下都應(yīng)在執(zhí)行有窮步后結(jié)束。能行性。算法中每一條運(yùn)算都必須是足夠基本的。就是說，它們原(tōngguò)運(yùn)算就能完成。算法和程序不同，程序可以(kěyǐ)不滿足上述的特性（4）。例如，一個操作系統(tǒng)(cāozuòxìtǒnɡ)在用戶未使用前一直處于“等待(děngdài)”的循環(huán)中，直到出現(xiàn)新的用戶事件為止。這樣的系統(tǒng)可以無休止地運(yùn)行，直到系統(tǒng)停工。但在本書中，所有程序都沒有這種情況，故對算法和程序這兩個術(shù)語不加嚴(yán)格區(qū)分。算法的描述可以有多種方式，如語言方式、圖形方式、表格方式。在本C++和面向?qū)ο蟮碾p重特點(diǎn)，編出的程序結(jié)構(gòu)化程度高，可讀性強(qiáng)。為了更好地交C++此外，采用模板類表示抽象數(shù)據(jù)類型，有助于類的復(fù)用。如果將所有的模板類依出現(xiàn)的次序存放到計算機(jī)中，可在后續(xù)的應(yīng)用中直接使用它們解決問題，從而獲得較大的回報率。2、算法的設(shè)計現(xiàn)以選擇排序?yàn)槔?，說明如何把一個具體問題轉(zhuǎn)變?yōu)橐粋€算法。所使用的方法是自頂向下、逐步求精的結(jié)構(gòu)化程序設(shè)計方法。n個亂七八糟的數(shù)據(jù)按自小到大的順序排列起來?？赡苡械臄?shù)據(jù)具有相同的值，因此，最后的排列結(jié)果應(yīng)是數(shù)據(jù)的非遞減順序。其次，考慮問題解決方案。n個數(shù)據(jù)存在數(shù)組a[0]到a[n-1]中，需要一1a[0]a[0]a[n-1]中選擇一個最a[0]2個數(shù)a[1]a[1]a[n-1]a[1]，這234個數(shù)據(jù)，…，直n-1n-1n排了，因?yàn)橹皇Ｋ粋€，它無論如何就在這兒了。根據(jù)以上思路，寫出算法的框架。i0,1,2,…n-2i號n-1kkia[i]a[k]。n-1a中得到排序結(jié)果。程序1.16 排序算法的框架for(inti=0;in-1i++){ //n-1a[i]a[n-1]k;若i≠k，則交換a[i]與a[k];}然后將其細(xì)化。這時需要解決兩個問題：一是如何選擇值最小的數(shù)據(jù)；二是如何交換兩個數(shù)據(jù)的值。in-1iki+1,i+2,…n-1個，若檢測到還有比剛才最小的還要小的元素，用k標(biāo)示它。在檢查結(jié)束后k標(biāo)示的就是值最小的數(shù)據(jù)。交換兩個數(shù)據(jù)中的值時需要(xūyào)一個暫存變量，如用temp作為(zuòwéi)中介，以進(jìn)行(jìnxíng)對換：temp=a[i] a[i]=a[k] a[k]=temp綜合以上做法(zuòfǎ)，即可得到取名為selectSort的排序程序(chéngxù)如程序1.17所示。程序1.17 selectSort排序算法voidselectSort(inta[],constintn){//na[0],a[1],…,a[n-1]按非遞減的順序排序。inttemp,i,j,k;for(i=0;i<n-1;i++){ki; //a[i]檢查到a[n-1],最小的整數(shù)在a[k]for(j=i+1;j<n;j++)if(a[j]<a[k])k=j;if(i!=k){

//k指示當(dāng)前找到的最小整數(shù)//交換a[i]與a[k]temp=a[i];a[i]=a[k];a[k]=temp;}}}算法性能分析與度量在面向?qū)ο蟮某绦蛑?，通過建立類來實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)，同時還要實(shí)現(xiàn)類中各個成員函數(shù)，以及應(yīng)用各個類的服務(wù)的算法。因此，一旦確定了類的數(shù)據(jù)結(jié)構(gòu)，就需要描述算法的設(shè)計和實(shí)現(xiàn)細(xì)節(jié)，并寫成具體的過程。但是一個類的實(shí)現(xiàn)，可用多種數(shù)據(jù)結(jié)構(gòu)來表示；一個服務(wù)的實(shí)現(xiàn)，可以有多個算法可供選擇。因此，采用什么數(shù)據(jù)結(jié)構(gòu)和算法，成為一個重要的問題。算法的性能標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣與算法直接有關(guān)。數(shù)據(jù)結(jié)構(gòu)的性能實(shí)際是由實(shí)現(xiàn)其各個服務(wù)的算法來體現(xiàn)的。對數(shù)據(jù)結(jié)構(gòu)的分析實(shí)質(zhì)上就是對實(shí)現(xiàn)其各個服務(wù)的算法的性能的分析。判斷一個算法的優(yōu)劣，主要有以下幾個標(biāo)準(zhǔn)：1、正確性（Correctness）：要求算法能夠正確地執(zhí)行預(yù)定的功能和性能要求。這是最重要的標(biāo)準(zhǔn)，這要求算法的編寫者對問題的要求有正確的理解，并能正確地、無歧義地描述和利用某種編程語言正確地實(shí)現(xiàn)算法。2、可使用性（Usability）：要求算法能夠很方便地使用。此特性亦稱用戶友好性。為便于用戶使用，要求該算法具有良好的界面，完備的用戶文成一個功能。3、可讀性（Readability）：算法的需要。為了達(dá)到這一要求，算法的邏輯必須是清晰的、簡單的和結(jié)構(gòu)化的。所有的變量名、函數(shù)名的命名必須有實(shí)際含義、讓人見名知義。在算法中必須加入(jiārù)注釋，簡要說明算法的功能、輸入與輸出參數(shù)的使用規(guī)則、重要數(shù)據(jù)的作用、算法中各程序段完成的功能等。4、效率(xiàolǜ)（efficiency）：算法的效率主要指算法執(zhí)行時計算機(jī)資算法的時間代價。算法的效率與多種因素(yīnsù)有關(guān)。例如，所用的計算機(jī)系統(tǒng)、可用的存儲容量和算法的復(fù)雜性等。下面我們將重點(diǎn)地討論算法的效率，其他判斷標(biāo)準(zhǔn)在以后的章節(jié)中再加以討論。5、健壯性（Robustness）：讀文件記錄、子程序調(diào)用狀態(tài)進(jìn)行自動檢錯、報錯并通過與用戶對話來糾錯的功能。這也叫做容錯性或例外處理。一個完整的算法必須具有(jùyǒu)健壯性，能夠?qū)Σ缓侠淼臄?shù)據(jù)進(jìn)行檢查。但在算法初寫時可以暫不管它，集中精力考慮如何實(shí)現(xiàn)必要的功能，待到算法成熟時再追加它。6、簡單(jiǎndān)性（Simplicity）：算法的簡單性是指一個算法所采用的算法往往不是最有效的，即可能需要占用較長的運(yùn)行時間和較多的內(nèi)存空間。算法的后期測試的某些部位插裝時間函數(shù)（time()）來測定算法完成某一規(guī)定功能所需的時1.18a[i]xii在n號位置，函數(shù)返回-1。程序1.18 順序搜索的算法//search.cpp中intseqsearch(inta[],constintn,constintx){1]for(inti=0;i<n;i++)if(a[i]==x)break;if(i==n)return-1;elsereturni;

//a[0],…,a[n-}程序1.19給出測試程序的示例。它是對最壞情況進(jìn)行的測試，因此給0a[1001]順序搜索算法前后。程序1.19 測試程序運(yùn)行時#include<iostream.h>#include<time.h>voidTimeSearch(){inta[1001],n; longstart,stop;for(intj=0;j<=1000;j++)a[j]=j+1;cin>>n;//輸入(shūrù)ntime(&start);//開始(kāishǐ)計時intk=seqsearch(a,n,0);查找time(&stop);//停止(tíngzhǐ)計時longrunTime=stop-start;計算運(yùn)行(yùnxíng)時間cout<<""<<n<<""<<runTime<<endl;

//初始化a//////輸出}但是，一個算法與運(yùn)行環(huán)境有關(guān)，同樣的算法在速度不同的計算機(jī)運(yùn)行，執(zhí)行速度相差得非常大；此外，一個算法用不同的編譯器編譯出的目標(biāo)代碼也不一樣長，完成同樣的功能所需時間也不同。對于一個存儲需求極大的算法，如果可用的存儲空間不夠，在運(yùn)行時將不得不頻繁地進(jìn)行內(nèi)外存交換，需要的運(yùn)行時間就很多。因此，算法的運(yùn)行時間依賴于所用的計算機(jī)系統(tǒng)、編譯器、可用存儲空間大小等。我們可以對算法的運(yùn)行時間進(jìn)行測量，以評估算法的正確性和可使用性，但在不同的機(jī)型、不同的編譯器版本、不同的硬軟件配置情況下，想通過測量結(jié)果來判斷算法的優(yōu)劣是不行的。雜性與具體的運(yùn)行環(huán)境和編譯器版本無關(guān)，可以通過復(fù)雜性的度量來進(jìn)行比較。算法的事前估計算法復(fù)雜性的度量屬于事前估計。度度量。空間復(fù)雜度（SpaceComplexity）1n時，解決這個問題的算法在執(zhí)行時所占用的存儲空間也以某種單位由1S(n)S(n)；時間復(fù)雜度（TimeComplexity）1n時，解決這個問題的1T(n)T(n)。n個記錄n即為問題的規(guī)模。又如，對一nn。一般地，因?yàn)樗惴ㄊ轻槍δ骋粚?shí)例（類的對象）一個簡單變量，也可以是一個構(gòu)造型變量。時間單位一般規(guī)定為一個程序步（ProgramStep），不同的語句有不同的程序步。1、空間(kōngjiān)復(fù)雜度度量下面(xiàmian)1.20a+b+b*c+(a+b-c)/(a+b)+4.0的程序(chéngxù)1.211.22n1.21采用(cǎiyòng)1.22采用遞歸方式。程序(chéngxù)1.20 計算表達(dá)式floatabc(floata,floatb,floatc){returna+b+b*c+(a+b-c)/(a+b)+4.0;}1.21a前n個元素的值的迭代算法floatsum(floata[],constintn){floats=0.0;for(inti=0;i<n;i++)s+=a[i];returns;

//s=s+a[i]}1.22a前n個元素的值的遞歸算法floatrsum(floata[],constintn){if(n<=0)return0;elsereturnrsum(a,n-1)+a[n-1];}這些程序所需的存儲空間包括兩個部分：固定部分：這部分空間的大小與輸入輸出個數(shù)多少、數(shù)值大小無關(guān)。主要包括存放程序指令代碼的空間，常數(shù)、簡單變量、定長成分（如數(shù)組元素、結(jié)構(gòu)成分、對象的數(shù)據(jù)成員等）變量所占的空間等。這部分屬于靜態(tài)空間，只要做簡單的統(tǒng)計就可估算?？勺儾糠郑哼@部分空間主要包括其與問題規(guī)