ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Массивы и структурированные типы данных

Содержание

Введение...................................................................................................................................... 3

Рекомендуемая литература................................................................................................... 3

Требования к оформлению отчетов по лабораторным работам................................ 3

Работа №1. Массивы автоматические, статические и динамические....................... 3

Работа №2. Массивы и структурированные типы данных.......................................... 7

Работа №3. Файлы.................................................................................................................... 9

Работа №4. Очереди и стеки................................................................................................ 11

Работа №5. Связные списки................................................................................................. 12

Работа №6. Сортировка массивов..................................................................................... 13

Работа №7. Сортировка списков........................................................................................ 14

Работа №8. Поиск в массивах и списках......................................................................... 16

Работа №9. Двоичные деревья............................................................................................ 17

Введение

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

Лабораторные работы ориентированы на применение языка С++, хотя может быть использован и другой язык программирования.

Рекомендуемая литература

1. Вирт Н. Алгоритмы и структуры данных.: Пер. С англ. - М.: Мир, 2001.

2. Топп У., Форд У. Структуры данных в С++. 1999.

3. Седжвик Р. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск. 2001.

4. Хэзфилд Р., Кирби Л. Искусство программирования на C. Фундаментальные алгоритмы, структуры данных и примеры приложений. 2001.

5. Подбельский В.В. Язык Си++. - М.: Финансы и статистика, 1995.

Требования к оформлению отчетов по лабораторным работам

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

Лабораторная работа №1

Массивы автоматические, статические и динамические

Подготовка к работе. По указанной литературе и конспекту лекций повторить темы «Типы данных», «Массивы», «Указатели», «Операции с динамической памятью».

Разработать программу в соответствии с заданием к лабораторной работе.

Задание.

1. Определить в функции main() переменные и массивы по таблице 1 в соответствии с вариантом:

Таблица 1

№	Переменные	№	Переменные
	1. Одномерный символьный массив; 2. Указатель на тип char; 3. Статический одномерный массив целых чисел; 4. Указатель на массив целых чисел; 5. Трехмерный массив целых чисел; 6. Указатель на двумерный массив целых чисел.		1. Одномерный массив плавающих чисел; 2. Указатель на тип float; 3. Статический одномерный массив беззнаковых целых чисел; 4. Указатель на массив unsigned int; 5. Трехмерный массив символов; 6. Указатель на двумерный массив символов.
	1. Одномерный массив целых чисел; 2. Указатель на тип int; 3. Статический одномерный символьный массив; 4. Указатель на массив символов; 5. Трехмерный массив плавающих чисел; 6. Указатель на двумерный массив плавающих чисел.		1. Одномерный символьный массив; 2. Указатель на тип char; 3. Статический одномерный массив типа double; 4. Указатель на массив типа double; 5. Трехмерный массив целых чисел; 6. Указатель на двумерный массив целых чисел.
	1. Одномерный символьный массив; 2. Указатель на тип char; 3. Статический одномерный массив длинных чисел; 4. Указатель на массив длинных целых чисел; 5. Трехмерный массив плавающих чисел; 6. Указатель на двумерный массив плавающих чисел.		1. Одномерный массив целых чисел; 2. Указатель на тип int; 3. Статический одномерный массив плавающих чисел; 4. Указатель на массив плавающих чисел; 5. Трехмерный массив символов; 6. Указатель на двумерный массив символов.
	1. Одномерный массив длинных целых чисел; 2. Указатель на тип long int; 3. Статический одномерный массив символов; 4. Указатель на массив символов; 5. Трехмерный массив целых чисел; 6. Указатель на двумерный массив целых чисел.		1. Одномерный массив типа double; 2. Указатель на тип double; 3. Статический одномерный массив беззнаковых целых чисел; 4. Указатель на массив unsigned int; 5. Трехмерный массив символов; 6. Указатель на двумерный массив символов.
	1. Одномерный массив типа float; 2. Указатель на тип float; 3. Статический одномерный массив символов; 4. Указатель на массив символов; 5. Трехмерный массив целых чисел; 6. Указатель на двумерный массив целых чисел.		1. Одномерный массив беззнаковых целых чисел; 2. Указатель на тип unsigned int; 3. Статический одномерный массив символов; 4. Указатель на массив символов; 5. Трехмерный массив целых чисел; 6. Указатель на двумерный массив целых чисел.
	1. Одномерный символьный массив; 2. Указатель на тип char; 3. Статический одномерный массив коротких целых чисел; 4. Указатель на массив коротких целых чисел; 5. Трехмерный массив целых чисел; 6. Указатель на двумерный массив целых чисел.		1. Одномерный массив типа float; 2. Указатель на тип float; 3. Статический одномерный массив символов; 4. Указатель на массив символов; 5. Трехмерный массив unsigned int; 6. Указатель на двумерный массив беззнаковых целых чисел.
	1. Одномерный массив коротких целых чисел; 2. Указатель на тип short int; 3. Статический одномерный массив символов; 4. Указатель на массив символов; 5. Трехмерный массив целых чисел; 6. Указатель на двумерный массив целых чисел.		1. Одномерный символьный массив; 2. Указатель на тип char; 3. Статический одномерный массив плавающих чисел; 4. Указатель на массив плавающих чисел; 5. Трехмерный массив целых чисел; 6. Указатель на двумерный массив целых чисел.
	1. Одномерный массив типа double; 2. Указатель на тип double; 3. Статический одномерный массив целых чисел; 4. Указатель на массив целых чисел; 5. Трехмерный массив символов; 6. Указатель на двумерный массив символов.		1. Одномерный массив целых чисел; 2. Указатель на тип int; 3. Статический одномерный массив типа double; 4. Указатель на массив типа double; 5. Трехмерный массив символов; 6. Указатель на двумерный массив символов.

