Пример реализации метода прямой адресации с линейным опробыванием. Исходными данными являются 7 записей (для простоты информационная часть состоит из целых чисел) объявленного структурного типа:
struct zap {
int key; // Ключ
int info; // Информация
} data;
{59,1}, {70,3}, {96,5}, {81,7}, {13,8}, {41,2}, {79,9}; размер хеш-таблицы m = 10. Выберем хеш-функцию i = h (data) = data. key %10; т.е. остаток от деления на 10 – i Î[0,9].
На основании исходных данных последовательно заполняем хеш-таблицу.
Хеширование первых пяти ключей дает различные индексы (хеш-адреса):
i = 59 % 10 = 9; i = 70 % 10 = 0;
i = 96 % 10 = 6; i = 81 % 10 = 1;
i = 13 % 10 = 3.
Первая коллизия возникает между ключами 81 и 41 – место с индексом 1 занято. Поэтому просматриваем хеш-таблицу с целью поиска ближайшего свободного места, в данном случае – это i = 2.
Следующий ключ 79 также порождает коллизию: позиция 9 уже занята. Эффективность алгоритма резко падает, т.к. для поиска свободного места понадобилось 6 проб (сравнений), свободным оказался индекс i = 4. Общее число проб – 1–9 проб на элемент.
Реализация метода цепочек для предыдущего примера. Объявляем структурный тип для элемента однонаправленного списка:
struct zap {
int key; // Ключ
int info; // Информация
zap *Next; // Указатель на следующий элемент в списке
} data;
На основании исходных данных последовательно заполняем хеш-таблицу, добавляя новый элемент в конец списка, если место уже занято.
Хеширование первых пяти ключей, как и в предыдущем случае, дает различные индексы (хеш-адреса): 9, 0, 6, 1, и 3.
При возникновении коллизии новый элемент добавляется в конец списка. Поэтому элемент с ключом 41 помещается после элемента с ключом 81, а элемент с ключом 79 – после элемента с ключом 59.
ЗАДАНИЕ 8. Обработка списков
Вариант 1. Однонаправленные списки
Написать программу по созданию, просмотру, добавлению и решению поставленной задачи для однонаправленного линейного списка (стек и/или очередь).
1. Создать список из случайных целых чисел, лежащих в диапазоне от
–50 до +50 и преобразовать его в два списка. Первый должен содержать только положительные числа, а второй – только отрицательные. Порядок следования чисел должен быть сохранен.
2. Создать список из случайных целых чисел и удалить из него записи с четными числами.
3. Создать список из случайных положительных и отрицательных целых чисел (от –10 до 10) и удалить из него отрицательные элементы.
4. Создать список из случайных целых чисел и поменять местами крайние элементы.
5. Создать список из случайных целых чисел и удалить элементы, заканчивающиеся на цифру 5.
6. Создать список из случайных целых чисел и поменять местами элементы, содержащие максимальное и минимальное значения.
7. Создать список из случайных целых чисел. Перенести в другой список все элементы, находящиеся между вершиной и элементом с максимальным значением.
8. Создать список из случайных целых чисел. Перенести в другой список все элементы, находящиеся между вершиной и элементом с минимальным значением.
9. Создать список из случайных чисел, определить количество элементов, находящихся между минимальным и максимальным элементами, и удалить их.
10. Создать список из случайных чисел и определить количество элементов, имеющих значения, меньше среднего значения от всех элементов, и удалить эти элементы.
11. Создать список из случайных чисел, вычислить среднее арифметическое и заменить им первый элемент.
12. Создать список из случайных целых чисел, разделить его на два: в первый поместить все четные, а во второй – нечетные числа.
13. Создать список из случайных целых чисел в диапазоне от 1 до 10, определить наиболее часто встречающееся число и удалить его.
14. Создать список из случайных целых чисел и удалить из него каждый второй элемент.
15. Создать список из случайных целых чисел и удалить из него каждый нечетный элемент.
Вариант 2. Двунаправленные списки
Написать программу по созданию, просмотру, добавлению и решению поставленной задачи для двунаправленного линейного списка.
1. Создать список из случайных целых чисел. Найти минимальный элемент и сделать его первым.
2. Создать два списка из случайных целых чисел. В первом найти максимальный элемент и за ним вставить элементы второго.
3. Создать список из случайных целых чисел. Удалить из списка все элементы, находящиеся между максимальным и минимальным элементами.
4. Упорядочить элементы списка случайных целых чисел в порядке возрастания.
5. Создать список из случайных целых чисел. Удалить из списка все элементы, находящиеся до максимального элемента.
6. Создать список из случайных целых чисел. Удалить из списка все элементы, находящиеся после минимального элемента.
7. Создать список из случайных целых чисел. Из элементов, расположенных между максимальным и минимальным элементами, создать второй список, а из остальных – третий.
8. Создать список из случайных положительных и отрицательных целых чисел. Образовать из него два списка, первый должен содержать отрицательные числа, а второй – положительные.
9. Создать список из случайных целых чисел. Удалить из списка все элементы, находящиеся после максимального элемента.
10. Создать два списка из случайных целых чисел. Вместо элементов первого списка, заключенных между максимальным и минимальным элементами, вставить второй список.
11. Создать список из случайных целых чисел. Удалить из списка элементы с повторяющимися более одного раза значениями.
12. Создать список из случайных целых чисел и удалить все элементы, кратные 5.
13. Создать список из случайных целых чисел. Удалить из списка все элементы, большие среднего арифметического.
14. Создать список из случайных чисел. Преобразовать его в кольцо. Предусмотреть возможность движения по кольцу в обе стороны с отображением места положения текущего элемента.
15. Создать список из случайных целых чисел. Удалить из списка все элементы, находящиеся между максимальным и минимальным элементами.
ЗАДАНИЕ 9. Деревья и польская запись
Вариант 1. Создание и обработка структур типа «дерево»
Разработать проект для обработки дерева поиска, каждый элемент которого содержит целочисленный ключ и строку текста, содержащую, например, ФИО и номер паспорта (ввод исходной информации рекомендуется записать в файл). В программе должны быть реализованы следующие возможности:
– создание дерева;
– добавление новой записи;
– поиск информации по заданному ключу;
– удаление информации с заданным ключом;
– вывод информации;
– решение индивидуального задания;
– освобождение памяти при выходе из программы.
1. Поменять местами информацию, содержащую максимальный и минимальный ключи.
2. Подсчитать число листьев в дереве.
3. Удалить из дерева ветвь с вершиной, имеющей заданный ключ.
4. Определить глубину дерева.
5. Определить число узлов на каждом уровне дерева.
6. Удалить из левой ветви дерева узел с максимальным значением ключа и все связанные с ним узлы.
7. Определить количество узлов с четными ключами.
8. Определить число листьев на каждом уровне дерева.
9. Определить число узлов в дереве, имеющих только одного потомка.
10. Определить количество узлов правой ветви дерева.
11. Определить количество записей в дереве, начинающихся с введенной с клавиатуры буквы.
12. Найти среднее значение всех ключей дерева и найти строку, имеющую ближайший к этому значению ключ.
13. Определить количество узлов левой ветви дерева.
14. Определить число узлов в дереве, имеющих двух потомков.
15. Найти запись с ключом, ближайшим к среднему значению между максимальным и минимальным значениями ключей.
Вариант 2. Создание и использование польской записи
Написать программу формирования обратной польской записи и расчета полученного выражения. Предусмотреть возможности того, что идентификаторы могут состоять более чем из одного символа и могут быть использованы операции % и возведение в степень. Результат работы программы проверить на конкретном примере (табл. 15.1).
Например, если ввести выражение (a + b)*(c – d)/ e и значения переменных а = 3, b = 5, c = 6, d = 9, е = 7, должны получиться следующие результаты:
Постфиксная форма ab + cd – * e /
Результат расчета – 3.42857
Таблица 15.1
| № | Выражение | a | b | c | d | e | Результат |
| 1 | a /(b – c)*(d + e) | 8.6 | 2.4 | 5.1 | 0.3 | 7.9 | – 26.12 |
| 2 | (a + b)*(c – d)/ e | 7.4 | 3.6 | 2.8 | 9.5 | 0.9 | – 81.89 |
| 3 | a – (b + c * d)/ e | 3.1 | 5.4 | 0.2 | 9.6 | 7.8 | 2.16 |
| 4 | a / b – ((c + d)* e) | 1.2 | 0.7 | 9.3 | 6.5 | 8.4 | – 131.006 |
| 5 | a *(b – c + d)/ e | 9.7 | 8.2 | 3.6 | 4.1 | 0.5 | 168.78 |
| 6 | (a + b)*(c – d)/ e | 0.8 | 4.1 | 7.9 | 6.2 | 3.5 | 2.38 |
| 7 | a *(b – c)/(d + e) | 1.6 | 4.9 | 5.7 | 0.8 | 2.3 | – 0.413 |
| 8 | a /(b *(c + d))– e | 8.5 | 0.3 | 2.4 | 7.9 | 1.6 | 1.151 |
| 9 | (a +(b / c – d))* e | 5.6 | 7.4 | 8.9 | 3.1 | 0.2 | 0.666 |
| 10 | a *(b + c)/(d – e) | 0.4 | 2.3 | 6.7 | 5.8 | 9.1 | – 1.091 |
| 11 | a – (b / c *(d + e)) | 5.6 | 3.2 | 0.9 | 1.7 | 4.8 | – 17.51 |
| 12 | (a – b)/(c + d)* e | 0.3 | 6.7 | 8.4 | 9.5 | 1.2 | – 0.429 |
| 13 | a /(b + c – d * e) | 7.6 | 4.8 | 3.5 | 9.1 | 0.2 | 1.173 |
| 14 | a *(b – c)/(d + e) | 0.5 | 6.1 | 8.9 | 2.4 | 7.3 | – 0.144 |
| 15 | (a + b * c)/(d – e) | 9.1 | 0.6 | 2.4 | 3.7 | 8.5 | – 2.196 |
ГЛАВА 16. Переход к ООП
При переходе от языка Си к языку С++ в стандарт ANSI были введены дополнительные механизмы, которые позволили в конечном итоге создать среду для разработки программ в объектно-ориентированном стиле.
Рассмотрим некоторые из них.
Потоковый ввод-вывод
Поток – это абстрактное понятие, которое относится к любому переносу данных от источника к приемнику. Потоки С++ обеспечивают надежную работу как со стандартными (stdin, stdout), так и с определенными пользователями типами данных. Поток определяется как последовательность байт, не зависящая от конкретного устройства.
Для ввода-вывода в языке С++ используются два объекта класса iostream: cin (класс istream), cout (класс ostream) и две переопределенные операции побитового сдвига. Для их работы необходимо подключить заголовочный файл iostream.h.
Формат записи операций помещения в поток << (вывод на экран) и извлечения из потока >> (ввод с клавиатуры) следующий:
cout << ID переменной;
cin >> ID переменной;
Стандартный поток вывода cout по умолчанию связан со стандартным устройством вывода stdout (дисплей монитора), а ввода cin – со стандартным устройством ввода stdin, т.е. клавиатурой. Приведем пример:
#include<iostream.h>
void main (void)
{
int i, j, k;
cout << “ Hello! ” << endl; // «end line» – переход на новую строку
cout << “ Input i, j ”;
cin >> i >> j;
k = i + j;
cout << “ Sum i, j = “ << k << endl;
}
Управление выводом
В стандарте языка Си ANSI ввод-вывод данных осуществляется при помощи стандартных библиотечных функций. Управление выводом осуществляется при помощи использования форматов и управляющих символов.
Для форматирования и управления выводом данных в потоке введен механизм манипуляторов – специальных функций для модификации работы потока, предназначенных для форматирования данных, как при выводе, так и в оперативной памяти.
Использование манипуляторов
Манипуляторы – специальные функции, возвращающие модифицированные данные потока. В большинстве случаев их использование позволяет форматировать данные, как при выводе, так и в оперативной памяти.
Для их использования необходимо вместо файла iostream. h подключить заголовочный файл iomanip. h (манипуляторы для вывода потоками).
Рассмотрим работу некоторых манипуляторов на конкретном примере.
#include<iomanip.h>
main()
{
int a = 157;
double b = 1.55555;
cout << setw(10) << a << endl;
/* Манипулятор setw (n) – устанавливает ширину поля, т.е. n позиций, для вывода объекта. На экране объект а будет выводиться с 8-й позиции, первые 7 позиций – пустые: 157 (заполнение пробелами неиспользуемой части). Действует только для следующего за ним объекта. */
cout << setw(10) << setfill(‘z’) << a << endl;
/* Манипулятор setwfill (kod) – устанавливает заполнитель пробелов, заданный символом или его кодом (можно было указать 122 – код символа ' z '). На экране: zzzzzzz157. Действует до изменения или отмены setwfill (0).*/
cout << oct << a << endl;
/* Манипулятор oct – выполняет преобразование объекта в 8-ричную форму представления. На экране: 235 */
cout << hex << a << endl;
// hex – преобразует объект в 16-ричную форму. На экране: 9d
cout << dec << a << endl;
// dec – преобразует обратно в 10-тичную. На экране: 157
cout << b << endl; // На экране: 1.55555
cout << setprecision(3) << b << endl;
/* setprecision (n) – устанавливает n значащих цифр после запятой с учетом точки или без нее, в зависимости от системы программирования. На экране:
1.56 или 1.556 */
return 0;
}
Флажки
Помимо манипуляторов для управления выводом данных используются специальные флажки, принадлежащие классу ios, которые также позволяют формировать потоки вывода.
Установить флажок позволяет функция setiosflags (ios:: flag);
Снять флажок позволяет функция resetiosflags (ios:: flag);
Причем можно установить сразу несколько флажков, используя для этого побитовую операцию «|» (поразрядное ИЛИ) для их объединения в одну группу.
Следующий пример показывает приемы работы с некоторыми флажками механизма вывода потоками.
#include<iostream.h>
#include<iomanip.h>
#include<conio.h>
void main(void) {
int a = 157;
cout<<setiosflags(ios:: showbase)<<a<<“ “<<oct<<a<< “ “
<<hex<<a<< endl;
/* showbase – показать, в какой системе счисления выводится число. На экране: 157 0235 0х9d */
double a1 = 12.99, a2 = 15;
cout << setiosflags(ios:: showpoint | ios:: fixed)
/* showpoint – печатать десятичную точку, fixed – выводить в форме с фиксированной десятичной точкой */
<< setprecision(2) << setfill(‘*’) << setiosflags(ios:: right)
// right – выравнивать вывод по правому краю (по левому – left)
<< “ a1 “ << setw(10) << a1
<< “ a2 “ << setw(10) << a2 << endl;
// На экране: a1 *****12.99 a2 *****15.00
double pi = 3.14159;
cout << “ Pi “ << setw(15) << setfill(‘_’)
// Символ заполнения ‘_’ – знак подчеркивания
<< setiosflags(ios:: showpos | ios:: scientific)
<< setprecision(5) << pi << endl;
/* showpos – явно показать знак «+», scientific – вывод в форме с плавающей десятичной точкой. На экране: Pi _ _ _ +3.14159e+00 */
}
В заключение отметим, что можно создавать свои собственные манипуляторы, которые будут выполнять запрограммированные действия.
16.3. Проблема ввода-вывода кириллицы в среде Visual C++
Работа в среде Visual C++ 6.0 (в режиме консольных приложений) сопряжена с определенными неудобствами. Например, попытка вывести фразу на русском языке, как стандартными функциями вывода, так и с помощью ввода-вывода потоками, терпит неудачу. Создадим в среде Visual C++ 6.0 консольное приложение и наберем следующий текст:
#include <iostream.h>
int main()
{
cout << "Welcome to C++!" << endl;
cout << "Добро пожаловать в C++!" << endl;
return 0;
}
В результате на экране получим нечто следующее:
Welcome to C++!
─юсЕю яюцрыютрЄ № т C++!
Press any key to continue
То есть вместо фразы на русском языке получается бессмысленный набор символов. Это вызвано различными стандартами кодировки символов кириллицы в операционных системах MS DOS и Windows.
Весь ввод-вывод в консольном окне идет в кодировке стандарта ASCII. Данный стандарт является международным только в первой половине кодов, т.е. для кодов от 0 до 127, а вторая половина кодов от 128 до 255 предназначена для национальных шрифтов. Так, например, в бывшем СССР помимо альтернативной кодировки ГОСТа (Alt), использовались – основная кодировка ГОСТа (Mai), болгарская кодировка (MIC), кодировка КОИ-8 (KOI), у которых символы кириллицы имеют разные коды. Сейчас в России – альтернативная кодировка ASCII.
Текст же в исходных файлах, набираемый в текстовом редакторе Visual C++, имеет кодировку в стандарте ANSI. Данный стандарт в первой половине совпадает с альтернативной кодировкой ASCII, а во второй – отличается, так как разработчики Visual решили, что консольное приложение должно имитировать работу в среде MS DOS и оставили альтернативную кодировку ASCII.
Для нормального вывода строки, содержащей буквы русского алфавита, надо использовать функцию CharToOem, предназначенную для преобразования символов с кодировкой ANSI в кодировку ASCII. Аналогично, если в программе есть консольный ввод текста и этот текст в дальнейшем надо сохранять в документах (файлах) с кодировкой ANSI, то перед сохранением нужно воспользоваться функцией обратного преобразования – OemToChar. Эти функции декларированы в заголовочном файле windows. h.
С учетом сказанного выше можно предложить следующую программу корректного вывода информации на русском языке:
#include <iostream.h>
#include <windows.h>
char* Rus(const char* text);
char bufRus[255];
int main()
{
char s[] = "Минск!", ss[100];
cout << Rus("Город ") << Rus(s) <<endl;
cout << Rus("Введи строку:");
cin >> ss;
cout << Rus(" Строка: ") << ss << endl;
return 0;
}
char* Rus (const char* text)
{
CharToOem(text, bufRus);
return bufRus;
}
Результат программы может быть следующим:
Город Минск!
Введи строку: Москва!
Строка: Москва!
Таким образом, для решения проблемы с русским языком в консольном выводе Visual C++ 6.0 создана небольшая функция Rus, которая обращается к функции CharToOem, передает ей для преобразования полученный через свой параметр текст на русском языке и возвращает указатель на преобразованную строку. В качестве временного хранилища используется глобальный символьный массив bufRus. Использовать функцию просто: везде вместо строковых объектов (строковых констант и переменных) в программах нужно писать Rus (строковый объект).
Непосредственное использование функции CharToOem, например, в стандартных функциях вывода данных недопустимо, так как возвращает результат типа BOOL, а результат преобразования размещает по адресу своего второго аргумента. Поэтому и была создана эта небольшая пользовательская функция, которая имеет единственное ограничение: функцию Rus нельзя использовать в цепочке операций << более одного раза, так как для различных компиляторов и режимов оптимизации может быть получен неверный результат.
Операции new и delete
В языке С++ для захвата и освобождения памяти используется более простой механизм – операции new и delete. Рассмотрим эти операции на простых примерах:
1) type * p = new type (значение); – захват участка памяти размером sizeof (type), путем установки на него указателя, и запись в эту область указанного значения;
...
delete p; – освобождение захваченной памяти.
2) type * p = new type [ n ]; – захват памяти на n последовательно размещенных объектов, возвращает указатель на начало участка ОП размером n * sizeof (type); используется для создания массива;
...
delete [] p; – освобождение всей захваченной памяти.
Следует заметить, что операция delete не уничтожает значения, находящиеся по указанным адресам, а дает компилятору разрешение использовать ранее занятую память в дальнейшем.
Квадратные скобки в операции delete [ ] при освобождении памяти, занятой массивом, обязательны. Их отсутствие может привести к непредсказуемым результатам.
Пример создания одномерного динамического массива
Для примера приведем участок кода программы для одномерного динамического массива с использованием операций new и delete.
Напомним, что результатом операции new является адрес начала области памяти для размещения данных, указанного количества и типа. При нехватке памяти результат равен NULL.
¼
double *x;
int i, n;
puts(" Введите размер массива: ");
scanf(“%d”, &n);
x = new double [n];
if (x = = NULL) {
puts(" Ошибка! ");
return;
}
for (i=0; i<n; i++) // Ввод элементов массива
scanf(“%lf”, &x[i]);
¼ // Обработка массива
delete [ ]x; // Освобождение памяти
¼
Пример создания двухмерного динамического массива
Напомним, при создании двухмерного динамического массива сначала выделяется память на указатели, расположенные последовательно друг за другом, а затем каждому из них выделяется соответствующий участок памяти под элементы.
...
int **m, n1, n2, i, j;
puts(" Введите размеры массива (строк, столбцов): ");
scanf(“%d%d”, &n1, &n2);
m = new int*[n1]; // Захват памяти для указателей – А (n1=3)
for (i=0; i<n1; i++) // Захват памяти для элементов
*(m+i) = new int[n2];
for (i=0; i<n1; i++)
for (j=0; j<n2; j++)
m[i] [j] = i+j; // *(*(m+i)+j) = i+j;
...
for (i=0; i<n1; i++) // Освобождение памяти
delete []m[i];
delete []m;
...
