2.1 線性表的定義及運算

2.1.1 線性表的定義

線性表（linear list）是一種最簡單且最常用的數(shù)據(jù)結(jié)構(gòu)。一個線性表是n（n≥0）個相同類型的數(shù)據(jù)元素構(gòu)成的有限序列（a1,a2,…,an）。其中元素的個數(shù)n定義為線性表的長度，當(dāng)n=0時稱為空表，空表中沒有任何數(shù)據(jù)元素。線性表中數(shù)據(jù)元素的含義在不同情況下可以不同，它既可以是原子類型，也可以是結(jié)構(gòu)類型，但同一線性表中的數(shù)據(jù)元素必須屬于同一數(shù)據(jù)對象。例如，由26個英文字母構(gòu)成的表（a,b,c,…,z）是一個線性表，再如由全體職工的基本工資構(gòu)成的表（1236.60,1669.80,900.00,890.00,…,1842.00）是一個線性表。這兩個線性表中的每個數(shù)據(jù)元素都只由一個數(shù)據(jù)項構(gòu)成，是簡單的原子類型。而如表2-1所示的電話號碼表也是一個線性表，其數(shù)據(jù)元素是由姓名、職務(wù)、所在部門和聯(lián)系電話4個數(shù)據(jù)項構(gòu)成的，是復(fù)雜的結(jié)構(gòu)類型。

表2-1 電話號碼表

對于線性表（a1,a2,…,ai-1,ai,ai+1,…,an），元素ai-1領(lǐng)先于元素ai，稱ai-1是ai的直接前驅(qū)，而稱ai是ai-1的直接后繼。除了第一個元素a1外，每個元素ai有且僅有一個直接前驅(qū)ai-1，除了最后一個元素an外，每個元素ai有且僅有一個直接后繼ai+1。由此可見，線性表中數(shù)據(jù)元素之間的（相對位置）關(guān)系是線性的，即一維的。若元素間滿足a1≤a2≤…≤ai-1≤ai≤ai+1≤…≤an，則這種線性表稱為非遞減有序表；若元素間滿足a1≥a2≥…≥ai-1≥ai≥ai+1≥…≥an，則這種線性表稱為非遞增有序表。

2.1.2 線性表的基本運算

（1）InitList(l)，初始化線性表l。

（2）EmptyList(l)，判斷線性表l是否為空表，如果l為空表則返回1，否則返回0。

（3）ListLength(l)，求線性表l的長度。

（4）Locate(l,e)，求線性表l中元素e的位置。

（5）GetData(l,i)，返回線性表l中第i個元素的值。

（6）InsList(l,i,e)，在l中第i個元素（位置）之前插入數(shù)據(jù)元素e。

（7）DelList(l,i)，刪除l中的第i個數(shù)據(jù)元素。

在實際使用中線性表可能還有其他的運算，如將兩個或兩個以上的線性表合并成一個線性表；把一個線性表拆分成兩個或兩個以上的線性表；多種條件的合并、拆分、復(fù)制和排序等運算。這通常都可借助于這些基本運算的組合來實現(xiàn)。