第2章數(shù)據(jù)結(jié)構(gòu)及應(yīng)用概念及順序表(已修改)
2025-08-01 09:18 本頁面
【正文】 下一頁 上一頁 停止放映 第 2章數(shù)據(jù)結(jié)構(gòu)及應(yīng)用 概念及順序表 西安交通大學(xué)計教中心 下一頁 上一頁 停止放映 [第 2/42頁 ] 思考問題 數(shù)據(jù)結(jié)構(gòu)要研究什么問題？ 什么是線性數(shù)據(jù)結(jié)構(gòu)和線性表？ 如何描述線性表？ 線性表在計算機中如何存放？有幾種存儲形式？它們的特點是什么？ 如何處理線性數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)？ …… 下一頁 上一頁 停止放映 [第 3/42頁 ] 數(shù)據(jù)結(jié)構(gòu)問題的由來 計算機求解問題的過程步驟： 調(diào)試程序 編制 程序 求解 結(jié)果 運行 程序 結(jié)果輸出 用戶 需求 數(shù)據(jù)類型、格式、 邏輯結(jié)構(gòu) 數(shù)據(jù) 邏輯 運算 數(shù)據(jù)的物理 操作 分析抽象 實際問題 模型求解 問題 模型 命令 編程 求解算法 下一頁 上一頁 停止放映 [第 4/42頁 ] 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是計算機的專業(yè)技術(shù)基礎(chǔ)課。它研究的主要問題有： ?分析數(shù)據(jù)（計算機加工的對象）的特征 ?選擇適當(dāng)邏輯存儲結(jié)構(gòu)和物理存儲結(jié)構(gòu) ?在存儲結(jié)構(gòu)的基礎(chǔ)上實現(xiàn)對數(shù)據(jù)的操作 下一頁 上一頁 停止放映 [第 5/42頁 ] 數(shù)據(jù)結(jié)構(gòu)基本概念 1． 數(shù)據(jù) （ data） 數(shù)據(jù)是指能夠輸入到計算機中，并被計算機識別和處理的符號的集合 。 2．?dāng)?shù)據(jù)元素（ data element） 數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位 。 數(shù)據(jù)元素是一個數(shù)據(jù)整體中相對獨立的單位 。 但它還可以分割成若干個具有不同屬性的項 （ 字段 ） ， 故不是組成數(shù)據(jù)的最小單位 下一頁 上一頁 停止放映 [第 6/42頁 ] 數(shù)據(jù)結(jié)構(gòu) （ data structure） 是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素所組成的集合 。 數(shù)據(jù)結(jié)構(gòu)包含三個方面的內(nèi)容 ， 即數(shù)據(jù)的 邏輯結(jié)構(gòu) ， 數(shù)據(jù)的 存貯結(jié)構(gòu) 和對數(shù)據(jù)所施加的 運算 。 下一頁 上一頁 停止放映 [第 7/42頁 ] 數(shù)據(jù)的邏輯結(jié)構(gòu) 它是描述數(shù)據(jù)間的順序（邏輯）關(guān)系，只是抽象地反映數(shù)據(jù)元素的結(jié)構(gòu)，而不管它們在計算機中如何存放。一般用下列二元組來描述： DS=（ D， R） 其中： D：是數(shù)據(jù)元素的有限集合； R：是數(shù)據(jù)元素之間關(guān)系的集合。 與數(shù)據(jù)在計算機中的存放的 物理位置無關(guān) 下一頁 上一頁 停止放映 [第 8/42頁 ] 舉例 ? 課題組由 1名教師、 1~3名研究生、 1~6名本科生組成；成員關(guān)系是：教師指導(dǎo)研究生、研究生指導(dǎo) 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 } 下一頁 上一頁 停止放映 [第 9/42頁 ] 數(shù)據(jù)的存儲結(jié)構(gòu) ? 又稱物理結(jié)構(gòu) ? 是指數(shù)據(jù)結(jié)構(gòu)在計算機中的表示(又稱映象 ),即數(shù)據(jù)在計算機中的存放 。 數(shù)據(jù)庫中的數(shù)據(jù)存放在計算機中的物理位置 下一頁 上一頁 停止放映 [第 10/42頁 ] 邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的關(guān)系 ?數(shù)據(jù)的 邏輯結(jié)構(gòu) 是從邏輯關(guān)系（某種順序）上觀察數(shù)據(jù)，它是獨立于計算機的；可以在理論上、形式上進行研究、推理、運算等各種操作。 ?數(shù)據(jù)的 存儲結(jié)構(gòu) 是邏輯結(jié)構(gòu)在計算機中的實現(xiàn)，是依賴于計算機的；離開了機器，則無法進行任何操作。 ?任何一個 算法的設(shè)計 取決于選定的邏輯結(jié)構(gòu)；而算法的最終實現(xiàn) 依賴于采用的存儲結(jié)構(gòu)。 下一頁 上一頁 停止放映 [第 11/42頁 ] 數(shù)據(jù)存儲結(jié)構(gòu)分類 ?順序存儲結(jié)構(gòu) ?鏈?zhǔn)酱鎯Y(jié)構(gòu) ?索引存儲結(jié)構(gòu) ?散列存儲結(jié)構(gòu) 下一頁 上一頁 停止放映 [第 12/42頁 ] 順序存儲結(jié)構(gòu) 把數(shù)據(jù)元素按某種順序存放在一塊連續(xù)的存儲單元中的存儲形式。數(shù)據(jù)結(jié)點結(jié)構(gòu) : d1 d2 …… dn 數(shù)據(jù)域 特點 : ? 連續(xù)存放 。邏輯上相鄰 ,物理上也相鄰。 ? 結(jié)構(gòu)簡單，易實現(xiàn)。 ? 插入、刪除操作不便（需大量移動元素）。 下一頁 上一頁 停止放映 [第 13/42頁 ] 鏈?zhǔn)酱鎯Y(jié)構(gòu) 以鏈表形式將數(shù)據(jù)元素存放于任意存儲單元中，可連續(xù)存放，也可以不連續(xù)存放，以指針實現(xiàn)鏈表間的聯(lián)系。數(shù)據(jù)結(jié)點結(jié)構(gòu) : d1 ... d2 dn ^ 數(shù)據(jù)域 指針域 特點 : ? 非連續(xù)存放 ,借助指針來表示元素間的關(guān)系 。 ? 插入、刪除操作簡單，只要修改指針即可；
試題試卷相關(guān)推薦
鄂ICP備17016276號-1