Типичные ошибки, связанные с указателями

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

Пример.

int *x;

.......

*x = 16; // x не задано значение

Двойное указание

int* x = new int,

* y = new int,

* z = new int;

*x = 14; *y = 15; *z = 16;

printf(" (%d, %d, %d)\n", *x, *y, *z);

/* На экране имеем: (14, 15, 16) */

*z = *x;

printf(" (%d, %d, %d)\n", *x, *y, *z);

/* На экране: (14, 15, 14) */

y = x; //!!! Память, отведенная при объявлении y, становится недоступной

printf(" (%d, %d, %d)\n", *x, *y, *z);

/* На экране: (14, 14, 14) */

*x = -14; *y = -15; *z = -16;

printf(" (%d, %d, %d)\n", *x, *y, *z);

/* На экране: (-15, -15, -16) */

Замечание. Память, отведенная при инициализации указателю y, становится недоступной (" подвисшей" ).

Hе выполнено освобождение выделенной памяти

Забыли выполнить оператор delete (См. использование функции substr).

Задание адреса локальной (auto) переменной

См. пример для функции substr, использование локального массива для строки. После выхода из функции память, отведенная под массив, была бы освобождена и указатель p стал бы ссылаться на " мусор".

Не следует использовать явное задание адреса (pt=( double *)0777000)

При переходе на другую операционную систему программа даст ошибку. Этот критерий качества программы называют немобильностью.

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

Стек

Стек – это совокупность данных, в которой доступен только последний помещенный в нее элемент – вершина стека. Если удалить элемент из вершины, становится доступным предыдущий и т.д.

Состояние	Операция	Содержимое
	Нет	(пусто)
	Поместить в стек	элемент 1
	Поместить в стек	элемент 2 элемент1
	Извлечь из стека	элемент 1
	Извлечь из стека	(пусто)

Пример. Работа со стеком.

typedef < описание_хранимых_данных> TypeEl

// Описание делает фрагмент независи-

//мым от типа обрабатываемых данных

struct Stack{ // Элемент стека – рекурсивная структура

TypeEl zap; // Хранимые данные

struct Stack *p; // Ссылка на предыдущий элемент

}; // Это были описания, вводящие 2 новых типа

/* Определения */

typeEl sod; // Содержание хранимых данных элемента

Stack *TekPtr = NULL, // Текущий элемент – пока никуда не указывает

*PrPtr = NULL; // Предыдущий элемент – также не задан

........................................

// Поместить в стек

TekPtr = new Stack; // Выделяем память под элемент стека

TekPtr -> zap = sod; // Задаем значения элемента

TekPtr -> p = PrPtr; // 1 элемент стека не имеет предыдущего

PrPtr = TekPtr; // Запоминаем адрес элемента стека

........................................

// Извлечь из стека

if (TekPtr == NULL){ // Стек пуст

// Попытка извлечь из " пустого" стека

/* Обработка ошибки */ // Ошибка! Обрабатываем

} else { //Извлекаем данные. Запоминаем адрес предыдущего

// Освобождаем память

sod = TekPtr-> zap; PrPtr = TekPtr -> p; delete TekPtr; TekPtr = PrPtr;

} // В вершине стека предыдущий элемент

Пример. Дан массив {a_i}, i=1...n. Перестроить его в следующем порядке: сначала все a_i< 0 в порядке следования, затем все a_i> =0 в обратном порядке.

typedef float type_el; // Настройка типа

struct Stack{ // Определение типа Stack

type_el zap; // Хранимые данные

struct Stack* p; // Ссылка на предыдущий элемент

};

void perest( short n, type_el* a){

// Параметр - указатель a; аргумент - массив

int i, k;

Stack* tek_ptr, // Указатель на текущий элемент стека

*pr_ptr=NULL; // Указатель на предыдущий элемент. Пока его нет

for (k=i=0; i< n; i++){// 1-й проход по массиву

if (a[ i ]< 0){ // Заполнение a[ i ]< 0

a[k++]=a[ i ];

} else { // a[ i ]> =0 помещаются в стек

tek_ptr= new Stack; // Выделение памяти

// Заполнение

tek_ptr-> zap=a[ i ]; tek_ptr-> p=pr_ptr; pr_ptr=tek_ptr;

}

}

// 2 проход. Извлечение из стека и помещение в массив a

for (i=k; i< n; i++){

a[ i ]=tek_ptr-> zap; pr_ptr=tek_ptr-> p; delete tek_ptr; tek_ptr=pr_ptr;

}

}/* End perest */

Однонаправленный список

элемент 1

элемент k

элемент lll

элемент n

голова списка

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

Пример. Сортировка массива методом вставки в список.

struct Zap{ // Строение элемента списка

struct {...} dan; // Хранимая информация

short key; // Ключ сортировки

struct Zap* p; // Указатель на следующий элемент списка

};

/* Процедура сортировки по невозрастанию*/

Zap* sort(Zap* set, // Указатель на голову списка

short n){ // Число элементов списка

Zap* head, // " Голова" списка

*current, // Текущий элемент

*insert, // Вставляемый элемент

*prev; // Предыдущий элемент

short i, k;

head = set; head-> p = NULL;

for (i = 1; i < n; i++){

current = head; insert = set + i;

// Поиск места вставки

for (k = 0; k < i & & insert-> key > current-> key; k++){

prev = current; current = current-> p;

}

// Вставка

if (k == 0){ // 1-й элемент

head = insert;

} else {

prev-> p=insert;

}

if (k < i){ // Не последний элемент

insert-> p = current;

} else { // Последний элемент

insert-> p = NULL;

}

} // End i

return head;

} // End sort

/* Обработка списка в вызывающей процедуре */

tek = sort(s, n);

for (i = 0; i < n; i++){

....................... // Использование dan((tek-> dan).< имя> )

tek = tek-> p;

}

УКАЗАТЕЛИ и многомерные массивы

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

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 < coniow.h>

#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);

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

Рекурсивные процедуры

В языках 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 – число дисков в башне.

В общем случае для решения задачи требуется 2ⁿ -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

Рекурсивное решение

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 варианта реализации стека: в виде массива и в виде списка.

⇐ Предыдущая10111213141516171819Следующая ⇒

Поделиться: