Рацеев С.М. Программирование на языке Си

return a[*(const int *)p1] - a[*(const int *)p2];

}

int main()

{

int i, ind[N];

…/* заполнение массива a */ for(i = 0; i < N; i++)

ind[i] = i;

qsort(ind, N, sizeof(*ind), compare); return 0;

}

4. Сортировка двумерных массивов

Пусть a[M][N] – некоторая матрица. На множестве строк данной матрицы (a[0], a[1],…,a[M-1]) определим числовую функцию F. Например, функция F может возвращать значение первого элемента строки (F(a[i]) = a[i][0]), сумму элементов строки (F(a[i]) = a[i][0] + a[i][1] + … + a[i][N-1]) и т.д. Задача состоит в том, чтобы упорядочить строки матрицы таким образом, чтобы последовательность F(b[0]), F(b[1]),…, F(b[M-1]) была неубывающей, где символом b обозначена новая матрица, полученная из матрицы a путем перестановки строк.

Для решения данной задачи имеется несколько подходов. Вопервых, можно действительно переставлять строки матрицы a, но для матриц с большим значением числа N (число столбцов) это неэффективно. Во-вторых, можно завести массив индексов int ind[M] ={0, 1,…, M-1} и переставлять в нем элементы таким образом, что-

бы последовательность F(a[ind[0]]), F(a[ind[1]]),…, F(a[ind[M-1]])

удовлетворяла условию задачи. При этом матрица a останется без изменений, а обращение к “новой” матрице b будет происходить следующим образом:

a[ind[i]][j], 0 ≤ i < M, 0 ≤ j < N.

Такой подход для одномерных массивов мы уже рассматривали выше. Поэтому (для разнообразия) остановимся на третьем подхо-

321

де (сопряженным со вторым), который заключается в рассмотрении дополнительного массива указателей int *pa[M], где pa[i] содержит адрес i-ой строки матрицы a, i = 0,…,M-1.

Изначально массив pa инициализируется следующим обра-

зом:

for(i = 0; i < M; i++) pa[i] = a[i];

Затем с помощью алгоритма быстрой сортировки происходит преобразование массива указателей pa так, чтобы последовательность F(pa[0]), F(pa[1]),…, F(pa[M-1]) удовлетворяла начальному условию. В алгоритме ниже в качестве функции F выступает функция, которая возвращает первый элемент строки. Поэтому вместо записи F(pa[i]) будем использовать запись * pa[i].

#include<stdio.h>

#define M 5 /* Число строк матрицы */ #define N 10 /* Число столбцов матрицы */

/* вывод матрицы на экран через массив индексов pa */ void Print(int *pa[], int m, int n)

{

int i, j;

for (i = 0; i < m; i++)

{

for (j = 0; j < n; j++) printf("%5d", pa[i][j]);

printf("\n");

}

}

/* сортировка массива pa по первым элементам массива a: */ void QuickSort (int *pa[], int left, int right)

{

int i, j, buf; int x;

i = left;

322

j = right;

x = *pa[(left + right)/2]; do

{

while (*pa[i] < x) i++;

while (x < *pa[j]) j--;

if (i <= j)

{

buf = pa[i]; pa[i] = pa[j]; pa[j] = buf; i++;

j--;

}

} while( i <= j);

if (left < j) QuickSort (pa, left, j);

if (right > i) QuickSort (pa, i, right);

}

int main()

{

int i, a[M][N], /* исходная матрица */

*pa[M]; /* массив указателей */ …/* инициализация матрицы a */

/* инициализация массива индексов pa: */ for(i = 0; i < M; i++)

pa[i] = a[i];

/* вывод исходной матрицы a: */ Print(pa, M, N);

/* сортировка элементов массива указателей pa */ QuickSort(pa, 0, M-1);

/* вывод упорядоченной матрицы по первым элементам строк: */

Print(pa, M, N); return 0;

}

323

5. Сортировка строк

Рассмотрим алгоритмы сортировки строк. При этом задача состоит в том, чтобы выделить слова из введенной строки и расположить их в лексикографическом порядке на основе ASCII кодов символов. В качестве основы возьмем очень быстрые алгоритмы выделения всех слов из строки, приведенные в параграфе 8.7, а в качестве сортировки используем алгоритм быстрой сортировки (QuickSort), где сравнение слов будет происходить с помощью функции strcmp из библиотеки <string.h>.

Случай 1. Если слова в строке разделены символами ‘\0’ (см. случай 1 параграфа 8.7), то можно определить массив указателей, содержащий адреса выделенных слов. В этом случае сортируются ссылки на данные слова.

#include <stdio.h> #include <string.h>

#define DELIMITERS " .,:;?!\n\t" /* символы-разделители */ #define SIZE 100 /* максимальный размер массива указаателей */

#define N 1024 /* размер строки */

/* сортировка строк на основе быстрой сортировки */ void QuickSortWords (char *a[], int left, int right)

{

int i, j;

char *x, *buf; i = left;

j = right;

x = a[(left + right)/2]; do

{

while (strcmp(x, a[i]) > 0) i++;

while (strcmp(x, a[j]) < 0) j--;

if (i <= j)

{

324

buf = a[i]; a[i] = a[j]; a[j] = buf; i++; j--;

}

} while( i <= j);

if (left < j) QuickSortWords (a, left, j);

if (right > i) QuickSortWords (a, i, right);

}

int main( )

{

char sentence[N]; /* строка-предложение */ char *pstr[SIZE]; /* маасив указателей */ int i, j, flag[256] = {0}, n;

fgets(sentence, N, stdin);

for (i = 0; DELIMITERS[i]; i++) flag[DELIMITERS[i]] = 1;

for (i = 0; sentence[i] && flag[sentence[i]]; i++) sentence[i] = '\0';

n = 0;

/* выделяем слова в строке sentence и адреса слов записываем в массив pstr:

*/

while (sentence[i])

{

pstr[n++] = &sentence[i];

while (sentence[i] && !flag[sentence[i]]) i++;

j = i;

while (sentence[i] && flag[sentence[i]]) i++;

sentence[j] = '\0';

}

/* сортируем слова в строке через массив ссылок pstr: */

QuickSortWords(pstr, 0, n - 1);

/* выводим слова в лексикографическом порядке */ for(i = 0; i < n; i++)

puts(pstr[i]);

325

return 0;

}

Случай 2. Если слова выделяются из строки-предложения путем копирования слов в динамические строки (см. случай 2 параграфа 8.7), то адреса этих динамических строк будем сохранять в массиве ссылок pstr, а потом сортировать с помощью функции QuickSortWords (из предыдущего случая) не сами строки, а их адреса.

#include <stdio.h> #include <stdlib.h> #include <string.h>

#define DELIMITERS " .,:;?!\n\t" /* символы-разделители */ #define SIZE 100 /* максимальный размер массива указаателей */

#define N 1024 /* размер строки */

char *pstr[SIZE];

int n, i, j, flag[256] = {0};

for (i = 0; DELIMITERS[i]; i++) flag[DELIMITERS[i]] = 1;

fgets(sentence, N, stdin);

for (i = 0; sentence[i] && flag[sentence[i]]; i++)

;

n = 0;

while (sentence[i])

{

j = i;

while (sentence[i] && !flag[sentence[i]]) i++;

/* выделяем память для очередного слова: */ pstr[n] = (char *)malloc((i - j + 1) * sizeof(char)); /* копируем очередное слово: */ strncpy(pstr[n], &sentence[j], i - j);

326

pstr[n][i - j] = '\0'; n++;

while (sentence[i] && flag[sentence[i]]) i++;

}

/* функция QuickSortWords прописана в случае 1 */

QuickSortWords(pstr, 0, n - 1);

/* выводим слова в лексикографическом порядке */ for(i = 0; i < n; i++)

puts(pstr[i]); return 0;

}

327

Приложение 4. СОРТИРОВКА ФАЙЛОВ И СПИСКОВ

1.Сортировка двоичных файлов

Впараграфе «Двоичные файлы» был рассмотрен пример с созданием и выводом двоичного файла, содержащего сведения о работниках некоторой организации: фамилия работника, год рождения, заработная плата. Отсортируем все записи в файле, например по году рождения. Для ускорения алгоритма используем динамический массив, в который выгрузим весь файл (если у нас имеется достаточно оперативной памяти). В качестве алгоритма сортировки для удобства понимания читателем используем пузырьковую сортировку, которая легко может быть трансформирована в любой другой алгоритм.

#include<stdio.h> struct WORKER

{

char name[20]; int year;

float earnings;

};

/* размер файла в байтах */ long Size(char *fileName)

{

FILE *f; long n;

if ((f = fopen(fileName, "rb")) == NULL) return -1;

fseek(f, 0, SEEK_END); n = ftell(f);

fclose(f); return n;

}

/* сортировка файла на основе пузырьковой сортировки */

328

int SortFile(char *fileName)

{

FILE *f;

struct WORKER *a; /* динамический массив структур */ struct WORKER buf;

long n, i, r; int flag;

/* открываем файл для чтения и записи */ if ((f = fopen(fileName, "r+b")) == NULL)

return 1;

/* вычисляем количество записей в файле */ n = Size(fileName)/sizeof(struct WORKER);

/* выделяем память для динамического массива */

a = (struct WORKER *)malloc(n * sizeof(struct WORKER));

/* проверяем успешность выделения памяти и пытаемся выгрузить файл в массив */

if (a == NULL || fread(a, sizeof(struct WORKER), n, f) != n)

{

fclose(f); return 2;

}

/* сортируем массив a по году рождения */ r = n;

do

{

flag = 0;

for(i = 1; i < r; i++)

if (a[i-1].year > a[i].year)

{

buf = a[i]; a[i] = a[i-1]; a[i-1] = buf; flag = 1;

}

r--; }while(flag);

/* устанавливаем файловый указатель в начало файла */ rewind(f);

/* записываем отсортированный массив в файл */

329

fwrite(a, sizeof(struct WORKER), n, f); fclose(f);

free(a); return 0;

}

2. Сортировка линейных списков

Отсортируем список целых чисел методом прямого выбора.

/* элемент списка */ typedef struct ELEMENT

{

int data;

struct ELEMENT *next; } ELEMENT;

/* сортировка линейного списка методом прямого выбора */ void SortList(ELEMENT *head)

{

ELEMENT *q = head->next, *min, *t; int buf;

/* если список пустой или одноэлементный, то сортировка не требуется */

if(q == NULL || q->next == NULL) return;

for( ; q != NULL; q = q->next)

{

min = q;

for(t = q->next; t != NULL; t = t->next) if (t->data < min->data)

min = t; buf = q->data;

q->data = min->data; min->data = buf;

}

}

330