билеты. 1. Алгоритм и его свойства. Способы записи алгоритма. Программа. Языки программирования. Примеры алгоритмов и программ
 Скачать 83.2 Kb.
|
|
Билет №11 1.Указатели. Операции с указателями. Примеры указатель – адресная информация о расположении информационного ресурса, через которую пользователь может обратиться к нему. При изменении содержимого объекта через указатель на него всегда возникает проблема синхронизации (разделения) ресурса между несколькими пользователями, имеющими адресную информацию о нем Операции над указателями Операция Значение операции *p Значение указуемой переменной p+i Указатель на i-ю переменную после указуемой p-i Указатель на i-ю переменную перед указуемой *(p+i) Значение i-й переменной после указуемой p[i] Значение i-й переменной после указуемой p++ Переместить указатель на следующую переменную p-- Переместить указатель на предыдущую переменную p+=i Переместить указатель на i переменных вперед p-=i Переместить указатель на i переменных назад *p++ Получить значение указуемой переменной и переместить указатель к следующей *(--p) Переместить указатель к переменной, предшествующей указуемой, и получить ее значение p+1 Указатель на свободную память вслед за указуемой переменной Другие операции над указателями Сравнение указателей на равенство Пустой указатель (NULL-указатель). Сравнение указателей на «больше-меньше» Примеры работы с указателями: //----- Функция возвращает ссылку на минимальный элемент массива int &ref_min(int A[], int n){ for (int i=0,k=0; i if (A[i] return A[k];} void main(){ int B[5]={4,8,2,6,4}; ref_min(B,5)++; for (int i=0; i<5; i++) printf("%d ",B[i]); } //----- Функция возвращает указатель на минимальный элемент массива int *ptr_min(int *p, int n){ int *pmin; for (pmin=p; n>0; p++,n--) if (*p < *pmin) pmin=p; return pmin;} void main(){ int B[5]={4,8,2,6,4}; (*ptr_min(B,5))++; for (int i=0; i<5; i++) printf("%d ",B[i]); } 2. Структуры. Определение, инициализация, присваивание структур, доступ к элементам структур, указатели на структуры, битовые поля структур. Структура – это объединенное в единое целое множество поименованных элементов данных. Элементы структуры (поля) могут быть различного типа, они все должны иметь различные имена. Пример инициализации struct Student { char name[20]; int kurs; float rating; }; Student s={”Иванов”,1,3.5}; Для переменных одного и того же структурного типа определена операция присваивания. При этом происходит поэлементное копирование. Student ss=s; Доступ к элементам структур обеспечивается с помощью уточненных имен: Имя_структуры.имя_элемента employee.name – указатель на строку «Петров»; employee.rate – переменная целого типа со значением 10000 При определении указатель на структуру может быть сразу же проинициализирован. Student *ps=&mas[0]; Указатель на структуру обеспечивает доступ к ее элементам 2 способами: 1.(*указатель).имя_элемента 2. указатель->имя_элемента cin>>(*ps).name; cin>>ps->title; Битовые поля – это особый вид полей структуры. При описании битового поля указывается его длина в битах (целая положительная константа). Битовые поля могут быть любого целого типа. Они используются для плотной упаковки данных. Например, с их помощью удобно реализовать флажки типа «да» / «нет». Особенностью битовых полей является то, что нельзя получить их адрес. Размещение битовых полей в памяти зависит от компилятора и аппаратуры. Билет №12 1. Динамические переменные. Операции new и delete. Примеры. Динами́ческая переме́нная — переменная в программе, место в оперативной памяти под которую выделяется во время выполнения программы. По сути, она является участком памяти, выделенным системой программе для конкретных целей во время работы программы. Этим она отличается от глобальной статической переменной - участка памяти, выделенного системой программе для конкретных целей перед началом работы программы. Динамическая переменная — один из классов памяти переменной. Оператор new – Оператор new выделяет память для хранения значения типа тип_переменной и возвращает ее адрес. С помощью new могут быть размещены любые типы данных. Оператор delete – Оператор delete освобождает память, на которую указывает указатель переменная_указатель. Пример Использование динамической переменной #include using namespace std; int main() { int *a = new int; // Объявление указателя для переменной типа int int *b = new int(5); // Инициализация указателя *a = 10; *b = *a + *b; cout << "b is " << *b << endl; delete b; delete a; return 0; } Освобождение памяти #include using namespace std; int main() { // Выделение памяти int *a = new int; int *b = new int; float *c = new float; // ... Любые действия программы // Освобождение выделенной памяти delete c; delete b; delete a; return 0; } 2. Динамические структуры данных (однонаправленные и двунаправленные списки). Во многих задачах требуется использовать данные, у которых конфигурация, размеры и состав могут меняться в процессе выполнения программы. Для их представления используют динамические информационные структуры. К таким структурам относят: -линейные списки; -стеки; -очереди; -бинарные деревья; Они отличаются способом связи отдельных элементов и допустимыми операциями. Динамическая структура может занимать несмежные участки динамической памяти. Линейный список — это динамическая структура данных, каждый элемент которой посредством указателя связывается со следующим элементом. Каждый элемент односвязного списка кроме собственно данных содержит поле с адресом следующего элемента. В двухсвязном списке каждый элемент имеет поля с данными и два указателя: один указатель хранит адрес предшествующего элемента списка, второй — адрес последующего элемента. Над списками можно выполнять следующие операции: -начальное формирование списка (создание первого элемента); -добавление элемента в конец списка; -добавление элемента в начало списка; -удаление элемента с заданным номером; -чтение элемента с заданным ключом; -вставка элемента в заданное место списка (до или после элемента с заданным клю- чом); -упорядочивание списка по ключу Билет №13 1. Ссылки. Примеры. Ссылка — это тип переменной в C++, который работает как псевдоним другого объекта или значения. Ссылки бывают как на константные, так и не на константные переменные. Ссылка (на неконстантное значение) объявляется с использованием амперсанда (&) между типом данных и именем ссылки: int value = 7; // обычная переменная int &ref = value; // ссылка на переменную value 2. Создание списка, печать, удаление, добавление элементов (на примере однонаправленных и двунаправленных списков). Двунаправленные (двусвязные) списки Для ускорения многих операций целесообразно применять переходы между элементами списка в обоих направлениях. Это реализуется с помощью двунаправленных списков, которые являются сложной динамической структурой. Двунаправленный (двусвязный) список – это структура данных, состоящая из последовательности элементов, каждый из которых содержит информационную часть и два указателя на соседние элементы . При этом два соседних элемента должны содержать взаимные ссылки друг на друга. В таком списке каждый элемент (кроме первого и последнего) связан с предыдущим и следующим за ним элементами. Каждый элемент двунаправленного списка имеет два поля с указателями: одно поле содержит ссылку на следующий элемент, другое поле – ссылку на предыдущий элемент и третье поле – информационное. Наличие ссылок на следующее звено и на предыдущее позволяет двигаться по списку от каждого звена в любом направлении: от звена к концу списка или от звена к началу списка, поэтому такой список называют двунаправленным. Описание простейшего элемента такого списка выглядит следующим образом: struct имя_типа { информационное поле; адресное поле 1; адресное поле 2; }; где информационное поле – это поле любого, ранее объявленного или стандартного, типа; адресное поле 1 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка ; адресное поле 2 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес предыдущего элемента списка struct list {type elem ; list *next, *pred ;} list *headlist ; Билет №14 1. Одномерные массивы и указатели. Примеры. В языке С имя массива – это указатель-константа на первый байт нулевого элемента массива. Другими словами, имя массива имеет значение, равное адресу нулевого элемента массива или равное адресу начала самого массива. Этот указатель отличается от обычных указателей тем, что его нельзя изменить (например, установить на другую переменную), поскольку он сам хранится не в переменной, а является просто некоторым постоянным адресом. Следствием такой интерпретации имен массивов является то, что для того чтобы установить указатель p на начало массива, надо написать: int *p, mas[10]; p = mas; p = &mas[0]; но не p = &mas; // операция & перед одиноким именем массива не нужна // и недопустима (нельзя получить адрес константы)! 2. Потоковый ввод-вывод в С++. Открытие и закрытие потока. Стандартные потоки ввода-вывода. Библиотека ввода-вывода C++ предусматривает четыре предопределенных объекта-потока, связанных со стандартными входным и выходным устройствами. Ниже дана сводка этих объектов. Cin – стандартный ввод с клавиатуры Cout – стандартный вывод на экран Cerr – показ ошибок на экране без буферизации Clog – показ ошибок с буферизацией Операции извлечения и передачи в поток Основными классами ввода-вывода C++ являются istream и ostream. Первый из них перегружает операцию правого сдвига (>>), которая служит в нем для ввода данных и называется операцией извлечения из потока. Класс ostream перегружает соответственно операцию левого сдвига (<<); она применяется для вывода и называется операцией передачи в поток. Билет №15 1. Многомерные массивы и указатели. Примеры. Указатели на многомерные массивы в языке СИ — это массивы массивов, т.е. такие массивы, элементами которых являются массивы. При объявлении таких массивов в памяти компьютера создается несколько различных объектов. Например при выполнении объявления двумерного массива int arr2[4][3] в памяти выделяется участок для хранения значения переменной arr, которая является указателем на массив из четырех указателей. Для этого массива из четырех указателей тоже выделяется память. Каждый из этих четырех указателей содержит адрес массива из трех элементов типа int, и, следовательно, в памяти компьютера выделяется четыре участка для хранения четырех массивов чисел типа int, каждый из которых состоит из трех элементов. Такое выделение памяти показано на схеме на рис.3. Например, обращение к элементу arr2[1][2] можно осуществить с помощью указателя ptr2, объявленного в форме int *ptr2=arr2[0] как обращение ptr2[1*4+2] (здесь 1 и 2 это индексы используемого элемента, а 4 это число элементов в строке) или как ptr2[6]. Заметим, что внешне похожее обращение arr2[6] выполнить невозможно так как указателя с индексом 6 не существует. 2. Символьный, строковый, блоковый и форматированный ввод-вывод. Функция форматированного вывода printf получает в качестве аргументов строку формат и аргументы, которые необходимо вывести в соответствии с форматом, и возвращает число выведенных символов. В случае ошибки возвращает отрицательное значение и устанавливает значение ferror. Если произошло несколько ошибок, errno равно EILSEQ. int printf (const char * format, ...); Для блокового ввода и вывода используются функции : int fread( void *ptr, int size, int n, FILE *fp) , где void *ptr - указатель на область памяти, в которой размещаются считываемые из файла данные; int size - размер одного считываемого элемента; int n - количество считываемых элементов; FILE *fp - указатель на файл, из которого производится считывание. В случае успешного считывания информации функция возвращает число прочитанных элементов (а не байтов), иначе возвращает EOF. 2) int fwrite( void *ptr, int size, int n, FILE *fp) , где void *ptr - указатель на область памяти, в которой размещаются записываемые в файл данные; int size - размер одного записываемого элемента; int n - количество записываемых элементов; FILE *fp - указатель на файл, в который производится запись. В случае успешной записи информации функция возвращает число записанных элементов, иначе возвращает EOF. (Строковый) При вводе строк, как и символов, используется функция scanf(). При этом для форматного ввода и вывода строк используется спецификатор %s. Однако нажатие клавиши [Enter] или клавиши [пробел] не является значимым символом. При вводе строки с помощью функции scanf() нажатие одной из этих клавиш формирует символ конца строки. Таким образом надо помнить, что функция scanf() позволяет записать в строку только одно слово. Билет №16 1. Динамические массивы. Примеры. int main() { int num; // размер массива cout << "Enter integer value: "; cin >> num; // получение от пользователя размера массива int *p_darr = new int[num]; // Выделение памяти для массива for (int i = 0; i < num; i++) { // Заполнение массива и вывод значений его элементов p_darr[i] = i; cout << "Value of " << i << " element is " << p_darr[i] << endl; } delete [] p_darr; // очистка памяти return 0; } Синтаксис выделения памяти для массива имеет вид указатель = new тип[размер]. В качестве размера массива может выступать любое целое положительное значение. 2. Прямой доступ к файлам. Для внешних файлов определены два сорта доступа: последовательный доступ и прямой доступ. В настраиваемых пакетах SEQUENTIAL_IO и DIRECT_IO описаны соответствующие файловые типы и связанные с ними операции. Объект файлового типа, используемый для последовательного доступа, называется последовательным файлом, а используемый для прямого доступа — прямым файлом. Для использования прямого доступа к файлу требуется стандартная библиотека Файлы прямого доступа могут быть форматными, двоичными, неформатными. Все записи в файле прямого доступа имеют одинаковую длину. Длина записи задается параметром RECL= в операторе открытия файла. Для открытия форматного файла прямого доступа в программе записывается оператор следующей структуры: OPEN(N, FILE=fname, ACCESS=`DIRECT`, FORM=`FORMATTED`, RECL=recl) Оператор открытия двоичного файла прямого доступа: OPEN(N, FILE=fname, ACCESS=`DIRECT`, FORM=`BINARY`, RECL=recl) Здесь recl – целое число, задающее длину записи. По умолчанию файл прямого доступа имеет опцию FORM=`UNFORMATTED`. В файле прямого доступа можно перейти на начало любой записи с номером r с помощью оператора read, в котором задан параметр REC=r-1. При этом список ввода может отсутствовать. В неформатном или двоичном файле оператор имеет вид READ(N, [rec=r-1]) [список_ввода] В форматном файле: READ(N, frm, [rec=r-1]) [список_ввода] Если список ввода отсутствует, то просто происходит установка ФУ на соответствующую запись. Если отсутствует параметр rec=, то читается текущая запись. Аналогично записывается оператор WRITE для двоичного или неформатного файла: WRITE(N, [rec=r-1]) список_вывода Для форматного файла: WRITE(N, frm, [rec=r-1]) список_вывода Билет №17 1. Символьная информация и строки. Функции для работы со строками (библиотечный файл string.h). Символьная информация и строки. Функции для работы со строками (библиотечный файл string.h) Символ – элементарная единица, некоторый набор которых несет определенный смысл. В языке программирования С++ предусмотрено использование символьных констант. Символьная константа – это целочисленное значение (типа int) представленное в виде символа, заключённого в одинарные кавычки Строки в С++ представляются как массивы элементов типа char, заканчивающиеся нуль-терминатором \0 называются С строками или строками в стиле С. \0 — символ нуль-терминатора. Символьные строки состоят из набора символьных констант заключённых в двойные кавычки. При объявлении строкового массива необходимо учитывать наличие в конце строки нуль-терминатора, и отводить дополнительный байт под него. При объявлении строки не обязательно указывать её размер, но при этом обязательно нужно её инициализировать начальным значением. Тогда размер строки определится автоматически и в конец строки добавится нуль-терминатор. Строка может содержать символы, цифры и специальные знаки. В С++ строки заключаются в двойные кавычки. Имя строки является константным указателем на первый символ. Примеры: //инициализация строки без указания размера char string[] = "abcdefghf"; //всё то же самое только размер не указываем. // посимвольная инициализация строки: char string[10] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'f', '\0'}; // десятый символ это нуль-терминатор. В языке C++ для удобной работы со строками есть класс string, для использования которого необходимо подключить заголовочный файл string. Строки можно объявлять и одновременно присваивать им значения: string S1, S2 = "Hello"; Строка S1 будет пустой, строка S2 будет состоять из 5 символов. К отдельным символам строки можно обращаться по индексу, как к элементам массива или C-строк. Например S[0] - это первый символ строки. Для того, чтобы узнать длину строки можно использовать метод size() строки. Например, последний символ строки S это S[S.size() - 1]. Строки можно создавать с использованием следующих конструкторов: string() - конструктор по умолчанию (без параметров) создает пустую строку. string(string & S) - копия строки S string(size_t n, char c) - повторение символа c заданное число n раз. string(size_t c) - строка из одного символа c. string(string & S, size_t start, size_t len) - строка, содержащая не более, чем len символов данной строки S, начиная с символа номер start. Конструкторы можно вызывать явно, например, так: S += string(10, 'z'); В этом примере явно вызывается конструктор string для создания строки, состоящей из 10 символов 'z'. Ввод и вывод легко воспроизводиться с помощью cin и cout. Можно считывать строки до появления символа конца строки при помощи функции getline. Сам символ конца строки считывается из входного потока, но к строке не добавляется: getline(cin S); Со строками можно выполнять следующие арифметические операции: = - присваивание значения. += - добавление в конец строки другой строки или символа. + - конкатенация двух строк, конкатенация строки и символа. ==, != - посимвольное сравнение. <, >, <=, >= - лексикографическое сравнение. То есть можно скопировать содержимое одной строки в другую при помощи операции S1 = S2, сравнить две строки на равенство при помощи S1 == S2, сравнить строки в лексикографическом порядке при помощи S1 < S2, или сделать сложение (конкатенацию) двух строк в виде S = S1 + S2. Некоторые команды для строки: Метод size() возращает длину строки. S.resize(n) - Изменяет длину строки, новая длина строки становится равна n. S.resize(n, c), где c - символ, то при увеличении длины строки добавляемые символы будут равны c. S.clear() - очищает строчку, строка становится пустой. S.empty() - возвращает true, если строка пуста, false - если непуста. S.push_back(c) - добавляет в конец строки символ c, вызывается с одним параметром типа char. S.append(n, c) - добавляет в конец строки n одинаковых символов, равных с. n имеет целочисленный тип, c - char. S.append(T) - добавляет в конец строки S содержимое строки T. T может быть объектом класса string или C-строкой. S.append(T, pos, count) - добавляет в конец строки S символы строки T начиная с символа с индексом pos количеством count. S.erase(pos) - удаляет из строки S с символа с индексом pos и до конца строки. S.erase(pos, count) - удаляет из строки S с символа с индексом pos количеством count или до конца строки, если pos + count > S.size(). 2. Создание бинарных и текстовых файлов, удаление, добавление, корректировка элементов, печать файлов. int main() { srand((unsigned)time(NULL)); // инициализация датчика случайных чисел /* открываем выходной текстовый файл для записи */ { ofstream strm("c:/textfiles/oonumber.txt"); for(int i = 0; i < 10; i++) // выводим 10 чисел strm << rand()%10 << '\n'; } // деструктор закроет файл /* открываем тот же текстовый файл для чтения */ { ifstream strm("c:/textfiles/oonumber.txt"); char ss[20] = {0}; while(true) { strm.getline(ss, 20); // читаем числа как строки if (strm.eof()) break; // проверяем конец файла cout << ss << '\n'; // выводим на экран } } // опять деструктор закрывает файл return EXIT_SUCCESS; } fread –функция для чтения из файла: fwrite – функция для записи в файл: fseek – функция для произвольного доступа к байтам бинарных файлов: |