這周開(kāi)始自學(xué)數(shù)據(jù)結(jié)構(gòu)與算法露乏，在B站看了些視頻也有了一個(gè)初步的了解，由于是初學(xué)涂邀，一些概念還是記清楚點(diǎn)比較好瘟仿，這篇博客就按我的學(xué)習(xí)順序來(lái)總結(jié)一下本周學(xué)習(xí)內(nèi)容。

初入門(mén)

一比勉、基礎(chǔ)定義

數(shù)據(jù)結(jié)構(gòu)：

數(shù)據(jù)結(jié)構(gòu)(data structure)是帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的集合劳较，它研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)以及它們之間的相互關(guān)系驹止，并對(duì)這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法观蜗，并確保經(jīng)過(guò)這些運(yùn)算以后所得到的新結(jié)構(gòu)仍保持原來(lái)的結(jié)構(gòu)類(lèi)型臊恋。簡(jiǎn)而言之，數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合墓捻，即帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合抖仅。“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系砖第，分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)撤卢。

數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的兩個(gè)密切相關(guān)的方面，同一邏輯結(jié)構(gòu)可以對(duì)應(yīng)不同的存儲(chǔ)結(jié)構(gòu)梧兼。算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)放吩，而算法的實(shí)現(xiàn)依賴(lài)于指定的存儲(chǔ)結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容是構(gòu)造復(fù)雜軟件系統(tǒng)的基礎(chǔ)羽杰，它的核心技術(shù)是分解與抽象渡紫。通過(guò)分解可以劃分出數(shù)據(jù)的3個(gè)層次；再通過(guò)抽象忽洛，舍棄數(shù)據(jù)元素的具體內(nèi)容，就得到邏輯結(jié)構(gòu)环肘。類(lèi)似地欲虚，通過(guò)分解將處理要求劃分成各種功能，再通過(guò)抽象舍棄實(shí)現(xiàn)細(xì)節(jié)悔雹，就得到運(yùn)算的定義复哆。上述兩個(gè)方面的結(jié)合可以將問(wèn)題變換為數(shù)據(jù)結(jié)構(gòu)。這是一個(gè)從具體（即具體問(wèn)題）到抽象（即數(shù)據(jù)結(jié)構(gòu)）的過(guò)程腌零。然后梯找，通過(guò)增加對(duì)實(shí)現(xiàn)細(xì)節(jié)的考慮進(jìn)一步得到存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)運(yùn)算，從而完成設(shè)計(jì)任務(wù)益涧。這是一個(gè)從抽象（即數(shù)據(jù)結(jié)構(gòu)）到具體（即具體實(shí)現(xiàn)）的過(guò)程锈锤。?

數(shù)據(jù)的邏輯結(jié)構(gòu)

指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)闲询，其中的邏輯關(guān)系是指數(shù)據(jù)元素之間的前后間關(guān)系扭弧，而與他們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)阎姥。邏輯結(jié)構(gòu)包括：

1.集合：數(shù)據(jù)結(jié)構(gòu)中的元素之間除了“同屬一個(gè)集合” 的相互關(guān)系外，別無(wú)其他關(guān)系呼巴；

2.線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)一的相互關(guān)系；

3.樹(shù)形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)多的相互關(guān)系衣赶；

4.圖形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對(duì)多的相互關(guān)系诊赊。

數(shù)據(jù)的邏輯結(jié)構(gòu)

指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)屑埋，其中的邏輯關(guān)系是指數(shù)據(jù)元素之間的前后間關(guān)系摘能，而與他們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)。邏輯結(jié)構(gòu)包括：

1.集合：數(shù)據(jù)結(jié)構(gòu)中的元素之間除了“同屬一個(gè)集合” 的相互關(guān)系外严望，別無(wú)其他關(guān)系逻恐；

2.線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)一的相互關(guān)系复隆；

3.樹(shù)形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)多的相互關(guān)系；

4.圖形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對(duì)多的相互關(guān)系惭每。

數(shù)據(jù)的物理結(jié)構(gòu)

指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的存放形式台腥。

數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱(chēng)映像）黎侈，它包括數(shù)據(jù)元素的機(jī)內(nèi)表示和關(guān)系的機(jī)內(nèi)表示闷游。由于具體實(shí)現(xiàn)的方法有順序峻汉、鏈接脐往、索引钙勃、散列等多種辖源，所以希太，一種數(shù)據(jù)結(jié)構(gòu)可表示成一種或多種存儲(chǔ)結(jié)構(gòu)誊辉。

數(shù)據(jù)元素的機(jī)內(nèi)表示（映像方法）： 用二進(jìn)制位（bit）的位串表示數(shù)據(jù)元素堕澄。通常稱(chēng)這種位串為節(jié)點(diǎn)（node）霉咨。當(dāng)數(shù)據(jù)元素有若干個(gè)數(shù)據(jù)項(xiàng)組成時(shí)途戒，位串中與個(gè)數(shù)據(jù)項(xiàng)對(duì)應(yīng)的子位串稱(chēng)為數(shù)據(jù)域（data field）喷斋。因此，節(jié)點(diǎn)是數(shù)據(jù)元素的機(jī)內(nèi)表示（或機(jī)內(nèi)映像）浆西。

關(guān)系的機(jī)內(nèi)表示（映像方法）：數(shù)據(jù)元素之間的關(guān)系的機(jī)內(nèi)表示可以分為順序映像和非順序映像近零，常用兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)秒赤。順序映像借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系憎瘸。非順序映像借助指示元素存儲(chǔ)位置的指針（pointer）來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系幌甘。?

數(shù)據(jù)結(jié)構(gòu)有很多種锅风，一般來(lái)說(shuō)鞍泉，按照數(shù)據(jù)的邏輯結(jié)構(gòu)對(duì)其進(jìn)行簡(jiǎn)單的分類(lèi)咖驮，包括線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類(lèi)。

線性結(jié)構(gòu)

簡(jiǎn)單地說(shuō)恒界，線性結(jié)構(gòu)就是表中各個(gè)結(jié)點(diǎn)具有線性關(guān)系砚嘴。如果從數(shù)據(jù)結(jié)構(gòu)的語(yǔ)言來(lái)描述际长，線性結(jié)構(gòu)應(yīng)該包括如下幾點(diǎn)：

1也颤、線性結(jié)構(gòu)是非空集翅娶。?

2、線性結(jié)構(gòu)有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)燥翅。?

3森书、線性結(jié)構(gòu)所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn)凛膏。?

線性表就是典型的線性結(jié)構(gòu)脏榆，還有棧须喂、隊(duì)列和串等都屬于線性結(jié)構(gòu)坞生。?

非線性結(jié)構(gòu)

簡(jiǎn)單地說(shuō)，非線性結(jié)構(gòu)就是表中各個(gè)結(jié)點(diǎn)之間具有多個(gè)對(duì)應(yīng)關(guān)系又兵。如果從數(shù)據(jù)結(jié)構(gòu)的語(yǔ)言來(lái)描述，非線性結(jié)構(gòu)應(yīng)該包括如下幾點(diǎn)：?

1屯远、非線性結(jié)構(gòu)是非空集盲再。?

2螺男、非線性結(jié)構(gòu)的一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨結(jié)點(diǎn)和多個(gè)直接后繼結(jié)點(diǎn)页屠。

在實(shí)際應(yīng)用中，數(shù)組辰企、廣義表、樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)等數(shù)據(jù)結(jié)構(gòu)都屬于非線性結(jié)構(gòu)竹观。

常用的數(shù)據(jù)結(jié)構(gòu)

在計(jì)算機(jī)科學(xué)的發(fā)展過(guò)程中潜索，數(shù)據(jù)結(jié)構(gòu)也隨之發(fā)展。程序設(shè)計(jì)中常用的數(shù)據(jù)結(jié)構(gòu)包括如下幾個(gè)竹习。?

數(shù)組(Array)

數(shù)組是一種聚合數(shù)據(jù)類(lèi)型整陌，它是將具有相同類(lèi)型的若干變量有序地組織在一起的集合。數(shù)組可以說(shuō)是最基本的數(shù)據(jù)結(jié)構(gòu)随夸，在各種編程語(yǔ)言中都有對(duì)應(yīng)宾毒。一個(gè)數(shù)組可以分解為多個(gè)數(shù)組元素伍俘，按照數(shù)據(jù)元素的類(lèi)型勉躺，數(shù)組可以分為整型數(shù)組饵溅、字符型數(shù)組蜕企、浮點(diǎn)型數(shù)組轻掩、指針數(shù)組和結(jié)構(gòu)數(shù)組等。數(shù)組還可以有一維罕扎、二維以及多維等表現(xiàn)形式腔召。?

棧( Stack)

棧是一種特殊的線性表臀蛛，它只能在一個(gè)表的一個(gè)固定端進(jìn)行數(shù)據(jù)結(jié)點(diǎn)的插入和刪除操作浊仆。棧按照后進(jìn)先出的原則來(lái)存儲(chǔ)數(shù)據(jù)豫领，也就是說(shuō)氏堤，先插入的數(shù)據(jù)將被壓入棧底鼠锈，最后插入的數(shù)據(jù)在棧頂购笆，讀出數(shù)據(jù)時(shí)，從棧頂開(kāi)始逐個(gè)讀出样傍。棧在匯編語(yǔ)言程序中衫哥，經(jīng)常用于重要數(shù)據(jù)的現(xiàn)場(chǎng)保護(hù)撤逢。棧中沒(méi)有數(shù)據(jù)時(shí)蚊荣，稱(chēng)為空棧互例。

隊(duì)列(Queue)

隊(duì)列和棧類(lèi)似，也是一種特殊的線性表俊马。和棧不同的是柴我，隊(duì)列只允許在表的一端進(jìn)行插入操作艘儒，而在另一端進(jìn)行刪除操作界睁。一般來(lái)說(shuō)翻斟，進(jìn)行插入操作的一端稱(chēng)為隊(duì)尾访惜，進(jìn)行刪除操作的一端稱(chēng)為隊(duì)頭腻扇。隊(duì)列中沒(méi)有元素時(shí)幼苛，稱(chēng)為空隊(duì)列舶沿。?

鏈表( Linked List)

鏈表是一種數(shù)據(jù)元素按照鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)括荡，這種存儲(chǔ)結(jié)構(gòu)具有在物理上存在非連續(xù)的特點(diǎn)一汽。鏈表由一系列數(shù)據(jù)結(jié)點(diǎn)構(gòu)成，每個(gè)數(shù)據(jù)結(jié)點(diǎn)包括數(shù)據(jù)域和指針域兩部分召夹。其中监憎，指針域保存了數(shù)據(jù)結(jié)構(gòu)中下一個(gè)元素存放的地址鲸阔。鏈表結(jié)構(gòu)中數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序來(lái)實(shí)現(xiàn)的褐筛。

樹(shù)( Tree)

樹(shù)是典型的非線性結(jié)構(gòu)渔扎，它是包括晃痴，2個(gè)結(jié)點(diǎn)的有窮集合K倘核。在樹(shù)結(jié)構(gòu)中紧唱，有且僅有一個(gè)根結(jié)點(diǎn)漏益，該結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。在樹(shù)結(jié)構(gòu)中的其他結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)宁仔，而且可以有兩個(gè)后繼結(jié)點(diǎn)翎苫，m≥0煎谍。

圖(Graph)

圖是另一種非線性數(shù)據(jù)結(jié)構(gòu)呐粘。在圖結(jié)構(gòu)中作岖，數(shù)據(jù)結(jié)點(diǎn)一般稱(chēng)為頂點(diǎn)痘儡，而邊是頂點(diǎn)的有序偶對(duì)沉删。如果兩個(gè)頂點(diǎn)之間存在一條邊矾瑰，那么就表示這兩個(gè)頂點(diǎn)具有相鄰關(guān)系殴穴。

