O medidor linear é uma estrutura linear, que é uma sequência limitada que possui o mesmo elemento de dados do tipo n (n ≥ 0).
1. Array
A matriz possui limites superior e inferior e os elementos da matriz são contínuos nos limites superior e inferior.
O diagrama esquemático da matriz de 10,20,30, 40, 50 50 é o seguinte:
Recursos da matriz : os dados são contínuos;
A matriz um pouco mais complicada é a matriz multidimensional e a matriz dinâmica. Para o idioma C, a matriz multidimensional também é realizada por meio de uma matriz dimensional. Quanto à matriz dinâmica, é uma matriz da capacidade do grupo de índices que pode crescer dinamicamente; Vector;
Segundo, uma lista vinculada de uma via <r /> de uma maneira vinculada (lista vinculada única) é um tipo de lista vinculada.
O diagrama esquemático de uma única lista vinculada é a seguinte:
A cabeça da cabeça está vazia, o nó sucessor da cabeça é "nó 10" (nó de dados 10) e o nó sucessor de "nó 10" é "nó 20" (dados com dados 10) ,. ..
Nó de exclusão de cadeia única
Exclua "Nó 30"
Antes de excluir: o nó sucessor de "Nó 20" é "Nó 30" e o nó sucessor de "nó 30" é "nó 40".
Após a exclusão: o nó sucessor de "Nó 20" é "Nó 40".
Lista vinculada única nó adicionado
Adicione "Nó 15" entre "Nó 10" e "Nó 20"
Antes de adicionar: o nó sucessor de "nó 10" é "nó 20".
Após adicionar: o nó sucessor de "Nó 10" é "Nó 15" e o nó sucessor de "Nó 15" é "Nó 20".
A característica de uma única lista vinculada é que a direção do link do nó é de uma via;
Terceiro, Lista de dois caminhos vinculados
A lista vinculada de dois caminhos (Lista Linked Dual) é um tipo de lista vinculada. Como uma única lista vinculada, a lista de cadeia dupla também é composta de nós. Portanto, a partir de qualquer nó na lista vinculada por dois caminhos, você pode acessar facilmente seus nós frontais e nós subsequentes. Geralmente, todos nós construímos uma lista vinculada circular de dois caminhos.
O diagrama esquemático da lista vinculada dupla é a seguinte:
O cabeçalho está vazio, o nó sucessor da cabeça é "nó 10" (nó de dados 10); sucessor O nó é "nó 10"; .
Nó de exclusão de relógio de corrente dupla
Exclua "Nó 30"
Antes de excluir: o nó sucessor de "nó 20" é "nó 30" e o pré -nó de "nó 30" é "nó 20". O nó sucessor de "Nó 30" é "Nó 40" e o pré -nó de "nó 40" é "nó 30".
Após a exclusão: o nó sucessor de "nó 20" é "nó 40" e o pré -nó de "nó 40" é "nó 20".
Lista de links duplos Adicionando nós
Adicione "Nó 15" entre "Nó 10" e "Nó 20"
Antes de adicionar: o nó sucessor de "nó 10" é "nó 20" e o nó anterior do "nó 20" é "nó 10".
Após adicionar: o nó sucessor de "Nó 10" é "Nó 15" e o pré -nó de "nó 15" é "nó 10". O nó sucessor de "Nó 15" é "Nó 20" e o nó anterior de "nó 20" é "nó 15".
A implementação da lista de cadeia dupla é introduzida abaixo e as três implementações de C/C ++/Java são introduzidas, respectivamente.
1. C Implementar uma lista vinculada dupla
Implemente o arquivo de lista vinculado ao código de dois caminhos (Double_link.h)
#Ifndef_double_link_h#define_double_link_h // Crie uma "lista vinculada de dois caminhos". Sucesso, retorne à cabeça; Sucesso, retornar 0; Retorne a 1 para o vazio; extern int dlink_is_empty (); Sucesso, retorne ao ponteiro do nó; Extern void* dlink_get (int index); Sucesso, retorne ao ponteiro do nó; extern void* dlink_get_first (); Sucesso, retorne ao ponteiro do nó; extern void* dlink_get_last (); Sucesso, retornar 0; extern int dlink_insert (índice int, void *pval); Sucesso, retornar 0; extern int dlink_insert_first (void *pval); Sucesso, retornar 0; extern int dlink_append_last (void *pval); Sucesso, retornar 0; Sucesso, retornar 0; Sucesso, retornar 0;
Double_link.c em uma lista vinculada de dois caminhos
#include <stdio.h> #include <MaiSloc.h>/*** C A lista vinculada de dois caminhos de Lingle pode armazenar dados arbitrários. ** @Author Skywang* @Data 2013/11/07*/// Os nós da lista vinculada por dois lugares typedef tag_node {stroct tag_node*prev; Observe que o valor da cabeça não armazena o valor do elemento! Interseção Interseção Nó estático *phead = nulo; // Número do nó. Estático int conting = 0; // Crie um novo "nó". Sucesso, retorne ao ponteiro do nó; Nó estático *create_node (void *pval) {node *pnode = null; "); Retornar nulo;} // o padrão, o primeiro nó e o último nó do PNODE apontam para seu próprio pnode-> prev = pnode-> a seguir = pnode; // O valor do nó é pvalpnode-> p = pval; Sucesso, retornar 0; int create_dlink () {// Crie o cabeçalho PHEAD = CREATE_NODE (NULL); Contagem de retorno == 0;} // retorna à "lista de dois caminhos vinculados" int dlink_size () {contagem de retorno;} // Obtenha o "nó na posição de índice na lista de dois caminhos" nó estático* get_ nó (nó (int index) {ifx <0 || index> = count) {printf ("%s falhou! if (índice <= (contagem/2)) {int i = 0; Pesquise int j = 0; nó "nó estático * g et_first_node () () return get_node (0);} // obtenha o nó estático" Último nó " * get_last_node () {return get_node (count-);} // obtenha o" elemento da posição de índice na lista vinculada de mão dupla ". Sucesso, Retorno Valor do Nó; void * dlink_get (int index) {node * pindex = get_node (index); 1 个元素的值 ”void* dlink_get_first () {return dlink_get (0);} // 获取“ 双向链表中最后 1 个元素的值 ”void* dlink_get_last () {return dlink_get (count- 1);} /// Insira "pval" na posição do índice. Sucesso, retornar 0; int dlink_insert (int index, void * pval) {// insira o cabeçalho if (index == 0) retornar dlink_insert_first (pvalt (pval); // obtenha o nó que corresponde à posição a ser inserida.; se! Pindex) retornar -1; // 创建 创建 节点 节点 "nó *pnode = create_node (pval); if (! pnode) retornar -1; pnode-> prev = pindex-> prev; pnode-> next = pindex; pindex; -> Prev-> Next = PNODE; {node *PNOD E = Create_node (pval); ++; retorna 0;} // insira "pval" na posição final int dlink_append_last (void *pval) {node *pnode = create_node (pval); PNODE- AVESS = PHEAD-> ANTES; Lista vinculada ". Sucesso, retornar 0; int dlink_delete (int index) {node *pindex = get_node (index); > next-> prev = Pindex-> prev; Pindex-> prev-> next = Pindex-> Next; Free (Pindex); count-; Return 0;} // 删除第一个节点 int dlink_delete_first () {return dlink_delete (0);} // exclua um nó int dlink_delete_last () {return dlink_delete (count-);} // revisite "Lista vinculada de duas vias". Sucesso, retornar 0; Int Destroy_dlink () {if (! ;Programa de teste de lista de dois caminhos vinculados (dlink_test.c)
#include <stdio.h> #include "double_link.h"/*** c linguagem para implementar um programa de teste de lista de dois caminhos. ** (01) int_test ()* Demonstrar "Int Dados" em uma lista vinculada de dois caminhos. * (02) String_teest ()* Demonstre "dados da strine" em uma lista vinculada a dois caminhos. * (03) Object_teest ()* Demonstre o "objeto" em uma lista vinculada de duas via. ** @Author Skywang* @Date 2013/11/07* /// Operação da lista vinculada de duas vias int void int_teest () {int iarr [4] = {10, 20, 30, 40}; n -----%s ------ ", __func __); create_dlink (); // Crie uma lista vinculada de duas vias dlink_insert (0, & iarr [0]); // Insira os dados dlink_insert (0, & & & ig & & ig & & ig & & & 1]); Data printf ("dlink_is_empty () =%d/n", dlink_is_empty ()); O tamanho da lista vinculada à link de dois caminhos da lista de dois caminhos int i; ) dlink_get (i); vinte "," trinta "," Fringf ("/n ----%s ----%s--/n", __func __); 0, Sarr [0]); Lista vinculada de dois vias; n ", dlink_size ()); // O tamanho da lista vinculada de dois caminhos // imprima todos os dados Int I na lista vinculada de dois caminhos; char *p; int sz = dlink_size (); para (i = 0; tag_stu {int id; {40, {40, {40, {40, "Dan"},};#define arr_stu_size ", __func __); create_dlink (); // Crie uma lista ligada a dois caminhos dlink_insert (0, & ar_stu [0] ); "dlink_is_empty () =%d/n", dlink_is_empl ()); Lista de dois vias vinculadas // todos os dados na lista vinculada por duas via i; ) dlink_get (i); ); string_test (); object_test (); Retornar 0;}Resultado em execução
---- int_test ---- dlink_is_empty () = 0dlink_size () = 3dlink_get (0) = 30d_get (1) = 20dlink_get 0dlink_size () = 3dlink_get (0) = thregtydlink_get (1) = vintedlink_ (2) -object_test ---- dlink_is_empty () = 0dlink_size () = 3dlink_get (0) = [30, vic] dlink_get (1) = [20, jody] dlink_get (2) = [10, céu]
2. C ++ realiza a lista de cadeia dupla
Implementar o arquivo de lista vinculado ao código de dois vias (Doublelink.h)
#Ifndef Double_link_hxx#Definir Double_link_HXX# Prev, dnode *a seguir) {this-> value = t; tamanho (); int DELETE_LAST (); ) {// Crie "Speed". Nota: Não há dados de armazenamento na cabeça! Phead = novo dnode <T> (); > :: ~ doughlink () {// exclua todos os nós dnode <t>* ptmp; Excluir ptmp;} // excluir o "cabeça" excluir phead; Lista de cadeia 为空 modelo <classe T> int doublelink <t> :: is_empty () {return count == 0;} // 获取第 índice 位置的节点 modelo <classe t> dnode <t>* Doublelink <T>: : get_node (int index) {// validade do parâmetro de julgamento se (índice <0 || index> = contagem) {cout << / Localização if (índice <= count/ 2) {int i = 0; ;} / / Pesquisa reversa int j = 0; ; Temple <classe T> triveLink <t> :: get_first () {return get_node (0)-> value;} // obtenha o valor do último nó. Posição do índice Antes do modelo <classe T> int Doublelink <T> :: Insert (Int Index, T t) {ifx == 0) Return Insert_first (T) ;; > Anterior, previsto); Modelo <classe T> int doublelink <T> :: insert_fring (t) {dnode <t>* pnode = novo dnode <t> (t, phead-> próximo); > Next = PNODE; > Prev = pnode; > Próximo-> prev = pindex-> prev; T> int doublelink <t> :: delete_first () {return del (0);} // 删除最后一个节点 modelo <classe t> int doublelink <t> :: delete_last () {return del (count-);} #EndifArquivo de teste da lista vinculado de duas via (dlinktest.cpp)
#include <iostream> #include "doublelink.h" userspace std; --- "<< endl; // Crie uma lista vinculada de duas vias Doublelink <int>* pdlink = new Doublelink <int> (); pdlink-> insert (0, 20); // inserir 20 na primeira posição pdlink-> append_last (10); << "is_empty () =" << pdlink-> is_empty () << endl; << endl; -> get (i) << endl;} void string_test () {string Sarr [4] = {"ten", "vinte", "trinta", "quarenta"}; ---- "" ENDL; O segundo elemento em Sarr no primeiro pdlink-> append_last (Sarr [0]); ); () = "<< pdlink-> size () << endl; // todos os dados int sz = pdlink-> size (); para (int i = 0; i <sz; i ++)" <") = "<< pdlink-> get (i) << endl;} struct stu {int id; char nome [20];}; static stu arr_stu [] = {10," sky "}, {20 20", jody "}, {30," vic "}, {40," dan "},};#define arr_stu_size cout <<"/n ---- object_test ---- "<< endl; // criar um dois- Way List List Doublelink <Stu>* pdlink = new Doublelink <Stu> (); > Append_last (ARR_STU [0]); para a primeira posição // se a lista vinculada de mão dupla está vazia << "is_empty () =" << pdlink-> is_empty () << endl; = "<< pdlink-> size () << endl; // imprima todos os dados int sz = pdlink-> size () na lista vinculada de duas vias; = 0; i <sz; i ++) {p = pdlink-> get (i); main () {int_teest (); string_test (); object_test (); Retornar 0;}Exemplo de descrição
No exemplo acima, coloquei a "declaração" e a "implementação" da lista vinculada de duas via no arquivo de cabeçalho. As especificações de programação nos alertam: separam a declaração e a implementação da reivindicação, e o valor do arquivo de cabeçalho (arquivo .h ou .hpp) continha apenas a instrução e foi responsável pela implementação no arquivo de implementação (arquivo .cpp)!
Então, por que você faz isso? Isso ocorre porque, na implementação de uma lista vinculada a dois caminhos, o modelo é adotado; Para simplificar, se for declarado em Doublelink.H e implementado em Doublelink.cpp; Por razões específicas, você pode consultar "por que os compiladores C ++ não podem suportar a compilação separada de modelos".
Resultado em execução
---- int_test ---- is_empty () = 0size () = 3pdlink (0) = 30pdlink (1) = 20pdlink (2) = 10 ---- String_test ----- emway () = 0size () = 3pdlink (0) = thirtypdlink (1) = twentypdlink (2) = ten ---- object_teest ---- is_empty () = 0size () = 3pdlink (0) = [30, vic] pdlink (1) = [ 20 20, Jody] pdlink (2) = [10, céu]
3. Java percebe a lista de cadeia dupla
Implementação do Doublelink.java
/*** LISTA LIGADO DE TODOS OS JAVA. * Nota: Existe uma lista vinculada a dois caminhos no pacote de coleta de Java. / Top Wardpe Dnode <t> MHED; {this.value = value; Nota: Não há dados de armazenamento na cabeça! Mhead = novo dnode <T> (nulo, nulo, nulo); Retorne mcount;} // se a lista vinculada está vazia booleana isempty () {return mcount == 0;} // o nó private dnode <t> getNode (int index) {ifx) {index <0 || index> = mcount) Lanke Novo IndexOutfBoundSexception (); ;} // 反向查找 dnode <t> rnode = mhead.prev; int rindex = mcount - índice -1; para (int j = 0; j <rindex; j ++) rnode = rnode. / Obtenha o valor do nó da posição do índice. <t> (T, Mhead, Mhead.Next); T> (t, inode.prev, inode); Public void insertfirst (t t) {insert (0, t);} // Adicione o nó ao final da lista vinculada do public void AppendLast (t t) {dnode <t> novo dnode <t> (t, mhead. Prev mhead); .next = inode.next; Nó public void DeLeTelast () {del (mcount-);}}Programa de teste (dlinkTest.java)
/*** LISTA LIGADO DE TODOS OS JAVA. * NOTA: Existe uma lista vinculada a dois caminhos no pacote de coleta que vem com Java. Operação de tabela vinculada ao caminho de dois dados Int estático privado int_teest () {int [] {10, 20, 30, 40}; = Novo Doublelink <Teger> (); PRIMEIRA POSIÇÃO // Se a lista vinculada por dois caminhos é System.out.printf (ISEMPTY () =%b/n ", dlink.isempty ()); d/n ", dlink.size ()); // imprima todos os nós para (int i = 0; i <dlink.size (); i ++) System.out .println (" dlink ("+i+") = "+dlink.get (i));} private estático void string_test () {string [] Sarr = {" ten "," vinte "," trinta "," quarenta ""}; /n ---- String_test ---- "); // Crie uma lista vinculada de duas vias Doublelink <String> dlink = new Doublelink <String> (); [1]); // Insira o segundo elemento em Sarr na primeira posição dlink.appendLast (Sarr [0]); A primeira posição // se a lista vinculada por duas via é vazia System.out.printf ("isEmpty () =%b/ n", dlink.isempty ());// system.out.printf ("size () =%d/ n ", dlink.size ()); // imprima todos os nós para (int i = 0; i <dlink.size (); i ++) System.out.println (" dlink ("+i+ ") ="+dlink.get (i));} // a classe interna privada classe estática aluno {private string id estudante (int id, nome da string) {this.id = id; ouverridepublic string tostring () {"+id+", "+name+"] ";} tudent [] studers = novo aluno [] {new Student (10," Sky "), novo aluno (20," Jody "), novo Aluno (30, "VIC"), novo aluno (40, "Dan"),}; Lista de duas vias LIGADA DOUBLERING <LEGRIDO> DLINK = NOVO DOUBLELING <LEGRENDO> (); O primeiro elemento dos alunos para Dlink.InsertFirst (estudantes [estudantes [estudantes [2]); printf ("isEmpty () =%b/n", dlink.isempty ()); nós para (int i = 0; i <dlink.size ()); Estático void main (string [] arts) {int_test (); string_test (); object_test (); }}Resultado em execução
---- int_test ---- isEmpty () = falsSize () = 3dlink (0) = 30dlink (1) = 20dlink (2) = 10 ---- String_test ——- isEmpty () = FalseSize () = 3dlink (0) = threntydlink (1) = vintedlink (2) = ten ---- Object_teest --- isEmpty () = falssesize () = 3dlink (0) = [30, vic] dlink (1) = [20 20 , Jody] dlink (2) = [10, céu]
O acima é todo o conteúdo deste artigo. Espero que todos possam entender e ajudar a todos.