Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Масив



План:


Введення

Масив (в деяких мовах програмування також таблиця, ряд) - набір однотипних компонент (елементів), розташованих в пам'яті безпосередньо один за одним, доступ до яких здійснюється за індексу (індексами). На відміну від списку, масив є структурою з довільним доступом [1].

Розмірність масиву - кількість індексів, необхідне для однозначного доступу до елементу масиву [2] [3].

Форма або структура масиву - кількість розмірностей і розмір (довжина) масиву для кожної розмірності [4], може бути представлений одновимірним масивом [5].

У мові програмування APL масив є основним типом даних (при цьому нуль-мірний масив називається скаляром, одновимірний - вектором, двовимірний - матрицею) [5].

У ряді мов програмування, наприклад, Лісп, JavaScript, PHP, Ruby застосовуються також асоціативні масиви (або хеш-масиви), в яких елементи не обов'язково є однотипними, а доступ до них не обов'язково здійснюється за індексом.


1. Загальний опис

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

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

Приклад статичного масиву на мові Паскаль
 {Одновимірна масив цілих чисел. Нумерація елементів від 1 до 15}  a  :  array  [  1  ..  15  ]  of  Integer  ;  {Двовимірний масив символів. Нумерація по стовпцях по типу Byte (від 0 до 255) по рядках від 1 до 5}  multiArray  :  array  [  Byte  ,  1  ..  5  ]  of  Char  ;  {Одновимірна масив з рядків. Нумерація за типом word (від 0 до 65536)}  rangeArray  :  array  [  Word  ]  of  String  ; 
Приклад статичного масиву на С / С + +
 int  Array  [  10  ]  ;  / / Одновимірна масив цілих чисел розміру 10  / / Нумерація елементів від 0 до 9  double  Array  [  12  ]  [  15  ]  ;  / / Двовимірний масив дійсних чисел подвійної точності  / / Розміру 12 на 15.  / / Нумерація по стовпцях від 0 то 11, по рядках від 0 до 14 

Підтримка індексних масивів (свій синтаксис оголошення, функції для роботи з елементами і т. д.) є в більшості високорівневих мов програмування. Максимально допустима розмірність масиву, типи і діапазони значень індексів, обмеження на типи елементів визначаються мовою програмування і / або конкретним транслятором.

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

Оголошення типу "масив" в мові Паскаль
 type  TArrayType  =  array  [  0  ..  9  ]  of  Integer  ;  (* Оголошення типу "масив" *)  var  arr1  ,  arr2  ,  arr3  :  TArrayType  ;  (* Оголошення трьох змінних-масивів одного типу *) 

2. Специфічні типи масивів

2.1. Динамічні масиви

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

Приклад динамічного масиву на Delphi
 byteArray  :  Array  of  Byte  ;  / / Одновимірна масив  multiArray  :  Array  of  Array  of  string  ;  / / Багатомірний масив 
Приклад динамічного масиву на Сі
 float  *  array1  ;  / / Одновимірна масив  int  **  array2  ;  / / Двовимірний масив  array1  =  (  float  *  )  malloc  (  10  *  sizeof  (  float  )  )  ;  / / Виділення 10 блоків по sizeof (float) байт кожен  array2  =  (  int  **  )  malloc  (  16  *  sizeof  (  int  *  )  )  ;  / / Виділення 16 блоків по sizeof (int *) байт кожен. Сюди будуть записані покажчики на одномірні масиви-рядки  for  (  i  =  0  ;  i  <  16  ;  i  + +  )  array2  [  i  ]  =  (  int  *  )  malloc  (  8  *  sizeof  (  int  )  )  ;  / / Виділення 8 блоків по sizeof (int) байт кожен. Це одномірні масиви - рядки матриці.  / / Звернення до масиву  array1  [  i  ]  =  5.0  ;  / / Записи еквівалентні. Перша з використанням індексу,  *  (  array1  +  i  )  =  5.0  ;  / / Друга з операцією разименованія.  array2  [  i  ]  [  j  ]  =  6  ;  / / Записи еквівалентні. Перша з використанням індексу,  *  (  *  (  array2  +  i  )  +  j  )  =  6  ;  / / Друга з операцією разименованія. 

