圖解幾種常見的線性表

wawor4827 發(fā)布于2019-07-01 10:01 / 1616人閱讀

摘要：下面來看一下，有哪些數(shù)據(jù)結(jié)構(gòu)屬于線性表吧棧特性先進(jìn)后出只有唯一的一個(gè)出入口介紹棧又名堆棧，它是一種運(yùn)算受限的線性表。

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

線性表

什么是線性表？就是一種連續(xù)或間斷存儲的數(shù)組，這里的連續(xù)和間斷是針對物理內(nèi)存空間中線性表元素之間是否連續(xù)，其中連續(xù)數(shù)組對應(yīng)內(nèi)置數(shù)組的實(shí)現(xiàn)方式，間斷數(shù)組對應(yīng)的是指針的實(shí)現(xiàn)方式，這種方式也稱為鏈表實(shí)現(xiàn)。

也就是說，線性表有兩種實(shí)現(xiàn)方式，一種是內(nèi)置數(shù)組實(shí)現(xiàn)，另一種是鏈表實(shí)現(xiàn)。
下面來看一下，有哪些數(shù)據(jù)結(jié)構(gòu)屬于線性表吧！

棧(stack) 特性

先進(jìn)后出

只有唯一的一個(gè)出入口

介紹

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

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

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

php實(shí)現(xiàn)

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

array_push 將一個(gè)或多個(gè)單元壓入數(shù)組的末尾（入棧）;

array_pop 彈出數(shù)組最后一個(gè)單元（出棧）

簡單代碼示例：

$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下跑，就能看到效果了，看一下運(yùn)行g(shù)if圖：

從命令行的執(zhí)行結(jié)果來看，我們先依次入棧1、2、3三個(gè)值，后來取出的時(shí)候，也是按照棧的先進(jìn)后出，后進(jìn)先出的特性出棧的。

隊(duì)列（queue） 特性

先進(jìn)先出

兩個(gè)缺口，一入口，一個(gè)出口

介紹

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

php實(shí)現(xiàn)

同樣的，php中也可以以數(shù)組的形式實(shí)現(xiàn)隊(duì)列，兩個(gè)函數(shù)array_push和array_shift

array_push 將一個(gè)或多個(gè)單元壓入數(shù)組的末尾（入隊(duì)）;

array_shift 將數(shù)組開頭的單元移出數(shù)組（出隊(duì)）

可以發(fā)現(xiàn)array_push和上面的棧入棧是同一個(gè)函數(shù)，其實(shí)兩個(gè)函數(shù)的作用一樣。用在這里就表示為入隊(duì)了。

簡單代碼示例：

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

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

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

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

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

";
print_r($arr);

圖示：

從命令行的執(zhí)行結(jié)果我們可以看到，我們依次入隊(duì) 1、2、3三個(gè)值，出隊(duì)的時(shí)候先出1，再出2.符合我們隊(duì)列的特性，先進(jìn)先出，后進(jìn)后出。

單鏈表 特性

由每一個(gè)節(jié)點(diǎn)組成

每個(gè)節(jié)點(diǎn)中包含下一個(gè)節(jié)點(diǎn)的指針(*next)

介紹

單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。鏈表中的數(shù)據(jù)是以結(jié)點(diǎn)來表示的，每個(gè)結(jié)點(diǎn)的構(gòu)成：元素(數(shù)據(jù)元素的映象) + 指針(指示后繼元素存儲位置)，元素就是存儲數(shù)據(jù)的存儲單元，指針就是連接每個(gè)結(jié)點(diǎn)的地址數(shù)據(jù)

鏈表有兩個(gè)比較重要的部分組成:

指針指向下一個(gè)節(jié)點(diǎn)的地址，（即內(nèi)存位置的直接地址）

節(jié)點(diǎn) 鏈表中的組成部分，對于單鏈表，一個(gè)節(jié)點(diǎn)里面包含節(jié)點(diǎn)數(shù)據(jù)和下一個(gè)節(jié)點(diǎn)的指針

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

雙向鏈表 特性

同單鏈表類似由一個(gè)一個(gè)的節(jié)點(diǎn)組成

與單向鏈表不同的是，每個(gè)節(jié)點(diǎn)中包含了除數(shù)據(jù)(data)之外的上一個(gè)節(jié)點(diǎn)的指針(*prev)和下一個(gè)節(jié)點(diǎn)的指針(*next)

介紹

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

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

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

注：我們也可以構(gòu)造雙向循環(huán)鏈表；尾節(jié)點(diǎn)的下一個(gè)指針*next指向頭節(jié)點(diǎn)，而頭節(jié)點(diǎn)的*prev指向尾節(jié)點(diǎn)；這樣就構(gòu)成了一個(gè)雙向循環(huán)鏈表；下圖所示，我們只需把雙向鏈表簡單改造一下即可：

總結(jié)

以上，就是本篇文章介紹的內(nèi)容了。
數(shù)據(jù)結(jié)構(gòu)很多，也很高深，其中的算法知識，也讓人回味無窮。