Робота з великими масивами

Розмір одного масиву даних повинний бути не більше 64 Кб. Але в реальних задачах можуть використовуватися масиви, що вимагають ОП, більшої ніж 64 Кб. Наприклад, масив даних типу float з 300 рядків і 200 стовпців потребує для розміщення 300 * 200 * 4 = 240000 байтів.

Для вирішення поставленої задачі можна використовувати масив покажчиків і динамічне виділення ОП для кожного рядка матриці. Рядок матриці не повинен перевищувати 64 Кб. У вищенаведеному прикладі ОП для рядка складає всього 800 байтів. Для виділення ОП з купи кожен рядок повинний мати покажчик. Для всіх рядків масиву треба оголосити масив покажчиків, по одному для кожного рядка. Потім кожному рядку масиву виділити ОП, привласнивши кожному елементу масиву покажчиків адресу початку розміщення рядка в ОП, і заповнити цей масив.

У запропонованому лістингу представлена програма для роботи з великим масивом цілих значень: з 300 рядків і 200 стовпців. Для розміщення він вимагає: 200 * 300 * 2 = 120000 байтів. При формуванні великого масиву використовується р - статичний масив покажчиків

При виконанні програми перебираються i-номери рядків масиву. Для кожного рядка за допомогою функції malloc () виконується запит ОП з купи і формується p[i] - значення покажчика на дані i -рядки. Потім перебираються i -номери рядків від 1 до 200. Для кожного рядка перебираються j-номери стовпчиків від 1 до 300. Для кожного i та j за допомогою генератора випадкових чисел формуються і виводяться *(р[i] + j) - значення елементів масиву. Після обробки масиву за допомогою функції free (p[i]) звільняється ОП виділена i-рядку масиву.

У наведеній нижче програмі використовуються звертання до Ai,j - елементів масиву у вигляді: *(p[i]+j), де p[i] + j - адреса Ai,j-елемента масиву.

#include <conio.h>

#include <stdlib.h>

#include <stdio.h>

void main()

{

int *p[200], i, j;

clrscr();

randomize();

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

/* Запит ОП для рядків великого масиву: */

p[i] = (int*) malloc (300 * sizeof (int));

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

for (j = 0; j < 300; j++)

{

*(p[i] + j) = random(100);

printf("%3d", *(p[i] + j));

if ((j + 1) % 20 == 0)

printf ("\n");

}

/* Звільння ОП рядків великого масиву: */

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

free(p[i]);

}

У програмі використовується р - масив покажчиків.

1.10.2 Вільні масиви та покажчики

Термін "вільний" масив відносять до двовимірних масивів. Вони можуть бути будь-якого типу, у тому числі int, float, char і типу структура. Вільний масив - це двовимірний масив, у якому довжини його рядків можуть бути різними. Для роботи з вільними масивами використовуються масиви покажчиків, що містять в собі кількість елементів, рівну кількості рядків вільного масиву. Кожен елемент масиву покажчиків містить адресу початку рядка значень вільного масиву. ОП виділяється для кожного рядка вільного масиву, наприклад за допомогою функції malloc (), і звільняється функцією free (). Для того щоб виконати функцію malloc (), треба визначити кількість елементів у рядку, наприклад із вводу користувача або яким-небудь іншим способом. У нульовому елементі кожного рядка вільного масиву зберігається число, рівне кількості елементів даного рядка Дані в кожен рядок можуть вводитися з файлу або з клавіатури в режимі діалогу. Приклад вільного масиву цілих чисел приведений на рис 1.12:

У масиві на рис. 1.12 три рядки; у нульовому стовпці кожного рядка стоїть кількість елементів даного рядка. Далі - значення елементів матриці.

Приклад оголошення вільного масиву цілих, тобто статичного масиву покажчиків на дані типу int:

int *а[100];

Для масиву а приділяється ОП для 100 покажчиків на значення цілого типу, по одному покажчику на кожний з 100 рядків вільного масиву. Після визначення кількості елементів рядка для значень рядка повинна бути виділена ОП і сформоване значення покажчика в змінній a[i]. Цей покажчик посилається на область ОП, виділену для значень і-рядка матриці. Тільки після цього можна заносити в цю ОП значення елементів вільного масиву.

Реально ОП - це лінійна послідовність перенумерованих байтів. Елементи рядків вільного масиву можуть бути розташовані підряд або несуміжними відрізками ОП, виділеними для рядків.

1.11 Символьні рядки

1.11.1 Основні відомості про представлення рядків

Символьний рядок представляє собою набір з одного або більше символів.

Приклад: "Це рядок"

В мові Сі немає спеціального типу даних, який можна було б використовувати для опису рядків. Замість цього рядки представляються у вигляді масиву елементів типу char. Це означає, що символи рядка розташовуються в пам'яті в сусідніх комірках, по одному символу в комірці.

Необхідно відмітити, що останнім елементом масиву є символ '\0'. Це нульовий символ (байт, кожний біт якого рівний нулю). У мові Сі він використовується для того, щоб визначати кінець рядка.

Примітка. Нульовий символ - це не цифра 0; він не виводиться на друк і в таблиці символів ASCII (див. додаток) має номер 0. Наявність нульового символу передбачає, що кількість комірок масиву повинна бути принаймні на одну більше, ніж число символів, які необхідно розміщувати в пам'яті. Наприклад, оголошення

char str[10];

передбачає, що рядок містить може містити максимум 9 символів.

Основні методи ініціалізації символьних рядків.

• char str1[]= "ABCdef";

• char str2[]={'A', 'B', 'C', 'd', 'e', 'f',0};

• char str3[100];

gets(str3);

• char str4[100];

scanf("%s",str4);

Усі константи-рядки в тексті програми, навіть ідентично записані, розміщуються за різними адресами в статичній пам'яті. З кожним рядком пов'язується сталий покажчик на його перший символ. Власне, рядок-константа є виразом типу "покажчик на char" зі сталим значенням - адресою першого символу.

Так, присвоювання p="ABC" (p - покажчик на char) встановлює покажчик p на символ 'A'; значенням виразу *("ABC"+1) є символ 'B'.

Елементи рядків доступні через покажчики на них, тому будь-який вираз типу "покажчик на char" можна вважати рядком.

Необхідно мати також на увазі те, що рядок вигляду "х" - не те ж саме, що символ 'x'. Перша відмінність: 'x' - об'єкт одного з основних типів даних мови Сі (char), в той час, як "х" - об'єкт похідного типу (масиву елементів типу char). Друга різниця: "х" насправді складається з двох символів - символу 'x' і нуль-символу.

1.11.2 Функції роботи з рядками

1. Функції введення рядків.

Прочитати рядок із стандартного потоку введення можна за допомогою функції gets (). Вона отримує рядок із стандартного потоку введення. Функція читає символи до тих пір, поки їй не зустрінеться символ нового рядка '\n', який генерується натисканням клавіші ENTER. Функція зчитує всі символи до символу нового рядка, додаючи до них нульовий символ '\0'.

Синтаксис:

char *gets(char *buffer);

Як відомо, для читання рядків із стандартного потоку введення можна використовувати також функцію scanf () з форматом %s. Основна відмінність між scanf () і gets () полягає у способі визначенні досягнення кінця рядка; функція scanf () призначена скоріше для читання слова, а не рядка. Функція scanf () має два варіанти використання. Для кожного з них рядок починається з першого не порожнього символу. Якщо використовувати %s, то рядок продовжується до (але не включаючи) наступного порожнього символу (пробіл, табуляція або новий рядок). Якщо визначити розмір поля як %10s, то функція scanf () не прочитає більше 10 символів або ж прочитає послідовність символів до будь-якого першого порожнього символу.

2. Функції виведення рядків.

Тепер розглянемо функції виведення рядків. Для виведення рядків можна використовувати функції puts () і printf ().

Синтаксис функції puts ():

int puts(char *string);

Ця функція виводить всі символи рядка string у стандартний потік виведення. Виведення завершується переходом на наступний рядок.

Різниця між функціями puts () і printf () полягає в тому, що функція printf () не виводить автоматично кожний рядок з нового рядка.

Стандартна бібліотека мови програмування Сі містить клас функцій для роботи з рядками, і всі вони починаються з літер str. Для того, щоб використовувати одну або декілька функції необхідно підключити файл string.h.

#include<string.h>

3. Визначення довжини рядка. Для визначення довжини рядка використовується функція strlen (). Її синтаксис:

size_t strlen(const char *s);

Функція strlen () повертає довжину рядка s, при цьому завершуючий нульовий символ не враховується.

Приклад:

char *s= "Some string";

int len;

Наступний оператор встановить змінну len рівною довжині рядка, що адресується покажчиком s:

len = strlen(s); /* len == 11 */

4. Копіювання рядків. Оператор присвоювання для рядків не визначений. Тому, якщо s1 і s2 - символьні масиви, то неможливо скопіювати один рядок в інший наступним чином.

char s1[100];

char s2[100];

s1 = s2; /* помилка */

Останній оператор (s1=s2;) не скомпілюється.

Щоб скопіювати один рядок в інший необхідно викликати функцію копіювання рядків strcpy (). Для двох покажчиків s1 і s2 типу char * оператор

strcpy(s1,s2);

копіює символи, що адресуються покажчиком s2 в пам'ять, що адресується покажчиком s1, включаючи завершуючі нулі.

Для копіювання рядків можна використовувати і функцію strncpy (), яка дозволяє обмежувати кількість символів, що копіюються.

strncpy(destantion, source, 10);

Наведений оператор скопіює 10 символів із рядка source в рядок destantion. Якщо символів в рядку source менше, ніж вказане число символів, що копіюються, то байти, що не використовуються встановлюються рівними нулю.

Примітка. Функції роботи з рядками, в імені яких міститься додаткова літера n мають додатковий числовий параметр, що певним чином обмежує кількість символів, з якими працюватиме функція.

5. Конкатенація рядків.

Конкатенація двох рядків означає їх об'єднання, при цьому створюється новий, більш довгий рядок. Наприклад, при оголошенні рядка

char first[]= "Один ";

оператор

strcat(first, "два три чотири!");

перетворить рядок first в рядок "Один два три чотири".

При викликанні функції strcat(s1,s2) потрібно впевнитися, що перший аргумент типу char * ініціалізований і має достатньо місця щоб зберегти результат. Якщо s1 адресує рядок, який вже записаний, а s2 адресує нульовий рядок, то оператор

strcat(s1,s2);

перезапише рядок s1, викликавши при цьому серйозну помилку.

Функція strcat () повертає адресу рядка результату (що співпадає з її першим параметром), що дає можливість використати "каскад" декількох викликів функцій:

strcat(strcat(s1,s2),s3);

Цей оператор додає рядок, що адресує s2, і рядок, що адресує s3, до кінця рядка, що адресує s1, що еквівалентно двом операторам:

strcat(s1,s2);

strcat(s1,s3);

Повний список прототипів функцій роботи з рядками можна знайти в додатках на стор.

6. Порівняння рядків.

Функція strcmp () призначена для порівняння двох рядків. Синтаксис функції:

int strcmp(const char *s1, const char*s2);

Функція strcmp () порівнює рядки s1 і s2 і повертає значення 0, якщо рядки рівні, тобто містять одне й те ж число однакових символів. При порівнянні рядків ми розуміємо їх порівняння в лексикографічному порядку, приблизно так, як наприклад, в словнику. У функції насправді здійснюється посимвольне порівняння рядків.

Кожний символ рядка s1 порівнюється з відповідним символом рядка s2. Якщо s1 лексикографічно більше s2, то функція strcmp () повертає додатне значення, якщо менше, то - від'ємне.

1.12 Основні методи сортування масивів

Починаючи з даного розділу, розглянемо декілька методів впорядкування елементів масиву, які широко використовуються у практичному програмуванні.