1 Processamento de Registos Listas e Estruturas DI/FCT/UNL 1º Semestre 2004/2005

1

Processamento de Registos Listas e Estruturas

DI/FCT/UNL

1º Semestre 2004/2005

2

Processamento de Registos

• Podemos agora considerar outro tipo de processamento de registos, que não envolve necessariamente a escrita de novos ficheiros, correspondente a:

– Cálculo de totais e médias (de vencimentos, por exemplo)

– Determinação de máximos e mínimos (de vencimentos, ou antiguidades)

• Vamos ilustrar estes problemas com programas para determinação dos vencimentos totais e médios dos empregados da empresa, bem como da determinação do empregado mais antigo. Em ambos os casos apenas apresentamos a versão para formato variável.

• De notar a instrução printf, que permite escrever no terminal mensagens formatadas (com os formatos usados em ficheiros).

3

Processamento de Registos• O tratamento de vencimentos utiliza um contador (variável i) de

registos lidos e uma variável (total) para determinação do total dos vencimentos (sendo a média igual ao quociente total/i).

rem_sp("empresa_in_var.txt", "empresa_aux_var.txt"); [f_aux, msg] = fopen("empresa_aux_var.txt", "r"); [cod,nome, venc, data, count] = fscanf(f_aux,"%i%s%f%s","C"); i = 0; total = 0; while !feof(f_aux) i = i+1; total = total +venc; [cod,nome, venc, data, count] = fscanf(f_aux,"%i%s%f%s","C"); endwhile; printf("o total dos vencimentos é de %7.2f \n", total); printf("a média dos vencimentos é de %7.2f \n",total/i); fclose(f_aux); fclose(f_out);

4

Processamento de Registos• O tratamento de datas, implica reconhecer quando uma data é

anterior a outra, o que é feito com a função anterior que compara duas datas, sendo armazenada a data menor.

rem_sp("empresa_in_var.txt", "empresa_aux_var.txt"); [f_aux, msg] = fopen("empresa_aux_var.txt", "r"); [cod,nome, venc, data, count] = fscanf(f_aux,"%i%s%f%s","C"); data_menor =“01/01/2100”; while !feof(f_aux) if anterior(data,data_menor) data_menor = data; endif; [cod,nome, venc, data, count] = fscanf(f_aux,"%i%s%f%s","C"); endwhile; printf("a entrada mais antiga foi em %s\n",data_menor); fclose(f_aux); fclose(f_out);

5

Processamento de Registos• A comparação de datas é feita através da comparação dos seus

anos, meses e dias, tendo o cuidado de converter as cadeias de caracteres em números.

function d = anterior(data1,data2);% data no formato dd/mm/aaaa ano1 = str2num(substr(data1,7,4)); ano2 = str2num(substr(data2,7,4)); if ano1<ano2 d = 1; elseif ano1 > ano2 d = 0; else mes1 = str2num(substr(data1,4,2)); mes2 = str2num(substr(data2,4,2)); if mes1<mes2 d = 1; elseif mes1 > mes2 d = 0; else dia1 = str2num(substr(data1,1,2)); dia2 = str2num(substr(data2,1,2)); if dia1 < dia2 d = 1; else d = 0; endif; endif; endif; endfunction

6


• Neste último caso, a informação transmitida não é muito interessante. Provavelmente estaremos mais interessados em saber quem é o empregado mais antigo, ou seja, qual o nome do empregado com data de entrada mais antiga.

• Este problema pode ser resolvido com uma pequena adaptação do código, guardando não só a data mais antiga como o nomewhile !feof(f_aux) if anterior(data,m_data) data_menor = data; antigo = nome endif; [cod,nome, venc, data, count] = ...endwhile;printf("o empregado mais antigo é %s \n", antigo);printf("com data de entrada %s \n", data_menor);

7


• Todos estes programas obrigam a ler um ficheiro, cada vez que se pretende responder a uma questão.

• No entanto, a leitura de ficheiros, mesmo em “discos rápidos” é tipicamente milhares de vezes mais lenta que a leitura a partir de dados em memória.

• Haverá pois vantagem em copiar um ficheiro de registos para memória e passar a responder às questões a partir de aí.

• Veremos como responder a esta questão em geral e, no caso do Octave, como tal poderá ser feitos com estruturas e listas.

8

Processamento de Informação Alfanumérica• Podemos considerar que a informação dos ficheiros de

registos corresponde a uma tabela. Esta tabela é constituída por uma sequência de “registos”, um em cada linha.

