MindMap Gallery Estrutura de dados versão em linguagem C

Estrutura de dados versão em linguagem C

Introdução ao Capítulo 1 da Estrutura de Dados C Language Edition 2ª Edição, que apresenta o conteúdo de pesquisa da estrutura de dados 1.1, 1.2 Conceitos básicos e terminologia de estruturas de dados, 1.3 Representação e implementação de tipos de dados abstratos, etc.

Edited at 2024-04-21 17:36:01

WSCoUtCI

Estrutura de dados versão em linguagem C

WSCoUtCI

Recommended to you
Outline

Notas de leitura Isso é suficiente para estudar
- 17
- 1
- 1
75zb2rxr@bccto.cc
Mapa mental de influência
- 23
75zb2rxr@bccto.cc
Mapa mental Red Rock
- 22
75zb2rxr@bccto.cc
Um mapa mental simples de Os Analectos de Confúcio
- 23
75zb2rxr@bccto.cc
Gráfico de resumo do capítulo Como o aço foi temperado
- 14
- 1
- 1
75zb2rxr@bccto.cc
Mapa mental Viagem ao Oeste
- 12
75zb2rxr@bccto.cc
Mapa mental Margem da Água
- 15
75zb2rxr@bccto.cc
Notas de leitura da infância
- 14
75zb2rxr@bccto.cc
Mapa do curso de massa e densidade de física do ensino médio
- 16
75zb2rxr@bccto.cc
6 etapas para gerenciar o tempo do projeto
- 16
- 2
75zb2rxr@bccto.cc

introdução

1.1 Conteúdo de pesquisa da estrutura de dados

Estrutura de dados é um curso básico entre matemática, hardware e software de computador

Sistema de gerenciamento de status de aluno: relacionamento linear um para um

Problema de xadrez humano-computador: estrutura de árvore um para muitos

Problema do caminho mais curto: estrutura de malha muitos para muitos

1.2 Conceitos básicos e terminologia de estruturas de dados

1.2.1 Dados, elementos de dados, itens de dados e objetos de dados

Dados são uma representação simbólica de coisas objetivas. É um termo geral para todos os símbolos que podem ser inseridos em um computador e processados por um programa de computador.

Elemento de dados é a unidade básica de dados e geralmente é considerado e processado como um todo em computadores.

Item de dados é a menor unidade indivisível que constitui um elemento de dados e tem significado independente.

Objeto de dados é uma coleção de elementos de dados com as mesmas propriedades e é um subconjunto de dados.

1.2.2 Estrutura de dados

estrutura lógica

Definir estrutura Não há outra relação entre os elementos de dados além da relação de “pertencer à mesma coleção”

estrutura linear Existe um relacionamento um-para-um entre os elementos de dados

estrutura de árvore Existe um relacionamento um-para-muitos entre os elementos de dados

estrutura gráfica ou estrutura de malha Existe um relacionamento muitos-para-muitos entre os elementos de dados

estrutura de armazenamento

estrutura de armazenamento sequencial

estrutura de armazenamento em cadeia

1.2.3 Tipos de dados e tipos de dados abstratos

Um tipo de dados é uma coleção de valores e um conjunto de operações definidas neste conjunto de valores.

Abstract Data Type (ADT) geralmente se refere a um modelo matemático definido pelo usuário para representar um problema de aplicativo e o nome geral de um conjunto de operações definidas neste modelo. Inclui especificamente três partes: objetos de dados e relacionamentos em objetos de dados. Uma coleção de objetos de dados e uma coleção de operações básicas em objetos de dados.

1.3 Representação e implementação de tipos de dados abstratos

(1) Constantes e tipos predeterminados (2) A representação da estrutura de dados (estrutura de armazenamento) é descrita por uma definição de tipo (typedef). O tipo de elemento de dados é acordado como ElemType, que é definido pelo usuário ao usar esses dados; tipo. (3) Os algoritmos básicos de operação são descritos por funções no seguinte formato (4) Alocação dinâmica e liberação de memória. (5) Instrução de atribuição (6) Instrução de seleção (7) Instrução de loop (8) Instrução final (9) As instruções de entrada e saída usam C + streaming de entrada e saída (10) Funções básicas

1.4 Algoritmos e análise de algoritmos

1.4.1 Definição e características do algoritmo

(1) Finito. Um algoritmo sempre deve terminar após a execução de um número finito de etapas, e cada etapa deve ser concluída em um tempo finito.

(2) Certeza. As operações que devem ser realizadas em cada caso estão claramente especificadas no algoritmo, e não haverá ambigüidade. O executor ou leitor do algoritmo poderá compreender claramente seu significado e como executá-lo.

(3) Viabilidade. Todas as operações no algoritmo podem ser implementadas executando as operações básicas já implementadas um número finito de vezes.

(4) Entrada. Um algoritmo tem 0 ou mais entradas. Ao descrever um algoritmo como uma função, a entrada é frequentemente representada por parâmetros formais, cujos valores são obtidos da função chamadora quando são chamados.

(5) Saída. Um algoritmo possui uma ou mais saídas, que são os resultados do processamento de informações pelo algoritmo. Um algoritmo sem saída não tem significado. Ao usar funções para descrever algoritmos, a saída geralmente é representada por valores de retorno ou parâmetros formais de tipos de referência.

1.4.2 Critérios básicos para avaliação da qualidade dos algoritmos

(1) Correção. Com uma entrada de dados razoável, resultados corretos podem ser obtidos dentro de um tempo de execução limitado.

(2) Legibilidade. Um bom algoritmo deve, em primeiro lugar, ser fácil de ser entendido e comunicado pelas pessoas e, em segundo lugar, deve ser executável por máquina. Algoritmos legíveis ajudam as pessoas a entender o algoritmo, enquanto algoritmos difíceis de entender tendem a ocultar erros e são difíceis de depurar e modificar.

(3) Robustez. Quando os dados de entrada são ilegais, um bom algoritmo pode responder adequadamente ou tratá-los adequadamente, sem produzir resultados de saída inexplicáveis.

(4) Eficiência. A eficiência inclui aspectos de tempo e espaço. A eficiência do tempo significa que o algoritmo é razoavelmente projetado e possui alta eficiência de execução, que pode ser medida pela complexidade do tempo. A eficiência do espaço significa que a capacidade de armazenamento ocupada pelo algoritmo é razoável e pode ser medida pela complexidade do espaço; A complexidade do tempo e a complexidade do espaço são os dois principais indicadores para medir algoritmos.

1.4.3 Complexidade temporal do algoritmo

1. Tamanho da pergunta e frequência das afirmações

O número de vezes que uma instrução é executada repetidamente é chamado de frequência de instrução.

O tamanho do problema é a quantidade de entrada exigida pelo algoritmo para resolver o problema. É a representação essencial do tamanho do problema e geralmente é representado por um número inteiro n.

2. Definição de complexidade de tempo do algoritmo

Em geral, o número de execuções repetidas das instruções básicas no algoritmo é uma função An) do tamanho do problema n, e a medição do tempo do algoritmo é registrada como: A frequência é T(n)=O((n)) FrequênciaA Isso significa que à medida que o tamanho do problema n aumenta, a taxa de crescimento do tempo de execução do algoritmo é igual à taxa de crescimento de (n), que é chamada de complexidade de tempo assintótica do algoritmo, ou complexidade de tempo, para abreviar.

3. Exemplos de análise de complexidade de tempo de algoritmos

[Exemplo 1.5] Exemplo de ordem constante. [x;s=0;) Ambas as frases têm frequência 1

[Exemplo 1.6] Exemplo de ordem linear. para(i=0;i<n;i )(x ;s=0;) considerar A frequência das duas instruções básicas no corpo do loop é A(n)=n, então a complexidade de tempo do algoritmo é T(n)=O(n), que é chamada de ordem linear.

[Exemplo 1.7] Exemplo de ordem quadrada. Calcular (1) x=0;y=0; (2) para(k=1;k<=n;k) n) (3) x; (4) para (i=1;i<=n;i) (5) para(j=1;j<=n;j ) (6) você; Para instruções de loop, precisamos apenas considerar o número de execuções das instruções no corpo do loop. A instrução mais frequente no segmento do programa acima é (6) e sua frequência é f(n)=n2, portanto a complexidade do tempo. do algoritmo é T(n )=O(n2), chamada ordem quadrada.

4. Complexidade de tempo melhor, pior e média

A complexidade de tempo de um algoritmo no melhor caso é chamada de melhor complexidade de tempo, que se refere à quantidade mínima de cálculo possível do algoritmo; a complexidade de tempo do algoritmo no pior caso é chamada de pior complexidade de tempo, o que significa que o algoritmo A quantidade máxima possível de cálculo; a complexidade média de tempo de um algoritmo refere-se à média ponderada da quantidade de cálculo do algoritmo quando as instâncias de entrada aparecem com igual probabilidade em todas as circunstâncias possíveis.

1.4.4 Complexidade espacial do algoritmo

Em relação aos requisitos de espaço de armazenamento do algoritmo, semelhante à complexidade de tempo do algoritmo, usamos a complexidade assintótica do espaço (Complexidade do Espaço) como uma medida do espaço de armazenamento exigido pelo algoritmo, referida como complexidade do espaço. do tamanho do problema n, denotado como: um de Básico S(n)=O(f(n))