MAC0122  Princípios de Desenvolvimento de Algoritmos
Home  |   Administração  |   Fórum  |   Livros  |   WWW  |   Diário  |   Tarefas  |   Alunos

 

Um editor de linha

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 básico

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.

 

Implementação do buffer em vetor

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

 

Implementação em duas pilhas

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

 

Implementação em lista encadeada

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

 

Exercícios

  1. Escreva uma função que calcule o número de células de uma lista encadeada. Suponha que a primeira célula da lista é dummy. Repita tudo supondo que a lista não tem célula dummy.

  2. Escreva uma função que faça uma cópia de uma lista encadeada dada.

  3. Escreva uma função que libere o espaço ocupado por uma lista encadeada. Suponha que a primeira célula da lista é dummy. Repita tudo supondo que a lista não tem célula dummy.

  4. Escreva uma função que verifique se os caracteres armazenados numa lista encadeada estão em ordem crescente. Suponha que a primeira célula da lista é dummy. Repita tudo supondo que a lista não tem célula dummy.

  5. Escreva uma função que inverta uma lista encadeada, ou seja, coloca a última célula no lugar da primeira, a penúltima no lugar da segunda, etc. Sua função não deve criar novas células. Suponha que a primeira célula da lista é dummy. Repita tudo supondo que a lista não tem célula dummy.

  6. Escreva uma implementação de uma pilha em uma lista encadeada. 

 


Veja minhas anotações sobre listas encadeadas.
URL of this site: www.ime.usp.br/~pf/mac0122-2002/
Last modified: Mon Oct 9 07:14:51 BRT 2017
Paulo Feofiloff
IME-USP