數(shù)據(jù)結(jié)構(gòu)與算法——c語(yǔ)言和java語(yǔ)言描述 ppt及答案和其他資源01 緒論

1、唐懿芳,數(shù)據(jù)結(jié)構(gòu)與算法---C語(yǔ)言和Java語(yǔ)言描述,,01 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義,02 數(shù)據(jù)結(jié)構(gòu)的基本概念,03 算法及其描述,針對(duì)實(shí)際問(wèn)題，編寫出一個(gè)高效率的處理程序，就需要解決如何合理地組織數(shù)據(jù)，建立合適的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)較好的算法，來(lái)提高程序執(zhí)行效率這樣的問(wèn)題。數(shù)據(jù)結(jié)構(gòu)和算法就是在此背景下形成和發(fā)展起來(lái)的。,,簡(jiǎn)而言之，軟件開(kāi)發(fā)要多動(dòng)腦筋、想到好的解決辦法才能更快更好地編寫出效率更高的程序。數(shù)據(jù)結(jié)構(gòu)和算法這門課程的

2、目的正是使學(xué)生更快地編寫出更高效的程序。,后兩個(gè)條件比較容易實(shí)現(xiàn)，而第一個(gè)條件則需要花很多時(shí)間和精力才能夠達(dá)到，而它恰恰是區(qū)分程序設(shè)計(jì)人員水平高低的一個(gè)重要標(biāo)志。數(shù)據(jù)結(jié)構(gòu)貫穿程序設(shè)計(jì)的始終，缺乏數(shù)據(jù)結(jié)構(gòu)和算法的功底，很難設(shè)計(jì)出高水平的具有專業(yè)水準(zhǔn)的應(yīng)用程序。瑞士著名的計(jì)算機(jī)科學(xué)家尼古拉斯·沃思（Niklaus·Wirth）提出了“算法+數(shù)據(jù)結(jié)構(gòu)=程序”的觀點(diǎn)，這正說(shuō)明了數(shù)據(jù)結(jié)構(gòu)的重要性。,即使是在廣泛采用可視化程序設(shè)

3、計(jì)的今天，借助于集成開(kāi)發(fā)環(huán)境可以很快地生成程序，但要想成為一個(gè)專業(yè)的程序開(kāi)發(fā)人員，至少需要以下三個(gè)條件：（1）能夠熟練地選擇和設(shè)計(jì)各種業(yè)務(wù)邏輯的數(shù)據(jù)結(jié)構(gòu)和算法。（2）至少能夠熟練地掌握一門程序設(shè)計(jì)語(yǔ)言。（3）熟知所涉及的相關(guān)應(yīng)用領(lǐng)域知識(shí)。,,1.1.1 引言,2 邏輯結(jié)構(gòu)的延伸及基本算法3.物理結(jié)構(gòu)4.運(yùn)算集合（基本操作）,1.邏輯結(jié)構(gòu) (1) 線性結(jié)構(gòu)。結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)一的線性關(guān)系。 (2) 樹(shù)結(jié)構(gòu)。結(jié)

4、構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)多的層次關(guān)系。 (3) 圖結(jié)構(gòu)。結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對(duì)多的任意關(guān)系。,,1.1.2 數(shù)據(jù)結(jié)構(gòu)研究什么,線性結(jié)構(gòu)：除第一個(gè)和最后一個(gè)數(shù)據(jù)元素外，每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)和一個(gè)后繼數(shù)據(jù)元素。,樹(shù)結(jié)構(gòu)：除根結(jié)點(diǎn)外，每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素，可有０個(gè)或若干個(gè)后繼數(shù)據(jù)元素。,圖結(jié)構(gòu)：每個(gè)數(shù)據(jù)元素可有０個(gè)或若干個(gè)前驅(qū)數(shù)據(jù)元素和０個(gè)或若干個(gè)后繼數(shù)據(jù)元素。,,01 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義,02 數(shù)

