第二章 線性表課件

第二章線性表線性結(jié)構(gòu)的特點在數(shù)據(jù)元素的非空有限集中：

1、存在唯一的一個被稱為“第一個”的數(shù)據(jù)元素；

2、存在唯一的一個被稱為“最后一個”的數(shù)據(jù)元素；

3、除第一個之外，集合中的每個數(shù)據(jù)元素有且僅有一個直接前驅(qū)；

4、除最后一個之外，集合中的每個數(shù)據(jù)元素有且僅有一個直接后繼。線性表的概念及邏輯結(jié)構(gòu)線性表是ｎ個數(shù)據(jù)元素的有限序列。記為：

D={a1，a2，……an}

ai是一個抽象符號。同一線性表中元素具有相同性質(zhì)。相鄰數(shù)據(jù)元素間存在著序偶關(guān)系，可表示為：

R={〈ａi-1，ai〉│i=2..n}

〈ai-1，ai〉表示ai-1是ai直接前驅(qū)，ai是ai-1的直接后繼。線性表的長度：表中數(shù)據(jù)元素個數(shù)(ｎ≥0)。ｎ＝0表示空表。在非空表，每個元素都有確定的位置。ai是第i個元素，稱i為ai在線性表中的位序。元素間關(guān)系與元素具體內(nèi)容無關(guān)。線性表抽象數(shù)據(jù)類型描述ADT

List{

數(shù)據(jù)對象：D

數(shù)據(jù)關(guān)系；R

基本操作：

InitList(&L)：

初始化一個線性表

DestroyList(&L):撤消線性表

ClearList(&L)：

表置空操作

ListEmpty(L)：

判空表函數(shù)

ListLength(L)：

求線性表長度的函數(shù)

GetElem(L,i,&e)：

取第個i數(shù)據(jù)元素

LocateElem(L,x)：

定位函數(shù)

PriorElem(L,elm,&pre_e)：求元素elm的前驅(qū)

NextElem(L,elm,&next_e)：求元素elm的后繼

ListInsert(&L,i,e)：在第個i元素之前插入元素e

ListDelete(&L,i,&e)：刪除第i個元素

Listtraverse(L):遍歷線性表元素

}ADT

List

線性表的順序表示

存儲分配方式:

用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。設：

b為存儲空間的首地址

L為數(shù)據(jù)元素長度順序分配的實現(xiàn)：

#defineLIST_INIT_SIZE100#defineLISTINCREMENT10

typedef

struct{

ElemType*elem;

intLength;

int

Listsize;}sqlist;a1a2an空閑bb+Lb+(n-1)Lb+(Listsize-1)LelemLengthListsize線性表順序表示的特點

【特點1】邏輯上相鄰的元素ai和ai+1的存儲位置相鄰，即以結(jié)點“物理位置相鄰”來表示線性表中結(jié)點之間的邏輯關(guān)系。線性表的這種機內(nèi)表示稱為線性表的順序存儲結(jié)構(gòu)或順序映象。稱這種實現(xiàn)的線性表為順序表

【特點2】設第一個元素的存儲位置為線性表的開始位置，稱為基地址。每個結(jié)點的第一個單元地址作為結(jié)點的存儲地址。每個結(jié)點占L個存儲單元，結(jié)點ai的地址為loc(ai)，則有：

loc(ai)=loc(a1)+(i-1)*L

即只要確定了存儲線性表的起始地址，就直接確定了線性表中任一數(shù)據(jù)元素的存儲位置，從而實現(xiàn)對線性表元素的隨機存取(存取任一數(shù)據(jù)元素的存取時間都為一常數(shù))。該描述稱為公式化描述，用數(shù)學公式描述元素的存儲位置。

線性表順序表示的算法實現(xiàn)—初始化StatusInitlist_Sq(Sqlist&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE

*sizeof(ElemType);

if(!L.elem)exit(OVERFLOW);//存儲分配失敗

L.length=0;//空表長度為0

L.listsize=LIST_INIT_SIZE;//初始存儲容量

returnOK;}

元素ai對應著L.elem[i-1]。

L.length=0:表示為空表。

L.length=LIST_INIT_SIZE表示表滿。線性表的順序表示算法實現(xiàn)—基本操作撤銷線性表：

DestroyList_Sq(&L):{free(L.elem);L.elem=NULL;}清空線性表：

ClearList_Sq(&L)：{L.length=0;}求表長：

ListLength_Sq(L)：{return(L.length);}求第i個元素

：

GetElem_Sq(L,i,&e)：{e=L.elem[i-1];}線性表的順序表示算法實現(xiàn)—判表空

statusListEmpty_Sq(SqListL){if(L.length==0)return(TRUE);elsereturn(FALSE);}線性表的順序表示算法實現(xiàn)—定位函數(shù)

int

LocateElem_Sq(SqList

L,ElemTypee,Status(*compare)(ElemType,ElemType)){i=1;p=L.elem;

while(i<=L.length&&(*compare)(*p++,e))i++;if(i<=L.length)return(i);elsereturn(0);}

L.elem01i-1e算法時間復雜度：定位操作的平均比較次數(shù)為（1+2+3+…+n)/n=(n+1)/2，即算法時間復雜度為O(n)。

線性表順序表示的算法實現(xiàn)—求前驅(qū)和后繼

statusPriorElem_Sq(SqList

L,ElemType

e,ElemType&pre_e,Status(*compare)(ElemType,ElemType)){i=LocateElem_Sq(L,e,compare);if(i>=2){pre_e=L.elem[i-2];return(1);}elsereturn(0);}statusNextElem_Sq(SqList

L,ElemType

e,ElemType&next_e,Status(*compare)(ElemType,ElemType)){i=LocateElem_Sq(L,e,compare);if(i&&i<L.length){next_e=L.elem[i];return(1);}elsereturn(0);}

算法分析：算法的時間復雜度與定位函數(shù)的時間復雜度有關(guān)。即算法時間復雜度為O(n)。

線性表順序表示的算法實現(xiàn)—插入算法◆插入運算：在表的第i(1≤i≤n+1)個位置上，插入一個新結(jié)點x。假設插入前的狀態(tài)為：a1a2……ai-1ai……an

01i-2i-1n-1在第i個位置插入一個元素x后的狀態(tài)：

01i-2i-1ina1a2……ai-1xai……an后移一個位置插入后ai-1、ai的邏輯關(guān)系發(fā)生了變化，x成了ai-1的后繼，ai的前驅(qū)。在順序存儲結(jié)構(gòu)中也要反映其邏輯關(guān)系的變化，在物理位置上從ai到an都必須后移一個元素位置。

線性表順序表示的算法實現(xiàn)—插入算法算法思想：若i<=L.length，先將ai～an后移一個位置，然后插入。StatusListinsert_Sq(Sqlist&L,inti,Elemtypee){if(i<1‖i>L.length+1)returnERROR;//判斷i的正確性

if(L.length>=L.listsize)//判斷是否有空閑的存儲空間

{newbase=（ElemType*）realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)exit(OVERFLOW);

L.elem=newbase;

L.listsize+=LISTINCREMENT;}//擴展存儲空間

q=&(L.elem[i-1]);//需要后移的數(shù)據(jù)元素的開始位置

for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//移動元素*q=e;//插入

++L.length;//修改表的長度

returnOK;}線性表順序表示的算法實現(xiàn)—刪除算法◆刪除運算：刪除表的第i(1≤i≤n)個元素。

刪除前的狀態(tài)為：a1a2……ai-1aiai+1……an

01i-2i-1in-1刪除第i個元素后的狀態(tài)：

01i-2i-1n-2a1a2……ai-1ai+1

……an前移一個位置

刪除第i個結(jié)點后ai-1,ai+1的邏輯關(guān)系發(fā)生了變化，在存儲結(jié)構(gòu)上通過移動元素使之在邏輯上相鄰的元素在物理上也相鄰。算法思想：只需將ai+1～an依次向前移動一個位置，并修改其長度。

線性表順序表示的算法實現(xiàn)—刪除算法StatusListdelete_Sq(Sqlist&L,inti,Elemtype&e){if(i<1‖i>L.length)returnERROR;//判斷i的正確性

p=&(L.elem[i-1]);//指示被刪元素位置

e=*p;//返回被刪元素的值

q=L.elem+L.length-1;//指示最后元素位置

for(++p;p<=q;++p)*(p-1)=*p;//移動元素

--L.length;//修改表的長度

returnOK;}另一種移動方法：

e=L.elem[i-1];for(j=i;j<L.length;j++)L.lem[j-1]=L.lem[j];插入、刪除算法分析

線性表順序存儲結(jié)構(gòu)優(yōu)點:可隨機存取表中任一結(jié)點。缺點：插入刪除操作可能要移動大量元素。n+1∑i=1Ei=Pi（n-i+1）

設在線性表第i個元素前插入一新元素的概率為Pi，刪除第i個元素的概率為Qi，元素移動為算法的基本操作。則插入和刪除的平均移動期望值為：n∑i=1Ed=Qi

（n-i）等概率下：

Ei=n/2Ed=（n-1）/2

算法時間復雜度：O(n)線性表的鏈式表示—線性鏈表datanext特點：用一組任意的存儲單元存放線性表的結(jié)點。邏輯關(guān)系的表示：將元素ai與ai+1的地址存儲在一起。結(jié)點數(shù)據(jù)域指針域線性鏈表的三要素：

1、設立一個指針變量head來指向第一個結(jié)點。

2、每一個結(jié)點的存儲地址都由前一結(jié)點的指針域指示。

3、最后一個結(jié)點無后繼結(jié)點，其指針域為空。a2a1L頭指針元素結(jié)點尾結(jié)點^an…線性表的鏈式表示—線性鏈表例:設有線性表為:(Zhao,Qian,Sun,Li,Zhou)zhaoQian^ZhouLsunLi單鏈表的特點：

1、鏈表中各結(jié)點邏輯上有序，物理上可能無序。

2、任何兩個結(jié)點的存儲位置之間沒有固定的聯(lián)系。要訪問任一元素，必須從頭指針出發(fā)進行尋找。因此，單鏈表是順序訪問結(jié)構(gòu)。

3、增設一個頭結(jié)點作為鏈表的第一個結(jié)點可使某些算法更簡單，頭結(jié)點的數(shù)據(jù)域可以不存任何信息，指針域指示第一個結(jié)點（首元素）的地址。

zhaoQian^ZhouLsunLi空鏈表：^L單鏈表的C語言描述typedef

struct

ListNode{

Elemtypedata；

struct

ListNode

*next；

}ListNode

，

*Linklist；線性鏈表的運算1、線性鏈表的初始化的實現(xiàn)（帶頭結(jié)點）LinkList

InitList_L(void){head=(ListNode*)malloc(sizeof(ListNode));head->next=NULL;return(head);}2、撤消線性鏈表voidDestroyList_L(LinkList*L){p=*L;*L=NULL;while(p){q=p->next;free(p);p=q;}}3、置空線性鏈表

voidclearList_L(LinkList*L)

{p=L->next;L->next=NULL;while(p){q=p->next;free(p);p=q;}}線性鏈表的訪問運算4、訪問第i個數(shù)據(jù)元素：先找到第i各結(jié)點

StatusGetElem_L(LinkList

L,int

i,ElemType&e){p=L->next;j=1;while(p&&j<i){p=p->next;j++};if(!p||j>i)return(ERROR);e=p->data;return(OK);}算法分析：基本操作：移動指針。若1≤i≤n，則循環(huán)體執(zhí)行i-1次，否則執(zhí)行n次。成功平均移動指針次數(shù)為:（0+1+2+…+n-1)/n=(n-1)/2。算法時間復雜度為O(n)。線性鏈表的插入運算5、結(jié)點插入運算：在第i個數(shù)據(jù)元素前插入一個新元素PabxS在p后插入結(jié)點s：基本思想：先找到第i個結(jié)點的前驅(qū)結(jié)點，然后執(zhí)行插入。StatusListinsert_L(Linklist

L,int

i,Elemtypee){p=L;j=0;while(p&&j<i-1){p=p->next;++j}if(!p‖j>i-1)returnERROR;s=(LinkList)malloc(sizeof(ListNode));s->data=e;s->next=p->next;p->next=s;returnOK;}S->next=p->next;P->next=s;線性鏈表結(jié)點的刪除6、結(jié)點刪除運算：刪除第i個數(shù)據(jù)元素

刪除p后面的結(jié)點：基本思想：先找到第i個結(jié)點的前驅(qū)結(jié)點，然后執(zhí)行刪除。StatusListDelete_L(Linklist

L,int

i,Elemtype&e){p=L;j=0;while(p->next&&j<i-1){p=p->next;++j}if(!p->next‖j>i-1)returnERROR;

q=p->next;p->next=q->next;e=q->data;free(q);

returnOK;}Pacb算法時間復雜度：O(n)。qq=p->next;p->next=q->next;free(q);線性鏈表的生成7、線性鏈表生成基本思想：首先初始化線性鏈表，然后依次生成結(jié)點并插入到鏈表中。插入時，可插入到表頭，也可以插入到表尾，依元素間的邏輯順序而定。若從第一個元素開始輸入，必須插入到表尾，反之則插入到表頭。

voidCreateList(LinkList&L,intn){L=InitList_L()for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(ListNode));

scanf(p->data);p->next=L->next;L->next=p;}}插入到尾的算法？兩個有序鏈表的合并運算

將單鏈表la和lb歸并到鏈表lc，la和lb非遞減有序，lc也非遞減有序?；舅枷耄涸Opa、pb指向la和lb當前待比較的結(jié)點，pc指向lc的最后一個結(jié)點。則有：pa->data<=pb->data，把pa所指結(jié)點連接到pc結(jié)點之后。否則，把pb所指結(jié)點連接到pc結(jié)點之后。

