Работа с большими наборами данных автоматизируется проще, когда данные упорядочены, то есть образуют заданную структуру. Существует три основных типа структур данных: линейная, иерархическая и табличная. Их можно рассмотреть на примере обычной книги.
Если разобрать книгу на отдельные листы и перемешать их, книга потеряет свое назначение. Она по-прежнему будет представлять набор данных, но подобрать адекватный метод для получения из нее информации весьма непросто. (Еще хуже дело будет обстоять, если из книги вырезать каждую букву отдельно — в этом случае вряд ли вообще найдется адекватный метод для ее прочтения.) Если же собрать все листы книги в правильной последовательности, мы получим простейшую структуру данных — линейную. Такую книгу уже можно читать, хотя для поиска нужных данных ее придется прочитать подряд, начиная с самого начала, что не всегда удобно. Для быстрого поиска данных существует иерархическая структура. Так, например, книги разбивают на части, разделы, главы, параграфы и т. п. Элементы структуры более низкого уровня входят в элементы структуры более высокого уровня: разделы состоят из глав, главы из параграфов и т. д. Для больших массивов поиск данных в иерархической структуре намного проще, чем в линейной, однако и здесь необходима навигация, связанная с необходимостью просмотра. На практике задачу упрощают тем, что в большинстве книг есть вспомогательная перекрестная таблица, связывающая элементы иерархической структуры с элементами линейной структуры, то есть связывающая разделы, главы и параграфы с номерами страниц. В книгах с простой иерархической структурой, рассчитанных на последовательное чтение, эту таблицу принято называть оглавлением, а в книгах со сложной структурой, допускающей выборочное чтение, ее называют содержанием.
Линейные структуры (списки данных, векторы данных)
Линейные структуры — это хорошо знакомые нам списки. Список — это простейшая структура данных, отличающаяся тем, что каждый элемент данных однозначнс определяется своим номером в массиве. Проставляя номера на отдельных страницам рассыпанной книги, мы создаем структуру списка. Обычный журнал посещаемое^ занятий, например, имеет структуру списка, поскольку все студенты группы зарегаст рированы в нем под своими уникальными номерами. Мы называем номера уникальными потому, что в одной группе не могут быть зарегистрированы два студента < одним и тем же номером.
При создании любой структуры данных надо решить два вопроса: как разделят: элементы данных между собой и как разыскивать нужные элементы. В журнал посещаемости, например, это решается так: каждый новый элемент списка зано сится с новой строки, то есть разделителем является конец строки. Тогда нужны] элемент можно разыскать по номеру строки.
N п/п Фамилия, Имя, Отчество
1 Аистов Александр Алексеевич
2 Бобров Борис Борисович
3 Воробьева Валентина Владиславовна
… ………………………………..
27 Сорокин Сергей Семенович
Разделителем может быть и какой-нибудь специальный символ. Нам хорошо известны разделители°между словами — это пробелы. В русском и во многих европейских языках общепринятым разделителем предложений является точка. В рассмотренном нами классном журнале в качестве разделителя можно использовать любой символ, который не встречается в самих данных, например символ «*». Тогда наш список выглядел бы так:
Аистов Александр Алексеевич * Бобров Борис Борисович * Воробьева Валентина
Владиславовна *… * Сорокин Сергей Семенович
В этом случае для розыска элемента с номером п надо просмотреть список начиная с самого начала и пересчитать встретившиеся разделители. Когда будет отсчитано а(n-1) разделителей, начнется нужный элемент. Он закончится, когда будет встречен следующий разделитель.
Еще проще можно действовать, если все элементы списка имеют равную длину. В этом случае разделители в списке вообще не нужны. Для розыска элемента с номером п надо просмотреть список с самого начала и отсчитать a(n-i) символ, где а — длина одного элемента. Со следующего символа начнется нужный элемент. Его длина тоже равна а, поэтому его конец определить нетрудно. Такие упрощенные списки, состоящие из элементов равной длины, называют векторами данных. Работать с ними особенно удобно.
Таким образом, линейные структуры данных (списки) — это упорядоченные структуры, в которых адрес элемента однозначно определяется его номером.
Табличные структуры (таблицы данных, матрицы данных)
С таблицами данных мы тоже хорошо знакомы, достаточно вспомнить всем известную таблицу умножения. Табличные структуры отличаются от списочных тем, что элементы данных определяются адресом ячейки, который состоит не из одного параметра, как в списках, а из нескольких. Для таблицы умножения, например, адрес ячейки определяется номерами строки и столбца. Нужная ячейка находится на их пересечении, а элемент выбирается из ячейки.
При хранении табличных данных количество разделителей должно быть больше, чем для данных, имеющих структуру списка. Например, когда таблицы печатают в книгах, строки и столбцы разделяют графическими элементами — линиями вертикальной и горизонтальной разметки (рис. 1.4).
Если нужно сохранить таблицу в виде длинной символьной строки, используют один символ-разделитель между элементами, принадлежащими одной строке, и другой разделитель для отделения строк, например так:
Мерхурий*0,39*0>056*0#Венера*0,67*0,88*0#Земля*1,0*1,0*1#Марс*1,51*0,1*2#...
| Планета | Расстояние до Солнца, а.е. | Относительная масса | Количество спутников |
| Меркурий | 0,39 | 0,056 | |
| Венера | 0,67 | 0,88 | |
| Земля | 1,0 | 1,0 | |
| Марс | 1,51 | 0,1 | |
| Юпитер | 5,2 |
Рис. 1.4. В двумерных таблицах, которые печатают в книгах, применяется
два типа разделителей — вертикальные и горизонтальные
Для розыска элемента, имеющего адрес ячейки (т, п), надо просмотреть набор данных с самого начала и пересчитать внешние разделители. Когда будет отсчитан , т -1 разделитель, надо пересчитывать внутренние разделители. После того как будет найден , п -1 разделитель, начнется нужный элемент. Он закончится, когда будет встречен любой очередной разделитель.
Еще проще можно действовать, если все элементы таблицы имеют равную длину. Такие таблицы называют матрицами. В данном случае разделители не нужны, поскольку все элементы имеют равную длину и количество их известно. Для розыска элемента с адресом (т, п) в матрице, имеющей М строк и N столбцов, надо просмотреть ее с самого начала и отсчитать a [N(m -1) + (п -1)] символ, где а — длина одного элемента. Со следующего символа начнется нужный элемент. Его длина тоже равна а, поэтому его конец определить нетрудно.
Таким образом, табличные структуры данных (матрицы) — это упорядоченные структуры, в которых адрес элемента определяется номером строки и номером столбца, на пересечении которых находится ячейка, содержащая искомый элемент.
Многомерные таблицы.Выше мы рассмотрели пример таблицы, имеющей два измерения (строка и столбец), но в жизни нередко приходится иметь дело с таблицами, у которых количество измерений больше. Вот пример таблицы, с помощью которой может быть организован учет учащихся.
Номер факультета: 3
Номер курса (на факультете): 2
Номер специальности (на курсе): 2
Номер группы в потоке одной специальности: 1
Номер учащегося в группе: 19
Размерность такой таблицы равна пяти, и для однозначного отыскания данных об учащемся в подобной структуре надо знать все пять параметров (координат).
www.ronl.ru
Реферат на тему:
| Это служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавливается на информационные списки и глоссарии. |
Это — список структур данных. Для более широкого списка см. список терминов, относящихся к алгоритмам и структурам данных.
Попытка классификации некоторых из них на основании особенностей:
| Сумка | нет | нет | 1 |
| Множество | нет | да | 1 |
| Список | да | нет | 1 |
| Ассоциативный массив | нет | да | 2 |
«Упорядоченная» не означает — отсортированная, только то, что исходный порядок «сохранён». Другие структуры, такие как «связный список» и «стек» не могут легко быть определены таким образом, потому что существуют специальные операции ассоциирующиеся с ними.
скачатьДанный реферат составлен на основе статьи из русской Википедии. Синхронизация выполнена 14.07.11 10:09:03Похожие рефераты: Алгебраические структуры, Семиотика структуры, Диссипативные структуры, Структуры мозга, Синтаксические структуры, Демографические структуры населения, Масштабно-тематические структуры, Диаграмма композитной структуры, Предсказание структуры белка.Категории: Списки Компьютеры, Структуры данных.
Текст доступен по лицензии Creative Commons Attribution-ShareAlike.www.wreferat.baza-referat.ru
Реферат на тему:
Пример полной бинарной кучи.
В компьютерных науках ку́ча — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами). Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи, хотя на практике их число обычно не более двух. Куча является максимально эффективной реализацией абстрактного типа данных, который называется очередью с приоритетом. Кучи имеют решающее значение в некоторых эффективных алгоритмах на графах, таких как алгоритм Дейкстры и сортировка методом пирамиды.
Структуру данных куча не следует путать с понятием куча в динамическом распределении памяти. Впервые термин использовался именно для структур данных. В некоторых ранних популярных языках программирования типа ЛИСП обеспечивалось динамическое распределение памяти с использованием структуры данных «куча», которая и дала своё имя выделяемому объёму памяти.[1].
Кучи обычно реализуются в виде массивов, что исключает наличие указателей между её элементами.
Над кучами обычно проводятся следующие операции:
Ниже приведены оценки временно́й сложности вычислений для операций над некоторыми видами кучи.[1] Там, где значение отмечено звездочкой, оценка сделана методом амортизационного анализа (по наихудшему времени), в остальных случаях оценка является регулярным худшим случаем. O(F) даёт асимптотическую верхнюю границу, а Θ(F) является асимптотически точной оценкой (см. обозначения «O» большое и «o» малое). Имена операций выбраны для min-кучи.
| найти минимум | Θ(1) | Θ(log n) or Θ(1) | Θ(1)[1] | Θ(1) | Θ(1) |
| удалить минимум | Θ(log n) | Θ(log n) | O(log n)* | O(log n)* | O(log n) |
| добавить | Θ(log n) | O(log n) | Θ(1) | O(1)* | Θ(1) |
| уменьшить ключ | Θ(log n) | Θ(log n) | Θ(1)* | O(log n)* | Θ(1) |
| слияние | Θ(n) | O(log n)** | Θ(1) | O(1)* | Θ(1) |
(*) Амортизационное время(**) Где n — размер наибольшей кучи
Заметим, что «очередь Бродала» представляет собой реализацию очереди с параллельным приоритетом, разработанную группой во главе с Гертом Бродалом.[3]
Структуры данных типа кучи имеют множество применений.
Полная и почти полная бинарная куча может быть представлена очень эффективным способом с помощью индексного массива. Первый (или последний) элемент будет содержать корень. Следующие два элемента массива содержат узлы-потомки корня. Следующие четыре элемента содержат четверых потомков от двух узлов — потомков корня, и т.д. Таким образом, потомки узла уровня n будут расположены на позициях 2n и 2n+1 для массива, индексируемого с нуля, или на позициях 2n+1 и 2n+2 для массива, индексируемого с единицы. Это позволяет перемещаться вверх или вниз по дереву, выполняя простые вычисления индекса массива. Балансировка кучи делается перестановкой элементов, которые нарушают порядок. Поскольку мы можем построить кучу с помощью массива без дополнительной памяти (для узлов, например), то можно использовать пирамидальную сортировку для сортировки массива прямо на месте.
Категории: Кучи (структуры данных).
Текст доступен по лицензии Creative Commons Attribution-ShareAlike.wreferat.baza-referat.ru
Реферат на тему:
| Это служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавливается на информационные списки и глоссарии. |
Это — список структур данных. Для более широкого списка см. список терминов, относящихся к алгоритмам и структурам данных.
Попытка классификации некоторых из них на основании особенностей:
| Сумка | нет | нет | 1 |
| Множество | нет | да | 1 |
| Список | да | нет | 1 |
| Ассоциативный массив | нет | да | 2 |
«Упорядоченная» не означает — отсортированная, только то, что исходный порядок «сохранён». Другие структуры, такие как «связный список» и «стек» не могут легко быть определены таким образом, потому что существуют специальные операции ассоциирующиеся с ними.
скачатьДанный реферат составлен на основе статьи из русской Википедии. Синхронизация выполнена 14.07.11 10:09:03Похожие рефераты: Алгебраические структуры, Семиотика структуры, Диссипативные структуры, Структуры мозга, Синтаксические структуры, Демографические структуры населения, Масштабно-тематические структуры, Диаграмма композитной структуры, Предсказание структуры белка.Категории: Списки Компьютеры, Структуры данных.
Текст доступен по лицензии Creative Commons Attribution-ShareAlike.wreferat.baza-referat.ru
