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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Сложные структуры данных. Связные списки, слайд №1Сложные структуры данных. Связные списки, слайд №2Сложные структуры данных. Связные списки, слайд №3Сложные структуры данных. Связные списки, слайд №4Сложные структуры данных. Связные списки, слайд №5Сложные структуры данных. Связные списки, слайд №6Сложные структуры данных. Связные списки, слайд №7Сложные структуры данных. Связные списки, слайд №8Сложные структуры данных. Связные списки, слайд №9Сложные структуры данных. Связные списки, слайд №10Сложные структуры данных. Связные списки, слайд №11Сложные структуры данных. Связные списки, слайд №12Сложные структуры данных. Связные списки, слайд №13Сложные структуры данных. Связные списки, слайд №14Сложные структуры данных. Связные списки, слайд №15Сложные структуры данных. Связные списки, слайд №16Сложные структуры данных. Связные списки, слайд №17Сложные структуры данных. Связные списки, слайд №18Сложные структуры данных. Связные списки, слайд №19Сложные структуры данных. Связные списки, слайд №20Сложные структуры данных. Связные списки, слайд №21Сложные структуры данных. Связные списки, слайд №22Сложные структуры данных. Связные списки, слайд №23Сложные структуры данных. Связные списки, слайд №24Сложные структуры данных. Связные списки, слайд №25Сложные структуры данных. Связные списки, слайд №26Сложные структуры данных. Связные списки, слайд №27Сложные структуры данных. Связные списки, слайд №28Сложные структуры данных. Связные списки, слайд №29Сложные структуры данных. Связные списки, слайд №30Сложные структуры данных. Связные списки, слайд №31Сложные структуры данных. Связные списки, слайд №32Сложные структуры данных. Связные списки, слайд №33Сложные структуры данных. Связные списки, слайд №34Сложные структуры данных. Связные списки, слайд №35Сложные структуры данных. Связные списки, слайд №36Сложные структуры данных. Связные списки, слайд №37Сложные структуры данных. Связные списки, слайд №38Сложные структуры данных. Связные списки, слайд №39Сложные структуры данных. Связные списки, слайд №40Сложные структуры данных. Связные списки, слайд №41Сложные структуры данных. Связные списки, слайд №42Сложные структуры данных. Связные списки, слайд №43Сложные структуры данных. Связные списки, слайд №44Сложные структуры данных. Связные списки, слайд №45
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Сложные структуры данных. Связные списки. Доклад-сообщение содержит 45 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Сложные структуры данных Связные списки
Описание слайда:
Сложные структуры данных Связные списки

Слайд 2


Сложные структуры данных. Связные списки, слайд №2
Описание слайда:

Слайд 3


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

Слайд 4


Недостатки связного списка Недостатком связного списка, как и других структур типа «список», в сравнении его с массивом, является отсутствие возможности работать с данными в режиме произвольного доступа, т. е. список – структура последовательно доступа, в то время как массив – произвольного.
Описание слайда:
Недостатки связного списка Недостатком связного списка, как и других структур типа «список», в сравнении его с массивом, является отсутствие возможности работать с данными в режиме произвольного доступа, т. е. список – структура последовательно доступа, в то время как массив – произвольного.

Слайд 5


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

Слайд 6


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

Слайд 7


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

Слайд 8


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

Слайд 9


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

Слайд 10


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

Слайд 11


Управление памятью Для создания и использования динамических структур требуется динамическое распределение памяти — возможность получения памяти для хранения новых узлов и освобождать память для удаления узлов.
Описание слайда:
Управление памятью Для создания и использования динамических структур требуется динамическое распределение памяти — возможность получения памяти для хранения новых узлов и освобождать память для удаления узлов.

Слайд 12


Сложные структуры данных. Связные списки, слайд №12
Описание слайда:

Слайд 13


Сложные структуры данных. Связные списки, слайд №13
Описание слайда:

Слайд 14


Сложные структуры данных. Связные списки, слайд №14
Описание слайда:

Слайд 15


#include <stdlib.h> #include <stdlib.h> struct node { int x; struct node *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; }
Описание слайда:
#include <stdlib.h> #include <stdlib.h> struct node { int x; struct node *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; } }
Описание слайда:
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


