Дипломная работа: Разработка программ с использованием динамической памяти

[99]

Рисунок 2.2. – Последовательное хранение линейного списка

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

Описание структуры и указателя в этом случае может имееть вид:

typedef struct snd /* структура элемента хранения */

{ float val; /* элемент списка */

struct snd *n; /* указатель на элемент хранения */

} DL;

DL *p; /* указатель текущего элемента */

DL *dl; /* указатель на начало списка */

Для выделения памяти под элементы хранения необходимо пользоваться функцией malloc(sizeof(DL)) или calloc(l,sizeof(DL)). Формирование списка в связанном хранении может осуществляется операторами:

p=malloc(sizeof(DL));

p->val=10; p->n=NULL;

dl=malloc(sizeof(DL));

dl->val=7; dl->n=p;

В последнем элементе хранения (конец списка) указатель на соседний элемент имеет значение NULL. Получаемый список изображен на рисунке 2.3.

Рисунок 2.3. – Связное хранение линейного списка

2.2. Операции над элементами списка

При простом связанном хранении каждый элемент списка представляет собой структуру graf, состоящую из двух элементов: v - предназначен для хранения элемента списка, next - для указателя на структуру, содержащую следующий элемент списка. На первый элемент списка указывает указатель head. Для всех операций над списком используется описание:

typedef struct graf

{ int v;

struct graf* next;

} Graf;

Graf *g, *head, *teil;

Для реализации операций могут использоваться следующие фрагменты программ:

1) определить первый элемент в линейном списке (рисунок 2.4):

printf("v=");

scanf("%d",&head->v);

head->next=0;