Estruturas de Dados Elementares

Prévia do material em texto

L
N
C
C 
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 
L
N
C
C 
Estruturas de dados elementares 
!  Matrizes 
 
!  Listas encadeadas 
 
!  Pilhas e filas 
 
!  Cadeias de caracteres 
 
L
N
C
C 
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”) 
L
N
C
C 
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)); 
L
N
C
C 
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 ) 
L
N
C
C 
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)); 
... 
L
N
C
C 
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)); 
... 
L
N
C
C 
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 
L
N
C
C 
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 0
3 9 0 0 0 3
0 7 8 7 0 0
3 0 8 7 5 0
0 8 0 9 9 13
0 4 0 0 2 �1
⇥
⌃⌃⌃⌃⌃⌃⌅
L
N
C
C 
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 -1
col ind 1 5 1 2 6 2 3 4 1 ... 5 6 2 5 6
�
⇧⇧⇧⇧⇧⇧⇤
10 0 0 0 �2 0
3 9 0 0 0 3
0 7 8 7 0 0
3 0 8 7 5 0
0 8 0 9 9 13
0 4 0 0 2 �1
⇥
⌃⌃⌃⌃⌃⌃⌅
L
N
C
C 
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 
L
N
C
C 
Matrizes (X) 
!  Outras formas de representação: 
 
-  Compressed Diagonal Storage (CDS) 
 
!  Matrizes de banda fixa 
 
 
 
 
 
 
 
 
�
⇧⇧⇧⇧⇧⇧⇤
10 �3 0 0 0 0
3 9 6 0 0 0
0 7 8 7 0 0
0 0 8 7 5 0
0 0 0 9 9 13
0 0 0 0 2 �1
⇥
⌃⌃⌃⌃⌃⌃⌅
val(:,-1) 0 3 7 8 9 2
val(:, 0) 10 9 8 7 9 -1
val(:,+1) -3 6 7 5 13 0
L
N
C
C 
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] 
 
L
N
C
C 
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() 
 
L
N
C
C 
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 
L
N
C
C 
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 
L
N
C
C 
Listas encadeadas (IV) 
!  Tipos de listas: 
 
 
-  Listas encadeadas simples 
 
 
-  Listas circulares 
 
 
-  Listas duplamente 
encadeadas 
L
N
C
C 
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); 
} 
L
N
C
C 
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; 
} 
L
N
C
C 
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; 
} 
L
N
C
C 
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); 
} 
L
N
C
C 
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; 
} 
L
N
C
C 
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; 
}; 
L
N
C
C 
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 
L
N
C
C 
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; 
L
N
C
C 
Listas encadeadas (XIII) 
•  Comparação 
com implementação 
usando vetores? 
�
⇧⇧⇤
50 0 0 0
10 0 20 0
0 0 0 0
�30 0 �60 5
⇥
⌃⌃⌅
L
N
C
C 
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 
L
N
C
C 
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 
L
N
C
C 
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; 
} 
L
N
C
C 
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; 
} 
L
N
C
C 
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 
L
N
C
C 
Pilhas e filas (VI) 
!  Ex. (cont.): avaliação de 1 2 – 4 5 + * 
L
N
C
C 
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 
L
N
C
C 
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 
L
N
C
C 
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; 
} 
L
N
C
C 
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; 
} 
L
N
C
C 
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 
L
N
C
C 
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) 
 
L
N
C
C 
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!) 
 
L
N
C
C 
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; 
} 
L
N
C
C 
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]; 
} 
L
N
C
C 
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; 
} 
L
N
C
C 
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)... 
L
N
C
C 
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"; 
L
N
C
C 
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); 
... 
L
N
C
C 
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 
L
N
C
C 
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'; 
L
N
C
C 
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 
L
N
C
C 
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 
L
N
C
C 
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 
L
N
C
C 
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) 
L
N
C
C 
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; 
} 
L
N
C
C 
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-WideWeb 
-  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)