char strng[] = "The rain in Spain";
int i = strcspn(strng, " in");
Этот пример возвращает 3 (расположение первого пробела в строке strng) переменной i.
Функция strpbrk просматривает строку и определяет первое вхождение любого символа из образца.
Прототипфункции strpbrk:
char* strpbrk(const char* target, const char* pattern)
Функция strpbrk ищет в строке target первое вхождение любого символа из образца pattern. Если символы из образца не содержатся в строке, функция возвращает 0.
char *str = "Hello there how are you";
char *substr = "hr";
char *ptr;
ptr = strpbrk(str, substr);
cout « ptr « endl;
Вы увидите на экране строку "herehowareyou", потому что 'h' встречается в строке str раньше, чем 'r'.
Прототип функции strstr:
char* strstr(const char *str, const char *substr);
Функция ищет в строке str первое вхождение подстроки substr. Функция возвращает указатель на первый символ найденной в строке str подстроки substr. Если строка substr не обнаружена в строке str, функция возвращает 0.
char str[] = "Hello there! how are you";
char substr[] = "how";
char *ptr;
ptr = strstr (str, substr);
cout « ptr « endl ;
Это приведет к выводу строки "howareyou", поскольку в строке str , была обнаружена подстрока "how". Указатель ptr содержит адрес остатка первоначальной строки, начинающегося с подстроки "how".
Библиотека функций для работы со строками имеет функцию strtok, которая дает вам возможность разбить строку на подстроки на основании заданного набора символов-ограничителей.
Подстроки иногда называются лексемами.
Прототип функции strtok:
char* strtok(char *target, const char * delimiters);
Функция разбивает строку на лексемы, согласно символам-ограничителям, заданным в параметре delimeters. В следующем примере показано, как работать с этой функцией и как получать лексемы, на которые была разбита строка. Функция strtok вводит символ '\0' после каждой лексемы. (Опять же не забудьте сохранить копию вашей строки в другой строковой переменной.)
Библиотека <stdlib.h>. Здесь содержатся ф-ии преобразования строки в числа.
1) atoi(st) – преобр целое число строк (пр: r=atoi(“_ _ +121”)
2) atol(st)- преобрстр string втип long
3) atof(st) – преобрвтип double
Если строку нельзя преобразовать в число возвращается нуль
Библ. <ctype.h>. В этой библ содержатся ф-ии для работы форматом.
1) isalpha(ch) истина если симв-буква
2) isalnum(ch) истина если симв-бук или цифра
3) iscntrl(ch) истина если симв
4) isdigit(ch) истина если симв десятич цифры
5) islower(ch) истина если строчн буква
6) ispunct (ch) истина если симв пункт
7) isspace(ch) ис если симв пустого места или пробела
8) islower(ch) опр принадл к верх рег
9) isupper(ch) преобр к верхнему регистру
10) tolower(ch) toupper(ch) перевод в ниж и верх рег
Строка как параметр функции
Исп. строки в качестве парам ф-ии аналогично исп массивов в др. типа, однако имя масс есть ук. на его …, а имя строки явл-ся ук.перем., следовательно его значен может изм-сяю.
22. Сортировка данных. Алгоритмы сортировки.
Под сортировкой понимают процесс перестановки объектов данного множества в определённом порядке. Цель сорт.- обеспечить последующий поиск элем в отсортированном множестве. Метод сортировки разделяют на 2 категории:
1) Внутр.-сорт. масс.(масс располог во внут или отсорт пам)
2) Внешн – сорт ф-ов (ф. расп во внеш пам)
Как правило, сортируемые данные располагаются в массиве. А простейшем случае-это числовые мА-ы, однако для алг более хар-на сит, когда сорт масс структур. Поле, по знач кот производится сорт наз-ся ключом сорт. Основное требование к методам сорт-экономное исп пам. В этом смысле говорят что сортировку нужно вып insite – на том же месте.
Удобной мерой эффективности алг сорт на месте явл:
1) число С(compore) необходимых сравнений ключей
2) число M (move) необходимых пересылок элем-в.
Эффективн. алг. сорт треб порядка С~N*log2N сравнений где N – число элем сортируемого масс. Эти методы требуют меньшего числа оп,но эти оп. более сложные.
Простые методы сорт порядка С~N2 сравнений:
1) Они хорошо подходят для разъяснения св-в большинства принципов сорт.
2) Прогр. основан. на этих методах лёгкие для понимания и коротки.
3) При достаточно малых значениях N они раб также быстро как и сложные => больших N исп не эффективно.
23. Сортировка выбором.
1) выбир-ся элем с наиб значением ключа и меняется местами с послед элем.
2) выбирается наиб элем из первых (n-1) элем-в и меняется местами с послед элем и т.д.
void sort (float a[N], int n)
{float t; int k,i,j;
for (k=n;k>1;k--)
{i=0;
for (i=1;i<k;i++)
if (a[j]<a[i]) j=I;
t=a[k-1];
a[k-1]=a[j];
a[j]=t;}}
Эффективность сортр число C=(N-1)*N/2~N2 M=(3+N/4)*(N-1)~N2
24. Сортировка обменом.
1) Просм массив сначала при этом сравнив 2 сосед элем ai,ai+1 если ai> ai+1 то элем-ы меняются местами в рез 1-го просмотра масс-а мах знач переместится в конец.
2) Повторив ту же процедуру до предпоследнего элем и т.д. Сорт законч либо после очередного прохода не сделано ни одного обмена либо сделано (n-1) просмотров.
void sort (struct str a[N], int n)
{struct str t;
int fl,I,j;
do {fl=0; n--;
for (i=0;i<n;i++)
if (a[i].x>a[i+1].x)
{t=a[i]; a[i]=a[i+1]; a[i+1]=t; fl=1;}
}while (fl);
б) for(i=0;i<n-1;i++)
for(j=0;j<n-i-1;j++)
if (a[i].x>a[i+1].x)
{t=a[i]; a[i]=a[i+1]; a[i+1]=t;}
Эффективность сорт: C=N2/4 M=1.5*(N2/4)
25. Сортировка включением.
Элем разделяются на упорядоч инее упорядоч части.В начале упоряд часть содержит только один элем очередной элемент из начала неуп части вставляется на подход место в уп часть при этом уп часть удлин на 1 мм а неуп укорач. Сорт заканч при исчезнов не упорядоч части
voidsort (floata[N],intn)
{float t; int i,j;
for (j=1;j<n;j++)
{t=a[j];//заполн знач кот нужно поставить на своё место в 1 части
i=j-1;
while (i>=0 &&t<a[i])
{a[i+1]=a[i];i--;}//продвиж дырки в лев части мас до той позиц в кот долж быть включ элем
a[i+1]=t;}}//вкл элем в левую часть
Эффективность сорт: C=((N-2)+(N+1)*(N-2)/2)/2) M=(3*(N-2)+(N+5)*(N-2)/2)/2
26. Динамические структуры данных. Линейные списки.
Память под данные выд либо на этапе компиляции, либо во время вып прогр. с пом опер меню. В обоих случ выд непрерыв уч пам. Если же разм заранее не известен, то пам выд по мере необх отдельн блоками связ-ых др с другом с пом ук. Такой способ организации данных наз-ся дин. стр. данных. К дин.стр. отн линейные списки, стеки, очереди и бинарные деления. Они различаются способом связи отдельн элем и допуст опер.
Дин стр прим для более эффек раб прогр:
1) в задачах с многокр сорт данных( данные удобно предст в виде списка, т.к.не требуется переставлять элем, а нужно изм лишь ук.
2) в задачах поиска, когда важна скорость данные лучше всего представлять в виде бинарного дерева.
Элем люб дин стр данных предст собой стр сод-ую по крайней мере 2 поля: для хранения данных, для ук.
Линейный список - это конечная последовательность однотипных элементов (узлов), возможно, с повторениями. Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться.