Удаление элемента из однонаправленного списка

Динамические структуры данных

 

Однонаправленные (односвязные) списки

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

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

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

Метод доступа к элементам в очереди: FIFO (First Input – First Output) по принципу "первый пришёл – первый вышел".

Рисунок 1. Линейный однонаправленный список

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

struct имя_типа { информационное поле; адресное поле; };

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

struct Node {        int key;//информационное поле        Node*next;//адресное поле       };

Информационных полей может быть несколько.

struct point {         char*name;//информационное поле         int age;//информационное поле         point*next;//адресное поле        };

Каждый элемент списка содержит ключ, который идентифицирует этот элемент. Ключ обычно бывает либо целым числом, либо строкой.

Основными операциями, осуществляемыми с однонаправленными списками, являются:

· создание списка;

· печать (просмотр) списка;

· вставка элемента в список;

· удаление элемента из списка;

· поиск элемента в списке

· проверка пустоты списка;

· удаление списка.

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

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

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

struct Single_List {//структура данных               int Data; //информационное поле               Single_List *Next; //адресное поле              };. . . . . . . . . . Single_List *Head; //указатель на первый элемент списка. . . . . . . . . . Single_List *Current; //указатель на текущий элемент списка (при необходимости)

Создание однонаправленного списка

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

//создание однонаправленного списка (добавления в конец)void Make_Single_List(int n,Single_List** Head){ if (n > 0) { (*Head) = new Single_List(); //выделяем память под новый элемент cout << "Введите значение "; cin >> (*Head)->Data; //вводим значение информационного поля (*Head)->Next=NULL;//обнуление адресного поля Make_Single_List(n-1,&((*Head)->Next)); }}

Вставка элемента в однонаправленный список

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

Рисунок 2. Вставка элемента в однонаправленный список

/*вставка элемента с заданным номером в однонаправленный список*/Single_List* Insert_Item_Single_List(Single_List* Head,       int Number, int DataItem){   Number--; Single_List *NewItem=new(Single_List); NewItem->Data=DataItem;   NewItem->Next = NULL; if (Head == NULL) {//список пуст Head = NewItem;//создаем первый элемент списка } else {//список не пуст Single_List *Current=Head; for(int i=1; i < Number && Current->Next!=NULL; i++) Current=Current->Next; if (Number == 0){ //вставляем новый элемент на первое место NewItem->Next = Head; Head = NewItem; } else {//вставляем новый элемент на непервое место if (Current->Next != NULL)   NewItem->Next = Current->Next; Current->Next = NewItem; } } return Head; }

Удаление элемента из однонаправленного списка

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

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

Рисунок 3. Удаление элемента из однонаправленного списка

---

Дата добавления: 2020-04-25; просмотров: 101; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!