Problem with linked list

This is a discussion on Problem with linked list within the C++ Programming forums, part of the General Programming Boards category; Hello, I am currently writing a program that reads in an index of words and searches through a large text ...

  1. #1
    Registered User
    Join Date
    Dec 2004
    Posts
    9

    Problem with linked list

    Hello,

    I am currently writing a program that reads in an index of words and searches through a large text file for every instance of that word. I have the tokenize and input working correctly, but I am currently having problems getting my linked list which will consist of the pages it is on to work correctly. I think what its doing is only showing me the last node.
    Here are my structures:
    Code:
    typedef struct stag 
    {	
    	int pgno ; //page numbers 
    	struct stag *next ; //  pointer to next page No
    
    }NODE;
      
    typedef struct 
    { 
    	string word; 
    	NODE *link ;// pointer to linked list of pgno
    }
    Here is my portion of code for the linked list:
    Code:
    if(bin >= 0)//bin is the result of my binsearch
    {
            p = new(NODE);
    	p->next = NULL;
    	p->pgno = pages;//pgno is page number
    	index.awn[bin].link = p;
    }
    Any advice would be appreciated.

    Thanks.

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,325
    You need to add p to the list pointed to by link. I'm assuming link is meant to be the head of the list of nodes. You need to either walk down the list and add p to the point where you reach NULL, or point p->next to link and then make p the new value for link.

  3. #3
    Registered User
    Join Date
    Dec 2004
    Posts
    9
    Alright, I will try that.

  4. #4
    Registered User
    Join Date
    Dec 2004
    Posts
    9
    Thanks for the help, my list works now.

    Just one last question, id like to make it so that it doesnt add duplicates to the linked list, but have ran into a roadblock. This is what I was trying:

    Code:
    if(index.awn[bin].link->pgno != p->next->pgno)
    		p->pgno = pages;

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    847
    If your list is sorted then you can check the item you are about the add against the last item in the list before adding it, otherwise you'll need to search the entire list before adding each item.

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,325
    To not have a duplicate you have to search the whole list (a list is probably not the most efficient choice for this, but at this point I wouldn't worry about it until your code is working).

    I would have a variable set to false for whether a match was found. Then I'd loop through the list and if I got to the end without finding a match, I'd add the node to the list, otherwise I'd delete the node and not add it to the list. A slightly better algorithm would be to keep the list in sorted order. If you did that, you would walk down the list until you reached the end or until you reached a node with a higher page number, and then insert the node there. That way you don't have to go through the whole list, plus it will be sorted for you when you output it later.

  7. #7
    Registered User
    Join Date
    Dec 2004
    Posts
    9
    Thank you very much for your help. Ive got it all working now and am happy with the results.

    Once again, I appreciate the help.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 06:16 PM
  2. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  3. Replies: 6
    Last Post: 03-02-2005, 01:45 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21