數(shù)據(jù)結(jié)構(gòu)第二章線性表

第二章線性表(Linearlist)邏輯結(jié)構(gòu)與基本運(yùn)算1順序表2單鏈表與雙向鏈表3線性表應(yīng)用4madebyXiong’enLiuSchoolofComputer&InformationScience,FAFU1邏輯結(jié)構(gòu)與基本運(yùn)算L=(a1,a2,…,ai,…,an)

線性表邏輯結(jié)構(gòu)非空表中有且僅有一個(gè)第一個(gè)元素非空表中有且僅有一個(gè)最后一個(gè)元素除第一個(gè)元素之外，每個(gè)元素均有且僅有一個(gè)前趨除最后一個(gè)元素外，每個(gè)元素均有且僅有一個(gè)后繼#基本運(yùn)算的操作體現(xiàn)邏輯結(jié)構(gòu)特點(diǎn)線性表基本運(yùn)算初始化initiate(L)，建立一個(gè)空表求表長(zhǎng)length(L)，返回元素個(gè)數(shù)取第i個(gè)元素get(L,i)，其中1≤i≤length(L)元素定位locate(L,e)，返回元素的存儲(chǔ)位置插入元素insertion(L,i,e)，其中1≤i≤length(L)+1刪除元素deletion(L,i)，其中1≤i≤length(L)判表空empty(L)置表空clear(L)，清空表求前趨prior(L,e)求后繼next(L,e)問(wèn)題1：在線性表L中的元素a之前插入元素b。問(wèn)題2：刪除線性表L中的元素a。

線性表的應(yīng)用問(wèn)題---通過(guò)基本運(yùn)算實(shí)現(xiàn)insertion(L,a,b)變換成insertion(L,locate(L,a),b)deletion(L,a)變換成

deletion(L,locate(L,a))2順序表(sequentiallist)

一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素

順序表數(shù)據(jù)類型#defineM?//?maybe1024forexampletypedef struct { …… //accordingtotheproblem }element;typedef struct { elementdata[M]; intlen;

}sqList;

voidinitiate(sqList&L) //初始化順序表

{ L.len=0; }//-------------------------------------------------// intlength(constsqList&L) //求表長(zhǎng)

{ returnL.len; }//-------------------------------------------------// voidclear(sqList&L) //置表空

{ L.len=0; }//-------------------------------------------------// boolempty(constsqList&L) //判表空

{ if(L.len==0)returntrue; returnfalse; }

elementget(constsqList&L,inti)//

取第i個(gè)元素

{ if(i<1||i>L.len)returnNULL; returnL.data[i-1]; } intlocate(constsqList&L,elemente) //

元素定位

{ intp=0; while(p<L.len&&L.data[p]!=e) p++; if(p<L.len)returnp; return-1; }以上算法的時(shí)間復(fù)雜度T(n)=O(1)順序表其它涉及遍歷的算法時(shí)間復(fù)雜度T(n)=O(n)...順序表第i個(gè)元素之前插入新元素e1e2e3...eiei+1...enenen-1ei+1eie012i-1inn-1nlenn+1data

boolinsertion(sqList&L,inti,elementa) //插入元素

{ if(i<1||i>L.len+1)returnfalse; for(intj=L.len;j>=i;j--) L.data[j]=L.data[j-1]; L.data[i-1]=a; L.len++; returntrue; }//------------------------------------------------------------// booldeletion(sqList&L,inti) //元素刪除

{ if(i<1||i>L.len)returnfalse; for(intj=i;j<L.len;j++) L.data[j-1]=L.data[j]; L.len--; returnture; }順序表元素插入算法時(shí)間復(fù)雜度重復(fù)的基本操作---元素的移動(dòng)T(n)=O(n)元素刪除算法的時(shí)間復(fù)雜度T(n)=O(n)問(wèn)題3：順序表元素插入或刪除算法的時(shí)間效率高嗎？問(wèn)題4：實(shí)現(xiàn)insert(L,a,b)及deletion(L,a)【例2.1】運(yùn)用基本運(yùn)算算法實(shí)現(xiàn)清除順序表中的重復(fù)元素。

voidpurge(sqList&L) { inti=0,j; while(i<L.len-1) { j=i+1; while(j<L.len) if(L.data[i]==L.data[j])

deletion(L,j+1); elsej++; i++; } }T(n)=O(n3)3單鏈表與雙向鏈表(linkedlist)3.1單鏈表(singlylinkedlist)

