Academia.eduAcademia.edu
C U TRÚC D LI U  GI I THU T Lê Văn Hạnh levanhanhvn@gmail.com M C TIểU MỌN H C - - - - Sau khi hoàn tất, sinh viên có thể: Nhận thức đ ợc sự cần thiết của việc thiết kế cấu trúc dữ liệu. Rèn luyện khả năng t duy logic, phát triển các thuật toán, chọn lựa việc tổ chức dữ liệu phù hợp và các giải thuật xử lý dữ liệu có hiệu quả trong từng bài toán cụ thể. Phân tích đ phức tạp của các ch ơng trình có kích th c nhỏ và trung bình. Hiểu và vận dụng đ ợc • Các thuật toán sắp xếp và tìm kiếm trên mảng 1 chiều. • Các cấu trúc stacks, queues, linked list, binary tree, binary search tree, Balanced Binary Search Tree, .... Rèn kuyện khả năng tự nghiên cứu của sinh viên TÀI LI U THAM KH O 1. Nguyễn Quốc C ng, Hoàng Đức Hải, Cấu trúc dữ liệu + Giải thuật = Chương trình, sách dịch, NXB Giáo Dục – 1999 2. Đinh Mạnh T ng, Cấu trúc dữ liệu và Thuật toán, NXB Khoa Học và Kỹ Thuật – 2000 3. Trần Hạnh Nhi, D ơng Anh Đức, Giáo trình c u trúc d li u 1, Nhà xuất bản Đại học Quốc Gia Tp Hồ Chí Minh, 2003. 4. Robert Sedgewick, Cẩm nang thuật toán, bản dịch của nhóm tác giả Đại học khoa học tự nhiên, Nhà xuất bản Khoa học kỹ thuật, 1994. 5. A.V. Aho, J.E Hopcroft, J.D Ullman, Data structures and Algorithms, Addison Wesley, 1983. 6. P. S. Deshpande, C and Data structure, NXB Dreamtech Press India Pvt. Ltd, 2003. CÁCH TệNH ĐI M MỌN H C - Điểm số: • Giữa kỳ  Chuyên cần  Bài tập/Thực hành/Seminar : 40% : 10% : 30% • Thi cuối kỳ (tự luận/vấn đáp) : 60% GI I THI U - Hầu hết các bài toán đều có nhiều giải thuật khác nhau để giải quyết chúng. Vậy làm thế nào chọn đ ợc m t giải thuật tốt nhất? - Việc chọn lựa phụ thu c vào nhiều yếu tố nh : • Đ phức tạp tính toán của giải thuật • Nhu cầu về dung l ợng b nh . • Tần suất sử dụng • Tính đơn giản • Tốc đ thực hiện, • ... - Thông th ng mục tiêu chọn lựa là : i. Giải thuật rõ ràng, dễ hiểu, dễ mã hóa và hiệu chỉnh. ii.Giải thuật sử dụng có hiệu quả tài nguyên của máy tính và đặc biệt chạy càng nhanh càng tốt. N I DUNG MỌN H C - Ch ơng 1: Ôn tập về Ngôn ngữ lập trình - Chương 2: Đệ quy - Chương 3: Các giải thuật tìm kiếm trên mảng 1 chiều - Chương 4: Các giải thuật sắp xếp trên mảng 1 chiều - Chương 5: Danh sách liên kết đ ng (Linked List) - Chương 6: Ngăn xếp (Stack) - Chương 7: Hàng đợi (Queue) - Chương 8: Cây nhị phân tìm kiếm (Binary Search Tree) - Chương 9: Bảng băm (Hash Table) Ch ng 1 ỌN T P V NGỌN NG L P TRỊNH M C TIểU i. Nhắc lại các kiến thức cơ bản trong lập trình C ii. Gi i thiệu vai trò của tổ chức dữ liệu iii. Mối quan hệ giữa giải thuật & cấu trúc dữ liệu iv. Các khái niệm và yêu cầu về CTDL v. Tổng quan về đánh giá đ phức tạp giải thuật 8 N I DUNG 1. Kiểu dữ liệu 2. Xác định bài toán 3. Cấu trúc dữ liệu 4. Giải thuật 5. Đ phức tạp của giải thuật 6. Vai trò của cấu trúc dữ liệu & giải thuật 9 1. KI U D LI U Xét đoạn ch ơng trình sau: void main() { char x=200, y=100, z; z=x+y; printf(“Z=%d“,z); } Cho bi t k t qu ?? )z 1 0 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 1 1 0 0 10 1. KI U D LI U 1.1. Khái ni m v ki u d li u T = <V, O> - Các thu c tính của m t kiểu dữ liệu gồm: • T: Tên kiểu dữ liệu • V: Miền giá trị (th ng phụ thu c vào kích th • O: Tập các xử lý tác đ ng lên kiểu dữ liệu đó c l u trữ)  Ví dụ: Kiểu dữ liệu số nguyên char trong ngôn ngữ C T = char void main() V = {-128, 127} { char x=200, y=100, z; O = {+, -, *, /, %} } z=x+y; printf(“Z=%d“,z); 11 1. KI U D LI U 1.2. Phân loại ki u d li u - Ki u ếữ ệi u tĩnể (kiểu dữ liệu cơ bản) • Kiểu cơ s : Số nguyên, số thực và kiểu logic • Kiểu dãy (mảng), xâu ký tự • Kiểu có cấu trúc • Kiểu tập tin - Ki u ếữ ệi u độnỂ • Danh sách liên kết • Hàng đợi • Ngăn xếp • Cây • Bảng băm • … 12 1. KI U D LI U 1.2. Phân loại ki u d li u Ki u ếữ ệi u Tĩnể Ki u ếữ ệi u ĐộnỂ - Đ ợc định nghĩa th i - Đ ợc gắn kết v i m t con điểm biên dịch. trỏ (tại thời điểm biên dịch chưa có). - Đ ợc cấp phát th i điểm - Phát sinh lúc thực thi. liên kết. - Có thể có giá trị ban đầu - Không xác định giá trị ban tùy theo từng ngôn ngữ lập đầu. trình. - Tồn tại đến khi kết thúc - Đ ợc giải phóng khỏi b ch ơng trình. nh khi cần. 13 1. KI U D LI U 1.3. Ki u d li u tĩnh - Ki u s nguyên Tên ki u Stt 1 char 2 3 4 5 6 7 8 - Ki u s th c - Ki u lu n lỦ (C++) unsigned char short unsigned short int unsigned int long unsigned long Stt Tên ki u 1 float 2 double 3 long double Ghi chú Ký tự Sô nguyên Sô nguyên d ơng Sô nguyên Số nguyên d ơng Sô nguyên Số nguyên d ơng Sô nguyên Sô nguyên d ơng Ghi chú Kích thước 1 byte 1 byte 1 byte 2 bytes 2 bytes 4 bytes 4 bytes 4 bytes 4 bytes Kích thước 4 bytes 8 bytes 8 bytes Stt Tên ki u Ghi chú Kích thước 1 bool Gồm 2 giá trị: true hoặc 1 bit false 14 1. KI U D LI U 1.3. Ki u d li u tĩnh - Ki u m ng 1 chi u Gi t ị 5 7 1 Vị trí hỉàsố 0 10 … 2 … 3 11 2 n-2 n-1 • Khai báo <kiểu dữ liệu> <Tên mảng> [<Số l ợng phần tử>] ; • VD1: i t a[ ] = { }; • VD2: i t a[ ] = { , , , hoặc: i t a[] = { , , , - Ki u xơu kỦ t , , }; }; (chu i) • Khai báo char <Tên xâu> [<Số ký tự max>] ; • VD: har hote [ ]; 15 1. KI U D LI U 1.3. Ki u d li u tĩnh - Ki u có c u trúc • Khai báo stru t tê _stru t { khai o thuộ tí h; }; t pedef stru t tê _stru t tê _kiểu; • Ví dụ stru t stDate { har thu[9]; u sig ed har ga ; u sig ed har tha g; i t a ; }; t pedef stru t stDate DáTE; 16 1. KI U D LI U 1.4. Ki u d li u đ ng ậ Bi n con tr - Khi sử dụng phải cấp phát biến con trỏ bằng lệnh new, hủy bằng lệnh delete - M ng 1 chi u <KDL> *<Tên biến mảng>; - Xơu kỦ t char *<Tên biến chuỗi>; - T p tin FILE *<Tên biến chuỗi>; - VD: int *a; char *str; FILE *f; int n = 10; str = new char[51]; fà=àfope a = new int[n]; delete str; if (f!=NULL) //àsửàdụ gà ả gàa { TE“T.t t ,à /*àC àlệ hà ầ àd ;à g*/ /*àĐó gàtậpàti */ delete a; } delete f; 17 1. KI U D LI U 1.4. Ki u d li u đ ng ậ Bi n con tr - Truy c p thƠnh ph n c a bi n • Biến cấu trúc kiểu tĩnh (cấu trúc): dùng d u ch m giữa tên biến và thu c tính thành phần Khi sử dụng: VD: Khai báo tr c đó: stDate struct { char thu[9]; unsigned char ngay; unsigned char thang; int nam; }; typedef struct stDate DATE; DATE d; d.nam = 2012; • Biến cấu trúc kiểu con trỏ: dùng dấu chấm giữa tên biến và thu c tính thành phần VD: <tê à iế >->th hàphầ à ấuàtr Khi sử dụng: DATE *d; d->nam = 2012; 18 2. XÁC Đ NH BÀI TOÁN Input -> Process -> Output B1: Mô tả rõ: • Input: Các giả thiết, thông tin đ ợc cung cấp • Output: kết quả cần đạt đ ợc những yêu cầu nào? B2: Lựa chọn cấu trúc dữ liệu sẽ sử dụng trong cài đặt ch ơng trình (Process) B3: Thiết kế giải thuật: mô tả trình tự các thao tác trên m t số đối t ợng nào đó sao cho m t số hữu hạn lần thực hiện ta thu đ ợc kết quả nh mong đợi 19 3.C U TRÚC D LI U 3.1. Khái ni m - Cách thức liên kết/ tổ chức các kiểu dữ liệu cơ s / kiểu dữ liệu có cấu trúc hợp lý để sử dụng m t cách hiệu quả - Tập các thao tác để truy cập/ xử lý các thành phần dữ liệu 3.2. Các tiêu chuẩn đánh giá CTDL - Phản ánh đúng thực tế - Phù hợp v i thao tác - Tiết kiệm tài nguyên hệ thống 20 4. GI I THU T (HAY THU T GI I) 4.1 Khái ni m - Giải thuật là một t p ểợp ểữu ểạn của các chỉ thị hay ph ơng cách đ ợc định nghĩa rõ ràng cho việc hoàn tất m t số sự việc từ m t trạng thái ban đầu cho tr c. 4.2. Các phương pháp bi u di n gi i thuật - Các ph ơng pháp • Mã tự nhiên • Pseudocode (mã giả) • Flowchart (l u đồ) 21 4. Gi i thu t 4.2. Các ph ng pháp bi u di n gi i thu t 4.2.1. Mô t gi i thuật bằng mã tự nhiên - Thể hiện ý t ng giải quyết bài toán bằng ngôn ngữ tự nhiên giản l ợc. - Ví dụ: Tìm ướ số chung lớ hất ủa 2 số nguyên dươ g a, b • Bước 1: Nếu a = b thì kết luậ a là ướ số chung lớ kết thúc hất, • Bước 2: Nếu a > b thì a = a – b; Ngượ lại thì b = b – a; • Bước 3: Quay trở lại Bướ 1 22 4. Gi i thu t 4.2. Các ph ng pháp bi u di n gi i thu t 4.2.2. Mô t gi i thu t b ng mư gi (PSEUDOCODE) - Dễ hiểu, không chi tiết đến các kỹ thuật lập trình cấp đ hết sức tổng quát: gần ngôn ngữ tự nhiên - - Hoặc rất chi tiết: nh dùng ngôn ngữ tựa Pascal, C++, … - Các từ khóa • • • • • • • IF <Điều kiệ >àTHENà…àENDIF IF <Điều kiệ > THEN ... ELSE ... ENDIF WHILE <Điều kiệ >àDOà…àENDWHILE DOà…àUNTILà<Điều kiệ > WRITEà… REáDà… RETURNà… 23 4. Gi i thu t 4.2. Các ph ng pháp bi u di n gi i thu t 4.2.3. Mô t gi i thu t b ng l u đ (FLOWCHART) - CáẾ Ệý ểi u ếùnỂ mô tả Ểiải tểu t bằnỂ ệ u đ KÝ HI U Ý NGHƾA Bắt đầu/kết thúc Dữ liệu vào Xuất dữ liệu Lệnh hoặc nhóm lệnh để thực hiện 1 chức năng nào đó của ch ơng trình Ch ơng trình con đư định nghĩa tr c đó Quyết định h ng xử lý sẽ rẽ vào nhánh nào tùy vào việc thỏa điều kiện đư ghi trong khối. Khi điều kiện có nhiều nhánh ra (switch … case), điều kiện sẽ ghi trên từng nhánh     H ng xử lý của l u đồ Điểm nối của từng trang hoặc từng phần của l u đồ Giá trị trả về 4. Gi i thu t 4.2. Các ph ng pháp bi u di n gi i thu t 4.2.4. Mô t gi i thu t b ng 3 ph - ng pháp Bài tểựẾ ểànể 1: Cho số nguyên n. Tính trị tuyệt đối của n  Đầu vào: Số nguyên n  Đầu ra: |n| • Giải thuật  Bướ à :à  Bướ à :à  Bướ à :à dùng Mã tự nhiên: hậpà ếuà < àth à à:=à à*à -1) uấtà • Giải thuật dùng Pseudocode: READ n IF n<0 THEN n := n * (-1) ENDIF WRITE n • Giải thuật dùng Flowchart: BEGIN n Y n<0 N n END = *- 4. Gi i thu t 4.2. Các ph ng pháp bi u di n gi i thu t 4.2.4. Mô t gi i thu t b ng 3 ph - ng pháp TểựẾ hành 2: Giải và biện luận ph ơng trình bậc I: ax+b=0  Đầu vào: Hai số nguyên a và b  Đầu ra: Nghiệm của pt • Giải thuật dùng Mã tự nhiên:  Bước :à hậpàaà à  Bước : ếu a< th sa g Bướ ; gượ lại sa g Bướ  Bước : ếu < th uất PTV“N , o g sa g Bướ ; gượ lại sa g Bướ  Bước : uất PT“N , o g sa g Bướ  Bước : t h :=- /a uất a h h  Bước :àkếtàthú à hươ gàt h. •Giải thuật dùng Pseudocode: READ a, b IF a=0 THEN IF b=0 THEN WRITE PTàV“N ELSE WRITE PTàVN ENDIF ELSE x := -b/a WRITE Nghiệ à: à+à ENDIF 4. Gi i thu t 4.2. Các ph ng pháp bi u di n gi i thu t 4.2.4. Mô t gi i thu t b ng 3 ph - ng pháp TểựẾ hành 2: Giải và biện luận ph ơng trình bậc 1 ax + b = 0 •Giải thuật dùng Pseudocode: READ a, b IF a=0 THEN IF b=0 THEN WRITE PTàV“N ELSE WRITE PTàVN ENDIF ELSE x := -b/a WRITE Nghiệ à: à+à ENDIF • Giải thuật dùng Flowchart: BEGIN a,b N a=0 Y N x=-b/a PTVN END b=0 Y PTV“N 4. Gi i thu t 4.2. Các ph ng pháp bi u di n gi i thu t 4.2.4. Mô t gi i thu t b ng 3 ph ng pháp TểựẾ hành 3: Giải và biện luận ph ơng trình bậc ax2 + bx + c = 0 - • Giải thuật dùng Flowchart: • Giải thuật dùng Flowchart: BEGIN BEGIN a, b, c a=0 a, b, c Y N b=0 N x=-c/b a=0 PTB1(b,c) N Y Y delta=b*b -4ac Y c=0 “PTVSN” delta=b*b -4ac N delta<0 N delta=0 N “PTVN” Y END delta<0 N Y x=–b/2a x1 = -b + sqrt(delta)/2*a x2 = -b - sqrt(delta)/2*a delta=0 N “PTVN” Y Y END x=–b/2a x1 = -b + sqrt(delta)/2*a x2 = -b - sqrt(delta)/2*a 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG i. C u trúc tuần tự Lệnh 1 Lệnh 2 Lệnh 3 . . . ii. C u trúc r nhánh • • • if if … else if … else lồng nhau nhiều cấp iii. C u trúc lựa chọn iv. C u trúc lặp • • • switch case for while do … while C 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C 5.1. C U TRÚC TU N T Lệnh 1 Lệnh 2 Lệnh 3 Cấu trúc tuần t ̣ thực thi tiến trình, mỗi lệnh đ ợc thực thi theo m t chuỗi t trên xuống, xong lệnh này rồi chuyển xuống lệnh kê tiếp. 30 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG 5.1. C U TRÚC TU N T C void main() { BEGIN int a, b, tong, hieu, tich; float thuong; a,b printf("Nhap vao a: “); scanf(“%d”,&a); tong=a+b hieu=a+b tich=a+b thuong=a+b printf("Nhap vao b: “); scanf(“%d”,&b); tong = a + b; hieu = a - b; ‘Tong=“ + tong “Hieu=“ + hieu “Tich=“ + tich “Thuong=“+thuong tich = a * b; thuong = (float)a / b; //Ép kiểu printf(“Tong: %5d“, tong); printf(“Hieu: %5d“, hieu); printf(“Tich: %5d“, tich); printf(“Thuong: %5f”, Thuong); END } 31 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG 5.2. C U TRÚC RẼ NHÁNH C 6.1. Công d ng: Cấu trúc rẽ nhánh chỉ cho máy tính chọn thực hiện m t dưy lệnh nào đó dựa vào kết quả của m t điều kiện (biểu thức quan hệ hay biểu thức so sánh) 6.2. Phơn lo i: Gồm 2 dạng: Chỉ xét trường hợp đúng điều kiện if (biểu th́c đìu kịn) { <kh́i ḷnh> ; } Xét cả hai trường hợp đúng và sai: if (biểu th́c đìu kịn) { <kh́i ḷnh 1>; } else { <kh́i ḷnh 2>; } 32 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG 5.2. C U TRÚC R NHÁNH C Ví dụ: Viết ch ơng trình nhập vào m t số, in ra trị tuyệt đối của số đó. void main() BEGIN { int n; printf("Nhap mot so:“); scanf(“%d”,&n); if (n < 0) { n n<0 Y N n=n*(-1); n=n*(-1) } printf("Tri tuyet doi la:%d”,n); n } END 33 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG 5.2. C u trúc r nhánh C Ví ếụ 2: Nhập vào số nguyên a và b, nếu a là b i số của b thì in thông báo “a là b i số của b”, ng ợc lại in “a khong la boi so cua b” BEGIN if(a%b==0) printf("Nhap vao a: “); scanf(“%d”&a); printf(“Nhap vao b: “); scanf(“%d”&b); a,b N Y a mod b=0 “a KHÔNG lơ b i ś của b” “a LÀ b i ś của b” END else void main() { int a, b; printf("a LA boi so vao cua a: b“); printf("Nhap “); scanf(“%d”,&a); printf("Nhap vao b: “); printf("a KHONG la boi so cua b“); scanf(“%d”,&b); if(a%b == 0) printf(" a LA boi so cua b“); else } printf("a KHONG la boi so cua b“); 34 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C 5.3. C u trúc nhi u l a ch n s it hà ỉu th́  … aseàa N aseà Y Y case a action(s) break case b action(s) break case … action(s) break case n action(s) break N … N case n Y Y N defaultàa tio s …  aseàà : u lệ h ; eakà; aseàà :àààààààà à u lệ h ; eakà; .à.à.à aseàà k: < u lệ h>à; eakà; [default:àààà u lệ h] 35 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG 5.3. C u trúc nhi u lựa chọn C Ví dụ 1: Nhập vào tháng n. Cho biết tháng vừa nhập thu c quý nào? Vẽ l u đồ và viết ch ơng trình BEGIN (n-1)/3<=0 N Y Y - / <= Quýà Quýà N - / <= N - / <= N Th gàsai END Y Y Quýà Quýà #include <stdio.h> void main() { int n; printf(“Nhap n = “); scanf(“%d”, &n); if ((n-1)/3<=0) printf(“Quý 1”); else if ((n-1)/3<=1) printf(“Quý 2”); else if ((n-1)/3<=2) printf(“Quý 3”); else if ((n-1)/3<=3) printf(“Quý 4”); else printf(“ThƠng sai”); } 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG 5.3. C u trúc nhi u lựa chọn C Ví dụ 1: Nhập vào tháng n. Cho biết tháng vừa nhập thu c quý nào? Vẽ l u đồ và viết ch ơng trình BEGIN n x=(n-1)/3 x Case 0 “Quý 1”; break; Case 1 “Quý 2”; break; Case 2 “Quý 3”; break; Case 3 default “Quý 4”; break; “Tháng sai”; END #include <stdio.h> void main() { int n,x; printf(“Nhap n = “); scanf(“%d”, &n); x=(n-1)/3; switch (x) { case 0: printf(“Quý 1”); break; case 1: printf(“Quý 2”); break; case 2: printf(“Quý 3”); break; case 3: printf(“Quý 4”); break; default: printf(“ThƠng sai”); } } 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C 5.4. C u trúc lặp Xét điều kiện TR C khi thực hiện lệnh/khối lệnh Điều kiện lặp Xét điều kiện SAU khi thực hiện lệnh/khối lệnh Yes No Lệnh / Khối lệnh • hile • doà.à.à.à hile • fo 38 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C 5.4.1. L nh lặp while VỬ ếụ 1: Cho nhập số nguyên d ơng n. Tính tổng các số từ 1-n VD n=5 in ra 15 (vì 1+2+3+4+5=15) void main() { int n, s, i; printf(“Nhap n: ”); scanf(“%d”,&n); s=0; i=1; while(i<=n) { s=s+i++; } printf(“Tong=%d”,s); } BEGIN s= ; i= ; N s END i<= Y s=s+i; i++; 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C 5.4.1. L nh lặp while VỬ ếụ2: Cho nhập số nguyên d ơng n. In ra số l n nhất có trong n. VD n=5716 in ra So lon nhat la 7 void main() { int n, so, max=0; printf(“Nhap so nguyen duong”); scanf(“%d”,&n); while(n>0) { so=n%10; if (so>max) max=so; n=n/10; } printf(“So lon nhat la %d”,max); } N a END BEGIN max=0 > = / max=so Y N so=n % 10 so> a Y 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C 5.4.2. L nh do … while Ví dụ: Nhập vào m t số nguyên d ơng n (n>0), nếu nhập sai thì yêu cầu nhập lại. void main() { int n; do { printf("Nhap vao mot so nguyen duong: “); scanf(“%d”,&n); BEGIN } while (!(n>0)); printf("Ban da nhap dung yêu cau”); n } N đ ! > Y g END 41 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C 5.4.2. L nh do … while Ví dụ: Nhập vào m t số nguyên d ơng, nếu nhập sai thì thông báo lỗi và yêu cầu nhập lại. void main() { int n; do { printf("Nhap vao mot so nguyen duong: “); scanf(“%d”,&n); if (!(n>0)) printf(“Phai nhap so duong\n”); } while (!(n>0)); printf("Ban da nhap dung yeu cau”; BEGIN } BEGIN Y Phaià hapà soàduo g n N đ g END ! > N ! > Y N đ g END ! > Y 42 5.4.3. Lệnh for - Sơ đồ hoạt đ ng Khởiàg àgi àt ịà iế àđiềuàkhiể à lệ hàlặpà N Điềuàkiệ à lặp Y Cậpà hậtàgi àt ịà iế àđiềuàkhiể à lệ hàlặpà Lệ h/Khốiàlệ h - Hoạt đ ng t ơng tự nh lệnh while for (<Kh̉i ǵn iếnàđiềuàkhiểnàlệnhàlặp>à;<đìu kịn lặp>; <cập nhật gi àtrịàtrướ àkhiàxétàlạiàđiềuàkiệnàlặpà>)   lệnh/àkhốiàlệnh; 43 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C VỬ ếụ 1: In ra màn hình 10 dòng chữ “Xin chao” //dùng while void main() { int dem = 0; while(dem < 10) { printf("Xin chao\n”); dem++; } } //dùng for void main() END { for (int dem=0; dem<10; dem++) printf("Xin chao\n”); } BEGIN de = N de < de ++ Y Xi à hao 44 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C VỬ ếụ 2: Cho nhập số nguyên d ơng n. Tính tổng các số từ 1-n VD n=5 in ra 15 (vì 1+2+3+4+5=15) void main() { int n, s, i; printf(“Nhap n: ”); scanf(“%d”,&n); s=0; i=1; while(i<n) { s=s+i; i++; } /*dùng for for (int i=0; i<=n; i++) s=s+i; */ printf(“Tong=%d”,s); } BEGIN s= ; i= ; N i<= Y s=s+i; i++; a END 45 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C 5.4.6. Chuy n đ i gi a các l nh lặp - CểuỔ n đ i Ểiữa ềor và wểiệe Ví dụ: In ra màn hình gia trị t 10 đến 20 ngoại trừ số 15. void main() { for (int k<=20; k++; k++) int k=10; (k<=20) { if (k == 15) continue; printf(“%5d”,k); } } void main() { while { } } 46 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C 5.4.6. Chuy n đ i gi a các l nh lặp - CểuỔ n đ i Ểiữa ềor và ếo … wểiệe Ví dụ: In ra màn hình gia trị t 10 đến 20 ngoại trừ số 15 . void main() { k++; for (int k<=20; k++) int k=10; (k<=20) { if (k == 15) continue; cout<<k<<“\t"; } } void main() { do { } } while ; 47 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C 5.4.3. Chuy n đ i gi a các l nh lặp - Chuy n đổi gi a while và do … while Ví dụ: In ra màn hình gia trị t 10 đến 20 ngoại trừ số 15 . void main() { int int k=10; k=10; while (k<=20) { if if (k (k == == 15) 15) continue; continue; cout<<k<<“\t"; cout<<k<<“\t"; k++; } } void main() { do { } } while ; 48 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C i. Viết ch ơng trình cho nhập 1 số nguyên. In ra số l n nhất có trong n. VD: n= 9  9 void main () { int n, so, max=0; //nhập n; tam = n; //tìm ś l n nhất while n>0 { so=n%10; n=n/10; if (so>max) max=so; } } printf(“So lon nhat trong %d la %d”, tam,max); 49 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C ii. Viết ch ơng trình cho nhập 1 số nguyên. In ra chữ số t ơng ứng. VD: n=190  ot hi kho g void main () { int n, so, k=1; //nhập n; //tìm k while (k*10)<=n) k*=10; //Tach so printf(“Chu so tuong ung voi %d la: “, n); while (k>0) { so=n/k; n=n/k; k=k/10; InChuSo(so); } } void InChuSo(int m) { switch (m) { case 0: printf(“khong ”); break; case 1: printf(“mot ”); break; case 2: printf(“hai ”); break; case 3: printf(“ba ”); break; case 4: printf(“bon ”); break; case 5: printf(“nam ”); break; case 6: printf(“sau ”); break; case 7: printf(“bay ”); break; case 8: printf(“tam ”); break; case 9: printf(“chin ”); break; } } 50 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C iii. Viết ch ơng trình cho nhập 3 số nguyên. Tìm số lớn nhì? void main () { int a,b,c, max, mid, min; //nhập 3 ś a,b,c; //tìm ś l n nhất if ((a>=b)&&(a>=c)) max=a; else if ((b>=a)&&(b>=c)) max=b; else max=c; //tìm ś nhỏ nhất if ((a<=b)&&(a<=c)) min=a; else if ((b<=a)&&(b<=c)) min=b; else min=c; //tìm ś l n nhì mid=(a+b+c)-(max+min); } void main () { int a,b,c, mid; //nhập 3 ś a,b,c; //tìm ś l n nhì if ((a-b)*(a-c)<=0) mid=a; else if ((b-a)*(b-c)<=0) mid=b; else mid=c; } 51 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C iv. Viết ch ơng trình cho nhập chiều dài và chiều r ng của nền nhà, kích th c cạnh của viên gạch men lát nền (hình vuông) và kiểu của viên gạch men. Thực hiện lát nền nhà bằng các viên gạch men đư có. 52 5. C U TRÚC ĐI U KHI N TRONG NGÔN NG C ii.Lát gạch nền nhà. void main() { int Row, Col, d, c, canhB=3; char A[MAX][MAX], B[MAX][MAX] = { {'X',' ' ,'X'}, {' ','O',' '}, {'X',' ' ,'X'}}; 0 1 2 3 4 5 6 7 /*à hậpàRo à sốàdò g à 0 1 2 0 0 àColà sốà ột à ủaà ề à h */ 1 1 //àThự àhiệ àl tàgạ h 2 2 3 for (d = 0; d < Row; d++) 4 for (c = 0; c < Col; c++) 5 A[d][c] = B[d%canhB][c%canhB]; 6 7 //à e àkếtà uả 8 for (d = 0; d < Row; d++) … { for (c = 0; c < Col; c++) printf("%c",A[d][c]); printf("\n"); } } 53 6. Đ PH C T P C A GI I THU T 6.1. Đánh giá thời gian chạy của chương trình Th i gian chạy của ch ong trình phụ thu c vào : i. Input cho ch ơng trình ii. Chất l ợng mã sinh ra của ch ơng trình dịch. iii. Trạng thái và tốc đ của các lệnh chạy trên máy. iv. Đ phức tạp th i gian của giải thuật. 54 6. Đ PH C T P C A GI I THU T 6.2. Tiêu chuẩn đánh giá gi i thuật i. Tính đúng đắn ii.Tính đơn giản iii.Tính hiệu quả Thông th ng, để so sánh các thuật toán, ng i ta dựa vào đ phức tạp về th i gian thực thi (đ phức tạp của thuật toán (algorithm complexity)  ước lượng số phép tính cần thực hiện hay Đánh giá độ phức tạp giải thuật 55 6. Đ PH C T P C A GI I THU T 6.2. Tiêu chuẩn đánh giá gi i thu t - Đ phức tạp giải thuật cáng thấp  th i gian thực hiện ch ơng trình cành nhanh và ng ợc lại. - Các đ phức tạp giải thuật th ng gặp: log2n, n, nlog2n, n2, n3, n!, nn 56 6. Đ PH C T P C A GI I THU T 6.3. Quy t c tính đ ph c t p gi i thu t 6.3.1. Quy tắc cộng Nếu T1(N) và T2(N) là th i gian thực hiện của hai đoạn ch ơng trình P1 và P2; và T1(N)=O(f(N)), T2(N)=O(g(N)  th i gian thực hiện của đoạn hai ch ơng trình nối ti p nhau là T(N)=O(max(f(N), g(N))) 6.3.2. Quy tắc nhân Nếu T1(N) và T2(N) là th i gian thực hiện của hai đoạn ch ơng trình P1và P2 và T1(N) = O(f(N)), T2(N) = O(g(N)  th i gian thực hiện của đoạn hai đoạn ch ơng trình đó lồng nhau là T(N) = O(f(N).g(N)) 57 6. Đ PH C T P C A GI I THU T 6.3. Quy t c tính đ ph c t p gi i thu t 6.3.3. Quy tắc tính thời gian chạy i. Mỗi lệnh gán, read, write có giả thiết là O(1). ii. M t dưy lệnh xác định theo quy tắc tổng. iii. Lệnh if là thời gian thực hiện lệnh điều kiện cộng với thời gian kiểm tra điều kiện. iv. Lệnh if … else là thời gian kiểm tra điều kiện cộng với thời gian lớn nhất của 1 trong 2 lệnh rẽ nhánh true và false. v. Vò g lặp là tổng thời gian thực hiện trong thân vòng lặp và thời gian kiểm tra kết thúc vòng lặp. vi. Gọi hà : Nếu ch ơng trình có các thủ tục và không có thủ tục nào là đệ quy thì ta có thể tính thời gian chạy cùng một lúc, bắt đầu từ các thủ tục không gọi đến các thủ tục khác. 58 6. Đ PH C T P C A GI I THU T 6.3. BƠi t p xác đ nh đ ph c t p 6.3.4. BƠi t p 1: Tính đ phức tạp của hàm cho ng i dùng nhập giá trị cho các phần tử của mảng số nguyên A, gồm n phần tử void TaoMang (int A[], int n) { for(int i=0;i<n;i++) { } } printf("Nhap so: "); scanf("%d",&n); 59 6. Đ PH C T P C A GI I THU T 6.3. BƠi t p xác đ nh đ ph c t p 6.3.4. BƠi t p 2: Tính đ phức tạp của hàm in các sổ lẻ có trong mảng số nguyên A, gồm n phần tử void InSoLe(int A[], int n) { for(int i=0;i<n;i++) { } } if(A[i]%2!=0) printf("%5d",A[i]); 60 6. Đ PH C T P C A GI I THU T 6.3. BƠi t p xác đ nh đ ph c t p 6.3.4. BƠi t p 3: Tính đ phức tạp của hàm tính P= 1! + 2! + 3! + ... + n! long TinhP(int n) { long P=0; for(int i=1;i<=n;i++) { long t=1; for(int j=1;j<=i;j++) t=t*j; P=P+t; } return P; } long TinhP(int n) { long P=0; long t=1; for(int i=1;i<n;i++) { t=t*i; P=P+t; } return P; } 61 6. Đ PH C T P C A GI I THU T 6.4. Th c hƠnh Bài toán gà chó. N i dung bài toán nh sau: Vừa gà vừa chó Bó lại cho tròn Đúng ba sáu con M t trăm chân chẵn. i. Viết ch ơng trình tìm tất cả các tr ng hợp bài toán có nghiệm (vét cạn). Trong mỗi tr ng hợp, cho biết số l ợng gà, số l ợng chó? ii. Có thể cải tiến ch ơng trình đang có để giảm đ phức tạp? 62 6. Đ PH C T P C A GI I THU T 6.4. Th c hƠnh Bài toán gà chó. N i dung bài toán nh sau: i. ii. Vừa gà vừa chó Bó lại cho tròn Đúng ba sáu con M t trăm chân chẵn. Viết ch ơng trình tìm tất cả các tr ng hợp? Có thể cải tiến ch ơng trình đang có để giảm đ phức tạp? void main() { int ga, cho; printf("Dap an: co"); for (cho=0;cho<=36;cho++) for (ga=0;ga<=36;ga++) if ((ga*2 + cho*4 == 100) &&(ga+cho==36)) printf(“Ga=%d, Cho=%d\n", ga, cho); } void main() { int ga, cho; printf("Dap an: co"); 25 ;cho++) for (cho=0;cho<= 36 { ga=36-cho; if (ga*2 + cho*4==100) printf(“Ga=%d, Cho=%d\n", ga, cho); } 63 } 6. Đ PH C T P C A GI I THU T 6.5. BƠi t p v nhƠ Cài đặt hàm và tính đ phức tạp cho các hàm sau sao cho đ phức tạp là thấp nhất có thể 6.5.1. Bài toán trăm trâu. N i dung bài toán nh sau: Trăm trâu trăm cỏ Trâu đứng ăn năm Trâu nằm ăn ba Trâu già ăn m t Xác định số l ợng trâu mỗi loại? 6.5.2. Tìm những tam giác có 3 cạnh là số nguyên có kích th c nằm trong khoảng từ 1-10 và 3 cạnh đó tạo thành tam giác vuông? 6.5.2. Tính S, biết rằng S= x x2 + 1+2 + x3 1+2+3 +...+ xn + + +…+ 64 N I DUNG MỌN H C - Ch ơng 1: Ôn tập về Ngôn ngữ lập trình - Chương 2: Đệ quy - Chương 3: Các giải thuật tìm kiếm trên mảng 1 chiều - Chương 4: Các giải thuật sắp xếp trên mảng 1 chiều - Chương 5: Danh sách liên kết đ ng (Linked List) - Chương 6: Ngăn xếp (Stack) - Chương 7: Hàng đợi (Queue) trên mảng m t chiều) - Chương 8: Cây (Tree) - Chương 9: Bảng băm (Hash Table) Ch ng 2 Đ QUY (Recursion) M C TIểU i. Giải thích đ ợc đệ quy là gì ii. Phân loại đ ợc các loại đệ quy iii. Biết cách giải quyết 1 tác vụ h ng đệ quy iv. Biết cách hiện thực hàm đệ quy v. Giải thích đ ợc cách thực hiện của m t hàm đệ quy 67 N I DUNG CH NG 2 1. Tổng quan 2. Đệ quy tuyến tính 3. Đệ quy nhị phân 4. Đệ quy phi tuyến 5. Đệ quy hỗ t ơng 1. T NG QUAN 1.1. Khái ni m M t hàm đ ợc gọi có tính đệ quy nếu trong thân của hàm đó có lệnh gọi lại chính nó m t cách t ng minh hay tiềm ̉n. 1.2. Phân loại đ quy i. Đệ quy tuyến tính. ii. Đệ quy nhị phân. iii. Đệ quy phi tuyến. iv. Đệ quy hỗ t ơng. 69 2. Đ QUY TUÝN TệNH • Trong thân hàm có duy nhất m t l i gọi hàm gọi lại chính nó m t cách t ng minh. <Kỉu d̃ liệu h̀m> TenHam (<danh śch tham ś>) { //B1: Kỉm tra điều kiện dừng if (điều kiện dừng) { //Tr̉ về gí tṛ hay ḱt th́c công việc } /*B2: Tḥc hiện ṃt ś công việc (thường l̀ gọi đệ quy)*/ . . . TenHam (<danh śch tham ś>); } 70 2. Đ quy tuy n tí́nh Ví dụ 1: Tính S ( n)  1  2  3    n • Quy tắc (công thức) tính: Ta có: S(n) =1+2+3+ … + (n-2) + (n-1) + n Do đó: S(n-1)=1+2+3+ … + (n-2) + (n-1) Tương tự: S(n-2)=1+2+3+ … + (n-2) ..... Suy ra quy tắc (công thức) tính: S(n)=S(n-1)+n; • Điều kiện dừng: S(1) = 1 Giả sử với n=4: S(4) S(3) S(2) S(1) = = = = S(3) + 4 S(2) + 3 S(1)+ 2 1 71 2. Đ quy tuy n tí́nh V́ ḍ à:àT hà • C iàđặt: S ( n)  1  2  3    n long TongS (int n) { //B1: Kiểm tra đìu kịn d ng if(n==0) // hay if(n==1) return 0; // return 1; // B2: gọi đ̣ quy return ( TongS(n-1) + n ); } 72 2. Đ quy tuy n tí́nh Ví dụ 2: Tính P ( n)  n! • Quy tắc (công thức) tính: Ta có : P(n) = 1 Do đó : P(n-1) = 1 T ơng tự: P(n-2) = 1 ... X 2 X 3 X … X (n-2) X (n-1) X n X 2 X 3 X … X (n-2) X (n-1) X 2 X 3 X … X (n-2) Suy ra quy tắc (công thức) tính: P(n) = P(n-1) X n; • Điều kiện dừng: S(1) = 1 • Cài đặt long GiaiThua (int n) { //B1: Kiểm tra đìu kịn d ng if(n==1) return 1; // B2: gọi đ̣ quy return (GiaiThua (n-1) * n ); } 73 .àĐệ u àtu ́ àí́ h Cách hoạt đ ng hàm đệ quy • Ví dụ 2: tính P(n)? v i n=5 long GiaiThua (int n) { //B1:Kiểm tra đìu kịn d ng if(n==1) return 1; // B2: gọi đ̣ quy return (GiaiThua(n-1)*n); } void main() { int n=5; printf(“%d”,GiaiThua(n)); } main() n=5; GiaiThua(n) 5 GiaiThua(5) 120 n=5; GiaiThua(n-1)*n GiaiThua(4) 4 24 n=4; GiaiThua(n-1)*n 3 GiaiThua(3) n=3; GiaiThua(n-1)*n 6 GiaiThua(2 2 ) n=2; GiaiThua(n-1)*n 2 74 1 GiaiThua(1) n=1; return 1; 1 2. Đ quy tuy n tí́nh • Ví dụ 3: Cho mảng m t chiều các số nguyên. Viết hàm tính tổng cho các số chẵn trong mảng bằng ph ơng pháp đệ quy. Ta có hình ảnh mảng a có n phần tử nh sau: 0 1 n-2 n-1 12 43 … 23 44  Quy tắc (công thức tính): Ta có: tong= a[1] + a[2] + … + a[n-2] +a[n-1] Suy ra quy tắc (công thức) tính: tong = tong(n-1) X n;  Điều kiện dừng: n=0 (phần tử cuối của của mảng có chỉ số là 0)  Cài đặt: long Tong(int a[], int n) { } //B1: Kiểm tra đìu kịn d ng if (n==0) return 0; // B2: gọi đ̣ quy if(a[n-1]%2==0) return Tong(a,n-1)+a[n-1]; return Tong(a,n-1); 75 3. Đ QUY NH PHỂN t Trong thân của hàm có hai l i gọi hàm gọi lại chính nó m t cách ng minh. <Kỉu d̃ liệu h̀m> TenHam (<danh śch tham số >) //B1: Kiểm tra điều kiện dừng { if (điều kiện dừng) { ... //Tr v̀ giƠ tṛ hay k t th́c công vịc } // B2: gọi đệ quy //Tḥc hiện ṃt sốcông việc (ńu ć) //Gi i quy t vấn đ̀ nhỏ h n ... TenHam (<danh śch tham số >); //Tḥc hiện ṃt ś công việc (ńu ć) //Gi i quy t vấn đ̀ c̀n ḷi ... TenHam (<danh śch tham số >); } //Tḥc hiện ṃt sốcông việc (ńu ć) 76 3. Đ quy nh phơn Ví dụ: Tính sô hạng th n của dưy Fibonaci đ ợc định nghĩa nh sau: f1 = f0 =1 ; fn = fn-1 + fn-2 ; • Điều kiện dừng: f • Cài đặt à=àf (n>1) à=à . long Fibonaci (int n) //B1: Kiểm tra đìu kịn d ng { if(n==0 || n==1) return 1; // B2: gọi đ̣ quy return Fibonaci(n-1) + Fibonaci(n-2); } 77 4. Đ QUY PHI TUÝN Trong thân của hàm có l i gọi hàm gọi lại chính nó đ ợc đặt bên trong vòng lặp. <Kiểu dữ lịu hơm> TenHam (<danh sƠch tham sô>) { for (int i = 1; i<=n; i++) { //Tḥc hiện ṃt sốcông việc (ńu ć) if (đìu kịn d ng) { . . . //Trảvê gia tṛ hay k t th́c công vịc } } } else { //Tḥc hịn m t sô công vịc (n u ć) TenHam (<danh sƠch tham sô>); } 78 4. Đ quy phi tuy n Ví dụ: Tính số hạng thứ n của dưy {Xn} đ ợc định nghĩa nh sau: X = ; X =à X +à - X +à…à+à X - - Điều kiện dừng: X(0) = 1 - Cài đặt ; ≥ long TinhXn (int n) { if(n==0) return 1; long s = 0; for (int i=1; i<=n; i++) s = s + i * i * TinhXn(n-i); return s; } 79 5. Đ QUY H T NG Trong thân của hàm này có l i gọi hàm đến hàm kia va trong thân của hàm kia có l i gọi hàm t i hàm này. 80 5. Đ quy h t ng <Kỉu d̃ liệu h̀m> TenHam1 (<danh śch tham ś>) { //Tḥc hiện ṃt ś công việc (ńu ć) … TenHam2 (<danh śch tham ś>); //Tḥc hiện ṃt ś công việc (ńu ć) } <Kỉu d̃ liệu h̀m> TenHam2 (<danh śch tham ś>) { //Tḥc hiện ṃt ś công việc (ńu ć) … TenHam1 (<danh śch tham ś>); //Tḥc hiện ṃt ś công việc (ńu ć) } 81 5. Đ quy h t ng Ví dụ: Tính số hạng thứ n của hai dưy {Xn}, {Yn} đ ợc định nghĩa nh sau: X0 =Y0 =1 ; Xn = Xn-1 + Yn-1; (n>0) Yn = n2Xn-1 + Yn-1; (n>0) - Điều kiện dừng: - Cài đặt: X(0) = Y(0) = 1 long TinhXn (int n) { if(n==0) return 1; return TinhXn(n-1) + TinhYn(n-1); } long TinhYn (int n) { if(n==0) return 1; return n*n*TinhXn(n-1) + TinhYn(n-1); } 82 6. BÀI T P Tính P(n)  1.3.5(2n  1) ,v i n0 Tính S (n)  1  3  5    (2  n  1) ,v i n0 n 1 Tính S (n)  1  2  3  4    (1) n ,v i n0 Tính S (n)  1  1.2  1.2.3    1.2.3 n , v i n0 2 2 2 2 Tính S (n)  1  2  3    n ,v i n0 Tìm c số chung l n nhất của hai số nguyên d ơng a và b. Tìm giá trị X có xuất hiện trong mảng 1 chiều hay không? Có trả về true, không trả về false. viii. Lần l ợt viết hàm xuất ra giá trị đang có trong mảng 1 chiều theo 2 cách xuôi (từ trái sang phải) và ng ợc (từ phải sang trái). ix. Viết hàm tính tổng các số lẻ có trong mảng 1 chiều các số nguyên. x. Tính tổng các phần tử trong mảng 2 chiều các số nguyên i. ii. iii. iv. v. vi. vii. 83 N I DUNG MỌN H C - Ch ơng 1: Ôn tập về Ngôn ngữ lập trình - Chương 2: Đệ quy - Chương 3: Các giải thuật tìm kiếm trên mảng 1 chiều - Chương 4: Các giải thuật sắp xếp trên mảng 1 chiều - Chương 5: Danh sách liên kết đ ng (Linked List) - Chương 6: Ngăn xếp (Stack) - Chương 7: Hàng đợi (Queue) trên mảng m t chiều) - Chương 8: Cây (Tree) - Chương 9: Bảng băm (Hash Table) Ch ng 3 CÁC GI I THU T TỊM KÍM TRểN M NG 1 CHI U M C TIểU i. Hiểu và giải thích đ ợc các giải thuật tìm kiếm phần tử trên mảng 1 chiều ii. Cài đặt thành công các giải thuật tìm kiếm phần tử trên mảng 1 chiều 86 N I DUNG CH NG 3 1. Tìm kiếm tuyến tính 2. Tìm kiếm nhị phân Nhu cầu tìm kiếm trên máy tính khi dữ liệu đ ợc l u trữ trong mảng 1 chiều - Cho mảng 1 chiều gồm n phần tử a0, a1, a2…, an-1. Tìm phần t có khoá bằng X trong m ng? 1. Tìm Ki m Tuy n Tính - Ý tưởng: So sánh X lần l ợt v i phần tử thứ 0, thứ 1,… của mảng a cho đến khi gặp đ ợc khóa cần tìm, hoặc tìm hết mảng mà không thấy. - Các bước ti n hành •B c 1: Khởi ǵn i=0; • B c 2: So śnh a[i] với gí tṛ x cần tìm, ć 2 kh̉ năng ▪ a[i] == x tìm thấy x. Dừng; ▪ a[i] != x sang bước 3; •B c 3: i=i+1 //Xét típ phần tử ḱ típ trong m̉ng Ńu i==n: H́t m̉ng. Dừng; Ngược lại: Lặp lại bước 2; 1. Tìm Ki m Tuy n Tính  Cài đặt Hàm trả về 1 nếu tìm thấy, ng ợc lại trả về 0 int LinearSearch(int a[],int n, int x) { int i=0; while((i<n)&&(a[i]!=x)) i++; if(i==n) return 0; //không tìm thấy x else } return 1; //Tìm thấy 1. Tìm Ki m Tuy n Tính  Minh Họa Gi i thuật Tìm Ki m Tuy n Tính X=6 Tìm thấy 6 tại vị trí 4 i 2 8 5 1 6 4 6 0 1 2 3 4 5 6 int LinearSearch(int a[],int n, int x) { int i=0; while((i<n)&&(a[i]!=x)) i++; if(i==n) return 0; //không tìm thấy else return 1; //Tìm thấy } 1. Tìm Ki m Tuy n Tính  Minh Họa Gi i thuật Tìm Ki m Tuy n Tính X=10 i=7, không tìm thấy i 2 8 5 1 6 4 6 0 1 2 3 4 5 6 int LinearSearch(int a[],int n, int x) { int i=0; while((i<n)&&(a[i]!=x)) i++; if(i==n) return 0; //không tìm thấy else return 1; //Tìm thấy } 2. Tìm Ki m Nh Phơn 2.1. Giới thi u - Đ ợc áp dụng trên mảng đư có thứ tự. - Ý tưởng: • Giả xử ta xét mảng có thứ tự tăng, khi ấy ta có ai-1 <= ai <= ai+1 • Nếu X>ai thì X chỉ có thể xuất hiện trong đoạn [ai+1, an-1] • Nếu X<ai thì X chỉ có thể xuất hiện trong đoạn [a0, ai-1] • Ýt ng của giải thuật là tại mỗi b c ta so sánh X v i phần tử đứng giữa trong dưy tìm kiếm hiện hành, dựa vào kết quả so sánh này mà ta quyết định gi i hạn dưy tìm kiếm nữa d i hay nữa trên của dưy tìm kiếm hiện hành. 2. Tìm Ki m Nhị Phân 2.2. Gi i thuật Tìm Ki m Nhị Phân Giả sử dưy tìm kiếm hiện hành bao gồm các phần tử nằm trong aleft, aright, các b c của giải thuật nh sau: • Bước 1: left = 0; right = n-1; • Bước 2: ▪ mid =(left+right)/2;//chỉ số ph/tử giữa dãy hiện hành ▪ So śnh a[mid] với x. Ć 3 kh̉ năng • a[mid]= x: tìm thấy. Dừng • a[mid]> x: Right=mid-1; // thu hẹp bên phải dãy • a[mid]< x: Left= mid+1; // thu hẹp bên trái dãy • Bước 3: • Ńu Left<=Right ;//còn phần tử trong dãy hiện hành + Lặp lại bước 2 • Ngược lại: Dừng 2. Tìm Ki m Nhị Phân 2.3. Cài đặt Gi i thuật tìm nhị phân Hàm trả về giá trị 1 nếu tìm thấy, ng ợc lại hàm trả về giá trị 0 int BinarySearch(int a[],int n,int x) { int left, right, mid; left=0; right=n-1; do { mid=(left+right)/2; if(a[mid]==x) return 1; else if(a[mid]<x) left=mid+1; else right=mid-1; }while(left<=right); return 0; } 2. Tìm Ki m Nhị Phân 2.4. Minh Họa Gi i thuật Tìm Nhị Phân (giá trị cần tìm X=2) int BinarySearch(int a[],int n,int x) { int left, right, mid; left=0; right=n-1; do { mid=(left+right)/2; if(a[mid]==x) return 1; else if(a[mid]<x) left=mid+1; else right=mid-1; }while(left<=right); return 0; } Tìm thấy 2 tại ṿ trí 1 X=2 M L R 1 2 4 6 7 9 10 0 1 2 3 4 5 6 2. Tìm Ki m Nhị Phân 2.4. Minh Họa Gi i thuật Tìm Nhị Phân (giá trị cần tìm X=-1) int BinarySearch(int a[],int n,int x) { int left, right, mid; left=0; right=n-1; do { mid=(left+right)/2; if(a[mid]==x) return 1; else if(a[mid]<x) left=mid+1; else right=mid-1; }while(left<=right); return 0; } X=-1 M L R 1 2 4 6 7 9 10 0 1 2 3 4 5 6 L=0 R=-1 => L<R => dừng khi không tìm thấy X=-1 2. Tìm Ki m Nhị Phân 2.5. Cài đặt gi i thuật Tìm nhị phân: Gọi hàm tìm nhị phân void main() { int a[100], n, kq, x; // nhập ś phần t n // gọi hơm nhập m ng 1 chìu // nhập giƠ tṛ cần tìm x kq = BinarySearch(a,n,x); //hoặc if (BinarySearch(a,n,x)==1) if(kq==1) printf(“tìm thấy”); else printf(“không tìm thấy”); } int BinarySearch(int a[],int n,int x) { } int left, right, mid; left=0; right=n-1; do { mid=(left+right)/2; if(a[mid]==x) return 1; else if(a[mid]<x) left=mid+1; else right=mid-1; }while(left<=right); return 0; 2. Tìm Ki m Nhị Phân 2.5. Bài tập áp dụng 3 5 6 8 12 17 19 0 1 2 3 4 5 6 - Ghi kết quả chạy từng b c khi tìm X=19  B1: l=0, r=6, mid=(l+r)/2, A[mid] = 8, 8<19  B2: l= mid+1=4, mid=(l+r)/2=5, A[mid] =17<19  B3: l=mid+1=6, mid=(l+r)/2=6, A[mid]=19 =X dừng 2. Tìm Ki m Nhị Phân 2.5. Bài tập áp dụng (biểu diễn cách trình bày khác) 3 5 6 8 12 17 19 0 1 2 3 4 5 6 - Ghi kết quả chạy từng b L n 1 2 3 L 0 4 6 R 6 6 6 M 3 5 6 c khi tìm X=19 A[M] 8 17 19 Dừng sau khi tìm thấy X 2. Tìm Ki m Nhị Phân 2.6. Thực hành i. Trình bày các b c tìm X=35 trong mảng sau: ii. Thực hiện t ơng tự khi X=6 3 5 7 8 12 17 19 20 24 27 31 36 39 40 42 48 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Lần L R M A[M] Lần L R M A[M] 1 0 15 7 20 1 0 15 7 20 2 8 15 11 36 2 0 6 3 8 3 8 10 9 27 3 0 2 1 5 4 10 10 10 31 4 2 2 2 7 5 11 10 10 31 5 2 1 1 5 Dừng do L=11 >R=10  Không thấy X=35 Dùng do L=2 >R=1  Không thấy X=6 15 N I DUNG MỌN H C - Ch ơng 1: Ôn tập về Ngôn ngữ lập trình - Chương 2: Đệ quy - Chương 3: Các giải thuật tìm kiếm trên mảng 1 chiều - Chương 4: Các giải thuật sắp xếp trên mảng 1 chiều - Chương 5: Danh sách liên kết đ ng (Linked List) - Chương 6: Ngăn xếp (Stack) - Chương 7: Hàng đợi (Queue) trên mảng m t chiều) - Chương 8: Cây (Tree) - Chương 9: Bảng băm (Hash Table) Ch ng 4 CÁC GI I THU T S P X́P TRểN M NG 1 CHI U M C TIểU i. Hiểu và giải thích đ ợc các giải thuật sắp xếp trên mảng 1 chiều ii. Nắm vững, minh họa và tính toán đ ợc các phép gán (hoán vị) các giải thuật sắp xếp cơ bản trên mảng m t chiều iii. Cài đặt thành công các giải thuật sắp xếp trên mảng 1 chiều 104 N I DUNG i. Đổi chỗ trực tiếp – Interchange Sort ii. Chọn trực tiếp – Selection Sort iii. Chèn trực tiếp – Insertion Sort iv. Nổi bọt – Bubble Sort v. Giải thuật lắc - Shaker Sort (*) vi. Sắp xếp nhanh - Quick Sort vii. Sắp xếp tr n trực tiếp - Merge Sort (*) viii. Sắp xếp v i đ dài b c giảm dần - Shell Sort (*) ix. Sắp xếp vun đống - Heap Sort (*) x. Sắp xếp theo cơ số - Radix Sort (*) xi. Sắp xếp bằng đếm phân khối - Distribution Counting (*) xii. Sắp xếp tuyến tính – FlashSort (*) (*) Sinh viên tự nghiên cứu các giải thuật v và từ vii-ồii  Khái ni m ắngh ch th Ằ - Xét m t mảng các số a0, a1, …, an. - Nếu có i<j và ai > aj, thì ta gọi đó là m t nghịch thế. - Mảng ch a sắp xếp sẽ có nghịch thế. 2 3 5 9 7 - Mảng đư có thứ tự sẽ không chứa nghịch thế. Khi đó a0 sẽ là phần tử nhỏ nhất rồi đến a1, a2, …, an v i a0  a1  …  an 2 3 5 7 9 1. Đ i Ch Tr c Ti p ậ Interchange Sort - Ý tưởng: Xuất phát từ đầu dưy, tìm tất các các nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ 2 phần tử trong cặp nghịch thế. Lặp lại xử lý trên v i phần tử kế trong dưy. 1. Đ i Ch Tr c Ti p ậ Interchange Sort • Các bước ti n hành - B - B - B c 1: i = 0; // bắt đầu từ đầu dãy c 2: j = i+1; //tìm các nghịch thế với a[i] c 3: Trong khi j < n tḥc hịn N u a[i]> a[j] //xét cặp a[i], a[j] Swap(a[i],a[j]); - B c 4: i = i+1; N u Ng j = j+1; i < N-1: Lặp ḷi B c ḷi: D ng. c 2. 1. Đ i Ch Tr c Ti p ậ Interchange Sort • Minh họa lại gi i thuật j 1 12 0 i 2 1 8 2 5 3 1 6 4 4 5 6 15 7 1. Đ i Ch Tr c Ti p ậ Interchange Sort • Minh họa lại gi i thuật j 1 12 2 8 5 2 6 4 15 0 i 1 2 3 4 5 6 7 0 1. Đ i Ch Tr c Ti p ậ Interchange Sort • Minh họa lại gi i thuật j 1 2 4 12 8 5 6 4 15 0 1i 2 3 4 5 6 7 0 1. Đ i Ch Tr c Ti p ậ Interchange Sort • Minh họa lại gi i thuật j 1 2 4 5 12 8 6 5 15 0 1 2 i 3 4 5 6 7 0 1. Đ i Ch Tr c Ti p ậ Interchange Sort • Minh họa lại gi i thuật 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 1. Đ i Ch Tr c Ti p ậ Interchange Sort • Một cách trình bày dạng b ng i j A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] 2 8 5 1 6 4 15 0 1 12/2 2/12 8 5 1 6 4 15 0 2 2 12 8 5 1 6 4 15 0 3 2 12 8 5 1 6 4 15 0 4 2/1 12 8 5 1/2 6 4 15 0 5 1 12 8 5 2 6 4 15 0 6 1 12 8 5 2 6 4 15 0 7 1 12 8 5 2 6 4 15 1 2 1 12/8 8/12 5 2 6 4 15 1 3 1 8/5 12 5/8 2 6 4 15 1 4 1 5/2 12 8 2/5 6 4 15 1 5 1 2 12 8 5 6 4 15 1 6 1 2 12 8 5 6 4 15 1 7 1 2 12 8 5 6 4 15 1. Đ i Ch Tr c Ti p ậ Interchange Sort • Một cách trình bày khác i j A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] 1 7 1 2 12 8 5 6 4 15 2 3 1 2 12/8 8/12 5 6 4 15 2 4 1 2 8/5 12 5/8 6 4 15 2 5 1 2 5 12 8 6 4 15 2 6 1 2 5/4 12 8 6 4/5 15 2 7 1 2 4 12 8 6 5 15 3 4 1 2 4 12/8 8/12 6 5 15 3 5 1 2 4 8/6 12 6/8 5 15 3 6 1 2 4 6/5 12 8 5/6 15 3 7 1 2 4 5 12 8 6 15 4 5 1 2 4 5 12/8 8/12 6 15 4 6 1 2 4 5 8/6 12 6/8 15 4 7 1 2 4 5 6 12 8 15 5 6 1 2 4 5 6 12/8 8/12 15 5 7 1 2 4 5 6 8 12 15 6 7 1 2 4 5 6 8 12 15 1. Đ i Ch Tr c Ti p ậ Interchange Sort • Cài Đặt void Swap(int &x,int &y) { int tam = x; x = y; y = tam; } void InterchangeSort(int a[], int n) int i, j; { for (i = 0 ; i<n-1 ; i++) for (j = i+1; j < n ; j++) if(a[j ]< a[i]) //Tìm thấy 1 nghịch thế Swap(a[i], a[j]); } 1. Đ i Ch Tr c Ti p ậ Interchange Sort - Ðánh giá gi i thuật Số l ợng các phép so sánh xảy ra không phụ thu c vào tình trạng của dãy số ban đầu, nh ng số l ợng phép hoán vị thực hiện tùy thu c vào kết quả so sánh, có thể c l ợng trong từng tr ng hợp nh sau: 117 1. Đ i Ch Tr c Ti p ậ Interchange Sort • Bài tập áp dụng: Trình bày quá trình sắp xếp mảng sau bằng giải thuật Interchange Sort i. n=6 9 8 7 4 5 6 ii. n=7 9 8 7 6 5 4 3 2. Ch n Tr c Ti p ậ Selection Sort 2.1. Ý t ởnỂ - Chọn phần tử nhỏ nhất trong n phần tử trong dưy hiện hành ban đầu. - Đ a phần tử này về vị trí đầu dưy hiện hành - Xem dưy hiện hành chỉ còn n-1 phần tử của dưy hiện hành ban đầu • Bắt đầu từ vị trí thứ 2; • Lặp lại quá trình trên cho dưy hiện hành... đến khi dưy hiện hành chỉ còn 1 phần tử 2. Ch n Tr c Ti p ậ Selection Sort 2.2. Các b ớẾ Ếủa Ểiải tểu t Ếểọn trựẾ ti p - B c 1: i = 0; - B c 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n-1] - B c 3 : Đổi chỗ a[min] và a[i] - B c 4 : Nếu i < n-1 thì i = i+1; Lặp lại B Ng ợc lại: Dừng. c 2; 2. Ch n Tr c Ti p ậ Selection Sort 2.3. Cài Đặt Ểiải tểu t Cểọn TrựẾ Ti p void SelectionSort(int a[],int n ) { int min,i,j; for(i=0;i<n-1;i++) { min = i; for(j = i+1; j <n ; j++) if (a[j ] < a[min]) min=j;//lưu vtrí phần tử hiện nhỏ nhất } } Swap(a[min],a[i]); 2. Ch n Tr c Ti p ậ Selection Sort 2.4. Minh Họa Ểiải tểu t Cểọn TrựẾ Ti p i = 0;min=0; min=1;j=1; j=4; i=0; Vị (min)= nhất  trỬ A[min] =nhỏ 2 >> A[j] ==12  A[min] 12 A[j]trong A[min]= 12 lại  cập cập nhật nhật lại min min == jj == 14  void SelectionSort(int a[],int n ) { int min,i,j; for(i=0;i<n-1;i++) min = i; { for(j = i+1; j <n ; j++) if (a[j ] < a[min]) min=j; Swap(a[min],a[i]); } } đoạn [0,7]= 0 Swap(a[0],a[min]) a[4]) Swap(a[i], min i 12 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 2. Ch n Tr c Ti p ậ Selection Sort 2.4. Minh Họa Ểiải tểu t Cểọn TrựẾ Ti p void SelectionSort(int a[],int n ) int min,i,j; { for(i=0;i<n-1;i++) min = i; { for(j = i+1; j <n ; j++) if (a[j ] < a[min]) min=j; Swap(a[min],a[i]); } } i = 1; min=1; j=i+1=2;  A[min] = 2 Swap(a[1],a[min]) a[1]) Swap(a[i], min 1 2 8 5 12 6 4 15 0 1 2 3 4 5 6 7 i j 2. Ch n Tr c Ti p ậ Selection Sort 2.4. Minh Họa Ểiải tểu t Cểọn TrựẾ Ti p = 2; 2; min=2; min=3; j=i+1=3; j=6; ii =  A[min] A[min] == 85 > A[j]= 4   A[min] min = 6= 8 > A[j]=5   min A[min]  = 3= 4  A[min] = 5 void SelectionSort(int a[],int n ) int min,i,j; { for(i=0;i<n-1;i++) { min = i; for(j = i+1; j <n ; j++) if (a[j ] < a[min]) min=j; Swap(a[min],a[i]); } } Swap(a[2],a[min]) a[6]) Swap(a[i], min 1 0 2 1 i 8 5 12 2 3 4 j 6 5 4 6 15 7 2. Ch n Tr c Ti p ậ Selection Sort 2.5. Minh Họa Ểiải tểu t Cểọn TrựẾ Ti p ế ới ếạnỂ bảnỂ i min 0 0 0 0|1 1 12|2 0 1 2 0 j A[min] A[j] A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] 12 2 8 5 1 6 4 15 2 12 2 8 5 1 6 4 15 2 8 12 2 8 5 1 6 4 15 1 3 2 5 12 2 8 5 1 6 4 15 0 1|4 4 2|1 1 12 2 8 5 1 6 4 15 0 4 5 1 6 12 2 8 5 1 6 4 15 0 4 6 1 4 12 2 8 5 1 6 4 15 0 4 7 1 15 12|1 2 8 5 12|1 6 4 15 1 1 2 2 8 1 2 8 5 12 6 4 15 1 1 3 2 5 1 2 8 5 12 6 4 15 1 1 4 2 12 1 2 8 5 12 6 4 15 1 1 5 2 6 1 2 8 5 12 6 4 15 1 1 6 2 4 1 2 8 5 12 6 4 15 1 1 7 2 15 1 2 8 5 12 6 4 15 12 2. Ch n Tr c Ti p ậ Selection Sort 2.5. Minh Họa Ểiải tểu t Cểọn TrựẾ Ti p ế ới ếạnỂ bảnỂ i j A[min] A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] 1 7 2 1 2 8 5 12 6 4 15 2 2|3 3 8|5 5 1 2 8 5 12 6 4 15 2 3 4 5 12 1 2 8 5 12 6 4 15 2 3 5 5 6 1 2 8 5 12 6 4 15 2 6 6 4 4 1 2 8 5 12 6 4 15 2 6 7 4 15 1 2 4 5 12 6 8 15 3 3 4 5 12 1 2 4 5 12 6 8 15 3 3 5 5 6 1 2 4 5 12 6 8 15 3 3 6 5 8 1 2 4 5 12 6 8 15 3 3 7 5 15 1 2 4 5 12 6 8 15 5 12|6 6 1 2 4 5 12 6 8 15 4 5 6 6 8 1 2 4 5 12 6 8 15 4 5 7 6 15 1 2 4 5 12|6 6|12 8 15 5 5|6 6 6|8 8 1 2 4 5 6 12 8 15 5 6 7 8 15 1 2 4 5 6 12|8 8|12 15 6 6 7 12 15 1 2 4 5 6 8 12 15 4 min 4|5 A[j] 2. Ch n Tr c Ti p ậ Selection Sort 2.6. Đánể giá Ểiải tểu t Cểọn TrựẾ Ti p - Ðối v i giải thuật chọn trực tiếp, có thể thấy rằng l ợt thứ i, bao gi cũng cần (n-i) lần so sánh để xác định phần tử nhỏ nhất hiện hành. - Số l ợng phép so sánh này không phụ thu c vào tình trạng của dãy số ban đầu, do vậy trong mọi tr ng hợp có thể kết luận: T ườ g hợp Số lầ àsoàs h Số phép gán Tốt hất n(n-1)/2 0 Xấu hất n(n-1)/2 3n(n-1)/2 127 3. Chèn Tr c Ti p ậ Insertion Sort 3.1. Ý t ởnỂ - Giả sử có m t dưy a0, a1, ... , an-1 trong đó i phần tử đầu tiên a0 , a1 , ... , ai-1 đư có thứ tự. - Tìm cách chèn phần tử ai vào vị trí thích hợp của đoạn đư đ ợc sắp để có dưy m i a0 , a1,... , ai tr nên có thứ tự. Vị trí này chính là vị trí giữa hai phần tử ak-1 và ak thỏa ak-1 < ai < ak (1≤k≤i). 3. Chèn Tr c Ti p ậ Insertion Sort 3.2. Giải tểu t - Bước 1: i = 1; //gi s có đọn a[1] đã đ c sắp - Bước 2: Tìm ṿ trí pos thích h p trong đọn a[1] đ n a[i-1] để chèn a[i] vào x = a[i]; - Bước 3: Dời chỗ các phần t t a[pos] đ n a[i-1] sang ph i 1 ṿ trí để dành chổ cho a[i] - Bước 4: a[pos] = x; - Bước 5: i = i+1; //có đọn a[1]..a[i] N u i < n : Lặp ḷi B Ng c ḷi : D ng c 2 đã đ c sắp 3. Chèn Tr c Ti p ậ Insertion Sort 3.3. Cài đặt void InsertionSort(int d, int n ) { int pos, i; int x;/* l u giƠ tṛ a[i] trƠnh ḅ ghi đè khi dời chỗ for(i=1; i<n; i++) //đọn a[0] đã sắp { x = a[i]; pos = i-1; cƠc phần t . */ // tìm ṿ trí chèn x while((pos >= 0)&&(a[pos] > x)) {/*k t h p dời chỗ cƠc phần t s đ́ng sau x a[pos+1] = a[pos]; pos--; } } } a[pos+1] = x; // chèn x vơo dãy trong dãy m i */ 3. Chèn Tr c Ti p ậ Insertion Sort 3.4. Minể Họa Ểiải tểu t Insertion Sort 12 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 void InsertionSort(int d, int n ) { int pos, i; int x; for(i=1; i<n; i++) { x = a[i]; pos = i-1; while((pos >= 0)&&(a[pos] > x)) { a[pos+1] = a[pos]; pos--; } a[pos+1] = x; } } 3. Chèn Tr c Ti p ậ Insertion Sort 3.4. Minể Họa Ểiải tểu t Insertion Sort Insert a[1] into (0,0) pos 2 12 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 i x void InsertionSort(int d, int n ) int pos, i, x; { for(i=1; i<n; i++) { x = a[i]; pos = i-1; while((pos >= 0)&&(a[pos] > x)) { a[pos+1] = a[pos]; pos--; }//end while a[pos+1] = x; }//end for }//end function 3. Chèn Tr c Ti p ậ Insertion Sort 3.4. Minể ểọa Ểiải tểu t Insertion Sort Insert a[2] into (0, 1) pos 2 8 12 8 5 1 6 4 15 0 1 2 3 4 5 6 7 i x void InsertionSort(int d, int n ) int pos, i, x; { for(i=1; i<n; i++) { x = a[i]; pos = i-1; while((pos >= 0)&&(a[pos] > x)) { a[pos+1] = a[pos]; pos--; }//end while a[pos+1] = x; }//end for }//end function 3. Chèn Tr c Ti p ậ Insertion Sort 3.4. Minể ểọa Ểiải tểu t Insertion Sort Insert a[3] into (0, 2) pos 2 5 8 12 5 1 6 4 15 0 1 2 3 4 5 6 7 i x void InsertionSort(int d, int n ) int pos, i, x; { for(i=1; i<n; i++) { x = a[i]; pos = i-1; while((pos >= 0)&&(a[pos] > x)) { a[pos+1] = a[pos]; pos--; }//end while a[pos+1] = x; }//end for }//end function 3. Chèn Tr c Ti p ậ Insertion Sort 3.4. Minể ểọa Ểiải tểu t Insertion Sort Insert a[4] into (0, 3) pos 2 1 5 8 12 1 6 4 15 0 1 2 3 4 5 6 7 i x void InsertionSort(int d, int n ) int pos, i, x; { for(i=1; i<n; i++) { x = a[i]; pos = i-1; while((pos >= 0)&&(a[pos] > x)) { a[pos+1] = a[pos]; pos--; }//end while a[pos+1] = x; }//end for }//end function 3. Chèn Tr c Ti p ậ Insertion Sort 3.4. Minể ểọa Ểiải tểu t Insertion Sort Insert a[5] into (0, 4) pos 1 2 5 6 8 12 6 4 15 0 1 2 3 4 5 6 7 i x void InsertionSort(int d, int n ) int pos, i, x; { for(i=1; i<n; i++) { x = a[i]; pos = i-1; while((pos >= 0)&&(a[pos] > x)) { a[pos+1] = a[pos]; pos--; }//end while a[pos+1] = x; }//end for }//end function 3. Chèn Tr c Ti p ậ Insertion Sort 3.4. Minể ểọa Ểiải tểu t Insertion Sort Insert a[6] into (0, 5) pos 1 2 4 5 6 8 12 4 15 0 1 2 3 4 5 6 7 i x void InsertionSort(int d, int n ) int pos, i, x; { for(i=1; i<n; i++) { x = a[i]; pos = i-1; while((pos >= 0)&&(a[pos] > x)) { a[pos+1] = a[pos]; pos--; }//end while a[pos+1] = x; }//end for }//end function 3. Chèn Tr c Ti p ậ Insertion Sort 3.4. Minể ểọa Ểiải tểu t Insertion Sort Insert a[8] into (0, 6) pos 1 2 4 5 6 8 12 15 0 1 2 3 4 5 6 7 i x void InsertionSort(int d, int n ) int pos, i, x; { for(i=1; i<n; i++) { x = a[i]; pos = i-1; while((pos >= 0)&&(a[pos] > x)) { a[pos+1] = a[pos]; pos--; }//end while a[pos+1] = x; }//end for }//end function 3. Chèn Tr c Ti p ậ Insertion Sort 3.4. Minể Họa Giải tểu t Insertion Sort pos 1 2 4 5 6 8 12 15 0 1 2 3 4 5 6 7 void InsertionSort(int d, int n ) int pos, i, x; { for(i=1; i<n; i++) { x = a[i]; pos = i-1; while((pos >= 0)&&(a[pos] > x)) { a[pos+1] = a[pos]; pos--; }//end while a[pos+1] = x; }//end for }//end function 3. Chèn Tr c Ti p ậ Insertion Sort 3.5. Minh ểọa Ểiải tểu t Insertion Sort ế ới ếạnỂ bảnỂ i 1 Pos 0/-1 a[Pos] 12/2 x=a[i] 2 2 1 12 8 2 0 2 8 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] 12 2 8 5 1 6 4 15 12 2/12 8 5 1 6 4 15 12/2 12 8 5 1 6 4 15 2 12 8/12 5 1 6 4 15 K t tểúẾ vònỂ ệặp while do a[Pos]=2 !> x=8 2 12/8 12 5 1 6 4 15 3 2 12 5 2 8 12 5/12 1 6 4 15 3 1 8 5 2 8 12/8 12 1 6 4 15 3 0 2 5 K t tểúẾ vònỂ ệặp while do a[Pos]=2 !> x=5 2 8/5 8 12 1 6 4 15 4 3 12 1 2 5 8 12 1/12 6 4 15 4 2 8 1 2 5 8 12/8 12 6 4 15 4 1 5 1 2 5 8/5 8 12 6 4 15 4 0 2 1 2 5/2 5 8 12 6 4 15 4 -1 6 4 15 K t tểúẾ vònỂ ệặp while do Pos ! >= 0 2/1 2 5 8 12 3. Chèn Tr c Ti p ậ Insertion Sort 3.5. Minh ểọa Ểiải tểu t Insertion Sort ế ới ếạnỂ bảnỂ i Pos a[Pos] x=a[i] a[1] a[2] a[3] a[4] a[5] a[6] a[7] 1 2 5 8 12 6 4 15 a[0] 5 4 12 6 1 2 5 8 12 6/12 4 15 5 3 8 6 1 2 5 8 12/8 12 4 15 5 2 5 6 6 K t tểúẾ vònỂ ệặp while do a[Pos]=5 !> x=6 1 2 5 8/6 8 12 4 15 5 12 4 1 2 5 6 8 12 4/12 15 4 8 4 1 2 5 6 8 12/8 12 15 3 6 4 1 2 5 6 8/6 8 12 15 2 5 4 1 2 5 6/5 6 8 12 15 1 2 4 K t tểúẾ vònỂ ệặp while do a[Pos]=2 !> x=4 1 7 6 12 15 2 5/4 5 6 8 12 15 K t tểúẾ vònỂ ệặp while do a[Pos]=12 !> x=15 K t tểúẾ vònỂ ệặp for do i (=8) !< n (=8) 8 Mảng sau sắp xếp 1 2 4 5 6 8 12 15 3. Chèn Tr c Ti p ậ Insertion Sort 3.6. Đánể giá Ểiải tểu t Trường hợp Số phép so sánh �−1 Tốt nhất Xấu nhất �−1 ෍ �=1 ෍ �− �=1 =�− = � �− Số phép gán �−1 �−1 ෍ �+ �=1 = ෍ �=1 = �− �+ �+ − 142 4. N i B t ậ Bubble Sort 4.1. Ý t ởnỂ  Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đ a phần tử nhỏ hơn trong cặp phần tử đó về vị trí đúng đầu dãy hiện hành, sau đó sẽ không xét đến nó b c tiếp theo, do vậy lần xử lý thứ i sẽ có vị trí đầu dãy là i.  Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét. 4. N i B t ậ Bubble Sort 4.2. CáẾ b ớẾ Ếủa Ểiải tểu t Bubbệe Sort - B c 1: i = 0; - B c 2: j=N-1;//Duỵt // lần x t lý đầu tiên cúi dãy ng i Trong khi (j>i) tḥc hịn: N u a[j]<a[j-1] Doicho(a[j],a[j-1]); j = j-1; - B c 3 : i = i+1;// N u Ng lần x lý k ti p i =N-1: H t dãy. D ng c ḷi : Lặp ḷi B c 2. c v̀ ṿ trí 4. Nổi Bọt – Bubble Sort 4.3. Cài Đặt Ểiải tểu t Bubệe Sort void BubbleSort(int a[],int n) { int i, j; for (i = 0 ; i<n-1 ; i++) for (j =n-1; j >i ; j --) /* phƠt hịn ngḥch th giữa 2 phần t lìn k̀  đổi chỗ */ if(a[j]< a[j-1]) Swap(a[j], a[j-1]); } 4. Nổi Bọt – Bubble Sort 4.4. Minể Họa Ểiải tểu t void BubbleSort(int a[],int n) { int i, j; for (i = 0 ; i<n-1 ; i++) for (j =n-1; j >i ; j --) if(a[j]< a[j-1]) Swap(a[j], a[j-1]); } j i 12 1 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 4. Nổi Bọt – Bubble Sort 4.4. Minể Họa Ểiải tểu t void BubbleSort(int a[],int n) { int i, j; for (i = 0 ; i<n-1 ; i++) for (j =n-1; j >i ; j --) if(a[j]< a[j-1]) Swap(a[j], a[j-1]); } j i 1 2 12 2 8 5 4 6 15 0 1 2 3 4 5 6 7 4. Nổi Bọt – Bubble Sort 4.4. Minể Họa Ểiải tểu t void BubbleSort(int a[],int n) { int i, j; for (i = 0 ; i<n-1 ; i++) for (j =n-1; j >i ; j --) if(a[j]< a[j-1]) Swap(a[j], a[j-1]); } j 1 2 4 12 4 8 5 6 15 0 1 2 3 4 5 6 7 i 4. Nổi Bọt – Bubble Sort 4.4. Minể Họa Ểiải tểu t void BubbleSort(int a[],int n) { int i, j; for (i = 0 ; i<n-1 ; i++) for (j =n-1; j >i ; j --) if(a[j]< a[j-1]) Swap(a[j], a[j-1]); } j 1 2 4 12 5 8 5 6 15 0 1 2 3 4 5 6 7 i 4. Nổi Bọt – Bubble Sort 4.4. Minể Họa Ểiải tểu t void BubbleSort(int a[],int n) { int i, j; for (i = 0 ; i<n-1 ; i++) for (j =n-1; j >i ; j --) if(a[j]< a[j-1]) Swap(a[j], a[j-1]); } j 1 2 4 5 12 6 8 6 15 0 1 2 3 4 5 6 7 i 4. Nổi Bọt – Bubble Sort 4.4. Minể Họa Ểiải tểu t void BubbleSort(int a[],int n) { int i, j; for (i = 0 ; i<n-1 ; i++) for (j =n-1; j >i ; j --) if(a[j]< a[j-1]) Swap(a[j], a[j-1]); } j 1 2 4 5 6 8 12 8 15 0 1 2 3 4 5 6 7 i 4. Nổi Bọt – Bubble Sort 4.4. Minể Họa Ểiải tểu t void BubbleSort(int a[],int n) { int i, j; for (i = 0 ; i<n-1 ; i++) for (j =n-1; j >i ; j --) if(a[j]< a[j-1]) Swap(a[j], a[j-1]); } j 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 i 4. Nổi Bọt – Bubble Sort 4.5. Minh Họa Ểiải tểu t Buble Sort ế ới ếạnỂ bảnỂ i j A[j-1] A[j] A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] 12 2 8 5 1 6 4 15 0 7 4 15 12 2 8 5 1 6 4 15 0 6 6/4 4/6 12 2 8 5 1 6/4 4/6 15 0 5 1 4 12 2 8 5 1 4 6 15 0 4 5/1 1/5 12 2 8 5/1 1/5 4 6 15 0 3 8/1 1/8 12 2 8/1 1/8 5 4 6 15 0 2 2/1 1/2 12 2/1 1/2 8 5 4 6 15 0 1 12 1 12/1 1/12 2 8 5 4 6 15 1 7 6 15 1 12 2 8 5 4 6 15 1 6 4 6 1 12 2 8 5 4 6 15 1 5 5/4 4/5 1 12 2 8 5/4 4/5 6 15 1 4 8/4 4/8 1 12 2 8/4 4/8 5 6 15 1 3 2 4 1 12 2 4 8 5 6 15 1 2 12/2 2/12 1 12/2 2/12 4 8 5 6 15 4. Nổi Bọt – Bubble Sort 4.5. Minh Họa Ểiải tểu t Buble Sort ế ới ếạnỂ bảnỂ i j A[j-1] A[j] A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] 1 2 12 4 8 5 6 15 2 7 6 15 1 2 12 4 8 5 6 15 2 6 5 6 1 2 12 4 8 5 6 15 2 5 8/5 5/8 1 2 12 4 8/5 5/8 6 15 2 4 4 5 1 2 12 4 5 8 6 15 2 3 12/4 4/12 1 2 12/4 4/12 5 8 6 15 3 7 6 15 1 2 4 12 5 8 6 15 3 6 8/6 6/8 1 2 4 12 5 8/6 6/8 15 3 5 5 6 1 2 4 12 5 6 8 15 3 4 12/5 5/12 1 2 4 12/5 5/12 6 8 15 4 7 8 15 1 2 4 5 12 6 8 15 4 6 6 8 1 2 4 5 12 6 8 15 4 5 12/6 6/12 1 2 4 5 12/6 6/12 8 15 5 7 8 15 1 2 4 5 6 12 8 15 5 6 12/8 8/12 1 2 4 5 6 12/8 8/12 15 6 7 12 15 1 2 4 5 6 8 12 15 4. Nổi Bọt – Bubble Sort 4.6. Đánể giá Ểiải tểu t Buble Sort - Trong mọi tr ng hợp, số phép so sánh là: (n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n2) - Số phép hoán vị: • Tr ng hợp xấu nhất : n(n-1)/2 • Tr ng hợp tốt nhất :0 155 5. Shaker Sort 5.1. Ý t ởnỂ - Giải thuật Shaker Sort là cải tiến của Bubble Sort bằng cách thực hiện 2 l ợt đi và về cùng lúc. L ợt đi sẽ đ̉y các phần tử nhỏ về đầu dãy, l ợt về sẽ đ̉y các phần tử l n về cuối dãy. 5. Shaker Sort 5.2. Giải tểu t • B c 1: Khởi ṭo: L=0; k = n-1;//t R=n-1; • • L đ n R lơ đọn cần đ c sắp x p B c 2: j = R;//đẩy phần t nhỏ nhất v̀ đầu m ng Trong khi (j>L) N u a[j] < a[j-1]: hón ṿ a[j], a[j-1]; k=j;//l u ḷi n i x y ra hoƠn ṿ j = j-1; L=k; /*ghi nhận ḷi ṿ trí L x y ra hoƠn ṿ sau cùng để lơm c đọn l đ n r */ B c 3: j=L; // đẩy phần t l n v̀ cúi m ng Trong khi (j<r) N u a[j]>a[j+1]: hoán vị a[j], a[j+1]; k=j; //l u ḷi n i x y ra hoƠn ṿ j=j+1; R=k; //lọi b t phần t đã ć th́ ṭ ở cúi dãy • B c 4: N u L < R : lặp lại bước 2. sở thu hẹp 5. Shaker Sort 5.3. Cài đặt void ShakerSort(int a[], int n) { int i, k, left, right; k = 0; left = 0; right = n - 1; while (left < right) { for (i = right; i > left; i--) if (a[i-1] > a[i]) { Swap(a[i-1], a[i]); // Hoan vi a[i], a[i - 1] k = i;//Bi n k đƠnh dấu để bỏ qua đọn đã ć th́ ṭ } left = k; for (i = left; i < right; i++) if (a[i] > a[i + 1]) { Swap(a[i], a[i + 1]); k = i; } right = k; } } 5. Shaker Sort 5.4. Minh Họa Ểiải tểu t Shaker Sort ế ới ếạnỂ bảnỂ L R k i A[i-1] A[i] A[i+1] 0 7 0 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] 12 2 8 5 1 6 4 15 0 7 0 7 4 15 12 2 8 5 1 6 4 15 0 7 6 6 6 4 12 2 8 5 1 4 6 15 0 7 6 5 1 4 12 2 8 5 1 4 6 15 0 7 4 4 5 1 12 2 8 1 5 4 6 15 0 7 3 3 8 1 12 2 1 8 5 4 6 15 0 7 2 2 2 1 12 1 2 8 5 4 6 15 1 7 1 1 12 1 1 12 2 8 5 4 6 15 1 7 1 1 12 2 1 2 12 8 5 4 6 15 1 7 2 2 12 8 1 2 8 12 5 4 6 15 1 7 3 3 12 5 1 2 8 5 12 4 6 15 1 7 4 4 12 4 1 2 8 5 4 12 6 15 1 7 5 5 12 6 1 2 8 5 4 6 12 15 1 5 5 6 12 15 1 2 8 5 4 6 12 15 5. Shaker Sort 5.4. Minh Họa Ểiải tểu t Shaker Sort ế ới ếạnỂ bảnỂ L R k i A[i-1] A[i] A[i+1] 1 5 5 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] 1 2 8 5 4 6 12 15 1 5 5 5 6 12 1 2 8 5 4 6 12 15 1 5 4 4 5 4 1 2 8 4 5 6 12 15 1 5 3 3 8 4 1 2 4 8 5 6 12 15 1 2 4 8 5 6 12 15 3 5 3 2 3 5 3 3 8 5 1 2 4 5 8 6 12 15 4 4 4 4 8 6 1 2 4 5 6 8 12 15 6. Gi i thu t Quick Sort 6.1. Ý t ởnỂ - Chọn m t phần tử bất kỳ trong danh sách (giả sử là phần tử giữa) gọi là phần tử làm mốc (pivot element), xác định vị trí của phần tử này trong danh sách gọi là vị trí mốc. - Tiếp theo phân hoạch các phần tử còn lại trong danh sách cần sắp xếp sao cho các phần tử từ vị trí 0 đến vị trí pivot-1 đều có n i dung nhỏ hơn hoặc bằng phần tử mốc, các phần tử từ vị trí pivot+1 đến n-1 đều có n i dung l n hơn hoặc bằng phần tử mốc. 0 pivot-1 pivot pivot+1 n-1 X A[left]<=x A[right]>=x - Quá trình lại tiếp tục nh thế v i hai danh sách con từ vị trí 0 đến vị trí pivot-1 và từ vị trí pivot+1 đến vị trí n-1. - Kết quả của quá trình thực hiện sẽ đ ợc danh sách đư có thứ tự. 6. Gi i thu t Quick Sort 6.2. Cách Ếểọn pểần t làm mốẾ (pivot element) • Có thể chọn phần tử làm mốc bằng 1 trong các cách sau: - Chọn phần tử đứng đầu hoặc đứng cuối. - Chọn phần tử đứng giữa danh sách. - Chọn phần tử ngẫu nhiên làm phần tử mốc ( u điểm tránh đ ợc các tr ng hợp đặc biệt • Theo thống kê:  bad 0 <= pivot < n/4  good n/4 <= pivot < 3n/4  bad 3n/4<= pivot <=n-1 6. Gi i thu t Quick Sort 6.3. Hi u quả Ếủa tểu t toán pểụ tểuộẾ vào vi Ế Ếểọn giá trị Ếủa pểần t mốẾ (pivot) - Trường hợp tốt nhất: • Mỗi lần phân hoạch đều chọn đ ợc phần tử làm mốc có giá trị l n hơn hay bằng nửa số phần tử và nhỏ hơn hay bằng nửa số phần tử còn lại. Khi đó dãy đ ợc phân hoạch thành hai phần bằng nhau • Cần log2(n) lần phân hoạch thì sắp xếp xong. • Mỗi lần phân hoạch cần duyệt qua n phần tử. Vậy đ phức tạp trong tr ng hợp tốt nhất thu c O(nlog2(n)). 6. Gi i thu t Quick Sort 6.3. Hi u quả Ếủa tểu t toán pểụ tểuộẾ vào vi Ế Ếểọn giá trị Ếủa pểần t mốẾ (pivot) - Trường hợp xấu nhất: • Mỗi lần phần hoạch đều chọn phải phần tử có giá trị cực đại hoặc cực tiểu làm mốc. Khi đó dãy bị phân hoạch thành hai phần không đều: m t phần chỉ có m t phần tử, phần còn lại có n-1 phần tử. • Cần n lần phân hoạch m i sắp xếp xong. Vậy đ phức tạp trong tr ng hợp xấu nhất thu c O(n2). 6. Gi i thu t Quick Sort 6.4. Giải tểu t - B c 0: //chọn giá tṛ pivot tùy ý sao cho 0  pivot  n-1 pivot = 0; // chọn pivot là ṿ trí đầu left = ṿ trí đầu m ng right = ṿ trí cúi m ng K t thúc; //m ng đã đ c sắp x p - B - B c 1: N u left ≥ right K t thúc; // m ng có ít h n 2 phần t // m ng đã đ c sắp x p c 2: Phân họch dãy aleft … aright thành các đọn: aleft.. aj, aj+1.. ai-1, ai.. aright Đoạn 1  x Đoạn 2: aj+1.. ai-1 Đoạn 3: ai.. aright - B - B của m ng = x  x c 3: Sắp x p đọn 1: aleft.. aj c 4: Sắp x p đọn 3: ai.. aright 6. Gi i Thu t Quick Sort 6.4. Giải tểu t - B c 1: /* tham ś của hàm là m ng 1 chiểu (a), ṿ trí đầu tiên của m ng (left), ṿ trí cúi của m ng (right) */  L = left; R = right;  p = 0; /*Trong minh họa này, chọn pivot là ṿ trí đầu của m ng đang xét*/  x = a[p]; - B c 2: Phát hịn và đổi chỗ cặp phần t sai chỗ:  B  B  B - B - B - B - B a[L], a[R] nằm c 2a : Trong khi (a[L]<x) L++; c 2b : Trong khi (a[R]>x) R--; c 2c : N u L < R  Đoicho(a[L],a[R]); N u L <= R  L++ ; R--; c 3: N u L < R: Lặp ḷi B c 4: Đoicho(a[L],a[R]); c 2. Ng c 5: Sắp x p đọn 1: aleft.. AR c 6: Sắp x p đọn 3: aL.. aright c ḷi: D ng 6. Gi i Thu t Quick Sort 6.5. Cài đặt void QuickSort(int a[], int left, int right) { int L, R, x, pivot=left; /* chọn ḿc là phần t tiên trong m ng hịn ṭi*/ x = a[pivot]; L = left; R = right; while(L <= R) { đầu while ((a[L] < x) && (L<right)) L++; while ((a[R] > x) && (R>left)) R--; if (L <= R) if (L < R) Swap(a[L], a[R]); { L++; R--; } } //n u m ng bên TRÁI của pivot có nhìu h n 1 phần t if(left<R) QuickSort(a, left, R); //n u m ng bên PH I của pivot có nhìu h n 1 phần t if(L<right) QuickSort(a, L, right); } 6. Gi i thu t Quick Sort 6.6. Minể ểọa Ếể ơnỂ trửnể Ếài đặt Ếủa ẬuiẾỆ Sort • Cho mảng 1 chiều chứa các số nguyên, gồm 9 phần tử 40 20 10 80 60 50 7 30 100 • Chọn phần tử mốc (pivot element) cho việc phân hoạch Có nhiều cách chọn phần tử mốc. Trong ví dụ này lấy phần tử đầu tiên của mảng làm phần tử mốc 40 20 10 80 60 50 7 30 100 6. Gi i thu t Quick Sort 6.6. Minể ểọa Ếể ơnỂ trửnể Ếài đặt Ếủa ẬuiẾỆ Sort void QuickSort(int a[], int left, int right) { int pivot=left, x = a[left]; L = left; R = right; while(L <= R) { while ((a[L] < x) && (L<right)) L++; while ((a[R] > x) && (R>left)) R--; if (L <= R) { if (L < R) Swap(a[L], a[R]); L++; R--; } } if(left<R) QuickSort(a, left, R); if(L<right) QuickSort(a, L, right); } x = 40 40 20 10 80 60 50 7 30 100 left=0 right=8 [0] [1] [2] [3] [4] [5] [6] [7] [8] L=0 L R=8 R 6. Gi i thu t Quick Sort 6.6. Minể ểọa Ếể ơnỂ trửnể Ếài đặt Ếủa ẬuiẾỆ Sort void QuickSort(int a[], int left, int right) { int p=left, x = a[p]; L = left; R = right; while(L <= R) { while ((a[L] < x) && (L<right)) L++; while ((a[R] > x) && (R>left)) R--; if (L <= R) { if (L < R) Swap(a[L], a[R]); } L++; L++; R--; R--; } } if(left<R) QuickSort(a, left, R); if(L<right) QuickSort(a, L, right); } x = 40 40 20 10 80 60 50 7 30 100 left=0 right=8 L=0 R=8 [0] [1] [2] [3] [4] [5] [6] [7] [8] L R 6. Gi i thu t Quick Sort 6.6. Minể ểọa Ếể ơnỂ trửnể Ếài đặt Ếủa ẬuiẾỆ Sort void QuickSort(int a[], int left, int right) 1. pivot_index=0; L=1; R=n-1; { while int p=left, = a[p]; L = left; R = right; ++L 2. (A[L] x<= A[pivot]) while(L <= R) 3. while (A[R] > A[pivot]) --R { while ((a[L] < x) && (L<right)) L++; 4. if (L<R) swap A[L] while ((a[R] > x) && (R>left)) R--;and A[R] 5. while go to 2 if (R>L) (L <= R) if and (L <A[pivot_index] R) Swap(a[L], a[R]); 6. swap{ A[R] L++; L++; R--; R--; } } if(left<R) if(L<right) } QuickSort(a, left, R); QuickSort(a, L, right); } x = 40 left=0 right=8 L=0 R=8 R=7 40 20 10 80 60 50 7 30 100 [0] [1] [2] [3] [4] [5] [6] [7] [8] L R 6. Gi i thu t Quick Sort 6.6. Minể ểọa Ếể ơnỂ trửnể Ếài đặt Ếủa ẬuiẾỆ Sort void QuickSort(int a[], int left, int right) { int p=left, x = a[p]; L = left; R = right; while(L <= R) { while ((a[L] < x) && (L<right)) L++; while ((a[R] > x) && (R>left)) R--; if (L <= R) { if (L < R) Swap(a[L], a[R]); } L++; L++; R--; R--; } } if(left<R) QuickSort(a, left, R); if(L<right) QuickSort(a, L, right); } x = 40 left=0 right=8 40 20 10 80 60 50 7 30 100 [0] [1] [2] [3] [4] [5] [6] [7] [8] L=0 R=7 L R 6. Gi i thu t Quick Sort 6.6. Minể ểọa Ếể ơnỂ trửnể Ếài đặt Ếủa ẬuiẾỆ Sort void QuickSort(int a[], int left, int right) { int p=left, x = a[p]; L = left; R = right; while(L <= R) { while ((a[L] < x) && (L<right)) L++; while ((a[R] > x) && (R>left)) R--; if (L <= R) { if (L < R) Swap(a[L], a[R]); } L++; L++; R--; R--; } } if(left<R) QuickSort(a, left, R); if(L<right) QuickSort(a, L, right); } x = 40 left=0 30 right=8 [0] [1] [2] [3] [4] [5] [6] [7] [8] L=0 L=1 R=7 R=6 L 20 10 80 60 50 7 40 100 R 6. Gi i thu t Quick Sort 6.6. Minể ểọa Ếể ơnỂ trửnể Ếài đặt Ếủa ẬuiẾỆ Sort void QuickSort(int a[], int left, int right) { int intp=left, p=left,xx==a[p]; a[p];LL==left; left;RR==right; right while(L<= <=R) R) while(L while((a[L] ((a[L]<<x) x)&& &&(L<right)) (L<right))L++; L++; {{ while while((a[R] ((a[R]>>x) x)&& &&(R>left)) (R>left))R--; R--; while if(L (L<= <=R) R) if < R) Swap(a[L], a[R]); {{ if if (L(L < R) Swap(a[L], a[R]); L++; R--; L++; R--;} } }} if(left<R) if(left<R) QuickSort(a, left, R); if(L<right) if(L<right) QuickSort(a, L, right); } x = 40 left=0 30 right=8 [0] [1] [2] [3] [4] [5] [6] [7] [8] L=1 R=6 20 10 L 80 60 50 7 40 100 R 6. Gi i thu t Quick Sort 6.6. Minể ểọa Ếể ơnỂ trửnể Ếài đặt Ếủa ẬuiẾỆ Sort void QuickSort(int a[], int left, int right) { int p=left, x = a[p]; L = left; R = right; while(L <= R) { while ((a[L] < x) && (L<right)) L++; while ((a[R] > x) && (R>left)) R--; if (L <= R) { if (L < R) Swap(a[L], a[R]); } L++; L++; } R--; R--; } if(left<R) QuickSort(a, left, R); if(L<right) QuickSort(a, L, right); } x = 40 left=0 right=8 L=1 L=2 L=3 R=6 30 20 10 80 60 50 7 40 100 [0] [1] [2] [3] [4] [5] [6] [7] [8] L R 6. Gi i thu t Quick Sort 6.6. Minể ểọa Ếể ơnỂ trửnể Ếài đặt Ếủa ẬuiẾỆ Sort void QuickSort(int a[], int left, int right) { int p=left, x = a[p]; L = left; R = right; while(L <= R) { while ((a[L] < x) && (L<right)) L++; while ((a[R] > x) && (R>left)) R--; if (L <= R) { if (L < R) Swap(a[L], a[R]); } L++; L++; R--; R--; } } if(left<R) QuickSort(a, left, R); if(L<right) QuickSort(a, L, right); } x = 40 left=0 right=8 L=3 L=4 R=6 R=5 30 20 10 7 60 50 80 40 100 [0] [1] [2] [3] [4] [5] [6] [7] [8] L R 6. Gi i thu t Quick Sort 6.6. Minể ểọa Ếể ơnỂ trửnể Ếài đặt Ếủa ẬuiẾỆ Sort void QuickSort(int a[], int left, int right) { int p=left, x = a[p]; L = left; R = right; while(L <= R) { while ((a[L] < x) && (L<right)) L++; while ((a[R] > x) && (R>left)) R--; if (L <= R) { if (L < R) Swap(a[L], a[R]); L++; L++; R--; R--; } } } if(left<R) QuickSort(a, left, R); if(L<right) QuickSort(a, L, right); } x = 40 left=0 30 right=8 [0] [1] [2] [3] [4] [5] [6] [7] [8] L=4 R=5 R=4 R=3 20 10 7 60 L 50 R 80 40 100 6. Gi i thu t Quick Sort 6.6. Minể ểọa Ếể ơnỂ trửnể Ếài đặt Ếủa ẬuiẾỆ Sort void QuickSort(int a[], int left, int right) { int p=left, x = a[p]; L = left; R = right; while(L <= R) { while ((a[L] < x) && (L<right)) L++; while ((a[R] > x) && (R>left)) R--; if (L (L <= <= R) R) if if (L (L << R) R) Swap(a[L], Swap(a[L],a[R]); a[R]); if { } L++; L++; R--; R--; } } if(left<R) QuickSort(a, left, R); if(L<right) QuickSort(a, L, right); } x = 40 left=0 30 right=8 [0] [1] [2] [3] [4] [5] [6] [7] [8] L=4 R=3 20 10 7 60 R L 50 80 40 100 6. Gi i thu t Quick Sort 6.6. Minể ểọa Ếể ơnỂ trửnể Ếài đặt Ếủa ẬuiẾỆ Sort void QuickSort(int a[], int left, int right) { int p=left, x = a[p]; L = left; R = right; while(L <= R) { while ((a[L] < x) && (L<right)) L++; while ((a[R] > x) && (R>left)) R--; if (L <= R) { if (L << R) R) Swap(a[L], Swap(a[L], a[R]); a[R]); if (L L++; R--; } L++; R--; } } if(left<R) QuickSort(a, left, R); if(L<right) QuickSort(a, L, right); } QuickSort(a,left=0,R=3); x = 40 left=0 30 right=8 [0] [1] [2] [3] [4] [5] [6] [7] [8] L=4 R=3 20 10 7 60 R L 50 80 40 100 6. Gi i thu t Quick Sort 6.6. Minể ểọa Ếể ơnỂ trửnể Ếài đặt Ếủa ẬuiẾỆ Sort void QuickSort(int a[], int left, int right) { int p=left, x = a[p]; L = left; R = right; while(L <= R) { while ((a[L] < x) && (L<right)) L++; while ((a[R] > x) && (R>left)) R--; if (L <= R) { if (L << R) R) Swap(a[L], Swap(a[L], a[R]); a[R]); if (L L++; R--; } L++; R--; } } if(left<R) QuickSort(a, left, R); if(L<right) QuickSort(a, L, right); } QuickSort(a,left=0,R=3); QuickSort(a,L=4,right=8); 30 20 10 7 60 50 80 40 100 [0] [1] [2] [3] [4] [5] [6] [7] [8] R L 6. Gi i thu t Quick Sort 6.6. Minể ểọa Ếể ơnỂ trửnể Ếài đặt Ếủa ẬuiẾỆ Sort • Thực hiện đệ quy quá trình phân hoạch 2 mảng con vừa có 30 20 10 7 60 50 80 40 100 [0] [1] [2] [3] [4] [5] [6] [7] [8] void QuickSort(int a[], int left, int right) void QuickSort(int a[], int left, int right) //v i left=0 vơ right=3 //v i left=4 vơ right=8 6. Gi i thu t Quick Sort 6.7. Minể ểọa Ểiải tểu t ẬuiẾỆ Sort ế ới ếạnỂ bảnỂ với pivot=0 left=0 & right=7  x=a[pivot]=a[0]=12 Diễn giải L a[L] Kh i đầu CT 0 while(L <= R)//Lặp lần 1 0 R a[R] 7 12 7 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] 12 2 8 5 1 6 4 15 12 2 8 5 1 6 4 15 15 while ((a[L] < x) && (L<right)) L++ 0 while ((a[R] > x) && (R>left)) R--; 0 12 7/6 15/4 if(L<=R) Swap(a[L],a[R]) 0 12/4 6 4/12 12/4 2 8 5 1 6 4/12 15 L++; R-- 0/1 2 6/5 6 4 2 8 5 1 6 12 15 4 2 8 5 1 6 12 15 if (L<= R) while(L <= R)//Lặp lần 2 1 5 while ((a[L] < x) && (L<right)) L++ 1/6 2/12 5 6 4 2 8 5 1 6 12 15 while ((a[R] > x) && (R>left)) R--; 6 12 5 6 4 2 8 5 1 6 12 15 R L right 6 12 15 if (L<= R) if(L<=R) Swap(a[L],a[R]) L++; R-left Gọi đ̣ quy do !(L<=R) 6 12 5 6 4 2 8 MảnỂ 1 5 1 MảnỂ 2 6. Gi i thu t Quick Sort 6.7. Minể ểọa Ểiải tểu t ẬuiẾỆ Sort ế ới ếạnỂ bảnỂ với pivot=0 Gọi đ quỔ mảnỂ 1 với ệeềt=0 & riỂểt=5  x=a[pivot]=a[0]=4 Diễn giải L a[L] R a[R] a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] 4 2 8 5 1 6 12 15 4 2 8 5 1 6 12 15 Kh i đầu hàm 0 while(L <= R)//Lặp lần 1 0 4 5 6 while ((a[L] < x) && (L<right)) L++ 0 4 5 6 while ((a[R] > x) && (R>left)) R--; 0 4 5/4 6/1 if (L<= R) 0 if(L<=R) Swap(a[L],a[R]) 0 4/1 4 1/4 4/1 2 8 5 1/4 6 L++; R-- 0/1 1/2 4/3 5 1 2 8 5 4 6 12 15 1 2 3 5 1 2 8 5 4 6 12 15 while ((a[L] < x) && (L<right)) L++ 1/2 2/8 3 5 while ((a[R] > x) && (R>left)) R--; 2 8 3/1 5/2 if (L<= R) 2 left R L 1 2 5 12 15 while(L <= R)//Lặp lần 2 5 4 1 if(L<=R) Swap(a[L],a[R]) L++; R-Gọi đ̣ quy do !(L<=R) 3 2 M 1.1 right 8 M1.2 4 6 M2 6. Gi i thu t Quick Sort Gọi đ quỔ mảnỂ 1.1 với ệeềt=0 & riỂểt=1  x=a[pivot]=a[0]=1 6.7. Minể ểọa Ểiải tểu t ẬuiẾỆ Sort ế ới ếạnỂ bảnỂ với pivot=0 Diễn giải L Kh i đầu hàm 0 while(L <= R)//Lặp lần 1 0 a[L] R a[R] a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] 1 2 5 8 4 6 12 15 1 1 1 while ((a[L] < x) && (L<right)) L++ 0 1 while ((a[R] > x) && (R>left)) R--; 0 1/-1 2 if (L<= R) if(L<=R) Swap(a[L],a[R]) L++; R-K t th́c hơm đ̣ quy trên m ng 1.1 do !L<R  M1.1 đã đ c sắp tang dần 1 2 M 1.1 5 8 4 M1.2 6 12 15 M2 6. Gi i thu t Quick Sort 6.7. Minể ểọa Ểiải tểu t ẬuiẾỆ Sort ế ới ếạnỂ bảnỂ với pivot=0 Gọi đ quỔ mảnỂ 1.2 với ệeềt=2 & riỂểt=5  x=a[pivot]=a[2]=5 Diễn giải Kh i đầu hàm L a[L] 2 5 2 5 R a[R] a[0] a[1] 5 6 1 2 5/4 6/4 a[2] a[3] a[4] a[5] a[6] a[7] 5 8 4 6 12 15 5/4 8 4/5 6 4 8 5 6 4 8 5 6 left/R L 4 8 12 15 while(L <= R)//Lặp lần 1 while ((a[L] < x) && (L<right)) L++ while ((a[R] > x) && (R>left)) R--; if (L<= R) if(L<=R) Swap(a[L],a[R]) L++; R-while(L <= R)//Lặp lần 1 2/3 3 4/3 8 3 8 3/2 4 while ((a[L] < x) && (L<right)) L++ while ((a[R] > x) && (R>left)) R--; if (L<= R) if(L<=R) Swap(a[L],a[R]) L++; R-Gọi đ̣ quy do !(L>R) 3 2 1 M 1.1 2 1.2.1 right 5 1.2.2 6 M2 6. Gi i thu t Quick Sort 6.7. Minể ểọa Ểiải tểu t ẬuiẾỆ Sort ế ới ếạnỂ bảnỂ với pivot=0 Gọi đ quỔ mảnỂ 1.2.2 với ệeềt=3 & riỂểt=5  x=a[pivot]=a[3]=8 Diễn giải Kh i đầu hàm L a[L] 3 8 3 8 R a[R] a[0] a[1] a[2] a[3] a[4] 5 6 1 2 4 8 5 5 6 a[5] a[6] a[7] 6 12 15 while(L <= R)//Lặp lần 1 while ((a[L] < x) && (L<right)) L++ while ((a[R] > x) && (R>left)) R--; if (L<= R) if(L<=R) Swap(a[L],a[R]) 3 8/6 5 6/8 1 2 4 8/6 5 6/8 12 15 L++; R-- 4 6/5 4 5 1 2 4 6 5 8 12 15 1 2 4 6 5 8 12 15 left R L/ right while(L <= R)//Lặp lần 1 while ((a[L] < x) && (L<right)) L++ while ((a[R] > x) && (R>left)) R--; 4/5 5/8 4 5 if (L<= R) if(L<=R) Swap(a[L],a[R]) L++; R-Gọi đ̣ quy do !(L>R) Gọi đệ quy mảng 1.2.2.1. Gọi đệ quy mảng 1.2.2.2 1 phần tử  đư xếp1.2.2.2 xong. M 1.1chỉ gồm 1.2.1 1.2.2.1 M2 6. Gi i thu t Quick Sort 6.7. Minể ểọa Ểiải tểu t ẬuiẾỆ Sort ế ới ếạnỂ bảnỂ với pivot=0 Diễn giải Gọi đ quỔ mảnỂ 1.2.2.1 với ệeềt=3 & riỂểt=4  x=a[pivot]=a[3]=6 L Kh i đầu hàm 3 a[L] 6 R 4 a[R] a[0] a[1] a[2] a[3] a[4] 5 1 2 4 6 5 5/6 1 2 4 6/5 1 2 4 5 a[5] a[6] a[7] 8 12 15 5/6 8 12 15 6 8 12 15 while(L <= R)//Lặp lần 1 while ((a[L] < x) && (L<right)) L++ 3 while ((a[R] > x) && (R>left)) R--; 4 if (L<= R) if(L<=R) Swap(a[L],a[R]) L++; R-K t th́c hơm 6/5 3/4 4/3 !(L>R) M 1.1 1.2.1 1.2.2.1 1.2.2.2 M2 6. Gi i thu t Quick Sort 6.8. Giải tểu t QuickSort chia 3 ▪ M t ph ơng pháp chia khác là chia danh sách thành 3 danh sách con, lần l ợt nhỏ hơn, bằng và l n hơn phần tử mốc. ▪ Giải thuật QuickSort sắp xếp dãy a1, a2 ..., aN dựa trên việc phân hoạch dãy ban đầu thành 3 đoạn: • • • v Đoạn 1: Gồm các phần tử có giá trị bé hơn x Đoạn 2: Gồm các phần tử có giá trị bằng x Đoạn 3: Gồm các phần tử có giá trị l n hơn x i x là giá trị của m t phần tử tùy ý trong dãy ban đầu. 6. Gi i thu t Quick Sort 6.8. Giải tểu t QuickSort chia 3 - Đoạn thứ 2 đư có thứ tự. - Nếu các đoạn 1 và 3 chỉ có 1 phần tử  đư có thứ tự  dưy con ban đầu đư đ ợc sắp. - Ng ợc lại, nếu các đoạn 1 và 3 có nhiều hơn 1 phần tử thì dãy ban đầu chỉ có thứ tự khi các đoạn 1, 3 đ ợc sắp. - Để sắp xếp các đoạn 1 và 3, ta lần l ợt tiến hành việc phân hoạch từng dãy con theo cùng ph ơng pháp phân hoạch dãy ban đầu vừa trình bày 6. Gi i thu t Quick Sort 6.9. Đánh giá gi i thuật - Chi phí trung bình O(n*log2n) - Chi phí cho tr ng hợp xấu nhất O(n2) - Chi phí tùy thu c vào cách chọn phần tử pivot: • Nếu chọn đ ợc phần tử có giá trị trung bình, ta sẽ chia thành 2 dãy bằng nhau (log2n); • Nếu chọn đúng vào phần tử nhỏ nhất (hay l n nhất)  O(n2) 190 6. Gi i thu t Quick Sort 6.10. Bài t p: Minh họa giải thuật Quick Sort d bảng v i pivot luôn là vị trí giữa của mảng Diễn giải L a[L] R a[R] a[0] a[1] a[2] a[3] a[4] 12 2 8 5 1 a[5] 6 i dạng a[6] a[7] 4 15 N I DUNG MỌN H C - Chương 1: Tổng quan về giải thuật và cấu trúc dữ liệu - Chương 2: Đệ quy - Chương 3: Các giải thuật tìm kiếm trên mảng 1 chiều - Chương 4: Các giải thuật sắp xếp trên mảng 1 chiều - Chương 5: Danh sách liên kết đ ng (Linked List) - Chương 6: Ngăn xếp (Stack) - Chương 7: Hàng đợi (Queue) - Chương 8: Cây (Tree) - Chương 9: Bảng băm (Hash Table) Ch ng 5 DANH SÁCH LIểN ḰT Đ NG (Linked List) M C TIểU - Nắm vững khái niệm về kiểu dữ liệu tĩnh và đ ng - Nắm vững cách tổ chức dữ liệu đ ng bằng danh sách liên kết và minh họa đ ợc các thao tác xử lý trên danh sách liên kết đơn - Cài đặt minh họa đ ợc các thao tác của danh sách đơn bằng ngôn ngữ C/ C++ N I DUNG 1. Gi i thiệu vấn đề 2. Danh sách liên kết (DSLK) 3. Lập trình v i danh sách liên kết đơn (SV tự Ếài đặt và trửnể bàỔ pểần 4 và 5) 4. Danh sách liên kết không đơn i. DSLK đôi ii. DSLK đơn vòng iii. DSLK đôi vòng 5. Các kiểu phối hợp khác dựa trên DSLK i. Mảng các DSLK ii. DSLK v i n i dung mỗi node chứa 1 DSLK khác 1. Gi i thi u v n đ Cho 1 mảng có SIZE=8 phần tử, đư sử dụng n=7 phần tử. 1.1. Làm sao đ thêm một pểần t vào mảnỂ? 10 5 13 11 6 12 9 ?  Phải chuyển các phần tử về phía sau m t vị trí… 18 10 5 13 11 6 12 9 ? 13 11 6 12 9 13 11 6 12 9 18 10 5  Và thêm vào 10 18 5 18  Làm sao thêm m t phần tử nữa? 1. Gi i thi u v n đ 1.1. Làm sao đ thêm một pểần t vào mảnỂ? Bài t p: Cho mảng m t chiều kiểu số nguyên a, kích th c n. Hãy cài đặt hàm chèn m t phần tử có giá trị x vào vị trí vt trong mảng theo mẫu hàm nh sau: void ChenXVaoViTri(int a[], int &n, int x, int vt) void ChenXVaoViTri (int A[], int &n, int X, int vitri) { /* B1: Xuất phát từ uối ả g tiế hành đẩ lầ lượt các phầ tử ềàphíaàsauà hoàđế à ịàtríà ầ à hè */ for (int i = n; i >vitri ; i--) A[i] = A[i-1] ; // B2: Đưa phầ tử ầ chèn vào ị trí chèn A[vitri] = X; // B3: Tă g kích thướ ả g n++; } 197 1. Gi i thi u v n đ 1.2. Làm sao xóa một pểần t trong mảnỂ 10 5 18 13 11 - Phải d i các phần tử về tr 6 12 9 c m t vị trí 10 5 18 13 11 6 12 9 10 5 13 11 6 12 9 9 - Đ phức tạp của thêm và xóa là O(n) 1. Gi i thi u v n đ 1.2. Làm sao đ xóa một pểần t ra Ệểỏi mảnỂ? Bài t p: Cho mảng m t chiều số nguyên a, kích th c n. Hãy cài đặt hàm xóa m t phần tử tại vị trí vt theo mẫu hàm nh sau: void XoaTaiViTri(int a[], int &n, int x) void XoaTaiViTri (int A[], int &n, int vitri) { // B1: Dời sang tri từ vitri den n-1 for (int i = vitri; i < n ; i++) A[i] = A[i+1]; // B2: Giả n di 1 đơ ị n--; } 199 1. Gi i thi u v n đ 1.3. V n đ ki u d li u tĩnh i. Đ phức tạp của chèn/ xóa trên mảng 1 chiều là O(n) ii. Các vấn đề cần giải quyết: - Phức tạp khi chèn/ xóa? - Gi i hạn kích th c vùng nh tối đa? - Vùng nh không liên tục? int A[10]; nA=11; int B[1000000000], nB=3;  Có cần m t cấu trúc l u trữ khác? sửàḍ gà CẤUàTRÚCàDỮàLIỆUàĐỘNG 200 1. Gi i thi u v n đ 1.4. Bi n tĩnh vƠ bi n đ ng trong ngôn ng Bi n tƿnh Khai báo <kiểu dữ liệu> tên biến; VD int a; float y; char s[20]; Cấp Khi khai báo phát Bi n động <kiểu dữ liệu> *tên biến; int *a; float *y Khi cần dùng: e ài tà[ḱ hàthướ ] int *a; a=new int [10]; VD Thu hồi C Khi kết thúc hàm Do ng i lập trình delete a; VD Đặc ✓ Tồn tại trong phạm vi khai ✓ Chứa địa chỉ của m t đối điểm t ợng dữ liệu báo ✓ Đ ợc cấp phát vùng nh trong vùng dữ liệu ✓ Kích th c cố định ✓ Đ ợc cấp phát hoặc giải phóng b nh tùy thu c vào ng i lập trình ✓ Kích th c có thể thay đổi 201 2. Danh sách liên k t - Các phần tử đều đ c lập (r i nhau) - Đ ợc liên kết bằng các “dây xích” - Các phần tử không cần phải l u trữ liên tiếp nhau trong b nh - Có thể m r ng tuỳ ý (chỉ gi i hạn b i dung l ợng b nh ) 2. Danh sách liên k t 2.1. Chèn một pểần t vào danh sách 10 5 13 11 18 • Chỉ cần “móc” lại các dây xích khi thêm 10 5 13 11 18 10 18 5 13 11  Thao tác chèn không cần phải dịch chuyển phần tử mà chỉ cần thay đổi mối liên kết 2. Danh sách liên k t 2.2. Xóa một pểần t Ệểỏi danh sách 10 18 5 13 11 • “Móc” lại các dây xích khi xóa 10 18 5 13 10 5 13 11 11  Thao tác xóa không cần phải dịch chuyển phần tử mà chỉ cần thay đổi mối liên kết 2. Danh sách liên k t 2.3. Khái ni m v danh sách liên Ệ t (DSLK) 8a 8a pHead 9b 9b 1c data link data link 1c NULL data link • M t dãy tuần tự các node (Node). • Mỗi node có 2 thông tin:  Dữ liệu (data).  Con trỏ liên kết đến phần tử kế tiếp trong danh sách (Next pointer link)  Phần tử cuối cùng trong danh sách có Next pointer link = NULL • Quản lý phần tử đầu tiên của DSLK bằng con trỏ pHead. pHead không phải là 1 node, mà chỉ là “con trỏ chỉ đến node”. • Có thể sử dụng thêm con trỏ cuối (pTail). T ơng tự, pTail cũng không phải là 1 node pHead pTail 1e bc bc a8 1e a8 bc data link data link NULL data link 2. Danh sách liên k t 2.4. • • • • u đi m Các node không cần phải l u trữ liên tiếp nhau trong b nh . Có thể m r ng tuỳ ý (chỉ gi i hạn b i dung l ợng b nh ). Thao tác chèn/xóa không cần phải dịch chuyển các phần tử khác. Có thể truy xuất đến các phần tử khác thông qua con trỏ liên kết. 2. Danh sách liên k t 2.5. Cấu tạo Ếủa nút (node) • Node có 1 field dữ liệu number pNext typedef struct tagNODE { int number; tagNODE *Next; } NODE; • Node có nhiều field dữ liệu name typedef struct tagNODE { char name[30]; int id; float grdPts; tagNODE *Next; } NODE; id grdPts pNext 2. Danh sách liên k t 2.5. Cấu tạo Ếủa nút (node) - Node có dữ liệu là 1 struct gồm nhiều field typedef struct tagINFO { char name[30]; int id; float grdPts; } INFO; typedef struct tagNODE { INFO data; tagNODE* Next; } NODE; name id grdPts struct pNext 2. Danh sách liên k t 2.6. Cấu tạo Ếủa danh sách liên Ệ t 2.6.1. Quản lý DSLK đơn với phần tử đầu là pHead 8a 8a 9b 9b 1c 1c pHead data link data link  Danh sách rỗng, pHead = NULL NULL pHead NULL data link 2. Danh sách liên k t 2.6. Cấu tạo Ếủa danh sách liên Ệ t 2.6.2. Quản lý DSLK đơn với 1 cấu trúc để quản lý phần tử đầu và phần tử cuối pHead pTail 1e bc a8 1e a8 9 data link  Ví dụ: quản lý DSLK trong b nh 7e 2 7e bc 8 data link 5d NULL data link 34 99 5d 7 ab 5 bc 15 NULL 34 ab  Danh sách rỗng, pHead = NULL; pTail = NULL pHead 34 pTail 2. Danh sách liên k t 2.6. Cấu tạo Ếủa danh sách liên Ệ t 2.6.2. Quản lý DSLK đơn với 1 cấu trúc để quản lý phần tử đầu và phần tử cuối - Định nghĩa cấu trúc l u trữ Typedef struct tagNode { Data Info; // L u thông tin b n thân struct tagNode *Next; /*L u đ̣a chỉ của Node đ́ng lìn sau */ // đặt tên cho kiểu của phần t }Node; - Định nghĩa biến quản lý đầu danh sách (dùng cho các cấu trúc node khác nhau) typedef struct tagList { Node *pHead; Node //L u đ̣a chỉ Node đầu tiên trong List *pTail; //L u đ̣a chỉ của Node cúi cùng trong List }List; // đặt tên cho kiểu DSLK đ n 2. Danh sách liên k t 2.7. Các ệoại danh sách liên Ệ t - Danh sách liên Ệ t đơn (Linked List): Mỗi phần tử liên kết v i phần tử đứng sau nó trong danh sách pHead pTail 3A FA 3A A 4E 4E B 1F 1F C FA FA D NULL  Danh sách liên Ệ t đôi (Double-Linked List): Mỗi phần tử liên kết v i phần tử đứng tr c và sau nó trong danh sách pHead pTail 3A FA 3A NULL 4E A 4E 3A 1F B 1F 4E FA C FA 1F D NULL 2. Danh sách liên k t  Danh sách liên Ệ t đơn vòng (Circular-Linked List): Con trỏ Next của phần tử cuối danh sách liên kết v i phần tử đầu danh sách. pHead pTail 2.7. Các ệoại danh sách liên Ệ t 3A FA 3A A  4E 4E B 1F 1F C FA FA 3A D Danh sách liên Ệ t đôi vòng (Circular-Double Linked List): • Con trỏ Next của phần tử cuối danh sách liên kết v i phần tử đầu danh sách. • Con trỏ Prev của phần tử đầu danh sách liên kết v i phần tử cuối danh sách. pHead pTail 3A FA 3A FA 4E A 4E 3A 1F B 1F 4E FA C FA 1F D 3A 2. Danh sách liên k t 2.8. So sánh MảnỂ và Danh sách liên Ệ t M ng Kích th c cố định Các phần tử l u trữ tuần tự (địa chỉ tăng dần) trong b nh Phải dịch chuyển các phần tử khi Thêm/Xóa Truy xuất ngẫu nhiên Danh sách liên k t Số phần tử thay đổi tùy ý Các phần tử liên kết v i nhau bằng con trỏ Chỉ cần thay đổi con trỏ liên kết khi Thêm/Xóa Truy xuất tuần tự 3. L p trình v i danh sách liên k t đ n (Linked List) Cấu trúẾ t nỂ quát Ếể ơnỂ trửnể Khaià 1 2 3 4 5 Khaià oàthưà iệ àh oà ấuàt ú àda hàs hàliê àḱt Khaià oà à gu ê à ẫuàh void main() { KhởiàtạoàDSLK Nhập dữ liệu vào DSLK Các thao tác ử lý trên DSLK Hủ danh sách } C iàđặtà àh à o 215 3. L p trình v i danh sách liên k t đ n (Linked List) 3.1. Khai báo c u trúc DSLK 3.1.1. Khai báo c u trúc node cần dùng - Khai báo khi thành phần cuả node là đơn • VD1: Quản lý danh sách v i data chỉ là số nguyên typedef struct tagNode // L u thông tin b n thân node { int Info; /* L u đ̣a chỉ của node đ́ng sau*/ tagNode* pNext; Khaià oàthưà iệ }Node; Khaià àh oà ấuàt ú àDSLK Khaià oà à gu ê à ẫuàh void main() {àààààKhởiàtạoàD“LK Nhậpàdữàliệuà oàD“LK C àthaoàt à ửàlýàt ê àD“LK Hủ àda hàs h } C iàđặtà àh à o 3. L p trình v i danh sách liên k t đ n (Linked List) 3.1. Khai báo c u trúc DSLK 3.1.1. Khai báo c u trúc node cần dùng - Khai báo khi thành phần cuả node là m t struct • VD2: DSLK v i data là 1 struct //Cấu trúc thông tin của m t SV typedef struct SinhVien { char MSSV[10]; char HoTen[40]; float ĐTB; }SV; Khaià oàthưà iệ àh Khaià oà ấuàt ú àDSLK Khaià oà à gu ê à ẫuàh void main() {àààààKhởiàtạoàD“LK Nhậpàdữàliệuà oàD“LK C àthaoàt à ửàlýàt ê àD“LK Hủ àda hàs h } C iàđặtà àh à o //Cấu trúc của node v i thành phần ch́a cấu trúc SV typedef struct tagNode { SV Info; struct tagNode* pNext; }Node; 3. L p trình v i danh sách liên k t đ n (Linked List) 3.1. Khai báo c u trúc DSLK 3.1.2. Khai báo c u trúc qu n lý DSLK - Khai báo khi chỉ dùng pHead VD3: Node *pHead; - Khai báo cấu trúc khi dùng cả pHead và pTail VD4: typedef struct tagList { Node Node }List; *pHead; *pTail; Khaià oàthưà iệ àh Khaià oà ấuàt ú àDSLK Khaià oà à gu ê à ẫuàh void main() {àààààKhởiàtạoàD“LK Nhậpàdữàliệuà oàD“LK C àthaoàt à ửàlýàt ê àD“LK Hủ àda hàs h } C iàđặtà àh à o 3. L p trình v i danh sách liên k t đ n (Linked List) 3.2. Khởi tạo danh sách liên k t 3.2.1. Khi Ếểỉ dùng pHead pHead=NULL; 3.2.2. Khi dùng Ếấu trúc Do danh sách ban đầu ch a có (rỗng) nên địa chỉ của node đầu tiên và địa chỉ của node cuối cùng đều là NULL (không có). Khaià oàthưà iệ àh void InitList(List &l) { l.pHead=NULL; l.pTail=NULL; } Khaià oà ấuàt ú àD“LK Khaià oà à gu ê à ẫuàh void main() { KhởiàtạoàDSLK Nhậpàdữàliệuà oàD“LK C àthaoàt à ửàlýàt ê àD“LK Hủ àda hàs h } C iàđặtà àh à o 3. L p trình v i danh sách liên k t đ n (Linked List) CáẾ tểao táẾ Ếơ bản trên DSLK đơn Khaià oàthưà iệ àh Khaià oà ấuàt ú àD“LK Khaià oà à gu ê à ẫuàh i. Khai báo cấu trúc cần dùng ii. Kh i tạo 1 DSLK đơn (danh sách rỗng) void main() {àààààKhởiàtạoàD“LK iii. Nhập dữ liệu vào DSLK Nhậpàdữàliệuà oàD“LK C àthaoàt à ửàlýàt ê àDSLK • Tạo 1 node có data bằng X Hủ àda hàs h • Thêm m t phần tử có data là X vào } danh sách C iàđặtà àh à o  Thêm vào đầu/cuối danh sách  Thêm vào tr c/sau phần tử có khóa là Y  Thêm vào danh sách sao cho giữ đúng thứ tự tăng/giảm dần v. Duyệt danh sách • Liệt kê tất cả các phần tử có trong DSLK • Liệt kê tất cả các phần tử có trong DSLK theo điểu kiện • Đếm các phần tử thỏa điều kiện vi. Tìm m t phần tử có data bằng X vii. Hủy m t phần tử trong DSLK viii. Sắp xếp DSLK 3. L p trình v i danh sách liên k t đ n (Linked List) 3.3. Kểởi tạo ếanể sáẾể ệiên Ệ t 3.3.1. Tạo 1 phần t mới - Hàm trả về địa chỉ phần tử m i tạo VD5: Node* CreateNode(Data x) { Node *p; p = new Node;//Cấp phát vùng nh cho phần t if ( p==NULL) p exit(1); p->Info = x; //gán dữa lịu cho node p->pNext = NULL; Info Next return p; } 3. L p trình v i danh sách liên k t đ n (Linked List) 3.4. Duy t toàn bộ DSLK 3.4.1. Gi i thuật B1: p = pHead;/*p l u đ̣a chỉ của phần t đầu trong List */ B2: Trong khi ch a duỵt h t danh sách, tḥc hịn: + X lý phần t p//VD nh in giá tṛ Info + p=p->pNext;// chuyển sang phần t k 3. L p trình v i danh sách liên k t đ n (Linked List) 3.4. Duy t toàn bộ DSLK 3.4.2. Cài đặt void PrintList(List l) { Node *p; p=l.pHead; while(p!=NULL) { printf(“%5d”, p->Info); p=p->pNext; } } pHead 2f pTail f2 p 3 4f 3f 2f 3f 9 4f 5 … f2 7 NULL 3. L p trình v i danh sách liên k t đ n (Linked List) 3.5. Tạo 1 phần t mới - VD6: tạo node chứa cấu trúc sinh viên (SV) Node* CreateNode(SV x) { Node* TempNode; TempNode = new Node; //Hàm cấp phát vùng nh đ ng if(TempNode ==NULL) { printf(“không đủ b nh để cấp"); exit(1); } TempNode ->Info =x; //dữ lịu của Node TempNode ->Next = NULL; //Ch a có Node đ́ng sau return TempNode; } 3. L p trình v i danh sách liên k t đ n (Linked List) 3.6. Thêm 1 phần t vào DSLK - Nguyên tắẾ thêm: Khi thêm 1 phần tử vào List thì có làm cho pHead, pTail thay đổi? - Các vị trí Ếần thêm 1 pểần t vào List: ▪ Thêm vào đầu List đơn ▪ Thêm vào cuối List ▪ Thêm vào sau 1 phần tử q trong List 3. L p trình v i danh sách liên k t đ n (Linked List) 3.6. Thêm 1 phần t vào DSLK 3.6.1. Thêm 1 phần t vào đầu DSLK - Giải thuật thêm node p vào đầu danh sách liên kết đơn N u List rỗng thì begin + pHead = p; + pTail = pHead; end Ng c ḷi begin + p->pNext = pHead; + pHead = p end 3. L p trình v i danh sách liên k t đ n (Linked List) 3.6. Thêm 1 phần t vào DSLK 3.6.1. Thêm 1 phần t vào đầu DSLK - Cài đặt: void AddHead(List &l, Node* p) { if (l.pHead==NULL) pHead { l.pHead = p; NULL c2 l.pTail = l.pHead; } else { p->Next = l.pHead; l.pHead = p; } } pHead pTail c2 NULL c2 6 NULL pTail f2 c2 2f 2f 3 c2 6 2f NULL 4f 3f 2f 3f 9 4f 5 f2 … 7 NULL 3. L p trình v i danh sách liên k t đ n (Linked List) 3.6. Thêm 1 phần t vào DSLK 3.6.2. Thêm 1 phần t vào cuối DSLK - Giải thuật thêm node p vào cuối danh sách liên kết đơn N u List rỗng thì begin pHead = p; Tail = pHead; end Ng c ḷi begin pTail->Next=p; pTail=p end 3. L p trình v i danh sách liên k t đ n (Linked List) 3.6. Thêm 1 phần t vào DSLK 3.6.2. Thêm 1 phần t vào cuối DSLK - Cài đặt: void AddTail(List &l, Node* p) { if (l.pHead==NULL) pHead { l.pHead = p; NULL c2 l.pTail = l.pHead; } else { l.pTail->Next = p; l.pTail = p; } } pHead 2f pTail NULL c2 c2 6 NULL c2 pTail 6 f2 c2 3 4f 3f 2f 3f 9 4f 5 … f2 7 c2 NULL NULL 3. L p trình v i danh sách liên k t đ n (Linked List) 3.6. Thêm 1 phần t vào DSLK 3.6.3. Thêm 1 phần t p vào sau phần t q - Giải thuật thêm node p vào sau phần tử q Đặt q=pHead N u (q!=NULL) thì B1: p->pNext = q->pNext B2: + q->pNext = p + n u q = pTail thì pTail=p 3. L p trình v i danh sách liên k t đ n (Linked List) 3.6. Thêm 1 phần t vào DSLK 3.6.3. Thêm 1 phần t p vào sau phần t q - Cài đặt: void InsertAfterQ(List &l, Node *q, Node *p) if(q!=NULL) { { p->Next=q->Next; q->Next=p; if(l.Tail==q)/* n u q là node cúi thì chỉnh ḷi để p lơ node cúi*/ l.pTail=p; } else AddHead(l,p);// thêm q vào đầu list } pHead pTail 2f f2 q 3 4f 3f 2f 3f 9 5 … c2 4f c2 6 NULL 4f f2 7 NULL 3. L p trình v i danh sách liên k t đ n (Linked List) 3.6. Thêm 1 phần t vào DSLK 3.6.3. Thêm 1 phần t p vào sau phần t q - Cài đặt: void InsertAfterQ(List &l, Node *q, Node *p) if(q!=NULL) { { p->Next=q->Next; q->Next=p; if(l.Tail==q)/* n u q là node cúi thì chỉnh ḷi để p lơ node cúi*/ l.pTail=p; } else AddHead(l,p);// thêm q vào đầu list } pHead pTail 2f f2 q 3f 2f 3 3f 9 4f c2 c2 6 NULL 3. L p trình v i danh sách liên k t đ n (Linked List) 3.6. Thêm 1 phần t vào DSLK 3.6.4. Thực hành Bài 3.1: Cho cấu trúc nh sau, viết hàm thực hiện các yêu cầu: typedef struct tagNode { int Info; struct tagNode* pNext; }Node  B3.1.1. Viết hàm tạo DSLK nhận tham số là cấu trúc quản lý DSLK và số nguyên n. i. Hàm thực hiện tạo n node v i giá trị do ng i dùng nhập vào. ii. Hàm thực hiện tạo n node v i giá trị đ ợc phát sinh ngẫu nhiên sao cho giá trị thỏa điều kiện cho những tr ng hợp sau: - Các tr ng hợp số âm, số chẵn, số vừa âm vừa chẵn, … - Nằm trong khoảng từ 50 đến 100. - Nhỏ hơn 10 hoặc l n hơn hay bằng 50. - Giá trị các phần tử tăng dần. 3. L p trình v i danh sách liên k t đ n (Linked List) 3.6. Thêm 1 phần t vào DSLK 3.6.4. Thực hành Bài 3.1: Cho cấu trúc nh sau, viết hàm thực hiện các yêu cầu: typedef struct tagNode { int Info; struct tagNode* pNext; }Node  B3.1.2. Viết hàm chèn node p vào DSLK theo các yêu cầu: i. Chèn phần tử p (có Info=X) vào sau tất cả các phần tử trong DSLK có Info=Y. ii. Chèn p vào DSLK sao cho DSLK luôn chứa giá trị (Info) tăng dần. iii. Chèn phần tử p (có Info=X) vào tr c phần tử q (có Info=Y). 3. L p trình v i danh sách liên k t đ n (Linked List) 3.6. Thêm 1 phần t vào DSLK 3.6.4. Thực hành Bài t p 3.2: Cho các khai báo cấu trúc nh sau typedef struct SinhVien { char MSSV[10]; char HoTen[40]; float ĐTB; }SV; typedef struct tagNode { SV Info; struct tagNode* pNext; }Node; Viết hàm thực hiện các yêu cầu sau: i. Thêm 1 node p vào tr c node q trong DSLK, v i q.MSSV= “SV124M” và thông tin node p gồm: MSSV=“SV123M”, HoTen=“Nguyen Van X”, DTB=7.23 ii. Chèn p vào DSLK sao cho ĐTB luôn tăng dần. 3. L p trình v i danh sách liên k t đ n (Linked List) 3.7. Thực hi n các thao tác khác thông qua vi c duy t DSLK - Duyệt danh sách là thao tác th ng đ ợc thực hiện. Dựa vào thuật toán duyệt này để xử lý các phần tử trong danh sách nh : ▪ ▪ ▪ ▪ ▪ ▪ ▪ Đếm các phần tử trong danh sách. Tính trung bình các số có trong DSLK Kiểm tra DSLK chứa toàn số d ơng/số âm/số nguyên tố Tìm giá trị l n/nhỏ nhất trong DSLK Tìm vị trí chứa số l n/nhỏ nhất Tìm xem DSLK có chứa Info bằng giá trị X cho tr c. Tách DSLK A thành 2 DSLK B và C. V i B chỉ chứa các số nguyên tố, C chỉ chứa các số không là nguyên tố ▪ Hủy 1 hay nhiều node hoặc hủy toàn b danh sách ▪ … 3. L p trình v i danh sách liên k t đ n (Linked List) 3.7. Thực hi n các thao tác khác thông qua vi c duy t DSLK Bài 3.3: Viết hàm thực hiện các yêu cầu sau: Cho cấu trúc: typedef struct tagNode { int Info; struct tagNode* pNext; }Node  B3.3.1. Đ M: Viết hàm đếm số l ợng node i. ii. iii. iv. Có trong DSLK. int DemNode(LIST list) Số lần xuất hiện giá trị X. int DemX(LIST list, int x) Số l ợng số nguyên tố. int DemSNT(LIST list) Số l ợng giá trị (Info) là b i số của X int DemBoiX(LIST list,int x)  B3.3.2. T NG/TậUNG BÌNH: Viết hàm tính i. Tổng của t t c các node/tổng các số lẻ/tổng các số nguyên tố/ tổng các số âm có trong DSLK. int Tong(LIST list) ii. Trung bình của t t c các node/TB các số lẻ/TB các số nguyên tố/ TB các số âm có trong DSLK. float TrungBinh(LIST list) 3. L p trình v i danh sách liên k t đ n (Linked List) 3.7. Thực hi n các thao tác khác thông qua vi c duy t DSLK Bài 3.3: Viết hàm thực hiện các yêu cầu sau v i cấu trúc đư có là: typedef struct tagNode { int Info; struct tagNode* pNext; }Node  B3.3.3. TÌM: Các hàm tìm kiếm sau đây đ ợc viết d i 2 dạng: o Nếu tìm thấy, trả về true hoặc 1, ng ợc lại khi không tìm thấy hoặc DSLK rỗng, hàm trả về false hoặc 0 o Nếu tìm thấy, trả về con trỏ cho biết địa chỉ của node tìm thấy, ng ợc lại khi không tìm thấy hoặc DSLK rỗng, hàm trả về NULL. i. Giá trị X có xuất hiện trong DSLK hay không? int TimX(LIST list, int x) hoặc bool TimX(LIST list, int x) NODE* TimX(LIST list, int x) 3. L p trình v i danh sách liên k t đ n (Linked List) 3.7. Thực hi n các thao tác khác thông qua vi c duy t DSLK Bài 3.3: Viết hàm thực hiện các yêu cầu sau v i cấu trúc đư có là: typedef struct tagNode { int Info; struct tagNode* pNext; }Node  B3.3.3. TÌM: Các hàm tìm kiếm sau đây đ ợc viết d i 2 dạng: o Nếu tìm thấy, trả về giá tṛ của node, ng ợc lại khi không tìm thấy hoặc DSLK rỗng, hàm trả về -1 o Nếu tìm thấy, trả về con trỏ cho biết địa chỉ của node tìm thấy, ng ợc lại khi không tìm thấy hoặc DSLK rỗng, hàm trả về NULL. i. Số nguyên tố/số âm/số d ơng đầu tiên có trong DSLK. int TimSNTDauTien(LIST list) NODE* TimSNTDauTien(LIST list) ii. Giá trị l n/nhỏ nhất int TimMax(LIST list) NODE* TimMax(LIST list) iii. Giá trị “xa giá trị X nhất”/“gần giá trị X nhất”. int TimXaXNhat(LIST list, int x) NODE* TimXaXNhat(LIST list, int x) 3. L p trình v i danh sách liên k t đ n (Linked List) 3.7. Thực hi n các thao tác khác thông qua vi c duy t DSLK Bài 3.3: Viết hàm thực hiện các yêu cầu sau: Cho cấu trúc typedef struct tagNode { int Info; tagNode* pNext; }Node  B3.3.4. LI T KÊ: Viết hàm liệt kê: i. Các giá trị l n hơn X. ii. Các số nguyên tố có trong DSLK. iii. Số l ợng số nguyên tố.  B3.3.5. KI M TRA: Viết hàm kiểm tra DSLK (nếu đúng trả về 1, sai trả về 0): i. DSLK chứa toàn số chẵn/ số lẻ/ số âm/ số d ơng hay không? int KiemTraDSLKToanChan(LIST list) ii. DSLK đư đ ợc sắp tăng/ giảm dần hay ch a? int KiemTraDSLKTangDan(LIST list) 3. L p trình v i danh sách liên k t đ n (Linked List) 3.7. Thực hi n các thao tác khác thông qua vi c duy t DSLK Bài 3.3: Viết hàm thực hiện các yêu cầu sau, v i cấu trúc typedef struct tagNode { int Info; struct tagNode* pNext; }Node  B3.3.4. X LÝ KHÁC: Viết hàm thực hiện: i. Chuyển các phần tử có giá trị chẵn về đầu DSLK. ii. Chuyển các phần tử có giá trị âm về cuối DSLK. iii. Tìm c chung l n nhất của tất cả phần tử trong DSLK. 3. L p trình v i danh sách liên k t đ n (Linked List) 3.7. Thực hi n các thao tác khác thông qua vi c duy t DSLK Bài 3.3: Viết hàm thực hiện các yêu cầu sau, v i cấu trúc typedef struct tagNode { int Info; struct tagNode* pNext; }Node  B3.3.5. NH P TÁCH DSLK: Viết hàm thực hiện: i. Tách DSLK LA thành 2 DSLK LB và LC. V i LB chỉ chứa các số nguyên tố, LC chỉ chứa các số không là nguyên tố? Thực hiện t ơng tự cho các tr ng hợp số âm/số d ơng, số chẵn/số lẻ. ii. Nhập 2 DSLK LB và LC vào LA sao cho ngay khi đ a các giá trị từ LB và LC vào LA, giá trị các node trong LA luôn đ ợc sắp tăng dần (không thực hiện sắp xếp DSLK LA)? 3. L p trình v i danh sách liên k t đ n (Linked List) 3.7. Thực hi n các thao tác khác thông qua vi c duy t DSLK 3.7.2. Thực hành Bài 3.4: Viết hàm thực hiện các yêu cầu sau: ii. Trong VD2, lần l ợt viết các hàm: typedef struct SinhVien { char MSSV[10]; char HoTen[40]; float ĐTB; }SV; typedef struct tagNode { SV Info; struct tagNode* pNext; }Node;  B3.4.1. Viết hàm in ra họ tên và điểm trung bình của những SV có DTB từ 7 đến 8.  B3.4.2. Viết hàm đếm số l ợng sinh viên có DTB >=8.  B3.4.3. Viết hàm tìm xem sinh viên có học tên là X có xuất hiện trong DSLK hay không? (trả về true/false) 3. L p trình v i danh sách liên k t đ n (Linked List) 3.8. Hủy phần t trong DSLK đơn - Nguyên tắẾ: Phải cô lập phần tử cần hủy tr c hủy. - Các vị trị Ếần ểủỔ  Hủy phần tử đứng đầu List  Hủy phần tử có khoá bằng X  Huỷ phần tử đứng sau q  Hủy toàn b DSLK - L u ý: Khi các phần tử trong DSLK đơn đ ợc cấp phát vùng nh đ ng bằng hàm new, thì sẽ đ ợc giải phóng vùng nh bằng hàm delete. 3. L p trình v i danh sách liên k t đ n (Linked List) 3.8. Hủy phần t trong DSLK đơn 3.8.1. Hủy phần t đầu trong DSLK  Gi i thuật ▪ N u (pHead!=NULL) thì ▪ B1: p=pHead ▪ B2: + pHead = pHead->pNext + delete (p) ▪ B3: N u pHead==NULL thì pTail=NULL 3. L p trình v i danh sách liên k t đ n (Linked List) 3.8. Hủy phần t trong DSLK đơn 3.8.1. Hủy phần t đầu trong DSLK - Cài đặt: hủy thành công hàm trả về 1, ng ợc lại hàm trả về 0. int RemoveHead(List &l) { if(l.pHead != NULL) Node * p = l.pHead; { l.pHead = l.pHead->pNext; delete p; //n u sau khi xóa DSLK không còn node nào if(l.pHead == NULL) l.pTail=NULL; return 1; pHead pTail q NULL f2 } NULL NULL f2 f2 return 0; p f2 } NULL 7 NULL pHead 3f 2f pTail f2 p 4f 3f 2f 3 NULL 2f 3f 9 4f c2 5 … f2 7 c2 NULL 3. L p trình v i danh sách liên k t đ n (Linked List) 3.8. Hủy phần t trong DSLK đơn 3.8.2. Hủy phần t sau phần t q trong List  Gi i thuật N u (q!=NULL) thì //q tồn ṭi trong List ▪ B1: p=q->pNext; // p là phần t cần hủy ▪ B2: N u (p!=NULL) thì//q không ph i phần t cúi + q->pNext=p->pNext;//tách p ra khỏi xâu + n u (p== pTail)//node cần hủy là node cúi pTail=q; + delete p;// hủy p 3. L p trình v i danh sách liên k t đ n (Linked List) 3.8. Hủy phần t trong DSLK đơn 3.8.2. Hủy phần t sau phần t q trong List  Cài đặt int RemoveAfterQ(List &l, Node *q) { if(q!=NULL) { Node * p=q->Next; //p là node cần xoá if(p!=NULL) //q không phài là node cúi { if(p==l.Tail) //node cần xoá là node cúi l.Tail=q; // cập nhật ḷi pTail q->Next=p->Next; delete p; } return 1; } else return 0; } pHead pTail p NULL q NULL 3f 2f 2f f2 3f 2f 3 3f 9 4f 4f c2 5 … f2 7 NULL 3. L p trình v i danh sách liên k t đ n (Linked List) 3.8. Hủy phần t trong DSLK đơn 3.8.2. Hủy phần t sau phần t q trong List  Cài đặt int RemoveAfterQ(List &l, Node *q) { if(q!=NULL) { Node * p=q->Next; //p là node cần xoá if(p!=NULL) //q không phài là node cúi { if(p==l.Tail) //node cần xoá là node cúi l.Tail=q; // cập nhật ḷi pTail q->Next=p->Next; delete p; } return 1; } else p NULL f2 return 0; } pHead pTail q NULL 4f 2f 4f f2 3f 2f 3 3f 9 f2 4f 4f c2 5 NULL f2 7 NULL 3. L p trình v i danh sách liên k t đ n (Linked List) 3.8. Hủy phần t trong DSLK đơn 3.8.3. Hủy phần t sau có khóa là X  Gi i thuật B B c 1: Tìm phần t c 2: p có khoá bằng x, và q đ́ng tr N u (p!=NULL) thì //tìm thấy phần t có khoá bằng x Hủy p ra khỏi List bằng cách hủy phần t Ng đ́ng sau q c ḷi Báo không tìm thấy phần t c p có khoá 3. L p trình v i danh sách liên k t đ n (Linked List) 3.8. Hủy phần t trong DSLK đơn 3.8.3. Hủy phần t sau có khóa là X trong List  Cài đặt int RemoveX(List &l, int x) { Node *p,*q = NULL; p=l.Head; while((p!=NULL)&&(p->Info!=x))//khi ch a tìm thấy và ch a tìm h t trên danh sƠch*/ { q=p; p=p->Next; } if(p==NULL) //không tìm thấy phần t có khoá bằng x return 0; if (q!=NULL)//tìm thấy phần t có khoá bằng x DeleteAfterQ(l,q); else //phần t cần xoá nằm đầu List RemoveHead(l); return 1; } pHead 2f Tìm X=9 pTail p f2 2f 3 q 2f NULL 2f 3f 3f 3f 9 b2 4f 4f 5 b2 7 NULL 3. L p trình v i danh sách liên k t đ n (Linked List) 3.8. Hủy phần t trong DSLK đơn 3.8.4. Hủy toàn bộ DSLK  Gi i thuật ▪ B c 1: Trong khi (danh sách ch a h t) tḥc hịn • B11: p = pHead; pHead = pHead->pNext;// cập nhật pHead • B12: ▪ B Hủy p c 2: pTail = NULL;/* Trở ḷi cấu trúc List ban đầu khi DSLK rỗng */ 3. L p trình v i danh sách liên k t đ n (Linked List) 3.8. Hủy phần t trong DSLK đơn 3.8.4. Hủy toàn bộ DSLK  Cài đặt void RemoveList(List &l) { Node *p; while(l.pHead!=NULL)//còn phần t trong List { p = l.pHead; l.pHead = p->pNext; delete p; } } pHead 2f 3f pTail p b2 2f 3 2f NULL 3f 3f 9 b2 4f 4f 5 b2 7 NULL 3. L p trình v i danh sách liên k t đ n (Linked List) 3.8. Hủy phần t trong DSLK đơn 3.8.4. Hủy toàn bộ DSLK  Cài đặt void RemoveList(List &l) { Node *p; while(l.pHead!=NULL)//còn phần t trong List { p = l.pHead; l.pHead = p->pNext; delete p; } } pHead 4f 3f pTail b2 p 2f 3f 3f 9 b2 4f 4f 5 b2 7 NULL 3. L p trình v i danh sách liên k t đ n (Linked List) 3.8. Hủy phần t trong DSLK đơn 3.8.4. Hủy toàn bộ DSLK  Cài đặt void RemoveList(List &l) { Node *p; while(l.pHead!=NULL)//còn phần t trong List { p = l.pHead; l.pHead = p->pNext; delete p; } } pHead 4f b2 pTail b2 p 4f 3f b2 4f 5 b2 7 NULL 3. L p trình v i danh sách liên k t đ n (Linked List) 3.8. Hủy phần t trong DSLK đơn 3.8.4. Hủy toàn bộ DSLK  Cài đặt void RemoveList(List &l) { Node *p; while(l.pHead!=NULL)//còn phần t trong List { p = l.pHead; l.pHead = p->pNext; delete p; } l.pTail=l.pHead; } pHead 4f b2 NULL pTail b2 p b2 b2 NULL 7 NULL 3. L p trình v i danh sách liên k t đ n (Linked List) 3.9. Sắp x p DSLK đơn 3.9.1. Có hai cách ti p Ế n - Cách 1: Thay đổi thành phần Info pHead pTail 3f 4 c4 c4 7 5e pHead 5e 6 NULL pTail 3f 4 c4 c4 6 5e 5e 7 NULL 3. L p trình v i danh sách liên k t đ n (Linked List) 3.9. Sắp x p DSLK đơn 3.9.1. Có hai cách ti p Ế n - Cách 2: Thay đổi thành phần pNext (thay đổi trình tự móc nối của các phần tử sao cho tạo lập nên đ ợc thứ tự mong muốn) pHead pTail 3f 4 c4 c4 7 pHead c4 3f 4 5e 7 5e pTail NULL 5e 6 NULL 5e 6 c4 3. L p trình v i danh sách liên k t đ n (Linked List) 3.9. Sắp x p DSLK đơn 3.9.2. u, nể ợẾ đi m Ếủa 2 cách ti p Ế n - Thay đổi thành phần Info (dữ liệu) ▪ u: Cài đặt đơn giản, t ơng tự nh sắp xếp mảng ▪ Nh ợc: • Đòi hỏi thêm vùng nh khi hoán vị n i dung của 2 phần tử  chỉ phù hợp v i những DSLK có kích th c Info nhỏ. • Khi kích th c Info (dữ liệu) l n chi phí cho việc hoán vị thành phần Info l n  thao tác sắp xếp chậm 3. L p trình v i danh sách liên k t đ n (Linked List) 3.9. Sắp x p DSLK đơn 3.9.2. u, nể ợẾ đi m Ếủa 2 cách ti p Ế n - Thay đổi thành phần pNext ▪ u:  Kích th c của tr ng này không thay đổi  không phụ thu c vào kích th c bản chất dữ liệu l u tại mỗi node.  Thao tác sắp xếp nhanh ▪ Nh ợc: Cài đặt phức tạp 3. L p trình v i danh sách liên k t đ n (Linked List) 3.9. Sắp x p DSLK đơn 3.9.3. Dùng tểu t toán SelectionSort đ sắp ồ p DSLK (CƠch 1: thay đổi thơnh phần Info) void SelectionSort(List &l) { Node *p,*q,*min; p=l.pHead; while(p!=l.pTail) { min=p; q=p->pNext; while(q!=NULL) { if(q->Info < min->Info) min=q; q=q->pNext; } Swap(min->Info,p->Info); p=p->pNext; } } 3. L p trình v i danh sách liên k t đ n (Linked List) 3.10. TH C HÀNH Bài tểựẾ hành 3.5: Chèn node có giá trị x vào phía sau node có giá trị l n nhất (giả sử danh sách không có giá trị trùng nhau) void ChenXSauMax(LIST &list, int x); Bài tểựẾ hành 3.6: Xóa node có giá trị x xuất hiện đầu tiên trong danh sách (nếu có xóa: trả về true, ng ợc lại trả về false) bool XoaX(LIST &list, int x); Bài tểựẾ ểànể 3.7: Sắp tăng dslk bằng cách thay đổi thành phần link (pNext) void SapTang(LIST &list); 3. L p trình v i danh sách liên k t đ n (Linked List) 3.10. TH C HÀNH Bài tểựẾ ểànể 3.8: Viết ch ơng trình thực hiện yêu cầu sau: Tổ chức DSLK v i n i dung (Info) không trùng nhau. Nếu Info nhập vào ch a xuất hiện trong DSLK thì tạo node m i, nh ng nếu Info nhập vào trùng v i Info đư có thì không tạo thêm node m i mà chỉ tăng số lần xuất hiện của Info lên. Ví dụ: số 4 xuất hiện 1 lần, số 8 xuất hiện 3 lần, … Các thao tác thực hiện t ơng tự nh trên DSLK đơn. 4. CÁC DANH SÁCH LIểN ḰT KHỌNG Đ N (SV tự cài đặt các ếạnỂ danh sách liên Ệ t và báo cáo) i. Bài tập 3.11: DSLK đôi ii. Bài tập 3.12: DSLK đơn vòng iii. Bài tập 3.13: DSLK đôi vòng Các thao tác thực hiện t ơng tự nh trên DSLK đơn nh : i. Khai báo cấu trúc cần dùng ii. Kh i tạo 1 DSLK rỗng iii. Tạo 1 node có data bằng X iv. Thêm m t phần tử có data là X vào danh sách Thêm vào đầu danh sách Thêm vào cuối danh sách Thêm vào tr c/sau phần tử có khóa là Y Thêm vào danh sách sao cho giữ đúng thứ tự tăng/giảm dần v. Duyệt DSLK vi. Tìm m t phần tử có data bằng X vii. Hủy m t phần tử trong DSLK viii. Sắp xếp DSLK 5. Các d ng ph i h p khác d a trên DSLK (SV cài đặt các ếạnỂ danh sách liên Ệ t và báo cáo) i. Bài tập 3.14: Mảng các DSLK: trong đó, thành phần dữ liệu: • Mảng: mỗi phần tử là 1 cấu trúc gồm pHead và pTail. • Node: gồm Data là số nguyên và liên kết là pointer chỉ đến Node t ơng ứng. Alist Alist Alist Alist int int NULL Npointer Npointer Npointer int int int Npointer Npointer Npointer int Alist NULL Npointer int Npointer Alist NULL Alist int int Npointer int Npointer Alist NULL 5. Các d ng ph i h p khác d a trên DSLK (SV cài đặt các ếạnỂ danh sách liên Ệ t và báo cáo) ii. Bài tập 3.15: DSLK v i n i dung chứa 1 DSLK khác Có nhu cầu l u các số nguyên từ 0-1000. Trong đó, thành phần của các loại node nh sau: - DSLK cấp 1 (main): mỗi phần tử là 1 cấu trúc gồm: • Liên kết: các node liên kết qua 1 pointer. • pHead, pTail để quản lý các DSLK con (Sub). • Node thứ 1 sẽ quản lý các số (do ng i dùng nhập vào) từ 0-999, node thứ 2 sẽ quản lý các số từ 1000-1999, … Khi số nhập vào đư có, ch ơng trình sẽ báo lỗi. • Kh i đầu DSLK là rỗng. Node chỉ đ ợc tạo ra khi có phát sinh 1 giá trị thu c phạm vi node quản lý. - DSLK cấp 2 (sub): • Data: là số nguyên (do ng i dùng nhập vào), Khi giá trị đ ợc thêm vào danh sách sẽ luôn đ ợc sắp xếp tang dần. • Liên kết: là pointer chỉ đến Node t ơng ứng. 5. Các d ng ph i h p khác d a trên DSLK (SV cài đặt các ếạnỂ danh sách liên Ệ t và báo cáo) ii. Bài tập 3.15 : Minh họa gợi ý DSLK v i n i dung chứa 1 DSLK khác. pMHead pMTail [option] [option] [option] pMain pMain pMain pSHead pSHead pSHead pSTail pSTail pSTail NULL 7 1035 7105 Npointer Npointer Npointer 15 1838 Npointer Npointer 839 Npointer Chương 6 T CH C NGĂN X́P (Stack) N I DUNG 1. Gi i thiệu 2. Định nghĩa 3. Các thao tác cơ bản 4. Xây dựng Stack dựa trên cấu trúc mảng 1 chiều 5. Xây dựng Stack dựa trên cấu trúc DSLK 1. Gi i thi u v Stack Data Structured Linear Data Structured Array Queue Non Linear Data Structured Stack C u trúc d li u dạng tuy n tính (Linear Data Structured)? Trong cấu trúc dữ liệu dạng tuyến tính: • Dữ liệu đ ợc sắp xếp liên tục theo 1 trật tự đư đ ợc quy c tr c. • Việc duyệt các phần tử dữ liệu đ ợc thực hiện đơn giản bằng cách duyệt tuần tự từ phần tử 1, phần từ 2, … đến phần tử cuối. • Việc truy cập hoặc thay thế các phần tử đ ợc thực hiện trong b nh . 1. Gi i thi u v Stack Top Bottom Chồng khay cà phê Chồng tiền xu Chồng sách Chồng áo sơ mi 2. Đ nh nghĩa - Stack là 1 cấu trúc: • Gồm nhiều phần tử có thứ tự. • Việc thêm vào hoặc lấy phần tử ra chỉ thực hiện từ 1 phía  Hoạt đ ng theo cơ chế “Vào sau – Ra tr ớẾ” (LIFO – Last In, First Out) Đỉnh Stack 3. Các thao tác c b n trên Stack Push • • • • InitStack: kh i tạo Stack rỗng IsEmpty: kiểm tra Stack rỗng? IsFull: kiểm tra Stack đầy? Push: thêm 1 phần tử vào đỉnh Stack  có thể làm Stack đầy • Pop: lấy ra 1 phần tử từ đỉnh Stack  có thể làm Stack rỗng • StackTop: kiểm tra phần tử đỉnh Stack  không làm thay đổi Stack Pop 3. Các thao tác c b n trên Stack 3.1. Minh họa thao tác InitStack StkCount=0 3. Các thao tác c b n trên Stack 3.2. Minh họa thao tác IsEmpty  return true  return false or or 3. Các thao tác c b n trên Stack 3.3. Minh họa thao tác IsFull  return true  return false or or 3. Các thao tác c b n trên Stack 3.4. Minh họa thao tác Push Data StkCount++ 3. Các thao tác c b n trên Stack 3.5. Minh họa thao tác Pop StkCount-- Data 3. Các thao tác c b n trên Stack 3.6. Minh họa thao tác StackTop  Ngăn xếp không thay đổi StkCount không thay đổi Data ? 4. M t s ng d ng c a stacks Stack là cấu trúc đ ợc dung phổ biến trong CNTT: 4.1.Compilers  Kiểm tra sự sắp xếp của các cấu trúc lồng nhau. Vd phân tích cú pháp để kiểm tra tính hợp lệ của các cặp ngoặc (brackets) trong 1 biểu thức. Valid inputs {} ({[]}) {[]()} [{({}[]({}))}] 280 Invalid Inputs {(} ([(()]) {}[]) [{)}(]}] 4. M t s ng d ng c a stacks  Đảo ng ợẾ Ếểuỗi 4.1.Compilers • Để đảo ng ợc chuỗi, lần l ợt đi từ trái sang phải, cắt từng ký tự đ a vào stack cho đến khi cắt hết chuỗi. • Lấy từ stack ra để có chuỗi đảo ng ợc. • VD: Đảo ng ợc chuỗi “REVERSE” E ESREVER S R E V E R 281 4. M t s ng d ng c a stacks 4.2. Virtual machines - Biểu diễn biểu thức đại số: gồm 3 dạng • Trung tố (Infix): đặt toán tử nằm giữa các toán hạng. VD: a + b • Ti n tố (Prefix hay “ký pháp Ba Lan” - Polish notation): đặt toán tử lên tr c các toán hạng. VD: + a b • H u tố (Postfix hoặc - “ký pháp nghịch đảo Ba Lan” Reverse Polish notation): các toán tử sẽ đ ợc đặt sau các toán hạng. VD: a b + 4. M t s ng d ng c a stacks 4.2. Virtual machines - Chuyển từ Infix sang Postfix: • VD1: Cho 2 +(4-1)*5 Step Expression Current Symbol Action Performed Stack Status Append to postfix Postfix Expression 1 2 +(4-1)*5 2 2 2 +41-*5 + PUSH + + 2 3 2 +41-5* ( PUSH ( +( 2 4 2 41-5*+ 4 1 ) * 5 2 Append to postfix PUSH - 24 +(- Append to postfix 24 241 POP - +( 241- POP ( + 241- PUSH * +* 241- +* 241-5 + 241-5* Append to postfix POP * POP + 241-5*+ 4. M t s ng d ng c a stacks 4.2. Virtual machines - Chuyển từ Infix sang Postfix: • VD2: Cho a – (b + c * d ) / e Current Symbol Action Performed Stack Status Append to postfix a Postfix Expression a - PUSH - - a ( PUSH ( -( a -( ab Append to postfix b + PUSH + Append to postfix c * PUSH * Append to postfix d ) / -(+ -(+ abc -(+* -(+* abcd POP * - POP UNTIL ( -(+ abcd* POP + -( abcd*+ POP ( - abcd*+ PUSH / -/ abcd*+ Append to postfix e POP / - UNTIL EMPTY POP - abcd*+e - abcd*+e/ abcd*+e/- 4. M t s ng d ng c a stacks 4.2. Virtual machines - L ợng giá các biểu thức dạng Postfix. Vd: • Khi duyệt đến phép tính (c ng, trừ, nhân, chia, …), lấy 2 số ra khỏi stack để thực hiện. • Đặt kết quả vừa tính đ ợc vào stack để ch đến l ợt tính toán sau đó. • VD: Cho 241-5*+ Push 1 1 Push 4 4 Push 2 2 Push 5 4-1=3 5 3 3 2 2 3*5=15 15 2 2+15=17 17 4. M t s ng d ng c a stacks 4.2. Virtual machines - Trong máy tính, các phép tính đ ợc sắp xếp theo trật tự đư đ ợc quy c tr c (Reverse Polish Notation). Vd: • (5 + 3) * 6 đ ợc sắp xếp lại thành 5 3 + 6 * • 5 + 3 * 6 đ ợc sắp xếp lại thành 5 3 6 * + (i) Tính 5 3 + 6 * ? + 3 5 (ii) Tính 5 3 6 * + ? (iii) Tính 7 4 5 3 * + 2 / - (i) (ii) 6 8 * 6 8 48 4. M t s ng d ng c a stacks 4.3. Operating systems: Thực thi các hàm hoặc ph ơng thức đ ợc gọi thông qua program stack. a1 void main 1e void X() 31 void Y() 4a void Z() a2 { 1f { 32 { 4b { … … … … 33 Z(); 4c a9 … 24 Y(); 34 … 4d aa X(); 25 … ab … … … … … … } } } } 34 program stack 25 25 ab ab ab program stack program stack program stack 287 4. M t s ng d ng c a stacks 4.4. Artificial intelligence: finding a path • Theo dõi các lựa chọn tr c đó. Vd nh trong thuật toán backtracking • Theo dõi các lựa chọn ch a đ ợc thực hiện. Vd nh trong việc tạo tìm đ 288 ng đi trong m t mê cung. 4. M t s ng d ng c a stacks 4.4. Artificial intelligence: Cho sơ đồ các tuyến đ thành phố. Z Y W S R P X Q 289 T ng bay giữa các Finding a Path: Có thể tìm 1 đ ng đi từ bất kỳ thành phố (TP) C1 nào đến 1 TP C2 khác bằng cách dùng stack: - Đầu tiên đặt TP kh i hành vào đáy stack và đánh dấu để biết TP đó đư đ ợc xét. - Chọn bất kỳ mũi tên nào ra khỏi TP để đến TP khác v i điều kiện TP đến đó ch a đ ợc đánh dấu đư đ ợc xét. - Đ a TP m i chọn vào stack. - Nếu TP m i chọn là TP cần đến thì dừng lại. - Ng ợc lại, lặp lại việc chọn tiếp TP khác nh cách đư thực hiện trên cho đến khi tìm đ ợc TP cần đến - Khi tất cả các TP đều đư đ ợc xét nh ng vẫn ch a tìm thấy đ ng đi  không có đ ng đi. 4. M t s ng d ng c a stacks 4.4. Artificial intelligence: Cho sơ đồ các tuyến đ thành phố. Finding a Path: Cần tìm đ Z R S P X Q Y W R P stack stack ng đi từ P đến Y: - Đầu tiên đặt P đáy stack và đánh dấu để biết TP đó đư đ ợc xét. Y W ng bay giữa các T - Chọn (ngẫu nhiên trong số những TP có thể chọn) R là TP kế tiếp, đ a vào stack và đánh dấu R đư đ ợc xét. - Từ R không có đ ng đi tiếp  lấy R ra khoải stack. - Chọn W (lựa chọn duy nhất còn lại) là TP kế tiếp, đ a vào stack và đánh dấu W đư đ ợc xét. - Chọn Y (ngẫu nhiên trong số những TP có thể chọn), đ a vào stack và đánh dấu Y đư đ ợc xét. - Do Y là TP cần đến nên dừng thuật toán. - Lần l ợt lấy ra từ stack để có đ ng đi: Y  W  P 5. S d ng m ng 1 chi u lƠm Stack 5.1. Đặc đi m • Viết ch ơng trình dễ dàng, nhanh chóng. • Bị hạn chế do số l ợng phần tử cố định. • Tốn chi phí tái cấp phát và sao chép vùng nh nếu sử dụng mảng đ ng. 5. S d ng m ng 1 chi u lƠm Stack 5.2. Minh họa 9 8 7 6 5 4 3 2 1 0 StkCount=3 (Đỉnh Stack) 9 3 6 0 1 2 3 4 5 6 7 8 9 StkCount=3 6 3 9 Stack Minh họa Stack có khả năng chứa tối đa 10 phần tử và hiện đang chứa 3 phần tử 5. S d ng m ng 1 chi u lƠm Stack 5.3. Cài đặt 5.3.1. Khai báo c u trúc Stack //Giả sử Stack chứa các phần tử kiểu nguyên typedef struct STACK { int* StkArray; //m ng ch́a các phần t }; int StkMax; //ś phần t (śc ch́a) t́i đa int StkCount; // ṿ trí đỉnh Stack 5. S d ng m ng 1 chi u lƠm Stack 5.3. Cài đặt 5.3.2. Thao tác “Khởi tạo Stack rỗng” int InitStack (STACK& s, int MaxItems) { s.StkArray = new int[MaxItems]; if (s.StkArray == NULL) return 0; //Không cấp phát đ c b nh s.StkMax = MaxItems;//śc ch́a t́i đa s.StkCount = 0;//ch a có phần t nào trong Stack return 1; // khởi ṭo thành công } 5. S d ng m ng 1 chi u lƠm Stack 5.3. Cài đặt 5.3.3. Thao tác “Ki m tra Stack rỗng” bool IsEmpty(STACK s) { /*return true n u Stack rỗng, return false n u không rỗng*/ return (s.StkCount==0); } 5. S d ng m ng 1 chi u lƠm Stack 5.3. Cài đặt 5.3.4. Thao tác “Ki m tra Stack đầy” bool IsFull(STACK s) { /*return true n u Stack đầy, return false khi ch a đầy*/ return (s.StkCount>s.StkMax); } 5. S d ng m ng 1 chi u lƠm Stack 5.3. Cài đặt 5.3.5. Thao tác thêm một phần t vào đỉnh Stack bool Push(STACK& s, int NewItem) { if (IsFull(s)) return false; //stack đầy không thể thêm s.StkArray[s.StkCount] = NewItem; s.StkCount++; return true; } //thêm thành công 5. S d ng m ng 1 chi u lƠm Stack 5.3. Cài đặt 5.3.6. Thao tác l y ra 1 phần t từ đỉnh Stack bool Pop(STACK& s, int & OutItem) { if (IsEmpty(s)) return false; //Stack rỗng  không lấy đ s.StkCount--; OutItem = s.StkArray[s.StkCount]; return true; } //lấy ra thành công c 5. S d ng m ng 1 chi u lƠm Stack 5.3. Cài đặt 5.3.7. Thao tác ki m tra phần t làm thay đổi Stack) ở đỉnh Stack (không bool StackTop(STACK s, int& OutItem) { if (IsEmpty(s)) return false;//Stack rỗng, không lấy ra đ c OutItem = s.StkArray[s.StkCount-1]; return true; } //lấy ra thành công 6. TH C HÀNH Bài t p 6.1:Viết ch ơng trình thực hiện yêu cầu sau, v i prototype đ ợc đề nghị là: int PushDecToOthers(Stack &stack, int DecValue, int base) /* h̀m tr̉ về 1 ńu th̀nh công, ngược lại tr̉ về 0, DecValue l̀ gí tṛ hệ thập phân, base là cơ ś cần đổi*/ void PopDecToOthers(Stack &stack) /*h̀m sẽ gọi h̀m Pop đã có đ̉ xuất ḱt qủ ra m̀n hình*/ VI T CH NG TRÌNH S D NG STACK (V I CTDL S D NG LÀ M NG 1 CHI U) Đổi giá trị của 1 số thực không âm từ cơ số 10 sang cơ số 2, 8, 16 Nhập giá tṛ ḥ thập phân: X Ḱt qủ xuất ra màn hình: Giá tṛ t ng ́ng của X ở ḥ 2 là: Y Giá tṛ t ng ́ng của X ở ḥ 8 là: Z Giá tṛ t ng ́ng của X ở ḥ 16 là: W Trong đó • • X là giá tṛ do người dùng nhập vào. Y, Z, W là ḱt qủ tḥc hiện của chương trình 6. TH C HÀNH Bài t p 6.2: Viết ch ơng trình thực hiện: i. Đảo ng ợc 1 chuỗi do ng i dùng nhập vào • Lần l t đ a t ng ký ṭ của chuỗi str vào stack cho đ n khi h t chuỗi str. Hàm return 1 n u thành công, ng c ḷi return 0 int PushStringToStack(Stack &stack, char *str) • Hàm tr v̀ chuỗi đ c lấy ra t toàn b n i dung có trong stack char* PopFromStack(Stack &stack) ii. + Cho nhập biểu thức dạng Infix. + Sử dụng stack để chuyển biểu thức vừa nhập sang dạng Postfix. + Thực hiện tính toán giá trị cho biểu thức Postfix vừa có 6. TH C HÀNH Bài t p 6.3: Viết ch ơng trình sử dụng DSLK v i CTDL đ ợc đề nghị nh sau: typedef struct typedef struct tagStack typedef struct node node { Node *pHead; { {int info; int info; Node *pTail; struct node * pNext; struct node * pNext; }Stack; }Node; }Node; Lần l typedef ợt viết cácNode* hàm: STACK; i.void InitStack (Stack stack) ii.int IsEmpty (Stack stack) //thành công trả về 1, ng ợc lại trả về 0 iii. Node* CreateNode (int info) //trả về NULL nếu không cấp phát đ ợc đ ợc cho node m i, ng ợc lại trả về địa chỉ của Node vừa đ ợc tạo m i đư chứa tham số info. iv.void Push(Stack &stack, Node *p) v.void Pop(Stack &stack, Node *p) vi.void StackTop(Stack &stack, int &x) vii.void PushDecToOther(Stack &stack, int DecValue, int base) viii.void PopDecToOther(Stack &stack, int DecValue, int base) /* đổi m t số (DecValue) từ cơ số 10 sang các cơ số khác (base) */ Chương 7 HÀNG Đ I (Queue) 1. GI I THI U Phòng vé 1. GI I THI U - Queue là m t cấu trúc: • Gồm nhiều phần tử có thứ tự. • Hoạt đ ng theo cơ chế “Vào tr ớẾ, ra tr ớẾ” (FIFO - First In First Out) Front (hay Head) Rear (hay Tail) 2. GI I THI U - M t số dạng của Queues: • Hàng đợi tuy n tính (Linear Queues): Tổ chức queue theo nghĩa thông th ng. 0 1 2 3 4 5 6 7 • Hàng đợi vòng (Circular Queues): Giải quyết việc thiếu b nh khi sử dụng queue. • Hàng đợi ưu tiên (Priority Queues):  Mỗi phần tử có kết hợp thêm thông tin về đ u tiên.  Khi ch ơng trình cần lấy m t phần tử khỏi queue, nó sẽ xét những phần tử có đ u tiên cao tr c. priority=1 0 1 2 3 4 5 6 7 3 4 5 6 7 3 4 5 6 7 priority=2 0 1 2 priority=3 0 1 2 2. M t s ng d ng c a Queue 2.1. Tìm ki m theo chi u rộng trên đồ thị (BFS - Breadth First Search) Cho đồ thị nh hình bên. Xuất phát từ đỉnh 0, yêu cầu duyệt qua tất cả các đỉnh Queue Mảng ChuaXet Mảng LuuVet -1 0 -1 -1 -1 -1 -1 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 F T T T T T T T T T T T T 0 1 2 3 4 5 6 7 8 9 10 11 12 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2. M t s ng d ng c a Queue 2.1. Tìm ki m theo chi u rộng trên đồ thị (BFS - Breadth First Search) Queue Mảng ChuaXet Mảng LuuVet 0 1 3 11 -1 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 F F T F T T T T T T T F T 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 -1 0 -1 -1 -1 -1 -1 -1 -1 0 -1 2. M t s ng d ng c a Queue 2.1. Tìm ki m theo chi u rộng trên đồ thị (BFS - Breadth First Search) Queue Mảng ChuaXet Mảng LuuVet 0 1 3 11 -1 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 F F T F T T T T T T T F T 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 -1 0 -1 -1 -1 -1 -1 -1 -1 0 -1 2. M t s ng d ng c a Queue 2.1. Tìm ki m theo chi u rộng trên đồ thị (BFS - Breadth First Search) Lấy đỉnh 1 ra nhưng không tìm thấy đường đi tiếp Queue Mảng ChuaXet Mảng LuuVet 0 1 3 11 -1 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 F F T F T T T T T T T F T 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 -1 0 -1 -1 -1 -1 -1 -1 -1 0 -1 2. M t s ng d ng c a Queue 2.1. Tìm ki m theo chi u rộng trên đồ thị (BFS - Breadth First Search) Lấy đỉnh 3 ra, tìm thấy hai đỉnh 5 và 6 Queue Mảng ChuaXet Mảng LuuVet 0 1 3 11 5 6 0 1 2 3 4 5 6 7 8 9 10 11 12 F F T F T F F T T T T F T 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 -1 0 -1 3 3 -1 -1 -1 -1 0 -1 2. M t s ng d ng c a Queue 2.1. Tìm ki m theo chi u rộng trên đồ thị (BFS - Breadth First Search) Lấy đỉnh 11 ra, tìm thấy hai đỉnh 9 và 10 Queue Mảng ChuaXet Mảng LuuVet 0 1 3 11 5 6 9 10 0 1 2 3 4 5 6 7 8 9 10 11 12 F F T F T F F T T F F F T 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 -1 0 -1 3 3 -1 -1 11 11 0 -1 2. M t s ng d ng c a Queue 2.1. Tìm ki m theo chi u rộng trên đồ thị (BFS - Breadth First Search) Lấy đỉnh 5 ra, tìm thấy hai đỉnh 4 và 12 Queue Mảng ChuaXet Mảng LuuVet 0 1 3 11 5 6 9 10 4 12 0 1 2 3 4 5 6 7 8 9 10 11 12 F F T F F F F T T F F F F 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 -1 0 5 3 3 -1 -1 11 11 0 5 2. M t s ng d ng c a Queue 2.1. Tìm ki m theo chi u rộng trên đồ thị (BFS - Breadth First Search) Lấy đỉnh 6 ra, tìm thấy đỉnh 2 Queue Mảng ChuaXet Mảng LuuVet 0 1 3 11 5 6 9 10 4 12 2 0 1 2 3 4 5 6 7 8 9 10 11 12 F F F F F F F T T F F F F 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 6 0 5 3 3 -1 -1 11 11 0 5 2. M t s ng d ng c a Queue 2.1. Tìm ki m theo chi u rộng trên đồ thị (BFS - Breadth First Search) Lần lượt lấy đỉnh 9 và 10 ra nhưng đều không tìm thấy đường đi tiếp Queue Mảng ChuaXet Mảng LuuVet 0 1 3 11 5 6 9 10 4 12 2 0 1 2 3 4 5 6 7 8 9 10 11 12 F F F F F F F T T F F F F 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 6 0 5 3 3 -1 -1 11 11 0 5 2. M t s ng d ng c a Queue 2.1. Tìm ki m theo chi u rộng trên đồ thị (BFS - Breadth First Search) Lấy đỉnh 4 ra, thấy hai đỉnh 7 và 8 Queue Mảng ChuaXet Mảng LuuVet 0 1 3 11 5 6 9 10 4 12 2 0 1 2 3 4 5 6 7 8 9 10 11 12 F F F F F F F F F F F F F 7 8 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 6 0 5 3 3 4 4 11 11 0 5 2. M t s ng d ng c a Queue 2.1. Tìm ki m theo chi u rộng trên đồ thị (BFS - Breadth First Search) Lần lượt lấy đỉnh 12, 2, 7 và 8 ra nhưng đều không tìm thấy đường đi tiếp và tất cả các đỉnh đã đều được duyệt Queue Mảng ChuaXet Mảng LuuVet 0 1 3 11 5 6 9 10 4 12 2 0 1 2 3 4 5 6 7 8 9 10 11 12 F F F F F F F F F F F F F 7 8 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 6 0 5 3 3 4 4 11 11 0 5 2. M t s ng d ng c a Queue 2.2. Chuỗi Palindromes - Khái ni m: M t chuỗi đ ợc gọi là Palindrome nếu nh đọc xuôi hay đọc ng ợc đều giống nhau (chuỗi đối xứng). - Bài toán: Cho tr c m t chuỗi, kiểm tra xem chuỗi đó có phải là chuỗi Palindrome hay không? - Ví dụ: Able was I ere I saw Elba - Gi i pháp: • Để tránh ảnh h ng t i chuỗi ban đầu, đọc chuỗi nói trên vào stack và queue. • So sánh từng phần tử của stack và queue, nếu giống nhau từng cặp thì đó là chuỗi Palindrome Stack Push Pop A B L E W A S I E R E I S A W E L B A L E W A S I E R E I S A W E L B A Queue DeQueue A B EnQueue 2. M t s ng d ng c a Queue 2.3. Gi i thuật Demerging - Bài toán: Xem xét bài toán về hệ thống quản lý nhân sự. Các bản ghi đ ợc l u trên file. • Mỗi bản ghi gồm các tr ng: Họ tên, gi i tính, ngày tháng năm sinh, ... • Dữ liệu trên đư đ ợc sắp theo ngày tháng năm sinh. • Cần tổ chức lại dữ liệu sao cho nữ đ ợc liệt kê tr c nam nh ng vẫn giữ đ ợc tính đư sắp theo ngày tháng năm sinh. 2. M t s ng d ng c a Queue 2.3. Gi i thuật Demerging - Đ xu t cách gi i quy t: • Ý t ng không hiệu quả:  Sử dụng thuật toán sắp xếp.  Đ phức tạp của thuật toán O(nlogn) trong tr hợp tốt nhất. • Ý t ng hiệu quả hơn:  Sử dụng giải thuật demerging.  Đ phức tạp của giải thuật này là O(n) ng 2. M t s ng d ng c a Queue 2.3. Gi i thuật Demerging - Giải thuật Demerging: • B1. Tạo 2 queue rỗng, có tên lần l ợt là NU và NAM. • B2. V i mỗi bản ghi p, xem xét:  Nếu p có gi i tính nữ, đ a vào queue NU.  Ng ợc lại, (p có gi i tính nam) đ a vào queue NAM. • B3. Xét queue NU, khi queue ch a rỗng:  B3.1. Lấy từng phần tử trong queue này.  B3.2. Ghi vào file output. • B4. Xét queue NAM, khi queue ch a rỗng:  B4.1. Lấy từng phần tử trong queue này.  B4.2. Ghi tiếp vào file output trên. • B5. Kết thúc 2. M t s ng d ng c a Queue 2.4. Buffer - Giới thi u: Buffer là dữ liệu tạm thời và th l u trữ trong b nh tạm (RAM). ng đ ợc - Browser: khi xem m t đoạn video trực tuyến, có hai cách để trình duyệt tải dữ liệu từ đoạn video này: i. Tải toàn b dữ liệu của video rồi m i chạy ii. Tải từng phần của video và chạy từng phần n i dung mỗi khi dữ liệu đ ợc tải về máy. Từng phần dữ liệu video đ ợc tải về và l u vào vùng nh tạm của máy vùng nh tạm này đ ợc gọi là buffer. 2. M t s ng d ng c a Queue 2.4. Buffer - Web Server: khi có m t "slow" client request (request đến từ m t thiết bị có tốc đ kết nối/xử lý rất chậm) nh m t chiếc máy tính “yếu” hoặc điện thoại sử dụng 3G v i đ ng truyền “chậm”. Khi đó, Web Server sẽ phải làm 2 việc: • "keep alive" connection đến "slow" client request đó trong 1 queue (sử dụng buffer thông qua m t reverse proxy), và đợi cho đến khi client đó nhận đ ợc kết quả trả về! • Dành resource cho những client request khác. - Keyboard Buffer: là 1 vùng nhỏ trong b nh đ ợc dành riêng để giữ tạm các mã tín hiệu của các lần ấn phím sau cùng (của ng i dung) trên bàn phím. Nh vậy, máy tính có thể tiếp tục thu nhận các tín hiệu từ bàn phím ngay cả khi đang bận làm việc khác. 2. M t s ng d ng c a Queue 2.5. Mô hình Producer-Consumer - Mô hình này hay đ ợc sử dụng trong các hệ thống phân tán, khi các công việc sẽ đ ợc tạo b i m t loạt các tiến trình gọi là Producer, và công việc đó sẽ đ ợc xử lý b i m t loạt các tiến trình khác gọi là Consumer. - Producer và Consumer có thể nằm trên cùng 1 máy hoặc các máy khác nhau. - Vấn đề là làm thế nào chúng ta có thể chuyển công việc từ Producer đến Consumer  BlockingQueue 2. M t s ng d ng c a Queue 2.5. Mô hình Producer-Consumer - BlockingQueue là cấu trúc dữ liệu nhằm để giải quyết bài toán Producer-Consumer. Cụ thể là trong môi tr ng Multi Threaded khi mà nhiều Producers nằm trên nhiều Thread đều muốn "nhét" dữ liệu vào cùng 1 queue. Tính năng Thread safe của BlockingQueue giúp quản lý quá trình đó. - Tính năng Thread safe của BlockingQueue: • Khi queue bị đầy: hành vi đ a dữ liệu vào của Producer sẽ bị blocked cho đến khi Consumer giải phóng b t dữ liệu ra • Khi queue rỗng: Consumer sẽ bị blocked cho đến khi Producer có đ a dữ liệu vào. 2. M t s ng d ng c a Queue 2.5. Mô hình Producer-Consumer - SynchronousQueue và BlockingQueue cùng giải quyết bài toán queue cho mô hình Producer-Consumer. - Điểm khác biệt: SynchronousQueue sẽ block hành vi đ a dữ liệu vào khi có hành vi lấy dữ liệu ra t ơng ứng. Tức là SynchronousQueue chỉ cho phép thông l ợng (throughput) là 1 item trong khi BlockingQueue cho phép gi i hạn trên của buffer là n. Synchronous Queue Producer push() wait until consumer is ready queue No storage pop() Consumer wait until producer is ready 3. Các thao tác c b n trên Queue i. InitQueue: kh i tạo Queue rỗng ii. IsEmpty: kiểm tra Queue rỗng? iii.IsFull: kiểm tra Queue đầy? iv.EnQueue: thêm 1 phần tử vào cuối Queue  có thể làm Queue đầy v. DeQueue: lấy ra 1 phần tử từ đầu Queue  có thể làm Queue rỗng vi.QueueFront, QueueRear: kiểm tra phần tử đầu và phần tử cuối Queue  không làm thay đổi Queue. 4. S d ng m ng 1 chi u làm Queue 4.1. Đặc đi m • Viết ch ơng trình dễ dàng, nhanh chóng • Bị hạn chế do số l ợng phần tử cố định • Tốn chi phí tái cấp phát và sao chép vùng nh nếu sử dụng mảng đ ng 4. S d ng m ng 1 chi u làm Queue 4.2. C u trúc d li u cần s dụng - 1 mảng (qArray) để chứa các phần tử. - 1 số nguyên (qMax) để l u sức chứa tối đa. - 2 số nguyên (qFront, qRear) để xác định vị trí đầu, cuối. - 1 số nguyên (qCount) để l u số phần tử hiện có 0 qArray qMax = 7 qCount = 4 qFront = 1 qRear = 4 1 2 3 4 37 22 15 3 5 6 4. S d ng m ng 1 chi u làm Queue 4.3. Khai báo c u trúc Queue Giả sử Queue chứa các phần tử kiểu nguyên (int) typedef struct QUEUE { int //śc ch́a t́i đa int qMax; int qCount;// ś phần t int int }; *qArray; //ch́a các phần t của Queue hịn có qFront;// xác đ̣nh ṿ trí đầu qRear; // xác đ̣nh ṿ trí cúi 4. S d ng m ng 1 chi u làm Queue 4.4. Thao tác “Khởi tạo Queue” int InitQueue(QUEUE& q, int MaxItem) { q.qArray = new int[MaxItem]; if (q.qArray == NULL) return 0; // không đủ b nh q.qMax = MaxItem; q.qCount = 0; q.qFront = q.qRear = -1; // thành công return 1; } 4. S d ng m ng 1 chi u làm Queue 4.5. Thao tác “Ki m tra Queue rỗng” int IsEmpty(QUEUE q) { if (q.qCount == 0) return 1; // rỗng return 0; // không rỗng } 0 1 2 3 4 5 6 QArray QMax = 7; QCount = 0; QFront = -1; QRear = -1 4. S d ng m ng 1 chi u làm Queue 4.6. Thao tác “Ki m tra Queue đầy” int IsFull(QUEUE q) { if (q.qMax == q.qCount) return 1; // đã đầy return 0; // không/ch a đầy } 0 QArray 4 1 2 3 4 5 6 12 9 2 7 6 5 QMax = 7; QCount = 7; QFront = 0; QRear = 6 4. S d ng m ng 1 chi u làm Queue 4.7. Thao tác thêm phần t vào queue - Khi thêm phần tử vào queue  xảy ra hiện t ợng “tràn giả” 0 1 2 3 4 5 6 qArray 37 22 15 3 7 9 qMax = 7 qCount = 6 qFront = 1 qRear = 6 - Giải pháp? Nối dài mảng (mảng đ ng) hay sử dụng m t mảng vô cùng l n? 4. S d ng m ng 1 chi u làm Queue 4.7. Thao tác thêm phần t vào queue - Cách 1: Dồn các phần tử về đầu mảng 0 1 qArray qMax = 7; qCount = 5; 2 3 4 5 6 22 15 3 7 9 qFront = 2; qRear = 6 • Cách 1.1: ngay khi phần tử đầu trống. 0 1 2 3 4 QArray qArray 15 22 15 3 73 97 9 QMax==7; qMax 7;qCount QCount==4;5; qFront QFront==0; 0; 5 6 qRear QRear==34 • Cách 1.2: khi phần tử cuối đ ợc dùng 00 1 1 22 33 4 5 6 QArray qArray 22 15 223 15 7 3 7 9 QMax==7; qMax 7;qCount QCount==5;4; 5; QFront qFront ==0; 2; qRear QRear==456 4. S d ng m ng 1 chi u làm Queue 4.7. Thao tác thêm phần t vào queue - Cách 2: tổ chức hàng đợi dạng vòng (Queue Circular), có thể coi mảng v i các phân tử đ ợc xếp vòng tròn. 4. S d ng m ng 1 chi u làm Queue 4.7. Thao tác EnQueue: thêm 1 phần t vào cuối Queue int EnQueue(QUEUE &q, int NewItem) { if (IsFull(q)) return 0; // Queue đầy q.qRear++; //“trơn gi ” if (q.qRear==q.qMax) q.qRear = 0; // Quay trở v̀ đầu m ng q.qArray[q.qRear] = NewItem; q.qCount++; return 1; // Thêm thành công } NewItem=4 0 QArray qArray 4 1 2 3 4 5 6 12 9 2 7 6 5 QMax==7; qMax 7;qCount QCount==6;5; 7; qFront QFront==2; 0; 2; qRear QRear==067 0 4. S d ng m ng 1 chi u làm Queue 4.8. Thao tác DeQueue: l y ra 1 phần t ở đầu Queue int DeQueue(QUEUE &q, int &ItemOut) { if (IsEmpty(q)) //Queue rỗng, không lấy ra đ return 0; c q.qFront++; q.qCount--; if (q.qFront==q.qMax) q.qFront = 0; // n u Qfront đã đi h t m ng … //cho Qfront quay trở v̀ đầu m ng //lấy phần t ItemOut=q.qArray[q.qFront]; if (q.qCount==0) //n u lấy ra phần t đầu ra cúi cùng //khởi ṭo ḷi Queue q.qFront= q.qRear= -1; //Lấy ra thành công return 1; } ItemOut=9 ItemOut=5 QArray 0 1 2 3 4 4 3 9 2 7 QMax 0; 5; 1; 2; 2; 7; -1; QMax = = 7; 7; QCount QCount = = 3; 4; QFront QFront = = 6; 3; 5 6 6 5 5 QRear QRear -1 166 QRear == ==-1 4. S d ng m ng 1 chi u làm Queue 4.10. Thao tác QueueFront: Kiểm tra phần tử đầu Queue int QueueFront(const QUEUE &q, int& ItemOut) { if (IsEmpty(q)) return 0; //Queue rỗng, không kiểm tra // lấy phần tử đầu ra ItemOut = q.QArray[q.QFront]; return 1; } 4. S d ng m ng 1 chi u làm Queue 4.11. Thao tác QueueRear: Kiểm tra phần tử cuối queue int QueueRear(const QUEUE &q, int& itemout) { if (IsEmpty(q)) return 0; //Queue rỗng, không kiểm tra //lấy phần tử cuối ra itemout = q.QArray[q.QRear]; return 1; } 5. TH C HÀNH Bài t p 5.1 Cho khai báo nh sau: typedef struct QUEUE { char *qArray; int qMax; int qCount; int qFront; int qRear; }; typedef struct STACK { int* sArray; int sMax; int sCount; }; Viết ch ơng trình cài đặt bài toán về chuỗi Palindromes (chuỗi đối xứng) v i prototype nh sau (trả về 1 nếu đối xứng, ng ợc lại trả về 0): int KiemTraDoiXung (char* str) 5. TH C HÀNH Bài t p 5.2: Viết ch ơng trình thực hiện yêu cầu sau: typedef struct Queue { int *qArray; int qMax; int qCount; int qFront; int qRear; }QUEUE; Viết lại hàm Enqueue (thêm phần tử) để khi phần tử cuối đ ợc dùng (q.qRear==q.qMax-1), hàm sẽ thực hiện thêm việc dồn mảng về đầu (- cách 1.2 trong phần lý thuyết) int EnQueue(QUEUE &q, int NewItem) Sửa lại ch ơng trình khi không có khai báo thành phần qCount trong cấu trúc trên. 5. TH C HÀNH Bài t p 5.3. Viết ch ơng trình thực hiện yêu cầu sau: Có khai báo về queue cần dùng nh sau: typedef struct Queue int *qArray; { int qMax; int qCount; int qFront; int qRear; }QUEUE; V i khai báo đư có: QUEUE q1, q2, q3, q4, q5; Viết ch ơng trình thực hiện các yêu cầu sau: • 5.3.1. Giả sử q1 và q2 đư đ ợc sắp tăng dần. Nối q1 và q2 thành q3 sao cho q3 vẫn có thứ tự tăng dần, theo prototype sau: void Nhap(QUEUE q1, QUEUE q2, QUEUE &q3) • 5.3.2. Tách q1 thành 2 queue, sao cho:  Queue thứ nhất (q4) chứa các phần tử là số nguyên tố.  Queue thứ hai (q5) chứa các phần tử còn lại. V i prototype sau: void Tach(QUEUE q, QUEUE &q4, QUEUE &q5) 5. TH C HÀNH Bài t p 5.4. Viết ch ơng trình thực hiện yêu cầu sau: Viết ch ơng trình mô phỏng quy trình xếp hàng đặt vé xem phim nh sau:  Danh sách liên Ệ t A chứa số ghế của các ghế trống trong rạp (ban dầu kh i tạo các số ghế từ 1 đến n).  Danh sách hàng đợi B chứa số thự tự và tên của khách xếp hàng.  Danh sách liên Ệ t C chứa thông tin khách đư mua vé (số ghế, tên).  CểứẾ nănỂ ệấỔ số ồ p hàng: Ban đầu (khi B rỗng) thì khách đầu tiên sẽ có số thứ tự xếp hàng là 1, ng ợc lại thì số thứ tự xếp hàng là k+1 v i k là số thứ tự của node cuối của B.  CểứẾ nănỂ mua vé: Nếu còn ghế trống và có khách đang ch mua vé thì xóa node khỏi B, lấy tên khách và số ghế khách chọn để thêm node vào C đồng th i loại số ghế đó khỏi A.  CểứẾ nănỂ ểủỔ vé: Xóa node khỏi C đồng th i thêm số ghế m i hủy vào A.  CểứẾ nănỂ ểi n tểị: Hiển thị thông tin những vé đư bán (DSLK C). Ch ng 8 ThS.Lê Văn Hạnh N I DUNG 1. Giới thiệu 2. Một số tính chất 3. Một số thuật ngữ 4. Cây nhị phân (Binary Tree) 5. Cây nhị phân tìm kiếm (Binary Search Tree) 6. Cây nhị phân tìm kiếm cân bằng (Balanced Binary Search Tree) 1. GI I THI U 1.1. Định nghƿa - Cây: là m t đồ thị vô h ng liên thông, không chứa chu trình và có ít nhất hai đỉnh. - Rừng: là m t đồ thị vô h ng không chứa chu trình và có ít nhất hai thành phần, mỗi thành phần có ít nhất 2 đỉnh. Ví dụ: rừng sau gồm 3 cây 347 1.2. Định lý: Cho T là m t đồ thị có n  2 đỉnh. Các điều sau là t ơng đ ơng: - T là m t cây. - T liên thông và có n1 cạnh. - T không chứa chu trình và có n1 cạnh. - Giữa hai đỉnh phân biệt bất kỳ của T luôn có duy nhất m t đ ng đi sơ cấp. - T không chứa chu trình nh ng khi thêm m t cạnh m i thì có đ ợc m t chu trình duy nhất. 1. GI I THI U 348 1. GI I THI U 1.3. Cây khung - Trong đồ thị liên thông G, nếu ta loại bỏ cạnh nằm trên chu trình nào đó thì ta sẽ đ ợc đồ thị vẫn là liên thông. - Nếu cứ loại bỏ các cạnh các chu trình khác cho đến khi nào đồ thị không còn chu trình (vẫn liên thông) thì ta thu đ ợc m t cây nối các đỉnh của G. Cây đó gọi là cây khung hay cây bao trùm của đồ thị G. 349 1. GI I THI U 1.4. Rừng khung - Nếu G là đồ thị có n đỉnh, m cạnh và k thành phần liên thông. - G đ ợc coi là rừng khung khi các thành phần liên thông đều là cây khung. - Để G tr thành rừng khung thì số cạnh cần bị loại bỏ là mn+k, số này ký hiệu là (G) và gọi là chu số của đồ thị G. Ví dụ: n=18, m=22, k=4 (G)=22-18+4=8 350 1. GI I THI U 1.5. CỂY Cị G C - Cây có h ng là đồ thị có h ng mà đồ thị vô h ng nền của nó là m t cây. - Cây có gốc là m t cây có h ng, trong đó có m t đỉnh đặc biệt, gọi là gốc, từ gốc có đ ng đi đến mọi đỉnh khác của h c f cây. a e j d b g i k - Cấu trúc cây tổng quát: • Cây là m t cấu trúc gồm 1 tập hữu hạn các node có cùng kiểu dữ liệu. • Các node đ ợc nối v i nhau b i 1 cạnh. • Có duy nhất 1 node gốc. • Có duy nhất 1 đ ng đi từ node gốc đến 1 node bất kỳ 351 1. GI I THI U 1.6. Bi u di n cây 1.6.1. Bi u di n cây dưới dạng tập hợp node ǵc Cây con <T1> Cây con <T2> Cây <T> Cây con <T3> c a f g h i d b e j k Cây con <T4> 1. GI I THI U 1.6. Bi u di n cây 1.6.2. Bi u di n cây dưới dạng phân mức Cây <T> a f c Cây con <T1> h d i b j e Cây con <T2> g Cây con <T3> k Cây con <T4> 1. GI I THI U 1.6. Bi u di n cây 1.6.2. Bi u di n cây dưới dạng phân mức Cây <T> a f c Cây con <T1> e d j b Cây con <T2> h i g Cây con <T4> k Cây con <T3> 1. GI I THI U 1.6. Bi u di n cây 1.6.2. Bi u di n cây dưới dạng phân mức 355 1. GI I THI U 1.7. Cây m phân 1.7.1. Cây m phân - M t cây có gốc T đ ợc gọi là cây m-phân nếu mỗi đỉnh của T có nhiều nhất là m con. - Cây có gốc T đ ợc gọi là m t cây m-phân đầy đủ nếu mỗi đỉnh trong của T đều có m con. 1.7.2. Cây nhị phân - Khi cây m phân có m=2, ta có m t cây nhị phân. - Trong m t cây nhị phân, mỗi con đ ợc chỉ rõ là con bên trái hay con bên phải; con bên trái (hoặc bên phải) đ ợc vẽ phía d i về bên trái (hoặc bên phải) của cha. 356 1. GI I THI U 1.8. M t s ng d ng c a cơy - Organization Chart 1. GI I THI U 1.8. M t s ng d ng c a cơy - MindMap 1. GI I THI U 1.8. M t s ng d ng c a cơy - SiteMap T a gà hủ Giớiàthiệu T ườ g Nộià ộ Sinh viên Khoa A Họ àtập Khoa B Phong trào … Liê àkếtà ngoài Ti àtứ Đo -Hội “ựàkiệ … T ườ gàliê à kết Cơàhộià iệ à làm 1. GI I THI U 1.8. M t s ng d ng c a cơy - Directory tree 1. GI I THI U 1.8. M t s ng d ng c a cơy - Dictionary tree 1. GI I THI U 1.8. M t s ng d ng c a cơy - Expression tree 1. GI I THI U 1.8. M t s ng d ng c a cơy - Biological 1. GI I THI U 1.8. Một số ứng dụng của cây - Cây là m t cấu trúc quan trọng để biểu diễn: • Tính kế thừa:  Cây gia phả (biểu diễn mối quan hệ giữa những ng i trong m t dòng họ qua nhiều thế hệ).  Trong việc định nghĩa đối t ợng • Phân cấp  Cây phân cấp các loài  Cây phân cấp quản lý mạng Internet… 2. M T S TệNH CH T C A CỂY i. Node gốc không có node cha ii. Mỗi node khác không phải gốc đều chỉ có duy nhất m t node cha a iii. Mỗi node có thể có nhiều con f iv. Không có chu trình c d e leàá→á.àáàisàtheà root but it also has a parent. • Cycle B→C→E→D→B. • B has more than one parent (inbound edge). j b Node 4 has more than one parent (inbound edge). Not a tree h k There is more than one root. i g 3. M T S THU T NG i. Nút (Node): là m t phần tử trong cây. Mỗi node có thể chứa m t dữ liệu bất kỳ (do ng i dùng tự định nghĩa). ii. Nút cha (Parent node) Node có kết nối trực tiếp v i m t node khác ngay phía d ới. iii. Nút con (Child node) Node có kết nối trực tiếp v i m t node khác ngay phía trên. iv. Nút gốc (Root node): node trên cùng trong cây, và node gốc không có node cha v. Nhánh (Branch - Edge): là cạnh nối giữa Parent & Child node. Root node Left branch Internal node Branch node Parent node Leaf node Child node Node Child node External node Leaf node Right branch Leaf node 3. M T S THU T NG vi. Nút lá (Leaf node hay node ngoài – External node): là node có bậc = 0 (nút không có node con) vii. Nút nội (Internal node hay node nhánh, node trung gian): là node có Parent node và có child node viii. Nút anh em (Sibling node): là những node có cùng Parent node ix. Nút tổ tiên (Ancestor node): Là nút có thể truy cập bằng cách lặp đi lặp lại việc truy cập từ child node đến parent node x. Nút con cháu (Descendant node): Là nút có thể truy cập bằng cách lặp đi lặp lại việc truy cập từ parent node đến child node. Root node Left branch Node Internal node Branch node Parent node Leaf node Child node Child node External node Leaf node Right branch Leaf node 3. M T S xi. THU T NG a T tree Cây con (SubTree) f c d e j b h i g k xii. Bậc của một nút pi (Degree of node): là số nút con của nút pi.      Bậc Bậc Bậc Bậc Bậc (a) (f) (d) (j) (c) = = = = = 4 3 2 1 0 = bậc(b)=bậc(e)=bậc(g) = bậc(h)=bậc(i)=bậc(k) xiii. Bậc của cây (Degree of tree): là bậc l n nhất của tất cả các node có trong cây 3. M T S THU T NG xiv.Đường đi (Path): M t chuỗi node và các cạnh kết nối m t node v i node hậu duệ. xv. Mức (Level): Mức của 1 node đ ợc xác định bằng số l ợng kết nối giữa node đang xét và root node.  Mức của root node =0. Mức 0 Mức 1 Mức 2 Mức 3 3. M T S THU T NG ix. Độ sâu của node (Depth of node) là số cạnh đi từ root node đến node đang xét. x. Chi u cao của node (Heigh of node): là số nhánh (cạnh) trên con đ ng dài nh t giữa nút đó và lá. xi. Chi u cao của cây (Heigh of tree): chính là chiều cao của root node. Mức 0 Mức 1 Mức 2 Mức 3 5. CỂY NH PHỂN 5.1. Khái ni m: là cây mà các node đều có bậc tối đa là 2. left subtree root node right subtree T2 T1 T3 T4 5.2. Phân chia t p con trong cây nểị phân: có thể phân chia 1 cây nhị phân thành 3 tập con: - Tập con thứ nhất: có 1 node gọi là root node - Tập con thứ hai: là nhánh các cây con bên trái (left subtree). - Tập con thứ ba: là nhánh các cây con bên phải (right subtree).  Trong đó left subtree và right subtree có thể tự thân hình thành cây nhị phân. Do đó cây (nhánh) này cũng có thể là rỗng. 5. CỂY NH PHỂN 5.3. Các cây nểị phân đặẾ bi t - Cây nhị phân đúng (strickly binary tree): • Là cây mà các node không phải là node lá đều có 2 node con. • Gọi n là số node lá của cây  số node trên toàn b cây sẽ là 2n-1 - Cây nhị phân đầy đủ (complete binary tree): là cây thỏa 2 điều kiện: • Là cây nhị phân đúng. • Tất cả các node lá đều có cùng mức h. h-1 h strickly binary tree h complete binary tree 6. CỂY NH PHỂN TỊM KÍM (BST- Binary Search Tree) 6.1. Khái ni m - Là cây nhị phân - Giá trị của m t node bất kỳ luôn l n hơn giá trị của tất cả các node bên trái và nhỏ hơn giá trị tất cả các node bên phải  • cây không chứa giá trị trùng (giống nhau) • node có giá trị nhỏ nhất nằm trái nhất của cây • node có giá trị l n nhất nằm phải nhất của cây 7 Left subtree 3 Right subtree 36 1 6 4 15 40 23 6. CỂY NH PHỂN TỊM KÍM 6.1. Khái ni m - Nh trật tự bố trí khóa trên cây  định h nhanh khi tìm kiếm. ng đ ợc - Cây gồm N phần tử: • Tr ng hợp tốt nhất h = log2N • Tr ng hợp xấu nhất h = N  Khi nào xảy ra tr ng hợp xấu nhất? 6.2. Định nghƿa ki u d li u node Trỏ trái Giá trị Trỏ phải typedef struct TNODE { <Data> Key; struct TNODE *pLeft; struct TNODE *pRight; }*TREE; TNODE pLeft Key pRight Ví dụ khai báo cây nhị phân biểu diễn các node là số nguyên typedef struct TNODE { int Key; struct TNODE *pLeft, struct TNODE *pRight; } *TREE; START - B ớẾ 1: Khai báo kiểu dữ liệu biểu diễn cây Khai báo cấu trúc cây - B ớẾ 2: Xây dựng hàm đ a dữ liệu (nhập) vào cây Khởi tạo cây rỗng - B ớẾ 3: Xây dựng các thao tác duyệt, tìm kiếm, huỷ, … Xây dựng cây Các thao tác Hủy cây •L u ý: 1. Tr c khi tạo node m i phải xin cấp phát vùng nhớ. 2. Tr c khi kết thúc ch ơng trình phải huỷ cây (giải phóng vùng nh ). END 6.4. Các thao tác 1. int InitTree (TREE &t) : kh i tạo cây 2. int IsEmptyTree (TREE t) : kiểm tra cây rỗng 3. NODE CreateNode (int x) : cấp phát 1 node co dữ liệu là x 4. int AddNode (TREE &t, int x) : Đ a node vào cây 5. void TreeTraversal(TREE t) : Duyệt cây 6. void Info (TREE t) : Cho biết các thông tin của cây 7. int Search(TREE t) : Tìm kiếm 8. int DeleNode (TREE &t, NODE p): Xoá node trên cây 9. void ClearTree((TREE &t) : xóa toàn b cây 6.4.1. Khởi tạo cây int InitTree (TREE &t) { t = NULL; } 6.4.2. Ki m tra cây rỗng int IsEmptyTree (TREE t) { return (t == NULL) } 6. CỂY NH PHỂN TỊM KÍM 6.4. CÁC THAO TÁC TRểN CỂY NH PHỂN TỊM KÍM 6.4.3. Tạo 1 node mới Node* CreateNode(int x) { Node *p; p = new Node;//Cấp phát vùng nh cho phần t if ( p==NULL) exit(1); p->Info = x; //gán dữa lịu cho node p->pLeft = NULL; p->pRight = NULL; Info=x p return p; pLeft=NULL pRight=NULL } 6.4.4. Đưa node vào cây 7 36 3 1 6 int AddNode (TREE &t, int x) { if(t!=NULL) { if(x==t->Key) //giƠ tṛ x đã ć trên cƯy return 0; else if(x<t->Key) AddNode(t->pLeft, x); else AddNode(t->pRight, x); } else { NODE* p; p= CreateNode(X); if(t==NULL) return -1;//thêm KHÔNG thành công else t=p; return 1; } } 4 15 40 317466 40 15 BÀIàTẬP 6.4.5. Duy t cơy (Tree traversal) Có 3 thành phần tham gia vào quá trình duyệt cây là Node, Left, Right  Có 6 cách duyệt i. Node - Right - Left ii. Node - Left -Right iii. Left-Node-Right iv. Left-Right-Node v. Right-Node-Left vi. Right – Left -Node Trong thực tế, ng i ta chỉ quan tâm đến 3 cách dựa trên vị trí của root node (trong đó Left luôn đ ợc duyệt tr c Right) 6.4.5. Duy t cơy (Tree traversal) i. Duyệt gốc tr c (pre-order traversal hay Node-Left-Right) ii. Duyệt gốc giữa (in-order traversal hay Left-Node-Right) iii.Duyệt gốc sau (post-order traversal hay Left-Right-Node) 6.4.5.1. NLR Tại node t đang xét, nếu khác rỗng thì thực hiện lần l ợt i. In giá trị của t ii. Duyệt cây con bên trái của t theo thứ tự NLR iii. Duyệt cây con bên ph i của t theo thứ tự NLR 7 3 36 1 6 15 4 7 L7 7 3 L3 7 3 1 L1 R1 23 R7 R3 6 R6 L6 7 3 1 6 4 7 3 1 6 4 L4 R4 36 L36 36 15 L15 R36 R15 40 36 15 23 40 36 15 23 40 L40 40 R40 6.4.5.1. NLR Tại node t đang xét, nếu khác rỗng thì thực hiện lần l ợt i. In giá trị của t ii. Duyệt cây con bên trái của t theo thứ tự NLR iii. Duyệt cây con bên phải của t theo thứ tự NLR void NLR (TREE t) { if(t!=NULL) { printf(“%5d”,t->Key; NLR(t->pLeft); NLR(t->pRight); } } 6.4.5.2. LNR 7 Tại node t đang xét, nếu khác rỗng thì thực hiện lần l ợt i. Duyệt cây con bên trái của t theo thứ tự LNR ii. In giá trị của t iii. Duyệt cây con bên ph i của t theo thứ tự LNR L7 L3 3 L1 1 R1 3 7 R3 L6 7 36 1 6 15 40 4 23 36 R36 R7 7 6 R6 3 L36 L15 15 R15 36 L40 40 R40 1 3 L4 4 R4 6 7 15 L23 23 R23 36 40 1 3 7 15 23 40 4 6 36  Viết lại các giá trị trên cây theo thứ tự tăng dần  Nếu yêu cầu in giá trị trên cây theo thứ tự Ểiảm dần thì duyệt bằng cách nào? 6.4.5.2. LNR Tại node t đang xét, nếu khác rỗng thì: i. Duyệt cây con bên trái của t theo thứ tự LNR ii. In giá trị của t iii. Duyệt cây con bên phải của t theo thứ tự LNR void LNR (TREE t) { if(t!=NULL) { LNR(t->pLeft); printf(“%5D”,t->Key); LNR(t->pRight); } } 6.4.5.3. LRN Tại node t đang xét, nếu khác rỗng thì thực hiện lần l ợt i. Duyệt cây con bên trái của t theo thứ tự LRN 7 3 ii. Duyệt cây con bên ph i của t theo thứ tự LRN iii. In giá trị của t 36 1 6 4 L7 L3 L1 R1 1 1 1 R6 L6 L4 R4 3 6 3 4 6 3 4 6 3 L36 L15 L23 40 23 7 R7 R3 15 L40 R36 36 7 R40 40 36 7 R15 15 R23 23 15 40 36 7 23 15 40 36 7 6.4.5.3. LRN Tại node t đang xét, nếu khác rỗng thì thực hiện lần l ợt i. Duyệt cây con bên trái của t theo thứ tự LRN ii. Duyệt cây con bên phải của t theo thứ tự LRN iii. In giá trị của t void LRN (TREE t) { if(t!=NULL) { LRN(t->pLeft); LRN(t->pRight); printf(“%5d”,t->Key); } } 6.4.6. Cho bi t các thông tin c a cơy Số node lá (node bậc 0) Số node có 1 cây con (node bậc 1) Số node chỉ có 1 cây con phải Số node có 1 cây con trái Số node 2 cây con (node bậc 2) Đ cao của cây Số node của cây Các node trên từng mức của cây Đ dài đ ng đi từ gốc đến node x Kiểm tra xem cây có phải là cây nhị phân đúng (strictly binary tree) hay không? 11. Kiểm tra xem cây có phải là cây nhị phân đầy đủ (complete binary tree) hay không? 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 6.4.3.1. S node lá Nếu node t khác rỗng thì . Nếu node t có bậc 0 thì Trả về 1 . Ngược lại Trả về Số node lá cây trái t + Số node lá cây phải t Nếu node t rỗng thì trả về 0 int DemNutLa (TREE t) { if(t) { if(t->pLeft==NULL && t->pRight==NULL) return 1; else return DemNutLa(t->pLeft)+DemNutLa(t->pRight); } else return 0; } 6.4.6.2. S node có 1 cơy con Nếu node t khác rỗng thì d=Số node bậc 1 của cây trái t + Số node bậc 1 của cây phải t Nếu node t có bậc 1 thì trả về d+1 Ngược lại trả về d Nếu node t rỗng thì trả về 0 int DemNode1Con(TREE t) { if(t) { int d=DemNut1Con(t->pLeft) + DemNut1Con(t->pRight); if((t->pLeft!=NULL && t->pRight==NULL) ||(t->pLeft==NULL && t->pRight!=NULL)) return d+1; else return d; } else return 0; } 6.4.6.3. S node ch có 1 cơy con ph i Nếu node t khác rỗng thì d = Số node chỉ có 1 cây con phải của cây con trái t + Số node chỉ có 1 cây con phải của cây con phải t Nếu node t chỉ có 1 cây con phải thì trả về d+1 Ngược lại trả về d Nếu node t rỗng thì trả về 0 int DemNut1ConPhai(TREE t) { if(t) { int d = DemNut1ConPhai(t->pLeft) +DemNut1ConPhai(t->pRight); if(t->pLeft==NULL && t->pRight!=NULL) return d+1; else return d; } else return 0; } 6.4.6.4. S node ch có 1 cơy con trái Sinh viên tự cài đặt 6.4.6.5. S node có 2 cơy con Sinh viên tự cài đặt 6.4.6.6. Đ cao c a cơy int DoCaoCay(TREE t) { if(t) { int t1=DoCaoCay(t->pLeft); int t2=DoCaoCay(t->pRight); return Max(t1, t2)+1; } else return 0; } 6.4.6.7. S node c a cơy Sinh viên tự cài đặt 6.4.6.8. Các node trên từng m c Yêu cầu in ra màn hình các node trên từng mức. VD: v i cây hiện có nh hình bên, ch ơng trình sẽ in ra kết quả nh sau: Ḿc 0: 7 Ḿc 1: 3 36 Ḿc 2: 1 6 15 40 Ḿc 3: 4 23 7 3 36 1 6 15 4 void InMucK(TREE t, int m, int k) { if(t) { if(m==k) { cout<<t->Key; return; } else { m++; InMucK(t->pLeft, m, k); InMucK(t->pRight, m, k); } } } 40 23 6.4.6.9. In các node theo từng m c Sinh viên tự cài đặt 6.4.6.10. Đ dƠi đ ờng đi từ g c đ n node x Sinh viên tự cài đặt 6.4.6.11. Ki m tra xem cơy có ph i lƠ cơy nh phơn đúng (strickly binary tree) Sinh viên tự cài đặt h-1 h strickly binary tree 6.4.6.12. Ki m tra xem cơy có ph i lƠ cơy nh phơn đ y đ (complete binary tree) Sinh viên tự cài đặt h complete binary tree 1. Tìm node chứa giá trị x 2. Tìm min 3. Tìm min của cây con bên phải 4. Tìm max 5. Tìm max của cây con bên trái 6. Tìm parent node của node có khóa là x. 7 Ví dụ tìm x = 23 3 1 36 6 15 23 TNODE * TimKiem(TREE t,int x) 4 { if(t!=NULL) { if(t->Key==x) return t; if(x<t->Key) return TimKiem(t->pLeft, x); else return TimKiem (t->pRight, x); } return t; } 40 7 3 36 1 TNODE* Min(TREE t) { while(t->pLeft!=NULL) t=t->pLeft; return t; } 6 4 15 40 23 7 3 Sinh viên tự cài đặt 36 1 6 4 15 40 23 7 3 36 1 TNODE* Max(TREE t) { while(t->pRight!=NULL) t=t->pRight; return t; } 6 4 15 40 23 7 3 36 Sinh viên tự cài đặt 1 6 4 15 40 23 6.4.8. XÓA NODE TRÊN CÂY 1. Node lá 2. Node có 1 cây con 7 3. Node có 2 cây con 3 36 1 6 4 15 40 23 7 6.4.8.1. Xóa node lá 3 36 Xóa 1 Xóa 23 S b v̀ mã ḷnh s 1 tḥc hịn void DelNode (TREE & t, int x) { if(t!=NULL) { if(x<t->Key) DelNode(t->pLeft,x); else if(x>t->Key) DelNode(t->pRight,x); delete pHuy; } } 6 4 15 40 23 S 7 6.4.8.2. Xóa node có 1 cây con 3 Xóa 6 Xóa 15 b v̀ mã ḷnh s tḥc hịn 1 36 46 15 23 void DelNode (TREE & t, int x) { if(t!=NULL) { if(x<t->Key) 4 DelNode(t->pLeft,x); else { if(x>t->Key) DelNode(t->pRight,x); else { NODE * pHuy=t; if(t->pLeft==NULL) t=t->pRight; else if(t->pRight==NULL) t=t->pLeft; delete pHuy; } } } } 40 23 6.4.8.3. Xóa node có 2 cây con Tìm node thế mạng Cách 1: Tìm node trái nhất của cây con phải 7 3 36 23 1 6 15 40 Left Subtree Cách 2: Tìm node phải nhất của cây con trái Righ Subtree 16 23 4 16 Xóa 36 (Cách 2) Tìm node th m ng void TimTheMang (TREE &pHuy,TREE & q) { if(q->pLeft) TimTheMang(pHuy, q->pLeft); else { pHuy->Key=q->Key; pHuy=q; q=q->pRight; } } Xóa m t node có giá tr x void DelNode (TREE & t, int x) { if(t!=NULL) { if(x<t->Key) DelNode(t->pLeft,x); else { if(x>t->Key) DelNode(t->pRight,x); else { TNODE * pHuy=t; if(t->pLeft==NULL) t=t->pRight; else if(t->pRight==NULL) t=t->pLeft; else TimTheMang(pHuy,t->pRight); delete pHuy; } } } } 6.4.9. H y toƠn b cơy Giải thuật Nếu node khác rỗng • Hủy cây bên trái t • Hủy cây bên phải t • Hủy node t 7. BÀI T P 7.1. Tạo lập BST 1. Vẽ hình ảnh của cây khi biết thứ tự các khoá nhập vào nh sau: i. 8, 3, 5, 2, 20, 11, 30, 9, 18, 4. ii. 27, 19, 10, 21, 3, 15, 41, 50, 30, 7 iii. H, B, C, A, E, D, T, M, X, O 2. Từ kết quả của bài 1, lần l ợt thực hiện: i. Tính chiều cao của node có giá trị là 9 (i), 30(ii), O(iii) ii. Tính chiều cao của cây trong 3 cây có bài tập 1. iii. Đếm số l ợng node lá của cây trong 3 cây có bài tập 1? iv. Tính tổng các node không phải node lá của cây trong 2 cây có bài tập 1.i và 1.ii 7.BÀI T P 7.1. Tạo lập BST 3. Cho BST có các node chứa các số từ 0 đến 9. Vẽ cây cho các tr ng hợp sau: Tröôøng hôïp Toång caùc nuùt laù 1 2 3 12 18 19 4. Cho biết thứ tự của các phần tử khi thêm vào cây ra sao để có đ ợc cấu trúc này? (Giả sử lúc đầu cây rỗng) 60 i 25 25 ii 10 37 65 18 3 40 19 1 12 50 29 30 6 44 5 35 20 12 13 32 41 7.BÀI T P 7.1. Tạo lập BST 5. Cho m t cây nhị phân gồm 9 node v i key có giá trị từ 1 đến 9. Lần l ợt vẽ cây cho mỗi tr ng hợp sau: i. Biết tổng các node lá bằng 25. ii. Vẽ cây khi cây có 2 node lá, tổng các node lá là 12. iii. Vẽ cây khi biết tổng các node không lá là 34 iv. Vẽ cây có 4 node lá, sao cho tổng các node lá là nhỏ nhất. v. Vẽ cây sao cho các lá đều là số lẻ. vi. Xác định số node lá tối thiểu, số node lá tối đa của cây. Vẽ hình minh hoạ cho 2 tr ng hợp trên. Từ đó, đ a ra công thức tính số node lá tối đa khi biết số node của cây. 7.2. Duy t BST 1. Duyệt các cây trong hình sau theo 3 cách NLR, LNR và LRN R i D W 25 F 30 12 10 37 iv 18 1 6 5 35 20 12 13 50 29 32 41 40 19 M 25 3 65 H B iii 60 ii 44 7.BÀI T P 7.2. Duy t BST 2. Vẽ BST cho mỗi tr ng hợp, biết mỗi phần tử của cây là m t số nguyên và nếu áp dụng ph ơng pháp duyệt ta có kết quả: Trường hợp Cách duyệt Kết quả 1 NLR 532046798 2 NLR 5210437689 3 LRN 0143265897 4 LRN 0134567892 5 NRL 2798654310 6 NRL 3459678210 7 NLR 9, 4, 1, 3, 8, 6, 5, 7, 10, 14, 12, 13, 16, 19 8 LRN 1, 4, 7, 5, 3, 16, 18, 15, 29, 25, 30, 20, 8 7. BÀI T P 7.3. Tổng hợp v BST 1. Cho dãy số theo thứ tự nhập từ trái sang phải: 20, 15, 35, 30, 11, 13, 17, 36, 47, 16, 38, 28, 14 i. Vẽ cây nhị phân tìm kiếm cho dãy số trên ii. Lần l ợt cho biết kết quả duyệt cây trên theo thứ tự NLR và LRN iii. Cho biết đ cao của cây, các node lá, các node có bậc 2 iv. Vẽ lại cây sau khi thêm node: 25 và 91 v. Trình bày từng b node: 11 và 35 c và vẽ lại cây sau khi lần l ợt xoá các 7.BÀI T P 7.3. Tổng hợp v BST 2. Biết thứ tự các khoá nhập vào khi tạo cây là: 17, 4, 9, 5, 6, 22, 91, 18, 32, 45, 87, 35, 6, 4. Lần l ợt vẽ hình ảnh của cây sau mỗi thao tác sau: 7.BÀI T P 7.4. L p trình 1. Viết ch ơng trình thực hiện các yêu cầu sau: i. Hàm kh i tạo cây ii.Hàm thêm node vào cây iii.Hàm duyệt cây theo các cách: • • • • post-order in-order pre-order Duyệt cây theo mức (level) theo 2 dạng sau: 7.BÀI T P 7.4. L p trình 2. Viết ch ơng trình thực hiện các yêu cầu sau: i. Cho biết các thông tin của cây • Đếm số node trên cây • Đếm số node trên từng mức của cây • Tình tổng tất cả các khóa trên cây • Đếm số node lá trên cây • Đếm số node có duy nhất 1 cây con (không phân biệt trái hay phải) • Số node chỉ có 1 cây con phải • Số node có 1 cây con trái • Đếm số node có 2 cây con • Đ dài đ ng đi từ gốc đến node chứa giá trị X ii. Tìm kiếm • Cho biết khoá l n nhất trong cây là bao nhiêu • Liệt kê các số nguyên tố có trong cây iii. Xoá node trên cây • Xóa 1 node v i giá trị do ng i dùng cung cấp • Xóa toàn b cây. 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced binary search tree) 8.1. Định nghƿa (của Adelson Velski và Landis vào năm 1962 AVL Tree) • Cây AVL là cây nhị phân tìm kiếm mà tại tất cả các node của cây chiều sâu của cây con bên trái và cây con bên phải chênh nhau không quá 1. h2=1 hL8=0 hL1=0 hR1=6 h6=1 hR8=2 hL8=0 Non-Balanced Binary Tree hR8=1 Balanced Binary Tree 424 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.2. Phân loại • Gọi hL là chiều cao cây con trái hR là chiều cao cây con phải CNP cân bằng tương đối hL-hR • <=2 1 Mất cân bằng Ḷch trái 0 -1 >=-2 Cân bằng Ḷch ph i Mất cân bằng Gọi qL là số l ợng node có trong cây con trái qR là số l ợng node có trong cây con phải CNP cân bằng hoàn toàn qL-qR <=2 1 Mất cân bằng Ḷch trái 0 -1 >=-2 Cân bằng Ḷch ph i Mất cân bằng 425 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.3. Chỉ số cân bằng (Balance factor – bf) • Chỉ số cân bằng (bf) của 1 node trên cây AVL là hiệu của chiều cao cây con bên trái và chiều cao của cây con bên phải. • Xét 1 node p bất kỳ trên cây AVL, chỉ số cân bằng của p bf(p)- chỉ có thể là 1 trong 3 giá trị sau: bf(p) = (hL-hR) 1 0 -1 Ḷch trƠi Cân bằng Ḷch ph i AVL Tree và Ếểỉ số Ếân bằnỂ Ếủa mỗi noếe 426 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.4. Cây AVL m t cân bằng khi thêm / xóa node • Khi thêm/xóa 1 node trên cây AVL có thể làm cây mất cân bằng  cần thực hiện cân bằng lại cây. • Khi đó, để giảm thiểu chi phí, việc cân bằng lại cây th ng chỉ thực hiện cục b trên nhánh bị mất căn bằng bằng cách xoay trái hoặc xoay phải. • Đặt tên gọi cho các node Ancestor Node AncL AncLL AncR AncLR AncRL AncRR 427 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.4. Cây AVL m t cân bằng khi thêm / xóa node • Đề nghị cấu trúc dữ liệu: Để ghi nhận mức đ cân bằng tại mỗi node gốc cây con, dùng thêm thành phần balFactor trong cấu trúc dữ liệu của mỗi node. #define RNE -2 /* Mất cân bằng bên phải*/ #define RH -1 /* Cây con phải cao hơn*/ #define EH 0 /* Hai cây con bằng nhau*/ #define LH 1 /* Cây con trái cao hơn*/ #define LNE 2 /* Mất cân bằng bên trái*/ struct AVLNode{ char balFactor; //Chỉ số cân bằng DataType data; AVLNode* pLeft; AVLNode* pRight; }; typedef AVLNode* AVLTree; 428 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.4. Cơy AVL m t cơn b ng khi thêm / xóa node 8.4.1. Cây con trái lệch trái (Left of Left) 8.4.2. Cây con phải lệch phải (Right of Right) 429 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.4. Cây AVL m t cân b ng khi thêm / xóa node 8.4.3. Cây con trái lệch phải (Right of Left) 8.4.4. Cây con phải lệch trái (Left of Right) 430 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.4. AVL Tree - Các trường hợp m t cân bằng sau khi thêm Tổng quát về các trường hợp mất cân bằng 1 2 3 4 Trong đó: •  (Left of Left) và  (Right of Right) là các ảnh đối xứng •  (Right of Left) và  (Left of Right) là các ảnh đối xứng 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.5. AVL Tree - Các tác vụ xoay 8.5.1. Tác vụ xoay đơn - Tr ng hợp  đ ợc giải b i phép xoay: A B B A a f d b b D E a c E D c e f 1  Tr ng hợp  là xoay m t ảnh đối xứng d e 4 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.5. AVL Tree - Các tác vụ xoay 8.5.1. Tác vụ xoay đơn Ví dụ: Tái cân bằng tr 433 ng hợp  Left of Left 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.5. AVL Tree - Các tác vụ xoay 8.5.1. Tác vụ xoay đơn Ví dụ: Tái cân bằng trường hợp  Right of Right 434 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.5. AVL Tree - Các tác vụ xoay 8.5.2. Tác vụ xoay kép ng hợp  đ ợc giải b i phép xoay kép (double): - Tr A B C  A A B C B A B C Left rotation  Tr C Right rotation ng hợp  là xoay m t ảnh đối xứng 2 3 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.5. AVL Tree - Các tác vụ xoay 8.5.2. Tác vụ xoay kép Ví dụ: Tái cân bằng trường hợp  Right of Left 436 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.5. AVL Tree - Các tác vụ xoay 8.5.2. Tác vụ xoay kép Ví dụ: Tái cân bằng trường hợp  Left of Right 437 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.6. Thực hi n cân bằng sau khi thêm 8.6.1. Tr ng hợp AncestorNode->balFactor = -2 = RNE Case 1 Case 2 Case 3a Case 3b Case 3c Height Height Height Height Height AncRLL h h-1 h AncRLR h-1 h h 1 -1 0 balFactor of AncR->bf -1 0 AncRL h h+1 AncRR h+1 h+1 AncRL->bf – AncRR->bf=-1 -1 0 AncRL->bf Left rotation Double rotation (right + left rotation) Ancestor Node = -2 AncL AncLL AncR AncLR AncRL AncRR 438 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.6. Thực hi n cân bằng sau khi thêm 8.6.1. Tr ng hợp AncestorNode->balFactor = -2 = RNE 8.6.1.1. T/Hợp AncRL->balFactor – AncRR->balFactor=-1 balFactor of Height AncL h AncR h+2 AncRL h AncRR h+1 Thực hiện cân bằng: - B1: xoay đơn cây con phải AncR của node này lên thành node gốc (m i) - B2: chuyển AncestorNode (cũ) thành node con trái của node gốc m i và AncestorNode (cũ) có hai cây con là AncL và AncRL. 439 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.6. Thực hi n cân bằng sau khi thêm 8.6.1. Tr ng hợp AncestorNode->balFactor = -2 = RNE 8.6.1.2. T/Hợp AncRL->balFactor= balFactor of Height AncL h AncR h+2 AncRL h+1 AncRR h+1 AncRR->balFactor=0 Thực hiện cân bằng: - B1: xoay đơn cây con phải AncR của node này lên thành node gốc (m i) - B2: chuyển AncestorNode (cũ) thành node con trái của node gốc m i và AncestorNode (cũ) có hai cây con là AncL và AncRL. 440 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.6. Thực hi n cân bằng sau khi thêm 8.6.1. Tr ng hợp AncestorNode->balFactor = -2 = RNE 8.6.1.3. T/Hợp AncRL có chiều cao là h+1 và AncRR có chiều cao là h (AncR->balFactor = 1) Cây con có node gốc AncestorNode có thể vào m t trong ba dạng: Height Case 3a Case 3b Case 3c AncRLL h h-1 h AncRLR h-1 h h 1 -1 0 AncRL->balFactor Để cân bằng lại AncestorNode thực hiện việc xoay kép: xoay cây con trái AncRL và xoay cây con phải AncR (Double Rotation). 441 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.6. Thực hi n cân bằng sau khi thêm 8.6.1. Tr ng hợp AncestorNode->balFactor = -2 = RNE 8.6.1.3. T/Hợp AncRL có chiều cao là h+1 và AncRR có chiều cao là h (AncR->Bal = 1) Height Case 3a AncRLL h AncRLR h-1 AncRL->balFactor 1 442 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.6. Thực hi n cân bằng sau khi thêm 8.6.1. Tr ng hợp AncestorNode->balFactor = -2 = RNE 8.6.1.3. T/Hợp AncRL có chiều cao là h+1 và AncRR có chiều cao là h (AncR->Bal = 1) Height Case 3b AncRLL h-1 AncRLR h AncRL->balFactor -1 443 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.6. Thực hi n cân bằng sau khi thêm 8.6.1. Tr ng hợp AncestorNode->balFactor = -2 = RNE 8.6.1.3. T/Hợp AncRL có chiều cao là h+1 và AncRR có chiều cao là h (AncR->Bal = 1) Height Case 3c AncLRL h AncLRR h AncRL->balFactor 0 444 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.6. Thực hi n cân bằng sau khi thêm 8.6.2. Tr ng hợp AncestorNode->balFactor = 2 = LNE - T ơng tự nh tr ng hợp 8.6.1, thực hiện xoay đơn hoặc xoay kép các nhánh phía ng ợc lại - Các dạng: balFactor of Case 1 Case 2 Case 3a Case 3b Case 3c Height Height Height Height Height AncLL h+1 h+1 h AncLR h h+1 h+1 AncL->bf 1 0 -1 AncLRL h-1 h h AncLRR h h-1 h -1 1 0 AncRL->bf Left rotation Double rotation (right + left rotation) Ancestor Node->bf = 2 AncL AncLL AncR AncLR AncRL AncRR 445 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.6. Th c hi n cân b ng sau khi thêm 8.6.2. Trường hợp AncestorNode->balFactor = 2 = LNE Case 1 AncLL h+1 AncLR h AncL->balFactor 1 446 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.6. Th c hi n cân b ng sau khi thêm 8.6.2. Trường hợp AncestorNode->balFactor = 2 = LNE Case 2 AncLL h+1 AncLR h+1 AncL->balFactor 0 447 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.6. Th c hi n cân b ng sau khi thêm 8.6.2. Trường hợp AncestorNode->balFactor = 2 = LNE Case 3 AncLL h AncLR h+1 AncL->balFactor -1 - Việc cân bằng lại AncestorNode đ ợc thực hiện thông qua phép xoay kép: xoay cây con phải AncLR và xoay cây con trái AncL (Double Rotation). - Cây con có node gốc AncestorNode có thể trong ba dạng sau: vào m t Case 3A Case 3B Case 3C AncLRL h-1 h h AncLRR h h-1 h AncRL->balFactor -1 1 0 448 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.6. Th c hi n cân b ng sau khi thêm 8.6.2. Trường hợp AncestorNode->balFactor = 2 = LNE Case 3A AncLRL AncLRR AncRL->balFactor h-1 h -1 449 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.6. Th c hi n cân b ng sau khi thêm 8.6.2. Trường hợp AncestorNode->balFactor = 2 = LNE Case 3B AncLRL AncLRR AncRL->balFactor h h-1 1 450 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.6. Th c hi n cân b ng sau khi thêm 8.6.2. Trường hợp AncestorNode->balFactor = 2 = LNE Case 3C AncLRL AncLRR AncRL->balFactor h h 0 451 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.7. Xơy d ng các hƠm cơn b ng l i cơy AVL 8.7.1. HƠm xoay đ n Left-Left void rotateLL(AVLTree &T) //xoay đơn { AVLNode* T1 = T->pLeft; T->pLeft = T1->pRight; T1->pRight = T; switch(T1->balFactor) { case LH: T->balFactor T1->balFactor break; case EH: T->balFactor T1->balFactor break; } T = T1; } 452 Left-Left = EH; = EH; = LH; = RH; 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.7. Xơy d ng các hƠm cơn b ng l i cơy AVL 8.7.2. HƠm xoay đ n Right-Right void rotateRR (AVLTree &T) //xoay đơn Right-Right { AVLNode* T1 = T->pRight; T->pRight = T1->pLeft; T1->pLeft = T; switch(T1->balFactor) { case RH: T->balFactor = EH; T1->balFactor= EH; break; case EH: T->balFactor = RH; T1->balFactor= LH; break; } T = T1; } 453 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.7. Xơy d ng các hƠm cơn b ng l i cơy AVL 8.7.3. HƠm xoay đ n Left-Right void rotateLR(AVLTree &T)//xoay kép Left-Right { AVLNode* T1 = T->pLeft; AVLNode* T2 = T1->pRight; T->pLeft = T2->pRight; T2->pRight = T; T1->pRight = T2->pLeft; T2->pLeft = T1; switch(T2->balFactor) case LH: T->balFactor = RH; { T1->balFactor = EH; break; case EH: T->balFactor = EH; T1->balFactor = EH; break; case RH: T->balFactor = EH; T1->balFactor = LH; break; } T2->balFactor = EH; T = T2; } 454 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.7. Xơy d ng các hƠm cơn b ng l i cơy AVL 8.7.4. HƠm xoay đ n Right-Left void rotateRL(AVLTree &T) //xoay kép Right-Left { AVLNode* T1 = T->pRight; AVLNode* T2 = T1->pLeft; T->pRight = T2->pLeft; T2->pLeft = T; T1->pLeft = T2->pRight; T2->pRight = T1; switch(T2->balFactor) case RH: T->balFactor = LH; { T1->balFactor = EH; break; case EH: T->balFactor = EH; T1->balFactor = EH; break; case LH: T->balFactor = EH; T1->balFactor = RH; break; } T2->balFactor = EH; T = T2; } 455 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.7. Xơy d ng các hƠm cơn b ng l i cơy AVL 8.7.5. HƠm cơn b ng khi cơy l ch v bên trái int balanceLeft(AVLTree &T) //Cân bằng khi cây bị lêch về bên trái { AVLNode* T1 = T->pLeft; switch(T1->balFactor) { case LH: rotateLL(T); return 2; case EH: rotateLL(T); return 1; case RH: rotateLR(T); return 2; } return 0; } 456 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.7. Xơy d ng các hƠm cơn b ng l i cơy AVL 8.7.6. HƠm cơn b ng khi cơy l ch v bên ph i int balanceRight(AVLTree &T ) //Cân bằng khi cây bị lêch về bên phải { AVLNode* T1 = T->pRight; switch(T1->balFactor) { case LH: rotateRL(T); return 2; case EH: rotateRR(T); return 1; case RH: rotateRR(T); return 2; } return 0; } 457 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.7. Xơy d ng các hƠm cơn b ng l i cơy AVL 8.7.7. HƠm thêm m t ph n t vƠo cơy AVL int insertNode(AVLTree &T, DataType X) { int res; if (T) { if (T->key == X) return 0; //đã có if (T->key > X) { res = insertNode(T->pLeft, X); if(res < 2) return res; switch(T->balFactor) { case RH: T->balFactor = EH; return 1; case EH: T->balFactor = LH; return 2; case LH: balanceLeft(T); return 1; } } 458 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.7. Xơy d ng các hƠm cơn b ng l i cơy AVL 8.7.7. HƠm thêm m t ph n t vƠo cơy AVL //phần sau là mã ḷnh ti p theo của slide lìn else // T->key < X { res = insertNode(T-> pRight, X); if(res < 2) return res; switch(T->balFactor) { case LH: T->balFactor = EH; return case EH: T->balFactor = RH; return case RH: balanceRight(T); return } } T = new TNode; if(T == NULL) return -1; //thiếu bộ nhớ T->key = X; T->balFactor = EH; T->pLeft = T->pRight = NULL; return 2; // thành công, chiều cao tăng 459 }// End of insertNode function tr 1; 2; 1; c 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.8. H y m t node kh i cơy cơn b ng - T ơng tự nh trong cây nhị phân tìm kiếm, để hủy m t node, cần tìm kiếm vị trí của node cần hủy là node con trái hoặc node con phải của m t node. - Việc hủy cũng chia làm ba tr trong cây nhị phân tìm kiếm: ng hợp nh đối v i • DelNode là node lá, • DelNode là node trung gian có 01 cây con, • DelNode là node có đủ 02 cây con. 460 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.8. H y m t node kh i cơy cơn b ng - Trong tr ng hợp DelNode có đủ 02 cây con, sử dụng ph ơng pháp hủy phần tử thế mạng vì theo ph ơng pháp này sẽ làm cho chiều cao của cây ít biến đ ng. - Sau khi hủy, nếu tính cân bằng của cây bị vi phạm ta sẽ thực hiện việc cân bằng lại. - Tuy nhiên việc cân bằng lại trong thao tác hủy sẽ phức tạp hơn nhiều do có thể xảy ra phản ứng dây chuyền 461 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.8. H y m t node kh i cơy cơn b ng 8.8.1. Xây dựng hàm delNode: hàm trả về giá trị 1 khi hủy thành công hoặc 0 khi không có X trong cây. Nếu sau khi hủy, chiều cao cây bị giảm, giá trị 2 sẽ đ ợc trả về: int delNode(AVLTree &T, DataType X) { int res; if(T==NULL) return 0; if(T->key > X) { res = delNode (T->pLeft, X); if(res < 2) return res; switch(T->balFactor) { case LH: T->balFactor = EH; return 2; case EH: T->balFactor = RH; return 1; case RH: return balanceRight(T); }// switch } // if(T->key > X) 462 // xem ti p slide sau 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.8. H y m t node kh i cơy cơn b ng 8.8.1. Xây dựng hàm delNode // ti p theo n i dung slide lìn tr c if(T->key < X) { res = delNode (T->pRight, X); if(res < 2) return res; switch(T->balFactor) { case RH: T->balFactor = EH; return 2; case EH: T->balFactor = LH; return 1; case LH: return balanceLeft(T); } } // if(T->key < X) else //T->key == X { AVLNode* p = T; if(T->pLeft == NULL) {T = T->pRight; res=2;} else if(T->pRight == NULL) {T=T->pLeft; res=2;} else //T có đủ c 2 con { res = searchStandFor(p,T->pRight); if(res < 2) return res; switch(T->balFactor) { case RH: T->balFactor = EH; return 2; case EH: T->balFactor = LH; return 1; case LH: return balanceLeft(T); } } delete p; return res; } 463 End of delNode function }// 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.8. H y m t node kh i cơy cơn b ng 8.8.2. HƠm h y m t ph n t trên cơy AVL int searchStandFor(AVLTree &p, AVLTree &q) //Tìm phần tử thế mạng { int res; if(q->pLeft) { res = searchStandFor(p, q->pLeft); if(res < 2) return res; switch(q->balFactor) { case LH: q->balFactor = EH; return 2; case EH: q->balFactor = RH; return 1; case RH: return balanceRight(T); } } else { p->key = q->key; p = q; q = q->pRight; return 2; } } 464 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.9. Nh n xét v thêm vƠ h y trên AVL 8.9.1. Độ phức tạp - Thao tác thêm m t node có đ phức tạp O(1) - Thao tác hủy m t node có đ phức tạp O(h) - V i cây cân bằng trung bình 2 lần thêm vào cây thì cần m t lần cân bằng lại; 5 lần hủy thì cần m t lần cân bằng lại 465 8. CỂY NH PHỂN TỊM KÍM CỂN B NG (Balanced Search Tree) 8.9. Nh n xét v thêm vƠ h y trên AVL 8.9.2. Nhận xét - Việc hủy 1 node có thể phải cân bằng dây chuyền các node từ gốc cho đên phần tử bị hủy trong khi thêm vào chỉ cần 1 lần cân bằng cục b - Đ dài đ ng tìm kiếm trung bình trong cây cân bằng gần bằng cây cân bằng hoàn toàn log2n, nh ng việc cân bằng lại đơn giản hơn nhiều - M t cây cân bằng không bao gi cao hơn 45% cây cân bằng hoàn toàn t ơng ứng dù số node trên cây là bao nhiêu 466