I've done it. According to your advice Prelude I used doubly linked list. Now I completely realise why is better to use:
Code:
struct node {
int data;
struct node *link[2];
};
and not
Code:
struct node {
int data;
struct node *next;/* or left*/
struct node* prev;/* or right*/
};
I think that everything works fine now. And for you to see that your posts and advices aren't gone with the wind, here's complete code (maybe someone will find it useful):
header:
Code:
#ifndef DOUBLYLINKEDLIST_H
#define DOUBLYLINKEDLIST_H
enum {FAIL,SUCCES};
typedef struct Node
{
int data;
struct Node* next;
struct Node* prev;
}node;
int InsertHead(node**,int);
int InsertEnd(node**,int);
int InsertNext(node*,int);
int RemoveHead(node**);
int RemoveEnd(node**);
int RemoveNext(node*);
int RemoveAll(node**);
int Length(node*);
void Show(node*);
//BST
void InsertBST(node **,node*);
void BSTList (node *,node**);
node* BSTSort(node*);
#endif
implementation:
Code:
#include <stdio.h>
#include <stdlib.h>
#include "DoublyLinkedList.h"
int InsertHead(node** head,int data)
{
node* current=(node*)malloc(sizeof(node));
if(!current)
{
return FAIL;
}
current->data=data;
current->prev=current->next=NULL;
if(!*head)
{
*head=current;
return SUCCES;
}
current->next=*head;
*head=current;
return SUCCES;
}
int InsertEnd(node** head,int data)
{
node* current=(node*)malloc(sizeof(node));
node* walk=*head;
if(!current)
{
return FAIL;
}
current->data=data;
current->prev=current->next=NULL;
if(!*head)
{
*head=current;
return SUCCES;
}
for(;walk->next;walk=walk->next);
walk->next=current;
current->prev=walk;
return SUCCES;
}
int InsertNext(node* prev,int data)
{
node* current=(node*)malloc(sizeof(node));
if(!current || !prev)
{
return FAIL;
}
current->data=data;
current->next=prev->next;
prev->next=current;
current->prev=prev;
current->next->prev=current;
return SUCCES;
}
int RemoveHead(node** head)
{
node* helper;
if(!*head)
{
printf("\nNothing to remove!");
return FAIL;
}
helper=*head;
*head=(*head)->next;
(*head)->prev=NULL;
free(helper);
return SUCCES;
}
int RemoveEnd(node** head)
{
node* helper;
if(!*head)
{
printf("\nNothing to remove!");
return FAIL;
}
if(!(*head)->next)
{
free(*head);
*head=NULL;
return SUCCES;
}
for(helper=*head;helper->next->next;helper=helper->next);
free(helper->next);
helper->next=NULL;
return SUCCES;
}
int RemoveNext(node* previous)
{
node* helper;
if(!previous)
{
return FAIL;
}
helper=previous->next;
helper->next->prev=previous;
previous->next=previous->next->next;
free(helper);
return SUCCES;
}
int RemoveAll(node** head)
{
node* save;
if(!*head)
{
return FAIL;
}
while(*head)
{
save=(*head)->next;
free(*head);
*head=save;
}
return SUCCES;
}
int Length(node* walk)
{
int len=1;
if(!walk)
{
return FAIL;
}
while(walk=walk->next)
{
len++;
}
return len;
}
node* Find(node*walk,int data)
{
if(!walk)
{
return NULL;
}
for(;walk;walk=walk->next)
{
if(walk->data==data)
return walk;
}
return NULL;
}
void Show(node* head)
{
if(!head)
{
printf("\nThere are no elements in the list!\n");
return;
}
printf("\n");
while(head)
{
printf("%d ",head->data);
head=head->next;
}
}
void InsertBST(node **tree, node* element)
{
if (*tree == NULL)
{
*tree = element;
(*tree)->next=(*tree)->prev=NULL;
return;
}
if(element->data<=(*tree)->data)
InsertBST(&(*tree)->prev,element);
else
InsertBST(&(*tree)->next,element);
}
void BSTList (node* tree,node** list)
{
node* save;
if(!tree)
{
return;
}
BSTList(tree->next,list);
save=tree->prev;
tree->next=tree->prev=NULL;
InsertHead(list, tree->data);
BSTList(save,list);
}
node* BSTSort(node* list)
{
node* tree=NULL, *save;
while(list)
{
save=list->next;
list->prev=list->next=NULL;
InsertBST(&tree,list);
list=save;
}
BSTList(tree,&list);
return list;
}
And finally test program
Code:
#include <stdio.h>
#include <stdlib.h>
#include "DoublyLinkedList.h"
#include <crtdbg.h>
int main()
{
node* head=NULL;
int i;
for(i=0;i<10;i++)
InsertHead(&head,rand()%10);
Show(head);
head=BSTSort(head);
Show(head);
}
I would also like if you can examine parts of this code, especially functions RemoveEnd nad RemoveHead. I think that is correct, but for me it looks like a little bulky. If you can do that and give your opinion I would greatly appreciate it.
Thanks!