第2章線性表

        第  2  章  線性表

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

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

       2.2線性表的順序存儲(chǔ)及運(yùn)算實(shí)現(xiàn)    線性表有兩種基本的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

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

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

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

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