Chức vụ:
Danh sách bộ nhớ được liên kết
Ngôn ngữ:
C
Tác giả:
Philip J. Erdelsky
Ngày:
Ngày 31 tháng 7 năm 1998
Sử dụng:
Phạm vi công cộng; không hạn chế sử dụng
Tính di động:
Bất kỳ trình biên dịch C nào
Từ khóa:
Danh sách liên kết, sắp xếp
Trừu tượng:
Một hàm C để sắp xếp một danh sách liên kết trong bộ nhớ, sử dụng một hàm so sánh tùy ý và thuật toán kết hợp băng, là O (n log n) trong mọi trường hợp. Hàm này không đệ quy và tái nhập, và chỉ thay đổi các liên kết.
Các danh sách liên kết và các thường trình sắp xếp rất phổ biến trong lập trình.
Hàm sort_linked_list () sẽ sắp xếp hầu như bất kỳ loại danh sách liên kết đơn lẻ nào, sử dụng hàm so sánh được cung cấp bởi chương trình gọi. Nó có những ưu điểm sau qsort ():
Hàm này chỉ sắp xếp các danh sách được liên kết đơn lẻ. Nếu một danh sách được liên kết gấp đôi, các con trỏ lạc hậu có thể được phục hồi sau khi sắp xếp theo một vài dòng mã.
Mỗi phần tử của một danh sách liên kết được sắp xếp phải chứa, như các thành viên đầu tiên của nó, một hoặc nhiều con trỏ. Một trong các con trỏ, mà phải ở trong cùng một vị trí tương đối trong mỗi phần tử, là một con trỏ đến phần tử tiếp theo. Con trỏ này là NULL trong phần tử cuối cùng.
Chỉ mục là vị trí của con trỏ này trong mỗi phần tử. Nó là 0 cho con trỏ đầu tiên, 1 cho con trỏ thứ hai, v.v.
Hãy so sánh () là hàm so sánh so sánh hai phần tử như sau:
n = so sánh (p, q, con trỏ);
void * p, * q; con trỏ đến hai phần tử danh sách
void * pointer; con trỏ do người dùng xác định được chuyển đến so sánh () bởi
linked_list_sort ()
int n; kết quả so sánh * p và * q
> 0 nếu * p là sau * q theo thứ tự sắp xếp
<0 nếu * p là trước * q theo thứ tự sắp xếp
0 nếu thứ tự của * p và * q không liên quan
Hãy để “đầu tiên” là một con trỏ đến phần tử đầu tiên của danh sách. Sau đó, hàm gọi sau sắp xếp danh sách và trả về một con trỏ tới phần tử đầu tiên của danh sách được sắp xếp:
first_sorted =
sort_linked_list (đầu tiên, chỉ mục, so sánh, con trỏ, số lượng);
Đối số thứ tư (con trỏ) được chuyển đến so sánh () mà không thay đổi. Ví dụ được đưa ra ở đây không sử dụng con trỏ. Tuy nhiên, nó có thể là một tính năng vô giá nếu hai hoặc nhiều phương thức so sánh chia sẻ một lượng đáng kể mã và chỉ khác nhau trong một hoặc nhiều giá trị tham số.
Đối số cuối cùng (pcount) thuộc loại (unsigned long *). Nếu nó không phải là NULL, thì * pcount được đặt bằng số lượng bản ghi trong danh sách.
Có thể sắp xếp một danh sách trống. Nếu đầu tiên == NULL, giá trị trả về cũng sẽ là NULL.
Ví dụ: một phần tử có thể chứa cả tên và số:
phần tử cấu trúc
{
phần tử struct * next_in_alphabetical_order;
struct element * next_in_numerical_order;
char name [9];
số int;
/ * các thành viên khác, nếu có * /
};
Ban đầu, hai con trỏ trong mỗi phần tử giống hệt nhau và danh sách theo thứ tự tùy ý, trong đó “đầu tiên” là một con trỏ đến phần tử đầu tiên. Hai hàm gọi sau sắp xếp danh sách hai lần:
first_in_alphabetical_order =
sort_linked_list (đầu tiên, 0, compare_names, NULL);
first_in_numerical_order =
sort_linked_list (đầu tiên, 1, compare_numbers, NULL);
Dưới đây là các hàm so sánh:
int compare_names (phần tử struct * p, phần tử struct * q,
void * pointer)
{
return strcmp (p-> name, q-> name);
}
int compare_numbers (struct element * p, struct element * q,
void * pointer)
{
trả lại p-> số> q-> số? 1: -1;
/ * LƯU Ý: trả lại p-> số – q-> số sẽ đủ nếu có
không có nguy cơ tràn số * /
}
Một phiên bản trước của loại này, được xuất bản trong một tạp chí kỹ thuật, yêu cầu liên kết chuyển tiếp ở đầu mỗi phần tử. Trong khi điều này làm cho loại hiệu quả hơn một chút, nó cũng làm cho nó khó sử dụng với nhân danh sách liên kết.
Thuật toán khá đơn giản. Danh sách liên kết (được gọi là “băng” bằng cách tương tự với băng từ cũ) được chia thành hai băng cùng kích thước hoặc gần giống nhau. Điều này được thực hiện bằng cách “viết” các yếu tố cho hai băng luân phiên.
Hai băng sau đó được sáp nhập, phần tử theo phần tử, thành các khối được sắp xếp có chứa hai phần tử. Các khối được viết xen kẽ với hai băng khác.
Hai băng sau đó được sáp nhập, chặn theo khối, thành các khối được sắp xếp gồm bốn phần tử, và các khối được viết xen kẽ với hai băng khác.
Quá trình này tiếp tục, tăng gấp đôi kích thước khối mỗi lần, cho đến khi tất cả các phần tử nằm trong một khối được sắp xếp duy nhất trên một băng. Hàm trả về một con trỏ tới phần tử đầu tiên của băng đó.
Mỗi kết hợp yêu cầu so sánh O (n), trong đó n là số phần tử. Số lần hợp nhất là O (log n). Do đó toàn bộ sắp xếp có các so sánh O (n log n).
Hàm sort_linked_list () là reentrant nếu hàm so sánh là reentrant.
Những người hâm mộ C sẽ vui mừng khi biết rằng thuật toán này không thể được mã hóa dễ dàng trong Ada hoặc Pascal bởi vì nó dựa trên các dự đoán.
Hàm sort_linked_list () có thể được gọi dễ dàng từ một chương trình C ++ với một modicum kiểu kiểm tra nếu tệp tiêu đề LLMSORT.H được bao gồm. Nó chứa một mẫu cho việc tạo một cuộc gọi nội tuyến trên sort_linked_list (). Định dạng của cuộc gọi như sau:
#include “llmsort.h”
first_sorted = sort_list (đầu tiên, so sánh, con trỏ, pcount);
yourclass * trước tiên;
yourclass * first_sorted;
void * pointer;
unsigned long * pcount;
Hàm compare () được gọi như sau:
n = so sánh (p, q, con trỏ);
const yourclass * p;
const yourclass * q;
Ở đây “yourclass” là bất kỳ lớp nào mà bạn có thể định nghĩa. Trình biên dịch sẽ kiểm tra tính nhất quán của các kiểu đối số và tạo ra lệnh gọi thích hợp trên sort_linked_list ().
Mã nguồn ở định dạng văn bản:
Original Source: http://www.efgh.com/software/llmsort.htm