數(shù)據(jù)結(jié)構(gòu)之1緒論ppt課件.ppt

《數(shù)據(jù)結(jié)構(gòu)之1緒論ppt課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第一章緒論§1.1數(shù)據(jù)結(jié)構(gòu)的概念早期：數(shù)值計(jì)算——運(yùn)算對(duì)象是簡(jiǎn)單的整型、實(shí)型或布爾類型數(shù)據(jù)中后期：非數(shù)值計(jì)算——處理對(duì)象是類型復(fù)雜的數(shù)據(jù)，數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程式加以描述1例1：“學(xué)生”表格2例2：八皇后問題(用四皇后描述)????????????............四皇后問題的狀態(tài)樹3課程編號(hào)課程名稱先修課程C1計(jì)算機(jī)導(dǎo)論無C2數(shù)據(jù)結(jié)構(gòu)C1，C4C3匯編語言C1C4C程序設(shè)計(jì)語言C1C5計(jì)算機(jī)圖形學(xué)C2，C3，C4C6接口技術(shù)C3C7數(shù)據(jù)庫原理C2，C9C8編譯原理C4C9操作系統(tǒng)C2例3：教學(xué)計(jì)劃編排問題（a）計(jì)算機(jī)專業(yè)的

2、課程設(shè)置4C1C2C3C6C4C5C9C7C8（b）表示課程之間優(yōu)先關(guān)系的有向圖5例4：城市的煤氣管道問題（a）結(jié)點(diǎn)間管道的代價(jià)（b）最經(jīng)濟(jì)的管道鋪設(shè)6描述這類非數(shù)值計(jì)算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是一門研究（非數(shù)值計(jì)算的）程序設(shè)計(jì)問題中所出現(xiàn)的計(jì)算機(jī)操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。7課程學(xué)習(xí)前掌握的基本概念：數(shù)據(jù)數(shù)據(jù)元素（數(shù)據(jù)成員）數(shù)據(jù)對(duì)象8數(shù)據(jù)：數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)（數(shù)值、字符等）的集合。數(shù)據(jù)元素（數(shù)據(jù)成員）:是數(shù)據(jù)

3、的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。9數(shù)據(jù)對(duì)象：具有相同性質(zhì)的數(shù)據(jù)元素（數(shù)據(jù)成員）的集合。整數(shù)數(shù)據(jù)對(duì)象N={0,?1,?2,…}學(xué)生數(shù)據(jù)對(duì)象10數(shù)據(jù)結(jié)構(gòu)由某一數(shù)據(jù)對(duì)象及該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系組成。記為：Data_Structure={D,R}其中，D是某一數(shù)據(jù)對(duì)象，R是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。數(shù)據(jù)結(jié)構(gòu)的形式定義11數(shù)據(jù)結(jié)構(gòu)涉及三個(gè)方面：1.數(shù)據(jù)的邏輯結(jié)構(gòu)-----從用戶視圖看，是面向問題的。2.數(shù)據(jù)的物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）-----從具體實(shí)現(xiàn)視圖看，是面向計(jì)算機(jī)的。3.相關(guān)的操作及其實(shí)現(xiàn)。E

4、xample:學(xué)生表：邏輯結(jié)構(gòu)-----線性表物理結(jié)構(gòu)-----數(shù)組,鏈表操作-----插入,刪除,查找12數(shù)據(jù)結(jié)構(gòu)包括“邏輯結(jié)構(gòu)”和“物理結(jié)構(gòu)”兩個(gè)方面(層次):邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)成員之間的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)成員的集合和定義在此集合上的若干關(guān)系來表示;物理結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示和實(shí)現(xiàn)，故又稱“存儲(chǔ)結(jié)構(gòu)”。13邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系（某種順序）上觀察數(shù)據(jù)，它是獨(dú)立于計(jì)算機(jī)的；可以在理論上、形式上進(jìn)行研究、推理、運(yùn)算等各種操作。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，是依賴于計(jì)算機(jī)的；是數(shù)據(jù)的最終組織

5、形式。任何一個(gè)算法的設(shè)計(jì)取決于選定的邏輯結(jié)構(gòu)；而算法的最終實(shí)現(xiàn)依賴于采用的存儲(chǔ)結(jié)構(gòu)。14根據(jù)問題來建立邏輯結(jié)構(gòu)例如：Class=(D,S)數(shù)據(jù)集合：D={a,b1,…,bn,c1,…cn,d1,…dn}關(guān)系集合：S={R1,R2}R1={,,}//班長(zhǎng)-組長(zhǎng)R2={,,

6、j=2,3,…,n}//組長(zhǎng)-組員15ab1c1b2b3bn…c2c3cn…d2d3dn…d1班級(jí)Class的邏輯結(jié)構(gòu)的圖示16存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象。數(shù)據(jù)元素的映象：任何數(shù)據(jù)元素在計(jì)算機(jī)中最

7、終都是轉(zhuǎn)化成一個(gè)二進(jìn)制的位串。關(guān)系的映象：…17關(guān)系的映象方法：（關(guān)系對(duì)?x,y?）1.順序映象（順序存儲(chǔ)方法）：以相對(duì)的存儲(chǔ)位置表示后繼關(guān)系例如:令y的存儲(chǔ)位置和x的存儲(chǔ)位置之間差一個(gè)常量C，而C是一個(gè)隱含值，整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息xy182.鏈?zhǔn)接诚螅ㄦ溄哟鎯?chǔ)方法）:以附加信息(指針)表示后繼關(guān)系需要用一個(gè)和x在一起的附加信息（指針)指示y的存儲(chǔ)位置yx193.索引存儲(chǔ)方法4.散列存儲(chǔ)方法20線性結(jié)構(gòu)：表、棧、隊(duì)列非線性結(jié)構(gòu)層次結(jié)構(gòu)：樹，二叉樹，堆網(wǎng)狀結(jié)構(gòu)：圖其它：集合數(shù)據(jù)結(jié)構(gòu)的分類21線性結(jié)構(gòu)bindevetclibuser前驅(qū)

8、后繼22非線性結(jié)構(gòu)——層次結(jié)構(gòu)樹二叉樹141312111234567891098745623123堆（特殊的樹結(jié)構(gòu)）“最大”堆“最小”堆12354871110291641012115123698724圖結(jié)構(gòu)12564312543611331814665161921網(wǎng)絡(luò)結(jié)構(gòu)非線性結(jié)構(gòu)——群結(jié)構(gòu)25§1.2數(shù)據(jù)結(jié)構(gòu)的抽象形式C語言中的數(shù)據(jù)類型charintfloatdoublevoid字符型整型浮點(diǎn)型雙精度型無值數(shù)據(jù)類型定義：一組性質(zhì)相同的值的集合,以及定義于這個(gè)值集合上的一組操作的總稱.26不同類型的變量，其所能取的值的范圍不同，所能進(jìn)行的操作不同。

9、例如：整型(int)值的范圍是：-32768~32767（16位）操作是：+，-，*，/，%27抽象數(shù)據(jù)類型(ADTs:A