Лекции. Основные понятия и определения
 Скачать 1.94 Mb.
|
15.5. Типичные ошибки, связанные с указателямиОтсутствие инициализации указателяПример. 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)При переходе на другую операционную систему программа даст ошибку. Этот критерий качества программы называют немобильностью. 15.6. Примеры использования указателей. Структуры данных15.6.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 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 a[ i ]=tek_ptr->zap; pr_ptr=tek_ptr->p; delete tek_ptr; tek_ptr=pr_ptr; } }/* End perest */ 15.6.2. Однонаправленный списокЭта структура позволяет установить связи между составляющими ее элементами и осуществлять переходы от одного элемента к другому в соответствии с некоторым порядком. Элементы представляют собой структуры и могут образовывать массив либо располагаться в "куче". Например, с помощью списка можно выполнить сортировку элементов по значению одного из элементов структуры, не перемещая данные в памяти. Однако при этом требуется дополнительная память для размещения указателя на последующий (или предыдущий) элемент списка. Схематически список можно изобразить следующим способом.  Пример. Сортировка массива методом вставки в список. 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; } |