數(shù)據(jù)結(jié)構(gòu)與算法 課件 第2章 線性表

第2章線性表

線性表是一種典型的線性結(jié)構(gòu)，是簡單而且常用的數(shù)據(jù)結(jié)構(gòu)。線性表的順序和鏈式存儲結(jié)構(gòu)以及基本運算的實現(xiàn)又是后面各章的基礎(chǔ)。1【本章重點】①線性表的定義和線性表的基本運算；②順序存儲和鏈式存儲的基本思想；③基于順序表和單鏈表基本運算的實現(xiàn)；④基于順序表和單鏈表基本運算的時間特性和空間特性。⑤順序表和鏈表之間的比較。2【本章難點】①關(guān)于順序表、單鏈表、循環(huán)鏈表和雙向鏈表的算法設(shè)計及應(yīng)用；②模塊之間參數(shù)傳遞的問題。3【本章內(nèi)容】線性表的邏輯結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)順序表與鏈表的比較習(xí)題242.1線性表的邏輯結(jié)構(gòu)線性表的定義

線性表是由n（n≥0）個元素組成的有限序列，n為線性表的長度。當(dāng)n=0時稱為空表，當(dāng)n>0時稱為非空表，記為L=(a1,…,ai-1,ai,ai+1,…,an)需要注意的幾點（1）線性表中各元素具有相同的特性（2）i是元素ai在線性表中的位序，即位置序號，位序從1開始（3）對于一個非空線性表，有且僅有一個開始結(jié)點a1；有且僅有一個終端結(jié)點an；除第一個結(jié)點外，其余結(jié)點ai（2≤i≤n)均有且僅有一個直接前驅(qū)ai-1；除最后一個結(jié)點外，其余結(jié)點ai（1≤i≤n-1)均有且僅有一個直接后繼ai+15線性表的基本運算（1）InitList(&L)線性表初始化

初始條件：線性表L不存在。

運算結(jié)果：構(gòu)造一個空的線性表。（2）SetNull(L)置空表，

初始條件：線性表L已存在。

運算結(jié)果：將表L置為空表。（3）Length(L)求表長度

初始條件：線性表L已存在。

運算結(jié)果：返回表L中的數(shù)據(jù)元素個數(shù)。6每一種數(shù)據(jù)的邏輯結(jié)構(gòu)，對應(yīng)一組基本運算。這里只是給出抽象的運算，而運算的具體實現(xiàn)，只有在確定了數(shù)據(jù)的存儲結(jié)構(gòu)之后才能夠考慮。（4）Get(L,i)取元素值

初始條件：線性表L已存在。

運算結(jié)果：返回表L中第i個數(shù)據(jù)元素ai的值或元素的位置信息。（5）Locate(L,x)定位，按值查找

初始條件：線性表L已存在。

運算結(jié)果：若表L中存在一個或多個值為x的元素，返回第一個查找到的數(shù)據(jù)元素的位序，否則返回一個特殊值。（6）Insert(L,x,i)插入

初始條件：線性表L已存在。

運算結(jié)果：在表L中第i個位置上插入值為x的元素，若插入成功，表長加1。（7）Delete(L,i)刪除

初始條件：線性表L已存在。

運算結(jié)果：刪除表L中第i個數(shù)據(jù)元素，若刪除成功，表長減1。7函數(shù)的參數(shù)L是指向線性表結(jié)構(gòu)體的指針。對線性表的基本運算可以分為三類，所對應(yīng)的函數(shù)參數(shù)是不同的。（1）線性表初始化運算使得線性表從不存在到存在，顯然指針L的指向發(fā)生了變化；（2）置空表、插入和刪除運算使得線性表的內(nèi)容發(fā)生了變化，但指針的指向并不會發(fā)生變化；（3）求表長度、取元素值和定位運算對于指針L和表的內(nèi)容都沒有發(fā)生變化?；具\算應(yīng)用的舉例【例2.1】將線性表A按元素值奇、偶數(shù)拆分成兩個表，A表存放奇數(shù)，B表存放偶數(shù)。voidseparate(Linear_list*La,Linear_list*Lb)//已有線性表La和空線性表Lb{

inti=1,j=1,x; while(i<=Length(La)) { x=Get(La,i);//取ai

if(x%2==0) { Insert(Lb,x,j); j++; Delete(La,i);

}//ai是偶數(shù)，插入到B表末尾，并從A表中刪除

elsei++;//ai是奇數(shù)，仍放在A表中

}}說明: （1）將偶數(shù)插入到B表，A表只保留奇數(shù)

（2）時間復(fù)雜度是O(Length(La))82.2線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)又稱為順序表，是把線性表的元素按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。順序表中元素地址的計算

