intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Thực hành Cấu trúc dữ liệu và giải thuật 1

Chia sẻ: Nguyen Minh Phung | Ngày: | Loại File: PDF | Số trang:33

Thêm vào BST
Báo xấu
403
lượt xem 146
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cùng với học phần “Cấu trúc dữ liệu và giải thuật 1”, học phần “Thực hành Cấu trúc dữ liệu và giải thuật 1” nhằm cung cấp cho sinh viên các kiến thức căn bản và kỹ năng thực hành trên các cấu trúc dữ liệu cơ sở có cấu trúc tĩnh và động (thông qua danh sách liên kết và cây, chủ yếu là cây nhị phân) cũng như các thuật toán cơ bản liên quan đến chúng như sắp xếp, tìm kiếm ở bộ nhớ trong. Để có thể nắm bắt các kiến thức được trình bày trong...

Chủ đề:

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

Lưu

Nội dung Text: Thực hành Cấu trúc dữ liệu và giải thuật 1

  1. TRÖÔØNG ÑAÏI HOÏC ÑAØ LAÏT KHOA TOAÙN - TIN HOÏC TAÏ THÒ THU PHÖÔÏNG THÖÏC HAØNH CAÁU TRUÙC VAØ GIAÛI THUAÄT 1 (Baøi Giaûng Toùm Taét) -- Löu haønh noäi boä -- Ñaø Laït 2008
  2. LỜI MỞ ĐẦU Cùng với học phần “Cấu trúc dữ liệu và giải thuật 1”, học phần “Thực hành Cấu trúc dữ liệu và giải thuật 1” nhằm cung cấp cho sinh viên các kiến thức căn bản và kỹ năng thực hành trên các cấu trúc dữ liệu cơ sở có cấu trúc tĩnh và động (thông qua danh sách liên kết và cây, chủ yếu là cây nhị phân) cũng như các thuật toán cơ bản liên quan đến chúng như sắp xếp, tìm kiếm ở bộ nhớ trong. Để có thể nắm bắt các kiến thức được trình bày trong giáo trình này, sinh viên cần có các kiến thức về tin học đại cương và nhập môn lập trình. Các kiến thức trong học phần này sẽ tạo điều kiện cho học viên tiếp tục dễ dàng nắm bắt các kiến thức các học phần tin học về sau như: cấu trúc dữ liệu và giải thuật 2, toán rời rạc, đồ hoạ, hệ điều hành, trí tuệ nhân tạo, ... Nội dung giáo trình được trình bày thông qua 10 bài thực tập. Mỗi bài thực tập đều có phần hệ thống lại nội dung lý thuyết và phần bài tập thực hành cũng như bài tập nâng cao. Chắn chắn rằng trong giáo trình sẽ còn nhiều khiếm khuyết, tác giả mong muốn nhận được và rất biết ơn các ý kiến đóng góp quí báu của đồng nghiệp cũng như bạn đọc để giáo trình được hoàn thiện hơn nữa về mặt nội dung cũng như hình thức trong lần tái bản sau. Đà lạt, 5/2008 Tác giả
  3. MỤC LỤC Chương 1: Giới thiệu cấu trúc dữ liệu và thuật toán ................................. Trang 1 Bài thực hành số 1: Kiểu dữ liệu có cấu trúc ...................................................... 1 Chương2: Tìm kiếm và sắp xếp ............................................................................... 7 Bài thực hành số 2: Các phương pháp tìm kiếm ................................................. 7 Bài thực hành số 3: Các phương pháp sắp xếp ................................................. 10 Bài thực hành số 4: Các phương pháp sắp xếp (tt) ........................................... 14 Bài thực hành số 5: Áp dụng các phương pháp sắp xếp và tìm kiếm ............... 18 Chương 3: Cấu trúc danh sách liên kết ................................................................. 19 Bài thực hành số 6: Danh sách liên kết đơn ...................................................... 19 Bài thực hành số 7: Áp dụng danh sách liên kết ............................................... 21 Bài thực hành số 8: Các thao tác trên Stack - Queue ....................................... 23 Chương 3: Cấu trúc cây .......................................................................................... 27 Bài thực hành số 9: Cây nhị phân, Cây nhị phân tìm kiếm............................... 27 Bài thực hành số 10: Các thao tác trên cây nhị phân tìm kiếm cân bằng ......... 29 Các bài kiểm tra: ..................................................................................................... 30 TÀI LIỆU THAM KHẢO
  4. Thực hành Cấu trúc dữ liệu và Giải thuật 1 1 Chương 1: GIỚI THIỆU CẤU TRÚC DỮ LIỆU – PHÂN TÍCH THUẬT TOÁN BÀI THỰC HÀNH SỐ 1 (4 tiết) Mục tiêu Thống nhất một số chuẩn và quy ước trong lập trình. Nắm kiểu dữ liệu có cấu trúc và các thao tác trên chúng. Nội dung − Ôn lại kiểu dữ liệu có cấu trúc (kiểu định nghĩa bằng từ khóa struct) − Các quy ước lập trình. Yêu cầu Nắm vững phương pháp lập trình cấu trúc trong C/C++ và biết cách sử dụng môi trường lập trình Visual C++ 6.0. 1. CÁC QUY ƯỚC LẬP TRÌNH Quy ước đặt tên hằng Trong Visual C++ 6.0, hằng số được khai báo bằng từ khóa “#define”. Một số quy ước trong việc đặt tên hằng như sau: i) Tên hằng phải thể hiện được ý nghĩa của nó. ii) Tên hằng được viết hoa toàn bộ và các từ trong tên cách nhau bằng ký tự “_”. Quy ước đặt tên biến i) Tên biến phải thể hiện được ý nghĩa của nó. int t, m; // Không rõ nghĩa. int iTuSo, iMauSo; // Rõ nghĩa. ii) Tên biến được viết hoa các ký tự đầu mỗi từ trong tên, các ký tự còn lại viết thường. int ituso, imauso; // Không nên
  5. Thực hành Cấu trúc dữ liệu và Giải thuật 1 2 int iTuso, iMauso; // Không nên int iTuSo, iMauSo; // nên iii) Tên biến có phần tiếp đầu ngữ (prefix) thể hiện kiểu dữ liệu của biến (phong cách Hungarian): Kiểu dữ liệu số char – c char cKyTu; short – s short sSoNguyenNgan; int – i int iSoNguyen; long – l long lSoNguyenDai; float – f float fSoThuc; double – d double dSoThucDai; int nSo; Kiểu dữ liệu luận lý bool - b bool bLuanLy; Kiểu dữ liệu mảng [] – arr int arrSoNguyen[50]; HocSinh arrDanhSach[50]; Kiểu dữ liệu chuỗi char *, char [] – str char *strChuoi; char strChuoi[50]; Kiểu dữ liệu con trỏ *-p int *pConTro; HocSinh *pDanhSach; Quy ước đặt tên kiểu dữ liệu tự định nghĩa i) Tên kiểu dữ liệu tự định nghĩa (struct) thường là danh từ và phải thể hiện được ý nghĩa của kiểu dữ liệu đó. struct TinhPhanSo // không nên struct PhanSo // nên ii) Tên kiểu dữ liệu tự định nghĩa được viết hoa các ký tự đầu mỗi từ trong tên, các
  6. Thực hành Cấu trúc dữ liệu và Giải thuật 1 3 ký tự còn lại viết thường. Ví dụ struct PhanSo Quy ước đặt tên hàm i) Tên hàm thường là động từ và phải thể hiện hành động cần thực hiện. int DataFile(char *strFileName) // không nên int LoadDataFile(char *strFileName) // nên. int BadValue(long lValue) // không nên int CheckForBadValue(long lValue) // nên ii) Tên hàm được viết hoa các ký tự đầu mỗi từ trong tên, các ký tự còn lại viết thường. int checkforbadvalue(long lValue) // không nên int CheckforBadvalue(long lValue) // không nên int CheckForBadValue(long lValue) // Nên. Quy ước viết câu lệnh i) Viết mỗi câu lệnh riêng trên một dòng. // Không nên. x = 3; y = 5; // nên viết x = 3; y = 5; ii) Viết các dấu “{” “}” riêng trên một dòng. void Swap(int &a, int &b) { int c = a; a = b; b = c; } iii) Viết các câu lệnh if, while, for riêng trên một đoạn. if (a > b) printf( "a lon hon b");
  7. Thực hành Cấu trúc dữ liệu và Giải thuật 1 4 for (int i = 0; i < n; i++) x = x + 5; k = k * x; iv) Viết các câu lệnh cùng thực hiện một công việc riêng trên một đoạn. int c = a; a = b; b = c; k = k * a; x = b + c; Quy ước cách khoảng i) Viết cách vào một khoảng tab đối với các câu lệnh nằm giữa dấu “{“ “}”. // không nên // nên viết void Swap(int &a, int &b) void Swap(int &a, int &b) { { int c = a; int c = a; a = b; a = b; b = c; b = c; } } ii) Viết cách vào một khoảng tab đối với câu lệnh ngay sau if, else, while, for. // Không nên. // nên viết if (a > b) if (a > b) printf( "a lon hon b"); printf( "a lon hon b"); else else printf("a nho hon hoac bang b"); printf("a nho hon hoac bang b"); for (int i = 0; i < n; i++) x = x + 5; for (int i = 0; i < n; i++) x = x + 5; iii) Viết cách một khoảng trắng xung quanh các toán tử 2 ngôi. x=x+5*a-c; // Không nên x = x + 5 * a - c; // nên
  8. Thực hành Cấu trúc dữ liệu và Giải thuật 1 5 if (a>=b) // Không nên if (a >= b) // nên iv) Viết cách một khoảng trắng sau các dấu “,” “;”. void CalculateValues(int a,int b,int c); // không nên void CalculateValues(int a, int b, int c); // nên for (int i = 0;i < n;i++) // không nên for (int i = 0; i < n; i++) // nên Quy ước viết chú thích Trong C++, chúng ta dùng dấu “//” hoặc “/*” “*/” để viết chú thích cho chương trình. Một số quy ước khi viết chú thích như sau: i) Chú thích phải rõ ràng, dễ hiểu và diễn giải được ý nghĩa của đoạn lệnh, hàm... ii) Dùng dấu “//” thay cho “/*” “*/” khi viết chú thích. /* void Swap(int &a, int &b) // nên dùng { //void Swap(int &a, int &b) int c = a; //{ a = b; // int c = a; b = c; // a = b; } */ // b = c; //} 2. BÀI TẬP Giả sử quy tắc tổ chức quản lý nhân viên của một công ty như sau: • Thông tin về một nhân viên bao gồm lý lịch và bảng chấm công: * Lý lịch nhân viên: - Mã nhân viên : chuỗi 10 ký tự - Tên nhân viên : chuỗi 30 ký tự - Tình trạng gia đình : 1 ký tự (M = Married, S = Single) : số nguyên ≤ 20 - Số con - Trình độ văn hoá : chuỗi 2 ký tự (C1 = cấp 1, C2 = cấp 2, C3=cấp 3; DH = đại học, CH = cao học, TS = tiến sĩ) : số ≤ 1 000 000 - Lương căn bản * Chấm công nhân viên:
  9. Thực hành Cấu trúc dữ liệu và Giải thuật 1 6 − : số ≤ 28 Số ngày nghỉ có phép trong tháng − : số ≤ 28 Số ngày nghỉ không phép trong tháng − : số ≤ 28 Số ngày làm thêm trong tháng − Kết quả công việc : chuỗi 2 ký tự (T = tốt, TB = trung bình, K = Kém) − Lương thực lĩnh trong tháng : số ≤ 2 000 000 • Quy tắc tính lương: Lương thực lĩnh = Lương căn bản + Phụ trội Trong đó nếu: − số con > 2 : Phụ trội = +5% Lương căn bản − trình độ văn hoá = CH : Phụ trội = +10% Lương căn bản − làm thêm : Phụ trội = +4% Lương căn bản / 1 ngày − nghỉ không phép : Phụ trội = -5% Lương căn bản / 1 ngày • Các chức năng yêu cầu: − Cập nhật lý lịch, bảng chấm công cho nhân viên (thêm, xóa, sửa một hay mọi mẫu tin thoả mãn một tính chất nào đó) − Xem bảng lương hàng tháng − Khai thác (chẳng hạn tìm) thông tin của nhân viên Hãy chọn cấu trúc dữ liệu thích hợp (và giải thích tại sao?) để biểu diễn các thông tin trên và cài đặt chương trình theo các chức năng đã mô tả. Biết rằng số nhân viên tối đa là 50 người, chú ý các thông tin tĩnh và “động” hay thay đổi và là hệ quả của những thông tin khác.
  10. Thực hành Cấu trúc dữ liệu và Giải thuật 1 7 Chương 2: TÌM KIẾM VÀ SẮP XẾP BÀI THỰC HÀNH SỐ 2 Các phương pháp tìm kiếm (4 tiết) Mục tiêu Cài đặt các phương pháp tìm kiếm, so sánh các phương pháp. Nội dung lý thuyết 0. PHÁT BIỂU BÀI TOÁN Cho dãy a gồm N phần tử, cần tìm x trong dãy a. 1. CÁC PHƯƠNG PHÁP TÌM KIẾM a) Phương pháp tìm kiếm tuyến tính Ý tưởng So sánh x lần lượt với phần tử thứ 1, thứ 2,…của dãy a cho đến khi gặp phần tử có khóa cần tìm, hoặc đã tìm hết dãy mà không thấy x. Giải thuật Bước 1: i = 1; // bắt đầu từ phần tử đầu tiên của dãy Bước 2: So sánh a[i] với x. + Nếu a[i] = x: Tìm thấy. Dừng. + Nếu a[i] ≠ x: Sang Bước 3. Bước 3: i = i + 1; // xét tiếp phần tử kế trong dãy Nếu i ≤ N : lặp lại Bước 2. Ngược lại: Hết dãy. Không tìm thấy. Dừng b) Phương pháp tìm kiếm tuyến tính có lính canh Ý tưởng − Đặt một phần tử có giá trị x vào cuối dãy, gọi đây là phần tử “lính canh”. Như vậy, ta bảo đảm luôn tìm thấy x trong dãy, và dựa vào vị trí tìm thấy để đưa ra kết luận. − Phương pháp cải tiến này giúp giảm bớt một phép so sánh trong vòng lặp.
  11. Thực hành Cấu trúc dữ liệu và Giải thuật 1 8 Giải thuật Bước 1: i = 1; a[N+1] = x; // phần tử “lính canh” Bước 2: So sánh a[i] với x. + Nếu a[i] = x: Sang Bước 3 + Nếu a[i] ≠ x: i = i + 1; Lặp lại bước 2. Bước 3: Nếu i ≤ N : tìm thấy x tại vị trí i. Ngược lại: không tìm thấy x trong dãy. c) Phương pháp tìm kiếm nhị phân Ý tưởng Đối với những dãy số đã có thứ tự (tăng dần), các phần tử đã có quan hệ ai-1 ≤ ai ≤ ai+1. Nếu x > ai thì x chỉ có thể xuất hiện trong đoạn [ai+1, aN], ngược lại nếu x < ai thì x chỉ có thể xuất hiện trong đoạn [a1, ai-1]. Giải thuật áp dụng nhận xét trên để giới hạn phạm vi tìm kiếm sau mỗi lần so sánh x với một phần tử trong dãy. Tại mỗi bước, so sánh x với phần tử nằm giữa dãy tìm kiếm hiện hành, dựa vào kết quả so sánh để quyết định giới hạn của dãy tìm kiếm ở bước kế tiếp là nửa trên hay nửa dưới của dãy hiện hành. Giải thuật Bước 1: left = 1; right = N; // tìm kiếm trên tất cả các phần tử Bước 2: mid = (left + right)/2; // lấy mốc so sánh So sánh a[mid] với x + a[mid] = x: Tìm thấy. Dừng. + a[mid] > x: Tìm tiếp x trong dãy con aleft..amid-1 right = mid – 1; + a[mid] < x: Tìm tiếp x trong dãy con amid+1..aright left = mid + 1; Bước 3: Nếu left ≤ right Lặp lại bước 2. // còn phần tử chưa xét Ngược lại: Không tìm thấy x trong dãy. Dừng
  12. Thực hành Cấu trúc dữ liệu và Giải thuật 1 9 2. BÀI TẬP 1. Cài đặt các thuật toán tìm kiếm 2. Xây dựng và cài đặt thuật toán tìm: a) Phần tử lớn nhất (hay nhỏ nhất). b) Tất cả các số nguyên tố. c) Tìm phần tử đầu tiên trên dãy mà thỏa một tính chất TC nào đó. d) Dãy con (là một dãy các phần tử liên tiếp của dãy) tăng dài nhất trong một dãy các phần tử cho trước được cài đặt bằng mảng. Yêu cầu − Nắm vững nội dung lý thuyết và các bài thực tập đã tiến hành. − Kỹ thuật lập trình module.
  13. Thực hành Cấu trúc dữ liệu và Giải thuật 1 10 BÀI THỰC HÀNH SỐ 3 Các phương pháp sắp xếp (4 tiết) Mục tiêu Cài đặt và sử dụng các phương pháp sắp xếp: sắp xếp chọn, sắp xếp chèn, sắp xếp đổi chỗ. Nội dung lý thuyết 0. PHÁT BIỂU BÀI TOÁN SẮP XẾP Xét một dãy a gồm N phần tử. Cần sắp xếp các phần tử của dãy để thu được một dãy có thứ tự (ví dụ tăng dần/giảm dần theo một khóa được chỉ định). Các thuật toán sắp xếp được trình bày sau đây giả sử dãy a là một dãy số nguyên. 1. PHƯƠNG PHÁP SẮP XẾP CHỌN Ý tưởng: − Chọn phần tử nhỏ nhất x trong N phần tử ban đầu, đảo vị trí của x với phần tử đầu dãy để đưa x về đầu dãy. − Ta không quan tâm đến phần tử đầu dãy nữa, xem dãy bây giờ chỉ còn N-1 phần tử, bắt đầu từ vị trí thứ 2. − Lặp lại xử lí trên cho đến khi dãy hiện hành chỉ còn một phần tử. Giải thuật: Bước 1: i = 1 Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy a[i..N]. Bước 3: Hoán vị a[min] và a[i] Bước 4: Nếu i ≤ N – 1 thì i = i + 1. Lặp lại Bước 2 Ngược lại: Dừng. // N-1 phần tử đã nằm đúng vị trí. 2. PHƯƠNG PHÁP SẮP XẾP CHÈN a) Sắp xếp chèn đơn giản (Insertion Sort) Ý tưởng Xét dãy a1, a2…., an, trong đó i-1 phần tử đầu tiên a1, a2,…,an đã có thứ tự. Tìm vị
  14. Thực hành Cấu trúc dữ liệu và Giải thuật 1 11 trí thích hợp để chèn phần tử ai vào vị trí thích hợp trong i-1 phần tử đã sắp để có dãy mới a1, a2,…,ai trở nên có thứ tự. Vị trí này nằm giữa ak-1 và ak thỏa ak-1 ≤ ai < ak (1 ≤ k < i). Giải thuật Bước 1: i = 2 // Giả sử có đoạn a[1] đã được sắp Bước 2: x = a[i]; Tìm vị trí pos thích hợp trong đoạn a[1] đến a[i-1] để chèn a[i] vào. Bước 3: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chỗ cho a[i]. Bước 4: a[pos] = x; // có đoạn a[1]..a[i] đã được sắp Bước 5: i = i +1; Nếu i ≤ n : lặp lại bước 2. Ngược lại: Dừng b) Sắp xếp chèn cải tiến (Shell Sort) Ý tưởng − Shell Sort là phương pháp cải tiến của Insertion Sort. − Phân chia dãy ban đầu thành những dãy con gồm các phần tử cách nhau h vị trí. Dãy con thứ nhất: a1, ah+1, a2h+1… Dãy con thứ hai: a2, ah+2, a2h+2… …….. Dãy con thứ h: ah, a2h, a3h… − Sắp xếp các phần tử trong cùng dãy con sẽ làm cho các phần tử được đưa về vị trí đúng tương đối (so với toàn bộ các phần tử trong dãy ban đầu có thể chưa đúng). Giảm khoảng cách h để tạo các dãy con mới và lại tiếp tục sắp xếp. − Thuật toán dừng khi h = 1, lúc này bảo đảm tất cả các phần tử trong dãy ban đầu đã được so sánh với nhau để xác định trật tự đúng cuối cùng. Giải thuật Bước 1: Chọn k khoảng cách h[1], h[2],…, h[k]; i = 1; Bước 2: Phân chia dãy ban đầu thành các dãy con cách nhau h[i] khoảng cách. Sắp xếp từng dãy con bằng Insertion Sort. Bước 3: i = i + 1; Nếu i ≤ k : Lặp lại bước 2 Nếu i > k: Dừng
  15. Thực hành Cấu trúc dữ liệu và Giải thuật 1 12 3. PHƯƠNG PHÁP SẮP XẾP ĐỔI CHỖ a) Sắp xếp đổi chỗ đơn giản (Bubble Sort) Ý tưởng − Xét dãy gồm N phần tử − 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í đầu dãy hiện hành. − Ta không quan tâm đến phần tử đầu dãy nữa, xem dãy bây giờ chỉ còn N-1 phần tử, bắt đầu từ vị trí thứ 2. − Lặp lại xử lí trên cho đến khi không còn cặp phần tử nào để xét. Giải thuật Bước 1: i = 1; Bước 2: j = N; // Duyệt từ cuối dãy ngược về vị trí i Trong khi j > i thực hiện Nếu a[j] < a[j-1]: hoán vị a[j] và a[j-1]; // xét cặp phần tử kế cận j = j - 1; Bước 3: i = i + 1 Nếu i ≤ N – 1 : Lặp lại bước 2. Ngược lại: Hết dãy. Dừng. b) Sắp xếp đổi chỗ cải tiến (Shaker Sort) Ý tưởng − Shaker Sort cũng dựa trên nguyên tắc đổi chỗ trực tiếp nhưng tìm các khắc phục nhược điểm của Bubble Sort. Trong mỗi lần sắp xếp, duyệt mảng theo 2 lượt từ 2 phía khác nhau. ο Lượt đi: đẩy phần tử nhỏ về đầu mảng ο Lượt về: đẩy phần tử lớn về cuối mảng − Ghi nhận lại những đoạn đã sắp xếp nhằm tiết kiệm các phép so sánh thừa. Giải thuật Bước 1: l = 1; r = n; // từ l đến r là đoạn cần sắp xếp k = n; // ghi nhận vị trí k xảy ra hoán vị sau cùng // để làm cơ sở thu hẹp đoạn l đến r.
  16. Thực hành Cấu trúc dữ liệu và Giải thuật 1 13 Bước 2: Bước 2a: j = r; // đẩy phần tử nhỏ về đầu mảng Trong khi (j > l) thực hiện Nếu a[j] < a[j-1]: hoán vị a[j] và a[j-1]; k = j; // lưu lại nơi xảy ra hoán vị. j = j – 1; l = k; // loại các phần tử đã có thứ tự ở đầu dãy Bước 2b: j = l; // đẩy phần tử lớn về cuối mảng Trong khi (j < r) thực hiện Nếu a[j] > a[j-1]: hoán vị a[j] và a[j+1]; k = j; // lưu lại nơi xảy ra hoán vị. j = j + 1; r = k; // loại các phần tử đã có thứ tự ở cuối dãy Bước 3: Nếu l < r : Lặp lại bước 2. Ngược lại: Dừng. BÀI TẬP 1. Cài đặt các phương pháp sắp xếp trên. 2. Tổ chức hàm main theo dạng menu cho phép người dùng lựa chọn phương pháp sắp xếp cần áp dụng.
  17. Thực hành Cấu trúc dữ liệu và Giải thuật 1 14 BÀI THỰC HÀNH SỐ 4 Các phương pháp sắp xếp (tt) (4 tiết) Mục tiêu Cài đặt và sử dụng các phương pháp sắp xếp: phân hoạch, trên cây có thứ tự, trộn, dựa trên cơ số. Nội dung lý thuyết 1. QUICK SORT Ý tưởng Chọn x là giá trị của một phần tử tùy ý trong dãy ban đầu. Vị trí phần tử thường được chọn là k = (l + r)/2. Thực hiện phân hoạch với x: ak < x ak = x ak > x k = 1..i k = i..j k = j..N Dãy ban đầu được chia làm 3 phần, trong đó dãy con thứ 2 đã có thứ tự. Dãy ban đầu chỉ có thứ tự nếu dãy con 1 và 3 cũng có thứ tự. Nếu dãy con 1 và 3 chỉ có một phần tử thì chúng đã có thứ tự, ngược lại, ta lần lượt tiến hành phân hoạch từng dãy con theo phương pháp phân hoạch như trên. Giải thuật phân hoạch Bước 1: Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc, l ≤ k ≤ r Bước 2: Phát hiện và hiệu chỉnh cặp phần tử a[i], a[j] nằm sai chỗ: Bước 2a: Trong khi (a[i] < x) i++; Bước 2b: Trong khi (a[j] > x) j--; Bước 2c: Nếu i < j // a[i] ≥ x ≥ a[j] mà a[j] đứng sau a[i] Hoán vị a[i] và a[j]; i ++; j--; Bước 3: Nếu i ≤ j: Lặp lại bước 2. // chưa xét hết mảng Nếu i > j: Dừng
  18. Thực hành Cấu trúc dữ liệu và Giải thuật 1 15 Giải thuật Quick Sort Có thể phát biểu giải thuật sắp xếp Quick Sort một cách đệ qui như sau: Bước 1: Phân hoạch dãy a1…ar thành các dãy con Dãy con 1: a1..aj ≤ x Dãy con 1: aj+1..ai-1 = x Dãy con 1: ai..ar ≥ x Bước 2: Nếu (l < j) // dãy con 1 có nhiều hơn một phần tử Phân hoạch dãy a1..aj Nếu (i < r) // dãy con 3 có nhiều hơn một phần tử Phân hoạch dãy ai..ar 2. HEAP SORT Ý tưởng − Xét dãy gồm N phần tử − Hiệu chỉnh dãy thành heap. Đảo vị trí của phần tử đầu dãy với phần tử cuối dãy để đưa phần tử lớn nhất về cuối dãy. − Ta không quan tâm đến phần tử cuối dãy nữa, xem như dãy hiện hành chỉ gồm N-1 phần tử, tính từ 1. − Lặp lại xử lí trên cho đến khi dãy hiện hành chỉ còn một phần tử. Giải thuật Giai đoạn 1: Hiệu chỉnh dãy số ban đầu thành Heap Giai đoạn 2: Sắp xếp dãy số dựa trên Heap Bước 1: Đưa phần tử lớn nhất về vị trí đúng ở cuối dãy: r = n; Hoán vị (a1, ar); Bước 2: Loại bỏ phần tử lớn nhất ra khỏi heap: r = r – 1; Hiệu chỉnh phần còn lại của dãy a1, a2,…, ar thành một Heap. Bước 3: Nếu r > 1 (heap còn phần tử): Lặp lại bước 2 Ngược lại: Dừng. Dựa trên tính chất 3 của Heap, ta có thể thực hiện giai đoạn 1 bằng cách bắt đầu từ heap mặc nhiên an/2+1, an/2+2, …., an, lần lượt thêm vào các phần tử an/2, an/2-1, …., a1 ta sẽ nhận được heap theo mong muốn.
  19. Thực hành Cấu trúc dữ liệu và Giải thuật 1 16 3. MERGE SORT Ý tưởng − Gọi k là chiều dài của một dãy con − Phân chia dãy ban đầu thành các dãy con có độ dài k, các dãy con này được phân phối luân phiên vào 2 dãy phụ. − Trộn từng cặp dãy con của 2 dãy phụ thành một dãy con của dãy ban đầu, cuối cùng ta sẽ thu được dãy ban đầu có số lượng dãy con giảm phân nửa. − Tăng độ dài k, lặp lại qui trình trên sau một số bước ta sẽ thu được dãy chỉ gồm 1 dãy con, tức là dãy ban đầu đã được sắp xếp. Giải thuật Bước 1: k = 1; // k là chiều dài của dãy con trong bước hiện hành Bước 2: Tách dãy a1, a2,…, an thành 2 dãy b, c theo nguyên tắc luân phiên từng nhóm k phần tử: b = a1,…, ak, a2k+1, …,a3k,… c = ak+1,…, a2k+1, a3k+1, …,a4k,… Bước 3: Trộn từng cặp dãy con gồm k phần tử của 2 dãy b, c vào a. Bước 4: k = k*2; Nếu k < n : Lặp lại bước 2. Ngược lại: Dừng. 4. RADIX SORT Ý tưởng Radix Sort dựa trên nguyên tắc phân loại thư của bưu điện. Nó không quan tâm đến việc so sánh giá trị của phần tử và bản thân việc phân loại và trình tự phân loại sẽ tạo ra thứ tự cho các phần tử. Giải thuật thực hiện như sau: − Trước tiên, ta giả sử mỗi phần tử ai trong dãy a1, a2, …., an là một số nguyên có tối đa m chữ số.
  20. Thực hành Cấu trúc dữ liệu và Giải thuật 1 17 − Phân loại các phần tử lần lượt theo các chữ số hàng đơn vị, hàng chục, hàng trăm… Giải thuật Bước 1: // k cho biết chữ số dùng để phân loại hiện hành. k = 0; // k = 0: hàng đơn vị; k = 1: hàng chục;… Bước 2: // Tạo các lô chứa các loại phần tử khác nhau. Khởi tạo 10 lô B0, B1,…, B9 rỗng; Bước 3: For i = 1..n do Đặt ai vào lô Bt với t = chữ số thứ k của ai ; Bước 3: Nối B0, B1,…, B9 lại theo đúng trình tự thành a. Bước 4: k = k + 1. Nếu k < m: lặp lại bước 2. Ngược lại: Dừng BÀI TẬP 1. Cài đặt các phương pháp sắp xếp trên 2. Tổ chức hàm main theo dạng menu cho phép người dùng lựa chọn phương pháp sắp xếp cần áp dụng.
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
28=>1