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

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

北京大學(xué)信息科學(xué)與技術(shù)學(xué)院，轉(zhuǎn)載或翻印必究北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page22.6.1順序隊列

使用順序表來實現(xiàn)隊列用向量存儲隊列元素兩個變量分別指向隊列的前端和尾端

順時針前驅(qū)關(guān)系北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page3隊列的類定義

#include<assert.h>classQueue{private: float*Qlist;//存放數(shù)據(jù)元素的向量

intfront，rear; //隊列前端和尾端向量的下標(biāo)值

//當(dāng)新元素進入或隊列尾端的元素取出，

//這兩個變量值隨之增減北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page4 intmaxsize;

//隊列最大長度

intcurr_len;//隊列當(dāng)前長度public：

//創(chuàng)建隊列實例，指定該實例的向量空間長度

Queue(intsize); …};北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page5隊列的創(chuàng)建Queue::Queue(intsize=7){//隊列實例的創(chuàng)建，指定最大長度7maxsize=size;

//動態(tài)開辟向量存儲空間

//判new成功否，否則斷言程序異常，退出運行

Qlist=newfloat[maxsize];assert(ElmList!=NULL);front=rear=curr_len=0;//清空隊列}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page6新元素壓入隊列尾端北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page7新元素壓入隊列尾端voidQueue::EnQueue(floatitem){

//判隊列滿，否則隊列溢出異常，退出運行

assert(curr_len!=maxsize);curr_len++;Qlist[rear]=item;//在隊列尾端加入隊列

rear=(rear+1)%maxsize;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page8元素從隊列前端取出

floatQueue::DeQueue(){floattemp; //若隊列已空，異常退出運行

assert(curr_len!=0);temp=Qlist[front];curr_len--;front=(front+1)%maxsize;returntemp;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page92.6.2鏈?zhǔn)疥犃?/p>

單鏈表隊列

鏈接指針的方向從隊列的前端向尾端鏈接

鏈接指針的方向可否從隊列的后端向前端鏈接？單鏈的last指針有功用嗎？北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page10鏈?zhǔn)疥犃械念惗x

#include<assert.h>classQueue{private: ListPtrfront,rear;//單鏈表，其結(jié)點類型為ListNode intcurr_len;public：

//創(chuàng)建一個空隊列，不用指定最大長度

Queue(){ front=rear=NULL; curr_len=0; }；

…}；北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page11將元素加入單鏈隊列尾端

voidQueue::EnQueue(ELEMitem){ ListPtrtemp; temp=newListNode; assert(temp!=NULL);//若無存儲空間則異常

temp->data=item; temp->link=NULL;//temp將成為隊列尾部結(jié)點北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page12 if(curr_len!=0){//隊列尾端指針rear非NULL

rear->link=temp; rear＝temp;//更新隊列尾端指針

} else front=rear=temp; //只有一個結(jié)點時，隊列前端和尾端指針相同

curr_len++;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page13自單鏈隊列前端取出

ELEMQueue::DeQueue(){assert(curr_len!=0);//確定隊列非空ELEMresult=front->data;//暫存隊列頂內(nèi)容ListPtrtemp=front;//暫存原先前端指針

front=front->link;//更新前端指針

deletetemp;//刪除原先前端指針

所指向的結(jié)點

curr_len--;if（curr_len==0） rear=front=NULL;returnresult;}

若curr_len非零，需要更新表尾指針rear嗎？北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page142.6.3順序隊列與鏈?zhǔn)疥犃械谋容^

順序隊列

固定的存儲空間方便訪問隊列內(nèi)部元素鏈?zhǔn)疥犃锌梢詽M足浪涌大小無法估計的情況

訪問隊列內(nèi)部元素不方便

“浪涌電流”是指電網(wǎng)中出現(xiàn)的短時間象“浪”一樣的高電壓引起的大電流。當(dāng)某些大容量的電氣設(shè)備接通或斷開時間，由于電網(wǎng)中存在電感，將在電網(wǎng)產(chǎn)生“浪涌電壓”，從而引發(fā)浪涌電流。那么隊列中的“浪涌”現(xiàn)象？相比順序隊列，隊列正常出入操作會有不便嗎？北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page15大綱2.5棧(stack)2.5.1順序棧

2.5.2鏈?zhǔn)綏?/p>

2.5.3順序棧與鏈?zhǔn)綏５谋容^

2.5.4棧的應(yīng)用——后綴表達式求值2.6隊列(queue)2.6.1順序隊列

2.6.2鏈?zhǔn)疥犃?/p>

2.2.3順序隊列與鏈?zhǔn)疥犃械谋容^

2.7棧與遞歸(recursivefunction)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page16C/C++編譯的程序占用的內(nèi)存是怎樣的？程序中哪些代碼放在棧區(qū)(stack)？哪些放在堆區(qū)(heap)？函數(shù)壓棧怎么回事？北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page17什么是堆和棧？一個由C/C++編譯的程序運行占用的內(nèi)存分為以下部分:棧區(qū)（stack）由編譯器產(chǎn)生的代碼將自動分配釋放、存放函數(shù)的參數(shù)值、局部變量的值等其操作方式類似于數(shù)據(jù)結(jié)構(gòu)中的棧

堆區(qū)（heap）一般由程序員分配釋放；若程序員不釋放，當(dāng)程序自動結(jié)束或強制終止時，可能由操作系統(tǒng)回收。與數(shù)據(jù)結(jié)構(gòu)中的堆是兩回事，分配方式類似于鏈表

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page18全局區(qū)（靜態(tài)區(qū)）（static）初始化的全局變量和靜態(tài)變量存放在一塊區(qū)域未初始化的全局變量和靜態(tài)變量存放在相鄰另一塊區(qū)域程序結(jié)束后由操作系統(tǒng)收回

文字常量區(qū)常量字符串存放在這里，程序結(jié)束后由操作系統(tǒng)收回。程序代碼區(qū)存放函數(shù)體的二進制代碼。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page19示例

int

a

=

0;

//全局初始化區(qū)

char

*p1;

//全局未初始化區(qū)

main()

{

int

b;

char

s[]

=

“abc”;

char

*p2;

//棧

char

*p3

=

“123456”;

//123456\0在常量區(qū)，p3在棧上

static

int

c

=0；

//全局（靜態(tài)）初始化區(qū)

p1

=

(char

*)malloc(10);

p2

=

(char

*)malloc(20);

//分配得來10和20字節(jié)的區(qū)域就在堆區(qū)

strcpy(p1,

"123456");

//123456\0放在常量區(qū)，

//編譯器可能會將它與p3所指向的“123456”優(yōu)化成一個地方

}

棧區(qū)（stack）堆區(qū)（heap）全局區(qū)（靜態(tài)區(qū)）（static）文字常量區(qū)程序代碼區(qū)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page20函數(shù)調(diào)用過程中涉及的

壓棧、出棧處理？函數(shù)調(diào)用時首先進棧的是主函數(shù)中的下一條指令（函數(shù)調(diào)用語句的下一條可執(zhí)行語句）的地址；然后是函數(shù)的各個參數(shù)，在大多數(shù)的C編譯器中，參數(shù)是由右往左入棧的；然后是函數(shù)中的局部變量。注意:靜態(tài)變量是不入棧的函數(shù)調(diào)用結(jié)束后北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page21當(dāng)本次函數(shù)調(diào)用結(jié)束后局部變量先出棧，然后是參數(shù)，最后棧頂指針指向最開始存的地址，也就是主函數(shù)中的下一條指令，程序由該點繼續(xù)運行。

棧的先入后出的順序使得函數(shù)可以嵌套、遞歸；如果遞歸層數(shù)太多，棧也會滿，就會出現(xiàn)棧溢出。

在WINDOWS下，棧的缺省大小是1M（編譯時就確定的常數(shù)）；在SunOS/Solaris/Linus下，棧的缺省大小是8M；如果申請的空間超過棧的剩余空間時，將提示overflow。

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page22如何修改棧的大小?Windows(duringcompilation):1.Select"Project->Setting".2.Select"Link"page.3.Select"Category"to"Output".4.Typeyourpreferredstacksizein“Reserve:”fieldunder“Stackallocations”.e.g.,32768indecimalor0x20000inhexadecimal.Windows(tomodifytheexecutablefile):TwoprogramsincludedinMicrosoftVisualStudio,"dumpbin.exe"and"editbin.exe".Run"dumpbin/headersexecutable_file",andyoucanseethe"sizeofstackreserve"informationin"optionalheadervalues".Run"editbin/STACK:size"tochangethedefaultstacksize.

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page232.7棧與遞歸函數(shù)的遞歸定義

程序間(比如主程序和子程序)參數(shù)傳遞

棧在實現(xiàn)函數(shù)遞歸調(diào)用中所發(fā)揮的作用

遞推法遞歸窮舉搜索法貪婪法分治法動態(tài)規(guī)劃法迭代法北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page24遞歸算法一般用于

解決三類問題數(shù)據(jù)的定義是按遞歸定義的(Fibonacci函數(shù))問題解法通過遞歸算法實現(xiàn)(回溯)數(shù)據(jù)結(jié)構(gòu)形式是按遞歸定義的廣義表、樹的遍歷、圖的搜索遞歸的缺點：運行效率較低遞歸次數(shù)過多容易造成棧溢出等

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page25德羅斯特效應(yīng)(DrosteEffect)

“遞歸的一種視覺形式”TheDrosteeffectisaspecifickindofrecursivepicture,onethatinheraldryistermedmiseenabyme.AnimageexhibitingtheDrosteeffectdepictsasmallerversionofitselfinaplacewhereasimilarpicturewouldrealisticallybeexpectedtoappear.Thissmallerversionthendepictsanevensmallerversionofitselfinthesameplace,andsoon.Onlyintheorycouldthisgoonforever;practically,itcontinuesonlyaslongastheresolutionofthepictureallows,whichisrelativelyshort,sinceeachiterationexponentiallyreducesthepicture'ssize.Itisavisualexampleofastrangeloop,aself-referentialsystemofinstancing.北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page26北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page27德羅斯特效應(yīng)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page28

遞歸定義示例:階乘n！的遞歸定義如下：

(n)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page29計算階乘n！的兩個程序

循環(huán)迭代vs.遞歸//使用循環(huán)迭代方法，計算階乘n!的程序longfactorial(longn){ intm=1; if(n>0) for(inti=1;i<=n;i++) m=m*i; returnm;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page30//遞歸定義的計算階乘n!的函數(shù)longfactorial(longn){ if(n==0) return1; else returnn*factorial(n-1);//遞歸調(diào)用}一種直接或者間接地調(diào)用自身的算法，遞歸要素包括：邊界條件：確定遞歸到何時終止，也稱為遞歸出口，所描述問題的最簡單情況。遞歸規(guī)模：大問題是如何分解為小問題的，也稱為遞歸體，使問題向邊界條件轉(zhuǎn)化的規(guī)則。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page31用5個F機器來模擬4!的計算1.左邊是一個F機器，它能夠計算乘積并能夠與其他機器交換信息。2.通過內(nèi)部棧交換信息；右邊是它們所使用的棧。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page32北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page33遞歸內(nèi)部棧(形參)情況

-內(nèi)部棧交換信息longfactorial(longn){ if(n==0) return1; else returnn*factorial(n-1);}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page34longfactorial(longn){ if(n==0) return1; else returnn*factorial(n-1);}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page35示例:

hanoi塔問題的遞歸求解

漢諾塔是源自印度神話里的玩具主神梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上從下往上安大小順序摞著64片黃金圓盤。主神命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。有預(yù)言說，這件事完成時宇宙會在一瞬間閃電式毀滅。也有人相信婆羅門至今還在一刻不停地搬動著圓盤。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page36

圖示:hanoi塔的執(zhí)行過程北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page37河內(nèi)塔問題的遞歸求解程序hanoi(n,X,Y,Z)的含義是： 移動n個槃環(huán)，由X柱子（出發(fā)柱）將槃環(huán)移動到Z柱（終點柱）。其移動過程中，Y柱和X柱皆可用于暫時存放環(huán)槃，不過注意每一步移動都必須嚴(yán)格遵循大盤不能壓小盤的原則。例如，hanoi(2,‘B’,‘C’,‘A’),其含義是初始位于B柱上部的2個環(huán)槃移動到