Основы программирования на С# 3.0: ядро языка

7. Лекция: Символы и строки

Эта лекция посвящена работе с текстовой информацией. Рассматриваются различные типы данных, применяемые при работе с текстами - char, string, stringBuilder. Подробно обсуждаются классические алгоритмы поиска и сортировки строковых данных.

1.Общий взгляд 2

2.Класс char 3

2.1.Класс char[] - массив символов 7

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

3.Класс String 9

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

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

3.3.Строковые константы 10

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

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

3.6.Метод Format 13

3.7.Методы Join и Split 15

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

4.Класс StringBuilder - построитель строк 18

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

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

4.3.Основные методы 20

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

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

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

6.1.Задачи 24

6.2.Проекты 27

7.Поиск и Сортировка 27

7.1.Поиск 28

7.1.1.Линейный поиск 28

7.1.2.Поиск с барьером 29

7.1.3.Бинарный поиск 30

7.2.Задачи 34

8.Сортировка 34

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

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

8.1.2.Сортировка SortMinMax 35

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

8.1.4.Сортировка SortShaker 36

8.1.5.Сортировка SortInsert - сортировка вставками 36

8.1.6.Сортировка SortShell - улучшенный вариант сортировки вставками 36

8.2.Задачи 39

8.3.Проекты 40

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

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

8.5.1.Задача "Красные и белые" 41

8.5.2.Задача Дейкстры "О голландском национальном флаге" 41

8.5.3.Задача Гарри Поттера "Сортировочная шляпа" 42

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

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

8.6.Задачи 44

8.7.Проекты 46

1. Общий взгляд

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

• отдельные символы, чаще всего его называют типом 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;

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