5、據(jù)結(jié)構(gòu)的基本概念,03 算法及其描述,例如，學(xué)生信息可包括學(xué)生的學(xué)號(hào)、姓名、性別、年齡等數(shù)據(jù)。這些數(shù)據(jù)構(gòu)成學(xué)生情況的描述的數(shù)據(jù)項(xiàng)；包括學(xué)號(hào)、姓名、性別、年齡等數(shù)據(jù)項(xiàng)的一組數(shù)據(jù)就構(gòu)成學(xué)生信息的一個(gè)數(shù)據(jù)元素。,數(shù)據(jù)：人們利用文字符號(hào)、數(shù)字符號(hào)以及其他規(guī)定的符號(hào)對(duì)現(xiàn)實(shí)世界的事物及其活動(dòng)所做的抽象描述。數(shù)據(jù)元素：表示一個(gè)事物的一組數(shù)據(jù)。數(shù)據(jù)項(xiàng)：構(gòu)成數(shù)據(jù)元素的數(shù)據(jù)。抽象數(shù)據(jù)元素：沒(méi)有實(shí)際含義的數(shù)據(jù)元素。抽象數(shù)據(jù)元素的數(shù)據(jù)類型：沒(méi)有確

6、切定義的數(shù)據(jù)類型。數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的相互聯(lián)系方式。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)方式。數(shù)據(jù)的操作：對(duì)一種數(shù)據(jù)類型的數(shù)據(jù)進(jìn)行的某種處理。數(shù)據(jù)的操作集合：對(duì)一種數(shù)據(jù)類型的數(shù)據(jù)進(jìn)行的所有操作。,基本術(shù)語(yǔ),順序存儲(chǔ)結(jié)構(gòu)：把數(shù)據(jù)元素存儲(chǔ)在一塊連續(xù)地址空間的內(nèi)存中，其特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素在物理上也相鄰，數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在數(shù)據(jù)元素存儲(chǔ)位置關(guān)系上。,指針是指向物理存儲(chǔ)單元地址的變量。由數(shù)據(jù)元素域和指針域組成的一

7、個(gè)結(jié)構(gòu)體稱為結(jié)點(diǎn)。,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：使用指針把相互直接關(guān)聯(lián)的結(jié)點(diǎn)(即直接前驅(qū)結(jié)點(diǎn)或直接后繼結(jié)點(diǎn))鏈接起來(lái)，其特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰，數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在結(jié)點(diǎn)的鏈接關(guān)系上。,順序存儲(chǔ)結(jié)構(gòu),鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),從抽象角度，數(shù)據(jù)的操作主要討論某種數(shù)據(jù)類型數(shù)據(jù)應(yīng)具備的操作的邏輯功能，抽象角度下的操作一般和數(shù)據(jù)的邏輯結(jié)構(gòu)一起討論；,具體來(lái)說(shuō)，數(shù)據(jù)的操作主要討論操作的具體實(shí)現(xiàn)算法。具體問(wèn)題的操作實(shí)現(xiàn)必須在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)確定后才能進(jìn)行

8、。,數(shù)據(jù)結(jié)構(gòu)課程主要討論線性表、堆棧、隊(duì)列、串、數(shù)組、樹(shù)、二叉樹(shù)、圖等典型的常用數(shù)據(jù)結(jié)構(gòu)。在討論這些典型數(shù)據(jù)結(jié)構(gòu)時(shí)，主要從它們的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)操作三個(gè)方面進(jìn)行分析討論。,,01 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義,02 數(shù)據(jù)結(jié)構(gòu)的基本概念,03 算法及其描述,,算法是描述求解問(wèn)題方法的操作步驟集合。,文字形式 : 用中文或英文這樣的文字來(lái)描述算法。偽碼形式 : 用一種仿程序設(shè)計(jì)語(yǔ)言的語(yǔ)言來(lái)描述算法。程序設(shè)計(jì)語(yǔ)言形式 :

9、用某種程序設(shè)計(jì)語(yǔ)言描述算法。其優(yōu)點(diǎn)是算法不用修改，直接作為程序語(yǔ)句鍵入計(jì)算機(jī)，計(jì)算機(jī)能調(diào)用和運(yùn)行。,1.3.1 算法的概念和特定,,算法是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。此外，一個(gè)算法還具有下列五個(gè)重要特性 :,有窮性 確定性 可行性 輸入 輸出,現(xiàn)在，品牌忠誠(chéng)度成為最熱門的詞，消費(fèi)者的“情感”被當(dāng)作品牌要攻陷的最后堡壘。于是品牌整合營(yíng)銷、客戶關(guān)系管理等成為了鞏固

