線性鏈表數(shù)組PPT精品文檔

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

2、元。由數(shù)據(jù)域和指針域：表中元素的存儲單元。由數(shù)據(jù)域和指針域組成。數(shù)據(jù)域存放元素?cái)?shù)據(jù)，指針域存放指向下一結(jié)點(diǎn)位組成。數(shù)據(jù)域存放元素?cái)?shù)據(jù)，指針域存放指向下一結(jié)點(diǎn)位置的指針。置的指針。結(jié)點(diǎn)形式為：結(jié)點(diǎn)形式為：鏈表（鏈表（Link）：）：由結(jié)點(diǎn)組成的表。由結(jié)點(diǎn)組成的表。頭指針（頭指針（head）：）：指向鏈表中第指向鏈表中第1個結(jié)點(diǎn)的指針。個結(jié)點(diǎn)的指針。 data next數(shù)據(jù)域 指針域3單鏈表的物理存儲 存儲地址存儲地址 數(shù)據(jù)域（數(shù)據(jù)域（data） 指針域（指針域（next）grapes 60biscuit 61cheese 13eggs 1jam NULLbutter 12111121360611

3、1頭指針頭指針 headheadl（biscuit,butter,cheese,eggs,grapes,jam)4線性鏈表類 P57Template struct node T data ; node *next ; ;Template class linked_list private : 5 node *head;public : linked_list(); /建立空鏈表建立空鏈表 int flag_linked_list(); /判斷鏈表狀態(tài)判斷鏈表狀態(tài) if(head = NULL )return 0; return 1; void prt_linked_list(); /從頭指針開

4、始輸出從頭指針開始輸出 void ins_linked_list(T );/插入到鏈表頭插入到鏈表頭 T del_linked_list(); /刪除鏈頭刪除鏈頭參考參考P586課堂練習(xí)nP58 例子例子 2.12n定義一個空鏈表，依次插入定義一個空鏈表，依次插入1-100打印輸出；然后刪除前打印輸出；然后刪除前50個結(jié)點(diǎn)，并再次個結(jié)點(diǎn)，并再次輸出。輸出。7 帶鏈的棧n棧也是線性表，可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)棧也是線性表，可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)n順序棧最多可用于順序棧最多可用于2個棧的共享，對于更多個棧的共享，對于更多的棧就難于表達(dá)了。的棧就難于表達(dá)了。n對于最大空間需要量事先不知的情況，就不對于最大

5、空間需要量事先不知的情況，就不能使用順序棧了。這時，就需要采用鏈棧。能使用順序棧了。這時，就需要采用鏈棧。鏈棧：棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈棧：棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)8鏈棧示意圖a1a2a3棧底棧底top棧頂棧頂.ai9Template struct node T data ; node *next ; ;template class linked_Stack private: node *top; /棧頂指針棧頂指針 棧的鏈?zhǔn)奖硎?鏈棧10public:linked_stack();void prt_linked_stack ( ) ; int flag_linked_stack (); void ins_

6、linked_stack (T); T del_linked_stack();T read_linked_stack(); 11n 鏈棧為空的條件：鏈棧為空的條件：n top = NULLn 鏈棧為滿的條件鏈棧為滿的條件(無法繼續(xù)申請新結(jié)點(diǎn)無法繼續(xù)申請新結(jié)點(diǎn)):n t = NULL nt 為申請的結(jié)點(diǎn)為申請的結(jié)點(diǎn),為為NULL表示失敗。表示失敗。 12鏈棧進(jìn)棧操作操作步驟操作步驟:nstep1 ：申請一個鏈棧結(jié)點(diǎn)，若：申請一個鏈棧結(jié)點(diǎn)，若t=NULL，則表示鏈滿；否則，執(zhí)行則表示鏈滿；否則，執(zhí)行step2 ；nstep2 ：在：在top所指結(jié)點(diǎn)之前插入新結(jié)點(diǎn)，所指結(jié)點(diǎn)之前插入新結(jié)點(diǎn)，并將并將t

7、op指向新申請的結(jié)點(diǎn)指向新申請的結(jié)點(diǎn)t。13template void linked_Stack: ins_linked_stack (T x) node *p = new node ; if(p=NULL) return; p - data = x; p - next = top; top= p; 鏈棧進(jìn)棧算法14鏈棧出棧操作操作步驟操作步驟:nstep1 若鏈棧為空，則輸出棧溢出信息；否若鏈棧為空，則輸出棧溢出信息；否則，執(zhí)行則，執(zhí)行step 2。nstep2 (保存保存top為為q)并使并使top 指向被刪除結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的后件結(jié)點(diǎn)，刪除的后件結(jié)點(diǎn)，刪除q所指結(jié)點(diǎn)。所指結(jié)點(diǎn)。nste

8、p 3 釋放被刪除結(jié)點(diǎn)的存儲空間。返回出釋放被刪除結(jié)點(diǎn)的存儲空間。返回出棧元素值。棧元素值。15template T linked_Stack: del_linked_stack() T y ; node *q; if( top = = NULL ) cout“空?？諚！?next; / top = top- next; y = q-data; delete q; return (y); 16課堂練習(xí)nP62, 參考參考2.13;n建立空棧，入棧建立空棧，入棧 10,20,30,40,50；n退棧退棧2次，然后輸出棧中所有的元素；次，然后輸出棧中所有的元素；174 帶鏈的隊(duì)列1). 隊(duì)列也是線

9、性表，可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。隊(duì)列也是線性表，可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。data next數(shù)據(jù)域數(shù)據(jù)域 指針域指針域2). 存儲結(jié)構(gòu)的存儲結(jié)構(gòu)的C+ 語言描述，語言描述，18template /模板聲明，數(shù)據(jù)元素虛擬類型為模板聲明，數(shù)據(jù)元素虛擬類型為T class linked_Queue /循環(huán)隊(duì)列類循環(huán)隊(duì)列類 private: /數(shù)據(jù)成員數(shù)據(jù)成員 int mm; /存儲空間容量存儲空間容量 node* front; /排頭指針排頭指針 node * rear; /隊(duì)尾指針隊(duì)尾指針public: /成員函數(shù)成員函數(shù)linked_Queue(int); /構(gòu)造函數(shù)，建立空循環(huán)隊(duì)列構(gòu)造函數(shù)，建立空循環(huán)

10、隊(duì)列 void prt_linked_Queue(); /輸出排頭與隊(duì)尾指針以輸出排頭與隊(duì)尾指針以及隊(duì)中元素及隊(duì)中元素int flag_linked_Queue(); /檢測循環(huán)隊(duì)列的狀態(tài)檢測循環(huán)隊(duì)列的狀態(tài)void ins_linked_Queue(T); /入隊(duì)入隊(duì)T del_linked_Queue(); ; /退隊(duì)退隊(duì)19鏈隊(duì)列為空的表示鏈隊(duì)列為空鏈隊(duì)列為空， Queue.front = Queue.rear 表示形式：表示形式： front rearfront rear . ana2a1鏈隊(duì)滿的條件為鏈隊(duì)滿的條件為: :T = NULLT = NULL。T T 為新創(chuàng)建的結(jié)點(diǎn)為新創(chuàng)建的

11、結(jié)點(diǎn), ,非空隊(duì)列非空隊(duì)列:NULL20鏈隊(duì)列的入隊(duì)操作要求：在鏈隊(duì)列中插入一個元素要求：在鏈隊(duì)列中插入一個元素x x（入隊(duì)運(yùn)算）。（入隊(duì)運(yùn)算）。 算法操作步驟算法操作步驟: : Step1：申請建立一個新結(jié)點(diǎn)：申請建立一個新結(jié)點(diǎn)p；Step2：判別：判別p是否為空；若空，表示是否為空；若空，表示 隊(duì)列已滿；隊(duì)列已滿；Step3：非空，將：非空，將p插入鏈中，修改插入鏈中，修改rear指針。指針。21template /入隊(duì)入隊(duì)T linked_Queue:ins_linked_Queue(T x) node *p; p = new node ; if (p=NULL) coutdada =x

