Презентация - Односвязный и двусвязный список

На весь экран

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

Слайд 1

Основы программирования ФИСТ 1 курс Власенко Олег Федосович
Лекция 13 Односвязный и двусвязный список.

Слайд 2

Динамические структуры данных
«данные особой структуры, которые представляют собой отдельные элементы, связанные с помощью ссылок. Каждый элемент ( узел ) состоит из двух областей памяти: поля данных и ссылок. Ссылки – это адреса других узлов этого же типа, с которыми данный элемент логически связан. В языке Си для организации ссылок используются переменные - указатели. При добавлении нового узла в такую структуру выделяется новый блок памяти и (с помощью ссылок) устанавливаются связи этого элемента с уже существующими. Для обозначения конечного элемента в цепи используются нулевые ссылки (NULL).» http://k504.khai.edu/attachments/article/762/devcpp_4.pdf

Слайд 3

Где и когда нужны динамические структуры данных???

Слайд 4

Динамические структуры данных
Список односвязный Список двусвязный Циклический список Дерево Двоичное дерево Двоичное дерево поиска Графы …

Слайд 5

Еще раз о структурах
struct Line { int x1, y1, x2, y2; }; struct Line newLine = {10, 10, 20, 10}; struct Line * lines = NULL;

Слайд 6

Еще раз о структурах (2)
struct Line { int x1, y1, x2, y2; }; struct Line newLine = {10, 10, 20, 10}; struct Line * lines = NULL; struct Node { int data; struct Node * next; }; struct Node * first = NULL;

Слайд 7

Отрабатываем навыки рисования
void main() { struct Node node1 = {1, NULL}; struct Node node2 = { 2, NULL }; struct Node node3 = { 3, NULL }; first = &node1; node1.next = &node2; node2.next = &node3; printList(); }

Слайд 8

Отрабатываем навыки рисования (2)
void printList() { struct Node * ptr = first; while (ptr != NULL) { printf("(%d) -> ", ptr->data); ptr = ptr->next; } printf("NULL\n"); }

Слайд 9

Связанный список в динамической памяти
#define _CRT_SECURE_NO_WARNINGS #include struct Node { int data; struct Node * next; }; struct Node * first = NULL;

Слайд 10

Связанный список в динамической памяти (2)
void printList() { struct Node * ptr = first; while (ptr != NULL) { printf("(%d) -> ", ptr->data); ptr = ptr->next; } printf("NULL\n"); }

Слайд 11

Связанный список в динамической памяти (3)
void addToHead(int value) { struct Node * newNode; newNode = (struct Node*)malloc(sizeof( struct Node)); newNode->next = first; newNode->data = value; first = newNode; }

Слайд 12

Связанный список в динамической памяти (4)
int deleteFromHead() { int value = first->data; struct Node * delNode = first; first = first->next; free(delNode); return value; }

Слайд 13

Связанный список в динамической памяти (5)
void main() { addToHead(10); printList(); addToHead(20); printList(); addToHead(30); printList();

Слайд 14

Связанный список в динамической памяти (6)
int x1 = deleteFromHead(); printf("x1 = %d\n", x1); printList(); int x2 = deleteFromHead(); printf("x2 = %d\n", x2); printList(); int x3 = deleteFromHead(); printf("x3 = %d\n", x3); printList();

Слайд 15

Связанный список в динамической памяти (7)
int x4 = deleteFromHead(); printf("x4 = %d\n", x4); printList(); }

Слайд 16

И снова – урок рисования
!!!

Слайд 17

Очистка всего списка
void clearList() { while (first != NULL) { struct Node * delNode = first; first = first->next; free(delNode); } } Трассировка!!!

Слайд 18

Защита от пустого списка
int deleteFromHead() { if (first == NULL) { return -1; } int value = first->data; struct Node * delNode = first; first = first->next; free(delNode); return value; }

Слайд 19

Собираем все вместе
void main() { addToHead(10); printList(); clearList(); printList(); addToHead(20); printList(); addToHead(30); printList();

Слайд 20

Собираем все вместе (2)
int x1 = deleteFromHead(); printf("x1 = %d\n", x1); printList(); int x2 = deleteFromHead(); printf("x2 = %d\n", x2); printList(); int x3 = deleteFromHead(); printf("x3 = %d\n", x3); printList(); }

Слайд 21

Вставляем элемент в конец списка
void addToTail(int value) { struct Node * newNode; newNode = (struct Node*)malloc( sizeof(struct Node)); newNode->data = value; newNode->next = NULL;

Слайд 22

Вставляем элемент в конец списка (2)
if (first == NULL) { first = newNode; return; } if (first->next == NULL) { first->next = newNode; return; } struct Node * last = first; while (last->next != NULL) { last = last->next; } last->next = newNode; }

Слайд 23

Вставляем элемент в конец списка (3)
void main() { addToTail(10); printList(); addToTail(20); printList(); addToTail(30); printList(); addToTail(40); printList(); clearList(); printList(); }

Слайд 24

