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

1、.第一章 緒論.知 識(shí) 點(diǎn) 數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語 算法描述和分析方法 難 點(diǎn) 算法復(fù)雜性的分析方法 要 求 了解數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，算法的基本概念，它們對(duì)于程序設(shè)計(jì)的重要性以及相互關(guān)系 掌握算法復(fù)雜性的概念及分析方法 . 1.1 基本概念 1.2 算法的描述 1.3 算法的評(píng)價(jià) 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)系和對(duì)數(shù)據(jù)的操作，同時(shí)還研究如何將具有邏輯關(guān)系的數(shù)據(jù)按一定的存儲(chǔ)方式存放在計(jì)算機(jī)內(nèi)。例: 某單位職工檔案的管理。圖1.1中的

2、職工檔案表就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。如果把表中的一行看成一個(gè)記錄并稱為一個(gè)結(jié)點(diǎn)，則在此表中，結(jié)點(diǎn)和結(jié)點(diǎn)之間的關(guān)系是一種最簡(jiǎn)單的線性關(guān)系。. 某學(xué)校教師的名冊(cè)。雖然可以用例1.1中的二維表格將全校教師的名單列出，但采用圖1.2所示的結(jié)構(gòu)更好。它像一棵根在上而倒掛的樹，清晰地描述了教師所在的系和教研組，這樣一來可以從樹根沿著某系某教研組很快找到某個(gè)教師，查找的過程就是從樹根沿分支到某個(gè)葉子的過程。.例 在n個(gè)城市之間建立通信網(wǎng)絡(luò)，要求在其中任意兩個(gè)城市之間都有直接的或間接的通信線路，在已知某些城市之間直接通信線路預(yù)算造價(jià)的情況下，使網(wǎng)絡(luò)的造價(jià)最低。.通過上面三個(gè)例子可以看出：數(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)、如何存儲(chǔ)這些數(shù)據(jù)，并對(duì)為完成數(shù)據(jù)操作所設(shè)計(jì)的算法做出時(shí)間和空間的分析?！皵?shù)據(jù)結(jié)構(gòu)”在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課，它不僅是一般程序設(shè)計(jì)(特別是非數(shù)值計(jì)算的程序設(shè)計(jì))的基礎(chǔ)，而且也是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及大型應(yīng)用程序的重要基礎(chǔ)。.數(shù)據(jù)(Data)：一切能夠由計(jì)算機(jī)接受和處理的對(duì)象。 數(shù)據(jù)元素(Data element)：是數(shù)據(jù)的基本單位，在程序中作為一個(gè)整體加以考慮和處理。 數(shù)據(jù)項(xiàng)(Data item)：是數(shù)

4、據(jù)的不可分割的最小單位，在有些場(chǎng)合下，數(shù)據(jù)項(xiàng)又稱為字段或域。 .數(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ù)元素在計(jì)算機(jī)存儲(chǔ)器中是如何存儲(chǔ)的四類基本邏輯結(jié)構(gòu)的示意圖 .定義一組有關(guān)數(shù)據(jù)元素的運(yùn)算。在討論各種數(shù)據(jù)結(jié)構(gòu)時(shí)，針對(duì)其邏輯結(jié)構(gòu)和具體的存儲(chǔ)結(jié)構(gòu)給出對(duì)應(yīng)的數(shù)據(jù)類型，進(jìn)一步在確定的數(shù)據(jù)類型上實(shí)現(xiàn)各種操作。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)。數(shù)據(jù)元素在計(jì)算機(jī)中主要有兩種不同的存儲(chǔ)方法：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)的特點(diǎn)是在內(nèi)存中開辟一組

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

6、算法分為以下四種：.2、非形式算法描述 ： 用中文語言，同時(shí)還使用一些程序設(shè)計(jì)語言中的語句來描述算法，這稱為非形式算法描述。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。例：求兩個(gè)整數(shù)m,n(mn)的最大公因子.3、C語言描述： 這是可在計(jì)算機(jī)上運(yùn)行并獲得結(jié)果的算法，使給定問題能在有限時(shí)間內(nèi)被求解，通常這種算法也稱程序。本書將采用C語言描述算法，所有算法都以如下所示的函數(shù)形式表示： 函

7、數(shù)類型 函數(shù)名（參數(shù)表） 語句序列 例：求兩個(gè)整數(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)能正確地實(shí)現(xiàn)處理要求 。易讀性：有助于對(duì)算法的理解，便于糾正和擴(kuò)充 。簡(jiǎn)單性：使證明其正確性比較容易，對(duì)算法進(jìn)行修改也比較方便。高效率：達(dá)到所需的時(shí)、空性能。 .算法的復(fù)雜性包括時(shí)間復(fù)雜性（所需運(yùn)算時(shí)間）和空間復(fù)雜性（所占存儲(chǔ)空間) 。一個(gè)算法所需的運(yùn)算時(shí)間通常與所解決問題的規(guī)模大小有關(guān)。是

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

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