- •Раздел 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.3. Списки.
Рассмотренные структуры — стек и очередь, являются специальными разновидностями более общей структуры данных — обобщенного связанного списка. Существует множество способов его реализации. Рассмотрим линейные (однонаправленные) списки. Интерфейс для программ работы с такими списками приведен в листинге 5.7.
/* Интерфейс для работы со списком */.
itdefine LIST struct list
LIST
{
char aLastName[16];
char aFirstName[16];
char aTelephoneNumber[16];
LIST *pNext;
};
extern void insert(LIST **ppList, LIST *pItem);
extern void destroy(LIST **pList);
extern void display(LIST *pList);
extern int remove(LIST **ppList, LIST *pItem) ;
Чтобы сделать пример работы со списком более реалистичным и продемонстрировать особенности работы со структурами, предположим, что каждый элемент списка (рис. 5.8) представляет собой символьную строку. В принципе, возможности здесь безграничны, и вместо строки можно использовать любые достаточно сложные структуры и объединения.
Приведенные ниже функции из листинга 5.7 позволяют работать со списком:
insert — добавить новый элемент в список, сохраняя установленный порядок следования.
destroy — разрушить список.
display — вывести все элементы списка.
remove — удалить элемент списка.
Реализация этих функций представлена в листинге 5.8.
/* Реализация функций работы со списком */
#include <string.h>
#include <malloc.h>
#include <stdio.h>
#include "list.h"
// Статическая функция создания элемента списка
static LIST* create(LIST *pItem)
{
LIST *pNewItem = (LIST *)malloc(sizeof(LIST));
*pNewItem = *pItem;
return pNewItem; }
void insert(LIST **ppList, LIST *pItem)
{ char aKey[16];
LIST *pNewItem;
LIST *pCurItem = *ppList;
LIST *pPreItem = 0;
// В качестве ключевого поля в списке используется фамилия.
strcpy(aKey, pItem->aLastName);
// Ищем элемент, совпадаю!ций с ключевым
while(pCurItem != 0 &&
strcmp(pCurItem->aLastName, aKey) < 0)
{
pPreItem = pCurItem;
pCurItem = pCurItem->pNext;
}
// Здесь pCurItem либо 0, либо равен указателю на найденный элемент
// Создаем новый элемент и заполняем его поля
pNewItem = create(pItem);
pNewItem->pNext = pCurItem;
// Вставляем новый элемент в список
if (pPreltem = = 0) // либо в начало,
*ppList = pNewItem;
else // либо после ключевого pPreItem->pNext = pNewItem;
}
int remove(LIST **ppList, LIST *pItem)
{
LIST *pCur!tem = *ppList;
LIST *pPreItem = 0;
// Ищем заданный элемент
while(pCurItem != 0 &&
strcmp(pCurItem->aLastName, pItem->aLastName) != 0)
{
pPreItem = pCurItem;
pCurItem = pCurItem->pNext;
}
// Если такого элемента нет, то и удалять нечего
if (pCurItem != 0)
return 0;
if (pPreItem ==0)
// Удаляем первый элемент списка
*ppList = pCurItem->pNext;
else
// Удаляем элемент списка, начиная со второго
pPreItem->pNext = pCurItem->pNext;
free(pCurltem); // обязательно освобождаем память
return 1;
}
void destroy(LIST **ppList)
{
LIST *pCurItem = *ppList;
LIST *pPreItem = 0;
// Проходим весь список
while(pCurItem != 0)
{
pPreItem = pCurItem;
pCurItem = pCurItem->pNext;
// и удаляем каждый текущий элемент
free(pPreltem) ;
}
// Нулевой указатель на начало списка говорит, что список пустой
*ppList = 0;
}
void display(LIST *pList)
{
LIST *pCurItem = pList;
// Последовательно проходим весь список
while(pCurltem)
{
// и выводим информацию о каждом элементе
printf("\n%s, %s", pCurItem->aLastName, pCurItem->aFirstName);
printf(" \t%s", pCurItem->aTelephoneNumber);
pCur-Item = pCurltem->pNext;
}
printf("\n\n"); }
В листинге 5.8 имеется статическая функция create, которая предназначена для того, чтобы отводить память под новый элемент списка и передавать данные, помещенные по адресу pItem (указатель на структуру), в новый элемент. В функции используется множественное присваивание:
*pNewItem = *pItem;
для пересылки всей информации, расположенной по адресу pItem, в область памяти по адресу pNewItem.
Она введена исключительно для демонстрации работы со статическими функциями: ее можно вызвать только из перечисленных выше функций работы со списком; непосредственный вызов из другого модуля запрещен. Это один из приемов ограничения доступа — новый элемент списка можно создавать только при помощи интерфейсных функций.
Остановимся также на некоторых аспектах функций insert и remove, поскольку реализация функций display и destroy достаточно тривиальна и уже, в том или ином виде, рассматривалась.
Работа функции insert проиллюстрирована на рис. 5.9.
Таким образом, чтобы вставить элемент в список, необходимо сначала найти элемент со значением ключевого поля, совпадающим с заданным. Это осуществляется путем прохода по списку.
После этого вставляем новый элемент (не имеет значения, когда он был создан, до поиска или после). Обратите внимание, что новый элемент вставляется в список после ключевого. Поэтому имеет значение только, пустой это список или нет, для всех остальных случаев вставка осуществляется одинаково.
В некоторых случаях может возникнуть, задача вставки элемента перед ключевым. Решите ее самостоятельно в качестве упражнения — принцип при этом не изменяется.
Операция удаления элемента из списка также довольно проста (рис. 5.10).
Прежде всего необходимо организовать проход по списку, чтобы найти нужный элемент. Если такого элемента нет, то, ничего не удаляя, просто выходим из функции:
Если же такой элемент есть, то либо устанавливаем новое значение указателя на список (если это первый элемент), либо полю next предыдущего элемента присваиваем значение адреса следующего элемента. В обоих случаях не забываем освободить занимаемую элементом память:
Помимо рассмотренного линейного списка существуют и другие:
Циклический список — поле next последнего элемента содержит указатель назад на первый элемент (рис. 5.12). Такой список не имеет первого и последнего элементов. Однако в некоторых случаях удобно использовать внешний указатель на последний элемент, что автоматически делает первым следующий за ним элемент. Альтернативный вариант предполагает использование указателя на первый элемент.
Двунаправленные списки — каждый элемент такого списка содержит два указателя: один указывает на предшествующий элемент, а другой — на последующий. Такие списки могут быть линейными и циклическими (рис. 5.13).
Мультисписки — структура данных, состоящая из элементов, которые могут принадлежать нескольким спискам, не повторяясь в нескольких элементах дня каждого списка. Такие элементы имеют указатели на каждый список, которому они принадлежат (рис. 5.14). Списки в мультисписке могут быть линейными и циклическими, однонаправленными и двунаправленными.