Member Avatar for sahil_m
sahil_m 0 Newbie Poster

Hi,

I've just started coding a simple linked list library and I would like the final implementation to have functions like sorting & searching.

My questions are:-

1.I think that my library would need to implement sorting and searching similar to the qsort() and bsearch() implementation's in borland's library.

2.Could someone elaborate on how to implement these functions?

3.I am attaching my code along with this post, if you find any bugs, pitfalls or have any suggestions, kindly let me know.

Thanks,
Sahil

/* Chains - The Basic Linked List Library - ver 0.1a 
Bugs,improvements and ideas :- Sahil Muthoo, <static_void_2001@yahoo.com> */


#include <stdlib.h>
#include <stdio.h>

struct node					/*Generic node used to store the list*/
{
	void *data;
	struct node *next;
};

typedef struct node * nodeptr;

unsigned int count_nodes(nodeptr,nodeptr);     /* Counts the number of nodes in the list */
nodeptr getnode(size_t);                       /* Allocates memory for nodes */
nodeptr last(nodeptr);                         /* Seeks to the last node in the list */
nodeptr remove_node(nodeptr,nodeptr);          /* Removes a node from the list */
void stk_overflow(void);                       /* handles stack overflows */
nodeptr insert_node(nodeptr,nodeptr,int);	   /* Inserts a node in the list */	
int destroy_list(nodeptr);					   /* Destroys a list */	
nodeptr reverse(nodeptr);					   /* Reverses a list */	

unsigned int count_nodes(nodeptr head,nodeptr tail)  /*head must point to the start of the list and tail 
													  should point to the node till which you want to count
													  pass tail as NULL for counting the entire list*/
{
	nodeptr curr;
	unsigned int nodes=0;
	
	if(!head)
		return 0;                /* The list is empty */
	
	for(curr=head;curr!=tail;curr=curr->next)
		nodes++;
	
	return nodes;
}


nodeptr getnode(size_t node_size)    /*Size of your node should be passed through node_size */
{
	nodeptr temp;
	
	temp=malloc(sizeof(*temp));      /*Allocate node*/
	if(!temp)						
		stk_overflow();
			
	temp->data=malloc(node_size);   /*Allocate the user's structure in node->data*/
	if(!temp->data)
		stk_overflow();
	
	temp->next=NULL;
	
	return temp;
}

nodeptr last(nodeptr head)			/*Again head must point to the start of the list */
{
	nodeptr curr;
	
	if(!head)						/*The list is empty*/
		return NULL;
	
	for(curr=head;curr->next!=NULL;curr=curr->next)
	;
	
	return curr;
}

void stk_overflow(void)				
{
	printf("\nStack overflow...quitting"); /*If a stack overflow occurs, 
											simply print an error message and die :)*/
	exit(1);
}

nodeptr remove_node(nodeptr remove,nodeptr head) /*The node to be deleted must be passed through remove */
{
	nodeptr curr=head;        /*Initialize current node as head*/
	
	if(!head)				  /*The list is empty*/				
		return NULL;
	
	if(!remove)
		return head;         /*If remove was NULL, do nothing */
		
	
	
	
	if(remove==head)
	{
		if(head->next)
		{
			head=head->next;
			free(remove);
			return head;
		}
		free(head);
		return  NULL;              /*If the list becomes empty, return NULL*/
	}
	
	while(curr->next!=remove)
		curr=curr->next;
		
	curr->next=remove->next;
	free(remove);
	return head;

}

nodeptr insert_node(nodeptr insert,nodeptr head,int position) /*The node to be inserted must 
																be passed through insert */
{   /* Value of postion   Action
		     0             insert node at start
		    -1			   insert node at end of list	
       any other value	   insert after node */    
	
	nodeptr curr=head;           
	nodeptr temp=NULL;
	int nodes=0;
	
	
	switch(position)
	{
		case 0:
			insert->next=head;
			head=insert;
			return head;
			break;
			
		case -1:
			if(!head)
				return NULL;     /* The list is empty */
			curr=last(head);
			curr->next=insert;
			return head;
			break;
			
		default:
			nodes=count_nodes(head,NULL);
						
			if(position >= nodes || position < -1)
				return head;					/*Unable to add node, return */
			
						
			while(position > 0)
			{
				curr=curr->next;
				position--;
			}
			
				temp=curr->next;
				curr->next=insert;
				insert->next=temp;
				return head;
				
       
	}
	
}

int destroy_list(nodeptr head)
{
	nodeptr save=NULL,curr;
	
	for(curr=head;curr!=NULL;curr=curr->next)
	{
		save=curr->next;     /*save the next pointer of the node to be destroyed*/
		free(curr);
		curr=save;
	}
	return 0;
}

nodeptr reverse(nodeptr head)
{
	
	return head;
}
  • 1 Contributor
  • 0 Replies
  • 59 Views
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.