DATA  STRUCTURE PROGRAMMING

Single linkedlist:

1.#include
  #include
  #include
  #include
  struct sll
   {
  char item[40];
  struct sll *next;
   };
 typedef struct sll node;
main()
 {
  node *start;
  int choice;
  int menu(void);
void create(node*);
node *insert(node*);
node *delete(node*);
void display(node*);
clrscr();
do
{
choice=menu();
switch(choice)
{
case 1:
start=(node*)malloc(sizeof(node));
create(start);
printf("\n");
display(start);
continue;
case 2:
start=insert(start);
printf("\n");
display(start);
continue;
case 3:
start=delete(start);
printf("\n");
display(start);
continue;
default:
printf("End of computation \n");
}
}
while (choice!=4);
}
int menu(void)
{
int choice;
x:
printf("\n\n MAIN MENU: \n");
printf("\t 1-->CREATE the linked list \n");
printf("\t 2-->ADD a component \n");
printf("\t 3-->DELETE a component \n");
printf("\t 4-->EXIT \n");
printf("\n Please enter ur choice: ");
scanf("%d",&choice);
if(choice<1||choice>4)
{
printf("\n ERROR-please try again \n");
goto x;
printf("\n");
return(choice);
}
void create(node *record)
{
printf("Data item(type `end' when finished): ");
fflush(stdin);
gets(record->item);
if(strcmp(record->item,"end")==0)
record->next=NULL;
else
{
record->next=(node*)malloc(sizeof(node));
create(record->next);
}
return;
}
void display(node *record)
{
if(record->next!=NULL)
{
printf("%s \n",record->item);
display(record->next);
}
return;
}
node *insert(node *first)
{
node *locate(node*,char[]);
node *newrecord;
node *tag;
char newitem[40];
char target[40];
printf("\n New Data Item: ");
fflush(stdin);
gets(newitem);
printf("\n Place before(type `end' if last): ");
fflush(stdin);
gets(target);
if(strcmp(first->item,target)==0)
{
newrecord=(node*)malloc(sizeof(node));
strcpy(newrecord->item,newitem);
newrecord->next=first;
first=newrecord;
}
else
{
tag=locate(first,target);
if(tag==NULL)
printf("\n Match not found-Please try again \n");
else
{
newrecord=(node*)malloc(sizeof(node));
strcpy(newrecord->item,newitem);
newrecord->next=tag->next;
tag->next=newrecord;
}
}
return(first);
}
node *locate(node *record,char target[])
{
if(strcmp(record->next->item,target)==0)
return(record);
else
if(record->next->next==NULL)
return(NULL);
else
locate(record->next,target);
}
node *delete(node *first)
{
node *locate(node*,char[]);
node *tag;
node *temp;
char target[40];
printf("\n Data item to be deleted: ");
fflush(stdin);
gets(target);
if(strcmp(first->item,target)==0)
{
temp=first->next;
free(first);
first=temp;
}
else
tag=locate(first,target);
if(tag==NULL)
printf("\n Match not found-Please try again \n");
else
{
temp=tag->next->next;
free(tag->next);
tag->next=temp;
}
return(first);
}

2.Linked list:

#include
#include
#include
#include
struct stru{
char name[20];
struct stru *next;
}*head,*tail,*ptr,*p;
void modify();
void add();
void insert();
void del();
void display();
int find(char *);
typedef struct stru st;
int val,i;
void main()
{
int ch;
char *nm;
clrscr();
printf("Enter the number of values u want :");
scanf("%d",&val);
p=(st *)malloc(sizeof(st));
if((ptr=(st *)malloc(sizeof(st)*val))==NULL)
{
printf("Unable to allocate memory ");
exit(1);
}

head->next=&ptr[0];
for(i=0;inext=NULL;
display();
printf("\nEnter the name to find :");
scanf("%s",nm);
find(nm);
printf("\n1. Insert ");
printf("\n2. Add ");
printf("\n3. Modify ");
printf("\n4. Delete ");
printf("\n5. Exit");
printf("\nEnter your choice :");
scanf("%d",&ch);
switch(ch)
{
case 1:
 insert();
 break;
case 2:
 add();
 break;
case 3:
 modify();
 break;
case 4:
 del();
 break;
default:
 exit(0);
}
getch();
}
void display()
{
 p=(st *)malloc(sizeof(st));
 p=head->next;
  while(p->next!=NULL)
   {
    printf("\nName = %s ",p->name);
    p=p->next;
   }
}
int find(char *c)
{
 int re;
 int flag=0;
 p=(st *)malloc(sizeof(st));
 p=head->next;
 i=0;
  while(p->next!=NULL)
   {
    if(strcmp(p->name,c)==0)
   {
    printf("\nString found at %d ",i+1);
    flag=1;
   }
 i++;
 p=p->next;
}
if(flag!=0)
 {
 return 1;
 }
else
 {
 printf("\nString not found ");
 return 0;
 }
}
int n;
void insert()
{
st ins;
printf("Enter value after which you want to insert :");
scanf("%d",&n);
printf("Enter name :");
scanf("%s",&ins.name);
ptr[n-1].next=&ins;
ins.next=ptr[n-1].next->next;
display();
}
void add()
{
int n;
s addnm;
printf("Enter name :");
scanf("%s",&addnm.name);
ptr[val-1].next=&addnm;
addnm.next=ptr[n-1].next->next;
display();
}
void modify()
{
int n;
st modi;
printf("Enter value which you want to modify :");
scanf("%d",&n);
printf("Enter name :");
scanf("%s",&modi.name);
ptr[n-2].next=&modi;
modi.next=ptr[n-2].next->next;
display();
}
void del()
{
printf("Enter the no to delete ");
scanf("%d",&n);
ptr[n-2].next=ptr[n-2].next->next;
}
3.Tree Traversal

#include
#include
#include"alloc.h"
struct btreenode
{
struct btreenode *leftchild ;
int data ;
struct btreenode *rightchild ;
};
void insert(struct btreenode **,int);
void postorder(struct btreenode *);
void preorder(struct btreenode *);
void inorder(struct btreenode *);
void main()
{
struct btreenode *bt ;
int req,i=1,num;
bt=NULL ; /* empty tree */
clrscr();
printf("Specify the number of data items to be inserted: " ) ;
scanf("%d",&req);
while (i++<=req)
{
printf("Enter the data :" ) ;
scanf("%d",&num);
insert(&bt,num);
}
printf("\nInorder Traversal:" );
inorder (bt);
printf ("\n\n\nPreorder Traversal:" );
preorder(bt);
printf ("\n\n\nPostorder Traversal: " );
postorder(bt);
getch();
}
/* inserts a new node in a binary search tree */
void insert(struct btreenode **sr,int num)
{
if(*sr==NULL)
{
*sr=malloc(sizeof(struct btreenode));
(*sr)->leftchild=NULL;
(*sr)->data=num;
(*sr)->rightchild=NULL;
}
else /* search the node to which new node will be attached */
{
/* if new data is less, traverse to left */
if(num<(*sr)->data)
insert(&((*sr)->leftchild),num ) ;
else
/* else traverse to right */
insert(&((*sr)->rightchild),num);
}
}
/*traverse a binary search tree in a LDR (Left-Data-Right) fashion */
void inorder (struct btreenode *sr )
{
if(sr!=NULL)
{
inorder(sr->leftchild) ; 
printf(" %d ",sr->data) ;
inorder(sr->rightchild) ;
}
}
/* traverse a binary search tree in a DLR (Data-Left-right) fashion */
void preorder(struct btreenode *sr )
{
if(sr!=NULL)
{
/* print the data of a node */
printf(" %d ",sr->data); /* traverse till leftchild is not NULL */
preorder(sr->leftchild);
/* traverse till rightchild is not NULL */
preorder(sr->rightchild);
}
}
/* traverse a binary search tree in LRD (Left-Right-Data) fashion */
void postorder(struct btreenode *sr )
{
if(sr!=NULL )
{
postorder(sr->leftchild);
postorder(sr->rightchild);
printf( "%d ",sr->data);
}
}
4.Stack

 // to implement stack in an array
#include
#include
#include
int top=-1;
char ch;
void push(int a[]);
void pop(int a[]);
void display(int a[]);
void main()
{

int i,a[10];
do
{
clrscr();
gotoxy(10,10);
printf(" 1 --> Insert And Display");
gotoxy(10,12);
printf(" 2 --> Delete And Display ");
gotoxy(10,14);
printf(" 3 --> Display ");
gotoxy(10,16);
printf(" 4 --> Exit ");
gotoxy(10,18);
printf(" Enter choice ");
scanf("%d",&i);
switch(i)
{
case 1 : push(a);
display(a);
break;

case 2 : pop(a);
display(a);
break;

case 3 : display(a);
break;

case 4 : getch();
exit(1);

default : printf("\n wrong choice : - ");
}
printf("\n Do you want to continue : - ");
fflush(stdin);
ch=getchar();
}
while(ch=='y' || ch=='Y');
getch();
}

void push(int a[])
{
do{
if(top==9)
printf("\n the stack is overflow ");
else
{
top++;
printf("\n enter a element to be inserted : - ");
scanf("%d",&a[top]);
}
printf("do you want to continue");
fflush(stdin);
ch=getchar();
}while(ch=='y'||ch=='Y');
}
void display(int a[ ])
{
int i;
if(top==-1)
printf("\n stack is empty ");
else
{

printf("\n\n elements : - \n ");
for(i=0;i<=top;i++)
printf("%d \t ",a[i]);
}
}
void pop(int a[ ])
{
do{
if(top==-1)
printf("\n stack is empty ");
else
{
printf("\n %d is deleted ",a[top]);
top--;
}
printf("do you want to continue");
fflush(stdin);
ch=getchar();
}while(ch=='y'|| ch=='Y');
}

5.Queue

/* INSERTION AND DELETION IN A QUEUE ARRAY IMPLEMENTATION */
/* queue_a.c */

# include
# include
# include
# include
# define size 10

int rear, front;
int ch;
int q[size];

int rear = 0;
int front = 0;
void Insert_queue();
void Delete_queue();
void Display_queue();

/* Function to create queue */

void Insert_queue()
{
printf("\n Input the element :");
scanf("%d", &ch);
if(rear < size)
{
rear ++;
q[rear] = ch ;
if(front == 0)
front = 1;
}
else
printf("\n Queue is overflow");
}

/* Function to perform delete operation */

void Delete_queue()
{
if (front == 0)
{
printf("\n Underflow");
return ;
}
else
{
ch = q[front];

printf("\n Element deleted : %d", ch);
}
if(front == rear)
{
front = 0;
rear = 0;
}
else
front = front + 1;
}

/* Output function */

void Display_queue()
{
int i;
if (front == 0)
return;
for(i = front ; i <= rear; i++)
printf(" %d ", q[i]);
}

/* Function main */

void main()
{
int k = 0;
char choice;
clrscr();
do
{
printf("\nInsert->i Delete->d Quit->q:");
printf("\nInput the choice : ");
do
{
choice = getchar();
choice = tolower(choice);
}
while(strchr("idq",choice)==NULL);
printf("Your choice is: %c ", choice);

switch(choice)
{
case 'i' :
Insert_queue();
printf("\nQueue after inserting ");
Display_queue();
break;

case 'd' :
Delete_queue();
printf("\nQueue content after deleteion is as follows:\n");
Display_queue();
break;

case 'q':
k = 1;
}
} while(!k);
}
                           

 

  

    Source: geocities.com/subrato_ranjan