數(shù)據(jù)結(jié)構-第1章-概論精編版

1、數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 什么是數(shù)據(jù)結(jié)構？什么是數(shù)據(jù)結(jié)構？ 數(shù)據(jù)結(jié)構的作用是什么？數(shù)據(jù)結(jié)構的作用是什么？第第1章章 緒論緒論 為什么數(shù)據(jù)結(jié)構是計算機專業(yè)的為什么數(shù)據(jù)結(jié)構是計算機專業(yè)的核心課程核心課程 、也是考研的必考內(nèi)容？、也是考研的必考內(nèi)容？數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 學時分配 總學時64學時 課堂教學48學時 實驗16學時數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 平時考核

2、（10%）：點名、作業(yè)中期考核（10%）：隨堂考試期末考核（50%）：考試實驗成績（30%） ：實驗及報告考核方式數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 校外22/wlxt/course.aspx?courseid=0696或者：校內(nèi)：95/wlxt/course.aspx?courseid=0696作業(yè)網(wǎng)站數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UES

3、TC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 一、一、 意義意義1. 算法和數(shù)據(jù)結(jié)構是算法和數(shù)據(jù)結(jié)構是計算機科學計算機科學的兩大支柱的兩大支柱早期定義為早期定義為: : 研究研究算法算法的科學的科學1近期定義為近期定義為: : 研究研究數(shù)據(jù)數(shù)據(jù)的科學的科學2正在朝著：正在朝著： 研究研究服務服務的科學的科學3第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 2. 數(shù)據(jù)結(jié)構是程序設計的基礎數(shù)據(jù)結(jié)構是程序設計的基礎Algorithms + Data Structures = Prog

4、rams數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構是設計操作系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)、是設計操作系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)、編譯等編譯等系統(tǒng)程序系統(tǒng)程序和各種和各種應用程序應用程序 的重要基礎的重要基礎第第1章章 緒論緒論 有沒有人見過或聽過該公式？有沒有人見過或聽過該公式？有沒有人知道該公式是誰提出的？有沒有人知道該公式是誰提出的？-知識鏈接知識鏈接1數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 Algorithms + Data Structures = Programs是瑞士蘇黎世大學著名的是瑞士蘇黎世大學著名的計算機科學家計算機科學家、Pascal程序設計語言程

5、序設計語言之父之父、結(jié)構化程序設計結(jié)構化程序設計首創(chuàng)者首創(chuàng)者、1984年年圖靈獎圖靈獎獲得者獲得者沃斯沃斯(Niklaus Wirth)于于1976年的年的在這個著名經(jīng)典的公式中：在這個著名經(jīng)典的公式中：“+”生動地表達出了算法和數(shù)據(jù)結(jié)構的相互作用，是程序設生動地表達出了算法和數(shù)據(jù)結(jié)構的相互作用，是程序設計的精髓；計的精髓；“=”言簡意駭?shù)乜坍嫵隽怂惴ê蛿?shù)據(jù)結(jié)構是構成計算機程序言簡意駭?shù)乜坍嫵隽怂惴ê蛿?shù)據(jù)結(jié)構是構成計算機程序的兩個關鍵要素。的兩個關鍵要素。計算機程序是使用計算機程序是使用計算機程序設計語言計算機程序設計語言描述算法和數(shù)據(jù)結(jié)構，描述算法和數(shù)據(jù)結(jié)構，從而在計算機上實現(xiàn)應用問題的求解

6、。從而在計算機上實現(xiàn)應用問題的求解。知識鏈接知識鏈接1 - 算法數(shù)據(jù)結(jié)構程序算法數(shù)據(jù)結(jié)構程序有沒有人知道圖靈獎？有沒有人知道圖靈獎？-知識鏈接知識鏈接2數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 圖靈獎圖靈獎圖靈獎是圖靈獎是美國計算機協(xié)會于美國計算機協(xié)會于1966年年設立的，設立的，其名稱取自計算機科學先驅(qū)，英國科學家阿其名稱取自計算機科學先驅(qū)，英國科學家阿蘭蘭圖靈。獲獎者的貢獻必須在計算機領域圖靈。獲獎者的貢獻必須在計算機領域具有具有持久而重大的影響持久而重大的影響，有，有“計算機界諾貝計算機界諾貝爾獎爾獎”之稱，或相當于數(shù)學界的

7、菲爾茲獎。之稱，或相當于數(shù)學界的菲爾茲獎。 知識鏈接知識鏈接2- 圖靈獎圖靈獎 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 圖靈獎圖靈獎2000年年，姚期智姚期智(Andrew Chi-Chih Yao) ，由于在計算理，由于在計算理論方面的貢獻而獲獎，包括偽隨機數(shù)的生成算法、加密算論方面的貢獻而獲獎，包括偽隨機數(shù)的生成算法、加密算法和通訊復雜性。（法和通訊復雜性。（唯一一位華人獲此殊榮唯一一位華人獲此殊榮） 2006年，年，F(xiàn)rances E. Allen （首位女性獲獎者首位女性獲獎者，IBM終終生院士生院士(IBM Fello

8、w Emerita)），在編譯器優(yōu)化的理論和），在編譯器優(yōu)化的理論和實踐方面做出的開創(chuàng)性貢獻而獲獎。她的工作奠定了現(xiàn)代實踐方面做出的開創(chuàng)性貢獻而獲獎。她的工作奠定了現(xiàn)代優(yōu)化編譯器和自動并行化執(zhí)行的基礎。優(yōu)化編譯器和自動并行化執(zhí)行的基礎。 1975 Allen Newell、Herbert A. Simon（香農(nóng)）由于在人工智能、人類識別心理和表處理的基礎貢獻。由于在人工智能、人類識別心理和表處理的基礎貢獻。香農(nóng)：通信科學的奠基人、信息論之父是唯一一位獲得諾香農(nóng)：通信科學的奠基人、信息論之父是唯一一位獲得諾貝爾獎和圖靈獎的學者。貝爾獎和圖靈獎的學者。 1974 Donald E. Knuth由于

