Присваивание указателей друг другу 3 страница

printf(“%d”, m1.n);

В общем виде доступ к членам структуры с помощью оператора точка выглядит так:

имя_объекта.имя_члена

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

struct base m1, m2, m3;

m1 = m2; // присваиваем одну структуру другой

m1 = m2 = m3;

8.3. Вложенные структуры

Совпадающие элементы двух структур могут быть объединены в третьей структуре. Этот способ используется, например, когда в нескольких структурах имеется несколько совпадающих полей. Такую структуру нужно определить только один раз, а затем использовать как поле другой структуры. Если структура является членом другой структуры, то такая структура называется вложенной.

Допустим, имеется две структуры:

struct base1

{

int quant;

float cost;

char note[100];

};

struct base2

{

int n;

float cost;

char note[100];

};

Эти структуры содержат разные данные, но имеют совпадающие поля (cost и note), которые могут быть объединены в третью структуру.

struct base3

{

float cost;

char note[100];

};

Следующим образом можно использовать эту структуру как элемент другой структуры:

struct base1

{

int quant;

base3 thing;

} m1;

struct base2

{

int n;

base3 thing;

} m2;

В этом описании – 3 структуры, а в структурах base1 и base2 – по 2 элемента.

Можно также присваивать значения элементам вложенной структуры при помощи оператора точка, но при этом нужно использовать вложенность в операторе точно так же, как и в самой структуре. Например, для присвоения полю cost 2-ой структуры значения 2.3 нужно записать следующее:

m2.thing.cost = 2.3;

Аналогично - для присвоения полю cost 1-ой структуры значения 2.3 нужно записать следующее:

m1.thing.cost = 2.3;

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

Указатель на структуру объявляется с помощью символа *, который ставится перед именем самой структуры. Объявление:

struct base *p; // объявление указателя p на данные типа base

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

Для получения адреса структурной переменной перед её именем нужно поставить оператор &.

Теперь, чтобы получить доступ к членам структуры нужно использовать оператор стрелка ->. Альтернативный способ доступа – использование оператора точка., однако до этого необходимо разыменовать указатель на структуру, т.е. (*имя_указателя_на_структуру).имя_поля. Следующий пример показывает, как получить доступ к полям n и cost структурной переменной m1 через указатель *p:

struct base m1, *p = &m1;

p->n = 1; // Можно (*p).n = 1;

p->cost = 1.2; // Можно (*p).cost = 1.2;

Необходимо помнить, что оператор точка используется при работе с самой структурой, а оператор стрелка – при работе с указателем на структуру.

Выделение под структурную переменную динамической памяти:

p = (struct base*) malloc(sizeof(struct base));

p будет содержать адрес младшего байта выделенного блока памяти, равного размеру шаблона.

++p->cost; // это выражение увеличивает cost на 1,

// а не р, так как оно эквивалентно выражению

// ++(p->cost);

(++p)->cost; // сначала увеличится p на 1 до доступа к cost,

// т. е. увеличится p на sizeof тип

(p++)->cost; // увеличивает p после доступа к cost

8.5. Массивы структурных переменных

При объявлении массива структур в квадратных скобках пишется количество резервируемых для дальнейшего использования структур. Например, следующий код – создание 100 структур mas, каждая из которых состоит из 5 элементов:

struct base

{

int n;

char name[20];

float cost;

int quant;

char note[100];

};

struct base mas[100]; // объявление массива структур

// типа base из 100 элементов

Но нужно быть осторожным при использовании массивов структур, поскольку они занимают много места в памяти.

Оператор точка работает с элементами массива структур точно так же, как и с обычными структурными переменными.

mas[i].n = 10; // полю n i-той структуры присваивается

// значение 10

mas[i].name[j] = ‘a’; // j-тому элементу поля name

// i-той структуры

// присваивается значение ‘a’

Можно использовать для присвоения значений элементам массива указатель:

p = &mas[0]; // указателю p присваивается адрес

// первой структуры

(p+i)->n; // обращение к i-тому элементу, i увеличивается

// на sizeof(struct base).

