Односвязный циклический список

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

Каждый узел однонаправленного (односвязного) циклического списка (ОЦС) содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит адрес корневого элемента.
Односвязный циклический список

Узел ОЦС можно представить в виде структуры, аналогичной односвязному линейному списку

struct list {
  int field; // поле данных
  struct list *ptr; // указатель на следующий элемент
};

Основные действия, производимые над элементами ОЦС:

  • Инициализация списка
  • Добавление узла в список
  • Удаление узла из списка
  • Вывод элементов списка
  • Взаимообмен двух узлов списка

Поскольку список является циклическим, реализация отдельной функции для удаления корня списка не требуется.

Инициализация ОЦС

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

struct list * init(int a) {// а- значение первого узла
  struct list *lst;
  // выделение памяти под корень списка
  lst = (struct list*)malloc(sizeof(struct list));
  lst->field = a;
  lst->ptr = lst; // указатель на сам корневой узел
  return(lst);
}
Добавление узла в ОЦС

Функция добавления узла в список принимает два аргумента:

  • Указатель на элемент, после которого происходит добавление
  • Данные для добавляемого элемента.

Процедуру добавления элемента можно отобразить следующей схемой:
Добавление элемента ОЦС
Добавление элемента в ОЦС включает в себя следующие этапы:

  • создание добавляемого узла и заполнение его поля данных;
  • переустановка указателя узла, предшествующего добавляемому, на добавляемый узел;
  • установка указателя добавляемого узла на следующий узел (тот, на который указывал предшествующий узел).

Таким образом, функция добавления узла в ОЦС имеет вид, полностью аналогичный функции добавления узла в односвязный линейный список:

struct list * addelem(list *lst, int number) {
  struct list *temp, *p;
  temp = (struct list*)malloc(sizeof(list));
  p = lst->ptr; // сохранение указателя на следующий элемент
  lst->ptr = temp; // предыдущий узел указывает на создаваемый
  temp->field = number; // сохранение поля данных добавляемого узла
  temp->ptr = p; // созданный узел указывает на следующий элемент
  return(temp);
}

Возвращаемым значением функции является адрес добавленного узла.

Удаление узла ОЦС

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

Функция возвращает указатель на узел, следующий за удаляемым.

Удаление узла может быть представлено следующей схемой:
Удаление элемента ОЦС
Удаление узла ОЦС включает в себя следующие этапы:

  • установка указателя предыдущего узла на узел, следующий за удаляемым;
  • освобождение памяти удаляемого узла.
struct list * deletelem(list *lst) {
  struct list *temp;
  temp = lst;
  while(temp->ptr!=lst) // просматриваем список начиная с корня
  { // пока не найдем узел, предшествующий lst
    temp = temp->ptr;
  }
  temp->ptr = lst->ptr; // переставляем указатель
  free(lst); // освобождаем память удаляемого узла
  return(temp);
}
Вывод элементов ОЦС

Функция вывода элементов ОЦС аналогична функции для ОЛС за исключением условия окончания обхода элементов.
В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.

void listprint(list *lst) {
  struct list *p;
  p = lst;
  do {
    printf("%d ",p->field); // вывод значения узла p
    p = p->ptr; // переход к следующему узлу
  }while(p != lst); // условие окончания обхода
}

Для ОЦС также можно вызвать функцию вывода элементов списка начиная с любого узла.

Взаимообмен узлов ОЦС

В качестве аргументов функция взаимообмена ОЦС принимает два указателя за обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого узла списка.

Взаимообмен узлов списка осуществляется путем переустановки указателей. Для этого необходимо определить предшествующий и последующий узлы для каждого заменяемого. При этом возможны две ситуации:

  • заменяемые узлы являются соседями;
  • заменяемые узлы не являются соседями, то есть между ними имеется хотя бы один элемент.

При замене соседних узлов переустановка указателей выглядит следующим образом:
Взаимообмен элементов ОЦС
При замене узлов, не являющихся соседними переустановка указателей выглядит следующим образом:
Взаимообмен элементов ОЦС

При переустановке указателей необходимость в проверке корневого узла отсутствует (в отличие от аналогичной функции для ОЛС).

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

struct list * swap(struct list *lst1, struct list *lst2, struct list *head) {
// Возвращает новый корень списка
  struct list *prev1, *prev2, *next1, *next2;
  prev1 = head;
  prev2 = head;
  while(prev1->ptr!= lst1) // поиск узла предшествующего lst1
    prev1 = prev1->ptr;
  while(prev2->ptr!= lst2) // поиск узла предшествующего lst2
    prev2 = prev2->ptr;
  next1 = lst1->ptr; // узел следующий за lst1
  next2 = lst2->ptr; // узел следующий за lst2
  if(lst2 == next1) {
 // обмениваются соседние узлы
    lst2->ptr = lst1;
    lst1->ptr = next2;
    prev1->ptr = lst2;
  }
  else if(lst1 == next2) {
  // обмениваются соседние узлы
    lst1->ptr = lst2;
    lst2->ptr = next1;
    prev2->ptr = lst2;
  }
  else {
  // обмениваются отстоящие узлы
    prev1->ptr = lst2;
    lst2->ptr = next1;
    prev2->ptr = lst1;
    lst1->ptr = next2;
  }
  if(lst1 == head)
    return(lst2);
  if(lst2 == head)
    return(lst1);
  return(head);
}

Назад

Комментариев к записи: 2

  • при вызове функции addelem(list *lst, int number)
    в скобках вместо int number пишем число.
    а вместо list *lst что нужно написать?


    • *lst — это указатель на элемент, после которого требуется осуществить добавление.


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

Ваш e-mail не будет опубликован. Обязательные поля помечены *