Чем стек отличается от структуры данных линейный список
Перейти к содержимому

Чем стек отличается от структуры данных линейный список

  • автор:

Чем стек отличается от структуры данных линейный список?

Author24 — интернет-сервис помощи студентам

Чем стек отличается от структуры данных линейный список? Немного не понимаю что лучше использовать, обучаюсь С++ немного.

Лучшие ответы ( 1 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Чем отличается список от структуры
Чем отличается список от структуры?

Реализовать структуры данных «линейный список» и «циклический список»
Реализовать структуры данных «линейный список» и «циклический список». Дополнительно программа.

Реализовать структуры данных «линейный список»
Ребят помогите написать прогу! задание тут: http://ifolder.ru/29432716 ( извините что так, но.

Структуры данных – связный список, стек, очередь
Добрый день! Задали лабу по программированию, но в ней 2 странички текста без какой-либо толковой.

Эксперт С++

8739 / 4317 / 960
Регистрация: 15.11.2014
Сообщений: 9,760

Лучший ответ

Сообщение было отмечено luckoff как решение

Решение

ЦитатаСообщение от luckoff Посмотреть сообщение

Чем стек отличается от структуры данных линейный список?
стек заточен под задачу FIFO (первым пришёл — первым ушёл)
а список — просто список.
2512 / 1234 / 456
Регистрация: 08.11.2016
Сообщений: 3,383

ЦитатаСообщение от hoggy Посмотреть сообщение

стек заточен под задачу FIFO
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

Чем класс отличается от структуры?
Господа, скажите еще пожалуйста, чем класс отличается от структуры.

Реализовать стек, используя линейный список
Необходимо реализовать стек с помощью линейного списка, шаблонного типа. Вот код программы: .

Однонаправленный линейный список типа СТЕК
Всем здравствуйте! Прошу помощи с заданием. Написать программу по созданию, добавлению.

Стек как линейный список, вывести на печать два последних элемента
Здравствуйте, нужна программа — стек как линейный список, вывести на печать два последних элемента.

Или воспользуйтесь поиском по форуму:

Структуры данных

Теоретический материал: стеки, очереди, кольца (Паскаль)

Стек. Отличия стека от списка. Основные операции со стеком

Сейчас Вы познакомитесь с одной из разновидностей обычного линейного списка – стеком. Этот вид списка очень часто используется в программировании. Стек – это линейный список, в котором добавление новых элементов и удаление существующих производится только с одного конца, называемого вершиной стека. Стек часто называют структурой LIFO (сокращение LIFO означает Last In – First Out, т.е. последним пришел – первым вышел). Это сокращение помогает запомнить механизм работы стека. Изобразим стек графически: При программировании на Паскале стек чаще всего реализуется в виде однонаправленного списка. Каждый элемент структуры содержит указатель на следующий. Однако, к этому виду списка, по определению, неприменима операция обхода элементов. Доступ возможен только к верхнему элементу структуры. Стек предполагает вставку и удаление элементов, поэтому он является динамической, постоянно меняющейся структурой. Стеки довольно часто встречаются в практической жизни. Простой пример: детская пирамидка. Процесс ее сборки и разборки подобен процессу функционирования стека. Итак, стек – это такой список, добавление или извлечение элементов которого происходит с начала и только с начала (или, возможно, с конца и только с конца) списка. Значением указателя, представляющего стек, является ссылка на вершину стека, и каждый элемент стека содержит поле ссылки на соседний, «нижний» элемент. Таким образом, описать стек можно следующим образом:

Если стек пуст, то значение указателя равно Nil. Рассмотрим возможные операции со стеком.

Занесение элемента в стек

Занесение элемента в стек производится аналогично вставке нового элемента в начало списка. Процедура занесения элемента в стек должна содержать два параметра: первый задает вершину стека, в который нужно занести элемент, второй – заносимое значение элемента стека. Процедура формирования стека будет иметь следующий вид:

Procedure FormStack;
Var
Stack : EXST;
Digit : integer;
Procedure writeStack(Var u : EXST; Digit : integer);
Var
x : EXST;
Begin
new(x);
x^.Data := Digit;
x^.Next := u;
u := x;
End;
Begin
Stack := Nil;
writeln(‘Введите элементы стека. Окончание ввода – 0’);
read(Digit);
while Digit <> 0 do
begin
writeStack(Stack, Digit);
read(Digit);
end;
End;

Извлечение элемента из стека

В результате выполнения этой операции некоторой переменной i должно быть присвоено значение первого элемента стека, и значение указателя на начало списка должно быть перенесено на следующий элемент стека.

Procedure readStack(Var u : EXST; Var i : integer);
Var
x : EXST;
Begin
i := u^.Data;
x := u;
u := u^.Next;
dispose(x);
End.

Недостатком описанной процедуры является предположение о том, что стек не пуст. Для его исправления следует разработать логическую функцию, определяющую, пуст ли обрабатываемый стек.

Function FreeStack(u : EXST) : boolean;

Задание. Описать функцию и закончить программу, для чего описать процедуру вывода значений элементов стека на экран (она аналогична выводу списка). Протестировать программу, дополнить комментарием.

Примеры решения задач

Пример 1. Используя стек, напечатать содержимое текстового файла, выписывая литеры каждой его строки в обратном порядке.

Program MordovskihK;
Type
EXST = ^ST;
ST = record
Data : char;
Next : EXST;
End;
Var
Stack : EXST;
i : integer;
f : text;
Stroka : string;
c : char;
Procedure writeStack(Var u : EXST; Simvol : char);
Var
x : EXST;
Begin
new(x);
x^.Data := Simvol;
x^.Next := u;
u := x;
End;
Procedure Print(Var u : EXST);
Begin
while u <> Nil do
Begin
write (u^.Data);
u := u^.Next;
End;
End;
Begin
Stack := Nil;
Assign(f, ‘c:\autoexec.bat’);
Reset(f);
while Not Eof(f) do
Begin
readln (f, Stroka);
For i := 1 to Length(Stroka) do
writeStack(Stack, Stroka[i]);
Print(Stack);
writeln;
End;
close(f);
End.

Пример 2. Написать программу, проверяющую своевременность закрытия скобок в строке символов. Для решения задачи определим стек, элементами которого являются символы:

Type
EXST = ^ST;
ST = record
Data : char;
Next : EXST;
End;

Будем двигаться по строке а : string до ее конца. Если в процессе просмотра встретится одна из открывающих скобок (

while (i<>Length(a)) and f do .

Осталось выяснить, как определить, соответствует ли очередная закрывающая скобка скобке, находящейся в вершине стека. Можно заметить, что коды соответствующих друг другу скобок отличаются не более чем на 2, что можно проверить с помощью функции Ord(x)):

< >123–125
[ ] 91–93
( ) 40–41,

причем код открывающей скобки меньше. Таким образом, можно записать следующее условие соответствия:

if (Ord(a[i])–Ord(stack^.Data)) then
. . .

А теперь просмотрите полный текст программы:

Program Skobki;
Type
EXST = ^ST;
ST = record
Data : char;
Next : EXST;
end;
Var
a : string;
f : boolean;
i : integer;
Procedure writeStack(Var x1 : EXST; c : char);
Var
u : EXST;
Begin
new(u);
u^.Data := c;
u^.Next := x1;
x1 := u;
End;
Procedure DelStack(Var x1 : EXST);
Var
u : EXST;
Begin
u := x1;
x1 := x1^.Next;
dispose(u);
End;
Procedure Solve(a : string);
Var
Stack : EXST;
Begin
Stack := Nil;
i := 1;
while (i <=Length(a)) and f do
begin
if (a[i]='(‘) or (a[i]=’ <') or (a[i]='[')
then
writeStack(Stack , a[i])
else
if (a[i]=’)’) or (a[i]=’>’) or (a[i]=’]’)
then
if (Stack <> Nil) And (Ord(a[i]) — Ord(Stack ^.Data) then
DelStack(Stack)
else
f := False;
Inc(i);
end;
end;
Begin
writeln(‘Введите строку’);
readln(a);
f := True;
if a<>»
then
begin
Solve(a);
if f
then
writeln(‘Все скобки расставлены верно’)
else
writeln(‘Скобка ‘,a[i-1],’ закрыта преждевременно’);
end
else
writeln(‘Строка пуста’);
readln;
End.

Линейные структуры данных

(англ. ) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним. Стек должен поддерживать следующие операции: push Добавить (положить) в конец стека новый элемент
pop Извлечь из стека последний элемент
top Узнать значение последнего элемента (не удаляя его)
size Узнать количество элементов в стеке
clear Очистить стек (удалить из него все элементы)

Стек можно хранить двумя способами: либо массивом некоторого фиксированного размера, либо при помощи ссылочной реализации.

Структура данных Stack

Для работы со стеком создадим структуру данных Stack . Поскольку элементами стека могут быть любые данные (числа, строки и т.д.), то эта структура будет шаблоном (template) над произвольным типом данных T . Вот каким должен быть интерфейс стека:

template struct Stack < Stack(); // Конструктор ~Stack(); // Деструктор void push(T d); // Добавить в стек новый элемент T pop(); // Удалить из стека последний элемент // и вернуть его значение T top(); // Вернуть значение последнего элемента int size(); // Вернуть количество элементов в стеке void clear(); // Очистить стек >;

Реализация на базе массива

В простейшем случае для хранения элементов стека можно использовать массив. Элементы стека будем класть в начало стека. Заведем два поля в структуре: поле m_data — массив элементов стека и m_size — число элементов в стеке. Объявим их, как приватные члены класса.

private: T m_data[MAXSIZE]; int m_size;

Значение m_size инициализируем в конструкторе:

Stack ()

Добавление элементов в стек заключается в увеличении поля m_size и записи элемента в массив m_data :

void push(T val)

Оставшиеся методы реализовать также просто:

T top() < return m_data[m_size - 1]; >T pop() < --m_size; return m_data[m_size]; >void size() < return m_size; >void clear()

Массив переменного размера

Данная реализация имеет недостаток: размер стека фиксирован константой MAXSIZE . Попробуем сделать реализацию, в которой размер массива будет увеличиваться динамически. Для этого заменим статический массив m_data на указатель и будем динамически выделять память. Размер выделенной памяти (т.е. максимальное число элементов в стеке без увеличения его размера) будем хранить в поле m_maxsize . В конструкторе необходимо выделить память для хранения данных:

Stack()

В деструкторе нужно освободить выделенную память:

~Stack()

Создадим вспомогательный метод resize , выделяющий дополнительную память:

void resize(int newsize)

Теперь при добавлении нового элемента в стек проверим, не заполнен ли стек полностью. Если это произошло, то вызовем метод resize для увеличения размера стека:

void push(T val)

Ссылочная реализация стека

Другой способ реализации стека: ссылочная реализация. В ссылочной реализации стек хранится в виде последовательности отдельных элементов. Каждый элемент состоит из двух полей: данных и указателя на предыдущий элемент стека:

template struct StackElem < T m_data; StackElem* m_prev; >

В самой структуре Stack хранится число элементов в стеке m_size и указатель на последний элемент стека m_top :

private: int m_size; StackElem * m_top;

При создании стека нужно проинициализировать поле m_top нулевым указателем (указатель в “никуда” свидетельствует о том, что в стеке нет ни одного элемента:

Stack()

Чтобы вернуть значение последнего элемента в стеке, разыменуем указатель m_top и вернем поле m_data результирующей структуры:

T top() < return m_top ->m_data; >

Чтобы удалить верхний элемент в стеке нужно освободить занимаемую им память и передвинуть указатель:

void pop() < StackElemprev = m_top -> m_prev; delete m_top; m_top = prev; --m_size; >

Для добавления нового элемента необходимо выделить для него память и связать его с последним элементом стека:

void push(T val) < StackElemnew_top = new StackElem new_top -> m_data = val; new_top -> m_prev = m_top; m_top = new_top; ++m_size; >

Для очистки стека будем удалять из него элементы по одному, пока стек не пуст:

void clear() < while (m_size >0) pop(); >

Также в деструкторе нужно вызвать метод очистки стека, чтобы осводить всю выделенную память:

~Stack ()

Упражнения

A: Стек

Реализуйте структуру данных “стек“, релизовав все методы стека. Стек должен быть реализован в виде шаблона над произвольным типом данных. Стек должен иметь произвольный размер. Можно выбрать одну из двух реализаций: на базе динамического массива или ссылочную реализацию.

Программа получает на вход последовательность команд: push n Добавить в стек число n (значение n задается после команды). Программа должна вывести ok .
pop Удалить из стека последний элемент. Программа должна вывести его значение. Если стек пуст, то программа выводит error .
top Программа должна вывести значение последнего элемента, не удаляя его из стека. Если стек пуст, то программа выводит error .
size Программа должна вывести количество элементов в стеке.
clear Программа должна очистить стек и вывести ok .
exit Программа должна вывести bye и завершить работу.

При этом должна быть реализована двойная защита: вызов методов top и pop для пустого стека не должен приводить к обращению к несуществующим элементам массива m_data , а функция main должна выводить сообщение error , при считывании некорректной операции.

push 2 top pop size pop push 1 size exit
ok 2 2 0 error ok 1 bye

Очередь

Очередью (aнгл. )) называется структура данных, в которой элементы кладутся в конец, а извлекаются из начала. Таким образом, первым из очереди будет извлечен тот элемент, который будет добавлен раньше других.

Элементы очереди будем также хранить в массиве. При этом из очереди удаляется первый элемент, и, чтобы не сдвигать все элементы очереди, будем в отдельном поле m_start хранить индекс элемента массива, с которого начинается очередь. При удалении элементов, очередь будет «ползти» дальше от начала массива. Чтобы при этом не происходил выход за границы массива, замкнем массив в кольцо: будем считать, что за последним элементом массива следует первый.

Описание структуры очередь:

const int MAX_SIZE=1000; struct queue < int m_size; // Количество элементов в очереди int m_start; // Номер элемента, с которого начинается очередь int m_elems[MAX_SIZE]; // Массив для хранения элементов queue(); // Конструктор ~queue(); // Деструктор void push(int d); // Добавить в очередь новый элемент int pop(); // Удалить из очереди первый элемент // и вернуть его значение int front(); // Вернуть значение первого элемента int size(); // Вернуть количество элементов в очереди void clear(); // Очистить стек >;

B: очередь

Реализуйте очередь. Очередь поддерживает те же операции, что и стек, за исключением операции top , которая заменена операцией front .

Очередь должна быть реализована на базе закольцованного динамического массива.

Дек

Деком (англ. – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека: push_front Добавить (положить) в начало дека новый элемент
push_back Добавить (положить) в конец дека новый элемент
pop_front Извлечь из дека первый элемент
pop_back Извлечь из дека последний элемент
front Узнать значение первого элемента (не удаляя его)
back Узнать значение последнего элемента (не удаляя его)
size Узнать количество элементов в деке
clear Очистить дек (удалить из него все элементы)

С: дек

Аналогично заданиям A и B, но для дека.

Дек должен быть реализован при помощи ссылочной реализации.

Списки

Списки представляют собой последовательности элементов, в которые можно произвольно вставлять элементы и удалять элементы. Списки реализовываются в виде двусвязных ссылочных структур, поэтому в списках легко перемещаться от одного элемента к следующему и к предыдущему, но нельзя быстро перейти к элементу с заданным номером в списке (как в массиве).

D: двусвязный список

Реализуйте список, элементами которого являются целые числа.

Список состоит из произвольного числа элементов. Один из элементов списка будем называть текущим. Также в качестве текущего элемента может выступать фиктивный элемент, находящийся за последним элементом списка — будем называть его концом списка, это аналог итератора end() . Этот фиктивный элемент нужен для того, чтобы можно было добавлять элементы в конец списка.

В самом начале список пустой, а текущим элементом является конец списка.

Список поддерживает следующие операции: get Вывести значение текущего элемента. Если текущим является конец списка, то вывести error . set n Установить значение текущего элемента в n. Вывести ok или error , если текущим является конец списка. next Переместиться на один элемент в сторону конца списка. Вывести значение нового текущего элемента, или end , если текущим элементом стал конец списка, или error , если текущим элементом уже был конец списка. prev Переместиться на один элемент в сторону начала списка. Вывести значение нового текущего элемента или error , если текущим элементом был первый элемент списка.
insert n Вставить новый элемент перед текущим и задать ему значение n. Новый элемент становится текущим. Программа выводит ok .
erase Удалить текущий элемент. Программа выводит значение удаленного элемента или error , если текущим был конец списка. Текущим элементом становится элемент, следущий за текущим.
size Программа должна вывести количество элементов в списке.
clear Программа должна очистить список и вывести ok .
exit Программа должна вывести bye и завершить работу.

insert 1 insert 2 insert 3 next erase get set 4 prev prev erase next next insert 5 prev insert 6 next erase erase get size clear size exit
ok ok ok 2 2 1 ok 3 error 3 end error ok 4 ok 4 4 5 error 1 ok 0 bye

Бинарное дерево поиска

Реализуйте бинарное дерево поиска. Программа получает на вход последовательность чисел и строит из них бинарное дерево поиска. Элементы в деревья добавляются в соответствии с результатом поиска их места. Если элемент уже существует в дереве, добавлять его не надо. Балансировка дерева не производится.

Программа получает на вход последовательность натуральных чисел (типа int ). Последовательность завершается число 0, которое означает конец ввода, и добавлять его в дерево не надо.

Вот пример построенного дерева для последовательности 7 3 2 1 9 5 4 6 8 0 :

После построения дерева решите поставленную задачу.

E-1: Высота дерева

Выведите высоту полученного дерева (реализуйте рекурсивную процедуру, возвращающую высоту дерева).

7 3 2 1 9 5 4 6 8 0

E-2: Количество элементов

Подсчитайте количество элементов в получившемся дереве (реализуйте рекурсивную процедуру, возвращающую количество элементов в дереве).

1 2 3 1 0

E-3: Второй максимум

Выведите второй по величине элемент в построенном дереве. Гарантируется, что такой найдется.

7 3 2 1 9 5 4 6 8 0
1 1 1 2 2 2 0

E-4: Обход

Выведите все элементы полученного дерева в порядке возрастания. Удобней это делать при помощи рекурсивной процедуры.

7 3 2 1 9 5 4 6 8 0
1 2 3 4 5 6 7 8 9

E-5: Вывод листьев

Для полученного дерева выведите список всех листьев (вершин, не имеющих потомков) в порядке возрастания.

7 3 2 1 9 5 4 6 8 0
1 4 6 8

E-6: Вывод развилок

Для полученного дерева выведите список всех вершин, имеющих по два ребёнка, в порядке возрастания.

7 3 2 1 9 5 4 6 8 0
3 5 7

E-7: Вывод веток

Для полученного дерева выведите список всех вершин, имеющих только одного ребёнка, в порядке возрастания.

7 3 2 1 9 5 4 6 8 0

E-8: Сбалансированность

Дерево называется сбалансированным, если для любой его вершины высота левого и правого поддерева для этой вершины различаются не более чем на 1. Определите, является ли дерево сбалансированным, выведите слово YES или NO.

7 3 2 1 9 5 4 6 8 0
1 2 3 0

E-9: Подсчет элементов

По данной последовательности постройте дерево, запоминая для каждого элемента его значение и количество его повторений в последовательности.

Выведите на экран содержимое дерева в порядке возрастания, по одному элементу на строку. В каждой строке выводите значение элемента, затем, через пробел, укажите, сколько раз он встречается в исходной последовательности.

9 7 9 1 7 9 0
1 1
7 2
9 3

E-10: Удаление элементов

  1. Если у удаляемого элемента нет потомков, то он просто удаляется.
  2. Если у удаляемого элемента один потомок, то этот потомок становится на место удаляемого.
  3. Если у удаляемого элемента два потомка, то на место удаляемого элемента ставится минимальный элемент из его правого поддерева.

Программа получает на вход последовательность целых чисел, заверщающаяся числом 0. При этом положительное число \(+d\) обозначает, что в дерево нужно добавить элемент со значением \(d\) (возможно, что он уже есть в дереве).

Отрицательное число \(-d\) означает, что из дерева нужно удалить элемент со значением \(d\), вполне возможно, что в дереве такого элемента нет (тогда дерево не модифицируется).

После окончания ввода программа должна вывести все элементы в дереве в порядке возрастания. В одной строке выводится три числа: значение элемента, значение его левого потомка, значение его правого потомка. Если у элемента нет соответствующего потомка, то выводится число 0.

7 3 2 1 9 5 4 6 8 -2 -4 -7 0
1 0 0
3 1 5
5 0 6
6 0 0
8 3 9
9 0 0

Красно-черные деревья

Красно-черные деревья это бинарные деревья поиска, все операции с которыми (поиск, добавление, удаление) выполняются за логарифм от числа элементов в дереве. При этом высота дерева также поддерживается пропорциональной логарифму от числа элементов: это достигается за счет балансировки дерева — поворотов отдельных поддеревьев при добавлении и удалении элементов.

  1. Корень дерева всегда черный
  2. Если узел — красный, то оба его дочерних узла — черные.
  3. Для каждого узла все пути от него до листьев, являющихся его дочерними узлами, содержат одинаковое число черных узлов.

Для простоты реализации удобно считать, что все листья дерева — это фиктивные элементы, не хранящие данных, и они покрашены в черный цвет.

О том, как выполняются операции добавления и удаления в красно-черном дереве можно прочитать в книге Кормен, Лейзерсон, Ривест, Штайн, “Алгоритмы: построение и анализ”, глава 13.

F-1: Красно-черное дерево, добавление элементов

Реализуйте красно-черное дерево только с операцией добавления элементов.

Программа получает на вход последовательность целых чисел, заверщающаяся числом 0. Программа последовательно добавляет данные элементы в красно-черное дерево, осуществляя балансировку дерева при необходимости. Число 0 обозначает конец ввода, его добавлять не надо. Если число уже содержится в дереве, его добавлять не надо.

После окончания ввода программа должна вывести все элементы в дереве в порядке возрастания. В каждой строке выводится подряд через пробел: значение элемента, цвет этого элемента (один символ, либо R , либо B , что означает красный и черный цвет соответственно), значение его левого потомка, значение его правого потомка. Если у элемента нет соответствующего потомка, то выводится число 0.

1 2 3 4 5 6 7 8 9 10 0
1 B 0 0 2 B 1 3 3 B 0 0 4 B 2 6 5 B 0 0 6 B 5 8 7 B 0 0 8 R 7 9 9 B 0 10 10 R 0 0

F-2: Красно-черное дерево, удаление элементов

Реализуйте красно-черное дерево с операциями добавления и удаления элементов.

Формат входных данных аналогичен задаче E-10, формат выходных данных аналогичен задаче F-1.

Структуры данных. Типы структур данных

Структура данных — это «контейнер», который используется для хранения и организации данных по определенным правилам. Это способ упорядочивания данных на компьютере таким образом, чтобы к ним можно было эффективно получать доступ и вносить изменения.

В зависимости от требований и проекта важно выбрать оптимальную структуру данных. Например, если вы хотите хранить данные последовательно в памяти, то можно воспользоваться Массивом.

Примечание: Структура данных и типы данных немного различаются. Структура данных — это набор типов данных, упорядоченных в определенном порядке.

Типы структур данных

В основном, структуры данных делятся на два типа:

Линейные структуры данных.

Нелинейные структуры данных.

Рассмотрим их детально.

Линейные структуры данных

В линейных структурах данных элементы располагаются последовательно друг за другом. Поскольку элементы упорядочены в определенном порядке, данную структуру относительно легко создать и поддерживать. Однако с увеличением сложности программы линейные структуры данных уже могут быть не лучшим вариантом из-за операционных сложностей.

Рассмотрим наиболее популярные линейные структуры данных.

Структура данных Массив

В массиве элементы в памяти располагаются в непрерывной последовательности. Все элементы массива имеют одинаковый тип. Тип элементов, которые можно хранить в виде массивов, определяется языком программирования.

Массив, где каждый элемент представлен индексом

Структура данных Стек

В стеке элементы хранятся по принципу LIFO (сокр. от англ. «Last In, First Out»). Это означает, что последний элемент, добавленный в стек, удаляется первым.

Структура данных Очередь

В отличие от стека, очередь работает по принципу FIFO (сокр. от англ. «First In, First Out»), где первый элемент, помещенный в очередь, первым и удаляется.

Структура данных Связный список

В связном списке данные связаны через серию узлов. Каждый узел содержит элементы данных и адрес следующего узла. Посредством адреса и осуществляется «связывание».

Нелинейные структуры данных

В отличие от линейных структур данных, элементы в нелинейных структурах данных не расположены в какой-либо последовательности. Вместо этого они организованы иерархически, где один элемент связан с другим или сразу несколькими другими элементами.

Нелинейные структуры данных делятся на графовые и древовидные структуры данных.

Структура данных Граф

В графе каждый узел называется вершиной, а каждая вершина соединена с другими вершинами через ребра.

Пример структуры данных Граф

Древовидные структуры данных

Подобно графу, дерево также представляет собой набор вершин и ребер. Однако в древовидной структуре данных между двумя вершинами может быть только одно ребро.

Пример древовидной структуры данных

Популярные древовидные структуры данных:

Бинарное дерево (Binary Tree)

Двоичное дерево поиска (Binary Search Tree)

АВЛ-дерево (AVL Tree)

Красно-черное дерево (Red-Black Tree)

Различия между линейными и нелинейными структурами данных

Линейные структуры данных Нелинейные структуры данных
Элементы данных расположены в последовательном порядке, один за другим. Элементы данных расположены в иерархическом (непоследовательном) порядке.
Все элементы находятся на одном уровне. Элементы данных находятся на разных уровнях.
Всю цепочку элементов можно последовательно пройти за один проход. Всю цепочку данных нельзя пройти за один проход. Требуется несколько проходов.
Память используется неэффективно. Память используется более эффективно.
Время доступа к элементам резко увеличивается с увеличением количества элементов. Время доступа к элементам зачастую не так резко увеличивается с увеличением количества элементов.
Примеры: Массив, Стек, Очередь. Примеры: Деревья, Графы, Карты.

Зачем изучать структуры данных?

Знание и понимание структур данных поможет вам выбрать правильные структуры данных в своих проектах. Таким образом вы сможете писать более эффективный код, с точки зрения памяти и времени.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *