數(shù)據(jù)結(jié)構(gòu) + 算法 = 程序
1. 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容
如何合理的組織數(shù)據(jù)，高效的處理數(shù)據(jù)株婴，主要研究非數(shù)值計(jì)算問(wèn)題怎虫，非數(shù)值計(jì)算問(wèn)題無(wú)法用數(shù)學(xué)方程建立數(shù)學(xué)模型暑认。
好的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更快的運(yùn)行或是存儲(chǔ)效率。
2. 概念和術(shù)語(yǔ)
概念：
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)大审、組織數(shù)據(jù)的方式蘸际，是由相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合和集合中數(shù)據(jù)元素之間的關(guān)系組成(元素和元素之間的關(guān)系)；
是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合徒扶。
數(shù)據(jù)之間的關(guān)系稱為結(jié)構(gòu)粮彤。
中文名|英文名
---|---|--|
數(shù)據(jù)|Data|指能輸入到計(jì)算機(jī)并且被計(jì)算機(jī)程序處理的符號(hào)的總稱。
數(shù)據(jù)元素|Data Element|數(shù)據(jù)的基本單位姜骡，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮或處理导坟。
數(shù)據(jù)項(xiàng)|Data Item|一個(gè)數(shù)據(jù)元素可以有若干個(gè)數(shù)據(jù)項(xiàng)組成。
數(shù)據(jù)對(duì)象|Data Object|性質(zhì)相同的數(shù)據(jù)元素的集合圈澈，是數(shù)據(jù)的一個(gè)子集惫周。
3. 數(shù)據(jù)結(jié)構(gòu)包含的內(nèi)容
- 數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)之間的邏輯關(guān)系，算法的設(shè)計(jì)就需要依賴于邏輯結(jié)構(gòu)士败。
- 數(shù)據(jù)的物理結(jié)構(gòu)：數(shù)據(jù)在計(jì)算機(jī)中的表示闯两，即存儲(chǔ)結(jié)構(gòu)褥伴，算法的實(shí)現(xiàn)需要依賴于物理結(jié)構(gòu)谅将。
- 數(shù)據(jù)的運(yùn)算結(jié)構(gòu)：暫時(shí)不討論
文章所描述的數(shù)據(jù)結(jié)構(gòu)：包括邏輯結(jié)構(gòu)和物理結(jié)構(gòu)兩個(gè)層次；
1. 邏輯結(jié)構(gòu)：
從邏輯關(guān)系上描述數(shù)據(jù)重慢，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)饥臂，是獨(dú)立于計(jì)算機(jī)的，可看做是從具體問(wèn)題中抽象出來(lái)的數(shù)學(xué)模型似踱。
它有兩大要素：數(shù)據(jù)元素和關(guān)系隅熙；
四類基本邏輯結(jié)構(gòu)：
根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，分為四類基本結(jié)構(gòu)：
| 結(jié)構(gòu)名稱 | 特點(diǎn) |
|---|---|
| 集合結(jié)構(gòu) | 屬于同一結(jié)合別無(wú)其他關(guān)系核芽； |
| 線性結(jié)構(gòu) | 數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系囚戚； |
| 樹(shù)結(jié)構(gòu) | 元素之間存在一對(duì)多的關(guān)系； |
| 圖結(jié)構(gòu) | 元素之間存在多對(duì)多的關(guān)系轧简； |
數(shù)據(jù)邏輯結(jié)構(gòu)：分為線性和非線性結(jié)構(gòu)
2. 物理結(jié)構(gòu)
數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)驰坊，也叫物理結(jié)構(gòu)；
存儲(chǔ)數(shù)據(jù)時(shí)既要存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)哮独，又要存儲(chǔ)數(shù)據(jù)元素之間的邏輯關(guān)系拳芙；
數(shù)據(jù)元素在計(jì)算機(jī)中有兩種基本的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)皮璧；
| 名稱 | 特點(diǎn) |
|---|---|
| 順序存儲(chǔ)結(jié)構(gòu) | 借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系舟扎；要求所有元素依次存放在一片連續(xù)的存儲(chǔ)空間中； 一般借用程序設(shè)計(jì)語(yǔ)言中的數(shù)組類型表示悴务； |
| 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) | 借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系睹限，無(wú)需占用一整塊連續(xù)的存儲(chǔ)空間，但為了表示節(jié)點(diǎn)之間的關(guān)系，需要給每一個(gè)節(jié)點(diǎn)添加附加指針字段羡疗，用于存放后續(xù)元素的存儲(chǔ)地址删窒； 一般借助程序設(shè)計(jì)語(yǔ)言中的指針類型表示； |
任何一個(gè)算法的設(shè)計(jì)取決于選定的數(shù)據(jù)邏輯結(jié)構(gòu)顺囊，而算法的實(shí)現(xiàn)依賴于采用的存儲(chǔ)結(jié)構(gòu)
3.數(shù)據(jù)類型
按值的不同特性肌索，高級(jí)程序語(yǔ)言中的數(shù)據(jù)結(jié)構(gòu)可分為兩類：
1.非結(jié)構(gòu)的原子類：原子類型的值是不可分解的。
2.結(jié)構(gòu)類型：如自定義的數(shù)據(jù)類型特碳。
4.抽象數(shù)據(jù)類型 （abstract data type）ADT
指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作诚亚。由一個(gè)值域和定義在該值域上的一組操作組成。
按其值得不同特性分為下列3類：
1.原子類型 atomic data type：該類型的變量的值是不可分解的午乓。
2.固定聚合類型 fixed-aggregate data type:該類型的變量站宗，其值由確定數(shù)目的成分按某種結(jié)構(gòu)組成。
3.可變聚合類型 variable-aggregate data type:該類型的值的成分的數(shù)目是不確定的益愈。
4. 程序
算法+數(shù)據(jù)結(jié)構(gòu) = 程序
1.算法和算法分析性
算法：Algorithm是為解決某類問(wèn)題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列梢灭。
算法必須滿足的5個(gè)特性：
| 編號(hào) | 名稱 | 解釋 |
|---|---|---|
| 1 | 有窮性 | 一個(gè)算法必須總是在執(zhí)行又窮步后結(jié) 束，且每一步都必須在有窮的時(shí)間內(nèi)完成蒸其。 |
| 2 | 確定性 | 對(duì)于每一種情況所應(yīng)執(zhí)行的操作敏释，在算 法中都有確切的規(guī)定，不會(huì)產(chǎn)生二義性摸袁，是算法的執(zhí)行者或閱讀者都能明確其含義以及如何執(zhí)行 |
| 3 | 可行性 | 算法中的所有操作都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)钥顽。 |
| 4 | 輸入 | 0個(gè)或多個(gè)輸入。 |
| 5 | 輸出 | 1個(gè)或多個(gè)輸出靠汁。 |
算法設(shè)計(jì)的要求：
| 編號(hào) | 名稱 | 說(shuō)明 |
|---|---|---|
| 1 | 正確性 | 算法能正確反映需求 |
| 2 | 可讀性 | 易于閱讀 |
| 3 | 健壯性 | 當(dāng)輸入非法數(shù)據(jù)時(shí)蜂大，能正確的做出反映 |
2. 算法的評(píng)價(jià)標(biāo)準(zhǔn)：
| 名稱 | 說(shuō)明 |
|---|---|
| 正確性 | 在合理 的輸入下，能夠在有限的運(yùn)行時(shí)間內(nèi)得到正確的結(jié)果蝶怔。 |
| 可讀性 | 便于人們理解和交流奶浦。 |
| 健壯性 | 輸入非法數(shù)據(jù)時(shí)，能適當(dāng)?shù)淖龀稣_的反應(yīng)或進(jìn)行相應(yīng)的處理踢星。 |
| 高效性 | 時(shí)間和空間兩個(gè)方面澳叉，時(shí)間方面指算法設(shè)計(jì)合理，執(zhí)行效率高斩狱，可用時(shí)間復(fù)雜度來(lái)度量耳高，空間方面指算法占用存儲(chǔ)容量合理，空間復(fù)雜度衡量所踊。 |
3. 數(shù)據(jù)結(jié)構(gòu)中的堆棧：
在數(shù)據(jù)結(jié)構(gòu)中泌枪，堆棧是：堆 和棧兩種數(shù)據(jù)結(jié)構(gòu)；
堆：是完全二叉樹(shù)秕岛，堆中各元素是有序的碌燕。在這個(gè)二叉樹(shù)中所有的雙親節(jié)點(diǎn)和孩子節(jié)點(diǎn)存在著大小關(guān)系误证，如所有的雙親節(jié)點(diǎn)都大于孩子節(jié)點(diǎn)則 為大頭堆，如果所有的雙親節(jié)點(diǎn)都小于其孩子節(jié)點(diǎn)說(shuō)明這是一個(gè)小頭堆修壕，建堆的過(guò)程就是一個(gè)排序的過(guò)程愈捅，堆得查詢效率也很高。
棧：是一種先進(jìn)后出的線性表慈鸠。
