АйТи бубен

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

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

Вы посетили:
odnosvjaznyj_spisok

Различия

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

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

odnosvjaznyj_spisok [2018/08/09 10:11]
 odnosvjaznyj_spisok [2020/06/13 13:46] (текущий)
Строка 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>

Инструменты страницы

Я на связи КОНТАКТЫ
Если не указано иное, содержимое этой вики предоставляется на условиях следующей лицензии: GNU Free Documentation License 1.3