Выбор, размещение и задание свойств компонентов.

 Коды обработчиков событий и функций

Для подготовки текста, выводимого в файл, воспользуемся окном редактирования многострочного текста – компонентом Memo, в котором для всего текста формат одинаков. Сохранять текст в файле удобно, используя компонент “Сохранить файл” – SaveDialog, а для чтения из файла – компонент “Открыть файл” – OpenDialog.

Выводить текст, имея в виду последующую работу с текстом, целесообразно в многострочное окно редактирования – компонент RichEdit, который работает с текстом в обогащенном формате RTF. Здесь можно устанавливать атрибуты выделенного текста свойством SelAttributes, которое имеет ряд подсвойств, например, Style (стиль). Весь текст в RichEdit, представленный одной строкой типа AnsiString, внутри которой используются разделители типа символов возврата каретки и перевода строки, содержится в свойстве Text.

Memo и RichEditимеют общее основное свойство – Lines, содержащее текст окна в виде списка строк. Доступ к отдельной строке текста, например первой, можно получить так: RichEdit1->Lines->String[0]. Во время выполнения приложения можно заносить текст в окно с помощью методов свойства Lines.

При работе с Memo и RichEdit пользуются компонентом PopupMenu – контекстным всплывающим меню. Это меню привязано к конкретным компонентам. Оно всплывает, если во время, когда данный компонент (в нашем случае Memo или RichEdit) находится в фокусе, пользователь щелкнет правой кнопкой мыши. Для Memo всплывающее меню должно содержать команды Сохранить и Сохранить как, а для RichEdit – Открыть.

Первое и второе слова, которые нужно найти и выделить в окне  RichEdit, а затем там же поменять их местами, удобно задавать в однострочных окнах редактирования с метками – LabeledEdit. Введенный в окно текст  присваивается свойству Text, который имеет тип строки AnsiString.

В компонентах Memo, RichEdit и LabeledEdit свойства только времени выполнения SelLength, SelStart, SelText определяют соответственно длину выделенного текста, позицию перед первым символом выделенного текста и сам выделенный текст.

1.Запустите C++Builder 6.

2.Создайте новый проект командой Файл/Новый/Приложение.

3.Сохраните файлы модуля и проекта командой Файл/Сохранить все под именами LR_2 и PR_LR_2 в каталоге ТЕХН_ПРОГР. Для этого удобно использовать соответствующую быструю кнопку (Сохранить все). В последующих сеансах работы сохраненный проект можно открыть командой Файл/Открыть проект (или Повторно открыть). Теперь перейдем к проектированию приложения - переносам на форму необходимых компонентов и заданию их свойствам значений, а в обработчиках событий – размещению кодов соответствующих алгоритмов. (Рекомендуется нажимать кнопку  Сохранить все по окончании работы с каждым компонентом.) В результате проектирования получим форму, представленную на рис.2.1.

Рис.2.1 – форма по окончании проектирования

4.Выделите форму, щелкнув на ней левой кнопкой мыши, и в свойство Caption(надпись) впишите ТЕКСТОВЫЕ ФАЙЛЫ, СИМВОЛЫ, СТРОКИ.

5.Перенесите на форму (страница Диалоги) компоненты SaveDialog1 и OpenDialog1. Все диалоги являются невизуальными компонентами, так что место их размещения на форме не имеет значения. При обращении к этим компонентам вызываются стандартные диалоги.

6.Перенесите дважды на форму со страницы Стандарт компонент PopupMenu. Он также является невизуальным компонентом. Двойным щелчком на компонентеPopupMenu1 перейдите в Конструктор Меню (окно Form1->PopupMenu1) и внесите разделы Сохранить и Сохранить как, а для компонента PopupMenu2- Открыть.

7.Перенесите на форму компоненты Memo1 (страница Стандарт) и RichEdit1(страницаWin32). В свойствоPopupMenu компонента Memo1 внесите из выпадающего спискаPopupMenu1, а в свойствоPopupMenu компонента RichEdit1 - внеситеPopupMenu2.

8.В файле LR_2.cpp перед обработчиком щелчка на разделе Сохранить дайте объявление

AnsiString MyFName="";

а в обработчик щелчка на разделе Сохранить внесите (курсив)

void __fastcall TForm1::N1Click(TObject *Sender)

{

if(MyFName!="")

Memo1->Lines->SaveToFile(MyFName);

else

if(SaveDialog1->Execute())

{

  MyFName=SaveDialog1->FileName;

  Memo1->Lines->SaveToFile(SaveDialog1->FileName);

}

}

9.В обработчик щелчка на разделе Сохранить как внесите (курсив)

void __fastcall TForm1::N2Click(TObject *Sender)

{

SaveDialog1->FileName=MyFName;

if(SaveDialog1->Execute())

{

MyFName=SaveDialog1->FileName;

Memo1->Lines->SaveToFile(SaveDialog1->FileName);

}

}

10.В обработчик щелчка на разделе Открыть внесите (курсив)

void __fastcall TForm1::N3Click(TObject *Sender)

{

 if(OpenDialog1->Execute())

{

MyFName=OpenDialog1->FileName;

RichEdit1->Lines->LoadFromFile(OpenDialog1->FileName);

}

}

11.Перенесите на форму (рис.2.1) кнопку Button1(страница Стандарт) с надписью СБРОС для очистки окон редактирования; перед обработчиком щелчка на кнопке внесите int f=0; а в обработчик – {курсив}

void __fastcall TForm1::Button1Click(TObject *Sender)

{

 Memo1->Clear();RichEdit1->Clear();

 LabeledEdit1->Clear(); LabeledEdit2->Clear();

 Memo1->SetFocus();

 f=1;

}

12.Поместите на форме, ниже кнопки с надписью СБРОС, окно редактирования с меткой LabeledEdit1(страница Дополнительно). Свойству LabelPosition присвойте значение lpAbove (из выпадающего списка), а раскрыв свойство EditLabel,в подсвойствоCaption впишите первое слово.

13.Ниже разместите кнопку Button2 (страница Стандарт) с надписью найти первое слово. В файле LR_2.cpp перед обработчиком щелчка на кнопке дайте объявления

int k1,k2;

unsigned l1,l2;

а в обработчик щелчка на кнопке внесите (курсив)

void __fastcall TForm1::Button2Click(TObject *Sender)

{

Memo1->Lines->Add("НАЙТИ:");

l1=LabeledEdit1->SelLength;

 if((k1=FindWord(RichEdit1->Text.c_str(),

         LabeledEdit1->SelText.c_str()))>=0)

{Memo1->Lines->Add("Первое слово - с позиции "+IntToStr(k1+1));

RichEdit1->SelStart=k1;

RichEdit1->SelLength=l1;

RichEdit1->SelAttributes->Style=

      RichEdit1->SelAttributes->Style<<fsBold;

RichEdit1->SelStart=k1+l1;}

      else Memo1->Lines->Add("Нет первого слова!");

}

14.Ниже разместите LabeledEdit2(страница Дополнительно). Свойству LabelPosition присвойте значение lpAbove (из выпадающего списка), а раскрыв свойство EditLabel,в подсвойствеCaption впишите второе слово.

15.Ниже разместите кнопку Button3 (страница Стандарт) с надписью найти второе слово, в обработчик щелчка на которой внесите (курсив)

void __fastcall TForm1::Button3Click(TObject *Sender)

{       

    l2=LabeledEdit2->SelLength;

     if((k2=FindWord(RichEdit1->Text.c_str(),

             LabeledEdit2->SelText.c_str()))>=0)

      {Memo1->Lines->Add("Второе слово - с позиции "+IntToStr(k2+1));

      RichEdit1->SelStart=k2;

      RichEdit1->SelLength=l2;

      RichEdit1->SelAttributes->Style=

           RichEdit1->SelAttributes->Style<<fsBold;

      RichEdit1->SelStart=k1+l2;}

else Memo1->Lines->Add("Нет второго слова!");

}

16.Введенные в компонентыLabeledEdit1и LabeledEdit2первое и второе словав тексте могут оказаться стоящими как второе и первое. Следовательно, введенные слова необходимо упорядочить. Разместите на форме кнопку Button4 (страница Стандарт) с надписью упорядочить, в обработчик щелчка на которой внесите (курсив)

void __fastcall TForm1::Button4Click(TObject *Sender)

{

  AnsiString s="";

unsigned d=0;

if(k1>k2){

       Memo1->Lines->Add("");

       Memo1->Lines->Add("УПОРЯДОЧИТЬ:");

       d=k1; k1=k2; k2=d;

       d=l1; l1=l2; l2=d;

       s=LabeledEdit1->Text;

       LabeledEdit1->Text=LabeledEdit2->Text;

       LabeledEdit2->Text=s;

       Memo1->Lines->Add("Первое слово - с позиции "+IntToStr(k1+1));

       Memo1->Lines->Add("Второе слово - с позиции "+IntToStr(k2+1));}

}

