Алгоритмические языки и программирование

Сентябрь 7, 2022

Главная
Алгебра
Алгоритмические языки и программирование

Содержание

2. Сложные структуры данных Связные списки
3. Часть 1
4. Структуры, ссылающиеся на себя struct node { int x; struct node *next; };
5. Связный список Структура данных, представляющая собой конечное множество упорядоченных элементов (узлов), связанных друг с другом посредством
6. Недостатки связного списка Недостатком связного списка, как и других структур типа «список», в сравнении его с
7. Односвязный список Каждый узел односвязного (однонаправленного связного) списка содержит указатель на следующий узел. Из одной точки
8. Односвязный список Каждый узел однонаправленного (односвязного) линейного списка (ОЛС) содержит одно поле указателя на следующий узел.
9. Односвязный список Основные действия, производимые над элементами ОЛС: Инициализация списка Добавление узла в список Удаление узла
10. Инициализация ОЛС Инициализация списка предназначена для создания корневого узла списка, у которого поле указателя на следующий
11. Добавление узла в ОЛС Функция добавления узла в список принимает два аргумента: Указатель на узел, после
12. Добавление узла в ОЛС Процедуру добавления узла можно отобразить следующей схемой:
13. Добавление узла в ОЛС Добавление узла в ОЛС включает в себя следующие этапы: создание добавляемого узла
14. Добавление узла в ОЛС Таким образом, функция добавления узла в ОЛС имеет вид: struct list *
15. Удаление узла ОЛС В качестве аргументов функции удаления элемента ОЛС передаются указатель на удаляемый узел, а
16. Удаление узла ОЛС Удаление узла может быть представлено следующей схемой: Удаление узла ОЛС включает в себя
17. Удаление узла ОЛС struct list * deletelem(list *lst, list *root) { struct list *temp; temp =
18. Удаление корня списка Функция удаления корня списка в качестве аргумента получает указатель на текущий корень списка.
19. Вывод элементов списка В качестве аргумента в функцию вывода элементов передается указатель на корень списка. Функция
20. Лабораторные работы
22. Скачать презентацию

Слайд 2

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

Слайд 3

Часть 1

Слайд 4

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

Слайд 5

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

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

Слайд 6

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

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

Слайд 7

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

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

Слайд 8

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

указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL).
Узел ОЛС можно представить в виде структуры

typedef struct list { int field; // поле данных struct list *ptr; // указатель на следующий элемент } list;

Слайд 9

Односвязный список
Основные действия, производимые над элементами ОЛС:
Инициализация списка
Добавление узла в список
Удаление

узла из списка
Удаление корня списка
Вывод элементов списка

Слайд 10

Инициализация ОЛС
Инициализация списка предназначена для создания корневого узла списка, у которого

поле указателя на следующий элемент содержит нулевое значение.

struct list * init(int a) // а- значение первого узла { struct list *lst; // выделение памяти под корень списка lst = (struct list*)malloc(sizeof(struct list)); lst->ptr = NULL; // это последний узел списка
lst->field = a; return(lst); }

Слайд 11

Добавление узла в ОЛС
Функция добавления узла в список принимает два аргумента:
Указатель

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

Слайд 12

Добавление узла в ОЛС
Процедуру добавления узла можно отобразить следующей схемой:

Слайд 13

Добавление узла в ОЛС
Добавление узла в ОЛС включает в себя следующие

этапы:
создание добавляемого узла и заполнение его поля данных;
переустановка указателя узла, предшествующего добавляемому, на добавляемый узел;
установка указателя добавляемого узла на следующий узел (тот, на который указывал предшествующий узел).

Слайд 14

Добавление узла в ОЛС
Таким образом, функция добавления узла в ОЛС имеет

вид:

struct list * addelem(list *lst, int number) { struct list *temp, *p; temp = (struct list*)malloc(sizeof(list)); p = lst->ptr; // сохранение указателя на следующий узел lst->ptr = temp; // предыдущий узел указывает на создаваемый temp->field = number; // сохранение поля данных добавляемого узла temp->ptr = p; // созданный узел указывает на следующий элемент return(temp); }

Возвращаемым значением функции является адрес добавленного узла.

Слайд 15

Удаление узла ОЛС
В качестве аргументов функции удаления элемента ОЛС передаются указатель

на удаляемый узел, а также указатель на корень списка.
Функция возвращает указатель на узел, следующий за удаляемым.

Слайд 16

Удаление узла ОЛС
Удаление узла может быть представлено следующей схемой:
Удаление узла ОЛС

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

Слайд 17

Удаление узла ОЛС
struct list * deletelem(list lst, list root) { struct list *temp; temp = root; while (temp->ptr != lst) // просматриваем список начиная с корня { // пока не найдем

узел, предшествующий lst temp = temp->ptr; } temp->ptr = lst->ptr; // переставляем указатель free(lst); // освобождаем память удаляемого узла return(temp); }

Реализация удаления элемента ОЛС:

Слайд 18

Удаление корня списка
Функция удаления корня списка в качестве аргумента получает указатель

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

struct list * deletehead(list *root) { struct list *temp; temp = root->ptr; free(root); // освобождение памяти текущего корня return(temp); // новый корень списка }

Слайд 19

Вывод элементов списка
В качестве аргумента в функцию вывода элементов передается указатель

на корень списка. Функция осуществляет последовательный обход всех узлов с выводом их значений.

void listprint(list *lst) { struct list *p; p = lst; do { printf("%d ", p->field); // вывод значения элемента p p = p->ptr; // переход к следующему узлу } while (p != NULL); }

Слайд 20

Алгоритмические языки и программирование

Содержание

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

Часть 1

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

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

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

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

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

Односвязный списокОсновные действия, производимые над элементами ОЛС:Инициализация спискаДобавление узла в списокУдаление

Инициализация ОЛСИнициализация списка предназначена для создания корневого узла списка, у которого

Добавление узла в ОЛСФункция добавления узла в список принимает два аргумента:Указатель

Добавление узла в ОЛСПроцедуру добавления узла можно отобразить следующей схемой:

Добавление узла в ОЛСДобавление узла в ОЛС включает в себя следующие

Добавление узла в ОЛСТаким образом, функция добавления узла в ОЛС имеет

Удаление узла ОЛСВ качестве аргументов функции удаления элемента ОЛС передаются указатель

Удаление узла ОЛСУдаление узла может быть представлено следующей схемой:Удаление узла ОЛС

Удаление узла ОЛСstruct list * deletelem(list *lst, list *root) { struct list *temp; temp = root; while (temp->ptr != lst) // просматриваем список начиная с корня { // пока не найдем

Удаление корня спискаФункция удаления корня списка в качестве аргумента получает указатель

Вывод элементов спискаВ качестве аргумента в функцию вывода элементов передается указатель

Лабораторные работы

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