《數(shù)據(jù)結(jié)構(gòu)與算法》PPT課件.ppt

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

1、數(shù)據(jù)結(jié)構(gòu)與算法（Java版）2021年10月4日數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)及相關(guān)專(zhuān)業(yè)中一門(mén)重要的專(zhuān)業(yè)基礎(chǔ)課程。當(dāng)用計(jì)算機(jī)來(lái)解決實(shí)際問(wèn)題時(shí)，就要涉及到數(shù)據(jù)的表示及數(shù)據(jù)的處理，而數(shù)據(jù)表示及數(shù)據(jù)處理正是數(shù)據(jù)結(jié)構(gòu)課程的主要研究對(duì)象，通過(guò)這兩方面內(nèi)容的學(xué)習(xí)，為后續(xù)課程，特別是軟件方面的課程打下厚實(shí)的知識(shí)基礎(chǔ)，同時(shí)也提供了必要的技能訓(xùn)練。因此，數(shù)據(jù)結(jié)構(gòu)課程在計(jì)算機(jī)應(yīng)用專(zhuān)業(yè)中具有舉足輕重的作用。2021年10月4日課程任務(wù)在基礎(chǔ)方面，要求學(xué)生掌握常用數(shù)據(jù)結(jié)構(gòu)的基本概念及其不同的實(shí)現(xiàn)方法；在技能方面，通過(guò)系統(tǒng)學(xué)習(xí)能夠在不同

2、存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)不同的運(yùn)算，并對(duì)算法設(shè)計(jì)的方式和技巧有所體會(huì)。學(xué)業(yè)基礎(chǔ)本課程的先修課程為離散數(shù)學(xué)和高級(jí)語(yǔ)言程序設(shè)計(jì)。學(xué)習(xí)本課程必須具備高級(jí)語(yǔ)言程序設(shè)計(jì)(C語(yǔ)言)的基礎(chǔ)知識(shí)與基本技能。它的后續(xù)課程有操作系統(tǒng)和數(shù)據(jù)庫(kù)原理等。2021年10月4日⒈教學(xué)內(nèi)容：(1)數(shù)據(jù)結(jié)構(gòu)的概念；(2)抽象數(shù)據(jù)類(lèi)型；(3)算法和算法分析。⒉教學(xué)目的：(1)領(lǐng)會(huì)數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)的概念及其相互間的關(guān)系；(2)清楚數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的聯(lián)系與區(qū)別；(3)理解抽象數(shù)據(jù)類(lèi)型的概念；(4)掌握進(jìn)行簡(jiǎn)單算法分析的方法。第1

3、章數(shù)據(jù)結(jié)構(gòu)與算法2021年10月4日⒊教學(xué)重點(diǎn)：⑴數(shù)據(jù)、數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)的概念；⑵邏輯結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)在概念上的聯(lián)系與區(qū)別；⑶抽象數(shù)據(jù)類(lèi)型和數(shù)據(jù)抽象；⑷評(píng)價(jià)算法優(yōu)劣的標(biāo)準(zhǔn)及方法。⒋教學(xué)難點(diǎn)：⑴區(qū)別算法與程序；⑵邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的聯(lián)系與區(qū)別；⑶抽象數(shù)據(jù)類(lèi)型與數(shù)據(jù)抽象；⑷算法的時(shí)間復(fù)雜度分析。2021年10月4日1.1.1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)發(fā)展的初期，人們使用計(jì)算機(jī)的目的主要是處理數(shù)值計(jì)算問(wèn)題。由于當(dāng)時(shí)所涉及的運(yùn)算對(duì)象是簡(jiǎn)單的整型、實(shí)型或布爾類(lèi)型數(shù)據(jù)，所以程序設(shè)計(jì)者的主要精力是集中

4、于程序設(shè)計(jì)的技巧上，而無(wú)須重視數(shù)據(jù)結(jié)構(gòu)。隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大和軟、硬件的發(fā)展，非數(shù)值計(jì)算問(wèn)題越來(lái)越顯得重要。這類(lèi)問(wèn)題涉及到的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)元素之間的相互關(guān)系一般無(wú)法用數(shù)學(xué)方程式加以描述。解決這類(lèi)問(wèn)題的關(guān)鍵是要設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)，才能有效地解決問(wèn)題。1.1引言2021年10月4日【例1-1】成績(jī)檢索系統(tǒng)。要求成績(jī)檢索系統(tǒng)提供自動(dòng)查詢(xún)的功能，如查找某個(gè)學(xué)生的單科成績(jī)或平均成績(jī)，查詢(xún)某門(mén)課程的最高分等等。學(xué)號(hào)姓名考試成績(jī)平均成績(jī)高等數(shù)學(xué)C語(yǔ)言英語(yǔ)20071801吳承志90958590200

5、71802李淑芳8876918520071803劉麗9278828420071804張會(huì)友8178727720071805石寶國(guó)7682797920071806何文穎8690918920071807趙勝利7678807820071808崔文靖8293868720071809劉麗80858182………………圖1-1學(xué)生成績(jī)表【例1-2】棋盤(pán)布局問(wèn)題。要求將4個(gè)棋子布在4行4列的棋盤(pán)上，使得任兩個(gè)棋子既不在同一行或同一列，也不在同一對(duì)角線上。2021年10月4日【例1-3】教學(xué)計(jì)劃編排問(wèn)題一個(gè)教學(xué)計(jì)劃

6、包含許多課程，在教學(xué)計(jì)劃包含的許多課程之間，有些必須按規(guī)定的先后次序進(jìn)行，有些則沒(méi)有次序要求。即有些課程之間有先修和后續(xù)的關(guān)系，有些課程可以任意安排次序。這種各個(gè)課程之間的次序關(guān)系可用一個(gè)稱(chēng)作圖的數(shù)據(jù)結(jié)構(gòu)來(lái)表示，如圖所示。有向圖中的每個(gè)頂點(diǎn)表示一門(mén)課程，如果從頂點(diǎn)vi到vj之間存在有向邊，則表示課程i必須先于課程j進(jìn)行。2021年10月4日由以上三個(gè)例子可見(jiàn)，描述這類(lèi)非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹(shù)、圖之類(lèi)的數(shù)據(jù)結(jié)構(gòu)。因此，可以說(shuō)數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計(jì)算

7、的程序設(shè)計(jì)問(wèn)題中所出現(xiàn)的計(jì)算機(jī)操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。2021年10月4日1、數(shù)據(jù)結(jié)構(gòu)課程的發(fā)展數(shù)據(jù)結(jié)構(gòu)作為一門(mén)獨(dú)立的課程在國(guó)外是從1968年才開(kāi)始的，但在此之前其有關(guān)內(nèi)容已散見(jiàn)于編譯原理及操作系統(tǒng)之中。從20世紀(jì)60年代末到70年代初，出現(xiàn)了大型程序，軟件也相對(duì)獨(dú)立，結(jié)構(gòu)程序設(shè)計(jì)成為程序設(shè)計(jì)方法學(xué)的主要內(nèi)容，人們?cè)絹?lái)越重視數(shù)據(jù)結(jié)構(gòu)。從70年代中期到80年代，各版本的數(shù)據(jù)結(jié)構(gòu)著作相繼出現(xiàn)。1.1.2數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容2021年10月4日數(shù)據(jù)結(jié)構(gòu)課程集中討論軟件開(kāi)發(fā)過(guò)程中的設(shè)計(jì)階段、

8、同時(shí)涉及編碼和分析階段的若干基本問(wèn)題。此外，為了構(gòu)造出好的數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)，還需考慮數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)的評(píng)價(jià)與選擇。因此，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容包括三個(gè)層次的五個(gè)“要素”。2、數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容2021年10月4日1.2.1有關(guān)概念和術(shù)語(yǔ)1、數(shù)據(jù)數(shù)據(jù)是信息的載體，是所有能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的符號(hào)的總稱(chēng)。2、數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)（DataItem）是具有獨(dú)立含義的標(biāo)識(shí)單位，是數(shù)據(jù)不可分割的最小單位。3、數(shù)據(jù)元素?cái)?shù)據(jù)元素（DataElement）是數(shù)據(jù)的基本單位。4、數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象（Dat