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

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

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

北京大學(xué)信息科學(xué)與技術(shù)學(xué)院，轉(zhuǎn)載或翻印必究北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page2大綱2.1線(xiàn)性表(linearlist)2.2順序表—

向量(vector)2.3鏈表(linkedlist)2.4線(xiàn)性表實(shí)現(xiàn)方法的比較2.5棧(stack)2.6隊(duì)列(queue)2.7棧與遞歸(recursivefunction)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page3數(shù)據(jù)的邏輯結(jié)構(gòu)（結(jié)點(diǎn)+關(guān)系）線(xiàn)性結(jié)構(gòu)（linearstructure）樹(shù)型結(jié)構(gòu)（treestructure）圖結(jié)構(gòu)（graphstructure）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(結(jié)點(diǎn)+關(guān)系->存儲(chǔ)器的映射）順序(sequential)鏈接(linked)索引(indexing)散列(hashing)數(shù)據(jù)的運(yùn)算(算法->程序->解決問(wèn)題）

1.2什么是數(shù)據(jù)結(jié)構(gòu)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page4大綱2.1線(xiàn)性表(linearlist)2.1.0線(xiàn)性表的定義和性質(zhì)2.1.1線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型2.1.2線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)2.1.3線(xiàn)性表運(yùn)算分類(lèi)2.2順序表—

向量(vector)2.3鏈表(linkedlist)2.4線(xiàn)性表實(shí)現(xiàn)方法的比較2.5棧(stack)2.6隊(duì)列(queue)2.7棧與遞歸(recursivefunction)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page5線(xiàn)性表的定義線(xiàn)性表(N,r)的定義：由結(jié)點(diǎn)集N，以及定義在結(jié)點(diǎn)集N上的線(xiàn)性關(guān)系r

所組成的線(xiàn)性結(jié)構(gòu)。這些結(jié)點(diǎn)稱(chēng)為線(xiàn)性表的元素。線(xiàn)性關(guān)系，也稱(chēng)為‘前后關(guān)系’，有時(shí)也稱(chēng)為‘大小關(guān)系’。關(guān)系r是有向的，且滿(mǎn)足全序性和單索性等約束條件。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page6線(xiàn)性表的性質(zhì)線(xiàn)性表（N,r）的性質(zhì)：（a）結(jié)點(diǎn)集N中有一個(gè)唯一的開(kāi)始結(jié)點(diǎn)，它沒(méi)有前驅(qū)，但有一個(gè)唯一的后繼；（b）對(duì)于有限集N，它存在一個(gè)唯一的終止結(jié)點(diǎn)，該結(jié)點(diǎn)有一個(gè)唯一的前驅(qū)而沒(méi)有后繼；（c）其它的結(jié)點(diǎn)皆稱(chēng)為內(nèi)部結(jié)點(diǎn)；每一個(gè)內(nèi)部結(jié)點(diǎn)，既有一個(gè)唯一的前驅(qū)，也有一個(gè)唯一的后繼；北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page7線(xiàn)性表的性質(zhì)（續(xù)）（d）線(xiàn)性表所包含的結(jié)點(diǎn)個(gè)數(shù)稱(chēng)為線(xiàn)性表的長(zhǎng)度，它是線(xiàn)性表的一個(gè)重要參數(shù)；長(zhǎng)度為0的線(xiàn)性表稱(chēng)為空表；（e）線(xiàn)性表的關(guān)系r，簡(jiǎn)稱(chēng)“前驅(qū)關(guān)系”，應(yīng)具有反對(duì)稱(chēng)性和傳遞性(離散數(shù)學(xué)中的概念)。設(shè)R為非空集合N上的二元關(guān)系反對(duì)稱(chēng)性:(x,y)∈R∧(y,x)∈R→x=y傳遞性:(x,y)∈R∧(y,z)∈R

→

(x,z)∈R北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page8大綱2.1線(xiàn)性表(linearlist)2.1.0線(xiàn)性表的定義和性質(zhì)2.1.1線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型2.1.2線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)2.1.3線(xiàn)性表運(yùn)算分類(lèi)2.2順序表—

向量(vector)2.3鏈表(linkedlist)2.4線(xiàn)性表實(shí)現(xiàn)方法的比較2.5棧(stack)2.6隊(duì)列(queue)2.7棧與遞歸(recursivefunction)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page92.1.1線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型

取值空間運(yùn)算集

用類(lèi)模板表達(dá)抽象數(shù)據(jù)類(lèi)型北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page10線(xiàn)性表類(lèi)模板template<classELEM,intMax_length>classlist//線(xiàn)性表類(lèi)模板list，模板類(lèi)型參數(shù)ELEM//非類(lèi)型參數(shù)Max_length用于規(guī)定所存儲(chǔ)線(xiàn)性表的最大長(zhǎng)度{private:…

//私有變量，線(xiàn)性表存儲(chǔ)空間;例如ELEMelements[Max_length];public: intcurr_len; //公共變量，該線(xiàn)性表的當(dāng)前長(zhǎng)度

intcurr; //公共變量，該線(xiàn)性表的當(dāng)前“指針”，游標(biāo)

list(); //構(gòu)造函數(shù)，創(chuàng)建一個(gè)空的新線(xiàn)性表

~list();//析構(gòu)函數(shù),從計(jì)算機(jī)存儲(chǔ)空間刪去整個(gè)線(xiàn)性表類(lèi)型參數(shù)：用來(lái)說(shuō)明類(lèi)模板中的屬性類(lèi)型、成員服務(wù)的參數(shù)類(lèi)型和返回值類(lèi)型非類(lèi)型參數(shù)：用來(lái)說(shuō)明類(lèi)模板中的屬性北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page11 voidclear();//將該線(xiàn)性表的全部元素清除

voidappend(ELEMvalue);//在表的尾部添加一個(gè)新元素

voidinsert(inti,ELEMvalue);//第i號(hào)位置上插入一個(gè)新結(jié)點(diǎn)

voidremove(inti);//刪去第i號(hào)元素，表的長(zhǎng)度減1，其后元素前移

ELEMfetch(inti);//讀取，返回第i個(gè)元素的值}為線(xiàn)性表設(shè)計(jì)的抽象數(shù)據(jù)類(lèi)型并不是唯一的private:ELEM*ptrElement;intsize;public:list(constintsize);北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page122.1.2線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)

定長(zhǎng)的一維數(shù)組結(jié)構(gòu)即向量型的順序存儲(chǔ)結(jié)構(gòu)，地址相鄰存儲(chǔ)

缺陷：長(zhǎng)度變化不得超過(guò)固定長(zhǎng)度變長(zhǎng)的線(xiàn)性存儲(chǔ)結(jié)構(gòu)鏈接式存儲(chǔ)結(jié)構(gòu)，使用指針表示前驅(qū)關(guān)系串結(jié)構(gòu)、動(dòng)態(tài)數(shù)組、以及順序文件

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page132.1.3線(xiàn)性表運(yùn)算分類(lèi)

創(chuàng)建線(xiàn)性表的一個(gè)實(shí)例(list()）線(xiàn)性表消亡（~list()）

獲取有關(guān)當(dāng)前線(xiàn)性表的信息

查找、由位置讀取等訪(fǎng)問(wèn)線(xiàn)性表并改變線(xiàn)性表的內(nèi)容或結(jié)構(gòu)添加、更新、刪除、清空等線(xiàn)性表的輔助性管理操作游標(biāo)加減、求表的長(zhǎng)度實(shí)現(xiàn)算法及其復(fù)雜性與采用的存儲(chǔ)結(jié)構(gòu)有密切關(guān)系北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page14大綱2.1線(xiàn)性表(linearlist)2.2順序表—

向量(vector)2.2.1向量的類(lèi)定義2.2.2向量的運(yùn)算2.3鏈表(linkedlist)2.4線(xiàn)性表實(shí)現(xiàn)方法的比較2.5棧(stack)2.6隊(duì)列(queue)2.7棧與遞歸(recursivefunction)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page152.2順序表—向量(sequentiallist—vector)

采用定長(zhǎng)的一維數(shù)組存儲(chǔ)結(jié)構(gòu)主要特性:元素的類(lèi)型相同

元素順序地存儲(chǔ)在連續(xù)存儲(chǔ)空間中，每一個(gè)元素有唯一的索引值（下標(biāo)值）

使用（靜態(tài)）常數(shù)作為向量長(zhǎng)度

數(shù)組存儲(chǔ)；主要優(yōu)點(diǎn)是讀寫(xiě)其元素很方便，通過(guò)下標(biāo)即可指定位置。

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page16函數(shù)調(diào)用過(guò)程中涉及的“形參”、“實(shí)參”“傳遞變量指針”、“引用形參”const修飾北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page17函數(shù)調(diào)用過(guò)程形參與實(shí)參voidswap(int,int);//形參為整型變量intmain(){

inti=3,j=4;

cout<<"i="<<i<<",j="<<j<<endl;

swap(i,j);

cout<<"i="<<i<<",j="<<j<<endl;

system("PAUSE");

return0;}

