INF 1620
–
Estruturas de Dados
–
Semestre 08.2
Trabalho 3: Agenda de Tarefas
O objetivo deste trabalho é a implementação de um conjunto de funções para a
manipulação de uma agenda de tarefas diárias, de forma a permitir a criação de listas de
tarefas associadas a datas específicas, bem como a consulta das tarefas previstas para
uma determinada data ou período, entre outras coisas.
struct agenda
{
struct entrada *p;
};
typedef struct agenda Agenda;
Essa agenda é representada pelo tipo Agenda, definido acima como um ponteiro para
uma lista encadeada em que cada nó é do tipo de dados Entrada, que corresponde a uma
entrada específica no calendário e aponta para uma lista de tarefas previstas para aquela
data. Esse último é definido a partir da estrutura entrada, conforme descrito a seguir:
struct entrada
{
Data d;
Tarefa *t;
struct entrada *p;
};
typedef struct entrada Entrada;
Observe que a estrutura entrada possui os campos d, t e p. O campo d armazena uma
variável do tipo Data (descrito a seguir), que corresponde à data para a qual estão
agendadas as tarefas da lista associada a essa entrada do calendário. O campo t é um
ponteiro para o tipo Tarefa (descrito adiante) que indica a lista de tarefas associada a
essa entrada. O campo p armazena um ponteiro para o próximo nó da lista de entradas.
Essa lista é simplesmente encadeada e mantida em ordem cronológica. O tipo de dados
Data é definido a partir da estrutura data, conforme descrito a seguir:
struct data
{
int dd, mm, aa;
};
typedef struct data Data;
A estrutura data possui os campos dd, mm e aa, inteiros que armazenam o dia, mês e
ano associados a uma entrada na agenda. Cada nó da lista de tarefas, por sua vez, é do
tipo Tarefa, definido a partir da estrutura tarefa, conforme descrito a seguir:
struct tarefa
{
char descr[81];
int tempo;
int prio;
struct tarefa *ant;
struct tarefa *prox;
};
typedef struct tarefa Tarefa;
A estrutura tarefa possui os campos descr, tempo, prio, ant e prox. O campo descr é uma
cadeia de caracteres que contém a descrição da tarefa. O campo tempo é um inteiro que
armazena o tempo de duração de uma tarefa (em minutos). O campo prio é um inteiro
que armazena a prioridade da tarefa, um número de 1 (baixa) a 3 (alta). Os campos ant e
prox armazenam ponteiros para o nó anterior e o próximo da lista de tarefas,
respectivamente. Ou seja, a lista de tarefas é mantida como uma lista duplamente
encadeada.
A lista deve ser mantida ordenada considerando a prioridade e ordem de chegada. Ou
seja, quando uma nova tarefa é introduzida, ela deve ser posicionado na lista após todas
aquelas que têm prioridade igual ou maior a ela. Por outro lado, uma tarefa deve ser
retirada sempre do início da lista. A Figura 1 exemplifica a estrutura descrita.
Agd p
Figura 1: Exemplo da representação de uma agenda de tarefas
Observa-se que Agd, uma variável do tipo agenda, é um ponteiro para uma lista de
variáveis do tipo Entrada, mantida em ordem cronológica. Neste exemplo, esta lista
contém quatro nós, cada um deles apontando para uma lista duplamente encadeada de
variáveis do tipo Tarefa. Cada uma destas listas é tratada como uma fila de prioridades,
de tal forma que uma nova tarefa é posicionada na lista sempre atrás de todas as outras
tarefas que têm prioridade igual ou maior. Por exemplo, na lista apontada pela entrada
de data 18/11/08, uma nova tarefa com prioridade 1 seria inserida no final da lista. Se a
tarefa tivesse prioridade 2, seria inserida na segunda posição da lista (entre “Malhar” e
“Compras”). Com prioridade 3, a tarefa seria inserida no início da lista. Na retirada, é
selecionada sempre a primeira tarefa da lista, respeitando-se o critério de uma fila.
Função
Cria_agenda
Cria_tarefa
Insere_tarefa
Consulta_tarefa
Remove_tarefa
Exibe_dia
Exibe_agenda
Libera_agenda
Descrição
Cria uma agenda vazia.
Aloca dinamicamente uma nova variável do tipo Tarefa,
que posteriormente será inserida na agenda.
Insere na agenda, em uma data fornecida como parâmetro,
uma tarefa previamente criada. Se não existir uma entrada
com a data fornecida na lista de entradas, a entrada deve
ser criada e adicionada na ordem cronológica. Nesse caso,
a tarefa será adicionada como a primeira da lista de tarefas
apontada por essa entrada. Se a entrada já existir, a tarefa
deve ser inserida na lista correspondente depois de todas
as tarefas que têm prioridade maior ou igual a esta. Nesse
caso, a tarefa só poderá ser inserida na lista associada a
esta entrada se, após sua inclusão, o somatório do tempo
de duração de todas as tarefas da lista não ultrapasse 8
horas (480 minutos).
Verifica que tarefa está no início da lista, devolvendo um
ponteiro para uma cadeia de caracteres alocada
dinamicamente que deve receber a descrição da tarefa. Se
a entrada correspondente a essa data não for encontrada,
ou caso sejam fornecidos valores inválidos como
parâmetro, a função deve retornar NULL.
Retira a tarefa que está no início da lista, devolvendo um
ponteiro para esta variável. Se a entrada correspondente a
essa data não for encontrada, ou caso sejam fornecidos
valores inválidos como parâmetro, a função deve retornar
NULL. Se esse nó for o único elemento da lista de tarefas
associada à entrada correspondente, então, após a remoção
da tarefa, esta entrada também deverá ser removida da
lista de entradas e liberada.
Imprime na tela a as tarefas previstas para uma
determinada data, respeitando a ordem da lista. Se a
entrada correspondente a essa data não for encontrada,
deve ser impressa a mensagem “Nenhuma atividade
prevista”. Caso sejam fornecidos valores inválidos como
parâmetros, deve ser impresso “Data invalida”.
Exibe na tela todas as tarefas da agenda em ordem
cronológica, respeitando a ordem da lista para cada
entrada. Se a agenda estiver vazia deve ser impressa a
mensagem “Nenhuma atividade prevista”.
Libera todas as variáveis alocadas dinamicamente.
As funções que devem ser implementadas estão descritas resumidamente na tabela
acima, e detalhadamente --- com seus parâmetros de entrada e valores de retorno ---, no
Anexo 1, que apresenta a interface da biblioteca agendadetarefas.h. O Anexo 2 mostra
exemplos das saídas produzidas pelas funções Exibe_dia e Exibe_agenda.
OBSERVAÇÕES:
1 - A especificação dos tipos de dados e funções que devem ser implementadas estão no
arquivo agendadetarefas.h, que está disponível no site do enunciado do trabalho e cujo
conteúdo não pode ser alterado.
2 – Os alunos deverão implementar e incluir em agendadetarefas.c todas as demais
funções descritas no arquivo agendadetarefas.h.
3 – Mesmo as funções que não forem implementadas devem ser acrescentadas no
arquivo agendadetarefas.c com o corpo vazio ou com um retorno nulo (caso a função
retorne algum valor) para evitar erro de compilação na submissão do trabalho.
4 – A função “main”, fornecida no arquivo Testa_Agenda.c, tem somente a finalidade
de demonstrar a utilização das funções implementadas, executando algumas das ações
descritas no enunciado. Além disso, pode servir também como modelo para a
implementação de testes mais completos.
5 – O arquivo agendadetarefas.c deve ser enviado contendo apenas as funções
implementadas. Ou seja, o seu arquivo submetido NÃO deve possuir a função “main”.
A correção do trabalho será realizada pelo corretor automático, que terá um programa
que chamará as funções conforme declaradas na interface agendadetarefas.h.
6 – Programas que não compilarem receberão nota zero. O programa não pode ser
escrito usando a sintaxe própria de C++ ou funções que não são do padrão de C.
Programas que compilarem serão executados e avaliados numa seqüência de testes.
7- Certamente cada aluno pode discutir com seus colegas (e com seus professores) a
forma de implementação que empregará. Observamos, entretanto, que os trabalhos são
individuais. Trabalhos similares poderão ter suas notas reduzidas, podendo receber nota
zero se o grau de similaridade for muito acentuado.
8 – Data de entrega: 26 de Novembro.
Anexo 1
/********************************************************************/
/*
agendadetarefas.h
*/
/********************************************************************/
/********************************************************************/
/*
*/
/* Funcao Cria_agenda – Cria uma agenda vazia.
*/
/*
*/
/* Nao tem parametros.
*/
/*
*/
/* Saída: Ponteiro para uma Agenda com campo p = NULL.
*/
/*
*/
/********************************************************************/
Agenda* Cria_agenda(void);
/********************************************************************/
/*
*/
/* Funcao Cria_tarefa – Aloca dinamicamente uma nova variavel
*/
/* do tipo Tarefa (que posteriormente sera inserida na agenda)
*/
/* e retorna um ponteiro para a nova variavel.
*/
/*
*/
/* Parametros de Entrada:
*/
/* k – descricao (ponteiro para uma cadeia de caracteres);
*/
/* t – tempo de duracao, em minutos (inteiro > 0);
*/
/* p – prioridade (inteiro de 1 a 3);
*/
/*
*/
/* Saída: Ponteiro para a nova variavel. Se a operacao falhar,
*/
/*
porque nao foi possível alocar espaco na memoria
*/
/*
para mais um no da lista de tarefas, ou porque algum
*/
/*
dos parametros recebeu valor invalido, a funcao deve
*/
/*
retornar NULL.
*/
/*
*/
/*
Obs: No caso de ocorrer alguma das falhas mencionadas,
*/
/*
qualquer variavel dinamica que tenha sido alocada
*/
/*
desnecessariamente deve ser liberada.
*/
/*
*/
/********************************************************************/
Tarefa* Cria_tarefa(char *k, int t, int p);
/********************************************************************/
/*
*/
/* Funcao Insere_tarefa – Insere na agenda uma tarefa previamente */
/* criada. Se nao existir uma entrada com a data indicada para
*/
/* esta tarefa na lista, a entrada deve ser criada e adicionada
*/
/* a lista de tarefas na ordem cronologica. Nesse caso, a nova
*/
/* tarefa sera a primeira da lista de tarefas correspondente.
*/
/* Se a entrada ja existir, a tarefa deve ser inserida na lista
*/
/* correspondente considerando sua prioridades, ou seja,
*/
/* devera ser posicionada depois de todas as tarefas que tem
*/
/* prioridade maior ou igual a esta. Uma tarefa so pode ser
*/
/* inserida na lista associada a uma certa entrada se, apos sua
*/
/* inclusao, o somatorio do tempo de execucao de todas as tarefas */
/* da lista nao for ultrapassar 8 horas (480 miunutos).
*/
/*
*/
/* Parametros de Entrada:
*/
/* p – ponteiro para a agenda;
*/
/* d – dia do agendamento da tarefa (inteiro de 1 a 31);
*/
/* m – mes do agendamento da tarefa (inteiro de 1 a 12);
*/
/* a – ano do agendamento da tarefa (inteiro de 0 a 99);
*/
/* t – ponteiro para a tarefa que deve ser inserida;
*/
/*
*/
/* Saída: Inteiro indicando se a operacao de criacao e insercao
*/
/*
da tarefa foi bem sucedida, de acordo com os seguintes
*/
/*
valores:
*/
/*
0 - operacao bem sucedida;
*/
/*
-1 - operacao falhou porque nao foi possível alocar
*/
/*
espaco na memoria para um no da lista de entradas
*/
/*
da agenda;
*/
/*
1 - operacao falhou porque algum dos parametros
*/
/*
continha valores invalidos;
*/
/*
2 - operacao falhou porque a inclusao desta tarefa iria */
/*
ultrapassar o limite de tempo;
*/
/*
*/
/*
Obs: No caso de ocorrer alguma das falhas mencionadas,
*/
/*
qualquer variavel dinamica que tenha sido alocada
*/
/*
desnecessariamente deve ser liberada
*/
/*
*/
/********************************************************************/
int Insere_tarefa(Agenda *p, int d, int m, int a, Tarefa *t);
/********************************************************************/
/*
*/
/* Funcao Consulta_tarefa – Verifica que tarefa esta no início
*/
/* da lista de tarefas apontada pela entrada correspondente a
*/
/* uma data fornecida. Devolve um ponteiro para uma string
*/
/* alocada dinamicamente que deve receber a descricao desta
*/
/* tarefa. Se a entrada correspondente a essa data nao for
*/
/* encontrada, ou caso sejam fornecidos valores invalidos como
*/
/* parametros, a funcao deve retornar NULL.
*/
/*
*/
/* Parametros de Entrada:
*/
/* p – ponteiro para a agenda;
*/
/* d – dia (inteiro de 1 a 31);
*/
/* m – mes (inteiro de 1 a 12);
*/
/* a – ano (inteiro de 0 a 99);
*/
/*
*/
/* Saída: ponteiro para uma string alocada dinamicamente que deve */
/*
receber a descricao da tarefa que esta no inicio da
*/
/*
lista apontada pela entrada correspondente a data
*/
/*
fornecida como parametro. A funcao deve retornar NULL
*/
/*
se a entrada correspondente a essa data nao for
*/
/*
encontrada, ou caso sejam fornecidos valores invalidos
*/
/*
como parametros.
*/
/*
*/
/*
*/
/********************************************************************/
char* Consulta_tarefa(Agenda *p, int d, int m, int a);
/********************************************************************/
/*
*/
/* Funcao Remove_tarefa – Retira a tarefa que esta no início
*/
/* da lista de tarefas apontada pela entrada correspondente a
*/
/* uma data fornecida, devolvendo um ponteiro para esta
*/
/* variavel. Se a entrada correspondente a essa data nao for
*/
/* encontrada, ou caso sejam fornecidos valores invalidos como
*/
/* parametros, a funcao deve retornar NULL. Se essa tarefa for
*/
/* o único elemento da lista de tarefas associada a essa entrada, */
/* entao a entrada também devera ser removida (e liberada) apos
*/
/* a remocao da tarefa.
*/
/*
*/
/* Parametros de Entrada:
*/
/* p – ponteiro para a agenda;
*/
/* d – dia (inteiro de 1 a 31);
*/
/* m – mes (inteiro de 1 a 12);
*/
/* a – ano (inteiro de 0 a 99);
*/
/*
*/
/* Saída: ponteiro para a tarefa que estava no inicio da lista.
*/
/*
A funcao deve retornar NULL se entrada correspondente
*/
/*
a essa data nao for encontrada, ou caso sejam
*/
/*
fornecidos valores invalidos como parametros.
*/
/*
*/
/********************************************************************/
Tarefa* Remove_tarefa(Agenda *p, int d, int m, int a);
/********************************************************************/
/*
*/
/* Funcao Exibe_dia – Exibe na tela as tarefas previstas para
*/
/* uma data, respeitando a ordem da lista. Se a entrada
*/
/* correspondente a essa data nao for encontrada, deve ser
*/
/* impressa a mensagem 'Nenhuma atividade prevista'. Caso sejam
*/
/* fornecidos valores invalidos como parametro, deve ser impressa */
/* a mensagem 'Data invalida'.
*/
/*
*/
/* Parametros de Entrada:
*/
/* p – ponteiro para a agenda;
*/
/* d – dia (inteiro de 1 a 31);
*/
/* m – mes (inteiro de 1 a 12);
*/
/* a – ano (inteiro de 0 a 99);
*/
/*
*/
/********************************************************************/
void Exibe_dia(Agenda *p, int d, int m, int a);
/********************************************************************/
/*
*/
/* Funcao Exibe_agenda – Exibe na tela todas as tarefas da agenda */
/* em ordem cronologica e respeitando a ordem da lista de tarefas */
/* para tarefas agendadas para a mesma data. Se a agenda estiver
*/
/* vazia deve ser impressa a mensagem 'Nenhuma atividade
*/
/* prevista'.
*/
/*
*/
/* Parametros de Entrada:
*/
/* p – ponteiro para a agenda;
*/
/*
*/
/********************************************************************/
void Exibe_agenda(Agenda *p);
/********************************************************************/
/*
*/
/* Funcao Libera_agenda – Libera todas as variaveis alocadas
*/
/* dinamicamente para armazenar uma agenda, com sua lista de
*/
/* entradas e as respectivas listas de tarefas.
*/
/*
*/
/* Parametros de Entrada:
*/
/* p – ponteiro para a agenda;
*/
/*
*/
/* Saída: Inteiro indicando o numero de tarefas que foram
*/
/*
apagadas, ou:
*/
/*
0 - se agenda estava vazia;
*/
/*
-1 - se a operacao falhou por algum outro motivo;
*/
/*
*/
/********************************************************************/
int Libera_agenda(Agenda *p);
Anexo 2
O quadro abaixo ilustra o formato correto da saída a ser mostrada na tela para a função
Exibe_dia, com parâmetros indicando a data 18/11/08, considerando o mesmo exemplo
apresentado na Figura 1. Observe que a função deve escrever o nome de uma tarefa em
cada linha, obedecendo a ordem da lista de tarefas:
Malhar
Compras
Ler
Considerando a data de 20/11/08, a saída seria:
Correr
Praia
Se a função for chamada com a data de 22/11/08, a saída seria:
Nenhuma atividade prevista
Se a função for chamada com a data fictícia de 22/15/08, a saída seria:
Data invalida
O quadro abaixo ilustra a saída da função Exibe_agenda. Observe que a função deve
escrever o nome de uma tarefa em cada linha, obedecendo a ordem da lista de entradas e
a ordem da lista de tarefas:
Reuniao
Estudar
Cinema
Malhar
Compras
Ler
Correr
Praia