LNCC

Parte 1: Estruturas de dados elementares

GA-024

Antônio Tadeu A. Gomes, D.Sc.

atagomes@gmail.com http://wiki.martin.lncc.br/atagomes-cursos-lncc-ga024

Sala 2C-01

LNCC

Estruturas de dados elementares

!  Matrizes

!  Listas encadeadas

!  Pilhas e filas

!  Cadeias de caracteres

LNCC

Matrizes (I) !  Conjuntos multidimensionais homogêneos !  Alocação estática:

-  É necessário saber de antemão as dimensões !  Ex. (bidimensional):

-  Variável que

representa matriz é um ponteiro para o primeiro elemento da primeira linha

-  Há: !  Formas alternativas de inicialização na declaração !  Passagem de matrizes como parâmetros de funções

(representação “row major”)

LNCC

Matrizes (II)

!  Alocação dinâmica -  C e C++ só permitem alocação dinâmica de conjuntos

unidimensionais

-  É necessário criar abstrações conceituais com vetores para representar matrizes alocadas dinamicamente

!  Uso de TAD pode ser conveniente para encapsular abstração

float* v; … v = (float*) malloc(n * sizeof(float));

LNCC

Matrizes (III) !  TAD “Matrix” bidimensional

(elementos ponto-flutuante) -  Estrutura: ??? -  Operações principais:

!  Matrix* matrix_create( int m, int n ): cria matriz de zeros !  Matrix* matrix_create( void ): cria a partir de stdin !  matrix_print( Matrix* m ): imprime matriz em stdout !  matrix_destroy( Matrix* m ) !  float matrix_getelem( Matrix* m, int x, int y ) !  matrix_setelem( Matrix* m, int x, int y, float elem ) !  matrix_{getcolumncount,getlinecount}( Matrix* m )

-  Outras operações: !  Matrix* matrix_transpose( Matrix* m ) !  Matrix* matrix_{add,subtract,multiply}( Matrix* m, Matrix* m )

LNCC

Matrizes (IV)

!  Matriz dinâmica bidimensional representada por um vetor simples:

-  mat[ i ][ j ] mapeado em v[ k ] onde k = i * n + j -  Implementação de matrix_getelem()?

Operação matrix_create( int m, int n ): float *mat; /* matriz m x n como um vetor */ ... mat = (float*) malloc(m*n*sizeof(float)); ...

LNCC

Matrizes (V)

!  Matriz dinâmica bidimensional representada por um vetor de ponteiros:

-  Cada elemento do vetor armazena o endereço do primeiro elemento de cada linha da matriz

-  Implementação de matrix_getelem()?

Operação matrix_create( int m, int n ): int i; float **mat; /* matriz como um vetor de ponteiros */ ... mat = (float**) malloc(m*sizeof(float*)); for (i=0; i<m; i++) mat[i] = (float*) malloc(n*sizeof(float)); ...

LNCC

Matrizes (VI)

!  Matrizes simétricas -  mat é uma matriz simétrica se mat[ i ][ j ] = mat[ j ][ i ] -  estratégia de armazenamento:

!  basta armazenar os elementos da diagonal e metade dos elementos restantes, por exemplo, os elementos abaixo da diagonal, ou seja, mat[ i ][ j ], onde i > j

-  em lugar de n2 valores, armazena-se n(n+1)/2 valores -  Implementação de matrix_getelem()?

!  Com vetores simples !  Com vetores de ponteiros

LNCC

Matrizes (VII)

!  Matrizes esparsas

-  Muitas posições preenchidas por zeros

-  Ex. de aplicação: solução numérica de eq. diferenciais parciais (EDPs) (métodos diretos ou iterativos)

-  Alocação ineficiente de memória tanto com vetores simples como com vetores de ponteiros

�

⇧⇧⇧⇧⇧⇧⇤

10 0 0 0 �2 03 9 0 0 0 30 7 8 7 0 03 0 8 7 5 00 8 0 9 9 130 4 0 0 2 �1

⇥

⌃⌃⌃⌃⌃⌃⌅

LNCC

Matrizes (VIII) !  Compressed Row Storage (CRS)

-  Não assume características específicas da matriz

row ptr 1 3 6 9 13 17 20

val 10 -2 3 9 3 7 8 7 3 ... 9 13 4 2 -1col ind 1 5 1 2 6 2 3 4 1 ... 5 6 2 5 6

�

⇧⇧⇧⇧⇧⇧⇤

10 0 0 0 �2 03 9 0 0 0 30 7 8 7 0 03 0 8 7 5 00 8 0 9 9 130 4 0 0 2 �1

⇥

⌃⌃⌃⌃⌃⌃⌅

LNCC

Matrizes (IX)

!  Variantes da CRS: -  “Column-major” (CCS)

-  Block-compressed (BCRS, BCCS)

!  Útil na discretização de EDPs com vários graus de liberdade (tamanho do bloco determinado pelo número de graus de liberdade)

!  Neste caso, vetor val armazena ponteiros para um outro vetor que contém de fato os blocos

Tamanho do bloco = 2

LNCC

Matrizes (X)

!  Outras formas de representação:

-  Compressed Diagonal Storage (CDS)

!  Matrizes de banda fixa

�

⇧⇧⇧⇧⇧⇧⇤

10 �3 0 0 0 03 9 6 0 0 00 7 8 7 0 00 0 8 7 5 00 0 0 9 9 130 0 0 0 2 �1

⇥

⌃⌃⌃⌃⌃⌃⌅

val(:,-1) 0 3 7 8 9 2val(:, 0) 10 9 8 7 9 -1val(:,+1) -3 6 7 5 13 0

LNCC

Matrizes (XI)

!  Outras formas de representação (cont.):

-  Jagged Diagonal Storage (JDS) !  Mais eficiente em espaço que CDS !  Útil na implementação de métodos iterativos em

computadores paralelos/vetoriais

-  Skyline Storage (SKS) !  Matrizes de banda variável !  Útil na implementação de métodos diretos e na

fatoração de matrizes em blocos

!  Referência: [Barret et al., 2006, Seção 4.3]

LNCC

Listas encadeadas (I)

!  Vetores e matrizes (alocadas estaticamente ou dinamicamente com vetores simples/de ponteiros)

-  Ocupam (grupos de) espaços contíguos de memória !  Permitem acesso (quase) direto aos elementos

-  Devem ser dimensionados com um número máximo de

elementos !  Em C, possibilidade de redimensionamento com realloc()

LNCC

Listas encadeadas (II)

!  Lista encadeada: -  Sequência de elementos chamados de nós

-  Um nó de uma lista contém:

!  a informação armazenada (homogênea ou não em relação ao resto da lista)

!  um ou mais ponteiros que apontam para outros nós da lista

-  Uma lista é representada por um ponteiro para um nó da lista

-  Ponteiros em um nó de uma lista podem ser NULL

LNCC

Listas encadeadas (III)

!  TAD “List” em C (elementos inteiros) !  Operações principais:

!  List* list_create( void ): cria lista vazia !  void list_destroy( List* l) !  List* list_insert( List* l, int i ): insere nó com informação i no

início da lista !  List* list_remove( List* l, int v ): retira nó com informação v !  int list_empty(List* l): retorna 1 se lista vazia !  List* list_get(List* l, int v): retorna ponteiro para nó com

informação v !  Outras operações:

!  void list_print(List* l): imprime conteúdo da lista em stdout

LNCC

Listas encadeadas (IV)

!  Tipos de listas:

-  Listas encadeadas simples

-  Listas circulares

-  Listas duplamente encadeadas

LNCC

Listas encadeadas (V) !  Ex.1: lista encadeada simples armazenando

inteiros

struct list { int info; struct list* next; }; typedef struct list List;

/* inserção no início: retorna a lista atualizada */ List* list_insert(List* l, int i) { List* novo = (List*) malloc(sizeof(List)); novo->info = i; novo->next = l; return novo; }

/* imprime valores dos elementos em stdout */ void list_print (List* l) { List* p; for (p = l; p != NULL; p = p->next) printf(“%d\n”, p->info); }

LNCC

Listas encadeadas (VI)

!  Ex.1 (cont.) -  Remoção

!  Caso 1:

!  Caso 2:

/* retira elemento da lista */ List* list_remove( List* l, int v ) { List* ant = NULL; /* ponteiro para elemento anterior */ List* p = l; /* ponteiro para percorrer a lista */ /* procura elemento na lista, guardando anterior */ while (p != NULL && p->info != v) { ant = p; p = p->next; } /* verifica se achou elemento */ if (p == NULL) return l; /* não achou: retorna lista original */ /* retira elemento */ if (ant == NULL) /* retira elemento do inicio */ l = p->next; else /* retira elemento do meio da lista */ ant->next = p->next; free(p); return l; }

LNCC

Listas encadeadas (VII) !  Ex.2: lista

encadeada simples ordenada

/* insere elemento em ordem */ List* list_insert(List* l, int v) { List* novo; List* ant = NULL; /* ponteiro para elemento anterior */ List* p = l; /* ponteiro para percorrer a lista */ /* procura posição de inserção */ while (p != NULL && p->info < v) { ant = p; p = p->next; } /* cria novo elemento */ novo = (List*) malloc(sizeof(List)); novo->info = v; /* encadeia elemento */ if (ant == NULL) { /* insere elemento no início */ novo->next = l; l = novo; } else { /* insere elemento no meio/final da lista */ novo->next = ant->next; ant->next = novo; } return l; }

LNCC

Listas encadeadas (VIII)

!  Ex.3: lista circular -  A lista pode ser representada por um ponteiro para um

elemento inicial qualquer da lista

-  E as outras operações?

void list_print(List* l) { List* p = l; /* faz p apontar para o nó inicial */ /* testa se lista não é vazia e então percorre com do-while */ if (p) do { printf("%d\n", p->info); /* imprime informação do nó */ p = p->next; /* avança para o próximo nó */ } while (p != l); }

LNCC

Listas encadeadas (IX)

!  Ex.4: lista duplamente encadeada -  Cada elemento tem um ponteiro para o próximo

elemento e um ponteiro para o elemento anterior

-  E as outras operações?

struct list { int info; struct list* prev; struct list* next; };

/* inserção no início: retorna a lista atualizada */ List* list_insert(List* l, int v) { List* novo = (List*) malloc(sizeof(List)); novo->info = v; novo->next = l; novo->prev = NULL; /* verifica se lista não estava vazia */ if (l != NULL) l->prev = novo; return novo; }

LNCC

Listas encadeadas (X)

!  Nós de uma lista podem armazenar ponteiros para informações, ao invés das informações em si

-  Permite a implementação de listas genéricas

-  Demanda generalização também nas operações do TAD

!  Neste caso, uso de linguagem orientada o objetos (ex. C++) facilita implementação

-  Herança e polimorfismo

/* Definição de nó genérico */ struct list { int type; void *info; struct list *next; };

LNCC

Listas encadeadas (XI)

!  Representação de matrizes esparsas usando listas encadeadas

-  Representações CRS, BCRS, CDS, JDS, SKS etc. dão suporte a operações matemáticas eficientes (adição, multiplicação, produto interno etc.) quando a matriz é um operando, mas não a modificações na matriz (inclusão/exclusão de item) de forma eficiente

!  Problema relacionado à alocação estática de memória

-  Representações de lista encadeada e tabela de dispersão (hash) oferecem alternativas interessantes

LNCC

Listas encadeadas (XII)

