Tipos de dados complexos - FCUP - Departamento de Ciência ...nam/aulas/0102/pi/slides/slipi07.pdf · Estruturas - elementos de tipos diferentes mas de tamanho ﬁxo (est´aticas)

Tipos de dados complexos

Considera os seguintes problemas:

1. Contar as ocorrencias de cada caracter num ficheiro de texto.

2. Determinar a maior palavra de um ficheiro de texto.

3. Ordenar uma sequencia de valores. Exemplo:

• inteiros por ordem crescente• letras do alfabeto• palavras por ordem lexicografica

4. Operacoes sobre conjuntos finitos de inteiros

5. Suponha um conjunto de alunos em cada aluno tem um nome e uma nota.Pretende-se saber qual o nome do aluno que teve melhor (ou pior) nota.

Departamento de Ciencia de Computadores da FCUP — PI — Aula 7 1

Para cada um dos problemas anteriores nao e possıvel, duma forma geral, representara informacao usando variaveis simples (escalares), isto e, em que se associa umnome a um so valor.

Os tipos de dados complexos em C, construıdos a partir de tipos simples, permitemassociar um so nome a um conjunto de elementos, e distinguem-se por:

Variaveis indexadas - numero fixo de elementos do mesmo tipo (estaticas).Oındice pode ter uma ou varias dimensoes.

Estruturas - elementos de tipos diferentes mas de tamanho fixo (estaticas).

Estruturas de dados dinamicas : o numero de elementos pode serdinamicamente modificado durante a execucao.


Variaveis Indexadas Unidimensionais

[ePD94, Cap. 6.1-4]

Permitem manipular um conjunto (sequencia) de elementos do mesmo tipo:

a 8 5 6 1 3 9 4

Os elementos sao referidos pelo seu ındice i (posicao):

i 0 1 2 3 4 5 6a[i] 8 5 6 1 3 9 4

Em C uma variavel indexada ao ser declarada tem de ter:

1. um tipo, que e o tipo de cada elemento

2. um tamanho, que e o numero de elementos que a variavel pode conter e cujoespaco de memoria e reservado. Tem de ser uma constante inteira.

3. um nome


int a[7];

Reserva memoria para 8 inteiros

Os ındices dos elementos sao numerados a partir de 0.

main() {int i, a[7];

a[0] = 8; a[1] = 5; a[2] = 6; a[3] = 1;a[4] = 3; a[5] = 9; a[6] = 4;for(i = 0; i < 7; i++)printf("a[%d]= %d\t",i,a[i]);

printf("\n");}

Execucao:

% vi1a[0]= 8 a[1]= 5 a[2]= 6 a[3]= 1 a[4]= 3 a[5]= 9 a[6]= 4

Pode-se usar #define MAX 7 e depois int a[MAX] ...


O que imprime o seguinte programa?

#define MAX 10main() {int i,a[MAX],b[MAX];a[0]=1;b[MAX-1]=1;for(i=1;i<MAX;i++) {a[i]=a[i-1]*2;b[MAX-i-1]=a[i];

}for(i=0;i<MAX;i++)printf("%3d %3d %3d\n",i,a[i],b[i]);

}

Execucao:% vi20 1 5121 2 2562 4 1283 8 644 16 325 32 166 64 87 128 48 256 29 512 1


Inicializacao de variaveis indexadas

1. Elemento a elemento.int a[4], b[10];a[0]=3; a[1]=4;a[2]=10; a[3]=5;for(i=0;i<10;i++)

scanf("%d",&b[i]);

#define TAM 10int s[TAM], i;for(i=0;i<TAM; i++)

s[i]=2+2*i;

2. Na declaracao das variaveis, com um sinal = seguido duma lista de valoresseparados por , e entre chavetas

int a[4]={3,4,10,5}; a 3 4 10 5

ouint a[]={3,4,10,5}; a 3 4 10 5

neste caso, sao reservados tantos elementos quanto os da inicializacao.Departamento de Ciencia de Computadores da FCUP — PI — Aula 7 6

ou

int a[4]={3,4}; a 3 4 0 0

neste caso, so os dois primeiros elementos sao inicializados mas os restantes saoautomaticamente inicializados em 0. Assim, em

int s[100]={0};

as 100 posicoes sao inicializadas em 0.

Nota: O C nao verifica (nao da erro sintactico) se e um ındice e maior que otamanho da variavel. E o seu comportamento pode ser imprevisıvel...

int a[10], i;for (i = 0; i <= 10; i++) a[i] = 0;

Pode entrar em ciclo! Como?Se a variavel i estiver guardada a seguir a a[9] e oprograma ao executar a[10]=0, esta realmente a fazer i=0...


Taxas de juro

Problema 1. Determinar o valor de 100 euros investidos a diferentes taxas dejuro durante um certo perıodo de anos.

Se fosse so a uma taxa de juro, nao era necessario uso de variaveis indexadas...

scanf("%d %d",&taxa,&num_anos);valor = 100;for(ano = 1; ano<= num_anos; ano++)valor += (float) taxa / 100 * valor;

mas para ano e necessario de terminar o valor para cada uma das diferentes taxas...

Vamos usar uma variavel indexada int valor[NUM TAXAS]que guarda para cadataxa o valor em cada ano.

Nota: outra solucao era calcular primeiro os valores para uma taxa ao longo detodos os anos, depois para outra, etc...


#define BALANCO_INICIAL 100.0#define NUM_TAXAS 5main() {int taxa_inicial, num_anos, i, ano; float valor[5];printf("Introduzir taxa de juro:");scanf("%d",&taxa_inicial);printf("Introduzir numero de anos:");scanf("%d",&num_anos);printf("\n Anos");for(i = 0; i < NUM_TAXAS; i++ ) {printf("%6d%%",taxa_inicial+i);valor[i] = BALANCO_INICIAL; }

printf("\n");for (ano = 1; ano <= num_anos; ano++) {printf("%3d ",ano);for(i = 0; i < NUM_TAXAS; i++ ) {valor[i] += (float) (taxa_inicial + i)/100 * valor[i];printf("%7.2f",valor[i]);}

printf("\n");}}


Execucao:

%./taxasIntroduzir taxa de juro:6Introduzir numero de anos:5


Anos 6% 7% 8% 9% 10%1 106.00 107.00 108.00 109.00 110.002 112.36 114.49 116.64 118.81 121.003 119.10 122.50 125.97 129.50 133.104 126.25 131.08 136.05 141.16 146.415 133.82 140.26 146.93 153.86 161.05

%


Dado um conjunto de 30 valores de 1 a 10 determinar amedia, qual a frequencia de cada valor e o histograma.

1,2,6,4,8,5,9,7,8,10,1,6,2,3,3,5,8,4,6,5,4,3,6,7,8,4,4,4,4,5

Algoritmo:

1. Supomos que os valores estao numa variavel indexada valores e na variavelindexada frequencia irao ser contadas as ocorrencias de cada classificacao:a i-esima posicao correspondendo ao numero de ocorrencias do valor i.Por exemplo,se no fim o conteudo de frequencia[4] for 7, significa que o valor 4 ocorreu7 vezes.

Na variavel inteira soma ira ser calculada a soma dos valores.

2. Para r = 0...30:

valores[r] sera adicionado a variavel soma e o contador correspon-dente (frequencia[valores[r]]) sera incrementado.


#include<stdio.h>#define TAM 30#define FREQ 11main() {int valores[TAM] = {1,2,6,4,8,5,9,7,8,10,1,6,2,3,3,5,8,4,6,5,

4,3,6,7,8,4,4,4,4,5};int frequencia[FREQ] = {0};int r,c, soma = 0;for(r = 0; r < TAM; r++){soma += valores[r]; ++frequencia[valores[r]];

}printf("Valores Frequencia Histograma\n");for(c = 1; c < FREQ; c++) {printf("%4d%8d\t\t",c,frequencia[c]);for(r = 0; r < frequencia[c]; r++) printf("*");printf("\n");

}printf("Media=%3.1f\n",(float)soma/TAM);

}


Compilacao e execucao:

%cc freq.c -o freq% freqValores Frequencia Histograma

1 2 **2 2 **3 3 ***4 7 *******5 4 ****6 4 ****7 2 **8 4 ****9 1 *10 1 *

Media=5.1

Exercıcio 7.1. Reescrever o programa da simulacao de 6000 lancamentos deum dado, usando variaveis indexadas. �


Manipulacao dos elementos duma variavel indexada

Nestes caso o ındice do elemento nao tem outro significado, senao de indicar a suaordem...

Problema 2. Escreve uma parte de programa que desloque os n-1 primeiroselementos, de uma variavel indexada a[], uma posicao para a direita (supondo quese reservou espaco...).

Resolucao 2

Por exemplo, 8 5 6 1 3 devia ficar 8 8 5 6 1 3

Primeira tentativa:

for(i = 0; i < n - 2;i++) a[i+1] = a[i];

Resultado: 8 8 8 8 8 8 ERRADO!!

Resolucao correcta:

for(i = n - 2;i > 0;i--) a[i+1] = a[i];


Aplicacao

Inserir um elemento x na posicao j < n, deslocando os elementos para a direita...se estiver reservado espaco.

Por exemplo, se 8 5 6 1 3

e x = 12 e j = 3 deve resultar

8 5 6 12 1 3

for(i = n - 1; i >= j; i--)a[i+1] = a[i];

a[j] = x;


Inversao dos elementos

Problema 3. Escreve uma parte de programa que troque simetricamente os nelementos de uma variavel indexada a[], isto e, a[0] troca com a[n-1], a[1]troca com a[n-2],etc. Por exemplo,

8 5 6 1 3

deve ficar

3 1 6 5 8

Resolucao 3

Ideia: para i=0..n-1 trocar a[n-1-i] com a[i]. Como?

Primeira tentativa:for(i = 0;i < n;i++) {a[n-1-i] = a[i];a[i] = a[n-1-i];

}

Resultado: 8 5 6 5 8 ERRADO!!


E faz duas vezes cada um... Entao basta percorrer metade dos valores: n/2

E como nao estragar? Utilizando uma auxiliar variavel (simples) ... (como quandose troca o valor de x com o valor de y...)

Resolucao correcta:

for(i = 0;i < n/2; i++) {aux = a[n-1-i];a[n-1-i] = a[i];a[i] = aux;

}


Operacoes sobre conjuntos

[ePD94, Cap. 6.8]

As variaveis indexadas representam conjuntos finitos de dados em que cada elementotem uma posicao determinada e pode ocorrer mais que uma vez. No entanto podem-se definir algoritmos para implementar as operacoes basicas sobre conjuntos: x ∈ C,A ∪B, A ∩B, A−B, A ⊂ B, etc.


Pesquisa

Problema 4. Procurar se um valor x existe numa variavel indexada a[]:a[0],. . . ,a[n-1].

A resposta pode ser:

1. Um ındice i tal que x = a[i].

2. -1 se nao houver nenhum i nessas condicoes.

Seja a seguinte variavel indexada, com n = 7i 0 1 2 3 4 5 6

a[i] 8 5 6 1 3 9 4

Se x = 9 a resposta deve ser 5 pois a[5] = 9.Exercıcio 7.2. Quais deveriam ser as respostas para os seguintes valores de x:0, 8 e 1? �


Pesquisa Linear: um algoritmo

Ideia:Para i = 0, 1,. . . ,n− 1 comparamos a[i] com x. Se forem iguais, o resultadoe i. Se nunca forem iguais, o resultado e −1.#include<stdio.h>main(){int x, pos;

int a[] = {8,5,6,1,3,9,4}, n = 7;scanf("%d",&x);for(i = 0;i < n;i++) if(a[i] == x) break;if (i < n) pos = i;else pos = -1;if(pos >= 0)printf("Posicao = %2d\n",pos);

elseprintf("Nao ocorre em a[ ]\n");

}


Execucao:

$proc3Posicao = 4$proc4Posicao = 6$proc12Nao ocorre em a[ ]

Exercıcio 7.3. Considera as seguintes alteracoes ao programa anterior:

1. Usando a instrucao de ciclo “while” sem utilizar “break”.Uma solucao:.

i=0;while(i<n && a[i]!=x) i++;/* Pela semantica do "&&" a comparacao a[n] != x nunca se faz */


2. Simplifica e melhora a eficiencia do programa anterior, comecando por colo-car x em a[n], supondo-se que esta posicao esta livre.Uma solucao:

i = 1; a[n] = x;while(a[i] != x) i++; /* termina sempre! */pos = i<n? i: -1;

Poupaste em cada iteracao uma comparacao e uma instrucao if...

�

Exercıcio 7.4. Sao dados a[] e b[] com respectivamente m e n elementos.Pretende-se escrever os elementos que pertencem a interseccao dos conjuntosrepresentados. Por exemplo, se a[] e b[] sao8 6 5 1 3 e 2 1 4 6 , deve ser escrito 6 e 1. �


Pesquisa e Ordenacao

[?, Cap. 4.4-5]

Se os valores da sequencia estiverem ordenados a pesquisa pode ser efectuada deforma mais eficiente. Vamos supor os valores ordenados por ordem crescente.

Como se procura um numero de telefone numa lista telefonica (ordenadapor nome)?E se nao estivesse ordenada?

O que acontece numa pesquisa linear? Seja x=30.

-1 8 14 25 45 78 90

Resposta:Nao e necessario continuar se a[i] > x!

Mas se n grande e/ou o x nao estiver la, nao adianta muito...

Suponhamos v[0],. . . , v[n-1] uma sequencia ordenada. Comparar x com oelemento do meio da sequencia: seja m=(n-1)/2 o seu ındice:

• Se x = v[m], eureka, a resposta e m.


• Se x < v[m], o valor x so pode estar nos ındices compreendidos entre 0 e m-1(inclusive).

• Se x > v[m], o valor x so pode estar nos ındices compreendidos entre m+1 e n-1(inclusive).

So com uma comparacao ou encontramos x ou eliminamos cerca de n/2 elementos!


Pesquisa binaria

Algoritmo

Sejam em cada passo a e b os ındices entre os quais pode estar x

• Inicialmente a=0 e b=n-1

• Se a > b o intervalo e vazio, x nao esta em v[]

• Seja m = (a + b)/2. Ao comparar x com v[m]

1. Se x < v[m], b passa a ser m− 1 (a mantem-se)

2. Se x > v[m], a passa a ser m+1 (b mantem-se)

3. Se x = v[m], o ındice foi encontrado: m.


Vamos escrever uma funcao que retorna o ındice de x ou -1, caso x nao esteja navariavel indexada...

int pb(int x, int a, int b) {int m;while(a <= b) {m = (a + b) / 2;if (x == v[m]) return m;if (x < v[m])b = m - 1; /* quando x < v[m] */

elsea = m + 1; /* quando x > v[m] */

}return -1; /* n~ao esta */

}


Suponhamos:

i 0 1 2 3 4 5 6v[i] -1 2 4 6 7 9 15

Procurar x=8:a=0, b=6, m=3a=4, b=6, m=5a=4, b=4, m=4-1

Procurar x=15:a=0, b=6, m=3a=4, b=6, m=5a=6, b=6, m=66

Procurar x=0:a=0, b=6, m=3a=0, b=2, m=1a=0, b=0, m=0-1

Numero maximo de iteracoes: log2(n)


Ordenacao

[ePD94, Cap. 6.6]

2 15 -1 7 9 4 6

Existem muitos metodos de ordenar ....

bolha (bublesort)Percorrer os elementos da sequencia e comparar pares de ele-mentos consecutivos trocando-os se nao estiverem ordenados. Ao fim de umaiteracao o elemento maior encontrado (e na ultima posicao). Repetir o processoate todos os elementos estarem ordenados (no maximo n vezes).

Para i=0,... n-1 e enquanto houver trocaspara j=0,... n-i-2se a[j]>a[j+1] trocar a[j] com a[j+1]


insercao (usado para ordenar em jogos de cartas) Introduzir cada elemento a[i],na subsequencia ordenada de a[0], . . . , a[i-1] de modo a mante-la ordenada.

Para i=1,... n-1faca x=a[i]inserir x na posic~ao correcta entreas posic~oes 0 e i-1

selecao selecionar sucessivamente o menor elemento da sequencia e coloca-lo naprimeira posicao nao ordenada.

quicksort . . .

...


Metodo da selecao

Seja v[0], . . . v[n-1] a sequencia a ordenar.

Ideia: Para i=1,. . . , n-2:

Supondo que de v[0] a v[i-1] esta ordenado, procurar de v[i+1] a v[n-1] oelemento menor e troca-lo com v[i]; fica ordenado de v[0] a v[i]

void selord() {int i;for(i = 0;i < n-1;i++){int j, min = i, t;/* min: indice do menor entre pos. i+1 e n-1 */for(j = i + 1; j < n;j++)if(v[j] < v[min]) min=j;

/* Agora trocamos v[i] <-> v[min] */t=v[i]; v[i]=v[min]; v[min]=t;}

}


Considerando:

int n=7, v[] = {2,15,-1,7,9,4,6};void selord();main() {selord();}

Execucao, escrevendo o valor de v[] no fim de cada iteracao:

2 15 -1 7 9 4 6-1 15 2 7 9 4 6-1 2 15 7 9 4 6-1 2 4 7 9 15 6-1 2 4 6 9 15 7-1 2 4 6 7 15 9-1 2 4 6 7 9 15


Explicacao

i 0 1 2 3 4 5 6v[i] 2 15 -1 7 9 4 6--------------------------------------------------v[i] 2 15 -1 7 9 4 6 0..6: min=-1v[i] -1| 15 2 7 9 4 6 1..6: min=2v[i] -1 2| 15 7 9 4 6 2..6: min=4v[i] -1 2 4| 7 9 15 6 3..6: min=6v[i] -1 2 4 6| 9 15 7 4..6: min=7v[i] -1 2 4 6 7|15 9 5..6: min=9v[i] -1 2 4 6 7 9|15--------------------------------------------------

Para estimar a eficiencia, podemos contar o numero c(n) de vezes que a com-paracao da instrucao if(v[j]<v[min]). . . e efectuada (uma das que e mais vezesefectuada. . . ): c(n) = (n− 1) + (n− 2) + · · ·+ 1 = n(n− 1)/2 = (n2 − n)/2

Dizemos que se trata de um algoritmo de ordem O(n2).


Ordenacao, pesquisa e mais alguma coisa...#include <stdio.h>int n=7;int v[] = {2,15,-1,7,9,4,6};void selord ();main() {int i;selord();printf("Procura:\n"); scanf("%d",&i);printf("\n\n %2d ", pb(i,0,n-1));

}void selord() {int i;for(i=0;i<n-1;i++){int j, min=i, t;/* min: indice do menor entre pos. i+1 e n */for(j=i+1;j<n;j++)if(v[j]<v[min])min=j;


/* Agora trocamos v[i] <-> v[min] */t=v[i];v[i]=v[min];v[min]=t;

}}/* pesquisa binaria */int pb(int x,int a, int b) {int m;while(a<=b){m=(a+b)/2;printf("a=%d, b=%d, m=%d\n",a,b,m);if(x==v[m]) return(m);if(x<v[m]) b=m-1;else a=m+1;

}return(-1);

}


Leituras

[ePD94, Cap. 6.1-4,6-8] [?, Cap. 4.4-5]


Referencias

[Bro97] J. Glenn Brookshear. Computer Science, an overview. Addison-Wesley,1997.

[ePD94] H.M. Deitel e P.J. Deitel. C:How to Program. Prentice Hall InternationalEditions, 2 edition, 1994.


Documents

Tipos de dados complexos - FCUP - Departamento de Ciência ...nam/aulas/0102/pi/slides/slipi07.pdf · Estruturas - elementos de tipos diferentes mas de tamanho ﬁxo (est´aticas)