Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Сложные структуры данных. Связные списки

Содержание

Структуры, ссылающиеся на себяstruct node { int x; struct node *next;};
Сложные структуры данных Связные списки Структуры, ссылающиеся на себяstruct node { int x; struct node *next;}; Связный списокСтруктура данных, представляющая собой конечное множество упорядоченных элементов (узлов), связанных друг Недостатки связного спискаНедостатком связного списка, как и других структур типа «список», в Односвязный списокКаждый узел односвязного (однонаправленного связного) списка содержит указатель на следующий узел. Односвязный списокКаждый из блоков представляет элемент (узел) списка. Здесь и далее Head Односвязные и двусвязные спискиОдносвязный список не самый удобный тип связного списка, т. Двусвязный списокОсобенность двусвязного списка, что каждый элемент имеет две ссылки: на следующий Двусвязный списокВозможность двигаться как вперед, так и назад полезна для выполнения некоторых Кольцевой списокЕще один вид связного списка – кольцевой список. В кольцевом односвязном Управление памятьюДля создания и использования динамических структур требуется динамическое распределение памяти — Управление памятьюФункции для управления динамической памятью объявлены в stdlib.hфункция для выделения памяти:void* mallocvoid* malloc (size_t size);Резервирует блоки памяти размером size байт памяти и возвращает freevoid free (void* ptr);Освобождает память, т.е. память возвращается системе, и в дальнейшем #include struct node { int x; struct node *next;};int main(){ /* int main(){ /* Это менять нельзя, т.к. тогда мы потеряем список /* Создаёт новый узел в конце */ conductor->next = malloc( conductor = root;if ( conductor != NULL ) { /*убедимся, что существует conductor = root;while ( conductor != NULL ) { printf( Очистка памяти struct node *temp; temp = root->ptr; free(root); /* освобождение Стек Стеком называется структура данных, организованная по принципу LIFO – last-in, first-out , т.е. элемент, попавшим в множество последним, Стек Стек Реализация 1на основе массиваДля реализации стека, состоящего не более чем из 100  чисел, Стек Реализация 2на основе массива с использованием общей структурыstruct Stack{int stack[100];int n;}; Стек Реализация 3на основе указателейЕсли максимальный размер стека можно выяснить только после ОчередьОчередью называется структура данных, организованная по принципу FIFO – first-in, first-out , т.е. элемент, попавшим в множество первым, Очередь Очередь реализацияДля реализации очереди необходимо знать первый и последний элемент находящийся в Бинарное деревоБинарными деревьями называют структуру данных, в которой, как правило, задан корневой элемент или корень и для Бинарное дерево реализацияstruct STree{ int value; struct STree *prev; struct STree *left, *right;};здесь указатель prev указывает на Бинарное деревоБинарное дерево называется деревом поиска, если для любой вершины дерева a ключи всех вершин Дерево поискаПоиск элементаstruct STree *Find(struct STree *root, int v){if(root==NULL)return NULL;if(root->value==v)return root;if(root->value>=v)return Find(root->right,v);else return Find(root->left, v);}; Дерево поиска Добавление элемента struct STree *Insert(struct STree *root, struct STree *v){ Дерево поиска Дерево поискаif(v->value>=root->value) Дерево поискаreturn root->right==NULL ? Дерево поискаroot->right==NULL ?(v->back=root,v->right=v->left=NULL,root->right=v) : Insert(root->right, v); Дерево поискаif(v->value>=root->value) Дерево поиска return root->left==NULL ? Дерево поискаroot->left==NULL ? (v->prev=root,v->right=v->left=NULL,root->left=v) : Insert(root->left, v); Функция Insert добавляет элемент в бинарное дерево поиска и возвращает указатель на Аргументы командной строки При запуске программы через консоль возможно передать в программу данные, Аргументы командной строки Обратиться к аргументам командной строки в программе возможно через специальные Аргументы командной строки#include int main(int argc, char *argv[]){ if(argc > 1) { printf( Аргументы командной строки
Слайды презентации

Слайд 2 Структуры, ссылающиеся на себя
struct node {
int x;

Структуры, ссылающиеся на себяstruct node { int x; struct node *next;};

struct node *next;
};

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

Связный списокСтруктура данных, представляющая собой конечное множество упорядоченных элементов (узлов), связанных

элементов (узлов), связанных друг с другом посредством указателей, называется

связным списком.
Каждый элемент связного списка содержит поле с данными, а также указатель на следующий и/или предыдущий элемент. Эта структура позволяет эффективно выполнять операции добавления и удаления элементов для любой позиции в последовательности.


Слайд 4 Недостатки связного списка
Недостатком связного списка, как и других

Недостатки связного спискаНедостатком связного списка, как и других структур типа «список»,

структур типа «список», в сравнении его с массивом, является

отсутствие возможности работать с данными в режиме произвольного доступа, т. е. список – структура последовательно доступа, в то время как массив – произвольного.

Слайд 5 Односвязный список
Каждый узел односвязного (однонаправленного связного) списка содержит

Односвязный списокКаждый узел односвязного (однонаправленного связного) списка содержит указатель на следующий

указатель на следующий узел. Из одной точки можно попасть

лишь в следующую точку, двигаясь тем самым в конец. Так получается своеобразный поток, текущий в одном направлении.

Слайд 6 Односвязный список
Каждый из блоков представляет элемент (узел) списка.

Односвязный списокКаждый из блоков представляет элемент (узел) списка. Здесь и далее

Здесь и далее Head list – заголовочный элемент списка

(для него предполагается поле next). Он не содержит данные, а только ссылку на следующий элемент. На наличие данных указывает поле info, а ссылки – поле next. Признаком отсутствия указателя является поле null.

Слайд 7 Односвязные и двусвязные списки
Односвязный список не самый удобный

Односвязные и двусвязные спискиОдносвязный список не самый удобный тип связного списка,

тип связного списка, т. к. из одной точки можно

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

Слайд 8 Двусвязный список
Особенность двусвязного списка, что каждый элемент имеет

Двусвязный списокОсобенность двусвязного списка, что каждый элемент имеет две ссылки: на

две ссылки: на следующий и на предыдущий элемент, позволяет

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

Слайд 9 Двусвязный список
Возможность двигаться как вперед, так и назад

Двусвязный списокВозможность двигаться как вперед, так и назад полезна для выполнения

полезна для выполнения некоторых операций, но дополнительные указатели требуют

задействования большего количества памяти, чем таковой необходимо в односвязном списке.

Слайд 10 Кольцевой список
Еще один вид связного списка – кольцевой

Кольцевой списокЕще один вид связного списка – кольцевой список. В кольцевом

список. В кольцевом односвязном списке последний элемент ссылается на

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

Слайд 11 Управление памятью
Для создания и использования динамических структур требуется

Управление памятьюДля создания и использования динамических структур требуется динамическое распределение памяти

динамическое распределение памяти — возможность получения памяти для хранения

новых узлов и освобождать память для удаления узлов.

Слайд 12 Управление памятью
Функции для управления динамической памятью объявлены в

Управление памятьюФункции для управления динамической памятью объявлены в stdlib.hфункция для выделения

stdlib.h
функция для выделения памяти:
void* malloc (size_t size);
Функция для освобождения

ранее выделенной памяти:
void free (void* ptr);

Слайд 13 malloc
void* malloc (size_t size);
Резервирует блоки памяти размером size

mallocvoid* malloc (size_t size);Резервирует блоки памяти размером size байт памяти и

байт памяти и возвращает указатель на начало зарезервированного участка

памяти.
Например:
newPtr = malloc (sizeof(struct node));
sizeof(struct node) определяет размер в байтах структуры типа struct node, а malloc выделяет новый блок памяти размером в sizeof(struct node) и возвращает указатель на выделенную память в newPtr. Если памяти для выделения не достаточно, то malloc возвращает указатель на NULL

Слайд 14 free
void free (void* ptr);
Освобождает память, т.е. память возвращается

freevoid free (void* ptr);Освобождает память, т.е. память возвращается системе, и в

системе, и в дальнейшем её можно будет выделить снова.
Например:
free

(newPtr);
После того как выделенная память больше не нужна необходимо её освободить при помощи free. Так же это не обходимо делать перед завершением программы, если память ещё не была освобождена.

Слайд 15 #include

struct node {
int x;
struct node

#include struct node { int x; struct node *next;};int main(){ /*

*next;
};
int main()
{
/* Обычная структура */
struct

node *root;
/* Теперь root указывает на структуру node */
root = (struct node *) malloc( sizeof(struct node) );
/* Узел root указывает на следующий элемент, которого пока нет */
root->next = NULL;
/* Использование оператора -> позволяет изменять узел структуры, на которую он указывает */
root->x = 5;
free ( root );
return 0;
}

Слайд 16 int main()
{
/* Это менять нельзя, т.к.

int main(){ /* Это менять нельзя, т.к. тогда мы потеряем список

тогда мы потеряем список в памяти */
struct

node *root;
/* Это указывает на каждый элемент списка, пока мы пробегаем по нему */
struct node *conductor;

root = malloc( sizeof(struct node) );
root->next = NULL;
root->x = 12;
conductor = root;
if ( conductor != NULL ) {
while ( conductor->next != NULL)
{
conductor = conductor->next;
}
}

Слайд 17 /* Создаёт новый узел в конце */

next = NULL; conductor->x = 42; return 0;}">/* Создаёт новый узел в конце */ conductor->next = malloc(

conductor->next = malloc( sizeof(struct node) );

conductor = conductor->next;

if ( conductor == NULL )
{
printf("Не хватает памяти!\n");
return 0;
}
/* инициализируем память */
conductor->next = NULL;
conductor->x = 42;

return 0;
}

Слайд 18 conductor = root;
if ( conductor != NULL )

x); conductor = conductor->next; } printf( "%d\n", conductor->x );}">conductor = root;if ( conductor != NULL ) { /*убедимся, что

{
/*убедимся, что существует место старта*/
while (

conductor->next != NULL ) {
printf( "%d\n", conductor->x);
conductor = conductor->next;
}
printf( "%d\n", conductor->x );
}

Слайд 19 conductor = root;
while ( conductor != NULL )

x ); conductor = conductor->next;}">conductor = root;while ( conductor != NULL ) { printf( x ); conductor = conductor->next;}">

{
printf( "%d\n", conductor->x );
conductor =

conductor->next;
}

Слайд 20 Очистка памяти
struct node *temp;
temp = root->ptr;

Очистка памяти struct node *temp; temp = root->ptr; free(root); /* освобождение

free(root); /* освобождение памяти текущего корня*/
root =

temp; // новый корень списка

Слайд 21 Стек
 Стеком называется структура данных, организованная по принципу LIFO – last-in, first-out , т.е. элемент,

Стек Стеком называется структура данных, организованная по принципу LIFO – last-in, first-out , т.е. элемент, попавшим в множество

попавшим в множество последним, должен первым его покинуть.
При

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

Слайд 22 Стек

Стек

Слайд 23 Стек Реализация 1
на основе массива
Для реализации стека, состоящего не

Стек Реализация 1на основе массиваДля реализации стека, состоящего не более чем

более чем из 100  чисел, следует определить массив, состоящий из 100  элементов и

целую переменную, указывающую на вершину стека (ее значение будет также равно текущему числу элементов в стеке)
int stack[100], n=0;

Слайд 24 Стек Реализация 2
на основе массива с использованием общей структуры

struct

Стек Реализация 2на основе массива с использованием общей структурыstruct Stack{int stack[100];int n;};

Stack{
int stack[100];
int n;
};

Слайд 25 Стек Реализация 3
на основе указателей
Если максимальный размер стека можно

Стек Реализация 3на основе указателейЕсли максимальный размер стека можно выяснить только

выяснить только после компиляции программы, то память под стек

нужно выделять динамически. При этом, вершину стека можно указывать не индексом в массиве, а указателем на вершину. Для этого следует определить следующие переменные
int *stack, *head;
или
struct SStack{
int *stack;
int *n;
};

Слайд 26 Очередь
Очередью называется структура данных, организованная по принципу FIFO – first-in, first-out , т.е. элемент,

ОчередьОчередью называется структура данных, организованная по принципу FIFO – first-in, first-out , т.е. элемент, попавшим в множество

попавшим в множество первым, должен первым его и покинуть.

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

Слайд 27 Очередь

Очередь

Слайд 28 Очередь реализация
Для реализации очереди необходимо знать первый и последний

Очередь реализацияДля реализации очереди необходимо знать первый и последний элемент находящийся

элемент находящийся в ней. Например, для реализации стандартной очереди

из менее чем 100 целых чисел определить следующие данные
#define N 100
int array[N], begin=0,end=0;

Соответственно при добавлении элементов в очередь переменная end будет увеличиваться, а при изъятии их из очереди увеличиваться будет begin.

Слайд 29 Бинарное дерево
Бинарными деревьями называют структуру данных, в которой, как

Бинарное деревоБинарными деревьями называют структуру данных, в которой, как правило, задан корневой элемент или корень и

правило, задан корневой элемент или корень и для каждой вершины (элемента) существует не

более двух потомков.

Слайд 30 Бинарное дерево реализация
struct STree{
int value;
struct STree *prev;
struct STree *left,

Бинарное дерево реализацияstruct STree{ int value; struct STree *prev; struct STree *left, *right;};здесь указатель prev указывает

*right;
};
здесь указатель prev указывает на родительский элемент данной вершины, а left и right – на

двух потомков, которых традиционно называют левым и правым. Величина value называется ключом вершины.

Слайд 31 Бинарное дерево
Бинарное дерево называется деревом поиска, если для любой

Бинарное деревоБинарное дерево называется деревом поиска, если для любой вершины дерева a ключи всех

вершины дерева a ключи всех вершин в правом поддереве больше или

равны ключа a, а в левом – меньше. Неравенства можно заменить на строгие, если известно, что в дереве нет равных элементов.

Слайд 32 Дерево поиска
Поиск элемента

struct STree *Find(struct STree *root, int

Дерево поискаПоиск элементаstruct STree *Find(struct STree *root, int v){if(root==NULL)return NULL;if(root->value==v)return root;if(root->value>=v)return Find(root->right,v);else return Find(root->left, v);};

v){
if(root==NULL)return NULL;
if(root->value==v)return root;
if(root->value>=v)return Find(root->right,v);
else return Find(root->left, v);
};

Слайд 33 Дерево поиска Добавление элемента
struct STree *Insert(struct STree *root, struct

Дерево поиска Добавление элемента struct STree *Insert(struct STree *root, struct STree

STree *v){
if(v->value>=root->value)
return root->right==NULL ?
(v->prev=root,

v->right=v->left=NULL, root->right=v) : Insert(root->right, v);
else
return root->left==NULL ?
(v->prev=root,v->right=v->left=NULL,root->left=v) : Insert(root->left, v);
};

Слайд 34 Дерево поиска

Дерево поиска

Слайд 35 Дерево поиска
if(v->value>=root->value)

Дерево поискаif(v->value>=root->value)

Слайд 36 Дерево поиска
return root->right==NULL ?


Дерево поискаreturn root->right==NULL ?

Слайд 37 Дерево поиска
root->right==NULL ?
(v->back=root,v->right=v->left=NULL,root->right=v) : Insert(root->right, v);

Дерево поискаroot->right==NULL ?(v->back=root,v->right=v->left=NULL,root->right=v) : Insert(root->right, v);

Слайд 38 Дерево поиска
if(v->value>=root->value)

Дерево поискаif(v->value>=root->value)

Слайд 39 Дерево поиска
return root->left==NULL ?

Дерево поиска return root->left==NULL ?

Слайд 40 Дерево поиска
root->left==NULL ?
(v->prev=root,v->right=v->left=NULL,root->left=v) : Insert(root->left, v);

Дерево поискаroot->left==NULL ? (v->prev=root,v->right=v->left=NULL,root->left=v) : Insert(root->left, v);

Слайд 41 Функция Insert добавляет элемент в бинарное дерево поиска

Функция Insert добавляет элемент в бинарное дерево поиска и возвращает указатель

и возвращает указатель на добавляемый элемент.
Дерево поиска Добавление элемента

Слайд 42 Аргументы командной строки
При запуске программы через консоль возможно

Аргументы командной строки При запуске программы через консоль возможно передать в программу

передать в программу данные, называемые Аргументы командной строки, в

виде строк.
Они могут быть использованы во время работы программы

Слайд 43 Аргументы командной строки
Обратиться к аргументам командной строки в

Аргументы командной строки Обратиться к аргументам командной строки в программе возможно через

программе возможно через специальные переменные int argc и char

*argv[]
argc – число переданных аргументов,
argv – массив строк равный числу аргументов.
При вызове программы всегда есть один аргумент имя запущенной программы.

Слайд 44 Аргументы командной строки
#include

int main(int argc, char *argv[]){
if(argc

Аргументы командной строки#include int main(int argc, char *argv[]){ if(argc > 1) { printf(

> 1) {
printf("Вы ввели много чего");
}
printf("Но это точно имя

этой программы: %s", argv[0]);

return 0;
}
  • Имя файла: slozhnye-struktury-dannyh-svyaznye-spiski.pptx
  • Количество просмотров: 125
  • Количество скачиваний: 0
- Предыдущая Аттестационная работа. Программа внеурочной деятельности Магия чисел
Следующая - Кто спит зимой

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

“Информатикалық эрудит” интеллектуалдық ойыны “Информатикалық эрудит” интеллектуалдық ойыны 212
Передача информации 10 класс Передача информации 10 класс 184
Тема Логика. Логические операции Тема Логика. Логические операции 176
Ввод информации в память компьютера Ввод информации в память компьютера 110
Презентация. Цель применения ИКТ. Презентация. Цель применения ИКТ. 130
Презентация по теме Сервисы Google Презентация по теме Сервисы Google 160
Обучающая презентация Программа PowerPoint Обучающая презентация Программа PowerPoint 138
Базы данных. Информационные системы Базы данных. Информационные системы 127
Подготовка к ГИА Подготовка к ГИА 101
Симметрия Симметрия 98
Компьютерные переводчики Компьютерные переводчики 112
Графика в сервисах Google Графика в сервисах Google 105
Правовая охрана программ и данных Правовая охрана программ и данных 116
Устройство компьютера Устройство компьютера 121
Программирование на языке ассемблер (Assembler) Программирование на языке ассемблер (Assembler) 137
Сложные условия Сложные условия 140
Редактирование текста Редактирование текста 178
Кодирование звуковой информации Кодирование звуковой информации 143
Понятия об информационных и геоинформационных системах Понятия об информационных и геоинформационных системах 124
ЛИЧНОСТЬ И ИНТЕРНЕТ. СЕТЕВАЯ ЛИЧНОСТЬ И ПСИХОЛОГИЧЕСКИЙ АСПЕКТ ЛИЧНОСТЬ И ИНТЕРНЕТ. СЕТЕВАЯ ЛИЧНОСТЬ И ПСИХОЛОГИЧЕСКИЙ АСПЕКТ 123
Программирование циклов (9 класс) Программирование циклов (9 класс) 250
Архивация файлов Архивация файлов 200
Презентация по информатике не тему Алгоритм және оның атқарушылары Презентация по информатике не тему Алгоритм және оның атқарушылары 163
Искусственный интеллект Искусственный интеллект 158
Протокол OSPF Протокол OSPF 137
Информационные модели Информационные модели 133
Стилизация фото Стилизация фото 163
Структура программного обеспечения компьютера Структура программного обеспечения компьютера 275
Презентация по информатике на тему Основные характеристики ОС Презентация по информатике на тему Основные характеристики ОС 131
Антивирус авира Антивирус авира 163