кольцевой список. Кольцо. Лабораторная работа. Структура данных кольцевой список
 Скачать 25.4 Kb.
|
|
Структуры и алгоритмы обработки данных Лабораторная работа. Структура данных «кольцевой список» Цель работы: изучить построение кольцевых списков и алгоритмы работы с этой структурой данных, научиться разрабатывать алгоритмы решения задач с использованием структуры данных «кольцо» на языке C++. Словесная постановка задачи. N ребят стоят по кругу. В считалочке k слов. Удалять каждого k-го ребенка, смыкая круг. Используя кольцевой список, вывести каким по счёту нужно встать, чтобы остаться последним в кругу? Входящие физические величины – количество людей в кругу, количество слов в считалочке. Задача имеет решение в том случае, если длина очереди больше 0. Математическая модель. В этом подразделе вводятся математические описания физических величин и математическое описание их взаимодействий. Цель подраздела – представить решаемую задачу в математической формулировке Алгоритм. Программа создает кольцевой список из n элементов, а затем удаляет из него n-1 элементов, которые по номеру являются k-ми относительно первого элемента (если число k (количество слов в считалке) превышает количество элементов, то список обходится несколько раз). На каждом шаге (после удаления очередного элемента) отображается содержимое списка. Отсчет следующего круга начинается после удаленного элемента. Круг заполняется нулями, числа 1-2-3… это элементы которые были удалены. Листинг. #include using namespace std; void Print(int* items, int n) { int i; for (i = 0; i < n; i++) cout << items[i] << " "; cout << endl; } int Next(int* items, int l, int n, int k) { int tk = l + 1, kl = 1; do { if (tk == n) tk = 0; else { if (items[tk++] == 0) ++kl; } } while (kl <= k); return tk - 1; } int main() { setlocale(LC_ALL, "ru"); int n, k; cout << "Введите количество участников: "; cin >> n; cout << "Введите количество слов в считалочке: "; cin >> k; int i, l = -1, t, m = 0; int items[1000]; for (i = 0; i < n; i++) { //инициализируем всеми нулями items[i] = 0; } while (m < n - 1) { t = Next(items, l, n, k); items[t] = ++m; l = t; Print(items, n); } Print(items, n); for (i = 0; i < n, items[i] != 0; i++) ; cout << "Участник, оставшийся последний: "<< i + 1; return 0; } Контрольный тест.  Выводы. Контрольные вопросы. Дать определение структуре "кольцевой список". Циклический (кольцевой) список – это структура данных, представляющая собой последовательность элементов, последний элемент которой содержит указатель на первый элемент списка, а первый (в случае двунаправленного списка) – на последний. Где применяется структура данных «кольцо»? Списки с круговой связью широко используются в приложениях, где задачи должны повторяться, или в приложениях с разделением времени. Циклическая очередь может отслеживать задачи, которые были выполнены и которые должны быть выполнены, как только конкретная задача выполнена, она переходит к следующей, а когда весь набор задач завершен, он снова переходит к первой задаче, чтобы завершить оставшуюся работу. |