| [Оглавление] | [<< страница] | [>>страница] |
Создание стека. Для стека в векторной памяти необходимо ностроить дескриптор и отвести память под элементы стека исходя из максимально возможного их количества. Это может быть выполнено либо транслятором, либо путем получения динамической памяти в ходе выполнения программы. В любом случае при инициализации дескриптора в него обязательно заносятся указатели начала и конца стека, а в указателе вершины устанавливается признак «пусто».
Для стека списковой структуры создание стека сводится к построению только дескриптора, в нем достаточно наличия только указателя на начало списка, который одновременно является и указателем вершины списка, так как включение и выборка элемента осуществляются с начала списка. Этот указатель устанавливается в NULL, обозначая, что стек пуст.
Включение элемента в стек. В случае стека в векторной памяти, если нет переполнения стека, новый элемент включается в вершину стека, при переполнении отказ oт включения.
В случае стека списковой структуры переполнения, как правило не бывает, по-этому включение сводится к получению динамической памяти под элемент и занесению туда данных. Очевидно, что в указатель в новом элементе заносится значение указателя на начало списка (для первою элемента это NULL), а в указатель начала списка - адрес нового элемента.
Выборка элемента из стека. Она возможна только тогда, когда стек не пускт. Она означает, что выбирается значение из элемента, находящегося в вершине стека, а сам элемент исключается из стека. Исключение для векторного стека сводится к смещению указателя вершины на один элемент к началу стека. При выборке из списка списковой структуры указатель на начальный элемент списка заменяется на указатель из начального элемента, а память освобождается из-под элемента списка.
Извлечение данных из любого элемента стека без удаления самого элемента. В запросе на выполнение этой операции необходимо указать номер элемента от вершины стека или какой-либо другой уникальный признак элемента; по нему отыскивается нужный элемент, если таковой имеется в стеке.
Уничтожение стека. Сводится к освобождению динамической памяти, полученной в процессе создания и обработки стека; если же элементы и дескриптор были построены транслятором, то - к очистке элементов списка и установке признака «пусто» в дескрипторе.
Создадим файл, в котором определены структура дескриптора стека STC и переменная S1 типа STC, а также включены функции, реализующие рассмотренные выше операции над стеками.: Дескриптор построен транслятором, память под элементы стека! получена динамически. Элементы стека имеют значения типа EL, максимальное число элементов m. В дескрипторе определены указатель начала стека в виде адреса начала динамической памяти и указатели вершины и конца стека в виде целых чисел (индексов- элементов стека). Этот файл включается директивой #include в* исходный файл с программой для работы со стеком. Предварительно должен быть определен тип элемента EL. например define double EL. Допускаются типы EL. только такие, что переменным этого типа можно присваивать значения оператором «=». Таковыми являются скалярные типы (int, float, double, char) и структурный тип struct.
Пример.
/* Файл включения для работы со стеком.
c:\bc\xbs\stack\incl stc.c */
#define STC struct st
STC /* дескриптор стека */
{ EL *un; /* Указатель начала стека */
int uk; /* Указатель конца стека */
int uv; /* Указатель вершины стека */
int m. /* число элементов в стеке */
} S1; /* s1 переменная типа STC */
/* ДОБАВЛЕНИЕ ЭЛЕМЕНТА В СТЕК /
int Push_el(STC s,EL el)
{if (s->un == NULL) /* стек не создан */
return -2;
if (s->uv == s->uk)
return -1; /* стек полон */
*(s->un + s->uv+1) = el; ++s->uv;
return 0;
}
/* ВЫБОРКА ЭЛЕМЕНТА ИЗ СТЕКА */
int Pop_el(STC *s,EL *el)
{if (s->un == NULL)
return -2;
/* стек не создан */
if (s->uv < 0)
return -1; /* стек пуст */
else
{ *el = *(s->un + s->uv);
--s->uv;
return 0;
}
}
/*ИЗВЛЕЧЕНИЕ ЗНАЧЕНИЯ ЭЛЕМЕНТА ИЗ СТЕКА БЕЗ УДАЛЕНИЯ ЭЛЕМЕНТА */
int Peek_el(STC *s,EL *el)
{if (s->un == NULL)
return -2; /* стек не создан */
if (s->uv < 0)
return -1; /* стек пуст */
else
{ *el = *(s->un + s->uv);
return 0;
}
}
/* ОСВОБОЖДЕНИЕ СТЕКА */
int Destroy(STC *s)
{ free(s->un);
s->un = NULL;
return 0;
}
/* ЗДАНИЕ СТЕКА */
int Crt stc(STC *s)
{ int n=10; /* число элементов стека можно определить как глобальную переменную */
s->un = (EL*) calloc(n,sizeof(EL));
if (s->un == NULL)
return -1; /* память не выделена */
else
{ s->uv = -1; s->uk = n-1;
s->m =n; return 0;
}
}
/* **** Конец файла включения */
Ниже приведен пример программы на Си для работы со стеком в векторной памяти. Элементом стека является переменная типа struct, хотя в структуре содержится единственный элемент — строка. Это вызвано тем ограничением, о котором говорилось выше. Содержанием элемента стека является команда DOS либо имя исполняемого файла. Обработка элемента стека сводится к выполнению этой команды или исполняемого файла.
Пример 2.2.
/* РАБОТА СО СТЕКОМ В ВЕКТОРНОЙ ПАМЯТИ
\stack\dstackg2.c — головной файл */
#include
#include
#include
#include
#include
typedef struct *Структура элемента стека с именем EL */
{ char Name[80];
} EL;
EL e;
#include"c:\bc\xbs\stack\incl_stc.c" /*файл включения */
char *menu[7][40];
static int p=1;
int ln_el(EL*);
int Show_stc(STC);
void main_menu(void);
/* ===================== ГЛАВНАЯ ФУНКЦИЯ ====== */
int main()
{*menu[0]="1.Создание пустого стека";
*menu[1]="2.Включение элемента в стек";
*menu[2]="3.Выборка элемента из стека";
*menu[3]="4.Освобождение стека";
*menu[4]="5.Вывод содержимого стека на экран";
*menu[5]="6.Конец работы";
*rnenu[6]=" Введите номер строки";
clrscr();
printf(" Работа со стеком в векторной памяти\n” );
while(p)
{ main_menu();
clrscr();
}
printf(" Конец работы со стеком\n");
return 0;
}
/* ВЫВОД ГЛАВНОГО МЕНЮ */
void main_menu(void)
{ char ns; int pp=1,r=0,i;
flushall(); /* чистка буферов */
while (pp)
{for(i=0;i<7;i++)
printf("\n %s",*menu[i]);
printf("\n");
ns=getchar();
if (ns<"1" || ns>'6')
{ clrscr();
рrintf("\nОшибка в номере!! Будьте внимательны.");
continue;
}
else pp=0;
switch(ns)
{ case "1":
if ( Crt_stc(&s1) == -1)
{ printf ("\n Память под стек не выделена");
getch();
} break;
case "2":
if (ln_el(&e) == 0)
{r=Push_el(&s1,e);
if (r == -2)
{ printf("\nCтек не создан!!!"); getch();
}
else
if(r==-1)
{printf("\n Стек полон!!!");
getch();
}
} break;
case "3":
r=Pop_el(&s1,&e);
if(r==-1)
printf("\n Стек пуст");
else
if (r == -2)
printf("\n Стек не создан!!");
else
{ printf("\n Элемент выбран\n");
/* Обработка элемента */
system(e.Name);
}
getch();break;
case "4": Destroy(&s1);break;
case "5":
if (Show_stc(s1) == -1)
{ printf("\n Стек не создан"); getch();
} break;
case "6": p=0;
}
}
}
/*==================================================*/
int ln_el(EL *el)
{ printf("\n Ввод элемента стека или ** для отказа от ввода");
printf("\n Введите команду DOS или имя исполняемого файла\n=>");
flushall();
gets(el->Name);
return 0;
}
/*==================================================*/
int Show_stc(STC s)
{ int i;
if (s.un == NULL)
return -1;
for (i=0; i<=s.uv;i++)
printf("\n %s",s.un[i].Name);
getch();
return 0;
}
| [Оглавление] | [<<страница] | [>>страница] | [В начало ] |