132_2. 5— копия. Основные теоретические положения

• Название: Основные теоретические положения
• Дата: 07.06.2021
• Размер: 159.44 Kb.
• Имя файла: 132_2. 5— копия.docx
• Тип: Документы; #215178

_{Цель работы.}

изучение свойств и организация динамических массивов и двусвязных списков; получение практических навыков в работе с динамическими массивами и двусвязными списками; проведение сравнительной характеристики скорости вставки, получения и удаления элементов из них.
Основные теоретические положения.

Одномерные динамические массивы

Для того чтобы создать в динамической области некоторый объект, необходима одна обычная переменная-указатель (не динамическая переменная). Сколько таких объектов понадобится для одновременной обработки, столько необходимо иметь обычных переменных-указателей. Таким образом, проблема задач неопределенной размерности созданием одиночных динамических объектов решена быть не может.

Решить эту проблему поможет возможность создавать в динамической области памяти массивы объектов с таким количеством элементов, которое необходимо в данный момент работы программы, т. е. создание динамических массивов. Действительно, для представления массива требуется всего одна переменная-указатель, а в самом массиве, на который ссылается этот указатель, может быть столько элементов, сколько требуется в данный момент времени.

Очень часто в процессе работы программы требуется изменять размеры уже созданных и заполненных данными массивов. Общий алгоритм решения этой задачи таков:

1.      создать исходный массив размерности N1 и заполнить его данными;
2.      создать промежуточный массив размерности N2 (пусть N2 > N1);
3.      скопировать данные из исходного массива в промежуточный массив;
4.      освободить память от исходного массива;
5.      переменной-указателю исходного массива присвоить значение переменной-указателя промежуточного массива;
6.      заполнить новые элементы массива данными.

Для того чтобы получить двумерный массив, необходимо:

1)  создать одномерный динамический массив из RowCount указателей на базовый тип элементов массива (в нашем случае – указателей на тип int);
2)  в цикле создать RowCount одномерных динамических массивов, каждый из которых содержит ColCount элементов базового типа (в нашем  случае –  указателей на тип int), и адреса их первых элементов записать в соответствующие элементы «вертикального» массива.

Обычный одномерный массив определяется как указатель на базовый тип данных элементов этого массива. Базовым типом элементов этого массива являются указатели int*. Для того чтобы определить указатель на указатель достаточно использовать следующую конструкцию: (int*)* или проще int**.

Для создания динамических двумерных массивов с другими базовыми типами элементов достаточно в предыдущих примерах заменить тип данных int, на необходимый тип данных. Ну, и конечно, изменить работу с элементами массива в соответствии с их типом данных. Обязательные места исправлений выделены красным цветом.

По аналогии с двумерными динамическими массивами можно создавать и массивы большей мерности.

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

Каждый узел двусвязного (двунаправленного) линейного списка содержит два поля указателей – на следующий и на предыдущий узлы. Указатель на предыдущий узел корня списка содержит нулевое значение. Указатель последнего узла также содержит нулевое значение.

Основные действия, производимые над узлами двусвязного линейного списка (ДЛС):

1)  инициализация списка;
2)  добавление узла в список;
3)  удаление узла из списка;
4)  удаление корня списка;
5)  вывод элементов списка;
6)  вывод элементов списка в обратном порядке;
7)  взаимообмен двух узлов списка.

Порядок действия очень похож на односвязный линейный список, но необходимо учитывать, что в двусвязном списке имеется два указателя: на следующий и предыдущий элементы.

Удаление элементов двусвязного списка

Удаление первого элемента и последнего элемента практически аналогично удалению элемента из односвязного списка. Нужно изменить значение указателя на первый элемент, обнулить значение указателя головы/хвоста, освободить динамическую память.

С удалением элемента из середины списка дело обстоит сложнее: необходимо проделать аналогичные операции по отношению к двум узлам, а не к одному.

Вставка узла

Вставка нового узла в двусвязный линейный список проводится аналогично. Также присутствует три ситуации: вставка нового корня, вставка последним элементом и вставка узла в середину списка.



