線性鏈表2.4 數組_第1頁
線性鏈表2.4 數組_第2頁
線性鏈表2.4 數組_第3頁
線性鏈表2.4 數組_第4頁
線性鏈表2.4 數組_第5頁
已閱讀5頁,還剩77頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

2.3線性鏈表及其運算線性表的順序存儲結構容易實現,可以隨機存取表中的任意元素。順序表缺點是:難于插入、刪除操作;需要預先分配空間,不管這些空間能否最大限度地利用。鏈表存儲結構在這兩個方面恰好是優(yōu)點:容易插入、刪除操作不需要預分空間。鏈表基本概念定義:線性表的鏈式存儲結構稱為線性鏈表

結點(NODE):表中元素的存儲單元。由數據域和指針域組成。數據域存放元素數據,指針域存放指向下一結點位置的指針。結點形式為:

datanext數據域指針域鏈表(Link):由結點組成的表。頭指針(head):指向鏈表中第1個結點的指針。舉例由食品組成的單鏈表(biscuit,butter,cheese,eggs,grapes,jam)

grapesbiscuitbuttercheesejameggs^head

頭指針最后一個結點指針域為空單鏈表的物理存儲

存儲地址數據域(data)指針域(next)grapes60biscuit61cheese13eggs1jamNULLbutter121111213606111頭指針

head(biscuit,butter,cheese,eggs,grapes,jam)線性鏈表類P57Template<classT>

structnode{Tdata;node*next;};Template<classT>classlinked_list{private:node<T>*head;public:linked_list();//建立空鏈表

intflag_linked_list();//判斷鏈表狀態(tài)

{if(head==NULL)return0;return1;}voidprt_linked_list();//從頭指針開始輸出

voidins_linked_list(T);//插入到鏈表頭

Tdel_linked_list();//刪除鏈頭}參考P58課堂練習P58例子2.12定義一個空鏈表,依次插入1-100打印輸出;然后刪除前50個結點,并再次輸出。

帶鏈的棧棧也是線性表,可以采用鏈式存儲結構順序棧最多可用于2個棧的共享,對于更多的棧就難于表達了。對于最大空間需要量事先不知的情況,就不能使用順序棧了。這時,就需要采用鏈棧。鏈棧:棧的鏈式存儲結構鏈棧示意圖a1a2a3^棧底top棧頂…...aiTemplate<classT>structnode{Tdata;node*next;};template<classT>classlinked_Stack{private:node<T>*top;

//棧頂指針

棧的鏈式表示—鏈棧public: linked_stack(); voidprt_linked_stack();intflag_linked_stack();voidins_linked_stack(T);Tdel_linked_stack(); Tread_linked_stack();}

鏈棧為空的條件:

top=NULL

鏈棧為滿的條件(無法繼續(xù)申請新結點):t=NULLt為申請的結點,為NULL表示失敗。

鏈棧進棧操作操作步驟:step1:申請一個鏈棧結點,若t=NULL,則表示鏈滿;否則,執(zhí)行step2;step2:在top所指結點之前插入新結點,并將top指向新申請的結點t。template<classT>

voidlinked_Stack<T>::

ins_linked_stack(Tx){node<T>*p=newnode<T>;if(p==NULL)return;p->data=x;p->next=top;top=p;}鏈棧進棧算法鏈棧出棧操作操作步驟:step1若鏈棧為空,則輸出棧溢出信息;否則,執(zhí)行step2。step2(保存top)并使top指向被刪除結點的后件結點,刪除top所指結點。step3釋放被刪除結點的存儲空間。返回出棧元素值。template<classT>

Tlinked_Stack<T>::del_linked_stack(){Ty;node<T>*q;if(top==NULL){cout<<“空?!?lt;<endl;

return0;}q=top;y=q->data;top=q->next;deleteq;return(y);}課堂練習P62,參考2.13;建立空棧,入棧10,20,30,40,50;退棧2次,然后輸出棧中所有的元素;4帶鏈的隊列1).隊列也是線性表,可以采用鏈式存儲結構。datanext數據域指針域2).存儲結構的C++語言描述,template<classT>//模板聲明,數據元素虛擬類型為Tclasslinked_Queue//循環(huán)隊列類{private://數據成員

intmm;//存儲空間容量

node<T>*front;//排頭指針

node<T>*rear;//隊尾指針public://成員函數

linked_Queue(int);//構造函數,建立空循環(huán)隊列

voidprt_linked_Queue();//輸出排頭與隊尾指針以及隊中元素

intflag_linked_Queue();//檢測循環(huán)隊列的狀態(tài)

voidins_linked_Queue(T);//入隊

Tdel_linked_Queue();};//退隊鏈隊列為空的表示鏈隊列為空,

Queue.front=Queue.rear表示形式:

front

rearfront

rear

^...ana2a1鏈隊滿的條件為:T=NULL。T為新創(chuàng)建的結點,非空隊列:NULL鏈隊列的入隊操作要求:在鏈隊列中插入一個元素x(入隊運算)。

算法操作步驟:

Step1:申請建立一個新結點p;Step2:判別p是否為空;若空,表示隊列已滿;Step3:非空,將p插入鏈中,修改rear指針。template<classT>//入隊T linked_Queue<T>::ins_linked_Queue(Tx){

node<T>*p;p=newnode<T>;if(p==NULL){cout<<“隊列已滿\n”);return(0);}p->dada=x;p->next=NULL;if(rear==NULL)

front=p;elserear->next=p;rear=p;return;}

鏈隊列的出隊操作出隊操作要考慮兩種情況:當隊列長度為1時,除了修改隊頭指針外,還要修改隊尾指針。QueueQueuefrontrearrearfronta1

an

^a1a2

...a2

^...an

^

當隊列長度大于1時,只修改隊頭指針即可Queuean^rearQueuefrontrearTfrontNULL鏈隊列的出隊操作要求:在鏈隊列中刪除一個元素(退隊運算)。算法描述:Step1:判別隊列是否為空;若空,則顯示隊列‘下溢’;Step2:非空,則判別隊列長度是否為1;

Step2.1:不為1,修改頭指針;

Step2.2:為1,則修改頭、尾指針;Step3:釋放T。

template<classT>//出隊Tlinked_Queue<T>::del_linked_Queue(){Ty;node<T>*q;if(front==NULL){cout<<“隊列已空\n”);return(0);}y=front->data;q=front;front=q->next;deleteq;if(front==NULL)rear=NULL;return(y);}課堂練習P65例子2.14建立空隊列,插入1-100;作40次退隊操作;打印輸出;2.3.2線性鏈表基本運算1.單鏈表的查找find2.單鏈表的的插入insert3.單鏈表的刪除delete

指針的基本操作設指針變量p、q的定義為:NODE*p,*q;對鏈表的操作實際上是對指針的操作。例如,要刪除結點ai,首先要使指針p指向ai,即:a1......headaian^p指針p是存儲單元的地址,地址內的內容可以通過p->data得到,指向下個元素的指針用p->next得到

指針的基本操作列表p=(NODE*)malloc(sizeof(NODE))申請一個結點空間,并將地址送入p中。free(p)釋放p指針所指結點的空間p=q指針p指向指針q所指的結點p=q->next指針p指向指針q所指結點的后件p=p->next指針p向后移動一個結點p->next=q將指針q所指結點改接為指針p所指結點 的后件p->next=NULL將指針p所指結點與后件結點斷開

線性鏈表的查找算法要求:在頭指針為HEAD的非空線性鏈表中尋找包含元素x的前一個結點p

算法操作步驟:step1初始化,指針p指向頭指針step2p非空且p指向的下一個元素不是x,循環(huán)step3每循環(huán)一次,p后移一個位置step4循環(huán)結束,返回指針p.template<classT>ListNode<T>*List<T>::Find(Tx){p=head;

//當前指針

p

指示第一個結點while(p->next!=NULL&&(p->next)->data!=x)p=p->next;returnp;}返回的指針p要么是指向x的前一個結點,要么指向最后一個結點

線性鏈表插入算法要求:在頭指針為HEAD的線性鏈表中包含元素x的結點之前插入新元素b

算法操作步驟:step1找到x的位置,使指針p指向x的前一個結點;step2申請并生成新結點sstep3使s插入到x所在結點之前

考慮幾種特殊情況:空鏈表,首元素為x

template<classT>voidlinked_llist<T>::del_linked_llist(Tx,Tb){node<T>*p,*q;p=newnode<T>;p->data=b;if(head==NULL){head=p;p->next=NULL;return;}if(head->dada==x){p->next=head;head=p;return;}q=head;while((q->next!=NULL)&&((q->next)->dada)!=x))q=q->next;p->next=q->next;q->next=p;return;}對于空表和第一個結點處理必須單獨考慮(后面引入頭結點概念)

線性鏈表刪除算法要求:在頭指針為HEAD的線性鏈表中刪除包含元素x的結點。算法操作步驟:step1找到x的前件,使指針q指向x的前件;step2使指針p指向x所在結點;step3使p所指結點x脫鏈step4釋放ptemplate<classT>intlinked_llist<T>::ins_linked_llist(Tx){node<T>*p,*q;if(head==NULL)return0;if(head->dada==x){p=head->next;deletehead;head=p;return1}q=head;while((q->next!=NULL)&&((q->next)->d!=x))q=q->next;if(q->next==NULL)return0;p=q->next;q->next=p->next;deletep;return1;}課堂練習參考P70例2.15(1)建立空線性鏈表(2)插入1-30;(3)輸出鏈表;(4)將單數的節(jié)點刪除;(5)再次輸出鏈表;2.3.3循環(huán)鏈表和雙向鏈表引入頭節(jié)點頭結點:為方便操作,在頭指針和第1個結點之 間設置的結點。首元結點

第一個結點(a1)。head頭指針a1首元結點

ai...第i個結點頭結點空表和非空表表示形式在頭結點上得到統一(任何情況下至少存在一個結點)空表的形式

:head->next=NULL

head^頭結點head頭結點非空表的形式:head->Next=Address引入頭節(jié)點無頭結點時,空表和非空表的運算不統一;鏈表檢索只能從頭指針開始,且只能順鏈表方向移動。在單鏈表中,從表的任一結點ai找其前件結點,時間復雜度是O(n)。如果讓鏈表首尾相接,構成環(huán)形,這就是單循環(huán)鏈表。如果在結點中增加一個指向前一個結點的指針域,鏈表可以從兩個方向檢索,效果更佳;這就是雙向循環(huán)鏈表。循環(huán)單鏈表(1)單循環(huán)鏈表表示形式:headhead...a1a2an單循環(huán)鏈表為空的條件:head->next=head表示形式為:(2)單循環(huán)鏈表特點:從表中任一結點出發(fā),均可以找到表中其它結點。找其前件結點的時間復雜度是O(n)。雙向循環(huán)鏈表在單向循環(huán)鏈表中,也存在檢索前件結點費時的問題(所需時間是O(n))。雙向循環(huán)鏈表,其存儲結構:template<classT>structnode{Td; node*next,*prior;

};其它定義與單向鏈表相同。(1)雙向循環(huán)鏈表結點結構指向后件結點指針域數據域指向前件結點指針域

priordatanext(2)雙向循環(huán)鏈表表示形式雙向循環(huán)鏈表表示形式:head^^head......ana2a1雙向循環(huán)鏈表為空的條件:

head->prior=head->next=head表示形式為:總結:

雙向循環(huán)鏈表特點

適合于兩個方向的移動。找其前件結點的時間復雜度是O(1)。循環(huán)鏈表的運算特點空表與非空表統一判斷鏈表結束的條件改變了P->next=nullP->next=head雙向鏈表的運算要修改兩個指針循環(huán)鏈表的插入template<classT>voidlinked_llist<T>::ins_linked_llist(Tx){node<T>*p,*q;p=newnode<T>;p->dada=b;

q=head;while((q->next!=head)&&((q->next)->dada)!=x))q=q->next;p->next=q->next;q->next=p;return;}循環(huán)鏈表的刪除template<classT>intlinked_llist<T>::ins_linked_llist(Tx){node<T>*p,*q;q=head;while((q->next!=head)&&((q->next)->dada!=x))q=q->next;if(q->next==head)return0;p=q->next;q->next=p->next;deletep;return1;}鏈表存儲結構的特點插入、刪除操作極為方便數據非連續(xù)存放、順序存取邏輯上相鄰,物理上不一定相鄰存儲結構較復雜、需要額外的存儲空間結論:鏈表存儲結構適合于表中元素頻繁變動的線性表。課堂練習參考P74例2.16(1)建立單向空循環(huán)鏈表;(2)插入1-100;(3)刪除單數結點;作業(yè)P152:2.32.71.思考題:1)假設一單循環(huán)鏈表的長度大于1,且表中即無頭結點也無頭指針。已知S為指向鏈表中某結點的指針。試寫出刪除表中結點S的算法。2)假設以數組sequ[m-1]存放循環(huán)隊列的元素,設變量rear和quelen分別為指示隊尾元素位置和隊中元素個數,試寫出入隊和出隊算法。作業(yè)2.4數組

2.4.1

數組的順序存儲結構

2.4.2

規(guī)則矩陣的壓縮

2.4.3

一般稀疏矩陣的表示

2.4.1數組的順序存儲數組是相同類型數據元素的有限集合;數組中的各個分量稱為數組元素;每個數組元素值可以用數組名和一個下標值唯一地確定;數組是有限個數組元素的集合。數組中所有元素有相同的特性。每個數組元素由數組名和下標組成。每個具有下標值的數組元素有一個與該下標值對應的數組元素值。

二維數組三維數組行向量下標i頁向量下標i列向量下標j行向量下標j

列向量下標k數組元素之間的關系

二維數組m行n列可以看作是m個或n個一維數組:Am×n=((a11a12…a1n),(a21a22…a2n),..(am1am2…amn))數組的操作數組有兩種基本的操作:給定下標,讀取相應的數組元素;給定下標,修改相應數組元素的值。數組的順序存儲結構數組元素是連續(xù)存放的,因此采用順序存儲結構。無論幾維數組,在計算機中都是按一維數組來存放。數組存放通常采用兩種方式:按行優(yōu)先順序(Pascal,C)按列優(yōu)先順序(Fortran)1).按行優(yōu)先順序存儲結構

例如:二維數組Am×n,可以看作m個行向量,每個行向量n個元素。數組中的每個元素由元素的兩個下標表達式唯一確定。地址計算公式:

LOC(aij)=LOC(a11)+((i-1)×n+(j-1))×L

其中,L是每個元素所占的存儲單元。二維數組按行優(yōu)先存儲舉例有二維數組如下:LOC(a23)=LOC(a11)+(2-1)×4+(3-1)=7LOC(a34)=1+(3-1)×4+(4-1)=12LOC(a14)=1+(1-1)×4+(4-1)=42).按列優(yōu)先順序存儲結構

按列優(yōu)先順序存放是將數組看作若干個列向量。例如,二維數組Amxn,可以看作n個列向量,每個列向量m個元素。數組中的每個元素由元素的兩個下標表達式唯一確定。

地址計算公式:

LOC(aij)=LOC(a11)+((j-1)*m+(i-1))*L

其中,L是每個元素所占的存儲單元。二維數組按列優(yōu)先存儲舉例LOC(a23)=LOC(a11)+(3-1)*4+(2-1)=10LOC(a34)=1+(4-1)*4+(3-1)=15LOC(a14)=1+(4-1)*4+(1-1)=13

有二維數組如下:2.4.2規(guī)則矩陣的壓縮

實際工程問題中推導出的數組常常是高階、含大量零元素的矩陣,或者是一些有規(guī)律排列的元素。為了節(jié)省存儲空間,通常是對這類矩陣進行壓縮存儲。

壓縮的含義是:相同值的多個元素占用一個存儲單元;零元素不分配存儲單元。能夠采用壓縮存儲的矩陣對稱矩陣:存儲主對角線以上(下)的元素;上(下)三角矩陣:只存儲三角陣元素;帶狀矩陣:只存儲帶狀元素;稀疏矩陣:只存儲非零元素;1下三角矩陣的壓縮存儲

開辟一個長度為n(n+1)/2的一維數組B,然后一行接一行地依次存放A中下三角部分的元素。以行為主壓縮存儲以列為主壓縮存儲

2對稱矩陣的壓縮存儲

對稱矩陣的元素滿足:aij=aji1≤i,j≤n

因此將n*n個元素壓縮存放到

n(n+1)/2個單元的一維數組S((n+1)*n/2)中。

(按行存放)aij的地址為:對稱矩陣的壓縮存儲舉例存于一維數組S[6]S[6]=(a11,a21,a22,a31,a32,a33)123456LOC(a31)=3(3-1)/2+1=4LOC(a22)=2(2-1)/2+2=3LOC(a21)=2(2-1)/2+1=2設有A3x3矩陣:3三對角矩陣的壓縮存儲

在三對角矩陣中,三條對角線以外的元素均為零,并且,除了第一行與最后一行外,其他每一行均只有三個元素為非零,因此,n階三對角矩陣共有3n-2個非零元素。對角矩陣的壓縮存儲以行為主存放:以列為主存放:2.4.3一般稀疏矩陣的表示如果一個矩陣中絕大多數的元素值為零,只有很少的元素值非零,則稱該矩陣為稀疏矩陣。1三列二維數組表示(1)非零元素所在的行號i;(2)非零元素所在的列號j;(3)非零元素的值V。即每一個非零元素可以

溫馨提示

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

評論

0/150

提交評論