堆(Heap)

堆是一種特殊的樹(shù)形數(shù)據(jù)結(jié)構(gòu)推正，一般討論的堆都是二叉堆植榕。堆的特點(diǎn)是根結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中最小的或者最大的尊残，并且根結(jié)點(diǎn)的兩個(gè)子樹(shù)也是一個(gè)堆結(jié)構(gòu)寝衫。

散列表(Hash)

散列表源自于散列函數(shù)(Hash function)慰毅，其思想是如果在結(jié)構(gòu)中存在關(guān)鍵字和T相等的記錄汹胃，那么必定在F(T)的存儲(chǔ)位置可以找到該記錄着饥，這樣就可以不用進(jìn)行比較操作而直接取得所查記錄宰掉。?

算法定義：

算法是解決特定問(wèn)題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列拒炎，并且每條指令表示一個(gè)或多個(gè)操作枝冀，每一個(gè)操作都有特定的功能

算法的基本特點(diǎn)：

（1）輸入輸出：算法具有0個(gè)或多個(gè)輸入，至少有一個(gè)或多個(gè)輸出谷誓；

（2）有窮性：指算法在執(zhí)行有限的步驟之后捍歪，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無(wú)限循環(huán)糙臼，并且每一個(gè)步驟在可接受的時(shí)間內(nèi)完成变逃；

（3）確定性：算法的每一步驟都具有確定的含義揽乱，不會(huì)出現(xiàn)二義性凰棉。

（4）可行性：算法的每一步都必須是可行的撒犀，也就是說(shuō)绘证，每一步都能夠通過(guò)執(zhí)行有限次數(shù)完成嚷那；

算法設(shè)計(jì)要求：

（1）正確性：算法的正確性是指算法至少應(yīng)該具有輸入魏宽、輸出和加工處理無(wú)歧義性队询、能正確反映問(wèn)題的需求蚌斩、能夠得到問(wèn)題的正確答案送膳；

（2）可讀性：算法設(shè)計(jì)的另一目的是為了便于閱讀叠聋、理解和交流

（3）健壯性：當(dāng)輸入數(shù)據(jù)不合法時(shí)虏束，算法也能做出相關(guān)處理镇匀，而不是產(chǎn)生異惩嗫校或莫名其妙的結(jié)果汗侵；

（4）時(shí)間效率高存儲(chǔ)量低：時(shí)間效率指的是算法的執(zhí)行時(shí)間，對(duì)于同一個(gè)問(wèn)題囊骤，如果有多個(gè)算法能夠解決晃择，執(zhí)行時(shí)間短的算法效率高，執(zhí)行時(shí)間長(zhǎng)的效率低也物。存儲(chǔ)量需求指的是算法在執(zhí)行過(guò)程中需要的最大存儲(chǔ)空間宫屠，主要指算法程序運(yùn)行時(shí)所占用的內(nèi)存或外部硬盤(pán)存儲(chǔ)空間滑蚯。設(shè)計(jì)算法應(yīng)該盡量滿(mǎn)足時(shí)間效率高和存儲(chǔ)量低的需求浪蹂。

常用算法

數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容：就是如何按一定的邏輯結(jié)構(gòu)，把數(shù)據(jù)組織起來(lái)告材，并選擇適當(dāng)?shù)拇鎯?chǔ)表示方法把邏輯結(jié)構(gòu)組織好的數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)的存儲(chǔ)器里坤次。研究的目的是為了更有效的處理數(shù)據(jù)，提高數(shù)據(jù)運(yùn)算效率斥赋。數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上缰猴，但運(yùn)算的具體實(shí)現(xiàn)要在存儲(chǔ)結(jié)構(gòu)上進(jìn)行。一般有以下幾種常用運(yùn)算：?

