- •Раздел 4. Разработка по Тема 4.1. Проектирование интерфейса с пользователем
- •4.1.1. Типы пользовательских интерфейсов.
- •4.1.2. Пользовательская и программная модели интерфейса.
- •4.1.3. Разработка диалогов.
- •4.1.4. Основные компоненты графических пользовательских интерфейсов.
- •Тема 4.2. Реализация графических пользовательских интерфейсов.
- •4.2.1. Диалоги, управляемые пользователем.
- •4.2.2. Диалоги, управляемые системой.
- •4.2.3. Использование метафор.
- •4.2.4. Технология Drag and Drop.
- •4.2.5. Интеллектуальные элементы.
- •4.3.1. Базовые типы данных.
- •Константы
- •Область действия имен
- •4.3.2. Указатели и адресная арифметика.
- •4.3.3. Составные типы данных. Структуры
- •Битовые поля
- •Определение типов
- •Перечислимые типы
- •4.3.4. Выражения и операции.
- •4.3.5. Управляющие конструкции. Условные операторы
- •Операторы циклов
- •4.4.1. Статические одномерные массивы.
- •4.4.2. Статические многомерные массивы.
- •4.4.3. Динамические массивы.
- •4.4.4. Массивы указателей.
- •4.5.1. Стеки.
- •4.5.2. Очереди.
- •4.5.3. Списки.
- •4.5.4. Бинарные деревья.
- •4.6.1. Объявление классов и экземпляров классов.
- •4.6.2. Инкапсуляция данных и методов.
- •4.6.3. Конструкторы классов.
- •Конструктор по умолчанию
- •Конструктор копирования
- •4.6.4. Деструкторы классов.
- •4.7.1. Разделы в описании класса.
- •4.7.2. Friend-конструкции.
- •4.7.3. Статические члены классов.
- •4.7.4. Использование описателя const в классах.
- •4.8.1. Вложенность классов.
- •4.8.2. Наследование данных и методов.
- •4.8.3. Типы наследования.
- •4.9.1. Полиморфизм раннего связывания.
- •4.9.2. Полиморфизм позднего связывания и виртуальные функции.
- •4.9.3. Абстрактные методы и классы.
- •4.10.1. Функции консольного ввода-вывода.
- •4.10.2. Функции файлового ввода-вывода.
- •4.10.3. Использование библиотеки классов потокового ввода-вывода.
- •4.11.1. Перегрузка операций.
- •4.11.2. Шаблоны функций.
- •4.11.3. Шаблоны классов.
- •4.11.4. Обработка исключений.
- •Тема 4.12. Com-технология.
- •4.12.1. Основные понятия.
- •4.12.2. Типы интерфейсов.
- •Свойства интерфейсов
- •Типы интерфейсов
- •4.12.3. Типы com-объектов.
- •4.12.4. Фабрика классов.
- •Тема 4.13. Построение com-сервера.
- •4.13.1. Язык idl.
- •Содержимое файла idl
- •4.13.2. Определение пользовательского интерфейса.
- •4.13.3. Реализация пользовательского интерфейса.
- •4.13.4. Создание тестового клиента.
- •Тема 4.14. Обзор платформы ms .Net.
- •4.14.1. Общая идея архитектуры .Net.
- •4.14.2. Достоинства и недостатки .Net.
- •4.14.3. Схема трансляции программ в .Net.
- •4.14.4. Язык msil.
- •4.14.5. Объектно-ориентированная модель .Net.
4.5.1. Стеки.
Стеком называется упорядоченный набор элементов, в котором размещение новых элементов и удаление существующих производится только с одного его конца, называемого вершиной стека. Очевидно, что изобразить стек, можно различными способами. При этом обязательно нужно указывать его вершину.
Его еще называют структурой типа LIFO (Last In First Out, первым вошел — последним вышел). Максимальное число элементов, которые можно разместить в стеке, не должно ограничиваться программным окружением: по мере вталкивания в стек новых элементов и выталкивания старых, память под него должна динамически запрашиваться и освобождаться. Состояние стека рассматривается только по отношению к его вершине, а не ко всему содержимому. С этой точки зрения состояния (а) и (б) на рис. 5.2 ничем не отличаются друг от друга.
Операции, выполняемые над стеком, имеют специальные названия. При добавлении элемента в стек мы говорим, что элемент вталкивается в стек (push). Для стека s и элемента sItem определена операция push(s, sItem), по которой в стек s добавляется элемент sItem. Аналогичным образом определяется операция выталкивания из стека— pop(s), по которой из стека s "верхний" элемент удаляется и возвращается в качестве значения функции. Следовательно, операция присваивания
sItem = pop(s);
удалит элемент из стека и присвоит его значение переменной sItem. На применение операции выталкивания из стека существует единственное ограничение: она не может применяться к пустому стеку, т. е. к такому, который не содержит ни одного элемента.
Помимо этих двух основных операций часто бывает необходимо прочитать элемент в вершине стека, не извлекая его оттуда. Для этих целей используют операцию peek(s).
В стек можно помещать элементы любого типа. Никаких ограничений нет.
Наиболее часто используются два подхода к реализации стека: на базе массивов и динамический. Поскольку первый подход менее нагляден и реже используется, остановимся лишь на использовании динамических структур данных.
В листинге приведен интерфейс для программ работы со стеком. Поскольку важны общие принципы, в качестве базового типа его элементов выбран целый.
/* Интерфейс для работы со стеком */]
#define STACK struct stack
STACK
{
int info;
STACK *next;
};
extern void push(STACK **ppStack, int nltem);
extern int pop(STACK **ppStack, int *nError);
extern int peek(STACK **ppStack, int *nError);
Обратите внимание на второе поле структуры — указатель на структуру stack. Такой способ рекурсивного определения, при котором поле структуры содержит ссылку на саму себя, является абсолютно допустимым. Компилятор отводит под указатель next требуемое количество памяти независимо от того, на какой объект он указывает.
Еще один момент, на который следует обратить внимание, заключается в том, что в функциях push и pop используются двойные ссылки. Благодаря этому каждая из них может возвращать в качестве результата своей работы указатель на новый элемент stack (используется передача параметров по адресу). Напомню, что указатель в языке С++ является такой же правомерной переменной, что и, например, короткое целое (short). Поэтому, для того чтобы можно было вернуть значение указателя из функции, необходимо использовать именно двойные ссылки. Входным параметром указанных функций является указатель на стек, с использованием которого вычисляется и возвращается новый адрес элемента, находящегося на вершине. После каждой операции вталкивания и выталкивания указатель, связанный с вершиной, меняется.
На рис. 5.3 показано состояние памяти при работе со стеком.
Функции pop и peek имеют еще один параметр целого типа, передаваемый через указатель, — error. Если в стеке есть хоть один элемент, то функции возвращают error = 0. Если же стек пуст, т. е. не имеет смысла удалять или считывать из него что-либо, error принимает значение 1. Реализация функций работы со стеком представлена в листинге 5.2.
/* Реализация функций работы со стеком */
#include <malloc.h>
#include "stack.h"
void push(STACK **ppStack, int nItem)
{
STACK *pNewItem;
// Запрашиваем память под структуру для элемента стека
pNewItem = (STACK *)malloc(sizeof(STACK));
// Заполняем поля структуры — информационное и
// указателя на следующий элемент
pNewItem->info = nItem;
pNewItem->next = *ppStack;
// Устанавливаем новый указатель на вершину стека
*ppStack = pNewItem;
}
int pop(STACK **ppStack, int *nError)
{
// Запоминаем "старый" адрес вершины стека
STACK *pOldItem = *ppStack;
int nOldInfo = 0;
if(*ppStack)
{
// Если стек не пустой, извлекаем элемент ...
nOldInfo = pOldItem->info;
*ppStack = (*ppStack)->next;
//и освобождаем память
free(pOldItem);
*nError = 0;
} else
// В противном случае ошибка
*nError = 1;
return nOldInfo;
}
int peek(STACK **ppStack, int *nError)
{
if(*ppStack) {
// Если стек не пустой, то читаем информацию об элементе
//не удаляя его из стека
*nError = 0;
return (*ppStack)->info;
}
else
{
//В противном случае ошибка
*nError = 1;
return 0;
} )
Применение стека наглядно иллюстрирует калькулятор с четырьмя основными действиями. Однако пока мы ограничимся более простой программой, оставив калькулятор до знакомства с очередями.
В листинге 5.3 приведена простейшая тестовая программа, иллюстрирующая работу со стеком.
/* Простейшая программа, иллюстрирующая работу со стеком */
#include <stdio.h>
#include "stack.h"
STACK *sl, *s2;
int main()
{
int nError;
// Помещаем в стек число 12
push(&sl, 12);
printf("\npeek(sl) = %d", peek(&sl, &nError)); // проверяем
// Помещаем в стек число 13
push(&sl, 13);
printf("\npeek(si) = %d", peek(&sl, &nError)); // проверяем
// Помещаем в стек число 14
push(&sl, 14);
printf("\npeek(si) = %d", peek(&sl, &nError)); // проверяем
// Помещаем в стек число 15
push(&sl, 15);
printf("\npeek(sl) = %d\n", peek(fisl, snError)); // проверяем
// Извлекаем элементы из одного стека и помещаем в другой
push(&s2, pop(&sl, &nError));
push(&s2, pop(&sl, &nError));
push(&s2, pop(&sl, &nError));
push(&s2, pop(&sl, &nError));
// Распечатываем результаты, одновременно освобождая стек
printf("\npop(s2) = %d", pop(&s2, &nError));
printf("\npop(s2) = %d", pop(&s2, &nError));
printf("\npop(s2) = %d", pop(&s2, &nError));
printf("\npop(s2) = %d\n", pop(&s2, &SnError));
getchar();
return 1;
}