• Se toda a informação fosse numérica, isto é se cada registo tivesse n “campos”, ela poderia ser guardada numa matriz com m linhas, uma linha para cada registo de n posições.

• Em Octave, existe um problema: uma posição de uma matriz não pode ser ocupada por uma cadeia de caracteres!cod nome vencimento data

610 Paul o Fer nandes Lopes 2341. 36 15/ 04/ 1996825 Pedr o Vi ei r a 989. 24 25/ 06/ 1999316 Mar t a Cost a Mar t i ns 1389. 17 05/ 01/ 199234 Rui Vasco Per ei r a 5310. 32 15/ 04/ 1996723 J or ge Bar at a 767. 26 03/ 09/ 2002

9

Processamento de Informação Alfanumérica• Desta forma a informação de uma tabela alfanumérica não

pode ser guardada como uma matriz. Vamos ver como se podem ultrapassar estes problemas em Octave, fazendo-o em duas “fases”:

– Como representar um registo heterogéneo, com vários campos de diferentes tipos, alguns alfanuméricos.

– Como armazenar e aceder a vários destes registos heterogéneos.

cod nome vencimento data

610 Paul o Fer nandes Lopes 2341. 36 15/ 04/ 1996825 Pedr o Vi ei r a 989. 24 25/ 06/ 1999316 Mar t a Cost a Mar t i ns 1389. 17 05/ 01/ 199234 Rui Vasco Per ei r a 5310. 32 15/ 04/ 1996723 J or ge Bar at a 767. 26 03/ 09/ 2002

10

Estruturas

• Vectores e Matrizes são muito úteis quando os dados são todos do mesmo tipo (no Octave, de qualquer tipo numérico).

• No entanto, em muitos casos, a informação que se pretende agrupar com um só identificador não é do mesmo tipo.

• Por exemplo, um empregado duma empresa pode ter associado a seguinte informação

– Um código (um número?)– Um nome (uma cadeia de caracteres)– Um vencimento (um decimal)– Uma data de entrada (uma cadeia, ou 3 campos numéricos,

para o dia, mês e ano)

cod nome venc data610 Paulo Fernandes Lopes 2341.36 15/04/1996

11

Estruturas

• As várias linguagens de programação permitem o agrupamento destes dados heterogéneos, com um mesmo identificador de uma forma variada (records no Pascal, Struct em C, ...)

• O Octave adopta uma designação semelhante à do C, denominando estes agrupamentos como estruturas.

• Consideremos pois o caso do empregado abaixo, em que gostaríamos de agregar toda a informação numa única variável, do tipo estrutura, que denotaremos como emp_610.

cod nome venc data610 Paulo Fernandes Lopes 2341.36 15/04/1996emp_610 =

12

Estruturas• As estruturas são compostas por vários campos, cada um

com um nome. Na estrutura para representação da informação de empregados, consideraremos os campos abaixo, que guardam a informação “esperada”

– cod: o código do empregado

– nome: o nome do empregado

– venc: o vencimento do empregado

– data: a data de entrada do empregado na empresa.


13

Estruturas• Uma vez definidos os nomes dos campos da estrutura,

podemos atribuir-lhe os valores pretendidos.

• O acesso a um campo da estrutura é feito fazendo suceder ao nome da estrutura o nome do campo pretendido, separado por um ponto (‘.’).

• Por exemplo, a atribuição dos 4 valores dos campos pode ser feita pelas seguintes atribuições:

emp_610.cod = 610;emp_610.nome = “Paulo Fernandes Lopes”;emp_610.venc = 2341.36;emp_610.data=“15/04/1996”;


14

Estruturas• De notar que os campos de uma estrutura não são ordenados,

e podem ser preenchidos por qualquer ordem.

• Assim a estrutura que temos referido

pode ser inicializada quer com a sequência de instruções empregado.data=“15/04/1996”;empregado.cod = 610;empregado.nome = “Paulo Fernandes Lopes”;empregado.venc = 2341.36;

ou com outra sequência empregado.venc = 2341.36;

empregado.cod = 610;empregado.data=“15/04/1996”;empregado.nome = “Paulo Fernandes Lopes”;


15

Estruturas• Uma vez agrupados os vários items de informação numa só

variável do tipo estrutura, podemos referir alguns campos depois de verificar outros.

• Por exemplo, dados vários empregados com o tipo referido, indicar qual o nome dos que ganham mais de 1000 euros.

• Na sintaxe do Octave, tal poderia ser feito através da instrução condicional

if emp_610.venc > 1000 then disp(emp_610.nome)

endif

• No entanto este tipo de processamento só é verdadeiramente útil se tivermos a possibilidade de aceder a todos os empregados de uma forma genérica.

16

Estruturas• Por exemplo, se tivéssemos uma tabela com várias linhas,

com códigos na primeira coluna e vencimentos na 2ª coluna, poderíamos apresentar os códigos dos empregados com vencimento superior a 1000 euros através da seguinte instrução iterativa:for i = 1:n

if tabela(i,2) > 1000 then disp(tabela(i,1))

endif endfor;

• Por analogia, o que é necessário é poder aceder a uma sequência de (1 a n) estruturas do tipo da do empregado.

• Em Octave, essa sequência pode ser implementada através de listas.

1 2

1 610 2341. 362 825 989. 243 316 1389. 174 34 5310. 325 723 767. 26... . . . . . .

17

Listas• Uma lista é uma sequência de dados do mesmo tipo, simples

ou complexo, para as quais estão definidas as operações de:

• Criação: list(elem_1, elem_2, ..., elem_k)

– Cria uma lista, com os elementos de 1 a k (ou uma lista vazia se k = 0)

• Acrescento: append(nome_lista,elem_1, ...,elem_k)

– Acrescenta os os elementos de 1 a k à lista com o nome indicado no 1º argumento

• Acesso: nth(nome_lista, k)

– Acede ao k-ésimo elemento da lista. De notar que esse elemento pode ser uma estrutura arbitrariamente complexa.

18

Listas• Para ilustrar estes conceitos, vamos ler um ficheiro com

informação sobre empregados e criar uma lista com essa informação.

• A instrução principal consiste em criar uma estrutura, emp, e atribuir-lhe os valores lidos do ficheiro (a formatação dos campos é feita como anteriormente).

[emp.cod, emp.nome, emp.venc, emp.data, count] = fscanf(f_aux,"%i%s%f%s","C");

• Para além destas instruções, são necessárias instruções para inicializar a lista e para a ir acrescentando com os empregados lidos. O número de empregados também é computado.

19

Listas• Eis o programa completo, que cria uma lista, tab_empregados, com a informação sobre os empregados inicialmente no ficheiro “empresa_aux_var.txt”.

[f_aux, msg] = fopen("empresa_aux_var.txt", "r"); tab_empregados = list(); n = 0; [emp.cod,emp.nome,emp.venc,emp.data, count] = fscanf(f_aux,"%i%s%f%s","C"); while !feof(f_aux) n = n+1; tab_empregados = append(tab_empregados, emp); [emp.cod,emp.nome,emp.venc,emp.data, count] = fscanf(f_aux,"%i%s%f%s","C"); endwhile; fclose(f_aux);

20

Listas

• A partir deste momento, todo o processamento da informação sobre os empregados pode ser feito sem leitura do ficheiro, mas apenas por acesso à lista “tab_empregados”.

• Se já tiver sido lida a informação dos empregados para a lista “tab_empregados”, com n elementos, ela pode ser acedida directamente, sem necessidade de nova leitura do ficheiro.

total = 0; for i = 1:n total = total + nth(tab_empregados,i).venc; endfor; printf("o total de vencimentos é %7.2f \n“, total); printf(“ e a sua média é %7.2f \n", total/n);

21

Listas

• Igualmente se podem escrever o nome e vencimento dos empregados que ganham mais de 1000 euros, sem necessidade de leitura do ficheiro, mas apenas usando a mesma lista “tab_empregados”, com n elementos.

printf("Lista de empregados com mais de 1000 €: \n"); for i = 1:n emp = nth(tab_empregados,i); if emp.venc > 1000 printf("\t%s\t%7.2f\t\n",emp.nome,emp.venc); endif; endfor;

22

Estruturas e Listas em Funções• Estruturas e listas podem ser retornadas como resultado de uma

função. Por exemplo, a leitura de um ficheiro com o formato considerado pode ser feita pela função (que também retorna o número de elementos):

function [t, n] = ler_tabela(ficheiro); [f_aux, msg] = fopen(ficheiro, "r"); tab_empregados = list(); n = 0; [emp.cod,emp.nome,emp.venc,emp.data, count] = fscanf(f_aux,"%i%s%f%s","C"); while !feof(f_aux) n = n+1; tab_empregados = append(tab_empregados, emp); [emp.cod,emp.nome,emp.venc,emp.data, count] = fscanf(f_aux,"%i%s%f%s","C"); endwhile; fclose(f_aux); t = tab_empregados;endfunction;

23

Ordenação de Registos• Um outro problema igualmente importante é o da apresentação dos

registos de acordo com uma determinada ordem. Por exemplo:– Apresentar uma listagem dos empregados por ordem alfabética;– Apresentar uma listagem dos empregados ordenados por antiguidade;

• Complementarmente, podem-se adicionar restrições: – Apresentar uma listagem, ordenada por ordem alfabética, dos empregados

que tenham um vencimento superior a 1000 €;– Apresentar uma listagem, ordenada por antiguidade, dos empregados que

tenham um vencimento superior a 1000 €;

• Em qualquer dos casos é importante saber ordenar os registos de acordo com um determinado critério.

• Vamos então descrever dois algoritmos simples de ordenação (insert sort e bubble sort) e depois mostrar como podem ser aplicados na ordenação de registos (guardados em listas).

24

Algoritmos de Ordenação: insert sort• Suponhamos que queríamos ordenar o seguinte vector:

v0 = [12, 2, 9, 15, 10]

• Talvez a maneira mais intuitiva de o fazer seja através do algoritmo insert sort:

– Começa-se por criar um vector v1 apenas com o primeiro elemento de v0:

• v1 = [12]

– Acrescentam-se o restantes elementos, um a um, de modo a manter v1 sempre ordenado:

• v1 = [2, 12]

• v1 = [2, 9, 12]

• v1 = [2, 9, 12, 15]

• v1 = [2, 9, 10, 12, 15]

• O problema fundamental deste algoritmo é como é que se faz para inserir um elemento numa lista ordenada.

25

Algoritmos de Ordenação: insert sort• Para inserir um elemento numa lista ordenada podemos percorrer a lista do fim

para o principio até se descobrir a posição que o elemento deve ocupar na ordenação.

• Ao percorrer a lista podemos ir chegando uma posição à direita todos os elementos maiores do que o novo elemento de modo a arranjar espaço para ele:

function L = insert(L0,x)

L=L0; n=length(L);

for i=n:-1:1

if (L(i)<x) L(i+1)=x; return;

else

L(i+1)=L(i);

if (i==1) L(i)=x; return; endif

endif

endfor

endfunction

26

Algoritmos de Ordenação: insert sort• A seguinte função insert_sort começa por criar um vector inicial apenas

com o primeiro elemento da lista para ordenar e vai acrescentando todos os outros elementos, um a um, recorrendo à função insert:

function L = insert_sort(L0)

n=length(L0);

L=[L0(1)];

for i=2:n

L=insert(L,L0(i));

endfor

endfunction

27

Algoritmos de Ordenação: bubble sort• Um outro algoritmo de ordenação, um pouco mais sofisticado, é o

bubble sort. – Suponhamos que queremos ordenar o vector:

• v0 = [12, 2, 9, 15, 10]

– Começa-se por percorrer o vector inicial (até ao penúltimo elemento) e trocar dois elementos sempre estiverem na ordem errada:

• v1 = [2, 12, 9, 15, 10]

[2, 9, 12, 15, 10]

[2, 9, 12, 15, 10]

[2, 9, 12, 10, 15]

– Agora, que garantidamente o último elemento do vector é o maior, repete-se o processo (para os elementos ainda não garantidamente ordenados) :

• v1 = [2, 9, 12, 10, 15]

[2, 9, 12, 10, 15]

[2, 9, 10, 12, 15]

• v1 = [2, 9, 10, 12, 15]

[2, 9, 10, 12, 15]

• v1 = [2, 9, 10, 12, 15]

28

Algoritmos de Ordenação: bubble sort• O código Octave do algoritmo de ordenação bubble sort será então:

function L = bubble_sort(L0) n=length(L0);

L=L0;

for k=n-1:-1:1

for i=1:k

if L(i+1)<L(i)

temp=L(i);

L(i)=L(i+1);

L(i+1)=temp;

endif;

endfor;

endfor;

endfunction

29

Algoritmos de Ordenação e Listas• Os algoritmos de ordenação como o bubble sort e o insert sort

podem ser utilizados para ordenar uma lista de registos se considerarmos vectores de índices.

• Por exemplo:– o vector [1, 2, 3, 4, 5] pode representar os cinco primeiros elementos de uma

lista na sequência: 1º, 2º, 3º, 4º e 5º.– o vector [5, 4, 3, 2, 1] pode representar os mesmos cinco elementos mas por

ordem inversa.

• Se t é uma lista de registos, nth(t,i) é o elemento de índice i• No exemplo da lista de empregados, o código, nome, vencimento e

data do empregado de índice i são respectivamente:– nth(t,i).cod– nth(t,i).nome– nth(t,i).venc– nth(t,i).data

30

Algoritmos de Ordenação e Listas• Deste modo, a função listagem_nome_venc apresenta o nome e

vencimento dos empregados de acordo com a ordenação dos índices representada no vector L:

function listagem_nome_venc(t,L)

n=length(L);

for i=1:n

printf("Nome: %-25s Vencimento: %7.2f \n“

,nth(t,L(i)).nome, nth(t,L(i)).venc);

endfor;

endfunction

• Assim, para obtermos uma listagem ordenada basta ordenar os índices e chamar a função listagem_nome_venc.

31

Algoritmos de Ordenação e Listas• Para ordenar os índices pode-se usar um algoritmo de ordenação

tendo o cuidado de “redefinir” a comparação entre dois elementos de acordo com o critério de ordenação que se pretende.

• Por exemplo, a função bubble_sort_list_cod usa o bubble sort para ordenar os índices existentes no vector L0 por ordem crescente do código do empregado:

function L = bubble_sort_list_cod(t,L0) L=L0; n=length(L0); for k=n-1:-1:1 for i=1:k if nth(t,L(i+1)).cod < nth(t,L(i)).cod temp=L(i); L(i)=L(i+1); L(i+1)=temp; endif; endfor; endfor; endfunction

32



• A função bubble_sort_list_venc é idêntica à anterior mas ordena os índices existentes no vector L0 por ordem crescente do vencimento do empregado:

function L = bubble_sort_list_venc(t,L0) L=L0; n=length(L0); for k=n-1:-1:1 for i=1:k if nth(t,L(i+1)).venc < nth(t,L(i)).venc temp=L(i); L(i)=L(i+1); L(i+1)=temp; endif; endfor; endfor; endfunction

33



• A função bubble_sort_list_data ordena os índices existentes no vector L0 por ordem crescente de antiguidade do empregado, e usa a função anterior para comparar duas datas:

function L = bubble_sort_list_data(t,L0) L=L0; n=length(L0); for k=n-1:-1:1 for i=1:k if anterior(nth(t,L(i+1)).data,nth(t,L(i)).data)==1 temp=L(i); L(i)=L(i+1); L(i+1)=temp; endif; endfor; endfor;endfunction

34



• A função bubble_sort_list_nome ordena os índices existentes no vector L0 por ordem alfabética dos nomes dos empregados, e usa a função my_str_norm_before para comparar dois nomes:

function L = bubble_sort_list_nome(t,L0) L=L0; n=length(L0); for k=n-1:-1:1 for i=1:kif my_str_norm_before (nth(t,L(i+1)).nome,nth(t,L(i)).nome)==1 temp=L(i); L(i)=L(i+1); L(i+1)=temp; endif; endfor; endfor;endfunction

35

Algoritmos de Ordenação e Listas• Se além da ordenação estivermos também interessados em seleccionar

apenas alguns registos, podemos previamente construir um vector apenas com os índices dos registos seleccionados.

• Por exemplo, a função select_venc cria um vector apenas com os índices de L0 cujos empregados tenham um vencimento superior a 1000 €:

function L = select_venc(t,L0) L=[]; j=0; n=length(L0); for i = 1:n if nth(t,L0(i)).venc > 1000 j=j+1; L(j)=L0(i); endif; endfor;endfunction

• Assim para obter apenas estes índices ordenados pelo nome do empregado bastaria:L=select_venc(t,L0); L=bubble_sort_list_nome(t,L)

36

Algoritmos de Ordenação e Listas• Podemos agora dar resposta a cada uma das perguntas anteriores.• Primeiro lê-se o ficheiro de texto para uma tabela:

• Para apresentar uma listagem dos empregados por ordem alfabética de nomes ou por antiguidade, teríamos que considerar todos os índices, ordená-los de acordo com o critério e apresentar os campos que queremos visualizar dos respectivos registos:

L=[1:n]; L1=bubble_sort_list_nome(t,L);listagem_nome_venc(t,L1);L2=bubble_sort_list_data(t,L);listagem_nome_venc(t,L2);

[t,n] = ler_tabela("empresa_aux_var.txt");

• Se além disto estivermos apenas interessados nos empregados com um salário superior a 1000 €, temos que previamente seleccionar apenas os índices dos registos que satisfazem o critério:L=[1:n]; L=select_venc(t,L); L1=bubble_sort_list_nome(t,L);listagem_nome_venc(t,L1);L2=bubble_sort_list_data(t,L);listagem_nome_venc(t,L2);

Documents

1 Processamento de Registos Listas e Estruturas DI/FCT/UNL 1º Semestre 2004/2005