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