Все записи автора Stilet

Список двунаправленный. Сортировка по полям и условиям




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

Для построения списка нам понадобятся две структуры: Одна — поля элемента списка. Вторая — сам элемент списка с якорями, которые будут связывать элементы между собой.

Первая структура может выглядеть так:

Это структура данных списка. В ней должны содержаться поля, которые непосредственно к самому списку (вернее к его структуре ) отношения не имеют, зато хранят информацию. Эта запись — контейнер (назовем ее так).

Вторая запись:

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

Для чего понадобился такой разворот на две структуры? Так будет удобнее производить сортировку. В обычных условиях список сортируется путем перенаправления его полей-якорей на другие элементы (Next и Prev в данном примере). Т.е. сами данные, как были в памяти так в той же ячейке (ячейках) и остаются, а меняются только указатели на соседей. И это конечно хорошо и правильно, но сложно. Чем выше сложность, тем больше вероятность нарваться на баг в программе. Поэтому стоит упростить программу, чтобы можно было не якоря менять, а данные местами (как обычно это делается в сортировке массивов к примеру). Поэтому целесообразнее данные выделить в отдельный блок-структуру, чтоб перетягивать их одним оператором, а не таскать каждое поле отдельно. Ниже вы увидите что имеется ввиду.

Для работы со списком нужны переменные головы списка и, по необходимости, хвоста:

И вот так уже будет выглядеть процедура наполнения списка:

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

Не забываем о процедуре освобождения списка. Оставлять мусор в памяти — дурной тон, даже если умная операционка сама умеет чиститься:

Процедура вывода:

Такая большая она из-за «марафета». Красивый вывод на экран — достаточно важная опциональность программы. Поэтому ширину для элементов и табличный вид стоит соблюсти.

Теперь переходим к самому интересному — сортировке списка. Процедуру сортировки я разбил на две части, убрав из нее условия проверки, которые анализируют нужно ли сортируемые элементы продвигать по списку в зависимости от условия. Сама же процедура сортировки выглядит так:

В нее договоримся передавать опции сортировки: Имя поля, которое подлежит сортировке, и направление сортировки (asc — по возрастанию или desc — по убыванию).

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

Функция анализатор выглядит так:

Она выполняет 4 условия:

  1. Если asc — по возрастанию, и сортируемое поле — х:
  2. Если desc — по убыванию, и поле то же
  3. Если asc — по возрастанию, но сортируется второе поле, строковое
  4. Если desc — по убыванию с строковым полем

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




Собираем описанное выше в одну программу и дописываем функцию main():

Обратите внимание: Я словами указываю, как сортировать список, по какому полю и в каком порядке.

Результат:

сортировка двунаправленного списка в С++

О втором методе сортировки списка путем перезацепления якорей можете почитать на programmersforum

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

Опишу небольшой код с применением этого контейнера, как альтернатива тому, что описано выше:

сортировка двунаправленного списка в С++

Если задача позволяет использовать STL — используйте. Решение окажется надежнее и не будет траты времени на изобретения своего механизма хранения списков.

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

Чтобы поддержать наш сайт — нажмите на копилку и выберите любой удобный способ.

Рассылка новых уроков по программированию:

Библиотека iostream. Основные операции

библиотека iostream, класс cin, класс cout, методы класса cout,  методы класса cin,  boolalpha, scientific, write, getline, getМодуль (или как говорят в случае с Си — хедер) или заголовочный файл iostream призван предоставить средства ввода-вывода, для стандартной консоли. Т.е. то, что вводит с клавиатуры и читает с экрана пользователь.

Все его возможности размещены в пространстве имен std, поэтому для его использования либо приходится приписывать префикс std, либо указывать пространство имен через using namespace

Или

В этой статье будем использовать первый вариант — подключение пространства имен через using namespace.

iostream содержит два основных класса:

  • cin — для обработки ввода с клавиатуры;
  • cout — для вывода в консоль переменных или просто текста;

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

Сразу скажу, что не всё, что присуще этим классам будет описано. Только самое часто используемое из функционала. Это операторы перенаправления форматированного вывода (<< и >>), которые занимаются выводом значений переменных в зависимости от их типов и указанного формата. Это операторы неформатированного чтения\записи (читай: по байтам или посимвольно), методы get(), put() и write() призванные просто вывести массив символов какими бы они ни были. И операторы форматирования setf(), width(), precision(), которые указывают для текущего вывода, как форматировать выводимое, как выравнивать его, по какой стороне и сколько ставить символов после запятой.

Класс cin

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

библиотека iostream, класс cin, класс cout, cin.get

Как сказано выше, для начинающих программистов, мы рассмотрим только некоторые из них.

Класс cin основан на классе istream, и содержит возможность перенаправления ввода. Используя перегрузку оператора >> , класс позволяет указать в какую переменную будет производиться ввод данных.

Перечисленные в примере переменные получают (считывают) свои данные согласно своим позициям в операции. В данном примере сначала считывается вещественное в d, потом целое в i, и затем строковая переменная. Это нужно обязательно учитывать — неправильная последовательность переменных может дать либо ошибку ввода, либо переменные могут получить данные им не предназначающиеся.

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

библиотека iostream, класс cin, класс cout, cin.get

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

Если нужно считать строку целиком до переноса каретки, стоит использовать рассматриваемый ниже метод getline().

Метод get()

Позволяет ввести символ или строку. При вводе стоки поддерживает разделитель, указанный программистом, до которого будет читаться строка. По умолчанию стоит символ перевода строки '\n' То есть метод get() ждет нажатия клавиши Энтер. Только потом обрабатывает считываемое.

При вводе символа в числовую переменную, метод возвращает код этого символа:

cin.get() часто ставят в конце программы, чтобы задержать консоль с результатами:

В классическом Си популярным аналогом является функция getchar() для такой задержки.

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

Схема простая: Передаем указатель на массив символов, передаем количество считываемого, и после нажатия клавиши Энтер, cin.get() считает в этот массив заданное количество символов. Остальные символы считаны не будут, поэтому чтобы освободить от них буфер ввода можно вызвать метод ignore().

Если указать третьим параметром символ-разделитель, cin.get() будет считывать либо сколько заказано символов, либо пока cin не встретит этот символ:

Тут в s строку считываются символы вплоть до первого пробела. Если пробелов не обнаружится — считываться будет либо до нажатия Энтер либо до n-ного символа.

Метод getline()

Аналогичен методу get(). Помимо всего, что «умеет» get(), переопределен для строк типа string. Так же как и get() умеет считывать до символа, указанного в качестве разделителя, так же первым параметром указывается массив символов, а вторым количество символов для считывания.

Использование его переопределенной версии в хедере string выглядит так:

Класс cout

Класс cout предполагает вывод данных в консоль. Базовый класс ostream. Основной оператор — перегруженный << Он указывает, какую переменную выводить в консоль.

Правила последовательности те же, что у cin — вывод слева направо.

Для перевода каретки на новую строку рекомендуется использовать оператор endl. Или передавать старый добрый ‘\n’

Метод put() выводит символ в консоль:

Выведет один символ.

Метод write() выведет блок символов из массива символов, переданный ему в качестве указателя

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

библиотека iostream, класс cin, класс cout, cout.write

Метод width() задает ширину выводимого, если необходимо выровнять до определенного количества символов. Как правило применяется при построении таблиц. Типичный пример: Вывод таблицы вычисления формулы (пример ниже).

Метод precision() указывает сколько цифр будет в дробной части, если выводится вещественная переменная.

Метод setf() определяет, как будет выравниваться (влево, вправо, по центру) выводимое, и в каком формате оно будет.

Комплексный пример этих методов можно увидеть в задании построения таблицы параболы:

библиотека iostream, класс cin, класс cout, методы класса cout

16-тиричное представление строки можно вывести, например, вот так :

библиотека iostream, класс cin, класс cout, методы класса cout, basefield

А так научный формат представления вещественного:

scientific, библиотека iostream, класс cin, класс cout, методы класса cout

Можно задать формат вывода булевских переменных:

библиотека iostream, класс cin, класс cout, методы класса cout, boolalpha

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

Рассылка новых уроков по программированию:


Согласен получать уведомления от purecodecpp.com на мой e-mail

Задача. Вычислить количество дней между датами.

Задача простая: Найти количество дней между двумя датами. Предусмотреть учет високосных лет.

Для практики предлагается два варианта:

  1. Одна из граничных дат описывается только годом. То есть начальная дата вводится полностью (например 25.12.2015), а вторая только год (например 2016). Производится подсчет дней до 01.01.2016
  2. Обе даты полные — описываются днем месяцем годом.

Приведу свой пример, частично решающий первый упрощенный вариант:

Здесь функция DaysCount() принимает в первых трех параметрах начальную дату (год, месяц, день) и последним параметром граничную (год, 1-й день января)

Решать можно любым способом, хоть циклом хоть чем-то еще. А вот решение по второму варианту не покажу :) Пусть оно будет домашним заданием. Удачи!

Вопросы задавайте в комментариях

Рассылка новых уроков по программированию:

Поиск подстроки в строке




алгоритмы поиска с++, поиск подстроки в строке, c++, как найти подстроку в строкеСейчас мы разберём на примерах, как может выглядеть алгоритм поиска подстроки в строке. Примеры будут основываться на функциях стандартных библиотек, ведь именно в таких функциях и проявляются все удобства написания программ. А вот классический разбор алгоритма, основанный на циклах и сравнениях, также достаточно примечателен. Поэтому мы его рассмотрим в этом же уроке.

Сам алгоритм в принципе очень прост. Есть две строки. Например "Hello world" и "lo"

Работать будем в два цикла:

  1. Первый будет выполнять проход по всей строке, и искать местоположение первой буквы искомой строки ( "lo" ).
  2. Второй, начиная с найденной позиции первой буквы — сверять, какие буквы стоят после неё и сколько из них подряд совпадают.

Проиллюстрируем поиск подстроки в строке:

алгоритмы поиска с++, поиск подстроки в строке, c++, как найти подстроку в строке, программирование на с++ для начинающих, доклад, курсовая работа

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

На третьей итерации совпал только первый символ искомой строки, а вот второй уже не совпадает. Придется первому циклу продолжить работу. Четвертая итерация дает необходимые результаты — совпадают все символы искомой строки с частью исходной строки. А раз все символы совпали — подстрока найдена. Работу алгоритма можно закончить.

Посмотрим, как выглядит классический код поиска подстроки в строке в С++:

Два цикла выполняют каждый свою задачу. Один топает по строке в надежде найти «голову» искомого слова (первый символ). Второй выясняет, есть ли после найденной «головы» «тело» искомого. Причем проверяет, не лежит ли это «тело» в конце строки. Т.е. не является ли длина найденного слова на единицу больше длины искомой строки, если учитывать, что в эту единицу попадает нулль-терминатор ( '\0' ).

алгоритмы поиска с++, поиск подстроки в строке, c++, как найти подстроку в строке, программирование на с++ для начинающих, доклад, курсовая работа

Мы видим, что программа нашла начало подстроки pa в ячейках символьного массива с индексом 0 и 4. Но почему? Ведь в слове parapapa 3 таких подстроки. Все дело в '\0' .

