Tôi đã thử tìm kiếm một vấn đề tương tự như của tôi, nhưng không tìm thấy nhiều trợ giúp.Sắp xếp chèn vào danh sách được liên kết trong C?
Tôi có một danh sách liên kết các cấu trúc thuộc loại này:
struct PCB {
struct PCB *next;
int reg1, reg2;
};
đầu tiên tôi tạo ra 10 struct PCB liên kết với nhau theo cách này:
for(i=20;i<=30;i++) {
curr = (struct PCB *)malloc(sizeof(struct PCB));
curr->reg1 = i;
curr->next = head;
head = curr;
}
sau đó tôi cần phải tạo thêm 20 struct PCB , nhưng giá trị reg1
cần phải được tạo bằng cách sử dụng rand()
. Tôi hiện đang làm điều đó như vậy:
for (j = 0;j<20;j++) {
curr = (struct PCB *)malloc(sizeof(struct PCB));
curr->reg1 = rand()%100;
curr->next = head;
head = curr;
}
Tuy nhiên, khi chèn những cấu trúc PCB vào danh sách liên kết với reg1
giá trị ngẫu nhiên, tôi cần phải được chèn chúng trong danh sách liên kết trong trật tự (sắp xếp chèn). Cách tốt nhất để tiếp cận điều này chỉ trong một danh sách liên kết đơn là gì? Cảm ơn
EDIT: Tôi bây giờ theo dõi các struct tạo đầu tiên để có thể lặp qua các danh sách liên kết ngay từ đầu:
// create root struct to keep track of beginning of linked list
root = (struct PCB *)malloc(sizeof(struct PCB));
root->next = 0;
root->reg1 = 20;
head = NULL;
// create first 10 structs with reg1 ranging from 20 to 30
for(i=21;i<=30;i++) {
curr = (struct PCB *)malloc(sizeof(struct PCB));
// link root to current struct if not yet linked
if(root->next == 0){
root->next = curr;
}
curr->reg1 = i;
curr->next = head;
head = curr;
}
Sau đó, khi tôi đang tạo ra thêm 10 PCB struct cần phải được sắp xếp:
// create 20 more structs with random number as reg1 value
for (j = 0;j<20;j++) {
curr = (struct PCB *)malloc(sizeof(struct PCB));
curr->reg1 = rand()%100;
// get root for looping through whole linked list
curr_two = root;
while(curr_two) {
original_next = curr_two->next;
// check values against curr->reg1 to know where to insert
if(curr_two->next->reg1 >= curr->reg1) {
// make curr's 'next' value curr_two's original 'next' value
curr->next = curr_two->next;
// change current item's 'next' value to curr
curr_two->next = curr;
}
else if(!curr_two->next) {
curr->next = NULL;
curr_two->next = curr;
}
// move to next struct in linked list
curr_two = original_next;
}
head = curr;
}
Nhưng điều này ngay lập tức đã làm hỏng chương trình của tôi.
cái này hoạt động chính xác! cảm ơn bạn! – Jakemmarsh
Nhưng Hey, tôi chỉ sao chép nhận xét từ @Joachim! – wildplasser