singly linked list
Hi everybody,
I have been working on a singly linked list recently. This version is a recursive version. The problem i am having is that the program only works if there are two or less links in the list. The format of the expected input of my program is: "(" CR "A" CR "B" CR "C" CR ")" CR
Where CR is a carridge return, "A" "B" and "C" are data items, and the quotes should be omitted. What follows is my program, and thanks ahead of time to anyone who can find my bug. If you feel like my program is too long or complicated to look over, i don't blame you.
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
typedef int boolean;
typedef char data;
typedef struct node
{
data info;
struct node *next;
} list_node;
typedef list_node list_head;
typedef list_head *list;
void printlist (list);
list nullist(void);
boolean null(list);
data car(list);
list cdr(list);
list cons(data, list);
data read_element(void);
list readlist_element(void);
list readlist(void);
void printlist (list);
int main()
{
list Test_List;
Test_List = readlist();
printf("readlist complete \n");
printlist(Test_List);
return 0;
}
list nullist() /* return an empty list */
{
list L;
L = (list_head *) malloc (sizeof(*L));
L->info = NULL;
L->next = NULL;
printf("entered nullist \n");
return(L);
}
boolean null(list L) /* test an empty list */
{
if (L->next->info == NULL)
{
printf("null test true \n");
return(1);
}
else
{
printf("null test false \n");
return(0);
}
}
data car(list L) /* obtain the first element of given list */
{
list_node *Current_Node;
Current_Node = L->next;
return(Current_Node->info);
}
list cdr(list L) /* obtain the rest of the list */
{
list_head *cdr_head; /* Structure Sharing */
cdr_head = L->next; /* Get to header */
cdr_head = cdr_head->next; /* make cdr_head->next point to the second element in the list */
return(cdr_head);
}
list cons(data alpha, list L) /* insert an element in the front */
{
list_node *insert; /* Structure Sharing */
list_head *cons_head;
if(L->next == NULL)
{
insert = nullist(); /* allocate memory for the new node */
cons_head = nullist(); /* allocate memory for the header */
cons_head = L; /* make passed in pointer point to header */
cons_head->next = insert; /* make header point to new first node */
insert->info = alpha; /* insert data into node element */
insert->next = nullist(); /* be sure to make the last node NULL */
}
else
{
insert = nullist(); /* allocate memory for the new node */
cons_head = nullist(); /* allocate memory for the header */
insert->next = nullist(); /* allocate memory for temporary storage */
cons_head = L; /* make passed in pointer point to header */
insert->next = cons_head->next; /* make new first node point where old first node used to point */
cons_head->next = insert; /* make header point to new first node */
insert->info = alpha; /* insert data into node element */
insert->next->next = nullist(); /* be sure to make the last node NULL */
}
return(L);
}
data read_element() /* to skip spaces */
{
data letter;
letter = getchar();
while(isspace(letter)) letter = getchar();
return(letter);
}
list readlist_element(void) /* to read in elements */
{
printf("entered readlist_element \n");
data letter;
letter = read_element(); /* returns data for list */
if(letter == ')') /* if at the end of the list, return an empty list */
return(nullist());
else if(isalpha(letter)) /* if not at end of list, get more data for another link */
return(cons(letter, readlist_element()));
else
{
printf("Error in readlist_element. \n");
return nullist();
}
}
list readlist(void) /* to start reading a list */
{
list lister;
data letter;
printf("Input List >> ");
letter = read_element();
if (letter == '(')
{
lister = readlist_element();
printf("readlist_element executed \n");
return lister;
}
else
{
printf("Error on input format. \n");
return nullist();
}
}
void printlist (list L) /* to print out a list */
{
static int i = 0;
if(i == 0)
{
printf("(");
printf(" ");
i++;
printlist(L);
}
else if(null(L))
printf(")\n");
else
{
printf("%c", L->next->info);
printf(" ");
printlist(L->next);
}
i = 0;
}
