admin / 02.09.2018

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

.

Содержание

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

Связный список

Последнее обновление: 02.09.2016

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

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

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

Перед созданием списка нам надо определить класс узла, который будет представлять одиночный объект в списке:

public class Node<T> { public Node(T data) { Data = data; } public T Data { get; set; } public Node<T> Next { get; set; } }

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

Далее определим сам класс списка:

using System.Collections; using System.Collections.Generic; namespace SimpleAlgorithmsApp { public class LinkedList<T> : IEnumerable<T> // односвязный список { Node<T> head; // головной/первый элемент Node<T> tail; // последний/хвостовой элемент int count; // количество элементов в списке // добавление элемента public void Add(T data) { Node<T> node = new Node<T>(data); if (head == null) head = node; else tail.Next = node; tail = node; count++; } // удаление элемента public bool Remove(T data) { Node<T> current = head; Node<T> previous = null; while (current != null) { if (current.Data.Equals(data)) { // Если узел в середине или в конце if (previous != null) { // убираем узел current, теперь previous ссылается не на current, а на current.Next previous.Next = current.Next; // Если current.Next не установлен, значит узел последний, // изменяем переменную tail if (current.Next == null) tail = previous; } else { // если удаляется первый элемент // переустанавливаем значение head head = head.Next; // если после удаления список пуст, сбрасываем tail if (head == null) tail = null; } count—; return true; } previous = current; current = current.Next; } return false; } public int Count { get { return count; } } public bool IsEmpty { get { return count == 0; } } // очистка списка public void Clear() { head = null; tail = null; count = 0; } // содержит ли список элемент public bool Contains(T data) { Node<T> current = head; while (current != null) { if (current.Data.Equals(data)) return true; current = current.Next; } return false; } // добвление в начало public void AppendFirst(T data) { Node<T> node = new Node<T>(data); node.Next = head; head = node; if (count == 0) tail = head; count++; } // реализация интерфейса IEnumerable IEnumerator IEnumerable.GetEnumerator() { return ((IEnumerable)this).GetEnumerator(); } IEnumerator<T> IEnumerable<T>.GetEnumerator() { Node<T> current = head; while (current != null) { yield return current.Data; current = current.Next; } } } }

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

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

Node<T> head; // головной/первый элемент Node<T> tail; // последний/хвостовой элемент int count; // количество элементов в списке

Метод добавления:

public void Add(T data) { Node<T> node = new Node<T>(data); if (head == null) head = node; else tail.Next = node; tail = node; count++; }

Если у нас не установлена переменная head (то есть список пуст), то устанавливаем head и tail. После добавления первого элемента они будут указывать на один и тот же объект.

Если же в списке есть как минимум один элемент, то устанавливаем свойство tail.Next — теперь оно хранит ссылку на новый узел. И переустанавливаем tail — теперь она ссылается на новый узел.

Сложность данного метода составляет O(1).

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

Графически это выглядит так:

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

public void AddWithoutTail(T data) { Node<T> node = new Node<T>(data); if (head == null) { head = node; } else { Node<T> current = head; // ищем последний элемент while (current.Next!=null) { current = current.Next; } //устанавливаем последний элемент current.Next = node; } count++; }

Данный способ вполне рабочий и нередко встречается, однако необходимость перебора элементов для нахождения последнего увеличивает время на поиск и сложность алгоритма. Она равна O(n).

Особняком стоит метод добавления в начало списка, где нам достаточно переустановить ссылку на головной элемент:

public void AppendFirst(T data) { Node<T> node = new Node<T>(data); node.Next = head; head = node; if (count == 0) tail = head; count++; }

Удаление элемента

public bool Remove(T data) { Node<T> current = head; Node<T> previous = null; while (current != null) { if (current.Data.Equals(data)) { // Если узел в середине или в конце if (previous != null) { previous.Next = current.Next; if (current.Next == null) tail = previous; } else { head = head.Next; if (head == null) tail = null; } count—; return true; } previous = current; current = current.Next; } return false; }

Алгоритм удаления элемента представляет следующую последовательность шагов:

  1. Поиск элемента в списке путем перебора всех элементов

  2. Установка свойства Next у предыдущего узла (по отношению к удаляемому) на следующий узел по отношению к удаляемому.

Для отслеживания предыдущего узла применяется переменная . Если элемент найден, и переменная previous равна null, то удаление идет сначала, и в этом случае происходит переустановка переменной head, то есть головного элемента.

Если же previous не равна null, то реализуются шаги выше описанного алгоритма.

Сложность такого алгоритма составляет O(n). Графически удаление можно представить так:

Чтобы проверить наличие элемента, исползуется метод Contains:

public bool Contains(T data) { Node<T> current = head; while (current != null) { if (current.Data.Equals(data)) return true; current = current.Next; } return false; }

Здесь опять же просто осуществляется перебор. Сложность алгоритма метода составляет O(n).

И для того, чтобы список можно было бы перебрать во внешней прграмме с помощью цикла for-each, класс списка реализует интерфейс IEnumerable:

// реализация интерфейса IEnumerable IEnumerator IEnumerable.GetEnumerator() { return ((IEnumerable)this).GetEnumerator(); } IEnumerator<T> IEnumerable<T>.GetEnumerator() { Node<T> current = head; while (current != null) { yield return current.Data; current = current.Next; } }

Реализация данного интерфейса не является неотъемлимой частью односвязных списков, однако предоставляет эффективный метод для перебора коллекции в цикле foreach.

Иначе нам бы пришлось реализовать какие-то собственные конструкции по перебору списка.

Применение LinkedList:

LinkedList<string> linkedList = new LinkedList<string>(); // добавление элементов linkedList.Add(«Tom»); linkedList.Add(«Alice»); linkedList.Add(«Bob»); linkedList.Add(«Sam»); // выводим элементы foreach(var item in linkedList) { Console.WriteLine(item); } // удаляем элемент linkedList.Remove(«Alice»); foreach (var item in linkedList) { Console.WriteLine(item); } // проверяем наличие элемента bool isPresent = linkedList.Contains(«Sam»); Console.WriteLine(isPresent == true ? «Sam присутствует» : «Sam отсутствует»); // добавляем элемент в начало linkedList.AppendFirst(«Bill»);

НазадСодержаниеВперед

Структуры данных. Понятие Структуры данных. Линейные структуры данных (массив, список, очередь).

1234

Структуры данных (сд) – совокупность эл-в данных, объединенных структурными взаимосвязями, при этом каждый эл- в данных в структуре может быть представлен как структура данных

Каждая сд хар-ся набором типовых операций, применимых к данной структуре, на которой ориентирована данная структура

Группы структур:

Линейные, циклические, нелинейные, другие (ост-е)

 

Линейные

Массив, список, очередь, стек, дек, хэш-таблица

Массив (яд, индекс. массив) – сд, эл-ты которой расположены в памяти др. за др., доступ к ним осущ-ся по индексам

Кол-во используемых индексов различно

Операции:

· Получение значения эл-та по индексу

· Установка значения эл-та по индексу

Дост.:

Легкость вычисления адреса эл-та по индексу

Одинаковое время доступа ко всем эл-там

Мин. Размер эл-в (только собственные данные)

Недост.:

Для статич. массива это отсутствие динамики (удаление и вставка эл-та, сдвигая другие)

Для динамич. более низкое быстродействие по сравнению со статич. и доп. расходы на поддержку динамич св-в

При работе с масс. в стиле C и при отсутствии доп. средств контроля, есть угроза выхода за границу масс. и повреждения данных

Списоксд, её эл-ты расположены в памяти в произв. порядке, эл-ты связаны м/д собой, образуя лин. последовательность, порядок эл-в в списке может не совпадать с порядком расположения в памяти. Каждый эл-т содержит соб. данные и 1-2 ссылки на соседние эл-ты (односвязный двусвязный) Операции:

· удалить из списка

· поместить в список

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

Операции:

· вставка в очередь

· удаление из очереди

 

 

24. Структуры данных. Понятие Структуры данных. Линейные структуры данных (стек, дек, хеш-таблица).

См в №23

Стексд доступ к данным по принципу LIFO

Стек м/б реализован на базе массива или списка

Операции:

· push (добавление в стек)

· pop (удаление из стека)

Дек – (двусвязная очередь) сд, в которой эл-ты добав. и удал. как в начале так и в конце

Операции:

· push Back (добав. эл-т – последний)

· pop Front (добав. эл-т – первый)

· push Front (2 эл-т с конца– последний)

· pop Back(2 эл-т с конца – первый)

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

Ключ – некий уник. идентификатор данных эл-та

Обычно ключ получается применением Hash функций к данным эл-та

Типы:

· таблица в которой не допускается дублирование ключей

· таблица в которой возможно хранение эл-в с одинак. ключами

Hash Table – допускается дубл.

Ассоциатив-й масс. – по опр. не допускается дубл.

Hash Table чаще всего реализуется на базе масс. в этом случае ключ – индекс

Операции:

· Добавление эл-та (в 3 этапа)

1. расчет знач. ключа

2. проверка возможности добав. эл-та в табл.

3. добав.

· Удаление эл-та (в 3 этапа)

1. расчет знач. ключа

2. проверка наличия эл-та

3. удаление

· Поиск эл-та в таблице

1. расчет знач. ключа

2. поиск (проверка есть или нет)

 

Структуры данных. Понятие Структуры данных. Циклические структуры данных (циклический список, циклическая очередь, циклический дек). Назначение циклических структур данных.

См в №23

Циклический список

· односвязный (посл. эл-т ссылается на первый)

· двусвязный (посл. на первый, первый на посл.)

Операции аналогично лин. списку

Циклическая очередь

Циклический дек

Осн. назначение

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

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

См в №23

И лин. и цикл. структуры – частный случай нелинейных

Граф (Осн. структура) — многосвязная сд, эл-ты расположены в произв. порядке, имеют произв. кол-во связей. В общем случае – множество вершин (узлов) и ребер (дуг)

Узлы – данные

Ребра – связи

Свойства:

· на каждый эл-т может указывать множество ссылок

· каждый эл-т может ссылаться на множество др.

эл-в

· каждая связь может иметь направление и вес

Неориентированный граф – граф у которого все ребра не имеют направления

Ориентированный граф – граф у которого все ребра имеют заданное направление

Смешанный граф – граф у которого нек.

ребра ориентированы, а нек. нет.

Дерево – частный случай графа, это ориент. или неориент. граф, хар-ся 3 св-ми:

· не содержит цикл (сущ. только 1 способ добраться от 1 вершины к др.)

· выделена 1 вершина – корень, на него не ссылается ни одна вершина

· на каждую вершину дерева кроме корня имеется одна единственная ссылка

листья, поддерево!!!

Высота – число уровней вершин

Бинарное дерево

N-нарное дерево

?

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

дерево любого вида м/б представлено эквивалентный бинарным деревом

Типовые операции:

· поиск узла в дереве

· удаление узда или поддерева

· добавление узла

· обход дерева в зад. направлении

Дост:

Хорошо подходит для работы с отсорт. данными

По совокуп. операций эта структура обеспечивает наилучшую проив-сть

Недост.: сложность реализации алгоритмов типовых оперций

1234



Связные списки

Односвязный линейный список

Односвязный циклический список

Двусвязный линейный список

Двусвязный циклический список

Стек

Очередь

Дерево

Двоичная куча

Граф


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

10 структур данных, которые вы должны знать (+видео и задания)

Для такой структуры характерно, что в процессе вычислений изменяются не только значения объектов, но и структура хранения информации. Поэтому такие объекты называются динамическими информационными структурами. Их компоненты, в свою очередь, на некотором уровне детализации представляют собой объекты со статической структурой, то есть они принадлежат к одному из основных типов данных.

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

Понятие структуры данных

Необходимым условием построения алгоритма является формализация данных, т.е. приведение информации к некоторой информационной модели (см. “Информационные модели”), уже описанной и исследованной. Когда такая модель найдена, говорят, что определена абстрактная структура данных.

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

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

· целые числа;

· вещественные числа;

· символы;

· логические значения.

Для компьютерной обработки этих объектов в языках программирования существуют соответствующие типы данных (см. “Типы данных”). Базовые объекты можно объединять в более сложные структуры, добавляя операции уже над структурой в целом и правила доступа к отдельным элементам этой абстрактной структуры данных.

К таким абстрактным структурам данных относятся:

· векторы (конечные массивы);

· таблицы (матрицы), а в общем случае — многомерные массивы;

· графы;

· динамические структуры:

— последовательности символов, чисел;

— строки;

— списки;

— очереди;

— стеки;

— деревья;

— графы.

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

Заметим, что перечисленные структуры существуют независимо от их реализации при программировании. С этими структурами данных работали и в XVIII, и в XIX веках, когда еще не придумали вычислительную машину. Мы можем разрабатывать алгоритм в терминах абстрактной структуры данных, но для реализации алгоритма в конкретном языке программирования необходимо найти способ ее представления в терминах типов данных и операторов, поддерживаемых данным языком программирования (см. “Операторы языка программирования”). Для компьютерного представления абстрактных структур используются структуры данных,которые представляют собой набор переменных, возможно различных типов данных, объединенных определенным образом. Для конструирования таких структур, как вектор, таблица, строка, последовательность, в большинстве языков программирования присутствуют стандартные типы данных: одномерный массив, двухмерный массив, строка, файл (реже список) соответственно. Организацию остальных структур данных, в первую очередь динамических структур, размер которых меняется во время выполнения программы, программисту приходится осуществлять самостоятельно, используя базовые типы данных. Рассмотрим такие структуры подробнее.

Списки

Линейный список — последовательность линейно связанных элементов, для которых разрешены операции добавления элементов в произвольное место списка и удаление любого элемента. Линейный список однозначно задается указателем на начало списка. Типовыми операциями над списками являются: обход списка, поиск заданного элемента, вставка элемента сразу после или перед определенным элементом, удаление заданного элемента, объединение двух списков в один, разбиение одного списка на два и более списков и т.п.

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

Пример 1.

Порядок следования записей фамилий читателей в компьютере библиотекаря определяет отношение “предыдущий–следующий”. Как правило, сами записи имеют дополнительное свойство — они упорядочены по алфавиту. Над этим списком реализованы операции добавления нового читателя и, при необходимости, удаления старого. Если к тому же ведутся записи выданных каждому читателю книг, то каждую такую запись удобно представлять опять же с помощью списка выданных книг.

Кольцевые списки — такая же структура, как и линейный список, но имеющая дополнительную связь между последним и первым элементом, то есть следующим за последним элементом является первый элемент.

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

Пример 2. Во многих играх дети используют считалочки, чтобы выбрать ведущего, разделиться на команды и т.п. Как правило, считалочки длинные, и дети (сами того не зная) организуют кольцевой список. Отношение “предыдущий–следующий” определяется тем, в какую сторону ведущий считает. Типичная операция в такой структуре — удаление элемента из списка с сохранением его кольцевой структуры.

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

Стек — частный случай линейного односвязного списка, для которого определены две операции: добавление элемента в вершину стека (перед первым элементом) и удаление элемента из вершины стека (удаление первого элемента).

Пример 3. Рассмотрим задачу определения сбалансированности скобок различных видов в арифметическом выражении. Например, требуется проанализировать, сбалансированы ли скобки в выражении, содержащем круглые и квадратные скобки: ? Для решения этой задачи будем использовать динамическую структуруданных стек. Приведем алгоритм решения этой задачи по шагам. Будем использовать следующие обозначения:

i — номер анализируемого символа;

n — количество символов в выражении.

1. i= 0.

2. i = i + 1.

3. Если i n, то переход на п. (4), иначе если стек пуст, то выдаем сообщение “скобки сбалансированы”, в противном случае выдаем сообщение “скобки не сбалансированы”. Конец алгоритма.

4. Если i-й символ отличен от символов скобок, то переход на п. (2).

5. Если i-й символ равен “(” или “[”, то помещаем его в стек, переход на п. (2).

6. Если i-й символ равен “)”, то проверяем вершину стека: если в вершине стека находится “(”, то извлекаем ее из стека; переход на п. (2), иначе выдаем сообщение “скобки не сбалансированы”. Конец алгоритма.

7. Если i-й символ равен “]”, то проверяем вершину стека: если в вершине стека находится “[”, то извлекаем ее из стека; переход на п. (2), иначе выдаем сообщение “скобки не сбалансированы”. Конец алгоритма.

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

Понятие очереди действительно очень близко к бытовому термину “очередь”. Очередь покупателей в магазине хорошо описывается в терминах этой структуры данных.

Деревья

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

Над деревом определены следующие операции: добавление элемента в дерево, удаление элемента из дерева, обход дерева, поиск элемента в дереве.

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

Используются деревья и для определения выигрышной стратегии в играх (см. статью “Игры. Выигрышные стратегии”), и для построения различных информационных моделей (см. “Информационные модели”).

Особенно важную роль в информатике играют так называемые бинарные деревья.

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

Если дополнительно для узлов дерева выполняется условие, что все значения элементов левого поддерева меньше значения корня дерева, а все значения элементов правого поддерева больше значения корня, то такое дерево называется деревом бинарного поиска и предназначено для быстрого поиска элементов. Алгоритм поиска в таком дереве работает так: искомое значение сравнивается со значением корня дерева, и в зависимости от результата сравнения поиск либо заканчивается, либо продолжается только в левом или только в правом поддереве соответственно. Общее количество операций сравнения не будет превосходить так называемую высоту дерева — максимальное количество элементов на пути от корня дерева к одному из листьев. Так, высота изображенного на рисунке дерева равна 4.

Графы

Граф — это множество элементов, называемых вершинами графа вместе с набором отношений между этими вершинами, называемых ребрами графа. Графической интерпретацией этой структуры данных является множество точек, соответствующих вершинам, некоторые пары из которых соединены линиями или стрелками, которые соответствуют ребрам. В последнем случае граф называется ориентированным (см. также статьи “Графические модели” и “Табличные модели”).

В силу того, что с помощью графов можно описывать объекты произвольной структуры, графы являются основным средством для описания структур сложных объектов и функционирования систем. Например, для описания вычислительной сети, транспортной системы, иерархической структуры (дерево является одной из разновидностей графа). Блок-схемы алгоритмов (см. “Способы записи алгоритмов”) также представляют собой графы.

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

Пример 5. В терминах взвешенного графа удобно решать следующую задачу. Правительство России составляет план строительства современных автомагистралей, соединяющих города, население которых превышает миллион человек. Какие именно дороги следует построить, чтобы из любого такого города можно было добраться в любой другой по новым автомагистралям, а общая длина дорог была бы минимальной?

Эта задача в теории графов имеет простое и точное решение. Мы можем начать планирование сети дорог, начиная с любого города, например, Санкт-Петербурга. Соединим его с ближайшим городом-миллионником. Далее на каждом шаге к имеющейся сети добавляется кратчайшая дорога, которой можно соединить город, еще не присоединенный к сети, с одним из городов, уже включенных в сеть. Количество дорог будет, таким образом, на единицу меньше, чем число городов.

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

Наибольшее распространение получило табличное хранение графа (см. “Табличные модели”), называемое также матрицей смежности, т.е. двухмерного массива, скажем, A, где для невзвешенного графа (или 1), если ребро между вершинами i и j существует, и (или 0) в противном случае. Для взвешенного графа A[i][j] равно весу соответствующего ребра, а отсутствие ребра в ряде задач удобно обозначать бесконечностью. Для неориентированных графов матрица смежности всегда симметрична относительно главной диагонали (i = j). C помощью матрицы смежности легко проверить, существует ли в графе ребро, соединяющее вершину i с вершиной j. Основной же ее недостаток заключается в том, что матрица смежности требует, чтобы объем памяти был достаточен для хранения N2 значений для графа, содержащего N вершин, даже если ребер в графе существенно меньше, чем N2.

Методические рекомендации

При объяснении понятия структуры данных можно воспользоваться следующей иллюстрацией.

Основные структуры данных.

При решении любой задачи возникает необходимость работы с данными и выполнения операций над ними. Набор этих операций для каждой задачи, вообще говоря, свой. Однако, если некоторый набор операций часто используется при решении различных задач, то полезно придумать способ организации данных, позволяющий выполнять именно эти операции как можно эффективнее. После того, как такой способ придуман, при решении конкретной задачи можно считать, что у нас в наличии имеется “черный ящик” (его мы и будем называть структурой данных), про который известно, что в нем хранятся данные некоторого рода, и который умеет выполнять некоторые операции над этими данными. Это позволяет отвлечься от деталей и сосредоточиться на характерных особенностях задачи. Внутри (т.е. в компьютере) этот “черный ящик” может быть реализован различным образом, при этом следует стремиться к как можно более эффективной (быстрой и экономично расходующей память) реализации.

Государственный образовательный стандарт предусматривает изучение различных структур данных как в базовом курсе основной школы, так и в старших классах. В курсе программирования основной школы в Примерной программе упоминаются в качестве обрабатываемых объектов цепочки символов (строки), числа, списки, деревья, графы. Однако в практических работах из данных сложной структуры упоминается только массив (см. статью “Операции с массивами”). В основной школе остальные структуры, видимо, имеет смысл изучать в первую очередь при построении графических и других моделей (см. раздел IV энциклопедии).

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

Бинарное дерево также легко представить в памяти компьютера с помощью одномерного массива, при этом в первом элементе массива будет храниться корень дерева, а потомки узла дерева, хранящегося в i-м элементе массива, будут располагаться в 2i-м и (2i + 1)-м элементах соответственно. Если потомок у узла отсутствует, то соответствующий элемент будет равен, например, 0. Рекурсивная процедура обхода дерева t и печати его элементов в этом случае будет выглядеть так:

procedure

order(i:integer);

begin

if t[i] <> 0 then

begin

writeln(t[i]);

order(2*i);

order(2*i + 1)

end

end

;

О реализации списков и массивов с помощью динамических переменных можно прочитать, например, в классической книге Н.Вирта “Алгоритмы и структуры данных”.

В программу для профильной школы включены и алгоритмы на графах. В частности, упоминается поиск кратчайшего пути в графе. Для невзвешенного графа решать эту задачу можно, например, с использованием алгоритма “поиска в ширину”, когда сначала помечаются вершины графа, соединенные ребром с исходной вершиной, затем все вершины, соединенные с помеченными, и т.д. Для взвешенного графа чаще всего используют алгоритм Дийкстры (см., например, статью Е.В. Андреевой “Олимпиады по информатике. Пути к вершине”, “Информатика” № 8/2002). Знание таких алгоритмов необходимо для успешного решения олимпиадных задач по информатике. Так, на IV федеральном окружном этапе Всероссийской олимпиады по информатике 2007 г. предлагалась задача “Окопы и траншеи”, решение которой как раз и сводилось к поиску кратчайшего пути во взвешенном графе.

Похожие главы из других работ:

Автоматизированное рабочее место сотрудника пожарного контроля

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

В программе используются следующие таблицы: Водители; Криминалисты; Командиры; Пожарные; Бригада; Машины; Тип машины; Информация о вызовах; Диспетчер; Пострадавшие. Наиболее важной является таблица «Информация о вызовах»…

Анализатор цветового набора для WEB-страницы

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

Основной структурой данного проекта является промежуточный файл с именем “tempfile.htm”, который аналогичен входному файлу, но во входном файле все символы латинского алфавита преобразуются в нижний регистр…

АРМ замдиректора по научной работе

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

программирование автоматизирующий интерфейс алгоритм В программе используются следующие таблицы: — Мероприятия; — Студент; — Задачи мероприятия; — Администратор; — Научный руководитель; — Место проведения…

База данных учащихся

2.3 Структура баз данных

Иерархическая модель данных. Структуры данных

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

Организация данных в СУБД иерархического типа определяется в терминах: элемент, агрегат, запись (группа), групповое отношение, база данных. Атрибут (элемент данных) — наименьшая единица структуры данных…

Изучение языка объектно-ориентированного программирования Borland Delphi и разработка практических заданий

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

Для хранения данных о точках введем тип данных tmypoint: 1. type 2. tmypoint = record 3. x: Integer; 4. y: Integer; 5. end; Тип tmypoint представляет собой запись, которая имеет 2 поля: x и y, для хранения соответствующих координат точек…

Основные типы моделей данных

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

Организация данных в СУБД иерархического типа определяется в терминах: элемент, агрегат, запись (группа), групповое отношение, база данных. Атрибут (элемент данных) — наименьшая единица структуры данных…

Основные типы моделей данных

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

На разработку этого стандарта большое влияние оказал американский ученый Ч. Бахман. Основные принципы сетевой модели данных были разработны в середине 60-х годов…

Основные типы моделей данных

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

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

Программное обеспечение для организации курсовых работ и практик

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

При разработке программного обеспечения большую роль играет проектирование хранилища данных и представление всех данных в виде множества связанных структур данных…

Программный комплекс для определения константы скорости химической реакции

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

Входные экспериментальные данные по изменению концентрации компонентов во времени представлены далее.

Начальная концентрация CВ = 0,1 моль/л; СС = 0,01 моль/л, СD = 0,002 моль/л. Распределение концентрации CА(t) во времени t приведено в таблице 1…

Разработка приложения для отдела информационных технологий ООО «Уралмаш — металлургическое оборудование»

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

На основании разработанной информационной модели были созданы 7 таблиц: 1. Информация о компьютере Данная таблица содержит информацию обо всех компьютерах на предприятии. Данная информация необходима для осуществления процесса ремонта…

Разработка приложения для учета рабочего времени сотрудников предприятия

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

Для описания базы данных необходимо располагать описанием выбранной предметной области, которое должно охватывать реальные объекты и процессы…

Разработка проекта информационной системы учета и анализа трудозатрат на промышленном предприятии ОАО «КнААПО»

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

Следующим этапом в проектировании автоматизированной информационной системы является моделирование структуры данных, т.е. составление модели данных для хранения их в каком либо хранилище данных (в нашем случае это MS ACCESS)…

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

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

Сцена представляется набором объектов двух типов: источников света и собственно объектов, которые необходимо визуализировать…

FILED UNDER : IT

Submit a Comment

Must be required * marked fields.

:*
:*