none
problem in linked list c++

    Question

  • im working with linked list, where i should search the book name in the list by author name.

    the problem is when i key in author name, compiler point me here:

    // xstring internal header (from <string>)

    int compare(const _Myt& _Right) const
            {    // compare [0, _Mysize) with _Right
            return (compare(0, this->_Mysize, _Right._Myptr(), _Right.size()));
            }

     

    is there any slightly change should i do?

     

    void book::search(string target)
    {
        bool data=true;

       
            pCurr = pHead;

            int i =1 ;

            while (i<=numItem)
            {
                pPrev=pCurr;
                pCurr=pCurr->link;

                    if(pCurr->Author == target )
                    {
                        data=true;
                       
                       
                    }
                    else
                    {
                        data=false;
                    }
               
               
                if (data=true)
               

                cout<<pCurr->Books<<endl<<endl;
               

                i++;
            }
           
       
    }

    int book::NumberOfItem()
    {

          return numItem;

    }

     

    Tuesday, March 29, 2011 8:47 PM

Answers

  • StOPpER's wrote:
    >
    >i still cant understand wht u mean...actually i used pCurr as pointer to trace current node
     
    Yes, but you have a separate variable (numItem) that supposedly tracks the
    number of items in the list.  That's just an opportunity for errors,
    because it's so easy for that count to get out of sync.  You have to
    remember to bump it up or down every time you add or remove from the list.
     
    That's why you USUALLY traverse a list without using a count:
     
        NodeType pCurr = pHead;
        while( pCurr )
        {
            // Do something with pCurr
            pCurr = pCurr->link;
        }
     
    Why do you have pCurr and pPrev in the "book" class?  Usually, you would
    only have the Head pointer there.  A "current" pointer is usually a
    temporary, used and then discarded.  You don't need that as a class member.
    pPrev also doesn't make sense.  If you want a doubly-linked list, then you
    need two pointers in the NodeType class, not in the "book" class.
    --
    Tim Roberts, timr@probo.com
    Providenza & Boekelheide, Inc.
     

    Tim Roberts, DDK MVP Providenza & Boekelheide, Inc.
    • Marked as answer by StOPpER's Monday, April 04, 2011 10:05 AM
    Wednesday, March 30, 2011 6:19 AM
  • Tim Roberts [MVP] wrote:

    pPrev also doesn't make sense. If you want a doubly-linked list, then  you
    need two pointers in the NodeType class, not in the "book" class.

    When traversing a singly linked list, it's often necessary to keep track  of two neighboring nodes using two pointers that are advanced in sync,  e.g. to insert a new node in between once the correct spot is located.  Perhaps something like this is what's going on here.


    Igor Tandetnik

    • Marked as answer by StOPpER's Monday, April 04, 2011 10:05 AM
    Wednesday, March 30, 2011 11:58 AM
  • Hello StOPpER,

    I write a demo, you can refer to it.

    #include <iostream>

    #include <string>

    #include <cstdlib>

     

    using namespace std;

    class NodeType

    {

    public:

           string Author;

           NodeType *link;

    };

     

    class book

    {

    public:

           book();

           ~book();

           NodeType* Creatlist();

           void Traverse(NodeType *head, string);

    };

    void  book:: Traverse(NodeType *head, string target)

    {

           NodeType *pCurr=head;

           while (pCurr != NULL)

           {

                  if(pCurr->Author == target)

                  {

                         cout<<pCurr->Author<<endl;

                         cout<<"Get it"<<endl;

                         break;

                  }

                  else

                  {

                         pCurr = pCurr->link;

                  }

           }

     

    }

     

    NodeType*  book::Creatlist()

    {

           int n; // node list number

           cout<<"please input node total"<<endl;

           cin>>n;

     

           NodeType *head = NULL;

           head   = new NodeType;

     

           cout<<"please input Author's name:"<<endl;

           cin>> head->Author;

          

           head->link = NULL;

     

           for(int i= n-1; i>=1; i--)

           {

                  NodeType * q = NULL;

                  q = new NodeType;

                  cout<<"please input Author's name:"<<endl;

                  cin>> q->Author;

                  q->link = head;

                  head =q;

           }

     

           return head;

    }

    int main()

    {

           book *p = NULL;

           NodeType* q = p->Creatlist();

           p->Traverse(q, "abc");

           system("pause");    

           return 0;

    }

     

    I hope it's helpful to you.

     

    Best regard,

    Peter Yu


    Pet Yu [MSFT]
    MSDN Community Support | Feedback to us
    Get or Request Code Sample from Microsoft
    Please remember to mark the replies as answers if they help and unmark them if they provide no help.

    • Marked as answer by StOPpER's Monday, April 04, 2011 10:05 AM
    Thursday, March 31, 2011 3:26 AM

