1.0數(shù)據(jù)結(jié)構(gòu)簡介
1、數(shù)據(jù)結(jié)構(gòu)是組織與存儲數(shù)據(jù)鹦肿，數(shù)據(jù)組織的好涣旨，存取速度快烹棉。
2辅髓、數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值計算的數(shù)學(xué)模型，如：學(xué)生信息表、菜單樹、課程關(guān)系圖等之類的有結(jié)構(gòu)的數(shù)據(jù)，將數(shù)據(jù)歸納為某一種類型進(jìn)行相應(yīng)的運算汇歹，完成數(shù)據(jù)處理過程胶果。
1.1數(shù)據(jù)結(jié)構(gòu)的基本概念、術(shù)語分析
1.數(shù)據(jù) （Data）：是一種計算機符號的表示形式。是對客觀信息的符號化描述趟佃，是描述客觀事物的數(shù)值、字符以及能輸入機器且能被處理的各種符號瓶蝴。
2.數(shù)據(jù)元素 （Data Element）：是數(shù)據(jù)的基本單位狡恬。如每一個學(xué)生的記錄就是一個數(shù)據(jù)元素。
3.數(shù)據(jù)項（data item）：數(shù)據(jù)的不可分割的最小單位。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成簿训。例：學(xué)生記錄中的姓名琼了、學(xué)號等盏档。
4.數(shù)據(jù)類型：在一種程序設(shè)計語言中勺拣，變量所具有的數(shù)據(jù)種類。整型商模、浮點型忿晕、字符型等等
5.邏輯結(jié)構(gòu)：數(shù)據(jù)之間的相互關(guān)系。
6.數(shù)據(jù)對象（data object）：性質(zhì)相同的數(shù)據(jù)元素的集合确丢，是數(shù)據(jù)的一個子集崎苗，如大寫字母字符數(shù)據(jù)對象是集合C = {‘A’,’B’,’C’,……，’Z’}育谬，整數(shù)數(shù)據(jù)對象是 集合{0,±1,±2, … }互站。
7.數(shù)據(jù)結(jié)構(gòu)（data structure）：是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合自脯。數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)油额。
8.數(shù)據(jù)類型（Data Type）：數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作顷歌。
基本數(shù)據(jù)類型的每一個數(shù)據(jù)元素都是單一的無法再分割的整體锰蓬。構(gòu)造數(shù)據(jù)類型可以由不同成分的內(nèi)置數(shù)據(jù)類型或子結(jié)構(gòu)類型按照一定的規(guī)則組成灼狰。
數(shù)據(jù)類型中定義了兩個集合：
1.數(shù)據(jù)取值范圍
2.數(shù)據(jù)允許使用的一組運算浮禾。
9.抽象數(shù)據(jù)類型ADT：抽象的本質(zhì)就是抽取反映問題本質(zhì)的東西蝴簇，忽略非本質(zhì)的細(xì)節(jié)互拾。另外嫉晶，抽象數(shù)據(jù)類型把使用與實現(xiàn)分離，實現(xiàn)封裝與信息隱蔽剪况。一般的翎蹈，抽象數(shù)據(jù)類型由用戶定義淮菠，是用于表示應(yīng)用問題的數(shù)據(jù)模型。
抽象數(shù)據(jù)類型=數(shù)據(jù)結(jié)構(gòu)+操作
=數(shù)據(jù)對象+數(shù)據(jù)關(guān)系+操作
10.數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是存在關(guān)系的數(shù)據(jù)元素集荤堪，其中“關(guān)系”是描述數(shù)據(jù)元素之間的邏輯關(guān)系合陵，稱為邏輯結(jié)構(gòu)。
11.物理結(jié)構(gòu)：數(shù)據(jù)的物理結(jié)構(gòu)又稱為數(shù)據(jù)的存儲結(jié)構(gòu)澄阳，是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的映像拥知，即數(shù)據(jù)結(jié)構(gòu)在計算機中的存儲。
數(shù)據(jù)結(jié)構(gòu)（邏輯結(jié)構(gòu)） =數(shù)據(jù)集合+數(shù)據(jù)關(guān)系
物理結(jié)構(gòu)（存儲結(jié)構(gòu)） =數(shù)據(jù)映像+關(guān)系映像
12.順序存儲結(jié)構(gòu)的特點是借助元素在連續(xù)空間的存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系碎赢。
13.非順序映像是借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系低剔。
數(shù)據(jù)結(jié)構(gòu)據(jù)關(guān)系劃分有四種
1.集合 ：結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系揩抡。
2.線性結(jié)構(gòu) ：數(shù)據(jù)元素之間一對一的關(guān)系
3.樹形結(jié)構(gòu)： 數(shù)據(jù)元素之間一對多的關(guān)系
4.圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) ：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系
數(shù)據(jù)結(jié)構(gòu)的形式定義：
Data-Structure = (D,S)
D：數(shù)據(jù)元素的有限集户侥；
S：D上關(guān)系的有限集。
例：在計算機科學(xué)中峦嗤，復(fù)數(shù)可取如下定義：
復(fù)數(shù)是一種數(shù)據(jù)結(jié)構(gòu)
Complex=（C蕊唐，R）
其中，C是含兩個實數(shù)集合{c1烁设，c2}替梨；R={P}钓试，P是定義在集合C上的一種關(guān)系{<c1，c2>}副瀑，其中有序偶<c1弓熏，c2>表示c1是復(fù)數(shù)的實部，c2是復(fù)數(shù)的虛部糠睡。
ADT定義格式:
ADT＜ADT名＞
{ 數(shù)據(jù)對象：＜數(shù)據(jù)對象的定義＞
結(jié)構(gòu)關(guān)系挽鞠；＜結(jié)構(gòu)關(guān)系的定義＞
基本操作：＜基本操作的定義＞
}ADT＜ADT名＞
數(shù)據(jù)對象和結(jié)構(gòu)關(guān)系的定義采用數(shù)學(xué)符號和自然語言描述。
基本操作的定義格式為C語言基本函數(shù)
基本操作按函數(shù)的定義形式：
函數(shù)類型 函數(shù)名（[參數(shù)列表]）
[類型定義列表]
{
函數(shù)體
}
鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點
⑴ 結(jié)點中除存放數(shù)據(jù)元素+指針狈孔。
⑵ 要存取第i個結(jié)點的信息信认，必須從第1個結(jié)點開始查找，存取速度較慢均抽。
⑶ 鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點是插入嫁赏、刪除元素時不必移動其他元素。
⑷ 鏈?zhǔn)酱鎯κ且环N動態(tài)存儲結(jié)構(gòu)油挥，申請空間潦蝇，釋放空間方便，也不用預(yù)分配空間深寥。
順序存儲結(jié)構(gòu)的特點
（1）邏輯相鄰的數(shù)據(jù)物理也相鄰攘乒，順序存儲結(jié)構(gòu)是指邏輯上相鄰的數(shù)據(jù)元素，其結(jié)點的物理位置也相鄰
（2）順序表的存儲空間需要預(yù)先分配翩迈。
如何選擇存儲結(jié)構(gòu)：
1）順序存儲結(jié)構(gòu)利于隨機存取元素持灰，鏈?zhǔn)街荒茼樞虼嫒 ?br>
2）主要操作速度；執(zhí)行的主要操作是插入负饲、刪除堤魁，則最好用鏈?zhǔn)酱鎯Y(jié)構(gòu)，否則應(yīng)該用順序存儲結(jié)構(gòu)返十；
3）若預(yù)先可以估計出元素的個數(shù)妥泉，則可以采用順序存儲結(jié)構(gòu)，否則宜用鏈?zhǔn)酱鎯Y(jié)構(gòu)洞坑。
