資訊專欄INFORMATION COLUMN
摘要：線性表的基本運(yùn)算置空表，構(gòu)造一個空的線性表。三線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)單鏈表線性鏈表鏈?zhǔn)酱鎯Y(jié)構(gòu)除了存儲本身的信息之外，還需要一個存儲指示其后繼元素存儲位置的指針，由這兩個部分組成元素的存儲映像通常稱為結(jié)點(diǎn)。用這種方法存儲的線性表稱為鏈表。
目錄
? ? ? ?今天我們來學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的第2章——線性表。線性表是最簡單和最常用的一種數(shù)據(jù)結(jié)構(gòu)，所以這一章是數(shù)據(jù)結(jié)構(gòu)當(dāng)中的重點(diǎn)內(nèi)容，小伙伴們一定要熟練掌握！本文主要介紹基本概念，算法和代碼實(shí)現(xiàn)不過多贅述。
? ? 1）線性表的定義
? ? ? ? 線性表是由??個數(shù)據(jù)元素（結(jié)點(diǎn)）?組成的有限序列。其中，數(shù)據(jù)元素的個數(shù)??為表的長度。當(dāng)??為零時稱為空表。
? ? 2）線性表的邏輯特征
????????對于一個非空的線性表：
????????① 有且僅有一個稱為開始元素的?，它沒有前趨，僅有一個直接后繼?；
????????② 有且僅有一個稱為終端元素的?，它沒有后繼，僅有一個直接前趨；
????????③ 其余元素?稱為內(nèi)部元素，它們都有且僅有一個直接前趨??和一個直接后繼?。
（1）置空表 InitList(L)，構(gòu)造一個空的線性表 L。
（2）求表長 ListLength(L)，返回線性表 L 中元素個數(shù)，即表長。
（3）取表中第??個元素 GetNode(L，i)，若1ListLength(L)，則返回第??個元素?。
（4）按值查找 LocateNode(L，x)，在表 L 中查找第一個值為??的元素，并返回該元素在表 L 中的位置，若表中沒有元素的值為?，則返回 0 值。
（5）插入InsertList(L，i，x)，在表 L 的第??個元素之前插入一個值為??的新元素，表 L 的長度加1。
（6）刪除DeleteList(L，i)，刪除表 L 的第??個元素，表 L 的長度減1。
???????線性表的順序存儲指的是將線性表的數(shù)據(jù)元素按其邏輯次序依次存入一組地址連續(xù)的存儲單元里，用這種方法存儲的線性表稱為順序表。順序表是一種隨機(jī)存取結(jié)構(gòu)。
? ? 1）插入運(yùn)算
? ? ? ? 線性表的插入運(yùn)算是指在線性表的第?-1 個元素和第??個元素之間插入一個新元素?，使長度為??的線性表：
()
????????變?yōu)殚L度為?+1 的線性表：
()
? ? ? ? ！插入是向后移動元素。
? ? 2）刪除運(yùn)算
???????線性表的刪除運(yùn)算是指將表中第??個元素刪除，使長度為??的線性表
()
變?yōu)殚L度為?-1 的線性表：
()
????????！刪除是向前移動元素。
???????鏈?zhǔn)酱鎯Y(jié)構(gòu)除了存儲??本身的信息之外，還需要一個存儲指示其后繼元素??存儲位置的指針，由這兩個部分組成元素??的存儲映像通常稱為結(jié)點(diǎn)。它包括兩個域：存儲數(shù)據(jù)元素的域稱為數(shù)據(jù)域，存儲直接后繼存儲地址的域稱為指針域。用這種方法存儲的線性表稱為鏈表。
????????個結(jié)點(diǎn)鏈成一個鏈表，即為線性表（）的鏈?zhǔn)酱鎯Y(jié)構(gòu)。由于這種鏈表的每個結(jié)點(diǎn)只包含一個指針域，因此又稱為單鏈表。
? ? 1）建立單鏈表
???????建立單鏈表的常用方法有兩種：頭插法和尾插法。
???????① 頭插法建表
???????頭插法建表是從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入的數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。
???????② 尾插法建表
???????尾插法是將新結(jié)點(diǎn)插入在當(dāng)前鏈表的表尾上，因此需要增設(shè)一個尾指針 rear，使其始終指向鏈表的尾結(jié)點(diǎn)。
? ? 2）查找運(yùn)算（帶頭結(jié)點(diǎn)）
???????①?按結(jié)點(diǎn)序號查找
? ? ? ?在單鏈表中要查找第??個結(jié)點(diǎn)，就必須從鏈表的第1個結(jié)點(diǎn)（開始結(jié)點(diǎn)，序號為1）開始，序號為 0 的是頭結(jié)點(diǎn)，p 指向當(dāng)前結(jié)點(diǎn)，j 為計數(shù)器，其初始值為1，當(dāng) p 掃描下一個結(jié)點(diǎn)時，計數(shù)器加1。當(dāng) j=?時，指針 p 所指向的結(jié)點(diǎn)就是要找的結(jié)點(diǎn)。
???????② 按結(jié)點(diǎn)值查找
???????在單鏈表中按值查找結(jié)點(diǎn)，就是從鏈表的開始結(jié)點(diǎn)出發(fā)，順鏈逐個將結(jié)點(diǎn)的值和給定值 k 進(jìn)行比較，若遇到相等的值，則返回該結(jié)點(diǎn)的存儲位置，否則返回 NULL。
? ? 3）插入運(yùn)算
???????鏈表插入時不需要移動結(jié)點(diǎn)，但需要用移動指針來進(jìn)行位置查找。
? ? 4）刪除運(yùn)算?
???????鏈表刪除和插入同理，不需要移動結(jié)點(diǎn)，但需要移動指針。
???????循環(huán)鏈表的特點(diǎn)是單鏈表中最后一個結(jié)點(diǎn)（終端結(jié)點(diǎn)）的指針域不為空，而是指向鏈表的頭結(jié)點(diǎn)，使整個鏈表構(gòu)成一個環(huán)。
???????雙向鏈表的特點(diǎn)是在單鏈表的結(jié)點(diǎn)類型中增加一個指向其直接前趨的指針域。這樣形成的鏈表中就有兩條不同方向的鏈。因此稱之為雙向鏈表。
???????順序表可以隨機(jī)存取表中任一元素，插入和刪除操作時需移動大量元素。鏈表插入和刪除不用大量移動元素，但失去了隨機(jī)訪問的特點(diǎn)。
???????順序表查詢快，增刪慢；鏈表查詢慢，增刪快。
???????在實(shí)際問題中，若經(jīng)常對線性表進(jìn)行查找操作，則以順序表存儲為宜。若經(jīng)常對線性表進(jìn)行插入和刪除操作，則以鏈表存儲為宜。
???????順序表的存儲空間是靜態(tài)分配的，設(shè)置過大將產(chǎn)生空間浪費(fèi)，設(shè)置過小會使空間溢出，因此順序存儲結(jié)構(gòu)適合對數(shù)據(jù)量大小能事先知道的應(yīng)用問題。
???????而鏈表的存儲空間是動態(tài)分配的，只要內(nèi)存有空閑空間，就不會產(chǎn)生溢出，因此鏈?zhǔn)酱鎯Y(jié)構(gòu)適合數(shù)據(jù)量變化較大的動態(tài)問題。
ps：博主創(chuàng)作不易，如果喜歡就點(diǎn)個贊吧！?( ′???` )比心
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/122177.html
新編html網(wǎng)頁設(shè)計從入門到精通共分為21章，全面系統(tǒng)地講解了html的發(fā)展歷史及4.0版的新特性、基本概念、設(shè)計原則、文件結(jié)構(gòu)、文件屬性標(biāo)記、用格式標(biāo)記進(jìn)行頁面排版、使用圖像裝飾頁面、超鏈接的使用、使用表格組織頁面、使用多媒體美化頁面、創(chuàng)建多框架頁面、動態(tài)網(wǎng)頁的制作、使用層疊樣式表(css)美化頁面、javascript語言、數(shù)組和字符串以及表達(dá)式與程序的流程控制等內(nèi)容。 本書適合作為培訓(xùn)學(xué)校的...
摘要：貢獻(xiàn)者飛龍版本最近總是有人問我，把這些資料看完一遍要用多長時間，如果你一本書一本書看的話，的確要用很長時間。為了方便大家，我就把每本書的章節(jié)拆開，再按照知識點(diǎn)合并，手動整理了這個知識樹。 Special Sponsors showImg(https://segmentfault.com/img/remote/1460000018907426?w=1760&h=200); 貢獻(xiàn)者：飛龍版...
摘要：主成分分析就是降維，通過線性組合，把多個原始變量合并成若干個主成分，這樣每個主成分都變成原始變量的線性組合。相關(guān)系數(shù)系數(shù)為為為。從結(jié)果看，這個數(shù)據(jù)可能不太適合用來分析，因?yàn)榻档骄S后的代筆性不足。 這兩天用學(xué)了主成分分析，用的是PCA。主成分分析就是降維，通過線性組合，把多個原始變量合并成若干個主成分，這樣每個主成分都變成原始變量的線性組合。所以你想看具體哪個特征對結(jié)果的影響大，通過PC...
摘要：強(qiáng)烈推薦上值得前端學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)與算法項(xiàng)目，包含圖的演示過程與視頻講解。該倉庫包含了多種基于的算法與數(shù)據(jù)結(jié)構(gòu)，提供進(jìn)一步閱讀的解釋和鏈接。數(shù)據(jù)結(jié)構(gòu)和算法必知必會的個代碼實(shí)現(xiàn)。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言 算法為王。想學(xué)好前端，先練好內(nèi)功，內(nèi)功不行，就算招式練的再花哨，終究成不了高手；只有內(nèi)功深厚者，前端之路才會走得...
閱讀 1057·2021-11-18 13:23
閱讀 762·2021-11-08 13:16
閱讀 876·2021-10-11 10:58
閱讀 3523·2021-09-22 15:26
閱讀 1753·2021-09-08 10:42
閱讀 1831·2021-09-04 16:45
閱讀 1746·2019-08-30 15:54
閱讀 2577·2019-08-30 13:45
