Презентация Основы программирования. Линейные списки онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Основы программирования. Линейные списки абсолютно бесплатно. Урок-презентация на эту тему содержит всего 40 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Основы программирования. Линейные списки
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:40 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:246.03 kB
- Просмотров:59
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№2 слайд
![Список Линейный список это](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img1.jpg)
Содержание слайда: Список
Линейный список – это контейнер, в котором элементы располагаются в памяти в произвольном порядке, а связь между ними обеспечивается с помощью указателей (ссылок).
Элемент однонаправленного списка состоит из двух частей – информационной (собственно данных) и указателя (ссылки) на следующий элемент списка. Как правило, память для каждого элемента выделяется динамически.
Для доступа к начальному элементу списка используется отдельный указатель (ссылка).
Последний элемент списка не ссылается ни на что, т.е. имеет нулевой указатель (пустую ссылку). Во многих случаях выгодно хранить отдельный указатель на последний элемент.
№3 слайд
![Иллюстрация pbeg указатель на](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img2.jpg)
Содержание слайда: Иллюстрация
pbeg – указатель на начальный элемент,
pend – указатель на конечный элемент
(если он нужен).
Доступ к элементам осуществляется последовательно, по указателям (ссылкам). Если необходимо обеспечить переход не только к последующим, но и к предыдущим элементам, в элементы нужно включить еще один указатель (ссылку) – на предыдущий элемент (нуль для начального элемента списка). Соответствующий список будет двунаправленным.
№4 слайд
![Элемент списка Для](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img3.jpg)
Содержание слайда: Элемент списка
Для представления элемента списка нужно создать соответствующий тип, т.е. описать структуру (класс).
Пусть информационная часть элемента – это просто целое число. Тогда новый тип будет выглядеть следующим образом:
struct IElem
{
int value;
IElem *next;
}
По умолчанию в структуре все поля являются открытыми (public), поэтому никаких дополнительных методов доступа к ним не надо.
№5 слайд
![Стек на основе списка На](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img4.jpg)
Содержание слайда: Стек на основе списка
На основе списка можно строить другие структуры данных. Для примера модифицируем стек из раздела «Структуры и классы», сохраняя весь открытый интерфейс.
Учитывая, что добавление и извлечение элементов стека производится в его вершине, будем считать вершиной начальный элемент списка (т.е. начальный указатель списка всегда показывает на вершину стека, а конечный указатель вообще не нужен).
Элементы списка выделяются динамически, поэтому для стека не нужен массив, и количество элементов стека не ограничено.
№10 слайд
![Информационная часть](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img9.jpg)
Содержание слайда: Информационная часть элементов
Информационная часть элементов списка может быть представлена любым типом, в том числе, структурой или классом. Например, для списка линий это может быть:
class PLine
{
double *x, *y;
int key; int length; …
public:
void setlength(int len);
void free();
void setp(int n,double vx,double vy);
…
};
№14 слайд
![Операции с начальным](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img13.jpg)
Содержание слайда: Операции с начальным элементом
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;
}
№16 слайд
![Добавление элемента в конец](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img15.jpg)
Содержание слайда: Добавление элемента в конец списка
Вариант 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 слайд
![Добавление элемента в конец](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img16.jpg)
Содержание слайда: Добавление элемента в конец списка
Вариант 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 слайд
![Извлечение последнего](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img17.jpg)
Содержание слайда: Извлечение последнего элемента списка
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;
}
№20 слайд
![Сцепление двух списков void](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img19.jpg)
Содержание слайда: Сцепление двух списков
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 слайд
![Поиск в списке по ключу Для](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img20.jpg)
Содержание слайда: Поиск в списке по ключу
Для поиска реализуем 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;
}
№23 слайд
![Удаление элемента с заданным](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img22.jpg)
Содержание слайда: Удаление элемента с заданным ключом
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 слайд
![Операции с текущим элементом](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img23.jpg)
Содержание слайда: Операции с текущим элементом списка
Во многих задачах пользователю требуется выполнять операции с конкретным (текущим) элементом списка, например:
модифицировать информационную часть текущего элемента
вставить новый элемент после текущего
удалить текущий элемент
последовательно обработать все элементы от начала до конца списка.
При этом пользователь должен работать только с информационной частью элементов, а формат списка и его элементов должны быть скрытыми.
Чтобы реализовать это, можно добавить в класс еще одно private-поле (указатель на текущий элемент), модифицировать старые и включить новые методы.
№25 слайд
![Модификация класса List В](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img24.jpg)
Содержание слайда: Модификация класса 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](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img25.jpg)
Содержание слайда: Модификация метода 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 слайд
![Методы доступа к](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img26.jpg)
Содержание слайда: Методы доступа к информационной части
Получение адреса информационной части начального элемента (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 слайд
![Методы доступа к](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img27.jpg)
Содержание слайда: Методы доступа к информационной части
Получение адреса информационной части текущего элемента (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 слайд
![Включение нового элемента](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img28.jpg)
Содержание слайда: Включение нового элемента
Включение нового элемента после текущего (текущая позиция не изменяется):
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 слайд
![Удаление текущего элемента](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img29.jpg)
Содержание слайда: Удаление текущего элемента
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 слайд
![Пример работы с текущим](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img30.jpg)
Содержание слайда: Пример работы с текущим элементом
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 слайд
![Класс для упорядоченного](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img31.jpg)
Содержание слайда: Класс для упорядоченного списка целых
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 слайд
![Добавление к упорядоченному](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img32.jpg)
Содержание слайда: Добавление к упорядоченному списку
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;
}
}
№36 слайд
![Идея слияния двух](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img35.jpg)
Содержание слайда: Идея слияния двух упорядоченных списков
Слияние двух упорядоченных списков A (текущего) и B можно проводить, строя дополнительный упорядоченный список C. При этом не нужно создавать новых элементов: надо извлекать начальные элементы либо из A, либо из B, и переносить их в конец C.
После заполнения C списки A и B будут пустыми. Если необходимо, чтобы объединенный список хранился в A, необходимо просто перенести туда значения pbeg и pend из C, а затем очистить эти поля в C (это необходимо, чтобы при работе деструктора C не удалялись элементы списка).
№39 слайд
![Слияние двух упорядоченных](/documents_6/a4cc7429e6066f60fa9a8f28828d0ab5/img38.jpg)
Содержание слайда: Слияние двух упорядоченных списков
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;
}
}
Скачать все slide презентации Основы программирования. Линейные списки одним архивом:
Похожие презентации
-
Курс по основам программирования на Python. Списки
-
Основы программирования - Java. Списки
-
Основы программирования - Java. Знакомство с unit тестами. Списки – практика
-
Основная (каноническая) задача линейного программирования (ОЗЛП)
-
Методика изучения линейных алгоритмов на основе графических операторов языка программирования Pascal
-
Предмет, метод и теоретические основы методов линейного программирования
-
Язык программирования Паскаль. Основные понятия
-
Нелинейные алгоритмы. Язык программирования Паскаль. 8 класс
-
Основные конструкции языка программирования. Турбо Паскаль (тестирование). 10 -11 класс
-
Кодирование основных типов алгоритмических структур на языках объектно — ориентированного и процедурного программирования