!!! МЕТОДИЧКА_Срр_Часть1. Учебнометодическое пособие предназначено для студентов, изучающих дисциплину Программирование
 Скачать 2.01 Mb.
|
Метод «пузырька» (или метод простого обмена) заключается в сравнении пары соседних элементов и замене их местами, если первый оказался больше второго. После этого сравнивается следующая пара и т.д. При выполнении этой последовательности действий элементы с большими значениями будут продвигаться (“всплывать” как пузырьки) в конец массива. Тот же массив этим методом сортируется следующей программой на языке С++: #include #include { const int N = 9; int mas[N] = {420, 79, 429, 53, 908, 140, 897, 594, 682}; int bound, t, j, temp; bound = N-1; do { t = 0; for(j = 0; j <= bound-1; j++) if (mas[j] > mas[j + 1]) { temp = mas[j]; mas[j] = mas[j + 1]; mas[j + 1] = temp; t = j; } bound = t; } while (t); //выводим упорядоченный массив на экран cout<<"Otsortirov. massiv"< } В начале сортировки ничего не известно о порядке размещения элементов. В переменной bound хранится индекс самого правого элемента массива, о котором не известно, занял ли он свою окончательную позицию или нет. В переменной t хранится индекс самого последнего элемента массива, который участвовал в обмене. Если после просмотра массива переменная t равна 0, то все элементы массива упорядочены и сортировка завершена. В противном случае, продолжаем просмотр массива, исключая элементы с индексом от t до N-1, которые уже заняли свои окончательные позиции. Пример выполнения сортировки методом пузырька для массива из 9 элементов {420, 79, 429, 53, 908, 140, 897, 594, 682} приведен на рис. 6.3. Рис. 6.3. Пример сортировка методом «пузырька» Как видно, после каждого прохода массива все элементы, расположенные правее самого последнего, который участвовал в обмене, и сам этот элемент занимают свои окончательные позиции (на рис. 6.3 эта часть массива отделена вертикальной чертой). При следующих просмотрах их проверять уже не нужно. Обратите внимание на то, что после третьего прохода еще четыре правых элемента {420, 429, 594, 682} сразу заняли свои позиции, а при последнем проходе перемещений элементов вообще не было. Реализуем описанный алгоритм на языке С++. В результате будет получен следующий результат (рисунок 6.4.) Рис. 6.4. Окно выполнения задачи Сортировка методом простых вставок Пусть существующие m из N элементов массива уже упорядочены, т.е. mas[0] ≤ mas[1] ≤ … ≤ mas[m-1], а элементы mas[m], mas[m+1], …, mas[N-1] не известны. Метод сортировки вставкой применяется в тех случаях, когда массив надо заполнить так, чтобы после вставки каждого нового элемента сохранилась его упорядоченность. Для этого осуществляется поиск подходящего для вставки места в уже заполненной части массива. Место для нового элемента освобождается путем сдвига больших элементов к концу массива. На языке С++ программа выглядит следующим образом: #include #include { const int N = 9; int mas[N] = {79, 420, 429}; int i, j, m, el; m = 3; //заполнение пустой части массива for (i = m; i < N; i++) { //ввод нового элемента cout<<"Vvedite novyj element:"; cin >> el; //поиск и высвобождение места под новый элемент j = i - 1; while (j >= 0 && el < mas[j]) { //перемещение элемента mas[j] в позицию mas[j+1] mas[j+1] = mas[j]; j--; } //вставка нового элемента в массив mas[j+1] = el; } //выводим упорядоченный массив на экран cout<<"Otsortirov. massiv"< _getch(); return 0; } Поиск ведется с конца заполненной части к началу массива следующим образом. Новый элемент el сравнивается по очереди с элементами mas[m-1], mas[m-2], mas[m-3], … До тех пор, пока el меньше текущего элемента и не достигнуто начало массива, происходит высвобождение под него места путем перемещения большего элемента mas[j] на одну позицию к концу массива. Новый элемент помещается в освободившуюся позицию. Пример заполнения массива с помощью алгоритма сортировки вставкой приведен на рис. 6.3. Здесь к уже существующим элементам {79, 420, 429} (m=3) добавляются новые: 53, 908, 140, 897, 594, 682. 79 420 429 : 53 ^ 53 79 420 429 :908 ^ 53 79 420 429 908 :140 ^ 53 79 140 420 429 908 :897 ^ 53 79 140 420 429 897 908 :594 ^ 53 79 140 420 429 594 897 908 :682 ^ 53 79 140 420 429 594 682 897 908 Рис. 6.5. Пример сортировки методом простых вставок Выполнив данную программу с помощью среды Microsoft Visual Studio 2010, получим окно, представленное на рисунке 6.6. Рис. 6.6. Окно выполнения задачи Для заполнения пустого массива нужно прежде ввести первый элемент (m=1), а после выполнить действия алгоритма сортировки вставкой. Видоизмененная программа имеет вид: const int N = 9; int mas[N]; int i, j, el; //заполнение пустой части массива cout<<"Vvedite pervyj element:"; cin >> mas[0]; for (i = 1; i < N; i++) { cout<<"Vvedite sleduwij element:"; cin >> el; j = i - 1; while (j >= 0 && el < mas[j]) { mas[j+1] = mas[j]; j--; } mas[j+1] = el; } Результирующее окно при выполнении этой программы представлено на рисунке 6.7. Рис. 6.7. Окно выполнения задачи Задачи для индивидуального решения: 1. Написать программу для заполнения данными одномерного массива в соответствии с номером своего варианта. 2. Отсортировать полученный массив по возрастанию методами выбора, «пузырька» и простых вставок. 3. Сделать выводы о полученных результатах работы программ. Варианты заданий Вариант Одномерный массив 1. Записать в массив значения функции f (x) = kx + b, при x = 1,2,...,100. 2. Записать в массив значения функции f (x) = asin(x /100) , при x = 1,2,...,100. 3. Написать программу ввода в массив 20 чисел. 4. Записать в массив значения функции f (x) = a cos(x / 50) , при x = 1,2,...,100. 5. Написать программу ввода в массив 10 чисел. 6. Записать в массив значения функции f (x) = x 2 + b , при x = 1,2,...,10. 7. Написать программу ввода в массив 15 чисел. 8. Записать в массив значения функции f (x) = x 3 + 5/b , при x = 1,2,...,10. 9. Записать в массив значения функции f (x) = 1/ x + b , при x = 1,2,...,50. 10. Записать в массив значения функции f (x) = k/x + b, при x = 1,2,...,100. Лабораторная работа № 7 Обработка символьной информации, работа со строками Цель работы: познакомить с понятием «строка» и получить навыки работы с символьной информацией в языке программирования С++, научиться использовать строки символов и множества при решении задач. Общие сведения Символьная константа является символом, заключенным в апострофы. Управляющая последовательность рассматривается как одиночный символ и ее допустимо использовать в символьных константах. Значением символьной константы является числовой код символа. Например: ' ' – пробел , 'Q' – буква Q , '\n' – символ новой строки, '\\' – обратная дробная черта, '\0' – символ с нулевым кодом В языке C++ для хранения однобайтового символа используется тип данных char. Переменную типа char можно рассматривать двояко: как целое число, занимающее 1 байт и способное принимать значения от -128 до 127 (тип signedchar, есть также беззнаковая модификация unsignedchar, принимающая значения от 0 до 255) и как один символ текста. Само по себе определение char может оказаться как знаковым, так и беззнаковым, в зависимости от операционной системы и компилятора. Поэтому использовать тип char не рекомендуется, лучше явно указывать будет ли он знаковым (signed) или беззнаковым (unsigned). Как и целые числа, данные типа char можно складывать, вычитать, умножать и даже делить. Но если операции умножения и деления, как правило, бессмысленны, то сложение и вычитание вполне осмысленно. Например, если к символу 'A' прибавить 1, то получится символ 'B', а если вычесть 1, то получится символ '@'. То есть в следующем фрагменте кода на экран будет выведена буква B. char c = 'A'; c = c + 1; cout< Кроме того, этот пример показывает, что при выводе на экран переменной типа char мы увидим изображение этого символа. Значение ASCII-кода символа не нужно узнавать, сам символ – это и есть ASCII-код. Для того.чтобы вывести его на экран необходимо преобразовать значение величины типа char к значению типа int. Например: cout<< (int) c< Аналогично, при считывании переменной типа char через поток cout, из потока ввода считывается один символ, переменная получает значение, равное его ASCII-коду. Например, если написать программу, содержащую строку: char c; cin>>c; затем запустить ее, ввести символ A (без всяких кавычек!), то в переменную c будет записано значение 65 – ASCII-код символа A. Переменным типа char можно и явно присваивать числовые значения. Например: #include using namespace std; int main() { unsigned char c = 'A'; cout<< c << " " << (int) c < Эта программа выведет две строки: “A 65” и “ 126”, то есть символы с ASCII- кодами 65 (A) и 126 () и сами ASCII-коды. Организовать последовательное посимвольное считывание всего входного потока можно при помощи цикла while: #include { char c; while (cin>>c) // Цикл пока считывание успешно { // Делаем необходимые действия, // обрабатывая символ c } return 0; } В этом примере программа будет посимвольно считывать входной поток (по умолчанию – ввод с клавиатуры), пока не встретит признак конца файла. Для того, чтобы сообщить программе о завершении входного потока при вводе с клавиатуры необходимо нажать клавиши Ctrl-d в системе Linux и Ctrl-z в системе Windows. Эта программа при считывании данных будет игнорировать символы–разделители: пробелы, символы новой строки и табуляции. Если нужно, чтобы в переменную c считывались все символы, в том числе и разделители, то необходимо для потока ввода cin установить манипулятор noskipws при помощи инструкции: cin>>noskipws; Строковой константой называется последовательность любых символов заключенных в кавычки (") . Например: "Адыгейский государственный университет", "город Майкоп", "YZPT КОД". Все управляющие символы, кавычка ("), обратная дробная черта (\) и символ новой строки в строковой и символьной константах представляются соответствующими управляющими последовательностями. Каждая управляющая последовательность представляется как один символ. Например, при выводе на экран строки "Адыгейский \n государственный университет" его часть "Адыгейский" будет напечатана на одной строке, а вторая часть "государственный университет" на следующей строке. В конец каждой строковой константы компилятором автоматически добавляется нулевой символ (признак конца строки), представляемый управляющей последовательностью \0. Строки имеют тип char[] - это означает, что строка представляется как массив символов. Отметим, что тип char используется для представления символа. Строки в языке C++ Текстовая строка – это последовательность символов. Поскольку символы в строке пронумерованы, то естественным представлением для строки был бы массив символов. Так строки и представлялись в языке Cи – строкой считался массив символов, а для обозначения конца строки использовался символ с ASCII-кодом 0, что позволяло хранить строки переменной длины (то есть в массиве char[n] можно было хранить строки любой длины, не превосходящей n-1. Такой способ хранения строк порождал ряд неудобств: любая строка была ограничена по длине размером массива, а чтобы вычислить длину строки необходимо было пройти по всей строке до появления нулевого символа, то есть определение длины строки требует количество операций, пропорциональное этой длине. В языке C++ для представления строк существует более совершенный тип данных string, в основе которого лежит такой же массив символов, завершающийся нулевым символом, но содержащий еще ряд дополнительных возможностей. Для работы со строками языка C++ необходимо в начале программы подключить описание типа string, которое находится в одноименном файле: #include Переменная для хранения строковых данных объявляется так: string S; Присвоить строковой переменной некоторое константное значение можно так: S = "Hello, world!"; В рассмотренных ранее примерах мы уже встречались записью строк в тексте программы в кавычках – когда выводили текст в поток cout. Обратите внимание – константы типа char записываются в одинарных кавычках, а строки – в двойных кавычках. В частности, 'A' – это символ, а "A" – это строка, состоящая из одного символа. Поэтому переменной типа char нельзя присвоить значение "A", поскольку они имеют несовместимые типы данных. По сути, переменная типа string является массивом символов и с каждым символом этой строки можно работать по отдельности, обращаясь к ним по индексу, как к элементам массива. Например: cout< Для определения длины строки есть метод size(), применяемый к строке. Он возвращает целое число – количество символов в строке. Его можно использовать так: string S; cin>>S; cout<< "Вы ввели слово " < Основная операция над строками – сложение: например, при сложении строк "Hello, " и "world!" получится строка "Hello, world!". Такая операция над строками называется конкатенацией. Пример использования конкатенации строк: string S, S1, S2; // Объявление трех строк cout<< "Who are you? "; cin>>S1; // Считали строкуS1 S2 = "Hello, " // Присвоили строке значение S = S2 + S1; // Использование конкатенации cout< Другая операция – изменение размера строки. Для этого существует метод resize, который применяется к строке. У метода resize есть две формы записи: с одним и с двумя параметрами. Если он вызывается с одним параметром, то этот параметр задает новую длину строки. Например, так: string S = "abcdefg" S.resize(3); cout< S.resize(6, 'd'); cout< String S1, S2, S3; // объявили 3 строки cin>>S1>>S2>>S3; ввести текст ‘Мама мыла раму’ (с произвольным количеством пробелов между словами), то в массив S1 будет записана строка "Мама", в S2 – "мыла", в S3 – "раму". Таким образом, организовать считывание всего файла по словам, можно следующим образом: string s; while (cin>>s) // Цикл пока считывание успешно { // Делаем необходимые действия } Если нужно считать строку со всеми пробелами, то необходимо использовать функцию getline следующим образом: string S; getline(cin, S); В данном случае если запустить эту программу и ввести строку "Мама мыла раму", то именно это значение и будет присвоено строке S. Считать же весь входной поток по строкам можно при помощи следующего кода: string S; while (getline(cin, S)) // Цикл пока считывание успешно { // Делаем необходимые действия Пример 1. Заменить во введенном с клавиатуры тексте все встречающиеся символы "n" на символ "b". Словесный алгоритм будет иметь вид: а) Формирование тела программы, объявление переменных; б) Ввод текста; в) Выяснение, не пустая ли строка; г) Если строка не пуста, то цикл, в котором сравнение очередного символа введенной строки с искомой переменной, с последующей заменой ее на определенный символ. На языке С++ данный алгоритм будет реализован следующей программой: #include #include #include // Установка русской страницы setlocale(LC_ALL, "Russian"); // Чтение введенной с клавиатуры строки. cout<<"Введите текст для замены:"; getline(cin, s0); s1="n"; s2="b"; // Выясняем, не пустая ли строка. if (s0.empty()){ cout << "String is empty"<<"\n"; } else{ cout << "String isn't empty. Replacing..."<<"\n"; for (int i=0; i _getch(); } Реализовав данную программу в интегрированной среде программирования, получим результирующее окно, представленное на рисунке 7.1. Рис. 7.1. Окно выполнения задачи Пример 2. Дан текст (допустим используются латинские символы), слова в котором будут разделяться пробелами. Требуется напечатать все слова с удвоенной буквой "n". Этапы решения задачи: Разобьем задачу на несколько блоков а) формирование тела программы, объявление переменных; б) ввод текста; в) определение начальных переменных и выяснение, не пустая ли строка; г) если строка не пустая, то организуем цикл пока она не кончится; д) сбрасываем flag и заполняем строку s1 пробелами; е) организуем цикл до окончания строки с текстом (выйдем, как только встретим пробел). Если очередной символ строки s0 не пробел, то копируем его в строку s1; ж) поиск в строке s1 (очередное слово) удвоенных букв "n" и печать найденного слова; з) удаление найденного слова из строки s0, включая последующий пробел. и) если текст не закончился возвращение к пункту (д). |