В целом смысл самого алгоритма на этом заканчивается. Больше никаких сложностей кроме нуля в конце строки нет. Однако, следует обратить внимание на множественность поиска. Что, если нам необходимо найти в строке несколько позиций? Сколько раз искомое слово встречается в строке и в каких местах? Именно это и призван контролировать третий параметр — int nномер вхождения в строку. Если поставить туда единицу — он найдет первое совпадение искомого. Если двойку, он заставит первый цикл пропустить найденное первое, и искать второе. Если тройку — искать третье и так далее. С каждым найденным искомым словом, этот счетчик вхождений уменьшается на единицу. Это и позволяет описать поиск в цикле:

То есть найти первое, второе, третье, четвертое совпадение… Пока функция не вернет -1, что укажет на отсутствие N-ного искомого в строке.

 

Теперь, для сравнения, поиск подстроки в строке С++ с хедером string.

Все! Класс string в С++ снабжен методом find(), возвращающий номер ячейки, с которого начинается тело искомой строки в исходной строке. Результат:

алгоритмы поиска с++, поиск подстроки в строке, c++, как найти подстроку в строке, программирование на с++ для начинающих, доклад, курсовая работа

Как же множественность? Да пожалуйста:

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

алгоритмы поиска с++, поиск подстроки в строке, c++, как найти подстроку в строке, программирование на с++ для начинающих, доклад, курсовая работа

Всё это есть в С++, и сам класс string достаточно удобный для работы со строками именно, как строками, а не просто с массивом символов.

Рассылка новых уроков по программированию:

Сортировка вставками




сортировка вставками с++, алгоритм сортировки вставками, программирование для начинающихЕще одним алгоритмом, разработанным для упорядочивания массивов, является алгоритм Сортировка вставками (Insertion Sort). Этот алгоритм (как и другие, рассматриваемые на нашем сайте) достаточно прост. Он состоит из двух циклов (один вложен в другой). Первый цикл производит проход по массиву, а второй — перемещение обрабатываемых элементов. Давайте сразу посмотрим, как может выглядеть код такой сортировки, а уже ниже разберем, как он работает.

Алгоритм Сортировка вставками можно описать следующими позициями:

  1. Запомнить во временную переменную ( buff в примере) значение текущего элемента массива;
  2. Пока элементы слева от запомненного значения больше чем запомненное — перемещаем их на позицию вправо. Получается, что предыдущий элемент займет ячейку запомненного. А тот, что стоит перед предыдущим — переместится в свою очередь на место предыдущего. И так элементы будут двигаться друг за дружкой.
  3. Движение элементов заканчивается, если очередной элемент, который нужно сдвинуть, оказывается по значению меньше, чем тот, что запомнили во временную переменную в начале цикла.
  4. Цикл берет следующий элемент, и опять сдвигает все, которые расположены перед ним и большие по значению.

Покажем визуально перемещение значения в массиве из семи элементов во время работы Сортировки вставками:

сортировка вставками с++, алгоритм сортировки вставками, программирование для начинающих

На первой итерации в переменную-буфер запишется значение из ячейки с индексом 1 и цикл будет проверять этот элемент. Там у нас находится число 2. Оно больше значения, которое записано в нулевой ячейке, поэтому перемещений не будет. Далее в переменную-буфер запишется значение из ячейки с индексом 2 и снова пойдет сравнение со значениями слева и т.д. Только на четвертой итерации внешнего цикла начнется перезапись значений. Тройка сначала поменяется местами с пятеркой, а затем с четверкой.

Таким образом, в процессе Сортировки вставками элемент записанный в buff «просеивается» к началу массива. А в случаях, когда будет найден элемент со значением меньше чем buff или будет достигнуто начало последовательности — просеивание останавливается.

Хорошая визуальная иллюстрация алгоритма Сортировка вставками есть на википедии:

сортировка вставками с++, алгоритм сортировки вставками, программирование для начинающих

Затраты времени на работу данного алгоритма полностью зависят от начальных данных: количества элементов в массиве и его изначальной упорядоченности. Это понятно, что чем больше массив — тем больше времени надо на его обработку. Также больше времени потребуется на сортировку массива в котором значения абсолютно не упорядочены.

Алгоритм Сортировка вставками хорош для небольших массивов (до нескольких десятков элементов). Еще эффективнее работает, если данные такого массива ранее были частично отсортированы. Если в массив будут добавляться новые данные (новые элементы), алгоритм сможет их сортировать по мере их добавления (в отличии от сортировки пузырьком и сортировки выбором). Эффективность алгоритма значительно возрастет, если добавить в код алгоритм бинарного поиска.

Предлагаем также посмотреть короткий видоурок по информатике с разбором алгоритма Сортировка вставками:

Рассылка новых уроков по программированию:

Сортировка выбором С++




сортировка выбором с++, алгоритм сортировки выбором, для начинающихСмысл Сортировки выбором (Selection Sort) состоит в поиске минимального значения элемента в массиве, и перемещения этого значения в начало массива. Нужно сразу оговориться, что в данном случае можно назвать «началом» массива (куда перемещается найденное минимальное значение). «Начало» в алгоритме Сортировка выбором с каждым шагом цикла смещается в сторону хвоста массива. Поэтому на первой итерации цикла, найденное минимальное значение меняется местами со значением в нулевой ячейке массива. На второй итерации «начало» уже будет указывать на следующую (первую) ячейку и так далее.

сортировка выбором с++, алгоритм сортировки выбором, для начинающих

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

Код программы весьма прост, и не требует каких-то особых описаний:

Роль «начала» здесь играет счетчик i внешнего цикла. На каждом шаге значение элемента, номер которого отсчитывает эта переменная, считается минимальным. Вложенный цикл проводит проход по хвосту массива, вычисляя номер ячейки массива с минимальным значением (строка 18 — тернарный оператор). Если после прохода вложенным циклом переменная min не изменилась, значит из всего хвоста массива, который обрабатывается, минимального значения нет, и элемент «начала» остается на своем месте. Иначе — значение меняется местами с найденным.

сортировка выбором с++, алгоритм сортировки выбором, для начинающих

Хвост обрабатываемого массива с каждым проходом циклов уменьшается и когда достигнет конца массива, он (массив) окажется уже отсортированным. Работа алгоритма Сортировка выбором прекратится.

Вот отличное короткое видео по информатике с разбором Сортировки выбором (Selection Sort):

Прочтите также наши следующие уроки посвященные алгоритмам сортировки: пузырьковая сортировка и шейкерная сортировка массива.

Рассылка новых уроков по программированию:

Битовые поля в С++




битовые поля с++, структуры в с++ для начинающихВ языке С++ есть возможность задавать элементам структур определённое количество памяти в битах. Например, если необходимо создать структуру данных, соответствующую размеру регистра в каком-либо устройстве. Типом элемента (его называют битовым полем) такой структуры может быть целочисленное (чаще всего типа unsigned) или перечислимое (enum).

Синтаксически битовое поле в структуре определяется следующим образом:
битовые поля с++, структуры в с++ для начинающихНапример:

Мы определили структуру, в которой переменные будут занимать указанное количество бит. 2 + 2 + 4 дает 8 бит (мы выровняли до размера байта). Если в эту структуру дописать еще unsigned short fifth : 5; — уже будет задействовано 2 байта. Во втором байте естественно будет мусор 8 — 5 = 3 бита, которые будут невостребованными.

В отличии от объединений (union) размер битовых полей варьируется, в зависимости от того, сколько бит программист заказал. Если заказано 7 бит (скажем две переменные по 3 бита, и одна — 1 бит), то С++ отведет один байт (8 бит) под эти три переменные. Если программист закажет 11 бит, то С++ отведет два байта (16 бит). Причем во втором байте будут задействованы только 5 бит, а остальные скорее всего будут, как бесполезный хвост. Поэтому при описании битовых полей следует учитывать такое «выравнивание» до байта. Т.е. распределять в нем переменные так, чтоб каждый бит был востребован. Для выравнивания занимаемой памяти можно использовать неименованные битовые поля.

Приведем еще один короткий пример, в котором битовые поля отводятся под дату и время для демонстрации этой технологии.

Результат:

битовые поля с++, структуры в с++ для начинающих

Как видите, битовые поля хранят дату и время. Занимает эта структура 6 байт, хотя для неё хватит и пяти. И на то есть свои причины: сам компилятор может выравнивать отводимую память до четного числа байтов. Например если мы заказали 18 бит, компилятор отведет нам не 3 байта, а 4, учитывая что процессор любит работать с байтами, а не с битами. По крайней мере хранить в памяти или своих регистрах процессор предпочитает не биты, а именно байты. Согласно его разрядности: x32 хранят 4 байта, x64 уже 8 байт. Пусть даже из этих байт работа идет только с одним из них, остальные все равно будут подтягиваться.

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

Рассылка новых уроков по программированию:

Объединения в С++ (union C++)




объединения в с++, union c++, доклад, курсовая работаТехнология объединений union берет свои истоки в 90-х. Слабенькие по нашим временам ЭВМ (сейчас их и компьютерами то не назовешь), мало памяти (все измерялось килобайтами). Жесткие диски по 40 мегабайт были чуть ли не чудом техники, олицетворяющим огроменные объемы информации, которые умельцами «растачивались» специальными ПО до хранения 80 мегабайт (чтоб побольше было). Каждый байт памяти был на вес золота, приходилось экономить на всём. Вот и объединение переменных тоже было призвано (и достаточно успешно, о чем я расскажу ниже) помочь программисту сделать оптимальную и экономную программу, «кушающую» маленькие объемы памяти.

Чтобы понять в чем смысл объединения нужно вспомнить как хранятся переменные. Разные переменные разного типа или одинаковой группы типов (вроде int, long и short) несмотря на работу с одним и тем же типом данных (имею ввиду целое) занимают в памяти разное количество байт. long в любом случае занимает максимальное количество байт в памяти, при этом в память для переменной этого типа вполне можно записать значения int или short. Просто получится, что не все зарезервированные байты long-а будут востребованы. Если поместить к примеру число 325 в long, будут заняты два байта (зависит от разрядности процессора), а остальные байты заполнятся нулями.

Именно в этом и появляется смысл union, ибо эта инструкция говорит компилятору: «Зарезервируй мне место для типа данных с максимальным запросом объема памяти, а я уже буду сама разбираться, как и какие значения в них положить».

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

Доступ к элементам объединения осуществляется так же, как и к элементам структур: Имя объекта объединения myUnion , точка . и имя элемента name1 .

К данным, которые хранят элементы структуры (например short, int, long) мы можем обращаться в любой момент (хоть к одному, хоть и ко всем сразу). А в объединении могут храниться данные либо short, либо int, либо long. Например:

Запускаем программу:

объединения в с++, union c++, доклад, курсовая работа

Как видите, после того, как мы записали значение в элемент name3 типа long int , уже невозможно нормально обращаться к элементу name1 . Все потому, что в их общую память уже записано значение long int, а переменная типа short int неспособна работать с данными такого объема. Схематически можно это представить так:

объединения в с++, union c++, доклад, курсовая работа

Поэтому, чтобы опять работать с данными типа short int необходимо снова присвоить элементу name1 новое значение. Вот и получается — память одна и та же, а переменные в ней размещаются разные. К какой обращаемся — такая и запрашивает из этой памяти значение.

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

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

Если бы мы описали просто набор переменных не объединяя их в union, то для их размещения потребовалось бы 2 + 4 + 4 байта = 10 байт. Вот и экономия. А так объединение занимает 4 байта. Целых 6 байт сэкономили, натрамбовав три переменные в один отрезок памяти.

