C言語関係掲示板

過去ログ

No.921 マージソート

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

ファイルの入出力
投稿者---無限(2004/01/11 23:42:40)


課題:「プログラムの第1引数で指定されたファイル(data.txt)は1行毎に1列目に名前(アルファベット表記)と2列目に数値が記されており、列は1個以上の空白文字で区切られている。数値の大きい順に並び替えて、第2引数で指定されたファイル(data2.txt)に出力するプログラム。但し、数値が同じ場合はアルファベット順にする」(下記例参照)

このような課題はどのようにすれば良いのでしょうか。下記コードを応用して組むみたいなんですけど。


  #include <stdio.h>
  #include <stdlib.h>

  int main(int argc,char *argv[])
  {
    FILE *fp,*fp2;
    char buf[128],name[30];
    int number;

    if( argc!=2 ) { printf("usage: prog filename\n"); exit(0); }
      fp=fopen("data.txt","r");
      fp2=fopen("data2.txt","w");
    if( fp==NULL ) { printf("cannot open file\n"); exit(0); }

    while( fgets(buf,128,fp)!=NULL ){
      sscanf( buf,"%s %d",name,&number);
      fprintf(fp2,buf);
      fclose(fp2);
      fclose(fp);
    }
  }



例:data.txt

Sato 200
Saiki 80
Kawano 150
Tokyo 50
Tokio 50
   ↓ >prog data.txt data2.txt
data2.txt

Sato 200
Kawano 150
Saiki 80
Tokio 50
Tokyo 50

   




No.11677

Re:ファイルの入出力
投稿者---RAPT(2004/01/12 00:24:39)


【掲示板ご利用上の注意】を実践しましょう。

> 題名は具体的にお願いします。
これは、ファイルの入出力ではなく、ソートの問題でしょう。

> 学校の課題はある程度ご自分の解き方をお示しください。
> なるべく詳しく環境などの情報をお書きください。 
これが一切記載されていません。


No.11698

Re:ファイルの入出力
投稿者---無限(2004/01/12 22:17:49)


>【掲示板ご利用上の注意】を実践しましょう。
>
>> 題名は具体的にお願いします。
>これは、ファイルの入出力ではなく、ソートの問題でしょう。

RAPTさん申し訳ありませんでした。
この課題は選択ソート等を使用し、また辞書式で比較するためstrcmpを使用するものです。

>> 学校の課題はある程度ご自分の解き方をお示しください。
>> なるべく詳しく環境などの情報をお書きください。 
>これが一切記載されていません。

解き方は、ファイルの入出力部分しか分からず、これにどうやって選択ソート等を記載すれば良いのか分かりません。(Win XP、Borland bcc)

申し訳ありませんがお力を貸して下さい。

No.11699

Re:ファイルの入出力
投稿者---RAPT(2004/01/12 22:23:23)


選択ソートについてのアルゴリズムが分からなければ、
「選択ソート」でGoogle検索してみましょう。

ソートアルゴリズムは基本的なものなので、探せばいくらでも見つかります。

No.11700

Re:ファイルの入出力
投稿者---無限(2004/01/12 23:36:36)


RAPTさん。例えば下記のような選択ソートのコードだとすると、これをファイルの入出力コード上でどの部分にどのように記載すれば良いのでしょうか。それとstrcmpをどこに記載して良いのかも分かりません。
C言語を勉強して数ヶ月の未熟者です。申し訳ありません。

int main()
  {
      int i, a[30], k, mnp, tmp;
  
      for( i = 0;i < 30;i++ ){
        mnp = i;
        for( k = i+1 ; k < 30; k++ ){
          if( a[k] < a[mnp] ) mnp = k;
      }
        tmp = a[i]; a[i] = a[mnp]; a[mnp] = tmp;
    }


No.11710

Re:ファイルの入出力
投稿者---NykR(2004/01/13 10:53:11)


> ファイルの入出力コード上でどの部分にどのように記載すれば良いのでしょうか。

ファイルの内容をすべて配列に格納 --> 配列をソート
という順序になりますから、入力の終わった後ですね。

> それとstrcmpをどこに記載して良いのかも分かりません。

strcmpは大きさ比較する関数ですから大きさを比較するところに記載すれば良いです。

> 例えば下記のような選択ソートのコードだとすると、

    int main()
      {
          int i, a[30], k, mnp, tmp;
  
          for( i = 0;i < 30;i++ ){
            mnp = i;
            for( k = i+1 ; k < 30; k++ ){
              if( a[k] < a[mnp] ) mnp = k;
          }
            tmp = a[i]; a[i] = a[mnp]; a[mnp] = tmp;
        }


これは選択ソートではありません。

No.11776

Re:ファイルの入出力
投稿者---かずま(2004/01/15 02:50:42)


>   int main()
>     {
>         int i, a[30], k, mnp, tmp;
> 
>         for( i = 0;i < 30;i++ ){
>           mnp = i;
>           for( k = i+1 ; k < 30; k++ ){
>             if( a[k] < a[mnp] ) mnp = k;
>         }
>           tmp = a[i]; a[i] = a[mnp]; a[mnp] = tmp;
>       }
>
> これは選択ソートではありません。
 
なぜですか?  選択ソートのはずです。

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

#define L  1000

typedef struct { char *name; int ber; } Entry;

int compare(const Entry *a, const Entry *b)
{
    return (a->ber != b->ber) ? (b->ber - a->ber) : strcmp(a->name, b->name);
}

void selection_sort(Entry a[], int n)
{
    Entry tmp;  int i, j, m;

    for (i = 0; i < n-1; i++) {
        m = i;
        for (j = i+1; j < n; j++)
            if (compare(a+j, a+m) < 0) m = j;
        if (m != i)
            tmp = a[i], a[i] = a[m], a[m] = tmp;
    }
}

int main(int argc, char *argv[])
{
    FILE *fp1, *fp2;  Entry a[L];  char name[50];  int  i, n;

    if (argc != 3) puts("usage: prog infile outfile"), exit(1);
    fp1 = fopen(argv[1], "r");
    if (fp1 == NULL) printf("can't open %s\n", argv[1]), exit(1);
    fp2 = fopen(argv[2], "w");
    if (fp2 == NULL) printf("can't create %s\n", argv[2]), exit(1);

    for (n = 0; n < L; n++) {
        if (fscanf(fp1, "%49s%d", name, &a[n].ber) != 2) break;
        a[n].name = strdup(name);
    }

    selection_sort(a, n);

    for (i = 0; i < n; i++)
        fprintf(fp2, "%-10s %5d\n", a[i].name, a[i].ber);

    return 0;
}


No.11781

Re:ファイルの入出力
投稿者---NykR(2004/01/15 09:41:39)


> なぜですか? 選択ソートのはずです。

あ゛、寝呆けていた様です。失礼しました。

No.11764

Re:ファイルの入出力(マージソート)
投稿者---無限(2004/01/14 22:57:16)


以前、投稿した課題を以下のようにコード化しましたが、data2.txtに出力した際、出力例のようにどうしても数値データの並びが統一されません。
どうしてでしょうか。それとこのコードでもっと簡素化できる部分がありましたらレス願います。(Win XP)


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

  #define L 1000
  #define R 1000
  #define M 50
  #define W 50

  void merge_sort_a(int a[],int x[],int s,int e)
  {
    int m,tmp,i,j,k,temp[L];

    if( e==s ) return;
    if( e==s+1 ) {
      if( a[x[s]]<a[x[e]] ) { tmp=x[s]; x[s]=x[e]; x[e]=tmp; }
      return;
    }
    m=(s+e)/2;

    merge_sort_a(a,x,s,m);
    merge_sort_a(a,x,m+1,e);

    for( i=s; i<=m; i++ )
      temp[i]=x[i];
    for( i=m+1, j=e; i<=e; i++, j-- )
      temp[i]=x[j];

    i=s; j=e;

    for( k=s; k<=e; k++ ) { 
      if( a[temp[i]]>=a[temp[j]] )
        x[k]=temp[i++];
      else
        x[k]=temp[j--];
    }
  }

  void merge_sort_b(char a[][M],int x[],int s,int e)
  {
    int m,tmp,i,j,k,temp[L];

    if( e==s ) return;
    if( e==s+1 ) {
      if( strcmp(a[x[s]],a[x[e]])>0 ) { tmp=x[s]; x[s]=x[e]; x[e]=tmp; }
      return;
    }
    m=(s+e)/2;

    merge_sort_b(a,x,s,m);
    merge_sort_b(a,x,m+1,e);

    for( i=s; i<=m; i++ )
      temp[i]=x[i];
    for( i=m+1, j=e; i<=e; i++, j-- )
      temp[i]=x[j];

    i=s; j=e;

    for( k=s; k<=e; k++ ) {
      if ( strcmp(a[temp[i]],a[temp[j]])<=0 )
        x[k]=temp[i++];
      else
        x[k]=temp[j--];
    }
  }

  int main()
  {
     FILE *fp1,*fp2;
    char buf[R], num[W];
    char name[L][M];
    int  ber[L],x[L];
    int  i,j,k,n,a;
    

    fp1=fopen("data.txt", "r");
    fp2=fopen("data2.txt", "w");

    n=0;
    while( fgets(buf, L, fp1)!=NULL ) {
      i=j=0;
      a=0;

      while(1) {
        if ((buf[i]!=' ')&&(buf[i]!='\n')&&(buf[i]!='\0')) {
          if(a==0) {
            a=1;
          }
          name[n][j]=buf[i];
          i++; j++;
        }else if(buf[i]==' ') { 
          if(a==1) {
            name[n][j]='\0'; break;
          }
        }else{
          break;
        }
      }
      if (a==0) {
        break;
      }

      a=0;
      while(1) {
        if((buf[i]!= ' ')&&(buf[i]!='\n')&&(buf[i]!='\0')) {
          if(a==0) {
            a=1;
          }
          num[j]=buf[i];
            i++; j++;
        }else{
          if(a==1) { 
            num[j]='\0';
            ber[n]=atoi(num);
          }  
          if((buf[i]=='\n')||(buf[i]=='\0')) {
            break;
          }else{
            i++; j=0;
          }
        }
      }
      x[n]=n;
      n++;
    }
    fclose(fp1);

    merge_sort_b(name,x,0,n-1);
    merge_sort_a(ber,x,0,n-1);

    for( i=0; i<n; i++ ) {
      fprintf(fp2, "%s  %d\n",name[x[i]],ber[x[i]]);
    }
    fclose(fp2);

  return 0;
  }


【出力例】
>prog data.txt

Sato  200
Kawano  150
Saiki 80
Tokio   50
Tokyo   50

    ↑こんな感じです。


No.11775

Re:ファイルの入出力(マージソート)
投稿者---かずま(2004/01/15 02:35:06)


> それとこのコードでもっと簡素化できる部分がありましたらレス願います。
#include <stdio.h>
#include <stlib.h>
#include <string.h>

#define L  1000

typedef struct { char *name; int ber; } Entry;

int compare(const Entry *a, const Entry *b)
{
    return (a->ber != b->ber) ? (a->ber - b->ber) : strcmp(a->name, b->name);
}

void merge_sort(Entry a[], int s, int e)
{
    int m, i, j, k;  Entry tmp, temp[L];

    if (e == s) return;
    if (e == s+1) {
        if (compare(a+s, a+e) < 0)
            tmp = a[s], a[s] = a[e], a[e] = tmp;
        return;
    }
    m = (s + e) / 2;
    merge_sort(a, s, m);
    merge_sort(a, m+1, e);
    for (i = s; i <= m; i++) temp[i] = a[i];
    for (i = m+1, j = e; i <= e; i++, j--) temp[i] = a[j];
    i = s;  j = e;
    for (k = s; k <= e; k++)
        a[k] = temp[(compare(temp+i, temp+j) >= 0) ? i++ : j--];
}

int main(void)
{
    FILE *fp1, *fp2;  Entry a[L];  char name[50];  int i, n;

    fp1 = fopen("data.txt", "r");
    if (fp1 == NULL) puts("can't open data.txt"), exit(1);
    fp2 = fopen("data2.txt", "w");
    if (fp1 == NULL) puts("can't create data2.txt"), exit(1);

    for (n = 0; n < L; n++) {
        if (fscanf(fp1, "%49s%d", name, &a[n].ber) != 2) break;
        a[n].name = strdup(name);
    }

    merge_sort(a, 0, n-1);

    for (i = 0; i < n; i++)
        fprintf(fp2, "%-10s %5d\n", a[i].name, a[i].ber);

    return 0;
}


No.11913

Re:ファイルの入出力(マージソート)
投稿者---無限(2004/01/18 17:38:20)


ありがとうございました。
参考になりました。

No.11916

Re:ファイルの入出力(マージソート)
投稿者---かずま(2004/01/18 22:16:10)


> 参考になりました。

どの辺が参考になったかを書いてほしかったんですが。

バグが 4つぐらいあるんですが、わかりますか?
ただし、free() と fclose() がないのはバグではありません。

No.11952

Re:ファイルの入出力(マージソート)
投稿者---無限(2004/01/19 23:04:52)


>どの辺が参考になったかを書いてほしかったんですが。

大変失礼致しました。
構造体を使用すると言ったところでしょうか。

>バグが 4つぐらいあるんですが、わかりますか?
>ただし、free() と fclose() がないのはバグではありません。

現在このところを見直ししているところで、一つずつ減らしています。