огромное спасибо за подробности и ваш подход. Видео о более правильном построении такого списка есть на ютубе и люди часами настраивают его с учетом всех принципов ООП, но получить первый уровень понимания как строить такие списки без высочайшего понимания C++ на таких роликах не выйдет. А у вас достаточно маленьких знаний и желания Ещё раз спасибо
Вот такой момент: сколько смотрел видео по тегам односвязный список, будь-то СимплКод или преподы из МФТИ, ничего годного найти не удалось до твоего канала. Урок реально помог! Спасибо!
Только один вопрос: что означает изначальное Node* внутри класса Node? Создание большого указателя, по которому может идти перемещение посредством this? Как называется этот элемент синтаксиса?
Спасибо! Node - это класс (тип данных), а Node *head - это объявление указателя типа Node. То есть, head - это обычная переменная-указатель внутри класса.
Вот рабочий вариант: #include using namespace std; // Making a node struct containing an int data and a pointer // to next node struct Node{ int data; Node *next; // Parameterised constructor with default argument Node(int val=0) :data(val),next(nullptr){} // Parameterise constructor Node(int val, Node *tempNext):data(val),next(tempNext){} }; class LinkedList{ // Head pointer Node* head; public: // default constructor. Initializing head pointer LinkedList():head(nullptr){} // inserting elements (At start of the list) void insert(int val){ // make a new node Node* new_node = new Node(val); // If list is empty, make the new node, the head if (head == nullptr){ head = new_node; } // else, make the new_node the head and its next, the previous // head else{ new_node->next = head; head = new_node; } } // loop over the list. return true if element found bool search(int val){ Node* temp = head; while(temp != nullptr){ if (temp->data == val) return true; temp = temp->next; } return false; } void remove(int val){ Node* temp = head; // If the head is to be deleted if (temp != nullptr && temp->data == val){ head = temp->next; delete temp; return; } // Else loop over the list and search for the node to delete else{ Node* curr = head; while(temp != nullptr && temp->data != val){ // When node is found, delete the node and modify the pointers curr = temp; temp = temp->next; } // If values is not found in the linked list if(!temp){ cout next; delete temp; } } void display() { Node* temp = head; while(temp != nullptr){ cout data next; } cout
Добрый день! Я конечно не знаком с C++, но примерно все уловил, но не понял почему когда вызывали метод insert в самом конце и указывая индекс 0 он вставлял значения после 1, а не перед?
Поправьте, пожалуйста, если не прав: в методе Erase, в случае, если удалённый элемент node являлся tail, разве теперь tail не должен быть right, а не left?
Вопрос автору! Не является ли излишеством в методе getAt() в условии цикла while вставлять проверку node? Ведь всё равно когда обход списка дойдёт до последнего элемента node->next станет NULL и цикл завершит свою работу. Или может логической необходимости в этой проверке нет, и она прописана для подстраховки?
нужно переписать, чтобы индекс соответствовал вставляемому элементу (считайте это домашним заданием), а вообще вставку первого и последнего лучше выполнять методами push_front() и push_back() они оптимизированы под это
Лучше сделать через switch case, чтобы два раза не вычислять k, но разница мизерная. А на вопрос: "почему else if, а не else" - чтобы при передаче отрицательного индекса фукция ничего не выполняла.
Реализация не соответствует примеру на видео, потому что метод erase удаляет node по первому попавшемуся значению, а не по индексу node и ещё нету метода insert который тоже принимает индекс как аргумент
@@selfedu_rus а можно ссылку на видео? Курс ООП на Python? там много видео, в названиях вроде нигде не увидел упоминаний про списки.. а все просматривать в поисках нужной инфы - долго(
С++ подходит для демонстрации всех нюансов создания и работы с объектами в памяти компьютера, на мой взгляд, для этого лучше подойдёт язык ассемблера, а реализацию односвязного списка и стека на его основе можно создать на любом языке программирования.
@@alex6161 новички вообще ничего не понимают, ни в C++ ни тем более в языке ассемблера, который специфичен в зависимости от архитектуры платформы. А те кто понимают не смотрят такие видео на youtube. Я не поленился и посмотрел весь материал относящийся к с++ на этом канале и признаться сделал это с трудом и почти ничего из увиденного толком не запомнил и не понял зачем.
@@fil-os-of ну я вот новичок, решил golang изучить, но курса по структурам на go я не нашел на русском языке, так что вот смотрю это, и довольно понимаю (ровно то что говорят, эти примеры и синтаксис языка), тонкости языка в примерах не используются. Гарвардский курс тоже с примерами на с++, но там именно учат этому языку во всех подробностях, что мне не надо. А вот от слова ассемблер мне страшно.
@@alex6161 каждому своё, мне лично ничего не страшно. Просто в языке ассемблера ещё меньше абстракций и простые функции приходится описывать в рамках машинной логики. Инструментарий скудный, набор объектов не велик, вот и получается куча рутинного текста решающего простые задачи. Есть ли сложности, конечно, приходится читать документацию к платформе и к реализации языка.
Всё, что нужно знать про приведенный пример: main.cpp:70:5: error: expected unqualified-id before ‘for’ 70 | for (;node->next != tail; node = node->next); | ^~~ main.cpp:70:11: error: ‘node’ does not name a type; did you mean ‘Node’? 70 | for (;node->next != tail; node = node->next); | ^~~~ | Node main.cpp:70:31: error: ‘node’ does not name a type; did you mean ‘Node’? 70 | for (;node->next != tail; node = node->next); | ^~~~ | Node main.cpp:71:5: error: ‘node’ does not name a type; did you mean ‘Node’? 71 | node->next = NULL; | ^~~~ | Node main.cpp:72:5: error: expected unqualified-id before ‘delete’ 72 | delete tail; | ^~~~~~ main.cpp:73:5: error: ‘tail’ does not name a type 73 | tail = node; | ^~~~ main.cpp: In destructor ‘SinglyLinkedList::~SinglyLinkedList()’: main.cpp:32:30: error: ‘pop_front’ was not declared in this scope; did you mean ‘push_front’? 32 | while (head != NULL) pop_front(); | ^~~~~~~~~ | push_front main.cpp:34:25: warning: empty parentheses were disambiguated as a function declaration [-Wvexing-parse] 34 | double pop_front(){ | ^~ main.cpp:34:25: note: remove parentheses to default-initialize a variable 34 | double pop_front(){ | ^~ | -- main.cpp:34:25: note: or replace parentheses with braces to value-initialize a variable main.cpp:34:27: error: a function-definition is not allowed here before ‘{’ token 34 | double pop_front(){ | ^ main.cpp: In member function ‘double SinglyLinkedList::push_back(double)’: main.cpp:52:5: warning: no return statement in function returning non-void [-Wreturn-type] 52 | } | ^ main.cpp: In member function ‘double SinglyLinkedList::push_front(double)’: main.cpp:59:5: warning: no return statement in function returning non-void [-Wreturn-type] 59 | } | ^ main.cpp: In member function ‘double SinglyLinkedList::pop_back()’: main.cpp:62:27: error: return-statement with no value, in function returning ‘double’ [-fpermissive] 62 | if (tail == NULL) return; | ^~~~~~ main.cpp:66:13: error: return-statement with no value, in function returning ‘double’ [-fpermissive] 66 | return; | ^~~~~~ main.cpp: In member function ‘double SinglyLinkedList::insert(int, double)’: main.cpp:88:27: error: return-statement with no value, in function returning ‘double’ [-fpermissive] 88 | if (left == NULL) return; | ^~~~~~ main.cpp:91:9: error: ‘left’ does not name a type 91 | left->next = node; | ^~~~ main.cpp: In member function ‘int SinglyLinkedList::erase(int)’: main.cpp:97:20: error: return-statement with no value, in function returning ‘int’ [-fpermissive] 97 | if (k < 0) return; | ^~~~~~ main.cpp:99:13: error: ‘pop_front’ was not declared in this scope; did you mean ‘push_front’? 99 | pop_front(); | ^~~~~~~~~ | push_front main.cpp:100:13: error: return-statement with no value, in function returning ‘int’ [-fpermissive] 100 | return; | ^~~~~~ main.cpp:103:27: error: return-statement with no value, in function returning ‘int’ [-fpermissive] 103 | if (node == NULL) return; | ^~~~~~
Это точно С++ а то синтаксис несколько отличается . По ходу я заметил что программа пишется в графредакторе а не Визуал студио и врядли скомпилируется .
Спасибо огромное за такой ценный концентрат знаний!🏆🎁 Удивительно, что на незнакомом мне С++ до меня наконец-то дошло понимание связанных списков!
огромное спасибо за подробности и ваш подход. Видео о более правильном построении такого списка есть на ютубе и люди часами настраивают его с учетом всех принципов ООП, но получить первый уровень понимания как строить такие списки без высочайшего понимания C++ на таких роликах не выйдет.
А у вас достаточно маленьких знаний и желания
Ещё раз спасибо
Вот такой момент: сколько смотрел видео по тегам односвязный список, будь-то СимплКод или преподы из МФТИ, ничего годного найти не удалось до твоего канала. Урок реально помог! Спасибо!
Только один вопрос: что означает изначальное Node* внутри класса Node? Создание большого указателя, по которому может идти перемещение посредством this? Как называется этот элемент синтаксиса?
Спасибо! Node - это класс (тип данных), а Node *head - это объявление указателя типа Node. То есть, head - это обычная переменная-указатель внутри класса.
@@selfedu_rus благодарю за ответ
Ну явно тупенький
CodeBlog норм
ОГРОМНОЕ СПАСИБО! всё очень понятно и доходчиво!
З.ы. компилируется всё нормально Visual Studio Community 2022 Версия 17.7.5
Вот рабочий вариант:
#include
using namespace std;
// Making a node struct containing an int data and a pointer
// to next node
struct Node{
int data;
Node *next;
// Parameterised constructor with default argument
Node(int val=0) :data(val),next(nullptr){}
// Parameterise constructor
Node(int val, Node *tempNext):data(val),next(tempNext){}
};
class LinkedList{
// Head pointer
Node* head;
public:
// default constructor. Initializing head pointer
LinkedList():head(nullptr){}
// inserting elements (At start of the list)
void insert(int val){
// make a new node
Node* new_node = new Node(val);
// If list is empty, make the new node, the head
if (head == nullptr){
head = new_node;
}
// else, make the new_node the head and its next, the previous
// head
else{
new_node->next = head;
head = new_node;
}
}
// loop over the list. return true if element found
bool search(int val){
Node* temp = head;
while(temp != nullptr){
if (temp->data == val)
return true;
temp = temp->next;
}
return false;
}
void remove(int val){
Node* temp = head;
// If the head is to be deleted
if (temp != nullptr && temp->data == val){
head = temp->next;
delete temp;
return;
}
// Else loop over the list and search for the node to delete
else{
Node* curr = head;
while(temp != nullptr && temp->data != val){
// When node is found, delete the node and modify the pointers
curr = temp;
temp = temp->next;
}
// If values is not found in the linked list
if(!temp){
cout next;
delete temp;
}
}
void display()
{
Node* temp = head;
while(temp != nullptr){
cout data next;
}
cout
legend
Добрый день! Я конечно не знаком с C++, но примерно все уловил, но не понял почему когда вызывали метод insert в самом конце и указывая индекс 0 он вставлял значения после 1, а не перед?
Спасибо большое! Очень жаль, что нет кода на гитхабе
Хотелось бы пример с односвязным списком на Питоне увидеть, С++ не знаю от слова совсем
Поправьте, пожалуйста, если не прав: в методе Erase, в случае, если удалённый элемент node являлся tail, разве теперь tail не должен быть right, а не left?
Если мы удаляем последний элемент, то tail должен сдвигаться влево, т.к. справа ничего нет.
Вопрос автору! Не является ли излишеством в методе getAt() в условии цикла while вставлять проверку node? Ведь всё равно когда обход списка дойдёт до последнего элемента node->next станет NULL и цикл завершит свою работу. Или может логической необходимости в этой проверке нет, и она прописана для подстраховки?
Это привычка делать "основательные" проверки, не полагаясь на другие, т.к. они (другие) могут в будущем поменяться.
а чем отличается эта версия видео №9 от предыдущей?
упоминаю об std::forward_list
А как тогда вставлять элементы в начало такого списка с помощью метода insert, если при вставке по нулевому индексу вставляется на первый?
нужно переписать, чтобы индекс соответствовал вставляемому элементу (считайте это домашним заданием), а вообще вставку первого и последнего лучше выполнять методами push_front() и push_back() они оптимизированы под это
@@selfedu_rus понял спасибо!
Я так сделал:
if (k > 0)
{
Node* left = getAt(k - 1);
if (left == NULL) return;
Node* node = new Node(data);
node->next = left->next;
if (left->next == NULL) tail = node;
left->next = node;
}
else if (k == 0)
push_front(data);
Лучше сделать через switch case, чтобы два раза не вычислять k, но разница мизерная. А на вопрос: "почему else if, а не else" - чтобы при передаче отрицательного индекса фукция ничего не выполняла.
Автор пише код в Visual Studio. Я повторяю код. в CLion, всё работает.
Реализация на python, может кому нужно
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
def is_empty(self):
return self.head is None
def push_back(self, data):
new_node = Node(data)
if self.is_empty():
self.head = self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
def push_front(self, data):
new_node = Node(data)
if self.is_empty():
self.head = self.tail = new_node
else:
new_node.next = self.head
self.head = new_node
def erase(self, data):
if self.is_empty():
return
if self.head.data == data:
self.head = self.head.next
return
current = self.head
while current.next:
if current.next.data == data:
print(current.next.next)
current.next = current.next.next
return
current = current.next
def search(self, data):
current = self.head
while current:
if current.data == data:
return True
current = current.next
return False
def print_list(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
linked_list = LinkedList()
linked_list.push_back(12)
linked_list.push_back(103)
linked_list.push_back(11)
linked_list.push_back(43)
linked_list.push_back(12)
linked_list.push_back(23)
print(linked_list.print_list())
Реализация не соответствует примеру на видео, потому что метод erase удаляет node по первому попавшемуся значению, а не по индексу node и ещё нету метода insert который тоже принимает индекс как аргумент
почему мы для pop_font написали ~OneLinkedList() {
while (head!= NULL) pop_front();
} а для pop_back не написали что то подобное на цикл
~OneLinkedList(){...} Это деструктор класса. Он не имеет отношение к pop_front. Просто в нем использовали pop_front можно было и pop_back использовать
А что делать, если у меня данные не помещаются в double?
Есть же вроде double double
коллега, как пофиксил?
@@user-cq4kq3nc4u максимальный размер оперируемого блока можно определить глобально в соответствии с архитектурой аппаратной платформы
В моём компиляторе не работает void
странно, старый значит? раньше его не было, но уже с ANSI C появился
Зачем в классе дважды указывается public?
так принято, первый - для переменных, второй - для методов
По мне так это дело стиля и вкуса. Если честно, я не знаю принято ли так где-то, но так описание класса выглядит более структурированным.
14:50 разве это не логическое "и"?
цикл завершится, если n != k или пока не дойдем до конца списка (говорится о завершении цикла, а не об условии его работы)
А что, без классов создать односвязный список нельзя?
почему бы и не с классами?
можно через struct
А почему на пайтон не показали?)
в курсе ООП было и на С++ более подробно выходит
@@selfedu_rus надо чекнуть, спасибо
@@selfedu_rus а можно ссылку на видео? Курс ООП на Python? там много видео, в названиях вроде нигде не увидел упоминаний про списки.. а все просматривать в поисках нужной инфы - долго(
@@romangrigorovich5205 В этом курсе stepik.org/course/116336/
@@selfedu_rus в виде задачи в курсе? я думал где-то в видео объяснение было.
ну тогда ладно
С++ подходит для демонстрации всех нюансов создания и работы с объектами в памяти компьютера, на мой взгляд, для этого лучше подойдёт язык ассемблера, а реализацию односвязного списка и стека на его основе можно создать на любом языке программирования.
C++ так или иначе понимают все, и он ближе к ассемблеру чем прочие языки. Примеры на ассемблере будут непонятны широкому кругу новичков.
@@alex6161 новички вообще ничего не понимают, ни в C++ ни тем более в языке ассемблера, который специфичен в зависимости от архитектуры платформы. А те кто понимают не смотрят такие видео на youtube. Я не поленился и посмотрел весь материал относящийся к с++ на этом канале и признаться сделал это с трудом и почти ничего из увиденного толком не запомнил и не понял зачем.
@@fil-os-of ну я вот новичок, решил golang изучить, но курса по структурам на go я не нашел на русском языке, так что вот смотрю это, и довольно понимаю (ровно то что говорят, эти примеры и синтаксис языка), тонкости языка в примерах не используются. Гарвардский курс тоже с примерами на с++, но там именно учат этому языку во всех подробностях, что мне не надо. А вот от слова ассемблер мне страшно.
@@alex6161 каждому своё, мне лично ничего не страшно. Просто в языке ассемблера ещё меньше абстракций и простые функции приходится описывать в рамках машинной логики. Инструментарий скудный, набор объектов не велик, вот и получается куча рутинного текста решающего простые задачи. Есть ли сложности, конечно, приходится читать документацию к платформе и к реализации языка.
Всё, что нужно знать про приведенный пример:
main.cpp:70:5: error: expected unqualified-id before ‘for’
70 | for (;node->next != tail; node = node->next);
| ^~~
main.cpp:70:11: error: ‘node’ does not name a type; did you mean ‘Node’?
70 | for (;node->next != tail; node = node->next);
| ^~~~
| Node
main.cpp:70:31: error: ‘node’ does not name a type; did you mean ‘Node’?
70 | for (;node->next != tail; node = node->next);
| ^~~~
| Node
main.cpp:71:5: error: ‘node’ does not name a type; did you mean ‘Node’?
71 | node->next = NULL;
| ^~~~
| Node
main.cpp:72:5: error: expected unqualified-id before ‘delete’
72 | delete tail;
| ^~~~~~
main.cpp:73:5: error: ‘tail’ does not name a type
73 | tail = node;
| ^~~~
main.cpp: In destructor ‘SinglyLinkedList::~SinglyLinkedList()’:
main.cpp:32:30: error: ‘pop_front’ was not declared in this scope; did you mean ‘push_front’?
32 | while (head != NULL) pop_front();
| ^~~~~~~~~
| push_front
main.cpp:34:25: warning: empty parentheses were disambiguated as a function declaration [-Wvexing-parse]
34 | double pop_front(){
| ^~
main.cpp:34:25: note: remove parentheses to default-initialize a variable
34 | double pop_front(){
| ^~
| --
main.cpp:34:25: note: or replace parentheses with braces to value-initialize a variable
main.cpp:34:27: error: a function-definition is not allowed here before ‘{’ token
34 | double pop_front(){
| ^
main.cpp: In member function ‘double SinglyLinkedList::push_back(double)’:
main.cpp:52:5: warning: no return statement in function returning non-void [-Wreturn-type]
52 | }
| ^
main.cpp: In member function ‘double SinglyLinkedList::push_front(double)’:
main.cpp:59:5: warning: no return statement in function returning non-void [-Wreturn-type]
59 | }
| ^
main.cpp: In member function ‘double SinglyLinkedList::pop_back()’:
main.cpp:62:27: error: return-statement with no value, in function returning ‘double’ [-fpermissive]
62 | if (tail == NULL) return;
| ^~~~~~
main.cpp:66:13: error: return-statement with no value, in function returning ‘double’ [-fpermissive]
66 | return;
| ^~~~~~
main.cpp: In member function ‘double SinglyLinkedList::insert(int, double)’:
main.cpp:88:27: error: return-statement with no value, in function returning ‘double’ [-fpermissive]
88 | if (left == NULL) return;
| ^~~~~~
main.cpp:91:9: error: ‘left’ does not name a type
91 | left->next = node;
| ^~~~
main.cpp: In member function ‘int SinglyLinkedList::erase(int)’:
main.cpp:97:20: error: return-statement with no value, in function returning ‘int’ [-fpermissive]
97 | if (k < 0) return;
| ^~~~~~
main.cpp:99:13: error: ‘pop_front’ was not declared in this scope; did you mean ‘push_front’?
99 | pop_front();
| ^~~~~~~~~
| push_front
main.cpp:100:13: error: return-statement with no value, in function returning ‘int’ [-fpermissive]
100 | return;
| ^~~~~~
main.cpp:103:27: error: return-statement with no value, in function returning ‘int’ [-fpermissive]
103 | if (node == NULL) return;
| ^~~~~~
Это точно С++ а то синтаксис несколько отличается . По ходу я заметил что программа пишется в графредакторе а не Визуал студио и врядли скомпилируется .
Всё ооочень быстро, скомкано, ничего не понятно