數(shù)據(jù)結(jié)構(gòu)與算法b-2014年3月12日課堂listmar

數(shù)據(jù)結(jié)構(gòu)與算法

—線性結(jié)構(gòu)主講教員:段凌宇2014年3月12日

北京大學(xué)信息科學(xué)與技術(shù)學(xué)院，轉(zhuǎn)載或翻印必究北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page22.2.2向量的運算（示例）插入元素運算voidinsert(constELEM&item)

刪除元素運算

ELEMremove()

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page3插入算法/*

設(shè)元素類型為ELEM，nodelist是存儲順序表向量，msize是此向量的最大長度，curr_len是此向量的當(dāng)前長度，curr為此向量當(dāng)前下標(biāo)）*/＃include<assert.h>…template<classELEM>voidlist<ELEM>::insert(constELEM&item){

//需要檢查當(dāng)前長度不能大于或等于msize;//當(dāng)前游標(biāo)指針curr不能小于0,也不能大于或等于當(dāng)前長度;

//此條件不滿足時，程序異常，退出運行。

assert((curr_len<msize)&&(curr>=0)&&(curr<curr_len));北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page4

//從表尾curr_len-1起往右移動直到curr

for

(inti=curr_len;i>curr;i--) nodelist[i]=nodelist[i-1];

//當(dāng)前指針處插入新元素

nodelist[curr]=item;

//表的實際長度curr_len加1

curr_len++;}循環(huán)至i=curr+1，最后一次移動是nodelist[curr]北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page5插入算法執(zhí)行時間

元素總個數(shù)為k，各個位置插入的概率（可能性）相等，即p＝1/k平均移動元素次數(shù)為

:總時間開銷估計為：

O（k）

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page6刪除算法/*設(shè)元素類型為ELEM，nodelist是存儲順序表向量，msize是此向量的最大長度，curr_len是此向量的當(dāng)前長度，curr為此向量當(dāng)前下標(biāo)*///返回curr所指的元素值，并從表中刪去此元素＃include<assert.h>…template<classELEM>ELEMlist<ELEM>::remove(){

//需要檢查當(dāng)前長度不能大于msize;//當(dāng)前游標(biāo)指針curr不能小于0,也不能大于等于當(dāng)前長度;

//此條件不滿足時，程序異常，退出運行。

assert((curr_len<=msize)&&(curr>=0)&&(curr<curr_len));北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page7ELEMtemp＝

nodelist[curr];//從指針curr到curr_len每個元素往前移一格for(inti=curr;i<curr_len-1;i++)nodelist[i]=nodelist[i+1];curr_len--;//表的實際長度cur_len減1returntemp;//返回值是進入時的舊值}循環(huán)至i=curr_len-2，最后一次移動是nodelist[curr_len-1]北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page8刪除算法時間代價

刪除操作與插入操作相似時間代價為O(k)

順序表存取元素方便時間代價為O(1)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page9大綱2.1線性表(linearlist)2.2順序表—

向量(vector)2.3鏈表(linkedlist)2.3.1單鏈表2.3.2雙鏈表2.3.3循環(huán)鏈表2.4線性表實現(xiàn)方法的比較2.5棧(stack)2.6隊列(queue)2.7棧與遞歸(recursivefunction)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page10約瑟夫環(huán)問題

(JosephusProblem)在羅馬人占領(lǐng)喬塔帕特(Yodfat)

后，39個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數(shù)，每報數(shù)到第3人該人就必須自殺，然后再由下一個重新報數(shù)，直到所有人都自殺身亡為止。Josephus和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page11約瑟夫環(huán)問題

(JosephusProblem)用鏈表（或者數(shù)組）實現(xiàn),時間復(fù)雜度高達(dá)O(nm)，當(dāng)n，m非常大(例如上百萬，上千萬)的時候，幾乎是沒有辦法在短時間內(nèi)出結(jié)果的.模擬整個游戲過程注意到原問題僅僅是要求出最后的勝利者的序號，而不是要模擬整個過程。遞推公式:

f[1]=0;

f[i]=(f[i-1]+m)%i;(i>1)

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page12約瑟夫環(huán)問題

(JosephusProblem)遞推公式:

f[1]=0;

f[i]=(f[i-1]+m)%i;(i>1)

將這些人從0到n-1編號，假設(shè)出列的是第k個人。

0,1,2,3,...,k-2,k-1,k,...,n-1//originalsequence(1)

0,1,2,3,...,k-2,,k,...,n-1//getridofthekthperson(2)

k,k+1,...,n-1,0,1,...,k-2//rearrangethesequence(3)

0,1,...,n-k-1,n-k,n-k+1,...,n-2//n-1person(4)

就接下來出列編號來說，注意到(2)式(3)其實是同一個序列，并且編號與(1)序列保持一致，然后(4)式進行了重新編號（對應(yīng)“新一輪的報數(shù)”）。

對比(3)(4)兩式，可以看出(3)中的編號x‘與(4)中的編號x對應(yīng)關(guān)系即為x’(注：上一輪報數(shù)階段的編號）=(x(注：當(dāng)前報數(shù)階段的編號)+m)modn考慮(4)式的編號與(3)式的編號，存在上述遞推關(guān)系；當(dāng)知道(4)式（當(dāng)前報數(shù)階段）的出列編號R，就可以遞推出(4)式R在(3)式的編號R’，即(1)式的編號。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page13約瑟夫環(huán)問題

(JosephusProblem)用鏈表（或者數(shù)組）實現(xiàn),時間復(fù)雜度高達(dá)O(nm)，當(dāng)n，m非常大(例如上百萬，上千萬)的時候，幾乎是沒有辦法在短時間內(nèi)出結(jié)果的.模擬整個游戲過程注意到原問題僅僅是要求出最后的勝利者的序號，而不是要模擬整個過程?；谶f推的算法的時間復(fù)雜度為O(n)，相對于模擬算法已經(jīng)有了很大的提高。適當(dāng)?shù)剡\用數(shù)學(xué)策略，不僅可以讓編程變得簡單，而且往往會成倍地提高算法執(zhí)行效率。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page142.3.1

單鏈表通過指針將一串存儲結(jié)點鏈接成一個鏈

存儲結(jié)點由兩部分組成：Data字段Link字段數(shù)據(jù)的邏輯結(jié)構(gòu)(K，R)K是由有限個結(jié)點組成的集合；R是定義在集合K上的一組二元關(guān)系北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page15單鏈表的存儲結(jié)構(gòu)

每一個存儲結(jié)點Data字段都代表一個基本類型數(shù)據(jù)，或一組有明確結(jié)構(gòu)的數(shù)據(jù)（復(fù)合數(shù)據(jù)類型、類對象）北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page16單鏈表結(jié)點類型定義,頭尾指針變量申明structListNode{ ELEMdata；

ListNode*link;};typedefListNode*ListPtr;ListPtrfirst,last;//頭、尾指針在VC6中，若源程序是cpp后綴名那么是沒有問題的，但是如果后綴名為c，會如何？出現(xiàn)errorC2081等錯誤，意思就是ListNode沒有定義等。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page17//在VC6中，若源程序是c后綴名，//需做以下修改typedef

struct

tagListNode{ ELEMdata；

ListNode*link;}ListNode;typedefListNode*ListPtr;ListPtrfirst,last;//頭、尾指針例子：來自微軟的矩形類型定義typedefstructtagRECT{LONGleft;LONGtop;LONGright;LONGbottom;}RECT,*PRECT;北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page18查找

單鏈表中第i個結(jié)點算法

ListNode*FindIndex(constinti)//函數(shù)返回值是找到的結(jié)點指針{ //first表首變量，可能指向空表

if(i==-1)returnfirst; ListNode*p=first->link;

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page19intj=0; while(p!=NULL&&j<i) { p=p->link; j++; };returnp;}循環(huán)至j=i-1，p=p->link指向第i個結(jié)點P何時返回NULL?當(dāng)鏈表中結(jié)點數(shù)小于i+1時北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page20插入

單鏈表中第i個結(jié)點算法ii+1北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page21插入

單鏈表中第i個結(jié)點算法

ListNode*Insert(ELEMvalue,inti)//插入數(shù)據(jù)內(nèi)容為value的新結(jié)點，//使之成為第i個結(jié)點{ ListNode*p，*q; q=newListNode; p=FindIndex(i-1); if(p==NULL)returnNULL;鏈表中結(jié)點數(shù)小于i,表尾結(jié)點最多是第i-2個結(jié)點北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page22 q->data=value;

q->link=p->link; p->link=q; if(q->link==NULL) last=q;//若插入結(jié)點無后繼,更新尾指針 returnq;//返回插入結(jié)點的指針}

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page23刪除

單鏈表指定結(jié)點算法

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page24voidRemoveAfter(ListNode*link)//刪除由參數(shù)link指定結(jié)點的下一個節(jié)點{ ListNode*newlink=link->link; if(newlink!=NULL){ link->link=newlink->link;

deletenewlink;}//若link指向的結(jié)點不是尾部結(jié)點}

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page25單鏈表長度算法intLength(){ intcount=0; ListNode*p=first->link; while(p!=NULL) { p=p->link; count++; } returncount;}

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page26大綱2.3鏈表(linkedlist)2.3.1單鏈表2.3.2雙鏈表2.3.3循環(huán)鏈表2.4線性表實現(xiàn)方法的比較北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page272.3.2雙鏈表

(doublelinkedlist)

單鏈表的主要不足：link字段僅僅指向后繼結(jié)點，不能有效地找到前驅(qū)雙鏈表彌補了上述不足:增加一個指向前驅(qū)的指針北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page28雙鏈表及其結(jié)點類型定義structDblListNode{ ELEMdata;

DblListNode*rlink; DblListNode*llink;};

structDoubleList{ DblListNode*first,*last;};北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page29插入雙鏈表中

指定結(jié)點的算法會出現(xiàn)問題嗎？有更簡潔方式？會出現(xiàn)問題嗎？北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page30在p所指結(jié)點后面

插入一個新結(jié)點首先執(zhí)行newq開辟結(jié)點空間。然后，讓該新結(jié)點的rlink填入p所指的后繼地址，新結(jié)點的llink填入指向p結(jié)點的指針，即newq;q->rlink=p->rlink;q->llink=p;//Error:q->llink=p->rlink->llink;此外，要把新結(jié)點的地址填入原p所指結(jié)點的rlink字段，而且新結(jié)點后繼的llink字段也應(yīng)該回指新結(jié)點。p->rlink=q;q->rlink->llink=q;

//注意：安全代碼需檢查q->rlink是否為空北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page31刪除雙鏈表中

指定結(jié)點的算法有問題嗎？實踐中需要檢驗p所指的結(jié)點是否有后繼?北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page322.3.3循環(huán)鏈表

(circularlylinkedlist)

將單鏈表或者雙鏈表的頭尾結(jié)點鏈接起來，就是一個循環(huán)鏈表。給操作帶來了方便,不增加額外存儲花銷從循環(huán)表中任一結(jié)點出發(fā)，都能訪問到表中其他結(jié)點；單鏈不可以。提高訪問效率。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page33幾種主要鏈表比較北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page342.4線性表實現(xiàn)方法的比較順序表的主要優(yōu)點

沒有使用指針，不用花費附加開銷

線性表元素的讀訪問非常簡潔便利

鏈表的主要優(yōu)點

無需事先了解線性表的長度

允許線性表的長度有很大變化

能夠適應(yīng)經(jīng)常插入、刪除內(nèi)部元素的情況通過建立雙向或循環(huán)鏈表提高訪問效率北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page35應(yīng)用場合的選擇

避免使用順序表的場合經(jīng)常插入、刪除時，不宜使用順序表

線性表的最大長度也是一個重要因素避免使用鏈表的場合

讀操作頻率大于插入、刪除操作頻率當(dāng)指針的存儲開銷，和整個結(jié)點內(nèi)容所占空間相比，指針開銷比例較大時，應(yīng)該慎重選擇

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page36大綱2.5棧(stack)2.5.1順序棧

2.5.2鏈?zhǔn)綏?/p>

2.5.3順序棧與鏈?zhǔn)綏５谋容^

2.5.4棧的應(yīng)用——后綴表達(dá)式求值2.6隊列(queue)2.6.1順序隊列

2.6.2鏈?zhǔn)疥犃?/p>

2.2.3順序隊列與鏈?zhǔn)疥犃械谋容^

2.7棧與遞歸(recursivefunction)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page372.5棧(stack)

一種限制訪問端口的線性表，后進先出表(LIFO表，Last-InFirst-Out)。也稱為“下推表”。元素插入稱為棧的‘壓入’（push)，刪除稱為棧的‘彈出’(pop)。表首被稱為‘棧頂’，而棧的另一端則叫做‘棧底’

