Лекция 14
Найти в массиве размер N индекс k, такой, что все элементы с индексом i<=k имеют один знак, а все элементы с индексом i>k имеют другой знак, причем равенство 0 допускается только для элемента с индексом k (k>0 и k<N-1).
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
-2 |
-1 |
-3 |
-7 |
-12 |
-5 |
0 |
2 |
1 |
3 |
4 |
Процедура Индекс смены знака
! Дано: Массив A размера N
! Найти: Индекс k, для которого все элементы с индексом i<=k имеют один знак, а все
! элементы с индексом i>k имеют другой знак, причем равенство 0 допускается только
! для элемента с индексом k (k>0 и k<N-1)
k := -1
Если A[N-1] != 0 то
Цикл для I от N-2 до 1 (включительно) выполнять
Если A[I] * A[N-1] <= 0 то
k = I
выйти из цикла
Конец если
Конец цикла
Если k > 0 то
Цикл для I от k-1 до 0 (включительно) выполнять
Если A[I] * A[N-1] >= 0 то
k = -1
выйти из цикла
Конец цикла
Конец если
ответ := k
Конец процедуры
int k = -1;
int array[100] = { -1, -2, 0, 4, 11 }; /* Значения первых 5 элементов массива */
int array[] = { 23, -17, 245, 6, -7, 14 }; /* Массив размера 6 */
char str[20] = { 'a', 'b', 'c' }; /* Значения первых 3 элементов массива */
char str1[] = { 'a', 'b', 'c' }; /* Массив размера 3 */
char str2[] = "abc"; /* Массив размера 4 */
В конце строковой константы — некий символ, который обозначает конец строки: символ с кодом 0 (так как символ с кодом 0 — служебный и не был еще занят).
ASCII (American Standard Institute …)
0 – символ конца строки символов
…
10 – символ конца строки в тексте (в Линуксе — один этот символ — конец строки)
…
13 — символ перевода каретки (Line Feed) (в Windows – два символа конца строки 13+10)
(утилиты Линукса dos2unix и unix2dos)
…
32 – пробел
...
48 — '0' (ноль)
49 — '1' (единица)
…
57 — '9' (девятка)
(код цифры → ее значение: value = с — '0', где c - char)
…
65 – 'a'
66 – 'b'
…
90 – 'z'
…
Символ с кодом 0 определяет, где строка кончается.
Проблемы: При отсутствии символа с кодом 0 в строке — может произойти
выход за границу массива при последовательном обращении к символам строки и даже выход за границу доступного сегмента памяти, что приведет к ошибке Segmentation Fault.
Задача 1. Скопировать строку
char *strcpy(char *str1, char *str2) {
while (*(str2++) = *(str1++)); /* значение выражения в условии while равно присвоенному значению */
return –str2; /* Возвращаем адрес символа с кодом 0, завершающего строку */
}
(man strcpy → документация по функции strcpy())
Задача 2. Сравнить две строки
int strcmp(char *str1, char *str2) {
while (*str1) {
if (*str1 > *str2)
return 1;
if (*str1 < *str2)
return -1;
++str1;
++str2;
}
return (*str2 == 0 ? 0 : -1);
}
Лексико-графический порядок — строки упорядочены по алфавиту, начиная с первого символа
|
0 |
... |
|
|
|
s1 |
|
|
|
|
s2 |
|
|
|
|
array |
|
|
|
|
|
|
|
... |
∞ |
|
|
|
|
|
|
'a' |
'b' |
'c' |
\0 |
|
'o' |
'f' |
\0 |
|
|
&s1 |
|
&s2 |
|
|
|
|
|
|
|
N=2
Задача 3. Отсортировать массив строк по возрастанию (исходный код)
/* Массив строк array, размер массива N */
void sort(char *array[], int N) {
int i, j;
char *buf;
for (i = 0; i < N; i++) {
for (j = 0; j < N-1; j++) {
if (strcmp(array[j], array[j+1]) > 0) {
buf = array[j];
array[j] = array[j+1];
array[j+1] = buf;
}
}
}
}