Лекция 1.7 Символы и строки

Общий взгляд

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

  • отдельные символы, чаще всего, его называют типом char;
  • строки постоянной длины, часто они представляются массивом символов;
  • строки переменной длины – это, как правило, тип string, соответствующий современному представлению о строковом типе.

Символьный тип char, представляющий частный случай строк длиной 1, полезен во многих задачах. Основные операции над строками — это разбор и сборка. При их выполнении приходится, чаще всего, доходить до каждого символа строки. В языке Паскаль, где был введен тип char, сам строковый тип рассматривался, как char[]–массив символов. При таком подходе получение i-го символа строки становится такой же простой операцией, как и получение i-го элемента массива, следовательно, эффективно реализуются обычные операции над строками – определение вхождения одной строки в другую, выделение подстроки, замена символов строки. Однако заметьте, представление строки массивом символов хорошо только для строк постоянной длины. Массив не приспособлен к изменению его размеров, вставки или удалению символов (подстрок).

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

Тип string в языке C# допускает двойственную интерпретацию. С одной стороны значения переменной типа string можно рассматривать, как неделимое значение – скаляр – строку текста. С другой стороны это значение можно интерпретировать, как массив из  n элементов, где n – это длина строки. Каждый такой элемент задает отдельный символ и принадлежит символьному типу char.

string s1 = ”рок”, s2 = ”око”,;

char ch1, ch2, ch3;

ch1 = s1[0];  ch2 = s1[1]; ch3 = s1[2];

string s3 = s1 + s2;

В этом примере показано, как можно работать с отдельными символами строки  и как можно работать со скалярным представлением строки.

Класс char

В C# есть символьный класс char, основанный на классе System.Char и использующий двухбайтную кодировку Unicode представления символов. Для этого типа в языке определены символьные константы – символьные литералы. Константу можно задавать:

  • символом, заключенным в одинарные кавычки;
  • escape-последовательностью;
  • Unicode-последовательностью, задающей Unicode код символа.

Вот несколько примеров объявления символьных переменных и работы с ними:

/// <summary>

/// Символы, коды, строки

/// </summary>

public void TestChar()

{

char ch1=’A', ch2 =’\x5A’, ch3=’\u0058′;

char ch = new Char();

int code; string s;

ch = ch1;

//преобразование символьного типа в тип int

code = ch; ch1=(char) (code +1);

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

//s = ch;  

s = ch1.ToString()+ch2.ToString()+ch3.ToString();

Console.WriteLine(«s= {0}, ch= {1}, code = {2}»,

s, ch, code);

}//TestChar

Три символьные переменные инициализированы константами, значения которых заданы тремя разными способами. Переменная ch объявляется в объектном стиле, используя new и вызов конструктора класса. Тип char, как и все типы C#, является классом. Этот класс наследует свойства и методы класса object и имеет большое число собственных методов.

Существуют ли преобразования между классом char и другими классами? Явные или неявные преобразования между классами char и string отсутствуют, но, благодаря методу ToString, переменные типа char стандартным образом преобразуются в тип string. Поскольку у каждого символа есть свой код, то существуют неявные преобразования типа char в целочисленные типы, начиная с типа ushort. Обратные преобразования целочисленных типов в тип char также существуют, но они уже явные.

В результате работы процедуры TestChar строка s, полученная сцеплением трех символов, преобразованных в строки, имеет значение BZX, переменная ch равна A в латинском алфавите, а ее код – переменная code – 65. Хотя преобразования символа в код  и обратно просты, полезно иметь процедуры, выполняющие взаимно-обратные операции, – получение по коду символа и получение символа по его коду:

/// <summary>

/// Код символа

/// </summary>

/// <param name=»sym»>символ</param>

/// <returns>его код</returns>

public static int SayCode(char sym)

{

return sym;

}//SayCode

 

/// <summary>

/// Символ

/// </summary>

/// <param name=»code»>Код символа</param>

/// <returns>символ</returns>

public static char SaySym(int code)

{

return (char)code;

}// SaySym

В первой процедуре преобразование к целому типу выполняется неявно. Во второй – преобразование явное.

Говоря о символах и их кодировке, следует помнить, что для символов алфавитов естественных языков (латиницы, кириллицы) применяется плотная кодировка. Это означает, что поскольку буква z в латинице следует за буквой y, то код z на единицу больше кода y. Только буква «Ё»  в кириллице  не подчиняется этому правилу. Для цифр также используется плотная кодировка, и их коды предшествуют кодам букв. Заглавные буквы в кодировке предшествуют строчным. Ряд символов воспринимаются как управляющие, выполняя при их появлении определенное действие. К таковым относятся такие символы как «перевод строки» (new line), «возврат каретки» (carriage return), «звонок». Эти символы не имеют видимого образа, а их коды задаются escape последовательностями (‘\n’, ‘\r’).  Поскольку алфавит, задаваемый Unicode кодировкой, содержит более 65000 символов, то большинство кодов зарезервировано и им пока не соответствуют реальные символы. Рассмотрим пример, демонстрирующий коды некоторых символов.

// <summary>

/// Преобразования код <-> символ

/// </summary>

public void SymToFromCode()

{

char sym1 = ’0′, sym2 = ‘a’,

sym3 = ‘A’, sym4 = ‘\r’,

sym5 = ‘а’, sym6 = ‘А’;

PrintCode(sym1); PrintCode(sym2);

PrintCode(sym3); PrintCode(sym4);

PrintCode(sym5); PrintCode(sym6);

int code1 = 13, code2 = 122,

code3 = 1071, code4 = 70000;

PrintSym(code1); PrintSym(code2);

PrintSym(code3); PrintSym(code4);

}

Процедуры печати PrintCode и PrintSym достаточно просты, так что код их не приводится. Результат работы этого метода показан на рис. 7_1.

Рис. 7_1  Символы  и их коды

Класс char, как и все классы в C#, наследует свойства и методы родительского класса object. Но у него есть и собственные методы и свойства, и их немало. Приведу сводку этих методов:

Таблица 13-1. Статические методы и свойства класса char

Метод Описание
GetNumericValue Возвращает численное значение символа, если он является   цифрой, и (-1) в противном случае.
GetUnicodeCategory Все символы разделены на категории. Метод возвращает Unicode категорию символа.   Ниже приведен пример.
IsControl Возвращает true,   если символ является управляющим.
IsDigit Возвращает true,   если символ является десятичной цифрой.
IsLetter Возвращает true,   если символ является буквой.
IsLetterOrDigit Возвращает true,   если символ является буквой или цифрой.
IsLower Возвращает true,   если символ задан в нижнем регистре.
IsNumber Возвращает true,   если символ является числом (десятичной или шестнадцатеричной цифрой).
IsPunctuation Возвращает true,   если символ является знаком препинания.
IsSeparator Возвращает true,   если символ является разделителем.
IsSurrogate Некоторые символы Unicode с кодом в интервале [0x1000, 0x10FFF] представляются двумя 16-битными «суррогатными» символами.   Метод возвращает true,   если символ является суррогатным.
IsUpper Возвращает true,   если символ задан в верхнем регистре.
IsWhiteSpace Возвращает true,   если символ является «белым пробелом». К белым пробелам, помимо пробела,   относятся и другие символы, например, символ конца строки и символ перевода   каретки.
Parse Преобразует строку в символ. Естественно, строка должна   состоять из одного символа, иначе возникнет ошибка.
ToLower Приводит символ к нижнему регистру.
ToUpper Приводит символ к верхнему регистру.
MaxValue,   MinValue Свойства, возвращающие символы с максимальным и минимальным   кодом. Возвращаемые символы не имеют видимого образа.

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

/// <summary>

/// Свойства символов

/// </summary>

public void TestCharMethods()

{

Console.WriteLine(«Метод GetUnicodeCategory:»);

System.Globalization.UnicodeCategory cat1, cat2;

cat1 = char.GetUnicodeCategory(‘A’);

cat2 = char.GetUnicodeCategory(‘;’);

Console.WriteLine(«‘A’ — category {0}», cat1);

Console.WriteLine(«‘;’ — category {0}», cat2);

Console.WriteLine(«Метод IsLetter:»);

Console.WriteLine(«‘z’ — IsLetter — {0}»,

char.IsLetter(‘z’));

Console.WriteLine(«‘Я’ — IsLetter — {0}»,

char.IsLetter(‘Я’));

Console.WriteLine(«Метод IsLetterOrDigit:»);

Console.WriteLine(«’7′ — IsLetterOrDigit — {0}»,

char.IsLetterOrDigit(’7′));

Console.WriteLine(«‘Я’ — IsLetterOrDigit — {0}»,

char.IsLetterOrDigit(‘Я’));

Console.WriteLine(«Метод IsControl:»);

Console.WriteLine(«‘;’ — IsControl — {0}»,

char.IsControl(‘;’));

Console.WriteLine(@»‘\r’ — IsControl — {0}»,

char.IsControl(‘\r’));

Console.WriteLine(«Метод IsSeparator:»);

Console.WriteLine(«‘ ‘ — IsSeparator — {0}»,

char.IsSeparator(‘ ‘));

Console.WriteLine(«‘;’ — IsSeparator — {0}»,

char.IsSeparator(‘;’));

Console.WriteLine(«Метод IsWhiteSpace:»);

Console.WriteLine(«‘ ‘ — IsWhiteSpace — {0}»,

char.IsWhiteSpace(‘ ‘));

Console.WriteLine(@»‘\r’ — IsWhiteSpace — {0}»,

char.IsWhiteSpace(‘\r’));

}//TestCharMethods

Вот как выглядят результаты консольного вывода, порожденного выполнением метода:

Рис. 7_2. Свойства символов

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

Кроме статических методов, у класса char есть и динамические методы. Большинство из них — это методы родительского класса object, унаследованные и переопределенные в классе char. Из собственных динамических методов стоит отметить метод CompareTo, позволяющий проводить сравнение символов. Он отличается от метода Equal тем, что для несовпадающих символов выдает «расстояние» между символами в соответствии с их упорядоченностью в кодировке Unicode.

Класс char[] – массив символов

В языке C# определен класс char[], и его можно использовать для представления строк постоянной длины, как это делается в С++. Более того, поскольку массивы в C# динамические, то расширяется класс задач, в которых можно использовать массивы символов для представления строк. Так что имеет смысл разобраться, насколько хорошо C# поддерживает работу с таким представлением строк.

Массив char[] – это обычный массив, элементы которого являются символами.  Массив символов можно преобразовать в строку, можно выполнить и обратное преобразование. У класса string есть конструктор, которому в качестве аргументов можно передать массив символов. У класса string есть динамический метод ToCharArray, преобразующий строку в массив символов.

Класс char[], как и всякий класс-массив в C#, является наследником не только класса object, но и класса Array. Некоторые методы класса Array можно рассматривать как операции над строками. Например, метод Copy дает возможность выделять и заменять подстроку в теле строки. Методы IndexOf, LastIndexOf позволяют определить индексы первого и последнего вхождения в строку некоторого символа. К сожалению, их нельзя использовать для более интересной операции – нахождения индекса вхождения подстроки в строку. При необходимости такую процедуру можно написать самому. Вот как она выглядит:

int IndexOfStr( char[]s1, char[] s2)

{

//возвращает индекс первого вхождения подстроки s2 в строку s1

int i =0, j=0, n=s1.Length-s2.Length; bool found = false;

while( (i<=n) && !found)

{

j = Array.IndexOf(s1,s2[0],i);

if (j <= n)

{

found=true; int k = 0;

while ((k < s2.Length)&& found)

{

found =char.Equals(s1[k+j],s2[k]); k++;

}

}

i=j+1;

}

if(found) return(j); else return(-1);

}//IndexOfStr

В реализации используется метод IndexOf класса Array, позволяющий найти начало совпадения строк, после чего проверяется совпадение остальных символов. Реализованный здесь алгоритм является самым очевидным, но не самым эффективным.

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

/// <summary>

/// Строки и массивы символов

/// </summary>

public void TestCharArray()

{

const string STROKA = «Строка «;

const string HAS = » содержит подстроку «;

const string NO = «не «;

string source = «Петроград», pattern = «рад»;

char[] sour = source.ToCharArray();

char[] pat = pattern.ToCharArray();

int first = SymAndStr.IndexOfStr(sour, pat);

if ( first >= 0)

Console.WriteLine(STROKA + source +

HAS + pattern);

else

Console.WriteLine(STROKA + source + NO +

HAS + pattern);

string word = new string(sour, first — 1, 4);

Console.WriteLine(word);

}

Существует ли в C# строки типа char*

В языке C# указатели допускаются в блоках, отмеченных как небезопасные. Теоретически в таких блоках можно объявить переменную типа char*, рассматривая ее как строку.  В C# строки типа char* использовать не рекомендуется.

Класс String

Основным типом при работе со строками является тип string, задающий строки переменной длины. Класс string в языке C# относится к ссылочным типам. Над строками – объектами этого класса — определен широкий набор операций, соответствующий современному представлению о том, как должен быть устроен строковый тип.

Объявление строк. Конструкторы класса string

Объекты класса string объявляются как все прочие объекты простых типов – с явной или отложенной инициализацией, с явным или неявным вызовом конструктора класса. Чаще всего, при объявлении строковой переменной конструктор явно не вызывается, а инициализация задается строковой константой. Но у класса string достаточно много конструкторов. Они позволяют сконструировать строку из:

  • символа, повторенного заданное число раз;
  • массива символов char[];
  • части массива символов.

Некоторым конструкторам в качестве параметра инициализации можно передать строку, заданную типом char*. Но все это небезопасно, и подобные примеры приводиться и обсуждаться не будут. Приведу примеры объявления строк с вызовом разных конструкторов:

public void TestDeclStrings()

{

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

string world = «Мир»;

//string s1 = new string(«s1″);

//string s2 = new string();

string sssss = new string(‘s’,5);

char[] yes = «Yes».ToCharArray();

string stryes = new string(yes);

string strye = new string(yes,0,2);

Console.WriteLine(«world = {0}; sssss={1}; stryes={2};»+

» strye= {3}», world, sssss, stryes, strye);

}

Объект world создан без явного вызова конструктора, а объекты sssss, stryes, strye созданы разными конструкторами класса string. Заметьте, не допускается явный вызов конструктора по умолчанию – конструктора без параметров. Нет также конструктора, которому в качестве аргумента можно передать обычную строковую константу. Соответствующие операторы в тексте закомментированы.

Операции над строками

Над строками определены следующие операции:

  • присваивание (=);
  • две операции проверки эквивалентности (= =) и (!=);
  • конкатенация или сцепление строк (+);
  • взятие индекса ([]).

Начну с присваивания. Поскольку string — это ссылочный тип, то в результате присваивания создается ссылка на константную строку, хранимую в «куче». С одной и той же строкой в «куче» может быть связано несколько переменных строкового типа. Эти переменные являются синонимами – разными именами одного и того же объекта, разделяя общую память.

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

Бинарная операция “+” сцепляет две строки, приписывая вторую строку к хвосту первой.

Возможность взятия индекса при работе со строками отражает тот приятный факт, что строку можно рассматривать как массив и получать без труда каждый ее символ. Каждый символ строки имеет тип char, он доступен только для чтения, но не для записи.

Вот пример, в котором над строками выполняются данные операции:

/// <summary>

/// Операции над строками

/// </summary>

public void TestOpers()

{

const string DEL = «->»;

string s1 = «ABC», s2 = «CDE»;

string s3 = s1 + s2;

string s4 = s3.Substring(0, 3);

bool b1 = (s1 == s4);

char ch1 = s1[2];

Console.WriteLine(s1 + DEL + s2 + DEL + s3 +

DEL + b1.ToString() + DEL + ch1.ToString());

}

Строковые константы

Без констант не обойтись. В C# существуют два вида строковых констант:

  • обычные константы, которые представляют строку символов, заключенную в кавычки;
  • @-константы, заданные обычной константой c предшествующим знаком @.

В обычных константах некоторые символы интерпретируются особым образом. Связано это, прежде всего, с тем, что необходимо уметь задавать в строке непечатаемые символы, такие, как, например, символ табуляции. Возникает необходимость задавать символы в виде escape-последовательностей. Для всех этих целей используется комбинация символов, начинающаяся символом “\” – обратная косая черта. Так, пары символов: “\n”, “\t”, “\\”, “\”” задают соответственно символ перехода на новую строку, символ табуляции, сам символ обратной косой черты, символ кавычки, вставляемый в строку, но не сигнализирующий о ее окончании. Комбинация “\xNNNN” задает символ, определяемый шестнадцатеричным кодом NNNN. Хотя такое решение возникающих проблем совершенно естественно, иногда возникают неудобства: например, при задании констант, определяющих путь к файлу, приходится каждый раз удваивать символ обратной косой черты. Это одна из причин, по которой появились @-константы.

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

/// <summary>

/// Два вида констант

/// </summary>

public void TestConstants()

{

string s1 = «\x50″;

string s2 = @»\x50″»";

bool b1 = (s1 == s2);

Console.WriteLine(«s1={0}, s2={1}, b1={2}»,

s1, s2, b1);

s1 = «c:\\c#book\\ch5\\chapter5.doc»;

s2 = @»c:\c#book\ch5\chapter5.doc»;

b1 = (s1 == s2);

Console.WriteLine(«s1={0}, s2={1}, b1={2}»,

s1, s2, b1);

s1 = «\»A\»";

s2 = @»"»A»"»;

b1 = (s1 == s2);

Console.WriteLine(«s1={0}, s2={1}, b1={2}»,

s1, s2, b1);

 

}

Первая проверка эквивалентности строк в этом примере даст знаение False, остальные – True.

Неизменяемый класс string

В языке C# существует понятие неизменяемый (immutable) класс. Для такого класса невозможно изменить значение объекта. Методы могут создавать новый объект на основе существующего, но не могут изменить значение существующего объекта.

К таким неизменяемым классам относится и класс string. Ни один из методов этого класса не меняет значения существующих объектов. Когда метод изменяет строку, то результатом является новая строка – новый объект в куче. Невозможность изменять значения строк касается не только методов. Аналогично, при работе со строкой как с массивом разрешено только чтение отдельных символов, но не их замена. Оператор присваивания, в котором делается попытка изменить первый символ строки, не допустим, а потому закомментирован:

//Неизменяемые значения

s1= «Zenon»; ch1 = s1[0];

//s1[0]=’L';

По какой причине на класс string наложены такие строгие ограничения?  Цель благая. Хотя класс string по целому ряду причин целесообразно отнести к ссылочным типам, но для переменных этого типа хотелось бы иметь ту же семантику, что и для переменных арифметического типа, полагая, что каждая переменная имеет собственную память.  Неизменяемость типа обеспечивает эту семантику. Поясним ситуацию на примере.

/// <summary>

/// String — неизменяемый тип данных!

/// </summary>

public void TestUnchanged()

{

string s1 = «Zenon»;

string s2 = s1;

Console.WriteLine( «s1 = » + s1 + «\t s2 = » + s2);

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

s1 = s1.Insert(s1.Length, » — это философ!»);

Console.WriteLine( «s1 = » + s1 + «\t s2 = » + s2);

Теперь в куче два объекта, s1 стала ссылкой на вновь созданный объект, изменение ее значения никак не отразилось на переменной s2.  Переменная s2 также может изменить свое значение, например так:

s2 = s2.Replace(s2[0], ‘L’) + » — это музыкант!»;

Console.WriteLine( «s1 = » + s1 + «\t s2 = » + s2);

}

Строка «Zenon» осталась в куче висячей, без ссылок на нее и является объектом для сборщика мусора. Как видите, невозможность изменять значение строки непосредственно в памяти, где хранится ее значение, гарантирует, что изменение значения строковой переменной никак не отражается на других строковых переменных, что соответствует семантике поведения развернутых типов.

На рис. 7_3 показаны результаты работы метода TestUnchanged.

  Рис. 7_3 Тип string – это неизменяемый тип    

Статические свойства и методы класса string

Таблица 7-1. Статические методы и свойства класса string

Метод Описание

Empty

Возвращается пустая строка. Свойство со статусом read only.

Compare

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

CompareOrdinal

Сравнение двух строк. Метод перегружен. Реализации метода   позволяют сравнивать как строки, так и подстроки. Сравниваются коды символов.

Concat

Конкатенация строк. Метод перегружен, допускает сцепление   произвольного числа строк.

Copy

Создается копия строки.

Format

Выполняет форматирование в соответствии с заданными   спецификациями формата. Ниже приведено более полное описание метода.

Intern, IsIntern

Отыскивается и возвращается ссылка на строку, если таковая   уже хранится во внутреннем пуле данных. Если же строки нет, то первый из   методов добавляет строку во внутренний пул, второй – возвращает null. Методы применяются   обычно тогда, когда строка создается с использованием построителя строк –   класса StringBuilder.

Join

Конкатенация массива строк в единую строку. При конкатенации   между элементами массива вставляются разделители. Операция, заданная методом Join, является обратной к   операции, заданной методом Split.   Последний является динамическим методом и, используя разделители,   осуществляет разделение строки на элементы.

Метод Format

Метод Format в наших примерах встречался многократно. Всякий раз, когда выполнялся вывод результатов на консоль, неявно вызывался и метод Format. Рассмотрим оператор печати:

Console.WriteLine(«s1={0}, s2={1}», s1,s2);

Здесь строка, задающая первый аргумент метода, помимо обычных символов содержит форматы, заключенные в фигурные скобки, и, как следствие, автоматически вызывается метод Format, форматирующий строку перед выдачей ее на печать. В данном примере используется простейший вид формата, — он определяет объект, который должен быть подставлен в участок строки, занятый данным форматом. Помимо неявных вызовов метода Format, нередко возникает необходимость явного форматирования строки.

Давайте рассмотрим общий синтаксис метода Format и используемых в нем форматов. Метод Format, как и большинство методов, является перегруженным и может вызываться с разным числом параметров. Первый необязательный параметр метода задает провайдера, определяющего национальные особенности, которые используются в процессе форматирования. В качестве такого параметра должен быть задан объект, реализующий интерфейс System.IFormatProvider. Если этот параметр не задан, то используется культура, заданная по умолчанию. Вот примеры сигнатуры двух реализаций этого метода:

public static string Format(IFormatProvider, string, object);

public static string Format(string, params object[]);

Параметр типа string задает форматируемую строку. Заданная строка содержит один или несколько форматов, составляющих список форматов. Признаком формата в строке являются фигурные скобки, окружающие формат. Списку форматов ставится в соответствие список объектов, следующий за форматируемой строкой. Чаще всего, оба списка имеют одинаковую длину, но это не обязательное требование, поскольку один и тот же объект может по-разному форматироваться. Каждый формат однозначно определяет объект из списка объектов. Этот объект преобразуется в строку текста, текст форматируется в соответствии с параметрами, задаваемыми форматом и подставляется в то место строки, где расположен формат. Так что форматы в строке – это держатели места (placeholder), куда подставляется форматируемый текст. Метод Format в качестве результата возвращает переданную ему строку, где все форматы заменены строками, полученными в результате форматирования объектов.

Общий синтаксис, специфицирующий формат, таков:

{N [,M [:<коды_форматирования>]]}

Обязательный параметр N задает индекс объекта в списке объектов. Индексация объектов начинается с нуля, как это принято в массивах.

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

Третий необязательный параметр задает коды форматирования, указывающие, как следует форматировать объект. Применяются разные коды форматирования для числовых данных, дат, перечислений. Например, для числовых данных код C (currency) говорит о том, что параметр должен форматироваться как валюта с учетом национальных особенностей представления. Код P (percent) задает форматирование в виде процентов с точностью до сотой доли. Код F для дат позволяет вывести в полном формате дату и время. Полный набор кодов форматирования можно посмотреть в справочной системе. Частично их эффект демонстрируется в данном примере:

enum Rainbow {красный, желтый, голубой};

/// <summary>

/// Форматирование чисел, дат, перечислений

/// </summary>

public void TestFormat()

{

int x = 77;

double p = 0.52;

double d = -151.17;

DateTime today = DateTime.Now;

//Форматирование чисел

string s =
string.Format(«Итого:{0:P}\n» +

«Сумма_1 = {1:C}\n» +

«x = {1:#######} рублей\n» +

«d = {2,-10:F} рублей\n» +

«d = {2, 10:F} рублей\n» +

«d = {2:E}\n», p, x, d);

Console.WriteLine(s);

//Форматирование дат

s = string.Format(«Время: {0:t}, Дата: {0:d}\n» +

«Дата и время — {0:F}», today);

Console.WriteLine(s);

//Форматирование перечислений

s = string.Format(«Цвет1: {0:G}, Цвет2: {1:F}\n»,

Rainbow.голубой, Rainbow.красный);

Console.WriteLine(s);

//Национальные особенности

System.Globalization.CultureInfo ci =

new System.Globalization.CultureInfo(«en-US»);

s = string.Format(ci, «Итого:{0,4:C} «, 77.77);

Console.WriteLine(s);

}//TestFormat

Приведу некоторые комментарии к этой процедуре. Заметьте, консольный вывод всегда можно свести к форме Console.WriteLine(s), если строку s предварительно отформатировать, используя явный вызов метода Format.   Этот метод полезно вызывать и в Windows проектах при выводе специфических данных – денежных сумм, процентов, дат и времени. В примере показано использование различных спецификаций формата с разными кодами форматирования для таких данных. В заключительном фрагменте кода  демонстрируется задание провайдером национальных особенностей. С этой целью создается объект класса CultureInfo, инициализированный так, чтобы он задавал особенности форматирования, принятые в США. Заметьте, класс CultureInfo наследует интерфейс IFormatProvider. Российские национальные особенности форматирования установлены по умолчанию. При необходимости их можно установить таким же образом, как это сделано для США, задав соответственно константу “ru-RU”. Результаты работы метода показаны на рис. 7_4:

Рис. 7_4 Результаты работы метода Format

Методы Join и Split

Методы Join и Split выполняют над строкой текста взаимно обратные преобразования. Динамический метод Split позволяет осуществить разбор текста на элементы. Статический метод Join выполняет обратную операцию, собирая строку из элементов.

Заданный строкой текст зачастую представляет собой совокупность структурированных элементов – абзацев, предложений, слов, скобочных выражений и т.д. При работе с таким текстом необходимо разделить его на элементы, пользуясь специальными разделителями элементов, – это могут быть пробелы, скобки, знаки препинания. Практически подобные задачи возникают постоянно при работе со структурированными текстами. Методы Split и Join облегчают решение этих задач.

Динамический метод Split, как обычно, перегружен. Наиболее часто используемая реализация имеет следующий синтаксис:

public string[]Split(params char[])

На вход методу Split передается один или несколько символов, интерпретируемых как разделители. Объект string, вызвавший метод, разделяется на подстроки, ограниченные этими разделителями. Из этих подстрок создается массив, возвращаемый в качестве результата метода.

Синтаксис статического метода Join таков:

public static string Join(string delimiters, string[] items )

В качестве результата метод возвращает строку, полученную конкатенацией элементов массива items, между которыми вставляется строка разделителей delimiters. Как правило, строка delimiters состоит из одного символа, который и разделяет в результирующей строке элементы массива items; но в отдельных случаях ограничителем может быть строка из нескольких символов, например запятая и следующий за  ней пробел.

Рассмотрим примеры применения этих методов. В первом из них строка представляет сложноподчиненное предложение, которое разбивается на простые предложения. Во втором предложение разделяется на слова. Затем производится обратная сборка разобранного текста. Вот код соответствующей процедуры:

/// <summary>

/// Разборка и сборка текстов

/// </summary>

public void TestSplitAndJoin()

{

string txt = «А это пшеница, которая в темном чулане хранится,» +

» в доме, который построил Джек!»;

Console.WriteLine(«txt={0}», txt);

Console.WriteLine(«Разделение текста на простые предложения:»);

string[] SimpleSentences, Words;

//размерность массивов SimpleSentences и Words устанавливается

// автоматически в соответствии с размерностью массива,

//возвращаемого методом Split

SimpleSentences = txt.Split(‘,’);

for (int i = 0; i < SimpleSentences.Length; i++)

Console.WriteLine(«SimpleSentences[{0}]= {1}»,

i, SimpleSentences[i]);

string txtjoin = string.Join(«,», SimpleSentences);

Console.WriteLine(«txtjoin={0}», txtjoin);

Words = txt.Split(‘ ‘);

for (int i = 0; i < Words.Length; i++)

Console.WriteLine(«Words[{0}]= {1}», i, Words[i]);

txtjoin = string.Join(» «, Words);

Console.WriteLine(«txtjoin={0}», txtjoin);

}//TestSplitAndJoin

Взгляните на результаты выполнения этой процедуры:

Рис. 7_5. Разбор и сборка строки текста

Обратите внимание, что методы Split и Join хорошо работают, когда при разборе используется только один разделитель. В этом случае сборка действительно является обратной операцией и позволяет восстановить исходную строку. Если же при разборе задается некоторое множество разделителей, то возникают две проблемы:

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

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

Динамические методы класса string

Операции, разрешенные над строками в C#, разнообразны. Методы этого класса позволяют выполнять основные типичные операции — вставку, удаление, замену строк, поиск вхождения подстроки в строку. Класс string наследует методы класса object, частично их переопределяя. Класс string наследует и, следовательно, реализует методы четырех интерфейсов: ICompareable, ICloneable, IConvertible, IEnumerable.

Рассмотрим наиболее характерные методы при работе со строками.

Таблица 14-2. Динамические методы и свойства класса string

Метод Описание

Insert

Вставляет подстроку в заданную позицию.

Remove

Удаляет подстроку в заданной позиции.

Replace

Заменяет подстроку в заданной позиции на новую подстроку.

Substring

Выделяет подстроку в заданной позиции.

IndexOf,   IndexOfAny,

LastIndexOf,   LastIndexOfAny

Определяются индексы первого и последнего вхождения заданной   подстроки или любого символа из заданного набора

StartsWith, EndsWith

Возвращается true или false, в зависимости от того,   начинается или заканчивается строка заданной подстрокой.

PadLeft, PadRight

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

Trim, TrimStart,   TrimEnd

Обратные операции к методам Pad. Удаляются пробелы в начале   и в конце строки, или только с одного ее конца.

ToCharArray

Преобразование строки в массив символов.

Сводка методов, приведенная в таблице, дает достаточно полную картину широких возможностей, имеющихся при работе со строками в C#. Следует помнить, что класс string является неизменяемым. Поэтому Replace, Insert и другие методы, изменяющие строку, представляют собой функции, возвращающие в качестве результата новую строку.

Класс StringBuilder – построитель строк

Класс string не разрешает изменять существующие объекты. Строковый класс StringBuilder позволяет компенсировать этот недостаток. Этот класс принадлежит к изменяемым классам и его можно найти в пространстве имен System.Text. Рассмотрим класс StringBuilder подробнее.

Объявление строк. Конструкторы класса StringBuilder

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

  • public StringBuilder(string str, int cap); Параметр str задает строку инициализации, cap – емкость объекта;
  • public StringBuilder(int curcap, int maxcap); Параметры curcap и maxcap задают начальную и максимальную емкость объекта;
  • public StringBuilder(string str, int start, int len, int cap); Параметры str, start, len задают строку инициализации, cap – емкость объекта.

Операции над строками

Над строками этого класса определены практически те же операции, что и над строками класса string:

  • присваивание (=);
  • две операции проверки эквивалентности (= =) и (!=);
  • взятие индекса ([]).

 

Операция конкатенации (+) не определена над строками класса StringBuilder, ее роль играет метод Append, дописывающий новую строку в хвост уже существующей. Семантика операций частично изменилась. Присваивание для строк этого класса является полноценным ссылочным присваиванием, так что изменение значения строки сказывается на всех экземплярах, ссылающихся на строку в динамической памяти. Эквивалентность теперь является проверкой ссылок, а не значений. Со строкой этого класса можно работать как с массивом, но, в отличие от класса string, здесь уже все делается как надо: допускается не только чтение отдельного символа, но и его изменение. Рассмотрим уже знакомый пример работы со строками, используя теперь строки класса StringBuilder:

/// <summary>

/// Операции над строками StringBuilder

/// </summary>

public void TestStringBuilder()

{

string DEL = «->»;

StringBuilder s1 = new StringBuilder(«ABC»),

s2 = new StringBuilder(«CDE»);

StringBuilder s3 = s2.Insert(0,s1.ToString());

s3.Remove(3, 3);

bool b1 = (s1 == s3);

char ch1 = s1[2];

string s = s1.ToString() + DEL + s2.ToString() +

DEL + s3.ToString() + DEL +

b1.ToString() + DEL + ch1.ToString();

Console.WriteLine(s);

 

s2.Replace(«ABC», «Zenon»);

s1 = s2;

s2[0] = ‘L’;

s1.Append(» — это музыкант!»);

Console.WriteLine(s1.ToString() +

» -> » + s2.ToString());

}

Результаты работы этого метода показаны на рис. 7_6.

Рис. 7_6 Тип StringBuilder – это изменяемый тип    

Этот пример демонстрирует возможность выполнения над строками класса StringBuilder тех же операций, что и над строками класса string. Обратите внимание, теперь методы, изменяющие строку, Replace, Insert, Remove, Append реализованы как процедуры, а не как функции. Они изменяют значение строки непосредственно в буфере, отводимом для хранения строки.  Появляется новая возможность – изменять отдельные символы строки.

Основные методы

У класса StringBuilder методов значительно меньше, чем у класса string. Это и понятно, класс создавался с целью дать возможность изменять значение строки. По этой причине у класса есть основные методы, позволяющие выполнять такие операции над строкой, как вставка, удаление и замена подстрок, но нет методов, подобных поиску вхождения, которые можно выполнять над обычными строками. Технология работы обычно такова: создается обычная строка; из нее конструируется строка класса StringBuilder; выполняются операции, требующие изменение значения; полученная строка преобразуется в строку класса string; над этой строкой выполняются операции, не требующие изменения значения строки.

Давайте чуть более подробно рассмотрим основные методы класса StringBuilder:

  • public StringBuilder Append(<объект>); К строке, вызвавшей метод, присоединяется строка, полученная из объекта, который передан методу в качестве параметра. Метод перегружен и может принимать на входе объекты всех простых типов, начиная от char и bool до string и long. Поскольку объекты всех этих типов имеют метод ToString,  всегда есть возможность преобразовать объект в строку, которая и присоединяется к исходной строке. В качестве результата возвращается ссылка на объект, вызвавший метод. Поскольку возвращаемую ссылку ничему присваивать не нужно, то правильнее считать, что метод изменяет значение строки;
  • public StringBuilder Insert(int location,<объект>); Метод вставляет строку, полученную из объекта, в позицию, указанную параметром location. Метод Append является частным случаем метода Insert;
  • public StringBuilder Remove(int start, int len); Метод удаляет подстроку длины len, начинающуюся с позиции start;
  • public StringBuilder Replace(string str1,string str2); Все вхождения подстроки str1 заменяются на строку str2;
  • public StringBuilder AppendFormat(<строка форматов>, <объекты>); Метод является комбинацией метода Format класса string и метода Append. Строка форматов, переданная методу, содержит только спецификации форматов. В соответствии с этими спецификациями находятся и форматируются объекты. Полученные в результате форматирования строки присоединяются в конец исходной строки.

За исключением метода Remove, все рассмотренные методы являются перегруженными. В представленном описании приведен основной вариант вызова метода, не отражающий точный синтаксис всех перегруженных реализаций.

Емкость буфера

Каждый экземпляр строки класса StringBuilder имеет буфер, в котором хранится строка. Объем буфера – его емкость — может меняться в процессе работы со строкой. Объекты класса имеют две характеристики емкости – текущую и максимальную.  В процессе работы текущая емкость изменяется, естественно, в пределах максимальной емкости, которая реально достаточно высока. Если размер строки увеличивается, то соответственно автоматически растет и текущая емкость. Если же размер строки уменьшается, то емкость буфера остается на том же уровне. По этой причине иногда разумно уменьшать емкость. Следует помнить, что попытка уменьшить емкость до величины, меньшей длины строки, приведет к ошибке.

У класса StringBuilder имеется 2 свойства и один метод, позволяющие анализировать и управлять емкостными свойствами буфера. Напомню, что этими характеристиками можно управлять также еще на этапе создания объекта, – для этого имеется соответствующий конструктор. Рассмотрим свойства и метод класса, связанные с емкостью буфера:

  • свойство Capacity – возвращает или устанавливает текущую емкость буфера;
  • свойство MaxCapacity – возвращает максимальную емкость буфера. Результат один и тот же для всех экземпляров класса;
  • метод int EnsureCapacity(int capacity) – позволяет убедиться, что емкость буфера не меньше емкости, заданной параметром capacity; если текущая емкость меньше, то она увеличивается до значения capacity, иначе не изменяется. Максимум текущей емкости и capacity возвращается в качестве результата работы метода.

Приведу код, в котором проводятся различные эксперименты с емкостью буфера:

/// <summary>

/// Анализ емкости буфера

/// </summary>

public void TestCapacity()

{

string txt = «А это пшеница, которая в темном чулане хранится,» +

» в доме, который построил Джек!»;

string str = «А роза упала на лапу Азора»;

StringBuilder strbuild = new StringBuilder(100, 1000);

StringBuilder txtbuild = new StringBuilder(txt);

strbuild.Append(str);

//Емкость буфера

Console.WriteLine(«strbuild: емкость буфера = {0}, » +

«максимальная емкость = {1}»,

strbuild.Capacity, strbuild.MaxCapacity);

Console.WriteLine(«txtbuild: емкость буфера = {0}, » +

«максимальная емкость = {1}»,

txtbuild.Capacity, txtbuild.MaxCapacity);

//Изменение емкости

//Ошибка периода выполнения!

//попытка установить емкость меньше длины строки

//txtbuild.Capacity = 75;

int sure = txtbuild.EnsureCapacity(75);

Console.WriteLine(«sure= {0}», sure);

// увеличим строку за пределы буфера

// емкость автоматически увеличится!

txtbuild.Append(txtbuild.ToString());

Console.WriteLine(«txtbuild: емкость буфера = {0}»,

txtbuild.Capacity);

}

В этом фрагменте кода анализируются и изменятся емкостные свойства буфера двух объектов. Демонстрируется, как меняется емкость при работе с объектами. Результаты работы этого фрагмента кода показаны на рис. 7_7:

Рис. 7_7. Анализ емкостных свойств буфера

Архитектура Решения

Как обычно, для демонстрации примеров данной главы построено Решение с именем главы  Ch7. В Решение включены три проекта. Проект DLL с именем SearchAndSorting содержит два сервисных класса Service<T> и SortService<T>, методы которых реализуют алгоритмы поиска по образцу и сортировки массивов.  Проект Windows с именем SearchAndSort имеет традиционную архитектуру с главной кнопочной формой. Два интерфейсных класса FormSearch и FormSorting обеспечивают интерфейс пользователя, позволяющий анализировать методы поиска и сортировки из DLL, подключенной к проекту.  Консольный проект SymbolsAndStrings  содержит класс Testing, большое число методов которого представляют собой различные тесты , иллюстрирующие работу со строками и символами. К этому проекту также подключена DLL, так что часть тестов позволяет работать с методами поиска и сортировки в консольном варианте.

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

Классы построенной DLL являются универсальными классами с параметрами. Такие классы будут подробно рассматриваться в последующих главах курса. Возможно, не совсем корректно по отношению к читателю использовать в примерах еще не описанный инструментарий. Но выбирая между методичностью изложения и примерами, с самого начала демонстрирующими возможности языка и стиль программирования, я склоняюсь в пользу примеров.

Алгоритмы и задачи

Вначале было слово.

Так говорит история человечества. В истории компьютеров вначале было число. Долгое время вместо термина «компьютер» использовались аббревиатуры «ЭВМ» (Электронная Вычислительная Машина) и «ЦВМ» (Цифровая Вычислительная Машина), что подчеркивало цифровую сущность первых компьютеров. И использовались они тогда в отраслях, связанных с военными применениями, в зарождающейся космической отрасли, в физике, — в тех областях, где господствовала цифра. Тогда в почете были физики, а не лирики с их, казалось бы, ненужными текстами.

В первых языках программирования – Фортране и Алголе практически отсутствовали средства представления текстовой  информации и работы с ней. В сборнике упражнений по Алголу [9], подготовленном на факультете ВМК МГУ и вышедшем в 1975 году, нет ни одного упражнения по работе с текстовой информацией, все упражнения предназначены для работы с числами. Приведу еще цитату из книги [8], вышедшей у нас в 1980 году и посвященной обзору расплодившихся тогда языков программирования: «Можно сказать, что для «научных» языков программирования характерно полное или почти полное отсутствие средств для работы со строками литер».

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

Широкое применение компьютеров не только в инженерных дисциплинах, но и в бизнесе, также способствовало развитию  работы с текстовыми документами.

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

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

Интернет далеко не единственная область, где подобные алгоритмы играют важнейшую роль. Молекулярная биология (и ее раздел — биоинформатика) является сегодня бурно развивающейся  научной областью. Как ни странно, а может быть вполне естественно, что при анализе структур ДНК и РНК, при расшифровке генома человека работа с текстами играет определяющую роль. В книге Дэна Гансфилда [Строки], подробно рассматриваются алгоритмы работы с текстами, как необходимый инструментарий решения задач вычислительной биологии. Приведу из нее некоторые цитаты, поясняющие, как биологическая информация представляется в виде текста: «Можно получить биологически осмысленные результаты, рассматривая ДНК как одномерную строку символов”. Аналогичное, но более сильное предположение делается и о белках. Информация, которая лежит за биохимией, клеточной биологией, может быть представлена обычной строкой, составленной из 4-х символов G, А, Т и С. Для биологии организмов эта строка является исходной структурой данных.

Для работы с текстами на языке C# библиотека классов FCL предлагает целый набор  разнообразных классов, сосредоточенных в разных пространствах имен этой библиотеки. Классы для работы с текстами находятся как в основном пространстве имен System, так и в пространствах System.Text и System.Text.RegularExpression.

Классы C#, используемые для представления строк – char,  сhar[], string, StringBuilder, связаны между собой, и из объекта одного класса нетрудно получить объект другого класса. Конструктору класса string можно передать массив символов, создав тем самым объект класса string. Для обратного преобразования из string в char[] следует вызвать метод ToCharArray, которым обладают объекты класса string. Достаточно вызвать метод ToString объекта StringBuilder для преобразования объекта класса StringBuilder  в объект класса string. Обратное преобразование можно выполнить, передавая конструктору класса StringBuilder  объект string.

Задачи

  1. Напишите процедуру, подсчитывающую частоту использования группы символов в заданном тексте. Проведите исследование произведений двух поэтов, подсчитав частоты использования гласных и согласных, глухих и звонких согласных. Для представления текстов используйте класс char [].
  2. Напишите процедуру, подсчитывающую частоту использования группы символов в заданном тексте. Проведите исследование произведений двух поэтов, подсчитав частоты использования частоты использования гласных и согласных, глухих и звонких согласных. Для представления текстов используйте класс string.
  3. Напишите процедуру, подсчитывающую частоту использования группы символов в заданном тексте. Проведите исследование произведений двух поэтов, подсчитав частоты использования частоты использования гласных и согласных, глухих и звонких согласных. Для представления текстов используйте класс StringBuilder.
  4. Напишите процедуру, разделяющую исходный текст на предложения.  Для представления текстов используйте класс char [].
  5. Напишите процедуру, разделяющую исходный текст на предложения.  Для представления текстов используйте класс string.
  6. Напишите процедуру, разделяющую исходный текст на предложения.  Для представления текстов используйте класс StringBuilder.
  7. Исходный текст представляет собой предложение. Напишите процедуру, разделяющую исходный текст на слова.  Для представления текстов используйте класс char[].
  8. Исходный текст представляет собой предложение. Напишите процедуру, разделяющую исходный текст на слова.  Для представления текстов используйте класс string.
  9. Исходный текст представляет собой предложение. Напишите процедуру, разделяющую исходный текст на слова.  Для представления текстов используйте класс StringBuilder.
  10. Напишите процедуру IsIder, проверяющую является ли исходный текст правильно построенным идентификатором. Для представления текста используйте класс char [].
  11. Напишите процедуру IsIder, проверяющую является ли исходный текст правильно построенным идентификатором. Для представления текста используйте класс string.
  12. Напишите процедуру IsIder, проверяющую является ли исходный текст правильно построенным идентификатором. Для представления текста используйте класс StringBuilder.
  13. Напишите процедуру IsInt, проверяющую является ли исходный текст правильно построенным целым числом. Для представления текста используйте класс char [].
  14. Напишите процедуру IsInt, проверяющую является ли исходный текст правильно построенным целым числом. Для представления текста используйте класс string.
  15. Напишите процедуру IsInt, проверяющую является ли исходный текст правильно построенным целым числом. Для представления текста используйте класс StringBuilder.
  16. Напишите процедуру IsFloat, проверяющую является ли исходный текст правильно построенным числом с плавающей точкой. Для представления текста используйте класс char [].
  17. Напишите процедуру IsFloat, проверяющую является ли исходный текст правильно построенным числом с плавающей точкой. Для представления текста используйте класс string.
  18. Напишите процедуру IsFloat, проверяющую является ли исходный текст правильно построенным числом с плавающей точкой. Для представления текста используйте класс StringBuilder.
  19. Напишите процедуру IsNumber, проверяющую является ли исходный текст правильно построенным числом. Для представления текста используйте класс char [].
  20. Напишите процедуру IsNumber, проверяющую является ли исходный текст правильно построенным числом. Для представления текста используйте класс string.
  21. Напишите процедуру IsNumber, проверяющую является ли исходный текст правильно построенным числом. Для представления текста используйте класс StringBuilder.
  22. Исходный текст представляет описание класса на C#. Напишите процедуру, выделяющую из этого текста заголовки методов класса с предшествующими им тегами  summary. Для представления текстов используйте класс char [].
  23. Исходный текст представляет описание класса на C#. Напишите процедуру, выделяющую из этого текста заголовки методов класса с предшествующими им тегами  summary. Для представления текстов используйте класс string.
  24. Исходный текст представляет описание класса на C#. Напишите процедуру, выделяющую из этого текста заголовки методов класса с предшествующими им тегами  summary. Для представления текстов используйте класс StringBuilder.
  25. Исходный текст представляет описание класса на C#. Напишите процедуру, удаляющую из этого текста теги summary и комментарии. Для представления текстов используйте класс char [].
  26. Исходный текст представляет описание класса на C#. Напишите процедуру, удаляющую из этого текста теги summary и комментарии. Для представления текстов используйте класс string.
  27. Исходный текст представляет описание класса на C#. Напишите процедуру, удаляющую из этого текста теги summary и комментарии. Для представления текстов используйте класс StringBuilder.
  28. Исходный текст представляет описание класса на C#. Напишите процедуру, создающую массив строк, каждая из которых содержит описание одного из методов класса. Для представления текстов используйте класс char [].
  29. Исходный текст представляет описание класса на C#. Напишите процедуру, создающую массив строк, каждая из которых содержит описание одного из методов класса. Для представления текстов используйте класс string.
  30. Исходный текст представляет описание класса на C#. Напишите процедуру, создающую массив строк, каждая из которых содержит описание одного из методов класса. Для представления текстов используйте класс StringBuilder.
  31. Исходный текст представляет описание класса на C#. Напишите процедуру, создающую массив строк, каждая из которых содержит описание одного из полей класса. Для представления текстов используйте класс char [].
  32. Исходный текст представляет описание класса на C#. Напишите процедуру, создающую массив строк, каждая из которых содержит описание одного из полей класса. Для представления текстов используйте класс string.
  33. Исходный текст представляет описание класса на C#. Напишите процедуру, создающую массив строк, каждая из которых содержит описание одного из полей класса. Для представления текстов используйте класс StringBuilder.
  34. Исходный текст задает оператор языка C#. Напишите процедуру, определяющую тип оператора. Для представления текстов используйте класс char [].
  35. Исходный текст задает оператор языка C#. Напишите процедуру, определяющую тип оператора. Для представления текстов используйте класс string.
  36. Исходный текст задает оператор языка C#. Напишите процедуру, определяющую тип оператора. Для представления текстов используйте класс StringBuilder.
  37. Напишите процедуру «Строгий Палиндром», определяющую является ли заданный текст палиндромом. Напомню, палиндромом называется симметричный текст, одинаково читаемый как слева направо, так и справа налево.
  38. Напишите процедуру «Палиндром», определяющую является ли заданный текст палиндромом. При анализе текста:
    - пробелы не учитываются;
    - регистр не учитывается;
    - буквы «е» и «ё», «и» и «й» считаются одинаковыми.
    Фраза, которую Мальвина диктовала Буратино, — «А роза упала на лапу Азора» считается палиндромом.
  39. Напишите процедуру «Слог», разбивающую слово на слоги. Предложите свой алгоритм. За основу возьмите следующие правила:
    - две подряд идущие гласные рассматриваются как одна гласная;
    - число слогов определяется числом гласных букв (с учетом предыдущего правила);
    - Если n – число согласных между двумя соседними гласными, то n/2 согласных относятся к предыдущему слогу, а оставшиеся к следующему. Вот примеры нескольких разбиений в соответствии с этим алгоритмом: «слог», «сло — во», «прог — ноз», «транс – крип — ция», «зоо – ма – га – зин».

Проекты

  1. Создайте класс CharArray для представления строк и интерфейс для работы с ним. Методы класса должны включать набор методов класса string. Внутреннее представление строки должно задаваться массивом символов – char []. Методы, изменяющие размер строки должны реализовываться функциями, как в классе string, создавая новый объект.
  2. Создайте класс CharArray для представления строк и интерфейс для работы с ним. Методы класса должны включать набор методов класса string. Внутреннее представление строки должно задаваться массивом символов – char []. Методы, изменяющие размер строки должны реализовываться процедурами, как в классе StringBuilder.
  3. Создайте класс MyText для работы с текстом. Методы этого класса должны выполнять должны различные операции над текстом. Примеры некоторых операций даны в задачах этого раздела. Операции над текстом должны, например, позволять получать коллекции абзацев, предложений, слов текста, получать абзац, предложение, слово по его номеру, разбивать слово на слоги.
  4. Создайте класс MyProgramText для работы с текстом программ на языке C#. Методы этого класса должны выполнять должны различные операции над текстом программы. Примеры некоторых операций даны в задачах этого раздела.

Поиск и Сортировка

Задачи поиска и сортировки возникают в самых разных контекстах. Рассмотрим задачу поиска в следующей постановке. Дан массив Items c элементами типа (класса) T и элемент pattern типа T, называемый образцом. Необходимо определить, встречается ли образец в массиве и, если да, определить индекс его вхождения.

Задача сортировки состоит в том, чтобы отсортировать массив Items. Предполагается, что тип T является упорядоченным типом, так что его элементы можно сравнивать. Задачу можно конкретизировать, полагая, например, что T – это тип string, и рассматривать поиск и сортировку строковых массивов. Поскольку алгоритмы поиска и сортировки практически не зависят от типа T, то отложим конкретизацию типа настолько, насколько это возможно.

Поиск

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

Линейный поиск

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

Чтобы эта простая задача смотрелась интереснее, рассмотрим параметризованный алгоритм с параметром T, задающим тип элементов, и его реализацию на языке C#. Построим универсальный класс (класс с родовыми параметрами):

public class Service<T> where T:IComparable<T>

{

}

Класс  Service имеет параметр T,  на который наложено ограничение – класс T должен быть наследником интерфейса IComparable, следовательно, должен реализовать метод CompareTo этого интерфейса. Содержательно это означает, что T является упорядоченным классом.

Класс Service будем рассматривать, как сервисный класс, реализованный в виде модуля, предоставляющий клиентским классам некоторые сервисы, в частности возможность осуществлять поиск в массивах любого типа. Добавим в этот класс два статических метода, реализующих алгоритм линейного поиска:

/// <summary>

/// Линейный поиск образца в массиве

/// </summary>

/// <param name=»massiv»>искомый массив</param>

/// <param name=»pattern»>образец поиска</param>

/// <returns>

/// индекс первого элемента, совпадающего с образцом

/// или -1, если образец не встречается в массиве

/// </returns>

public static int SearchPattern(T[] massiv, T pattern)

{

for (int i = 0; i < massiv.Length; i++)

if (massiv[i].CompareTo(pattern)==0) return (i);

return (-1);

}

/// <summary>

/// Вариация линейного поиска образца в массиве

/// </summary>

/// <param name=»massiv»>искомый массив</param>

/// <param name=»pattern»>образец поиска</param>

/// <returns>

/// индекс первого элемента, совпадающего с образцом

/// или -1, если образец не встречается в массиве

/// </returns>

public static int SearchPattern1(T[] massiv, T pattern)

{

int i = 0;

while((i<massiv.Length)&& (massiv[i].CompareTo(pattern)!=0))

i++;

if (i == massiv.Length) return (-1); else return (i);

}

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

Поиск с барьером

Алгоритм линейного поиска можно упростить, избавившись от проверки дополнительного условия, если быть уверенным, что в массиве обязательно присутствует элемент, совпадающий с образцом. Иногда истинность этого условия следует из знания того, как строился массив и образец поиска. Но можно добиться выполнения этого условия принудительно, соорудив в массиве «барьер», препятствующий выходу поиска за границы массива. С этой целью массив расширяется на один элемент и в качестве последнего элемента записывается «барьер» — образец поиска. В этом случае поиск всегда найдет образец. Если образца нет среди «родных» элементов массива, то он встретится в конце в виде «барьера».

Для упрощения больше подходит вторая версия алгоритма линейного поиска. Приведу реализацию этой схемы:

/// <summary>

/// Линейный поиск с барьером

/// Предусловие: В массиве существует элемент,

/// совпадающий с образцом pattern

/// </summary>

/// <param name=»massiv»>искомый массив</param>

/// <param name=»pattern»>образец поиска</param>

/// <returns>

/// индекс первого элемента, совпадающего с образцом

/// </returns>

public static int SearchBarrier(T[] massiv, T pattern)

{

int i = 0;

while (massiv[i].CompareTo(pattern) != 0)

i++;

return (i);

}

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

Бинарный поиск

У этого метода поиска много синонимичных названий – метод деления пополам, двоичный или бинарный поиск, метод дихотомии. Все эти названия отражают тот приятный факт, что в заранее отсортированном  массиве сравнение с одним элементом позволяет вдвое уменьшить число кандидатов. Для этого достаточно сравнить образец с элементом массива, стоящим в середине. Если образец совпадает с этим элементом, то элемент найден и поиск завершается. Если образец меньше срединного элемента, то размеры области поиска сокращаются вдвое — элемент может находиться лишь в первой половине массива. Если образец больше срединного элемента, он находится во второй половине массива. Введение двух параметров – start и finish, задающих границы области поиска, позволяет достаточно просто описать схему алгоритма. Алгоритм бинарного поиска намного эффективнее линейного поиска в особенности для больших массивов. Нетрудно понять, что для отсортированного массива из n элементов он требует не более чем log2(n) сравнений образца с элементами массива. Вот его возможная реализация:

/// <summary>

/// Бинарный поиск образца в упорядоченном массиве

/// Предусловие: Массив упорядочен

/// </summary>

/// <param name=»massiv»>искомый массив</param>

/// <param name=»pattern»>образец поиска</param>

/// <returns>

/// индекс элемента, совпадающего с образцом,

/// но не обязательно индекс первого вхождения,

/// -1, если образец не встречается в массиве

/// </returns>

public static int BinSearch(T[] massiv, T pattern)

{

int start = 0, finish = massiv.Length-1, mid = (start+finish)/2;

while (start <= finish)

{

if (massiv[mid].CompareTo(pattern) == 0) return (mid);

if(massiv[mid].CompareTo(pattern) == 1)

finish = mid-1;

else

start = mid+1;

mid = (start+finish)/2;

}

return(-1);

}

Как клиентский класс может пользоваться сервисами универсального класса Service? Приведу примеры работы с методами класса, когда в качестве клиента выступает класс из консольного проекта и класс из Windows проекта. Начнем с консоли.  Клиент работает с массивом строк класса string. Он предпочитает использовать метод поиска с барьером и сам заботится об организации барьера до вызова метода:

public void TestSearch()

{

string answer = «yes»;

int n;

Console.WriteLine(«Введите n — число элементов массива»);

n = Convert.ToInt32(Console.ReadLine());

string[] ar1 = new string[n + 1];

for (int i = 0; i < n; i++)

{

Console.WriteLine(«Введите строку — элемент» +

» массива с номером {0}», i);

ar1[i] = Console.ReadLine();

}

do

{

string pat1;

Console.WriteLine(«Введите строку — образец поиска»);

pat1 = Console.ReadLine();

ar1[n] = pat1;

//Выполнено условие метода поиска с барьером

int k = Service<string>.SearchBarrier(ar1, pat1);

if (k != n)

Console.WriteLine(«Образец pat1 = {0} найден в массиве!» +

«\nЭто элемент ar[{1}] = {2} «, pat1, k, ar1[k]);

else

Console.WriteLine(«Образец pat1 ={0} не найден!», pat1);

Console.WriteLine(«Продолжим? (yes/no»);

answer = Console.ReadLine();

} while (answer != «no»);

}

На рис. 7_8 показаны результаты работы метода:

Рис. 7.8 Поиск по образцу в консольном проекте

Метод  TestSearch включен в класс Testing консольного проекта SymbolsAndStrings, многократно использованного в предыдущих примерах. К консольному проекту присоединена библиотека классов — DLL с именем, содержащая  универсальный  класс Service<T>. При вызове метода этого класса, реализующего поиск с барьером, задается параметр типа, характеризующий тип элементов массива, в котором ведется поиск:

Service<string>.SearchBarrier(ar1, pat1)

Для проведения более полных экспериментов с методами поиска и проведения сравнения времени работы методов поиска построен Windows проект с именем SearchAndSort, к которому подключена та же библиотека классов SearchAndSorting. Архитектурно новый проект представляет проект с главной кнопочной формой, которая позволяет перейти к анализу методов поиска, либо к анализу методов сортировки, о которых пойдет речь далее. На рис. 7_9 показана форма, обеспечивающая интерфейс, необходимый при исследовании поведения методов поиска по образцу:

Рис. 7_9 Интерфейс, поддерживающий работу с методами поиска

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

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

private void buttonBarierSearch_Click(object sender, EventArgs e)

{

int n = arr.Length — 1;

arr[n] = pattern; //барьер

int result;

result = Service<int>.SearchBarrier(arr, pattern);

if (result != n)

textBoxResult.Text = PATTERN_IS_FOUND + result;

else

textBoxResult.Text = PATTERN_IS_NOT_FOUND;

}

Нетрудно видеть, что  в сравнении с консольным проектом единственное изменение при вызове метода поиска из класса Service<T> состоит в том, что передается другое значение параметра типа, поскольку поиск ведется в массиве целых чисел.

Рассмотрим теперь подробнее, как оценивается время, затрачиваемое  различными методами на поиск образца в массиве. Для этой цели используется стандартный прием, неоднократно используемый в примерах этого курса. В классе  Service<T> определяется функциональный тип:

public delegate int SearchMethod(T[] arr, T pattern);

Все рассматриваемые нами методы поиска являются экземплярами этого типа, поскольку их сигнатуры совпадают с сигнатурой, заданной делегатом SearchMethod. В класс Service<T> добавлен следующий метод:

public static long HowLong(SearchMethod search, int count,

T[] arr, T pattern)

{

DateTime start, finish;

start = DateTime.Now;

for(int i =0; i < count; i++)

search(arr,pattern);

finish = DateTime.Now;

return finish.Ticks — start.Ticks;

}

Метод HowLong позволяет оценить время работы метода, переданного в качестве первого аргумента. Это может быть любой метод, принадлежащий типу SearchMethod. Время здесь измеряется в тиках. Напомню, что один тик равен 100 наносекундам или 0.0001 миллисекунды.

Рассмотрим теперь, как вызывается метод HowLong в обработчике события соответствующей командной кнопки интерфейсного  класса:

private void buttonBinSearchTime_Click(object sender, EventArgs e)

{

textBoxTimeBinSearch.Text = Service<int>.HowLong

(Service<int>.BinSearch, count, arr, pattern).ToString();

}

Задачи

  1. Создайте DLL, включающую сервисный класс с тремя методами поиска по образцу в массивах типа double. Постройте консольный и Windows проекты, использующие эти методы поиска. Получите оценки времени работы методов поиска.
  2. Создайте DLL, включающую сервисный класс с тремя методами поиска по образцу в массивах типа StringBuilder. Постройте консольный и Windows проекты, использующие эти методы поиска. Получите оценки времени работы методов поиска.
  3. Создайте DLL, включающую сервисный класс с тремя методами поиска по образцу в массивах типа int. Постройте консольный и Windows проекты, использующие эти методы поиска. Получите оценки времени работы методов поиска.
  4. Создайте DLL, включающую сервисный класс с тремя методами поиска по образцу в массивах типа Person. Класс Person определите самостоятельно. Реализуйте возможность поиска по различным полям объекта (по имени, возрасту, адресу).  Постройте Windows проект, использующий эти методы поиска.
  5. Создайте DLL, включающую сервисный класс с тремя методами поиска по образцу в массивах типа Point. Класс Point определите самостоятельно. Реализуйте возможность поиска по различным полям объекта (по декартовым координатам точки, по полярным координатам).  Постройте Windows проект, использующий эти методы поиска.
  6. Создайте DLL, включающую сервисный класс с тремя методами поиска по образцу в массивах типа Account. Класс Account определите самостоятельно. Реализуйте возможность поиска по различным полям объекта (по номеру банковского счета, по размеру вклада).  Постройте Windows проект, использующий эти методы поиска.
  7. На основе приведенного описания класса Service<T> создайте собственный универсальный класс, включающий различные варианты метода поиска. Создайте Windows-интерфейс для работы с этим классом по образцу интерфейса, приведенного на рис 7_9.

Сортировка

Задача сортировки формулируется достаточно просто. Дан массив Ar с элементами типа T. Тип (класс) T является упорядоченным типом, так что для него определена операция сравнения элементов. Отсортировать массив можно по возрастанию или по убыванию. В первом случае для всех элементов массива выполняется условие Ar[i] <= Ar[i+1], во-втором – справедливо условие  Ar[i] >= Ar[i+1]. Порядок сортировки можно задавать как параметр метода, что сказывается лишь на операции  сравнения элементов  — «больше» или «меньше».

Методов сортировки великое множество. Классическим трудом является третий том «Искусства программирования» Д. Кнута [Кнут], который так и называется «Сортировки». Одним из основных критериев классификации методов сортировки является сложность метода сортировки – временная и емкостная – T(n) и P(n). В первом случае нас интересует время сортировки произвольного массива из n элементов, во-втором -  дополнительная память, требуемая в процессе сортировки. Говоря о времени сортировки, можно рассматривать минимальное, максимальное или среднее время сортировки. Время сортировки определяется числом требуемых операций, которые в свою очередь разделяются на операции сравнения элементов и операции обмена элементами, когда два элемента Ar[i] и Ar[j] обмениваются местами.

Методы сортировки за время порядка O(n2)

В ситуациях, когда приходится сортировать массивы небольшой размерности, разумно пользоваться простыми методами сортировки. Простые и естественные способы сортировки требуют, как правило, времени работы порядка O(n2).  Эти методы сортируют массивы небольшой размерности быстрее, чем их соперники — более эффективные по порядку, но и более сложные методы сортировки. Но понятно, что у каждого из квадратичных методов сортировки есть свой предел, то максимальное значение n, после которого эффективные методы со сложностью O(n*log2(n)) начинают работать быстрее.

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

Сортировка SortMin (SortMax)

Две сортировки минимумами и максимумами являются вариациями алгоритма, называемого часто «простым выбором». Идея алгоритма прозрачна и состоит в том, чтобы найти минимальный (максимальный) элемент массива и поставить его на первое (последнее) место. Затем применить тот же прием к массиву без первого (последнего) элемента, повторяя эту схему, пока оставшаяся часть массива не будет состоять из одного элемента.

Сортировка SortMinMax

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

Сортировка SortBubble (SortBall)

Эти две вариации одного алгоритма сортировки относят к классу «обменных сортировок». В каждом алгоритме сортировки присутствуют операции сравнения элементов и обмена элементов. Но алгоритмы могут отличаться тем, какие операции превалируют в реализации алгоритма. В сортировках прямого выбора минимумами и максимумами обмен выполняется только после того, как сделан выбор нужного элемента, требующий многократных проверок. В обменных сортировках обмен элементов является основной операцией в процессе сортировки. И те и другие методы имеют свои достоинства и соответственно недостатки. Операции обмена обычно более дорогие (требуют больше времени), чем операции сравнения. В этом преимущество методов прямого выбора. Но в обменных сортировках за один проход не только один элемент становится на свое место, но и другие элементы стремятся занять свои места, что позволяет ускорить сортировку.

Идея алгоритма пузырьковой сортировки SortBubble, принадлежащей классу обменных сортировок,  состоит в том, чтобы, начиная с конца массива, сравнивать два соседних элемента и, если нарушается упорядоченность, производить обмен элементами – более легкий элемент меняется местами со своим соседом. Очевидно, что при первом проходе массива минимальный элемент, как самый легкий всплывет наверх, подобно пузырьку воздуха, и станет на первое место. Важно то, что при этом будут всплывать, приближаясь к своим законным местам и другие легкие элементы. Обменные сортировки хорошо работают на почти упорядоченных массивах. Достоинство алгоритма еще и в том, что он позволяет собрать важную информацию — на каждом проходе можно подсчитывать число обменов. Если оно равно 0, то массив уже упорядочен, и сортировку можно прекращать.

Алгоритм «тяжелого шарика» SortBall является симметричной вариацией пузырьковой сортировки. Работа начинается с начала массива и в процессе обмена вниз опускаются тяжелые элементы, так что на первом проходе максимальный элемент станет на последнее место.

Сортировка SortShaker

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

Сортировка SortInsert – сортировка вставками

Сортировка вставками – это еще один класс простых методов сортировки. Рассмотрим простейший вариант этого способа сортировки. Чтобы описать идею алгоритма, предположим вначале, что массив уже упорядочен за исключением последнего элемента. Тогда задача сводится к тому, чтобы вставить этот элемент в нужную позицию. Это можно сделать двояко. Во-первых, можно применить алгоритм, подобный «пузырьку», выполняя обмен, пока последний элемент не «всплывет» на свое место. В лучшем случае не придется делать ни одного обмена, если последний элемент – это максимальный элемент и стоит уже на своем месте. В худшем случае придется сделать n сравнений и n обменов, если последний элемент – это минимальный элемент массива. В среднем – истина посредине. Другой способ состоит в том, чтобы воспользоваться упорядоченностью массива. В этом случае место вставки, используя алгоритм бинарного поиска, можно найти значительно быстрее за log(n) операций. К сожалению, нельзя избежать сдвига всех элементов массива ниже точки вставки.

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

Сортировка SortShell – улучшенный вариант сортировки вставками

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

В чем идея алгоритма сортировки Шелла? Зададим последовательность чисел:

hk, hk-1…, h1

Эта последовательность должна быть убывающей и заканчиваться значением h1 = 1. Любая последовательность чисел с такими свойствами является подходящей и гарантирует сортировку массива. До сих пор неизвестно, какая последовательность является наилучшей. Желательным свойством последовательности является взаимная простота чисел hi. Другое свойство требует, чтобы  каждое из них примерно в два раза было меньше предыдущего. Хорошим выбором считается последовательность чисел, в которой hi = 2i -1. Первый член последовательности hk подбирается так, чтобы он был примерно равен n/2, где n – размерность массива. При n = 1000 последовательность может быть такой: 511, 255, 127, 63, 31, 15, 7, 3, 1.

Внешний цикл в сортировке Шелла – это цикл по последовательности hi. Каждый член этой последовательности делит элементы массива на группы, состоящие из элементов массива, отстоящих друг от друга на расстоянии hi. Для выбранной нами последовательности первый член последовательности создает большое число групп – Hk групп, в каждой из которых не более двух элементов. На следующем шаге число групп уменьшается, а число элементов в них увеличивается. На последнем шаге при h1 = 1 возникает одна группа, в которую входят все элементы. Суть алгоритма в том, что к каждой возникающей группе независимо применяется обычный алгоритм вставки, сортирующий каждую группу. В чем же суть алгоритма. Ведь на последнем этапе ко всему массиву применяется обычный алгоритм вставки. За счет чего же достигается эффективность алгоритма? Дело в том, что к последнему этапу массив будет «почти упорядочен», а на таких массивах алгоритм вставки работает крайне быстро. Действительно, если массив упорядочен, то алгоритм SortInsert c «пузырьковым обменом» выполнит всего лишь n операций сравнения и ему вообще не потребуются операции обмена.

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

/// <summary>

/// Сортировка Шелла

/// </summary>

/// <param name=»arr»></param>

public static void ShellSort(T[] arr)

{

int n = arr.Length, m = (int)Math.Log(n);

//Создать последовательность чисел Шелла — h

int[] h = new int[m];

int t = 2;

for (int i = 0; i < m; i++)

{

h[i] = t — 1; t *= 2;

}

//Внешний цикл по последовательности чисел h

//Внутренний по числу групп

for (int i = 0; i < m; i++)

for (int j = 0; j < h[i]; j++)

SortInsert(arr, n, h[i], j);

}

/// <summary>

/// Сортировка вставкой группы элементов массива arr,

/// начинающейся с элемента, заданного индексом ind,

/// и отстоящих друг от друга на расстоянии h

/// </summary>

/// <param name=»arr»>массив</param>

/// <param name=»h»>расстояние между элементами в группе</param>

/// <param name=»ind»>индекс начального элемента группы</param>

private static void SortInsert(T[] arr, int n, int h, int ind)

{

int k = ind + h, i = 0;

T item;

while (k < n)

{

//вставка arr[k] на место

i = k — h;

while (i >= ind)

{

if (arr[i+h].CompareTo(arr[i]) == -1)

{

item = arr[i]; arr[i] = arr[i + h];

arr[i + h] = item; i -= h;

}

else break;

}

k += h;

}

}

Заметьте, сортировка группы элементов, строящейся в методе Шелла, выделена в отдельную процедуру. Тем самым отделен процесс формирования группы от ее сортировки, что облегчает понимание алгоритма и обоснование его корректности. Для сортировки группы применяется метод сортировки вставкой, который, как отмечалось, эффективно работает для почти отсортированных групп. Несмотря на свою сложность сортировка Шелла весьма эффективна и сравнима с быстрой сортировкой Хоара. Считается, что временная сложность этой сортировки в среднем равна O(n*log(n)), что соответствует характеристикам лучших методов сортировки. Мои эксперименты на массивах различной длины от 10 до 10000 подтверждают высокую эффективность этого метода. На рис. 7_10 показаны результаты одного из экспериментов, где сравнивались времена четырех наиболее эффективных методов сортировки – быстрой сортировки Хоара, пирамидальной сортировки, сортировки слиянием и сортировки Шелла.

Задачи

  1. Создайте DLL с сервисным классом ServiceSort, включающим методы сортировки SortMin, SortMax и метод HowLong, позволяющий оценить время сортировки. Постройте Windows проект, поддерживающий работу с этой библиотекой классов.
  2. Создайте DLL с сервисным классом ServiceSort, включающим методы сортировки SortMin, Sortmax, SortMinMax и метод HowLong, позволяющий оценить время сортировки. Постройте Windows проект, поддерживающий работу с этой библиотекой классов.
  3. Создайте DLL с сервисным классом ServiceSort, включающим методы сортировки SortBubble, SortBall и метод HowLong, позволяющий оценить время сортировки. Постройте Windows проект, поддерживающий работу с этой библиотекой классов.
  4. Создайте DLL с сервисным классом ServiceSort, включающим методы сортировки SortBubble, SortBall, SortShaker и  метод HowLong, позволяющий оценить время сортировки. Постройте Windows проект, поддерживающий работу с этой библиотекой классов.
  5. Создайте DLL с сервисным классом ServiceSort, включающим методы сортировки SortBubble, SortInsert и метод HowLong, позволяющий оценить время сортировки. Постройте Windows проект, поддерживающий работу с этой библиотекой классов.
  6. Создайте DLL с сервисным классом ServiceSort, включающим метод сортировки SortBubble, SortShell и метод HowLong, позволяющий оценить время сортировки. Постройте Windows проект, поддерживающий работу с этой библиотекой классов.
  7. Создайте DLL с сервисным классом ServiceSort<T>, включающим методы сортировки SortMin, SortMax для массивов с произвольным типом элементов T, метод HowLong, позволяющий оценить время сортировки. Постройте Windows проект, поддерживающий работу с этой библиотекой классов.
  8. Создайте DLL с сервисным классом ServiceSort<T>,  включающим методы сортировки SortMin, Sortmax, SortMinMax для массивов с произвольным типом элементов T,  метод HowLong, позволяющий оценить время сортировки. Постройте Windows проект, поддерживающий работу с этой библиотекой классов.
  9. Создайте DLL с серви сным классом ServiceSort<T>,  включающим методы сортировки SortBubble, SortBall для массивов с произвольным типом элементов T, метод HowLong, позволяющий оценить время сортировки. Постройте Windows проект, поддерживающий работу с этой библиотекой классов.
  10. Создайте DLL с сервисным классом ServiceSort<T>, включающим методы сортировки SortBubble, SortBall, SortShaker для массивов с произвольным типом элементов T,   метод HowLong, позволяющий оценить время сортировки. Постройте Windows проект, поддерживающий работу с этой библиотекой классов.
  11. Создайте DLL с сервисным классом ServiceSort<T>,  включающим методы сортировки SortBubble, SortInsert для массивов с произвольным типом элементов T, метод HowLong, позволяющий оценить время сортировки. Постройте Windows проект, поддерживающий работу с этой библиотекой классов.
  12. Создайте DLL с сервисным классом ServiceSort<T>,  включающим метод сортировки SortBubble, SortShell для массивов с произвольным типом элементов T,  метод HowLong, позволяющий оценить время сортировки. Постройте Windows проект, поддерживающий работу с этой библиотекой классов.

Проекты

  1. Постройте класс ServiceSorting, содержащий методы сортировки и позволяющий анализировать время работы методов сортировки на одних и тех же массивах.
  2. Постройте универсальный класс ServiceSorting<T>, содержащий методы сортировки массивов произвольного типа и позволяющий анализировать время работы методов сортировки на одних и тех же массивах.

Рекурсивные методы сортировки за время порядка O(n*log2(n))

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

Сортировка за линейное время

За линейное время можно сортировать только массивы, на элементы которых наложены дополнительные ограничения, например, элементы принадлежат фиксированному числу видов.

Задача «Красные и белые»

В этой задаче элементы массива принадлежат двум видам – они либо красные, либо белые. Отсортировать такой массив можно за линейное время, более того, за один проход по массиву, выполняя не более одной проверки и одного обмена для каждого элемента массива. Задача разбиения массива на два подмножества в той или иной формулировке часто встречается в практике программирования. В частности она возникает в алгоритме быстрой сортировки Хоара.

Все множество индексов элементов массива разделим на три непересекающихся подмножества – 0-зона, содержащая только белые элементы, непроверенная зона для тех элементов, чей цвет не установлен, 1- зона для красных элементов. Инвариантом, поддерживаемым в проектируемом алгоритме, будет расположение зон. Массив отсортирован, когда непроверенная зона становится пустой. В этом идея алгоритма — поддерживать истинность инварианта, сокращая непроверенную зону. В начальном состоянии 0-зона и 1-зона пусты, а непроверенная зона занимает все множество индексов, так что ее начальная граница Start = 0, а граница Finish = n-1. В начальном состоянии инвариант считается истинным. Основной и единственный проход по циклу выполняется по непроверенной зоне до тех пор, пока эта зона не станет пустой (или состоять из одного элемента). Проверка элементов начинается с левого конца непроверенной зоны. До тех пор, пока очередной элемент является белым, расширяется 0-зона и соответственно сокращается непроверенная зона – значение границы Start увеличивается на 1. В тот момент, когда встречается красный элемент, проверка прекращается и запускается аналогичный цикл, но теперь уже с правого конца непроверенной зоны. Когда на правом конце обнаруживается белый элемент, происходит обмен значениями на двух концах непроверенной зоны. Обмен восстанавливает истинность инварианта. По завершении цикла непроверенная зона становится пустой, так что 1-зона с красными элементами следует сразу за 0-зоной с белыми элементами и массив отсортирован.

Задача Дейкстры «О голландском национальном флаге»

Эдсгар Дейкстра рассматривал эту задачу в своей известной книге по структурному программированию. Элементы в массиве принадлежат трем видам – красные, белые и синие. Требуется отсортировать массив в порядке следования этих цветов во флаге Голландии. Поскольку цвета флагов России и Голландии совпадают, то для нас приятнее сортировать массив в порядке следования этих цветов во флаге России  — белые, синие, красные элементы.

Алгоритм сортировки за один проход по массиву нетрудно получить обобщением предыдущего алгоритма. Рассмотрим массив, состоящий из четырех зон,  -0-зоны, содержащей только белые элементы, 1-зоны с синими элементами, непроверенная зоны и 2-зоны с красными элементами.  Инвариантом, поддерживаемым в алгоритме, является расположение зон.  В начальный момент все зоны, кроме непроверенной пусты и инвариант считается истинным. Внешний цикл по-прежнему идет по элементам непроверенной зоны, продвигаясь попеременно, то слева, то справа. При движении слева, пока встречаются синие элементы, расширяется синяя зона. Если встретился не синий элемент, то он может быть либо белым, либо красным. Если это белый элемент, то он меняется местами с первым элементом, начинающим синюю зону. После чего проверка продолжается с левого конца непроверенной зоны. Когда же встречается красный элемент, то непроверенная зона начинает проверяться с правого конца. Когда при проверке справа встречается не красный элемент, то происходит обмен с красным элементом, найденным при проверке слева. Если справа был обнаружен белый элемент, то понадобится еще один обмен, чтобы поставить его на свое место.

Все операции поддерживают истинность инварианта. Когда цикл завершается и непроверенная зона становится пустой, массив отсортирован.

Задача Гарри Поттера «Сортировочная шляпа»

Задачи, где в массиве 4 вида элементов, встречаются не менее часто. Например, молекула ДНК, как уже упоминалось, представляется строкой (массивом char)  в алфавите из четырех символов. Этот массив иногда требуется отсортировать в некотором заданном порядке следования символов. Приведу следующую содержательную постановку этой задачи.

В школу чародейства и волшебства Хогвартс прибыли новые ученики числом N.  Их посадили за один стол в произвольном порядке. Сортирующая шляпа рассортировала учеников и рассадила их по своим классам – слева направо:  Гриффиндор, Рэйвенкло, Хаффлпафф, Слизерин.

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

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

Сортировка массивов с элементами m типов

Приведенные выше алгоритмы сортировки описаны в предположении, что  методу сортировки заранее известны и тип сортируемых элементов и их возможные значения. Давайте рассмотрим, как может выглядеть метод сортировки, позволяющий сортировать элементы произвольных типов, возможные значения которых заранее неизвестны, но передаются методу сортировки в момент вызова в качестве одного из аргументов. Начну с рассмотрения частного случая, когда в массиве элементы двух видов. Главная цель примера не столько в том, чтобы продемонстрировать сам алгоритм – он достаточно прост, а в том, чтобы показать, как на C# написать универсальный алгоритм для элементов любого типа и с разными названиями видов. Хочется, чтобы алгоритм можно было использовать для классификации элементов 0 и 1, «мужчин» и «женщин», «красных» и «белых».

Добавим в класс SortService универсальный метод сортировки массивов с двумя видами элементов. Вот текст этого метода сортировки:

/// <summary>

/// Сортировать массив,

/// Предусловие: Элементы массива принадлежат двум видам,

/// заданным в массиве Spacimen

/// </summary>

/// <param name=»ar»>сортируемый массив</param>

/// <param name=»Spacimen»>массив представителей</param>

public static void SortTwoKinds(T[] ar, T[] Spacimen)

{

int start = 0, finish = ar.Length — 1;

T val1 = Spacimen[0], val2 = Spacimen[1];

while (start < finish)

{

while ((start < finish) && (ar[start].CompareTo(val1) == 0))

start++;

while ((start < finish) && (ar[finish].CompareTo(val2) == 0))

finish—;

//обмен

T temp = ar[start]; ar[start] = ar[finish];

ar[finish] = temp;

start++; finish—;

}

}

Тот факт, что элементы сортируемого массива могут быть экземплярами произвольного класса T, обеспечивается тем, что класс SortService является универсальным классом с параметром T.  Тот факт, что виды элементов могут иметь произвольные значения, обеспечивается тем, что методу сортировки передается массив Spacimen, хранящий представителей массива – возможные значения элементов массива.

Покажем теперь, как клиентский класс может  вызывать метод сортировки в конкретной ситуации:

public void TestSortRedAndWhite()

{

//Два вида элементов

int m = 2;

string[] cand = new string[m];

cand[0] = «red»; cand[1] = «white»;

//Моделирование массива ar

Random rnd = new Random();

const int n = 10;

string[] ar = new string[n];

for (int ind, i = 0; i < n; i++)

{

ind = rnd.Next(0, m);

ar[i] = cand[ind];

}

Console.WriteLine(«Массив до сортировки!»);

for (int i = 0; i < n; i++)

Console.Write(ar[i] + » «);

Console.WriteLine();

//Сортировка массива ar

SortService<string>.SortTwoKinds(ar,cand);

Console.WriteLine(«Массив после сортировки!»);

for (int i = 0; i < n; i++)

Console.Write(ar[i] + » «);

Console.WriteLine();

}

Рассмотренный алгоритм вряд ли целесообразно обобщать на случай, когда число видов более четырех. Тем не менее, можно построить эффективный алгоритм, когда число видов m известно и оно заведомо меньше n – числа элементов в массиве. В этом случае можно построить алгоритм сортировки, работающий за время O(n*log(m)). Идея алгоритма достаточно прозрачна. За один проход по сортируемому массиву посчитаем, сколько элементов каждого вида находится в массиве. Для хранения этой информации потребуется дополнительный массив Counts размерности m, элемент которого Counts[i] задает число элементов вида Spacimen[i] в сортируемом массиве. Используя этот массив и массив Spacimen можно за время O(n) заполнить сортируемый массив элементами, следующими в нужном порядке. Основное время алгоритма уходит на формирование массива Counts, поскольку для каждого элемента нужно определить какому виду он принадлежит,  что требует проведения поиска в массиве Spacimen. Для поиска можно использовать метод SearchBarrier,  на что уйдет время порядка O(m).   Время можно сократить до O(log2 (m)), если использовать бинарный поиск, предварительно отсортировав массив Spacimen.  Заметьте, на сортировку и хранение отсортированного массива понадобится дополнительное время порядка O(m*log2(m)) и дополнительная память. Когда число видов m сравнимо по порядку с числом элементов n, то алгоритм становится эквивалентным по сложности классическим алгоритмам сортировки.

Сортировка черпаками

Если в процессе сортировки нужно хранить не только ключи, но и связанную с ними информацию, например указатели на объекты, то нельзя обойтись подсчетом числа элементов одного вида, поскольку для каждого из элементов нужно сохранять связанную с ним информацию. В этом случае для каждого вида элементов нужно иметь свой «черпак» — массив, хранящий элементы данного вида. Алгоритм сортировки, как и в вышеописанном случае, состоит из двух этапов. На первом – заполняются черпаки, на втором – данные из черпаков сливаются в  общий массив.

До сих пор разбиение элементов массива на виды осуществлялось с помощью представителей – к одному виду относились элементы с одним и тем же значением. Общий способ классификации состоит в задании классифицирующей функции – int Classification(int m, T item), которая для каждого элемента item возвращает число, задающее его вид. Аргумент m этой функции указывает максимальное число видов для этой функции классификации. Обычно предполагается, что значение, возвращаемое функцией, является целым числом в диапазоне [0, m-1], задавая номер вида. Примером такой функции классификации (оракула) является сортировочная шляпа из задачи Гарри Поттера, которая умеет по некоторым признакам ученика определить, к какому классу он должен принадлежать.

Задачи

  1. Создайте Windows проект для задачи «Красные и белые».
  2. Создайте Windows проект для задачи Э. Дейкстры.
  3. Создайте Windows проект для задачи «Сортировочная шляпа».
  4. Создайте Windows проект для сортировки за линейное время массивов типа string, элементы которого могут принимать одно из трех значений, заданных в массиве представителей.
  5. Создайте Windows проект для сортировки за линейное время массивов типа string, элементы которого могут принадлежать одному из трех видов. Вид элемента определяется  функцией классификации, передаваемой методу сортировки в качестве параметра.
  6. Создайте Windows проект для сортировки за линейное время массивов типа string, элементы которого могут принимать одно из четырех значений, заданных в массиве представителей.
  7. Создайте Windows проект для сортировки за линейное время массивов типа string, элементы которого могут принадлежать одному из четырех видов. Вид элемента определяется  функцией классификации, передаваемой методу сортировки в качестве параметра.
  8. Создайте Windows проект для сортировки за линейное время массивов типа string, элементы которого могут принимать одно из m значений, заданных в массиве представителей.
  9. Создайте Windows проект для сортировки за линейное время массивов типа string, элементы которого могут принадлежать одному из m видов. Вид элемента определяется  функцией классификации, передаваемой методу сортировки в качестве параметра.
  10. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortTwoKinds – процедуру сортировки массива типа T, содержащего элементы двух видов.  Алгоритм должен выполняться за время порядка O(n), где n – это число элементов массива. Виды элементов задаются массивом представителей. Создайте Windows проект, поддерживающий работу с этой DLL.
  11. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortTwoKinds – процедуру сортировки массива типа T, содержащего элементы двух видов.  Алгоритм должен выполняться за время порядка O(n), где n – это число элементов массива. Деление элементов на два вида задается соответствующей функцией классификации, передаваемой процедуре сортировки в качестве параметра. Создайте Windows проект, поддерживающий работу с этой DLL.
  12. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortThreeKinds – процедуру сортировки массива типа T, содержащего элементы трех видов.  Алгоритм должен выполняться за время порядка O(n), где n – это число элементов массива. Виды элементов задаются массивом представителей. Создайте Windows проект, поддерживающий работу с этой DLL.
  13. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortThreeKinds – процедуру сортировки массива типа T, содержащего элементы трех видов.  Алгоритм должен выполняться за время порядка O(n), где n – это число элементов массива. Деление элементов на два вида задается соответствующей функцией классификации, передаваемой процедуре сортировки в качестве параметра. Создайте Windows проект, поддерживающий работу с этой DLL.
  14. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortFourKinds – процедуру сортировки массива типа T, содержащего элементы четырех видов.  Алгоритм должен выполняться за время порядка O(n), где n – это число элементов массива. Виды элементов задаются массивом представителей. Создайте Windows проект, поддерживающий работу с этой DLL.
  15. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortFourKinds – процедуру сортировки массива типа T, содержащего элементы четырех видов.  Алгоритм должен выполняться за время порядка O(n), где n – это число элементов массива. Деление элементов на два вида задается соответствующей функцией классификации, передаваемой процедуре сортировки в качестве параметра. Создайте Windows проект, поддерживающий работу с этой DLL.
  16. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortMKinds – процедуру сортировки массива типа T, содержащего элементы m видов.  Виды элементов задаются массивом представителей. Создайте Windows проект, поддерживающий работу с этой DLL.
  17. Создайте DLL с классом, содержащим универсальную (с параметром типа T) процедуру SortMKinds – процедуру сортировки массива типа T, содержащего элементы m видов.  Деление элементов на два вида задается соответствующей функцией классификации, передаваемой процедуре сортировки в качестве параметра. Создайте Windows проект, поддерживающий работу с этой DLL.

Проекты

  1. На основе рассмотренного в этом разделе класса SortService постройте собственный класс, включающий  различные методы сортировки для разных значений числа видов m. Постройте Windows-интерфейс, позволяющий клиентам класса вызывать его методы для массивов разных типов.
  2. Постройте проект, позволяющий сравнивать время, затрачиваемое компьютером на сортировку массива, когда применяются методы универсального класса SortService<T> и аналогичные методы, написанные для конкретного типа данных. Цель проекта – анализ  возможных потерь эффективности, как плата за универсальный характер методов сортировки.
  3. Постройте проект, позволяющий сравнивать время, затрачиваемое компьютером на сортировку массива с элементами двух, трех, четырех и m видов, при использовании методов класса SortService и метода быстрой сортировки Хоара, встроенной в библиотеку FCL.

/li

Скачать лекцию 1.7