'

Структуры в языке Си

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

В этой лекции рассматриваются более сложные агрегаты данных, называемые структурами Под структурой в языке Си понимается набор одной или большего числа переменных, возможно имеющих различный тип и объединенных под единым именем, называемым именем структуры Описание всякой структуры в программе начинается с ключевого слова struct и в простейшем случае имеет следующий формат: struct {member-declaration list} identifier <,identifier ... >; struct есть ключевое слово языка Си, а в угловые скобки (<>) заключена необязательная часть конструкции member-declaration list - одно или более описаний переменных, каждая из которых называется элементом структуры, а identifier - имя переменной, определяемой как имеющей тип структура


Слайд 3

Так, например, инструкция struct { char name[30]; int group; } student; определяет структуру с именем student , элементами которой являются массив символов name и целочисленная переменная group Каждое из описаний в member-declaration list имеет тот же самый формат, что и рассмотренные ранее описания обычных переменных или массивов, однако здесь недопустимо использование описателей класса памяти и инициализирующих выражений Вся эта совокупность описаний, заключенная в фигурные скобки, определяет общую схему структуры и называется ее шаблоном


Слайд 4

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


Слайд 5

Например, обозначение student.group задает элемент group в составе структуры student, в то время как ссылка student.name[9] выделяет десятый элемент массива name той же структуры


Слайд 6

В отличие от имени массива, имя структуры само по себе не является синонимом своего имени. По существу это означает, что употребление имени структуры без следующего за ним символа операции получения элемента (.) и его имени не является допустимым и приводит к ошибке на этапе компиляции программы Для получения же адреса начала структуры необходимо явным образом применить операцию & к имени структуры или ее первого элемента Например, следующие два адресных выражения &student и &student.name[0] полностью эквивалентны и их значения равны адресу размещения структуры student в памяти компьютера


Слайд 7

Совершенно аналогично, выражение &student.group определяет адрес элемента group в составе рассматриваемой структуры


Слайд 8

Рассмотренный нами простейший способ определения структур требует всякий раз повторять шаблон структуры в каждом новом описании, даже если эти описания определяют структуры с одной и той же общей схемой Чтобы избежать такого повторения, язык Си предоставляет возможность снабдить шаблон создаваемой структуры некоторым именем, называемым тегом структуры Поэтому более общий способ описания структур в программе имеет следующий формат: struct <tag> {member-declaration list} <identifier<,...>>; где tag является именем, присваиваемым шаблону структуры, а все остальные обозначения сохраняют свой прежний смысл


Слайд 9

После своего определения в программе, тег структуры совместно с ключевым словом struct может быть использован как эквивалент имени типа данных, т. е. допустимыми являются последующие описания вида struct tag identifier <, identifier ... >; определяющие имя identifier как имеющее тип struct tag


Слайд 10

Частным случаем рассмотренной только что общей схемы определения структур является описание, в котором отсутствует список имен переменных после закрывающей фигурной скобки, но в обязательном порядке указано имя в поле tag Например: struct STACK { int pointer; float vector[100]; }; Такое описание определяет лишь общую схему структуры, присваивая ей имя STACK и не требуя от компилятора фактического выделения памяти


Слайд 11

Теперь, воспользовавшись сокращенной формой, можно определить конкретную структуру struct STACK stack; имеющую ранее фиксированный шаблон Ссылки же на отдельные элементы структуры stack задаются в этом случае обычным образом stack.vector[9] что соответствует обращению к десятому элементу массива vector в составе структуры stack


Слайд 12

В следующем примере struct DATE { int day; int month; int year; char day_name[15]; char mon_name[15]; }; struct DATE date_1; имя DATE присваивается шаблону структуры и одновременно определяется конкретная структура date_1, под представление которой компилятором выделяются тридцать шесть байт оперативной памяти После этого для определения структуры date_2 уже нет необходимости вновь описывать шаблон структуры, а достаточно воспользоваться сокращенной формой вида struct DATE date_2;


Слайд 13

В инструкциях описания структур, как и при определении обычных переменных или массивов, может содержаться дополнительная информация о классе памяти в виде соответствующего описателя, стоящего перед ключевым словом struct Способы их назначения и роль в программе остаются в этом случае прежними В частности, структуры, имеющие класс памяти static или extern, могут быть инициализированы путем указания в фигурных скобках списка начальных значений всех или нескольких первых элементов определяемой структуры


Слайд 14

Так, например, возвращаясь к структурному шаблону с именем DATE, можем записать struct DATE date_3 = {17, 3, 1989, "пятница", "февраль"}; Если список инициализирующих выражений меньше полного количества элементов в структуре или отсутствует вообще, элементы внешних и статических структур, не имеющие инициализатора, полагаются равными нулю При описании же структур, имеющих класс памяти auto, значения их элементов остаются неопределенными


Слайд 15

Массивы структур Отдельные структуры с произвольным общим шаблоном, как и обычные переменные любого типа, могут быть объединены в массивы фиксированной длины Описания массивов структур в программе строятся на той же самой синтаксической основе, что и описания обычных массивов. Так, в следующем примере struct BOOK { char author[30]; /* Автор книги */ char title[256]; /* Название книги */ int year; /* Год издания */ int pages; /* Количество страниц */ } catalog[10]; /* Массив структур */ имя catalog объявлено как массив десяти структур с общим шаблоном BOOK. Организация данных, подобная этой, может быть использована, например, при составлении библиографических каталогов


Слайд 16

Для обращения к отдельным элементам массива структур его имя всякий раз необходимо модифицировать при помощи квадратных скобок ([ ]), задающих операцию взятия элемента массива Конкретный элемент выбранной из массива структуры выделяется в этом случае обычным образом при помощи символа точка (.). Так, обращение вида catalog[3].title[4] задает пятый символ массива title элементов типа char в составе четвертого элемента массива структур catalog Применяя к какому-либо элементу массива операцию & получения адреса &catalog[7] можно найти начало размещения в памяти соответствующей структуры


Слайд 17

Замечание. Поскольку имя всякого массива является синонимом своего адреса, то упоминание самого по себе имени массива структур тождественно операции получения адреса нулевого элемента этого массива В частности, для массива структур catalog из предыдущего примера следующие выражения эквивалентны catalog &catalog[0].author[0] catalog[0].author


Слайд 18

Указатели на структуры В предыдущем параграфе, определяя понятие массива структур, мы сделали первый шаг к пониманию того, что тип struct является совершенно полноправным типом данных языка Си Теперь, расширяя наши представления о структурах, попробуем определить понятие указателя на структуру и придать ему конкретный смысл в программе Формально указатель на структуру можно описать подобно тому, как мы это делали для указателей на простые типы данных Общая схема такого описания должна иметь, видимо, один из следующих форматов: struct <tag> { member-declaration list }*identifier <, ... >; или struct tag *identifier <, ... >;


Слайд 19

В частности, возвращаясь в примерам предыдущих параграфов, мы могли бы написать struct STUDENT { char name[30]; int group; } *studptr; определяя тем самым указатель studptr на структурный тип STUDENT Комбинация *studptr должна рассматриваться как сама структура и формально можно задать ссылку на ее отдельный элемент, используя операцию точка (.): (*studptr).group Заметим, что в этом примере, как и при определении указателей на массивы, круглые скобки являются существенными, поскольку стандартный приоритет операции получения элемента (.) выше приоритета операции косвенной адресации (*)


Слайд 20

Однако последняя запись может и не иметь конкретного смысла, поскольку создавая указатель на структуру компилятор не выделяет реальную память под хранение ее элементов Эта ситуация полностью аналогична той, с которой мы столкнулись, рассматривая эквивалентность массивов и указателей В то же время, указатели на структуры обеспечивают принципиальную возможность более гибкого манипулирования данными, нежели сами структуры, поскольку используя аппарат указателей память под размещение элементов структуры можно выделять динамически при помощи функций alloca() , malloc() или realloc() Так, например, воспользовавшись пер вой из этих функций, мы можем написать studptr = (struct STUDENT*)alloca(n*sizeof(struct STUDENT)); зарезервировав тем самым блок памяти, достаточный для размещения массива n структур с шаблоном STUDENT


Слайд 21

Теперь, используя обозначения последнего примера, попробуем придать конкретный смысл арифметическим операциям над указателями на структуры Вспоминая, что увеличивая на единицу значение указателя на простой тип данных, мы заставляли его ссылаться на очередной элемент данных соответствующего типа, нетрудно понять, что операции вида studptr = studptr + 1 или studptr++ смещают указатель на структурный тип STUDENT на начало очередной структуры этого типа Используя далее общее понятие эквивалентности массивов и указателей, можно проиндексировать указатель на структуру, понимая эту операцию в смысле равенства адресов studptr + i == &studptr[i] или в контексте выделения отдельного элемента структуры (*(studptr+i)).name[k] == studptr[i].name[k]


Слайд 22

Для удобства выделения элементов структур, заданных своими указателями, в языке Си дополнительно введена операция следования, знаком которой является комбинация -> символов '-' и '>‘ Ее приоритет совпадает с приоритетом обычной операции получения элемента структуры. Используя эту операцию в нашем примере, вместо обозначения (*studptr).name определяющего адрес массива name в составе структуры с указателем studptr, следует писать studptr->name что семантически совершенно эквивалентно предыдущей записи


Слайд 23

Определение и использование новых типов данных С возможностью определения новых типов данных мы по существу уже встречались при описании структур, объединений и перечислений. Действительно, определяя, например, тег структуры, программист фактически вводит в работу и снабжает некоторым именем новую организацию данных, причем ссылки на нее становятся допустимыми всюду в дальнейшем как и на стандартные имена типов данных В дополнение к уже рассмотренным средствам, в языке Си имеется специальная инструкция, позволяющая расширить возможности определения и использования новых типов данных, сделав их в то же время более лаконичными Эта инструкция начинается с ключевого слова typedef


Слайд 24

Рассмотрим несколько наиболее характерных примеров использования инструкции typedef 1. В простейшем случае эта инструкция позволяет переопределить имена стандартных типов данных, назначив, например, имя whole для обозначения стандартного типа int: typedef int whole; 2. Наиболее характерным применением инструкции typedef является назначение имен вновь определяемым агрегатам данных. Следующее описание typedef struct { int poiter; char string[81]; } STACK; вводит новый тип данных с именем STACK, задающий структуру с шаблоном из двух элементов. В процессе разработки программ имена типов данных, определенные с помощью инструкции typedef, могут использоваться всюду наравне с именами стандартных типов данных


Слайд 25

Рассмотрим каким образом можно организовать работу с комплексными числами c1 = a1 + i b1 struct complex { double real; double imag;}; typedef struct complex COMPLEX; Теперь доступ к конкретному элементу можно получить уже известными способами: COMPLEX z; z.real = 3.4; z.imag = 5.6; COMPLEX *pt; pt = &z; ... pt->real ; pt->imag ;


Слайд 26

Чтобы производить арифметические действия с такими "искусственными" комплексными числами, нужно написать специальные функции. Это сделать довольно несложно, если вспомнить, как это делается в математике Необходимо задать операции сложения, вычитания, умножения и деления c1 + c2 = (a1 + i b1) + (a2 + i b2) = (a1 + a2) + i (b1 + b2) c1 - c2 = (a1 + i b1) - (a2 + i b2) = (a1 - a2) + i (b1 - b2) c1 * c2 = (a1 + i b1) * (a2 + i b2) = (a1 a2 - b1 b2) + i (a2 b1 + a1 b2) Немного сложнее с делением c1 / c2 = (a1 + i b1) / (a2 + i b2) = (a1 + i b1) (a2 - i b2) / (a22 + b2 2) = = (a1 a2 + b1 b2) / (a22 - b2 2) + i (a2 b1 - a1 b2) / (a22 + b2 2)


Слайд 27

/* Сложение двух комплексных чисел */ void add(COMPLEX *a, COMPLEX *b, COMPLEX *c) { c->real = a->real + b->real; c->imag = a->imag + b->imag; } /* Вычитание комплексных чисел */ void sub(COMPLEX *a, COMPLEX *b, COMPLEX *c) { c->real = a->real - b->real; c->imag = a->imag - b->imag; } /* Умножение двух комплексных чисел */ void mult(COMPLEX *a, COMPLEX *b, COMPLEX *c) { c->real = a->real*b->real - a->imag*b->imag; c->imag = a->imag*b->real + a->real*b->imag; }


Слайд 28

/* Деление комплексных чисел */ void div(COMPLEX *a, COMPLEX *b, COMPLEX *c) { double znam; if(b->real || b->imag) { znam = b->real*b->real + b->imag*b->imag; c->real = (a->real*b->real + a->imag*b->imag)/znam; c->imag = (a->imag*b->real - a->real*b->imag)/znam; } else printf("\n Деление невозможно"); } /* Присвоение значения*/ void assign_real(double r, COMPLEX *c) { c->real = r; } void assign_imag(double i, COMPLEX *c) { c->imag = i; } /* Вывод на экран комплексного числа */ void printf_complex(COMPLEX *c) { printf("\n%lf + %lf*j",c->real,c->imag); }


Слайд 29

Подумайте, в каком виде будет выводиться комплексное число на экран. Заметим, что можно придумать и более хитрую функцию, которая выводит комплексное число в привычной записи: void printf_complex(COMPLEX *c) { char sign; if (c->imag<0) sign = '-'; else sign = '+'; printf("\n%lf %c j*%lf", c->real, sign, fabs(c->imag)); }


Слайд 30

Вложение структур Возможно включение одних структур в качестве элементов шаблона других. Такая схема определения структуры по существу есть ни что иное, как вложение структур и ее достаточно полно иллюстрирует следующий пример: struct { int pointer; struct { int length; float array[MAX}; } vector[DEPTH]; } stack; в котором массив структур vector является внутренним по отношению к структуре stack


Слайд 31

Приведенное описание может определять стек динамических ограниченных векторов элементов типа float. В этом случае элемент pointer структуры stack следует рассматривать как указатель вершины стека глубины DEPTH, реализованного на базе массива структур vector. Каждая же структура этого массива определяет динамический вектор, текущая длина которого равна length и ограничена сверху константой MAX Для ссылки на отдельные элементы вложенных структур необходимо руководствоваться общим правилом доступа к полям структуры, последовательно применяя операцию получения элемента. Так, например, оператор вида stack.vector[stack.pointer].length++; увеличивает на единицу текущую длину динамического вектора, расположенного на вершине стека


Слайд 32

Несколько более сложным примером вложения структур является их рекурсивное определение, построенное таким образом, что в качестве шаблона внутренней структуры используется шаблон внешней структуры Подобные агрегаты данных могут применяться, например, для представления бинарных деревьев, алгоритмы поиска для которых носят ярко выраженный рекурсивный характер. Действительно, структура со следующим шаблоном struct TNODE { char word[30]; struct TNODE *left; struct TNODE *right; }; может определять узел бинарного дерева, в котором располагается символьный массив word и из которого можно спуститься вниз по дереву в двух возможных направлениях left и right


Слайд 33

Структуры и функции Совершенно очевидно, что отдельные элементы структур, являющиеся простыми переменными или указателями произвольного типа, могут быть использованы в качестве аргументов при обращении к функциям Однако более важным является вопрос о возможности передачи через аппарат формальных/фактических параметров структур в целом. Эту операцию наиболее естественно осуществить, используя понятие указателя на структуру Для иллюстрации технических деталей, связанных с передачей и обработкой структур, рассмотрим фрагмент программы, отыскивающей в сводном каталоге книгу, имеющую наиболее ранний год издания. Общая организация данных, необходимая для решения этой задачи, может быть представлена при помощи структурного шаблона BOOK


Слайд 34

#include <stdio.h> #define MAX 300 struct BOOK { char author[30]; /* Автор книги */ char title[256]; /* Название книги */ int year; /* Год издания */ int pages; /* Количество страниц */ }; /* Поиск самой старой книги */ int find(book) struct BOOK *book; { int cnt, min; min = book->year; for (cnt = 0; cnt < MAX; cnt++, book++) if (book->year < min) min = book->year; return (min); }


Слайд 35

void main() { int min_year; struct BOOK catalog[MAX]; ... min_year = find(catalog); printf("\nСамая старая книга издана в %d году", min_year); } Замечание. Некоторые реализации языка Си допускают использование структур как единого целого в качестве аргументов функций, передавая по значению отдельные элементы таких структур


Слайд 36

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


Слайд 37

Для иллюстрации использования обьединений рассмотрим пример организации данных, обеспечивающих доступ к рабочим регистрам микропроцессоров Intel union REGS { struct { unsigned int ax; unsigned int bx; unsigned int cx; unsigned int dx; } x; struct { unsigned char al, ah; unsigned char bl, bh; unsigned char cl, ch; unsigned char dl, dh; } h; } regs;


Слайд 38

Здесь элементы внутренних структур x и h размещены в одной и той же области памяти, в которую будет пересылаться содержимое рабочих регистров (скажем, при помощи программы, написанной на языке ассемблера). При этом обращение вида regs.x.ax моделирует доступ к регистру AX микропроцессора, а выражения regs.h.al и regs.h.ah обеспечивают соответственно доступ к младшему AL и старшему AH байтам этого регистра


Слайд 39

Перечисления Тип данных перечисление позволяет определить набор символических имен, связав с каждым из них числовое значение целого типа Описания объединений имеют тот же самый формат, что и описания структур только вместо ключевого слова struct используется enum Каждый идентификатор в этом списке именует один элемент из множества перечисляемых значений. По умолчанию первый из них получает значение нуль, второй - значение единица и т. д. Опция = constant-expression позволяет нарушить стандартное правило назначения числовых значений именам из этого списка, причем константное выражение должно иметь тип int. Допустимым также является совпадение числовых значений различных имен в списке


Слайд 40

В следующем примере определяется перечисление с именем day и объявляется переменная workday, имеющая тип перечисление: enum day { saturday, sunday = 0, monday, tuesday, wednesday, thursday, friday } workday; Значение нуль связывается с идентификатором saturday по умолчанию, а идентификатору sunday оно же присваивается явным образом. Остальные пять имен в этом списке последовательно получают значения от 1 до 5


×

HTML:





Ссылка: