數(shù)據(jù)結構與算法

—線性結構主講教員:段凌宇2014年3月7日

北京大學信息科學與技術學院，轉載或翻印必究北京大學信息學院，轉載或翻印必究Page2大綱2.1線性表(linearlist)2.2順序表—

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

1.2什么是數(shù)據(jù)結構北京大學信息學院，轉載或翻印必究Page4大綱2.1線性表(linearlist)2.1.0線性表的定義和性質2.1.1線性表的抽象數(shù)據(jù)類型2.1.2線性表的存儲結構2.1.3線性表運算分類2.2順序表—

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

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

→

(x,z)∈R北京大學信息學院，轉載或翻印必究Page8大綱2.1線性表(linearlist)2.1.0線性表的定義和性質2.1.1線性表的抽象數(shù)據(jù)類型2.1.2線性表的存儲結構2.1.3線性表運算分類2.2順序表—

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

取值空間運算集

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

//私有變量，線性表存儲空間;例如ELEMelements[Max_length];public: intcurr_len; //公共變量，該線性表的當前長度

intcurr; //公共變量，該線性表的當前“指針”，游標

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

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

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

voidinsert(inti,ELEMvalue);//第i號位置上插入一個新結點

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

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

定長的一維數(shù)組結構即向量型的順序存儲結構，地址相鄰存儲

缺陷：長度變化不得超過固定長度變長的線性存儲結構鏈接式存儲結構，使用指針表示前驅關系串結構、動態(tài)數(shù)組、以及順序文件

北京大學信息學院，轉載或翻印必究Page132.1.3線性表運算分類

創(chuàng)建線性表的一個實例(list()）線性表消亡（~list()）

獲取有關當前線性表的信息

查找、由位置讀取等訪問線性表并改變線性表的內容或結構添加、更新、刪除、清空等線性表的輔助性管理操作游標加減、求表的長度實現(xiàn)算法及其復雜性與采用的存儲結構有密切關系北京大學信息學院，轉載或翻印必究Page14大綱2.1線性表(linearlist)2.2順序表—

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

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

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

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

數(shù)組存儲；主要優(yōu)點是讀寫其元素很方便，通過下標即可指定位置。

北京大學信息學院，轉載或翻印必究Page16函數(shù)調用過程中涉及的“形參”、“實參”“傳遞變量指針”、“引用形參”const修飾北京大學信息學院，轉載或翻印必究Page17函數(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;}結果：i=3,j=4i=3,j=4執(zhí)行函數(shù)swap后，形參a和b的改變不會影響實參i和j的值北京大學信息學院，轉載或翻印必究Page18函數(shù)調用過程形參與實參傳給形參的是變量的值傳遞是單向的；如果在執(zhí)行函數(shù)期間形參的值發(fā)生變化，并不傳回給實參。因為在調用函數(shù)期間，形參和實參不是同一個存儲單元。北京大學信息學院，轉載或翻印必究Page19函數(shù)調用過程形參與實參調用函數(shù)時把變量i和j的地址傳送給形參p1和p2，因此*p1和i為同一內存單元，*p2和j是同一內存單元。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;}結果：i=3,j=4i=4,j=3北京大學信息學院，轉載或翻印必究Page20函數(shù)調用過程傳遞變量指針傳給形參的是指針變量，實參是一個變量的地址；調用函數(shù)時，形參（指針變量）指向實參變量單元。這種方式還是“值傳遞”，只不過實參的值是變量的地址而已。在函數(shù)中改變的不是實參的值，而是實參地址所指向的變量的值。北京大學信息學院，轉載或翻印必究Page21函數(shù)調用過程的引用形參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;}結果：i=3,j=4i=4,j=3由實參把變量名傳給形參。i的名字傳給引用變量a，j的名字傳給引用變量b。此時a和b就分別與i,j占用同一內存空間。北京大學信息學院，轉載或翻印必究Page22函數(shù)調用過程的引用形參這種把實參地址傳遞到形參，使形參的地址取實參的地址，從而使形參與實參共享同一單元的方式，就是地址傳遞方式。示例(2)中，傳遞指針變量要另外開辟內存單元，其內容為地址；而示例(3)引用不是一個獨立的變量，不單獨占內存單元。示例(3)

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

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

//傳遞過來的參數(shù)在函數(shù)內不可以改變

//(意義不大，因為Var本身就是形參)

voidfunction(constchar*Var);

//參數(shù)指針所指內容為常量不可變voidfunction(char*constVar);

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

//(意義不大，因為char*Var也是形參)

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

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

//

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

//

TYPE為定義的某個基本或復合類型

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

intcurr_len; //私有變量，順序表實例的當前長度

ELEM*nodelist;//私有變量，存儲順序表實例的向量public:

intcurr;//當前下標，順序表的公共變量

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

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

刪除元素運算

ELEMremove()

北京大學信息學院，轉載或翻印必究Page29插入算法/*

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

//需要檢查當前長度不能大于或等于msize;//當前游標指針curr不能小于0,也不能大于或等于當前長度;

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

assert((curr_len<msize)&&(curr>=0)&&(curr<curr_len));北京大學信息學院，轉載或翻印必究Page30

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

for

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

//當前指針處插入新元素

nodelist[curr]=item;

//表的實際長度curr_len加1

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

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

:總時間開銷估計為：

O（k）

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

//需要檢查當前長度不能大于msize;//當前游標指針curr不能小于0,也不能大于等于當前長度;

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

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

nodelist[curr];//從指針curr到curr_len每個元素往前移一格for(inti=curr;i<curr_len-1;i++)nodelist[i]=nodelist[i+1];curr_len--;//表的實際長度cur