• 締切済み

最小ヒープソートについて

問題:numbers.datから10個の整数を読みこみヒープソートで昇順に表示せよ。 numbers.dat 91 63 71 14 60 1 24 13 80 15 質問:下記が自分のコードなんですが実行すると 1 13 13 13 13 13 13 13 13 13になるんですが、何を直せばいいでしょうか。最小の値を取り出していくようにしているつもりなんですが #include<stdio.h> #include<stdlib.h> void insert( int i,int a[], int n); int deletemin(int a[], int n,int m); int main() { int a[10],m[10]; int i,j,k; int n = 10; FILE *fp; fp = fopen("numbers.dat", "r"); if(fp == NULL) { printf("ファイルが開けません\n"); return 1; } fscanf(fp,"%d %d %d %d %d %d %d %d %d %d\n",&a[0] ,&a[1] ,&a[2] ,&a[3] ,&a[4] ,&a[5] ,&a[6] ,&a[7] ,&a[8],&a[9] ); for(i = (n - 2)/2; i >= 0; i--) { insert(i, a, n-1); } for(i = n-1; i >= 0; i-- ) { m[9-i] = deletemin(a, i, n-1); } for(j = 0; j < 10; j++){ printf("%3d",m[j]); } return 0; } void insert( int i,int a[], int n) { int j; int temp; while (2 * i + 1 <= n) { j = 2 * i + 1; if (j < n) { if (a[j] > a[j + 1]) { j++; } } if (a[i] <= a[j]) { break; } temp = a[j]; a[j] = a[i]; a[i] = temp; i = j; } } int deletemin(int a[],int n, int m) { int b; int temp; int i,j; b = a[0]; a[0] = a[n]; i = 0; while (2 * i + 1 <= m) { j = 2 * i + 1; if (j < m) { if (a[j] > a[j + 1]) { j++; } } if (a[i] <= a[j]) { break; } temp = a[j]; a[i] = a[j]; a[i] = temp; i = j; } return b; }

みんなの回答

  • jjon-com
  • ベストアンサー率61% (1599/2592)
回答No.2
全文を見る
すると、全ての回答が全文表示されます。
  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

「何を直せばいいか」を考えるためには「どこが悪いのか」を知る必要があります. そのための努力はしたんですか? あと, せめて各関数の仕様は書いてほしい.

全文を見る
すると、全ての回答が全文表示されます。

関連するQ&A

  • 一次元配列で表現された最小ヒープの値挿入

    問題文:ヒープに新たなデータを挿入する関数insertを作成せよ。空の配列に複数回insertを行うことで 構成したヒープがヒープ条件を満たしていることをcheck_heapを用いることで確認せよ。プロトタイプ宣言は以下とする。 void insert(int val, int a[],int *n); 質問:  複数回はおいといてとりあえず1回insertしようと思って書いたんですが、ヒープの最後に新しいノードを 作って親より小さければ親の値と交換を繰り返してヒープを完成させようとしてるんですが、1回しか交換されません。 どうすればいいですか?check_heapは最小ヒープ条件が満たされていれば1を満たされていなければ0を返す関数です。 自分のソース #include<stdio.h> #include<stdlib.h> #include<time.h> int check_heap(int a[], int n); void insert(int val, int a[], int *n); int main(void) { int a[11] = {1,13,71,14,15,80,91,24,60,63}; int n; int i; int b,c; srandom(time(NULL)); b = random() % 100 + 1; n = 10; insert(b, a, &n); printf("%d\n", check_heap(a, 11)); for(i = 0; i < 11; i++){ printf("%3d", a[i]); } return 0; } int check_heap(int a[], int n) { int i; int m; m = (n - 1) / 2; for(i = 0; i < m; i++) { if(a[i] >= a[i * 2 + 1]) { return 0; } if(a[i] >= a[i * 2 + 2]){ return 0; } } if(n % 2 == 0){ if(a[(n - 1)/2] > a[n - 1]){ return 0; } } return 1; } void insert(int val, int a[], int *n) { int temp; a[*n] = val; while(a[(*n-1) / 2] >= a[*n]){ temp = a[(*n-1) / 2]; a[(*n-1) / 2] = a[*n]; a[*n] = temp; } }

  • ヒープソートがわかりません

    以下のようなヒープソートのプログラムを作ったのですが、どうしても動きません。 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define NS 3000000 /* 入力の最大数 */ #define WC 64 /* 入力の1行の文字数 */ void down(int from, int to); void heapsort(int s[NS+1][WC], int n); void down(int from, int to){ int i, j; int val; int s[NS+1][WC]; i = from; val = s[from][WC]; while(i <= to/2){ j = i*2; if(j+1 <= to && s[j] > s[j+1]) j++; if(val <= s[j][WC]) break; s[i][WC] = s[j][WC]; i = j; } s[i][WC] = val; } void heapsort(int s[NS+1][WC], int n) { int i; int tmp; for(i = n/2; i >= 1; i--) down(i, n); for(i = n; i >=2; i--){ tmp = s[1][WC]; s[1][WC] = s[i][WC]; s[i][WC] = tmp; down(1, i-1); } } main(int argc, char *argv[]) { FILE *fp; char s[NS][WC], buff[WC]; int i=0,n=0; if ((argc==1) || (argc>=3)) { printf("Input filename\n"); exit(1); } fp=fopen(argv[1],"r"); while(fgets(buff, sizeof(buff),fp)!=NULL){ sscanf(buff,"%s",&s[i]); i=n; } printf("File reading completed.\n"); heapsort(s[NS+1][WC],n); for (i=0; i<n; i++) { if (strcmp(A1[i],A2[i])!=0) { printf("Results are incorrect!\n"); exit(1); } } printf("Results are correct.\n"); fclose(fp); exit(0); }

  • ヒープ deleteminの関数作成がわかりません

    問題文:ヒープの最小値を取り除く、deletemin関数を作成せよ。空の配列にinsertを複数実行することでヒープ条件を満たすヒープを構成する。これにdeleteminを実行することで最小値を抽出せよ。最小値を抽出した後、一次元配列がヒープ条件を満たすように再構成せねばならない。プロトタイプ宣言は以下とする。 int deletemin(int a[], int *n); 質問:関数deleteminについて調べてはみたんですが何をしているのか分からないものばかりだったので質問させてください。ヒープの最後のノードを根に持ってきて、右のノードと左のノードを比べて小さい値のノードの方と比較して最後から持ってきたノードの値の方が大きければ交換するというの繰り返して最小ヒープを再構成したいのですが、どうすればいいのかわかりません。サイトなどみても分からなかったのでど素人でも分かるように説明お願いします。 以下自分のソース #include<stdio.h> #include<stdlib.h> #include<time.h> int check_heap(int a[], int n); void insert(int val, int a[], int *n); int deletemin(int a[],int *n); int main(void) { int a[12] = {1,13,71,14,15,80,91,24,60,63}; int n; int i; int b,c; srandom(time(NULL)); b = random() % 100 + 1; n = 10; insert(b, a, &n); n = 11; c = random() % 100 + 1; insert(c, a, &n); printf("%d\n", check_heap(a, 12)); deletemin(a, &n); return 0; } int check_heap(int a[], int n) { int i; int m; m = (n - 1) / 2; for(i = 0; i < m; i++) { if(a[i] >= a[i * 2 + 1]) { return 0; } if(a[i] >= a[i * 2 + 2]){ return 0; } } if(n % 2 == 0){ if(a[(n - 1)/2] > a[n - 1]){ return 0; } } return 1; } void insert(int val, int a[], int *n) { int temp; int i; a[*n] = val; i = *n; while( 0 < i){ if(a[(i-1)/2] <= a[i]) { break; } temp = a[(i-1) / 2]; a[(i-1) / 2] = a[i]; a[i] = temp; i = (i - 1)/2; } } int deletemin(int a[],int *n){ int b; int i,j,k; b = a[0]; return b; }

  • printfの挿入箇所

    #include <stdio.h> #include <stdlib.h> #define N 500 void bubblesort(int h, int k, int *A); void swap(int i, int j, int *A); int main(void) { int A[N]; int n, i; FILE *file; file=fopen("sortdata", "r"); /* データの読込み */ fscanf(file, "%d", &n); if(n>N) { printf("Illegal array size n = %d for N = %d\n", n, N); exit(1); } for(i=0; i<n; i++) fscanf(file, "%d", &A[i]); /**/ printf("A = "); /**/ printf("\n"); bubblesort(0, n-1, A); /* 配列A[0]からA[n-1]の整列 */ return(0); } /* A[k],...,A[h]の要素をバブルソートによって整列 */ void bubblesort(int h, int k, int *A) { int i, j, p; int no; int test; /* test==1; すでに整列済み */ for(i=h; i<k; i++) /* バブル操作の反復 */ { test=1; for(j=k; j>=i+1; j--) { for(no=0; no<j; no++) printf(" %d",A[no]); if(A[j]<A[j-1]) { printf(" > %d ",A[j]); swap(j, j-1, A); test=0; } else { printf(" < %d ",A[j]); } for(no=j+1; no<=k; no++) printf(" %d ",A[no]); printf("\n"); } printf("\n"); if(test==1) return; } return; } /* Swap A[i] and A[j]. */ void swap(int i, int j, int *A) { int temp; temp=A[i]; A[i]=A[j]; A[j]=temp; return; } 以上のプログラムを A = パス1: 7 5 1 2 8 > 3 7 5 1 2 < 3 8 7 5 1 < 2 3 8 7 5 > 1 2 3 8 7 > 1 5 2 3 8 1 7 5 2 3 8 パス2: 1 7 5 2 3 < 8 1 7 5 2 < 3 8 1 7 5 > 2 3 8 1 7 > 2 5 3 8 1 2 7 5 3 8 パス3: 1 2 7 5 3 < 8 1 2 7 5 > 3 8 1 2 7 > 3 5 8 1 2 3 7 5 8 パス4: 1 2 3 7 5 < 8 1 2 3 7 > 5 8 1 2 3 5 5 8 パス5: 1 2 3 5 7 < 8 1 2 3 5 7 8 比較は15回でした。 交換は8回でした。 と表示させたいのですがうまくいきません。 どなたかご指導よろしくお願いします

  • c言語についての質問です

    #include<stdio.h> #define N 3 void inputAns(int *row,int *col,int data[][N]); void printAns(int ID,int data[][N]); int main(){ int row[N]={2,3,6},col[N]={8,5,3},answer[N][N]; int i,ID; printf("Input your ID number :\n"); scanf("%d",&ID);inputAns(row,col,answer); printAns(ID,answer); return(1); } void inputAns(int *row,int *col,int data[][N]){ int i,j; printf(" Input Answers of matrxi Q :\n"); for(i=0;i<N;i++){ for(j=0; j<N; j++){ printf("%2d+%2d=",row[i],col[j]); scanf("%d",&data[i][j]); } } } void printAns(int ID, int data[][N]){ FILE *fp; int i,j; fp=fopen("ans.dat","a+t"); fprintf(fp,"%d\n",ID); for(i=0; i<N; i++){ for(j=0; j<N; j++) fprintf(fp," %3d",data[i][j]); fprintf(fp,"\n"); } fclose(fp); } この百マス計算のプログラムの28行目からを書き換えて以下のような画面出力を求めたいです。 >./a.exe ID=50413001 [ 9/9 ] ID=50413002 [ 5/9 ] ID=50413003 [ 7/9 ] ID=50413004 [ 6/9 ] ID=50413005 [ 5/9 ] == correct rate === 4/5 3/5 5/5 5/5 1/5 4/5 4/5 1/5 5/5 =================== > 読み込むファイル(ans.dat)は以下のものです。 50413001 10 7 5 11 8 6 14 11 9 50413002 10 7 5 11 9 5 13 10 9 50413003 10 7 5 11 5 6 14 10 9 50413004 10 11 5 11 5 6 14 10 9 50413005 9 11 5 11 5 6 14 10 9 読み込みから集計がうまくいかず困っています。 どなたか教えてくれませんか?

  • CでBAモデルを作りたいのですが

    複雑ネットワークの勉強をしている者です。 Cでバラバシモデルの作成を行っておりますが、Pajekを使いCで書いたプログラムを動かしたいのです。 しかし、最終頂点数が20を超えると動かなかったり、クラスター係数が出なくなったりします。 原因は、 (1)i,jの値が重なっている (2)同じ組み合わせが出現する ことだと思われます。 (1)(2)が出なくなるプログラムにする方法を教えてください。 #include <stdio.h> #include <stdlib.h> #include <time.h> void ba_model(int N, int m0, int m); int sum(int *data, int n); int main(int argc, char *argv[]) { int N; int m0=atoi(argv[1]); int m=atoi(argv[2]); char filename[18]="ba_model.net"; FILE *fp; if(argc == NULL) exit(0); printf("Input Vertex Size: "); scanf("%d", &N); printf("Vertex Size: %d\n",N); printf("Initial Vertex: %d\n",m0); printf("Edge Number: %d\n",m); fp=fopen(filename, "w"); fprintf(fp, "*Vertices %d\n", N); fprintf(fp, "*Edges\n"); fclose(fp); ba_model(N, m0, m); return 0; } void ba_model(int N, int m0, int m) { int i, j, n; int output_degree[100]; int edge_number; double p; char filename[18]="bamodel.net"; FILE *fp; fp=fopen(filename, "a"); if(fp==NULL) { printf("Error FileOpen\n"); } else { printf("FileOpen OK:%s\n",filename); } srand(time(NULL)); printf("乱数初期化OK\n"); printf("N=%d, m0=%d, m=%d\n",N,m0,m); for(i=0; i<N; i++) { edge_number=0; for(j=m0; j<N; j++) { p=(double)(output_degree[j]+1)/(double)sum(output_degree, i); printf("p(%d)=%lf\n",j,p); if(p > (double)rand()/RAND_MAX) { output_degree[i]++; output_degree[j]++; edge_number++; if((i+1)!=(j+1)) { printf("%d %d 1\n", i+1, j+1); }else{ break; } } if( m < edge_number ) break; } } fclose(fp); } int sum(int *data, int n) { int k; int sum=0; printf("In Sum: n=%d\n",n); if(n==0) { sum = 1; } for(k=0; k<n; k++) { printf("k=0 n=0\n"); sum = sum + data[k] + 1; } return sum; }

  • C言語<素数を求めるプログラム>

    #include<stdio.h> int j; int prime(int n) { int i; if(n < 2) return 0; if(n == 2) return 1; if(n%2 == 0) return 0; for(i = 3; i*i<= n; i += 2){ if(n%i == 0) return 0; } return 1; } int main(void) { int n; for(n=1; n <= 1000; n++) { if(prime(n)){ printf("%d\n",n); j++; } } printf("素数の個数は全部で %d 件見つかりました。\n",j); return 0; } このプログラムは1から1000までの素数のみを表示させるプログラムでありますが、このアルゴリズムが全くわかりません。 int prime(int n)の中身のアルゴリズムがどういう仕組みになっているのかお分かりになりますでしょうか?

  • 行列の積を計算するプログラムがうまくいきません

    どこが間違っているのかわかる方お願いします ・行列A,Bはファイルから読み込む ・行列A,Bの積Cの計算には関数を用いる #include<stdio.h> #define ROW 10 #define COL 10 void MatrixProduct(int a[][COL],int b[][ROW],int c[][ROW],int n,int m ) { int i,j,k; for(i=0;i<n;i++){ for(j=0;j<n;j++){ c[i][j]=0; } } for(i=0;i<n;i++){ for(j=0;j<n;j++){ for(k=0;k<m;k++){ c[i][j]=c[i][j]+a[i][k]*b[k][j]; } } } } int main(void) { FILE *fp1,*fp2; char fname1[64],fname2[64]; int a[ROW][COL],b[ROW][COL],c[ROW][COL],n,m; int i,j,k; printf("Input file name ?"); scanf("%s",fname1); printf("Output file name ?"); scanf("%s",fname2); fp1=fopen(fname1,"r"); fp2=fopen(fname2,"w"); fscanf(fp1,"%d %d",&n,&m); MatrixProduct(a,b,c,n,m); for(i=0;i<n;i++){ for(j=0;j<n;j++){ fprintf(fp2,"%3d",c[i][j]); } fprintf(fp2,"\n"); } fclose(fp1); fclose(fp2); return(0); } fp1 3 4 1 2 3 4 2 3 4 5 3 4 5 6 1 2 3 2 3 4 3 4 5 4 5 6

  • C言語のソートプログラム

    学校でプログラミングの課題が出たので自分のパソコンに Microsoft Visual C++ 2010 Express をインストールして作ってみました。 それが以下のプログラムです。 これは任意の値nを入力してa[n]までの配列をつくり それを降順に並び替えるものです。 #include <stdio.h> #define N 10000 int main(){ int a[N],i,j,max,min,n,temp; n=0; printf("n="); scanf("%d",&n); if(N<n){ return 0; } else if(n<=0){ return 0; } else if(n<=N){ for(i=0;i<n;i++){ printf("a[%d]",i); scanf("%d",&a[i]); } max=min=a[0]; for(i=1;i<n;i++){ if(max<a[i]){ max=a[i]; } else if(min>a[i]){ min=a[i]; } } printf("a[i]のソート結果\n"); for(i=0;i<n;i++);{ for(j=i+1;j<n;j++){ if(a[i]<a[j]){ temp=a[i]; a[i]=a[j]; a[j]=temp; } } } for(i=0;i<n;i++){ printf("a[%2d]=%d\n",i,a[i]); } printf("Max=%d\n",max); printf("Min=%d\n",min); } } これを実行すると 最初に入力した配列の順番のまま表示されてしまいます。 例えば n=4 a[0]7 a[1]4 a[2]6 a[3]1 a[i]のソート結果 a[0]7 a[1]4 a[2]6 a[3]1 のようにです。 しかしプログラミング上では for(i=0;i<n;i++);{ for(j=i+1;j<n;j++){ if(a[i]<a[j]       temp=a[i];       a[i]=a[j];            a[j]=temp;        }        }        } のようにiとjを比較して a[0]がa[1]より大きければa[0]とa[1]を交換する。 あとはa[0]とa[2], a[0]とa[3]...a[3]とa[4]まで for文の続く限り繰り返すように書いたはずです。 まだ勉強し始めた私にはどこが間違っているのか分からないので 分かる方はご指摘をお願いします。

  • C言語のプログラムについてご指導願えますか?

    ファイルを読み込み、そのなかにI,We,You,He,She,Theyの単語がいくつかるかカウントするプログラムを作成したいのですが、単語のカウントがうまくできません。 下記に作成したソースを記載しますので、間違っている箇所を指摘していただけませんか? #include <stdio.h> #include <stdlib.h> #include <string.h> int main( void ) { char filename[FILENAME_MAX]; int j=0; int k=0; int l=0; int m=0; int n=0; int o=0; FILE *fp; gets(filename); fp = fopen(filename,"r"); { if(fp==NULL) { printf("ERROR"); return -1; } if(strcmp("I",fp)==0) { j++; } if(strcmp("We",fp)==0) { k++; } if(strcmp("You",fp)==0) { l++; } if(strcmp("He",fp)==0) { m++; } if(strcmp("She",fp)==0) { n++; } if(strcmp("They",fp)==0) { o++; } } printf("I: %d\n",j); printf("We: %d\n",k); printf("You: %d\n",l); printf("He: %d\n",m); printf("She: %d\n",n); printf("They: %d",o); fclose(fp); return 0; }