🗊Презентация Основы программирования. Линейные списки

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Основы программирования. Линейные списки, слайд №1Основы программирования. Линейные списки, слайд №2Основы программирования. Линейные списки, слайд №3Основы программирования. Линейные списки, слайд №4Основы программирования. Линейные списки, слайд №5Основы программирования. Линейные списки, слайд №6Основы программирования. Линейные списки, слайд №7Основы программирования. Линейные списки, слайд №8Основы программирования. Линейные списки, слайд №9Основы программирования. Линейные списки, слайд №10Основы программирования. Линейные списки, слайд №11Основы программирования. Линейные списки, слайд №12Основы программирования. Линейные списки, слайд №13Основы программирования. Линейные списки, слайд №14Основы программирования. Линейные списки, слайд №15Основы программирования. Линейные списки, слайд №16Основы программирования. Линейные списки, слайд №17Основы программирования. Линейные списки, слайд №18Основы программирования. Линейные списки, слайд №19Основы программирования. Линейные списки, слайд №20Основы программирования. Линейные списки, слайд №21Основы программирования. Линейные списки, слайд №22Основы программирования. Линейные списки, слайд №23Основы программирования. Линейные списки, слайд №24Основы программирования. Линейные списки, слайд №25Основы программирования. Линейные списки, слайд №26Основы программирования. Линейные списки, слайд №27Основы программирования. Линейные списки, слайд №28Основы программирования. Линейные списки, слайд №29Основы программирования. Линейные списки, слайд №30Основы программирования. Линейные списки, слайд №31Основы программирования. Линейные списки, слайд №32Основы программирования. Линейные списки, слайд №33Основы программирования. Линейные списки, слайд №34Основы программирования. Линейные списки, слайд №35Основы программирования. Линейные списки, слайд №36Основы программирования. Линейные списки, слайд №37Основы программирования. Линейные списки, слайд №38Основы программирования. Линейные списки, слайд №39Основы программирования. Линейные списки, слайд №40
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Основы программирования. Линейные списки. Доклад-сообщение содержит 40 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Основы программирования Линейные списки
Описание слайда:
Основы программирования Линейные списки

Слайд 2


Список Линейный список – это контейнер, в котором элементы располагаются в памяти в произвольном порядке, а связь между ними обеспечивается с помощью указателей (ссылок). Элемент однонаправленного списка состоит из двух частей – информационной (собственно данных) и указателя (ссылки) на следующий элемент списка. Как правило, память для каждого элемента выделяется динамически. Для доступа к начальному элементу списка используется отдельный указатель (ссылка). Последний элемент списка не ссылается ни на что, т.е. имеет нулевой указатель (пустую ссылку). Во многих случаях выгодно хранить отдельный указатель на последний элемент.
Описание слайда:
Список Линейный список – это контейнер, в котором элементы располагаются в памяти в произвольном порядке, а связь между ними обеспечивается с помощью указателей (ссылок). Элемент однонаправленного списка состоит из двух частей – информационной (собственно данных) и указателя (ссылки) на следующий элемент списка. Как правило, память для каждого элемента выделяется динамически. Для доступа к начальному элементу списка используется отдельный указатель (ссылка). Последний элемент списка не ссылается ни на что, т.е. имеет нулевой указатель (пустую ссылку). Во многих случаях выгодно хранить отдельный указатель на последний элемент.

Слайд 3


Иллюстрация pbeg – указатель на начальный элемент, pend – указатель на конечный элемент (если он нужен). Доступ к элементам осуществляется последовательно, по указателям (ссылкам). Если необходимо обеспечить переход не только к последующим, но и к предыдущим элементам, в элементы нужно включить еще один указатель (ссылку) – на предыдущий элемент (нуль для начального элемента списка). Соответствующий список будет двунаправленным.
Описание слайда:
Иллюстрация pbeg – указатель на начальный элемент, pend – указатель на конечный элемент (если он нужен). Доступ к элементам осуществляется последовательно, по указателям (ссылкам). Если необходимо обеспечить переход не только к последующим, но и к предыдущим элементам, в элементы нужно включить еще один указатель (ссылку) – на предыдущий элемент (нуль для начального элемента списка). Соответствующий список будет двунаправленным.

