Đồ án Tìm hiểu về thuật toán RadixSort

Nội dung text: Đồ án Tìm hiểu về thuật toán RadixSort

1. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN LỜI NÓI ĐẦU Trong những năm qua, vấn đề công nghệ thông tin đang được quan tâm rất nhiều, song song đó là sự phát triển của máy vi tính với nhiều ứng dụng rộng rãi trong mọi lĩnh vực của cuộc sống .Nó hỗ trợ cho nhân viên làm việc ở văn phòng cho đến những nhà khoa học làm việc trong các phòng thí nghiệm. Cấu trúc dữ liệu và giải thuật là môn học nền tảng của ngành CNTT. Các cấu trúc dữ liệu luôn gắn liền với các ứng dụng trong thực tế. Vì vậy khi được giao làm đề tài “ Tìm hiểu về thuật toán RadixSort ” dưới sự hướng dẫn của thầy giáo Lưu Văn Hiền.Việc làm đồ án giúp cho em hiểu biết thêm về các giải thuật tác động lên dữ liệu cũng như cách tổ chức , sắp xếp dữ liệu để giải quyết các bài toán sao cho dễ nhất, tối ưu nhất. Em xin chân thành cảm ơn sự giúp đỡ và hướng dẫn của thầy để em hoàn thành đồ án này. Tuy nhiên, trong khi thực hiện sẽ không tránh khỏi được sai sót, mong các thầy cô góp ý cho em sửa chữa để có thể thực hiện tốt hơn với các đồ án sau. Em xin chân thành cám ơn! Đà Nẵng, ngày 01 tháng 10 năm 2008 SVTH Củng Công Minh SVTH : CỦNG CÔNG MINH 1 ĐỀ TÀI: RADIXSORT
2. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN MỤC LỤC LỜI NÓI ĐẦU Phần 1: Tổng quan về thuật toán RadixSort 4 1. Giới thiệu thuật toán : 4 2. Ý tưởng thuật toán : 4 3. Ví dụ minh họa về thuật toán : . 5 4. Giải thích: . 11 Phần 2: Trình bày về cấu trúc dữ liệu Queue 11 1. Định nghĩa: 11 2. Ví dụ : 11 3. Một số ứng dụng của cấu trúc hàng đợi : 13 4. Một số thao tác phép toán trên hàng đợi: 13 5.Cài đặt hàng: 13 5.1 Cài đặt hàng bằng mảng : .15 5.1.1 Phương pháp di chuyển tịnh tiến khi hàng bị tràn : 15 Tạo hàng rỗng CREATE_QUEUE(Q) Kiểm tra hàng rỗng EMPTY_QUEUE Kiểm tra hàng đầy FULL_QUEUE(Q) Xóa 1 phần tử của hàng REMOVE(Q) Thêm 1 phần tử vào hàng ADD(x,Q) Xác định giá trị của phần tử đầu tiên của hàng FRONT(Q) SVTH : CỦNG CÔNG MINH 2 ĐỀ TÀI: RADIXSORT
3. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN 5.1.2 Phương pháp mảng xoay vòng : 15 Xóa 1 phần tử của hàng REMOVE(Q) Kiểm tra hàng đầy FULL_QUEUE(Q) Thêm 1 phần tử vào hàng ADD(x,Q) 5.2 Cài đặt hàng bằng danh sách liên kết(dùng con trỏ) 16 Khởi tạo hàng rỗng CREATE_QUEUE(Q) Kiểm tra hàng rỗng EMPTY_QUEUE Thêm 1 phần tử vào hàng ADD(x,Q) Xóa 1 phần tử của hàng REMOVE(Q) Xác định giá trị của phần tử đầu tiên của hàng FRONT(Q) Phần 3: Tìm hiểu những thành phần liên quan của ngôn ngữ VB để cài đặt thuật toán. Một số đối tượng trong ngôn ngữ Visual Basic . Công cụ lưới VSFlex Grid 6.0 và cách thức làm việc với lưới này. Phần 4: Lưu đồ thuật toán Phần 5: Cài đặt 18 Màn hình mô phỏng từng bước chạy của thuật toán RadixSort TÀI LIỆU THAM KHẢO 19 NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN 20 NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN 21 SVTH : CỦNG CÔNG MINH 3 ĐỀ TÀI: RADIXSORT
4. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN Phần 1: Tổng quan về thuật toán RadixSort 1. Giới thiệu thuật toán : Khác với các thuật toán trước, Radix sort là một thuật toán tiếp cận theo một hướng hoàn toàn khác. Nếu như trong các thuật toán khác, cơ sở để sắp xếp luôn là việc so sánh giá trị của 2 phần tử thì Radix sort lại dựa trên nguyên tắc phân loại thư của bưu điện. Vì lý do đó nó còn có tên là Postman?s sort. Nó không hề 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ử. Ta biết rằng, để chuyển một khối lượng thư lớn đến tay người nhận ở nhiều địa phương khác nhau, bưư điện thường tổ chức một hệ thống phân loại thư phân cấp. Trước tiên, các thư đến cùng một tỉnh, thành phố sẽ được sắp chung vào một lô để gửi đến tỉnh thành tương ứng. Bưu điện các tỉnh thành này lại thực hiện công việc tương tự. Các thư đến cùng một quận, huyện sẽ được xếp vào chung một lô và gửi đến quận, huyện tương ứng. Cứ như vậy, các bức thư sẽ được trao đến tay người nhận một cách có hệ thông mà công việc sằp xếp thư không quá nặng nhọc. 2. Ý tưởng thuật toán : Coi các phần tử trong mảng sắp xếp được cấu thành từng các lớp có độ ưu tiên khác nhau. Ví dụ, các số tự nhiên chia thành các lớp như: hàng đơn vị, hàng chục, hàng trăm, hàng nghìn, Bước đầu tiên ta sắp xếp dãy các phần tử bằng cách so sánh các phần tử ở lớp có độ ưu tiên thấp nhất (ví dụ các chữ số hàng đơn vị). Số nào có hàng đơn vị thấp hơn thì ta đưa lên trên. Như vậy các số có hàng đơn vị là 0 ở trên cùng, sau đó đến các số có hàng đơn vị là 1, Sau bước 1, ta thu được 1 thứ tự sắp xếp mới. Ta lại làm tương tự với các lớp kế tiếp(chữ số thuộc hàng chục, hàng trăm, ) cuối cùng ta sẽ có dãy đã sắp xếp. SVTH : CỦNG CÔNG MINH 4 ĐỀ TÀI: RADIXSORT
5. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN 3. Ví dụ minh họa về thuật toán : Cho dãy như sau: {701, 1725, 999, 9170, 3252, 4518, 7009, 1424, 428, 1239, 8425, 7013} Ta viết theo dạng cột để quan sát: Dãy ban đầu Sắp xếp theo Sắp xếp theo Sắp xếp theo Sắp xếp theo hàng hàng đơn vị hàng chục hàng trăm nghìn 0 7 0 1 9 1 7 0 0 7 0 1 7 0 0 9 0 4 2 8 1 7 2 5 0 7 0 1 7 0 0 9 7 0 1 3 0 7 0 1 0 9 9 9 3 2 5 2 7 0 1 3 9 1 7 0 0 9 9 9 9 1 7 0 7 0 1 3 4 5 1 8 1 2 3 9 1 2 3 9 3 2 5 2 1 4 2 4 1 4 2 4 3 2 5 2 1 4 2 4 4 5 1 8 1 7 2 5 1 7 2 5 1 4 2 4 1 7 2 5 7 0 0 9 8 4 2 5 8 4 2 5 8 4 2 5 3 2 5 2 1 4 2 4 4 5 1 8 0 4 2 8 0 4 2 8 4 5 1 8 0 4 2 8 0 4 2 8 1 2 3 9 4 5 1 8 7 0 0 9 1 2 3 9 0 9 9 9 3 2 5 2 0 7 0 1 7 0 1 3 8 4 2 5 7 0 0 9 9 1 7 0 1 7 2 5 8 4 2 5 7 0 1 3 1 2 3 9 0 9 9 9 0 9 9 9 9 1 7 0 SVTH : CỦNG CÔNG MINH 5 ĐỀ TÀI: RADIXSORT
6. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN Hoặc viết theo dạng hàng để quan sát: Sắp xếp theo hàng đơn vị: 12 0701 11 1725 10 0999 9 9170 8 3252 7 4518 6 7009 5 1424 4 0428 3 1239 0999 2 8425 1725 4518 7009 1 7013 9170 0701 3252 7013 1424 8425 0428 1239 CS A 0 1 2 3 4 5 6 7 8 9 Các lô B dùng để phân loại SVTH : CỦNG CÔNG MINH 6 ĐỀ TÀI: RADIXSORT
7. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN Sắp xếp theo hàng chục: 12 0999 11 7009 10 1239 9 4518 8 0428 7 1725 6 8425 5 1424 4 7013 0428 3 3252 1725 2 0701 7009 4518 8425 1 9170 0701 7013 1424 1239 3252 9170 0999 CS A 0 1 2 3 4 5 6 7 8 9 SVTH : CỦNG CÔNG MINH 7 ĐỀ TÀI: RADIXSORT
8. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN Sắp xếp theo hàng trăm: 12 0999 11 9170 10 3252 9 1239 8 0428 7 1725 6 8425 5 1424 4 4518 3 7013 0428 2 7009 7013 3252 8425 1725 1 0701 7009 9170 1239 1424 4518 0701 0999 CS A 0 1 2 3 4 5 6 7 8 9 SVTH : CỦNG CÔNG MINH 8 ĐỀ TÀI: RADIXSORT
9. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN Sắp xếp theo hàng ngàn: 12 0999 11 1725 10 9 4518 8 0428 7 8425 6 1424 5 3252 4 1239 3 9170 0999 1725 2 7013 0701 1424 7013 1 7009 0428 1239 3252 4518 7009 8425 9170 CS A 0 1 2 3 4 5 6 7 8 9 SVTH : CỦNG CÔNG MINH 9 ĐỀ TÀI: RADIXSORT
10. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN Lấy các phần tử từ các lô B0, B1, ., B9 nối lại thành a: 12 9170 11 8425 10 7013 9 7009 8 4518 7 3252 6 1725 5 1424 4 1239 3 0999 2 0701 1 0428 CS A 0 1 2 3 4 5 6 7 8 9 SVTH : CỦNG CÔNG MINH 10 ĐỀ TÀI: RADIXSORT
11. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN 4.Giải thích: Quy tắc duyệt các phần tử từ trên xuống dưới. Ban đầu sắp xếp theo hàng đơn vị,tức là số nào có hàng đơn vị là 0 lên trên cùng, kế đến là 1,2, Như vậy số 9170 được chuyển lên trên cùng. Ta thấy không còn số nào có hàng đơn vị là 0 nữa, nên duyệt các số có hàng đơn vị là 1. Ta đưa 0701 ở vị trí thứ 2. Tiếp theo không còn số nào có hàng đơn vị là 1, ta xét các số có hàng đơn vị là 2, như vậy ta đưa số 3252 lên vị trí thứ 3, quá trình kết thúc ta được cột số 2 trong bảng. Từ cột thứ 2, ta sắp xếp các số theo hàng chục. Như vậy số nào có hàng chục là 0 thì lên trên cùng. Khi đó ta đưa 0701 lên vị trí số 1, sau đó là 7009 lên vị trí số 2. Bây giờ thì hết số có hàng chục là 0, nên ta đưa số có hàng chục là 1 lên, như vậy số 7013 ở vị trí thứ 3, số 4518 ở vị trí thứ 4, Kết thúc ta được cột thứ 3 trong bảng. Tương tự ta sắp xếp theo hàng trăm và hàng nghìn, ta thu được cột thứ 3 và thứ 4. Ở cột thứ 4 ta thu được dãy đã sắp xếp. 5.Nhận xét:  Thuật toán có độ phức tạp tuyến tính nên hiệu quả khi sắp dãy cố rất nhiều phần tử, nhất là khi khóa sắp xếp không quá dài so với số lượng phần tử (điều này thường gặp trong thực tế). được x là phần tử median của dãy. Tuy nhiên do chi phí xác định phần tử median quá cao nên trong thực tế người ta không chọn phần tử này mà chọn phần tử nằm chính giữa dãy làm mốc với hy vọng nó có thể gần với giá trị median  Thuật toán không có trường hợp xấu nhất và tốt nhất. Mọi dãy số đều được sắp với chi phí như nhau nếu chúng có cùng số phần tử và các khóa có cùng chiều dài.  Thuật toán cài đặt thuận tiện với các mảng với khóa sắp xếp là chuỗi (ký tự hay số) hơn là khóa số như trong ví dụ do tránh được chi phí lấy các chữ số của từng số.  Tuy nhiên, số lượng lô lớn (10 khi dùng số thập phân, 26 khi dùng chuỗi ký tự tiếng anh, .) nhưng tổng kích thước của tất cả các lô chỉ bằng dãy ban đầu nên ta không thể dùng mảng để biểu diễn B. Như vậy, phải dùng cấu trúc dữ liệu động để biểu diễn B => Radix sort rất thích hợp cho sắp xếp trên danh sách liên kết.  Người ta cũng dùng phương pháp phân lô theo biểu diễn nhị phân của khóa sắp xếp. Khi đó ta có thể dùng hoàn toàn cấu trúc dữ liệu mảng để biểu diễn B vì chỉ cần dùng hai lô B0 và B1. Tuy nhiên, khi đó chiều dài khóa sẽ lớn. Khi sắp các dãy không nhiều phần tử, thuật toán Radix sort sẽ mất ưu thế so với các thuật toán khác. SVTH : CỦNG CÔNG MINH 11 ĐỀ TÀI: RADIXSORT
12. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN Phần 2: Trình bày về cấu trúc dữ liệu Queue 1. Định nghĩa: Queue là một danh sách có đặc điểm là thao tác thêm nút được thực hiện ở một đầu, và thao tác lấy nút ra được thực hiện ở đầu còn lại. Xếp hàng mua vé xem phim là một hình ảnh trực quan của khái niệm trên, người mới đến thêm vào cuối hàng còn người ở đầu hàng mua vé và ra khỏi hang, vì vậy hàng còn được gọi là cấu trúc FIFO (first in - first out) hay "vào trước - ra trước". 2.Ví dụ : Sử dụng mảng để biểu diễn hàng đợi : Thao tác thêm nút vào hàng đợi chỉ được thực hiện ở vị trí rear (rear có nghĩa là đằng sau,ở đây xếp hàng :ai đến trước đứng trước,ai đến sau đứng đằng sau ): Thao tác lấy nút ra khỏi hàng đợi chỉ được thực hiện tại vị trí front (đầu của hàng đợi): SVTH : CỦNG CÔNG MINH 12 ĐỀ TÀI: RADIXSORT
13. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN Nút nào vào hàng đợi trước thì sẽ được lấy ra khỏi hàng đợi trước( FIFO : first in – first out ) 3. Một số ứng dụng của cấu trúc hàng đợi : Hàng đợi là một cấu trúc dữ liệu được dùng khá phổ biến trong thiết kế giải thuật. Bất kỳ nơi nào ta cần quản lí dữ liệu, quá trình theo kiểu vào trước-ra trước đều có thể ứng dụng hàng đợi. Ví dụ rất dễ thấy là quản lí in trên mạng, nhiều máy tính yêu cầu in đồng thời và ngay cả một máy tính cũng yêu cầu in nhiều lần. Nói chung có nhiều yêu cầu in dữ liệu, nhưng máy in không thể đáp ứng tức thời tất cả các yêu cầu đó nên chương trình quản lí in sẽ thiết lập một hàng đợi để quản lí các yêu cầu. Yêu cầu nào mà chương trình quản lí in nhận trước nó sẽ giải quyết trước. 4. Một số thao tác phép toán trên hàng đợi: ▪ CREAT_QUEUE(Q) khởi tạo hàng đợi ▪ EMPTY_QUEUE(Q) kiểm tra hàng đợi có rỗng không. ▪ FULL_QUEUE(Q) kiểm tra hàng đợi có bị đầy không. ▪ ADD(x,Q) thêm một phần tử x vào hàng đợi. ▪ REMOVE(Q) xóa phần tử tại đầu của hàng đợi. ▪ FRONT(Q) hàm trả về giá trị của phần tử đầu tiên của hàng. 5.Cài đặt hàng: 5.1 Cài đặt hàng bằng mảng : Ta dùng 1 mảng để chứa các phần tử của hàng, khởi đầu phần tử đầu tiên của hàng được đưa vào vị trí thứ 1 của mảng, phần tử thứ 2 đưa vào vị trí thứ 2 của mảng, Giả sử hàng có n phần tử ta có front=0, rear=n. Khi xóa 1 phần tử front tăng lên 1, khi thêm 1 phần tử rear tăng lên 1. Như vậy hàng có khuynh hướng đi xuống,đến 1 lúc nào đó ta không thể thêm vào hàng được nữa dù mảng còn nhiều chỗ trống(các vị trí trước front) trường hợp này ta gọi là hàng bị tràn. SVTH : CỦNG CÔNG MINH 13 ĐỀ TÀI: RADIXSORT
14. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN Pt1 Pt2 Pt3 Pt4 Pt5 Pt6 Front Rear Trong trường hợp toàn bộ mảng đã chứa các phần tử của hàng ta gọi là hàng bị đầy. Cách khắc phục hàng bị tràn: Dời toàn bôn mảng lên front vị trí, cách này gọi là di chuyển tịnh tiến.Trong trường hợp này ta luôn có front<rear. Xem mảng như là 1 vòng tròn nghĩa là khi hàng bị tràn nhưng chưa đầy ta thêm phần tử mới vào vị trí 1 của mảng, thêm 1 phần tử mới nữa thì thêm vào vị trí 2 (nếu có thể) Rõ ràng cách làm này front có thể lớn hơn rear.Cách khắc phục này gọi là dùng mảng xoay vòng 5.1.1 Phương pháp di chuyển tịnh tiến khi hàng bị tràn : Để quản lý ta chỉ cần quản lý đầu hàng (front) và cuối hàng (rear).Giả sử cần 1 khoảng tối đa MAXSIZE phần tử cho mảng . Khai báo cài đặt Const maxsize = . struct QUEUE{ Kiểu_lưu_trữ A[maxsize]; //Mảng A dùng để lưu trữ dữ liệu. int front,rear ; }; Cài đặt bằng ngôn ngữ Visual Basic: Private Type QUEUE a(100) As Integer '/Mang A dung de luu tru du lieu A1(100) As Integer SVTH : CỦNG CÔNG MINH 14 ĐỀ TÀI: RADIXSORT
15. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN front As Integer rear As Integer End Type Tạo hàng rỗng CREAT_QUEUE(Q) Lúc này front và rear không trỏ đến vị trí hợp lệ nào trong mảng vậy ta có thể cho front và rear đều bằng 0 . void CREAT_QUEUE(QUEUE&Q) { Q.front=Q.rear=0; } Cài đặt bằng ngôn ngữ Visual Basic: Private Sub CREAT_QUEUE(Q As QUEUE) '/ Tao hang rong Q.front = Q.rear = 0 End Sub Kiểm tra hàng rỗng EMPTY_QUEUE Trong quá trình làm việc ta có thể thêm và xóa các phần tử trong hàng.Rõ ràng , nếu ta có đưa vào hàng 1 phần tử nào đó thì rear>0 .Khi xóa 1 phần tử ta tăng front lên 1 , nếu hàng rỗng (front=rear) cũng đặt front=0 . Hơn nữa khi mới khởi tạo hàng , tức là front=0 thì hàng cũng rỗng.Vì vậy hàng rỗng khi và chỉ khi front=0 . int EMPTY_QUEUE(QUEUE Q) { if (Q.front = = 0) return 1; else return 0; } Cài đặt bằng ngôn ngữ Visual Basic: Private Function EMPTY_QUEUE(Q As QUEUE) '/ Kiem tra hang doi rong if Q.front = 0 Then EMPTY_QUEUE = 1 else EMPTY_QUEUE = 0 end if End Function Kiểm tra hàng đầy FULL_QUEUE(Q) Hàng đầy nếu số phần tử hiện có trong hàng bằng độ dài của mảng. int FULL_QUEUE(Q) { if(Q.rear - Q.front = = maxsise) return 1; else return 0; } Cài đặt bằng ngôn ngữ Visual Basic: Private Function FULL_QUEUE(Q As QUEUE) '/ Kiem tra hang doi day if Q.rear - Q.front = 100 Then SVTH : CỦNG CÔNG MINH 15 ĐỀ TÀI: RADIXSORT
16. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN FULL_QUEUE = 1 else FULL_QUEUE = 0 end If End Function Xóa 1 phần tử của hàng REMOVE(Q) Xóa phần tử đầu hàng ta chỉ cần cho front tăng lên 1 . Nếu front = rear thì hàng thực chất đã rỗng, nên ta khởi tạo lại hàng đợi rỗng (tức là đặt lại giá trị front = rear = 0) . Trường hợp hàng đợi rỗng không xác định. void REMOVE(QUEUE&Q) { if( !EMPTY_QUEUE(Q)) { Q.front = Q.front + 1; if(Q.front = = Q.rear) Q.front = Q.rear = 0; } else cout -1 Then Q.front = Q.front + 1 else Q.front = Q.front + 2 end If if (Q.front = Q.rear) Then Q.front = Q.rear = 0 End Sub Thêm 1 phần tử vào hàng ADD(x,Q) Khi thêm 1 phần tử vào hàng ta xét các trường hợp sau + Nếu hàng đầy thì không thêm được nữa . +Nếu hàng chưa đầy ta phải xem xét hàng có bị tràn hay không.Nếu bị tràn ta di chuyển tịnh tiến rồi mới nối thêm phần tử mới vào đuôi hàng , rear tăng lên 1.Đặc biệt nếu thêm vào hàng rỗng thì ta cho front = 1 để front trỏ đúng phần tử đầu tiên của hàng . void ADD(Kiểu_lưu_trữ x<QUEUE&Q) { if (FULL_QUEUE(Q)) { if(Q.rear = = maxsize) { // Di chuyển tịnh tiến toàn bộ hàng lên front – 1 vị trí . for(int i = Q.front + 1; i<=0; i++) Q.A[i-Q.front ] = Q.A[i]; SVTH : CỦNG CÔNG MINH 16 ĐỀ TÀI: RADIXSORT
17. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN // Đặt lại giá trị đầu hàng , cuối hàng . Q.rear = maxsize – Q.front ; Q.front = 0 ; } Q.rear = Q.rear + 1 ; Q.A[Q.rear] = x ; } else cout 1) Then if (Q.rear = 100) Then for i = Q.front + 1 To Q.rear Q.a(i - Q.front) = Q.a(i) Next i Q.rear = 100 - Q.front Q.front = 0 end if Q.rear = Q.rear + 1 Q.a(Q.rear) = x end if End Function Xác định giá trị của phần tử đầu tiên của hàng FRONT(Q) Trường hợp hàng rỗng thì không xác định . Kiểu_dữ_liệu FRONT(QUEUE Q) { if(EMPTY_QUEUE(Q)) cout 1 Then if Q.front = -1 Then Q.front = Q.front + 1 FRONT1 = Q.a(Q.front + 1) end if End Function SVTH : CỦNG CÔNG MINH 17 ĐỀ TÀI: RADIXSORT
18. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN 5.1.2 Phương pháp mảng xoay vòng : [2] [2] [1] [3] J2 [3] [1] J3 J 1 [0] [4] [4] [0] front=0 front=0 [5] rear=0 [5] rear=3 Khi hàng bị tràn tức là rear = maxsize, nhưng chưa đầy, tức là front>0, thì ta thêm phần tử mới vào vị trí 1 của mảng và cứ tiếp tục như vậy vì từ 1 đến front là các vị trí trống. Vì ta sử dụng mảng 1 cách xoay vòng như vậy nen phương pháp này gọi là phưong pháp dùng mảng xoay vòng. Các phần khai báo cấu trúc QUEUE , tạo hàng rỗng, kiểm tra hàng rỗng hoặc xác định giá trị ở đầu hàng giống như phương pháp di chuyển tịnh tiến . Xóa 1 phần tử của hàng REMOVE(Q) Xóa phần tử đầu hàng ta chỉ cần cho front tăng lên 1 . Nếu front = rear thì hàng thực chất đã rỗng, nên ta khởi tạo lại hàng đợi rỗng (tức là đặt lại giá trị front = rear = 0) . void REMOVE(QUEUE&Q) { if( !EMPTY_QUEUE(Q)) { Q.front = Q.front % maxsize + 1; if(Q.front = = Q.rear) Q.front = Q.rear = 0; } else cout<<”Lỗi : Hàng rỗng”; } Kiểm tra hàng đầy FULL_QUEUE(Q) Hàng đầy nếu số phần tử hiện có trong hàng bằng độ dài của mảng. int FULL_QUEUE(QUEUE Q) SVTH : CỦNG CÔNG MINH 18 ĐỀ TÀI: RADIXSORT
19. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN { if(Q.rear = = Q.front)&& Q.rear != 0 ) return 1; else return 0; } Thêm 1 phần tử vào hàng ADD(x,Q) Trường hợp hàng đầy không thêm được. void ADD(Kiểu_lưu_trữ x,QUEUE&Q) { if (FULL_QUEUE(Q)) { Q.rear = = Q.rear % maxsize + 1; Q.A[Q.rear] = x ; } else cout<<”Lỗi : Hàng đầy” } 5.2 Cài đặt hàng bằng danh sách liên kết(dùng con trỏ) Với danh sách liên kết có thể dùng 2 con trỏ front và rear để trỏ tới phần tử đầu hàng và cuối hàng như hình sau: NULL front rear Khai báo kiểu dữ liệu struct Node{ Kiểu_dữ_liệu Info ; // Trường Info chứa thông tin cần lưu trữ. Node *Next ; // Next là con trỏ trỏ đến phần tử kế tiếp . }; Struct QUEUE { Node*front , *rear ;}; Khởi tạo hàng rỗng CREAT_QUEUE(Q) void CREAT_QUEUE(QUEUE&Q) { Q.front = Q.rear = NULL; } SVTH : CỦNG CÔNG MINH 19 ĐỀ TÀI: RADIXSORT
20. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN Kiểm tra hàng rỗng EMPTY_QUEUE Hàng rỗng nếu front hoặc rear bằng NULL int EMPTY_QUEUE(QUEUE Q) { if (Q.front = = NULL) return 1; else return 0; } Thêm 1 phần tử vào hàng ADD(x,Q) Thêm 1 phần tử vào hàng thực chất là chèn 1 giá trị x vào cuối danh sách liên kết . void ADD(Kiểu_lưu_trữ x,QUEUE&Q) { Node*p = new Node ; // Cấp phát 1 Node mới . p->Info = x ; p->Next = NULL ; if(Q.front = = NULL) Q.front = p ; // Khi Q rỗng thì thành Q có 1 phần tử. Else Q.rear = p ; } SVTH : CỦNG CÔNG MINH 20 ĐỀ TÀI: RADIXSORT
21. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN Xóa 1 phần tử của hàng REMOVE(Q) Thực chất là xóa phần tử nằm ở đầu danh sách.Trường hợp danh sách rỗng không xóa được . void REMOVE(QUEUE&Q) { if( !EMPTY_QUEUE(Q)) { Node*p = Q.front ; Q.front  p-> Next ; delete(p) ; } else cout Info ; } Phần 3: Tìm hiểu những thành phần liên quan của ngôn ngữ VB để cài đặt thuật toán. 1. Giới thiệu 1 số đối tượng trong ngôn ngữ Visual Basic : SVTH : CỦNG CÔNG MINH 21 ĐỀ TÀI: RADIXSORT
22. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN Inttrrinsicc CCoonntrroolss Pointer tool Picture box Label Text box Frame Command button Check Option button box Combo box List box Horizontal scroll bar Vertical scroll bar Timer Drive list Directory list box File list box Shape Image Line OLE container Data • Text Box (hộp nhập liệu) . Được dùng để nhận/ nhập thông tin (i.e., input) từ người dùng • Command Button (nút lệnh) . Thực hiện hành động khi người dùng Click vào nó • Label – Nhãn . Cho người dùng biết thông tin được nhập vào hoặc hiển thị thông tin (không sửa đổi khi chạy chương trình) • Picture Box – Hộp ảnh . Được dùng để hiển thị Text hoặc hình ảnh đồ họa • Check boxes . Hộp kiểm (checked – 1 hoặc unchecked 0 – grayed – 2 (chọn và bị mờ)) • Option Buttons – Nút chọn . Selected – True, Not selected - False • Frames - Khung . Được dùng để nhóm các đối tượng với nhau phục vụ cùng một mục đích • List boxes – Hộp danh sách . Được dùng để liệt kê danh sách chọn • Combo boxes . Kết hợp giữa text & List • Timer . Đối tượng ẩn, được triệu gọi khi người lập trình thiết lập thuộc tính interval cho nó SVTH : CỦNG CÔNG MINH 22 ĐỀ TÀI: RADIXSORT
23. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN 2. Giới thiệu về công cụ lưới MSFlex Grid : 2.1 Các thuộc tính thường dùng của MSFlexgrid khi lập trình : - AllowBigSelection : Cho phép chọn một nhiều cell bằng cách nhấp vào fixed area. - AllowUserResizing : Cho phép người dùng thay đổi kích thước dòng và cột bằng chuột. - BackColorBkg : Màu nền của vùng không chứa cell. - BackColorFixed : Màu nền của các dòng và cột tiêu đề (FixedCols). - BackColorSel : Màu nền của các cell đuợc chọn. - Cols, rows : số cột và số dòng trên grid - DataSource : Quy định nguồn dữ liệu nguồn cho VSFlexGrid. - FixedCols, FixedRows: số cột và số dòng header. - FillStyle : Thay đổi nội dung của cell hịện tại hay toàn bộ các cell được chọn - Formatstring : dùng gán tên cho các cột, tên giữa các cột được ngăn cách bởi dấu - GridLine : quy định cách thể hiện của các đường kẻ giữa các dòng và cột. - GridLinesFixed : Quy định kiều đường phân cách giữa các fixed cell. - GridLineWidth : Quy định độ dày của của các đường kẻ (tính bằng pixel). - HighLight : Quy định vùng selected có được làm nồi bật hay không. - MergeCells : Kết hợp các cell có cùng nội dung thành 1 (kết hợp theo dòng/ cột) - TextStyle : quy định kiểu chữ cho grid. - TextStyleFixed : quy định kiểu chữ cho fixedRow & fixedCol - SelectionMode : quy định chế độ chọn trên grid flexSelectionFree, flexSelectionByRow, flexSelectionByColumn, flexSelectionListBox - Index : chỉ số . - v v Các thuộc tính thông dụng : Thuộc tính Giải thích Left Vị trí cạnh trái của điều khiển so với vật chứa nó Top Vị trí cạnh trên của điều khiển so với vật chứa nó Height Chiều cao của điều khiển Width Chiều rộng của điều khiển Name Một giá trị chuỗi được dùng để nói đến điều khiển Enable Giá trị logic (True hoặc False) quyết định người sử dụng có được làm việc với điều khiển hay không Visible Giá trị logic (True hoặc False) quyết định người sử dụng có thấy điều khiển hay không SVTH : CỦNG CÔNG MINH 23 ĐỀ TÀI: RADIXSORT
24. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN 2.2 Nội dung các thao tác trên lưới: 2.2.1 Gán dữ liệu lên VSFlexGrid: Sử dụng thuộc tính DataSource của VSFlexGrid: tham chiếu trực tiếp đến nguồn dữ liệu. Thứ tự các cột dữ trên grid sẽ tương ứng với thứ tự của dữ liệu cần thể hiện trên grid, số lượng cột và dòng trên cũng tương ứng với số field và số record của dữ liệu. Ví dụ : Set MSFlexGrid1.DataSource = [DataSource] Merge dữ liệu trên grid: • MergeCol : xác định các cột sẽ được merge (mang giá trị True|False) Ví dụ : MSFlexGrid1.MergeCol = True • MergeRow : xác định các dòng sẽ merge (mang giá trị True|False) Ví dụ : MSFlexGrid1.MergeRow = True 2.2.3 Các thao tác trên dòng và cột: - RowPosition, RowData, RowHeight, RowHeightMin, RowVisible, RowPos,RowSel,Rows, - ColData, ColPosition,ColVisible, Ví dụ : Tô màu xen kec cho giữa các hàng Public Sub FG_AlternateRowColors(FG As MSFlexGrid, lColor1 As Long, lcolor2 As Long) Dim lRow As Long, lCol As Long Dim lOrgRow As Long, lOrgCol As Long Dim lColor As Long With FG ' MSFlexGrid1 <- Bugfix as stated by Trivium .Redraw = False lOrgRow = .Row ' save the current cell position lOrgCol = .Col For lRow = .FixedRows To .Rows – 1 ' only the data rows .Row = lRow If lRow / 2 = lRow \ 2 Then lColor = lColor1 Else lColor = lcolor2 End If For lCol = .FixedCols To .Cols – 1 ' only the data columns .Col = lCol .CellBackColor = lColor Next lCol Next lRow ' restore the orginal cell position .Row = lOrgRow .Col = lOrgCol .Redraw = True End With End Sub SVTH : CỦNG CÔNG MINH 24 ĐỀ TÀI: RADIXSORT
25. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN 2.2.4 Các thao tác trên cell: Truy xuất và cập nhật nội dung của cell : - Textmatrix (row, col): truy xuất đến dữ liệu của cell. - Text: truy xuất hoặc cập nhật nội dung của cell được chọn (kết hợp với phương thức Select). - TextArray: truy xuất hoặc gán nội dung cho cell theo chỉ số cell truyền vào. - TextStyle - TextStyleFixed - v.v Ví dụ : Chỉnh sửa Cell Option Explicit ' to store the row/column of the cell ' being edited Dim m_lCellCol As Long Dim m_lCellRow As Long Private Sub Form_Load() m_lCellRow = -1 m_lCellCol = -1 txtCell.BorderStyle = 0 txtCell.Visible = False ' set the text background color to the ' backcolor of the tooltip text to make ' the cell being edited having a different color txtCell.BackColor = vbInfoBackground MSFlexGrid1.Cols = 10 MSFlexGrid1.Rows = 10 End Sub 2.2.5 Selection mode: SelectionMode: thiết lập chế độ select trên grid Ví dụ : MSFlexGrid1.SelectionMode = flexSelectionByColumn Các giá trị của SeectionlMode - FlexSelectionFree - FlexSelectionByRow - FlexSelectionByColumn - v v SVTH : CỦNG CÔNG MINH 25 ĐỀ TÀI: RADIXSORT
26. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN 2.2.6 Các phương thức khác của VSFlex Grid : - AddItem: MSFlexGrid1.AddItem - RemoveItem: MSFlexGrid1.RemoveItem - Clear: MSFlexGrid1.Clear - Drag - Move - SetFocus 3. Một số bước cơ bản làm việc với lưới MSFlex Grid 6.0 : + Cách chèn điều khiển lưới MSFlex vào công cụ Toolbox : Project Components Microsoft Flex Grid 6.0 OK . + Đưa dữ liệu và điều khiển lưới thông qua thuộc tính và phương thức : ROWS và COLUMS cung cấp các ô để đưa dữ liệu vào lưới . + Dùng phương thức AddItems để đưa dữ liệu vào lưới . + Dùng phương thức Format String để tạo tiêu đề cho lưới . - Gán chuỗi lí tự cho dòng tiêu đề . - Cho phép canh lề các ô trống trong lưới ngay lúc đưa vào tiêu đề . + Dùng phương thức Text Matrix để đưa hình ảnh vào điều khiển lưới : CellPicture , LoadPicture , Set , + Sắp xếp dữ liệu trong điều khiển lưới . + Dùng điều khiển lưới Flex để trộn dữ liệu trong ô . + Sử dụng lưới Flex với cơ sở dữ liệu . + v.v SVTH : CỦNG CÔNG MINH 26 ĐỀ TÀI: RADIXSORT
27. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN Phần 4: Lưu đồ thuật toán Begin int *A int n, int i=0; i <= 9 CREATE_Q(Q[i]) i ++ k = Len(Max(100,13,20,66,70 8,54,939,25,30,69,258,76, 3812,9801,1286,37,2323, 5678)) j ++ End j <= k F i <= n T j=(A[i]/(int)pow(10,i-1))%10 SVTH : CỦNG CÔNG MINH 27 ĐỀ TÀI: RADIXSORT
28. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN ADD(A[i],Q[j]) i ++ n = 0 i <= 9 T !EMPTY_Q(Q[i]) End !EMPTY_Q(Q[i]) n = n + 1 A[n]  Front(Q[i]) REMOVE(Q[i]) i ++ SVTH : CỦNG CÔNG MINH 28 ĐỀ TÀI: RADIXSORT
29. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN Phần 5: Cài đặt Cho một file chứa 1 dãy số nguyên. Sắp xếp dữ liệu trên file này tăng dần bằng thuật toán RadixSort Dùng ngôn ngữ VB để cài đặt Vẽ 10 queue trên màn hình Mô tả được quá trình sắp xếp của thuật tóan bằng cách chạy từng bước Màn hình mô phỏng chương trình SVTH : CỦNG CÔNG MINH 29 ĐỀ TÀI: RADIXSORT
30. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH 30 ĐỀ TÀI: RADIXSORT
31. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH 31 ĐỀ TÀI: RADIXSORT
32. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN TÀI LIỆU THAM KHẢO : [1] Lưu Văn Hiền, giáo trình cấu trúc dữ liệu và giải thuật. [2] Nguyễn Thị Bảo Trang,giáo trình Cơ sở lập trình. [3] Trung tâm tin học- Ngoại ngữ Trí Đức (2002),Cấu trúc dữ liệu và giải thuật,, NXB Thống Kê. [4] Đỗ xuân Lôi (1995), Cấu trúc dữ liệu và giải thuật,, NXB Khoa học và kỹ thuật Hà Nội. [5] Nguyễn Đức Mận, Lập trình trực quan Visual Basic SVTH : CỦNG CÔNG MINH 32 ĐỀ TÀI: RADIXSORT
33. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN Đà Nẵng, Ngày Tháng .Năm Giáo Viên Hướng Dẫn SVTH : CỦNG CÔNG MINH 33 ĐỀ TÀI: RADIXSORT
34. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN Đà Nẵng, Ngày Tháng .Năm Giáo Viên Phản Biện SVTH : CỦNG CÔNG MINH 34 ĐỀ TÀI: RADIXSORT