數(shù)據(jù)結(jié)構(gòu)與算法b-2014年3月07日課堂listmar_第1頁
數(shù)據(jù)結(jié)構(gòu)與算法b-2014年3月07日課堂listmar_第2頁
數(shù)據(jù)結(jié)構(gòu)與算法b-2014年3月07日課堂listmar_第3頁
數(shù)據(jù)結(jié)構(gòu)與算法b-2014年3月07日課堂listmar_第4頁
數(shù)據(jù)結(jié)構(gòu)與算法b-2014年3月07日課堂listmar_第5頁
已閱讀5頁,還剩32頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

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

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

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

向量(vector)2.3鏈表(linkedlist)2.4線性表實(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)系)線性結(jié)構(gòu)(linearstructure)樹型結(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)算(算法->程序->解決問題)

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

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

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

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

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

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

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

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

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

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

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

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

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

voidremove(inti);//刪去第i號元素,表的長度減1,其后元素前移

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

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

缺陷:長度變化不得超過固定長度變長的線性存儲(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線性表運(yùn)算分類

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

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

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

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

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

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

使用(靜態(tài))常數(shù)作為向量長度

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

北京大學(xué)信息學(xué)院,轉(zhuǎn)載或翻印必究Page16函數(shù)調(diào)用過程中涉及的“形參”、“實(shí)參”“傳遞變量指針”、“引用形參”const修飾北京大學(xué)信息學(xué)院,轉(zhuǎn)載或翻印必究Page17函數(shù)調(diào)用過程形參與實(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)用過程形參與實(shí)參傳給形參的是變量的值傳遞是單向的;如果在執(zhí)行函數(shù)期間形參的值發(fā)生變化,并不傳回給實(shí)參。因?yàn)樵谡{(diào)用函數(shù)期間,形參和實(shí)參不是同一個(gè)存儲(chǔ)單元。北京大學(xué)信息學(xué)院,轉(zhuǎn)載或翻印必究Page19函數(shù)調(diào)用過程形參與實(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)用過程傳遞變量指針傳給形參的是指針變量,實(shí)參是一個(gè)變量的地址;調(diào)用函數(shù)時(shí),形參(指針變量)指向?qū)崊⒆兞繂卧_@種方式還是“值傳遞”,只不過實(shí)參的值是變量的地址而已。在函數(shù)中改變的不是實(shí)參的值,而是實(shí)參地址所指向的變量的值。北京大學(xué)信息學(xué)院,轉(zhuǎn)載或翻印必究Page21函數(shù)調(diào)用過程的引用形參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){//形參為引用類型

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)用過程的引用形參這種把實(shí)參地址傳遞到形參,使形參的地址取實(shí)參的地址,從而使形參與實(shí)參共享同一單元的方式,就是地址傳遞方式。示例(2)中,傳遞指針變量要另外開辟內(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)用過程中涉及的“形參”、“實(shí)參”“傳遞變量指針”、“引用形參”const修飾北京大學(xué)信息學(xué)院,轉(zhuǎn)載或翻印必究Page24const修飾函數(shù)參數(shù)“const”修飾函數(shù)參數(shù)是它最廣泛的一種用途,它表示函數(shù)體中不能修改參數(shù)的值(包括參數(shù)本身的值或者參數(shù)其中包含的值)。voidfunction(constintVar);

//傳遞過來的參數(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è)類voidfunction(constTYPE&Var);//引用參數(shù)在函數(shù)內(nèi)為常量不可變,

//

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

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

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

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

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

list(constintsize);//創(chuàng)建一個(gè)新的順序表,實(shí)參傳遞表實(shí)例的最大長度~list();//用于將該表實(shí)例從內(nèi)存中刪去2.2.1向量的類定義北京大學(xué)信息學(xué)院,轉(zhuǎn)載或翻印必究Page27BooleanisEmpty();//當(dāng)線性表為空時(shí),返回Trueintlength();//返回此順序表的當(dāng)前實(shí)際長度ELEMcurrValue();//返回當(dāng)前curr位置的元素值BooleanisInList();//若當(dāng)前下標(biāo)curr位置有值時(shí),返回Truevoidappend(constELEM&);//在表尾增添一個(gè)新元素,順序表實(shí)際長度加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}獲取訪問輔助管理北京大學(xué)信息學(xué)院,轉(zhuǎn)載或翻印必究Page282.2.2向量的運(yùn)算(示例)插入元素運(yùn)算voidinsert(constELEM&item)

刪除元素運(yùn)算

ELEMremove()

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

設(shè)元素類型為ELEM,nodelist是存儲(chǔ)順序表向量,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)前長度;

//此條件不滿足時(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í)際長度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í)間開銷估計(jì)為:

O(k)

北京大學(xué)信息學(xué)院,轉(zhuǎn)載或翻印必究Page32刪除算法/*設(shè)元素類型為ELEM,nodelist是存儲(chǔ)順序表向量,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)前長度;

//此條件不滿足時(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í)際長度cur

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論