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

ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 1 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 ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 2 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) ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 3 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 ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 4 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. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 5 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 hàng đơn vị Sắp xếp theo hàng chục Sắp xếp theo hàng trăm Sắp xếp theo hàng 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 ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 6 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 ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 7 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 ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 8 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 ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 9 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 ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 10 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 ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 11 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. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 12 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): ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 13 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. ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 14 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 Pt1 Pt2 Pt3 Pt4 Pt5 Pt6 ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 15 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 ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 16 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<<”Lỗi : Hàng rỗng”; } Cài đặt bằng ngôn ngữ Visual Basic: Private Sub REMOVE(Q As QUEUE) '/ Xoa 1 phan tu ra khoi hang doi if Q.front -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]; ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 17 // Đặ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<<”Lỗi : Hàng đầy ”; } Cài đặt bằng ngôn ngữ Visual Basic: Private Function ADD(x As Integer, Q As QUEUE) '/Them 1 phan tu vao hang doi if (FULL_QUEUE(Q) 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<<”Lỗi : Không xác định ”; else return Q.A[Q.front + 1]; } Cài đặt bằng ngôn ngữ Visual Basic: Private Function FRONT1(Q As QUEUE) if EMPTY_QUEUE(Q) 1 Then if Q.front = -1 Then Q.front = Q.front + 1 FRONT1 = Q.a(Q.front + 1) end if End Function ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 18 5.1.2 Phương pháp mảng xoay vòng : [2] [2] [1] [3] [3] [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) J2 J3 J 1 ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 19 { 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; } ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 20  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ử