c - c 中具有多维数据类型的多维数组

Question

我必须实现一个奇怪的数据结构。有一个队列，其中包含内存分配(它可能是队列或数组，但不是链表或代码中使用 malloc() 的任何内容)。 我们必须使用这个 body :-

Struct  //we don't have to use pointer in structure in achieving the task
{
int frequency;
unsigned char symbol;
short int left,right;     
}

在这里你可以看到我们在第一个索引处有像a、b、c、d和e这样的字母，它们在第二个索引上的相应频率和其他两个索引目前没有用，但我们必须为其分配内存他们现在。

目前唯一对我们有用的就是第二个索引(即字母的频率)。在这个问题中我要做的是两个添加两个最小频率(我必须将其放在一个地方，以便必须保持递增顺序)例如:您可以在下面看到我们添加前两个节点频率:所以对于第一个索引我们获得“a+b”的结果，假设“z”(a+b=z)，第二个索引(3+3=6)，其他两个索引是“0”和“0”，所以对我们来说没有用。现在我们必须调整获得的内存，使其保持频率递增的顺序

现在的问题是: (1)如何实现这种类型的数据结构有什么想法吗？ (不使用指针、malloc()、链表等)(但可以使用队列/堆栈)，此外我们可以使用 memcpy() 进行移位。 (2)如何在这种情况下实现排序(但这是次要的事情，首先如何实现它？)(很抱歉，我将这个问题标记在可以解决这个问题的主题上，对此感到抱歉) 如果您对这个问题有任何不明白的地方，请随时询问我。

Answer 1

这个结构主要用于搜索还是存储？您会不断添加和删除元素，还是会保持相当静态？

假设我理解这个问题(无法保证)，听起来最简单的方法是使用结构的常规数组类型¹:

struct afreq {
  int freq;
  unsigned char sym;      // why unsigned? why not just plain char?
  short int left,right;
};

...
struct afreq data[N]; // where N is large enough for as many elements
                      // as you need
size_t dataSize;

根据需要使用qsort库函数对数组进行排序。您必须编写一个比较函数来传递给 qsort:

int cmpAfreq( const void *lhs, const void *rhs )
{
  const struct afreq *l = lhs;
  const struct afreq *r = rhs;

  if ( l->freq < r->freq ) return -1;
  if ( l->freq > r->freq ) return 1;
  return 0;
}

因此，假设您从以下内容开始:

struct afreq data[N] = { {3, 'a', 0, 0 }, {3, 'b', 0, 0}, {4, 'c', 0, 0 },
                         {6, 'd', 0, 0 }, {9, 'e', 0, 0} };
size_t dataSize = 5;

您可以像这样添加一个新元素:

struct afreq newItem;
newItem.freq = data[i].freq + data[j].freq;
newItem.sym = 'z';
newItem.left = newItem.right = 0;

if ( dataSize < N )
{
  data[dataSize++] = newItem;
  qsort( data, dataSize, sizeof data[0], cmpAfreq );
}
else
{
  // data array is full, can't add another element
}

要从数组中删除一个元素，您可以用最后一个元素覆盖要删除的元素，将计数器减 1，然后对数组重新排序:

data[i] = data[dataSize--];
qsort( data, dataSize, sizeof data[0], cmpAfreq );

这绝不是高效；每次添加或删除数据时都必须对数组进行完全重新排序，成本高昂(尤其是在已经大部分排序的数组上，qsort 的性能很差)。但这可能是我能想到的最简单的实现。

---

^{1.实际上，听起来最简单的方法是使用 C++ 或 Java 或 Python 等语言，或者任何其他提供 map 或类似容器的语言，关键是您的sym 成员}