7 Одновимірні масиви



Скачати 113.17 Kb.
Дата конвертації23.06.2019
Розмір113.17 Kb.

7.1. Одновимірні масиви

Характерною ознакою простих типів даних є те, що вони атомарні, тобто не містять як складові елементи дані інших типів. Типи даних, що не задовольняють зазначеній властивості, називаються структурованими. У мові Pascal означено такі структуровані типи: масиви, рядки, множини, записи та файли. Структуро-ваний тип характеризується множиною елементів, з яких складаються дані цього типу. Елементи структурованого типу називаються компонентами (компоненти масивів найчастіше називають елементами масивів). Отже, змінна або константа структурованого типу завжди містить декілька компонентів. У свою чергу, кожний компонент може належати до структурованого типу, що дозволяє говорити про вкладеність типів. З простих елементів даних, або компонентів, більш складні структури утворюються двома способами: об'єднанням однорідних елементів даних з метою створення масивів та об'єднанням різнорідних елементів даних з метою створення записів.

Потреба у масивах виникає тоді, коли в оперативній пам'яті зберігається велика, але визначена кількість однотипних даних. Наприклад, можна задати масив щоденних значень температури повітря протягом місяця з метою визначення середньої температури або масив логічних значень, що зображуватиме наявність квитків на кіносеанс на всі місця у кінозалі. Розрізняють одновимірні та багатовимірні масиви. Зокрема, масив температур є одновимірним, а масив квитків - двовимірним. Одновимірні масиви розглядаються в розділі 7.1, а багатовимірні -в розділі 7.2. У розділі 7.3 розглянуто рядки, які є різновидом одновимірних масивів.



7.1.1. Поняття масиву та його властивості

Дамо означення одновимірного масиву, розрізняючи тип масиву та дані цього типу. Терміном «масив» надалі позначатимемо саме дані деякого типу масиву.

Одновимірний масив — це послідовність однотипних даних.
Уважно проаналізувавши це означення, можна зробити висновок, що масив фактично поєднує в собі дві структури: множину елементів і заданий на цій множині порядок. Усі елементи масиву мають один і той самий тип, що називається базовим. З іншого боку, порядок теж визначається набором значень одного й того самого типу, що називається індексним, а самі ці значення називаються індексами. Кожному елементу масиву відповідає певний індекс. Індексний тип має бути простим порядковим типом даних. Кількість елементів в одновимір-ному масиві називається його розмірністю, або довжиною.

Тип масиву — це структурований тип даних, множина допустимих значень котрого складається з усіх масивів, для яких зафіксовано:



  • розмірність;

  • базовий тип;

  • індексний тип;

  • множину значень індексу.

Щойно наведене визначення типу масиву можна застосувати до типів як одновимірних, так і багатовимірних масивів. Зауважимо також, що усі елементи одновимірного масиву записуються до розташованих поряд ділянок оперативної пам'яті. Тому і весь масив може розглядатися як одна нерозривна область пам'яті.

З точки зору математики одновимірний масив — це вектор. Наприклад, масив або вектор А, що має п'ять елементів, які записують у математиці у вигляді індексованих змінних а1 и а2, а3, а4, а5, можна зобразити значеннями цих змінних у сусідніх ділянках оперативної пам'яті.



а1

а2

а3

а4

а5

Ідентифікатор типу масиву можна оголосити в розділі type з використанням такого синтаксису:

<ім'я типу масиву> = array[<нижній індекс>..<верхній індекс>] of <тип елементів>;

У цьому оголошенні array, of — зарезервовані слова, що перекладаються як «масив», «з»; <ім'я типу масиву> — деякий ідентифікатор; <тип елементів> — будь-який тип даних, окрім файлового типу; <нижній індекс> і <верхній індекс> — константи, що визначають межі діапазону допустимих значень індексу. Розмірність масиву дорівнює величині оrd(<верхній індeкс>)-оrd(<нижній індекс>)+1.

У розділі var оголошується змінна, що матиме раніше оголошений тип масиву:

<ім'я масиву> : <ім'я типу масиву>;

Синтаксис мови Pascal дає можливість поєднати у розділі var оголошення змінної-масиву із визначенням її типу. При цьому ідентифікатор типу масиву не оголошується:



<ім'я масиву> : array[<нижній індекс>..<верхній індекс>] of <тип елементів>;

Нагадаємо, що обсяг пам'яті, яка виділена для зберігання всіх оголошених у розділах var змінних, не повинен перевищувати 64 Кбайт. Тому є обмеження на максимальну кількість елементів у масиві. Так, максимальна кількість елементів типу integer не може перевищувати 32 767, а елементів типу real — 10 922.

Оголосити змінну типу масиву можна і з використанням такого синтаксису:

<ім'я масиву> : array[<тип індексів>] of <тип елементів>;

Тут <тип індексів> — цілі типи shortint або byte, для яких кількість допустимих значень становить 256, або оголошений в розділі type перелічуваний тип. Як типи індексів не дозволяється вказувати типи integer, word і longint, оскільки розмір оголошеного в такий спосіб масиву становив би не менш ніж 64 Кбайт.





Приклад 7.1

Наведемо декілька прикладів оголошень одновимірних масивів.



Program ex7_1;
const
  start=10;
  finish=30;
type
  day=(Monday, Tuesday, Wednwsday, Thursday, Friday, Saturday, Sunday);
  vector=array[1..10] of integer;
  STR=array[byte] of char;
var
  a:vector;
  str:STR;
  digit:array[5..20] of integer;
  float:array[start..finish] of real;
  temperature:array[day] of real;
begin
  writeln('ex7_1');
end.

Підсумовуючи матеріал розділу 7.1.1, назвемо основні властивості масивів, притаманні як одновимірним, так і багатовимірним масивам:



  • однорідність — усі елементи належать одному типу;

  • сталість — вимірність масиву задається під час його оголошення і не змінюється протягом роботи з ним;

  • рівнодоступність — спосіб доступу до всіх елементів є однаковим;

  • послідовність розташування — усі елементи масиву розташовані в послідовних комірках оперативної пам'яті;

  • індексованість — елементи однозначно ідентифікуються своїми індексами;

  • упорядкованість індексу — індексний тип має бути простим порядковим типом даних.

7.1.2. Базові операції обробки одновимірних масивів

Будь-яка обробка масивів здійснюється шляхом виконання операцій над їх елементами. Двома найпростішими операціями над елементами одновимірного масиву є вибір певного елемента та зміна його значення. Для доступу до окремого елемента масиву застосовується операція індексування [], за допомогою якої утворюються вирази <і м' я масиву>[<і ндексний вираз>]. Елемент масиву є окремою змінною, що ідентифікується вище зазначеним виразом. Приклад ідентифікації елементів масиву а з індексами 1, 2, ..., 10 та масиву digit з індексами 5, 6, ..., 20 наведено нижче:

a[1], a[2], ..., a[10], digit[5], digit[6], ..., digit[20] .

Значення елементів масиву змінюються так само, як і значення інших змінних. Наприклад, для першого елемента масиву а це можна зробити операцією присвоєння а[1]:=5 або операцією введення даних readln(a[1]).

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



  • введення та виведення масиву;

  • ініціалізація масиву;

  • копіювання масиву;

  • пошук максимального або мінімального елемента;

  • обчислення узагальнювальних характеристик (сум елементів, їх добутків);

  • пошук заданого елемента;

  • перестановка елементів або обмін значеннями між елементами масиву;

  • вставка та видалення елемента.

Базові операції обробки масивів зручно реалізовувати у вигляді процедур, що згодом можуть бути використані як «архітектурні блоки» при розв'язанні більш складних задач. Серед таких задач найважливішою є задача упорядкування масивів. Декілька алгоритмів розв'язання цієї задачі буде розглянуто в розділі 7.1.3, а решту розділу 7.1.2 присвятимо розгляду базових операцій обробки одновимірних масивів.

Введення та виведення масиву

Мова Pascal не має засобів введення та виведення масиву як цілісного об'єкта, ця операція виконується поелементно за допомогою оператора циклу. Під час введення елементів масиву необхідно врахувати те, що їх кількість, тип та тип індексів задаються в оголошенні масиву до початку виконання програми і не можуть бути змінені. Якщо межі індексів масиву точно не відомі, їх добирають так, щоб введена кількість елементів масиву під час виконання програми не перевищувала верхньої межі індексу. Наприклад, після оголошення масиву а:аrrау[1. .100] of real кількість елементів, що до нього вводяться, не повинна перевищувати 100.





Приклад 7.2

Розглянемо реалізацію операцій введення та виведення одновимірного масиву. Для зберігання значень елементів масиву на етапі компіляції виділяється оперативна пам'ять, обсяг якої дорівнює означеній кількості елементів, помноженій на обсяг пам'яті, що її потребує збереження одного елемента. Під час виконання програми користувач вводить реальну кількість елементів, яка не повинна перевищувати оголошеної кількості. Наведений нижче код ілюструє принцип використання операції введення та виведення масиву. Зазначимо, що елементи масиву слід вводити через пробіл, оскільки при цьому застосовується оператор read.



Program ex7_2;
var
  mas:array[1..10] of integer;
  n:integer;
  i:integer;
begin
  writeln('Enter number of elements <=10');
  read(n);
  writeln('Enter elements values ');
  for i:=1 to n do
    read(mas[i]);
    writeln('Entered array');
  for i:=1 to n do
    write(mas[i],' ');
  writeln;
end.



Ініціалізація масиву

Введення значень елементів із клавіатури фактично є одним із способів ініціалізації масиву. Іншій спосіб ініціалізації масиву полягає у присвоєнні кожному його елементу деякого значення. Найбільш ефективно ця операція виконується за допомогою оператора for. Наприклад, у наведеному нижче коді десяти елементам масиву аrr присвоюються квадрати цілих чисел від 1 до 10.



for i:=1 to n do
  arr[i]:=sqr(i);

Одновимірні масиви-константпи записуються за наведеним нижче зразком як перелік значень їх елементів:



const a:array[1..5] of integer = (1,3,2,-5,6);

Така ініціалізація еквівалентна серії присвоювань


а[1]:=1; а[2]:=3; а[3]:=2; а[4]:= - 5; а[5]:= - 6:

Для однотипних масивів А та В як для цілісних об'єктів визначена операція присвоєння А := В . Однотипність масивів означає, що вони мають однакові типи індексів та однакові типи елементів. У результаті виконання операції присвоєння А := В значення елементів масиву В присвоюються відповідним елементам масиву А, тобто здійснюється копіювання масиву В до масиву А.



Пошук максимального та мінімального значень

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





Приклад 7.3

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

Оцінки суддів вважатимемо елементами масиву дійсних чисел. Кількість суддів, а значить, і кількість оцінок вводитимемо до змінної n. Якщо знайдено максимальний та мінімальний бал (змінні max і min) та накопичено суму балів у змінній sum, то за формулою res = (sum - min - max)/(n - 2) можна обчислити шукане значення. Цю задачу розв'язує програма ех7_3. Результати її роботи зображено на рис. 7.1.

Program ex7_3;
var
  mark:array[1..10] of real;
  i,n:integer;
  min,max,sum,result:real;
begin
  writeln('grade defining');
  writeln('enter numbers of arbiters (<=10)');
  read(n);
  writeln('enter ',n,' grades');
  for i:=1 to n do
    read(mark[i]);
    min:=mark[1];
    max:=mark[1];
    sum:=mark[1];
  for i:=2 to n do
    begin
      if min>mark[i] then min:=mark[i];
      if maxthen max:=mark[i];
      sum:=sum+mark[i];
    end;
  writeln('margin grades');
  writeln('max=',max:3:2,' min=',min:3:2);
  result:=(sum-min-max)/(n-2);
  writeln('rezult grade=',result:3:2);
end.



Рис. 7.1. Результати роботи програми ех7_3. Обчислення середньої оцінки виступу спортсмена

Демонстрація прикладу



Під час пошуку найбільшого або найменшого елемента масиву може виникнути потреба у визначенні його індексу. Значення індексу, як правило, використовується при подальшій перестановці елементів масиву, їх видаленні тощо. Для розв'язання цієї задачі застосований у прикладі 7.3 алгоритм потрібно модифікувати. А саме, окрім змінної max (min) слід використати змінну, в якій зберігатимуться значення індексів. Припустимо, це буде змінна nom. Цій змінній спочатку присвоюється індекс першого елемента масиву, а в тілі циклу вона змінює значення тоді, коли і змінна max (min). Отже, змінній nom присвоюється значення індексу того елемента, який виявився більшим за поточне значення max (меншим за поточне значення min).





Приклад 7.4

У магазині утворилася черга з декількох покупців. Відомий час обслуговування продавцем кожного покупця. Визначити час перебування кожного покупця у черзі, а також номер покупця, обслуговування якого потребує найменше часу.

Легко побачити, що час перебування кожного покупця у черзі дорівнює сумарному часу обслуговування його та всіх попередніх покупців. Якщо позначити час обслуговування і-го покупця змінною ti, а час його перебування в черзі — servi то це значення визначається за формулою servi = t1 + t2 + ... + ti. Можна застосувати рекурентну формулу, згідно з якою час перебування покупця в черзі визначається як сума часу його обслуговування та часу перебування в черзі попереднього покупця: servi = servi-1 + ti. Якщо час обслуговування n покупців подати у вигляді n-елементного масиву, то номер покупця з мінімальним часом обслуговування — це індекс мінімального елемента в масиві. Програмне розв'язання цієї задачі наведено нижче.

Program EX7_4;
var
  n,i:integer;
  t:array[1..10]of real;
  serv:array[1..10]of real;
  nom:integer;
  min:real;
begin
  randomize;
  Writeln('defining the number of buyer with a minimum service time');
  writeln('enter number of the buyers (<=10)');
  readln(n);
  for i:=1 to n do
    t[i]:=random*10;
  writeln('service time of the buyers');
  for i:=1 to n do
    write( t[i]:5:2,' ');
  writeln;
  serv[1]:=t[1];
  for i:=2 to n do
    serv[i]:=serv[i-1]+t[i];
  writeln('service time');
  for i:=1 to n do
    write(serv[i]:5:2,' ');
  writeln;
  nom:=1;
  min:=t[1];
  for i:=2 to n do
    if t[i]then
      begin
        min:=t[i];
        nom:=i;
      end;
  write('number of buyer having min service time =');
  writeln(nom);
end.



Рис. 7.2. Результати роботи програми ех7_4. Визначення номера покупця з мінімальним часом обслуговування

Демонстрація прикладу



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



Пошук у неупорядкованому та упорядкованому масивах

Пошук є однією з найбільш поширених задач програмування. Пошук в масиві за певним ключем полягає у визначенні номерів елементів масиву або їх значень, для котрих деяка умова, «ключ», виконується. Розрізняють задачі пошуку в упорядкованому та неупорядкованому масивах. В неупорядкованому масиві пошук можна здійснити лише за допомогою перегляду всього масиву. Такий пошук називається лінійним. Якщо значення елементів в масиві повторюються, то шляхом лінійного пошуку можна знайти лише перший з таких елементів, перервавши подальший пошук, або знайти усі потрібні значення, переглянувши весь масив. Приклади програм пошуку в неупорядкованому масиві першого з елементів і всіх елементів, які відповідають ключу пошуку, наведені нижче.





Приклад 7.5

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

Лінійний пошук здійснюється шляхом перебирання всіх елементів масиву та порівняння кожного з них із заданим значенням. Якщо елемент знайдено, цикл пошуку переривається і виводиться знайдений індекс. А якщо цикл пошуку дійшов останнього елемента, і цей елемент не дорівнює заданому значенню, виводиться повідомлення про відсутність шуканого елемента. Описаний алгоритм пошуку елемента в неупорядкованому масиві реалізовано в програмі ех7_5, код якої наведено нижче. На рис. 7.3 зображено результати роботи програми ех7_5.

Program EX7_5;
var n,i:integer;
  a:array[1..10]of integer;
  value:integer;
begin
  randomize;
  writeln('defining the number of the given component');
  writeln('enter number of the components (<=10)');
  readln(n);
  for i:=1 to n do
    a[i]:=random(10);
  writeln('generated array');
  for i:=1 to n do
    write( a[i],' ');
  writeln;
  writeln('enter value for search');
  readln(value);
  for i:=1 to n do
    if a[i]=value then
      begin
        writeln('nom=',i);
        break;
      end;
    if a[i]<>value then writeln('value not found');
end.

Рис. 7.3. Результати роботи програми ех7_5. Пошук у неупорядкованому масиві першого з елементів, що відповідає ключу пошуку



Демонстрація прикладу

За матеріалами сайту http://vvpc.com.ua/tests_informatiks/inform/osnovy_program/7/1.htm

Поділіться з Вашими друзьями:


База даних захищена авторським правом ©wishenko.org 2017
звернутися до адміністрації

    Головна сторінка