Cod sursa(job #562552)

Utilizator crouchHotea Cristian crouch Data 23 martie 2011 12:58:59
Problema Sortare prin comparare Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 2.02 kb
#include<stdio.h>
#include<stdlib.h>
typedef struct nod{
	void* data;
	struct nod* next;
} q_nod;

typedef q_nod* Queue;

int isEmpty(Queue c) {
	if(c == NULL)
		return 1;
	return 0;
}
int size(Queue c) {
	if(isEmpty(c)) {
		return 0;
	}
	int i = 1;
	while(c->next) {
		i++;
		c = c->next;
	}
	return i;
}
void* Front(Queue c) {
	return c->data;
}
int enqueue(Queue *c, void *val) {
	if(isEmpty(*c)){
		*c = malloc(sizeof(q_nod));
		(*c)->data = val;
		(*c)->next = NULL;
	}
	else {
		Queue aux = malloc(sizeof(q_nod));
		aux = *c;
		while(aux->next)
			aux = aux->next;
		Queue new = malloc(sizeof(q_nod));
		new->data = val;
		aux->next = new;
		new->next = NULL;
	}
}
void* dequeue(Queue *c) {
		void *aux2;
		Queue aux = malloc(sizeof(q_nod));
		aux = *c;		
		
		aux2 = aux->data;
		if(size(*c) == 1){
			*c=NULL;
		}
		else		
			(*c) = (*c)->next;
		free(aux);
		return aux2;
	}

int rang(int n,int *a) {
	int max,i,r = 0;
	max = a[0];
	for(i = 1 ; i < n ; i++)
		if(a[i] > max)
			max = a[i];
	while(max){
		r++;
		max/=10;
	}
	return r;
}
void afisare(Queue c) {
	if(isEmpty(c)) {
		printf("0\n");
	}
	else {
		printf("%d ",*(int *)c->data);	
		while(c->next){
			c = c->next;
			printf("%d ",*(int *)c->data);
		}	
		printf("\n");
	}
}
void distribuire(int n,int *x,Queue *c,int rang) {
	int i,y,cif,j,*px;

	for(i = 0 ; i < n ; i++) {
		y = x[i];
		for(j = 0 ; j < rang ; j++)
			y/=10;
		cif = y%10;
		px = malloc(sizeof(int));
		*px = x[i];
		enqueue(&c[cif],px);
	}
}
void colecteaza(int n,int *x,Queue *c) {
	int i,k = 0,y;
	void *px;
	for(i = 0 ; i < 10 ; i++)
		while( !isEmpty(c[i]) ) {
			px = dequeue(&c[i]);
			x[k++] = *(int*)px;
			free(px);
		}
}
int main () {
int i=0 ,r,*a, n;
FILE *s=fopen("algsort.in","r");
FILE *d=fopen("algsort.out","w");
Queue *c = malloc(10*sizeof(Queue));
fscanf(s,"%d",&n);
a=malloc(sizeof(int));
fscanf(s,"%d",&a[0]);
for(i=1;i<n;i++) {
	a=realloc(a,(i+1)*sizeof(int));
	fscanf(s,"%d",&a[i]);
}
r=rang(n,a);
for(i=0;i<r;i++) {
distribuire(n,a,c,i);	
colecteaza(n,a,c);
}

for(i=0;i<n;i++)
	fprintf(d,"%d ",a[i]);

}