Лінійні структури (списки даних, вектори даних)

Лінійні структури — це добре знайомі нам списки. Список — це проста структура даних, що відрізняється тим, що кожен елемент даних однозначно визначається своїм номером в масиві. Проставляючи номери на окремих сторінках розсипаної книги, ми створюємо структуру списку. Звичайний журнал відвідуваності занять, наприклад, має структуру списку, оскільки всі студенти групи зарегист­рированы в нім під своїми унікальними номерами. Ми називаємо номери уникаль­ными тому, що в одній групі не можуть бути зареєстровані два студенти з одним і тим же номером.

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

N п/п Прізвище, Ім'я, По батькові

1 Лелек Олександр Олексійович

2 Бобрів Борис Борисович

3 Воробйова Валентина Владиславівна

27 Сорокин Сергій Семенович

Роздільником може бути і який-небудь спеціальний символ. Нам добре відомі роздільники між словами — це пропуски. У російському і в багатьох європейських мовах загальноприйнятим роздільником пропозицій є крапка. У розглянутому наами класному журналі як роздільник можна використовувати будь-який символ, який не зустрічається в самих даних, наприклад символ «*». Тоді наш список ыглядел би так:

Лелек Олександр Олексійович * Бобрів Борис Борисович * Воробйова Валентина Владиславівна *... * Сорокин Сергій Семенович

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

ще простіше можна діяти, якщо всі елементи списку мають рівну довжину. В цьому випадку роздільники в списку взагалі не потрібні. Для розшуку елементу з номером п треба проглянути список із самого початку і відлічити а(п—1) символ, де а — довжина одного елементу. З наступного символу почнеться потрібний елемент, довжина теж рівна а, тому його кінець визначити неважко. Такі спрощені списки, що складаються з елементів рівної довжини, називають векторами даних. Працювати з ними особливо зручно.

Таким чином, лінійні структури даних (списки) — це впорядковані струк­туры, в яких адреса елементу однозначно визначається його номером.

Таблиці даних, матриці даних

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

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

Планета	Відстань до Сонця, а.е.	Відносна маса	Кількість супутників
Меркурій	0,39	0,056	0
Венера	0,67	0,88	0

ялині потрібно зберегти таблицю у вигляді довгого символьного рядка, використовують один символ - роздільник між елементами, що належать одному рядку, і інший роздільник для відділення рядків, наприклад так:

Меркурий*0,39*0,056*0#Венера*0,67*0,88*0#Земля*1,0*1,0*1#Марс*1,51*0,1*2#...

Для розшуку елементу, що має адресу осередку (т, п), треба проглянути набір даних Із самого початку і перерахувати зовнішні роздільники. Коли буде відлічений т-1 роздільник, треба перераховувати внутрішні роздільники. Після того, як буде знайдений n-1 роздільник, почнеться потрібний елемент. Він закінчиться, коли буде зустрінутий будь-який черговий роздільник.

Ще простіше можна діяти, якщо всі елементи таблиці мають рівну довжину. Такі таблиці називають матрицями. В даному випадку роздільники не потрібні, оскільки всі елементи мають рівну довжину і кількість їх відомо. Для розшуку елементу з адресою (т, п) в матриці, що має М рядків і N стовпців, треба про­смотреть її із самого початку і відлічити а[N (т-1) + ( п-1)] символ, де а — довжина одного елементу. З наступного символу почнеться потрібний елемент. Його довжина теж рівна а, тому його кінець визначити неважко.

Таким чином, табличні структури даних (матриці) — це впорядковані структури, в яких адреса елементу визначається номером рядка і номером стовпця, на перетині яких знаходиться осередок, що містить шуканий елемент.

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

Номер факультету: 3

Номер курсу (на факультеті): 2

Номер спеціальності (на курсі): 2

Номер групи в потоці однієї спеціальності: 1

Номер що вчиться в групі: 19

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