2.2線性表

2.2.1線性表的定義及操作定義2-1線性表(Linear-list)是n(n≥0)個數據元素的有限序列（一對一）。記為：

(a1，a2,...,an)

其中，數據元素個數n稱為表的長度，n=0時，稱此線性表為空表。線性表的結構僅涉及諸元素的線性相對位置，即第i個元素ai處在第i-1個元素ai-1的后面和第i+1個元素ai+1的前面，這種位置上的有序性就是一種線性關系，所以線性表是一種線性結構。線性表中每個數據元素ai的具體含義，在不同情況下各不相同，它可以是一個數，或是一個符號，也可以是一頁書，甚至是其它更復雜的信息。但在同一個線性表中的數據元素必須具有相同的特性(或者說具有相同的類型)。

線性表的邏輯結構：若線性表是非空表，則第一個元素a1無前驅（前件）（只有一個根結點或首結點），最后一個元素an無后繼（后件），其它元素ai(1<i<n)均只有一個直接前驅ai-1和一個直接后繼ai+1。下面給出幾個線性表的例子：

例2-126個大寫的英文字母表：(A，B，C，...，Z)

例2-2

某校從1996年到2002年各種型號計算機擁有量的變化情況，可以用線性表給出：

(200，220，250，300，400，700，1200)

例2-3

某單位職工政治面貌登記表如表2-2所示，每個職工的情況為一條記錄，它由職工號、姓名、性別、職稱、工齡、政治面貌六個數據項組成。在表2-2中，一個數據元素由若干個數據項組成。在這種情況下，常把數據元素稱為記錄，含有大量記錄的線性表又稱為文件。表2-2職工政治面貌登記表

職工號姓名性別職稱工齡政治面貌

000100020003…張忠王平李林…男女男…工程師助工助工…1222…黨員團員團員…

線性表是一個相當靈活的數據結構，它的長度可以根據需要增減，操作也比較靈活方便。線性表的基本操作有以下幾種：

(1)INITIATE(L)。初始化操作，設定一個空的線性表L。

(2)LENGTH(L)。求表長，求出線性表L中數據元素個數。

(3)GET(L，i)。取元素函數，若1≤i≤LENGTH(L)，則函數值為給定線性表L中第i個數據元素，否則為空元素NULL。

(4)PRIOR(L，elm)。求前趨函數，若elm的位序大于1，則函數值為elm的前趨，否則為空元素。

(5)NEXT(L，elm)。求后繼函數，若elm的位序小于LENGTH(L)，則函數值為elm的后繼，否則為空元素。

(6)LOCATE(L，x)。定位函數，返回元素x在線性表L中的位置。若L中有多個x，則只返回第一個x的位置，若在L中不存在x，則返回0。

(7)INSERT(L，i，x)。插入操作，在線性表L中的第i個位置上插入元素x，運算結果使得線性表的長度增加1。

(8)DELETE(L，i)。刪除操作，若1≤i≤LENGTH(L)，刪除給定線性表L中的第i個數據元素，使得線性表的長度減1。

(9)EMPTY(L)。判空表函數，若L為空表，則返回布爾值“true”，否則返回布爾值“false”。對線性表還有一些更為復雜的操作，如將兩個線性表合并成一個線性表；把一個線性表拆分成兩個或兩個以上的線性表；重新復制一個線性表；對線性表中的元素按值的大小重新排序等。這些運算都可以通過上述基本運算來實現。

2.2.2線性表的順序存儲結構在計算機內可以用不同的方式來表示線性表，其中最簡單和最常用的方式是用一組地址連續的存儲單元依次存儲線性表中的元素。圖2-2線性表順序存儲結構示意圖(設每個數據元素占有1個存儲單元)

線性表的順序存儲結構就是將線性表的元素按其邏輯次序依次存放在一組地址連續的存儲單元里。