Проверка, есть ли элемент в списке
void main() { addToTail(10); addToTail(20); addToTail(30); addToTail(40); printList(); printf("contains(10) = %d\n", contains(10)); printf("contains(15) = %d\n", contains(15)); printf("contains(20) = %d\n", contains(20)); clearList(); printList(); }

Слайд 25

Проверка, есть ли элемент в списке - код
int contains(int value) { struct Node * ptr = first; while (ptr != NULL) { … } return 0; // если так и не нашли элемента ==value }

Слайд 26

Односвязный список
struct Node { int data; struct Node * next; }; struct Node * first = NULL;

Слайд 27

Двусвязный список
struct Node2 { int data; struct Node2 * next; struct Node2 * prev; }; struct Node2 * first = NULL; struct Node2 * last = NULL;

Слайд 28

Отрабатываем навыки рисования
void main() { struct Node2 node1 = { 1, NULL, NULL }; struct Node2 node2 = { 2, NULL, NULL }; struct Node2 node3 = { 3, NULL, NULL }; first = &node1; node1.next = &node2; node2.next = &node3; last = &node3; node3.prev = &node2; node2.prev = &node1; printList(); printListRev(); }

Слайд 29

Вывод списка
void printList() { printf(">> "); struct Node2 * ptr = first; while (ptr != NULL) { printf("(%d) -> ", ptr->data); ptr = ptr->next; } printf("NULL\n"); }

Слайд 30

Вывод списка от конца в начало
void printListRev() { printf("<< "); struct Node2 * ptr = last; while (ptr != NULL) { printf("(%d) -> ", ptr->data); ptr = ptr->prev; } printf("NULL\n"); }

Слайд 31

Добавление элемента в голову списка
void addToHead(int value) { struct Node2 * newNode = (struct Node2*) malloc(sizeof(struct Node2)); newNode->next = first; newNode->data = value; newNode->prev = NULL; if (first == NULL) { last = newNode; first = newNode; } else { first->prev = newNode; first = newNode; } }

Слайд 32

Добавление элемента в хвост списка
void addToTail(int value) { struct Node2 * newNode = (struct Node2*) malloc(sizeof(struct Node2)); newNode->next = NULL; newNode->data = value; newNode->prev = last; if (last == NULL) { first = newNode; last = newNode; } else { last->next = newNode; last = newNode; } }

Слайд 33

Пример добавления элементов в список
void main() { addToHead(10); addToHead(20); addToHead(30); addToHead(40); addToTail(110); addToTail(120); addToTail(130); addToTail(140); printList(); printListRev(); } Что будет выведено???

Слайд 34

Пример добавления элементов в список
void main() { addToHead(10); addToHead(20); addToHead(30); addToHead(40); addToTail(110); addToTail(120); addToTail(130); addToTail(140); printList(); printListRev(); }

Слайд 35

Очистка списка
void clearList() { while (first != NULL) { struct Node2 * delNode = first; first = first->next; free(delNode); } last = NULL; }

Слайд 36

Список содержит элемент?
int contains(int value) { struct Node2 * ptr = first; while (ptr != NULL) { if (ptr->data == value) { return 1; } ptr = ptr->next; } return 0; }

Слайд 37

Вызов clearList() и contains()
void main() { addToHead(10); addToHead(20); addToHead(30); addToHead(40); printList(); printListRev(); printf("contains(10) = %d\n", contains(10)); printf("contains(15) = %d\n", contains(15)); printf("contains(20) = %d\n", contains(20)); clearList(); printList(); printListRev(); }

Слайд 38

Удаление элемента из головы
int deleteFromHead() { if (first == NULL) { return -1; } int value = first->data; struct Node2 * delNode = first;

Слайд 39

Удаление элемента из головы (2)
if (first == last) { first = NULL; last = NULL; free(delNode); } else { first = first->next; first->prev = NULL; free(delNode); } return value; }

Слайд 40

Удаление элемента из хвоста (1)
int deleteFromTail() { if (last == NULL) { return -1; } int value = last->data; struct Node2 * delNode = last;

Слайд 41

Удаление элемента из хвоста (2)
if (first == last) { first = NULL; last = NULL; free(delNode); } else { last = last->prev; last->next = NULL; free(delNode); } return value; }

Слайд 42

Тестирование удаления
void main() { addToHead(10); addToHead(20); addToHead(30); addToHead(40); printList(); printListRev(); int x1 = deleteFromHead(); printf("deleteFromHead(): x1 = %d\n", x1); printList(); printListRev();

Слайд 43

Тестирование удаления (2)
int x2 = deleteFromTail(); printf("deleteFromTail(): x2 = %d\n", x2); printList(); printListRev(); int x3 = deleteFromHead(); printf("deleteFromHead(): x3 = %d\n", x3); printList(); printListRev(); }

Слайд 44

Домашнее задание
Делайте текущие лабораторные работы и сдавайте домашние работы! Читайте про списки – см следующий слайд!

Слайд 45

Источники информации
http://www.intuit.ru/studies/courses/648/504/lecture/11456 - Динамические структуры данных: однонаправленные и двунаправленные списки http://k504.khai.edu/attachments/article/762/devcpp_4.pdf - Динамические структуры данных