Диспетчеризация действий на основе компонентов ActionManager, ActionMainMenuBar, ActionToolBar

    Диспетчер действий ActionManager не только создает и хранит набор действий, как и ActionList, но и управляет полосами действий – визуальными компонентами, на которых располагаются элементы пользовательского интерфейса. К таким компонентам относятся ActionMainMenuBar – полоса главного меню и ActionToolBar – инструментальная панель. Во время проектирования эти компоненты могут вводиться в приложение непосредственно из палитры компонентов, или создаваться простым перетаскиванием на них необходимых действий из окна Редактора Действий ActionManager. Компонент ActionManager запоминает информацию о составе набора действий и конфигурации полос действий в текстовом или двоичном файле на диске.

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

    Загрузим в компонент ImageList1 пиктограммы из файлов fldropen, filesave, floppy, insert, show, delete, arrow1u, erase, dooropen. В компоненте ActionManager1 установим свойство Images равным ImageList1, связав тем самым диспетчер действий со списком изображений.

     Свойство State определяет реакцию на действия пользователя. Значение asNormal соответствует нормальной рабочей реакции: при щелчке пользователя на доступных интерфейсных компонентах действий выполняются соответствующие действия.

    Свойство FileName задает имя файла, в котором ActionManager хранит информацию о составе связанных с ним полос действий. В начале выполнения приложения ActionManager читает информацию из этого файла и в соответствии с ней формирует полосы действий. А при любых изменениях настройки в процессе выполнения ActionManager записывает в этот файл проведенные изменения. Так что при следующем сеансе работы состав полос действий будет таким, каким сделал его пользователь в предыдущем сеансе.

    Примечание. При изменении полос действий в процессе проектирования нужно задавать значение FileName по окончании проектирования, так как в противном случае в файле будет сохранено состояние полос действий предыдущего сеанса. Если же потребовалось изменить полосы действий после того, как было задано значение FileName, то нужно предварительно удалить с диска файл, в котором запоминается состояние. В этом случае при очередном выполнении приложения этот файл создастся заново.

    Если в процессе проектирования впервые задается значение FileName, надо просто записать в этом свойстве имя файла с путем к нему. При отсутствии пути файл будет создан в том каталоге, в котором расположен проект. Если же нужно задать в качестве значения FileName имя уже существующего файла, то можно воспользоваться для его выбора кнопкой с многоточием около свойства FileName в окне Инспектора Объектов.

    Перейдем к рассмотрению и использованию основного инструмента проектирования – Редактора Действий компонента ActionManager1. Двойным щелчком на компоненте вызывается окно Редактора Действий (Редактирование Form1->ActionManager1) на странице Действия с пустыми панелями Категории: и Действия:. Щелкнем правой кнопкой мыши и в появившемся контекстном меню выберем команду Новое действие. Повторим команду Новое действие еще два раза. После этого в панели Действия: появятся имена Action1, Action2, Action3 объектов этих действий, а в панели Категории: – их категории. Выделим Action1. В Инспекторе Объектов будут видны свойства, которые можно изменить: Caption, Hint, ShortCut и другие. Строка свойства Hint отображается в окне Редактора Действий в панели Описание. Можно изменить также категории действий – их свойства Category. Если в компоненте ActionList понятия категорий лишены определенного смысла, то здесь – при создании меню названия категорий станут надписями головных разделов меню.

    Зададим свойства объектов действий. Для Action1: Caption – Сохранить, Category - Файл, Hint – сохранить список в файле, Name  - FileSave1, ShortCat - F2. Для Action2: Caption – Сохранить как, Category - Файл, Hint – сохранить список в файле как…, Name  - FileSaveAs1, ShortCat – Ctrl+K. Для Action3: Caption – Открыть, Category - Файл, Hint – вывести список из файла, Name  - FileOpen1, ShortCat - Ctrl+O. В свойство ImageIndex заносим соответствующие значения.

В дальнейшем действия будут связаны с соответствующими компонентами, например, разделами меню. Щелчок пользователя на разделе будущего меню инициализирует соответствующее действие, что вызывает событие OnExecute. Для перехода в обработчик этого события действия Сохранить сделайте на нем двойной щелчок. Занесите в обработчик соответствующий код (см. файл реализации модуля LR_7). Подобным же образом заполните обработчики для действий Сохранить как и Открыть. Затем для всех действий задайте свойство Enabled = true.

    Описанным выше образом командой Новое действие создайте действия Action1, Action2, Action3, Action4, Action5, Action6. Для всех этих действий в свойство Category внесите Действия. Задайте остальные свойства новых объектов действий. Для Action1: Caption – Добавить элемент, Hint –  добавить элемент в список, Name  - Add, ShortCat - Ctrl+A. Для Action2: Caption – Вывести список, Hint – вывести  список в таблицу, Name  - Out, ShortCat – Ctrl+T. Для Action3: Caption – Удалить элемент, Hint – удалить элемент из списка, Name  - Del, ShortCat - Ctrl+B. Для Action4: Caption – Удалить подсписок, Hint – удалить подсписок из списка, Name - Clear_down, ShortCat - Ctrl+C. Для Action5: Caption – Уничтожить список, Hint – уничтожить список, Name  - Clear, ShortCat – Ctrl+D. Для Action6: Caption – Выход, Hint – Выход/Завершение работы, Name  - A_exit, ShortCat - Ctrl+E. В свойство ImageIndex заносите соответствующие значения.

    В обработчики события OnExecute этих шести действий внесите коды из файла реализации модуля LR_7. Убедитесь, что для всех шести действий свойство Enabled = true.

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

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

    Перейдите на страницу Панели окна Редактора Действий. Кнопкой Новый…добавьте на форму первую инструментальную панель ActionToolBar1. (Отметим, что компонент ActionToolBar можно также добавлять на форму переносом из палитры компонентов.) По умолчанию панель расположится вверху, на всю ширину формы. Задайте её свойство Align = alNone, чтобы придать ей нужные размеры и расположить в нужном месте. Здесь и в дальнейшем может оказаться полезным задание свойству Orientation  значения boTopToBottom или boBottomToTop. Полезно также воспользоваться свойством Constraints. В свойство Hint занесите инструментальная панель 1, в ShowHint – true.

     Перейдите на страницу Действия окна Редактора Действий. Перетащите из Редактора Действий на панель категорию Файл. При этом все действия категории перенесутся на панель. Действия также можно перетаскивать на панель поодиночке и там изменять порядок их следования.

    Описанным выше образом добавьте на форму вторую инструментальную панель ActionToolBar2, задайте в ней свойства и перетащите на неё категорию Действия.    

    Выделите одну из полос действий на странице Панели окна Редактора Действий и просмотрите в Инспекторе Объектов ее свойства. В свойствах Caption (надпись) измените значения полос действий соответственно на Главное меню, Инструментальная панель 1, Инструментальная панель 2.

    Выделите компонент ActionManager1 и задайте значение свойства FileName в окне Инспектора Объектов, т.е. имя файла, в котором ActionManager1 хранит информацию о составе связанных с ним полос действий.

    Выделите кнопку Добавить элемент и в её свойство Action занесите Add, чтобы связать кнопку с одноименным действием.

    Дополните файл реализации модуля LR_7 обработчиками событий: создания формы, где размещается код для создания заголовка таблицы, и щелчков на компонентах RadioButton1 и RadioButton2, в которых реализуется подготовка компонентов для ввода данных элементов списка.

    Удаление элемента и подсписка из списка осуществляется по ячейке, выделенной в таблице вывода списка. При этом используется событие OnSelectCell компонента StringGrid1. В обработчик этого события передаются целые параметры ACol и ARow – столбец и строка выделенной ячейки и булев параметр CanSelect – допустимость выбора.

int r; //переменная для номера строки выделенной ячейки в таблице

bool flag=true; //флаг - нет выделенной ячейки в таблице

void __fastcall TForm1::StringGrid1SelectCell(TObject *Sender, int ACol,

int ARow, bool &CanSelect)

{

r=ARow; //номер строки выделенной ячейки сохранен в переменной r

flag=false; //ячейка в таблице выделена

}

Для удаления элемента и подсписка из списка используется параметр ARow– номер строки выделенной ячейки.

    На этом проектирование приложения завершается.

Рис.7.4 – меню

Тестирование и использование приложения

1.Запустите приложение на выполнение, нажав быстрые кнопки Сохранить все и Запуск.

2.Выполните тестирование по рис.7.5. Рекомендуется добавлять и удалять элементы с включенным индикатором. Команда Вывести список необходима при отладке и тестировании приложения.

3.Составьте и выполните тесты, которые проверят правильность всех случаев добавления и удаления элементов подсписков (см. комментарии в файлах f_7.cpp и LR_7.cpp).

4.Убедитесь в правильности сохранения списка в файле.

5.Модифицируйте код, переместив данные-элементы классов TRollи TBikeв закрытые части классов. Выполните отладку. Результаты продемонстрируйте преподавателю.

Рис.7.5 – форма с результатами тестирования

Файл реализации LR_7.cpp модуля LR_7

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

#include <vcl.h>

#pragma hdrstop

#include "LR_7.h"

#include "f_7.h"

#include<string.h>

#include<fstream.h>

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

#pragma package(smart_init)

#pragma link "CSPIN"

#pragma resource "*.dfm"

TForm1 *Form1;

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

__fastcall TForm1::TForm1(TComponent* Owner)

   : TForm(Owner)

{

}

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

//при создании формы создаем заголовок таблицы

void __fastcall TForm1::FormCreate(TObject *Sender)

{

StringGrid1->FixedRows=1;

StringGrid1->RowCount=1;

StringGrid1->FixedCols=0;

StringGrid1->ColCount=8;

StringGrid1->Cells[0][0]="номер";

StringGrid1->Cells[1][0]="изделие";

StringGrid1->Cells[2][0]="кол-во(шт) в п/сп";

StringGrid1->Cells[3][0]="дата поступления";

StringGrid1->Cells[4][0]="производитель";

StringGrid1->Cells[5][0]="диам колес(мм)";

StringGrid1->Cells[6][0]="вес(кг)";

StringGrid1->Cells[7][0]="кол-во скоростей";

}

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