(1)檢索疤剑。檢索就是在數(shù)據(jù)結(jié)構(gòu)里查找滿(mǎn)足一定條件的節(jié)點(diǎn)滑绒。一般是給定一個(gè)某字段的值闷堡，找具有該字段值的節(jié)點(diǎn)。?

(2)插入疑故。往數(shù)據(jù)結(jié)構(gòu)中增加新的節(jié)點(diǎn)杠览。?

(3)刪除。把指定的結(jié)點(diǎn)從數(shù)據(jù)結(jié)構(gòu)中去掉纵势。?

(4)更新踱阿。改變指定節(jié)點(diǎn)的一個(gè)或多個(gè)字段的值。

(5)排序钦铁。把節(jié)點(diǎn)按某種指定的順序重新排列软舌。例如遞增或遞減。?

以上是我覺(jué)得入門(mén)數(shù)據(jù)結(jié)構(gòu)和算法需要了解的東西Ｓ稀：丁栽烂！

時(shí)間復(fù)雜度和空間復(fù)雜度

時(shí)間復(fù)雜度

（1）時(shí)間頻度

一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間躏仇，從理論上是不能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道腺办。但我們不可能也沒(méi)有必要對(duì)每個(gè)算法都上機(jī)測(cè)試焰手，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了怀喉。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例书妻，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多躬拢。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱(chēng)為語(yǔ)句頻度或時(shí)間頻度躲履。記為T(mén)(n)。算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量聊闯。

（2）時(shí)間復(fù)雜度

在剛才提到的時(shí)間頻度中工猜，n稱(chēng)為問(wèn)題的規(guī)模，當(dāng)n不斷變化時(shí)菱蔬，時(shí)間頻度T(n)也會(huì)不斷變化篷帅。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律。為此拴泌，我們引入時(shí)間復(fù)雜度概念魏身。

一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)蚪腐，用T(n)表示箭昵，若有某個(gè)輔助函數(shù)f(n),存在一個(gè)正常數(shù)c使得fn*c>=T(n)恒成立。記作T(n)=O(f(n)),稱(chēng)O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度回季，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度家制。

在各種不同算法中掉房，若算法中語(yǔ)句執(zhí)行次數(shù)為一個(gè)常數(shù)，則時(shí)間復(fù)雜度為O(1),另外慰丛，在時(shí)間頻度不相同時(shí)卓囚，時(shí)間復(fù)雜度有可能相同，如T(n)=n^2+3n+4與T(n)=4n^2+2n+1它們的頻度不同诅病，但時(shí)間復(fù)雜度相同哪亿，都為O(n^2)。

按數(shù)量級(jí)遞增排列贤笆，常見(jiàn)的時(shí)間復(fù)雜度有：

常數(shù)階O(1),對(duì)數(shù)階O(log2n)(以2為底n的對(duì)數(shù)蝇棉，下同),線性階O(n),

線性對(duì)數(shù)階O(nlog2n),平方階O(n^2)，立方階O(n^3),...芥永，

k次方階O(n^k),指數(shù)階O(2^n)篡殷。隨著問(wèn)題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大埋涧，算法的執(zhí)行效率越低板辽。

這是我截取的視頻中的常見(jiàn)時(shí)間復(fù)雜度表:

空間復(fù)雜度

與時(shí)間復(fù)雜度類(lèi)似，空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量棘催。記作:

S(n)=O(f(n))

算法執(zhí)行期間所需要的存儲(chǔ)空間包括3個(gè)部分：

算法程序所占的空間劲弦；

輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間；

算法執(zhí)行過(guò)程中所需要的額外空間醇坝。

在許多實(shí)際問(wèn)題中画畅，為了減少算法所占的存儲(chǔ)空間乡革，通常采用壓縮存儲(chǔ)技術(shù)。

線性表

一、順序表（數(shù)組）

