Динамические списки

Содержание

Слайд 2

План

Лекция 20

План
Динамические списки
Динамические структуры данных
Списки: состав функций
Создание, добавление, поиск, удаление узлов
Решение задач

План Лекция 20 План Динамические списки Динамические структуры данных Списки: состав функций
с использованием списков

Слайд 3

Динамические списки

Динамические структуры данных
Списки: состав функций
Создание, добавление, поиск, удаление узлов
Решение задач с

Динамические списки Динамические структуры данных Списки: состав функций Создание, добавление, поиск, удаление
использованием списков

Слайд 4

Организация курса

Динамические структуры данных

Строение: набор узлов, объединенных с помощью ссылок.
Как устроен узел:

Типы

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

списки

деревья

графы

односвязный

двунаправленный (двусвязный)

циклические списки (кольца)

Слайд 5

Организация курса

Когда нужны списки?

Задача (алфавитно-частотный словарь). В файле записан текст. Нужно записать

Организация курса Когда нужны списки? Задача (алфавитно-частотный словарь). В файле записан текст.
в другой файл в столбик все слова, встречающиеся в тексте, в алфавитном порядке, и количество повторений для каждого слова.
Проблемы:
количество слов заранее неизвестно (статический массив);
количество слов определяется только в конце работы (динамический массив).
Решение – список.
Алгоритм:
создать список;
если слова в файле закончились, то стоп.
прочитать слово и искать его в списке;
если слово найдено – увеличить счетчик повторений, иначе добавить слово в список;
перейти к шагу 2.

Слайд 6

Организация курса

Что такое список:
пустая структура – это список;
список – это начальный узел

Организация курса Что такое список: пустая структура – это список; список –
(голова) и связанный с ним список.

Списки: новые типы данных

Структура узла:

struct Node {
char word[40]; // слово
int count; // счетчик повторений
Node *next; // ссылка на следующий элемент
};

typedef Node *PNode;

Указатель на эту структуру:

Адрес начала списка:

PNode Head = NULL;

Слайд 7

Организация курса

Что нужно уметь делать со списком?

Создать новый узел.
Добавить узел:
в начало списка;
в

Организация курса Что нужно уметь делать со списком? Создать новый узел. Добавить
конец списка;
после заданного узла;
до заданного узла.
Искать нужный узел в списке.
Удалить узел.

Слайд 8

Организация курса

Создание узла

PNode CreateNode ( char NewWord[] )
{
PNode NewNode = new

Организация курса Создание узла PNode CreateNode ( char NewWord[] ) { PNode
Node;
strcpy(NewNode->word, NewWord);
NewNode->count = 1;
NewNode->next = NULL;
return NewNode;
}

Функция CreateNode (создать узел):
вход: новое слово, прочитанное из файла;
выход: адрес нового узла, созданного в памяти.

возвращает адрес созданного узла

новое слово

Слайд 9

Организация курса

Добавление узла в начало списка

1) Установить ссылку нового узла на голову

Организация курса Добавление узла в начало списка 1) Установить ссылку нового узла
списка:

NewNode->next = Head;

2) Установить новый узел как голову списка:

Head = NewNode;

void AddFirst (PNode * Head, PNode NewNode)
{
NewNode->next = *Head;
*Head = NewNode;
}

адрес головы меняется

*

Слайд 10

Организация курса

Добавление узла после заданного

1) Установить ссылку нового узла на узел, следующий

Организация курса Добавление узла после заданного 1) Установить ссылку нового узла на
за p:

NewNode->next = p->next;

2) Установить ссылку узла p на новый узел:

p->next = NewNode;

void AddAfter (PNode p, PNode NewNode)
{
NewNode->next = p->next;
p->next = NewNode;
}

Слайд 11

Организация курса

Задача:
сделать что-нибудь хорошее с каждым элементом списка.
Алгоритм:
установить вспомогательный указатель q

Организация курса Задача: сделать что-нибудь хорошее с каждым элементом списка. Алгоритм: установить
на голову списка;
если указатель q равен NULL (дошли до конца списка), то стоп;
выполнить действие над узлом с адресом q ;
перейти к следующему узлу, q->next.

Проход по списку

...
PNode q = Head; // начали с головы
while ( q != NULL ) { // пока не дошли до конца
... // делаем что-то хорошее с q
q = q->next; // переходим к следующему узлу
}
...

Слайд 12

Организация курса

Добавление узла в конец списка

Задача: добавить новый узел в конец списка.
Алгоритм:
найти

Организация курса Добавление узла в конец списка Задача: добавить новый узел в
последний узел q, такой что q->next равен NULL;
добавить узел после узла с адресом q (процедура AddAfter).
Особый случай: добавление в пустой список.

void AddLast ( PNode *Head, PNode NewNode )
{
PNode q = *Head;
if ( *Head == NULL ) {
AddFirst( Head, NewNode );
return;
}
while ( q->next ) q = q->next;
AddAfter ( q, NewNode );
}

особый случай – добавление в пустой список

ищем последний узел

добавить узел после узла q

Слайд 13

Организация курса

Проблема: нужно знать адрес предыдущего узла, а идти назад нельзя!
Решение: найти

Организация курса Проблема: нужно знать адрес предыдущего узла, а идти назад нельзя!
предыдущий узел q (проход с начала списка).

Добавление узла перед заданным

void AddBefore ( PNode * Head, PNode p, PNode NewNode )
{
PNode q = *Head;
if ( *Head == p ) {
AddFirst ( Head, NewNode );
return;
}
while ( q && q->next != p ) q = q->next;
if ( q ) AddAfter(q, NewNode);
}

особый случай – добавление в начало списка

ищем узел, следующий за которым – узел p

добавить узел после узла q

Слайд 14

Организация курса

Добавление узла перед заданным (II)

Задача: вставить узел перед заданным без поиска

Организация курса Добавление узла перед заданным (II) Задача: вставить узел перед заданным
предыдущего.
Алгоритм:
поменять местами данные нового узла и узла p;
установить ссылку узла p на NewNode.

void AddBefore2 ( PNode p, PNode NewNode )
{
Node temp;
temp = *p; *p = *NewNode;
*NewNode = temp;
p->next = NewNode;
}

Слайд 15

Организация курса

Поиск слова в списке

Задача: найти в списке заданное слово или определить,

Организация курса Поиск слова в списке Задача: найти в списке заданное слово
что его нет.
Функция Find:
вход: слово (символьная строка);
выход: адрес узла, содержащего это слово или NULL.
Алгоритм: проход по списку.

PNode Find ( PNode Head, char NewWord[] )
{
PNode q = Head;
while (q && strcmp(q->word, NewWord))
q = q->next;
return q;
}

ищем это слово

результат – адрес узла

while ( q && strcmp ( q->word, NewWord) )
q = q->next;

пока не дошли до конца списка и слово не равно заданному

Слайд 16

Организация курса

Куда вставить новое слово?

Задача: найти узел, перед которым нужно вставить, заданное

Организация курса Куда вставить новое слово? Задача: найти узел, перед которым нужно
слово, так чтобы в списке сохранился алфавитный порядок слов.
Функция FindPlace:
вход: слово (символьная строка);
выход: адрес узла, перед которым нужно вставить это слово или NULL, если слово нужно вставить в конец списка.

PNode FindPlace ( PNode Head, char NewWord[] )
{
PNode q = Head;
while ( q && strcmp(NewWord, q->word) > 0 )
q = q->next;
return q;
}

> 0

слово NewWord стоит по алфавиту до q->word

Слайд 17

Организация курса

Удаление узла

void DeleteNode ( Pnode *Head, PNode p )
{
PNode q =

Организация курса Удаление узла void DeleteNode ( Pnode *Head, PNode p )
*Head;
if ( *Head == p )
*Head = p->next;
else {
while ( q && q->next != p )
q = q->next;
if ( q == NULL ) return;
q->next = p->next;
}
delete p;
}

Проблема: нужно знать адрес предыдущего узла q.

особый случай: удаляем первый узел

ищем предыдущий узел, такой что q->next == p

освобождение памяти

Слайд 18

Организация курса

Алфавитно-частотный словарь

Алгоритм:
открыть файл на чтение;
прочитать слово:
если файл закончился (n!=1), то перейти

Организация курса Алфавитно-частотный словарь Алгоритм: открыть файл на чтение; прочитать слово: если
к шагу 7;
если слово найдено, увеличить счетчик (поле count);
если слова нет в списке, то
создать новый узел, заполнить поля (CreateNode);
найти узел, перед которым нужно вставить слово (FindPlace);
добавить узел (AddBefore);
перейти к шагу 2;
вывести список слов, используя проход по списку.

char word[80];
...
n = fscanf ( in, "%s", word );

FILE *in;
in = fopen ( "input.dat", "r" );

read, чтение

вводится только одно слово (до пробела)!

Слайд 19

Организация курса

Двусвязные списки

Структура узла:

struct Node {
char word[40]; // слово
int count;

Организация курса Двусвязные списки Структура узла: struct Node { char word[40]; //
// счетчик повторений
Node *next; // ссылка на следующий элемент
Node *prev; // ссылка на предыдущий элемент
};

typedef Node *PNode;

Указатель на эту структуру:

Адреса «головы» и «хвоста»:

PNode Head = NULL;
PNode Tail = NULL;

Имя файла: Динамические-списки.pptx
Количество просмотров: 190
Количество скачиваний: 1