Язык Си. Реализация списков с помощью цепочек динамических объектов (А.А. Вылиток - Лекции)

А. А. ВылитокЯзык Си. Реализация списков с помощью цепочекдинамических объектовВ языке Си нет встроенных типов данных и операций для работы со списками.Программируя на языке Паскаль (в котором также нет стандартных типов для списков),мы представляли списки цепочками динамических объектов. Аналогичная реализациявозможна и в языке Си.1. Стандартные функции для работы с динамической памятьюДля работы с динамическим объектами в Си есть аналоги паскалевскиxпроцедур new и dispose — это функции стандартной библиотеки malloc и free. Для ихиспользования нужно включить в программу заголовочный файл ‹stdlib.h›. В этомфайле также вводится обозначение NULL для пустого (нулевого) указателя.void *malloc (size_t size)malloc возвращает указатель на место в памяти для объекта размера size.Выделенная память не инициализируется.

Если память отвести не удалось, торезультат работы функции — NULL. (Тип size_t — это беззнаковый целый тип,определяемый в файле ‹stddef.h›, результат операции sizeof имеет тип size_t). Какправило, обобщенный указатель, возвращаемый этой функцией, явноприводится к указателю на тип данных. Например, создать динамическуюпеременную типа double и присвоить значение, возвращаемое malloc,переменной dp — указателю на double, можно с помощью выраженияdp = (double*) malloc (sizeof (double)).Созданная динамическая переменная существует вплоть до завершения работыпрограммы, или до момента, когда она явно уничтожается с помощью функцииfree.void free (void *p)free освобождает область памяти, на которую указывает p; если p равно NULL,то функция ничего не делает.

Значение p должно указывать на область памяти,ранее выделенную с помощью функций malloc или calloc После освобожденияпамяти результат разыменования указателя p непредсказуем; результат такженепредсказуем при попытке повторного обращения к free c этим же указателем.Приведем описание еще одной функции распределения памяти в Си. Ею удобнопользоваться, когда нужно разместить массив в динамической памяти.void *calloc (size_t nobj, size_t size)calloc возвращает указатель на место в памяти, отведенное для массива nobjобъектов, каждый из которых имеет размер size. Выделенная область памятипобитово обнуляется.

(Заметим, что это не всегда равнозначно присваиваниюнулевых значений соответствующим элементам массива. В некоторыхреализациях в побитовом представлении нулевого указателя или значения 0.0 сплавающей точкой могут быть ненулевые биты). Если память отвести неудалось, то результат работы функции — NULL.2. Представление списков цепочками звеньевДля хранения отдельного элемента списка создается динамический объект —структура с двумя членами, называемая звеном.

В одном из членов (информационном)располагается сам элемент, а другой член содержит указатель на звено, содержащееследующий элемент списка, или пустой указатель, если следующего элемента нет. Спомощью указателей звенья как бы сцеплены в цепочку. Зная указатель на первое звеноможно добраться и до остальных звеньев, то есть указатель на первое звено задаёт весьсписок. Пустой список представляется пустым указателем.Приведём соответствующие описания на языке Си. В качестве типа элементасписка выбран тип char. Списки с элементами других типов описываются аналогично.#include <stdio.h>#include <stdlib.h>typedef struct Node *link;typedef char elemtype;/* указатель на звено/* тип элемента списка*/*/typedef struct Node {elemtype elem;link next;} node;/* звено состоит из двух полей:/* – элемент списка,/* – указатель на следующее звено*/*/*/typedef link list;/* список задается указателем на звено */list lst;/* переменная типа список*/Переменная lst представляет в программе список.Обратите внимание на то, что в описании типа link используется незавершенныйтип struct Node.

Описание указателей на незавершенный тип допустимо в Си. Тип structNode становится завершенным при описании типа node. Тип list объявляетсясинонимом типа link.В примерах мы будем обозначать обсуждаемые списки в виде кортежей, как этопринято в математике. Так, конструкция 〈'a', 'b', 'c'〉 означает список из трех элементов.Первый элемент в этом списке — 'a', второй — 'b', третий — 'c'. Пустой списоквыглядит так 〈 〉.Пример. Список символов 〈'a', 'b', 'c'〉, представленный цепочкой звеньев,изображается следующим образом (в переменной lst — указатель на первое звено):lst'a''b''c'NULLПри этом в программе выражение lst означает указатель на первое звено в цепочке; *lstозначает само первое звено, (*lst).elem — первый элемент списка. По-другому первыйэлемент обозначается с помощью операции доступа к члену структуры через указатель:lst−>elem.

Выражение lst−>next означает указатель на второе звено. Далее,*lst−>next— само второе звено,lst−>next−>elem— второй элемент списка,lst−>next−>next— указатель на третье звено,*lst–>next−>next— само третье звено,lst−>next−>next−>elem — третий элемент списка,lst−>next−>next−>next — пустой указатель (конец списка).Выражение lst имеет и другой смысл. Оно обозначает список в программе,поскольку, зная указатель на первое звено, мы имеем доступ ко всем остальнымзвеньям, т.е. «знаем» весь список. С этой точки зрения выражение lst−>next в нашемпримере обозначает список1 〈'b', 'c'〉, а выражение lst−>next−>next−>next — пустойсписок.Заметим, что соседние звенья цепочки располагаются в оперативной памятипроизвольно относительно друг друга, в отличие от соседних компонент массива,всегда занимающих смежные участки памяти.

Такое расположение звеньев облегчаетоперации вставки и удаления, так как нет необходимости перемещать элементы, как этобыло бы в случае реализации списков массивами. Поясним это на примерах.Пусть из списка 〈'a', 'b', 'c'〉, представленного в программе переменной lst,требуется удалить второй элемент. Для этого достаточно исключить из цепочки второезвено – «носитель» второго элемента. Изменим указатель в поле next первого звена:lst−>next = lst−>next−>next.Теперь после первого звена в цепочке идёт звено, содержащее элемент 'c'.Получился список 〈'a', 'c'〉. Чтобы исключённое звено не занимало места в памяти, егоследует уничтожить с помощью функции free, предварительно запомнив указатель нанего во вспомогательной переменной q.

Итак, окончательное решение таково:q = lst−>next; lst−>next = lst−>next−>next; free(q);Покажем на рисунке происходящие после каждого действия изменения.1По правилам языка Си имена link и list обозначают один и тот же тип, и мы вправе рассматриватьlst−>next как переменную типа list, означающую список.q = lst–>next;'a'lst'b''c'NULL'c'NULLqlst–>next = lst–>next–>next;'a'lst'b'qfree(q);lst'a''c'NULLqПусть теперь требуется вставить 'd' после первого элемента списка 〈'a', 'c'〉.Решение состоит из двух этапов.

Во-первых, необходимо создать «носитель» — звенодля хранения вставляемого элемента, и занести этот элемент в поле elem «носителя».Во-вторых, путём изменения указателей включить созданное звено в цепочку послепервого звена. Первый этап реализуется фрагментомq = (link) malloc(sizeof (node)); q−>elem = 'd';где q — вспомогательная переменная типа link. Фрагментq−>next = lst−>next; lst−>next = q;осуществляет второй этап вставки.

Следующий рисунок иллюстрирует этапы вставки.q = (link) malloc(sizeof (node)); q−>elem = 'd';lstq'a''c'NULL'd'q–>next = lst–>next; lst–>next = q;lstq'a''c'NULL'd'Из примеров видно, что длина цепочки (количество звеньев в ней) можетдинамически изменяться, т.е. изменяться в процессе выполнения программы. Подобноцепочкам можно сконструировать и более сложные структуры, в которых объектысвязаны между собой с помощью указателей. Такого рода структуры данныхназываются динамическими.3.

Некоторые операции со спискамиПриведём описание нескольких функций для работы со списками.Создание спискаФункция create (s) создает и возвращает в качестве результата список изсимволов параметра-строки s.list create (char *s){int i;link cur;/* указатель на текущее звено спискаlist res;/* возвращаемый списокif ( *s == '\0' ) return NULL; /* если строка пуста, то возвращаемпустой списокиначе строим непустой списокres = cur = ( link ) malloc ( sizeof (node)); /* создаем первое звено спискаcur−>elem = *s++;/* заполняем поле elem и переходим к*/*/*/*/следующему элементу строки*/while ( *s != '\0' ) {/* пока не конец строки*/cur = cur−>next = (list) malloc( sizeof (node)); /* присоединяем в конецсписка новое звено*/cur−>elem = *s++;/* помещаем в новое звено очередной элементи переходим к следующему элементустроки*/}cur−>next = NULL;/* последнее звено должно иметь нулевойуказатель*/return res;/* возвращаем список (указатель на первоезвено)*/}Условие *s != '\0' можно заменить на *s, а *s == '\0' заменить на !*s .Печать элементов списка/* print: печатает в стандартный выходной поток элементы спискаvoid print ( list p ){while ( p != NULL ) {/*пока не конец списка,putchar ( p−>elem ); /*печатаем очередной элементp = p−>next;/*и переходим к следующему звену}putchar ( '\n' );}*/*/*/*/Заголовок while-цикла можно было записать как while ( p ).

Однако, выражениеp != NULL более информативно — по нему можно догадаться, что p скорее всегоявляется указателем, даже не видя его описания.Опишем функцию печати, используя цикл for./* print: печать в стандартный выходной поток элементов спискаверсия с циклом forvoid print ( list p ){for ( ; p ; p = p−>next )/* пока не конец списка, т.е. p!=NULL/* печатаем очередной элементputchar ( p−>elem );и переходим к следующему звенуputchar( '\n' ) ;}*/*/*/Здесь мы использовали p в качестве условия продолжения цикла, а не p != NULL,так как рядом стоящее p –>next (в третьем выражении заголовка for), говорит о том,что p — указатель.Вычисление свойств и характеристик списков/* is_empty: возвращает 1, если список пуст, иначе — 0int is_empty ( list ls){return ls == NULL;}*//* count: подсчитывает число вхождений элемента elem в список lsint count ( list ls, elemtype elem){int c = 0; /* счетчик вхожденийfor ( ; ls ; ls = ls−>next )if ( ls−>elem == elem ) c++ ;return c;}*/*/Можно обойтись без условного оператора в теле цикла for, записав вместо негооператор-выражение:c += ( ls−>elem == elem);/* length: вычисляет длину списка lsint length ( list ls ){int c;for ( c = 0; lst ; lst = lst−>next, c++);return c;}*/Теперь опишем рекурсивную версию функции length.