All replies

  • What does the debugger say the value of pCurr is?  I suspect it is either NULL or pointing at invalid memory.  Traditionally, in a linked list the final element's next (link in your case) pointer points to NULL, and any time you traverse the list you must check each iteration for the end of list case.

    In your code it looks like you are relying on a count variable, which is somehow out of sync with your list.

    A couple of other things I would point out -- There is probably not a good reason to keep pCurr as a member of your class.  It really ought to be a local variable.  pCurr as a member limits how your class functions can call each other.

    Also this line:    if (data=true) probably doesn't do what you want it to.  It will assign the value true to the variable data, then always execute the cout line.  You might try if (data == true).

     

    Tuesday, March 29, 2011 10:24 PM
  • i still cant understand wht u mean...actually i used pCurr as pointer to trace current node

     here is my class definition:

    class book
    {
    private:

        class NodeType
          {
          public:
                 string Author;
                 double Price;
                 string Books;
                NodeType *link;
          };
          NodeType *pHead;
         NodeType *pCurr;
         NodeType *pPrev;
          int numItem;
       

    public:

          book();
          ~book();
          void AddToFront();
          void DeleteFront();
          void DeleteMiddle();
         void Traverse(string );
          void AddToMiddle();
          void printData();
          void printAuthorData(int &);
          int NumberOfItem();




    };

    Wednesday, March 30, 2011 3:29 AM
  • StOPpER's wrote:
    >
    >i still cant understand wht u mean...actually i used pCurr as pointer to trace current node
     
    Yes, but you have a separate variable (numItem) that supposedly tracks the
    number of items in the list.  That's just an opportunity for errors,
    because it's so easy for that count to get out of sync.  You have to
    remember to bump it up or down every time you add or remove from the list.
     
    That's why you USUALLY traverse a list without using a count:
     
        NodeType pCurr = pHead;
        while( pCurr )
        {
            // Do something with pCurr
            pCurr = pCurr->link;
        }
     
    Why do you have pCurr and pPrev in the "book" class?  Usually, you would
    only have the Head pointer there.  A "current" pointer is usually a
    temporary, used and then discarded.  You don't need that as a class member.
    pPrev also doesn't make sense.  If you want a doubly-linked list, then you
    need two pointers in the NodeType class, not in the "book" class.
    --
    Tim Roberts, timr@probo.com
    Providenza & Boekelheide, Inc.
     

    Tim Roberts, DDK MVP Providenza & Boekelheide, Inc.
    • Marked as answer by StOPpER's Monday, April 04, 2011 10:05 AM
    Wednesday, March 30, 2011 6:19 AM
  • Tim Roberts [MVP] wrote:

    pPrev also doesn't make sense. If you want a doubly-linked list, then  you
    need two pointers in the NodeType class, not in the "book" class.

    When traversing a singly linked list, it's often necessary to keep track  of two neighboring nodes using two pointers that are advanced in sync,  e.g. to insert a new node in between once the correct spot is located.  Perhaps something like this is what's going on here.


    Igor Tandetnik

    • Marked as answer by StOPpER's Monday, April 04, 2011 10:05 AM
    Wednesday, March 30, 2011 11:58 AM
  • Hello StOPpER,

    I write a demo, you can refer to it.

    #include <iostream>

    #include <string>

    #include <cstdlib>

     

    using namespace std;

    class NodeType

    {

    public:

           string Author;

           NodeType *link;

    };

     

    class book

    {

    public:

           book();

           ~book();

           NodeType* Creatlist();

           void Traverse(NodeType *head, string);

    };

    void  book:: Traverse(NodeType *head, string target)

    {

           NodeType *pCurr=head;

           while (pCurr != NULL)

           {

                  if(pCurr->Author == target)

                  {

                         cout<<pCurr->Author<<endl;

                         cout<<"Get it"<<endl;

                         break;

                  }

                  else

                  {

                         pCurr = pCurr->link;

                  }

           }

     

    }

     

    NodeType*  book::Creatlist()

    {

           int n; // node list number

           cout<<"please input node total"<<endl;

           cin>>n;

     

           NodeType *head = NULL;

           head   = new NodeType;

     

           cout<<"please input Author's name:"<<endl;

           cin>> head->Author;

          

           head->link = NULL;

     

           for(int i= n-1; i>=1; i--)

           {

                  NodeType * q = NULL;

                  q = new NodeType;

                  cout<<"please input Author's name:"<<endl;

                  cin>> q->Author;

                  q->link = head;

                  head =q;

           }

     

           return head;

    }

    int main()

    {

           book *p = NULL;

           NodeType* q = p->Creatlist();

           p->Traverse(q, "abc");

           system("pause");    

           return 0;

    }

     

    I hope it's helpful to you.

     

    Best regard,

    Peter Yu


    Pet Yu [MSFT]
    MSDN Community Support | Feedback to us
    Get or Request Code Sample from Microsoft
    Please remember to mark the replies as answers if they help and unmark them if they provide no help.

    • Marked as answer by StOPpER's Monday, April 04, 2011 10:05 AM
    Thursday, March 31, 2011 3:26 AM
  • thanks all,

    finally i understand and solved this problem...

     

     

    Monday, April 04, 2011 10:06 AM