/* Создаёт новый узел в конце */ /* Создаёт новый узел в конце */ conductor->next = malloc( sizeof(struct node) ); conductor = conductor->next; if ( conductor == NULL ) { printf("Не хватает памяти!\n"); return 0; } /* инициализируем память */ conductor->next = NULL; conductor->x = 42; return 0; }
Описание слайда:
/* Создаёт новый узел в конце */ /* Создаёт новый узел в конце */ 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; conductor = root; if ( conductor != NULL ) { /*убедимся, что существует место старта*/ while ( conductor->next != NULL ) { printf( "%d\n", conductor->x); conductor = conductor->next; } printf( "%d\n", conductor->x ); }
Описание слайда:
conductor = root; 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; conductor = root; while ( conductor != NULL ) { printf( "%d\n", conductor->x ); conductor = conductor->next; }
Описание слайда:
conductor = root; conductor = root; while ( conductor != NULL ) { printf( "%d\n", conductor->x ); conductor = conductor->next; }

Слайд 20


Очистка памяти struct node *temp; temp = root->ptr; free(root); /* освобождение памяти текущего корня*/ root = temp; // новый корень списка
Описание слайда:
Очистка памяти struct node *temp; temp = root->ptr; free(root); /* освобождение памяти текущего корня*/ root = temp; // новый корень списка

Слайд 21


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

Слайд 22


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

Слайд 23


Стек Реализация 1 на основе массива Для реализации стека, состоящего не более чем из 100  чисел, следует определить массив, состоящий из 100  элементов и целую переменную, указывающую на вершину стека (ее значение будет также равно текущему числу элементов в стеке) int stack[100], n=0;
Описание слайда:
Стек Реализация 1 на основе массива Для реализации стека, состоящего не более чем из 100  чисел, следует определить массив, состоящий из 100  элементов и целую переменную, указывающую на вершину стека (ее значение будет также равно текущему числу элементов в стеке) int stack[100], n=0;

Слайд 24


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

Слайд 25


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

Слайд 26


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

Слайд 27


Очередь
Описание слайда:
Очередь

Слайд 28


Очередь реализация Для реализации очереди необходимо знать первый и последний элемент находящийся в ней. Например, для реализации стандартной очереди из менее чем 100 целых чисел определить следующие данные #define N 100 int array[N], begin=0,end=0; Соответственно при добавлении элементов в очередь переменная end будет увеличиваться, а при изъятии их из очереди увеличиваться будет begin.
Описание слайда:
Очередь реализация Для реализации очереди необходимо знать первый и последний элемент находящийся в ней. Например, для реализации стандартной очереди из менее чем 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, *right; }; здесь указатель prev указывает на родительский элемент данной вершины, а left и right – на двух потомков, которых традиционно называют левым и правым. Величина value называется ключом вершины.
Описание слайда:
Бинарное дерево реализация struct STree{ int value; struct STree *prev; struct STree *left, *right; }; здесь указатель prev указывает на родительский элемент данной вершины, а left и right – на двух потомков, которых традиционно называют левым и правым. Величина value называется ключом вершины.

Слайд 31


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

Слайд 32


Дерево поиска Поиск элемента 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 *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); };

Слайд 33


Дерево поиска Добавление элемента struct STree *Insert(struct STree *root, struct 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); };
Описание слайда:
Дерево поиска Добавление элемента struct STree *Insert(struct STree *root, struct 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


Дерево поиска
Описание слайда:
Дерево поиска

Слайд 36


Дерево поиска
Описание слайда:
Дерево поиска

Слайд 37


Сложные структуры данных. Связные списки, слайд №37
Описание слайда:

Слайд 38


Сложные структуры данных. Связные списки, слайд №38
Описание слайда:

Слайд 39


Сложные структуры данных. Связные списки, слайд №39
Описание слайда:

Слайд 40


Сложные структуры данных. Связные списки, слайд №40
Описание слайда:

Слайд 41


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

Слайд 42


Аргументы командной строки
Описание слайда:
Аргументы командной строки

Слайд 43


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

Слайд 44


Аргументы командной строки #include <stdio.h> int main(int argc, char *argv[]){ if(argc > 1) { printf("Вы ввели много чего"); } printf("Но это точно имя этой программы: %s", argv[0]); return 0; }
Описание слайда:
Аргументы командной строки #include <stdio.h> int main(int argc, char *argv[]){ if(argc > 1) { printf("Вы ввели много чего"); } printf("Но это точно имя этой программы: %s", argv[0]); return 0; }

Слайд 45


Аргументы командной строки
Описание слайда:
Аргументы командной строки

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию