Code:
#include <stdio.h>
#include <stdlib.h>
#define snapd(expr) printf(#expr " = %d\n", expr);
#define snapd(expr) printf(#expr " = %d\n", expr);
/* Function prototypes */
struct node *createlist(int value);
void printlist(struct node *list);
void find(struct node *list, int value);
void removenode(struct node *list, int value);
void insert(struct node *list, int value);
/* Node definition */
struct node
{
int data;
struct node *ptr;
};
/* This function creates the linked list with the first element equal to its argument */
struct node *createlist(int value)
{
struct node *first;
first = (struct node*)malloc(sizeof(struct node));
first->data = value;
first->ptr = NULL;
return first;
}
/* This function prints out the contents of the linked list */
void printlist(struct node *list)
{
if (list->ptr == (struct node *)-1)
{
printf("The list is empty!\n");
return;
}
while (list->ptr != NULL)
{
printf("%d\n", list->data);
list = list->ptr;
}
if (list->ptr == NULL)
{
printf("%d\n", list->data);
}
}
void find(struct node *list, int value)
{
struct node *previous = list;
if (list->data == value)
{
printf("The element %d have been at the beginning of the list before %d\n", value, list->ptr->data);
return;
}
while (list->ptr != NULL)
{
if (list->data == value && list->ptr != NULL)
{
printf("The element %d have been found between %d and %d\n", value, previous->data, list->ptr->data);
return;
}
previous = list;
list = list->ptr;
}
if (list->data == value)
{
printf("The element %d have been found at the end of the list after %d\n", value, previous->data);
return;
}
printf("The element %d is not found in the list...\n");
}
/* This function removes the node with specified value from the linked list */
void removenode(struct node *list, int value)
{
struct node *previous, *next, *first = list;
int i;
if (list->ptr == (struct node *)-1)
{
printf("The list is already empty!\n");
return;
}
//if the list contains only one element, free the list and exit function
//then set a flag that this element is not a member of the linked list anymore
if (list->data == value && list->ptr == NULL)
{
list->ptr = (struct node*)-1; //set the flag
free(list);
return;
}
for (i = 0; list->data != value; i++)
{
previous = list;
list = list->ptr;
}
if (i != 0)
{
next = list->ptr;
previous->ptr = next;
free(list);
}
else
{
//shift all the elements to the left
for (;;)
{
list->data = list->ptr->data;
list = list->ptr;
if (list->ptr == NULL)
break;
}
//remove the last element
list = first;
while (list->ptr != NULL)
{
previous = list;
list = list->ptr;
}
previous->ptr = NULL;
free(list);
}
}
/* This function inserts the value in the appropriate position in the linked list */
void insert(struct node *list, int value)
{
struct node *newnode;
struct node *previous = list;
//create an empty new node
newnode = (struct node*)malloc(sizeof(struct node));
//scan until the end of the list
while (list->ptr != NULL)
{
if (value > list->data)
{
previous = list;
}
//if it is less than current, and more than previous, insert value between them
if ( (value < list->data) && (value > previous->data) )
{
previous->ptr = newnode;
newnode->ptr = list;
newnode->data = value;
printf("%d is inserted between %d and %d!\n", value, previous->data, list->data);
break;
}
if (value == list->data)
{
printf("There is already value %d in the list!\n", value);
break;
}
if (value < list->data)
{
printf("%d is added before %d...\n", value, list->data);
newnode->data = list->data;
newnode->ptr = list->ptr;
list->data = value;
list->ptr = newnode;
break;
}
list = list->ptr;
}
if (list->ptr == NULL)
{
//if the value is more than the last element add the last element with new value
if (value > list->data)
{
newnode->data = value;
newnode->ptr = NULL;
list->ptr = newnode;
printf("%d is added after %d...\n", value, list->data);
}
if (value == list->data)
{
printf("There is already value %d in the list!\n", value);
}
if (value < list->data)
{
printf("%d is added before %d...\n", value, list->data);
newnode->data = list->data;
newnode->ptr = list->ptr;
list->data = value;
list->ptr = newnode;
}
}
}
void main (int argc, char *argv[])
{
struct node *mylist;
int value;
int command;
printf("Enter the first element of the linked list to be created: ");
scanf("%d", &value);
mylist = createlist(value);
printf("Available commands:\n");
printf("1 - add new element:\n");
printf("2 - remove element:\n");
printf("3 - print the list:\n");
printf("4 - find a value in a list:\n");
printf("0 - quit program:\n");
printf("Enter command: ");
for(;;)
{
scanf("%d", &command);
switch (command)
{
case 1:
printf("Enter the value to be added: ");
scanf("%d", &value);
//if the list is empty, create the new list again
if (mylist->ptr == (struct node *)-1)
{
mylist = createlist(value);
}
else
//otherwise, insert new value in the current list
insert(mylist, value);
printf("Enter the next command ");
break;
case 2:
printf("Enter the value to be removed: ");
scanf("%d", &value);
removenode(mylist, value);
printf("Enter the next command ");
break;
case 3:
printf("Linked list values:\n");
printf("===================\n");
printlist(mylist);
printf("===================\n");
printf("Enter the next command ");
break;
case 4:
printf("Enter the value to be searched for: ");
scanf("%d", &value);
find(mylist, value);
printf("Enter the next command ");
break;
case 0:
return;
break;
default:
printf("wrong command!\n");
printf("Available commands:\n");
printf("1 - add new element:\n");
printf("2 - remove element:\n");
printf("3 - print the list:\n");
printf("4 - find a value in a list:\n");
printf("0 - quit program:\n");
printf("Enter command: ");
break;
}
}
}
And also please pay attention on how i identify the empty list...that casting like (struct node *)-1.. waht do you think about this method?
