lab5

lab5A

・・・・途中経過

#ref error ：指定ページの閲覧権限がありません。ログインするか、別のページの画像ファイルを指定してください。

ポインタ使ってむずいので、とりあえず教科書写して配列を使ったやつを
載せときます

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

#define N 500

void deletemin(int *A,int *n);//ヒープ内の一番小さい数をけす
void downmin(int i,int *A,int n);//木をヒープの順に並び変える
void swap(int i,int j,int *A);//配列A[i]とA[j]を入れ替える
void insert(int x,int *A,int *n);//木に新しい要素を入れる
void upmin(int i,int *A,int n);//ヒープの数を比較し、親の方が大きかったとき入れ替える

int main(int argc,char *argv[])
{
	FILE *fp;
 	fp = fopen("../aaa.txt","r");//テキストを開く
	int A[N];
	int a,b,n=0,i,m,temp,j,k;
	fscanf(fp,"%d",&a);//要素の数を決める
	for(i=0;i<a;i++){//要素の数だけまわす
		fscanf(fp,"%d",&b);//新しい要素に入れる数
		printf("\ninput:%d",b);
		insert(b,A,&n);//新しい要素を作る
		printf("\n");
//===========３角形に表示（入れた後を表示）==========================================================-
		temp=1;
		for(j=1;j<=n;j++){
			if(temp==j){
				if(j!=1) printf("\n");
			temp*=2;
			}
			printf(" %d",A[j-1]);
		}
//===============================================================
	}
	while(n>=0){
	deletemin(A,&n);//最小値を消す
	printf("\n");
//====================三角形に表示(消した後を表示)==============================================
	temp=1;
		for(j=1;j<=n;j++){
			if(temp==j){
				if(j!=1) printf("\n");
			temp*=2;
			}
			printf(" %d",A[j-1]);
		}
//=====================================================================
 	}
	fclose(fp);
} 

//ヒープ内の一番小さい数をけす
	void deletemin(int *A,int *n)
	{
		int min,n1;
		n1= *n;
		if(n1<1){//要素の数が1より小さいとき
			printf("Error: Heap is empty.\n");
			exit(1);
		}
		min=A[0];A[0]=A[n1-1];//最小値を消す
		if(n1>1) downmin(0,A,n1-1);
		printf("\ndelete:%d",min);
		*n=n1-1;//全体の要素数をへらす
	}

//木をヒープの順に並び変える
	void downmin(int i,int *A,int n)
	{
		int j;
		if(i<0 || i>=n)
		{
			printf("Illegal element i=%d for n=%d\n",i,n);exit(1);
		}
		j=2*i+1;
		if(j>=n) return;
 		if(j+1<n && A[j]>A[j+1]) j=j+1;

		if(A[j]<A[i])
		{
			swap(i,j,A);//入れ替え
			downmin(j,A,n);//並び替え
		}
		return;
	}

	void swap(int i,int j,int *A)
	{
		int temp;
		temp=A[i];A[i]=A[j];A[j]=temp;
		return;
	}
//木に新しい要素を入れる
void insert(int x,int *A,int *n)
{ 
	int n1;
	n1=*n;
	if(n1>=N)
	{
		printf("Error: Heap A is full.\n");
		exit(1);
	}
	A[n1]=x;
	upmin(n1,A,n1+1);
	*n=n1+1;
	return;
}  
 
//ヒープの数を比較し、親の方が大きかったとき入れ替える
void upmin(int i,int *A,int n)
{ 
	int j;
	if(i<0 || i>=n)
	{
		printf("Illegal element i=%d for n=%d\n",i,n);exit(1);
	}
	if(i==0) return;
	j=(i-1)/2;
	if(A[j]>A[i])
	{
		swap(i,j,A);//入れ替え
		upmin(j,A,n);//並び替え
	}
	return;
}

//==================================
//実行結果
//==================================
/*
input:8
 8
input:4
 4
 8
input:1
 1
 8 4
input:6
 1
 6 4
 8
input:3
 1
 3 4
 8 6
input:7
 1
 3 4
  8 6 7
input:9
 1
 3 4
 8 6 7 9
input:0
 0
 1 4
 3 6 7 9
 8
input:5
 0
 1 4
 3 6 7 9
 8 5
input:2
 0
 1 4
 3 2 7 9
  8 5 6
delete:0
 1
 2 4
 3 6 7 9
 8 5
delete:1
 2
 3 4
 5 6 7 9
 8
delete:2
 3
 5 4
 8 6 7 9
delete:3
 4
 5 7
 8 6 9
delete:4
 5
 6 7
 8 9
delete:5
 6
 8 7
 9
delete:6
 7
 8 9
delete:7
 8
 9
delete:8
 9
delete:9
Error: Heap is empty.
続行するには何かキーを押してください . . .