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