Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
1.Структуры языка СИ.
Структурой в языке C называется совокупность логически связанных переменных различных типов, сгруппированных под одним именем для удобства дальнейшей обработки.
Структура – это способ связать воедино данные разных типов и создать пользовательский тип данных. В языке Pascal подобная конструкция носит название записи.
Структура – тип данных, задаваемый пользователем. В общем случае при работе со структурами следует выделить четыре момента:
- объявление и определение типа структуры,
- объявление структурной переменной,
- инициализация структурной переменной,
- использование структурной переменной.
Определение типа структуры представляется в виде
struct ID
{
<тип> <имя 1-го элемента>;
<тип> <имя 2-го элемента>;
…………
<тип> <имя последнего элемента>;
};
Определение типа структуры начинается с ключевого слова struct и содержит список объявлений, заключенных в фигурные скобки. За словом struct следует имя типа, называемое тегом структуры (tag – ярлык, этикетка). Элементы списка объявлений называются членами структуры или полями. Каждый элемент списка имеет уникальное для данного структурного типа имя. Однако следует заметить, что одни и те же имена полей могут быть использованы в различных структурных типах.
Определение типа структуры представляет собой шаблон (template), предназначенный для создания структурных переменных.
Объявление переменной структурного типа имеет следующий вид:
struct ID var1;
при этом в программе создается переменная с именем var1 типа ID. Все переменные, использующие один шаблон (тип) структуры, имеют одинаковый набор полей, однако различные наборы значений, присвоенные этим полям. При объявлении переменной происходит выделение памяти для размещения переменной. Шаблон структуры позволяет определить размер выделяемой памяти.
В общем случае, под структурную переменную выделяется область памяти не менее суммы длин всех полей структуры, например,
struct list
{
char name[20];
char first_name[40];
int;
}L;
В данном примере объявляется тип структура с именем list, состоящая из трех полей, и переменная с именем L типа struct list,при этом для переменной L выделяется 64 байта памяти.
Отметим, что определение типа структуры может быть задано в программе на внешнем уровне, при этом имя пользовательского типа имеет глобальную видимость (при этом память не выделяется). Определение типа структуры также может быть сделано внутри функции, тогда имя типа структуры имеет локальную видимость.
Создание структурной переменной возможно двумя способами: с использованием шаблона (типа) или без него.
Создание структурной переменной pt на основе шаблона выполняется следующим образом:
struct point //Определение типа структуры
{
int x;int y;
};
……
struct point pt; //Создание структурной переменной
Структурная переменная может быть задана уникальным образом:
struct //Определение анонимного типа структуры
{
char name[20];
char f_name[40];
char s_name[20];
} copymy; //Создание структурной переменной
При размещении в памяти структурной переменной можно выполнить ее инициализацию. Неявная инициализация производится для глобальных переменных, переменных класса static. Структурную переменную можно инициализировать явно при объявлении, формируя список инициализации в виде константных выражений.
Формат: struct ID name_1={значение1, … значениеN};
Внутри фигурных скобок указываются значения полей структуры, например,
struct point pt={105,17};
при этом первое значение записывается в первое поле, второе значение – во второе поле и т. д., а сами значения должны иметь тип, совместимый с типом поля.
Над структурами возможны следующие операции:
- присваивание значений одной структурной переменной другой структурной переменной, при этом обе переменные должны иметь один и тот же тип;
- получение адреса переменной с помощью операции &;
- осуществление доступа к членам структуры.
Присваивание значения одной переменной другой выполняется путем копирования значений соответствующих полей, например:
struct point pt={105,15},pt1;
pt1=pt;
В результате выполнения этого присваивания в pt1.x будет записано значение 105, а в pt1.y – число 15.
Работа со структурной переменной обычно сводится к работе с отдельными полями структуры. Доступ к полю структуры осуществляется с помощью операции. (точка) посредством конструкции вида:
имя_структуры.имя_поля_структуры;
при этом обращение к полю структуры представляет собой переменную того же типа, что и поле, и может применяться везде, где допустимо использование переменных такого типа.
Например,
struct list copy = {"Ivanov","Petr",1980};
Обращение к "Ivanov" имеет вид copy.name. И это будет переменная типа указатель на char. Вывод на экран структуры copy будет иметь вид: printf("%s%s%d\n",copy.name,copy.first_name,copy.i);
Структуры нельзя сравнивать. Сравнивать можно только значения конкретных полей.
К началу главы
12.2. Структуры и функции
Структуры могут быть переданы в функцию в качестве аргументов и могут служить в качестве возвращаемого функцией результата.
Существует три способа передачи структур функциям:
- передача компонентов структуры по частям;
- передача целиком структуры;
- передача указателя на структуру.
Например, в функцию передаются координаты двух точек:
void showrect(struct point p1,struct point p2)
{
printf("Левый верхний угол прямоугольника:%d %d\n",
p1.x, p1.y);
printf("Правый нижний угол прямоугольника:
%d %d\n", p2.x, p2.y);
}
При вызове такой функции ей надо передать две структуры:
struct point pt1={5,5},
pt2={50,50};
showrect(pt1,pt2);
Теперь рассмотрим функцию, возвращающую структуру:
struct point makepoint (int x,int y) /*makepoint – формирует точку по компонентам x и y*/
{
struct point temp;
temp.x = x;
temp.y = y;
return temp;
}
Результат работы этой функции может быть сохранен в специальной переменной и выведен на экран:
struct point buf;
buf=makepoint(10,40);
printf("%d %d\n",buf.x,buf.y);
После выполнения этого фрагмента на экран будут выведены два числа: 10 и 40.
К началу главы
12.3. Указатели на структуру
Если функции передается большая структура, то эффективнее передать указатель на эту структуру, нежели копировать ее в стек целиком. Указатель на структуру по виду ничем не отличается от указателей на обычные переменные.
Формат: struct point *pp;
где pp – указатель на структуру типа struct point, *pp – сама структура, (*pp).x и (*pp).y – члены структуры.
Скобки (*pp).x необходимы, так как приоритет операции (.) выше приоритета операции (*). В случае отсутствия скобок *pp.x понимается как *(pp.x).
Инициализация указателя на структуру выполняется так же, как и инициализация указателей других типов: struct point var1, *S1; здесь var1 – структурная переменная, *S1 – указатель на структуру.
Для определения значения указателя ему нужно присвоить адрес уже сформированной структуры:
S1 = &var1;
Теперь возможно еще одно обращение к элементам структуры:
(*S1).name.
Указатели на структуры используются весьма часто, поэтому для доступа к ее полям была введена короткая форма записи. Если р – указатель на структуру, то p → <поле структуры> зволяет обратиться к указанному полю структурной переменной.
Знак → (стрелка) вводится с клавиатуры с помощью двух символов: '–' (минус) и '>' (больше). Например, pp → x; pp → y.
Операторы доступа к полям структуры (.) и (→) вместе с операторами вызова функции () и индексами массива [] занимают самое высокое положение в иерархии приоритетов операций в языке C.
Указатели на структуру используются в следующих случаях:
· доступ к структурам, размещенным в динамической памяти;
· создание сложных структур данных – списков, деревьев;
· передача структур в качестве параметров в функции.
К началу главы
12.4. Массивы структур
При необходимости хранения некоторых данных в виде нескольких массивов одной размерности, но разного типа, возможна организация массива структур. Наглядно массив структур можно представить в виде таблицы, где столбцы таблицы представляют собой поля структуры, а строки – элементы массива структур.
Например, имеется два разнотипных массива:
char c[N];
int i[N];
Объявление
struct key
{
char c;
int i;
} keytab[N];
создает тип структуры key и объявляет массив keytab[N], каждый элемент которого есть структура типа key.
Возможна запись:
struct key
{
char c;
int i;
};
struct key keytab[N];
Инициализация массива структур выполняется следующим образом:
struct key
{
char c;
int i;
} keytab[]={
'a', 0,
'b', 0
};
В этом примере создается массив на две структуры типа key с именем keytab. Рассмотрим обращение к полю структуры в этом случае – для примера выведем на экран содержимое массива:
for(int i=0;i<2;i++)
printf("%c %d\n",keytab[i].c,keytab[i].i);
При обращении к полю структуры сначала происходит обращение к элементу массива (keytab[i]), а затем только обращение к полю структуры (keytab[i].c).
Доступ к полю элемента массива структур может быть получен через константу-указатель на массив и смещение внутри массива, например, доступ к полю элемента массива с номером i следует записать следующим образом:
(*(keytab+i)).c или (keytab+i)→ c.
Массив структур также может быть передан в функцию в качестве аргумента, передача массива происходит через указатель на массив.
Пример программы, в которой массив точек формируется и выводится на экран с помощью функций:
#include <stdio.h>
#define N 5
struct point
{
int x,y;
};
void form_mas(struct point* mas, int n)
{
printf("Enter koordinates!\n");
for(int i=0;i<n;i++)
{
printf("x→");
scanf("%d",&mas[i].x);
printf("y→");
scanf("%d",&mas[i].y);
}
}
void print_mas(struct point* mas, int n)
{
printf(" x y\n");
for(int i=0; i<n; i++)
printf("%4d %6d\n",(mas+i)→x,(mas+i)→y);
}
int main()
{
struct point Points[N];
form_mas(Points,N);
print_mas(Points,N);
return 0;
}
Функция form_mas() заполняет массив точек, который передан в функцию через указатель mas. Параметр функции n определяет количество элементов массива. Доступ к элементу массива – через операцию . (точка). Выражение &mas[i].x вычисляет адрес элемента структуры mas[i].x, так как операция & имеет более низкий приоритет, чем операции [] и · (точка).
Функция print_mas() выводит массив на экран. Передача массива в функцию происходит также через указатель mas. Параметр n – количество элементов массива. Доступ к элементу массива – через операцию → (стрелка).
К началу главы
12.5. Вложенные структуры
Полем структурной переменной может быть переменная любого типа, в том числе другая структурная переменная. Поле, представляющее собой структуру, называется вложенной структурой.
Тип вложенной структуры должен быть объявлен раньше. Кроме того, структура не может быть вложена в структуру того же типа.
Объявление вложенной структуры:
struct point
{
int x,y;
};
struct rect
{
struct point LUPoint, RDPoint;
char BorderColor[20];
};
struct rect Rect;
В переменной Rect два поля LUPoint (точка, соответствующая левому верхнему углу прямоугольника) и RDPoint (точка, соответствующая правому нижнему углу) представляют собой вложенные структуры. Для доступа к полю вложенной структуры следует сначала обратится к внешней структуре, затем к вложенной: Rect.LUPoint.x.
Пример создания и использования вложенной структуры:
struct rect Rect={10,5,50,25,"White"};
printf("Параметры прямоугольника:\n");
printf("Координаты левого верхнего угла %d %d\n", Rect.LUPoint.x, Rect.LUPoint.y);
printf("Координаты левого верхнего угла %d %d\n", Rect.RDPoint.x, Rect.RDPoint.y);
printf("Цвет границы: %s\n", Rect.BorderColor);
В качестве поля структуры также можно использовать указатели на любые структуры, в том числе на структуры того же типа:
struct PointList
{
int x,y;
struct PointList* LastPoint;
};
Структуры, имеющие в своем составе поля-указатели на такую же структуру, используются для создания сложных структур данных – списков, деревьев.
C++. Динамические массивы
Обычно, объем памяти, необходимый для той или иной переменной, задается еще до процесса компиляции посредством объявления этой переменной. Если же возникает необходимость в создание переменной, размер которой неизвестен заранее, то используют динамическую память. Резервирование и освобождение памяти в программах на C++ может происходить в любой момент времени. Осуществляются операции распределения памяти двумя способами:
с помощью функции malloc, calloc, realloc и free;
посредством оператора new и delete.
Функция malloc резервирует непрерывный блок ячеек памяти для хранения указанного объекта и возвращает указатель на первую ячейку этого блока. Обращение к функции имеет вид:
void *malloc(size);
Здесь size — целое беззнаковое значение, определяющее размер выделяемого участка памяти в байтах. Если резервирование памяти прошло успешно, то функция возвращает переменную типа void *, которую можно привести к любому необходимому типу указателя.
Функция - calloc также предназначена для выделения памяти. Запись ниже означает, что будет выделено num элементов по size байт.
void *calloc (nime, size);
Эта функция возвращает указатель на выделенный участок или NULL при невозможности выделить память. Особенностью функции является обнуление всех выделенных элементов.
Функция realloc изменяет размер выделенной ранее памяти. Обращаются к ней так:
char *realloc (void *p, size);
Здесь p — указатель на область памяти, размер которой нужно изменить на size. Если в результате работы функции меняется адрес области памяти, то новый адрес вернется в качестве результата. Если фактическое значение первого параметра NULL, то функция realloc работает также, как и функция malloc, то есть выделяет участок памяти размером size байт.
Для освобождения выделенной памяти используется функция free. Обращаются к ней так:
void free (void *p size);
Здесь p — указатель на участок памяти, ранее выделенный функциями malloc, calloc или realloc.
Операторы new и delete аналогичны функциям malloc и free. New выделяет память, а его единственный аргумент — это выражение, определяющее количество байтов, которые будут зарезервированы. Возвращает оператор указатель на начало выделенного блока памяти. Оператор delete освобождает память, его аргумент — адрес первой ячейки блока, который необходимо освободить.
Динамический массив — массив переменной длины, память под который выделяется в процессе выполнения программы. Выделение памяти осуществляется функциями calloc, malloc или оператором new. Адрес первого элемента выделенного участка памяти хранится в переменной, объявленной как указатель. Например, следующий оператор означает, что описан указатель mas и ему присвоен адрес начала непрерывной области динамической памяти, выделенной с помощью оператора new:
int *mas=new int[10];
Выделено столько памяти, сколько необходимо для хранения 10 величин типа int.
Фактически, в переменной mas хранится адрес нулевого элемента динамического массива. Следовательно, адрес следующего, первого элемента, в выделенном участке памяти - mas+1, а mas+i является адресом i-го элемента. Обращение к i-му элементу динамического массива можно выполнить, как обычно mas[i], или другим способом *(mas +i). Важно следить за тем, чтобы не выйти за границы выделенного участка памяти.
Когда динамический массив (в любой момент работы программы) перестает быть нужным, то память можно освободить с помощью функции free или оператора delete.
4. Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.[1] Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.
Линейный связный список[править | править исходный текст]
Односвязный список (Однонаправленный связный список)[править | править исходный текст]
Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.
Двусвязный список (Двунаправленный связный список)[править | править исходный текст]
Здесь ссылки в каждом узле указывают на предыдущий и на последующий узел в списке. По двусвязному списку можно передвигаться в любом направлении — как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, так как всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.
XOR-связный список[править | править исходный текст]
Основная статья: XOR-связный список
Кольцевой связный список[править | править исходный текст]
Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний.
Реализация такой структуры происходит на базе линейного списка. В каждом кольцевом списке есть указатель на первый элемент. В этом списке константы NULL не существует.
Также существуют циклические списки с выделенным головным элементом, облегчающие полный проход через список.
5.СТЕКИ
Стек — это особый способ хранения данных, при котором в каждый момент времени доступ возможен только к одному из элементов, а именно к тому, который был занесен в стек последним. Часто главный принцип стека формулируют в виде: “первым пришел — последним вышел” (в англоязычной литературе применяется более строгий термин LIFO — это сокращение от Last In — First Out, что означает последним пришел — первым вышел).
При описании работы стека принято говорить, что он имеет фиксированное основание (нижнюю границу, дно) и подвижную вершину, через которую, собственно, и происходит запись и чтение данных (см. рис. 1).
Рис. 1
В начальный момент времени основание и вершина стека совпадают. По мере записи данных область, занятая информацией (на рис. 1 она закрашена серым цветом), расширяется; вершина стека при этом смещается вверх. При извлечении данных из стека происходит противоположный процесс. Когда стек свободен от данных (вершина и основание совпадают), попытка считывания данных является грубой ошибкой. В другом предельном случае, когда данных чрезмерно много (вершина совпадает с верхней границей области памяти, отведенной под стек), некорректной, напротив, становится запись.
Над стеком можно определить следующие операции:
· добавление нового элемента в стек (общепринят термин PUSH — “заталкивать” в стек);
· извлечение элемента из стека (POP — “выталкивать” из стека);
· операции по изменению верхнего элемента стека (так как операнд один, то такие операции называют “унарными”);
· бинарные операции с двумя извлеченными из стека верхними элементами; результат возвращается обратно в вершину стека.
Подчеркнем, что все приведенные выше принципы настолько общие, что пока никак не связаны с компьютерной реализацией. А теперь подумаем, как практически реализовать стек в памяти машины.
Прежде всего очевидно, что для манипуляций со стеком нужно где-то постоянно хранить координаты (адрес) текущего положения вершины стека. Договоримся называть эту важнейшую характеристику указателем, но пока не будем конкретизировать место его хранения, обозначая в максимально общем виде R — некоторый регистр процессора.
Учитывая, что стек может расти как в сторону увеличения, так и в сторону уменьшения адресов, а также тот факт, что существуют равноправные договоренности о последовательности операций при записи/чтении (например, сначала менять адрес, а потом читать данные или наоборот), возможно предложить несколько разных вариантов организации стека в оперативной памяти (ОЗУ). Тем не менее, несмотря на теоретическое разнообразие, программисты практически всегда строят стек единообразно. А именно, при заполнении стека значение указателя уменьшается, а при извлечении данных — растет. Кроме того, для записи данных используется алгоритм, который можно обозначить как “–(R)”, т.е. сначала значение указателя уменьшается, а затем происходит запись данных. Очевидно, что такой выбор предопределяет алгоритм чтения типа “(R)+”, при котором сперва считываются данные, а затем наращивается указатель стека.
Стек — метод неявной адресации
Как следует из описанных выше принципов, конкретный адрес при обращении к памяти берется из указателя стека. Например, для записи в стек содержимого некоторого регистра Ri достаточно указать команду PUSH Ri, никак не ссылаясь на адрес информации в ОЗУ. Подобные способы обращения к данным, когда адрес данных не указывается, а подразумевается, принято называть неявными.
Стек является одним из образцов неявной адресации, причем очень развитым и необычайно полезным образцом. “Важным преимуществом стека по сравнению с адресной организацией памяти является то, что его элементами можно манипулировать, не адресуясь к ним явно, не называя их имени” [2].
Очевидным преимуществом неявной адресации является короткая форма записи программы и ее практически полная независимость от конкретных адресов ОЗУ (программы, которые способны без изменения исполняться с любого адреса памяти, часто называют перемещаемыми). И хотя это весьма важное с теоретической точки зрения достоинство, истинное значение стекового метода адресации все же не в этом: данный механизм позволяет реализовать многие структуры алгоритмов или данных, которые без него осуществить необычайно сложно. Рассмотрим показательный, хотя и не совсем тривиальный, пример из книги [3].
“Во всех языках программирования есть понятие процедур с локальными переменными. Эти переменные доступны во время выполнения процедуры, но перестают быть доступными после окончания процедуры. Возникает вопрос: где должны храниться такие переменные?
К сожалению, предоставить каждой переменной абсолютный адрес в памяти невозможно. Проблема заключается в том, что процедура может вызывать себя сама… Достаточно сказать, что если процедура вызывается дважды, то хранить ее переменные под конкретными адресами в памяти нельзя, поскольку второй вызов нарушит результаты первого”.
Стековая память является простым и весьма эффективным решением сформулированной проблемы.