C言語関係掲示板

過去ログ

No.918 名前を2次元配列でマージソートし辞書順出力

[戻る] [ホームページ]
No.11643

名前を2次元配列でマージソートし辞書順出力
投稿者---ボル(2004/01/11 00:04:37)


アルファベット表記の名前を2次元配列で実現し、マージソートして、辞書順にソートする課題ですが、この状態でコンパイルすると、

.灰瓮鵐伐媾蠅痢merge_sort( name, 0, 49 );」で「問題のあるポインタの変換」というエラーメッセージが出てしまいます。
仮にこの行を削除するとエラーメッセージは出ませんが、50人のうち1人(Ao)だけしか表示しません。それとこの行はどこかで使用しなければ後が続かないと思うのですが?
プログラム中でintをcharに変更する箇所が分かりません。変更する箇所があるのか無いのか分かりません。

以上、 銑どなたか回答を宜しくお願い致します。

#include <stdio.h>
#include <string.h>

void merge_sort(char [],int,int);
void merge(char [],int,int,int,int);
int dic_first(char [][30]);

int main()
{
char name[50][30];
int fpos;

strcpy(name[0],"Ka");
strcpy(name[1],"Aoi");
strcpy(name[2],"Is");
strcpy(name[3],"Ishi");
strcpy(name[4],"Uen");
strcpy(name[5],"Uet");
strcpy(name[6],"Onu");
strcpy(name[7],"Oga");
strcpy(name[8],"Ao");
strcpy(name[9],"Kan");
strcpy(name[10],"Kim");
strcpy(name[11],"Kiku");
strcpy(name[12],"Kuro");
strcpy(name[13],"Koi");
strcpy(name[14],"Sat");
strcpy(name[15],"Sai");
strcpy(name[16],"Saga");
strcpy(name[17],"Sasa");
strcpy(name[18],"Shimi");
strcpy(name[19],"Shis");
strcpy(name[20],"Shir");
strcpy(name[21],"Suzu");
strcpy(name[22],"Sumi");
strcpy(name[23],"Sega");
strcpy(name[24],"Set");
strcpy(name[25],"Sono");
strcpy(name[26],"Tachika");
strcpy(name[27],"Taga");
strcpy(name[28],"Tano");
strcpy(name[29],"Tsuga");
strcpy(name[30],"Tomo");
strcpy(name[31],"Todo");
strcpy(name[32],"Naka");
strcpy(name[33],"Nishi");
strcpy(name[34],"Nemo");
strcpy(name[35],"Nomu");
strcpy(name[36],"Hat");
strcpy(name[37],"Hira");
strcpy(name[38],"Hor");
strcpy(name[39],"Ma");
strcpy(name[40],"Mit");
strcpy(name[41],"Mura");
strcpy(name[42],"Mori");
strcpy(name[43],"Yasa");
strcpy(name[44],"Yosh");
strcpy(name[45],"Yoshi");
strcpy(name[46],"Yoko");
strcpy(name[47],"Wata");
strcpy(name[48],"Wac");
strcpy(name[49],"Wad");

name[50][0]='\0';

/* この下3行の書き方が? */
merge_sort( name, 0, 49 );
fpos=dic_first(name);
printf(" %s \n",name[fpos]);

return 0;
}

int dic_first(char name[][30])
{
int min,i,cmp;

 min = 0;
 for( i=0; name[i][0]!='\0'; i++ ){
  cmp=strcmp(name[i],name[min]);
   if( cmp<0 ) min=i;
 }
 return min;
 }

void merge_sort(char name[],int s,int e)
{
int m,tmp;

 if( e==s )return;
 if( e==s+1 ){
 if( name[s]>name[e] ) { tmp=name[s]; name[s]=name[e]; name[e]=tmp; }
 return;
 }
 m=(s+e)/2;
 merge_sort(name,s,m);
 merge_sort(name,m+1,e);
 merge(name,s,m,m+1,e);
}

void merge(char name[],int s1,int e1,int s2,int e2)
{
int p1=s1,p2=s2;
int b[50],k=0,i;

 while(( p1<=e1 )||( p2<=e2 )){
  if(( p1<=e1 )&&( name[p1]<name[p2] )){
   b[k]=name[p1];p1++;k++;
  }else{
   b[k]=name[p2];p2++;k++;
  }
 }
 for( i=0;i<k;i++ ) name[s1+i]=b[i];
}

全体的に


No.11648

Re:名前を2次元配列でマージソートし辞書順出力
投稿者---RAPT(2004/01/11 01:59:14)


> (2) 仮にこの行を削除するとエラーメッセージは出ませんが、50人のうち1人(Ao)だけしか表示しません。
> それとこの行はどこかで使用しなければ後が続かないと思うのですが?
意味不明です。一体何がしたいのですか?
あなたのコードに対するプログラムの動作自体は問題ありませんが。

アルゴリズムは見ていませんが、これでコンパイル・実行はできるでしょう。
どこが悪かったのか、あなたのコードと見比べてみてください。


#include <stdio.h>
#include <string.h>

int dic_first(const char name[][30], const int count)
{
  int min = 0, i;
  for(i = 1; i < count; ++i){
    if (strcmp(name[i], name[min]) < 0){
      min = i;
    }
  }
  return min;
}

void merge(char name[][30], int begin1, int end1, int begin2, int end2)
{
  int p1 = begin1, p2 = begin2;
  int k = 0, i;
  char tmp[50][30] = {0};

  const char *ptr = NULL;
  
  while( (p1 <= end1) || (p2 <= end2) ){
    if( (p1 <= end1) && (strcmp(name[p1], name[p2]) < 1) ){
      ptr = name[p1];
      strcpy(tmp[k++], name[p1++]);
    }else{
      ptr = name[p2];
      strcpy(tmp[k++], name[p2++]);
    }
  }
  for(i = 0; i < k; ++i){
    strcpy(name[begin1+i], tmp[i]);
  }
}

void merge_sort(char name[][30], int begin, int end)
{
  int mid;
  char tmp[30] = {0};
  
  if (begin == end)
    return;

  if (begin+1 == end){
    if (strcmp(name[begin], name[end]) > 0){
      strcpy(tmp, name[begin]);
      strcpy(name[begin], name[end]);
      strcpy(name[end], tmp);
    }
    return;
  }
  mid = (begin + end) / 2;
  merge_sort(name, begin, mid);
  merge_sort(name, mid+1, end);
  merge(name, begin, mid, mid+1, end);
}

int main()
{
  int fpos, i;
  char name[][30] = {
    "Ka", "Aoi", "Is",  "Ishi", "Uen", 
    "Uet",  "Onu",  "Oga",  "Ao", "Kan", 
    "Kim",  "Kiku", "Kuro",  "Koi",  "Sat",  
    "Sai",  "Saga", "Sasa",  "Shimi",  "Shis", 
    "Shir", "Suzu",  "Sumi", "Sega",  "Set",  
    "Sono", "Tachika", "Taga",  "Tano", "Tsuga", 
    "Tomo", "Todo",  "Naka", "Nishi", "Nemo",  
    "Nomu", "Hat", "Hira",  "Hor",  "Ma", 
    "Mit",  "Mura", "Mori",  "Yasa", "Yosh",  
    "Yoshi",  "Yoko", "Wata",  "Wac",  "Wad",  
  };  
  
  merge_sort(name, 0, 49);
  fpos = dic_first(name, 50); 
  printf("name[%d]=%s\n", fpos, name[fpos]);
  
  return 0;
}


No.11653

Re:名前を2次元配列でマージソートし辞書順出力
投稿者---ボル(2004/01/11 15:31:38)


RAPTさんご教示ありがとうございました。
当方の質問の意図が意味不明であったことを深くお詫び申し上げます。

本課題は、「50人のアルファベット表記の名前をマージソートで辞書順にソートして出力するプログラムの作成であり、50人の名前は2次元配列で実現し、プログラム内で設定せよ」と言うものであります。

RAPTさんから頂いた回答を参考にコンパイルを実施したところ、50人中1人([name21]=Ao)しか出力しません。例えば50人全員をアルファベット順に出力したい場合には、どのようにすれば良いのでしょうか。下記参照。

Ao
Aoi
Ha
Hira

省略

Wac
Wad
Wata
Yoko
Yoshi

申し訳ありません。宜しくお願い致します。


No.11680

Re:名前を2次元配列でマージソートし辞書順出力
投稿者---RAPT(2004/01/12 00:42:25)


> 50人中1人しか出力しません。
そりゃ、そうでしょう。dic_first関数で、最小のデータのみを出力
するようなコードが書かれているのですから。

50人分全部表示するのは簡単です。ソート後のデータをfor文で
全出力させてやればいいだけでしょう?

問題は、ソート処理がいけていない、というだけのことでしょう。
正しくソートされていれば、最小のデータは、配列の先頭[0]に
位置付けられるはずですから。


No.11683

Re:名前を2次元配列でマージソートし辞書順出力
投稿者---RAPT(2004/01/12 02:30:49)


アルゴリズムを修正しておきました。

結果から言えば、もともとのコードでは、右側の方がデータの個数が少ない時、
左側の値<=右側の値、となるまで、ひたすら右側のデータをコピーしまくり
だったのが問題でした。

#include <stdio.h>
#include <string.h>


void merge(char name[][30], const int begin1, const int end1, const int begin2, const int end2)
{
  int left = begin1, right = begin2;
  int k = 0, i;
  char tmp[50][30] = {0};

  /* 左側か、右側か、どちらか短い方の終端まで比較処理を行なう */
  while( (left <= end1) && (right <= end2) ){
    if(strcmp(name[left], name[right]) < 1){
      strcpy(tmp[k++], name[left++]);
    }else{
      strcpy(tmp[k++], name[right++]);
    }
  }

  /* 左側が残っていれば、すべてコピー */
  while( left <= end1 ){
    strcpy(tmp[k++], name[left++]);
  }

  /* 右側が残っていれば、すべてコピー */
  while( right <= end2 ){
    strcpy(tmp[k++], name[right++]);
  }

  /* 整列済みデータの書き戻し */
  for(i = 0; i < k; ++i){
    strcpy(name[begin1+i], tmp[i]);
  }
}

void merge_sort(char name[][30], const int begin, const int end)
{
  int mid;
  char tmp[30] = {0};
  
  if(end == begin)
    return;

  if(end == begin+1){
    if(strcmp(name[begin], name[end]) > 0){
      /* 値交換 */
      strcpy(tmp, name[begin]);
      strcpy(name[begin], name[end]);
      strcpy(name[end], tmp);
    }
    return;
  }
  mid = (begin + end) / 2;
  merge_sort(name, begin, mid); /* 左側の部分ソート */
  merge_sort(name, mid+1, end); /* 右側の部分ソート */
  merge(name, begin, mid, mid+1, end);  /* 併合処理 */
}

int main()
{
  int i;
  char name[][30] = {
    "Ka", "Aoi", "Is",  "Ishi", "Uen", 
    "Uet",  "Onu",  "Oga",  "Ao", "Kan", 
    "Kim",  "Kiku", "Kuro",  "Koi",  "Sat",  
    "Sai",  "Saga", "Sasa",  "Shimi",  "Shis", 
    "Shir", "Suzu",  "Sumi", "Sega",  "Set",  
    "Sono", "Tachika", "Taga",  "Tano", "Tsuga", 
    "Tomo", "Todo",  "Naka", "Nishi", "Nemo",  
    "Nomu", "Hat", "Hira",  "Hor",  "Ma", 
    "Mit",  "Mura", "Mori",  "Yasa", "Yosh",  
    "Yoshi",  "Yoko", "Wata",  "Wac",  "Wad",  
  };

  /* 要素の個数を自動計算 */
  const int size = sizeof(name) / sizeof(name[0]);

  puts("--- ソート前 ---");
  for( i = 0; i < size; ++i){
    printf("name[%2d]=%s\n", i, name[i]);
  }

  merge_sort(name, 0, size-1);

  puts("--- ソート後 ---");
  for( i = 0; i < size; ++i){
    printf("name[%2d]=%s\n", i, name[i]);
  }

  return 0;
}


No.11689

Re:名前を2次元配列でマージソートし辞書順出力
投稿者---ボル(2004/01/12 10:21:08)


><pre>アルゴリズムを修正しておきました。

RAPTさん度重なるご教示ありがとうございました。
大変勉強になりました。

No.11668

Re:名前を2次元配列でマージソートし辞書順出力(追加)
投稿者---ボル(2004/01/11 18:33:26)


RAPTさん申し訳ありません。追加の質問があります。
同じ課題をクイックソート(下記コード参照)で実施した場合、うまく動きません。どこがおかしいか教えて下さい。


  #include <stdio.h>
  #include <string.h>

  void quick_sort(char [][30],int,int);
  int dic_first(char [][30],int);

  int main()
  {
    int fpos,i;
    char name[50][30]={
      "Ka","Ao","Ish","Wa","Ue",
      "Uet","Onu","Oga","Aok","Kan",
      "Kim","Kik","Kuro","Ko","Sat",
      "Sai","Sag","Sas","Shi","Shis",
      "Shir","Su","Sum","Seg","Set",
      "Son","Ta","Tag","Too","Tsug",
      "Tom","Tod","Nak","Nis","Nem",
      "Nom","Ha","Hi","Hor","Mae",
      "Mi","Mur","Mor","Yas","Yos",
      "Yo","Yoko","Wat","Wac","Is"
    };

    quick_sort( name, 0, 49 );
    fpos=dic_first(name,50);
    printf(" %s ",name[fpos]);

  return 0;
  }

  int dic_first(char name[][30],int c)
  {
    int min=0,i;

    for( i=1; i<c; i++ ){
      if( strcmp(name[i],name[min])<0){
        min=i;
      }
    }
    return min;
  }

  void quick_sort(char name[][30],int s,int e)
  {
    int i,j;
    char x,tmp[30]={0};

      if( s+1>=e ){
        if( strcmp(name[s],name[e]) >0 ) { 
          strcpy(tmp,name[s]);
          strcpy(name[s],name[e]); 
          strcpy(name[e],tmp);
        }
        return;
      }
      x=(s+e)/2;
      i=s; j=e;
      while(1){
        while( strcmp(name[i],name[j]) <x ) i++;
          while( strcmp(name[j],name[i]) >x ) j--;
            if( i>j )break;
              strcpy(tmp,name[i]);
              strcpy(name[i],name[j]);
              strcpy(name[j],tmp);
              i++; j--;
      }
      quick_sort(name,s,j);
      quick_sort(name,i,e);
  }




No.11649

Re:名前を2次元配列でマージソートし辞書順出力
投稿者---YuO(2004/01/11 02:10:09)


丸囲み数字(と思われる文字)はUS-ASCII/JIS X 0208/JIS X 0212に含まれない文字です。
基本的にEUC-JPを使っている掲示板での使用は厳禁です。
see) 日月火水木金土
#URLが変化しているかも。Googleのキャッシュ

それから,ある程度以上のソースコードを記述は,【掲示板ご利用上の注意】に従って下さい。
最低でも,pre要素の内容として書いてインデントが付いていないと,読みにくいだけです。


>(1) コメント箇所の「merge_sort( name, 0, 49 );」で「問題のあるポインタの変換」というエラーメッセージが出てしまいます。

そのまんまです。
char [50][30]型,つまりはchar (*)[30]型をchar *型に変換することはできません。

char [50][30]型を引数として渡されたいのだから,
merge_sortの最初の引数はchar [][30]のように宣言する必要があります。
#つーか,dic_firstではそうしているのに,何故merge_sortではそうしない?


>(2) 仮にこの行を削除するとエラーメッセージは出ませんが、50人のうち1人(Ao)だけしか表示しません。それとこの行はどこかで使用しなければ後が続かないと思うのですが?

で,何がしたいのですか?

マージソートをしようがしまいが,Aoしか表示されないようにプログラムが組んであるのですから,当たり前のことです。
#まぁ,未定義動作していることには目を瞑っていますが。


>(3) プログラム中でintをcharに変更する箇所が分かりません。変更する箇所があるのか無いのか分かりません。

なんのために変更したいのですか?


それでもって,コードをちょっと見て気になった点。

>char name[50][30];
なのに,
>name[50][0]='\0';
なんてしたらいけません。
#理由がわからないなら要配列再勉強。


>strcpy(name[0],"Ka");
(snip)
>strcpy(name[49],"Wad");

char name[50][30] = {
    "Ka",
    "Aoi",
    /* 省略 */
    "Wad"
};

のように,初期化を使った方が見やすくなります。
定数リテラルを配列に設定するために,strcpyを並べるのはいいことがないですよ。

No.11652

Re:名前を2次元配列でマージソートし辞書順出力
投稿者---ボル(2004/01/11 15:13:20)


ご教示ありがとうございました。
以後、ソースを添付する際には【HTML変換ツール】を使用致します。
今後とも宜しくお願い致します。