Thread: Problem Making a Vector in C

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    69

    Problem Making a Vector in C

    Hello,

    I'm currently trying to make a Vector in C. Most of functions seem to work but I'm getting a Segmentation Fault. Here is my code:

    Code:
    #include "Vector.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    #define NODES_AT_ONCE 1000
    #define NAME_LENGTH 100
    
    Node* orgHead;
    Node* orgTail;
    
    static Node* freeList = NULL;
    
    Node* newNode( void* s, Node* next) {
     Node * r = freeList;  int i;
     if ( freeList == NULL ) { /* then get space for some Nodes */
       freeList = (Node*)calloc(NODES_AT_ONCE, sizeof(Node));
       for(i = NODES_AT_ONCE - 1; i >= 0; i--) {
        freeList[i].next = r;
        r = &freeList[i];
       }	/* the Nodes are linked together as the freeList. */
     }
     freeList = r->next;  strncpy(r->val, s, NAME_LENGTH);   r->next = next;
     return r; /* r points to the new Node which was removed from freeList */
    } 
    
    void freeNode( Node* p ) { p->next = freeList;  freeList = p; }
    
    void newVector(Vector *pv) {
       pv->head = pv->tail = (Node *)
       pv->size = 0;
    }
    
    void add(Vector *pv, void* p) {
       Node* v = (Node *)malloc(sizeof(Node));
       v->val = p;
       v->next = 0;
       if (pv->size == 0) pv->head = pv->tail = v;
       else pv->tail = pv->tail->next = v;
       pv->size++;
    }
    
    void deleteAt(Vector *pv, int num) {
       int i;
       Node *v;
       if (num == 0) pv->head = pv->head->next;
       else {
          v = pv->head;
          for (i = 1; i < num; i++) 
             if (v->next != NULL) v = v->next;
          if (v->next->next != NULL) v->next = v->next->next;
          else v->next = NULL;
       }
       freeNode(v);
    }
    
    void insertAt(Vector *pv, int num, void* p) {
       int i;
       Node *v = (Node *)malloc(sizeof(Node));
       v->val = p;
       Node *curr;
       if (num == 0) {
          v->next = pv->head;
          pv->head = v;
       }
       else if (num == pv->size-1) {
          v->next = 0;
          pv->tail = pv->tail->next = v;
       }
       else {
          curr = pv->head;
          for(i = 1; i < num; i++)
             if (curr->next != NULL) curr = curr->next;
          v->next = curr->next;
          curr->next = v;
       }
    }
    
    void* hasMore(Vector *pv) {
       if (pv->head->next != NULL) return (void *)1;
       else return 0;
    }
    
    void* next(Vector *pv) {
       void* value = pv->head->val;
       pv->head = pv->head->next;
       return value;
    }
    
    void reset(Vector *pv) {
       pv->head = orgHead;
    }
    
    main() {
     Vector v;
     newVector( &v ); //initializes v to be empty
     add(&v, "Mom");
     add(&v, "Dad");
     add(&v, "dog");
     add(&v, "Bro");
     add(&v, "Sis");
     deleteAt(&v, 2); // goodbye dog
     insertAt(&v, 0, "Hi");
     while ( hasMore( &v ) )
      printf("%s ", (char *)next( &v ));
     putchar('\n');
     reset( &v );
     while ( hasMore( &v ) )
      printf("%s ", (char *)next( &v ));
     putchar('\n');
    }
    What this does is it prints out Hi Mom and then gives a Segmentation Fault. I ran it through the gdb debugger and it said it was receiving the Segmentation Fault at the bolded line in the hasMore function. Any help would be appreciated!

  2. #2
    Registered User
    Join Date
    Sep 2003
    Posts
    69

    Talking

    Nevermind, I figured out that problem!

    However, now I have another problem (of course). Now when I try to print it, it only prints Hi Mom Dad. It has something to do with my deleteAt function, I know that for sure. When I take that out of my main function, the list prints correctly. When I try to delete from the 0 position in the Vector, it prints correctly. So, it's something in the else portion of the code. What it seems to be doing is deleting everything after the 2 position, so in this case it deletes dog, and everything after dog.
    Last edited by Zildjian; 10-22-2003 at 09:32 PM.

  3. #3
    Registered User
    Join Date
    Sep 2003
    Posts
    22

    Vector in c

    Hey Zild,
    I need your help please. My program is not compiling..i got this error from the ( hasMore).

    Also the (next) method is not working properly it said it doesn't have the member "tail"
    Could you please show me how you ended up coding your

    deleteAt.
    hasMore, and
    next methods...

    Thanks!
    M

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826

    Re: Vector in c

    Originally posted by dalguy2004
    Hey Zild,
    I need your help please. My program is not compiling..i got this error from the ( hasMore).

    Also the (next) method is not working properly it said it doesn't have the member "tail"
    Could you please show me how you ended up coding your

    deleteAt.
    hasMore, and
    next methods...

    Thanks!
    "Hi! I see you're doing the same homework I am. Can I copy off of yours? Mine doesn't work. Please fix yours and let me copy it. Thanks."

    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    void deleteAt(Vector *pv, int num) {
       int i;
       Node *v;
       if (num == 0) pv->head = pv->head->next;
       else {
          v = pv->head;
          for (i = 1; i < num; i++) 
             if (v->next != NULL) v = v->next;
          if (v->next->next != NULL) v->next = v->next->next;
          else v->next = NULL;
       }
       freeNode(v);
    }
    'v' may be used uninitialized here. If the first if check fails, you will end up trying to free 'v', which points at nothing. Or rather, it points at some random point in memory, since you haven't told it anything specific to point it.

    So what happens is that you set up your head node pointers and then free an invalid 'v'.

    Personally I'd use a double linked list, because they're so easy to delete from.
    Code:
    void delAt( Vector *pv, int n )
    {
        Node *v = pv==NULL?NULL:pv->head;
        int x = 0;
    
        if( !v )
            ...error, no valid list passed, exit...
    
        for( x = 0; x<n; x++ )
            if( v != NULL )
                v = v->next;
            else
                break;
    
        if( x != n )
            ...error, no valid node, exit...
        
        if( n == 0 )
            pv->head = pv->head->next;
    
        if( v->prev )
            v->prev->next = v->next;
        if( v->next )
            v->next->prev = v->prev;
    
        freeNode( v );
    }
    The concept is the same, except you link the node to the node before and after it. Just like links in a chain. Much easier to delete from. Much easier to randomly insert into. Just a slight cost (typically 4 bytes per node, for the additional pointer) in memory, for much more ease of use.

    Otherwise, you can do fairly close to what you have been.

    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    Sep 2003
    Posts
    22

    Vector in c

    Hey quzah,
    what were you saying there?,

    "Hi! I see you're doing the same homework I am. Can I copy off of yours? Mine doesn't work. Please fix yours and let me copy it. Thanks."


    are you doing the same assignment?
    I didn't get your story.
    M

  7. #7
    Registered User
    Join Date
    Sep 2003
    Posts
    22

    Vector in c

    Ok here's my problem again,
    I got this segmentation fault from the hasMore function:

    if(pv->head->next !- NULL)

    any help would be appreciated! if you understand how i can put the hasMore function.

    This is what i have :
    <
    void* hasMore(Vector *pv)

    if(pv->head->next != NULL)
    return(void *) 1;
    else
    return 0;

    >
    Thanks
    M

  8. #8
    King of the Internet Fahrenheit's Avatar
    Join Date
    Oct 2001
    Posts
    128
    Try code tags... but anyway the way you are getting a segmentation fault is if pv or pv->head is an invalid pointer. You probably didn't init pv correctly before passing it to hasMore...

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826

    Re: Vector in c

    Originally posted by dalguy2004
    are you doing the same assignment?
    I didn't get your story.
    I was openly mocking you.

    Quzah.
    Hope is the first step on the road to disappointment.

  10. #10
    Registered User
    Join Date
    Sep 2003
    Posts
    22

    Vector in c

    Thanks w00t, and thanks for the mocking too quzah.It's all good, someday i'm here for help, and i appreciate it in all form.
    Thanks
    M

  11. #11
    Visionary Philosopher Sayeh's Avatar
    Join Date
    Aug 2002
    Posts
    212
    Quzah, thank you, thank you... very funny. ;P
    It is not the spoon that bends, it is you who bends around the spoon.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 11-07-2005, 11:34 PM
  2. searching problem
    By DaMenge in forum C Programming
    Replies: 9
    Last Post: 09-12-2005, 01:04 AM
  3. crashing problem in c++
    By Enki in forum C++ Programming
    Replies: 6
    Last Post: 11-08-2002, 01:21 AM
  4. half ADT (nested struct) problem...
    By CyC|OpS in forum C Programming
    Replies: 1
    Last Post: 10-26-2002, 08:37 AM
  5. binary tree problem - help needed
    By sanju in forum C Programming
    Replies: 4
    Last Post: 10-16-2002, 05:18 AM