(C語言詳細(xì)版)第一章-什么是數(shù)據(jù)結(jié)構(gòu)

第一章緒論重點：數(shù)據(jù)結(jié)構(gòu)的根本概念難點：ADT、算法復(fù)雜度-1-第一章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2根本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)1.4算法和算法分析1.4.1算法1.4.2算法設(shè)計的要求1.4.3算法效率的度量1.4.4算法的存儲空間的需求作業(yè)-2-1.1什么是數(shù)據(jù)結(jié)構(gòu)眾所周知，二十世紀(jì)四十年代，電子數(shù)字計算機問世的直接原因是解決彈道學(xué)的計算問題。在電子計算機開展的初期階段，人們用計算機主要處理數(shù)值計算問題，用以解決人們用手工或機械計算機難以勝任的數(shù)值計算。當(dāng)時涉及的數(shù)據(jù)對象還比較簡單，不外乎是整型、實型、布爾型等?！獢?shù)學(xué)軟件。隨著計算機使用領(lǐng)域的擴大和深入，解決“非數(shù)值性問題〞越來越引起人們的重視和關(guān)注。例如：-3-1.1什么是數(shù)據(jù)結(jié)構(gòu)

金融和工商企業(yè)領(lǐng)域的信息管理系統(tǒng)支持多媒體的文獻(xiàn)資料查詢 神經(jīng)元和模式識別網(wǎng)絡(luò)與通信圖形化用戶界面等等-4-1.1什么是數(shù)據(jù)結(jié)構(gòu)解決此類問題使用的數(shù)學(xué)工具已不是分析數(shù)學(xué)和計算方法，而更多地用到離散數(shù)學(xué)和計算機的有關(guān)知識，所涉及的對象也更為復(fù)雜，其突出的特點是：數(shù)據(jù)元素之間所具有的特定聯(lián)系已不能用分析數(shù)學(xué)的方程式來簡單描述。

現(xiàn)代計算機科學(xué)的觀點，計算機科學(xué)是一門研究用計算機進行信息表示和處理的科學(xué)。這里面涉及到兩個問題：-5-1.1什么是數(shù)據(jù)結(jié)構(gòu)信息的表示和信息的處理 信息的表示直接關(guān)系到處理信息的程序的效率。隨著計算機的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，為了編寫出一個“好〞的程序，必須分析待處理的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。-6-1.1什么是數(shù)據(jù)結(jié)構(gòu)重要性歷史沿革1968年D·E·Knuth發(fā)表：“Artofcomputerprogramming〞IEEE68教程1983IEEE83教程1991IEEE91教程2000IEEE2000教程國內(nèi)在78年開設(shè)、相應(yīng)地有93教程等。計算機科技的兩大支柱Algorithm+DataStructures=Programs——NiklausWirthAlgorithm:求解問題的策略DS: 問題的數(shù)學(xué)模型Programs:為計算機處理問題編制的一組指令-7-1.1什么是數(shù)據(jù)結(jié)構(gòu)實例：銀行帳號共100000個如下圖，組成一個順序存儲的結(jié)構(gòu)，存于計算機之中。插入新帳號45怎樣進行呢？插入新帳號45：1、查找位置2、移表3、插入適宜位置移動一個結(jié)點，需100us,移動100000個結(jié)點需100us×100000＝10秒。每天處理10000個帳號，需30小時，無法接受。如何快速地進行插入?節(jié)省訪問外存的時間，是一個很重要的問題。-8-1.1什么是數(shù)據(jù)結(jié)構(gòu)地位：1、“數(shù)據(jù)結(jié)構(gòu)〞在計算機科學(xué)中是一門綜合性的專業(yè)根底課。2、數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機硬件和計算機軟件三者之間的一門核心課程。3、數(shù)據(jù)結(jié)構(gòu)這一門課的內(nèi)容不僅是一般程序設(shè)計〔特別是非數(shù)值性程序設(shè)計〕的根底，而且是設(shè)計和實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要根底。-9-1.1什么是數(shù)據(jù)結(jié)構(gòu)事實證明，要想有效地使用計算機，僅掌握計算機語言而缺乏數(shù)據(jù)結(jié)構(gòu)和算法的有關(guān)知識，難以應(yīng)付眾多復(fù)雜的應(yīng)用課題。

-10-1.1什么是數(shù)據(jù)結(jié)構(gòu)一般來說，用計算機解決一個具體問題時，大致需要經(jīng)過以下幾個步驟：1〕首先要從具體問題抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型；2〕然后設(shè)計一個解此數(shù)學(xué)模型的算法；3〕最后編出程序、進行測試、調(diào)整直至得到最終解答。尋求數(shù)學(xué)模型的實質(zhì)是分析問題，從中提取操作的對象，并找出這些操作對象之間含有的關(guān)系，然后用數(shù)學(xué)的語言加以描述。例如，求解梁架結(jié)構(gòu)中應(yīng)力的數(shù)學(xué)模型為線性方程組；預(yù)報人口增長情況的數(shù)學(xué)模型為微分方程。然而，更多的非數(shù)值計算問題無法用數(shù)學(xué)方程加以描述。下面請看幾個例子。-11-1.1什么是數(shù)據(jù)結(jié)構(gòu)為了幫助同學(xué)們建立對?數(shù)據(jù)結(jié)構(gòu)?的感性認(rèn)識，下面舉幾個簡單的例子例1：學(xué)生成績單-12-1.1什么是數(shù)據(jù)結(jié)構(gòu)例1：學(xué)生成績單要求：給定學(xué)生的學(xué)號或姓名，要求打印出其成績；假設(shè)學(xué)生不存在，那么報告沒有該學(xué)生的信息。計算機處理該問題時，應(yīng)考慮：1)數(shù)據(jù)及其存儲：學(xué)生(學(xué)號,姓名,成績) structstudent{ charsNo[8]; charsName[9]; intnScore; }astStudent[200];2)根本運算的實現(xiàn)-13-1.1什么是數(shù)據(jù)結(jié)構(gòu)例2：圖書館書目檢索系統(tǒng)自動化問題例3：計算機和人對弈問題例4：多叉路口交通燈的管理問題例5：附設(shè)煤氣管道的最小費用問題例6：酒店管理系統(tǒng)中的客房分配問題-14-1.1什么是數(shù)據(jù)結(jié)構(gòu)結(jié)論描述這類非數(shù)值計算問題的數(shù)學(xué)模型不是數(shù)學(xué)方程,而是樹、表和圖之類的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)描述現(xiàn)實世界實體的數(shù)學(xué)模型及其上的操作在計算機中的表示和實現(xiàn)目前，多數(shù)高級語言尚不能直接操作這些帶結(jié)構(gòu)的數(shù)據(jù)。我們將在高級語言〔C語言〕的層次上討論如何表示這些數(shù)據(jù)和如何對它們進行操作。-15-1.2根本概念和術(shù)語數(shù)據(jù)(Data)信息的載體能輸入到計算機中被計算機程序處理的符號集數(shù)據(jù)元素(DataElement)數(shù)據(jù)的根本單位在計算機程序中作為一個整體進行考慮和處理一個數(shù)據(jù)元素可以由假設(shè)干數(shù)據(jù)項(DataItem)組成數(shù)據(jù)項是具有獨立含義的最小標(biāo)識單位數(shù)據(jù)對象(DataObject)性質(zhì)相同的數(shù)據(jù)元素的集合e.g.C={‘A’,‘B’,…,‘Z’}-16-1.2根本概念和術(shù)語-數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(DataStructure)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。即帶結(jié)構(gòu)的數(shù)據(jù)對象，它有兩層含義：第一，它包括一個具有共同特性的數(shù)據(jù)元素的集合，即數(shù)據(jù)對象。第二，它還包括一個定義在這個集合上的一組關(guān)系，即數(shù)據(jù)元素之間的“結(jié)構(gòu)〞。-17-1.2根本概念和術(shù)語-數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(DataStructure)形式定義Data_Structure=〔D,S〕D--數(shù)據(jù)對象S—該對象中各數(shù)據(jù)元素之間的關(guān)系的有限集四個根本的數(shù)據(jù)結(jié)構(gòu)集合結(jié)構(gòu)：關(guān)系集合是空集

頂點元素間無任何關(guān)系，R={}空集-18-1.2根本概念和術(shù)語-線性結(jié)構(gòu)/樹線性結(jié)構(gòu)：元素間的關(guān)系是1:1

一個結(jié)點〔除尾結(jié)點外〕有且僅有一個直接前驅(qū)

一個結(jié)點〔除頭結(jié)點外〕有且僅有一個直接后繼樹型結(jié)構(gòu)：一般樹、二叉樹、森林

一個結(jié)點可以有多個直接后繼〔除葉子結(jié)點外〕，

但只有一個直接前驅(qū)〔除根結(jié)點外〕-19-1.2根本概念和術(shù)語-圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)：元素間的關(guān)系是m:n

一個結(jié)點可以有多個直接后繼，也可以有多個直接前驅(qū)注：由于“集合〞是數(shù)據(jù)元素之間關(guān)系極為松散的一種結(jié)構(gòu)，因此可用其他結(jié)構(gòu)來表示-20-1.2根本概念和術(shù)語-邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和物理結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)研究的是數(shù)據(jù)元素及其關(guān)系的數(shù)學(xué)特性。特征從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)從具體問題抽象出來的數(shù)據(jù)模型與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān)與數(shù)據(jù)元素的相對位置無關(guān)分類線性結(jié)構(gòu)：線性表非線性結(jié)構(gòu)：樹、圖-21-1.2根本概念和術(shù)語-存儲結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)〔存儲結(jié)構(gòu)〕研究的是它們在計算機內(nèi)的實現(xiàn)方法〔映象〕。〔OR〕數(shù)據(jù)結(jié)構(gòu)在計算機中的表示對機器語言：這種實現(xiàn)是具體的對高級語言：在高級語言的層次上來討論這種實現(xiàn)，用高級語言中的數(shù)據(jù)類型來描述這種實現(xiàn)細(xì)節(jié)，不妨稱其為虛擬存儲結(jié)構(gòu)。依賴于計算機程序設(shè)計語言說明：為簡明起見，以后我們簡稱數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)——數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)——存儲結(jié)構(gòu)-22-1.2根本概念和術(shù)語-存儲結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系的表示順序映像〔順序存儲結(jié)構(gòu)〕：借助數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。

向量〔表格存儲結(jié)構(gòu)〕非順序映像〔鏈?zhǔn)酱鎯Y(jié)構(gòu)〕：借助指示元素存儲地址的指針〔Pointer〕表示數(shù)據(jù)元素之間的邏輯關(guān)系。

單鏈表、雙鏈表、多重鏈表、循環(huán)鏈表索引存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)-23-1.2根本概念和術(shù)語-存儲結(jié)構(gòu)說明：四種根本映射模型：順序〔sequential〕、鏈接〔linked〕、索引〔indexed〕和散列〔hashing〕映射。因此，我們至少可以得到4×4種可能的物理數(shù)據(jù)結(jié)構(gòu)：

sequential(sets)

linkedlists

indexedtrees

hashgraphs并不是所有的可能組合都合理-24-1.2根本概念和術(shù)語-存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是密切相關(guān)的兩個方面，任何一個算法的設(shè)計取決于選定的數(shù)據(jù)〔邏輯〕結(jié)構(gòu)，而算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu)-25-1.2根本概念和術(shù)語-抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型數(shù)據(jù)類型一個值的集合定義在該值集上的一組操作C語言中的根本數(shù)據(jù)類型intshortcharfloatdouble…抽象數(shù)據(jù)類型一個數(shù)學(xué)模型及定義在該模型上的一組操作如：矩陣+〔求轉(zhuǎn)置、加、乘、逆、特征值〕

-26-1.2根本概念和術(shù)語-抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型定義〔D,S,P〕D—數(shù)據(jù)對象

S—D上的關(guān)系集

P—對D的根本操作集ADT抽象數(shù)據(jù)類型名{ 數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉 數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉根本操作：〈根本操作的定義〉}ADT抽象數(shù)據(jù)類型名根本操作名〔參數(shù)表〕初始條件：〈初始條件描述〉操作結(jié)果：〈操作結(jié)果描述〉-27-1.2根本概念和術(shù)語-抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的特征數(shù)據(jù)抽象

對程序處理的實體的描述強調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部養(yǎng)護的接口(即外界使用它的方法)數(shù)據(jù)封裝

將實體的外部特性和其內(nèi)部實現(xiàn)細(xì)節(jié)別離，并且對外部養(yǎng)護隱藏其內(nèi)部實現(xiàn)細(xì)節(jié)認(rèn)為DT僅存在于想象之中。注意力集中在感興趣的性質(zhì)上，不關(guān)心數(shù)據(jù)的表示形式，操作的具體代碼等等。給出標(biāo)準(zhǔn)或說明。-28-1.2根本概念和術(shù)語-抽象數(shù)據(jù)類型-29-1.2根本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)的內(nèi)容包括三個層次的五個“要素〞，如下圖。-30-1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)通過程序設(shè)計語言中的類型來實現(xiàn)C抽象數(shù)據(jù)類型數(shù)據(jù)對象 結(jié)構(gòu)體根本操作 函數(shù)C++，Java抽象數(shù)據(jù)類型類class數(shù)據(jù)對象數(shù)據(jù)成員根本操作成員函數(shù)(方法)一個例子-31-1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)表示：偽語言借用程序設(shè)計語言的結(jié)構(gòu)描述---簡潔、嚴(yán)謹(jǐn)忽略程序設(shè)計語言的細(xì)節(jié)---簡潔偽C語言與C語言的區(qū)別抽象數(shù)據(jù)類型：typedef賦值：成組賦值、交換賦值選擇語句：

switch的擴展輸入/輸出：可以忽略格式串頭文件、輔助變量定義：忽略C的擴展：引入C++的引用參數(shù)表示變參-32-1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)偽C中的引用參數(shù)——C的擴展C的虛實結(jié)合：單向的值傳遞問題：如何簡單地表示返回多個值？ C支持的策略： 全局變量、將形參定義為指針類型、將返回值定義為指針類型 C++的另一種處理：引用參數(shù)

類型說明符&引用參數(shù)名 引用參數(shù)與實在參數(shù)共享存儲單元 利用引用參數(shù)表示變參(可以將在被調(diào)用函數(shù)體中改變了的值代回主調(diào)處〕-33-1.4算法和算法分析-定義和特性定義

對特定問題的求解步驟的一種描述，指令的有限序列，其中每一條指令表示一個或多個操作。特性有窮性：算法在執(zhí)行有窮步后能結(jié)束，且每一步都在有窮時間內(nèi)完成。確定性：每一指令有確切的含義，無二義。且算法只有一個入口和一個出口?？尚行裕好恳徊僮鞫伎梢酝ㄟ^已經(jīng)實現(xiàn)的根本運算執(zhí)行有限次來實現(xiàn)輸入：零個或多個輸入輸出：一個或多個輸出-34-1.4算法和算法分析-算法評價標(biāo)準(zhǔn)算法評價標(biāo)準(zhǔn)正確性〔Correctness〕首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說明〞方式給出的需求。其次，對算法是否“正確〞的理解可以有以下四個層次：程序不含語法錯誤；對于幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；通常以第3層意義的正確性作為衡量一個算法是否合格的標(biāo)準(zhǔn)。-35-1.4算法和算法分析-算法評價標(biāo)準(zhǔn)可讀性〔Readability〕算法主要是為了人的閱讀與交流，其次才是為計算機執(zhí)行。因此算法應(yīng)該易于人的理解；另一方面，晦澀難讀的程序很容易隱藏較多錯誤而難以調(diào)試健壯性〔Robustness〕當(dāng)輸入的數(shù)據(jù)非法時，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個表示錯誤或錯誤性質(zhì)的值，以便在更高的抽象層次上進行處理?！惓Ｌ幚頇C制-36-1.4算法和算法分析-算法評價標(biāo)準(zhǔn)高效率與低存儲量需求通常，效率指的是算法執(zhí)行時間；存儲量指的是算法執(zhí)行過程中所需的最大存儲空間。兩者都與問題的規(guī)模有關(guān)。-37-1.4算法和算法分析-事后統(tǒng)計算法效率的度量一個可執(zhí)行的正確的算法也有優(yōu)劣之分，通常以算法執(zhí)行時在時間和空間資源方面消耗的多寡作為評價算法優(yōu)劣的標(biāo)準(zhǔn)。事后統(tǒng)計利用計算機內(nèi)部的計時功能 doublestart,stop;time(&start); mainprocess(n,…);time(&stop); doublerunTime=stop-start;printf(〞%d%d\n",n,runTime);缺陷1、必須執(zhí)行程序2、其它因素掩蓋算法本質(zhì)〔時間統(tǒng)計量依賴于計算機的軟硬件環(huán)境〕-38-1.4算法和算法分析-時間分析事前分析估算(時間)算法的策略問題規(guī)模編程語言編譯器產(chǎn)生的機器代碼質(zhì)量機器執(zhí)行指令的速度-39-1.4算法和算法分析-時間分析時間復(fù)雜度度量定義顯然，在各種因素都不能確定的情況下，很難比較出算法的執(zhí)行時間。也就是說，使用執(zhí)行算法的絕對時間來衡量算法的效率是不適宜的。為此，可以將上述各種與計算機相關(guān)的軟、硬件因素都確定下來，這樣一個特定算法的“運行工作量〞的大小，只依賴于問題的規(guī)模〔通常用整數(shù)量n表示〕，或者說，它是問題規(guī)模的函數(shù)。-40-1.4算法和算法分析-時間分析一個算法是由控制結(jié)構(gòu)和原操作構(gòu)成的，其執(zhí)行時間取決于兩者的綜合效果。為了便于比較同一問題的不同的算法，通常的做法是：從算法中選取一種對于所研究的問題來說是根本運算的原操作，以該原操作重復(fù)執(zhí)行的次數(shù)作為算法的時間度量。一般情況下，算法中原操作重復(fù)執(zhí)行的次數(shù)是規(guī)模n的某個函數(shù)T(n)。假設(shè)，隨著問題規(guī)模n的增長，算法執(zhí)行時間的增長率和f(n)的增長率相同，那么可記作： T(n)=O(f(n)) 稱T(n)為算法的(漸近)時間復(fù)雜度-41-1.4算法和算法分析-時間分析運行時間=算法中每條語句執(zhí)行時間之和頻度：是指該語句重復(fù)執(zhí)行的次數(shù)。每條語句執(zhí)行時間=頻度*語句執(zhí)行一次所需時間設(shè)每條語句執(zhí)行一次所需時間為單位時間(漸進)時間復(fù)雜度：T(n)=O(f(n))例子常見函數(shù)的增長率：P16-42-1.4算法和算法分析-時間分析例1-4-1 for(i=1，i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}分析：……由于是一個三重循環(huán)，每個循環(huán)從1到n，那么總次數(shù)為:n×n×n=n3時間復(fù)雜度為T(n)=O(n3)-43-1.4算法和算法分析-時間分析例1-4-2{++x;s=0;}將x自增看成是根本操作，那么語句頻度為１，即時間復(fù)雜度為Ｏ(1)如果將s=0也看成是根本操作，那么語句頻度為２，其時間復(fù)雜度仍為Ｏ(1)，即常量階。-44-1.4算法和算法分析-時間分析例1-4-3for(i=1;i<=n;++i){++x;s+=x;}語句頻度為：2n其時間復(fù)雜度為：O(n)即時間復(fù)雜度為線性階。-45-1.4算法和算法分析-時間分析例1-4-4 for(i=1;i<=n;i=2^i)(1){++x;s+=x;}(2)分析：其中根本語句為(2)，設(shè)其執(zhí)行次數(shù)為f(n),那么2f(n)<=n故f(n)<=log2n=O(log2n)即時間復(fù)雜度為對數(shù)階。定理：假設(shè)A(n)=amnm+am-1nm-1+…+a1n+a0是一個m次多項式，那么A(n)=O(nm)?！沧C略〕-46-1.4算法和算法分析-時間分析例1-4-5for(i=2;i<=n;++I)for(j=2;j<=i-1;++j){++x;a[i，j]=x;}

語句頻度為：

1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2∴時間復(fù)雜度為O(n2

)

即此算法的時間復(fù)雜度為平方階.-47-1.4算法和算法分析-時間分析例1-4-6n！的遞歸算法intfac(intn){ if(n<=1)return1;(1) elsereturn(n*fac(n-1));(2)}分析：設(shè)T(n)為fac(n)的時間開銷，顯然T(1)=O(1)。 語句(1)的時間開銷為O(1)，遞歸調(diào)用fac(n-1)的時間開銷為T(n-1)，那么語句(2)的時間開銷為：O(1)+T(n-1)。那么：T(n)=O(1)+T(n-1)=O(1)+O(1)+T(n-2)=……=(n-1)*O(1)+T(1)=n*O(1)=O(n)-48-1.4算法和算法分析-時間分析例1-4-7如下為N