Основные элементы языка программирования Си алфавит, идентификаторы, ключевые слова, константы
 Скачать 0.78 Mb.
|
|
Предикаты Особая разновидность вспомогательной функции. Предикат возвращает булево значение, часто используются в качестве критерия сортировки или поиска. Предикаты бывают унарные и бинарные. Предикаты не имеют состояния, для одних и тех же значений должен быть одинаковый результат. Унарные предикаты // Функция (предикат) проверяет является ли число // простым или нет bool isPrime(int number) { … } // Поиск первого простого числа в зад. диапазоне auto pos = find_if(coll.cbegin(), coll.cend(),isPrime); // предикат для поиска значения Пример: #include #include #include #include using namespace std; // Функция (предикат) проверяет является ли число простым или нет bool isPrime(int number) { // ignore negative sign number = abs(number); // 0 and 1 are no prime numbers if (number == 0 || number == 1) { return false; } // find divisor that divides without a remainder int divisor; for (divisor = number / 2; number % divisor != 0; --divisor) { ; } // if no divisor greater than 1 is found, it is a prime number return divisor == 1; } int main() { list // insert elements from 24 to 30 for (int i = 24; i <= 30; ++i) { coll.push_back(i); } // Поиск первого простого числа auto pos = find_if(coll.cbegin(), coll.cend(), // диапазон isPrime); // предикат для поиска значения if (pos != coll.end()) { // found cout << *pos << " is first prime number found" << endl; } else { // not found cout << "no prime number found" << endl; } } 45.Предикаты в стандартной библиотеке шаблонов (STL), унарные и бинарные предикаты, пример использования бинарного предиката для сортировки элементов в контейнере на примере функции sort. Может использоваться для сортировки, имеет два параметра – элемента контейнера, возвращает true или false при сравнении двух элементов. Пример: #include #include #include #include using namespace std; struct Student // Студент { std::string Name; // ФИО std::vector }; bool comp1(Student &st1, Student &st2) // Предикат для сортировки по ФИО { return st1.Name < st2.Name; } void SortByName(std::vector { sort(studs.begin(), studs.end(), comp1); } bool isTwo(const Student &st) // Предикат для определения студента двоичника { for (auto pos: st.Ratings) if (pos == 2) return true; return false; } size_t CountTwoness(const std::vector { vector int n = 0; while ((pos = find_if(pos, st.end(), isTwo)) != st.end()) { // В цикле ищем всех двоечников st_2.push_back(*pos); // Добавляем двоечников в новый список ++pos; n++; } return n; } int main() { vector Student st2 = {"Petrov P.I.", {5, 5, 5, 5}}; studs.push_back(st2); Student st3 = {"Sidorov S.S.", {5, 3, 2, 3}}; studs.push_back(st3); Student st1 = {"Ivanov I.I.", {3, 3, 2, 4}}; studs.push_back(st1); Student st4 = {"Abramov A.S.", {5, 5, 5, 5}}; studs.push_back(st4); for (auto pos: studs) // Печать списка { cout << pos.Name << ' '; for (auto pos2: pos.Ratings) cout << pos2 << ' '; cout << endl; } SortByName(studs); cout << "After sorting:" << endl; for (auto pos: studs) // Печать списка после сортировки { cout << pos.Name << ' '; for (auto pos2: pos.Ratings) cout << pos2 << ' '; cout << endl; } vector size_t N2; N2 = CountTwoness(studs, studs_2); // Получаем спискок двоечников и их число cout << "N2=" << N2 << endl; for (auto pos: studs_2) // Печать списка двоечников { cout << pos.Name << ' '; for (auto pos2: pos.Ratings) cout << pos2 << ' '; cout << endl; } } 46.Понятие о динамических структурах данных. Линейные односвязные списки, основные функции для работы с ними. Примеры функций: добавление элемента в список и извлечение элемента из списка.(без линейного односвязного) Статические структуры данных СД (обычные переменные, массивы, структуры, объединения и т.п.) имеют раз навсегда заданные для них объем памяти и соответственно диапазон возможных значений. Множество задач требуют хранения данных с более сложной структурой, в процессы вычисления должны меняться не только значения переменных, но и их структура и соответственно размер выделяемой памяти. Такие данные называются данными с динамической структурой. Иногда их называют данными с рекурсивной структурой. Пример генеалогическое дерево определяется как имя человека + 2 дерева его родителей, такое определение ведет к бесконечной структуре, реальные деревья всегда конечны. Особенность рекурсивных структур – способность изменять размер. Для этого используется метод динамического распределения памяти, т.е. память под отдельные компоненты выделяется в тот момент, когда они начинают существовать. Это можно реализовать с помощью указателей. Структура, описывающая элемент линейного односвязного список: struct Inform { ... }; // Информационное поле (любая структура) struct ListItem // Элементсписка { Inform Inf; ListItem *pNext; // Указатель на следующий элемент }; Для работы с ЛОС необходимо знать указатель на первый элемент списка (признак последнего элемента pNext==0), иногда удобно хранить указатель на последний элемент для ускорения доступа к последнему элементу, например, чтобы добавить элемент в конец списка. Часто эти указатели хранят внутри отдельной структуры. struct List // Для описания собственно списка { ListItem *pFirst; // Указатель на первый элемент ….. // Иногда хранят другие поля: указатель на последний элемент, число элементов и др. }; Основные функции для работы со списком • Добавить элемент в начало списка. • Добавить элемент в конец списка. • Добавить элемент после заданного (перед заданным). • Извлечь элемент из начала списка. • Извлечь произвольный элемент из списка. • Найти элемент с заданным ключом. Добавление узла в ОЛС: struct list * addelem(list *lst, int number) { struct list *temp, *p; temp = (struct list*)malloc(sizeof(list)); p = lst->ptr; // сохранение указателя на следующий узел lst->ptr = temp; // предыдущий узел указывает на создаваемый temp->field = number; // сохранение поля данных добавляемого узла temp->ptr = p; // созданный узел указывает на следующий элемент return(temp); } УдалениеузлаОЦС struct list * deletelem(list *lst) { struct list *temp; temp = lst; while (temp->ptr != lst) // просматриваем список начиная с корня { // пока не найдем узел, предшествующий lst temp = temp->ptr; } temp->ptr = lst->ptr; // переставляем указатель free(lst); // освобождаем память удаляемого узла return(temp); } 47.Линейные двухсвязные списки, основные функции для работы с ними. Примеры функций: добавление элемента в список и извлечение элемента из списка Структура для задания элемента двухсвязного списка: struct ListItem { Inform Inf; List2 * pNext; List2 * pPred; }; Функции для работы с двухсвязным списком: Примеры: • Добавить элемент в начало списка. • Добавить элемент в конец списка. • Добавить элемент после заданного (перед заданным). • Извлечь элемент из начала списка. • Извлечь произвольный элемент из списка. • Найти элемент с заданным ключом. 48.Кольцевые односвязные списки. Основные функции для работы с кольцевыми односвязными списками. Примеры функций: добавление элемента в список и извлечение элемента из списка. #include #include #include using namespace std; struct BUS { string name; double l, h; int v, max_pas; }; void print(const BUS &bus) { cout << bus.name << ' ' << bus.l << ' ' << bus.h << ' ' << bus.v << ' ' << bus.max_pas << endl; } struct ListItem { BUS bus; ListItem *pNext, *pPred; }; struct List { ListItem *pFirst = nullptr, *pEnd = nullptr; }; void push_back(List &list, BUS &bus) { ListItem *p = new ListItem; p->bus = bus; if (list.pFirst == nullptr) { p->pNext = p->pPred = nullptr; list.pFirst = list.pEnd = p; } else { p->pNext = nullptr; p->pPred = list.pEnd; list.pEnd->pNext = p; list.pEnd = p; } } void print(const List &list) { for (auto p = list.pFirst; p != nullptr; p = p->pNext) print(p->bus); } void CreateListFromFile(istream &in, List &list) { BUS bus; int n; in >> n; for (int i = 0; i < n; i++) { in.ignore(); in >> bus.name; in >> bus.l >> bus.h >> bus.v >> bus.max_pas; push_back(list, bus); } } int main() { ifstream fin("MyData.txt"); if (!fin) { cout << "Error! File not found!!" << endl; return 1; } List list1; CreateListFromFile(fin, list1); print(list1); return 0; } 49.Кольцевые двухсвязные списки. Основные функции для работы с кольцевыми двухсвязными списками. Примеры функций: добавление элемента в список и извлечение элемента из списка. Примеры функций для работы с двухсвязным кольцевым списком #include #include using namespace std; struct Man // Информационное поле - человек { int N; // Его возраст string fio; // ФИО человека }; struct ListItem { Man man; // Инф поле ListItem *pNext, *pPred; }; //ListItem *pF1=0; struct List { ListItem *pFirst; }; void addInList(List &list, ListItem *p, bool flag = true) // flag = true Добавляем в начало списка { if (list.pFirst == 0) { list.pFirst = p->pNext = p->pPred = p; } else { p->pNext = list.pFirst; p->pPred = list.pFirst->pPred; list.pFirst->pPred->pNext = p; list.pFirst->pPred = p; if (flag) list.pFirst = p; // Элемент стал первый } } void addAfterZad(ListItem *pZad, ListItem *p) { p->pNext = pZad->pNext; p->pPred = pZad; pZad->pNext->pPred = p; pZad->pNext = p; } ListItem *myremove(List &list, ListItem *p) { if (list.pFirst == 0 || p == 0) return 0; if (list.pFirst->pNext == list.pFirst) // Список состоит из 1 элемента { if (p == list.pFirst) { list.pFirst = 0; return p; } else return 0; // Ошибка } if (p == list.pFirst) // Извлекаемый элемент первый list.pFirst = list.pFirst->pNext; // Второй будет первым p->pPred->pNext = p->pNext; p->pNext->pPred = p->pPred; return p; } void print(List list) { ListItem *p = list.pFirst; do { cout << endl << p->man.fio << ' ' << p->man.N; p = p->pNext; } while (p != list.pFirst); } |