Структуры и алгоритмы обработки данных Лекция. Структуры. Связные списки. Заикин Олег Сергеевич zaikin.all24.org.

Презентация:



Advertisements
Похожие презентации
Сложные структуры данных Связные списки. Структуры, ссылающиеся на себя struct node { int x; struct node *next; };
Advertisements

Списки Лекция 10. Списки Список – структура данных, представляющая собой конечную последовательность элементов. Элемент списка: Данные Связь.
Распределение памяти. Динамическое выделение памяти.
Основы информатики Лекция. Массивы. Указатели. Заикин Олег Сергеевич
Структуры и объединения Structures and unions НГТУ ИРИТ кафедра ИСУ Ольга Пронина.
Функции Функция – именованная последовательность описаний и операторов, выполняющая некоторое действие. Может иметь параметры и возвращать значение. Функция.
Основы информатики Массивы. Указатели. Заикин Олег Сергеевич
Абстрактный тип данных список. Операции над абстрактным списком Создать пустой список Уничтожить список Определить, пуст ли список Определить количество.
УКАЗАТЕЛИ. Переменная - это именованная область памяти с заданным типом. [=значение]; int a; //Переменная типа integer с именем a int b=2;// Переменная.
Переменная - это величина, которая имеет имя, тип и значение. Значение переменной может меняться во время выполнения программы. В компьютерах каждая переменная.
Лабораторная работа 4. Подпрограммы. Задание на лабораторную работу Написать программу, реализующую хранение информации, указанной в вариантах индивидуальных.
Пусть у нас есть очередь из трех элементов а, в и с, в которую первым был помещен элемент а, а последним элемент с. АВС Esimene Viimane Esimene начало.
Лекция 9 Функции. Массивы-параметры функции Передача массива в функцию Пример: void array_enter(int a[], int size) { int i; for (i = 0; i < size; i++)
Лекция 6 Функции. Объявления и определения Объявление функции – указание имени функции, а также входных и выходных параметров Определение функции – указание.
Лекция 14 Динамические данные. Виды памяти Существует три вида памяти: статическая, стековая и динамическая. Статическая память выделяется еще до начала.
Основы информатики Классы Заикин Олег Сергеевич zaikin.all24.org
Практическое занятие 6. Функции. Большинство языков программирования используют понятия функции и процедуры. C++ формально не поддерживает понятие процедуры,
Преобразования типов В языке C/C++ имеется несколько операций преобразования типов. Они используются в случае, если переменная одного типа должна рассматриваться.
Лекция 6 Функции. Объявления и определения Объявление функции – указание имени функции, а также входных и выходных параметров Определение функции – указание.
Лекция 10 Структуры. Классификация типов данных Простые Целые, вещественные, void, перечисления Являются атомарными не состоят из других типов Адресные.
Транксрипт:

Структуры и алгоритмы обработки данных Лекция. Структуры. Связные списки. Заикин Олег Сергеевич zaikin.all24.org

ПЕРЕЧИСЛЕНИЕ СТРУКТУРЫ ОБЪЕДИНЕНИЯ

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

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

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

Перечисление имя_перечисления задает тип переменной, его можно использовать для объявления переменных. Пример. 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

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

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

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

Структуры В 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;

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

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

Объединения Формат описания: union имя { тип имя_элемента1; … тип имя_элементаN; } список_переменных; Пример: struct double_char{ char h_b, l_b;}; union un{ short int i; double_char j; }; il_bh_ba un a; a.j.h_b = \0; a.j.l_b=1; cout

СВЯЗНЫЕ СПИСКИ intuit.ru динамические структуры данных

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

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

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

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

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

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

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

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

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

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

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

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

Однонаправленный. Просмотр //печать однонаправленного списка void Print_Single_List(Single_List* Head) { if (Head != NULL) { cout Data Next); } else cout

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

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

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

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

Двунаправленный связный список struct Double_List { // структура данных Int Data; // информационное поле Double_List *Next, // адрес следующего *Prior; // адрес предыдущего }; Double_List *Head; // указатель на первый // узел списка Double_List *Current; // указатель на текущий // узел списка (при необходимости)

Двунаправленный. Создание void Make_Double_List(int n, Double_List* Head, Double_List* Prior) { if (n > 0) { Head = new Double_List(); cout > Head->Data; Head->Prior = Prior; Head->Next=NULL; Make_Double_List(n-1, Head->Next, Head); } else Head= NULL; }

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

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

XOR-связный список В каждом элементе хранится только один адрес результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Нужно хранить два указателя на соседние узлы. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию 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