2015-10-22
1089
Иногда надо скопировать матрицу A размером M на N в одномерный массив B размером
M*N. Очевидно, что при копировании по строкам (сначала первая строка, затем вторая и т.д.)элемент первой строки A[0][j] надо скопировать в B[j], элементы второй строки A[1][j] в B[N+j] и т.д. Отсюда следует, что для любой строки i элемент A[i][j] копируется в B[i*N+j]. теперь осталось только в двойном цикле перебрать все элементы матрицы.
for (i = 0; i < M; i ++)
for (j = 0; j < N; j ++)
B[i*N+j] = A[i][j];
Заметим, что если надо провести какую-то операцию со всеми или некоторыми (стоящими
подряд) элементами матрицы и для одномерного массива уже есть соответствующая процедура, ее можно использовать, учитывая, что имя строки массива (например, A[0]) является указателем на начальный элемент этой строки. При этом надо учитывать, что в памяти элементы матрицы расположены по строкам. Например, функция вычисления суммы элементов (см. массивы) может применяться для матрицы так:
s0 = Sum(A[0], N); // суммастроки 0
s14 = Sum(A[1], 4*N); // суммастрок 1-4
sAll = Sum(A[0], M*N); // сумма всех строк
|
|
|
Сортировка
Мы уже научились сортировать массивы целых и вещественных чисел, а теперь надо сор-
тировать строки. Можно придумать разные способы, но наиболее часто встречается алфавитная сортировка. При сортировке строк возникают две проблемы.
1. Определить, какая из двух строк «меньше», то есть какая из двух должна стоять выше.
2. Сортировка массивов чисел предусматривает перестановку элементов массива. В случае строк это связано с копированием больших объемов данных, что крайне невыгодно.Начнем с первой. Мы говорили, что есть функция сравнения строк strcmp, которая возвращает нуль, если строки равны, и не нуль, если они разные. Оказывается, эта функция возвращает «разность» этих строк, то есть разность кодов их первых отличающихся символов.Если функция вернула отрицательное число, то первая строка «меньше» второй и стоит по алфавиту раньше, если положительное – наоборот. Здесь надо учитывать, что сравнение идет по таблице кодов, и коды заглавных букв меньше, чем коды строчных (и для русских, и для английских).
Вторая проблема более серьезная и решается с помощью указателей. Сначала выделим в
памяти массив указателей на строки и сделаем так, чтобы i - ый указатель указывал на i - ую
строку массива. Теперь достаточно правильно расставить указатели и сортировка будет выполнена – к строкам можно будет обращаться в алфавитном (или каком-либо другом) порядке с помощью этих указателей. Процедура сортировки методом пузырька выглядит так:
void SortStrings (char *s[], int n) // *s[] – массивуказателей
{ // n – число строк
char *p;
int i, j;
for (i = 0; i < n-1; i ++)
for (j = n-1; j > i; j --)
|
|
|
if (strcmp(s[j-1],s[j]) > 0) {
p = s[j]; s[j] = s[j-1]; // перестановка УКАЗАТЕЛЕЙ
s[j-1] = p;
}
}
Эту функцию использует приведенная ниже программа, которая сортирует строки и выводит их на экран уже в алфавитном порядке.
Main()
{
char s[20][80]; // массив из 20 строк
char *ps[20]; // массив из 20 указателей на строки
int i, count;
// здесь нужно ввести строки и записать
// в переменную count их количество
for (i = 0; i < count; i ++) // расставитьуказатели
ps[i] = s[i];
