Алгоритм
<<  Что такое алгоритм Тема "Алгоритмы" в школьном курсе информатики  >>
Структуры и алгоритмы обработки данных Лекция
Структуры и алгоритмы обработки данных Лекция
Перечисление структуры объединения
Перечисление структуры объединения
Перечисление
Перечисление
Перечисление
Перечисление
Перечисление
Перечисление
Перечисление
Перечисление
Структура
Структура
Структуры
Структуры
Структуры
Структуры
Структуры
Структуры
Структуры
Структуры
Объединения
Объединения
Объединения
Объединения
СВЯЗНЫЕ СПИСКИ intuit
СВЯЗНЫЕ СПИСКИ intuit
Связный список
Связный список
Связный список
Связный список
Связный список
Связный список
Классификация
Классификация
Однонаправленный связный список
Однонаправленный связный список
Однонаправленный связный список
Однонаправленный связный список
Однонаправленный связный список
Однонаправленный связный список
Однонаправленный связный список
Однонаправленный связный список
Однонаправленный связный список
Однонаправленный связный список
Однонаправленный
Однонаправленный
Однонаправленный
Однонаправленный
Однонаправленный
Однонаправленный
Однонаправленный
Однонаправленный
Однонаправленный
Однонаправленный
Однонаправленный
Однонаправленный
Однонаправленный
Однонаправленный
Двунаправленный связный список
Двунаправленный связный список
Двунаправленный связный список
Двунаправленный связный список
Двунаправленный
Двунаправленный
Двунаправленный
Двунаправленный
Кольцевой связный список
Кольцевой связный список
Xor-связный список
Xor-связный список
Xor-связный список
Xor-связный список

Презентация на тему: «Структуры и алгоритмы обработки данных Лекция». Автор: . Файл: «Структуры и алгоритмы обработки данных Лекция.ppt». Размер zip-архива: 532 КБ.

Структуры и алгоритмы обработки данных Лекция

содержание презентации «Структуры и алгоритмы обработки данных Лекция.ppt»
СлайдТекст
1 Структуры и алгоритмы обработки данных Лекция

Структуры и алгоритмы обработки данных Лекция

Структуры. Связные списки.

Заикин Олег Сергеевич zaikin.all24.org

2 Перечисление структуры объединения

Перечисление структуры объединения

3 Перечисление

Перечисление

Перечисление (enumeration) — тип данных, множество значений которого представляет собой ограниченный список идентификаторов. Каждому элементу перечисления соответствует целое число. Начальное значение равно 0, каждое последующее на 1 больше предыдущего. Пример: winter_months {december, january, february}

4 Перечисление

Перечисление

Формат: enum имя_перечисления { список_перечисления } список_переменных; список_переменных необязателен.

5 Перечисление

Перечисление

Создание именованных констант с автоматическим увеличением значения константы Предупреждения о возможных ошибках со стороны компилятора Пример enum winter_months{december, january, february}; cout << december << ‘ ’ << february; Вывод: 0 2

6 Перечисление

Перечисление

имя_перечисления задает тип переменной, его можно использовать для объявления переменных. Пример. rmsk - перечисление римских цифр enum rmsk { I=1, V=5, X=10, L=50, C=100, D=500, M=1000 }; rmsk newvar; // объявление newvar newvar = M + D + V; cout << newvar << endl; Результат: 1505

7 Структура

Структура

Структура – коллекция объединенных общим именем переменных, которая обеспечивает удобное средство хранения данных в одном месте. Структура – составной тип данных. Переменные в структуре называются ее элементами.

8 Структуры

Структуры

Формат описания: struct имя_структуры { тип имя_элемента1; … тип имя_элементаN; } список_переменных; Пример struct complex { float re,im} a; a.re = 5; a.im=10;

re

a

im

9 Структуры

Структуры

Операции доступа к элементу структуры: . – через переменную -> – через указатель Доступ к элементам: complex a, c,*b=&c; // b - указатель a.re=0.0; a.im=3.0; c.re=1.0; b–>im=2.0; (*b).im=2.0; Присваивание c=*b; a=c; Массивы структур: complex d[5];

10 Структуры

Структуры

В C++ нельзя узнать размер динамического массива через его указатель. Поэтому нужно хранить текущую длину динамического массива в целочисленной переменной. В структуре можно хранить указатель и длину: struct dynamic_array{ float *arr; int arr_len } d_arr; arr_len = 10; arr=new float[arr_len]; d_arr.arr = arr; d_arr.arr_len = arr_len;

11 Структуры

Структуры

Структура может содержать в качестве элемента статический массив и даже указатель на эту же структуру. Пример. struct mystruct{ int a; char str[80]; mystruct *sptr; } Структуры, с указателями на самих себя часто используются для реализации связных списков.

12 Объединения

Объединения

Объединение состоит из нескольких переменных, которые разделяют одну и ту же область памяти. Обеспечивает единый интерфейс для различных типов данных.

13 Объединения

Объединения

Формат описания: union имя { тип имя_элемента1; … тип имя_элементаN; } список_переменных;

Пример: struct double_char{ char h_b, l_b;}; union un{ short int i; double_char j; };

un a; a.j.h_b = ‘f’; a.j.l_b=‘d’; cout << a.i << endl; Результат: 49

i

l_b

a

h_b

14 СВЯЗНЫЕ СПИСКИ intuit

СВЯЗНЫЕ СПИСКИ intuit

ru динамические структуры данных

15 Связный список

Связный список

Структура данных, состоящая из узлов, каждый из которых содержит данные, и ссылки на следующий и/или предыдущий узел списка. Преимущество перед массивом - структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка задаётся его внутренними связями.

16 Связный список

Связный список

Узел связного списка состоит из двух полей: адресного поля (P), в котором содержатся один или несколько указателей, связывающий данный узел с другими узлами списка; поля данных (D), в котором содержатся те данные, ради которых и создается структура.

17 Связный список

Связный список

В общем случае узел списка может содержать не один, а несколько указателей и несколько полей данных. Поле данных может быть переменной, массивом или структурой.

18 Классификация

Классификация

Линейные связные списки - Однонаправленный связный список - Двунаправленный связный список - XOR-связный список Кольцевой связный список …

19 Однонаправленный связный список

Однонаправленный связный список

В каждом узле хранится указатель на следующий узел списка. В последнем элементе указатель на следующий элемент равен NULL. Можно передвигаться только в сторону конца списка.

20 Однонаправленный связный список

Однонаправленный связный список

Описание простейшего узла: struct имя_списка { информационное поле; адресное поле; }; Пример struct human { char *name; // информационное поле int age; // информационное поле human *ptr; // адресное поле };

21 Однонаправленный связный список

Однонаправленный связный список

Необходимо обеспечивать позиционирование какого-либо указателя на первый элемент. В противном случае часть или весь список будет недоступен.

22 Однонаправленный связный список

Однонаправленный связный список

Основные операции: создание списка; просмотр списка; вставка элемента в список; удаление элемента из списка; поиск элемента в списке проверка пустоты списка; удаление списка.

23 Однонаправленный связный список

Однонаправленный связный список

// Объявление struct Single_List { //структура данных int Data; //информационное поле Single_List *Next; //адресное поле }; Single_List *Head; //указатель на первый // элемент списка Single_List *Current; //указатель на текущий // элемент списка

24 Однонаправленный

Однонаправленный

Создание

Сначала нужно создать первый элемент списка, а затем добавить остальные элементы. void Make_Single_List(int n, Single_List *&Head){ if (n > 0) { Head = new Single_List(); // выделяем память cout << "Введите значение " << endl; cin >> Head->Data; // получаем значение // информационного поля Head->Next=NULL; // обнуление адресного поля Make_Single_List(n-1, Head->Next); } }

25 Однонаправленный

Однонаправленный

Создание

Make_Single_List() рекурсивно вызывается, пока n > 0. Head->Next передается как нулевой адрес очередного узла. После последнего вызова функции значение Head->Next останется равным NULL. Таким образом будет сделан последний узел односвязного списка.

26 Однонаправленный

Однонаправленный

Просмотр

Операция печати списка заключается в последовательном просмотре всех узлов списка и выводе их значений на экран. Для обработки списка организуется функция, в которой нужно переставлять указатель на следующий узел списка до тех пор, пока указатель не станет, равен NULL, то есть будет достигнут конец списка.

27 Однонаправленный

Однонаправленный

Просмотр

//Печать однонаправленного списка void print_single_list(single_list* head) { if (head != NULL) { cout << head->data << “ ”; //переход к следующему элементу print_single_list(head->next); } else cout << endl; }

28 Однонаправленный

Однонаправленный

Добавление узла

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

29 Однонаправленный

Однонаправленный

Удаление узла

После удаления указатель текущего элемента устанавливается на предшествующий элемент списка или на новое начало списка, если удаляется первый. Алгоритмы удаления первого и последующих элементов списка отличаются друг от друга.

30 Однонаправленный

Однонаправленный

Поиск

Операция поиска элемента в списке заключается в последовательном просмотре всех элементов списка до тех пор, пока текущий элемент не будет содержать заданное значение или пока не будет достигнут конец списка. В последнем случае фиксируется отсутствие искомого элемента в списке (функция принимает значение false).

31 Двунаправленный связный список

Двунаправленный связный список

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

32 Двунаправленный связный список

Двунаправленный связный список

Struct double_list { // структура данных int data; // информационное поле double_list *next, // адрес следующего *prior; // адрес предыдущего }; double_list *head; // указатель на первый // узел списка double_list *current; // указатель на текущий // узел списка (при необходимости)

33 Двунаправленный

Двунаправленный

Создание

void Make_Double_List(int n, Double_List* Head, Double_List* Prior) { if (n > 0) { Head = new Double_List(); cout << "Введите значение "; cin >> Head->Data; Head->Prior = Prior; Head->Next=NULL; Make_Double_List(n-1, Head->Next, Head); } else Head= NULL; }

34 Двунаправленный

Двунаправленный

Создание

Make_Double_List() рекурсивно вызывается, пока n > 0. Head->Next передается как нулевой адрес очередного узла. Адрес текущего узла передается как Prior, чтобы запомнить его как предыдущий для следующего узла. При создании первого узла Prior == NULL, у первого узла нет предыдущего. Пример. Make_Double_List(3, Head, NULL); После последнего вызова функции значение Head->Next останется равным NULL. Таким образом будет сделан последний узел односвязного списка.

35 Кольцевой связный список

Кольцевой связный список

Может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний. Узла с указателем на NULL не существует.

36 Xor-связный список

Xor-связный список

В каждом элементе хранится только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Нужно хранить два указателя на соседние узлы. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию XOR, которая и даст реальный адрес следующего элемента.

37 Xor-связный список

Xor-связный список

Пример Пусть даны указатели First и Second. First указывает на узел № 2, Second – на узел 3. First->P = XOR от адресов узлов № 1 и 3, Second->P = XOR от адресов узлов № 2 и 4. XOR (First->P, Second) = адрес узла 1 XOR (Second->P, First) = адрес узла 4

«Структуры и алгоритмы обработки данных Лекция»
http://900igr.net/prezentacija/informatika/struktury-i-algoritmy-obrabotki-dannykh-lektsija-205750.html
cсылка на страницу
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Алгоритм > Структуры и алгоритмы обработки данных Лекция