合工大計算機專業(yè)相關(guān)課件數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)(第四章鏈棧和鏈隊列)

DataStructures胡學(xué)鋼張晶計算機與信息學(xué)院2009年9月1第四章鏈棧和鏈隊列

第四章鏈棧和鏈隊列

4.1引言

4.2鏈棧

4.3鏈隊列

2第四章鏈棧和鏈隊列4.1引言

前面已介紹的順序棧、順序隊列的有關(guān)特性回顧與分析：

運算實現(xiàn)：簡單，時間復(fù)雜度好。

存儲特性：靜態(tài)規(guī)模，編譯前確定。

問題：程序的通用性和空間利用率之間的矛盾！

期望：在實際運行過程中，根據(jù)實際問題的需要臨時確定存儲空間，這就涉及到動態(tài)變量。

動態(tài)變量：在程序運行過程中產(chǎn)生和釋放的變量。與之相反的是靜態(tài)變量，

靜態(tài)變量：在程序運行過程中一直存在的變量。在一般程序設(shè)計語言（如C、C++）中，靜態(tài)變量是出現(xiàn)在說明語句中的變量，而動態(tài)變量則由于是在運行過程中產(chǎn)生，因而不會事先說明。

如何實現(xiàn)動態(tài)變量？通過指針來實現(xiàn)：指針變量的說明，動態(tài)變量產(chǎn)生和釋放。34.1引言下面依次介紹指針變量動態(tài)變量的說明，動態(tài)變量操作、產(chǎn)生和釋放。（1）指針變量說明

例：變量說明語句intm,n,*p，*q;說明了4個變量，其中：m和n說明為int型，p,q為指向int型變量的指針，其所指示的變量名稱分別為*p，*q。（動態(tài)變量）指針和其所指示的變量之間的關(guān)系如下圖所示。1020p*pq*q指針和目標(biāo)變量的關(guān)系：所謂指針指向一個變量，就是存放著目標(biāo)變量的地址的值。44.1引言（2）動態(tài)變量的操作

基本操作：和其他類型的變量類似，可以對動態(tài)變量賦值、引用。特別要注意區(qū)分：指針賦值和動態(tài)變量賦值操作的關(guān)系和效果。例如語句*p=*q;和p=q;的效果存在明顯的差異：假設(shè)初始時*p=10；*q=20；如圖所示。1020p*pq*q*p=*q的效果201020p*pq*qp=q的效果區(qū)別：一個是整型變量的賦值，一個是指針型變量的賦值。*p54.1引言（3）動態(tài)變量產(chǎn)生動態(tài)變量需要在執(zhí)行申請變量操作后才能產(chǎn)生，否則無效。申請變量的操作如下：（對前面給出的變量說明）

p=newint;

------產(chǎn)生一個int類型變量，并將該變量的地址放到指針變量p中。（4）動態(tài)變量的釋放釋放變量：將動態(tài)變量的存儲空間還給系統(tǒng)，以便重新分配使用。釋放變量的操作：

deletep;-----釋放指針p所指示的變量（即*p）的存儲空間（因而使*p無效，除非重新賦值或申請）64.1引言例：閱讀下面程序，寫出運行結(jié)果。intmain(){int*p,*q;p=newint;q=newint;*p=10;*q=20;cout<<*p<<*q<<endl;*p=*q;*q=30;cout<<*p<<*q<<endl;p=q;*p=40;*q=50;cout<<*p<<*q<<endl;deletep;}輸出結(jié)果是？74.2鏈棧4.2.1鏈表為了避免前述的順序存儲方式在的問題規(guī)模事先難以確定的問題，可以將表中元素用鏈地址連接起來構(gòu)成一個表。由此而得到鏈表。鏈表：將表中元素用鏈地址連接起來構(gòu)成的表。例如，下圖就是一個鏈表的示意圖，其中：由若干稱為結(jié)點的“單元”連接而成。每個結(jié)點由兩部分組成：存放元素值的字段存放下一個結(jié)點的地址的字段。另外，有一個指向表頭的指針（頭指針）head，指示起點。最后一個結(jié)點（也稱為尾結(jié)點）的后繼指針為空值，表示其后續(xù)沒有結(jié)點了。結(jié)點尾結(jié)點a1a2a3an……∧

head頭指針84.2鏈棧鏈表存儲結(jié)構(gòu)的實現(xiàn)如何實現(xiàn)鏈表的存儲結(jié)構(gòu)？

對此，可有兩類方法，其一是用數(shù)組來實現(xiàn)，其二是用動態(tài)鏈表。1.用數(shù)組來存儲表中元素------靜態(tài)鏈表就是用數(shù)組元素存儲表中元素的值，以及后續(xù)元素的地址。（因而需要說明為構(gòu)造類型）例如，右圖是一個存儲了部分英語字母的鏈表。這類表由于數(shù)組的規(guī)模事先確定，因而稱為靜態(tài)鏈表。靜態(tài)鏈表的不足：難以兼顧到通用性和存儲空間的利用率。E6D0A3B4C1G-1F50123456下標(biāo)datanexthead=2∧94.2鏈棧2.采用動態(tài)變量來實現(xiàn)——動態(tài)鏈表

其中每個結(jié)點用一個結(jié)構(gòu)來描述，包括兩個字段，存放元素值的字段data存放下一個結(jié)點的指針如右圖所示。設(shè)結(jié)點類型為node，則類型描述如下：

typedefstruct{elementtypedata;//元素字段node*next;//指針字段}node;

不特別說明的情況下，鏈棧就是采用動態(tài)鏈表來存儲，就是鏈棧。

datanextnode類型104.2鏈棧4.2.2鏈棧結(jié)構(gòu)及描述可以用鏈表來存儲棧：表頭存儲棧頂元素;設(shè)一個棧頂指針。如圖所示。結(jié)構(gòu)的描述：數(shù)據(jù)成員：除了計數(shù)分量count外，還需要給出棧頂指針top.函數(shù)成員：原有的函數(shù)full（）可以不用（為什么？）。由于鏈表采用的是動態(tài)結(jié)構(gòu)，即使在棧變量的作用域外，動態(tài)變量也不會自行釋放。因此，需要設(shè)一個析構(gòu)函數(shù)，以便在棧變量無效時自行釋放鏈表的存儲空間。antopa1a2a3∧

……114.2鏈棧由此得類stack的描述如下：classstack{public://函數(shù)成員stack();~stack();Boolempty()const;Boolfull()const;error_codeget_top(elementtype&x)const;error_codepush(constelementtyoex);error_codepop();private://數(shù)據(jù)成員intcount;node*top;//棧頂指針};新增的析構(gòu)函數(shù)原有的函數(shù)124.2鏈棧4.2.3鏈棧運算的實現(xiàn)初始化運算的實現(xiàn)：stack::stack（）{count=0;top=NULL;}判斷空的實現(xiàn)：Boolstack::empty(){returncount==0;}//等價于：returntop==NULL;判斷滿的實現(xiàn)：Boolstack::full(){returnFALSE;}//本函數(shù)無實際意義134.2鏈棧取棧頂元素的實現(xiàn)：error_codestack::get_top(elementtype&x)const{if(empty())returnunderflow;x=top->data;returnsuccess;}析構(gòu)函數(shù)的實現(xiàn)：主要任務(wù)是釋放鏈表中各結(jié)點的存儲空間，有兩種方法，一種方法是：直接釋放各結(jié)點的存儲空間。另一種方法是：調(diào)用后面要描述的出棧算法：逐個將元素出棧，直到為空為止。（下面采用這種方法來實現(xiàn)）error_codestack::~stack(){while(!empty())pop();}144.2鏈棧入棧運算的實現(xiàn)入棧就是將待插入元素裝入一個結(jié)點后，連接到鏈表的表頭上。因此，操作包括：產(chǎn)生結(jié)點；裝入元素的值到結(jié)點中；連接結(jié)點到表頭----注意連接操作的順序。修改其他信息。操作過程如下圖所示。算法如下：error_codestack::push(constelementtypex){s=newnode;s->data=x;//產(chǎn)生結(jié)點；裝入元素的值到結(jié)點中；s->next=top;top=s;//連接結(jié)點到表頭count++;//計數(shù)returnsuccess;//返回成功操作標(biāo)志}a1a2a3an∧……xstop①②③154.2鏈棧出棧運算的實現(xiàn)出棧操作就是刪除表頭結(jié)點，并使放其元素空間。另外要修改相關(guān)的信息。注意刪除操作的次序。error_codestack::pop(){if(empty())returnunderflow;u=top;top=top->next;deleteu;count--;returnsuccess;}a1a2a3an^……top③釋放該結(jié)點u①②164.3鏈隊列4.3.1鏈隊列存儲結(jié)構(gòu)

分析：在用如圖所示鏈表存儲隊列時，如何確定其對應(yīng)關(guān)系？即隊頭、隊尾元素的位置-------不同結(jié)構(gòu)影響運算的性能。首先，隊頭位置的確定。如果將表頭作為隊尾，顯然不便（？）因此，應(yīng)將表頭設(shè)置為隊頭，因而將表頭指針標(biāo)記為front.

其次，為了使入隊操作更快捷，需要設(shè)置尾指針（為什么？），不妨設(shè)為rear.如圖所示。另外，為了使入隊操作在隊列為空和不空時的操作保持一致，特別設(shè)置一個不存放元素值的附加結(jié)點（稱為頭結(jié)點）。如圖所示。不做強調(diào)的情況下，后面的鏈隊列均為此結(jié)構(gòu)。fronta1a2a3an^……rear/////frontfront174.3鏈隊列由上述討論可得到鏈隊列類queue的描述如下：其中：數(shù)據(jù)成員部分除了計數(shù)變量count外，增設(shè)了頭尾指針。函數(shù)成員中增設(shè)了析構(gòu)函數(shù)。另外，判斷滿的函數(shù)可以不用。

classqueue{public://函數(shù)成員queue();~queue();Boolempty()const;Boolfull()const;error_codeget_front(elmenttype&x)const;error_codeappend(constelementtypex);error_codeserve();private://數(shù)據(jù)成員intcount;node*front,*rear;

};新增的析構(gòu)函數(shù)原有的函數(shù)184.3鏈隊列4.3.2鏈隊列的運算實現(xiàn)如前所述，鏈隊列的結(jié)構(gòu)為帶頭結(jié)點的鏈表，如下圖所示。運算實現(xiàn)：初始化的實現(xiàn)：分析：首先要清楚，空隊列的結(jié)構(gòu)形式：元素個數(shù)為0，但要有頭結(jié)點----事先沒有，需要產(chǎn)生出來。如圖所示。算法如下。queue::queue（）{front=newnode;//產(chǎn)生由頭指針front指示的頭結(jié)點rear=front;//尾指針也指向頭結(jié)點front->next=NULL;//頭結(jié)點（此時也是尾結(jié)點）后繼指針設(shè)置為空count=0;}

^frontrearfronta1a2an^a3……rear194.3鏈隊列判斷空的運算的實現(xiàn)

Boolstack::empty(){returncount==0;};

//等價于

returnfront==rear;或

returnfront->next=NULL；判斷滿的運算的實現(xiàn)

Boolstack::full(){returnFALSE;}//本函數(shù)無實際意義取隊頭元素運算的實現(xiàn)error_codequeue::get_front(elementtype&x)const{if(empty())returnunderflow;x=front->next->data;returnsuccess;}204.3鏈隊列入隊運算的實現(xiàn)分析：對鏈隊列的入隊操作應(yīng)當(dāng)包括如下操作：產(chǎn)生結(jié)點，裝入待插入元素；將新結(jié)點連接到表尾；調(diào)整尾指針；計數(shù)。如下圖所示。算法如下：error_codequeue::append(constelementtypex){s=newnode;s->data=x;s->next=NULL;rear->next=s;rear=s;count++;returnsuccess;}fronta1a2an^a3……rears①

②x③^④⑤214.3鏈隊列出隊運算的實現(xiàn)分析：在隊列不空的情況下，出隊運算就是刪除表頭結(jié)點，即刪除由指針

？

所指向的結(jié)點