線性鏈表2.4 數組

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。即每一個非零元素可以