Использование динамических списков на примере игры «Крестики-нолики»

КУРСОВАЯ РАБОТА по дисциплине

«Технологии программирования»

Тема: «Использование динамических списков на примере игры „Крестики-нолики“»

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

Достоинства динамической памяти:

— экономичность и эффективность ее использования;

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

— статические переменные существуют только в течение жизни блока, в котором они объявлены, а динамические — и после выхода из блока до окончания программы, а на практике — столько, сколько нужно по алгоритму;

— переменная, размещаемая динамически, не объявляется в разделе VAR и не имеет имени в программе («невидимка»). Компилятор не планирует выделение места в памяти под такие переменные.

Недостатки динамической памяти:

— усложняются процессы выделения и освобождения динамической памяти по сравнению со статической;

— усложняются алгоритмы обработки данных, представленных динамическими структурами.

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

· Указатель (на участок динамической памяти) определен как локальный объект автоматической памяти. В этом случае выделенная память будет недоступна при выходе за пределы блока локализации указателя, и ее нужно освободить перед выходом из блока.

· Указатель определен как локальный объект статической памяти. Динамическая память, выделенная однократно в блоке, доступна через указатель при каждом повторном входе в блок. Память нужно освободить только по окончании ее использования.

· Указатель является глобальным объектом по отношению к блоку. Динамическая память доступна во всех блоках, где «виден» указатель. Память нужно освободить только по окончании ее использования.

Указатель может находиться в одном из трех состояний, а именно:

не инициализирован;

содержит адрес размещения;

содержит значение предопределенной константы nil; такой указатель называется пустым, то есть не указывает ни на какую переменную.

Указатель со значением nil содержит 0 в каждом из четырех байтов.

Указатели можно

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

Указатель нельзя

ь отпечатать;

ь вывести на экран.

Средства выделения и освобождения памяти

В языке C++ существуют предусмотренные стандартом C++, а также перешедшие «в наследство» от C средства выделения и освобождения памяти. Кроме того, каждая платформа предоставляет свои средства управления памятью (как правило, стандартные языковые средства как раз к ним и обращаются, но у программиста есть возможность обратиться к ним непосредственно). Проблема этих систем и языков (в том числе C++) состоит в том, что программист сам отвечает за своевременное освобождение блоков памяти после того, как в них отпадает необходимость — для этого тоже есть специальные функции. Если программист забудет освободить блок, впоследствии может возникнуть нехватка памяти — виртуальное адресное пространство процесса «забьется» и свободного места не останется, хотя в то же время в памяти будут присутствовать блоки, которые фактически не используются.

Рассмотрим коротко средства управления памятью.

Оператор new очень удобен — он не требует указания размера блока, который нужно выделить. Размер определяется компилятором автоматически исходя из типа, который указывается после ключевого слова new. Кроме вызова самой функции выделения памяти происходит еще и вызов конструктора объекта, если указан объектный тип. Синтаксис вызова оператора имеет несколько вариантов, рассмотрим наиболее часто употребляемый:

new Type (parameters)

где Type — тип создаваемого объекта, на основе которого компилятор автоматически определит требуемый для него объем памяти;

parameters — необязательный список параметров, который будет передан конструктору объекта. В случае отсутствия списка параметров скобки указывать необязательно.

Функция malloc, доставшаяся языку C++ в наследство от C, требует указания необходимого количества байт и не производит кроме собственно выделения памяти никаких дополнительных действий.

Функции операционной системы Windows — LocalAlloc и GlobalAlloc — считаются устаревшими, хотя и поддерживаются в целях совместимости. Современным приложениям рекомендуется пользоваться HeapAlloc, а также VirtualAlloc, которая, помимо выделения памяти, поддерживает операцию резервирования памяти и выделения зарезервированной памяти.

Соответственно, средства освобождения памяти следующие.

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

Функция free () освобождает выделенный с помощью malloc () блок. Следует передать адрес блока.

В языке C++ имеются средства создания динамических структур данных, которые позволяют во время выполнения программы образовывать объекты, выделять для них память, освобождать память, когда в них исчезает необходимость.

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

Динамические структуры данных — это структуры данных, память под которые выделяется и освобождается по мере необходимости.

Динамические структуры данных в процессе существования в памяти могут изменять не только число составляющих их элементов, но и характер связей между элементами. При этом не учитывается изменение содержимого самих элементов данных. Такая особенность динамических структур, как непостоянство их размера и характера отношений между элементами, приводит к тому, что на этапе создания машинного кода программа-компилятор не может выделить для всей структуры в целом участок памяти фиксированного размера, а также не может сопоставить с отдельными компонентами структуры конкретные адреса. Для решения проблемы адресации динамических структур данных используется метод, называемый динамическим распределением памяти, то есть память под отдельные элементы выделяется в момент, когда они «начинают существовать» в процессе выполнения программы, а не во время компиляции. Компилятор в этом случае выделяет фиксированный объем памяти для хранения адреса динамически размещаемого элемента, а не самого элемента.

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

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

· В процессе работы программы нужен массив, список или иная структура, размер которой изменяется в широких пределах и трудно предсказуем.

· Когда размер данных, обрабатываемых в программе, превышает объем сегмента данных.

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

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

· размер структуры ограничивается только доступным объемом машинной памяти;

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

· большая гибкость структуры.

Вместе с тем, связное представление не лишено и недостатков, основными из которых являются следующие:

· на поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память;

· доступ к элементам связной структуры может быть менее эффективным по времени.

Порядок работы с динамическими структурами данных следующий:

1. создать (отвести место в динамической памяти);

2. работать при помощи указателя;

3. удалить (освободить занятое структурой место).

Динамические структуры широко применяют и для более эффективной работы с данными, размер которых известен, особенно для решения задач сортировки.

Одним из видов динамической структуры является — список.

Связные линейные списки

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

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

Графически связи в списках удобно изображать с помощью стрелок. Если компонента не связана ни с какой другой, то в поле указателя записывают значение, не указывающее ни на какой элемент. Такая ссылка обозначается специальным именем — nil.

Машинное представление связных линейных списков

На рисунке приведена структура односвязного списка. На нем поле INF — информационное поле, данные, NEXT — указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка.

Структура односвязного списка

Однако, обработка односвязного списка не всегда удобна, так как отсутствует возможность продвижения в противоположную сторону. Такую возможность обеспечивает двухсвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. Структура линейного двухсвязного списка приведена на рисунке, где поле NEXT — указатель на следующий элемент, поле PREV — указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать nil,.

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

Структура двухсвязного списка

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

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

Структура кольцевого двухсвязного списка

В памяти список представляет собой совокупность дескриптора и одинаковых по размеру и формату записей, размещенных произвольно в некоторой области памяти и связанных друг с другом в линейно упорядоченную цепочку с помощью указателей. Запись содержит информационные поля и поля указателей на соседние элементы списка, причем некоторыми полями информационной части могут быть указатели на блоки памяти с дополнительной информацией, относящейся к элементу списка. Дескриптор списка реализуется в виде особой записи и содержит такую информацию о списке, как адрес начала списка, код структуры, имя списка, текущее число элементов в списке, описание элемента и т. д., и т. п. Дескриптор может находиться в той же области памяти, в которой располагаются элементы списка, или для него выделяется какое-нибудь другое место.

Реализация операций над связными линейными списками

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

На всех рисунках сплошными линиями показаны связи, имевшиеся до выполнения и сохранившиеся после выполнения операции. Пунктиром показаны связи, установленные при выполнении операции. Значком 'x' отмечены связи, разорванные при выполнении операции. Во всех операциях чрезвычайно важна последовательность коррекции указателей, которая обеспечивает корректное изменение списка, не затрагивающее другие элементы. При неправильном порядке коррекции легко потерять часть списка. Поэтому на рисунках рядом с устанавливаемыми связями в скобках показаны шаги, на которых эти связи устанавливаются.

Вставка элемента в список

Вставка элемента в середину 1-связного списка

Вставка элемента в середину 2-связного списка

Приведенные примеры обеспечивают вставку в середину списка, но не могут быть применены для вставки в начало списка. При последней должен модифицироваться указатель на начало списка, как показано на рисунке.

Вставка элемента в начало 1-связного списка

Удаление элемента из списка

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

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

Перестановка элементов списка

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

Нелинейные разветвленные списки

Основные понятия

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

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

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

Схематическое представление разветвленного списка

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

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

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

Длина. Это число элементов уровня 1 в списке. Например, длина списка на рисунке равна 3.

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

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

Структура элемента разветвленного списка

В этом случае указатель down указывает на данные или на подсписок. Поскольку списки могут составляться из данных различных типов, целесообразно адресовать указателем down не непосредственно данные, а их дескриптор, в котором может быть описан тип данных, их длина и т. п. Само описание того, является ли адресуемый указателем данных объект атомом или узлом также может находиться в этом дескрипторе. Удобно сделать размер дескриптора данных таким же, как и элемента списка. В этом случае размер поля type может быть расширен, например, до 1 байта и это поле может индицировать не только атом/подсписок, но и тип атомарных данных, поле next в дескрипторе данных может использоваться для представления еще какой-то описательной информации, например, размера атома.

Пример представления списка элементами одного формата

Постановка задачи

Для демонстрации применения списков, требуется написать игру. Программа написана на языке С++. Тип — однонаправленный, не кольцевой, без головного элементом. В силу особенностей реализации игры, список, также, является разветвлённым. Тип игры выбирается произвольно, в случае данной работы — морской бой.

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

Описание работы

Программа написана на языке С++. Тип списка — однонаправленный, не кольцевой, без головного элемента, разветвлённый.

При запуске программы происходит вызов меню. Меню циклическое.

Пункты меню:

1. New game (Старт игры)

2. Options (Настройки)

3. Information (Информации о разработчике)

4. Exit (Выход) Начало игры происходит при выборе соответствующего пункта меню. Игра представляет собой 2 поля размером 10 на 10. При нажатии enter происходит «выстрел» по клетке поля. Цель игры — уничтожить все корабля противника.

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

Тестирование

Новая игра. 2 поля 10×10. Сформированы 2 списка Игрок сделал ход и промахнулся. Очередь компьютера делать ход.

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

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

После этого он уничтожает четырёхпалубный корабль игрока.

После этого игра продолжается.

В итоге победил игрок.

Заключение

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

Для работы с динамической памятью используют указатели. С их помощью осуществляется доступ к участкам динамической памяти, которые называются динамическими переменными. Для хранения динамических переменных выделяется специальная область памяти, называемая «кучей» .

Список материалов

Литература

: Р. Лафоре Объектно-ориентированное программирование в C++.

Бьерн Страуструп. Язык программирования С++

Подбельский В. Язык С++

Листинг списков

class shiplist

{

public:

struct ship //элемент списка

{

int x, y;

ship* nextright;

ship* nextdown;

ship (int _x, int _y, ship *nr = NULL, ship *nd = NULL)// конструктор с передающ значениями

{

x = _x;

y = _y;

nextright = nr;

nextdown = nd;

}

};

int shipCount;

ship* first; // Первый элемент

ship* firstdown; //Верхний элемент

ship* lastright; //Последний элемент в списке корабля

ship* lastdown;// Последний элемент в списке кораблей

shiplist () // Конструктор списка

{

shipCount = 0;

first = firstdown = lastright = lastdown = NULL;

}

void addshipFirst (int _x, int _y) //добавление первого корабля

{

ship* newship = new ship (_x, _y);

first = newship;

lastright = newship;

lastdown = newship;

shipCount++;

}

void addshipRight (int _x, int _y) //добавление корабля вправо (ячейки)

{

ship* newship = new ship (_x, _y);

lastright->nextright = newship;

lastright = newship;

shipCount++;

}

void addshipDown (int _x, int _y) //добавление первой ячейки следующего корабля

{

ship* newship = new ship (_x, _y);

lastdown->nextdown = newship;

lastdown = newship;

lastright = newship;

shipCount++;

}

bool delShip (int _x, int _y) //удаление ячейки

{

ship* prev = NULL,

*current = first,

*lastdown = first,

*prevup = NULL;

while (current) //пока не 0

{

while (current->nextdown) //пока снизу не ноль

{

while (current->nextright) //пока справа не ноль

{

if ((current->x == _x) && (current->y == _y)) //если значения совпали

{

if (current == first) //если первый

{

if (current->nextright) //если справа что-то есть

{

current->nextright->nextdown = current->nextdown;

first = current->nextright;

lastdown = first;

delete current;

shipCount—;

current = first;

return true;

}

else

{

first = current->nextdown;

lastdown = first;

delete current;

shipCount—;

current = first;

return true;

}

else if ((prev == 0) && (prevup ≠ 0) && (current->nextright ≠ 0)) //если слева пусто и сверху есть клетка и справа не пусто

{

prevup->nextdown = current->nextright;

current->nextright->nextdown = current->nextdown;

lastdown = current->nextright;

delete current;

shipCount—;

current = lastdown;

return true;

}

else if (prev) //если предыдущий не равен 0

{

prev->nextright = current->nextright;

delete current;

shipCount—;

current = prev->nextright;

return true;

}

}

else //если значения не совпали идём дальше

{

prev = current;

current = current->nextright;

}

}

if ((current->x == _x) && (current->y == _y)) //если справа 0

{

if (prev) //если слева не пусто

{

prev->nextright = 0;

delete current;

shipCount—;

current = prev;

return true;

}

else if ((prev == 0) && (prevup ≠ 0) && (current->nextright == 0) && (current->nextdown ≠0)) //если слева пусто и сверху есть клетка и справа пусто и снизу не пусто

{

prevup->nextdown = current->nextdown;

lastdown = current->nextdown;

delete current;

shipCount—;

current = lastdown;

return true;

}

prevup = lastdown;

current = lastdown->nextdown;

lastdown = current;

prev = 0;

}

delete current;

shipCount—;

return true;

}

return false;

}