Estruturas de Dados - Representação Básica de Informações

Prévia do material em texto

CIC/UnB - Estruturas de 
dados
Representação básica de informações
O que é dado/informação?
● Dado é geralmente usado para valores de 
atributos, por exemplo:
idade = 25
sexo = feminino
● Informação diz respeito a um conjunto de 
dados já trabalhados, por exemplo:
17,5% dos jovens brasilienses fumam
Estruturas de dados
● Compreendem os métodos para 
– Representar os dados nos computadores
– Permitir o acesso aos dados visando 
facilitar a sua transformação em 
informações
Representações 
elementares
● Os dados são representados através de 
dígitos binários, com valores 0 e 1
● Um computador de 16 bits por palavra pode, 
por exemplo, representar um número inteiro 
não negativo entre 0 e 65535:
0: 0000000000000000
1: 0000000000000001
 ...
65535: 1111111111111111
Representações 
elementares
● Ou números inteiros entre -32767 e +32767 em 
complemento de 1:
1000000000000000 a 0111111111111111
● Ou números entre -32768 e +32767 em 
complemento de dois (pega-se a representação 
negativa em complemento de 1 e soma-se 1)
Representações 
elementares
● Números também podem ser representados 
como concatenações de números decimais:
P ex. 2 0 0 8
 0010 0000 0000 1000
Nesse caso há um ´´desperdício´´ de 
capacidade informacional, pois as 
combinações acima de 1010 não são usadas
Representações 
elementares
● Números reais são representados em ponto 
flutuante, onde há uma ´´mantissa´´ e um 
expoente (em base 10, geralmente).
● O número -387,53, por exemplo seria 
representado como -38753 x 10-2
● Para uma máquina de 32 bits, podemos ter 
24 bits para a mantissa e 8 para expoente:
 11111111011010001001111111111110
Representações 
elementares
● Caracteres também são representados 
através de convenções – códigos como 
o ASCII, o EBCDIC, o BCL, entre outros.
● Em EBCDIC, ¨A¨ é representado como
 11000000 e ¨B¨ como 11000001
portanto, a cadeia ¨AB¨ é guardada 
assim:
 1100000011000001
Representações 
elementares
● Portanto, os bits per si não tem significado 
algum. O significado busca-se na 
interpretação de suas seqüências, de acordo 
com uma particular convenção.
● Normalmente os dados são guardados no 
computador e depois buscados de volta com 
um mapa da mina. Podemos, por exemplo, 
convencionar que na primeira palavra de 
memória guardaremos a variável ¨A¨ , na 
segunda a ¨B¨ e assim por diante.
Representações 
elementares
● As modernas linguagem de 
programação e os sistemas de 
gerência de arquivos e bancos de 
dados são poderosas abstrações que 
trazem embutidas convenções sobre 
como guardamos nossos dados e 
informações no computador.
● Sem essas ferramentas estaríamos 
engatinhando nas tecnologias de 
informação e comunicação, as TICs.
Representações 
elementares
● As linguagens de programação utilizam 
esquemas de nomeação de dados que 
mascaram os detalhes de implementação
● Por exemplo, quando se escreve em C:
a = a + b
o primeiro ¨a¨ representa um endereço onde 
o valor de ¨a¨ + ¨b¨ será armazenado
Representações 
elementares
● Os detalhes tais como onde estão 
esses dados e como eles estão 
armazenados (tipos de dados) são 
abstraídos e tratados pelo compilador.
● Em linguagem de máquina, uma 
operação como essa pode ser bem 
mais complicada de se realizar.
Tipos de dados em C
● A linguagem C contem quatro tipos 
básicos de dados:
– int (short, long unsigned)
– float
– char
– double 
Ponteiros em C
● Se houver um inteiro declarado como:
int x
&x é o endereço que esse inteiro ocupa.
Ele é chamado ponteiro de x 
Ponteiros em C
● É também possível declarar variáveis 
que são ponteiros:
int *pi;
float *pf;
char *pc;
● O * indica que o valores são ponteiros 
para variáveis do tipo indicado – pi é 
um ponteiro para um inteiro, e assim 
por diante.
Ponteiros em C
● Por exemplo, pode-se fazer:
pi = &x (se x for um inteiro)
● Já o valor contido na posição apontada 
por pi pode ser obtido assim:
y = *pi
Ponteiros em C
● Como os ponteiros têm tipos, existe uma 
aritmética de ponteiros. Por exemplo, se 
existe um int *pi, então
 pi + 1
é o próximo ponteiro de inteiro, após pi.
(se o inteiro é representando em 4 palavras, 
o endereço será 4 unidades maior)
Vetores em C
● É um conjunto finito e ordenado de 
elementos homogêneos:
int a[100]
Define um conjunto de 100 inteiros 
numerados de 0 a 99.
● Para inicializá-lo com zeros:
for (i=0; i<100; a[i++] = 0);
Vetores em C
● Uma abordagem melhor ainda:
#define MAX 100
int a[MAX];
for (i=0; i<MAX; a[i++] = 0);
(para alterar o tamanho do vetor 
altera-se apenas o valor de MAX)
Uso de vetores 
unidimensionais
● Suponha que você queira ler n 
números, calcular sua média e verificar 
quanto cada um deles se desvia da 
média:
#define MAX 10
 int num[MAX];
 int i, total;
 float media, dif;
(n aquí é 10)
Uso de vetores 
unidimensionais
● Para ler, achar a média e imprimí-la:
total=0;
 for (i=0; i<MAX;i++) {
 scanf("%d", &num[i]);
 total+=num[i];
 }
 media= (float) total / (float) MAX;
 printf("\ntotal=%d, 
media=%f",total,media);
Uso de vetores 
unidimensionais
● Para imprimir as diferenças:
 printf("\ntotal=%d, media=%f",total,media);
 printf("\nDiferença dos números\n");
 for (i=0;i<MAX;i++) {
 dif=(float) num[i]- media;
 printf("num= %d dif= %f\n", num[i], dif);
 }
Uso de vetores 
unidimensionais
● #include <stdio.h>
● #define MAX 10
● tiramedia()
● {int num[MAX];
● int i, total;
● float media, dif;
● 
● total=0;
● for (i=0; i<MAX;i++) {
● scanf("%d", &num[i]);
● total+=num[i];
● }
● media= (float) total / (float) MAX;
● printf("Total=%d, media=%f",total,media);
● printf("\nDiferença dos números\n");
● for (i=0;i<MAX;i++) {
● dif=(float) num[i]- media;
● printf("num = %d dif= %f\n", num[i], dif);
● }
● }
● int main () {
● tiramedia();
● return 0;
● }
Uso de vetores 
unidimensionais
● kurumin@kurumin:~/UnB/EstDad/prog$ gcc media.c
● kurumin@kurumin:~/UnB/EstDad/prog$ ./a.out
● 5
● 7
● 8
● 9
● 6
● 4
● 3
● 2
● 1
● 5
● Total=50, media=5.000000
● Diferença dos números
● num = 5 dif= 0.000000
● num = 7 dif= 2.000000
● num = 8 dif= 3.000000
● num = 9 dif= 4.000000
● num = 6 dif= 1.000000
● num = 4 dif= -1.000000
● num = 3 dif= -2.000000
● num = 2 dif= -3.000000
● num = 1 dif= -4.000000
● num = 5 dif= 0.000000
● 
Vetores
● A estrutura de dados “vetor“, portanto é uma 
seqüência de elementos de mesmo tipo (e 
tamanho), na qual qualquer dos elementos 
pode ser acessado mediante indexação.
● É uma estrutura básica que servirá de apoio 
à implementação da maioria das demais 
estruturas de dados.
● É chamada de array em outras linguagens, 
arranjo em português.
Vetores
● É interessante verificar que na declaração
int num[MAX]
num é um endereço a partir do qual foram 
alocados MAX inteiros. Assim,
num[0] equivale a *num
num[1] equivale a *(num+1)
 ...
num[9] equivale a *(num+9)
Vetores
● #include <stdio.h>
● #define MAX 5
● tiramedia()
● {int num[MAX];
● int i, total=0;
● float media, dif;
● for (i=0; i<MAX;i++) {
● scanf("%d",num+i); /* era &num[i] */
● total+=*(num+i); /* era num[i] */
● }
● media= (float) total / (float) MAX;
● printf("Total=%d, media=%f\n",total,media);
● printf("Diferença dos números\n");
● for (i=0;i<MAX;i++) {
● dif=(float) *(num+i)- media; /* era num[i] */
● printf("num = %d dif= %f\n",*(num+i), dif); /* idem */
● }
● }
● int main () {
● tiramedia();
●return 0;
● }
Vetores X Strings
● Os vetores pressupõem elementos de 
mesmo tamanho
● Strings (cadeias de caracteres ou 
simplesmente cadeias) de caracteres 
são geralmente de tamanhos diversos
● Como resolver?
Vetores X Strings
● Em C convenciona-se que as cadeias 
terminam com um caractere com valor 0, 
representado por ''\0'', por exemplo:
Alô!\0
Bom dia,\0
Como vai você?\0
● Essas três frases poderiam estar 
representadas em dois vetores em memória, 
um para marcar os inícios das frases e outro 
para contê-las
Vetores X Strings
● 
0
5 Alô!\0Bom dia!\0Como vai você?\0
14
 
Vetores como parâmetros
● Quando passamos vetores como parâmetros 
devemos passar o endereço – passagem por 
referência é mais eficiente que por valor
● O tamanho não é declarado no procedimento 
que o recebe
● Qualquer alteração em elementos do vetor 
será feita realmente (diferentemente de 
variáveis passadas por valor)
Vetores como parâmetros
● #include <stdio.h>
● float avg(a,size)
● float a[ ] ; int size;
● {
● int i; float sum=0;
● for (i=0;i<size;i++) sum+=a[i];
● return (sum/size);
● }
● main() {
● #define SZ 4
● int i;
● float a[SZ];
● for (i=0; i<SZ;i++) scanf("%f", &a[i]);
● printf("\nmedia=%f\n",avg(a,SZ));
● return;
● }
Strings em C
● Uma string é um vetor de caracteres, 
terminado com o caractere null ( \0 )
● Uma variável string pode ser definida assim: 
#define NOMESZ 30
char nome [NOMESZ]
● Uma constante string é denotada assim:
''Marco Aurelio de Carvalho''
● Um caractere null será colocado no final dela
Operações com Strings 
(string.h)
● strlen(string) – devolve o tamanho de string
● strpos(s1,s2) – posição inicial de s1 em s2
● strcpy(s1,s2) – copia s2 em s1
● strcat(s1,s2) – concatena s2 em s1
● substr(s1,i,j,s2) – s2 = s1[i] + j caracteres
● Ver mais: http://en.wikipedia.org/wiki/String.h
Operações com Strings
● #include <stdio.h>
● #include <string.h>
● #define STSZ 6 
● main(){
● char str[STSZ];
● str[0]='M';
● str[1]='A';
● str[2]='C';
● str[3]='\0';
● printf("String =\"%s\", tamanho=%d\n",str,strlen(str));
● strcpy(str,"Marco");
● printf("String =\"%s\", tamanho=%d\n",str,strlen(str));
● return;
● }
String ="MAC", 
tamanho=3
String ="Marco", 
tamanho=5
Vetores 
multidimensionais
● O tipo de um componente de um vetor pode 
ser outro vetor. Por exemplo:
int vendas[3] [5] cria uma estrutura assim:
 prod0 prod1 prod2 prod3 prod4
filial 0
filial 1
filial 2
 vendas[1][3] o total de vendas do produto 3 na filial 1
Vetores 
multidimensionais
● float temp[90][360][500]
latitude de 0 a 89,
longitude de 0 a 359,
altitude de 0 a 499 (representando múltiplos de 10 metros)
 ...
Temperatura em BSB
temp[15][45][100]
 altitude
 longitude
 latitude
Vetores 
multidimensionais
● Na solução anterior assume-se:
– Temperaturas do hemisfério sul
– Graus inteiros, sem fracionamento
– Altitudes em múltiplos de 10, de 10 metros 
a 5000 metros
Estruturas em C
● Uma estrutura é um grupo de itens 
onde cada membro tem um 
identificador próprio
● Em algumas linguagens denominam-se 
registro e campo
 
Estruturas em C
● Exemplo
 struct {
 char prenome[10];
char inicial_meio;
char sobrenome[20];
 } sname, ename;
● No exemplo acima são criadas duas 
variáveis, chamadas sname e ename
● Para acessar o prenome de sname usa-se:
 sname.prenome
Estruturas em C
● Outra abordagem, usando typedef:
 typedef struct {
char prenome[10];
char inicial_meio;
char sobrenome[20];
 } tiponome;
● A partir disso é criado um novo tipo que pode 
ser usado para declarar variáveis:
 tiponome snome, enome;
 
Estruturas em C
● Vamos ver um programa para armazenar os 
nomes de pessoas e depois localizar aquelas 
que têm uma determinada inicial do meio. 
Essas são as declarações globais:
 
#include <stdio.h>
#include <string.h>
#define TPRENOME 10 
#define TSOBRENOME 20
#define TOTNOME 3
typedef struct {
 char prenome[TPRENOME];
 char inicial_meio;
 char sobrenome[TSOBRENOME];
} tiponome;
Estruturas em C
● O programa carrega os nomes, pede o 
caractere inicial do nome do meio desejado, 
e lista os nomes com aquela inicial.
 
main(){
 char inicial;
 tiponome nomes[TOTNOME];
 lernomes(nomes); 
 printf("\nEntre com a inicial do meio que vocë quer 
pesquisar:");
 scanf("%s",&inicial);
 printf("Resultado:\n");
 achanomes(inicial,nomes);
 printf("\nObrigado por usar o programa\n");
 return 0;
}
Estruturas em C
● O procedimento lernomes carrega cada 
campo do nome:
lernomes (nomes) 
 tiponome nomes[ ];
{ int i;
 for (i=0;i<TOTNOME; i++) {
 printf("Reg %d-Dê o nome, inicial do meio e sobrenome:\n",
 i+1);
 scanf("%s",&nomes[i].prenome);
 scanf("%s",&nomes[i].inicial_meio);
 scanf("%s",&nomes[i].sobrenome);
 }
 printf("\nObrigado por fornecer os nomes");
 return;
}
Estruturas em C
● O procedimento achanomes lista os 
nomes cujas iniciais do meio coincidem 
com a informada:
achanomes (inicial,nomes) 
 tiponome nomes[];
 char inicial;
{ int i;
 for (i=0;i<TOTNOME; i++)
 if (inicial==nomes[i].inicial_meio) 
 printf("%s %c 
%s\n",nomes[i].prenome,nomes[i].inicial_meio,
 nomes[i].sobrenome);
 return;
}
Estruturas em C
● Reg 1-Dê o nome, inicial do meio e sobrenome:Marco
A
Carvalho
Reg 2-Dê o nome, inicial do meio e sobrenome:
Marcelo
L
Ladeira
Reg 3-Dê o nome, inicial do meio e sobrenome:
Célia
A
Ralha
Obrigado por fornecer os nomes
Entre com a inicial do meio que vocë quer pesquisar:A
Resultado:
Marco A Carvalho
Célia A Ralha
Obrigado por usar o programa
Estruturas em C
● Estruturas podem conter qualquer tipo de 
campos, inclusive vetores ou outras 
estruturas
● O tamanho de uma estrutura é a soma dos 
tamanhos dos seus campos
● Uma variável do tipo estrutura pode ter 
layouts diferentes, a partir da construção 
union
● Veja um exemplo completo:
Estruturas em C
● Uma seguradora tem 3 tipos de apólices:
#define VIDA 1
#define AUTO 2
#define CASA 3
● Considere 2 estruturas auxiliares:
struct ender { char street[30]; char cid[10];
 char estado[2]; char cep[8];};
struct data {int dia; int mes; int ano;};
Estruturas em C
● struct apolice{ int numero; int quantidade; float premio;
 char nome[30];
 struct ender endereco;
 int tipo;
 union {
struct {char beneficiario[30];
 struct data aniversario;
 } vida;
 struct {int idauto; char licenca[10];
 char modelo[15]; int ano;
 } auto;
struct {int idcasa; int anoconstr;
 } casa;
 } infoapolice;
} 
Estruturas em C
● Esse tipo de construção permitirá que sejam 
acessados diferentes campos do registro 
dependendo do seu tipo
● O controle disso, no entanto, é 
responsabilidade do programador
● Se tivermos, por exemplo, uma variável
 struct apolice p
poderemos codificar:
Estruturas em C
● if (p.tipo==VIDA)
 printf(''\n%s 
'',p.infoapolice.vida.beneficiario);
else if (p.tipo==AUTO)
 printf(''\n%d '',p.infoapolice.auto.licenca);
else if (p.tipo==CASA)
 printf(''\n%d 
'',p.infoapolice.casa.anoconstr);
Estruturas como 
parâmetros
● A passagem de estruturas em C deve ser feita por 
endereço, de forma semelhante aos vetores.
● Examine o procedimento escrevenome, a seguir, querecebe o ponteiro de uma estrutura como parâmetro.
● Repare a construção ''->'' que permite que o ponteiro 
passado como parâmetro seja usado para indicar os 
campos da estrutura.
● Para chamar o procedimento faremos:
 x = escrevenome(&snome)
sendo snome uma variável do tipo tiponome.
x receberá o tamanho da string que for escrita.
Estruturas como 
parâmetros
● int escrevenome(nome)
struct tiponome *nome; {
 int count, i;
 printf(''\n'');
 count = 0;
 for (i=0; (i<10) && (nome->prenome[i] != '\0'; i++) {
 printf(''%c'', nome->prenome[i]);
 count++;
 }
 printf(''%c'', ' ');
 count++;
 if (nome->inicial_meio!= ' ') {
 printf(''%cs´´, nome->inicial_meio, ''. ''); count+=3;
 }
 for (i=0; (i<20) && (nome->sobrenome[i] != '\0' ); i++) {
 printf(''%c'' , nome->sobrenome[i]); count++;
 }
 return count;
}
Um exemplo: representação de 
números racionais
● Números racionais são aqueles que podem 
ser colocados na forma i/j, onde i e j são 
números inteiros, com j diferente de 0.
● Assim, 1/3, 3/4, 2/3 e 2 são números 
racionais, enquanto sqrt (2) e π, por 
exemplo, não são, pois não podem ser 
representados através de uma razão entre 
inteiros.
● Como não existe um tipo nativo em C para 
racionais, podemos criá-lo: 
Um exemplo: representação de 
números racionais
● typedef struct {
 int numerador;
 int denominador;
} racional;
● Com isso, podemos declarar variáveis:
 racional r, q;
● E a álgebra racional?
Um exemplo: representação de 
números racionais
● Aí podem ocorrer alguns problemas: 
geralmente representa-se o racional por 
aproximação real:
 1/3 == 0.33333333
 2/3 == 0.66666667 (pois é arredondado)
● 1/3 + 1/3==0.333333+0.333333==0.666666
1/3 + 1/3 == 2/3
então: 2/3 != 1/3 + 1/3 ?!!
Um exemplo: representação de 
números racionais
● Outra questão: quando dois números racionais 
são iguais? São iguais, em princípio, quando os 
numeradores são iguais e os denominadores 
também
● Porém, 1 / 2 == 2 / 4 e 2/3 == 12/18
● Como decidir pela igualdade?
● O algorítmo de Euclides pode ser usado para 
reduzir um número racional aos seus termos 
mínimos:
Um exemplo: representação de 
números racionais
● 1 - Seja a o maior entre o numerador e o denominador 
e b o menor deles.
● 2 - Divida a por b encontrando q (quociente) e r (resto)
● 3 - Faça a=b e b=r
● 4 – repita 2 e 3 até que b seja igual a zero
● 5 – Divida o numerador e o denominador originais pelo 
último valor de a.
Um exemplo: representação de 
números racionais
● Por exemplo, considere o racional 16/24
● Passo 1 : a =24, b=16
● Passo 2 : 24 / 16 -> q = 1, r = 8
● Passo 3 : a = 16, b = 8 (a=b, b=r)
● Passo 4 : (repetindo 2 e 3 até que b seja 0:)
 16 /8 -> q = 2, r = 0; a=8 
● Passo 5 : - Numerador = 16/8 == 2
 Denominador = 24/8 == 3
● Portanto o racional reduzido é 2/3
Um exemplo: representação de 
números racionais
● Declarações do programa principal:
#include <stdio.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
typedef struct {
 int numerador;
 int denominador;
} racional;
Um exemplo: representação de 
números racionais
● Veja o procedimento de redução em C:
reduz (inrac, outrac)
racional *inrac, *outrac; {
int a,b, rem;
 if (inrac->numerador>inrac->denominador) 
 {a = inrac->numerador; b = inrac->denominador;}
 else {b = inrac->numerador; a = inrac->denominador;}
 while (b!=0) {
 rem = a % b;
 a = b;
 b=rem;
 }
 outrac->numerador = inrac->numerador / a;
 outrac->denominador = inrac->denominador / a;
}
Um exemplo: representação de 
números racionais
● Veja a verificação de igualdade:
igual (rac1, rac2)
 racional *rac1, *rac2; 
{
 racional r1,r2;
 reduz(rac1, &r1);
 reduz(rac2, &r2);
 if (r1.numerador == r2.numerador &&
 r1.denominador == r2.denominador) return TRUE;
 else return FALSE;
}
Um exemplo: representação de 
números racionais
● O procedimento principal:
main() {
 racional r1,r2;
 r1.denominador=1;
 while (r1.denominador!=0) {
 printf("Entre o numerador e denominador de cada 
racional:\n");
 scanf("%d%d%d%d",&r1.numerador,&r1.denominador,
 &r2.numerador, &r2.denominador);
 if (r1.denominador!=0) 
 if (igual(&r1,&r2)) printf("\nSão iguais\n");
 else printf("\nSão diferentes\n");
 }
 return 0;
}
Um exemplo: representação de 
números racionais
● Veja um procedimento de multiplicação:
 multiply (rac1, rac2, rac3) /* result em rac3 */ 
 racional *rac1, *rac2, *rac3; 
{
 racional r3;
 r3.numerador=rac1->numerador * rac2->numerador;
 r3.denominador=rac1->denominador * rac2->denominador;
 reduz(&r3, rac3);
}
Um exemplo: representação de 
números racionais
● Veja a chamada da multiplicação:
main() {
 racional r1,r2,r3;
 r1.denominador=1;
 while (r1.denominador!=0) {
 printf("Entre o numerador e o denominador:\n");
 scanf("%d%d%d%d",&r1.numerador,&r1.denominador,
 &r2.numerador, &r2.denominador);
 if (r1.denominador !=0) {
 multiply (&r1,&r2,&r3);
 printf("Resultado:%d/%d\n",r3.numerador,r3.denominador);
 }
 }
 return 0;
}
Algumas palavras sobre alocação de 
memória
● As variáveis declaradas em uma função são 
automáticas e locais
● As variáveis declaradas no início do programa 
fora das funções são globais e estáticas, 
ficando disponíveis e qualquer lugar
● Variáveis locais que precisem reter o valor 
entre uma chamada e outra são ditas static
 por exemplo static int i
● Veja o manual (ou livro) de seu compilador 
para maiores detalhes.
Exercício
● Suponha que o seu compilador de C não seja 
capaz de realizar operações com números reais 
(float) e que você deva armazená-los em uma 
estrutura do tipo:
ou algo semelhante. (Será essa a melhor 
estrutura? Você pode propor outra, se achar 
conveniente).
typedef struct {
 int inteiro;
 int fracao;
} real;
Exercício
● Escreva os procedimentos para fazer 
soma e multiplicação de reais assim 
definidos:
soma (r1, r2, result)
real *r1,*r2,*result;
mult(r1, r2, result)
real *r1,*r2,*result;
Exercício
● Lembre-se de usar somente aritmética inteira 
em sua solução
● Se você precisar de exponenciação use 
pow(i,j) ou escreva uma função tal como:
int power (base,exp) 
 int base,exp; {
 int i,j;
 j=base;
 for (i=0;i<exp;i++) j*=base;
 return j;
}
Exercício
● Podem fazer em duplas
● Façam um programa principal para ler os 
quatro números (int1,frac1,int2,frac2) e a 
operação (* ou +), imprimindo o resultado e 
voltando para realizar outra operação, até que 
int1 seja zero.
● Enviar o exercício pelo Moodle até segunda 
feira próxima