17.Ниже разместите кнопку Button5 (страница Стандарт) с надписью поменять местами, в обработчик щелчка на которой внесите (курсив)

void __fastcall TForm1::Button5Click(TObject *Sender)

{

if(k1>=0&&k2>=0&&f){

f=0; Memo1->Lines->Add("");

Memo1->Lines->Add("ПОМЕНЯТЬ МЕСТАМИ:");

RichEdit1->SelStart=k1;

RichEdit1->SelLength=l1;

RichEdit1->SetSelTextBuf(LabeledEdit2->Text.c_str());

RichEdit1->SelStart=k2+(l2-l1);

RichEdit1->SelLength=l2;

RichEdit1->SetSelTextBuf(LabeledEdit1->Text.c_str());

Memo1->Lines->Add("Второе слово - с позиции "+IntToStr(k1+1));

  Memo1->Lines->Add("Первое слово - с позиции "+

IntToStr(k2+1+(l2-l1)));}

}

18.Проектирование приложения закончим включением в файл LR_2.cpp   перед обработчиком щелчка на кнопкеButton2 (с надписью найти первое слово) определения функции, которая для строк типа char* ищет одну строку в другой. В случае успеха функция возвращает номер позиции, с которой начинается короткая строка в длинной строке, а в случае неуспеха - возвращает -1.

int FindWord(char*str,char*word)

{ unsigned ls=strlen(str);

for(unsigned i=0; i<ls; i++)

{ bool find=true;

char*w=word; int k=i;

if(str[i]==*w)

{ while(*w) if(*w++!=str[k++])

{ find=false; break;}

if(find) return k-strlen(word);}

}

return -1;

}

19.По окончании проектирования файл LR_2.cpp будет выглядеть так:

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

#include <vcl.h>

#pragma hdrstop

#include "LR_2.h"

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

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

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

__fastcall TForm1::TForm1(TComponent* Owner)

   : TForm(Owner)

{

}

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

AnsiString MyFName="";

void __fastcall TForm1::N1Click(TObject *Sender)

{

if(MyFName!="")

Memo1->Lines->SaveToFile(MyFName);

else

if(SaveDialog1->Execute())

{

  MyFName=SaveDialog1->FileName;

  Memo1->Lines->SaveToFile(SaveDialog1->FileName);

}

}

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

void __fastcall TForm1::N2Click(TObject *Sender)

{

 SaveDialog1->FileName=MyFName;

if(SaveDialog1->Execute())

{

MyFName=SaveDialog1->FileName;

Memo1->Lines->SaveToFile(SaveDialog1->FileName);

}

}

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

void __fastcall TForm1::N3Click(TObject *Sender)

{

if(OpenDialog1->Execute())

{

MyFName=OpenDialog1->FileName;

RichEdit1->Lines->LoadFromFile(OpenDialog1->FileName);

}

}

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

int f=0;

void __fastcall TForm1::Button1Click(TObject *Sender)

{

 Memo1->Clear(); RichEdit1->Clear();

 LabeledEdit1->Clear(); LabeledEdit2->Clear();

 Memo1->SetFocus(); f=1;

}

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

//Функция поиска слова word в строке str. В случае успеха

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

int FindWord(char*str,char*word)

{ unsigned ls=strlen(str);

for(unsigned i=0;i<ls;i++)

{ bool find=true;

char*w=word;  int k=i;

if(str[i]==*w)

{ while(*w) if(*w++!=str[k++])

{ find=false; break;}

//если в строке str есть слово word, то выход из цикла while –

//по завершающему нулевому символу слова word в позиции i

if(find) return k-strlen(word);} //вычитаем длину слова word

}

return -1;

}

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

int k1,k2;

unsigned l1,l2;

void __fastcall TForm1::Button2Click(TObject *Sender)

