С++ для начинающих. Кольцевой Однонаправленный список, FIFO
По некоторым причинам у начинающих вопрос по кольцевым спискам возникает достаточно часто. Кольцевые списки также называют циклическими списками. Смысл в том, что у таких списков нет признака начала и нет признака конца. Они очень похожи на некольцевые однонаправленные линейные списки. В отличие от некольцевых списков, в которых есть признаки головы и хвоста, где в хвост записан адрес, ссылающийся вникуда, в циклических списках последний ссылается на начало списка, а не вникуда, и таким образом образуется замкнутый круг.
Так как в в циклическом списке ничто не ссылается вникуда, то признаком для обработки может быть счётчик элементов списка. В предыдущих статьях я, как правило, опускал создание счётчика, но тут он будет очень полезен.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
//Листинг #1 Кольцевой список FIFO Описываем две структуры: элемент списка и сам список #include <iostream.h> #include <stdlib.h> struct Node { int x; Node *Next; }; class List { Node *Head, *Tail; //Первый элемент и тот что последний int size; //Число элементов в списке public: List():Head(NULL),Tail(NULL),size(0){}; //Инициализация элементов в ноль с помощью конструктора }; int main() { system("CLS"); system("PAUSE"); return 0; } |
Начало положено. В отличие от предыдущих примеров, показанных на страницах моего сайта, в глаза может броситься название структуры Node. Но во-первых, так часто называют звенья списков (Node), а во-вторых, в многочисленных примерах можно встретить именно такое название первой структуры. Просто Element (из прошлых моих примеров стало Node). Называть-то можно как душе угодно, главное, чтобы и вам удобно было и другие могли прочитать то, что вы напишете.
Второе отличие в том, что появилась переменная size внутри класса List. Лично мне так оказалось вполне удобно в написании кода дальше. Предполагается подсчет элементов внутри списка.
Второе отличие в том, что появилась переменная size внутри класса List. Лично мне так оказалось вполне удобно в написании кода дальше. Предполагается подсчет элементов внутри списка.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
//Листинг #2 Кольцевой список FIFO Циклический Однонаправленный Добавление функции добавления элементов #include <iostream.h> #include <stdlib.h> struct Node { int x; Node *Next; }; class List { Node *Head, *Tail; //Первый элемент и тот что последний int size; //Число элементов в списке public: List():Head(NULL),Tail(NULL),size(0){}; //Инициализация элементов в ноль с помощью конструктора void Add(int x); //Функция добавления элемента в список }; void List::Add(int x) { size++; //При каждом добавлении элемента увеличиваем число элементов в списке Node *temp = new Node; //Выделение памяти для нового элемента списка temp->Next = Head; //Замыкание контура. Последний элемент - это начало списка temp->x = x; //Записываем в выделенную ячейку памяти значение x if (Head != NULL) //В том случае если список не пустой { Tail->Next = temp; //Запись данных в следующее за последним элементом поле Tail = temp; //Последний активный элемент=только что созданный. } else Head = Tail = temp; //Если список пуст то создается первый элемент. } int main() { system("CLS"); system("PAUSE"); return 0; } |
В листинге #2 была дописана функция добавления элементов в список. Стоит обратить внимание, что на этой стадии при каждом добавлении элемента в список будет постоянное увеличение размера списка (размера size, обозначающего количество элементов). Также стоит обратить внимание на то, что следующий элемент после добавленного — это начало списка, а не NULL. Таким образом получается как бы круг и без определённого признака из круга выйти не получится. Для того, чтобы выйти из круга после прохода по всем элементам, как раз и была создана переменная для подсчета элементов внутри списка. Во-первых, это достаточно понятно, во-вторых очень удобно. Cледующий шаг написания программы — это отображение списка на экране.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
//#Листинг #3 Однонаправленный список FIFO Кольцевой Добавление элементов и вывод списка на экран #include <iostream.h> #include <stdlib.h> struct Node { int x; Node *Next; }; class List { Node *Head, *Tail; //Первый элемент и тот что последний int size; //Число элементов в списке public: List():Head(NULL),Tail(NULL),size(0){}; //Инициализация элементов в ноль с помощью конструктора void Add(int x); void Show(int size); }; void List::Add(int x) { size++; //При каждом добавлении элемента увеличиваем число элементов в списке Node *temp = new Node; //Выделение памяти для нового элемента списка temp->Next = Head; //Замыкание контура. Последний элемент - это начало списка temp->x = x; //Записываем в выделенную ячейку памяти значение x if (Head != NULL) //В том случае если список не пустой { Tail->Next = temp; //Запись данных в следующее за последним элементом поле Tail = temp; //Последний активный элемент=только что созданный. } else Head = Tail = temp; //Если список пуст то создается первый элемент. } void List::Show(int size) { Node *tempHead = Head; //Указываем на голову int temp = size; //Временная переменная равная числу элементов в списке while (temp != 0) //Пока не выполнен признак прохода по всему списку { cout << tempHead->x << " "; //Очередной элемент списка на экран tempHead = tempHead->Next; //Указываем, что нужен следующий элемент temp--; //Один элемент считан, значит осталось на один меньше } } int main() { system("CLS"); system("PAUSE"); return 0; } |
В листинг #3 была создана переменная, которая приравнивается к числу элементов внутри списка. Сами эти элементы считаются при каждом новом добавлении элемента в список (см. листинг #2). Переменную, обозначающую число элементов в списке, лучше не трогать, поэтому обработка ведётся с помощью дополнительной переменной. Ведь может понадобится новая обработка этого списка и размер какой был, таким и должен оставаться (или изменяться только при добавлении/удалении, но не отображении списка на экране).
Обращаю внимание, что в функцию отображения передаётся аргумент, обозначающий количество элементов, помещённых в список. Список ведь кольцевой, и если знать сколько в нём элементов, то будет проще его обработать.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
//Листинг #4 Список FIFO, кольцевой Запись элементов #include <iostream.h> #include <stdlib.h> struct Node { int x; Node *Next; }; class List { Node *Head, *Tail; //Первый элемент и последний int size; //Число элементов в списке public: List():Head(NULL),Tail(NULL),size(0){}; //Инициализация элементов в ноль с помощью конструктора void Add(int x); void Show(int size); }; void List::Add(int x) { size++; //При каждом добавлении элемента увеличиваем число элементов в списке Node *temp= new Node; //Выделение памяти для нового элемента списка temp->Next = Head; //Замыкание контура. Последний элемент - это начало списка temp->x = x; //Записываем в выделенную ячейку памяти значение x if (Head != NULL) //В том случае если список не пустой { Tail->Next = temp; //Запись данных в следующее за последним элементом поле Tail = temp; //Последний активный элемент=только что созданный. } else Head = Tail = temp; //Если список пуст то создается первый элемент. } void List::Show(int size) { Node *tempHead = Head; //Указываем на голову int temp = size; //Временная переменная равная числу элементов в списке while (temp != 0) //Пока не выполнен признак прохода по всему списку { cout << tempHead->x << " "; //Очередной элемент списка на экран tempHead = tempHead->Next; //Указываем, что нужен следующий элемент temp--; //Один элемент считан, значит осталось на один меньше } } int main() { system("CLS"); List lst; //lst - Переменная тип которой список lst.Add(100); //Записали 100 в список lst.Add(200); //Записали 200 в список lst.Add(300); //Записали 300 в список system("PAUSE"); return 0; } |
Изменилось то, что внутри функии main(). И вот тут у кого-то может возникнуть вопрос по отображению списка на экране. Кто всё понял, тот молодчик, но кому нужно помочь объясняю. Вспоминаем, что внутри списка при каждом новом добавлении элемента счётчик числа элементов увеличивается. Но сам по себе счётчик объявлен внутри класса и в защищённой секции, в private. Доступ к этому счётчику разрешён только изнутри класса, а вне класса доступ закрыт. Чтобы этот счётчик не был бесполезен, нужно создать новую функцию класса, которая и будет возвращать значение этого счётчика.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
//Листинг #5 Список FIFO, кольцевой Добавляем функцию для вывода значения счётчика элементов #include <iostream.h> #include <stdlib.h> struct Node { int x; Node *Next; }; class List { Node *Head, *Tail; //Первый элемент и тот что последний int size; //Число элементов в списке public: List():Head(NULL),Tail(NULL),size(0){}; //Инициализация элементов в ноль с помощью конструктора void Add(int x); //Функция добавления элементов в списов void Show(int size); //Функция отображения элементов списка int Count(); //Функция возвращающая число элементов в списке }; int List::Count() { return size; //Возвращаем число элементов списка } void List::Add(int x) { size++; //При каждом добавлении элемента увеличиваем число элементов в списке Node *temp = new Node; //Выделение памяти для нового элемента списка temp->Next = Head; //Замыкание контура. Последний элемент - это начало списка temp->x = x; //Записываем в выделенную ячейку памяти значение x if (Head != NULL) //В том случае если список не пустой { Tail->Next = temp; //Запись данных в следующее за последним элементом поле Tail = temp; //Последний активный элемент=только что созданный. } else Head = Tail = temp; //Если список пуст то создается первый элемент. } void List::Show(int temp) { Node *tempHead = Head; //Указываем на голову temp = size; //Временная переменная равная числу элементов в списке while (temp != 0) //Пока не выполнен признак прохода по всему списку { cout << tempHead->x << " "; //Очередной элемент списка на экран tempHead = tempHead->Next; //Указываем, что нужен следующий элемент temp--; //Один элемент считан, значит осталось на один меньше } } int main() { system("CLS"); List lst; lst.Add(100); lst.Add(200); lst.Add(300); lst.Show(lst.Count()); //Показываем список на экране. system("PAUSE"); return 0; } |
Вроде бы всё. Но нет. Ни в коем случае не всё. При динамическом программировании если была выделена память, то выделенную память надо освобождать, чтобы не допустить утечки памяти. Освобождение памяти очень удобно описать в деструкторе. Реализация этой чати кода очень похожа на реализацию в функцию отображения списка.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
//#Листинг #6 Кольцевой список FIFO Добавляем деструктор, в котором описываем высвобождение памяти #include <iostream.h> #include <stdlib.h> struct Node { int x; Node *Next; }; class List { Node *Head, *Tail; //Первый элемент и тот что последний int size; //Число элементов в списке public: List():Head(NULL),Tail(NULL),size(0){}; //Инициализация элементов в ноль с помощью конструктора ~List(); //Прототип деструктор: в деструкторе освободим память void Add(int x); //Прототип функции добавления элементов в списов void Show(int size); //Прототип функции отображения элементов списка int Count(); //Прототип функции возвращающей число элементов в списке }; List::~List() { while (size != 0) //Пока размерность списка не станет нулевой { Node *temp = Head->Next; delete Head; //Освобождаем память от активного элемента Head = temp; //Смена адреса начала на адрес следующего элемента size--; //Один элемент освобожден. корректируем число элементов } } int List::Count() { return size; //Возвращаем число элементов списка } void List::Add(int x) { size++; //При каждом добавлении элемента увеличиваем число элементов в списке Node *temp = new Node; //Выделение памяти для нового элемента списка temp->Next = Head; //Замыкание контура. Последний элемент - это начало списка temp->x = x; //Записываем в выделенную ячейку памяти значение x if (Head != NULL) //В том случае если список не пустой { Tail->Next = temp; //Запись данных в следующее за последним элементом поле Tail = temp; //Последний активный элемент=только что созданный. } else Head = Tail = temp; //Если список пуст то создается первый элемент. } void List::Show(int temp) { Node *tempHead = Head; //Указываем на голову temp = size; //Временная переменная равная числу элементов в списке while (temp != 0) //Пока не выполнен признак прохода по всему списку { cout << tempHead->x << " "; //Очередной элемент списка на экран tempHead = tempHead->Next; //Указываем, что нужен следующий элемент temp--; //Один элемент считан, значит осталось на один меньше } } int main() { system("CLS"); List lst; lst.Add(100); lst.Add(200); lst.Add(300); lst.Show(lst.Count()); //Показываем список на экране. cout << endl; system("PAUSE"); return 0; } |
Вот такое вот знакомство с кольцевым однонаправленным списком. Конечно, здесь есть некоторые отличия от предыдущих статей, описанных на сайте, по спискам, но сам принцип изучения однонаправленных списков базируется на этих примерах. Даже если и объяснил не идеально и где-то неправильно, я уверен, что даже попытка изложить материал в настолько подробном виде способна многим помочь и сэкономить время. Ведь поймешь принцип, сможешь хоть что-то. Использовать легко, но понять и оттолкнутся тяжеловато (наверное, не всем, но, думаю, многим). Успехов в изучении!
15 комментариев на «“С++ для начинающих. Кольцевой Однонаправленный список, FIFO”»
Добавить комментарий
Случайная книга в электронном формате
1. Утечка памяти
void List::Show(int temp)
{
Node *tempHead= Head;//Саму голову трогать не надо
//вместо
///Node *tempHead=new Node;
//// tempHead=Head; //Саму голову трогать не надо
2. Не понял смысла в функции Show(int), передаваемый параметр затирается количеством в списке. Так лучше не делать. Объяснять не буду, но минусы стиль, путаница для другого программиста, быстродействие.
temp=size; //Временная переменная равная числу элементов в списке
Лучше сделать так
void List::Show(void)
{
int temp=size;
1 пункт исправил.
2 пункт я поясню.
тут не имеет значения то, что переменная затирается. Так как в момент вызова функции вовнутрь функции передается параметр, а сама функция принимает этот параметр как обычную переменную (не как указатель или ссылку), то внутри функции создается локальная копия переменной, что является аналогом того, что вы в пункте 2 написали. В любом случае переменная вне функции, которую мы отдаем вовнутрь функции работой функции не измениться.
а как добавить в кольцевой односвязный список фиктивный элемент, выполняющий роль барьера, между началом и концом списка?
я сейчас не могу ответить на этот вопрос. 🙁
Можно удаление пробовать вот так
Item* List::deleteAfter(Item* sought_item) {
Item* tmp = sought_item->Next;
sought_item->Next = tmp->Next;
if(tmp == Head)
Head = sought_item->Next;
if(tmp == Tail)
Tail = sought_item->Next;
delete tmp;
size—;
return sought_item->Next;
}
спасибо. я позднее посмотрю.
это неправильно.
Здравствуйте, хотела спросить, а удаление и поиск нужного элемента как производиться, у меня с этим проблемы.
и вам я сейчас ответить не смогу.
я сам не особо в них разбираюсь.
Помогите пожалуйста
Во всех вариантах необходимо организовать список, состоящий из 10 элементов вводимых с клавиатуры, через функцию вставки первого элемента в список. Организовать функцию просмотра всего списка элементов. Организовать функцию очистки списка. Остальные функции реализовать в соответствии с вариантом.
17. Организовать однонаправленный линейный список с функцией вывода на экран элементов больших первого элемента.
2 пункт я поясню.
тут не имеет значения то, что переменная затирается. Так как в момент вызова функции вовнутрь функции передается параметр, а сама функция принимает этот параметр как обычную переменную (не как указатель или ссылку), то внутри функции создается локальная копия переменной, что является аналогом того, что вы в пункте 2 написали. В любом случае переменная вне функции, которую мы отдаем вовнутрь функции работой функции не изменитьс
Это Ваш ответ от 29.08.2013 в 5:28 пп
Но все равно можно ведь и сократить код, убрав метод Count (), просто создать локальную переменную в Show и все….
Переписал полностью по FIFO http://ci-plus-plus-snachala.ru/?p=58
сделал проще.
А как удалить любой элемент из списка?
А как удалить любой элемент из списка?
И каким боком здесь АДА? Не хорошо так.