Tabela de liga única simulada
Tabela linear:
As tabelas lineares (também chamadas tabelas seqüenciais) são as estruturas de dados mais básicas, mais simples e mais usadas.
A relação entre os elementos de dados em uma tabela linear é um relacionamento individual, ou seja, exceto para o primeiro e o último elementos de dados, outros elementos de dados estão conectados ao final.
A estrutura lógica das tabelas lineares é simples, o que é fácil de implementar e operar.
Em aplicações práticas, as tabelas lineares são usadas na forma de mesas lineares especiais, como pilhas, filas e cordas.
As características básicas da estrutura linear são:
1. Deve haver um "primeiro elemento" único na coleção;
2. Deve haver um "último elemento" único na coleção;
3. Exceto pelo último elemento, há um sucessor único (mais recente item);
4. Exceto pelo primeiro elemento, há uma tração dianteira única (peça frontal).
Lista vinculada: Lista vinculada
Uma lista vinculada é uma estrutura de armazenamento não contínua e não sequencial em uma unidade de armazenamento físico. A ordem lógica dos elementos de dados é que cada item de dados implementado através da ordem do link do ponteiro na lista vinculado está contido em um "ponto de link".
Um link é um objeto de uma classe, e esse tipo pode ser chamado de link. Existem muitos links semelhantes na lista vinculada, e cada link contém um campo em seguida, referenciado ao próximo link.
O próprio objeto da lista vinculado mantém uma referência ao primeiro nó do link. (Se não houver primeiro, não pode ser localizado)
A linked list cannot directly access data items like an array (using subscripts), but needs to be positioned with the relationship between data, that is, access the next link referenced by the link node, and then the next one, until the required data is accessed and the time complexity of inserting and deleting the required data at the head is O(1), because only the reference pointing is necessary to find, delete the specified node, and insert it after the specified node. Essas operações exigem uma média de pesquisa metade dos nós na lista vinculada, com uma eficiência de O (n).
Lista vinculada única:
Uma tabela linear é representada por "Sequência de nós" e é chamada de lista linear LIGNED (Lista Linked)
É uma estrutura de dados de acesso à cadeia, usando um conjunto de unidades de armazenamento com endereços arbitrários para armazenar elementos de dados em uma tabela linear. (Este conjunto de células de memória pode ser contínuo ou descontínuo)
A estrutura do nó do link:
Dados de campo de dados que armazenam valores de nó; Campo de ponteiro (campo de corrente) que armazena referência de nó em seguida
A lista vinculada vincula os n nós da tabela linear em sua ordem lógica através do domínio do link de cada nó.
Uma lista vinculada com apenas um campo de link por nó é chamada de uma única lista de links. Em uma direção, existem apenas referências a nódulos subsequentes.
/*** Lista vinculada única: Método de inserção do cabeçalho e primeira saída* O lado esquerdo da lista vinculado é chamado de cabeça da corrente e o lado direito é chamado de cauda de corrente. * O método de inserção do cabeçalho para criar uma única lista vinculada é obtida visualizando a extremidade direita da lista vinculada conforme fixo, e a lista vinculada continua se estendendo para a esquerda. * A primeira coisa que vem do método de inserção do cabeçalho é o nó da cauda * @Author Stone */ Public Class SingleLinkedList <T> {Private Link <T> Primeiro; // O primeiro nó public singleLinkedList () {} public boolean isEmpty () {return primeiro == null; } public void insertfirst (t data) {// inserir na cabeça do link da cadeia <t> newlink = new link <t> (dados); newlink.Next = primeiro; // O próximo do novo nó aponta para o nó anterior primeiro = newlink; } link público <t> deletefirst () {// excluir o link do cabeçalho da corrente <T> temp = primeiro; primeiro = primeiro.next; // altere o primeiro nó para retornar temp; } link público <T> encontre (t) {link <T> encontre = primeiro; while (encontre! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} retornar encontre; } link público <t> delete (t t) {if (isEmpty ()) {return null; } else {if (primeiro.data.equals (t)) {link <t> temp = primeiro; primeiro = primeiro.next; // altere o primeiro nó para o próximo nó retorno temp; }} Link <T> p = primeiro; Link <t> q = primeiro; while (! } else {q = p; p = p.next; }} q.next = p.next; retornar p; } public void DisplayList () {// transip System.out.println ("List (primeiro-> last):"); Link <t> atual = primeiro; while (atual! = null) {current.displaylink (); current = current.next; }} public void DisplayListerSe () {// Link de travessia inverso <T> p = primeiro, q = primeiro.next, t; while (q! = null) {// ponteiro é revertido, a ordem de dados atravessada é atrasada t = q.next; // no3 if (p == primeiro) {// Quando é o cabeçalho original, o .next da cabeça deve estar vazio p.next = null; } q.next = p; // no3 -> no1 ponteiro reverso p = q; // Start é reverso q = t; // NO3 START} // No if no loop acima, primeiro.next está vazio e quando q é nulo e não executa o loop, p é o item mais original de dados. Após a inversão, P é atribuído a primeiro = P; displaylist (); } classe link <T> {// Dados do ponto de link T; // Link do campo de dados <T> Em seguida; // ponteiro subsequente, link de domínio da cadeia de nó (dados t) {this.data = data; } void DisplayLink () {System.out.println ("Os dados são" + data.toString ()); }} public static void main (string [] args) {singleLinkedList <Teger> list = new SingleLinkedList <Teger> (); list.InsertFirst (33); list.InsertFirst (78); list.InsertFirst (24); list.InsertFirst (22); list.InsertFirst (56); list.DisplayList (); list.DeleteFirst (); list.DisplayList (); System.out.println ("LINCE:" + list.find (56)); System.out.println ("LINCE:" + list.find (33)); System.out.println ("Excluir encontre:" + list.Delete (99)); System.out.println ("Excluir encontre:" + list.Delete (24)); list.DisplayList (); System.out.println ("--- reverso ----"); list.displaylisterSe (); }}Imprimir
Lista (primeiro-> Última): Os dados são 56 Os dados são 22 Os dados são 24 Os dados são 78 Os dados são 33 (primeiro-> último): os dados são 22 Os dados são 24 Os dados são 78 Os dados são 33 Localizar: NULL LINDO: Linked_list.SingLelinkedlistlink@4b71bbc9 DELETE Find: NULL DELET. Encontre: linked_list.singlelinkedlist$link@17dfafd1 Lista (primeiro-> Última): os dados são 22 Os dados são 78 Os dados são 33 --- Lista reversa (primeiro-> Última): os dados são 33 os dados são 78, os dados são 22
Lista vinculada única: Método de inserção da cauda, de volta à primeira saída - se a extremidade esquerda da lista vinculada for corrigida, a lista vinculada continuará se estendendo à direita, esse método de estabelecer uma lista vinculado é chamado Método de Inserção de Tail.
Ao criar uma lista vinculada com o método de inserção da cauda, o ponteiro da cabeça é corrigido; portanto, um ponteiro de cauda deve ser configurado para se estender à direita da lista vinculada.
A primeira coisa que vem do método de inserção da cauda é o nó da cabeça.
classe pública SingleLinkedList2 <T> {private link <t> head; // O primeiro nó public singleLinkedList2 () {} public boolean isEmpty () {return head == null; } public void insertLast (t data) {// inserir link <t> newlink = new link <t> (dados); if (head! = null) {link <t> nextp = head.next; if (nextp == null) {head.next = newlink; } else {link <T> traseiro = null; while (nextp! = null) {traseiro = nextp; nextp = nextp.next; } rear.Next = newlink; }} else {head = newlink; }} link público <T> DeLeTELAST () {// Exclua a cauda do link da corrente <T> P = Head; Link <t> q = head; enquanto (p.next! = null) {// O próximo nó de p não está vazio, q é igual ao p atual (ou seja, q é o anterior e p é o próximo). Quando o loop termina, q é igual à penúltima extremidade da cadeia q = p; p = p.next; } // excluir q.next = null; retornar p; } link public <T> encontre (t t) {link <t> find = head; while (encontre! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} retornar encontre; } link público <t> delete (t t) {if (isEmpty ()) {return null; } else {if (head.data.equals (t)) {link <t> temp = head; cabeça = cabeça.next; // altere o primeiro nó para retornar temp; }} Link <T> p = Head; Link <t> q = head; while (! } else {q = p; p = p.next; }} q.next = p.next; retornar p; } public void DisplayList () {// Travel System.out.println ("List (Head-> Last):"); Link <t> atual = cabeça; while (atual! = null) {current.displaylink (); current = current.next; }} public void DisplayListerSe () {// Link de travessia inverso <T> p = cabeça, q = head.next, t; while (q! = null) {// o ponteiro é revertido e a ordem de dados percorrida é atrasada t = q.next; // no3 if (p == Head) {// Quando é o cabeçalho original, o .next da cabeça deve estar vazio p.next = null; } q.next = p; // no3 -> no1 ponteiro reverso p = q; // Start é reverso q = t; // NO3 START} // No IF no loop acima, Head.Next está vazio, quando q é nulo e não executa o loop, P é o item mais original de dados. Após a inversão, P é atribuído à cabeça da cabeça = P; displaylist (); } classe link <T> {// Dados do ponto de link T; // Link de domínio de dados <T> Em seguida; // ponteiro sucessivo, link de domínio da cadeia de nó (dados t) {this.data = data; } void DisplayLink () {System.out.println ("Os dados são" + data.toString ()); }} public static void main (string [] args) {singleLinkedList2 <Teger> list = new SingleLinkedList2 <Teger> (); list.InsertLast (33); list.InsertLast (78); list.InsertLast (24); list.InsertLast (22); list.InsertLast (56); list.DisplayList (); list.DeleteLast (); list.DisplayList (); System.out.println ("LINCE:" + list.find (56)); System.out.println ("LINCE:" + list.find (33)); System.out.println ("Excluir encontre:" + list.Delete (99)); System.out.println ("Excluir encontre:" + list.Delete (78)); list.DisplayList (); System.out.println ("---- reverso -----"); list.displaylisterSe (); }}Imprimir
List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 the data is 56 List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 find:null find:linked_list.SingleLinkedList2$Link@4b71bbc9 delete find:null delete Encontre: Linked_List.SingLelinkedList2$link@17dfafd1 Lista (Head-> Last): Os dados são 33 Os dados são 24 Os dados são 22 --- Lista reversa (Head-> Last): Os dados são 22 Os dados são 24, os dados são 33
Simule uma lista vinculada de ponta dupla para implementar pilha e filas com listas vinculadas
Lista vinculada de ponta dupla:
A lista vinculada de ponta dupla é muito semelhante à lista tradicional vinculada. Ele possui apenas um novo atributo adicionado - ou seja, uma referência ao último link é traseira.
Dessa forma, a inserção no final da corrente se tornará muito fácil. Basta alterar o próximo da parte traseira para o nó recém -adicionado, sem loop para procurar o último nó, então há insertfirst e insertlast
Ao excluir o cabeçalho da corrente, você só precisa alterar o ponto de referência; Ao excluir a cauda da corrente, você precisa esvaziar o próximo nó do penúltimo nó.
Nenhuma referência para ele, então é necessário um loop para ler a operação
/ *** Lista vinculada de ponta dupla* @Author Stone*/ Public Classe TwondPointList <T> {private link <t> head; // link privado do primeiro nó <T> traseiro; // ponteiro de cauda public twondpointList () {} public t peekhead () {if (head! = null) {return head.data; } retornar nulo; } public boolean isEmpty () {return head == null; } public void insertfirst (t data) {// inserir na cabeça do link da cadeia <t> newlink = new link <t> (dados); newlink.Next = Head; // O próximo do novo nó aponta para a cabeça do nó anterior = newlink; } public void insertLast (t data) {// inserir link <t> newlink = new link <t> (dados); if (head == null) {traseiro = null; } if (traseiro! = null) {rear.next = newlink; } else {head = newlink; head.next = traseiro; } traseiro = newlink; // Na próxima vez que você inserir, insira da traseira} public t DeLeteHead () {// exclua o cabeçalho da corrente se (isEmpty ()) retorna nulo; Link <t> temp = cabeça; cabeça = cabeça.next; // Altere o primeiro nó para ser o próximo nó if (head == null) {<span style = "white-space: pre"> </span> traseiro = cabeça; } retornar temp.data; } public t encontre (t t) {if (isEmpty ()) {return null; } Link <T> encontre = cabeça; while (encontre! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} if (find == null) {return null; } return find.data; } public t delete (t t) {if (isEmpty ()) {return null; } else {if (head.data.equals (t)) {link <t> temp = head; cabeça = cabeça.next; // altere o primeiro nó para o próximo nó retornar temp.data; }} Link <T> p = Head; Link <t> q = head; while (! } else {q = p; p = p.next; }} q.next = p.next; retornar p.data; } public void DisplayList () {// Travel System.out.println ("List (Head-> Last):"); Link <t> atual = cabeça; while (atual! = null) {current.displaylink (); current = current.next; }} public void DisplayListerSe () {// Traversal inverso if (isEmpty ()) {return; } Link <T> p = cabeça, q = head.next, t; while (q! = null) {// o ponteiro é revertido e a ordem de dados percorrida é atrasada t = q.next; // no3 if (p == Head) {// Quando é a cabeça original, o .next da cabeça deve estar vazio p.next = null; } q.next = p; // no3 -> no1 ponteiro reverso p = q; // Start é reverso q = t; // NO3 START} // No IF no loop acima, Head.Next está vazio e quando q é nulo e não executa o loop, P é o item mais original de dados. Após a inversão, P é atribuído à cabeça da cabeça = P; displaylist (); } classe link <t> {// link nó t dados; // Link de domínio de dados <T> Em seguida; // ponteiro sucessivo, link de domínio da cadeia de nó (dados t) {this.data = data; } void DisplayLink () {System.out.println ("Os dados são" + data.toString ()); }} public static void main (string [] args) {twoEndPointList <Teger> list = new TwoEndPointList <Teger> (); list.InsertLast (1); list.InsertFirst (2); list.InsertLast (3); list.InsertFirst (4); list.InsertLast (5); list.DisplayList (); list.DeleteHead (); list.DisplayList (); System.out.println ("LINDO:" + list.find (6)); System.out.println ("LINCE:" + list.find (3)); System.out.println ("Excluir encontre:" + list.Delete (6)); System.out.println ("Excluir encontre:" + list.Delete (5)); list.DisplayList (); System.out.println ("--- reverso ----"); list.displaylisterSe (); }}Imprimir
Lista (cabeça-> Última): os dados são 4 Os dados são 2 Os dados são 1 Os dados são 3 Os dados são 5 listas (cabeça-> último): os dados são 2 Os dados são 1 Os dados são 3 Os dados são 5 Localizar: NULL LINDO: 3 Excluir o encontro: Dados NULT: Lista 5 (lista de dados): os dados são 3: os dados são 3-os dados são 3--a lista de dados é 3: os dados são 3-os dados são 3-a lista de dados é 3: os dados são 3-os dados são 3--Dados são 3 --- Lista 5:
Use listas vinculadas para implementar a pilha e use a lista única vinculada antes de inseri -la.
Esta classe usa uma lista vinculada de ponta dupla para implementar:
classe pública LinkStack <T> {private TwoEndPointList <T> dados; public linkStack () {DataS = new TwoEndPointList <T> (); } // Coloque na pilha public void push (dados t) {datas.insertfirst (dados); } // coloque o pilha public t pop () {return datas.deletehead (); } // Verifique a parte superior da pilha public t peek () {return datas.peekhead (); } // se a pilha está vazia pública booleana isEmpty () {return datas.isempty (); } public static void main (string [] args) {linkStack <Teger> Stack = new LinkStack <Teger> (); for (int i = 0; i <5; i ++) {staCK.push (i); } para (int i = 0; i <5; i ++) {integer peek = pilha.peek (); System.out.println ("Peek:" + Peek); } para (int i = 0; i <6; i ++) {Integer Pop = Stack.pop (); System.out.println ("pop:" + pop); } System.out.println ("----"); para (int i = 5; i> 0; i--) {staCK.push (i); } para (int i = 5; i> 0; i--) {integer peek = stack.peek (); System.out.println ("Peek:" + Peek); } para (int i = 5; i> 0; i--) {Integer Pop = Stack.pop (); System.out.println ("pop:" + pop); }}}Imprimir
Peek: 4 Peek: 4 Peek: 4 Peek: 4 Peek: 4 PARA: 4 POP: 4 POP: 3 POP: 2 POP: 1 POP: 1 POP: 0 POP: NULL --- Peek: 1 Peek: 1 Peek: 1 Peek: 1 Pop: 1 Pop: 1 Pop: 2 Pop: 3 Pop: 4 POP: 5 POP: 5 POP: 5
A fila de implementação da lista vinculada é implementada usando uma lista vinculada de ponta dupla:
classe pública LinkQueue <T> {private TwoEndPointList <T> Lista; public linkQueue () {list = new TwoEndPointList <T> (); } // Insira a cauda da fila public void insert (t data) {list.insertLast (dados); } // Remova a cabeça da equipe public t remover () {return list.deletehead (); } // Veja o chefe da equipe public t peek () {return list.peekhead (); } public boolean isEmpty () {return list.isempty (); } public static void main (string [] args) {linkQueue <Teger> fileue = new LinkQueue <Teger> (); for (int i = 1; i <5; i ++) {Queue.insert (i); } para (int i = 1; i <5; i ++) {integer peek = fileue.peek (); System.out.println ("Peek:" + Peek); } para (int i = 1; i <5; i ++) {integer remove = fileue.remove (); System.out.println ("remover:" + remover); } System.out.println ("----"); para (int i = 5; i> 0; i--) {fileue.insert (i); } para (int i = 5; i> 0; i--) {integer peek = fileue.peek (); System.out.println ("peek2:" + peek); } para (int i = 5; i> 0; i--) {integer remove = fileue.remove (); System.out.println ("remover:" + remover); }}}Imprimir
Peek: 1 Peek: 1 Peek: 1 Peek: 1 Peek: 1 Remover: 1 Remover: 2 Remover: 3 Remover: 4 --- Peek2: 5 peek2: 5 peek2: 5 peek2: 5 peek2: 5 Remover: 5 Remover: 4 Remover: 3 Remover: 2 Remover: 1