ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем Представление текстовой информации Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра. - презентация

1 ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем Представление текстовой информации Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем ЯЗЫКИ ПРОГРАММИРОВАНИЯ / ПРОГРАММИРОВАНИЕ

2 Представление текстовой информации © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2 Вычислительная техника оперирует только числовой информацией (в двоичной СС) Вычислительная техника оперирует только числовой информацией (в двоичной СС) Текст необходимо представить в виде набора чисел Текст необходимо представить в виде набора чисел Естественные разбиения текста: по символам (таблица ASCII), по словам. Естественные разбиения текста: по символам (таблица ASCII), по словам.

3 Представление текстовой информации (пример) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 3 mom soap frame A.B.C.D.E.F 6.`abcdefghijklmno 7.pqrstuvwxyz{|}~DL = momsoap frame 6D6F6D20736F D65

4 Хранение текстовой информации (строки) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 4 Описанный способ представления предполагает описание текста в виде набора однотипных данных. Для хранения подобной информации в языках высокого уровня (например, СИ) применяются массивы – строки. Для хранения одного символа в языке СИ предусмотрен тип данных char. Хранение текста, приведенного на предыдущем слайде, может быть организовано в массиве: char text[14];

5 Операции со строками © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 5 получение символа по номеру позиции (индексу); определение длины строки; копирование строки; проверка на совпадение строк (с учётом или без учёта регистра символов); сравнение строк (в алфавитном порядке); поиск символа в строке; конкатенация (соединение) строк: "ab" + "cd" = "abcd"; получение подстроки по индексам начала и конца: "abcdefghijklmnopqrstuvwxyz", 3, 8 "defghi" ;

6 Операции со строками © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 6 проверка вхождения одной строки в другую (поиск подстроки в строке): "abcdefghij": "cdef" – да, "cfde" – нет; определение подстроки, состоящей только из заданного набора символов. разбиение строки на поля (tokens), разделенные заданным набором символов. замена подстроки в строке: "abcdefghij", "cdef" на "cfde" = "abcfdeghij"

7 Особенности хранения текстовой информации © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 7 Actions speak louder than words Ask no questions and you will be told no lies Best defence is offence Let well alone В чем (с точки зрения хранения) заключается отличие между следующими текстовыми данными? Каким образом можно организовать хранение информации о размере строки?

8 Подходы к представлению строк © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 8 Pascal strings – представление в виде массива символов, размер которого хранится отдельно: NULL-terminated strings (C Strings, ASCIIZ) – представление в виде массива символов, заканчивающегося специальным допустимым символом – "нуль-терминатором". В языке СИ это символ с кодом 0 (символьная константа '\0'), иногда – число 0xFF или код символа '$' (0х24). 14momsoap frame momsoap frame\0

9 Преимущества Pascal-strings © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 9 размер строки известен => быстрые операции конкатенации и получения размера строки; строка может содержать любые данные, нет выделенного символа для нуль-терминатора; возможно автоматическое отслеживание выхода за границы строки при её обработке; быстрая операции вида «взятие N-ого символа с конца строки». 14momsoap frame…

10 Недостатки Pascal-strings © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 10 осложнено хранение и обработка символов произвольной длины (например UTF8); дополнительные накладные расходы на хранение длины строки (хранение большого количества строк маленького размера); ограничение на максимальный размер строки (зависит от разрядности ячейки для хранения длины) 14momsoap frame…

11 Преимущества С-strings © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 11 momsoap frame\0... меньший объем служебной информации о строке; представления строки без создания отдельного типа данных; отсутствуют ограничения на максимальный размер строки; простота получения суффикса строки; возможность использовать алфавит с переменным размером символа (например, UTF-8).

12 Недостатки С-strings © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 12 momsoap frame\0... сложная операция получения длины и конкатенации строк; отсутствие средств контроля за выходом за пределы строки (в случае повреждения завершающего байта возможно повреждение больших областей памяти); отсутствие возможности использовать символ завершающего байта в качестве элемента строки. англ.; рус. (перевод плохой).

13 Нуль-терминатор © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» A.B.C.D.E.F 0.NULSOHSTXETXEOTENQACKBELBSTABLFVTFFCRSOSI 1.DLEDC1DC2DC3DC4NAKSYNETBCANEMSUBESCFSGSRSUS 2. !"#$ %&'()*+,./ : ; ? 5.PQRSTUVWXYZ[\]^_ 6.`abcdefghijklmno 7.pqrstuvwxyz{|}~DEL Специальный символ таблицы ASCII, который обозначает конец строки

14 Инициализация строк в языке СИ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 14 В языке СИ инициализация строки может быть выполнена двумя способами: 1. Согласно правилам инициализации массивов. Символы задаются с использованием символьных констант, а нуль-терминатор необходимо указывать явным образом. char s1[5]={'t','e','s','t','\0'}; char s2[] = {'h','e','l','l','o','\0'}; 2.С использованием строковых констант. Содержимое строки задается в двойных кавычках, вставка нуль- терминатора происходит автоматически: char s1[5]= "test"; char s2[] = "hello";

15 Ввод-вывод строк в языке СИ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 15 В языке СИ ввод-вывод строк может быть выполнен двумя способами: 1. Посимвольно: i=0; do{ scanf("%c",&s[i]); i++; }while(s[i-1] != '\n'); s[i-1] = '\0'; for(i=0; s[i] != '\0'; i++) printf("%c",s[i]); 2.С использованием спецификатора %s: scanf("%s",s); // ввод до пробела! fgets(s,msize,stdin); // ввод до '\n' printf("%s",s); // вывод до '\0'

16 Операции со строками © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 16 получение символа по номеру позиции (индексу); определение длины строки; копирование строки; проверка на совпадение строк (с учётом или без учёта регистра символов); сравнение строк (в алфавитном порядке); поиск символа в строке; конкатенация (соединение) строк: "ab" + "cd" = "abcd"; получение подстроки по индексам начала и конца: "abcdefghijklmnopqrstuvwxyz", 3, 8 "defghi" ;

17 Операции со строками © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 17 определение подстроки, состоящей только из заданного набора символов. проверка вхождения одной строки в другую (поиск подстроки в строке): "abcdefghij": "cdef" – да, "cfde" – нет; разбиение строки на поля (tokens), разделенные заданным набором символов. замена подстроки в строке: "abcdefghij", "cdef" на "cfde" = "abcfdeghij"

18 Получение символа по индексу © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 18 Получение символа по номеру позиции (индексу) является тривиальной операцией в языке СИ. Она реализуется через операцию индексации массивов. Например: char s[5]= "test"; s[0] = = 't' s[1] = = 'e' s[2] = = 's' s[3] = = 't' s[4] = = '\0'

19 Определение длины строки © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 19 Операция определения длины строки может быть выполнена двумя способами: 1. Явно запрограммирована: int i; for(i=0;s[i] != '\0'; i++); len = i; 2. С использованием функции strlen():... #include... len = strlen(s);

20 Копирование строки* © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 20 В языке СИ не предусмотрено операции присваивания строк. Существует два способа ее реализации: 1. Явное программирование: ? 2. С использованием функции strcpy():... #include... strcpy(s2,s1);

21 Копирование строки © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 21 В языке СИ не предусмотрено операции присваивания строк. Существует два способа ее реализации: 1. Явное программирование: int i; for(i=0;s1[i] != '\0'; i++) s2[i] = s1[i]; s2[i] = '\0'; 2. С использованием функции strcpy(): #include... strcpy(s2,s1);

22 Проверка строк на совпадение (с учетом регистра) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 22 В языке СИ не предусмотрено операции сравнения строк. Существует два способа ее реализации: 1. Явное программирование: int i, flg = 1; for(i=0; flg && s1[i]!='\0' && s2[i]!='\0';i++){ if( s1[i]!=s2[i] ) flg = 0; } if( flg == 1 ) – равны! 2. С использованием функции strcmp(): #include if( strcmp(s1,s2) == 0 ) – равны!

23 Проверка строк на совпадение (без учета регистра)* © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 23 В языке СИ не предусмотрено операции сравнения строк. Существует два способа ее реализации: 1. Явное программирование: ? Подсказка: Расстояние между любыми одинаковыми символами в верхнем и нижнем регистре одинаково и равно 'a' – 'A' 2. С использованием функции strcasecmp(): #include if( strcasecmp(s1,s2) == 0 ) – равны!

24 Справочный слайд (таблица ASCII) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» A.B.C.D.E.F 2. !"#$ %&'()*+,./ : ; ? 5.PQRSTUVWXYZ[\]^_ 6.`abcdefghijklmno 7.pqrstuvwxyz{|}~

25 Сравнение строк в алфавитном порядке © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 25 Существует два способа реализации: 1. Явное программирование: int i, flg = 0; for(i=0;!flg && s1[i]!='\0' && s2[i]!='\0';i++){ if( s1[i] < s2[i] ) flg = -1; else if( s1[i] > s2[i] ) flg = 1; } if( s1[i] < s2[i] ) flg = -1; // если строки else if( s1[i] > s2[i] ) flg = 1;// разной длины if( flg == 0 ) – равны! if( flg > 0 ) – s1 по алфавиту ниже s2 if( flg < 0 ) – s1 по алфавиту выше s2

