《數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 (1).ppt》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 (1).ppt（62頁珍藏版）》請在匯文網(wǎng)上搜索。

1、算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)2 2第一章第一章 緒論緒論課程簡介課程簡介算法與數(shù)據(jù)結(jié)構(gòu)3 3 3 3n編寫高質(zhì)量的編寫高質(zhì)量的程序程序n(1)(1)能夠分析研究計算機加工的對象的特性，能夠分析研究計算機加工的對象的特性，選擇合適的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)并設(shè)計相應(yīng)的選擇合適的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)并設(shè)計相應(yīng)的算法；算法；n(2)(2)提高處理復雜程序設(shè)計問題的能力，要求提高處理復雜程序設(shè)計問題的能力，要求編寫的程序結(jié)構(gòu)正確、清晰、易讀；編寫的程序結(jié)構(gòu)正確、清晰、易讀；n(3)(3)掌握算法的時間復雜度和空間復雜度的分掌握算法的時間復雜度和空間復雜度的分析技術(shù)。析技術(shù)。u學習數(shù)據(jù)結(jié)構(gòu)有什么用？學習數(shù)據(jù)結(jié)構(gòu)

2、有什么用？算法與數(shù)據(jù)結(jié)構(gòu)4 4 4 4數(shù)據(jù)結(jié)構(gòu)課程的重要性數(shù)據(jù)結(jié)構(gòu)課程的重要性n后后續(xù)課程（數(shù)據(jù)程（數(shù)據(jù)庫、操作系、操作系統(tǒng)、人工智能、人工智能、編譯等）的等）的基基礎(chǔ)n碩士研究生入學考士研究生入學考試課程程n2002年前：年前：專業(yè)課兩兩張卷，各卷，各100分分 (多數(shù)高校多數(shù)高校數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)構(gòu)占占100分分)n2003-2008：專業(yè)課一一張卷，卷，150分分 (部分高校只考部分高校只考數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)，構(gòu)，如如華中中 科大、北京交大、江科大、北京交大、江蘇大學等大學等)n2009-專業(yè)基基礎(chǔ)綜合一合一張卷卷 全國統(tǒng)考全國統(tǒng)考 (4科，科，數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)構(gòu)占占45分分)n2013-專業(yè)基基礎(chǔ)綜合

3、一合一張卷卷 全國統(tǒng)考全國統(tǒng)考/自主命題自主命題 (暨南大學、深圳大學等只考數(shù)據(jù)南大學、深圳大學等只考數(shù)據(jù)結(jié)構(gòu)構(gòu) )算法與數(shù)據(jù)結(jié)構(gòu)5 5教材與參考教材與參考書n教材：算法與數(shù)據(jù)結(jié)構(gòu)教材：算法與數(shù)據(jù)結(jié)構(gòu)(c+語言版語言版)，馮廣慧，電子工業(yè)出版社馮廣慧，電子工業(yè)出版社n參考書：參考書：n算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第3版）陳守孔版）陳守孔，機械，機械工工業(yè)出版社出版社 n數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)構(gòu) C語言版言版 嚴蔚敏蔚敏 清清華大學出版社大學出版社n數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)與算法分析構(gòu)與算法分析 C+描述（第描述（第3版）版）Mark Allen Weiss著著 人民人民郵電出版社出版社

4、nD.E.Knuth.The Art of Computer Programming.Addison-Wesley Educational Publishers Inc算法與數(shù)據(jù)結(jié)構(gòu)6 6授課與授課與考核考核方式方式算法與數(shù)據(jù)結(jié)構(gòu)n授課方式授課方式n知識點視頻知識點視頻：80余節(jié)余節(jié)n考核方式考核方式n視頻觀看率視頻觀看率 20%20%n實驗作業(yè)完成率實驗作業(yè)完成率 10%10%n測驗通過率測驗通過率 10%10%n期末筆試分數(shù)期末筆試分數(shù) 50%50%7 7第一章第一章 緒論緒論課程簡介課程簡介算法與數(shù)據(jù)結(jié)構(gòu)8 8第一章第一章 緒論1.4 抽象數(shù)據(jù)抽象數(shù)據(jù)類型型 1.3 算法和算法分析算法和

5、算法分析 1.2 基本概念和基本概念和術(shù)語1.1 什么是數(shù)據(jù)什么是數(shù)據(jù)結(jié)構(gòu)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)9 9例例1.1 學生信息管理系學生信息管理系統(tǒng) 算法與數(shù)據(jù)結(jié)構(gòu)在在這類問題中：中：(1)計算機算機處理的理的對象是各種表；象是各種表；(2)元素之元素之間的的邏輯關(guān)系是關(guān)系是線性關(guān)系；性關(guān)系；(3)施加于施加于對象上的操作有遍象上的操作有遍歷、查找、插入、找、插入、刪除等。除等。1010例例1.2 人機博弈人機博弈 在在這類問題中：中：(1)計算機算機處理的理的對象是象是樹型型結(jié)構(gòu)；構(gòu)；(2)元素元素間的關(guān)系是一種一的關(guān)系是一種一對多的多的層次關(guān)系；次關(guān)系；(3)施加于施加于對象上的操作有遍象上的操作有

6、遍歷、查找、插入、找、插入、刪除等。除等。算法與數(shù)據(jù)結(jié)構(gòu)1111例例1.3 哥尼斯堡七哥尼斯堡七橋問題 在在這類問題中：中：(1)計算機算機處理的理的對象是各種象是各種圖；(2)元素元素間的關(guān)系是復的關(guān)系是復雜的的圖形或網(wǎng)狀關(guān)系，是一種多形或網(wǎng)狀關(guān)系，是一種多對多多的關(guān)系；的關(guān)系；(3)施加于施加于對象上的操作有遍象上的操作有遍歷、查找、插入、找、插入、刪除等。除等。算法與數(shù)據(jù)結(jié)構(gòu)1212什么是數(shù)據(jù)什么是數(shù)據(jù)結(jié)構(gòu)構(gòu)n沒有標準的定義，但有共識沒有標準的定義，但有共識n數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：簡單地說，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值簡單地說，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它

7、們計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作的學科之間的關(guān)系和操作的學科。算法與數(shù)據(jù)結(jié)構(gòu)1313第一章第一章 緒論1.4 抽象數(shù)據(jù)抽象數(shù)據(jù)類型型 1.3 算法和算法分析算法和算法分析 1.2 基本概念和基本概念和術(shù)語1.1 什么是數(shù)據(jù)什么是數(shù)據(jù)結(jié)構(gòu)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)14141.2 基本概念和基本概念和術(shù)語1數(shù)據(jù)（數(shù)據(jù)（Data）是信息的）是信息的載體，是描述客體，是描述客觀事物的數(shù)、字事物的數(shù)、字符、以及所有能符、以及所有能輸入到入到計算機中，被算機中，被計算機程序算機程序識別和和處理理的符號的集合。的符號的集合。2數(shù)據(jù)元素（數(shù)據(jù)元素（Data Element）是數(shù)據(jù)中的一個）

8、是數(shù)據(jù)中的一個“個體個體”，是數(shù)據(jù)的基本是數(shù)據(jù)的基本單位。在有些情況下數(shù)據(jù)元素也稱位。在有些情況下數(shù)據(jù)元素也稱為元素、元素、結(jié)點、點、頂點、點、記錄等。數(shù)據(jù)元素用于完整地描述一個等。數(shù)據(jù)元素用于完整地描述一個對象。象。如：一個學生如：一個學生記錄、棋、棋盤中的一個格局、中的一個格局、圖中的一個中的一個頂點等。點等。3數(shù)據(jù)數(shù)據(jù)項(Data Item)是是組成數(shù)據(jù)元素的有特定意成數(shù)據(jù)元素的有特定意義的的不可分割的最小不可分割的最小單位。如構(gòu)成一個數(shù)據(jù)元素的字段、域、屬位。如構(gòu)成一個數(shù)據(jù)元素的字段、域、屬性等都可稱之性等都可稱之為數(shù)據(jù)數(shù)據(jù)項。數(shù)據(jù)元素是數(shù)據(jù)。數(shù)據(jù)元素是數(shù)據(jù)項的集合。的集合。如：學生信