//активация компонентов для ввода данных элемента списка - велосипед

void __fastcall TForm1::RadioButton1Click(TObject *Sender)

{

GroupBox1->Caption="Велосипед";

DateTimePicker1->SetFocus();

LabeledEdit3->Enabled=true;

CSpinEdit1->Enabled=true;

Label2->Enabled=true;

}

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

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

//  списка - ролик. коньки

void __fastcall TForm1::RadioButton2Click(TObject *Sender)

{

GroupBox1->Caption="Ролик. коньки";

DateTimePicker1->SetFocus();

LabeledEdit3->Enabled=false;

CSpinEdit1->Enabled=false;

Label2->Enabled=false;

}

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

list spisok;//создаем объект класса - список

void __fastcall TForm1::AddExecute(TObject *Sender)

{

 if(RadioButton1->Checked)

{ //создаем элемент списка - велосипед

TBike *bike=new TBike;

strcpy(bike->date,(DateToStr(DateTimePicker1->Date)).c_str());

if(LabeledEdit1->Text=="")

{

   MessageBox(NULL,"Введите название производителя!","Ошибка", 0);

   LabeledEdit1->SetFocus();

   return;

}

strcpy(bike->comp,(LabeledEdit1->Text).c_str());

   if(LabeledEdit2->Text==""||!isdigit(LabeledEdit2->Text[1]))

{

   MessageBox(NULL,"Введите диаметр колес!","Ошибка",0);

   LabeledEdit2->SetFocus();

   return;

}

bike->diam=StrToInt(LabeledEdit2->Text);

if(LabeledEdit3->Text==""||!isdigit(LabeledEdit3->Text[1]))

{

   MessageBox(NULL,"Введите вес!","Ошибка",0);

   LabeledEdit3->SetFocus();

   return;

}

bike->weight=StrToFloat(LabeledEdit3->Text);

bike->speeds=CSpinEdit1->Value;

//созданный элемент добавляем в список

spisok.append_bike(bike);

}

 if(RadioButton2->Checked)

{ //создаем элемент списка - роликовые коньки

TRoll *roll=new TRoll;

strcpy(roll->date,(DateToStr(DateTimePicker1->Date)).c_str());

if(LabeledEdit1->Text=="")

{

   MessageBox(NULL,"Введите название производителя!","Ошибка",0);

   LabeledEdit1->SetFocus();

   return;

}

strcpy(roll->comp,(LabeledEdit1->Text).c_str());

if(LabeledEdit2->Text==""||!isdigit(LabeledEdit2->Text[1]))

{

   MessageBox(NULL,"Введите диаметр колес!","Ошибка",0);

   LabeledEdit2->SetFocus();

   return;

}

roll->diam=StrToInt(LabeledEdit2->Text);

//созданный элемент добавляем в список

spisok.append_roll(roll);

}

MessageBox(NULL,"Элемент добавлен!","",0);

//если индикатор включен - список выводится в таблицу

if(CheckBox1->Checked)spisok.out_list();

//вывод информации о списке

Form1->StatusBar1->SimpleText="Количество подсписков - "+

IntToStr(spisok.count_dsp)+" "+"Количество элементов в списке - "+

IntToStr(spisok.count_elem_sp);

}

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

void __fastcall TForm1::A_exitExecute(TObject *Sender)

{

 Close();

}

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

//вывод списка в таблицу

void __fastcall TForm1::OutExecute(TObject *Sender)

{

spisok.out_list();

}

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

int r; //переменная для номера строки выделенной ячейки в таблице

bool flag=true; //флаг - нет выделенной ячейки в таблице

void __fastcall TForm1::StringGrid1SelectCell(TObject *Sender, int ACol,

int ARow, bool &CanSelect)

{

r=ARow; //номер строки выделенной ячейки сохранен в переменной r

flag=false; //ячейка в таблице выделена

}

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

//удаляем из списка элемент, соответствующий номеру

//строки выделенной в таблице ячейки

void __fastcall TForm1::DelExecute(TObject *Sender)

{

if(spisok.is_empty)//если список пуст

{

  MessageBox(NULL,"Список пуст!","",0);

   return;

}

if(flag) //если ячейка в таблице не выделена

{

   MessageBox(NULL,"Выделите элемент в таблице!","Ошибка",0);

   return;

}

//удаляем из списка элемент, соответствующий значению переменной r

spisok.del(r);

//если индикатор включен - список выводится в таблицу

if(CheckBox1->Checked)spisok.out_list();

flag=true;//можно снова выделять ячейку в таблице

}

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

//удаляем из списка подсписок, соответствующий номеру

// строки выделенной в таблице ячейки

void __fastcall TForm1::Clear_downExecute(TObject *Sender)

