1、,DATA,10,65,865,姓名 學(xué)號(hào) 成績(jī) 班級(jí) 李紅 9761059 95 機(jī)97.6,數(shù)據(jù)結(jié)構(gòu),第二章數(shù)據(jù)結(jié)構(gòu)與算法,2.1 概述 數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。,第二章數(shù)據(jù)結(jié)構(gòu)與算法,2.1 概述 數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。,能輸入到計(jì)算機(jī)中 并能被計(jì)算機(jī)程序處理的 符號(hào)的集合。,整數(shù)(1,2)、實(shí)數(shù)(1.1,1.2) 字符串(Beijing)、 圖形、聲音。,第二章數(shù)據(jù)結(jié)構(gòu)與算法,2.1 概述 數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。,計(jì)算機(jī)管理圖書問(wèn)題 在圖書館里有各種卡片：有按書名編排的、 有按作者編排的

2、、有按分類編排 如何將查詢圖書的這些信息存入計(jì)算機(jī)中 既要考慮查詢時(shí)間短，又要考慮節(jié)省空間,第二章數(shù)據(jù)結(jié)構(gòu)與算法,2.1 概述 數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。,最簡(jiǎn)單的辦法之一是建立一張表， 每一本書的信息在表中占一行，如,第二章數(shù)據(jù)結(jié)構(gòu)與算法,2.1 概述 數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。,如何將0,1,2,3,4,5,6,7,8,9這10個(gè)數(shù)存放在 計(jì)算機(jī)中能最快地達(dá)到你所需要的目的？ 目的不同，最佳的存儲(chǔ)方方法就不同。 從大到小排列：9,8,7,6,5,4,3,2,1,0 輸出偶數(shù)：0,2,4,6,8,1,3,5,7,9,數(shù)據(jù)元素在 計(jì)算

3、機(jī)中的表示,第二章數(shù)據(jù)結(jié)構(gòu)與算法,2.1 概述 數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。,對(duì)數(shù)據(jù)結(jié)構(gòu)中的節(jié)點(diǎn)進(jìn)行 操作處理 (插入、刪除、修改、查找、排序),數(shù)據(jù)元素(Data Element),數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體。 有時(shí)一個(gè)數(shù)據(jù)元數(shù)可由若干數(shù)據(jù)項(xiàng)(Data Item)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。,數(shù)據(jù)元素亦稱節(jié)點(diǎn)或記錄。,名詞解釋,數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）,有限個(gè)數(shù)據(jù)元素的集合,有限個(gè)節(jié)點(diǎn)間關(guān)系的集合,1數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A 順序存儲(chǔ),B

4、鏈?zhǔn)酱鎯?chǔ),線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個(gè)主要問(wèn)題,數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）,1數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A 順序存儲(chǔ),B 鏈?zhǔn)酱鎯?chǔ),線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個(gè)主要問(wèn)題,數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）,我和你們的邏輯結(jié)構(gòu)是師生結(jié)構(gòu),我和你們?cè)诮淌抑械奈恢酶鶕?jù)要求而不同,1數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A 順序存儲(chǔ),B 鏈?zhǔn)酱鎯?chǔ),線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu)

5、,數(shù)據(jù)結(jié)構(gòu)的三個(gè)主要問(wèn)題,數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）,線性結(jié)構(gòu),A , B , C , ，X ,Y , Z,學(xué) 生 成 績(jī) 表,線性表結(jié)點(diǎn)間是以線性關(guān)系聯(lián)結(jié),1數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A 順序存儲(chǔ),B 鏈?zhǔn)酱鎯?chǔ),線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面,數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）,樹形結(jié)構(gòu),全校學(xué)生檔案管理的組織方式,計(jì)算機(jī)程序管理系統(tǒng)也是典型的樹形結(jié)構(gòu),樹形結(jié)構(gòu) 結(jié)點(diǎn)間具有分層次的連接關(guān)系,1數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪

6、除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A 順序存儲(chǔ),B 鏈?zhǔn)酱鎯?chǔ),線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面,(亦稱物理結(jié)構(gòu)),D= 1 , 2 , 3 , 4 R=(1,2) , (1,3) , (1,4) , (2,3) (3,4) , (2,4) ,D= 1 , 2 , 3 R= (1,2) , (2,3) , (3,2) , (1,3) ,圖形結(jié)構(gòu)節(jié)點(diǎn)間的連結(jié)是任意的,1數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A 順序存儲(chǔ),B 鏈?zhǔn)酱鎯?chǔ),線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面,(亦稱物

7、理結(jié)構(gòu)),元素n,.,元素i,.,元素2,元素1,Lo,Lo+m,Lo+(i-1)*m,Lo+（n-1)*m,存儲(chǔ)地址,存儲(chǔ)內(nèi)容,Loc(a)=Lo+（i-1)*m,順序存儲(chǔ),每個(gè)元素所占用 的存儲(chǔ)單元個(gè)數(shù),元素n,.,元素i,.,元素2,元素1,存儲(chǔ)內(nèi)容,順序存儲(chǔ)結(jié)構(gòu)常用于線性數(shù)據(jù)結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里。,順序存儲(chǔ)結(jié)構(gòu)的三個(gè)弱點(diǎn)： 1.作插入或刪除操作時(shí)，需移動(dòng)大量元數(shù)。 2.長(zhǎng)度變化較大時(shí)，需按最大空間分配。 3.表的容量難以擴(kuò)充。,1數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A 順序存

8、儲(chǔ),B 鏈?zhǔn)酱鎯?chǔ),線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面,(亦稱物理結(jié)構(gòu)),1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,鏈?zhǔn)酱鎯?chǔ),每個(gè)節(jié)點(diǎn)都由兩部分組成：數(shù)據(jù)域和指針域。 數(shù)據(jù)域存放元素本身的數(shù)據(jù)， 指針域存放指針。 數(shù)據(jù)元素之間邏輯上的聯(lián)系由指針來(lái)體現(xiàn)。,1536,元素2,1400,元素1,1346,元素3,元素4,head,鏈?zhǔn)酱鎯?chǔ),1345,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,鏈?zhǔn)酱鎯?chǔ),1.比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小 (每個(gè)節(jié)點(diǎn)都由數(shù)據(jù)域和指針愈組成)。 2.邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰。 3.插入

9、、刪除靈活 (不必移動(dòng)節(jié)點(diǎn)，只要改變節(jié)點(diǎn)中的指針)。,鏈接存儲(chǔ)結(jié)構(gòu)特點(diǎn)：,總之，有下列四種基本結(jié)構(gòu): 集合: 數(shù)據(jù)元素之間屬于一個(gè)集合,別無(wú)其他關(guān)系. 線性結(jié)構(gòu): 結(jié)構(gòu)中的數(shù)據(jù)元素存在著線性(一對(duì)一)的關(guān)系. 樹形結(jié)構(gòu): 結(jié)構(gòu)中的數(shù)據(jù)元素存在著層次(一對(duì)多)的關(guān)系. 圖形結(jié)構(gòu): 結(jié)構(gòu)中的數(shù)據(jù)元素存在著任意(多對(duì)多)的關(guān)系.,1數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A 順序存儲(chǔ),B 鏈?zhǔn)酱鎯?chǔ),線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面,(亦稱物理結(jié)構(gòu)),數(shù)據(jù)結(jié)構(gòu)側(cè)重于解決問(wèn)題的策略和方法，即研究算法。 它不但要

10、求給出問(wèn)題的一種算法，還要求算法的時(shí)空效率高、算法結(jié)構(gòu)和可讀性好、容易驗(yàn)證等等。,2.1.3 算法的基本概念,算法：是對(duì)特定問(wèn)題求解步驟的一種描述。,算法的五個(gè)特性： 有窮性、確定性、可行性、輸入和輸出。,評(píng)價(jià)算法： 正確性、易讀性、健壯性、效率和低存儲(chǔ)量。,算法的五個(gè)特性： 有窮性： 一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束。 確定性： 算法的每一步必須是確切定義的。對(duì)于相同輸入必須得到相同結(jié)果 。 可行性： 算法的每一步都是能夠?qū)崿F(xiàn)的，即可操作的。 有輸出： 算法執(zhí)行完畢，必須有一個(gè)或若干個(gè)輸出結(jié)果。,評(píng)價(jià)算法： 正確性： 對(duì)于一切合法輸入都能產(chǎn)生滿足規(guī)格要求的結(jié)果。 易讀性： 算法要便于閱讀，有

11、助于人們對(duì)算法的理解。 健壯性： 當(dāng)輸入非法數(shù)據(jù)時(shí)，也能正常作出反應(yīng)和處理。 效率和低存儲(chǔ)量： 對(duì)相同規(guī)模的問(wèn)題，運(yùn)行時(shí)間短、 占用空間少。,算法的時(shí)間復(fù)雜度: 算法中實(shí)現(xiàn)基本操作的語(yǔ)句（基本語(yǔ)句）重復(fù)執(zhí)行的次數(shù)，稱為算法的頻度。 記作：T(n)=O(f(n) 隨問(wèn)題規(guī)模n的增大，算法的頻度T(n)和f(n)的增長(zhǎng)率同階。 例1： x+=5; 單個(gè)語(yǔ)句的頻度為1，則 程序段的時(shí)間復(fù)雜度為T(n)=O(1)。,例 for (i=1; i=n; +i) /* n+1 */ for (j=1; j=n; +j) /* n(n+1) */ c ij=0; /* n2 */ - T(n)=2n2+2n+1 當(dāng)n充分大時(shí)， T(n)與n2是同階的。 該算法時(shí)間復(fù)雜度為：T(n)=O(n2),作業(yè)： P72 第1、2、3題,P72 第2題,(a)解 i=1+2+3+n =(1+n)*n/2 O(i)=O(n2),1in,1in,P72 第2題,(b)解 1=1+1+1+1 =(1+1)*n/2 =n O(1)=O(n),1in,1in,P72 第2題,(c)解 I2=12+22+32+n