Главная страница
Навигация по странице:

  • 6.5. Практикум №4 Замечание

  • Практикум №1 ..................................................................................................................... 23

  • Практикум №2 ..................................................................................................................... 35

  • Практикум №3 ................................................................................................................. 74

  • Практикум №4 ...................................................................................................................... 84

  • Розовая методичка. Огнева М. В., Кудрина Е. В. Структуры данных и алгоритмы программирование на языке c


    Скачать 1.93 Mb.
    НазваниеОгнева М. В., Кудрина Е. В. Структуры данных и алгоритмы программирование на языке c
    Дата14.05.2019
    Размер1.93 Mb.
    Формат файлаpdf
    Имя файлаРозовая методичка.pdf
    ТипДокументы
    #77078
    страница8 из 8
    1   2   3   4   5   6   7   8
    Замечание. Подумайте, что будет выведено в выходной поток, если во входном будет содержаться последовательность: 1 1 1 2 2 1 2 2 3 4 5 3 .
    6.4.
    Решение практических задач с использованием библиотеки STL
    1. Дана последовательность натуральных чисел. Перед каждым элементом, равным х вставить элемент, равный у. Входная последовательность целых чисел и заданные числа х и у хранятся в файле input.txt (в первой строке файла через пробел записаны х и у, во второй — последовательность чисел), выходная последовательность целых чисел записывается в файл output.txt.
    #include

    #include
    using namespace std; int main()
    { 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();((ivalue));i++,iter++);
    //если дошли до конца списка и все числа больше 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
    1   2   3   4   5   6   7   8


    написать администратору сайта