線性表概述 Linear List

在了解線性表之前，我們首先了解一下什么是線性結構。線性結構的特點是：在數據元素的非空有限集中

存在唯一的一個被稱為“第一個”的數據元素。

存在唯一的一個被稱為“最后一個”的數據元素。

除第一個外，集合中的每個數據元素均只有一個前驅。

除最后一個外，集合中的每個數據元素均只有一個后驅。

---

1 線性表的定義

線性表是一種最常用且最簡單的數據結構。簡單來說，一個線性表是 $n$ $(n\ge 0)$ 個數據元素的有限序列，其中 $n$ 為表長，當 $n=0$ 時線性表是一個空表。若用 $L$ 命名線性表，則其一般表示為
$$L=(a_1,a_2,\dots ,a_i,a_{i+1},\dots ,a_n)$$
其中 $a_1$ 又稱為表頭元素，$a_n$ 又稱為表尾元素，$i$ 稱為數據元素 $a_i$ 在線性表中的位序。除開表頭元素，任意元素有且僅有一個前驅；除開表尾元素，任意元素有且僅有一個后驅。這種線性有序的邏輯特征就是線性表名字的由來。

在生活中，我們經常用到線性表這樣的數據結構。例如，包含26個英文字母的字母表 $(A,B,C,\dots ,Z)$ 就是一個線性表，其數據元素是單個字母字符。又比如，某個中學對學生年齡的統計 $(12,12,13,14,12)$ ，其數據元素是整數。在稍復雜的情況下，線性表中的數據元素還可以由若干個數據項構成。例如某醫院對病人的信息記錄由五個部分組成：姓名、身份證號、性別、年齡和健康狀況。在這種情況下，我們常把數據元素稱為記錄（Record），含有大量記錄的線性表又稱為文件（File）

姓名身份證號性別年齡健康狀況

通過上述例子我們可以歸納，不同線性表中的數據元素的類型可以是不同的，但是在同一線性表中，所有數據元素必定具有相同特性（或屬于同一數據類型）。

同時，我們可以發現線性表討論的只是各數據元素之間的邏輯關系，并不涉及數據元素的存儲和運算，因此線性表是一種邏輯結構。

總結一下，線性表有如下特點：

• 表中元素個數有限。
• 表中元素具有邏輯上的順序性，有其先后次序。
• 表中元素都是數據元素。
• 表中元素的數據類型都相同，這意味著每個元素占有相同大小的存儲空間。
• 表中元素具有抽象性，即僅討論元素間的邏輯關系。

---

2 線性表的基本操作

一個數據結構的基本操作是指其最核心，最基本的操作。其他較復雜的操作都可以通過調用其基本操作來實現。

2.1 主要操作

線性表的主要操作如下：

主要操作操作結果

InitList(&L)	初始化操作，構造一個空的線性表
DestroyList(&L)	銷毀操作，銷毀線性表并釋放所占用的內存空間
ListEmpty(L)	判空操作，若 L 為空返回True，否則返回False
ListLength(L)	求表長操作，返回線性表 L 的長度，即元素個數
GetElem(L, i)	按位查找操作，獲取表 L 中第 i 個位置的元素的值
LocateElem(L, e)	按值查找操作，在表中查找具有給定關鍵字值的元素
ListInsert(&L, i , e)	插入操作，在表的第 i 個位置插入元素 e
ListDelete(&L, i , &e)	刪除操作，刪除表中第 i 個元素的值，并用 e 返回刪除元素的值
ListPrint(L)	輸出操作，按前后順序輸出線性表 L 的所有元素值

2.2 其他常用操作

2.2.1 兩表的并集

假設現在有兩個線性表 $LA$ 和 $LB$ ，要求擴大線性表 $LA$ ，將存在于線性表 $LB$ 中而不存在于線性表 $LA$ 中的數據元素插入到線性表 $LA$ 中去。

基本思路是從線性表 $LB$ 中依次取得每個數據元素，并依值在線性表 $LA$ 中查找，若不存在則插入該數據元素。

2.2.2 兩表的合并

假設現在有兩個線性表 $LA$ 和 $LB$ ，它們的數據元素按值非遞減有序排列，現要求將 $LA$ 和 $LB$ 歸并為一個新的線性表 $LC$ ，且 $LC$ 中的元素仍按值非遞減有序排列。例如，假設
$$\begin{array}{rl}LA& =(3,5,8)\\ LB& =(2,8,9)\end{array}$$
則
$$\begin{array}{rl}LC& =(2,3,5,8,8,9)\end{array}$$

基本思路是先令 $LC$ 為空表，然后用兩個指針 $i$ 和 $j$ 分別指向 $LA$ 和 $LB$ 中的元素，比較元素大小，將更小的元素插入 $LC$ 中，并將對應的指針后移一位。

---

相關章節

第一節 【緒論】數據結構的基本概念
第二節 【緒論】算法和算法評價
第三節 【線性表】線性表概述
第四節 【線性表】線性表的順序表示和實現
第五節 【線性表】線性表的鏈式表示和實現
第六節 【線性表】雙向鏈表、循環鏈表和靜態鏈表
第七節 【棧和隊列】棧
第八節 【棧和隊列】棧的應用
第九節 【棧和隊列】棧和遞歸
第十節 【棧和隊列】隊列

總結

以上是生活随笔為你收集整理的三、【线性表】线性表概述的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。