c - 如何在C中访问指针到指针的值？

Question

我正在编写一个程序，试图用 C 语言实现哈希表。它必须使用指向指针的指针作为结构数据类型中的属性。这是相关结构的代码。

      struct node {
      char * data;
      struct node * next;
    };

    struct hashtable {
      int size;
      struct node ** table;
    };

问题的第一部分:

我一直在做大量的研究来弄清楚指向指针的指针是如何工作的，但我似乎仍然无法理解它。我发现的每个示例都为第一个和第二个指针分配了两个不同的指针名称。例如

  x = 5;
  *p = &x;
  **q = &p; 

上面的例子“struct node ** table;”怎么样？在这种情况下 ** table 与 **q 相同吗？在这种情况下， q 、 *q 和 **q 的值是什么？ q = 5 然后 *q 和 **q 通过地址返回，还是 **q = 5 并且 *q 和 q 存储地址？

问题的第二部分:

如何访问另一个函数中的指针？这是我现在的代码。

struct hashtable * hashtable_new(int size){

    struct hashtable *newTable;

    if ( size < 1 )
    {
        return NULL;
    printf("Its returning Null.");
    }
    else
    {
        newTable = malloc(sizeof(struct hashtable));
        newTable -> size = size;
        newTable -> table = malloc(sizeof(struct node) * size);
        int i;
        for (i = 0; i < size; i++ )
        {

            newTable -> table[i] = NULL;
        }
    fprintf(stderr, "Table has been created.");
        return newTable;
    }

};

我不确定我是否理解如何通过 -> 符号访问指针或指向指针的指针。是“newtable -> table”还是“newtable -> -> table”？

该表的目标本质上是成为一个二维表，其中列表主要是一维的，并且可以扩展到二维以处理散列中的冲突。

尾注:

希望我已经提供了足够的信息来使提出这个问题具有上下文意义。这是我第一次在 stackoverflow 上问问题，所以请随时问我额外的问题，提供抄送或标记我在问这个问题时犯的任何错误。

谢谢!

Answer 1

有多种方法可以查看指向指针的指针。一种方法正如您所描述的

int   x =  5;
int  *p = &x;
int **q = &p; 

毕竟，以下内容都是正确的:

**q == *p ==  x == 5
 *q ==  p == &x
  q == &p

但是，查看指向指针的指针的另一种方法是将其视为指针的数组。例如，假设声明:

int *arr[10];

除非它是 sizeof 或一元 & 操作数的操作数，否则表达式 arr 将从键入“int * 的 10 元素数组”到“指向 int * 的指针”，或 int **。

如果您想动态分配一个指向结构节点的N元素数组，您可以编写

struct node **arr = malloc( sizeof *arr * N );

您可以使用 [] 下标运算符来访问 arr 中的元素，就像访问普通数组一样。由于 arr 具有类型 struct node **，因此每个 arr[i] 具有类型 struct node *，因此您将像这样访问结构的成员:

arr[i]->data = "foo"; // use -> when the LHS is a pointer to a struct or union
arr[i]->next = NULL;

struct hashtable 允许您创建多个哈希表实例，每个实例都有一个 size 成员和一个 struct node * 数组，其中您在运行时分配，如下所示:

struct hashtable h1;

h1.size = 512;
h1.table = calloc( h1.size, sizeof h1.table ); // calloc initializes all elements of
                                               // h1.table to NULL
if ( !h1.table )
{
  // calloc call failed, handle as appropriate
}

您可以像这样在表中插入一个新元素:

/**
 * Assumes we know that the string data points to is not already in
 * the table.  hashfunc is a pointer to the hashing function.
 */
void insert( struct hashtable *h, const char *data, size_t (*hashfunc)(const char *))
{
  /**
   * Create a new table entry.  Remember that table is an array of
   * *pointers* to struct node, and that each array element is initially
   * NULL.  We still need to allocate something for that table entry
   * to point *to*.
   */
  struct node *newNode = malloc( sizeof *newNode );
  if ( !newNode )
  {
    /**
     * Memory allocation for new node failed, handle as appropriate
     */
  }

  newNode->data = malloc( strlen( data ) + 1 );
  strcpy( newNode->data, data );

  /**
   * Get the table index by computing the hash and modding against the
   * table size.
   */
  size_t idx = hashfunc( data ) % h->size;

  /**
   * Insert newNode at the head of the list starting at
   * h->table[idx].  In reality you'd probably want to insert 
   * strings in order, but for a toy example this is good enough.
   */
  newNode->next = h->table[idx]; // newNode->next points to the previous head of list
  h->table[idx] = newNode;       // newNode becomes new head of list.
}

完成后，您的哈希表如下所示:

    +---+
h1: |   | size
    +---+             +---+     +---+---+     +---+---+
    |   | table ----> |   | --> |   |   | --> |   |   |
    +---+             +---+     +---+---+     +---+---+
                      |   | 
                      +---+     +---+---+
                      |   | --> |   |   |
                      +---+     +---+---+     +---+---+     +---+---+
                      |   | --> |   |   | --> |   |   | --> |   |   |
                      +---+     +---+---+     +---+---+     +---+---+
                       ...

table指向一个struct node *数组，其中每个都可以指向struct node的一个实例，每个都可以指向结构节点的另一个实例。上图中，两个字符串已经哈希到table[0]，一个到table[2]，三个到table[3]。