UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO UNIVERSITÁRIO NORTE DO ESPÍRITO SANTO
Disciplina: Estrutura de Dados I
Professor: Renato E. N. de Moraes
Aluno:
Turma: 3EC/4CC Data: 23/09/15
Semestre: 2015-2
Valor: 0,00
Lista de Exercı́cios 04
Nota:
(04.26) Considere uma lista encadeada que representa um conjunto de alunos. O tipo que representa cada nó da lista é dado por:
struct lista {
int mat; /* número de matrı́cula */
char nome[81]; /* nome do aluno */
struct lista* prox; /* ponteiro para próximo elemento */
};
typedef struct lista Lista;
Assumindo que os elementos da lista estejam ordenados (ordem crescente) pelo número de
matrı́cula, escreva uma função que insira um novo aluno na lista. Esse novo aluno deve ser
inserido de forma que a ordenação da lista seja mantida. A função deve receber como parâmetro
o ponteiro para o primeiro nó da lista e os dados do novo aluno (número de matrı́cula e nome),
e deve ter como valor de retorno o ponteiro para o primeiro nó da lista após a inserção. O
protótipo dessa função é dado por: Lista* insere (Lista* l, int m, char* n);
(04.27) Considere uma lista encadeada que armazena as notas de um conjunto de alunos. Os
tipos dos dados são apresentados abaixo:
struct aluno {
char nome[81]; /* nome do aluno */
char mat[11]; /* matrı́cula do aluno */
float nota; /* nota do aluno */
};
typedef struct aluno Aluno;
struct no {
Aluno info;
struct no *prox;
};
typedef struct no No;
Escreva uma função que imprima o nome e a matrı́cula do aluno que tem a maior nota. A função
recebe como parâmetro o ponteiro para o primeiro nó da lista e tem o seguinte protótipo: void
imprime (No* prim);
(04.28) Considere uma fila dupla de valores reais que usa um vetor para armazenar seus elementos. O tipo que representa a fila é dado abaixo, onde ini indica o ı́ndice do vetor onde o
elemento do inı́cio da fila está armazenado e fim indica o ı́ndice imediatamente após o último
elemento da fila.
#define N 50
struct fila {
int ini, fim;
float vet[N];
};
typedef struct fila Fila;
Centro Universitário Norte do Espı́rito Santo
Rodovia BR 101 Norte, Km 60, Bairro Litorâneo, CEP: 29.932-540, São Mateus – ES
Tel.: +55 (27) 3312.1511, Fax.: +55 (27) 3312.1510
Sı́tio eletrônico: http://www.ceunes.ufes.br/
UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO UNIVERSITÁRIO NORTE DO ESPÍRITO SANTO
Considerando a utilização de incremento e decremento circulares, pede-se:
(a) Escreva a função que retira um elemento do inı́cio da fila. float retira_ini (Fila* f);
(b) Escreva a função que retira um elemento do fim da fila. float retira_fim (Fila* f);
Notas: (a) Ambas as funções devem ter como valor de retorno o valor do elemento retirado da
fila; (b) Deve-se considerar que a fila nunca estará vazia quando da chamada de uma dessas
funções.
(04.29) Considere a implementação de uma pilha para armazenar valores inteiros implementada
com o uso de lista encadeada. O tipo que representa a pilha é dado por:
struct no {
int info;
struct no* prox;
};
typedef struct no No;
struct pilha {
No* prim; /* aponta para o topo da pilha */
};
typedef struct pilha Pilha;
Escreva uma função que troque o valor do topo com o valor imediatamente “abaixo” do topo.
O resultado dessa operação é ilustrado na figura. Essa função deve ter o seguinte protótipo:
Pilha* troca_topo (Pilha* p);
Nota: Considera-se que nunca haverá menos do que dois elementos na pilha.
(04.30) Considere a existência de um tipo abstrato Pilha de números reais, cuja interface é
definida pelo arquivo pilha.h com o seguinte conteúdo:
typedef struct pilha Pilha;
Pilha* cria (void); /* cria uma pilha vazia */
void push (Pilha* p, float v); /* insere um elemento no topo */
float pop (Pilha* p); /* retira o elemento do topo */
int vazia (Pilha* p); /* retorna se está vazia */
void libera (Pilha* p); /* libera a pilha */
Sem conhecer a representação interna deste tipo abstrato e usando apenas as funções declaradas
no arquivo pilha.h, implemente uma função que imprima os valores dos elementos armazenados
numa pilha dada. Os elementos devem ser impressos da base para o topo, isto é, o elemento do
topo deve ser o último a ser impresso. Ao final da função, a pilha deve ter o mesmo conteúdo
original. Esta função deve obedecer o seguinte protótipo: void imprime (Pilha* p);
Dica: use uma pilha auxiliar para transferir os valores da pilha original ou faça uma implementação recursiva.
(04.31) Considere uma lista encadeada que represente um conjunto de alunos matriculados em
disciplinas de um determinado curso. Cada elemento da lista contém um código alfanumérico
Centro Universitário Norte do Espı́rito Santo
Rodovia BR 101 Norte, Km 60, Bairro Litorâneo, CEP: 29.932-540, São Mateus – ES
Tel.: +55 (27) 3312.1511, Fax.: +55 (27) 3312.1510
Sı́tio eletrônico: http://www.ceunes.ufes.br/
UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO UNIVERSITÁRIO NORTE DO ESPÍRITO SANTO
da disciplina, o nome do aluno e a nota obtida pelo aluno na disciplina. O tipo que representa
o nó da lista é dado por:
struct lista {
char cod[8]; /* código da disciplina */
char nome[81]; /* nome do aluno */
float nota; /* nota do aluno na disciplina */
struct lista* prox; /* ponteiro para próximo elemento */
};
typedef struct lista Lista;
Escreva uma função que, dado o código de uma disciplina, tenha como valor de retorno a média
das notas obtidas pelos alunos nessa disciplina. Se na lista não existir alunos na disciplina
dada, a função deve ter zero como valor de retorno. O protótipo dessa função é dado por:
float media (Lista* l, char* cod);
(04.32) Considere a existência de um tipo abstrato Pilha de números reais, cuja interface é
definida pelo arquivo pilha.h com o seguinte conteúdo:
typedef struct pilha Pilha;
Pilha* cria (void); /* cria uma pilha vazia */
void push (Pilha* p, float v); /* insere um elemento no topo */
float pop (Pilha* p); /* retira o elemento do topo */
int vazia (Pilha* p); /* retorna se está vazia */
void libera (Pilha* p); /* libera a pilha */
Sem conhecer a representação interna deste tipo abstrato e usando apenas as funções declaradas
no arquivo pilha.h , implemente uma função que retorne o número de elementos armazenados
numa pilha dada. Ao final da função, a pilha deve ter o mesmo conteúdo original. Esta função
deve obedecer ao seguinte protótipo: int num_elem (Pilha* p);
Dica: use uma pilha auxiliar para transferir os valores da pilha original ou faça uma implementação recursiva.
(04.33) Considere a existência de um tipo abstrato Fila de números reais, cuja interface é
definida pelo arquivo fila.h com o seguinte conteúdo:
typedef struct fila Fila;
Fila* cria (void); /* cria uma fila vazia */
void insere (Fila* f, float v); /* insere um elemento */
float retira (Fila * f); /* retira um elemento */
int vazia (Fila * f); /* retorna se está vazia */
void libera (Fila * f); /* libera a estrutura */
Sem conhecer a representação interna deste tipo abstrato e usando apenas as funções declaradas
no arquivo fila.h, implemente uma função que, dada uma fila, inverta a ordem de seus elementos. Por exemplo, se a fila originalmente tiver seus elementos na ordem 4.8, 3.2, 9.8, 3.3, após a
chamada da sua função a fila deve ter seus elementos na ordem 3.3, 9.8, 3.2, 4.8. O protótipo da
função deve ser: void inverte (Fila* f);
Dica: use uma pilha auxiliar para inverter os valores da fila ou faça uma implementação recursiva. Para usar uma pilha auxiliar, considere as operações de pilha definidas na questão
anterior.
(04.34) Considere a implementação de uma lista encadeada para armazenar um cadastro de
alunos. O tipo que representa a lista é dado a seguir:
struct lista {
int mat;
char nome[81];
char email[41];
struct lista *prox;
Centro Universitário Norte do Espı́rito Santo
Rodovia BR 101 Norte, Km 60, Bairro Litorâneo, CEP: 29.932-540, São Mateus – ES
Tel.: +55 (27) 3312.1511, Fax.: +55 (27) 3312.1510
Sı́tio eletrônico: http://www.ceunes.ufes.br/
UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
CENTRO UNIVERSITÁRIO NORTE DO ESPÍRITO SANTO
};
typedef struct lista Lista;
Escreva uma função que, dados o ponteiro para o primeiro elemento da lista e um número
de matrı́cula, retire o aluno correspondente da lista. A função deve retornar 1 se o aluno for
retirado com sucesso e retornar 0 se o número de matrı́cula fornecido não for encontrado na
lista. A função deve obedecer ao protótipo: int retira (Lista* l, int mat);
(04.35) O sistema de controle de fila de um banco opera da seguinte forma. O cliente que chega
à agência retira uma senha que pode ter prioridade preferencial (para gestantes, portadores de
necessidades especiais e maiores de 65 anos) ou não preferencial. A agência dispõe de um caixa
preferencial e diversos caixas não preferenciais. Ao decidir qual o próximo cliente a ser atendido,
são consideradas duas polı́ticas:
i. O caixa preferencial seleciona o primeiro cliente preferencial da fila. Não havendo clientes
preferenciais, é selecionado o primeiro cliente da fila;
ii. O caixa não preferencial respeita a ordem de chegada e seleciona sempre o primeiro cliente
que está aguardando na fila, preferencial ou não.
Para armazenar as informações da fila, o sistema utiliza uma lista duplamente encadeada, em
que cada nó é do tipo Cliente, definido a partir da estrutura cliente, descrita a seguir:
struct cliente {
int senha;
char prio;
struct cliente *ant, *prox;
};
typedef struct cliente Cliente;
Nessa estrutura, o campo senha guarda o número da senha atribuı́da a um cliente, o campo
prio é um caractere que pode ter os valores ’P’ ou ’N’, indicando que o cliente é preferencial
ou não preferencial, e os campos ant e prox apontam para os nós anterior e próximo da lista,
respectivamente.
(a) Escreva uma função em C que receba como parâmetros o ponteiro lst para a lista de clientes, o inteiro senha e o caractere prio. Os dois últimos valores são usados para preencher
os campos senha e prio de uma variável Cliente que deve ser alocada dinamicamente e
inserida no final da lista. A função, que deve retornar o ponteiro para o inı́cio da lista
atualizado.
(b) Escreva uma função em C que receba como parâmetros o ponteiro lst para a lista de
clientes e o caractere prt — que tem o valor ’P’ para indicar que a seleção deve ser feita
para um caixa preferencial, ou ’N’, para um caixa não preferencial — e retorne a senha do
cliente selecionado para atendimento, segundo as polı́ticas apresentadas. Ou seja, se prt =
’P’ a função deve retornar o primeiro cliente com campo prio = ’P’ encontrado, ou, se não
houver nenhum, o primeiro cliente da lista. Se prt = ’N’ a função deve retornar o primeiro
cliente da lista. O respectivo nó deve ser retirado da lista e liberado. Se a lista estiver vazia
a função deve retornar -1.
Centro Universitário Norte do Espı́rito Santo
Rodovia BR 101 Norte, Km 60, Bairro Litorâneo, CEP: 29.932-540, São Mateus – ES
Tel.: +55 (27) 3312.1511, Fax.: +55 (27) 3312.1510
Sı́tio eletrônico: http://www.ceunes.ufes.br/