Урок 8.1.3. Указатели и структуры

8.1.3. Указатели и структуры

При решении многих задач возникает необходимость использования
специальных типов данных отличных от типов данных предусматриваемых языком
программирования. В информатике эти типы представлены такими как, например,
очереди, стеки, двоичные деревья, списки различного вида и другие типы,
особенности которых мы здесь не имеем возможности рассматривать, - это предмет
специального разговора, выходящего за рамки изучения языка Си. Однако, все же
мы должны показать каким образом программист, используя стандартные возможности
Си, может создавать и обрабатывать такие неординарные типы данных. Многие из
этих типов создаются из "связанных" структур. Связывание структур
осуществляется с помощью указателей на структуры. В качестве примера рассмотрим
организацию и обработтку однонаправленного списка.

Для начала определим
понятие списка. Списком называется совокупность структурных данных, каждое из
которых содержит ссылку, связывающую его со следующим данным. Для организации
списков используются структурные данные, состоящие из двух частей: основной и
дополнительной. Основная часть содержит информацию, подлежащую обработке, а в
дополнительной части находится указатель на следующее данное списка. Последнее
данное списка в своей дополнительной части содержит указатель на нулевой адрес,
что является признаком конца списка. Начало списка, как правило, определяется
отдельным, не входящим в список, указателем на первое данное в списке. Схема
организации списка дана на рис. 9.2.

 

 

 

 

Рис. 9.2. Схема организации списка.

Рассмотрим простейшую задачу. Допустим, необходимо создать программу
для печати информации о сотрудниках некоторого учреждения. Программа должна запрашивать
сведения о сотрудниках, например, такие как фамилия, табельный номер, зарплата
в месяц и так далее. Для простоты реализации будем вводить данные о сотрудниках
с клавиатуры компьютера и после того, как ввод данных о всех сотрудниках
завершен, будем выводить их на принтер или на экран. Кроме того, программу
нужно сделать так, чтобы была обеспечена ее работоспособность независимо от
количества сотрудников учреждения. Последнее требование к программе заставляет
задуматься над организацией способа хранения данных. Очевидно, что такие данные
можно представить структурным типом, а, именно, одномерным массивом структур,
как, например, показано на рис. 9.1. Но каков должен быть размер такого
массива? Где гарантии того, что количество сотрудников не превысит размер
массива? Если мы опишем массив уж очень большого размера, то при относительно
малом количестве сотрудников, значительная часть памяти, зарезервированная под
массив, не будет использоваться. Учитывая эти рассуждения, нужно построить
программу так, чтобы она требовала для хранения данных количество памяти
пропорциональное количеству сотрудников конкретного учреждения и тогда
ограничения на применимость программы будут диктоваться ресурсами компьютера по
оперативной памяти, а не особенностью ее реализации. Таким образом, мы приходим
к необходимости организации списка: будем запрашивать данные о сотруднике и
динамически, в области куча, с помощью функции malloc(_размер_), выделять
память для их хранения и "связывать" с помощью указателя на данные о
последующем сотруднике. Что это за память с названием куча и как отрабатывает
встроенная функция malloc можно вспомнить, посмотрев разделы 8.1.2. и 8.1.5.

Итак, рассмотрим возможности организации списков в Турбо Си с помощью
указателей на структуры. Для этого изменим, показанное ранее, описание
структурного шаблона RECORD, включив в него описание указателя pw:

struct RECORD

{ int num;

char name[20];

float pmn;

struct RECORD *pw;

};

В таком включении, как уже отмечалось, нет ничего противоречивого, так
как struct
RECORD *pw; описывает не саму
структуру, а ссылку на нее. Такой структурный шаблон задает основную часть для
хранения данных о сотруднике и дополнительную часть для указателя на следующее
данное списка. Используем этот структурный шаблон для организации списка
сотрудников учреждения. Программу представим в виде фрагментов с разъяснениями
того, что в них делается.

#include <stdio.h>

#include <string.h>

#include <alloc.h>

#define STOP ""

#define str1 "Введите фио или ВВОД для
окончания"

#define str2 "Введите табельный номер
струдника "

#define str3 "Введите помесячную
зарплату"

Директивы препроцессора #include
включают в исходный текст программы три заголовочных файла, - файл stdio.h содержит описание функций ввода-вывода, файл string.h содержит описания функций обработки строк, а
в файле alloc.h содержатся описание функций распределения
памяти. Включение этих файлов обусловлено тем, что в программе будут
использованы встроенные функции соответствующего назначения.

Директивы препроцессора #define
определяют 4 символьные строки. Строка STOP содержит только нуль-символ и используется
для завершения ввода данных о сотрудниках.

main()

{

struct RECORD

{ int num;

char name[20];

float pmn;

struct RECORD *pw;

};

struct RECORD *first=NULL, *current=NULL, *prec;

char inp[20];

Начало основной программы. Описаны шаблон структуры, три указателя на
структурные переменные, два из которых инициализированы нулевым адресом, и
символьная строка, для ввода данных о сотруднике. Такая инициализация возможна,
так как сушествует системное определение #define NULL 0 . Указатель first будет использован для ссылки на первую запись списка, а current - на текущую, то есть на обрабатываемую в
данный момент. Указатель prec будет использован для печати списка сотрудников.
Вначале оба указателя ссылаются на нулевой адрес памяти, ибо еще не создано ни
одного элемента списка.

puts(str1);

Функция puts выводит содержимое строки, полученной в качестве
параметра, то есть осуществляет приглашение на ввод фамилии первого сотрудника.

while(strcmp(gets(inp),STOP)!=0)

Оператор while позволяет организовать цикл по вводу данных о
сотрудниках. Цикл будет выполняться до тех пор, пока функция strcmp (сравнение строк) не возвратит нулевое
значение, то есть пока введенная пользователем строка в область inp (в результате отработки функции) не будет
пустой. Далеерассматриваемтелоцикла.

{

if (first != NULL)

{

current->pw=(struct RECORD *)
malloc(sizeof(struct RECORD));

current=current->pw;

}

else

{

first= (struct RECORD *) malloc(sizeof(struct
RECORD));

current=first;

}

Условный оператор if-else
предназначен для обработки первого элемента списка. Так как для него не
существует предыдущего элемента, то его адрес мы будем хранить в указателе first. При первом проходе цикла указатель first содержит NULL и, следовательно, выполнится группа операторов после
else. Функция malloc возвратит указатель на свободный участок
памяти из области куча, достаточный для размещения структурной переменной типа
struct RECORD, - этот указатель преобразуется к типу struct RECORD * применением операции преобразования типа (struct RECORD *) и присваивается указателям first иcurrent.
При последующих выполнениях цикла будут обрабатываться операторы, записанные
после if. Первый из них осуществляет "связку"
нового элемента списка, полученного от функции malloc, с текущим через указатель current->pw, а второй делает новый элемент текущим.

strcpy(current->name,inp);

Функция strcpy копирует введенную фамилию сотрудника из области inp в область name динамически полученной памяти, то есть в области
данных сформированного элемента списка появилась фамилия сотрудника.

puts(str2);

scanf("%d",&current->num);

puts(str3);

scanf("%f",&(current->pmn));

current->pw=NULL;

Выполняются приглашения на ввод и вводятся остальные данные о
сотруднике. Ссылка на последующий элемент списка устанавливается в NULL, так как заранее не известно будут ли еще
добавлены в список элементы.

puts(str1);

getchar();

}

Выполняется приглашение на ввод фамилии следующего сотрудника. Функция
getchar использована здесь в связи с тем, что, ранее отработавшая, функция
scanf имеет особенность "оставлять" при чтении в буфере символ новой
строки (\n), который при повторении цикла автоматически
завершал бы выполнение функции gets.
Чтобы этого не произошло, функция getchar
должна прочитать этот символ, очистив тем самым буфер.

Таким образом, в результате завершения цикла (при вводе "пустой
строки" на запрос фамилии сотрудника) в памяти сформирован список,
отражающий информацию о сотрудниках учреждения и содержажий ровно столько
элементов списка, сколько сотрудников в данном учреждении.

prec = first;

while( prec != NULL ) {

printf("%-5d %-20s
%-5f\n",prec->num,prec->name,prec->pmn);

prec=prec->pw;

}

}

И, наконец, последний фрагмент программы иллюстрирует удобство
обработки связных списков с помощью указателей. Указателю prec присваивается
адрес первого элемента списка, а затем он пробегает по всем элементам пока не
встретит значение NULL.

Для лучшего восприятия приводим цельный текст только что рассмотренной
программы обработки списков.

/* Начало исходного файла */

/* Директивы препроцессора для включения
описаний функций */

#include <stdio.h>

#include <string.h>

#include <alloc.h>

/* Директивы препроцессора для определения
констант */

#define STOP ""

#define str1 "Введите фио или ВВОД для
окончания"

#define str2 "Введите табельный номер
струдника "

#define str3 "Введите помесячную
зарплату"

 

/* Начало программы обработки списка */

main()

{

struct RECORD

{ int num;

char name[20];

float pmn;

struct RECORD *pw;

};

struct RECORD *first=NULL, *current=NULL, *prec;

char inp[20];

/* Запрос данных и динамическое
формирование списка */

puts(str1);

while(strcmp(gets(inp),STOP)!=0) {

if (first != NULL)

{ current->pw=(struct
RECORD *) malloc(sizeof(struct RECORD));

current=current->pw;

}

else { first= (struct RECORD *)
malloc(sizeof(struct RECORD));

current=first;

}

strcpy(current->name,inp);

puts(str2);

scanf("%d",&current->num);

puts(str3);

scanf("%f",&(current->pmn));

current->pw=NULL;

puts(str1);

getchar();

}

/* Выводсписка */

prec = first;

while( prec != NULL ) {

printf("%-5d %-20s
%-5f\n",prec->num,prec->name,prec->pmn);

prec=prec->pw;

}

} /* Конец программы */

Отметим, что рассмотренная программа является учебным примером, так как
в ней не реализованы составные части, необходимые для пользовательской
программы. Например, не реализована проверка того, выделена ли динамическая
память по запросу программы, не контролируется корректность ввода исходных
данных и, конечно, сам список сотрудников предпочтительно формировать в файле
на магнитном носителе, а не в оперативной памяти. Все это сделано умышленно,
чтобы не "затенять" основную учебную цель - проиллюстрировать метод
динамического создания нетривиальных типов данных на основе структурных
переменных, указателей и соответствующих операций доступа к элементам
структуры. Кстати, обратим внимание на то, что в программе нет имен структурных
переменных как таковых, а использованы указатели на структурный тип, что
обеспечило эффективное использование операции -> для доступа к элементам
динамически создаваемой структуры.

рассказать друзьям и получить подарок

Оставить комментарий

Ваш email не будет опубликован. Обязательные поля отмечены *

Вы можете использовать это HTMLтеги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Translate Переводчик

Подписка на новости

SmartResponder.ru
Ваш e-mail: *
Ваше имя: *

Хостинг для Wordpress сайтов