2) Круговой связанный список

Преимущества кругового связного списка

Единственный связанный список как круговой связанный список

#include<stdio.h>
#include<stdlib.h>

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

struct node* addToEmpty(struct node*,int);
struct node *insertCurrent(struct node *, int);
struct node *insertAfter(struct node *, int, int);
struct node *removeAfter(struct node *, int);
struct node *removeCurrent(struct node *);

void peek(struct node *);

int main()
{
...

Объяснение кода:

1. Первые две строки кода являются необходимыми заголовочными файлами.
2. В следующем разделе описывается структура каждого самоссылающегося узла. Он содержит значение и указатель того же типа, что и структура.
3. Каждая структура неоднократно ссылается на объекты структуры одного типа.
4. Существуют разные прототипы функций для:
   1. Добавление элемента в пустой связанный список
   2. Вставка в текущей указанной позиции кругового связанного списка.
   3. Вставка после определенного индексированного значения в связанный список.
   4. Удаление / Удаление после определенного индексированного значения в связанном списке.
   5. Удаление в текущей указанной позиции кругового связанного списка
5. Последняя функция печатает каждый элемент посредством кругового обхода в любом состоянии связанного списка.

int main()
{
    struct node *last = NULL;
    last = insertCurrent(last,4);
    last = removeAfter(last, 4);
    peek(last);
    return 0;
}

struct node* addToEmpty(struct node*last, int data)
{
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp->item = data;
    last = temp;
    last->next = last;
    return last;
}
    
struct node *insertCurrent(struct node *last, int data)

Объяснение кода:

1. Для кода addEmpty выделите пустой узел с помощью функции malloc.
2. Для этого узла поместите данные в переменную temp.
3. Назначьте и свяжите единственную переменную с переменной temp
4. Вернуть последний элемент в контекст main () / application.

struct node *insertCurrent(struct node *last, int data)
{
    if(last == NULL)
    {
       return    addToEmpty(last, data);
    }
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp -> item = data;
    temp->next = last->next;
    last->next = temp;
    return last;
}
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
…

Объяснение кода

1. Если нет элемента для вставки, то вы должны обязательно добавить в пустой список и вернуть управление.
2. Создайте временный элемент для размещения после текущего элемента.
3. Свяжите указатели, как показано.
4. Вернуть последний указатель, как в предыдущей функции.

...
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
    if (last == NULL)
    {
       return addToEmpty(last, item);
    }
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );


    if(temp->item != data)
    {
       printf("Element not found. Please try again");
...

Объяснение кода:

1. Если в списке нет элемента, игнорируйте данные, добавьте текущий элемент в качестве последнего элемента в списке и верните элемент управления
2. Для каждой итерации в цикле do-while убедитесь, что есть предыдущий указатель, который содержит последний пройденный результат.
3. Только тогда может произойти следующий обход.
4. Если данные найдены, или температура достигает последнего указателя, выполнение завершается. Следующий раздел кода решает, что должно быть сделано с элементом.

...
    if(temp->item != data)
    {
       printf("Element not found. Please try again");
       return last;
    }
    else
    {
   	 newnode = (struct node *)malloc(sizeof(struct node));
             newnode->item = item;
             prev->next = newnode;
             newnode->next = temp;
    }
    return last;
}

struct node *removeCurrent(struct node *last)
...

Объяснение кода:

1. Если весь список был пройден, но элемент не найден, отобразите сообщение «элемент не найден», а затем верните управление вызывающей стороне.
2. Если найден узел, и / или узел еще не последний, то создайте новый узел.
3. Свяжите предыдущий узел с новым узлом. Свяжите текущий узел с temp (переменная обхода).
4. Это гарантирует, что элемент будет размещен после определенного узла в круговом связанном списке. Вернитесь к звонящему.

struct node *removeCurrent(struct node *last)
{
    if(last == NULL)
    {
        printf("Element Not Found");
        return NULL;
    }
    struct node *temp = last->next;
    last->next = temp->next;
    free(temp);
    return last;
}

struct node *removeAfter(struct node *last, int data)

Объяснение кода

1. Чтобы удалить только последний (текущий) узел, убедитесь, что этот список пуст. Если это так, то ни один элемент не может быть удален.
2. Переменная temp просто пересекает одну ссылку вперед.
3. Свяжите последний указатель с указателем после первого.
4. Освободите временный указатель. Он освобождает несвязанный последний указатель.

struct node *removeAfter(struct node *last,int data)
{
    struct node *temp = NULL,*prev = NULL;
    if (last == NULL)
    {
   	 printf("Linked list empty. Cannot remove any element\n");
   	 return NULL;
    }
    temp = last->next;
    prev = temp;
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
      printf("Element not found");
...

Объяснение кода

1. Как и в предыдущей функции удаления, проверьте, нет ли элемента. Если это правда, то ни один элемент не может быть удален.
2. Указателям назначаются определенные позиции для определения местоположения удаляемого элемента.
3. Указатели продвинуты, один за другим. (предыдущий темп)
4. Процесс продолжается до тех пор, пока элемент не будет найден или пока следующий элемент не вернется к последнему указателю.

    if(temp->item != data)
    {
        printf("Element not found");
        return last;
    }
    else
    {
        prev->next = temp->next;
        free(temp);
    }
    return last;
}

void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
   return;	

Объяснение программы

1. Если элемент найден после обхода всего связанного списка, отображается сообщение об ошибке, в котором говорится, что элемент не найден.
2. В противном случае элемент разделяется и освобождается на шагах 3 и 4.
3. Предыдущий указатель связан с адресом, указанным как «следующий» удаляемым элементом (temp).
4. Поэтому временный указатель освобождается и освобождается.

...
void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
         return;    
    }
    if(last -> next == last)
    {
        printf("%d-", temp->item);
    }
    while (temp != last)
    {
       printf("%d-", temp->item);
       temp = temp->next;
    }
}

Объяснение кода

1. Просмотр или обход невозможны, если нужны нули. Пользователь должен выделить или вставить узел.
2. Если есть только один узел, нет необходимости проходить через него, содержимое узла может быть напечатано, и цикл while не выполняется.
3. Если существует более одного узла, то temp печатает весь элемент до последнего элемента.
4. Момент времени достигается последний элемент, цикл завершается, и функция возвращает вызов основной функции.

Приложения Циркулярного связного списка