假設(shè)順序表中每個元素占用c個存儲單元，其中的第一個單元的存儲地址則是該元素的存儲地址，順序表中開始元素a1的存儲地址是Loc(a1)，那么元素ai的存儲地址Loc(ai)可通過下式計算：Loc(ai)=Loc(a1)+(i-1)*c（1≤i≤n）

其中Loc(a1)是順序表的第一個元素a1的存儲地址，稱為順序表的起始地址或基地址?？梢詫樞虮眄樞虼嫒』螂S機存取。9順序表的結(jié)構(gòu)類型定義#definemaxsize1024typedefintdatatype;typedefstruct{ datatypedata[maxsize];//采用一維數(shù)組存儲線性表 intlast;//順序表當(dāng)前的長度}sequenlist;10線性表順序存儲的兩種方式

由于線性表結(jié)點的位序從1開始，而C語言中數(shù)組的下標從0開始，關(guān)于線性表中數(shù)據(jù)元素的位序（邏輯位置）和存放它的數(shù)組下標（物理位置）之間的關(guān)系通常有兩種處理方式。（1）從下標為0的數(shù)組元素開始存放，則結(jié)點的位序等于數(shù)組元素的下標加一。（2）從下標為1的數(shù)組元素開始使用，這樣結(jié)點的位序和數(shù)組的下標是相等的，使用起來會更簡單自然一些，下標為0的元素不用或用作其它用途。這里我們約定采用第一種方式。11位序=下標+1，下標=位序-1位序=下標若L是指向順序表的指針，則a1~an分別存儲在L->data[0]~L->data[L->last-1]中。L->data[i-1]是元素ai；L->last表示線性表當(dāng)前的長度?；具\算在順序表上的實現(xiàn)1、順序表的初始化

在函數(shù)中建立一個空順序表L，指針L從沒有指向順序表變?yōu)橹赶蛞粋€空表，顯然指針L的指向發(fā)生了變化。如何將這一變化的結(jié)果帶回到主調(diào)函數(shù)，我們給出以下三種方式，并進行比較。【算法2.1】通過函數(shù)返回值將結(jié)果帶回到主調(diào)函數(shù)。sequenlist*InitList(){ sequenlist*L=(sequenlist*)malloc(sizeof(sequenlist));//分配順序表的動態(tài)存儲空間 L->last=0;//將表的長度置為0 returnL;}//時間復(fù)雜度為O(1)12在函數(shù)中定義的指針指向順序表，指針作為函數(shù)的返回值?！舅惴?.2】采用指向指針的指針作為函數(shù)參數(shù)，通過函數(shù)的參數(shù)將結(jié)果帶回到主調(diào)函數(shù)。voidInitList(sequenlist**L){ *L=(sequenlist*)malloc(sizeof(sequenlist));//第二級指針*L指向順序表 *L->last=0;//將*L所指向的順序表長度置0}//時間復(fù)雜度為O(1)13第一級指針L指向第二級指針*L，L的指向沒有改變，而*L的指向發(fā)生了變化，函數(shù)運行結(jié)束，將*L的指向帶回到主調(diào)函數(shù)?！舅惴?.3】采用指針的引用作為函數(shù)參數(shù)，通過函數(shù)的參數(shù)將結(jié)果帶回到主調(diào)函數(shù)。voidInitList(sequenlist*&L)//指針的引用作為參數(shù){ L=(sequenlist*)malloc(sizeof(sequenlist)); L->last=0;}//時間復(fù)雜度為O(1)14參數(shù)的類型使用了C++語言中的指針類型的引用，從而可以將指針所指向的結(jié)構(gòu)體動態(tài)存儲帶回到主調(diào)函數(shù)。2、在順序表中插入一個元素

在線性表的第i（1≤i≤n+1）個位置上插入一個新結(jié)點x，并且使表的長度加一，即使 (a1,…,ai-1,ai,…an)變?yōu)殚L度是n+1的線性表 (a1,…,ai-1,x,ai,…an)15【算法2.4】在順序表的第i個位置上插入一個新結(jié)點x。intInsert(sequenlist*L,datatypex,inti)//將新結(jié)點插入順序表的第i個位置。插入成功，返回1；不成功，返回0{ if(L->last==maxsize){print("表已滿");return0;} elseif(i<1||i>L->last+1){print("非法插入位置");return0;} else{ for(j=L->last;j>=i;j--)L->data[j]=L->data[j-1];//結(jié)點后移 L->data[i-1]=x;//插入到L->data[i-1]中 L->last++;//表長度加1 return1;}}16

3、在順序表中刪除一個元素

