Задача 9.1. Стек

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

Что-то подобное я уже здесь читал... - подумаете вы и будете правы. Вы это читали в задаче 3.3. А может быть, вы пойдете дальше и подумаете: Да сколько ж можно! . Или еще что-нибудь подобное. И вот тут мы с вами не согласимся, потому что когда мы решали эту задачу, нам пришлось выделить для хранения границ неотсортированных фрагментов массива два массива, причем большая часть этой памяти пропадала совершенно зря. Но это еще полбеды, а настоящая беда может случиться, если массив для сортировки будет настолько большой длины, что еще два выделить просто не удастся. И вот тут нам на помощь приходит динамическое выделение памяти - когда выделяется нужное количество байт в нужное время, и ничего лишнего.

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

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

struct Node { . Элемент стека

int left, right:

Node* p:

Node* top = 0*: Вершина стека

Удобно оформить занесение и выборку элемента в виде отдельных функций. Функция помещения в стек обычно называется push, а выборки - pop. Все необходимое передается функциям через параметры. В отличие от Учебника (с. 120) мы не будем использовать отдельную функцию для занесения первого элемента в стек, так как если указателю top присвоить О перед первым обращением к функции push О, то функция push вполне прилично справится с созданием первого элемента стека:

Занесение в стек

Node* push(Node* top. const int 1, const int r) { Node* pv = new Node: 1

pv->left = 1: 2

pv->right = r; pv->p = top; return pv;

3 4 5

6 7 8 9 10

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

Выборка из стека Node* pop(Node* top. int& 1. int& г) {

Node* pv = top->p:

1 = top->1eft;

r = top->right:

delete top;

return pv;

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

Прежде всего мы описываем вспомогательную переменную-указатель и заносим в нее адрес нового элемента стека, который создается с помощью операции new (оператор 1). Выделяется столько памяти, сколько необходимо для хранения структуры типа Node. В операторах 2 и 3 информационные поля этой структуры 1 eft и ri ght заполняются значениями переданных в функцию границ фрагмента массива. Доступ к этим полям выполняется через указатель pv и операцию выбора ->. Новый элемент становится вершиной стека. Поле его указателя должно ссылаться на элемент, помещенный в стек ранее. Эта ссылка создается в операторе 4. Если <*затал-киваемый в стек элемент является первым, то в качестве первого аргумента функции push О надо задать 0.

Функция push возвращает указатель на вершину стека. Им всегда является указатель на только что занесенный элемент (оператор 5).

Выборка из стека (функция pop) выполняется аналогично. Сначала из вершины стека выбирается указатель на его следующий элемент (оператор 6), который станет новой вершиной стека. Этот указатель является возвращаемым значением функции (оператор 10). Информационная часть элемента заносится в переменные 1 и г, которые передаются в вызывающую функцию по ссылке (операторы 7 и 8). После того как вся информация из элемента выбрана, его можно удалить (оператор 9).

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

Теперь можно заменить в задаче 3.3 решение с массивами на классический стек: #include <fstream.h> struct Node {.

int left, right;

Node* p;

Node* push(Node* top. const int 1. const int r): Node* pop(Node* top. int &1. int &r):

-............ .......-

int mainO { int i. n;

float middle, temp:

ifstream finCsortl.txt . ios::in ios::nocreate):

if (Ifin) { cout Нет файла sortl.txt endl: return 0: }

fin n:

float* arr = new floatCn]:

for (i - 0: i < n: i++) fin arr[i]:

Сортировка

int j. left, right:

Node* top - 0:

top = push(top. 0. n - 1):

while (top) { top = pop(top. left, right): while (left < right) { Разделение { arrCleft] .. arr[right] } i = left: j = right: middle - arr[(left + right) / 2]: while (i < j) { while (arr[i] < middle) while (middle < arr[j]) j--:

if (i <= j) { , temp = arr{i]: arr[i] - arr[j]: arrCj] = temp:

i++: j--:

if (i < right) { Запись в стек запроса из правой части top = push(top. i. right):

right = j:

Теперь left и right ограничивают левую часть

Вывод результата

for (i = 0: i < n: i++) cout arr[i] : cout endl: return 0:

............-----........--- Занесение в стек

Node* push(Node* top. const int 1. const int r) {

Node* pv = new Node: pv->left - 1; pv->right = r: pv->p = top: return pv:

....................................... Выборка из стека

Node* pop(Node* top. int &1. int &r) {

Node* pv = top->p:

1 - top->left:

r = top->right:

delete top;

return pv:

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

Задача 9.2. Линейный список

Написать программу работы с базой отдела кадров предприятия. База хранится в текстовом файле, его размер может быть произвольным. Каждая строка файла содержит запись об одном сотруднике. Формат записи: фамилия и инициалы (30 ТЮЗ., фамилия должна начинаться с первой позиции), год рождения (5 поз.), оклад (10 поз.). Программа должна обеспечивать поиск в базе по заданным критериям, корректировку и дополнение базы.

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

const int l name = 31:

struct Man { Элемент списка

char name[l name]: int birth day: float pay: Man *next:

Man *beg: Указатель на начало списка

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

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

1) добавление сотрудника;

2) удаление сотрудника;

3) поиск сотрудника;

4) корректировка сведений о сотруднике;

5) вывод базы на экран;

6) вывод базы в файл;

7) выход.

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

Man* addCMan* beg. const Man& man): Удаление сотрудника. Чтобы удалить сотрудника из базы, надо знать, из какой базы и какого сотрудника удалять. Удаление сотрудника логично выполнять по его фамилии и инициалам, следовательно, надо их предварительно запросить у пользователя. Чтобы удалить элемент из списка, надо предварительно найти этот элемент, то есть путем просмотра списка получить указатель на него. Поиск элемента списка по фамилии потребуется в нашей программе и сам по себе, и для корректировки списка, поэтому оформим его в виде отдельной функции. Запрос фамилии требуется и при удалении сотрудника, и при корректировке сведений, поэтому его также будет логично оформить в виде совсем небольшой вспомогательной функции. Назовем ее get name (впрочем, без этой функции вполне можно обойтись, это дело вкуса):

void get name(char *name): Итак, запрос фамилии будет выполняться внутри функции удаления, поэтому извне в нее должен передаваться только указатель на начало списка:

Man* remove(Man *beg): Эта функция, так же, как и функция добавления, возвращает указатель на начало списка на тот случай, если удаление выполняется из его начала (при этом указатель изменяется).

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

□ сведения об отдельном сотруднике по его фамилии и инициалам;

□ сведения о сотрудниках старше заданного года рождения;

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

void find man(Man *beg):

Поиск в списке по конкретному критерию оформим в виде перегруженных функций, которые будут вызываться из f i ndman:

Man* find(Man *beg. char *name. Man **prev): void find(Man *beg. int birth day): void find(Man *beg. float pay):

Вторая и третья функции выполняют поиск и вывод списка сотрудников по заданному году рождения и окладу. Первая функция выполняет поиск по фамилии, выводит сведения о сотруднике и возвращает указатель на найденный элемент или ноль, если элемент не найден. Кроме того, мы предусмотрительно добавили в список параметров указатель на элемент, предшествующий найденному. Он передается по адресу (как указатель на указатель*), поскольку должен формироваться внутри функции. Этот указатель потребуется в подпрограмме удаления, поскольку при этом надо связать между собой предыдущий и следующий по отношению к удаляемому элементы.

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

int edit(Man *beg):

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

void print dbase(Man *beg): на экран

int write dbase(char *filename. Man *beg): в файл

Начальное формирование списка из файла выполняется в функции read dbase: Man* read dbase(char *filename):

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

Man read man();

int menuO:

Альтернативный способ передачи указателя по адресу - с использованием ссылки на указатель будет показан в задаче 9.4.