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

lab12A

これはVisualStudioでは動かないけどTeraなんたらでは動きます。

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

struct NODE
{
	int data;
	struct NODE* next;
};
struct NODE head;


struct NODE* mergesort(struct NODE* x);
struct NODE* merge_list(struct NODE* x, struct NODE* y);
void addlist(int data);
void printlist(struct NODE* x);
 
 int main(int argc,char *argv[])
 {
 	head.next = NULL;
 	int a,b,i;
 	FILE *fp;
 	fp=fopen("aaa.dat","r");
 	fscanf(fp,"%d",&a);
 	for(i=0;i<a;i++){ 
		fscanf(fp,"%d",&b);
		addlist(b);
	}
	
	printlist( &head );   /* リストの内容を出力 */
	mergesort( &head );  /* マージソートを実行 */
	printlist( &head );   /* リストの内容を出力 */
 	fclose(fp);
	return 0;
}
  
struct NODE* mergesort(struct NODE* x)
{
	struct NODE *a, *b, *y;
	
	/* リストに含まれる要素数が０または１個のときは、ソートの必要がない */
	if( x == NULL || x->next == NULL ){ return x; }
	
	a = x;                           /* aは先頭の要素を指す */
	b = x->next;
	if( b != NULL ){ b = b->next; }  /* bは先頭から３番目の要素を指す */
	
	/* 線形リストを中心くらいから半分に分けるため、中心位置がどこにあるのか探る */
	while( b != NULL )
	{
		a = a->next;                     /* aは常に１つだけ進む */
		b = b->next;
		if( b != NULL ){ b = b->next; }  /* bは基本的に２つ進む */
	}
	

	y = a->next;
  	a->next = NULL;
	
 	return merge_list( mergesort( x ), mergesort( y ) );
}


 struct NODE* merge_list(struct NODE* x, struct NODE* y)
{
 	struct NODE z, *p;
 	
 	p = &z;  /* xとyをマージしてzを作り上げる */
 	 
	/* 分割されている２つのリストのいずれか一方が空になるまで繰り返す */
 	while( x != NULL && y != NULL )
	{
		/* ２つのリストの先頭要素同士を比較する */
		if( x->data <= y->data )
		{
			/* リストxの方の先頭要素を、マージ後のリストに連結する */
			p->next = x;
			p = x;
			x = x->next;
		}
		else
		{
			/* リストyの方の先頭要素を、マージ後のリストに連結する */
			p->next = y;
			p = y;
			y = y->next;
		}
	}
	
	/* 先に片方のリストが空になるので、残された方のリストの要素を、マージ後リストに連結する */
	if( x == NULL )
	{
		p->next = y;
	}
	else
	{
		p->next = x;
	}
	
 	return z.next;
}  
  
/*
	線形リストに要素を追加する。
	引数　data：追加したい要素の値。
*/
void addlist(int data)
{
	struct NODE* p, *q, *newcell;
	
	p = head.next;   /* 先頭要素の次の要素のアドレス */
	q = &head;       /* 先頭要素のアドレス */
	while( p != NULL )
	{
		q = p;         /* 追加位置の直前の要素のnextを後で設定するために、
			              追加位置の直前の要素のアドレスを記憶しておく */
		p = p->next;   /* 次の要素へ進む */
	}
	
	/* 新しく追加する要素のためのメモリ領域を確保する */
	newcell =malloc( sizeof(struct NODE) );
	if( newcell == NULL )
	{
		return;
	}
	
	newcell->data = data;  /* 新しい要素のデータを設定 */
	newcell->next = p;     /* 新しい要素の次の要素へのアドレスを設定 */
	q->next = newcell;     /* 新しい要素の直前の要素のnextに、新しい要素のアドレスを設定 */
}  

void printlist(struct NODE* x)
{
	struct NODE *p;
	
	for( p=head.next; p!=NULL; p=p->next )
	{
		printf( "%d\n", p->data );
	}
 	printf( "\n\n" );
} 
 

lab12B

#include<stdio.h>
#include<stdlib.h>
#define N 10000

void merge(int *A,int nA,int *B,int nB,int i,int *C){
 	int iA,iB,iC;
  	iA=iB=iC=0;
 	while(iC<=nA+nB-1){
 		if(iA>=nA){
 			C[i+iC]=B[iB];
 			iB=iB+1;
 		}
 		else{
  			if(iB>=nB){ 
				C[i+iC]=A[iA];
				iA+=1;
			}
			else{
					if(A[iA]<=B[iB]){
						C[i+iC]=A[iA];
						iA+=1;
					}
					else{
					C[i+iC]=B[iB];
					iB+=1;
					}
			}
		}
			iC+=1;
	}
		return;
}



void mergesort(int i,int j,int *A){
	int k,n,n1,n2,mid;
	int A1[N],A2[N];
	n=j-i+1;
	if(n>1){
		mid=i+(n-1)/2;
 		mergesort(i,mid,A);
		mergesort(mid+1,j,A);
		n1=mid-i+1;
		for(k=i;k<=mid;k++) A1[k-i]=A[k];
		n2=j-mid;
		for(k=mid+1;k<=j;k++) A2[k-mid-1]=A[k];
		merge(A1,n1,A2,n2,i,A);
	}
	return;
} 

int main(int argc,char* argv[]){
	int a,b,i;
	int A[N];
	FILE *fp;
	fp=fopen("../aaa.dat","r");
	fscanf(fp,"%d",&a);
	for(i=0;i<a;i++){
		fscanf(fp,"%d",&b);
		A[i]=b;
	}
	mergesort(0,a,A);
	for(i=1;i<=a;i++)printf("%d ",A[i]);
	fclose(fp);
}