第2章 線性表課件

第2章線性表

2.1線性表的基本概念

2.2線性表的順序存儲

2.3線性表的鏈式存儲

2.4線性表的應用

2.5有序表

本章小結

2.1線性表的基本概念

2.1.1線性表的定義

2.1.2線性表的運算

2.1.1線性表的定義

線性表是具有相同特性的數(shù)據(jù)元素的一個有

限序列。該序列中所含元素的個數(shù)叫做線性表的

長度，用n表示，吟0。

當n=0時,表示線性表是一個空表，即表中不包

含任何元素。設序列中第i（i表示位序）個元素為

^（1<1<0）0

線性表的一般表示為：

（a。％,??????盧口）

有手中B為第一個元素，又稱做表頭元素聲2為

(二個元素聲0為最后一個元素，又稱做表尾元

素。

例如，在線性表

(1,4,3,2,8,10)

中J為表頭元素J0為表尾元素。

2.1.2線性表的運算

線性表的基本運算如下：

(1)初始化線性表InitList(&L):構造一'個空的線性

表L。

(2)銷毀線，性表DestroyList(&L):釋放線，性表L占用

的內點空間。

(3)判線性表是否為空表ListEmpty(L):若L為空

表，則返回真,否則返回假。

(4)求線性表的長度ListLength(L):返回L中元素

個數(shù)。

(5)輸出線性表DispList(L):當線性表L不為空時,

順序顯示L中各結點的值域。

(6)求線性表L中指定位置的某個數(shù)據(jù)元素

GetEIem(L上&e):用e返回L中第i(l<i<ListLength(L))

個元素的值。

(7)定位查找LocateElem(L,e):返回L中第1個值域

與e相等的位序。若這樣的元素不存在，則返回值為0。

(8)插入數(shù)據(jù)元素ListInsert(&L》e):在L的第

i(l<i<ListLength(L)+1)個元素之前插入新的元素e,L

的長度增L

(9)刪除數(shù)據(jù)元素ListDelete(&L,i,&e):刪除L的第

i(lWiWListLength(L))個元素,并用e返回W值,L的長度

41o

例2.1假設有兩個集合A和B分別用兩個線性

表LA和LB表示，即線性表中的數(shù)據(jù)元素即為集合

中的成員。編寫一個算法求一個新的集合C=AUB,

即將兩個集合的并集放在線性表LC中。

解:本算法思想是:先初始化線性表LC,將LA的所

有元素復制到LC中，然后掃描線性表LB,若LB的當

前元素不在線性表LA中，則將其插入到LC中。算法

如下：

voidunionList(ListLA,ListLB,List&LC)

intlenajencj;

ElemTypee;

InitList(LC);

for(i=l;i<=ListLength(LA);i++)

/*將LA的所有元素插入到Lc中*/

{GetElem(LAJ,e);

ListInsert(LC,i?e);

)

lena=ListLength(LA);/*求線性表的長度*/

lenb=ListLength(LB);

for(i=l;i<=lenb;i++)

GetElem(LB,i,e);

/*取LB中第i個數(shù)據(jù)元素賦給e*/

if(!LocateElem(LA,e))

ListInsert(LC,++lena,e);

/*LA中不存在和e相同者，則插入到LC中*/

由于LocateElem(LA'e)運算的時間復雜度為

O(ListLength(LA)),所以本算法的時間復雜度為：

O(ListLength(LA)*ListLength(LB))o

2.2線性表的順序存儲

2.2.1線性表的順序存儲一順序表

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

2.2.1線性表的順序存儲一順序表

線性表的順序存儲結構就是:把線性表中的所

有元素按照其邏輯順序依次存儲到從計算機存儲

器中指定存儲位置開始的一塊連續(xù)的存儲空間中。

這樣，線性表中第一個元素的存儲位置就是指

定的存儲位置，第i+1個元素(10i0n?l)的存儲位置

緊接在第i個元素的存儲位置的后面。

假定線性表的元素類型為ElemType，則每個元

素所占用存儲空間大小(即字節(jié)數(shù))為

sizeof(ElemType),整個或性表所占用存儲空間的大

小為：

n*sizeof(ElemType)

其中表示線性表的長度。

下標位置線性表存儲空間存儲地址

0aiLOC(A)

18L2LOC(A)+sizeof(ElemType)

11

11

11

i-1aiLOC(A)+(i-l)*sizeof(ElemType)

1

11

11

1

n-1dnLOC(A)+(n-l)*sizeof(EIemType)

i

1i

1i

1

i

i

MaxSize-1iLOC(A)+(MaxSize-l)*sizeof(ElemType)

順序表示意圖

在定義一個線性表的順序存儲類型時，需要定義

一個數(shù)組來存儲線線表中的所有元素和定義一個整

型變量來存儲線性表的長度。

假定數(shù)組用data[MaxSize]表示，長度整型變量用

length表示，并采用結構體類型表示，則元素類型為通

用類型標識符ElemType的線性表的順序存儲類型可

描述如下：

typedefstruct

{ElemTypedata[MaxSize];

intlength;

}SqList;/*順序表類型*/

其中,data成員存放元素Jength成員存放線性表的

實際長度。

說明：由于C/C++中數(shù)組的下標從0開始，線性表的第i

個元素均存放順序表的第位置上。為了清楚，我們?yōu)樵谶?/p>

輯序列中的位置稱為邏輯位序，在順序表中的位置稱為物理

位序。

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

一旦采用順序表存儲結構，我們就可以用C/C++

語言實現(xiàn)線性表的各種基本運算。為了方便，假設

ElemType為char類型/吏用如下自定義類型語句：

typedefcharElemType;

建立順序表

其方法是將給定的含有n個元素的數(shù)組的

每個元素依次放入到順序表中，并將n賦給順

序表的長度成員。算法如下：

voidCreateList(SqList*&L,ElemTypea[]9intn)

/*建立順序表*/

(

inti;

for(i=0;i<n;i++)

L->data[i]=a[i];

L->length=n;

順序表基本運算算法

(1)初始化線性表InitList(L)

該運算的結果是構造一個空的線性表L。實際上只

需將length最員設置為0即可。

voidInitList(SqList*&L)〃引用型指針

{

L=(SqList*)malloc(sizeof(SqList));

/*分配存放線性表的空間刃

L->length=0;

}

本算法的時間復雜度為0(1)。

(2)銷毀線性表DestroyList(L)

該運算的結果是釋放線性表L占用的內存空間。

voidDestroyList(SqList*&L)

{

free(L);

本算法的時間復雜度為O⑴O

(3)判定是否為空表ListEmpty(L)

該運算返回一個值表示L是否為空表。若L為空

表，則返回1,否則返回0。

intListEmpty(SqList*L)

(

return(L->length=O);

本算法的時間復雜度為0(1)。

(4)求線性表的長度ListLength(L)

該運算返回順序表L的長度。實際上只需返回

length成員的值即可。

intListLength(SqList*L)

(

return(L->Iength);

}

本算法的時間復雜度為0(1)。

(5)輸出線性表DispList(L)

該運算當線性表L不為空時，順序顯示L中各元素的

值。

voidDispList(SqList*L)

{

inti;

if(ListEmpty(L))return;

for(i=O;i<L->length;i++)

printf(n%cn,L->data[i]);

printf(n\nn);

本算法中基本運算為for循環(huán)中的printf語句,

故時間復雜度為：

O(L?>length)或O(n)

(6)求某個數(shù)據(jù)元素值GetElem(Lje)

該運算返回L中第i(lWi0ListLength(L))個元素的值,

存放在e中。

intGetElem(SqList*L,inti,ElemType&e)

(

if(i<l||i>L->length)return0;

e=L->data[i-l];

return1;

本算法的時間復雜度為0(1)。

(7)按元素值查找LocateElem(L,e)

該運算順序查找第1個值域與e相等的元素的位序。若

這樣的元素不存在，則返回值為0。

intLocateElem(SqList*L,ElemTypee)

(

inti=0;

while(i<L->length&&L->data[i]!=e)i++;

if(i>=L->length)return0;

elsereturni+1;

本算法中基本運算為while循環(huán)中的i++語句，故時

間復雜度為：

O(L->length)或O(n)

(8)插入數(shù)據(jù)元素Listlnsert(LJ'e)

該運算在順序表L的第i個位置

(lWiWListLength(L)+l)上插入新的元素eo

思路：如果i值不正確,則顯示相應錯誤信息;

否則將順序表原來第i個元素及以后元素均后移

一個位置,騰出一個空位置插入新元素，順序表長

度增L

intListInsert(SqList*&L,inti,ElemTypee)

intj;

if(i<l||i>L->length+l)return0;

i-；/*修順序表邏輯位序轉化為elem下標即物理位序*/

for(j=L->length;j>i;j—)L->data[j]=L->data[j-1];

/*將data川及后面元素后移一個位置*/

L->data[i]=e;

L->length++;/*順序表長度增1*/

return1;

對于本算法來說,元素移動的次數(shù)不僅與表長

L?length=ii有關，而且與插入位置i有關:當i=n+l時，移

動次數(shù)為0;當i=l時，移動次數(shù)為小達到最大值。在

線性表四中共有n+1個可以插入元素的地方。假設

1

Pi(=是在第i個位置上插入一個元素的概率，則在

〃+1

長勺線性表中插入一個元素時所需移動元素

的平均次數(shù)為:

〃+1〃+i1n

Z25-，+1)=￡------(n—i+1)=—=0(")

?=1i=ln+12

因此插入算法的平均時間復雜度為O(n)o

(9)刪除數(shù)據(jù)元素ListDelete(LJ,e)

刪除順序表L中的第i(lWiWListLength(L))個元

素。

思路：如果i值不正確，則顯示相應錯誤信息；

否則將線性表第i個元素以后元素均向前移動一個

位置，這樣覆蓋了原來的第i個元素，達到刪除該元

素的目的，最后順序表長度減L

intListDelete(SqList*&L，inti,ElemType&e)

intj;

if(i<l||i>L->length)return0;

i-;/*將順序表邏輯位序轉化為elem下標即物理位序*/

e=L->data[i];

for(j=i;j<L->length-1;j++)L->data[j]=L->data[j+1];

/*將data[i]之后的元素前移一個位置*/

L->length—;/*順序表長度減1*/

returnX;

}

對于本算法來說，元素移動的次數(shù)也與表長n和

刪除元素的位置i有關:當i=n時，移動次數(shù)為0；當i=l

時，移動次數(shù)為n-L在線性表sq中共有n個元素可以

被刪除。假設Pi(Pi=與是刪除第i個位置上元素的概

率，則在長度為n的線標表中刪除一個元素時所需移

動元素的平均次數(shù)為：

〃n1n1

=22Pi~~(n-i)=-----=O(n)

i=ii=in2

因此刪除算法的平均時間復雜度為0(11)。

例2.2設計一個算法；尋x插入到一個有序

（從小到大排序）的線性表（順序存儲結構即順序

表）的適當位置上，并保持線性表的有序性。

解:先通過比較在順序表L中找到存放x的位

置i,然后將x插入到L.data[i]中，最后將順序表的

長度增L

voidInsert(SqList*&L,ElemTypex)

inti=0,j;

while(i<L->length&&L->data[i]<x)

.A查找插入位置

i++;

forO=L->length-l;j>=i;j-)

-元素后移一個位置

L->data[j+l]=L->data[j];

L->data[i]=x;

L->length++;

L[0]L[l]...L[i]L[i+1]...L[n-1]

例2.3設計一個算法，臀兩個元素有序(從小

到大)的順序表合并成一個有序順序表。

思路:將兩個順序表進行二路歸并。例如：

加頁序表p:l,3,5<—i掃*苗p

順序表q:2,4,10,20—j掃描q

歸并到順序表r中―k記錄r中元素個數(shù)

l(i=0)o2(j=0)n將l(i=l)插入r(k=l)

3(i=l)o2(j=0)n4尋2(j=l)插入r(k=2)

3(i=l)o4(j=l)n1尋3(i=2)插入r(k=3)

5(i=2)o4(j=l)n1尋4(j=2)插入r(k=4)

5(i=2)o10(j=2)=>將5。=3)插入r(k=5)

將q中余下元素插入r中。

SqList*merge(SqList*p,SqList*q)

(

SqList*r;inti=OJ=O,k=O;

r=(SqList*)malloc(sizeof(SqList));

while(i<p->length&&j<q->length)

{if(p->data[i]<q->data[j])

{r->data[k]=p->data[i];

i++;k++;

)

else

{r->data[k]=q->data[j];

j++;k++;

while(i<p->length)

{r->data[k]=p->data[i];

i++;k++;

}

while(j<q->length)

{r->data[k]=q->data[j];

j++;k++;

}

r->length=k;/*或p->length+q?>length*/

return(r);

例2.4已知長度為n的線性表A采用順序存儲結

構，編寫一個時間復雜度為O(n)、空間復雜度為0(1)

的算法，該算法刪除線性表中而有值為item的數(shù)據(jù)元

素。

解:用k記錄順序表A中等于item的元素個數(shù)，邊

掃描A邊統(tǒng)計k,并將不為item的元素前移k個位置，最

后修改A的長度。對應的算法如下：

voiddelnodel(SqList&A,ElemTypeitem)

{intk=0,i；/*k記錄值不等于item的元素個數(shù)*/

for(i=0;i<A.length;i++)

算法L類似于

if(A.data[i]!=item)建順序表

A.data[k]=A.data[i];

k++;/*不等于item的元素增1*/

A.length=k;/*順序表A的長度等于k*/

voiddelnode2(SqList&A,ElemTypeitem)

{intk=0,i=0;/*k記錄值等于item的元素個數(shù)*/

while(i<A.length)二---

算法2

{if(A.data[i]==item)k++;-----------

elseA.data[i-k]=A.data[i];/*當前元素前移k個位置*/

i++；

A.length=A.length-k;/*順序表A的長度遞減*/

上述算法中只有一個while循環(huán),時間復雜度為

O(n)o算法中只用了i,k兩個臨時變量，空間復雜度為

O(l)o

2.3線性表的錢式存儲

2.3.1線性表的鏈式存儲一鏈表

2.3.2單鏈表基本運算的實現(xiàn)

2.3.3雙鏈表

2.3.4循環(huán)鏈表

235靜態(tài)鏈表

2.3.1線性表的鏈式存儲一鏈表

在鏈式存儲中，每個存儲結點不僅包含有所存元

素本身的信息（稱之為數(shù)據(jù)域）,而且包含有元素之間

邏輯關系的信息,即前驅結點包含有后繼結點的地址

信息，這稱為指針域,這樣可以通過前驅結點的指針域

方便地找到后繼結點的位置，提高數(shù)據(jù)查找速度。

一般地，每個結點有一個或多個這樣的指針域。

若一個結點中的某個指針域不需要任何結點,則僅它

的值為空，用常量NULL表示。

由于順序表中的每個元素至多只有一個前驅元素

和一個后繼元素,即數(shù)據(jù)元素之間是一對一的邏輯關

系，所以當進行鏈式存儲時，一種最簡單也最常用的方

法是：

在每個結點中除包含有數(shù)據(jù)域外,只設置一個指

針域陰以指向其后繼結點，這樣構成的鏈接表稱為線

性單向鏈接表，簡稱單鏈表；

在線性表的鏈式存儲中，為了便于插入和刪除算法

的實現(xiàn)，每個鏈表帶有一個頭結點，并通過頭結點的指

針惟一標識該鏈表。

頭結點開始結點終端結點

aia2

帶頭結點單鏈表示意圖

在單鏈表中，由于每個結點只包含有一個指向后

繼結點的指針，所以當訪問過一個結點后，只能接著

訪問它的后繼結點，而無法訪問它的前驅結點。

另一種可以采用的方法是:在每個結點中除包含

有數(shù)值域外,設置有兩個指針域，分別用以指向其前

驅結點和后繼結點，這樣構成的鏈接表稱之為線性

雙向鏈接表，簡稱雙鏈表。

頭結點開始結點終端結點

dhead—?aia2一:…an八

帶頭結點的雙鏈表示意圖

雙鏈表的特點

在雙鏈表中，由于每個結點既包含有一個指向后繼

結點的指針，又包含有一個指向前驅結點的指針，所

以當訪問過一個結點后，既可以依次向后訪問每一個

結點，也可以依次向前訪問每一個結點。

在單鏈表中,假定每個結點類型用LinkList表示，它

應包括存儲元素的數(shù)據(jù)域,這里用data表示/類型用

通用類型標識符ElemType表示，還包括存禧后繼元素

位置的指針域，這里用next表示。

LinkList類型的定義如下：

typedefstructLNode/*定義單鏈表結點類型*/

{ElemTypedata;

structLNode*next;/*指向后繼結點*/

}LinkList;

2.3.2單鏈表基本運算的實現(xiàn)

1.建立單鏈表

先考慮如何建立單鏈表。假設我們通過一個含有

n個數(shù)據(jù)的數(shù)組來建立單鏈表。建立單鏈表的常用

方法有如下兩種：

(1)頭插法建表

該方法從一個空表開始,讀取字符數(shù)組a中的字

符，生成新結點，將讀取的數(shù)據(jù)存放到新結點的數(shù)據(jù)

域中，然后將新結點插入到當前鏈表的表頭上，直到

結束為止。采用頭插法建表的算法如下：

voidCreateListF(LinkList*&L,ElemTypea[]Jntn)

{LinkList*s;inti;

L=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建頭結點*/

L->next=NULL;

for(i=0;i<n;i++)

{s=(LinkList*)malloc(sizeof(LinkList));

/*創(chuàng)建新結點*/

s->data=a[i];s->next=L->next;

/*將*s插在原開始結點之前,頭結點之后*/

L->next=s;

采用頭插法建立單鏈表的過程

adcb

第1步:建頭結點

head一八i=Oi=li=2i=3

第2步：i=0,新建a結點，插入到頭結點之后

head—----ka八

第3步:i=1,新建d結點，插入到頭結點之后

head—----kdka八

第4步:i=2,新建c結點，插入到頭結點之后

head-匚口~~k|C|]~~kd>aA

第5步：i=3,新建b結點,插入到頭結點之后

head一|~―?|"bl~―Hed-----a八

(2)尾插法建表

頭插法建立鏈表雖然算法簡單,但生成的鏈表

中結點的次序和原數(shù)組元素的順序相反。若希望

兩者次序一致，可采用尾插法建立。該方法是將

新結點插到當前鏈表的表尾上，為此必須增加一

個尾指針r,使其始終指向當前鏈表的尾結點。采

用尾插法建表的算法如下：

voidCreateListR(LinkList*&L,ElemTypea[],intn)

{LinkList*s,*r;inti;

L=(LinkList*)malloc(sizeof(LinkList));

/*創(chuàng)建頭結點*/

r=L;/*i?始終指向終端結點，開始時指向頭結點*/

for(i=0;i<n;i++)

{s=(LinkList*)malloc(sizeof(LinkList));

/*創(chuàng)建新結點*/

s->data=a[i];r->next=s;/*將*s插入*r之后*/

r=s;

r->next=NULL;/*終端結點next域置為NULL*/

采用尾插法建立單鏈表的過程

adcb

i=0i=li=2i=3

head—......ka---'d---kC--->b八

頭結點

2.插入結點運算

插入運算是將值為x的新結點插入到單鏈表

的第i個結點的位置上。先在單鏈表中找到第i.l

個結點，再在其后插入新結點。

單鏈表插入結點的過程如下圖所示。

pp

???—?a一一b

A

(a)插入前(b)s->next=p->next

(c)p->next=s(d)插入后

插入結點示意圖

3.刪除結點運算

刪除運算是將單鏈表的第i個結點刪去。先在單

鏈表中找至U第i?l個結點，再刪除其后的結點。刪除

單鏈表結點的過程如下圖所示。

p

ab

(a)刪除前

(b)p->next=p->next->next

(c)刪除后

刪除結點示意圖

4.線性表基本運算實現(xiàn)

(1)初始化線性表InitList(L)

該運算建立一個空的單鏈表和創(chuàng)建一個頭結點。

voidInitList(LinkList*&L)

L=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建頭結點*/

L->next=NULL;

(2)銷毀線性表DestroyList(L)

釋放單鏈表L占用的內存空間。即逐一釋放全部結點

的空間。

voidDestroyList(LinkList*&L)

{LinkList*p=L/q=p->next;

while(q!=NULL)

{free(p);

p=q;q=p->next;

}

free(p);

)

(3)判線性表是否為空表ListEmpty(L)

若單鏈表L沒有數(shù)據(jù)結點，則返回真,否則返回假。

intListEmpty(LinkList*L)

r

return(L->next==NULL);

(4)求線性表的長度ListLength(L)

返回單鏈表L中數(shù)據(jù)結點的個數(shù)。

intListLength(LinkList*L)

{LinkList*p=L;inti=0;

while(p->next!=NULL)

{i++；

p=p->next;

}

return(i);

(5)輸出線性表DispList(L)

逐一掃描單鏈表L的每個數(shù)據(jù)結點,并顯示各結點

的data域值o

voidDispList(LinkList*L)

{LinkList*p=L->next;

while(p!=NULL)

{printf(u%cn,p->data);

p=p->next;

printf(u\nn);

(6)求線性表L中指定位置的某個數(shù)據(jù)元素

GetElem(L9i,&e)

思路：在單鏈表L中從頭開始找到第i個結點，若

存在第i個數(shù)據(jù)結點,則將其data域值賦給變量e。

intGetElem(LinkList*L,inti,ElemType&e)

{intj=0;

LinkList*p=L;

while(j<i&&p!=NULL)

{j++；

p=p->next;

)

if(p==NULL)return0;/*不存在第i個數(shù)據(jù)結點*/

else/*存足第i個數(shù)據(jù)結點刃

{e=p->data;

return1;

(7)按元素值查找LocateElem(L,e)

思路：在單鏈表L中從頭開始找第1個值域與e相等的

結點，若存在這樣的結點，則返回位置，否則返回0。

intLocateElem(LinkList*L,ElemTypee)

{LinkList*p=L->next;intn=l;

while(p!=NULL&&p->data!=e)

{p=p->next;n++;}

if(p==NULL)return(O);

elsereturn(n);

(8)插入數(shù)據(jù)元素ListInsert(&LJ,e)

思路：先在單鏈表L中找到第i?l個結點*p,若存在這

樣的結點,將值為e的結點*s插入到其后。

intListInsert(LinkList*&L,inti,ElemTypee)

{intj=0;

LinkList*p=L,*s;

whileQ<i-1&&p!=NULL)/*查找第i-l個結點*/

{J++；

p=p->next;

if(p==NULL)return0;/*未找到位序為i-1的結點*/

else/*找到位序為i-1的結點*p*/

{s=(LinkList*)malloc(sizeof(LinkList));

/*創(chuàng)建新結點*s*/

s->data=e;

s->next=p->next;/*臀*s插入到*p之后*/

p->next=s;

return1;

(9)刪除數(shù)據(jù)元素ListDelete(&L』,&e)

思路：先在單鏈表L中找到第i-1個結點*p,若存在這

樣的結點，且也存在后繼結點，則刪除該后繼結點。

intListDelete(LinkList*&L,inti,ElemType&e)

{intj=0;

LinkList*p=L，*q;

while(j<i-l&&p!=NULL)/*查找第i-1個結點*/

{J++；

p=p->next;

if(p==NULL)return0;/*未找到位序為i4的結點*/

else/*找至U位序為i-1的結點*p*/

{q=p->next;/*q指向要刪除的結點*/

if(q==NULL)return0;

/*若不存在第i個結點，返回0*/

p->next=q->next;/*從單鏈表中刪除*q結點*/

free(q);/*釋放*q結點*/

return1;

例2?5設?=但］孫/2力2,…#1Pbn｝為一線性表,

采用帶頭結點的he單鏈表存放,編寫一個算法，將

其拆分為兩個線性表/吏得：

A一但］聲2八?”\},B-{bpb?,..”幾}

解：設拆分后的兩個線性表都用帶頭結點的單鏈表

存放。

先建立兩個頭結點*ha和*hb,它們用于存放拆分后

的線性表A和Bja和rb分別指向這兩個單鏈表的表尾,

用p指針掃描單鏈表he,將當前結點*p鏈到ha未尾,p沿

next域下移一個結點，若不為空，則當前結點*p鏈到hb未

尾,p沿next域下移一個結點，如此這樣，直到p為空。最

后圈兩個尾結點的next域置空。

對應算法如下：

voidfun(LinkList*hc,LinkList*&ha,LinkList*&hb)

LinkList*p=hc->next,*ra,*rb;

ha=hc;/*ha的頭結點利用he的頭結點*/

ra=ha;/*ra始終指向ha的末尾結點*/

hb=(LinkList*)malloc(sizeof(LinkLi§t));/*創(chuàng)建hb頭結點*/

rb=hb;/*rb始終指向hb的末尾結點*/

while(p!=NULL)

{ra->next=p;ra=p;/*將*p鏈到ha單鏈表未尾*/

p=p->next;

if(p!=NULL)

{rb->next=p;

rb=p;/*將*p鏈到hb單鏈表未尾*/

p=p->next;

}

ra->next=rb->next=NULL;/*兩個尾結點的next域置空*/

本算法實際上是采用尾插法建立兩個新表。

所以，尾插法建表算法是很多類似習題的基礎！

例2.6有一個帶頭結點的單鏈表head,其

ElemType類型為char,設計一個算法使其元素遞增

有序。

解：若原單鏈表中有一個或以上的數(shù)據(jù)結點，

先構造只含一個數(shù)據(jù)結點的有序表（只含一個數(shù)

據(jù)結點的單鏈表一定是有序表）。掃描原單鏈表

余下的結點*p（直到p==NULL為止），在有序表中通

過比較找插入*p的前驅結點*q,然后將*p插入到

*q之后（這里實際上采用的是直接插入排序方法）。

voidSort(LinkList*&head)

{LinkList*p=head->next,*q/r;

if(p!=NULL)/*head有一個或以上的數(shù)據(jù)結點*/

{r=p->next;/*r保存*p結點后繼結點的指針*/

p->next=NULL;

/*構造只含一個數(shù)據(jù)結點的有序表*/

P=r；

while(p!=NULL)

{r=p->next;

/*r保存*p結點后繼結點的指針*/

q=head;

while(q->next!=NULL&&q->next->data<p->data)

q=q->next;/*在有序表中找插入*p的前驅結點*q*/

p->next=q->next;/*將*p插入到*q之后*/

q->next=p;

p=r;/*掃描原單鏈表余下的結點*/

2.3.3雙鏈表

對于雙鏈表，采用類似于單鏈表的類型定義，其

DLinkList類型&勺定義如下：

typedefstructDNode/*定義雙鏈表結點類型*/

{ElemTypedata;

structDNode"prior;/*指向前驅結點*/

structDNode*next;/*指向后繼結點*/

}DLinkList;

在雙鏈表中，有些操作如求長度、取元素值和查

找元素等操作算法與單鏈表中相應算法是相同的，這

里不多討論。但在單鏈表中，進行結點插入和刪除時

涉及到前后結點的一個指針域的變化。而在雙鏈表

中，結點的插入和刪除操作涉及到前后結點的兩個指

針域的變化。

pp

AA

(a)插入前

(c)p->next->prior=s

(e)p->next=s(f)插入后

雙鏈表中插入結點示意圖

歸納起來，在雙鏈表中P所指的結點之后插入

一個*S結點。其操作語句藉述為：

s->next=p->next;/*將*s插入到*p之后*/

p->next->prior=s;

s->prior=p;

p->next=s;

p

(a)刪除前

在雙鏈表

中刪除一個

(b)p->next=p->next->next或p->next=q->next

結點的過程

如右圖所示:

(c)q->next->prior=p

^~n^FT

(d)刪除后

刪除結點示意圖

歸納起來,刪除雙鏈表L中*p結點的后續(xù)結點。

其操作語句描述為：

p->next=q->next;

q->next->prior=p;

2.3.4循環(huán)鏈表

循環(huán)鏈表是另一種形式的鏈式存儲結構。它的

特點是表中最后一個結點的指針域不再是空，而是

指向表頭結點，整個鏈表形成一個環(huán)。由此,從表中

任一結點出發(fā)均可找到鏈表中其他結點。

頭結點開始結點終端結點

(a)循環(huán)單鏈表

dhead—?

(b)循環(huán)雙鏈表

帶頭結點的循環(huán)單鏈表和循環(huán)雙鏈表的示意圖

例2.7編寫出判斷帶頭結點的雙向循環(huán)鏈表L是

否對稱相等的算法。

解:p從左向右掃描L5q從右向左掃描L,若對應數(shù)

據(jù)結點的data域不相等則退出循環(huán)，否則繼續(xù)比較,

直到p與q相等或p的下一個結點為*q為止。對應算

法如下：

intEqueal(DLinkList*L)

{intsame=l;

DLinkList*p=L->next;/*p指向第一個數(shù)據(jù)結點*/

DLinkList*q=L->prior;/*q指向最后數(shù)據(jù)結點*/

while(same==l)

if(p->data!=q->data)same=O;

else

(

if(p==q)break;/*數(shù)據(jù)結點為奇數(shù)的情況*/

q=q->prior;

if(p==q)break;/*數(shù)據(jù)結點為偶數(shù)的情況*/

p=p->next;

}

returnsame;

2.3.5靜態(tài)鏈表

靜態(tài)鏈表借用一維數(shù)組來描述線性鏈表。數(shù)組中

的一個分量表示一個結點，同時使用游標（指示器cur即

為偽指針）代替指針以指示結點在數(shù)組中的相對位置。

數(shù)組中的第0個分量可以看成頭結點，其指針域指示靜

態(tài)鏈表的第一個結點。

這種存儲結構仍然需要預先分配一個較大空間，但

是在進行線性表的插入和刪除操作時不需要移動元素,

僅需要修改“指針”，因此仍然具有鏈式存儲結構的主

要優(yōu)點。

下圖給出了一個靜態(tài)鏈表的示例。圖(a)是一個修改之前

的靜態(tài)鏈表，圖(b)是刪除數(shù)據(jù)元素“陳華”之后的靜態(tài)鏈表，圖

(c)插入數(shù)據(jù)元素“王華”之后的靜態(tài)鏈表，圖中用陰影表示修

改的游標。

數(shù)據(jù)域游標域數(shù)據(jù)域游標域數(shù)據(jù)域游標域

010101

1張斌21張斌21張斌2

2劉麗32劉麗3在“劉麗”之后2劉麗8

3李英4刪除“陳華”3李英5插入“王華”3李英5

4陳華5--------?4陳華5-------?4

5王奇65王奇65王奇6

6董強76董強76董強7

7王萍07王萍07王萍0

888k華3

999

(a)(b)(c)

2.4線性表的應用

計算任意兩個表的簡單自然連接過程討論線性

表的應用。假設有兩個表A和B,分別是ml行、nl列

和m2行、n2列，它們簡單自然連接結果C=AD<|B,其

i=j

中i表示表A中列號j表示表B中的列號,C為A和B的

笛卡兒積中滿足指定連接條件的所有記錄組,該連接

條件為表A的第i列與表B的第j列相等。例如：

-123一一35

A=233B=16

11134

C=AMB的計算結果如下:

3=1

12335

12334

23335

23334

11116

由于每個表的行數(shù)不確定，為此，用單鏈表作為表

的存儲結構,每行作為一個數(shù)據(jù)結點。另外,每行中的

數(shù)據(jù)個數(shù)也是不確定的,但由于提供隨機查找行中的

數(shù)據(jù)，所以每行的數(shù)據(jù)采用順序存儲結構,這里用長度

為MaxCol的數(shù)組存儲每行的數(shù)據(jù)。因此，該單鏈表

中數(shù)據(jù)結點類型定義如下：

#defineMaxCol10/*最大列數(shù)*/

typedefstructNodel/*定義數(shù)據(jù)結點類型*/

{ElemTypedata[MaxCol];

structNodel*next;/*指向后繼數(shù)據(jù)結點*/

}DList;

另外，需要指定每個表的行數(shù)和列數(shù)，為此將單鏈

表的頭結點類型定義如下：

typedefstructNode2/*定義頭結點類型*/

{intRow,Col;/*行數(shù)和歹U數(shù)*/

DList*next;/*指向第一個數(shù)據(jù)結點*/

}HList;

采用尾插法建表方法創(chuàng)建單鏈表，用戶先輸入表的

行數(shù)和列數(shù)然后輸入各行的數(shù)據(jù)，為了簡便，假設表中

數(shù)據(jù)為int型，因此定義：

typedefintElemType;

對應的建表算法如下：

voidcreate(HList*&h)

{inti,j;DList

h=(HList*)malloc(sizeof(HList)