2

我在 C 中有一个字符串数组和一个整数，表示数组中有多少个字符串。

char *strarray[MAX];  
int strcount;

在这个数组中，最高索引（其中 10 高于 0）是最近添加的项目，最低索引是最远添加的项目。数组中项目的顺序很重要。

我需要一种快速的方法来检查数组的重复项，删除除最高索引之外的所有重复项，然后折叠数组。

例如：

strarray[0] = "Line 1"; 
strarray[1] = "Line 2"; 
strarray[2] = "Line 3"; 
strarray[3] = "Line 2"; 
strarray[4] = "Line 4";

会成为：

strarray[0] = "Line 1"; 
strarray[1] = "Line 3"; 
strarray[2] = "Line 2"; 
strarray[3] = "Line 4";

原始数组的索引 1 被删除，索引 2、3 和 4 向下滑动以填补空白。

我对如何做到这一点有一个想法。它未经测试，我目前正在尝试对其进行编码，但仅根据我的模糊理解，我确信这是一个可怕的算法。

每次将新字符串添加到 strarray 时，都会运行下面介绍的算法。

为了表明我正在尝试，我将在下面包含我提出的算法：

  1. 搜索整个 strarray 以匹配 str
  2. 如果没有匹配，什么也不做
  3. 如果找到匹配，将 str 放入 strarray
  4. 现在我们有一个最多包含 1 个重复条目的 strarray
  5. 将最高索引 strarray 字符串添加到临时字符串数组的最低索引
  6. 继续向下进入 strarray 并检查每个元素
  7. 如果发现重复，跳过它
  8. 如果不是，则将其添加到临时字符串数组的下一个最高索引
  9. 反转临时字符串数组并复制到 strarray

再一次，这是未经测试的（我现在正在实施它）。我只是希望那里的人会有更好的解决方案。

项目的顺序很重要，代码必须使用 C 语言（不是 C++）。应删除最低索引重复项并保留单个最高索引。

谢谢！

4

4 回答 4

3

典型的高效独特功能是：

  1. 对给定的数组进行排序。
  2. 验证是否设置了相同项目的连续运行，以便只剩下一个。

我相信你可以qsort结合使用strcmp来完成第一部分；不过，写一个高效的remove东西就靠你了。

不幸的是，我在这里没有具体的想法；这对我来说是一个灰色地带，因为我通常使用 C++，这很简单：

std::vector<std::string> src;
std::sort(src.begin(), src.end());
src.remove(std::unique(src.begin(), src.end()), src.end);

我知道你不能使用 C++，但实现应该基本相同。

因为你需要保存原始订单，你可以有类似的东西：

typedef struct
{
    int originalPosition;
    char * string;
} tempUniqueEntry;

对 进行第一次排序string，删除排序集中的唯一元素集，然后对 进行排序originalPosition。这样，您仍然可以获得 O(n lg n) 性能，但不会丢失原始顺序。

EDIT2：简单的 C 实现示例std::unique：

tempUniqueEntry* unique ( tempUniqueEntry * first, tempUniqueEntry * last )
{
  tempUniqueEntry *result=first;
  while (++first != last)
  {
    if (strcmp(result->string,first->string))
      *(++result)=*first;
  }
  return ++result;
}
于 2010-08-01T06:00:13.797 回答
1

你能在输入进入数组时控制它吗？如果是这样，只需执行以下操作：

int addToArray(const char * toadd, char * strarray[], int strcount)
{
    const int toaddlen = strlen(toadd);

    // Add new string to end.
    // Remember to add one for the \0 terminator.
    strarray[strcount] = malloc(sizeof(char) * (toaddlen + 1));
    strncpy(strarray[strcount], toadd, toaddlen + 1);

    // Search for a duplicate.
    // Note that we are cutting the new array short by one.
    for(int i = 0; i < strcount; ++i)
    {
        if (strncmp(strarray[i], toaddlen + 1) == 0)
        {
            // Found duplicate.
            // Remove it and compact.
            // Note use of new array size here.  
            free(strarray[i]);
            for(int k = i + 1; k < strcount + 1; ++k)
                strarray[i] = strarray[k];

            strarray[strcount] = null;
            return strcount;
        }
    }

    // No duplicate found.
    return (strcount + 1);
}

您始终可以使用上述函数循环现有数组的元素，构建一个没有重复的新数组。

PS：如果你经常做这种类型的操作，你应该远离数组作为你的存储结构，而使用链表。它们对于从末端以外的位置删除元素的效率要高得多。

于 2010-08-01T06:07:43.133 回答
1

我不太了解您提出的算法（我不明白在步骤 5 中将字符串添加到索引中意味着什么），但我会做的是：

unsigned int i;
for (i = n; i > 0; i--)
{
    unsigned int j;

    if (strarray[i - 1] == NULL)
    {
        continue;
    }

    for (j = i - 1; j > 0; j--)
    {
        if (strcmp(strarray[i - 1], strarray[j - 1]) == 0)
        {
            strarray[j - 1] = NULL;
        }
    }
}

然后你只需要从你的数组中过滤出空指针（我将作为练习留下）。

一种不同的方法是在数组上向后迭代，并将每个项目插入到（平衡的）二叉搜索树中。如果该项已经在二叉搜索树中，则标记数组项（例如将数组元素设置为NULL）并继续。处理完整个数组后，像以前一样过滤掉标记的元素。这将有更多的开销并且会消耗更多的空间，但它的运行时间将是 O(n log n) 而不是 O(n^2)。

于 2010-08-01T06:28:55.283 回答
0

使用算法对数组进行排序qsort（man 3 qsort在终端中以查看应如何使用），然后使用该函数strcmp比较字符串并查找重复项

如果您想保持原始顺序，您可以使用嵌套两个的 O(N^2) 复杂度算法for，第一个每次选择一个元素进行比较，第二个 for 将用于扫描数组的其余部分以查找所选元素是否重复。

于 2016-04-26T12:41:11.440 回答