{

Memo1->Lines->Add("НАЙТИ:");

l1=LabeledEdit1->SelLength;//находим длину выделенного первого слова

//вызов функции FindWord() с преобразованием строк

// типа AnsiString к типу char*

if((k1=FindWord(RichEdit1->Text.c_str(),

             LabeledEdit1->SelText.c_str()))>=0) //искомое слово выделено

      {Memo1->Lines->Add("Первое слово - с позиции "+IntToStr(k1+1));

      RichEdit1->SelStart=k1; //ставим курсор перед первым словом

      RichEdit1->SelLength=l1; //выделяем первое слово

      RichEdit1->SelAttributes->Style=

           RichEdit1->SelAttributes->Style<<fsBold; //жирный шрифт

      RichEdit1->SelStart=k1+l1;} //ставим курсор после первого слова

                                                      //для сохранения выделения

  else Memo1->Lines->Add("Нет первого слова!");

}

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

void __fastcall TForm1::Button3Click(TObject *Sender)

{

l2=LabeledEdit2->SelLength;//находим длину выделенного второго слова

//вызов функции FindWord() с преобразованием строк

// типа AnsiString к типу char*

if((k2=FindWord(RichEdit1->Text.c_str(),

             LabeledEdit2->SelText.c_str()))>=0) //искомое слово выделено

      {Memo1->Lines->Add("Второе слово - с позиции "+IntToStr(k2+1));

      RichEdit1->SelStart=k2; //ставим курсор перед вторым словом

      RichEdit1->SelLength=l2; //выделяем второе слово

      RichEdit1->SelAttributes->Style=

           RichEdit1->SelAttributes->Style<<fsBold; //жирный шрифт

      RichEdit1->SelStart=k1+l2;} //ставим курсор после второго слова

                                                      //для сохранения выделения

  else Memo1->Lines->Add("Нет второго слова!");

}

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

void __fastcall TForm1::Button4Click(TObject *Sender)

{

 AnsiString s=""; //строка для обмена

unsigned d=0; //беззнаковое целое для обмена

if(k1>k2){ //условие неправильного порядка следования слов

       Memo1->Lines->Add("");

        Memo1->Lines->Add("УПОРЯДОЧИТЬ:");

       d=k1; k1=k2; k2=d;

       d=l1; l1=l2; l2=d;

       s=LabeledEdit1->Text;

       LabeledEdit1->Text=LabeledEdit2->Text;

       LabeledEdit2->Text=s;

       Memo1->Lines->Add("Первое слово - с позиции "+IntToStr(k1+1));

       Memo1->Lines->Add("Второе слово - с позиции "+IntToStr(k2+1));}

}

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

void __fastcall TForm1::Button5Click(TObject *Sender)

{

 if(k1>=0&&k2>=0&&f){ //проверяем, в тексте ли слова

f=0; Memo1->Lines->Add("");

Memo1->Lines->Add("ПОМЕНЯТЬ МЕСТАМИ:");

RichEdit1->SelStart=k1;

RichEdit1->SelLength=l1;

//ставим второе слово на место выделенного первого слова

RichEdit1->SetSelTextBuf(LabeledEdit2->Text.c_str());

RichEdit1->SelStart=k2+(l2-l1);

RichEdit1->SelLength=l2;

//ставим первое слово на место выделенного второго слова

RichEdit1->SetSelTextBuf(LabeledEdit1->Text.c_str());

Memo1->Lines->Add("Второе слово - с позиции "+IntToStr(k1+1));

Memo1->Lines->Add("Первое слово - с позиции "+

IntToStr(k2+1+(l2-l1)));}

}

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

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

    Пример выполнения приложения представлен на рис.2.2, 2.3.

Рис.2.2 – заданные первое и второе слова найдены и выделены в тексте

Рис.2.3 – найденные слова упорядочены и переставлены местами

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

2.Наберите текст в окне Memo1 для вывода в файл. Правой кнопкой мыши щелкните на окне и во всплывшем меню выберите нужную команду (сохранить или сохранить как). Сохраните текст в файле с расширением .dat.

3.Сотрите текст в окне Memo1, щелкнув на кнопке СБРОС. Щелкните правой кнопкой мыши на окне RichEdit1 и прочитайте файл.

4.В окно первое слово введите слово из текста, выделите введенное слово и нажмите кнопку найти первое слово.

5.В окно второе слово введите слово из текста, выделите введенное слово и нажмите кнопку найти второе слово. Результат представлен на рис.2.2.

6.Нажмите кнопку упорядочить. Если в тексте порядок следования введенных слов другой, то слова в окнах ввода поменяются местами (как в примере на рис.2.2).

7.Нажатием кнопки поменять местами завершаем выполнение задания (рис.2.3).

