1

所以我试图删除部分填充数组中的重复字符。该阵列是从位于我的 PC 上的文件中填充的。我的数组填充方法运行良好；但是，我的重复删除方法不是。这是我的方法：

    void deleteRepeated(char array[], int* numberUsed)
{
    for (int x = 0; x < *numberUsed ; x++) 
    {
        cout << "Positions used: " << *numberUsed << endl;
        for (int y = x+1; y < *numberUsed; y++ )
        {
            cout << "Positions used: " << *numberUsed << endl;
            if (array[y] == array[x])
            {
                cout << "Positions used: " << *numberUsed << endl;
                for (int z = y; z < *numberUsed; z++)
                    array[z] = array[z+1];
                y--; 
                *numberUsed--;
                cout << "Positions used: " << *numberUsed << endl;
            }
        }
    }
}

我正在传递整个数组，以及该数组中使用的索引数。数组长度为 10，我的测试中，我使用了 10 个字符中的 6 个字符：{'g'、'g'、'n'、'o'、'r'、'e'}。我究竟做错了什么？

注意： "cout << "Positions used: " << *numberUsed << endl" 用于检查方法是否正确删除。在索引为 z 的最内层循环中，该方法开始变得疯狂。

任何帮助将非常感激。

4

2 回答 2

1

每次找到 dup 时，都会减少使用的字符数

*numberUsed--;

但请记住这个控制第一个循环索引

for (int x = 0; x < *numberUsed ; x++)

所以试试这个

int count =*numberUsed;
for (int x = 0; x < count ; x++)

这样您就可以访问数组中的所有原始字符。

于 2013-02-04T01:16:30.450 回答
1

（在阅读您关于不允许使用 STL 的评论之前，我写了此答案的第一部分，但无论如何我都会留下它，因为我认为这是相当简洁的代码。）

您可以使用 C++ 标准库为您提供的功能。使用std::string而不是 char 数组（这几乎总是一个好主意），然后您可以执行以下操作（注意：C++11 仅因为unordered_setand std::begin）：

#include <string>
#include <unordered_set>
#include <iostream>
#include <iterator>

std::string uniquechars(const std::string& s) {
    std::unordered_set<char> uniquechars(std::begin(s), std::end(s));
    std::string newstring(std::begin(uniquechars), std::end(uniquechars));
    return newstring;
}

int main() {
    std::string teststr("thisisanexamplesentence");
    std::cout << "The unique characters of " << teststr << " are " << uniquechars(teststr) << std::endl;
}

请注意，它不会保留字符的原始顺序，因此如果需要，这不起作用。

如果你必须在没有标准库的情况下工作，你必须更深入地挖掘。上面的@TimChild 已经很好地开始诊断您的程序出了什么问题，但是还有更有效的解决方案，例如记录您已经看到的字符。当您使用chars 时，我会考虑一个可以保存标记的位字段（256/8=32 字节的额外开销），或者如果不是太多，只是一个普通的布尔数组（额外开销 256 字节）。因为后者更容易实现并且代码更清晰：

void deleteRepeated(char array[], int *numused) {
    bool seenthischar[256] = {false};
    char *readpointer = &array[0];
    char *writepointer = &array[0];
    int length = *numused;
    for ( ;readpointer <= &array[0] + length; readpointer++) {
      if (seenthischar[((unsigned char) *readpointer)]) {
        *numused--;
      } else {
        seenthischar[((unsigned char) *readpointer)] = true;
        *writepointer = *readpointer;
        writepointer++;
      }
    }
}

这只有一个循环，所以它只需要遍历数组一次，即它的时间复杂度与输入数组的长度成线性关系。

于 2013-02-04T01:39:27.813 回答