Пользовательские типы данных (C++). Лекция 7 по основам программирования презентация

Содержание


Презентации» Информатика» Пользовательские типы данных (C++). Лекция 7 по основам программирования
ЛЕКЦИЯ 7
 ОСНОВЫ ПРОГРАММИРОВАНИЯПОЛЬЗОВАТЕЛЬСКИЕ ТИПЫ ДАННЫХ
 Пользовательские типы данных можно создать с помощью:
 структурыОПЕРАТОР TYPEDEF
 Оператор typedef определяет новое имя для уже существующего типа.СТРУКТУРЫ
 Структура — это совокупность переменных, объединенных под одним именем. 
STRUCT
 struct тег {
  тип имя-члена;
  тип имя-члена;
 СТРУКТУРЫ
 struct addr
 {
  char name[30];
  char street[40];
 СТРУКТУРЫ
 Доступ к отдельным элементам структуры осуществляется с помощью оператора .АНАЛИЗ ПРОГРАММЫ
 int main()
 {
  struct {
   intАНАЛИЗ ПРОГРАММЫ
 // объявление массива структур
 struct addr addr_list[100];
 // объявлениеАНАЛИЗ ПРОГРАММЫ
 struct Phone
 { 
    char* name; 
    long phoneNumber;
БИТОВЫЕ ПОЛЯ
 Битовые поля — это особый вид полей структуры. ОниБИТОВЫЕ ПОЛЯ
 struct Options {
   bool centerX:1;
  ОБЪЕДИНЕНИЯ
 Объединение (union) представляет собой частный случай структуры, все поля которойОБЪЕДИНЕНИЯ
 struct Options {
   bool centerX:1;
   boolОБЪЕДИНЕНИЯ
 Ограничения объединений (по сравнению со структурами):
 объединение может инициализироваться толькоПЕРЕЧИСЛЕНИЯ
 Перечисление — это набор именованных целых констант.
 enum тег {списокПЕРЕЧИСЛЕНИЯ
 /*
 penny (пенни, монета в один цент)
 nickel (никель, монетаПЕРЕЧИСЛЕНИЯ
 enum Err {ERR_READ, ERR_WRITE, ERR_CONVERT};
 Err error;
 // ...
 switchДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
 Если до начала работы с данными невозможно определить,ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
 Механизм доступа (data engine) к данным –механизм сохраненияДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
 Динамические структуры данных (списки, стеки, очереди, деревья) различаютсяДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
 Элемент любой динамической структуры данных представляет собой структуруДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
 Описание простейшего элемента (компоненты, узла) динамической структуры: 
СПИСКИ
 Списком называется упорядоченное множество, состоящее из переменного числа элементов, кСПИСКИ
 Самый простой способ связать множество элементов — сделать так, чтобыСПИСКИ
 Каждый элемент списка содержит ключ, идентифицирующий этот элемент.
 Ключ обычноСВЯЗНЫЕ ЛИНЕЙНЫЕ СПИСКИ
 INF - информационное поле, данные
 NEXT - указательСВЯЗНЫЕ ЛИНЕЙНЫЕ СПИСКИ
 Линейный двусвязный список:
 Наличие двух указателей в каждомСВЯЗНЫЕ ЛИНЕЙНЫЕ СПИСКИ
 Кольцевой список (может быть организован на основе какОПЕРАЦИИ НАД СПИСКАМИ
 начальное формирование списка (создание первого элемента);
 добавление элементаРЕАЛИЗАЦИЯ ОПЕРАЦИЙ НАД ЛИНЕЙНЫМИ СПИСКАМИ
 Вставка элемента в середину 1-связного списка
РЕАЛИЗАЦИЯ ОПЕРАЦИЙ НАД ЛИНЕЙНЫМИ СПИСКАМИ
 Вставка элемента в середину 2-связного спискаРЕАЛИЗАЦИЯ ОПЕРАЦИЙ НАД ЛИНЕЙНЫМИ СПИСКАМИ
 Удаление элемента из 1-связного списка
 
РЕАЛИЗАЦИЯ ОПЕРАЦИЙ НАД ЛИНЕЙНЫМИ СПИСКАМИ
 Перестановка элементов 1-связного списка
 Изменчивость динамическихВОЗМОЖНЫЕ ОПЕРАЦИИ НАД ТИПОМ ДАННЫХ «СПИСОК»
 end(l) — вернуть позицию, следующуюАНАЛИЗ ПРОГРАММЫ
 //Описание структуры элемента списка
 struct Node
 {
 int d;
АНАЛИЗ ПРОГРАММЫ
 // Формирование первого элемента
  
 Node * first(intАНАЛИЗ ПРОГРАММЫ
 // Добавление в конец списка 
 void add(Node **pend,АНАЛИЗ ПРОГРАММЫ
 // Поиск элемента по ключу 
 Node * find(NodeАНАЛИЗ ПРОГРАММЫ
 // Вставка элемента 
 Node * insert(Node * constАНАЛИЗ ПРОГРАММЫ
 // Удаление элемента
 bool remove(Node **pbeg, Node **pend, intСРАВНЕНИЕ ОПЕРАЦИЙ  НАД СТРУКТУРАМИ ДАННЫХ
 Сравнение операций над статическими массивами,ДОСТОИНСТВА СПИСКОВ
 лёгкость добавления и удаления элементов
 размер ограничен только объёмомНЕДОСТАТКИ СПИСКОВ
 сложность определения адреса элемента по его индексу (номеру) вАБСТРАКТНЫЕ ПРИНЦИПЫ ОБРАБОТКИ СПИСКОВ 
 
 FIFO (First In, First Out)ОЧЕРЕДИ
 Очередь — это частный случай линейного  1-связного списка, добавлениеОЧЕРЕДИ
 Типичные операции:
 void push(const value_type&) - добавить элемент
 void pop()СТЕКИ
 Стек — это частный случай линейного  1-связного списка, добавлениеСТЕКИ
 Типичные операции: 
   void push(const value_type&) - добавитьЗАДАЧИ (СПИСКИ)
 1) Написать программу, выводящую элемент списка по его номеру.



Слайды и текст этой презентации
Слайд 1
Описание слайда:
ЛЕКЦИЯ 7 ОСНОВЫ ПРОГРАММИРОВАНИЯ


Слайд 2
Описание слайда:
ПОЛЬЗОВАТЕЛЬСКИЕ ТИПЫ ДАННЫХ Пользовательские типы данных можно создать с помощью: структуры — группы переменных, имеющей одно имя и называемой агрегатным типом данных (соединение (compound), конгломерат (conglomerate).); объединения, которое позволяет определять один и тот же участок памяти как два или более типов переменных; битового поля, которое является специальным типом элемента структуры или объединения, позволяющим легко получать доступ к отдельным битам; перечисления — списка поименованных целых констант; ключевого слова typedef, которое определяет новое имя для существующего типа.

Слайд 3
Описание слайда:
ОПЕРАТОР TYPEDEF Оператор typedef определяет новое имя для уже существующего типа. Общий вид декларации: typedef type1 type2; type1 — это любой тип данных языка С++, type2 — новое имя этого типа.

Слайд 4
Описание слайда:
СТРУКТУРЫ Структура — это совокупность переменных, объединенных под одним именем. Объявление структуры создает шаблон, который можно использовать для создания ее объектов (то есть экземпляров этой структуры). Переменные, из которых состоит структура, называются членами (элементами, полями), и могут иметь любой тип, кроме типа этой же структуры, но могут быть указателями на него.

Слайд 5
Описание слайда:
STRUCT struct тег { тип имя-члена; тип имя-члена; тип имя-члена; . . . } переменные-структуры; тег или переменные-структуры могут быть пропущены, но только не оба одновременно.

Слайд 6
Описание слайда:
СТРУКТУРЫ struct addr { char name[30]; char street[40]; char city[20]; char state[3]; unsigned long int zip; }; struct addr addr_info; addr_info.zip = 12345;

Слайд 7
Описание слайда:
СТРУКТУРЫ Доступ к отдельным элементам структуры осуществляется с помощью оператора . (точка) имя-объекта-структуры.имя-элемента addr_info.zip = 191002; При обращении через указатель -> pointer_addr_info->zip = 198504;

Слайд 8
Описание слайда:
АНАЛИЗ ПРОГРАММЫ int main() { struct { int a; int b; } x, y, *z; x.a = 10; y=x; z=&x; cout<<y.a<<z->a; return 0;}

Слайд 9
Описание слайда:
АНАЛИЗ ПРОГРАММЫ // объявление массива структур struct addr addr_list[100]; // объявление указателя на структуру struct addr *addr_pointer; // использование вложенных структур struct emp { struct addr address; /* вложенная структура */ float salary; } worker;

Слайд 10
Описание слайда:
АНАЛИЗ ПРОГРАММЫ struct Phone {    char* name;    long phoneNumber; }; Phone *somePhone = new Phone; somePhone->name = "Иванов Иван"; somePhone->phoneNumber= 1234567;

Слайд 11
Описание слайда:
БИТОВЫЕ ПОЛЯ Битовые поля — это особый вид полей структуры. Они используются для плотной упаковки данных, например, флажков типа «да/нет». При описании битового поля после имени через двоеточие указывается длина поля в битах. Доступ к полю осуществляется по имени. Адрес поля получить нельзя.

Слайд 12
Описание слайда:
БИТОВЫЕ ПОЛЯ struct Options { bool centerX:1; bool centerY:1; unsigned int shadow:2; unsigned int palette:4; }; struct rgb_color { unsigned red_value:3; unsigned green_value:3; unsigned blue_value:3; };

Слайд 13
Описание слайда:
ОБЪЕДИНЕНИЯ Объединение (union) представляет собой частный случай структуры, все поля которой располагаются по одному и тому же адресу. В каждый момент времени в переменной типа объединение хранится только одно значение.

Слайд 14
Описание слайда:
ОБЪЕДИНЕНИЯ struct Options { bool centerX:1; bool centerY:1; unsigned int shadow:2; unsigned int palette:4; }; union { unsigned char ch; Options bit; } option = {0xC4}; cout << option.bit.palette; option.ch &= 0xF0; // наложение маски

Слайд 15
Описание слайда:
ОБЪЕДИНЕНИЯ Ограничения объединений (по сравнению со структурами): объединение может инициализироваться только значением его первого элемента; объединение не может содержать битовые поля; объединение не может содержать виртуальные методы, конструкторы, деструкторы и операцию присваивания; объединение не может входить в иерархию классов.

Слайд 16
Описание слайда:
ПЕРЕЧИСЛЕНИЯ Перечисление — это набор именованных целых констант. enum тег {список перечисления} список переменных; тег или переменные-структуры могут быть пропущены, но только не оба одновременно. Каждому элементу дается значение, на единицу большее, чем у его предшественника. Первый элемент перечисления имеет значение 0.

Слайд 17
Описание слайда:
ПЕРЕЧИСЛЕНИЯ /* penny (пенни, монета в один цент) nickel (никель, монета в пять центов) dime (монета в 10 центов) quarter (25 центов, четверть доллара) half-dollar (полдоллара) dollar (доллар) */ enum coin { penny, nickel, dime, quarter, half_dollar, dollar}; enum coin money; money = dime;

Слайд 18
Описание слайда:
ПЕРЕЧИСЛЕНИЯ enum Err {ERR_READ, ERR_WRITE, ERR_CONVERT}; Err error; // ... switch (error) { case ERR_READ: /* операторы */ break; case ERR_WRITE: /* операторы */ break; case ERR_CONVERT: /* операторы */ break; }

Слайд 19
Описание слайда:
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ Если до начала работы с данными невозможно определить, сколько памяти потребуется для их хранения, память выделяется по мере необходимости отдельными блоками, связанными друг с другом с помощью указателей. Такой способ организации данных называется динамическими структурами данных, поскольку их размер изменяется во время выполнения программы.

Слайд 20
Описание слайда:
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ Механизм доступа (data engine) к данным –механизм сохранения и получения информации. Очередь (queue) Стек (stack) Связанный список (linked list) Двоичное дерево (binary tree) Каждый из этих методов дает возможность решать задачи определенного класса. Они различаются способами связи отдельных элементов и допустимыми операциями.

Слайд 21
Описание слайда:
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ Динамические структуры данных (списки, стеки, очереди, деревья) различаются способами связи отдельных элементов и допустимыми операциями. Динамическая структура может занимать несмежные участки оперативной памяти. Динамические структуры широко применяют и для более эффективной работы с данными, размер которых известен, особенно для решения задач сортировки.

Слайд 22
Описание слайда:
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ Элемент любой динамической структуры данных представляет собой структуру (struct), содержащую по крайней мере два поля: для хранения данных и для указателя. Полей данных и указателей может быть несколько. Поля данных могут быть любого типа: основного, составного или типа указатель.

Слайд 23
Описание слайда:
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ Описание простейшего элемента (компоненты, узла) динамической структуры: struct Node { /* тип данных Data должен быть определен ранее */ Data d; Node *р: }:

Слайд 24
Описание слайда:
СПИСКИ Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным. Линейные связные списки – простейшие динамические структуры данных. Длина списка равна числу элементов, содержащихся в списке. Список нулевой длины называется пустым списком.

Слайд 25
Описание слайда:
СПИСКИ Самый простой способ связать множество элементов — сделать так, чтобы каждый элемент содержал ссылку на следующий. Такой список называется однонаправленным (односвязным). Если добавить в каждый элемент вторую ссылку — на предыдущий элемент, получится двунаправленный список (двусвязный). Если последний элемент связать указателем с первым, получится кольцевой список.

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

Слайд 27
Описание слайда:
СВЯЗНЫЕ ЛИНЕЙНЫЕ СПИСКИ INF - информационное поле, данные NEXT - указатель на следующий элемент списка nil - специальный признак, свидетельствующий о конце списка Линейный односвязный список: обработка односвязного списка не всегда удобна, так как отсутствует возможность продвижения в противоположную сторону.

Слайд 28
Описание слайда:
СВЯЗНЫЕ ЛИНЕЙНЫЕ СПИСКИ Линейный двусвязный список: Наличие двух указателей в каждом элементе усложняет список и приводит к дополнительным затратам памяти, но в то же время обеспечивает более эффективное выполнение некоторых операций над списком.

Слайд 29
Описание слайда:
СВЯЗНЫЕ ЛИНЕЙНЫЕ СПИСКИ Кольцевой список (может быть организован на основе как односвязного, так и двухсвязного)

Слайд 30
Описание слайда:
ОПЕРАЦИИ НАД СПИСКАМИ начальное формирование списка (создание первого элемента); добавление элемента в конец списка; чтение элемента с заданным ключом; вставка элемента в заданное место списка (до или после элемента с заданным ключом); удаление элемента с заданным ключом; упорядочивание списка по ключу.

Слайд 31
Описание слайда:
РЕАЛИЗАЦИЯ ОПЕРАЦИЙ НАД ЛИНЕЙНЫМИ СПИСКАМИ Вставка элемента в середину 1-связного списка Вставка элемента в начало 1-связного списка

Слайд 32
Описание слайда:
РЕАЛИЗАЦИЯ ОПЕРАЦИЙ НАД ЛИНЕЙНЫМИ СПИСКАМИ Вставка элемента в середину 2-связного списка

Слайд 33
Описание слайда:
РЕАЛИЗАЦИЯ ОПЕРАЦИЙ НАД ЛИНЕЙНЫМИ СПИСКАМИ Удаление элемента из 1-связного списка Удаление элемента из 2-связного списка

Слайд 34
Описание слайда:
РЕАЛИЗАЦИЯ ОПЕРАЦИЙ НАД ЛИНЕЙНЫМИ СПИСКАМИ Перестановка элементов 1-связного списка Изменчивость динамических структур данных предполагает не только изменения размера структуры, но и изменения связей между элементами. Для связных структур изменение связей не требует пересылки данных в памяти, а только изменения указателей в элементах связной структуры.

Слайд 35
Описание слайда:
ВОЗМОЖНЫЕ ОПЕРАЦИИ НАД ТИПОМ ДАННЫХ «СПИСОК» end(l) — вернуть позицию, следующую за последним элементом списка l. insert(x, p, l) — добавить элемент x в позицию p списка l. locate(x, l) — возвращает позицию элемента x в списке l. retrieve(p, l) — возвращает значение элемента в позиции p списка l. delete(p, l) — удаляет элемент в позиции p next(p, l) и previous(p, l), makeNull(l), first(l), printList(l) и т.п.

Слайд 36
Описание слайда:
АНАЛИЗ ПРОГРАММЫ //Описание структуры элемента списка struct Node { int d; Node *next; Node *prev; };

Слайд 37
Описание слайда:
АНАЛИЗ ПРОГРАММЫ // Формирование первого элемента Node * first(int d) { Node *pv = new Node; pv->d = d; pv->next = 0; pv->prev = 0; return pv; };

Слайд 38
Описание слайда:
АНАЛИЗ ПРОГРАММЫ // Добавление в конец списка void add(Node **pend, int d) { Node *pv = new Node; pv->d = d; pv->next = 0; pv->prev = *pend; (*pend)->next = pv; *pend = pv; }

Слайд 39
Описание слайда:
АНАЛИЗ ПРОГРАММЫ // Поиск элемента по ключу Node * find(Node * const pbeg, int d) { Node *pv = pbeg; while (pv) { if(pv->d == d) break; pv = pv->next; } return pv;}

Слайд 40
Описание слайда:
АНАЛИЗ ПРОГРАММЫ // Вставка элемента Node * insert(Node * const pbeg, Node **pend, int key, int d) { if(Node *pkey = find(pbeg, key)){ Node *pv = new Node; pv->d = d; // 1 - установление связи нового узла с последующим: pv->next = pkey->next; // 2 - установление связи нового узла с предыдущим: pv->prev = pkey; // 3 - установление связи предыдущего узла с новым: pkey->next = pv; // 4 - установление связи последующего узла с новым: if( pkey != *pend) (pv->next)->prev = pv; // Обновление указателя на конец списка, // если узел вставляется в конец: else *pend = pv; return pv; } return 0; }

Слайд 41
Описание слайда:
АНАЛИЗ ПРОГРАММЫ // Удаление элемента bool remove(Node **pbeg, Node **pend, int key) { if (Node *pkey = find(*pbeg, key)) { if (pkey == *pbeg) { *pbeg = (*pbeg)->next; (*pbeg)->prev =0;} else if (pkey == *pend) { *pend = (*pend)->prev; (*pend)->next = 0;} else { (pkey->prev)->next = pkey->next; (pkey->next)->prev = pkey->prev;} delete pkey; return true;} return false;}

Слайд 42
Описание слайда:
СРАВНЕНИЕ ОПЕРАЦИЙ НАД СТРУКТУРАМИ ДАННЫХ Сравнение операций над статическими массивами, динамическими массивами и связными списками:

Слайд 43
Описание слайда:
ДОСТОИНСТВА СПИСКОВ лёгкость добавления и удаления элементов размер ограничен только объёмом памяти компьютера и разрядностью указателей динамическое добавление и удаление элементов

Слайд 44
Описание слайда:
НЕДОСТАТКИ СПИСКОВ сложность определения адреса элемента по его индексу (номеру) в списке на поля-указатели (указатели на следующий и предыдущий элемент) расходуется дополнительная память (в массивах, например, указатели не нужны) работа со списком медленнее, чем с массивами, так как к любому элементу списка можно обратиться, только пройдя все предшествующие ему элементы элементы списка могут быть расположены в памяти разреженно, что окажет негативный эффект на кэширование процессора над связными списками гораздо труднее (хотя и в принципе возможно) производить параллельные векторные операции, такие как вычисление суммы

Слайд 45
Описание слайда:
АБСТРАКТНЫЕ ПРИНЦИПЫ ОБРАБОТКИ СПИСКОВ FIFO (First In, First Out) «первым пришёл — первым ушёл» FIFO (First In, First Out) «последним пришёл — первым ушёл»

Слайд 46
Описание слайда:
ОЧЕРЕДИ Очередь — это частный случай линейного 1-связного списка, добавление элементов в который выполняется в один конец, а выборка — из другого конца. Очередь реализует принцип обслуживания FIFO.

Слайд 47
Описание слайда:
ОЧЕРЕДИ Типичные операции: void push(const value_type&) - добавить элемент void pop() - удалить первый элемент size_type size() - размер очереди bool empty() - true, если очередь пуста value_type& front() - получить первый элемент value_type& back() - получить последний элемент

Слайд 48
Описание слайда:
СТЕКИ Стек — это частный случай линейного 1-связного списка, добавление элементов в который и извлечение из которого выполняются с одного конца, называемого вершиной стека. При извлечении элемент исключается из стека. Стек реализует принцип обслуживания LIFO.

Слайд 49
Описание слайда:
СТЕКИ Типичные операции: void push(const value_type&) - добавить элемент void pop() - удалить верхний элемент value_type& top() - получить верхний элемент size_type size() - размер стека bool empty() - true, если стек пуст

Слайд 50
Описание слайда:
ЗАДАЧИ (СПИСКИ) 1) Написать программу, выводящую элемент списка по его номеру. 2) Определить длину списка (вывести длину списка). Список вводится с клавиатуры. 3) Переформировать список так, чтобы список стал в обратном порядке. 4) По заданному списку посчитать количество каждого из встречаемых в нем элементов. 5) В список после каждого вхождения элемента Е вставить элемент F. 6) Реализовать стек и очередь на списках.

Слайд 51
Описание слайда:


Скачать презентацию на тему Пользовательские типы данных (C++). Лекция 7 по основам программирования можно ниже:

Похожие презентации