筆記轉(zhuǎn)自siki數(shù)據(jù)結(jié)構(gòu)與算法，視頻教程可在泰課在線網(wǎng)上觀看
為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？
同樣的問題，有的人寫出來的程序效率高，有的人卻用很復(fù)雜的方法解決。
學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)能用最有效的方法解決絕大多數(shù)的問題。
《數(shù)據(jù)結(jié)構(gòu)》這門課程的目的有三個(gè)。
- 第一個(gè)是講授常用的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)形成了程序員基本數(shù)據(jù)結(jié)構(gòu)工具箱(toolkit)。對于許多常見的問題，工具箱里的數(shù)據(jù)結(jié)構(gòu)是理想的選擇。就像.NET Framework 中 Windows 應(yīng)用程序開發(fā)中的工具箱，程序員可以直接拿來或經(jīng)過少許的修改就可以使用，非常方便。
- 第二個(gè)是講授常用的算法，這和數(shù)據(jù)結(jié)構(gòu)一樣，是人們在長期實(shí)踐過程中的總結(jié)，程序員可以直接拿來或經(jīng)過少許的修改就可以使用。可以通過算法訓(xùn)練來提高程序設(shè)計(jì)水平。
- 第三個(gè)目的是通過程序設(shè)計(jì)的技能訓(xùn)練促進(jìn)程序員綜合能力的提高。
數(shù)據(jù)結(jié)構(gòu)是程序員的內(nèi)功修煉的一部分
一、基本概念和術(shù)語
1.數(shù)據(jù)(Data)
計(jì)算機(jī)程序處理各種各樣的數(shù)據(jù)，可以是數(shù)值數(shù)據(jù)，如整數(shù)、實(shí)數(shù)或復(fù)數(shù)；也可以是非數(shù)值數(shù)據(jù)，如字符、文字、圖形、圖像、聲音等。
2.數(shù)據(jù)元素(Data Element)和數(shù)據(jù)項(xiàng)(Data Item)
數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常被作為一個(gè)整體進(jìn)行考慮和處理。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)(Data Item)組成。
數(shù)據(jù)項(xiàng)是不可分割的、含有獨(dú)立意義的最小數(shù)據(jù)單位，數(shù)據(jù)項(xiàng)有時(shí)也稱為字段(Field)或域(Domain)。
例如，一條學(xué)生記錄就是一個(gè)數(shù)據(jù)元素。這條記錄中的學(xué)生學(xué)號、姓名、性別、籍貫、出生年月、成績等字段就是數(shù)據(jù)項(xiàng)。數(shù)據(jù)項(xiàng)分為兩種，一種叫做初等項(xiàng)，如學(xué)生的性別、籍貫等，在處理時(shí)不能再進(jìn)行分割；另一種叫做組合項(xiàng)，如學(xué)生的成績，它可以再分為數(shù)學(xué)、物理、化學(xué)等更小的項(xiàng)。
3.數(shù)據(jù)對象(Data Object)
數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合， 是數(shù)據(jù)的一個(gè)子集。例如，整數(shù)數(shù)據(jù)對象是{0,±1,±2,±3,…}，字符數(shù)據(jù)對象是{a,b,c,…}。
4.數(shù)據(jù)類型(Data Type)
數(shù)據(jù)類型是高級程序設(shè)計(jì)語言中的概念，是數(shù)據(jù)的取值范圍和對數(shù)據(jù)進(jìn)行操作的總和。數(shù)據(jù)類型規(guī)定了程序中對象的特性。程序中的每個(gè)變量、常量或表達(dá)式的結(jié)果都應(yīng)該屬于某種確定的數(shù)據(jù)類型。
例如，C#語言中的字符串類型（ String，經(jīng)常寫為 string）。一個(gè) String 表示一個(gè)恒定不變的字符序列集合，所有的字符序列集合構(gòu)成 String 的取值范圍。我們可以對 String 進(jìn)行求長度、復(fù)制、連接兩個(gè)字符串等操作。
二、數(shù)據(jù)結(jié)構(gòu)分類 (Data Structure)
數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。在任何問題中，數(shù)據(jù)元素之間都不是孤立的，而是存在著一定的關(guān)系，這種關(guān)系稱為結(jié)構(gòu)(Structure)。
根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有 4 類基本數(shù)據(jù)結(jié)構(gòu)：
(1) 集合(Set)：如圖(a)所示，該結(jié)構(gòu)中的數(shù)據(jù)元素除了存在“同屬于一個(gè)集合”的關(guān)系外，不存在任何其它關(guān)系。
(2) 線性結(jié)構(gòu)(Linear Structure)：如圖(b)所示，該結(jié)構(gòu)中的數(shù)據(jù)元素存在著一對一的關(guān)系。
(3) 樹形結(jié)構(gòu)(Tree Structure)：如圖(c)所示，該結(jié)構(gòu)中的數(shù)據(jù)元素存在著一對多的關(guān)系。
(4) 圖狀結(jié)構(gòu)(Graphic Structure)：如圖(d)所示，該結(jié)構(gòu)中的數(shù)據(jù)元素存在著多對多的關(guān)系。
什么是算法？
算法可以理解為有基本運(yùn)算及規(guī)定的運(yùn)算順序所構(gòu)成的完整的解題步驟?；蛘呖闯砂凑找笤O(shè)計(jì)好的有限的確切的計(jì)算序列，并且這樣的步驟和序列可以解決一類問題
算法和數(shù)據(jù)結(jié)構(gòu)的關(guān)系
數(shù)據(jù)結(jié)構(gòu)可以認(rèn)為是數(shù)據(jù)在程序中的存儲結(jié)構(gòu)，和基本數(shù)據(jù)操作。
算法可以認(rèn)為是解決問題的，算法是基于數(shù)據(jù)結(jié)構(gòu)的。
數(shù)據(jù)結(jié)構(gòu)是問題的核心，是算法的基礎(chǔ)。
算法的評價(jià)標(biāo)準(zhǔn)
運(yùn)行時(shí)間(Running Time)。
占用空間(Storage Space)。
有時(shí)需要犧牲空間來換取時(shí)間，有時(shí)需要犧牲時(shí)間來換取空間。
其他方面:正確性(Correctness)、可讀性(Readability)、健壯性(Robustness)
