數(shù)據(jù)結(jié)構(gòu)基本概念
1.定義
數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中的操作對象，以及他們之間的關(guān)系和操作等相關(guān)問題的學(xué)科。
- 程序設(shè)計(jì) = 數(shù)據(jù)機(jī)構(gòu) + 算法
數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或者多種特定關(guān)系的數(shù)據(jù)元素的集合。
2.數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)項(xiàng)，數(shù)據(jù)對象的關(guān)系
- 數(shù)據(jù)是描述客觀事物的符號，是計(jì)算機(jī)中可以操作的對象，是能被計(jì)算機(jī)識別，并輸入給計(jì)算機(jī)處理的符號集合。
- 數(shù)據(jù)元素是組成數(shù)據(jù)的、有一定意義的基本單位，在計(jì)算機(jī)通常作為整體處理，也被成為記錄。
- 數(shù)據(jù)項(xiàng)是數(shù)據(jù)元素的組成部分或?qū)傩?，?shù)據(jù)項(xiàng)是不可分割的最小單位。
- 數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。
人類中的數(shù)據(jù)對象為人；眼睛，耳朵是人的數(shù)據(jù)項(xiàng)；人又是具有姓名、生日等相同數(shù)據(jù)項(xiàng)的數(shù)據(jù)對象；張三，李四是數(shù)據(jù)對象中的數(shù)據(jù)元素。
3.數(shù)據(jù)結(jié)構(gòu)分類
3.1.邏輯結(jié)構(gòu)
是指數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關(guān)系。
- 集合結(jié)構(gòu)
- 同屬于一個集合
- 線性結(jié)構(gòu)
- 元素之間是一對一關(guān)系
- 樹形結(jié)構(gòu)
- 元素之間是一對多關(guān)系
- 圖形結(jié)構(gòu)
- 元素之間是多對多關(guān)系
3.2.物理結(jié)構(gòu)
是指邏輯解耦股在計(jì)算機(jī)中的存儲形式。
-
順序存儲結(jié)構(gòu)
- 地址連續(xù)
-
鏈?zhǔn)酱鎯Y(jié)構(gòu)
- 元素存放在任意的存儲單元里，地址可能是不連續(xù)的
4.數(shù)據(jù)類型
是指一組性質(zhì)相同的值得集合以及定義在此集合上的一些操作的總稱。
- 原子類型：不可以再分解的基本類型，包括整型、實(shí)型、字符型等。
- 結(jié)構(gòu)類型：有若干類型組合而成，是可以再分解的。
4.1.抽象
抽象是指抽取出事物具有的普遍性的本質(zhì)。
4.2.抽象數(shù)據(jù)類型
抽象數(shù)據(jù)類型（Abstract Data Type，ADT）：是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。
抽象的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。
抽象數(shù)據(jù)類型體現(xiàn)了程序設(shè)計(jì)中問題分解、抽象和信息隱藏的特性。
ADT 抽象數(shù)據(jù)類型名
Data
數(shù)據(jù)元素之間邏輯關(guān)系的定義
Operation
操作1
初始條件
操作結(jié)果描述
操作2
...
操作n
...
endADT
