數(shù)據(jù)結構講義一章緒論(與“算法”有關文檔共58張)

1.1數(shù)據(jù)結構討論的范疇1.2數(shù)據(jù)結構的基本概念1.3抽象數(shù)據(jù)類型1.4算法及其描述1.5算法的度量主要內容第1頁，共58頁。

Algorithm

+DataStructures=Programs

算法+數(shù)據(jù)結構=程序設計程序設計：

為計算機處理問題編制一組指令集

數(shù)據(jù)結構：

問題的數(shù)學模型算法：

處理問題的策略§1.1數(shù)據(jù)結構的研究范疇第2頁，共58頁。一般來說，用計算機解決一個數(shù)值問題時，大致需要經(jīng)過下列幾個步驟：首先要從具體問題抽象出一個適當?shù)臄?shù)學模型；然后設計一個解此數(shù)學模型的算法；最后編出程序，進行測試、調整至得到最終解答。尋求數(shù)學模型的實質是分析問題，從中提取操作的對象，并找出這些操作對象之間含有的關系，然后用數(shù)學的語言加以描述。§

1.1數(shù)據(jù)結構的研究范疇第3頁，共58頁。一般來說，用計算機解決一個非數(shù)值問題時，大致需要經(jīng)過下列幾個步驟：首先要從分析實際問題入手，從中提取出所要處理的數(shù)據(jù)對象，并找出這些數(shù)據(jù)對象之間的關系；然后分析對這些數(shù)據(jù)對象所要進行的操作；最后設計算法、編出程序，進行測試、調整至得到最終解答?！?/p>

1.1數(shù)據(jù)結構的研究范疇第4頁，共58頁。001高等數(shù)學樊映川S01…002理論力學羅遠祥L01…003高等數(shù)學華羅庚S01…004線性代數(shù)欒汝書S02………………樊映川001，…華羅庚003，…欒汝書004，………例1-1圖書館的書目檢索系統(tǒng)自動化問題按登錄號順序排列的書目文件作者名索引表書名索引表分類號索引表高等數(shù)學001，003，…理論力學002，…線性代數(shù)004，………L002，…S001，003，………第5頁，共58頁。抽象數(shù)據(jù)類型(AbstractDataType)scanf("%f",x);對棋盤數(shù)據(jù)進行的基本操作：下棋、悔棋、判斷輸贏、計算得分等。一個算法所耗費的時間=算法中每條語句的執(zhí)行時間之和Traverse()遍歷整個數(shù)據(jù)結構for（i=2；寄存本身所用的指令、常數(shù)、變量和輸入數(shù)據(jù)然后設計一個解此數(shù)學模型的算法；處理問題的策略O(n3)立方型f(n)=n3r={〈d,b〉,〈d,g〉,〈d,a〉,〈b,c〉,〈g,e〉,〈g,h〉,〈a,f〉}i<=n;i++）首先要從具體問題抽象出所要處理的數(shù)據(jù)對象；

在這類文檔管理的數(shù)學模型中，計算機處理的數(shù)據(jù)對象之間通常存在著一種最簡單的線性關系，這類數(shù)學模型可稱為線性的數(shù)據(jù)結構

。然后分析對這些數(shù)據(jù)對象所要進行的操作；設計對圖書、借閱者、借閱情況等數(shù)據(jù)進行生成、檢索、修改等操作。最后設計算法、編出程序，測試、調整至得到最終解答。根據(jù)選定的數(shù)據(jù)結構和要進行的操作設計算法、編寫程序，測試、修改，最終應用到圖書館的借閱管理實踐中。例1-1圖書館的書目檢索系統(tǒng)自動化問題第6頁，共58頁。例1-2計算機和人對弈問題。例1-2計算機和人的井字棋對弈問題井字棋由兩人對弈。棋盤為3×3的方格，當一方的3個棋子占同一行、或同一列、或同一對角線時便為勝方。圖中所示為對弈過程中井字棋的一個棋局，從當前棋盤格局可以派生出5個格局，而從每一個新的格局又可派生出4個可能出現(xiàn)的格局。以此類推分析可能出現(xiàn)的結果，從而選擇最好的位置放置棋子。第7頁，共58頁。首先要從具體問題抽象出所要處理的數(shù)據(jù)對象；若將從對弈開始到結束的過程中所有可能出現(xiàn)的格局都畫在一張圖上，則可得到一棵倒長的“樹”。“樹根”是對弈開始之前的棋盤格局，而所有的“葉子”就是可能出現(xiàn)的結局，對弈的過程就是從樹根沿樹杈到某個葉子的過程。各棋盤數(shù)據(jù)間的關系體現(xiàn)為“樹”型數(shù)據(jù)結構。然后分析對這些數(shù)據(jù)對象所要進行的操作；對棋盤數(shù)據(jù)進行的基本操作：下棋、悔棋、判斷輸贏、計算得分等。最后設計算法、編出程序，測試、調整至得到最終解答

根據(jù)選定的數(shù)據(jù)結構和要進行的操作設計算法、編寫程序，測試、修改，最終應用到人機對弈實踐中。例1-2計算機和人的井字棋對弈問題第8頁，共58頁。假設要在n個城市間建立通訊網(wǎng)，連通n個城市只需要n-1條線路。每架設一條線路，相應的要付出一定的費用。如何在最節(jié)省經(jīng)費的條件下建立這個連通網(wǎng)？用一個連通網(wǎng)（各邊帶有權值的連通圖）來表示n個城市間的通訊網(wǎng)，網(wǎng)中的頂點代表各個城市，邊代表城市間的通訊線路，各邊的權值表示鋪設該條線路需要的費用。afgcdeb191818208153920715例1-3建立n個城市之間的通訊網(wǎng)問題第9頁，共58頁。首先要從具體問題抽象出所要處理的數(shù)據(jù)對象；連通網(wǎng)中的數(shù)據(jù)對象是各個城市，這些數(shù)據(jù)對象之間有著多對多的復雜的聯(lián)系，這組數(shù)據(jù)對象以及它們之間的復雜關系體現(xiàn)的就是一種“圖”型數(shù)據(jù)結構。然后分析對這些數(shù)據(jù)對象所要進行的操作；對城市通訊網(wǎng)數(shù)據(jù)對象的操作：增加、刪除、布網(wǎng)、修改等最后設計算法、編出程序，測試、調整至得到最終解答

根據(jù)選定的數(shù)據(jù)結構和要進行的操作設計算法、編寫程序，測試、修改，最終應用到通訊網(wǎng)的布網(wǎng)實踐中。例1-2計算機和人的井字棋對弈問題第10頁，共58頁。雜亂的數(shù)據(jù)不能表達和交流信息；數(shù)據(jù)之間是有聯(lián)系的；數(shù)據(jù)之間是有結構的；在某種數(shù)據(jù)結構上可定義一組操作。§

1.1數(shù)據(jù)結構的研究范疇綜上所述，我們可以發(fā)現(xiàn)我們用計算機所處理的數(shù)據(jù)信息具有以下特點：數(shù)據(jù)結構研究的是從分析實際問題入手，從中提取出所要處理的數(shù)據(jù)對象，并找出這些數(shù)據(jù)對象之間的關系，以及對這些數(shù)據(jù)對象的操作等的學科。第11頁，共58頁。數(shù)據(jù)的各種邏輯結構和存儲結構，以及它們之間的相應關系。并對每種結構定義相適應的各種操作。設計出相應的算法。分析算法的效率。§

1.1數(shù)據(jù)結構的研究范疇第12頁，共58頁。數(shù)據(jù)（Data）數(shù)據(jù)元素（DataElement）數(shù)據(jù)對象（DataObject）數(shù)據(jù)結構（DataStructure）邏輯結構（LogicalStructure）存儲結構（PhysicalStructure）§

1.2數(shù)據(jù)結構的基本概念第13頁，共58頁。數(shù)據(jù)：描述客觀事物的數(shù)字、字符以及一切能夠輸入到計算機中，并且能夠被計算機程序處理的符號的集合。

數(shù)據(jù)是一個廣義的概念，可以指普通的數(shù)據(jù)（可參加算術運算），也可以指符號（源程序、產品名稱等）或數(shù)字化了的聲音、圖形、圖像等?！?/p>

1.2數(shù)據(jù)結構的基本概念第14頁，共58頁。..................北京1983.11河北女趙虹玲101住址出生年月籍貫性別姓名學號數(shù)據(jù)元素數(shù)據(jù)項數(shù)據(jù)元素：數(shù)據(jù)(集合)中的一個個"個體"，是組成數(shù)據(jù)的"基本單位"。數(shù)據(jù)項：構成數(shù)據(jù)元素的不可分割的數(shù)據(jù)單位。§

1.2數(shù)據(jù)結構的基本概念第15頁，共58頁。數(shù)據(jù)對象：性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如：整數(shù)集合：N={0，±1，±2，…}

無限集字符集合：C={'A'，'B'，…，'Z'}

有限集§

1.2數(shù)據(jù)結構的基本概念第16頁，共58頁。……129ABZ…………數(shù)據(jù)數(shù)據(jù)對象2數(shù)據(jù)對象1數(shù)據(jù)元素1數(shù)據(jù)元素2數(shù)據(jù)元素1數(shù)據(jù)元素2數(shù)字N字符C數(shù)據(jù)集合D

={…0,1,…,9,…,A,B,…,Z，…

}數(shù)字集合N={0,1,…,9}字母集合C={A,B,…,Z}數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象的關系第17頁，共58頁。注：數(shù)據(jù)結構用來指內存中的數(shù)據(jù)組織，外存中的數(shù)據(jù)組織通常稱為文件結構。數(shù)據(jù)結構：(DataStructure)數(shù)據(jù)結構是帶“結構”的數(shù)據(jù)元素的集合?！敖Y構”即指數(shù)據(jù)元素之間存在的聯(lián)系。所以數(shù)據(jù)結構又可以定義為有聯(lián)系的數(shù)據(jù)元素的集合。§

1.2數(shù)據(jù)結構的基本概念第18頁，共58頁。

四類基本的結構：集合結構線性結構:一對一樹狀結構：一對多圖狀結構：多對多§

1.2數(shù)據(jù)結構的基本概念邏輯結構：

(LogicalStructure)數(shù)據(jù)的邏輯結構是指數(shù)據(jù)元素之間邏輯關系。第19頁，共58頁。綜上所述，數(shù)據(jù)的邏輯結構可概括為：線性結構邏輯結構非線性結構線性表棧隊列字符串數(shù)組廣義表樹圖§

1.2數(shù)據(jù)結構的基本概念第20頁，共58頁?！?/p>

1.2數(shù)據(jù)結構的基本概念存儲結構：(PhysicalStructure)又稱物理結構，是數(shù)據(jù)的邏輯結構在計算機中的表示與實現(xiàn)，它包括數(shù)據(jù)元素在計算機中的表示以及數(shù)據(jù)元素之間的關系在計算機中的表示和實現(xiàn)。第21頁，共58頁。數(shù)據(jù)元素的表示：在計算機中，用一個有若干二進制位組合起來形成的一個位串表示一個數(shù)據(jù)元素。數(shù)據(jù)元素之間關系的表示：1、順序映象（順序存儲結構）：以存儲位置表示前后關系，整個存儲結構中只含數(shù)據(jù)元素本身的信息。2、非順序映象（非順序——鏈式存儲結構）：以附加信息(指針)表示前后關系?！?/p>

1.2數(shù)據(jù)結構的基本概念存儲結構的實現(xiàn)：第22頁，共58頁。邏輯結構…d1d2d3d4…d30a2a1a3a4a30存儲結構1.順序映象（順序存儲結構）線性結構（線性表）a1a2a3a30劉曉光馬廣生王民…張玉華男男…女男漢回壯…漢161721…25

姓名性別民族年齡Example第23頁，共58頁。2、非順序映象（非順序——鏈式存儲結構）a1a2a3a30∧list……d1d2d3d4

a2a1a4a3d4d1d5d3存儲結構Example第24頁，共58頁。

抽象數(shù)據(jù)類型(AbstractDataType)用C語言實現(xiàn)抽象數(shù)據(jù)類型ADTADT的表示與實現(xiàn)§

1.3

抽象數(shù)據(jù)類型第25頁，共58頁。數(shù)學模型抽象數(shù)據(jù)模型數(shù)據(jù)結構非形式算法偽語言程序可執(zhí)行程序用抽象數(shù)據(jù)類型的概念來指導問題的求解過程：注：一個抽象數(shù)據(jù)類型確定了一個模型，但將模型的實現(xiàn)細節(jié)隱藏起來；它定義了一組運算，但將運算的實現(xiàn)過程隱藏起來。§

1.3

抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型：(簡稱ADT)是指基于一類邏輯關系的數(shù)據(jù)類型以及定義在這個類型之上的一組操作。第26頁，共58頁。ADT的定義格式

ADT<ADT名>

{數(shù)據(jù)對象:<數(shù)據(jù)對象的定義>

結構關系:<結構關系的定義>

基本操作:<基本操作的定義>}ADT<ADT名>

基本操作的定義格式為：<操作名稱>(參數(shù)表)操作前提:<操作前提描述>操作結果:<操作結果描述>§

1.3

抽象數(shù)據(jù)類型第27頁，共58頁。數(shù)據(jù)元素：所有ai屬于同一數(shù)據(jù)對象，i=1，2，……，nn≥0；邏輯結構：所有數(shù)據(jù)元素ai（i=1，2，…，n-1）存在一定邏輯關系；操作

Initial()

初始化數(shù)據(jù)結構；

Destroy()銷毀數(shù)據(jù)結構；

Get(i)

查找第i

個元素；

Insert(i,b)

在第i個位置插入元素b；

Delete(i)

刪除第i個元素；

Traverse()遍歷整個數(shù)據(jù)結構抽象數(shù)據(jù)類型的基本描述§

1.3

抽象數(shù)據(jù)類型第28頁，共58頁。用標準C語言表示和實現(xiàn)ADT描述時，主要有兩個方面：二、用C語言函數(shù)實現(xiàn)各操作。一、通過結構體將int、float等固有類型組合到一起，構成一個結構類型，再用typedef為該類型或該類型指針重新起一個名字。用C語言實現(xiàn)抽象數(shù)據(jù)類型ADT§

1.3

抽象數(shù)據(jù)類型第29頁，共58頁。算法（Algorithm）定義算法設計的要求算法的特性算法的描述方法§

1.4

算法及其描述第30頁，共58頁。算法：Algorithmisafinitesetofruleswhich

givesasequenceofoperationforsolvingaspecifictype

ofproblem. 算法是指令的有限序列，是為解決特定問題而規(guī)定的一系列操作?！?/p>

1.4

算法及其描述第31頁，共58頁。算法的特性1.有限性：有限步驟之內正常結束，不能形成無窮循環(huán)。2.確定性：算法中的每一個步驟必須有確定含義，無二義性。3.可行性：算法中的每一步都是可行的。算法翻譯成程序語言以后能夠在計算機上精確執(zhí)行，而且能夠完成指定的功能?！?/p>

1.4

算法及其描述第32頁，共58頁。主要區(qū)別：

1、程序可以是無窮的，算法必須是有窮的。

2、程序可以是錯誤的，算法必須是正確的。

3、程序是用程序設計語言描述，在機器上可以執(zhí)行。算法可以用框圖和自然語言等方式描述。算法與程序的區(qū)別§

1.4

算法及其描述程序：用某種程序設計語言對算法的具體實現(xiàn)第33頁，共58頁。mark3:x=b[i];//n-1次基本操作:<基本操作的定義>程序：用某種程序設計語言對算法的具體實現(xiàn)數(shù)據(jù)是一個廣義的概念，可以指普通的數(shù)據(jù)（可參加算術運算），也可以指符號（源程序、產品名稱等）或數(shù)字化了的聲音、圖形、圖像等。O(2n)指數(shù)型f(n)=2n數(shù)據(jù)元素（DataElement）x=b[i];2數(shù)據(jù)結構的基本概念1數(shù)據(jù)結構的研究范疇確定所解決問題的問題規(guī)模n；for(j=0;j<n;j++)算法在計算機上不止執(zhí)行一次，必須多次執(zhí)行，然后對結果進行統(tǒng)計分析。在實際計算語句頻度時，可以不考慮循環(huán)語句和條件語句本身，而只考慮他們所包含的循環(huán)體和條件體。2、程序可以是錯誤的，算法必須是正確的。scanf("%f",x);j++;//n(n-1)/2次算法設計的要求§

1.4

算法及其描述1.正確性（四個層次）

a.程序沒有語法錯誤；

b.程序對于幾組輸入數(shù)據(jù)能夠得出滿足要求的結果；

c.程序對于精心選擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠的除滿足要求的結果；

d.程序對于一切合法的數(shù)據(jù)數(shù)據(jù)都能夠產生滿足要求的結果。2.可讀性：3.健壯性：4.高效率和低存儲量：第34頁，共58頁。例：求n個數(shù)的最大值問題

max=0;

for（i=1；i<=n;i++）

{

scanf("%f",x);

if(x>max)

max=x;}

scanf("%f",x);

max=x;

for（i=2；i<=n;i++）

{

scanf("%f",x);

if(x>max)

max=x;}第35頁，共58頁?！?/p>

1.5

算法的度量評價算法的標準：

算法所占用機器資源的多少

1.時間復雜度：

算法執(zhí)行所需的機器時間。2.空間復雜度：

算法執(zhí)行所占用的存儲空間。第36頁，共58頁。§

1.5

算法的度量事后統(tǒng)計法：

把算法變?yōu)槌绦?，然后在機器上執(zhí)行，并計時。

1.算法在計算機上不止執(zhí)行一次，必須多次執(zhí)行，然后對結果進行統(tǒng)計分析。2.機器的速度、編譯程序的質量等等外在的因素，會影響算法的執(zhí)行時間。事前分析估計法：

在編寫算法過程中就要對算法的效率進行分析估算算法的度量方法第37頁，共58頁。一個算法的運行時間：是指在計算機上從開始到結束運行所花費的時間，它大致等于計算機執(zhí)行一種簡單操作(如賦值、比較、計算、轉向、返回、輸入、輸出等)所需的時間與算法中進行簡單操作次數(shù)的乘積。因為執(zhí)行一種簡單操作所需的時間隨機器而異，它是由機器本身硬軟件環(huán)境決定的，與算法無關，所以我們只討論影響運行時間的另一個因素——算法中進行簡單操作的次數(shù)。§

1.5

算法的度量算法的運行時間第38頁，共58頁。

語句頻度：是指語句被重復執(zhí)行的次數(shù)?！罢Z句”：指描述算法的基本語句，它的執(zhí)行是不可再分割的。一個算法所耗費的時間=算法中每條語句的執(zhí)行時間之和每條語句的執(zhí)行時間

=語句被重復執(zhí)行的次數(shù)×語句執(zhí)行一次所需時間§

1.5

算法的度量算法耗費的時間和語句頻度第39頁，共58頁。矩陣相乘：求各語句頻度inti,j,k;for(i=0;i<n;i++)for(j=0;j<n;j++){ c[i][j]=0;

for(k=0;k<n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j];}解:該算法中所有語句的頻度之和即算法的時間耗費，我們用T(n)來表示，為：

T(n)=2n3+3n2+2n+1

Example基本語句1基本語句2n+1

n2(n+1)

n(n+1)

n2

n3

第40頁，共58頁?！?/p>

1.5

算法的度量算法執(zhí)行時間的相關因素

問題規(guī)模

編寫程序的語言編譯程序產生的機器代碼的質量

計算機執(zhí)行指令的速度第41頁，共58頁。問題規(guī)模n

——對不同的問題其含義不同：矩陣階數(shù)多項式運算圖集合運算多項式項數(shù)頂點個數(shù)集合中元素個數(shù)§

1.5

算法的度量算法的度量——問題規(guī)模第42頁，共58頁。§

1.5

算法的度量問題規(guī)模與語句頻度問題規(guī)模與語句頻度的關系：語句的頻度使用問題規(guī)模來表示的，語句頻度要表示成問題規(guī)模的函數(shù)。算法耗時、問題規(guī)模、語句頻度的關系：算法的耗費時間由算法中所有語句的頻度之和來表示，而語句頻度是問題規(guī)模的函數(shù)。第43頁，共58頁。時間復雜度：當問題規(guī)模n趨近于無窮時，算法耗費時間的增長率(數(shù)量級)，表示為問題規(guī)模n的函數(shù)：

T(n)=O(f(n))

T(n)=O(f(n)

)的數(shù)學定義:

在數(shù)學里，如果T(n)=O(

f

(n)

)，那么當且僅當

（c為非零常數(shù)）時間復雜度§

1.5

算法的度量時間復雜度和大O表示法第44頁，共58頁。數(shù)據(jù)結構中常用的時間復雜度數(shù)量級有7個，按照數(shù)量級遞增排序有:O(1)

常數(shù)型O(log2n)

對數(shù)型f(n)=log2nO(n)

線性型f(n)=nO(n2)

平方型f(n)=n2O(n3)

立方型f(n)=n3O(2n)

指數(shù)型f(n)=2n隨著n的增大，T(n)增長速度較慢的算法為優(yōu)，即T(n)的數(shù)量級O(f(n))較小的算法效率較高。

第45頁，共58頁。1.確定所解決問題的問題規(guī)模n；2.找出算法中的所有基本語句；3.計算出所有基本語句的語句頻度，并把他們相加得出T(n);4.求出T(n)的數(shù)量級f(n)，則T(n)=O(f(n))即為算法的時間復雜度§

1.5

算法的度量算法的時間復雜度的估算步驟第46頁，共58頁。循環(huán)語句的整體、函數(shù)調用語句不能算作基本語句，因為它們還包括循環(huán)體或函數(shù)體。在一個算法中，有些語句可能很少被執(zhí)行，且與程序的問題規(guī)模無關，在估算時間復雜度是，可以不考慮他們。一般只考慮與程序的問題規(guī)模有關的語句的語句頻度。在實際計算語句頻度時，可以不考慮循環(huán)語句和條件語句本身，而只考慮他們所包含的循環(huán)體和條件體?！?/p>

1.5

算法的度量算法的時間復雜度的估算第47頁，共58頁。求時間復雜度：交換i和j的內容

Temp=i;i=j;j=temp;Example以上三條單個語句的頻度均為1，該程序段的執(zhí)行時間是一個與問題規(guī)模n無關的常數(shù)。算法的時間復雜度為常數(shù)階，記作T(n)=O(1)。如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句，其執(zhí)行時間也不過是一個較大的常數(shù)。此類算法的時間復雜度是O(1)。第48頁，共58頁。求時間復雜度：(1)x=0;y=0;(2)for(k-1;k<=n;k++)(3)x++;(4)for(i=1;i<=n;i++)(5)for(j=1;j<=n;j++)(6)y++;Example在多數(shù)情況下，只要選出算法中含在嵌套層數(shù)最多的，即最內層的循環(huán)體中的基本語句，該基本語句的執(zhí)行次數(shù)(語句頻度)就可作為算法的時間度量。第49頁，共58頁。主要任務：分析算法在實現(xiàn)時所需要的輔助空間單元個數(shù)。用空間復雜度作為算法所需存儲空間的量度，記做：

S(n)=O(f(n)

)

存儲空間寄存本身所用的指令、常數(shù)、變量和輸入數(shù)據(jù)（取決于問題本身，與算法無關）對數(shù)據(jù)進行操作的輔助存儲空間（與算法有關）§

1.5

算法的度量算法的空間復雜度第50頁，共58頁。

數(shù)據(jù)結構與其它課程關系圖：數(shù)據(jù)結構數(shù)據(jù)庫人工智能專業(yè)基礎課操作系統(tǒng)編譯原理非線性程序設計離散數(shù)學語言程序設計計算機原理設計§

1.5

算法的度量第51頁，共58頁。（1）A=（K，R），其中：K={a，b，c，d，e，f，g}R={r}r={〈a,b〉,〈b,c〉,〈c,d〉,〈d,e〉,〈e,f〉,〈f,g〉}（2）B=（K，R），其中：K={a，b，c，d，e，f，g，h}R={r}r={〈d,b〉,〈d,g〉,〈d,a〉,〈b,c〉,〈g,e〉,〈g,h〉,〈a,f〉}（3）C=（K，R），其中：K={1，2，3，4，5，6}R={r}r={（1,2）,（2,3）,（2,4）,（3,4）,（3,5）,（3,6）,（4,5）,（4,6）}這里的圓括號對表示兩結點是雙向的。

練

習1、有下列幾種用二元組表示的數(shù)據(jù)結構，畫出它們分別對應的邏輯圖形表示，并指出它們分別屬于何種結構。第52頁，共58頁。

A對應邏輯圖形如下，它是一種線性結構。

練

習（1）A=（K，R），其中：K={a，b，c，d，e，f，g}R={r}r={〈a,b〉,〈b,c〉,〈c,d〉,〈d,e〉,〈e,f〉,〈f,g〉}1、有下列幾種用二元組表示的數(shù)據(jù)結構，畫出它們分別對應的邏輯圖形表示，并指出它們分別屬于何種結構。第53頁，共58頁。

B對應邏輯圖形如下，它是一種樹形結構。

練

習1、有下列幾種用二元組表示的數(shù)據(jù)結構，畫出它們分別對應的邏輯圖形表示，并指出它們分別屬于何種結構。（2）B=（K，R），其中：K={

a，b，c，d，e，f，g，h

}R={r}r={〈d,b〉,〈d,g〉,〈d,a〉,〈b,c〉,〈g,e〉,〈g,h〉,〈a,f〉}第54頁，共58頁。

C對應邏輯圖形如下，它是一種圖形結構。

練

習1、有下列幾種用二元組表示的數(shù)據(jù)結構，畫出它們分別對應的邏輯圖形表示，并指出它們分別屬于何種結構。（3）C=（K，R），其中：K={1，2，3，4，5，6}R={r}r={(1,2),(2,3)

,