Статические линейные структуры данных. Стандартные структурированные данные.
Министерство образования и науки Российской Федерации
Санкт-Петербургский государственный электротехнический
университет “ЛЭТИ”
КОНСПЕКТ ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ
«СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ»
Для подготовки бакалавров по направлениям:
230400 – «Информационные системы и технологии»
Санкт-Петербург
2010
Конспект лекций по дисциплине
«Структуры и алгоритмы обработки данных»
При подборе материала использованы литературные и интернет ресурсы:
1.Алексеев А.Ю., Ивановский С.А., Куликов Д.В. Динамические структуры данных. Практикум по программированию. СПб.: СПбГЭТУ, 2000.
2.Вирт Н. Алгоритмы и структуры данных. – СПб: Невский Диалект, 2008.
3.Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов.- М.: Мир, 1981.
4.Иванов В.Н. Дискретная математика. Алгоритмы и программы: учеб. пособие. – М; Лаборатория Базовых Знаний. 2002.
5.Ключарев А.А., Матьяш В.А., Щекин С.В. Структуры и алгоритмы обработки данных. –СПб.: СПбГУАП, 2003.
6.Кнут Д. Искусство программирования для ЭВМ. Том 1: Основные алгоритмы.-.-М.:Издательский дом “Вильямс”, 2000.
7.Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск.- М.:Издательский дом “Вильямс”, 2000.)
8.Кормен Т., Лейзерсон Ч., Ривест Р., Штейн К. Алгоритмы. Построение и анализ. –М.: Вильямс, 2007.
9.Кристофидес Н. Теория графов. Алгоритмический подход.- М.: Мир, 1978.
10. Кузнецов С.Д.,Методы сортировки и поиска. http://citforum.ru
|
|
|
11.Лойко В.И. Структуры и алгоритмы обработки данных.- Краснодар: КубГАУ. 2000.
12.Макконел Д. Основы современных алгоритмов. – М:Техносфера, 2004.
13. Шень, А. Программирование: теоремы и задачи. – М.: Московский центр непрерывного математического образования, 1995.
14.http://algolist.manual.ru
15.http://www.intuit.ru
ЛЕКЦИЯ 1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ. КЛАССИФИКАЦИЯ СТРУКТУР ДАННЫХ.ОЦЕНКА СЛОЖНОСТИ АЛГОРИТМОВ
Цели и задачи лекции: ознакомить с программой дисциплины, с классификацией данных, повторить и обобщить концепцию типов данных.
Основные вопросы: структуры данных и алгоритмы, концепция типов данных, простые и структурированные данные; файлы, прямой и последовательный доступ; классификация структур данны, оценка сложности алгоритмов
.
Введение. Цели и задачи дисциплины.
“ Целью дисциплины «Структуры и алгоритмы обработки данных» является изучение способов организации данных, разработки и анализа алгоритмов, взаимосвязи алгоритмов и структур данных. Знание этих структур и алгоритмов позволяет осуществлять выбор оптимальных способов решения задач при создании программного обеспечения различного назначения.
Задачи дисциплины:Сформировать базовые теоретические понятия, лежащие в основе процесса разработки алгоритмов и структур данных, знания об основных классах алгоритмов и используемых в них структурах данных, способах оценки алгоритмов и структур обработки данных, общих схемах решения задач на их основе. Научить программной реализации типовых алгоритмов и структур данных и их модификаций .
|
|
|
Требования к уровню освоения дисциплины
В результате изучения дисциплины студенты должны
Знать:основные методы разработки машинных алгоритмов и программ, структуры данных, используемые для представления типовых информационных объектов, основные задачи анализа алгоритмов; основные машинные алгоритмы и характеристики их сложности для типовых задач.
Уметь:разрабатывать алгоритмы, используя типовые схемы, методы и приемы построения алгоритмов, выбирая подходящие структуры данных для представления информационных объектов; доказывать корректность составленного алгоритма и оценивать основные характеристики его сложности;
реализовывать алгоритмы и используемые структуры данных средствами языков программирования высокого уровня
Иметь представление : о классификации алгоритмических задач по их сложности, о сводимости алгоритмических задач к известным задачам определенного класса сложности.
|
|
|
Классификация структур данных, концепция данных
Классификация структур данных
Алгоритм - это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату.
Базовые управляющие алгоритмические конструкции: следование, ветвление, цикл с предусловием.
Под структурой данных в общем случае понимают множество элементов данных и множество связей между ними.
Понятие физическая структура данных отражает способ физического представления данных в памяти машины и называется еще структурой хранения, внутренней структурой или структурой памяти. Рассмотрение структуры данных без учета ее представления в машинной памяти называется абстрактной или логической структурой.
В зависимости от размещения физических структур, а соответственно, и доступа к ним, различают внутренние (находятся в оперативной памяти) и внешние (на внешних устройствах) структуры данных.
Различаются элементарные (простые, базовые, примитивные) структуры данных и составные (интегрированные, композитные, сложные).
|
|
|
По признаку изменчивости различают структуры статические и динамические.
Понятие «структуры данных» тесно связано с понятием «типы данных». Любые данные, т. е. константы, переменные, значения функций или выражения, характеризуются своими типами.
Информация по каждому типу однозначно определяет:
- структуру хранения данных указанного типа, т. е. выделение памяти, представление данных в ней и метод доступа к данным;
-множество допустимых значений, которые может иметь тот или иной объект описываемого типа:
- набор допустимых операций, которые применимы к объекту описываемого типа.
Различают простые типы данных и составные (структурированные).
К простым стандартным относят перечисленные ниже типы.
1) Целый.
2) Вещественный.
3) логический;
d) символьный;
4) ссылочный(указатель)
К пользовательским относят:
a) перечисляемый;
b) интервальный (диапазон).
В любом порядковом типе можно выделить подмножество значений, определяемое минимальным и максимальным значениями, в которое входят все значения исходного типа, находящиеся в этих границах, включая сами границы. Такое подмножество определяет диапазонный тип.
Статические линейные структуры данных. Стандартные структурированные данные.
Одномерный массив (вектор). Вектор - это чисто линейная упорядоченная структура, где отношение между ее элементами есть строго выраженная последовательность элементов структуры.
Многомерные массивы. В общем случае элемент массива - это есть элемент вектора, который сам по себе тоже является элементом структуры.
Строки. Строка последовательность символов кодовой таблицы.
Множества. Множества- структурированный тип данных, представляющий набор взаимосвязанных по какому либо признаку объектов, которые можно рассматривать как единое целое.
Записи
Запись предполагает множество элементов разного типа. Элементы данных в записи часто называют полями записи.
Элемент записи может включать в себя записи. В этом случае возникает сложная иерархическая структура данных.
Файлы. Файл-поименованная область памяти на внешнем носителе. Различают файлы последовательного и прямого доступа.
Таблицы
Таблица - это конечный набор записей.
Элементом данных таблицы является запись. Поэтому операции, которые производятся с таблицей - это операции, производимые с записью.
Операции с таблицами:
1. Поиск записи по заданному ключу.
2. Занесение новой записи в таблицу.
3 Удаление записи из таблицы
Ключ - это идентификатор записи. Для хранения этого идентификатора отводится специальное поле. Первичные ключи – это ключи, позволяющие однозначно идентифицировать запись. Составной ключ - ключ, содержащий два или более двух полей.
Дата добавления: 2018-05-02; просмотров: 488; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!