TDA Lista de enteros VIII

TDA Lista de enteros VIII

Esta es una de los códigos más dificiles de interpretar para una persona que nos sea experto en leer código C. Se trata de dos procedimientos para ordenar una y dos listas, respectivamente, mediante el algoritmo de ordenación mergesort.

Voy a dejaros, en primer lugar,  el procedimiento que ordena una lista de enteros, que se le pasa como argumentos y se le devuelve una lista ordenada:

void lista_mergesort ( lista *c ) {
	
	lista rep;
	
	if ((*c)->tam != 0 ) && ((*c)->tam != 1 ) {
		l_marc (*c, div((*c)->tam, 2).quot);
		
		rep = ( struct l_dir *) malloc(sizeof ( struct l_dir ));
		
		rep->prim = (*c)->nodo->sig;
		rep->ulti = (*c)->ulti;
		(*c)->ulti = (*c)->nodo;
		(*c)->ulti->sig = NULL;
		
		rep->tam = (*c)->tam - (*c)indnodo;
		(*c)->tam = (*c)->indnodo;
		lista_mergesort ( c );
		lista_mergesort ( &rep );
		lista_merge ( c, &rep );
	}
	
}

Este procedimiento llama a otro procedimiento cuya función es ordenar una lista de enteros mediante el algoritmo de mergesort, el más complejo y a la vez el más eficiente de todos:

lista lista_merge (  lista *c, lista *d ) {
	
	lista b
	l_lst bcorr, dcorr, ccorr;
	
	if (!(*c)->tam ) {
		
		free (*c);
		*c = *d;
		*d = NULL;
		
		return (*c);
	}
	
	else {
	
		b = *c;
		if ( (*d)->tam ) {
			b->tam = (*c)->tam = (*d)->tam;
			ccorr = (*c)->prim;
			dcorr = (*d)->prim;
			if (l_menor(ccorr->val, dcorr->val)) {
				bcorr = b->nodo = b->prim = ccorr;
				ccorr = cccorr->sig;
			}
			
			else {
			
				bcorr == b->nodo = b->prim = dcorr;
				dcorr = ccorr->sig;
			
			}
			
			b->indnodo = 1;
			while ((ccorr) && (dcorr )) {
			
				if (l_menor (ccorr->val, dcorr->val) {
				
					bcoor->sig = ccorr;
					ccorr = ccorr->sig;
				
				}
				
				else {
				
					bcorr->sig = dcorr;
					dcorr = dcorr->sig;
				
				}
				
				bcorr = bcorr->sig;				
			
			}
			
			if ( !ccorr ) {
			
				b->ulti = (*d)->ulti;
				bcorr->sig = dcorr;
			
			}
			
			else {
			
				b->ulti = (*c)->ulti;
				bcorr->sing = ccorr;
			
			}
			
		}
		
		free (*d);
		*d = NULL;
		
		return (b);
	
	}
		
}

Como siempre, tenéis la sección de contacto para dejar vuestras aportaciones y códigos alternativos.

No Comments

Post a Comment