將表的第i（1≤i≤n）個結(jié)點刪去，并且使表的長度減一。即使 (a1,…,ai-1,ai,ai+1,…an)變成長度為n-1的線性表 (a1,…,ai-1,ai+1,…an)17【算法2.5】刪除順序表的第i個結(jié)點。intDelete(sequenlist*L,inti)//刪除順序表的第i個結(jié)點。刪除成功，返回1；不成功，返回0{ intj; if((i<1)||(i>L->last)){print("非法刪除位置");return0;} else{

for(j=i;j<=L->last-1;j++)L->data[j-1]=L->data[j];//結(jié)點前移

L->last--;//表長度減1

return1； }}18

【例2.2】有順序表A和B，其表中元素按由小到大的順序排列。編寫一個算法將它們合并為順序表C，并且表C中的元素也按由小到大的順序排列。voidmerge(sequenlist*A,sequenlist*B,sequenlist*&C){//在函數(shù)中產(chǎn)生順序表C，為了將C的指向帶回到主調(diào)函數(shù)，參數(shù)采用指針的引用 if(A->last+B->last>maxsize)rintf("Error!\n"); else{ C=(sequenlist*)malloc(sizeof(sequenlist)); i=0; j=0; k=0; while(i<A->last&&j<B->last) if(A->data[i]<B->data[j]) C->data[k++]=A->data[i++]; else C->data[k++]=B->data[j++]; while(i<A->last) C->data[k++]=A->data[i++]; //將表A的剩余元素復(fù)制完 while(j<B->last) C->data[k++]=B->data[j++]; //將表B的剩余元素復(fù)制完 C->last=k; }}19順序表的應(yīng)用實例——一個完整的程序

問題的描述：首先建立一個順序存儲結(jié)構(gòu)的線性表，然后刪除順序表中所有值為x的結(jié)點。202.3線性表的鏈式存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)的線性表具有順序存取和隨機存取表中元素的優(yōu)點，同時，它也存在下列缺點：（1）插入、刪除操作時需要移動大量元素，效率較低；（2）最大表長難以估計，太大了浪費空間，太小了容易溢出。鏈式存儲結(jié)構(gòu)的線性表可以克服上述缺點，但是只能順序存取不能隨機存取。鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表。21

線性表采用單鏈表來表示，在內(nèi)存中用一組連續(xù)的或不連續(xù)的存儲單元來存儲線性表的數(shù)據(jù)元素，每個元素含有數(shù)據(jù)域（data）和一個指針域（next），這兩部分信息組成了單鏈表中的一個結(jié)點。22單鏈表單鏈表的結(jié)點類型定義typedef結(jié)點數(shù)據(jù)域類型datatype;typedefstructnode{ datatypedata; structnode*next;}linklist;linklist*head,*p; //head為頭指針，p為工作指針指針所指向的結(jié)點存儲空間是在程序執(zhí)行過程中生成和釋放的，故稱為動態(tài)存儲空間。在C語言中，通過下面兩個標準函數(shù)生成或釋放結(jié)點。

生成結(jié)點：p=(linklist*)malloc(sizeof(linklist));

釋放結(jié)點：free(p);必須通過指針來訪問結(jié)點，即用*p表示結(jié)點。用p->data和p->next，或者(*p).data和(*p).next表示結(jié)點的數(shù)據(jù)域和指針域。23關(guān)于鏈表的頭結(jié)點

單鏈表以及后面所討論的循環(huán)鏈表和雙向鏈表均可以帶頭結(jié)點或者不帶頭結(jié)點。24單鏈表的基本運算1、建立單鏈表

假設(shè)單鏈表結(jié)點的數(shù)據(jù)域類型是字符型，我們逐個輸入字符，并以換行符“\n”作為輸入結(jié)束標志。動態(tài)建立單鏈表通常有以下兩種方法。（1）頭插法建表

從空表開始，每次將輸入的字符作為新結(jié)點插入到表頭，鏈表中結(jié)點的次序與輸入字符的順序相反。用偽代碼描述單鏈表的建立過程：

251 建立只有頭結(jié)點的空表2 循環(huán)讀取字符，若不是換行符，則執(zhí)行循環(huán)體；若是換行符，則結(jié)束循環(huán)

2_1 產(chǎn)生新結(jié)點

2_2 將新結(jié)點插入到表頭，即作為單鏈表當(dāng)前的第一個結(jié)點3 返回單鏈表的頭指針【算法2.6】頭插法建立單鏈表linklist*CreateListF()//帶頭結(jié)點的頭插法，返回單鏈表的頭指針{ linklist*head,*p;charch;head=(linklist*)malloc(sizeof(linklist));//產(chǎn)生頭結(jié)點①head->next=NULL; while((ch=getchar())!='\n')//輸入abc{p=(linklist*)malloc(sizeof(linklist));//生成新結(jié)點②p->data=ch;//對結(jié)點的數(shù)據(jù)域賦值③p->next=head->next;//新結(jié)點的指針域指向原第一個結(jié)點④head->next=p;//修改頭結(jié)點的指針域⑤}returnhead;}26（2）尾插法建表【算法2.7】尾插法建立單鏈表linklist*CreateListR()//帶頭結(jié)點的尾插法，返回單鏈表的頭指針{ linklist*head,*p,*r;charch; head=(linklist*)malloc(sizeof(linklist)); //生成頭結(jié)點① head->next=NULL;//建立空表 r=head;//r指針指向頭結(jié)點

while((ch=getchar())!='\n')//輸入abc { p=(linklist*)malloc(sizeof(linklist));//生成新結(jié)點② p->data=ch;//將輸入的字符賦給新結(jié)點的數(shù)據(jù)域 r->next=p; //新結(jié)點插入表尾③ r=p; //r指針指向到表尾④ } r->next=NULL;//表尾結(jié)點的指針域置空⑤ returnhead;}//時間復(fù)雜度為O(n)272、單鏈表查找對單鏈表的查找只能從表頭開始順序查找。

（1）按序號查找

單鏈表的第一個結(jié)點的序號為1，第二個結(jié)點的序號為2，以此類推。

設(shè)單鏈表的長度為n，并且規(guī)定頭結(jié)點的位序為0，要查找第i個結(jié)點，僅當(dāng)1≤i≤n時，才能查找到；否則查找不到，返回NULL。

（2）按值查找

在單鏈表中查找是否存在給定查找值key的結(jié)點，若存在，則返回該結(jié)點的地址；否則返回NULL。283、單鏈表的插入

在單鏈表中插入結(jié)點，只需要修改指針的指向，不需要移動結(jié)點。

單鏈表只能做“后插”，不能做“前插”。算法2.11是在單鏈表的第i個結(jié)點之前插入一個新結(jié)點，必須先找到第i-1個結(jié)點并插入，即將“前插”變?yōu)椤昂蟛濉??！纠?.3】將值為x的新結(jié)點插入到遞增有序單鏈表中，使插入后該鏈表仍然有序。

先查找插入位置，然后插入新結(jié)點。在查找過程中，若遇到某個結(jié)點的元素值大于等于x，則在該結(jié)點之前插入新結(jié)點。在單鏈表中必須利用前驅(qū)指針將“前插操作”變?yōu)椤昂蟛宀僮鳌薄?94、單鏈表的刪除

在單鏈表中刪除一個結(jié)點，必須先查找到該結(jié)點的直接前驅(qū)結(jié)點，然后刪除該結(jié)點?！舅惴?.12】單鏈表的刪除voidDelete(linklist*L,inti)//在帶頭結(jié)點的單鏈表中刪除第i個結(jié)點{ p=Get(L,i-1);//調(diào)用算法2.9，找第i-1個結(jié)點① if(p!=NULL&&p->next!=NULL)//第i-1個結(jié)點和第i個結(jié)點均存在 { r=p->next;//r指向*p的后繼結(jié)點② p->next=r->next;//刪除結(jié)點*r③ free(r);//釋放結(jié)點*r所占的存儲空間 } elseprintf("第i個結(jié)點不存在");}30循環(huán)鏈表

循環(huán)鏈表的一種形式是單循環(huán)鏈表。其特點是單鏈表中最后一個結(jié)點的指針域指向頭結(jié)點或開始結(jié)點，整個鏈表形成一個環(huán)，從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點。31【例2.4】在單循環(huán)鏈表上實現(xiàn)將兩個線性表（a1,a2,…,am）和（b1,b2,…,bn）合并為一個循環(huán)鏈表（a1,…,am,b1,…,bn）的運算。（1）采用尾指針，為指針指向終端結(jié)點，在算法中沒有循環(huán)，算法的時間復(fù)雜度為O(1)。（2）采用頭指針，分別需要找到La表和Lb表的終端結(jié)點，需要兩個循環(huán)的并列，算法的時間復(fù)雜度為O(Length(La)+Length(Lb))。32雙向鏈表（雙向循環(huán)鏈表）

雙向鏈表結(jié)點的結(jié)構(gòu)體類型定義：typedefstructdnode{datatypedata; //data為結(jié)點的數(shù)據(jù)域structdnode*prior,*next;//prior和next分別是結(jié)點的前驅(qū)和后繼指針域}dlinklist;dlinklist*head;33雙向鏈表將頭結(jié)點和終端結(jié)點鏈接起來，構(gòu)成順時針和逆時針的兩個環(huán)。

雙向鏈表可以“后插”，也可以“前插”。【算法2.13】雙向鏈表的后插voidDInsertAfter(dlinklist*p,datatypex){//在帶頭結(jié)點的非空雙向鏈表中,將值為x的新結(jié)點插入*p之后

dlinklist*s=(dlinklist*)malloc(sizeof(dlinkl