Структуры и алгоритмы обработки данных

Лабораторная работа.

Структура данных «кольцевой список»

Цель работы: изучить построение кольцевых списков и алгоритмы работы с этой структурой данных, научиться разрабатывать алгоритмы решения задач с использованием структуры данных «кольцо» на языке 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;

}

Контрольный тест.



Выводы.

Контрольные вопросы.

1. 
   Дать определение структуре "кольцевой список".
   

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

2. 
   Где применяется структура данных «кольцо»?
   

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

---

Смотрите также файлы

• Инструкция по технике безопасности для учащихся на занятиях по футболу.doc

• Влияние занятий легкой атлетикой на организм.doc

• Даниил Крутов Юб 311.pptx

• Индивидуальный шифр а а а.doc

• Аннотация Актуальность методической разработки.docx