9、在算法分析和程序語言設計方面的重要貢獻，計算機由于在算法分析和程序語言設計方面的重要貢獻，計算機程序設計藝術的作者。程序設計藝術的作者。 知識鏈接知識鏈接2- 圖靈獎圖靈獎 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 算法和數(shù)據(jù)結(jié)構是計算機科學的兩大支柱算法和數(shù)據(jù)結(jié)構是計算機科學的兩大支柱數(shù)據(jù)結(jié)構是程序設計的基礎數(shù)據(jù)結(jié)構是程序設計的基礎第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 二、要求二、要求掌握各類掌握各類基本數(shù)據(jù)結(jié)構類型基本數(shù)據(jù)結(jié)構類型和相應的

10、和相應的存儲結(jié)構存儲結(jié)構提高閱讀和編寫提高閱讀和編寫算法算法的能力的能力能針對給定問題，能針對給定問題，選擇選擇相適應的數(shù)據(jù)結(jié)構，并相適應的數(shù)據(jù)結(jié)構，并能能設計和分析算法設計和分析算法掌握典型算法思想及程序?qū)崿F(xiàn)；掌握典型算法思想及程序?qū)崿F(xiàn)；培養(yǎng)算法設計能力及編程能力；培養(yǎng)算法設計能力及編程能力；為后繼課程學習及從事軟件開發(fā)打好基礎。為后繼課程學習及從事軟件開發(fā)打好基礎。 第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 1.2 計算機問題求解過程計算機問題求解過程 第第1章章 緒論緒論 問題的理解問題的理解數(shù)據(jù)結(jié)構設

11、計數(shù)據(jù)結(jié)構設計算法設計算法設計算法分析算法分析程序?qū)崿F(xiàn)程序?qū)崿F(xiàn)數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 計算機問題求解計算機問題求解5步驟步驟1. 問題的理解：清楚問題的輸入、要求和輸出；問題的理解：清楚問題的輸入、要求和輸出；2. 數(shù)據(jù)結(jié)構設計：一方面要選擇或設計能有效表示和數(shù)據(jù)結(jié)構設計：一方面要選擇或設計能有效表示和存儲應用問題中所涉及的數(shù)據(jù)對象的數(shù)據(jù)結(jié)構，同時存儲應用問題中所涉及的數(shù)據(jù)對象的數(shù)據(jù)結(jié)構，同時還要選擇或設計能支持算法策略實現(xiàn)的數(shù)據(jù)結(jié)構；還要選擇或設計能支持算法策略實現(xiàn)的數(shù)據(jù)結(jié)構；3. 算法設計：包括選擇算法策略、

12、用適當?shù)姆绞矫枋鏊惴ㄔO計：包括選擇算法策略、用適當?shù)姆绞矫枋龊椭鸩郊毣惴ú襟E；和逐步細化算法步驟；4. 算法分析：發(fā)現(xiàn)有改進完善之處，返回第二步，重算法分析：發(fā)現(xiàn)有改進完善之處，返回第二步，重新選擇或設計數(shù)據(jù)結(jié)構、重新設計算法；新選擇或設計數(shù)據(jù)結(jié)構、重新設計算法；5. 程序?qū)崿F(xiàn)：用某種計算機程序設計語言，定義數(shù)據(jù)程序?qū)崿F(xiàn)：用某種計算機程序設計語言，定義數(shù)據(jù)結(jié)構、編寫實現(xiàn)算法的代碼，在計算機上調(diào)試和運行結(jié)構、編寫實現(xiàn)算法的代碼，在計算機上調(diào)試和運行程序。程序。 第第1章章 緒論緒論 有誰編過程序？有誰編過程序？-知識鏈接知識鏈接3數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學

13、計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 1954年，年，IBM開始研制開始研制Fortran（Formula Translation）語言，）語言，57年研制完成。如今演年研制完成。如今演變?yōu)樽優(yōu)閂isual Fortran。 11959年，年，Grace Murray Hopper 開始研開始研制制COBOL （Common Business-Oriented Language）語言，）語言，61年完成。年完成。21965年，年，Thomas E. Kurtz和和John Kemeny研制研制了了BASIC（Beginners All Purpose Symbolic Instructio

14、n Code），后來發(fā)展為，后來發(fā)展為Visual BASIC 。3知識鏈接知識鏈接3- 程序設計語言程序設計語言 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 1967年，年，Niklaus Wirth開始在開始在Algol基礎基礎上開發(fā)出上開發(fā)出PASCAL語言，語言，71年完成年完成 。41972年，年，Bell 實驗室發(fā)明了實驗室發(fā)明了C語言。語言。 80年年，Bell 實驗室的實驗室的Bjarne Stroustrup設計實設計實現(xiàn)了現(xiàn)了C+語言語言 51979年，年，Jean Ichbiah研制了研制了Ada語言，語言，被

15、廣泛用于美國軍方。被廣泛用于美國軍方。6知識鏈接知識鏈接3- 程序設計語言程序設計語言 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 19831983年，年，BorlandBorland公司成立并推出公司成立并推出Turbo Turbo PascalPascal，成為，成為PCPC上最流行的開發(fā)工具。上最流行的開發(fā)工具。Turbo CTurbo C、Borland C/C+Borland C/C+，與微軟的，與微軟的Visual Visual C+C+對抗，對抗，BorlandBorland推出的推出的PascalPascal現(xiàn)代版現(xiàn)

16、代版DelphiDelphi號稱號稱VBVB（Visual BasicVisual Basic）的殺手。）的殺手。71989年，年，Tim Berners-Lee 創(chuàng)作了創(chuàng)作了World Wide Web，HTML語言開始流行。語言開始流行。81995年，年，Java語言誕生。語言誕生。9知識鏈接知識鏈接3- 程序設計語言程序設計語言 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 這里需要強調(diào)以下三點這里需要強調(diào)以下三點：（1 1）第二步中選擇或設計數(shù)據(jù)結(jié)構，以及第三步中選擇算）第二步中選擇或設計數(shù)據(jù)結(jié)構，以及第三步中選擇算法策略都是

17、非常重要的，是影響算法性能的關鍵。法策略都是非常重要的，是影響算法性能的關鍵。（2 2）算法與程序是有區(qū)別的。算法是求解問題的一種方法）算法與程序是有區(qū)別的。算法是求解問題的一種方法或一個過程，是將輸入按要求轉(zhuǎn)換成輸出的一個變換。通?；蛞粋€過程，是將輸入按要求轉(zhuǎn)換成輸出的一個變換。通常對一個待求解的問題可以有多種算法。程序是用某種程序設對一個待求解的問題可以有多種算法。程序是用某種程序設計語言對算法的具體實現(xiàn)。它們之間的主要區(qū)別在：有窮性計語言對算法的具體實現(xiàn)。它們之間的主要區(qū)別在：有窮性和描述方法。和描述方法。 算法是有窮的；程序可以是無窮的，算法是有窮的；程序可以是無窮的，例如操作系統(tǒng)是一

18、組例如操作系統(tǒng)是一組程序，而不是算法，開機后，操作系統(tǒng)就會不停地運行，哪程序，而不是算法，開機后，操作系統(tǒng)就會不停地運行，哪怕沒有作業(yè)需要處理，它也在執(zhí)行等待進程。怕沒有作業(yè)需要處理，它也在執(zhí)行等待進程。 程序是用程序設計語言描述程序是用程序設計語言描述，在計算機上可以執(zhí)行；，在計算機上可以執(zhí)行；算法除了可以用程序設計語言描述以外，還可以用框圖、自算法除了可以用程序設計語言描述以外，還可以用框圖、自然語言等方式描述。然語言等方式描述。第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 這里需要強調(diào)以下三點這里需要強調(diào)以

19、下三點：（3）算法與數(shù)據(jù)結(jié)構是有聯(lián)系的。）算法與數(shù)據(jù)結(jié)構是有聯(lián)系的。一方面算法所求解問題的對象需要用適當?shù)臄?shù)一方面算法所求解問題的對象需要用適當?shù)臄?shù)據(jù)結(jié)構存儲到計算機中，算法才能對其進行操據(jù)結(jié)構存儲到計算機中，算法才能對其進行操作和處理；作和處理；另一方面，算法本身需要適當?shù)臄?shù)據(jù)結(jié)構來支另一方面，算法本身需要適當?shù)臄?shù)據(jù)結(jié)構來支持算法策略的實現(xiàn)。持算法策略的實現(xiàn)。一個高效的算法常常是因為選用或設計了一個一個高效的算法常常是因為選用或設計了一個好的數(shù)據(jù)結(jié)構，算法與數(shù)據(jù)結(jié)構是計算機問題好的數(shù)據(jù)結(jié)構，算法與數(shù)據(jù)結(jié)構是計算機問題求解的關鍵技術。求解的關鍵技術。 下面我們以迷宮為例，來初步認識什么是數(shù)據(jù)下

20、面我們以迷宮為例，來初步認識什么是數(shù)據(jù)結(jié)構和算法。結(jié)構和算法。第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 1.3 迷宮問題迷宮問題 1. 問題描述問題描述 從出發(fā)點（入口）開始，在給定的空間從出發(fā)點（入口）開始，在給定的空間中，沿可行的路徑進行探索，直到達到目標中，沿可行的路徑進行探索，直到達到目標（出口）。（出口）。 在資源勘探中，在戰(zhàn)爭或游戲中，都會有在資源勘探中，在戰(zhàn)爭或游戲中，都會有類似的情景，在給定的空間中，如森林、山類似的情景，在給定的空間中，如森林、山洞、沙漠等，搜索特定目標，如出路、人或洞、沙漠

21、等，搜索特定目標，如出路、人或物等。這類問題都可以歸結(jié)為迷宮問題。物等。這類問題都可以歸結(jié)為迷宮問題。 第第1章章 緒論緒論 如何讓計算機來如何讓計算機來求解迷宮問題？求解迷宮問題？數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 需要需要解決以下幾個問題：解決以下幾個問題： 如何表示給定的空間和可行的路徑？如何表示給定的空間和可行的路徑？ 如何表示入口和出口？如何表示入口和出口？ 當有多條可行的路徑時如何選擇？當有多條可行的路徑時如何選擇？ 當某條路徑在某一點再沒有可行之路時如當某條路徑在某一點再沒有可行之路時如何處理？何處理？前兩個問

22、題屬于數(shù)據(jù)結(jié)構選擇和設計，后兩前兩個問題屬于數(shù)據(jù)結(jié)構選擇和設計，后兩個問題涉及算法設計。個問題涉及算法設計。第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 2. 迷宮表示迷宮表示可以用一個可以用一個m行行n列的二維數(shù)組列的二維數(shù)組mazemn來表示迷宮空間（或稱迷宮地圖），來表示迷宮空間（或稱迷宮地圖），并約定：并約定：當數(shù)組元素當數(shù)組元素mazeij=0，表示通路，表示通路， mazeij=1，表示不通；，表示不通；入口為左上角入口為左上角maze11，出口為右下角，出口為右下角mazemn；第第1章章 緒論緒論

23、 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 迷宮地圖簡化迷宮地圖簡化 為了使探索方向個數(shù)一致，可在原來的迷為了使探索方向個數(shù)一致，可在原來的迷宮地圖四周都擴展一個點，即增加兩行和兩宮地圖四周都擴展一個點，即增加兩行和兩列，并將迷宮四周增加點的值全部置為列，并將迷宮四周增加點的值全部置為1，表，表示是墻，不能通行。示是墻，不能通行。 這樣做使得原迷宮地圖中的所有點都成為這樣做使得原迷宮地圖中的所有點都成為了中間點，不用再判斷當前點是角點、邊點、了中間點，不用再判斷當前點是角點、邊點、還是中間點，每個點的探索方向均為還是中間點，每個點

24、的探索方向均為8個。個。 第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 第第1章章 緒論緒論 0 1 2 3 4 5 6 7 8 90123456711111111111111111111111111111111011101111010111101000001011101111001100001100110入口(1,1)出口(6,8)數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 增量數(shù)組增量數(shù)組DeltaXY在某一點（在某一點（x，y），有），有8個可以

25、探索的方向：個可以探索的方向： 第第1章章 緒論緒論 x-1，y-1x，y-1x+1，y-1 x-1，yx，y x+1，yx-1，y+1x，y+1x+1，y+1假設：從正東方向開始，沿順時針方向依次假設：從正東方向開始，沿順時針方向依次進行探索，則增量數(shù)組進行探索，則增量數(shù)組DeltaXY 為：為：x y110-1-1-10101 1 10-1-1-1數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 已解決問題和還未解決的問題已解決問題和還未解決的問題1. 二維數(shù)組二維數(shù)組mazem+2n+2來表示迷宮，解決了來表示迷宮，解決了迷宮地圖的

26、存儲；迷宮地圖的存儲；2. 一維數(shù)組一維數(shù)組DeltaXY8來記載了來記載了8個探索方向的坐個探索方向的坐標增量，將標增量，將8個探索方向數(shù)字化為個探索方向數(shù)字化為0到到7，并將向下，并將向下一點前進的操作統(tǒng)一為當前點的坐標一點前進的操作統(tǒng)一為當前點的坐標+沿該探索方沿該探索方向的增量，即可得到下一點的坐標；向的增量，即可得到下一點的坐標；3. 當某點無路可通行時當某點無路可通行時，需要從該點返回到前一點，需要從該點返回到前一點，再從前一點選擇下一個方向繼續(xù)進行探索，即需要再從前一點選擇下一個方向繼續(xù)進行探索，即需要知道前一點和前一點當前探索的方向。因此，我們知道前一點和前一點當前探索的方向。

27、因此，我們需要保留依次到達的各點的坐標和到達該點的方向；需要保留依次到達的各點的坐標和到達該點的方向；4. 還需要防止重復到達某點，避免在迷宮中兜死圈還需要防止重復到達某點，避免在迷宮中兜死圈子，需要記載已到達過的點。子，需要記載已到達過的點。 第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 如何保留到達各點的如何保留到達各點的坐標坐標和到達時的探索和到達時的探索方向方向？可以選用一個數(shù)據(jù)結(jié)構可以選用一個數(shù)據(jù)結(jié)構-棧，棧，該棧中元素是由行號該棧中元素是由行號x、列號、列號y和到達該點的探索方和到達該點的探索方向向d

28、組成的三元組（組成的三元組（x，y，d），），其中其中x為到達點的橫坐標或行號，為到達點的橫坐標或行號，y為到達點的縱坐為到達點的縱坐標或列號，標或列號，d為為07中的一個數(shù)字，表示到達坐標中的一個數(shù)字，表示到達坐標為（為（x，y）的點的方向。）的點的方向。例如從（例如從（2，2）點沿東南方向到達（）點沿東南方向到達（3，3）點時，）點時，在棧中要記錄一個三元組（在棧中要記錄一個三元組（3，3，1）。）。 第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 如何避免在迷宮中如何避免在迷宮中兜死圈子兜死圈子？可以用以下兩

29、種方法解決該問題：可以用以下兩種方法解決該問題：設置一個標志數(shù)組設置一個標志數(shù)組markmn，所有元素初始化為，所有元素初始化為0； 在探索中，當所探索的點在探索中，當所探索的點( i，j )對應的對應的markij=0時，時，才進入該點，并將才進入該點，并將markij置為置為1； 當所探索的點當所探索的點( i，j )對應的對應的markij=1時，表明已探索時，表明已探索過，不需要再進入。過，不需要再進入。2. 當?shù)竭_某點（當?shù)竭_某點（i，j）后，在迷宮地圖的該點坐標上標記特殊）后，在迷宮地圖的該點坐標上標記特殊值，例如將值，例如將mazeij 置置 -1，以便區(qū)別未到達過的點。，以便區(qū)

30、別未到達過的點。第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 迷宮小結(jié)迷宮小結(jié)數(shù)據(jù)結(jié)構有兩大用途：數(shù)據(jù)結(jié)構有兩大用途：一是用于一是用于存放要處理的數(shù)據(jù)存放要處理的數(shù)據(jù)，如迷宮地圖；，如迷宮地圖；二是用于二是用于實現(xiàn)算法策略實現(xiàn)算法策略，如迷宮例子中探索，如迷宮例子中探索方向增量數(shù)組、回溯的棧、避免重復走的標方向增量數(shù)組、回溯的棧、避免重復走的標志數(shù)組或特殊標記）志數(shù)組或特殊標記）第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 1.4

31、數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構一、一、DS主要研究內(nèi)容主要研究內(nèi)容二、數(shù)據(jù)結(jié)構概念及相關術語二、數(shù)據(jù)結(jié)構概念及相關術語第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 27063010班號班號 83202670 計算機學院辦公室電話號碼計算機學院辦公室電話號碼610054 電子科技大學郵編電子科技大學郵身份證號碼身份證號碼 例例1：2706301083202670610054510102197806187481結(jié)論結(jié)論1.雜亂的數(shù)據(jù)不能表達和交流信息雜亂的數(shù)據(jù)不能表達和交流信息2706301

32、083202670610054510102197806187481第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 例例2 電話號碼查詢電話號碼查詢 設有一個電話號碼薄，它記錄了設有一個電話號碼薄，它記錄了n個人的名字和其相應的電話個人的名字和其相應的電話號碼，如：號碼，如：(a(a1 1，b b1 1)(a)(a2 2，b b2 2) )(a(an n，b bn n) )其中其中ai，bi(i=1，2n) 分別表示某人的名字和對應電話號碼分別表示某人的名字和對應電話號碼問題：問題：設計一個算法，當給定一個名字時，該

33、算法能查找出相設計一個算法，當給定一個名字時，該算法能查找出相應的電話號碼，如果該電話簿中沒有這個名字，則該給出沒應的電話號碼，如果該電話簿中沒有這個名字，則該給出沒有此人信息。有此人信息。要做的事情：要做的事情：如何表示和存儲電話號碼簿的所有信息如何表示和存儲電話號碼簿的所有信息數(shù)據(jù)結(jié)構設計數(shù)據(jù)結(jié)構設計如何實現(xiàn)快速查找如何實現(xiàn)快速查找-算法設計算法設計結(jié)論結(jié)論2.數(shù)據(jù)之間是有聯(lián)系的數(shù)據(jù)之間是有聯(lián)系的這些聯(lián)系常常影響算法的選擇和效率。這些聯(lián)系常常影響算法的選擇和效率。DS就是要研究數(shù)據(jù)之間的聯(lián)系。就是要研究數(shù)據(jù)之間的聯(lián)系。數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科

34、學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 職工號職工號姓名姓名性別性別出生年月出生年月職務職務單位單位0101郭建成郭建成男男19521952年年8 8月月處長處長 0202肖明肖明男男19581958年年6 6月月科長科長教材科教材科0303晨曦晨曦女女19541954年年1212月月科長科長考務科考務科0404趙麗霞趙麗霞女女19621962年年8 8月月主任主任辦公室辦公室0505崔小龍崔小龍男男19491949年年8 8月月科員科員教材科教材科0606袁莉袁莉女女19651965年年4 4月月科員科員教材科教材科0707王芳王芳女女19621962年年6 6月月科員科員考務科考務科0808張宏

35、愿張宏愿男男19571957年年3 3月月科員科員考務科考務科0909馬明華馬明華男男19651965年年1010月月科員科員考務科考務科1010李冰李冰男男19661966年年7 7月月科員科員辦公室辦公室表中共有表中共有1010條職工記錄，每條職工記錄都由條職工記錄，每條職工記錄都由6 6個數(shù)據(jù)項組個數(shù)據(jù)項組成，每條職工記錄的職工號各不相同，我們將用職工號來成，每條職工記錄的職工號各不相同，我們將用職工號來代表整個職工記錄。代表整個職工記錄。 例例3 教務處人事簡表教務處人事簡表 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 按職

36、工年齡從大到小排列按職工年齡從大到小排列 在人事管理中，我們經(jīng)常將職工年齡做在人事管理中，我們經(jīng)常將職工年齡做為職工退休的重要依據(jù)。將職工記錄的排列為職工退休的重要依據(jù)。將職工記錄的排列順序按職工年齡從大到小排列，查詢職工的順序按職工年齡從大到小排列，查詢職工的年齡或出生年月是很方便的。年齡或出生年月是很方便的。 0 5 0 1 0 3 0 8 0 2 0 7 0 4 0 6 0 9 1 0 在這類人事管理的數(shù)學模型中，計算機在這類人事管理的數(shù)學模型中，計算機處理的對象之間通常存在著一種最簡單的線處理的對象之間通常存在著一種最簡單的線性關系，這類數(shù)學模型稱為線性結(jié)構。性關系，這類數(shù)學模型稱為線

37、性結(jié)構。 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 職工之間領導和被領導的關系職工之間領導和被領導的關系0 5 0 1 0 3 0 8 0 2 0 7 0 4 0 6 0 9 1 0 該圖好像倒著畫的一棵樹，一個領導者領導著多該圖好像倒著畫的一棵樹，一個領導者領導著多個被領導者，職工記錄之間存在著個被領導者，職工記錄之間存在著1：n的聯(lián)系的聯(lián)系（n1），這類數(shù)學模型稱為樹型結(jié)構。），這類數(shù)學模型稱為樹型結(jié)構。數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 職工之間的朋友關系

38、職工之間的朋友關系 好友的關系是相互的，在該圖中我們用一條無好友的關系是相互的，在該圖中我們用一條無向邊來代表好友關系。職工記錄之間的好友關系向邊來代表好友關系。職工記錄之間的好友關系存在著存在著m：n的聯(lián)系（的聯(lián)系（m1，n1），這類數(shù)學模型），這類數(shù)學模型稱為圖形結(jié)構。稱為圖形結(jié)構。 0 5 0 1 0 3 0 8 0 2 0 7 0 4 0 6 0 9 1 0 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 結(jié)論結(jié)論 數(shù)據(jù)之間是有結(jié)構的數(shù)據(jù)之間是有結(jié)構的例例3中數(shù)據(jù)之間存在著各種結(jié)構：線性結(jié)構、中數(shù)據(jù)之間存在著各種結(jié)構：線性結(jié)構、

39、樹狀結(jié)構、圖狀結(jié)構樹狀結(jié)構、圖狀結(jié)構DS就是要研究數(shù)據(jù)之間的各類結(jié)構就是要研究數(shù)據(jù)之間的各類結(jié)構數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 例例4：圖書目錄管理：圖書目錄管理設書目含：書名，作者，登錄號，分類，出版年月設書目含：書名，作者，登錄號，分類，出版年月對圖書目錄常有如下操作：對圖書目錄常有如下操作： 查找：某書在書庫中是否存在？查找：某書在書庫中是否存在？ 插入：購進新書時的登錄；插入：購進新書時的登錄； 刪除：報廢或丟失的書，需從目錄中去掉。刪除：報廢或丟失的書，需從目錄中去掉。結(jié)論結(jié)論 在某種數(shù)據(jù)結(jié)構上可定義一組運算在

40、某種數(shù)據(jù)結(jié)構上可定義一組運算DS就是要研究各類數(shù)據(jù)結(jié)構上的各種運算就是要研究各類數(shù)據(jù)結(jié)構上的各種運算數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 DS主要研究內(nèi)容主要研究內(nèi)容數(shù)據(jù)的各種邏輯結(jié)構和物理結(jié)構，以及數(shù)據(jù)的各種邏輯結(jié)構和物理結(jié)構，以及它們之間的相應關系它們之間的相應關系對每種結(jié)構定義相適應的各種運算對每種結(jié)構定義相適應的各種運算設計出相應的算法設計出相應的算法分析算法的效率分析算法的效率常見的數(shù)據(jù)結(jié)構有：數(shù)組、棧、隊列、表、常見的數(shù)據(jù)結(jié)構有：數(shù)組、棧、隊列、表、串、樹、圖和文件等串、樹、圖和文件等數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電

41、子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 數(shù)據(jù)是對客觀事物的符號表示，是信息的載體。數(shù)據(jù)是對客觀事物的符號表示，是信息的載體。在計算機科學中數(shù)據(jù)指所有能夠被計算機在計算機科學中數(shù)據(jù)指所有能夠被計算機識別識別的的符號符號集合。集合。1.1.數(shù)據(jù)（數(shù)據(jù)（datadata）: :“識別識別”：輸入、存儲、處理、顯示、輸出：輸入、存儲、處理、顯示、輸出“符號符號”：數(shù)字、字母、漢字、語音、圖形、圖像：數(shù)字、字母、漢字、語音、圖形、圖像相關術語相關術語第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構

42、與算法 是數(shù)據(jù)（集合）中的一個是數(shù)據(jù)（集合）中的一個“個體個體”2. 2. 數(shù)據(jù)元素（數(shù)據(jù)元素（Data ElementData Element） : :是數(shù)據(jù)結(jié)構中討論的是數(shù)據(jù)結(jié)構中討論的基本基本單位單位數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 3.數(shù)據(jù)項數(shù)據(jù)項（Data Item） ：是數(shù)據(jù)結(jié)構中討論的是數(shù)據(jù)結(jié)構中討論的最小最小單位單位數(shù)據(jù)元素可以是數(shù)據(jù)項的集合數(shù)據(jù)元素可以是數(shù)據(jù)項的集合例如：例如：描述一個運動員的數(shù)據(jù)元素可以是描述一個運動員的數(shù)據(jù)元素可以是年年 月月 日日稱之為組合項稱之為組合項數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電

43、子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 4. 4. 數(shù)據(jù)對象（數(shù)據(jù)對象（Data ObjectData Object）：）： 數(shù)據(jù)對象數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。合，是數(shù)據(jù)的一個子集。 例如，迷宮數(shù)據(jù)對象中的數(shù)據(jù)元素是一個例如，迷宮數(shù)據(jù)對象中的數(shù)據(jù)元素是一個個點；電話薄數(shù)據(jù)對象中數(shù)據(jù)元素是每個個點；電話薄數(shù)據(jù)對象中數(shù)據(jù)元素是每個人的記錄；圖書目錄數(shù)據(jù)對象中數(shù)據(jù)元素人的記錄；圖書目錄數(shù)據(jù)對象中數(shù)據(jù)元素是一張張書目卡片。是一張張書目卡片。 數(shù)據(jù)、數(shù)據(jù)對象、數(shù)據(jù)元素和數(shù)據(jù)項這四數(shù)據(jù)、數(shù)據(jù)對象、數(shù)據(jù)元素和數(shù)據(jù)

44、項這四個概念他們相互是個概念他們相互是集合和子集的關系集合和子集的關系。即。即，數(shù)據(jù)對象是數(shù)據(jù)的子集，數(shù)據(jù)元素是數(shù)，數(shù)據(jù)對象是數(shù)據(jù)的子集，數(shù)據(jù)元素是數(shù)據(jù)對象的子集，數(shù)據(jù)項又是數(shù)據(jù)元素的子據(jù)對象的子集，數(shù)據(jù)項又是數(shù)據(jù)元素的子集。集。數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 所謂結(jié)構就是數(shù)據(jù)元素之間的關系，即描述數(shù)所謂結(jié)構就是數(shù)據(jù)元素之間的關系，即描述數(shù)據(jù)元素之間的運算及運算規(guī)則。據(jù)元素之間的運算及運算規(guī)則。用集合的形式描述，數(shù)據(jù)結(jié)構是一個二元組：用集合的形式描述，數(shù)據(jù)結(jié)構是一個二元組：DS=(DDS=(D，R)R)其中：其中：D D

45、是數(shù)據(jù)元素的集合，是數(shù)據(jù)元素的集合，R R是是D D上上關系的集合。關系的集合。簡言之，數(shù)據(jù)元素和其相互關系稱為數(shù)據(jù)結(jié)構。簡言之，數(shù)據(jù)元素和其相互關系稱為數(shù)據(jù)結(jié)構。5.5.數(shù)據(jù)結(jié)構：數(shù)據(jù)結(jié)構：帶結(jié)構結(jié)構的數(shù)據(jù)元素的集合數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 第第1章章 緒論緒論 Data_Structure （D，L，S，O），其中：），其中：D（Data）是數(shù)據(jù)元素的有限集，是存儲和操作的對象；）是數(shù)據(jù)元素的有限集，是存儲和操作的對象；L（Logical Structure）是數(shù)據(jù)元素集合）是數(shù)據(jù)元素集合D中數(shù)據(jù)元素之間中數(shù)據(jù)

46、元素之間客觀存在的關系的有限集，稱為客觀存在的關系的有限集，稱為邏輯結(jié)構邏輯結(jié)構；S（Storage Structure）是數(shù)據(jù)元素集合）是數(shù)據(jù)元素集合D和數(shù)據(jù)元素之和數(shù)據(jù)元素之間的關系集合間的關系集合L在計算機中的存儲表示，稱為在計算機中的存儲表示，稱為存儲結(jié)構存儲結(jié)構或物或物理結(jié)構；理結(jié)構；O（Operation）是在數(shù)據(jù)元素集合）是在數(shù)據(jù)元素集合D上規(guī)定的一組操作。上規(guī)定的一組操作。簡言之，數(shù)據(jù)結(jié)構包含：數(shù)據(jù)元素、數(shù)據(jù)元素之間的邏輯簡言之，數(shù)據(jù)結(jié)構包含：數(shù)據(jù)元素、數(shù)據(jù)元素之間的邏輯關系、邏輯關系在計算機中的存儲表示、以及所規(guī)定的操關系、邏輯關系在計算機中的存儲表示、以及所規(guī)定的操作這四部

47、分。作這四部分。我們認為：數(shù)據(jù)結(jié)構應由一個四元組來表示：我們認為：數(shù)據(jù)結(jié)構應由一個四元組來表示：數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 6.6.邏輯結(jié)構邏輯結(jié)構邏輯結(jié)構是指數(shù)據(jù)元素之間客觀存在的關系，與數(shù)邏輯結(jié)構是指數(shù)據(jù)元素之間客觀存在的關系，與數(shù)據(jù)在計算機中如何存儲無關，主要用于人們理解和據(jù)在計算機中如何存儲無關，主要用于人們理解和交流、以及指導算法的設計。交流、以及指導算法的設計。 可歸結(jié)為以下可歸結(jié)為以下四類四類: :線性線性結(jié)構樹形樹形結(jié)構圖形圖形結(jié)構集合集合結(jié)構數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算

48、機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 集合結(jié)構：數(shù)據(jù)元素之間的關系是集合結(jié)構：數(shù)據(jù)元素之間的關系是“屬于同一個屬于同一個集合集合”。集合結(jié)構是數(shù)據(jù)元素關系極為松散的一。集合結(jié)構是數(shù)據(jù)元素關系極為松散的一種結(jié)構。種結(jié)構。 線性結(jié)構：數(shù)據(jù)元素之間存在著一對一的關系，線性結(jié)構：數(shù)據(jù)元素之間存在著一對一的關系，可以用一個線性的序列來表示?？梢杂靡粋€線性的序列來表示。 樹形結(jié)構：數(shù)據(jù)元素之間存在著一對多的關系，樹形結(jié)構：數(shù)據(jù)元素之間存在著一對多的關系，用圓圈表示數(shù)據(jù)元素，連線表示數(shù)據(jù)元素之間的用圓圈表示數(shù)據(jù)元素，連線表示數(shù)據(jù)元素之間的關系。關系。 圖形結(jié)構：數(shù)據(jù)元素之間存在著多對多的關系，圖形

49、結(jié)構：數(shù)據(jù)元素之間存在著多對多的關系，用圓圈表示數(shù)據(jù)元素，連線表示數(shù)據(jù)元素之間的用圓圈表示數(shù)據(jù)元素，連線表示數(shù)據(jù)元素之間的關系。圖形結(jié)構也稱作網(wǎng)狀結(jié)構。關系。圖形結(jié)構也稱作網(wǎng)狀結(jié)構。樹形結(jié)構和圖形結(jié)構統(tǒng)稱為非線性結(jié)構。樹形結(jié)構和圖形結(jié)構統(tǒng)稱為非線性結(jié)構。第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 從不同的角度看問題時，數(shù)據(jù)元素之間可以有不從不同的角度看問題時，數(shù)據(jù)元素之間可以有不同的邏輯結(jié)構。例如，在太陽系中，包含了圍繞同的邏輯結(jié)構。例如，在太陽系中，包含了圍繞太陽運行的行星及其衛(wèi)星、彗星、流星體等星體。太陽運

50、行的行星及其衛(wèi)星、彗星、流星體等星體。如果只考慮太陽系含哪些大行星，則可以用集合結(jié)如果只考慮太陽系含哪些大行星，則可以用集合結(jié)構，太陽系含有八大行星，他們是：地球、火星、構，太陽系含有八大行星，他們是：地球、火星、水星、金星、木星、土星、天王星、海王星；用數(shù)水星、金星、木星、土星、天王星、海王星；用數(shù)據(jù)結(jié)構表示為：據(jù)結(jié)構表示為：太陽系的大行星太陽系的大行星 =（D1，R1，S，O）其中：其中：D1=地球，火星，水星，金星，木星，土地球，火星，水星，金星，木星，土星，天王星，海王星星，天王星，海王星R1=D1； 第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科

51、學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 如果考慮以太陽為首，這些大行星之間的鄰接關如果考慮以太陽為首，這些大行星之間的鄰接關系，則可以用線性結(jié)構表示系，則可以用線性結(jié)構表示。順序依次為：太陽、水星、金星、地球、火星、順序依次為：太陽、水星、金星、地球、火星、木星、土星、天王星、海王星；木星、土星、天王星、海王星；用數(shù)據(jù)結(jié)構表示為：用數(shù)據(jù)結(jié)構表示為：太陽系大行星鄰接關系太陽系大行星鄰接關系=（D2，R2，S，O）其中：其中：D2 =太陽、太陽、D1R2=，第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 如果考慮圍

52、繞旋轉(zhuǎn)關系時，可以用樹形結(jié)構，如果考慮圍繞旋轉(zhuǎn)關系時，可以用樹形結(jié)構，第一層是太陽，第二層是圍繞太陽旋轉(zhuǎn)的八大行第一層是太陽，第二層是圍繞太陽旋轉(zhuǎn)的八大行星，第三層分別是圍繞這些大行星旋轉(zhuǎn)的衛(wèi)星，星，第三層分別是圍繞這些大行星旋轉(zhuǎn)的衛(wèi)星，如繞地球旋轉(zhuǎn)的月球，繞土星旋轉(zhuǎn)的如繞地球旋轉(zhuǎn)的月球，繞土星旋轉(zhuǎn)的60個衛(wèi)星個衛(wèi)星M1，M2，M60，等等。，等等。星球圍繞旋轉(zhuǎn)星球圍繞旋轉(zhuǎn)=（D3，R3，S，O）其中：其中：D3= D2，月球，月球，M1，M2，M60R3=太陽太陽地球地球月球月球，火星，水星，金星，木星，火星，水星，金星，木星，土星，土星 M1，M2，M60，天王星，海王星，天王星，海王星第

53、第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 7.存儲結(jié)構（存儲結(jié)構（Storage Structure）數(shù)據(jù)的存儲結(jié)構也稱物理結(jié)構，指數(shù)據(jù)結(jié)構數(shù)據(jù)的存儲結(jié)構也稱物理結(jié)構，指數(shù)據(jù)結(jié)構在計算機中的存儲表示，包括數(shù)據(jù)結(jié)構中元在計算機中的存儲表示，包括數(shù)據(jù)結(jié)構中元素的表示及元素間關系的表示。素的表示及元素間關系的表示。存儲結(jié)構主要用于指導算法的實現(xiàn)。存儲結(jié)構主要用于指導算法的實現(xiàn)。有三種基本的存儲結(jié)構，即順序存儲結(jié)構、有三種基本的存儲結(jié)構，即順序存儲結(jié)構、鏈式存儲結(jié)構和散列存儲結(jié)構。鏈式存儲結(jié)構和散列存儲結(jié)構。數(shù)據(jù)結(jié)構數(shù)

54、據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 1）順序存儲結(jié)構：順序存儲結(jié)構：把邏輯上相鄰的元素存儲在物把邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元中，特點是借助于數(shù)據(jù)元理位置相鄰的存儲單元中，特點是借助于數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關系。順序存儲結(jié)構是一種最基本的存儲表邏輯關系。順序存儲結(jié)構是一種最基本的存儲表示方法，通常借助于程序設計語言中的數(shù)組來實示方法，通常借助于程序設計語言中的數(shù)組來實現(xiàn)?，F(xiàn)。 2）鏈式存儲結(jié)構：鏈式存儲結(jié)構：在數(shù)據(jù)元素中添加一些地址域在數(shù)據(jù)元素中添加

55、一些地址域或輔助結(jié)構，用于存放數(shù)據(jù)元素之間的關系，特或輔助結(jié)構，用于存放數(shù)據(jù)元素之間的關系，特點是借助于指示數(shù)據(jù)元素地址的指針表示數(shù)據(jù)元點是借助于指示數(shù)據(jù)元素地址的指針表示數(shù)據(jù)元素之間的邏輯關系，這種方法不要求邏輯上相鄰素之間的邏輯關系，這種方法不要求邏輯上相鄰的元素在存儲器中的位置也相鄰，通常借助于程的元素在存儲器中的位置也相鄰，通常借助于程序設計語言中的指針類型或索引結(jié)構來實現(xiàn)。序設計語言中的指針類型或索引結(jié)構來實現(xiàn)。 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 3）散列存儲結(jié)構：散列存儲結(jié)構：也稱哈希（也稱哈希（Hash）結(jié)構

56、）結(jié)構，通過對關鍵字直接計算得到數(shù)據(jù)元素的，通過對關鍵字直接計算得到數(shù)據(jù)元素的存儲位置，特點數(shù)據(jù)元素的存儲和查找都存儲位置，特點數(shù)據(jù)元素的存儲和查找都是通過對關鍵字直接計算得到的。是通過對關鍵字直接計算得到的。 同樣的邏輯結(jié)構可以使用不同的存儲結(jié)構同樣的邏輯結(jié)構可以使用不同的存儲結(jié)構實現(xiàn)。實現(xiàn)。 存儲結(jié)構的選擇主要考慮算法的實現(xiàn)和算存儲結(jié)構的選擇主要考慮算法的實現(xiàn)和算法的時間與空間要求。法的時間與空間要求。 各種基本存儲結(jié)構既可以單獨使用，也可各種基本存儲結(jié)構既可以單獨使用，也可以組合起來使用。以組合起來使用。 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)

57、構與算法數(shù)據(jù)結(jié)構與算法 8. 數(shù)據(jù)結(jié)構的操作數(shù)據(jù)結(jié)構的操作（Operation）數(shù)據(jù)結(jié)構的操作也稱為運算，數(shù)據(jù)結(jié)構的操作也稱為運算，運算的定義是在邏輯結(jié)構上，運算的定義是在邏輯結(jié)構上，而運算的實現(xiàn)是建立在存儲結(jié)構上的。而運算的實現(xiàn)是建立在存儲結(jié)構上的。通常有數(shù)據(jù)結(jié)構的創(chuàng)建和銷毀；通常有數(shù)據(jù)結(jié)構的創(chuàng)建和銷毀；數(shù)據(jù)元素的查找、插入、刪除、遍歷和排序數(shù)據(jù)元素的查找、插入、刪除、遍歷和排序等基本操作。等基本操作。第第1章章 緒論緒論 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 9數(shù)據(jù)類型數(shù)據(jù)類型（Data Type） 數(shù)據(jù)類型數(shù)據(jù)類型: :

58、 是是程序設計語言程序設計語言中用來刻中用來刻劃操作對象的特性的一個劃操作對象的特性的一個值的集合值的集合和定和定義在此集合上的義在此集合上的一組操作一組操作的總稱。的總稱。 不同類型的變量，其所能取的值的不同類型的變量，其所能取的值的范圍和所能進行的操作是不同的。范圍和所能進行的操作是不同的。數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 例如，例如，C 語言中提供的語言中提供的基本數(shù)據(jù)類型基本數(shù)據(jù)類型有有: :短整型短整型 shot浮點型浮點型 float字符型字符型 char邏輯型邏輯型 bool （ C+語言）語言）雙精度型雙精

59、度型 double實型（實型（ C+語言）語言）整型整型整型整型 int長整型長整型 long數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 C 語言中提供的其它數(shù)據(jù)類型有語言中提供的其它數(shù)據(jù)類型有: :數(shù)組類型數(shù)組類型結(jié)構體類型結(jié)構體類型 struct文件類型文件類型 file聯(lián)合體類型聯(lián)合體類型 union結(jié)構類型結(jié)構類型指針類型指針類型 *p空類型空類型 void數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構數(shù)據(jù)類型與數(shù)據(jù)結(jié)構 數(shù)據(jù)類型數(shù)據(jù)類型可以看作是

60、程序設計語言自身實可以看作是程序設計語言自身實現(xiàn)了的現(xiàn)了的數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構。 在實際應用中，根據(jù)應用需要，可以用程在實際應用中，根據(jù)應用需要，可以用程序設計語言提供的已有序設計語言提供的已有數(shù)據(jù)類型數(shù)據(jù)類型來構造更來構造更高級、更有效的高級、更有效的數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構。 數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構UESTC 電子科技大學電子科技大學 計算機科學計算機科學 數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法 10.10.抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型( (Abstract Data Type ，ADT) ) ADT一般包含數(shù)據(jù)元素、數(shù)據(jù)元素之間一般包含數(shù)據(jù)元素、數(shù)據(jù)元素之間關系及操作三要素關系及操作三要素(D, R, O)，其中：，其