Также одной операцией присваивания можно присвоить одной структуре данные, находящиеся в другой структуре:

mas[i] = mas[j];

Можно использовать указатель для присвоения значений элементов массива друг другу:

*(mas + i) = *(mas + j);

8.6. Передача функциям структурных переменных

В некоторых случаях приходится передавать функциям в качестве параметров отдельные поля структур или даже структуры целиком. Язык Си предоставляет программисту несколько способов решения этой задачи.

Например, имеется следующая структура:

struct base

{

int n;

char name[20];

float cost;

int quant;

char note[100];

} m1;

и пусть f1(), f2(), f3() – некоторые функции. Тогда члены этой структуры передаются этим функциям следующим образом:

f1(m1.n); // функции f1 передаётся значение n

f2(m1.name); // функции f1 передаётся адрес name

f3(m1.name[i]); // функции f1 передаётся значение

// i-того элемента в массиве name

Чтобы передать адреса членов этой структуры функции, можно написать следующее:

f1(&m1.n); // функции f1 передаётся адрес n

f2(m1.name); // функции f1 передаётся адрес name

f3(&m1.name[i]); // функции f1 передаётся адрес

// i-того элемента в массиве name

Для того чтобы использовать структурную переменную в качестве аргумента функции (если не нужно изменять значения, находящиеся в ней), следует использовать способ вызова по значению. Если же имеется необходимость в изменении значений, надо передавать не саму структурную переменную, а указатель на неё.

Например, нужно умножить 2 числа, которые являются элементами структуры. Это можно сделать несколькими способами:

1. Передать функции в качестве параметров члены структуры:

mult(m1.cost, m1.quant); // функции mult передаются

// значения cost и quant

...

float mult(float cost, int quant) // объявление функции mult

{

return (cost * quant); // выполняется само умножение

}

2. Передать функции в качестве параметра саму структуру:

mult(m1); // функции mult передаётся

// структурная переменная m1

...

float mult(struct base m1) // объявление функции mult

{

return (m1.cost * m1.quant); // выполняется само умножение

}

3. Передать функции в качестве параметра указатель на структуру:

mult(&m1); // функции mult передаётся адрес

// структурной переменной m1

...

float mult(struct base *p) // объявление функции mult

{

return (p->cost * p->quant); // выполняется само умножение

}

Нужно помнить, что 3-й вариант выполняется намного быстрее, особенно, когда структуры довольно громоздкие.

Также необходимо помнить, что тип аргумента функции должен соответствовать типу параметра.

Точно таким же образом функции передаётся массив структур. Путём передачи непосредственно самого массива структур:

struct base mas[5]; // объявление массива структур,

// состоящего из 6-ти элементов

f1(mas); // передача функции f1 массива структур mas

f1(struct base mas[])

{

...

mas[i].n = 1;

...

}

Либо путём передачи функции указателя на массив структур:

f1(struct base *p)

{

...

(p + i)->n = 1; // Можно также p[i].n = 1

// или (*(p + i)).n = 1

...

}

8.7. Оператор typedef

Используя ключевое слово typedef, можно определять новые типы данных (точнее, определять новое имя для уже существующего типа). Это может быть полезным при обеспечении переносимости программ или для более удобного представления типов данных.

Общий вид оператора typedef такой:

typedef тип новое_имя_типа;

где тип – имя любого типа данных Си, а новое_имя_типа – новое имя этого типа, которое будет использоваться совместно с этим типом данных.

Например, если в коде программы по ошибке вместо int написано integer, можно решить эту проблему разными способами, в том числе и следующим:

typedef int integer;

Однако нужно помнить, что новый тип данных не создаётся, а только определяется новое имя для уже существующего типа.

8.8. Поля битов в структурах

Поля битов позволяют помещать, например, в ячейку памяти типа int, несколько различных переменных. Поле представляет собой набор смежных бит, внутри одной переменной типа int.

Синтаксис определения и обработки полей базируется на структурах. В общем виде определение поля следующее:

тип имя: длина;

Тип может быть signed int или unsigned int. При этом каждому полю выделяется столько бит, сколько указано.

struct

{

unsigned int pol:1;

unsigned m:1;

int k:2;

} stat;

Обращение к полям осуществляется следующим образом

stat.pol = 0;

Как и элемент структурной переменной, каждое поле доступно с помощью оператора точка.

Поля позволяют рационально использовать свободную память. Однако, существуют и минусы их использования: невозможно получить адрес поля; манипуляции с битовыми полями машинно-зависимы (например, в некоторых машинах битовые поля могут пересекать границы машинного слова, тогда как в других машинах это недопустимо); использование полей битов может привести к тому, что компилятор будет генерировать машинный код, который выполняется с низкой скоростью (приходится использовать дополнительные операции машинного языка для получения доступа к отдельным частям адресуемых элементов памяти).

8.9. Объединения

Объединение внешне напоминает структуры и может хранить в различные моменты времени данные различного типа и размера. Как и для структур, объявление объединения состоит из:

1. задание шаблона объединения;

2. объявление переменной типа объединения.

Объявление объединения начинается с ключевого слова union и в общем случае выглядит следующим образом:

union [имя_типа_объединения]

{

тип имя_члена;

тип имя_члена;

.

.

.

тип имя_члена;

} [одна или более переменных объединения];

Например:

union pole { int n; float m; char s; } var;

По сути, объединения – это структуры с нулевым смещением элементов структуры относительно ее начала. Объем выделяемой памяти под объединение равен размеру самого большого элемента в объединении.

Доступ к членам объединения осуществляется с помощью оператора точка (для получения доступа к объединению с помощью указателя используется оператор стрелка ->).

var.m = 1; // элементу m из var присваивается значение 1

void f1(union pole *p)

{

...

p->m = 2; // элементу m из var присваивается значение 2

...

}

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

var.m = 0; // теперь все члены объединения равны 0

var.s = 65; // после этого младший байт двух остальных

// членов объединения станет равным 65, т.е.,

// например, при чтении var.n получим тоже 65

8.10. Перечисления

Перечисляемый тип представляет собой упорядоченное множество элементов, доступ к которым осуществляется по имени. Этот тип позволяет улучшить читаемость текста программы.

Синтаксис для задания данных переменных подобен синтаксису объявления структурной переменной и в общем виде выглядит так:

enum имя_типа_перечисл {список_перечисл} список_переменных;

enum month{Jan,Feb,Mar,...}; // объявляется перечисление

// с именем month, в фигурных

// скобках – возможные

// значения данной переменной

enum month m1; // m1 объявляется в качестве

// переменной типа month

m1 = Jan; // m1 присваивается Jan

Элементы списка, указанные в шаблоне, представляют собой константы, которые обозначаются идентификатором. Им соответствуют неявно значения, начиная с 0, с последующим увеличением на 1. Выражение в шаблоне можно проинициализировать, т.е. назначить отдельному элементу перечисления явно какое-либо значение.

Число байт, отводимое под переменную перечисления, зависит от количества и значений констант в шаблоне.

Если все значения констант могут быть представлены значениями типа unsigned char, то под переменную m1 отведется 1 байт, если не хватает – 2 байта.

Имя переменной может использоваться в выражениях, например

if ((m1 < Mar) || (m1 > Nov))

printf(“Winter”);

else

{

if (m1 < Jun)

printf(“Spring”);

else

{

if (m1 < Sep)

printf(“Summer”);

else

printf(“Autumn”);

}

}

9. Динамические структуры данных

9.1. Общие сведения

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

Создание динамических структур требует динамического распределения памяти. Это дает возможность заранее не учитывать объем требуемой памяти, а в процессе выполнения программы увеличивать ее объем для хранения добавленных элементов или освобождать при их удалении.

В Си для этого существуют функции calloc, malloc и free.

Функции malloc и calloc служат для выделения памяти в динамической куче, а free – для ее освобождения.

9.2. Связные списки

9.2.1. Односвязные списки

Список – это линейная динамическая структура данных, число элементов которой может изменяться по мере их добавления и/или удаления.

Список состоит из элементов, называемых узлами. Каждый узел содержит в себе указатель на адрес, где хранится следующий элемент списка. Доступ к списку осуществляется через внешний указатель, который объявляется в программе и указывает на первый элемент. Указатель на первый элемент списка называется головой, а последний – хвостом.

Следует отметить, что узлы связных списков обычно не хранятся в памяти друг за другом, как элементы массива.

В зависимости от организации связи между узлами списка различают его различные виды.

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

На рис. 9.1 приведен пример односвязного направленного списка. Узел данного списка состоит из поля данных element типа int и указателя на следующий элемент NextPtr, указатель на первый элемент – HeadPtr.

Структура, описывающаясоздаваемый список:

struct spisok

{

int element;

struct spisok *nextPtr;

};

Рис. 9.1. Односвязный список

Если список пуст, то указатель на список (headPtr) будет содержать NULL, и в этом случае список попросту будет заполняться в том порядке, в котором будут вводиться данные. Ниже приведена программа по созданию данного списка.

// Программа, демонстрирующая создание односвязного списка

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

// структура, описывающая создаваемый список

struct spisok

{

int element;

struct spisok *nextPtr;

};

typedef spisok Spisok;

typedef Spisok *SpisokPtr;

void createSpisok(SpisokPtr *firstPtr); // описание прототипа

// функции создания

void main()

{

clrscr();

SpisokPtr headPtr = NULL;

int a;

printf(“Vvedite elementi:\n”);

createSpisok(&headPtr);

}

// функция создания односвязного списка

// в качестве параметра получает указатель на начало списка

void createSpisok(SpisokPtr *firstPtr)

{

SpisokPtr newPtr;

int value;

scanf(“%d”, &value);

// выделение памяти для нового элемента списка

newPtr = (Spisok *) malloc(sizeof(Spisok));

if ((newPtr!= NULL) && (value!= 1))

{

newPtr->element = value;

newPtr->nextPtr = *firstPtr; // список сдвигается на один

// элемент, путем

*firstPtr = newPtr; // вставки на первое

// место нового элемента

// рекурсивный вызов функции создания

createSpisok(&((*firstPtr)->nextPtr));

}

else

printf(“Error!”);

}

Для того чтобы вставить новый элемент в уже имеющийся список, необходимо разорвать связь между узлами списка, куда вставляется новый элемент. Для этого указателю узла, расположенного перед вставляемым элементом, необходимо присвоить значение адреса, по которому была выделена память для элемента, и в свою очередь, указателю, содержащемуся во вставляемом узле, присвоить адрес узла, расположенного после вставляемого элемента (рис. 9.2).

Рис. 9.2. Вставка элемента в список

// Функция вставки элемента в список

void insertElement(SpisokPtr *firstPtr, int value)

{

SpisokPtr newPtr, previousPtr, workPtr;

newPtr = (Spisok *) malloc(sizeof(Spisok));

if (newPtr!= NULL)

{

newPtr->element = value;

newPtr->nextPtr = NULL;

workPtr = *firstPtr; // некоторому рабочему указателю

// присваивается значение указателя

// на первый элемент списка

previousPtr = NULL; // значение предыдущего указателя

// равно NULL

while (workPtr!= NULL && value > workPtr->element)

{

previousPtr = workPtr; // происходит продвижение

// по списку

workPtr = workPtr->nextPtr;

}

previousPtr->nextPtr = newPtr; // вставка нового элемента

// в список

newPtr->nextPtr = workPtr;

}

else

printf("Error!");

}

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

// Функция удаления элемента из списка

void deleteElement(SpisokPtr *firstPtr, int value)

{

SpisokPtr newPtr, predPtr, workPtr;

if (*firstPtr!= NULL)

{

workPtr = *firstPtr;

predPtr = NULL;

//пока не конец списка или не найден искомый элемент

while (workPtr!= NULL && value > workPtr->element)

{

predPtr = workPtr; //перемещение по списку

workPtr = workPtr->nextPtr;

}

if (predPtr!= NULL)

{

// если удаляемый элемент находится не в начале списка

predPtr->nextPtr = workPtr->nextPtr;

free(workPtr);

}

else

{

predPtr = *firstPtr; // если в начале

*firstPtr = (*firstPtr)->nextPtr;

free(predPtr);

}

}

else

printf("Error!");

}

9.2.2. Двусвязные списки

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

На рис 9.3 изображен двусвязный список, каждый узел которого включает в себя поле данных типа char, указатель на следующий элемент – nextPtr и указатель на предыдущий элемент – predPtr. Указатель на начало списка – HeadPtr, на конец – LastPtr.

Рис. 9.3. Двусвязный список

9.2.3. Циклические списки

Циклические связные списки отличаются от обычных только одним: последний узел ссылается не в NULL, а на первый узел данного списка, то есть на «начало» списка. Пустой циклический список, таким образом, содержит единственный узел, который указывает сам на себя. При добавлении элементов, последний узел будет указывать на первый узел (рис. 9.4).

Циклические списки во многом значительно упрощают разработку алгоритмов.

а) однонаправленный связный циклический список

б) двусвязный циклический список

Рис. 9.4. Циклические списки

9.3. Стеки

Стек представляет собой упорядоченный набор элементов, доступ к которым осуществляется только с одного конца, называемого вершиной стека. Проще говоря, стек – это вид связного списка, вставку и удаление элементов которого можно совершить только с одного конца – из вершины стека. Стек организован по принципу LIFO (Last Input First Output) – “последним вошел, первым вышел”. Стек, аналогично списку, состоит из связных узлов, каждый из которых представляет собой поле данных и указатель, содержащий адрес следующего элемента. Указатель последнего элемента имеет значение NULL, чтобы тем самым обозначить конец стека (рис. 9.5).

Рис. 9.5. Стек

Над стеком выполняются две основные операции: занести элемент данных в стек – функция PUSH, и извлечь элемент данных из вершины стека – функция POP.

Ниже приведено программное описание стека. Он содержит два поля: поле данных типа char и указатель на структуру того же типа, т.е. на следующий элемент стека.

struct Stack

{

char letter;

struct Stack *nextPtr;

};

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

typedef Stack *StackPtr;

void push(StackPtr *beginPtr, char value)

{

StackPtr newPtr;

//выделение памяти под элемент

newPtr = (Stack *) malloc(sizeof(Stack));

if (newPtr!= NULL)

{

newPtr->letter = value;

newPtr->nextPtr = *beginPtr; // помещение элемента

*beginPtr = newPtr; // в стек

}

else

printf("Ошибка выделения памяти!!!");

}

Функция poр получает в качестве параметров указатель на начало стека, а возвращает значение, которое оттуда извлекает, т.е. элемент данных, который находился в вершине стека. Для удаления элемента рабочему указателю присваивается значения указателя на начало стека. В свою очередь, значению указателя на начало стека присваивается значение указателя на следующий элемент стека, а динамическая память выделенная под удаляемый элемент освобождается при помощи функции free.

char pop(StackPtr *beginPtr)

{

char popValue;

StackPtr tempPtr;

tempPtr = *beginPtr;

popValue = (*beginPtr)->letter; // присваивание значения

// возвращаемого элемента

// переопределение указателя на начало стека

*beginPtr = (*beginPtr)->NextPtr;

free(tempPtr); //освобождение памяти

return popValue;

}

При использовании стека в программе, следует очистить его, когда в нем уже не будет надобности, это сэкономит машинные ресурсы.

9.4. Очереди

Очередь – это также подвид списка, это набор данных, доступ к которым осуществляется с двух концов. Запись осуществляется с конца очереди, называемого хвостом, а удаление из начала очереди. Принцип организации очереди – FIFO (First Input First Output) – «Первым вошел, первым вышел» -- противоположен принципу организации стека.

Структура очереди не отличается от структуры односвязного списка или стека. Она состоит из поля данных, в данном случае, элемента типа int и указателя на следующий элемент очереди (рис. 9.6):

struct Queue

{

int element;

struct Queue *nextPtr;

};

Рис. 9.6. Очередь

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

typedef struct queue *QueuePtr;

void insertElement(QueuePtr *firstPtr,

QueuePtr *endPtr,