8.Для завершения работы щелкните на кнопке формы “Закрыть” и выйдите из среды Builder.

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

1.Поясните назначение и использование компонентов “Сохранить файл” и “Открыть файл”.

2.Поясните назначение компонента контекстное всплывающее меню. Как осуществляется связь этого компонента с окнами Memoи RichEdit?

3.Какие общие свойства имеют компоненты LabeledEdit, Memoи RichEdit? Компоненты Memoи RichEdit? Чем отличаетсяRichEditот Memo?

4.Как используются компонентыLabeledEdit, Memoи RichEditпри выполнении задания?

5.Представьте блок-схему алгоритма, реализованного функцией FindWord(). Расскажите по алгоритму,  как осуществляется поиск слова в строке.

6.Какие операции с указателями используются в функции FindWord()?

7.Как вызывается функция FindWord()?

8.Как преобразовать строку типа AnsiStringв строку типа char*? Как выполнить обратное преобразование?

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

10.Объясните, как переставляются местами найденные в тексте слова. Какие свойства компонента RichEditпри этом используются?

11.Поясните назначение глобальных переменных.

12.Как сохранить в файле текст, представленный в RichEdit?

13.Как заключить в кавычки выделенные в тексте слова?

14.Как изменить размер шрифта и цвет выделенных в тексте слов?

Задания

С помощью текстового редактора создать файл, содержащий текст, длина которого не превышает 1000 символов, а длина строки текста содержит не более 70 символов.

 Имя файла должно иметь расширение DAT.

Написать программу, которая:

                                                а) выводит текст на экран дисплея;

                                      б) далее – по варианту.

1. По нажатию произвольной клавиши поочередно выделяет каждое предложение текста; определяет количество предложений в тексте.

2. По нажатию произвольной клавиши поочередно выделяет каждое слово текста; определяет количество слов в тексте.

3. По нажатию произвольной клавиши поочередно выделяет каждое слово текста, оканчивающееся на гласную букву; определяет количество таких слов в тексте.

4. По нажатию произвольной клавиши поочередно выделяет каждое предложение текста в последовательности 2, 1, 3.

5. По нажатию произвольной клавиши поочередно выделяет каждое из слов текста, у которых первый и последний символы совпадают; определяет количество таких слов в тексте.

6. По нажатию произвольной клавиши поочередно выделяет каждое слово текста, начинающееся на гласную букву; определяет количество таких слов в тексте.

7. Определяет количество символов в самом длинном слове; по нажатию произвольной клавиши поочередно выделяет каждое слово текста, содержащее максимальное количество символов.

8. Определяет количество символов в самом коротком слове; по нажатию произвольной клавиши поочередно выделяет каждое слово текста, содержащее минимальное количество символов.

9. Определяет в каждом предложении текста количество символов, отличных от букв и пробела; по нажатию произвольной клавиши поочередно выделяет каждое предложение текста, а в выделенном предложении – поочередно все символы, отличные от букв и пробела.

10. Определяет количество предложений текста и количество слов в каждом предложении; по нажатию произвольной клавиши поочередно выделяет каждое предложение текста, а в выделенном предложении - поочередно все слова.

11. Определяет количество букв ‘а’ в последнем слове текста; по нажатию произвольной клавиши выделяет последнее слово текста, а в выделенном слове – поочередно все буквы ‘а’.

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

13. Определяет порядковый номер заданного слова в каждом предложении текста (заданное слово вводится с клавиатуры); по нажатию произвольной клавиши поочередно выделяет каждое предложение текста, а в выделенном предложении – заданное слово.

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

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

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

17. Выводит текст на экран дисплея ещё раз, вставляя в каждое предложение в качестве последнего заданное слово, введенное с клавиатуры в качестве исходных данных; по нажатию произвольной клавиши поочередно выделяет в тексте вставленное слово.

18. По нажатию произвольной клавиши поочередно выделяет в тексте лишние пробелы между словами; выводит текст на экран дисплея ещё раз, удаляя лишние пробелы между словами и начиная каждое предложение с новой строки.

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

20. Определяет наибольшее количество подряд идущих пробелов в тексте; по нажатию произвольной клавиши поочередно выделяет каждую из последовательностей пробелов максимальной длины.

21. Определяет в каждой строке текста количество прописных букв; по нажатию произвольной клавиши поочередно выделяет каждое слово, начинающееся с прописной буквы, а в выделенном слове – прописные буквы.

