Односвязные списки на примерах Си

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

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

Существует два основных способа построения односвязного списка. Первый способ — помещать новые элементы в конец списка^[1]. Второй — вставлять элементы в определенные позиции списка, например, в порядке возрастания. От способа построения списка зависит алгоритм функции добавления элемента. Давайте начнем с более простого способа создания списка путем помещения элементов в конец.

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

struct address {
  char name[40];
  char street[40];
  char city[20];
  char state[3];
  char zip[11];
  struct address *next; /* ссылка на следующий адрес */
} info;

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

void slstore(struct address *i,
             struct address **last)
{
  if(!*last) *last = i; /* первый элемент в списке */
  else (*last)->next = i;
  i->next = NULL;
  *last = i;
}

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

При вставке элемента в односвязный список может возникнуть одна из трех ситуаций: элемент становится первым, элемент вставляется между двумя другими, элемент становится последним. На рис. 22.3 показана схема изменения ссылок в каждом случае.

Стандартные операции с односвязными линейными списками

• Вставка элемента в начало

• Удаление элемента из начала

• Вставка элемента после текущего 

• Удаление элемента после текущего 

• Проход по списку 

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

                 +----+            п                +----+
                 |new |            р                |new |
                 +----+            е                +----+
                 |    |            в   .------------|    |
                 +----+            р   |            +----+
                                   а   |
       +----+    +----+    +----+  щ в |  +----+    +----+    +----+
       |info|    |info|    |info|  а   |  |info|    |info|    |info|
\/\/\->+----+    +----+    +----+  е   |  +----+    +----+    +----+
       |    |--->|    |--->| 0  |  т   '->|    |--->|    |--->| 0  |
       +----+    +----+    +----+  с      +----+    +----+    +----+
                                   я

Вставка в середину списка

                 +----+            п                    +----+
                 |new |            р                    |new |
                 +----+            е                    +----+
                 |    |            в        .---------->|    |
                 +----+            р        |        .--+----+
                                   а        |        | 
       +----+    +----+    +----+  щ в      | +----+ |  +----+    +----+
       |info|    |info|    |info|  а        | |info| |  |info| .->|info|
\/\/\->+----+    +----+    +----+  е   \/\/\->+----+ |  +----+ |  +----+
       |    |--->|    |--->| 0  |  т        '-|    | '->|    |-'  | 0  |
       +----+    +----+    +----+  с          +----+    +----+    +----+
                                   я


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

                 +----+            п                    +----+
                 |new |            р                    |new |<----------.
                 +----+            е                    +----+           |
                 |    |            в                    | 0  |           |
                 +----+            р                    +----+           |
                                   а                                     |
       +----+    +----+    +----+  щ в        +----+    +----+    +----+ |
       |info|    |info|    |info|  а          |info| .->|info|    |info| |
\/\/\->+----+    +----+    +----+  е   \/\/\->+----+ |  +----+    +----+ |
       |    |--->|    |--->| 0  |  т          |    |-'  |    |--->|    |-'
       +----+    +----+    +----+  с          +----+    +----+    +----+
                                   я

Следует помнить, что при вставке элемента в начало (первую позицию) списка необходимо также изменить адрес входа в список где-то в другом месте программы. Чтобы избежать этих сложностей, можно в качестве первого элемента списка хранить служебный сторожевойэлемент^[2]. В случае упорядоченного списка необходимо выбрать некоторое специальное значение, которое всегда будет первым в списке, чтобы начальный элемент оставался неизменным. Недостатком данного метода является довольно большой расход памяти на хранение сторожевого элемента, но обычно это не столь важно.

Следующая функция, sls_store(), вставляет структуры типа address в список рассылки, упорядочивая его по возрастанию значений в поле name. Функция принимает указатели на указатели на первый и последний элементы списка, а также указатель на вставляемый элемент. Поскольку первый или последний элементы списка могут измениться, функция sls_store() при необходимости автоматически обновляет указатели на начало и конец списка. При первом вызове данной функции указатели first и last должны быть равны нулю.

/* Вставка в упорядоченный односвязный список. */
void sls_store(struct address *i, /* новый элемент */
               struct address **start, /* начало списка */
               struct address **last) /* конец списка */
{
  struct address *old, *p;

  p = *start;

  if(!*last) { /* первый элемент в списке */
    i->next = NULL;
    *last = i;
    *start = i;
    return;
  }

  old = NULL;
  while(p) {
    if(strcmp(p->name, i->name)<0) {
      old = p;
      p = p->next;
    }
    else {
      if(old) { /* вставка в середину */
        old->next = i;
        i->next = p;
        return;
      }
      i->next = p; /* вставка в начало */
      *start = i;
      return;
    }
  }
  (*last)->next = i; /* вставка в конец */
  i->next = NULL;
  *last = i;
}

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

void display(struct address *start)
{
  while(start) {
    printf("%s\n", start->name);
    start = start->next;
  }
}

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

Для получения элемента из списка нужно просто пройти по цепочке ссылок. Ниже приведен пример функции поиска по содержимому поляname:

struct address *search(struct address *start, char *n)
{
  while(start) {
    if(!strcmp(n, start->name)) return start;
    start = start->next;
  }
  return NULL;  /* подходящий элемент не найден */
}

Поскольку функция search() возвращает указатель на элемент списка, содержащий искомое имя, возвращаемый тип описан как указатель на структуру address. При отсутствии в списке подходящих элементов возвращается нуль (NULL).

Удаление элемента из односвязного списка выполняется просто. Так же, как и при вставке, возможны три случая: удаление первого элемента, удаление элемента в середине, удаление последнего элемента. На рис. 22.4 показаны все три операции.

Удаление первого элемента списка
                                   
       +------+    +------+    +------+  
       |данные|    |данные|    |данные|
\/\/\->+------+    +------+    +------+
       |      |--->|      |--->|  0   |
       +------+    +------+    +------+

                   превращается в

       +------+        +------+    +------+
       |удален| \/\/\->|данные| .->|данные|
       +------+        +------+ |  +------+
       |  0   |        |      |-'  |  0   |
       +------+        +------+    +------+

Удаление среднего элемента списка
                                   
       +------+    +------+    +------+  
       |данные|    |данные|    |данные|
\/\/\->+------+    +------+    +------+
       |      |--->|      |--->|  0   |
       +------+    +------+    +------+

                   превращается в

       +------+    +------+    +------+
       |данные|    |удален|    |данные|
\/\/\->+------+    +------+    +------+
       |      |    |  0   | .->|  0   |
       +------+    +------+ |  +------+
             \______________|

Удаление последнего элемента списка
                                   
       +------+    +------+    +------+  
       |данные|    |данные|    |данные|
\/\/\->+------+    +------+    +------+
       |      |--->|      |--->|  0   |
       +------+    +------+    +------+

                   превращается в

       +------+    +------+    +------+
       |данные|    |данные|    |удален|
\/\/\->+------+    +------+    +------+
       |      |--->|  0   |    |  0   |
       +------+    +------+    +------+

Ниже приведена функция, удаляющая заданный элемент из списка структур address.

void sldelete(
     struct address *p, /* предыдущий элемент */
     struct address *i, /* удаляемый элемент */
     struct address **start, /* начало списка */
     struct address **last) /* конец списка */
{
  if(p) p->next = i->next;
  else *start = i->next;

  if(i==*last && p) *last = p;
}

Функции sldelete() необходимо передавать указатели на удаляемый элемент, предшествующий удаляемому, а также на первый и последний элементы. При удалении первого элемента указатель на предшествующий элемент должен быть равен нулю (NULL). Данная функция автоматически обновляет указатели start и last, если один из них ссылается на удаляемый элемент.

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

^[1]Не забывайте, что у односвязного списка, как и у веревки, два конца: начало и конец.

^[2]Часто называется еще сигнальной меткой.

На этом все! Теперь вы знаете все про односвязные списки на ах си, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое односвязные списки на ах си и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных