Computer science and information technology. Tree data structures (lecture notes)

Free technical library

Lecture notes, cheat sheets
Free library / Directory / Lecture notes, cheat sheets

Computer science and information technology. Tree data structures (lecture notes)

Lecture notes, cheat sheets

Directory / Lecture notes, cheat sheets

Comments on the article

Table of contents (expand)

Introduction to Computer Science (Informatics. Information. Presentation and processing of information. Number systems. Representation of numbers in a computer. Formalized concept of an algorithm)
Pascal language (Introduction to Pascal. Standard procedures and functions. Pascal operators)
Procedures and functions (The concept of an auxiliary algorithm. Procedures in Pascal. Functions in Pascal. Anticipatory descriptions and connection of subroutines. Directive)
Subroutines (Routine parameters. Subroutine parameter types. String type in Pascal. Procedures and functions for string type variables. Records. Sets)
Files (Files. File operations. Modules. Types of modules)
Dynamic memory (Reference data type. Dynamic memory. Dynamic variables. Working with dynamic memory. Untyped pointers)
Abstract data structures (Abstract data structures. Stacks. Queues)
Tree Data Structures (Tree data structures. Operations on trees. Examples of implementation of operations)
Counts (The concept of a graph. Methods of representing a graph. Representation of a graph by a list of incidences. Depth-first traversal algorithm for a graph. Representation of a graph as a list of lists. Breadth-first traversal algorithm for a graph)
Object data type (Object type in Pascal. The concept of an object, its description and use. Inheritance. Creating instances of objects. Components and scope)
Methods (Methods. Constructors and destructors. Destructors. Virtual methods. Object data fields and formal method parameters)
Object Type Compatibility (Encapsulation. Extensible objects. Object type compatibility)
Assembler (About assembler. Microprocessor software model. User registers. General purpose registers. Segment registers. Status and control registers)
Registers (Microprocessor system registers. Control registers. System address registers. Debug registers)
Assembly programs (Assembler program structure. Assembler syntax. Comparison operators. Operators and their precedence. Simplified segment definition directives. Identifiers created by the MODEL directive. Memory models. Memory model modifiers)
Assembly Instruction Structures (Structure of a machine instruction. Methods for specifying instruction operands. Addressing methods)
commands (Data transfer commands. Arithmetic commands)
Control Transfer Commands (Logical commands. Truth table for logical negation. Truth table for logical inclusive OR. Truth table for logical AND. Truth table for logical exclusive OR. Meaning of abbreviations in the jcc command name. List of conditional jump commands for the command. Conditional jump commands and flags)

LECTURE № 8. Abstract data structures

1. Abstract data structures

Structured data types, such as arrays, sets, and records, are static structures because their sizes do not change during the entire execution of the program.

It is often required that data structures change their sizes in the course of solving a problem. Such data structures are called dynamic. These include stacks, queues, lists, trees, etc.

Description of dynamic structures with the help of arrays, records and files leads to wasteful use of computer memory and increases the time for solving problems.

Each component of any dynamic structure is a record containing at least two fields: one field of type "pointer", and the second - for data placement. In general, a record may contain not one, but several pointers and several data fields. A data field can be a variable, an array, a set, or a record.

If the pointing part contains the address of one element of the list, then the list is called unidirectional (or singly linked). If it contains two components, then it is doubly connected. You can perform various operations on lists, for example:

1) adding an element to the list;

2) removing an element from the list with a given key;

3) search for an element with a given value of the key field;

4) sorting the elements of the list;

5) division of the list into two or more lists;

6) combining two or more lists into one;

7) other operations.

However, as a rule, the need for all operations in solving various problems does not arise. Therefore, depending on the basic operations that need to be applied, there are different types of lists. The most popular of these are stack and queue.

2. Stacks

A stack is a dynamic data structure, the addition of a component to which and the removal of a component from which are made from one end, called the top of the stack. The stack works on the principle of LIFO (Last-In, First-Out) - "Last in, first out".

There are usually three operations performed on stacks:

1) initial formation of the stack (record of the first component);

2) adding a component to the stack;

3) selection of the component (deletion).

To form a stack and work with it, you must have two variables of the "pointer" type, the first of which determines the top of the stack, and the second is auxiliary.

Example. Write a program that forms a stack, adds an arbitrary number of components to it, and then reads all the components and displays them on the display screen. Take a character string as data. Data input - from the keyboard, a sign of the end of input - a string of characters END.

Program STACK;

uses Crt;

type

Alpha = String[10];

PComp = ^Comp;

Comp = record

SD : Alfa

pNext : PComp

end;

var

pTop:PComp;

sc: Alfa;

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

begin

New(pTop);

pTop^.pNext := NIL;

pTop^.sD := sC;

end;

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

var pAux : PComp;

begin

NEW(pAux);

pAux^.pNext := pTop;

pTop := pAux;

pTop^.sD := sC;

end;

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

begin

sC := pTop^.sD;

pTop := pTop^.pNext;

end;

begin

Clrscr;

writeln(' ENTER STRING ');

readln(sC);

CreateStack(pTop, sc);

repeat

writeln(' ENTER STRING ');

readln(sC);

AddComp(pTop, sc);

until sC = 'END';

writeln('****** OUTPUT ******');

repeat

DelComp(pTop, sc);

writeln(sC);

until pTop = NIL;

end.

3. Queues

A queue is a dynamic data structure where a component is added at one end and retrieved at the other end. The queue works on the principle of FIFO (First-In, First-Out) - "First in, first served".

To form a queue and work with it, it is necessary to have three variables of the pointer type, the first of which determines the beginning of the queue, the second - the end of the queue, the third - auxiliary.

Example. Write a program that forms a queue, adds an arbitrary number of components to it, and then reads all the components and displays them on the display screen. Take a character string as data. Data input - from the keyboard, a sign of the end of input - a string of characters END.

ProgramQUEUE;

uses Crt;

type

Alpha = String[10];

PComp = ^Comp;

Comp = record

SD : Alfa

pNext : PComp;

end;

var

pBegin, pEnd : PComp;

sc: Alfa;

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

begin

New(pBegin);

pBegin^.pNext := NIL;

pBegin^.sD := sC;

pEnd := pBegin;

end;

Procedure Add ProcedureQueue(var pEnd : PComp; var sC : Alfa);

var pAux : PComp;

begin

New(pAux);

pAux^.pNext := NIL;

pEnd^.pNext := pAux;

pEnd := pAux;

pEnd^.sD := sC;

end;

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

begin

sC := pBegin^.sD;

pBegin := pBegin^.pNext;

end;

begin

Clrscr;

writeln(' ENTER STRING ');

readln(sC);

CreateQueue(pBegin, pEnd, sc);

repeat

writeln(' ENTER STRING ');

readln(sC);

AddQueue(pEnd, sc);

until sC = 'END';

writeln(' ***** DISPLAY RESULTS *****');

repeat

DelQueue(pBegin, sc);

writeln(sC);

until pBegin = NIL;

end.

Author: Tsvetkova A.V.

<< Back: Abstract data structures (Abstract data structures. Stacks. Queues)

>> Forward: Counts (The concept of a graph. Methods of representing a graph. Representation of a graph by a list of incidences. Depth-first traversal algorithm for a graph. Representation of a graph as a list of lists. Breadth-first traversal algorithm for a graph)

We recommend interesting articles Section Lecture notes, cheat sheets:

▪ Legal psychology. Lecture notes

▪ Consumer behavior. Crib

▪ History of domestic state and law. Crib

See other articles Section Lecture notes, cheat sheets.

Read and write useful comments on this article.

<< Back

Latest news of science and technology, new electronics:

The existence of an entropy rule for quantum entanglement has been proven 09.05.2024

Quantum mechanics continues to amaze us with its mysterious phenomena and unexpected discoveries. Recently, Bartosz Regula from the RIKEN Center for Quantum Computing and Ludovico Lamy from the University of Amsterdam presented a new discovery that concerns quantum entanglement and its relation to entropy. Quantum entanglement plays an important role in modern quantum information science and technology. However, the complexity of its structure makes understanding and managing it challenging. Regulus and Lamy's discovery shows that quantum entanglement follows an entropy rule similar to that for classical systems. This discovery opens new perspectives in the field of quantum information science and technology, deepening our understanding of quantum entanglement and its connection to thermodynamics. The results of the study indicate the possibility of reversibility of entanglement transformations, which could greatly simplify their use in various quantum technologies. Opening a new rule ... >>

Mini air conditioner Sony Reon Pocket 5 09.05.2024

Summer is a time for relaxation and travel, but often the heat can turn this time into an unbearable torment. Meet a new product from Sony - the Reon Pocket 5 mini-air conditioner, which promises to make summer more comfortable for its users. Sony has introduced a unique device - the Reon Pocket 5 mini-conditioner, which provides body cooling on hot days. With it, users can enjoy coolness anytime, anywhere by simply wearing it around their neck. This mini air conditioner is equipped with automatic adjustment of operating modes, as well as temperature and humidity sensors. Thanks to innovative technologies, Reon Pocket 5 adjusts its operation depending on the user's activity and environmental conditions. Users can easily adjust the temperature using a dedicated mobile app connected via Bluetooth. Additionally, specially designed T-shirts and shorts are available for convenience, to which a mini air conditioner can be attached. The device can oh ... >>

Energy from space for Starship 08.05.2024

Producing solar energy in space is becoming more feasible with the advent of new technologies and the development of space programs. The head of the startup Virtus Solis shared his vision of using SpaceX's Starship to create orbital power plants capable of powering the Earth. Startup Virtus Solis has unveiled an ambitious project to create orbital power plants using SpaceX's Starship. This idea could significantly change the field of solar energy production, making it more accessible and cheaper. The core of the startup's plan is to reduce the cost of launching satellites into space using Starship. This technological breakthrough is expected to make solar energy production in space more competitive with traditional energy sources. Virtual Solis plans to build large photovoltaic panels in orbit, using Starship to deliver the necessary equipment. However, one of the key challenges ... >>

Random news from the Archive

British nutrition is deteriorating 11.09.2006

According to British statistics, the quality of food eaten by the British has deteriorated significantly since the 40s of the last century.

Over 60 years, the iron content in an average steak has decreased by 55%, calcium - by 4%, magnesium - by 7%. The content of iron in milk decreased by 62%, calcium - by 21%. Cheddar cheese is 38% magnesium, 9% calcium and 47% iron.

In some cases, these changes can be explained by new, more rigorous and accurate methods of analysis, changed methods of processing, storage and transportation, but in general, as environmentalists suggest, the changes for the worse are associated with the transition to intensive agriculture.

Farmers do not wait for the soil to restore its nutritional properties and fertility under fallow, but stuff it with chemical fertilizers that do not contain many trace elements important for plants and humans.

Other interesting news:

▪ Jurassic crickets singing bass

▪ Sea lions trained to play video games

▪ Silicon nanotube anodes triple the capacity of lithium-ion batteries

▪ New world speed record for cars

▪ The most dangerous countries

News feed of science and technology, new electronics

Interesting materials of the Free Technical Library:

▪ site section Acoustic systems. Article selection

▪ article Cry with a great voice. Popular expression

▪ article What is required for glass production? Detailed answer

▪ article Catamaran Princess Frog. Personal transport

▪ article Welding from an electric motor. Encyclopedia of radio electronics and electrical engineering

▪ article Powerful IF 38 MHz. Encyclopedia of radio electronics and electrical engineering

Leave your comment on this article:

All languages of this page

Home page | Library | Articles | Website map | Site Reviews