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

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

健康情況王小林790631

男18

健康陳紅790632

女20

一般劉建平790633

男21

健康張立立790634

男17

神經衰弱

……..

……..…….…….

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

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

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

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

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

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

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

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

在順序表上做查找運算，算法的平均時間復雜度為O(n)。2.插入例：在順序表{12，15，33，45，67，89，57，78}的第三個元素處插入元素44。12153345678957780123456744程序實現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;插入算法的時間復雜度問題規模：表的長度，設它的值為n。算法的時間：主要化費在循環的結點后移語句上。移動結點的次數（依賴于表的長度，插入位置）。最好情況：i=n；由于循環變量的終值大于初值，結點后移語句將不進行；這是，其時間復雜度O（1）；最壞情況：當i=1時，結點后移語句將循環執行n次，其時間復雜度O（n）；平均復雜度：在長度為n的線性表中第i個位置上插入一個結點，令Eis(n)表示移動結點的期望值（即移動的平均次數），則在第i個位置上插入一個結點的移動次數為n-i+1。故Eis(n)=∑pi(n-i+1)

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

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

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

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

在順序表上做插入運算，算法的平均時間復雜度為O(n)。3.刪除：在上例完成后，再刪除44121544334567895778012345678完成后121533456789577801234567程序實現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;//找不到，不能刪除}算法的平均復雜度=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++;}}線性表的鏈式表示和實現順序表的優點：取數方便快速。缺點：刪除、插入平均要移o(n)個元素。適應性不強。

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

datalink單鏈表（SingleLinked):每一個結點只有一個鏈域，將各節點按順序聯系在一起的鏈表。鏈式存儲的優點：存儲方便。空間使用性好。取用不方便（一定是順序取用）。鏈表：非順序存儲，順序取用例1、線性表:(bat，cat，eat，fat，hat，jat，lat，mat)的單鏈表示意圖如下：165………………110hat200………….……130cat135135eat170……….……160matNull165bat130170fat110………………200jat205205lat160………………heatheadbatcateatmat^…單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。

單鏈表的類定義1.復合類定義法：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;單鏈表的實現不帶表頭的單鏈表結構x2xn∧x1first判斷空表的條件：first=NULLlast帶表頭的單鏈表結構x1xn∧∧first判斷空表的條件：first->link=NULLlast建立單鏈表

1、頭插法建表該方法從一個空表開始，重復讀入數據，生成新結點，將讀入數據存放到新結點的數據域中，然后將新結點插入到當前鏈表的表頭上，直到讀入結束標志為止。2、尾插法建表

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

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

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

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上，故時間復雜度亦為O(n)。四、刪除運算刪除運算是將表的第i個結點刪去。因為在單鏈表中結點ai的存儲地址是在其直接前趨結點aai-1的指針域link中，所以我們必須首先找到ai-1的存儲位置p。然后令p–>link指向ai的直接后繼結點，即把ai從鏈上摘下。最后釋放結點ai的空間，將其歸還給“存儲池”。

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

a1an

….first⑴非空表⑵空表

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

在很多實際問題中，表的操作常常是在表的首尾位置上進行，此時頭指針表示的單循環鏈表就顯得不夠方便.如果改用尾指針last來表示單循環鏈表，則查找開始結點a1和終端結點an都很方便，它們的存儲位置分別是(last–>link)—>link和last，顯然，查找時間都是O(1)。因此，實際中多采用尾指針表示單循環鏈表。判斷表尾的條件：P->link==first;判斷空表的條件：first->link==first;由于循環鏈表中沒有NULL指針，故涉及遍歷操作時，其終止條件就不再像非循環鏈表那樣判斷p或p—>link是否為空，而是判斷它們是否等于某一指定指針，如頭指什或尾指針等。例、在鏈表上實現將兩個線性表(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用循環鏈表解約瑟夫問題約瑟夫問題：旅行社用循環余數方法選擇旅客，提供免費旅行。例子：n=8,m=3雙鏈表問題的提出:雙向遍歷（刪除）雙鏈表的結構1節點的結構llinkdatarlink2雙鏈表結構∧axfirst雙向鏈表(Doublelinkedlist):在單鏈表的每個結點里再增加一個指向其直接前趨的指針域llink。這樣就形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。雙鏈表與單鏈表的區別判斷表空的條件：

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

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

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

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

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