數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語課件.ppt

《數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語課件.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)課程類別：專業(yè)選修學(xué)時、學(xué)分?jǐn)?shù)：48學(xué)時3學(xué)分考核方式與要求：考查課程介紹重要性數(shù)學(xué)軟件硬件數(shù)據(jù)結(jié)構(gòu)章節(jié)介紹緒論4線性表6棧和隊(duì)列6串1數(shù)組和廣義表1樹和二叉樹9圖9查找6內(nèi)部排序6數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)集合順序?qū)崿F(xiàn)鏈?zhǔn)綄?shí)現(xiàn)操作，算法5數(shù)組和廣義表4串3棧和隊(duì)列2線性表7圖6樹和二叉樹主要內(nèi)容10排序9查找?guī)c(diǎn)要求上課請關(guān)機(jī)不遲到，不曠課準(zhǔn)備筆記本機(jī)房禁止玩游戲，上網(wǎng)，吃東西第一章緒論學(xué)習(xí)目的：掌握數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語。重點(diǎn)難點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的基本概念。1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語教學(xué)內(nèi)容1.1什么是數(shù)據(jù)結(jié)

2、構(gòu)IT計算機(jī)科學(xué)家pascal語言的創(chuàng)始人NiklausWirth（尼古拉斯·沃斯）教授在1976年出版了一本書：“Algorithms+DataStructures=Programs”說明了算法和數(shù)據(jù)結(jié)構(gòu)是進(jìn)行程序設(shè)計的兩大要素。1.計算機(jī)是怎么解決問題的？很多數(shù)值計算問題的數(shù)學(xué)模型通?？捎靡唤M線性或非線性的代數(shù)方程組或微分方程組來描述：如：結(jié)構(gòu)靜力分析計算---線性代數(shù)方程組，全球天氣預(yù)報---環(huán)流模式方程抽象模型設(shè)計算法調(diào)試測試編碼得出結(jié)果如今計算機(jī)所處理的是大量的非數(shù)值計算的程序設(shè)計問題：例1**數(shù)據(jù)庫管理系統(tǒng)例2計算機(jī)對弈：數(shù)學(xué)模型：表格和數(shù)

3、據(jù)庫數(shù)學(xué)模型：樹形結(jié)構(gòu)例3交叉路口的紅綠燈管理。如今十字路口橫豎兩個方向都有三個紅綠燈，分別控制左拐、直行和右拐，那么如何控制這些紅綠燈既使交通不堵塞，又使流量最大呢？數(shù)學(xué)模型：圖狀結(jié)構(gòu)例4煤氣管道的鋪設(shè)問題。如下圖：需為城市的各小區(qū)之間鋪設(shè)煤氣管道，對n個小區(qū)只需鋪設(shè)n-1條管線，由于地理環(huán)境不同等因素使各條管線所需投資不同(如圖上所標(biāo)識)，如何使投資成本最低？數(shù)學(xué)模型：圖狀結(jié)構(gòu)綜合各種程序設(shè)計問題，抽取它具體的物理含義，就可以得到兩類數(shù)學(xué)模型：和數(shù)值計算相關(guān)的數(shù)學(xué)模型：（非）線性代數(shù)方程，常微分方程--計算數(shù)學(xué)非數(shù)值計算問題的數(shù)學(xué)模型：數(shù)學(xué)模型的表

4、示和求解方法--數(shù)據(jù)結(jié)構(gòu)由以上幾個例子可見，描述這類非數(shù)值計算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。2.什么是數(shù)據(jù)結(jié)構(gòu)?數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象以及它們之間的關(guān)系和操作的學(xué)科。要使計算機(jī)能夠更有效地進(jìn)行這些非數(shù)值性處理，就必須弄清楚這些操作對象的特點(diǎn)，在計算機(jī)中的表示方式以及各個操作的具體實(shí)現(xiàn)手段。這些就是《數(shù)據(jù)結(jié)構(gòu)》這門課程研究的主要內(nèi)容。是所有能被輸入到計算機(jī)中，且能被計算機(jī)處理的所有符號(數(shù)字、字符等)的集合，它是計算機(jī)操作對象的總稱，是計算機(jī)處理的信息的載體，是信息的某種特定的符號表

5、示形式。數(shù)據(jù)是個集合，如果用集合的表示方法來寫的話，就是：數(shù)據(jù)={x

6、x是計算機(jī)操作的對象}是數(shù)據(jù)(集合)中的一個“個體”，在計算機(jī)中通常作為一個整體進(jìn)行考慮和處理，是數(shù)據(jù)結(jié)構(gòu)中討論的“基本單位”，但不是“最小單位”。1、數(shù)據(jù)2、數(shù)據(jù)元素1.2基本概念和術(shù)語數(shù)據(jù)元素分類一類是不可分割的“原子”型數(shù)據(jù)元素，如：整數(shù)“5”，字符“N”等一類是由多個款項(xiàng)構(gòu)成的數(shù)據(jù)元素，其中每個款項(xiàng)被稱為一個“數(shù)據(jù)項(xiàng)”。例如描述一個學(xué)生的信息的數(shù)據(jù)元素可由下列6個數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)結(jié)構(gòu)中討論的“最小單位”。數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合。稱之為組合項(xiàng)是性質(zhì)相同的數(shù)據(jù)元素的集合，

7、它是數(shù)據(jù)的一個子集。如：整數(shù)數(shù)據(jù)對象N={0,?1,?2,…}字母字符數(shù)據(jù)對象C={‘A’,’B’,……‘Z’}在同一個數(shù)學(xué)模型中的數(shù)據(jù)元素必然具有相同特性。3、數(shù)據(jù)對象4、數(shù)據(jù)結(jié)構(gòu)1）概念：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，即帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合?！敖Y(jié)構(gòu)”即指數(shù)據(jù)元素之間存在的約束關(guān)系。數(shù)據(jù)結(jié)構(gòu)是一堆數(shù)據(jù)元素和這些數(shù)據(jù)元素之間的關(guān)系的總和。例5一個12位數(shù)的十進(jìn)制數(shù)可以用3個4位的十進(jìn)制數(shù)表示：3214，6587，9345--a1(3214),a2(6587),a3(9345)a1,a2,a3之間存在“次序”關(guān)系,

8、，意為x和y之間存在“x領(lǐng)先于y”的次序關(guān)系。a1a2a3a2a1a3≠例6可以用下述數(shù)據(jù)結(jié)構(gòu)來描述2行3列的矩陣：它是一個含6個數(shù)據(jù)元素{a1,a2,a3,a4,a5,a6}的集合，且集合上存在“行關(guān)系”和“列關(guān)系”兩個次序關(guān)系，其中：行row={，，，}列col={，，}a1a3a5a2a4a6a1a2a3a4a5a6同樣的這6個數(shù)據(jù)元素組成的一維數(shù)組{a1,a2,a3,a4,a5,a6}的數(shù)據(jù)元素之間存在如下的次序關(guān)系:{

9、i,ai+1>

10、i=1,2,…5}同樣的數(shù)據(jù)元素，不同的關(guān)系構(gòu)成了不同的結(jié)構(gòu)，因此數(shù)據(jù)結(jié)構(gòu)是帶