(1)設有線性表(a1，a2，...，an)，若1個數據元素只占1個存儲單元，則這種分配方式如圖2-2所示。若用Loc表示某元素的地址，則線性表中第i個數據元素的存儲地址為：

Loc(ai)=Loc(a1)+(i-1)

其中，Loc(a1)是線性表第一個數據元素的存儲地址，通常稱做線性表的起始地址或者基地址。

(2)若1個數據元素占d個存儲單元，則有

Loc(ai)=Loc(a1)+(i-1)*dLoc(ai+1)=Loc(ai)+d

可見，線性表中每個元素的存儲地址是該元素在表中序號的線性函數。只要確定了線性表的起始地址，線性表中任一數據元素都可以隨機存取，所以線性表的順序存儲結構是一種隨機存取的存儲結構。

順序存儲結構是以元素在計算機內“物理位置相鄰”來表示線性表中數據元素之間相鄰的邏輯關系。即順序存儲結構線性表的邏輯關系的存儲是隱含的。線性表的順序存儲結構通常稱為向量(Vector)。可用字母V來表示，用V［i］表示向量V的第i個分量，設向量下界為1，上界為線性表的長度n（i=1~n），則可以用此向量來表示長度為n的線性表。向量的第i個分量V［i］是線性表的第i個數據元素ai在計算機內存中的映像。

在C語言中，向量即一維數組，所以可用一維數組來描述順序存儲結構。#definemaxlen100

typedef

int

datatype;struct

sqlisttp

{

int

elem[maxlen];datatype

elem[maxlen];

intlast;};

其中，

maxlen是線性表的最大長度，它可以根據實際需要而修改。這里假設線性表的數據元素是整數，當然也可以根據需要取其它類型,甚至還可以是一種結構(即每個數據元素有多個數據項)。數據域elem描述了線性表中數據元素占用的數組空間，線性表的各個元素a1，a2，…，an依次存放在一維數組elem的各個分量elem[1]，elem[2]，…，elem[n]中。數據域last指示最后一個數據元素在數組中的相對位置。在這種存儲結構中，線性表的某些操作很容易實現。如線性表的長度即為last域的值等。下面著重討論線性表的插入和刪除兩種操作。

算法2-1

線性表的插入算法。已知線性表的當前狀態是(a1，a2，…，ai-1，ai，…，an)，要在第i個位置插入一個元素x，線性表變為(a1，a2，…，ai-1，x，ai，…，an)。其實施步驟為：

(1)

將第n至第i個元素后移一個存儲位置；

(2)

將x插入到第i個位置；

(3)

線性表的長度加1。…..a2a1an…..ai+1ai01i-1in-1在線性表的第i個元素之前插入一個新的元素，先移動，后插入。ai-1…..a2a1alast…ai+1aixai-1…..a2a1

aiai+1…alast

alast……ai+1

aix#definemaxlen100struct

sqlisttp{/*定義了sqlisttp型的結構

int

elem[maxlen];/*maxlen=n,elem=a*/

intlast;/*last=length*/};sqlisttp

v;/*定義了sqlisttp型的結構對象v

voidinsert(sqlisttp

v,int

i,int

x){intk;

if(i<1||i>v.last+1)

printf(''插入位置不合適！\n'');

elseif(v.last>=maxlen-1)

printf(''線性表已滿！\n''); else {for(k=v.last-1;k>=i-1;k--)

v.elem[k+1]=v.elem[k];

v.elem[i-1]=x;

v.last++; }}

算法2-2

線性表的刪除算法。已知線性表的當前狀態是(a1，a2，…，ai-1，ai，ai+1，…，an)，若要刪除第i個元素ai，則線性表成為(a1，a2，…，ai-1，ai+1，…，an)。具體實施步驟為：

(1)

若i值合法，則將第i+1至第n個位置上的元素依次向前移動一個存儲單位；

(2)

將線性表的長度減1。…..a2a1an…..ai+1ai01i-1in-1刪除線性表的第i個元素，后面所有元素前移。ai-1…..a2a1alast…ai+1aiai-1…..a2a1

aiai+1…alast刪除結點aiai+1…alast#definemaxlen100struct

sqlisttp{

int

elem[maxlen];

intlast;};sqlisttp

v;

voiddelete(sqlisttp

v,int

i){intk;

if(i<1||i>v.last)/*存取v的結構成員last

printf(''刪除位置不合適！\n'');

else { for(k=i;k<=v.last-1;k++)

v.elem[k-1]=v.elem[k];

v.last--; }}從上述算法中不難看出，當在順序存儲結構的線性表中某個位置上插入或刪除一個數據元素時，其時間主要耗費在移動元素上，而移動元素的個數取決于插入或刪除元素的位置。

假設在第i個元素之前插入一個新元素的概率為1/(n+1)，即在表的任何位置(包括an之后)插入新元素的概率是相等的，則插入操作中元素的平均移動次數(實際上就是時間復雜度)為：

T=

對于刪除操作，假定對長度為n的線性表，在表的任何位置上刪除元素的概率是相等的，即等于1/n，則刪除操作中元素的平均移動次數(即是時間復雜度)為：

T=

從以上分析可以看出，在順序存儲的線性表中進行插入或刪除操作，平均要移動一半的元素，即T(n)=O(n)。當線性表的元素很多，且每個元素的數據項較多時，花費在移動元素上的時間會很長。一般情況下，線性表的順序存儲結構適合于表中元素變動較少的線性表。

2.2.3線性表的鏈式存儲結構線性表的順序存儲結構的特點是邏輯關系上相鄰的兩個元素在物理位置上也是相鄰的。因此，可以隨機存取表中任一元素，它的存儲位置可用一個簡單、直觀的公式來表示。缺點：

在作插入或刪除操作時，需移動大量元素；在給長度變化較大的線性表預先分配空間時，必須按最大空間分配，使存儲空間不能得到充分利用；表的容量難以擴充。1．線性鏈表線性表的鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表中的數據元素，這組存儲單元可以是連續的，也可以是不連續的。這樣，邏輯上相鄰的元素在物理位置上就不一定是相鄰的，為了能正確反映元素的邏輯順序，就必須在存儲每個元素ai的同時，存儲其直接后繼元素的存儲位置。為克服線性表順序存儲結構的缺點，引進了另一種存儲結構——鏈式存儲結構。這時，存放數據元素的結點至少包括兩個域，一個域存放該元素的數據，稱為數據域(data)；另一個域存放后繼結點在存儲器中的地址，稱為指針域或鏈域(next)。這種鏈式分配的存儲結構稱為鏈表。datanext此結構的C語言描述為：struct

node{

intdata;

struct

node

*next;/*定義了指向node類型的結構指針 };typedef

structnodeNODE;

/*重新定義該結構類型的新名字NODE}NODE；數據元素的結點結構如下：一般情況下，鏈表中每個結點可以包含若干個數據域和指針域。若每個結點中只有一個指針域，則稱此鏈表為線性鏈表或單鏈表，否則被稱為多鏈表。例2-4

設有線性表由動物名組成：(cat,horse,monkey,elephant,pig,panda)。

它的物理狀態如圖2-3所示。當鏈表采用圖2-3來表示時，邏輯上的順序不易觀察，所以經常把鏈表用圖2-4所示的邏輯狀態來表示。圖2-4線性鏈表的邏輯狀態示意圖圖2-3線性鏈表的物理狀態示意圖

在圖2-4中，指針域的值用箭頭代替了，線性鏈表結點的相鄰關系用箭頭來指示，邏輯結構的表示非常形象、清晰。在此單鏈表中，head是指向單鏈表中第一個結點的指針，我們稱之為頭指針；最后一個元素panda所在結點不存在后繼，因而其指針域為“空”(用NULL或∧

表示)。可以看出，用線性鏈表表示線性表時，數據元素之間的邏輯關系是由結點中的指針指示的，邏輯上相鄰的兩個數據元素其存儲的物理位置不要求相鄰，因此，這種存儲結構為非順序映像或鏈式映像。在使用中，我們只關心數據元素的邏輯次序而不必關心它的真正存儲地址。通常，我們在單鏈表第一個元素所在的結點之前附設一個結點——頭結點（增加的目的是統一空表與非空表的處理）。頭結點的指針域存儲第一個元素所在結點的存儲位置；頭結點的數據域可以不存儲任何信息，也可以存儲如線性表的長度等附加信息。若線性表為空表，則頭結點的指針域為“空”，如圖2-5所示。

圖2-5帶頭結點的單鏈表

2．線性鏈表的運算線性鏈表是線性表的鏈式存儲表示，所以對線性鏈表的運算與前面所介紹的對線性表的運算相同，只是相應的算法與順序存儲的線性表有所不同。設head為單鏈表的表頭指針。下面主要介紹對帶頭結點單鏈表的查找、插入、刪除等常用操作的算法。對鏈表操作時，最基本的操作為插入、刪除運算。在討論插入、刪除操作之前，首先要解決插入時的新結點從何處取出，刪除后的結點又往何處送的問題。在采用鏈接分配時，總存在一個可利用的內存空間稱為可利用空間表，至于可利用空間表是怎樣生成的，可以有不同的方法，這里不再介紹。假設可利用空間表總是可以滿足存儲要求的。這樣，每當要調用新結點時就到這個可利用空間表里去取，刪除時就把結點歸還給這個可利用空間表。在C語言的編程實現時，申請與釋放一結點對應于C語言中兩個標準函數malloc(sizeof(NODE))和free(p)。

(1)malloc

是從可利用空間表中調用一新結點，并返回該結點的地址。

(2)free(p)將p指向的結點歸還給可利用空間表。為方便起見，以后把指針型變量p所指向的結點稱為p結點。

1)單鏈表的查找由于鏈表存儲結構不是一種隨機存取結構，要查找單鏈表中的一個結點，必須從頭指針出發，沿結點的指針域逐個往后查找，直到找到要查找的結點為止。

算法2-3

在帶頭結點的單鏈表中找出第i個元素所在的結點。NODE*get(NODE*head,inti){ NODE*p;/*等同于structnode*p

intcounter=1;p=head->next;/*通過指針訪問結構的成員時必須使用操作符->while((p!=NULL)&&(counter<i)) { p=p->next; counter++;

}if((p!=NULL)&&(counter=i))/*找到,1<=i<=n*/ returnp;else returnNULL;/*找不到,i>n或i<=0*/}注意（1）需事先定義NULL的具體數值，比如：

#defineNULL-1

（2）上述算法的平均時間復雜度為：

T(n)=O(n)。

2)單鏈表的插入設有線性表(a1，a2，...，ai-1，ai，...，an)，用帶頭結點的單鏈表存儲，頭指針為head，要求在線性表中第i個元素ai之前插入一個值為x的元素，線性表變為(a1，a2，…，ai-1，x，ai，…，an)。

插入前單鏈表的邏輯狀態如圖2-6所示。

圖2-6帶頭結點單鏈表的邏輯狀態

為插入數據元素x，

(1)

首先要生成一個數據域為x的新結點s；

(2)

然后確定插入位置，即找到ai之前的元素

ai-1，并使指針p指向之；

(3)

最后改變鏈接，將x插在ai-1與ai之間，修改結點p和結點s的指針域。即

s->next=p->next；p->next=s。插入結點s后單鏈表的邏輯狀態如圖2-7所示。圖2-7在單鏈表中插入結點S

算法2-4voidinsert(NODE*head,inti,intx){ NODE*p,*s;

intj=0; p=head; while((p!=NULL)&&(j<i-1)) { p=p->next; j++; }

if((p==NULL)||(j>i-1))

printf(''i值不合法\n'');/*找不到,i>n或i<=0*/ else { s=(NODE*)malloc(sizeof(NODE));/**/ s->data=x;/**/ s->next=p->next;/**/ p->next=s;/**/ } }

