常見的數據結構都有哪些?數據結構 = 數據元素 數據元素的關系，我來為大家講解一下關于常見的數據結構都有哪些?跟着小編一起來看一看吧!

常見的數據結構都有哪些

數據結構 = 數據元素 數據元素的關系。

數據元素的關系也是數據。

這裡的關系是指邏輯意義上的關系，包括：

I 一對一的線性關系：元素之間是前驅後繼的關系。

II 一對多的樹型關系：元素之間是父子、兄弟關系。

III 多對多的圖型關系：元素之間是鄰接關系。

元素及其關系都需要存儲到存儲器才能被處理，存儲的方式稱為存儲關系，存儲還有關系？有的。計算機的存儲單元是一種線性關系，因為不可能所有的數據都存儲到一起，有時需要分散存儲。正像我們在一個倉庫存儲物品一樣，當一批物品所需要的空間較大，而倉庫沒有這樣大的一整塊空間，但一些零散的空間可以存儲下來，就要分散存儲（假設分7個位置），分散存儲的物品，如何能找到全部的物品呢？

I 每一個位置再放置一張卡片，上面标識下一個位置的地址，隻要知道了第一個位置的地址，順着找便能全部找到；

II 額外建立一張表格，用來存儲每一個地址，這樣的表格稱索引表，你打開索引表一看，就知道物品的位置了，就像一本書的目錄一樣。

以上都是需要額外增加空間來表示存儲關系的，對應到計算機存儲器上的數據存儲，就是鍊式存儲和索引存儲。

順序存儲自然不用說，數據不加處理地按順序放到一起，通過存儲單元的線性關系來體現其數據元素邏輯上的線性關系，如數組。還有一種稱為哈希存儲的方式，我們知道，對于一個數組，數組名就是這一塊内存單元的基地址，通過偏移值便可以得出各元素的偏移地址，在數據中，偏移值稱為下标。對于一個數據元素，在一個數組的地址空間中，如果不考慮按順序放置數據元素，是否可以根據數據元素的關鍵字來确定一個特定的下标呢？這是可以的，解決的辦法就是使用哈希函數，用哈希函數哈希一下這個關鍵字，得出一個特定的下标，作為其存儲地址，這樣，當用關鍵字查詢時，隻需用哈希函數哈希關鍵字便可求出地址而找到元素了。當然，有可能會有幾個關鍵字通過相同的哈希函數哈希出相同的下标，解決的方法很多，其中之一就是鍊地址法，将相同下标的數據元素再串成一張線性鍊表，這樣就形成了數組 鍊表的方式。

數組 鍊表的方式是一個萬能的方式，數據元素的關系都可以通過鍊式存儲來實現，相比用數組（如圖型的鄰接矩陣）來存儲數據關系，更能節約内存空間，如樹型的孩子鍊表表示法、圖型的鄰接表等。

不管是數組 數據（或二維數組）還是數組 鍊表，都是一種線性關系，所以說，非線性關系的樹型和圖型的邏輯關系和存儲關系都是用線性的數據或鍊表來表示和存儲的。

線性關系是一種一維關系，樹型和圖型可以理解為一種二維關系，二維關系可以用二維數組來描述，也可以用數組 鍊表的方式來描述和存儲。

我們來看一下數組和鍊表的在增删、查找等基礎操作上執行性能（時間複雜度）：

數組：增删是O(n)，查找是O(1)。

鍊表：增删是O(1)，查找是O(n)。

如何在兩者之間獲得一個平衡？

在數據結構中，二叉樹是一個很特殊的存在。我們知道，現實中的樹不可能隻有兩個叉，在計算機科學中也是一樣，二叉樹也是特意設置的，我們知道，二分查找可以獲得O(logn)的效率，如果用一個圖形來描述，就是一個二叉樹的形狀。

如果将線性關系的數據組織成特定二叉樹的形式，其查找效率便可以獲得O(logn)的時間複雜度，O(1)<O(logn)<O(n)，所謂的特定就是要求相對平衡和有序，如平衡搜索樹，紅黑樹等。

另外，對于數據結構，很核心的一個東西就是遍曆了，遍曆離不開循環，循環要理解循環的結束方式及元素或指針的移動方式。

數組和鍊表的遍曆較簡單，也不需要什麼輔助的數據結構，樹和圖就要複雜一些，要将一個非線性結構進行線性化的操作。深度優先遍曆需要一個顯式棧或隐式棧（遞歸會由編譯器實現一個隐式棧），廣度優先遍曆需要一個隊列作為輔助。

無論哪種搜索，都是通過對一個線性表進行處理，隻不過是先處理頭部還是尾部的問題罷了。

處理頭部優先的時候，也就是先加入的先探索，就是廣度優先了，因為，頭部的都是兄弟節點；

而尾部的則是深度優先，因為放入尾部的都是剛剛生産出來的節點，後加入的先探索——也就是所謂一條路走到死。

同理可以聯想到啟發式搜索。啟發式搜索就是先以你自定義的優先級處理，然後再以廣度為優先級處理。

所以，歸根結底，所謂的搜索，就是一種定義了優先級的枚舉。(不管是廣度還是深度，遍曆都會形成一條一維的線)

1 數組

for (int i = 0; i < n; i ) { printf(“%d\n”, a[i]); }

下标是相對于數組起始地址a的偏移量，i 表示每次移動一個數據類型的内存單元長度。

for的循環次數确定，因此循環結束條件也是确定的：i < n。

i ……→n。

2 鍊表

typedef struct lnk { int data; struct lnk* next; }*lnkPtr; lnkPtr p; …… while (p) { p = p->next; }

對于鍊表，尾部結構會特殊處理，将next指針置為NULL，這樣在循環時便可以将此作為結束标志。

鍊表的指針域指向相鄰結點，因此指針的移動用p = p->next;表示。

對于指針的賦值，可以理解為指針指向。如p = p->next;可以理解為p指向p->next。

p = p->next……→p(NULL)

3 棧和隊列

while(!stk.empty()) // 棧非空 { stk.pop(); // 出棧； // 操作出棧元素 } while(!q.empty()) // 隊非空 { q.dequeue( ); // 出隊； // 操作出隊中元素 }

棧有順序棧（一般用數組實現）和鍊式棧（一般用單鍊表實現），隊列也是如此。其循環操作類似上述的數組與鍊表。在出棧函數中一般定義了内存地址或指針的移動，也類似于上述的數組與鍊表。

stk.pop()……stk.empty()==0 q.dequeue……q.empty()==0

-End-

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!