1. Prefácio
Recentemente, ao revisar estruturas e algoritmos de dados, alguns problemas de algoritmo usam a idéia de pilhas e, quando se trata de pilhas, precisamos falar sobre listas vinculadas. Matrizes e listas vinculadas são a base das estruturas de armazenamento linear, e pilhas e filas são aplicações de estruturas de armazenamento linear ~
Este artigo explica principalmente os pontos básicos de conhecimento das listas de reticulação e faz uma introdução simples. Se houver algum erro, corrija -o.
2. Revisão e conhecimento
Falando em listas vinculadas, vamos primeiro mencionar a matriz. Compará -los com as matrizes faz com que você entenda muito bem a estrutura de armazenamento das listas vinculadas.
2.1 Revise a matriz
Aprendemos matrizes em C e Java:
Vantagens das matrizes:
Desvantagens das matrizes:
2.2 Descrição da lista de links
Depois de ler a matriz, volte para a nossa lista vinculada:
Os n nós são discretamente alocados e conectados entre si por meio de ponteiros. Cada nó possui apenas um nó antecessor, cada nó possui apenas um nó subsequente, o primeiro nó não possui um nó antecessor e o nó da cauda não possui um nó subsequente.
Vantagens da lista vinculada:
Desvantagens das listas vinculadas:
Vou explicar os termos relacionados à lista vinculada através da imagem acima:
Para determinar uma lista vinculada, precisamos apenas de um ponteiro da cabeça, e toda a lista vinculada pode ser deduzida através do ponteiro da cabeça ~
Existem várias categorias de listas vinculadas:
1. Tabela de link unidirecional
2. Tabela de link bidirecional
3. Lista de links de reciclagem
O que você precisa lembrar ao operar uma lista vinculada é:
O campo de ponteiro no nó aponta para um nó!
3. Lista de links de implementação Java
algoritmo:
Primeiro, definimos uma classe como um nó
Para a conveniência da operação, eu a defini diretamente como pública.
public class Node {// Data Data Public Int Data; // Domínio de ponteiro, apontando para o próximo nó nó público a seguir; public Node () {} public node (int dados) {this.data = data; } public node (int data, nó a seguir) {this.data = data; this.Next = Next; }} 3.1 Crie uma lista vinculada (Adicionar nós)
Insira dados na lista vinculada:
/*** Adicione dados à lista vinculada** @param value dados a serem adicionados*/public static void addData (int vale) {// inicialize o nó a ser adicionado newNode = new Node (value); // temp de nó temporário = head; // Encontre o nó da cauda enquanto (temp.next! = Null) {temp = temp.next; } // O caso em que o nó da cabeça.next é nulo foi incluído ~ temp.Next = newNode; } 3.2 Travessando a lista vinculada
Escrevemos o método de adição acima e agora passaremos por ele para ver se está correto ~~~
Comece no primeiro nó e continue pesquisando para trás até que não haja dados no nó subsequente:
/ *** Atravessando a lista vinculada** @param Head Head Node*/ public static void Traverse (cabeça do nó) {// Nó temporário, inicie a partir do primeiro nó temp = head.next; while (temp! = null) {System.out.println ("Siga a conta oficial java3y:" + temp.data); // continua com o próximo temp = temp.next; }}resultado:
3.3 Insira o nó
/*** Inserir nó** @param Head Pointer* @param Índice Posição a ser inserida* @param valor do valor a ser inserido*/public estático void insertNode (cabeça do nó, int index, int valor) {// primeiro de tudo, você precisa determinar se a posição especificada é legal if (Índice <1 | ilegal. "); retornar; } // nó temporário, inicie a partir do início do nó temp = head; // Clique na posição atual do traversal int currentpos = 0; // inicialize o nó a ser inserido no nó insertNode = new Node (valor); while (temp.next! = null) {// A localização do nó anterior foi encontrada se ((índice - 1) == currentpos) {// temp representa o nó anterior // apontar o ponteiro original do nó anterior para o nó inserido para insertNode.next = temp.next; // apontar o campo ponteiro do nó anterior para o nó a ser inserido temp.next = insertNode; retornar; } currentpos ++; temp = temp.next; }} 3.4 Obtenha o comprimento da lista vinculada
É muito simples obter o comprimento da lista vinculada. Isso pode ser feito atravessando -o e obtendo +1 para cada nó ~
/ *** Obtenha o comprimento da lista vinculada* @param cabeça de cabeça ponteiro*/ public static int linkListLength (cabeça do nó) {int length = 0; // nó temporário, inicie a partir do primeiro nó temp = head.next; // Encontre o nó da cauda enquanto (temp! = Null) {comprimento ++; temp = temp.next; } comprimento de retorno; } 3.5 Excluir nós
A exclusão de um nó em um determinado local é realmente muito semelhante ao nó de inserção e você também precisa encontrar o nó anterior. Altere o campo de ponteiro do nó anterior e você pode excluí -lo ~
/** * Exclua nós de acordo com a localização * * @param Head Pointer * @param índice O local a ser excluído */public static void deletenode (cabeça do nó, int index) {// Primeiro de tudo, você precisa determinar se o local especificado é legal, se (índice <1 | retornar; } // nó temporário, inicie a partir do início do nó temp = head; // A localização atual da travessal de registro é int currentPos = 0; while (temp.next! = null) {// A localização do nó anterior é encontrada se ((índice - 1) == currentpos) {// temp representa o nó anterior // temp.next representa o nó que você deseja excluir // armazenar o nó que deseja deletar node deltenode = temp.next; // O próximo nó que você deseja excluir o nó é entregue ao nó anterior para controlar temp.next = deletenode.next; // java irá reciclá -lo, e não deve fazer muito sentido defini -lo como nulo (eu pessoalmente acho, se não estiver correto, aponte -o ~) deletenode = null; retornar; } currentpos ++; temp = temp.next; }} 3.6 Classificar a lista vinculada
Eu já falei sobre 8 algoritmos de classificação [resumo de oito algoritmos de classificação]. Vou escolher uma simples classificação de bolhas desta vez (na verdade, quero escrever um tipo rápido, mas parece um pouco difícil experimentá -lo ...)
/ ** * Classifique a lista vinculada * * @param head * */ public static void SortLinkList (cabeça do nó) {node currentNode; Nó nextNode; para (currentNode = head.next; currentNode.Next! = null; currentNode = currentNode.Next) {for (nextNode = head.next; nextNode.next! nextNode.data = nextnode.next.data; nextNode.Next.Data = temp; }}}} 3.7 Encontre o nó K-Last na lista vinculada
Esse algoritmo é bastante interessante: defina dois ponteiros P1 e P2 para fazer os nós P2 K mais rápido que o P1 e atravessar para trás ao mesmo tempo. Quando P2 está vazio, P1 é o K-Último Nó
/ *** Encontre o k-th até o último nó na lista vinculada (defina dois ponteiros P1 e P2, torne P2 K mais rápido que P1 e atravessem para trás ao mesmo tempo. Linklistlen (Head)) Retorno NULL; retornar P1;
3.8 Excluir dados duplicados na lista vinculada
É semelhante ao tipo de bolha, desde que seja igual, pode ser excluído ~
/ ** * Exclua dados duplicados na lista vinculada (semelhante à borbulha, é equivalente à exclusão) * * @param Head Head Node */ public static void DeLeTedUclecate (cabeça do nó) {// nó temporário, (começando do primeiro nó-> nó com dados reais) nó temp = head.next; // Próximo nó do nó atual (nó do primeiro nó) nextNode = temp.next; while (temp.next! = null) {while (nextNode.next! = null) {if (nextNode.next.data == nextNode.data) {// exclua o próximo nó (o nó atual aponta para o próximo nó) nextNode.next = nextNode.next.next; } else {// continue com o próximo próximonode = nextNode.next; }} // Na próxima rodada de comparação temp = temp.next; }} 3.9 Consulte os nós intermediários da lista vinculada
Esse algoritmo também é bastante interessante: um ponteiro que leva 1 passo a cada vez, um ponteiro que dá 2 passos de cada vez e depois dá um passo, que é o nó intermediário
/ *** Consulta o nó intermediário de uma única lista vinculada*/ public estático nó searchMid (cabeça do nó) {nó p1 = head; Nó p2 = cabeça; // Dê um passo e um passo duas etapas até que seja nulo. O nó do meio que você atinge (p2! = Null && p2.next! = Null && p2.next.next! = Null) {p1 = p1.next; p2 = p2.next.next; } retornar P1; }3.10, produza mesas de reticulação recursivamente de cauda a cabeça
/ *** Saída Lista vinculada única de cauda na cabeça por recursivamente** @param cabeça cabeça nó*/ public static void printListerSely (cabeça do nó) {if (head! = Null) {printListerSely (head.next); System.out.println (head.data); }} 3.11 Lista de links reversos
/ *** Implemente a inversão da lista vinculada** @param nó o nó da cabeça da lista vinculada*/ public static node reverselinkList (nó nó) {node prev; if (node == null || node.next == null) {prev = node; } else {node tmp = reverselinkList (node.next); node.Next.Next = Node; node.next = null; prev = tmp; } retornar prev; } Referência à lista de links reversos de: //www.vevb.com/article/136185.htm
4. Finalmente
Não é difícil entender a própria lista vinculada, mas pode causar dores de cabeça ao fazer operações relacionadas. Head.Next próximo próximo ... (ainda estou fraco no algoritmo ... Eu não tenho cérebros suficientes ...) Escrevi essa coisinha depois de dois dias ...
Você pode fazer qualquer coisa simplesmente conhecendo o ponteiro da cabeça ao operar uma lista vinculada.
1. Adicione dados à lista vinculada
2. Atravesse a lista vinculada
3. Insira nós na lista vinculada em um determinado local
4. Obtenha a duração da lista vinculada
5. Exclua o nó no local fornecido
6. Classifique a lista vinculada
7. Encontre o nó K-Last na lista vinculada
8. Excluir dados duplicados na lista vinculada
9. Consulte os nós intermediários da lista vinculada
10. Exercite a mesa de ligação única recursivamente de cauda a cabeça
11. Lista de links reversos
PS: A implementação de todos será diferente; portanto, alguns pequenos detalhes mudarão inevitavelmente, e não há uma maneira fixa de escrevê -lo, para que você possa realizar as funções correspondentes ~
Resumir
O acima é o conteúdo inteiro deste artigo. Espero que o conteúdo deste artigo tenha certo valor de referência para o estudo ou trabalho de todos. Se você tiver alguma dúvida, pode deixar uma mensagem para se comunicar. Obrigado pelo seu apoio ao wulin.com.
Referências: