Look, I'm already warning you that it's a big answer, because the program is big,
Then let's start.The libraries used are as follows:#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 */
Now I'll show you how the structure was made, this was a dynamic, double-locked list, why I'll explain it further ahead./** 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;
As you can see this is our list, with all the data that were proposed in the exercise.Now we go to the first question.a) What kind of data structure (list, queue, pile, tree, ...)
would you use to solve this problem? What type of implementation
this data structure should have (by vector, by us allocated
dynamically, ...)? Justify your answer.A: I believe it's a list, because although on a track cars behave like a queue there are still overtakings, that is, they do not respect the primary law of a queue that is FIFO (First In First Out), so a list would be the best option because in this way it has a better manipulation of the data.Thought in this way I did the dually bound dynamic list exercise, but why?First, a dynamic list makes it easy to use, as it is not limited equal to linear (static), although it has put a maximum amount to it, this is easily changed since it is part of the list itself, so if the street has a maximum capacity gain the program would be easily updated, just doing a function to increase or decrease the maximum capacity of the list.Second, it is used double chaining as this makes it easier to manipulate the list, making it easier to program with it.Third, it is used descriptive node as this further facilitates the manipulation of the list, in this way you have controls with, the amount of elements it possesses, the maximum amount it supports, a point to the beginning and end, this greatly helps the manipulation of it.(b) Program this data structure by creating functions to insert a
vehicle, remove a vehicle, check if the data structure is
empty or full, search for a vehicle, change speed of a vehicle,
change vehicle range.Before you start answering this question in fact we will have to do some basic functions before, these are, createList, liberalList and puppy, because in order to be able to insert in the list, remove and etc, we need to create it, so let's go there.createsLista, this will be the function in charge of creating the list, to make it it is necessary to pass the list by reference, also to pass the maximum size that the list should bear, also remembering to return, -1 if it has allocation error and 1 if the creation is a success, we must also make the initial and final points point to NULL, and that the size is started in 0, I will make it clear here that there are I I prefer it and I think it's okay, so let's go, the function will the next way.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 */
}
Now we will go to the next, liberaLista, this is the function in charge of deleting all that is in the list, including the own, is function must return -1 if the list is nonexistent and an excite case in releasing the list, to make the release, just make a loop that will release all elements of the list, until you have nothing else to release, when this occurs release the list itself, so the code is as follows.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 */
}
The function creates NO is quite simple, just pass the data to be inserted into it and the node by reference in the parameters, allocate the no, start the notes in NULL and assign the data passed to the node, the function will look like this.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 */
}
Now we will finally begin to answer the question b, we will start it with the full and empty list check functions, as this will be used further in the insertion and removal functions.listVazi, this function will check whether or not the list is empty, to make it just check if the list is existing, if it is not return -1, if it is check whether the list is full or not using the list quantity mark, return 0 if the list is not empty and 1 case otherwise.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 */
}
Cheia list, this is required to check if the list is full, it works the same way as the previous one, just change the 0 by the max variable of the list, the function stays in such a way.short listaCheia ( lista* li )
{
if ( !li )
return -1;
return (li->qtd == li->MAX);
}
There are several ways to insert yourself in a list, at the end, beginning and a half, the medium would be very useful at the time of making the overtakings, but as in the exercise it was not requested, and as vehicles in the street behave very much like a queue, we will only implement the insertFinal List, which will take care of inserting our data at the end of the list, remembering that vehicles behave in FIFO mode.This will have to check if the list exists, if it is not full, and finally if you pass these two insert at the end of the list, then the function will be as follows.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;
}
As the previous one we will think a little in queues here, so we will do the removeListaIncio, because the first car to enter will be the first to go out if there are no overdrives, but again I stress here, the exercise did not ask to do this, we will not focus on it for now.To make the function removeListaInicio is very easy, just remember to do the checks, change the notes, from the old start to the new that will be the next to the start, and remember to update the quantity, then we go there to the function.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;
}
Now it is enough only three, if you have arrived here and understood everything, you are already a champion, then the next will be the query, the name of the function is queryListaCont, because it makes the query of the list by the content, this in the case is theRegister, so to make this function simply pass the list, the number of registration of the vehicle, and the variable that will receive the query, besides this consultation we also have a very similar Pos works the same way that the ListaCont query only changes that it will use a position and not a registration number, so come on, the function will be that way.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;
}
Both the track changes and speed works literally in the same way, so explaining an explain the two, as it was with the query, but let's go there, you will pass the list by parameter along with the record number of the vehicle and with the new value of the track, make the checks if the list exists, if this empty, after that checks whether the beginning or the end do not hit with forgetting the given record number, if you find a nodeshort 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;
}
As said earlier, it changes Speed equals the previous function, so I will put the code straight without explanations and comments.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) Test your data structure by inserting at least 10 vehicles
initially and making a repeat loop in which the vehicles go
being inserted, removed, changing track, randomly.Before starting the question c it is important to do one more function to assist us, this is the function printedConteudo, to make it is very simple, just go through the list and go printing everything there in it, but do not forget about the hein checks, as the function is very simple I will put straight without comments.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;
}
We will make the main now, with the random tests that the exercise asked, remembering that we will use the srand ( time(NULL) ) in this way, because so the seeds that generate the supposed randomness is always changed making it a random function in fact, so now it is quite easy, just develop the main, and remember to use the function rand()to have the randomness.It is important to remember that certain numbers have limits, for example time, would be without notion someone staying in a ring by type 999999 minutes right, so to put a limit on the rand() just put the mod operator, so it will never pass from the limit that turn after the mod, this way always when it arrives or exceeds this limit it will zear, to avoid unwanted zeros just add with 1 then, staying as follows rand() % limite + 1 or rand() % limite, if you have no problem having zeros, remembering that the limit can be any value.So let's go to the main function.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;
}
Finally finished, I hope I have helped ;), as you may have seen it is a lot to explain, so I have to do well summarized, so I suggest you look for your teacher to help you if you have difficulty because to explain so much so I believe that the best way is in a live class, or in video lessons and books, so to help you leave here a link of a site that helped me a lot when I was doing data structure. https://programacaodescomplicada.wordpress.com/indice/estrutura-de-dados/