著名的瑞士科學家Niklaus Wirth教授提出：數據結構+算法＝程序。數據結構是程序的骨架，算法是程序的靈魂。
1.1 數據結構基礎知識
學習數據結構首先從認識以下幾個概念開始。
1．數據
數據是指所有能輸入到計算機中的描述客觀事物的符號，包括文本、聲音、圖像、符號等。我們經常使用的“掃一掃”的二維碼，也是數據。
2．數據元素
數據元素是數據的基本單位，也稱節點或記錄，如圖1-1所示。
著名的瑞士科學家Niklaus Wirth教授提出：數據結構+算法＝程序。數據結構是程序的骨架，算法是程序的靈魂。
1.1 數據結構基礎知識
學習數據結構首先從認識以下幾個概念開始。
1．數據
數據是指所有能輸入到計算機中的描述客觀事物的符號，包括文本、聲音、圖像、符號等。我們經常使用的“掃一掃”的二維碼，也是數據。
2．數據元素
數據元素是數據的基本單位，也稱節點或記錄，如圖1-1所示。
圖1-1 數據元素
3．數據項
數據項表示有獨立含義的數據最小單位，也稱域。若干個數據項構成一個數據元素，數據項是不可分割的最小單位，如圖1-1所示的“86”。
4．數據對象
數據對象是指相同特性的數據元素的集合，是數據的一個子集。
5．數據結構
數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。
數據結構是帶“結構”的數據元素的集合，“結構”是指數據元素之間存在的關係。數據結構研究的問題是將帶有關係的數據存儲在計算機中，並進行相關操作。數據結構包含邏輯結構、存儲結構和運算三個要素。
6．邏輯結構和存儲結構
邏輯結構是數據元素之間的關係，存儲結構是數據元素及其關係在計算機中的存儲方式。例如，小明和小勇是表兄弟，這是他們之間的邏輯關係；他們在教室裡面的位置是他們的存儲結構。無論他們的座位怎樣安排，是挨著坐，還是分開坐，都不影響他們的表兄弟關係。
邏輯結構：數據元素間抽象化的相互關係，與數據的存儲無關，獨立於計算機，它是從具體問題中抽象出來的數學模型。
數據結構的邏輯結構共有以下4種。
（1）集合——數據元素間除“同屬於一個集合”外，無其他關係。
集合中的元素是離散、無序的，就像雞圈中的小雞一樣，可以隨意走動，它們之間沒有什麼關係，唯一的親密關係就是在同一個雞圈裡，如圖1-2所示。數據結構重點研究的是數據之間的關係，而集合中的元素是離散的，沒有什麼關係。因此，集合雖然是一種數據結構，但在數據結構書中不講，在離散數學的集合論部分有重點講述。
著名的瑞士科學家Niklaus Wirth教授提出：數據結構+算法＝程序。數據結構是程序的骨架，算法是程序的靈魂。
1.1 數據結構基礎知識
學習數據結構首先從認識以下幾個概念開始。
1．數據
數據是指所有能輸入到計算機中的描述客觀事物的符號，包括文本、聲音、圖像、符號等。我們經常使用的“掃一掃”的二維碼，也是數據。
2．數據元素
數據元素是數據的基本單位，也稱節點或記錄，如圖1-1所示。
圖1-1 數據元素
3．數據項
數據項表示有獨立含義的數據最小單位，也稱域。若干個數據項構成一個數據元素，數據項是不可分割的最小單位，如圖1-1所示的“86”。
4．數據對象
數據對象是指相同特性的數據元素的集合，是數據的一個子集。
5．數據結構
數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。
數據結構是帶“結構”的數據元素的集合，“結構”是指數據元素之間存在的關係。數據結構研究的問題是將帶有關係的數據存儲在計算機中，並進行相關操作。數據結構包含邏輯結構、存儲結構和運算三個要素。
6．邏輯結構和存儲結構
邏輯結構是數據元素之間的關係，存儲結構是數據元素及其關係在計算機中的存儲方式。例如，小明和小勇是表兄弟，這是他們之間的邏輯關係；他們在教室裡面的位置是他們的存儲結構。無論他們的座位怎樣安排，是挨著坐，還是分開坐，都不影響他們的表兄弟關係。
邏輯結構：數據元素間抽象化的相互關係，與數據的存儲無關，獨立於計算機，它是從具體問題中抽象出來的數學模型。
數據結構的邏輯結構共有以下4種。
（1）集合——數據元素間除“同屬於一個集合”外，無其他關係。
集合中的元素是離散、無序的，就像雞圈中的小雞一樣，可以隨意走動，它們之間沒有什麼關係，唯一的親密關係就是在同一個雞圈裡，如圖1-2所示。數據結構重點研究的是數據之間的關係，而集合中的元素是離散的，沒有什麼關係。因此，集合雖然是一種數據結構，但在數據結構書中不講，在離散數學的集合論部分有重點講述。
圖1-2 集合
（2）線性結構——一個對一個，如線性表、棧、隊列、數組、廣義表。
線性結構就像穿珠子，是一條線，不會分叉，如圖1-3所示。有唯一的開始和唯一的結束，除了第一個元素外，每個元素都有唯一的直接前驅（前面那個）；除了最後一個元素外，每個元素都有唯一的直接後繼（後面那個）。
著名的瑞士科學家Niklaus Wirth教授提出：數據結構+算法＝程序。數據結構是程序的骨架，算法是程序的靈魂。
1.1 數據結構基礎知識
學習數據結構首先從認識以下幾個概念開始。
1．數據
數據是指所有能輸入到計算機中的描述客觀事物的符號，包括文本、聲音、圖像、符號等。我們經常使用的“掃一掃”的二維碼，也是數據。
2．數據元素
數據元素是數據的基本單位，也稱節點或記錄，如圖1-1所示。
圖1-1 數據元素
3．數據項
數據項表示有獨立含義的數據最小單位，也稱域。若干個數據項構成一個數據元素，數據項是不可分割的最小單位，如圖1-1所示的“86”。
4．數據對象
數據對象是指相同特性的數據元素的集合，是數據的一個子集。
5．數據結構
數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。
數據結構是帶“結構”的數據元素的集合，“結構”是指數據元素之間存在的關係。數據結構研究的問題是將帶有關係的數據存儲在計算機中，並進行相關操作。數據結構包含邏輯結構、存儲結構和運算三個要素。
6．邏輯結構和存儲結構
邏輯結構是數據元素之間的關係，存儲結構是數據元素及其關係在計算機中的存儲方式。例如，小明和小勇是表兄弟，這是他們之間的邏輯關係；他們在教室裡面的位置是他們的存儲結構。無論他們的座位怎樣安排，是挨著坐，還是分開坐，都不影響他們的表兄弟關係。
邏輯結構：數據元素間抽象化的相互關係，與數據的存儲無關，獨立於計算機，它是從具體問題中抽象出來的數學模型。
數據結構的邏輯結構共有以下4種。
（1）集合——數據元素間除“同屬於一個集合”外，無其他關係。
集合中的元素是離散、無序的，就像雞圈中的小雞一樣，可以隨意走動，它們之間沒有什麼關係，唯一的親密關係就是在同一個雞圈裡，如圖1-2所示。數據結構重點研究的是數據之間的關係，而集合中的元素是離散的，沒有什麼關係。因此，集合雖然是一種數據結構，但在數據結構書中不講，在離散數學的集合論部分有重點講述。
圖1-2 集合
（2）線性結構——一個對一個，如線性表、棧、隊列、數組、廣義表。
線性結構就像穿珠子，是一條線，不會分叉，如圖1-3所示。有唯一的開始和唯一的結束，除了第一個元素外，每個元素都有唯一的直接前驅（前面那個）；除了最後一個元素外，每個元素都有唯一的直接後繼（後面那個）。
圖1-3 線性結構
（3）樹形結構——一個對多個，如樹。
樹形結構就像一棵倒立的樹，樹根可以發出多個分支，每個每支也可以繼續發出分支，樹枝和樹枝之間是不相交的，如圖1-4所示。
（4）圖形結構——多個對多個，如圖、網。
圖形結構就像我們經常見到的地圖，任何一個節點都可能和其他節點有關係，就像一張錯綜複雜的網，如圖1-5所示。
著名的瑞士科學家Niklaus Wirth教授提出：數據結構+算法＝程序。數據結構是程序的骨架，算法是程序的靈魂。
1.1 數據結構基礎知識
學習數據結構首先從認識以下幾個概念開始。
1．數據
數據是指所有能輸入到計算機中的描述客觀事物的符號，包括文本、聲音、圖像、符號等。我們經常使用的“掃一掃”的二維碼，也是數據。
2．數據元素
數據元素是數據的基本單位，也稱節點或記錄，如圖1-1所示。
圖1-1 數據元素
3．數據項
數據項表示有獨立含義的數據最小單位，也稱域。若干個數據項構成一個數據元素，數據項是不可分割的最小單位，如圖1-1所示的“86”。
4．數據對象
數據對象是指相同特性的數據元素的集合，是數據的一個子集。
5．數據結構
數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。
數據結構是帶“結構”的數據元素的集合，“結構”是指數據元素之間存在的關係。數據結構研究的問題是將帶有關係的數據存儲在計算機中，並進行相關操作。數據結構包含邏輯結構、存儲結構和運算三個要素。
6．邏輯結構和存儲結構
邏輯結構是數據元素之間的關係，存儲結構是數據元素及其關係在計算機中的存儲方式。例如，小明和小勇是表兄弟，這是他們之間的邏輯關係；他們在教室裡面的位置是他們的存儲結構。無論他們的座位怎樣安排，是挨著坐，還是分開坐，都不影響他們的表兄弟關係。
邏輯結構：數據元素間抽象化的相互關係，與數據的存儲無關，獨立於計算機，它是從具體問題中抽象出來的數學模型。
數據結構的邏輯結構共有以下4種。
（1）集合——數據元素間除“同屬於一個集合”外，無其他關係。
集合中的元素是離散、無序的，就像雞圈中的小雞一樣，可以隨意走動，它們之間沒有什麼關係，唯一的親密關係就是在同一個雞圈裡，如圖1-2所示。數據結構重點研究的是數據之間的關係，而集合中的元素是離散的，沒有什麼關係。因此，集合雖然是一種數據結構，但在數據結構書中不講，在離散數學的集合論部分有重點講述。
圖1-2 集合
（2）線性結構——一個對一個，如線性表、棧、隊列、數組、廣義表。
線性結構就像穿珠子，是一條線，不會分叉，如圖1-3所示。有唯一的開始和唯一的結束，除了第一個元素外，每個元素都有唯一的直接前驅（前面那個）；除了最後一個元素外，每個元素都有唯一的直接後繼（後面那個）。
圖1-3 線性結構
（3）樹形結構——一個對多個，如樹。
樹形結構就像一棵倒立的樹，樹根可以發出多個分支，每個每支也可以繼續發出分支，樹枝和樹枝之間是不相交的，如圖1-4所示。
（4）圖形結構——多個對多個，如圖、網。
圖形結構就像我們經常見到的地圖，任何一個節點都可能和其他節點有關係，就像一張錯綜複雜的網，如圖1-5所示。
圖1-4 樹形結構
著名的瑞士科學家Niklaus Wirth教授提出：數據結構+算法＝程序。數據結構是程序的骨架，算法是程序的靈魂。
1.1 數據結構基礎知識
學習數據結構首先從認識以下幾個概念開始。
1．數據
數據是指所有能輸入到計算機中的描述客觀事物的符號，包括文本、聲音、圖像、符號等。我們經常使用的“掃一掃”的二維碼，也是數據。
2．數據元素
數據元素是數據的基本單位，也稱節點或記錄，如圖1-1所示。
圖1-1 數據元素
3．數據項
數據項表示有獨立含義的數據最小單位，也稱域。若干個數據項構成一個數據元素，數據項是不可分割的最小單位，如圖1-1所示的“86”。
4．數據對象
數據對象是指相同特性的數據元素的集合，是數據的一個子集。
5．數據結構
數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。
數據結構是帶“結構”的數據元素的集合，“結構”是指數據元素之間存在的關係。數據結構研究的問題是將帶有關係的數據存儲在計算機中，並進行相關操作。數據結構包含邏輯結構、存儲結構和運算三個要素。
6．邏輯結構和存儲結構
邏輯結構是數據元素之間的關係，存儲結構是數據元素及其關係在計算機中的存儲方式。例如，小明和小勇是表兄弟，這是他們之間的邏輯關係；他們在教室裡面的位置是他們的存儲結構。無論他們的座位怎樣安排，是挨著坐，還是分開坐，都不影響他們的表兄弟關係。
邏輯結構：數據元素間抽象化的相互關係，與數據的存儲無關，獨立於計算機，它是從具體問題中抽象出來的數學模型。
數據結構的邏輯結構共有以下4種。
（1）集合——數據元素間除“同屬於一個集合”外，無其他關係。
集合中的元素是離散、無序的，就像雞圈中的小雞一樣，可以隨意走動，它們之間沒有什麼關係，唯一的親密關係就是在同一個雞圈裡，如圖1-2所示。數據結構重點研究的是數據之間的關係，而集合中的元素是離散的，沒有什麼關係。因此，集合雖然是一種數據結構，但在數據結構書中不講，在離散數學的集合論部分有重點講述。
圖1-2 集合
（2）線性結構——一個對一個，如線性表、棧、隊列、數組、廣義表。
線性結構就像穿珠子，是一條線，不會分叉，如圖1-3所示。有唯一的開始和唯一的結束，除了第一個元素外，每個元素都有唯一的直接前驅（前面那個）；除了最後一個元素外，每個元素都有唯一的直接後繼（後面那個）。
圖1-3 線性結構
（3）樹形結構——一個對多個，如樹。
樹形結構就像一棵倒立的樹，樹根可以發出多個分支，每個每支也可以繼續發出分支，樹枝和樹枝之間是不相交的，如圖1-4所示。
（4）圖形結構——多個對多個，如圖、網。
圖形結構就像我們經常見到的地圖，任何一個節點都可能和其他節點有關係，就像一張錯綜複雜的網，如圖1-5所示。
圖1-4 樹形結構
圖1-5 圖形結構
存儲結構：數據元素及其關係在計算機中的存儲方式。
存儲結構可以分為4種：順序存儲、鏈式存儲、散列存儲和索引存儲。很多數據結構類書籍只介紹了前兩種基本的存儲結構，這裡加上後兩種，以便讀者瞭解。
（1）順序存儲
順序存儲是指邏輯上相鄰的元素在計算機內的存儲位置也是相鄰的。例如，張小明是哥哥，張小波是弟弟，他們的邏輯關係是兄弟，如果他們住的房子是前後院，也是相鄰的，就可以說他們是順序存儲，如圖1-6所示。
著名的瑞士科學家Niklaus Wirth教授提出：數據結構+算法＝程序。數據結構是程序的骨架，算法是程序的靈魂。
1.1 數據結構基礎知識
學習數據結構首先從認識以下幾個概念開始。
1．數據
數據是指所有能輸入到計算機中的描述客觀事物的符號，包括文本、聲音、圖像、符號等。我們經常使用的“掃一掃”的二維碼，也是數據。
2．數據元素
數據元素是數據的基本單位，也稱節點或記錄，如圖1-1所示。
圖1-1 數據元素
3．數據項
數據項表示有獨立含義的數據最小單位，也稱域。若干個數據項構成一個數據元素，數據項是不可分割的最小單位，如圖1-1所示的“86”。
4．數據對象
數據對象是指相同特性的數據元素的集合，是數據的一個子集。
5．數據結構
數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。
數據結構是帶“結構”的數據元素的集合，“結構”是指數據元素之間存在的關係。數據結構研究的問題是將帶有關係的數據存儲在計算機中，並進行相關操作。數據結構包含邏輯結構、存儲結構和運算三個要素。
6．邏輯結構和存儲結構
邏輯結構是數據元素之間的關係，存儲結構是數據元素及其關係在計算機中的存儲方式。例如，小明和小勇是表兄弟，這是他們之間的邏輯關係；他們在教室裡面的位置是他們的存儲結構。無論他們的座位怎樣安排，是挨著坐，還是分開坐，都不影響他們的表兄弟關係。
邏輯結構：數據元素間抽象化的相互關係，與數據的存儲無關，獨立於計算機，它是從具體問題中抽象出來的數學模型。
數據結構的邏輯結構共有以下4種。
（1）集合——數據元素間除“同屬於一個集合”外，無其他關係。
集合中的元素是離散、無序的，就像雞圈中的小雞一樣，可以隨意走動，它們之間沒有什麼關係，唯一的親密關係就是在同一個雞圈裡，如圖1-2所示。數據結構重點研究的是數據之間的關係，而集合中的元素是離散的，沒有什麼關係。因此，集合雖然是一種數據結構，但在數據結構書中不講，在離散數學的集合論部分有重點講述。
圖1-2 集合
（2）線性結構——一個對一個，如線性表、棧、隊列、數組、廣義表。
線性結構就像穿珠子，是一條線，不會分叉，如圖1-3所示。有唯一的開始和唯一的結束，除了第一個元素外，每個元素都有唯一的直接前驅（前面那個）；除了最後一個元素外，每個元素都有唯一的直接後繼（後面那個）。
圖1-3 線性結構
（3）樹形結構——一個對多個，如樹。
樹形結構就像一棵倒立的樹，樹根可以發出多個分支，每個每支也可以繼續發出分支，樹枝和樹枝之間是不相交的，如圖1-4所示。
（4）圖形結構——多個對多個，如圖、網。
圖形結構就像我們經常見到的地圖，任何一個節點都可能和其他節點有關係，就像一張錯綜複雜的網，如圖1-5所示。
圖1-4 樹形結構
圖1-5 圖形結構
存儲結構：數據元素及其關係在計算機中的存儲方式。
存儲結構可以分為4種：順序存儲、鏈式存儲、散列存儲和索引存儲。很多數據結構類書籍只介紹了前兩種基本的存儲結構，這裡加上後兩種，以便讀者瞭解。
（1）順序存儲
順序存儲是指邏輯上相鄰的元素在計算機內的存儲位置也是相鄰的。例如，張小明是哥哥，張小波是弟弟，他們的邏輯關係是兄弟，如果他們住的房子是前後院，也是相鄰的，就可以說他們是順序存儲，如圖1-6所示。
圖1-6 兄弟兩家前後相鄰
順序存儲採用一段連續的存儲空間，將邏輯上相鄰的元素存儲在連續的空間內，中間不允許有空。順序存儲可以快速定位第幾個元素的地址，但是插入和刪除時需要移動大量元素，如圖1-7所示。
著名的瑞士科學家Niklaus Wirth教授提出：數據結構+算法＝程序。數據結構是程序的骨架，算法是程序的靈魂。
1.1 數據結構基礎知識
學習數據結構首先從認識以下幾個概念開始。
1．數據
數據是指所有能輸入到計算機中的描述客觀事物的符號，包括文本、聲音、圖像、符號等。我們經常使用的“掃一掃”的二維碼，也是數據。
2．數據元素
數據元素是數據的基本單位，也稱節點或記錄，如圖1-1所示。
圖1-1 數據元素
3．數據項
數據項表示有獨立含義的數據最小單位，也稱域。若干個數據項構成一個數據元素，數據項是不可分割的最小單位，如圖1-1所示的“86”。
4．數據對象
數據對象是指相同特性的數據元素的集合，是數據的一個子集。
5．數據結構
數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。
數據結構是帶“結構”的數據元素的集合，“結構”是指數據元素之間存在的關係。數據結構研究的問題是將帶有關係的數據存儲在計算機中，並進行相關操作。數據結構包含邏輯結構、存儲結構和運算三個要素。
6．邏輯結構和存儲結構
邏輯結構是數據元素之間的關係，存儲結構是數據元素及其關係在計算機中的存儲方式。例如，小明和小勇是表兄弟，這是他們之間的邏輯關係；他們在教室裡面的位置是他們的存儲結構。無論他們的座位怎樣安排，是挨著坐，還是分開坐，都不影響他們的表兄弟關係。
邏輯結構：數據元素間抽象化的相互關係，與數據的存儲無關，獨立於計算機，它是從具體問題中抽象出來的數學模型。
數據結構的邏輯結構共有以下4種。
（1）集合——數據元素間除“同屬於一個集合”外，無其他關係。
集合中的元素是離散、無序的，就像雞圈中的小雞一樣，可以隨意走動，它們之間沒有什麼關係，唯一的親密關係就是在同一個雞圈裡，如圖1-2所示。數據結構重點研究的是數據之間的關係，而集合中的元素是離散的，沒有什麼關係。因此，集合雖然是一種數據結構，但在數據結構書中不講，在離散數學的集合論部分有重點講述。
圖1-2 集合
（2）線性結構——一個對一個，如線性表、棧、隊列、數組、廣義表。
線性結構就像穿珠子，是一條線，不會分叉，如圖1-3所示。有唯一的開始和唯一的結束，除了第一個元素外，每個元素都有唯一的直接前驅（前面那個）；除了最後一個元素外，每個元素都有唯一的直接後繼（後面那個）。
圖1-3 線性結構
（3）樹形結構——一個對多個，如樹。
樹形結構就像一棵倒立的樹，樹根可以發出多個分支，每個每支也可以繼續發出分支，樹枝和樹枝之間是不相交的，如圖1-4所示。
（4）圖形結構——多個對多個，如圖、網。
圖形結構就像我們經常見到的地圖，任何一個節點都可能和其他節點有關係，就像一張錯綜複雜的網，如圖1-5所示。
圖1-4 樹形結構
圖1-5 圖形結構
存儲結構：數據元素及其關係在計算機中的存儲方式。
存儲結構可以分為4種：順序存儲、鏈式存儲、散列存儲和索引存儲。很多數據結構類書籍只介紹了前兩種基本的存儲結構，這裡加上後兩種，以便讀者瞭解。
（1）順序存儲
順序存儲是指邏輯上相鄰的元素在計算機內的存儲位置也是相鄰的。例如，張小明是哥哥，張小波是弟弟，他們的邏輯關係是兄弟，如果他們住的房子是前後院，也是相鄰的，就可以說他們是順序存儲，如圖1-6所示。
圖1-6 兄弟兩家前後相鄰
順序存儲採用一段連續的存儲空間，將邏輯上相鄰的元素存儲在連續的空間內，中間不允許有空。順序存儲可以快速定位第幾個元素的地址，但是插入和刪除時需要移動大量元素，如圖1-7所示。
圖1-7 順序存儲
（2）鏈式存儲
鏈式存儲是指邏輯上相鄰的元素在計算機內的存儲位置不一定是相鄰的。例如，哥哥張小明因為工作調動去了北京，弟弟仍然在鄭州，他們的位置是不相鄰的，但是哥哥有弟弟家的地址，很容易可以找到弟弟，就可以說他們是鏈式存儲，如圖1-8所示。
著名的瑞士科學家Niklaus Wirth教授提出：數據結構+算法＝程序。數據結構是程序的骨架，算法是程序的靈魂。
1.1 數據結構基礎知識
學習數據結構首先從認識以下幾個概念開始。
1．數據
數據是指所有能輸入到計算機中的描述客觀事物的符號，包括文本、聲音、圖像、符號等。我們經常使用的“掃一掃”的二維碼，也是數據。
2．數據元素
數據元素是數據的基本單位，也稱節點或記錄，如圖1-1所示。
圖1-1 數據元素
3．數據項
數據項表示有獨立含義的數據最小單位，也稱域。若干個數據項構成一個數據元素，數據項是不可分割的最小單位，如圖1-1所示的“86”。
4．數據對象
數據對象是指相同特性的數據元素的集合，是數據的一個子集。
5．數據結構
數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。
數據結構是帶“結構”的數據元素的集合，“結構”是指數據元素之間存在的關係。數據結構研究的問題是將帶有關係的數據存儲在計算機中，並進行相關操作。數據結構包含邏輯結構、存儲結構和運算三個要素。
6．邏輯結構和存儲結構
邏輯結構是數據元素之間的關係，存儲結構是數據元素及其關係在計算機中的存儲方式。例如，小明和小勇是表兄弟，這是他們之間的邏輯關係；他們在教室裡面的位置是他們的存儲結構。無論他們的座位怎樣安排，是挨著坐，還是分開坐，都不影響他們的表兄弟關係。
邏輯結構：數據元素間抽象化的相互關係，與數據的存儲無關，獨立於計算機，它是從具體問題中抽象出來的數學模型。
數據結構的邏輯結構共有以下4種。
（1）集合——數據元素間除“同屬於一個集合”外，無其他關係。
集合中的元素是離散、無序的，就像雞圈中的小雞一樣，可以隨意走動，它們之間沒有什麼關係，唯一的親密關係就是在同一個雞圈裡，如圖1-2所示。數據結構重點研究的是數據之間的關係，而集合中的元素是離散的，沒有什麼關係。因此，集合雖然是一種數據結構，但在數據結構書中不講，在離散數學的集合論部分有重點講述。
圖1-2 集合
（2）線性結構——一個對一個，如線性表、棧、隊列、數組、廣義表。
線性結構就像穿珠子，是一條線，不會分叉，如圖1-3所示。有唯一的開始和唯一的結束，除了第一個元素外，每個元素都有唯一的直接前驅（前面那個）；除了最後一個元素外，每個元素都有唯一的直接後繼（後面那個）。
圖1-3 線性結構
（3）樹形結構——一個對多個，如樹。
樹形結構就像一棵倒立的樹，樹根可以發出多個分支，每個每支也可以繼續發出分支，樹枝和樹枝之間是不相交的，如圖1-4所示。
（4）圖形結構——多個對多個，如圖、網。
圖形結構就像我們經常見到的地圖，任何一個節點都可能和其他節點有關係，就像一張錯綜複雜的網，如圖1-5所示。
圖1-4 樹形結構
圖1-5 圖形結構
存儲結構：數據元素及其關係在計算機中的存儲方式。
存儲結構可以分為4種：順序存儲、鏈式存儲、散列存儲和索引存儲。很多數據結構類書籍只介紹了前兩種基本的存儲結構，這裡加上後兩種，以便讀者瞭解。
（1）順序存儲
順序存儲是指邏輯上相鄰的元素在計算機內的存儲位置也是相鄰的。例如，張小明是哥哥，張小波是弟弟，他們的邏輯關係是兄弟，如果他們住的房子是前後院，也是相鄰的，就可以說他們是順序存儲，如圖1-6所示。
圖1-6 兄弟兩家前後相鄰
順序存儲採用一段連續的存儲空間，將邏輯上相鄰的元素存儲在連續的空間內，中間不允許有空。順序存儲可以快速定位第幾個元素的地址，但是插入和刪除時需要移動大量元素，如圖1-7所示。
圖1-7 順序存儲
（2）鏈式存儲
鏈式存儲是指邏輯上相鄰的元素在計算機內的存儲位置不一定是相鄰的。例如，哥哥張小明因為工作調動去了北京，弟弟仍然在鄭州，他們的位置是不相鄰的，但是哥哥有弟弟家的地址，很容易可以找到弟弟，就可以說他們是鏈式存儲，如圖1-8所示。
圖1-8 哥哥有弟弟家地址
鏈式存儲就像一個鐵鏈子，一環扣一環才能連在一起。每個節點除了數據域，還有一個指針域，記錄下一個元素的存儲地址，如圖1-9所示。
（3）散列存儲
散列存儲，又稱哈希（Hash）存儲，由節點的關鍵碼值決定節點的存儲地址。用散列函數確定數據元素的存儲位置與關鍵碼之間的對應關係，如圖1-10所示。
著名的瑞士科學家Niklaus Wirth教授提出：數據結構+算法＝程序。數據結構是程序的骨架，算法是程序的靈魂。
1.1 數據結構基礎知識
學習數據結構首先從認識以下幾個概念開始。
1．數據
數據是指所有能輸入到計算機中的描述客觀事物的符號，包括文本、聲音、圖像、符號等。我們經常使用的“掃一掃”的二維碼，也是數據。
2．數據元素
數據元素是數據的基本單位，也稱節點或記錄，如圖1-1所示。
圖1-1 數據元素
3．數據項
數據項表示有獨立含義的數據最小單位，也稱域。若干個數據項構成一個數據元素，數據項是不可分割的最小單位，如圖1-1所示的“86”。
4．數據對象
數據對象是指相同特性的數據元素的集合，是數據的一個子集。
5．數據結構
數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。
數據結構是帶“結構”的數據元素的集合，“結構”是指數據元素之間存在的關係。數據結構研究的問題是將帶有關係的數據存儲在計算機中，並進行相關操作。數據結構包含邏輯結構、存儲結構和運算三個要素。
6．邏輯結構和存儲結構
邏輯結構是數據元素之間的關係，存儲結構是數據元素及其關係在計算機中的存儲方式。例如，小明和小勇是表兄弟，這是他們之間的邏輯關係；他們在教室裡面的位置是他們的存儲結構。無論他們的座位怎樣安排，是挨著坐，還是分開坐，都不影響他們的表兄弟關係。
邏輯結構：數據元素間抽象化的相互關係，與數據的存儲無關，獨立於計算機，它是從具體問題中抽象出來的數學模型。
數據結構的邏輯結構共有以下4種。
（1）集合——數據元素間除“同屬於一個集合”外，無其他關係。
集合中的元素是離散、無序的，就像雞圈中的小雞一樣，可以隨意走動，它們之間沒有什麼關係，唯一的親密關係就是在同一個雞圈裡，如圖1-2所示。數據結構重點研究的是數據之間的關係，而集合中的元素是離散的，沒有什麼關係。因此，集合雖然是一種數據結構，但在數據結構書中不講，在離散數學的集合論部分有重點講述。
圖1-2 集合
（2）線性結構——一個對一個，如線性表、棧、隊列、數組、廣義表。
線性結構就像穿珠子，是一條線，不會分叉，如圖1-3所示。有唯一的開始和唯一的結束，除了第一個元素外，每個元素都有唯一的直接前驅（前面那個）；除了最後一個元素外，每個元素都有唯一的直接後繼（後面那個）。
圖1-3 線性結構
（3）樹形結構——一個對多個，如樹。
樹形結構就像一棵倒立的樹，樹根可以發出多個分支，每個每支也可以繼續發出分支，樹枝和樹枝之間是不相交的，如圖1-4所示。
（4）圖形結構——多個對多個，如圖、網。
圖形結構就像我們經常見到的地圖，任何一個節點都可能和其他節點有關係，就像一張錯綜複雜的網，如圖1-5所示。
圖1-4 樹形結構
圖1-5 圖形結構
存儲結構：數據元素及其關係在計算機中的存儲方式。
存儲結構可以分為4種：順序存儲、鏈式存儲、散列存儲和索引存儲。很多數據結構類書籍只介紹了前兩種基本的存儲結構，這裡加上後兩種，以便讀者瞭解。
（1）順序存儲
順序存儲是指邏輯上相鄰的元素在計算機內的存儲位置也是相鄰的。例如，張小明是哥哥，張小波是弟弟，他們的邏輯關係是兄弟，如果他們住的房子是前後院，也是相鄰的，就可以說他們是順序存儲，如圖1-6所示。
圖1-6 兄弟兩家前後相鄰
順序存儲採用一段連續的存儲空間，將邏輯上相鄰的元素存儲在連續的空間內，中間不允許有空。順序存儲可以快速定位第幾個元素的地址，但是插入和刪除時需要移動大量元素，如圖1-7所示。
圖1-7 順序存儲
（2）鏈式存儲
鏈式存儲是指邏輯上相鄰的元素在計算機內的存儲位置不一定是相鄰的。例如，哥哥張小明因為工作調動去了北京，弟弟仍然在鄭州，他們的位置是不相鄰的，但是哥哥有弟弟家的地址，很容易可以找到弟弟，就可以說他們是鏈式存儲，如圖1-8所示。
圖1-8 哥哥有弟弟家地址
鏈式存儲就像一個鐵鏈子，一環扣一環才能連在一起。每個節點除了數據域，還有一個指針域，記錄下一個元素的存儲地址，如圖1-9所示。
（3）散列存儲
散列存儲，又稱哈希（Hash）存儲，由節點的關鍵碼值決定節點的存儲地址。用散列函數確定數據元素的存儲位置與關鍵碼之間的對應關係，如圖1-10所示。
圖1-9 鏈式存儲
著名的瑞士科學家Niklaus Wirth教授提出：數據結構+算法＝程序。數據結構是程序的骨架，算法是程序的靈魂。
1.1 數據結構基礎知識
學習數據結構首先從認識以下幾個概念開始。
1．數據
數據是指所有能輸入到計算機中的描述客觀事物的符號，包括文本、聲音、圖像、符號等。我們經常使用的“掃一掃”的二維碼，也是數據。
2．數據元素
數據元素是數據的基本單位，也稱節點或記錄，如圖1-1所示。
圖1-1 數據元素
3．數據項
數據項表示有獨立含義的數據最小單位，也稱域。若干個數據項構成一個數據元素，數據項是不可分割的最小單位，如圖1-1所示的“86”。
4．數據對象
數據對象是指相同特性的數據元素的集合，是數據的一個子集。
5．數據結構
數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。
數據結構是帶“結構”的數據元素的集合，“結構”是指數據元素之間存在的關係。數據結構研究的問題是將帶有關係的數據存儲在計算機中，並進行相關操作。數據結構包含邏輯結構、存儲結構和運算三個要素。
6．邏輯結構和存儲結構
邏輯結構是數據元素之間的關係，存儲結構是數據元素及其關係在計算機中的存儲方式。例如，小明和小勇是表兄弟，這是他們之間的邏輯關係；他們在教室裡面的位置是他們的存儲結構。無論他們的座位怎樣安排，是挨著坐，還是分開坐，都不影響他們的表兄弟關係。
邏輯結構：數據元素間抽象化的相互關係，與數據的存儲無關，獨立於計算機，它是從具體問題中抽象出來的數學模型。
數據結構的邏輯結構共有以下4種。
（1）集合——數據元素間除“同屬於一個集合”外，無其他關係。
集合中的元素是離散、無序的，就像雞圈中的小雞一樣，可以隨意走動，它們之間沒有什麼關係，唯一的親密關係就是在同一個雞圈裡，如圖1-2所示。數據結構重點研究的是數據之間的關係，而集合中的元素是離散的，沒有什麼關係。因此，集合雖然是一種數據結構，但在數據結構書中不講，在離散數學的集合論部分有重點講述。
圖1-2 集合
（2）線性結構——一個對一個，如線性表、棧、隊列、數組、廣義表。
線性結構就像穿珠子，是一條線，不會分叉，如圖1-3所示。有唯一的開始和唯一的結束，除了第一個元素外，每個元素都有唯一的直接前驅（前面那個）；除了最後一個元素外，每個元素都有唯一的直接後繼（後面那個）。
圖1-3 線性結構
（3）樹形結構——一個對多個，如樹。
樹形結構就像一棵倒立的樹，樹根可以發出多個分支，每個每支也可以繼續發出分支，樹枝和樹枝之間是不相交的，如圖1-4所示。
（4）圖形結構——多個對多個，如圖、網。
圖形結構就像我們經常見到的地圖，任何一個節點都可能和其他節點有關係，就像一張錯綜複雜的網，如圖1-5所示。
圖1-4 樹形結構
圖1-5 圖形結構
存儲結構：數據元素及其關係在計算機中的存儲方式。
存儲結構可以分為4種：順序存儲、鏈式存儲、散列存儲和索引存儲。很多數據結構類書籍只介紹了前兩種基本的存儲結構，這裡加上後兩種，以便讀者瞭解。
（1）順序存儲
順序存儲是指邏輯上相鄰的元素在計算機內的存儲位置也是相鄰的。例如，張小明是哥哥，張小波是弟弟，他們的邏輯關係是兄弟，如果他們住的房子是前後院，也是相鄰的，就可以說他們是順序存儲，如圖1-6所示。
圖1-6 兄弟兩家前後相鄰
順序存儲採用一段連續的存儲空間，將邏輯上相鄰的元素存儲在連續的空間內，中間不允許有空。順序存儲可以快速定位第幾個元素的地址，但是插入和刪除時需要移動大量元素，如圖1-7所示。
圖1-7 順序存儲
（2）鏈式存儲
鏈式存儲是指邏輯上相鄰的元素在計算機內的存儲位置不一定是相鄰的。例如，哥哥張小明因為工作調動去了北京，弟弟仍然在鄭州，他們的位置是不相鄰的，但是哥哥有弟弟家的地址，很容易可以找到弟弟，就可以說他們是鏈式存儲，如圖1-8所示。
圖1-8 哥哥有弟弟家地址
鏈式存儲就像一個鐵鏈子，一環扣一環才能連在一起。每個節點除了數據域，還有一個指針域，記錄下一個元素的存儲地址，如圖1-9所示。
（3）散列存儲
散列存儲，又稱哈希（Hash）存儲，由節點的關鍵碼值決定節點的存儲地址。用散列函數確定數據元素的存儲位置與關鍵碼之間的對應關係，如圖1-10所示。
圖1-9 鏈式存儲
圖1-10 散列存儲
例如，假設散列表的地址範圍為0～9，散列函數為H(key)=key%10。輸入關鍵碼序列：（24,10,32,17,41,15,49），構造散列表，如圖1-11所示。
24%10=4：存儲在下標為4的位置。
10%10=0：存儲在下標為0的位置。
32%10=2：存儲在下標為2的位置。
17%10=7：存儲在下標為7的位置。
41%10=1：存儲在下標為1的位置。
15%10=5：存儲在下標為5的位置。
49%10=9：存儲在下標為9的位置。
著名的瑞士科學家Niklaus Wirth教授提出：數據結構+算法＝程序。數據結構是程序的骨架，算法是程序的靈魂。
1.1 數據結構基礎知識
學習數據結構首先從認識以下幾個概念開始。
1．數據
數據是指所有能輸入到計算機中的描述客觀事物的符號，包括文本、聲音、圖像、符號等。我們經常使用的“掃一掃”的二維碼，也是數據。
2．數據元素
數據元素是數據的基本單位，也稱節點或記錄，如圖1-1所示。
圖1-1 數據元素
3．數據項
數據項表示有獨立含義的數據最小單位，也稱域。若干個數據項構成一個數據元素，數據項是不可分割的最小單位，如圖1-1所示的“86”。
4．數據對象
數據對象是指相同特性的數據元素的集合，是數據的一個子集。
5．數據結構
數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。
數據結構是帶“結構”的數據元素的集合，“結構”是指數據元素之間存在的關係。數據結構研究的問題是將帶有關係的數據存儲在計算機中，並進行相關操作。數據結構包含邏輯結構、存儲結構和運算三個要素。
6．邏輯結構和存儲結構
邏輯結構是數據元素之間的關係，存儲結構是數據元素及其關係在計算機中的存儲方式。例如，小明和小勇是表兄弟，這是他們之間的邏輯關係；他們在教室裡面的位置是他們的存儲結構。無論他們的座位怎樣安排，是挨著坐，還是分開坐，都不影響他們的表兄弟關係。
邏輯結構：數據元素間抽象化的相互關係，與數據的存儲無關，獨立於計算機，它是從具體問題中抽象出來的數學模型。
數據結構的邏輯結構共有以下4種。
（1）集合——數據元素間除“同屬於一個集合”外，無其他關係。
集合中的元素是離散、無序的，就像雞圈中的小雞一樣，可以隨意走動，它們之間沒有什麼關係，唯一的親密關係就是在同一個雞圈裡，如圖1-2所示。數據結構重點研究的是數據之間的關係，而集合中的元素是離散的，沒有什麼關係。因此，集合雖然是一種數據結構，但在數據結構書中不講，在離散數學的集合論部分有重點講述。
圖1-2 集合
（2）線性結構——一個對一個，如線性表、棧、隊列、數組、廣義表。
線性結構就像穿珠子，是一條線，不會分叉，如圖1-3所示。有唯一的開始和唯一的結束，除了第一個元素外，每個元素都有唯一的直接前驅（前面那個）；除了最後一個元素外，每個元素都有唯一的直接後繼（後面那個）。
圖1-3 線性結構
（3）樹形結構——一個對多個，如樹。
樹形結構就像一棵倒立的樹，樹根可以發出多個分支，每個每支也可以繼續發出分支，樹枝和樹枝之間是不相交的，如圖1-4所示。
（4）圖形結構——多個對多個，如圖、網。
圖形結構就像我們經常見到的地圖，任何一個節點都可能和其他節點有關係，就像一張錯綜複雜的網，如圖1-5所示。
圖1-4 樹形結構
圖1-5 圖形結構
存儲結構：數據元素及其關係在計算機中的存儲方式。
存儲結構可以分為4種：順序存儲、鏈式存儲、散列存儲和索引存儲。很多數據結構類書籍只介紹了前兩種基本的存儲結構，這裡加上後兩種，以便讀者瞭解。
（1）順序存儲
順序存儲是指邏輯上相鄰的元素在計算機內的存儲位置也是相鄰的。例如，張小明是哥哥，張小波是弟弟，他們的邏輯關係是兄弟，如果他們住的房子是前後院，也是相鄰的，就可以說他們是順序存儲，如圖1-6所示。
圖1-6 兄弟兩家前後相鄰
順序存儲採用一段連續的存儲空間，將邏輯上相鄰的元素存儲在連續的空間內，中間不允許有空。順序存儲可以快速定位第幾個元素的地址，但是插入和刪除時需要移動大量元素，如圖1-7所示。
圖1-7 順序存儲
（2）鏈式存儲
鏈式存儲是指邏輯上相鄰的元素在計算機內的存儲位置不一定是相鄰的。例如，哥哥張小明因為工作調動去了北京，弟弟仍然在鄭州，他們的位置是不相鄰的，但是哥哥有弟弟家的地址，很容易可以找到弟弟，就可以說他們是鏈式存儲，如圖1-8所示。
圖1-8 哥哥有弟弟家地址
鏈式存儲就像一個鐵鏈子，一環扣一環才能連在一起。每個節點除了數據域，還有一個指針域，記錄下一個元素的存儲地址，如圖1-9所示。
（3）散列存儲
散列存儲，又稱哈希（Hash）存儲，由節點的關鍵碼值決定節點的存儲地址。用散列函數確定數據元素的存儲位置與關鍵碼之間的對應關係，如圖1-10所示。
圖1-9 鏈式存儲
圖1-10 散列存儲
例如，假設散列表的地址範圍為0～9，散列函數為H(key)=key%10。輸入關鍵碼序列：（24,10,32,17,41,15,49），構造散列表，如圖1-11所示。
24%10=4：存儲在下標為4的位置。
10%10=0：存儲在下標為0的位置。
32%10=2：存儲在下標為2的位置。
17%10=7：存儲在下標為7的位置。
41%10=1：存儲在下標為1的位置。
15%10=5：存儲在下標為5的位置。
49%10=9：存儲在下標為9的位置。
圖1-11 散列表
散列存儲可以通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。如果有衝突，則有多種處理衝突的方法。
（4）索引存儲
索引存儲是指除建立存儲節點信息外，還建立附加的索引表來標識節點的地址。索引表由若干索引項組成。如果每個節點在索引表中都有一個索引項，則該索引表稱為稠密索引。若一組節點在索引表中只對應於一個索引項，則該索引表稱為稀疏索引。索引項的一般形式是關鍵字、地址，如圖1-12所示。
著名的瑞士科學家Niklaus Wirth教授提出：數據結構+算法＝程序。數據結構是程序的骨架，算法是程序的靈魂。
1.1 數據結構基礎知識
學習數據結構首先從認識以下幾個概念開始。
1．數據
數據是指所有能輸入到計算機中的描述客觀事物的符號，包括文本、聲音、圖像、符號等。我們經常使用的“掃一掃”的二維碼，也是數據。
2．數據元素
數據元素是數據的基本單位，也稱節點或記錄，如圖1-1所示。
圖1-1 數據元素
3．數據項
數據項表示有獨立含義的數據最小單位，也稱域。若干個數據項構成一個數據元素，數據項是不可分割的最小單位，如圖1-1所示的“86”。
4．數據對象
數據對象是指相同特性的數據元素的集合，是數據的一個子集。
5．數據結構
數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。
數據結構是帶“結構”的數據元素的集合，“結構”是指數據元素之間存在的關係。數據結構研究的問題是將帶有關係的數據存儲在計算機中，並進行相關操作。數據結構包含邏輯結構、存儲結構和運算三個要素。
6．邏輯結構和存儲結構
邏輯結構是數據元素之間的關係，存儲結構是數據元素及其關係在計算機中的存儲方式。例如，小明和小勇是表兄弟，這是他們之間的邏輯關係；他們在教室裡面的位置是他們的存儲結構。無論他們的座位怎樣安排，是挨著坐，還是分開坐，都不影響他們的表兄弟關係。
邏輯結構：數據元素間抽象化的相互關係，與數據的存儲無關，獨立於計算機，它是從具體問題中抽象出來的數學模型。
數據結構的邏輯結構共有以下4種。
（1）集合——數據元素間除“同屬於一個集合”外，無其他關係。
集合中的元素是離散、無序的，就像雞圈中的小雞一樣，可以隨意走動，它們之間沒有什麼關係，唯一的親密關係就是在同一個雞圈裡，如圖1-2所示。數據結構重點研究的是數據之間的關係，而集合中的元素是離散的，沒有什麼關係。因此，集合雖然是一種數據結構，但在數據結構書中不講，在離散數學的集合論部分有重點講述。
圖1-2 集合
（2）線性結構——一個對一個，如線性表、棧、隊列、數組、廣義表。
線性結構就像穿珠子，是一條線，不會分叉，如圖1-3所示。有唯一的開始和唯一的結束，除了第一個元素外，每個元素都有唯一的直接前驅（前面那個）；除了最後一個元素外，每個元素都有唯一的直接後繼（後面那個）。
圖1-3 線性結構
（3）樹形結構——一個對多個，如樹。
樹形結構就像一棵倒立的樹，樹根可以發出多個分支，每個每支也可以繼續發出分支，樹枝和樹枝之間是不相交的，如圖1-4所示。
（4）圖形結構——多個對多個，如圖、網。
圖形結構就像我們經常見到的地圖，任何一個節點都可能和其他節點有關係，就像一張錯綜複雜的網，如圖1-5所示。
圖1-4 樹形結構
圖1-5 圖形結構
存儲結構：數據元素及其關係在計算機中的存儲方式。
存儲結構可以分為4種：順序存儲、鏈式存儲、散列存儲和索引存儲。很多數據結構類書籍只介紹了前兩種基本的存儲結構，這裡加上後兩種，以便讀者瞭解。
（1）順序存儲
順序存儲是指邏輯上相鄰的元素在計算機內的存儲位置也是相鄰的。例如，張小明是哥哥，張小波是弟弟，他們的邏輯關係是兄弟，如果他們住的房子是前後院，也是相鄰的，就可以說他們是順序存儲，如圖1-6所示。
圖1-6 兄弟兩家前後相鄰
順序存儲採用一段連續的存儲空間，將邏輯上相鄰的元素存儲在連續的空間內，中間不允許有空。順序存儲可以快速定位第幾個元素的地址，但是插入和刪除時需要移動大量元素，如圖1-7所示。
圖1-7 順序存儲
（2）鏈式存儲
鏈式存儲是指邏輯上相鄰的元素在計算機內的存儲位置不一定是相鄰的。例如，哥哥張小明因為工作調動去了北京，弟弟仍然在鄭州，他們的位置是不相鄰的，但是哥哥有弟弟家的地址，很容易可以找到弟弟，就可以說他們是鏈式存儲，如圖1-8所示。
圖1-8 哥哥有弟弟家地址
鏈式存儲就像一個鐵鏈子，一環扣一環才能連在一起。每個節點除了數據域，還有一個指針域，記錄下一個元素的存儲地址，如圖1-9所示。
（3）散列存儲
散列存儲，又稱哈希（Hash）存儲，由節點的關鍵碼值決定節點的存儲地址。用散列函數確定數據元素的存儲位置與關鍵碼之間的對應關係，如圖1-10所示。
圖1-9 鏈式存儲
圖1-10 散列存儲
例如，假設散列表的地址範圍為0～9，散列函數為H(key)=key%10。輸入關鍵碼序列：（24,10,32,17,41,15,49），構造散列表，如圖1-11所示。
24%10=4：存儲在下標為4的位置。
10%10=0：存儲在下標為0的位置。
32%10=2：存儲在下標為2的位置。
17%10=7：存儲在下標為7的位置。
41%10=1：存儲在下標為1的位置。
15%10=5：存儲在下標為5的位置。
49%10=9：存儲在下標為9的位置。
圖1-11 散列表
散列存儲可以通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。如果有衝突，則有多種處理衝突的方法。
（4）索引存儲
索引存儲是指除建立存儲節點信息外，還建立附加的索引表來標識節點的地址。索引表由若干索引項組成。如果每個節點在索引表中都有一個索引項，則該索引表稱為稠密索引。若一組節點在索引表中只對應於一個索引項，則該索引表稱為稀疏索引。索引項的一般形式是關鍵字、地址，如圖1-12所示。
圖1-12 索引存儲
在搜索引擎中，需要按某些關鍵字的值來查找記錄，為此可以按關鍵字建立索引，這種索引稱為倒排索引。為什麼稱為倒排索引呢？因為正常情況下，都是由記錄來確定屬性值的，而這裡是根據屬性值來查找記錄。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。帶有倒排索引的文件稱為倒排索引文件，又稱為倒排文件。倒排文件可以實現快速檢索，索引存儲是目前搜索引擎最常用的存儲方法，如圖1-13所示。
著名的瑞士科學家Niklaus Wirth教授提出：數據結構+算法＝程序。數據結構是程序的骨架，算法是程序的靈魂。
1.1 數據結構基礎知識
學習數據結構首先從認識以下幾個概念開始。
1．數據
數據是指所有能輸入到計算機中的描述客觀事物的符號，包括文本、聲音、圖像、符號等。我們經常使用的“掃一掃”的二維碼，也是數據。
2．數據元素
數據元素是數據的基本單位，也稱節點或記錄，如圖1-1所示。
圖1-1 數據元素
3．數據項
數據項表示有獨立含義的數據最小單位，也稱域。若干個數據項構成一個數據元素，數據項是不可分割的最小單位，如圖1-1所示的“86”。
4．數據對象
數據對象是指相同特性的數據元素的集合，是數據的一個子集。
5．數據結構
數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。
數據結構是帶“結構”的數據元素的集合，“結構”是指數據元素之間存在的關係。數據結構研究的問題是將帶有關係的數據存儲在計算機中，並進行相關操作。數據結構包含邏輯結構、存儲結構和運算三個要素。
6．邏輯結構和存儲結構
邏輯結構是數據元素之間的關係，存儲結構是數據元素及其關係在計算機中的存儲方式。例如，小明和小勇是表兄弟，這是他們之間的邏輯關係；他們在教室裡面的位置是他們的存儲結構。無論他們的座位怎樣安排，是挨著坐，還是分開坐，都不影響他們的表兄弟關係。
邏輯結構：數據元素間抽象化的相互關係，與數據的存儲無關，獨立於計算機，它是從具體問題中抽象出來的數學模型。
數據結構的邏輯結構共有以下4種。
（1）集合——數據元素間除“同屬於一個集合”外，無其他關係。
集合中的元素是離散、無序的，就像雞圈中的小雞一樣，可以隨意走動，它們之間沒有什麼關係，唯一的親密關係就是在同一個雞圈裡，如圖1-2所示。數據結構重點研究的是數據之間的關係，而集合中的元素是離散的，沒有什麼關係。因此，集合雖然是一種數據結構，但在數據結構書中不講，在離散數學的集合論部分有重點講述。
圖1-2 集合
（2）線性結構——一個對一個，如線性表、棧、隊列、數組、廣義表。
線性結構就像穿珠子，是一條線，不會分叉，如圖1-3所示。有唯一的開始和唯一的結束，除了第一個元素外，每個元素都有唯一的直接前驅（前面那個）；除了最後一個元素外，每個元素都有唯一的直接後繼（後面那個）。
圖1-3 線性結構
（3）樹形結構——一個對多個，如樹。
樹形結構就像一棵倒立的樹，樹根可以發出多個分支，每個每支也可以繼續發出分支，樹枝和樹枝之間是不相交的，如圖1-4所示。
（4）圖形結構——多個對多個，如圖、網。
圖形結構就像我們經常見到的地圖，任何一個節點都可能和其他節點有關係，就像一張錯綜複雜的網，如圖1-5所示。
圖1-4 樹形結構
圖1-5 圖形結構
存儲結構：數據元素及其關係在計算機中的存儲方式。
存儲結構可以分為4種：順序存儲、鏈式存儲、散列存儲和索引存儲。很多數據結構類書籍只介紹了前兩種基本的存儲結構，這裡加上後兩種，以便讀者瞭解。
（1）順序存儲
順序存儲是指邏輯上相鄰的元素在計算機內的存儲位置也是相鄰的。例如，張小明是哥哥，張小波是弟弟，他們的邏輯關係是兄弟，如果他們住的房子是前後院，也是相鄰的，就可以說他們是順序存儲，如圖1-6所示。
圖1-6 兄弟兩家前後相鄰
順序存儲採用一段連續的存儲空間，將邏輯上相鄰的元素存儲在連續的空間內，中間不允許有空。順序存儲可以快速定位第幾個元素的地址，但是插入和刪除時需要移動大量元素，如圖1-7所示。
圖1-7 順序存儲
（2）鏈式存儲
鏈式存儲是指邏輯上相鄰的元素在計算機內的存儲位置不一定是相鄰的。例如，哥哥張小明因為工作調動去了北京，弟弟仍然在鄭州，他們的位置是不相鄰的，但是哥哥有弟弟家的地址，很容易可以找到弟弟，就可以說他們是鏈式存儲，如圖1-8所示。
圖1-8 哥哥有弟弟家地址
鏈式存儲就像一個鐵鏈子，一環扣一環才能連在一起。每個節點除了數據域，還有一個指針域，記錄下一個元素的存儲地址，如圖1-9所示。
（3）散列存儲
散列存儲，又稱哈希（Hash）存儲，由節點的關鍵碼值決定節點的存儲地址。用散列函數確定數據元素的存儲位置與關鍵碼之間的對應關係，如圖1-10所示。
圖1-9 鏈式存儲
圖1-10 散列存儲
例如，假設散列表的地址範圍為0～9，散列函數為H(key)=key%10。輸入關鍵碼序列：（24,10,32,17,41,15,49），構造散列表，如圖1-11所示。
24%10=4：存儲在下標為4的位置。
10%10=0：存儲在下標為0的位置。
32%10=2：存儲在下標為2的位置。
17%10=7：存儲在下標為7的位置。
41%10=1：存儲在下標為1的位置。
15%10=5：存儲在下標為5的位置。
49%10=9：存儲在下標為9的位置。
圖1-11 散列表
散列存儲可以通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。如果有衝突，則有多種處理衝突的方法。
（4）索引存儲
索引存儲是指除建立存儲節點信息外，還建立附加的索引表來標識節點的地址。索引表由若干索引項組成。如果每個節點在索引表中都有一個索引項，則該索引表稱為稠密索引。若一組節點在索引表中只對應於一個索引項，則該索引表稱為稀疏索引。索引項的一般形式是關鍵字、地址，如圖1-12所示。
圖1-12 索引存儲
在搜索引擎中，需要按某些關鍵字的值來查找記錄，為此可以按關鍵字建立索引，這種索引稱為倒排索引。為什麼稱為倒排索引呢？因為正常情況下，都是由記錄來確定屬性值的，而這裡是根據屬性值來查找記錄。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。帶有倒排索引的文件稱為倒排索引文件，又稱為倒排文件。倒排文件可以實現快速檢索，索引存儲是目前搜索引擎最常用的存儲方法，如圖1-13所示。
圖1-13 倒排索引
7．抽象數據類型
抽象數據類型（Abstract Data Type，ADT）是將數據對象、數據對象之間的關係和數據對象的基本操作封裝在一起的一種表達方式，它和工程中的應用是一致的。在工程項目中，開始編程之前，首先列出程序需要完成的功能任務，先不用管具體怎麼實現，實現細節在項目後期完成，一開始只是抽象出有哪些基本操作。把這些操作項封裝為抽象數據類型，等待後面具體實現這些操作。而其他對象如果想調用這些操作，只需要按照規定好的參數接口調用，並不需要知道具體是怎麼實現的，從而實現了數據封裝和信息隱藏。在C++中可以用類的聲明表示抽象數據類型，用類的實現來實現抽象數據類型的具體操作。
抽象數據類型可以用以下的三元組來表示。
ADT抽象數據類型名{
數據對象：<數據對象的定義>
數據關係：<數據關係的定義>
基本操作：<基本操作的定義>
} ADT抽象數據類型名
例如，線性表的抽象數據類型的定義：
ADT List{
數據對象：D={ai|ai∈Elemset, i=1,2,…,n,n≥0}
數據關係：R={<ai−1,ai>|ai−1,ai∈D, i=2,…,n}
基本操作：
InitList(&L)
操作結果：構造一個空的線性表L
DestroyList(&L)
初始條件：線性表已存在
操作結果：銷燬線性表L
ClearList(&L)
初始條件：線性表已存在
操作結果：置線性表L為空表
ListEmpty(L)
初始條件：線性表已存在
操作結果：若線性表L為空表，則返回TRUE，否則返回FALSE
ListLenght(L)
初始條件：線性表已存在
操作結果：返回線性表L數據元素個數
GetElem(L, i, &e)
初始條件：線性表已存在（1≤i≤ListLenght(L)）
操作結果：用e返回線性表L中第i個數據元素的值
locatElem(L, e, comare())
初始條件：線性表已存在，comare()是數據元素判定函數
操作結果：返回線性表L中第1個與e滿足關係comare()的數據元素的位序
PriorElem(L, cur_e, &pre_e)
初始條件：線性表已存在
操作結果：若cur_e是線性表L的數據元素，且不是第一個，則用pre_e返回它
的前驅，否則操作失敗，pre_e無定義
NextElem(L, cur_e, &next_e)
初始條件：線性表已存在
操作結果：若cur_e是線性表L的數據元素，且不是第最後一個，則用next_e返
回它的後繼，否則操作失敗，next_e無定義
ListInsert(&L, i, e)
初始條件：線性表已存在（1≤i≤ListLenght(L)+1）
操作結果：在線性表L中第i個數據元素之前插入新元素e，L長度加1
ListDelete(&L, i, &e)
初始條件：線性表已存在（1≤i≤ListLenght(L)）
操作結果：刪除線性表L中第i個數據元素，用e返回其值，L長度減1
ListTraverse(L, visit())
初始條件：線性表已存在
操作結果：依次對線性表L的每個數據元素調用visit()函數，一旦visit()失敗，
則操作失敗
}ADT List
（1）為什麼要使用抽象數據類型？
抽象數據類型的主要作用是數據封裝和信息隱藏，讓實現與使用相分離。數據及其相關操作的結合稱為數據封裝。對象可以對其他對象隱藏某些操作細節，從而使這些操作不會受到其他對象的影響，這就是信息隱藏。抽象數據類型獨立於運算的具體實現，使用戶程序只能通過抽象數據類型定義的某些操作來訪問其中的數據，實現了信息隱藏。
（2）為什麼很多書中沒有使用抽象數據類型？
既然抽象數據類型符合工程化需要，可以實現數據封裝和信息隱藏，為什麼很多數據結構書中的程序並沒有使用抽象數據類型呢？因為很多人覺得數據結構難以理解，學習起來非常吃力，因此僅僅將數據結構的基本操作作為重點，把每一個基本操作講解清楚，使讀者學會和掌握數據結構的基本操作，便完成了數據結構書的基本任務。在實際工程中，需要根據實際情況融會貫通，靈活運用，這是後續話題。目前要掌握的就是各種數據結構的基本操作，本書也將基本操作作為重點講述，並結合實例講解數據結構的應用。
數據結構和算法相輔相成，密不可分，在學習數據結構之前，首先要了解什麼是算法、好算法的衡量標準，以及算法複雜度的計算方法。
著名的瑞士科學家Niklaus Wirth教授提出：數據結構+算法＝程序。數據結構是程序的骨架，算法是程序的靈魂。
1.1 數據結構基礎知識
學習數據結構首先從認識以下幾個概念開始。
1．數據
數據是指所有能輸入到計算機中的描述客觀事物的符號，包括文本、聲音、圖像、符號等。我們經常使用的“掃一掃”的二維碼，也是數據。
2．數據元素
數據元素是數據的基本單位，也稱節點或記錄，如圖1-1所示。
圖1-1 數據元素
3．數據項
數據項表示有獨立含義的數據最小單位，也稱域。若干個數據項構成一個數據元素，數據項是不可分割的最小單位，如圖1-1所示的“86”。
4．數據對象
數據對象是指相同特性的數據元素的集合，是數據的一個子集。
5．數據結構
數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。
數據結構是帶“結構”的數據元素的集合，“結構”是指數據元素之間存在的關係。數據結構研究的問題是將帶有關係的數據存儲在計算機中，並進行相關操作。數據結構包含邏輯結構、存儲結構和運算三個要素。
6．邏輯結構和存儲結構
邏輯結構是數據元素之間的關係，存儲結構是數據元素及其關係在計算機中的存儲方式。例如，小明和小勇是表兄弟，這是他們之間的邏輯關係；他們在教室裡面的位置是他們的存儲結構。無論他們的座位怎樣安排，是挨著坐，還是分開坐，都不影響他們的表兄弟關係。
邏輯結構：數據元素間抽象化的相互關係，與數據的存儲無關，獨立於計算機，它是從具體問題中抽象出來的數學模型。
數據結構的邏輯結構共有以下4種。
（1）集合——數據元素間除“同屬於一個集合”外，無其他關係。
集合中的元素是離散、無序的，就像雞圈中的小雞一樣，可以隨意走動，它們之間沒有什麼關係，唯一的親密關係就是在同一個雞圈裡，如圖1-2所示。數據結構重點研究的是數據之間的關係，而集合中的元素是離散的，沒有什麼關係。因此，集合雖然是一種數據結構，但在數據結構書中不講，在離散數學的集合論部分有重點講述。
圖1-2 集合
（2）線性結構——一個對一個，如線性表、棧、隊列、數組、廣義表。
線性結構就像穿珠子，是一條線，不會分叉，如圖1-3所示。有唯一的開始和唯一的結束，除了第一個元素外，每個元素都有唯一的直接前驅（前面那個）；除了最後一個元素外，每個元素都有唯一的直接後繼（後面那個）。
圖1-3 線性結構
（3）樹形結構——一個對多個，如樹。
樹形結構就像一棵倒立的樹，樹根可以發出多個分支，每個每支也可以繼續發出分支，樹枝和樹枝之間是不相交的，如圖1-4所示。
（4）圖形結構——多個對多個，如圖、網。
圖形結構就像我們經常見到的地圖，任何一個節點都可能和其他節點有關係，就像一張錯綜複雜的網，如圖1-5所示。
圖1-4 樹形結構
圖1-5 圖形結構
存儲結構：數據元素及其關係在計算機中的存儲方式。
存儲結構可以分為4種：順序存儲、鏈式存儲、散列存儲和索引存儲。很多數據結構類書籍只介紹了前兩種基本的存儲結構，這裡加上後兩種，以便讀者瞭解。
（1）順序存儲
順序存儲是指邏輯上相鄰的元素在計算機內的存儲位置也是相鄰的。例如，張小明是哥哥，張小波是弟弟，他們的邏輯關係是兄弟，如果他們住的房子是前後院，也是相鄰的，就可以說他們是順序存儲，如圖1-6所示。
圖1-6 兄弟兩家前後相鄰
順序存儲採用一段連續的存儲空間，將邏輯上相鄰的元素存儲在連續的空間內，中間不允許有空。順序存儲可以快速定位第幾個元素的地址，但是插入和刪除時需要移動大量元素，如圖1-7所示。
圖1-7 順序存儲
（2）鏈式存儲
鏈式存儲是指邏輯上相鄰的元素在計算機內的存儲位置不一定是相鄰的。例如，哥哥張小明因為工作調動去了北京，弟弟仍然在鄭州，他們的位置是不相鄰的，但是哥哥有弟弟家的地址，很容易可以找到弟弟，就可以說他們是鏈式存儲，如圖1-8所示。
圖1-8 哥哥有弟弟家地址
鏈式存儲就像一個鐵鏈子，一環扣一環才能連在一起。每個節點除了數據域，還有一個指針域，記錄下一個元素的存儲地址，如圖1-9所示。
（3）散列存儲
散列存儲，又稱哈希（Hash）存儲，由節點的關鍵碼值決定節點的存儲地址。用散列函數確定數據元素的存儲位置與關鍵碼之間的對應關係，如圖1-10所示。
圖1-9 鏈式存儲
圖1-10 散列存儲
例如，假設散列表的地址範圍為0～9，散列函數為H(key)=key%10。輸入關鍵碼序列：（24,10,32,17,41,15,49），構造散列表，如圖1-11所示。
24%10=4：存儲在下標為4的位置。
10%10=0：存儲在下標為0的位置。
32%10=2：存儲在下標為2的位置。
17%10=7：存儲在下標為7的位置。
41%10=1：存儲在下標為1的位置。
15%10=5：存儲在下標為5的位置。
49%10=9：存儲在下標為9的位置。
圖1-11 散列表
散列存儲可以通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。如果有衝突，則有多種處理衝突的方法。
（4）索引存儲
索引存儲是指除建立存儲節點信息外，還建立附加的索引表來標識節點的地址。索引表由若干索引項組成。如果每個節點在索引表中都有一個索引項，則該索引表稱為稠密索引。若一組節點在索引表中只對應於一個索引項，則該索引表稱為稀疏索引。索引項的一般形式是關鍵字、地址，如圖1-12所示。
圖1-12 索引存儲
在搜索引擎中，需要按某些關鍵字的值來查找記錄，為此可以按關鍵字建立索引，這種索引稱為倒排索引。為什麼稱為倒排索引呢？因為正常情況下，都是由記錄來確定屬性值的，而這裡是根據屬性值來查找記錄。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。帶有倒排索引的文件稱為倒排索引文件，又稱為倒排文件。倒排文件可以實現快速檢索，索引存儲是目前搜索引擎最常用的存儲方法，如圖1-13所示。
圖1-13 倒排索引
7．抽象數據類型
抽象數據類型（Abstract Data Type，ADT）是將數據對象、數據對象之間的關係和數據對象的基本操作封裝在一起的一種表達方式，它和工程中的應用是一致的。在工程項目中，開始編程之前，首先列出程序需要完成的功能任務，先不用管具體怎麼實現，實現細節在項目後期完成，一開始只是抽象出有哪些基本操作。把這些操作項封裝為抽象數據類型，等待後面具體實現這些操作。而其他對象如果想調用這些操作，只需要按照規定好的參數接口調用，並不需要知道具體是怎麼實現的，從而實現了數據封裝和信息隱藏。在C++中可以用類的聲明表示抽象數據類型，用類的實現來實現抽象數據類型的具體操作。
抽象數據類型可以用以下的三元組來表示。
ADT抽象數據類型名{
數據對象：<數據對象的定義>
數據關係：<數據關係的定義>
基本操作：<基本操作的定義>
} ADT抽象數據類型名
例如，線性表的抽象數據類型的定義：
ADT List{
數據對象：D={ai|ai∈Elemset, i=1,2,…,n,n≥0}
數據關係：R={<ai−1,ai>|ai−1,ai∈D, i=2,…,n}
基本操作：
InitList(&L)
操作結果：構造一個空的線性表L
DestroyList(&L)
初始條件：線性表已存在
操作結果：銷燬線性表L
ClearList(&L)
初始條件：線性表已存在
操作結果：置線性表L為空表
ListEmpty(L)
初始條件：線性表已存在
操作結果：若線性表L為空表，則返回TRUE，否則返回FALSE
ListLenght(L)
初始條件：線性表已存在
操作結果：返回線性表L數據元素個數
GetElem(L, i, &e)
初始條件：線性表已存在（1≤i≤ListLenght(L)）
操作結果：用e返回線性表L中第i個數據元素的值
locatElem(L, e, comare())
初始條件：線性表已存在，comare()是數據元素判定函數
操作結果：返回線性表L中第1個與e滿足關係comare()的數據元素的位序
PriorElem(L, cur_e, &pre_e)
初始條件：線性表已存在
操作結果：若cur_e是線性表L的數據元素，且不是第一個，則用pre_e返回它
的前驅，否則操作失敗，pre_e無定義
NextElem(L, cur_e, &next_e)
初始條件：線性表已存在
操作結果：若cur_e是線性表L的數據元素，且不是第最後一個，則用next_e返
回它的後繼，否則操作失敗，next_e無定義
ListInsert(&L, i, e)
初始條件：線性表已存在（1≤i≤ListLenght(L)+1）
操作結果：在線性表L中第i個數據元素之前插入新元素e，L長度加1
ListDelete(&L, i, &e)
初始條件：線性表已存在（1≤i≤ListLenght(L)）
操作結果：刪除線性表L中第i個數據元素，用e返回其值，L長度減1
ListTraverse(L, visit())
初始條件：線性表已存在
操作結果：依次對線性表L的每個數據元素調用visit()函數，一旦visit()失敗，
則操作失敗
}ADT List
（1）為什麼要使用抽象數據類型？
抽象數據類型的主要作用是數據封裝和信息隱藏，讓實現與使用相分離。數據及其相關操作的結合稱為數據封裝。對象可以對其他對象隱藏某些操作細節，從而使這些操作不會受到其他對象的影響，這就是信息隱藏。抽象數據類型獨立於運算的具體實現，使用戶程序只能通過抽象數據類型定義的某些操作來訪問其中的數據，實現了信息隱藏。
（2）為什麼很多書中沒有使用抽象數據類型？
既然抽象數據類型符合工程化需要，可以實現數據封裝和信息隱藏，為什麼很多數據結構書中的程序並沒有使用抽象數據類型呢？因為很多人覺得數據結構難以理解，學習起來非常吃力，因此僅僅將數據結構的基本操作作為重點，把每一個基本操作講解清楚，使讀者學會和掌握數據結構的基本操作，便完成了數據結構書的基本任務。在實際工程中，需要根據實際情況融會貫通，靈活運用，這是後續話題。目前要掌握的就是各種數據結構的基本操作，本書也將基本操作作為重點講述，並結合實例講解數據結構的應用。
數據結構和算法相輔相成，密不可分，在學習數據結構之前，首先要了解什麼是算法、好算法的衡量標準，以及算法複雜度的計算方法。
京東網上商城 京東購書
（1）完美圖解+豐富實例，複雜問題簡單化
為基本操作配以圖解，用數據結構解決生活中的實際問題，學習過程更加輕鬆有趣。
（2）原理分析+實戰演練，真正地學以致用
通俗化講解基礎知識，在實戰中體會數據結構的設計和操作，鍛鍊獨立思考的能力。
（3）配套代碼+在線答疑，為學習保駕護航
提供書中的範例程序源代碼、練習題以及答案解析，並在博客和QQ群中答疑解惑。