Home | Administração | Fórum | Livros | WWW | Diário | Tarefas | Alunos |
Esta página foi extraída (com várias modificações) do capítulo 9 (Efficiency and ADTs) do livro de Eric Roberts. Ela usa o exemplo de um editor de linha para mostrar como a eficiência de uma ADT depende de sua implementação.
Roberts também usa esse exemplo para introduzir o conceito de listas encadeada (= linked list).
Um editor de linha permite que o usuário contrua e modifique uma linha de texto digitando comandos que movimentam um cursor, inserem caracteres e removem caracteres. Eis um exemplo (as ações do usuário estão em vermelho):
*Iaxc a x c ^ *J a x c ^ *F a x c ^ *D a c ^ *Ib a b c ^ *Q
Observe que temos um buffer de caracteres e um cursor que indica a posição corrente do editor. O cursor fica entre dois caracteres (ou antes do primeiro caracter ou depois do último).
Eis como o programa pode ser escrito:
// Este programa é um editor de linha (ou editor de buffer) // um tanto antiquado. Ele obedece os seguintes comandos // digitados pelo usuário depois do "prompt" *: // I... insere os caracteres digitados na posição em que // está o cursor // D (delete) apaga o caracter que está depois do cursor // F (forward) avança o cursor de uma posição // B (back) retroce o cursor de uma posição // J (jump) posiciona o cursor no início do buffer // E (end) posiciona o cursor no fim do buffer // Q (quit) sai do programa //////////////////////////////////////// // Seção 1: Bibliotecas e tipos de dados //////////////////////////////////////// typedef char* string; typedef enum {FALSE, TRUE} bool; #include <stdio.h> #include <stdlib.h> // preciso de atof #include <ctype.h> // preciso de toupper etc. ///////////////////////////////////////////////////////// // Seção 2: Editor de buffer // O buffer é representado por um struct do tipo bufferT. // Veja abaixo. ///////////////////////////////////////////////////////// ////////////////////////////////////// // Seção 3: Código do editor de buffer ////////////////////////////////////// void ExecuteCommand( string line); string getLine( void); int main( void) { bufferT *b; b = NewBuffer(); while (TRUE) { printf( "*"); ExecuteCommand( b, getLine()); DisplayBuffer( b); } FreeBuffer( b); return 0; } // Interpreta e executa o comando fornecido em line. void ExecuteCommand( bufferT *b, string line) { int i; switch (toupper( line[0])) { case 'I': for (i = 1; line[i] != '\0'; i++) InsertCharacter( b, line[i]); break; case 'D': DeleteCharacter( b); break; case 'F': MoveCursorForward( b); break; case 'B': MoveCursorBackward( b); break; case 'J': MoveCursorToStart( b); break; case 'E': MoveCursorToEnd( b); break; case 'Q': exit( EXIT_SUCCESS); default: printf( "Illegal command\n"); } } // Lê uma linha do teclado e devolve a linha na forma de // uma string. A linha deve ter no máximo 100 caracteres. // Esta função foi inspirada na GetLine da biblioteca // simpio de Eric Roberts, mas é bem mais simples que // aquela. string getLine( void) { string line; int n, ch; n = 0; line = malloc( 100+1); if (line == NULL) exit( EXIT_FAILURE); while ((ch = getc( stdin)) != '\n') { if (n >= 100) { free( line); exit( EXIT_FAILURE); } line[n++] = ch; } line[n] = '\0'; return line; }
Vamos examinar a seguir três diferentes implementações do buffer (seção 2 do código acima). Observe como o programa principal (seção 3 do código acima) não depende da implementação do buffer: podemos trocar as implementações sem alterar nada no programa principal.
Eis a implementação do editor que foi omitida acima. Nesta primeira versão, vamos usar um vetor para representar o buffer.
///////////////////////////////////////////////////////// // Seção 2: Editor de buffer // Nesta seção estão definidas as estruturas e as funções // básicas do editor. O buffer do editor é implementado em // um vetor. ///////////////////////////////////////////////////////// // O editor é representado por um struct do tipo bufferT. // Se b é um ponteiro para uma variável do tipo bufferT, // o texto sendo editado está em b->text[0 .. b->length-1]. // O cursor fica entre as posições b->cursor - 1 e // b->cursor. É claro que // 0 <= b->cursor <= b->length. // Se b->cursor == 0, estamos prontos para inserir antes // do primeiro caracter. Se b->cursor == b->length, estamos // prontos para inserir depois do último caracter. #define MaxBuffer 100 typedef struct { char text[MaxBuffer]; int length; int cursor; } bufferT; // Avança o cursor do buffer b de uma posição. void MoveCursorForward( bufferT *b) { if (b->cursor < b->length) b->cursor++; } // Retrocede o cursor do buffer b de uma posição. void MoveCursorBackward( bufferT *b) { if (b->cursor > 0) b->cursor--; } // Posiciona o cursor no início do buffer b. void MoveCursorToStart( bufferT *b) { b->cursor = 0; } // Posiciona o cursor no fim do buffer b. void MoveCursorToEnd( bufferT *b) { b->cursor = b->length; } // Insere o caracter ch na posição em que está o cursor // do buffer b. Após a inserção, o cursor é posicionado // depois do caracter inserido. void InsertCharacter( bufferT *b, char ch) { int i; if (b->length == MaxBuffer) exit( EXIT_FAILURE); for (i = b->lenght; i > b->cursor; i--) b->text[i] = b->text[i - 1]; b->text[b->cursor] = ch; b->length++; b->cursor++; } // Apaga o caracter que está logo depois do cursor de b. // A posição do cursor não muda. Se o cursor estiver // no fim do buffer, nada acontece. void DeleteCharacter( bufferT *b) { int i; if (b->cursor < b->length) { for (i = b->cursor + 1; i < b->length; i++) b->text[i - 1] = b->text[i]; b->length--; } }
Além dessas funções "principais", é importante que o módulo tenha algumas funções "auxiliares":
// Esta função cria um editor de buffer e devolve // o seu endereço. bufferT *NewBuffer( void) { bufferT *b; b = malloc( sizeof (bufferT)); if (b = NULL) exit( EXIT_FAILURE); b->length = b->cursor = 0; return b; } // Destrói o buffer criado por NewBuffer. void FreeBuffer( bufferT *b) { free( b); } // Esta função exibe o buffer sendo editado. Também // exibe a posição do cursor. void DisplayBuffer( bufferT *b) { int i; for (i = 0; i < b->length; i++) printf( " %c", b->text[i]); printf( "\n"); for (i = 0; i < b->cursor; i++) printf( " "); printf( "^\n"); }
Consumo de tempo no pior caso, em função do número de caracteres N (igual a b->length):
Operação | tempo |
---|---|
MoveCursorForward | 1 |
MoveCursorBackward | 1 |
MoveCursorToStart | 1 |
MoveCursorToEnd | 1 |
InsertCharacter | N |
DeleteCharacter | N |
Eis uma outra implementação do editor, desta vez usando duas pilhas. Vamos usar a implementação de pilha que estudamos em outra ocasião, com um pequeno ajuste: vamos supor que os elementos da pilha não são números do tipo double mas sim caracteres.
///////////////////////////////////////////////////////// // Seção 2: Editor de buffer // Nesta seção estão definidas as estruturas e as funções // básicas do editor. O buffer do editor é implementado em // um par de pilhas. ///////////////////////////////////////////////////////// // O editor é representado por uma struct do tipo bufferT // que contém duas pilhas. A pilha before contém os elementos // anteriores ao cursor e a pilha after contém os elementos // posteriores ao cursor. typedef struct { stackT *before; stackT *after; } bufferT; // Avança o cursor de uma posição. void MoveCursorForward( bufferT *b) { if (!StackIsEmpty( b->after)) { char ch; ch = Pop( b->after); Push( b->before, ch); } } // Retrocede o cursor de uma posição. void MoveCursorBackward( bufferT *b) { if (!StackIsEmpty( b->before)) { char ch; ch = Pop( b->before); Push( b->after, ch); } } // Posiciona o cursor no início do buffer. void MoveCursorToStart( bufferT *b) { while (!StackIsEmpty( b->before)) { char ch; ch = Pop( b->before); Push( b->after, ch); } } // Posiciona o cursor no fim do buffer. void MoveCursorToEnd( bufferT *b) { while (!StackIsEmpty( b->after)) { char ch; ch = Pop( b->after); Push( b->before, ch); } } // Insere o caracter ch na posição em que está o cursor. void InsertCharacter( bufferT *b, char ch) { Push( b->before, ch); } // Apaga o caracter que está logo depois do cursor. void DeleteCharacter( bufferT *b) { if (!StackIsEmpty( b->after)) Pop( b->after); }
Além dessas funções "principais", é importante que o módulo tenha algumas funções "auxiliares":
// Esta função cria um editor de buffer novo e // devolve o seu endereço. bufferT *NewBuffer( void) { bufferT *b; b = malloc( sizeof (bufferT)); if (b = NULL) exit( EXIT_FAILURE); b->before = NewStack(); b->after = NewStack(); return b; } // Destrói o buffer criado por NewBuffer. void FreeBuffer( bufferT *b) { FreeStack( b->before); FreeStack( b->after); free( b); } // Esta função exibe o conteúdo do buffer. // Também exibe a posição do cursor. void DisplayBuffer( bufferT *b) { int i; for (i = StackDepth( b->before) - 1; i >= 0; i--) printf( " %c", GetStackElement( b->before, i)); for (i = 0; i < StackDepth( b->after); i++) printf( " %c", GetStackElement( b->after, i)); printf( "\n"); for (i = 0; i < StackDepth( b->before); i++) printf( " "); printf( "^\n"); }
Consumo de tempo no pior caso, em função do número N de caracteres no buffer:
Operação | vetor | pilhas |
---|---|---|
MoveCursorForward | 1 | 1 |
MoveCursorBackward | 1 | 1 |
MoveCursorToStart | 1 | N |
MoveCursorToEnd | 1 | N |
InsertCharacter | N | 1 |
DeleteCharacter | N | 1 |
No lugar de cada elemento do vetor text da primeira implementação, teremos uma "célula" com dois campos: o campo ch será o "conteúdo" da célula e o campo link será o endereço da célula seguinte.
typedef struct cellT { char ch; struct cellT *link; } cellT;
Como nas outras implementações, o cursor fica entre duas células consecutivas. Mas, ao contrário do que fizemos acima, vamos registrar (na variável cursor) o endereço da célula anterior à posição do cursor. Isso cria um problema quando o cursor está antes da primeira célula. Para resolver o problema, vamos usar uma célula-cabeça-de-lista, ou dummy cell.
///////////////////////////////////////////////////////// // Seção 2: Editor de buffer // Nesta seção estão definidas as estruturas e as funções // básicas do editor. O buffer do editor é implementado em // uma lista encadeada. ///////////////////////////////////////////////////////// // O editor é representado por uma struct do tipo bufferT // que contém o endereço do início da lista encadeada e o // endereço da célula anterior à posição do cursor. typedef struct { cellT *start; cellT *cursor; } bufferT; // Avança o cursor de uma posição. void MoveCursorForward( bufferT *b) { if (b->cursor->link != NULL) b->cursor = b->cursor->link; } // Retrocede o cursor de uma posição. void MoveCursorBackward( bufferT *b) { cellT *cp; if (b->cursor != b->start) { cp = b->start; while (cp->link != b->cursor) cp = cp->link; b->cursor = cp; } } // Posiciona o cursor no início do buffer. void MoveCursorToStart( bufferT *b) { b->cursor = b->start; } // Posiciona o cursor no fim do buffer. void MoveCursorToEnd( bufferT *b) { while (b->cursor->link != NULL) MoveCursorForward( b); } // Insere o caracter ch na posição em que está o cursor, // (Funciona corretamente mesmo quando b->cursor == &dummy.) void InsertCharacter( bufferT *b, char ch) { cellT *cp; cp = malloc( sizeof (cellT)); cp->ch = ch; cp->link = b->cursor->link; b->cursor->link = cp; b->cursor = cp; } // Apaga o caracter que está logo depois do cursor. // (Funciona corretamente mesmo quando b->cursor == &dummy.) void DeleteCharacter( bufferT *b) { cellT *cp; if (b->cursor->link != NULL) { cp = b->cursor->link; b->cursor->link = cp->link; free( cp); } }
Além dessas funções "principais", é importante que o módulo tenha algumas funções "auxiliares":
bufferT *NewBuffer( void) { bufferT *b; b = malloc( sizeof (bufferT)); if (b = NULL) exit( EXIT_FAILURE); b->start = b->cursor = malloc( sizeof (cellT)); // "dummy" return b; } // Destrói o buffer criado por NewBuffer. void FreeBuffer( bufferT *b) { cellT *cp, *next; cp = b->start; while (cp != NULL) { next = cp->link; free( cp); cp = next; } free( b); } // Esta função exibe o buffer sendo editada. Também exibe // a posição do cursor. void DisplayBuffer( bufferT *b) { cellT *cp; for (cp = b->start->link; cp != NULL; cp = cp->link) printf( " %c", cp->ch); printf( "\n"); for (cp = b->start->link; cp != b->cursor; cp = cp->link) printf( " "); printf( "^\n"); }
Consumo de tempo no pior caso, em função do número de N caracteres:
Operação | vetor | pilhas | lista |
---|---|---|---|
MoveCursorForward | 1 | 1 | 1 |
MoveCursorBackward | 1 | 1 | N |
MoveCursorToStart | 1 | N | 1 |
MoveCursorToEnd | 1 | N | N |
InsertCharacter | N | 1 | 1 |
DeleteCharacter | N | 1 | 1 |