132_2. 5— копия. Основные теоретические положения
Скачать 159.44 Kb.
|
Цель работы. изучение свойств и организация динамических массивов и двусвязных списков; получение практических навыков в работе с динамическими массивами и двусвязными списками; проведение сравнительной характеристики скорости вставки, получения и удаления элементов из них. Основные теоретические положения. Одномерные динамические массивыДля того чтобы создать в динамической области некоторый объект, необходима одна обычная переменная-указатель (не динамическая переменная). Сколько таких объектов понадобится для одновременной обработки, столько необходимо иметь обычных переменных-указателей. Таким образом, проблема задач неопределенной размерности созданием одиночных динамических объектов решена быть не может. Решить эту проблему поможет возможность создавать в динамической области памяти массивы объектов с таким количеством элементов, которое необходимо в данный момент работы программы, т. е. создание динамических массивов. Действительно, для представления массива требуется всего одна переменная-указатель, а в самом массиве, на который ссылается этот указатель, может быть столько элементов, сколько требуется в данный момент времени. Очень часто в процессе работы программы требуется изменять размеры уже созданных и заполненных данными массивов. Общий алгоритм решения этой задачи таков: 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 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); } |