Reputation: 213
Exception thrown in linked list
I need to write a function that returns the size of a linked list. It seems simple enough, but I get an exception when I try to advance my pointer. This is the code:
int List_size(List *list)
{
List_node *p;
int counter = 0;
p = list->head;
while (p != NULL)
{
p = p->next;
counter = counter + 1;
}
return counter;
}
This is the code that defines the linked list:
typedef struct List_node
{
int data;
struct List_node *next;
struct List_node *prev;
}List_node;
typedef struct List
{
List_node *head;
}List;
And this is the code that creates the list:
List *create_list(int n)
{
List *list = (List*) calloc(n,sizeof(List));
list->head = NULL;
return list;
}
Lastly, I have inserted data (numbers) into the list using these two functions: (so don't think the lists are empty).
void insert_first(List_node *x, List *list)
{
x->next = list->head;
list->head = x;
}
void insert(List_node *x, List_node *y)
{
x->next = y->next;
y->next = x;
}
List_node *mk_node(int data, int n)
{
List_node *node = (List_node *)calloc(n, sizeof(List_node));
node->data = data;
return node;
}
Using a breakpoint I discovered that the problem lies in p = p->next, but I don't understand why.
Thank you very much.
edit - I did not think the full code is necessary, but here it is:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include "List.h"
void merge(List *small_list, List *big_list)
{
List_node *x, *y;
y = small_list->head;
x = big_list->head;
t = x->prev;
// while (y < x) //If there are smaller numbers on the small list, insert them first
// {
// insert(y,t)
// t = t->next;
// y = y->next;
// }
while (y != NULL && x->next != NULL)
{
if (x <= y && x->next >= y)
{
insert(y, x);
y = y->next;
}
else
x = x->next;
}
while (y != NULL)
{
insert(y, x);
y = y->next;
}
}
void main()
{
List *L1, *L2, *big_list, *small_list;
int num1, num2;
int i;
int a, b;
create_list(5,&L1);
create_list(3,&L2);
printf("Insert first number into L1\n");
scanf("%d", &num1);
node = mk_node(0,5);
insert_first(node, &L1);
for (i = 0; i<5; i++)
{
printf("Now insert the rest of the numbers\n");
scanf("%d", &num1);
next = mk_node(&num1,5);
insert(next, node);
node = next;
}
printf("Insert first number into L2\n");
scanf("%d", &num2);
node = mk_node(0,3);
insert_first(node, &L2);
for (i = 0; i<3; i++)
{
printf("Now insert the rest of the numbers\n");
scanf("%d", &num2);
next = mk_node(&num2,3);
insert(next, node);
node = next;
}
//If lists are in descending order, reverse them to ascending order
//if (L1->head > L1->head->next)
// reverse(L1);
// if (L2->head > L2->head->next)
// reverse(L2);
int size_L1 = List_size(L1);
int size_L2 = List_size(L2);
if (size_L1 <= size_L2)
{
big_list = L2;
small_list = L1;
}
else
{
big_list = L1;
small_list = L2;
}
merge(small_list, big_list);
print_list(L3);
getchar(); getchar();
}
As you can see, I inserted the numbers using the function insert(). I hope it is okay.
The function reverse is: (I really hope it works, I translated it from pseudo-code)
List reverse(List *list)
{
List_node *x, *y, *z;
if (list->head == NULL || list->head->next == NULL)
{
return *list;
}
x = list->head;
y = list->head->next;
z = list->head->next->next;
x->next = NULL;
while (z != NULL)
{
y->next = x;
x = y;
y = z;
z = z->next;
}
y->next = x;
list->head = y;
}
Basically, this is an assignment that says I have two 2-directional sorted linked lists, and I'm supposed to merge them into one big sorted linked list.
As for the exception - Unhandled exception at 0x00E21766 in Lists.exe: 0xC0000005: Access violation reading location 0xCCCCCCD0.
Edit - the print_list function:
void print_list(List *list)
{
List_node *p;
p = list->head;
printf("The linked list consists of: ");
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
Upvotes: 0
Views: 211
Answers (3)
Reputation: 25286
I added a comment above that I copied your code into my compiler and that it doesn't compile, so it won't run: the calls to create_list don't compile: they return a value as function return, not in a parameter; there are undeclared variables. Further, it is useless to give create_list and mk_node a parameter: they will allocate an array, not create a single list element. A call of calloc(1, sizeof(your_thing)) would suffice. After fixing these erors, several bugs became apparent:
- in insert_first(node, &L2); you give it the address of the list, which is already a pointer. Remove the '&' (the compiler should have complained!).
- same for List_size(&L1); L1 is already a pointer. Remove the '&'.
- in: if (x <= y ...) you compare memory addresses. Change to: if (x->data <= y->data...)
- in that statement the part "x->next >= y" also compares memory address, and I don't see why it is needed. I removed it.
The real problem seems to be in merge. You should either merge the lists into L1, or into L2, and preferably should create a result list. But you "randomly" insert an element into L1, then into L2, then again into L1, etcetera. In my test it ran indefinitly. The following merge works fine:
List *merge(List *small_list, List *big_list)
{
List_node *x, *y, *r;
List *result= create_list();
y = small_list->head;
x = big_list->head;
if (x->data < y->data)
{result->head= x; x= x->next;}
else {result->head= y; y= y->next;}
r= result->head;
while (y != NULL && x != NULL)
{
if (x->data < y->data)
{
r->next= x;
x = x->next;
}
else {
r->next= y;
y = y->next;
}
r= r->next;
}
while (y != NULL)
{
r->next= y;
y = y->next;
r= r->next;
}
while (x != NULL)
{
r->next= x;
x = x->next;
r= r->next;
}
r->next= 0;
return (result);
}
Upvotes: 1
Reputation: 25286
So the problem is that you allocate the list head, but never allocate memory for the list elements. Serge added mk_node which does the allocation (so Serge solved it).
Upvotes: 1
Reputation: 148910
The problem is in code you did not show, because all the code you give is fine (*).
I could use your structs and functions to :
- create a List
- add a first node (with insert_first)
- add other nodes (with insert)
- get the size (using List_size)
- display the data value of every node
- free the nodes and the list
Here's the full code :
#include <stdio.h>
#include <malloc.h>
typedef struct List_node
{
int data;
struct List_node *next;
struct List_node *prev;
}List_node;
typedef struct List
{
List_node *head;
}List;
List *create_list()
{
List *list = (List*) malloc(sizeof(List));
list->head = NULL;
return list;
}
int List_size(List *list)
{
List_node *p;
int counter = 0;
p = list->head;
while (p != NULL)
{
p = p->next;
counter = counter + 1;
}
return counter;
}
void insert_first(List_node *x, List *list)
{
x->next = list->head;
list->head = x;
}
void insert(List_node *x, List_node *y)
{
x->next = y->next;
y->next = x;
}
/* my own additions */
List_node *mk_node(int data) {
List_node *node = (List_node *) malloc(sizeof(List_node));
node->data = data;
return node;
}
void delete_list(List *list) {
List_node *node = list->head;
while (node != NULL) {
List_node *next = node ->next;
free(node);
node = next;
}
free(list);
}
int main() {
List* list = create_list();
List_node *node, *next;
int i;
node = mk_node(0);
insert_first(node, list);
for (i=1; i<5; i++) {
next = mk_node(i);
insert(next, node);
node = next;
}
int n = List_size(list);
printf("size : %d\n", n);
node = list->head;
while (node != NULL) {
printf("node val : %d\n", node->data);
node = node->next;
}
delete_list(list);
return 0;
}
(*) Your code is not perfect because List_node struct contains a pointer prev that is never used, so you end with a single-linked list with every third value unused.
Upvotes: 3