線性表

線性表是最基本、最簡單、也是最常用的一種數據結構。線性表（linear list）是數據結構的一種，一個線性表是n個具有相同特性的數據元素的有限序列。

線性表中數據元素之間的關係是一對一的關係，即除了第一個和最後一個數據元素之外，其它數據元素都是首尾相接的（注意，這句話只適用大部分線性表，而不是全部。比如，循環鍊表邏輯層次上也是一種線性表（存儲層次上屬於鏈式存儲），但是把最後一個數據元素的尾指針指向了首位結點）。

基本介紹

• 中文名：線性表
• 外文名：linear list
• 元素關係：一對一
• 類別：一般線性表和受限線性表
• 優點：邏輯結構簡單，便於實現和操作
• 套用學科：計算機科學、測繪科學、通信工程

簡介

定義

線性表（linear list）是數據結構的一種，一個線性表是n個具有相同特性的數據元素的有限序列。數據元素是一個抽象的符號，其具體含義在不同的情況下一般不同。

在稍複雜的線性表中，一個數據元素可由多個數據項（item）組成，此種情況下常把數據元素稱為記錄（record），含有大量記錄的線性表又稱檔案（file）。

線性表中的個數n定義為線性表的長度，n=0時稱為空表。在非空表中每個數據元素都有一個確定的位置，如用a_i表示數據元素，則i稱為數據元素a_i線上性表中的位序。

線性表的相鄰元素之間存在著序偶關係。如用（a₁，…，a_i-1，a_i，a_i+1，…，a_n）表示一個順序表，則表中a_i-1領先於a_i，a_i領先於a_i+1，稱a_i-1是a_i的直接前驅元素，a_i+1是a_i的直接後繼元素。當i=1,2，…，n-1時，a_i有且僅有一個直接後繼，當i=2，3，…，n時，a_i有且僅有一個直接前驅。

分類

我們說“線性”和“非線性”，只在邏輯層次上討論，而不考慮存儲層次，所以雙向鍊表和循環鍊表依舊是線性表。

在數據結構邏輯層次上細分，線性表可分為一般線性表和受限線性表。一般線性表也就是我們通常所說的“線性表”，可以自由的刪除或添加結點。受限線性表主要包括棧和佇列，受限表示對結點的操作受限制。

優點

線性表的邏輯結構簡單，便於實現和操作。因此，線性表這種數據結構在實際套用中是廣泛採用的一種數據結構。

特徵

1．集合中必存在唯一的一個“第一元素”。

2．集合中必存在唯一的一個 “最後元素” 。

3．除最後一個元素之外，均有唯一的後繼(後件)。

4．除第一個元素之外，均有唯一的前驅(前件)。

基本操作

1）MakeEmpty(L) 這是一個將L變為空表的方法

2）Length（L） 返回表L的長度，即表中元素個數

3）Get（L，i） 這是一個函式，函式值為L中位置i處的元素（1≤i≤n）

4）Prior（L，i） 取i的前驅元素

5）Next（L，i） 取i的後繼元素

6）Locate（L，x） 這是一個函式，函式值為元素x在L中的位置

7）Insert（L，i，x）在表L的位置i處插入元素x，將原占據位置i的元素及後面的元素都向後推一個位置

8）Delete（L，p） 從表L中刪除位置p處的元素

9）IsEmpty(L) 如果表L為空表(長度為0)則返回true，否則返回false

10）Clear（L）清除所有元素

11）Init（L）同第一個，初始化線性表為空

12）Traverse（L）遍歷輸出所有元素

13）Find（L，x）查找並返回元素

14）Update（L，x）修改元素

15）Sort（L）對所有元素重新按給定的條件排序

16) strstr(string1,string2)用於字元數組的求string1中出現string2的首地址

存儲結構

線性表主要由順序表示或鏈式表示。在實際套用中，常以棧、佇列、字元串等特殊形式使用。

順序表示指的是用一組地址連續的存儲單元依次存儲線性表的數據元素，稱為線性表的順序存儲結構或順序映像（sequential mapping）。它以“物理位置相鄰”來表示線性表中數據元素間的邏輯關係，可隨機存取表中任一元素。

鏈式表示指的是用一組任意的存儲單元存儲線性表中的數據元素，稱為線性表的鏈式存儲結構。它的存儲單元可以是連續的，也可以是不連續的。在表示數據元素之間的邏輯關係時，除了存儲其本身的信息之外，還需存儲一個指示其直接後繼的信息（即直接後繼的存儲位置），這兩部分信息組成數據元素的存儲映像，稱為結點（node）。它包括兩個域；存儲數據元素信息的域稱為數據域；存儲直接後繼存儲位置的域稱為指針域。指針域中存儲的信息稱為指針或鏈。

結構特點

1.均勻性：雖然不同數據表的數據元素可以是各種各樣的，但對於同一線性表的各數據元素必定具有相同的數據類型和長度。

2.有序性：各數據元素線上性表中的位置只取決於它們的序號，數據元素之前的相對位置是線性的，即存在唯一的“第一個“和“最後一個”的數據元素，除了第一個和最後一個外，其它元素前面均只有一個數據元素(直接前驅)和後面均只有一個數據元素（直接後繼）。

線性表的推廣

時間有序表、排序表、和頻率有序表都可以看做是線性表的推廣。如果按照結點到達結構的時間先後，作為確定結點之間關係的，這樣一種線性結構稱之為時間有序表。例如，在紅燈前停下的一長串汽車，最先到達的為首結點，最後到達的為尾結點；在離開時最先到達的汽車將最先離開，最後到達的將最後離開。這些汽車構成理一個佇列，實際上就是一個時間有序表。棧和佇列都是時間有序表。頻率有序表是按照結點的使用頻率確定它們之間的相互關係的，而排序表是根據結點的關鍵字值來加以確定的。