數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)數(shù)學(xué)知識(shí)點(diǎn)(數(shù)據(jù)結(jié)構(gòu)涉及到哪些數(shù)學(xué)知識(shí))

1.數(shù)據(jù)結(jié)構(gòu)涉及到哪些數(shù)學(xué)知識(shí)

好！ 我告訴你。 我畢業(yè)兩年了，都是做c/c++開發(fā)方面的~

首先說(shuō)一下數(shù)據(jù)結(jié)構(gòu)和vc/mfc以及數(shù)據(jù)結(jié)構(gòu)的應(yīng)用，vc/mfc主要是開發(fā)上位機(jī)軟件，即pc機(jī)上的軟件的。一般情況下做vc一般開發(fā)不需要掌握太多的數(shù)據(jù)結(jié)構(gòu)知識(shí)。開發(fā)中不會(huì)用太多，了解就夠了。數(shù)據(jù)結(jié)構(gòu)一般常用在嵌入式開發(fā)，譬如路由器開發(fā)里常用到樹結(jié)構(gòu)。

第二數(shù)據(jù)結(jié)構(gòu)和數(shù)學(xué)，數(shù)據(jù)結(jié)構(gòu)里用的最多的是離散數(shù)學(xué)，尤其是樹和圖，基本就是離散數(shù)學(xué)的知識(shí)，其次是線性代數(shù)里的矩陣也用的比較多。所以學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)也不一定要把所有的數(shù)學(xué)都學(xué)好。不過(guò)要想學(xué)得好必須先學(xué)好我指的那幾點(diǎn)。否則學(xué)起來(lái)比較吃力。

第三c++、數(shù)據(jù)結(jié)構(gòu)、vc++。的順序問(wèn)題，數(shù)據(jù)結(jié)構(gòu)是不分語(yǔ)種的，但你要想學(xué)c++版的數(shù)據(jù)結(jié)構(gòu)，你首先得了解c++的一般語(yǔ)法吧，至少得看懂偽代碼，常用的c++結(jié)構(gòu)，指針、類的使用等。要知道c++是計(jì)算機(jī)語(yǔ)言、vc是開發(fā)工具、數(shù)據(jù)結(jié)構(gòu)是程序的思路，數(shù)學(xué)是基礎(chǔ)。好了，不啰嗦了，相信你都已經(jīng)明白了

2.數(shù)據(jù)結(jié)構(gòu)知識(shí)歸納

第一章：數(shù)據(jù)結(jié)構(gòu)概述一、什么是數(shù)據(jù)結(jié)構(gòu)1、作者開篇談到： 一般來(lái)說(shuō)解決一個(gè)具體的問(wèn)題時(shí)，大致需要經(jīng)過(guò)下列幾個(gè)步驟：首先要從具體的問(wèn)題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，最后編寫出程序代碼，進(jìn)行測(cè)試、調(diào)整直至得到最終的解決方案。

總結(jié)為：現(xiàn)實(shí)中具體的問(wèn)題—>數(shù)學(xué)模型—>算法程序—>解決方案動(dòng)作為：抽象提取、設(shè)計(jì)編碼、測(cè)試調(diào)整2、數(shù)學(xué)角度闡述： 尋求數(shù)學(xué)模型的實(shí)質(zhì)是分析問(wèn)題，從中提取操作的對(duì)象，并找出這些操作對(duì)象之間含有的關(guān)系，然后用數(shù)學(xué)的語(yǔ)言加以描述。3、定義數(shù)據(jù)結(jié)構(gòu)： 描述這類非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)，因此，簡(jiǎn)單來(lái)說(shuō)，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間關(guān)系和操作等的學(xué)科，用一句話來(lái)說(shuō)就是，數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

研究對(duì)象：1、集合2、線性結(jié)構(gòu)3、樹形結(jié)構(gòu)4、圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)） 結(jié)構(gòu)分類：1、數(shù)據(jù)的邏輯結(jié)構(gòu)2、數(shù)據(jù)的物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)） 關(guān)系表示：1、順序映像2、非順序映像，兩者分別對(duì)應(yīng)為順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二、算法和算法分析 1、算法的五個(gè)特性：有窮性、確定性、可行性、輸入和輸出 2、算法設(shè)計(jì)的要求：正確性、可讀性、健壯性以及效率與低存儲(chǔ)量需求 3、算法的度量：時(shí)間復(fù)雜度和空間復(fù)雜度 總結(jié)：編寫代碼設(shè)計(jì)算法時(shí)候首先先考慮算法的正確性，確保程序能夠滿足要求，在正確性的前提下再進(jìn)一步考慮算法的可讀性、健壯性、拓展性以及算法的效率等。第二章：線性表一、線性表的定義 線性結(jié)構(gòu)的特點(diǎn)是：在數(shù)據(jù)元素的非空有限集中（1）存在唯一的一個(gè)被稱做“第一個(gè)”的數(shù)據(jù)元素；（2）存在唯一的一個(gè)被稱做“最后一個(gè)”的數(shù)據(jù)元素；（3）除第一個(gè)之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)；（4）除最后一個(gè)元素之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。

線性表是最常用并且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)單來(lái)說(shuō)，一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列。至于每個(gè)數(shù)據(jù)元素的具體含義，在不同的情況下各不相同，既可以是一個(gè)數(shù)也可以是一個(gè)符號(hào)等等。

二、線性表的操作 線性表是一個(gè)相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，它的長(zhǎng)度可根據(jù)需要增長(zhǎng)或者縮短，即對(duì)線性表的數(shù)據(jù)元素不但可以進(jìn)行訪問(wèn)，還可以進(jìn)行插入和刪除等操作。線性表存儲(chǔ)方式有兩種，順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，下面通過(guò)代碼進(jìn)行簡(jiǎn)單模擬操作。

第三章：棧和隊(duì)列 棧和隊(duì)列是兩種重要的線性結(jié)構(gòu)，從數(shù)據(jù)結(jié)構(gòu)的角度看，棧和隊(duì)列也是線性表，其特殊性在于棧和隊(duì)列的基本操作是線性表操作的子集，它們是操作受限制的線性表，因此可以稱為限定性的數(shù)據(jù)結(jié)構(gòu)。一、棧的定義 棧是限定在表尾進(jìn)行插入或刪除操作的線性表，棧的特定是先進(jìn)后出。

棧的存儲(chǔ)方式有兩種，一種是順序棧另外一種是鏈?zhǔn)綏?，下面只通過(guò)代碼簡(jiǎn)單模擬棧的操作。二、棧的應(yīng)用 棧的應(yīng)用主要有數(shù)制轉(zhuǎn)換、括號(hào)匹配的檢驗(yàn)、迷宮問(wèn)題求解以及表達(dá)式求值。

另外棧遞歸實(shí)現(xiàn)的經(jīng)典例子有八皇后問(wèn)題、漢諾塔問(wèn)題等。三、隊(duì)列的定義 隊(duì)列和棧有點(diǎn)不同，隊(duì)列是一種先進(jìn)先出得線性表，它只能夠在表的一端進(jìn)行插入另外一頭進(jìn)行刪除操作。

隊(duì)列在程序設(shè)計(jì)中比較常見的例子是操作系統(tǒng)中的作業(yè)排隊(duì)。雙端隊(duì)列、循環(huán)隊(duì)列有時(shí)間再進(jìn)一步演進(jìn)，暫時(shí)先了解些基本概念。

第四章：串一、串的定義 計(jì)算機(jī)上的非數(shù)值處理的對(duì)象基本上都是字符串?dāng)?shù)據(jù)。串是由零個(gè)或多個(gè)字符組成的有限序列。

串中字符的數(shù)目成為字符串的長(zhǎng)度，零個(gè)字符的串成為空串。串的模式匹配算法經(jīng)典的是KMP算法。

第五章：數(shù)組和廣義表一、數(shù)組和廣義表定義 數(shù)組是讀者已經(jīng)很熟悉的一種數(shù)據(jù)類型，幾乎所有的程序設(shè)計(jì)語(yǔ)言都把數(shù)組類型設(shè)為固有的類型。數(shù)組的應(yīng)用中涉及到一個(gè)比較重要的數(shù)學(xué)知識(shí)，矩陣的壓縮存儲(chǔ)問(wèn)題。

廣義表是線性表的推廣，在java開發(fā)中好像用得不多，有時(shí)間再進(jìn)一步學(xué)習(xí)。 第六章：樹和二叉樹一、樹的定義和基本操作1、樹的特點(diǎn) 樹是一個(gè)結(jié)點(diǎn)n的有限集，在任意一顆樹非空樹中：1、有且只有一個(gè)根結(jié)點(diǎn)，2、當(dāng)n>1時(shí)，其余結(jié)點(diǎn)分為m(m>0)個(gè)互不相交的有限集，其中每個(gè)集合本身又是一棵樹，叫做根的子樹。

關(guān)鍵詞組：有限集、唯一性、對(duì)稱性、遞歸性。 基本術(shù)語(yǔ)：結(jié)點(diǎn)、度、葉子、分支結(jié)點(diǎn)、孩子、雙親、兄弟、層次以及深度等。

基本操作：構(gòu)造初始化樹、取得左子樹或右子樹、插入結(jié)點(diǎn)、刪除結(jié)點(diǎn)、樹的遍歷等等。2、線性結(jié)構(gòu)VS樹結(jié)構(gòu) 線性結(jié)構(gòu)是一個(gè)“序列”，元素之間存在的是“一對(duì)一”的關(guān)系，而樹是一個(gè)層次結(jié)構(gòu)，元素之間存在的是“一對(duì)多”的關(guān)系。

二、二叉樹的定義1、二叉樹的特點(diǎn) 每個(gè)結(jié)點(diǎn)至多只有二棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)），并且二叉樹的子樹有左右之分，其次序不能顛倒。 關(guān)鍵詞組：對(duì)稱、次序2、二叉樹的具體實(shí)例 滿二叉樹、完全二叉樹、平衡二叉樹等，具體區(qū)別參考書籍教材詳解。

3、二叉樹的存儲(chǔ)結(jié)構(gòu) 主要分為兩種方式，一類是順序結(jié)構(gòu)（可使用一組地址連續(xù)的存儲(chǔ)單元依次自上而下、自左至右存儲(chǔ)完全二叉樹上的結(jié)點(diǎn)元。

3.學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)需要哪些數(shù)學(xué)知識(shí)

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)我個(gè)人認(rèn)為如果將來(lái)只側(cè)重于實(shí)用，不做很深研究的話，只要掌握高中的所有數(shù)學(xué)知識(shí)就行。

強(qiáng)調(diào)一下，雖然只需要掌握高中的數(shù)學(xué)知識(shí)，但是，你必須學(xué)的精。高考必須可以考135以上。

最早的計(jì)算機(jī)模型就是由數(shù)學(xué)家提出的，所以這個(gè)標(biāo)準(zhǔn)不知道你是否覺得苛刻了點(diǎn)。如果這個(gè)層次都達(dá)不到。

那么你是不可能學(xué)精通的。當(dāng)然，由于數(shù)學(xué)與計(jì)算機(jī)之間有著千絲萬(wàn)屢的聯(lián)系，所以我還是希望你能把大學(xué)的數(shù)學(xué)知識(shí)都學(xué)好，例如離散數(shù)學(xué)，線性代數(shù)——。

這樣對(duì)你的提高有百利而無(wú)一害。（這里談一點(diǎn)我的心得）。

4.數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識(shí)

第一章 什么是數(shù)據(jù)結(jié)構(gòu)1.1 基本概念和術(shù)語(yǔ)1.2 數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu) 1.1 基本概念和術(shù)語(yǔ)1.數(shù)據(jù)（data）： 是對(duì)客觀事物的符號(hào)的表示，是所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。

2.數(shù)據(jù)元素（data element）： 是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體來(lái)處理。一個(gè)數(shù)據(jù)元素由多個(gè) 數(shù)據(jù)項(xiàng)（data item）組成，數(shù)據(jù) 項(xiàng)是數(shù)據(jù)不可分割的最小單位。

3.數(shù)據(jù)結(jié)構(gòu)（data structure）： 是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組，記為： data_structure=(D,S).其中D為數(shù)據(jù)元素的集合，S是D上關(guān)系的集合。

數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)（structure）。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常由下列四類基本結(jié)構(gòu)： （1）集合：數(shù)據(jù)元素間的關(guān)系是同屬一個(gè)集合。

（圖1） (2)線性結(jié)構(gòu)：數(shù)據(jù)元素間存在一對(duì)一的關(guān)系。（圖2） (3)樹形結(jié)構(gòu)：結(jié)構(gòu)中的元素間的關(guān)系是一對(duì)多的關(guān)系。

（圖3） (4)圖（網(wǎng)）狀結(jié)構(gòu)：結(jié)構(gòu)中的元素間的關(guān)系是多對(duì)多的關(guān)系。（圖4） 1.2 數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間存在的關(guān)系（邏輯關(guān)系）叫數(shù)據(jù)的邏輯結(jié)構(gòu)。

物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（映象）叫數(shù)據(jù)的物理結(jié)構(gòu)。 一種邏輯結(jié)構(gòu)可映象成不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和非順序存儲(chǔ)結(jié)構(gòu)（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和散列結(jié)構(gòu)）。

5.數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識(shí)

第一章 什么是數(shù)據(jù)結(jié)構(gòu)

1.1 基本概念和術(shù)語(yǔ)

1.2 數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

1.1 基本概念和術(shù)語(yǔ)

1.數(shù)據(jù)（data）:

是對(duì)客觀事物的符號(hào)的表示，是所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。

2.數(shù)據(jù)元素（data element）:

是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體來(lái)處理。一個(gè)數(shù)據(jù)元素由多個(gè) 數(shù)據(jù)項(xiàng)（data item）組成，數(shù)據(jù) 項(xiàng)是數(shù)據(jù)不可分割的最小單位。

3.數(shù)據(jù)結(jié)構(gòu)（data structure）:

是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組，記為：

data_structure=(D,S).其中D為數(shù)據(jù)元素的集合，S是D上關(guān)系的集合。

數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)（structure）。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常由下列四類基本結(jié)構(gòu)：

(1)集合：數(shù)據(jù)元素間的關(guān)系是同屬一個(gè)集合。（圖1）

(2)線性結(jié)構(gòu)：數(shù)據(jù)元素間存在一對(duì)一的關(guān)系。（圖2）

(3)樹形結(jié)構(gòu)：結(jié)構(gòu)中的元素間的關(guān)系是一對(duì)多的關(guān)系。（圖3）

(4)圖（網(wǎng)）狀結(jié)構(gòu)：結(jié)構(gòu)中的元素間的關(guān)系是多對(duì)多的關(guān)系。（圖4）

1.2 數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間存在的關(guān)系（邏輯關(guān)系）叫數(shù)據(jù)的邏輯結(jié)構(gòu)。

物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（映象）叫數(shù)據(jù)的物理結(jié)構(gòu)。

一種邏輯結(jié)構(gòu)可映象成不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和非順序存儲(chǔ)結(jié)構(gòu)（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和散列結(jié)構(gòu)）。

6.求數(shù)據(jù)結(jié)構(gòu)的復(fù)習(xí)資料

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)界至今沒有標(biāo)準(zhǔn)的定義。

個(gè)人根據(jù)各自的理解的不同而有不同的表述方法： Sartaj Sahni在他的《數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用》一書中稱：“數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對(duì)象，以及存在于該對(duì)象的實(shí)例和組成實(shí) 例的數(shù)據(jù)元素之間的各種聯(lián)系。這些聯(lián)系可以通過(guò)定義相關(guān)的函數(shù)來(lái)給出?！?/p>

他將數(shù)據(jù)對(duì)象（data object）定義為“一個(gè)數(shù)據(jù)對(duì)象是實(shí)例或值的集合”。 Clifford A.Shaffer在《數(shù)據(jù)結(jié)構(gòu)與算法分析》一書中的定義是：“數(shù)據(jù)結(jié)構(gòu)是 ADT（抽象數(shù)據(jù)類型Abstract Data Type） 的物理實(shí)現(xiàn)?！?/p>

Lobert L.Kruse在《數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)》一書中，將一個(gè)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)過(guò)程分成抽象層、數(shù)據(jù)結(jié)構(gòu)層和實(shí)現(xiàn)層。其中，抽象層是指抽象數(shù)據(jù)類型層，它討論數(shù)據(jù)的邏輯結(jié)構(gòu)及其運(yùn)算，數(shù)據(jù)結(jié)構(gòu)層和實(shí)現(xiàn)層討論一個(gè)數(shù)據(jù)結(jié)構(gòu)的表示和在計(jì)算機(jī)內(nèi)的存儲(chǔ)細(xì)節(jié)以及運(yùn)算的實(shí)現(xiàn)。

數(shù)據(jù)結(jié)構(gòu)具體指同一類數(shù)據(jù)元素中，各元素之間的相互關(guān)系，包括三個(gè)組成成分，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)運(yùn)算結(jié)構(gòu)。編輯本段重要意義 一般認(rèn)為，一個(gè)數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來(lái)的。

對(duì)數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)必須在計(jì)算機(jī)內(nèi)存儲(chǔ)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)形式，是其在計(jì)算機(jī)內(nèi)的表示；此外討論一個(gè)數(shù)據(jù)結(jié)構(gòu)必須同時(shí)討論在該類數(shù)據(jù)上執(zhí)行的運(yùn)算才有意義。一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率。

在許多類型的程序的設(shè)計(jì)中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個(gè)基本的設(shè)計(jì)考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗(yàn)表明，系統(tǒng)實(shí)現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴(yán)重的依賴于是否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。

許多時(shí)候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時(shí)候事情也會(huì)反過(guò)來(lái)，我們根據(jù)特定算法來(lái)選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。

不論哪種情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。 選擇了數(shù)據(jù)結(jié)構(gòu)，算法也隨之確定，是數(shù)據(jù)而不是算法是系統(tǒng)構(gòu)造的關(guān)鍵因素。

這種洞見導(dǎo)致了許多種軟件設(shè)計(jì)方法和程序設(shè)計(jì)語(yǔ)言的出現(xiàn)，面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言就是其中之一。編輯本段研究?jī)?nèi)容 在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象（數(shù)據(jù)元素）以及它們之間的關(guān)系和運(yùn)算等的學(xué)科，而且確保經(jīng)過(guò)這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來(lái)的結(jié)構(gòu)類型。

“數(shù)據(jù)結(jié)構(gòu)”作為一門獨(dú)立的課程在國(guó)外是從1968年才開始設(shè)立的。 1968年美國(guó)唐·歐·克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作的著作。

“數(shù)據(jù)結(jié)構(gòu)”在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。

數(shù)據(jù)結(jié)構(gòu)這一門課的內(nèi)容不僅是一般程序設(shè)計(jì)（特別是非數(shù)值性程序設(shè)計(jì)）的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ)。 計(jì)算機(jī)是一門研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。

這里面涉及到兩個(gè)問(wèn)題：信息的表示，信息的處理 。 而信息的表示和組織又直接關(guān)系到處理信息的程序的效率。

隨著計(jì)算機(jī)的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，為了編寫出一個(gè)“好”的程序，必須分析待處理的對(duì)象的特征及各對(duì)象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問(wèn)題。

眾所周知，計(jì)算機(jī)的程序是對(duì)信息進(jìn)行加工處理。在大多數(shù)情況下，這些信息并不是沒有組織，信息（數(shù)據(jù)）之間往往具有重要的結(jié)構(gòu)關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。

數(shù)據(jù)的結(jié)構(gòu)，直接影響算法的選擇和效率。 計(jì)算機(jī)解決一個(gè)具體問(wèn)題時(shí)，大致需要經(jīng)過(guò)下列幾個(gè)步驟：首先要從具體問(wèn)題中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法（Algorithm），最后編出程序、進(jìn)行測(cè)試、調(diào)整直至得到最終解答。

尋求數(shù)學(xué)模型的實(shí)質(zhì)是分析問(wèn)題，從中提取操作的對(duì)象，并找出這些操作對(duì)象之間含有的關(guān)系，然后用數(shù)學(xué)的語(yǔ)言加以描述。計(jì)算機(jī)算法與數(shù)據(jù)的結(jié)構(gòu)密切相關(guān)，算法無(wú)不依附于具體的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)直接關(guān)系到算法的選擇和效率。

運(yùn)算是由計(jì)算機(jī)來(lái)完成，這就要設(shè)計(jì)相應(yīng)的插入、刪除和修改的算法 。也就是說(shuō)，數(shù)據(jù)結(jié)構(gòu)還需要給出每種結(jié)構(gòu)類型所定義的各種運(yùn)算的算法。

數(shù)據(jù)是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并由計(jì)算機(jī)程序處理的符號(hào)的總稱。 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體考慮。

一個(gè)數(shù)據(jù)元素由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。

有兩類數(shù)據(jù)元素：一類是不可分割的原子型數(shù)據(jù)元素，如：整數(shù)"5"，字符 "N" 等；另一類是由多個(gè)款項(xiàng)構(gòu)成的數(shù)據(jù)元素，其中每個(gè)款項(xiàng)被稱為一個(gè)數(shù)據(jù)項(xiàng)。例如描述一個(gè)學(xué)生的信息的數(shù)據(jù)元素可由下列6個(gè)數(shù)據(jù)項(xiàng)組成。

其中的出生日期又可以由三個(gè)數(shù)據(jù)項(xiàng)："年"、"月"和"日"組成，則稱"出生日期"為組合項(xiàng)，而其它不可分割的數(shù)據(jù)項(xiàng)為原子項(xiàng)。 關(guān)鍵字指的是能識(shí)別一個(gè)或多個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。

若能。

7.數(shù)據(jù)結(jié)構(gòu)的重點(diǎn)

棧和隊(duì)列：基礎(chǔ)章節(jié)，容易出基本概念題，必考內(nèi)容之一。

而棧常與其它章節(jié)配合考查，也常與遞歸等概念相聯(lián)系進(jìn)行考查。 串 ：基礎(chǔ)章節(jié)，概念較為簡(jiǎn)單。

專門針對(duì)于此章的大型算法設(shè)計(jì)題很少，較常見的是根據(jù)KMP進(jìn)行算法分析。 多維數(shù)組及廣義表 ：基礎(chǔ)章節(jié)，基于數(shù)組的算法題也是常見的，分?jǐn)?shù)比例波動(dòng)較大，是出題的“可選單元”或“侯補(bǔ)單元”。

一般如果要出題，多數(shù)不會(huì)作為大題出。數(shù)組常與“查找，排序”等章節(jié)結(jié)合來(lái)作為大題考查。

樹和二叉樹 ：重點(diǎn)難點(diǎn)章節(jié)，各校必考章節(jié)。各校在此章出題的不同之處在于，是否在本章中出一到兩道大的算法設(shè)計(jì)題。

通過(guò)對(duì)多所學(xué)校的試卷分析，絕大多數(shù)學(xué)校在本章都曾有過(guò)出大型算法設(shè)計(jì)題的歷史。 圖 ：重點(diǎn)難點(diǎn)章節(jié)，名校尤愛考。

如果作為重點(diǎn)來(lái)考，則多出現(xiàn)于分析與設(shè)計(jì)題型當(dāng)中，可與樹一章共同構(gòu)成算法設(shè)計(jì)大題的題型設(shè)計(jì)。 查找 ：重點(diǎn)難點(diǎn)章節(jié)，概念較多，聯(lián)系較為緊密，容易混淆。

出題時(shí)可以作為分析型題目給出，在基本概念型題目中也較為常見。算法設(shè)計(jì)型題中可以數(shù)組結(jié)合來(lái)考查，也可以與樹一章結(jié)合來(lái)考查。

排序 ：與查找一章類似，本章同屬于重點(diǎn)難點(diǎn)章節(jié)，且概念更多，聯(lián)系更為緊密，概念之間更容易混淆。在基本概念的考查中，尤愛考各種排序算法的優(yōu)劣比較此類的題。

算法設(shè)計(jì)大題中，如果作為出題，那么常與數(shù)組結(jié)合來(lái)考查。 二、數(shù)據(jù)結(jié)構(gòu)各章節(jié)重點(diǎn)勾劃： 第0章 概述 本章主要起到總領(lǐng)作用，為讀者進(jìn)行數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)進(jìn)行了一些先期鋪墊。

大家主要注意以下幾點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的基本概念，時(shí)間和空間復(fù)雜度的概念及度量方法，算法設(shè)計(jì)時(shí)的注意事項(xiàng)。本章考點(diǎn)不多，只要稍加注意理解即可。

第一章 線性表 作為線性結(jié)構(gòu)的開篇章節(jié)，線性表一章在線性結(jié)構(gòu)的學(xué)習(xí)乃至整個(gè)數(shù)據(jù)結(jié)構(gòu)學(xué)科的學(xué)習(xí)中，其作用都是不可低估的。在這一章，第一次系統(tǒng)性地引入鏈?zhǔn)酱鎯?chǔ)的概念，鏈?zhǔn)酱鎯?chǔ)概念將是整個(gè)數(shù)據(jù)結(jié)構(gòu)學(xué)科的重中之重，無(wú)論哪一章都涉及到了這個(gè)概念。

總體來(lái)說(shuō)，線性表一章可供考查的重要考點(diǎn)有以下幾個(gè)方面： 1.線性表的相關(guān)基本概念，如：前驅(qū)、后繼、表長(zhǎng)、空表、首元結(jié)點(diǎn)，頭結(jié)點(diǎn)，頭指針等概念。 2.線性表的結(jié)構(gòu)特點(diǎn)，主要是指：除第一及最后一個(gè)元素外，每個(gè)結(jié)點(diǎn)都只有一個(gè)前趨和只有一個(gè)后繼。

3.線性表的順序存儲(chǔ)方式及其在具體語(yǔ)言環(huán)境下的兩種不同實(shí)現(xiàn)：表空間的靜態(tài)分配和動(dòng)態(tài)分配。靜態(tài)鏈表與順序表的相似及不同之處。

4.線性表的鏈?zhǔn)酱鎯?chǔ)方式及以下幾種常用鏈表的特點(diǎn)和運(yùn)算：?jiǎn)捂湵怼⒀h(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表。其中，單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都是較為常見的考查方式。

此外，近年來(lái)在不少學(xué)校中還多次出現(xiàn)要求用遞歸算法實(shí)現(xiàn)單鏈表輸出（可能是順序也可能是倒序）的問(wèn)題。 在鏈表的小題型中，經(jīng)?？嫉揭恍┲T如：判表空的題。

在不同的鏈表中，其判表空的方式是不一樣的，請(qǐng)大家注意。 5.線性表的順序存儲(chǔ)及鏈?zhǔn)酱鎯?chǔ)情況下，其不同的優(yōu)缺點(diǎn)比較，即其各自適用的場(chǎng)合。

單鏈表中設(shè)置頭指針、循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針以及索引存儲(chǔ)結(jié)構(gòu)的各自好處。 棧與隊(duì)列，是很多學(xué)習(xí)DS的同學(xué)遇到第一只攔路虎，很多人從這一章開始坐暈車，一直暈到現(xiàn)在。

所以，理解棧與隊(duì)列，是走向DS高手的一條必由之路，。 學(xué)習(xí)此章前，你可以問(wèn)一下自己是不是已經(jīng)知道了以下幾點(diǎn)： 1.棧、隊(duì)列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念，包括：順序棧，鏈棧，共享?xiàng)?，循環(huán)隊(duì)列，鏈隊(duì)等。

棧與隊(duì)列存取數(shù)據(jù)（請(qǐng)注意包括：存和取兩部分）的特點(diǎn)。 2.遞歸算法。

棧與遞歸的關(guān)系，以及借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法：n！階乘問(wèn)題，fib數(shù)列問(wèn)題，hanoi問(wèn)題，背包問(wèn)題，二叉樹的遞歸和非遞歸遍歷問(wèn)題，圖的深度遍歷與棧的關(guān)系等。其中，涉及到樹與圖的問(wèn)題，多半會(huì)在樹與圖的相關(guān)章節(jié)中進(jìn)行考查。