讓我們假設有一個員工ADT，例如
//employee.h
typedef struct employee_t employee_t;
employee_t* employee_create(char* company, char* department, char* position);
void employee_free(employee_t* me);
，客戶端代碼將是
#include "employee.h"
employee_t* Kevin = employee_create("Facebook", "Marketing", "Sales");
employee_t* John = employee_create("Microsoft", "R&D", "Engineer");
現在客戶想要使用串列 ADT 插入 Kevin 和 John 來列出某些任務。
//list.h
typedef struct list_t list_t;
list_t* list_create(/*might have some arguments*/);
所以客戶端代碼將是
#include "employee.h"
#include "list.h"
employee_t* Kevin = employee_create("Facebook", "Marketing", "Sales");
employee_t* John = employee_create("Microsoft", "R&D", "Engineer");
list_t* employee = list_create(/*might have some arguments*/);
list_insert(employee, Kevin);
list_insert(employee, John);
employee_free(Kevin);
employee_free(John);
list_print(employee); //Oops! How to print structure that you can't see?
因為employee是用opaque指標封裝的，list沒有辦法復制它。
如何為串列撰寫ADT和實作？
uj5u.com熱心網友回復：
執行此操作的常用方法是讓您的串列結構將資料存盤為void*. 例如，假設您的串列是一個單向鏈表：
struct list_t
{
void *data;
struct list_t *next;
};
現在list_insert應該是這樣的：
list_t *list_insert(list_t *head, void *data)
{
list_t *newHead = (list_t*)malloc(sizeof(list_t));
newHead->data;
newHead->next = head;
return newHead;
}
如果你想隱藏結構的實作，那么你可以添加方法來提取資料。例如：
void *list_get_data(list_t *head)
{
return head->data;
}
uj5u.com熱心網友回復：
在不知道結構實作的情況下如何撰寫通用串列？
創建抽象處理結構的函式。
如何為串列撰寫ADT和實作？
list_create();需要傳入特定物件型別的輔助函式指標以抽象地執行各種任務。
像這樣的復制函式知道如何復制.
void *employee_copy(const void *emp)list_insert(employee, Kevin);Kevin像這樣的自由函式可以在銷毀或成員一一洗掉時釋放串列。
void employee_free(void *emp)list_uninsert(employee_t)一個列印功能
int employee_print(void *emp)，從而list_print(employee_t)知道如何列印其串列中的每個成員。可能還有其他人。
與其傳入 3 個函式指標，不如考慮傳入struct包含這些指標的 a，那么串列只需要 1 個指標的開銷：list_create(employee_t_function_list)
您正在邁出重寫 C 的第一步
uj5u.com熱心網友回復：
您可以使用稱為侵入式串列的東西。這個概念在 Linux 內核中被大量使用。您所需要做的就是將節點嵌入到結構體中，并讓通用代碼僅對這個結構體成員進行操作。
#include <stddef.h>
struct list_node {
struct list_node *next;
};
struct list_head {
struct list_node *first;
};
/* translates pointer to a node to pointer to containing structure
* for each pointer `ptr` to a `struct S` that contain `struct list_node node` member:
* list_entry(&ptr->node, S, node) == ptr
*/
#define list_entry(ptr, type, member) \
(type*)((char*)ptr - offsetof(type, member))
void list_insert(struct list_head *head, struct list_node *node) {
node->next = head->first;
head->first = node;
}
#define LIST_FOREACH(it, head) \
for (struct list_node *it = (head)->first; it; it = it->next)
該界面可以通過其他助手輕松擴展，例如list_is_empty, list_first, list_remove_first, embed size to struct list_head.
示例用法：
typedef struct {
char *name;
struct list_node node;
} employee_t;
typedef struct {
char *name;
struct list_head employees;
} employer_t;
employer_t company = { .name = "The Company" };
employee_t bob = { .name = "Bob" };
employee_t mark = { .name = "Mark" };
list_insert(&company.employees, &bob.node);
list_insert(&company.employees, &mark.node);
printf("Employees of %s:\n", company.name);
LIST_FOREACH(n, &company.employees) {
employee_t *e = list_entry(n, employee_t, node);
printf("%s\n", e->name);
}
印刷：
Employees of The Company:
Mark
Bob
請注意，該list_*介面也可以輕松用于其他型別。
有關將此概念用于雙鏈表的更多資訊，請參閱文章。
編輯
Note that list_entry invokes a subtle Undefined Behavior.
It is related to performing pointer arithmetics outside of the struct member object but still within a parent object.
Note that any objects can be treated as an array of chars.
This code will work on all major compilers and it very unlikely to ever fail because it would break a lot of existing and heavily used code (like Linux kernel or Git).
This program is strictly conforming if struct node is a first member of the embedding struct because C standard allows safe conversion between any structure and its first member.
To be strictly conforming if node is not a first member,
The issue could be circumvented by forming a pointer to struct list_node not as &bob.node but rather using a pointer arithmetics on a pointer to bob. The result would be:
(struct list_node*)((char*)&bob offsetof(employee_t, node))
However, this syntax is really nasty, so personally I would go for &bob.node.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/331913.html
下一篇：С條件型別轉換