ai^anLa…pab2^bnLbpbc1ckLc…pcpa->data<=pb->datapa->data>pb->data兩個有序鏈表的合并運算voidMergelist_L(Linklist&La,Linklist&Lb,Linklist&Lc){pa=La->next;pb=Lb->next;

Lc=pc=La;while(pa&&pb){if(pa->data<=pb->data) {pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;free(Lb);}

算法時間復雜度：O(m+n)線性表的鏈式表示--循環(huán)鏈表循環(huán)鏈表：首尾相接的鏈表。在單鏈表中，將最后一個結(jié)點的指針域指向開始結(jié)點或頭結(jié)點，就得到單鏈形式的循環(huán)鏈表，簡稱單循環(huán)鏈表。特點：從任一結(jié)點出發(fā)，可以訪問表中所有其它結(jié)點。為使空表和非空表的運算統(tǒng)一，在循環(huán)鏈表中設置頭結(jié)點。它的值域或為空，或按需要設定。這樣，循環(huán)鏈表至少存在一個結(jié)點。當插入或刪除運算時，不再需要改變表頭指針。La1a2anL空單循環(huán)鏈表線性表的鏈式表示--循環(huán)鏈表a1a2anA

若在循環(huán)鏈表中設置尾指針而不是頭指針，結(jié)點插入時既可方便地插到an,又可方便地插到a1，還可以使某些某些操作簡化，如兩個線性表首尾相連合并為一個表。

a1a2anBP=A->next;A->next=B->next->next;Q=B->next;B->next=p;A=B;free(Q);P①②Q③④A⑤線性表的鏈式表示--雙向鏈表雙向鏈表：每個結(jié)點設置兩個指針域，一個指向直接前驅(qū)，一個指向直接后繼。雙向循環(huán)鏈表：在雙向鏈表中，若第一個結(jié)點（或頭結(jié)點）的前向指針指向最后一個結(jié)點，最后一個結(jié)點的后向指針指向第一個結(jié)點（或頭結(jié)點），則就是雙向循環(huán)鏈表。雙向循環(huán)鏈表一般都有頭結(jié)點。a1a2anLL雙向空鏈表后向指針數(shù)據(jù)前向指針typedef

struct

Dublnode{

Elemtypedata;

struct

Dublnode*prior；

struct

Dublnode*next；}Dublnode,*Dublinklist

；雙向鏈表結(jié)點的存儲結(jié)構(gòu)定義雙向鏈表結(jié)點結(jié)構(gòu)雙向鏈表運算—刪除節(jié)點①②Pabc刪除結(jié)點p主要操作p->prior->next=p->next;p->next->prior=p->peior;free(p);雙向鏈表運算--插入結(jié)點abP在結(jié)點p前插入值為x的結(jié)點主要操作S=(Dublnode*)malloc(sizeof(Dublnode));S->data=x;S->prior=p->priorp->prior->next=s;S->next=p;p->prior=s;xs①②④③線性表存儲結(jié)構(gòu)的討論線性表的兩種存儲結(jié)構(gòu)：順序表和鏈表。

1、基于空間的考慮順序表存儲空間一般存在存儲空間浪費。鏈表的存儲空間根據(jù)需要而分配，無存儲空間浪費。線性表長度基本固定時，采用順序表，否則采用鏈表。

2、基于時間的考慮順序表是隨機存取結(jié)構(gòu)，存取的時間復雜度為O(1)。

鏈表是順序存取結(jié)構(gòu)，時間復雜度為O(n)。順序表插入和刪除運算可能要移動大量元素。鏈表插入和刪除運算修改指針就可實現(xiàn)，無需移動元素。鏈表應用實例—一元多項式表示及運算多項式pn(x)可表示成:

pn(x)=a0+a1x+a2x2+…+anxn

線性表表示：（a0，a1，a2，…，an）指數(shù)隱含在系數(shù)ai的序號中。順序表：n+1個單元。當n很大、0系數(shù)較多時，浪費空間和時間。如：s(x)=1+3x1000+2x20000

采用線性鏈表的存儲結(jié)構(gòu)靈活性大。其結(jié)點結(jié)構(gòu)為：

typedef

structNode{floatcoef;

int

expn;

structNode*next}PolyNode,*polynomial;103100022000?p鏈表應用實例--一元多項式表示及運算多項式相加運算規(guī)則：

指數(shù)相同，系數(shù)相加，若不為0，則構(gòu)成一項。指數(shù)不同，則兩項系數(shù)照抄。

設A(x)=A(x)+B(x)

p、q分別指向兩個多項式中當前被檢測的結(jié)點。若：

p->exp<q->exp:

結(jié)果多項式的當前結(jié)點為p;p->exp=q->exp:p->coef=p->coef+q->coef

刪除結(jié)點q,若結(jié)果為0，刪除結(jié)點p;p->exp>q->exp:

將