Розовая методичка. Огнева М. В., Кудрина Е. В. Структуры данных и алгоритмы программирование на языке c
 Скачать 1.93 Mb.
|
3. Удаление элемента с заданным номером из двунаправленного списка (на примере функции Remove) При удалении элемента с заданным номером из двунаправленного списка необходимо рассмотреть четыре случая. Продемонстрируем работу фрагментов функции Remove, отвечающих за обработку каждого из возможных случаев. Случай 1 (частный) — после удаления список становится пустым: if (size==0) // если после удаления элемента список окажется пустым, то { //указатели на начало и конец списка «обнулим» head= NULL ; tail= NULL ; } Случай 2 (частный) - удаляем первый элемент в списке: if (cur==head) //если удаляем первый элемент из списка, { //то указатель head перемещаем на следующий элемент и полагаем, //что у этого элемента предыдущего нет head=head->next; head->prev= NULL ; } Случай 3 (частный) - удаляем последний элемент в списке: if (cur==tail) //если удаляемый элемент последний, { //то указатель tail перемещаем на предыдущий элемент и полагаем, //что у этого элемента следующего нет tail=tail->prev; tail->next= NULL ; } Случай 4 (общий) - удаляем произвольный элемент в списке: 71 cur->prev->next=cur->next; //1 cur->next->prev=cur->prev; //2 Рис. 5.14. Общий случай удаления элемента с заданным номером из двунаправленного списка Затем независимо от того, какой именно случай нам встретился, выполняется последовательность команд: //для удаляемого элемента «обнуляем» указатели на следующий и //предыдущий элементы, чтобы корректно исключить его из списка cur->next=NULL; cur->prev=NULL; delete cur; //освобождаем память, связанную с указателем сиr 5.10. Решение практических задач с использованием двунаправленных списков 1. Дана последовательность натуральных чисел. Создать из них список, после чего удалить из списка все элементы равные х. Число х и входная последовательность целых чисел хранятся в файле input.txt, выходная последовательность целых чисел записывается в файл output.txt. #include #include using namespace std; //подключаем файл, содержащий класс-шаблон DoubleLinkedList #include "double_linked_list.cpp" //определяем глобальные потоки ifstream in( "input.txt" ); ofstream out( "output.txt" ); int main() { DoubleLinkedList < int > l; int value, x; in >> x; //пока файл не пуст, считываем из него очередной элемент и помещаем в список while (in >> value) { l.InsertRight(l.GetLength(),value); 72 } in.close(); оut << "Исходный список:" ; l.PrintLeftToRight(); //просматриваем список поэлементно for ( int i=1;i<=l.GetLength();) { if (l.Get(i)==x) //если значение элемента в i-той позиции равно х { l.Remove(i); //то удаляем данный элемент из списка } else { i++; //иначе переходим к следующему элементу списка } } out << "Измененный список:" ; l.PrintLeftToRight(); out.close(); l.DoubleLinkedList(); //вызываем деструктор return 0; } Результата работы программы: ________input.txt_______ ______________output.txt_________________ 7 Исходный список: 7 7 1 3 7 5 2 5 7 2 7 9 3 7 7 7 7 1 3 7 5 2 5 7 2 7 9 3 7 7 Измененный список: 1 3 5 2 5 2 9 3 2. Дан файл, компонентами которого являются целые числа. Создать на основе данных файла упорядоченную по убыванию структуру данных без использования какого-либо алгоритма сортировки. #include #include using namespace std; //подключаем файл, содержащий класс-шаблон DoubleLinkedList #include "double_linked_list.cpp" //определяем глобальные потоки ifstream in( "input.txt" ); ofstream out( "output.txt" ); int main() { DoubleLinkedList < int > l; int value, i, k=1; in >> value; //считываем первый элемент из файла l.InsertRight(l.GetLength(),value); //помещаем его в список //последовательно считываем элементы из файла while (in >> value) { 73 //пропускаем все элементы списка, большие value for (i=1;((i //если дошли до конца списка и все числа больше value if (i==k && l.Get(i)>value) { l.InsertRight(i,value); //то вставляем value в конец списка } else { l.InsertLeft(i,value); //иначе нашли элемент в списке, } //меньший value, и вставляем value слева от этого элемента k++; //увеличиваем количество элементов в списке } in.close(); l.PrintLeftToRigth(); out.close(); l.DoubleLinkedList(); 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 5.11. Практикум №3 I. Каждую задачу данного раздела нужно выполнить в четырех вариантах: со стеком, очередью, списком общего вида в односвязной и двусвязной реализации. При необходимости функциональные возможности классов - шаблонов List и DoubleLinkedList можно расширить. Ввод-вывод данных файловый. 1. Создать список из целых чисел. Подсчитать количество отрицательных элементов, создав из них новый список. 2. Создать список из целых чисел. Подсчитать сумму положительных элементов. Создать из положительных элементов новый список. 3. Создать список из целых чисел. Найти среднее арифметическое значение четных элементов списка. Создать из четных элементов новый список. 4. Создать список из слов. Подсчитать, сколько слов начинается на данную букву. Создать из них новый список, удалив их из исходного списка. 5. Создать список из целых чисел. После каждого элемента, равного х вставить элемент, равный у. 6. Создать список из целых чисел. Исключить из списка все элементы, равные х. 7. Создать список из целых чисел. Заменить каждую последовательность повторяющихся элементов на один элемент. 8. Создать список из целых чисел. Удвоить вхождение каждого четного элемента в нем. 74 9. Создать список из целых чисел. Найти минимальный элемент и удалить из списка все элементы, равные минимальному. 10. Создать список из целых чисел. Найти максимальный элемент и удалить из списка все элементы, равные максимальному. 11 .Создать список из целых чисел. Поменять в списке местами максимальный и минимальный элементы. 12. Создать список из слов. Подсчитать количество слов, совпадающих с последним словом. Удалить все такие слова из списка, оставив одно последнее. 13. Создать список из слов, в который все слова исходного текста входят только один раз. 14. Создать список из целых чисел. Создать новый список, записав в него вначале все четные, а затем все нечетные числа из исходного списка. 15. Создать список из целых чисел. Создать новый список, записав в него вначале все положительные числа, а затем все отрицательные числа из исходного списка. 16. Создать список из чисел. Подсчитать количество пар соседних элементов, которые совпадают между собой. Оставить по одному из таких элементов, то есть исключить все повторяющиеся, идущие подряд элементы. 17. Создать список из чисел. Создать новый список, записав в него сначала все отрицательные элементы из исходного списка, затем все положительные. 18. Создать список из целых чисел. Удалить лишние элементы в списке так, чтобы в результирующем списке каждый элемент был не меньше среднего арифметического всех элементов, следующих за ним. 19. Создать список из слов. Продублировать все однобуквенные слова в списке. 20. Создать список из слов. Перестроить элементы списка в обратном порядке. II*. Пусть дано математическое выражение, в котором используются лексемы (синтаксически неделимые единицы): 1. целые и действительные числа; 2. математические операции: +, -, *, /; 3. круглые скобки; 4. однобуквенные переменные. Для программного подсчета значения математического выражения необходимо: 1) разбить данное математическое выражение на лексемы; 2) проверить корректность математической записи; 3) записать выражение в виде польской записи; 4) по записи подсчитать значение выражения (если в выражении встречаются переменная, то ее значение запрашивается с клавиатуры только один раз). Замечание. Существуют три способа записи арифметических выражений: инфиксная (привычная для нас - знак математической операции помещается между операндами), префиксная (знак математической операции помещается перед операндами) и постфиксная (знак математической операции помещается после операндов). Постфиксную запись арифметического выражения называют обратной польской записью) Рассмотрим алгоритм формирования обратной польской записи математического выражения. Для его реализации нам потребуется два списка: 75 очередь (основной список) и стек (вспомогательный список). Напомним, что математические операции умножения и деления имеют высший приоритет по отношению к сложению и вычитанию. При формировании обратной польской записи будем использовать следующие правила: 1) если текущая лексема - число или переменная, то она помещается в очередь; 2) если текущая лексема - открывающаяся скобка, то она помещается в стек; 3) если текущая лексема - математическая операция и стек пуст или вершиной стека является открывающаяся скобка, то лексема помещается в стек; 4) если текущая лексема - математическая операция и стек не пуст и вершиной стека не является открывающаяся скобка, то: a) если вершиной стека является математическая операция одного приоритета с текущей лексемой, то эта операция извлекается из стека и помещается в очередь, а текущая лексема записывается в стек; b) если вершиной стека является математическая операциbя с приоритетом выше текущей лексемы, то все операции до открывающейся скобки извлекаются из стека и записываются в очередь, а текущая операция помещается в стек; c) если вершиной стека является математическая операция с приоритетом ниже текущей лексемы, то текущая лексема помещается в стек. 5) если текущая лексема — закрывающая скобка, то из стека извлекаются все операции до открывающейся скобки и помещаются в очередь, открывающаяся скобка также извлекается из стека; 6) если лексемы закончились, и стек оказался не пуст, то все операции извлекаются из стека и помещаются в очередь. Проиллюстрируем правила формирования обратной польской записи на примере математического выражения: 3+(4*a/7-3.5/(2.1*4))*10-a. 76 Больше лексем нет, поэтому итоговая очередь, содержащая польскую запись математического выражения, будет выглядеть следующим образом: 3 4а * 7 / 3.5 2.14 * / - 10 * + а- Чтобы подсчитать значение выражения по польской записи, необходимо последовательно применять операцию к двум аргументам, стоящим слева от операции. Для рассматриваемого выражения порядок выполнения операций будет иметь следующий вид: 1 2 3 4 5 6 7 8 ((3 ((((4 а *) 7 /) (3.5 (2.1 4 *)/)-) 10 *) +) а -) Реализуйте рассмотренный алгоритм самостоятельно. Замечание Разбиение исходного выражения на лексемы можно проводить с помощью стандартных функций для работы со строками, а проверку корректности записи математического выражения можно проводить на этапе формирования польской записи выражения. Если выражение начинается с унарного минуса, например, «-7+4/2» или «-а*b», то рекомендуется свести унарный минус к бинарному минусу добавлением незначащего нуля следующим образом: «0-7+4/2» или «0-а*b». 6. РЕАЛИЗАЦИЯ СПИСКОВ С ПОМОЩЬЮ БИБЛИОТЕКИ СТАНДАРТНЫХ ШАБЛОНОВ В пособии [9] мы рассматривали класс-контейнер vector библиотеки стандартных шаблонов (STL - Standard Template Library) языка C++, а также итераторы и алгоритмы для работы с этим классом-контейнером. Теперь мы изучим классы-контейнеры STL, предназначенные для реализации списков. 6.1. Класс-контейнер stack Стандартный класс-контейнер stack очень похож на класс, реализацию которого мы рассматривали в пункте 5.2 «Стек». Для работы с данным классом- контейнером необходимо подключить соответствующую библиотеку #include В классе имеется конструктор по умолчанию, который инициализирует пустой стек. Например: stack < int > s; Основные функции данного класса-контейнера рассмотрены в следующей таблице: Функция Описание empty() Возвращает true, если исходный стек пуст и false в противном случае size() Возвращает размер стека top() Возвращает указатель на вершину стека рор() Удаляет элемент из вершины стека push(val) Добавляет элемент в вершину стека Предположим, мы задали пустой стек stack < int > s; Тогда после выполнения оператора: 77 if (s.empty()) { cout << "Стек пуст" << endl; } else { cout << "Стек не пуст" << endl; } На экране появится сообщение: «Стек пуст» Положить в стек элементы со значениями от 0 до 10 можно следующим образом: for (int j = 0; j <= 10; j++) { s.push(j); } Вывести содержимое стека на экран можно следующим образом: while (!s.empty()) { cout << s.top() << " " ; s.pop(); } В результате на экране получим: 1 0 9 8 7 6 5 4 3 2 1 0 6.2. Класс-контейнер queue Стандартный класс-контейнер queue очень похож на класс, реализацию которого мы рассматривали в пункте 5.5. «Очередь». Для работы с данным классом-контейнером необходимо подключить соответствующую библиотеку: #include В классе существует конструктор по умолчанию, который инициализирует пустую очередь. Например, пустая очередь, которая будет состоять из целых чисел, может быть создана следующим образом: queue < int > q; Основные функции данного класса-контейнера рассмотрены в следующей таблице: Функция Описание empty() Возвращает true, если исходная очередь пуста и false в противном случае size() Возвращает размер очереди front() Возвращает указатель на первый элемент очереди back() Возвращает указатель на последний элемент очереди pop() Удаляет первый элемент очереди push() Добавляет элемент в конец очереди Положим в очередь элементы с значениями от 0 до 10, затем выведем содержимое очереди на экран: 78 queue < int > q; for (int i = 0; i <=10; i++) { q.push(i); } while (!q.empty()) { cout << q.front() << " " ; q.pop(); } В результате на экране получим: 0 1 2 3 4 5 6 7 8 9 1 0 6.3. Класс-контейнер list Стандартный класс-контейнер list очень похож на класс, реализацию которого мы рассматривали в пункте 5.9. «Двунаправленный список». Для работы с данным классом- контейнером необходимо подключить соответствующую библиотеку: #include Данный класс-контейнер содержит несколько конструкторов: list() — конструктор по умолчанию, создает пустой список; list(num,val) - создает список из num элементов, значение которых равно vat; list(anotherList) — создает список из тех же элементов, что и список anotherList. Замечание. Здесь и далее val имеет тот же тип, что элементы списка, iter - это итератор, num - целое, anotherList - объект класса-контейнера list. Таким образом, задать пустой список 1 из целых чисел можно следующим образом: list < int > l; Основные функции и алгоритмы для работы с данным классом- контейнером представлены в следующей таблице: Название Описание empty() Возвращает true, если исходный список пуст и false в противном случае size() Возвращает размер списка insert(iter, val ) val) Вставляет элемент val в список непосредственно перед элементом, на который указывает итератор iter push_front(val) Вставляет элемент val в начало списка push_back(val) Вставляет элемент val в конец списка remove(val) Удаляет из списка все элементы, имеющие значение val erase(iter) Удаляет из списка элемент, на который указывает итератор iter front() Возвращает значение первого элемента списка pop_front() Удаляет первый элемент из списка begin() Возвращает итератор на начало списка end() Возвращает итератор на конец списка reverse() Переворачивает исходный список merge(anotherList ) Объединяет исходный список со списком anotherList unique() Удаляет стоящие рядом элементы с одинаковыми значениями, оставляя только один из них Проиллюстрируем на примере работу некоторых функций и алгоритмов для класса-контейнера list. 79 Предположим, что во входном файле, связанным с потоком in, записаны числа: 1 1 1 2 2 2 2 3 4 5 А список l описан следующим образом: list < int > l; Выполним следующие операторы: if (l.empty()) { out << "Список пуст" << endl; } else { out << "Список не пуст" << endl; } out << "Размер " << l.size() << endl; В выходном файле, связанном с потоком out появится следующая запись: Список пуст Размер 0 Выполним далее чтение данных из файла в список: while (in >> value) { l.push_back(value); } in.close(); Если после этого мы опять выполним операторы: if (l.empty()) { out << "Список пуст" << endl; } else { out << "Список не пуст" << endl; } out << "Размер " << l.size() << endl; Тогда в выходной файл добавятся строки: Список не пуст Размер 10 Вывести содержимое списка в файл можно с помощью следующего цикла: list < int >:: iterator iter; //описываем итератор для класса-контейнера list //с помощью итератора проходим по списку слева направо for (iter = l.begin(); iter != l.end(); iter++) { out << *iter << " " ; //выводим значение, на которое указывает итератор } out << endl; 80 В выходном файле добавится строка: 1 1 1 2 2 2 2 3 4 5 Перевернем список и опять выведем его в выходной файл: l.reverse(); for (iter = l.begin(); iter != l.end(); iter++) { out << *iter << " " ; } out << endl; Получим: 5 4 3 2 2 2 2 1 1 1 И, наконец, удалим из списка рядом стоящие повторящиеся элементы: l.unique(); for (iter = l.begin(); iter != l.end(); iter++) { out << *iter << " " ; } out << endl; Получим: 5 4 3 2 1 |