FACTORIAL.c

/* CALCULO DEL FACTORIAL DE NUMEROS GRANDES
	- SI LA MEMORIA LO PERMITE -
	SE UTILIZA UN DIGITO POR CELDA
	( LISTAS LIGADAS )
*/

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

struct Nodo
{
	int Digito;
	struct Nodo *Sig;
	struct Nodo *Ant;
};
struct Nodo *Numero_Entrada;			// NUmero al que se le calcularA el factorial
struct Nodo *Factorial;				// Resultado al calcular el factorial de Numero_Entrada


void Solicita_Dato(char*);
struct Nodo *Crea_Nodo(int);
struct Nodo *Crea_Lista(char*);
void Muestra_Lista(struct Nodo*);
int Compara(struct Nodo*, struct Nodo*);
struct Nodo *Suma_Lista_Escalar(struct Nodo *, int);
void Calcula_Factorial();
struct Nodo *Producto_Lista_Escalar(struct Nodo*, int, struct Nodo*, int);
struct Nodo *Producto_Lista_Lista(struct Nodo*, struct Nodo*);

struct Nodo *Crea_Nodo(int Numero)
{
	struct Nodo *Temporal = (struct Nodo *)malloc(sizeof(struct Nodo *));
	Temporal->Digito = Numero;
	Temporal->Ant = Temporal->Sig = NULL;
	return Temporal;
}


// (FACTOR_1, ESCALAR, SUMA_PARCIAL, posiciOn_de_corrimiento)			SUMA = RESP * ESC
struct Nodo *Producto_Lista_Escalar(struct Nodo *RESP, int ESC, struct Nodo *SUMA, int POS)
{
	int TEMP = 0;							// Entero para guardar el producto parcial de ESCALAR * ESCALAR
	int LLEVO = 0;							// Se almacena el acarreo si lo hay
	struct Nodo *Nuevo = NULL;					// CreaciOn de nuevos nodos

	while (RESP->Sig != NULL) RESP = RESP->Sig;			// Se posiciona el apuntador en el dIgito menos significativo
	while (SUMA->Sig != NULL) SUMA = SUMA->Sig;			// Se posiciona el apuntador en el dIgito menos significativo
	while ( POS ) { SUMA = SUMA->Ant; --POS; }			// Se recorre el apuntador hacia atrAs POS posiciones

	while ( RESP != NULL )						// Mientras existan dIgitos en RESP
	{
		TEMP = ESC * RESP->Digito + SUMA->Digito + LLEVO;
		if (TEMP > 9) { SUMA->Digito = TEMP % 10; LLEVO = (TEMP - SUMA->Digito) / 10; }
		else { SUMA->Digito = TEMP; LLEVO = 0; }
		if (SUMA->Ant != NULL) SUMA = SUMA->Ant;
		else
		{
			Nuevo = Crea_Nodo(0);
			Nuevo->Sig = SUMA; SUMA->Ant = Nuevo; SUMA = Nuevo;
		}
		RESP = RESP->Ant;
	}
	if ( LLEVO ) SUMA->Digito = LLEVO;
	else								// Se elimina el nodo mas significativo con contenido de cero
	{ Nuevo = SUMA; SUMA = SUMA->Sig; SUMA->Ant = NULL; free(Nuevo); }
	while (SUMA->Ant != NULL) SUMA = SUMA->Ant;			// Se regresa al dIgito mas significativo
	return SUMA;
}

struct Nodo *Producto_Lista_Lista(struct Nodo *Factorial, struct Nodo *Factor)
{
	struct Nodo *Suma_Acumulada = Crea_Nodo(0);
	int Inicio = 0;						// Cantidad de dIgitos que se corren para realizar la suma acumulada
	
	while(Factor->Sig != NULL) Factor = Factor->Sig;	// Se posiciona el apuntador en el dIgito menos significativo

	while ( 1 )						// Ciclo infinito hasta la cantidad de dIgitos de Factor
	{
		Suma_Acumulada = Producto_Lista_Escalar(Factorial, Factor->Digito, Suma_Acumulada, Inicio);
		if ( Factor->Ant != NULL ) { Factor = Factor->Ant; Inicio++; }			// Se hace un corrimiento a la izquierda
		else break;
	}
	while (Suma_Acumulada->Ant != NULL) Suma_Acumulada = Suma_Acumulada->Ant;
	return Suma_Acumulada;
}


void Calcula_Factorial()
{
	struct Nodo *Factor = Crea_Nodo(1);				// Inicializa el caso base
	Factorial = Crea_Nodo(1);					// Inicializa el caso base
	int Detectar = 0;						// Bandera cuando se iguala el Factor con el Numero_Entrada

	while (!Detectar)						// Mientras Factor sea menor que Numero_Entrada
	{
		Detectar = Compara(Factor, Numero_Entrada);		// Ya se llegO al nUmero deseado pero aUn asI se multiplica
		Factorial = Producto_Lista_Lista(Factorial, Factor);
		Factor = Suma_Lista_Escalar(Factor, 1);
	}
}

struct Nodo *Suma_Lista_Escalar(struct Nodo *Lista, int ESCALAR)
{
	struct Nodo *Nuevo = NULL;
	
	while(Lista->Sig != NULL) Lista = Lista->Sig;			// Se posiciona el apuntador en el dIgito menos significativo
	while ( 1 )							// Ciclo infinito por si hay corrimientos
	{
		Lista->Digito += ESCALAR;
		if (Lista->Digito < 10) break;				// No hay corrimiento. No tiene caso continuar
		ESCALAR = (Lista->Digito - Lista->Digito % 10) / 10;
		Lista->Digito = Lista->Digito - ESCALAR*10;
		if ( Lista->Ant != NULL ) Lista = Lista->Ant;
		else							// Significa que ya llegO al principio de la lista y se efectUa un corrimiento
		{
			Nuevo = Crea_Nodo(ESCALAR);			// Por consiguiente se agrega un nodo al principio (dIgito mas significativo)
			Nuevo->Sig = Lista;
			Lista->Ant = Nuevo;
			Lista = Nuevo;
			break;
		}
	}
	while(Lista->Ant != NULL) Lista = Lista->Ant;			// Se posiciona el apuntador en el dIgito mas significativo
	return Lista;
}

int Compara(struct Nodo *N1, struct Nodo *N2)
{
	while(N1)
	{
		if (N1->Digito != N2->Digito) return 0;					// Con un digito que sea diferente, todo es diferente.
		if (N1->Sig != NULL && N2->Sig != NULL) { N1 = N1->Sig; N2 = N2->Sig; }	// Existe un prOximo Digito
		else if (N1->Sig == NULL && N2->Sig == NULL) return 1;				// Ambas llegaron al final al mismo tiempo
			else return 0;								// Al menos una llegO al final y la otra no
	}
	return 1;
}

void Muestra_Lista(struct Nodo *Lista)	{ while(Lista) { printf("%d ", Lista->Digito); Lista = Lista->Sig; } printf("\nOK\n"); }
void Solicita_Dato(char *Numero)	{ printf("Introduce el nUmero al que se le calcularA el factorial: "); gets(Numero); }

struct Nodo *Crea_Lista(char *CAD)
{
	int Indice = 0;
	struct Nodo *Nuevo=NULL, *Aux=NULL, *Lista=NULL;

	while( CAD[Indice] != '\0')
	{
		Nuevo = Crea_Nodo(CAD[Indice] - 48);  // (Ascii - 48 = N) Convierte a decimal
		
		if (!Lista) Lista = Aux = Nuevo;
		else
		{
			Aux->Sig = Nuevo;
			Nuevo->Ant = Aux;
			Aux = Nuevo;
		}
		Indice++;
	}
	return Lista;
}

int main()
{
	char *Numero = (char*)malloc(sizeof(char*)*100);
	Numero_Entrada = Factorial = NULL;				// Se inicializan como listas vacIas

	Solicita_Dato(Numero);
	Numero_Entrada = Crea_Lista(Numero);
	Calcula_Factorial();
	Muestra_Lista(Factorial);
}