22. По нажатию произвольной клавиши поочередно выделяет в тексте слово с заданной буквой; выводит на экран дисплея ещё раз те слова, в которых заданная буква встречается более одного раза.

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

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

25. Выводит текст на экран дисплея ещё раз, разделяя знаками переноса каждое слово на слоги; по нажатию произвольной клавиши поочередно выделяет в каждой строке текста слово с наибольшим количеством слогов.

26. По нажатию произвольной клавиши поочередно выделяет в тексте слова, после которых стоит знак препинания; выводит текст на экран ещё раз, выделяя знаки препинания.

27. По нажатию произвольной клавиши выводит количество десятичных чисел по строкам; выводит текст на экран дисплея ещё раз, заменяя десятичные числа на шестнадцатеричные.

28. По нажатию произвольной клавиши поочередно выделяет каждое число в тексте; выводит текст на экран дисплея ещё раз, заменяя числа пробелами.

29. По нажатию произвольной клавиши поочередно выделяет в тексте слова с заданной буквой (вводится с клавиатуры); выводит на экран дисплея ещё раз те слова, в которых нет заданной буквы.

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

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

СОРТИРОВКИ ЧИСЛОВЫХ МАССИВОВ.

РЕКУРСИВНЫЕ ФУНКЦИИ

Задание

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

СОРТИРОВКА ОБМЕНАМИ

    Выполняется за n-1 проходов, где n – размер массива. В первом проходе первый элемент массива (с индексом 0) сравнивается с остальными элементами массива (с индексами 1…n-1) и, если предшествующий элемент больше последующего, они меняются местами. В последнем проходе сравниваются предпоследний и последний элементы массива. Следовательно, в каждом проходе количество сравнений фиксировано. Общее количество сравнений за сортировку равно n(n-1)/2.

Количество обменов зависит от состояния исходного массива. Если массив уже отсортирован, то обменов не будет. Это наилучший случай с точки зрения затрат машинного времени. Наихудший случай – при пересортировке массива, когда исходный массив отсортирован по убыванию. В этом случае каждое сравнение сопровождается обменом и, следовательно, количество обменов за сортировку равно  n(n-1)/2.

СОРТИРОВКА ВЫБОРОМ

    Эта сортировка требует также n-1 проходов. В первом проходе сравнениями первого элемента с остальными находят минимальный элемент и обменом помещают его на место первого элемента. В последнем проходе сравниваются предпоследний и последний элементы массива. Следовательно, в каждом проходе количество сравнений фиксировано. Общее количество сравнений за сортировку равно n(n-1)/2.

    Число обменов всегда один на проход, следовательно, сортировка требует n-1 обменов. Наилучшего и наихудшего случаев не существует.

СОРТИРОВКА ВСТАВКАМИ

    Выполняется за n-1 проходов. В первом проходе второй элемент массива (с индексом 1) сравнивается с первым элементом массива и, если второй оказывается меньше первого, первый сдвигается на место второго, а второй вставляется на место первого. В последнем проходе последний элемент массива сравнивается с предшествующими, начиная с предпоследнего, и вставляется между элементами, предыдущий из которых меньше, а последующий – больше последнего элемента. Среднее количество сравнений за сортировку - n(n-1)/4. Наилучший случай соответствует уже отсортированному массиву, когда количество сравнений равно n-1. Наихудший случай имеет место при пересортировке массива, при этом количество сравнений равно n(n-1)/2.

    Обменов при сортировке вставками нет.

СОРТИРОВКА ПУЗЫРЬКОМ

    В отличие от сортировки обменами, здесь сравниваются только соседние элементы и, если они стоят неправильно, меняются местами. В первом проходе сравниваются с соседним справа элементы с первого до предпоследнего. При этом сохраняется индекс первого из участвующих в последнем обмене элементов, что исключает избыточные просмотры массива. В следующем проходе просматривается часть массива с первого элемента по элемент с сохраненным индексом. Наилучший случай – массив уже отсортирован и нужен всего один проход с n-1 сравнениями. Наихудший случай – при пересортировке, когда потребуется n-1 проход с n(n-1)/2 сравнениями и n(n-1)/2 обменами.

БЫСТРАЯ СОРТИРОВКА

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

    Наилучший случай соответствует отсортированному массиву с четным количеством элементов, когда число сравнений равно . При пересортировке число сравнений практически такое же.

    В наихудшем случае центральный элемент все время попадает в одноэлементный подмассив, а все остальные элементы остаются во втором подмассиве. Это происходит тогда, когда центральным всегда оказывается наименьший элемент. Здесь общее число сравнений равно n(n+1)/2-1. Однако этот случай маловероятен на практике.

РЕКУРСИВНЫЕ ФУНКЦИИ

    В программировании рекурсия – вызов функции из этой же функции (простая рекурсия) или через другие функции (сложная рекурсия). Количество вложенных вызовов рекурсивной функции называют глубиной рекурсии. Рекурсивные функции реализуют рекурсивные алгоритмы.

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

    Приведем рекурсивные функции для указанных выше сортировок по возрастанию массива a длиной  n. В приводимых функциях: swap() – вызов функции обмена, obm и sr – количество обменов и сравнений соответственно.

СОРТИРОВКА ОБМЕНАМИ

void SwapSort(int i, int j)

{ if(i==n-1) return;

if(j<n) {

            if(a[i]>a[j]) {swap(a[i],a[j]); obm++;}

                sr++; SwapSort(i,j+1);

         }

else SwapSort(i+1,i+2);

}

Вызов функции - SwapSort(0, 1).

СОРТИРОВКА ВЫБОРОМ

void SelectSort(int i, int j, int min)

{ if(i==n-1) return;

if(j<n) {

            if(a[min]>a[j]) min=j;

            sr++; SelectSort(i, j+1, min);

          }

else {

          swap(a[i],a[j]); obm++;

          SelectSort(i+1, i+2, i+1);

         }

}

Вызов функции - SelectSort(0, 1, 0).

СОРТИРОВКА ВСТАВКАМИ

void InsertSort(int i, int j, int z)

{ if(i==n) return;

if(j>0&&z<a[j-1]) {

                               a[j]=a[j-1]; sr++;

                               InsertSort(i, j-1, z);

                            }

else {

           a[j]=z; sr++;

            InsertSort(i+1, i+1, a[i+1]);

        }

}

Вызов функции - InsertSort(1, 1, a[1]).

СОРТИРОВКА ПУЗЫРЬКОМ

void BubbleSort(int i, int j, int last)

{ if(i<=0) return;

if(j<i) {

          if(a[j]>a[j+1]) {swap(a[i],a[j]); obm++; last=j;}

                sr++; BubbleSort (i,j+1,last);

         }

else BubbleSort (last,0,0);

}

Вызов функции - BubbleSort (n-1,0,0).

БЫСТРАЯ СОРТИРОВКА

void QuickSort(int l, int h)

{ int su,sd,m,p;

if(h-l<=0) return;

else if(h-l==1) {

                          if(a[h]<a[l]) { swap(a[l],a[h]); obm++; }

                                  sr++;

                              return;

                        }

m=(l+h)/2; p=a[m]; swap(a[m],a[l]); obm++; su=l+1;sd=h;

do {

    while(su<=sd && a[su]<=p) {su++; sr++;}

    while(p<a[sd]) {sd++; sr++;}

    if(su<sd) {swap(a[su],a[sd]); obm++; }

  } while(su<sd);

a[l]=a[sd]; a[sd]=p; obm++;

if(l<sd-1) QuickSort(l,sd-1);

if(sd+1<h) QuickSort(sd+1,h);

}

Вызов функции - QuickSort(0,n-1);

    Данные для формирования массивов и размещения результатов сортировки массивов, а также функции сортировок инкапсулированы в классе. Объявление класса:

    class array {

              public:

              array(int);  //конструктор 1 (с параметром)

              array(array&);                 //конструктор 2 (копии)

              void swap(int&, int&);  //обмен элементов массива

              void SwapSort(int, int);   //обменная сортировка

              void SelectSort(int, int, int); //сортировка выбором

void InsertSort(int, int, int); //сортировка вставками

              void BubleSort(int, int, int);   //сортировка пузырьком

              void QuickSort(int, int);    //быстрая сортировка             

                  void out_mass_a()const;    //вывод массива

int get_sr() const; //получение количества сравнений

               int get_obm() const;  //получение количества обменов      

              ~array() {delete [] a;}        //деструктор

              private:

              int* a; //указатель для формирования массива

              int n;  //размер массива

              int sr; //количество сравнений

              int obm; //количество обменов

                 };

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