2.1 線性表的定義及運(yùn)算

2.1.1 線性表的定義

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

表2-1 電話號(hào)碼表

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

2.1.2 線性表的基本運(yùn)算

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

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

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

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

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

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

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

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