Похожие презентации:
Введение в программирование С++. Закрепление знаний в программирование и изучение функций, pointers и оператора Stack
1.
Введение в программирование С++.Закрепление знаний в программирование и
изучение функций, pointers и оператора
Stack.
ПМ06 Программирование цифровых устройств на базе микроконтроллеров
1
2.
ЦелиПознакомиться
• С контейнерами и последовательностями, как с
абстрактными типами данных;
• С динамическими структурами данных;
• Со способами реализации этих представлений на языке
C++
Получить навыки
• Реализации некоторых АТД на языке C++
2
3.
Соглашения о терминологии• Абстрактный
Тип
функциональное
Данных
описание
(АТД)
[abstract
некоторого
design]
–
сущностей
в
logic
класса
терминах операций, которые могут выполняться над ними.
• Интерфейс АТД – формальное и однозначное описание синтаксиса
и
семантики
операций,
которые
могут
выполняться
над
экземплярами АТД.
Т А К ЖЕ, К А К ОП ИСА НИЕ Я З Ы К А П Р О Г Р А М М И Р О В А Н И Я НЕ
ОПРЕДЕЛЯ ЕТ
ОСОБЕННОСТИ
ЕГО
РЕАЛИЗАЦИИ,
ТАК
И
ИНТЕРФЕЙС А Т Д НЕ ОПРЕДЕЛЯЕТ Р Е А Л И З А Ц И Ю АТД.
3
4.
Контейнер• Контейнер [container] – Абстрактный тип данных, представляющий собой
структурированную коллекцию информационных элементов, доступ к
которым определяется структурой контейнера.
• Добавление
и
удаление
элементов
контейнера
назовём
его
трансформацией.
• Доступ к элементу контейнера – операция получения или изменения
значения этого элемента.
• Последовательность
[sequence]
–
контейнер,
в
котором
элементы
упорядочены по индексам (пронумерованы).
4
5.
Некоторые видыпоследовательностей
• Вектор [vector]
• последовательность, в которой возможен доступ к любому
элементу по индексу элемента
• Дек
• Стек
• Очередь
5
6.
Дек• Дек [deque, double ended queue] – последовательность, в
которой возможны только:
1.
доступ: к концевым элементам;
2.
добавление: до начального и после конечного элемента;
3.
удаление: концевых элементов.
Добавление
Удаление
Удаление
Добавление
Deque
6
7.
Очередь• Очередь [queue] – дек, в котором возможны только:
1.
доступ: к начальному элементу;
2.
добавление: после конечного элемента;
3.
удаление: начального элемента.
• Конечный элемент очереди часто называют хвостом очереди,
а начальный – головой очереди.
Добавление
Удаление
Queue
7
8.
Стек• Стек [stack] – дек, в котором возможны только:
1.
доступ: к конечному элементу;
2.
добавление: после конечного элемента;
3.
удаление: конечного элемента.
• Конечный элемент стека называют вершиной стека.
Добавление
Удаление
Stack
8
9.
СпискиОдносвязный
Двусвязный
9
10.
Список• Список представляет собой такую реализацию
последовательности однотипных элементов, когда элементы
связаны друг с другом посредством ссылок.
• Каждый элемент списка содержит не только информационное поле,
но одно или более полей со ссылками на другие элементы.
10
11.
Наиболее распространённыесписки
• односвязные списки
• каждый элемент, кроме последнего, содержит ссылку на следующий,
последний элемент ссылается на null
• двухсвязные списки
• каждый элемент, кроме первого и последнего, содержит ссылки на
предыдущий и следующий
11
12.
Односвязный списокНачало списка [Top]
Value
Value
……...
null
Value
Примеры
5
7
……...
10
null
“foo”
“bar”
……...
“baz”
null
12
13.
Модель элемента односвязногосписка
Начало списка [Top]
Value
Value
……...
Value
null
#include "iostream"
using namespace std;
struct ListItem {
i n t n;
ListItem* next;
};
void main() {
ListItem head; / / создаём структуру
head.n = 1; / / значение поля структуры
head.next = NULL; / / значение поля типа указатель
}
13
14.
Как добавить элемент водносвязный список?
/ / добавим элемент
ListItem newItem;
newItem.n = 2;
newItem.next = NULL;
/ / head должен "указывать" на новый элемент
head.next = &newItem;
/ / пройдём по списку, нужен "указатель"
ListItem* curr = &head;
while (curr != NULL) {
cout << curr->n << endl;
curr = curr->next;
}
system("pause");
Самостоятельно напишем функцию, добавления элемента в конец
односвязного списка следующий слайд
14
15.
Вставка элемента в односвязный списокПусть имеется некоторый односвязный список и ссылка р на элемент,
после которого мы хотим вставить новый элемент.
Состояние списка перед
добавление элемента
n
……...
Value
n+1
Value
……...
Предшествующий
элемент
А лг оритм добавления элемента
1. создание нового элемента
2. присвоение значений его полям
3. добавление связи с элементом, следующим за P
4. добавление связи с элементом P
15
16.
Создание и инициализация новогоэлемента
1. Создание нового элемента
Новый элемент [Tmp]
?
ListItem Tmp;
?
2. Присвоение значений его полям
Tmp.n = 2;
Tmp.next = NULL;
Новый элемент [Tmp]
New
?
16
17.
Добавление связей3. добавление связи с элементом, следующим за P
Новый элемент [Tmp]
New
n
……...
Tmp.next = p.next;
n+1
Value
Value
Предшествующий
элемент [P]
……...
4. добавление связи с элементом P
Новый элемент [Tmp]
New
p.next = &Tmp;
n
……...
Максименкова О.В., 2015
Value
Предшествующий
элемент [P]
n+1
Value
……...
17
17
18.
Удаление элемента из односвязногосписка
Пусть имеется некоторый односвязный список и ссылка р на
элемент, предшествующий тому, который мы хотим удалить.
Состояние списка перед
удалением элемента
……...
n
n+1
n+2
Value
Value
Value
……...
Предшествующий
элемент [P]
А лг оритм удаления элемента
1. добавление связи между P и следующим за удаляемым элементом
2. Освобождение памяти из под удалённого элемента!!!
18
19.
Двусвязный списокНачало списка [Head]
Конец списка [Tail]
null
Value
Value
……...
Value
null
null
5
7
……...
9
null
19
20.
Модель элемента двусвязного спискаНачало списка [Head]
null
Value
Value
Конец списка [Tail]
……...
Value
null
struct DblListItem {
i n t n;
ListItem* next;
ListItem* prev;
};
void main() {
DblListItem head;
head.n = 1;
head.next = NULL;
head.prev = NULL;
}
20
21.
Задание: многомерные массивы1. Опишите функцию structure_create(), которая формирует
структуру данных X, основанную на массиве целочисленных
массивов, по следующему правилу: на вход функции подаётся
количество элементов 0<N<1000, хранящихся в X. Каждый массив
из X, начиная со второго содержит на один элемент больше
предыдущего, последний массив может содержать произвольное
количество элементов.
2. Опишите функцию s t r u c t u r e _ f i l l ( ) заполнения значениями
уже созданной структуры вида X.
3. Опишите функцию structure_print() для отформатированного
вывода на экран структуры вида X.
Пример заполнения X числами от 1 до 12
1
2 3
4 5 6
7 8 9 10
11 12
21
22.
Задание: односвязный список1. Описать функцию добавления нового элемента в конец односвязного
списка (как узнать, в какой список добавить элемент?).
2. Описать функцию вывода на экран всех элементов списка, начиная с
головы.
3. Описать функцию добавления элемента в произвольное место в
односвязном списке (как задавать это место?)
4. Описать функцию удаления элемента из списка.
5. Описать функцию обращения/инверсии списка. Функция заменяет
порядок следования элементов на обратный.
22
23.
Задание: двусвязные и закольцованныесписки
1. Опишите набор функций для управления двусвязным списком:
добавление элемента списка, удаление элемента списка, добавление
элемента в конец списка, добавление элемента в начало списка;
вывод списка в прямом и обратном порядке.
2. Каким образом реализовать закольцованный список?
3. * Опишите функции для управления односвязным и двусвязным
закольцованными списками.
4. ** Реализуйте алгоритм сортировки слиянием для односвязного
списка.
23
24.
Задание: двусвязные и закольцованныесписки
4. Объявление и инициализация указателя
Создайте целочисленную переменную и указатель на неё.
Инициализируйте указатель адресом этой переменной и
выведите на экран значение переменной через указатель.
5. Арифметика указателей
Создайте массив из 5 целых чисел и указатель, который
указывает на первый элемент массива. Используя арифметику
указателей, выведите все элементы массива на экран.
6.Указатели и функции
Напишите функцию, которая принимает указатель на целое
число и увеличивает значение этого числа на 10. Вызовите эту
функцию из main и продемонстрируйте изменение значения
переменной.
25.
Спасибо за внимание![email protected]
87021986799
25