9、息表中的學號、姓名、性如：學生信息表中的學號、姓名、性別、專業(yè)等。等。算法與數(shù)據(jù)結(jié)構(gòu)15154數(shù)據(jù)數(shù)據(jù)對象象(Data Object)是具有相同性是具有相同性質(zhì)的數(shù)據(jù)元素的的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。集合，是數(shù)據(jù)的一個子集。如：整數(shù)數(shù)據(jù)如：整數(shù)數(shù)據(jù)對象是集合象是集合N=0，1，2，字，字母字符數(shù)據(jù)母字符數(shù)據(jù)對象是字符集合象是字符集合C=a，b，z，學生，學生數(shù)據(jù)數(shù)據(jù)對象等。象等。5數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)（構(gòu)（Data Structure）通）通過抽象的方法研究一抽象的方法研究一組有特定關(guān)系的數(shù)據(jù)的存有特定關(guān)系的數(shù)據(jù)的存儲與與處理，理，數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)主要研究三個構(gòu)主要研究三個方面的方面的內(nèi)容內(nèi)容。(

10、1)數(shù)據(jù)之數(shù)據(jù)之間的的邏輯關(guān)系，即數(shù)據(jù)的關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；構(gòu)；(2)數(shù)據(jù)及其數(shù)據(jù)及其邏輯關(guān)系如何在關(guān)系如何在計算機中存算機中存儲實現(xiàn)，即數(shù)據(jù)的，即數(shù)據(jù)的存存儲結(jié)構(gòu)；構(gòu)；(3)在某種存在某種存儲模式下，模式下，對數(shù)據(jù)施加的操作是如何數(shù)據(jù)施加的操作是如何實現(xiàn)的，的，即運算即運算實現(xiàn)。算法與數(shù)據(jù)結(jié)構(gòu)1.2 基本概念和基本概念和術(shù)語16161616數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三要素的三要素 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等 線性結(jié)構(gòu)線性結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu)順序順序鏈式鏈式索引索引散列散列

11、線性表線性表 棧和隊列棧和隊列 字符串字符串樹樹 圖圖 算法與數(shù)據(jù)結(jié)構(gòu)17176數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)集合結(jié)構(gòu)：集合結(jié)構(gòu)：元素間的次序是任意的。元素之間除了元素間的次序是任意的。元素之間除了“屬于同一集合屬于同一集合”的聯(lián)系外沒有其他的關(guān)系。的聯(lián)系外沒有其他的關(guān)系。線性結(jié)構(gòu)線性結(jié)構(gòu)：數(shù)據(jù)元素的有序序列。除了第一個和最：數(shù)據(jù)元素的有序序列。除了第一個和最后一個元素外，其余元素都有一個前趨和一個后繼，后一個元素外，其余元素都有一個前趨和一個后繼，1對對1樹形結(jié)構(gòu)樹形結(jié)構(gòu)：除了根元素外，每個節(jié)點有且僅有一個：除了根元素外，每個節(jié)點有且僅有一個前趨，后繼數(shù)目不限前趨，后繼數(shù)目不限，1對多對多圖型

12、結(jié)構(gòu)圖型結(jié)構(gòu)：每個元素的前趨和后繼數(shù)目都不限，多：每個元素的前趨和后繼數(shù)目都不限，多對多對多算法與數(shù)據(jù)結(jié)構(gòu)1.2 基本概念和基本概念和術(shù)語18181818算法與數(shù)據(jù)結(jié)構(gòu)6數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)1.2 基本概念和基本概念和術(shù)語19197數(shù)據(jù)的存數(shù)據(jù)的存儲結(jié)構(gòu)構(gòu)(1)順序存序存儲結(jié)構(gòu)：借助元素在存構(gòu)：借助元素在存儲器中的相器中的相對位置表示數(shù)據(jù)元素之位置表示數(shù)據(jù)元素之間的關(guān)系，通常用數(shù)的關(guān)系，通常用數(shù)組來來實現(xiàn)。(2)鏈接存接存儲結(jié)構(gòu)：借助表示元素存構(gòu)：借助表示元素存儲地址的指地址的指針顯式地指出元素之式地指出元素之間的的邏輯關(guān)系，關(guān)系，邏輯上相上相鄰的元素其物理位置不要求相的元素其物理位置

13、不要求相鄰，通常借助指，通常借助指針實現(xiàn)。采用。采用鏈接存接存儲結(jié)構(gòu)除了存構(gòu)除了存儲數(shù)據(jù)元素本身之外數(shù)據(jù)元素本身之外還要存要存儲指示元素指示元素間關(guān)系的指關(guān)系的指針。(3)哈希（散列）存哈希（散列）存儲方式：是方式：是專用于集合用于集合結(jié)構(gòu)的數(shù)據(jù)存放方式。在哈構(gòu)的數(shù)據(jù)存放方式。在哈希存希存儲中，用一個哈希函數(shù)將數(shù)據(jù)元素按關(guān)中，用一個哈希函數(shù)將數(shù)據(jù)元素按關(guān)鍵字和一個唯一的存字和一個唯一的存儲位置位置關(guān)關(guān)聯(lián)起來。方法是根據(jù)起來。方法是根據(jù)設(shè)定好的哈希函數(shù)定好的哈希函數(shù)f(key)和和處理沖突的理沖突的規(guī)則將一將一組關(guān)關(guān)鍵字映象到一個有限的字映象到一個有限的連續(xù)的地址集的地址集(區(qū)區(qū)間)上。上。(4

14、)索引存索引存儲方式：數(shù)據(jù)元素被排成一個序列方式：數(shù)據(jù)元素被排成一個序列：d1，d2，dn，每，每個個結(jié)點點d 在序列里都有在序列里都有對應(yīng)的位序的位序i，位序可以作，位序可以作為結(jié)點的索引存點的索引存儲在索在索引表中。引表中。檢索索時利用利用結(jié)點的點的順序號序號i來確定來確定結(jié)點的存點的存儲地址。地址。算法與數(shù)據(jù)結(jié)構(gòu)1.2 基本概念和基本概念和術(shù)語20208數(shù)據(jù)的運算數(shù)據(jù)的運算(1)創(chuàng)建：創(chuàng)建某種數(shù)據(jù)結(jié)構(gòu)；創(chuàng)建：創(chuàng)建某種數(shù)據(jù)結(jié)構(gòu)；(2)清除：刪除數(shù)據(jù)結(jié)構(gòu)；清除：刪除數(shù)據(jù)結(jié)構(gòu)；(3)插入：在數(shù)據(jù)結(jié)構(gòu)指定的位置上插入一個新元素；插入：在數(shù)據(jù)結(jié)構(gòu)指定的位置上插入一個新元素；(4)刪除：將數(shù)據(jù)結(jié)構(gòu)中

15、的某個元素刪去；刪除：將數(shù)據(jù)結(jié)構(gòu)中的某個元素刪去；(5)搜索：在數(shù)據(jù)結(jié)構(gòu)中搜索滿足特定條件的元素；搜索：在數(shù)據(jù)結(jié)構(gòu)中搜索滿足特定條件的元素；(6)更新：修改數(shù)據(jù)結(jié)構(gòu)中的某個元素的值；更新：修改數(shù)據(jù)結(jié)構(gòu)中的某個元素的值；(7)訪問：訪問數(shù)據(jù)結(jié)構(gòu)中的某個元素；訪問：訪問數(shù)據(jù)結(jié)構(gòu)中的某個元素；(8)遍歷：按照某種次序訪問數(shù)據(jù)結(jié)構(gòu)中的每一元素，使每遍歷：按照某種次序訪問數(shù)據(jù)結(jié)構(gòu)中的每一元素，使每個元素恰好被訪問一次；個元素恰好被訪問一次；算法與數(shù)據(jù)結(jié)構(gòu)1.2 基本概念和基本概念和術(shù)語21212121自自測題1 1在數(shù)據(jù)在數(shù)據(jù)結(jié)構(gòu)中，從構(gòu)中，從邏輯上可以將之分上可以將之分為()。A.動態(tài)結(jié)構(gòu)和靜構(gòu)和靜態(tài)

16、結(jié)構(gòu)構(gòu)B.緊湊湊結(jié)構(gòu)和非構(gòu)和非緊湊湊結(jié)構(gòu)構(gòu)C.內(nèi)部內(nèi)部結(jié)構(gòu)和外部構(gòu)和外部結(jié)構(gòu)構(gòu) D.線性性結(jié)構(gòu)和非構(gòu)和非線性性結(jié)構(gòu)構(gòu)【中南大學中南大學2005一一.1(2分分)】D算法與數(shù)據(jù)結(jié)構(gòu)22222222算法與數(shù)據(jù)結(jié)構(gòu)自自測題2 2地址元素鏈接地址1000Ha1010H1004Hb100CH1008Hc1000H100CHdNULL1010He1004H1014H己知表頭元素為己知表頭元素為c c的單鏈表在內(nèi)存中的存儲狀態(tài)如下表所示。的單鏈表在內(nèi)存中的存儲狀態(tài)如下表所示?，F(xiàn)將現(xiàn)將f f放于放于1014H1014H處并插入到單鏈表中，若處并插入到單鏈表中，若f f在邏輯上位在邏輯上位a a和和e e之之間，則間，則a a，e e，f f的鏈接地址的鏈接地址”依次是依次是()()。A A1010H,1014H,1004H 1010H,1014H,1004H B B1010H,1004H,1014H1010H,1004H,1014HC C1014H,1010H,1004H 1014H,1010H,1004H D D1014H,1004H,1010H1014H,1004H,1010H【20122012年