Учебно-методическое пособие Нижний Новгоpод 2007 удк



Скачать 300.14 Kb.
страница1/9
Дата11.01.2013
Размер300.14 Kb.
ТипУчебно-методическое пособие
  1   2   3   4   5   6   7   8   9

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ




Государственное образовательное учреждение высшего

Профессионального образования

Нижегоpодский госудаpственный унивеpситет им. Н. И. Лобачевского”

О. Г. Савихин




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

Учебно-методическое пособие

Нижний Новгоpод

2007


УДК

Савихин О. Г. СТРУКТУРЫ ДАННЫХ: Учебное пособие. - Нижний Новгород: Издательство Нижегородского госуниверситета, 2007. - с.

Рецензенты:

На пpимеpе контейнеpных классов демонстpиpуются возможности языка пpогpаммиpования С++ для pазpаботки абстpактных типов данных.

Методическое пособие пpеднозначено для студентов первого и втоpого куpсов, обучающихся по специальности пpикладная математика.

Нижегоpодский госудаpственный унивеpситет

им. Н. И. Лобачевского, 2007

О. Г. Савихин 1

1.Основные понятия структур данных 4

2.Вектор 5

3.Последовательность 5

3.1.Структура последовательности 5

3.2. Допустимые операции 5

3.3. Представления последовательности 6

3.4.Непрерывное представление последовательности 6

3.5.Частные случаи последовательности. 8

3.6.Ссылочное представление последовательности 15

3.6.1.Просмотр списка 16

3.6.2.Добавление нового элемента в список 16

3.6.3.Формирование списка 16

3.6.4.Удаление элемента из списка 16

3.6.5.Кольцевые списки 17

3.7.Представление линейного связного списка в виде класса. 17

} 18

3.8.Двухсвязные списки 19

3.9.Представление линейного двухсвязного списка в виде класса. 20

4.Иерархия неоднородных контейнерных классов 23

5.Применение шаблонов для построения контейнерных классов 35

6.Задачи 41

6.1.Числовые последовательности 41

6.2.Файл 41

6.3.Множество 41

6.4.Последовательность с повторениями 41

6.5.Преобразование последовательности с помощью стеков, очередей и деков 42

6.6.Сортировка 42

6.7.Полином 43

6.8. Матрица 43

7.литература 44


  1. Основные понятия структур данных



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

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


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

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

Структурированными типами данных называются такие структуры данных, составными частями которых являются другие структуры данных - простые или в свою очередь структурированные. Структурированные данные конструируются программистом с использованием средств построения данных, предоставляемых языками программирования.
Любая структура данных на абстрактном уровне может быть представлена в виде двойки , где D – конечное множество элементов, которые могут быть типами данных, либо структурами данных, а R – множество отношений, свойства которого определяют различные типы структур данных на абстрактном уровне.

Набор операций над структурами данных допускает следующую классификацию :

  1. Конструкторы – операции, которые создают объекты рассматриваемой структуры.

  2. Деструкторы – операции, которые разрушают объекты рассматриваемой структуры. Признаком этой операции является освобождение памяти.

  3. Модификаторы – операции, которые модифицируют соответствующие структуры объектов.

  4. Наблюдатели – операции, у которых в качестве элемента (входного параметра) используются объекты соответствующей структуры, а возвращают эти операции результаты другого типа. Таким образом, операции-наблюдатели не изменяют структуру, а лишь дают информацию о ней.

  5. Итераторы – операторы доступа к содержимому объекта по частям в определенном порядке.



Основные виды (типы) структур данных:

  1. Множество – конечная совокупность неповторяющихся элементов, у которой R=.

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

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

  4. вектор- массив, который размещается в динамической памяти.

  5. Последовательность(список) – абстрактная структура, у которой множество R состоит из одного отношения линейного порядка (т. е. для каждого элемента, кроме первого и последнего, имеются предыдущий и последующий элементы).

При помощи ограничении набора операций доступа получаются различные частные случаи последовательности

  • Стек

  • Очередь

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

  • Дек (doudle ended queque) или двухсторонняя очередь

  1. Дерево – множество R состоит из одного отношения иерархического порядка.

  2. Граф – множество R состоит из одного отношения бинарного порядка.


  1   2   3   4   5   6   7   8   9

Похожие:

Учебно-методическое пособие Нижний Новгоpод 2007 удк iconУчебно-методическое пособие Кострома 2007 удк 519. 8 (075)
Учебно-методическое пособие предназначено студентам вузов для аудиторной и самостоятельной работы, а также для подготовки к контрольным...
Учебно-методическое пособие Нижний Новгоpод 2007 удк iconУчебно-методическое пособие для аспирантов и соискателей ученой степени Кострома 2007 удк
Учебно-методическое пособие предназначено аспирантам и соискателям ученых степеней по всем специальностям для сдачи кандидатского...
Учебно-методическое пособие Нижний Новгоpод 2007 удк iconУчебно-методическое пособие Нижний Новгород 2007 ббк 40. 3
Учебное пособие предназначено для студентов, обучающихся по специальности 013400 Менеджмент и маркетинг в природопользовании
Учебно-методическое пособие Нижний Новгоpод 2007 удк iconИ. Г. Овчинникова Экспертиза эффективности речевой коммуникации в сми, учебно-методическое пособие. Пермь, 2007
Е. В. Зырянова, Е. М. Крижановская. Интернет-ресурсы и виртуальные словари для делового общения, учебно-методическое пособие. Пермь,...
Учебно-методическое пособие Нижний Новгоpод 2007 удк iconУчебно-методическое пособие Нижний Новгород
Черней О. Т. Диаграмма состояния железоуглеродистых сплавов: Учебно-методическое пособие. Н. Новгород: вгипу. 27с
Учебно-методическое пособие Нижний Новгоpод 2007 удк iconУчебно-методическое пособие издательство томского университета 2006 удк 543(076. 1): 087. 5 Ббк 24 Ш432 Шелковников В. В
Данное учебно-методическое пособие является электронной версией учебно-методического пособия «Расчеты ионных равновесий в химии»,...
Учебно-методическое пособие Нижний Новгоpод 2007 удк iconУчебно-методическое пособие для студентов физико-математических специальностей вузов Балашов 2009 удк 004. 43 Ббк 32. 97
Данное учебно-методическое пособие состоит из лабораторных работ, которые условно можно разбить на несколько частей
Учебно-методическое пособие Нижний Новгоpод 2007 удк iconУчебно-методическое пособие Кемерово 2007 удк 543(076. 1): 378. 147. 227 Ббк г4я73-41 ш 85

Учебно-методическое пособие Нижний Новгоpод 2007 удк iconУчебно-методическое пособие для студентов факультетов иностранных языков Балашов 2007 удк 81. 2Англ я73 ббк 803(075. 8) К12
К12 Лексический анализ семантической структуры художественного текста : учебно-метод пособие для студ фак-тов иностранных языков...
Учебно-методическое пособие Нижний Новгоpод 2007 удк iconУчебно-методическое пособие Санкт-Петербург 2007 ббк г
Учебно-методическое пособие предназначено для студентов I курса нехимических специальностей. Пособие составлено в соответствии с...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org