15.7. Ссылки УКАЗАТЕЛИ и многомерные массивы
(В С++ есть понятие ссылки int &a=b;)
Для решения одних и тех же задач можно использовать многомерные массивы и массивы указателей. Для простоты сравнения возьмем двумерный массив и одномерный массив указателей. Пусть имеем следующие определения:
short a[10][10];
short *b[10];
и пусть оба массива используются аналогичным образом, т.е. a[5][5] и b[5][5] допустимые обращения к одному и тому же целому значению. Тогда под массив a будет выделена память размером в 100 целых значений (200 байтов), а под массив b – размером в 10 указателей типа short. Если каждая ссылка массива b указывает на массив из 10 целых, то потребная память для решения составит: 100 целых + 10 указателей на short. Кроме того, необходимо будет динамически выделять память под массив. Однако, не требуется вычислять адрес элемента двумерного массива, а можно обратиться прямо по ссылке.
Второе преимущество: каждый элемент массива ссылок может указывать на массив, количество элементов которого может быть произвольным, т.е. с его помощью можно реализовать так называемые непрямоугольные массивы, содержащие разное число элементов в младших измерениях. Обычно это используют при работе с массивами строк (string). См. пример "Инициализация массива ссылок".
Пример. Вывод сообщений в окна.
#include
#define Screen BLACK
void message(short nom, // Номер сообщения
short reg){ // Режим: 1-вывод сообщения, 0-очистить окно
static struct mes{ // Описание сообщения
short beg_x, // Начальная позиция окна по x
beg_y, // Начальная позиция окна по y
end_x, // Конечная позиция окна по x
end_y, // Конечная позиция окна по y
regim; // Режим вывода текста: 'r' – с разрядкой,
// 'p' - плотный
char *text; // Текст сообщения
} def[ ]={ // Инициализация списка сообщений
28, 2, 54, 4, 'r', "ВВОД ДАННЫХ",
19, 12, 61, 14, 'p', "Имя файла входных данных",
……………………………………………………………..
19, 12, 61, 14, 'r', "ВВОД ДАННЫХ ЗАКОНЧЕН"
};
struct mes *p; // Указатель на элемент списка
p = &def[nom-1];
if(reg){ // Вывод сообщения в окно
init_window(p->beg_x, p->beg_y, p->end_x, p->end_y,
BLACK, LIGHTGRAY, 1);
out_text(2, 2, 200, p->regim, p->text);
}else{ // Очистка окна
clear_window(p->beg_x, p->beg_y, p->end_x, p->end_y, Screen);
}
} // End message
15.8. Рекурсивные процедуры
В языках C и Basic любая процедура может быть рекурсивной , т.е. в ее теле может быть обращение к самой себе. Такие процедуры применяются для реализации класса рекурсивных алгоритмов, наиболее простым и известным из которых является вычисление функции факториала.
Пример. Вычислить n!=n*(n-1)!.
short factorial(short n){
short fact;
if(n == 0){ // Условие завершение рекурсии
return 1;
}else{
fact = n * factorial(n – 1);
}
return fact;
}
Рекурсия реализуется с помощью рассмотренной выше структуры данных – стека. При этом не предусматриваются никакие механизмы защиты памяти, вследствие чего при неправильном программировании терминальной ветви рекурсивного алгоритма (см. пример выше) автоматически выделяемая память под каждый рекурсивный вызов (программный стек) будет переполняться и вызывать прерывание программы во время выполнения (run time error) с сообщением stack overflow (переполнение стека).
Рекурсивные процедуры работают не быстрее нерекурсивных, но зато они более компактны и понятны. Ниже разбирается пример реализации более сложного рекурсивного алгоритма. Для сравнения приводятся 2 нерекурсивных решения той же задачи.
Пример. "Ханойская башня".
Это последовательность дисков различного диаметра, положенных друг на друга так, чтобы диск меньшего диаметра располагался сверху.
Требуется: переместить башню с одной площадки на другую с соблюдением следующих условий:
- за 1 раз переносится 1 диск;
- нельзя ставить диск большего диаметра на диск меньшего диаметра;
- можно использовать только одну резервную площадку.
Рисунок ниже иллюстрирует процесс решения для n=2и n=3.
n=2 n=3
Площ. 1 Площ. 2 Площ. 3 Площ. 1 Площ. 2 Площ. 3
В соответствии с рисунком рекурсивное решение для n=3 записывается так:
hanoi(1, 3, 2)
hanoi(1, 2, 3) = 1→ 2
hanoi(3, 2, 2)
Для произвольного n и произвольных номеров площадок от 1 до 3 получим:
hanoi(a, 6-a-b, n-1)
hanoi(a, b, n ) = a → b
hanoi(6-a-b, b, n-1)
Здесь:
- a - № начальной площадки,
- b - № конечной площадки,
- n – число дисков в башне.
В общем случае для решения задачи требуется 2n -1 операций переноса дисков. Решение представляется в выводе на экран последовательности номеров начальной и конечной площадок. Для n=4 решение имеет вид:
1 → 3 1 → 2 3 → 2 1 → 3 2 → 1 2 → 3 1 → 3 1 → 2 3 → 2 3 → 1 2 → 1 3 → 2 1 → 3 1 → 2 3 → 2
15.8.1. Рекурсивное решение
void hanoi(short a, // № начальной площадки
short b, // № конечной площадки
short n){ // Число дисков
if(n == 1){ // Конец рекурсии
printf(" %2hd %2hd\n", a, b);
return;
}
hanoi(a, 6-a-b, n-1);
printf(" %2hd %2hd\n", a, b);
hanoi(6-a-b, b, n-1);
} // End hanoi
При каждом рекурсивном вызове процедуры hanoi транслятор помещает значения аргументов a, b, n в так называемый стек вызова, т.е. программисту не надо вручную записывать операции помещения в стек и извлечения из стека.
В нерекурсивном решении возможны 2 варианта реализации стека: в виде массива и в виде списка.
15.8.2. Нерекурсивное решение. Стек в виде массива
#define DEEP 20 // Максимальная глубина стека
void hanoi(short a, // Исходная площадка
short b, // Площадка - цель
short n){ // Число дисков
short stack[DEEP][3],
i; // Индикатор уровня стека
bool fl; // false – стек пуст. Конец вычислений
fl = true;
i = -1;
while(fl){
if(n > 1){ // Заполнение стека
i++;
stack[ i ][0] = a;
stack[ i ][1] = b;
stack[ i ][2] = n;
// Подготовить первое обращение
b = 6-a-b;
n--;
}else{
if(i >= 0){ // Стек не пуст
// Печать вершины уровня 1
printf(" %2hd %2hd\n", a, b);
// Извлечь данные из стека
a = stack[ i ][0];
b = stack[ i ][1];
n = stack[ i ][2];
// Печать "корня"
printf(" %2hd %2hd\n", a, b);
// Подготовить второе обращение
a = 6-a-b;
n--;
// Убрать вершину из стека
i--;
}else{ // Стек пуст
fl = 0;
}
}
} // End while
// Печать последней вершины
printf(" %2hd %2hd\n", a, b);
} // End hanoi
15.8.3. Нерекурсивное решение. Стек в виде списка
Причем:
- элемент стека – произвольная структура;
- операции над стеком позволяют организовать в программе произвольное число стеков.
Файл hanoi.cpp. Главная процедура и процедура решения "ханойской башни".
#include
#include
#include "stek.h" // Заголовочный файл для операций над стеком
int main( ){
short n;
void hanoi(short, short, short); // Прототип функции hanoi
printf("\n\nЧисло дисков:"); scanf("%hd", &n);
printf("\nПерестановки\n");
hanoi(1, 2, n );
}// End main
/* Ханойская башня */
void hanoi(short a, // Исходная площадка
short b, // Площадка - цель
short n){ // Число дисков
typedef struct{ // Содержимое элемента стека. В стек не помещается
short a, b, n;
} Cont;
Cont* cont; // Указатель на содержимое. Помещается в стек
bool fl = true; // false – конец вычислений
void* ident; // Идентификатор стека
ident = init( ); // Операция размещения стека
if(ident == NULL){ // Нет памяти под управляющие элементы стека
printf("\n\nНет памяти под стек \"Ханой\"\n\n");
exit(0); // Выход из программы. Это обработка ошибки
}
while(fl){
if(n > 1){ // Помещение в стек
cont=new Cont; // Размещение содержимого
if(cont == NULL){ // Нет памяти под содержимое элемента
printf("\n\nНет памяти под элемент стека \"Ханой\"\n\n");
exit(0);// Тоже обработка ошибки
}
// Заполнение содержимого элемента стека
cont->a = a; cont->b = b; cont->n = n;
//Поместить указатель на элемент в стек
if(push((CTRL*)ident, cont)){
printf("\n\nНет памяти под стек \"Ханой\"\n\n");
exit(0);// Обработка ошибки
}
// Опуститься на 1 уровень
b = 6-a-b; // Подготовка следующего содержимого элемента
n--;
}else{ // Печать переноса диска и извлечение из стека
printf(" %2hd %2hd\n", a, b);
// Получить указатель на элемент "вершины"
cont = (CONT*)top((CTRL*)ident);
if(cont == NULL){ // Стек пуст
fl = 0;
}else{ // Извлечение содержимого и печать переноса диска
a = cont->a; b = cont->b; n = cont->n;
printf(" %2hd %2hd\n", a, b);
// Опуститься на 1 уровень
a = 6-a-b; // Подготовка следующего элемента
n--;
delete cont;// Освободить память "верхнего" элемента
// Извлечь "вершину" стека. Освободить память
if(pop((CTRL*)ident)){ // Ошибка при извлечении
printf("\n\nОшибка при извлечении из стека\"Ханой\"\n\n");
exit(0); // Обработка ошибки
}
}
}
} // End while
finish((CTRL*)ident); // Освободить память из под стека
} // End hanoi
Файлы stek.h и stek.cpp. Операции над стеком.
// stek.h
// Типы данных
struct STEK{ // Стек указателей на элементы
STEK* prev; // Указатель на предыдущий элемент стека
void* cont; // Указатель на содержимое элемента
};
struct CTRL{ // Управляющие переменные
Stek* tek, // Указатель на текущий элемент стека
*prev; // Указатель на предыдущий элемент стека
};
/* Прототипы функций */
void* init( ); // Разместить и инициализировать управляющие
// переменные
bool push(Ctrl* ident, void* cont) // Поместить в стек указатель на
// элемент
void* top(Ctrl* ident); // Прочесть информацию "вершины" стека
bool pop(Ctrl* ident); // Удалить "вершину" стека
void finish(Ctrl* ident); // Очистить стек и освободить память под
// управляющие переменные
// stek.cpp
#include "stek.h"
#include
// Инициализация стека
void* init( ){
Ctrl* ident;
ident = new Ctrl; // Размещение управляющих переменных
if(ident != NULL){ // Проверка выделения памяти
ident->prev = ident->tek = NULL;
}
return ident;
} // End init
// Поместить указатель на элемент в стек
bool push(Ctrl* ident, void* cont){
ident->tek = new Stek; // Выделение памяти под указатель
if(ident->tek == NULL){ // Проверка выделения памяти
returntrue;
}else{ // Включение элемента в список
ident->tek->prev = ident->prev; ident->tek->cont = cont;
ident->prev = ident->tek;
returnfalse;
}
} // End push
// Прочесть "вершину" стека
void* top(Ctrl* ident){
if(ident->tek == NULL){ // Стек пуст. Ошибка!
return NULL;
}else{ // Возврат указателя на содержимое элемента
return ident->tek->cont;
}
} // End top
// Удалить "вершину" стека
bool pop(Ctrl* ident){
if(ident->tek == NULL){ // Стек пуст. Ошибка!
returntrue;
}else{
ident->prev = ident->tek->prev; free(ident->tek);
ident->tek = ident->prev; returnfalse;
}
} // End pop
// Освободить память под стек и управляющие переменные
void finish(Ctrl* ident){
if(ident != NULL){
while(ident->tek != NULL){ //
ident->prev = ident->tek->prev;delete ident->tek;
ident->tek = ident->prev;
}
delete ident;
}
} // End finish
|
Скачать 1.94 Mb.