Программирование в Linux. Учебное пособие С. В. Шапошникова, Лаборатория юного линуксоида, май 2012 1 Пояснительная записка
 Скачать 0.88 Mb.
|
|
Урок 16. Организация динамических структур данных Структуры одного типа можно объединять не только в массивы. Их можно связывать между собой, создавая так называемые динамические структуры данных. Связь между отдельными структурами может быть организована по-разному, и именно поэтому среди динамических данных выделяют списки, стеки, очереди, деревья, графы и др. Мы не будем рассматривать каждый тип. Цель этого урока — понять, что такое динамические данные, и как они создаются на языке программирования C Для динамических данных память выделяется и освобождается в процессе выполнения программы, а не в момент ее запуска. Так, например, если в программе объявлен массив из 100 элементов, то при запуске программы резервируется память для всех ста элементов, даже если в процессе работы программы всего будут использованы первые 10 элементов массива. С другой стороны, при использовании в программе динамических типов память под них 63 заранее не выделяется. Лишь когда поступают новые данные, вызывается специальная функция, которая выделяет память, куда эти данные записываются. Тут появляется проблема. Для динамических типов данных не объявляются переменные, иначе память бы выделялась под переменные. Как тогда обращаться к данным, записанным неизвестно где в памяти? Можно ввести переменные-указатели и при выделении памяти записывать адрес этой памяти в указатели. Но мы же не знаем, сколько памяти потребуется в процессе выполнения. Сколько вводить указателей? Проблема решается путем использования структур. Допустим, мы пишем программу, позволяющую вводить данные на сотрудников организации. Количество сотрудников неизвестно. Можно было бы создать массив записей с запасом. Однако, если данных о каждом сотруднике много, то каждая запись занимает много памяти; получается, что мы будем расходовать много памяти в пустую, если сотрудников мало. Идея заключается примерно в следующем: 1. В программе определяем структурный тип данных с "кое-какой изюминкой" и создаем переменную указатель на него. В итоге при запуске программы память выделяется только под указатель. 2. В процессе выполнения программы, в случае возникновения необходимости в создании структуры, с помощью специальной функции выделяем память под хранение данных (полей структуры). 3. Присваиваем указателю адрес, по которому расположена только что созданная структура. 4. Когда поступает команда на создание следующей структуры, снова с помощью функции выделяется память, а указателю присваивается адрес этой новой структуры. 5. "Изюминка" определенного ранее структурного типа данных заключается в том, что одним из его полей является указатель на структуру этого же типа. 6. В это поле-указатель записывается адрес на структуру, которая была создана перед данной структурой. Таким образом получается цепочка взаимосвязанных структур. Самая первая созданная структура не имеет ссылки на другую структуру. Ее поле-указатель имеет значение NULL. Вторая созданная структура ссылается на первую, третья на вторую и т.д. Адрес последней созданной структуры хранится в переменной-указателе, которая была объявлена в программе программистом. Чтобы извлечь данные из такого агломерата данных, надо пройтись по ссылкам начиная с переменной-указателя. Т.е. первой мы извлечем последнюю записанную структуру. Потом предпоследнюю и постепенно будем двигаться к структуре, которая была создана первой во времени. Такой динамический тип данных называется стеком. Объекты извлекаются из стека таким образом, что первым выбирается тот, который был помещен последним. Стек — это не единственный способ организации динамических данных, но наиболее простой. Если динамические данные больше не нужны, следует не забыть освободить память. В языке программирования C выделение памяти в процессе выполнения программы можно организовать с помощью функций malloc() и calloc() , освобождение памяти с помощью free() . Объявление этих функций находится в заголовочных файлах stdlib.h и malloc.h. К исходному коду можно подключить любой из них. 64 Функция malloc() принимает в качестве параметра число, обозначающее объем памяти, который требуется выделить. Если свободная память есть, и malloc() удается ее "захватить", то функция возвращает указатель на нее. Этот указатель не имеет типа, поэтому программист самостоятельно должен привести его к требуемому в программе типу данных. Функция free() принимает указатель, и освобождает память по адресу, который он содержит. Рассмотрим программу: #include #include struct stack { int data; struct stack *next; }; struct stack *create(struct stack *, int); // присоединение элемента к голове, возврат адреса головы void list(struct stack *); // просмотр стека main() { int i, n; struct stack *head; // адрес, указывающий на голову стека head = NULL; scanf("%d", &n); for (i=0; i <= n; i+=5) { head = create(head,i); printf("%d<--", head->data); } printf("\n"); list(head); free(head); } struct stack *create(struct stack *head, int x) { struct stack *element; // указатель на новую структуру element = (struct stack *)malloc(sizeof(struct stack)); // выделяем память element->next = head; element->data = x; return element; } void list(struct stack *p){ while (p != NULL) { // пока не конец стека printf("%d-->", p->data); p = p->next; // продвижение по списку } printf("\n"); } В процессе выполнения эта программа запрашивает целое число и сначала выводит числа от 0 до указанного числа, а затем выводит их же в обратном порядке — от указанного число до нуля: 60 0<--5<--10<--15<--20<--25<--30<--35<--40<--45<--50<--55<--60<-- 60-->55-->50-->45-->40-->35-->30-->25-->20-->15-->10-->5-->0--> 65 Осталось выяснить почему она так делает. • В программе определяется тип данных struct stack, одним из полей которого является указатель на структуру типа struct stack. • В функции main() создается указатель (head) на struct stack, которому сначала присваивается NULL, т.к. он никуда не указывает. • В цикле определенное количество раз вызывается функция create() , которой передается текущее значение указателя (адрес) и какое-то число. • В теле create() создается новый указатель (element) типа struct stack. • С помощью функции malloc() выделяется память, необходимая под одну структуру. Объем этой памяти вычисляется с помощью функции sizeof() . Возвращаемый malloc() указатель приводится к типу struct stack. • Адрес выделенной памяти под новую структуру присваивается переменной- указателю element. • В поле next новой структуры записывается адрес, который содержится в аргументе, переданном в функцию. При первом вызове create() там содержится NULL. При последующих вызовах адрес памяти созданной в предыдущем вызове функции структуры. Таким образом в поле next структуры, доступной по указателю element, сохраняется адрес, содержащийся в head. Следовательно head в дальнейшем можно изменить, не потеряв связь с предыдущими данными. • В поле data записывается число (какие-то существенные для нас данные). • Из функции create() возвращается указатель на только что выделенную память с новой структурой, в которой сохранен адрес на предыдущую структуру. Этот указатель присваивается head. В результате head постоянно указывает на последнюю созданную структуру. • На экран с помощью printf() выводится значение поля data структуры, на которую указывает в данный момент head. • Функция list() позволяется просмотреть стек, получив указатель на его последний (по времени создания) элемент. При вызове значение head присваивается переменной p. Обратите внимание, изменение p в теле list() не повлияет на значение head в теле main() . Переменная p получает копию адреса и далее изменяет лишь свое значение. • В выражении p = p->next сначала изымается значение из поля next структуры, на которую указывает p. Там содержится адрес на предыдущую структуру, и этот адрес присваивается p. Таким образом p как бы перемещается по стеку, начиная с последней вошедшей в него структуры и заканчивая на той, которая была создана первой. Поле next первой структуры содержит NULL, который служит условием выхода из цикла. • В конце с помощью функции free() освобождает память по адресу, на который указывает head. (Освобождается ли при этом вся выделенная память или только та, что была отведена на последнюю структуру?) Преимущество этой программы в том, что память выделяется только под то количество структур, которое необходимо. Количество структур определяется в процессе выполнения программы. Однако приходится тратить память на указатели. Если структура содержит лишь одно значащее поле, как в примере выше, то такие затраты могут быть неоправданны. Проще было бы объявить массив с запасом. Но если структура сложная, содержит много полей, то организация динамических типов данных приносит существенный плюс. 66 Задание 1. Напишите программу, аналогичную приведенной в уроке. При этом структурный тип данных должен быть более сложным и содержать как минимум три значащих поля (например, данные о сотрудниках: ФИ, сфера деятельности, стаж). Поля должны заполняться пользователем. 2. Напишите к вашей программе функцию, которая выводит значения полей указанной пользователем структуры. Например, пользователь пишет ФИ и получает остальные сведения о человеке. 3. Напишите еще одну функцию, которая позволяет удалять последнюю записанную структуру. 4. Подумайте над алгоритмом удаления структуры из любого места стека. Попробуйте его реализовать. Урок 17. Ввод данных из файла и вывод в файл Открытие и закрытие файлов До этого при вводе-выводе данных мы работали со стандартными потоками — клавиатурой и монитором. Теперь рассмотрим, как в языке C реализовано получение данных из файлов и запись их туда. Перед тем как выполнять эти операции, надо открыть файл и получить доступ к нему. В языке программирования C указатель на файл имеет тип FILE и его объявление выглядит так: FILE *myfile; С другой стороны, функция fopen() открывает файл по указанному в качестве первого аргумента адресу в режиме чтения ("r"), записи ("w") или добавления ("a") и возвращает в программу указатель на него. Поэтому процесс открытия файла и подключения его к программе выглядит примерно так: myfile = fopen ("hello.txt", "r"); При чтении или записи данных в файл обращение к нему осуществляется посредством файлового указателя (в данном случае, myfile). Если в силу тех или иных причин (нет файла по указанному адресу, запрещен доступ к нему) функция fopen() не может открыть файл, то она возвращает NULL. В реальных программах почти всегда обрабатывают ошибку открытия файла в ветке if , мы же далее опустим это. Объявление функции fopen() содержится в заголовочном файле stdio.h, поэтому требуется его подключение. Также в stdio.h объявлен тип-структура FILE. После того, как работа с файлом закончена, принято его закрывать, чтобы освободить буфер от данных и по другим причинам. Это особенно важно, если после работы с файлом программа продолжает выполняться. Разрыв связи между внешним файлом и указателем на него из программы выполняется с помощью функции fclose() . В качестве параметра ей передается указатель на файл: fclose(myfile); В программе может быть открыт не один файл. В таком случае каждый файл должен быть связан со своим файловым указателем. Однако если программа сначала работает с одним файлом, потом закрывает его, то указатель можно использовать для открытия второго файла. 67 Чтение из текстового файла и запись в него fscanf() Функция fscanf() аналогична по смыслу функции scanf() , но в отличии от нее осуществляет форматированный ввод из файла, а не стандартного потока ввода. Функция fscanf() принимает параметры: файловый указатель, строку формата, адреса областей памяти для записи данных: fscanf (myfile, "%s%d", str, &a); Возвращает количество удачно считанных данных или EOF. Пробелы, символы перехода на новую строку учитываются как разделители данных. Допустим, у нас есть файл содержащий такое описание объектов: apples 10 23.4 bananas 5 25.0 bread 1 10.3 Тогда, чтобы считать эти данные, мы можем написать такую программу: #include main () { FILE *file; struct food { char name[20]; unsigned qty; float price; }; struct food shop[10]; char i=0; file = fopen("fscanf.txt", "r"); while (fscanf (file, "%s%u%f", shop[i].name, &(shop[i].qty), &(shop[i].price)) != EOF) { printf("%s %u %.2f\n", shop[i].name, shop[i].qty, shop[i].price); i++; } } В данном случае объявляется структура и массив структур. Каждая строка из файла соответствует одному элементу массива; элемент массива представляет собой структуру, содержащую строковое и два числовых поля. За одну итерацию цикл считывает одну строку. Когда встречается конец файла fscanf() возвращает значение EOF и цикл завершается. fgets() Функция fgets() аналогична функции gets() и осуществляет построчный ввод из файла. Один вызов fgets() позволят прочитать одну строку. При этом можно прочитать не всю строку, а лишь ее часть от начала. Параметры fgets() выглядят таким образом: fgets ( массив_символов, количество_считываемых_символов, указатель_на_файл ) Например: fgets (str, 50, myfile) Такой вызов функции прочитает из файла, связанного с указателем myfile, одну строку текста полностью, если ее длина меньше 50 символов с учетом символа '\n', который функция также 68 сохранит в массиве. Последним (50-ым) элементом массива str будет символ '\0', добавленный fgets() . Если строка окажется длиннее, то функция прочитает 49 символов и в конце запишет '\0'. В таком случае '\n' в считанной строке содержаться не будет. #include #define N 80 main () { FILE *file; char arr[N]; file = fopen("fscanf.txt", "r"); while (fgets (arr, N, file) != NULL) printf("%s", arr); printf("\n"); fclose(file); } В этой программе в отличие от предыдущей данные считываются строка за строкой в массив arr. Когда считывается следующая строка, предыдущая теряется. Функция fgets() возвращает NULL в случае, если не может прочитать следующую строку. getc() или fgetc() Функция getc() или fgetc() (работает и то и другое) позволяет получить из файла очередной один символ. while ((arr[i] = fgetc (file)) != EOF) { if (arr[i] == '\n') { arr[i] = '\0'; printf("%s\n",arr); i = 0; } else i++; } arr[i] = '\0'; printf("%s\n",arr); Приведенный в качестве примера код выводит данные из файла на экран. Запись в текстовый файл Также как и ввод, вывод в файл может быть различным. • Форматированный вывод. Функция fprintf ( файловый_указатель, строка_формата, переменные ) • Посточный вывод. Функция fputs ( строка, файловый_указатель ) • Посимвольный вывод. Функция fputc() или putc( символ, файловый_указатель ) Ниже приводятся примеры кода, в которых используются три способа вывода данных в файл. Запись в каждую строку файла полей одной структуры: file = fopen("fprintf.txt", "w"); while (scanf ("%s%u%f", shop[i].name, &(shop[i].qty), &(shop[i].price)) != EOF) { 69 fprintf(file, "%s %u %.2f\n", shop[i].name, shop[i].qty, shop[i].price); i++; } Построчный вывод в файл ( fputs() , в отличие от puts() сама не помещает в конце строки '\n'): while (gets (arr) != NULL) { fputs(arr, file); fputs("\n", file); } Пример посимвольного вывода: while ((i = getchar()) != EOF) putc(i, file); Чтение из двоичного файла и запись в него С файлом можно работать не как с последовательностью символов, а как с последовательностью байтов. В принципе, с нетекстовыми файлами работать по-другому не возможно. Однако так можно читать и писать и в текстовые файлы. Преимущество такого способа доступа к файлу заключается в скорости чтения-записи: за одно обращение можно считать/записать существенный блок информации. При открытии файла для двоичного доступа, вторым параметром функции fopen() является строка "rb" или "wb". Тема о работе с двоичными файлами достаточно сложная, для ее изучения требуется отдельный урок. Здесь будут отмечены только особенности функций чтения-записи в файл, который рассматривается как поток байтов. Функции fread() и fwrite() принимают в качестве параметров: 1. адрес области памяти, куда данные записываются или откуда считываются, 2. размер одного данного какого-либо типа, 3. количество считываемых данных указанного размера, 4. файловый указатель. Эти функции возвращают количество успешно прочитанных или записанных данных. Т.е. можно "заказать" считывание 50 элементов данных, а получить только 10. Ошибки при этом не возникнет. Пример использования функций fread() и fwrite() : #include #include main () { FILE *file; char shelf1[50], shelf2[100]; int n, m; file = fopen("shelf1.txt", "rb"); n=fread(shelf1, sizeof(char), 50, file); fclose(file); file = fopen("shelf2.txt", "rb"); m=fread(shelf2, sizeof(char), 50, file); fclose(file); shelf1[n] = '\0'; 70 shelf2[m] = '\n'; shelf2[m+1] = '\0'; file = fopen("shop.txt", "wb"); fwrite(strcat(shelf2,shelf1), sizeof(char), n+m, file); fclose(file); } Здесь осуществляется попытка чтения из первого файла 50-ти символов. В n сохраняется количество реально считанных символов. Значение n может быть равно 50 или меньше. Данные помещаются в строку. То же самое происходит со вторым файлом. Далее первая строка присоединяется ко второй, и данные сбрасываются в третий файл. |