Основы программирования для автоматизированного проектирования и решения творческих задач. Романенко А.В - 27 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

се работы программы. Наиболее удобной базой для их построения стали структуры. Оказалось, что возможность использо-
вания в составе структур указателей того же типа, что и сам структурный тип, связана с целым рядом новых свойств. На их
основе строятся динамические структуры данных: списки, буферы, стеки, деревья.
12.1 Однонаправленный линейный список
Рассмотрим, какой эффект можно получить от включения в состав структуры указателя на саму структуру:
struct lSp
{
struct lSP *next;
int key;
};
Определим в программе два указателя вышеописанного типа:
struct lSp *first, *other;
Создадим в основной памяти ЭВМ, не занятой нашей программой, ячейку памяти типа lSp и запомним ее адрес в указа-
теле first, а в поле next этой ячейки запишем NULL:
first = (struct lSp *) malloc(sizeof(struct lSp));
first->next = NULL;
Таким образом, появилась новая ячейка памяти, которая не занимает область сегмента данных программы, а вынесена в
свободную память компьютера, называемую кучей.
Далее мы можем создать неограниченное количество подобных ячеек, каждая из которых будет хранить свою инфор-
мацию. Для того, чтобы программа не потеряла связь с этими ячейками, необходимо объединить их в цепочку. В этом случае
наша программа может обойтись всего двумя указателями для работы с созданным списком: указатель first будет помнить
адрес первой ячейки в списке, а указатель other, переходя от ячейки к ячейке, может быть настроен на любую из них. Окон-
чание списка показывает ячейка, у которой в поле next находится значение NULL. Созданный таким образом список носит
название однонаправленного линейного списка. Процесс его создания приведен в примере 24, а устройство показано ни рис.
10.
П р и м е р 24
other = first;
while (other->next != NULL) other = other->next;
other->next = (struct lSp *) malloc(sizeof(struct lSp));
other = other->next;
other->next = NULL;
scanf("%d", &other->key);
Рис. 10 Устройство однонаправленного списка
Наиболее распространенными операциями, применяемыми к элементам динамических структур данных, являются по-
иск элемента по некоторому ключевому полю, добавление нового элемента в список и удаление элемента по ключевому зна-
чению. Рассмотрим эти действия применительно к однонаправленному линейному списку.
Поиск элемента осуществляется последовательным перебором элементов списка, начиная с первого, до тех пор, пока
нужный элемент не будет обнаружен или не закончатся элементы в списке.
П р и м е р 25
int key;
scanf("%d", &key);
other = first;
while (other != NULL && key != other->key) other = other->next;
Добавление элемента в уже созданный список. Для осуществления этой операции необходимо установить в списке ме-
сто расположения элемента, после которого планируется осуществить вставку нового элемента. После этого создается новая
ячейка памяти (отдельно от списка). В поле next данной ячейки заносим содержимое поля next ячейки из списка, после кото-
рой будет осуществлена вставка, а сама ячейка из списка должна запомнить адрес новой ячейки. После осуществления этих
действий новая ячейка окажется встроенной внутрь списка.

Страницы