로그인
로그인

estrutura de dados

A estrutura de dados, que organiza o conteúdo principal e a estrutura lógica dos conceitos básicos da estrutura de dados, ajuda a compreender e lembrar pontos de conhecimento e é adequada para revisão de exames!

2024-03-27 14:56:11에 편집됨

WSCoUtCI

estrutura de dados

WSCoUtCI

추천 사항
개요

"Características e Funções do SGBD na Gestão de Bancos de Dados"
- 19
livia.morais@aluno.unifenas.br
Noções básicas comuns de computador
- 14
WSb6eYgD
01Estrutura de dados
- 17
WSysQn6v
Dados e estruturas de dados
- 25
슈퍼직장인
Capítulo Um Introdução
- 19
WSb6eYgD
Mapa mental de algoritmo de estrutura de dados
- 15
WSCoUtCI
algoritmo de classificação de estrutura de dados
- 15
WSCoUtCI
Algoritmo de pesquisa de estrutura de dados
- 19
WSCoUtCI
Estruturas de dados e algoritmos
- 19
WSCoUtCI
Implementação de estrutura de dados e análise de algoritmo
- 17
WSCoUtCI

estrutura de dados

introdução

Conceitos básicos de estrutura de dados

dados

elemento de dados, item de dados

Resuma com exemplos

objetos de dados, estruturas de dados

Tipos de dados, tipos de dados abstratos

Três elementos

estrutura lógica

estrutura linear

juntar

estrutura de árvore

Estrutura do gráfico (estrutura de malha)

estrutura não linear

Estrutura física (estrutura de armazenamento)

armazenamento sequencial

armazenamento em cadeia

Armazenamento de índice

Armazenamento de hash

armazenamento não sequencial

Operações de dados

algoritmo

conceito básico

o que é algoritmo

Programa = estrutura de dados + algoritmo

Estruturas de dados são as informações a serem processadas

Algoritmos são etapas para processar informações

Cinco características dos algoritmos

Finitude

Pode ser executado dentro de um tempo limitado

Algoritmos são finitos

Os programas podem ser infinitos

certeza

A mesma entrada produzirá apenas a mesma saída

viabilidade

Algoritmos podem ser implementados usando operações básicas existentes

digitar

Dados lançados no algoritmo para processamento

saída

O resultado do processamento do algoritmo

Características de um algoritmo “bom”

correção

Capaz de resolver problemas corretamente

legibilidade

Descreva o algoritmo para que outras pessoas possam entendê-lo

Robustez

Algoritmos podem lidar com algumas situações anormais

Alta eficiência e baixos requisitos de armazenamento

Ou seja, a execução do algoritmo economiza tempo e memória.

Baixa complexidade de tempo e baixa complexidade de espaço

Uma medida da eficiência do algoritmo

complexidade de tempo

Como calcular

① Encontre uma operação básica (o loop mais profundo)

② Analise a relação entre o número de tempos de execução x desta operação básica e o tamanho do problema n x = f (n)

③A ordem de grandeza O(x) de x é a complexidade de tempo do algoritmo T(n)

Técnicas comumente usadas

Regra de adição: O( f( n)) × O( g( n)) = O( max( f( n), g( n)))

Regra de multiplicação: O( f( n)) × O( g( n)) = O( ( f( n) × g( n)))

"Sempre consulte a ordem de poder"

Três níveis de complexidade

Complexidade de tempo no pior caso: considere o “pior” caso dos dados de entrada

Complexidade média de tempo: considere a situação em que todos os dados de entrada parecem igualmente prováveis

Melhor complexidade de tempo: considere o "melhor caso" para os dados de entrada

complexidade do espaço

sobrecarga de memória

①Variáveis de armazenamento

②Chamada recursiva

Como calcular

Programa normal

①Encontre as variáveis relacionadas ao espaço ocupado e ao tamanho do problema

②Analise a relação entre o espaço ocupado x e o tamanho do problema n x = f (n)

③A ordem de grandeza O(x) de x é a complexidade do espaço do algoritmo S(n)

programa recursivo

① Encontre a relação entre a profundidade da chamada recursiva x e o tamanho do problema n x = f(n)

②A ordem de grandeza O(x) de x é a complexidade espacial do algoritmo

Nota: Alguns algoritmos requerem espaço de armazenamento diferente para cada camada de função e os métodos de análise são ligeiramente diferentes.

Técnicas comumente usadas

Regra de adição: complexidade de tempo simultâneo

Regra de multiplicação: complexidade de tempo simultâneo

"Sempre consulte a ordem de poder"

Capítulo um

mesa linear

Definição e operações básicas de tabelas lineares

definição

Uma tabela linear possui uma sequência finita de n (n>=0) elementos de dados do mesmo tipo de dados, onde n é o comprimento da tabela quando n=0. Uma lista linear é uma lista vazia.

ordem

A ordem dos bits começa em 1 e o subscrito da matriz começa em 0

Comprimento da mesa, mesa vazia

Elementos de cabeçalho e rodapé

antecessor direto e sucessor direto

Exceto o primeiro elemento, cada elemento possui um e apenas um antecessor direto; Cada elemento, exceto o último elemento, tem exatamente um sucessor direto.

Recursos notáveis

Os elementos de dados são do mesmo tipo, limitados e ordenados

Operações básicas

Crie vendas, adicione, exclua, modifique e verifique

Julgue vazio, julgue longo, imprima a saída (função de função personalizada)

Outros pontos dignos de nota

Entenda quando passar referências de parâmetros "&"

A nomenclatura da função deve ser legível

Tabela de sequência (armazenamento sequencial)

Definição (estrutura de armazenamento)

Os elementos de dados que são logicamente adjacentes também são fisicamente adjacentes

Método para realizar

alocar memória estaticamente

Use a implementação de "matriz estática" para definir o número máximo de armazenamento

Uma vez determinado o tamanho, ele não pode ser alterado

Alocar memória dinamicamente

Usando "array dinâmico", o ponteiro de dados definido na estrutura aloca memória dinamicamente por meio de malloc (há uma área de heap)

L.data＝(ElemType *)malloc(sizeof(ElemType)*tamanho)

Quando a tabela de sequência está cheia, malloc pode ser usado para expandir dinamicamente a capacidade máxima da tabela de sequência.

É necessário copiar os elementos de dados para uma nova área de armazenamento e utilizar a função livre para liberar a área original.

Cabeçalhos usados #include <stdlib.h>

Características

acesso aleatório

Pode encontrar o i-ésimo elemento em tempo O (1)

Alta densidade de armazenamento

Expandir a capacidade é inconveniente

Inserir e excluir elementos de dados é inconveniente

Função de operação

inserir

Complexidade de tempo: Melhor O(1) Pior O(n) Média O(n)

excluir

Complexidade de tempo: Melhor O(1) Pior O(n) Média O(n)

Pontos de código

O código deve prestar atenção à diferença entre a ordem de bits i e o subscrito

O algoritmo deve ser robusto e prestar atenção à legalidade do i

Uso de citações

Encontrar

Pesquisa bit a bit

No caso de memória alocada dinamicamente, a complexidade de tempo é O(1)

Encontrar por valor

Complexidade do tempo de alocação estática: melhor O(1) pior O(n) média O(n)

Estático e dinâmico são iguais

lista vinculada

ponteiro de cabeça

fila

1. Matrizes e listas vinculadas podem ser usadas

Listas vinculadas circulares e matrizes circulares

Ponteiros de cabeça e cauda, subscritos

Capítulo dois