Слайд 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();
}
Слайд 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("
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
- Динамические структуры данных
",">
> "); struct Node2 * ptr = first; while" alt="Вывод списка void printList() { printf(">> "); struct Node2 * ptr = first; while (ptr != NULL) { printf("(%d) -> ",">
data); ptr = ptr->prev; } printf("NULL\n");}" alt="Вывод списка от конца в начало void printListRev() { printf(" ", ptr->data); ptr = ptr->prev; } printf("NULL\n");}">
