返回目錄

線性表(biao)是(shi)最(zui)基(ji)本、最(zui)簡(jian)單、也(ye)是(shi)最(zui)常用(yong)(yong)的(de)(de)一(yi)種。線性表(biao)中(zhong)數(shu)據(ju)元(yuan)素(su)之間的(de)(de)關系是(shi)一(yi)對一(yi)的(de)(de)關系，即除了第一(yi)個和最(zui)后(hou)一(yi)個數(shu)據(ju)元(yuan)素(su)之外，其它數(shu)據(ju)元(yuan)素(su)都是(shi)首(shou)尾(wei)相(xiang)接的(de)(de)。線性表(biao)的(de)(de)邏輯結(jie)構簡(jian)單，便于實(shi)現和操(cao)作。因此，線性表(biao)這種數(shu)據(ju)結(jie)構在(zai)實(shi)際應用(yong)(yong)中(zhong)是(shi)廣泛采用(yong)(yong)的(de)(de)一(yi)種數(shu)據(ju)結(jie)構。

線(xian)性(xing)表(biao)是一種常(chang)用的(de)，以下(xia)介紹(shao)線(xian)性(xing)表(biao)及其順序(xu)存儲(chu)，并對(dui)棧(zhan)和及它們的(de)順序(xu)實現給出了(le)詳(xiang)細的(de)設計描述(shu)。

在實際應用中，線性表都是(shi)以棧(zhan)、隊列、字符(fu)串(chuan)、數組(zu)，鏈(lian)表（環(huan)形鏈(lian)表比較特殊，它是(shi)首尾相連的(de)）等特(te)殊(shu)線性(xing)(xing)表的(de)形式來使用的(de)。由于(yu)這些特(te)殊(shu)線性(xing)(xing)表都具(ju)有各自(zi)的(de)特(te)性(xing)(xing)，因此(ci)，掌握這些特(te)殊(shu)線性(xing)(xing)表的(de)特(te)性(xing)(xing)，對于(yu)數據運算的(de)可靠性(xing)(xing)和(he)提高操作效(xiao)率都是(shi)至(zhi)關重要的(de)。

線(xian)性(xing)表是一(yi)個(ge)(ge)線(xian)性(xing)結(jie)(jie)構，它是一(yi)個(ge)(ge)含(han)有(you)n≥0個(ge)(ge)結(jie)(jie)點(dian)的有(you)限序列，對于其中的結(jie)(jie)點(dian)，有(you)且(qie)僅(jin)有(you)一(yi)個(ge)(ge)開始結(jie)(jie)點(dian)沒有(you)前(qian)驅但有(you)一(yi)個(ge)(ge)后繼結(jie)(jie)點(dian)，有(you)且(qie)僅(jin)有(you)一(yi)個(ge)(ge)終端(duan)結(jie)(jie)點(dian)沒有(you)后繼但有(you)一(yi)個(ge)(ge)前(qian)驅結(jie)(jie)點(dian)，其它的結(jie)(jie)點(dian)都有(you)且(qie)僅(jin)有(you)一(yi)個(ge)(ge)前(qian)驅和一(yi)個(ge)(ge)后繼結(jie)(jie)點(dian)。一(yi)般(ban)地，一(yi)個(ge)(ge)線(xian)性(xing)表可(ke)以表示成(cheng)一(yi)個(ge)(ge)線(xian)性(xing)序列：k1,k2,…,kn，其中k1是開始結(jie)(jie)點(dian)，kn是終端(duan)結(jie)(jie)點(dian)。

是一(yi)個(ge)數據元(yuan)素(su)的(de)有序(xu)（次序(xu)）集

圖示

特征

線性結(jie)構(gou)的基本特征為:

1．集(ji)合中必存(cun)在(zai)唯一(yi)(yi)(yi)的一(yi)(yi)(yi)個“第(di)一(yi)(yi)(yi)元素”；

2．集合中必存在唯(wei)一(yi)(yi)的一(yi)(yi)個 “最后(hou)元素” ；

3．除最后(hou)一個(ge)元素之外，均有 唯一的后(hou)繼(后(hou)件)；

4．除第一個元素之外，均(jun)有 唯一的前驅(前件)。

由n(n≥0)個數據元素(結點)a1,a2,…,an組成(cheng)的(de)有限序列。

數據元素(su)的(de)個(ge)數n定(ding)義為表的(de)長度。

當n=0時稱(cheng)為空(kong)表。

常常將非空的線性表(n>0)記(ji)作：

(a1，a2，…an)

數據元素ai(1≦i≦n)只是一個抽象的符號，其(qi)具體含義在不同的情況下(xia)可以不同。

線性表的基本操作

1）MakeEmpty(L) 這(zhe)是一個將L變為空表(biao)的方法

2）Length（L） 返回表L的長度，即表中元素個數

3）Get（L，i） 這是一個(ge)函數，函數值為(wei)L中位置i處的(de)元(yuan)素（1≤i≤n）

4）Prev（L，i） 取(qu)i的前趨(qu)元素

5）Next（L，i） 取i的(de)后繼元素

6）Locate（L，x） 這是一(yi)個函數，函數值為元素x在(zai)L中的位(wei)置

7）Insert（L，i，x）在(zai)表L的位置(zhi)(zhi)(zhi)i處插入元素(su)x，將原(yuan)占據位置(zhi)(zhi)(zhi)i的元素(su)及后(hou)面的元素(su)都向后(hou)推一(yi)個位置(zhi)(zhi)(zhi)

8）Delete（L，p） 從表L中刪除位置p處的元素

9）IsEmpty(L) 如(ru)果(guo)表(biao)L為空表(biao)(長(chang)度為0)則返(fan)回true，否則返(fan)回false

10）Clear（L）清除所(suo)有元素

11）Init（L）同第一個，初始化線性表為空

12）Traverse（L）遍歷(li)輸(shu)出所有元素

13）Find（L，x）查找并返回(hui)元素

14）Update（L，x）修改元(yuan)素

15）Sort（L）對所有元素重(zhong)新按給定的條件(jian)排序

結構特點

線性表具有如下的結(jie)構(gou)特點(dian)：

1.均勻(yun)性：雖然不(bu)同數據表的(de)數據元素可(ke)以(yi)是各種(zhong)各樣的(de)，但(dan)對于同一線性表的(de)各數據元素必定具有(you)相同的(de)和長度。

2.有(you)(you)序性(xing)：各數(shu)據(ju)(ju)元(yuan)素(su)(su)在(zai)線性(xing)表中(zhong)的(de)(de)(de)位置只取決于它(ta)們的(de)(de)(de)序與(yu)，數(shu)據(ju)(ju)元(yuan)素(su)(su)之(zhi)前(qian)的(de)(de)(de)相對位置是線性(xing)的(de)(de)(de)，即存(cun)在(zai)唯一(yi)的(de)(de)(de)“第(di)一(yi)個(ge)(ge)“和(he)“最后(hou)一(yi)個(ge)(ge)“的(de)(de)(de)數(shu)據(ju)(ju)元(yuan)素(su)(su)，除了(le)第(di)一(yi)個(ge)(ge)和(he)最后(hou)一(yi)個(ge)(ge)外(wai)，其它(ta)元(yuan)素(su)(su)前(qian)面(mian)均只有(you)(you)一(yi)個(ge)(ge)數(shu)據(ju)(ju)元(yuan)素(su)(su)直(zhi)(zhi)接前(qian)驅(qu)和(he)后(hou)面(mian)均只有(you)(you)一(yi)個(ge)(ge)數(shu)據(ju)(ju)元(yuan)素(su)(su)（直(zhi)(zhi)接后(hou)繼）。

在(zai)實(shi)現線(xian)(xian)性表(biao)數(shu)(shu)據(ju)元素(su)的存(cun)儲(chu)方面，一般可用順序存(cun)儲(chu)結(jie)(jie)(jie)構和(he)兩種方法。鏈式存(cun)儲(chu)結(jie)(jie)(jie)構將在(zai)本(ben)網站線(xian)(xian)性中介紹，本(ben)章主要介紹用數(shu)(shu)組實(shi)現線(xian)(xian)性表(biao)數(shu)(shu)據(ju)元素(su)的順序存(cun)儲(chu)及其應用。另外棧(zhan)．隊列(lie)和(he)串也是(shi)線(xian)(xian)性表(biao)的特殊(shu)情況，又(you)稱為受限(xian)的線(xian)(xian)性結(jie)(jie)(jie)構。

返回目錄