2.4. Представление основных структур программирования: итерация, ветвление, повторение; процедуры.

Итерация – повторение – цикл.

Оператор if (ветвление)

if (выражение) оператор1; [else оператор2;]

Выполнение оператора if начинается с вычисления выражения.

Далее выполнение осуществляется по следующей схеме:

- если выражение истинно (т.е. отлично от 0), то выполняется оператор1.

- если выражение ложно (т.е. равно 0),то выполняется оператор2.

- если выражение ложно и отсутствует оператор2, то выполняется следующий за if оператор. Допускается использование вложенных операторов if.

Оператор for - это наиболее общий способ организации цикла (с известным количеством повторений). for (выражение 1; выражение 2; выражение 3) тело;

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

Схема выполнения оператора for:

1. Вычисляется выражение 1.

2. Вычисляется выражение 2.

3. Если значения выражения 2 отлично от нуля (истина), выполняется тело цикла, вычисляется выражение 3 и осуществляется переход к пункту 2, если выражение 2 равно нулю (ложь), то управление передается на оператор, следующий за оператором for.

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

Оператор while (с предусловием)

while (выражение) тело;

Схема выполнения оператора while следующая:

1. Вычисляется выражение.

2. Если выражение ложно, то выполнение оператора while заканчивается и выполняется следующий по порядку оператор. Если выражение истинно, то выполняется тело оператора while.

3. Процесс повторяется с пункта 1.

Оператор do while (с постусловием)

Используется в тех случаях, когда необходимо выполнить тело цикла хотя бы один раз. do тело while (выражение);

Схема выполнения оператора do while :

1. Выполняется тело цикла (которое может быть составным оператором).

2. Вычисляется выражение.

3. Если выражение ложно, то выполнение оператора do while заканчивается и выполняется следующий по порядку оператор. Если выражение истинно, то выполнение оператора продолжается с пункта Итерация – цикл for.

2.5 Типы данных, определяемые пользователем; структуры;файлы.

Для того, чтобы сделать программу более ясной, можно задать типу новое имя с помощью ключевого слова typedef: typedef тип новое_имя [размерность];

Перечисления (enum)

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

enum [имя_типа] {список_констант};

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

Структура (struct)

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

struct [имя] {список полей}

Список полей – перечень объявлений. Каждое объявление состоит из спецификации типа, идентификатора и ;. Доступ: идентификатор.имя поля, обращение к значению то адресу идентификатор->имя поля.

Битовые поля

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

Спецификация_типа идентификатор: константное выражение;

Объединения (union)

Объединения предназначены для хранения данных различного типа в одной и той же области памяти.

union [имя] {список полей}

Файл

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

1. просмотр (последовательное продвижение по файлу сначала). В процессе просмотра изменять значения компонентов на новые запрещается.

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

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

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

(В Си предусмотрены два вида операций ввода/вывода с файлами: форматированный и бинарный (двоичной) … ).

2.6. Динамические структуры данных; списки: основные виды и способы реализации Области значений. Описатели

…появляется необходимость динамически выд5лять память, поэтому…

Список – базовая структура, позволяющая определить любую структуру данных. Указатели вводятся в языки высокого уровня с целью поддержания списковых структур. Элемент списка представляет собой объект, содержащий информационное поле и 1 или несколько адресных полей, предназначенных для связи с другими элементами списка. При отсутствии связи адресное поле равно специальному значению указателя, гарантировано ссылающемуся ни какой объект (NULL – нулевой указатель).

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

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

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

Создание связного списка.

Выделить память для хранения адреса головы;

Выделить память для хранения элементов списка;

Обнулить поле адреса;

Записать в поле данных содержащую информацию;

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

Добавление элемента в конец списка.

Присвоить указателю адрес головы списка;

Проанализировать значение поля адреса. Пока оно не равно 0, присваивать указателю значение поля адреса.

Создать элемент списка и записать его в поле адрес конца списка.

Просмотр связного списка.

создание списка

struct Node {

char word[40];

int count;

Node *next;

};

typedef Node *PNode;

создание узла

Pnode CreateNode ( char NewWord[] )

{

PNode NewNode = new Node;

strcpy(NewNode->word, NewWord);

NewNode->count = 1;

NewNode->next = NULL;

return NewNode;

}

доб узла в нач

void AddFirst(PNode NewNode)

{

NewNode->next = Head;

Head = NewNode;

}

Например, следующая процедура ищет в списке элемент, соответствующий заданному слову

(для которого поле word совпадает с заданной строкой NewWord), и возвращает его адрес или

NULL, если такого узла нет.

void Find (PNode Head, char NewWord[])

{

PNode q = Head;

while (q && strcmp(q->word, NewWord))

q = q->next;

return q;

}

доб после заданного

void AddAfter (PNode p, PNode NewNode)

{

NewNode->next = p->next;

p->next = NewNode;

}

доб перед заданным

void AddBefore(PNode p, PNode NewNode)

{

PNode q = Head;

if (Head == p) {

AddFirst(Head, NewNode);

return;

}

while (q && q->next!=p) q = q->next;

if (q) AddAfter(q, NewNode);

}

доб узла в конец списка

void AddLast(PNode NewNode)

{

PNode q = Head;

if (Head == NULL) {

AddFirst(Head, NewNode);

return;

}

while (q->next) q = q->next;

AddAfter(q, NewNode);

}

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

если сравнение дает положительный результат, то выдать элемент списка.

если достигнуто значение адреса 0, выдать сообщение, что элемент не найден.

Добавление элемента в произвольное место списка.

Найти заданный элемент, сохранить значение его поля адреса, создать новый элемент, записать адрес нового элемента в поле адреса заданного (найденного) элемента.

Записать в поле адреса добавляемого элемента сохраненный адрес следующего элемента.

Процедура добавления элемента в произвольное место списка показывает преимущество связного хранения перед последовательным (массивы).

Удаление элемента из конца списка.

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

Удаление произвольного элемента связного списка.

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

Кольцевой односвязный список

Структура аналогична структуре односвязного

однонаправленного списка, за исключением

того, что в поле адреса конечного элемента

хранится адрес головы списка.

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

Двунаправленный список

объявл

struct Node {

char word[40];

int count;

Node *next, *prev;

};

typedef Node *PNode;

доб в нач

void AddFirst(PNode NewNode)

{

NewNode->next = Head;

NewNode->prev = NULL;

if ( Head ) Head->prev = NewNode;

Head = NewNode;

if ( ! Tail ) Tail = Head;

}

конец head<->taid next<->prev

доб после задан

void AddAfter (PNode p, PNode NewNode)

{

if ( ! p->next )

AddLast (Head, Tail, NewNode);

else {

NewNode->next = p->next;

NewNode->prev = p;

p->next->prev = NewNode;

p->next = NewNode;

}

}

удаление

void Delete(PNode &Head, PNode &Tail, PNode OldNode)

{

if (Head == OldNode) {

Head = OldNode->next;

if ( Head )

Head->prev = NULL;

else Tail = NULL;

}

else {

OldNode->prev->next = OldNode->next;

if ( OldNode->next )

OldNode->next->prev = OldNode->prev;

else Tail = NULL;

}

delete OldNode;

}

Каждый элемент списка содержит адрес не

только следующего элемента, но и

предыдущего. Голова списка в адресе

предыдущего элемента содержит NULL.

Кольцевой двунаправленный список

Поле предыдущий элемент головы списка

содержит адрес конца списка.

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

Каждый элемент списка содержит 2 ссылки

на 2 следующих элемента.

Двунаправленный (двусвязный) список

Элемент такого списка помимо ссылки на

левый и правый следующие элементы

содержит ссылку на предыдущий элемент.

Многосвязный список

Каждый элемент содержит n-ссылок

на следующие элементы.

( Преимущество последовательного хранения: при известном размере каждого элемента возможен доступ по индексу элемента.

Недостатки: необходимость резервирования предполагаемого максимального размера, невозможность добавления и исключения элементов, а только модификация.

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

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

Дисциплина обслуживания.

Очередь: «first-in, first-out» (FIFO).

Стек:«last-in, first-out» (LIFO).

Дек – двунаправленная очередь – это

линейный список, у которого операции

добавления и удаления элементов и

доступа к элементам возможны как вначале так и в конце списка.

стек

объявление

struct Stack {

PNode Head, Tail;

};

добавление на верш

void Push ( Stack &S, int i )

{

PNode NewNode;

NewNode = new Node;

NewNode->data = i;

NewNode->next = S.Head;

NewNode->prev = NULL;

if ( S.Head ) S.Head->prev = NewNode;

S.Head = NewNode;

if ( ! S.Tail ) S.Tail = S.Head;

}

удал с верш

int Pop ( Stack &S )

{

PNode TopNode = S.Head;

int i;

if ( ! TopNode ) return 0;

i = TopNode->data;

S.Head = TopNode->next;

if ( S.Head ) S.Head->prev = NULL;

else S.Tail = NULL;

delete TopNode;

return i;

}

дек

доб-у эл-та в конец

void PushTail ( Stack &S, int i )

{

PNode NewNode = new Node;

NewNode->data = i;

NewNode->prev = S.Tail;

NewNode->next = NULL;

if ( S.Tail ) S.Tail->next = NewNode;

S.Tail = NewNode;

if ( ! S.Head ) S.Head = S.Tail;

}

получ посл

int PopTail ( Stack &S )

{

PNode LastNode = S.Tail;

int i;

if ( ! LastNode ) return 0;

i = LastNode->data;

S.Tail = LastNode->prev;

if ( S.Tail ) S.Tail->next = NULL;

else S.Head = NULL;

delete LastNode;

return i;

}