數(shù)據(jù)結(jié)構(gòu)與算法（Java語(yǔ)言版）課件 第1章 數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介

第1章數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介2024/11/91主要內(nèi)容邏輯結(jié)構(gòu)物理結(jié)構(gòu)算法與結(jié)構(gòu)1.1邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)是指有限多個(gè)節(jié)點(diǎn)（結(jié)點(diǎn)，頂點(diǎn)，元素）之間的邏輯關(guān)系，不涉及節(jié)點(diǎn)（結(jié)點(diǎn)，頂點(diǎn)，元素）在計(jì)算機(jī)中的存儲(chǔ)位置。2024/11/92主要的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)，樹(shù)形結(jié)構(gòu)，圖結(jié)構(gòu)和集合這四種結(jié)構(gòu)。⒈線性結(jié)構(gòu)2024/11/93在實(shí)際生活中，經(jīng)常遇到具有線性結(jié)構(gòu)的一組數(shù)據(jù)，比如，中國(guó)農(nóng)歷的二十四節(jié)氣：立春、雨水、驚蟄、春分、清明、谷雨、立夏、小滿、芒種、夏至、小暑、大暑、立秋、處暑、白露、秋分、寒露、霜降、立冬、小雪、大雪、冬至、小寒、大寒2024/11/94⒈線性結(jié)構(gòu)2024/11/95⒈線性結(jié)構(gòu)2024/11/96⒈線性結(jié)構(gòu)2024/11/972024/11/982.

樹(shù)結(jié)構(gòu)

2024/11/992.

樹(shù)結(jié)構(gòu)用倒置的樹(shù)形示意一個(gè)樹(shù)2024/11/9102.

樹(shù)結(jié)構(gòu)一個(gè)樹(shù)T=(A,R)

由多個(gè)互不相交的樹(shù)構(gòu)成2024/11/9112.

樹(shù)結(jié)構(gòu)樹(shù)的每個(gè)結(jié)點(diǎn)至多有2個(gè)子結(jié)點(diǎn)，稱這樣的樹(shù)是二叉樹(shù)二叉查詢樹(shù)，特點(diǎn)是，每個(gè)結(jié)點(diǎn)上的值都大于等于它的左子樹(shù)上的結(jié)點(diǎn)里的值、小于它的右子樹(shù)上結(jié)點(diǎn)里的值。首先猜m是上面的二叉樹(shù)的根結(jié)點(diǎn)中的數(shù)，如果猜測(cè)錯(cuò)誤，反饋信息給你，你猜測(cè)的比根結(jié)點(diǎn)中的數(shù)大，那你就繼續(xù)猜測(cè)這個(gè)數(shù)是當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)，如果告知你，你猜測(cè)的數(shù)不大于根結(jié)點(diǎn)中的數(shù)，那你就繼續(xù)猜測(cè)這個(gè)數(shù)是當(dāng)前節(jié)點(diǎn)的左子結(jié)點(diǎn)，依次類推，您可以較快的猜測(cè)到這個(gè)數(shù)。2024/11/9122.

樹(shù)結(jié)構(gòu)樹(shù)的層從上至下，從0層開(kāi)始根結(jié)點(diǎn)沒(méi)有父結(jié)點(diǎn)，非根、非葉結(jié)點(diǎn)有且只有一個(gè)父結(jié)點(diǎn)，但有一個(gè)或多個(gè)子結(jié)點(diǎn)，葉結(jié)點(diǎn)有且只有一個(gè)父結(jié)點(diǎn)，但沒(méi)有子結(jié)點(diǎn)。根據(jù)樹(shù)結(jié)構(gòu)的這個(gè)特點(diǎn)，可以把樹(shù)的結(jié)點(diǎn)按層次分類：樹(shù)的結(jié)點(diǎn)按層次分類，從根開(kāi)始定義，根為第0層，根的子結(jié)點(diǎn)為第1層，以此類推。每一層上的結(jié)點(diǎn)只能和上一層中的至多一個(gè)結(jié)點(diǎn)有關(guān)系，但可能和下一層的0個(gè)或多個(gè)結(jié)點(diǎn)有關(guān)系。2024/11/9133.

圖結(jié)構(gòu)鋼筋焊接起來(lái)的平面架中的焊點(diǎn)：a,b,c,d,e2024/11/9143.

圖結(jié)構(gòu)鋼筋焊接起來(lái)的平面架中的焊點(diǎn)：a,b,c,d,e

這個(gè)圖結(jié)構(gòu)中，人們規(guī)定(a,b)和(b,a)是一樣的（都代表同一根鋼筋），即(a,b)和(b,a)都是沒(méi)有方向的“標(biāo)量”邊，這樣的圖結(jié)構(gòu)稱作無(wú)向圖2024/11/9153.

圖結(jié)構(gòu)當(dāng)V×V的子集E滿足下列①和②時(shí)，稱E是V上的圖關(guān)系，記作G=(V,E)

2024/11/9163.

圖結(jié)構(gòu)當(dāng)V×V的子集E滿足下列①和②時(shí)，稱E是V上的圖關(guān)系，記作G=(V,E)

對(duì)于G=(V,E)，如果(a,b)是邊，那么默認(rèn)(b,a)也就是邊，并規(guī)定(a,b)邊等于(b,a)邊，這樣規(guī)定的G=(V,E)是無(wú)向圖，簡(jiǎn)稱V是無(wú)向圖，即無(wú)向圖的邊是沒(méi)有方向的。無(wú)向圖2024/11/9173.

圖結(jié)構(gòu)當(dāng)V×V的子集E滿足下列①和②時(shí)，稱E是V上的圖關(guān)系，記作G=(V,E)

如果(a,b)，(b,a)都是邊，就規(guī)定(a,b)邊不等于(b,a)邊，這樣規(guī)定的G=(V,E)是有向圖，簡(jiǎn)稱V是有向圖，即有向圖的邊是有方向的。2024/11/9184.

集合集合A中的元素除了同屬一個(gè)集合外，無(wú)其它任何關(guān)系，即關(guān)系集合是空集合，可表示為(A,?)（?是A×A的空子集）2024/11/919對(duì)于(A,R)，計(jì)算機(jī)程序在存儲(chǔ)空間中存放集合A的節(jié)點(diǎn)（結(jié)點(diǎn)，頂點(diǎn)，元素）的形式，稱為A的節(jié)點(diǎn)（結(jié)點(diǎn)，頂點(diǎn)，元素）的物理結(jié)構(gòu)，也稱為A的存儲(chǔ)結(jié)構(gòu)。1.2物理結(jié)構(gòu)比如，對(duì)于一個(gè)線性表，可根據(jù)需要采用順序存儲(chǔ)（節(jié)點(diǎn)的物理地址是依次相鄰的）或鏈?zhǔn)酱鎯?chǔ)（節(jié)點(diǎn)的物理地址不必是相鄰的）。常用的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)和哈希存儲(chǔ)等，有關(guān)細(xì)節(jié)見(jiàn)后續(xù)的章節(jié)，例如，第4章至第11章2024/11/920實(shí)施于集合上的算法，在其執(zhí)行完畢后，必須保持集合的邏輯結(jié)構(gòu)不變，比如，對(duì)于線性表，實(shí)施了增加或刪除節(jié)點(diǎn)的操作后，要保證新的節(jié)點(diǎn)構(gòu)成的集合仍然是線性結(jié)構(gòu)，否則算法必須對(duì)當(dāng)前的線性表的節(jié)點(diǎn)進(jìn)行