Вставка нового корневого узла отличается от удаления тем, что необходимо изменить Head-указатель прошлого корневого узла, указатель на корневой узел и правильно связать новый узел со списком.

Вставка узла в конец списка не должна вызывать затруднений: необходимо изменить Tail-указатель прежнего последнего элемента на адрес нового узла, затем правильно связать новый узел с двусвязным списком (Head – адрес на предыдущий элемент, Tail – NULL-указатель).

Обмен элементов местами

Больше всего трудностей может возникнуть именно с взаимообменом элементов двусвязного списка. Главная проблема – возможная путаница в указателях. Нужно правильно изменить указатели всех затрагиваемых узлов.



Видно, сколько необходимо изменить адресов указателей, чтобы двумерный список работал корректно. Если хоть один указатель будет ссылаться неправильно, то список будет работать некорректно и может вовсе зациклиться. Причем программист этого может не заметить, если поле Data однородно или вовсе отсутствует. Поэтому (как и с любыми указателями) нужно быть внимательным.

Задача

Необходимо реализовать программу, которая выполняет следующие действия.

1.   Формирование целочисленного одномерного массива размерности N, где:

a) пользователь вводит количество элементов в массиве, который будет автоматически заполняться случайными числами (0 до 99);

б) пользователь вводит в консоль элементы массива, N определяется автоматически по количеству введенных элементов;

в) * массив считывается с файла, N определяется как количество элементов массива в файле.

2.   Определение скорости создания динамического массива п. 1.

3.   Вставка, удаление и получение элемента массива. Удаление и получение элемента необходимо реализовать по индексу и по значению.

4.   Определение скорости вставки, удаления и получения элемента массива п. 3.

5.   Формирование двусвязного списка размерности N, где:

a) пользователь вводит количество элементов в списке, который будет автоматически заполняться случайными числами (0 до 99);

б) пользователь вводит в консоль элементы списка, N определяется автоматически по количеству введенных элементов;

в) * список считывается с файла, N определяется как количество элементов списка в файле.

6.   Определение скорости создания двусвязного списка п. 5.

7.   Вставка, удаление и получение элемента двусвязного списка. Удаление и получение элемента необходимо реализовать по индексу и по значению.

8.   Определение скорости вставки, удаление и получения элемента двусвязного списка п. 7.

Должна быть возможность запуска каждого пункта многократно, если есть возможность (если в списке/массиве нет элементов, то нельзя ничего удалить и об этом нужно сообщить пользователю). Необходимо сравнить результаты. Для этого пункты 1–4 и 5–8 должны принимать одинаковые значения.

void List::AddTail(int n)

{

Node * temp = new Node;

// Следующего нет

temp->Next = 0;
temp->data = n;

temp->Prev = Tail;
// Если элементы есть?

if (Tail != 0)

Tail->Next = temp;
if (countElements == 0)

Head = Tail = temp;

else

Tail = temp;
countElements++;

}

void List::Insert()

{

cout << "\nInsert element.\n";
int pos;

cout << "Input position: ";

cin >> pos;
// Позиция от 1 до Count?

if (pos < 1 || pos > countElements + 1)

{

cout << "Incorrect position !!!\n";

return;

}
// Если вставка в конец списка

if (pos == countElements + 1)

{

int data;

cout << "Input new number: ";

cin >> data;

timeStart = Clock::now();

Add(data); // Добавление в конец списка

timeEnd = Clock::now();

cout << "\nTime to add an item: " << sec(timeEnd - timeStart).count() << " s." << endl;

return;

}

else if (pos == 1)

{

int data;

cout << "Input new number: ";

cin >> data;

timeStart = Clock::now();

AddTail(data); // Добавление в начало списка

timeEnd = Clock::now();

cout << "\nTime to add an item: " << sec(timeEnd - timeStart).count() << " s." << endl;

}
int i = 1; // Счетчик

Node * temp = new Node;

cout << "Input new number: "; cin >> temp->data;
timeStart = Clock::now();
Node *Ins = Head;
while (i < pos)

{

// Доходим до элемента,

// перед которым вставляемся

Ins = Ins->Next;

i++;

}
// Доходим до элемента,

// который предшествует

Node * PrevIns = Ins->Prev;
// настройка связей

if (PrevIns != 0 && countElements != 1)

PrevIns->Next = temp;
temp->Next = Ins;

temp->Prev = PrevIns;

Ins->Prev = temp;
countElements++;

timeEnd = Clock::now();

cout << "\nTime to add an item: " << sec(timeEnd - timeStart).count() << " s." << endl;

}
void List::Del()

