Найдите такие же элементы в C-структуре
Мне нужно написать функцию, которая будет добавлять элементы в C-структуру, но она не может добавить тот же элемент. Пример:
Вход:
1 2 1 3
Вывод:
ADDED 1
ADDED 2
NOT ADD 1
ADD 3
Элементы берутся из массива, вот фрагмент кода, который использует функцию, которую мне нужно написать:
int tab[] = {1,4,1,3,5};
Node* head = 0;
for (size_t i = 0, e = std::size(tab); i != e; ++i) {
bool b = add(head,tab[i]);
cout << tab[i] << (b ? " " : " NOT ")
<< "added" << endl;
}
C-struct Node выглядит так:
struct Node {
int data;
Node* next;
};
Вот что я написал, но он добавляет все элементы из массива. Я не могу изменить цикл, только функция add:
bool add(Node*& head, int data){
Node *n = new Node;
n->data = data;
n->next = 0;
if (!head)
head = n;
else{
Node *tmp = head;
while(tmp->next)
tmp = tmp->next;
tmp->next = n;
}
};
Я не знаю, как перебирать список, чтобы найти тот же элемент
В чем именно заключается ваш вопрос? В вашем вопросе нет вопросов. Примечание: нет необходимости в if в add, вы можете использовать while(head) head = head->next;.
@Mrfk Вы уже просматриваете список в блоке else. В блоке while просто проверьте значение tmp->data и, если оно совпадает с data, прервите операцию.
Это простой цикл, Node *tmp = head; while (tmp) { if (tmp->data == data) { found it } tmp = tmp->next; }. Кажется, он проще, чем код, который вы уже написали, но я думаю, что указатели сложны.
Спасибо за примечание, я это изменю. Мой вопрос: как перебирать элементы узла, чтобы определить, есть ли те же элементы
Вам не хватает возвращаемых значений add. Включите предупреждения все для вашего компилятора, это поможет вам находить такие ошибки.
@WernerHenze Вы уверены?
Спасибо, ребята, я знаю, что теперь делать. Я перепишу функцию, чтобы она имела больше смысла
@Mrfk предупреждение, не поймите неправильный ответ, лол
Ответы 3
в настоящее время вы просто добавляете элемент, не глядя, присутствует он уже или нет
Определение может быть примерно таким:
bool add(Node*& head, int data){
if (!head) {
head = new Node;
n->data = data;
n->next = 0;
return true;
}
Node *tmp = head;
while (tmp->next) {
if (tmp->data == data)
return false;
tmp = tmp->next;
}
if (tmp->data == data)
return false;
tmp->next = new Node;
tmp->next->data = data;
tmp->next->next = 0;
return true;
}
Я рекомендую вам добавить конструктор, чтобы вам не приходилось устанавливать поля data и next каждый раз после создания нового экземпляра.
Пример
Node::Node(int d) : next(0), data(d) {
}
// add should be a static method of Node, to be able to access next and data while they are private
bool add(Node*& head, int data){
if (!head) {
head = new Node(data);
return true;
}
Node *tmp = head;
while (tmp->next) {
if (tmp->data == data)
return false;
tmp = tmp->next;
}
if (tmp->data == data)
return false;
tmp->next = new Node(data);
return true;
}
Спасибо за ваш вклад, но нет, я не могу добавить те же данные
Я предположил, что важен только результат, я отредактировал свой ответ, чтобы не добавлять, если он уже присутствует
Я не сторонник отрицательных отзывов, но должен сказать: эта функция add делает слишком много вещей. Поскольку мы занимаемся цитированием: должны быть Node* node_new(int), bool node_isNil(Node*), Node* node_last(Node*) и bool node_find(int).
Должен быть while (tmp), а не while (tmp->next), поскольку он не найдет последний элемент в списке.
@john нет, пока ищите последний элемент, чтобы добавить новый после него, с while(tmp) как вы можете добавить новый элемент в конец списка?
@bruno Вы правы, вы не можете добавить новый элемент с помощью цикла, такого как while(tmp), но вы не можете выполнить поиск по всему списку с помощью цикла, такого как while(tmp->next). Эти две операции разные.
@Bruno Я взял ваш код, исправил ошибки компиляции (необъявленная переменная n) изменил вход на int tab[]= {1,1};, на выходе был 1 added 1 added
о да, когда я изменил определение, я удалил тест через некоторое время, я снова ввел его
@bruno, хорошо, голос "против" удален, ваш лучший ответ
@PaulSanders, что ты имеешь в виду? new Node(..) возвращает новый экземпляр узла
@PaulSanders Я не понимаю, мой конструктор просто Node::Node(int d) : next(0), data(d) {}
@PaulSanders Я добавил новую строку между '{' и '}' на тот случай, если он был менее читабельным, когда все были в одной строке
Вот моя попытка. Найдите существующие данные первый, затем добавьте, если они отсутствуют (без изменений из существующего кода)
bool add(Node*& head, int data) {
Node *tmp = head;
while (tmp) {
if (tmp->data == data)
return false; // data already present
tmp = tmp->next;
}
Node *n = new Node;
n->data = data;
n->next = 0;
if (!head) {
head = n;
}
else {
Node *tmp = head;
while(tmp->next)
tmp = tmp->next;
tmp->next = n;
}
return true; // data added
}
Какая плохая идея - просмотреть список 2 раза!
@bruno, очень верно, я оставлю это улучшение OP
Я сделал что-то подобное, и это работает с данными, которые у меня есть. Я полагаю, это работает в целом
bool add(Node*& head, int data){
Node *n = new Node;
n->data = data;
n->next = 0;
if (!head)
head = n;
else{
Node *tmp = head;
while(tmp->next){
if (tmp->data == data)
return false;
else
tmp = tmp->next;
}
tmp->next = n;
}
};
Он без необходимости выделяет узел, даже если он не будет использоваться.
Верно то, что плохо. Спасибо, что заметили это
Он также не находит равного элемента, когда он последний элемент в списке.
вы делаете утечку памяти
Что вам нужно сделать, так это изменить свой код
addтак, чтобы если сначала искать элемент в списке, используя цикл, и добавлять его только в том случае, если он его не находит. Это кажется очевидным, на какой части вы застряли?