数据结构课件.pptx

數據結構

——C++語言描述1

第1章緒論數據結構在程式設計中的作用本課程討論的主要內容數據結構的基本概念演算法及演算法分析本章的基本內容是：

1938年出生，25歲畢業於加州理工學院數學系，博士畢業後留校任教，28歲任副教授。30歲時，加盟斯坦福大學電腦系，任教授。從31歲起，開始出版他的歷史性經典巨著：TheArtofComputerProgramming，他計畫共寫7卷，然而出版三卷之後，已震驚世界，使他獲得電腦科學界的最高榮譽——圖靈獎，此時，他年僅36歲。數據結構的創始人——克努思

1.1數據結構在程式設計中的作用程式設計的實質是什麼?數據表示：將數據存儲在電腦（記憶體）中數據處理：處理數據，設計方案（演算法）數據結構問題起源於程式設計

1.1數據結構在程式設計中的作用利用電腦求解問題的一般過程?電腦不能分析問題並產生問題的解決方案，必須由人來分析問題，確定問題的解決方案，編寫程式，然後讓電腦執行程式最終獲得問題的解。

1.1數據結構在程式設計中的作用例1-1手機電話號碼查詢問題將電話號碼集合組織成線性結構和樹結構，查找操作的效率不同，當數據量較大時差別就更大。

1.2本課程討論的主要內容電腦求解問題:問題→抽象出問題的模型→求模型的解問題——數值問題、非數值問題數值問題→數學方程非數值問題→數據結構

例1-2學籍管理問題完成什麼功能?各表項之間是什麼關係？1.2本課程討論的主要內容

例1-3人——機對弈問題如何實現對弈?各格局之間是什麼關係？1.2本課程討論的主要內容

例1-4七巧板塗色問題如何表示區域之間的鄰接關係？1.2本課程討論的主要內容

本課程討論非數值問題的數據組織和處理，主要內容如下：（1）數據的邏輯結構：線性表、樹、圖等數據結構，其核心是如何組織待處理的數據以及數據之間的關係；（2）數據的存儲結構：如何將線性表、樹、圖等數據結構存儲到電腦的記憶體中，其核心是如何有效地存儲數據以及數據之間的邏輯關係；（3）演算法：如何基於數據的某種存儲結構實現插入、刪除、查找等基本操作，其核心是如何有效地處理數據；（4）常用數據處理技術：查找技術、排序技術、索引技術等。1.2本課程討論的主要內容

1.3數據結構的基本概念數據：所有能輸入到電腦中並能被電腦程式識別和處理的符號集合。數值數據：整數、實數等非數值數據：圖形、圖象、聲音、文字等數據元素：數據的基本單位，在電腦程式中通常作為一個整體進行考慮和處理。資料項目：構成數據元素的不可分割的最小單位。數據結構的基本概念學號姓名性別出生日期政治面貌0001陸宇男1986/09/02團員0002李明男1985/12/25黨員0003湯曉影女1986/03/26團員資料項目數據元素

數據、數據元素、資料項目之間的關係包含關係：數據由數據元素組成，數據元素由資料項目組成。數據元素是討論數據結構時涉及的最小數據單位，其中的資料項目一般不予考慮。1.3數據結構的基本概念數據結構數據元素關係

數據結構：相互之間存在一定關係的數據元素的集合。按照視點的不同，數據結構分為邏輯結構和存儲結構。邏輯結構：指數據元素之間邏輯關係的整體。1.3數據結構的基本概念數據結構的基本概念關聯方式或鄰接關係數據的邏輯結構是從具體問題抽象出來的數據模型學籍管理問題中，表項之間的邏輯關係指的是什麼？人機對弈問題中，格局之間的邏輯關係指的是什麼？教學計畫編排問題中，課程之間的邏輯關係指的是什麼？

數據結構：相互之間存在一定關係的數據元素的集合。按照視點的不同，數據結構分為邏輯結構和存儲結構。邏輯結構：指數據元素之間邏輯關係的整體。1.3數據結構的基本概念數據結構的基本概念數據的邏輯結構在形式上可定義為一個二元組：Data_Structure=(D,R)其中D是數據元素的有限集合，R是D上關係的集合。

數據結構：相互之間存在一定關係的數據元素的集合。按照視點的不同，數據結構分為邏輯結構和存儲結構。邏輯結構：指數據元素之間邏輯關係的整體。1.3數據結構的基本概念數據結構的基本概念Data_Structure=(D,R)其中D={A,B,C,D,E,F,G}R={R1}，R1={A,B,A,E,A,F,B,C,B,D,C,D,D,E,D,G,E,F,E,G}

數據結構：相互之間存在一定關係的數據元素的集合。按照視點的不同，數據結構分為邏輯結構和存儲結構。邏輯結構：指數據元素之間邏輯關係的整體。存儲結構：又稱為物理結構，是數據及其邏輯結構在電腦中的表示。1