12、; p-next = NULL; if （ rear = = NULL）/隊(duì)列為空的情況隊(duì)列為空的情況 front =p; else rear - next =p; rear = p; return ; 22 鏈隊(duì)列的出隊(duì)操作出隊(duì)操作要考慮兩種情況出隊(duì)操作要考慮兩種情況:q當(dāng)隊(duì)列長度為當(dāng)隊(duì)列長度為1時，除了修改隊(duì)頭指針外，還要修時，除了修改隊(duì)頭指針外，還要修改隊(duì)尾指針。改隊(duì)尾指針。QueueQueueQueueQueuefrontrearrearfronta1 an a1a2 .a2 .an q 當(dāng)隊(duì)列長度大于當(dāng)隊(duì)列長度大于1時時,只修改隊(duì)頭指針即可只修改隊(duì)頭指針即可QueueQueuean

13、rearQueueQueuefrontrearTfrontNULL23鏈隊(duì)列的出隊(duì)操作要求：在鏈隊(duì)列中刪除一個元素（退隊(duì)運(yùn)要求：在鏈隊(duì)列中刪除一個元素（退隊(duì)運(yùn)算）。算）。算法描述算法描述:Step1：判別隊(duì)列是否為空；若空，則顯示隊(duì)：判別隊(duì)列是否為空；若空，則顯示隊(duì)列列下溢下溢；Step2 ：非空，則判別隊(duì)列長度是否為：非空，則判別隊(duì)列長度是否為1； Step2.1：不為：不為1，修改頭指針；，修改頭指針； Step2.2：為：為1，則修改頭、尾指針；，則修改頭、尾指針；Step3：釋放：釋放T。24 template /出隊(duì)出隊(duì)T linked_Queue:del_linked_Queue(

14、) T y; node *q; if ( front = = NULL) coutdata; q=front; front = q-next; delete q; if (front = = NULL ) rear = NULL ; return(y);25課堂練習(xí)nP65 例子例子 2.14 n建立空隊(duì)列，插入建立空隊(duì)列，插入1-100；n作作40次退隊(duì)操作；次退隊(duì)操作；n打印輸出；打印輸出；262.3.2 線性鏈表基本運(yùn)算 1. 單鏈表的查找單鏈表的查找 find2. 單鏈表的的插入單鏈表的的插入insert3. 單鏈表的刪除單鏈表的刪除delete27 指針的基本操作n設(shè)指針變量設(shè)指針變

15、量p、q的定義為：的定義為： NODE *p，*q；n對鏈表的操作實(shí)際上是對指針的操作。例如，對鏈表的操作實(shí)際上是對指針的操作。例如，要刪除結(jié)點(diǎn)要刪除結(jié)點(diǎn)ai，首先要使指針，首先要使指針p指向指向ai，即：，即：a1.headaianp指針指針p是存儲單元的地址，地址內(nèi)的內(nèi)容可以通過是存儲單元的地址，地址內(nèi)的內(nèi)容可以通過p-data得到，指向下個元素的指針用得到，指向下個元素的指針用p-next 得到得到28 指針的基本操作列表np=（NODE*）malloc（sizeof（NODE） 申請一個結(jié)點(diǎn)空間，并將地址送入申請一個結(jié)點(diǎn)空間，并將地址送入p中。中。nfree（p） 釋放釋放p指針?biāo)附Y(jié)