{

if(spisok.is_empty) //если список пуст

{

  MessageBox(NULL,"Список пуст!","",0);

   return;

}

if(flag) //если ячейка в таблице не выделена

{

   MessageBox(NULL,"Выделите элемент в таблице!","Ошибка",0);

   return;

}

//удаляем из списка подсписок, соответствующий значению переменной r

spisok.clear_down(r);

//если индикатор включен - список выводится в таблицу

if(CheckBox1->Checked)spisok.out_list();

flag=true; //можно снова выделять ячейку в таблице

}

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

//уничтожаем список

void __fastcall TForm1::ClearExecute(TObject *Sender)

{

if(spisok.is_empty) //если список пуст

{

  MessageBox(NULL,"Список пуст!","",0);

   return;

}

//для объекта - список вызывается функция уничтожения списка

spisok.clear();

//уничтожение списка контролируется выводом в таблицу

spisok.out_list();

}

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

AnsiString fn=""; //строка для имени файла

//вспомогательная строка для вывода списка из таблицы в файл

char str[50];

int s;//вспомогательная переменная для вывода в файл

  //количества элементов в списке

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

//сохраняем список в файле

void __fastcall TForm1::FileSave1Execute(TObject *Sender)

{

if(fn!="") //если есть имя файла со списком

{

ofstream outfile(fn.c_str(),ios::out);//открываем файл для записи

//в переменную s заносим количество элементов в списке

s=spisok.count_elem_sp;

//выводим в файл число из переменной s побайтно

outfile.write((char*)&s,sizeof(s));

//из таблицы список выводим в файл

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

   {

    for(int j=0;j<8;j++)

     { //преобразовав элемент из таблицы к типу char*,

       //копируем его в вспомогательную строку str

       strcpy(str,Form1->StringGrid1->Cells[j][i].c_str());

       //выводим побайтно содержимое str в файл

       outfile.write((char*)&str,50);

     }

   }

outfile.close();//закрываем файл

}

else //если файл со списком отсутствует

   //открывается диалог сохранения в файле и пользователь

   //выбирает имя файла

   if(SaveDialog1->Execute())

   { //выбранное имя файла сохраняется в строке fn

     fn=SaveDialog1->FileName;

     //создается и открывается для записи файл с выбранным именем

     ofstream outfile(fn.c_str(),ios::out);

     //в переменную s заносим количество элементов в списке

     s=spisok.count_elem_sp;

     //выводим в файл число из переменной s побайтно

     outfile.write((char*)&s,sizeof(s));

     //из таблицы список выводим в файл

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

      {

       for(int j=0;j<8;j++)

        { //преобразовав элемент таблицы к типу char*,

          //копируем его во вспомогательную строку str

          strcpy(str,Form1->StringGrid1->Cells[j][i].c_str());

          //выводим побайтно содержимое str в файл

          outfile.write((char*)&str,50);

        }

      }

    outfile.close();//закрываем файл

   }

}

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

//выводим список из файла в таблицу

//по данным таблицы формируем список в оперативной памяти

void __fastcall TForm1::FileOpen1Execute(TObject *Sender)

{

 spisok.clear();//уничтожаем список в оперативной памяти

 //открываем файл на чтение с выбранным при сохранении именем

 ifstream infile(fn.c_str(),ios::in);

 if(!infile) //проверка, удалось ли открыть файл

{

MessageBox(NULL,"Файл не удается открыть!","Ошибка",0);

return;

}  

 //в переменную s читаем из файла количество элементов в списке

 infile.read((char*)&s,sizeof(s));

 //читаем файл в таблицу

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

{

Form1->StringGrid1->RowCount++;//добавляем строку в таблице

for(int j=0;j<8;j++)

  { //читаем в строку str из файла очередную запись в 50 байт

    infile.read((char*)&str,50);

//из строки str переносим запись в элемент таблицы

    Form1->StringGrid1->Cells[j][i]=(AnsiString)str;

  }

}

 infile.close();//закрываем файл, открытый на чтение

 //из данных строк таблицы формируем элементы списка

 //элементы списка добавляем в список

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

{

if(StringGrid1->Cells[1][i]=="Bike")

{ //формируем элемент списка - велосипед

   TBike* bike=new TBike;

   strcpy(bike->date,StringGrid1->Cells[3][i].c_str());

   strcpy(bike->comp,StringGrid1->Cells[4][i].c_str());

   bike->diam=StrToInt(StringGrid1->Cells[5][i]);

   bike->weight=StrToFloat(StringGrid1->Cells[6][i]);

   bike->speeds=StrToInt(StringGrid1->Cells[7][i]);

   spisok.append_bike(bike);//добавляем в список

}

  if(StringGrid1->Cells[1][i]=="Roll")

{ //формируем элемент списка - роликовые коньки

   TRoll* roll=new TRoll;

   strcpy(roll->date,StringGrid1->Cells[3][i].c_str());

   strcpy(roll->comp,StringGrid1->Cells[4][i].c_str());

   roll->diam=StrToInt(StringGrid1->Cells[5][i]);

   spisok.append_roll(roll);//добавляем в список

}

}

 spisok.out_list(); //выводим прочитанный список в таблицу

 //вывод информации о прочитанном списке

 StatusBar1->SimpleText="Количество подсписков - "+

IntToStr(spisok.count_dsp)+" "+

    "Количество элементов в списке - "+

       IntToStr(spisok.count_elem_sp);

}

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

//сохраняем как...

void __fastcall TForm1::FileSaveAs1Execute(TObject *Sender)

{

//выбранное ранее имя файла заносится в свойство FileName

//компонента SaveDialog1 и предлагается пользователю по умолчанию

  SaveDialog1->FileName=fn;

//если при открытии диалога пользователь выбрал новое имя

if(SaveDialog1->Execute())

{ //то новое имя файла сохраняется в строке fn

fn=SaveDialog1->FileName;

//создается и открывается для записи файл с новым именем

ofstream outfile(fn.c_str(),ios::out);

if(!outfile) //проверка, удалось ли создать и открыть файл

  {

   MessageBox(NULL,"Файл не удается создать!","Ошибка",0);

   return;

  }

//в переменную s заносим количество элементов в списке

s=spisok.count_elem_sp;

//выводим в файл число из переменной s побайтно

outfile.write((char*)&s,sizeof(s));

//из таблицы список выводим в файл

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

  {

    for(int j=0;j<8;j++)

     { //преобразовав элемент таблицы к типу char*,

       //копируем его в вспомогательную строку str

       strcpy(str,Form1->StringGrid1->Cells[j][i].c_str());

       //выводим побайтно содержимое str в файл

       outfile.write((char*)&str,50);

     }

  }

outfile.close(); //закрываем файл

}

}

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

Контрольные вопросы

1.Расскажите о назначении базового класса.

2.Объясните содержание класса link, TBike, TRoll, list.

3.Как выполняется конструктор класса link, TBike, TRoll, list?

4.Как выполняется деструктор класса link, TBike, TRoll, list?

5.Укажите в коде точки, где вызывается конструктор класса link, TBike, TRoll, list.

6.Укажите в коде точки, где вызывается деструктор класса link, TBike, TRoll, list.

7.Как нужно изменить остальное содержание класса link, TBike, TRoll, list, если данные-элементы класса из открытой части класса перенести в закрытую часть класса?

8.Объясните, как в список заносится первый элемент.

9.Объясните, как в список добавляется второй и последующие элементы с разными типами, отличающимися от типа первого элемента.

10.Объясните, как добавляется элемент в подсписок.

11.Как добавляется в список новый подсписок?

12.Когда и как переназначаются указатели на начало и конец списка?

13.Как удалить элемент из первого подсписка (элемент – единственный в подсписке, первый в подсписке, последний в подсписке, находится внутри подсписка)?

14.Как удалить элемент из последнего подсписка (элемент – единственный в подсписке, первый в подсписке, последний в подсписке, находится внутри подсписка)?

15.Как удалить элемент из внутреннего подсписка (элемент – единственный в подсписке, первый в подсписке, последний в подсписке, находится внутри подсписка)?

16.Как удалить подсписок (первый, последний, внутренний, из одного элемента, из нескольких элементов)?

17.Как уничтожить список?

18.Как вывести список из ОП в таблицу?

19.Расскажите, как список сохранить в файле.

20.Как вывести список из файла в таблицу?

21.Как ввести список в ОП из таблицы? из файла, минуя таблицу?

22.Как по выделенной в таблице ячейке определить положение удаляемого элемента?  подсписка?

23.Расскажите о назначении и возможностях диспетчера действий ActionManager. Что относится к полосам дествий ActionManager?

24.Расскажите об использовании Редактора Действий ActionManager.

25.Как создать меню, инструментальную панель с помощью ActionManager?

26.Как связать меню, инструментальную панель с ImageList?

27.Как сохранить настройки полос действий ActionManager?

Задания

1.Используя двунаправленный список, написать и протестировать функции, реализующие отдельные действия при игре в “новое домино”, в котором кроме традиционных правил игрок может на каждом ходу заменить любую конечную кость на свою. Необходимы следующие функции: а)проверить, можно ли сделать ход; б)сделать ход; в)проверить, можно ли сделать замену, г)заменить кость; д)определить, закончена ли игра.

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

3.Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении поездов дальнего следования. Для каждого поезда указывается: номер поезда, станция назначения, время отправления. Данные в информационной системе организованы в виде линейного списка. Составить программу, которая: 1)обеспечивает первоначальный ввод данных в информационную систему и формирование линейного списка; 2)производит вывод всего списка; 3)вводит номер поезда и выводит все данные об этом поезде; 4)вводит название станции назначения и выводит данные обо всех поездах, следующих до этой станции. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

4.На междугородной телефонной станции картотека абонентов, содержащая сведения о телефонах и их владельцах, организована как линейный список. Составить программу, которая: 1)обеспечивает начальное формирование картотеки в виде линейного списка; 2)производит вывод всей картотеки; 3)вводит номер телефона и время разговора; 4)выводит извещение на оплату телефонного разговора. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

5.Сложить два многочлена, используя представление многочлена в виде списка, в котором элементы расположены в порядке убывания степеней x, а поля элемента содержат соответственно коэффициент при x, степень x, указатель на следующий элемент. Нулевые слагаемые исключить из результирующего списка.

6.Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах содержат: номер УДК, фамилию и инициалы автора, название, год издания, количество экземпляров данной книги в библиотеке. Программа должна обеспечивать: а)начальное формирование данных о всех книгах в библиотеке в виде списка; б)добавление данных о книгах, вновь поступающих в библиотеку; в)удаление данных о списываемых книгах; г)по запросу выдавать сведения о наличии книг в библиотеке, упорядоченные по годам издания.

7.Используя представление многочлена в виде списка в порядке убывания степеней x, по многочлену S(x) построить его производную - многочлен P(x).

8.Картотека в бюро обмена квартир организована как линейный список. Сведения о каждой квартире содержат: количество комнат, этаж, площадь, адрес. Составить программу, которая обеспечивает: а)начальное формирование картотеки; б)ввод заявки на обмен; в)поиск в картотеке подходящего варианта: при равенстве количества комнат и этажа и различии площадей в пределах 10% выводится соответствующая карточка и удаляется из списка, в противном случае поступившая заявка включается в список; г)вывод всего списка. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

9.Перемножить два многочлена, задав их в виде списков.

10. Анкета для опроса населения содержит две группы вопросов. Первая группа содержит сведения о респонденте: возраст, пол, образование (начальное, среднее, высшее). Вторая группа содержит собственно вопрос анкеты, ответ на который либо ДА, либо НЕТ. Составить программу, которая: 1)обеспечивает начальный ввод анкет и формирует из них линейный список; 2)на основе анализа анкет выдает ответы на следующие вопросы: а)сколько мужчин старше 40 лет, имеющих высшее образование, ответили ДА на вопрос анкеты; б)сколько женщин моложе 30 лет, имеющих среднее образование, ответили НЕТ на вопрос анкеты; в)сколько мужчин моложе 25 лет, имеющих начальное образование, ответили ДА на вопрос анкеты; 3)производит вывод всех анкет и ответов на вопросы. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

11. Представить в виде списка распорядок рабочего дня. Написать функции для справок, изменения распорядка.

12. Написать и протестировать функции для включения, исключения и поиска элемента кругового списка для: а)списка без заголовка; б)списка с заголовком (заголовок может содержать некоторую информацию о списке, например, число элементов списка).

13. Написать программу, которая а)сцепляет два списка данных символьного типа; б)объединяет упорядоченные списки данных целого типа в единый упорядоченный список.

14. Написать программу, которая помещает заданное количество случайных целых чисел в диапазоне от 0 до 100 в упорядоченный список. Вычислить сумму элементов и среднее арифметическое.

15. Написать программу, которая создает связный список из заданного количества символов, а затем создаёт второй список - копию, но в обратной последовательности.

16. Написать программу, беспорядочно смешивающую буквы слова для создания слова-путаницы. Каждый символ в строке произвольно помещается либо в начало, либо в конец списка. Например, с вводом jumble последовательность случайных чисел 011001 создаёт lbjume.

17. Написать программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке. Сведения о каждом автобусе содержат: номер автобуса, фамилию водителя, номер маршрута. Программа должна обеспечивать: а)начальное формирование данных о всех автобусах в парке в виде списка; б)при выезде каждого автобуса из парка вводится номер автобуса, и программа удаляет данные об этом автобусе из списка автобусов, находящихся в парке, и записывает эти данные в список автобусов, находящихся на маршруте; в)при въезде каждого автобуса в парк вводится номер автобуса, и программа удаляет данные об этом автобусе из списка автобусов, находящихся на маршруте, и записывает эти данные в список автобусов, находящихся в парке; г)по запросу выдаются сведения об автобусах, находящихся в парке, или об автобусах, находящихся на маршруте.

18. Составить программу, которая содержит текущую информацию о заявках на авиабилеты. Каждая заявка содержит: пункт назначения, номер рейса, фамилию и инициалы пассажира, желаемую дату вылета. Программа должна обеспечивать: а)хранение всех заявок в виде списка; б)добавление заявок в список; в)удаление заявок; г)вывод заявок по заданному номеру рейса и дате вылета; д)вывод всех заявок.

19. Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах содержат: номер УДК, фамилию и инициалы автора, название, год издания, количество имеющихся экземпляров. Программа должна обеспечивать: а)начальное формирование данных о всех книгах в библиотеке в виде списка; б)при взятии каждой книги вводится номер УДК, и программа уменьшает значение количества книг на единицу или выдает сообщение о том, что требуемой книги в библиотеке нет или требуемая книга находится на руках; в)при возвращении каждой книги вводится номер УДК, и программа увеличивает значение количества книг на единицу; г)по запросу выдаются сведения о наличии книг в библиотеке.

