圖解幾種常見的線性表

wawor4827 發布于2019-07-01 10:01 / 1633人閱讀

摘要：下面來看一下，有哪些數據結構屬于線性表吧棧特性先進后出只有唯一的一個出入口介紹棧又名堆棧，它是一種運算受限的線性表。

原文是在我自己博客中，小伙伴也可以點閱讀原文進行跳轉查看，還有好聽的背景音樂噢背景音樂已取消~ 2333333

線性表

什么是線性表？就是一種連續或間斷存儲的數組，這里的連續和間斷是針對物理內存空間中線性表元素之間是否連續，其中連續數組對應內置數組的實現方式，間斷數組對應的是指針的實現方式，這種方式也稱為鏈表實現。

也就是說，線性表有兩種實現方式，一種是內置數組實現，另一種是鏈表實現。
下面來看一下，有哪些數據結構屬于線性表吧！

棧(stack) 特性

先進后出

只有唯一的一個出入口

介紹

棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

通過上面的話語表達，相信不難理解棧的概念。下面我們上圖感受一下棧和入棧出棧情況：

上圖中我們可以看到入棧、出棧的實際情況。只有一個入口（缺口），在這個缺口處，進行入棧和出棧操作。在現實生活中更形象的比喻就是壘磚。
磚一次一次往上疊加，取的時候也是從最上部取，一直取到底部的最后一塊。

php實現

php也可以實現簡單的棧，由于php中沒有提供很好的操作指針的方式，所以只能通過數組的方式實現。使用連個函數就可以，它們分別是 array_push和array_pop

array_push 將一個或多個單元壓入數組的末尾（入棧）;

array_pop 彈出數組最后一個單元（出棧）

簡單代碼示例：

$arr = [];

array_push($arr, 1); // $arr[] = 1;
print_r($arr);
sleep(1);

array_push($arr, 2); // $arr[] = 2;
print_r($arr);
sleep(1);

array_push($arr, 3); // $arr[] = 3;
print_r($arr);
sleep(1);

$val = array_pop($arr);
echo $val . "

";
print_r($arr);
sleep(1);

$val = array_pop($arr);
echo $val . "

";
print_r($arr);

把這段代碼放在cli下跑，就能看到效果了，看一下運行gif圖：

從命令行的執行結果來看，我們先依次入棧1、2、3三個值，后來取出的時候，也是按照棧的先進后出，后進先出的特性出棧的。

隊列（queue） 特性

先進先出

兩個缺口，一入口，一個出口

介紹

隊列（queue）是一種采用先進先出(FIFO)策略的抽象數據結構，它的想法來自于生活中排隊的策略。在生活中比較形象的比喻就是排隊了。

php實現

同樣的，php中也可以以數組的形式實現隊列，兩個函數array_push和array_shift

array_push 將一個或多個單元壓入數組的末尾（入隊）;

array_shift 將數組開頭的單元移出數組（出隊）

可以發現array_push和上面的棧入棧是同一個函數，其實兩個函數的作用一樣。用在這里就表示為入隊了。

簡單代碼示例：

header("Content-type:text/html;charset=utf-8");  

$arr = [];
echo "入隊-1 array_push($arr, 1)" . "
";
array_push($arr, 1); // $arr[] = 1;
print_r($arr);
sleep(1);
echo "入隊-2 array_push($arr, 2)" . "
";
array_push($arr, 2); // $arr[] = 2;
print_r($arr);
sleep(1);
echo "入隊-3 array_push($arr, 2)" . "
";
array_push($arr, 3); // $arr[] = 3;
print_r($arr);
sleep(1);

echo "出隊-3 array_shift($arr)" . "
";
$val = array_shift($arr);
echo $val . "

";
print_r($arr);
sleep(1);

echo "出隊-2 array_shift($arr)" . "
";
$val = array_shift($arr);
echo $val . "

";
print_r($arr);

圖示：

從命令行的執行結果我們可以看到，我們依次入隊 1、2、3三個值，出隊的時候先出1，再出2.符合我們隊列的特性，先進先出，后進后出。

單鏈表 特性

由每一個節點組成

每個節點中包含下一個節點的指針(*next)

介紹

單鏈表是一種鏈式存取的數據結構，用一組地址任意的存儲單元存放線性表中的數據元素。鏈表中的數據是以結點來表示的，每個結點的構成：元素(數據元素的映象) + 指針(指示后繼元素存儲位置)，元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據

鏈表有兩個比較重要的部分組成:

指針指向下一個節點的地址，（即內存位置的直接地址）

節點鏈表中的組成部分，對于單鏈表，一個節點里面包含節點數據和下一個節點的指針

圖中我們可以看到，單向鏈表由一個頭指針、頭節點、n個元素節點和尾節點組成。
其中頭指針代表，我們根據這個指針可以找到對應的鏈表
頭節點，用來存儲鏈表的一些信息，比如鏈表長度，頭節點指針指向第一個元素節點
每個節點中又包括，節點數據（data）和指針（*next指向下一個元素節點）、
一直到尾節點為null

雙向鏈表 特性

同單鏈表類似由一個一個的節點組成

與單向鏈表不同的是，每個節點中包含了除數據(data)之外的上一個節點的指針(*prev)和下一個節點的指針(*next)

介紹

雙向鏈表又叫做雙鏈表；跟單向鏈表不同的是，他的每個節點都有兩個指針，一個指向前面的一個節點，一個指向后面的節點。通過這兩個指針我們可以很方便的通過某一個節點，訪問到相（前）鄰（后）的兩個節點。

我們來看一下，雙向鏈表的圖示：

圖中我們可以看到，除了頭節點和尾節點之外，每個中間節點與節點之間都是首尾相連，每個節點保存了上一個節點的指針和下一個節點的指針，這就是與單鏈表的不同之處。

注：我們也可以構造雙向循環鏈表；尾節點的下一個指針*next指向頭節點，而頭節點的*prev指向尾節點；這樣就構成了一個雙向循環鏈表；下圖所示，我們只需把雙向鏈表簡單改造一下即可：

總結

以上，就是本篇文章介紹的內容了。
數據結構很多，也很高深，其中的算法知識，也讓人回味無窮。

云服務器 GPU云服務器線性表的存儲結構線性表的順序表c語言線性表集合的交并分別建立包含10個數據元素的順序線性表和鏈式線性表

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/28717.html

CodeSalt | Python數據結構的實現 — 鏈表

摘要：數據結構實現鏈表簡單介紹鏈表是一種常見的基礎數據結構，是一種線性表，但是并不會按線性的順序存儲數據，而是在每一個節點里存到下一個節點的指針。圖解如下查找通過遍歷鏈表，使用標記是否找到了正在尋找的項。一旦為，就是對包含要刪除的項的節點的引用。 Python數據結構實現—鏈表 1. 簡單介紹鏈表(Linked list)是一種常見的基礎數據結構，是一種線性表，但是并不會按線性的順序存儲數...

BaronZhang 2019-07-30 14:32 評論0 收藏0
幾分鐘理解數據結構 - 哈希表及其優化

摘要：小概哈希容器也可以理解為是一種映射容器，采用哈希算法映射算法，散列算法，將不定長的數據壓縮成定長的數據，這串定長值我們稱為哈希值，并將不同的哈希值分組存起來，每一個分組我們認為是一個槽我們將不同的數據格式通過哈希算法，將其映射到不同的槽內，小概哈希容器也可以理解為是一種映射容器，采用哈希算法（映射算法，散列算法），將不定長的數據壓縮成定長的數據，這串定長值我們稱為哈希值，并將不同...

Dean 2019-08-15 11:06 評論0 收藏0
【算法】算法圖解筆記_算法簡介

摘要：在本書中你將學習比較不同算法的優缺點該使用合并排序算法還是快速排序算法或者該使用數組還是鏈表。這樣的算法包括快速排序一種速度較快的排序算法。在讀《算法圖解》這本書，這本書有兩個優點：手繪風格的圖，看著很讓人入戲；算法采用Python語言描述，能更好的表達算法思想。關于算法的學習有兩點心得：算法思想最重要，理解了思想，算法是很容易寫出來的，所以盡量不要把過多精力放在細節上...

tomlingtm 2019-07-31 10:10 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

zsirfs 2019-08-23 15:33 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

you_De 2019-08-16 15:26 評論0 收藏0