16、點(diǎn)的空間指針?biāo)附Y(jié)點(diǎn)的空間np=q 指針指針p指向指針指向指針q所指的結(jié)點(diǎn)所指的結(jié)點(diǎn)np=q-next 指針指針p指向指針指向指針q所指結(jié)點(diǎn)的后件所指結(jié)點(diǎn)的后件np=p-next 指針指針p向后移動一個結(jié)點(diǎn)向后移動一個結(jié)點(diǎn) np-next=q 將指針將指針q所指結(jié)點(diǎn)改接為指針?biāo)附Y(jié)點(diǎn)改接為指針p所指結(jié)點(diǎn)所指結(jié)點(diǎn) 的后件的后件np-next=NULL 將指針將指針p所指結(jié)點(diǎn)與后件結(jié)點(diǎn)斷開所指結(jié)點(diǎn)與后件結(jié)點(diǎn)斷開29 線性鏈表的查找算法要求：在頭指針為要求：在頭指針為HEADHEAD的非空線性鏈的非空線性鏈表中尋找包含元素表中尋找包含元素x x的前一個結(jié)點(diǎn)的前一個結(jié)點(diǎn)p p 算法操作步驟算法操作步驟

17、:nstep1 初始化初始化,指針指針p指向頭指針指向頭指針nstep2 p非空且非空且p指向的下一個元素指向的下一個元素不是不是x, 循環(huán)循環(huán)nstep3 每循環(huán)一次每循環(huán)一次,p后移一個位置后移一個位置nstep4 循環(huán)結(jié)束循環(huán)結(jié)束,返回指針返回指針p.30template ListNode * List :Find ( T x ) p = head; /當(dāng)前指針 p 指示第一個結(jié)點(diǎn)while ( p -next != NULL & (p-next)-data!= x ) p=p-next; return p; 返回的指針返回的指針p要么是指向要么是指向x的前一個結(jié)點(diǎn)，的前一個結(jié)點(diǎn)

18、，要么指向最后一個結(jié)點(diǎn)要么指向最后一個結(jié)點(diǎn)31 線性鏈表插入算法要求：在頭指針為要求：在頭指針為HEADHEAD的線性鏈表中包含的線性鏈表中包含元素元素x x的結(jié)點(diǎn)之前插入新元素的結(jié)點(diǎn)之前插入新元素b b 算法操作步驟算法操作步驟:nstep1 找到找到x的位置的位置,使指針使指針p指向指向x的前的前一個結(jié)點(diǎn)；一個結(jié)點(diǎn)；nstep2 申請并生成新結(jié)點(diǎn)申請并生成新結(jié)點(diǎn)snstep3 使使s插入到插入到x所在結(jié)點(diǎn)之前所在結(jié)點(diǎn)之前 考慮幾種特殊情況：空鏈表，首元素為考慮幾種特殊情況：空鏈表，首元素為x 32template void linked_llist:ins_linked_llist(T x

19、, T b) node *p,*q; p= new node ; 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;對于空表和第一個結(jié)點(diǎn)處理必須單獨(dú)考慮對于空表和第一個結(jié)點(diǎn)處理必須單獨(dú)考慮（后面引入頭結(jié)點(diǎn)概念）（后面引入頭結(jié)點(diǎn)概念）33 線性鏈表刪

20、除算法要求：在頭指針為要求：在頭指針為HEADHEAD的線性鏈表中刪除包含的線性鏈表中刪除包含元素元素x x的結(jié)點(diǎn)。的結(jié)點(diǎn)。算法操作步驟算法操作步驟:nstep1 找到找到x的前件的前件,使指針使指針q指向指向x的前件；的前件；nstep2 使指針使指針p指向指向x所在結(jié)點(diǎn)；所在結(jié)點(diǎn)；nstep3 使使p所指結(jié)點(diǎn)所指結(jié)點(diǎn)x脫鏈脫鏈nstep4 釋放釋放p 34template int linked_llist:ins_linked_llist(T x) node *p,*q; if(head=NULL) return 0; if(head-dada=x) p=head-next; delete

21、 head; head =p; return 1 q=head ; while(q-next!=NULL)& (q-next)-d != x) ) q = q- next; if( q-next = NULL ) return 0; p=q-next; q-next = p- next; delete p; return 1; 35課堂練習(xí)n參考參考P70 例例2.15n(1)建立空線性鏈表建立空線性鏈表n(2)插入插入1-30；n(3)輸出鏈表；輸出鏈表；n(4)將單數(shù)的節(jié)點(diǎn)刪除；將單數(shù)的節(jié)點(diǎn)刪除；n(5)再次輸出鏈表；再次輸出鏈表；36引入頭節(jié)點(diǎn)頭結(jié)點(diǎn)頭結(jié)點(diǎn) ：為方便操作，在頭指針

22、和第為方便操作，在頭指針和第1個結(jié)點(diǎn)之個結(jié)點(diǎn)之 間設(shè)置的結(jié)點(diǎn)。間設(shè)置的結(jié)點(diǎn)。首元結(jié)點(diǎn)首元結(jié)點(diǎn) 第一個結(jié)點(diǎn)（第一個結(jié)點(diǎn)（a1）。）。head頭指針頭指針a1首元結(jié)點(diǎn)首元結(jié)點(diǎn) ai.第第i i個結(jié)點(diǎn)個結(jié)點(diǎn)頭結(jié)點(diǎn)頭結(jié)點(diǎn)37空表和非空表表示形式在頭結(jié)點(diǎn)上得到統(tǒng)一空表和非空表表示形式在頭結(jié)點(diǎn)上得到統(tǒng)一（任何情況下至少存在一個結(jié)點(diǎn)）（任何情況下至少存在一個結(jié)點(diǎn)）空表的形式空表的形式 : head - next = NULL head頭結(jié)點(diǎn)頭結(jié)點(diǎn)head頭結(jié)點(diǎn)頭結(jié)點(diǎn)非空表的形式非空表的形式: head - Next = Address引入頭節(jié)點(diǎn)38n無頭結(jié)點(diǎn)時，空表和非空表的運(yùn)算不統(tǒng)一；無頭結(jié)點(diǎn)時，空表和非

23、空表的運(yùn)算不統(tǒng)一；n鏈表檢索只能從頭指針開始，且只能順鏈表方向移鏈表檢索只能從頭指針開始，且只能順鏈表方向移動。動。n在單鏈表中，從表的任一結(jié)點(diǎn)在單鏈表中，從表的任一結(jié)點(diǎn)ai找其前件結(jié)點(diǎn)，時間找其前件結(jié)點(diǎn)，時間復(fù)雜度是復(fù)雜度是O（n）。）。n如果讓鏈表首尾相接，構(gòu)成環(huán)形，這就是如果讓鏈表首尾相接，構(gòu)成環(huán)形，這就是單循環(huán)鏈單循環(huán)鏈表表。n如果在結(jié)點(diǎn)中增加一個指向前一個結(jié)點(diǎn)的指針域，如果在結(jié)點(diǎn)中增加一個指向前一個結(jié)點(diǎn)的指針域，鏈表可以從兩個方向檢索，效果更佳；這就是鏈表可以從兩個方向檢索，效果更佳；這就是雙向雙向循環(huán)鏈表循環(huán)鏈表。39循環(huán)單鏈表(1)單循環(huán)鏈表表示形式：單循環(huán)鏈表表示形式：head

24、head.a1a2an單循環(huán)鏈表為空的條件單循環(huán)鏈表為空的條件: head-next=head表示形式為表示形式為:(2)單循環(huán)鏈表特點(diǎn)：單循環(huán)鏈表特點(diǎn)：n從表中任一結(jié)點(diǎn)出發(fā)，均可以找到表中其它結(jié)點(diǎn)。從表中任一結(jié)點(diǎn)出發(fā)，均可以找到表中其它結(jié)點(diǎn)。n找其前件結(jié)點(diǎn)的時間復(fù)雜度是找其前件結(jié)點(diǎn)的時間復(fù)雜度是O（n）。）。40雙向循環(huán)鏈表n在單向循環(huán)鏈表中，也存在檢索前件結(jié)點(diǎn)費(fèi)時的在單向循環(huán)鏈表中，也存在檢索前件結(jié)點(diǎn)費(fèi)時的問題（所需時間是問題（所需時間是O（n）。）。n雙向循環(huán)鏈表，其存儲結(jié)構(gòu)：雙向循環(huán)鏈表，其存儲結(jié)構(gòu)：template struct node T d; node *next，*prior

25、； ；其它定義與單向鏈表相同。41（1）雙向循環(huán)鏈表結(jié)點(diǎn)結(jié)構(gòu)指向后件結(jié)點(diǎn)指針域數(shù)據(jù)域指向前件結(jié)點(diǎn)指針域 prior data next42（2）雙向循環(huán)鏈表表示形式雙向循環(huán)鏈表表示形式：雙向循環(huán)鏈表表示形式：headhead.ana2a1雙向循環(huán)鏈表為空的條件雙向循環(huán)鏈表為空的條件: head -prior = head-next = head表示形式為表示形式為:43總結(jié):雙向循環(huán)鏈表特點(diǎn)n 適合于兩個方向的移動。適合于兩個方向的移動。n 找其前件結(jié)點(diǎn)的時間復(fù)雜度是找其前件結(jié)點(diǎn)的時間復(fù)雜度是O(1)。44循環(huán)鏈表的運(yùn)算特點(diǎn)n空表與非空表統(tǒng)一空表與非空表統(tǒng)一n判斷鏈表結(jié)束的條件改變了判斷鏈表結(jié)

26、束的條件改變了nP-next=nullnP-next=headn雙向鏈表的運(yùn)算要修改兩個指針雙向鏈表的運(yùn)算要修改兩個指針45循環(huán)鏈表的插入循環(huán)鏈表的插入template void linked_llist:ins_linked_llist(T x) node *p,*q; p= new node ; p-dada =b; q =head;while(q-next !=head)&(q-next)-dada)!=x) q=q-next; p-next =q-next; q-next= p; return;46循環(huán)鏈表的刪除循環(huán)鏈表的刪除template int linked_llist:

27、del_linked_llist(T x) node *p,*q; q=head ; while(q-next!=head)& (q-next)-dada != x) ) q = q- next; if( q-next = head ) return 0; p=q-next; q-next = p- next; delete p; return 1; 47鏈表存儲結(jié)構(gòu)的特點(diǎn)n插入、刪除操作極為方便插入、刪除操作極為方便n數(shù)據(jù)非連續(xù)存放、順序存取數(shù)據(jù)非連續(xù)存放、順序存取n邏輯上相鄰，物理上不一定相鄰邏輯上相鄰，物理上不一定相鄰n存儲結(jié)構(gòu)較復(fù)雜、需要額外的存儲空間存儲結(jié)構(gòu)較復(fù)雜、需要額外的

28、存儲空間結(jié)論結(jié)論： 鏈表存儲結(jié)構(gòu)適合于表中元素頻繁變動鏈表存儲結(jié)構(gòu)適合于表中元素頻繁變動的線性表。的線性表。48課堂練習(xí)n參考參考P74 例例2.16n(1)建立單向空循環(huán)鏈表建立單向空循環(huán)鏈表;n(2)插入插入1-100；n(3)刪除單數(shù)結(jié)點(diǎn)；刪除單數(shù)結(jié)點(diǎn)；491.思考題：思考題：1）假設(shè)一單循環(huán)鏈表的長度大于）假設(shè)一單循環(huán)鏈表的長度大于1，且表中即無頭結(jié)點(diǎn)，且表中即無頭結(jié)點(diǎn)也無頭指針。已知也無頭指針。已知S為指向鏈表中某結(jié)點(diǎn)的指針。試為指向鏈表中某結(jié)點(diǎn)的指針。試寫出刪除表中結(jié)點(diǎn)寫出刪除表中結(jié)點(diǎn)S 的算法。的算法。2）假設(shè)以數(shù)組）假設(shè)以數(shù)組sequm存放循環(huán)隊(duì)列的元素，設(shè)變量存放循環(huán)隊(duì)列的元

29、素，設(shè)變量rear和和quelen分別為指示隊(duì)尾元素位置和隊(duì)中元素個數(shù)，分別為指示隊(duì)尾元素位置和隊(duì)中元素個數(shù)，試寫出入隊(duì)和出隊(duì)算法。試寫出入隊(duì)和出隊(duì)算法。【提示提示】：如何判斷隊(duì)列滿如何判斷隊(duì)列滿/空？空？如何求出隊(duì)首位置？如何求出隊(duì)首位置？循環(huán)隊(duì)列隊(duì)首循環(huán)隊(duì)列隊(duì)首/尾位置的計(jì)算尾位置的計(jì)算【約定約定】：rear下標(biāo)從下標(biāo)從0開始開始作作 業(yè)業(yè)501)template int linked_llist:del_linked_llist(T x) node *p,*q; q=s; while (q-next != s) q = q- next; p = q; p-next = s-next; d

30、elete s; return 1; 51 2) template /入隊(duì)入隊(duì)void sq_Queue:ins_sq_Queue(T x) if (quelen = m) /存儲空間已滿，上溢錯誤存儲空間已滿，上溢錯誤 cout Queue_overflow! endl; return; rear= (rear+1)%m; /隊(duì)尾指針進(jìn)一隊(duì)尾指針進(jìn)一 sequrear=x; /新元素入隊(duì)新元素入隊(duì) quelen+； return;522)template /出隊(duì)出隊(duì)T sq_Queue:del_sq_Queue() T y; int front; if (quelen =0) /隊(duì)列為空，下

31、溢錯誤隊(duì)列為空，下溢錯誤 cout Queue_underflow! =j LOC(a )= j(j-1)/2+i ij 當(dāng) 當(dāng) 66對稱矩陣的壓縮存儲舉例存于一維數(shù)組存于一維數(shù)組S6 S6=( a11, a21, a22, a31, a32, a33 ) 1 2 3 4 5 6 LOC(a31)=3(3-1)/2+1= 4 LOC(a22)=2(2-1)/2+2= 3 LOC(a21)=2(2-1)/2+1= 2112122313233aAaaaaa設(shè)有A3x3矩陣:673 三對角矩陣的壓縮存儲 在三對角矩陣中，三條對角線以外的元素均為零，在三對角矩陣中，三條對角線以外的元素均為零，并且，除

32、了第一行與最后一行外，其他每一行均并且，除了第一行與最后一行外，其他每一行均只有三個元素為非零，因此，只有三個元素為非零，因此，n階三對角矩陣共有階三對角矩陣共有3n-2個非零元素。個非零元素。1112021222332333401,21,11,1aaaaaaaaAaaannnnnnaan nnn68對角矩陣的壓縮存儲以行為主存放以行為主存放 ：2(j 1)i(11)0(1 1)ijBijiajiji 或 以列為主存放 ：2(1)(11)0(1 1)ijBijijiajiji 或 692.4.3 2.4.3 一般稀疏矩陣的表示 n如果一個矩陣中絕大多數(shù)的元素值為零，只有很如果一個矩陣中絕大多數(shù)

33、的元素值為零，只有很少的元素值非零，則稱該矩陣為稀疏矩陣少的元素值非零，則稱該矩陣為稀疏矩陣 。00000500003020000600000000070000000000090000000010000300A70q例如，例如，上述稀疏矩陣上述稀疏矩陣A中的中的8個非零元素可以用以下個非零元素可以用以下8個二元組表示（以行為主的順序排列）：個二元組表示（以行為主的順序排列）： （1，3，3） （1，8，1）（）（3，1，9）（）（4，5，7） （5，7，6） （6，4，2）（）（6，6，3） (7，3，5）q為了表示的唯一性，除了每一個非零元素用一個三為了表示的唯一性，除了每一個非零元素用一個三元組表示外，在所有表示非零元素的