下载麻将游戏免费|手机麻将游戏

鏈表不會?看這個立馬就懂!

飛來科技  發布時間:2019-12-23 15:01:12

本文關鍵詞:鏈表的基本操作博客

鏈表_c語言程序設計 職工信息管理系統 鏈表_鏈表的基本操作博客

小白: 慶哥慶哥,鏈表是哪個啊?

慶哥: 呦西,那么愛學習啊,那咱今天就來把鏈表懟一懟吧,爭取之后再也不學鏈表啦

小白: 為啥以后再也不學啦,難道鏈表沒什么用嗎?

慶哥: 那應該不啊,鏈表不僅有用而且很有用,必須好好把握,為啥以后不再學了呢?因為經過此次的學習,你就再也忘不掉啦

小白: 那慶哥,我可先說好了,我之前雖然對鏈表一竅不通啊

慶哥: 那沒事,誰不學哪都是不會滴,學了不就毀了嘛,接下來咱就一起學習鏈表,攻克這個知識點,記住,有哪些不懂得應趕快問哦。

小白: 好呀,我的第一個問題來啦,什么是鏈表啊

慶哥: 首先就從“鏈表”二字來看,你認為是個啥?想一想。鏈表?鏈子?表?,有看法沒,有的之后針對名字啊,為了方便大眾的理解,名字通常就簡單的表現了它是個啥,所以鏈表是倆字,一個鏈一個表,那什么是鏈什么是表呢?

小白: 這個啊,我想想,鏈是不是就是我們常見的鏈子啊

慶哥: 是啊,就是這樣的。,大鐵鏈子,不不,大金鏈子

你看,就是這個。怎么樣,看到這個大金鏈子,有沒有覺得自己針對“鏈”這個詞有點意思了,知道它一般是個哪些玩意了吧。

小白: 嗯嗯,是的,鏈子嘛,就像這個大金鏈子一樣,一環扣一環的,那啥是表呢?我記得之前常說這個表啊,什么數據表,對,還有之前說的哈希表,這個表是個啥啊?

慶哥: 的確,我們之前一直都在說哪個這表那表的,但是啥是表呢?難道是我們戴的那個手表嗎?鐘表?當然不是啦,咱們這說的表通常是指:

按照一定次序排列的元素集合,那就是表

啥意思呢?也就是說啊,咱們這兒的表指的只是一些數據集合,啥是數據集合嘞,就可以理解成一堆數據,只不過這數據人家有一定的順序。

小白: 順序?是不是那種根據12345這樣排序啊

慶哥: 這里的排序啊,是這種的,它嘞,有一個前驅后繼的概念,啥意思咧,看圖:

在這里插入圖片描述

其實也好知道,說白了,在這個表中存儲的也就是數據,這些數據是根據排序排列的,這里的次序的理解是這種的,就是表中的每個元素就是一個數據吧,這些個數據,它的前邊也有數據,后面還有數據,前面的數據就叫做這個數據的前驅,那上面的嘞,自然就是后繼了。

小白: 那每個數據都是這樣的嗎

慶哥: 那可不一定啊,你想想最前面的后更前面的哪個,是不是最前面的唯有后繼,最前面的唯有前驅呢?你可以想想這種排隊的,最前面那貨跟更前面那貨

小白: 嗯嗯,這下對表這個概念有點理解了,說白了,不就是數據集合嘛

慶哥: 可以的,就可以如此簡單的理解,清楚這個概念后來,再看“鏈表”,知道是個啥了嗎?有沒有覺得概念清晰一點了。

小白: 嗯嗯,經過中間的大鐵鏈子還有這個表的理解,現在對鏈表是個啥,明白了許多,我今天的理解就是,鏈表就和個大鐵鏈子似的,不過每個節點不是大鐵環子,而是一個數據

慶哥: 哈哈,可以的,這樣理解也有可以的,不過你認為這個每個節點的數據是怎樣的呢?

小白: 經過前面的講解,我今天對鏈表的理解,它就是這樣的:

在這里插入圖片描述

鏈表嘛,就和大鐵鏈子似的,一個扣著一個,每一環雖然都是數據。

慶哥: 可以的,這樣理解不錯,不過還不是太具體,雖然說鏈表和大鐵鏈子似的,畢竟人家不是大鐵鏈子啊,不是真的象大鐵鏈子這樣,一環扣著一環的,大鐵鏈子是物理上存在的,可以相互的一環扣著一環,但是像鏈表,人家是個數據結構,不是那么可以看得見摸得著的,所以,人家的鏈接可不是像大鐵鏈子那樣,那么,你想想,對于鏈表而言,它的每個數據是如何鏈接的呢?

小白: 這個啊,讓我想想,數據之間相互鏈接起來?咋鏈呢?不能手牽手吧,哦哦,我想起來了,可以用指針啊,就是用個指針指向下一個數據,這樣也行吧?就像那樣:

在這里插入圖片描述

c語言程序設計 職工信息管理系統 鏈表_鏈表的基本操作博客_鏈表

行嗎?

慶哥: 必須可以啊,實際上,鏈表中就是依靠指針互相鏈接的,那么你對指針了解的多少呢?

小白: 指針啊,掌握的不是太好,這個是在學習C語言中學的,在java中沒有指針吧,好像java中的引用和指針類似。

慶哥: 是的,指針可以說是c語言中的真諦啊,比較難理解,而且易于出錯,所以java語言在設計的之后聲稱吸收C語言的特定,摒棄其難理解且易于出錯的指針,實際上,在java中的引用就跟指針類似,在學習鏈表的過程中,理解指針的概念很重要,這將有助于對鏈表的理解跟掌握。

小白: 嗯嗯,我也明白指針的重要性,但是,對于指針的話,我認為理解出來好費勁啊,也不知道是不是自己沒有找到好的方式去理解鏈表的基本操作博客,反正對于指針的概念總認為模模糊糊的。

慶哥: 指針確實是個值得研究的東西,這次我也不能花大篇幅去幫你說指針,這里咱們針對這個鏈表去把此處的指針給弄清楚就行了,我們先來看個圖:

在這里插入圖片描述

這個圖需要是非常明白的吧,這個圖中鏈表才是鏈表的真是樣子,不是這樣哦

在這里插入圖片描述

小白: 嗯嗯,單獨看你花的這個鏈表和我這個有點像啊

在這里插入圖片描述

慶哥: 確實這么,你畫的這個基本上可以說就是一個鏈表的樣子,但是我認為此處有個很重要的點需要畫下來,那就是鏈表中的每個結點不單單是一個數據,而是基本的比如兩個部分(這里暫時說的是單鏈表),一部分是實際存儲的數據,一部分則是next指針,也就是指向下一個數據結點的指針,所以,以下這個圖對理解鏈表比較重要:

在這里插入圖片描述

就是這個,也就是說在鏈表中啊,每個結點包含兩個別,就像上圖那樣,一個是data,一個next,data就相當于實際存儲的數據值,而next指針的,也是存儲的一個數值,這個數值是下一個數據的內存地址。

小白: 這個?有點不明白啊,data是保存的實際的數據值這個了解,不過針對這個next還是有點模糊啊。

慶哥: 嗯嗯,那好,我們今天來看這個圖:

在這里插入圖片描述

首先左邊的這個數據1知道是個啥吧,它就相當于一個鏈表中的一個節點,下面是一個完整的鏈表:

在這里插入圖片描述

很容易看起來,這樣的一個節點有兩個別組成,一個是data,一個next,那么,data是啥呢?next又是啥呢?首先你對這個圖了解嗎?

在這里插入圖片描述

小白: 這是個數據在內存中的存儲吧,有點模糊。

慶哥: 那我幫你大白話的講一下,首先嘞,這里有個內存,內存是啥,可以供我們存儲數據吧,那好,我們今天要存儲數據了,比如我們要存儲3個數據,現在還要向存儲申請三塊地方供我們存儲,于是內存給我們劃分了三塊地方,我們分別存上三個數據,就如上圖中這樣,分別存儲數據123,這個知道吧?

小白: 嗯嗯,你這說的太清楚,明白了。

慶哥: 那好,咱們繼續,現在你如果幫內存要了三塊地址,那么內存總得給這三塊地址編個號吧,畢竟這三塊地方被使用了,里面還保存著數據,假如有人要要很多數據的話,我好告訴它去哪兒找那些數據啊,于是乎,這三塊地方被編上號了,就是圖中的那種,這個明白吧

小白: 嗯嗯,原來是這樣回事啊,經過你這樣一講,我倒是明白的挺吶

慶哥: 嗯嗯,這里還必須進一步表明,我們之前不是說了嗎,鏈表中的一個數據結點包含兩個部分,一個data和一個next,比如我們要在數組中內存一個數值5,那么它就是這樣的:

在這里插入圖片描述

看到了沒,在申請的三塊地方,第一塊地方被命名成0x0000,這塊硬盤空間儲存的就是數據1,數據1嘞,其實分為兩部份,一部分存儲數值5,一部分則存儲next指針,也就是0x0001,這不就是第二塊內存空間的地址嘛,我們按照數據1中存儲的next指針也即是0x0001就可以找到第二塊內存空間,從而找到數據2啊。

咋樣,明白不?

小白: 這塊經你這么說,確實知道了這些,不過此處我如何感覺鏈表有點像函數啊,內存空間是連續分布的嗎?你看這0x0001,0x0002

慶哥: 確實,你這個難題問的很高,我們了解數組是根據排序排列的,在存儲中申請空間也有一整塊的,連續的,鏈表也有這種嗎?答案顯然是不鏈表的基本操作博客,其實,鏈表它的常態是這種的:

c語言程序設計 職工信息管理系統 鏈表_鏈表_鏈表的基本操作博客

在這里插入圖片描述

你看,跟后面的那種有哪些區別嗎?

小白: 嗯嗯,不一樣的就是內存中申請的內存空間不是連續的了,這個非常散,咦,不對啊,在里面那些連續的地方,數據1的next指針存放的是0x0001,指向的就是數據2,那么這次這樣不對吧

慶哥: 可以啊,看的挺仔細嘛,確實,這里的數據1的next指針存儲的空間地址就不是0x0001了,因為應指向數據2,那么數據1的next就必須存放的是數據2的內存地址,也就是0x0008,就是這樣:

在這里插入圖片描述

咋樣,這下清楚了吧?

小白: 嗯嗯,明白了,那鏈表和函數有啥差別呢?也就是說,我想知道的是鏈表有啥特點啊?

慶哥: 想知道鏈表和函數的區別是吧,那你明白數組有啥特點不?

小白: 數組啊,它非常顯著的特征不就是支持隨機讀取嗎,也就是讀取的強度相當高,因為可以使用下標來直接訪問,而且數組的存儲空間都是連續的,大概是這個樣子的:

在這里插入圖片描述

這里是一片內存空間,紅色的代表一個數組的空間地址分布,它都是連續的,占用一整塊的存儲空間。

慶哥: 可以啊,數組基本就是這樣的,不過關于數組后面我們單獨會進行分析,這里這樣的理解即將可以了,現在我們了解數組是這種的,那鏈表的,它是這種的:

在這里插入圖片描述

看見了吧,鏈表的分布式沒有順序的,非連續的,也就是隨心所欲,想在哪在哪,那如何找到下一個的,就是靠指針連接的。那根據這個圖,想一下,鏈表有啥特點嘞

小白: 想想啊,對于函數,內存分布式連續分布的,支持下標隨機寫入,如果要插入刪除的話,則必須進行數據移動啥的,所以針對數組吧,讀取效率高,但是插入刪除操作就不咋滴了,再看這個鏈表,因為內存分布不連續,想在那就在哪,只要有空地就可以用,那按照這種說,鏈表的插入刪除效率非常高啊

慶哥: 那是為何嘞?

小白: 我是這種想的,就例如鏈表的插入吧,就是新增加一個元素唄,就像那樣:

在這里插入圖片描述

就像那樣,中間那個深紅色的是新增加的,那么只應該把指針指向更改一下就ok啦

慶哥: 哈哈,說的挺正確啊,666啊,那鏈表的讀取嘞?

小白: 讀取嗎?這個?我想想啊,數組可以支持下標直接調用,那效率非常高,這個數組沒啥下標,那么只能是找到一個數據然后只能按照當前數據保存的下一個數據的指針找到下一個數據,其他的只是依次類推吧

慶哥: 嗯嗯,說的挺對的,所以說啊,對于鏈表來說,插入刪除這類操作非常迅速,但是讀取的話就不象數組那樣,只能一個一個的找啦

小白: 嗯嗯,那這就是我們所說的鏈表了嗎?

慶哥: 對,你這一問,我倒是要好好看看的了,上面我們討論的這些鏈表,就是這樣的:

在這里插入圖片描述

這個實際上叫做單鏈表,除了這個還有雙向鏈表,那雙向鏈表是啥嘞,你自己想猜一下,這個雙向鏈表是個啥?

小白: 單向鏈表,雙向鏈表?我想想,哦哦,是不是這樣啊,單向鏈表我們里面的圖顯示的是這些箭頭都朝一個方向,那上雙向鏈表是不是還有相反方向的箭頭呢?

就像這種:

在這里插入圖片描述

是不是這樣啊?

慶哥: 嗯嗯,理解的挺對,那你明白這箭頭都是啥嘛?

小白: 這個不就是代表指針指向嘛

c語言程序設計 職工信息管理系統 鏈表_鏈表的基本操作博客_鏈表

慶哥: 是的啊,那么你看我們之前的圖:

在這里插入圖片描述

這里我們之前說的,next指針存放的是下一個數據的存儲空間的地址,通過這個next可以找到下一個數據,那么你再看你畫的這個:

在這里插入圖片描述

有沒有發現問題,這樣的雙箭頭,next到底存的啥呢?存放的下一個數據的存儲空間地址嘛?那好,那由data指向next的既是咋回事呢?難道data中也存放空間地址嘛?不對吧,人家data存放的是實際數據啊。

小白: 你這么一說,好像是的啊,迷糊了

慶哥: 它似乎是這種的:

在這里插入圖片描述

看到了不,這里多了一個prev,這是啥呢?想一想

小白: 你這么一畫,我就知道這些了,這個next代表指向右邊的指針,那么這個prev是不是就是指向后面的指針啊

慶哥: 嗯嗯,是的,next和prev都是用來放置空間地址的,next就像我們之前說的存放的是后一個數據的存儲空間地址,而prev就是存放的前一個數據的內存空間地址。

小白: 哦哦,這也就是雙向鏈表啊,那么,這兩端的null是咋回事啊

慶哥: 這個啊,也簡單啊,你想啊,最前的哪個數據,他后面是不是沒有數據了,那prev不就是指向null了,那么最終的哪個數據同理啊

小白: 吆西,懂了懂了

慶哥: 那么你明白啥是循環鏈表嘛?

小白: 啥,還有循環鏈表,我想想啊,循環的話是不是頭尾相連啊,就像那樣:

在這里插入圖片描述

是不是?

慶哥: 可以的,完全正確。

小白: 感覺現在學到好多知識啊,那么鏈表就某些內容了嗎?

慶哥: 為了加深理解,我們再來看看鏈表的一些基本操作,首先嘞,我們來說說鏈表的查找操作,要知道這里的查找,其實就是查找某個節點,這里我們還拿單向鏈表來說吧,看后面的這個鏈表:

本文來自互聯網,由機器人自動采編,文章內容不代表本站觀點,請讀者自行辨別信息真偽,如有發現不適內容,請及時聯系站長處理。

相關閱讀
下载麻将游戏免费 广东十一选五助手软件手机版 彩票直通车苹果 最新广东好彩1开奖结果查询 新疆18选7走势图2元网 博彩网站 北单比分蛮高的 竞彩网首页 湖北快3走势图连线 天天乐棋牌游戏新手卡 皇冠篮球比分网