Danh sách liên kết đôi trong C++

Question

Tôi có một bài tập yêu cầu chúng tôi triển khai lớp danh sách được liên kết kép. Đối với một số lý do họ định nghĩa nút struct như sau:

struct node { 
    node *next; 
    node *prev; 
    T  *o; 
}; 

Dường như với tôi rằng nó sẽ dễ dàng hơn rất nhiều để viết lớp nếu hội viên struct 'dữ liệu' không phải là một con trỏ. Không cần phải nói rằng tôi không thể thay đổi nó vì vậy tôi sẽ phải làm việc xung quanh nó. Tôi đã cố gắng thực hiện các phương pháp mà thêm phần tử vào đầu danh sách như sau:

template <typename T> 
void Dlist<T>::insertFront(T *o) { 
    node *np = new node; 
    T val = *o; 

    np->o = &val; 
    np->prev = NULL; 
    np->next = first; 

    if (!isEmpty()) { 
     first->prev = np; 
    } else { 
     last = np; 
    } 
    first = np; 
} 

khi sử dụng đđ để gỡ lỗi tôi nhận ra rằng tất cả mọi thứ hoạt động tốt lần đầu tiên bạn chèn một số nhưng lần thứ hai xung quanh tất cả mọi thứ được screwed up kể từ khi bạn đặt 'val' thành phần tử mới, nó sẽ "ghi đè" cái đầu tiên kể từ khi địa chỉ bộ nhớ của val được sử dụng. Tôi đã thử làm những việc khác như thay vì chỉ có biến 'val' thực hiện như sau:

T *valp = new T; 
T val; 
valp = &val; 
val = *o; 

np->o = valp 

Điều này dường như không hoạt động. Tôi nghĩ rằng điều này là bởi vì nó khá nhiều chỉ là một hình thức phức tạp hơn những gì tôi đã làm ở trên chỉ với một rò rỉ bộ nhớ bổ sung :)

Bất kỳ ý tưởng/con trỏ đi đúng hướng sẽ là tuyệt vời.

Answer 1

số T val bạn tạo là biến tự động. Lỗi của bạn là lưu địa chỉ vào biến ngăn xếp đó.

Bạn nên sử dụng new để phân bổ dung lượng trên heap, như bạn nghi ngờ, nhưng con trỏ dữ liệu của bạn cần trỏ trực tiếp đến địa chỉ được trả về new.

sai lầm của bạn trong nỗ lực mới nhất của bạn là ở đây:

valp = &val; 

Bạn đang thay đổi valp để điểm ở một nơi khác (địa chỉ của val), khi bạn đang có khả năng cố gắng để dữ liệu bản sao val của, không địa chỉ của nó.

Dữ liệu được truyền cho chức năng của bạn phải được sao chép sang bộ nhớ mới nơi valp điểm.

Answer 2

T val = *o; 

    np->o = &val; 

Phần này là đáng ngờ. Gợi ý là bộ nhớ được cấp phát trên ngăn xếp trong một hàm sẽ không có sẵn khi chức năng này nằm ngoài phạm vi.

Answer 3

Tôi không nghĩ rằng bạn nên làm điều này:

T val = *o; 

Kể từ khi o thành viên trong cơ cấu nút là một con trỏ, và tham số để insertFront cũng là một con trỏ, giảng viên của bạn có thể có ý định cho bạn để lấy con trỏ bạn đã cho và lưu nó trong danh sách, không tạo bản sao của đối tượng và lưu con trỏ vào đó. Chỉ cần lưu con trỏ o được chuyển vào insertFront làm thành viên o của nút và bạn sẽ không sao.

Answer 4

Mã của bạn không phù hợp với định nghĩa của bạn về node - trong node bạn đang xác định một thành viên data, nhưng trong mã của bạn, bạn đang sử dụng o để thay thế.

Trong mọi trường hợp, bạn sẽ phải thực hiện hai phân bổ động để thêm mỗi nút - một nút cho chính nút đó và một cho đối tượng dữ liệu mà nó trỏ đến. Khi bạn phân bổ đối tượng dữ liệu đó, bạn cũng có thể chỉ định giá trị trả lại từ new trực tiếp đến con trỏ trong nút của bạn. Sau đó, bạn sẽ cần phải sao chép đối tượng dữ liệu có con trỏ được truyền vào đối tượng dữ liệu mà bạn vừa chỉ định, con trỏ trong nút trỏ đến.

Answer 5

Bạn nghĩ rằng tải trọng con trỏ là bất tiện. Nhưng có lẽ danh sách có nghĩa là để được sử dụng để tạo ra một liên kết trên đầu trang của đối tượng hiện có, như trong:

struct A { int i; }; 
A as[10] = { 1,2,3,4,5,6,7,8,9,10 }; 

LinkedList primes_in_my_data; 
insertFront(primes_in_my_data, &as[1]); 
insertFront(primes_in_my_data, &as[2]); 
insertFront(primes_in_my_data, &as[3]); 
insertFront(primes_in_my_data, &as[5]); 
insertFront(primes_in_my_data, &as[7]); 

// now I have a linked list of primes, and caused no extra memory allocation 
// (except for the list overhead)