Связанные структуры

Структуры, содержащие указатели, позволяют формировать линейные и нелинейные связанные структуры:

ü линейные – стеки, очереди и списки;

ü нелинейные – деревья и сети.

Все линейные структуры имеют много общего:

1) все элементы их представляют собою последовательность элементов, связанных между собой в цепь с помощью указателей;

2) оперативная память для структур выделяется и освобождается с помощью функций Free, Malloc;

3) максимальное количество элементов структур ограничено только объемом доступной оперативной памяти;

4) последовательность элементов имеет начало цепи и конец (вершину).

Различие названий структур связано с разными способами включения и исключения элементов из связанных структур.

Стек – это организация накопления и извлечения данных, в которой элемент, поступивший в стек последним, извлекается первым. LIFO – last in first out (последним вошел, первым вышел). Этот способ данных используется при обработке последовательности активизированных функций и вложенных циклов. Например, цикл, начавший выполняться последним, завершит свою работу первым. Базовые операции над стеком: поместить в стек новый элемент, считать данные из вершины стека, удалить из стека данные (последние).

#include <stdio.h>

#include <alloc.h>

#include <conio.h>

#define Stack struct stack

Stack { int info; Stack *uk;};

Stack *s;

void main(void)

{

Stack *n;

int err,i,k;

clrscr();

printf("\n заполнение стека\n");

for(i=0;i<4;i++)

{

scanf("%d",&k);

n=(Stack*)malloc(sizeof(Stack));

n->info=k;

n->uk=s; s=n;

}

printf("\n чтение и удаление из стека\n");

for(i=0;i<6;i++)

{

if(s)

{printf("%5d",s->info);

Stack *old=s;

s=s->uk;

free(old);}

else

printf("\n end");

}

getch();

}

При включении нового элемента в стек положение указателя на последний элемент стека сдвигается

0

s= n

При размещении нового элемента структуры в стеке:

1) запрашивается память для ее размещения;

2) в ней размещается новая информация;

3) указатель новой структуры получает адрес предыдущего элемента стека;

4) адрес вершины стека получает адрес нового элемента.

Для удаления элемента из стека производятся операции:

1) указатель вершины стека получает адрес предыдущего элемента стека;

2) освобождается оперативная память удаляемого элемента стека.

Очередь.

- это организация накопления и извлечения данных, в которой элемент, поступивший первым, извлекается тоже первым. FIFO – first in – first out. Базовые операции над очередью – поместить элемент в очередь, считать элемент из очереди, удалить элемент из очереди.

#include <stdio.h>

#include <alloc.h>

#include <conio.h>

struct Och { int info; Och *uk;};

Och *s;

void main(void)

{

Och *n,*cur,*pr;

int err,i,k;

clrscr();

printf("\n добавление\n");

for(i=0;i<4;i++)

{cur=s; // cur – адресует первый элемент очереди

pr=0; // pr – указатель на предыдущий элемент очереди

scanf("%d",&k);

n=(Och*)malloc(sizeof(Och));

n->info=k;

n->uk=0; // обнуляем, т.к. это последний элемент очереди

while(cur) // поиск конца очереди для размещения нового элемента

{

pr=cur; cur=cur->uk;} // движение вдоль очереди

if(pr) //pr!=0

pr->uk=n; / /подключение нового элемента

else s=n; // новый элемент - первый в очереди

}

printf("\n чтение и удаление\n");

Och *old;

for(i=0;i<4;i++)

{

if(s)

{printf("%5d",s->info);

old=s;

s=s->uk;

free(old);

}

else

printf("\n end");

}

getch();

}

Схема перемещения указателей вдоль очереди

Дата добавления: 2014-01-06