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

Связный список

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

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

Каждый элемент связного списка содержит поле с данными, а также указатель (ссылку) на следующий и/или предыдущий элемент.

Эта структура позволяет эффективно выполнять операции добавления и удаления элементов для любой позиции в последовательности.

Причем это не потребует реорганизации структуры, которая бы потребовалась в массиве.

Минусом связного списка, как и других структур типа «список», в сравнении его с массивом, является отсутствие возможности работать с данными в режиме произвольного доступа, т. е.

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

По типу связности выделяют односвязные, двусвязные, XOR-связные, кольцевые и некоторые другие списки.

Каждый узел односвязного (однонаправленного связного) списка содержит указатель на следующий узел. Из одной точки можно попасть лишь в следующую точку, двигаясь тем самым в конец. Так получается своеобразный поток, текущий в одном направлении.

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

На изображении каждый из блоков представляет элемент (узел) списка. Здесь и далее Head list – заголовочный элемент списка (для него предполагается поле next). Он не содержит данные, а только ссылку на следующий элемент. На наличие данных указывает поле info, а ссылки – поле next (далее за ссылки будет отвечать и поле prev). Признаком отсутствия указателя является поле nil.

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

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

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

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

Двусвязный список

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

Когда количество памяти, по каким-либо причинам, ограничено, тогда альтернативой двусвязному списку может послужить XOR-связный список. Последний использует логическую операцию XOR (исключающее «ИЛИ», строгая дизъюнкция), которая для двух переменных возвращает истину лишь при условии, что истинно только одно из них, а второе, соответственно, ложно. Таблица истинности операции:

ab
000
011
101
110

В качестве переменных a и b у нас выступают адреса (на следующий и предыдущий элемент), над которыми выполняется операция XOR, возвращающая реальный адрес следующего элемента.

XOR-связный список

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

Кольцевой список

Рассмотрим основные операции над связными списками.

Программная реализация списка

На примере двусвязного списка, разберем принцип работы этой структуры данных. При реализации списка удобно использовать структуры (в Pascal – записи).

Общая форма описания узла двунаправленного связного списка и указателя на первый элемент списка:

struct имя_списка { информационное_поле_1; информационное_поле_2; … информационное_поле_n; указатель_на_следующий_элемент; указатель_на_предыдущий_элемент; }; имя_списка *указатель_на_голову_списка;

указатель_на_следующий_элемент;указатель_на_предыдущий_элемент;имя_списка *указатель_на_голову_списка;

Пример:

struct DoubleList //описание узла списка { int data; //информационное поле DoubleList *next; //указатель на следующий элемент DoubleList *prev; //указатель на предыдущий элемент }; DoubleList *head; //указатель на первый элемент списка

struct DoubleList //описание узла спискаint data; //информационное полеDoubleList *next; //указатель на следующий элементDoubleList *prev; //указатель на предыдущий элементDoubleList *head; //указатель на первый элемент списка

Теперь, предполагая, что описан узел и указатель на голову списка (см. пример выше), напишем функции обработки связного списка.

Добавление элемента

Опишем функцию AddList, которая в качестве параметров принимает значение и адрес будущего узла, после чего создает его в списке:

void AddList(int value, int position) { DoubleList *node=new DoubleList; //создание нового элемента node->data=value; //присвоение элементу значения if (head==NULL) //если список пуст { node->next=node; //установка указателя next node->prev=node; //установка указателя prev head=node; //определяется голова списка } else { DoubleList *p=head; for(int i=position; i>1; i—) p=p->next; p->prev->next=node; node->prev=p->prev; node->next=p; //добавление элемента p->prev=node; } coutnext=node; //установка указателя nextnode->prev=node; //установка указателя prevhead=node; //определяется голова спискаfor(int i=position; i>1; i—) p=p->next;node->next=p; //добавление элементаcoutnext; a->prev->next=a->next; //удаление элемента a->next->prev=a->prev; delete a; } coutnext;a->prev->next=a->next; //удаление элементаcoutprev=a->prev; delete a; } cout

Источник: http://kvodo.ru/linked-lists.html

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

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

Каждый узел однонаправленного (односвязного) линейного списка (ОЛС) содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на 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);}

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

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

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

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

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

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

50

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);}

Назад: Структуры данных

Источник: https://prog-cpp.ru/data-ols/

Понятие односвязного линейного списка и его реализация на языке C

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

До сих пор мы с Вами рассматривали структуры данных, отображая их на массив. За это время мы успели изучить стек, очередь, очередь с приоритетами и таблицу. Однако эти структуры данных можно реализовывать и без массива, а например с использованием так называемых связных списков.

Списку можно дать несколько определений. Здесь представлены некоторые из них.

Связный список—конечная последовательность однотипных элементов, которые называются узлами списка.

Связный список—последовательность, элементами которой являются записи (структуры), связанные друг с другом с помощью указателей, которые хранятся в этих же элементах.

Связный список—структура данных, определяемая следующим образом:

  1. Пустой список является списком
  2. Структура вида [Голова | Хвост] является списком, если голова — первый элемент списка, а хвост — список, состоящий из оставшихся элементов исходного списка

Обращаю Ваше внимание, что последнее определение называется рекурсивным определением списка.

Существует несколько видов списка: односвязный линейный список (ОЛС), последовательный линейный список (ПЛС), двусвязный линейный список (ДЛС) и другие. Однако в данной статье будет рассматриваться именно ОЛС.

Чтобы Вам стало более понятно, что такое список, рассмотрим следующую картинку.#image.jpg

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

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

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

Над линейный списком определены следующие операции:

  1. Инициализация
  2. Включение элемента
  3. Исключение элемента
  4. Переход в начало списка
  5. Переход в конец списка
  6. Переход к следующему элементу
  7. Уничтожение списка

Реализация односвязного линейного списка

При реализации ОЛС в статической памяти располагают дескриптор, состоящий из двух полей:

  1. Указатель на фиктивный элемент
  2. Указатель на текущий элемент

/*Базовый тип списка*/typedef int listOneBaseType;/*Указатель на элемент списка*/typedef struct element *ptrEl;/*Структура элемента списка*/struct element {listOneBaseType data; // ДанныеptrEl link; // Указатель на следующий элемент списка};/*Дескриптор списка*/typedef struct {ptrEl start; // Указатель на фиктивный элементptrEl ptr; // Указатель на рабочий элемент}

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

P.S. При использовании фиктивного элемента, все операции нужно выполнять после того элемента, на который указывает ptr.

Инициализация списка

Инициализация происходит в три шага:

  1. Выделение памяти для фиктивного элемента
  2. В дескрипторе указателю start присвоить блок с только что выделенной памятью
  3. Указателю ptr присвоить start.

Поясню, что здесь, и зачем. При инициализации происходит создание списка, но не заполнение его элементами. Создание списка подразумевает создание фиктивного элемента. Так как его поле данных не используется, то список остается по-прежнему пуст. Когда память выделена, остается лишь правильно присвоить ссылки указателям.Код инициализации таков:

/*Инициализация списка. L — дескриптор*/void initListOne(ListOne *L) {// Выделение пямяти под фиктивный элементL->start = (ptrEl) malloc(sizeof(element));/*Если памяти не хватило*/if (!L->start) {listOneError = listOneNoMem;return;}/*Иначе*/// ptr указывает на то, что и start — на фиктивныйL->ptr = L->start;// Нет ссылки на следующий элементL->ptr->link = NULL;}

Включение элемента

Включение элемента порой сложно понять, поэтому постараюсь как можно доходчиво объяснить. Рассмотрим список из нескольких элементов.#image.jpg

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

Допустим, мы вставляем элемент с данными — 100.Теперь нужно вставить новый элемент между двумя элементами списка, то есть изменить ссылки, находящиеся в полях ptr.#image.jpgТеперь рассмотрим код операции включения.

/*Включение элемента в список L — дескриптор. E — данные*/void putListOne(ListOne *L, listOneBaseType E) {// Выделение памяти под новый элементptrEl temp = (ptrEl) malloc(sizeof(element));/*Если памяти недостаточно*/if (!temp) {listOneError = listOneNoMem;return;}/*Иначе перемычка*/// Внесение информции в новый элементtemp->data = E;// Новый элемент указывает на следующийtemp->link = L->ptr->link;// Текущий элемент указывает на новыйL->ptr->link = temp;}

 Исключение элемента

Пусть нам дан тот же список, что и в примере с включением элемента.

#image.jpgТак как ptr указывает на фиктивный — исключаем первый. Здесь перемычка ссылок немного сложнее, чем в предыдущем примере. Нужно создать временный элемент так, чтобы он был равен исключаемому, т.

е. имел один и тот же с ним адрес. Это нужно для того, чтобы не потерять тот элемент, на который исключаемый ссылается.#image.jpgТеперь — перемычка указателей и удаление временного элемента. #image.

jpg

Вот и вся операция исключения. Ниже представлен код.

/*Исключение элемента из списка. L — дескриптор. E — переменная для данных*/void getListOne(ListOne *L, listOneBaseType *E) {/*Если список пуст*/if (isEmptyListOne(L)) {return;}/*Если рабочий указатель указывает на последний элемент*/if (!L->ptr->link) {listOneError = listOneEnd;return;}/*Иначе*/// Временный элементptrEl pntr = L->ptr->link;// Текущий элемент ссылается на тот, на который ссылается исключаемыйL->ptr->link = pntr->link;// Считывание информации из элемента списка*E = pntr->data;// Временный элемент ни на что не ссылаетсяpntr->link = NULL;// Удаление временного элементаfree((void *) pntr);}

Остальные операции я не буду так подробно расписывать, так как они просты в реализации.

Готовая реализация односвязного линейного списка

Файл List_One.h

/****************************************//* Односвязный линейный список *//****************************************/#ifndef _lIST_ONE_H_#define _lIST_ONE_H_/*Описание исключительных ситуаций*/const int listOneOK = 0;const int listOneEmpty = 1;const int listOneNoMem = 2;const int listOneEnd = 3;/**********************************//*Переменная ошибок*/extern int listOneError;/*Базовый тип списка*/typedef int listOneBaseType;/*Указатель на элемент списка*/typedef struct element *ptrEl;/*Структура элемента списка*/struct element {listOneBaseType data; // ДанныеptrEl link; // Указатель на следующий элемент списка};/*Дескриптор списка*/typedef struct {ptrEl start; // Указатель на фиктивный элементptrEl ptr; // Указатель на рабочий элемент} ListOne;/*Функции работы со списком*/void initListOne(ListOne *L); // Инициализация спискаvoid putListOne(ListOne *L, listOneBaseType E); // Включение элемента в списокvoid getListOne(ListOne *L, listOneBaseType *E);// Исключение элемента из спискаvoid movePtrListOne(ListOne *L); // Сдвиг рабочего указателяvoid beginPtrListOne(ListOne *L); // Установка рабочего указателя в начало спискаvoid endPtrListOne(ListOne *L); // Установка рабочего указателя в конец спискаvoid doneListOne(ListOne *L); // Удаление спискаint isEmptyListOne(ListOne *L); // Предикат: является ли список пустым/***************************/#endif

Файл List_One.c

Источник: https://mvblog.ru/archives/396/

����������� ������

Линейный односвязный список
���������� |

� ����������� ������ ������ ������� ���������� �������� ������ �� ��������� ������� ������. ������ ������� ������ ������ ������������ ����� ���������, ������� ������� �� �������������� ����� � ��������� �����. ������������� ����������� ������ �������� ���, ��� �������� �� ���. 22.2.

���. 22.2 ����������� ������

+———+ +———+ +———+| ������ | | ������ | | ������ |+———+ +———+ +———+|���������|—>|���������|—>| 0 |+———+ +———+ +———+

���������� ��� �������� ������� ���������� ������������ ������. ������ ������ � �������� ����� �������� � ����� ������[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 �������� ����� ��������� ������ � ������ ������.

���. 22.3. ������� �������� new � ����������� ������ (� ������� info — ���� ������)

������� � ������ ������ +—-+ � +—-+ |new | � |new | +—-+ � +—-+ | | � .————| | +—-+ � | +—-+ � | +—-+ +—-+ +—-+ � � | +—-+ +—-+ +—-+ |info| |info| |info| � | |info| |info| |info|\/\/\->+—-+ +—-+ +—-+ � | +—-+ +—-+ +—-+ | |—>| |—>| 0 | � '->| |—>| |—>| 0 | +—-+ +—-+ +—-+ � +—-+ +—-+ +—-+ � ������� � �������� ������ +—-+ � +—-+ |new | � |new | +—-+ � +—-+ | | � .———->| | +—-+ � | .—+—-+ � | | +—-+ +—-+ +—-+ � � | +—-+ | +—-+ +—-+ |info| |info| |info| � | |info| | |info| .->|info|\/\/\->+—-+ +—-+ +—-+ � \/\/\->+—-+ | +—-+ | +—-+ | |—>| |—>| 0 | � '-| | '->| |-' | 0 | +—-+ +—-+ +—-+ � +—-+ +—-+ +—-+ � ������� � ����� ������ +—-+ � +—-+ |new | � |new ||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)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», 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 �������� ��� ��� ��������.

���. 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]����� ���������� ��� ���������� ������.

���������� |

Источник: https://cpp.com.ru/shildt_spr_po_c/22/2205.html

Реализация односвязного линейного списка в СИ

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

Односвязный список – это динамическая структура данных, элементы которой содержат ссылку на следующий элемент. Последний элемент имеет в качестве ссылки NULL. Для доступа к списку используется указатель на первый элемент.

  1. Работа со списком занимает гораздо меньше времени, чем с массивом
  2. Списки можно нарисовать на бумаге, тем самым наглядно понять механизм работы
  3. Списки можно определить рекурсивно

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

typedef struct Node{int value;struct Node *next;} Spisok;

  • Используем typedef для создания нового типа, чтобы в дальнейшем не писать слово struct.
  • int value — хранимое значение, может быть любого типа.
  • struct Node *next —  указатель на следующий узел списка.
  • Spisok — название структуры.

Инициализируем список

Spisok *create(int data){// Выделение памяти под корень спискаSpisok *tmp = (Spisok*)malloc(sizeof(Spisok));// Присваивание значения узлуtmp -> value = data;// Присваивание указателю на следующий элемент значения NULLtmp -> next = NULL;return(tmp);}

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

Добавим узел в начало списка

Spisok *add_element_start(int data, Spisok *head){// Выделение памяти под узел спискаSpisok *tmp = (Spisok*)malloc(sizeof(Spisok));// Присваивание значения узлуtmp -> value = data;// Присваивание указателю на следующий элемент значения указателя на «голову» // первоначального спискаtmp -> next = head;return(tmp);}

Добавим узел в конец списка

void add_element_end(int data, Spisok *head){// Выделение памяти под корень спискаSpisok *tmp = (Spisok*)malloc(sizeof(Spisok));// Присваивание значения узлуtmp -> value = data;// Присваивание указателю на следующий элемент значения NULLtmp -> next = NULL;// Присваивание новому указателю указателя head.

// Присваивание выполняется для того, чтобы не потерять указатель на «голову» спискаSpisok *p = head;// Сдвиг указателя p в самый конец первоначального спискаwhile (p -> next != NULL)p = p -> next;// Присваивание указателю p -> next значения указателя tmp (созданный новый узел)p -> next = tmp;}

  • p -> next имеет значение NULL, так как указатель p расположен в конце списка. Указатель tmp ссылается на только что созданный узел, который мы хотим добавить в конец списка. Следовательно, нужно сделать так, чтобы последний элемент текущего списка ссылался на добавляемый узел (а не на NULL). Именно для этого используется строчка p -> next = tmp.
  • Мы не проверяем список на пустоту, так как ранее список был инициализирован (имеется заглавное звено).

Добавим узел в определенное место списка

Spisok *add_element_n_position(int data, int n, Spisok *head){// Присваивание новому указателю указателя head.

// Присваивание выполняется для того, чтобы не потерять указатель на «голову» спискаSpisok *p = head;// Счетчикint count = 1;// Поиск позиции nwhile (count < n - 1 && p -> next != NULL){p = p -> next;count++;}// Выделение памяти под узел спискаSpisok *tmp = (Spisok*)malloc(sizeof(Spisok));// Присваивание значения узлуtmp -> value = data;// Присваивание указателю tmp -> next значения указателя p -> next // (созданный новый узел)tmp -> next = p -> next;// Присваивание указателю p -> next значения указателя tmp (созданный новый узел)p -> next = tmp;return head;}

  • Рассмотрим пример для того, чтобы лучше понять принцип работы данной функции. Имеем следующий список: 1 2 3 4 5 6 7 8 9. Например, нам нужно в пятую позицию добавить элемент 10. Сдвигаем указатель p до 4 элемента (это выполняется в цикле while). Указателю на следующий элемент для нового узла присваиваем значение p -> next [строчка tmp -> next = p -> next] (после четвертого элемента идет пятый, но мы на 5 позицию вставляем новый узел списка, он должен ссылаться на «старый» пятый элемент, чтобы «цепочка» из указателей не прерывалась после вставки нового элемента).
  • Мы «соединили» новый узел с элементами, которые следуют после пятой позиции, то есть имеем следующие: 10 5 6 7 8 9. Однако нам нужно «присоединить» предшествующие элементы. Для этого указателю на следующий элемент для четвертого узла присваиваем значение tmp. То есть теперь p -> next [строчка p -> next = tmp] ссылается не на элемент со значением 5, а на новый узел с параметром 10. А узел со значением 10 (то есть узел, который мы добавляем в список), в свою очередь, ссылается на элемент c параметром 5, который ссылается на элемент со значением 6 и так далее.

Удалим весь список

Spisok *remove_all(Spisok *head){// Сдвиг указателя head в самый конец первоначального спискаwhile (head != NULL){// Присваивание новому указателю указателя headSpisok *p = head;head = head -> next;// Освобождение памяти для указателя pfree(p);}return NULL;}

Данная функция полностью «уничтожает» список, рассмотрим случай когда нужно удалить только определенный элемент из списка.

Удалим определенный узел списка

Spisok *remove_element(int data, Spisok *head){// Присваивание новому указателю  tmp указателя head, p — NULLSpisok *tmp = head, *p = NULL;// Проверка списка на пустотуif (head == NULL)return NULL;// Если список не пуст, поиск указателя на искомый элементwhile (tmp && tmp -> value != data){p = tmp;tmp = tmp -> next;}// Если удаляемый элемент первыйif (tmp == head){free(head);return tmp -> next;}// Если в списке нет искомого элемента, то возвращаем первоначальный списокif (!tmp)return head;// Присваивание новому указателю указателя tmpp -> next = tmp -> next;// Освобождение памяти для указателя tmpfree(tmp);return head;}

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

Двухсвязные линейные списки

Как мы уже говорили, линейные списки могут быть односвязными и двухсвязными.

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

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

Рассмотрим особенности работы с двухсвязным списком.

1. Как и в случае с односвязным списком, создадим две структуры. Тексты этих структур расположим в начале программы (до main() и других функций). Вот возможная реализация структур:

struct Data

{

   int a; // данные

};

struct List2

{

   Data d;

   List2 *prev; // указатель на предшествующий элемент

   List2 *next; // указатель на последующий элемент

};

2. Затем создаём два указателя:

List2 *Begin = NULL; // Начало списка

List2 *End   = NULL; // Конец списка

3. Теперь можно формировать какой-то начальный список. Делаем это по аналогии с тем, как делали при работе с односвязными списками. Начнём формировать список из трёх чисел 3, 5 и 1:

// Создаём первый элемент

List2 *t = new List2;

t->d.a = 3;

t->prev = NULL;

t->next = NULL;

// Настроим на него оба указателя

Begin = t;

End = t;

// Создаём второй элемент

t->next = new List2;

List2 *p = t;

t = t->next;

t->prev = p;

t->d.a = 5;

t->next = NULL;

End = t;

// Создаём третий элемент

t->next = new List2;

p = t;

t = t->next;

t->prev = p;

t->d.a = 1;

t->next = NULL;

End = t;

Всё, список из трёх чисел создан. Приведём хотя бы некоторые действия с этим списком.

1.Обход списка в прямом направлении и его вывод на экран монитора:

void print_forward(List2 *Begin)

{

   List2 *p = Begin;

   cout

Источник: http://victor192007.narod.ru/files/cpp_d1.html

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