0

假设有一个员工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是用不透明指针封装的，所以list没有办法复制它。

如何为列表编写 ADT 和实现？

4

3 回答 3

1

执行此操作的常用方法是让您的列表结构将数据存储为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;
}
于 2021-10-22T10:37:27.743 回答
0

在不知道结构实现的情况下如何编写通用列表？

创建抽象处理结构的函数。

如何为列表编写 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++ 迈出第一步

于 2021-10-22T11:47:19.490 回答
-4

你可以使用一种叫做侵入式列表的东西。这个概念在 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_*接口也可以轻松用于其他类型。

有关将此概念用于双链表的更多信息，请参阅文章。

编辑

请注意，这会list_entry调用一个微妙的未定义行为。它与在结构成员对象之外但仍在父对象内执行指针算术有关。请注意，任何对象都可以被视为chars 的数组。

这段代码适用于所有主要的编译器，而且它不太可能失败，因为它会破坏许多现有的和大量使用的代码（如 Linux 内核或 Git）。

该程序严格符合 ifstruct node是嵌入结构的第一个成员，因为 C 标准允许在任何结构与其第一个成员之间进行安全转换。

为了严格遵守 ifnode不是第一个成员，可以通过形成指向struct list_nodenot as的指针，&bob.node而是在指向 的指针上使用指针算术来规避该问题bob。结果将是：

(struct list_node*)((char*)&bob + offsetof(employee_t, node))

但是，这种语法真的很讨厌，所以我个人会选择&bob.node.

于 2021-10-22T10:45:08.007 回答