Одновимірні та багатовимірні масиви

Реферат

На тему:

Одновимірні та багатовимірні масиви

Підготував

студент групи ПМ-11

факультету ПМіКІС

Позняковський Артем

Рівне 2008

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

Масив - це змінна, утворена послідовністю змінних, причому:

усі вони (компоненти, або елементи масиву) мають той самий тип;

кожний компонент має свій номер у послідовності (індекс) і відрізняється ним від інших елементів (ідентифікується);

множина індексів (індексова множина) скінченна й зафіксована в означенні масиву та в процесі виконання програми не змінюється;

можливість обробки компонента, або його доступність, не залежить від його місця в послідовності (елементи рівнодоступні).

Кількість елементів індексової множини називається довжиною масиву.

Подивимося на масив із точки зору математики. Нехай компоненти масиву мають тип T, а індекси - тип I. Значенням змінної-масиву є послідовність значень типу T, занумерованих значеннями типу I, тобто функція типу I® T. Множина всіх таких функцій утворює носій для типу, який у мові Паскаль означається виразом вигляду array [I ] of T.

Наприклад, масив, у якому треба зберігати коефіцієнти полінома, міг би мати тип array[0 101]of real. У такому масиві 102 компоненти дійсного типу із номерами від 0 до 101. Або масив, у якому треба зберігати кількості символів, прочитаних десь, міг би мати тип array [ char ] of integer. У ньому 256 цілих змінних, а їх номерами є символи.

Типом компонентів може бути довільний тип, окрім файлів (розділ 13). Типом індексів I - будь-який перелічуваний тип. Щоправда, система Турбо Паскаль не дозволяє вказувати типи integer та word, а тим паче тип longint, як типи індексів. Там занадто багато елементів. Але це не страшно, оскільки система дозволяє створювати масиви навіть із ще більшою кількістю елементів (див. підрозділ 16.5).

Якщо тип індексів означається виразом у дужках [ ] як діапазон, то, зрозуміло, там пишуться дві сталі, і ніяких змінних там не може бути.

В означенні масивів як змінних немає ніяких особливостей. Наприклад, ми можемо написати як

type ART=array[0 101]of real; var A : ART;

так і

var A : array[0 101]of real;

В обох випадках змінна A складається зі 102 дійсних змінних. Вони ідентифікуються виразами A[0], A[1], … , A[101]. Або виразами вигляду A[індексовий-вираз], де індексовий-вираз має значення від 0 до 101.

З точки зору математики, для масивів означена операція індексування []. За масивом типу I® T та номером компонента в ньому вона породжує змінну типу T. Нехай ім'я означено як масив типу array[I] of T, E - вираз типу I. Тоді вираз ім'я[E] задає елемент цього масиву, тобто змінну типу T, номер якої в масиві є значенням виразу E.

Вирази з операцією [] допустимі в операторах скрізь, де вживається змінна відповідного типу, за винятком того, що елемент масиву не може бути параметром циклу. Наприклад, якщо діє означення типу ART та змінної A, то можна писати щось на зразок

A[1] :=1; A[2] := A[1]+2;

for k := 3 to 101 do readln(A[k]);

writeln(A[1]+A[2]+A[3]+A[4]).

Індексування - це єдина операція над масивами як цілісними об'єктами. Тому обробка масивів описується через обробку їх компонентів. Щоправда, в мові Турбо Паскаль можна присвоювати однотипні масиви. Наприклад, за дії означень

var a, b : array[char] of integer; ch : char;

можна замість циклу

for ch:= chr(0) to chr(255) do b[ch]:=a[ch];

написати лаконічно

b := a;

Зупинимося на підстановці аргументу-масиву на місце параметра підпрограми. Якщо параметр-масив є параметром-значенням, то на початку виконання виклику підпрограми в локальній пам'яті цього виклику створюється копія аргументу. Якщо у масиві багато елементів, то можлива ситуація, коли автоматичної пам'яті для такого аргументу не вистачить. Проте за виконання підпрограми масив або залишається без змін, або змінюється, причому саме змінений масив і потрібний для подальшої обробки за програмою. У першому випадку його можна підставляти за посиланням, а не за значенням; в другому - треба. Випадки, коли параметри-масиви необхідно означати як параметри-значення, трапляються досить рідко. Звичайно, використання параметрів-змінних типу масив вимагає підвищеної акуратності.

2. Рядки

