arrays - 为什么我要使用数据结构（例如哈希表）而不是数组？

这可能听起来很愚蠢，但我正在尝试制作一个高效的程序（时间/内存方面）

高效的程序做什么？你从来没有真正说出你想要做什么。

研究哈希表我已经看到它基本上是一个链表数组

这是一个常见的实现，但它并没有说明你为什么首先要使用哈希表。

当您基于非数字键（即字符串）搜索记录时，您使用哈希表。您将该键输入到一个散列函数中，该函数会输出一个整数值，然后使用该值对表进行索引。所以如果f("foo")吐出来3，那就是你用来存储数据的表索引和键"foo"。

没有实用的散列函数是完美的，不同的字符串会产生相同的散列值，称为冲突。使用链表是解决冲突的一种方法，其他方法是计算表中的二级索引或只是将 1 添加到返回的索引。

相对于线性或二分搜索，从键计算散列是快速的，与 O(n) 的线性搜索时间和 O(log ₂ n) 的二分搜索时间相比，时间复杂度为 O(1)。权衡是您的表没有以任何方式排序- 线性遍历将出现随机排序。

编辑

来自评论：

我需要将文本保存为一堆行，所以我知道每一行在哪里（第 1 行将是第一行，duh），我似乎没有必要使用哈希表，但问题是我不知道如何它会有很多行，所以如果我制作一个 50 的数组可能还不够，我想知道是使用列表/哈希表/其他一些结构还是只是一个 char 数组的数组更好（也在帖子中添加）

如果您只需要存储一系列字符串，则可以动态分配一个数组，然后根据需要扩展该数组。假设所有行都是已知的固定长度，您可以执行以下操作（将文件读入内存，将内容转储到标准输出）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LENGTH 80

size_t read_arr( FILE *in, char (**arr)[MAX_LENGTH+1] ) 
{
  size_t size = 1;
  size_t read = 0;

  *arr = malloc( sizeof **arr * size );
  if ( !*arr )
  {
    return 0;
  }

  char buf[MAX_LENGTH+1];
  while( fgets( buf, sizeof buf, in ) )
  {
    if ( read == size )
    {
      char (*tmp)[MAX_LENGTH+1] = realloc( *arr, sizeof **arr * (size * 2) );
      if ( tmp )
      {
        *arr = tmp;
        size *= 2;
      }
      else
      {
        fprintf( stderr, "Unable to extend array past %zu entries, returning what we have so far.\n", read );
        return read;
      }
    }
    strcpy( (*arr)[read++], buf );
  }
  return read;
}

int main( int argc, char **argv )
{
  if ( argc < 2 )
  {
    fprintf( stderr, "USAGE: %s <file name>\n", argv[0] );
    return EXIT_FAILURE;
  }

  FILE *in = fopen( argv[1], "r" );
  if ( !in )
  {
    fprintf( stderr, "File %s not found\n", argv[0] );
    return EXIT_FAILURE;
  }

  char (*arr)[MAX_LENGTH+1];
  size_t n = read_arr( in, &arr );

  for ( size_t i = 0; i < n; i++ )
    printf( "%s", arr[i] );

  free( arr );
  return EXIT_SUCCESS;
}

realloc是一项相对昂贵的操作，因此您不想对文件中的每一行都执行此操作。每次将数组加倍可以最大限度地减少调用次数，尽管权衡是内部碎片的可能性（例如，需要 256 行来存储 129 行）。但平均而言，这应该不是问题。

你能告诉我是什么吗char (**arr)[MAX_LENGTH+1]，我从未见过这种结构；它是一个二维数组吗？

是的，我想我应该解释一下。

T (*a)[N];

声明a为指向的 N 元素数组的指针T。type 的表达式T [M][N]将“衰减”为 type T (*)[N]( not T ** )。

我想动态分配足够的空间来存储 M 类型的对象T [N]。所以我们从常见的成语开始

P *p = malloc( sizeof *p * M );

sizeof *p等价于sizeof (P)，因此我们分配了足够的空间来存储 M 类型的对象P。现在我们用数组类型替换P类型，这T [N]给了我们

T (*p)[N] = malloc( sizeof *p * M );

在这种情况下，sizeof *p等价于sizeof (T [N])，因此我们分配了足够的空间来存储的 M 个 N 元素数组T。

由于a[i]定义为*(a + i)，因此以下情况成立：

(*p)[i] == (*(p + 0))[i] == (p[0])[i] == p[0][i]

所以我们可以p像任何其他二维数组一样索引。

所以在上面的main函数中，我声明arr为一个MAX_LENGTH+1指向char. 由于我想read_arr更新存储在arr自身中的值（分配内存的地址），我需要将指针传递给arr. 请记住，如果您希望函数更新其参数之一，则必须将指针传递给该参数¹，即使该参数已经是指针类型。如果的类型arr，char (*)[MAX_LENGTH+1]那么的类型&arr，char (**)[MAX_LENGTH+1]或者“指向指向MAX_LENGTH+1元素数组的指针char”。

同样，这假设文件中的所有行都接近相同的长度，并且它们都小于某个已知的最大长度。如果您有一个文件，其中行的长度差异很大，或者 99% 的行长度为 20，而一两个行的长度为 200，那么您将想做其他事情。

^{数组很奇怪，但在这种情况下，我们处理的不是数组类型，而是指针类型。}

arrays - 为什么我要使用数据结构（例如哈希表）而不是数组？

问题描述

解决方案

推荐阅读