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

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

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

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

Опис найпростішого елемента такого списку виглядає наступним чином:

struct Імя_Типу {інформаційне поле; адресне поле; };

де інформаційне поле – це поле будь-якого, раніше оголошеного або стандартного, типу;

адресне поле – це покажчик на об'єкт того ж типу, що й обумовлена структура, в нього записується адреса наступного елемента списку.

Наприклад:

struct Node {

int key;//інформаційне поле

Node*next;//адресне поле

};

Інформаційних полів може бути декілька, наприклад:

struct point {

char*name;// інформаційне поле

int age;// інформаційне поле

point*next;//адресне поле

};

Приклад створення списку:

void Make_Single_List(int n,Single_List** Head){

if (n > 0) {

(*Head) = new Single_List();

//виділяємо пам'ять під новий елемент

cout << "Введите значение ";

cin >> (*Head)->Data;

//вводим значення інформаційного поля

(*Head)->Next=NULL;//обнуление адресного поля

Make_Single_List(n-1,&((*Head)->Next));

}

}

Приклад друку (проглядання) списку:

void Print_Single_List(Single_List* Head) {

if (Head!= NULL) {

cout << Head->Data << "\t";

Print_Single_List(Head->Next);

//перехід до наступного элементу

}

else cout << "\n";

}

Приклад вставки елемента у список:

{

//вставляємо новий елемент на перше місце

NewItem->Next = Head;

Head = NewItem;

}

else {// вставляємо новий елемент на не перше місце

if (Current->Next!= NULL)

NewItem->Next = Current->Next;

Current->Next = NewItem;

}

Приклад видалення елементу із списку:

{//видалення першого елемента

Head = Head->Next;

delete(Current);

Current = Head;

}

else {//видалення не першого елемента

ptr = Head;

while (ptr->Next!= Current)

ptr = ptr->Next;

ptr->Next = Current->Next;

delete(Current);

Current=ptr;

}

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

bool Find_Item_Single_List(Single_List* Head, int DataItem){

Single_List *ptr; //допоміжний вказівник

ptr = Head;

while (ptr!= NULL){//пока не кінець списку

if (DataItem == ptr->Data) return true;

else ptr = ptr->Next;

}

return false;

}

Приклад видалення списку:

void Delete_Single_List(Single_List* Head){

if (Head!= NULL){

Delete_Single_List(Head->Next);

delete Head;

}

}

Двонаправлений (двусвязний) список – це структура даних, що складається з послідовності елементів, кожен з яких містить інформаційну частину і два покажчика на сусідні елементи. При цьому два сусідні елементи повинні містити взаємні посилання один на одного.

Опис двонаправленого списку

struct имя_типа {

інформаційне поле;

адресне поле 1;

адресне поле 2;

};

Наприклад:

struct list {

type elem;

list *next, *pred;

}

list *headlist;

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

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

- за допомогою функції malloc, calloc, realloc і free;

- за допомогою оператора new і delete.

Динамічний масив - це масив змінної довжини, пам'ять під який виділяється в процесі виконання програми. Виділення пам'яті здійснюється функціями calloc, malloc або оператором new.

int *mas=new int[10];

При роботі з динамічними матрицями у C++ можна використовувати звичайні покажчики. Після опису покажчика, необхідно буде виділити пам'ять для зберігання M елементів N - число рядків, M - число стовпців). Так виділяється пам'ять для зберігання цілочисельної матриці розміром NxM:

int *A, n, m;

A=(int *) calloc (N*M, sizeof(int));

Для виділення пам’яті можна також використати функцію malloc:

A=(int *) malloc (N*M*sizeof(int));

Або операцію new:

A=new int (N*M);

Після виділення пам'яті, залишається знайти спосіб звернутися до елементу матриці. Всі елементи двовимірного масиву зберігаються в одновимірному масиві розміром NxM елементів. Спочатку в цьому масиві розташовано 0-й рядок матриці, потім 1-й і т. д. Тому для звернення до елемента Ai, j необхідно за номером рядка i та номером стовпця j обчислити номер елемента k в динамічному масиві. Враховуючи, що в масиві елементи нумеруються з нуля k = iM + j, звернення до елемента A[i] [j] буде таким *(A + i*m+j).