итип. Способ представления. Различают физическую и логическую (абстрактную) структуры данных. Физическая структура данных это способ представления (хранения) данных в машинной памяти компьютера
 Скачать 15.74 Kb.
|
|
Способ представления. Различают физическую и логическую (абстрактную) структуры данных. Физическая структура данных — это способ представления (хранения) данных в машинной памяти компьютера. Логическая структура — это рассмотрение структуры данных без учета ее представления в машинной памяти. В общем случае между логической и соответствующей ей физической структурами существуют расхождения, которые определяются самой структурой и особенностями той среды, в которой она должна быть реализована. Существуют процедуры, которые осуществляют отображение логической структуры в физическую и, наоборот, физической структуры в логическую. Вид памяти, используемой для сохранности данных. В зависимости от размещения физических структур, а соответственно, и доступа к ним, различают внутренние и внешние структуры данных. Внутренние структуры — это данные, размещенные в статической и динамической памяти компьютера. Внешние структуры размещаются на внешних устройствах и называются файловыми структурами или файлами. Примеры файловых структур: файлы, В-деревья и др. Сложность представления. Структуры данных делятся на элементарные и составные. Элементарными называются такие структуры данных, которые не могут быть расчленены на составные части. С точки зрения физической структуры важным является то обстоятельство, что в конкретной машинной архитектуре, в конкретной системе программирования всегда можно заранее сказать, каков будет размер элементарной единицы данных и как она будет размещена в памяти. С логической точки зрения элементарные единицы данных являются неделимыми. Составными называются такие структуры данных, которые могут быть разбиты на части — другие (элементарные или составные) структуры данных. Составные структуры данных конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования. Характер упорядоченности элементов в структуре. Важный признак составной структуры данных — характер упорядоченности ее частей. По этому признаку структуры можно делить на линейные и нелинейные. Линейные структуры разделяют на структуры с последовательным расположением элементов в памяти (векторы, строки, 5 1. Алгоритмы и структуры данных массивы, стеки, очереди) и структуры с произвольным связным распределением элементов в памяти, к которым относятся односвязные и двусвязные линейные списки. Нелинейные структуры — многосвязные списки, деревья, графы. Изменчивость. Изменчивость определяется изменением числа элементов и/или связей между составными частями структуры. В определении изменчивости структуры не учитывается факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры статические и динамические. Статическими, например, являются массивы, множества, записи, таблицы; динамическими — связные списки, графы, деревья. Слайд №8: Понятность. Исполнитель алгоритма должен знать, как его выполнять. Дискретность. Алгоритм должен представлять процесс решения задачи как последовательное выполнение простых шагов (этапов), каждый из которых выполняется за конечное время. Детерминированность. Каждое правило алгоритма должно быть четким, однозначным и выдавать для одних исходных данных всегда один и тот же результат. Результативность. При корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. Массовость. Алгоритм разрабатывается в общем виде и должен быть применим для некоторого класса задач и разных исходных данных. Слайд №9: Словесный способ не имеет широкого распространения из-за отсутствия строгой формализации словесного описания алгоритма. Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление называется схемой алгоритма (или граф-схемой алгоритма — ГСА). Слайд №11: Псевдокод занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи. В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя. Другое различие между псевдокодом и обычным кодом заключается в том, что в псевдокоде, как правило, не рассматриваются некоторые вопросы, которые приходится решать разработчикам программного обеспечения. Такие вопросы, как абстракция данных, модульность и обработка ошибок часто игнорируются, чтобы более выразительно передать суть алгоритма. До сих пор не принята какая-либо форма псевдокода в качестве стандарта. Главная цель использования псевдокода — обеспечить понимание алгоритма человеком, сделать описание более воспринимаемым, чем исходный код на языке программирования. Слайд №23 Самым простым методом внешней сортировки является прямое слияние (или двухфазная сортировка прямым слиянием). Метод работает следующим образом: 1. Последовательность А разбивается на две половины В и С. 2. Части В и С сливаются в A, при этом одиночные элементы из В и С образуют упорядоченные пары. 3. Шаги 1 и 2 повторяются, при этом размер отсортированных блоков с каждой итерацией увеличивается в два раза Слайд №24 Для устранения этого недостатка можно поступить следующим образом: 1. Исходный сверхбольшой набор данных разделить на отдельные фрагменты такого размера, чтобы каждый фрагмент мог целиком разместиться в ОП. 2. Каждый фрагмент отдельно загрузить в ОП и отсортировать алгоритмом внутренней сортировки. 3. Каждый отсортированный фрагмент после этого рассматривать как серию. Полученные серии рассортировать по выходным файлам. Эти действия носят подготовительный характер. Принцип изображен на слайде. К полученным файлам затем применяется один из предложенных ранее методов сортировки естественным слиянием. С каждым шагом в выходных файлах будут формироваться серии в два раза длиннее, пока не получится одна серия длиной n. Слайд №28 Недостатком любого алгоритма, основанного на хешировании, является то, что существует вероятность совпадения хешей строк, поскольку значение хеша берется по модулю. Таким образом, разделяют истинные совпадения и ложные. Рассмотрим следующий пример: Слайд №29 При первом сравнении совпали 4 элемента. Обращаемся к префикс-функции p( ) S = [0,0,1,2,0,0] и используем число в четвертой ячейке, равное 2. Это означает, что в просмотренной части строки суффикс длины 2 является префиксом исходной подстроки. Следовательно, можно осуществить сдвиг на 4–2 = 2 шага. На втором шаге снова совпало пять символов. Обращаемся к префикс-функции p( ) S = [0,0,1,2,0,0] и используем число в пятой ячейке, равное 0. Это означает, что в просмотренной части строки нет суффикса, который является префиксом исходной подстроки. В этом случае можно осуществить максимальный сдвиг на 5–0 = 5 шагов. На третьем шаге все элементы подстроки совпали, соответственно задача нахождения входа подстроки в строку решена. |