С++ для начинающих. Однонаправленный список LIFO

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

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

Сначала описывается структура, которая сама по себе является элементом списка. Она содержит информационные поля и указатель на следующий элемент списка. Информационные поля — это набор переменных из структуры (в нашем случае одно поле: одна переменная x). Предполагаемый список можно в самом начале знакомства представлять как обычный одномерный массив. Объявленный x будет считываться посредством клавиатуры и передаваться в элемент списка. Элемент списка будет как бы приклеиваться к уже существующему списку. Если выражаться понятнее, то x является информационным полем каждого отдельного элемента из списка.


Весь этот длинный код #2 имеет такой же смысл как код пустой программы. Я уже писал во время разминки мозга, что используется конструктор и деструктор. Конструктор выносить за класс я не стал (мне так удобно, там всего строчка кода), деструктор вынесен за класс, чтоб не путал. Запись в конструкторе Head = NULL сводит указатель, обозначающий на начало, в нулевой адрес (иные указатели элементов списка, за исключением последнего добавленного, будут указывать на адреса существующих объектов).
В деструкторе для освобождения памяти использован цикл. Для корректного освобождения памяти необходимо куда-то записывать адреса, чтобы при освобождении памяти от очередного элемента списка было известно откуда удалять следующий элемент. Для этого создаётся указатель, который сначала считывает адрес следующего элемента, и только потом освобождается тот элемент, который хранит адрес начала объекта из общего списка списка. Дальше адрес начала объекта изменяется на то значение, которое было взято как адрес следующего элемента.


Видно, что код разросся. Внутри класса List Было объявлено две функции и обе они вынесены за класс. Сначала была описана функция добавления элементов в список. Для того, чтобы выделить память для нового прицепляемого значения, была объявлена отдельная локальная переменная *temp, тип которой есть структура, а сама переменная является указателем на структуру. При этом в информационный элемент этой объявленной переменной записывается параметр, принятый функцией. А в адресный элемент присваивается значение-адрес, равное: адрес последнего активного элемент-участника списка (т. е. последнего добавленного). После чего последний буквально только что активный элемент заменяется на только что введенный в список. Т. е. происходит обновление последнего элемента. Если в очередь обычную добавляется участник, то этот участик (если он добросовестный и не имеет особых льгот) становится последним, меняя последнего активного заканчивающего очередь участника собой.
Далее была описана функция вывода списка на экран. Если присмотреться, то можно заметить большое сходство с описанием в деструкторе. Для прохода по всему списку используется цикл и внутри цикла идет поэлементное обращение к элементам непосредственного одного кусочка списка. Обратились к одному, обращаемся к следующему.
Осталось только использовать всю эту жуткую и страшную для начинающих конструкцию. Дописываем код в функцию main().


Что тут можно сказать? Это намного проще, чем вся предварительная подготовка. Объявляется переменная N для определния числа элементов в списке, объявляется переменная x, на каждом новом повторении цикла получающая себе новое значение, эта x с каждым своим новым значением заносится в элемент-кусочек списка, а также объявляется и переменная, тип которой и есть этот наш злополучный список. C помощью цикла идёт поэлементное добавление данных в список. Это напоминает сцепку вагонов. После цикла, сцепляющего каждый новый кусочек-элемент списка, идёт вывод списка на экран.
Только при выводе списка на экран мне стало ясно, что обозначает: "первым пришел, последним ушел".
  • Особое внимание хотелось бы обратить на то, что при динамической обработке после создания чего-то — это что-то нужно высвобождать из памяти и при этом высвобождать правильно. Во многих примерах, которые встречаются на некоторых страницах интернета и форумах, иногда этот момент пропускают.

======================================================================
======================================================================

СЛЕДУЮЩИЙ ШАГ — СОЗДАНИЕ СПИСКА СТРУКТУР

======================================================================
======================================================================

Только если то что выше описано воспринимается как пальцем щёлкнуть, то только тогда и только тогда имеет смысл приступать к этому новому шагу. Иначе едва ли будет понятно то, что изложено ниже.
Выше был приведён код, который обрабатывал одно поле структуры, но смысл-то в том, что весь этот материал помогает создавать динамические структуры, а значит имеет смысл рассмотреть создание списка, который будет содержать набор структур, и при этом сами структуры будут содержать более одного информационного поля. При всём этом, изначально я ориентируюсь на одно адресное поле и в дальнейших примерах приводить аналоги описываемого c наступившего момента шага — не считаю нужным.
Итак. Листинг #4 был изучен. Значит, имеет смысл привести иной готовый код с описанием создания.


Первым делом описывается некоторая структура. В дальнейшем эта структура будет являться звеном списка. В этом примере выбрана некоторая структура Студент, имя которой говорит само за себя.
В функции ввода данных в структуру параметр функции прописан как ссылка на саму эту структуру. Дело в том, что иначе в дальнейшем будет объявлена локальная переменная, тип которой будет Студент (имя созданной структуры). И изменение локальной переменной внутри функции будет изменять локальный объект, а не настоящий.
Чтобы заполнить переменную-объект структуры Student данными, удобно использовать такой прием: использовать параметр как ссылку. Иначе, без ссылочности параметра, мы будем заполнять локальную по отношению к функции добавления переменную-объект, но не оригинальную. Сама функция ввода данных в список является частью нашей структуры List. Можно было легко описать как отдельную функцию, но чтобы не запутаться в дальнейшем, пока что проще определять функции по принадлежности к чему-то (структура, класс).
Не забываем, что мы создаём динамический список и, значит, в каждом элементе-звене структуры должен хранится как минимум один адрес на другой элемент-звено структуры. По приведённому изначально примеру (листинг #4) это адрес на прошлый элемент-звено структуры. Объявляем указатель на адрес последнего звена собираемой в списке цепочки элементов.
  • (Указателем на начало следующей структуры будет указатель на предшествующее ему начало)
  • (Указатель = следующий элемент = предыдущее начало списка)
Итак. Что у нас есть? Сама структура создана, переменные в ней прописаны. Объявлены нужные функции.
Внутри структуры, имеющей значение звена цепочки элементов, т. е. внутри структуры List объявлена функция ввода данных в структуру (функция добавления элемента списка). Этой функцией и занимаемся. Особых вопросов возникнуть не должно. Может смутить cin.ignore(); Дело в том, что когда мы нажимаем Enter, подтверждая ввод, в переменную-возраст попадает символ нажатия Enter, а то, что мы пытаемся ввести как переменную-возраст, попадает в переменную-место учёбы. Чтобы нажатие Enter не уходило в переменную-возраст, это нажатие мы принудительно игнорируем, благодаря чему в нужные переменные попадают нужные значения. Если вводили строку, а дальше надо вводить числовую переменную, то каждый раз можно использовать такой способ игнорирования, пропуская нажатый Enter во избежание его занесения в переменные не для него.
Далее в функции main() была объявлена переменная типа Student. Так как язык различает регистр, я назвал эту переменную тем же именем, что и имя структуры, но с маленькой буквы. Учитывая, что названия классов (структур) многие пишут с большой буквы, то то, что переменная названа с маленькой, особой путаницы внести не должно. Также предполагается, что число студентов известно заранее и потому объявляется переменная N, обозначающая это число. После ввода числа N нажимается клавиша Enter и в поток ввода информации передается символ клавиши Enter. Происходит точно такая же ситуация, как описана выше, поэтому нужно проигнорировать этот символ. (lst.Add… пока не пишется)
Дальше в функции main() прописывается цикл ввода данных в структуру: student.Input(student);. При этом в функцию ввода передается созданная переменная-объект student, тип которого Student (тип с большой буквы, соответствует названию класса, а объект этого класса с маленькой буквы). Напоминаю, что переменная-объект student представляет собой структуру данных, в функции Student::input данные этой структуры заполняются. А так как функция принимала параметр как ссылку, то все изменения в объекте student сохранились и доступны для дальнейшей обработки. (lst.Add… пока не пишется)
Только теперь создается class List. Легко заметить большое сходство этого класса с тем классом, что описывался в самом начале этой страницы (листинг #4). Единственное отличие в том, что в качестве параметра принимается ссылка на объект, тип которого структура-студент. Зачем нужно использовать параметр-ссылку уже было написано. А параметр имеет тип структуры студент только потому что мы в список добавляем объект-студентов как звенья цепочки. Один студент, второй студент, третий студент как бы сцепляются друг с другом, чем, в общем-то, и создаётся список.
После написания класса у меня автоматом пишется конструктор и деструктор, сразу же описываю то, что в них должно происходить. (Использую конструктор по умолчанию и выношу деструктор за класс, пишу в деструкторе код).
После написания конструктора и деструктора класса List была объявлена функция добавления элемента структуры в список: void Add(Student &student). Вне класса было написано то, что должна выполнять эта функция. Учитывая, что в примере при каждом новом добавлении элемента в список изменяется адрес начала списка (сохраняя при этом адрес прошлой своей позиции), можно понять, что при каждом новом вызове функции добавления нужна временная переменная, которая будет сохранять текущий адрес. (Сам указатель на начало списка трогать не надо, потерять начало списка = потерять весь список). Дальше в новый элемент, под который выделили память, копируются данные из объекта, принимаемого функцией. После того как все данные были занесены в только что созданную переменную, идёт смена указателя на новое начало. Началом становится начало только что заполненной структуры, при этом в ней остается сохраненным указатель на прошлый элемент.
Далее была написана функция класса List для вывода списка на экран: void List Show()
На все структуры поиндексного доступа нет, есть только начало списка от которого можно оттолкнутся, по этому адресу хранится то, что вводили, и указатель на следующий элемент списка. Указатели на адреса следующих за ними элементов образуют цепочку, связывая все эти только что вводимые данные в одну кучу, в которую собраны все наши объекты-студенты. Полагаю, кому-то может быть сложно понять именно это место, но оно к пониманию обязательно. Так как все объект-студенты сохранили в себе то, что в них было введено, достаточно знать указатель на начало списка и можно легко обращаться поэлементно к каждому элементу из списка, т. е. к любому объект-суденту, сцепленного в список, что и было проделано.
В последнюю очередь в функции main() была объявлена переменная lst, тип которой есть список List. Другими словами, был создан объект типа список. Там же в функции main() внутри цикла, с помощью которого вызывается функция заполнения объект-студента, был добавлен вызов функции, добавляющей описанного объект-студента в объект-список lst. Так получилось, что заполнили одну структуру, добавилось в список, заполнили следующую, добавили — и так происходит, пока выполняется цикл. Самым последним был прописан вызов функции, отображающей список на экране (там же в main()).

======================================================================
======================================================================

ВОЗВРАЩЕНИЕ К ПЕРВОМУ КОДУ (ЛИСТИНГ #4) И ДОПИСЫВАНИЕ ФУНКЦИИ ИЗЪЯТИЯ ЭЛЕМЕНТА

======================================================================
======================================================================

Список c организацией LIFO обычно называют стеком. А для стека, как правило, определён определённый набор необходимых стеку методов:

  • —> Функция добавления элемента в стек.
  • —> Функция извлечения элемента.
  • —> Очистка стека.
  • —> Счетчик элементов стека.
  • —> Вывод всех элементов на экран.
Добавлю частичной функциональности к нашему списку: Добавлю переменную, считающую число элементов внутри списка, и функцию извлечения элемента из списка.




Вызов функции извлечения будет делаться так:


Я извиняюсь за столь неважно изложенное окончание статьи, но прошу относиться к этому последнему кусочку кода как к шпаргалке, которая поможет написать собственный список LIFO с указанными тут функциями. Статья получилась итак не маленькая и поэтому я решил ограничится только теми данными, которые дал. К параметрам, принимаемых функциями, было дописано слово const, это не должно отпугивать, постепенное и эволюционирующее восприятие материала было изложено, а параметры объявлены константными, так как многие примеры пишутся подобным образом и константы помогают избегать собственных же наших ошибок. Изменять эти параметры в нашем случае всё равно не нужно, нужно только брать из них значения.
Если эта тема была понята, то рекомендуется к изучению посмотреть информацию о правиле трёх, вы можете смотреть в разных источниках, на сайте была описана тема: С++ для начинающих. Специальные функции-члены классов. Правило трёх. Чтобы материал был в более доступной форме к пониманию, правило трёх в этой статье было проигнорировано.

34 комментария на «“С++ для начинающих. Однонаправленный список LIFO”»

  1. Дмитрий:

    Я немного усовершенствовал, и перегрузил cin>> и <<cout для отдельной структуры student чтобы можно было сделать класс list шаблонным…

    Спасибо очень помогло в понимании.

  2. Виталий:

    все очень понятно написано…спасибо за предоставленную информацию…

    такой вопрос . вот сейчас разбираюсь со списоком, и там есть такое понятие как фиктивный узел …что такое фиктивный узел и как его объявлять ? спасибо

    • Фиктивный узел — это узел, который указывает на пустое значение
      В моем примере (в случае с LIFO)

      Head = NULL, значит Head = фиктивный узел

      ============
      Списки могут быть построены по разному, поэтому если есть не пустой узел P и P->Next=NULL, то при P=P->Next, P будет фиктивным узлом.
      вот как-то так

  3. Виктор:

    Спасибо автору за классную информацию.

    В листинге 2 есть небольшая ошибка в деструкторе,

    Надо записать,

    Так как Вы используете структуру element, а не Node.

    Можно еще в учебных целях вставить строку в деструкторе

    для проверки работы деструктора.

    Спасибо автору за отличный сайт.

  4. Виктор:

  5. Виктор:

  6. Благодарю за показанную ошибку. Исправлено.

  7. Александр:

    Вам бы еще кнопку для отображения печатной версии статьи, и было бы просто великолепно! Статьи супер, объясняешь очнь понятным языком =))

  8. Slavik:

    Спасибо автору за статью, очень хорошо описано, но там в Show() в первом классе есть утечка памяти, было

  9. Slavik:

    правильно будет

  10. Дмитрий:

    Мне нужно удалить первые k элементов из конца. Все описано так как у вас.
    Вот мой код функции для удаления k элементов из начала :
    void List::Delete(List &current, int k)//k-кол-во элементов которые надо удалить
    {
    if(k==0)
    {
    cout<<"Uncorrect value"<next;
    delete head;
    current.head=temp;
    k—;
    }
    }
    }
    Скажите пожалуйся, что исправить, чтобы удалялись элементы с конца?

    • Дмитрий:

      не то прислал. извиняюсь
      void List::Delete(List &current, int k)
      {
      while(current.head!=NULL && k!=0)
      {
      Info *temp=current.head->next;
      delete head;
      current.head=temp;
      }
      }

      • Может подход исправить нужно?
        Если список имеет вид: 1,2,3 , и 1 — это начало, а 3 -это конец списка, то
        Для операций только к начальной части списка использовать FIFO
        Для операция только к конечной части списка использовать LIFO
        Для операций к обеим частям списка использовать двусвязный список
        ====================

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

      • хотя я может не понял.
        если
        1 2 3 4 5
        и при удалении 3 элементов должно стать
        1 2
        то я сейчас посмотрю, должно быть просто

        • Дмитрий:

          да именно так

        • точнее в LIFO достаточно просто удалять так
          Список 1 2 3 4 5
          Удалить 3 элемента
          Список стал 4 5
          ====================
          а иначе (именно чтоб по LIFO) можно,но у меня сейчас нет желания и возможности заниматься такими вещами.
          я могу только подсказать. Каждый раз придется копировать весь список без последнего элемента. Путем такого копирования получится эффект удаления с обратной стороны.

          • Дмитрий:

            Попробую, спасибо!)

          • Еще не забывайте удалять тот элемент, который не включается при копировании. (а-то совсем не удаление будет)
            Думаю по разному можно делать и думаю я предложил не самый изящны и не самый простой.

  11. SsAn:

    Здравствуйте! Очень помогает эта информация. Но никак не могу понять как записать список в обратном порядке 🙁 Не могли бы Вы помочь?

  12. SsAn:

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

    • Я не понимаю вопроса. 😐
      Вот данные 1,2,3,4,5
      Есть два варианта списка
      _______________
      5,4,3,2,1 (LIFO, стек)
      1,2,3,4,5 (FIFO)
      _______________
      Чтобы делать FIFO Нужен указатель на начало и указатель на следующий элемент в списке.
      Чтобы делать LIFO достатоно одного указателя на следующий элемент в списке.
      (насколько я знал (вероятно ошибочно). я давно этим всем не занимаюсь)

  13. Влад:

    а как вызвать в основной части деструктор, для удаления списка?

  14. Максим:

    Здравствуйте,нужна помощь.

    Удалить из очереди все элементы , расположенные между минимальным и максимальным элементами очереди.
  15. Георгий:

    Здравствуйте, пытаюсь сделать шаблонным этот стек:

    // 2.cpp: определяет точку входа для консольного приложения.
    //
    
    #include "stdafx.h"
    #include <iostream>
    
    using namespace std;
    
    template<typename T> struct Link{
    	T data;
    	Link* next;
    };
    template<typename T> class List{
    	Link<T>* first;
    public:
    	List() :first(NULL){}
    	~List(){		
    		Link<T> *current = first;
    		while (current != NULL){
    			Link<T>* temp = current;
    			current = current->next;
    			delete temp;
    		}
    	}
    	void add(T d){	
    		Link<T>* newlink = new Link;
    		newlink->data = d;
    		newlink->next = first;
    		first = newlink;
    	}
    	void pop(){
    		Link<T>* current = first;
    		if (current != NULL){
    			cout << current->data << endl;
    			first = current->next;
    		}
    	}
    };
    int _tmain(int argc, _TCHAR* argv[]){
    	List<int> LS;
    	int n = 3;
    	for (int i = 0; i < n; i++){
    		LS.add(i);
    	}
    
    	LS.pop();
    	LS.pop();
    	LS.pop();
    	LS.pop();
    
    	_gettch();
    	return 0;
    }
    

    однако, ошибка тут Link<T>* newlink = new Link; 1) нет подходящего ctor’a по ум 2) для исп-я класса-шаблона требуется список аргументов. Подскажите, пожалуйста, в чем проблема

  16. Георгий:

    спасибо!  а почему у меня не получается оформить код в комментариях правильно? Я делаю так: нажимаю на кнопку <>,  выбираю язык с++, вставляю код (вроде бы видно что он выделен от остального текста в комментарии)

    void main(){
        cout<<"hi";
    }

    но когда публикую, то нет того черного фона и нумерованных строк и подсветки. Может быть нужно какую то конкретную тему выбрать?

    • Потому что не прочитан красно-бордовый текст, предваряющий начало комментариев, где написано большими буквами:
      Для вставки кода в комментарий, вставьте ваш код в php теги:
      [php]ВАШ КОД[/php]

  17. Иван:

    Добрый день. Один вопрос интересует: если все сделать, НЕ ИСПОЛЬЗУЯ структуру. Это является правильным решением?

    Расписано понятно, но мне всё равно тяжело. Постепенно понимаю, огромное спасибо за предоставленную информацию!

    • С помощью класса.

      Смысл такой, что при «правильном решении» получается некоторого рода массив, который хранит адреса на свои элементы.

      Структура и класс в c++ это одно и то же.

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

  18. Vova:

    как перегрузить оператор = для списка 

    • 1. Можно написать отдельную функцию-член класса, которая будет копировать список в список. Её переделать под оператор =.
      2. Написать конструктор копирования. Это так вообще делать правильно. А в операторе перегрузки просто использовать этот конструктор.

      Сможете написать конструктор копирования?
      Если Вы хотите понять и разобраться, то имеет смысл его написать своими силами. Потом всё совсем просто.

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

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

Поиск

 
     

Случайная книга в электронном формате

https://www.litres.ru/d-m-zlatopolskiy/programmirovanie-tipovye-zadachi-algoritmy-metody-6509134/?lfrom=15589587
Яндекс.Метрика