Chức năng thao tác danh sách chung trong C là gì? (Tôi thấy điều này khi tôi xem xét một số tài liệu.)Chức năng thao tác danh sách chung trong C?
Sự khác biệt giữa chức năng này và chức năng có thể chấp nhận các thành phần thuộc loại nào?
Chúng có giống nhau không ...? Làm thế nào chúng ta có thể thực hiện chúng riêng lẻ nếu chúng không giống nhau?
Một danh sách chung có khả năng là đơn lẻ liên kết, và có lẽ giả định rằng các mục trong danh sách có một cấu trúc như thế này:
typedef struct list_item list_item;
struct list_item
{
list_item *next;
...data for node...
};
Sử dụng bố trí này, bạn có thể viết các chức năng để thao tác danh sách chỉ sử dụng các con trỏ tiếp theo.
Đôi khi, '...data for node...' sẽ đơn giản 'void *'; có nghĩa là, các mục danh sách sẽ chứa các con trỏ tới nút tiếp theo trong danh sách (hoặc NULL nếu không có nút tiếp theo) và các con trỏ tới dữ liệu.
typedef struct list list;
struct list
{
list *next;
void *data;
};
Vì bạn có thể bỏ bất kỳ con trỏ đến 'void *', bạn có thể có bất kỳ kết hợp của các kiểu dữ liệu trong danh sách - nhưng mã của bạn phải biết làm thế nào để xử lý chúng.
Bạn hỏi về chức năng danh sách chung 'a', nhưng có lẽ không phải là một thiết kế một chức năng duy nhất, và chắc chắn không phải là một thiết kế đơn giản. Có một số tập hợp hàm có thể có thể làm cho các hàm danh sách chung. Một bộ, lấy cảm hứng từ Lisp, sẽ bao gồm:
void *car(list *lp); // Return the data for the first item on the list
list *cdr(list *lp); // Return the tail of the list
list *cons(list *lp1, list *lp2); // Construct a list from lists lp1 and lp2
list *cond(list *lp, void *data); // Append data item to list
Bạn có thể muốn cung cấp khả năng kiểm tra xem danh sách có trống và một vài mục khác không.
Một giải thích tốt, được thừa nhận trong C++, được tìm thấy trong "Ruminations on C++" của Koenig ". Các ý tưởng có thể được chuyển thể thành C khá dễ dàng - nó không phải là khủng khiếp (mặc dù việc quản lý lưu trữ trong C khó hơn trong C++).
C không có khái niệm về con trỏ hoặc đối tượng "chung" - gần nhất bạn có thể nhận được là sử dụng con trỏ void*. Nếu bạn muốn một đoạn mã để có thể xử lý bất kỳ loại dữ liệu nào, bạn sẽ phải sử dụng các con trỏ void*. Đối với các loại dữ liệu có kích thước không lớn hơn con trỏ, bạn có thể truyền giữa loại và void*; đối với các kiểu dữ liệu lớn hơn, bạn sẽ phải sử dụng bộ nhớ động và có điểm thành viên void* vào bộ nhớ động. Chỉ cần xem ra cho rò rỉ bộ nhớ!
typedef struct list_node {
struct list_node *next;
void *data;
} list_node;
void list_insert(list_node *node, void *data) {
// ...
}
Mặt khác, nếu bạn muốn tạo mã cho mỗi kiểu dữ liệu có thể, bạn sẽ phải làm điều đó với macro, và sau đó nhanh chóng các macro cho mỗi loại dữ liệu bạn có thể sử dụng. Ví dụ:
#define DEFINE_LIST(type) \
typedef struct list_node_##type { \
struct list_node_##type *next; \
type data; \
}
#define IMPLEMENT_LIST_INSERT(type) \
void list_##type##_insert(list_node_##type *node, type data) { \
... \
}
DEFINE_LIST(int); // defines struct list_node_int
DEFINE_LIST(double); // defines struct list_node_double
IMPLEMENT_LIST_INSERT(int); // defines list_int_insert
IMPLEMENT_LIST_INSERT(double); // defines list_double_insert
Các hạt nhân Linux có một thực hiện thú vị của một danh sách liên kết chung trong C trên linux/list.h tiêu đề của nó.Đó là một danh sách gấp đôi liên kết với một nút đầu, được sử dụng như thế này:
struct mystruct {
...
/* Contains the next and prev pointers */
struct list_head mylist;
...
/* A single struct can be in several lists */
struct list_head another_list;
...
};
struct list_head mylist_head;
struct list_head another_list_head;
Một số điều thú vị trong ví dụ nhỏ này:
struct list_head, không cho cấu trúc đích (trên ví dụ trên, chúng trỏ đến &(foo->mylist) cho danh sách thứ nhất và &(foo->another_list) cho danh sách thứ hai).Tất cả các chức năng thao tác trong danh sách đều trỏ đến struct list_head (và hầu hết không quan tâm dù đó là nút đầu riêng biệt hay một trong các nút được nhúng). Để nhận được từ số struct list_head đối với cấu trúc đích, bạn sử dụng macro list_entry (tương tự như macro containter_of từ tiêu đề linux/kernel.h), mở rộng thành phép trừ con trỏ đơn giản.
Vì nó là một danh sách gấp đôi liên kết với một nút đầu, bạn có thể trong O(1):
C và thư viện chuẩn của nó không cung cấp bất kỳ chức năng cụ thể nào của danh sách.
Nhưng có những thư viện với nhiều chức năng hữu ích cho C có hỗ trợ các kiểu dữ liệu được biết đến từ ngôn ngữ lập trình khác: http://library.gnome.org/devel/glib/2.18/glib-data-types.html
Như đã đề cập ở trên, tôi đã cố gắng sử dụng cách tiếp cận macro để tạo ra các chức năng danh sách các thao tác. Dễ dàng tạo quy trình hoạt động INSERT nhưng rất khó để tạo ra các thao tác Xóa và di chuyển. Sau đó cấu trúc danh sách và chữ ký thông thường INSERT:
#define LIST_DEFINE(type) \
struct list_node_##type \
{ \
type *data; \`
struct list_node_##type *next; \
};
LIST_INSERT(&ListHead,&Data, DataType);
đâu:
ListHead - Trưởng danh sách liên kết
Data - Các dữ liệu mà một nút mới sẽ được tạo ra và dữ liệu được chèn vào trong nút DataType - Là loại dữ liệu của dữ liệu được chuyển qua
FYI, tôi cấp phát bộ nhớ trong hàm và sao chép tất cả dữ liệu được chuyển vào nút mới tạo và thêm nút trong danh sách được liên kết.
Bây giờ, khi một thói quen LIST_DELETE được tạo, nút cần xóa sẽ được xác định bằng cách sử dụng số nhận dạng duy nhất trong dữ liệu. Mã định danh đó cũng được chuyển trong quy trình MACRO làm khóa sẽ được thay thế trong phần mở rộng MACRO. Chữ ký thói quen có thể là:
LIST_DELETE(&ListHead, DataType, myvar->data->str, char*);
đâu:
ListHead - Trưởng danh sách liên kết
DataType - Là dữ liệu kiểu của dữ liệu
myvar->data->str - Unique key
char* - loại chính
Bây giờ, khi khóa được mở rộng, bạn không thể sử dụng cùng một khóa đó để so sánh như thể chúng tôi viết
if((keytype)ListHead->data->key == (keytype)key)
Nó mở rộng để
ListHead->data->myvar->data->str == myvar->data->str
Và đây không có biến như: ListHead->data->myvar->data->str
Vì vậy, phương pháp này không thể làm việc để viết xóa thói quen và là traversal và tìm kiếm thói quen cũng sử dụng khóa duy nhất, tương tự vấn đề cũng sẽ phải đối mặt với họ.
Và, trên ghi chú không liên quan, cách xác định logic phù hợp cho khóa duy nhất, vì khóa duy nhất có thể là bất kỳ thứ gì.
Đối với giáo lý của tôi, tôi đã phát triển mô-đun danh sách "chung" này, có thể là phiên bản đơn giản của hạt nhân Linux, có thêm các lỗi chưa được khám phá, và sử dụng phần mở rộng gcc ... Mọi bình luận đều được hoan nghênh!
#ifndef _LISTE
#define _LISTE
#include <stdlib.h>
typedef struct liste_s {
struct liste_s * suivant ;
} * liste ;
#define newl(t) ((liste) malloc (sizeof (struct liste_s) + sizeof (t)))
#define elt(l,t) (* ((t *) (l + 1)))
#define liste_vide NULL
#define videp(l) (l == liste_vide)
#define lvide() liste_vide
#define cons(e,l) \
({ liste res = newl(typeof(e)) ; \
res->suivant = l ; \
elt(res,typeof(e)) = e ; \
res ; })
#define hd(l,t) ({ liste res = l ; if (videp(res)) exit (EXIT_FAILURE) ; elt(res,t) ; })
#define tl(l) ({ liste res = l ; if (videp(res)) exit (EXIT_FAILURE) ; res->suivant ;})
#endif
Tôi đã thử một điều gì đó khác biệt. Đây là quan điểm khác làm thế nào để ban các vấn đề
Nếu chúng ta có cấu trúc sau:
typedef struct token {
int id;
char *name;
struct token *next;
} Token;
và chúng ta cần tạo một hàm trả về đuôi của một danh sách liên kết, nhưng các chức năng nên được chung chung cho bất kỳ danh sách được liên kết nào, vì vậy:
void* tail(void* list, void* (*f)(void *)) {
void *head = list;
while(f(head) != NULL) {
head = f(head);
}
return head;
}
Bây giờ sẽ cần thiết tạo ra cầu nối giữa cấu trúc tùy chỉnh của chúng tôi với tính khả dụng chung trong chức năng đuôi. Bằng cách đó, chúng ta có:
void* nextToken(void *a) {
Token *t = (Token *) t;
return (void *) (a->next);
}
Cuối cùng, chúng tôi chỉ đơn giản là có thể sử dụng:
Token *listTokens;
(...)
Token *lastToken = tail(listTokens, nextToken);