Инструменты пользователя

Инструменты сайта


odnosvjaznyj_spisok

Различия

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

Ссылка на это сравнение

odnosvjaznyj_spisok [2018/08/09 03:11] (текущий)
Строка 1: Строка 1:
 +====== Односвязный список ======
  
 +{{htmlmetatags>​
 +metatag-description=(Структура данных Связный список в C#, добавление и удаление узлов. Пример реализации односвязного списка на C++.)
 +}}
 +
 +
 +
 +{{ :​spisok-01.png |}}
 +Односвязный список - это совокупность нескольких объектов,​ каждый из которых представляет собой элемент списка,​ состоящий из двух частей. Первая часть элемента - значение,​ которое он хранит,​ вторая - информация о следующем элементе списка. ​
 +
 +Характер информации о следующем элементе зависит от того, где конкретно хранится список. Например,​ если это оперативная память,​ то информация будет представлять собой адрес следующего элемента,​ если файл - позицию следующего элемента в файле. Мы с Вами будем рассматривать реализацию списка хранящегося в оперативной памяти,​ однако,​ при желании,​ вы сможете создать собственный код для хранения списка в файле. Итак, приступим: ​
 +
 +Каждый элемент списка мы представим программно с помощью структуры,​ которая состоит из двух составляющих: ​
 +
 +1.Одно или несколько полей, в которых будет содержаться основная информация,​ предназначенная для хранения. ​
 +
 +2. Поле, содержащее указатель на следующий элемент списка. ​
 +
 +Отдельные объекты подобной структуры мы далее будем называть узлами,​ связывая их между собой с помощью полей, содержащих указатели на следующий элемент. ​
 +
 +<​file>​
 +    //узел списка
 +    struct node
 +    {
 + // Информационная часть узла ​
 + int value;
 +
 +  // Указатель на следующий узел списка ​
 +      node *next;
 +    };
 +</​file>​
 +После создания структуры,​ нам необходимо инкапсулировать её объекты в некий класс, что позволит управлять списком,​ как цельной конструкцией. В классе будет содержаться два указателя (на хвост, или начало списка и голову,​ или конец списка),​ а так же набор функции для работы со списком. ​
 +
 +
 + //​голова
 +    node *phead;
 +
 + //​хвост
 + node *ptail;
 +
 + 
 +
 +В целом, полученный список можно представить так:
 +
 +
 +Итак, основные моменты создания списка,​ мы рассмотрели,​ переходим непосредственно к его формированию.
 +
 +Формирование списка.
 +Отведем место для указателей в статической памяти.
 +    node *phead;
 + node *ptail;
 +
 + 
 +
 +
 +Зарезервируем место для динамического объекта. ​
 + phead=new node;
 +
 + 
 +
 +
 +Присвоим значение переменной ptail, и поместим в информационное поле значение элемента. ​
 + ptail = phead;
 +    ptail->​value = "​значение1";​
 +
 +
 + 
 +
 +
 +Поместим в поле узла адрес еще одного - нового динамического объекта. ​
 + ptail->​next = new node;
 +
 + 
 +
 +
 +Переменная ptail должна содержать адрес последнего добавленного элемента,​ т. к. он добавлен в конец. ​
 + ptail = ptail->​next;​
 +
 + 
 +
 +
 +Если требуется завершить построение списка,​ то в поле указателя последнего элемента нужно поместить NULL. 
 + ptail->​next = NULL;
 +    ptail->​value = "​значение2";​
 +
 + 
 +
 +
 +В результате построен линейный односвязный список,​ содержащий два узла.
 +
 +Вставка узла в определенное заданное место списка.
 +Здесь и далее, мы не будем приводить фрагменты кода, так как они являются крупными. Позже мы с вами просто рассмотрим пример реализации односвязного списка целиком. А, сейчас,​ разберем операции над списком с помощью иллюстраций. ​
 +Выделить память под новый узел. ​
 +Записать в новый узел значение. ​
 +Записать в указатель на следующий узел адрес узла, который должен располагаться после нового узла. ​
 +Заменить в узле, который будет располагаться перед новым узлом, записанный адрес на адрес нового узла. ​
 +
 +Удаление узла из списка.
 +Записать адрес узла, следующего за удаляемым узлом, в указатель на следующий узел в узле, предшествующем удаляемому. ​
 +Удалить узел, предназначенный для удаления. ​
 +
 +====== Реализация - односвязный список ======
 +
 +<​file>​
 +#include <​iostream>​
 +using namespace std;
 + 
 +
 +struct Element
 +{
 +   // Данные
 +   char data;
 +   // Адрес следующего элемента списка
 +   ​Element * Next;
 +};
 +
 +// Односвязный список
 +class List
 +{
 +   // Адрес головного элемента списка
 +   ​Element * Head;
 +   // Адрес головного элемента списка
 +   ​Element * Tail;
 +   // Количество элементов списка
 +   int Count;
 +
 +public:
 +   // Конструктор
 +   ​List();​
 +   // Деструктор
 +   ​~List();​
 +
 +   // Добавление элемента в список
 +   // (Новый элемент становится последним)
 +   void Add(char data);
 +
 +   // Удаление элемента списка
 +   // (Удаляется головной элемент)
 +   void Del();
 +   // Удаление всего списка
 +   void DelAll();
 +
 +   // Распечатка содержимого списка
 +   // (Распечатка начинается с головного элемента)
 +   void Print();
 +
 +   // Получение количества элементов,​ находящихся в списке
 +   int GetCount();
 +};
 +
 +List::​List()
 +{
 +   // Изначально список пуст
 +   Head = Tail = NULL;   
 +   Count = 0;
 +}
 +
 +List::​~List()
 +{
 +   // Вызов функции удаления
 +   ​DelAll();​
 +}
 +
 +int List::​GetCount()
 +{
 +   // Возвращаем количество элементов
 +   ​return Count;
 +}
 +
 +void List::​Add(char data)
 +{
 +   // создание нового элемента
 +   ​Element * temp = new Element;
 +
 +   // заполнение данными
 +   ​temp->​data = data;
 +   // следующий элемент отсутствует
 +   ​temp->​Next = NULL;
 +   // новый элемент становится последним элементом списка
 +   // если он не первый добавленный
 +   ​if(Head!=NULL){
 + Tail->​Next=temp;​
 + Tail = temp;
 +   }
 +   // новый элемент становится единственным
 +   // если он первый добавленный
 +   else{
 +    ​Head=Tail=temp;​
 +   }
 +}
 +
 +void List::Del()
 +{
 +   // запоминаем адрес головного элемента
 +   ​Element * temp = Head;
 +   // перебрасываем голову на следующий элемент
 +   Head = Head->​Next;​
 +   // удаляем бывший головной элемент
 +   ​delete temp;
 +}
 +
 +void List::​DelAll()
 +{
 +   // Пока еще есть элементы
 +   ​while(Head != 0)
 +      // Удаляем элементы по одному
 +      Del();
 +}
 +
 +void List::​Print()
 +{
 +   // запоминаем адрес головного элемента
 +   ​Element * temp = Head;
 +   // Пока еще есть элементы
 +   ​while(temp != 0)
 +   {
 +      // Выводим данные
 +      cout << temp->​data << " ";
 +      // Переходим на следующий элемент
 +      temp = temp->​Next;​
 +   }
 +
 +   cout << "​\n\n";​
 +}
 +
 +// Тестовый пример
 +void main()
 +{
 +   // Создаем объект класса List
 +   List lst;
 +
 +   // Тестовая строка
 +   char s[] = "​Hello,​ World !!!\n";​
 +   // Выводим строку
 +   cout << s << "​\n\n";​
 +   // Определяем длину строки
 +   int len = strlen(s);
 +   // Загоняем строку в список
 +   ​for(int i = 0; i < len; i++)
 +      lst.Add(s[i]);​
 +   // Распечатываем содержимое списка
 +   ​lst.Print();​
 +   // Удаляем три элемента списка
 +   ​lst.Del();​
 +   ​lst.Del();​
 +   ​lst.Del();​
 +   //​Распечатываем содержимое списка
 +   ​lst.Print();​
 +}
 +</​file>​
загрузка...
odnosvjaznyj_spisok.txt · Последние изменения: 2018/08/09 03:11 (внешнее изменение)