20. Написать программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке. Сведения о каждом автобусе содержат: номер автобуса, фамилию и инициалы водителя, номер маршрута, признак того, где находится автобус – на маршруте или а парке. Программа должна обеспечивать: а)начальное формирование данных о всех автобусах в виде списка; б)при выезде каждого автобуса из парка вводится номер автобуса, и программа устанавливает значение признака “автобус на маршруте”; в)при въезде каждого автобуса в парк вводится номер автобуса, и программа устанавливает значение признака “автобус в парке”; г)по запросу выдаются сведения об автобусах, находящихся в парке, или об автобусах, находящихся на маршруте.

21. Составить программу, моделирующую заполнение гибкого диска. Общий объём памяти на диске 1,44 Мбайта. Файлы имеют произвольную длину от 72 байт до 128 Кбайт. В процессе работы файлы либо записываются на диск, либо удаляются с него. В начале работы файлы записываются подряд друг за другом. После удаления файла на диске образуется свободный участок памяти, и вновь записываемый файл размещается на свободном участке, либо, если файл не вмещается в свободный участок, размещается после последнего записанного файла. В случае, когда файл превосходит длину самого большого свободного участка, выдается аварийное сообщение. Требование на запись или удаление файла задается в командной строке, которая содержит имя файла, его длину в байтах, признак записи или удаления. Программа должна выдавать по запросу сведения о занятых и свободных участках памяти на диске. Указание: следует создать список занятых участков и список свободных участков памяти на диске.

22. В файловой системе каталог файлов организован как линейный список. Для каждого файла в каталоге содержатся следующие сведения: имя файла, дата создания, количество обращений к файлу. Составить программу, которая обеспечивает: а)начальное формирование каталога файлов; б)вывод каталога файлов; в)удаление файлов, дата создания которых меньше заданной; г)выборку файла с наибольшим количеством обращений. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

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

24. Текст помощи для некоторой программы организован как линейный список. Каждая компонента текста помощи содержит термин (слово) и текст, содержащий пояснения к этому термину. Количество строк текста, относящихся к одному термину, от одной до пяти. Составить программу, которая обеспечивает: а)начальное формирование текста помощи; б)вывод текста помощи; в)вывод поясняющего текста для заданного термина. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

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

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

27. Проверить на равенство два многочлена, представив каждый из многочленов в виде списка, в котором элементы расположены в порядке убывания степеней x.

28. В целочисленной точке x вычислить значение многочлена S(x), представленного в виде списка в порядке убывания степеней x..

29. Распечатать многочлен, заданный в виде списка, в обычном виде (например, так: 52y^3-6y^2+y).

30. Используя представление многочлена в виде списка, привести подобные члены в многочлене и расположить их по убыванию степеней x.

ЛАБОРАТОРНАЯ РАБОТА 8

БИНАРНОЕ УПОРЯДОЧЕННОЕ  ДЕРЕВО

Введение

    Дерево является нелинейной динамической структурой хранения данных. Дерево состоит из узлов или вершин, которые содержат поля данных и указатели на другие узлы или вершины.

Бинарное дерево

    Узел или вершина бинарного дерева содержит поле данных и два поля с указателями. Поля указателей называются левым указателем (left) и правым указателем (right), поскольку они указывают на левое и правое поддерево, соответственно. Значение NULL указателя является признаком пустого поддерева.

    Корневой узел определяет входную точку дерева, а поле указателя – узел следующего уровня. Листовой узел (лист) содержит NULL в поле правого и левого указателей.

Класс TreeNode

    Объекты класса  TreeNode являются узлами бинарного дерева (рис.8.1).

class TreeNode

{

private:

// указатели левого и правого дочерних узлов

TreeNode* left;

TreeNode* right;

public:

// открытый элемент

int data;

// конструктор

TreeNode(const int& item, TreeNode* lptr=NULL,

                                         TreeNode* rptr=NULL);

// функции-элементы доступа к полям указателей

TreeNode* Left() const;

TreeNode* Right() const;

};

    Конструктор инициализирует поля данных и указателей. С помощью пустого указателя NULL узлы инициализируются как листья. Имея указатель P объекта класса TreeNode в качестве параметра, конструктор присоединяет P как левого или правого потомка нового узла. Функции-элементы Left() и Right() возвращают значения полей левого и правого указателей. Благодаря этому клиент класса имеет доступ к левому и правому потомкам узла.

Примеры

// указатели целочисленных узлов дерева

TreeNode*root, *lp, *rp;

TreeNode*p;

// создать листья, содержащие 20 и 30 в качестве данных

lp=new TreeNode (20);

rp=new TreeNode (30);

// создать корень, содержащий число 10 и двух потомков

root= new TreeNode (10, lp, rp);

Рис.8.1 – бинарное дерево

root->data=50;// присвоить корню 50

Переопределение конструктора

// конструктор инициализирует поля данных и указателей

