🏡作者主頁：點擊！

🤖數(shù)據結構專欄：點擊！

??創(chuàng)作時間：2024年12月12日01點09分

緒論

• 數(shù)據是信息的載體，描述客觀事物屬性的數(shù)、字符及所有能輸入到計算機并被計算機程序識別和處理的符號的集合。
• 數(shù)據是計算機程序加工的原料
• 數(shù)據元素是數(shù)據的基本單位，通常作為一個整體進行考慮和處理
• 一個數(shù)據元素可由數(shù)據項組成，數(shù)據項是構成數(shù)據元素的不可分割的最小單位
• 數(shù)據對象是具有相同性質的數(shù)據元素的集合，是數(shù)據的一個子集
• 數(shù)據結構是相互之間存在一種或多種特定關系的數(shù)據元素的集合

數(shù)據結構三要素

邏輯結構

• 集合結構：各個元素同屬一個集合，別無其他關系
• 線性結構：數(shù)據元素之間是一對一的關系，除第一個元素，所有元素都有唯一前驅；除最后一個元素，所有元素都有唯一后繼
• 樹形結構：數(shù)據元素之間的一對多的關系
• 圖狀結構：數(shù)據元素之間是多對多的關系

數(shù)據的運算

針對某種邏輯結構，結合實際需求，定義基本運算

結合邏輯結構、實際需求來定義基本運算

物理結構(存儲結構)

如何在計算機表示出數(shù)據元素的邏輯關系

? 數(shù)據的存儲結構：

1. 順序存儲：邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元中，元素之間的關系由存儲單元的鄰接關系來體現(xiàn)

   順序存儲要求各個數(shù)據元素之間按順序存放

2. 鏈式存儲：邏輯上相鄰的元素存儲在物理位置上可以不相鄰，借助指示元素存儲地址的指針來表示元素之間的邏輯關系

3. 索引存儲：存儲元素信息的同時，還建立附加的索引表。索引表中的每項稱為索引項，索引項的一般形式是關鍵字、地址

4. 散列存儲：根據元素的關鍵字直接計算出該元素的存儲地址，又稱哈希存儲

   2、3、4 非順序存儲

運算的定義是針對邏輯結構的，指出運算的功能

運算的實現(xiàn)是針對存儲結構的，指出運算的具體操作內容

數(shù)據類型

數(shù)據類型是一個值的集合和定義在此集合上的一組操作的總稱

數(shù)據類型分為原子類型和結構類型

• 原子類型：值不可再分的數(shù)據類型
• 結構類型：值可以再分解為若干成分的數(shù)據類型

抽象數(shù)據類型是抽象數(shù)據組織及與之相關的操作

算法

程序 = 數(shù)據結構 + 算法

算法：對特定問題求解步驟的一種描述，指令的有限序列，每條指令表示一個或多個操作求解問題的步驟

算法的特性

• 有窮性：一個算法必須總在執(zhí)行有窮步之后結束，每一步都可在有窮時間內完成

  算法是有窮的，程序可以是無窮的

• 確定性：算法中每條指令必須有確切的含義，對于相同的輸入只能得出相同的輸出

• 可行性：算法中描述的操作都可以通過已經實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)

  輸入：算法有零個或多個輸入，輸入取自于某個特定的對象的集合

  輸出：算法有一個或多個輸出，輸出是與輸入有著某種特定關系的量

好算法的特性

• 正確性：算法應能夠正確的解決求解問題
• 可讀性：算法應具有良好的可讀性，幫助人們理解
• 健狀性：輸入非法數(shù)據時，算法能適當?shù)刈龀龇磻蜻M行處理，而不會產生莫名其妙的輸出結果
• 高效率與底存儲量需求（時間復雜度低，空間復雜度低）