К слову нужно заметить, что эта технология умудрилась получить неплохое продолжение, и в современных языках используется везде где нужно и не нужно. СиШарп, PHP, Делфи, современные наследники Си плюс плюс — все они используют такие объединения. Только в современном мире они уже называются variant. В переменную variant можно без проблем запихнуть до 10 байт (10 это максимум для 32-х разрядных систем под вещественное число). Соответственно в эти 10 байт и все семейство целых и вещественных, и указатели, и объекты, и строки (точнее описатели строк или указатели на них) вмещаются.

На сегодняшний день экономия памяти не так актуальна, как 15-20 лет назад. Конечно, никто не запрещает использовать union, но зачем? Если есть более удобные на сегодня средства работы с памятью для программиста.

Следует отметить также, что программы для выполнения в память загружаются с избытком (т.е. для программы выделяется количество памяти, зачастую чрезвычайно большее чем надо). Это можно наблюдать, написав программу с одной переменной. Казалось бы — переменная 4 байта, но открыв диспетчер задач в Винде программа «почему-то» заняла 10 килобайт. Так работает современная операционная система, выделяя памяти с лихвой. В 90-х, увы, такой роскоши и быть не могло.

В следующем уроке мы рассмотрим битовые поля в С++. Не поленитесь посмотреть видео по теме Объединения (union) в С++:

Рассылка новых уроков по программированию:

Решето Эратосфена С++




решето эратосфена в с++, алгоритм поиска простых чисел, c++ для начинающихРешето Эратосфена — один из древнейших алгоритмов, позволяющих найти числа, которые называют «простыми». Т.е. числа, которые могут делиться без остатка только на единицу и на себя. Например число 2. На что из натуральных (целых) чисел можно разделить 2, чтоб не получать остаток? Только на 2 и на 1. Или число 7. То же самое. Без остатка оно делится опять таки только на себя и единицу.

Достаточно простой алгоритм еще до нашей эры придумал хитрый дядько Эратосфен Киренский. Грек по национальности. Математик, астроном, географ. Решето дядьки Эратосфена достаточно популярный алгоритм поиска.

Какого-то особого описания этот алгоритм на самом деле не требует. Он предполагает два цикла прохода по набору чисел. Первый определяет следующее простое число, второй вложенный в него вычеркивает все сложные числа (по определенной формуле) стоящие после этого простого. Надо сразу оговориться, что второй цикл сразу все сложные числа не вычеркивает. Он вычеркивает следующие числа после простого, которые от этого простого находятся на определенном расстоянии. Расстояние это рассчитывается по формуле: Текущий элемент в квадрате + значение этого элемента. Например если число 5 простое, то следующее после него, которое стоит вычеркнуть будет равно 5*5 = 10, потом 5*5+5 = 15,потом 5*5+5+5 = 20… и так далее. Вычеркиваются таким образом числа кратные этому найденному простому. Нахождение простого начинается с числа 2. Соответственно вычеркиваются 2*2, 2*2+2, 2*2+2+2…

Хорошая иллюстрация есть на сайте Википедии:

решето эратосфена в с++, алгоритм поиска простых чисел, c++ для начинающих

Берем первое простое число 2 (синий кружочек) и вычеркиваем все числа, которые кратны двум (синие крестики). Потом берем простое число 3 (зеленый кружочек) и вычеркиваем все что ему кратно (зеленые крестики) и т.д.

После того, как числа вычеркнуты из списка легко определить следующее простое число — оно будет первое не вычеркнутое после текущего.

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

Работает сей код следующим образом: Запрашивается массив чисел. Я специально для удобства добавил к массиву один «вспомогательный» элемент в конец, чтоб программа начинала работать с массивом не с нуля, как принято отсчитывать в С++ массивы, а с единицы. Для наглядности естественно. После запроса массив заполняется числами по порядку. Можно было конечно не использовать массив чисел, а просто массив булевых (true, false), и простыми числами считать номера элементов, которые после просеивания будут содержать true, но я решил, что это не так наглядно.

После того, как числа в массиве размещены (1,2,3,4,5,6,7,8,9,10…n) можно приступать к их просеиванию. Пока что на начальном этапе все числа в решете считаются программой простыми. Первая итерация цикла берет первое (а точнее второе по счету) число — 2. От этого числа второй цикл обнуляет элементы массива, которые попадают под фильтр-условие Число*Число+Число. Таким образом просеиваются числа кратные двум после двойки. Далее первый цикл продолжает проход, проверяя условие if(a[i]) , т.е. есть ли в ячейке число, отличающееся от нуля (мы ведь обнуляем сложные числа). Как только такое число будет найдено, опять уже от него сработает второй цикл, обнуляя после найденного кратные ему числа, стоящие после него.

И так циклы просеивают числа пока не достигнут заданной нами границы просеивания — до какого числа вылавливать простые.

решето эратосфена в с++, алгоритм поиска простых чисел, c++ для начинающих

Где используются простые числа? Хм… Например в криптографии. Так же в некоторых генераторах случайных чисел. Ну и конечно же в ВУЗах :) По сути решетом преподаватели тоже не гнушаются и регулярно умело балуют студентов заданиями «Нахождения простого числа». Вот с помощью такого решета эта задача вполне решаема.

Рассылка новых уроков по программированию:

Интерполирующий поиск




интерполирующий поиск в с++, c++ для начинающих, алгоритм поиска доклад, курсовая работаУгадайте, какое самое любимое занятие многих преподавателей? Подсказываю: Выдумывать в своих классных комнатах страшно академические словечки, чтоб у студентов волосы встали дыбом от мегаулетности его сенсея. Одно из таких коварных словечек, повергающих молодых людей в шок — Интерполяция. Предлагаю осмотреть это чудо математической мысли с самого простейшего ракурса и используя минимум кода, чтоб не мулять глаза тоннами операторов, запутывая себя в теории.

Итак, для начала — что же это за слово такое «Интерполяция»? Интерполяция — это (если говорить на языке студента) определение области поиска, путем вычисления подобия расстояний между искомым значением и всей областью. Помните по геометрии подобие треугольников? Те, у которых одинаковые по значению углы, но пропорции разные. Здесь практически тот же принцип. Вычисляется длина области поиска, и длина от начала области до некоего числа (скажем до центрального элемента в массиве). Вычисление сие проводится как с номерами элемента, так и с их значениями, после чего полученная длина области умножается на длину между значениями, и результат прибавленный к значению из начала области дает искомое.

Сложно сразу понять на словах, поэтому попробую показать картинкой:

интерполирующий поиск в с++, c++ для начинающих, алгоритм поиска доклад, курсовая работа

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

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

Получается: 1 + (20-1)/(100-1) * (200-5) = 38 с копейками.

Результат и есть то самое искомое. Т.е. при таких значениях как на картинке в ячейке №20 будет стоять 38. Вот и весь смысл интерполяции — составления подобия между номерами элементов и между значениями элементов.

На С++ это выглядит так:

Таким образом сам цикл просто вычисляет по формуле область массива, где может находиться искомое используя этот самый принцип интерполяции в С++, подбирая подобия так сказать. Если вычисленное не равно искомому, значит нужно сдвинуть границы области, где проходит вычисление.

Если вычисленное больше — сдвигается правая граница области поиска, если меньше — левая. Так отрезая (как в бинарном поиске) кусок массива за куском постепенно достигается нужная ячейка массива, ну или границы области поиска сужаются до таких величин, в пределах которого уже искать нечего, когда дистанция между границами равна 1 (т.е. между точкой А и В нет более элементов для вычисления) решение говорит о том, что значение в массиве не найдено.

Как видите сам цикл не настолько уж и сложен и ужасен. Вся соль то скрыта в его форуме. А остальное — просто проверки: нашли или дальше искать. Вот такая вот она… интерполяция в С++

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

Рассылка новых уроков по программированию: