Pessoal de ADS. Por esses dias estarei colocando no blog algumas noções de programação, como lista encadeada, alocação dinâmica, verificação de código com GDB, entre outras… Isso porque estou notando uma queda de rendimento de vocês em sala principalmente quando envolve programação. Vamos lá!
Normalmente para realizarmos a representação de um grupo de dados, utilizamos a forma mais simples para tal que é a dada através do uso de um vetor. Ao declararmos um vetor estamos reservando um espaço de memória unido e em sequência, para armazenarmos seus elementos. Em um vetor, acessamos seus elementos indexando o ponteiro para seu primeiro elemento.
#define TAMANHO 10
int vetor[TAMANHO];
Ao realizarmos a declaração acima, estamos a partir do endereço de memória FF04, inclusive com este, alocando um total de 10 espaços em memória para que dados do tipo inteiro possam ser gravados nestes.
Desta forma, vetor é o endereço da memória onde o primeiro elemento do vetor está armazenado. De forma análoga poderíamos escrever a mesma situação como &vetor[0].
Apesar de extremamente útil em várias situações, o uso de vetores apresenta como grande desvantagem o fato deste não ser uma estrutura flexível, haja vista que necessitamos dimensioná-lo com um número máximo de elementos. Seu redimensionamento em tempo de execução não é simples e pode requer um recurso computacional mais elevado. Com isso, ao utilizarmos um vetor, corremos o risco da necessidade de cresce-lo além do previsto durante a execução do programa ou então termos super dimensionado o problema e ficarmos com espaço alocado para o mesmo sem que estes sejam utilizados.
Ao fazermos uso portanto de estruturas dinâmicas, como estas alocam seus elementos usando alocação dinâmica de memória, temos esta situação resolvida.
Listas Encadeadas
Listas encadeadas são estruturas flexíveis onde a cada novo elemento inserido na estrutura é alocado um espaço de memória para que seja processado seu armazenamento. Listas encadeadas, devido ao uso do mecanismo de alocação dinâmica, terão sempre o espaço de memória utilizado variando de acordo com seu número de elementos.
Uma lista encadeada é uma coleção de nós, que armazenam dados, e de ligações com outros nós. Os nós podem estar localizados agora em qualquer lugar na memória, e a passagem de um nó para o outro se dará através do armazenamento dos endereços de outros nós.
Na lista encadeada cada nó conterá um ou mais campos responsáveis pelo armazenamento das informações, além de um campo que é um ponteiro para uma próxima estrutura do mesmo tipo.
struct noh {
int mat;
struct noh *prox;
};
typedef struct noh lista;
De forma a fornecer um facilitador na compreensão das listas, trabalharemos com o conceito de lista com cabeça, ou seja, teremos sempre o conteúdo do primeiro nó irrelevante. Este servirá apenas para marcar o início da lista, não se alterará, e quando estiver apontando para null, indicará que a lista está vazia.
struct noh {
int mat;
struct noh *prox;
};
typedef struct noh lista;
lista *inicio;
inicio =(lista*) malloc (sizeof (lista));
inicio->prox = NULL;Função para inicialização
A função para inicialização de uma lista deve criar o nó inicial da lista mas também, no momento de sua criação verificar se há espaço livre na memória para a efetivação do processo.
Iniciaremos neste momento através dos exemplos dados a construção de um primeiro programa modelo, para tratamento de listas, o qual fará uso de variáveis globais de forma a eliminar a necessidade no momento de passagem de parâmetros às funções. Um outro exemplo será dado no decorrer de nossas aulas utilizando estes recursos.
struct noh {
int mat;
char *nome;
char sexo[1];
struct noh *prox;
};
typedef struct noh lista;
char onome[256];
lista *inicio=NULL;
lista *atual=NULL;
lista *anterior=NULL;
void inicializa(){
inicio =(lista*) malloc (sizeof (lista));
if (!inicio){
printf(“\nNao existe espaco na memoria!”);
exit(1);
}
inicio->prox = NULL;
}Função para inserção
A partir do momento que temos nossa lista inicializada, podemos proceder com a inserção de novos elementos nesta. Lembrando que para cada novo elemento adicionado estaremos alocando um novo espaço de memória para este.
Podemos realizar a inserção em qualquer lugar da lista, entretanto, a maneira mais simples de execução desta tarefa é dada com a inserção do novo elemento no início da lista. Sendo assim o novo elemento entrará logo após nosso marcador de início da lista.
O mais importante aqui é realizar sempre sua programação de maneira defensiva e com o máximo de cuidado nos detalhes de modo a não cometer falhas de direcionamento de próximos nós.
Vejamos como ficaria nossa função de inserção.
void insere(){
lista *novo=NULL;
novo = (lista*) malloc (sizeof (lista));
if (!novo){
printf("\nNao existe espaco na memoria!");
exit(1);
}
printf("\nDigite a matricula: ");
scanf("%d",&novo->mat);
printf("\nDigite o nome: ");
scanf("%s",onome);
novo->nome = (char*) malloc (strlen(onome)+1);
strcpy(novo->nome,onome);
fflush(stdin);
printf("\nDigite o sexo: ");
scanf("%s",novo->sexo);
fflush(stdin);
if (inicio->prox == NULL){
inicio->prox = novo;
novo->prox = NULL;
}else{
novo->prox = inicio->prox;
inicio->prox = novo;
}
}Função para impressão
Nossa função de impressão terá uma tarefa bem simples a ser realizada. Seu papel será de a partir do marcador de início da lista, percorrer toda esta, e imprimir as informações gravadas em seus campos. Antes de ler a solução proposta abaixo para nosso estudo, tente criar a função de impressão como um primeiro exercício de nossa disciplina.
Dica: Não se esqueça de verificar antes de tudo se alista não está vazia. Ao realizar a impressão a mesma deve ocorrer, pela lógica proposta acima, na ordem inversa a da entrada dos dados.
void imprime(){
if (inicio->prox==NULL)
printf("\nFila vazia!\n");
else{
atual=inicio;
do{
atual=atual->prox;
printf("\n\nMatricula: %d",atual->mat);
printf("\nNome: %s",atual->nome);
printf("\nSexo: %s",atual->sexo);
} while (atual->prox!=NULL);
}
}Função para busca sequencial
Para verificarmos se um determinado elemento encontra-se presente em nossa lista, utilizaremos aqui de uma busca sequencial. Em nosso exemplo como citado anteriormente estamos trabalhando neste primeiro momento com variáveis globais e com as funções sem passagem de parâmetros. Entretanto, adiante estaremos reescrevendo a mesma recebendo como parâmetros um ponteiro para lista e uma informação que necessitamos pesquisar. Vamos ao nosso exemplo:
void busca(){
int matbusca,encontrou=0;
printf("\n\nDigite a matricula para busca: ");
scanf("%d",&matbusca);
if (inicio->prox==NULL)
printf("\nFila vazia! Busca nao pode ser processada!\n");
else{
for (atual=inicio->prox; atual!=NULL; atual=atual->prox){
if (matbusca==atual->mat){
printf("\n\nMatricula: %d",atual->mat);
printf("\nNome: %s",atual->nome);
printf("\nSexo: %s",atual->sexo);
encontrou=1;
}
if (atual->prox==NULL && encontrou==0)
printf("\nRegistro nao encontrado!\n");
}
}
}Função para excluir um elemento da lista
Implementaremos agora a função responsável por localizar e excluir um elemento da lista. Novamente é importante estar atento a detalhes como:
– lista está vazia?
– o elemento a ser excluído não é o primeiro da lista?
A função para remover um elemento da lista é um pouco mais complexa já que devemos guardar o elemento anterior ao procurado e fazer com que este aponte após a exclusão do elemento identificado para o posterior a ele, de forma a manter de maneira correta o encadeamento de nossa lista.
Vamos ao nosso código!
void exclui(){
int matbusca,encontrou=0;
printf("\n\nDigite a matricula para exclusao: ");
scanf("%d",&matbusca);
if (inicio->prox==NULL)
printf("\nFila vazia! Busca para exclusao nao pode ser processada!\n");
else{
anterior = inicio;
for (atual=inicio->prox; atual!=NULL; atual=atual->prox){
if (matbusca==atual->mat){
anterior->prox = atual->prox;
free(atual);
encontrou=1;
}
if (encontrou == 1)
break;
anterior=atual;
if (atual->prox==NULL && encontrou==0)
printf("\nRegistro para exclusao nao encontrado!\n");
}
}
}Observações finais sobre listas encadeadas
Tivemos a oportunidade de iniciar nosso estudo sobre listas através das listas de encadeamento simples. Notamos que pelo fato de não possuirmos o apontador para elementos anteriores, nosso caminhar pela lista fica prejudicado e necessitamos de soluções nada elegantes para a resolução de problemas como uma exclusão de um elemento no meio da lista.
Partiremos no próximo estudo para o tratamento das listas duplamente encadeadas, o que nos permitirá controlar de maneira eficiente este caminhar, nos inserindo nos tópicos de filas e pilhas.
Quando fazemos uso de linguagens de programação que possuem coletores de lixo de memória, não nos é necessário desalocar o espaço de memória utilizado. Entretanto a linguagem C não possui este mecanismo e liberar a memória utilizada é algo essencial. Fazemos isso através do comando free().