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