поиск узла в односвязном списке

Question

поиск узла в односвязном списке

У меня есть односвязный список, состоящий из узлов со следующей структурой:

struct date
{
int day, month, year;
};
struct Node
{
string item;
date Exp;
int count;
Node *link;
};
typedef Node* NodePtr;

Когда я ищу дату истечения срока действия, все другие узлы отображаются при поиске, но не первый узел. Это происходит, когда я меняю порядок узлов тоже. Это простая ошибка?

Вот функция, которую я использую для поиска узла:

NodePtr search_date(NodePtr head, int month, int day, int year)
{
// Point to the head node
NodePtr here = head;

// If the list is empty nothing to search
if (here == NULL)
return NULL;

// Search for the item
else{
//while you have still items and you haven't found the target yet
while (here-> Exp.day != day &&
here-> Exp.month != month &&
here->Exp.year != year &&
here->link != NULL)
here = here->link;

// Found the target, return the pointer at that location
if (here-> Exp.month == month &&
here-> Exp.day == day &&
here-> Exp.year == year)
return here;

// Search unsuccessful, return Null
else
return NULL;
}
}

-1

c++linked-list singly-linked-list

Решение

Другие решения

@LiHO в принципе прав: ваша логика сравнения ошибочна.

Хороший способ исправить это — сделать оператор сравнения для date

struct date
{
int day, month, year;

bool operator==(const date &lhs, const date &rhs)
{
return (rhs.day == lhs.day) && (rhs.month == lhs.month) (rhs.year == lhs.year);
}
};

Тогда ваш цикл упрощается до

NodePtr search_date(NodePtr head, const date &wantedDate)
{
for (NodePtr p == head; p != NULL; p = p->link)
if (p.Exp == wantedDate)
return p;

return NULL;
}

Предупреждение. непроверенный 😉

1

Источник

Accepted Answer

Проблема в состоянии вашего while заявление. Допустим, вы ищете дату 03/21/2013 и первый элемент, который вы «осмотрите», будет иметь дату 04/21/2013, Дни не равны, поэтому условие будет оценено как false и даже если есть запись с датой, которую вы ищете, вы никогда не достигнете ее.

Эта функция может выглядеть так:

NodePtr search_date(NodePtr node, int month, int day, int year)
{
// while there is some node still:
while (node)
{
// if we found the right node, return it:
if (node->Exp.month == month &&
node->Exp.day == day &&
node->Exp.year == year)
return node;

// move to the next node:
node = node->link;
}

// we haven't found it:
return NULL;
}

1