第2章線性表

        第  2  章  線性表

       線性表是最簡單、最基本,也是最常用的數(shù)據(jù)結構。   幼兒園小朋友人數(shù)眾多,有的幼兒園為便于管理,會給每個班級排一個固定順序的隊伍,如班級里有30個小朋友,會按照順序給小朋友排學號1,2,3……30,不管是平時放學排隊還是外出參加活動,小朋友都按照學號排隊,讓每個小朋友記住自己前后的小朋友,若發(fā)現(xiàn)前后小朋友不在馬上報告老師,而老師只要記住第1個小朋友就可以了。班級中,只有1號前面沒有小朋友,只有30號后面沒有小朋友,其他每個學號都是前面只有一個小朋友,后面只有一個小朋友,這就是一個典型的線性表。   本章我們就要來學習線性表。    2.1線性表的邏輯結構     2.1.1線性表的定義   線性表L是n(n≥0)個具有相同屬性的數(shù)據(jù)元素a1,a2,a3,…,an組成的有限序列。其中，序列中元素的個數(shù)n稱為線性表的長度。   當n=0時稱為空表,即不含有任何元素。   常常將非空的線性表L(n>0)記為：L=(a1,a2,…，ai-1,ai,ai+1,…，an)。   其中，ai-1為ai的直接前驅(qū),ai＋1為ai的直接后繼。a1為表頭元素,an為表尾元素。線性表有以下特點。   (1) 在非空的線性表中,存在唯一的一個被稱為“第一個”的數(shù)據(jù)元素,又稱為表頭元素；存在唯一的一個被稱為“最后一個”的元素,又稱為表尾元素。   (2) 線性表中數(shù)據(jù)的位置先后是有序的。除表頭元素外,線性表中的每一個元素有且僅有一個前驅(qū)；除表尾元素外,線性表中的每一個元素有且僅有一個后繼。表頭元素只有一個后繼而沒有前驅(qū),表尾元素只有一個前驅(qū)而沒有后繼。   (3) 線性表中的數(shù)據(jù)的類型是相同的。表的長度n的取值是有限數(shù),最小為0。   在日常生活中,線性表的例子很多。例如，26個英文字母組成的字母表(A,B,C,…,Y,Z)就是一個典型的線性表,該表長度是26,每個字母是表中的一個元素。表2��1所示的學生信息表也構成了一個線性表。     表2��1學生信息表     學號姓名班級年齡宿舍  160210001崔雨計科160118星苑305  160210002丁潔計科160119星苑305  160210003樊辰計科160118松苑207  160210004馮波計科160119松苑207  160210005郭力計科160120松苑207  160210006胡志計科160120松苑207    該線性表表長為6,表中每個學生的信息為一個“數(shù)據(jù)元素”,包括學號、姓名、班級、年齡和宿舍等“數(shù)據(jù)項”信息。

        2.1.2線性表的基本運算   數(shù)據(jù)結構的基本運算是定義在邏輯結構層次上的,而這些運算的具體實現(xiàn)是需要建立在存儲結構上的,因此下面定義的線性表的基本運算作為邏輯結構的一部分,其具體實現(xiàn)卻要在線性表的存儲結構確定之后才能夠完成。   線性表的基本操作有以下幾項。   (1) 線性表L的初始化，其語句如下。    InitList(L)    構造一個空的線性表L，即表的初始化。   (2) 創(chuàng)建線性表L，其語句如下。    CreatList(L)    (3) 求線性表L的長度，其語句如下。    GetLength(L)    求表中結點的個數(shù),即求表的長度。   (4) 按序號取線性表L中的元素，其語句如下。    GetNode(L,i)    取線性表L中的第i個元素,這里1≤i≤Length(L)。   (5) 在線性表L中查找元素e，其語句如下。    LocateList(L,e)    在L中查找值為e 的結點,并返回該結點在L中的位置。若L中有多個結點的值和e 相同,則返回首次找到的結點位置；若L中沒有結點的值為e,則返回一個特殊值(如-1),表示查找失敗。   (6) 在線性表L中插入新元素，其語句如下。    InsertList(L,i,e)    在線性表L的第i個位置上插入一個值為x 的新結點,使得原編號為i,i+1,…,n的結點變?yōu)榫幪枮閕+1,i+2,…,n+1的結點。這里1≤i≤n+1,而n是原表L的長度。插入后,表L的長度加1。   (7) 在線性表L中刪除元素，其語句如下。    DeleteList(L,i)    刪除線性表L的第i個結點,使得原編號為i+1,i+2,…,n的結點變成編號為i,i+1,…,n-1的結點。這里1≤i≤n (n是原表L的長度),刪除后表L的長度減1,為n-1。   (8) 將線性表中元素輸出，其語句如下。    PrintList(L)    將線性表L中的元素打印輸出,若對線性表進行了一些操作,如插入、刪除等,需要將其打印輸出查看操作結果。

       2.2線性表的順序存儲及運算實現(xiàn)    線性表有兩種基本的存儲結構：順序存儲結構和鏈式存儲結構。

       2.2.1線性表的順序存儲結構   線性表的順序存儲是最簡單、最直接的一種存儲方式,即把線性表的結點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。這樣的存儲方式使線性表邏輯上相鄰的元素存儲在物理地址相鄰的存儲單元里,即以計算機內(nèi)“物理位置相鄰”來反映數(shù)據(jù)元素之間邏輯上的相鄰關系,采用這種存儲方式的線性表又稱為順序表。   順序表有以下特征。   (1) 線性表的所有元素所占的空間是連續(xù)的。   (2) 線性表中各個數(shù)據(jù)元素在存儲空間中是按照邏輯順序依次存放的。   由于線性表中的所有數(shù)據(jù)元素都是同一數(shù)據(jù)類型,所以每個元素在存儲器中占用的空間(字節(jié)數(shù))相同。只要知道了第1個數(shù)據(jù)元素a1的存儲地址和它所占有的存儲單元個數(shù),即可求得第i個數(shù)據(jù)元素ai的地址。假定第一個元素a1的地址為LOC(a1),每個數(shù)據(jù)元素占k個字節(jié),則第i個數(shù)據(jù)元素ai的地址是：   LOC(ai)=LOC(a1)+(i－1)×k(1≤i≤n)   例如：第2個數(shù)據(jù)元素a3的地址是LOC(a2)=LOC(a1)+k   第3個數(shù)據(jù)元素a3的地址是LOC(a3)=LOC(a1)+2k   ……   第i個數(shù)據(jù)元素ai的地址是LOC(ai)=LOC(a1)+(i－1)×k   順序表的順序存儲結構如圖2��1所示。    圖2��1順序表的順序存儲示意圖     由于線性表中的數(shù)據(jù)元素都是按照邏輯關系進行存儲的，所以只要確定了順序表的起始位置，線性表中的任一數(shù)據(jù)元素都可以隨機存取，因此線性表的順序存儲結構是一種“隨機存取”的存儲結構。   順序表在具體實現(xiàn)時,一般用高級語言中的數(shù)組來對應連續(xù)的存儲空間。設最多可存儲MaxSize個元素,在C語言中可用數(shù)組data\[MaxSize\]來存儲數(shù)據(jù)元素,為保存線性表的長度需定義一個整型變量length。線性表的第l,2,…,n個元素分別存放在此數(shù)組下標為0,1,…,length-1數(shù)組元素中,如圖2��1所示。   在C語言中,可用下述類型定義來描述線性表。    #defineMaxSize100/*順序表的容量*/   typedefintDataType;/*在應用中,將實際數(shù)據(jù)類型定義成DataType */   typedefstruct{   DataTypedata\[MaxSize\];/*定義存儲表元素的數(shù)組*/   intlength;/*順序表的實際長度*/   }SeqList; /*順序表數(shù)據(jù)類型說明*/   SeqList *L;/*定義一個順序表類型的指針變量L*/     在使用一維數(shù)組存放線性表時,通常定義的數(shù)組的空間要比實際表稍長大一些,以便對線性表進行各種運算,特別是對線性表的插入運算。一般情況下,應該盡可能考慮到使用的線性表可能達到的最大長度,如果定義的存儲空間過小,則在線性表動態(tài)增長時可能會出現(xiàn)存儲空間不夠而無法插入新的元素的情況；如果存儲空間過大,而實際又沒有用到那么大的存儲空間,則會造成存儲空間的浪費。在實際應用中,可以根據(jù)線性表動態(tài)變化過程中的一般規(guī)模來決定開辟存儲空間量,設置足夠的數(shù)組長度,以備擴展。

        2.2.2順序表上基本運算的實現(xiàn)

        1. 順序表L的初始化   順序表的初始化即構造一個空表,順序表是否為空取決于其數(shù)據(jù)元素個數(shù)是否為0,因此,只要將表L的長度設置為0即可構造出一個空表。   算法2��1順序表的初始化。    void InitList(SeqList *L)/*順序表的初始化即將表的長度置為0*/   {   L-＞length=0;   }    該算法的時間復雜度為O(1)。

        2. 創(chuàng)建一個順序表L   算法2��2創(chuàng)建一個元素為整型數(shù)的順序表,元素不包括0,遇到0時表示輸入結束。順序表長度由用戶輸入的數(shù)據(jù)來決定。    void CreatList(SeqList *L)   {   int k=0;/*計數(shù)*/   DataType x;   scanf("%d",&x);   while(x!=0)/*依次從鍵盤輸入順序表元素,遇到0結束。*/   {   L->data\[k\]=x;   k++;   scanf("%d",&x);   }   L->length=k;   }    該算法的時間復雜度為O(n),其中n為該順序表中元素個數(shù)的規(guī)模。     思考：  若順序表長度為固定值,如何創(chuàng)建順序表？