2013-04-11 36 views
5

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.

Trả lời

3

Dưới đây là phiên bản đơn giản của @Joachim:

void insert(struct PCB **head, const int reg1, const int reg2) 
{ 
    struct PCB *new ; 
     /* Find the insertion point */ 
    for (  ;*head; head = & (*head)->next) 
    { 
     if ((*head)->reg1 > reg1) break; 
    } 

    new = malloc(sizeof *new); 
    new->reg1 = reg1; 
    new->reg2 = reg2; 
    new->next = *head; 
    *head = new; 
} 

Các ý tưởng rất đơn giản: không cần bất kỳ trường hợp đặc biệt nào, trong mọi trường hợp: cần thay đổi con trỏ, đây có thể là con trỏ gốc hoặc con trỏ đuôi hoặc một số con trỏ ở phần giữa của LL. Trong bất kỳ/tất cả các trường hợp:

  • nút mới thực sự đánh cắp con trỏ này:
  • nó làm cho nó điểm mà tại tự
  • thông qua giá trị trước đó như là một kế (gán nó vào con trỏ ->next của nó.
+0

cái này hoạt động chính xác! cảm ơn bạn! – Jakemmarsh

+0

Nhưng Hey, tôi chỉ sao chép nhận xét từ @Joachim! – wildplasser

6

Cách "tốt nhất" có thể là triển khai chức năng mới để chèn. Hàm này sẽ lặp lại trong danh sách cho đến khi nó tìm thấy một nút có giá trị nút next nhỏ hơn hoặc bằng nút bạn muốn chèn, sau đó đặt nút mới trước nút next.


Làm thế nào về chức năng này:

void insert(struct PCB **head, const int reg1, const int reg2) 
{ 
    struct PCB *node = malloc(sizeof(struct PCB)); 
    node->reg1 = reg1; 
    node->reg2 = reg2; 
    node->next = NULL; 

    if (*head == NULL) 
    { 
     /* Special case, list is empty */ 
     *head = node; 
    } 
    else if (reg1 < (*head)->reg1) 
    { 
     /* Special case, new node is less than the current head */ 
     node->next = *head; 
     *head = node; 
    } 
    else 
    { 
     struct PCB *current = *head; 

     /* Find the insertion point */ 
     while (current->next != NULL && reg1 < current->next->reg1) 
      current = current->next; 

     /* Insert after `current` */ 
     node->next = current->next; 
     current->next = node; 
    } 
} 

Bạn sẽ gọi nó là như thế này:

insert(&root, rand() % 100, 0); 
+0

nhưng sau đó tôi không cần một liên kết kép để có thể nhận được các nút cả trước và sau khi tôi sẽ chèn vào đâu? – Jakemmarsh

+1

Không cần. Khi bạn đang nhìn vào một nút, cũng nhìn vào nút tiếp theo. Vì vậy, đối với mỗi lần lặp, bạn giữ hai tham chiếu: một cho tham chiếu hiện tại mà bạn đang xem và một cho phần tiếp theo trong liên kết. Sau đó, bạn so sánh hai thứ đó với nút bạn đang chèn. – Santa

+0

@Jakemmarsh Không, bởi vì trong vòng lặp, bạn có nút 'current', nhưng bạn so sánh với' current-> next'. Bằng cách này bạn có thể chèn nút mới giữa 'current' và' current-> next'. –

Các vấn đề liên quan