Слайд 4


Элемент списка Для представления элемента списка нужно создать соответствующий тип, т.е. описать структуру (класс). Пусть информационная часть элемента – это просто целое число. Тогда новый тип будет выглядеть следующим образом: struct IElem { int value; IElem *next; } По умолчанию в структуре все поля являются открытыми (public), поэтому никаких дополнительных методов доступа к ним не надо.
Описание слайда:
Элемент списка Для представления элемента списка нужно создать соответствующий тип, т.е. описать структуру (класс). Пусть информационная часть элемента – это просто целое число. Тогда новый тип будет выглядеть следующим образом: struct IElem { int value; IElem *next; } По умолчанию в структуре все поля являются открытыми (public), поэтому никаких дополнительных методов доступа к ним не надо.

Слайд 5


Стек на основе списка На основе списка можно строить другие структуры данных. Для примера модифицируем стек из раздела «Структуры и классы», сохраняя весь открытый интерфейс. Учитывая, что добавление и извлечение элементов стека производится в его вершине, будем считать вершиной начальный элемент списка (т.е. начальный указатель списка всегда показывает на вершину стека, а конечный указатель вообще не нужен). Элементы списка выделяются динамически, поэтому для стека не нужен массив, и количество элементов стека не ограничено.
Описание слайда:
Стек на основе списка На основе списка можно строить другие структуры данных. Для примера модифицируем стек из раздела «Структуры и классы», сохраняя весь открытый интерфейс. Учитывая, что добавление и извлечение элементов стека производится в его вершине, будем считать вершиной начальный элемент списка (т.е. начальный указатель списка всегда показывает на вершину стека, а конечный указатель вообще не нужен). Элементы списка выделяются динамически, поэтому для стека не нужен массив, и количество элементов стека не ограничено.

Слайд 6


Пример класса для стека Для описания элементов стека используем структуру IElem. class IStack { IElem *pbeg; public: IStack() { pbeg = NULL; } ~IStack(); void push(int val); int pop(); };
Описание слайда:
Пример класса для стека Для описания элементов стека используем структуру IElem. class IStack { IElem *pbeg; public: IStack() { pbeg = NULL; } ~IStack(); void push(int val); int pop(); };

Слайд 7


Реализация методов IStack void IStack::push(int val) { IElem *ptr = new IElem; ptr->value = val; ptr->next = pbeg; pbeg = ptr; } int IStack::pop() { if (!pbeg) return -1; IElem *ptr = pbeg; int val = pbeg->value; pbeg = pbeg->next; delete ptr; return val; }
Описание слайда:
Реализация методов IStack void IStack::push(int val) { IElem *ptr = new IElem; ptr->value = val; ptr->next = pbeg; pbeg = ptr; } int IStack::pop() { if (!pbeg) return -1; IElem *ptr = pbeg; int val = pbeg->value; pbeg = pbeg->next; delete ptr; return val; }

Слайд 8


Деструктор класса IStack Деструктор класса IStack должен удалять все элементы списка. Используем pbeg для указания на текущий удаляемый элемент списка. void IStack::~IStack() { IElem *ptr; while (pbeg != NULL) { ptr = pbeg; pbeg = pbeg->next; delete ptr; } }
Описание слайда:
Деструктор класса IStack Деструктор класса IStack должен удалять все элементы списка. Используем pbeg для указания на текущий удаляемый элемент списка. void IStack::~IStack() { IElem *ptr; while (pbeg != NULL) { ptr = pbeg; pbeg = pbeg->next; delete ptr; } }

Слайд 9


Использование стеков void main() { int i; IStack a, *pb; for (i = 0; i < 10; i++) a.push(i*2); pb = new IStack; for (i = 0; i < 20; i++) pb->push(i+10); for (i = 0; i < 22; i++) cout << pb->pop() << endl; delete pb; }
Описание слайда:
Использование стеков void main() { int i; IStack a, *pb; for (i = 0; i < 10; i++) a.push(i*2); pb = new IStack; for (i = 0; i < 20; i++) pb->push(i+10); for (i = 0; i < 22; i++) cout << pb->pop() << endl; delete pb; }

Слайд 10


Информационная часть элементов Информационная часть элементов списка может быть представлена любым типом, в том числе, структурой или классом. Например, для списка линий это может быть: class PLine { double *x, *y; int key; int length; … public: void setlength(int len); void free(); void setp(int n,double vx,double vy); … };
Описание слайда:
Информационная часть элементов Информационная часть элементов списка может быть представлена любым типом, в том числе, структурой или классом. Например, для списка линий это может быть: class PLine { double *x, *y; int key; int length; … public: void setlength(int len); void free(); void setp(int n,double vx,double vy); … };

Слайд 11


Элемент списка линий Элемент списка может содержать либо саму линию: struct ListElem { PLine line; ListElem *next; }; либо указатель на динамически выделяемую линию: struct ListElem { PLine *line; ListElem *next; };
Описание слайда:
Элемент списка линий Элемент списка может содержать либо саму линию: struct ListElem { PLine line; ListElem *next; }; либо указатель на динамически выделяемую линию: struct ListElem { PLine *line; ListElem *next; };

Слайд 12


Элемент списка целых Для простоты будем рассматривать список целых с элементами struct ListElem { int value; ListElem *next; }; где значение value будет также служить ключом при поиске в списке.
Описание слайда:
Элемент списка целых Для простоты будем рассматривать список целых с элементами struct ListElem { int value; ListElem *next; }; где значение value будет также служить ключом при поиске в списке.

Слайд 13


Класс для списка целых Начальный вид класса, в который мы будем добавлять новые методы: class List { ListElem *pbeg, *pend; public: List() { pend = pbeg = NULL; } ~List() { clear(); } void push_front(int val); int pop_front(); void clear(); … };
Описание слайда:
Класс для списка целых Начальный вид класса, в который мы будем добавлять новые методы: class List { ListElem *pbeg, *pend; public: List() { pend = pbeg = NULL; } ~List() { clear(); } void push_front(int val); int pop_front(); void clear(); … };

Слайд 14


Операции с начальным элементом void List::push_front(int val) { ListElem *pnew = new ListElem; pnew->value = val; pnew->next = pbeg; pbeg = pnew; if (!pend) pend = pnew; } int List::pop_front() { if (!pbeg) return -1; ListElem *ptr = pbeg; int val = pbeg->value; pbeg = pbeg->next; if (!pbeg) pend = NULL; delete ptr; return val; }
Описание слайда:
Операции с начальным элементом void List::push_front(int val) { ListElem *pnew = new ListElem; pnew->value = val; pnew->next = pbeg; pbeg = pnew; if (!pend) pend = pnew; } int List::pop_front() { if (!pbeg) return -1; ListElem *ptr = pbeg; int val = pbeg->value; pbeg = pbeg->next; if (!pbeg) pend = NULL; delete ptr; return val; }

Слайд 15


Очистка списка Открытый метод clear очищает список, удаляя все его элементы. Данный метод используется и в деструкторе. void List::clear() { ListElem *ptr; while (pbeg != NULL) { ptr = pbeg; pbeg = pbeg->next; delete ptr; } }
Описание слайда:
Очистка списка Открытый метод clear очищает список, удаляя все его элементы. Данный метод используется и в деструкторе. void List::clear() { ListElem *ptr; while (pbeg != NULL) { ptr = pbeg; pbeg = pbeg->next; delete ptr; } }

