2

C の文字列の配列と、配列内の文字列の数を示す整数があります。

char *strarray[MAX];  
int strcount;

この配列では、最も高いインデックス (10 は 0 より大きい) が最後に追加された項目であり、最も低いインデックスが追加された最も遠い項目です。配列内の項目の順序は重要です。

配列の重複をチェックし、最も高いインデックスの duplicate 以外をすべて削除し、配列を折りたたむ簡単な方法が必要です。

例えば：

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. 1 つだけが残るように、同じ項目の連続実行が設定されていることを確認します。

最初の部分を達成するため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

私はあなたの提案したアルゴリズムをよく理解していません (ステップ 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^2) ではなく O(n log n) になります。

于 2010-08-01T06:28:55.283 に答える
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 に答える
0

qsort（端末で使用方法を確認するために）のようなアルゴリズムで配列をソートしman 3 qsort、関数を使用しstrcmpて文字列を比較し、重複を見つけます

元の順序を維持したい場合は、O(N^2) の複雑さのアルゴリズムを使用して two をネストforし、最初の要素を毎回選択して他の要素と比較し、2 番目の要素を使用して残りの配列をスキャンして、選択した要素が重複しているかどうかを調べます。

于 2016-04-26T12:41:11.440 に答える