如果事先告之p指針所指的位置，則這種在p指針后插入一個元素算法的時間復雜度T(n)=O(1)，否則平均時間復雜度T(n)=O(n)。

3)單鏈表的刪除刪除操作和插入操作一樣，

(1)首先要搜索單鏈表以找到指定刪除結點的前趨結點(假設為p)；

(2)然后改變鏈接，即只要將待刪除結點的指針域內容賦予p結點的指針域即可。設有線性表(a1，a2，...，ai-1，ai，ai+1，...，an)，用帶頭結點的單鏈表存儲，刪除前的邏輯狀態如圖2-8所示。

刪除元素ai所在的結點之后，單鏈表的邏輯狀態如圖2-9所示。圖2-8帶頭結點的單鏈表圖2-9在單鏈表中刪除一個結點算法2-5voiddelete(NODE*head,inti){ NODE*p,*s;

intj=0; p=head; while((p->next!=NULL)&&(j<i-1)) {p=p->next; j++;}

if((p->next==NULL)||(j>i-1))

printf(“i值不合法\n”);/*找不到,i>n或i<=0*/ else {s=p->next; p->next=s->next; free(s); } }

如果事先告之p指針所指的位置，則這種在p指針后刪除一個元素算法的時間復雜度T(n)=O(1)，否則平均時間復雜度T(n)=O(n)。

4)動態建立單鏈表的算法要對單鏈表進行操作，首先要掌握怎樣建立單鏈表。鏈表是一種動態存儲結構，所需的存儲空間只有在程序執行malloc之后，才可能申請到一個可用結點空間；free(p)的作用是系統回收一個結點，回收后的空間可以備作再次生成結點時用。整個可用存儲空間可為多個鏈表共同享用，每個鏈表占用的空間不需預先分配劃定，而是由系統應需求即時生成。因此，建立線性表的鏈式存儲結構的過程就是一個動態生成鏈表的過程。即從“空表”的初始狀態起，依次建立各元素結點，并逐個插入鏈表。動態建立線性表的鏈式存儲結構有兩種基本方法，分別適用于不同的場合。可根據所建鏈表結點的順序要求選擇采用一種方法。

單鏈表建立方法一：反向建立鏈表（頭插法）。

思想：若線性表的元素已順序存放在一維數組A[N]中，建表方法是從線性表的最后一個元素開始，從后向前依次插入到當前鏈表的第一個結點之前。算法2-6#defineNm/*m為鏈表中數據元素的個數,如m=10*/intA[N]; NODE*creatlink1(){ NODE*head,*s;

inti; head=(NODE*)malloc(sizeof(NODE));/*生成頭結點*/ head->next=NULL;/*置空表*/ for(i=N-1;i>=0;i--)/*插入10個數據*/

{ s=(NODE*)malloc(sizeof(NODE));/*生成新結點*/ s->data=A[i];/*將輸入數據放入新結點數據域*/ s->next=head->next;/*新結點與原首結點鏈接*/ head->next=s;/*將新結點插入到表頭*/ } returnhead;/*返回單鏈表頭指針*/}算法的時間復雜度為：T(n)=O(n)

單鏈表建立方法二：正向建立單鏈表（尾插法）。

