lab 4 incopleto

Prévia do material em texto

INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DE SÃO PAULO 
DEPARTAMENTO INFORMÁTICA 
CURSO BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO 
 
DISCIPLINA: Laboratório de Estrutura de Dados 
 
 
 
 
 
 
 
 
 
 
 
LAB 4 - LISTAS CIRCULARES 
 
 
 
 
 
 
 
 
 
Aluno: Victor Precoma 
Prof. Fabio Modesto 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
SALTO, 2023. 
 
1. INTRODUÇÂO 
 
As estruturas de dados desempenham um papel fundamental no 
desenvolvimento de algoritmos eficientes e na manipulação de dados. Uma 
estrutura de dados comumente utilizada é a lista circular. Ao contrário das listas 
lineares tradicionais, nas quais o último elemento aponta para NULL, as listas 
circulares têm uma conexão adicional, fazendo com que o último elemento se 
conecte ao primeiro, formando um ciclo contínuo. 
 
Essa característica distintiva das listas circulares proporciona vantagens 
significativas em termos de manipulação e gerenciamento dos dados. As 
operações realizadas em uma lista circular são mais eficientes, já que não há 
necessidade de percorrer toda a lista para alcançar o final. Além disso, a 
natureza circular permite iterações contínuas e acesso flexível aos elementos 
da lista. 
 
As listas circulares são amplamente utilizadas em diversas áreas da ciência da 
computação e engenharia. Elas são especialmente úteis em situações em que 
a ordem dos elementos é importante e deve ser mantida em um loop infinito. 
Além disso, as listas circulares são aplicadas em problemas que envolvem 
agendamento de tarefas, simulação de eventos, gerenciamento de buffers, 
implementação de algoritmos de busca circular, entre outros. 
 
Neste relatório, exploraremos os conceitos fundamentais das listas circulares, 
suas propriedades e operações básicas. Também discutiremos exemplos 
práticos de aplicação para ilustrar como essa estrutura de dados pode ser 
utilizada de maneira eficaz e eficiente. 
 
 
 
2 CONTEÚDO 
 
Para esse programa foi utilizado a linguagem C e suas bibliotecas padrões 
(stdio.h e stdlib.h), foi utilizado as funções para alocação dinâmica como malloc 
e free. 
As funções criadas foram: IniciaLista, InsertNode, printLista e freeLista. O 
funcionamento de cada uma será descrito no procedimento experimental. 
 
 
 
3 METODOLOGIA EXPERIMENTAL 
 
 
3.2 Procedimento Experimental 
 
#include <stdio.h> 
#include <stdlib.h> 
 
typedef struct Node { 
 int data; 
 struct Node* next; 
} Node; 
 
typedef struct CircularList { 
 Node* head; 
 Node* tail; 
} CircularList; 
 
void IniciaLista(CircularList* list) { 
 list->head = NULL; 
 list->tail = NULL; 
} 
 
void insertNode(CircularList* list, int data) { 
 Node* newNode = (Node*)malloc(sizeof(Node)); 
 newNode->data = data; 
 
 if (list->head == NULL) { 
 newNode->next = newNode; 
 list->head = newNode; 
 list->tail = newNode; 
 } else { 
 newNode->next = list->head; 
 list->tail->next = newNode; 
 list->tail = newNode; 
 } 
} 
 
void printLista(CircularList* list) { 
 if (list->head == NULL) { 
 printf("A lista circular está vazia.\n"); 
 return; 
 } 
 
 Node* current = list->head; 
 do { 
 printf("%d ", current->data); 
 current = current->next; 
 } while (current != list->head); 
 printf("\n"); 
} 
 
void freeLista(CircularList* list) { 
 if (list->head == NULL) { 
 
 return; 
 } 
 
 Node* current = list->head; 
 Node* temp; 
 
 while (current != list->tail) { 
 temp = current; 
 current = current->next; 
 free(temp); 
 } 
 
 free(list->tail); 
 list->head = NULL; 
 list->tail = NULL; 
} 
 
int main() { 
 CircularList list; 
 IniciaLista(&list); 
 
 insertNode(&list, 1); 
 insertNode(&list, 2); 
 insertNode(&list, 3); 
 insertNode(&list, 4); 
 
 printf("Lista circular: "); 
 printLista(&list); 
 
 freeLista(&list); 
 
 return 0; 
} 
 
O código fornecido implementa uma lista circular em C e demonstra seu 
funcionamento por meio de algumas operações básicas. 
 
As estruturas Node e CircularList são definidas para representar um nó 
individual na lista circular e a lista em si, respectivamente. 
 
A função IniciaLista é responsável por inicializar a lista circular. Ela define os 
ponteiros head e tail como NULL, indicando que a lista está vazia. 
 
A função insertNode insere um novo nó na lista circular. Ela recebe um valor 
data como parâmetro, cria um novo nó dinamicamente usando malloc e atribui 
o valor data ao campo data do novo nó. 
 
Se a lista estiver vazia (ou seja, list->head == NULL), o novo nó se torna o 
único nó na lista. O ponteiro next do novo nó é configurado para apontar para 
ele mesmo, indicando que é o único nó na lista circular. Os ponteiros head e tail 
são atualizados para apontar para o novo nó. 
 
Se a lista já contiver nós, o novo nó é inserido no final da lista. O ponteiro next 
do novo nó é configurado para apontar para o primeiro nó (list->head). O 
ponteiro next do nó anterior ao final da lista (list->tail->next) é atualizado para 
 
apontar para o novo nó. Por fim, o ponteiro tail é atualizado para apontar para o 
novo nó. 
 
A função printLista é usada para imprimir os valores dos nós na lista circular. 
Ela começa verificando se a lista está vazia (list->head == NULL). Se estiver 
vazia, imprime uma mensagem indicando que a lista está vazia. Caso contrário, 
ela percorre a lista a partir do nó head, imprimindo o valor do nó atual e 
avançando para o próximo nó (current = current->next). O loop continua até 
que o próximo nó seja igual ao nó head, indicando que todos os nós foram 
percorridos. 
 
A função freeLista é usada para liberar a memória alocada para os nós da lista 
circular. Ela começa verificando se a lista está vazia (list->head == NULL). Se 
estiver vazia, a função retorna. Caso contrário, a função percorre a lista a partir 
do nó head, liberando a memória alocada para cada nó. Por fim, ela libera a 
memória do nó tail, redefine head e tail como NULL, indicando que a lista está 
vazia. 
 
Na função main, uma lista circular é criada chamando IniciaLista(&list). Em 
seguida, alguns nós são inseridos na lista usando a função insertNode(&list, 
data). Neste exemplo, são inseridos quatro nós com valores 1, 2, 3 e 4. 
 
Em seguida, a função printLista é chamada para imprimir os valores da lista 
circular. 
 
Por fim, a função freeLista é chamada para liberar a memória. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4 RESULTADOS E DISCUSSÂO 
 
4.1 Entrada de Dados 
 
É criado 4 nós com os valores 1, 2, 3 e 4. 
 
 
 
4.2 Saída de Dados 
 
 
 
4.3 Memória 
 
Apenas a struct CircularList esta alocada na Stack, pois é apenas uma struct 
de base para criar a lista. Todo o restante da lista é alocado dinamicamente, 
portanto é utilizado o heap.