Динамические структуры данных
Работа добавлена на сайт samzan.net:
Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Лабораторная работа № 11
Динамические структуры данных.
Цель работы – ознакомиться с возможностями использования динамической памяти для размещения переменных, получить навыки описания ссылочных переменных и их использования для обращения к динамическим переменным, освоить операции со ссылками и научиться создавать и использовать простейшие динамические структуры данных - списки.
Постановка задачи
Написать две программы согласно индивидуальному варианту.
При выполнении первого задания использовать массивы или матрицы, размещаемые в динамической памяти.
При выполнении второго задания исходные данные должны считываться с клавиатуры или из бинарного файла записей (в том числе созданного при выполнении лабораторной работы №9), и размещаться в линейном односвязном списке. Предусмотреть следующие операции над списком: добавление элемента, удаление элемента, редактирование элемента, просмотр всего списка, поиск элемента по указанному критерию, сохранение данных в бинарном файле.
Варианты заданий
Вариант № 1
- Дана матрица размера N*M (N<=150, M<=200). В каждой строке с отрицательным элементом на главной диагонали найти наибольший из элементов.
- Дан файл записей, содержащий сведения об ассортименте игрушек в магазине. Структура записи: название игрушки, цена, количество, возрастные границы, например от 2 до 5 лет. Считать данные из файла в односвязный линейный список. Вывести названия игрушек, которые подходят детям от 3 до 5 лет и стоят не больше Х рублей. Получить суммарную стоимость всех имеющихся в магазине кукол.
Вариант № 2
- Дана матрица размера N*M (N<=150, M<=200). Отсортировать каждый столбец матрицы по возрастанию, используя метод поиска максимума (метод выбора).
- В файле записей содержатся сведения о спортсменах: фамилия, пол, вид спорта, год рождения, рост. Считать данные из файла в односвязный линейный список. Найти самого молодого спортсмена, занимающегося плаванием, среди мужчин. Вывести сведения о спортсменках – женщинах, выступающих в возрастной категории от 20 до 30 лет.
Вариант № 3
- Дан одномерный динамический массив А, размер которого вводится и заранее неизвестен. Сформировать динамическую матрицу, в которой первая строка содержит элементы массива А, вторая строка – эти же элементы во второй степени, третья строка – в третьей степени и т.д. Количество строк матрицы вводится.
- Имеется файл записей, содержащий сведения о наличии билетов на рейсы Аэрофлота. Структура записи: номер рейса, пункт назначения, время вылета, цена билета, количество свободных мест в салоне. Считать данные из файла в односвязный линейный список. Произвести корректировку данных в списке при продаже билетов, исходные данные – номер рейса и количество проданных билетов. Получить сведения о рейсах в определенный город, на которые имеются непроданные билеты.
Вариант № 4
- Дана матрица размера N*M (N<=200, M<=160). Найти в ней количество элементов, превышающих среднее арифметическое элементов последнего столбца, и создать динамический одномерный массив из таких элементов, выделив под него строго необходимое количество памяти.
- Бинарный файл содержит информацию о наличии семян в магазине: название растения, время (месяц) высадки, количество семян в упаковке, стоимость одной упаковки. Считать данные из файла в односвязный линейный список. Вывести названия растений, семена которых можно высаживать с марта по май. Провести корректировку цены для самых дорогих семян на новое значение.
Вариант № 5
- Дана динамическая матрица размера N*M (N и M вводятся). В каждом столбце матрицы найти значение элемента, наиболее близкое к среднему арифметическому элементов этого столбца.
- Сведения о животных зоопарка находятся в бинарном файле. Запись состоит из полей: название животного, природная зона, затраты на корм за один день. Считать данные из файла в односвязный линейный список. Какие животные степной зоны содержатся в зоопарке? Сколько надо суммарно затратить на их пропитание в течение месяца (30 дней)?
Вариант № 6
- Дана матрица размера N*M (N<=150, M<=200). .Элементы 1й строки циклически сдвинуть на 1 позицию вправо, 2й строки на 2 позиции, 3й строки на 3 позиции и т. д.
- Дан файл, содержащий сведения о поступивших в продажу автомобилях. Записи содержат следующие поля: марка автомобиля, страна производитель, год выпуска, объем двигателя, расход бензина на 100 км, цена, количество экземпляров. Считать данные из файла в односвязный линейный список. Скорректировать данные о количестве автомобилей при продаже 1 машины определенной марки (исходные данные: марка машины, производитель, год выпуска). Вывести сведения об автомобилях, произведенных в России за два последних года.
Вариант № 7
- Даны два динамических одномерных массива X и Y размера N. Сформировать динамическую матрицу Z размера N*3, в которой первый столбец образуют элементы массива X, второй столбец - элементы массиваY, а третий столбец заполнен средними арифметическими значениями соответствующих пар элементов из X и Y ().
- В файле хранится информация о курортах мира: страна, город, название отеля, класс отеля, стоимость проживания за один день, стоимость проезда в оба конца. Считать данные из файла в односвязный линейный список. Вывести отели и страны, куда можно поехать на неделю, включая стоимость проезда, с наименьшими затратами.
Вариант № 8
- Дана динамическая матрица размера N*2 (N вводится). Каждая строка матрицы содержит значения координат X и Y одной точки на плоскости, матрица содержит координаты N точек. Найти координаты двух точек, наиболее удалённых друг от друга.
- Дан файл, содержащий сведения о химических элементах: название, символическое обозначение, массу атома, заряд ядра. Считать данные из файла в односвязный линейный список. Вывести сведения о химическом элементе по его символическому названию. Найти элемент с самой большой массой среди тех, названия которых начинаются с буквы ‘А’.
Вариант № 9
- Дана динамическая матрица размера N*M (N и M вводятся). В каждой строке матрицы найти среднее арифметическое чисел, расположенных между первым и последним положительными элементами строки, и заменить их найденным значением.
- Расписание движение поездов хранится в файле и содержит информацию: пункт назначения, номер поезда, тип поезда, время отправления, время в пути. Вывести сведения о поездах, следующих в Москву в определенный временной период. Считать данные из файла в односвязный линейный список. Найти поезд определенного типа, доезжающий до Москвы за наименьшее время. Выяснить, какие поезда отправляются после 22 часов.
Вариант № 10
- Дана динамическая матрица размера N*M (N и M вводятся). Среди столбцов матрицы, содержащих только элементы в диапазоне от 0 до 10, найти столбец с максимальной суммой.
- В файле хранятся сведения о личной библиотеке: фамилия автора, название, издательство, год издания, тематика книги. Считать данные из файла в односвязный линейный список. Вывести названия книг, изданных в определенном издательстве за последние 5 лет. Определить, имеются ли в библиотеке книги по определённой теме.
Вариант № 11
- Дана матрица размера N*M (N<=160, M<=200). Найти максимальный элемент той строки матрицы, сумма элементов которой минимальна.
- В файле содержатся сведения о сотрудниках лаборатории: фамилия, год рождения, пол, образование (среднее, высшее), год поступления на работу. Считать данные из файла в односвязный линейный список. Найти самого старшего сотрудника среди мужчин. Вывести список молодых специалистов (до 28 лет) с высшим образованием.
Вариант № 12
- Дана матрица размера N*M (N<=150, M<=180). Найти в ней первую по порядку строку, содержащую наибольшее количество нулей.
- Имеется файл, содержащий сведения об экспортируемых товарах: наименование товара, страна-импортер и объем поставляемой партии в штуках. Считать данные из файла в односвязный линейный список. Вывести список товаров, которые экспортируются в определенную страну и общий объем экспорта в эту страну.
Вариант № 13
- Дана матрица размера N*M (N<=160, M<=160). Среди элементов матрицы, лежащих выше главной диагонали, найти те, которые превышают все элементы, лежащие ниже главной диагонали. Вычислить их сумму.
- Результаты сдачи студентами экзаменационной сессии хранятся в файле, содержащем следующие данные: фамилия студента и оценки по физике, математике и информатике. Считать данные из файла в односвязный линейный список. Вывести количество двоек по каждому из предметов и вывести список студентов, имеющих двойки хотя бы по одному предмету.
Вариант № 14
- Дана матрица размера N*M (N<=150, M<=200). Отсортировать матрицу, переставляя её строки таким образом, чтобы элементы второго столбца были упорядочены по возрастанию.
- Каталог радиодеталей, имеющихся в магазине, хранится в файле и содержит следующие сведения: название радиодетали, тип, номинал, количество штук в наличии. Считать данные из файла в односвязный линейный список. Вывести сведения о конденсаторах с емкостью в диапазоне от С1 до С2. Получить перечень проданных радиодеталей, которых в наличии не осталось, и удалить сведения о них из массива.
Вариант № 15
- Дана матрица размера N* N (N<=160). Найти скалярное произведение строки с наибольшим элементом и столбца с наименьшим элементом.
- В файле содержатся сведения о пациентах глазной клиники. Структура записи: фамилия пациента, пол, возраст, место проживания (город), диагноз. Считать данные из файла в односвязный линейный список. Определить количество иногородних пациентов с диагнозом Х. Вывести список пациентов пенсионного возраста.
Вариант № 16
- Даны матрица размера N*M (N<=150, M<=180) и массив С из М элементов. Заменить массивом С ту строку матрицы, в которой среднее арифметическое элементов наименьшее.
- Дан файл, содержащий сведения об отправлении поездов дальнего следования с Московского вокзала: номер поезда, станция назначения, время отправления, время в пути, наличие билетов. Считать данные из файла в односвязный линейный список. Вывести список поездов в Москву и время их отправления. Получить информацию о наличии билетов на поезд с номером ХХХ.
Вариант № 17
- Даны матрица размера N*M (N<=150, M<=180) и натуральное число K (K<=N). Выяснить, имеются ли в строке матрицы с номером K элементы, для которых сумма элементов, расположенных левее, равна сумме элементов, расположенных правее. Если такие элементы имеются, то вывести их номера и значения.
- В файле хранятся сведения об архитектурных памятниках: название, местоположение, тип постройки, архитектор, год постройки. Считать данные из файла в односвязный линейный список. Вывести сведения о сооружениях определенного типа (например, “собор”), построенных в 18 веке. Найти самое старое творение определённого архитектора.
Вариант № 18
- Сформировать динамическую матрицу размера N*N (N вводится). Заполнить её следующим образом: в центре элемент (или элементы) со значением 1, вокруг – элементы со значением 2, далее – 3, и т.д. Например, при N=5 должна получиться матрица вида:
5 4 3 4 5
4 3 2 3 4
3 2 1 2 3
4 3 2 3 4
5 4 3 4 5
- В файле хранятся сведения о спортсменах по зимним видам спорта: фамилия, вид спорта, страна, результат, личный рекорд. Считать данные из файла в односвязный линейный список. Вывести сведения о спортсменах из указанной страны, занимающихся заданным видом спорта. Выяснить, сколько спортсменов улучшили свой личный рекорд.
Вариант № 19
- Дана динамическая матрица размера N*2 (N вводится). Она задаёт N отрезков на числовой оси. Первый элемент в каждой строке содержит начало одного отрезка, второй элемент – его конец. Определить, существует ли отрезок, являющийся пересечением всех заданных отрезков, и если да, то найти его.
- В файле хранятся сведения о вкладчиках банка: номер счета, паспортные данные, категория вклада, текущая сумма вклада, дата последней операции. Считать данные из файла в односвязный линейный список. Изменить данные при совершении операции приема любой суммы или выдачи денег в пределах имеющихся средств. Выяснить имеются ли вклады, операции по которым не совершались в течение последних 5 лет, и вывести сведения о них.
Вариант № 20
- Дана динамическая матрица размера N*M (N и M вводятся). Заменить нулями элементы первой и последней строк матрицы, а также её первого и последнего столбцов, используя для этого один цикл. Вывести элементы матрицы по спирали, начиная с центра, по часовой стрелке
- Дан файл, содержащий сведения о вступительных экзаменах в ВУЗ по результатам ЕГЭ по математике, русскому языку и английскому языку и дополнительному испытанию по профильному предмету: фамилия, баллы по предметам. Известна проходная сумма баллов. Считать данные из файла в односвязный линейный список. Вывести список абитуриентов, имеющих наибольшую сумму баллов по результатам ЕГЭ и дополнительному испытанию, и процент абитуриентов, не выдержавших конкурса.
Вариант № 21
- Дана динамическая матрица размера N*M (N и M вводятся). Вывести элементы матрицы в порядке их следования по диагоналям матрицы, параллельным главной диагонали, начиная с левого нижнего угла до правого верхнего угла. Найти, на какой диагонали сумма элементов максимальна.
- Даны два файла, содержащих сведения о нападающих для каждой из хоккейных команд: ”ЦСК” и “Динамо” соответственно: фамилии нападающих, число заброшенных ими шайб, сделанных голевых передач, заработанное штрафное время. Считать данные из файлов в односвязные линейные списки. Найти лучшего игрока обеих команд (фамилию нападающего, команду, сумму очков (голы + передачи)). Вывести фамилии и показатели результативности для игроков, не имеющих штрафного времени.
Вариант № 22
- Дана динамическая матрица размера N*M (N и M вводятся). Выяснить, какие из строк матрицы образуют арифметическую прогрессию. Для каждой такой строки вывести первый член прогрессии и её разность.
- Имеется 2 файла: первый содержит сведения о собранных сотрудниками цеха изделиях (фамилия сборщика, тип и количество собранных им изделий); второй - о расценках сборочных работ (тип изделия, стоимость сборки 1 изделия). Считать данные из файлов в односвязные линейные списки. Определить стоимость работ, выполненных сборщиком Х.
Контрольные вопросы.
- В каких областях оперативной памяти могут располагаться данные при выполнении программы?
- Какие переменные называют динамическими? Чем они отличаются от статических переменных?
- С какой целью используют динамические переменные?
- Как обращаются к динамическим переменным?
- Какие значения могут принимать ссылочные переменные?
- Какие бывают указатели? Как их описать?
- Как обозначается операция разыменования? Для чего она используется?
- Каким образом можно выделять память для динамических переменных и освобождать её?
- Как определить, выделена память или нет?
- Почему нельзя забывать освобождать выделенную память?
- Чему равно значение указателя после освобождения области памяти, на которую он указывал?
- Как разместить в динамической памяти матрицу очень большого размера?
- Что такое «рекурсивная структура данных»?
- Из каких элементов образуются списки? Каким образом элементы списка связываются между собой?
- Как называются операции «.» и «->»? Чем они отличаются? Когда используется каждая из них?
- Как найти конец списка?
- Чем различаются стратегии обслуживания стека и очереди?
- Как строится односвязный список со стековой организацией? Чем отличается организация очереди?
- Как выполняются поиск, удаление, вставка и добавление элементов в односвязный список?
- Можно ли вывести на экран данные из односвязного списка в обратном порядке?