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

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

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

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

刪除元素運(yùn)算

ELEMremove()

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

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

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

//此條件不滿(mǎn)足時(shí)，程序異常，退出運(yùn)行。

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

//從表尾curr_len-1起往右移動(dòng)直到curr

for

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

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

nodelist[curr]=item;

//表的實(shí)際長(zhǎng)度curr_len加1

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

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

:總時(shí)間開(kāi)銷(xiāo)估計(jì)為：

O（k）

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

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

//此條件不滿(mǎn)足時(shí)，程序異常，退出運(yùn)行。

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

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

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

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

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

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

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

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

f[1]=0;

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

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

(JosephusProblem)遞推公式:

f[1]=0;

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

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

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)

就接下來(lái)出列編號(hào)來(lái)說(shuō)，注意到(2)式(3)其實(shí)是同一個(gè)序列，并且編號(hào)與(1)序列保持一致，然后(4)式進(jìn)行了重新編號(hào)（對(duì)應(yīng)“新一輪的報(bào)數(shù)”）。

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

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

單鏈表通過(guò)指針將一串存儲(chǔ)結(jié)點(diǎn)鏈接成一個(gè)鏈

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

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

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

struct

tagListNode{ ELEMdata；

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

單鏈表中第i個(gè)結(jié)點(diǎn)算法

ListNode*FindIndex(constinti)//函數(shù)返回值是找到的結(jié)點(diǎn)指針{ //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個(gè)結(jié)點(diǎn)P何時(shí)返回NULL?當(dāng)鏈表中結(jié)點(diǎn)數(shù)小于i+1時(shí)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page20插入

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

單鏈表中第i個(gè)結(jié)點(diǎn)算法

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

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

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

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

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

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

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page25單鏈表長(zhǎng)度算法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)性表實(shí)現(xiàn)方法的比較北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page272.3.2雙鏈表

(doublelinkedlist)

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

DblListNode*rlink; DblListNode*llink;};

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

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

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

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

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

(circularlylinkedlist)

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

沒(méi)有使用指針，不用花費(fèi)附加開(kāi)銷(xiāo)

線(xiàn)性表元素的讀訪(fǎng)問(wèn)非常簡(jiǎn)潔便利

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

無(wú)需事先了解線(xiàn)性表的長(zhǎng)度

允許線(xiàn)性表的長(zhǎng)度有很大變化

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

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

線(xiàn)性表的最大長(zhǎng)度也是一個(gè)重要因素避免使用鏈表的場(chǎng)合

讀操作頻率大于插入、刪除操作頻率當(dāng)指針的存儲(chǔ)開(kāi)銷(xiāo)，和整個(gè)結(jié)點(diǎn)內(nèi)容所占空間相比，指針開(kāi)銷(xiāo)比例較大時(shí)，應(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隊(duì)列(queue)2.6.1順序隊(duì)列

2.6.2鏈?zhǔn)疥?duì)列

2.2.3順序隊(duì)列與鏈?zhǔn)疥?duì)列的比較

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

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

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

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

template<classELEM>classStack{…//棧的運(yùn)算集

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

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

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

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

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

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

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

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

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

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

順序棧的創(chuàng)建

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

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

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

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

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

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

floatStack::Pop(){ //判斷棧非空，若斷言?？债惓?，退出運(yùn)行

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

floatStack::GetTop(){

//判斷棧非空，若斷言?？债惓?，退出運(yùn)行

assert(!IsEmpty());

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

清空棧voidStack::MakeEmpty()

{top=-1;}棧消亡

~Stack(){delete[]ElmList;}棧滿(mǎn)時(shí)，返回真（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隊(duì)列(queue)2.6.1順序隊(duì)列

2.6.2鏈?zhǔn)疥?duì)列

2.2.3順序隊(duì)列與鏈?zhǔn)疥?duì)列的比較

2.7棧與遞歸(recursivefunction)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page492.5.2鏈?zhǔn)綏Ｓ脝捂湵矸绞酱鎯?chǔ)指針的方向從棧頂向下鏈接

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

#include<assert.h>structListNode{

ELEMdata;

ListNode*link;};//單鏈表的結(jié)點(diǎn)類(lèi)型

classStack{private:ListNode*top;public：

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

//不用指定最大長(zhǎng)度

Stack(){top=NULL;};

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

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