01數(shù)據(jù)結(jié)構(gòu)概述.ppt

第1章數(shù)據(jù)結(jié)構(gòu)概述 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)處理算法的描述與分析 數(shù)據(jù)結(jié)構(gòu) 是計(jì)算機(jī)專業(yè)的一門重要基礎(chǔ)課程 它研究的問題是從實(shí)際需要中抽象出來(lái)的 是計(jì)算機(jī)科學(xué)各領(lǐng)域以及系統(tǒng)軟件都會(huì)用到的知識(shí) 本章是全書的基礎(chǔ) 主要介紹以下幾個(gè)方面的內(nèi)容 1 1數(shù)據(jù)的邏輯結(jié)構(gòu) 人們要讓計(jì)算機(jī)做事情 都必須涉及三個(gè)問題 一 確定所要加工處理的數(shù)據(jù)間的關(guān)系 以便進(jìn)行處理時(shí) 能夠知道一個(gè)數(shù)據(jù)的后面是哪一個(gè)數(shù)據(jù) 這是數(shù)據(jù)的邏輯結(jié)構(gòu)問題 二 確定要對(duì)數(shù)據(jù)做哪些處理 這是算法描述問題 三 確定以何種方式把數(shù)據(jù)存放到計(jì)算機(jī)的內(nèi)存 并反映出它們間的鄰接關(guān)系 這是數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)問題 1 1 1數(shù)據(jù)及數(shù)據(jù)間的鄰接關(guān)系 數(shù)據(jù) 是信息的載體 是人們用符號(hào)來(lái)表示客觀事物的一種集合 現(xiàn)在把 數(shù)據(jù) 定義為 所有能夠輸入到計(jì)算機(jī)中被計(jì)算機(jī)加工 處理的符號(hào)的集合 通常 數(shù)據(jù)由 數(shù)據(jù)元素 簡(jiǎn)稱 元素 集合而成的 數(shù)據(jù)元素也常被稱作 結(jié)點(diǎn) 頂點(diǎn) 記錄 每個(gè)數(shù)據(jù)元素都具有完整 確定的實(shí)際意義 是數(shù)據(jù)加工處理的對(duì)象 某公司雇員的信息 一個(gè)數(shù)據(jù)元素又可以細(xì)分成由若干個(gè) 數(shù)據(jù)項(xiàng) 組成 數(shù)據(jù)項(xiàng)也常稱作 字段 域 它是數(shù)據(jù)元素中不可再分割的最小標(biāo)識(shí)單位 通常不具備完整 確定的實(shí)際意義 只是反映數(shù)據(jù)元素某一方面的屬性 數(shù)據(jù)結(jié)構(gòu)關(guān)心的是從一個(gè)數(shù)據(jù)能夠找到另一個(gè)數(shù)據(jù)的那種 關(guān)系 人們根據(jù)那種關(guān)系來(lái)組織和存儲(chǔ)數(shù)據(jù) 以便順利 有效地實(shí)現(xiàn)對(duì)數(shù)據(jù)的各種處理要求 如果兩個(gè)數(shù)據(jù)結(jié)點(diǎn)間有著某種邏輯上的聯(lián)系 就稱這兩個(gè)結(jié)點(diǎn)是 鄰接的 若用圓圈代表結(jié)點(diǎn) 用結(jié)點(diǎn)間的一條連線代表它們之間存在的邏輯關(guān)系 那么 就用圖1 1來(lái)表示結(jié)點(diǎn)A和B是 鄰接的 直觀定義 數(shù)據(jù)結(jié)構(gòu)是研究程序設(shè)計(jì)中計(jì)算機(jī)操作的對(duì)象以及它們之間的關(guān)系和運(yùn)算的一門學(xué)科 圖1 1結(jié)點(diǎn)的鄰接 常見的數(shù)據(jù)間的鄰接關(guān)系有三種 線性關(guān)系 樹型關(guān)系以及圖狀關(guān)系 數(shù)據(jù)間的鄰接關(guān)系 就是數(shù)據(jù)的 邏輯結(jié)構(gòu) 1 1 2數(shù)據(jù)的邏輯結(jié)構(gòu) 所謂數(shù)據(jù)間具有 線性 關(guān)系 是指數(shù)據(jù)一個(gè)接一個(gè)地排列成一行 如果所要處理的數(shù)據(jù)間呈線性關(guān)系 那么就說它的邏輯結(jié)構(gòu)是線性的 在線性關(guān)系中 排在第1個(gè)位置的結(jié)點(diǎn)稱為起始結(jié)點(diǎn) 排在最后一個(gè)位置的結(jié)點(diǎn)稱為終端結(jié)點(diǎn) 其余的結(jié)點(diǎn)稱為中間結(jié)點(diǎn) 如圖1 2所示 1 線性關(guān)系 圖1 2線性關(guān)系中的各種結(jié)點(diǎn) 線性關(guān)系的特點(diǎn)是 除起始結(jié)點(diǎn)和終端結(jié)點(diǎn)外 每個(gè)結(jié)點(diǎn)的前面和后面 都有且只有一個(gè)結(jié)點(diǎn)與它鄰接 起始結(jié)點(diǎn)的前面沒有鄰接的結(jié)點(diǎn) 終端結(jié)點(diǎn)的后面沒有鄰接的結(jié)點(diǎn) 簡(jiǎn)單地說 線性關(guān)系的特點(diǎn)是 有頭有尾 順序排列 所謂數(shù)據(jù)間具有 樹型 關(guān)系 是指在數(shù)據(jù)之間具有分支 層次的邏輯關(guān)系 如果所要處理的數(shù)據(jù)之間呈樹型關(guān)系 那么就說它的邏輯結(jié)構(gòu)是樹型的 文件目錄間的邏輯結(jié)構(gòu)就是樹型的 圖1 3所示為一個(gè)樹型目錄圖例 2 樹型關(guān)系 圖1 3文件目錄間的樹型關(guān)系 樹型關(guān)系的特點(diǎn)是 第1層只有一個(gè)結(jié)點(diǎn) 它是樹型關(guān)系的起點(diǎn) 除第1層結(jié)點(diǎn)和分支末端結(jié)點(diǎn)外 位于中間各層的結(jié)點(diǎn)的前面只有一個(gè)結(jié)點(diǎn)與它相鄰接 每個(gè)結(jié)點(diǎn)的后面可以有多個(gè)結(jié)點(diǎn)與它相鄰接 第1層結(jié)點(diǎn)的前面沒有結(jié)點(diǎn)與之鄰接 每個(gè)分支末端結(jié)點(diǎn)的后面沒有結(jié)點(diǎn)與之鄰接 如果數(shù)據(jù)中的任何兩個(gè)元素間都可能有鄰接關(guān)系 那么就說它們之間的關(guān)系是圖狀的 如果所要處理的數(shù)據(jù)之間呈圖狀關(guān)系 那么就說它的邏輯結(jié)構(gòu)是圖狀的 圖狀關(guān)系是數(shù)據(jù)間最復(fù)雜的關(guān)系 圖1 4所示為一張航空網(wǎng)絡(luò)圖 在圖狀關(guān)系中 找不到誰(shuí)是起點(diǎn) 誰(shuí)是終點(diǎn) 各個(gè)結(jié)點(diǎn)的地位可以說都是相同的 3 圖狀關(guān)系 圖1 4航空網(wǎng)絡(luò) 圖狀關(guān)系的特點(diǎn)是 每個(gè)結(jié)點(diǎn)都可能與多個(gè)結(jié)點(diǎn)有鄰接關(guān)系 數(shù)據(jù)間的線性關(guān)系和樹型關(guān)系 都可以視為是圖狀關(guān)系的一個(gè)特例 1 2數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 在計(jì)算機(jī)里存放數(shù)據(jù)時(shí) 既要存儲(chǔ)數(shù)據(jù)本身 也要存儲(chǔ)數(shù)據(jù)間的鄰接關(guān)系 這樣 在對(duì)數(shù)據(jù)進(jìn)行加工處理時(shí) 才能夠方便 正確地從一個(gè)數(shù)據(jù)找到與之鄰接的另一個(gè)數(shù)據(jù) 數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu) 就是研究數(shù)據(jù)在內(nèi)存中的存儲(chǔ)方式 也就是在內(nèi)存中有哪些存放數(shù)據(jù)的方法 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)也稱為數(shù)據(jù)的 物理結(jié)構(gòu) 從整體上來(lái)看 數(shù)據(jù)在存儲(chǔ)器內(nèi)有兩種存放的方式 一種是集中地存放在內(nèi)存中的一個(gè)連接的存儲(chǔ)區(qū) 另一種是利用存儲(chǔ)器中的零星區(qū)域 分散地存放在內(nèi)存地各個(gè)地方 在把數(shù)據(jù)存儲(chǔ)到存儲(chǔ)器時(shí) 是以數(shù)據(jù)元素 即數(shù)據(jù)結(jié)點(diǎn) 為單位進(jìn)行的 分配給一個(gè)數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)區(qū)域 稱為一個(gè) 存儲(chǔ)結(jié)點(diǎn) 在一個(gè)存儲(chǔ)結(jié)點(diǎn)里 除了要有數(shù)據(jù)本身的內(nèi)容外 還要有體現(xiàn)數(shù)據(jù)間鄰接關(guān)系的內(nèi)容 所謂數(shù)據(jù)的 順序式存儲(chǔ) 結(jié)構(gòu) 即是為一組數(shù)據(jù)分配一個(gè)連續(xù)的存儲(chǔ)區(qū) 然后按照數(shù)據(jù)間的鄰接關(guān)系 相繼存放每個(gè)數(shù)據(jù) 這種存儲(chǔ)結(jié)構(gòu) 是借助存儲(chǔ)結(jié)點(diǎn)間的位置關(guān)系 來(lái)體現(xiàn)數(shù)據(jù)元素間的鄰接關(guān)系的 1 2 1順序式存儲(chǔ)結(jié)構(gòu) 比如 圖1 5左側(cè)為一個(gè)數(shù)據(jù)元素所需要的存儲(chǔ)尺寸 size字節(jié) 圖1 5右側(cè)所示為在內(nèi)存里開辟了一個(gè)連續(xù)的存儲(chǔ)區(qū) 用來(lái)依次存放數(shù)據(jù)的若干個(gè)存儲(chǔ)結(jié)點(diǎn) 圖1 5順序存儲(chǔ)結(jié)構(gòu) 所謂數(shù)據(jù)的 鏈?zhǔn)酱鎯?chǔ) 結(jié)構(gòu) 即是存儲(chǔ)每個(gè)數(shù)據(jù)的存儲(chǔ)結(jié)點(diǎn)都由兩個(gè)部分組成 一部分用來(lái)存放數(shù)據(jù)元素本身的信息 另一部分用來(lái)存放與本數(shù)據(jù)元素鄰接的數(shù)據(jù)元素存儲(chǔ)結(jié)點(diǎn)的位置 即存儲(chǔ)指向與之鄰接的存儲(chǔ)結(jié)點(diǎn)的指針 起始地址 通過這些指針反映出數(shù)據(jù)間的邏輯關(guān)系 圖1 6給出的是一個(gè)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 1 2 2鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 圖1 6鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中 存儲(chǔ)結(jié)點(diǎn)里的指針并不局限于只能是一個(gè) 而應(yīng)根據(jù)問題的需要安排為一個(gè)或多個(gè) 如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí) 存儲(chǔ)結(jié)點(diǎn)里只有一個(gè)指針 則稱是單鏈?zhǔn)浇Y(jié)構(gòu) 如果存儲(chǔ)結(jié)點(diǎn)里有兩個(gè)指針 則稱是雙鏈?zhǔn)浇Y(jié)構(gòu) 如此等等 1 3算法及算法分析 人們關(guān)注數(shù)據(jù)地邏輯結(jié)構(gòu) 即鄰接關(guān)系 以及數(shù)據(jù)在內(nèi)存中的存儲(chǔ)結(jié)構(gòu) 最終目的是要使用計(jì)算機(jī)對(duì)數(shù)據(jù)進(jìn)行各種加工處理 比如插入 刪除 查找 修改 排序等 實(shí)現(xiàn)數(shù)據(jù)的加工處理時(shí) 如果問題較大 較復(fù)雜 就應(yīng)該先通過分析列出與加工處理相關(guān)的各個(gè)步驟 然后再去用某種計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言編寫出程序在計(jì)算機(jī)上運(yùn)行 第一步就是所謂的算法描述 第二步就是所謂的程序?qū)崿F(xiàn) 1 算法和程序的區(qū)別 1 3 1算法及算法的描述 算法和計(jì)算機(jī)程序是兩個(gè)不同的概念 所謂 算法 是指解決問題的一種方法步驟或者一個(gè)過程 對(duì)于一個(gè)問題 可以用多種算法來(lái)解決 而一個(gè)給定的算法 則只解決一個(gè)特定的問題 一個(gè)算法應(yīng)該具有以下幾個(gè)重要的特征 1 輸入 一個(gè)算法應(yīng)該有n n 0 個(gè)初始的輸入數(shù)據(jù) 2 輸出 一個(gè)算法可以沒有或有一個(gè)或多個(gè)輸出信息 它們與輸入數(shù)據(jù)之間會(huì)有著某種特定的關(guān)系 3 確定性 算法中的每一個(gè)步驟都必須具有確切的含義 不能有二義性 4 可行性 算法中描述的每一個(gè)操作步驟都必須是可以執(zhí)行的 也就是說 都可以通過計(jì)算機(jī)實(shí)現(xiàn) 5 有窮性 一個(gè)算法必須在經(jīng)歷有限個(gè)步驟之后正常結(jié)束 不能形成死循環(huán) 例1 1判斷下面用文字描述的計(jì)數(shù)過程是否構(gòu)成一個(gè)算法 1 開始 2 n 0 變量n賦初值0 3 n n 1 變量n增1 4 重復(fù)執(zhí)行 3 循環(huán)執(zhí)行增1操作 5 結(jié)束 例1 2編寫一個(gè)算法 按照從小到大的順序排列兩個(gè)數(shù)值變量x y的內(nèi)容 即要求最終有x y 解 用文字描述解決這個(gè)問題的算法如下 1 輸入變量x y的數(shù)值 2 把兩個(gè)數(shù)值中的小者存放到x里 3 把兩個(gè)數(shù)值中的大者存放到y(tǒng)里 4 輸出x y的值 可以看出 上面的描述符合算法的5個(gè)特征 所謂 程序 Program 是指使用某種計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言對(duì)一個(gè)算法的具體實(shí)現(xiàn) 比如 例1 2的算法 可以用如下的C語(yǔ)言程序來(lái)實(shí)現(xiàn) include stdio main intx y temp scanf d d 打印輸出 算法側(cè)重于對(duì)解決問題的方法描述 即要做些什么 而程序是算法在計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言中的實(shí)現(xiàn) 即具體要怎樣去做 算法是可以用不同方法來(lái)描述的 下面給出幾種常見的方法 2 算法的描述 算法描述方法1 使用人們習(xí)慣的自然語(yǔ)言來(lái)描述算法 算法描述方法2 使用人們熟悉的流程圖 即框圖 來(lái)描述算法 例1 4用流程圖描述輸出整數(shù)1 2 3 9 10的過程 解 用流程圖描述輸出整數(shù)1 2 3 9 10的過程的算法如圖1 8所示 圖1 7流程圖的各種圖形名稱和作用 圖1 8用流程圖描述算法 算法描述方法3 用 類C語(yǔ)言 來(lái)描述算法 本書將采用類C語(yǔ)言來(lái)描述算法 算法描述方法4 直接采用C語(yǔ)言來(lái)描述算法 例1 5分別用C語(yǔ)言和類C語(yǔ)言來(lái)描述輸出整數(shù)1 2 3 9 10的過程 解 1 用C語(yǔ)言描述輸出整數(shù)1 2 3 9 10的過程的算法如下 voidnum inti i 1 while i 10 printf i d n i i i 1 2 用類C語(yǔ)言描述輸出整數(shù)1 2 3 9 10的過程的算法如下 voidnum i 1 while i 10 printf i d n i i i 1 現(xiàn)簡(jiǎn)單說明C語(yǔ)言的語(yǔ)法結(jié)構(gòu)如下 1 盡量不要使用算法中涉及的變量做具體說明 2 預(yù)定義常量和類型 defineTRUE1 defineFALSE 1 defineERRORNULL 3 函數(shù)的形式 數(shù)據(jù)類型 函數(shù)名 形式參數(shù) 形式參數(shù)說明 內(nèi)部數(shù)據(jù)說明 執(zhí)行語(yǔ)句組 函數(shù)名 函數(shù)的定義主要由函數(shù)名和函數(shù)體組成 函數(shù)體用花括號(hào) 和 括起來(lái) 函數(shù)中用方括號(hào)括起來(lái)的部分為可選項(xiàng) 函數(shù)名之間的圓括號(hào)不可省略 函數(shù)的結(jié)果可由指針或別的方式傳遞到函數(shù)之外 執(zhí)行語(yǔ)句可由各種類型的語(yǔ)句所組成 兩個(gè)語(yǔ)句之間用 號(hào)分隔 可將函數(shù)中的表達(dá)式的值通過return語(yǔ)句返回給調(diào)用它的函數(shù) 最后的花括號(hào) 之后的 函數(shù)名 為注釋部分 可舍 4 賦值語(yǔ)句簡(jiǎn)單賦值 變量名 表達(dá)式 它表示將表達(dá)式的值賦給左邊的變量 變量 它表示變量加1后賦值給變量 變量 它表示變量減1后賦值給變量 成組賦值 1 變量1 變量2 變量3 變量k 表達(dá)式1 表達(dá)式2 表達(dá)式3 表達(dá)式k 2 數(shù)組名1 下標(biāo)1 下標(biāo)2 數(shù)組名2 下標(biāo)1 下標(biāo)2 串聯(lián)賦值 變量1 變量2 變量3 變量k 表達(dá)式 條件賦值 變量名 條件表達(dá)式 表達(dá)式1 表達(dá)式2 交換賦值 變量1 變量2 表示變量1和變量2互換 5 條件選擇語(yǔ)句if 表達(dá)式 語(yǔ)句 if 表達(dá)式 語(yǔ)句1 else語(yǔ)句2 情況語(yǔ)句switch 表達(dá)式 case判斷值1 語(yǔ)句組1 break case判斷值2 語(yǔ)句組2 break case判斷值n 語(yǔ)句組n break default 語(yǔ)句組 break 注意 switchcase語(yǔ)句是先計(jì)算表達(dá)式的值 然后用其值與判斷值相比較 若它們相一致時(shí) 就執(zhí)行相應(yīng)的case下的語(yǔ)句組 若不一致 則執(zhí)行default下的語(yǔ)句組 其中的方括號(hào)代表可選項(xiàng) 6 循環(huán)語(yǔ)句 for語(yǔ)句for 表達(dá)式1 表達(dá)式2 表達(dá)式3 循環(huán)體語(yǔ)句 首先計(jì)算表達(dá)式1的值 然后求表達(dá)式2的值 若結(jié)果非零則執(zhí)行循環(huán)體語(yǔ)句 最后對(duì)表達(dá)式3運(yùn)算 如此循環(huán) 直到表達(dá)式2的值為零時(shí)止 while語(yǔ)句while 條件表達(dá)式 循環(huán)體語(yǔ)句 while循環(huán)首先計(jì)算條件表達(dá)式的值 若條件表達(dá)式的值非零 則執(zhí)行循環(huán)體語(yǔ)句 然后再次計(jì)算條件表達(dá)式 重復(fù)執(zhí)行 直到條件表達(dá)式的值為假時(shí)退出循環(huán) 執(zhí)行該循環(huán)之后的語(yǔ)句 do while語(yǔ)句do 循環(huán)體語(yǔ)句 while 條件表達(dá)式 該循環(huán)語(yǔ)句首先執(zhí)行循環(huán)體語(yǔ)句 然后再計(jì)算條件表達(dá)式的值 若條件表達(dá)式成立 則再次執(zhí)行循環(huán)體 再計(jì)算條件表達(dá)式的值 直到條件表達(dá)式的值為零 即條件不成立時(shí)結(jié)束循環(huán) 7 輸入 輸出語(yǔ)句輸入語(yǔ)句 用函數(shù)scanf實(shí)現(xiàn) 特別當(dāng)數(shù)據(jù)為字符時(shí) 用getchar函數(shù)實(shí)現(xiàn) 輸出語(yǔ)句 用printf函數(shù)實(shí)現(xiàn) 當(dāng)要輸出字符數(shù)據(jù)時(shí) 用putchar函數(shù)實(shí)現(xiàn) 8 其他一些語(yǔ)句 1 return表達(dá)式或return 用于函數(shù)結(jié)束 2 break語(yǔ)句 可用在循環(huán)語(yǔ)句或case語(yǔ)句中結(jié)束循環(huán)過程或跳出情況語(yǔ)句 3 exit語(yǔ)句 表示出現(xiàn)異常情況時(shí) 控制退出語(yǔ)句 9 注釋形式可用 字符串 或者單行注釋或 文字序列 10 一些基本的函數(shù)如 max函數(shù) 用于求一個(gè)或幾個(gè)表達(dá)式中的最大值 min函數(shù) 用于求一個(gè)或幾個(gè)表達(dá)式中的最小值 abs函數(shù) 用于求表達(dá)式的絕對(duì)值 eof函數(shù) 用于判定文件是否結(jié)束 eoln函數(shù) 用于判斷文本行是否結(jié)束 對(duì)同一個(gè)問題可以設(shè)計(jì)出不同的算法 它們之間當(dāng)然有好差之分 判定算法質(zhì)量時(shí)應(yīng)遵循下面的幾條原則 1 3 2算法分析 算法是否易讀 易于人們理解 算法的結(jié)構(gòu)是否簡(jiǎn)明 清晰 算法的執(zhí)行效率是否高 算法的存儲(chǔ)利用率是否高 算法的可移植性是否好 在算法分析中 人們最看重的是執(zhí)行效率 時(shí)間 和存儲(chǔ)利用率 空間 這兩個(gè)問題 在數(shù)據(jù)結(jié)構(gòu)里 對(duì)一個(gè)算法執(zhí)行效率的度量 稱為 時(shí)間復(fù)雜度 對(duì)一個(gè)算法在執(zhí)行過程中所需占用存儲(chǔ)空間的度量 稱為 空間復(fù)雜度 例1 6變量a b c d中各存一個(gè)整數(shù) 求a b c中的最大者與d的乘積的算法 voidmax1 a b c d a a d b b d c c d if a b x a elsex b if c x x c printf d n x 圖1 9max1的流程 算法2為 voidmax2 a b c d if a b x a elsex b if c x x c x x d printf d n x 圖1 10max2的流程 對(duì)比max1和max2 前者比后者多做了兩次乘法 因此max1比max2得計(jì)算量要大 即如果按照這兩個(gè)算法分別寫出程序執(zhí)行 在相同得軟硬件環(huán)境下 max1花費(fèi)的運(yùn)行時(shí)間要比max2多 這就是說 max2的時(shí)間性能要比max1好 基本操作 是指算法中那些所需時(shí)間與操作數(shù)的具體取值無(wú)關(guān)的操作 賦值 兩個(gè)數(shù)相加或兩個(gè)數(shù)比較大小等 都可以作為基本操作 這些操作的執(zhí)行時(shí)間與具體操作數(shù)是無(wú)關(guān)的 比如說 把數(shù)值1和把數(shù)值1000賦給變量x 計(jì)算機(jī)所花費(fèi)的時(shí)間是相同的 都只是執(zhí)行一個(gè)賦值操作 例1 7分析下面所給算法段中基本操作的執(zhí)行次數(shù) for i 1 i n i y y 1 for j 0 j 2 n j x 解 這里把y y 1 和x 視為基本操作 y y