數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式，是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合；它研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)以及它們之間的相互關(guān)系，并對這種結(jié)構(gòu)定義相適應(yīng)的運算，設(shè)計出相應(yīng)的算法，并確保經(jīng)過這些運算以后所得到的新結(jié)構(gòu)仍保持原來的結(jié)構(gòu)類型。

php零基礎(chǔ)到就業(yè)直播視頻課：進入學(xué)習(xí)
程序員必備接口測試調(diào)試工具：立即使用

本教程操作環(huán)境：windows7系統(tǒng)、Dell G3電腦。

數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運行或者存儲效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。

名詞定義

數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關(guān)系組成。記為：
Data_Structure=(D,R)
其中D是數(shù)據(jù)元素的集合，R是該集合中所有元素之間的關(guān)系的有限集合。

（一）常用結(jié)構(gòu)

1.數(shù)組:在程序設(shè)計中，為了處理方便， 把具有相同類型的若干變量按有序的形式組織起來。這些按序排列的同類數(shù)據(jù)元素的集合稱為數(shù)組。在C語言中， 數(shù)組屬于構(gòu)造數(shù)據(jù)類型。一個數(shù)組可以分解為多個數(shù)組元素，這些數(shù)組元素可以是基本數(shù)據(jù)類型或是構(gòu)造類型。因此按數(shù)組元素的類型不同，數(shù)組又可分為數(shù)值數(shù)組、字符數(shù)組、指針數(shù)組、結(jié)構(gòu)數(shù)組等各種類別。

2.棧: 是只能在某一端插入和刪除的特殊線性表。它按照先進后出的原則存儲數(shù)據(jù)，先進入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）。

3.隊列: 一種特殊的線性表，它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列是按照“先進先出”或“后進后出”的原則組織數(shù)據(jù)的。隊列中沒有元素時，稱為空隊列。

4.鏈表:是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，它既可以表示線性結(jié)構(gòu)，也可以用于表示非線性結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點（鏈表中每一個元素稱為結(jié)點）組成，結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域。

5.樹: 是包含n（n>0）個結(jié)點的有窮集合K，且在K中定義了一個關(guān)系N，N滿足 以下條件：

（1）有且僅有一個結(jié)點 K0，他對于關(guān)系N來說沒有前驅(qū)，稱K0為樹的根結(jié)點。簡稱為根（root）?！?

（2）除K0外，K中的每個結(jié)點，對于關(guān)系N來說有且僅有一個前驅(qū)。

（3）K中各結(jié)點，對關(guān)系N來說可以有m個后繼（m>=0）。

6.圖: 是由結(jié)點的有窮集合V和邊的集合E組成。其中，為了與樹形結(jié)構(gòu)加以區(qū)別，在圖結(jié)構(gòu)中常常將結(jié)點稱為頂點，邊是頂點的有序偶對，若兩個頂點之間存在一條邊，就表示這兩個頂點具有相鄰關(guān)系。

7.堆:在計算機科學(xué)中，堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，每個結(jié)點都有一個值。通常我們所說的堆的數(shù)據(jù)結(jié)構(gòu)，是指二叉堆。堆的特點是根結(jié)點的值最?。ɑ蜃畲螅?，且根結(jié)點的兩個子樹也是一個堆。

8.散列表（Hash table，也叫哈希表）: 若結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄，則必定在f(K)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應(yīng)關(guān)系f為散列函數(shù)(Hash function)，按這個思想建立的表為散列表。

9.八大排序算法： 排序算法可以分為內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。

1.數(shù)據(jù)的邏輯結(jié)構(gòu)：指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，其中的邏輯關(guān)系是指數(shù)據(jù)元素之間的前后件關(guān)系，而與他們在計算機中的存儲位置無關(guān)。

邏輯結(jié)構(gòu)包括：

1）集合
數(shù)據(jù)結(jié)構(gòu)中的元素之間除了“同屬一個集合” 的相互關(guān)系外，別無其他關(guān)系；

2）線性結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)中的元素存在一對一的相互關(guān)系；

3）樹形結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)中的元素存在一對多的相互關(guān)系；

4）圖形結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)中的元素存在多對多的相互關(guān)系。

2.數(shù)據(jù)的物理結(jié)構(gòu)：指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間的存放形式。
數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（又稱映像），它包括數(shù)據(jù)元素的機內(nèi)表示和關(guān)系的機內(nèi)表示。由于具體實現(xiàn)的方法有順序、鏈接、索引、散列等多種，所以，一種數(shù)據(jù)結(jié)構(gòu)可表示成一種或多種存儲結(jié)構(gòu)。
數(shù)據(jù)元素的機內(nèi)表示（映像方法）： 用二進制位（bit）的位串表示數(shù)據(jù)元素。通常稱這種位串為節(jié)點（node）。當(dāng)數(shù)據(jù)元素有若干個數(shù)據(jù)項組成時，位串中與個數(shù)據(jù)項對應(yīng)的子位串稱為數(shù)據(jù)域（data field）。因此，節(jié)點是數(shù)據(jù)元素的機內(nèi)表示（或機內(nèi)映像）。關(guān)系的機內(nèi)表示（映像方法）：數(shù)據(jù)元素之間的關(guān)系的機內(nèi)表示可以分為順序映像和非順序映像，常用兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。順序映像借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序映像借助指示元素存儲位置的指針（pointer）來表示數(shù)據(jù)元素之間的邏輯關(guān)系。

3.數(shù)據(jù)結(jié)構(gòu)的運算

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

在許多類型的程序的設(shè)計中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個基本的設(shè)計考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗表明，系統(tǒng)實現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴重的依賴于是否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時候事情也會反過來，我們根據(jù)特定算法來選擇數(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è)計方法和程序設(shè)計語言的出現(xiàn)，面向?qū)ο蟮某绦蛟O(shè)計語言就是其中之一。
計算機解決一個具體問題時，大致需要經(jīng)過下列幾個步驟：首先要從具體問題中抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計一個解此數(shù)學(xué)模型的算法（Algorithm），最后編出程序、進行測試、調(diào)整直至得到最終解答。
尋求數(shù)學(xué)模型的實質(zhì)是分析問題，從中提取操作的對象，并找出這些操作對象之間含有的關(guān)系，然后用數(shù)學(xué)的語言加以描述。當(dāng)人們用計算機處理數(shù)值計算問題是，所用的數(shù)學(xué)模型是用數(shù)學(xué)方程描述。所涉及的運算對象一般是簡單的整形、實型和邏輯型數(shù)據(jù)，因此程序設(shè)計者的主要精力集中于程序設(shè)計技巧上，而不是數(shù)據(jù)的存儲和組織上。然而，計算機應(yīng)用的