ЦЕЛЬ РАБОТЫ

• закрепление навыков работы с пользовательскими структурами данных;
• закрепление навыков составление и отладка программ из нескольких модулей;
• получение навыков работы с файлами;
• получение навыков создания и использования абстрактных структур данных (АСД);
• получение навыков использования и разработки алгоритмов с АСД;

 

ДОПОЛНИТЕЛЬНЫЕ МАТЕРИАЛЫ ДЛЯ ПОДГОТОВКИ

• МООК
  • Алгоритмы: теория и практика. Структуры данных

 

КРИТЕРИИ ОЦЕНКИ

Для выполнения работы на оценку «удовлетворительно»:

• Создать структуру (структуры), соответствующие индивидуальному заданию, с использованием однонаправленного списка
• Реализовать операции:

• • создание списка;
  • изменение списка (добавление и удаление);
  • печать списка (вывод через консоль);

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

Для выполнения работы на оценку «хорошо»:

• Создать структуру (структуры), соответствующие индивидуальному заданию, с использованием двунаправленного списка
• Реализовать операции:

• • создание списка;
  • изменение списка (добавление и удаление);
  • печать списка (вывод через консоль);

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

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

• Ввод данных осуществлять через консоль и из файлов.
• Работу со структурами реализовать в отдельных файлах (cpp и h)
• Обеспечить тестирование, которое должно покрывать основные моменты индивидуального задания
• Выбор тестов через консольное меню, т.е. не обязательно все действия каждого теста (ввод данных, их модификация, вывод данных) осуществлять вручную. При этом должны быть тесты для ввода данных с консоли и из файлов.

Для выполнения работы на оценку «отлично»:

• Создать структуру (структуры), соответствующие индивидуальному заданию, с использованием бинарного дерева

• Создать функции для выполнения следующих операций над двоичным деревом:

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

• Функции обработки, указанные в индивидуальном варианте задания. В случае с реализацией в форме деревьев согласовать и скорректировать эти функции с преподавателем.
• В программе должна быть предусмотрена обработка исключительных состояний (конец данных, недопустимость преобразования вычислительных состояний)
• Ввод данных осуществлять через консоль и из файлов.
• Обеспечить тестирование, которое должно покрывать основные моменты индивидуального задания. Для каждого теста реализовать специальную функцию.
• Выбор тестов через консольное меню, т.е. не обязательно все действия каждого теста (ввод данных, их модификация, вывод данных) осуществлять вручную. Можно создать для каждого теста функцию и вызывать её. При этом должны быть тесты для ввода данных с консоли и из файлов.
• Работу со структурами и тестированием реализовать в отдельных файлах (cpp и h)

 

Оглавление

Список. 5

Базовые определения. 5

Добавление элемента к пустому однонаправленному списку. 6

Добавление элемента к пустому двунаправленному списку. 7

Добавление элемента в начало непустого однонаправленного списка. 7

Добавление элемента в начало непустого двунаправленного списка. 8

Добавление элемента в конец непустого однонаправленного списка. 8

Добавление элемента в конец непустого двунаправленного списка. 9

Вывод списка в прямом направлении. 9

Вывод двунаправленного списка в обратном направлении. 10

Алгоритм удаления элемента с заданным номером из двунаправленного списка. 10

Бинарные деревья и деревья поиска. 11

Алгоритмы включения узла в дерево. 13

Алгоритм удаления узла из дерева поиска. 14

Об алгоритмах обхода дерева. 18

О структурах С++. 20

Таблица спецификаций структур. 23

Индивидуальные задания и примечания. 24

Содержание отчёта. 24

Варианты.. 24

Примечания. 26

Базовые определения

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

Логический порядок следования может не совпадать с физическим расположением элементов в памяти компьютера. Объединение элементов в список производится по разным критериям в зависимости от решаемой задачи. Например, если в виде списка организуется информация об авиарейсах, то понятие «следующий» может относиться к авиарейсу, время вылета которого позднее, чем время вылета рейса, который будет «предыдущим».

Графически списковая структура данных имеет вид:

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

Списки подразделяются на однонаправленные и двунаправленные.

Однонаправленным списком является такой, элементы которого связаны адресами или ссылками в  одном направлении.

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

 

В любом списке кроме совокупности элементов необходимо задать адрес его первого элемента («голову» списка), а в двунаправленном списке  удобно  хранить  ещё  и  адрес  последнего  элемента — «хвост» списка с тем, чтобы была  возможность двигаться как от начала списка к его концу, так и наоборот.

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

Здесь и в дальнейшем при описании различных операций над списками примем следующие обозначения: элемент списка обозначим OBJECT; в его состав для однонаправленного списка входят поля: DATA — данные и NEXT — указатель (адрес) следующего элемента. Для двунаправленного списка каждый элемент содержит поля DATA, NEXT и PREV (адрес предыдущего элемента). Голову списка обозначим START, хвост обозначим END.

Пример. Пусть числа 3, 2, 8, 15, 7, 9 записываются в память в порядке их поступления. Если их связать в однонаправленный список по возрастанию, то список будет иметь вид:

 

Далее рассмотрим основные алгоритмы работы со списками.

 

Добавление элемента к пустому однонаправленному списку

Вначале START=0

1. Размещение элемента списка OBJECT.
2. Заполнение OBJECT->DATA.
3. OBJECT->NEXT=0
4. START=OBJECT

Список после размещения элемента:

 

Добавление элемента к пустому двунаправленному списку

Вначале START=0, END=0

1. Размещение элемента списка OBJECT.
2. Заполнение OBJECT->DATA.
3. OBJECT->NEXT=0, OBJECT->PREV=0
4. START=OBJECT, END=OBJECT

Список после размещения элемента:

Добавление элемента в начало непустого однонаправленного списка

Вначале START#0

1. Размещение элемента списка OBJECT.
2. Заполнение OBJECT->DATA.
3. OBJECT->NEXT=START
4. START=OBJECT

Список после размещения элемента:

Добавление элемента в начало непустого двунаправленного списка

Вначале START#0

1. Размещение элемента списка OBJECT.
2. Заполнение OBJECT->DATA.
3. OBJECT->NEXT=START
4. OBJECT->PREV=0
5. START->PREV=OBJECT
6. START=OBJECT

Список после размещения элемента:

Добавление элемента в конец непустого однонаправленного списка

Вначале START#0

1. Размещение элемента списка OBJECT.
2. Заполнение OBJECT->DATA.
3. OBJECT->NEXT=0
4. TEMP=START
5. Пока TEMP->NEXT#0 выполнить

5.1. TEMP=TEMP->NEXT

6. TEMP->NEXT=OBJECT

Список после размещения элемента:

Добавление элемента в конец непустого двунаправленного списка

Вначале START#0

1. Размещение элемента списка OBJECT.
2. Заполнение OBJECT->DATA.
3. END->NEXT=OBJECT
4. OBJECT->NEXT=0, OBJECT->PREV=END
5. END=OBJECT

Список после размещения элемента:

 

 Вывод списка в прямом направлении.

1. Если START=0, то
   • Вывод сообщения «список пуст»

иначе

1.2. TEMP=START

1.3. Пока TEMP#0 выполнить

1.3.1. Вывод TEMP->DATA

1.3.2. TEMP=TEMP->NEXT

Вывод двунаправленного списка в обратном направлении.

1. Если START=0, то

• Вывод сообщения «список пуст»

иначе

1.2. TEMP=END

1.3. Пока TEMP#0 выполнить

1.3.1. Вывод TEMP->DATA

1.3.2. TEMP=TEMP->PREV

 

Удалять элемент можно по номеру, по совпадению какого-то поля и т.д.

Алгоритм удаления элемента с заданным номером из двунаправленного списка.

1. Прием параметра NUM (номер удаляемого элемента)
2. TEMP=START
3. Если NUM=1, то START=TEMP->NEXT иначе

3.1. PREV=0 I=1

3.2.Пока TEMP->NEXT #0 выполнить

3.2.1. Если I=NUM, то PREV->NEXT=TEMP->NEXT иначе

3.2.2. PREV=TEMP  I=I+1

3.2.3. TEMP=TEMP->NEXT

3.3. Если I=NUM, то  PREV->NEXT=TEMP->NEXT

3.4. Возврат rez=0 (элемент успешно удален)

иначе

3.5. Возврат rez=1 (нет элемента с указанным номером)

Список после удаления элемента:

Бинарные деревья и деревья поиска

Бинарное дерево — это динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных, не более двух ссылок на различные бинарные деревья. На каждый узел имеется ровно одна ссылка. Начальный узел называется корнем дерева.

На рисунке приведен пример бинарного дерева (корень обычно изображается сверху). Узел, не имеющий поддеревьев, называется листом. Исходящие узлы называются предками, входящие — потом­ками. Высота дерева определяется количеством уровней, на которых располага­ются его узлы.

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

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

Например, функцию обхода всех узлов дерева в общем виде можно описать так:

function way_around ( дерево ){

way_around ( левое поддерево )

посещение корня

way_around ( правое поддерево )}

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

1, 6. 8, 10. 20, 21, 25,. 30

Если в функции обхода первое обращение идет к правому поддереву, результат обхода будет другим:

30. 25. 21, 20. 10, 8, 6, 1

Таким образом, бинарные деревья позволяют сортировать значения.

Структура элемента дерева:

d (Данные)

left (Левый потомок)

right (Правый потомок)

 

Для бинарных деревьев определены операции:

• включения узла в дерево;
• поиска по дереву;
• обход дерева;
• удаления узла.

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

Алгоритмы включения узла в дерево.

Каждое значение слева от корня (8) меньше восьми, каждое значение справа – больше либо равно корню. Это правило применимо к любому узлу дерева.

Добавление элемента в дерево на корректную позицию.

Есть всего два случая, которые надо учесть:

1. Дерево пустое.
2. Дерево не пустое.

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

 

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

Предположим, что вершины в дерево добавлялись в следующем порядке:

8,4,2,3,10,6,7

Рассмотрим подробнее первые шаги.

В первую очередь добавляется 8. Это значение становится корнем дерева. Затем мы добавляем 4. Поскольку 4 меньше 8, мы устанавливаем ее в качестве левого потомка, согласно правилу 2. После этого мы добавляем 2. Она меньше 8, поэтому идем налево. Так как слева уже есть значение, сравниваем его со вставляемым. 2 меньше 4, а у четверки нет левых потомков, поэтому 2 становится левым потомком 4.

Затем мы добавляем тройку. Она идет левее 8 и 4. Но так как 3 больше, чем 2, она становится правым потомком 2, согласно третьему правилу.

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

 Словесное описание алгоритма включения узла в дерево с поиском уже существующей вершины

1. Прием параметров: root – корень дерева, d1 – данные добавляемой вершины
2. pv =root found = 0
3. Пока pv#0 и found=0 выполнить

3.1. prev = pv

3.2. Если d1 =pv->d, то found = 1

иначе

3.3. Если d1<pv->d, то pv=pv->left  иначе pv=pv->right

4. Если found=0, то

4.1. Размещение в памяти pnew

4.2. pnew->d  = d1

4.3.pnew->left =0

4.4. pnew->right = 0

4.5. Если d1 < prev->d, то

4.5.1. prev->left = pnew;

иначе

4.5.2. prev->right = pnew

Алгоритм удаления узла из дерева поиска

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

В целом, алгоритм удаления элемента выглядит так:

• Найти узел, который надо удалить.
• Удалить его.

 

Для поиска узла необходимо осуществить проход по дереву, выполняя в каждом узле следующие шаги:

1. Если текущий узел null, вернуть null.
2. Если значение текущего узла равно искомому, вернуть текущий узел.
3. Если искомое значение меньше значения текущего узла, установить левого потомка текущим узлом и перейти к шагу 1.
4. В противном случае установить правого потомка текущим узлом и перейти к шагу 1.

 

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

Случай 1: У удаляемого узла нет правого потомка.

 

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

Случай 2: У удаляемого узла есть правый потомок, у которого, в свою очередь нет левого потомка.

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

Случай 3: У удаляемого узла есть правый потомок, у которого есть левый потомок.

 

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

Давайте посмотрим, почему это так. Мы знаем о поддереве, начинающемся с удаляемого узла следующее:

• Все значения справа от него больше или равны значению самого узла.
• Наименьшее значение правого поддерева — крайнее левое.

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

После удаления узла дерево будет выглядеть так:

 

Словесное описание алгоритма

Алгоритм должен учитывать случаи, когда удаляемый узел является корневым, содержит две, одну или ни одной ссылки на поддеревья. Для узлов, содержащих меньше двух ссылок, удаление тривиально. Чтобы сохранить упорядоченность дерева при удалении узла с двумя ссылками, его заменяют на узел с самым близким к нему ключом. Это может быть самый левый узел его правого поддерева или самый правый узел левого поддерева (например, чтобы удалить из дерева на рис. узел с ключом 25, его нужно заме­нить на 21 или 30, узел 10 заменяется на 20 или 8, и т. д.).

Алгоритм состоит из следующих шагов:

1. Прием параметров: root – корень дерева, key – удаляемый элемент
2. Если root->d=key, то

2.1. Если root->left=0 и root->right=0, то

2.1.1.temp=root->left

2.1.2. Удаление из памяти root

2.1.3.Возврат temp

иначе

2.2. Если root->left=0, то

2.2.1. temp= root->right

2.2.2. Удаление из памяти root

2.2.3. Возврат temp

иначе

2.3. Если root->right=0, то

2.3.1.temp= root->left

2.3.2. Удаление из памяти root

2.3.3. Возврат temp

иначе

2.4. Если root->left#0 и root->right#0, то

2.4.1.temp2= root->right

2.4.2.temp= root->right

2.4.3. Пока temp->left#0 выполнить

2.4.3.1.temp= temp->left

2.4.4. temp->left= root->left

2.4.5.Удаление из памяти root

2.4.6. Возврат temp2

3. Если key>root->d, то

3.1. root->right=удаление(root->right, key)

3.2. Возврат root

иначе

4. Если key<root->d, то

4.1. root->left=удаление(root->left, key)

4.2. Возврат root

Об алгоритмах обхода дерева

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

 Обход по возрастанию. Порядок обхода: 1, 2, 3, 4, 5, 6, 7, 8

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

Посещаем сначала левое поддерево, затем узел, затем — правое поддерево.

Для корня дерева рекурсивно вызывается следующая процедура:

Обойти левое поддеревоПосетить узелОбойти правое поддерево

Обход по убыванию. Порядок обхода: 8, 7, 6, 5, 4, 3, 2, 1

Для корня дерева рекурсивно вызывается следующая процедура:

Обойти правое поддеревоПосетить узелОбойти левое поддерево

 

О структурах С++

Структура в языке C++ представляет собой производный тип данных, который представляет какую-то определенную сущность.

Для определения структуры применяется ключевое слово struct, а сам формат определения выглядит следующим образом:

1 2 3 4

struct имя_структуры { компоненты_структуры };

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

После имени структуры в фигурных скобках помещаются Компоненты_структуры, которые представляют набор описаний объектов и функций, которые составляют структуру.

Например, определим простейшую структуру:

#include <iostream>

#include <string>

 

struct person

{

int age;

std::string name;

};

 

int main()

{

person tom;

tom.name = «Tom»;

tom.age = 34;

std::cout << «Name: » << tom.name << «\tAge: » << tom.age << std::endl;

return 0;

}

Здесь определена структура person, которая имеет два элемента: age (представляет тип int) и name (представляет тип string).

После определения структуры мы можем ее использовать. Для начала мы можем определить объект структуры — по сути обычную переменную, которая будет представлять выше созданный тип. Также после создания переменной структуры можно обращаться к ее элементам — получать их значения или, наоборот, присваивать им новые значения. Для обращения к элементам структуры используется операция «точка»:

1	имя_переменной_структуры.имя_элемента

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

1	person tom = { 34, «Tom» };

Инициализация структур аналогична инициализации массивов: в фигурных скобках передаются значения для элементов структуры по порядку. Так как в структуре person первым определено свойство, которое представляет тип int — число, то в фигурных скобках вначале идет число. И так далее для всех элементов структуры по порядку.

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

#include <iostream>

#include <string>

 

struct user

{

user(std::string n, int a)

{

name = n; age = a;

}

void move()

{

std::cout << name << » is moving» << std::endl;

}

void setAge(int a)

{

if (a > 0 && a < 100) age = a;

}

std::string getName()

{

return name;

}

int getAge()

{

return age;

}

 

std::string name;

int age;

 

};

 

int main()

{

user tom(«Tom», 22);

std::cout << «Name: » << tom.getName() << «\tAge: » << tom.getAge() << std::endl;

tom.setAge(31);

std::cout << «Name: » << tom.getName() << «\tAge: » << tom.getAge() << std::endl;

return 0;

}

В некоторых случаях необходимо отделить объявление методы от его реализации. Тогда поступают аналогично функциям, но в имя метода через двойное двоеточие добавляют упоминание о структуре (имя_структуры::имя_метода). Для предыдущего примера вынесем реализацию метода move из структуры, тогда будем иметь следующий код:

#include <iostream>

#include <string>

 

struct user

{

user(std::string n, int a)

{

name = n; age = a;

}

void move();

 

void setAge(int a)

{

if (a > 0 && a < 100) age = a;

}

std::string getName()

{

return name;

}

int getAge()

{

return age;

}

 

std::string name;

int age;

 

};

 

int main()

{

user tom(«Tom», 22);

std::cout << «Name: » << tom.getName() << «\tAge: » << tom.getAge() << std::endl;

tom.setAge(31);

std::cout << «Name: » << tom.getName() << «\tAge: » << tom.getAge() << std::endl;

return 0;

}

void user::move()

{

std::cout << name << » is moving» << std::endl;

}

 

 

Таблица спецификаций структур

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

 

Таблица – Спецификация структуры матрица Matrix

 

№	Имя поля	Назначение поля	Тип поля	Диапазон
1	Name	Имя матрицы	Строка	Символы ASCII кодировки
2	NumberOfRows	Количество строк	Целое	[2; 10]
3	NumberOfСols	Количество столбцов	Целое	[2; 10]
4	Data	Двумерный массив, содержащий данные	двумерный массив целых чисел	От -2 147 483 648 до 2 147 483 647

 

С учётом этого в таблице внешних спецификаций в поле «Тип» необходимо указывать пользовательский тип данных, если он подразумевается. В поле «Диапазон» указывается специфика типа при решении задачи. Например, если тип Matrix предполагает прямоугольные матрицы (что желательно), то дополнительно указываем ограничения на «квадратность».

 

№	Имя	Назначение	Тип	Вх/Вых.	Диапазон
1	С	Матрица С	Matrix	вход	Квадратная матрица с размером от 2 до 10

 

 

Индивидуальные задания и примечания

 

Содержание отчёта

1. Условие задачи
2. Таблица внешних спецификаций всей программы
3. Таблица спецификаций структур
4. Схема иерархии функций
5. Таблицы спецификаций функций
6. Схема иерархии модулей (файлы cpp и h)
7. Словесное описание основных алгоритмов
8. Таблица тестов
9. Программа на языке C++

 

Варианты

Таблица – Список вариантов для выполнения заданий со списками

N варианта	Задание для списка	Принцип добавления для списков (ключ-поле)	Принцип удаления для списков
1	A1	В конец	По табельному номеру
2	A2	В начало	По табельному номеру
3	A3	Перед концом	По фамилии
4	A4	По алфавиту	По фамилии
5	A1	По табельному номеру	По табельному номеру
6	B1	По шифру	По шифру
7	B2	По шифру	По шифру
8	B3	По наименованию	По наименованию
9	C1	По шифру	По шифру
10	C2	По весу	По весу
11	C3	В конец	По шифру
12	C4	В начало	По наименованию
13	C5	По шифру	По шифру
14	C6	По алфавиту	По шифру
15	C7	По шифру	По наименованию
16	C8	По шифру	По шифру

 

При добавлении новых элементов в список необходимо их связать в упорядоченный список по указанному ключу-полю из записи, если не указано добавить «в конец» или «в начало».

 

Таблица – Список вариантов для выполнения заданий с деревьями

№ варианта	Задание для дерева	Поле-ключ
1 (структура из варианта А)	Вывести на печать те элементы, в которых стаж работы содержится в заданных пределах и специальность совпадает с заданной	Табельный номер
2 (структура из варианта А)	Найти среднее значение оклада для лиц со стажем 12 лет.	Табельный номер
3 (структура из варианта А)	Удалить все элементы, у которых «специальность» совпадает с заданным значением специальности.	Табельный номер
4 (структура из варианта А)	Удалить все элементы с повторяющимися фамилиями (оставить одного – первого по порядку табельного номера).	Табельный номер
5 (структура из варианта C)	Подсчитать количество элементов, вес деталей которых больше среднего (среди всех элементов).	По шифру
6 (структура из варианта C)	Подсчитать количество элементов, цена деталей которых больше среднего (среди всех элементов).	По шифру
7 (структура из варианта C)	Удалить все элементы, вес которых меньше заданного	По шифру
8 (структура из варианта C)	Удалить все элементы, цена деталей которых меньше заданного	По шифру

 

ВАРИАНТ А

Структура элемента с данными: Фамилия И.,О., табельный номер, стаж работы, оклад, специальность.

А 1. Вывести на печать те элементы списка, в которых стаж работы содержится в заданных пределах и специальность совпадает с заданной.

А 2. Вывести на печать фамилии и оклады из всех записей списка SPI, найти среднее значение оклада для лиц со стажем 12 лет.

А 3. Удалить все элементы списка, у которых «специальность» совпадает с заданным значением специальности.

А 4. Удалить все повторяющиеся элементы списка (если в них совпадают фамилия и табельный номер, оставить первую по порядку).

ВАРИАНТ В

Структура элемента с данными: Шифр детали, наименование, количество.

В 1. Составить процедуру слияния 2-х упорядоченных однонаправленных списков: GOL1, GOL2 – указатели на входе; GOL – указатель общего списка.

В 2. В однонаправленный упорядоченный список включить новый список, не нарушая его упорядоченность.

В 3. Скопировать список S1 в новый список S2.

ВАРИАНТ С

Структура элемента с данными (DSP): Шифр детали, наименование, расценка, вес.

С 1. Удалить элемент, предшествующий 2-му с конца списка элементу.

С 2. Удалить элемент с заданным номером К от начала списка.

С 3. Удалить элемент с заданным номером от конца списка.

С 4. Удалить повторяющиеся элементы списка DSP, если в них совпадает шифр и наименование.

С 5. Проверить упорядочены ли элементы списка по возрастанию шифра детали от начала к концу.

С 6. Проверить упорядочены ли элементы списка DSP от конца к началу по возрастанию шифра детали.

С 7. Подсчитать количество элементов списка, шифры деталей, в которых встречаются в списке только 1 раз, и вывести их на печать.

С 8. Найти сумму расценок по всем деталям, наибольшую и наименьшую расценки и соответствующие наименования деталей.

 

Примечания

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

• вставка элемента в начало списка;
• вставка элемента в середину списка;
• вставка в конец списка (т.е. перед последним элементом);
• попытка вставить элемент перед элементом, номер К которого больше количества элементов в списке (т.е. проверить и сообщить об ошибке).

 

Примечание 2. Возможно разделить структуру с данными и структуры узла списка и узла дерева.

struct Data

{

   int id;

   string message;

};

struct List

{

   Data d;

   List *next;

};

struct Btree

{

   Data d;

   Btree *left;

   Btree *right;

};

 

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

 

Примечание 4. В бинарном дереве из полей рассматриваемой записи для реализации операций необходимо выбрать уникальный идентификатор узла (ключ). Можно выбирать в т.ч. и строковый идентификатор (можно сравнивать с использованием функции strcmp или операций сравнения для типа string).

 

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