Danh sách liên kết chứa các danh sách được liên kết khác & miễn phí

Question

Tôi có danh sách liên kết chung được thực hiện với cấu trúc nút chứa dấu * cho dữ liệu và cấu trúc danh sách chứa tham chiếu đến đầu. Bây giờ, đây là vấn đề của tôi, một nút trong danh sách liên kết có thể chứa một tham chiếu đến một danh sách liên kết khác thông qua khoảng trống của nó *. Điều này gây ra rò rỉ bộ nhớ khi tôi giải phóng danh sách lớn hơn chứa danh sách nhỏ hơn. Vì vậy, tôi tự hỏi là có một cách để kiểm tra xem void * là trỏ đến danh sách khác vì vậy tôi làm theo và miễn phí mà còn hoặc chỉ là dữ liệu.

Nếu tôi thêm khóa vào đầu cấu trúc của mình, số ma thuật mà tôi có thể kiểm tra bằng cách hủy đăng ký void * và tìm ra đây là danh sách?

EDIT: Người gọi không chèn các danh sách nhỏ hơn mà chúng được chèn vào bởi các hàm của tôi. Tôi không muốn người gọi xử lý việc xóa nhiều danh sách chỉ với danh sách mà họ giữ con trỏ.

Answer 1

Câu hỏi này thực sự phụ thuộc vào trách nhiệm của người đó là dọn dẹp các mục trong danh sách. Nếu cấu trúc của bạn có trách nhiệm làm sạch bộ nhớ được tham chiếu bởi các trường void *, thì bạn có một vấn đề lớn hơn nhiều ở đây, cụ thể là việc đưa ra một số khối bộ nhớ tùy ý bạn không bao giờ biết được cách đúng đắn để giải quyết nó là gì . Ví dụ: nếu bạn có triển khai mảng động dọc theo các dòng của C++ std::vector thì void * của bạn có thể trỏ đến cấu trúc có chứa con trỏ và danh sách của bạn sẽ cần phải biết rằng nó phải đi vào cấu trúc đó đệ quy miễn phí khối phân bổ động của nó. Trường hợp bạn mô tả, nơi bạn đang rò rỉ một danh sách lồng nhau - chỉ là một trường hợp đặc biệt của vấn đề tổng quát hơn này.

Nếu, mặt khác, danh sách không chịu trách nhiệm làm sạch bộ nhớ được tham chiếu bởi các cửa hàng của void *, sau đó bạn không nên lo lắng về vấn đề này cả.

Nếu danh sách của bạn có ngữ nghĩa quyền sở hữu và được yêu cầu dọn dẹp bộ nhớ cho các phần tử được lưu trữ trong đó, tôi sẽ không khuyến khích bạn sử dụng số ma thuật để xác định xem bạn có danh sách lồng nhau hay không. Thay vào đó, bạn có lẽ nên có máy khách cung cấp cho bạn một con trỏ hàm chứa một thường trình deallocation để chạy trên các phần tử được chèn vào danh sách. Bằng cách đó, mã của bạn có thể sử dụng mã dọn dẹp được cung cấp của người dùng để đảm bảo rằng mọi thành phần được lưu trữ trong danh sách đều được dọn sạch.

Answer 2

Nó không chỉ là void* của bạn có thể trỏ đến một danh sách. Nó có thể trỏ đến bất kỳ bộ nhớ được cấp phát động nào.

Cách GLib xử lý vấn đề này là để nói rằng đó là trách nhiệm của người gọi để đảm bảo rằng bất cứ điều gì được chỉ định bởi void *data của danh sách được giải phóng. Xem http://library.gnome.org/devel/glib/unstable/glib-Doubly-Linked-Lists.html#g-list-free.

Phương án thay thế (mà GLib cung cấp) là tạo một hàm nhận con trỏ hàm và gọi trên mỗi void *data khi nó di chuyển qua danh sách. Tra cứu g_list_free_full.

Answer 3

Lời khuyên của tôi sẽ là nếu có thể đơn giản hóa mọi thứ một chút và chỉ cần đảm bảo rằng một danh sách được liên kết chỉ chứa một loại đối tượng.

Nếu bạn không thể làm điều đó, tôi có thể có mỗi nút trong danh sách không chỉ giữ một số dữ liệu, mà còn là một con trỏ tới một hàm biết cách giải phóng các mục của loại đó. Chắc chắn, hai tuần sau khi bạn viết mã đặc biệt của bạn cho một danh sách liên kết, bạn sẽ quyết định bạn cũng cần một số ma thuật khác để có thể giữ một mảng động, v.v.

Answer 4

Để trả lời câu hỏi về sự khôn ngoan của "Nếu tôi thêm chìa khóa vào đầu cấu trúc của tôi một số ma thuật mà tôi có thể kiểm tra bằng cách hủy đăng ký void * và tìm ra đây là danh sách?"

Có, bạn có thể thực hiện việc này, nhưng ít người sẽ giới thiệu. Chỉ cần thực sự là chắc chắn rằng giá trị 'ma thuật' không thể xảy ra nếu không. Đó là một yêu cầu khá lớn. Bạn muốn xem xét những gì khác bạn có thể được trỏ đến và những giá trị nó có thể mất khi đại diện như một cái gì đó giống như một số nguyên unsigned. Hãy nhớ rằng nếu bạn quyết định đó là một danh sách, bạn sẽ giải phóng nó và do đó có khả năng sẽ bị lỗi và ghi nếu bạn sai.

Giải pháp hiệu quả đơn giản nhất là nếu bạn cần một Nút để biết rằng nó trỏ đến danh sách, hãy cung cấp cờ trong nút nói như vậy.

Nếu bạn thực sự muốn danh sách sở hữu trách nhiệm giải phóng tất cả nội dung của nó, bạn cần nhiều hơn một lá cờ, bạn cần biết cách làm miễn phí. Đó có thể là một id hoặc một cái gì đó giống như một con trỏ đến hàm giải phóng nội dung của nó.