思想：依次讀入線性表的元素，從前往后依次將元素插入到當前鏈表的最后一個結點之后。圖B新結點*s插入到單鏈表head的尾上算法2-7NODE*creatlink2(){ NODE*head,*p,*s;

intnum; head=(NODE*)malloc(sizeof(NODE));/*生成頭結點*/

scanf(“%d”,&num);/*讀入第一個結點值*/ p=head;/*頭指針=尾指針*/ while(num!=0)/*輸入為0為輸入結束符*/

{ s=(NODE*)malloc(sizeof(NODE));/*生成新結點*/ s->data=num;/*新結點上填入輸入值*/ p->next=s;/*新結點*s插入到尾結點*p之后*/ p=s;/*尾指針p指向新的表尾*/

scanf(“%d”,&num);/*讀入下一個結點值*/ } p->next=NULL;/*將尾結點的指針置空*/ returnhead;/*返回單鏈表頭指針*/}算法的時間復雜度：T(n)=O(n)

3.線性鏈表算法示例

例2-5

求不帶頭結點的頭指針為head的單鏈表中的結點數目。解：

intlength(NODE*head) {NODE*p;

intj; p=head; j=0;while(p!=NULL) { p=p->next; j++; } returnj;}算法的平均時間復雜度：T(n)=O(n)

例2-6

設計算法：將一個帶頭結點的單鏈表A分解為兩個帶頭結點的單鏈表A和B，使得A表中含有原表中序號為奇數的元素，B表中含有原表中序號為偶數的元素，且保持其相對順序。解：voiddisA(NODE*A,NODE*B){ NODE*r,*p,*q; B=(NODE*)malloc(sizeof(NODE)); /*建立單鏈表B的頭結點*/ r=B; p=A->next; while((p!=NULL)&&(p->next!=NULL))

{ q=p->next; p->next=q->next; r->next=q; r=q; p=p->next; } r->next=NULL; p->next=NULL;}

例2-7

已知兩個不帶頭結點的單鏈表A、B分別表示兩個集合，其元素遞增有序。試設計算法求出A與B的交集C。要求C另外開辟存儲空間，并同樣以元素值遞增的帶頭結點的單鏈表形式存儲。解：voidintersectionset(NODE*A,NODE*B,NODE*C){ NODE*r,*p,*q,*s; C=(NODE*)malloc(sizeof(NODE)); r=C; p=A; q=B; while((p!=NULL)&&(q!=NULL)) { if(p->data<q->data)

p=p->next; elseif(p->data>q->data) q=q->next; elseif(p->data==q->data) { s=(NODE*)malloc(sizeof(NODE)); s->data=p->data;r->next=s; r=s; p=p->next; q=q->next; } } r->next=NULL;}

2.2.4循環鏈表和雙向鏈表

1.循環鏈表

如果鏈表最后一個結點的指針域指向頭結點，整個鏈表形成一個環，這樣的鏈表稱為循環鏈表。這樣，從表中任一結點出發均可找到表中其它結點，其邏輯狀態圖如圖2-10。圖2-10循環單鏈表

循環鏈表一般設表頭結點，這樣鏈表將永不為空，這將使空表和非空表的邏輯狀態及運算統一起來。循環鏈表的操作和線性鏈表基本一致，差別僅在于算法中的循環條件不是p或p->next是否為空，而是它們是否等于頭指針。與單鏈表比較，循環鏈表有以下特點：

(1)

在循環單鏈表中，從表中任何一個結點出發都能訪問到其它所有的結點；而單鏈表一般把頭指針作為入口點，從某一結點出發，只能訪問到其所有后繼結點。

(2)

循環單鏈表的空表判定條件是：

head->next=head。

2．雙向鏈表前面討論的鏈式存儲結構中只有一個指示直接后繼的指針域，所以從某結點出發只能順指針往后查找其它結點。若要查找結點的直接前趨，則應從頭指針出發(或在循環單鏈表中從p結點出發)一直往后找，直到結點q滿足q->next=p，那么q是p的前趨結點。為克服鏈表這種單向性的缺點，為有更大的靈活性來操作線性鏈表，可采用雙向鏈表存儲結構。在每個結點上增加另一個指向線性表中每個元素的前趨結點的指針域prior，就得到雙向鏈表。其結點的結構如