10、品牌的熱門手段，精耕細(xì)作、不盲目追求銷售量的提升速度是這個(gè)階段的特征。,1.3.2 算法設(shè)計(jì)的要求,,算法設(shè)計(jì)的好壞關(guān)乎程序的執(zhí)行效率，算法設(shè)計(jì)必須滿足以下要求：,正確性 可讀性 健壯性 效率與低存儲(chǔ)量需求,現(xiàn)在，品牌忠誠(chéng)度成為最熱門的詞，消費(fèi)者的“情感”被當(dāng)作品牌要攻陷的最后堡壘。于是品牌整合營(yíng)銷、客戶關(guān)系管理等成為了鞏固品牌的熱門手段，精耕細(xì)作、不盲目追求銷售量的提升速度是這個(gè)階段的特征。,1.3.3 算法的分析,,1.

11、算法效率的度量 算法執(zhí)行的時(shí)間是其對(duì)應(yīng)的程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間。程序在計(jì)算機(jī)上運(yùn)行所需時(shí)間與下列因素有關(guān)：算法本身選用的策略；書(shū)寫程序的語(yǔ)言；編譯產(chǎn)生的機(jī)器代碼質(zhì)量；機(jī)器執(zhí)行指令的速度；,1.3.3 算法的分析,,2. 算法的時(shí)間復(fù)雜度可用算法中語(yǔ)句的執(zhí)行次數(shù)來(lái)度量一個(gè)算法的效率。語(yǔ)句頻度是指語(yǔ)句在一個(gè)算法中重復(fù)執(zhí)行的次數(shù)。以下給出了兩個(gè)n×n階矩陣相乘算法中的各條語(yǔ)句以及每條語(yǔ)句的語(yǔ)句頻度。

12、 語(yǔ)句 語(yǔ)句頻度 for（i=0；i< n;i++） n＋1 for （j=0；j<n;j++） n2＋n {c[i][j]=0; n2

13、 for (k=0;k< n; k++) n3＋n2 c[i][j]=c[i][j]+a[i][k]*b[k][j]; n3 },1.3.3 算法的分析,,所有語(yǔ)句的總執(zhí)行次數(shù)為Tn=2n3+3n2 +2n+1, 即語(yǔ)句總的執(zhí)行次數(shù)是問(wèn)題的規(guī)模（矩陣的階）n的函數(shù)f(n)（Tn= f(n)）。 上式是Tn= f(n

14、)中忽略其系數(shù)的n的最高冪次項(xiàng)，它表示隨問(wèn)題規(guī)模n的增大算法的執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。如上算法的時(shí)間復(fù)雜度T(n)=O(n3)。 算法中n的最高次冪項(xiàng)與算法中稱作原操作的語(yǔ)句的語(yǔ)句頻度對(duì)應(yīng)，原操作是算法中實(shí)現(xiàn)基本運(yùn)算的操作，在上面的算法中的原操作是c[i][j]=c[i][j]+a[i][k]*b[k][j]。一般情況下原操作由最深層循環(huán)內(nèi)的語(yǔ)句實(shí)現(xiàn)。

15、 算法的時(shí)間復(fù)雜度記作： T(n)=O(f(n)),1.3.3 算法的分析,,T(n)隨n的增大而增大，增長(zhǎng)的越慢，其算法的時(shí)間復(fù)雜度越低。下列三個(gè)程序段中分別給出了原操作count++的三個(gè)不同數(shù)量級(jí)的時(shí)間復(fù)雜度。（1）count++ ；其時(shí)間復(fù)雜度為O(1) ，稱之為常量階時(shí)間復(fù)雜度（2）for (i=1; i<= n; i++)

16、 count++; 其時(shí)間復(fù)雜度為O(n)，是線性階時(shí)間復(fù)雜度 （3）for (i=1; i<= n; i++) for (j=1;j<= n; j++) count++; 其時(shí)間復(fù)雜度為O(n2)，平方階時(shí)間復(fù)雜度此外，算法能呈現(xiàn)的時(shí)間復(fù)雜度還有：對(duì)數(shù)階O(log2n),指數(shù)階O(2n)等,1.3.3 算法的分析,,常見(jiàn)的時(shí)

17、復(fù)雜度O(1) 常數(shù)階、O(n)線性階、O(n2)平方階、O(n3)立方階、O(2n)指數(shù)階、O(log2n)對(duì)數(shù)階與O(nlog2n)。時(shí)間復(fù)雜度（從小到大排列）的比較如表1.2所示 :,1.3.3 算法的分析,,3.算法的空間復(fù)雜度 采用空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度，記作： S(n)=O(f (n))其中n為問(wèn)題的規(guī)模。 程序執(zhí)行時(shí)，除了需存儲(chǔ)本身所用的指令，常數(shù)