{

int var = -1;
cout << "\nRemoving an item.\n";
cout << "\n1) By position\n"

<< "2) By value\n";

cout << endl;

cout << "Enter: "; cin >> var;
if (var == 1) {

int pos;

cout << "Input position: "; cin >> pos;
timeStart = Clock::now();

if (pos < 1 || pos > countElements) // Неверная позиция

{

cout << "Incorrect position !\n";

timeEnd = Clock::now();

return;

}
int i = 1; // Счетчик

Node *Del = Head;

while (i < pos) // Доходим до элемента, который удаляется

{

Del = Del->Next;

i++;

}
Node * PrevDel = Del->Prev; // Доходим до элемента, который предшествует удаляемому

Node * AfterDel = Del->Next; // Доходим до элемента, который следует за удаляемым
if (PrevDel != 0 && countElements != 1) // Если удаляем не голову

PrevDel->Next = AfterDel;
if (AfterDel != 0 && countElements != 1) // Если удаляем не хвост

AfterDel->Prev = PrevDel;
if (pos == 1) // Удаляются крайние?

Head = AfterDel;

if (pos == countElements)

Tail = PrevDel;
delete Del; // Удаление элемента

timeEnd = Clock::now();

cout << "\nTime to remove an item: " << sec(timeEnd - timeStart).count() << " s." << endl;

}

else {

int i = 1; // Счетчик

int count = 1; // Счетчик

int value;

cout << "Input value: "; cin >> value;
timeStart = Clock::now();

Node *Del = Head;

for (int i = 1; i < countElements+1; i++) {
if (Del->data == value) {

count = i;

}

Del = Del->Next;

}

if (count < 0) // Неверное значение

{

cout << "Incorrect value!\n";

timeEnd = Clock::now();

return;

}
Del = Head;

while (i < count) // Доходим до элемента, который удаляется

{

Del = Del->Next;

i++;

}
Node *PrevDel = Del->Prev; // Доходим до элемента, который предшествует удаляемому

Node *AfterDel = Del->Next; // Доходим до элемента, который следует за удаляемым
if (PrevDel != 0 && countElements != 1) // Если удаляем не голову

PrevDel->Next = AfterDel;
if (AfterDel != 0 && countElements != 1) // Если удаляем не хвост

AfterDel->Prev = PrevDel;
if (count == 1) // Удаляются крайние?

Head = AfterDel;

if (count == countElements)

Tail = PrevDel;
delete Del; // Удаление элемента

timeEnd = Clock::now();

cout << "\nTime to remove an item: " << sec(timeEnd - timeStart).count() << " s." << endl;

}
countElements--;

}

void List::Del(int pos)

{

int i = 1;

Node *Del = Head;
while (i < pos)

{

Del = Del->Next;

i++;

}
Node *PrevDel = Del->Prev;

Node *AfterDel = Del->Next;
if (PrevDel != 0 && countElements != 1)

PrevDel->Next = AfterDel;

if (AfterDel != 0 && countElements != 1)

AfterDel->Prev = PrevDel;
if (pos == 1)

Head = AfterDel;

if (pos == countElements)

Tail = PrevDel;

delete Del;
countElements--;

}
Node *List::GetElem()