每次取出（并被刪除）的總是剛壓進的元素，而最先壓入的元素則被放在棧的底部

棧頂棧底按壓入先后次序，最先壓入的元素編號為1，然后依次為2,3,4北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page38棧的抽象數(shù)據(jù)類型

template<classELEM>classStack{…//棧的運算集

}棧頂棧底棧的元素類型為ELEM棧的存儲：可以用順序表或單鏈表存儲，長度為定長北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page39enumBoolean{True,False}template<classELEM>classStack{stack(ints);//創(chuàng)建棧的實例

~stack();//該實例消亡

voidPush(ELEMitem); //item壓入棧頂

ELEMPop();//返回棧頂內(nèi)容，并從棧頂出

ELEMGetTop();//返回棧頂內(nèi)容，但不彈出

voidMakeEmpty(); //變?yōu)榭諚?/p>

BooleanIsEmpty(); //返回真，若棧已空

BooleanIsFull();//返回真，若棧已滿};北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page40棧的實現(xiàn)

順序棧使用向量實現(xiàn)鏈?zhǔn)綏Ｓ脝捂湵矸绞酱鎯?，其中指針的方向是從棧頂向下鏈接，即鏈表的頭結(jié)點位置對應(yīng)“棧頂”。

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page412.5.1順序棧//設(shè)棧的類定義為stack，棧元素類型為浮點float類型enumBoolean{True,False}#include<assert.h>//引入邏輯斷言語句classStack{public: float*ElmList;//存放數(shù)據(jù)元素的指針變量北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page42inttop;//該變量指示棧頂在該向量的位置（下標(biāo)值）//當(dāng)新元素壓入或棧內(nèi)容彈出，top值隨之增減intmaxsize;//棧的最大長度Stack(intsize); //構(gòu)建函數(shù)，創(chuàng)建棧的實例，向量空間長度為size//其他運算集，比如~Stack();};北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page43

順序棧的創(chuàng)建

//棧實例的創(chuàng)建，指定最大長度10Stack::Stack(intsize=10){ maxsize=size; //開辟向量存儲空間

ElmList=newfloat[maxsize]; //判斷new命令成功否，否則斷言程序異常

assert(ElmList!=NULL); top=-1;//表示?？諁北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page44壓入棧頂

voidStack::Push(floatitem){ //判斷是非棧滿，若棧溢出，退出運行

assert(!IsFull()); top++;//更新棧頂位置

ElmList[top]=item;//壓入棧頂元素}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page45從棧頂彈出

floatStack::Pop(){ //判斷棧非空，若斷言棧空異常，退出運行

assert(!IsEmpty()); returnElmList[top--];}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page46從棧頂讀取，但不彈出

floatStack::GetTop(){

//判斷棧非空，若斷言棧空異常，退出運行

assert(!IsEmpty());

returnElmList[top];}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page47其他算法

清空棧voidStack::MakeEmpty()

{top=-1;}棧消亡

~Stack(){delete[]ElmList;}棧滿時，返回真（true）BooleanIsFull(){returntop==(maxsize-1);}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page48大綱（續(xù)）2.5棧(stack)2.5.1順序棧

2.5.2鏈?zhǔn)綏?/p>

2.5.3順序棧與鏈?zhǔn)綏５谋容^

2.5.4棧的應(yīng)用——后綴表達(dá)式求值2.6隊列(queue)2.6.1順序隊列

2.6.2鏈?zhǔn)疥犃?/p>

2.2.3順序隊列與鏈?zhǔn)疥犃械谋容^

2.7棧與遞歸(recursivefunction)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page492.5.2鏈?zhǔn)綏Ｓ脝捂湵矸绞酱鎯χ羔樀姆较驈臈ｍ斚蛳骆溄?/p>

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page50鏈?zhǔn)綏５膭?chuàng)建

#include<assert.h>structListNode{

ELEMdata;

ListNode*link;};//單鏈表的結(jié)點類型

classStack{private:ListNode*top;public：

//創(chuàng)建一個空棧

//不用指定最大長度

Stack(){top=NULL;};

//其它運算集};北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page51壓入棧頂

voidStack::Push(floatitem){ ListNode*temp; temp=newListNode; //若無存儲空間則