Основні теоретичні відомості. Рядок – це тип даних, елементи якого – довільна послідовність символів алфавіту

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

Найчастіше у мовах програмування використовують три типи представлення рядків у пам'яті:

– у вигляді масиву символів із заданою довжиною;

– у вигляді масиву символів із завершенням спеціальним байтом;

– у вигляді динамічної структури даних.

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

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

Стосовно третього методу варто зазначити, що він використовує значно більше оперативної пам'яті для зберігання символів, оскільки крім них треба ще зберігати покажчики на попередній та/або наступний символ. Але це дозволяє значно прискорити виконання багатьох операцій над рядками. Одним з прикладів такого представлення рядків є реалізація їх у вигляді списку, де кожний символ у рядку – це елемент списку, що зберігає покажчик на наступний за ним символ.

Нижче наведено перелік найбільш розповсюджених операцій над рядками:

– отримання елементу за його порядковим номером у рядку;

– отримання позиції заданого елементу;

– конкатенація рядків;

– вибірка підрядку за індексами початку та кінця;

– перевірка входження одного рядку в інший (пошук у рядку);

– перевірка на еквівалентність рядків (порівняння рядків);

– визначення довжини рядку;

– заміна підрядку у рядку.

Приклад. Для створення списку-рядка необхідно подати кожний його елемент у вигляді класу, наведеного нижче:

class Node

{

public:

char d;

Node *next;

Node (char dat = 0) { d = dat;next = 0;}

};

class List

{

public:

Node *pbeg, *pend;

List() { pbeg = 0;pend = 0;}

~List();

void add(char d);

int pos(char d);

int len();

char get(int num);

void concat(List lst2);

void print();

};

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

void List::add(char d) //Додавання елемента у рядок

{ Node *pv = new Node(d);

if(!pbeg) {pbeg = pend = pv;}

else { pend->next = pv;

pend = pv;}

}

// визначення позиції вказанного символу у рядку

int List::pos(char d)

{ int p=0;

Node *pv = pbeg;

while(pv) { if(pv->d == d) return p;

p++; pv = pv->next;}

return -1;

}

int List::len() // визначення довжини рядку

{ int p=0;

Node *pv = pbeg;

while(pv) { p++; pv = pv->next;

}

return p;

}

char List::get(int num) //отримання елементу за його порядковим номером у рядку

{ int i=0;

Node *pv = pbeg;

while(pv)

{ if (num==i) return pv->d;

i++; pv = pv->next;

}

void List::concat(List lst2) // об’єднання двох рядків

{for(int i=0;i!=lst2.len();i++)

add(lst2.get(i));}

void List::print() // Відображення тексту рядку на екрані

{ Node *pv = pbeg;

cout << endl << " list: ";

while(pv)

{ cout << pv->d << " ";

pv = pv->next;}

cout << endl;

}

List::~List() // Деструктор

{

if(pbeg)

{ Node *pv = pbeg;

while(pv) { pv = pv->next; delete pbeg; pbeg = pv;}

}

Нижче наведений приклад програми, що використовує клас List. Програма формує список-рядок 'BETA' та друкує його на екран; визначає позицію елемента 'A', довжину списка-рядку, отримує за номером 2 елемент списку; формує список-рядок 'list' та друкує його на екран; об’єднує перший список-рядок з другим; формує список-рядок '11' та друкує його на екран; об’єднує перший список-рядок з третім.

void main()

{ List l1;

l1.add('B');

l1.add('E');

l1.add('T');

l1.add('A');

l1.print();

cout<<" pos="<<l1.pos('A')<<endl;

cout<<" len="<<l1.len()<<endl;

cout<<" elem="<<l1.get(2)<<endl;

List l2;

l2.add('l');