Слайд 16


Добавление элемента в конец списка Вариант 1: указатель на последний элемент pend не используется. void List::push_back(int val) { ListElem *pcur, *pnew = new ListElem; pnew->value = val; pnew->next = NULL; if (!pbeg) pbeg = pnew; else { for (pcur = pbeg; pcur->next; ) pcur = pcur->next; pcur->next = pnew; } }
Описание слайда:
Добавление элемента в конец списка Вариант 1: указатель на последний элемент pend не используется. void List::push_back(int val) { ListElem *pcur, *pnew = new ListElem; pnew->value = val; pnew->next = NULL; if (!pbeg) pbeg = pnew; else { for (pcur = pbeg; pcur->next; ) pcur = pcur->next; pcur->next = pnew; } }

Слайд 17


Добавление элемента в конец списка Вариант 2: используется указатель на последний элемент списка pend. void List::push_back(int val) { ListElem *pnew = new ListElem; pnew->value = val; pnew->next = NULL; if (!pbeg) pbeg = pend = pnew; else { pend->next = pnew; pend = pnew; } }
Описание слайда:
Добавление элемента в конец списка Вариант 2: используется указатель на последний элемент списка pend. void List::push_back(int val) { ListElem *pnew = new ListElem; pnew->value = val; pnew->next = NULL; if (!pbeg) pbeg = pend = pnew; else { pend->next = pnew; pend = pnew; } }

Слайд 18


Извлечение последнего элемента списка int List::pop_back() { if (!pbeg) return -1; ListElem *pcur = pbeg, *prem = pend; int val = pend->value; if (pbeg == pend) pbeg = pend = NULL; else { while (pcur->next != pend) pcur = pcur->next; pcur->next = NULL; pend = pcur; } delete prem; return val; }
Описание слайда:
Извлечение последнего элемента списка int List::pop_back() { if (!pbeg) return -1; ListElem *pcur = pbeg, *prem = pend; int val = pend->value; if (pbeg == pend) pbeg = pend = NULL; else { while (pcur->next != pend) pcur = pcur->next; pcur->next = NULL; pend = pcur; } delete prem; return val; }

Слайд 19


Вычисление длины списка int List::getcount() { ListElem *pcur = pbeg; int count = 0; for (; pcur; pcur = pcur->next) count++; return count; }
Описание слайда:
Вычисление длины списка int List::getcount() { ListElem *pcur = pbeg; int count = 0; for (; pcur; pcur = pcur->next) count++; return count; }

Слайд 20


Сцепление двух списков void List::join(List& lst) { if (!lst.pbeg) return; if (!pbeg) pbeg = lst.pbeg; else pend->next = lst.pbeg; pend = lst.pend; lst.pbeg = lst.pend = NULL; } Вызов: List a, b; int i; for (i = 0; i < 10; i++) a.push_back(i*2); for (i = 0; i < 20; i++) b.push_back(i+1); a.join(b);
Описание слайда:
Сцепление двух списков void List::join(List& lst) { if (!lst.pbeg) return; if (!pbeg) pbeg = lst.pbeg; else pend->next = lst.pbeg; pend = lst.pend; lst.pbeg = lst.pend = NULL; } Вызов: List a, b; int i; for (i = 0; i < 10; i++) a.push_back(i*2); for (i = 0; i < 20; i++) b.push_back(i+1); a.join(b);

Слайд 21


