lab8 - なんだかいろいろウィキ

lab8

• ビジュアルスタジオ用

  #include<stdio.h> 
  #include<stdlib.h>
  #define N 10000
  #define m 10
  #define K 5
  void radixsort(struct word *A,int *idx,int n);
  void bucketsort(struct word *A,int *idx,int n,int k);
  void insert(struct word *A,int idx,struct cell **B,int k);
  
  struct word{
  	int letter[K];
  };
  struct cell{
  	int index;
  	struct cell *next;
  };
  int main(int argc,char* argv[]){
  	int n;
  	int b,d,i,j;
  	FILE *fp;
  	fp=fopen("../aaa.dat","r");
  	struct word A[N];
  	int idx[N];
  	fscanf(fp,"%d", &n);
  	for(i=0;i<n;i++){
  		fscanf(fp,"%d", &b);
  		for(int j=K-1;j>=0;j--){
  			d=b%10;
  			b=(b-d)/10;
  		A[i].letter[j]=d;
  
  		//for(j=0;j<K;j++)printf("%d ",A[idx[i]].letter[j]);//格納された配列の表示
  
  
  		}
  		idx[i]=i;
  	}
  	radixsort(A,idx,n);
  	for(i=0;i<n;i++){
  		for(int j=0;j<K;j++)printf("%d",A[idx[i]].letter[j]);//整列後の配列の表示
  		printf("\n");
  	}
  	fclose(fp);
  } 
  void radixsort(struct word *A,int *idx,int n){
  	int k;
  	for(k=K-1;k>=0;k--) bucketsort(A,idx,n,k);
  	return;
  }
  void bucketsort(struct word *A,int *idx,int n,int k){
  	struct cell *B[m];
  	struct cell *p,*q;
  	int i,j;
  	for(j=0;j<m;j++) B[j]=NULL;
  	for(i=0;i<n;i++) insert(A,idx[i],B,k);
  	i=n-1;
  	for(j=m-1;j>=0;j--){
  		p=B[j];
  		while(p!=NULL)
  		{
  			idx[i]=p->index;
  			i=i-1;
  			q=p->next;
  			free(p);
  			p=q;
  		}
  	}
  	return;
  } 
  void insert(struct word *A,int idx,struct cell **B,int k){
  	struct cell *p;
  	p=(cell *)malloc(sizeof(cell));
  	p->index=idx;
  	p->next=B[A[idx].letter[k]];
  	B[A[idx].letter[k]]=p;
  	return ;
  } 
  

• テラパッド用（推奨）

  #include<stdio.h> 
  #include<stdlib.h>
  #define N 10000
  #define m 10
  #define K 5
  
  struct word{
  	int letter[K];
  };
  struct cell{
  	int index;
  	struct cell *next;
  };
  
  void radixsort(struct word *A,int *idx,int n);
  void bucketsort(struct word *A,int *idx,int n,int k);
  void insert(struct word *A,int idx,struct cell **B,int k);
  
  int main(int argc,char* argv[]){
  	int n;
  	int b,d,i,j;
  	FILE *fp;
  	fp=fopen("rand1000.dat","r");
  	struct word A[N];
  	int idx[N];
  	fscanf(fp,"%d", &n);
  	for(i=0;i<n;i++){
  		fscanf(fp,"%d", &b);
  		for(j=K-1;j>=0;j--){
  			d=b%10;
  			b=(b-d)/10;
  		A[i].letter[j]=d;
  		}
  		idx[i]=i;
  	}
  	radixsort(A,idx,n);
  	for(i=0;i<n;i++){
  		for(j=0;j<K;j++)printf("%d",A[idx[i]].letter[j]);
  		printf("\n");
  	}
  	fclose(fp);
  } 
  void radixsort(struct word *A,int *idx,int n){
  	int k;
  	for(k=K-1;k>=0;k--) bucketsort(A,idx,n,k);
  	return;
  } 
  void bucketsort(struct word *A,int *idx,int n,int k){
  	struct cell *B[m];
  	struct cell *p,*q;
  	int i,j;
  	for(j=0;j<m;j++) B[j]=NULL;
  	for(i=0;i<n;i++) insert(A,idx[i],B,k);
  	i=n-1;
  	for(j=m-1;j>=0;j--){
  		p=B[j];
  		while(p!=NULL)
  		{
  			idx[i]=p->index;
  			i=i-1;
  			q=p->next;
  			free(p);
  			p=q;
  		}
  	}
  	return;
  }  
  void insert(struct word *A,int idx,struct cell **B,int k){
  	struct cell *p;
  	p=malloc(sizeof(struct cell));
  	p->index=idx;
  	p->next=B[A[idx].letter[k]];
  	B[A[idx].letter[k]]=p;
  	return ;
  }