數(shù)據(jù)結(jié)構(gòu)線性表課件

第二章數(shù)組2.1線性表2.2順序表2.3單鏈表2.4線性鏈表的其他變形2.5單鏈表的應(yīng)用：多項式及其運算2.1線性表線性表(LinearList)

：由n(n≧0)個數(shù)據(jù)元素(結(jié)點)a1，a2，…an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱為空表，常常將非空的線性表(n>0)記作：(a1，a2，…an)()這里的數(shù)據(jù)元素ai(1≦i≦n)只是一個抽象的符號，其具體含義在不同的情況下可以不同。例子例1、26個英文字母組成的字母表（A，B，C、…、Z）例2、某校從1978年到1983年各種型號的計算機擁有量的變化情況。（6，17，28，50，92，188）例3、學(xué)生健康情況登記表如下：姓名學(xué)號性別年齡

健康情況王小林790631

男18

健康陳紅790632

女20

一般劉建平790633

男21

健康張立立790634

男17

神經(jīng)衰弱

……..

……..…….…….

…….例4、一副撲克的點數(shù)（2，3，4，…，J，Q，K，A）線性表的邏輯特征是：在非空的線性表，有且僅有一個開始結(jié)點a1，它沒有直接前趨，而僅有一個直接后繼a2；有且僅有一個終端結(jié)點an，它沒有直接后繼，而僅有一個直接前趨an-1；其余的內(nèi)部結(jié)點ai(2≦i≦n-1)都有且僅有一個直接前趨ai-1和一個直接后繼ai+1

線性表的邏輯結(jié)構(gòu)：線性結(jié)構(gòu)數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上的。運算的具體實現(xiàn)則是在（物理）存儲結(jié)構(gòu)上進行的。線性表只能“順序存取”數(shù)組與線性表的異同：數(shù)組id與位置的對應(yīng)。線性表是線性排列的“對象”。線性表的特點線性表上實現(xiàn)的基本操作1.構(gòu)造2.隨機訪問：取第i個位置上的元素。3.插入：線性表的插入運算是指在表的第I(1≦i≦n+1個位置上，插入一個新結(jié)點x。4.刪除：線性表的刪除運算是指將表的第i(1≦i≦n)結(jié)點刪除。5.查找：尋找具有特定數(shù)據(jù)的節(jié)點。6.歸并、復(fù)制、計數(shù)、排序。線性表的實現(xiàn)順序表：用順序方法存儲的線性表叫順序表。順序存儲： 用一組連續(xù)的存儲空間，依

次存儲線性表的元素。特點： 其邏輯結(jié)構(gòu)與物理結(jié)構(gòu)（順 序結(jié)構(gòu)相同。注意:

順序表是順序存儲，隨機存 取。實現(xiàn)順序存儲一種最好的方式是用數(shù)組。[例]順序表{a0,a1,a2,…,an-1}地址bb+cb+2cb+3cb+icb+(n-1)C元素a0a1a2a3…an-1空閑區(qū)位置0123…n-1Loc(a[i])=loc(a[0])+i*c順序表的抽象數(shù)據(jù)結(jié)構(gòu)p43順序表上實現(xiàn)的基本運算1.查找例：在順序表{12，15，33，45，67，89，57，78}查找57（找到），查找66（找不到）。121533456789577801234567程序?qū)崿F(xiàn)Templet<classtype>intSeqlist<type>::Find(type&x)const{Inti=0；

while(i<=last&&data[i]!=x)i++;If(i>last)return-1;//沒找到

Elsereturni;//找到}查找算法的時間復(fù)雜度問題規(guī)模：表的長度，設(shè)它的值為n。算法的時間：主要化費在循環(huán)比較語句上。比較結(jié)點的次數(shù)依賴于（表的長度，被查找元素位置）。最好情況：a0=x；這時，其時間復(fù)雜度O（1）；最壞情況：找不到；比較語句將循環(huán)執(zhí)行n次，其時間復(fù)雜度O（n）平均復(fù)雜度：在長度為n的線性表中第i個位置上找到一個結(jié)點，令Efd(n)表示找到結(jié)點的期望值（即比較的平均次數(shù)），則在第i個位置上找到一個結(jié)點的比較次數(shù)為i+1。故Efd(n)=∑pi(i+1)假設(shè)在表中任何位置(0≦i≦n-1)上查找結(jié)點的機會是均等的，則

p0=p1=p2=…=pn-1=1/n因此，在等概率插入的情況下，

Efd(n)=∑(i+1)/n=(n+1)/2

在順序表上做查找運算，算法的平均時間復(fù)雜度為O(n)。2.插入例：在順序表{12，15，33，45，67，89，57，78}的第三個元素處插入元素44。12153345678957780123456744程序?qū)崿F(xiàn)Templet<classtype>intSeqlist<type>::Insert(type&x,inti){If(i<0||i>last+1||last==MaxSize-1)return0;//procondition校驗Else{last++;for(intj=last;j>i;j--)data[j]=data[j-1];data[i]=x;//插入return1;插入算法的時間復(fù)雜度問題規(guī)模：表的長度，設(shè)它的值為n。算法的時間：主要化費在循環(huán)的結(jié)點后移語句上。移動結(jié)點的次數(shù)（依賴于表的長度，插入位置）。最好情況：i=n；由于循環(huán)變量的終值大于初值，結(jié)點后移語句將不進行；這是，其時間復(fù)雜度O（1）；最壞情況：當(dāng)i=1時，結(jié)點后移語句將循環(huán)執(zhí)行n次，其時間復(fù)雜度O（n）；平均復(fù)雜度：在長度為n的線性表中第i個位置上插入一個結(jié)點，令Eis(n)表示移動結(jié)點的期望值（即移動的平均次數(shù)），則在第i個位置上插入一個結(jié)點的移動次數(shù)為n-i+1。故Eis(n)=∑pi(n-i+1)

假設(shè)在表中任何位置(1≦i≦n+1)上插入結(jié)點的機會是均等的，則

p1=p2=p3=…=pn+1=1/(n+1)

因此，在等概率插入的情況下，

Eis(n)=∑(n-i+1)/(n+1)=n/2

在順序表上做插入運算，算法的平均時間復(fù)雜度為O(n)。3.刪除：在上例完成后，再刪除44121544334567895778012345678完成后121533456789577801234567程序?qū)崿F(xiàn)Templet<classtype>intSeqlist<type>::Remove(type&x){inti=find（x）//查找if(i>0){last--;for(intj=i;j<=last;j++)data[j]=data[j+1];//依次前移

return1;}renturn0;//找不到，不能刪除}算法的平均復(fù)雜度=0(n)順序表的使用Templet<classtype>voidUnion(SeqList<type>&La,SeqList<type>&Lb){intn=La.Length();intm=Lb.Length();for(inti=1;i<=m;i++){typex=Lb.Get(i);//取值

intk=La.Find(x);//查找

if（k==-1）La.Insert(x;n+1);//找不到

n++;}}線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)順序表的優(yōu)點：取數(shù)方便快速。缺點：刪除、插入平均要移o(n)個元素。適應(yīng)性不強。

鏈表：是指用一組任意的存儲單元來存放線性表的結(jié)點，這組存儲單元可以是零散分布在內(nèi)存中的任意位置上的。任意的存儲單元如何存放線性表例：（a1,a2,a3,a4)鏈表中的結(jié)點結(jié)構(gòu)：

datalink單鏈表（SingleLinked):每一個結(jié)點只有一個鏈域，將各節(jié)點按順序聯(lián)系在一起的鏈表。鏈?zhǔn)酱鎯Φ膬?yōu)點：存儲方便?？臻g使用性好。取用不方便（一定是順序取用）。鏈表：非順序存儲，順序取用例1、線性表:(bat，cat，eat，fat，hat，jat，lat，mat)的單鏈表示意圖如下：165………………110hat200………….……130cat135135eat170……….……160matNull165bat130170fat110………………200jat205205lat160………………h(huán)eatheadbatcateatmat^…單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。

單鏈表的類定義1.復(fù)合類定義法：Classlist;Templete<classType>ClasslistNode{friendclasslist;private:Type*data;listNode*link;};Templet<classtype>classlist{private:listNode*first,*last;public://公共線性表操作}；嵌套類Templet<classtype>classlist{private:classlistNode{public:type*data;listNode*link;}listNode*first;*last;public://公共線性表操作}；對象和對象指針對象指針：用于存放對象地址的變量聲明形式：類名*對象指針名。Point*p;Pointp1;p=&p1;對象成員的引用：p1.x,p1.y;通過對象指針引用對象成員：p->x,p->y單鏈表的插入與刪除插入（表首、中間、最后）gathatcatpSS->link=p->link;P->link=S;刪除算法（表首、中間、最后）gathatcatPSp->link=s->link;DeleteS;單鏈表的實現(xiàn)不帶表頭的單鏈表結(jié)構(gòu)x2xn∧x1first判斷空表的條件：first=NULLlast帶表頭的單鏈表結(jié)構(gòu)x1xn∧∧first判斷空表的條件：first->link=NULLlast建立單鏈表

1、頭插法建表該方法從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。2、尾插法建表

頭插法建立鏈表雖然算法簡單，但生成的鏈表中結(jié)點的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點插入到當(dāng)前鏈表的表尾上，為此必須增加一個尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點。查找運算

1、按序號查找在鏈表中，即使知道被訪問結(jié)點的序號i，也不能象順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順鏈域link逐個結(jié)點往下搜索，直到搜索到第i個結(jié)點為止。因此，鏈表不是隨機存取結(jié)構(gòu)。設(shè)單鏈表的長度為n，要查找表中第i個結(jié)點，僅當(dāng)1≦i≦n時，i的值是合法的。但有時需要找頭結(jié)點的位置，故我們將頭結(jié)點看做是第0個結(jié)點，其算法如下：Templete<classtype>listNode<type>*list<type>::find(inti){If(i<-1)returnNULL;If(i==-1)returnfirst;listNode<type>*p=first->link;intj=0;while(p!=NULL&&j<i){p=p–>link;j++;}returnp;}2、按值查找按值查找是在鏈表中，查找是否有結(jié)點值等于給定值key的結(jié)點，若有的話，則返回首次找到的其值為key的結(jié)點的存儲位置；否則返回NULL。查找過程從開始結(jié)點出發(fā)，順著鏈表逐個將結(jié)點的值和給定值key作比較。其算法如下：Templete<classtype>listNode<type>*list<type>::find(typevalue){listNode<type>*p=first->link;while(p!=NULL&&p->data!=value)p=p–>link;returnp;}算法的執(zhí)行時間亦與輸入實例中的的取值key有關(guān)，其平均時間復(fù)雜度的分析類似于按序號查找，也為O(n)。三、插入運算

插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，我們必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點*p，并令結(jié)點*p的指針域指向新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化，插入過程如：

Templete<classtype>intlist<type>::insert(typevalue,inti){listNode<type>*p=find(i-1);If(p==NULL）return0;listNode<type>*newNode=GetNode(value,p->link);if(p->link==NULL)last=newNode;p->link=newNode;return1;}算法的時間主要耗費在查找操作find上，故時間復(fù)雜度亦為O(n)。四、刪除運算刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點aai-1的指針域link中，所以我們必須首先找到ai-1的存儲位置p。然后令p–>link指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間，將其歸還給“存儲池”。

設(shè)單鏈表的長度為n，則刪去第i個結(jié)點僅當(dāng)1≦i≦n時是合法的。注意，當(dāng)i=n+1時，雖然被刪結(jié)點不存在，但其前趨結(jié)點卻存在，它是終端結(jié)點。因此被刪結(jié)點的直接前趨*p存在并不意味著被刪結(jié)點就一定存在，僅當(dāng)*p存在（即p!=NULL）且*p不是終端結(jié)點即p–>link!=NULL）時，才能確定被刪結(jié)點存在。顯然此算法的時間復(fù)雜度也是O(n)。從上面的討論可以看出，鏈表上實現(xiàn)插入和刪除運算，無須移動結(jié)點，僅需修改指針。單鏈表的游標(biāo)指針的抽象：first；current；last；仿真：模仿人的工作。應(yīng)用的方便性：在幾乎不損失效率的前提下，可以利用游標(biāo)直接完成多種運算。它是一種利用單鏈表的基本方式。(求和、求平均、求最大值。。。）O靜態(tài)鏈表數(shù)組中的每一個元素附加一個鏈接指針，就形成了一個靜態(tài)鏈表。靜態(tài)鏈表是利用數(shù)組實現(xiàn)的，在運算過程中存儲空間大小不變（靜態(tài)）如何利用空間：分成兩個鏈表1.可利用空間鏈表2.已用空間鏈表(實例)循環(huán)鏈表單循環(huán)鏈表：在單鏈表中，將終端結(jié)點的指針域NULL改為指向表頭結(jié)點，就得到了單鏈形式的循環(huán)鏈表，并簡單稱為單循環(huán)鏈表。為了使空表和非空表的處理一致，循環(huán)鏈表中也可設(shè)置一個頭結(jié)點。這樣，空循環(huán)鏈表僅有一個自成循環(huán)的頭結(jié)點表示。如下圖所示：

a1an

….first⑴非空表⑵空表

在用頭指針表示的單鏈表中，找開始結(jié)點a1的時間是O(1)，然而要找到終端結(jié)點an，則需從頭指針開始遍歷整個鏈表，其時間是O(n)first

在很多實際問題中，表的操作常常是在表的首尾位置上進行，此時頭指針表示的單循環(huán)鏈表就顯得不夠方便.如果改用尾指針last來表示單循環(huán)鏈表，則查找開始結(jié)點a1和終端結(jié)點an都很方便，它們的存儲位置分別是(last–>link)—>link和last，顯然，查找時間都是O(1)。因此，實際中多采用尾指針表示單循環(huán)鏈表。判斷表尾的條件：P->link==first;判斷空表的條件：first->link==first;由于循環(huán)鏈表中沒有NULL指針，故涉及遍歷操作時，其終止條件就不再像非循環(huán)鏈表那樣判斷p或p—>link是否為空，而是判斷它們是否等于某一指定指針，如頭指什或尾指針等。例、在鏈表上實現(xiàn)將兩個線性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)鏈接成一個線性表的運算。算法：

templete<classT>Circlist<T>*Circlist<T>::Merge(Circlist<T>&A，

Merge(Circlist<T>&B){CirclistNode<T>*p=A->last->link;A->last->link=(B->last->link)->link;deleteB->last->link;B->last->link=p;returnA);}x1xn∧firstx1xn∧lastfirstlast用循環(huán)鏈表解約瑟夫問題約瑟夫問題：旅行社用循環(huán)余數(shù)方法選擇旅客，提供免費旅行。例子：n=8,m=3雙鏈表問題的提出:雙向遍歷（刪除）雙鏈表的結(jié)構(gòu)1節(jié)點的結(jié)構(gòu)llinkdatarlink2雙鏈表結(jié)構(gòu)∧axfirst雙向鏈表(Doublelinkedlist):在單鏈表的每個結(jié)點里再增加一個指向其直接前趨的指針域llink。這樣就形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。雙鏈表與單鏈表的區(qū)別判斷表空的條件：

first==first->llink==first->rlink==last;判斷表尾的條件：

p->rlink==first;雙鏈表的對稱性：p->llink->rlink=p->rlink->llink=p

和單鏈表類似，雙鏈表一般也是由頭指針唯一確定的，增加頭指針也能使雙鏈表上的某些運算變得方便，將頭結(jié)點和尾結(jié)點鏈接起來也能構(gòu)成循環(huán)鏈表，并稱之為雙向鏈表。

向后插入算法雙向鏈表的向后操作算法：

{q->llink=p->lling;q->rlink=p;p->rlink->llink=q;p->rlink=q;}向前插入算法雙向鏈表的前插操作算