Olha, já vou avisando que está resposta será imensa, pois o programa é grande,
Então vamos começar.
As bibliotecas usadas são as seguintes:
#include <stdio.h> /* adiciona as funções de input e output */
#include <stdlib.h> /* Alocação dinâmica, rand e srand */
#include <time.h> /* Para usar com o srand */
#include <locale.h> /* para poder usar acentos brasileiros */
Agora mostrarei como foi feita a estrutura usada, esta foi uma lista dinâmica, duplamente encadeada, o porque explicarei mais à frente.
/** informações do veiculo */
typedef struct informacao
{
int velocidade, numRegistro, tempo; /* velocidade dele, numero único de registro do automóvel
e o tempo que ele permanecerá no anel */
short faixa; /* faixa em que ele está */
}info;
/** elementos da lista */
struct elementos
{
struct informacao dados; /* dados dos veículos */
struct elementos* prox,* ant; /* os apontamentos para os próximos e anteriores da lista */
};
/** nó discritor */
struct noDiscritor
{
struct elementos* pInicio,* pFinal; /* apontamento para o inicio da lista e para o final */
unsigned long qtd, MAX; /* quantidade de elementos que a lista possui e quantidade máxima que
ela pode possuir */
};
/* apenas typedefs para facilitar a manipulação das mesmas */
typedef struct elementos elem;
typedef struct noDiscritor lista;
Como pode ver esta é a nossa lista, com todos os dados que foram propostos no exercício.
Agora vamos para a primeira pergunta.
a) Que tipo de estrutura de dados (lista, fila, pilha, árvore, ...)
você usaria para resolver este problema? Que tipo de implementação
esta estrutura de dados deveria ter (por vetor, por nós alocados
dinamicamente, ...)? Justifique sua resposta.
R: Eu acredito que seja lista, pois apesar de em uma pista carros se comportarem como uma fila ainda assim há ultrapassagens, ou seja, eles não respeitam a lei primaria de uma fila que é FIFO (First In First Out), assim uma lista seria a melhor opção pois desta forma se tem uma manipulação melhor dos dados.
Pensado desta forma eu fiz o exercício lista dinâmica duplamente encadeada, mas por que?
- Primeiro, uma lista dinâmica facilita o uso, pois ela não é limitada igual a linear (estática), apesar de ter posto uma quantidade máxima para ela, esta é facilmente alterada uma vez que faz parte da própria lista, assim caso a rua tenha um ganho de capacidade máxima o programa seria facilmente atualizado, apenas fazendo uma função para aumentar ou diminuir a capacidade máxima da lista.
- Segundo, é utilizado duplo encadeamento pois assim facilita a manipulação da lista, tornando mais fácil de se programar com ela.
- Terceiro, é usado nó descritivo pois isto facilita ainda mais a manipulação da lista, desta forma você tem controles com, a quantidade de elementos que ela possui, a quantidade máxima que ela suporta, um apontamento para o inicio e final, isto ajuda em muito a manipulação dela.
b) Programe esta estrutura de dados criando funções para inserir um
veículo, remover um veículo, verificar se a estrutura de dados está
vazia ou cheia, procurar um veículo, alterar velocidade de um veículo,
alterar faixa do veículo.
Antes de começar a responder esta pergunta de fato teremos que fazer umas funções básicas antes, estas são, criaLista, liberaLista e criaNO, pois para podermos inserir na lista, remover e etc, necessitamos cria-la, então vamos lá.
criaLista, esta será a função encarregada de criar a lista, para faze-la é necessário passar a lista por referencia, também passar o tamanho máximo que a lista deverá suportar, lembrando também de retornar, -1 caso tenha erro de alocação e 1 caso a criação seja um sucesso, também devemos fazer com que os apontamentos de inicio e final apontem para NULL, e que o tamanho seja iniciado em 0, eu deixarei claro aqui que existem varias formas de se fazer a função cria lista, e está é a que eu prefiro e acho certa okay, então vamos lá, a função ficará da seguinte maneira.
short criaLista ( lista** li, unsigned long MAX ) /* note que a lista é passada como ** de lista
isto se deve a passagem por referência */
{
*li = (lista*)malloc(sizeof(lista)); /* aloca a lista*/
if ( !li ) /* verifica se a lista foi alocada corretamente, caso contrario retorna -1 */
return -1;
(*li)->pInicio = NULL; /* seta os apontamentos para NULL */
(*li)->pFinal = NULL;
(*li)->qtd = 0; /* inicia o qtd em 0 */
(*li)->MAX = MAX; /* inicia o max no valor passado pelos parâmetros */
return 1; /* retorna 1 pois a alocação foi um sucesso */
}
Agora iremos para o próximo, liberaLista, esta é a função encarregada de deletar tudo o que está na lista, inclusive a própria, está função deve retornar -1 caso a lista seja inexistente e um caso excito em liberar a lista, para fazer a liberação, basta fazer um loop que vai liberando todos elementos da lista, até que não tenha mais nada para liberar, quando isto ocorrer libere a lista em si, desta forma o código fica da seguinte maneira.
short liberaLista ( lista* li )
{
elem* no; /* cria nó auxiliar, para poder andar pela lista e ir liberando, assim não perde
o apontamento para o inicio da lista */
if ( !li ) /* verifica se a lista existe */
return -1;
while ( (li->pInicio) != NULL ) /* enquanto houver elemento na lista, remova os elementos */
{
no = li->pInicio; /* utiliza o ó para não perder o apontamento da lista */
li->pInicio = li->pInicio->prox; /* atribua a próxima posição da lista ao inicio */
free(no); /* remova antigo inicio */
}
free(li); /* remove lista */
return 1; /* retorna 1 a liberação foi um sucesso */
}
A função criaNO é bem simples, basta você passar os dados a serem inseridos nele e o nó por referência nos parâmetros, alocar o no, iniciar os apontamentos em NULL e atribuir os dados passados à nó, a função ficará assim.
short criaNo ( elem** no, info dado )
{
*no = (elem*)malloc(sizeof(elem)); /* aloca o nó */
if ( !no ) /* verifica se não houve erro ao alocar. */
return 0; /* retorna 0 caso falha */
(*no)->dados = dado; /* atribui os dados passados ao nó */
(*no)->prox = NULL; /* seta os apontamentos em NULL. */
(*no)->ant = NULL;
return 1; /* retorna 1 caso sucesso */
}
Agora finalmente iremos começar a responder a pergunta b, iniciaremos ela com as funções de checagem de lista cheia e vazia, pois esta serão usadas mais à frente nas funções de inserção e remoção.
listaVazi, esta função verificará se a lista está ou não vazia, para faze-la basta verificar se a lista é existente, caso não seja retorne -1, caso seja verifique se a lista esta cheia ou não utilizando o marcado de quantidade da lista, retorne 0 caso a lista não seja vazia e 1 caso contrario.
short listaVazia ( lista* li )
{
if ( !li ) /* verifica se a lista existe */
return -1;
return (li->qtd == 0); /* retorna um 1 caso seja vazia, ou 0 caso o oposto */
}
listaCheia, esta é incumbida de verificar se a lista está cheia, funciona da mesma maneira que a anterior, apenas troque o 0 pela variável max da lista, a função ficara de tal maneira.
short listaCheia ( lista* li )
{
if ( !li )
return -1;
return (li->qtd == li->MAX);
}
Existem varias formas de se inserir em uma lista, no final, inicio e meio, o meio seria muito útil na hora de fazer as ultrapassagens, mas como no exercício não foi pedido isso, e como veículos na rua se comportam muito parecido com uma fila, iremos implementar somente o insereListaFinal, que cuidará de inserir nossos dados no final da lista, lembrando que veículos se comportam de modo FIFO.
Esta terá que verificar se a lista existe, se ela não esta cheia, e por fim caso passe desses dois inserir no final da lista, então a função ficara da seguinte forma.
short insereListaFinal ( lista* li, info dado ) /* passa a lista que deseja a inserção, e o dado a ser inserido. */
{
elem* no; /* no auxiliar para poder inserir na lista */
short bol = criaNo(&no, dado); /* função que cria o nó */
if ( (!li) || (!bol) ) /* verifica se a lista e o nó é existentes */
return -1;
if ( listaCheia(li) ) /* verifica se a lista está cheia */
return 0;
no->ant = li->pFinal; /* seta o apontamento do anterior do nó no final da lista */
if( listaVazia(li) ) /* caso a lista seja vazia o final e o inicio irão apontar para nó */
li->pInicio = no;
else
li->pFinal->prox = no; /* caso contrario o antigo final apontará para nó */
li->pFinal = no; /* nó vira o novo final */
++li->qtd; /* atualiza a quantidade de elementos da lista */
return 1;
}
Da mesma forma que a anterior iremos pensar um pouco em filas aqui, então faremos o removeListaIncio, pois o primeiro carro a entrar será o primeiro a sair caso não haja ultrapassagens, mas de novo eu ressalto aqui, o exercício não pediu para fazer isso, não não focaremos nisso por agora.
Para fazer a função removeListaInicio é muito fácil, basta lembrar de fazer as verificações, mudar os apontamentos, do antigo inicio para o novo que será o próximo ao inicio, e lembrar de atualizar a quantidade, então vamos lá para a função.
short removeInicio ( lista* li )
{
elem* no; /* cria o nó que ira auxiliar a liberar o dado desejado */
if ( !li ) /* verifica se lista existe */
return -1;
if ( listaVazia(li) ) /* verifica se a lista não esta vazia */
return 0;
no = li->pInicio; /* aponta o no ao inicio da lista */
if ( li->qtd == 1 ) /* caso tenha apenas um elemento, a lista se tornará vazia. */
{
li->pFinal = NULL; /* mudando o apontamento para NULL */
li->pInicio = NULL;
}
else
{
li->pInicio = li->pInicio->prox; /* caso contrario, atualize a apontamento para o novo inicio */
li->pInicio->ant = NULL; /* atualize o apontamento do novo inicio, desvinculando-o do anterior */
}
--li->qtd; /* atualize a quantidade de elementos */
free(no); /* libere o antigo inicio */
return 1;
}
Agora basta apenas três, se você chegou até aqui e entendeu tudo, você já é um campeão, então o próximo será o consulta, o nome da função é consultaListaCont, pois ele faz a consulta da lista pelo conteúdo, este no caso é o numRegistro, então para fazermos esta função basta passar a lista, o numero de registro do veiculo, e a variável que receberá a consulta, além desta consulta também temos uma muito similar que é a consultaListaPos, que consulta a lista por meio de uma posição dada, implementaremos a segunda, pois usaremos na questão C, na hora de fazer tudo aleatório, assim facilitará para a gente usar o consulta, o consultaListaPos funciona do mesmo jeito que o consultaListaCont só muda que usará uma posição e não um numero de registro, então vamos lá, a função ficará dessa maneira.
short consultaListaPos ( lista* li, unsigned long pos, info* dado ) /* passe a lista por parâmetro, a posição que
deseja consultar e onde ira receber o dado */
{
elem* no; /* no auxiliar, para percorrer a lista, assim não perde o apontamento para o inicio */
register unsigned long i; /* contador */
if ( !li ) /* checa se a lista existe */
return -1;
if ( (listaVazia(li)) || (pos <= 0) || (pos > li->qtd) ) /* chega se a lista esta vazia, ou, posição é 0 ou inferior
ou se posição é maior que a quantidade de elementos da lista */
return 0;
for ( i = 1, no = li->pInicio; (i != pos) && (no != NULL); ++i, no = no->prox ); /* encontra a posição do dado */
if ( no == NULL ) /* verifica se a posição era de fato existente */
return 0;
*dado = no->dados; /* atribuir ao dado, o dado da lista */
return 1;
}
Ambos o altera faixa e altera velocidade funcionam literalmente da mesma maneira, então explicando um explico os dois, tipo como foi com o consulta, mas vamos lá, você passará a lista por parâmetro junto com o numero de registro do veiculo e com o novo valor da faixa, faça as verificações se a lista existe, se esta vazia, após isso verifica se o inicio ou o final não batem com o numero de registro passado, caso contrario use um loop para encontrar o dado, não se esqueça de usar um nó para isso, porque se não você perderá o apontamento para o inicio, no momento que encontrar o dado atribua o valor da faixa passado por parâmetro ao da lista, a função ficará assim.
short alteraFaixa ( lista* li, int numRegistro, short faixa )
{
elem* no; /* nó auxiliar, para percorrer a lista */
if ( !li ) /* verifica se a lista existe */
return -1;
if ( listaVazia(li) ) /* verifica se a mesma não é vazia */
return 0;
if ( li->pInicio->dados.numRegistro == numRegistro ) /* se for igual o numRegisto, atribua o novo valor */
{
li->pInicio->dados.faixa = faixa;
return 1;
}
if ( li->pFinal->dados.numRegistro == numRegistro ) /* similar ao anterior */
{
li->pFinal->dados.faixa = faixa;
return 1;
}
if ( (no = li->pInicio->prox) == NULL ) /* aponta o nó ao próximo e checa se a lista não contém somente um elemento */
return 0;
while ( (no != li->pFinal) && (no->dados.numRegistro != numRegistro) ) /* encontra o veiculo */
no = no->prox;
if ( no == li->pFinal ) /* checa se foi encontrado mesmo de fato */
return 0;
no->dados.faixa = faixa; /* atribui o novo valor faixa */
return 1;
}
Como dito anteriormente o alteraVelocidade é igual a função anterior, então colocarei direto o código sem explicações e comentários.
short alteraVelocidade(lista* li, int numRegistro, int velocidade)
{
elem* no;
if ( !li )
return -1;
if ( listaVazia(li) )
return 0;
if ( li->pInicio->dados.numRegistro == numRegistro )
{
li->pInicio->dados.velocidade = velocidade;
return 1;
}
if ( li->pFinal->dados.numRegistro == numRegistro )
{
li->pFinal->dados.velocidade = velocidade;
return 1;
}
if ( (no = li->pInicio->prox) == NULL )
return 0;
while ( (no != li->pFinal) && (no->dados.numRegistro != numRegistro) )
no = no->prox;
if ( no == li->pFinal )
return 0;
no->dados.velocidade = velocidade;
return 1;
}
c) Teste sua estrutura de dados inserindo pelo menos 10 veículos
inicialmente e fazendo um loop de repetição no qual os veículos vão
sendo inseridos, removidos, alterando de faixa, aleatoriamente.
Antes de começar a questão c é importante fazer mais uma função para nos auxiliar, esta é a função imprimeConteudo, para faze-la é bem simples, basta percorrer a lista e ir imprimindo tudo o que há nela, mas não se esqueça das verificações hein, como a função é bem simples colocarei direto sem comentários.
short imprimeConteudo ( lista* li )
{
elem* no;
register unsigned long i;
setlocale(LC_ALL, ""); /* comando da locale.h para poder ter acentos */
if ( !li )
return -1;
if ( listaVazia(li) )
return 0;
printf("\n\t##### ...Começando a imprimir... #####\n");
for ( no = li->pInicio, i = 1; no != NULL; no = no->prox, ++i )
printf("\n%luº Carro:"
"\nfaixa: %hi"
"\nvelocidade: %3i km/h"
"\nnumero de registro: %6i."
"\ntempo que permanecerá: %3i min"
"\n ----------\n", i, no->dados.faixa, no->dados.velocidade, no->dados.numRegistro, no->dados.tempo);
printf("\n\t##### ...Termino da impreção... #####\n");
return 1;
}
Vamos fazer o main agora, com os testes aleatórios que o exercício pediu, lembrando que usaremos o srand ( time(NULL) )
desta forma, pois assim as seed que geram a suposta aleatoriedade é sempre mudada fazendo ser uma função aleatória de fato, então agora fica bem fácil, só desenvolver o main, e lembrar de usar a função rand()
, para ter a aleatoriedade.
É importante lembrar que certos números tem limites, por exemplo o tempo, seria sem noção alguém ficar em um anel por tipo 999999 minutos certo, então para colocar um limite no rand()
basta colocar o operador de mod, assim ele nunca passará do limite que virar após do mod, desta forma sempre quando ele chegar ou ultrapassar este limite ele ira zerar, para evitar zeros não desejados basta somar com 1 depois, ficando da seguinte maneira rand() % limite + 1
ou rand() % limite
, caso não tenha problema em ter zeros, lembrando que o limite pode ser qualquer valor.
Então vamos para a função main.
int main ()
{
lista* li;
info veiculo;
register int i, j, op;
int tam = 10;
long max = 100, qtd = 10;
short bol;
setlocale(LC_ALL, ""); /* adiciona os acentos brasileiros */
srand( time(NULL) ); /* cria seeds diferentes toda vez que é executado o programa */
criaLista(&li, max); /* cria a lista */
for ( i = 0; i < 10; ++i ) /* cria os 10 primeiros elementos aleatórios */
{
veiculo.faixa = rand() % 2 + 1; /* faixa só pode ser 1 ou 2, desta maneira ele escolherá aleatoriamente um dos dois*/
veiculo.numRegistro = rand() % 999999 + 1; /* numero de registro */
veiculo.velocidade = rand() % 200; /* velocidade, eu sei que 200 km\h é um pouco de mais, mas é só para testar*/
veiculo.tempo = rand() % 120 + 1; /* tempo do veiculo, ele ficara no maximo 2 horas, mas pode mudar o limite caso queira*/
insereListaFinal(li, veiculo); /* isere o veiculo na lista */
}
printf("Antes da simulação:");
imprimeConteudo(li);/* imprimirá para a gente checar no console */
op = rand() % 4 + 1; /* na primeira vez op não pode ser 0 por isso o + 1 */
while (op != 0) /* ficara escolhendo as funções leatóriamente, até que op seja 0 */
{
switch ( op ) /* escolherá aleatóriamente a função */
{
case 1:
tam = rand() % tam + 1;
for ( i = 0; i < tam; ++i, --qtd )
{
bol = removeInicio(li);
if ( bol != 1 )
break;
}
if (qtd < 0) /* checa se o for não foi executado mais uma vez após chegar em lista vaiza, caso chegue*/
qtd = 0; /* caso sim atribui zero a qtd */
break;
case 2:
tam = rand() % max + 1;
for ( i = 0; i < tam; ++i, ++qtd)
{
veiculo.faixa = rand() % 2 + 1;
veiculo.numRegistro = rand() % 999999 + 1;
veiculo.velocidade = rand() % 200;
veiculo.tempo = rand() % 120 + 1;
bol = insereListaFinal(li, veiculo);
if ( bol != 1 )
break;
}
if (qtd > max) /* checa se não foi tentado introduzir uma elemento a mais caso a lista esta cheia*/
qtd = max; /* caso sim, diminui o valor de qtd para o max*/
break;
case 3:
tam = rand() % qtd + 1;
for ( j = 0; j < tam; ++j )
{
i = rand() % qtd + 1;
consultaListaPos(li, (unsigned long)(i), &veiculo); /* casting do i para evitar erros */
alteraVelocidade(li, veiculo.numRegistro, rand() % 200);
}
break;
case 4:
tam = rand() % qtd + 1;
for ( j = 0; j < tam; ++j )
{
i = rand() % qtd + 1;
consultaListaPos(li, (unsigned long)(i), &veiculo); /* casting do i para evitar erros */
alteraFaixa(li, veiculo.numRegistro, rand() % 2 + 1);
}
break;
}
op = rand() % 5; /* limete 5, ou seja, poderá conter valores de 0 a 4 */
}
printf("\nDepois da simulação:");
imprimeConteudo(li); /* imprime a lista para nós vermos o resultado final */
liberaLista(li); /* libera a lista */
return 0;
}
Finalmente terminado, espero ter ajudado ;), como pode ter visto é muita coisa para explicar, por isso tiver que fazer bem resumido, então sugiro que você procure seu professor para ajuda-lo caso tenha dificuldade pois para explicar tanta coisa assim eu acredito que a melhor maneira é em uma aula ao vivo, ou em vídeo aulas e livros, então para ajuda-lo deixarei aqui um link de un site que me ajudou muito quando estava fazendo estrutura de dados.
Programação descomplicada