Galeria de mapas mentais Estrutura de Dados Capítulo 2-Tabela Linear
Capítulo 2 de “Estrutura de Dados” - classificando o conhecimento de tabelas lineares, incluindo sua definição e operações básicas, representação sequencial e representação em cadeia.
Editado em 2022-11-23 16:06:11Microbiologia medica, Infezioni batteriche e immunità riassume e organizza i punti di conoscenza per aiutare gli studenti a comprendere e ricordare. Studia in modo più efficiente!
La teoria cinetica dei gas rivela la natura microscopica dei fenomeni termici macroscopici e le leggi dei gas trovando la relazione tra quantità macroscopiche e quantità microscopiche. Dal punto di vista del movimento molecolare, vengono utilizzati metodi statistici per studiare le proprietà macroscopiche e modificare i modelli di movimento termico delle molecole di gas.
Este é um mapa mental sobre uma breve história do tempo. "Uma Breve História do Tempo" é um trabalho científico popular com influência de longo alcance. Ele não apenas introduz os conceitos básicos da cosmologia e da relatividade, mas também discute os buracos negros e a expansão. Do universo. questões científicas de ponta, como inflação e teoria das cordas.
Microbiologia medica, Infezioni batteriche e immunità riassume e organizza i punti di conoscenza per aiutare gli studenti a comprendere e ricordare. Studia in modo più efficiente!
La teoria cinetica dei gas rivela la natura microscopica dei fenomeni termici macroscopici e le leggi dei gas trovando la relazione tra quantità macroscopiche e quantità microscopiche. Dal punto di vista del movimento molecolare, vengono utilizzati metodi statistici per studiare le proprietà macroscopiche e modificare i modelli di movimento termico delle molecole di gas.
Este é um mapa mental sobre uma breve história do tempo. "Uma Breve História do Tempo" é um trabalho científico popular com influência de longo alcance. Ele não apenas introduz os conceitos básicos da cosmologia e da relatividade, mas também discute os buracos negros e a expansão. Do universo. questões científicas de ponta, como inflação e teoria das cordas.
mesa linear
Definição e operações básicas
definição
Uma tabela linear é uma sequência finita de n elementos de dados do mesmo tipo de dados
a1 é o elemento do cabeçalho
an é o elemento da tabela
Cada elemento, exceto o primeiro elemento, tem um e apenas um predecessor direto; cada elemento, exceto o último elemento, tem um e apenas um sucessor direto;
Características
O número de elementos na tabela é limitado
Os elementos da tabela possuem uma sequência lógica. Os elementos da tabela possuem sua ordem.
Os elementos da tabela são todos elementos de dados e cada elemento é um único elemento
Os tipos de dados dos elementos da tabela são todos iguais, o que significa que cada elemento ocupa o mesmo tamanho de espaço de armazenamento
Os elementos da tabela são abstratos, ou seja, apenas é discutida a relação lógica entre os elementos, sem considerar o que os elementos realmente representam.
Operações básicas de tabelas lineares
InitList(&): Lista de inicialização. Construa uma tabela linear vazia
Comprimento (L): Encontre o comprimento da mesa. Retorna o comprimento da tabela linear L, ou seja, o número de elementos de dados em L
LocateElem(L,e): Encontre a operação por valor. Encontre elementos na tabela L com determinado valor-chave
GetElem(L,i): operação de pesquisa bit a bit. Obtenha o valor do elemento na posição i na tabela
ListInsert (&L,i,e): Operação de inserção. Insira o elemento especificado e na i-ésima posição na tabela L
ListDelete(&L,i,&e): operação de exclusão. Exclua o elemento na i-ésima posição da tabela e use e para retornar o valor do elemento excluído
PrintList(L): Operação de saída. Produza todos os valores dos elementos da tabela linear em ordem sequencial
Vazio(L): Operação vazia. Se o trabalho for uma tabela vazia, retorne verdadeiro, caso contrário, retorne falso
DestroyList(&L): operação de destruição. Destrua a tabela linear e libere o espaço de memória ocupado pela tabela linear L
representação sequencial
definição
O armazenamento sequencial de uma tabela linear usa um conjunto de unidades de armazenamento com endereços consecutivos para armazenar sequencialmente os elementos de dados na tabela linear, de modo que dois elementos logicamente adjacentes também sejam fisicamente adjacentes.
Características
acesso aleatório
O elemento especificado pode ser encontrado no tempo O(1) através do primeiro endereço e número do elemento.
Alta densidade de armazenamento, cada nó armazena apenas elementos de dados
A ordem lógica dos elementos em uma tabela é igual à ordem física, portanto, as operações de inserção e exclusão exigem a movimentação de um grande número de elementos
Operações básicas
(1) inserir
Complexidade de tempo: O(n)
(2) excluir
Complexidade de tempo: O(n)
(3) Encontrar por valor (pesquisa sequencial)
Complexidade de tempo: O(n)
representação em cadeia
Definição de lista vinculada individualmente
Armazene elementos de dados em uma tabela linear por meio de um conjunto arbitrário de unidades de armazenamento
Para cada nó da lista vinculada, além de armazenar as informações do próprio elemento, ele também precisa armazenar um ponteiro para seu sucessor.
Anexe um nó antes do primeiro nó da lista vinculada individualmente, chamado de nó principal. Seu campo de dados não contém nenhuma informação e o ponteiro aponta para o primeiro nó do elemento da lista linear.
Operações básicas de lista vinculada individualmente
Crie uma lista vinculada individualmente usando o método de inserção de cabeçalho
A ordem dos nós na lista vinculada gerada é inconsistente com a ordem dos dados de entrada.
Complexidade de tempo: O(n)
Crie uma lista vinculada individualmente usando o método de inserção final
Apresente o ponteiro final r, que sempre aponta para o nó final da lista vinculada atual
Complexidade de tempo: O(n)
Encontre o valor do nó por número de série
Complexidade de tempo: O(n)
Encontre nós da tabela por valor
Complexidade de tempo: O(n)
Operação de inserção de nó
complexidade de tempo
Inserindo após um determinado nó: O(1)
Caso contrário, O(n)
Operação de inserção direta
Suponha que o nó a ser inserido seja s e insira-o na frente do nó p: s pode ser inserido depois de p primeiro e então p->dados e s->dados são trocados. A complexidade de tempo é de apenas O(1).
Operação de exclusão de nó
Complexidade de tempo: O(1)
Abordagem estendida: para excluir o nó p, você pode primeiro atribuir o valor de seu nó sucessor a si mesmo e, em seguida, excluir o nó sucessor. A complexidade de tempo é de apenas O (1).
Encontre a operação de comprimento da tabela
Complexidade de tempo: O(n)
Lista duplamente vinculada
A complexidade de tempo de acesso ao nó predecessor de uma única lista vinculada é O(n). Por esta razão, uma lista duplamente encadeada é introduzida dois ponteiros, anterior e próximo, apontando para seus nós predecessor e sucessor, respectivamente.
operação de inserção
Excluir operação
lista vinculada circular
Lista circular unida individualmente
O ponteiro do último nó da tabela não é NULL, mas aponta para o nó principal.
O resto é igual a uma lista vinculada individualmente
Lista circular duplamente vinculada
O ponteiro anterior do nó principal aponta para o nó final da lista quando a lista vinculada é uma lista vazia, o campo anterior e o próximo campo do nó principal são ambos iguais a L;
lista vinculada estática
Use matrizes para descrever a estrutura de armazenamento vinculada de listas lineares
O ponteiro é o endereço relativo do nó (subscrito da matriz), também conhecido como cursor
Use next==-1 como marca final
Comparação de lista de sequências e lista vinculada
Métodos de acesso (leitura e gravação)
Tabela de sequência: pode ser acessada sequencialmente ou aleatoriamente
Lista vinculada: os elementos só podem ser acessados sequencialmente no topo da lista
Estrutura lógica e estrutura física
Operações de localização, inserção e exclusão de elementos
alocação de espaço
O armazenamento sequencial é difícil de expandir quando o armazenamento estático é alocado e a alocação dinâmica de armazenamento reduzirá a eficiência operacional;