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

Стек

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

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

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

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

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

Пример.

int *x;

.......

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

int* x = (int*)malloc(sizeof (int)),

y = (int*)malloc(sizeof (int)),

z = (int*)malloc(sizeof (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, становится недоступной ("подвисшей").

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

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

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

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

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

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

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

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

typedef <скалярный_тип> TypeEl; // Описание делает фрагмент независимым

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

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

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

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

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

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

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

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

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

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

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

TekPtr = (Stack*)malloc(sizeof (Stack));// Выделяем память под элемент стека

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

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

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

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

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

if (TekPtr == NULL){ /* Стек пуст */ // Попытка извлечь из "пустого" стека

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

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

sod = TekPtr->zap; PrPtr = TekPtr -> p; free(TekPtr); TekPtr = PrPtr;

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

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

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

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

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

struct stack *p;// Ссылка на предыдущий элемент. Использование метки

} Stack; // структуры. Нельзя ссылаться на определяемый тип

void perest(type_el *a, short n){// Параметр - указатель 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=(Stack*)malloc(sizeo f(Stack));// Выделение памяти

tek_ptr->zap=a[ i ]; tek_ptr->p=pr_ptr; pr_ptr=tek_ptr;// Заполнение

}

}

for (i=k; i<n; i++){ // 2 проход. Извлечение из стека и помещение в массив a

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

}

}/* End perest */

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

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

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

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

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

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

} Zap;

/* Процедура сортировки */

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;

}

Дата добавления: 2014-12-27