27-1第2章基本數(shù)據(jù)結(jié)構(gòu)2.1數(shù)據(jù)結(jié)構(gòu)的基本概念1.什么是數(shù)據(jù)結(jié)構(gòu)2.數(shù)據(jù)結(jié)構(gòu)的表示27-2數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)和數(shù)據(jù)結(jié)構(gòu)1.基本術(shù)語(yǔ)數(shù)據(jù)(data)--反映客觀事物的信息的集合，是信息的載體，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。數(shù)據(jù)元素(dataelement)--集合中的個(gè)體，數(shù)據(jù)的基本單位，一個(gè)數(shù)據(jù)元素可以由多個(gè)數(shù)據(jù)項(xiàng)組成（字段、域、屬性）數(shù)據(jù)項(xiàng)—是具有獨(dú)立含義的最小數(shù)據(jù)單位。數(shù)據(jù)對(duì)象(dataobject)相同特性的數(shù)據(jù)元素的集合--數(shù)據(jù)的子集★2.1數(shù)據(jù)結(jié)構(gòu)的基本概念27-3數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)和數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(datastructure)—互相關(guān)聯(lián)的數(shù)據(jù)元素的集合[二要素:B=(D,R)]，其中：數(shù)據(jù)元素之間的邏輯關(guān)系，也稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)元素極其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)施加的操作，即算法數(shù)據(jù)結(jié)構(gòu)可以嵌套定義邏輯結(jié)構(gòu)與物理結(jié)構(gòu)及其兩類映象數(shù)據(jù)類型(datatype)--與機(jī)器、運(yùn)算有關(guān)的屬性思考題：二要素（D,R)各自在計(jì)算機(jī)中如何表現(xiàn)？★27-4數(shù)據(jù)舉例：身份證數(shù)據(jù)的管理在身份證管理應(yīng)用層次的視圖數(shù)據(jù)元素：每個(gè)身份證信息是一個(gè)數(shù)據(jù)元素，包括姓名、性別、身份證號(hào)和相片等數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)：姓名、性別、身份證號(hào)和相片都是數(shù)據(jù)項(xiàng)數(shù)據(jù)結(jié)構(gòu)：身份證信息之間的關(guān)系：邏輯結(jié)構(gòu)：（線性）表結(jié)構(gòu)物理結(jié)構(gòu)：數(shù)組操作：增加、刪除、查找數(shù)據(jù)結(jié)構(gòu)的嵌套：例如：相片是一個(gè)圖象數(shù)據(jù)，具有圖象數(shù)據(jù)結(jié)構(gòu)，它可以作為一個(gè)數(shù)據(jù)項(xiàng)嵌套在每個(gè)人的數(shù)據(jù)項(xiàng)中。27-51.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)特征從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無關(guān)從具體問題抽象出來的數(shù)據(jù)模型與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān)分類線性結(jié)構(gòu)：線性表非線性結(jié)構(gòu)：樹、圖★27-6數(shù)據(jù)結(jié)構(gòu)四個(gè)基本的數(shù)據(jù)結(jié)構(gòu)集合結(jié)構(gòu)：關(guān)系集合是空集

頂點(diǎn)元素間無任何關(guān)系，R={}空集27-7線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)：元素間的關(guān)系是1對(duì)1

1)有且只有一個(gè)初始節(jié)點(diǎn)2)最多有一個(gè)前區(qū)驅(qū),最多有一個(gè)后繼(也可以無)3)插入或刪除一個(gè)節(jié)點(diǎn)后仍滿足1),2)非線性結(jié)構(gòu):元素間的關(guān)系是1對(duì)多不滿足線性結(jié)構(gòu)特點(diǎn)的通稱為非線性結(jié)構(gòu)樹型結(jié)構(gòu)：一般樹、二叉樹、森林

一個(gè)結(jié)點(diǎn)可以有多個(gè)直接后繼（除葉子結(jié)點(diǎn)外），

但只有一個(gè)直接前驅(qū)（除根結(jié)點(diǎn)外）★27-8圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)：元素間的關(guān)系是多對(duì)多

一個(gè)結(jié)點(diǎn)可以有多個(gè)直接后繼，也可以有多個(gè)直接前驅(qū)★27-9邏輯結(jié)構(gòu)舉例以班級(jí)數(shù)據(jù)為例，數(shù)據(jù)元素是學(xué)生，學(xué)生有學(xué)號(hào)、姓名和性別等數(shù)據(jù)項(xiàng)。學(xué)生同屬于一個(gè)班級(jí)的關(guān)系構(gòu)成集合結(jié)構(gòu)按學(xué)號(hào)排列的學(xué)生關(guān)系構(gòu)成線性結(jié)構(gòu)如果學(xué)生分組管理，班長(zhǎng)-組長(zhǎng)-普通學(xué)生，那么學(xué)生的上下級(jí)關(guān)系則構(gòu)成層次結(jié)構(gòu)學(xué)生之間的朋友關(guān)系構(gòu)成一個(gè)網(wǎng)狀結(jié)構(gòu)27-10例1、學(xué)生基本情況登記表。學(xué)號(hào)姓名 專業(yè)政治面藐

001 王洪 計(jì)算機(jī)黨員002孫文計(jì)算機(jī)團(tuán)員003 謝軍 計(jì)算機(jī)團(tuán)員004 李輝 計(jì)算機(jī)團(tuán)員005 沈祥福計(jì)算機(jī)黨員006 余斌 計(jì)算機(jī)團(tuán)員007 鞏力計(jì)算機(jī)團(tuán)員008 孔令輝計(jì)算機(jī)團(tuán)員

00100300200400600500007學(xué)號(hào)關(guān)系是一種線性結(jié)構(gòu)關(guān)系邏輯結(jié)構(gòu)舉例27-112.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示—為數(shù)據(jù)元素分配存儲(chǔ)單元將數(shù)據(jù)元素間的邏輯關(guān)系映射到存儲(chǔ)位置關(guān)系上依賴于程序設(shè)計(jì)語(yǔ)言所提供的數(shù)據(jù)類型和存儲(chǔ)形式1.順序存儲(chǔ)結(jié)構(gòu)等長(zhǎng)；等間隔邏輯上相鄰-->物理上相鄰,關(guān)系自然確定易于描述線性結(jié)構(gòu)，也可存儲(chǔ)經(jīng)過線性化處理的非線性結(jié)構(gòu)主要數(shù)據(jù)類型:向量（表格存儲(chǔ)結(jié)構(gòu)）,數(shù)組高級(jí)計(jì)算機(jī)語(yǔ)言以數(shù)據(jù)類型的方式提供了一個(gè)基本數(shù)據(jù)結(jié)構(gòu)集的存儲(chǔ)和操作。影響選擇的因素：數(shù)據(jù)的訪問效率和存儲(chǔ)空間占用的權(quán)衡?！?7-1227-13順序結(jié)構(gòu)數(shù)據(jù)的存取27-14

2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)每個(gè)節(jié)點(diǎn)由兩部分組成:數(shù)據(jù)域,位置指示域(指針域)即可實(shí)現(xiàn)線性結(jié)構(gòu),又可表示非線性結(jié)構(gòu)特點(diǎn):可以表示任意復(fù)雜的結(jié)構(gòu)存儲(chǔ)空間不連續(xù)存儲(chǔ)順序與結(jié)構(gòu)順序不一致不能隨機(jī)訪問訪問效率不均等主要形式:

單鏈表、雙鏈表、多重鏈表、循環(huán)鏈表3.索引存儲(chǔ)結(jié)構(gòu)—順序與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的組合4.散列存儲(chǔ)結(jié)構(gòu)—位置信息通過關(guān)鍵字解析★data

單元節(jié)點(diǎn)P27-15鏈?zhǔn)酱鎯?chǔ)示例data

dca10001001100210031004100510061007100101003鏈?zhǔn)酱鎯?chǔ)單元節(jié)點(diǎn)PP27-16數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系1.數(shù)據(jù)的邏輯結(jié)構(gòu)必定要有某種存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)2.兩種結(jié)構(gòu)的關(guān)聯(lián)既不固定，也不唯一。3.常用數(shù)據(jù)結(jié)構(gòu)的分類可以定義在邏輯結(jié)構(gòu)上，也可以定義在存儲(chǔ)結(jié)構(gòu)上，還可以定義在存儲(chǔ)方法上?！?7-172.1.3數(shù)據(jù)結(jié)構(gòu)的圖形表示邏輯結(jié)構(gòu)的表示符號(hào)的表示

B=(D,R)

B-數(shù)據(jù)結(jié)構(gòu),D-數(shù)據(jù)元素的集合,

R-D上的一個(gè)關(guān)系圖形的表示d2d3d1d4d5根節(jié)點(diǎn)內(nèi)部節(jié)點(diǎn)終節(jié)點(diǎn)關(guān)系描述★27-18例、家族的族譜

家族的族譜反映的是家族成員之間的血緣關(guān)系，假設(shè)某家族有10個(gè)成員：A、B、C、D、E、F、G、H、I、J，他們之間的血緣關(guān)系可以用如下圖表示。這種分支結(jié)構(gòu)關(guān)系被稱為樹結(jié)構(gòu)，它很象一棵倒置的樹，A是樹的根。非線性結(jié)構(gòu)的圖形表示JIACHGFE家族樹的圖示表示血緣關(guān)系是一種非線性結(jié)構(gòu)關(guān)系BD27-19數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象及本課程討論的問題數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象：非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，不一定能在分析數(shù)學(xué)范疇內(nèi)建立解析模型運(yùn)算操作以插入、刪除、查找、更改為主。本課程討論的問題：

應(yīng)用中常用的幾種數(shù)據(jù)結(jié)構(gòu)，以及如何存儲(chǔ),如何處理它們。★27-20

操作與數(shù)據(jù)結(jié)構(gòu)的定義密切相關(guān)。主要算法涉及到以下操作：①插入：在數(shù)據(jù)結(jié)構(gòu)中的指定位置插入新的數(shù)據(jù)元素。②刪除：刪去數(shù)據(jù)結(jié)構(gòu)中的指定的數(shù)據(jù)元素。③更新：改變數(shù)據(jù)結(jié)構(gòu)中某個(gè)數(shù)據(jù)元素的值。④查找：在數(shù)據(jù)結(jié)構(gòu)中尋找滿足某個(gè)特定要求的數(shù)據(jù)元素。（返回位置或值）⑤排序：在線性數(shù)據(jù)結(jié)構(gòu)中重新安排數(shù)據(jù)元素之間的邏輯順序關(guān)系。數(shù)據(jù)結(jié)構(gòu)的基本操作27-21算法與數(shù)據(jù)結(jié)構(gòu)的對(duì)應(yīng)性1.行為特性設(shè)計(jì)---算法設(shè)計(jì)信息結(jié)構(gòu)特性設(shè)計(jì)---數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)2.不能離開數(shù)據(jù)結(jié)構(gòu)去抽象地分析程序的算法；也不能脫離算法去孤立地研究程序的數(shù)據(jù)結(jié)構(gòu)，而只能從算法與數(shù)據(jù)結(jié)構(gòu)的統(tǒng)一上去認(rèn)識(shí)程序。27-22數(shù)據(jù)結(jié)構(gòu)對(duì)算法影響一個(gè)算法的效率與數(shù)據(jù)的表示形式直接有關(guān)，對(duì)程序質(zhì)量的影響極大。數(shù)據(jù)的構(gòu)成和表示方式數(shù)據(jù)的存儲(chǔ)方式數(shù)據(jù)的類型選擇★27-23離散問題中的算法與數(shù)據(jù)結(jié)構(gòu)27-24離散問題中的算法與數(shù)據(jù)結(jié)構(gòu)27-25算法與程序設(shè)計(jì)的關(guān)系。程序就是在數(shù)據(jù)的某些特定的表示方式和結(jié)構(gòu)基礎(chǔ)上對(duì)抽象算法的計(jì)算機(jī)語(yǔ)言具體表述。數(shù)據(jù)結(jié)構(gòu)是對(duì)數(shù)據(jù)的抽象，獨(dú)立于具體數(shù)據(jù)算法是對(duì)處理過程的抽象，獨(dú)立于具體處