Struct SStack3 st3;

Стек. Реализация 4.

Однако, можно поступить и по-другому. Т.к. элементы stack и head имеют один тип, то их можно объединить в один массив объектов соответствующего типа (т.е. типа int*). Массив, естественно, должен быть длины 2:

int *st4[2];

Здесь следует заметить, что при определении/описании переменных квадратные скобки имеют приоритет больший, чем *, поэтому переменная st4 имеет тип `массив указателей’, а не `указатель на массив’.

Функция создания стека не более чем из n элементов может выглядеть, в простейшем случае, следующим образом

void StackCreate4(int n, int *st[2]) {st[1]= st[0] = (int*)malloc(n*sizeof(int));}

а ее вызов будет выглядеть так: StackCreate4(n,st4);

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

void StackAdd4(int v, int * st[2]) { (*(st[1]++)) = v;}

а ее вызов будет выглядеть так: StackAdd4 (v, st4);

Проверка стека на пустоту выглядит следующим образом:

int StackIsEmpty4 (int * st[2]) { return st[1]<=st[0]; }

Стек. Реализация 5.

У Реализации 4 есть существенный недостаток. Допустим, что стек создан внутри некоторой функции и требуется использовать его вне данной функции. Тогда у нас есть единственная возможность осуществить данную реализацию, это - сделать переменную st4 глобальной или локальной статической. В противном случае, при выходе из данной функции переменная st4 утратит свое существование и указателями st4[0], st4[1] уже нельзя будет пользоваться. Но, как уже писалось, подобный способ реализации является дурным стилем.

Собственно, вся наша проблема состоит в том, что память под переменную st4 отводится и очищается автоматически. В качестве альтернативы, отведение/очистку памяти под указатели можно взять на себя. Для этого следует использовать указатель на указатель на целую переменную:

int **st5;

Функция создания стека не более чем из n элементов может выглядеть, в простейшем случае, следующим образом

int ** StackCreate5(int n)

{int **st; st = (int**)malloc(2*sizeof(int*)); st[1]= st[0] = (int*)malloc(n*sizeof(int));}

а ее вызов будет выглядеть так: st5=StackCreate5(n);

Теперь переменная st5 может быть локальной и если ее вернуть из функции, то содержимое стека не будет потерянным. Очистку стека можно произвести с помощью следующей функции

void StackDelete5(int **st) { free(st[0]); free(st);}

а ее вызов будет выглядеть так: StackDelete5 (st5);

Лекция 6

Структуры данных (+ в языке С: массивы, структуры, оператор typedef).

  Д.Кнут. Искусство программирования для ЭВМ. тт 1-3. Москва. Мир. 1996-1998 Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы. Построение и анализ. Москва. МЦНМО. 1999.  

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

Стек.

Стеком называется структура данных, организованная по принципу LIFO – last-in, first-out, т.е. элемент, попавшим в множество последним, должен первым его покинуть. При практическом использовании часто налагается ограничение на длину стека, т.е. требуется, чтобы количество элементов не превосходило N для некоторого целого N.

Создание исполнителя стек предполагает наличие следующих функций

Ø инициализация

Ø добавление элемента на вершину стека

Ø взятие/извлечение элемента с вершины стека

Ø проверка: пуст ли стек?

Ø очистка стека

Стек можно реализовать на базе массива или (в языке С) это можно сделать на базе указателей.

---

Дата добавления: 2015-10-30