WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Нижегородский государственный технический университет

им. Р.Е. Алексеева»

Кафедра "Информационные радиосистемы"

Реализация динамических структур на массиве

Методические указания к лабораторной работе № 1

по дисциплине «Информационные технологии» для студентов направления подготовки бакалавра 210400 «Радиотехника»

дневной формы обучения Нижний Новгород 2012 Составили: Е.Н.Приблудова, С.Б.Сидоров, М.В.Уханов УДК 621.325.5-181.4 Реализация динамических структур на массиве: метод. указания к лаб. работе по дисциплине «Информационные технологии» для студентов направления подготовки бакалавра 210400 «Радиотехника» дневной формы обучения / НГТУ; сост.: Е.Н.Приблудова, С.Б.Сидоров, М.В.Уханов. Н.Новгород, 2012, с.

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

Научный редактор А.Г.Рындык Редактор Э.Б.Абросимова Подп. к печ. Формат 60x84 1/16. Бумага газетная.

Печать офсетная. Печ.л. 0,75. Уч.-изд.л. 0,5. Тираж Заказ.

Нижегородский государственный технический университет им. Р.Е.Алексеева Типография НГТУ. 603950, Н.Новгород, ул.Минина, 24.

Нижегородский государственный технический университет им. Р.Е.Алексеева, Приблудова Е.Н., Сидоров С.Б.,, М.В.Уханов, 1. Цель работы Практическое изучение методики непрерывной реализации динамической структуры на массиве.

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

Будем рассматривать структуры данных (сложноорганизованные типы данных), которые представляют собой конечную совокупность некоторых объектов (элементов) одного и того же типа E. Между собой структуры различаются тем, как именно они работают с элементами, т.е. отличаются набором операций над элементами и способом упорядоченности элементов, или, говоря иначе, заданным отношением следования между элементами.

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

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

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

стек, динамический вектор, очередь, дек, список, последовательность, множество, дерево, двоичное дерево.

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

Как правило, динамические структуры не являются предопределенными типами данных в языках программирования. Отсюда вытекает необходимость реализации поддержки требуемых динамических структур. Эта реализация должна быть проведена с использованием средств и возможностей конкретного языка программирования. Часто рассматривается задача реализации одних динамических структур на базе других.

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

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

На рис. 1 приведена графическая иллюстрация общей схемы непрерывной реализации динамической структуры на массиве. Переменная First содержит индекс элемента массива, предшествующего первому элементу структуры, а Last - индекс последнего элемента. Индексы First и Last могут принимать значения от -1 до N-1. Если First = Last = -1, то динамическая структура не содержит элементов.

Рассмотрим некоторые динамические структуры, в частности:

Основные отличия приведенных динамических структур состоят в отношении следования элементов внутри структуры и в способах добавления или удаления элементов.

Стеком называется упорядоченный набор некоторого переменного числа объектов (возможно, нулевого), работающий по правилу, – "последний пришел, первый вышел". Часто стек определяется аббревиатурой LIFO – Last In First Out. Вершина стека – это индекс элемента, записанного последним.

Для стека определяются следующие операции:

- добавление одного элемента;



- проверка, определяющая, пуст ли стек;

- извлечение одного элемента.

Алгоритм добавления одного элемента в стек:

- увеличить индекс;

- добавить один элемент.

Проверяя пуст ли стек, необходимо выяснить равенство индекса –1.

Алгоритм извлечения одного элемента из стека:

- извлечь один элемент;

- уменьшить индекс.

На рис. 2 представлена графическая иллюстрация работы стека:

- добавление одного элемента (б);

- добавление еще одного элемента (в);

- извлечение одного элемента (г);

- извлечение еще одного элемента, стек пуст (д).

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

Часто очередь определяется аббревиатурой FIFO – First In First Out.

Рассмотрим идеи реализации динамической структуры типа очередь на массиве. Поскольку операции над очередью производятся с двух концов, то необходимо рассмотреть две переменные First и Last.

Для очереди определяются следующие операции:

- добавление одного элемента в конец очереди;

- проверка, определяющая: является ли очередь пустой;

- извлечение одного элемента из начала очереди.

Алгоритм добавления одного элемента в очередь:

- увеличить значение Last;

- добавить один элемент.

Алгоритм извлечения одного элемента из очереди:

- увеличить значение First;

- извлечь один элемент.

На рис. 3 представлена графическая иллюстрация работы очереди (переменные First и Last, обведенные пунктирной линией, обозначают предыдущие положения индексов):

- очередь пустая (а);

- добавление одного элемента (б);

- добавление еще одного элемента (в);

- извлечение одного элемента (г);

- извлечение еще одного элемента, очередь пустая (д);

- добавление двух элементов (по одному) на массиве, свернутом в кольцо (е).

При непрерывной реализации очереди необходимо решить ряд проблем.

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

Особая ситуация возникает при попытке занесения элемента в очередь, показанную на рис 3, е. В данном случае необходимо добавить сначала один элемент, затем другой в очередь. Но в конце очереди свободно место только под один элемент. В то же время из рисунка видно, что в массиве имеются свободные места для новых элементов. Возможно несколько подходов к решению данной проблемы.

Прежде всего, можно сдвинуть все элементы очереди в начало массива.

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

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

При этом выполняется соединение первого и последнего элементов массива. В этом случае следующим после крайнего слева элемента массива становится первый справа элемент массива. Если k – индекс элемента массива, а N – количество элементов в массиве, то индекс следующего за ним можно определить по формуле Таким образом, при добавлении нового элемента индекс элемента массива, куда необходимо произвести запись, определяется из приведенной формулы. Аналогичным способом производится и извлечение элемента из очереди.

При этом новое значение переменной First определяется по той же самой формуле.

Обобщением очереди является динамическая структура дек. В такой динамической структуре добавлять и извлекать элементы можно с любой стороны.

При организации динамической структуры дек необходимо переменные First и Last расположить в середине массива рис. 4, а. В данном примере число элементов массива – четное, поэтому за середину может выбираться элемент с индексом 3 или 4. В нашем случае за середину выбран элемент с индексом 3. На рис. 4 представлена графическая иллюстрация работы дека.

Для дека определены следующие операции:

- добавление элемента в начало;

- добавление элемента в конец;

- проверка, определяющая: является ли дек пустым;

- извлечение элемента из начала;

- извлечение элемента из конца.

Алгоритм добавления одного элемента в начало дека:

- добавить один элемент с индексом First;

- уменьшить индекс First.

Алгоритм добавления одного элемента в конец дека:

- увеличить индекс Last;

- добавить один элемент с индексом Last.

Алгоритм извлечения одного элемента с начала дека:

- увеличить индекс First;

- извлечь один элемент с индексом First;

Алгоритм извлечения одного элемента с конца дека:

- извлечь один элемент с индексом Last;

- уменьшить индекс Last.

На рис. 4 представлена графическая иллюстрация работы дека:

- дек пуст (а);

- добавление одного элемента в начало и в конец (б);

- извлечение одного элемента из начала и из конца, дек пуст (в).

добавить в конец взять с конца добавить в конец взять 3. Порядок выполнения лабораторной работы 1. Подготовка к работе.

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

2. Выполнение работы.

Выполнение работы состоит в следующем:

- анализ варианта задания;

- разработка алгоритма решения задачи, определение структуры программы и данных, используемых в ней;

- представление разработанного алгоритма преподавателю;

- получение программной реализации на массиве одной из динамических структур (все операции оформить в виде функций);

- отладка полученной программы, реализующей основной набор операций с заданной динамической структурой;

- внесение в программу изменений, предложенных преподавателем.

3. Отчетность лабораторной работы.

Отчет по лабораторной работе должен содержать:

- исходные данные;

- алгоритм, составленный с помощью блок-схемы;

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

4. Контрольные вопросы Как Вы понимаете термин «структура данных»?

Что такое «динамическая структура данных»?

Приведите примеры динамических структур.

В чем заключается задача реализации одних динамических структур на базе других?

5. Что такое непрерывная реализация динамической структуры?

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

5. Список рекомендуемой литературы Павловская Т.А. С/C++. Программирование на языке высокого уровня:

учебник / Т.А.Павловская.- СПб.: Питер, 2005.

2. Шилдт, Г. Полный справочник по С, 4-е издание.: [пер. с анг.] / Г.Шилдт.М.: Вильямс, 2005.

3. Демидович Е. М. Основы алгоритмизации и программирования. Язык Си:

Учебное пособие / Е.М.Демидович.- БХВ-Петербург, 2008.





Похожие работы:

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ВЫПОЛНЕНИЕ И ОФОРМЛЕНИЕ КУРСОВЫХ РАБОТ ПО ФАРМАКОГНОЗИИ учебное наглядное пособие по специальности 060301 - Фармация Воронеж 20014 2 УДК 615.322 (076.5). Утверждено научно методическим советом фармацевтического факультета ( 15.03.05 г, протокол № 6 ) Составители: Т.Г. Афанасьева, И.М. Коренская Рецензент Кандидат...»

«Министерство образования и науки Российской Федерации Государственное образовательное учреждение высшего профессионального образования Чувашский государственный педагогический университет им. И. Я. Яковлева Психология рекламной деятельности Учебно-методический комплекс дисциплины Специальность 032401 Реклама Чебоксары 2010 УДК 659.1.013(075.8) ББК 88.493р30 П 863 Психология рекламной деятельности : учебнометодический комплекс дисциплины : специальность 032401 Реклама / сост. Е. А. Андреева. –...»

«УДК 615.15.37:001.81 КОМПЛЕКСНЫЙ ПОДХОД К УЧЕБНО-ВОСПИТАТЕЛЬНОЙ РАБОТЕ С ЦЕЛЬЮ ПОВЫШЕНИЯ КАЧЕСТВА ПОДГОТОВКИ ПРОВИЗОРОВ Гаврилин М.В., Курегян А.Г., Куль И.Я., Степанюк С.Н., Благоразумная Н.В., Дуккардт Л.Н., Арчинова Т.Ю., Сенченко С.П. ГБОУ ВПО Пятигорская государственная фармацевтическая академия Росздрава, Пятигорск, Россия,(357532, Пятигорск, пр. Калинина, 11),e-mail :[email protected] Разработан комплексный подход к процессу обучения студентов на кафедре фармацевтической химии Пятигорской...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего профессионального образования Национальный исследовательский ядерный университет МИФИ Технологический институт - филиал НИЯУ МИФИ кафедра ТЕХНИЧЕСКИХ СИСТЕМ КОНТРОЛЯ И УПРАВЛЕНИЯ ЭКОНОМИКА И ОРГАНИЗАЦИЯ ПРОИЗВОДСТВА Методическая разработка по выполнению экономической части ДИПЛОМНОГО ПРОЕКТА Направление 220200 Автоматизация и управление Специальность 220201 Управление...»

«© Абдульмянов С.Н., Веретенникова М.В. Физическая география материков и океанов (из опыта работы). Справочно-информационное учебное пособие. Часть 1. Практикум Лекции по курсу: Физическая география материков и океанов. 4 курс. 7 семестр. 01. Антарктика. Исследователи. Антарктический материк в силу своего исключительного географического положения, изолированности, труднодоступности представляет уникальные возможности естественной лаборатории не только для изучения природы антарктического...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РФ ДЕПАРТАМЕНТ НАУЧНО-ТЕХНОЛОГИЧЕСКОЙ ПОЛИТИКИ И ОБРАЗОВАНИЯ ФГОУ ВПО КОСТРОМСКАЯ ГСХА Кафедра философии ФИЛОСОФИЯ Учебно-методическое пособие для студентов всех специальностей заочной формы обучения 3-е издание, исправленное и дополненное КОСТРОМА КГСХА 2008 УДК-11/13 ББК 87 Ф 56 Составитель: к.ф.н, доцент, зав. кафедрой философии ФГОУ ВПО Костромская ГСХА Ю.П. Пятин. Рецензент: к.и.н., доцент кафедры истории и культурологии ФГОУ ВПО Костромская ГСХА Т.А....»

«ВНИМАНИЕ учащимсязаочникам! Данный экземпляр методических рекомендаций является предварительным, черновым вариантом и будет дорабатываться. Изменениям подвергнутся методические рекомендации по изучению учебной дисциплины и рекомендации по выполнению домашних контрольных работ. Задания для домашних контрольных работ и распределение их по вариантам изменены НЕ БУДУТ!!!!!! Приносим извинения за временные неудобства. Администрация 1 МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ Учреждение...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Сочинский государственный университет туризма и курортного дела Филиал Сочинского государственного университета туризма и курортного дела в г.Н.Новгород Факультет менеджмента СБОРНИК МЕТОДИЧЕСКИХ МАТЕРИАЛОВ первого года обучения (1 -2 курс) для студентов очно-заочной формы обучения факультета менеджмента Нижний Новгород 2010 ББК 65.290-2 С 23 Сборник методических материалов по учебным дисциплинам 1 года обучения (1 -2...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Сыктывкарский лесной институт (филиал) федерального государственного бюджетного образовательного учреждения высшего профессионального образования Санкт-Петербургский государственный лесотехнический университет имени С. М. Кирова (СЛИ) Кафедра экономики отраслевых производств ИСТОРИЯ ЭКОНОМИЧЕСКОЙ НАУКИ В РОССИИ Учебно-методический комплекс для студентов по направлению 080000 Экономика и управление специальности 080109 Бухгалтерский учет,...»

«Государственное образовательное учреждение Высшего профессионального образования Липецкий государственный технический университет Металлургический институт УТВЕРЖДАЮ Директор металлургического института В.Б. Чупров _2011 г. РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ (МОДУЛЯ) ПОДЪЕМНО-ТРАНСПОРТНЫЕ МАШИНЫ Направление подготовки: 151000 Технологические машины и оборудование Профиль подготовки: Металлургические машины и оборудование Квалификация (степень) выпускника: бакалавр Форма обучения: очная г. Липецк –...»

«Министерство транспорта Российской Федерации Федеральное агентство железнодорожного транспорта ГОУ ВПО Дальневосточный государственный университет путей сообщения Кафедра Экономика транспорта В.В. Комарова О.Б. Кадурова ЦЕНООБРАЗОВАНИЕ НА ТРАНСПОРТЕ Рекомендовано Методическим советом в качестве учебного пособия Хабаровск Издательство ДВГУПС 2006 УДК 338.47:656.2(075.8) ББК У9(2)372.1я73 К 630 Рецензенты: Кафедра Экономика транспорта Самарского государственного университета путей сообщения...»

«ПРОФСОЮЗ РАБОТНИКОВ НЕФТЯНОЙ, ГАЗОВОЙ ОТРАСЛЕЙ ПРОМЫШЛЕННОСТИ И СТРОИТЕЛЬСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ УЧЕБНО МЕТОДИЧЕСКОЕ ПОСОБИЕ КНИГА II МОСКВА 2005 Мотивация профсоюзного членства. Книга II. М.: ЗАО ИПК МИнИн Центр, 2006. 64 с. Настоящее пособие из серии В помощь профсоюзным преподавателям подготовлено для подготовки и проведения семинара по теме Мотивация профсоюзного членства. В пособии подробно разбирается понятие мотивация, дается описание статусных групп профсоюза, причины, влияющие на...»

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. Ломоносова Юридический факультет А. М. АРБУЗКИН ОБЩЕСТВОЗНАНИЕ Учебное пособие Издание четвертое, переработанное и дополненное Москва ЗЕРЦАЛО М 2011 ББК 67 Арбузкин, А. М. Обществознание: Учебное пособие. 4 е изд., перераб. и доп. — М.: ИКД Зерцало М, 2011. — 608 с. ISBN 978 5 94373 192 1 Пособие по учебному курсу Обществознание подготовлено в соот ветствии с программой вступительных экзаменов в высшие учебные заве дения гуманитарного профиля и...»

«Уважаемые выпускники! В перечисленных ниже изданиях содержатся методические рекомендации, которые помогут должным образом подготовить, оформить и успешно защитить выпускную квалификационную работу. Рыжков, И. Б. Основы научных исследований и изобретательства [Электронный ресурс] : [учебное пособие для студентов вузов, обучающихся по направлению подготовки (специальностям) 280400 — Природообустройство, 280300 — Водные ресурсы и водопользование] / И. Б. Рыжков.— СанктПетербург [и др.] : Лань,...»

«О порядке присвоения учебным изданиям грифа УМО 1. Общие положения 1.1. Положение разработано в соответствии с приказами Министерства образования Республики Беларусь № 57 от 17.02.2003 Об учебно-методических объединениях высших учебных заведений Республики Беларусь по профилям, направлениям и специальностям подготовки специалистов (далее – УМО), № 509 от 08.09.2005 О внесении изменений и дополнений в приказы № 57 от 17.02.2003 и № 327 от 27.04.2004, Положением об учебно-методическом объединении...»

«Издательство норматИвно-правовой лИтературы представляет Учебно-методическое издание для врачей-педиатров Визуальная педиатрия унИкальное учебно-методИческое ИзданИе для участковых врачей-педИатров вИзуальная педИатрИя ребенок работа Врачебный контроль роВый Вы и Ваш здо желанный в москве ребенок за здороВьем ребенка АктуАльные вАкАнсии Учебно-методическое издание За последнее десятилетие произошло значительное развитие медицинской науки, что привело для врачей-педиатров к новым открытиям,...»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Факультет экономики и менеджмента Кафедра экономики и менеджмента недвижимости и технологий Озеров Е.С., Пупенцова С.В. Документальное сопровождение оценки недвижимой собственности Методические указания по подготовке и оформлению курсовых и квалификационных работ студентов...»

«ФГБНУ Центр исследования проблем воспитания, формирования здорового образа жизни, профилактики наркомании, социально-педагогической поддержки детей и молодежи (г. Москва) Департамент общего образования Томской области Департамент образования администрации Города Томска Томский научный центр Сибирского отделения Российской академии наук Национальный исследовательский Томский государственный университет Федеральное государственное бюджетное учреждение высшего профессионального образования Томский...»

«Федеральное агентство по образованию ГОУ ВПО Челябинский государственный университет Институт психологии и педагогики С.В. Сидоров Управление процессами в школьном инновационном менеджменте Шадринск 2007 УДК 373 ББК 74.204 С 347 Сидоров С.В. Управление процессами в школьном инС 347 новационном менеджменте: науч.-метод. пособие / под ред. С.А. Репина. – Шадринск: изд-во Шадринский Дом Печати, 2007. – 95 с. Рецензенты: В.В. Базелюк, доктор педагогических наук, профессор, проректор по НИР...»

«ТРЕБОВАНИЯ К ОСНАЩЕНИЮ ОБРАЗОВАТЕЛЬНОГО ПРОЦЕССА В СООТВЕТСТВИИ С СОДЕРЖАТЕЛЬНЫМ НАПОЛНЕНИЕМ УЧЕБНЫХ ПРЕДМЕТОВ ФЕДЕРАЛЬНОГО КОМПОНЕНТА ГОСУДАРСТВЕННОГО СТАНДАРТА ОБЩЕГО ОБРАЗОВАНИЯ БИОЛОГИЯ ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Основания и цели разработки требований Настоящие требования разработаны на основе федерального компонента государственного образовательного стандарта общего образования по биологии (для основной средней школы, базового и профильного уровней полной средней школы). Материал представляют...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.