сылки однотипны, но число их может быть различным в зависимости от типа списка.
В связи с этим для описания элемента списка подходит тип «структура», так как этот тип данных может иметь разнотипные поля. Например, для однонаправленного списка элемент должен содержать как минимум два поля: одно поле типа «указатель», другое - для хранения данных пользователя. Для двунаправленного - три поля, два из которых должны быть типа «указатель».
Элементы массива располагаются в памяти в определенном постоянном порядке - подряд, друг за другом, что закрепляется их номерами. Каждый элемент массива имеет свое место, которое не может быть изменено, хотя значение элемента может изменяться. Порядок обработки элементов определяется использованием их номеров, индексов.
В отличие от элементов массива элементы списка могут располагаться в памяти в свободном порядке, не подряд.
Порядок их обработки определяется ссылками, то есть в общем случае очередной элемент своей ссылкой указывает на тот элемент, который должен быть обработан следующим.
Последний по порядку элемент содержит в ссылочной части признак, свидетельствующий о необходимости прекращения обработки элементов списка, указывающий как бы конец списка.
Если последний элемент содержит ссылку на первый элемент списка, то такой список называется кольцевым, циклическим. Изменения в списке при этом минимальны - добавляется ссылка с последнего на первый элемент списка: в адресной части последнего элемента значение Nullзаменяется на адрес первого элемента списка.
При обработке однонаправленного списка могут возникать трудности, связанные с тем, что по списку с такой организацией можно двигаться только в прямом направлении и, как правило, начиная с первого элемента. Обработка списка в обратном направлении сильно затруднена. Для устранения этого недостатка служит двунаправленный список, каждый элемент которого содержит ссылки на последующий и предыдущий элементы.
Такая организация списка позволяет от каждого элемента двигаться по списку как в прямом, так и в обратном направлениях. Наиболее удобной при этом является та организация ссылок, при которой движение, перебор элементов в обратном направлении является строго противоположным перебору элементов в прямом направлении. В этом случае двунаправленный список называетсясимметричным. Например, в прямом направлении элементы линейного списка пронумерованы и выбираются так: 1, 2, 3, 4, 5. Строго говоря, перебирать элементы в обратном направлении можно по-разному, соответствующим способом организуя ссылки, например: 4, 1, 5, 3, 2. Симметричным же будет называться список, реализующий перебор элементов в таком порядке: 5, 4, 3, 2, 1.
Как указывалось ранее, замкнутый, циклический, кольцевой список организован таким образом, что в адресную часть конечного элемента вместо константы null помещается адрес начального элемента (список замыкается на себя). В симметричном кольцевом списке такое положение характерно для обоих - прямого и обратного - списков, следовательно, можно построить циклический двунаправленный список Двунаправленный (двусвязный) список – это структура данных, состоящая из последовательности элементов, каждый из которых содержит информационную часть и два указателя на соседние элементы (рис.1). При этом два соседних элемента должны содержать взаимные ссылки друг на друга.
В таком списке каждый элемент (кроме первого и последнего) связан с предыдущим и следующим за ним элементами. Каждый элемент двунаправленного списка имеет два поля с указателями: одно поле содержит ссылку на следующий элемент, другое поле – ссылку на предыдущий элемент и третье поле – информационное. Наличие ссылок на следующее звено и на предыдущее позволяет двигаться по списку от каждого звена в любом направлении: от звена к концу списка или от звена к началу списка, поэтому такой список называют двунаправленным.
 |
Описание простейшего элемента такого списка выглядит следующим образом:
struct имя_типа {
информационное поле;
адресное поле 1;
адресное поле 2;
};
где информационное поле – это поле любого, ранее объявленного или стандартного, типа;
адресное поле 1 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка ;
адресное поле 2 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес предыдущего элемента списка.
При работе со списками любых видов нельзя обойтись без указателя на первый элемент. Не менее полезными, хотя и не всегда обязательными, могут стать адрес последнего элемента списка и количество элементов. Эти данные могут существовать по отдельности, однако их можно объединить в единый тип «структура» (из-за разнотипности полей: два поля указателей на элементы и числовое поле - для количества элементов). Эта структура и будет представлять так называемый головной элемент списка.
Следуя идеологии динамических структур данных, головной элемент списка также необходимо сделать динамическим, выделяя под него память при создании списка и освобождая после окончания работы. Тем не менее, стоит отметить, что головной элемент может быть и статического типа. Тогда он описывается в разделе VAR как обычная переменная типа RECORD соответствующей структуры.
Использование данных головного элемента делает работу со списком более удобной, но требует определенных действий по его обслуживанию.
Головной элемент содержит основные характеристики списка – адрес первого элемента, адрес последнего элемента, текущее количество элементов списка. Это даёт возможность не создавать и не применять постоянно подпрограммы определения текущего количества элементов списка, поиска адреса последнего элемента списка. Особенно наличие головного элемента облегчает работу с симметричным списком. Кроме того, при работе со списком циклы WHILE … DO и REPEAT…UNTIL могут быть заменены циклами FOR.
Структура головного элемента (приведен минимальный набор полей, последовательность их расположения произвольна)
| First | N | Last |
где:
1. First – адрес первого элемента списка;
2. Last - адрес последнего элемента списка;
3. N - текущее количество элементов списка;
Рис. 1. Двунаправленный список
Описание простейшего элемента такого списка выглядит следующим образом:
struct имя_типа {
информационное поле;
адресное поле 1;
адресное поле 2;
};
где информационное поле – это поле любого, ранее объявленного или стандартного, типа;
адресное поле 1 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка ;
адресное поле 2 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес предыдущего элемента списка.
Головной элемент содержит основные характеристики списка – адрес первого элемента, адрес последнего элемента, текущее количество элементов списка. Это даёт возможность не создавать и не применять постоянно подпрограммы определения текущего количества элементов списка, поиска адреса последнего элемента списка. Особенно наличие головного элемента облегчает работу с симметричным списком. Кроме того, при работе со списком циклы WHILE … DO и REPEAT…UNTIL могут быть заменены циклами FOR.
Структура головного элемента (приведен минимальный набор полей, последовательность их расположения произвольна)
| First | N | Last |
где:
- First – адрес первого элемента списка;
- Last - адрес последнего элемента списка;
- N - текущее количество элементов списка;
Двунаправленный кольцевой список с головным элементом:
Постановка задачи
Для демонстрации применения списков, требуется написать игру. Программа написана на языке С++. Тип списка – двунаправленный, кольцевой, с головным элементом. Тип игры выбирается произвольно, в случае данной работы - сапер.
При заполнении поля игры случайными элементами каждый из них заносится в список. Каждый элемент содержит следующие поля:
i, j – номер строки и столбца ячейки, в которой находится элемент
k – порядковый номер элемента
true/false – boolean переменная, которая говорит является ли элемент бомбой
Когда бомба на поле отмечена флагом верно, соответствующий элемент списка переносится в другой список, состоящий только из отмеченных бомб. В конце игры оба списка выводятся на экран, а потом очищаются.
Описание работы
Меню игры многоуровневое и циклическое, главное меню состоит из четырех пунктов, во втором пункте есть 4 подпункта:
- New game (Новая игра)
- Options (Опции)
- Bomb number (Количество бомб)
- Color (Выбор цвета)
- Red (Красный)
- Green (Зеленый)
-Blue (Синий)
- Difficulty (Сложность)
- 5х5
- 9х9
-Back (Возврат на уровень выше)
-Developers (Разработчики)
-Exit (Выход)
Управление меню производится с помощью стрелочек, выбор пункта клавиша Enter. Выход и возврат на уровень выше с помощью клавиши Esk. Курсор меню цветовой (цвет выделенный строки отличается от общего цвета меню). Выход из меню выполняется с подтверждением.
Начало игры происходит при выборе соответствующего пункта меню. Игра представляет собой поле размером 5 на 5 или 9 на 9, на котором случайным образом расположены бомбы. Цель игры – открывать ячейки поля и с помощью цифр вычислять расположение бомб на поле. Далее необходимо отметить их с помощью флагов, ни разу не ошибившись (не открыв ячейку с бомбой). Игра заканчивается, когда все бомбы отмечены флагами (победа) или открыта ячейка с бомбой (проигрыш).
Тестирование 
Ячейка с бомбой открыта, следовательно зафиксирован проигрыш и выведены на экран списки. Все элементы остались в первом списке, так как не выполнено условие (не отмечена флагом ни одна бомба). Второй список пуст.
На игровом поле отмечены флагами две бомбы, одна ячейка с бомбой открыта. Результат: в первом списке осталось 23 элемента (20 элементов-цифр и три бомбы), во втором списке оказались две найденные бомбы.
Флагами отмечены 20 ячеек игрового поля, во второй список перенесены только элементы-бомбы.
Все бомбы отмечены флагами, условие победы выполнено.
Список материалов
Литература:
Т.О. Сундукова, Г.В. Ваныкина Структуры и алгоритмы компьютерной обработки данных
Бьерн Страуструп. Язык программирования С++
Джесс Либерти: Освой самостоятельно C++
http://www.vr-online.ru/content/s-dvusvjaznye-spiski-3085 - с++ , Двусвязные списки.
http://www.rsdn.ru/forum/src/2261478.1.aspx – с++, списки
http://comp-science.narod.ru/Progr/Dynamic.htm - динамические структуры данных, списки
Исходный проект находится по адресу
Листинг
#include "StdAfx.h"
#include "a2b2c2.h"
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <string>
using namespace std;
void list::Add_element(int str, int stb, int num, bool bomb)
{
element *new_element = new element;
if (head == NULL) //first elem
{
new_element->prev = new_element;
new_element->next = new_element;
head = new_element;
tail = new_element;
}
new_element->bomb = bomb;
new_element->num = num;
new_element->str = str;
new_element->stb = stb;
tail->next = new_element;//ссылка с предпоследнего
head->prev = new_element;//ссылка с первого
new_element->next = head;
new_element->prev = tail;
tail = new_element;
count_element++;
};
void list::Print_list()
{
element *new_element = head;
if (head == NULL)
cout << "Empty list\n";
else
{
cout << endl;
for (int i=0; i<count_element; i++)
{
if (new_element->bomb == true)
cout << "bomb " << ": [" << new_element->str << ";" << new_element->stb << "]\n";
//else
// cout << "box number " << new_element->num << ": [" << new_element->str << ";" << new_element->stb << "]\n";
new_element = new_element->next;
}
/*
cout << endl << "List <-:";
new_element = tail;
for (int i=0; i < count_element; i++)
{
cout << new_element->data + ' ';
new_element = new_element->prev;
}*/
}
};
void list::Del_element(int str, int stb, int level)
{
element *new_element = head;
{
for(int i=0; i<level; i++) //иначе, переходим до этого элемента
{
new_element = new_element->next;
if ((new_element->str==str) && (new_element->stb == stb))
break;
}
if (new_element == head) //если удаляем первый элемент
{
if (count_element == 1) //если этот элемент единственный
{
head = NULL;
tail = NULL;
}
else //если он первый, но не единственный
{
head = new_element->next;//head укаывает на второй
new_element->next = NULL;
new_element->prev = NULL;//удаляем ссылки удаляемого элемента
head->prev = tail;//второй->последний
tail->next = head;//последний->второй
}
cout << "\nbomb number"<<new_element->num<< ": [" << str<< ";"<<stb << "] is found ";
delete new_element;
count_element--;
return;
}
}
if (new_element == tail) //если удаляем последний элемент
{
tail = new_element->prev;
new_element->next = NULL;
new_element->prev = NULL;
tail->next = head;
head->prev = tail;
cout << "\nbomb number"<<new_element->num<< ": [" << str<< ";"<<stb << "] is found ";
delete new_element;
count_element--;
}
//если элемент находится в центре списка
if ((new_element != head) && (new_element != tail))
{
//new_element
new_element->prev->next = new_element->next; //предыдущий элемент указывает на следующий
new_element->next->prev = new_element->prev; //следующий указывает на предыдущий
cout << "\nbomb number"<<new_element->num<< ": [" << str<< ";"<<stb << "] is found ";
delete new_element;
count_element--;
return;
}
};
void list::Del_list()
{
if (head != NULL)
for (int i=0; i < count_element; i++)
{
element *new_element = head;
head = head->next;
new_element->next = NULL;
new_element->prev = NULL;
delete new_element;
}
count_element = 0;
head = NULL;
tail = NULL;
};
void KillBomb(int level)
{
bool fl=true;
for (int i=0; i<level; i++)
for (int j=0; j<level; j++)
if ((a[i][j]==20) && (b[i][j]==1))
{
new_element = bomb_list.head;
int ttl =0;
bool usf_elem = true;
while (usf_elem)
{
new_element = new_element->next;
ttl++;
if (((new_element->str == i) && (new_element->stb == j)) || (ttl>level*level+1))
usf_elem=false;
}
if (new_element == bomb_list.head)
if (bomb_list.count_element == 1)
bomb_list.head = NULL;
else
bomb_list.head = new_element->next;
if (new_element == bomb_list.tail)
if (bomb_list.count_element == 1)
bomb_list.tail = NULL;
else
bomb_list.tail = new_element->prev;
new_element->prev->next = new_element->next;//ссылка с предпоследнего на следующий
new_element->next->prev = new_element->prev;//со следующего на предыдущий
bomb_list.count_element--;
if(game_list.head == NULL)
{
game_list.head = new_element;
game_list.tail = new_element;
new_element->next = new_element;
new_element->prev = new_element;
}
else
{
game_list.tail->next = new_element;
new_element->prev = game_list.tail;
game_list.head->prev = new_element;
new_element->next = game_list.head;
game_list.tail = new_element;
}
game_list.count_element++;
}
cout <<"\nBombs left: ";
bomb_list.Print_list();
cout <<"\nBombs found: ";
game_list.Print_list();
bomb_list.Del_list();
game_list.Del_list();};