Новый элемент стал вершиной стека.

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

Если программа должна работать с фиксированным числом экземпляров одного типа структуры, то объявляется массив структур.

Если заранее не известно, сколько будет структур, можно пользоваться связанными структурами, в которых каждая отдельная структура связана с помощью указателей с соседней или с соседними.

Рассмотрим линейные связанные структуры.

1) Все элементы связанных структур представляют собой

последовательность элементов, связанных в цепь посредством

указателей.

2) ОП для элементов выделяется и освобождается динамическая

(new – delete или malloc – free)

1) последовательность элементов имеет вершину и хвост.

К линейным связанным структурам относятся стеки, очереди, списки, и т. д., включение и исключение элементов в которых происходит по-разному:

1) в стеке включение и исключение происходит только с одного конца – с вершины стека;

2) в очереди включение происходит в хвосте цепи (конец очереди), а исключение происходит с вершины цепи (начало очереди);

3) в списке элементы упорядочены по определенному признаку (одному из полей структуры), включение и исключение происходит в любом месте цепи, так чтобы не нарушать порядок списка.

Стек

новый элемент вершина стека хвост стека

data next

data next

data next

data next

data next

…

0

s- указатель на вершину до включения

stnew ->next= s

s = stnew -указатель на вершину после включения

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

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

Рассмотрим функции

1) включения нового элемента

2) исключения элемента

3) считывание данных вершины стека

//Функция дополнения стека:

#include <iostream.h>

#include <conio.h>

struct stack { int data; stack * next; }

stack * beg; // указатель на вершину стека – глобальный

//-------------------------------------------------------------------------------

//Функция дополнения стека:

void dop (stack*&s, int dat) // cссылка на указатель для передачи

// адреса вершины стека и

// данные для нового элемента

/* адрес вершины стека будет меняться в функции дополнения, поэтому указатель на вершину-глобальная переменная будет передаваться в функцию по ссылке, в нее и будут записываться все изменения адреса вершины */

{ stack * stnew; // указатель на новый элемент стека

stnew = new (stack); // выделение памяти под новый элемент

stnew -> data = dat; // размещение информации в новый элемент

stnew->next=s; //“указывает” на бывшую вершину стека

s = stnew; // указатель на вершину –это указатель на новыйэлемент

новый элемент стал вершиной стека.

//---------------------------------------------------------------------------------

//Функция дополнения стека с клавиатуры:

void dop1 (stack*&s)

{ stack * stnew;

stnew = new (stack);

cout<<”\n Введите данные data = “;

cin>>stnew -> data;

stnew->next=s;

s = stnew;

}

//-----------------------------------------------------------------------------

//Функция удаления элемента. Возвращает данное удаляемого эл.:

int ud (stack *&s) //ссылка указатель на вершину

{ stack * fr = s // удаляемый элемент – является вершиной стека

// указатель на него – это указатель на вершину

int k =0;

if (s) { k= fr ->data; //информацию помещаем в переменную k

s = fr -> next; // указателю на вершину присваеваем адрес

// следующего элемента

delete fr; } // освобождаем память

return k; // функция возвращает информацию

}

//-----------------------------------------------------------------------------------

//Функция чтения из вершины стека.

//Т.к. значение указателя на вершину стека не изменяется в функции //чтения, формальным параметром может быть сам указатель на //вершину

int cht (stack *s)

{ if (s) return (s -> data); }

//-----------------------------------------------------------------

// Рекурсивная функция выводит все содержимое стека

int cht1 (stack *s)

{ if (s = = NULL)

{cout<<”\nСтек опустел”; return;}

cout<<”\n data = “ <<s->data;

cht1(s->next);

}

//---------------------------------------------------------------------------

void main ()

{clrscr();

stack*beg1;

for (int i=1; i < =10; i++)

dop (beg, i);

beg1=beg;

for (int i=0; i < 10; i++)

{cout<<cht(beg1); beg1=beg1->next;}

//cht1(beg);

cout<<’\n’<<ud(beg);

cht1(beg);

}

Дата добавления: 2015-07-26