數(shù)據(jù)結(jié)構(gòu) C C++ 第一章 緒論

1、.第一章 緒論.知 識 點 數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語 算法描述和分析方法 難 點 算法復(fù)雜性的分析方法 要 求 了解數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，算法的基本概念，它們對于程序設(shè)計的重要性以及相互關(guān)系 掌握算法復(fù)雜性的概念及分析方法 . 1.1 基本概念 1.2 算法的描述 1.3 算法的評價 1.4 應(yīng)用舉例及分析 小 結(jié) 習(xí)題與練習(xí) .分析程序處理的數(shù)據(jù)的特性及數(shù)據(jù)之間的關(guān)系，這就是“數(shù)據(jù)結(jié)構(gòu)”這門學(xué)科形成和發(fā)展的背景。數(shù)據(jù)結(jié)構(gòu)主要研究非數(shù)值應(yīng)用問題中數(shù)據(jù)之間的邏輯關(guān)系和對數(shù)據(jù)的操作，同時還研究如何將具有邏輯關(guān)系的數(shù)據(jù)按一定的存儲方式存放在計算機內(nèi)。例: 某單位職工檔案的管理。圖1.1中的

2、職工檔案表就是一個數(shù)據(jù)結(jié)構(gòu)。如果把表中的一行看成一個記錄并稱為一個結(jié)點，則在此表中，結(jié)點和結(jié)點之間的關(guān)系是一種最簡單的線性關(guān)系。. 某學(xué)校教師的名冊。雖然可以用例1.1中的二維表格將全校教師的名單列出，但采用圖1.2所示的結(jié)構(gòu)更好。它像一棵根在上而倒掛的樹，清晰地描述了教師所在的系和教研組，這樣一來可以從樹根沿著某系某教研組很快找到某個教師，查找的過程就是從樹根沿分支到某個葉子的過程。.例 在n個城市之間建立通信網(wǎng)絡(luò)，要求在其中任意兩個城市之間都有直接的或間接的通信線路，在已知某些城市之間直接通信線路預(yù)算造價的情況下，使網(wǎng)絡(luò)的造價最低。.通過上面三個例子可以看出：數(shù)據(jù)結(jié)構(gòu)中元素和元素之間存在著

3、邏輯關(guān)系，而線性表，樹，圖是三種基本的邏輯結(jié)構(gòu)，其他各類的數(shù)據(jù)結(jié)構(gòu)都是由這三種基本結(jié)構(gòu)派生的。數(shù)據(jù)結(jié)構(gòu)就是解決如何分析數(shù)據(jù)元素之間的關(guān)系、如何確立合適的邏輯結(jié)構(gòu)、如何存儲這些數(shù)據(jù)，并對為完成數(shù)據(jù)操作所設(shè)計的算法做出時間和空間的分析。“數(shù)據(jù)結(jié)構(gòu)”在計算機科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課，它不僅是一般程序設(shè)計(特別是非數(shù)值計算的程序設(shè)計)的基礎(chǔ)，而且也是設(shè)計和實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及大型應(yīng)用程序的重要基礎(chǔ)。.數(shù)據(jù)(Data)：一切能夠由計算機接受和處理的對象。 數(shù)據(jù)元素(Data element)：是數(shù)據(jù)的基本單位，在程序中作為一個整體加以考慮和處理。 數(shù)據(jù)項(Data item)：是數(shù)

4、據(jù)的不可分割的最小單位，在有些場合下，數(shù)據(jù)項又稱為字段或域。 .數(shù)據(jù)結(jié)構(gòu)(Data structure)：數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。研究數(shù)據(jù)結(jié)構(gòu)，是指研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系數(shù)據(jù)的物理結(jié)構(gòu)：數(shù)據(jù)元素在計算機存儲器中是如何存儲的四類基本邏輯結(jié)構(gòu)的示意圖 .定義一組有關(guān)數(shù)據(jù)元素的運算。在討論各種數(shù)據(jù)結(jié)構(gòu)時，針對其邏輯結(jié)構(gòu)和具體的存儲結(jié)構(gòu)給出對應(yīng)的數(shù)據(jù)類型，進一步在確定的數(shù)據(jù)類型上實現(xiàn)各種操作。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機存儲器中的實現(xiàn)。數(shù)據(jù)元素在計算機中主要有兩種不同的存儲方法：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。順序存儲的特點是在內(nèi)存中開辟一組

5、連續(xù)的空間(高級語言中的數(shù)組)來存放數(shù)據(jù)。鏈式存儲的特點是通過指針反映數(shù)據(jù)元素之間的邏輯關(guān)系，又稱動態(tài)存儲。.算法(Algorithm)：對特定問題求解步驟的一種描述。程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法”。算法是一個有窮的規(guī)則序列，這些規(guī)則決定了解決某一特定問題的一系列運算。由此問題相關(guān)的一定輸入，計算機依照這些規(guī)則進行計算和處理，經(jīng)過有限的計算步驟后能得到一定的輸出。 返回.1、框圖算法描述：這種描述方法在算法研究的早期曾流行過。它的優(yōu)點是直觀、易懂，但用來描述比較復(fù)雜的算法就顯得不夠方便，也不夠清晰簡潔。例：求兩個整數(shù)m,n(mn)的最大公因子 算法的描述方法有很多，根據(jù)描述算法語言的不同，可將

6、算法分為以下四種：.2、非形式算法描述 ： 用中文語言，同時還使用一些程序設(shè)計語言中的語句來描述算法，這稱為非形式算法描述。a. 求余數(shù)求余數(shù) 以以n 除除m， 并令并令r為余數(shù)為余數(shù) (0 r n)；b. 余數(shù)是零否余數(shù)是零否 若若r = 0 則結(jié)束算法，則結(jié)束算法，n 就是最大公就是最大公因子；因子；c. 替換并返回替換并返回a 若若r 0 則則m n, n r返回返回 a。例：求兩個整數(shù)m,n(mn)的最大公因子.3、C語言描述： 這是可在計算機上運行并獲得結(jié)果的算法，使給定問題能在有限時間內(nèi)被求解，通常這種算法也稱程序。本書將采用C語言描述算法，所有算法都以如下所示的函數(shù)形式表示： 函

7、數(shù)類型 函數(shù)名（參數(shù)表） 語句序列 例：求兩個整數(shù)m,n(mn)的最大公因子int max_common_factor (int m, int n) int r ; r = m % n; while (r != 0) m = n ; n = r ; r = m % n; return n ;.正確性：算法應(yīng)能正確地實現(xiàn)處理要求 。易讀性：有助于對算法的理解，便于糾正和擴充 。簡單性：使證明其正確性比較容易，對算法進行修改也比較方便。高效率：達到所需的時、空性能。 .算法的復(fù)雜性包括時間復(fù)雜性（所需運算時間）和空間復(fù)雜性（所占存儲空間) 。一個算法所需的運算時間通常與所解決問題的規(guī)模大小有關(guān)。是

8、該算法中所有語句執(zhí)行次數(shù)之和。用n 表示問題規(guī)模的量 ，把算法運行所需的時間T表示為n的函數(shù)，記為T(n)。時間復(fù)雜性：當n逐漸增大時T(n)的極限情況，一般簡稱為時間復(fù)雜性。時間復(fù)雜性常用數(shù)量級的形式來表示，記作T(n)=O(f(n)。 其中，大寫字母O為Order(數(shù)量級)的字頭，f(n)為函數(shù)形式，如T(n)=O(n2)。.算法的運行時間往往還與具體輸入的數(shù)據(jù)有關(guān)，通常用以下兩種方法來確定一個算法的運算時間：1. 平均時間復(fù)雜性：研究同樣的n值時各種可能的輸入，取它們運算時間的平均值。2. 最壞時間復(fù)雜性：研究各種輸入中運算最慢的一種情況下的運算時間。 .計算下面交換i和j內(nèi)容程序段的時

9、間復(fù)雜性。 temp=i; i=j; j=temp; 解：以上三條單個語句均執(zhí)行1次，該程序段的執(zhí)行時間是一個與問題n無關(guān)的常數(shù)，因此，算法的時間復(fù)雜度為常數(shù)階,記作T(n)=O(1). .計算下面求累加和程序段的時間復(fù)雜性 （1） sum=0； （一次） （2） for(i=1;i=n;i+) （n次 ） （3） for(j=1;j=n;j+) （n2次 ） （4） sum+； （n2次 ）解：T(n)=2n2+n+1 =O(n2) 當T(n)為多項式時,可只取其最高次冪項,且它的系數(shù)也可略去不寫。返回.一般地，對于足夠大的n，常用的時間復(fù)雜性存在以下順序： O(1) O(logn) O(n) O(n*logn) O(n2) O(n3)O(2n)O(3n)O(n!) 其中,O(1)為常數(shù)數(shù)量級,.本章介紹了貫穿全書的基本概念和基本思想。 數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)算法算法的時間復(fù)雜性 返回.試寫一算法，自大至小依次輸出順序讀入的三個整數(shù)X，Y和Z的值。.實驗?zāi)康模毫私獬绦蛟O(shè)計的一般步驟實驗要求：1、掌握C語言算法的描述形式2、掌握程序編輯方法和程序風(fēng)格3、了解程序設(shè)計的步驟和