Thực hiện thanh lịch danh sách liên kết đơn lẻ trong C?

Question

Đi qua các cấu trúc dữ liệu cổ điển và đã dừng lại trên danh sách được liên kết. Chỉ cần triển khai danh sách liên kết đơn lẻ tròn, nhưng tôi bị ấn tượng quá mức rằng danh sách này có thể được thể hiện một cách thanh lịch hơn, đặc biệt là chức năng remove_node. Lưu ý hiệu quả và khả năng đọc mã, có ai có thể trình bày giải pháp ngắn gọn và hiệu quả hơn cho danh sách vòng tròn đơn lẻ không?

#include <stdio.h> 
#include <stdlib.h> 


struct node{ 
    struct node* next; 
    int value; 
}; 


struct list{ 
    struct node* head; 
}; 


struct node* init_node(int value){ 
    struct node* pnode; 
    if (!(pnode = (struct node*)malloc(sizeof(struct node)))){ 
     return NULL; 
    } 
    else{ 
     pnode->value = value; 
    } 
    return pnode; 
} 

struct list* init_list(){ 
    struct list* plist; 
    if (!(plist = (struct list*)malloc(sizeof(struct list)))){ 
     return NULL;   
    } 
    plist->head = NULL; 
    return plist; 
} 


void remove_node(struct list*a plist, int value){ 

    struct node* current, *temp; 
    current = plist->head; 
    if (!(current)) return; 
    if (current->value == value){ 
     if (current==current->next){ 
      plist->head = NULL; 
      free(current); 
     } 
     else { 
      temp = current; 
      do {  
       current = current->next;  
      } while (current->next != plist->head); 

      current->next = plist->head->next; 
      plist->head = current->next; 
      free(temp); 
     } 
    } 
    else { 
     do { 
      if (current->next->value == value){ 
       temp = current->next; 
       current->next = current->next->next; 
       free(temp); 
      } 
      current = current->next; 
     } while (current != plist->head); 
    } 
} 

void print_node(struct node* pnode){ 
    printf("%d %p %p\n", pnode->value, pnode, pnode->next); 
} 
void print_list(struct list* plist){ 

    struct node * current = plist->head; 

    if (!(current)) return; 
    if (current == plist->head->next){ 
     print_node(current); 
    } 
    else{ 
     do { 
      print_node(current); 
      current = current->next; 

     } while (current != plist->head); 
    } 

} 

void add_node(struct node* pnode,struct list* plist){ 

    struct node* current; 
    struct node* temp; 
    if (plist->head == NULL){ 
     plist->head = pnode; 
     plist->head->next = pnode; 
    } 
    else { 
     current = plist->head; 
     if (current == plist->head->next){ 
      plist->head->next = pnode; 
      pnode->next = plist->head;  
     } 
     else { 
      while(current->next!=plist->head) 
       current = current->next; 

      current->next = pnode; 
      pnode->next = plist->head; 
     } 

    } 
} 

Answer 1

Hãy nhìn vào danh sách liên kết hình tròn trong nguồn kernel Linux: http://lxr.linux.no/linux+v2.6.36/include/linux/list.h

vẻ đẹp của nó xuất phát từ thực tế là bạn không có một cấu trúc đặc biệt cho dữ liệu của bạn để phù hợp trong danh sách, bạn chỉ phải bao gồm struct list_head * trong cấu trúc bạn muốn có dưới dạng danh sách. Các macro để truy cập các mục trong danh sách sẽ xử lý phép tính bù trừ để lấy từ con trỏ struct list_head đến dữ liệu của bạn.

Một giải thích chi tiết hơn về danh sách liên kết được sử dụng trong hạt nhân có thể được tìm thấy tại kernelnewbies.org/FAQ/LinkedLists (Xin lỗi, tôi không có đủ nghiệp để đăng hai siêu liên kết).

Chỉnh sửa: Vâng, danh sách là danh sách được liên kết kép chứ không phải danh sách liên kết đơn lẻ như bạn có, nhưng bạn có thể áp dụng khái niệm và tạo danh sách liên kết đơn của riêng bạn.

Answer 2

Một vài ý kiến:

• Tôi nghĩ rằng hàm remove không điều chỉnh một cách chính xác các con trỏ danh sách tròn khi bạn xóa các nút đầu và danh sách là lớn hơn so với 3 yếu tố. Vì danh sách là hình tròn, bạn phải trỏ nút cuối cùng trong danh sách đến đầu mới.
• Bạn có thể rút ngắn chức năng xóa một chút bằng cách tạo chức năng "find_node". Vì danh sách là hình tròn, tuy nhiên, sẽ vẫn có trường hợp cạnh xóa nút đầu sẽ phức tạp hơn trong danh sách không tròn.
• Mã "làm đẹp" nằm trong con mắt của kẻ thù. Như mã đi của bạn là dễ dàng để đọc và hiểu được nhịp đập rất nhiều mã trong tự nhiên.

Answer 3

Xử lý danh sách (đặc biệt là danh sách tròn) dễ dàng hơn khi bạn xử lý đầu danh sách như một phần tử trong danh sách (cái gọi là "sentinel"). Rất nhiều trường hợp đặc biệt chỉ biến mất. Bạn có thể sử dụng một nút giả cho sentinel, nhưng nếu con trỏ tiếp theo là lần đầu tiên trong cấu trúc, bạn không cần phải làm ngay cả điều đó. Bí quyết lớn khác là giữ một con trỏ đến con trỏ tiếp theo của nút trước đó (để bạn có thể sửa đổi nó sau này) bất cứ khi nào bạn sửa đổi danh sách. Kết hợp tất cả lại với nhau, bạn sẽ nhận được điều này:

struct node* get_sentinel(struct list* plist) 
{ 
    // use &plist->head itself as sentinel! 
    // (works because struct node starts with the next pointer) 
    return (struct node*) &plist->head; 
} 

struct list* init_list(){ 
    struct list* plist; 
    if (!(plist = (struct list*)malloc(sizeof(struct list)))){ 
     return NULL;   
    } 
    plist->head = get_sentinel(plist); 
    return plist; 
} 

void add_node_at_front(struct node* pnode,struct list* plist){ 
    pnode->next = plist->head; 
    plist->head = pnode; 
} 

void add_node_at_back(struct node* pnode,struct list* plist){ 
    struct node *current, *sentinel = get_sentinel(plist); 

    // search for last element 
    current = plist->head; 
    while (current->next != sentinel) 
     current = current->next; 

    // insert node 
    pnode->next = sentinel; 
    current->next = pnode; 
} 

void remove_node(struct list* plist, int value){ 
    struct node **prevnext, *sentinel = get_sentinel(plist); 
    prevnext = &plist->head; // ptr to next pointer of previous node 
    while (*prevnext != sentinel) { 
     struct node *current = *prevnext; 
     if (current->value == value) { 
      *prevnext = current->next; // remove current from list 
      free(current); // and free it 
      break; // we're done! 
     } 
     prevnext = &current->next; 
    } 
} 

void print_list(struct list* plist){ 
    struct node *current, *sentinel = get_sentinel(plist); 
    for (current = plist->head; current != sentinel; current = current->next) 
     print_node(current); 
} 

Answer 4

Tôi sử dụng phần sau để tạo danh sách liên kết đơn lẻ. Tất cả nó đòi hỏi là kích thước.

Node* createCircularLList(int size) 
{ 
    Node *it; // to iterate through the LList 
    Node *head; 

    // Create the head /1st Node of the list 
    head = it = (Node*)malloc(sizeof(Node)); 
    head->id = 1; 

    // Create the remaining Nodes (from 2 to size) 
    int i; 
    for (i = 2; i <= size; ++i) { 
     it->next = (Node*)malloc(sizeof(Node)); // create next Node 
     it = it->next;       // point to it 
     it->id = i;        // assign its value/id 
     if (i == 2) 
      head->next = it; // head Node points to the 2nd Node 
    } 
    // close the llist by having the last Node point to the head Node 
    it->next = head; 

    return head; // return pointer to start of the list 
} 

Và tôi xác định Node ADT như vậy:

typedef struct Node { 
    int id; 
    struct Node *next; 
} Node;