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

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

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

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 = NULL;  // это последний узел списка
  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, list *root) {
  struct list *temp;
  temp = root;
  while(temp->ptr!=lst)  // просматриваем список начиная с корня
    {    // пока не найдем узел, предшествующий lst
      temp = temp->ptr;
    }
  temp->ptr = lst->ptr; // переставляем указатель
  free(lst);  // освобождаем память удаляемого узла
  return(temp);
}
Удаление корня списка

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

struct list * deletehead(list *root) {
  struct list *temp;
  temp = root->ptr;
  free(root);   // освобождение памяти текущего корня
  return(temp); // новый корень списка
}
Вывод элементов списка

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

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

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

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

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

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

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

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

Назад

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

  • Кристина

    Здравствуйте! не могли бы вы помочь ?! Задание такое: дан линейный список, в нем нужно найти максимальный элемент и потом его поставить в начало списка.


  • . Создать односвязный список на основе класса, объекты которого будут формировать этот список. В описание класса должны входить данные для хранения комплексных чисел; функции для доступа к отдельным компонентам списка, вывод на экран элементов списка в формате ai+b, добавление элемента в начало списка, удаление элемента списка. Использовать указатель this.



  • Добрый день! Может кто поможет, не получается никак решить задачу такого типа, нужно сформировать стек чисел и занести в новый список до максимума из первого стека — списка. Мое решение, все работает, кроме копирования в новый список.. вот сама функция записи (стек уже заполнен)

    struct Stack *new_list = NULL; // указатель на стек, в который будем записывать
    void task(struct Stack*begin) {
    struct Stack *temp = begin;  // создали указатель на стек
    int max = 0;
    printf("\n От вершины до максимального значения:\n");
    while (temp != NULL) { // заносим значения в новый стек до max
      if ((temp->number) > max) {
        new_list = (struct Stack*)malloc(sizeof(struct Stack));
        new_list->number = temp->number;
        new_list->next = new_list;
        max = (temp->number);
      }
      temp = temp->next;
      }
    printf("\nПросмотр\n");
    while (new_list != NULL) {
      printf("%4d", new_list->number);
      new_list = new_list->next;
    }
    }

    • Елена Вставская

      Нужно в цикле определить максимальный элемент и запомнить его указатель.

      struct Stack *maxelem = begin;
      int max = maxelem->number;
      while(temp!=NULL) {
        if((temp->number) > max) {
          maxelem = temp;
          max = (temp->number);
        }
        temp = temp->next;
      }

      Только после этого, когда мы знаем максимальный элемент и указатель на него, можно формировать новый список.


      • Большое спасибо за быстрый ответ.. наверное, я что-то не понял, определил указатель на макс элемент, занес в новый список значения, но на консоли не отображается.  Не могли бы вы посмотреть, очень благодарен вам за помощь.

        struct Stack *new_list = NULL;
        void task(struct Stack*begin) {
          struct Stack *temp = begin;
          struct Stack *maxelem = begin;
          int max = maxelem->number;
          printf("\n От вершины до максимального значения:\n");
          while (temp != NULL) {
            if ((temp->number) > max) {
              maxelem = temp;
              max = (temp->number);
            }
            temp = temp->next;
          }
          struct Stack*temp2 = begin;
          while (temp2 != maxelem) {
          new_list = (struct Stack*)malloc(sizeof(struct Stack));
          new_list->number = temp2->number;
          new_list->next = new_list;
          temp2->next = temp2;
          }
          printf("\nПросмотр\n");
          while (new_list != NULL) {
          printf("%4d", new_list->number);
          new_list = new_list->next;
          }
        }

        • Елена Вставская

          Ошибка в выделенной строчке. Вы зацикливаете указатель на сам элемент. Поле указателя на следующий элемент нужно инициализировать в момент создания этого «следующего» элемента.


          • Так в цикле я создаю структуру и инициализирую ее поля ,т.е. присваиваю в новую структуру адрес предыдущей.. запутался..


          • Елена Вставская
            struct Stack *new_list = (struct Stack*)malloc(sizeof(struct Stack));
            new_list->number = begin->number; // это корень нового списка
            new_list->next = NULL;
              while (temp2 != maxelem) {
              struct Stack *temp3 = new_list;
              new_list = (struct Stack*)malloc(sizeof(struct Stack));
              new_list->number = temp2->number;
              temp3->next = new_list;
              new_list->next = NULL;
              temp2 = temp2->next;
              }

  • Николай

    В функции addelem() уже известен адрес узла, который содержит NULL. А я не понимаю как его найти. Допустим при инициализации списка известен адрес корня, который и есть последним узлом. Теперь, допустим у меня возникла необходимость добавить в этот список еще узел. Тут все понятно. Узел root имеет адрес. Я создаю вашей функцией новый. Заполняю его. Сохраняю в промежуточном указателе адрес поля рут т.е NULL.  Далее меняю указатель рута на адрес нового узла, и потом переписываю указатель добавленного узла на NULL. Теперь я еще добавляю узел. Знаю о существовании рута. Если я воспользуюсь вашей функцией то перепишу указатель рута и нового узла. Опс…Все понял спасибо. Но тогда еще вопрос. Таким образом я получу список задом наперед. Если я имею словарь с уже отсортированными словами от а до я. То в памяти буква я станет в начале списка, а А в конце. Можете помочь разобраться с этим?


    • Елена Вставская

      В функцию addelem() Вы передаете указатель на элемент, после которого необходимо осуществить добавление. Указатель корня списка при этом должен быть сохранен в другой переменной, и вывод списка необходимо осуществлять с корня.


      • Николай

        Значит я должен реализовать просмотр списка и как только я найду узел с NULL передать его указатель в функцию добавления узла. Благодарю за помощь. Со словарем не понятно. Имею файл с отсортированными словами от А до Я. Мне нужно его загрузить в память так что бы возле корня была буква А. С NULL буква Я. Ваша функция добавляет новый узел в конец списка. А как сделать наоборот? Я только учусь. Поэтому вопросы могут быть простыми для вас…


        • Елена Вставская

          В этом случае нужна функция, которая будет добавлять элемент в начало списка, наподобие этой

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

  • Николай

    У меня вопрос. В самом начале в списке один узел и его указатель = NULL. После добавления в список еще одного узла, указатель корневого станет показывать адрес добавленного узла, а у того, что добавился станет NULL. Как добавить следующий узел? Ведь единственный известный — это корневой


    • Елена Вставская

      Для этой цели в статье предлагается использовать функцию addelem()


  • Мне кажется в описании функции удаления узла есть ошибка: «Функция возвращает указатель на узел, следующий за удаляемым», но в приведенной функции возвращается как раз предшествующий, т.е. тот, чей ptr и переписали ("пока не найдем узел, предшествующий lst"). и, в принципе, зачем что-то возвращать, если можно просто сделать функцию как void.


    • Елена Вставская

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



  • Здравствуйте!) Можете пожалуйста объяснить что означает  (struct list*) перед функцией mallocа в строчке

    lst = (struct list*)malloc(sizeof(struct list));

    когда мы создаем корень списка?


    • Елена Вставская

      Это — приведение типа. Поскольку функция malloc() возвращает указатель неопределенного типа, чтобы не возникало ошибки его нужно привести к требуемому значению. Значение типа должно совпадать с тем, что стоит в левой части равенства. В данном случае это указатель lst, имеющий тип (struct list *).


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

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