Поиск в списке по ключу Для поиска реализуем private-метод find_elem (поиск элемента списка по ключу) и public-метод find (поиск значения по ключу): ListElem* List::find_elem(int keyval) { ListElem *pcur = pbeg; for (; pcur; pcur = pcur->next) if (pcur->value == keyval) break; return pcur; } int List::find(int keyval) { ListElem *ptr = find_elem(keyval); if (!ptr) return -1; return ptr->value; }
Описание слайда:
Поиск в списке по ключу Для поиска реализуем private-метод find_elem (поиск элемента списка по ключу) и public-метод find (поиск значения по ключу): ListElem* List::find_elem(int keyval) { ListElem *pcur = pbeg; for (; pcur; pcur = pcur->next) if (pcur->value == keyval) break; return pcur; } int List::find(int keyval) { ListElem *ptr = find_elem(keyval); if (!ptr) return -1; return ptr->value; }

Слайд 22


Поиск элемента по ключу (для удаления) ListElem* List::find_elem(int keyval, ListElem*& prev) { ListElem *pcur = pbeg; prev = NULL; while (pcur && pcur->value != keyval) { prev = pcur; pcur = pcur->next; } return pcur; }
Описание слайда:
Поиск элемента по ключу (для удаления) ListElem* List::find_elem(int keyval, ListElem*& prev) { ListElem *pcur = pbeg; prev = NULL; while (pcur && pcur->value != keyval) { prev = pcur; pcur = pcur->next; } return pcur; }

Слайд 23


Удаление элемента с заданным ключом Public-метод удаления элемента с заданным значением ключа: bool List::remove(int keyval) { ListElem *prem, *prev; prem = find_elem(keyval, prev); if (!prem) return false; if (!prev) pbeg = pbeg->next; else prev->next = prem->next; if (prem == pend) pend = prev; delete prem; return true; }
Описание слайда:
Удаление элемента с заданным ключом Public-метод удаления элемента с заданным значением ключа: bool List::remove(int keyval) { ListElem *prem, *prev; prem = find_elem(keyval, prev); if (!prem) return false; if (!prev) pbeg = pbeg->next; else prev->next = prem->next; if (prem == pend) pend = prev; delete prem; return true; }

Слайд 24


Операции с текущим элементом списка Во многих задачах пользователю требуется выполнять операции с конкретным (текущим) элементом списка, например: модифицировать информационную часть текущего элемента вставить новый элемент после текущего удалить текущий элемент последовательно обработать все элементы от начала до конца списка. При этом пользователь должен работать только с информационной частью элементов, а формат списка и его элементов должны быть скрытыми. Чтобы реализовать это, можно добавить в класс еще одно private-поле (указатель на текущий элемент), модифицировать старые и включить новые методы.
Описание слайда:
Операции с текущим элементом списка Во многих задачах пользователю требуется выполнять операции с конкретным (текущим) элементом списка, например: модифицировать информационную часть текущего элемента вставить новый элемент после текущего удалить текущий элемент последовательно обработать все элементы от начала до конца списка. При этом пользователь должен работать только с информационной частью элементов, а формат списка и его элементов должны быть скрытыми. Чтобы реализовать это, можно добавить в класс еще одно private-поле (указатель на текущий элемент), модифицировать старые и включить новые методы.

Слайд 25


Модификация класса List В данном примере приведены только новые члены класса и модифицируемый метод поиска элемента: class List { ListElem *pbeg, *pend, *pcurpos; ListElem *find_elem(int keyval); public: List() { pend = pbeg = pcurpos = NULL; } int *get_first(); int *get_last(); int *get_next(); int *get_current(); bool insert(int val); bool remove(); };
Описание слайда:
Модификация класса List В данном примере приведены только новые члены класса и модифицируемый метод поиска элемента: class List { ListElem *pbeg, *pend, *pcurpos; ListElem *find_elem(int keyval); public: List() { pend = pbeg = pcurpos = NULL; } int *get_first(); int *get_last(); int *get_next(); int *get_current(); bool insert(int val); bool remove(); };

Слайд 26


Модификация метода find_elem Private-метод find_elem ищет элемент списка по ключу и изменяет указатель на текущий элемент: ListElem* List::find_elem(int keyval) { ListElem *pcur = pbeg; for (; pcur; pcur = pcur->next) if (pcur->value == keyval) break; pcurpos = pcur; return pcur; }
Описание слайда:
Модификация метода find_elem Private-метод find_elem ищет элемент списка по ключу и изменяет указатель на текущий элемент: ListElem* List::find_elem(int keyval) { ListElem *pcur = pbeg; for (; pcur; pcur = pcur->next) if (pcur->value == keyval) break; pcurpos = pcur; return pcur; }

Слайд 27


Методы доступа к информационной части Получение адреса информационной части начального элемента (NULL для пустого списка): int* List::get_first() { pcurpos = pbeg; if (!pcurpos) return NULL; return &(pcurpos->value); } Получение адреса информационной части последнего элемента (NULL для пустого списка): int* List::get_last() { pcurpos = pend; if (!pcurpos) return NULL; return &(pcurpos->value); }
Описание слайда:
Методы доступа к информационной части Получение адреса информационной части начального элемента (NULL для пустого списка): int* List::get_first() { pcurpos = pbeg; if (!pcurpos) return NULL; return &(pcurpos->value); } Получение адреса информационной части последнего элемента (NULL для пустого списка): int* List::get_last() { pcurpos = pend; if (!pcurpos) return NULL; return &(pcurpos->value); }

Слайд 28


Методы доступа к информационной части Получение адреса информационной части текущего элемента (NULL, если текущий не установлен): int* List::get_current() { if (!pcurpos) return NULL; return &(pcurpos->value); } Получение адреса информационной части элемента, следующего за текущим (или NULL): int* List::get_next() { if (!pcurpos) return NULL; pcurpos = pcurpos->next; if (!pcurpos) return NULL; return &(pcurpos->value); }
Описание слайда:
Методы доступа к информационной части Получение адреса информационной части текущего элемента (NULL, если текущий не установлен): int* List::get_current() { if (!pcurpos) return NULL; return &(pcurpos->value); } Получение адреса информационной части элемента, следующего за текущим (или NULL): int* List::get_next() { if (!pcurpos) return NULL; pcurpos = pcurpos->next; if (!pcurpos) return NULL; return &(pcurpos->value); }

Слайд 29


Включение нового элемента Включение нового элемента после текущего (текущая позиция не изменяется): bool List::insert(int val) { if (!pcurpos) return false; ListElem *pnew = new ListElem; pnew->value = val; pnew->next = pcurpos->next; pcurpos->next = pnew; return true; }
Описание слайда:
Включение нового элемента Включение нового элемента после текущего (текущая позиция не изменяется): bool List::insert(int val) { if (!pcurpos) return false; ListElem *pnew = new ListElem; pnew->value = val; pnew->next = pcurpos->next; pcurpos->next = pnew; return true; }

Слайд 30


Удаление текущего элемента bool List::remove() { if (!pcurpos) return false; ListElem *pcur = pbeg, *prev = NULL; while (pcur != pcurpos) { prev = pcur; pcur = pcur->next; } if (!prev) pbeg = pcur->next; else prev->next = pcur->next; pcurpos = pcur->next; if (!pbeg) pend = pcurpos = NULL; else if (pend == pcur) pend = prev; delete pcur; return true; }
Описание слайда:
Удаление текущего элемента bool List::remove() { if (!pcurpos) return false; ListElem *pcur = pbeg, *prev = NULL; while (pcur != pcurpos) { prev = pcur; pcur = pcur->next; } if (!prev) pbeg = pcur->next; else prev->next = pcur->next; pcurpos = pcur->next; if (!pbeg) pend = pcurpos = NULL; else if (pend == pcur) pend = prev; delete pcur; return true; }

Слайд 31


Пример работы с текущим элементом void main() { List a; int i, *pval; for (i = 0; i < 50; i++) a.push_back(rand()%100); for (pval = a.get_first(); pval;) { if (pval->value%2) (pval->value)--; pval = a.get_next(); } a.get_first(); if (!a.get_next()) return; if (get_current()->value < 50) { a.insert(77); a.remove(); } }
Описание слайда:
Пример работы с текущим элементом void main() { List a; int i, *pval; for (i = 0; i < 50; i++) a.push_back(rand()%100); for (pval = a.get_first(); pval;) { if (pval->value%2) (pval->value)--; pval = a.get_next(); } a.get_first(); if (!a.get_next()) return; if (get_current()->value < 50) { a.insert(77); a.remove(); } }

Слайд 32


Класс для упорядоченного списка целых class SortedList { ListElem *pbeg, *pend; ListElem *find_elem(int keyval, ListElem*& prev); ListElem *find_elem(int keyval); ListElem *pop_front(); void push_back(ListElem *ptr); public: SortedList() { pend = pbeg = NULL; } ~SortedList() { clear(); } void clear(); bool remove(int keyval); void add(int val); int find(int keyval); void merge(SortedList &lst); };
Описание слайда:
Класс для упорядоченного списка целых class SortedList { ListElem *pbeg, *pend; ListElem *find_elem(int keyval, ListElem*& prev); ListElem *find_elem(int keyval); ListElem *pop_front(); void push_back(ListElem *ptr); public: SortedList() { pend = pbeg = NULL; } ~SortedList() { clear(); } void clear(); bool remove(int keyval); void add(int val); int find(int keyval); void merge(SortedList &lst); };

Слайд 33


Добавление к упорядоченному списку void SortedList::add(int val) { ListElem *pnew = new ListElem; pnew->value = val; pnew->next = NULL; if (!pbeg) pbeg = pend = pnew; else if (pbeg->value >= val) { pnew->next = pbeg; pbeg = pnew; } else if (pend->value < val) { pend->next = pnew; pend = pnew; } else { ListElem *prev=pbeg, *pnex=pbeg->next; while (pnex->value < val) { prev = pnex; pnex = pnex->next; } prev->next = pnew; pnew->next = pnex; } }
Описание слайда:
Добавление к упорядоченному списку void SortedList::add(int val) { ListElem *pnew = new ListElem; pnew->value = val; pnew->next = NULL; if (!pbeg) pbeg = pend = pnew; else if (pbeg->value >= val) { pnew->next = pbeg; pbeg = pnew; } else if (pend->value < val) { pend->next = pnew; pend = pnew; } else { ListElem *prev=pbeg, *pnex=pbeg->next; while (pnex->value < val) { prev = pnex; pnex = pnex->next; } prev->next = pnew; pnew->next = pnex; } }

Слайд 34


Поиск элемента в упорядоченном списке ListElem* SortedList::find_elem(int keyval) { ListElem *pcur = pbeg; while (pcur && pcur->value < keyval) pcur = pcur->next; if (pcur && pcur->value == keyval) return pcur; return NULL; }
Описание слайда:
Поиск элемента в упорядоченном списке ListElem* SortedList::find_elem(int keyval) { ListElem *pcur = pbeg; while (pcur && pcur->value < keyval) pcur = pcur->next; if (pcur && pcur->value == keyval) return pcur; return NULL; }

Слайд 35


Поиск значения в упорядоченном списке int SortedList::find(int keyval) { ListElem *ptr = find_elem(keyval); if (!ptr) return -1; return ptr->value; }
Описание слайда:
Поиск значения в упорядоченном списке int SortedList::find(int keyval) { ListElem *ptr = find_elem(keyval); if (!ptr) return -1; return ptr->value; }

Слайд 36


