1.3　線性表及其順序存儲結構

視頻二維碼（掃碼觀看）

一、線性表的基本概念

線性表（Linear List）是最簡單、最常用的一種數據結構。如：一個n維向量、矩陣，學生情況登記表。

線性表是由n（n≥0）個數據元素a₁，a₂，…，a_n組成的一個有限序列，表中的每一個數據元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。即線性表或是一個空表，或可以表示為（a₁，a₂，…，a_i，…，a_n），其中a_i（i＝1，2，…，n）是屬于數據對象的元素，通常也稱其為線性表中的一個結點。

非空線性表有如下一些結構特征：

（1）有且只有一個根結點a₁它無前件；

（2）有且只有一個終端結點a_n，它無后件；

（3）除根結點與終端結點外，其他所有結點有且只有一個前件，也有且只有一個后件。

【說明】

①線性表中結點的個數n稱為線性表的長度。

②當n＝0時，稱為空表。

二、線性表的順序存儲結構

1特點

（1）線性表中所有元素所占的存儲空間是連續的；

（2）線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。

在線性表的順序存儲結構中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面。

圖1-3　線性表的順序存儲結構

【注意】

①在程序設計語言中，通常定義一個一維數組來表示線性表的順序存儲空間。

②在用一維數組存放線性表時，該一維數組的長度通常要定義得比線性表的實際長度大一些，以便對線性表進行各種運算，特別是插入運算。

2線性表的相關操作

（1）插入：在線性表的指定位置處加入一個新的元素。

（2）刪除：在線性表中刪除指定的元素。

（3）查找：在線性表中查找某個（或某些）特定的元素。

（4）排序：對線性表中的元素進行整序（即線性表的）。

（5）分解：按要求將一個線性表分解成多個線性表。

（6）合并：按要求將多個線性表合并成一個線性表。

（7）復制：復制一個線性表。

（8）逆轉：逆轉一個線性表。

三、順序表的插入運算

【例5】長度為8的線性表順序存儲在長度為10的存儲空間中。在第2個元素之前插入一個新元素87。然后在線性表的第9個元素之前插入一個新元素14。

圖1-4　線性表在順序存儲結構下的插入

線性表的存儲空間從1到m，線性表的長度為n（n≤m），插入的位置為i（i表示在第i個元素之前插入）。線性表的插入操作如下：

第一步首先處理以下三種異常情況：

①當存儲空間已滿（即n＝m）時為“上溢”錯誤，不能進行插入，算法結束；

②當i＞n時，認為在最后一個元素之后插入；

③當i＜1時，認為在第1個元素之前插入。

第二步從最后一個元素開始，直到第i個元素，每一個元素往后移動一個位置。

第三步將新元素插入到第i個位置，線性表的長度加1。

四、順序表的刪除運算

【例6】長度為8的線性表順序存儲在長度為10的存儲空間中。現在要求刪除線性表中的第1個元素。再刪除線性表中的第6個元素。

圖1-5　線性表在順序存儲結構下的刪除

線性表的存儲空間從1到m，線性表的長度為n（n≤m），刪除的位置為i（表示刪除第i個元素）。線性表的刪除操作如下：

第一步首先處理以下兩種異常情況：

①當線性表為空（即n＝0）時錯誤，不能進行刪除，算法結束；

②當i＜1或i＞n時，錯誤，不能進行刪除，算法結束。

第二步刪除線性表中的第i個元素。

第三步從第i＋1個元素開始，直到最后一個元素，其中每一個元素均依次往前移動一個位置。線性表的長度減小1。