Розовая методичка. Огнева М. В., Кудрина Е. В. Структуры данных и алгоритмы программирование на языке c
 Скачать 1.93 Mb.
|
|
Замечание. Подумайте, что будет выведено в выходной поток, если во входном будет содержаться последовательность: 1 1 1 2 2 1 2 2 3 4 5 3 . 6.4. Решение практических задач с использованием библиотеки STL 1. Дана последовательность натуральных чисел. Перед каждым элементом, равным х вставить элемент, равный у. Входная последовательность целых чисел и заданные числа х и у хранятся в файле input.txt (в первой строке файла через пробел записаны х и у, во второй — последовательность чисел), выходная последовательность целых чисел записывается в файл output.txt. #include #include { stack < int > t,t1; int i,x,y; ifstream in( "input.txt" ); ofstream out( "output.txt" ); in >> x >> y; while (in >> i) //считываем данные из файла в стек { t.push(i); } in.close(); while (!t.empty()) //пока первый стек не пуст { //запоминаем значение верхнего элемента из первого стека 81 i=t.top(); t1.push(i); //помещаем это значение во второй стек if (i==x) //если это значение равно х, то { t1.push(y); //во второй стек записываем значение у } t.pop(); //удаляем верхний элемент из первого стека } //выводим содержимое второго стека в выходной файл while (!t1 .empty()) { out << t1.top() << " " ; t1.pop(); } out.close(); return 0; } Результата работы программы: _______input.txt_________ ____________output.txt_____________ 7 0 0 7 0 7 1 3 0 7 5 2 5 0 7 2 0 7 9 3 0 7 0 7 7 7 1 3 7 5 2 5 7 2 7 9 3 7 7 2. Дан файл input.txt, компонентами которого являются натуральные числа. Создать на основе файла очередь. Все элементы, равные х, заменить на у. Результат вывести в выходной файл output.txt. #include #include using namespace std; int main() { queue < int > t,t1; int i,x,y; ifstream in( "input.txt" ); ofstream out( "output.txt" ); in >> x >> y; while (in >> i) //считываем данные из файла в очередь { t.push(i); } in.close(); while (!t.empty()) //пока первая очередь не пуста { i=t.front(); //запоминаем значение первого элемента if (i!=x) //если это значение равно х { t1 push(i); //то помещаем это значение во вторую очередь 82 } else { t1 .push(y); //иначе во вторую очередь помещаем значение у } t.pop(); //удаляем первый элемент из очереди } while (!t1.empty()) //выводим вторую очередь в выходной файл { out << t1.front() << " " ; t1.рoр(); } out.close(); return 0; } Результат работы программы: _______input.txt________ _______output.txt_______ 70 0 0 1 3 0 5 2 5 0 2 0 9 3 0 0 7 7 1 3 7 5 2 5 7 2 7 9 3 7 7 3 . Дан файл, компонентами которого являются целые числа. Создать на основе данных файла упорядоченную по убыванию структуру данных без использования какого-либо алгоритма сортировки. #include #include using namespace std; int main() { list < int > l; int value; ifstream in( "input.txt" ); ofstream out( "output.txt" ); //считываем первый элемент из входного потока и помещаем //его в список in >> value; l.push_back(value); list < int >:: iterator iter; //описываем итератор unsigned int i; while (in >> value) //пока не достигнут конец входного потока { //пропускаем все элементы списка, большие value for (i=1,iter=l.begin();((i //если дошли до конца списка и все числа больше value if (i==l.size()&&*iter>value) l.push_back(value); //то вставляем value в конец списка 83 else { l.insert(iter, value); //иначе нашли элемент в списке, } //меньший value, и вставляем value слева от этого элемента } in.close(); //выводим содержимое списка в выходной файл for (iter=l.begin();iter!=l.end();iter++) { out << *iter << " " ; } out.close(); return 0; } Результата работы программы: ______input.txt_______ _______output.txt______ 7 7 1 3 7 5 2 5 7 2 7 9 3 7 7 9 7 7 7 7 7 7 7 5 5 3 3 2 2 1 6.5. Практикум №4 Замечание При решении задачи самостоятельно выберите необходимый класс- контейнер. Свой выбор обоснуйте. 1. Пусть символ # определен в текстовом редакторе как стирающий символ Backspace, т.е. строка abc#d##c в действительности является строкой ас. Дан текстовый файл, в котором встречается символ #. Преобразовать его с учетом действия этого символа. 2. В текстовом файле записана без ошибок формула вида: <формула>=<цифра>|М(<формула>, <формула>)|m(<формула>, <формула>) где | - или <цифра>=0|1|2|3|4|5|6|7|8|9 М обозначает вычисление максимума, m - минимума Вычислить значение этой формулы. Например, М(т(3,5),М(1,2))=3 3. В текстовом файле записана без ошибок формула вида: <формула>=<цифра>|р(<формула>, <формула>)|m(<формула>, <формула>) где | - или <цифра>=0|1|2|3|4|5|6|7|8|9 m(а, b) = (a-b) mod 10, р(а, b) = (a+b) mod 10. Вычислить значение этой формулы. Например, m(9, р(р(3, 5), m(3, 8))) = 6. 4. Дан текстовый файл. За один просмотр файла напечатать элементы файла в следующем порядке: сначала все символы, отличные от цифр, а затем все цифры, сохраняя исходный порядок в каждой группе символов. Дан файл, содержащий информацию о сотрудниках фирмы: фамилия, имя, отчество, пол, возраст, размер зарплаты. За один просмотр файла напечатать элементы файла в следующем порядке: сначала все данные о мужчинах, потом все данные о женщинах, сохраняя исходный порядок в каждой группе сотрудников. 84 6. Дан файл, содержащий информацию о сотрудниках фирмы: фамилия, имя, отчество, пол, возраст, размер зарплаты. За один просмотр файла напечатать элементы файла в следующем порядке: сначала все данные о сотрудниках младше 30 лет, потом данные об остальных сотрудниках, отсортировав данные о сотрудниках в каждой группе по размеру зарплаты. 7. Дан файл, содержащий информацию о студентах: фамилия, имя, отчество, номер группы, оценки по трем предметам текущей сессии. За один просмотр файла напечатать элементы файла в следующем порядке: сначала все данные о студентах, обучающихся на 4 и 5, потом данные об остальных студентах, отсортировав данные о студентах в каждой группе по алфавиту. 8*. Дан многочлен от одной переменной, например: у 4 -у+1, z 2 -8.9z+1.2z 2 или - 5 Х 3 +5- 6.7 Х 4 - Х Разработать класс Polinom, поле которого - многочлен, хранящийся в виде связного списка, со следующими функциональности: a) проверка корректности исходной записи многочлена; b) представление многочлена в виде списка с полями: коэффициент при переменной, степень; c) приведение подобных в многочлене; d) распечатка по списку многочлена в нормальном виде (подобные члены в многочлене приведены и расположены в порядке убывания степеней); e) подсчет значения многочлена для заданного значения х; f) умножение многочлена на число; g) сложение двух многочленов; h) произведение двух многочленов; i) нахождение производной n-ного порядка; j) нахождение интеграла n-ного порядка; k) нахождение рациональных корней данного многочлена. Полную структуру класса продумайте самостоятельно. Работу класса продемонстрировать на примерах. 85 ЛИТЕРАТУРА 1. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман. Структуры данных и алгоритмы. - М.: Издательский дом «Вильямс», 2000. 2. Батраева И.А., Кудрина Е.В., Огнева М.В., Родин А.М. Программируем на C++: Учеб, пособие в 3 ч. 4.2: Структуры данных и алгоритмы. — Саратов: Изд-во «Научная книга», 2004. 3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М: МЦНМО, 2001. 4. Круз Р.Л. Структуры данных и проектирование программ. — М.: Бином. Лаборатория знаний, 2008. 5. Кубенский А.А. Структуры и алгоритмы обработки данных: объектно- ориентированный подход и реализация на C++. - СПб.: БХВ-Петербург, 2004. 6. Лаптев В.В. C++ Объектно-ориентированное программирование. . - СПб: Питер, 2008. 7. Лафоре Р. Объектно-ориентированное программирование в C++. Классика Computer Science. 4-е изд. - СПб.: Питер, 2007. 8. Липпман С.Б., Лажойе Ж. Язык программирования C++. Вводный курс. 4-е изд- е. Изд. дом "Вильямс", 2007 г.. 9. Огнева М.В., Кудрина Е.В. Основы программирования на языке C++: Учеб, пособие в 2 ч. Часть 2. — Саратов: ООО Издательский центр «Наука», 2009. — 100 с. 10. Павловская Т.А. C/C++. Программирование на языке высокого уровня. - СПб: Питер, 2006. П.Шилдт Г. Самоучитель C++: Пер. с англ. — 3-е изд. — СПб.: БХВ- Петербург, 2005. 86 СОДЕРЖАНИЕ 1. Введение в объектно-ориентированное программирование.............................................................. 4 2. Стиль программирования ..................................................................................................................... 6 2.1. Правила объявления идентификаторов .................................................................................. 6 2.2. Форматирование текста ........................................................................................................... 8 2.3. Правило записи операторов ...................... ............................................................................ 8 2.4. Комментарии ............................................................................................................................ 9 2.6. Магические числа .................................................................................................................... 9 3. Классы и объекты ............................................................................................................................... 10 3.1. Основные понятия ................................................................................................................. 10 3.2. Конструкторы ......................................................................................................................... 13 3.3. Деструкторы ........................................................................................................................... 16 3.4. Статические члены класса .................................................................................................... 16 3.5. Перегрузка операций ............................................................................................................ 18 3.6. Пример простого класса ........................................................................................................ 20 3.7. Практикум №1 ..................................................................................................................... 23 4. Наследование ...................................................................................................................................... 27 4.1. Основные понятия ................................................................................................................ 27 4.2. Наследование конструкторов ................................................................................................ 28 4.3. Виртуальные функции .......................................................................................................... 30 4.4. Абстрактные классы и чисто виртуальные функции .......................................................... 32 4.5. Практикум №2 ..................................................................................................................... 35 5. Объектно-ориентированая реализация списков .............................................................................. 38 5.1. Основные понятия ................................................................................................................. 39 5.2. Стек ......................................................................................................................................... 39 5.3. Решение практических задач с использованием стеков ...................................................... 43 5.4. Применение исключений и шаблонов .................................................................................. 47 5.5. Очередь ................................................................................................................................... 49 5.6. Решение практических задач с использованием очереди ................................................... 53 5.7. Однонаправленный список общего вида ............................................................................. 55 5.8. Решение практических задач с использованием однонаправленных списков .................. 61 5.9. Двунаправленный список ...................................................................................................... 63 5.10. Решение практических задач с использованием двунаправленных списков…………... 72 5.11. Практикум №3 ................................................................................................................. 74 6. Реализация списков с помощью библиотеки стандартных шаблонов ............................................ 77 6.1. Класс-контейнер stack ........................................................................................................... 77 6.2. Класс-контейнер queue ........................................................................................................ 78 6.3. Класс-контейнер list ............................................................................................................... 79 6.4 Решение практических задач с использованием библиотеки STL ...................................... 81 6.5 Практикум №4 ...................................................................................................................... 84 Литература .............................................................................................................................................. 86 87 Эта страница не хочет удаляться, так что пускай здесь будет послесловие. Ну и замучился же я форматировать всё это дело в ворде! FineReader – ужасная гадость! Везде разные шрифты, разные размеры, наклон, весь текст во фреймах, отступы рандомные. Но всё же я смог не бросить всё, и доделать до конца. Хотя под конец уже забил на редактирование кода. Не знаю, что здесь ещё написать, поэтому, пользуясь случаем, хочу порекомендовать всем немного музыки: Исполнитель: Blue Sky Black Death Альбомы: Glaciers Melted, Noir, Violet, Euphoric tape (I, II, III). Направления: Abstract, instrumental hip-hop, chill wave Звучат просто шикарно, обожаю этих ребят! И ещё немного отличных исполнителей по жанрам: Инди-рок: Alt-J, Foster the People, Bondage Fairies, Uncle Outrage, OK GO, M83 Чилаут: Odesza, Dan Croll, iamamiwhoami, Adam Fielding, Chrome Sparks, Little People, 88 ULTRA Эмбиент, глитч: Solar fields, Маяк, ЭЛЕКТРОНИКА 302, Sk'p, Jiony, Ryoji Ikeda, Jerobeam Fenderson, Hollan Holmes, Klin, aivi & surasshu Вичуха, вапор: Summer of Haze, 猫 シ Corp., SUICIDEWΛVЕ, kislotnoe probujdenie, Clams Casino, ✝BL▲CK C∆T✝, V▲LH▲LL, Crystal Castles, George Crys.t.al, MACINTOSH PLUS, IAMTHEKIDYOUKNOWWHATIMEAN, Lay Bac, MUNGUUGNUM, † CΛIN †, t e l e p a t h テレパシー能力者, Universe Inside, CROSSPARTY Синтипоп, ретровейв: Hotline Miami OST (обе части), Betamaxx, Tyson, Trevor Something, Mitch Murder, Atrey, Com Truise, Lost Years, Miami Nights 1984, Le Cassette Драм: Pendulum, Prodigy, Нейромонах Феофан, Wolfgun, Grafix & Fred V Чиптьюн: Reboot Me, Kitsune 2 , Gamegate, KOSMOPOP2, Kubbi, Henry Homesweet, Chipzel, LHS/DFS, SoulEye, Balloonbear Спидкор, happycore: Renard, Truxton, Futret, The Quick Brown Fox, Negaren, Goreshit, Kitcaliber, SqueZ, Nero’s day at Disneyland, Ecchi-chan, Akamushi |