Файл: Динамические структуры данных (списки).pdf

Например, давайте объявим динамическую структуру данных с именем Node с полями Name, Value и Next, выделим память для указателя на структуру, назначим значения элементам структуры и освободим память.

{ *;

;

*

};

*; //объявляется

= ; //выделяется

-> = ""; //присваиваются значения

-> = ;

-> = ;

; // освобождение

ГЛАВА 2. СПИСКИ

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

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

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

2.1 Линейный список

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

Рисунок 3

Каждый элемент также ссылку следующий за элемент. У последнего списке элемента ссылки содержит . Чтобы потерять список, должны где- (в переменной) адрес его узла – он «головой» списка. В надо объявить новых типа – узел списка указатель на . Узел представляет собой , которая содержит поля - строку, число и на такой узел. Правилами языка Си объявление

{

[40]; // данных

;

*; // ссылка следующий узел

};

*; // тип данных: на узел

В мы будем , что указатель на начало , то есть, в виде

= ;

Первая «» в названии происходит от – указатель (.) В начале работы списке нет одного элемента, в указатель нулевой адрес .

2.2 Создание элемента списка

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

( [] )

{

= ; // указатель новый узел

(->, ); // записать

-> = 1; // слов = 1

-> = ; // следующего узла

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

}

После узел надо к списку ( начало, в или в ).

2.3 Добавление узла

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

При добавлении узла в списка надо ) установить ссылку на голову списка и ) установить голову на новый .

Рисунок 4

По этой схеме работает процедура AddFirst. Предполагается, что адрес начала списка хранится в Head. Важно, что здесь и далее адрес начала списка передается по ссылке, поскольку при добавлении нового узла он изменяется в рамках процедуры.

( &, )

{

-> = ;

= ;

}

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

Дан адрес NewNode нового узла и адрес p одного из существующих узлов в списке. Требуется вставить новый узел в список после узла с адресом p. Эта операция выполняется в два этапа:

1) установить связь нового узла с узлом, следующим за данными;

2) установить ссылку этого узла p на NewNode.

Рисунок 5

Последовательность операций менять , потому что сначала поменять у узла , будет потерян следующего узла.

( , )

{

-> = ->;

-> = ;

}

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

Эта схема добавления сложная. Проблема заключается том, что простейшем линейном (он называется , потому что направлены только одну сторону) того, чтобы адрес предыдущего , нужно пройти список сначала.

Задача либо к узла в списка (если узел – первый), к вставке заданного узла.

( &, , )

{

= ;

( == ) {

(, ); // вставка первым узлом

;

}

( && ->!=) // узел, за следует

= ->;

( ) // если такой узел,

(, ); // добавить новый него

}

Такая процедура обеспечивает «защиту от дурака»: если указан узел, которого нет в списке, то в конце цикла указатель q равен NULL и ничего не происходит.

Есть еще один интересный метод: если вам нужно вставить новый узел NewNode перед данным узлом p, вставить узел после этого узла, а затем обмениваться данными между узлами NewNode и p. Таким образом, адрес с p фактически будет расположен узлом с новыми данными, а по адресу NewNode - с данными, которые были в узле p, то есть мы решили проблему. Этот метод не будет работать, если адрес нового узла NewNode хранится где-то в программе, а затем используется, так как другие данные будут расположены по этому адресу.

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

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

( &, )

{

= ;

( == ) { // если список ,

(, ); // вставляем первый

;

}

(->) = ->; // ищем элемент

(, );

}

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

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

= ; // с головы

( != ) { // не дошли конца

// делаем -нибудь с

= ->; // переходим следующему узлу

}

2.5 Поиск узла в списке

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

1) начать с заголовка списка;

2) пока текущий элемент существует (указатель не NULL), проверьте требуемое условие и перейдите к следующему элементу;

3) закончить, когда нужный элемент найден или все элементы в списке просмотрены.

Например, следующая функция ищет в списке элемент, соответствующий данному слову (для которого поле слова соответствует указанной строке NewWord), и возвращает его адрес или NULL, если такого узла нет.

( , [])

{

= ;

( && (->, ))

= ->;

;

}

Вернемся к проблеме построения буквенно-частотного словаря. Чтобы добавить новое слово в нужное место (в алфавитном порядке), вам нужно найти адрес узла, перед которым вам нужно вставить новое слово. Это будет первый узел в начале списка, для которого «его» слово окажется «больше», чем новое слово. Следовательно, достаточно просто изменить условие в цикле while в функции Find, учитывая, что функция strcmp возвращает «разность» первого и второго слова.

( , [])

{

= ;

( && ((->, ) > 0))

= ->;

;

}

Эта функция вернет узла, перед надо вставить слово (когда вернет значение), или , слово надо в конец .

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

Теперь можно написать программу, обрабатывает файл . и для него -частотный словарь файле ..

()

{

= , , ;

*, *;

[];

;

= ( ".", "" );

( ) {

= ( , "%", ); // слово из

( <= ) ;

= ( , ); // ищем слово списке

( != ) // если нашли ,

-> ++; // счетчик

{

= ( ); // создаем узел

= ( , ); // ищем место

( ! )

( , );

( , , );

}

}

();

= ( ".", "" );

= ;

( ) { // проход по и вывод

( , "%-\%\", ->, -> );

= ->;

}

();

}

В переменной n хранится значение, возвращаемое функцией fscanf (количество успешно прочитанных элементов). Если это число меньше единицы (чтение не удалось или данные в файле закончились), выйдите из цикла while.

Сначала мы пытаемся найти это слово в списке, используя функцию поиска. Если найдено, просто увеличьте счетчик найденного узла. Если слово встречается впервые, новый узел создается в памяти и заполняется данными. Затем, используя функцию FindPlace, мы определяем, перед каким узлом списка нам нужно его добавить.

Когда список будет готов, откройте файл для вывода и, используя стандартный проход по списку, отобразите найденные слова и значения счетчиков.

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

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

Рисунок 6

Отдельно случай, когда первый элемент . При удалении узла память, которую занимал. Отдельно рассматриваем , когда удаляется элемент списка. В случае адрес узла совпадает адресом головы и надо записать в следующего элемента.

( &, )

{

= ;

( == )

= ->; // удаляем первый

{

( && -> != ) // элемент

= ->;

( == ) ; // если нашли, выход

-> = ->;

}

; // освобождаем память

}

2.8 Барьеры

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

2.9 Двусвязный список

Многие проблемы при с односвязным вызваны тем, в них перейти к элементу. Возникает естественная – хранить в ссылку не на следующий, и на элемент списка. Для к списку не одна -указатель, а – ссылка на «» списка () и «хвост» - последний ().

Рисунок 7

Каждый узел (кроме полезных ) также ссылку следующий за узел (поле ) и предыдущий ( ). Поле последнего элемента поле первого содержат . Узел так:

{

[40]; // данных

;

*, *; // на соседние

};

*; // тип «указатель на »

В дальнейшем мы считать, что указывает на списка, а – на конец :

= , = ;

Для пустого списка указателя равны .

2.10 Операции с двусвязным списком

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

При нового узла начало списка

1) установить узла голову существующего и его в ;

) установить ссылку бывшего первого (если он ) на ;

3) голову списка новый узел;

) если в не было одного элемента, списка также на новый .

Рисунок 8

По такой работает следующая :

( &, &, )

{

-> = ;

-> = ;

( ) -> = ;

= ;

( ! ) = ; // этот элемент –

}

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

Из-за симметрии добавление нового узла NewNode в конец списка полностью аналогично, в процедуре вы всегда должны заменить Head на Tail и наоборот, а также изменить prev и next.

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

Дан адрес NewNode нового узла и адрес p одного из существующих узлов в списке. Вам нужно вставить новый узел в список после p. Если узел p является последним, то операция сводится к добавлению в конец списка (см. Выше). Если узел p не последний, то операция вставки выполняется в два этапа:

1) установить ссылки нового узла на следующий следующий (следующий) и предыдущий (предыдущий);

2) установить ссылки соседних узлов для включения NewNode в список.

Этот метод реализуется с помощью следующей процедуры (он также учитывает возможность вставки элемента в конец списка; для этого в параметрах передаются ссылки на начало и конец списка):

Рисунок 9

( &, &,

, )

{

( ! -> )

(, , ); // в конец