Содержание
- 2. Список Линейный список – это контейнер, в котором элементы располагаются в памяти в произвольном порядке, а
- 3. Иллюстрация pbeg – указатель на начальный элемент, pend – указатель на конечный элемент (если он нужен).
- 4. Элемент списка Для представления элемента списка нужно создать соответствующий тип, т.е. описать структуру (класс). Пусть информационная
- 5. Стек на основе списка На основе списка можно строить другие структуры данных. Для примера модифицируем стек
- 6. Пример класса для стека Для описания элементов стека используем структуру IElem. class IStack { IElem *pbeg;
- 7. Реализация методов IStack void IStack::push(int val) { IElem *ptr = new IElem; ptr->value = val; ptr->next
- 8. Деструктор класса IStack Деструктор класса IStack должен удалять все элементы списка. Используем pbeg для указания на
- 9. Использование стеков void main() { int i; IStack a, *pb; for (i = 0; i a.push(i*2);
- 10. Информационная часть элементов Информационная часть элементов списка может быть представлена любым типом, в том числе, структурой
- 11. Элемент списка линий Элемент списка может содержать либо саму линию: struct ListElem { PLine line; ListElem
- 12. Элемент списка целых Для простоты будем рассматривать список целых с элементами struct ListElem { int value;
- 13. Класс для списка целых Начальный вид класса, в который мы будем добавлять новые методы: class List
- 14. Операции с начальным элементом void List::push_front(int val) { ListElem *pnew = new ListElem; pnew->value = val;
- 15. Очистка списка Открытый метод clear очищает список, удаляя все его элементы. Данный метод используется и в
- 16. Добавление элемента в конец списка Вариант 1: указатель на последний элемент pend не используется. void List::push_back(int
- 17. Добавление элемента в конец списка Вариант 2: используется указатель на последний элемент списка pend. void List::push_back(int
- 18. Извлечение последнего элемента списка int List::pop_back() { if (!pbeg) return -1; ListElem *pcur = pbeg, *prem
- 19. Вычисление длины списка int List::getcount() { ListElem *pcur = pbeg; int count = 0; for (;
- 20. Сцепление двух списков void List::join(List& lst) { if (!lst.pbeg) return; if (!pbeg) pbeg = lst.pbeg; else
- 21. Поиск в списке по ключу Для поиска реализуем private-метод find_elem (поиск элемента списка по ключу) и
- 22. Поиск элемента по ключу (для удаления) ListElem* List::find_elem(int keyval, ListElem*& prev) { ListElem *pcur = pbeg;
- 23. Удаление элемента с заданным ключом Public-метод удаления элемента с заданным значением ключа: bool List::remove(int keyval) {
- 24. Операции с текущим элементом списка Во многих задачах пользователю требуется выполнять операции с конкретным (текущим) элементом
- 25. Модификация класса List В данном примере приведены только новые члены класса и модифицируемый метод поиска элемента:
- 26. Модификация метода find_elem Private-метод find_elem ищет элемент списка по ключу и изменяет указатель на текущий элемент:
- 27. Методы доступа к информационной части Получение адреса информационной части начального элемента (NULL для пустого списка): int*
- 28. Методы доступа к информационной части Получение адреса информационной части текущего элемента (NULL, если текущий не установлен):
- 29. Включение нового элемента Включение нового элемента после текущего (текущая позиция не изменяется): bool List::insert(int val) {
- 30. Удаление текущего элемента bool List::remove() { if (!pcurpos) return false; ListElem *pcur = pbeg, *prev =
- 31. Пример работы с текущим элементом void main() { List a; int i, *pval; for (i =
- 32. Класс для упорядоченного списка целых class SortedList { ListElem *pbeg, *pend; ListElem *find_elem(int keyval, ListElem*& prev);
- 33. Добавление к упорядоченному списку void SortedList::add(int val) { ListElem *pnew = new ListElem; pnew->value = val;
- 34. Поиск элемента в упорядоченном списке ListElem* SortedList::find_elem(int keyval) { ListElem *pcur = pbeg; while (pcur &&
- 35. Поиск значения в упорядоченном списке int SortedList::find(int keyval) { ListElem *ptr = find_elem(keyval); if (!ptr) return
- 36. Идея слияния двух упорядоченных списков Слияние двух упорядоченных списков A (текущего) и B можно проводить, строя
- 37. Извлечение начального элемента Private-метод извлечения начального элемента и возврата его адреса: ListElem *SortedList::pop_front() { if (!pbeg)
- 38. Добавление элемента в конец списка Private-метод добавления элемента, заданного адресом, в конец списка: void SortedList::push_back(ListElem *ptr)
- 39. Слияние двух упорядоченных списков void SortedList::merge(SortedList& B) { if (!B.pbeg) return; if (!pbeg){ pbeg = B.pbeg;
- 41. Скачать презентацию