Versao mais eficiente do algoritmo de ordenacao topologica.A diferenca para o algoritmo do post anterior e a introducao da fila de saida. Ela permite que, ao detectarmos uma tarefa cujos pre-requisitos ja foram cumpridos, esta ja seja inserida na fila de saida./*** MAC 2301 - Laboratorio de Programacao** Exercicio da aula 3** Assunto: Lista ligada e fila* Aplicacao: ordenacao topologica em tempo linear** Programa que executa a mesma tarefa do da aula anterior mas mais rapidamente* A unica modificacao e a introducao da fila de saida***/#include #include #define MAX 100struct cel{ int chave; /* conteudo */ struct cel *prox; /* ponteiro para o proximo elemento */} ;/* Para nao termos que digitar struct cel toda hora, definimos: */typedef struct cel celula;/* Insercao no comeco de uma lista com cabeca */void insereNaLista (int x, celula *lista){ celula *nova; nova = malloc (sizeof (celula)); nova->chave = x; nova->prox = lista->prox; lista->prox = nova;}/* Funcao de remocao. Remove a lista inteira. */void removeLista(celula *lista){ celula *temp; if(lista != NULL) { temp = lista->prox; while(temp != NULL) { lista->prox = temp->prox; free(temp); temp = lista->prox; } free(lista); }}void inicializaLista(celula ** ptrLista) /* com cabeca */{ *ptrLista = malloc(sizeof(celula)); (*ptrLista)->prox = NULL; (*ptrLista)->chave = -1;}/* usada apenas para depuracao */void imprimeLista(celula *lista){ celula *varre = lista->prox; printf("\n Conteudo da lista: \n"); while(varre != NULL) { printf(" %d ", varre->chave); varre = varre->prox; } printf("\n-----\n\n");}/* Precisaremos de uma fila.* Vamos implementa-la usando lista ligada com cabeca */void insereNaFila (int x, celula * fila){ if(fila != NULL) { celula *nova = malloc(sizeof(celula)); nova->chave = x; /* esta implementacao insere no comeco e retira do fim */ nova->prox = fila->prox; fila->prox = nova; }}/* Recebe a fila e devolve a chave do primeiro da fila* Se a fila estiver vazia, devolve -1* Possui efeito colateral!! Remove o elemento da fila */int proximoDaFila (celula * fila){ int valorDeDevolucao; celula *anterior; celula *percorre; anterior = fila; percorre = fila->prox; while(percorre != NULL) { if(percorre->prox == NULL) { anterior->prox = NULL; valorDeDevolucao = percorre->chave; free(percorre); return valorDeDevolucao; } anterior = percorre; percorre = percorre->prox; } return -1;}int main(){ int i; /* contador */ celula *sucessores[MAX]; /* vetor com as listas (no livro e o CB)*/ int antecessores[MAX]; /* vetor que guarda em [i] o numero de antecessores pendentes da tarefa i */ celula *filaDeSaida; /* a saida de fato e a impressao na tela, mas usaremos esta fila para guardar as tarefas que ja podem ser executadas (i.e, que tem nenhum predecessor) antes de imprimirmos */ int quantidadeDePares; int quantidadeDeTarefas; /* variaveis temporarias */ int umaTarefa, outraTarefa; /* usadas na leitura */ /* usada para percorrer listas */ celula *varreSucessores; int valorDoProxDaFila; printf("\n Ordenacao topologica\n --------------------\n\n"); /* vamos agora ler os dados e preencher o vetor de listas */ printf("\n Digite a quantidade de tarefas a serem executadas: "); scanf("%d", &quantidadeDeTarefas); printf("\n Digite a quantidade de dependencias entre as elas: "); scanf("%d", &quantidadeDePares); /* inicializando os dois vetores */ for(i = 0; i < quantidadeDeTarefas; i++) { inicializaLista(&(sucessores[i])); antecessores[i] = 0; } inicializaLista(&filaDeSaida); /* lendo dimensoes do problema */ printf("\n Digite os pares