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

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

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

Схема, показанная ниже, предназначена для односвязного списка:

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

Такая схема представлена ниже:

Объявление

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

struct node
 {
 int data;
 struct node *next;
 };

struct node

{

int data;

struct node *next;

};

Для реализации циклического связного списка мы поддерживаем внешний указатель “last”, который указывает на последний узел в циклическом связном списке. Следовательно, last->next будет указывать на первый узел в связном списке.

Делая так, мы гарантируем, что при вставке нового узла в начале или в конце списка нам не нужно будет проходить весь список. Это связано с тем, что last указывает на последний узел, а last->next указывает на первый узел.

Это было бы невозможно, если бы мы указали внешний указатель на первый узел.

Основные операции

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

Вставка

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

Читать также: Инструкция по выбору (CASE-of-ELSE) в языке Паскаль

1) Вставка в пустой список

Когда в циклическом списке нет узлов, а список пуст, а последний указатель равен null, тогда мы вставляем новый узел N, указывая последний указатель на узел N, как показано выше. Следующий указатель N будет указывать на сам узел N, поскольку существует только один узел. Таким образом, N становится первым и последним узлом в списке.

2) Вставка в начало списка

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

N-> следующий = последний-> следующий

Последний-> следующий = N

3) Вставка в конец списка

Чтобы вставить новый узел в конец списка, выполните следующие действия:

N-> следующий = последний -> следующий;
последний -> следующий = N
последний = N

4) Вставка между списком

Предположим, нам нужно вставить новый узел N между N3 и N4, сначала нам нужно пройти по списку и найти узел, после которого должен быть вставлен новый узел, в данном случае его N3.

После того, как узел найден, мы выполняем следующие шаги:

N -> следующий = N3 -> Следующий;
N3 -> Следующий = N

Такая операция вставляет новый узел N после N3.

Удаление

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

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

Читать также: Обработка переменных в языке программирования Паскаль

Графическое представление операции удаления показано ниже:

Обход

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

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

Теперь мы представим реализацию операций с циклическим связным списком с использованием C ++ и Java. Здесь мы реализовали операции вставки, удаления и обхода. Для ясного понимания мы изобразили циклический связанный список как

Таким образом, к последнему узлу 50 мы снова присоединяем узел 10, который является первым узлом, тем самым указывая его как кольцевой связный список.

Программа на C++:

#include<iostream>
using namespace std;
  
struct Node
{
   int data;
   struct Node *next;
};
//вставьте новый узел в пустой список
struct Node *insertInEmpty(struct Node *last, int new_data)
{
   // если last не равен null, то список не пуст, поэтому вернитесь
   if (last != NULL)
   return last;
  
   // выделите память для узла
   struct Node *temp = new Node;
  
   // Назначьте данные
   temp -> data = new_data;
   last = temp;
  
   // Создайте указатель
   last->next = last;
  
   return last;
}
//вставьте новый узел в начало списка
struct Node *insertAtBegin(struct Node *last, int new_data)
{
   //если список пуст, добавьте узел, вызвав insertInEmpty
   if (last == NULL)
   return insertInEmpty(last, new_data);
  
   //в противном случае создайте новый узел
   struct Node *temp = new Node;
  
   //задайте новые данные для узла
   temp -> data = new_data;
   temp -> next = last -> next;
   last -> next = temp;
  
   return last;
}
//вставьте новый узел в конец списка
struct Node *insertAtEnd(struct Node *last, int new_data)
{
   //если список пуст, добавьте узел, вызвав insertInEmpty
   if (last == NULL)
   return insertInEmpty(last, new_data);
  
   //в противном случае создайте новый узел
   struct Node *temp = new Node;
  
   //назначить данные новому узлу
   temp -> data = new_data;
   temp -> next = last -> next;
   last -> next = temp;
   last = temp;
  
   return last;
}
  
//вставьте новый узел между узлами
struct Node *insertAfter(struct Node *last, int new_data, int after_item)
{
   //возвращает значение null, если список пуст
   if (last == NULL)
   return NULL;
  
