Classificar lista vinculada C ++

Lista vinculada

Uma lista vinculada é uma espécie de estrutura de dados. Os itens dentro da lista vinculada estão conectados usando ponteiros. É uma coleção de nós. Um nó contém duas partes. Um inclui os dados, e a segunda parte consiste no ponteiro. Este ponteiro é usado para armazenar o endereço de memória do elemento do nó adjacente a ele na lista vinculada. A vantagem da lista vinculada de uma matriz é que ela tem um tamanho dinâmico.

Representação de uma lista vinculada

O primeiro nó da lista vinculada é chamado com antecedência. Seu valor é nulo no caso de uma matriz vazia. Em C ++, usamos uma estrutura para representar um nó.

Este é um código C ++ simples da criação de lista vinculada. Criamos uma classe na qual sua parte pública, uma variável de dados do tipo inteiro, é criada com uma variável de tipo de ponteiro 'Next' que armazenará o endereço do nó.

Três nós são criados dentro do programa principal, com o primeiro nó do primeiro nó declarado como o nó 'cabeça'. Todos os três pontos desses nós estão vazios, então eles são declarados como nulos inicialmente. Depois de fazer isso, todos os três nós são alocados em uma pilha. 'cabeça' em segundo e terceiro é atribuído com o novo nó.

Agora atribuiremos dados, e os dados podem ser qualquer valor aleatório. Primeiro, atribuiremos dados no primeiro nó.

Cabeça-> dados = 1;

Esta demonstração de atribuição de dados mostra que a parte de dados do primeiro nó conterá dados. Após atribuir dados, vincularemos o primeiro nó com o segundo

Cabeça-> próximo = segundo;

Nós conectamos a parte do ponteiro 'próximo' com o outro nó para vincular dois nós. Atribuiremos dados armazenados na parte de dados do primeiro nó. Enquanto a parte "próxima" conterá o endereço de memória do nó presente depois dela. Da mesma forma, agora atribuiremos dados ao segundo nó, e o segundo nó estará vinculado ao terceiro nó. Agora adicione dados no terceiro nó. Como criamos apenas três nós, não há outro nó, a próxima parte do terceiro ponteiro será declarada como nula; Isso indica que a lista vinculada é encerrada.

Terceiro-> próximo = nulo;

Exemplo

Classificar lista vinculada

Aqui declaramos uma estrutura representando um nó de uma única lista vinculada. Como descrito acima, o conceito de declaração da lista vinculada, a variável de dados e as variáveis ​​de ponteiro são tomadas na estrutura. Como a parte do ponteiro 'próximo' que armazena o endereço, também declaramos mais duas variáveis ​​do tipo ponteiro: cabeça de nó e cauda de nó. Ambos são declarados inicialmente como nulos.

Como nó de inserção lida com a inserção de dados na lista vinculada, usaremos uma função de adicionar um nó. Os dados também atribuirão este nó. Portanto, o parâmetro desta função conterá dados como argumento. Antes da inserção, o nó será criado com a alocação de memória usando uma função malloc (). A parte dos dados do novo nó será atribuída com os dados aprovados.

NewNode-> dados = dados;

E da mesma forma, a próxima parte é atribuída como nula, pois não há conexão entre este nó com qualquer outro. Como as variáveis ​​de cabeça e cauda são declaradas para ajudar no tipo de inserção. Agora vamos utilizá -los aqui. Primeiro, usando uma declaração if-else, verificaremos se a cabeça é nula, como declaramos como nulo acima, o que significa que toda a lista está vazia. É por isso que a cabeça está vazia, então a cabeça e as variáveis ​​da cauda apontam para o nó recém -criado. Caso contrário, na parte else, se a lista não estiver vazia, suponha que, ao criar a lista, também inserimos dados, então, neste caso, o novo nó será adicionado no último lugar.

Cauda-> próximo = newNode;

E agora, este novo nó atuará como uma nova história.

Cauda = newNode;

Para uma adição adicional, o mesmo processo continua, mas precisamos classificar a lista vinculada. Por isso, adicionamos um único nó que atua como um nó temporário para armazenar dados temporariamente.

Depois de adicionar o novo nó, usaremos uma função para classificar/ organizar a lista. Como o tipo de classificação não é mencionado aqui, por padrão, a lista será classificada em ordem crescente.

Voltando ao exemplo, outro ponteiro atual aponta para a cabeça, como declaramos acima. Isso é usado para classificar os itens da lista. Outra variável do tipo ponteiro será usada aqui e depois declarada como nula. Mais uso estará no programa mais tarde.

Aqui, aplicaremos um cheque para identificar se o ponteiro da cabeça está na posição nula e depois retornará ao programa principal. Caso contrário, aplicaremos a lógica aqui que seguirá um loop de tempo. O ponteiro do índice apontará para a próxima parte do nó atual. Dentro disso, durante o loop, outro enquanto o loop é usado, e isso também durará até que o nó atual não seja nulo. Aqui, usaremos uma estatura IF para verificar se os dados no nó atual são maiores que os dados dentro do nó do índice, os dados entre eles são trocados.

A variável temp desempenhará um papel importante aqui na troca de dados. Primeiro, os dados do nó atual são transferidos para a temperatura e, em seguida, o nó atual está agora vazio. Este nó receberá o valor dos dados do índice. E no final, o nó de índice vazio é atribuído pelos dados presentes na variável temp.

Fora da declaração IF, o nó do índice também é incrementado com o novo valor de um índice. Da mesma forma, fora do loop while, o nó atual também é atribuído pelo novo valor.

Em seguida, usamos uma função de exibição aqui para exibir o valor de todos os nós. O ponteiro atual apontará para a cabeça. Em outro caso, um pouco o loop exibe todos os valores até que o nó atual não seja nulo.

Agora considere o programa principal, a função de addNode () é chamada com os valores para adicionar novos valores dentro da lista. Em seguida, a função de exibição exibirá todos os valores inseridos antes de classificar. Em seguida, chame a função Sort (). E, novamente, chame a função de exibição para exibir toda a lista classificada.

Salve o arquivo de código e execute -o no terminal Ubuntu com a ajuda de um compilador G ++.

$ g ++ -o arquivo de arquivo.c

$./arquivo

A partir do valor resultante, você pode observar que os valores são organizados em ordem crescente à medida que foram inseridos aleatoriamente na lista vinculada.

Conclusão

'Lista vinculada de classificação C ++' contém a descrição do conhecimento básico sobre a lista vinculada e sua criação. Um código de amostra é suficiente para demonstrar a criação de nós e o funcionamento de todos os nós na lista vinculada. Os elementos dentro da lista vinculada são organizados em ordem crescente usando um processo detalhado adicionando novos nós e depois classificando uma variável temporária. Explicação com o código é feita para ajudar o usuário.