線性鏈表2.4 數(shù)組

2.3線性鏈表及其運(yùn)算線性表的順序存儲(chǔ)結(jié)構(gòu)容易實(shí)現(xiàn)，可以隨機(jī)存取表中的任意元素。順序表缺點(diǎn)是：難于插入、刪除操作；需要預(yù)先分配空間，不管這些空間能否最大限度地利用。鏈表存儲(chǔ)結(jié)構(gòu)在這兩個(gè)方面恰好是優(yōu)點(diǎn)：容易插入、刪除操作不需要預(yù)分空間。鏈表基本概念定義：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表

結(jié)點(diǎn)（NODE）：表中元素的存儲(chǔ)單元。由數(shù)據(jù)域和指針域組成。數(shù)據(jù)域存放元素?cái)?shù)據(jù)，指針域存放指向下一結(jié)點(diǎn)位置的指針。結(jié)點(diǎn)形式為：

datanext數(shù)據(jù)域指針域鏈表（Link）：由結(jié)點(diǎn)組成的表。頭指針（head）：指向鏈表中第1個(gè)結(jié)點(diǎn)的指針。舉例由食品組成的單鏈表（biscuit,butter,cheese,eggs,grapes,jam)

grapesbiscuitbuttercheesejameggs^head

頭指針最后一個(gè)結(jié)點(diǎn)指針域?yàn)榭諉捂湵淼奈锢泶鎯?chǔ)

存儲(chǔ)地址數(shù)據(jù)域（data）指針域（next）grapes60biscuit61cheese13eggs1jamNULLbutter121111213606111頭指針

head（biscuit,butter,cheese,eggs,grapes,jam)線性鏈表類(lèi)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();//從頭指針開(kāi)始輸出

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

Tdel_linked_list();//刪除鏈頭}參考P58課堂練習(xí)P58例子2.12定義一個(gè)空鏈表，依次插入1-100打印輸出；然后刪除前50個(gè)結(jié)點(diǎn)，并再次輸出。

帶鏈的棧棧也是線性表，可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序棧最多可用于2個(gè)棧的共享，對(duì)于更多的棧就難于表達(dá)了。對(duì)于最大空間需要量事先不知的情況，就不能使用順序棧了。這時(shí)，就需要采用鏈棧。鏈棧：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈棧示意圖a1a2a3^棧底top棧頂…...aiTemplate<classT>structnode{Tdata;node*next;};template<classT>classlinked_Stack{private:node<T>*top;

//棧頂指針

棧的鏈?zhǔn)奖硎尽湕ublic: linked_stack(); voidprt_linked_stack();intflag_linked_stack();voidins_linked_stack(T);Tdel_linked_stack(); Tread_linked_stack();}

鏈棧為空的條件：

top=NULL

鏈棧為滿的條件(無(wú)法繼續(xù)申請(qǐng)新結(jié)點(diǎn)):t=NULLt為申請(qǐng)的結(jié)點(diǎn),為NULL表示失敗。

鏈棧進(jìn)棧操作操作步驟:step1：申請(qǐng)一個(gè)鏈棧結(jié)點(diǎn)，若t=NULL，則表示鏈滿；否則，執(zhí)行step2；step2：在top所指結(jié)點(diǎn)之前插入新結(jié)點(diǎn)，并將top指向新申請(qǐng)的結(jié)點(diǎn)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;}鏈棧進(jìn)棧算法鏈棧出棧操作操作步驟:step1若鏈棧為空，則輸出棧溢出信息；否則，執(zhí)行step2。step2(保存top)并使top指向被刪除結(jié)點(diǎn)的后件結(jié)點(diǎn)，刪除top所指結(jié)點(diǎn)。step3釋放被刪除結(jié)點(diǎn)的存儲(chǔ)空間。返回出棧元素值。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);}課堂練習(xí)P62,參考2.13;建立空棧，入棧10,20,30,40,50；退棧2次，然后輸出棧中所有的元素；4帶鏈的隊(duì)列1).隊(duì)列也是線性表，可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。datanext數(shù)據(jù)域指針域2).存儲(chǔ)結(jié)構(gòu)的C++語(yǔ)言描述，template<classT>//模板聲明，數(shù)據(jù)元素虛擬類(lèi)型為T(mén)classlinked_Queue//循環(huán)隊(duì)列類(lèi){private://數(shù)據(jù)成員

intmm;//存儲(chǔ)空間容量

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

node<T>*rear;//隊(duì)尾指針public://成員函數(shù)

linked_Queue(int);//構(gòu)造函數(shù)，建立空循環(huán)隊(duì)列

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

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

voidins_linked_Queue(T);//入隊(duì)

Tdel_linked_Queue();};//退隊(duì)鏈隊(duì)列為空的表示鏈隊(duì)列為空，

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

front

rearfront

rear

^...ana2a1鏈隊(duì)滿的條件為:T=NULL。T為新創(chuàng)建的結(jié)點(diǎn),非空隊(duì)列:NULL鏈隊(duì)列的入隊(duì)操作要求：在鏈隊(duì)列中插入一個(gè)元素x（入隊(duì)運(yùn)算）。

算法操作步驟:

Step1：申請(qǐng)建立一個(gè)新結(jié)點(diǎn)p；Step2：判別p是否為空；若空，表示隊(duì)列已滿；Step3：非空，將p插入鏈中，修改rear指針。template<classT>//入隊(duì)T linked_Queue<T>::ins_linked_Queue(Tx){

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

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

鏈隊(duì)列的出隊(duì)操作出隊(duì)操作要考慮兩種情況:當(dāng)隊(duì)列長(zhǎng)度為1時(shí)，除了修改隊(duì)頭指針外，還要修改隊(duì)尾指針。QueueQueuefrontrearrearfronta1

an

^a1a2

...a2

^...an

^

當(dāng)隊(duì)列長(zhǎng)度大于1時(shí),只修改隊(duì)頭指針即可Queuean^rearQueuefrontrearTfrontNULL鏈隊(duì)列的出隊(duì)操作要求：在鏈隊(duì)列中刪除一個(gè)元素（退隊(duì)運(yùn)算）。算法描述:Step1：判別隊(duì)列是否為空；若空，則顯示隊(duì)列‘下溢’；Step2：非空，則判別隊(duì)列長(zhǎng)度是否為1；

Step2.1：不為1，修改頭指針；

Step2.2：為1，則修改頭、尾指針；Step3：釋放T。

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

指針的基本操作設(shè)指針變量p、q的定義為：NODE*p，*q；對(duì)鏈表的操作實(shí)際上是對(duì)指針的操作。例如，要?jiǎng)h除結(jié)點(diǎn)ai，首先要使指針p指向ai，即：a1......headaian^p指針p是存儲(chǔ)單元的地址，地址內(nèi)的內(nèi)容可以通過(guò)p->data得到，指向下個(gè)元素的指針用p->next得到

指針的基本操作列表p=（NODE*）malloc（sizeof（NODE））申請(qǐng)一個(gè)結(jié)點(diǎn)空間，并將地址送入p中。free（p）釋放p指針?biāo)附Y(jié)點(diǎn)的空間p=q指針p指向指針q所指的結(jié)點(diǎn)p=q->next指針p指向指針q所指結(jié)點(diǎn)的后件p=p->next指針p向后移動(dòng)一個(gè)結(jié)點(diǎn)p->next=q將指針q所指結(jié)點(diǎn)改接為指針p所指結(jié)點(diǎn) 的后件p->next=NULL將指針p所指結(jié)點(diǎn)與后件結(jié)點(diǎn)斷開(kāi)

線性鏈表的查找算法要求：在頭指針為HEAD的非空線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)p

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

//當(dāng)前指針

p

指示第一個(gè)結(jié)點(diǎn)while(p->next!=NULL&&(p->next)->data!=x)p=p->next;returnp;}返回的指針p要么是指向x的前一個(gè)結(jié)點(diǎn)，要么指向最后一個(gè)結(jié)點(diǎn)

線性鏈表插入算法要求：在頭指針為HEAD的線性鏈表中包含元素x的結(jié)點(diǎn)之前插入新元素b

算法操作步驟:step1找到x的位置,使指針p指向x的前一個(gè)結(jié)點(diǎn)；step2申請(qǐng)并生成新結(jié)點(diǎn)sstep3使s插入到x所在結(jié)點(diǎn)之前

考慮幾種特殊情況：空鏈表，首元素為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;}對(duì)于空表和第一個(gè)結(jié)點(diǎn)處理必須單獨(dú)考慮（后面引入頭結(jié)點(diǎn)概念）

線性鏈表刪除算法要求：在頭指針為HEAD的線性鏈表中刪除包含元素x的結(jié)點(diǎn)。算法操作步驟:step1找到x的前件,使指針q指向x的前件；step2使指針p指向x所在結(jié)點(diǎn)；step3使p所指結(jié)點(diǎn)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;}課堂練習(xí)參考P70例2.15(1)建立空線性鏈表(2)插入1-30；(3)輸出鏈表；(4)將單數(shù)的節(jié)點(diǎn)刪除；(5)再次輸出鏈表；2.3.3循環(huán)鏈表和雙向鏈表引入頭節(jié)點(diǎn)頭結(jié)點(diǎn)：為方便操作，在頭指針和第1個(gè)結(jié)點(diǎn)之 間設(shè)置的結(jié)點(diǎn)。首元結(jié)點(diǎn)

第一個(gè)結(jié)點(diǎn)（a1）。head頭指針a1首元結(jié)點(diǎn)

ai...第i個(gè)結(jié)點(diǎn)頭結(jié)點(diǎn)空表和非空表表示形式在頭結(jié)點(diǎn)上得到統(tǒng)一（任何情況下至少存在一個(gè)結(jié)點(diǎn)）空表的形式

:head->next=NULL

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

}；其它定義與單向鏈表相同。（1）雙向循環(huán)鏈表結(jié)點(diǎn)結(jié)構(gòu)指向后件結(jié)點(diǎn)指針域數(shù)據(jù)域指向前件結(jié)點(diǎn)指針域

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

head->prior=head->next=head表示形式為:總結(jié):

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

適合于兩個(gè)方向的移動(dòng)。找其前件結(jié)點(diǎn)的時(shí)間復(fù)雜度是O(1)。循環(huán)鏈表的運(yùn)算特點(diǎn)空表與非空表統(tǒng)一判斷鏈表結(jié)束的條件改變了P->next=nullP->next=head雙向鏈表的運(yùn)算要修改兩個(gè)指針循環(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;}鏈表存儲(chǔ)結(jié)構(gòu)的特點(diǎn)插入、刪除操作極為方便數(shù)據(jù)非連續(xù)存放、順序存取邏輯上相鄰，物理上不一定相鄰存儲(chǔ)結(jié)構(gòu)較復(fù)雜、需要額外的存儲(chǔ)空間結(jié)論：鏈表存儲(chǔ)結(jié)構(gòu)適合于表中元素頻繁變動(dòng)的線性表。課堂練習(xí)參考P74例2.16(1)建立單向空循環(huán)鏈表;(2)插入1-100；(3)刪除單數(shù)結(jié)點(diǎn)；作業(yè)P152:2.32.71.思考題：1）假設(shè)一單循環(huán)鏈表的長(zhǎng)度大于1，且表中即無(wú)頭結(jié)點(diǎn)也無(wú)頭指針。已知S為指向鏈表中某結(jié)點(diǎn)的指針。試寫(xiě)出刪除表中結(jié)點(diǎn)S的算法。2）假設(shè)以數(shù)組sequ[m-1]存放循環(huán)隊(duì)列的元素，設(shè)變量rear和quelen分別為指示隊(duì)尾元素位置和隊(duì)中元素個(gè)數(shù)，試寫(xiě)出入隊(duì)和出隊(duì)算法。作業(yè)2.4數(shù)組

2.4.1

數(shù)組的順序存儲(chǔ)結(jié)構(gòu)

2.4.2

規(guī)則矩陣的壓縮

2.4.3

一般稀疏矩陣的表示

2.4.1數(shù)組的順序存儲(chǔ)數(shù)組是相同類(lèi)型數(shù)據(jù)元素的有限集合；數(shù)組中的各個(gè)分量稱為數(shù)組元素；每個(gè)數(shù)組元素值可以用數(shù)組名和一個(gè)下標(biāo)值唯一地確定；數(shù)組是有限個(gè)數(shù)組元素的集合。數(shù)組中所有元素有相同的特性。每個(gè)數(shù)組元素由數(shù)組名和下標(biāo)組成。每個(gè)具有下標(biāo)值的數(shù)組元素有一個(gè)與該下標(biāo)值對(duì)應(yīng)的數(shù)組元素值。

二維數(shù)組三維數(shù)組行向量下標(biāo)i頁(yè)向量下標(biāo)i列向量下標(biāo)j行向量下標(biāo)j

列向量下標(biāo)k數(shù)組元素之間的關(guān)系

二維數(shù)組m行n列可以看作是m個(gè)或n個(gè)一維數(shù)組:Am×n=((a11a12…a1n),(a21a22…a2n),..(am1am2…amn))數(shù)組的操作數(shù)組有兩種基本的操作：給定下標(biāo)，讀取相應(yīng)的數(shù)組元素；給定下標(biāo)，修改相應(yīng)數(shù)組元素的值。數(shù)組的順序存儲(chǔ)結(jié)構(gòu)數(shù)組元素是連續(xù)存放的，因此采用順序存儲(chǔ)結(jié)構(gòu)。無(wú)論幾維數(shù)組，在計(jì)算機(jī)中都是按一維數(shù)組來(lái)存放。數(shù)組存放通常采用兩種方式：按行優(yōu)先順序(Pascal，C)按列優(yōu)先順序(Fortran)1).按行優(yōu)先順序存儲(chǔ)結(jié)構(gòu)

例如：二維數(shù)組Am×n，可以看作m個(gè)行向量，每個(gè)行向量n個(gè)元素。數(shù)組中的每個(gè)元素由元素的兩個(gè)下標(biāo)表達(dá)式唯一確定。地址計(jì)算公式：

LOC（aij）=LOC（a11）+（（i-1）×n+（j-1））×L

其中，L是每個(gè)元素所占的存儲(chǔ)單元。二維數(shù)組按行優(yōu)先存儲(chǔ)舉例有二維數(shù)組如下：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)先順序存儲(chǔ)結(jié)構(gòu)

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

地址計(jì)算公式：

LOC（aij）=LOC（a11）+（（j-1）*m+（i-1））*L

其中，L是每個(gè)元素所占的存儲(chǔ)單元。二維數(shù)組按列優(yōu)先存儲(chǔ)舉例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

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

實(shí)際工程問(wèn)題中推導(dǎo)出的數(shù)組常常是高階、含大量零元素的矩陣，或者是一些有規(guī)律排列的元素。為了節(jié)省存儲(chǔ)空間，通常是對(duì)這類(lèi)矩陣進(jìn)行壓縮存儲(chǔ)。

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

開(kāi)辟一個(gè)長(zhǎng)度為n（n+1）/2的一維數(shù)組B，然后一行接一行地依次存放A中下三角部分的元素。以行為主壓縮存儲(chǔ)以列為主壓縮存儲(chǔ)

2對(duì)稱矩陣的壓縮存儲(chǔ)

對(duì)稱矩陣的元素滿足：aij=aji1≤i，j≤n

因此將n*n個(gè)元素壓縮存放到

n（n+1）/2個(gè)單元的一維數(shù)組S（（n+1）*n/2）中。

（按行存放）aij的地址為：對(duì)稱矩陣的壓縮存儲(chǔ)舉例存于一維數(shù)組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設(shè)有A3x3矩陣:3三對(duì)角矩陣的壓縮存儲(chǔ)

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