Приклад динамічного масиву на С + +

 float  *  array1  ;  / / Одновимірна масив  int  **  array2  ;  / / Багатомірний масив  array1  =  new  float  [  10  ]  ;  / / Виділення 10 блоків розміром типу float  array2  =  new  int  *  [  16  ]  ;  / / Виділення 16 блоків розміром типу покажчика на int  for  (  int  i  =  0  ;  i  <  16  ;  i  + +  )  {  array2  [  i  ]  =  new  int  [  8  ]  ;  } 

2.2. Гетерогенні масиви

Гетерогенним називається масив, в різні елементи якого можуть бути безпосередньо записані значення, які належать до різних типам даних. Масив, що зберігає покажчики на значення різних типів, не є гетерогенним, так як власне зберігаються в масиві дані відносяться до єдиного типу - типу "покажчик". Гетерогенні масиви зручні як універсальна структура для зберігання наборів даних довільних типів. Відсутність їх підтримки в мові програмування призводить до необхідності реалізації більш складних схем зберігання даних. З іншого боку, реалізація гетерогенності вимагає ускладнення механізму підтримки масивів у трансляторі мови. Гетерогенний масив як вбудований тип даних присутній в мовах PHP і [ ] .


3. Реалізація

Одним з способом реалізації статичних масивів з одним типом елементів є наступний (в Фортрані порядок індексів протилежний такому в Сі [4]):

  1. Під масив виділяється безперервний блок пам'яті об'ємом S * m 1 * m 2 * m 3... m n, де S - розмір одного елемента, а m 1... m n - розміри діапазонів індексів (тобто кількість значень, які може приймати відповідний індекс) .
  2. При зверненні до елементу масиву A [i 1, i 2, i 3,..., i n] адресу відповідного елемента обчислюється як B + S * ((... (i 1p * m 1 + i 2p) * m 2 + ... + i (n-1) p) * m n-1 + i np), де B - база (адреса початку блоку пам'яті масиву), i kp - значення k-го індексу, наведене до цілого з нульовим початковим зміщенням.

Таким чином, адреса елемента із заданим набором індексів обчислюється так, що час доступу до всіх елементів масиву однаково.

Перший елемент масиву, в залежності від мови програмування, може мати різний індекс. Розрізняють три основних різновиди масивів: з відліком від нуля (zero-based), з відліком від одиниці (one-based) і з відліком від специфічного значення заданого програмістом (n-based). Відлік індексу елемента масивів з нуля більш характерний для низькорівневих мов програмування, проте цей метод був використаний в мовах більш високого рівня мовою програмування Сі.

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


4. Переваги

  • легкість обчислення адреси елемента за його індексом (оскільки елементи масиву розташовуються один за іншим)
  • однаковий час доступу до всіх елементів
  • малий розмір елементів: вони складаються тільки з інформаційного поля

5. Недоліки

  • для статичного масиву - відсутність динаміки, неможливість видалення або додавання елемента без зсуву інших
  • для динамічного і / або гетерогенного масиву - більш низьке (у порівнянні зі звичайним статичним) швидкодія і додаткові накладні витрати на підтримку динамічних властивостей і / або гетерогенності.
  • при роботі з масивом в стилі C (з покажчиками) і при відсутності додаткових засобів контролю - загроза виходу за межі масиву і пошкодження даних

Література

  • Вірт Н. Алгоритми і структури даних = Algoritms and data structure. - М .: Світ, 1989. - 360 с. - ISBN 5-03-001045-9
  • Хювенен Е., Сеппянен Й. Світ Ліспу. Введення в мову ЛИСП і функціональне програмування. У 2-х т. = Lisp-maailma: Johdatus kieleen ja ohjelmointiin / Пер. з фінськ. - М .: Світ, 1990. - ISBN 5-03-001935-9
  • Магара Н. А. Мова програмування АПЛ. - М .: "Радіо і зв'язок", 1983. - 96 с.
  • Бартеньев О. В. Сучасний Фортран. - 3-е изд., Доп. і перероб .. - М .: ДІАЛОГ-МІФІ, 2000. - 449 с.

Примітки


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Комсомольський масив
Ортогональний масив
Асоціативний масив
Розріджений масив
Масив Костаса
Масив Вінсон
Центральний масив
Гірський масив
Індексний масив
© Усі права захищені
написати до нас