Введение в программирование С++. Закрепление знаний в программирование и изучение функций, 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