| Home | Administração | Fórum | Livros | WWW | Diário | Tarefas | Alunos |
Esta página é uma versão simplificada do capítulo 12 (Recursive lists) do livro de Eric Roberts. O capítulo discute manipulação recursiva de listas e um programa de aritmética inteira com precisão arbitrária.
Uma lista encadeada é uma estrutura inerentemente recursiva, especialmente se confundirmos a idéia de lista com a idéia de endereço do primeiro elemento da lista. Suponha, por exemplo, que os elementos de nossas listas são números inteiros. Então podemos dar a seguinte definição recursiva do conceito de lista: uma lista é
Em consonância com essa definição, convém reescrever assim a definição das células da lista:
typedef struct cellT *listT; struct cellT { int head; // cabeça da lista listT tail; // cauda da lista } ;
As palavras "cabeça", "cauda", "head" e "tail" têm aqui um significado diferente daquele empregado no contexto de filas.
O que segue é um pequeno programa que manipula inteiros com número arbitrário de dígitos. O programa é muito simples:
Diremos que um inteiro desse tipo é um bigint. Eis nossas decisões de projeto:
Todas as funções no módulo abaixo são escritas recursivamente para enfatizar o caráter recursivo do conceito de lista. (É bem verdade que isso torna algumas das funções um pouco ineficientes.)
///////////////////////////////////////////////////////////// // Módulo bigint // Este módulo manipula bigints, ou seja, inteiros com número // arbitrário de dígitos. Um bigint é // . NULL (que representa o bigint de valor 0) ou // . um número d entre 0 e 9 seguido de um bigint n (que // representa o bigint de valor 10 * n + d). ///////////////////////////////////////////////////////////// typedef struct cellT *bigIntT; struct cellT { int finalDigit; // cabeça (dígito das unidades) bigIntT leadingDigits; // cauda (dezenas, centenas etc.) } ; // A função NewBigInt cria um bigint com valor i. bigIntT NewBigInt( int i) { bigIntT b; if (i < 0) exit( EXIT_FAILURE); if (i == 0) return NULL; else { b = NewBigInt( i / 10); return DigitCons( b, i % 10); } } // A função abaixo converte uma string str de dígitos // em um bigint. Exemplos: "1234" é convertida em 1234, // "001" é convertido em 1, "00" é convertida em NULL. bigIntT StringToBigInt( string str) { int len; char ch; bigIntT b; len = strlen( str); if (len == 0) return NULL; else { ch = str[len - 1]; str[len - 1] = '\0'; b = StringToBigInt( str); return DigitCons( b, ch - '0'); } } // A função abaixo converte um bigint n em uma string. // Exemplos: 1234 é convertido em "1234" e NULL é // convertido em "0". string BigIntToString( bigIntT n) { string oldstr, newstr; bigIntT b; if (b == NULL) return "0"; else { b = LeadingDigits( n); oldstr = BigIntToString( b); len = strlen( oldstr); newstr = malloc( len + 1 + 1); if (newstr == NULL) exit( EXIT_FAILURE); strcpy( newstr, oldstr); free( oldstr); newstr[len] = FinalDigit( n) + '0'; newstr[len + 1] = '\0'; return newstr; } } // A função DigitCons recebe um bigint n e um inteiro d // entre 0 e 9 e devolve o bigint cujo valor é 10 * n + d. // Se n é NULL ou d == 0 então a função devolve NULL. bigIntT DigitCons( bigIntT n, int d) { bigIntT cp; if (n == NULL && d == 0) return NULL; else { cp = malloc( sizeof (cellT)); if (cp == NULL) exit( EXIT_FAILURE); cp->finalDigit = d; cp->leadingDigits = n; return cp; } } // A função LeadingDigits devolve o bigint formado pelos // dígitos mais significativos (dezenas, centenas, etc) de n. bigIntT LeadingDigits( bigIntT n) { return (n == NULL) ? NULL : n->leadingDigits; } // A função FinalDigit devolve o dígito das unidades de n. int FinalDigit( bigIntT n) { return (n == NULL) ? 0 : n->finalDigit; } // Devolve o resultado da soma de n1 com n2. bigIntT AddBigInt( bigIntT n1, bigIntT n2) { return AddWithCarry( n1, n2, 0); } // Devolve o valor de n1 + n2 + carry. bigIntT AddWithCarry( bigIntT n1, bigIntT n2, int carry) { int sum; bigIntT p1, p2, b; p1 = LeadingDigits( n1); p2 = LeadingDigits( n2); sum = FinalDigit( n1) + FinalDigit( n2) + carry; if (sum == 0 && p1 == NULL && p2 == NULL) return NULL; else { b = AddWithCarry( p1, p2, sum / 10); return DigitCons( b, sum % 10); } } // A função MultiplyBigInt devolve o valor de n1 * n2. // A recursão tem por base a expressão // FinalDigit( n1) * n2 + LeadingDigits( n1) * n2 * 10. // Por exemplo, 342 * 173 == 342 * 3 + 342 * 17 * 10. bigIntT MultiplyBigInt( bigIntT n1, bigIntT n2) { int sum; bigIntT b, c, n2vezes10; if (n1 == NULL) return NULL; else { b = MultiplyDigit( FinalDigit( n1), n2); n2vezes10 = DigitCons( n2, 0); c = MultiplyBigInt( LeadingDigits( n1), n2vezes10); return AddBigInt( b, c); } } // A função MultiplyDigit devolve o valor de d * n. bigIntT MultiplyDigit( int d, bigIntT n) { bigIntT b; if (d == 0) return NULL; else { b = MultiplyDigit( d - 1, n); return AddBigInt( b, n); } }
Note que não temos uma função FreeBigInt. Uma tal função seria "perigosa" pois permitiria que o cliente fazer algo como
b = LeadingDigits( n); . . . FreeBigInt( b);
Com isso, o cliente poderia destruir n acidentalmente.
Para testar nosso módulo de inteiros com número arbitrário de dígitos, vamos escrever uma função que faz uma tabela de fatoriais:
// Programa bigfactorial. int main( int numargc, char *arg[]) { int LowerLimit, Upperlimit, i; LowerLimit = atoi( arg[1]); Upperlimit = atoi( arg[2]); for (i = LowerLimit; i <= UpperLimit; i++) printf( "2%d! = %s\n", i, BigIntToString( BigFact( i))); return 0; } // A função BigFact recebe um inteiro n e devolve um bigint // cujo valor é o fatorial de n. bigIntT BigFact( int n) { bigIntT bn, bf; if (n == 0) return NewBigInt( 1); else { bn = NewBigInt( n); bf = BigFact( n - 1); return MultiplyBigInt( bn, bf); } }
Se invocarmos "bigfactorial 15 20" teremos: