- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Списки. Структуры данных. Массивы презентация
Содержание
- 1. Списки. Структуры данных. Массивы
- 2. СТРУКТУРЫ ДАННЫХ Значения стандартных типов данных можно
- 3. МАССИВЫ Массив – это набор некоторого числа
- 4. ПРОБЛЕМЫ РАБОТЫ С МАССИВАМИ Первым недостатком массивов
- 5. СОЗДАНИЕ МАССИВА Статический массив. Располагается в статической
- 6. СОЗДАНИЕ МАССИВА Динамический массив. Располагается в динамической
- 7. ПРОБЛЕМЫ РАБОТЫ С МАССИВАМИ Второй недостаток массивов
- 8. СТРУКТУРЫ Еще одним примером структур данных являются
- 9. СТРУКТУРЫ Структуры также, как и массивы, имеют
- 10. СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ В силу перечисленных особенностей массивы и структуры называют статическими структурами данных
- 11. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ Недостатков статических структур данных
- 12. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ Переменные, входящие в состав
- 13. ЛИНЕЙНЫЕ (ОДНОНАПРАВЛЕННЫЕ) СПИСКИ Самый простой способ соединить
- 14. ЛИНЕЙНЫЕ СПИСКИ Между элементами линейного списка существует отношение предыдущий-последующий
- 15. ТИП ДАННЫХ ЭЛЕМЕНТА СПИСКА Для элемента линейного
- 16. ЛИНЕЙНЫЙ СПИСОК P
- 17. ОПЕРАЦИИ НАД СПИСКАМИ Основными операциями при работе
- 18. ИНИЦИАЛИЗАЦИЯ СПИСКА Эта операция сводится к созданию пустого списка p = NULL;
- 19. ПРОВЕРКА СПИСКА НА ПУСТОТУ Проверка на пустоту
- 20. ДОБАВЛЕНИЕ ЭЛЕМЕНТА В ПУСТОЙ СПИСОК Операция сводится
- 21. ДОБАВЛЕНИЕ ЭЛЕМЕНТА В НЕПУСТОЙ СПИСОК Предполагается, что
- 22. ДОБАВЛЕНИЕ ПОСЛЕ ВЫДЕЛЕННОГО Для этого необходимо выполнить
- 23. ДОБАВЛЕНИЕ ПОСЛЕ ВЫДЕЛЕННОГО
- 24. ДОБАВЛЕНИЕ ПОСЛЕ ВЫДЕЛЕННОГО q= new elem;
- 25. ДОБАВЛЕНИЕ ПЕРЕД ВЫДЕЛЕННЫМ В этом случае задача
- 26. ДОБАВЛЕНИЕ ПЕРЕД ВЫДЕЛЕННЫМ q= new elem;
- 27. СПОСОБЫ ВВОДА ДАННЫХ В СПИСОК Операции добавления
- 28. СОЗДАНИЕ СПИСКА Операции добавления в список позволяют
- 29. СОЗДАНИЕ СПИСКА В зависимости от выбора способа добавления получим прямой или инвертированный список
- 30. СОЗДАНИЕ ПРЯМОГО СПИСКА
- 31. СОЗДАНИЕ ИНВЕРТИРОВАННОГО СПИСКА P
- 32. ПОИСК В СПИСКЕ q = p;
- 33. УДАЛЕНИЕ ЭЛЕМЕНТА ИЗ СПИСКА Особенность этой операции
- 34. УДАЛЕНИЕ ЭЛЕМЕНТА ИЗ СПИСКА
- 35. УДАЛЕНИЕ ПЕРВОГО ЭЛЕМЕНТА СПИСКА Особым случаем является
- 36. УДАЛЕНИЕ ПЕРВОГО ЭЛЕМЕНТА СПИСКА
- 37. ДОПОЛНИТЕЛЬНО: ПРОСМОТР СПИСКА Операция заключается в последовательном
- 38. ПРИМЕР РЕАЛИЗАЦИИ СПИСКА Рассмотрим пример реализации линейного списка в виде динамической структуры Тестирование приложения
- 39. ДВУНАПРАВЛЕННЫЕ СПИСКИ Двунаправленные списки отличаются от однонаправленных
- 40. ДВУНАПРАВЛЕННЫЕ СПИСКИ Небольшое усложнение структуры элемента списка
- 41. ОПЕРАЦИИ ДОБАВЛЕНИЯ И УДАЛЕНИЯ Реализации этих операций
- 42. ОПЕРАЦИИ ДОБАВЛЕНИЯ ЭЛЕМЕНТА Добавить перед q= new
- 43. ДОБАВЛЕНИЕ НА КРАЯХ СПИСКА Добавить первый q=
- 44. УДАЛЕНИЕ ЭЛЕМЕНТА Удалить перед текущим q=r->prev;
- 45. УДАЛЕНИЕ ЭЛЕМЕНТА В двунаправленном списке можно удалить
- 46. КОЛЬЦЕВЫЕ СПИСКИ Кольцевой однонаправленный список получается из
- 47. КОЛЬЦЕВЫЕ СПИСКИ Для двунаправленного кольцевого списка требуется
- 48. РЕАЛИЗАЦИЯ СПИСКА Вышеописанная реализация списка в виде
- 49. РЕАЛИЗАЦИЯ СПИСКА В МАССИВЕ Однако список может
- 50. РЕАЛИЗАЦИЯ СПИСКА В МАССИВЕ В этом случае
- 51. РЕАЛИЗАЦИЯ СПИСКА В МАССИВЕ При этом остается
- 52. СПИСОК КАК АБСТРАКТНАЯ СТРУКТУРА ДАННЫХ Понятие списка
- 53. АБСТРАКТНЫЕ ТИПЫ ДАННЫХ В число этих операций
- 54. СПИСОК КАК АТД Конкретные реализации АТД называются
- 55. ПРИМЕР РЕАЛИЗАЦИИ АТД «СПИСОК» Текст приложения Тестирование приложения
СТРУКТУРЫ ДАННЫХ Значения стандартных типов данных можно группировать и создавать структуры данных Структура данных представляется одной переменной – именем структуры данных, а входящие в нее значения – элементы, выделяются тем или
Слайд 2СТРУКТУРЫ ДАННЫХ
Значения стандартных типов данных можно группировать и создавать структуры данных
Структура
данных представляется одной переменной – именем структуры данных, а входящие в нее значения – элементы, выделяются тем или иным способом, специфичным для каждой такой структуры
Наиболее простой и часто используемой структурой данных является массив
Наиболее простой и часто используемой структурой данных является массив
Слайд 3МАССИВЫ
Массив – это набор некоторого числа однотипных данных, расположенных в последовательных
ячейках памяти
Количество элементов массива называется его размером, а тип элементов – типом массива
Количество элементов массива называется его размером, а тип элементов – типом массива
5
3
7
34
0
-6
11
11
19
Слайд 4ПРОБЛЕМЫ РАБОТЫ С МАССИВАМИ
Первым недостатком массивов является их фиксированный размер, который
устанавливается при создании массива и в дальнейшем не может быть изменен
Частично эта проблема решается при использовании динамических массивов путем создания новых массивов большего размера
Частично эта проблема решается при использовании динамических массивов путем создания новых массивов большего размера
Слайд 5СОЗДАНИЕ МАССИВА
Статический массив. Располагается в статической или автоматической памяти
using namespace std;
const
int n = 10;
int mas[n] = {5, 7, 24, -10, 9, 14, 18, -2, 2, 4};
void sort (int[ ] a, int length)
{
int j, x;
for (int i = 0; i < length; i++){
. . .
}
}
int mas[n] = {5, 7, 24, -10, 9, 14, 18, -2, 2, 4};
void sort (int[ ] a, int length)
{
int j, x;
for (int i = 0; i < length; i++){
. . .
}
}
Слайд 6СОЗДАНИЕ МАССИВА
Динамический массив. Располагается в динамической памяти
int *mas, n;
int _tmain (int
argc, _TCHAR* argv[])
{
. . .
cout << "Задайте размер массива" << endl;
cin >> n;
mas = new int [n] {4, 7 ,9};
. . .
delete [ ] mas;
. . .
}
{
. . .
cout << "Задайте размер массива" << endl;
cin >> n;
mas = new int [n] {4, 7 ,9};
. . .
delete [ ] mas;
. . .
}
Слайд 7ПРОБЛЕМЫ РАБОТЫ С МАССИВАМИ
Второй недостаток массивов связан с тем, что элементы
массива занимают смежные ячейки памяти
Это сильно усложняет выполнение операций добавления и удаления элементов в заполненной части массива
Это сильно усложняет выполнение операций добавления и удаления элементов в заполненной части массива
Слайд 8СТРУКТУРЫ
Еще одним примером структур данных являются структуры
struct
{ char
fio [30];
int age, code;
double salary;
} smith;
Здесь объявлена структура с именем smith, содержащая 4 поля
int age, code;
double salary;
} smith;
Здесь объявлена структура с именем smith, содержащая 4 поля
Слайд 9СТРУКТУРЫ
Структуры также, как и массивы, имеют фиксированный размер, определяемый как сумма
размеров их полей
В отличие от массивов, операции добавления и удаления элементов для структуры невозможны
В отличие от массивов, операции добавления и удаления элементов для структуры невозможны
Слайд 10СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
В силу перечисленных особенностей массивы и структуры называют статическими
структурами данных
Слайд 11ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Недостатков статических структур данных лишены структуры данных с изменяющимися
во время выполнения программы составом и размерами, называемые динамическими структурами данных
Слайд 12ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Переменные, входящие в состав динамических структур, необходимо каким-либо образом
связывать друг с другом
Поэтому каждый элемент динамической структуры должен содержать один или несколько адресов связанных с ним элементов, т.е. указателей на эти элементы
Поэтому каждый элемент динамической структуры должен содержать один или несколько адресов связанных с ним элементов, т.е. указателей на эти элементы
Слайд 13ЛИНЕЙНЫЕ (ОДНОНАПРАВЛЕННЫЕ) СПИСКИ
Самый простой способ соединить отдельные элементы между собой заключается
в том, чтобы снабдить каждый из них только одним указателем на другой элемент
В результате получается динамическая структура, называемая линейным (однонаправленным) списком
В результате получается динамическая структура, называемая линейным (однонаправленным) списком
Слайд 14ЛИНЕЙНЫЕ СПИСКИ
Между элементами линейного списка существует отношение предыдущий-последующий
Слайд 15ТИП ДАННЫХ ЭЛЕМЕНТА СПИСКА
Для элемента линейного списка можно определить следующий тип
данных:
struct element
{ int info; // информационное поле
element* next; // указатель на следующий }; // элемент
Для информационного поля может быть выбран любой другой тип данных, в том числе, массив или структура
struct element
{ int info; // информационное поле
element* next; // указатель на следующий }; // элемент
Для информационного поля может быть выбран любой другой тип данных, в том числе, массив или структура
Слайд 17ОПЕРАЦИИ НАД СПИСКАМИ
Основными операциями при работе со списками являются:
инициализация списка
проверка списка
на пустоту
добавление элемента в список
удаление элемента из списка
поиск в списке
добавление элемента в список
удаление элемента из списка
поиск в списке
Слайд 19ПРОВЕРКА СПИСКА НА ПУСТОТУ
Проверка на пустоту заключается в вычислении значения выражения
p
== NULL,
которое имеет значение TRUE в случае, если список пуст, и FALSE в противном случае
которое имеет значение TRUE в случае, если список пуст, и FALSE в противном случае
Слайд 20ДОБАВЛЕНИЕ ЭЛЕМЕНТА В ПУСТОЙ СПИСОК
Операция сводится к созданию нового элемента с
помощью указателя на голову списка
p= new elem;
p->next = NULL;
x = rand() % 100;
p->info = x;
p= new elem;
p->next = NULL;
x = rand() % 100;
p->info = x;
Слайд 21ДОБАВЛЕНИЕ ЭЛЕМЕНТА В НЕПУСТОЙ СПИСОК
Предполагается, что предварительно в списке тем или
иным способом выделен некоторый элемент
Далее, возможны две ситуации:
новый элемент нужно вставить перед выделенным;
новый элемент нужно вставить после выделенного
Рассмотрим каждую из ним в отдельности
Далее, возможны две ситуации:
новый элемент нужно вставить перед выделенным;
новый элемент нужно вставить после выделенного
Рассмотрим каждую из ним в отдельности
Слайд 22ДОБАВЛЕНИЕ ПОСЛЕ ВЫДЕЛЕННОГО
Для этого необходимо выполнить следующие действия:
определить рабочую переменную-указатель
создать новый
элемент с помощью рабочего указателя
связать новый элемент со следующим за выделенным
связать выделенный элемент с новым
связать новый элемент со следующим за выделенным
связать выделенный элемент с новым
Слайд 24ДОБАВЛЕНИЕ ПОСЛЕ ВЫДЕЛЕННОГО
q= new elem; // создать
новый элемент
q->next = r->next; // связать его со следующим за // выделенным
r->next = q; // связать выделенный элемент с // новым
x = rand() % 100;
q->info = x;
q = NULL;
q->next = r->next; // связать его со следующим за // выделенным
r->next = q; // связать выделенный элемент с // новым
x = rand() % 100;
q->info = x;
q = NULL;
Слайд 25ДОБАВЛЕНИЕ ПЕРЕД ВЫДЕЛЕННЫМ
В этом случае задача сводится к предыдущей, а именно,
нужно:
добавить новый элемент после выделенного,
произвести обмен значениями между выделенным и новым элементами
добавить новый элемент после выделенного,
произвести обмен значениями между выделенным и новым элементами
Слайд 26ДОБАВЛЕНИЕ ПЕРЕД ВЫДЕЛЕННЫМ
q= new elem; // создать
новый элемент
q->next = r->next; // связать его со следующим за // выделенным
r->next = q; // связать выделенный элемент с // новым
x = rand() % 100;
q->info = r->info; // обмен значениями
r->info = x;
q->next = r->next; // связать его со следующим за // выделенным
r->next = q; // связать выделенный элемент с // новым
x = rand() % 100;
q->info = r->info; // обмен значениями
r->info = x;
Слайд 27СПОСОБЫ ВВОДА ДАННЫХ В СПИСОК
Операции добавления элементов в список могут различаться
способом ввода данных
Данные могут задаваться
путем консольного ввода,
путем считывания из файла,
путем использования генератора случайных чисел
Данные могут задаваться
путем консольного ввода,
путем считывания из файла,
путем использования генератора случайных чисел
Слайд 28СОЗДАНИЕ СПИСКА
Операции добавления в список позволяют создавать списки как с прямым,
так и с обратным по отношению к порядку ввода следованием элементов
Алгоритм создания списка:
инициировать список
повторить нужное число раз операцию добавления элемента в список
Алгоритм создания списка:
инициировать список
повторить нужное число раз операцию добавления элемента в список
Слайд 29СОЗДАНИЕ СПИСКА
В зависимости от выбора способа добавления получим прямой или инвертированный
список
Слайд 32ПОИСК В СПИСКЕ
q = p; //поиск заданного значения
x
while (q->next != NULL && q->info!=x)
q = q->next;
if (q->info==x)
cout << «Значение найдено»;
else
cout << «Значение не найдено»;
while (q->next != NULL && q->info!=x)
q = q->next;
if (q->info==x)
cout << «Значение найдено»;
else
cout << «Значение не найдено»;
Слайд 33УДАЛЕНИЕ ЭЛЕМЕНТА ИЗ СПИСКА
Особенность этой операции заключается в том, что удалить
можно только элемент, следующий за выделенным
Алгоритм удаления состоит просто в изменении значения поля указателя выделенного элемента:
q = r->next;
r->next = q->next;
delete *q;
Алгоритм удаления состоит просто в изменении значения поля указателя выделенного элемента:
q = r->next;
r->next = q->next;
delete *q;
Слайд 35УДАЛЕНИЕ ПЕРВОГО ЭЛЕМЕНТА СПИСКА
Особым случаем является удаление первого элемента списка, которое
сводится изменению значения указателя на голову списка:
p = r->next;
delete *r;
Разумеется, удаление элемента возможно только при условии, что список не пуст
p = r->next;
delete *r;
Разумеется, удаление элемента возможно только при условии, что список не пуст
Слайд 37ДОПОЛНИТЕЛЬНО: ПРОСМОТР СПИСКА
Операция заключается в последовательном переборе всех элементов списка от
первого до последнего
Просмотр списка может сопровождаться выводом значений информационных полей, поиском максимального значения и т.д.
Операция реализуется простым циклом for
Просмотр списка может сопровождаться выводом значений информационных полей, поиском максимального значения и т.д.
Операция реализуется простым циклом for
Слайд 38ПРИМЕР РЕАЛИЗАЦИИ СПИСКА
Рассмотрим пример реализации линейного списка в виде динамической структуры
Тестирование
приложения
Слайд 39ДВУНАПРАВЛЕННЫЕ СПИСКИ
Двунаправленные списки отличаются от однонаправленных тем, что между их элементами
существуют отношения предыдущий-последующий и последующий-предыдущий
Слайд 40ДВУНАПРАВЛЕННЫЕ СПИСКИ
Небольшое усложнение структуры элемента списка позволяет получить возможность просмотра его
в двух направлениях: от начала к концу и от конца к началу
struct element
{ int info; // информационное поле
element* prev; // указатель на предыдущий
element* next; // указатель на следующий
};
struct element
{ int info; // информационное поле
element* prev; // указатель на предыдущий
element* next; // указатель на следующий
};
Слайд 41ОПЕРАЦИИ ДОБАВЛЕНИЯ И УДАЛЕНИЯ
Реализации этих операций в двунаправленных списках имеют свои
особенности благодаря возможности доступа к предыдущему и последующему элементам
Так добавление элемента перед выделенным уже не требует обмена значениями и отличается от аналогичной операции добавления после выделенного только способом задания значений ссылок
Так добавление элемента перед выделенным уже не требует обмена значениями и отличается от аналогичной операции добавления после выделенного только способом задания значений ссылок
Слайд 42ОПЕРАЦИИ ДОБАВЛЕНИЯ ЭЛЕМЕНТА
Добавить перед
q= new elem;
q->next = r;
q->prev
= r->prev;
x = rand() % 100;
q->info = x;
r->prev = q;
r->prev->next = q;
q = NULL;
x = rand() % 100;
q->info = x;
r->prev = q;
r->prev->next = q;
q = NULL;
Добавить после
q= new elem;
q->prev = r;
q->next = r->next;
x = rand() % 100;
q->info = x;
r->next = q;
r->next->prev = q;
q = NULL;
Слайд 43ДОБАВЛЕНИЕ НА КРАЯХ СПИСКА
Добавить первый
q= new elem;
q->next =
p;
q->prev = NULL;
x = rand() % 100;
q->info = x;
p->prev = q;
p = q;
q = NULL;
q->prev = NULL;
x = rand() % 100;
q->info = x;
p->prev = q;
p = q;
q = NULL;
Добавить последний
q= new elem;
q->prev = r;
q->next = NULL;
x = rand() % 100;
q->info = x;
r->next = q;
q = NULL;
Слайд 44УДАЛЕНИЕ ЭЛЕМЕНТА
Удалить перед текущим
q=r->prev;
r->prev = q->prev;
q->prev->next =r;
delete *q;
Удалить после текущего
q=r->next;
r->next = q->next;
q->next->prev =r;
delete *q;
Слайд 45УДАЛЕНИЕ ЭЛЕМЕНТА
В двунаправленном списке можно удалить и текущий элемент:
r->prev->next = r->next;
r->next->prev
=r->prev;
delete *r;
delete *r;
Слайд 46КОЛЬЦЕВЫЕ СПИСКИ
Кольцевой однонаправленный список получается из линейного «замыканием» последнего элемента на
первый
Соответственно, операция добавления в конец такого списка должна завершаться следующим присваиванием:
q->next = p;
Соответственно, операция добавления в конец такого списка должна завершаться следующим присваиванием:
q->next = p;
Слайд 47КОЛЬЦЕВЫЕ СПИСКИ
Для двунаправленного кольцевого списка требуется установить две ссылки:
первого элемента на
последний,
последнего элемента на первый
Ссылка первого элемента *p на созданный в конце списка элемент *q имеет вид
p->prev = q;
а последнего на первый
q->next = p;
последнего элемента на первый
Ссылка первого элемента *p на созданный в конце списка элемент *q имеет вид
p->prev = q;
а последнего на первый
q->next = p;
Слайд 48РЕАЛИЗАЦИЯ СПИСКА
Вышеописанная реализация списка в виде связной динамической структуры имеет ряд
очевидных достоинств
К числу этих достоинств относятся:
возможность создавать, удалять и регулировать размер списков во время выполнения программы;
относительная простота выполнения операций добавления элементов в список и их удаления из списка
К числу этих достоинств относятся:
возможность создавать, удалять и регулировать размер списков во время выполнения программы;
относительная простота выполнения операций добавления элементов в список и их удаления из списка
Слайд 49РЕАЛИЗАЦИЯ СПИСКА В МАССИВЕ
Однако список может быть реализован и с помощью
массива
Для этого необходимо создать массив с типом элемента вида:
struct element
{ int info; // информационное поле
int next; // указатель на следующий элемент
};
Для этого необходимо создать массив с типом элемента вида:
struct element
{ int info; // информационное поле
int next; // указатель на следующий элемент
};
Слайд 50РЕАЛИЗАЦИЯ СПИСКА В МАССИВЕ
В этом случае поле ссылки имеет значение индекса
следующего элемента
Для обозначения «свободных» элементов массива можно использовать особые значения поля ссылки, например, равные -2
Операции добавления новых элементов требуют в этих случаях предварительного поиска в массиве свободных мест
Для обозначения «свободных» элементов массива можно использовать особые значения поля ссылки, например, равные -2
Операции добавления новых элементов требуют в этих случаях предварительного поиска в массиве свободных мест
Слайд 51РЕАЛИЗАЦИЯ СПИСКА В МАССИВЕ
При этом остается ограничение на длину списка, что
позволяет реализовать списки с длиной, не превышающей объявленную длину массива
Соответственно, появляется еще одна дополнительная операция – проверка на переполнение списка
Пример реализации списка в виде массива
Тестирование приложения
Соответственно, появляется еще одна дополнительная операция – проверка на переполнение списка
Пример реализации списка в виде массива
Тестирование приложения
Слайд 52СПИСОК КАК АБСТРАКТНАЯ СТРУКТУРА ДАННЫХ
Понятие списка вводится в информатике как структура
данных, представляющая соответствующий абстрактный тип данных
Абстра́ктным типом да́нных (АТД) называется тип данных, который определяется путем перечисления набора возможных операций над его данными
Абстра́ктным типом да́нных (АТД) называется тип данных, который определяется путем перечисления набора возможных операций над его данными
Слайд 53АБСТРАКТНЫЕ ТИПЫ ДАННЫХ
В число этих операций входят операции создания и удаления
элементов АТД
Вся внутренняя структура такого типа спрятана от разработчика программного обеспечения и в этом и заключается суть абстракции
Вся внутренняя структура такого типа спрятана от разработчика программного обеспечения и в этом и заключается суть абстракции
Слайд 54СПИСОК КАК АТД
Конкретные реализации АТД называются структурами данных
Абстрактный тип данных список
может быть реализован при помощи массива или линейного списка
Однако каждая реализация определяет один и тот же набор функций, который должен работать одинаково (по результату, а не по скорости) для всех реализаций
Однако каждая реализация определяет один и тот же набор функций, который должен работать одинаково (по результату, а не по скорости) для всех реализаций