26 Сравнение строк в алфавитном порядке (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 26 Существует два способа реализации: 1. Явное программирование (предыдущий слайд …) 2. С использованием функции strcmp(): #include if( strcmp(s1,s2) == 0 ) – равны! if( strcmp(s1,s2) > 0 ) – s1 по алфавиту ниже s2 if( strcmp(s1,s2) < 0 ) – s1 по алфавиту выше s2

27 Поиск символа в строке © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 27 Существует два способа реализации данной операции. 1. Явное программирование: int i; char c = ?; for(i=0;(s1[i]!='\0') && (s1[i]!=c); i++); if( s[i] == c ) – найден по индексу i. 2. С использованием функции strchr(): #include char c = ?, *ptr; ptr = strchr(s1,c); abcdefghijklmnop\0… ptr = &s1[10]

28 Конкатенация строк © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 28 Операция определения длины строки может быть выполнена двумя способами: 1. Явно запрограммирована: int i,j; for(i=0;s1[i] != '\0';i++); for(j=i;s2[j-i] != '\0';j++){ s1[j] = s2[j-i]; } s1[j] = s2[j-i]; // установка нуль-тарминатора 2. С использованием функции strcat(): #include strcat(s1,s2);

29 Получение подстроки по индексам* © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 29 int main() { int i,j; char s1[100] = "abcdefghijklmnop"; char s2[10]; int s = 3, e = 8; for(i=s; i

30 Получение подстроки по индексам © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 30 int main() { int i,j; char s1[100] = "abcdefghijklmnop"; char s2[10]; int s = 3, e = 8; for(i=s; i

31 Получение подстроки по индексам © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 31 // 1. временная подстановка нуль-терминатора char bkp = s1[e+1]; s1[e+1] = '\0'; strcpy(s2,&s1[s]); s1[e+1] = bkp; // 2. использование strncpy strncpy(s2,&s1[s],e-s+1); s2[e+1] = '\0' Данная задача может быть решена двумя способами. 1. Явное программирование (… см. предыдущие слайды) 2. Специальной функции, предназначенной для решения данной задачи, однако она может быть решена с использованием строковых функций:

32 Получение подстроки по индексам © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 32 // 1. временная подстановка нуль-терминатора char bkp = s1[e+1]; s1[e+1] = '\0'; strcpy(s2,&s1[s]); s1[e+1] = bkp; // 2. использование strncpy strncpy(s2,&s1[s],e-s+1); s2[e+1] = '\0' abcdefghijklmnop\0… s1[s] \0bkp

33 Операции со строками © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 33 определение подстроки, состоящей только из заданного набора символов. проверка вхождения одной строки в другую (поиск подстроки в строке): "abcdefghij": "cdef" – да, "cfde" – нет; разбиение строки на поля (tokens), разделенные заданным набором символов. замена подстроки в строке: "abcdefghij", "cdef" на "cfde" = "abcfdeghij"

34 Определение подстроки, состоящей из допустимых символов* © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 34 Операция определения длины строки может быть выполнена двумя способами: 1. Явно запрограммирована: ? Подсказки: 1. Каждый символ строки s1 необходимо проверить на вхождение s2. 2. Индекс первого символа, не входящего в s2 является искомым решением. 3. Задача проверки вхождения символа в строку была рассмотрена ранее.

35 Определение подстроки, состоящей из допустимых символов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 35 Операция определения длины строки может быть выполнена двумя способами: 1. Явно запрограммирована (см. предыдущие слайды) 2. С использованием функции strspn(): #include char s1[] = "hello world!", s2[] = "oelhw"; size_t t = strspn(s1,s2); helloworld!\0nop … t = 5

36 Поиск подстроки в строке © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 36 "abcdefghij": "cdef" – да, "cfde" – нет В языке СИ предусмотрено решение данной задачи при помощи строковых функций: if( strstr(s1,s2) != NULL ) – найдено char *ptr = strstr(s1,s2); if( ptr != NULL ){ ptr указывает на начало s2 в s1 } abcdefghijklmnop\0… ptr = &s1[2]

37 Поиск подстроки в строке* "abcdefghij": "cdef" – да, "cfde" – нет Решить задачу явно (запрограммировать). Алгоритм: 1. Сначала найти в s1 вхождение s2[0] – пусть это s1[i]. 2. Далее посимвольно сравнить остальные элементы: s1[i+1] == s2[1], s1[i+2] == s2[2], … s1[i+k] == s2[k], где (k+1) = strlen(s2) 3. Если в процессе проверки какие-то из символов не совпали, то проверка равенства s1[i] и s2 прекращается. 4. Продолжить поиск вхождения s2 в s1 начиная с i+1 элемента. 37 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 38 Хранение многострочного текста © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 38 В языке СИ перевод строки ранится в виде специального символа, ASCII код которого обозначается через Escape- последовательность '\n'. Данный символ не является признаком конца строки в терминах языка СИ. Это позволяет хранить многострочный текст в одной строке: char str[] = "Hello!\nHow are you?\nCan we talk now?\n"; Hello!\nHow are you? Canwe talk now? \0

39 Хранение набора строк © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 39 Одним из наиболее простых способов хранения набора строк является использование двумерного массива символов, также необходимо хранить число использованных строк: char srings[6][20]; int size; Drop inthebucket\0 Letwellalone Ahardnuttocrack Aliebegetsalie Storminateacup Afterusthedeluge

40 Обработка набора строк © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 40 инициализация набора строк; обращение к строке набора по индексу; вставка новой строки; удаление строки из набора; поиск заданной строки в наборе; поиск строки, содержащей заданную подстроку; конкатенация строк набора; перестановка строк в наборе; сортировка строк набора (в алфавитном порядке).

41 Инициализация набора строк © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 41 char strings[10][256]; int size = 0, i; for(i=0;i

42 Обращение к строке набора по индексу © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 42 char strings[10][256];... strlen(strings[i]); Для работы с отдельной строкой в наборе используются сечения двумерных массивов: фиксируется старший индекс, который отвечает за номер строки. \0rop inthebuck... Letwellalone\0... \0fterusthedel...

43 Вставка новой строки © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 43 char strings[10][256];... strcpy(strings[size], "Let well alone"); size++; 1.Запись новой строки в первую свободную позицию. 2.Увеличение количества занятых ячеек. Letwellalone\0... \0etwellalone... \0fterusthedel...

44 Удаление строки из набора © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 44 do{ strings[i][j] = strings[size-1][j]; j++; while(strings[size-1][j] != '\0') strings[size-1] = '\0'; size--; 1.Перестановка с последней ненулевой строкой. 2.Запись нуль-терминатора в первый элемент строки двумерного массива с номером size-1. 3.Уменьшение количества свободных строк.

45 Удаление строки из набора (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 45 Letwellalone\0... Hello!\0lalone... \0fterusthedel... Hello!\0lalone... \0ello! lalone... \0fterusthedel...

46 Поиск заданной строки в наборе © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 46 char strings[10][256], s[256];... for(i=0;i

47 Поиск в наборе строки, содержащей заданную подстроку © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 47 char strings[10][256], s[256];... for(i=0;i

48 Конкатенация строк набора © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 48 char strings[10][256], s[2560] = "";... for(i=0;i

49 Конкатенация строк набора (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 49 Letwell\0alone... Hello!\0lalone... Hi!\0!? sthedel... \0 s Letwell s LetwellHello!Hi! s

50 Перестановка строк в наборе © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 50 char strs[10][256], s[2560] = "";... int l1 = strlen(strs[i]); int l2 = strlen(strs[j]); for(k=0;k

51 Перестановка строк в наборе (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 51 Letwell\0alone... Hello!\0lalone... Hi!\0!? sthedel... Hi!\0!? salone... Hello!\0lalone... Letwell\0thedel...

52 Сортировка строк набора (в алфавитном порядке) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 52 Для сортировки набора строк может быть использован любой алгоритм сортировки. Например, алгоритм сортировки методом пузырька. Соотношению x < y ставится в соответствие результат сравнения строк при помощи функции strcmp: s1 strcmp(s1,s2) < 0 т.е. строка s1 по алфавиту должна располагаться выше строки s2.

53 Сортировка методом пузырька © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 53 Letwell\0 Hello! l Hi! !? sl s[0] > s[1] s[1] < s[2]

54 Оптимизация сортировки строк методом пузырька © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 54 Letwell\0 Hello! l Hi! !? sl В процессе сортировки задача перестановки двух строк возникает многократно. Это достаточно трудоемкая операция, которая не может быть выполнена за фиксированное число действий. Для повышения скорости сортировки может быть использован массив целочисленных индексов. idx s

55 Оптимизация сортировки строк методом пузырька (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 55 Letwell\0 Hello! l Hi! !? sl Letwell Hello! l Hi! !? sl idx s s

56 Оптимизация сортировки строк методом пузырька © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 56 Letwell\0 Hello! l Hi! !? sl Работа с отсортированным массивом должна выполняться через полученный индексный массив. Например, для доступа к i-му элементу необходимо использовать следующее выражение: s[idx[i]] idx s

57 Перестановка элементов набора © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 57 Letwell\0 Hello! l Hi! !? sl s[idx[0]] > s[idx[1]] => idx[0] idx[1] s[idx[0]] > s[idx[1]] => idx[0] idx[1] Letwell\0 Hello! l Hi! !? sl 1 0 2

58 58 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» СПАСИБО ЗА ВНИМАНИЕ!