資源描述：
《數(shù)據(jù)結(jié)構(gòu)與算法第1節(jié)概述.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第2章數(shù)據(jù)結(jié)構(gòu)與算法一、數(shù)據(jù)結(jié)構(gòu)討論與研究的范疇二、算法第1節(jié)概述學(xué)習(xí)內(nèi)容與要求學(xué)習(xí)和了解數(shù)據(jù)結(jié)構(gòu)所研究的內(nèi)容；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的定義和基本分類(lèi)；學(xué)習(xí)和掌握與數(shù)據(jù)結(jié)構(gòu)有關(guān)的名詞術(shù)語(yǔ)（如數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)類(lèi)型、抽象數(shù)據(jù)類(lèi)型ADT等等）；學(xué)習(xí)和了解算法的概念、特點(diǎn)以及算法的評(píng)價(jià)標(biāo)準(zhǔn)。2DataStructures+Algorithms=Programs——NicklausWirth程序:數(shù)據(jù)結(jié)構(gòu):算 法:利用計(jì)算機(jī)語(yǔ)言編制的一組具有確定功能的指令集合。處理問(wèn)題的策略。問(wèn)題或?qū)ο蟮臄?shù)學(xué)模型(如何描述數(shù)據(jù)的外部表現(xiàn)形式和內(nèi)部存儲(chǔ)結(jié)
2、構(gòu))。3一、數(shù)據(jù)結(jié)構(gòu)研究和討論的范疇4“學(xué)生”數(shù)據(jù)1234567895“課程”數(shù)據(jù)6“選課”數(shù)據(jù)學(xué)號(hào)課程編號(hào)成績(jī)時(shí)間981640240028206.6.10981640240169006.6.15981650240028506.6.10981650240167606.6.15981650240248906.6.139816598164024016024002024024學(xué)生課程7學(xué)生(學(xué)號(hào),姓名,性別,籍貫)課程(課程號(hào),課程名,學(xué)分)選課(學(xué)號(hào),課程號(hào),成績(jī))“選課”數(shù)據(jù)包含如下信息:學(xué)號(hào)課程編號(hào)成績(jī)時(shí)間學(xué)生選課系統(tǒng)中“學(xué)生”和“課程”這兩個(gè)實(shí)體
3、構(gòu)成了網(wǎng)狀（圖狀）關(guān)系（即“選課”關(guān)系）。8UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖/(root)binlibuseretcmathdsswlintaoxieStack.cppQueue.cppTree.cpp9數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容綜合上述例子可見(jiàn)，描述這類(lèi)非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹(shù)和圖之類(lèi)的數(shù)據(jù)結(jié)構(gòu)。簡(jiǎn)單地說(shuō)，作為一門(mén)學(xué)科，數(shù)據(jù)結(jié)構(gòu)主要研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題當(dāng)中計(jì)算機(jī)的操作對(duì)象（數(shù)據(jù)）以及它們之間的關(guān)系（邏輯結(jié)構(gòu)和物理結(jié)構(gòu)）和操作（算法實(shí)現(xiàn)）。10若干名詞術(shù)語(yǔ)數(shù)據(jù)（data）數(shù)據(jù)元素（dataelement）數(shù)據(jù)項(xiàng)（datai
4、tem）數(shù)據(jù)對(duì)象（dataobject）數(shù)據(jù)結(jié)構(gòu)（datastructure）數(shù)據(jù)類(lèi)型（datatype）抽象數(shù)據(jù)類(lèi)型（ADT）11數(shù)據(jù)（data）數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中、被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)12數(shù)據(jù)元素(dataelement)和 數(shù)據(jù)項(xiàng)（dataitem）數(shù)據(jù)元素是數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)元素又可稱(chēng)為元素、結(jié)點(diǎn)、記錄。有時(shí)一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)（dataitem）組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。13數(shù)據(jù)對(duì)象(
5、dataobject)具有相同性質(zhì)的數(shù)據(jù)成員（數(shù)據(jù)元素）的集合，數(shù)據(jù)的子集。例：整數(shù)數(shù)據(jù)對(duì)象N={0,?1,?2,…}學(xué)生數(shù)據(jù)對(duì)象有窮集和無(wú)窮集14什么是數(shù)據(jù)結(jié)構(gòu)定義:由某一數(shù)據(jù)對(duì)象及該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系組成。與“數(shù)據(jù)對(duì)象”這一概念的區(qū)別？作為術(shù)語(yǔ)名詞和作為學(xué)科名詞的區(qū)別？15數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)內(nèi)的表示，即數(shù)據(jù)的存儲(chǔ)表示（物理結(jié)構(gòu)、物理表示）。數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)元素施加的操作。作為學(xué)科，數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的組織形式，包括以下內(nèi)容：16數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)從數(shù)據(jù)的邏輯關(guān)系上描述數(shù)據(jù)，
6、與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，與數(shù)據(jù)元素本身的具體形式、內(nèi)容無(wú)關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)據(jù)模型。17數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類(lèi)：線性結(jié)構(gòu)：一對(duì)一關(guān)系樹(shù)形結(jié)構(gòu)：一對(duì)多關(guān)系圖狀結(jié)構(gòu)：多對(duì)多關(guān)系集合結(jié)構(gòu)：簡(jiǎn)單隸屬關(guān)系18數(shù)據(jù)邏輯結(jié)構(gòu)的描述方式Data_Structure={D,R}其中，D是某一數(shù)據(jù)對(duì)象，R是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。一般表現(xiàn)形式如下：D={d1,d2,…,dn}R={r1,r2,…,rm}關(guān)鍵字：數(shù)據(jù)元素中可用于標(biāo)識(shí)該數(shù)據(jù)元素的某個(gè)分量（數(shù)據(jù)項(xiàng)）。通常用關(guān)鍵字區(qū)別不同的數(shù)據(jù)元素。19D＝{01,02,03
7、,04,05,06,07,08,09,10}R1={<08,05>,<05,02>,<02,01>,<01,03>,<03,09>,<09,04>,<04,06>,<06,10>,<10,07>}R2={<01,02>,<01,05>,<01,08>,<02,03>,<02,04>,<05,06,>,<05,07>,<08,09>,<08,10>}R3={<01,04>,<04,01>,<01,05>,<05,01>,<01,08>,<08,01>,<04,07>,<07,04>,<05,06>,<06,05>,<06,04>,<04,06>,<0
8、5,08>,<08,05>,<06,09>,<09,06>,<09,02>,<02,09>,<08,10>,<10,08>
