›
›

Bài giảng Cấu trúc dữ liệu - Nguyễn Thị Thúy Loan

pdf 54 trang hapham 3640
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu - Nguyễn Thị Thúy Loan", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_cau_truc_du_lieu_nguyen_thi_thuy_loan.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu - Nguyễn Thị Thúy Loan

  1. Cách đánh giá BÀI GIẢNG . Thực hành: 30% CẤU TRÚC DỮ LIỆU . Bài tập: 20% ThS. Nguyễn Thị Thúy Loan . Lý thuyết: 50% 6/8/2010 Nguyễn Thị Thúy Loan 2 Tài liệu tham khảo NỘI DUNG CHƯƠNG TRÌNH 1. Bài giảng: ThS. Nguyễn Hà Giang 2. Cấu trúc dữ liệu & giải thuật, Dương Anh Đức, Trần . Độ phức tạp thuật toán. Hạnh Nhi, NXB ĐHQG Tp.HCM, 2008. . Tìm kiếm và sắp xếp. 3. Cấu trúc dữ liệu, Nguyễn Trung Trực, ĐHBK, 1992. 4. Giải thuật & lập trình, Lê Minh Hoàng, ĐHSPHN, . Danh sách liên kết. 1999-2002. 5. Cấu trúc dữ liệu + giải thuật = chương trình, Nguyễn . Stack & Queue. Quốc Cường – Hoàng Đức Hải, NXB Giáo dục. 6. Fundamentals of Data Structures, Ellis Horowitz, . Cây. Sartaj Sahni. 6/8/2010 Nguyễn Thị Thúy Loan 3 6/8/2010 Nguyễn Thị Thúy Loan 4
  2. NỘI DUNG Chương I ĐỘ PHỨC TẠP THUẬT I. ĐO THỜI GIAN TOÁN II. DỰA VÀO ĐỘ LỚN CỦA DỮ LIỆU III. MỘT SỐ CÔNG THỨC THƯỜNG DÙNG IV. CÁCH TÍNH ĐỘ PHỨC TẠP ThS. Nguyễn Thị Thúy Loan 6/8/2010 Nguyễn Thị Thúy Loan 6 Đo thời gian Dựa vào độ lớn của dữ liệu Gọi t(n) là thời gian thực hiện của thuật toán A (thông thường là chu kỳ của CPU), t(n) sẽ là một trong các loại: a. O(1): độ phức tạp là một hằng số. VD: for (int i=1; i<= 10 ; i++) printf (“%d”, i ); Phép so sánh: i = 1 10 và i =11 (để dừng) = 11. Phép gán: i = 1 + (i = 1 10) = 11. 6/8/2010 Nguyễn Thị Thúy Loan 7 6/8/2010 Nguyễn Thị Thúy Loan 8
  3. Dựa vào độ lớn của dữ liệu Dựa vào độ lớn của dữ liệu b. O(log n): Tìm nhị phân. 2 Nhận xét c. O(√n): Kiểm tra một số có phải là số . Trừ số 2, tất cả các số chẵn không phải nguyên tố? là số nguyên tố. VD: Kiểm tra số nguyên tố, xét i=2 → (n/2), . Các số lẻ không có ước số chẵn. nếu i là ước số của n n không phải là . i là ước số của n → (n/i) là ước số của n. số nguyên tố, ngược lại n là nguyên tố. 6/8/2010 Nguyễn Thị Thúy Loan 9 6/8/2010 Nguyễn Thị Thúy Loan 10 Dựa vào độ lớn của dữ liệu Một số công thức thường dùng n a.  1 n d. O(n): Độ phức tạp tuyến tính (áp dụng i 1 b b a 1 duyệt mảng, dãy). 1 1 1 b a 1 (a b N) i a i 1 i 1 e. O(nlog n): “thuật toán Logarit” (áp dụng 2 n n ( n 1) b.  i sắp xếp mảng). i 1 2 n n(n 1) (a 1)(a 1 1) f. O(nα)(α>1): đa thức. i i a 2 n g. O(2 ), O(n!): mũ (áp dụng liệt kê tất cả 2 2 2 n n (n 1) i các tập con của tập gồm n phần tử).  i 1 2 6/8/2010 Nguyễn Thị Thúy Loan 11 6/8/2010 Nguyễn Thị Thúy Loan 12
  4. Một số công thức thường dùng Cách tính độ phức tạp Ví dụ 1: Cho thuật toán tính tổng như sau: n n(n 1)(2n 1) long Tong (int n) c. i2  { long s = 0; i 1 6 n for (int i = 1 ; i <= n ; i ++) 2 n(n 1)(2n 1) a(a 1)(2a 1) i s += i; i a 6 return s; 2 n n n 2 (n 1)2 } d. i3 i i 1 i 1 4 a. Tính độ phức tạp của thuật toán. b. Cải tiến để thuật toán có độ phức tạp nhỏ hơn. 6/8/2010 Nguyễn Thị Thúy Loan 13 6/8/2010 Nguyễn Thị Thúy Loan 14 Cách tính độ phức tạp Cách tính độ phức tạp GIẢI n n ( n 1) n b) Thực chất là tính: s i  2 a) Số phép so sánh:  1 1 n 1 i 1 i 1 n Cải tiến: long Tong (int n) Số phép gán: 1 1 (1 1) 2 2n { return (n * (n + 1))/2; i 1 Độ phức tạp là O(n). } Không phép so sánh, không phép gán O(1). 6/8/2010 Nguyễn Thị Thúy Loan 15 6/8/2010 Nguyễn Thị Thúy Loan 16
  5. Cách tính độ phức tạp Cách tính độ phức tạp Vd3: Cho thuật toán sau: Vd2: Cho thuật toán sau: long Tong (int n) long Tong (int n) { long s = 0; { long s = 0; for (int i = 1 ; i <= n ; i ++) for (int i = 1 ; i <= n ; i ++) for (int j = 1 ; j<= i*i ; j ++) for (int j = i ; j<= n ; j ++) s += j; s += j; return s; return s; } } a. Tính độ phức tạp của thuật toán. a. Tính độ phức tạp của thuật toán. b. Cải tiến để thuật toán có độ phức tạp nhỏ hơn. b. Cải tiến để thuật toán có độ phức tạp nhỏ hơn. 6/8/2010 Nguyễn Thị Thúy Loan 17 6/8/2010 Nguyễn Thị Thúy Loan 18 Chương II Nội dung trình bày TÌM KIẾM VÀ SẮP . TÌM KIẾM XẾP . SẮP XẾP ThS. Nguyễn Thị Thúy Loan Tham khảo bài giảng ThS. Nguyễn Hà Giang 6/8/2010 Nguyễn Thị Thúy Loan 20
  6. Tìm kiếm Tìm kiếm . Tìm kiếm là quá trình xác định một đối . Tìm kiếm là thao tác quan trọng & thường tượng nào đótrong một tập các đối tượng. được sử dụng trong tin học. Kết quả trả về là đối tượng tìm được (nếu o Tìm kiếm một nhân viên trong danh sách có) hoặc một chỉ số (nếu có) xác định vị trí nhân viên. của đối tượng trong tập đó. o Tìm một sinh viên trong danh sách sinh viên . Việc tìm kiếm dựa theo một trường nào đó của một lớp của đối tượng, trường này là khóa (key) o Tìm kiếm một tên sách trong thư viện. của việc tìm kiếm. 6/8/2010 Nguyễn Thị Thúy Loan 21 6/8/2010 Nguyễn Thị Thúy Loan 22 Tìm kiếm Tìm kiếm Tìm ki m . VD: Muốn tìm sinh viên tên Nguyễn Văn A Tìm kiếm có trong lớp hay không? Tìm kiếm tuyến tính Tìm kiếm nhị phân . Ta có hai cách tìm kiếm như sau: Tập dữ liệu Tập dữ liệu đã bất kỳ được sắp xếp 6/8/2010 Nguyễn Thị Thúy Loan 23 6/8/2010 Nguyễn Thị Thúy Loan 24
  7. Tìm kiếm Tìm kiếm tuyến tính Bài toán được mô tả như sau: . Ý tưởng chính: duyệt tuần tự từ phần tử . Tập dữ liệu được lưu trữ là dãy a0, a2, , đầu tiên, lần lượt so sánh khóa tìm kiếm an-1. Giả sử chọn cấu trúc dữ liệu mảng để với khoá tương ứng của các phần tử lưu trữ dãy số này trong bộ nhớ chính, có trong danh sách. Cho đến khi gặp phần khai báo: int a[MAX]; tử cần tìm hoặc đến khi duyệt hết danh . Khóa cần tìm là x, có kiểu nguyên: int x; sách. 6/8/2010 Nguyễn Thị Thúy Loan 25 6/8/2010 Nguyễn Thị Thúy Loan 26 Các bước thực hiện Tìm kiếm tuyến tính . Bước 1: i = 0; Ví dụ: Cho dãy số a, giá trị tìm x = 8: . Bước 2: So sánh a[i] với x, có hai t.hợp: 12258164 o a[i] = x: Tìm thấy Trả về vị trí i Tìm được o a[i] x: Sang bước 3 x = 8 . Bước 3: i = i + 1// xét phần tử kế tiếp oNếu i≥N:Hết mảng không thấy Trả về -1 12 2 5 8 1 6 4 oNếu i N: Quay lại bước 2 6/8/2010 Nguyễn Thị Thúy Loan 27 6/8/2010 Nguyễn Thị Thúy Loan 28
  8. Tìm kiếm tuyến tính Tìm kiếm tuyến tính 1. Cài đặt bình thường. Nhận xét: 2. Cải tiến lại bằng cách sử dụng phần tử . Giải thuật tìm kiếm tuyến tính không phụ cầm canh. thuộc vào thứ tự của các phần tử trong mảng, do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một dãy bất kỳ. 6/8/2010 Nguyễn Thị Thúy Loan 29 6/8/2010 Nguyễn Thị Thúy Loan 30 Tìm kiếm tuyến tính Tìm kiếm nhị phân Khái niệm: . Một thuật toán có thể được cài đặt theo . Phép tìm kiếm nhị phân được áp dụng trên dãy nhiều cách khác nhau, kỹ thuật cài đặt khóa đã có thứ tự: k[0] k[0] k[n-1]. ảnh hưởng nhiều đến tốc độ thực hiện. . Phương pháp này dựa trên ý tưởng sau: Ví dụ như thuật toán cải tiến sẽ chạy Giả sử ta cần tìm trong đoạn a[left right] với khoá nhanh hơn thuật toán trước do vòng lặp tìm kiếm là x, trước hết ta xét phần tử giữa while chỉ so sánh một điều kiện a[mid], với mid = (left + right)/2. 6/8/2010 Nguyễn Thị Thúy Loan 31 6/8/2010 Nguyễn Thị Thúy Loan 32
  9. Tìm kiếm nhị phân Các bước thực hiện . Nếu a[mid] x thì có nghĩa là đoạn a[mid] đến o a[mid] = x: Tìm thấy Trả về vị trí mid o a[mid] >x: right = mid -1; a[right] chỉ chứa khoá > x, ta tiến hành tìm o a[mid] right. o Ngược lại: Trả về -1// đã xét hết các phần tử 6/8/2010 Nguyễn Thị Thúy Loan 33 6/8/2010 Nguyễn Thị Thúy Loan 34 Tìm kiếm nhị phân Tìm kiếm nhị phân Ví dụ: cho dãy số gồm 8 phần tử bên dưới và x = 8: Nhận xét: 1245681215 . Thuật giải nhị phân dựa vào quan hệ giá trị X = 8 của các phần tử trong mảng để định hướng 1 2 4 5 6 8 12 15 trong quá trình tìm kiếm, do vậy chỉ áp dụng Left = 0 Mid = 3 Right = 7 Đoạn tìm kiếm được với dãy đã có thứ tự. X = 8 . Thuật giải nhị phân tìm kiếm nhanh hơn tìm = kiếm tuyến tính. 1 2 4 5 6 8 12 15 Left = 4 Mid = 5 Right = 7 Đoạn tìm kiếm 6/8/2010 Nguyễn Thị Thúy Loan 35 6/8/2010 Nguyễn Thị Thúy Loan 36
  10. Tìm kiếm nhị phân Sắp xếp . Sắp xếp là quá trình bố trí lại các phần tử . Tuy nhiên khi áp dụng thuật giải nhị của một tập đối tượng theo một thứ tự phân thì cần phải quan tâm đến chi phí nhất định. cho việc sắp xếp mảng. Vì khi mảng . Ví dụ: {1, 2, 5, 7, 9, 12}, {14, 12, 7, 5, 2, 1} được sắp thứ tự rồi thì mới tìm kiếm nhị {“An” “Binh” “Dương” “Hương”} phân. 6/8/2010 Nguyễn Thị Thúy Loan 37 6/8/2010 Nguyễn Thị Thúy Loan 38 Sắp xếp Sắp xếp . Dữ liệu thường được tổ chức thành mảng . Việc sắp xếp là một bài toán phổ biến các mẫu tin. trong tin học. Do các yêu cầu tìm kiếm . Mỗi mẫu tin thường có một số các trường thuận lợi, sắp xếp kết xuất cho các bảng dữ liệu khác nhau. biểu . Trường tham gia quá trình tìm kiếm gọi là khóa (key). . Việc sắp xếp sẽ được tiến hành dựa vào giá trị khoá này. 6/8/2010 Nguyễn Thị Thúy Loan 39 6/8/2010 Nguyễn Thị Thúy Loan 40
  11. Các phương pháp sắp xếp Mô tả bài toán . Để tiện cho việc minh họa các thuật toán 1. Đổi chỗ trực tiếp (interchange Sort) sắp xếp ta mô tả bài toán như sau: 2. Chèn trực tiếp (insertion Sort) Cho một mảng a gồm các phần tử, mỗi 3. Chọn trực tiếp (Selection Sort) phần tử trong mảng có một thuộc tính 4. Nổi bọt (Bubble Sort ) khóa. Hãy sắp xếp tăng hoặc giảm các 5. Shell sort phần tử trong mảng theo giá trị khóa này. 6. Quick sort 6/8/2010 Nguyễn Thị Thúy Loan 41 6/8/2010 Nguyễn Thị Thúy Loan 42 Mô tả bài toán Interchange Sort Ý tưởng: . Do mỗi phần tử có giá trị khóa nên ta gọi . Xuất phát từ đầu dãy, lần lượt tìm những k[0 n-1] là mảng các khóa của các phần phần tử còn lại không thỏa thứ tự với tử trong e. phần tử đang xét. Với mỗi phần tử tìm . Yêu cầu: sắp xếp các giá trị này sao cho được mà không thoả thứ tự mảng k có thứ tự tăng hoặc giảm. • Thực hiện hoán vị để thỏa thứ tự . Lặp lại tương tự với các phần tử tiếp theo 6/8/2010 Nguyễn Thị Thúy Loan 43 6/8/2010 Nguyễn Thị Thúy Loan 44
  12. Các bước thực hiện Ví dụ minh họa B1: i = 0; // đầu dãy B2: j = i +1; // duyệt qua các phần tử sau i j B3: while j < n do o if a[j] < a[i] then Swap(a[i], a[j]); 10 3 7 6 2 5 4 16 o j = j +1; i B4: i = i +1; o if i < n then B2; o else Kết thúc! 6/8/2010 Nguyễn Thị Thúy Loan 45 6/8/2010 Nguyễn Thị Thúy Loan 46 Cài đặt Insertion Sort Ý tưởng: . Cho dãy ban đầu a[0], a[2], , a[n-1], ta có thể xem dãy con gồm một phần tử a[0] đã được sắp. . Sau đó thêm a[1] vào đoạn a[0] sao cho a[0] a[1] được sắp. 6/8/2010 Nguyễn Thị Thúy Loan 47 6/8/2010 Nguyễn Thị Thúy Loan 48
  13. Insertion Sort Các bước thực hiện B1: i = 1;//giả sử có đoạn a[0] đã được sắp . Tiếp tục thêm a[2] vào để có a[0] a[1] a[2] B2: x= a[i]; được sắp o Tìm được vị trí cần chèn x vào là pos . Cho đến khi thêm xong a[n-1] vào đoạn B3: Dời chỗ các phần tử từ a[pos] a[i-1] a[0] a[1] a[n-2] đoạn a[0] a[1] a[n-2] sang phải một vị trí để dành chỗ cho a[i]. B4: a[pos] = x;// có a[0] a[i] được sắp. a[n-1] được sắp. B5: i = i +1; o Nếu i < n: Lặp lại B2 o Ngược lại: Dừng Dãy đã được sắp 6/8/2010 Nguyễn Thị Thúy Loan 49 6/8/2010 Nguyễn Thị Thúy Loan 50 Selection Sort Các bước thực hiện Ý tưởng: B1: i = 0 . Lượt thứ nhất, chọn trong dãy khoá k[0 n-1] ra B2: Tìm phần tử a[min] nhỏ nhất trong dãy khóa nhỏ nhất và đổi giá trị với k[0], khi đók[0] hiện hành từ a[i] đến a[n-1] sẽ trở thành khoá nhỏ nhất. B3: Hoán vị a[i] và a[min] . Lượt thứ hai, chọn trong dãy khoá k[1 n-1] ra B4: Nếu i < n -1 thì i= i+1 Lặp B2 khóa nhỏ nhất và đổi giá trị với k[1] . Ngược lại Dừng . Lượt n-2, chọn giá trị nhỏ nhất trong k[n-2] và Ví dụ: Cho dãy số như sau: k[n-1] ra khoá nhỏ nhất và đổi giá trị với k[n-2]. 122851641 6/8/2010 Nguyễn Thị Thúy Loan 51 6/8/2010 Nguyễn Thị Thúy Loan 52
  14. Bubble Sort Các bước thực hiện Ý tưởng: B1: i=0; // lần xử lý đầu tiên . Xuất phát từ cuối dãy, đổi chỗ các cặp phần B2: j=n-1; // duyệt từ cuối ngược về i tử kế cận để đưa phần tử nhỏ hơn về đầu. Trong khi (j>i) thực hiện: . Sau đó ở bước tiếp theo không xét phần tử o Nếu a[j] n-1: Hết dãy Dừng cặp phần tử nào được xét. o Ngược lại: quay lại B2 6/8/2010 Nguyễn Thị Thúy Loan 53 6/8/2010 Nguyễn Thị Thúy Loan 54 ShellSort ShellSort Ý tưởng: . Xét một dãy a[0] a[n-1], cho một số . Cải tiến insertion sort nguyên h (1 h n), chia dãy thành h dãy o Hạn chế phương pháp chèn: khi luôn con như sau: chèn 1 phần tử vào đầu dãy! o Dãy con 1: a[1], a[1+h], a[1+2h] . ShellSort cải tiến bằng cách chia làm o Dãy con 2: a[2], a[2+h], a[2+2h] nhiều dãy con và thực hiện phương pháp o Dãy con 3: a[3], a[3+h], a[3+2h] chèn trên từng dãy con. o Dãy con h: a[h], a[2h], a[3h] 6/8/2010 Nguyễn Thị Thúy Loan 55 6/8/2010 Nguyễn Thị Thúy Loan 56
  15. Ví dụ minh họa Ý tưởng . VD: cho dãy n = 8, h = 3 . Với mỗi bước h, áp dụng Insertion Sort 1037625416 trên từng dãy con độc lập để làm mịn dần các phần tử trong dãy chính. Dãy chính 10 3 7 6 2 5 4 16 . Tiếp tục làm tương tự đối với bước h div Dãy con 1 10 6 4 2 cho đến h = 1. . Khi h =1 thực hiện Insertion Sort trên 1 Dãy con 2 3216 dãy duy nhất là dãy chính Dãy con 3 75 . Kết quả được dãy phần tử được sắp. 6/8/2010 Nguyễn Thị Thúy Loan 57 6/8/2010 Nguyễn Thị Thúy Loan 58 Các bước thực hiện QuickSort B1: chọn k khoảng cách h[0], h[1], ,h[k-1], và . Thuật toán do Hoare đề xuất i = 0; o Tốc độ trung bình nhanh hơn thuật toán B2: Chia dãy ban đầu thành các dãy con có khác. bước nhảy là h[i]. o Do đó Hoare dùng “quick” để đặt tên o Thực hiện sắp xếp từng dãy con bằng . Ý tưởng chính: QS phân hoạch dãy ban insertion sort. đầu thành hai phần dựa vào một giá trị x. B3: i = i+1 o Nếu i ≥ k: Dừng o Dãy 1: gồm các phần tử a[i] nhỏ hơn x o Ngược lại: Bước 2. o Dãy 2: gồm các phần tử a[i] lớn hơn x 6/8/2010 Nguyễn Thị Thúy Loan 59 6/8/2010 Nguyễn Thị Thúy Loan 60
  16. QuickSort Các bước thực hiện . B1: Phân hoạch dãy a[l] a[r] thành các . Phân hoạch dãy cần sắp a[l] a[r] thành dãy con: ba phần: o Dãy con 1: a[l] a[j] x o a[k] > x, với k = j n-1 . B2: Trong đóx làmột giá trị nào đó trong o Nếu (l x o Nếu (i x j ; ThS. Nguyễn Thị Thúy Loan o Nếu i <= j Swap(a[i], a[j]) B3: Nếu i <= j Bước 2; o Ngược lại Dừng. Tham khảo bài giảng ThS. Nguyễn Hà Giang
  17. Nội dung DSLK đơn - Giới thiệu . Mảng 1 chiều . Danh sách liên kết đơn o Kích thước cố định o Giới thiệu o Chèn 1 phần tử vào mảng rất khó o Cài đặt o Các phần tử tuần tự theo chỉ số 0 n-1 o Thao tác o Truy cập ngẫu nhiên o Ứng dụng chèn . Danh sách vòng . Danh sách liên kết kép 0 1 234 n-2 n-1 6/8/2010 Nguyễn Thị Thúy Loan 65 6/8/2010 Nguyễn Thị Thúy Loan 66 Giới thiệu Giới thiệu Danh sách liên kết . Cấp phát động lúc chạy chương trình Insert, . Các phần tử nằm rải rác ở nhiều nơi trong bộ Delete nhớ . Kích thước danh sách chỉ bị giới hạn do RAM . Thao tác thêm Xóa đơn giản 6/8/2010 Nguyễn Thị Thúy Loan 67 6/8/2010 Nguyễn Thị Thúy Loan 68
  18. Định nghĩa Ôn pointer . Danh sách liên kết đơn là chuỗi các Node, . Nhắc lại pointer được tổ chức theo thứ tự tuyến tính 1FF0 1FF4 int i, *pi; i ??pi . Mỗi Node gồm 2 phần: o Phần Data, information i 1FF0 1FF4 pi = &i; *pi ? pi 1FF0 o Phần link hay con trỏ trỏ đến Node kế tiếp i 1FF0 1FF4 i = 10 or *pi = 10 *pi 10 pi 1FF0 6/8/2010 Nguyễn Thị Thúy Loan 69 6/8/2010 Nguyễn Thị Thúy Loan 70 Minh họa Minh họa . Mô tả danh sách Data Link . Ví dụ: Địa chỉ pHead 700 500 A A A A 1 2 3 n ‘D’ 500 ‘S’ 600 600 300 null ‘L’ 300 ‘D’ null Head Node Node Tail Node 6/8/2010 Nguyễn Thị Thúy Loan 71 6/8/2010 Nguyễn Thị Thúy Loan 72
  19. Khai báo phần data Khai báo phần data . Khai báo danh sáchLK typedef struct Node . Data { Cấu trúc Data info; Node o Kiểu dữ liệu định nghĩa trước Node * next; }; o Chứa dữ liệu, thông tin của từng Node Typedef struct Node { DATA info ; typedef struct Node typedef struct Node { { Node * next ; int info; SinhVien info; }; Node * next; Node * next; Data: int, long, float, SV, }; }; 6/8/2010 NguyNVễn Thị Thúy, . Loan 73 6/8/2010 Nguyễn Thị Thúy Loan 74 Khai báo và khởi tạo Thao tác cơ bản . Tạo một nút mới typedef struct Node . Thêm phần tử vào đầu danh sách { . Thêm phần tử vào cuối danh sách Data info; . Thêm phần tử vào sau q Node * next; Phần minh . Xóa phần tử đầu. họa sẽ dùng }; Data là int . Xóa phần tử sau q Node* h; h quản lý danh sách . Tìm kiếm. Node* h = NULL; Khởi tạo danh sách . Sắp xếp. 6/8/2010 Nguyễn Thị Thúy Loan 75 6/8/2010 Nguyễn Thị Thúy Loan 76
  20. Tạo nút mới Thêm phần tử vào đầu DS Node * Getnode (Data x) . Thêm vào đầu danh sách p new { Node * p = new Node; h h if ( p == NULL ) return NULL; p info = x; p next = NULL; p p return p ; h h } 6/8/2010 Nguyễn Thị Thúy Loan 77 6/8/2010 Nguyễn Thị Thúy Loan 78 Thêm phần tử vào đầu DS Thêm phần tử vào cuối DS 6/8/2010 Nguyễn Thị Thúy Loan 79 6/8/2010 Nguyễn Thị Thúy Loan 80
  21. Thêm vào sau phần tử q Xóa phần tử đầu . Thêm vào sau Node q trong danh sách . Xóa phần tử đầu danh sách p new p h q q h p p h h q q p 6/8/2010 Nguyễn Thị Thúy Loan 81 6/8/2010 Nguyễn Thị Thúy Loan 82 Xóa phần tử sau q Xóa toàn bộ danh sách . Xóa phần tử sau Node q trong danh sách h q p p q p h q p 6/8/2010 Nguyễn Thị Thúy Loan 83 6/8/2010 Nguyễn Thị Thúy Loan 84
  22. Xóa toàn bộ danh sách Tìm kiếm . Tìm phần tử lớn nhất. . Tìm vị trí phần tử lớn nhất. . Tìm phần tử có giá trị bằng x. 6/8/2010 Nguyễn Thị Thúy Loan 85 6/8/2010 Nguyễn Thị Thúy Loan 86 Sắp xếp Sắp xếp void Selection_sort (Node* h) void Interchange_sort (Node * h) { { } } 6/8/2010 Nguyễn Thị Thúy Loan 87 6/8/2010 Nguyễn Thị Thúy Loan 88
  23. Duyệt danh sách Minh họa in danh sách void Duyet (Node* h [, Node * t] ) p h 3000 5000 4000 { for (Node* p = h; p ; p = p next) 3000 4 5000 10 4000 5 NULL ; p = h; } while (p!=NULL) { printf(“ %5d”, p info); p = p next; } 6/8/2010 Nguyễn Thị Thúy Loan 89 6/8/2010 Nguyễn Thị Thúy Loan 90 Minh họa in danh sách Minh họa in danh sách p 3000 p 3000 h 3000 5000 4000 h 3000 5000 4000 3000 4 5000 10 4000 5 NULL 3000 4 5000 10 4000 5 NULL p = h; p = h; while (p!=NULL) while (p!=NULL) { { printf(“ %5d”, p info); printf(“ %5d”, p info); p = p next; p = p next; } } 6/8/2010 Nguyễn Thị Thúy Loan 91 6/8/2010 Nguyễn Thị Thúy Loan 92
  24. Minh họa in danh sách In danh sách void Indanhsach(Node *h) p 3000 { for (Node *p = h; p; p = p next) printf(“%5d”, p info); h 3000 5000 4000 3000 4 5000 10 4000 5 NULL } void Indanhsach (Node * h) { Node* p = h; p = h; while (p!=NULL) while (p!=NULL) { printf(“ %5d”, p info); { p = p next; printf(“ %5d”, p info); } p = p next; } } 6/8/2010 Nguyễn Thị Thúy Loan 93 6/8/2010 Nguyễn Thị Thúy Loan 94 Bài tập bổ sung Bài tập bổ sung 1. Đếm số Node có trong danh sách 6. Tạo danh sách (h1, t1) chứa các phần tử 2. Đếm số phần tử dương trong danh sách dương trong danh sách đã cho. 3. Đếm số phần tử lớn hơn phần tử kề sau 7. Xóa 1 phần tử có khoá là x 4. Kiểm tra mọi phần tử trong danh sách có 8. Thêm phần tử x vào danh sách đã có thứ chẵn không? tự (tăng) sao cho sau khi thêm vẫn có thứ 5. Kiểm tra mọi phần tử có được sắp xếp tự (tăng). tăng? 6/8/2010 Nguyễn Thị Thúy Loan 95 6/8/2010 Nguyễn Thị Thúy Loan 96
  25. Bài tập bổ sung Danh sách liên kết kép . Cho phép di chuyển 2 chiều đến nút trước 9. Xóa các phần tử trùng nhau trong danh và sau. sách, chỉ giữ lại duy nhất một phần tử (*) o Liên kết nút trước là: prev 10.Trộn hai danh sách có thứ tự tăng thành o Liên kết nút sau là: next một danh sách cũng có thứ tự tăng. (*) . Nút đầu có prev là NULL . Nút cuối có next là NULL A1 A2 An 6/8/2010 Nguyễn Thị Thúy Loan 97 6/8/2010 Nguyễn Thị Thúy Loan 98 Khai báo Các thao tác cơ bản . Tạo nút mới typedef struct Node { . Thêm vào đầu/ cuối Data info; . Thêm vào trước q/ sau q Node* pre; trỏ đến nút trước . Xóa đầu/ cuối Node* next; trỏ đến nút sau }; . Xóa sau q h quản lý danh sách Node *h; . Duyệt danh sách h = NULL; Khởi tạo danh sách . Duyệt từ cuối danh sách . Sắp xếp danh sách 6/8/2010 Nguyễn Thị Thúy Loan 99 6/8/2010 Nguyễn Thị Thúy Loan 100
  26. Tạo một nút mới Thêm đầu Node *Getnode (Data x) { Node *p = new Node; if (p == NULL) return NULL; p info = x; p next = NULL; p pre = NULL; return p; } 6/8/2010 Nguyễn Thị Thúy Loan 101 6/8/2010 Nguyễn Thị Thúy Loan 102 Thêm cuối Thêm trước q q p newNode new q 6/8/2010 Nguyễn Thị Thúy Loan 103 6/8/2010 Nguyễn Thị Thúy Loan 104
  27. Thêm trước q, sau q (q ≠ ) Xóa đầu newNode p q r p q r 6/8/2010 Nguyễn Thị Thúy Loan 105 6/8/2010 Nguyễn Thị Thúy Loan 106 Xóa cuối Xóa sau q (q ≠ t) q q p r 6/8/2010 Nguyễn Thị Thúy Loan 107 6/8/2010 Nguyễn Thị Thúy Loan 108
  28. Duyệt danh sách Sắp xếp danh sách BB Cách 1: void Bubble_sort( Node *h, Node *t) for (Node *p = h; p; p = p next) { for (Node *p= h; p; p = p next) ; for (Node*q =t; q!= p; q = q pre) Cách 2: if (q info ; } 6/8/2010 Nguyễn Thị Thúy Loan 109 6/8/2010 Nguyễn Thị Thúy Loan 110 Bài tập bổ sung Bài tập bổ sung 1. Đếm số phần tử nguyên tố trong danh sách 5. Tìm giá trị của phần tử nhỏ nhất trong danh 2. Đếm số phần tử lớn hơn hai phần tử xung sách? quanh. 6. Tìm giá trị phần tử dương nhỏ nhất trong 3. Kiểm tra mọi phần tử trong danh sách có danh sách? phải là chính phương không? 7. Đếm số lần xuất hiện của phần tử x trong 4. Kiểm tra mọi phần tử có được sắp xếp danh sách. giảm? 6/8/2010 Nguyễn Thị Thúy Loan 111 6/8/2010 Nguyễn Thị Thúy Loan 112
  29. Chương IV STACK & QUEUE ThS. Nguyễn Thị Thúy Loan 8/6/20106/8/2010Nguyễn Nguy Thị Thúyễn Th Loanị Thúy – CLoanĐ PTTH II 114 Giới thiệu Hiện thực stack . LIFO: Last In First Out Mảng 1 chiều Danh sách LK Kích thước stack Cấp phát . Thao tác Pop, Push chỉ diễn ra ở 1 đầu khi quá thiếu, lúc động! quá thừa Push/Pop khá dễ dàng Push / Pop hơi phức tạp 6/8/2010 Nguyễn Thị Thúy Loan 115 6/8/2010 Nguyễn Thị Thúy Loan 116
  30. Tổ chức theo mảng 1 chiều Khai báo Tạo cấu trúc dữ liệu cho stack Mảng 1 chiều #define Max 100 // stack chứa 100 ptử Kích thước stack khi quá thiếu, lúc quá thừa typedef struct Stack { int top; Data a[Max]; }; Stack s;// khai báo s // s.top; Push / Pop hơi phức tạp // s.a[]; 6/8/2010 Nguyễn Thị Thúy Loan 117 6/8/2010 Nguyễn Thị Thúy Loan 118 Thao tác Khởi tạo Stack . Các thao tác trên stack InitStack Pop void Init (Stack &s) IsEmpty Push Top GetSize { s.top = 0; pTop } P ush op P Đầu danh sách 6/8/2010 Nguyễn Thị Thúy Loan 119 6/8/2010 Nguyễn Thị Thúy Loan 120
  31. Kiểm tra rỗng/ đầy Thêm phần tử vào Stack int Push (Stack &s, Data x) int isEmpty (Stack s) { if (s.top < MAX) { return s.top = = 0; { s.a[s.top] =x; } s.top ++; return 1; int isFull (Stack s) } { return s.top == MAX; return 0; } } 6/8/2010 Nguyễn Thị Thúy Loan 121 6/8/2010 Nguyễn Thị Thúy Loan 122 Thêm phần tử vào Stack Lấy phần tử ra khỏi Stack int Push (Stack &s, Data x) int Pop (Stack &s, Data &x) { if (isFull (s)) { if (isEmpty (s)) return 0; return 0; s.a[s.top ++] =x; x= s.a[ s.top]; return 1; return 1; } } 6/8/2010 Nguyễn Thị Thúy Loan 123 6/8/2010 Nguyễn Thị Thúy Loan 124
  32. Tổ chức theo DSLK Khai báo Danh sách LK Tạo cấu trúc dữ liệu cho stack Cấp phát động! typedef struct NodeS { Data info; NodeS *next; }; Push/Pop khá dễ dàng typedef NodeS* Stack; 6/8/2010 Nguyễn Thị Thúy Loan 125 6/8/2010 Nguyễn Thị Thúy Loan 126 Kiểm tra rỗng/ khởi tạo Thêm phần tử vào Stack . Push int isEmpty (Stack s) o Tạo Node mới { return s = = NULL; o Đưa vào đầu stack } pTop pTop void Init (Stack &s) Push new { s = NULL; 2 9 8 2 9 } 6/8/2010 Nguyễn Thị Thúy Loan 127 6/8/2010 Nguyễn Thị Thúy Loan 128
  33. Lấy phần tử ra khỏi Stack Top . Top: Pop: o Xem nội dung của phần tử đầu stack Lấy ra phần tử đầu danh sách pTop Trả về nội dung và giải phóng nút Top pTop pTop 5 2 9 Pop pTop 5 2 9 2 9 5 2 9 6/8/2010 Nguyễn Thị Thúy Loan 129 6/8/2010 Nguyễn Thị Thúy Loan 130 Ứng dụng Tháp Hanoi . Tháp Hanoi Move( số đĩa, cọc nguồn, cọc đích, cọc tạm) . Ứng dụng stack 123 123 . Khử đệ quy: . Tháp Hanoi, QuickSort Move(n-1, 1, 2, 3); 123 Kết quả . Áp dụng cho các bài toán dùng mô hình Move(1, 1, 3, 2); Move(n-1, 2, 3, 1); LIFO 123 123 6/8/2010 Nguyễn Thị Thúy Loan 131 6/8/2010 Nguyễn Thị Thúy Loan 132
  34. Tháp Hanoi Tháp Hanoi 2. Pop: Stack {n, src, des) . Stack khử đệ quy . Nếu n = 1: move src des o {n, src, des} Stack lưu . Ngược lại: o Các cọc đánh số 1, 2, 3 trữ thứ tự ngược o temp = 6 – (src+des) o Cọc temp = 6 – (src+des) o Push stack: {n-1, temp, des} 1. Push stack: {n, 1, 2} o Push stack: {1,src, des} o Push stack: {n-1,src, temp} 6/8/2010 Nguyễn Thị Thúy Loan 133 6/8/2010 Nguyễn Thị Thúy Loan 134 QuickSort QuickSort Ý tưởng QuickSort không đệ quy o Đưa vào stack đoạn bên phải . Dùng stack khử đệ quy o Nếu đoạn bên trái nhiều hơn 1 phần . Stack lưu giữ {biên trái, biên phải} của đoạn tử, cập nhật right = i, lập lại với đoạn . Khi phân đến [left, right] ta được left, right mới tương tự. o [left, i] các phần tử nhỏ hơn x o Khi đoạn bên trái hết thì ta sẽ lấy trong o [i+1,j-1] các phần tử bằng x stack ra o [j, right] các phần tử lớn hơn x o Quá trình lặp lại cho đến khi stack rỗng 6/8/2010 Nguyễn Thị Thúy Loan 135 6/8/2010 Nguyễn Thị Thúy Loan 136
  35. QuickSort Queue - Mô tả Bài tập: Cài đặt thuật giải Quicksort không Queue dùng DSLK dùng đệ quy. . Con trỏ first trỏ đầu danh sách . Dùng DSLK, mỗi nút chứa thông tin biên . Con trỏ last trỏ đến cuối danh sách trái và biên phải của đoạn chưa được . Thao tác Remove diễn ra ở first sắp. . Tháo tác Insert diễn ra ở last . Áp dụng ý tưởng của slide trước để cài . Thao tác thêm xóa dễ dàng ở hai đầu. đặt. 6/8/2010 Nguyễn Thị Thúy Loan 137 8/6/20106/8/2010Nguyễn Nguy Thị Thúyễn Th Loanị Thúy – CLoanĐ PTTH II 138 Tổ chức theo mảng 1 chiều Khởi tạo Queue Tạo cấu trúc dữ liệu cho QUEUE #define Max 100 // stack chứa 100 ptử void Init (Queue &Q) { Q.n = 0; typedef struct Queue { Q.f = 0; int n; Data a[Max]; Q.l = 0; int f; } int l; }; 6/8/2010 Nguyễn Thị Thúy Loan 139 6/8/2010 Nguyễn Thị Thúy Loan 140
  36. Kiểm tra rỗng/ đầy Thêm phần tử vào Queue int isEmpty (Queue Q) int EnQ (Queue &Q, Data x) { return Q.n = = 0; { if(isFull(Q)) return 0; } Q.a[Q.l] = x; int isFull (Queue Q) Q.l = (Q.l +1)% MAX; { return Q.n == MAX; Q.n ++; } return 1; } 6/8/2010 Nguyễn Thị Thúy Loan 141 6/8/2010 Nguyễn Thị Thúy Loan 142 Lấy phần tử ra khỏi Queue Tổ chức theo DSLK int DeQ (Queue &Q, Data &x) . Tạo cấu trúc Node cho Queue { if (isEmpty (Q)) typedef struct NodeQ { return 0; Data info; x= Q.a[Q.f]; NodeQ *next; Q.f = (Q.f +1) % MAX; }; typedef struct Queue Q.n ; { return 1; NodeQ *h, *t; } }; 6/8/2010 Nguyễn Thị Thúy Loan 143 6/8/2010 Nguyễn Thị Thúy Loan 144
  37. Giới thiệu Khởi tạo kiểm tra rỗng . FIFO int Init (Queue &Q) . Thêm vào cuối và lấy ra ở đầu { Q.h = Q.t = NULL; } int isEmpty (Queue Q) { return Q.h == NULL; } 6/8/2010 Nguyễn Thị Thúy Loan 145 6/8/2010 Nguyễn Thị Thúy Loan 146 Thêm phần tử vào Queue Thêm phần tử vào Queue int EnQ (Queue &Q, Data x) pFront pRear { NodeQ *p = new NodeQ; new if(!p) return 0; 5 2 9 x p info = x; p next = NULL; pFront pRear if(!Q.h) Q.h = p; else Q.t next = p; new 5 2 9 x Q.t =p; return 1; } 6/8/2010 Nguyễn Thị Thúy Loan 147 6/8/2010 Nguyễn Thị Thúy Loan 148
  38. Lấy phần tử ra khỏi Queue Lấy phần tử ra khỏi Queue int Pop (Queue &Q, Data &x) pFront pRear { if (isEmpty (Q)) return 0; 5 2 9 NodeQ *p = Q.h; x = p info; pFront pRear Q.h = Q.h next; delete p; 2 9 if (Q.h = = NULL) Q.t = NULL; return 1; } 6/8/2010 Nguyễn Thị Thúy Loan 149 6/8/2010 Nguyễn Thị Thúy Loan 150 Ứng dụng Tính giá trị biểu thức . Trong bài toán hàng đợi “Vào trước ra . Giai đoạn 1: Chuyển biểu thức trung tố trước” FIFO: sang hậu tố Trung tố (infix) o Các ứng dụng đặt vé tàu lửa, máy bay Hậu tố (Postfix) (6 / 2 + 3) * (7 - 4) 6 2 / 3 + 7 4 - * o Các hệ thống rút tiền o Tính giá trị biểu thức. Biểu thức hậu tố dễ tính toán hơn trong máy tính 6/8/2010 Nguyễn Thị Thúy Loan 151 6/8/2010 Nguyễn Thị Thúy Loan 152
  39. Tính giá trị biểu thức Tính giá trị biểu thức Chuyển từ trung tố về hậu tố. o Nếu C là toán tử: . Duyệt qua từng phần tử trong infix (C) o Lấy các toán tử có độ ưu tiên cao hơn bỏ o Nếu C là toán hạng thì bỏ vào postfix vào postfix. o Nếu C là “(“ thì push stack. o Bỏ toán tử vào stack. o Nếu C là “)” thì lấy tất cả phần tử trong stack Ví dụ: (6/2 + 3) * (7 – 4) ra bỏ vào postfix cho đến khi gặp “(“. 6/8/2010 Nguyễn Thị Thúy Loan 153 6/8/2010 Nguyễn Thị Thúy Loan 154 Tính giá trị biểu thức Tính giá trị biểu thức (2 * 3 + 8/ 2) * (5 – 1) (2 * 3 + 8/ 2) * (5 – 1) Đọc Xử lý Stack postfix Đọc Xử lý Stack postfix Lấy trong stack ra cho đến khi gặp ( Đẩy vào stack ( ) 2 3 * 8 2 / + ngoặc (. 2 Bỏ vào postfix ( 2 Do ‘*’ ưu tiên hơn ‘(‘ ở đỉnh stack * Đưa vào stack * 2 3 * 8 2 / + * ( * 2 nên đưa ‘*’ vào stack ( Đưa vào stack * ( 2 3 * 8 2 / + 3 Bỏ vào postfix ( * 2 3 5 Bỏ vào postfix * ( 2 3 * 8 2 / + 5 Do ‘+’ ưu tiên thấp hơn ‘*’ ở đỉnh stack nên ta lấy ‘*’ ra. Độ ưu tiên của ‘-‘ cao hơn ‘(‘ trong + ( + 2 3 * - * ( - 2 3 * 8 2 / + 5 Tiếp tục so sánh ‘+’ với ‘(‘ thì ‘+’ ưu đỉnh stack nên đưa ‘-‘ vào stack tiên cao hơn nên đưa vào stack 1 Bỏ vào postfix * ( - 2 3 * 8 2 / + 5 1 8 Bỏ vào postfix ( + 2 3 * 8 Lấy trong stack ra cho đến khi gặp Do ‘/’ có độ ưu tiên cao hơn ‘+’ trên ) * 2 3 * 8 2 / + 5 1 - / ( + / 2 3 * 8 ngoặc đóng đỉnh stack nên đưa ‘/’ vào stack. Lấy những phần tử còn lại trong 2 3 * 8 2 / + 5 1 - * 2 Bỏ vào postfix ( + / 2 3 * 8 2 stack và hiển thị 6/8/2010 Nguyễn Thị Thúy Loan 155 6/8/2010 Nguyễn Thị Thúy Loan 156
  40. Tính giá trị biểu thức Tính giá trị biểu thức Ý tưởng . Giai đoạn 2: Tính giá trị biểu thức postfix . Khởi tạo stack = {Ø} Postfix không cần có dấu ngoặc vẫn có thể tính đúng . Đọc lần lượt các phần tử từ trái, kiểm tra bằng cách đọc lần lượt biểu thức từ trái qua phải và dùng o Nếu toán hạng: Push stack một stack để lưu trữ kết quả trung gian 34*5+ o Nếu toán tử: lấy hai toán hạng, thực hiện phép toán, kết quả Push vào stack . Sau khi đọc xong, trong stack còn duy Jan Lukasiewicz nhất một phần tử kết quả! 6/8/2010 Nguyễn Thị Thúy Loan 157 6/8/2010 Nguyễn Thị Thúy Loan 158 Tính giá trị biểu thức Bài tập (2 * 3 + 8/ 2) * (5 – 1) 2 3 * 8 2 / + 5 1 - * Đọc Xử lý Stack Output 2,3 Đưa vào satck 2, 3 * 2*3 6 8 Đưa vào stack 6, 8 3 * (2 + 6 *2 / 3 – 1) – 2 * 3/ 2 + 1 2 Đưa vào satck 6, 8, 2 /Lấy 8/2 6, 4 + Lấy 6 + 4 10 5 Đưa vào satck 10, 5 1 Đưa vào satck 10, 5, 1 - Lấy 5 -1 10, 4 * Lấy 10 *4 40 40 6/8/2010 Nguyễn Thị Thúy Loan 159 6/8/2010 Nguyễn Thị Thúy Loan 160
  41. Chương V CÂY ThS. Nguyễn Thị Thúy Loan Cấu trúc cây Tham khảo bài giảng ThS. Nguyễn Hà Giang 6/8/2010 Nguyễn Thị Thúy Loan 162 Cấu trúc cây Nội dung . Tập hợp các nút và cạnh nối các nút đó. . Cấu trúc cây . Có một nút gọi là gốc. . Quan hệ one-to-many giữa các nút. . Cây nhị phân . Có duy nhất một đường đi từ gốc đến một . Cây nhị phân tìm kiếm nút. . Các loại cây: o Nhị phân: mỗi nút có {0,1, 2} nút con o Tam phân: mỗi nút có {0,1,2,3} nút con o n-phân: mỗi nút có {0,1, ,n} nút con 6/8/20108/6/2010 Nguyễn Nguy Thị Thúyễn Th Loanị Thúy – CLoanĐ PTTH II 163 6/8/2010 Nguyễn Thị Thúy Loan 164
  42. Khái niệm Khái niệm . Thuật ngữ o Nút gốc: không có nút cha gốc Cạnh J o Nút lá: không có nút con nút o Nút trong: không phải nút lá và nút gốc Z A o Chiều cao: khoảng cách từ gốc đến lá B R D Nút gốc Q K A F L Lá Nút trong Chiều cao Nút lá 6/8/2010 Nguyễn Thị Thúy Loan 165 6/8/2010 Nguyễn Thị Thúy Loan 166 Khái niệm Nội dung Root Node A Node B  Cấu trúc cây.  Cây nhị phân. Node C Node D Node E Node F Node G  Cây nhị phân tìm kiếm. Node H Node I Node J Node K Node L Cây con Nút anh em 6/8/2010 Nguyễn Thị Thúy Loan 167 6/8/2010 Nguyễn Thị Thúy Loan 168
  43. Cây nhị phân Cây nhị phân . Cây nhị phân là một đồ thị có hướng, mỗi . Cây nhị phân có thể rỗng (không có nút nút có tối đa 2 nút con. nào) . Cấu trúc cây đơn giản nhất . Cây NP khác rỗng có 1 nút gốc . Tại mỗi nút gồm các 3 thành phần o Có duy nhất 1 đường đi từ gốc đến 1 nút. o Phần data: chứa giá trị, thông tin o Nút không có nút con bên trái và con bên o Liên kết đến nút con trái (nếu có) phải là nút lá. o Liên kết đến nút con phải (nếu có) 6/8/2010 Nguyễn Thị Thúy Loan 169 6/8/2010 Nguyễn Thị Thúy Loan 170 Cây nhị phân Cây nhị phân Kích thước = 9 (số nút) . Cây nhị phân đúng: Mức 0 A Nút gốc và nút trung gian có đúng 2 con Cây con trái Cây con phải o Mức 1 . Cây nhị phân đúng có n nút lá thì số nút B C trên cây 2* n – 1. A Mức 2 D E F G B C D E F G Mức 3 H I Độ sâu/chiều cao = 3 H I J K 6/8/2010 Nguyễn Thị Thúy Loan 171 6/8/2010 Nguyễn Thị Thúy Loan 172
  44. Cây nhị phân Cấu trúc cây nhị phân . Cây nhị phân đầy đủ với chiều sâu d . Cấu trúc của cây nhị phân. o Phải là cây nhị phân đúng typedef struct Tree Chứa thông tin của nút o Tất cả nút lá có chiều sâu d { Data info; A Tree * left; Cấu trúc của một nút Số nút = (2d+1 -1) Tree *right; Số nút trung gian = ? B C Trỏ đến nút con phải Biết số nút tính d của cây NP đầy đủ }; Trỏ đến nút con trái D E F G 6/8/2010 Nguyễn Thị Thúy Loan 173 6/8/2010 Nguyễn Thị Thúy Loan 174 Sơ đồ cây nhị phân Các thao tác cơ bản pTree . Tạo nút mới. Con trỏ pTree trỏ 8 đến nút gốc của cây . Thêm nút con trái T . Thêm nút con phải T 5 10 . Duyệt cây . Xóa con trái T 1 3 4 20 . Xóa con phải T 9 7 . Xóa cây. 6/8/2010 Nguyễn Thị Thúy Loan 175 6/8/2010 Nguyễn Thị Thúy Loan 176
  45. Duyệt cây Duyệt cây . Do cây là cấu trúc không tuyến tính A PreOrder (NLR) . 3 cách duyệt cây NP B C o Duyệt theo thứ tự trước PreOrder: NLR InOrder (LNR) D E F G o Duyệt theo thứ tự giữa InOrder: LNR PostOrder (LRN) o Duyệt theo thứ tự sau PostOrder: LRN H I J K 6/8/2010 Nguyễn Thị Thúy Loan 177 6/8/2010 Nguyễn Thị Thúy Loan 178 Duyệt Node Left Right Duyệt Left Node Right void NLR(Tree *T) void LNR(Tree *T) { if (T == NULL) return; { if(T == NULL) return; ; LNR(T left); NLR(T left); ; NLR(T right); LNR(T right); } } 6/8/2010 Nguyễn Thị Thúy Loan 179 6/8/2010 Nguyễn Thị Thúy Loan 180
  46. Duyệt Left Right Node Tạo nút mới Tree *CreateNode (int x) void LRN (Tree *T) { { if (T == NULL) return; Tree *p = New Node; T LRN (T left); if(!p) return NULL: LRN (T right); p info = x; new ; p left = NULL; X } p right = NULL; return p; } 6/8/2010 Nguyễn Thị Thúy Loan 181 6/8/2010 Nguyễn Thị Thúy Loan 182 Thêm nút con bên trái T Thêm nút con bên phải T int Them_trai (Tree *T, int x) int Them_phai (Tree *T, int x) { { } } 6/8/2010 Nguyễn Thị Thúy Loan 183 6/8/2010 Nguyễn Thị Thúy Loan 184
  47. Xóa cây Các thao tác mở rộng void Xoa_LRN (Tree *&T) . Đếm số nút lá trên cây. { . Đếm số nút trên cây. . Đếm số nút trong. . Xác định độ sâu/chiều cao của cây. . Tìm giá trị nhỏ nhất/lớn nhất trên cây. . Tính tổng các giá trị trên cây. } . Đếm số nút có giá trị bằng x. 6/8/2010 Nguyễn Thị Thúy Loan 185 6/8/2010 Nguyễn Thị Thúy Loan 186 Nội dung Khái niệm . BST là cây nhị phân mà mỗi nút thoả . Cấu trúc cây o Giá trị của tất cả nút con trái nút gốc . Cây nhị phân . Cây nhị phân tìm kiếm (BST– Binary 5 Search Tree) 5 3 10 1 4 8 20 6/8/2010 Nguyễn Thị Thúy Loan 187 6/8/2010 Nguyễn Thị Thúy Loan 188
  48. Cấu trúc dữ liệu Cây nhị phân tìm kiếm typedef struct Tree . Xây dựng cây BST { Data info; o Tìm kiếm/ thêm Tree *left; o Xóa Tree *right; . Luôn duy trì tính chất } ; o Giá trị nhỏ hơn ở bên cây con trái o Giá trị lớn hơn ở bên cây con phải 6/8/2010 Nguyễn Thị Thúy Loan 189 6/8/2010 Nguyễn Thị Thúy Loan 190 Tìm kiếm Ví dụ . Xuất phát từ gốc 5 10 o Nếu gốc = NULL => không tìm thấy 10 2 45 o Nếu khóa x = khóa nút gốc => tìm thấy 5 45 5 30 30 o Ngược lại nếu khóa x 2 25 30 Tìm trên cây bên trái 2 25 45 10 o Ngược lại => tìm trên cây bên phải 25 Binary Non-binary search trees search tree 6/8/2010 Nguyễn Thị Thúy Loan 191 6/8/2010 Nguyễn Thị Thúy Loan 192
  49. Ví dụ tìm x= 9 Duyệt cây x = 9 10 10>9, left 5 y, thêm nút lá x mới } bên phải của y 20 x 6/8/2010 Nguyễn Thị Thúy Loan 195 6/8/2010 Nguyễn Thị Thúy Loan 196
  50. Xóa phần tử khỏi cây Ví dụ xóa x = 25 Xóa nhưng phải đảm bảo vẫn là cây BST . Trường hợp 1: nút p là nút lá, xóa bình . Thực hiện tìm nút có giá trị x. thường . Nếu nút là nút lá, xóa nút. 10 10 . Ngược lại Xóa 25 o Thay thế nút bằng một trong hai nút sau. 5 30 5 30 o Y là nút lớn nhất của cây con bên trái o Z là nút nhỏ nhất của cây con bên phải 2 25 45 2 45 o Chọn nút Y hoặc Z để thế chỗ. o Giải phóng nút có giá trị x. 6/8/2010 Nguyễn Thị Thúy Loan 197 6/8/2010 Nguyễn Thị Thúy Loan 198 Ví dụ xóa x = 5 Ví dụ . Trường hợp 3: nút p có 2 cây con, chọn . Trường hợp 2: p chỉ có 1 cây con, cho nút nút thay thế theo 1 trong 2 cách như sau: cha của p trỏ tới nút con duy nhất của nó, o Nút lớn nhất trong cây con bên trái rồi hủy p o Nút nhỏ nhất trong cây con bên phải 10 10 Xóa 5 5 30 30 22545 22545 Nút lớn Nút nhỏ bên trái bên phải 6/8/2010 Nguyễn Thị Thúy Loan 199 6/8/2010 Nguyễn Thị Thúy Loan 200
  51. Ví dụ Ví dụ . Xóa nút 10: cách 1 . Xóa nút 10: cách 2 50 50 50 50 10 55 5 55 10 55 25 55 5 30 Xóa 10 30 Xóa 10 5 30 5 30 22545 22545 22545 2 45 Chọn nút có khóa lớn nhất bên trái Chọn nút nhỏ nhất bên phải 6/8/2010 Nguyễn Thị Thúy Loan 201 6/8/2010 Nguyễn Thị Thúy Loan 202 Ví dụ xóa x = 25 Ví dụ xóa x = 25 52 52 P P 25 66 25 f 66 15 39 60 99 15 39 60 99 9 19 27 42 58 62 9 19 27 42 58 62 31 rp 31 6/8/2010 Nguyễn Thị Thúy Loan 203 6/8/2010 Nguyễn Thị Thúy Loan 204
  52. Ví dụ xóa x = 25 Ví dụ xóa x = 25 52 P 52 P mới 27 f 66 mới 27 f 66 15 39 60 99 15 39 60 99 9 19 27 42 58 62 27 9 19 25 42 58 62 rp 31 31 6/8/2010 Nguyễn Thị Thúy Loan 205 6/8/2010 Nguyễn Thị Thúy Loan 206 Ví dụ xóa x = 25 Ví dụ xóa x = 25 f Trường hợp đặc biệt: 52 52 P f == p P Nút thế mạng rp là nút con phải của nút p cần 25 rp mới xóa 27 f 66 15 39 15 39 60 99 9 19 42 9 19 31 42 58 62 6/8/2010 Nguyễn Thị Thúy Loan 207 6/8/2010 Nguyễn Thị Thúy Loan 208
  53. Ví dụ xóa x = 25 Ví dụ xóa x = 25 f Trường hợp đặc biệt: f Trường hợp đặc biệt: 52 52 P f == p P f == p Nút thế mạng rp là nút Nút thế mạng rp là nút con phải của nút p cần con phải của nút p cần 39 rp 39 rp xóa xóa - Đưa giá trị của nút rp - Chuyển liên kết phải 15 39 lên nút p 15 39 của p đến liên kết phải của rp 9 19 42 9 19 42 6/8/2010 Nguyễn Thị Thúy Loan 209 6/8/2010 Nguyễn Thị Thúy Loan 210 Ví dụ xóa x = 25 Ví dụ xóa x = 25 f Trường hợp đặc biệt: f Trường hợp đặc biệt: 52 52 P f == p P f == p Nút thế mạng rp là nút Nút thế mạng rp là nút con phải của nút p cần con phải của nút p cần 39 rp 39 xóa xóa - xóa nút rp - Sau khi xóa 15 39 15 42 9 19 42 9 19 6/8/2010 Nguyễn Thị Thúy Loan 211 6/8/2010 Nguyễn Thị Thúy Loan 212
  54. Giải thuật Giải thuật Ngược lại có 2 con Gọi f = p và rp = p right; Nếu T = NULL thoát Tìm nút rp: rp left = null và nút f là nút cha Nếu T info > x Xoa (T left, x) nút rp Nếu T info <x Xoa (T right, x) Thay đổi giá trị nội dung của T và rp Nếu T info = x Nếu f = p (trường hợp đặc biệt) thì: p = T f right = rp right; Ngược lại: f left = rp right; Nếu T có 1 nút con thì T trỏ đến nút con đó p = rp; // p trỏ tới rp để xóa 6/8/2010 Nguyễn Thị Thúy Loan 213 Xóa p Cài đặt Bài tập int Xoa_x (Tree *&T, int x) { 1. Tìm phần tử max âm trên cây. 2. Đếm có bao nhiêu phần tử chẵn trên cây. } 6/8/2010 Nguyễn Thị Thúy Loan 215 6/8/2010 Nguyễn Thị Thúy Loan 216