Информатика и информационные технологии. Древовидные структуры данных (конспект лекций)

Biblioteca técnica gratuita

RESUMO DA AULA, CRIBS
Biblioteca gratuita / Diretório / Notas de aula, folhas de dicas

Информатика и информационные технологии. Древовидные структуры данных (конспект лекций)

Notas de aula, folhas de dicas

Diretório / Notas de aula, folhas de dicas

Comentários do artigo

Índice (expandir)

Introdução à Ciência da Computação (Informática. Informação. Apresentação e processamento de informação. Sistemas numéricos. Representação de números num computador. Conceito formalizado de algoritmo)
Linguagem Pascal (Introdução ao Pascal. Procedimentos e funções padrão. Operadores Pascal)
Procedimentos e funções (O conceito de algoritmo auxiliar. Procedimentos em Pascal. Funções em Pascal. Descrições antecipatórias e conexão de sub-rotinas. Diretiva)
Sub-rotinas (Parâmetros de rotina. Tipos de parâmetros de sub-rotina. Tipo string em Pascal. Procedimentos e funções para variáveis do tipo string. Registros. Conjuntos)
Arquivos (Arquivos. Operações de arquivo. Módulos. Tipos de módulos)
Memória dinâmica (Tipo de dados de referência. Memória dinâmica. Variáveis dinâmicas. Trabalhando com memória dinâmica. Ponteiros não digitados)
Estruturas de dados abstratas (Estruturas de dados abstratas. Pilhas. Filas)
Estruturas de dados em árvore (Estruturas de dados em árvore. Operações em árvores. Exemplos de implementação de operações)
Contagens (O conceito de gráfico. Métodos de representação de um gráfico. Representação de um gráfico por uma lista de incidências. Algoritmo de travessia em profundidade para um gráfico. Representação de um gráfico como uma lista de listas. Algoritmo de travessia em largura para um gráfico )
Tipo de dados do objeto (Tipo de objeto em Pascal. O conceito de objeto, sua descrição e uso. Herança. Criação de instâncias de objetos. Componentes e escopo)
Métodos (Métodos. Construtores e destruidores. Destruidores. Métodos virtuais. Campos de dados de objetos e parâmetros de métodos formais)
Compatibilidade do tipo de objeto (Encapsulamento. Objetos extensíveis. Compatibilidade de tipo de objeto)
Montador (Sobre assembler. Modelo de software de microprocessador. Registros de usuário. Registros de uso geral. Registros de segmento. Registros de status e controle)
Registros (Registros do sistema microprocessador. Registros de controle. Registros de endereço do sistema. Registros de depuração)
Programas de montagem (Estrutura do programa Assembler. Sintaxe Assembler. Operadores de comparação. Operadores e sua precedência. Diretivas simplificadas de definição de segmento. Identificadores criados pela diretiva MODEL. Modelos de memória. Modificadores de modelo de memória)
Estruturas de instruções de montagem (Estrutura de uma instrução de máquina. Métodos para especificar operandos de instrução. Métodos de endereçamento)
Equipes (Comandos de transferência de dados. Comandos aritméticos)
Comandos de transferência de controle (Comandos lógicos. Tabela verdade para negação lógica. Tabela verdade para OR lógico inclusivo. Tabela verdade para AND lógico. Tabela verdade para OR exclusivo lógico. Significado das abreviaturas no nome do comando jcc. Lista de comandos de salto condicional para o comando. Salto condicional comandos e sinalizadores)

PALESTRA № 8. Estruturas de dados abstratas

1. Estruturas de dados abstratas

Tipos de dados estruturados, como arrays, conjuntos e registros, são estruturas estáticas porque seus tamanhos não mudam durante toda a execução do programa.

Muitas vezes, é necessário que as estruturas de dados mudem seus tamanhos no decorrer da resolução de um problema. Essas estruturas de dados são chamadas de dinâmicas. Estes incluem pilhas, filas, listas, árvores, etc.

A descrição de estruturas dinâmicas com a ajuda de arrays, registros e arquivos leva ao desperdício de memória do computador e aumenta o tempo de resolução de problemas.

Cada componente de qualquer estrutura dinâmica é um registro contendo pelo menos dois campos: um campo do tipo "ponteiro" e o segundo - para posicionamento de dados. Em geral, um registro pode conter não um, mas vários ponteiros e vários campos de dados. Um campo de dados pode ser uma variável, uma matriz, um conjunto ou um registro.

Se a parte indicadora contiver o endereço de um elemento da lista, a lista será chamada de unidirecional (ou vinculada individualmente). Se contiver dois componentes, estará duplamente conectado. Você pode realizar várias operações em listas, por exemplo:

1) adicionar um elemento à lista;

2) remover um elemento da lista com uma determinada chave;

3) procurar um elemento com um determinado valor do campo chave;

4) ordenação dos elementos da lista;

5) divisão da lista em duas ou mais listas;

6) combinar duas ou mais listas em uma;

7) outras operações.

No entanto, como regra, não surge a necessidade de todas as operações na resolução de vários problemas. Portanto, dependendo das operações básicas que precisam ser aplicadas, existem diferentes tipos de listas. Os mais populares são pilha e fila.

2. Pilhas

Uma pilha é uma estrutura de dados dinâmica, a adição de um componente ao qual e a remoção de um componente do qual são feitas de uma extremidade, chamada de topo da pilha. A pilha funciona com o princípio LIFO (Last-In, First-Out) - "Last in, first out".

Geralmente, há três operações executadas em pilhas:

1) formação inicial da pilha (registro do primeiro componente);

2) adicionar um componente à pilha;

3) seleção do componente (exclusão).

Para formar uma pilha e trabalhar com ela, você deve ter duas variáveis do tipo "ponteiro", sendo que a primeira determina o topo da pilha e a segunda é auxiliar.

Exemplo. Escreva um programa que forme uma pilha, adicione um número arbitrário de componentes a ela e, em seguida, leia todos os componentes e os exiba na tela de exibição. Tome uma cadeia de caracteres como dados. Entrada de dados - do teclado, um sinal do fim da entrada - uma seqüência de caracteres END.

Programa PILHA;

usa Crt;

tipo

Alfa = Cadeia[10];

PComp = ^Comp;

Comp = registro

SD: Alfa;

pPróximo: PComp

end;

var

pTop: PComp;

sc: Alfa;

Create ProcedureStack(var pTop : PComp; var sC : Alfa);

começar

Novo(pTop);

pTopo^.pPróximo := NIL;

pTop^.sD := sC;

end;

Adicione ProcedureComp(var pTop : PComp; var sC : Alfa);

var pAux : PComp;

começar

NOVO(pAux);

pAux^.pNext := pTop;

pTop := pAux;

pTop^.sD := sC;

end;

Procedimento DelComp(var pTop : PComp; var sC : ALFA);

começar

sC := pTop^.sD;

pTopo := pTopo^.pPróximo;

end;

começar

Clrscr;

writeln('DIGITE UMA STRING');

readln(sc);

CreateStack(pTop, sc);

repetir

writeln('DIGITE UMA STRING');

readln(sc);

AddComp(pTop, sc);

até sC = 'FIM';

writeln('******* SAÍDA *****');

repetir

DelComp(pTop, sc);

escrever(sC);

até pTop = NIL;

final.

3. Filas

Uma fila é uma estrutura de dados dinâmica onde um componente é adicionado em uma extremidade e recuperado na outra extremidade. A fila funciona segundo o princípio FIFO (First-In, First-Out) - "Primeiro a entrar, primeiro a ser servido".

Para formar uma fila e trabalhar com ela, é necessário ter três variáveis do tipo ponteiro, a primeira das quais determina o início da fila, a segunda - o fim da fila, a terceira - auxiliar.

Exemplo. Escreva um programa que forme uma fila, adicione um número arbitrário de componentes a ela e, em seguida, leia todos os componentes e os exiba na tela de exibição. Tome uma cadeia de caracteres como dados. Entrada de dados - a partir do teclado, o sinal do fim da entrada - uma seqüência de caracteres END.

Programa FILA;

usa Crt;

tipo

Alfa = Cadeia[10];

PComp = ^Comp;

Comp = registro

SD: Alfa;

pNext: PComp;

end;

var

pBegin, pEnd: PComp;

sc: Alfa;

Create ProcedureQueue(var pBegin,pEnd:PComp; var sC:Alfa);

começar

Novo(pBegin);

pBegin^.pNext := NIL;

pBegin^.sD := sC;

pFim := pInício;

end;

Procedimento AddQueue(var pEnd : PComp; var sC : Alfa);

var pAux : PComp;

começar

Novo(pAux);

pAux^.pPróximo := NIL;

pEnd^.pNext := pAux;

pEnd := pAux;

pEnd^.sD := sC;

end;

Procedimento DelQueue(var pBegin : PComp; var sC : Alfa);

começar

sC := pBegin^.sD;

pBegin := pBegin^.pNext;

end;

começar

Clrscr;

writeln('DIGITE UMA STRING');

readln(sc);

CreateQueue(pBegin, pEnd, sc);

repetir

writeln('DIGITE UMA STRING');

readln(sc);

AddQueue(pEnd, sc);

até sC = 'FIM';

writeln(' ***** EXIBIR RESULTADOS *****');

repetir

DelQueue(pBegin, sc);

escrever(sC);

até pInício = NIL;

final.

Autor: Tsvetkova A.V.

<< Voltar: Estruturas de dados abstratas (Estruturas de dados abstratas. Pilhas. Filas)

>> Encaminhar: Contagens (O conceito de gráfico. Métodos de representação de um gráfico. Representação de um gráfico por uma lista de incidências. Algoritmo de travessia em profundidade para um gráfico. Representação de um gráfico como uma lista de listas. Algoritmo de travessia em largura para um gráfico )

Recomendamos artigos interessantes seção Notas de aula, folhas de dicas:

▪ Psicologia Jurídica. Notas de aula

▪ Comportamento do consumidor. Berço

▪ História do Estado interno e do direito. Berço

Veja outros artigos seção Notas de aula, folhas de dicas.

Leia e escreva útil comentários sobre este artigo.

<< Voltar

Últimas notícias de ciência e tecnologia, nova eletrônica:

A existência de uma regra de entropia para o emaranhamento quântico foi comprovada 09.05.2024

A mecânica quântica continua a nos surpreender com seus fenômenos misteriosos e descobertas inesperadas. Recentemente, Bartosz Regula do Centro RIKEN de Computação Quântica e Ludovico Lamy da Universidade de Amsterdã apresentaram uma nova descoberta que diz respeito ao emaranhamento quântico e sua relação com a entropia. O emaranhamento quântico desempenha um papel importante na moderna ciência e tecnologia da informação quântica. No entanto, a complexidade da sua estrutura torna a sua compreensão e gestão um desafio. A descoberta de Regulus e Lamy mostra que o emaranhamento quântico segue uma regra de entropia semelhante à dos sistemas clássicos. Esta descoberta abre novas perspectivas na ciência e tecnologia da informação quântica, aprofundando a nossa compreensão do emaranhamento quântico e a sua ligação à termodinâmica. Os resultados do estudo indicam a possibilidade de reversibilidade das transformações de emaranhamento, o que poderia simplificar muito seu uso em diversas tecnologias quânticas. Abrindo uma nova regra ... >>

Mini ar condicionado Sony Reon Pocket 5 09.05.2024

O verão é uma época de relaxamento e viagens, mas muitas vezes o calor pode transformar essa época em um tormento insuportável. Conheça um novo produto da Sony – o minicondicionador Reon Pocket 5, que promete deixar o verão mais confortável para seus usuários. A Sony lançou um dispositivo exclusivo - o minicondicionador Reon Pocket 5, que fornece resfriamento corporal em dias quentes. Com ele, os usuários podem desfrutar do frescor a qualquer hora e em qualquer lugar, simplesmente usando-o no pescoço. Este miniar condicionado está equipado com ajuste automático dos modos de operação, além de sensores de temperatura e umidade. Graças a tecnologias inovadoras, o Reon Pocket 5 ajusta o seu funcionamento em função da atividade do utilizador e das condições ambientais. Os usuários podem ajustar facilmente a temperatura usando um aplicativo móvel dedicado conectado via Bluetooth. Além disso, camisetas e shorts especialmente desenhados estão disponíveis para maior comodidade, aos quais um mini ar condicionado pode ser acoplado. O dispositivo pode, oh ... >>

Energia do espaço para Starship 08.05.2024

A produção de energia solar no espaço está se tornando mais viável com o advento de novas tecnologias e o desenvolvimento de programas espaciais. O chefe da startup Virtus Solis compartilhou sua visão de usar a Starship da SpaceX para criar usinas orbitais capazes de abastecer a Terra. A startup Virtus Solis revelou um ambicioso projeto para criar usinas de energia orbitais usando a Starship da SpaceX. Esta ideia poderia mudar significativamente o campo da produção de energia solar, tornando-a mais acessível e barata. O cerne do plano da startup é reduzir o custo de lançamento de satélites ao espaço usando a Starship. Espera-se que este avanço tecnológico torne a produção de energia solar no espaço mais competitiva com as fontes de energia tradicionais. A Virtual Solis planeja construir grandes painéis fotovoltaicos em órbita, usando a Starship para entregar os equipamentos necessários. Contudo, um dos principais desafios ... >>

Notícias aleatórias do Arquivo

A nutrição britânica está se deteriorando 11.09.2006

De acordo com estatísticas britânicas, a qualidade dos alimentos consumidos pelos britânicos se deteriorou significativamente desde a década de 40.

Ao longo de 60 anos, o teor de ferro em um bife médio diminuiu 55%, cálcio - 4%, magnésio - 7%. O teor de ferro no leite diminuiu 62%, cálcio - 21%. O queijo cheddar tem 38% de magnésio, 9% de cálcio e 47% de ferro.

Em alguns casos, essas mudanças podem ser explicadas por novos métodos de análise, mais rigorosos e precisos, métodos alterados de processamento, armazenamento e transporte, mas em geral, como sugerem os ambientalistas, as mudanças para pior estão associadas à transição para a agricultura intensiva .

Os agricultores não esperam que o solo restaure suas propriedades nutricionais e fertilidade em pousio, mas o enchem de fertilizantes químicos que não contêm muitos oligoelementos importantes para as plantas e os seres humanos.

Outras notícias interessantes:

▪ Grilos jurássicos cantando baixo

▪ Leões marinhos treinados para jogar videogame

▪ Ânodos de nanotubos de silício triplicam a capacidade das baterias de íons de lítio

▪ Novo recorde mundial de velocidade para carros

▪ Os países mais perigosos

Feed de notícias de ciência e tecnologia, nova eletrônica

Materiais interessantes da Biblioteca Técnica Gratuita:

▪ seção do site Sistemas acústicos. Seleção de artigos

▪ artigo Chore com uma grande voz. expressão popular

▪ artigo O que é necessário para a produção de vidro? Resposta detalhada

▪ artigo Catamaran Princess Frog. transporte pessoal

▪ artigo Soldagem a partir de um motor elétrico. Enciclopédia de rádio eletrônica e engenharia elétrica

▪ artigo Poderoso IF 38 MHz. Enciclopédia de rádio eletrônica e engenharia elétrica

Deixe seu comentário neste artigo:

Todos os idiomas desta página

Página principal | Biblioteca | Artigos | Mapa do Site | Revisões do site