每個(gè)結(jié)點(diǎn)附設(shè)1個(gè)指向后繼結(jié)點(diǎn)的指針僅為現(xiàn)有元素分配結(jié)點(diǎn)空間，元素刪除時(shí)釋放結(jié)點(diǎn)元素插入或刪除時(shí)，不改變其它結(jié)點(diǎn)存儲(chǔ)位置單鏈表結(jié)點(diǎn)數(shù)據(jù)類型

typedef structnode { elementdata; structnode*next; }linknode;

linknode*initiate() //初始化單鏈表

{ linknode*p; p=newlinknode; p->next=NULL; returnp; } boolempty(linknode*hp) //判空表

{ if(hp->next==NULL)returntrue; returnfalse; }

單鏈表遍歷,T(n)=O(n)//-------------------------------------------------// intlength(linknode*hp) //求表長(zhǎng)

{ intn=0; hp=hp->next; while(hp) //while(hp!=NULL) { n++; hp=hp->next; } returnn; } elementget(linknode*hp,inti) //取第i個(gè)元素

{ intj=1; hp=hp->next; while(hp&&j<i) { hp=hp->next; j++; } if(hp==NULL||j!=i)returnNULL; returnhp->data; }//-------------------------------------------------// linknode*locate(linknode*hp,elemente)//定位

{ hp=hp->next; while(hp&&hp->data!=e) hp=hp->next; returnhp; }單鏈表元素結(jié)點(diǎn)插入

boolinsertion(linknode*hp,inti,elemente) //單鏈表元素插入

{ intj=0; linknode*p=hp,*q; while(p!=NULL&&j<i-1)//定位前趨

{ p=p->next; j++; } if(p==NULL||j!=i-1)returnfalse; q=newlinknode; q->data=e; q->next=p->next;

p->next=q; returntrue; }問(wèn)題5：?jiǎn)捂湵砼c順序表元素插入T(n)=O(n),哪個(gè)實(shí)際效率更高？問(wèn)題6：如何實(shí)現(xiàn)單鏈表建立過(guò)程？單鏈表元素結(jié)點(diǎn)刪除

booldeletion(linknode*hp,inti)//刪除元素

{ intj=0; linknode*p=hp,*q; while(p->next!=NULL&&j<i-1)//定位前趨

{ p=p->next; j++; } if(p->next==NULL||j!=i-1)returnfalse; q=p->next;

p->next=q->next;//p->next=p->next->next; deleteq; returntrue; }問(wèn)題7：實(shí)現(xiàn)算法（指定元素的插入或刪除） ①boolinsertion(linknode*hp,elementa,elementb); ②booldeletion(linknode*hp,elementa);【例3.1】將兩個(gè)遞增有序的單鏈表合并成一個(gè)遞增有序的表。

linknode*merge(linknode*ha,linknode*hb) { linknode*q=ha,*pa=ha->next,*pb=hb->next; while(pa!=NULL&&pb!=NULL) if(pa->data<=pb->data) { q->next=pa; q=pa; pa=pa->next; } else { q->next=pb; q=pb; pb=pb->next; } if(pa!=NULL)q->next=pa; elseq->next=pb; deletehb; returnha; }linknode*merge(linknode*ha,linknode*hb) //改進(jìn)版{ linknode*q=ha,*pa=ha->next,*pb=hb->next; while(pa&&pb) { while(pa&&pa->data<=pb->data) { q=pa; pa=pa->next; } q->next=pb; while(pb&&pb->data<pa->data) { q=pb; pb=pb->next; } q->next=pa; } if(pa)q->next=pa; elseq->next=pb; deletehb; returnha;}3.2雙向鏈表(doublelinkedlist)問(wèn)題8：?jiǎn)捂湵砬笄摆呥\(yùn)算及其T(n)雙向鏈表結(jié)點(diǎn)數(shù)據(jù)類型

typedef structnode { elementdata; structnode*prior,*next; }dlinknode;

dlinknode*initiate() //初始化雙向循環(huán)鏈表

{ dlinknode*p; p=newdlinknode; p->prior=p->next=p; returnp; } boolempty(dlinknode*hp) //雙向循環(huán)鏈表判空表

{ if(hp->next==hp)returntrue; //if(hp->prior==hp)returntrue; returnfalse; }//-------------------------------------------------// dlinknode*locate(dlinknode*hp,elemente) //雙向循環(huán)鏈表元素定位

{ dlinknode*p=hp->next; //p=hp->prior; while(p!=hp&&p->data!=e) p=p->next; //p=p->prior; if(p!=hp)returnp; returnNULL; }雙向鏈表元素結(jié)點(diǎn)插入

boolinsertion(dlinknode*hp,inti,elemente) //雙向循環(huán)鏈表元素插入

{ intj=0; dlinknode*p=hp,*q; while(p!=hp&&j<i-1)//定位前趨

{ p=p->next; j+