Идея слияния двух упорядоченных списков Слияние двух упорядоченных списков A (текущего) и B можно проводить, строя дополнительный упорядоченный список C. При этом не нужно создавать новых элементов: надо извлекать начальные элементы либо из A, либо из B, и переносить их в конец C. После заполнения C списки A и B будут пустыми. Если необходимо, чтобы объединенный список хранился в A, необходимо просто перенести туда значения pbeg и pend из C, а затем очистить эти поля в C (это необходимо, чтобы при работе деструктора C не удалялись элементы списка).
Описание слайда:
Идея слияния двух упорядоченных списков Слияние двух упорядоченных списков A (текущего) и B можно проводить, строя дополнительный упорядоченный список C. При этом не нужно создавать новых элементов: надо извлекать начальные элементы либо из A, либо из B, и переносить их в конец C. После заполнения C списки A и B будут пустыми. Если необходимо, чтобы объединенный список хранился в A, необходимо просто перенести туда значения pbeg и pend из C, а затем очистить эти поля в C (это необходимо, чтобы при работе деструктора C не удалялись элементы списка).

Слайд 37


Извлечение начального элемента Private-метод извлечения начального элемента и возврата его адреса: ListElem *SortedList::pop_front() { if (!pbeg) return NULL; ListElem *ptr = pbeg; pbeg = pbeg->next; if (!pbeg) pend = NULL; return ptr; }
Описание слайда:
Извлечение начального элемента Private-метод извлечения начального элемента и возврата его адреса: ListElem *SortedList::pop_front() { if (!pbeg) return NULL; ListElem *ptr = pbeg; pbeg = pbeg->next; if (!pbeg) pend = NULL; return ptr; }

Слайд 38


Добавление элемента в конец списка Private-метод добавления элемента, заданного адресом, в конец списка: void SortedList::push_back(ListElem *ptr) { ptr->next = NULL; if (!pbeg) pbeg = pend = ptr; else { pend->next = ptr; pend = ptr; } }
Описание слайда:
Добавление элемента в конец списка Private-метод добавления элемента, заданного адресом, в конец списка: void SortedList::push_back(ListElem *ptr) { ptr->next = NULL; if (!pbeg) pbeg = pend = ptr; else { pend->next = ptr; pend = ptr; } }

Слайд 39


Слияние двух упорядоченных списков void SortedList::merge(SortedList& B) { if (!B.pbeg) return; if (!pbeg){ pbeg = B.pbeg; pend = B.pend; B.pbeg = B.pend = NULL; } else { SortedList C; ListElem *ptr; while (pbeg || B.pbeg) { if (!B.pbeg) ptr = pop_front(); else if (!pbeg) ptr = B.pop_front(); else if (pbeg->value <= (B.pbeg)->value) ptr = pop_front(); else ptr = B.pop_front(); C.push_back(ptr); } pbeg = C.pbeg; pend = C.pend; C.pbeg = C.pend = NULL; } }
Описание слайда:
Слияние двух упорядоченных списков void SortedList::merge(SortedList& B) { if (!B.pbeg) return; if (!pbeg){ pbeg = B.pbeg; pend = B.pend; B.pbeg = B.pend = NULL; } else { SortedList C; ListElem *ptr; while (pbeg || B.pbeg) { if (!B.pbeg) ptr = pop_front(); else if (!pbeg) ptr = B.pop_front(); else if (pbeg->value <= (B.pbeg)->value) ptr = pop_front(); else ptr = B.pop_front(); C.push_back(ptr); } pbeg = C.pbeg; pend = C.pend; C.pbeg = C.pend = NULL; } }

Слайд 40


Использование упорядоченных списков void main() { SortedList a, b; int i; for (i = 0; i < 30; i++) a.add(rand()%100); for (i = 0; i < 20; i++) b.add(rand()%100); if (a.find(99) != -1) a.remove(99); b.merge(a); cout << b.getcount() << endl; }
Описание слайда:
Использование упорядоченных списков void main() { SortedList a, b; int i; for (i = 0; i < 30; i++) a.add(rand()%100); for (i = 0; i < 20; i++) b.add(rand()%100); if (a.find(99) != -1) a.remove(99); b.merge(a); cout << b.getcount() << endl; }

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию