Linked List OverWritting

This is a discussion on Linked List OverWritting within the C Programming forums, part of the General Programming Boards category; when trying to insert into my linked list(doing so at the top) it seems to overwrite all data there, yet ...

  1. #1
    Registered User
    Join Date
    Jan 2003
    Posts
    36

    Linked List OverWritting

    when trying to insert into my linked list(doing so at the top) it seems to overwrite all data there, yet I declare to different node's prior to inserting.

    There should be about 30 objects in the node, but no matter what I've tried it only seems the last object exists.

    Another question: I've been reading posts about Linked Lists on the board, and was wondering if I should make listTop a pointer to a node, rather then the actual node? It seems both ways have been done.

    Code:
    struct NODE
    {
    	char word[WORDSIZE];
    	struct NODE *next;
    };
    
    struct LIST
    {
    	struct NODE listTop;
    };
    
    void insert(char string[])
    {
    	int hashValue=0;
    
    	struct NODE newTop;
    	struct NODE oldTop;
    
    	hashValue=hash(string);	//gets the space in the array to insert word
    
    //this is where I note the 30 supposed objects
    if(hashValue==188)
    printf("%s",string);
    
    //-----------------------------------------------	
    	
    //puts the top into this node
    	oldTop=table[hashValue].listTop;
    
    //copy the string into the newTop
    	strcpy(newTop.word,string);
    
    //points to where oldTop is
    	newTop.next=&oldTop;
    
    //now declares the listTop should be the newTop
    	table[hashValue].listTop=newTop;		//puts the node at the top of list
    
    //-----------------------------------------------*/
    
    
    }

  2. #2
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    It looks like you are updating the top or the head pointer when you create a node.. You need to keep a global pointer (head) to keep track of the head or the top..

  3. #3
    Registered User
    Join Date
    Jan 2003
    Posts
    36
    Im not really sure what you mean.

    table[hashValue].listTop

    is the top of the list

    I take it as that is being moved into oldTop(along with the pointers it contatins)

    so that is the global head(although not global because part of array)

    are you suggesting I make it a pointer to a head? instead of the actual data?

  4. #4
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,386
    The problem is that you have no pointer to the tail. You only put objects on top. Those objects on top have no pointer to the objects below them. So from the top, you cannot go below.

  5. #5
    Registered User
    Join Date
    Jan 2003
    Posts
    36
    A pointer to the tail isnt required for a linked list(I've never programmed in C before, but learned lots about LL in java programming).

    The top has a pointer to the data below it, it's defined in a struct NODE and listTop is a node. So it will automatically have a pointer to the next object(although I didnt post that part, its set to null to start).

    So when inserting, all you have to do is redirect linkTop to the new data, and set the new node to link to the old top.

    I think my problem is linkTop should be a pointer, but my theory is correct as far as profs have told us that in all courses, and thats how we learned to insert(by not having a tail, this LL is just a stack without stack uses).

  6. #6
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,386
    A pointer to the tail isn't always required. But in your situation a pointer to the tail seems required to me, because, the next-pointer, points to the node at top of the current node.

    You have this situation:

    {listTop} <- {node1.next} <- {node2.next} <- {node3.next}

    You only know listTop, is that correct? Now node1.next points to listTop, but you have no possibility to get from listTop to node1. To solve this problem, you would have to

    1. add a new pointer in the nodes pointing to the previous node.

    or

    2. introduce a pointer pointing to the tail.

  7. #7
    Registered User
    Join Date
    Jan 2003
    Posts
    36
    We seem to be interpreting each other backwards.

    My list is meant like this

    ListTop ->node -> node

    and when inserting, it will be the new listTop
    so a new node would be:

    ListTop(newnode)->node(old ListTop)->node->node

  8. #8
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    >>newTop.next=&oldTop;
    Here you are putting the address of a local variable into the .next element, which I expect isn't what you mean to do. It will go out of scope when you leave the function.


    Where is you dynamic memory allocation?

    Also, string is a reserved name, so you shouldn't be using it.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  9. #9
    Registered User
    Join Date
    Jan 2003
    Posts
    36
    okay - bad programming style with using the variable "string"

    Since Next is a pointer, I want it to point at the old top, so I set the node.next to the oldtop address so it knows where to go.

    Why would it be losing it when going out of function?

    Dynamic Memory Allocation? You mean allocating everything? Right now I have problems using malloc, constantly getting errors so I'm trying to solve this problem before moving onto the next one.

  10. #10
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    The variable oldtop is local to the function insert(). If you take its address (by using &oldtop) and then try and reference it when you're outside of the insert() function, or even if you come back into it, you're doing wrong.

    To make a new node you should really be malloc()'ing one.

    Code:
    struct NODE *newitem;
    newitem = malloc(sizeof(*newitem));
    Now, the memory pointed to by newitem is going to live as long as the program runs, or until you free() it. In other words, you can leave the insert() function and still reference it.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  11. #11
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,386
    Okay I see now, I was wrong.

    These two:

    struct NODE newTop;
    struct NODE oldTop;

    Are local variables. As Hammer said, you'll lose them when you exit the function. So what you need to do is allocate memory for a new node, using malloc() and then add that node to the list. Each time you want to add a new node, you have to allocate new memory for that node.

    How do you use malloc? It should be something like this:

    struct NODE *newTop;
    newTop = malloc (sizeof (struct NODE));

    After malloc() you need to perform a check. If newTop is NULL, then malloc could not allocate memory. If newTop is not NULL, memory is allocated and you can use your new node.

  12. #12
    Registered User
    Join Date
    Jan 2003
    Posts
    36
    okay, I've tried to do that what I can, although now instead of only getting the one object, I get that same object looping

    Code:
    void insert(char string[])
    {
    	int hashValue=0;
    
    //printf("%i",hashValue);
    	struct NODE *newTop;
    	struct NODE *oldTop;
    	
    
    
    	hashValue=hash(string);	//gets the space in the array to insert word
    
    if(hashValue==188)
    printf("%s",string);
    
    //-----------------------------------------------	
    	oldTop=(struct NODE*)malloc(sizeof(struct NODE));
    	newTop=(struct NODE*)malloc(sizeof(struct NODE));
    	
    	oldTop=&(table[hashValue].listTop);
    
    	strcpy(newTop->word,string);
    
    	newTop->next=oldTop;
    
    	table[hashValue].listTop=*newTop;		//puts the node at the top of list
    
    
    //-----------------------------------------------*/
    
    
    }
    with my output
    acquit
    adjustors
    atrocities
    bowls
    breakaway
    cataract
    colonels
    conditionals
    conjecturing
    conserver
    faced
    gulch
    gushes
    harp
    hitting
    ispell's
    limply
    livest
    lowering
    outlet's
    padding
    personable
    protection
    registering
    safe
    shader
    teaspoonfuls
    towel
    treasuries
    trimer
    188 asian
    trimer
    trimer
    trimer
    trimer
    trimer
    trimer
    trimer
    ....

    until I break from the program.

  13. #13
    Registered User
    Join Date
    Jan 2003
    Posts
    36
    Sorry Shiro, missed you post when I was posting.

    I'm trying to search if the allocated memory is NULL, but it turns up false because nothing is set to the array like before.

    Yet I dont see why I shouldnt have more then enough memory to allocate those two nodes.

    Code:
    oldTop=(struct NODE*)malloc(sizeof(struct NODE));
    	newTop=(struct NODE*)malloc(sizeof(struct NODE));
    	
    	if(NULL==oldTop && NULL==newTop)
    	{
    
    		oldTop=&(table[hashValue].listTop);
    
    		strcpy(newTop->word,string);
    
    		newTop->next=oldTop;
    
    		table[hashValue].listTop=*newTop;		//puts the node at the top of list
    	}
    with the output stopping after 188asian
    (no words in list)

  14. #14
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    I don't know if this will help you, but give these a try

    >>Top=(struct NODE*)malloc(sizeof(struct NODE));
    >>newTop=(struct NODE*)malloc(sizeof(struct NODE));
    You're only inserting one new node I presume, so you only need to malloc() one, not two structures.

    Have a look at this version, which I based on yours.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define WORDSIZE 100
    
    struct NODE
    {
    	char word[WORDSIZE];
    	struct NODE *next;
    };
    
    struct LIST
    {
    	struct NODE *listTop;
    };
    
    void AddNode(struct LIST *, char *);
    void PrintList(struct LIST);
    
    int main(void)
    {
      struct LIST mylist = {0}; /* Init as NULL */
      
      AddNode(&mylist, "This");
      AddNode(&mylist, "is");
      AddNode(&mylist, "a");
      AddNode(&mylist, "test");
      
      PrintList(mylist);
    
      /*
       * There should be a function to free() the
       * memory created by malloc().  I'll leave that
       * for you to write.
       */
      return 0;  
    }
    
    void PrintList(struct LIST list)
    {
      struct NODE *tmp = list.listTop;
      
      while (tmp)
      {
        printf ("Item: >%s<\n", tmp->word);
        tmp = tmp->next;
      }
    }
    
    void AddNode(struct LIST *list, char *word)
    {
      struct NODE *newnode;
      
      if ((newnode = malloc(sizeof(*newnode))) == NULL)
      {
        perror("Out of memory");
        return;
      }
    
      strncpy (newnode->word, word, sizeof(newnode->word));
      newnode->next = list->listTop;
      list->listTop = newnode;
    }
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  15. #15
    Registered User
    Join Date
    Jan 2003
    Posts
    36
    Although the code makes perfect sense, mine is more complex. Every list of mine is inside an array, 2000 to be exact. Which is why i believe it's running out of memory

    here is mine entire code:

    Code:
    //Hashtable Dictionary
    //Hashes the words into the table position, then inserts them in the LL at that location
    //After mistake found - insert into q and put the line it was found on in linequeue
    //print out incorrect words and the times it appears in the file
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<ctype.h>
    #include<malloc.h>
    
    #define WORDSIZE 32
    #define TABLESIZE 2000
    #define HASH_VALUE 13
    #define LINESIZE 520
    #define CHECKFILE "photoshop_primer.txt"
    
    #define TRUE 1
    #define FALSE 0
    
    int tablePosition;
    char delim[]=" .,!?()\";:";
    char line[LINESIZE]={'a','s','i','a','n'};
    int lineCounter;
    
    struct LIST table[TABLESIZE];		//table
    
    
    //global methods
    int hash(char string[]);
    void checkMistakes();
    
    /*typedef struct NODE Node;
    typedef struct LIST List;
    typedef struct QNODE QNode;
    typedef struct QUEUE Queue;
    */
    struct NODE
    {
    	char word[WORDSIZE];
    	struct NODE *next;
    };
    
    struct LIST
    {
    	struct NODE listTop;
    };
    
    struct LINEQUEUE
    {
    	struct NODE lineTop;
    	struct NODE lineBottom;
    };
    
    struct QNODE
    {
    	char word[WORDSIZE];
    	struct LINEQUEUE;
    	struct QNODE *next;
    };
    
    struct QUEUE
    {
    	struct QNODE queueTop;
    	struct QNODE queueBottom;
    }queue;
    
    void enter(char word[])
    {
    
    /*get the word,
    search for it
    	int found=FALSE;
    	struct QNODE current;
    	struct QNODE qnode;
    
    	current = queue.queueTop;
    
    	while(current.word[0]!='\0' && FALSE==found)
    	{
    printf("%s",node->word);
    
    	//if(iter->code == key) return iter;
    	if(strcmp(current.word,string)==0)
    		found=TRUE;
    	else
    		current=current.next;
    	}
    
    
    
    if not found
    	if(found!=TRUE)
    create a new instance of it with blank array of lines
    put into QNODE
    		strcpy(qnode.word,string);
    		queueBottom.next=&QNODE;
    		qnode.lines={0};
    		lines[lineCounter]=TRUE;
    	else
    current is the same word
    		current.lines[lineCounter]=TRUE;
    
    */
    }
    
    void printQueue()
    {
    /*
    	int i;
    start at beginning and print each word with lines
    	struct QNODE current=queue.queueTop;
    while(!at the bottom)
    	printf("%s",current.word);
    	printf("%s","On Lines");
    print the lines the word is mispelled on
    
    
    */
    }
    
    int hash(char string[])
    {
    	int wordValue=0; //value of word
    	int hashValue;	 //position in table
    	int i=0;
    	char c=string[i];
    
    	//loops through the word and uses horners method
    	//for the polynomial function
    	while( (c!='\n') && (c!='\0')&& (i<WORDSIZE) )
    	{
    		wordValue = wordValue*HASH_VALUE+string[i];
    		i++;
    		c=string[i];
    	}
    
    //printf("%s %i\n",string,wordValue);
    	//mods so the word will be in the table
    	hashValue = abs(wordValue%TABLESIZE);
    
    	return hashValue;
    }
    
    void insert(char string[])
    {
    	int hashValue=0;
    
    //printf("%i",hashValue);
    	//struct NODE *node;
    	struct NODE *newTop;
    	struct NODE *oldTop;
    
    
    
    	hashValue=hash(string);	//gets the space in the array to insert word
    
    /........canf(oldstring, "%30s", &newstring);*/
    if(hashValue==188)
    printf("%s",string);
    
    //-----------------------------------------------
    	oldTop=(struct NODE*)malloc(sizeof(struct NODE));
    	newTop=(struct NODE*)malloc(sizeof(struct NODE));
    
    	if(oldTop==NULL && newTop==NULL)
    	{
    
    		oldTop=&(table[hashValue].listTop);
    
    		strcpy(newTop->word,string);
    
    		newTop->next=oldTop;
    
    		table[hashValue].listTop=*newTop;		//puts the node at the top of list
    	}
    	else
    		perror("Out Of Memory");
    
    
    //-----------------------------------------------*/
    
    
    }
    
    void checkMistakes()
    {
    	char *token;
    	char word[WORDSIZE];
    	char lowerWord[WORDSIZE];
    	int hashValue;
    	int i=0;
    	int found=FALSE;
    	struct NODE *node;
    
    	lineCounter++;	//increment the line currently reading
    
    	token=strtok(line,delim);
    	while(token!=NULL)
    	{
    		strcpy(word,token);
    
    		for(i=0;i<strlen(word) && word[i]!='\0';i++)
    		{
    			lowerWord[i]=(char)tolower(word[i]);
    		}
    
    		//puts a null character at the end of the word so array knows where word ends
    		lowerWord[i]='\0';
    
    		hashValue=hash(lowerWord);
    printf("%i %s\n",hashValue,word);
    		node=&(table[hashValue].listTop);
    		if(table[hashValue].listTop.word[0]!='\0')
    		{
    
    /*NODE   struct book *iter;
    
    
      for(iter=head; iter!=NULL; iter=iter->next)
    */
    while(node->word[0]!='\0' && FALSE==found)
    {
    printf("%s",node->word);
    
    	//if(iter->code == key) return iter;
    	if(strcmp(node->word,lowerWord)==0)
    		found=TRUE;
    	else
    	if(node->next!=NULL && node->next->word[0]!='\0')
    		node=node->next;
    	else
    		break;
    }
    
    
    			//search for the word in the list
    /*			while(node->word[0]!='\0' && found!=TRUE)
    			{
    				if(strcmp(node->word,word)==0)
    					//then found
    					found=TRUE;
    				else
    					//increment
    					node = &(node->next);
    			}
    */
    //printf("%s %s\n",word,lowerWord);
    		}
    
    		if(found==TRUE)
    		{
    printf("%s %s\n",word,lowerWord);
    //			enter(word);
    		}
    
    
    		token=strtok(NULL,delim);
    	}
    }
    
    
    
    int main(int argc, char *argv[])
    {
    
    	int i;
    	int arg;
    	char string[WORDSIZE];
    	FILE* word;
    	FILE* check;
    
    	{
    		void insert();
    		void printQueue();
    	}
    
    	lineCounter=0;
    	arg=getopt(argc,argv,"d:");
    
    	if(-1!=arg)
    		word = fopen(optarg,"r");
    	else
    	printf("OOPS");
    
    
    	//sets the first character in each list to NULL to check for empty lists
    	for(i=0;i<TABLESIZE;i++)
    		table[i].listTop.word[0]='\0';
    
    	while(fgets(string,WORDSIZE,word))
    	{
    //printf("%s",string);
    		insert(string);
    	}
    checkMistakes();
    /*
    	check= fopen(CHECKFILE,"r");
    
    	while(NULL!=fgets(line,LINESIZE,check))
    	{
    		checkMistakes();
    
    	}
    */
    	fclose(check);
    	fclose(word);
    
    	printQueue();
    	return EXIT_SUCCESS;
    }
    sorry about all the commenting out, but as I try things I comment out so I dont lose any code until I found the best.
    Im trying to test for one word right now rather then the entire file

    So initializing list to {0} wont work, i dont really have an axs for it

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 11-04-2006, 06:39 PM
  2. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 11:01 AM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 06:46 PM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

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