voidswap(inta,intb){//形參為整型變量

inttemp;

temp=a;

a=b;

b=temp;}結(jié)果：i=3,j=4i=3,j=4執(zhí)行函數(shù)swap后，形參a和b的改變不會(huì)影響實(shí)參i和j的值北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page18函數(shù)調(diào)用過(guò)程形參與實(shí)參傳給形參的是變量的值傳遞是單向的；如果在執(zhí)行函數(shù)期間形參的值發(fā)生變化，并不傳回給實(shí)參。因?yàn)樵谡{(diào)用函數(shù)期間，形參和實(shí)參不是同一個(gè)存儲(chǔ)單元。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page19函數(shù)調(diào)用過(guò)程形參與實(shí)參調(diào)用函數(shù)時(shí)把變量i和j的地址傳送給形參p1和p2，因此*p1和i為同一內(nèi)存單元，*p2和j是同一內(nèi)存單元。voidswap(int*,int*);//形參為整型指針變量intmain(){

inti=3,j=4;

cout<<"i="<<i<<",j="<<j<<endl;

swap(&i,&j);//變量地址

cout<<"i="<<i<<",j="<<j<<endl;

system("PAUSE");

return0;}

voidswap(int*p1,int*p2){//形參為整型指針變量

inttemp;

temp=*p1;

*p1=*p2;

*p2=temp;}結(jié)果：i=3,j=4i=4,j=3北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page20函數(shù)調(diào)用過(guò)程傳遞變量指針傳給形參的是指針變量，實(shí)參是一個(gè)變量的地址；調(diào)用函數(shù)時(shí)，形參（指針變量）指向?qū)崊⒆兞繂卧?。這種方式還是“值傳遞”，只不過(guò)實(shí)參的值是變量的地址而已。在函數(shù)中改變的不是實(shí)參的值，而是實(shí)參地址所指向的變量的值。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page21函數(shù)調(diào)用過(guò)程的引用形參voidswap(int

&,

int

&);

//參數(shù)為整型變量的引用intmain(){

inti=3,

j=4;

cout<<"i="<<i<<",j="<<j<<endl;

swap(i,

j);

//變量名

cout<<"i="<<i<<",j="<<j<<endl;

system("PAUSE");

return0;}

voidswap(int&a,

int&b){//形參為引用類(lèi)型

inttemp;

temp=a;

a=b;

b=temp;}結(jié)果：i=3,j=4i=4,j=3由實(shí)參把變量名傳給形參。i的名字傳給引用變量a，j的名字傳給引用變量b。此時(shí)a和b就分別與i,j占用同一內(nèi)存空間。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page22函數(shù)調(diào)用過(guò)程的引用形參這種把實(shí)參地址傳遞到形參，使形參的地址取實(shí)參的地址，從而使形參與實(shí)參共享同一單元的方式，就是地址傳遞方式。示例(2)中，傳遞指針變量要另外開(kāi)辟內(nèi)存單元，其內(nèi)容為地址；而示例(3)引用不是一個(gè)獨(dú)立的變量，不單獨(dú)占內(nèi)存單元。示例(3)

中，main函數(shù)調(diào)用swap函數(shù)時(shí)，實(shí)參不必用函數(shù)中變量的地址(即&i,

&j)，而直接使用變量名。系統(tǒng)向形參傳遞的是實(shí)參的地址而不是實(shí)參的值。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page23函數(shù)調(diào)用過(guò)程中涉及的“形參”、“實(shí)參”“傳遞變量指針”、“引用形參”const修飾北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page24const修飾函數(shù)參數(shù)“const”修飾函數(shù)參數(shù)是它最廣泛的一種用途，它表示函數(shù)體中不能修改參數(shù)的值(包括參數(shù)本身的值或者參數(shù)其中包含的值)。voidfunction(constintVar);

//傳遞過(guò)來(lái)的參數(shù)在函數(shù)內(nèi)不可以改變

//(意義不大，因?yàn)閂ar本身就是形參)

voidfunction(constchar*Var);

//參數(shù)指針?biāo)竷?nèi)容為常量不可變voidfunction(char*constVar);

//參數(shù)指針本身為常量不可變

//(意義不大，因?yàn)閏har*Var也是形參)

參數(shù)為引用，為了增加效率同時(shí)防止修改。

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page25const修飾函數(shù)參數(shù)“const”修飾函數(shù)參數(shù)是它最廣泛的一種用途，它表示函數(shù)體中不能修改參數(shù)的值(包括參數(shù)本身的值或者參數(shù)其中包含的值)。參數(shù)為引用，為了增加效率同時(shí)防止修改。voidfunction(constClass&Var);//引用參數(shù)在函數(shù)內(nèi)不可以改變，

//

Class為定義的某個(gè)類(lèi)voidfunction(constTYPE&Var);//引用參數(shù)在函數(shù)內(nèi)為常量不可變，

//

TYPE為定義的某個(gè)基本或復(fù)合類(lèi)型

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page26enumBoolean{False,True};constintMax_length=100;//假定最大長(zhǎng)度為100template<classELEM>//類(lèi)型參數(shù)ELEM表示元素類(lèi)型Tclasslist{private: intmsize;//私有變量，順序表實(shí)例的最大長(zhǎng)度

intcurr_len; //私有變量，順序表實(shí)例的當(dāng)前長(zhǎng)度

ELEM*nodelist;//私有變量，存儲(chǔ)順序表實(shí)例的向量public:

intcurr;//當(dāng)前下標(biāo)，順序表的公共變量

list(constintsize);//創(chuàng)建一個(gè)新的順序表，實(shí)參傳遞表實(shí)例的最大長(zhǎng)度~list();//用于將該表實(shí)例從內(nèi)存中刪去2.2.1向量的類(lèi)定義北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page27BooleanisEmpty();//當(dāng)線(xiàn)性表為空時(shí)，返回Trueintlength();//返回此順序表的當(dāng)前實(shí)際長(zhǎng)度ELEMcurrValue();//返回當(dāng)前curr位置的元素值BooleanisInList();//若當(dāng)前下標(biāo)curr位置有值時(shí)，返回Truevoidappend(constELEM&);//在表尾增添一個(gè)新元素，順序表實(shí)際長(zhǎng)度加1voidinsert(constELEM&);//在當(dāng)前下標(biāo)curr位置插入元素新值ELEMremove();//當(dāng)前下標(biāo)curr位置的元素值作為返回值，并刪去該元素voidclear();//將順序表存儲(chǔ)的內(nèi)容清除，成為空表voidsetFirst();//將當(dāng)前下標(biāo)curr賦值為第一個(gè)元素的位置voidnext();

//將當(dāng)前下標(biāo)curr下移一格，即curr+1voidprev();//將當(dāng)前下標(biāo)curr上移一格，即curr-1}獲取訪(fǎng)問(wèn)輔助管理北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page282.2.2向量的運(yùn)算（示例）插入元素運(yùn)算voidinsert(constELEM&item)

刪除元素運(yùn)算

ELEMremove()

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

設(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)載或翻印必究Page30

//從表尾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)載或翻印必究Page31插入算法執(zhí)行時(shí)間

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

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

O（k）

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page32刪除算法/*設(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)載或翻印必究Page33ELEMtemp＝

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