本詞條由“科普中國”科學(xué)百科詞條編寫與應(yīng)用工作項(xiàng)目 審核 。
線性表是最基本、最簡單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表（linear list）是數(shù)據(jù)結(jié)構(gòu)的一種，一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。
線性表中數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系，即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的（注意，這句話只適用大部分線性表，而不是全部。比如，循環(huán)鏈表邏輯層次上也是一種線性表（存儲(chǔ)層次上屬于鏈?zhǔn)酱鎯?chǔ)，但是把最后一個(gè)數(shù)據(jù)元素的尾指針指向了首位結(jié)點(diǎn)）。
- 中文名:線性表
- 外文名:linear list
- 元素關(guān)系:一對(duì)一
- 類 別:一般線性表和受限線性表
- 優(yōu) 點(diǎn):邏輯結(jié)構(gòu)簡單，便于實(shí)現(xiàn)和操作
- 應(yīng)用學(xué)科:計(jì)算機(jī)科學(xué)、測繪科學(xué)、通信工程
目錄
- 1 簡介
- ▪ 定義
- ▪ 分類
- ▪ 優(yōu)點(diǎn)
- 2 特征
- 3 基本操作
- 4 存儲(chǔ)結(jié)構(gòu)
- 5 結(jié)構(gòu)特點(diǎn)
- 6 線性表的推廣
線性表簡介
線性表定義
線性表（linear list）是數(shù)據(jù)結(jié)構(gòu)的一種，一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。數(shù)據(jù)元素是一個(gè)抽象的符號(hào)，其具體含義在不同的情況下一般不同。
在稍復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素可由多個(gè)數(shù)據(jù)項(xiàng)（item）組成，此種情況下常把數(shù)據(jù)元素稱為記錄（record），含有大量記錄的線性表又稱文件（file）。
線性表中的個(gè)數(shù)n定義為線性表的長度，n=0時(shí)稱為空表。在非空表中每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置，如用ai表示數(shù)據(jù)元素，則i稱為數(shù)據(jù)元素ai在線性表中的位序。
線性表的相鄰元素之間存在著序偶關(guān)系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一個(gè)順序表，則表中ai-1領(lǐng)先于ai，ai領(lǐng)先于ai+1，稱ai-1是ai的直接前驅(qū)元素，ai+1是ai的直接后繼元素。當(dāng)i=1,2，…，n-1時(shí)，ai有且僅有一個(gè)直接后繼，當(dāng)i=2，3，…，n時(shí)，ai有且僅有一個(gè)直接前驅(qū) [1] 。
線性表分類
我們說“線性”和“非線性”，只在邏輯層次上討論，而不考慮存儲(chǔ)層次，所以雙向鏈表和循環(huán)鏈表依舊是線性表。
在數(shù)據(jù)結(jié)構(gòu)邏輯層次上細(xì)分，線性表可分為一般線性表和受限線性表。一般線性表也就是我們通常所說的“線性表”，可以自由的刪除或添加結(jié)點(diǎn)。受限線性表主要包括棧和隊(duì)列，受限表示對(duì)結(jié)點(diǎn)的操作受限制。
線性表優(yōu)點(diǎn)
線性表的邏輯結(jié)構(gòu)簡單，便于實(shí)現(xiàn)和操作。因此，線性表這種數(shù)據(jù)結(jié)構(gòu)在實(shí)際應(yīng)用中是廣泛采用的一種數(shù)據(jù)結(jié)構(gòu)。
線性表特征
1．集合中必存在唯一的一個(gè)“第一元素”。
2．集合中必存在唯一的一個(gè) “最后元素” 。
3．除最后一個(gè)元素之外，均有唯一的后繼(后件)。
4．除第一個(gè)元素之外，均有唯一的前驅(qū)(前件)。
線性表基本操作
編輯
1）MakeEmpty(L) 這是一個(gè)將L變?yōu)榭毡淼姆椒?/DIV>
2）Length（L） 返回表L的長度，即表中元素個(gè)數(shù)
3）Get（L，i） 這是一個(gè)函數(shù)，函數(shù)值為L中位置i處的元素（1≤i≤n）
4）Prior（L，i） 取i的前驅(qū)元素
5）Next（L，i） 取i的后繼元素
6）Locate（L，x） 這是一個(gè)函數(shù)，函數(shù)值為元素x在L中的位置
7）Insert（L，i，x）在表L的位置i處插入元素x，將原占據(jù)位置i的元素及后面的元素都向后推一個(gè)位置
8）Delete（L，p） 從表L中刪除位置p處的元素
9）IsEmpty(L) 如果表L為空表(長度為0)則返回true，否則返回false
10）Clear（L）清除所有元素
11）Init（L）同第一個(gè)，初始化線性表為空
12）Traverse（L）遍歷輸出所有元素
13）Find（L，x）查找并返回元素
14）Update（L，x）修改元素
15）Sort（L）對(duì)所有元素重新按給定的條件排序
16) strstr(string1,string2)用于字符數(shù)組的求string1中出現(xiàn)string2的首地址
線性表存儲(chǔ)結(jié)構(gòu)
編輯
線性表主要由順序表示或鏈?zhǔn)奖硎�。在�?shí)際應(yīng)用中，常以棧、隊(duì)列、字符串等特殊形式使用。
順序表示指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，稱為線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映像（sequential mapping）。它以“物理位置相鄰”來表示線性表中數(shù)據(jù)元素間的邏輯關(guān)系，可隨機(jī)存取表中任一元素。
鏈?zhǔn)奖硎局傅氖怯靡唤M任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。在表示數(shù)據(jù)元素之間的邏輯關(guān)系時(shí)，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息（即直接后繼的存儲(chǔ)位置），這兩部分信息組成數(shù)據(jù)元素的存儲(chǔ)映像，稱為結(jié)點(diǎn)（node）。它包括兩個(gè)域；存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域；存儲(chǔ)直接后繼存儲(chǔ)位置的域稱為指針域。指針域中存儲(chǔ)的信息稱為指針或鏈 [1] 。
線性表結(jié)構(gòu)特點(diǎn)
編輯
1.均勻性：雖然不同數(shù)據(jù)表的數(shù)據(jù)元素可以是各種各樣的，但對(duì)于同一線性表的各數(shù)據(jù)元素必定具有相同的數(shù)據(jù)類型和長度。
2.有序性：各數(shù)據(jù)元素在線性表中的位置只取決于它們的序號(hào)，數(shù)據(jù)元素之前的相對(duì)位置是線性的，即存在唯一的“第一個(gè)“和“最后一個(gè)”的數(shù)據(jù)元素，除了第一個(gè)和最后一個(gè)外，其它元素前面均只有一個(gè)數(shù)據(jù)元素(直接前驅(qū))和后面均只有一個(gè)數(shù)據(jù)元素（直接后繼）。
線性表線性表的推廣
編輯
時(shí)間有序表、排序表、和頻率有序表都可以看做是線性表的推廣。如果按照結(jié)點(diǎn)到達(dá)結(jié)構(gòu)的時(shí)間先后，作為確定結(jié)點(diǎn)之間關(guān)系的，這樣一種線性結(jié)構(gòu)稱之為時(shí)間有序表。例如，在紅燈前停下的一長串汽車，最先到達(dá)的為首結(jié)點(diǎn)，最后到達(dá)的為尾結(jié)點(diǎn)；在離開時(shí)最先到達(dá)的汽車將最先離開，最后到達(dá)的將最后離開。這些汽車構(gòu)成了一個(gè)隊(duì)列，實(shí)際上就是一個(gè)時(shí)間有序表。棧和隊(duì)列都是時(shí)間有序表。頻率有序表是按照結(jié)點(diǎn)的使用頻率確定它們之間的相互關(guān)系的，而排序表是根據(jù)結(jié)點(diǎn)的關(guān)鍵字值來加以確定的。 [2]