1. 性質(zhì)：①?隨機(jī)訪問(wèn)（查找快，直接定位） ② 存儲(chǔ)密度高坚踩，只存儲(chǔ)數(shù)據(jù)元素 ③ 插入嗓节、刪除操作需要大量移動(dòng)元素( 插入平均移動(dòng)? n/2 個(gè)元素信姓，刪除平均移動(dòng) (n-1)/2 個(gè)元素 )

2. 順序表的插入：時(shí)間復(fù)雜度：O(n) ; 空間復(fù)雜度：O(1)

//先判斷插入是否合法（省略）for(inti=L.length;i>=pos;i--)//pos為插入位置从诲，數(shù)組下表從0開(kāi)始L.data[i]=L.data[i-1];L.data[i-1]=e;//e為插入元素L.length++;//線性表長(zhǎng)度加1

3. 順序表的刪除：時(shí)間復(fù)雜度：O(n) ; 空間復(fù)雜度：O(1)

//先判斷刪除是否合法（省略）for(inti=pos;i<L.length;i++)//pos為刪除位置定页，數(shù)組下表從0開(kāi)始L.data[i-1]=L.data[i];L.length--;//線性表長(zhǎng)度減1

4. 順序表的訪問(wèn)：時(shí)間復(fù)雜度：O(1) （基于隨機(jī)訪問(wèn)）

5. 順序表的遍歷和交換太簡(jiǎn)單了恩够，估計(jì)看完一遍書(shū)絕大部分的人都會(huì)吧

6. 算法分析（以后會(huì)開(kāi)一個(gè)專(zhuān)題說(shuō)的，現(xiàn)在這個(gè)階段先把基礎(chǔ)打好，有能力的同學(xué)可以試試寫(xiě)一寫(xiě)數(shù)組逆置； 用O(n)的方法刪除數(shù)組中不等于5的元素附井； 歸并操作卷雕； 二分查找）這些后面都會(huì)說(shuō)的

二、鏈表

1. 單鏈表

性質(zhì)： 非隨機(jī)存儲(chǔ)（查找要逐個(gè)遍歷）太雨，所以查找比較慢 、插入刪除操作快（已經(jīng)找到了位置的前提下）

①頭指針指向鏈表的第一個(gè)結(jié)點(diǎn)魁蒜，頭結(jié)點(diǎn)的帶頭結(jié)點(diǎn)鏈表的第一個(gè)結(jié)點(diǎn)（通常不存儲(chǔ)信息）锥咸。

PS：為什么要設(shè)立頭結(jié)點(diǎn)？ 可以對(duì)鏈表統(tǒng)一操作，邊界操作統(tǒng)一

有頭結(jié)點(diǎn)：第一個(gè)有效數(shù)據(jù)的地址為 L->next

無(wú)頭結(jié)點(diǎn)：第一個(gè)有效數(shù)據(jù)的地址 L

②建立：頭插法、尾插法（設(shè)一個(gè)指向表尾的結(jié)點(diǎn)指針rear）

③插入： O（n） 如下圖理解

在第i個(gè)位置 插入

p=GetElem(L,i-1);//時(shí)間復(fù)雜度O(n)s->next=p->next;//①? 注意①②順序不能換峡迷，假如交換了就斷鏈了银伟，i-1就找不到原來(lái)i了p->next=s;//② （注意，單單只是將這個(gè)插入操作有時(shí)候只強(qiáng)調(diào)插入绘搞，即后兩行代碼彤避，為O(1)）

注意一個(gè)小細(xì)節(jié)，我的圖跟書(shū)上的不一樣夯辖，我的 “→”箭頭的起始端是跟“圓圈”連起來(lái)的琉预，其實(shí)“→”就是next域，“圓圈”就是data域蒿褂，連起來(lái)才是一個(gè)結(jié)構(gòu)體圆米。而書(shū)上的箭頭跟圓圈是分開(kāi)的，我覺(jué)得這樣不助于我們學(xué)生理解贮缅。以后我都用下面的寫(xiě)法來(lái)畫(huà)結(jié)點(diǎn)這樣才能完整的保留結(jié)點(diǎn)的存儲(chǔ)特性榨咐。

