數據結構與算法b-2014年3月07日課堂listmar

數據結構與算法

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

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

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

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

向量(vector)2.3鏈表(linkedlist)2.4線性表實現方法的比較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線性表的性質（續）（d）線性表所包含的結點個數稱為線性表的長度，它是線性表的一個重要參數；長度為0的線性表稱為空表；（e）線性表的關系r，簡稱“前驅關系”，應具有反對稱性和傳遞性(離散數學中的概念)。設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線性表的抽象數據類型2.1.2線性表的存儲結構2.1.3線性表運算分類2.2順序表—

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

取值空間運算集

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

使用（靜態）常數作為向量長度

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

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

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

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

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

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

voidfunction(constchar*Var);

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

//參數指針本身為常量不可變

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

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

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

//

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

//

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

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

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

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

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

list(constintsize);//創建一個新的順序表，實參傳遞表實例的最大長度~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++;}循環至i=curr+1，最后一次移動是nodelist[curr]北京大學信息學院，轉載或翻印必究Page31插入算法執行時間

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

:總時間開銷估計為：

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