第二章?線性表

在數據元素的非空有限集中：

(1)存在唯一一個被稱作“第一個”的數據元素；

(2)存在唯一一個被稱作“最后一個”的數據元素；

(3)除第一個之外，集合中的每個數據元素均只有一個前驅；

(4)除最后一個之外，集合中每個元素均只有一個后繼。

2.1 線性表的類型定義

線性表(linear_list) 是n個數據元素的有限序列。

? ?線性表 --> 文件file

數據元素 --> 記錄 record

? ?數據項 -->

線性表中的數據元素可以是各種各樣的，但同一線性表中的元素必定具有相同特性，即屬同一對象。

相鄰數據元素之間存在著序偶(ordered pair)關系。

直接前驅

直接后繼

線性表中元素的個數n定義為線性表的長度，n=0時稱為空表。

i稱為位序

?

基本操作：

InitList

DestroyList

ClearList

ListEmpty

ListLength

GetElem

LocateElem

PriorElem

NextElem

ListInsert

ListDelete

ListTraverse

2.2 線性表的順序表示和實現

用一組地址連續的存儲單元依次存儲線性表的數據元素。

是線性表的第一個數據元素的存儲位置，通常稱作線性表的起始位置或基地址。

隨機存取

順序表，用數組表示。

2.3 線性表的鏈式表示和實現

順序表：隨機存取

鏈表：插入、刪除

?

線性鏈表/單鏈表：用一組任意的存儲單元存儲線性表的數據元素。

|--數據域

|--指針域

?

頭指針指向頭結點，頭結點指向首結點。

頭結點的數據域可以不存儲任何信息，也可以存儲如線性表的長度等類的信息。

在單鏈表中，取得第i個數據元素必須從頭指針出發尋找，因此，單鏈表是非隨機存取的存儲結構。

?

靜態鏈表：

用一維數組來描述線性鏈表

方便于在不設指針類型的高級程序設計語言中使用鏈表結構。

數組的一個分量表示一個結點，同時用游標(指示器cur)代替指針指示結點在數組中的相對位置。數組的第零分量可看成頭節點，其指針域指示鏈表的第一個結點。

為了辨明數組中哪些分量未被使用，解決的辦法是將所有未被使用過以及被刪除的分量用游標鏈成一個備用的鏈表，每當進行插入時便可從備用鏈表上取得第一個結點作為待插入的新結點；反之，在刪除時將從鏈表中刪除下來的結點鏈接到備用鏈表上。

?

循環鏈表 circular linked list：

表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環。

通常為，僅設尾指針的循環鏈表。

?

雙向鏈表 double linked list：

結點中有兩個指針域，其一指向直接后繼，另一指向直接前驅。

?

2.4 線性表的應用——一元多項式的表示及相加

?