Лекція "Сортування інших структур даних"

Лекція № 7

Тема: Сортування інших структур даних

Мета: Ознайомится сортуванням інших структур даних.

 

План

1. Сортування рядків.
2. Сортування структур.

 

Навчально-методичне забезпечення, ТЗН: конспект лекцій.

 

Література:

1. [2] стор. 300-305.
2. [3] стор. 89-102.

 

ВИКЛАД ЛЕКЦІЙНОГО МАТЕРІАЛУ

 

1. Сортування рядків

Сортування рядків є поширеним завданням програмування. Рядки найлегше сортувати, коли вони зберігаються в таблиці рядків. Таблиця рядків — це просто масив рядків. А масив рядків — це двовимірний масив символів, в якому кількість рядків в таблиці визначається розміром лівого виміру, а максимальна довжина рядка — розміром правого виміру. Нижченаведена строкова версія швидкого сортування приймає масив рядків, в якому розмір кожного рядка обмежений десятьма символами. (Можете змінити цю довжину, якщо хочете.) Ця версія сортує рядки в лексикографічному порядку.

/* Швидке сортування рядків. */

voidquick_string(charitems[][10], intcount)

{

qs_string(items, 0, count-1);

}

 

voidqs_string(char items[][10], intleft, intright)

{

registerint i, j;

char *x;

chartemp[10];

 

  i = left; j = right;

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

 

do {

while((strcmp(items[i],x) < 0) && (i <right)) i++;

while((strcmp(items[j],x) > 0) && (j >left)) j--;

if(i <= j) {

strcpy(temp, items[i]);

strcpy(items[i], items[j]);

strcpy(items[j], temp);

      i++; j--;

   }

  } while(i <= j);

if(left< j) qs_string(items, left, j);

if(i <right) qs_string(items, i, right);

}

Зверніть увагу, що у фрагменті порівняння тепер використовується функція strcmp(). Ця функція повертає негативне число, якщо перший рядок лексикографічно менше за другу, повертає нуль, якщо рядки рівні, і позитивне число, якщо перший рядок лексикографічно більше за другу. Також слід зазначити, що для обміну двох рядків потрібно три виклики функції strcpy().

Майте на увазі, що функція strcmp() уповільнює сортування з двох причин. По-перше, в програмі з'являється виклик функції, що завжди віднімає час. По-друге, сама функція strcmp() виконує декілька порівнянь, щоб визначити, який з двох рядків більше. У першому випадку, якщо швидкість дуже важлива, можна помістити код порівняння рядків безпосередньо у функцію сортування, продублювавши код функції strcmp(). У другому випадку немає ніякого способу уникнути порівняння рядків, оскільки за визначенням це саме те, що вимагається в цьому завданні. Ті ж міркування відносяться і до функції strcpy(). Обмін двох рядків з допомогою strcpy() включає виклик функції і посимвольний обмін вмісту рядків — кожна з цих операцій займає час. Накладні витрати на виклик функції можна усунути, вставивши код копіювання прямо в алгоритм сортування. Проте той факт, що обмін двох рядків означає обмін окремих символів (один за іншим), змінити неможливо.

Нижче приведена проста функція main(), що демонструє роботу функції швидкого сортування рядків quick_string():

#include<stdio.h>

#include<string.h>

 

voidquick_string(charitems[][10], intcount);

voidqs_string(char items[][10], intleft, intright);

 

charstr[][10] = { "один",

                   "два",

                   "три",

                   "чотири"

                 };

intmain(void)

{

int i;

quick_string(str, 4);

for(i=0; i<4; i++) printf("%s ", str[i]);

return 0;

}

2. Сортування структур

У більшості застосовних програм, в яких використовується сортування, передбачено сортування сукупностей даних. Наприклад, списки поштового розсипу, складські бази даних і журнали співробітників містять набори різнотипних даних. Як вам відомо, в програмах на мові C сукупності даних зазвичай зберігаються в структурах. Хоча структура зазвичай містить декілька членів, структури, як правило, сортуються тільки по одному полю-членові, який використовується як ключ сортування. За винятком вибору ключа, прийоми сортування структур нічим не відрізняються від прийомів сортування інших типів даних.

Щоб проілюструвати приклад сортування структур, давайте створимо структуру під назвою address, у якій можна зберігати поштову адресу. Подібна структура може застосовуватися в програмі поштової розсилки. Опис структури address показано нижче:

structaddress {

charname[40];   /* ім'я */

charstreet[40]; /* вулиця */

charcity[20];   /* місто */

charstate[3];   /* штат */

charzip[11];    /* індекс */

};

Оскільки представляється розумним організувати список адрес у вигляді масиву структур, в цьому прикладі припустимо, що процедура сортування сортуватиме масив структур типу address. Така процедура показана нижче. Вона сортує адреси по поштовому індексу.

/* Швидке сортування структур типу address. */

voidquick_struct(structaddressitems[], intcount)

{

qs_struct(items,0,count-1);

}

voidqs_struct(struct addressitems[], intleft, intright)

{

registerint i, j;

char *x;

structaddresstemp;

  i = left; j = right;

  x = items[(left+right)/2].zip;

do {

while((strcmp(items[i].zip,x) < 0) && (i <right)) i++;

while((strcmp(items[j].zip,x) > 0) && (j >left)) j--;

if(i <= j) {

temp = items[i];

items[i] = items[j];

items[j] = temp;

      i++; j--;

    }

  } while(i <= j);

if(left< j) qs_struct(items, left, j);

if(i <right) qs_struct(items, i, right);

}

 

Контрольні запитання:

1. Дайте визначення рядка.
2. Дайте визначення структури.
3. Дайте визначення сортування.