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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сравнение строк в алфавитном порядке © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 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

Сравнение строк в алфавитном порядке (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 Существует два способа реализации данной операции. 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 Операция определения длины строки может быть выполнена двумя способами: 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 int main() { int i,j; char s1[100] = "abcdefghijklmnop"; char s2[10]; int s = 3, e = 8; for(i=s; i

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

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

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

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

Поиск подстроки в строке © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 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]

Поиск подстроки в строке* "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 В языке СИ перевод строки ранится в виде специального символа, ASCII код которого обозначается через Escape- последовательность '\n'. Данный символ не является признаком конца строки в терминах языка СИ. Это позволяет хранить многострочный текст в одной строке: char str[] = "Hello!\nHow are you?\nCan we talk now?\n"; Hello!\nHow are you? Canwe talk now? \0

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

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

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

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

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

Удаление строки из набора © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 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.Уменьшение количества свободных строк.

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

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

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

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

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

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

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

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

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