Структуры, ссылающиеся на себя. Структуры, ссылающиеся на себя, содержат в качестве элемента указатель, который ссылается на структуру того эе типа. Например, определение
struct node {
int data;
struct node *nextptr;
};
описывает тип struct node. Структура типа struct node состоит из двух элементов – целого data и указателя nextPtr. Элемент nextPtr указывает на структуру типа struct node – структур того же самого типа, что и только объявленная. Элемент nextPtr иногда называют связкой, т. е. nextPtr можно использовать для того, чтобы связать структуру типа struct node с другой структурой того же типа.
Динамическое распределение памяти. Создание и использование динамических структур данных требует динамического распределения памяти – возможности получать в процессе исполнения дополнительную память для хранения новых узлов и освобождать блоки памяти, ставшие ненужными. Максимальный размер выделяемой динамической памяти определяется доступной физической памятью компьютера или доступным виртуальным адресным пространством в системе с виртуальной памятью. Для динамического распределения памяти необходимо применение функций malloc и free, а также операция sizeof. Функция malloc принимает в качестве аргумента число байт, которое необходимо выделить, и возвращает указатель на выделенную память типа void*. Указатель void* можно присвоить любой переменной-указателю. Функция malloc обычно используется совместно с операцией sizeof. Если необходимого количества памяти нет в наличии, malloc возвращает указатель NULL. Функция free освобождает память, т. е. память возвращается системе, и в дальнейшем ее можно выделить снова.
Связанные списки. Связанные списки – это линейный набор ссылающихся на себя структур, называемых узлами, и объединенных указателем-связкой. Доступ к связанному списку обеспечивается указателем на первый узле списка. Доступ к следующим узлам производится через связывающий указатель, хранящийся в каждом узле. По общему соглашению связывающий указатель в последнем узле списка устанавливается в NULL, отмечая конец списка. Данные хранятся в связанном списке динамически – каждый узел создается по мере необходимости. Узел может содержать данные любого типа, включая другие структуры. Связанный список удобен, когда заранее не известно, сколько элементов данных будет содержать структура. Связанные списки могут содержаться в сортированном виде, если помещать каждый новый элемент в соответствующую позицию списка.
Стеки. Стек – это упрощенный вариант связанного списка. Новые узлы могут добавляться в стек и удаляться из стека только сверху. По этой причине, стек часто называют структурой вида последним пришел – первым вышел (LIFO). На стек ссылаются через указатель на верхний элемент стека. Связывающий элемент в последнем узле стека установлен равным NUL, чтобы пометить границу стека.
Очереди. В очереди узлы удаляются только с головы, а добавляются только в хвост очереди. По этой причине очереди часто называют структурами данным типа первым пришел – первым ушел (FIFO).
Деревья. Дерево является нелинейной структурой, двумерной структурой данных с особыми свойствами. Узлы дерева содержат две или более связей. Двоичные деревья – деревья, узлы которых содержат только две связки. Первый узел дерева называется корневым. Каждая связь корневого узла ссылается на потомка. Левый потомок – первый узел левого поддерева, а правый потомок – первый узел правого поддерева. Потомки одного узла называются узлами-сиблингами. Двоичное дерево поиска (с неповторяющимися значениями в узлах) устроено так, что значения в любом левом поддереве меньше, чем значение в родительском узле, а значение в любом правом поддерево больше, чем значение в родительском узле.
Основная литература: 1осн[457-479]
Дополнительная литература: 9доп[212-223], 11доп[13-16]
Контрольные вопросы:
1. Назовите линейные динамические структуры данных?
2. В чем заключается различие между связанным списком и стеком?
3. Откуда удаляются узлы в очереди?
4. Куда вставляются узлы в стеках?
5. Какое дерево является двоичным деревом поиска?
Тема 13. Работа с файлами в Си.
Как при чтении, так и при записи информации в файл, его нужно открыть с помощью стандартной библиотечной функции fopen. Обращение к fopen в программе выполняется так:
fp = fopen (name, mode);
первый параметр – имя файла, строка символов, второй параметр – mode также строка символов, указывающая, как будет использоваться файл. Ниже приводятся основные способы применения файла:
«r» – файл нужно читать,
«w» – файл нужно записать,
«а» – файл нужно дополнить,
«r+» – открыть файл одновременно для чтения и записи (файл доллжен существовать),
«w+» – открыть пустой файл для чтения и записи (если этот файл ранеее сеществовал, его содержимое уничтожается),
«а+» – открыть фал для чтения и добавления (если файла нет, то вначале он создается).
При применении «r» открывается существующий файл. При попытке прочитать несуществующий файл – ошибка. При обнаружении ошибки fopen выдает нулевую ссылку со значением NULL. При применении «w» или «а» открывается файл для записи или дополнения, но если такого файла нет, он будет создан.
Внимание. Если используется «w» для существующего файла, то старая версия его стирается.
Третий параметр является указателем на файл; это значение возвращается функцией:
FILE *fp;
fp = fopen (“dann” , “r”);
Теперь fp является указателем на файл “dann”. С этого момента программа ссылается на файл при помощи указателя fp, а не по имени “dann”. Необходимо отметить: функция fopen ( ) возвращает указатель на ‘FILE’ в качестве аргумент; fopen () как функци указателя на ‘FILE’ не объявляется, т. к. это описание содержится в stdio. h:
FILE * fopen ();
Пример:
main ();
{ FILE *fp;
int ch;
if ((fp = fopen (“dann” , “r”)) ! = NULL)
{ while ((ch = getc (fp) ! = EOF) /* получение символа из файла, на который указывает fp*/
putch (ch, stdout); /*записывается символ ch в файл, на который ссылается */
/* указатель stdout, stdout – указатель на стандартный вызов */
fclose (fp); }
else
printf (“ файл не открыт \ n ”); }
Если fopen () не может открыть файл, она возвращает значение ‘NULL’ (в stdio. h определенное как 0).
fclose () – закрыть файл.
fclose (fp) – аргумент, fp – указатель на файл.
Можно проверить, успешно ли закрыт файл. Функция fclose () возвращает значение 0, если файл закрыт успешно, и – 1 в противном случае.
Ввод-вывод файла:
fprintf (), fscanf ()
Эти функции аналогичны функция printf () и scanf (), но в данном случае необходимо указать ссылку на файл.
main ()
{ FILE *fp;
int m;
fp = fopen (“dann1” , “ r ”);
fscanf (fp, “% d” , &m);
fclose (fp);
fp = fopen (“dann2”, “a”);
fprintf (fp, “ % d \ n“ , m);
fclose (fp);
- - - - - - - - }
Рассмотрим следующие функции
fgets (), fputs (), fread (), fwrite ().
1. fgets ( )
char * fgets (string, n, stream);
char * string;
int n;
FILE * stream;
Функция fgets () читает строку из входного потока stream и помещает ее в строку, адрес которой задается значением параметра string. Символы читаются из потока до тех пор, пока не будет прочитан символ новой строки (‘ \ n’ ), который включается в строку, или пока не наступит конец потока, или пока не будет прочитано (n-1) символов. Результат помещается в string и заканчивается нулевым символом (‘ \ 0 ’). Если n=1, то формируется пустая строка (возвращается адрес строки; значение NULL, если произошла ошибка или достигнут конец файла).
2. fputs ( )
int fputs (string, stream);
char * string;
FILE * stream;
Функция копирует строку string в поток stream с текущей позиции. Завершающийся нулевой символ (‘ \ 0 ‘) не копируется (возвращаемое значение: последний записанный символ; значение 0, если строка string пустая; значение EOF, если произошла ошибка).
3. fread ( )
int fread (buffer, size, count, stream);
void * buffer;
size-t size;
size-t count;
FILE * stream;
Функция читает count элементов длины sizе из входного потока stream и помещает их в заданный массив buffer. Указатель файла, связанный с потоком stream, увеличивается на число действительно прочитанных байтов. Форматных преобразований данных (как для функции fscanf ()) не производится. Символы перевода строки (‘ \ n ‘) специально (как для fgets ()) не обрабатываются. (Возвращаемое значение: количество действительно прочитанных элементов, которое может быть меньше, чем count, если встретилась ошибка или конец файла раньше, чем было прочитано count элементов. )
4. fwrite ( )
int fwrite (buffer, size, count, stream);
сhar * buffer;
int size;
int count;
FILE * stream;
Функция дописывает count записей по size байтов из области buffer в выходной поток stream (высокоуровневый ввод/вывод). Указатель файла (имеется в виду внутренний указатель), связанный с потоком stream, увеличивается на число записанных байтов. Форматных преобразований данных (как для fprintf ()) не производится. Символы перевода строки (‘ \ n ’) специально (как для fputs) не обрабатываются. (Возвращаемое значение: количество реально помещенных в файл записей; это число может быть меньше, чем значение count, если имела место ошибка.)
5. fseek ( )
int fseek (stream, offset, origin);
FILE * stream;
long offset;
int origin;
Функция перемещает (внутренний) указатель файла, связанного с потоком stream, на новое место в файле, которое вычисляется по смещению offset и указанию направления отсчета origin. Следующая операция ввода/вывода с указанным потоком stream будет выполнена, начиная с той позиции, на которую произведено перемещение.
Основная литература: 1осн[425-444], 2осн[437-450]
Дополнительная литература: 10доп[51-54], 11доп[16-23]
Контрольные вопросы:
1. В чем состоит сходство и различие между массивом и файлом?
2. Какие действия выполняют функции fseek и fopen?
3. Назовите функции записи информации в файл?
4. Назовите функции чтения информации из файла?
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
