成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

03線性表之鏈表

jayce / 1693人閱讀

摘要：帶頭雙向循環(huán)鏈表結(jié)構(gòu)最復(fù)雜，一般用在多帶帶存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。

肚子餓了就要吃? ?~? ?嗝? ——— 路飛?

1.本章重點(diǎn)

  1. 鏈表表示和實(shí)現(xiàn)（單鏈表+雙鏈表）
  2. 鏈表的常見OJ題
  3. 順序表和鏈表的區(qū)別和聯(lián)系

2.為什么需要鏈表

引子：順序表的問(wèn)題及思考

(1)動(dòng)態(tài)順序表

特點(diǎn)：

  1. 插入數(shù)據(jù)，空間不夠了，需要增容。
  2. 要求數(shù)據(jù)是依次存儲(chǔ)的。

缺陷：

  1. 如果空間不夠，增容。增容會(huì)付出一定的性能消耗，需要申請(qǐng)新空間，拷貝數(shù)據(jù)，釋放舊空間。會(huì)有不小的消耗。
  2. 增容，可能存在增容后的空間有所浪費(fèi)。（? ?增容一般都是增容2倍? ）
  3. 頭部或者中部左右插入數(shù)據(jù)，要求依次移動(dòng)，插入效率低下。（? ?O(N)? ）

（2）如何解決：

  1. 按需求給空間（存一個(gè)給一個(gè)）。
  2. 不需要物理空間連續(xù)，頭部和中部的插入，不需要挪動(dòng)數(shù)據(jù)。

這就引出了一個(gè)新的物理存儲(chǔ)結(jié)構(gòu)? ? ————>? ?鏈表

3.鏈表的概念及結(jié)構(gòu)

概念：鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序實(shí)現(xiàn)的。

邏輯結(jié)構(gòu)（想象出來(lái)的），如圖：（單鏈表為例）

物理結(jié)構(gòu)（在內(nèi)存中的結(jié)構(gòu)），如圖：（單鏈表為例）

實(shí)際中要實(shí)現(xiàn)的鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來(lái)就有8種鏈表結(jié)構(gòu)：

  1. 單向，雙向
  2. 帶頭，不帶頭
  3. 循環(huán)，非循環(huán)

雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實(shí)際中最常用還是兩種結(jié)構(gòu)：

1. 無(wú)頭單向非循環(huán)鏈表：

結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)多帶帶用來(lái)存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

2. 帶頭雙向循環(huán)鏈表：

結(jié)構(gòu)最復(fù)雜，一般用在多帶帶存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來(lái)很多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡(jiǎn)單了，后面我們代碼實(shí)現(xiàn)了就知道了。

4.單鏈表的實(shí)現(xiàn)

注：

plist/phead——>頭指針（一般保持不動(dòng)）

cur——>當(dāng)前位置(? current簡(jiǎn)寫)

?

?

找尾巴注意的點(diǎn)：

對(duì)比

	//錯(cuò)誤代碼    //找到原來(lái)的尾巴（進(jìn)而插尾）	SLTNode* tail = phead;	while (tail != NULL)	{		tail = tail->next;	}
	//正確代碼    //找到原來(lái)的尾巴（進(jìn)而插尾）	SLTNode* tail = phead;	while (tail->next != NULL)	{		tail = tail->next;	}

解釋：

第一段代碼是錯(cuò)誤的，因?yàn)?/p>

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/119630.html

相關(guān)文章

  • 數(shù)據(jù)結(jié)構(gòu)與算法隨筆之鏈表-鏈表是否有環(huán)(二)

    摘要：初始化時(shí)指針走兩步，指針走一步，不停遍歷的變化最后快慢指針又相遇了，循環(huán)結(jié)束，代碼實(shí)現(xiàn)如下復(fù)雜度分析，假設(shè)鏈表長(zhǎng)度為時(shí)間復(fù)雜度，鏈表無(wú)環(huán)時(shí)，快指針會(huì)先到達(dá)尾部，時(shí)間就是如果有環(huán)，那么假設(shè)環(huán)部長(zhǎng)度為，時(shí)間就是，也就是空間復(fù)雜度 上一篇文章我們分析了下鏈表之反轉(zhuǎn)單向鏈表，這篇文章我們來(lái)分析下另外一個(gè)關(guān)于鏈表的經(jīng)典題目。 判斷鏈表是否有環(huán)(在leetcode上的題目地址：環(huán)形鏈表) 題目描述...

    molyzzx 評(píng)論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法的Python實(shí)現(xiàn)（二）——線性表之順序表

    摘要：文章首發(fā)于公眾號(hào)一件風(fēng)衣在編程中，我們常使用一組有順序的數(shù)據(jù)來(lái)表示某個(gè)有意義的數(shù)據(jù)，這種一組元素的序列的抽象，就是線性表，簡(jiǎn)稱表，是很多復(fù)雜數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)基礎(chǔ)，在中，和就可以看作是線性表的實(shí)現(xiàn)。 文章首發(fā)于公眾號(hào)一件風(fēng)衣（ID：yijianfengyi） 在編程中，我們常使用一組有順序的數(shù)據(jù)來(lái)表示某個(gè)有意義的數(shù)據(jù)，這種一組元素的序列的抽象，就是線性表，簡(jiǎn)稱表，是很多復(fù)雜數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)基...

    TerryCai 評(píng)論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)之線性表

    摘要：線性表是最基本的數(shù)據(jù)結(jié)構(gòu)之一，在實(shí)際程序中應(yīng)用非常廣泛，它還經(jīng)常被用作更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)基礎(chǔ)。鏈表之單鏈表線性表的定義，它是一些元素的序列，維持著元素之間的一種線性關(guān)系。 線性表學(xué)習(xí)筆記，python語(yǔ)言描述-2019-1-14 線性表簡(jiǎn)介 在程序中，經(jīng)常需要將一組（通常是同為某個(gè)類型的）數(shù)據(jù)元素作為整體管理和使用，需要?jiǎng)?chuàng)建這種元素組，用變量記錄它們，傳進(jìn)傳出函數(shù)等。一組數(shù)據(jù)中包含...

    leoperfect 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<