Размещено на http://www.allbest.ru/

ФИНАНСОВЫЙ УНИВЕРСИТ ПРИ ПРАВИТЕЛЬСТВЕ РФ

КОНТРОЛЬНАЯ РАБОТА № 1

по дисциплине: "Информатика и программирование"

МОСКВА

2013

1. Ввод и вывод данных

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

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

Существует несколько способов консольного ввода и вывода.

Первый способ - это использование функции ввода printf() и функции вывода scanf() (унаследована в С++ от С).

Второй способ - это использование оператора ввода cin >> и оператора вывода cout <<.

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

>> x - перемещает данные в x, а << x - перемещает данные из x.

Запомните:

Для работы с функциями printf();и scanf() необходимо подключить библиотеку базовых функций <stdio.h> директивой #include<stdio.h>

Для работы с операторами cin и cout необходимо подключить библиотеку <iostream> директивой #include<iostream> (табл. 2.1).

Таблица 2.1

Функции и операторы ввода/вывода информации

	Библиотека stdio.h	Библиотека iostream
Вывод	Функция printf();	Оператор cout
Ввод	Функция scanf();	Оператор cin

Функции ввода/вывода printf() и scanf()

Для ввода/вывода данных в стиле C используются функции, которые описываются в библиотечном файле stdio.h. Программа, содержащая обращения к функциям ввода-вывода, должна содержать строку подключения этого файла: #include <stdio.h>.

Рассмотрим шесть наиболее распространенных функций ввода информации с клавиатуры и ее вывода на экран (консольный ввод-вывод): getchar, putchar (для ввода-вывода символа); gets, puts (для ввода-вывода строки); scanf, printf (для форматированного ввода-вывода ); и функцию flush очистки буфера stdin.

Функция getchar предназначена для ввода символа, не имеет параметров, возвращает целое число - код введенного символа. Обращение имеет вид: getchar(). Выполняя эту функцию, программа приостанавливает свою работу и ждет от пользователя ввода символа и/или нажатия клавиши Enter. Заметим, что: 1. Эту функцию мы уже неоднократно использовали ранее для организации задержки смены экрана. 2. Будем использовать в последующих лабораторных работах для этих же целей.

Функция putchar предназначена для вывода символа. Имеет один параметр типа int (код выводимого символа) или char. Обращение имеет вид: putchar(i), где i - выражение, определяющее символ. После вывода символа курсор не переходит к началу новой строки.

Функция getchar() может использоваться в операторе присваивания. В этом случае код введенного символа присваивается переменной типа int (в примере - переменной ch).

Функция gets предназначена для ввода строки. Имеет один параметр, задающий адрес области памяти, в которую помещаются символы вводимой строки. В языке Си имя переменной, имеющей строковый тип, является этим адресом. Обращение имеет вид: gets(name)), где name - переменная строкового типа - имя вводимой строки. Выполняя эту функцию, программа приостанавливает свою работу и ждет от пользователя ввода последовательности символов и/или нажатия клавиши Enter.

Функция puts предназначена для вывода строки. Имеет один параметр, задающий адрес области памяти, из которой на экран выводятся символы. Как уже отмечалось, имя переменной, имеющей строковый тип, является этим адресом. Обращение имеет вид: puts(name)), где name - переменная-строка - имя выводимой строки или строка символов, заключенная в кавычки. После вывода строки курсор перемещается к началу новой строки экрана

Пример 2.5.

данные оператор контейнер алгоритм

/* Ввод-вывод с использованием функций getchar, putchar, gets, puts */

#include <stdio.h>

#include <conio.h>

main()

{

char nf[40]; int ch; clrscr();

puts("**************************");

put ("Введите Ваше имя и фамилию");

gets(nf);

puts("Вас зовут"); puts(nf);

puts("Введите любой символ"); ch=getchar();

puts("Вы ввели символ"); putchar(ch);

puts("**************************");

getch(); /*Организации задержки смены экрана*/

return(0);

}

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

Функция scanf предназначена для вывода форматированной последовательности данных

Формат функции ввода:

scanf("строка_формата", &список_переменных);

Основным отличием применения функции scanf() от функции printf() является знак & перед именем переменной, в которую записываются результаты ввода.

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

scanf(“ %d, %d ”, &n, &m);

Функция scanf() интерпретирует это так, как будто ожидает, что пользователь введет число, затем - запятую, а затем - второе число. Все происходит так, как будто требуется ввести два целых числа следующим образом:

88,221

или

88, 221

Функция scanf() возвращает число успешно считанных элементов. Если операции считывания не происходило, что бывает в том случае, когда вместо ожидаемого цифрового значения вводится какая-либо буква, то возвращаемое значение равно 0.

2. Определение последовательного контейнера

Контейнеры

Контейнер - это объект, который предназначен для хранения других объектов.

STL предоставляет два вида контейнеров:

o последовательные и

o ассоциативные.

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

Ассоциативные контейнеры получают доступ к своим элементам по ключу.

Все контейнерные классы библиотеки STL определены в пространстве имен std.

Последовательные контейнеры

Последовательный контейнер (последовательность) - это вид контейнеров, в котором введено отношение порядка для совокупности хранимых объектов.

Это означает, что для элементов контейнера определены понятия первый, последний, предыдущий и следующий. К этому виду контейнеров принадлежат

o векторы,

o списки,

o Деки,

o строки типа string.

Векторы

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

Библиотека STL предоставляет контейнерный класс vector, определенный в заголовочном файле и доступный в пространстве имен std.

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

template , class А = allocator>

class vector

{

// члены класса

}

По умолчанию память для элементов вектора распределяется и освобождается глобальными операторами new() и delete (). Таким образом, для создания нового элемента вектора вызывается конструктор класса Т. Для встроенных типов данных векторы можно определить следующим образом:

//Вектор целых чисел

vector vints;

//Вектор чисел типа

double vector vDbls;

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

vector int s(50);

Количество элементов в векторе можно узнать с помощью функции-члена size ():

size_type size() const;

Функция resize изменяет величину вектора. Она имеет следующий прототип:

void resize(size_type sz);

Если новая величина вектора sz больше текущей, то в конец вектора добавляется нужное число элементов класса Т. Если же новая величина вектора меньше текущей, вектор усекается с конца.

Функция

void pop_back(); //удаляет последний элемент вектора.

Обращаться к элементам вектора можно по индексам. Значения индекса начинаются с нуля. Например, присвоить значение четвертому элементу объявленного выше вектора можно следующим образом:

ints[3] = 15;

Если первоначально зарезервированная память для элементов вектора исчерпана, число элементов вектора будет автоматически увеличено.

Добавить элемент в конец вектора можно с помощью функции-члена push_back(), однако она требует, чтобы в классе хранимых в контейнере объектов был определен конструктор копирования (эта функция добавляет в контейнер копию элемента). Она имеет следующий прототип:

void push_back(const Т& х); //Добавить элемент в конец вектора

Проверить, не является ли контейнер пустым, можно с помощью функции-члена empty ():

bool empty() const; //является ли контейнер пустым

Она принимает значение true, если контейнер пуст.

Функция clear (), имеющая следующий прототип:

void clear(); //удаляет все элементы из вектора.

Функция front () возвращает ссылку на первый элемент в списке, а функция back () - на последний.

Функция at () работает подобно оператору индексирования ( [ ] ), но является более безопасной, поскольку проверяет, попадает ли переданный ей индекс в диапазон допустимых значений. Если индекс вне диапазона, она генерирует исключение out_of _range.

Функция insert () вставляет один или несколько элементов, начиная с указанной позиции в векторе. Функция pop_back () удаляет из вектора последний элемент. Кроме того, для класса vector определены обычные операции сравнения.

Рассмотри теперь функции-члены шаблонного класса vector.

Функция

size_type capacity() const; возвращает величину распределенной для вектора памяти в виде числа элементов, которые могут быть сохранены в векторе.

Функция

void reserve(size_type n); добавляет емкость вектору в предположении, что к вектору будут добавляться новые элементы.

После вызова этой функции последующие операции добавления элементов не будут вызывать перераспределения памяти, пока величина вектора не превзойдет n. Перераспределение памяти не появляется, если n не превосходит значения capacity(). Если происходит перераспределение памяти, то все итераторы и ссылки, указывающие на элементы вектора, становятся неверными.

Функция

reference back(); возвращает ссылку на последний элемент

функция

reference front(); возвращает ссылку на первый элемент вектора.

функция reference at(size_type n); возвращает ссылку на элемент со значением индекса n.

Функция

iterator insert (iterator position, const T& x);

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

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

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

Функция

reverse_iterator rbegin(); возвращает обратный итератор произвольного доступа, который указывает на область памяти за последним элементом.

Функция

reverse_iterator rend(); возвращает обратный итератор произвольного доступа, который указывает на первый элемент.

Списки

Список - это контейнер, предназначенный для обеспечения оптимального выполнения вставок и удалений объектов.

Библиотека STL содержит контейнерный класс list, предоставляющий в распоряжение двусвязный (двунаправленный) список. Он определен в заголовочном файле в пространстве имен std.

Этот класс имеет такие же функции, как вектор и ряд дополнительных функций.

Если с векторами итераторы используются редко, то при работе со списком они являются основным средством. Для создания списков предназначены конструкторы, которые имеют несколько форм. Конструктор

explicit list(const Allocator& alloc = Allocator() )

создает список, не содержащий элементов, причем список использует для распределения памяти объект alloc.

Следующий конструктор

explicit list(size_type n);

создает список длины n, содержащий копии значения по умолчанию объектов типа Т. Тип Т должен иметь конструктор по умолчанию. Список использует для распределения памяти объект alloc.

Конструктор list(size_type n, const T& value, const Allocator & alloc = Allocator()); создает список длины n, содержащий копии значения value объектов типа Т. Тип Т должен иметь конструктор по умолчанию. Список использует для распределения памяти объект alloc. В классе list определены дополнительные функции. Функции void push_front(const T& x); и void pop_front(); аналогичны функциям push_back() и pop_back(), однако осуществляют добавление и удаление элементов в начале списка. Функция void remove(const Т& value); удаляет элемент из списка.

