Đồ án Tìm hiểu về thuật toán RadixSort - Củng Công Minh

Chia sẻ: Nguyễn Thị Ngọc Lựu | Ngày: | Loại File: PDF | Số trang:34

Thêm vào BST

Báo xấu

265
lượt xem 18
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đồ án Tìm hiểu về thuật toán RadixSort gồm 5 phần: tổng quan về thuật toán, trình bày về cấu trúc dữ liệu Queue, 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, cài đặt. Tài liệu này cung cấp cho người đọc những kiến thức cơ bản về giải thuật toán 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.

Chủ đề:

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

Lưu

Nội dung Text: Đồ án Tìm hiểu về thuật toán RadixSort - Củng Công Minh

ĐỒ Á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
ĐỒ Á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
ĐỒ Á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
ĐỒ Á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
ĐỒ Á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 0701 9170 0701 7009 0428 1725 0701 7009 7013 0701 0999 3252 7013 9170 0999 9170 7013 4518 1239 1239 3252 1424 1424 3252 1424 4518 1725 1725 1424 1725 7009 8425 8425 8425 3252 1424 4518 0428 0428 4518 0428 0428 1239 4518 7009 1239 0999 3252 0701 7013 8425 7009 9170 1725 8425 7013 1239 0999 0999 9170 SVTH : CỦNG CÔNG MINH 5 ĐỀ TÀI: RADIXSORT
ĐỒ Á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
ĐỒ Á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
ĐỒ Á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
ĐỒ Á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
ĐỒ Á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
ĐỒ Á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
ĐỒ Á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
ĐỒ Á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
ĐỒ Á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
ĐỒ Á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
ĐỒ Á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
ĐỒ Á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
ĐỒ Á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 J1 [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
ĐỒ Á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
ĐỒ Á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