Bài giảng Cấu trúc dữ liệu và giải thuật: Danh sách - Nguyễn Đức Cương

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST

Báo xấu

91
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cấu trúc dữ liệu và giải thuật: Danh sách do Nguyễn Đức Cương biên soạn bao gồm những nội dung về khái niệm, khởi tạo danh sách, các thao tác trên danh sách (thêm, loại bỏ, sửa, tìm kiếm); duyệt danh sách; sắp thứ tự; tách, ghép danh sách; sao chép danh sách; hủy danh sách.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Danh sách - Nguyễn Đức Cương

!" #$ % & ' () * + #, -. " / 01 / # ,/ / * $- 01 / # ,- 2 !%3 ! !"#$ % & ' !"# $(%! ) *+# , -. .///( & % (%!
/ 5 AB C' (D" / E " ? 3 *F % & G H " / D , D" ? I 6 7 " / E " J " K & E " * *F L ) / / * $ -' $ ! 7 89!" : !; %G #M N L/ / $ !? 3 D"J %)1 C # C O / / # C N = 5 - 5 " / / / ; D" ? 3 E " ! "/ D" 1 " / >1 " / (? " / 4 @ !"$#&%(')+* ,- . $ / QR S , 8/ B T K%U V WX "YZ " . b S]]J -c . d J [ S 1 N :# H R * 0 L 6 7 " / /1 N : N = \" K]^_ ^S # V e Z * M1 ` $V * " "Z f chèn b ]J* *J g 0 1 2 3 4 n-2 n-1 0 1 2 3 4 n-2 n-1 P a 1
0 12345( 2$ !" 0 12345( 2$ M1 " / $ S 1 N :# H " / # -i * ."V Qc d! e Z $ S1 N : , H " / m $ f L / $ #H %N ! K 7S # U*B W* V b]J j J kkZ X/ %U ? " / __Qcd J ; S1 N :* " / g 9 n %, 5 H %L -o / M / ; h l 0 12345( 2$ 0 12345( 2$ . 7 8T S 1 N : * " /
M-NPO 1Q 0 3RS; L , ) G $ x /1 N : - " / $ % ' v1 N : $ #T * "/ ' 1 N :% " L* " / ' - " / $ % - " / $ %O - " / $ #y - " / $ %O' v 1 N : $ #T / 1 N :% *T #H" L z S4 S@ 0 3RS; TVUXW Y[Z\ ]+Y^ _ `XWacb+dFef ghi - " / $ # y '1 N : K " / / #T " / B / 1 N :% & $ #T 1 N :%N " / 86 \" K ? R wN :%N $ % & 6#U*BS!#H1 N : 1 ?1 N : % & ; 0 6# U* BkS ? R - "/ $ \N X/ %U #U* B? 1 N :%N "/ /1 N : 1 % & %U #U O r *F X SP Sa PO kjl'm Qv 1 N : ? " / % D' AB C' U 2 31 N : * " / % * x D" " #$ ' ' * x/ O #, 8R {1 N : 1 W"* Af ' * x %U \? * c 4]d J 1 N : 1 * " / ! | *x Q AJ /*U }. . H1 N : K " / gJ 1 W "* ~-•f 1 W"* A f - €WJ • •- H ) %n%U 2 *T A €WJ ~-•‚1 XJ •• * 9 \% 0 * ~-• A ‚1 XJ gJ gJ Sh Sl 3
L u tr DSLK n trong RAM a ch nopq'mr5s Ftu v #w Px 000 Ta có danh sách theo d ng Joe 100 b ng sau 140 a ch Address Name Age Link Bill 110 first 100 140 500 100 Joe 20 140 100 ‘Joe’ 140 ‘Marta’ 110 110 Bill 42 500 Marta 140 NULL 110 500 140 Marta 27 110 Sahra 230 ‘Bill’ 500 ‘Koch’ 230 230 Sahra 25 NULL 140 … … … 230 Kock 500 500 Koch 31 230 230 ‘Bill’ NULL … Sp ] yVR=S;Xzc{ |PO } yVR=S;Xzc{ |PO } )r R ƒ 3 X {% \N 8 %U \1 N !" # $ % & # :%N X{ '! () *91 "„% & o %) * x%U \ 1 W "* ~-•f • •) ? 31 N :* " / 1 N :%N X{ ! E 1( H%N X{ L 8/ ' - €WJ ~-•‚ 1( J ~-•‚ 1 XJ ) 5 &! L )" : C $ 3 * 9 gJ 8/ 1 W "* .€ f • •) " / $ ~-•‚ 1 J ~-•‚1( J ~-•‚1 J gJ S yVQ1w~2c[ ~-•‚… V - XZ )7 31 N : T " / !N = 5 { 5 ' f ~-•‚1J • • 01 1 / #o T new_ele = GetNode(x); 1b † ~-•J WV 1bb }..Zf jj‡ O %?83 T‡ J * * }.. J g †i " „r R ƒ%U \? 1 N : T 7 1^_€W b XJ • •…/ O 1 N :1 1^_1 X b }.. J * * 1J g 4 @ 4
! " void Init(LIST &l) { l.pHead = l.pTail = NULL; } P a y = c[1'[ h l y ~Pc[1'[ P$
• •1 ' " / V ! Z !1 N : T †i void AddFirst(LIST &l, NODE* new_ele) • • 1 ' " / V ! Z#T †i 6%N - { - " / * v ; if (l.pHead == NULL) ( b †i J l.pHead = l.pTail = new_ele; b( J else { & 7 new_ele->pNext = l.pHead; †i ^_1 X b( J l.pHead = new_ele; ( b †i J } } p 4] 5
Px y 1 cc[ NODE* InsertHead(LIST &l, Data x) { NODE* new_ele = GetNode(x); if (new_ele == NULL) return NULL; AddFirst(l, new_ele); return new_ele; } 4S 4 | F#= r1 PxP#y 1 $ • •1 ' " / V ! Z !1 N : T †i void AddTail(LIST &l, NODE *new_ele) • • 1 ' " / V ! Z#T †i 6 K- { - " / * v ; if (l.pHead==NULL) ( b †i J l.pHead = l.pTail = new_ele; b( J else & 7 l.pTail = l.pTail->pNext = new_ele; ^_1 X b †i J } b †i J 44 4@ y r1 cP
• •1 ' " / V ! Z ! H 1 N x5ˆ NODE* InsertTail(LIST &l, Data x) • • 1 ' " / V ! Z#T 1 N : ˆ6 { K- NODE* new_ele = GetNode(x); 71 N : T †i %) x5ˆ 7 % &' if (new_ele == NULL) $ †i # H K " / return NULL; & 7 AddTail(l, new_ele); ‰/ v return new_ele; } 4P 4a 6
# " $% &''( ) *+,-. / %" -. /0 " -. /% *+,0 #"%% , ( ) , % *+,0 1 2,2 *+, 4h 4l A=c[$w c[2 ! # u uW * V.€ e!~-•‚r! ~-•‚ †i Z f WVrŠ b }. .Z f †i ^_1 X b r^_1 XJ r^_1 X b †i J W Vr bb 1 Z 1 b †i J g " • • $ #H %N " / u ‹* "V ! †i ZJ g 4p @] ! ! ! "#$% &' ( )' * +$ ,- "# $ ! . 3 4 %5 06 6 "#$% & / 0* 12 / 3 7 18 # $% &''( # -.9: $%/ ( 2 ! 3 *(( 40"5 -66( 78) 9 40,-- 0 78 " : / 374 %-. /06 6 8 / 3 $% &'' ) ; ); 1 2,28 1 ); @S @ 7
< < = : 1 2 4 8 ! " 1 < ' = = > 12 , ? 1 1@! ; @4 @@ < = : X +F =¡¢"£ ¤2c[&¥[¦§ ~-•‚w ( V. € eZ %& f % &" '# () " %& ~-• ‚1 b }. .J #5 $% &''( ) WV 1( Š b }.. Zf %5 0 * () 1 b 1( J 5 %5 -. /0 (+ %& 1( b 1( ^_1 XJ 1^_1 X b }..J -. /% &''0 WV 1( bb }. .Z 1 b }. .J g 5 % &'' ) , % &''0 ! &( ,- * * 1J g @P @a < 6 > = : < Data RemoveHead(LIST &l) { if (l.pHead == NULL) return NULLDATA; NODE* p = PickHead(l); Data x = p->Info; delete p; return x; } @h @l 8
¡¢"£ ¤ =c[$w ¡¢"£ ¤ =c[$w • • 1 'X{ V ! Z! * 9r ~-•‚w uW *V.€ e! ~-•‚rZ • • 1 'X{ %n8U* B 1 N :" 1 N :r f ~-• ‚1J WV r Šb }.. Zf VrŠ b }.. Z ; 1 b r ^_1 X J 1 b r^_1 XJ • •1 H1 N : N ? WV 1 Šb }. .Z f WV1 bb 1 Z 1 b rJ V1 Š b }.. Z ;• •r O 1 R H K X{ r^_1 X b 1^_1 XJ 1^_1 X b }. . J r^_1 X b 1^_1 XJ • •/ 1 * 9 X{ g 1^_1 X b }.. J g " 1 b w ( V ZJ V1bb Z ; b rJ * * 1J g & 7' * B 1 N :%N X{ @p P] < ? < ? %& + + % &" '# () + + 3 4 ) 8 8 " 1 3 7 # $% &''( ) 66) =8 A 8 / 1 2 "0 1 2,2 A3 8 1 80 PS P < ? $ > "#$%& @ ?" ( )' 6* +$ ?- B= ! , 1 2 2 !8 /, = 1 . ! C8 ,= 1 ?1 2 "#$% & 0* 12 / "#$% & 0"5 / D > 3 * (( 40"5 - 66 ( 78) 9 40?-- . ) 8 !> 0 / 0 78 " : / 5= @! # 1 1@! ( ; 9( 00"5 - "5 / @ ?A9 (*+ -/ ; P4 P@ 9
$ > $ > B @ ( )' 6* - 3 4 %5 0 . ( "/ " . 3 7 18 #B ( 2 ! "#$% & / 374 < , = 0 0* 12 / 3 * ( 40"5 - 377 %-. /0 . ( + / . ( -/ % 0 1 2 * 0 - 1- 0 78 " : / ; ; PP Pa 2 > C ¨©ª¬«-®-¯±°²-³9¯ D?= @! > /,=@ 1 void RemoveList(LIST &l) !11 1 ! > ! = ! ! , 8 , " { 3 4 18 #B ( 2 ! NODE *p; 344 while (l.pHead!= NULL) { A %5 0 p = l.pHead; A5 %5 -. /0 . ( + / l.pHead = p->pNext; 347 delete p; A5 = 0 } 3 7 l.pTail = NULL; ,% &''0 3 " ) / + % &( ,- } Ph Pl ' D: E ' D: E 2 BF B 2 ! ! 1 ! 21 1 11 F 2 / 9:8 E 1 4 5 ! 1 ; 1 # 19:(; G 8 19:, > ! 1 E 1 7 = ? , 8 # H 18 ? ; 1 /( G 1 ! 21 2 ? / $ Pp a] 10
' D: E >= G E* ?E ' D : E2 BF void ListSelectionSort (LIST &l) = ) ?1 > H ) = ?) 2 2,! 2 2 { NODE *min, *p,*q; 1 p = l.pHead; while(p != l.pTail) { H E( " : -1 q = p->pNext; min = p; while(q != NULL) { G 1 / if(q->Info< min->Info ) G 1 2 ! @ H ,!, 1/ min = q; q = q->pNext; 3I18 4 #7 CJ@ = 1 } 14K@> J CL@ = 1 1 7 @M( Hoanvi(min->Info, p->Info); p = p->pNext; } } aS a ' D: E >= G E* ?E ' D: E >= G E* ?E N! 1 H1 = ? 1 , O H 2" , = @I1 2 ! , 21 / P ,> ! 2 2 1 H ; 7 34 G 2 P ,, Q1 0 37 ) 1 H , R 0 3 8 H 0 3J P ,0 3S' C,2@ 78 H 0 a4 a@ ' D: E E ' D: E E aP aa 11
' D: E E ' D: E E ah al ' D: E E ' D: E E void ListSelectionSort2 (LIST &list) { LIST lRes; NODE *min, *minprev; Init(lRes); while(list.pHead != NULL) { minprev = FindMinprev(list); min = PickAfter(list, minprev); AddTail(lRes, min); } list = lRes; } ap h] ' D: E E NODE* FindMinprev (LIST list) I E D: E { ! T 8U NODE *min, *minprev, *p, *q; minprev = q = NULL; min=p =list.pHead; ! N 1U while(p != NULL){ 4 5 %6 ( if (p->Info < min->Info) { min = p; minprev = q; } q = p; p = p->pNext; } hS h 12
J ?' K ' D: E ? %& % &" " 1 7 8- 3 4 / 7 B 1 0 % &" 1 3 7 2
´Xµ ¶+·F¸¹ºµ » ¼[¶ ½¾ ·"¿ÀÁÂÃÁ½Ä»Á ´Xµ ¶+·F¸ÅÆÇ ÈVÉAÊ;ËÌsÍ # $ % &' ( ) &* $ # $ +, +( hp l] ´Xµ ¶+·F¸ÅÆÇ ÈVÉAÊ;ËÌsÍ ´Xµ ¶+·F¸ÅÆÇ ÈVÉAÊ;ËÌsÍ void ListQSort(LIST &list) - &* ". ! #/ " #" +& { NODE *X, *p; LIST list1, list2; if (list.pHead == list.pTail) return; Init(list1); Init(list2); X = PickHead(list); while (list.pHead != NULL) { p = PickHead(list); if (p->Info Info) AddTail(list1, p); else AddTail(list2, p); } lS l ´Xµ ¶+·F¸ÅÆÇ ÈVÉAÊ;ËÌsÍ " EL ListQSort(list1); void ListAppend(LIST &list, LIST &list2) ListQSort(list2); { ListAppend(list, list1); if (list2.pHead == NULL) return; if (list.pHead == NULL) AddTail(list, X); list = list2; ListAppend(list, list2); else { list.pTail->pNext = list2.pHead; list.pTail = list2.pTail; } } Init(list2); } l4 l@ 14
J ? K : I K % &9 " : K % &9 " " 1 7 8- T 8 / 1 @ 3 4 / 7 1 ! B 1 0 ! &" 1 G 1" 8 V/ !/ >F 3 7 E , 1 1 2 = / ! 2,2 = 2, =, ' 7/ '4 '7; / ; 2@ 8= 8 H1, W1 ! 8 1 3 UV/ N 1 U #'4(; 2 / ; 3 JUV/ N 1 U #'7(; 3 S !'4 '7 H V/ ,2 / ' H 2 V/ ; lP la I KM< I KM< UV/ , 4 E 1 2 = , 4 , 44> ,47 E 1 2 = , , 4>, 7 !, 44> ,47 ,2 , 4 lh ll I KM< I KM< UV/ , 7 !, 4>, 7 ,2 , E 1 2 = , 7 , 74> ,77 !, 74> ,77 ,2 , 7 lp p] 15
I K =N I K =N ÎÏÐ Ñ ÒÓÐ ÔÕ ÖØ×ÚÙ Ûc×cÜFÏÚÙ Õ Ý ÒÓÞ ÜFß à$á Ð ÔÕ â ã ÒcÞ Ü ß á äåæá çè B $ C ( )' 6* + )' 6* O+ )' 6* L- Ð é Ý3á Ð ÔæÕ ê ëcì×ÓícÑVîîá Ð ÔÕ ê ëïßíÐ á â Ù ×ÓÕ ðcÙ ñ è . Þ ñcÐ Õ Ý á äæâ è Þ ñcÐ Õ Ý á çâ èèâ "#$% & 0@ ?2 (* -/ ÒÓÐ ÔÕ Ð òé Ý Ð Ôæá çÕ Ù ê ÐëcóÓìðÕ×Ó× íÓÝ Ñcá Ð Ôæâ Õ ã åôá äåá çâ3èèâ A * (*O+ -/ ÒÓÒÓÐÐ ÔÔÕÕ ÖØÖØ×Ú×ÚÙÙ ÛcÛc×c×cÜFÜFÏÚÏÚÙÙ ÕÕ ÝÝ áá çcäæââ èè 9(* 12 - õ ÒÓÐ ÔÕ ÖØ×ÚÙ Ûc× Ý á Ð ÔæÕ åôá äåá çâ3èèâ 9( 78) 9 P0* 12 78) 9 - ×á Ôï× ÒÓÐ ÔÕ öëcëï×ÚñÑ Ý á Ð ÔæÕ åôá äâ3è $ C (* +* O+* L-/ õ * $ C (* +* L+* O-/ ; pS p I K =N I K : ' N 1#'9 U X, > '9U X, 4>'9 U X, 7( " : K Y N 1 / 1 @ ZB[ \0 1 ! ; * ,##, 4; 5 ( XX#, 7; 5 (( Y G 1N 1 V/ !/ > 8 1 :#, 4; 5 -.9:]%, 7; 5 -.9:( 1 1 2 8 C %E 85 #, 4(0 1 ! ; , %E 85 #, 7(0 2N 1 / 8 1 2 ^ , #, >(0 1) F ! / H 2 > 18 _ 1 ! 1@ 8=; ' ^ #, > ,4(0' ^ #, > ,7(0 _ p4 p@ ´Xµ ¶+·F¸w÷4ÁøÀ , E B ) ( )' 6* - B @ ( )' * - ! " #$ % . . / "#$% & / $ :/ 0* 12 / PPQ R/ 88 / 3 * ( 40"5 - 9 ( 0S/ P / TT- . . ( &' -/ % ( 0 ))* +,- 1- 1 2* 0 PPQ" * R/ 88:/ 0 78 " : / InsertHead(l, x); ; ; ; pP pa ; 16