С++ для начинающих. Однонаправленный список LIFO
Для начала требуется подготовить мозг. Будет выделяться память. Будет использован класс. Будут использованы конструктор и деструктор. Конструктор нужен для инициализации первого элемента списка как пустого. Деструктор нужен, чтобы освободить всю выделенную память. Пугаться использования класса не надо. Для тех, кто не знаком с такими элементами языка С++, рекомендуются к изучению темы:
При описании этой темы в листингах написан код для старого компилятора. Многие студенты сталкиваются с упрямыми староверами, подсовывающими для решения задач компиляторы морально устаревшие. Но есть и такие люди, которым нужно знать, как решать подобные задачи в старых компиляторах. Надеюсь, что с маленьким получающимся неудобством вы справитесь своими силами. Отличий от современных подобных кодов очень мало.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
//#Листинг #1 Узел списка Односвязные списки Borland C++ 3.1 #include <conio.h> #include <iostream.h> struct element //Структура с инфополями и адресным полем { int x; //Инфополе. значения из x будут передаваться в список element *Next; //Адресное поле }; int main() { clrscr(); //зачистка экрана от старой информации cin.get(); //чтобы окно не закрывалось сразу return 0; } |
Сначала описывается структура, которая сама по себе является элементом списка. Она содержит информационные поля и указатель на следующий элемент списка. Информационные поля — это набор переменных из структуры (в нашем случае одно поле: одна переменная x). Предполагаемый список можно в самом начале знакомства представлять как обычный одномерный массив. Объявленный x будет считываться посредством клавиатуры и передаваться в элемент списка. Элемент списка будет как бы приклеиваться к уже существующему списку. Если выражаться понятнее, то x является информационным полем каждого отдельного элемента из списка.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
//Листинг #2 Список Односвязные списки Borland C++ 3.1 #include <conio.h> #include <iostream.h> struct element //Структура с инфополями и адресным полем { int x; //Инфополе. значения из x будут передаваться в список element *Next; //Адресное поле }; class List //Класс Список { element *Head; //Указатель на последний активный элемент или просто голова списка public: List() {Head=NULL;} //Конструктор и инициализация указателя пустым значением ~List(); //Деструктор }; List::~List() //Деструктор вынесен за класс { while (Head!=NULL) //Пока по адресу не пусто { element *temp=Head->Next; //Временная переменная для хранения адреса следующего элемента delete Head; //Освобождаем адрес обозначающий начало Head=temp; //Меняем адрес на следующий } } int main() { clrscr(); cin.get(); return 0; } |
Весь этот длинный код #2 имеет такой же смысл как код пустой программы. Я уже писал во время разминки мозга, что используется конструктор и деструктор. Конструктор выносить за класс я не стал (мне так удобно, там всего строчка кода), деструктор вынесен за класс, чтоб не путал. Запись в конструкторе Head = NULL сводит указатель, обозначающий на начало, в нулевой адрес (иные указатели элементов списка, за исключением последнего добавленного, будут указывать на адреса существующих объектов).
В деструкторе для освобождения памяти использован цикл. Для корректного освобождения памяти необходимо куда-то записывать адреса, чтобы при освобождении памяти от очередного элемента списка было известно откуда удалять следующий элемент. Для этого создаётся указатель, который сначала считывает адрес следующего элемента, и только потом освобождается тот элемент, который хранит адрес начала объекта из общего списка списка. Дальше адрес начала объекта изменяется на то значение, которое было взято как адрес следующего элемента.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
//Листинг #3 Односвязные списки Borland C++ 3.1 #include <conio.h> #include <iostream.h> struct element //Структура с инфополями и адресным полем { int x; //Инфополе. значения из x будут передаваться в список element *Next; //Адресное поле }; class List //Класс Список { element *Head; //Указатель на последний активный элемент или просто голова списка public: List() {Head=NULL;} //Конструктор и инициализация указателя пустым значением ~List(); //Деструктор. Далее он вынесен за класс void Add(int x); //Функция для добавления значений в список void Show(); //Функция для отображения списка на экране }; List::~List() //Деструктор вынесен за класс { while (Head!=NULL) //Пока по адресу не пусто { element *temp = Head->Next; //Временная переменная для хранения адреса следующего элемента delete Head; //Освобождаем адрес обозначающий начало Head = temp; //Меняем адрес на следующий } } void List::Add(int x) //Функция добавления элементов в список { element *temp = new element; //При каждом вызове выделяется память temp->x = x; //Записываем x в элемент структуры element (в x структуры element) temp->Next = Head; //Указываем, что след. элемент это объект по адресу Head Head = temp; //Указываем, что последний активный элемент это только что введенный } void List::Show() //Функция отображения списка на экране { element *temp = Head; //Определяем указатель, который изначально он равен адресу начала списка while (temp != NULL) //До тех пор пока не встретит пустое значение { cout << temp->x << " "; //Выведет элемент x из списка temp = temp->Next; //Указываем, что далее нам нужен следующий элемент } } int main() { clrscr(); cin.get(); return 0; } |
Видно, что код разросся. Внутри класса List Было объявлено две функции и обе они вынесены за класс. Сначала была описана функция добавления элементов в список. Для того, чтобы выделить память для нового прицепляемого значения, была объявлена отдельная локальная переменная *temp, тип которой есть структура, а сама переменная является указателем на структуру. При этом в информационный элемент этой объявленной переменной записывается параметр, принятый функцией. А в адресный элемент присваивается значение-адрес, равное: адрес последнего активного элемент-участника списка (т. е. последнего добавленного). После чего последний буквально только что активный элемент заменяется на только что введенный в список. Т. е. происходит обновление последнего элемента. Если в очередь обычную добавляется участник, то этот участик (если он добросовестный и не имеет особых льгот) становится последним, меняя последнего активного заканчивающего очередь участника собой.
Далее была описана функция вывода списка на экран. Если присмотреться, то можно заметить большое сходство с описанием в деструкторе. Для прохода по всему списку используется цикл и внутри цикла идет поэлементное обращение к элементам непосредственного одного кусочка списка. Обратились к одному, обращаемся к следующему.
Осталось только использовать всю эту жуткую и страшную для начинающих конструкцию. Дописываем код в функцию main().
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
//Листинг #4 Односвязный список LIFO, использование Borland C++ 3.1 #include <conio.h> #include <iostream.h> struct element //Структура с инфополями и адресным полем { int x; //Инфополе. значения из x будут передаваться в список element *Next; //Адресное поле }; class List //Класс Список { element *Head; //Указатель на последний активный элемент или просто голова списка public: List() {Head = NULL;} //Конструктор и инициализация указателя пустым значением ~List(); //Прототип деструктора. Сам деструктор вынесен за класс void Add(int x); //Прототип функции добавления значений в список void Show(); //Прототип функцииотображения списка на экране }; List::~List() //Деструктор вынесен за класс { while (Head != NULL) //Пока по адресу не пусто { element *temp = Head->Next; //Временная переменная для хранения адреса следующего элемента delete Head; //Освобождаем адрес обозначающий начало Head = temp; //Меняем адрес на следующий } } void List::Add(int x) //Функция добавления элементов в список { element *temp = new element; //При каждом вызове выделяется память temp->x = x; //Записываем x в элемент структуры element (в x структуры element) temp->Next = Head; //Указываем, что след. элемент это объект по адресу Head Head = temp; //Указываем, что последний активный элемент это только что введенный } void List::Show() //Функция отображения списка на экране { element *temp=Head; //Определяем указатель, который изначально он равен адресу начала списка while (temp != NULL) //До тех пор пока не встретит пустое значение { cout << temp->x << " "; //Выведет элемент x из списка temp = temp->Next; //Указываем, что далее нам нужен следующий элемент } } int main() { clrscr(); int N; //Число элементов в список int x; //Элементы вводимые в список List lst; //Переменная, тип которой список cout << "N = "; cin >> N; //Указали сколько элементов вводить в список for (int i=0; i<N; i++) { cout << i+1 << ". x = "; cin >> x; //Ввод x с клавиатуры lst.Add(x); //Добавление элемента в список } lst.Show(); //Вывод списка на экран cin.ignore().get(); //Для того, чтобы окно сразу не закрывалось return 0; } |
Что тут можно сказать? Это намного проще, чем вся предварительная подготовка. Объявляется переменная N для определния числа элементов в списке, объявляется переменная x, на каждом новом повторении цикла получающая себе новое значение, эта x с каждым своим новым значением заносится в элемент-кусочек списка, а также объявляется и переменная, тип которой и есть этот наш злополучный список. C помощью цикла идёт поэлементное добавление данных в список. Это напоминает сцепку вагонов. После цикла, сцепляющего каждый новый кусочек-элемент списка, идёт вывод списка на экран.
Только при выводе списка на экран мне стало ясно, что обозначает: "первым пришел, последним ушел".
- Особое внимание хотелось бы обратить на то, что при динамической обработке после создания чего-то — это что-то нужно высвобождать из памяти и при этом высвобождать правильно. Во многих примерах, которые встречаются на некоторых страницах интернета и форумах, иногда этот момент пропускают.
======================================================================
======================================================================
======================================================================
СЛЕДУЮЩИЙ ШАГ — СОЗДАНИЕ СПИСКА СТРУКТУР
======================================================================
======================================================================
Только если то что выше описано воспринимается как пальцем щёлкнуть, то только тогда и только тогда имеет смысл приступать к этому новому шагу. Иначе едва ли будет понятно то, что изложено ниже.
Выше был приведён код, который обрабатывал одно поле структуры, но смысл-то в том, что весь этот материал помогает создавать динамические структуры, а значит имеет смысл рассмотреть создание списка, который будет содержать набор структур, и при этом сами структуры будут содержать более одного информационного поля. При всём этом, изначально я ориентируюсь на одно адресное поле и в дальнейших примерах приводить аналоги описываемого c наступившего момента шага — не считаю нужным.
Итак. Листинг #4 был изучен. Значит, имеет смысл привести иной готовый код с описанием создания.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
//Листинг #5 Односвязный список LIFO, список студентов Borland C++ 3.1 #include <iostream.h> #include <string.h> #include <stdlib.h> /*СТРУКТУРА СТУДЕНТ*/ struct Student { char Name[20]; //Имя char NameLast[30]; //Фамилия int Age; //Возраст char School[30]; //Место учебы void Input(Student &student); //Функция ввода данных в структуру Student *Next; //Адрес на следующий элемент }; class List { Student *Head; //Указатель на начало списка public: List():Head(NULL){}; //Конструктор по умолчанию (Head=NULL) ~List(); //Прототип деструктора void Add(Student &student); //Прототип функции добавления элемента в список void Show(); //Прототип функции вывода списка на экран }; /*ФУНКЦИЯ ЗАПОЛНЕНИЯ ДАННЫХ ПО СТУДЕНТУ*/ void Student::Input(Student &student) { cout << endl; //Небольшой разрыв при каждом новом вводе cout << "Имя: "; cin.getline(Name,20); //Ввод имени cout << "Фамилия: "; cin.getline(NameLast,30); //Ввод фамилии cout << "Полных лет "; cin >> Age; //Ввод возраста cin.ignore(); //Игнорируем символ cout << "Где учится "; cin.getline(School, 30); //Ввод места учебы } List::~List() //Деструктор класса List { while (Head != NULL) //Пока по адресу есть хоть что-то { Student *temp = Head->Next; //Сразу запоминаем указатель на адрес следующего элемента структуры delete Head; //Освобождаем память по месту начала списка Head = temp; //Меняем адрес начала списка } } /*ФУНКЦИЯ ДОБАВЛЕНИЯ НОВОЙ СТРУКТУРЫ В СПИСОК*/ void List::Add(Student &student) { Student *temp = new Student; //Выделение памяти под новую структуру temp->Next = Head; //Указываем, что адрес следующего элемента это начало списка //Копирование содержимого параметра student в только что созданную переменную strcpy(temp->Name, student.Name); strcpy(temp->NameLast, student.NameLast); temp->Age = student.Age; strcpy(temp->School, student.School); Head = temp; //Смена адреса начала списка } /*ФУНКЦИЯ КЛАССА LIST ДЛЯ ВЫВОДА СПИСКА НА ЭКРАН*/ void List::Show() { Student *temp = Head; //Объявляем указатель и изначально он указывает на начало while (temp != NULL) //Пока по адресу на начало хоть что-то есть { //Выводим все элементы структуры cout << temp->Name << "\t\t"; //Вывод имени cout << temp->NameLast <<"\t\t"; //Вывод фамилии cout << temp->Age << "\t\t"; //Вывод возраста cout << temp->School << endl; //Вывод места учебы temp = temp->Next; //Указываем на следующий адрес из списка } cout << endl; } int main () { Student student; //Объявили переменную, тип которой Студент int N; //Объявили переменную - число студентов List lst; //Объявили переменную типа Список. Она выступает как контейнер данных cout << "N = "; cin >> N; //Ввели число студентов cin.ignore(); //Игнорируем клавишу Enter for (int i=0; i<N; i++) { student.Input(student); //Передаем в функцию заполнения переменную студент lst.Add(student); //Добавляем заполненную структуру в список } cout << endl; lst.Show(); //Показываем список на экране cin.ignore().get(); return 0; } |
Первым делом описывается некоторая структура. В дальнейшем эта структура будет являться звеном списка. В этом примере выбрана некоторая структура Студент, имя которой говорит само за себя.
В функции ввода данных в структуру параметр функции прописан как ссылка на саму эту структуру. Дело в том, что иначе в дальнейшем будет объявлена локальная переменная, тип которой будет Студент (имя созданной структуры). И изменение локальной переменной внутри функции будет изменять локальный объект, а не настоящий.
Чтобы заполнить переменную-объект структуры 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 обычно называют стеком. А для стека, как правило, определён определённый набор необходимых стеку методов:
- —> Функция добавления элемента в стек.
- —> Функция извлечения элемента.
- —> Очистка стека.
- —> Счетчик элементов стека.
- —> Вывод всех элементов на экран.
Добавлю частичной функциональности к нашему списку: Добавлю переменную, считающую число элементов внутри списка, и функцию извлечения элемента из списка.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
//Листинг #4a class List { Node *Head; int size; public: List():Head(NULL),size(0) {}; //Инициализация значений с помощью конструктора ~List(); void Add(const int x); //Дописано слово const void Show(); void Pop(const int N); //Объявлена функция извлечения элемента int Count() {return size;}; //Внутри класса описана функция-счетчик }; void List::Add(const int x) { size++; //При каждом вызове функции добавления увеличивается счетчик элементов |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//Листинг #4b /*ФУНКЦИЯ ИЗВЛЕЧЕНИЯ ЭЛЕМЕНТА ОПИСАНА ВНЕ КЛАССА*/ void List::Pop(const int N) //В качестве параметра принимается номер извлекаемого элемента { Node *temp = Head; //Обращаемся к началу списка if ((Head != NULL) && (N < size)) //Делаем проверку на то что список не пуст и N не превышает число его элементов { for (int i=0; i<N; i++) temp = temp->Next; //Меняем адрес N раз cout << temp-> x << " " << endl; //Выводим N элемент списка на экран } cout << endl; } |
Вызов функции извлечения будет делаться так:
|
1 2 3 4 5 6 |
//Листинг #4c lst.Pop(0); //Извлечение первого элемента lst.Pop(1); //Извлечение второго элемента lst.Pop(2); //Извлечение третьего элемента cout << lst.Count() << " " << endl; //Вызов Функции вывода числа элементов списка на экран |
Я извиняюсь за столь неважно изложенное окончание статьи, но прошу относиться к этому последнему кусочку кода как к шпаргалке, которая поможет написать собственный список LIFO с указанными тут функциями. Статья получилась итак не маленькая и поэтому я решил ограничится только теми данными, которые дал. К параметрам, принимаемых функциями, было дописано слово const, это не должно отпугивать, постепенное и эволюционирующее восприятие материала было изложено, а параметры объявлены константными, так как многие примеры пишутся подобным образом и константы помогают избегать собственных же наших ошибок. Изменять эти параметры в нашем случае всё равно не нужно, нужно только брать из них значения.
Если эта тема была понята, то рекомендуется к изучению посмотреть информацию о правиле трёх, вы можете смотреть в разных источниках, на сайте была описана тема: С++ для начинающих. Специальные функции-члены классов. Правило трёх. Чтобы материал был в более доступной форме к пониманию, правило трёх в этой статье было проигнорировано.
34 комментария на «“С++ для начинающих. Однонаправленный список LIFO”»
Добавить комментарий
Случайная книга в электронном формате
Я немного усовершенствовал, и перегрузил cin>> и <<cout для отдельной структуры student чтобы можно было сделать класс list шаблонным…
Спасибо очень помогло в понимании.
все очень понятно написано…спасибо за предоставленную информацию…
такой вопрос . вот сейчас разбираюсь со списоком, и там есть такое понятие как фиктивный узел …что такое фиктивный узел и как его объявлять ? спасибо
Фиктивный узел — это узел, который указывает на пустое значение
В моем примере (в случае с LIFO)
Head = NULL, значит Head = фиктивный узел
============
Списки могут быть построены по разному, поэтому если есть не пустой узел P и P->Next=NULL, то при P=P->Next, P будет фиктивным узлом.
вот как-то так
Спасибо автору за классную информацию.
В листинге 2 есть небольшая ошибка в деструкторе,
Надо записать,
Так как Вы используете структуру element, а не Node.
Можно еще в учебных целях вставить строку в деструкторе
для проверки работы деструктора.
Спасибо автору за отличный сайт.
Благодарю за показанную ошибку. Исправлено.
Вам бы еще кнопку для отображения печатной версии статьи, и было бы просто великолепно! Статьи супер, объясняешь очнь понятным языком =))
Спасибо автору за статью, очень хорошо описано, но там в Show() в первом классе есть утечка памяти, было
правильно будет
пока не проверил, но сомневаюсь, что так правильно.
мои сомнения напрасны. Вы правы.
Мне нужно удалить первые k элементов из конца. Все описано так как у вас.
Вот мой код функции для удаления k элементов из начала :
void List::Delete(List ¤t, int k)//k-кол-во элементов которые надо удалить
{
if(k==0)
{
cout<<"Uncorrect value"<next;
delete head;
current.head=temp;
k—;
}
}
}
Скажите пожалуйся, что исправить, чтобы удалялись элементы с конца?
не то прислал. извиняюсь
void List::Delete(List ¤t, 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) можно,но у меня сейчас нет желания и возможности заниматься такими вещами.
я могу только подсказать. Каждый раз придется копировать весь список без последнего элемента. Путем такого копирования получится эффект удаления с обратной стороны.
Попробую, спасибо!)
Еще не забывайте удалять тот элемент, который не включается при копировании. (а-то совсем не удаление будет)
Думаю по разному можно делать и думаю я предложил не самый изящны и не самый простой.
Здравствуйте! Очень помогает эта информация. Но никак не могу понять как записать список в обратном порядке 🙁 Не могли бы Вы помочь?
в обратном порядке список FIFO называется
Дело в том, что мне нужно записать список в обратном порядке с помощью одного указателя.
Я не понимаю вопроса. 😐
Вот данные 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) для исп-я класса-шаблона требуется список аргументов. Подскажите, пожалуйста, в чем проблемаспасибо! а почему у меня не получается оформить код в комментариях правильно? Я делаю так: нажимаю на кнопку <>, выбираю язык с++, вставляю код (вроде бы видно что он выделен от остального текста в комментарии)
void main(){ cout<<"hi"; }но когда публикую, то нет того черного фона и нумерованных строк и подсветки. Может быть нужно какую то конкретную тему выбрать?
Потому что не прочитан красно-бордовый текст, предваряющий начало комментариев, где написано большими буквами:
Для вставки кода в комментарий, вставьте ваш код в php теги:
[php
]ВАШ КОД[/php]Добрый день. Один вопрос интересует: если все сделать, НЕ ИСПОЛЬЗУЯ структуру. Это является правильным решением?
Расписано понятно, но мне всё равно тяжело. Постепенно понимаю, огромное спасибо за предоставленную информацию!
С помощью класса.
Смысл такой, что при «правильном решении» получается некоторого рода массив, который хранит адреса на свои элементы.
Структура и класс в c++ это одно и то же.
Можно написать один класс, это будет хорошо. У меня разделено только потому, что я плохо понимал что это вообще такое, один из наиболее понятных для себя примеров, я описал в этой теме.
Спасибо большое Вам! Делаю только класс, наловчился, удобно:)
как перегрузить оператор = для списка
1. Можно написать отдельную функцию-член класса, которая будет копировать список в список. Её переделать под оператор =.
2. Написать конструктор копирования. Это так вообще делать правильно. А в операторе перегрузки просто использовать этот конструктор.
Сможете написать конструктор копирования?
Если Вы хотите понять и разобраться, то имеет смысл его написать своими силами. Потом всё совсем просто.