書(shū)上的寫(xiě)法

有助于理解的寫(xiě)法

④刪除：?O（n） 如下圖理解

刪除 第i個(gè)元素

p = GetElem(L, i-1);? ? //時(shí)間復(fù)雜度O(n) 后面的操作為O(1)

q = p->next;

p->next = q->next;

free(q);

問(wèn)：帶有尾指針的單鏈表，在表尾插入一個(gè)元素的時(shí)間復(fù)雜度是O（1）谴供，但是刪除表尾的元素時(shí)間復(fù)雜度是O(n)。 大家可以思考一下為什么齿坷？

答：

不知道大家發(fā)現(xiàn)沒(méi)有桂肌，插入（刪除）操作，都是要找到插入（刪除）元素之前的一個(gè)元素永淌，我們上面是用“p”來(lái)指向的崎场，都是通過(guò)這個(gè)“p”來(lái)完成后續(xù)操作的。

在帶有尾指針rear的鏈表,插入直接用 rear->next = s 就可以了遂蛀，因?yàn)閞ear正是待插入結(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)谭跨。

而刪除表尾元素，就要找到rear的前驅(qū)結(jié)點(diǎn)，由于單鏈表所以要進(jìn)行一次遍歷螃宙，找到rear的前驅(qū)結(jié)點(diǎn)蛮瞄，再進(jìn)行刪除操作。

PS:大家知道為什么要設(shè)立head頭結(jié)點(diǎn)這么一說(shuō)了吧谆扎，正是因?yàn)橛辛薶ead結(jié)點(diǎn)這一個(gè)前驅(qū)結(jié)點(diǎn)挂捅，插入(刪除)操作才會(huì)統(tǒng)一。（鏈表為空的插入堂湖，鏈表還剩下一個(gè)的時(shí)候刪除）

總之闲先，在單鏈表的操作中，大家一定要重視待插入（刪除）的前驅(qū)結(jié)點(diǎn)的學(xué)習(xí)无蜂。上面總結(jié)出來(lái)的大家一定要好好理解伺糠。

2. 雙鏈表：在單鏈表的基礎(chǔ)上，結(jié)構(gòu)體增加一個(gè)指向前驅(qū)結(jié)點(diǎn)的prior的指針

3. 循環(huán)單鏈表：在單鏈表的基礎(chǔ)上斥季，在表尾的next指向表頭 r->next = L;

4. 循環(huán)雙鏈表：在循環(huán)單鏈表基礎(chǔ)上退盯，結(jié)構(gòu)體增加一個(gè)指向前驅(qū)結(jié)點(diǎn)的prior的指針，加上L->prior = r泻肯；r->next = L;

5. 靜態(tài)鏈表：用連續(xù)的塊內(nèi)存空間當(dāng)鏈表使用（跟操作系統(tǒng)中文件管理中的文件分配方式的顯示鏈接一樣）

以上說(shuō)的都離不開(kāi)單鏈表的基本操作渊迁，只要把單鏈表理解透徹，這些都是小Case灶挟。

我覺(jué)得一個(gè)適合自己的筆記琉朽，不是什么都寫(xiě)的非常詳細(xì)，只是讓自己有個(gè)索引稚铣，具體的書(shū)都是很清楚的箱叁，我就沒(méi)有必要在做了重復(fù)了，免得話(huà)就跟抄書(shū)沒(méi)有什么區(qū)別了惕医。

三耕漱、順序表與鏈表的選用：

通常比較穩(wěn)定的線性表，用順序存儲(chǔ)抬伺。（靜態(tài)）

頻繁做插入螟够、刪除操作的線性表，用鏈?zhǔn)酱鎯?chǔ)（動(dòng)態(tài)）

訪問(wèn)查找比較多的 —— 順序表

插入峡钓、刪除比較多的妓笙，要求占空間小 —— 鏈表