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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

А. А. ВылитокЯзык Си. Реализация списков с помощью цепочекдинамических объектовВ языке Си нет встроенных типов данных и операций для работы со списками.Программируя на языке Паскаль (в котором также нет стандартных типов для списков),мы представляли списки цепочками динамических объектов. Аналогичная реализациявозможна и в языке Си.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.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций