Problem with Search in a link list
I would like to write a function which search an item in a sorted link list, and return the item before the item I would like to search whether the searched item is found in the list, so basically I am looking for the right place to insert an item. However, i can't deal with the problem if my searched item is in fact the smaller than the first item in the list or greater than the last element in the list. So how should I modify my code please?
NodePtr find(NodePtr hdList, int tofind)
{
NodePtr temp = hdList, lastPtr = hdList;
while ((temp->data < tofind) && (temp != NULL))
{
lastPtr=temp;
temp = temp->next;
}
return NodePtr(lastPtr);
}
NodePtr find(NodePtr hdList, int tofind)
{
NodePtr temp = hdList, lastPtr = hdList;
while ((temp->data < tofind) && (temp != NULL))
{
lastPtr=temp;
temp = temp->next;
}
return NodePtr(lastPtr);
}
NodePtr find(NodePtr hdList, int tofind)
{
NodePtr temp = hdList, lastPtr = NULL;
while ((temp->data < tofind) && (temp != NULL))
{
lastPtr=temp;
temp = temp->next;
}
return NodePtr(lastPtr);
}
if lastPtr==NULL then the searched item is smaller than the first item
{
NodePtr temp = hdList, lastPtr = NULL;
while ((temp->data < tofind) && (temp != NULL))
{
lastPtr=temp;
temp = temp->next;
}
return NodePtr(lastPtr);
}
if lastPtr==NULL then the searched item is smaller than the first item
the head of the list???
I gun get it....because if the searched item is in the middle of the list, then I want to have the node before it, so when I call my insert or delete, i can input this node address(which is pointing to my searched item) and the item, then for insert, i just simply link this node to my new item, then my new item point back to where it should link. And for delete, i just simply skip my searched item and link to next item.
I gun get it....because if the searched item is in the middle of the list, then I want to have the node before it, so when I call my insert or delete, i can input this node address(which is pointing to my searched item) and the item, then for insert, i just simply link this node to my new item, then my new item point back to where it should link. And for delete, i just simply skip my searched item and link to next item.
to grellen
however, I still have problem if my searched item is indeed greater than all the numbers in the list, then my function crashes, it can not return the last node in the list.
however, I still have problem if my searched item is indeed greater than all the numbers in the list, then my function crashes, it can not return the last node in the list.
if the searched item greater than the last element in the list,it still work by judging if (lastPtr->next==NULL)...
it does not work, the problem is indeed in the while loop, because let say my last item in the list is 10, and the one before it is 9, and I am looking for 20, so when it gets into the while loop, before it stoppes, lastPtr equals 9, and temp equals to 10, but we expect the number 10, as I am looking for the right position to insert 20 into my list.
I think to do what you want to do you need to return a NodePtr* (ie, node pointer pointer).
You return &head if the int to find goes at the beginning;
You return &last->next if the int to find goes at the end;
You return &prev->next if prev points to the node before where to insert.
This is a common way to eliminate the special cases in linked list code.
You return &head if the int to find goes at the beginning;
You return &last->next if the int to find goes at the end;
You return &prev->next if prev points to the node before where to insert.
This is a common way to eliminate the special cases in linked list code.
Topic archived. No new replies allowed.