數據結構和算法之線性表

前言

上一篇《 數據結構和算法之時間復雜度和空間復雜度 》中介紹了時間復雜度的概念和常見的時間復雜度，并分別舉例子進行了一一說明。這一篇主要介紹線性表。

線性表屬于數據結構中邏輯結構中的線性結構。回憶一下，數據結構分為物理結構和邏輯結構，邏輯結構分為線性結構、幾何結構、樹形結構和圖形結構四大結構。其中，線性表就屬于線性結構。剩余的三大邏輯結構今后會一一介紹。

線性表

基本概念

線性表（List）：由零個或多個數據元素組成的有限序列。

注意：

1.線性表是一個序列。

2.0個元素構成的線性表是空表。

3.線性表中的第一個元素無前驅，最后一個元素無后繼，其他元素有且只有一個前驅和后繼。

4.線性表是有長度的，其長度就是元素個數，且線性表的元素個數是有限的，也就是說，線性表的長度是有限的。

如果用數學語言來進行定義，可如下：

若將線性表記為（a1,…,ai-1,ai,ai+1,…an）,則表中ai-1領先于ai,ai領先于ai+1,稱ai-1是ai的直接前驅元素,ai+1是ai的直接后繼元素。

線性表基本操作

InitList ( *L ) : 初始化操作，建立一個空的線性表L。

ListEmpty (L ) : 判斷線性表是否為空表，若線性表為空，返回 true，否則返回 false。

ClearList ( *L ) : 將線性表清空。 GetElem (L ,i ,*e ) : 將線性表L中的第i個位置元素值返回給e。

LocateElem (L ,e ) : 在線性表L中查找與給定值e相等的元素，如果查找成功，返回該元素在表中序號表示成功；否則，返回 0表示失敗。

ListInsert ( *L ,i ,e ) : 在線性表L中第i個位置插入新元素e。

ListDelete ( *L ,i ,*e ) : 刪除線性表L中第i個位置元素，并用e返回其值。

ListLength (L ) : 返回線性表L的元素個數。

對于不同的應用，線性表的基本操作是不同的，上述操作是最基本的。

對于實際問題中涉及的關于線性表的更復雜操作，完全可以用這些基本操作的組合來實現。