Anyone knowledgeable with C?
Thread Starter
Registered User
iTrader: (8)
Joined: Apr 2008
Posts: 1,493
From: Hercules CA
Car Info: 03 WRX --> 07 STI --> 10 Cayman S
Anyone knowledgeable with C?
I need some help with my C program and was wondering if anyone here can offer some assistance...
I am implementing an array of doubly linked-lists. I have two files (Graph.c and List.c) and two header files (Graph.h and List.h). I have a function in List.c called "insertAfterLast(ListRef L, int n)". In my array list, I'm trying to append numbers onto this array-addressed linked list in Graph.c. However, when I call on "insertAfterLast" the first time, it appends to the correct address and appends onto the linked list at that address, I get a segmentation fault when I call on "insertAfterLast" on the same address and try to append it onto the existing linked list.
I believe I properly defined it in my header files, and I did indeed include "List.h" in Graph.c. I have a feeling that it's in my Graph constructor where I'm having trouble calling it.
If anyone can provide some feedback, that'll be great.. This has been driving me nuts the last couple hours
Here is my list function for those that are curious...
I am implementing an array of doubly linked-lists. I have two files (Graph.c and List.c) and two header files (Graph.h and List.h). I have a function in List.c called "insertAfterLast(ListRef L, int n)". In my array list, I'm trying to append numbers onto this array-addressed linked list in Graph.c. However, when I call on "insertAfterLast" the first time, it appends to the correct address and appends onto the linked list at that address, I get a segmentation fault when I call on "insertAfterLast" on the same address and try to append it onto the existing linked list.
I believe I properly defined it in my header files, and I did indeed include "List.h" in Graph.c. I have a feeling that it's in my Graph constructor where I'm having trouble calling it.
If anyone can provide some feedback, that'll be great.. This has been driving me nuts the last couple hours
HTML Code:
typedef struct Graph{
ListRef* adj;
char *color;
int *parent;
int *distance;
int order;
int size;
int vertex;
}Graph;
/***Constructors-Destructors***/
GraphRef newGraph(int n){
int i;
GraphRef G = malloc(sizeof(Graph));
G->adj = calloc(n, sizeof(ListRef));
G->color = calloc(n, sizeof(char));
G->parent = calloc(n, sizeof(int));
G->distance = calloc(n, sizeof(int));
for(i = 1; i<n+1; i++){
G->adj[i] = newList();
G->color[i] = 'w';
G->distance[i] = INF;
G->parent[i] = NIL;
}
G->size = n;
return G;
}
HTML Code:
void insertAfterLast(ListRef L, int data){
NodeRef node = newNode(data);
if(isEmpty(L)){
L->current = node;
L->first = L->last = L->current;
L->length++;
}else{
node->next = NULL;
node->prev = L->last;
L->last->next = node;
L->last = node;
L->current = L->last;
L->length++;
}
}
typedef struct List{
NodeRef first;
NodeRef current;
NodeRef last;
int length;
}List;
ListRef newList(void){
ListRef L;
L = malloc(sizeof(List));
L->first = L->last = L->current = NULL;
L->length = 0;
return(L);
}
HTML Code:
typedef struct Graph{
ListRef* adj;
char *color;
int *parent;
int *distance;
int order;
int size;
int vertex;
}Graph;
/***Constructors-Destructors***/
GraphRef newGraph(int n){
int i;
GraphRef G = malloc(sizeof(Graph));
G->adj = calloc(n, sizeof(ListRef));
G->color = calloc(n, sizeof(char));
G->parent = calloc(n, sizeof(int));
G->distance = calloc(n, sizeof(int));
for(i = 1; i<n+1; i++){
G->adj[i] = newList();
G->color[i] = 'w';
G->distance[i] = INF;
G->parent[i] = NIL;
}
G->size = n;
return G;
}
HTML Code:
void insertAfterLast(ListRef L, int data){
NodeRef node = newNode(data);
if(isEmpty(L)){
L->current = node;
L->first = L->last = L->current;
L->length++;
}else{
node->next = NULL;
node->prev = L->last;
L->last->next = node;
L->last = node;
L->current = L->last;
L->length++;
}
}
typedef struct List{
NodeRef first;
NodeRef current;
NodeRef last;
int length;
}List;
ListRef newList(void){
ListRef L;
L = malloc(sizeof(List));
L->first = L->last = L->current = NULL;
L->length = 0;
return(L);
}
not sure why you need to move current when inserting, current should be used when traversing the list, such as reading from first to last. It is correct to set it when the first node is inserted, but on subsequent inserts only last should be moved.
aside from that, you shouldnt set last->next to node, it will be null after you make it the tip of the list again by setting Last = Node;
not really sure if this why you're segfaulting, usually a segfault means you're trying to use an address space that hasnt been allocated or defined. maybe look at how you initialize your node in newnode().
void insertAfterLast(ListRef L, int data)
{
NodeRef node = newNode(data);
if(isEmpty(L))
{
L->current = node;
L->first = L->last = L->current;
L->length++;
}else
{
node->prev = L->last;
L->last = node;
L->last->next = NULL;
L->length++;
}
}
Registered User
iTrader: (3)
Joined: Sep 2007
Posts: 207
From: Fremont, CA
Car Info: 2015 WRX Limited
Can't say for sure as I can't see what type of object NodeRef is, but it looks like it's segfaulting at this point: "L->last->next = node;" in your insertafterlast function. From what I can tell it's cause of this struct:
typedef struct List{
NodeRef first;
NodeRef current;
NodeRef last;
int length;
}List;
where first, current and last aren't actually pointing to addresses.
typedef struct List{
NodeRef first;
NodeRef current;
NodeRef last;
int length;
}List;
where first, current and last aren't actually pointing to addresses.
iClub Silver Vendor
iTrader: (12)
Joined: Mar 2003
Posts: 8,228
From: 631 Railroad Ave. Fairfield, CA
Car Info: A Laptop
Looks like you guys got it already.
Man I need to do some more coding... its been about 4 years since I've written any real code and it took me a little while to read through this. C, C++ and Java used to be second nature. Its amazing how quickly you lose it!
-- Ed
Man I need to do some more coding... its been about 4 years since I've written any real code and it took me a little while to read through this. C, C++ and Java used to be second nature. Its amazing how quickly you lose it!
-- Ed
Thread Starter
Registered User
iTrader: (8)
Joined: Apr 2008
Posts: 1,493
From: Hercules CA
Car Info: 03 WRX --> 07 STI --> 10 Cayman S
Thanks for all your guy's help.
I think I further isolated the problem. I have a feeling there's something wrong with my pointers. So the first time I call on my append function onto an empty list with say, insertAfterLast(G->adj[1], 2), it works fine, however when I try to append onto the existing linked list say with a call insertAfterLast(G->adj[1], 3), I seg fault. But one thing I noticed is that it seg faults when it calls onto a new node. So I have a feeling that perhaps I need to free the node when I create a new node. See below:
So you can see that I try to free the node after I'm done with creating it the node and doing my function, I call on freeNode(*node), however, I get an error saying that it's an incompatible type.
Any suggestion on this?
I think I further isolated the problem. I have a feeling there's something wrong with my pointers. So the first time I call on my append function onto an empty list with say, insertAfterLast(G->adj[1], 2), it works fine, however when I try to append onto the existing linked list say with a call insertAfterLast(G->adj[1], 3), I seg fault. But one thing I noticed is that it seg faults when it calls onto a new node. So I have a feeling that perhaps I need to free the node when I create a new node. See below:
HTML Code:
void insertAfterLast(ListRef L, int data){
printf("insertAfterLast1\n");
NodeRef node = newNode(data);
if(isEmpty(L)){
L->current = node;
L->first = L->last;
L->length++;
}else{
printf("insertAfterLast1\n");
printf("length: %d \n", getLength(L));
node->prev = L->last;
L->last = node;
node->next = NULL;
L->length++;
freeNode(*node);
}
}
/*********************/
/***Private Structs***/
typedef struct Node{
int data;
struct Node* next;
struct Node* prev;
}Node;
typedef Node* NodeRef;
typedef struct List{
NodeRef first;
NodeRef current;
NodeRef last;
int length;
}List;
/**************************************/
/***Private Constructors-Destructors***/
/*Returns pointer to new Node struct*/
NodeRef newNode(int data){
NodeRef node = malloc(sizeof(Node));
node->next = NULL;
node->prev = NULL;
node->data = data;
return(node);
}
/*freeNode
Frees heap memory pointed to by pL */
void freeNode(NodeRef* pN){
if(pN != NULL && *pN!=NULL){
free(*pN);
*pN = NULL;
}
}
/***************************************************/
/***Public ListRef struct, constructor-destructor***/
/*Returns ListRef pointing to new ListRef*/
ListRef newList(void){
ListRef L;
L = malloc(sizeof(List));
L->first = L->last = L->current = NULL;
L->length = 0;
return(L);
}
/*freeQueue
Frees all heap memory associated with the ListRef *pL, including
all memory in existing Nodes. Sets *pL to NULL*/
void freeList(ListRef* pL){
if(pL==NULL || *pL==NULL){return;}
while(!isEmpty(*pL)){deleteCurrent(*pL);}
free(*pL);
*pL = NULL;
}
Any suggestion on this?
Registered User
iTrader: (3)
Joined: Sep 2007
Posts: 207
From: Fremont, CA
Car Info: 2015 WRX Limited
No, you don't want to free it. That will just give the memory allocated back for future allocation.
Also here is another problem for you:
void insertAfterLast(ListRef L, int data){
printf("insertAfterLast1\n");
NodeRef node = newNode(data);
if(isEmpty(L)){
L->current = node;
L->first = L->last; --- you're setting first to NULL here when it should be the node you just created
L->length++;
You're segfaulting because of your pointers.
Also here is another problem for you:
void insertAfterLast(ListRef L, int data){
printf("insertAfterLast1\n");
NodeRef node = newNode(data);
if(isEmpty(L)){
L->current = node;
L->first = L->last; --- you're setting first to NULL here when it should be the node you just created
L->length++;
You're segfaulting because of your pointers.
Thread
Thread Starter
Forum
Replies
Last Post
akdmx
Bay Area
6
Jan 11, 2009 09:09 PM
slow04wrx
Bay Area
15
Oct 24, 2007 02:20 PM
BluWRX03
Suby Shopping & Maintenance/Warranty
0
Feb 8, 2006 11:49 PM
Kostamojen
Wheel & Tire
13
Nov 6, 2003 10:11 PM
