clarinetster

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;
}

Witch_King

It's a little confusing. Just curious, why did you want to use a recursive function to build the singly linked list? It can be simplified.

__________________
I compile code with:
Visual Studio.NET beta2

Clarinetster

It is our assignment to create a singly linked list with header, using both recursive and non-recursive functions and procedures. I have to use all the functions that are employed in the posted program because they are the basis for future programs. Our instructor enjoys making our lives difficult.

Clarinetster