   struct Node *temp, *p;
   p = last -> next;
   do
   {
      if (p ->data == after_item)
      {
         temp = new Node;
         temp -> data = new_data;
         temp -> next = p -> next;
         p -> next = temp;
        
         if (p == last)
         last = temp;
         return last;
       }
   p = p -> next;
 } while(p != last -> next);
  
   cout << "The node with data "<<after_item << " is not present in the list." << endl;
   return last;
  
}
//пройдите по циклическому связанному списку
void traverseList(struct Node *last) {
   struct Node *p;
  
   // Если список пуст, вернитесь
   if (last == NULL) {
      cout << "Circular linked List is empty." << endl;
      return;
      }
p = last -> next; // Укажите на первый узел в списке
  
// Просматривайте список, начиная с первого узла, пока первый узел не будет посещен снова
  
do {
      cout << p -> data << "==>";
      p = p -> next;
      } while(p != last->next);
   if(p == last->next)
   cout<<p->data;
   cout<<"\n\n";
   }
  
//удалите узел из списка
void deleteNode(Node** head, int key)
{
   // Если связный список пуст, повторите настройку
   if (*head == NULL)
   return;
  
   // Если список содержит только один узел, удалите этот узел; список пуст
   if((*head)->data==key && (*head)->next==*head) {
      free(*head);
      *head=NULL;
      }
Node *last=*head,*d;
  
// Если ключ - это head
if((*head)->data==key) {
   while(last->next!=*head) // Найдите последний узел в списке
   last=last->next;
  
   // укажите последний узел на следующий за head или вторым узлом списка
   last->next=(*head)->next;
   free(*head);
   *head=last->next;
   }
  
// достигнут конец списка или узел, подлежащий удалению, отсутствует в списке
while(last->next!=*head&&last->next->data!=key) {
   last=last->next;
}
// узел, подлежащий удалению, найден, поэтому освободить память и отобразить список
if(last->next->data==key) {
      d=last->next;
      last->next=d->next;
      cout<<"The node with data "<<key<<" deleted from the list"<<endl;
      free(d);
      cout<<endl;
      cout<<"Circular linked list after deleting "<<key<<" is as follows:"<<endl;
      traverseList(last);
      }
   else
   cout<<"The node with data "<< key << " not found in the list"<<endl;
   }
  
// основная программа
int main()
{
   struct Node *last = NULL;
  
   last = insertInEmpty(last, 30);
   last = insertAtBegin(last, 20);
   last = insertAtBegin(last, 10);
   last = insertAtEnd(last, 40);
   last = insertAtEnd(last, 60);
   last = insertAfter(last, 50,40 );
   cout<<"The circular linked list created is as follows:"<<endl;
   traverseList(last);
   deleteNode(&last,10);
   return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

#include<iostream>

using namespace std;

struct Node

{

int data;

struct Node *next;

};

//вставьте новый узел в пустой список

struct Node *insertInEmpty(struct Node *last, int new_data)

{

// если last не равен null, то список не пуст, поэтому вернитесь

if (last != NULL)

return last;

// выделите память для узла

struct Node *temp = new Node;

// Назначьте данные

temp -> data = new_data;

last = temp;

// Создайте указатель

last->next = last;

return last;

}

//вставьте новый узел в начало списка

struct Node *insertAtBegin(struct Node *last, int new_data)

{

//если список пуст, добавьте узел, вызвав insertInEmpty

if (last == NULL)

return insertInEmpty(last, new_data);

//в противном случае создайте новый узел

struct Node *temp = new Node;

//задайте новые данные для узла

temp -> data = new_data;

temp -> next = last -> next;

last -> next = temp;

return last;

}

//вставьте новый узел в конец списка

struct Node *insertAtEnd(struct Node *last, int new_data)

{

//если список пуст, добавьте узел, вызвав insertInEmpty

if (last == NULL)

return insertInEmpty(last, new_data);

//в противном случае создайте новый узел

struct Node *temp = new Node;

//назначить данные новому узлу

temp -> data = new_data;

temp -> next = last -> next;

last -> next = temp;

last = temp;

return last;

}

//вставьте новый узел между узлами

struct Node *insertAfter(struct Node *last, int new_data, int after_item)

{

//возвращает значение null, если список пуст

if (last == NULL)

return NULL;

struct Node *temp, *p;

p = last -> next;

{

if (p ->data == after_item)

{

temp = new Node;

temp -> data = new_data;

temp -> next = p -> next;

p -> next = temp;

if (p == last)

last = temp;

return last;

}

p = p -> next;

} while(p != last -> next);

cout << "The node with data "<<after_item << " is not present in the list." << endl;

return last;

}

//пройдите по циклическому связанному списку

void traverseList(struct Node *last) {

struct Node *p;

// Если список пуст, вернитесь

if (last == NULL) {

cout << "Circular linked List is empty." << endl;

return;

}

p = last -> next; // Укажите на первый узел в списке

// Просматривайте список, начиная с первого узла, пока первый узел не будет посещен снова

do {

cout << p -> data << "==>";

p = p -> next;

} while(p != last->next);

if(p == last->next)

cout<<p->data;

cout<<"\n\n";

}

//удалите узел из списка

void deleteNode(Node** head, int key)

{

// Если связный список пуст, повторите настройку

if (*head == NULL)

return;

// Если список содержит только один узел, удалите этот узел; список пуст

if((*head)->data==key && (*head)->next==*head) {

free(*head);

*head=NULL;

}

Node *last=*head,*d;

// Если ключ - это head

if((*head)->data==key) {

while(last->next!=*head) // Найдите последний узел в списке

last=last->next;

// укажите последний узел на следующий за head или вторым узлом списка

last->next=(*head)->next;

free(*head);

*head=last->next;

}

// достигнут конец списка или узел, подлежащий удалению, отсутствует в списке

while(last->next!=*head&&last->next->data!=key) {

last=last->next;

}

// узел, подлежащий удалению, найден, поэтому освободить память и отобразить список

if(last->next->data==key) {

d=last->next;

last->next=d->next;

cout<<"The node with data "<<key<<" deleted from the list"<<endl;

free(d);

cout<<endl;

cout<<"Circular linked list after deleting "<<key<<" is as follows:"<<endl;

traverseList(last);

}

else

cout<<"The node with data "<< key << " not found in the list"<<endl;

}

// основная программа

int main()

{

struct Node *last = NULL;

last = insertInEmpty(last, 30);

last = insertAtBegin(last, 20);

last = insertAtBegin(last, 10);

last = insertAtEnd(last, 40);

last = insertAtEnd(last, 60);

last = insertAfter(last, 50,40 );

cout<<"The circular linked list created is as follows:"<<endl;

traverseList(last);

deleteNode(&last,10);

return 0;

}

Вывод данных:

Созданный циклический связный список выглядит следующим образом:
10==>20==>30==>40==>50==>60==>10
Узел с данными 10 удаляется из списка
Кольцевой связный список после удаления 10 выглядит следующим образом:
20==>30==>40==>50==>60==>20

Программа на Java для операций с циклическим связным списком:

//Класс Java для демонстрации операций с циклическими связными списками
class Main
{
   static class Node {
      int data;
      Node next;
   };
//вставьте новый узел в пустой список
static Node insertInEmpty(Node last, int new_data)
{
   // если список не пуст, вернитесь
   if (last != null)
   return last;
  
   Node temp = new Node(); // создайте новый узел
  
   temp.data = new_data; // назначить данные новому узлу
   last = temp;
  
   last.next = last; // Создайте указатель
  
   return last;
   }
//вставьте новый узел в начало списка
static Node insertAtBegin(Node last, int new_data)
   {
      //если список равен null, то верните и вызовите функцию, чтобы вставить узел в пустой список
      if (last == null)
      return insertInEmpty(last, new_data);
  
      //создайте новый узел
      Node temp = new Node();
      //задайте данные для узла
      temp.data = new_data;
      temp.next = last.next;
      last.next = temp;
  
      return last;
   }
//вставьте новый узел в конец списка
static Node insertAtEnd(Node last, int new_data)
{
   //если список равен null, то вернитесь и вызовите функцию, чтобы вставить узел в пустой список
   if (last == null)
   return insertInEmpty(last, new_data);
   //создайте новый узел
   Node temp = new Node();
  
   temp.data = new_data;
   temp.next = last.next;
   last.next = temp;
   last = temp;
  
   return last;
   }
//вставить узел между узлами в списке
static Node addAfter(Node last, int new_data, int after_item)
   {
      //если список равен null, вернитесь
      if (last == null)
      return null;
  
      Node temp, p;
     p = last.next;
     do
     {
       if (p.data == after_item)
      {
         temp = new Node();
         temp.data = new_data;
         temp.next = p.next;
         p.next = temp;
     
         if (p == last)
         last = temp;
         return last;
         }
p = p.next;
   { while(p != last.next);
    
   System.out.println("The node with data " + after_item + " not present in the list.");
   return last;
  
   }
//пройдите по циклическому связному списку
static void traverse(Node last)
{
   Node p;
  
   // Если список пуст, вернитесь
   if (last == null) {
       System.out.println("Cicular linked List is empty.");
       return;
      }
  
p = last.next; // Укажите на первый узел списка
  
// Перемещение по списку
do{
      System.out.print(p.data + "==>");
      p = p.next;
      }
   while(p != last.next);
   if(p == last.next)
   System.out.print(p.data);
   System.out.print("\n\n");
   }
//удаление узла из списка
static Node deleteNode(Node head, int key) {
   //если список равен null, вернитесь
   if (head == null)
   return null;
  
   // Найдите необходимый узел, который должен быть удален
   Node curr = head, prev = new Node();
   while (curr.data != key) {
      if (curr.next == head) {
         System.out.printf("\nGiven node " + key + " is not found" + “in the list!");
           break;
         }
      prev = curr;
      curr = curr.next;
      }
// Проверьте, является ли узел только узлом
if (curr.next == head) {
   head = null;
   return head;
   }
// Если более одного узла, проверьте, является ли он первым узлом
if (curr == head) {
   prev = head;
   while (prev.next != head)
   prev = prev.next;
   head = curr.next;
   prev.next = head;
   }
  
// проверьте, является ли узел последним узлом
else if (curr.next == head) {
   prev.next = head;
   }
else {
    prev.next = curr.next;
    }
  
System.out.println("After deleting " + key + " the circular list is:");
traverse(head);
return head;
    }
// Основной код
public static void main(String[] args){
   Node last = null;
  
   last = insertInEmpty(last, 30);
   last = insertAtBegin(last, 20);
   last = insertAtBegin(last, 10);
   last = insertAtEnd(last, 40);
   last = insertAtEnd(last, 60);
   last = addAfter(last, 50, 40);
  
   System.out.println("Circular linked list created is:");
   traverse(last);
   last = deleteNode(last,40);
   }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

//Класс Java для демонстрации операций с циклическими связными списками

class Main

{

static class Node {

int data;

Node next;

};

//вставьте новый узел в пустой список

static Node insertInEmpty(Node last, int new_data)

{

// если список не пуст, вернитесь

if (last != null)

return last;

Node temp = new Node(); // создайте новый узел

temp.data = new_data; // назначить данные новому узлу

last = temp;

last.next = last; // Создайте указатель

return last;

}

//вставьте новый узел в начало списка

static Node insertAtBegin(Node last, int new_data)

{

//если список равен null, то верните и вызовите функцию, чтобы вставить узел в пустой список

if (last == null)

return insertInEmpty(last, new_data);

//создайте новый узел

Node temp = new Node();

//задайте данные для узла

temp.data = new_data;

temp.next = last.next;

last.next = temp;

return last;

}

//вставьте новый узел в конец списка

static Node insertAtEnd(Node last, int new_data)

{

//если список равен null, то вернитесь и вызовите функцию, чтобы вставить узел в пустой список

if (last == null)

return insertInEmpty(last, new_data);

//создайте новый узел

Node temp = new Node();

temp.data = new_data;

temp.next = last.next;

last.next = temp;

last = temp;

return last;

}

//вставить узел между узлами в списке

static Node addAfter(Node last, int new_data, int after_item)

{

//если список равен null, вернитесь

if (last == null)

return null;

Node temp, p;

p = last.next;

{

if (p.data == after_item)

{

temp = new Node();

temp.data = new_data;

temp.next = p.next;

p.next = temp;

if (p == last)

last = temp;

return last;

}

p = p.next;

{ while(p != last.next);

System.out.println("The node with data " + after_item + " not present in the list.");

return last;

}

//пройдите по циклическому связному списку

static void traverse(Node last)

{

Node p;

// Если список пуст, вернитесь

if (last == null) {

System.out.println("Cicular linked List is empty.");

return;

}

p = last.next; // Укажите на первый узел списка

// Перемещение по списку

do{

System.out.print(p.data + "==>");

p = p.next;

}

while(p != last.next);

if(p == last.next)

System.out.print(p.data);

System.out.print("\n\n");

}

//удаление узла из списка

static Node deleteNode(Node head, int key) {

//если список равен null, вернитесь

if (head == null)

return null;

// Найдите необходимый узел, который должен быть удален

Node curr = head, prev = new Node();

while (curr.data != key) {

if (curr.next == head) {

System.out.printf("\nGiven node " + key + " is not found" + “in the list!");

break;

}

prev = curr;

curr = curr.next;

}

// Проверьте, является ли узел только узлом

if (curr.next == head) {

head = null;

return head;

}

// Если более одного узла, проверьте, является ли он первым узлом

if (curr == head) {

prev = head;

while (prev.next != head)

prev = prev.next;

head = curr.next;

prev.next = head;

}

// проверьте, является ли узел последним узлом

else if (curr.next == head) {

prev.next = head;

}

else {

prev.next = curr.next;

}

System.out.println("After deleting " + key + " the circular list is:");

traverse(head);

return head;

}

// Основной код

public static void main(String[] args){

Node last = null;

last = insertInEmpty(last, 30);

last = insertAtBegin(last, 20);

last = insertAtBegin(last, 10);

last = insertAtEnd(last, 40);

last = insertAtEnd(last, 60);

last = addAfter(last, 50, 40);

System.out.println("Circular linked list created is:");

traverse(last);

last = deleteNode(last,40);

}

Вывод данных:

Созданный кольцевой связный список:
10==>20==>30==>40==>50==>60==>10
После удаления 40 кольцевой список будет:
10==>20==>30==>50==>60==>10

Преимущества и недостатки

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

Преимущества:

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

Недостатки:

Изменение кольцевого связного списка является сложным.
Поскольку узлы соединены, образуя кольцо (круг), нет надлежащей маркировки для начала или конца списка. Следовательно, трудно найти конец списка или элемент управления циклом. Если не позаботиться об этом, реализация может оказаться в бесконечном цикле.
Мы не можем вернуться к предыдущему узлу за один шаг. Мы должны сначала просмотреть весь список.

Читать также: Реляционные операторы в языке программирования Паскаль

Применения циклического связного списка

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

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

Итог

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

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

Циклические связные списки поддерживают различные операции, такие как вставка, удаление и обход.

В нашей следующей статье вы узнаете о структуре данных стека в С++.

С Уважением, МониторБанк

Объявление

Основные операции

Вставка

1) Вставка в пустой список

2) Вставка в начало списка

3) Вставка в конец списка

4) Вставка между списком

Удаление

Обход

Преимущества и недостатки

Применения циклического связного списка

Итог

Вам также может понравиться

Сортировка вставками в C++

Типы данных С++

Секреты профессионального программирования

Добавить комментарий Отменить ответ