過去ログ
No．１２８３ 配列１と配列２の重複文字列を省いて文字列を結合させたい
[戻る] [ホームページ]No.16976 |
配列の比較と結合 投稿者---アイソトープ(2004/09/30 18:07:01) |
||
たびたびすいません。またご質問です。 以下のような配列があった場合、配列１と配列２を比較してかぶっている文字列ははぶいて、文字列を結合させたいのですがいい方法はありますでしょうか？？？ char str1[10][10]={"あい","うえ","おか","きく","けこ","さし"}; char str2[10][10]={"かき","くけ","あい","ここ"}; 最終的に下記のような感じで結合させたいのですが・・・。 配列１と配列２では”あい”がかぶるので結合させるとき、これをはぶいて結合させたいのです。 {"あい","うえ","おか","きく","けこ","さし""かき","くけ","ここ"}; 私が考えたのが、ループ処理でまず配列１の”あい”と配列２のすべての文字列をmemcpyで比較し、戻り値が0の文字列だけ結合させるという感じで、配列１の”あい”の比較が終わったら"うえ"で配列２のすべての文字列と比較という感じで配列１の配列の個数分ループさせるという感じで考えました。 ただこの方法だと、配列が多い場合処理が重くなってしまうと思います。 この方法以外に一気に文字配列を比較する方法はありますでしょうか？？？ 比較して最終的にはかぶっている文字列をはぶいて結合させたいです。 たびたび申し訳ございませんがご伝授くださいませ。 |
|||
| No.16977 |
Re:配列の比較と結合 投稿者---tetrapod(2004/09/30 18:23:31) |
||
新しい配列を作ります。 その配列に、文字列を追加していきます。 追加する際、既に登録済みの文字列と同じであれば登録しない。 でいけそうです。 新しい「文字列配列」でなければならないか、それとも 新しい「ポインタの配列」でよいのかは用途次第でしょう。 |
|||
| No.16978 |
Re:配列の比較と結合 投稿者---アイソトープ(2004/09/30 18:35:10) |
||
>新しい配列を作ります。 >その配列に、文字列を追加していきます。 >追加する際、既に登録済みの文字列と同じであれば登録しない。 >でいけそうです。 その方法はループで文字列を１つ１つmemcpyで比較し戻り値が０ならば、新しい配列に格納していくというイメージでしょうか？？？ |
|||
| No.16979 |
Re:配列の比較と結合 投稿者---tetrapod(2004/09/30 18:44:39) |
||
>その方法はループで文字列を１つ１つmemcpyで比較し戻り値が０ならば、新しい配列に格納していくというイメージでしょうか？？？ memcpy で比較することはできません。文字列を比較するのは strcmp です。 リニアサーチで良いのなら御意、そのとおりです。 比較の条件が逆ですが。 for (i=0; i<n; ++i) {
if (strcmp(newarray[i],newstring)==0) return; /* skip same string */
}
newarray[n++]=newstring; /* remember new string */
って感じ。効率を上げたいのなら２分木とかのアルゴリズムを用いればいいです。 |
|||
| No.16980 |
Re:配列の比較と結合 投稿者---tetrapod(2004/09/30 18:52:13) |
||
別解。元文字列(複数個)をソートしてよいのなら、 元文字列１をソート、元文字列２をソート。 元文字列１と２をマージソート(重複させない) 元文字列１，２の並びが換わってしまってはならないのであれば、２分木もダメなので 結局リニアサーチしか手はないです。 |
|||
| No.16981 |
Re:配列の比較と結合 投稿者---アイソトープ(2004/09/30 18:58:05) |
||
ありがとうございます。勘違いしてました。 strcmpで比較しmemcpyで配列を結合させるつもりでしたが無理ですかね？？？ for (i=0; i<n; ++i) { if (strcmp(newarray[i],newstring)==0) return; } newarray[n++]=newstring; この処理は配列newarrayのi番目の配列とnewstringを比較し同じならばループを抜け、違っていた場合はnewstringを配列newarrayのn+1のところに文字列newstringを結合させるという感じの処理でしょうか？？？ newarray[n++]=newstring; がループの外にあるのが意味がわからないのですが・・・。 ど素人なものですいません・・・。 |
|||
| No.16982 |
Re:配列の比較と結合 投稿者---tetrapod(2004/09/30 19:15:49) |
||
今 newarray に n 個の文字列が登録済みとします (n>=0) この newarray に文字列 newstring を追加したいのですが、題意から 既に登録済みの文字列と同じであれば追加したくないわけです。 よって strcmp()==0 であれば登録済み文字列と同じなのでスキップ。 for を抜けたなら登録済み文字列とは不一致なので追加。 追加したなら n を１増やさねばいけないよね。 とただそれだけです。 提示の例はポインタ配列 newarray を作る場合を想定していますが、 文字列の配列であれば = で代入できないので memcpy または strcpy になります。 ポインタの配列にせよ文字列の配列にせよ、新しい配列用のメモリ確保が大事です。 # アルゴリズムの解説なのでその辺の実装は略しています。 リニアサーチよりはマージソートするほうが劇的に速いと思った。 |
|||
| No.16985 |
Re:配列の比較と結合 投稿者---Sciggepy(2004/09/30 21:30:40) |
||
こんなのはどうですか？結合元で重複していると使えませんが。 #include <stdlib.h>
#include <string.h>
#include <stdio.h>
int comp(const void *s1,const void *s2)
{
return strcmp((const char *)s1,(const char *)s2);
}
size_t k25(char **strs1,size_t nc1,char **strs2,size_t nc2,char ***ret)
{
char **r;
size_t i,j,n;
int c;
if(!(r=calloc(nc1+nc2,sizeof(char *)))) return 0;
qsort(strs1,nc1,sizeof(char *),comp);
qsort(strs2,nc2,sizeof(char *),comp);
for(i=0,j=0,n=0;i<nc1&&j<nc2;) {
if((c=strcmp(strs1[i],strs2[j]))<0) r[n++]=strs1[i++];
else r[n++]=strs2[j++];
if(c==0) i++;
}
while(i<nc1) r[n++]=strs1[i++];
while(j<nc2) r[n++]=strs2[j++];
if(ret) *ret=r; else free(r);
return n;
}
int main(void)
{
char *str1[6]={"あい","うえ","おか","きく","けこ","さし"};
char *str2[4]={"かき","くけ","あい","ここ"};
char **strd;
size_t n,i;
n=k25(str1,6,str2,4,&strd);
for(i=0;i<n;i++) printf("%d: %s\n",i,strd[i]);
free(strd);
return 0;
}
|
|||
| No.16998 |
Re:配列の比較と結合 投稿者---かずま(2004/10/01 13:43:51) |
||
> こんなのはどうですか？結合元で重複していると使えませんが。
> return strcmp((const char *)s1,(const char *)s2);
次のようにしないと、qsort がうまくいくとは思えません。
return strcmp(*(char **)s1, *(char **)s2);
効率のいい悪いは別にして、最初の質問のやりたいことは次のようなことでしょうか？
#include <stdio.h>
#include <string.h>
int main(void)
{
char *str1[6] = {"あい", "うえ", "おか", "きく", "けこ", "さし"};
char *str2[4] = {"かき", "くけ", "あい", "ここ"};
char *str3[10];
int i, j, k = 6;
memcpy(str3, str1, sizeof str1);
for (i = 0; i < 4; i++) {
for (j = 0; j < 6; j++)
if (strcmp(str1[j], str2[i]) == 0) break;
if (j == 6) str3[k++] = str2[i];
}
for (i = 0; i < k; i++) printf(" %s", str3[i]);
printf(" : %d\n", k);
return 0;
}
|
|||