!  Implementação de matrizes esparsas usando listas encadeadas

-  Cada coluna da matriz é representada por uma lista circular (com um nó cabeça)

!  Idem para cada linha

-  Elementos diferentes de zero na matriz (elementos ponto-flutuante) são representados por nós com a seguinte estrutura:

-  Nós cabeça possuem valores de line e column iguais a -1

struct node { struct node* right; struct node* below; int line; int column; float info; } typedef struct node Node;

LNCC

Listas encadeadas (XIII)

•  Comparação com implementação usando vetores?

�

⇧⇧⇤

50 0 0 010 0 20 00 0 0 0�30 0 �60 5

⇥

⌃⌃⌅

LNCC

Pilhas e filas (I)

!  Pilhas -  Novo elemento é inserido no topo e acesso é apenas ao

topo -  O primeiro que sai é o último que entrou

(LIFO – last in, first out) -  Operações básicas:

!  Empilhar (push) um novo elemento, inserindo-o no topo !  Desempilhar (pop) um elemento, removendo-o do topo

LNCC

Pilhas e filas (II)

!  TAD “Stack” em C (elementos ponto-flutuante): -  Operações principais:

!  Stack* stack_create(void) !  void stack_destroy(Stack* s) !  void stack_push(Stack* s, float v) !  float stack_pop(Stack* s) !  int stack_empty(Stack* s)

-  Duas implementações principais:

!  Como vetor !  Como lista encadeada

LNCC

Pilhas e filas (III)

!  Implementação de pilha com vetor -  elementos inseridos ocupam as primeiras posições do

vetor -  elemento vet[n-1] representa o elemento do topo

#define N 50 /* número máximo de elementos */ struct stack { int n; /* vet[n]: primeira posição livre do vetor */ float vet[N]; /* vet[n-1]: topo da pilha */ /* vet[0] a vet[N-1]: posições ocupáveis */ }; typedef struct stack Stack;

Stack* stack_create(void) { Stack* s = (Stack*) malloc(sizeof(Stack)); s->n = 0; /* inicia com zero elementos */ return s; }

LNCC

Pilhas e filas (IV)

!  Implementação de pilha com vetor (cont.)

void stack_push (Stack* s, float v) { if (s->n == N) { /* capacidade esgotada */ printf("Capacidade da pilha estourou.\n"); exit(1); /* aborta programa */ } /* insere elemento na próxima posição livre */ s->vet[s->n] = v; s->n++; }

float stack_pop (Stack* s) { float v; if (stack_empty(s)) { printf("Pilha vazia.\n"); exit(1); /* aborta programa */ } /* retira elemento do topo */ v = s->vet[s->n-1]; s->n--; return v; }

LNCC

Pilhas e filas (V)

!  Ex.: Notações para expressões aritméticas -  infixa = (1-2)*(4+5) -  pós-fixa = 1 2 – 4 5 + * -  pré-fixa = * - 1 2 + 4 5

!  Expressões pós-fixadas podem ser avaliadas em

uma pilha -  cada operando é empilhado numa pilha de valores -  quando se encontra um operador

!  desempilha-se o número apropriado de operandos (dois para operadores binários e um para operadores unários)

!  realiza-se a operação devida !  empilha-se o resultado

LNCC

Pilhas e filas (VI) !  Ex. (cont.): avaliação de 1 2 – 4 5 + *

LNCC

Pilhas e filas (VII)

!  Filas -  Um novo elemento é inserido ao final da fila -  Um elemento é retirado do início da fila -  Primeiro que entra é o primeiro que sai

(FIFO – first in first out) -  Operações básicas:

!  Enfileirar (enqueue) um novo elemento ao final da fila !  Retirar (dequeue) um elemento do início da fila

enqueue dequeue

LNCC

Pilhas e filas (VIII)

!  TAD “Queue” em C (elementos ponto-flutuante): -  Operações principais:

!  Queue* queue_create(void) !  void queue_destroy(Queue* q) !  void queue_enqueue(Queue* q, float v) !  float queue_dequeue(Queue* q) !  int queue_empty(Queue* q)

-  Duas implementações principais:

!  Como vetor !  Como lista encadeada

LNCC

Pilhas e filas (IX)

!  Implementação de fila com vetor -  Processo de inserção e remoção em extremidades

opostas da fila faz com que a fila “ande” no vetor -  Incremento das posições do vetor deve ser de forma

“circular” #define N 100 /* número máx. de elementos */ struct queue { int n; /* número de elementos na fila */ int ini; /* posição do próximo elemento a ser retirado da fila */ float vet[N]; }; typedef struct queue Queue;

Queue* queue_create(void) { Queue* q = (Queue*) malloc(sizeof(Queue)); q->n = 0; /* inicia com zero elementos */ q->ini = 0; /* escolhe posição inicial */ return q; }

LNCC

Pilhas e filas (X)

!  Implementação de fila com vetor (cont.) void queue_enqueue(Queue* q, float v) { int fim; if (q->n == N) { /* capacidade esgotada */ printf("Capacidade da fila estourou.\n"); exit(1); /* aborta programa */ } /* insere elemento na próxima posição livre */ fim = (q->ini + q->n) % N; q->vet[fim] = v; q->n++; }

float queue_dequeue(Queue* q) { float v; if (queue_empty(q)) { printf("Fila vazia.\n"); exit(1); /* aborta programa */ } /* retira elemento do início*/ v = q->vet[q->ini]; q->ini = (q->ini + 1)%N; q->n--; return v; }

LNCC

Pilhas e filas (XI)

!  Fila dupla: -  Fila na qual é possível:

!  inserir novos elementos no início e no fim !  retirar elementos de ambos os extremos

-  Simula, dentro de uma mesma estrutura, duas filas, com os elementos em ordem inversa uma da outra

!  Mudança no TAD, para incluir operações de queue e dequeue no início e no fim da fila

-  Implementações: !  Com vetor !  Com lista duplamente encadeada

LNCC

Pilhas e filas (XII)

!  Exs.: -  Filas de pacotes em roteadores -  Filas de tarefas aguardando a CPU em sistemas

operacionais

!  Caso especial de filas: priorização dos itens -  Exemplos acima! -  Métodos numéricos iterativos (seleção repetida de um

item com maior/menor valor) -  Sistemas de gerência de memória LRU (Least Recently

Used)

LNCC

Pilhas e filas (XIII) •  Fila de prioridades: valor associado a um elemento

reflete sua habilidade relativa de abandonar o conjunto de elementos rapidamente

•  TAD “PriQueue” em C (elementos ponto-flutuante): -  Operações principais:

!  PriQueue* priqueue_create(void) !  void priqueue_destroy(PriQueue* q) !  void priqueue_enqueue(PriQueue* q, float v) !  float priqueue_dequeue(PriQueue* q): retira maior/menor elemento !  float priqueue_peek(PriQueue* q): obtém maior/menor elem., sem

retirá-lo -  Implementações principais:

!  Como vetor ou lista encadeada (ordenados ou não) !  Como heap (não confundir com o homônimo usado em alocação

dinâmica de memória!)

LNCC

Pilhas e filas (XIV) •  Heap: sequência de itens c[1], c[2], …, c[n] tal que

c[i] >= c[2i] e c[i] >= c[2i+1] para todo i = 1, 2, ..., n/2 •  Definição corresponde a “max heaps” •  Implementação usual com vetores

•  Note que primeiro item tem sempre índice 1!!!

•  Ex. (max heap com elementos do tipo caracter): 1 2 3 4 5 6 7

S R O E N A D

#define N 101 /* num máx de elementos +1 !!*/ struct priqueue { int n; /* número de elementos na fila */ float vet[N]; /* posições ocupáveis: 1 a N-1 */ }; typedef struct priqueue PriQueue;

PriQueue* priqueue_create(void) { PriQueue* q = (PriQueue*) malloc(sizeof(PriQueue)); q->n = 0; /* inicia com zero elementos */ return q; }

LNCC

Pilhas e filas (XV)

•  Implementação de fila de prioridades com heap:

#include <float.h> … void priqueue_enqueue(PriQueue* q, float v) { if (q->n == N) { /* capacidade esgotada */ printf("Capacidade da fila estourou.\n"); exit(1); /* aborta programa */ } q->n++; q->vet[q->n] = -FLT_MAX; /*menor float existente */ increase(q, q->n, v); }

float priqueue_dequeue(PriQueue* q) { float v; if (q->n < 1) { printf("Fila vazia.\n"); exit(1); /* aborta programa */ } /* retira elemento do início*/ v = q->vet[1]; q->vet[1] = q->vet[q->n--]; rebuild(q); return v; }

float priqueue_peek(PriQueue* q) { if (q->n < 1) { printf("Fila vazia.\n"); exit(1); /* aborta programa */ } return q->vet[1]; }

LNCC

Pilhas e filas (XVI) •  Operações auxiliares para priqueue_enqueue() e

priqueue_dequeue(): •  static void rebuild(PriQueue *q): reconstrói a heap após retirada •  (static) void (priqueue_)increase(PriQueue *q, int i, float v): aumenta

valor do elemento na posição i para v

static void rebuild(PriQueue* q) { int left = 1; int j = left*2; float v = q->vet[left]; while (j <= q->n) { if ((j < q->n) && (q->vet[j] < q->vet[j+1])) j++; if (v >= q->vet[j]) break; q->vet[left] = q->vet[j]; left = j; j = left*2; } q->vet[left] = v; }

static void increase(PriQueue* q, int i, float v) { while ((i > 1) && (v >= q->vet[i/2])) { q->vet[i] = q->vet[i/2]; i /= 2; } q->vet[i] = v; }

LNCC

Cadeias de caracteres (I) !  Tipo básico caractere:

-  Em C: char (tamanho = 1 byte = 8 bits) !  Alguns alfabetos precisam de maior representatividade

-  Tabela de códigos: !  correspondência

entre caracteres e códigos numéricos

!  Exs.: ASCII (C/C++), Unicode (Java)...

LNCC

Cadeias de caracteres (II) !  Representação de cadeias de caracteres (strings)

em C: -  Vetor do tipo char, terminado pelo caractere nulo ('\0') -  É necessário reservar uma posição adicional no vetor

para o caractere de fim da cadeia !  Inicialização de cadeias de caracteres:

-  Vetor de caracteres (pouco usual) -  Caracteres entre aspas duplas

!  caractere nulo é representado implicitamente -  Exs: char s0[ ] = {’R’, ’i’, ’o’, ’\0’};

char s1[] = ""; char s2[] = "Rio de Janeiro"; char s3[81]; char s4[81] = "Rio";

LNCC

Cadeias de caracteres (III) !  Leitura de caracteres e cadeias de caracteres

através da entrada padrão (stdin) -  Operação scanf()

!  especificadores de formato definem comportamento !  Exs:

!  O que acontece com as entradas: -  “r”? -  “ r”? -  “rio”? -  “ rio”? -  “rio de janeiro\n”?

char a; ... scanf("%c", &a); ...

char a; ... scanf(" %c", &a); ...

char a[81]; ... scanf("%s", a); ...

char a[81]; ... scanf(" %[^\n]", a); ...

LNCC

Cadeias de caracteres (IV) !  Biblioteca de cadeias de caracteres padrão em C: string.h

-  size_t strlen(const char *s) -  char *strcpy(char *s1, const char *s2) -  char *strcat(char *s1, const char *s2) -  int strcmp(const char *s1, const char *s2) -  char *strdup(const char *s1) -  char *strstr(const char *s1, const char *s2) -  ...

!  Para cada uma dessas operações, pode-se imaginar implementações recursivas, se considerarmos que uma cadeia de caracteres é:

-  Uma cadeia vazia ou -  Um caracter seguido de uma (sub)cadeia

LNCC

Cadeias de caracteres (V)

!  Uma nota sobre constantes do tipo cadeia de caracteres:

-  Avaliação da constante resulta no ponteiro para onde a cadeia de caracteres está armazenada

-  Cuidado: o que acontece se executarmos ?

char cidade[4]; strcpy (cidade, "Rio" ); printf ( "%s \n", cidade );

char *cidade = "Rio"; printf ( "%s \n", cidade ); ou ou

char cidade[] = "Rio"; printf ( "%s \n", cidade );

cidade[2] = 'x';

LNCC

Cadeias de caracteres (VI)

!  Vetores de cadeias: -  Alocação estática:

!  Matriz de elementos do tipo char -  Alocação dinâmica:

!  Vetor de ponteiros !  Cada cadeia de caracteres (elemento do vetor) é alocada

dinamicamente

!  Nota (geral!) sobre alocação dinâmica e papel de clientes e provedores no contrato de uma função:

-  Idealmente (mas nem sempre!) quem aloca tem que desalocar depois

LNCC

Cadeias de caracteres (VII)

!  Um caso especial em C: função main()

!  Quais os valores de argc e argv caso o executável seja chamado como: ?

int main (int argc, char** argv) { … }

nome_programa param1 param2

LNCC

Cadeias de caracteres (VIII)

!  Processamento de cadeias

-  Inúmeras aplicações: !  Processamento de textos !  Recuperação de informação !  Sequenciamento de DNA !  Representação de imagens !  ...

-  Principais operações:

!  Casamento de cadeias (ou casamento de padrões) !  Compressão de cadeias

LNCC

Cadeias de caracteres (IX) !  Casamento de cadeias

-  Casamento exato

-  Casamento aproximado: operações de inserção, substituição e retirada de caracteres do padrão são permitidas

!  Conceito de distância de edição !  Ex. (dist. edição = 1)

LNCC

Cadeias de caracteres (X) !  Casamento exato:

-  Leitura dos caracteres

do texto um a um: !  Algoritmos força bruta,

Knuth-Morris-Pratt e Shift-And

!  Ex. força bruta: -  Códigos C++: [Ziviani, 2007, págs. 531-532]

-  Uso de uma janela que desliza pelo texto, pesquisando

por sufixo da janela que casa com sufixo do padrão, por comparações da direita p/ a esquerda:

!  Algoritmos Boyer-Moore-Horspool e BMH-Sunday -  Códigos C++: [Ziviani, 2007, págs. 532-533]

char *forcaBruta ( char * texto, char *padrao ) { int n = strlen(texto); int m = strlen(padrao); for ( int i = 0; i < (n − m + 1) ; i ++) { int k = i; int j = 0; while ( ( j < m) && (texto[k] == padrao[j] ) ) ) { j ++; k++; } if ( j ==m) return &texto[i]; } return NULL; }

LNCC

Cadeias de caracteres (XI) !  Compressão de cadeias:

-  Motivação: explosão de informação textual disponível !  Bibliotecas digitais !  Bancos de dados de documentos !  World-Wide Web

-  Além da economia de espaço, deve-se considerar: !  Velocidade de compressão e de descompressão !  Possibilidade de realizar casamento de cadeias diretamente

no texto comprimido !  Permitir acesso direto a qualquer parte do texto comprimido e

iniciar a descompressão a partir da parte acessada -  Algumas técnicas:

!  Huffman (baseado em caracteres e palavras), Ziv-Lempel (eficiente na compressão, ineficiente no casamento), Moffat e Katajainen (melhorias no Huffman)