// значение NULL соответствует пустому поддереву

TreeNode:: TreeNode (const int& item, TreeNode*lp,

     TreeNode*rp):data(item), left(lp), right(rp)

{}

Бинарное упорядоченное дерево ( дерево поиска)

Бинарное дерево поиска – это структура (рис.8.2), которая упорядочивает элементы посредством отношения “<”. Чтобы сравнить узлы дерева, подразумевают, что часть или все поле данных определено в качестве ключа и операция “<” сравнивает ключи при размещении элемента на дереве.

Бинарное дерево поиска строится по следующему правилу:

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

Дерево называется поисковым потому, что в поисках некоторого элемента (ключа) можно идти лишь по совершенно конкретному пути. Начав с корня, сканируют левое поддерево, если значение ключа меньше текущего узла. В противном случае сканируют правое поддерево. Метод создания дерева позволяет осуществлять поиск по кратчайшему пути от корня. Бинарные деревья поиска предназначены для быстрого доступа к данным. В идеале дерево является сбалансированным и имеет высоту и эффективность поиска порядка

                       Рис.8.2 – бинарное упорядоченное дерево

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

    левое поддерево-узел-правое поддерево, или симметричный метод;

    левое поддерево-правое поддерево-узел, или обратный метод;

    правое поддерево-узел- левое поддерево, или справа-налево;

    узел-левое поддерево-правое поддерево, или сверху-вниз.

Для реализации методов используют рекурсивные алгоритмы.

Класс BinSTree

    Объектом этого класса является бинарное упорядоченное дерево (пример - на рис.8.2).

// класс - бинарное дерево

class BinSTree

{

public:

// конструкторы и деструктор

BinSTree();

//конструктор копирования         

BinSTree(const BinSTree& tree);

~BinSTree();

// оператор присваивания

BinSTree& operator=(const BinSTree& rhs);

// функции-элементы обработки данных

int Find(int& item); // есть или нет узла с item

void Insert(const int& item); // вставить узел с item

void Delete(const int& item); // удалить узел с item

void ClearTree();        // уничтожить дерево

TreeNode *CopyTree(TreeNode *t); // копировать дерево

int Depth(TreeNode *t); // получить глубину дерева

// получить количество листьев в дереве

void CountLeaf(TreeNode *t,int& count); 

// получить корень дерева

TreeNode *GetRoot() const {return root;}

// получить количество узлов в дереве

int GetSize() const {return size;}

private:

// указатель на корень

TreeNode *root;

// количество узлов в дереве

int size;

// выделить память под узел дерева

TreeNode *GetTreeNode(const int& item,

      TreeNode *lptr, TreeNode *rptr);

// удалить все узлы дерева

void DeleteTree(TreeNode* t);

// получить указатели -  на узел с item и его родителя

TreeNode *FindNode(const int& item,

                     TreeNode* &parent)const;

}; 

    Конструктор инициализирует данные-элементы. Конструктор копирования и перегруженный оператор присваивания с помощью функции-элемента CopyTree создают новое бинарное дерево для текущего объекта.

 Алгоритм удаления узлов дерева реализован функцией-элементом DeleteTree и используется функцией-элементом ClearTree, вызываемой как деструктором, так и перегруженной операцией присваивания.

Функции-элементы Find и Insert начинают с корня и используют определение бинарного дерева поиска. Алгоритм идет по правому поддереву, когда ключ или новый элемент больше значения текущего узла. В противном случае прохождение продолжается по левому поддереву. Функция-элемент Find использует закрытую функцию-элемент FindNode, принимающую в качестве параметра ключ и осуществляющую прохождение вниз по дереву. Функция возвращает указатель на совпавший узел и указатель на его родителя. Если совпадение происходит в корне, родительский указатель равен NULL.

Функция-элемент Delete удаляет из дерева узел с заданным ключом. Сначала с помощью функции-элемента FindNode устанавливается место этого узла на дереве и определяется указатель на его родителя. Если искомый узел отсутствует, операция удаления завершается.

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

Функция FindNode возвращает указатель DNodePtr на узел D, подлежащий удалению. Второй указатель, PNodePtr, идентифицирует узел P – родителя удаляемого узла. Функция Delete ”пытается” подыскать заменяющий узел R, который будет присоединен к родителю и, следовательно, займет место удаленного узла. Заменяющий узел R идентифицируется указателем RNodePtr.

Функция  Delete реализует алгоритм поиска заменяющего узла  из четырех случаев, зависящих от числа и расположения сыновей удаляемого узла. Отметим, что если указатель на родителя равен NULL, то удаляется и обновляется корень. Эта ситуация учитывается алгоритмом.

Чтобы функции-элементы класса BinSTree получили доступ к закрытым данным-элементам left и right класса TreeNode, класс BinSTree объявляется другом класса TreeNode. Это объявление предваряется формальным объявлением класса BinSTree.  

Целью данной лабораторной работы является изучение алгоритмов и функций работы с бинарным упорядоченным деревом на примере дерева из целых чисел.

Проектирование приложения.