Программирование C++. Пензенский государственный университет введение в программирование на языке с лабораторный практикум пенза 2010 г 2
 Скачать 1.47 Mb.
|
|
N. Класс Данные Указатель на начало списка (список – очередь) Текущая длина очереди Максимальная длина очереди Методы Функции поместить значение в очередь (функция добавляет значение вконец списка выбрать значение из очереди (функция возвращает значение изначала списка и удаляет его из списка) длина очереди (функция возвращает количество элементов в списке) очередь заполнена (функция возвращает значение истина, если количество элементов списка равно N) вывести очередь (не изменяя содержимого списка, функция выводит все значения, которые хранятся в списке) 10) Двунаправленный линейный список целых чисел. Каждый элемент списка имеет указатель наследующий элемент списка и указатель на предыдущий элемент. Класс Данные Указатель на начало списка Методы поместить значение в список (функция добавляет значение вконец списка удалить значение из списка (функция удаляет значение из конца списка) вставить значение в список после элемента с порядковым номером M функция добавляет новый элемент в список после элемента с указанным номером. Если в списке меньше элементов, чем M, функция выводит предупредительное сообщение и не изменяет структуру списка) вывести список в прямом порядке (не изменяя содержимого списка, функция выводит все значения, которые хранятся в списке, от начала до конца списка) вывести список в обратном порядке (не изменяя содержимого списка, функция выводит все значения, которые хранятся в списке, от конца списка к началу) 81 5. ДОПОЛНИТЕЛЬНЫЕ ЗАДАНИЯ Обработка числовых массивов и строк Напишите функцию, которая осуществляет обработку информации по одному из условий, заданных ниже. Главная программа (main) осуществляет ввод исходных данных, передает их в функцию и выводит результаты, полученные из функции. 1) Для массива А, состоящего из N элементов a. Построить таблицу, каждая строка которой содержит значение элемента массива и количество его повторений в массиве. b. Найти индекс последнего положительного значения в массиве, которое делится без остатка на 10. Если такого элемента нетто выдать соответствующее сообщение. c. Найти последовательность положительных значений элементов массива элементы следуют друг за другом, максимальной длины. Если такой последовательности нет, выдать соответствующее сообщение. d. Записать в начало массива А элементы, имеющие нечетные значения, а вконец массива – четные значения. e. Назовем элемент А (i = 2, … , N-1) особым, если слева от него расположены элементы меньшие его индекса, а справа – большие. Найти количество таких элементов. f. Присвоить переменной F значение true, если элементы массива составляют строго убывающую арифметическую прогрессию с заданным шагом, ив противном случае g. Поменять местами минимальный и максимальный элементы массива, если индекс минимального элемента больше индеса максимального. В противном случае выдать соответствующее сообщение. h. Сформировать массив Виз таких элементов массива А, сумма которых не превышают заданное значение С. Если таких элементов в массиве А нетто выдать соответствующее сообщение. 2) Даны два массива X(N) и Y(M). Обменять максимальный элемент массива X и минимальный элемент массива Y и наоборот. 3) Даны два массива X(N) и Y(M). Вставить на первое место массива X максимальный элемент массива Y, на его место поставить последнй (вытесненный в результате вставки) элемент массива X. 4) Даны два массива X(N) и Y(M). Сформировать массив Z(N+M) из отрицательных элементов массивов X и положительных массива Y. Если таких элементов меньше N+M, то оставшимся элементам массива Z присвоить значение 0. 5) Даны массивы А, В состоящие из N элементов каждый. Присвоить переменной F значение true, если хотя бы один элементы массива А встречается в массиве В, ив противном случае 6) Задана целочисленная квадратная матрица A размерностью N: a. Поменять местами элементы матрицы, расположенные водном столбце и принадлежащие главной и побочной диагоналям 82 b. Найти максимальный элемент, расположенный на главной диагонали матрицы A, а из положительных элементов строки и столбца, на пересечении которых он находится, сформировать одномерный массив B c. Среди элементов, расположенных выше главной диагонали матрицы A, найти те элементы, которые удовлетворяют условию -10 Ai,j 10, и сформировать из них одномерный массив B d. Найти номер строки матрицы A, наиболее удаленной от последней строки, если расстояние S между строками L и K матрицы определяется по формуле j j K j L A A K L S ) ( ) , ( , , e. Сформировать одномерный массив B, элементы которого Bi равны true, если элементы го столбца матрицы A упорядочены по убыванию, ив противном случае f. Сформировать одномерный массив B, элементы которого Bi равны 1, если хотя бы один элемент ой строки матрицы A больше произведения элементов го столбца, ив противном случае. 7) Из массивов X(N) и Y(M) построить квадратную матрицу A размерностью K (K= M N ) таким образом, чтобы элементы массива Y были расположены на главной диагонали и ниже ее. 8) Задана целочисленная матрица A размерностью N×M и массив X(N). Присвоить заданное значение B элементам столбца матрицы с номером K, для которого X[K] 0. 9) Заданы целочисленные матрицы A, B размерностью N×N. Поменять местами столбец матрицы A, где расположен максимальный элемент, со строкой матрицы B, где расположен минимальный элемент. 10) Заданы целочисленные квадратные матрицы A, B размерностью N. Присвоить переменной F значение true, если матрица A имеет хотя бы одину строку с положительной суммой элементов большей, чем положительные суммы элементов строк матрицы B, ив противном случае. Если строка в матрице A с положительной суммой элементов не найдена, то выдать соответствующее сообщение 11) Заданы целочисленные квадратные матрицы A, B размерностью N. Поменять местами строку матрицы A, которая не содержит положительные элементы и имеет максимальный номер в матрице A, со столбцом матрицы B, произведение элементов которого положительно и номер которого минимальный в матрице B. Если строка в матрице A не найдена, то выдать соответствующее сообщение. Если столбец в матрице B не найден, то выдать соответствующее сообщение 12) Присвоить переменной F значение true, если из символов предложения S1 можно составить слово S2, ив противном случае. 13) Найти в предложении слова длиной не более 6 символов, в которых отсутствуют символы строки S2 (длина 3 символа. Если таких слов нет, выдать соответствующее сообщение. 14) Найти в предложении все слова, которые не являются палиндромами. 15) Заменить в предложении S1 все слова, в которых есть символы ‘a’ или ‘b’ на первое слово предложения S2, в котором есть символ ‘c’. Если таких слов нетто выдать соответствующее сообщение. 83 16) Найти в предложении все слова, в которых встречаются первые три символа последнего слова предложения. Если таких слов нет, выдать соответствующее сообщение. 17) В предложении S найти все слова, которые не содержат строку S1 (длина 2 символа) и содержат строку S2 (длина 3 символа. Если таких слов нет, выдать соответствующее сообщение. 18) В предложении S1 найти самое короткое слово, которое присутствует в предложении S2. Если такого слова нет, выдать соответствующее сообщение. 19) Присвоить переменной F значение true, если в предложении S1 есть хотя бы одно слово, которое отсутствует в предложении S2 , ив противном случае. 20) Присвоить переменной F значение true, если в предложении S1 есть хотя бы одно слово, которое присутствует в предложении S2 и длина которого не превышает 6 символов, в противном случае присвоить переменной F – false. 21) Сформировать предложении S из таких слов предложения S1, которые не содержат символы строки S2 (длина 3 символа. Если таких слов нет, выдать соответствующее сообщение. Динамические структуры данных Объявите заданную динамическую структуру данных и разработайте функции обработки значений данных этой структуры. Главная программа ( main ) осуществляет тестирование разработанных программных средств. 1) Однонаправленный линейный список целых чисел. Для работы со списком используются указатель на начало списка и указатель наконец списка. Функции поместить значение в список (функция добавляет значение в начало удалить значение из списка (функция удаляет значение из конца списка) вставить значение в список после элемента, имеющим целое значение M. Если в списке нет такого элемента, функция выводит предупредительное сообщение и не изменяет структуру списка вывести список в прямом порядке (не изменяя содержимого списка, функция выводит все значения, которые хранятся в списке, от начала до конца списка) найти максимальное значение в списке и поменять его со значением последнего элемента списка. 2) Двоичное число B, гдекаждая цифра bi=0,1 представлено в виде списка b 1, b 2, ... b n . Функции добавить элемент в список сформировать число B (используется функция добавить элемент в список) вывести число B вычислить десятичное значение числа B прибавить к числу B единицу 84 3) Отображение задано в виде списка пар (d 1, r 1 ), (d 2, r 2 ) … (d n, r n ), где d 1, d 2, ... d n – целые значения из области определения, а r 1, r 2, ... r n – символы ассоциированныес этими значениями. Функции добавить элемент (d i, r i ) в список вывести значения списка (на строке расположить значения d i, r i ) найти по значению d i ассоциированное с ним значение использовать функцию поиска для формирования строки по заданному массиву целых чисел (размерность массива 10) 4) Задан пример ориентированного графа (орграфа Реализовать описание орграфа следущим образом a. в виде связанных списков b. в виде динамических массивов Функции добавить вершину в орграф удалить вершину из орграфа добавить дугу в орграф удалить дугу из орграфа вывести матрицу смежности орграфа 85 5) Для формирования учебных планов используется структура данных, отражающая выбор студентами дополнительных дисциплин Реализовать структуру данных следущим образом a. в виде связанных списков. При этом студент может выбрать только одну дисциплину b. в виде связанных списков. При этом студент может выбрать не более трех дисциплин Функции сформировать список студентов вывести список студентов сформировать список дисциплин вывести список дисциплин сформировать выбор студентом дисциплины вывести результаты выбора студентов 6) Очередь представлена как динамический кольцевой массив ограничеснной длины Добавление в очередь перемещает указатель наконец очереди наследующий элемент массива. Удаление из очереди перемещает указатель на начало очереди к существующему следующему элементу. Функции добавить элемент в очередь (добавить вконец) удалить элемент из очереди (удалить изначала) очередь пуста очередь заполнена вывести содержимое очереди 86 7) Очередь c двусторонним доступом – как однонаправленный линейный список целых чисел, в который можно добавлять и удалять элементы с двух сторон. Задана максимальная длина очереди – N. a. реализовать дисциплину обслуживания FIFO (первым пришел – первым ушел) b. реализовать дисциплину обслуживания LIFO (последним пришел – первым ушел) Функции поместить значение в очередь выбрать значение из очереди длина очереди (функция возвращает количество элементов в списке) очередь заполнена (функция возвращает значение истина, если количество элементов списка равно N) вывести очередь (не изменяя содержимого списка, функция выводит все значения, которые хранятся в списке) 8) Очередь с приоритетами. Элементы имеющие более высокий приоритет помещаются ближе к началу очереди. При добавлении в очередь элемент располагается в конце последовательности элементов своего приоритета. Функции поместить значение в очередь (согласно приоритету) выбрать значение из очереди (изначала списка) длина очереди (функция возвращает количество элементов в списке) очередь заполнена (функция возвращает значение истина, если количество элементов списка равно N) вывести очередь (не изменяя содержимого списка, функция выводит все значения, которые хранятся в списке) Классы для создания и обработки динамических структур данных Темы заданий аналогичны заданиям из раздела 5.2. Объявите заданную динамическую структуру данных как класс и разработайте методы класса для обработки значений данных. Главная программа (main) осуществляет тестирование разработанных программных средств. Структура классов определяется аналогично заданиям 4.5.1. 87 ЛИТЕРАТУРА. Павловская ТА. С/C++.Программирование на языке высокого уровня. – СПб.: Питер, 2006. 2. Давыдов В.Г. Технология программирования. С. – СПб.: БХВ-Петербург, 2005. 3. Дейтел Х, Дейтел П. Как программировать на С. – М.:ЗАО Издательство БИНОМ, 2001. 4. Керниган Б, Пайк Р. Практика программирования – СПб.: Невский диалект, 2001. 5. Ахо А, Хопкрофт Д, Ульман Д. Структуры данных и алгоритмы. – М здательсктй дом «Вильямс», 2001. 6. Пол А. Объектно-ориентированное программирование на С. – СПб.: Невский диалект, 1999 |