2. В функции main() выполнить следующие действия:

1. Проверить содержимое массива №1 (с помощью цикла for и операции вывода cout<<).

2. Ввести данные в массив №1 (с помощью цикла for и операции ввода cin>>).

3. Еще раз проверить содержимое этого массива, сделать выводы.

4. Присвоить указателю №2 адрес массива №1, вывести на экран адреса массива и указателя и содержимое указателя. Сделать выводы.

5. Повторить пункт 3 для указателя, содержащего адрес массива. Сделать выводы.

6. Повторить пункты 1 – 3 для статического массива №3. Сделать выводы.

7. Используя имеющийся указатель №2, создать динамический массив и повторить для него пункты 1 – 3. Сделать выводы.

8. Удалить динамический массив. Используя указатель №4, создать двумерный динамический массив и повторить для него пункты 2, 3. Сделать выводы. Удалить двумерный динамический массив.

9. Вывести на экран любой из элементов трехмерного массива №5, используя операцию индексации.

10. Повторить пункт 9, используя имя массива как указатель и операцию доступа по указателю.

11. Присвоить указателю №6 на двумерный массив адрес трехмерного массива №5. Повторить для этого указателя пункт 10. Сделать выводы.

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

Сохранить файл с текстом программы для следующей работы.

Контрольные вопросы.

1. По каким признакам классифицируются структуры данных?

2. К какой группе структур данных относятся автоматические массивы?

3. Что означает понятие «тип данных»?

4. Какую информацию можно извлечь из типа данных?

5. К какой группе структур данных относятся статические массивы?

6. К какой группе структур данных относятся динамические массивы?

7. Что такое указатели?

8. Какие операции можно выполнять над указателями?

9. В чем заключается связь между указателями и массивами?

10. Какие операции обязательны при работе с динамическими массивами?

11. Свойства динамических массивов.

12. В чем заключается отличие между автоматическими и статическими массивами?

13. Можно ли изменить размер динамического массива при исполнении программы? Если да, то как это сделать?

14. Какое требование нужно соблюдать при присваивании адреса массива указателю?

15. Какие ограничения накладываются на определение многомерных динамических массивов?

16. В чем заключается отличие между именем массива и указателем?

Лабораторная работа №2

Массивы и структурированные типы данных

Подготовка к работе. По указанной литературе и конспекту лекций повторить темы «Массивы», «Указатели», «Структуры», «Операции с динамической памятью».

Разработать программу в соответствии с заданием к лабораторной работе.

Задание.

1. Определить структурный тип, содержащий следующие поля:

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

- указатель на тип char – для организации динамического массива, хранящего строку, например, с фамилией студента.

Остальные поля выбрать по варианту, приведенному в таблице 2.

Использовать одну из переменных для хранения некоторого идентификатора (номера); указатель на несимвольный тип – для организации динамического массива целых или плавающих чисел; другую переменную – для хранения размера этого массива;

Дополнить структурный тип любыми полями по своему выбору.

Таблица 2

№	Переменные	№	Переменные
	1. Переменная длинного целого типа; 2. Указатель на целый тип; 3. Переменная целого типа.		1. Переменная плавающего типа; 2. Указатель на тип float; 3. Переменная беззнакового целого типа.
	1. Переменная целого типа; 2. Указатель на тип int; 3. Переменная плавающего типа.		1. Переменная типа double; 2. Указатель на тип double; 3. Переменная целого типа.
	1. Переменная беззнакового длинного целого типа; 2. Указатель на длинный целый тип; 3. Переменная плавающего типа.		1. Переменная целого типа; 2. Переменная плавающего типа; 3. Указатель на плавающий тип.
	1. Переменная длинного целого типа; 2. Указатель на тип long int; 3. Переменная целого типа.		1. Переменная беззнакового целого типа; 2. Указатель на тип unsigned int; 3. Переменная символьного типа.
	1. Переменная типа float; 2. Указатель на тип float; 3. Переменная символьного типа.		1. Переменная беззнакового целого типа; 2. Указатель на тип unsigned int; 3. Переменная целого типа.
	1. Переменная символьного типа; 2. Указатель на короткий целый тип; 3. Переменная короткого целого типа.		1. Переменная типа float; 2. Указатель на тип float; 3. Переменная типа unsigned int.
	1. Переменная короткого целого типа; 2. Указатель на тип short int; 3. Переменная символьного типа.		1. Переменная плавающего типа; 2. Указатель на плавающий тип; 3. Переменная целого типа.
	1. Переменная типа double; 2. Указатель на тип double; 3. Переменная символьного типа.		1. Указатель на тип int; 2. Переменная типа double; 3. Переменная символьного типа.

2. Определить функции:

· инициализации структуры;

· заполнения массива чисел;

· вывода на экран массива чисел;

· ввода информации в строки имени и фамилии и другие поля;

· вывода на экран всех полей структуры, кроме массива чисел;

· функцию освобождения динамической памяти.

У половины функций, по выбору студента, одним из аргументов должен быть указатель на структуру, у второй половины – ссылка на структуру.

3. Определить функцию main(), в которой создать:

· объект ранее определенного структурного типа

· указатель на этот структурный тип.

С помощью указателя создать динамический массив объектов структурного типа из 3-х – 4-х элементов.

Для объекта последовательно вызывать функции инициализации, заполнения массива чисел, ввода данных в остальные поля, показа массива, показа полей.

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

Вывести на экран содержимое полей каждого элемента массива структур в цикле (for) с помощью соответствующих функций.

В конце функции main() вызвать функцию освобождения памяти для объекта структурного типа и в цикле для каждого элемента массива объектов.

Удалить динамический массив.

Ход выполнения программы контролировать по выводимым на экран сообщениям.

Сохранить файл с текстом программы для следующей работы.

Дополнительное задание.

Создать в функции main() блок, в котором определить локальный объект структурного типа. Ввести данные в поля локального объекта.

Попытаться вывести на экран содержимое полей локального объекта за пределами блока. Сделать выводы.

Контрольные вопросы.

1. Что представляет собой структурный тип данных?

2. Данные каких типов могут входить в состав структур?

3. Данные каких типов не могут входить в состав структур?

4. По каким признакам классифицируются структуры данных?

5. К какой группе структур данных относятся автоматические массивы?

6. Что означает понятие «тип данных»?

7. Какую информацию можно извлечь из типа данных?

8. К какой группе структур данных относятся статические массивы?

9. К какой группе структур данных относятся динамические массивы?

10. Что такое указатели?

11. Какие операции можно выполнять над указателями?

12. В чем заключается связь между указателями и массивами?

13. Какие операции обязательны при работе с динамическими массивами?

14. Каковы свойства динамических массивов?

15. Как обеспечить связь между массивами или структурами и функциями?

Лабораторная работа №3

Файлы

Подготовка к работе. По указанной литературе и конспекту лекций повторить темы «Массивы», «Структуры», «Файлы».

Разработать программу в соответствии с заданием к лабораторной работе.

Задание.

1. Определить функции записи и считывания структуры для двоичного и текстового файлов. У всех функций одним из аргументов должна быть ссылка на структурный тип, у функций работы с двоичными файлами еще одним аргументом должен быть указатель на тип FILE.

Использовать структурный тип и функции ввода и вывода на экран данных, определенные в программе к лабораторной работе №2.

2. Определить глобальные указатели на тип FILE для функций работы с двоичными файлами.

3. Определить функцию main(), в которой создать:

· указатели на тип FILE для функций работы с текстовыми файлами;

· указатель на структурный тип для организации динамического массива структур;

· первый динамический массив структур небольшого размера (3 – 4 элемента) – для ввода данных и их сохранения в файлах;

· второй динамический массив структур такого же размера – для считывания данных из текстового файла;

· третий динамический массив структур – для считывания данных из двоичного файла.

4. Ввести данные в элементы первого динамического массива с помощью функций, разработанных в лабораторной работе №2.

5. Сохранить содержимое элементов массива структур в текстовом и двоичном файлах.

6. Считать содержимое текстового файла в элементы второго массива и вывести на экран. Сравнить содержимое первого и второго массивов.

7. Считать содержимое двоичного файла в элементы третьего массива и вывести на экран. Сравнить содержимое первого и третьего массивов.

8. Просмотреть содержимое двоичного и текстового файлов с помощью любого тестового редактора или программы-просмотрщика (для просмотра тестового файла можно использовать «Блокнот» Windows, для просмотра двоичного файла рекомендуется Norton Commander или аналогичная программа). Установить соответствие между элементами данных в первом массиве и текстовом файле. Попытаться сделать то же самое для двоичного файла.

Сохранить файл с тестом программы для последующих работ.

Контрольные вопросы.

1. Что такое файл?

2. К какой группе структур данных относятся файлы?

3. Какие действия необходимо выполнить для работы с файлом?

4. Различаются ли файлы по типам?

5. Как в программах устанавливается связь с файлами?

6. Какие способы организации связи с файлами вам известны?

7. Какие операции можно выполнять над файлами?

8. Как открыть файл для записи?

9. Как открыть файл для считывания?

10. Какая функция позволяет узнать длину файла?

11. Как проверить, можно ли произвести запись в выбранный файл?

12. Можно ли считать данные из произвольного места в файле? Если да, то как это сделать?

13. Можно ли перемещаться по файлу? Если да, то с помощью какой функции?

14. Чем отличается запись действительных чисел в текстовый и двоичный файлы?

15. Как обеспечить связь между файлами и функциями?

Лабораторная работа №4

Очереди и стеки

Подготовка к работе. По указанной литературе и конспекту лекций повторить темы «Очереди», «Стеки».

Разработать программу в соответствии с заданием к лабораторной работе.

Задание.

1. Определить массив, который будет использован для организации очереди и стека. Тип массива выбрать по таблице №1 – массив №1.

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

2. Разработать функции занесения и извлечения данных для простой очереди, циклической очереди, стека на основе массива и на основе связного списка. Обратить внимание на аргументы функций. Можно использовать перегрузку функций.

3. В функции main() проверить работу простой и циклической очередей и обоих вариантов организации стека. Для простой очереди и стека на основе массива добиться их переполнения. Сделать то же самое для циклической очереди. Сделать выводы.

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

Сохранить файл с тестом программы для последующих работ.

Дополнительное задание.

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