【正文】 下一頁 第 2單元 線性數(shù)據(jù)結構 （一） 主講：劉志強 計算機軟件基礎 Fundamentals of Computer software 下一頁 上一頁 停止放映 第 2 頁 思考問題 數(shù)據(jù)結構要研究什么問題？ 數(shù)組是怎樣的存儲和操作？ 什么是線性數(shù)據(jù)結構和線性表？ 如何描述線性表？ 線性表在計算機中如何存放？有幾種存儲形式？它們的特點是什么？ 如何處理線性數(shù)據(jù)結構中的數(shù)據(jù)？ 下一頁 上一頁 停止放映 第 3 頁 什么是數(shù)據(jù)結構？ 數(shù)據(jù)結構是計算機的專業(yè)技術基礎課。它研究的主要問題： ? 分析數(shù)據(jù)（加工對象）的特征 ? 選擇邏輯存儲結構和物理存儲結構 ? 在存儲結構基礎上實現(xiàn)對數(shù)據(jù)的操作 下一頁 上一頁 停止放映 第 4 頁 第 2單元 線性數(shù)據(jù)結構（一） 教學目標： ? 了解數(shù)據(jù)結構的有關概念 什么是線性 DS、線性表 ? 了解線性 DS的特點 ? 了解線性 DS的邏輯結構、物理結構以及操作 下一頁 上一頁 停止放映 第 5 頁 學習要求 通過本單元的學習，了解并掌握： ? 有關 數(shù)據(jù)結構（ DS）的基本概念 –數(shù)據(jù)元素、 DS、邏輯結構、物理結構、 DS的分類及特點、算法、時間復雜度等 ? 線性 DS的常用存儲結構 –順序、鏈表、索引、散列存儲結構 –單向、雙向、循環(huán)鏈表等 ? 線性 DS的有關算法 –增、刪、改 下一頁 上一頁 停止放映 第 6 頁 涉及的章節(jié) 第 1章的 數(shù)據(jù)結構概述 (P13~P17) 線性表 (P17~P32) 下一頁 上一頁 停止放映 第 7 頁 數(shù)據(jù)結構問題的由來 計算機求解問題的過程步驟： 分析抽象 模型求解 命令 編程 調試程序 編制 程序 運行 程序 求解 結果 結果輸出 用戶 需求 數(shù)據(jù)類型、格式、 邏輯結構 數(shù)據(jù) 邏輯 運算 數(shù)據(jù)的物理 操作 實際問題 問題 模型 求解算法 下一頁 上一頁 停止放映 第 8 頁 問題模型 ? 結構分析 —— 線性方程組 ? 人口預報 —— 微分方程 ? 優(yōu)化問題 —— 線性規(guī)劃 、 非線性規(guī)劃 ? 震動問題 —— 矩陣分析；特征值 、 特征向量 ? 信息管理 —— 二維數(shù)據(jù)表 ? 下棋 —— 人工智能 (樹型結構 ) ? 交通管理 ——最佳道路選擇 (圖型結構 ) 下一頁 上一頁 停止放映 第 9 頁 下棋問題 ? 1 1 ? 1 1 1 ? ? 1 1 1 ? ? 1 1 1 ? ? ? ? 1 1 1 ? ? 1 ? 1 下一頁 上一頁 停止放映 第 10 頁 一、基本概念 ? 數(shù)據(jù)（ Data） 能存于計算機、并被計算機處理的符號的集合。它是客觀事物的符號表示。 ? 數(shù)據(jù)元素（ Element） 是數(shù)據(jù)的基本單位、數(shù)據(jù)集合中的個體。 ? 數(shù)據(jù)結構（ Data Structure） 是帶有結構特征的數(shù)據(jù)元素的集合 ,三要素： DS=數(shù)據(jù)的邏輯結構 +存儲結構 +數(shù)據(jù)的運算 數(shù)據(jù)結構是以數(shù)據(jù)為加工對象，研究數(shù)據(jù)組織方式和相關操作方法的學問。 按某種邏輯關系組織起來的一批數(shù)據(jù)，按一定的存儲方式把它存儲在計算機存儲器中，并在這些數(shù)據(jù)上定義了一個運算的集合，叫做一個數(shù)據(jù)結構 (Data Structures)。 下一頁 上一頁 停止放映 第 11 頁 數(shù)據(jù)結構分類 線性表 堆棧 隊列 串 數(shù)組 樹 二叉樹 圖 線性結構 非線性結構 數(shù)據(jù)結構 DS 下一頁 上一頁 停止放映 第 12 頁 1. 數(shù)據(jù)的邏輯結構 它是描述數(shù)據(jù)間的順序（邏輯）關系，只是抽象地反映數(shù)據(jù)元素的結構，而不管它們在計算機中如何存放。一般用下列二元組來描述： DS=（ D， R） 其中： D：是數(shù)據(jù)元素的有限集合； R：是數(shù)據(jù)元素之間關系的集合。 與數(shù)據(jù)在計算機中的存放的 物理位置無關 下一頁 上一頁 停止放映 第 13 頁 舉例 ? 課題組由 1名教師、 1~3名研究生、 1~6名本科生組成；成員關系是：教師指導研究生、研究生指導 1~2名本科生。 定義 DS如下： Group=（ D， R） 其中： D={T， G1， … ,Gn,S11,… Snm} 1 ? n ? 3 , 1 ? m ? 2 R={R1,R2} R1={T,Gi|1 ? i ? n , 1 ? n ? 3} R2={Gi,Sij|1?i?n ,1? j ? m , 1 ? n ? 3 , 1 ? m ? 2 } 下一頁 上一頁 停止放映 第 14 頁 2. 數(shù)據(jù)的存儲結構 ?又稱物理結構 ?是指數(shù)據(jù)結構在計算機中的表示 (又稱映象 ),即數(shù)據(jù)在計算機中的存放 。 數(shù)據(jù)庫中的數(shù)據(jù)存放在計算機中的物理位置 下一頁 上一頁 停止放映 第 15 頁 邏輯結構和物理結構的關系 ? 數(shù)據(jù)的 邏輯結構 是從邏輯關系（某種順序）上觀察數(shù)據(jù)，它是獨立于計算機的；可以在理論上、形式上進行研究、推理、運算等各種操作。 ? 數(shù)據(jù)的 存儲結構 是邏輯結構在計算機中的實現(xiàn)，是依賴于計算機的；離開了機器，則無法進行任何操作。 ? 任何一個 算法的設計 取決于選定的邏輯結構；而算法的最終實現(xiàn) 依賴于采用的存儲結構。 下一頁 上一頁 停止放映 第 16 頁 數(shù)據(jù)存儲結構分類 ?順序存儲結構 ?鏈式存儲結構 ?索引存儲結構 ?散列存儲結構 下一頁 上一頁 停止放映 第 17 頁 順序存儲結構 把數(shù)據(jù)元素按某種順序存放在一塊連續(xù)的存儲單元中的存儲形式。數(shù)據(jù)結點結構 : d1 d2 …… dn 數(shù)據(jù)域 特點 : ? 連續(xù)存放 。邏輯上相鄰 ,物理上也相鄰。 ? 結構簡單，易實現(xiàn)。 ? 插入、刪除操作不便（需大量移動元素）。 下一頁 上一頁 停止放映 第 18 頁 鏈式存儲結構 以鏈表形式將數(shù)據(jù)元素存放于任意存儲單元中，可連續(xù)存放，也可以不連續(xù)存放，以指針實現(xiàn)鏈表間的聯(lián)系。數(shù)據(jù)結點結構 : d1 ... d2 dn ^ 數(shù)據(jù)域 指針域 特點 : ? 非連續(xù)存放 ,借助指針來表示元素間的關系 。 ? 插入、刪除操作簡單，只要修改指針即可； ? 結構較復雜，需要額外存儲空間。 下一頁 上一頁 停止放映 第 19 頁 索引存儲結構 數(shù)據(jù)按索引形式存放。存儲時分為：數(shù)據(jù)項和索引號；通過索引表記錄邏輯號（記錄號）和物理號（存儲序號）之間的對應關系。數(shù)據(jù)結點結構 : 序 號： 1 2 3 4 5 6 7 數(shù)據(jù)項： 索引號： 12 21 35 2 45 5 10 4 3 2 7 1 6 5 數(shù)據(jù)域 索引順序號 特點： ? 非連續(xù)存放； ? 檢索速度快； ? 增、刪操作簡單。 下一頁 上一頁 停止放映 第 20 頁 散列存儲結構 ?在數(shù)據(jù)元素與存儲位置之間建立一種存儲關系 F，根據(jù)這種關系 F，已知元素 E，就可以得到它的存儲地址，即D=F（ E）。 ?哈希查找中的哈希表就是這樣一種存儲結構。 特點： – 數(shù)據(jù)元素間無內在聯(lián)系； – 存儲形式不定。 下一頁 上一頁 停止放映 第 21 頁 ?數(shù)據(jù)運算是指對存放在物理結構上的數(shù)據(jù) ,按定義的邏輯結構進行的各種操作。 常見操作有： – 輸入、檢索、插入、刪除、修改、排序等。 下一頁 上一頁 停止放映 第 22 頁 算法（ Algorithm） – 是對特定問題求解步驟的一種描述； – 是一組指令的有限集合。 算法和數(shù)據(jù)結構的關系 為了充分地利用系統(tǒng)資源；既要效率高、速度快，又要存儲空間少。顯然，這是矛盾的。 研究算法追求的目標是 時間和空間的適當和諧 下一頁 上一頁 停止放映 第 23 頁 算法的特性 ? 有窮性 一個算法必須總是在執(zhí)行有窮步后結束，且每一步都可在有窮時間內完成； ? 確定性 算法中的每一個指令比須有明確的含義，不能有二義性； ? 可行性 算法中描述的操作都是可通過已經實現(xiàn)的基本運算、執(zhí)行有限次實現(xiàn)的； ? 輸入 一個算法應有 0個或多個輸入； ? 輸出 一個算法應有 1個或多個輸出。 下一頁 上一頁 停止