C- Data structures FAQ

1) This program helps illustrates single link list manipulation

#include
#include "malloc.h"

typedef struct node {
int data;
struct node *next;
}node;
node *head;
void createlist (int data);
void destroylist ();
void reverselist (node *child, node *parent);

int main (int argc, char *argv[])
{
int cnt;
int data;
int i;
scanf ("%d", &cnt);
for (i=0;i<=cnt;i++) { scanf("%d",&data); createlist(data); } reverselist(head->next, head);
destroylist();
return 0;
}

void createlist (int data)
{
node *ptr;
node *tmp;
if ((ptr = (node *) malloc (sizeof (node))) == NULL)
{
printf ("Memory allocation failed \n");
exit (-1);
}
ptr->data=data;
if (head == NULL)
head = ptr;
else {
tmp = head;
while (tmp->next != NULL)
tmp = tmp->next;
tmp->next = ptr;
}
}

void destroylist()
{
node *tmp = head;
node *tmp1;
while (tmp != NULL)
{
tmp1 = tmp;
printf("Nodes values %d\n", tmp->data);
tmp = tmp->next;
free (tmp1);
}
}

void reverselist (node *child, node *parent)
{
if ( child != NULL )
{
reverselist(child->next, child);
child->next = parent;
}
else {
head->next = NULL;
head = parent;
}
}

2) Double link list manipulation

#include
#include "malloc.h"

typedef struct node {
int data;
struct node *next;
struct node *prev;
}node;
node *head;
void createlist (int data);
void destroylist ();
void reverselist (node *n);
void insertnode (int data, node *n);
int main (int argc, char *argv[])
{
int cnt;
int data;
int i;
scanf ("%d", &cnt);
for (i=0;i<=cnt;i++) { scanf("%d",&data); createlist(data); } reverselist(head); insertnode(10000, head->next->next);
destroylist();
return 0;
}

void createlist (int data)
{
node *ptr;
node *tmp;
if ((ptr = (node *) malloc (sizeof (node))) == NULL)
{
printf ("Memory allocation failed \n");
exit (-1);
}
ptr->data=data;
ptr->next= NULL;
if (head == NULL)
{
head = ptr;
head->prev = NULL;
}
else {
tmp = head;
while (tmp->next != NULL)
tmp = tmp->next;
tmp->next = ptr;
ptr->prev = tmp;
}
}

void destroylist()
{
node *tmp = head;
node *tmp1;
while (tmp != NULL)
{
tmp1 = tmp;
printf("Nodes values %d\n", tmp->data);
tmp = tmp->next;
free (tmp1);
}
}

void reverselist (node *n)
{
node *tmp;
if ( n->next != NULL )
{
reverselist(n->next);
tmp = n->next;
n->next = n->prev;
n->prev =tmp;
}
else {
head = n;
n->next = n->prev;
n->prev = NULL;
}
}

void insertnode (int data, node *n)
{
node *ptr;
node *tmp;
if ((ptr = (node *) malloc (sizeof (node))) == NULL)
{
printf ("Memory allocation failed \n");
exit (-1);
}
ptr->data=data;
ptr->next=NULL;
ptr->prev=NULL;
if (head == NULL)
{
ptr->next = NULL;
ptr->prev = NULL;
}
else
{
ptr->next=n->next;
ptr->prev=n;
if (ptr->next != NULL)
ptr->next->prev = ptr;
n->next=ptr;
}
}

3) Binary tree

#include

typedef struct node {
int data;
struct node *left;
struct node *right;
}node;
node *root;
void createlist (int );
void mirror (node * );
void display (node *n);
int main (int argc, char *argv[])
{
int data;
int count;
int i;
scanf("%d", &count);
for (i=0;idata = data;
tmp->left = NULL;
tmp->right = NULL;
if (root == NULL)
{
root=tmp;
return;
}
tmp1= &root;
while (*tmp1 != NULL)
{
if ( data < (*tmp1)->data)
tmp1= & (*tmp1)->left;
else
tmp1= & (*tmp1)->right;
}
*tmp1=tmp;
}

void display(node *n)
{
if (n == NULL)
{
return;
}
if (n->left != NULL)
{
display(n->left );
}
printf("Node data is %d\n", n->data);
if (n->right != NULL)
{
display(n->right );
}
}

void mirror(node *n)
{
node *tmp;
if (n == NULL)
return;
else if (n->left != NULL)
{
mirror(n->left);
}
else if (n->right != NULL)
{
mirror(n->right);
}
tmp = n->right;
n->right = n->left;
n->left = tmp;
}

4) State machine

#include
enum STATES {
stateA,
stateB,
stateC,
stateD,
stateE,
stateF
};
int statetransition (int currentState, int input);
int main (int argc, char *argv[])
{
enum STATES inputstate= stateA;
enum STATES currstate;
currstate=statetransition(inputstate, 'a');
printf("Current state is %d\n", currstate);
currstate=statetransition(inputstate, 'b');
printf("Current state is %d\n", currstate);
}
int statetransition (int currentState, int input)
{
int outstate;
switch (input) {
case 'a':
outstate=stateA;
break;
case 'b':
if(currentState == stateA)
outstate=stateB;
else
outstate=stateA;
break;
case 'c':
if(currentState == stateB)
outstate=stateC;
else
outstate=stateA;
break;
case 'd':
if(currentState == stateC)
outstate=stateD;
else
outstate=stateA;
break;
case 'e':
if (currentState == stateD)
outstate=stateE;
else
outstate=stateA;
break;
case 'f':
if (currentState == stateE)
outstate=stateF;
else
outstate=stateA;
break;
default:
outstate=stateA;
break;
}
return outstate;
}