Я знаю, что никогда не поверят трем вещам: истинному, вероятному и логическому.
Логика — это чистая сущность написания кода. Хочу поделиться с вами небольшой историей. Это было одну или две недели назад, когда я сдавал экзамен по структурам данных и алгоритмам, и я был человеком, который плохо разбирался в указателях. Я не понял, как работает односвязный список. Прошло несколько недель после начала курса, и я ничего не знал о связном списке и узлах. И все же здесь я столкнулся с моей первой оцениваемой лабораторией в связанном списке, и речь шла о ротации связанного списка. Я пытался вывести логику для этого, но я просто не мог, я имел это в виду, но почему-то я просто не мог реализовать это в среде IDE. Я пытался нарисовать решение, а затем реализовать его, но безрезультатно. Я пытался спросить других, но они тоже были пусты и не могли придумать решение, поэтому я воспользовался помощью «Внешних источников». Вы знаете, что я имею в виду, чтобы пройти экзамен, и я сделал это. Но моя душа не была спокойна Как я не мог придумать решение Как я только что сжульничал в самом важном предмете семестра, и вот я снова на чертежной доске, выводя решение для ротации односвязного списка. На этот раз решение просто пришло мне в голову не потому, что я уже видел решение, оно было совершенно отличным от этого, и что я не совсем понял решение, которое я видел.
Решение, которое я хотел бы показать, — это то, которое я вывел из нулевой точки. Теперь вы можете увидеть какую-нибудь ошибку новичка, а может быть, вы ее не видите. Давайте начнем с создания нашего класса узла.
class node
{
private:
int data;//creating variable for data
node* next;//pointer for pointing to next Node
public:
node()//default constructor for node
{
data = 0;//intitalizing data variable to zero
next = NULL;//pointing to NULL
}
node(int data)//parameterized constructor for Node
{
this->data = data;//setting data to passed data
next = NULL;//POINTING TO NULL
}
node* getnext()//THE ADDRESS OF THE NEXT VARIABLE WHICH THE OBJECT IS STORING
{
return next;
}
void setnext(node* ptr)//SET the address for the next node
{
this->next = ptr;
}
void setdata(int data)//set data of the current node
{
this->data = data;
}
int getdata()//get data of the current Node
{
return data;
}
Что делает этот код, если вы не понимаете. Мы создаем узел класса. Теперь я хочу упомянуть, что вы можете увидеть много реализаций этого с использованием struct Online на многих платформах. Я сделал это с классом, потому что я нахожу это проще. Таким образом, код имеет 2 переменные, одна из которых имеет тип int для хранения данных, а другая является указателем класса Node Type, поэтому он может хранить адрес следующего узла в связанном списке. У него есть конструктор по умолчанию для инициализации переменных, на которые указатель указывает на null, потому что мы не можем заранее знать, на что мы будем указывать. Двигаясь дальше, мы создадим класс связанного списка.
class linkedlist
{
private:
node* head;//node type pointer object
public:
linkedlist()//default constructor for the linked list
{
head = NULL;//head is initialized with NULL;
}
void add(int data)//add data function
{
node* N = new node(data);//we create a new node
if (head == NULL)//if head is found equal to NULL
{
this->head = N;//The new node is equal to head.
}
else
{
node* temp = head;//we create a temp variable and set it to head.
while (temp->getnext() != NULL)//loop to reach end
{
temp = temp->getnext();//we keep moving node to the next node
}
temp->setnext(N);//we point the last node to the new node.
}
}
void display()//Display function.
{
node* temp = head;//we create a node type pointer and point it to head.
while (temp != NULL)//loop to reach end
{
cout << temp->getdata() << endl;//print data of the list
temp = temp->getnext();//moving node to next node
}
}
}
Класс Linked List имеет динамический объект типа Node с именем Head. у него есть функция Add, которая добавляет в список новый узел с нужным элементом. Если головы нет и она равна NULL, мы устанавливаем head=N. N здесь имя созданного NewNode. В противном случае мы идем в конец списка и указываем последний узел на Новый узел. Давайте теперь перейдем к функции поворота.
void rotate(int data)
{
int j = 0;//varible to track how much rotation we are performing
while (j < data) {
//while j is less than data. Data here is the number of rotation
int i = 0;//i is way of variable to have one pointer on the second last node.
node* temp = head;//node pointing to head that will go to end.
node* prev = head;//node that will go till second last node.
while (temp->getnext() != NULL)//iterating to the end of the Linked List.
{
if (i >= 1)//if i greater than or equal to one
{
prev = prev->getnext();//we move prev to the next node.
}
temp = temp->getnext();//we move temp to next node
i++;//i++ so we can get prev moving.
}
temp->setnext(head);//we point the last node to the head the first element.
head = temp;//we set head as temp.
prev->setnext(NULL);//and we set the next of second last node as NULL.
j++;//j++ to perfom the number of rotation.
}
}
Это виновник, о котором так долго говорили, что эти несколько строк кода заставили меня запаниковать. Теперь мы обсудим, как это работает. Мое решение было, если бы я мог как-то повернуть функцию списка, если бы я мог понять логику, чтобы сделать это один раз. Все, что мне нужно сделать, это повторить это необходимое количество раз. мы начинаем с целочисленной переменной J, и данные передаются как количество оборотов, которые необходимо сделать. теперь, пока j меньше, чем данные. Цикл будет повторяться. Внутри петли совсем другая история. мы инициализируем переменную I, чтобы мы могли управлять указателем типа узла prev.
Основная логика заключается в том, чтобы указатель temp итерировался до конца списка, а указатель Prev оставался на предпоследнем узле. После этого мы указываем последний узел, который является временным, на головной узел. Помните, что головной узел уже указывает на все остальные узлы впереди. Затем мы устанавливаем последний узел как головной. Теперь почему мы отслеживали предпоследний узел с prev? Это было потому, что нам нужно указать предпоследний узел рядом с NULL, потому что он указывал на temp.
Теперь два указателя temp и prev указывают на голову. Теперь, хотя temp getnext() не равен NULL, это означает, что temp next не указывает на NULL, мы продолжаем двигаться вперед. внутри, если Iне больше или равно 1, мы не перемещаем указатель prev вперед, но I перемещается вперед один раз, а i++ не стоит в конце, теперь I на один шаг вперед, и prev начался. Теперь я впереди, а предыдущий позади. теперь мы достигаем конца. Темп направлен на голову. Для заголовка задано значение temp, а значение prev равно NULL, а значение J увеличивается, что означает завершение одной итерации.
Первый шаг — это основной список. На втором изображении мы указываем последний элемент на голову. И на третьем изображении мы устанавливаем последний элемент как головной и устанавливаем предпоследний узел, который был предыдущим, равным NULL.
