9. Строковые алгоритмы
Хранение символов в памяти компьютера.
Компьютер оперирует с определенным ограниченным набором символов – алфавитом. Идея хранения символов в памяти компьютера состоит в замене каждого символа его номером в алфавите.
Кодировки символов.
Unicode и ASCII
ASCII - В соответствие с таблицей кодирования ASCII для представления одного символа выделяется 1 байт (8 бит). Набор из 8 ячеек может принять 28 = 256 различных значений. Первые 128 значений (от 0 до 127) постоянны и формируют так называемую основную часть таблицы, куда входят десятичные цифры, буквы латинского алфавита (заглавные и строчные), знаки препинания (точка, запятая, скобки и др.), а также пробел и различные служебные символы (табуляция, перевод строки и др.). Значения от 128 до 255 формируют дополнительную часть таблицы, где принято кодировать символы национальных алфавитов.
Работа со строками
Сравнение двух строк
int strcmp(shar *s1, char *s2)
{
int i = 0;
while (s1[i] != '\0' && s2[i] != '\0')
{
if (s1[i] < s2[i])
{
return -1;
}
else
{
if (s1[i] > s2[i])
{
return 1;
}
}
++i;
}
if (s1[i] != '\0')
{
return 1;
}
if (s2[i] != '\0')
{
return -1;
}
return 0;
}
Нахождение длины строки
int strlen(shar *s)
{
int i = 0;
while (s[i] != '\0')
{
++i;
}
return i;
}
Копирование строки
void strcpy(shar *dst, char *src)
{
int i;
for (i = 0; src[i] != '\0'; ++i)
{
st[i] = src[i];
}
dst[i] = '\0';
}
Объединение
void strcat(char *dst, char *src)
{
int i = 0;
for (i = 0; dst[i] != '\0'; ++i);
int j;
for (j = 0; src[j] != '\0'; ++j)
{
dst[i++] = src[j];
}
}
Поиск подстроки в строке
int strstr(char *dst, char *src)
{
int n = strlen(dst);
int m = strlen(src);
for (int i = 0; i <= n - m; ++i)
{
int j = 0;
while (src[j] != '\0' && src[j] == dst[i + j])
{
++j;
}
if (src[j] == '\0')
{
return i;
}
}
return -1;
}
Свойства конкатенации.
Операция конкатенации определяется
для типов
данных,
имеющих структуру последовательности
(список, очередь, массив и
ряд других). В общем случае, результатом
конкатенации двух объектов 
и 
является
объект 
,
полученный поочерёдным добавлением
всех элементов объекта
,
начиная с первого, в конец объекта
.
Из соображений удобства и эффективности различают две формы операции конкатенации:
Модифицирующая конкатенация. Результат операции формируется в левом операнде.
Не модифицирующая конкатенация. Результатом является новый объект, операнды остаются неизменными.
Лексикографический
порядок — отношение
линейного порядка на
множестве слов длины 
над
некоторым упорядоченным алфавитом 
.
Своё название лексикографический
порядок получил по аналогии с сортировкой
по алфавиту в словаре.
Слово a предшествует
слову b (
),
если первые 
символов
слов совпадают, а 
символ
слова a меньше
(относительно отношения порядка,
заданного в
)
символа
слова b.
10.Линейные динамические структуры данных.
Стек - последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной списка
void push(node ***s, int x)
{
node *newnode = (node*)malloc(sizeof(node));
newnode->val = x;
newnode->next = *s;
*s = newnode;
}
int pop(node **s)
{
int x = (*s)->val;
node *old = *s;
*s = (*s)->next;
free(old);
return x;
}
Очередь - последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (конец или хвост очереди), а исключение – с другой стороны (начало или голова очереди).
Принцип функционирования:
FIFO (First - In - First- Out - “первым пришел – первым исключается").
Элементами очередей могут быть любые однотипные данные.
Дек (двусвязная очередь) -
особый вид очереди. Последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка.
Принцип функционирования:
одновременно FIFO и LIFO