Различия

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

@@ Строка 1: / Строка 1: @@
+====== Односвязный список ======
+{{htmlmetatags>
+metatag-description=(Структура данных Связный список в C#, добавление и удаление узлов. Пример реализации односвязного списка на C++.)
+}}
+{{ :spisok-01.png |}}
+Односвязный список - это совокупность нескольких объектов, каждый из которых представляет собой элемент списка, состоящий из двух частей. Первая часть элемента - значение, которое он хранит, вторая - информация о следующем элементе списка.
+Характер информации о следующем элементе зависит от того, где конкретно хранится список. Например, если это оперативная память, то информация будет представлять собой адрес следующего элемента, если файл - позицию следующего элемента в файле. Мы с Вами будем рассматривать реализацию списка хранящегося в оперативной памяти, однако, при желании, вы сможете создать собственный код для хранения списка в файле. Итак, приступим:
+Каждый элемент списка мы представим программно с помощью структуры, которая состоит из двух составляющих:
+.Одно или несколько полей, в которых будет содержаться основная информация, предназначенная для хранения.
+. Поле, содержащее указатель на следующий элемент списка.
+Отдельные объекты подобной структуры мы далее будем называть узлами, связывая их между собой с помощью полей, содержащих указатели на следующий элемент.
+<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>

загрузка...

АйТи бубен

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

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

Различия

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