Рядок у загальному значенні цього слова - скінченна послідовність символів. У програмуванні для подання рядків використовують масиви символів. У діалектах мови Паскаль означено спеціальні типи, в основі яких лежать масиви. Типи рядків мають свої специфічні операції, не означені над масивами символів, тобто рядки та символьні масиви є цілком різними типами.

Змінна-рядок є масивом символів разом із додатковим компонентом. В означенні типу задається довжина n послідовності символьних компонентів, індексованих цілими 1,…,n. Додатковий компонент указує довжину послідовності символів, поданої в масиві. Ця довжина значення-рядка може змінюватися в процесі виконання програми від 0 до довжини масиву n.

У мові Турбо Паскаль тип рядків задається виразом вигляду

string[n],

де n - ціла стала з діапазону 1 255 (можливо, іменована). Наприклад, string[80]. Змінна такого типу є масивом символів із індексами від 0 до n. Значення-рядок подається змінними з індексами від 1 до n, змінна з індексом 0 подає довжину рядка. Точніше, якщо її значення c, то m=ord(c) розглядається як довжина значення-рядка. У процесі виконання програми вона може мінятися від 0 до n.

Елементи масиву з індексами від m+1 до n недоступні; їх значення можна розглядати як "сміття". Спроба присвоїти щось цим елементам або взяти їх значення призведе до аварійного завершення програми.

Оскільки невід'ємна довжина значення-рядка подається в одному байті, вона не може перевищувати 255. Звідси "маємо, те що маємо", тобто обмеження 255 на довжини рядків. Ім'я типу string еквівалентне виразові string[255].

Найпростішими виразами типу рядок є ім'я змінної-рядка, рядкова стала (літерал), або вираз типу char. Над рядками означена бінарна операція катенації (або дописування); її знаком є '+'. Результат одержується дописуванням правого операнда до лівого: значенням виразу '123'+'45' є '12345'. Ціла довжина рядка повертається з виклику функції length із аргументом-рядком: length('123') = 3.

Рядки - єдиний нескалярний тип, змінні та вирази якого можуть бути аргументами стандартних процедур читання та запису. Особливості виконання цих процедур розглядаються в розділі 14. Рядки також можуть повертатися як значення функцій.

Вираз типу "рядок" можна присвоїти змінній-рядку. Його символи присвоюються елементам змінної, починаючи з першого. Якщо довжина значення більша максимально можливої довжини n змінної, то присвоюються лише n перших символів. При цьому довжина значення (або n) неявно присвоюється додатковому компоненту змінної-рядка (як символ нульовому елементу масиву). Наприклад, нехай змінна s означена як string[3]. Після присвоювання

s:='12345'

чотири її компоненти з індексами 0, 1, 2, 3 матимуть значення chr(3), '1', '2', '3', а після

s:='12'

- chr(2), '1', '2', а останній компонент буде недоступним, і його значення буде "сміттям". За останнього значення змінної s виконання оператора

s:=s+'9'

надасть їй значення '129', а оператора

s:='9'+s

- значення '912'. В обох випадках s[0]=chr(3). Після присвоювання s:='' змінна s подає порожній рядок: s[0]=chr(0), а решта елементів недоступні.

Змінити довжину значення можна явно, змінивши нульовий символ. Якщо після s:='' виконати s[0]:=2, то значення компонентів із індексами 1 і 2 зі "сміття" перетворяться на значення-рядок. Присвоювання іншим елементам рядка не змінює довжини його значення.

У типах рядків означено операції порівняння =, <>, <, … . За означенням, рядки рівні, якщо мають ту саму довжину, і в її межах відповідні символи однакові. У противному разі вони не рівні. Упорядкування рядків залежить від системи програмування.

У мові Турбо Паскаль, якщо length(s1)<length(s2), то рядок s1 менше рядка s2, тобто s1<s2 - істина. За рівних довжин рядки порівнюються в лексикографічному порядку, тобто s1<s2 тоді, коли існує таке i, що 1Ј іЈ length(s1), за якого s1[i]<s2[i], а всі відповідні елементи з меншими номерами рівні між собою. Як бачимо, упорядкування рядків у Турбо Паскаль відрізняється від лексикографічного.

У системі програмування Турбо Паскаль означено також багато корисних підпрограм обробки рядків. Розглянемо лише чотири з них.

Функція з заголовком

function copy ( s : string; ind, cnt : byte ) : string

задає повернення підрядка рядка s, що починається з s[ind] і має довжину cnt. Наприклад, copy('abcd', 2, 2)='bc'.

Функція з заголовком

function pos ( subs, s : string ) : byte