Вызвав функцию sort (), можно отсортировать список: void sort();

Эта функция сортирует список в соответствии с отношением порядка, задаваемым операторной функцией operator< ().

Деки

Название абстрактной структуры данных "дек" происходит от сокращения английских слов double-ended queue - двусторонняя очередь.

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

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

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

Однако, как и список, он позволяет легко добавлять элементы в начало или конец совокупности. Эта возможность обеспечивается только частично в векторах. Как и списки, и векторы, дек поддерживает вставку элементов в середину хранимой совокупности. Такие операции в нем не столь эффективны, как в списке, однако все же более эффективны, чем в векторе. Класс deque определен в заголовочном файле в пространстве имен std.

Стеки

Стек является одной из самых распространенных в программировании структур данных. Данные в стеке организованы по принципу "последним вошел - первым вышел" (LIFO -Last In - First Out). Это означает, что добавлять и удалять элементы стека можно только с одного конца. Доступный конец стека называется его вершиной, операция добавления элемента в стек называется помещением в стек (по англ. push()), а операция извлечения элемента из стека - выталкиванием (по англ. pop ()).

Абстрактный тип данных стек традиционно определяется как объект, который реализует перечисленные ниже операции:

Функция Реализуемая операция empty () Возвращает true, если стек пуст size () Возвращает число элементов стека top () Возвращает (но не удаляет) в вершине стека push (newElernent) Помещает новый элемент в стек

pop () Удаляет (но не возвращает) элемент из вершины стека

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

Ввиду того, что класс stack не реализует итератор, универсальные алгоритмы, описываемые ниже, не могут применяться к стандартным стекам.

Объявление и инициализация стека

Стек не является независимым контейнерным классом. По терминологии STL он представляет собой контейнерный адаптер, который строится поверх других контейнеров, которые в действительности хранят элементы. Класс stack лишь позволяет контейнеру вести себя как стек. В связи с этим объявление стека должно задавать тип элементов, которые будут помещаться и извлекаться из него, а также - тип контейнера, который будет использоваться для хранения элементов. Контейнером по умолчанию для стека является дек, однако можно использовать также и список или вектор. Векторная версия, вообще говоря, меньше, тогда как версия, использующая дек в качестве контейнера, работает несколько быстрее.

Очереди

Очередь также относится к одному из самых распространенных типов абстрактных структур данных. Данные очереди организованы по принципу "первым вошел - первым вышел" (FIFO - First In - First Out). Это означает, что элементы помещаются в очередь с одного конца (который называется ее хвостом), а извлекаются - из другого (который называется ее началом).

STL предоставляет двустороннюю очередь - класс queue. Подобно стеку, он представляет собой контейнерный адаптер, который позволяет контейнеру вести себя как очередь. Класс queue адаптирует любой контейнер, который поддерживает операции front (), back (), push_back() и pop_front().

В частности, могут использоваться дек и список. Контейнером по умолчанию для очереди является дек. Для элементов, хранимых в очереди, должны быть определены операции меньше (<) и равно (==).

Как и любая абстрактная структура данных типа очередь, класс queue поддерживает операции:

Функция Реализуемая операция

empty () Возвращает true, если очередь пуста

size() Возвращает число элементов очереди

front() Возвращает (но не удаляет) элемент из начала очереди

back() Возвращает (но не удаляет) элемент из конца очереди

push(newElement). Помещает новый элемент в конец очереди

pop () Удаляет (но не возвращает) элемент из начала очереди

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

Ввиду того, что класс queue не реализует итератор, универсальные алгоритмы, описываемые ниже, не могут применяться к стандартным очередям.

3. Понятие ассоциативного контейнера

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

STL предоставляет четыре ассоциативных контейнера:

· карту (mар),

· мультикарту (multimap),

· множество (set)

· мультимножество (multiset).

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

map_Object[key_value] = object_value;

или в функциях push_back () и insert ().

Мультикарта - это вид ассоциативного контейнера, в котором допускаются неуникальные ключи для доступа к элементам. Это означает, что несколько элементов могут иметь одинаковое значение ключа.

Множество - это вид ассоциативного контейнера, в котором хранятся только уникальные ключи.

Мультимножество - это вид ассоциативного контейнера, в котором хранятся неуникальные ключи.

4. Обобщенные алгоритмы (Краткий обзор)

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

1. По очереди исследовать каждый элемент.

2. Если элемент равен искомому значению, то вернуть его позицию в коллекции.

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

4. Если мы достигли конца коллекции и не нашли искомого, то вернуть некоторое значение, показывающее, что нужного элемента нет.

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

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

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

· некоторый обобщенный тип для представления позиции элемента внутри контейнера и специального признака на случай, если элемент не найден. Обычно мы возвращаем индекс элемента либо указатель на него. В ситуации, когда поиск неудачен, возвращается - 1 вместо индекса или 0 вместо указателя.

Размещено на Allbest.ru

...