數(shù)據(jù)結構基礎數(shù)學知識點(數(shù)據(jù)結構涉及到哪些數(shù)學知識)

1.數(shù)據(jù)結構涉及到哪些數(shù)學知識

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

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

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

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

2.數(shù)據(jù)結構知識歸納

第一章：數(shù)據(jù)結構概述一、什么是數(shù)據(jù)結構1、作者開篇談到： 一般來說解決一個具體的問題時，大致需要經過下列幾個步驟：首先要從具體的問題抽象出一個適當?shù)臄?shù)學模型，然后設計一個解此數(shù)學模型的算法，最后編寫出程序代碼，進行測試、調整直至得到最終的解決方案。

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

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

線性表是最常用并且最簡單的一種數(shù)據(jù)結構，簡單來說，一個線性表是n個數(shù)據(jù)元素的有限序列。至于每個數(shù)據(jù)元素的具體含義，在不同的情況下各不相同，既可以是一個數(shù)也可以是一個符號等等。

二、線性表的操作 線性表是一個相當靈活的數(shù)據(jù)結構，它的長度可根據(jù)需要增長或者縮短，即對線性表的數(shù)據(jù)元素不但可以進行訪問，還可以進行插入和刪除等操作。線性表存儲方式有兩種，順序存儲和鏈式存儲，下面通過代碼進行簡單模擬操作。

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

棧的存儲方式有兩種，一種是順序棧另外一種是鏈式棧，下面只通過代碼簡單模擬棧的操作。二、棧的應用 棧的應用主要有數(shù)制轉換、括號匹配的檢驗、迷宮問題求解以及表達式求值。

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

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

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

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

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

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

關鍵詞組：有限集、唯一性、對稱性、遞歸性。 基本術語：結點、度、葉子、分支結點、孩子、雙親、兄弟、層次以及深度等。

基本操作：構造初始化樹、取得左子樹或右子樹、插入結點、刪除結點、樹的遍歷等等。2、線性結構VS樹結構 線性結構是一個“序列”，元素之間存在的是“一對一”的關系，而樹是一個層次結構，元素之間存在的是“一對多”的關系。

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

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

3.學習數(shù)據(jù)結構需要哪些數(shù)學知識

學習數(shù)據(jù)結構我個人認為如果將來只側重于實用，不做很深研究的話，只要掌握高中的所有數(shù)學知識就行。

強調一下，雖然只需要掌握高中的數(shù)學知識，但是，你必須學的精。高考必須可以考135以上。

最早的計算機模型就是由數(shù)學家提出的，所以這個標準不知道你是否覺得苛刻了點。如果這個層次都達不到。

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

這樣對你的提高有百利而無一害。（這里談一點我的心得）。

4.數(shù)據(jù)結構的基礎知識

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

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

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

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

（圖1） (2)線性結構：數(shù)據(jù)元素間存在一對一的關系。（圖2） (3)樹形結構：結構中的元素間的關系是一對多的關系。

（圖3） (4)圖（網）狀結構：結構中的元素間的關系是多對多的關系。（圖4） 1.2 數(shù)據(jù)的邏輯結構和物理結構邏輯結構：數(shù)據(jù)元素之間存在的關系（邏輯關系）叫數(shù)據(jù)的邏輯結構。

物理結構：數(shù)據(jù)結構在計算機中的表示（映象）叫數(shù)據(jù)的物理結構。 一種邏輯結構可映象成不同的存儲結構：順序存儲結構和非順序存儲結構（鏈式存儲結構和散列結構）。

5.數(shù)據(jù)結構的基礎知識

第一章 什么是數(shù)據(jù)結構

1.1 基本概念和術語

1.2 數(shù)據(jù)的邏輯結構和物理結構

1.1 基本概念和術語

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

是對客觀事物的符號的表示，是所有能輸入到計算機中并被計算機程序處理的符號的總稱。

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

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

3.數(shù)據(jù)結構（data structure）:

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

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

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

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

(2)線性結構：數(shù)據(jù)元素間存在一對一的關系。（圖2）

(3)樹形結構：結構中的元素間的關系是一對多的關系。（圖3）

(4)圖（網）狀結構：結構中的元素間的關系是多對多的關系。（圖4）

1.2 數(shù)據(jù)的邏輯結構和物理結構

邏輯結構：數(shù)據(jù)元素之間存在的關系（邏輯關系）叫數(shù)據(jù)的邏輯結構。

物理結構：數(shù)據(jù)結構在計算機中的表示（映象）叫數(shù)據(jù)的物理結構。

一種邏輯結構可映象成不同的存儲結構：順序存儲結構和非順序存儲結構（鏈式存儲結構和散列結構）。

6.求數(shù)據(jù)結構的復習資料

數(shù)據(jù)結構在計算機科學界至今沒有標準的定義。

個人根據(jù)各自的理解的不同而有不同的表述方法： Sartaj Sahni在他的《數(shù)據(jù)結構、算法與應用》一書中稱：“數(shù)據(jù)結構是數(shù)據(jù)對象，以及存在于該對象的實例和組成實 例的數(shù)據(jù)元素之間的各種聯(lián)系。這些聯(lián)系可以通過定義相關的函數(shù)來給出。”

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

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

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

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

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

許多時候，確定了數(shù)據(jù)結構后，算法就容易得到了。有些時候事情也會反過來，我們根據(jù)特定算法來選擇數(shù)據(jù)結構與之適應。

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

這種洞見導致了許多種軟件設計方法和程序設計語言的出現(xiàn)，面向對象的程序設計語言就是其中之一。編輯本段研究內容 在計算機科學中，數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象（數(shù)據(jù)元素）以及它們之間的關系和運算等的學科，而且確保經過這些運算后所得到的新結構仍然是原來的結構類型。

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

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

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

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

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

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

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

尋求數(shù)學模型的實質是分析問題，從中提取操作的對象，并找出這些操作對象之間含有的關系，然后用數(shù)學的語言加以描述。計算機算法與數(shù)據(jù)的結構密切相關，算法無不依附于具體的數(shù)據(jù)結構，數(shù)據(jù)結構直接關系到算法的選擇和效率。

運算是由計算機來完成，這就要設計相應的插入、刪除和修改的算法 。也就是說，數(shù)據(jù)結構還需要給出每種結構類型所定義的各種運算的算法。

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

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

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

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

若能。

7.數(shù)據(jù)結構的重點

棧和隊列：基礎章節(jié)，容易出基本概念題，必考內容之一。

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

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

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

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

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

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

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

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

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

大家主要注意以下幾點：數(shù)據(jù)結構的基本概念，時間和空間復雜度的概念及度量方法，算法設計時的注意事項。本章考點不多，只要稍加注意理解即可。

第一章 線性表 作為線性結構的開篇章節(jié)，線性表一章在線性結構的學習乃至整個數(shù)據(jù)結構學科的學習中，其作用都是不可低估的。在這一章，第一次系統(tǒng)性地引入鏈式存儲的概念，鏈式存儲概念將是整個數(shù)據(jù)結構學科的重中之重，無論哪一章都涉及到了這個概念。

總體來說，線性表一章可供考查的重要考點有以下幾個方面： 1.線性表的相關基本概念，如：前驅、后繼、表長、空表、首元結點，頭結點，頭指針等概念。 2.線性表的結構特點，主要是指：除第一及最后一個元素外，每個結點都只有一個前趨和只有一個后繼。

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

4.線性表的鏈式存儲方式及以下幾種常用鏈表的特點和運算：單鏈表、循環(huán)鏈表，雙向鏈表，雙向循環(huán)鏈表。其中，單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都是較為常見的考查方式。

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

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

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

所以，理解棧與隊列，是走向DS高手的一條必由之路，。 學習此章前，你可以問一下自己是不是已經知道了以下幾點： 1.棧、隊列的定義及其相關數(shù)據(jù)結構的概念，包括：順序棧，鏈棧，共享棧，循環(huán)隊列，鏈隊等。

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

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