Mã C cho danh sách liên kết XOR

Question

Tôi đã cố gắng triển khai XOR linked list và các hoạt động của nó nhưng tôi đã không thể thực hiện đúng cách.

Có thể triển khai trong C kể từ khi danh sách liên kết XOR liên quan đến các thao tác trên địa chỉ không?

Tôi sẽ rất biết ơn nếu một số mã làm việc thực tế được đưa ra.

Answer 1

Đó là một ý tưởng thú vị mà tôi chưa từng thấy trước đây. Với bộ nhớ khá phong phú ngày nay, nó có vẻ như rất nhiều phức tạp để đạt được ít (mặc dù không phải tất cả các nền tảng được tuôn ra với bộ nhớ). Chỉnh sửa Trong khi thực hiện công việc thực sự của tôi, tâm trí của tôi tiếp tục trôi trở lại nó, vì vậy tôi đã thêm chức năng để tạo nút mới và đặt nó vào đầu đã cho. Đẹp hơn bây giờ. Nó khá mát mẻ rằng cả hai addnode và các chức năng đi ngang là đối xứng. Không cần phải biết hướng. Chỉ cần cung cấp cho nó một đầu của danh sách và họ hoạt động chính xác.

Và dựa trên nhận xét của Darron (cảm ơn), tôi đã thay đổi int thành intptr_t cho tính di động.

#include <stdio.h> 
#include <malloc.h> 
#include <stdint.h> // gcc needs this for intptr_t. 

typedef struct xorll { 
    int value; 
    struct xorll *np; 
} xorll; 


// traverse the list given either the head or the tail 
void traverse(xorll *start) // point to head or tail 
{ 
    xorll *prev, *cur; 

    cur = prev = start; 
    while (cur) 
     { 
     printf("value = %d\n", cur->value); 
     if (cur->np == cur) 
     // done 
     break; 
     if (cur == prev) 
     cur = cur->np; // start of list 
     else { 
     xorll *save = cur; 
     cur = (xorll*)((uintptr_t)prev^(uintptr_t)cur->np); 
     prev = save; 
     } 
     } 
} 

// create a new node adding it to the given end and return it 
xorll* newnode(xorll *prev, xorll *cur, int value) 
{ 
    xorll *next; 

    next = (xorll*)malloc(sizeof(xorll)); 
    next->value = value; 
    next->np = cur; // end node points to previous one 

    if (cur == NULL) 
     ; // very first node - we'll just return it 
    else if (prev == NULL) { 
     // this is the second node (they point at each other) 
     cur->np = next; 
     next->np = cur; 
     } 
    else { 
     // do the xor magic 
     cur->np = (xorll*)((uintptr_t)prev^(uintptr_t)next); 
     } 

    return next; 
} 



int main(int argc, char* argv[]) 
{ 
    xorll *head, *tail; 
    int value = 1; 

    // the first two nodes point at each other. Weird param calls to 
    // get the list started 
    head = tail = newnode(NULL, NULL, value++); 
    tail = newnode(NULL, tail, value++); 

    // now add a couple to the end 
    tail = newnode(tail->np, tail, value++); 
    tail = newnode(tail->np, tail, value++); 

    // this is cool - add a new head node 
    head = newnode(head->np, head, 999); 


    printf("Forwards:\n"); 
    traverse(head); 
    printf("Backwards:\n"); 
    traverse(tail); 


} 

Answer 2

Có thể triển khai trong C kể từ khi danh sách liên kết XOR liên quan đến hoạt động trên địa chỉ không ??

Vâng. Địa chỉ là con trỏ, con trỏ là số * và số cho phép XOR (ví dụ: a^b).

Look upnhững gì được thực hiện và bạn sẽ có thể thực hiện.

* Ít nhất, bạn có thể coi chúng là số - mặc dù phôi có thể được yêu cầu.

Answer 3

Vì bạn không thể thực hiện thao tác xor trên con trỏ, bạn sẽ phải chuyển đổi địa chỉ thành kiểu số nguyên để thực hiện xor và chuyển kết quả trở lại thành kiểu con trỏ bên phải.

Theo như tôi biết C99 chỉ có hai loại nguyên mà đảm bảo chuyển đổi đến và đi từ con trỏ với hành vi được xác định (= nhận được con trỏ gốc của bạn trở lại): intptr_t và uintptr_t từ <stdint.h>. Lưu ý rằng cả hai loại đều là tùy chọn, vì vậy việc triển khai của bạn có thể không có chúng.

Ví dụ về chuyển đổi, giả sử a và b là con trỏ hợp lệ để struct node:

#include <stdint.h> 

/* creating an xor field */ 
uintptr_t x = (uintptr_t) (void *) a^(uintptr_t) (void *) b; 
/* reconstructing an address */ 
a = (void *) (x^(uintptr_t) (void *) b); 

Tôi không chắc chắn 100% các diễn viên phụ để void * là cần thiết, ai đó hãy sửa lại cho tôi nếu họ không. Xem §7.18.1.4 của tiêu chuẩn C99 để biết thêm thông tin về các loại (u)intptr_t.