Programar em C/Listas encadeadas: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Nova página: Listas encadeadas são estruturas de dados lineares e dinâmicas, a grande vantagem que elas possuem em relação ao uso de vetor é o fato de terem tamanho máximo relativamente infin… |
(Sem diferenças)
|
Revisão das 22h59min de 24 de fevereiro de 2009
Listas encadeadas são estruturas de dados lineares e dinâmicas, a grande vantagem que elas possuem em relação ao uso de vetor é o fato de terem tamanho máximo relativamente infinito (o tamanho máximo é o da memória do computador), ao mesmo tempo que podem ter o tamanho mínimo de 1 elemento evitando o despedício de memória.
Struct
Cada nó de uma lista encadeada irá possuir guardar o valor do nó e o endereço do próximo nó.
struct No{
char *pString;
struct No *pProx;
};
Iniciar uma lista
A função abaixo demonstra como iniciar uma lista criando o espaço da raiz na memória.
void criarLista(struct No **pRaiz){
*pRaiz = NULL;
}
Inserção
Existem 2 tipos de inserção numa lista, pode-se inserir no começo ou no final da lista.
Inserção no início
void inserirNoInicio(struct No **pRaiz, char *pString){
struct No *pNovo;
pNovo = (struct No *) malloc(sizeof(struct No));
pNovo->pString = pString;
if(*pRaiz == NULL){
*pRaiz = pNovo;
pNovo->pProx = NULL;
}else{
pNovo->pProx = *pRaiz;
*pRaiz = pNovo;
}
}
Inserção no fim
void inserirNoFim(struct No **pRaiz, char *pString){
struct No *pNovo;
pNovo = (struct No *) malloc(sizeof(struct No));
pNovo->pString = pString;
pNovo->pProx = NULL;
if(*pRaiz == NULL){
*pRaiz = pNovo;
}else{
struct No *pAux;
pAux = *pRaiz;
while(pAux->pProx != NULL){
pAux = pAux->pProx;
}
pAux->pProx = pNovo;
}
}
Remoção
Assim como na inserção também existem 2 tipos de remoção, no início e no fim da lista.
Remoção no inicio
void removerNoInicio(struct No **pRaiz){
if(*pRaiz == NULL) printf("\nA lista ja esta vazia");
else{
struct No *pAux;
pAux = *pRaiz;
*pRaiz = (*pRaiz)->pProx;
free(pAux);
}
}
Remoção no fim
void removerNoFim(struct No **pRaiz){
if(*pRaiz == NULL) printf("\nA lista ja esta vazia");
else{
struct No *pAuxFrente, *pAuxTras;
pAuxFrente = *pRaiz;
while(pAuxFrente->pProx != NULL){
pAuxTras = pAuxFrente;
pAuxFrente = pAuxFrente->pProx;
}
pAuxTras->pProx = NULL;
free(pAuxFrente);
}
}