線性鏈表數組PPT精品文檔

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

2、元。由數據域和指針域：表中元素的存儲單元。由數據域和指針域組成。數據域存放元素數據，指針域存放指向下一結點位組成。數據域存放元素數據，指針域存放指向下一結點位置的指針。置的指針。結點形式為：結點形式為：鏈表（鏈表（Link）：）：由結點組成的表。由結點組成的表。頭指針（頭指針（head）：）：指向鏈表中第指向鏈表中第1個結點的指針。個結點的指針。 data next數據域 指針域3單鏈表的物理存儲 存儲地址存儲地址 數據域（數據域（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課堂練習nP58 例子例子 2.12n定義一個空鏈表，依次插入定義一個空鏈表，依次插入1-100打印輸出；然后刪除前打印輸出；然后刪除前50個結點，并再次個結點，并再次輸出。輸出。7 帶鏈的棧n棧也是線性表，可以采用鏈式存儲結構棧也是線性表，可以采用鏈式存儲結構n順序棧最多可用于順序棧最多可用于2個棧的共享，對于更多個棧的共享，對于更多的棧就難于表達了。的棧就難于表達了。n對于最大空間需要量事先不知的情況，就不對于最大

5、空間需要量事先不知的情況，就不能使用順序棧了。這時，就需要采用鏈棧。能使用順序棧了。這時，就需要采用鏈棧。鏈棧：棧的鏈式存儲結構鏈棧：棧的鏈式存儲結構8鏈棧示意圖a1a2a3棧底棧底top棧頂棧頂.ai9Template struct node T data ; node *next ; ;template class linked_Stack private: node *top; /棧頂指針棧頂指針 棧的鏈式表示 鏈棧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ù)申請新結點無法繼續(xù)申請新結點):n t = NULL nt 為申請的結點為申請的結點,為為NULL表示失敗。表示失敗。 12鏈棧進棧操作操作步驟操作步驟:nstep1 ：申請一個鏈棧結點，若：申請一個鏈棧結點，若t=NULL，則表示鏈滿；否則，執(zhí)行則表示鏈滿；否則，執(zhí)行step2 ；nstep2 ：在：在top所指結點之前插入新結點，所指結點之前插入新結點，并將并將t

7、op指向新申請的結點指向新申請的結點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; 鏈棧進棧算法14鏈棧出棧操作操作步驟操作步驟:nstep1 若鏈棧為空，則輸出棧溢出信息；否若鏈棧為空，則輸出棧溢出信息；否則，執(zhí)行則，執(zhí)行step 2。nstep2 (保存保存top為為q)并使并使top 指向被刪除結點指向被刪除結點的后件結點，刪除的后件結點，刪除q所指結點。所指結點。nste

8、p 3 釋放被刪除結點的存儲空間。返回出釋放被刪除結點的存儲空間。返回出棧元素值。棧元素值。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課堂練習nP62, 參考參考2.13;n建立空棧，入棧建立空棧，入棧 10,20,30,40,50；n退棧退棧2次，然后輸出棧中所有的元素；次，然后輸出棧中所有的元素；174 帶鏈的隊列1). 隊列也是線

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

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

11、結點, ,非空隊列非空隊列:NULL20鏈隊列的入隊操作要求：在鏈隊列中插入一個元素要求：在鏈隊列中插入一個元素x x（入隊運算）。（入隊運算）。 算法操作步驟算法操作步驟: : Step1：申請建立一個新結點：申請建立一個新結點p；Step2：判別：判別p是否為空；若空，表示是否為空；若空，表示 隊列已滿；隊列已滿；Step3：非空，將：非空，將p插入鏈中，修改插入鏈中，修改rear指針。指針。21template /入隊入隊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）/隊列為空的情況隊列為空的情況 front =p; else rear - next =p; rear = p; return ; 22 鏈隊列的出隊操作出隊操作要考慮兩種情況出隊操作要考慮兩種情況:q當隊列長度為當隊列長度為1時，除了修改隊頭指針外，還要修時，除了修改隊頭指針外，還要修改隊尾指針。改隊尾指針。QueueQueueQueueQueuefrontrearrearfronta1 an a1a2 .a2 .an q 當隊列長度大于當隊列長度大于1時時,只修改隊頭指針即可只修改隊頭指針即可QueueQueuean

13、rearQueueQueuefrontrearTfrontNULL23鏈隊列的出隊操作要求：在鏈隊列中刪除一個元素（退隊運要求：在鏈隊列中刪除一個元素（退隊運算）。算）。算法描述算法描述:Step1：判別隊列是否為空；若空，則顯示隊：判別隊列是否為空；若空，則顯示隊列列下溢下溢；Step2 ：非空，則判別隊列長度是否為：非空，則判別隊列長度是否為1； Step2.1：不為：不為1，修改頭指針；，修改頭指針； Step2.2：為：為1，則修改頭、尾指針；，則修改頭、尾指針；Step3：釋放：釋放T。24 template /出隊出隊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課堂練習nP65 例子例子 2.14 n建立空隊列，插入建立空隊列，插入1-100；n作作40次退隊操作；次退隊操作；n打印輸出；打印輸出；262.3.2 線性鏈表基本運算 1. 單鏈表的查找單鏈表的查找 find2. 單鏈表的的插入單鏈表的的插入insert3. 單鏈表的刪除單鏈表的刪除delete27 指針的基本操作n設指針變量設指針變

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

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

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

18、，要么指向最后一個結點要么指向最后一個結點31 線性鏈表插入算法要求：在頭指針為要求：在頭指針為HEADHEAD的線性鏈表中包含的線性鏈表中包含元素元素x x的結點之前插入新元素的結點之前插入新元素b b 算法操作步驟算法操作步驟:nstep1 找到找到x的位置的位置,使指針使指針p指向指向x的前的前一個結點；一個結點；nstep2 申請并生成新結點申請并生成新結點snstep3 使使s插入到插入到x所在結點之前所在結點之前 考慮幾種特殊情況：空鏈表，首元素為考慮幾種特殊情況：空鏈表，首元素為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;對于空表和第一個結點處理必須單獨考慮對于空表和第一個結點處理必須單獨考慮（后面引入頭結點概念）（后面引入頭結點概念）33 線性鏈表刪

20、除算法要求：在頭指針為要求：在頭指針為HEADHEAD的線性鏈表中刪除包含的線性鏈表中刪除包含元素元素x x的結點。的結點。算法操作步驟算法操作步驟:nstep1 找到找到x的前件的前件,使指針使指針q指向指向x的前件；的前件；nstep2 使指針使指針p指向指向x所在結點；所在結點；nstep3 使使p所指結點所指結點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課堂練習n參考參考P70 例例2.15n(1)建立空線性鏈表建立空線性鏈表n(2)插入插入1-30；n(3)輸出鏈表；輸出鏈表；n(4)將單數的節(jié)點刪除；將單數的節(jié)點刪除；n(5)再次輸出鏈表；再次輸出鏈表；36引入頭節(jié)點頭結點頭結點 ：為方便操作，在頭指針

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

23、空表的運算不統(tǒng)一；n鏈表檢索只能從頭指針開始，且只能順鏈表方向移鏈表檢索只能從頭指針開始，且只能順鏈表方向移動。動。n在單鏈表中，從表的任一結點在單鏈表中，從表的任一結點ai找其前件結點，時間找其前件結點，時間復雜度是復雜度是O（n）。）。n如果讓鏈表首尾相接，構成環(huán)形，這就是如果讓鏈表首尾相接，構成環(huán)形，這就是單循環(huán)鏈單循環(huán)鏈表表。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)鏈表特點：單循環(huán)鏈表特點：n從表中任一結點出發(fā)，均可以找到表中其它結點。從表中任一結點出發(fā)，均可以找到表中其它結點。n找其前件結點的時間復雜度是找其前件結點的時間復雜度是O（n）。）。40雙向循環(huán)鏈表n在單向循環(huán)鏈表中，也存在檢索前件結點費時的在單向循環(huán)鏈表中，也存在檢索前件結點費時的問題（所需時間是問題（所需時間是O（n）。）。n雙向循環(huán)鏈表，其存儲結構：雙向循環(huán)鏈表，其存儲結構：template struct node T d; node *next，*prior

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

26、束的條件改變了nP-next=nullnP-next=headn雙向鏈表的運算要修改兩個指針雙向鏈表的運算要修改兩個指針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鏈表存儲結構的特點n插入、刪除操作極為方便插入、刪除操作極為方便n數據非連續(xù)存放、順序存取數據非連續(xù)存放、順序存取n邏輯上相鄰，物理上不一定相鄰邏輯上相鄰，物理上不一定相鄰n存儲結構較復雜、需要額外的存儲空間存儲結構較復雜、需要額外的

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

29、素，設變量rear和和quelen分別為指示隊尾元素位置和隊中元素個數，分別為指示隊尾元素位置和隊中元素個數，試寫出入隊和出隊算法。試寫出入隊和出隊算法?！咎崾咎崾尽浚喝绾闻袛嚓犃袧M如何判斷隊列滿/空？空？如何求出隊首位置？如何求出隊首位置？循環(huán)隊列隊首循環(huán)隊列隊首/尾位置的計算尾位置的計算【約定約定】：rear下標從下標從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 /入隊入隊void sq_Queue:ins_sq_Queue(T x) if (quelen = m) /存儲空間已滿，上溢錯誤存儲空間已滿，上溢錯誤 cout Queue_overflow! endl; return; rear= (rear+1)%m; /隊尾指針進一隊尾指針進一 sequrear=x; /新元素入隊新元素入隊 quelen+； return;522)template /出隊出隊T sq_Queue:del_sq_Queue() T y; int front; if (quelen =0) /隊列為空，下

31、溢錯誤隊列為空，下溢錯誤 cout Queue_underflow! =j LOC(a )= j(j-1)/2+i ij 當 當 66對稱矩陣的壓縮存儲舉例存于一維數組存于一維數組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設有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如果一個矩陣中絕大多數的元素值為零，只有很如果一個矩陣中絕大多數

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為了表示的唯一性，除了每一個非零元素用一個三為了表示的唯一性，除了每一個非零元素用一個三元組表示外，在所有表示非零元素的