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

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

Код C++ Односвязный список

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

Код С++ Односвязный список

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

Код С++ Односвязный список

  Видно, что код разросся. Внутри класса List Было прописано две функции и обе они вынесены за класс. Не нужно забывать, что функции возвращают значение даже если оно пустое, то все равно должны. Исключение конструкторы и деструкторы. Сначала была описана функция добавления элементов в список. Для того чтобы выделить память для нового получаемого значения была объявлена отдельная локальная переменная *temp тип которой есть структура, а сама переменная является указателем на структуру. При этом в информационный элемент этой объявленной переменной записывается параметр принятый функцией. А в адресный элемент присваивается значение равное последнему активному элементу. После чего последний активный элемент меняется на только что введенный в список

(Возможно неправильное разъяснение. Это то, как я понял)
  Далее была описана функция вывода списка на экран. Если присмотреться, то можно заметить большое сходство с деструктором. Для прохода по всему списку используется цикл и внутри цикла идет поэлементное обращение к элементам списка. Обратились к одному, обращаемся к следующему.

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

Код С++ Односвязный список

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

  Только при выводе списка на экран мне стало ясно что обозначает первым пришел, последним ушел.

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

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

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

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

  Итак. Код был изучен. Значит имеет смысл привести готовый код с описанием того как он создавался.

Код C++ Список на основе структуры Студент (LIFO)

  Первым делом описывается некоторая структура. В дальнейшем эта структура будет являться звеном списка. В этом примере выбрана некоторая структура Студент, имя которой говорит само за себя.
  В функции ввода данных в структуру, параметр прописан как ссылка на саму эту структуру. Дело в том, что в дальнейшем будет объявлена локальная переменная, тип которой будет Студент (имя созданной структуры). Чтобы заполнить такую переменную данными удобно использовать такой прием. При этом сама функция ввода данных является частью этой структуры. Можно было легко описать как отдельную функцию, но чтоб не запутаться в дальнейшем, проще определять функции по принадлежности к чему-то (структура, класс)
  Не забываем, что мы создаем динамический список и, значит, в структуре должен хранится как минимум один адрес на другой элемент структуры. По приведенному изначально примеру это адрес на прошлый элемент (на предыдущее начало списка). Объявляем указатель на этот адрес

  • (Указателем на начало следующей структуры будет указатель на предшествующее ему начало)
  • (Указатель = следующий элемент = предыдущее начало списка)

  Итак. Сама структура создана, переменные в ней прописаны. Объявлены нужные функции.

  Внутри структуры объявлена функция ввода данных в структуру. Этой функцией и занимаемся. Особых вопросов возникнуть не должно. Может смутить cin.ignore(); Дело в том, что массив типа char всегда содержит символ NULL, который нужно проигнорировать в созданной ситуации. Подробнее происходило так: Сначала вводились символы в массив типа char и там остался символ завершения этого массива, при этом сразу после ввода данных в массив типа char, происходит попытка ввести значение в переменную-возраст. Оператор >> срабатывает так, что в переменную возраст записывается этот символ NULL, а то что мы ввели как возраст записывается в следующую переменную. Поэтому следует игнорировать NULL
(Если вводили строку, а дальше надо числовую переменную, то каждый раз можно использовать этот способ)

Далее в функции main() была объявлена переменная типа студент. Так как язык различает регистр, я назвал эту переменную тем же именем, что имя структуры. Разница в том, что маленькими буквами. На самом деле так делать мало кто рекомендует, но учитывая, что названия классов (структур) многие пишут с большой буквы, то то, что переменная названа с маленькой особой путаницы внести не должно. Также предполагается, что число студентов известно заранее и потому объявляется переменная N, обозначающая это число. После ввода N, нажимается клавиша Enter и в поток >> передается символ этой клавиши. Происходит точно такая же ситуация, как описана выше, поэтому нужно проигнорировать этот символ.(lst.Add… пока не пишется)

  Дальше в функции main() прописывается цикл ввода данных в структуру student.Input(student);. При этом в функцию ввода передается созданная переменная student, тип которой Студент (с большой буквы Имя класса, с маленькой объект этого класса). Напоминаю, что эта переменная представляет собой структуру данных, в функции данные этой структуры заполняются. А так как функция принимала параметр как ссылку, то все изменения в структуре студент сохранились и доступны для дальнейшей обработки . (lst.Add… пока не пишется)

  Только теперь создается class List. Легко заметить большое сходство этого класса с тем классом, что описывался в самом начале этой страницы. Единственное отличие в том, что в качестве параметра принимается ссылка на объект тип которого Структура студент. Зачем нужно уже было написано.

  После написания класс у меня автоматом пишется конструктор и деструктор, сразу же описываю то что в них должно происходить. (Использую конструктор по умолчанию и выношу деструктор за класс, пишу в деструкторе код).

  После написания конструктора и деструктора класса List была объявлена функция добавления элемента структуры в список void Add(Student &student). Вне класса был написано то что должна выполнять эта функция. Учитывая, что в примере при каждом новом добавлении элемента в список, изменяется адрес начала списка (сохраняя при этом адрес прошлой своей позиции), можно понять, что при каждом новом вызове функции добавления нужна временная переменная, которая будет сохранять текущий адрес. (Сам указатель на начало списка трогать не надо, потерять начало списка=потерять всю структуру). Дальше в новый элемент, под который выделили память копируются данные из объекта, который принимает функция. После того как все данные были занесены в только что созданную переменную, идет смена указателя на новое начало. Началом становится начало только что заполненной структуры, при этом в ней остается сохраненным указатель на прошлый элемент

  Далее была написана функция класса List для вывода списка на экран void List Show()

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

  В последнюю очередь в функции main была объявлена переменная lst, тип которой есть список (List). Другими словами был создан объект типа список. Там же в функции main внутри цикла, с помощью которого вызывается функция заполнения структуры, был добавлен вызов функции добавляющей эту заполненную структуру в список. Так получилось, что заполнили одну структуру, добавилось в список, заполнили следующую, добавили и так происходит пока выполняется цикл. Самым последним был прописан вызов функции отображающей список на экране (там же в main)

======================================================================
======================================================================
ВОЗВРАЩЕНИЕ К ПЕРВОМУ КОДУ И ДОПИСЫВАНИЕ ФУНКЦИИ ИЗЪЯТИЯ ЭЛЕМЕНТА
======================================================================
======================================================================

 Имеется ввиду тот код, который был до первого шага. В качестве основных функций обработки стека выступают:

  • —> Функция добавления элемента в стек
  • —> Функция извлечения элемента
  • —> Очистка стека
  • —> Счетчик элементов стека
  • —> Вывод всех элементов на экран

Это те функции, которые обычно присутствуют в реализации списка типа LIFO и большим выделено то, чего не хватает в первом описанном коде. Это я опишу вкратце, чтоб не писать одно и то же миллион раз

В классе добавляется переменная, которая будет считать число элементов внутри стека и функция извлечения элемента

Код С++

Вызов функции извлечения

==============================================
  Я извиняюсь за столь неважно изложенное окончание статьи, но прошу относится к этому последнему кусочку кода как к шпаргалке, которая поможет написать собственный список LIFO с указанными тут функциями. Статья получилась итак не маленькая и поэтому я решил ограничится только теми данными, которые дал. В качестве параметров принимаемых функциями было дописано слово const, это не должно отпугивать, поэтапное и эволюционирующее восприятие материала было изложено, а параметры объявлены константными так как многие примеры пишутся подобным образом и помогают избегать собственных же ошибок. Изменять эти параметры все равно не нужно., нужно только брать из них значения.

Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

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

  • Дмитрий говорит:

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

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

  • Виталий говорит:

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

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

    • admin говорит:

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

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

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

  • Виктор говорит:

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

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

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

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

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

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

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

  • Виктор говорит:

  • Виктор говорит:

  • admin говорит:

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

  • Александр говорит:

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

  • Slavik говорит:

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

  • Slavik говорит:

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

  • Дмитрий говорит:

    Мне нужно удалить первые 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;
      }
      }

      • admin говорит:

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

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

      • admin говорит:

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

        • Дмитрий говорит:

          да именно так

        • admin говорит:

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

          • Дмитрий говорит:

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

          • admin говорит:

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

  • SsAn говорит:

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

  • SsAn говорит:

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

    • admin говорит:

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

  • Влад говорит:

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

  • Максим говорит:

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

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

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

    // 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) для исп-я класса-шаблона требуется список аргументов. Подскажите, пожалуйста, в чем проблема

    • admin говорит:

  • Георгий говорит:

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

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

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

    • admin говорит:

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

  • Иван говорит:

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

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

    • admin говорит:

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

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

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

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

  • Vova говорит:

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

    • admin говорит:

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

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

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

Ваш e-mail не будет опубликован.

Поиск

 
     

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

Яндекс.Метрика
НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

Девушка-программист едет в трамвае, читает книгу. Старушка смотрит на девушку, смотрит на книгу, крестится и в ужасе выбегает на следующей остановке. Девушка читала книгу "Язык Ада"

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок