6.Динамически выделяемая память, динамические массивы (вставка, удаление элементов с концов и в середине).

Создание динамических массивов

Как было сказано раньше, массивы также могут быть динамическими. Чаще всего операции new и delete применяются, для создания динамических массивов, а не для создания динамических переменных. Рассмотрим фрагмент кода, создания одномерного динамического массива.

// объявление одномерного динамического массива на 10 элементов:

float *ptrarray = new float [10];

// где ptrarray – указатель на выделенный участок памяти под массив вещественных чисел типа float

// в квадратных скобочках указываем размер массива

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

// высвобождение памяти отводимой под одномерный динамический массив:

delete [] ptrarray;

После оператора delete ставятся квадратные скобочки, которые говорят о том, что высвобождается участок памяти, отводимый под одномерный массив. Разработаем программу, в которой создадим одномерный динамический массив, заполненный случайными числами.

// new_delete_array.cpp: определяет точку входа для консольного приложения.

#include "stdafx.h"

#include <iostream>

// в заголовочном файле <ctime> содержится прототип функции time()

#include <ctime>

// в заголовочном файле <iomanip> содержится прототип функции setprecision()

#include <iomanip>

using namespace std;

Int main(int argc, char* argv[])

{

srand(time(0)); // генерация случайных чисел

float *ptrarray = new float [10]; // создание динамического массива вещественных чисел на десять элементов

for (int count = 0; count < 10; count++)

ptrarray[count] = (rand() % 10 + 1) / float((rand() % 10 + 1)); //заполнение массива случайными числами с масштабированием от 1 до 10

cout << "array = ";

for (int count = 0; count < 10; count++)

cout << setprecision(2) << ptrarray[count] << " ";

delete [] ptrarray; // высвобождение памяти

cout << endl;

system("pause");

return 0;

}

Созданный одномерный динамический массив заполняется случайными вещественными числами, полученными c помощью функций генерации случайных чисел, причём числа генерируются в интервале от 1 до 10, интервал задается так - rand() % 10 + 1. Чтобы получить случайные вещественные числа, выполняется операция деления, с использованием явного приведения к вещественному типу знаменателя - float((rand() % 10 + 1)). Чтобы показать только два знака после запятой используем функцию setprecision(2), прототип данной функции находится в заголовочном файле <iomanip>. Функция time(0) засевает генератор случайных чисел временным значением, таким образом, получается, воспроизводить случайность возникновения чисел.

7.Связные списки: виды списков, итерирование, поиск максимума и минимума, поиск индекса элемента по значению, поиск значения по индексу.

8.Связные списки: операции вставки и удаления элементов с концов и в середине, перестановка местами элементов в списке (без копирования).

таблице 1 перечислены операции вставки и удаления элементов в списках. Списки поддерживают все функции деков, а также специальные реализации алгоритмов remove() и remove_if(). Как это обычно бывает при использовании STL, правильность аргументов обеспечивается вызывающей стороной. Итераторы должны ссылаться на правильные позиции, конец интервала не должен предшествовать началу, элементы не должны удаляться из пустого контейнера.

Таблица 1. Операции вставки и удаления для списковОперация Описание

c.insert(pos,elem) -Вставляет копию elem в позицию итератора pos и возвращает позицию нового элемента

c.insert(pos,n,elem) -Вставляет n копий elem в позицию итератора pos (и не возвращает значения)

c.insert(pos,beg,end) -Вставляет копию всех элементов интервала [beg,end) в позицию итератора pos (и не возвращает значения)

c.push_back(elem)- Присоединяет копию elem в конец списка

c.pop_back() -Удаляет последний элемент (не возвращая его)

c.push_front(elem) -Вставляет копию elem в начало списка

c.pop_front() -Удаляет первый элемент (не возвращая его)

c.remove(val) -Удаляет все элементы со значением val

c.remove_if(op) -Удаляет все элементы, для которых op(elem) возвращает true

c.erase(pos) -Удаляет элемент в позиции итератора pos и возвращает позицию следующего элемента

c.erase(beg,end) -Удаляет все элементы из интервала [beg,end) и возвращает позицию следующего элемента

c.resize(num)- Приводит контейнер к размеру num (если size() при этом увеличивается, новые элементы создаются своим конструктором по умолчанию)

c.resize(num,elem)- Приводит контейнер к размеру num (если size() при этом увеличивается, новые элементы создаются как копии elem)

c.clear() -Удаляет все элементы (контейнер остается пустым)

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

Для удаления элементов в списках предусмотрены специализированные версии алгоритмов remove(). Эти функции работают быстрее алгоритмов remove(), потому что используют вместо элементов только внутренние указатели. Следовательно, в отличие от векторов или деков операцию remove() для списков следует вызывать в форме функции класса, а не алгоритма (смотри шаг 136). Чтобы удалить все элементы с заданным значением, воспользуйтесь следующей конструкцией (за подробностями обращайтесь на 109 шаг):

std::list<Elem> coll;

. . . . .

// Удаление всех элементов со значением val

coll.remove(val);

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

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

list.remove_if (notl(bind2nd(modulus<int>(),2)));

: Вставка элемента в середину 1-связного списка

Односвязные и двусвязные списки.

Линейные списки

Массивы и записи - простейшие примеры структур данных. С их помощью можно моделировать любые сколь угодно сложные информаионные структуры

Познакомимся с некоторыми из них.