UNIVERSIDADE DO ALGARVE
FACULDADE DE CIÊNCIAS E TECNOLOGIA
Departamento de Engenharia Electrónica e Informática
Relatório da disciplina:
Estruturas de dados
2º semestre 2004/2005
Helder Aniceto Amadeu de Sousa Daniel
Faro
Julho de 2005
Estruturas de Dados (2004-2005)
1
Estruturas de Dados (2004-2005)
2
Índice
1
2
3
4
5
Introdução ............................................................................................................................... 1
Objectivos pedagógicos ........................................................................................................... 1
Conteúdos programáticos ......................................................................................................... 1
Programa ................................................................................................................................. 1
Bibliografia.............................................................................................................................. 2
5.1
Referências principais: ..................................................................................................... 2
5.2
Bibliografia complementar sobre C: ................................................................................. 3
5.3
Resumos das aulas ........................................................................................................... 3
6
Procedimento de avaliação ....................................................................................................... 3
6.1
Avaliação contínua ........................................................................................................... 3
6.2
Exame época normal e recurso ......................................................................................... 3
6.3
Aprovação na disciplina ................................................................................................... 3
7
Calendarização ........................................................................................................................ 3
7.1
Teórica ............................................................................................................................. 3
7.2
Prática .............................................................................................................................. 5
8
Assiduidade ............................................................................................................................. 6
8.1
Teóricas ........................................................................................................................... 6
8.2
Práticas ............................................................................................................................ 7
9
Avaliação................................................................................................................................. 7
Enunciados dos momentos de avaliação......................................................................................... 11
Estruturas de Dados (2004-2005)
i
Estruturas de Dados (2004-2005)
ii
1 Introdução
Neste relatório encontra-se definido o conteúdo, objectivos, programa, bibliografia, métodos de
avaliação da disciplina Estruturas de Dados, leccionada no 2º semestre do ano lectivo de 2004/2005,
às licenciaturas em Engenharia de Sistemas e Informática, Ensino de informática e Informática, da
Faculdade de Ciências e Tecnologia da Universidade do Algarve.
O programa abaixo apresentado, o qual foi seguido este ano, é idêntico ao desenvolvido pelo
Professor Doutor José Valente de Oliveira no ano lectivo 2003/2004, podendo ser consultado todo o
material lectivo em: http://w3.ualg.pt/~jvo/ed0304.
A matéria teórica e as fichas práticas referidas no ponto 7, foram idênticas às leccionadas no ano
lectivo 2003/2004, da autoria do Professor Doutor José Valente de Oliveira, salvo menção explícita
nesse mesmo ponto. O material lectivo referente ao ano 2004/2005 pode ser consultado em:
http://w3.ualg.pt/~hdaniel/ed.
No plano curricular das licenciaturas acima referidas, esta disciplina insere-se no 2º semestre do 1º
ano e correspondem-lhe 3 créditos.
A disciplina foi ainda leccionada ao curso de Engenharia de Sistema e Computação.
2 Objectivos pedagógicos
Dotar os alunos com a capacidade de desenvolver programas multi-modulares em ANSI C,
recorrendo a estruturas de dados elementares e algoritmos básicos de ordenação e procura.
3 Conteúdos programáticos
Tipos de dados e tipos de dados abstractos. Listas, pilhas, filas de espera e árvores binárias.
Algoritmos de ordenação elementares e algoritmo quicksort.
4 Programa
Abaixo apresenta-se o programa previsto para o semestre, conforme apresentado nas aulas teóricas:
I.
Conceitos fundamentais
a) Tipos básicos
b) Arrays, estruturas e uniões
c) Ponteiros
i.
Ponteiros para constantes
ii.
Ponteiros constantes
iii.
Ponteiros constantes para constantes
iv.
Ponteiros para estruturas
v.
Ponteiros para funções
vi.
Arrays de ponteiros e os argumentos da função main
II.
Reserva dinâmica de memória
a) Funções para reserva e libertação dinâmica de memória
b) Reserva dinâmica de memória para matrizes e tensores
III.
Primeiras noções de Projecto, de Projecto por Contrato e Aspectos sobre a
documentação de código.
IV.
Listas ligadas
a) Cadeias
b) Listas circulares simplesmente ligadas
Estruturas de Dados (2004-2005)
1
c) Listas duplamente ligadas
5
V.
Tipos de dados abstractos
a) Motivação e definição
b) A pilha (stack) como tipo de dados abstracto
i.
Programa cliente de Stack: calculadora de expressões aritméticas em
notação sufixa
ii.
Implementação do ADT Stack usando uma lista ligada
iii.
Implementação do ADT stack usando arrays
iv.
Programa cliente de stack para conversão de expressões algébricas de
notação infixa para notação sufixa.
c) O tipo de dados abstracto fila (FIFO queue): Interface e implementações
d) Noção de fila generalizada
e) Noção de deque (double-ended queue)
f) Implementação em C de tipos de dados abstractos com múltiplas instâncias: O
ADT Point e o ADT Queue
g) O tipo de dados abstracto polinómio
i.
interface
ii.
Implementação baseada em arrays e em listas ligadas
h) O ADT Matriz Esparsa
i.
Funções seleccionadas de interface
ii.
Implementação baseada em arrays e em listas ligadas
VI.
Árvores
a) Noções de recursividade
b) Generalidades, terminologia e representação de árvores ordenadas
c) Árvores binárias
i.
Funções de atravessamento
ii.
Propriedades básicas e funções elementares recursivas
VII.
Algoritmos elementares de ordenação
a) Terminologia e definição do problema de ordenação
b) Algoritmos de ordenação por selecção
c) Algoritmos de ordenação por inserção e troca (bubble sort)
d) Ordenação por selecção em listas ligadas
VIII.
O algoritmo Quicksort
a) Versão probabilística e sua implementação em C
b) Versão clássica e sua implementação em C
c) Desempenho
d) Melhoramentos do quicksort: subcolecções pequenas e partição por mediana
e) A função qsort do ANSI C.
IX.
Filas privadas e Acervos: Noções elementares
Bibliografia
5.1 Referências principais:
Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed (1993). “Fundamentals of Data Structures in
C”, Computer Science Press, New York
R. Sedgewick (1999). “Algorithms in C (3rd Searching,
Structures, Sorting and Searching”, Addison-Wesley.
Estruturas de Dados (2004-2005)
edition) Parts 1-4: Fundamentals, Data
2
5.2 Bibliografia complementar sobre C:
Brian W. Kernigham, M. Dennis Ritchie (1991). “The C Programming Language, (2nd edition)”.
Prentice-Hall.
P. Guerreiro (2001). “Elementos de Programação com C”, FCA.
5.3 Resumos das aulas
Resumos das aulas, assim como outros elementos relativos à disciplina, estão disponíveis on-line
em http://w3.ualg.pt/~hdaniel/ed/
6
Procedimento de avaliação
6.1 Avaliação contínua
Teste:
Trabalho prático:
60 % da nota final
40 % da nota final
Prova complementar para alunos com notas no intervalo [8.0; 9.5[.
6.2 Exame época normal e recurso
Os exames consistem de prova escrita, sem consulta, podendo incluir questões sobre conhecimentos
necessários à realização do trabalho prático.
A nota do exame constituí a nota final da disciplina
Todos os alunos regularmente inscritos são admitidos a exame.
6.3 Aprovação na disciplina
Serão aprovados na disciplina alunos com nota igual ou superior a 10 valores, na avaliação contínua
ou nos exames.
7 Calendarização
A disciplina é composta por componente teórica semanal de 2 horas e componente prática de 3
horas. A componente teórica divide-se em dois períodos não consecutivos de 1 hora.
7.1 Teórica
A exposição da matéria segundo o programa acima foi calendarizada para 28 aulas teóricas, com
duração aproximada de 50 minutos:
1. Apresentação
2. Estruturas de Dados Elementares: Tipos básicos, estruturas e uniões
3. Arrays e ponteiros I
4. Arrays e ponteiros II: Relacionamento entre ponteiros e arrays
5. Arrays de ponteiros; Args. função main; Reserva dinâmica de memória I
6. Reserva dinâmica de memória para matrizes. Introdução às listas ligadas
7. Noções de Projecto
8. Funções atómicas sobre cadeias. Aspectos de documentação de código
9. Mais funções sobre cadeias. Listas circulares
10. Listas duplamente ligadas
11. Tipos de Dados Abstractos. Interface para um ADT Stack
12. Cliente de ADT Stack: calculadora para expressões em notação sufixa
13. Primeiras implementações de um ADT Stack
14. Conversor de expressões algébricas
Estruturas de Dados (2004-2005)
3
15. O ADT FIFO queue
16. Filas aleatórias, generalizadas e deques. ADTs com múltiplas instâncias
16bRevisitando ADTs
17. O ADT polinómio: Interface e implementação baseada em arrays
18. O ADT polinómio: Implementação baseada em listas ligadas
19. O ADT matriz esparsa
20. Árvores e recursividade
21. Representação de árvores ordenadas
22. Funções e propriedades fundamentais das árvores binárias
23. Algoritmos elementares de ordenação I
24. Algoritmos elementares de ordenação II
25. Quicksort I
26. Quicksort II
27. Filas com prioridades e acervos
Relativamente à calendarização do ano lectivo de 2003-2004 foi introduzida a aula 16b, sobre
ADTs genéricos, e adicionada documentação sobre árvores binárias de busca à aula 22. Na aula 19
não foi tão aprofundada a implementação do ADT matriz esparsa baseado em listas ligadas, tendo
sido apresentadas conceitos sobre implementações alternativas deste ADT.
EDa 2004 / 2005
Teóricas
T2
Semana
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Inicio
14-Fev-05
21-Fev-05
28-Fev-05
07-Mar-05
14-Mar-05
21-Mar-05
28-Mar-05
04-Abr-05
11-Abr-05
18-Abr-05
25-Abr-05
02-Mai-05
09-Mai-05
16-Mai-05
23-Mai-05
30-Mai-05
06-Jun-05
Fim
18-Fev-05
25-Fev-05
04-Mar-05
11-Mar-05
18-Mar-05
25-Mar-05
01-Abr-05
08-Abr-05
15-Abr-05
22-Abr-05
29-Abr-05
06-Mai-05
13-Mai-05
20-Mai-05
27-Mai-05
03-Jun-05
10-Jun-05
TER
1
2/3
5
7
9
11
13
15
16b
18
20
21/22
23
24
Teste
T1
QUI
TER
2
1
4
2/3
6
5
8
7
10
9
Páscoa
12
11
14
13
16
15
17
16b
19
18
21
20
Semana académica
22
21
FER
22
25
24
Teste
26
SEX
2
4
6
8
10
12
14
16
17
19
FLT
21/22
23
25
FER
Os alunos dos cursos aos quais a cadeira é leccionada foram divididos em dois turnos, T1 e T2,
sendo distribuído o serviço docente do seguinte modo:
T1
T2
Helder Daniel
Helder Daniel
(professor auxiliar DEEI)
As aulas foram apresentadas conforme mostra a calendarização acima.
Como as aulas teóricas 21 e 22 foram leccionadas em 3 períodos de 1 hora, mais uma hora do que o
previsto, não houve tempo para apresentar a aula teórica 27.
Estruturas de Dados (2004-2005)
4
A aula teórica prevista para o turno T1 no dia 6 de Maio de 2005, não foi leccionada por ausência
do docente. Foi marcada uma aula de compensação para o dia 9 de Junho de 2005, de modo a
equilibrar o número de aulas de ambos os turnos teóricos.
As aulas teóricas previstas para os turnos T1 e T2 no dia 7 de Junho de 2005, não foram leccionadas
por coincidir com o dia do teste.
7.2 Prática
Nas aulas práticas, além do tempo dedicado aos trabalhos práticos, foram resolvidos exercícios
sobre os temas apresentados nas aulas teóricas, distribuídos por 11 fichas:
1. Exercícios de aquecimento
2. Estruturas, uniões, arrays e apontadores
3. Reserva dinâmica de memória
4. Listas simplesmente ligadas e diagramas de estrutura
5. Listas circulares
6. O Stack como tipo de dados abstracto
7. Filas de espera, deques e filas aleatórias
8. ADTs com múltiplas instâncias
9. Matrizes esparsas
10. Árvores
11. Algoritmos elementares de ordenação
EDa 2004 / 2005
Semana
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Inicio
14-Fev-05
21-Fev-05
28-Fev-05
07-Mar-05
14-Mar-05
21-Mar-05
28-Mar-05
04-Abr-05
11-Abr-05
18-Abr-05
25-Abr-05
02-Mai-05
09-Mai-05
16-Mai-05
23-Mai-05
30-Mai-05
06-Jun-05
Práticas
S
Fim
P4
18-Fev-05
25-Fev-05
1
04-Mar-05
2
11-Mar-05
3
18-Mar-05 4a / TRB
25-Mar-05
01-Abr-05 Páscoa
08-Abr-05
4b
15-Abr-05
5
22-Abr-05
6
FER
29-Abr-05
06-Mai-05
7
13-Mai-05
20-Mai-05
8
27-Mai-05
9
03-Jun-05
10
10-Jun-05
11
T
Q
S
S
P3
Q
P5
P2
P1
Não se efectuam aulas práticas
1
1
1
1
2
2
2
2
3
3
3
3
4a / TRB
4a / TRB 4a / TRB 4a / TRB
Páscoa
4b
4b
4b
4b
5
5
5
5
6
6
6
6
CC
7
7
7
7
8
8
8
8
9
9
9
Semana académica
9
10
10
10
FER
10
11
11
11
11
TRB
TRB
Teste
FER
TRB
Os alunos dos cursos aos quais a cadeira é leccionada foram divididos em cinco turnos, P1 – P5,
sendo distribuído o serviço docente do seguinte modo:
P1
P2
P3
P4
P5
Ana Paula Costa
Helder Daniel
Carlos Fonseca
Ana Paula Costa
Ana Paula Costa
(assistente DEEI)
(professor auxiliar DEEI)
(professor auxiliar DEEI)
Estruturas de Dados (2004-2005)
5
As aulas foram apresentadas conforme mostra a calendarização acima.
Na primeira semana não foram efectuadas aulas práticas por não ter sido leccionada matéria teórica.
A aula prática prevista para o turno P3 no dia 19 de Abril de 2005, não foi leccionada por ausência
do docente, pois coincidiu com uma reunião da Comissão Científica do DEEI. No entanto como
este turno tinha mais uma aula prevista que os restantes a calendarização não foi afectada.
A dessincronização do número de aulas para os diferentes turnos, devido a feriados e outros
acontecimentos eventuais, fez com que aos turnos P1, P2 e P5 coubesse mais uma aula que aos
restantes. Assim as aulas de 2, 3 e 9 de Junho de 2005 foram dedicadas apenas ao trabalho prático e
abertas a alunos inscritos em todos os turnos práticos.
O trabalho prático deste ano consistiu na implementação de uma aplicação de gestão de contas à
ordem de um só titular em ANSI C.
Foi requerido que implementação fosse baseada em Tipos de Dados abstractos e que fosse
efectuada a separação do interface de utilizador do motor da aplicação.
O trabalho prático foi faseado, ao longo do semestre, à medida que foram introduzidos os conceitos
e estruturas de dados necessárias para a implementação.
8
Assiduidade
8.1 Teóricas
Alunos inscritos na disciplina segundo os serviços académicos:
Curso
ESC
EI
I
ESI
Total
2
54
119
121
296
alunos
100
90
80
70
60
T1
50
T2
40
Total
30
20
10
0
1
3
5
7
9
11 13 15 17 19 21 23 25 27
aula nº
Fig. 1 – Assiduidade às aulas teóricas
No gráfico acima têm-se a assiduidade à componente teórica por aula, para cada turno e total.
Estruturas de Dados (2004-2005)
6
8.2 Práticas
Alunos inscritos nos turnos práticos:
Turno
P1
P2
P3
P4
P5
33
40
30
44
33
alunos
120
100
P1
80
P2
P3
Total
180
60
P4
P5
40
Total
20
0
1
2
3
4
5
6
7
8
9
10 11
12
13 14
aula nº
Fig. 2 – Assiduidade às aulas práticas
No gráfico acima têm-se a assiduidade à componente prática por aula, para cada turno e total.
9 Avaliação
Para avaliação contínua, exame de época normal e exame de recurso está indicada a percentagem de
aprovação baseada nos alunos que se propuseram a cada época de avaliação. Assim para avaliação
contínua será utilizado o número de alunos que compareceram ao teste e não a totalidade de
inscritos segundo os serviços académicos.
ESC
0
ESI
13
EI
6
I
9
Total
28
Entregaram o Trabalho:
0
12
6
11
29
Aprovados por avaliação continua:
% aprovação
0
7
1
5
13
0,00%
53,85%
16,67%
55,56%
46,43%
0
0
15
9
4
4
12
5
31
18
0,00%
60,00%
100,00%
41,67%
58,06%
1
1
5
1
1
0
9
2
16
4
100,00%
20,00%
0,00%
22,22%
25,00%
Assiduidade ao teste:
Assiduidade ao exame época normal:
Aprovados no exame época normal:
% aprovação:
Assiduidade ao exame recurso:
Aprovados no exame recurso:
% aprovação:
Total de alunos aprovados
Estruturas de Dados (2004-2005)
35
7
Os seguintes histogramas mostram a distribuição de notas para as épocas de avaliação acima
indicadas:
Distribuição de notas de frequência
7
6
5
4
3
2
1
0
0
1 2 3
4 5 6
7 8
9 10 11 12 13 14 15 16 17 18 19 20
nota
Distribuição de notas de exame época normal
5
4
4
3
3
2
2
1
1
0
0
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20
nota
Distribuição de notas de exame de recurso
5
4
3
2
1
0
0
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20
nota
Fig. 3 – Distribuição de notas
Estruturas de Dados (2004-2005)
8
____________________________________________________
Helder Daniel
Responsável pela disciplina de Estrutura de Dados no ano lectivo 2004/2005
Estruturas de Dados (2004-2005)
9
Estruturas de Dados (2004-2005)
10
Enunciados dos momentos de avaliação
Teste
Exame época normal
Prova Complementar
Exame recurso
Trabalho prático
Estruturas de Dados (2004-2005)
11
Estruturas de Dados (2004-2005)
12
UNIVERSIDADE DO ALGARVE
Faculdade de Ciências e Tecnologia
Departamental de Engenharia Electrónica e Informática
Estruturas de dados (2004/2005)
Licenciaturas em Engenharia de Sistemas e Informática, Ensino de Informática e Informática
Teste
7 de Junho 2005
Duração: 2h00m
1. Seja a seguinte declaração:
int ai[] = { 1, 2, 3, 4, 5 };
a) (0.5v) Justifique o que é impresso após executado o seguinte segmento de código:
int i, *pi = &ai[4];
for (i=0; i<=4; i++) printf ("%d ", *(pi-i));
b) (1v) Escreva um segmento de código que troque aleatoriamente as posições dos
elementos do array ai.
2. Considere uma lista simplesmente ligada (ou cadeia) de números inteiros, onde o ponteiro plist
aponta o nó que está à cabeça:
plist
1
2
3
4
NULL
e a estrutura do nó define-se como:
typedef struct node *link;
struct node { int item; link next; };
a) (1v) Implemente uma função que retorne o item à cabeça da lista. Se necessário indique
as pré-condições.
b) (1v) Implemente uma função que insira um nó, já existente passado como argumento, no
fim da lista.
c) (1.5v) Implemente uma função que remova o último nó. Indique pré e pós-condições.
d) (1v) Supondo que a lista acima suporta a implementação de um Stack, onde o topo está à
cabeça e que a função que substituí o item no topo pelo argumento t define-se como:
void STACKchgtop (link plist, int t) { plist->item = t; }
Justifique sucintamente se a lista plist poderá ser considerada um tipo de dados abstracto.
3. Seja a seguinte matriz esparsa de números inteiros e sua transposta:
⎡0 0 0 0 ⎤
A = ⎢⎢0 0 7 0⎥⎥
⎢⎣0 8 0 9⎥⎦
⎡0
⎢0
T
A =⎢
⎢0
⎢
⎣0
0 0⎤
0 8⎥⎥
7 0⎥
⎥
0 9⎦
a) (0.75v) Declare uma estrutura de dados que possa ser usada para guardar informação
sobre os elementos não nulos das matrizes, isto é um triplo.
b) (0.75v) Para a matriz A represente esquematicamente como poderia guardar a
informação dos elementos não nulos (os triplos) numa lista simplesmente ligada.
c) (1v) Escreva um segmento de código que transforme os triplos da lista de elementos não
nulos da matriz A nos triplos da matriz transposta de A, i.e.: A i, j = A T j,i
Teste ED 2004 / 2005 - 1/2
4. Na sequência TES*T*E uma letra representa uma operação de put numa fila de espera FIFO e
um * significa uma operação de get.
a) (0.75v) Qual a primeira letra na fila após as operações indicadas na sequência acima
terem sido efectuadas? Justifique.
b) (0.75v) Mostre o que sucederia se após o último put fossem efectuados mais 4 get
consecutivos, isto é a sequência de operações: TES*T*E**** .
5. Seja a seguinte árvore binária ordenada (ou de pesquisa), onde cada nó guarda um inteiro, e o
valor do item de um nó é maior que todos os itens na subárvore esquerda e menor ou igual que
todos os itens na subárvore direita.
a) (0.75v) Declare um ponteiro e uma estrutura que permitam referenciar e definir um nó
da árvore binária.
b) (1.5v) Implemente uma função que percorra uma árvore binária segundo um percurso
posorder e imprima os itens de cada nó. Para a árvore acima indique a ordem pela qual
os nós são percorridos.
c) (1.5v) Escreva uma função recursiva que verifique se uma árvore binária, onde os itens
são inteiros, é ou não ordenada (de pesquisa).
d) (1.5v) Represente a árvore binária acima usando um array, e explique como sabendo o
índice de um nó nesse array se pode chegar aos índices dos seus filhos esquerdo e
direito.
6. Seja a função que implementa o algoritmo de ordenação por inserção (ascendente) para um
array a de N inteiros:
void insertion(int *a, int N) {
int i, j, t;
for(i=1; i<N; i++)
for(j=i; j>0; j--)
if (a[j] < a[j-1]) {
t = a[j];
a[j] = a[j-1];
a[j-1] = t; }
}
a) (1.5v) Para os array seguintes indique o estado (ordem dos elementos do array) após ser
completada cada iteração do ciclo for exterior (variável i):
i) ai[ ] = { 5, 4, 3, 2, 1 };
ii) bi[ ] = { 1, 2, 3, 4, 5 };
b) (0.75v) Como poderia ser alterada a função de modo que os inteiros sejam ordenados por
ordem inversa (descendente)?
c) (1.5v) Explique as diferenças entre o algoritmo de ordenação por inserção e o algoritmo
bubble sort. Indique quais as alterações na função acima para que passe a implementar o
algoritmo bubble sort.
d) (1v) Descreva sucintamente como poderia ser melhorado, em termos médios, o
desempenho do algoritmo de inserção apresentado acima.
Teste ED 2004 / 2005 - 2/2
UNIVERSIDADE DO ALGARVE
Faculdade de Ciências e Tecnologia
Departamento de Engenharia Electrónica e Informática
Estruturas de dados (2004/2005)
Licenciaturas em Engenharia de Sistemas e Informática, Ensino de Informática e Informática
Exame época normal
2h00m
6 de Julho 2005
Duração:
1. (1v) Para as alíneas seguintes, justifique qual o valor impresso:
a)
int a = 1;
int *p = &a;
*p += 1;
printf ("%d", a);
b)
char s[] = "abcdef";
char *p = &s[2];
p ++;
printf ("%c", *p);
2. Considere uma lista simplesmente ligada onde cada item é um caracter, e o ponteiro plist aponta
o nó que está à cabeça:
plist
A
C
D
E
NULL
a) (0.75v) Declare um ponteiro e uma estrutura que permitam referenciar um nó da lista.
b) (1.25v) Implemente uma função que remova o item à cabeça da lista e liberte a memória.
Se necessário indique as pré-condições.
c) (1v) Implemente uma função que retorne o comprimento da lista.
d) (1v) Implemente uma função que imprima os itens da lista por ordem inversa, isto é do
último nó para o primeiro.
e) (1v) Discuta sucintamente as vantagens e desvantagens das listas duplamente ligadas
quando comparadas com listas simplesmente ligadas.
f) (1v) Supondo que já existe alocado na memória um nó com o item 'B', apontado por
nnode, implemente um segmento de código que o insira na lista entre o nó com item 'A'
e o nó com item 'C'.
3. Seja o polinómio: P(x) = 3x10 + x2 + 5
a) (1.5v) Descreva como poderia ser guardado um polinómio como o acima:
i) num array, onde mesmo os coeficientes nulos são armazenados.
ii) numa lista, que minimize o uso de memória, armazenando apenas os coeficientes
não nulos.
b) (1v) Implemente um segmento de código que realize a operação R(x) = P(x) x 2.
Considere que os coeficientes do polinómio acima já estão guardados no array P. O
resultado será guardado no array R, que deverá ser alocado na memória dinâmica (e
validada a sua alocação) com a mesma dimensão de P (11 elementos), antes de se
efectuar a operação.
4. Considere a sequência E*X*AME*.
a) (0.75v) Se uma letra representar uma operação put numa fila de espera FIFO e um * uma
operação get, quais as letras na fila, e a sua ordem, após as operações indicadas na
sequência acima terem sido efectuadas? Justifique.
b) (0.75v) Se uma letra representar uma operação push numa pilha, ou stack (LIFO), e um *
uma operação pop, quais as letras na pilha, e a sua ordem, após as operações indicadas na
sequência acima terem sido efectuadas? Justifique.
Exame época normal ED 2004 / 2005 - 1/2
5. Pretende-se implementar o ADT, com suporte para múltiplas instâncias, Ponto, com duas
coordenadas inteiras x e y. Considerando o ficheiro ponto.h que declara o interface do ADT e o
ficheiro de implementação do ADT ponto.c, escreva todo o código necessário (incluindo
protótipos de funções), nos ficheiros correctos, de acordo com:
a) (0.75v) Estrutura do ADT e ponteiro para esta (identificado por Ponto).
b) (1v) Função: Ponto PONTOnovo(int x0, int y0), que cria uma nova instância do ADT
na memória dinâmica e retorna um ponteiro para esta ou NULL se não existir memória
disponível.
c) (1v) Função: Ponto PONTOsoma(Ponto A, Ponto B), que retorna uma nova instância
do ADT Ponto, com a soma dos pontos argumentos A e B, isto é a soma das
coordenadas: C (x0+x1, y0+y1) <=> A (x0, y0) + B (x1, y1)
d) (0.75v) Escreva um segmento de código cliente que crie os pontos A(1,2), B(3,2) e
guarde no ponto C a soma de A com B.
6. Seja a seguinte árvore binária:
A
B
C
D
G
E
onde cada nó é definido por:
typedef struct node *link;
struct node { char item; link left, right; };
a) (1v) Escreva uma função que conte os nós internos da árvore binária.
b) (0.75v) A árvore binária é completa? Justifique.
c) (0.5v) Represente a árvore binária acima usando um array.
7. (1v) Explique sucintamente o funcionamento do algoritmo de ordenação por selecção
(ascendente) se a colecção de itens a ordenar estiver guardada numa lista simplesmente ligada.
8. Seja a seguinte implementação da versão probabilistica do algoritmo de ordenação quicksort
(descendente), para um array a de n inteiros, onde a macro exchange troca o valor dos seus
dois argumentos:
void qs(type* a, int n){
int i;
int partition(type* a, int n){
int i, last=0;
int p=rand()%n;
if (n<2) return;
i=partition(a, n);
qs(a, i);
qs(a+i+1, n-i-1);
exchange(a[0], a[p]);
for (i=1; i<n; i++)
if (a[i] > a[0]) {
++last;
exchange(a[i], a[last]);
}
exchange(a[0], a[last]);
return last;
};
};
a) (0.75v) Como poderia ser modificado o algoritmo para que a ordenação passe a ser
ascendente?
b) (0.75v) Para implementar a versão clássica, qual das duas funções acima deveria ser
modificada. Justifique.
c) (0.75v) Indique no que consiste o melhoramento do algoritmo quicksort denominado
partição pela mediana de 3 amostras.
Exame época normal ED 2004 / 2005 - 2/2
UNIVERSIDADE DO ALGARVE
Faculdade de Ciências e Tecnologia
Departamento de Engenharia Electrónica e Informática
Estruturas de dados (2004/2005)
Licenciaturas em Engenharia de Sistemas e Informática, Ensino de Informática e Informática
Exame época recurso
21 de Julho 2005
Duração: 2h00m
Ao longo do enunciado considere o array de inteiros: int ai[ ] = { 4, 6, 2, 5, 1, 3, 7 };
1.
a) (0.5v) Explique o que é impresso pelo seguinte segmento de código:
int i;
for (i=0; i<7; i+=2) printf ("%d ", *(ai+i));
b) (0.5v) Quais as alterações e efectuar ao código acima para que sejam impressos os
elementos de índice impar do array ai, isto é: 6 5 3
2.
a) (1.25v) Implemente uma função que reserve memória dinamicamente para um array de n
inteiros, e retorne um ponteiro para esse array ou NULL em caso de insuficiência de
memória. Indique pré-condições e excepções se necessário.
b) (1v) Escreva um segmento de código que reserve memória dinamicamente para um array
de 7 inteiros e copie para esse array os elementos do array ai pela mesma ordem.
3. Neste exercício considere que lista refere-se a uma lista simplesmente ligada de inteiros.
a) (0.75v) Declare um ponteiro e uma estrutura que permitam referenciar um nó da lista.
b) (1.5v) Escreva um segmento de código que crie uma nova lista, copiando os elementos do
array ai para essa lista pela mesma ordem.
c) (1v) Escreva um segmento de código que remova da lista criada na alínea anterior (e da
memória) o 2º nó, isto é o nó cujo elemento é o número 6.
d) Supondo que se pretende implementar um stack baseado numa lista:
i. (1v) Em que ponto da lista se devem fazer as operações de inserção e remoção de
elementos de modo que o tempo de execução destas seja constante e o menor possível?
Justifique.
ii. (1v) Implemente a função int STACKtop (link s), que retorna (mas não elimina) o
elemento no topo do stack s.
e) (1v) Supondo que existe um ponteiro para o ultimo nó da lista, identificado por plast,
escreva uma função que adicione em tempo constante, um nó já existente ao fim da lista.
4. Pretende-se implementar o ADT com suporte para múltiplas instâncias Date, para manipulação de
datas de acordo com o calendário Gregoriano. Cada instância guarda uma data em 3 inteiros: o dia,
o mês e o ano. Considerando que no ficheiro date.h será declarado o interface do ADT e o ficheiro
date.c terá a implementação, escreva todo o código necessário (incluindo protótipos de funções),
nos ficheiros correctos, de acordo com:
Exame época recurso ED 2004 / 2005 - 1/2
a) (0.75v) Estrutura do ADT e ponteiro para esta (identificado por Date). A estrutura contém
3 inteiros para guardar o dia, mês e ano.
b) (1.25v) Supondo que está disponível a função void sysdate (int *day, int *month, int
*year) que retorna nos seus argumentos a data actual do sistema, declare e defina a função
Date DATEnow (void) que cria uma nova instancia deste ADT e que retorna um ponteiro
para esta ou NULL no caso de insuficiência de memória.
c) (1v) Declare e defina a função void DATEprint (Date d) que escreve na consola a
instância d no formato: dia / mes / ano. Indique pré e pós condições se necessário.
d) (0,75v) Escreva um segmento de código que usando este ADT mostre no monitor a data
actual do sistema
e) (0.75v) Proponha uma estrutura alternativa para o ADT que permita poupar memória no
armazenamento do dia, mês e ano.
5. Seja a definição de um nó numa árvore binária:
typedef struct node *link;
struct node { int item; link left, right; };
a) (1.5v) Supondo que está disponível a função:
/* Descrição: se root == NULL é criado o nó raiz da árvore com o item t,
senão um novo nó com o item t é adicionado à árvore binária de pesquisa
com raiz root, onde o item do filho esquerdo é menor que o item do pai
e o item do filho direito é maior ou igual que o item do pai.
POS: Adiciona novo nó à árvore de pesquisa e retorna a raiz da árvore */
link btree (link root, int t);
escreva um segmento de código que percorra o array ai desde o índice 0 para o final, e
adicione cada elemento do array a uma árvore binária de pesquisa (inicialmente vazia).
b) (0.75v) Represente esquematicamente a árvore binária de pesquisa criada na alínea anterior.
c) (1v) Implemente uma função que retorne a altura de uma árvore binária. Considere que uma
árvore com apenas um nó, a raiz, tem altura 0.
6. Considere o código do algoritmo de ordenação Quicksort para inteiros:
void qs(int* a, int n){
int i;
int partition (int *a, int n) {
/* ... */
if (n<2) return;
i=partition(a, n);
qs(a, i);
qs(a+i+1, n-i-1);
}
}
a) (0.75v) Modifique o algoritmo de modo que se os elementos numa partição forem menores
que 10 sejam ordenados pela função: void selection (int *a, int n).
b) (1.25v) Seja a função void swap (int *a, int *b) que troca o valor dos seus dois
argumentos, defina a função: void selection (int *a, int n), que implementa o algoritmo de
ordenação por selecção.
c) (0.75) O algoritmo de ordenação por selecção é adequado para ordenar colecções guardadas
em ficheiros (por exemplo no disco rígido). Porquê?
Exame época recurso ED 2004 / 2005 - 2/2
UNIVERSIDADE DO ALGARVE
Faculdade de Ciências e Tecnologia
Departamento de Engenharia Electrónica e Informática
Estruturas de dados (2004/2005)
Licenciaturas em Engenharia de Sistemas e Informática, Ensino de Informática e Informática
Prova complementar
19 de Julho 2005
Duração: 1h00m
1. Considere uma lista simplesmente ligada (ou cadeia) de números inteiros, onde o ponteiro plist
aponta o nó que está à cabeça:
plist
1
2
3
4
NULL
a) Declare um ponteiro e uma estrutura que possa referenciar e definir um nó da lista na
memória dinâmica.
b) Implemente uma função que remova o item à cabeça da lista da memória dinâmica. Se
necessário indique as pré-condições.
c) Implemente uma função que percorra a lista e imprima o item do nó.
d) Supondo que a lista acima suporta a implementação de um Stack, onde o topo está à
cabeça, escreva uma função que remova e retorne o item no topo do stack.
2. Seja a seguinte árvore binária onde cada nó guarda um inteiro:
a) Declare um ponteiro e uma estrutura que permitam referenciar e definir um nó da árvore
binária na memória dinâmica.
b) Implemente uma função que percorra uma árvore binária segundo um percurso inorder e
imprima os itens de cada nó. Para a árvore acima indique a ordem pela qual os nós são
percorridos.
c) A árvore binária é completa? Justifique.
3. Seja a função que implementa o algoritmo de ordenação por selecção (ascendente) para um array
a de N inteiros:
void selection(int *a, int N) {
int t, i, j, im;
for(i=0; i<N-1; i++) {
im=i;
for(j=i+1; j<N; j++) if ([j] < a[im]) im=j;
t = a[i]; a[i] = a[im]; a[im] = t;
}
}
a) Para o array ai [ ] = { 3, 1, 2, 5, 4 }, indique o estado (ordem dos elementos do array)
após ser completada cada iteração do ciclo for exterior (variável i):
b) Como poderia ser alterada a função de modo que os inteiros sejam ordenados por ordem
inversa (descendente)?
c) Descreva sucintamente o principio de funcionamento do algoritmo de ordenação por
inserção quando aplicado a um array de inteiros.
Prova Complementar ED 2004/2005 - 1/1
Trabalho Prático EDa 2004/2005
Gestão de contas à ordem
Desenvolver uma aplicação que permita gerir contas à ordem de um só titular, em ANSI C, a
qual deverá suportar os seguintes serviços:
i)
ii)
iii)
iv)
v)
vi)
vii)
Criação de contas
Levantamentos e depósitos numa dada conta
Transferências manuais entre contas
Eliminação de movimentos
Extracto de movimentos de uma dada conta, ordenado por data e por descrição
Consulta de saldo de uma dada conta
Leitura e escrita em disco das contas e seus movimentos.
Todas as operações deverão ser efectuadas na memória principal, no entanto toda a
informação deverá ser também guardada na memória secundária por pedido explicito do
utilizador.
Para executar o programa deve ser digitado na linha de comandos do Linux o seu nome e o
nome de um ficheiro que guarda a informação:
> contas <nome do ficheiro para guardar a informação sobre as contas>
Os argumentos da linha de comandos devem ser validados e verificado se o ficheiro
especificado como primeiro argumento é valido. Se tal não suceder deve ser emitida uma
mensagem de erro correspondente e o programa deve abortar.
Se o ficheiro não existir deverá ser criado um novo.
As contas à ordem devem ser identificadas pelo número de conta, que deverá ser único. É
também necessário manter um registo de todos os movimentos efectuados numa conta, desde
a sua criação. Considere que um movimento é caracterizado por um número de ordem único,
sequencial e independente da conta; tipo, que poderá ser levantamento ou depósito; data;
descrição e valor positivo.
No caso de uma transferência, deve ser efectuado na conta fonte um levantamento e na conta
destino um depósito, ambos com o mesmo número de movimento, data, descrição e valor,
sendo também indicado qual a conta fonte e destino, como mostra o exemplo de extractos de
conta seguinte:
Nº de Conta: 1
Nº
data
0
01/09/04
1
10/09/04
3
01/10/04
4
10/10/04
tipo
descrição
depósito
Vencimento Out
levantamento
depósito
CHK CGD 123456
levantamento
valor (euros)
1000
100
100
50
Nº Conta
Destino 2
Nº de Conta: 2
Nº
data
2
05/09/04
4
10/10/04
tipo
depósito
depósito
valor (euros)
1000
50
Nº Conta
Fonte 1
descrição
Abertura
Enunciado do trabalho prático de Estruturas de dados 2004/5
1-2
No saldo deve constar a seguinte informação:
Nº de Conta: 2
Saldo:
€ 1050
A aplicação deve ser dividida em dois módulos principais: o motor, que pode ser visto como
um servidor que presta os serviços acima indicados e o interface com o utilizador, que
permitirá que um utilizador possa aceder aos serviços do motor. Este interface poderá ser
simples, no entanto terá de respeitar algumas especificações de modo que possa no futuro ser
substituído por outro mais elaborado.
Especificações sobre estruturas de dados e estrutura da aplicação que deverão ser
obrigatoriamente seguidas serão apresentadas gradualmente ao longo do semestre em 4
fases.
Entrega do trabalho
i) Data
A data limite de entrega é terça-feira 14 de Junho de 2005.
ii) Código fonte
O código fonte deve ser acompanhado de um makefile para gerar o executável, que deverá
chamadar-se contas. (Todos os ficheiros devem ter como comentário os Nomes, Nos. e Curso
dos elementos do grupo)
Cada módulo deve ser dividido em interface (<nome do módulo>.h) e implementação (<nome
do módulo>.c) excepto o programa principal.
Todas as funções devem ser documentadas (Descrição, Pré e Pós condições, Excepções).
Pode ser entregue por e-mail ou em disquete ao docente do turno prático em que esta
inscrito o grupo.
ii) Relatório
Com o código fonte terá der ser entregue um relatório, que incluirá um pequeno manual do
utilizador e um manual de referência. Este último deverá incluir um diagrama de estrutura da
aplicação. Um template para este relatório será disponibilizado na página da disciplina:
O relatório deverá ser entregue em papel, ao docente do turno prático em que está
inscrito o grupo.
Avaliação
De acordo com o indicado na aula teórica 1. Será tomada especial atenção à correcção do
programa e à eficiência da implementação. Será avaliada também a decomposição da
aplicação em módulos coesos e bem documentados como estudado nas aulas teóricas e a
implementação e utilização das estruturas de dados.
Nota: Funcionalidades não pedidas nos enunciados não serão avaliadas.
Bibliografia recomendada
Além da bibliografia indicada para a disciplina, as aulas teóricas e práticas disponíveis em
http://w3.ualg.pt/~hdaniel/Ed/, pode ser também consultada a resolução dos trabalhos práticos
de EDa, ano lectivo 2003/2004, já enviados para a mailing list da disciplina: [email protected].
Enunciado do trabalho prático de Estruturas de dados 2004/5
2-2
Trabalho de Estruturas de Dados 2004/2005
Gestão de contas à ordem
Pormenores sobre a implementação para a 1ª fase
1 Preliminares
O programa será dividido em 2 módulos principais. Um motor, que efectuará todas as operações de
gestão de contas à ordem, e um interface de utilizador. Estes módulos serão implementados como 2
ADTs (tipos de dados abstractos). O ADT accountmanager será o motor e o ADT amui o
interface de utilizador. Este último módulo aceitará comandos de utilizador e irá transformá-los em
pedidos de serviços ao motor (gestor):
memória
principal
Aplicação
accountmanager
comandos do
utilizador
utilizador
chamadas a
funções do motor
amui
retorno das
funções do motor
informação para
utilizador
sistema de
ficheiros
2 Função main
O programa terá que seguir algumas normas, de modo que numa fase posterior o ADT amui possa
ser substituído por outro compatível, em termos de interface com o o gestor de contas
(accountmannager). O programa principal terá obrigatoriamente o nome contas.c e o seguinte
layout:
/* Gestor de contas à ordem
TP ED 2004-2005
Nomes, Nºs e curso dos elementos do grupo
*/
#include "accman.h" /* account manager: header do ADT gestor de contas (motor)*/
#include "amui.h"
/* account manager user interface: header do ADT interface
de utilizador */
/* incluir outros headers necessários.
*/
int main(int argc, char** argv) {
accountmanager m; /* instância do ADT motor */
Pormenores de implementação da 1ª fase do trabalho prático de Estruturas de dados 2004/5
1-7
amui i;
/* instância do ADT interface de utilizador */
/* Valida linha de comandos do S.O. de modo a garantir que tem 1 argumento!
Senão deve imprimir no stderr a mensagem:
"Chamada:
contas <nome de ficheiro para guardar informação>"
e terminar
*/
/* Reserva memória e inicializa o ADT motor */
m = ACCMANinit(argv[1]);
/* Se m == NULL deve imprimir no stderr a mensagem:
"Não foi possível inicializar o motor"
e terminar
*/
/* Reserva memória e inicializa o ADT interface de utilizador e associa-o ao
motor */
i = AMUIinit(m);
/* Se i == NULL deve imprimir no stderr a mensagem:
"Não foi possível inicializar o interface de utilizador"
e terminar
*/
/* Executa interface de utilizador (e o programa)*/
AMUIrun (i);
/* Liberta memória reservada às instâncias dos ADTs*/
AMUIdel (i);
ACCMANdel (m);
return 0;
}
As únicas alterações necessárias consistem em substituir os comentários a vermelho pelo código
C respectivo. (e claro colocar no cabeçalho o nome, nº e curso dos elementos do grupo - comentário
a azul).
A partir dos dois includes no topo do programa verifica-se que os headers do ADT motor
(accountmanager) e interface de utilizador (amui) terão obrigatoriamente de ter os nomes:
accman.h e amui.h. Os ficheiros com a implementação das funções do interface destes ADTs terão
de ter os nomes: accman.c e amui.c.
No inicio do programa deve ser introduzido código para validar a linha de comandos do Sistema
Operativo. A chamada consiste no nome do executável e no caminho para um ficheiro que guarda
os dados sobre as contas:
contas <caminho do ficheiro de dados>
Se este ficheiro não existir assume-se que será criado um novo, mas isso será efectuado pelo ADT
accountmanager.
Na função main será necessário garantir que o programa é chamado com um argumento na linha de
comandos, como indica o 1º comentário a vermelho.
Pelo layout pode-se observar que os ADTs utilizados são primeiro inicializados:
m = ACCMANinit(argv[1]);
Pormenores de implementação da 1ª fase do trabalho prático de Estruturas de dados 2004/5
2-7
i = AMUIinit(m);
Estas funções retornam um ponteiro para a instância do ADT criada. Se retornarem NULL assumese que por algum motivo não foi possível criar e inicializar a instância do ADT, e o programa
termina imprimindo a mensagem de erro indicada nos comentários imediatamente abaixo das
chamadas às funções.
Toda a operação será efectuada após se executar o interface de utilizador, a instância i do ADT
amui:
AMUIrun (i);
Assim este é responsável por enviar os comandos do utilizador ao motor do gestor
(accountmanager), tendo por isso sido associado à instância m desse ADT, inicializada acima.
Após o utilizador pedir para terminar o interface, os ADTs são libertos da memória e o programa
termina:
AMUIdel (i);
ACCMANdel (m);
Repare-se que para cada ADT existe uma função para o inicializar e outra para o terminar. Esta é
uma boa prática quando se programa ADTs. Mesmo que numa dada altura do desenvolvimento não
sejam necessárias, estas funções devem existir para futura expansão – mesmo que não tenham
instruções no corpo. Por outro lado tarefas comuns destas funções são libertar a memória alocada à
instância do ADT passada como argumento, fecho de ficheiros ou streams, etc..
Nota: A especificação dos interfaces (ficheiro *.h) destes 2 ADTs, que deverá obrigatoriamente
ser seguida será apresentada na 2ª fase.
Pormenores de implementação da 1ª fase do trabalho prático de Estruturas de dados 2004/5
3-7
2.1
Teste da função main
Para testar se o programa faz o que se pretende, isto é validar a linha de comando do S.O. e a
inicialização dos ADTs accountmanager e amui pode-se implementar temporariamente nos
headers as funções necessária. Atenção que isto é uma implementação temporária só para testar a
função main. A programação destes ADTs será efectuada numa fase posterior. Assim o ficheiro
accman.h poderá ser:
#ifndef _ACCMAN_
#define _ACCMAN_
typedef void* accountmanager;
accountmanager ACCMANinit(const char* fn){
return (void *) 0;
/* 0 == NULL e qq valor != 0 é !NULL */
};
void ACCMANdel (accountmanager ui){
};
#endif
E o ficheiro amui.h:
#include "accman.h"
typedef void* amui;
amui AMUIinit(accountmanager m){
return (void *) 1;
/* 0 == NULL e qq valor != 0 é !NULL*/
};
void AMUIrun (amui ui){
};
void AMUIdel (amui ui){
};
Repare-se que foram definidas apenas as funções utilizadas em main. As funções de libertação de
memória não têm instruções no corpo.
As únicas funções com algum código no corpo são as de inicialização. Assim é possível fazer com
que estas funções retornem um ponteiro NULL – i.e. zero - ou não (modificando o valor retornado e
recompilando o programa) de modo a testar a validação da criação das instâncias de ambos os
ADTs na função main.
Para testar a validação da linha de comandos basta executar o programa com um número de
argumentos diferente de um.
2.2 Compilação do programa
Para compilar o programa, nesta fase de desenvolvimento, basta compilar o ficheiro contas.c. No
entanto é obrigatório desenvolver um makefile. O makefile será um ficheiro com esse nome,
semelhante aos utilizados nas aulas práticas e pode ter o seguinte layout:
#TP Eda 2004-5
CC
OUT
= gcc
= contas
Pormenores de implementação da 1ª fase do trabalho prático de Estruturas de dados 2004/5
4-7
LIBS
= -lm #-lncurses #necessario se UI usa biblioteca ncurses
CFLAGS = -g -ansi -Wall
FILES = $(OUT).o #accman.o amui.o #outros modulos necessarios
#link
$(OUT): $(FILES)
$(CC) $(FILES) -o $(OUT) $(LIBS)
#a linha acima inicia-se com um <TAB>
#compile
c.o: $*.c $*.h
$(CC) $(CFLAGS) -c $*.c -o $*.o
#a linha acima inicia-se com um <TAB>
clean:
rm -f *.o
rm -f $(OUT)
rm -f $(OUT).exe
#as 3 linhas acima iniciam-se com um <TAB>
Assim o nome do executável será contas (variável OUT), a biblioteca a incluir será para já apenas
m (variável LIBS), embora ainda não seja necessária poderá vir a ser na fase seguinte. Numa fase
posterior poderá ser necessário utilizar a biblioteca ncurses, dai que esteja em comentário.
Nesta fase como só temos um ficheiro, a variável FILES será apenas:
FILES
= $(OUT).o
isto é:
contas.o
Durante o desenvolvimento da aplicação, quando se adicionar mais módulos ao programa (leia-se
ficheiros com extensão *.c) basta adicionar o nome desse ficheiros, mas com extensão *.o à variável
FILES.
Assim para compilar o programa basta colocar todos os ficheiros no mesmo directório (incluindo o
makefile) e digitar:
make
na linha de comandos do S.O..
Repare-se que se se digitar:
make clean
serão apagados todos os ficheiros *.o e o executável, de modo que se possa recompilar todos os
módulos novamente.
3 Data do sistema
Para lançar movimentos é necessário ler a data do sistema. O seguinte programa ilustra como esta
pode ser acedida e transformada numa string no formato DD/MM/AAAA:
Pormenores de implementação da 1ª fase do trabalho prático de Estruturas de dados 2004/5
5-7
#include <time.h>
#include <stdio.h>
/* DEFINED in <time.h>
struct tm {
int
int
int
int
int
int
int
int
int
};
tm_sec;
tm_min;
tm_hour;
tm_mday;
tm_mon;
tm_year;
tm_wday;
tm_yday;
tm_isdst;
seconds
minutes
hours
day of the month
month
year
day of the week
day in the year
daylight saving time
The members of the tm structure are:
tm_sec The number of seconds after the minute, normally in the range 0
to 59, but can be up to 61 to allow for leap seconds.
tm_min The number of minutes after the hour, in the range 0 to 59.
tm_hour The number of hours past midnight, in the range 0 to 23.
tm_mday The day of the month, in the range 1 to 31.
tm_mon The number of months since January, in the range 0 to 11.
tm_year The number of years since 1900.
tm_wday The number of days since Sunday, in the range 0 to 6.
tm_yday The number of days since January 1, in the range 0 to 365.
tm_isdst
A flag that indicates whether daylight saving time is in effect
at the time described. The value is positive if daylight saving
time is in effect, zero if it is not, and negative if the information is not available.
*/
int main () {
time_t t;
struct tm* ts;
char datestr[11];
t = time(NULL);
ts = localtime(&t);
printf ("%s\n\n", ctime (&t));
sprintf
(datestr,
"%02d/%02d/%d",
>tm_year);
printf ("%s\n\n", datestr);
getchar();
return 0;
}
ts->tm_mday,
ts->tm_mon+1,
1900+ts-
Repare-se que a função:
t = time(NULL);
não retorna uma estrutura com o tempo discriminado, para isso é necessário converter o retorno da
função acima numa estrutura tm, com:
ts = localtime(&t);
Pormenores de implementação da 1ª fase do trabalho prático de Estruturas de dados 2004/5
6-7
Após se obter essa estrutura, hora e data podem ser lidas dos seus membros de dados, como mostra
o programa.
Nota: A função ctime (&t) retorne uma string com a data, maii precisamente no formato:
Sun Apr 10 09:48:48 2005
No entanto não se tem controlo sobre a formatação dessa string.
4 Funções sobre listas ligadas
Como serão obrigatoriamente utilizadas listas ligadas, deve-se começar a organizar o código da
biblioteca para listas ligadas. Se bem que não seja obrigatório usar listas duplamente ligadas
circulares, estas estruturas vão facilitar a implementação de algumas funções do gestor de contas, de
modo que se recomenda o seu uso (aulas teóricas 9 e 10 e ficha prática 5).
Podem ser utilizadas as funções sobre listas ligadas desenvolvidas nas aulas teóricas ou nas práticas,
no entanto funções com excepções devem ser modificadas para indicar a excepção retornando por
exemplo NULL, mas não abortar o programa nem imprimir mensagem de erro.
O módulo cliente é que deve decidir o que fazer ao detectar a excepção. Por exemplo indicar ao
interface de utilizador a excepção, de modo este trate dela (p. ex. emitindo uma mensagem de erro
para o utilizador)
5 Compilador a utilizar
Deve ser usada o compilador gcc 3. Este encontra-se instalado nos sistemas Linux.
Alternativamente pode ser usado o ambiente cygwin, que emula o S.O. Linux sobre Windows, e
correntemente incluí a versão 3.3.3 do gcc.
Também pode ser usado o ambiente de desenvolvimento BloodShed Dev-C++ para Windows, que
incluí uma versão do compilador gcc para este S.O.
No entanto não esquecer que deve ser entregue junto com o código fonte um makefile que
permita compilar a aplicação num S.O. Linux.
Pormenores de implementação da 1ª fase do trabalho prático de Estruturas de dados 2004/5
7-7
Trabalho de Estruturas de Dados 2004/2005
Gestão de contas à ordem
Pormenores sobre a implementação para a 2ª fase
1
Implementação de ADT para guardar informação sobre cada movimento
Nota: Pode-se utilizar o template apresentado como anexo da aula teórica 16b 2004/2005. Mais
informação sobre ADTs múltipla instância podem também ser encontradas nessa aula.
Este tipo de dados abstracto servirá para guardar a informação sobre cada movimento, por isso terá
de suportar múltiplas instâncias. Cada instância ou variável deste ADT deverá guardar informação
sobre:
Nº de movimento
Data do movimento
tipo
descrição
valor
Nº de Conta
- poderá ser um inteiro.
- a data actual do sistema quando lançado o movimento.
- depósito ou levantamento. (poderá ser um tipo enumerado)
- uma cadeia de caracteres (string)
- valor positivo, que representa um valor monetário em Euros,
arredondado aos cêntimos de Euro (2ª casa decimal)
- um número de conta. Só utilizado no caso de uma transferência, isto
é um par levantamento/depósito, onde todos os campos são idênticos
com excepção do tipo e deste.
No levantamento será a conta destino, no depósito será a conta fonte.
Esta é a informação que deve constar na estrutura de cada instância do ADT, definida no ficheiro de
implementação, por exemplo movimento.c.
Nas funções do interface, por exemplo movimento.h, deverão existir funções para:
- Criar uma nova instância e inicializar todas as variáveis dessa (as variáveis acima).
Deverá por isso ter argumentos para passar esses valores. Poderá não ser necessário
passar a data, pois como esta é a data do sistema na altura do lançamento, a função
pode lê-la, como mostrado na 1ª fase, e guardá-la no campo correspondente da
estrutura.
- Eliminar uma instância da memória.
- Escrever a informação de uma instância do movimento num stream em modo de texto
formatado, como indicado no enunciado.
- Escrever a informação de uma instância do movimento num stream em modo binário.
- Leitura da informação de uma instância do movimento num stream em modo binário.
Estas duas ultimas serão utilizadas em conjunto com outras para guardar e recuperar toda a
informação do gestor de contas, isto é todas as contas e seus movimentos, no ficheiro indicado
como argumento de linha de comando do Sistema Operativo. (serão utilizadas na 3ª fase)
Sugere-se que se siga a implementação do ADT complexo da aula teórica 16b de 2004/2005.
Pormenores de implementação da 2ª fase do trabalho prático de Estruturas de dados 2004/5
1-4
Para testar este ADT pode-se criar um programa cliente que:
#1 incialize uma instância do ADT (e as suas variáveis de instância)
#2 guarde-a em modo binário
#3 lê-a em modo binário
#4 escreve-a em modo de texto no stdout
#5 liberta-a da memória
Pode ser tomado como exemplo o programa cliente do ADT complexo da aula teórica 16b
2004/2005.
2 Definir item de cada nó da lista ligada
Os movimentos terão de ser guardados em memória numa lista ligada, de modo que o item de cada
nó da lista deverá ser do tipo do ponteiro para a estrutura do ADT movimento. (recomenda-se que a
lista seja duplamente ligada circular):
Instância do
ADT conta
...
Instância do
ADT movimento
Instância do
ADT movimento
Instância do
ADT movimento
Assim se o ponteiro para instância do ADT movimento definido no interface deste ADT fôr, por
exemplo:
typedef struct MOVst* mov;
isto é: mov, e se existir um ficheiro type.h que define o tipo do item de cada nó de uma lista
ligadas, este ultimo ficheiro deverá ser definido:
#ifndef _TYPE_
#define _TYPE_
typedef mov item;
printstring "%p"
#endif
/* opcional. Indica que deve ser impresso o endereço do item*/
Pormenores de implementação da 2ª fase do trabalho prático de Estruturas de dados 2004/5
2-4
3 Demonstração de entrada-saída de dados através de streams
Usando streams pode-se aceder ao sistema de ficheiros e ao monitor, i.e. o stdout. O seguinte
programa apresenta algumas funções que permitem esse acesso:
/* Stream I/O demo
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 20
typedef struct {
float n;
char s[MAX_SIZE];
} record;
/* Tipo de dados definido pelo utilizador */
/* Não é abstracto pois os membros de dados da
/* estrutura estão disponíveis para o cliente (main) */
int main () {
FILE *f;
record rec = { -1234.56, "uma string" };
record inrec;
/* Stream Output (texto formatado)
Se f == stdout escreve no monitor
*/
f = fopen("file.txt", "w");
if (!f) {
fprintf (stderr, "can not open file");
exit (1); }
if (fprintf (f, "%f | %s\n", rec.n, rec.s) < 0) {
fprintf (stderr, "I/O error");
exit (1); }
fclose(f);
/* Stream I/O em (binário)
*/
f = fopen("file.bin", "w");
if (!f) {
fprintf (stderr, "can not open file");
exit (1); }
/* retorna o numero de items escritos*/
if (fwrite (&rec, sizeof (record), 1, f) != 1) {
fprintf (stderr, "I/O error");
exit (1); }
fclose(f);
f = fopen("file.bin", "r");
if (!f) {
fprintf (stderr, "can not open file");
exit (1); }
/* retorna o numero de items lidos.
se menor que o pedido ocorreu um erro ou chegou-se
sucedeu erro de leitura ou chegou-se ao fim do ficheiro*/
if (fread (&inrec, sizeof (record), 1, f) < 1) {
fprintf (stderr, "I/O error");
exit (1); }
fclose(f);
printf ("%f | %s\n", inrec.n, inrec.s);
getchar();
return 0;
}
A função:
Pormenores de implementação da 2ª fase do trabalho prático de Estruturas de dados 2004/5
3-4
int fprintf (FILE* f, formatstring, ...);
Escreve no stream f as variáveis formatadas em modo texto de acordo com o 2º argumento
formatstring.
Retorna um número negativo se existiu erro de escrita ou positivo caso contrário.
Se no parâmetro f fôr passado o stream para a saída padrão - stdout - escreve no monitor (se a saída
não tiver sido previamente redireccionada).
int fputc (char c, FILE *f);
Escreve no stream f o caracter c.
Retorna o carácter caso tenha sucesso, ou EOF (-1) caso contrário.
int fwrite (void* p, int size, int count, FILE* f)
int fread (void* p, int size, int count, FILE* f)
Escreve\lê do\no stream f, os dados no endereço dado por p com comprimento size bytes, count
vezes.
Em caso de sucesso retorna count, caso contrário um número menor que count.
Para associar um stream a um ficheiro pode ser usada a função:
FILE* fopen (const char* fn, const char* mode);
Retorna um ponteiro para o stream associado ao ficheiro fn. Caso não tenha sucesso retorna NULL.
O parâmetro mode permite abrir o ficheiro para:
escrita:
leitura:
leitura e escrita:
"w"
"r"
"rw"
Para encerrar o stream f, descarregando dados ainda na memória para o ficheiro associado ao
stream deve-se usar:
fclose (File* f);
Quando se usa uma função de escrita num ficheiro como por exemplo fwrite ou fprintf, os dados
poderão não ser imediatamente guardados nesse ficheiro mas sim num buffer na memória. Por
questões de eficiência o sistema operativo encarregar-se-á de descarregar os dados nesse buffer
para o ficheiro posteriormente.
Deste modo, para garantir que tudo o que foi pedido escrever é efectivamente escrito no ficheiro,
deve-se antes de terminar um programa fechar todos os ficheiros com fclose.
Se se pretender apenas descarregar dados ainda no buffer para o ficheiro associado ao stream f,
mantendo-o aberto para leitura ou escrita, pode-se usar:
fflush (File* f);
Pormenores de implementação da 2ª fase do trabalho prático de Estruturas de dados 2004/5
4-4
Trabalho de Estruturas de Dados 2004/2005
Gestão de contas à ordem
Pormenores sobre a implementação para a 3ª fase
1
Estrutura do gestor de contas
- As contas devem ser itens de uma lista ligada. Deverá pois existir um ADT Conta que suporte
múltiplas instâncias.
- Para cada conta deverá existir uma colecção de movimentos, isto é de instâncias do ADT
movimento desenvolvido na 2ª fase.
Esta colecção deverá ser implementa sobre uma lista ligada, ordenada por data do movimento.
Recomenda-se que seja duplamente ligada circular de modo a facilitar implementação de funções
de visualização de movimentos ordenados pelos movimentos mais recentes ou pelos mais antigos.
Nota: Não é necessário que a lista seja implementada como um ADT. Podem inclusive ser
utilizadas as funções sobre listas apresentadas nas aulas teóricas.
- A ordenação dos movimentos pela sua descrição será ascendente, indirecta e efectuada recorrendo
a uma árvore binária de indexação, que será descrita na 4ª fase.
Lista de instâncias do ADT Conta
(apontada pelo ponteiro contas, variável de accountmamager)
(apontadas pelo ponteiro mov, variável de Conta)
Lista de instâncias do ADT Movimento
contas
Conta
1
saldo
mov
Conta
2
saldo
mov
mov 1
NULL
...
Conta
3
saldo
mov
NULL
mov 3
mov 2
mov 3
ADT accountmanager
(gestor de contas ou motor)
Assim o ADT accountmanager terá um ponteiro para uma lista de contas e por sua vez cada
instância do ADT conta terá um ponteiro para uma lista de movimentos.
Estes ADT podem ser implementados de modo semelhante ao ADT polinómio baseado em listas
ligadas introduzido na aula teórica 18.
De notar que o item de cada nó da lista deverá ser um ponteiro para uma instância de um ADT.
Como se terá duas listas com ADTs diferentes, sugere-se que este ponteiro seja void*:
Pormenores de implementação da 3ª fase do trabalho prático de Estruturas de dados 2004/5
1-3
struct node {
void * item;
link next;
};
Nº de conta e Nº de movimento terão de ser únicos e sequenciais. Para isso poderão existir duas
variáveis de instância do ADT accountmanager que serão incrementadas quando criado um novo
movimento e uma nova conta. Estas variáveis deverão ser inicializadas com o valor 1, quando o
ficheiro passado como primeiro argumento, na linha de comandos, não existir. Será assim criado
um novo ficheiro para guardar os dados das contas.
2 Interfaces dos ADTs
Os interfaces dos ADTs accountmanager (motor) e amui (interface de utilizador) que deverão
obrigatoriamente ser seguidos é dado em anexo, ficheiros accman.h e amui.h
As funções desses ADTs deverão ser programadas de acordo com a sua descrição, pré-condições,
pós-condições e excepções.
O ADT amui aceitará comandos do utilizador e chamará funções correspondentes do motor
accountmanager. Deste modo a estrutura deste ADT incluirá uma instância de accountmanager:
/* amui.c */
#include "amui.h"
#include "accman.h"
/* ... */
struct AMUIstruct {
accountmanager m;
/* outras variáveis que possam ser necessárias*/
};
Esta instância do motor será passada como argumento da função que inicializa o ADT amui, por
exemplo:
amui AMUIinit(accountmanager m){
amui ui = (amui) malloc (sizeof *ui);
if (ui) ui->m=m;
return ui;
};
A operação do interface de utilizador pode ser simples, mas deve validar as entradas do utilizador.
Se o menu fôr:
123456-
Gravar
Criar Conta
Depositar
Levantar
Transferir
Saldo
...
S – Sair
Pormenores de implementação da 3ª fase do trabalho prático de Estruturas de dados 2004/5
2-3
A função AMUIrun poderá ser:
void AMUIrun (amui ui){
int c;
/* ... */
do {
/* ...
Imprime menu
variável c tem tecla pressionada pelo utilizador
...
*/
switch(c) {
/* ... */
case '6': saldo(ui); break;
/* ... */
}
}
while(c!='S');
};
e a função auxiliar em amui.c:
static void saldo (amui ui) {
int nc;
printf ("\nNº Conta: ");
scanf("%d", &nc);
ACCMANbalance(ui->m, nc, stdout);
/* ... */
};
Nota: O saldo e o extracto devem ser apresentados como indicado no enunciado.
Atenção: Mesmo que não seja necessário implementar alguma função indicada nos interfaces
destes dois ADTs, esta terá de existir no ficheiro de implementação mas sem código no seu corpo:
int func (int a) {
/* corpo vazio
*/
}
Pormenores de implementação da 3ª fase do trabalho prático de Estruturas de dados 2004/5
3-3
Trabalho de Estruturas de Dados 2004/2005
Gestão de contas à ordem
Pormenores sobre a implementação para a 4ª fase
1 Extracto de movimentos de uma conta ordenados por descrição
A ordenação ascendente dos movimentos de cada conta, por descrição, será efectuada através de
uma árvore binária. Será pois ordenação indirecta, isto é a posição dos movimentos na lista não
será alterada, será sim criada uma árvore binária que indica as posições relativas destes movimentos
segundo o critério de ordenação acima indicado.
Instância do
ADT conta
lista
movimentos
Inst. movimento
número == 2
descrição == "D"
...
raiz
Inst. movimento
número == 4
descrição == "A"
...
Inst. movimento
número == 5
descrição == "T"
...
Inst. movimento
número == 10
descrição == "C"
...
(D)
(T)
(A)
(C)
Tal como na lista de movimentos de uma conta, cada nó da árvore terá como item um ponteiro para
uma instância do ADT movimento. Na figura acima, para simplificação mas sem perda de
generalidade, assume-se que a descrição de cada movimento é apenas um caracter.
Nota: As letras a azul no nós da árvore binária não representam dados do nó mas apenas uma
indicação para qual dos movimentos aponta o item do nó.
Assim para cada conta deverá existir uma árvore de ponteiros para os movimentos além da lista de
movimentos. Esta árvore deverá ser actualizada sempre que se adiciona um movimento.
Pormenores de implementação da 4ª fase do trabalho prático de Estruturas de dados 2004/5
1-5
Deste modo quando fôr pedido o extracto ordenado por descrição basta percorrer a árvore e
apresentar todos os movimentos. No entanto ocupa mais memória. Esta implementação requer no
entanto um espaço considerável de memória.
Alternativamente a árvore binária poderá ser criada temporariamente apenas quando se precisa de
mostrar o extracto de conta ordenado por descrição, poupando memória à custa de algum
desempenho. Para isso:
#1 percorrer a lista de movimentos da conta para a qual se pretende visualizar o extracto e
adicionar o ponteiro para o movimento (o item de cada nó da lista) como um item de cada nó
da árvore.
#2 percorrer a árvore segundo um percurso inorder e mostrar os movimentos apontados por
cada item da árvore.
#3 libertar a árvore da memória.
Qualquer das opções é válida mas deve ser justificado no relatório o porquê da escolha.
Podem-se usar as funções para árvores binárias ordenadas apresentadas na aula teórica 22. Um
ficheiro de demonstração destas funções, com o nome btree_ord.c pode ser encontrado em:
http://w3.ualg.pt/~hdaniel/ed/teorica/T22_code/
Uma função semelhante a btree(...) poderá ser utilizada para criar a árvore e uma função
semelhante a btlist(...) para imprimir os extractos.
O critério de ordenação poderá continuará a ser:
Chave do filho esquerdo menor que a chave do pai e
chave do filho direito maior ou igual que a chave do pai.
No entanto a chave é uma string, a descrição do movimento, de modo que pode ser comparada
usando a função:
#include <string.h>
int strcmp(const char *A, const char *B);
Que retorna um número > 0 (zero) quando *A se ordena lexicograficamente após *B,
retorna um número < 0 (zero) quando *A se ordena lexicograficamente antes de *B
e retorna 0 (zero) se as duas strings forem iguais.
Se mov representar um ponteiro para cada instância do ADT movimento, pode-se adicionar uma
função ao ADT movimento, por exemplo:
int MOVless (mov m0, mov m1)
que compara dois movimentos em termos de descrição usando strcmp(...), e retorna 1 caso a
descrição do movimento m0 se ordene lexicograficamente antes da descrição do movimento m1, ou
0 caso contrário.
Pormenores de implementação da 4ª fase do trabalho prático de Estruturas de dados 2004/5
2-5
Esta função poderá agora ser utilizada na função btree(...), onde é necessário determinar qual a
menor chave, isto é nas linhas:
...
if (t < root->item) root->left=r;
=> if (MOVless (t, root-item)) ...
...
if (r < root->item) return btree (r, r->left, t); => if (MOVless (r, root-item)) ...
...
Na função btlist(...) basta alterar a linha que imprime o item para chamar a função que imprime o
movimento, por exemplo:
...
btlist (root->left);
printf( ...
btlist (root->right);
...
=> MOVprint (root->item, stdout);
1.1 Integração na aplicação
No gestor (ou motor da aplicação) ficheiro accman.h está definida a função:
/* Escreve o extracto da conta número n, do gestor de conta m no stream f em modo texto
formatado.
Retorna 1 se a operação teve sucesso ou -2 se a conta número n não existe.
Se mode < 0 ordena os movimentos por data descendentemente
Se mode == 0 ordena os movimentos por descrição ascendentemente
Se mode > 0 ordena os movimentos por data ascendentemente
PRE: m != NULL && f != NULL
Excepção: Se ocorrer erro de escrita retorna 0
*/
int ACCMANtransactions (accountmanager m, int n, int mode, FILE *f);
Como mostra a descrição, esta função deve ser chamada a partir do interface de utilizador amui.c,
com o número de conta da qual se pretende visualizar o extracto e uma variável que indica o tipo de
extracto, mode.
Uma boa opção de implementação será delegar no ADT conta a impressão do extracto, já que este
ADT contém toda a informação necessária para a tarefa:
int ACCMANtransactions (accountmanager m, int n, int mode, FILE *f);
{
account pacc=ACCMANexist (m, n);
if (!pacc) return -2;
return ACCOUNTprint(pacc, f, mode);
};
Pormenores de implementação da 4ª fase do trabalho prático de Estruturas de dados 2004/5
3-5
Assim se a função auxiliar ACCMANexist(m, n), implementada em accman.c, retornar um
ponteiro para a conta com número n, do gestor m, ou NULL se esta não existir, pode-se delegar o
trabalho de escolha do tipo de extracto e sua impressão no stream f na função:
ACCOUNTprint(pacc, f, mode)
do ADT conta, que recebe o ponteiro pacc para a instância da conta, o stream f e o modo de
impressão mode.
Nota: Não é obrigatório que no ADT conta exista uma função que apresente todos os tipos de
extractos. Também é válido existir neste ADT uma função para apresentar cada tipo de extracto.
De qualquer forma, na implementação do interface de utilizador amui.c, para que seja mostrado o
extracto de uma conta a pedido do utilizador, pode-se usar um segmento de código semelhante a:
/* Pedir nºconta e modo de apresentação do extracto (por data ascendente ou por data
descendente ou por descrição ascendente) ao utilizador
*/
n = ACCMANtransaction (ui->m, nºconta, modo, stdout);
/* caso n diferente de 1 imprime mensagem de erro correspondente */
Se a instância do interface de utilizador fôr apontada por ui e o motor (ou gestor) associado a essa
seja apontado por m:
struct AMUIstruct {
accountmanager m;
/* ... */
};
2 Construir a aplicação com interface de utilizador alternativo
O código objecto do interface de utilizador alternativo (amui.o) está disponível para 3
compiladores diferentes, em:
http://w3.ualg.pt/~hdaniel/ed/avaliacao/tpfase4/cygwin
http://w3.ualg.pt/~hdaniel/ed/avaliacao/tpfase4/Dev-C++ (windows)/
http://w3.ualg.pt/~hdaniel/ed/avaliacao/tpfase4/linux-x86/
- Seguindo do o primeiro link enconta-se a versão de amui.o para gcc v3.3.3 em ambiente cygwin.
- Através do segundo link chega-se à versão de amui.o para Dev-C++ v4.9.9.2 (ou v4.9.9.0). Este
ambiente de desenvolvimento de aplicações corre em windows e usa como compilador uma versão
apropriada do gcc.
- Pelo terceiro link têm-se a versão de amui.o para gcc v2.95.4 e superiores sobre Linux (intel x86)
Pormenores de implementação da 4ª fase do trabalho prático de Estruturas de dados 2004/5
4-5
Para construir a aplicação com o interface de utilizador alternativo:
#1 Copiar todo o código fonte, e também o makefile, com excepção de amui.c, para um
novo directório.
#2 Colocar nesse novo directório um dos ficheiros amui.o indicado acima (que seja
apropriado para o compilador e sistema operativo usados)
#3 executar o makefile
Convém lembrar que para que o interface de utilizador alternativo possa ser compilado, os ficheiros
amui.h e accman.h deverão ser os fornecidos na 3ª fase (e não poderão ser alterados!)
Nos três links referidos acima encontram-se também os executáveis da aplicação final para o
sistema operativo e ambiente indicados. Estes demonstram não apenas a operação do interface de
utilizador mas toda a operação esperada da aplicação de gestão de contas.
Dependendo do sistema operativo o nome do executável é contas ou contas.exe.
3 Relatório
Fazer relatório de acordo com o template que será disponibilizado em:
http://w3.ualg.pt/~hdaniel/ed/avaliacao/
Pormenores de implementação da 4ª fase do trabalho prático de Estruturas de dados 2004/5
5-5