2014-02-24
866
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 1 2 3 4 5 6 7 8 9
Если удалить из этого фрагмента строки, не имеющие непосредственного отношения к решаемой задаче (это ввод данных в массивы, вывод данных на экран), то “скелет” алгоритма будет таким:
int N1 = 10, // Начальный размер массива
N2 = 20; // Новый размер массива
int *Arr = new int [N1]; // Создаем исходный массива из N1 элемента
……. // Работаем с массивом старой длины
int *Rez = new int [N2]; // Создаем промежуточный массив из N2 элементов
for (int i = 0; i < N1; ++ i) // Копируем данные из исходного массива
Rez[i] = Arr[i]; // в промежуточный
delete [ ] Arr; // Освобождаем память от исходного массива. Если этого не
// сделать, произойдет утечка памяти
Arr = Rez; // Изменяем переменную исходного массива
……. // Работаем с массивом новой длины
delete [ ] Arr; // Окончательно освобождаем память от исходного массива.
А вот как решается эта же задача при использовании стиля языка C:
int N1 = 10, // Начальный размер массива
N2 = 20; // Новый размер массива
int *Arr = (int *) malloc(N1 * sizeof (int)); // Создаем массив из N1 элемента
|
|
|
for (int i = 0; i < N1; ++ i) // Заполняем массив числами от 0 до 9
Arr[i] = i;
for (int i = 0; i < N1; ++ i) // Выводим массив на экран
cout << Arr[i] << " ";
cout << endl;
Arr = (int *) realloc(Arr, N2 * sizeof (int)); // Изменяем размер массива
for (int i = N1; i < N2; ++ i) // Дополняем массив числами от 10 до 19
Arr[i] = i;
for (int i = 0; i < N2; ++ i) // Снова выводим массив на экран
cout << Arr[i] << " ";
cout << endl;
delete [ ] Arr; // Окончательно освобождаем память от исходного массива.
А вот, что представляет “скелет” алгоритма, в этом случае:
int N1 = 10, // Начальный размер массива
N2 = 20; // Новый размер массива
int *Arr = (int *) malloc(N1 * sizeof (int)); // Создаем массив из N1 элемента
……. // Работаем с массивом старой длины
Arr = (int *) realloc(Arr, N2 * sizeof (int)); // Изменяем размер массива
……. // Работаем с массивом новой длины
delete [ ] Arr; // Окончательно освобождаем память от исходного массива.
Не правда ли, существенно короче и понятнее.
Перейдем к рассмотрению двумерных массивов. С ними дело обстоит несколько сложнее, чем с одномерными динамическими массивами.
В стиле C++ двумерный массив целых чисел можно создать и удалить следующим образом:
int (* Arr) [ 10 ] = new int [ dim ] [ 10 ];
delete [ ] Arr;
В этом примере создается двумерный массив из dim строк и 10 столбцов. Элементами массива являются целые числа типа int. При таком способе создания двумерных массивов изменять в процессе выполнения программы можно только самую левую размерность массива (dim). Вторая размерность должна задаваться константным значением (в нашем случае 10). Таким образом, динамически изменяемым в таких массивах является только количество строк, а количество столбцов остается постоянным. Пример использования этого метода:
|
|
|
cin >> dim; // Вводим с клавиатуры количество строк массива
int (* Arr) [ 10 ] = new int [ dim ] [ 10 ]; // Выделяем память в динамической области
// Заполняем массив Arr значениями равными сумме индексов элементов массива
for (int i = 0; i < dim; ++ i)
for (int j = 0; j < 10; ++ j)
Arr [ i ] [ j ] = i + j;
// Выводим на экран элементы массива Arr в виде таблицы, содержащей dim строк и
// 10 столбцов
for (int i = 0; i < dim; ++ i)
{
for (int j = 0; j < 10; ++ j)
cout << setw(4) << Arr[i][j];
cout << endl;
}
delete [ ] Arr; // Освобождаем память от массива Arr
Недостаток этого метода очевиден – мы можем управлять только одной размерностью такого массива.
Для того чтобы избавиться от этого недостатка представим двумерный массив как одномерный массив, элементами которого являются одномерные массивы элементов базового типа массива.
Пусть базовым типом элементов нашего двумерного массива, как и в предыдущем примере, будут целые числа типа int. Этот двумерный массив можно представить как набор из RowCount строк, то есть как одномерный массив строк. Этому массиву на приведенном ниже рисунке соответствует вертикальный массив, элементами которого являются указатели на тип int (каждый элемент этого массива будет содержать адрес первого элемента соответствующей строки int*). Каждая строка представляет собой одномерный массив из ColCount элементов типа int. Элементы массивов-строк служат для хранения данных, для которых и предназначен двумерный массив.
| int**Arr | ColCount | |||
| RowCount | int* | int* | ||
| int | int | …. | int | |
| int* | ||||
| int | int | ….. | int | |
| …. | …….. | |||
| int* | ||||
| int | int | ….. | int | |
Таким образом, для того чтобы получить двумерный массив, нам необходимо:
1. создать одномерный динамический массив из RowCount указателей на базовый тип элементов массива (в нашем случае указателей на тип int);
2. в цикле создать RowCount одномерных динамических массивов, каждый из которых содержит ColCount элементов базового типа (в нашем случае указателей на тип int) и адреса их первых элементов записать в соответствующие элементы “вертикального” массива.
Остается неясным вопрос: как определить массив указателей (“вертикальный” массив)? Обычный одномерный массив определяется как указатель на базовый тип данных элементов этого массива. Базовым типом элементов этого массива являются указатели int*. Для того чтобы определить указатель на указатель достаточно использовать следующую конструкцию: (int*)* или проще int**.
Таким образом, для того чтобы создать динамический массив Arr изуказателей, можно поступить так:
int ** Arr = new int * [ RowCount ]
Создание массива-строки p еще проще:
int * p = new int [ ColCount ]
Тогда для создания всего двумерного динамического массива необходимо выполнить следующие действия:
int ** Arr = new int * [ RowCount ]; // Создаем “вертикальный” массив
for (int i = 0; i < RowCount; ++ i)
Arr [ i ] = new int [ ColCount ]; // Создаем i-ый массив-строку
Для освобождения памяти необходимо:
1. сначала в цикле удалить RowCount массивов-строк;
2. затем удалить “вертикальный” массив.
for (int i = 0; i < RowCount; ++ i)
delete [ ] Arr [ i ]; // Удаляем i-ый массив-строку
delete [ ] Arr; // Удаляем “вертикальный” массив
Следующий рабочий фрагмент программы обеспечивает: создание такого двумерного массива размерности n на m (вводятся с клавиатуры), заполнение его некоторыми данными; вывод значений элементов массива на экран в виде таблицы; освобождение памяти:
int **CreateArr (unsigned RowCount, unsigned ColCount)
// Создает двумерный динамический массив целых чисел из RowCount строк
// и ColCount столбцов. Возвращает адрес массива.
{
int **Arr = new int* [RowCount];
for (unsigned i = 0; i < RowCount; ++i)
Arr[i] = new int[ColCount];
return Arr;
}
void FreeArr(int **Arr, unsigned RowCount)
// Удаляет двумерный динамический массив целых чисел Arr из RowCount строк
|
|
|
{
for (unsigned i = 0; i < RowCount; ++i)
delete [ ] Arr [ i ];
delete [ ] Arr;
}
int _tmain(int argc, _TCHAR* argv[])
{
int N1 = 10,
N2 = 20;
cin >> N1 >> N2; // Вводим размерности массива
int ** Arr = CreateArr (N1, N2); // Создаем массив
// Начинаем работу с массивом
for (int i = 0; i < N1; ++ i) // Заполняем массив данными
for (int j = 0; j < N2; ++ j)
Arr [ i ][ j ] = i + j;
for (int i = 0; i < N1; ++ i) // Выводим массив на экран
{
for (int j = 0; j < N2; ++ j)
cout << setw(4) << Arr [ i ][ j ];
cout << endl;
}
// Заканчиваем работу с массивом
FreeArr (Arr, N1); // Освобождаем память
system ("pause");
return 0;
}
В этом примере действия, связанные с созданием динамического двумерного массива и его удалением, оформлены в виде функций, чтобы не отвлекать внимание от содержания основного алгоритма. Операции с созданным таким образом двумерным динамическим массивом осуществляются точно так же, как и с обычными двумерными массивами.
Для создания динамических двумерных массивов с другими базовыми типами элементов достаточно в предыдущих примерах заменить тип данных int, на необходимый тип данных. Ну, и конечно, изменить работу с элементами массива в соответствии с их типом данных. Обязательные места исправлений выделены красным цветом.
По аналогии с двумерными динамическими массивами можно создавать и массивы большей мерности.
Одномерный однонаправленный список представляет собой совокупность отдельных элементов, каждый из которых содержит две части – информационную (Inf) и адресную (Adr). Информационная часть предназначена для хранения “полезных” данных и может иметь практически любой тип. Адресная часть каждого элемента содержит адрес следующего элемента списка. Схематическое изображение такого списка представлено на следующем рисунке.
| Beg = 100 |
| Inf Adr = 200 |
| Inf Adr = 400 |
| Inf Adr = 0 |
| Inf Adr = 500 |
Список может содержать произвольное количество элементов. Адресная часть последнего элемента списка содержит нулевой адрес, свидетельствующий об окончании списка.
Для работы со списком достаточно знать только адрес первого элемента списка (Beg). Зная адрес первого элемента списка можно последовательно получить доступ к любому другому его элементу.
|
|
|
Достоинством подобных структур являются простота добавления, удаления и перестановки элементов списка, которые осуществляются путем манипуляций с адресными частями без перезаписи всего списка.
Типовыми операциями при работе со списками являются:
· создание списка;
· освобождение памяти от списка (удаление списка);
· доступ к заданному элементу списка для манипуляций с его информационной частью;
· добавление нового элемента к списку;
· удаление элемента из списка;
· перестановка элемента списка на новую позицию внутри списка.
Рассмотрим эти операции на примере списка, в котором информационные части представляют собой, например, вещественные числа типа double. Все эти операции оформим в виде отдельных функций.
Прежде всего, определим необходимые типы данных для работы со списком.
Поскольку каждый элемент списка должен иметь две части, логичнее всего представить его в виде следующей структуры:
