Программирование C++. Пензенский государственный университет введение в программирование на языке с лабораторный практикум пенза 2010 г 2
 Скачать 1.47 Mb.
|
|
for (i=0; i for (j=0; j if (max < x.base[i][j]) max = x.base[i][j]; return max; } #endif Н Файл dinarray2.cpp использование динамического массива #include "dinarray2.h" //включение описания массива и файла int main() { array2d a, b; массива создание, вводи вывод значений, 3, a); input(a); print(a); массив b: создание, вводи вывод значений, 3, b); input(b); print(b); // поиски вывод максимальных значений массивов аи удаление массивов аи Результаты работы программы 45 3.8.3 Односвязный список Список это упорядоченная динамическая структура данных, каждый элемент которой содержит данные и ссылки, связывающие его с другими элементами Список называют односвязным (рисунок 3.4)., если элемент списка содержит только одну ссылку. Данные Указатель Данные Указатель Данные Указатель Указатель на начало списка NULL Рисунок 3.4 – Структура односвязного списка NULL – нулевой указатель обозначает конец списка (в программе можно использовать и значение 0 ). Пример Односвязный список Файл list1.h определение списка и его операций Н предотвращение многократного #define Н включения заголовочного файла #include using std::endl; using std::cout; Элемент списка struct Elem { int x; данные – целое значение Elem* next; указатель наследующий элемент списка }; Операции со списком Добавление элемента вконец списка void add_end(Elem **start, const int & a) { Elem *tmp, адрес нового, добавляемого элемента *cur; текущий указатель для прохода по списку tmp = new Elem; выделение памяти для нового элемента if (!tmp) { если память не выделена, тогда возврат память для элемента не выделена return ; } tmp->x = a; занесение данных в новый элемент tmp->next = NULL; новый элемент – последний в списке if (!*start) если список пуст, *start = tmp; формирование нового списка else { продвижение по списку до последнего элемента cur = *start; while (cur->next) пока cur->next неравно перемещение указателя наследующий элемент cur->next = tmp; ссылка последнего элемента на новый, добавляемый вконец списка } return ; } 46 Обратите внимание на прототип функции добавления элемента вконец списка void add_end(Elem **start, const int & a) Указатель на начало списка должен быть описан как двойной указатель. Значением start является указатель, который передается в функцию по адресу. Таким образом, в функции add_end формальный параметр start (указатель на начало списка) является указателем на указатель на структуру данных Удаление последнего элемента списка void del_end(Elem *start) { Elem *prev, указатель на предпоследний элемент списка *end; указатель на последний элемент списка if (!start){ если список пуст, Список пуст" < //тогда возврат return ; } if (!start->next){ если в списке один элемент, delete start; start=NULL; удаление списка return ; } продвижение по списку до последнего элемента end = start; while (end->next){ пока end->next неравно запоминание адреса предыдущего элемента end = end->next; перемещение указателя наследующий элемент } delete end; удаление последнего элемента списка prev->next = NULL; предпоследний элемент становится последним return ; } Вывод значений данных элементов списка void print_list( const Elem *start) { Elem *tmp; указатель на текущий элемент списка if (!start){ если список пуст, Список пуст тогда возврат return ; } продвижение по списку до последнего элемента tmp = const_cast while (tmp){ пока в списке есть элементы – tmp неравно вывод данных текущего элемента списка tmp = tmp->next; перемещение указателя наследующий элемент } cout< return ; } 47 Удаление списка void del_list(Elem *start) { Elem *tmp, *prev; вспомогательные указатели if (!start){ если список пуст, Список пуст тогда возврат return ; } продвижение по списку и удаление элементов tmp = start; while (tmp){ пока в списке есть элементы prev = tmp; запоминание адреса текущего элемента tmp = tmp->next; перемещение указателя наследующий элемент delete prev; удаление текущего элемента } start = NULL; список пуст return ; } #endif _LIST1_Н Файл List1.cpp использование списка" включение описания массива и файла int main() { Elem *start=NULL; сначала список пуст for ( int i=0; i<5;++i ) формирование списка из 5 элементов add_end(&start, данные списка 1, 2, 3, 4, 5 print_list(start); вывод значений данных элементов списка del_end (start); удаление последнего элемента списка del_end (start); удаление последнего элемента списка print_list(start); вывод значений данных элементов списка system( "pause" ); del_list (start); удаление списка return 0; } Формируемая в примере структура списка показана на рисунке 3.5. Рисунок 3.5 – Структура списка в окне отладки MS Visual Studio 48 Результат работы программы Задания для самостоятельной работы 3.9.1 Разработка функций обработки числовых массивов и строк Напишите функцию, которая осуществляет обработку информации по одному из условий, заданных ниже. Главная программа (main) осуществляет ввод исходных данных, передает их в функцию и выводит результаты, полученные из функции. 1) Для массива А, состоящего из N элементов a. Построить гистограмму значений массива каждый элемент массива отображается на одной строке и содержит количество ' ', равное значению элемента. b. Найти индекс первого положительного числа, оканчивающегося на 0. Если такого элемента нетто выдать соответствующее сообщение. c. Найти среднее арифметическое значение элементов массива, расположенных между наибольшими наименьшим элементами массива, включая наименьшее и наибольшее значения. d. Найти количество элементов массива, начиная со второго, значение которых больше суммы индексов элементов, стоящих передними. Назовем элемент А (i = 2, … , N-1) особым, если слева от него расположены элементы меньшие его, а справа большие. Найти количество таких элементов. f. Присвоить переменной F значение true, если элементы массива составляют строго возрастающую арифметическую прогрессию, ив противном случае g. Сформировать массив Виз таких элементов массива А, которые превышают среднее значение массива А. h. Записать в массив В положительные элементы массива А, отрицательные элементы – в массив С i. Сколько значений элементов встречаются в массиве более одного раза Какие это значения Напишите функцию, которая осуществляет рекурсивную обработку информации по одному из условий, заданных ниже j. Упорядочить массив А по возрастанию методом прямого выбора Просматривая массив с первого элемента, найти минимальный элемент и поставить его на место первого, а первый на место минимального. Просматривая массив со второго элемента, найти минимальный элемент и поставить его на место второго, а второй на место минимального, итак до предпоследнего элемента. k. Реализовать двоичный поиск заданного значениях в упорядоченном массиве А. 49 2) . Вычислить значения функции 2 / i i i a x z для всех таких значений и i a (i=1,2,…,N), что подкоренное выражение больше нуля 3) Решить уравнение i i i b x a для заданных пар значений i a и i b (i = 1, 2, … , N) 4) Даны два массива X(N) и Y(M). Сформировать массив Z(N+M) из положительных элементов массивов X и Y. Если положительных элементов меньше N+M, то оставшимся элементам массива Z присвоить значение +1 5) Даны массивы А, В состоящие из N элементов каждый. Присвоить переменной F значение true, если все элементы массива А встречаются в массиве В, ив противном случае 6) Задана целочисленная квадратная матрица A размерностью N: a. Поменять местами элементы матрицы, расположенные на одной строке и принадлежащие главной и побочной диагоналям b. Найти минимальный элемент, расположенный на главной диагонали матрицы A, а из элементов строки и столбца, на пересечении которых он находится, сформировать одномерный массив B c. Среди элементов, расположенных ниже главной диагонали матрицы A, найти те элементы, которые удовлетворяют условию K 1 A i,j K 2 (K 1 , K 2 – произвольные числа, и сформировать из них одномерный массив B d. Найти номер строки матрицы A, наиболее удаленной от первой строки, если расстояние между строками и K матрицы определяется по формуле j j K j L A A abs K L S ) ( ) , ( , , e. Найти седловую точку матрицы – такой элемент A i,j , который является наибольшим в строке i и наименьшим в столбце j. Если такого элемента нетто выдать соответствующее сообщение. f. Сформировать одномерный массив B, элементы которого B i равны true, если элементы й строки матрицы A упорядочены по возрастанию, ив противном случае g. Сформировать одномерный массив B, элементы которого B j равны 1, если хотя бы один элемент го столбца матрицы A больше суммы элементов этого столбца, ив противном случае. 7) Из массивов X(N) и Y(M) построить квадратную матрицу A размерностью K (K= M N ) таким образом, чтобы элементы массива X были расположены на главной диагонали и выше ее. 8) Задана целочисленная матрица A размерностью N×M и массив X(N). Обнулить строки матрицы с номером K, для которого X[K] 0. 9) Задана целочисленная матрица A размерностью N×M. Соседямиэлемента A i,j , матрицы A будем считать элементы A K,L , для которых i-1 K i+1 и j-1 L j+1; (K, L) (i, j). Сформироватьматрицу B путем сглаживания матрицы A – заменой каждого элемента A средним арифметическим его соседей. 10) Заданы целочисленные матрицы A, B размерностью N×M. Поменять местами столбец матрицы A, где расположен минимальный элемент, со столбцом матрицы B, где расположен максимальный элемент. 11) Заданы целочисленные квадратные матрицы A, B размерностью N. Вывести на экран значения той матрицы, которая содержит больше строк, с положительной суммой элементов. 50 12) Заданы целочисленные квадратные матрицы A, B размерностью N. Поменять местами строку матрицы A, которая содержит только положительные элементы и имеет минимальный номер в матрице A, со столбцом матрицы B, номер которого совпадает с номером найденной строки матрицы A. Если строка в матрице A не найдена, то выдать соответствующее сообщение) Введите с клавиатуры фамилию, имя и отчество. Программа должна преобразовать введенные данные и вывести их в виде инициалов и фамилии. Например, при вводе Тургенев Иван Сергеевич программа должна вывести И.С. Тургенев. В следующих заданиях предложение содержит не более 80 символов и слова разделены одним пробелом) В предложении заменить одинаковые, стоящие подряд символы одним символом, после которого в скобках указать количество символов, которые были заменены. 15) Найти в предложении слова длиной не более 6 символов, в которых количество гласных букв составляет не менее 30% 16) Найти в предложении все слова, которые являются палиндромами. 17) Заменить в предложении окончания слов «ing» на окончания «ed». 18) Найти в предложении все слова, в которых встречаются первые три буквы первого слова предложения. 19) В предложении S найти все слова, которые содержат строку S 1 (длина 2 символа) или строку длина 3 символа. 20) В предложении S 1 найти самое длинное слово, которое отсутствует в предложении S 2 21) В предложении S 1 найти все слова, которые есть в предложении S 2 3.9.2 Разработка динамических структур данных и функций их обработки Объявите заданную динамическую структуру данных и разработайте функции обработки значений данных этой структуры. Главная программа ( main ) осуществляет тестирование разработанных программных средств. 1) Для хранения целых чисел используется следующая структура данных Функции добавить значение (в зависимости от первой цифры число попадает вконец одного из списков) 51 вывести текущее состояние структуры данных (вывести все значения в виде двумерного массива) найти значение в структуре данных (функция возвращает 1, если значение найдено, ив противном случае) 2) Множество целых чисел представляется как однонаправленный линейный список. Функции найти значение в множестве (функция возвращает 1, если значение найдено, ив противном случае) добавить значение в множество (если значение уже есть в множестве, то оно в множество не добавляется. Для проверки используйте функцию найти значение в множестве) вывести текущее состояние множества (вывести все значения) определить мощность множества (подсчитать количество чисел в множестве) 3) Многочлен 0 1 1 1 1 a x a x a x a n n n n представляется как однонаправленный линейный список, элемент которого имеет следующую структуру степень Указатель наследующий элемент коэффициент Например, многочлену 3 5 2 3 x x будет соответствоватьсписок: Функции добавить элемент многочлена в список сформировать многочлен (используется функция добавить элемент многочлена в список) вывести многочлен (вывести общий вид многочлена для возведения в степень использовать символ « ^ », например, х) вычислить многочлен (функция возвращает значение многочлена при заданном х) 4) Длинное целое число представляется как однонаправленный линейный список, где каждая цифра – элемент списка. Функции сформировать длинное целое число (функция формирует список из цифр числа) вывести список (функция выводит длинное целое число) сложить два длинных целых числа (функция получает на вход два списка и возвращает третий список, каждый элемент которого содержит цифру, равную сумме, соответствующих цифр исходных списков. Фактически, результат функции – сумма двух чисел) 52 5) Циклический однонаправленный список целых чисел имеет следующуюструктуру: Начало списка. . Последний элемент указывает на начало списка Функции: добавить в список (функция добавляет элемент вконец списка) вывести список (функция выводит все значения, которые хранятся в списке) выбрать элемент из списка по номеру (функция удаляет элемент, отсчитывая его в соответствии с заданным номером от начала списка. Номер может быть больше количества элементов списка) 6) Динамический массив из N комплексных чисел. Функции сформировать массив вывести массив (функция выводит все комплексные числа) определить комплексное число как сумму всех комплексных чисел массива найти комплексное число с максимальным модулем ( модуль 2 2 im re , где re– действительная часть, im – мнимая часть комплексного числа) 7) Стек как динамический массив из N целых чисел. Функции поместить значение в стек извлечь значение из стека (функция возвращает значение из вершины стека и удаляет его из стека) стек заполнен (функция возвращает значение истина, если стек заполнен) стек пуст (функция возвращает значение истина, если в стеке нет значений) вывести стек (не изменяя содержимое стека функция, выводит все значения, которые хранятся в стеке) 8) Стек как однонаправленный линейный список целых чисел. Функции поместить значение в стек (функция добавляет значение в начало списка извлечь значение из стека (функция возвращает значение изначала списка и удаляет его из списка) стек пуст (функция возвращает значение истина, если в списке нет значений) вывести стек (не изменяя содержимого списка, функция выводит все значения, которые хранятся в списке) |