задає повернення номера того елемента в рядку s, починаючи з якого subs входить у s як підрядок (якщо не входить, то повертається 0). Наприклад, pos('bc', 'abcd')=2, pos('aa', 'abcd')=0.

Процедура з заголовком

procedure val(s : string, var v; var ErrCode : integer)

задає перетворення зображення числа в рядку s у числовий тип і присвоювання його змінній v. Якщо перетворення дійсно можливе, то значенням ErrCode буде 0. У противному разі її значенням буде позиція з символом у рядку, починаючи з якого перетворення неможливе. Тип аргументу, відповідного параметрові v, повинен мати тип, відповідний змісту рядка s. Так само зміст рядка повинен задавати число, представне в типі цього аргументу. Наприклад, за s='1.3' або s='1E2' другий аргумент повинен бути дійсного типу, а не цілого. Аналогічно за його типу integer у рядка не повинно бути значень, що подають числа, більші 32767 або менші -32768.

Процедура з заголовком

procedure delete(var s : string; start, len : integer)

задає знищення len символів, починаючи з позиції start у рядку s. Наприклад, за s='abcdef' після виклику delete(s, 3, 3) рядок s матиме значення 'abf'. За start=0 або len=0 або start>length(s) рядок не змінюється. За start+len>length(s) з s вилучається підрядок до кінця рядка.

3. Нестандартне подання чисел

В умовах і розв'язаннях багатьох задач виникають числа, що не подаються в стандартних типах, наприклад, великі цілі числа або дійсні з великою кількістю дробових розрядів. Розглянемо окремі питання реалізації "нестандартної арифметики" цілих та дійсних чисел.

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

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

Нестандартним поданням цілого числа також є послідовність цифр. Питання лише у виборі системи числення та кількості розрядів, а також одиниці пам'яті для відтворення розряду числа. Розглянемо деякі можливі варіанти нестандартного зображення цілих чисел у масивах.

1) Значення цифри десяткового числа подається елементом масиву типу integer. Пам'ять використовується дуже неекономно (розряд займає 2 або 4 байти), але арифметичні операції реалізуються через порозрядні операції над значеннями цифр, уже означені в Паскалі для типу integer.

2) Цифра числа (а не її значення-число) безпосередньо є значенням типу char і подається одним байтом. Покомпонентні операції над значеннями цифр треба відтворити у вигляді операцій над символами. Для зображення чисел зручно скористатися рядковим типом.

3) Значення цифри числа в P-ковій системі подається одним байтом як число від 0 до P-1, де PЈ 256. За P=256 кожний біт відображає значення двійкової цифри 0 чи 1; таке подання найекономніше витрачає пам'ять, але вимагає певних зусиль для реалізації операцій.

4) Значення P-кової цифри, де PЈ 16, подається чотирма бітами (півбайтом) так, що дві сусідні цифри займають байт.

Дійсні числа (точніше, раціональні з їх певної підмножини) можуть подаватися у вигляді з фіксованою чи з плаваючою крапкою. У першому випадку фіксуються розряди для зображення цифр цілої та дробової частини. У другому - розряди дробової частини та показника степеня (мантиси й порядку - див. підрозділ 11.2). Ще один розряд подає знак числа. Варіанти подання відрізняються основами систем числення та довжиною мантиси й порядку, а також одиницями пам'яті для розрядів.

4. Матриці та багатовимірні масиви Розглянемо прямокутну таблицю з mґ n однотипиних елементів як послідовність із m рядків, у кожному з яких n елементів. Послідовності певної довжини подаються в мовах програмування масивами. Отже, виникає поняття "масив, елементами якого є масиви", або двовимірний масив. Якщо елементи прямокутної таблиці самі є послідовностями або таблиці утворюють послідовність певної довжини, то виникає поняття тривимірного масиву тощо. Означення багатовимірних масивів та зображення їх елементів у мові Паскаль опишемо за допомогою простого прикладу. Позиція в грі "хрестики-нулики на полі 3ґ 3" подається квадратною таблицею з символів 'x', '0' або ' ' (пропуск). Пронумеруємо клітинки поля, як у шахах - літерами 'a', 'b', 'c' по горизонталі та числами 1, 2, 3 по вертикалі. Тоді рядки таблиці можна подати масивами типу type Row = array [ 'a' 'c' ] of char; Таблицю можна розглянути як послідовність трьох рядків і подати масивом типу type Table = array [ 1 3 ] of Row; Партія, тобто послідовність позицій, має довжину не більше 9, і може подаватися масивом таблиць: type Game = array [ 1 9 ] of Table; Масиви типу Table мають два виміри: номер рядка та номер символу в ньому; масиви типу Game - три: номери таблиці, рядка та символу. Вимір 1 9 у типі Game називається зовнішнім, вимір 'a' 'c', що нумерує символи в рядках, - внутрішнім. Тип Game можна задати еквівалентним виразом, не означаючи імен типів Row і Table, а саме: type Game = array [ 1 9 ] of array [ 1 3 ] of array [ 'a' 'c' ] of char; Нехай A - змінна типу Game. Вираз вигляду A[ i ], де 1Ј i Ј 9, задає змінну типу Table, або типу array [ 1 3 ] of array [ 'a' 'c' ] of char; вираз вигляду A[i][j], де 1Ј jЈ 3, - змінну типу Row, або типу array[ 'a' 'c' ] of char; вираз вигляду A[i][j][k], де 'a' Ј k Ј 'c', - змінну типу char. Мова Паскаль допускає іншу форму задання типів та елементів багатовимірних масивів: виміри та індекси записуються через кому в спільних дужках. Так, означення type Game1 = array [ 1 9, 1 3, 'a' 'c' ] of char еквівалентне означенню типу Game, а вираз A[i, j, k] - виразові A[i][j][k]. Елементи багатовимірних масивів розташовуються в пам'яті послідовно, найшвидше в них змінюється внутрішній індекс, найповільніше - зовнішній. Зокрема, двовимірні масиви (матриці) розташовуються за рядками. Так, послідовні числа масиву типу array [ 1 2, 'a' 'b' ] of real мають набори індексів [1, 'a'], [1, 'b'], [2, 'a'], [2, 'b'], а послідовні символи в масиві типу Game - [1, 1, 'a'], [1, 1, 'b'], [1, 1, 'c'], [1, 2, 'a'], … , [1, 3, 'c'], [2, 1, 'a'], … , [9, 3, 'c']. Задачі 30. Написати процедуру побудови за дійсними числами a1, … , an квадратної матриці а) 1 1 … 1 б) a1 a2 … an-1 an a1 a2 … an a2 a3 … an a1 … … a1n-1 a2n-1 … ann-1 an a1 … an-2 an-1 31.*У матриці розмірами M ґ N обміняти місцями а) два рядки, б) два стовпці, задані номерами. 32.*Транспонувати квадратну матрицю без використання додаткової матриці. 33.*Квадратну матрицю повернути за годинниковою стрілкою на а) 90° ; б) 180° . Додаткову матрицю не використовувати. 34. Елемент матриці називається сідловим, якщо його значення є мінімальним у рядку й максимальним у стовпці, на перетині яких він знаходиться (або навпаки, максимальним у рядку й мінімальним у стовпці). Написати процедуру повернення номерів рядка та стовпця якого-небудь із сідлових елементів (якщо таких немає, то повертається пара номерів зовні індексної множини матриці). 35. За матрицею з дійсними елементами побудувати нову "згладжену" матрицю, значенням кожного елемента якої є середнє арифметичне значень відповідного елемента та його сусідів у початковій матриці. 36.*Написати процедуру обчислення добутку двох матриць. 37. Написати процедуру обчислення степеня квадратної матриці на основі "індійського алгоритму" (див. підр. 9.4). 38. За квадратною матрицею розміру N одержати послідовність чисел b1, b2, … , bN*N обходом матриці а) "змійкою": б) за спіраллю: 39. Елементи N-вимірного масиву розмірів M1 ґ … ґ MN розміщаються в пам'яті комп'ютера послідовно так, що найшвидше змінюється їх останній індекс, найповільніше - перший. Написати функцію обчислення лінійного індексу елемента (його номера в порядку розташування в пам'яті) за заданими розмірами M1, … , MN та індексами елемента в N-вимірному масиві. Написати процедуру обчислення індексів елемента в багатовимірному масиві за його лінійним індексом та розмірами M1, … , MN. Значенням N є: а) 2; б) 3; в) 4. 40. Зображення містить замкнений контур і подається матрицею з 50 рядків по 80 символів. Елементи контура зображаються символом chr(219), порожні клітини всередині та зовні контура - пропуском ' '. Якщо всередині контура є хоча б один елемент із значенням '1' (відмічений), то зображення "заливається", тобто всі елементи всередині контура відмічаються за правилом: елемент відмічається, якщо з чотирьох його сусідніх по вертикалі чи горизонталі елементів хоча б один відмічений. Написати процедуру заливання зображення.