{

int var = -1;
cout << "\n1) By position\n"

<< "2) By value\n";

cout << endl;

cout << "Enter: "; cin >> var;
if (var == 1) {

int pos;

cout << "Input position: "; cin >> pos;

timeStart = Clock::now();

Node *temp = Head;
if (pos < 1 || pos > countElements) // Неверная позиция

{

cout << "Incorrect position!\n";

timeEnd = Clock::now();

return 0;

}
int i = 1;

while (i < pos && temp != 0) // Ищем нужный нам элемент

{

temp = temp->Next;

i++;

}
timeEnd = Clock::now();

cout << "\nTime to remove an item: " << sec(timeEnd - timeStart).count() << " s." << endl;

if (temp == 0)

return 0;

else

return temp;

}

else {

int count = -1; // Счетчик

int value;

int i = 1;

cout << "Input value: "; cin >> value;
timeStart = Clock::now();

Node *temp = Head;
for (int i = 1; i < countElements + 1; i++) {
if (temp->data == value) {

count = i;

}

temp = temp->Next;

}
if (count < 0) // Неверное значение

{

cout << "Incorrect value!\n";

timeEnd = Clock::now();

return 0;

}
temp = Head;

while (i < count) // Доходим до элемента, который удаляется

{

temp = temp->Next;

i++;

}

timeEnd = Clock::now();

cout << "\nTime to remove an item: " << sec(timeEnd - timeStart).count() << " s." << endl;
if (temp == 0)

return 0;

else

return temp;

}

}
int *GenerateArr(int *ar) {
//srand(time(NULL));
char option;
cout << "a)Array of random numbers\n" << "b)Enter numbers into an array\n" << "Enter: ";

cin >> option;
if (option == 'a') {
int count = 0;

cout << "Enter the number of elements: ";

cin >> count;

timeStart = Clock::now();

ar = new int[count];

for (int i = 0; i < count; i++) {

ar[i] = rand() % 99;

}

timeEnd = Clock::now();
countElements = count;
cout << endl;

cout << "Generation time: " << sec(timeEnd - timeStart).count() << " s." << endl;

}

else {

int count = 0;

while (cin >> ar[count])

{

char c = static_cast(cin.get());

count++;

if (isdigit(c) || c == '-' || c == '+')

{
}

else if (c == ' ')

{

continue;

}

else

{

break;

}

}

countElements = count;

}
for (int i = 0; i <= countElements - 1; i++) {

cout << ar[i] << " ";

}
return ar;

}
int *AddElementByIndex(int *ar) {
int index = 0;

int value = 0;
int *arrNew = new int[countElements + 1];
cout << "Enter the index: "; cin >> index;
if (index <= countElements - 1) {

cout << "Enter value: "; cin >> value;

timeStart = Clock::now();

for (int i = 0; i <= index - 1; i++) {

arrNew[i] = ar[i];

}

arrNew[index] = value;

for (int i = index + 1; i <= countElements+1; i++) {

arrNew[i] = ar[i-1];

}

countElements++;

timeEnd = Clock::now();
cout << "\nTime to add an item: " << sec(timeEnd - timeStart).count() << " s." << endl;
return arrNew;

}

else {

cout << "Element missing!\n";

return ar;

}

}
int *DeliteElement(int *ar) {
int var = -1;

int index = -1;

int value = 0;

int *arrNew = new int[countElements - 1];
cout << endl;

cout << "\n1) By index\n"

<< "2) By value\n";

cout << endl;

cout << "Enter: "; cin >> var;

if (var == 1) {
cout << "Enter the index: "; cin >> index;
if (index <= countElements - 1 && index >= 0) {

timeStart = Clock::now();

for (int i = 0; i < index; i++) {

arrNew[i] = ar[i];

}

for (int i = index + 1; i <= countElements - 1; i++) {

arrNew[i - 1] = ar[i];

}
countElements--;
timeEnd = Clock::now();

cout << "\nTime to remove an item: " << sec(timeEnd - timeStart).count() << " s." << endl;

return arrNew;

}

else {

cout << "Element missing!\n";

return ar;

}

}

else {

cout << "Enter the value: "; cin >> value;
timeStart = Clock::now();

for (int i = 0; i < countElements; i++) {

if (value == ar[i]) {

index = i;

}

}
if (index >= 0) {

for (int i = 0; i < index; i++) {

arrNew[i] = ar[i];

}

for (int i = index + 1; i <= countElements - 1; i++) {

arrNew[i - 1] = ar[i];

}
countElements--;
timeEnd = Clock::now();

cout << "\nTime to remove an item: " << sec(timeEnd - timeStart).count() << " s." << endl;

return arrNew;

}

else {

cout << "Item not found!\n";

return ar;

}

}

}
int *DeliteElements(int *ar, int index) {
int *arrNew = new int[countElements - 1];
for (int i = 0; i < index; i++) {

arrNew[i] = ar[i];

}

for (int i = index + 1; i <= countElements - 1; i++) {

arrNew[i - 1] = ar[i];

}
countElements--;

return arrNew;

}
int *DeliteOddArray(int *arrr) {

timeStart = Clock::now();
int count = countElements;

int i = 0;

for (int j = 0; j < count + 1; j++) {

if (j % 2 == 0) {

arrr = DeliteElements(arrr, j - i);

i++;

}

}

timeEnd = Clock::now();

cout << "\nTime to remove an odd item: " << sec(timeEnd - timeStart).count() << " s." << endl;

return arrr;

}
int GetElement(int *ar) {
int var = -1;

int *element = new int;

int index = -1;

int value = 0;
cout << "\n1) By index\n"

<< "2) By value\n";

cout << endl;

cout << "Enter: "; cin >> var;
if (var == 1) {

cout << "Enter the index: "; cin >> index;

timeStart = Clock::now();

if (index <= countElements - 1 && index >= 0) {

*element = ar[index];

}

}

else {

cout << "Enter the value: "; cin >> value;

timeStart = Clock::now();

for (int i = 0; i < countElements; i++) {

if (value == ar[i]) {

index = i;

}

}
if (index >= 0) {

*element = ar[index];

}

else {

cout << "Item not found!\n";

}

}
timeEnd = Clock::now();

cout << "\nTime to get an item: " << sec(timeEnd - timeStart).count() << " s." << endl;

return *element;

}
void PrintArray(int *ar) {

cout << "Array: ";

for (int i = 0; i <= countElements - 1; i++) {

cout << ar[i] << " ";

}

}
int main()

{

int varOne = -1;

do {

cout << "1) Array\n"

<< "2) List\n";

cout << endl;

cin >> varOne;
if (varOne == 1) {

int element = -1;

int var = -1;

int *arr = new int[1000]; // выделяем память под массив
arr = GenerateArr(arr);

do {

cout << endl;

cout << "\n1) Insert item\n"

<< "2) Remove item\n"

<< "3) Get the item\n"

<< "4) Removing odd items\n"

<< "0) Exit\n";

cout << endl;
cin >> var;
if (var == 1) {

cout << "Adding an item by index\n";

arr = AddElementByIndex(arr);

PrintArray(arr);

}

else if (var == 2) {

cout << "Remove item\n";

arr = DeliteElement(arr);

PrintArray(arr);

}

else if (var == 3) {

cout << "Get item\n";

element = GetElement(arr);

cout << "Element: " << element;

}

else if (var == 4) {

cout << "Removing odd items\n";

arr = DeliteOddArray(arr);

PrintArray(arr);

}

else {

break;

}
} while (var != 0);

}

else if (varOne == 2) {

int var = -1;
List *lst = new List;
lst = GenerateLst(lst);

lst->Show();
do {

cout << endl;

cout << "\n1) Insert item\n"

<< "2) Remove item\n"

<< "3) Get the item\n"

<< "4) Removing odd items\n"

<< "0) Exit\n";

cout << endl;
cin >> var;
if (var == 1) {

cout << "Adding an item by index\n";

lst->Insert();

lst->Show();

}

else if (var == 2) {

cout << "Remove item\n";

lst->Del();

lst->Show();

}

else if (var == 3) {

cout << "Get item\n";

cout << "Element: " << lst->GetElem();

}

else if (var == 4) {

cout << "Removing odd items\n";

timeStart = Clock::now();

int count = countElements;

int i = 0;

for (int j = 1; j < count+1; j++) {

if (j % 2 == 1) {

lst->Del(j-i);

i++;

}

}

timeEnd = Clock::now();

cout << "\nTime to remove an odd item: " << sec(timeEnd - timeStart).count() << " s." << endl;

lst->Show();

}

else {

break;

}
} while (var != 0);

}

} while (varOne > 0);

}