過去ログ
No．１０９１ 重複する文字列を削除する プログラム
[戻る] [ホームページ]No.14320 |
文字列削除 投稿者---AI(2004/05/31 10:53:38) |
||
| 文字列をソートして、重複する文字列を削除する
プログラムを考えています。 今現在、ソートして、同じ文字列順には 並べ替えることができたのですが、 同じ文字列を削除できません。 例として、配列に aaa bbb ccc aaa ccc を格納するとして、 最終的には aaa bbb ccc のように文字列を簡単にしたいです。 以下に今作成したプログラムを示します。 #include <stdio.h>
#include <stdlib.h>
int compar(const char *a,const char *b);
int main()
{
char *name[]={"aaa","bbb","ccc","aaa","ddd","ccc"};
int i,n;
int sizename=sizeof(name)/sizeof(name[0]);
cout<<"ソート前表示"<<endl;
for(i=0;i<sizename;i++){
printf("%s\n",name[i]);
}
cout<<"\n";
qsort(name,sizename,sizeof(name[sizename]),(int(*)(const void *,const void *))compar);
cout<<"ソート後表示"<<endl;
for(i=0;i<sizename;i++){
printf("%s\n",name[i]);
}
cout<<"\n";
return 0;
}
int compar(const char *a,const char *b)
{
if(*a<*b){
return -1;
}
else if(*a>*b){
return 1;
}
else{
return 0;
}
}
宜しくお願いします。
|
|||
No.14323 |
Re:文字列削除 投稿者---たか(2004/05/31 12:05:50) |
||
| 出力にcoutが使ってあるのにiostreamをインクルードしてないなど、妙な
点が見受けられますが、C++だとみなしてプログラムを書いてみました。 これがCだとしてもプログラムの流れは同じで行けると思います。 #include <iostream>
#include <cstring>
#include <iterator>
#include <algorithm>
bool mystrcmp(const char*& a, const char*& b)
{
return (std::strcmp(a, b) < 0) ? 1 : 0;
}
bool mystreq(const char*& a, const char*& b)
{
return (std::strcmp(a, b) == 0) ? 1 : 0;
}
int main()
{
char *name[] = {"aaa", "bbb", "ccc", "aaa", "ddd", "ccc"};
int sizename = sizeof(name) / sizeof(name[0]);
std::cout << "ソート前表示\n";
std::copy(name, name + sizename, std::ostream_iterator<char*>(std::cout, " "));
std::cout << std::endl;
std::sort(name, name + sizename, mystrcmp);
std::cout << "ソート後表示\n";
std::copy(name, name + sizename, std::ostream_iterator<char*>(std::cout, " "));
std::cout << std::endl;
char** end = std::unique(name, name + sizename, mystreq);
std::cout << "unique後表示\n";
std::copy(name, end, std::ostream_iterator<char*>(std::cout, " "));
std::cout << std::endl;
}
|
|||
| No.14325 |
Re:文字列削除 投稿者---あかま(2004/05/31 12:54:12) |
||
題意と外れるんですが、私も質問です。
BCCでAIさんのコードを実行したところ（compar()が文字列の比較として明らかに間違ってたのでそこだけ修正）
ソートが上手く動きませんでした（最後まで実行されるがまったくソートされてない）。
そこで色々試した結果、
char *name[]={"aaa","bbb","ccc","aaa","ddd","ccc"};
を
char name[][4]={"aaa","bbb","ccc","aaa","ddd","ccc"};
に変えるだけで上手く動いたのです。果たしてこの違いはなんなのでしょうか？
qsort内で*name[]版はchar*の入れ替え、name[][4]版はchar[]4文字の入れ替えの違いではないのでしょうか？
compar()内でa,bを出力するとname[][4]版はきっちり出力されて、*name[]版は文字化けするので
qsortの引数として渡し方がなにか間違っている気もするのですが。
|
|||
| No.14326 |
Re:文字列削除 投稿者---NykR(2004/05/31 13:37:03) |
||
qsortの比較関数の引数には要素へのポインタが渡されます > char *name[]={"aaa","bbb","ccc","aaa","ddd","ccc"}; の場合、nameはポインタの配列なので、比較関数の引数には文字列の先頭要素へのポインタのポインタが渡されます。 ですから、文字列の中の文字を取り出すには、二回間接参照しなければなりません。 例えば、if(*a<*b)ではなくif(**a<**b)。 一方 > char name[][4]={"aaa","bbb","ccc","aaa","ddd","ccc"}; は、オブジェクトの配列ですから、引数には文字列へのポインタが渡されます。 が、文字列というか配列へのポインタは、キャストするかvoid*経由で、先頭要素へのポインタと互いに変換できてしまうことが多いので、 *a<*b で先頭文字の値を比較することになり、うまく動いたのでしょう。 ＃ 実は“多い”ではなく“常に”かもしれないけど、規格をざっと見た限りではそういう記述は見当たらなかった。 ついでに、比較関数のプロトタイプは int compar(const void*,const void*) でないと予想外の動きをするかもしれません。 |
|||
| No.14327 |
Re:文字列削除 投稿者---ぽこ(2004/05/31 13:48:40) |
||
>文字列をソートして、重複する文字列を削除する >プログラムを考えています。 C++で要素がソートされ、重複しないデータ構造を求めているのでしたら、 setを利用してはどうでしょうか？ |
|||
| No.14328 |
Re:文字列削除 投稿者---NykR(2004/05/31 13:49:09) |
||
> 例えば、if(*a<*b)ではなくif(**a<**b) 例えが古かったですね。 strcmp(a,b)ではなくstrcmp(*a,*b) です。 で、比較関数は、 int compar(const char **a,const char **b) でも大抵の環境ではうまく動くでしょうけど int compar(const void *a,const void *b)
{
printf("%s,%s\n",*(const char*const*)a,*(const char*const*)b);
return strcmp(*(const char*const*)a,*(const char*const*)b);
}の方がいいと思います。
＃キャストしたら読みにくいから一時変数を導入した方がいいかも
|
|||
| No.14331 |
Re:文字列削除 投稿者---AI(2004/05/31 14:26:13) |
||
>出力にcoutが使ってあるのにiostreamをインクルードしてないなど、妙な >点が見受けられますが、C++だとみなしてプログラムを書いてみました。 すみません。書き忘れていました。 Ｃ/Ｃ＋＋初心者で、Ｃ＋＋よりも まだＣの方がわかっているほうですので、 たかさんのソースがかなり難しく感じます。 よろしければＣソースのほうを教えていただきたいです。 |
|||
| No.14332 |
Re:文字列削除 投稿者---たか(2004/05/31 15:12:15) |
||
ここまで皆さん書いてくださったのですから、後C言語でstd::unique() と同じような働きをする関数もお任せしましょう。 このようなある程度決まり切った事をやらせるには、もはやCよりC++の方 がずっと楽に書ける事にお気づきでしょうか。でもそれをCでどのように 書くのかを知っておくのはいい事です。 |
|||
| No.14333 |
Re:文字列削除 投稿者---たか(2004/05/31 15:23:12) |
||
>>文字列をソートして、重複する文字列を削除する >>プログラムを考えています。 > >C++で要素がソートされ、重複しないデータ構造を求めているのでしたら、 >setを利用してはどうでしょうか？ そうですね、初めからコンテナを使ってしまうのも一手です。ただ std::set()は大抵赤黒木を使って実装されているのでパフォーマンスが かなり悪いという欠点があります。std::sort()→std::unique()を std::vector()に適用する方が速い事がおいおいあります。それでも 概念的にはstd::setの方がすっきりしていてわかりやすいですね。 話が全然飛びますが、C++に欠けているのは遅延評価で、FC++やboost::Phoenix を使うとこれが実現できます。Haskellのような事ができるのです。 (話飛びすぎ) |
|||
| No.14334 |
Re:文字列削除 投稿者---AI(2004/05/31 17:02:05) |
||
Ｃ＋＋の方が簡単であるような ことはわかりました。erase()などで 削除すると早くできる・・・。 自分はまだＣ＋＋がわからないので、Ｃ言語で 書こうと思っています。 データを昇順ソートして 配列に格納し、 int j=0; for(int r=0;r<sizename;r++){ if(strcmp(name[r],name[j+1])!=0){ ・・・ のように そのデータをstrcmp()で比較して、 同じであれば削除して、次の配列は詰める ような感じのソースを書きたいです。 同じ文字列は１つだけ残して削除し、 文字列を詰める処理がわかりません。 考え方が間違っているのでしょうか？ 宜しくお願いします。 |
|||
| No.14335 |
Re:文字列削除 投稿者---かずま(2004/05/31 17:49:11) |
||
| > 自分はまだＣ＋＋がわからないので、Ｃ言語で書こうと思っています。
C のプログラムですから、ファイル名の拡張子は .cpp ではなく .c にしてください。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compar(const void *a, const void *b)
{
char *const *x = a, *const *y = b;
return strcmp(*x, *y);
}
int main(void)
{
char *name[] = { "aaa", "bbb", "ccc", "aaa", "ddd", "ccc" };
#define sizename (sizeof name / sizeof name[0])
int i, n;
puts("ソート前表示");
for (i = 0; i < sizename; i++) puts(name[i]);
qsort(name, sizename, sizeof name[0], compar);
puts("\nソート後表示");
for (i = 0; i < sizename; i++) puts(name[i]);
for (n = i = 1; i < sizename; i++)
if (strcmp(name[i-1], name[i])) name[n++] = name[i];
puts("\n重複除去後表示");
for (i = 0; i < n; i++) puts(name[i]);
return 0;
}
|
|||
| No.14336 |
Re:文字列削除 投稿者---あかま(2004/05/31 18:23:27) |
||
char name[][4]={"aaa","bbb","ccc","aaa","ddd","ccc"}; はたまたま動いていたのですね。 void *なのでchar *がcomparに渡されているのだとばかり思ってました。 char **だったとは… ありがとうございました。 |
|||
| No.14337 |
Re:文字列削除 投稿者---AI(2004/05/31 18:44:18) |
||
for (n = i = 1; i < sizename; i++) if (strcmp(name[i-1], name[i])) name[n++] = name[i]; 重複削除のところで、配列に代入をしていますが、 cppで実行を試みたのですが、Ｃ＋＋は 配列に代入できないと言うエラーが返ってきました。 何故でしょうか？ また、拡張子.cppでエラーをなくすにはどうしたらよいでのでしょうか？ 宜しくお願いします。 |
|||
| No.14338 |
Re:文字列削除 投稿者---ぽこ(2004/05/31 20:55:41) |
||
>そうですね、初めからコンテナを使ってしまうのも一手です。ただ >std::set()は大抵赤黒木を使って実装されているのでパフォーマンスが >かなり悪いという欠点があります。std::sort()→std::unique()を >std::vector()に適用する方が速い事がおいおいあります。それでも >概念的にはstd::setの方がすっきりしていてわかりやすいですね。 なるほど性能を考慮するとstd::sort()→std::unique()の方が良いわけですね。 勉強になりました。 |
|||
| No.14339 |
文字列削除 投稿者---たか(2004/05/31 21:43:31) |
||
>重複削除のところで、配列に代入をしていますが、 >.cppで実行を試みたのですが、Ｃ＋＋は >配列に代入できないと言うエラーが返ってきました。 >何故でしょうか？ >また、拡張子.cppでエラーをなくすにはどうしたらよいでのでしょうか？ >宜しくお願いします。 C++はCよりも型チェックが厳格なため、void型のポインタは他の型への ポインタに暗黙の内に変換されません。 明示的に型キャストをしなければ なりません。 int compar(const void *a, const void *b)
{
char *const *x = static_cast<char*const*>(a), *const *y = static_cast<char*const*>(b);
return strcmp(*x, *y);
}
|
|||
| No.14356 |
Re:文字列削除 投稿者---AI(2004/06/01 10:49:40) |
||
もし、格納されているデータが ポインタ配列ではなく、２次元配列の場合、 ソース自体変えなければならないところはありますか？ また、上記のソースの name[n++] = name[i];のところが 理解できません。 if (strcmp(name[i-1], name[i])) で name[i-1]とname[i]が一致しない場合に name[n++] = name[i];を行うところまでは 理解できました。 簡単なことかもしれませんが、 プログラムまだ始めたばかりなので 説明していただければ助かります。 宜しくお願いします。 |
|||
| No.14359 |
Re:文字列削除 投稿者---かずま(2004/06/01 11:35:46) |
||
> 重複削除のところで、配列に代入をしていますが、 name は配列ですが、name[n++] も name[i] も配列ではありません。 > .cppで実行を試みたのですが、Ｃ＋＋は > 配列に代入できないと言うエラーが返ってきました。 > 何故でしょうか？ コンパイル時に打ち込んだコマンドと、エラーメッセージを一字一句間違いなく 提示してください。また、ソースは改変していませんか？ > また、拡張子.cppでエラーをなくすにはどうしたらよいでのでしょうか？ なぜ、C言語のプログラムなのに .cpp にしなければならないのか理解できません。 説明をお願いします。 |
|||
| No.14361 |
Re:文字列削除 投稿者---AI(2004/06/01 12:08:14) |
||
>コンパイル時に打ち込んだコマンドと、エラーメッセージを一字一句間違いなく >提示してください。また、ソースは改変していませんか？ g++ -o source s.cpp ソースは、格納データを２次元配列にしました。 すると、 ISO C++は配列の代入を禁じます というエラーが出ました。 >なぜ、C言語のプログラムなのに .cpp にしなければならないのか理解できません。 >説明をお願いします。 先輩の下のソースに今行っている事を組み込むために、 その元のソースがＣ＋＋であり、 元の格納データも２次元配列だったので ソースを改変しました。 後手後手で申し訳ございません。 ２次元配列にするとどのように改変したらよいのでしょうか？ 宜しくお願いします。 |
|||
| No.14362 |
Re:文字列削除 投稿者---ぽこ(2004/06/01 13:00:33) |
||
>また、上記のソースの >name[n++] = name[i];のところが >理解できません。 iはどこまで重複チェックを行ったかを記憶する変数。 nは重複していない文字列を格納する場所を記憶する変数。 |
|||
| No.14364 |
Re:文字列削除 投稿者---たか(2004/06/01 14:56:26) |
||
>先輩の下のソースに今行っている事を組み込むために、 >その元のソースがＣ＋＋であり、 >元の格納データも２次元配列だったので >ソースを改変しました。 > >後手後手で申し訳ございません。 > >２次元配列にするとどのように改変したらよいのでしょうか？ >宜しくお願いします。 多分ポインタ配列を二次元配列に書き換えてしまったためにポインタでは なく 配列を代入しようとしたからエラーが出たのだと思います。 配列の代入はループによるしかありません。もしくは構造体の中に入れて 構造体として代入するかです。 main()の最後尾にreturn 0;がありませんがバグではありません。 ANSI/ISO C++ではmain()に限り、値を返さないとreturn 0;を暗黙の内に最後尾に あるものと見なします。 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LEN 4
int compar(const void* a, const void* b)
{
return strcmp(static_cast<const char*>(a), static_cast<const char*>(b));
}
int main(void)
{
char name[][LEN] = { "aaa", "bbb", "ccc", "aaa", "ddd", "ccc" };
#define sizename (sizeof name / sizeof name[0])
int i, j, n;
puts("ソート前表示");
for (i = 0; i < sizename; i++) puts(name[i]);
qsort(name, sizename, sizeof name[0], compar);
puts("\nソート後表示");
for (i = 0; i < sizename; i++) puts(name[i]);
for (n = i = 1; i < sizename; i++)
if (strcmp(name[i - 1], name[i])) {
for (j = 0; j < LEN; j++)
name[n][j] = name[i][j];
n++;
}
puts("\n重複除去後表示");
for (i = 0; i < n; i++) puts(name[i]);
}
|
|||
| No.14365 |
Re:文字列削除 投稿者---たか(2004/06/01 15:03:14) |
||
それと話は変わりますが、gccでこのソースをコンパイルすると、怪しげ な警告が出ませんでしたか？ gccは日本語に対応してないので、Shift-JISの環境ですとソ系ダメ文字 "ソ"と"表"を含んでいるため漢字が化けます。それぞれ"ソ\"と"表\"と 書く必要があります。 しかし多バイトコードにUTFを使用している環境なら大丈夫です。 |
|||
| No.14366 |
Re:文字列削除 投稿者---たか(2004/06/01 15:09:33) |
||
if (strcmp(name[i - 1], name[i])) {
for (j = 0; j < LEN; j++)
name[n][j] = name[i][j];
n++;
}
を
if (strcmp(name[i - 1], name[i]))
memcpy(name[n++], name[i], LEN);
に変更してもいいですね。
|
|||
| No.14382 |
Re:文字列削除 投稿者---AI(2004/06/02 12:13:57) |
||
すみません。 追加質問です。 for分のところで、 最大値ｎまでをsizenameに変更したら ｎ以降の文字が配列に残っていました。 その部分を完全に消したいのですが、 どのようにしたらよいのでしょうか？ 宜しくお願いします。 for (n = i = 1; i < sizename; i++)
if (strcmp(name[i - 1], name[i])) {
for (j = 0; j < LEN; j++)
name[n][j] = name[i][j];
n++;
}
puts("\n重複除去後表示");
for (i = 0; i < sizename; i++) puts(name[i]);
}
|
|||
| No.14383 |
Re:文字列削除 投稿者---AI(2004/06/02 12:50:06) |
||
たびたびの追加すみません。 下記に自分で作成しました。 しかし、セグメンテーション違反になります。 もとのデータサイズ:sizename コピーされたサイズ:n と解釈して、 残り：sizename-nで n以降の配列を全て削除すると 考え、ＮＵＬＬ文字を入れました。 宜しくお願いします。 for(n=i=1;i<sizename;i++){
if (strcmp(name[i - 1], name[i]))
memcpy(name[n++], name[i], LEN);
}
int d=sizename-n;
for( int j=0;j<d;j++){
for(int k=0;k<LEN;k++){
name[n+j][n+k];
}
}
|
|||
| No.14386 |
Re:文字列削除 投稿者---たか(2004/06/02 14:23:05) |
||
>しかし、セグメンテーション違反になります。
>もとのデータサイズ:sizename
>コピーされたサイズ:n
>と解釈して、
>残り：sizename-nで
>n以降の配列を全て削除すると
>考え、ＮＵＬＬ文字を入れました。
>
>宜しくお願いします。
>
>int d=sizename-n;
>for( int j=0;j<d;j++){
> for(int k=0;k<LEN;k++){
> name[n+j][n+k];
> }
>}
name[n+j][n+k]は解せません。name[n+j][k]ではないでしょうか。kは0〜LEN - 1
の間でしか変化してはいけないはずですから。
それからコピーがmemcpy()またはstrcpy()なら、充填はmemset()で行えば
すっきりします。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LEN 4
int compar(const void* a, const void* b)
{
return strcmp(static_cast<const char*>(a), static_cast<const char*>(b));
}
int main(void)
{
char name[][LEN] = { "aaa", "bbb", "ccc", "aaa", "ddd", "ccc" };
#define sizename (sizeof name / sizeof name[0])
int i, n;
puts("ソート前表示");
for (i = 0; i < sizename; i++) puts(name[i]);
qsort(name, sizename, sizeof name[0], compar);
puts("\nソート後表示");
for (i = 0; i < sizename; i++) puts(name[i]);
for (n = i = 1; i < sizename; i++)
if (strcmp(name[i - 1], name[i]))
memcpy(name[n++], name[i], LEN);
for (i = n; i < sizename; i++)
memset(name[i], '\0', LEN);
puts("\n重複除去後表示");
for (i = 0; i < sizename; i++)
puts(name[i]);
}
|
|||
| No.14392 |
Re:文字列削除 投稿者---AI(2004/06/02 17:01:21) |
||
ありがとうございます。 memsetなど、 まだまだ自分の知らない関数が たくさんあります。 丁寧に本当にありがとうございました。 また、わからないことが あれば教えていただければ 嬉しく感じます。 |
|||