Add two long positive intergers
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#include<ctype.h>
struct node
{
int data;
struct node*next;
};
void insert(struct node**p,int num)
{
struct node*temp;
if(*p==NULL)
{
(*p)=(struct node*)malloc(sizeof(struct node));
(*p)->next=NULL;
(*p)->data=num;
}
else
{
temp=(struct node*)malloc(sizeof(struct node));
temp->next=(*p);
(*p)=temp;
(*p)->data=num;
}
}
void add_in(struct node*a,struct node*b,struct node**c)
{
int d,carry;
carry=0;
struct node*t;
while(a!=NULL&&b!=NULL)
{
d=(a->data+b->data+carry)%10;
insert(c,d);
if( (a->data+b->data+carry) >= 10)
{
carry=1;
}
else carry=0;
a=a->next;
b=b->next;
}
if(a==NULL&&b==NULL)
{
return;
}
else
{if(a!=NULL&&b==NULL)
{
t=a;
}
else
{
t=b;
}
while(t!=NULL)
{
d=(carry+t->data)%10;
if((carry+t->data)>=10)
carry=1;
else
carry=0;
insert(c,d);
t=t->next;
}
if(carry==1)
insert(c,carry);
}
}
void numin(struct node**p)
{
*p=NULL;char c='c';
while(c!='n')
{
c=getch();
if(!isdigit(c))
return;
else
{
putch(c);
insert(p,c-'0');
}
}
}
void disp(struct node*p)
{
if(p==NULL)
return;
else
{
printf("%d",p->data);
disp(p->next);
}
}
void main()
{
struct node *a,*b,*c;
clrscr();
a=b=c=NULL;
printf("Enter the first number....");
numin(&a);
printf("Enter the second number....");
numin(&b);
printf("The added result is...");
add_in(a,b,&c);
disp(c);
getch();
}
Basic binary search tree routines
#include <stdio.h>
#include <stdlib.h>
struct tnode {
int data;
struct tnode *left;
struct tnode *right;
};
/* insert, swap, search value, search minimum and search maximum values */
struct tnode *tnode_insert(struct tnode *p, int value);
struct tnode *tnode_swap(struct tnode *p);
struct tnode *tnode_search(struct tnode *p, int key);
struct tnode *tnode_searchmin(struct tnode *p);
struct tnode *tnode_searchmax(struct tnode *p);
/* destroy, count tree nodes */
void tnode_destroy(struct tnode *p);
int tnode_count(struct tnode *p);
/* print binary tree inorder, preorder, postorder [recursive] */
void print_inorder(struct tnode *p);
void print_preorder(struct tnode *p);
void print_postorder(struct tnode *p);
int main(void) {
int demo_nr[] = {1, 3, 4, 7, 2, 9, 9, 0, 5, 6, 8, 7, 1, 2, 4};
struct tnode *root = NULL;
struct tnode *searchval = NULL;
int querry = 0;
int i = 0;
/* demo: insert some nr's into the binary tree */
for(i = 0; i < 15; i++)
root = tnode_insert(root, demo_nr[i]);
printf("=-=-=\n");
printf("Total number of tree nodes: %d\n", tnode_count(root));
printf("inorder : ");
print_inorder(root);
printf("\n");
printf("preorder : ");
print_preorder(root);
printf("\n");
printf("postorder: ");
print_postorder(root);
printf("\n");
printf("=-=-=\n");
printf("Enter integer, find: ");
scanf("%d", &querry);
searchval = tnode_search(root, querry);
if(searchval == NULL)
printf(" * %d Not! found in btree\n", querry);
else
printf(" * Found! %d in btree\n", searchval->data);
searchval = NULL;
printf("Searching for Minimum value\n");
searchval = tnode_searchmin(root);
if(searchval == NULL)
printf(" * Minimum Not! found in btree ?\n");
else
printf(" * Found! minimum value %d in btree\n", searchval->data);
searchval = NULL;
printf("Searching for Maximum value\n");
searchval = tnode_searchmax(root);
if(searchval == NULL)
printf(" * Maximum Not! found in btree ?\n");
else
printf(" * Found! Maximum value %d in btree\n", searchval->data);
printf("=-=-=\n");
printf("Exchanging all tree nodes: left <-> right\n");
root = tnode_swap(root);
printf("inorder : ");
print_inorder(root);
printf("\n");
printf("preorder : ");
print_preorder(root);
printf("\n");
printf("postorder: ");
print_postorder(root);
printf("\n");
printf("=-=-=\n");
printf("Destroying btree... bye!\n");
tnode_destroy(root);
return 0;
}
/* insert a tnode into the binary tree */
struct tnode *tnode_insert(struct tnode *p, int value) {
struct tnode *tmp_one = NULL;
struct tnode *tmp_two = NULL;
if(p == NULL) {
/* insert [new] tnode as root node */
p = (struct tnode *)malloc(sizeof(struct tnode));
p->data = value;
p->left = p->right = NULL;
} else {
tmp_one = p;
/* Traverse the tree to get a pointer to the specific tnode */
/* The child of this tnode will be the [new] tnode */
while(tmp_one != NULL) {
tmp_two = tmp_one;
if(tmp_one ->data > value)
tmp_one = tmp_one->left;
else
tmp_one = tmp_one->right;
}
if(tmp_two->data > value) {
/* insert [new] tnode as left child */
tmp_two->left = (struct tnode *)malloc(sizeof(struct tnode));
tmp_two = tmp_two->left;
tmp_two->data = value;
tmp_two->left = tmp_two->right = NULL;
} else {
/* insert [new] tnode as left child */
tmp_two->right = (struct tnode *)malloc(sizeof(struct tnode));
tmp_two = tmp_two->right;
tmp_two->data = value;
tmp_two->left = tmp_two->right = NULL;
}
}
return(p);
}
/* print binary tree inorder */
void print_inorder(struct tnode *p) {
if(p != NULL) {
print_inorder(p->left);
printf("%d ", p->data);
print_inorder(p->right);
}
}
/* print binary tree preorder */
void print_preorder(struct tnode *p) {
if(p != NULL) {
printf("%d ", p->data);
print_preorder(p->left);
print_preorder(p->right);
}
}
/* print binary tree postorder */
void print_postorder(struct tnode *p) {
if(p != NULL) {
print_postorder(p->left);
print_postorder(p->right);
printf("%d ", p->data);
}
}
/* returns the total number of tree nodes */
int tnode_count(struct tnode *p) {
if(p == NULL)
return 0;
else {
if(p->left == NULL && p->right == NULL)
return 1;
else
return(1 + (tnode_count(p->left) + tnode_count(p->right)));
}}
/* exchange all left and right tnodes */
struct tnode *tnode_swap(struct tnode *p) {
struct tnode *tmp_one = NULL;
struct tnode *tmp_two = NULL;
if(p != NULL) {
tmp_one = tnode_swap(p->left);
tmp_two = tnode_swap(p->right);
p->right = tmp_one;
p->left = tmp_two;
}
return(p);
}
/* locate a value in the btree */
struct tnode *tnode_search(struct tnode *p, int key) {
struct tnode *temp;
temp = p;
while(temp != NULL) {
if(temp->data == key)
return temp;
else if(temp->data > key)
temp = temp->left;
else
temp = temp->right;
}
return NULL;
}
/* locate a minimum value in the btree */
struct tnode *tnode_searchmin(struct tnode *p) {
if(p == NULL)
return NULL;
else
if(p->left == NULL)
return p;
else
return tnode_searchmin(p->left);
}
/* locate a maximum value in the btree */
struct tnode *tnode_searchmax(struct tnode *p) {
if(p != NULL)
while(p->right != NULL)
p = p->right;
return p;
}
/* destroy the binary tree */
void tnode_destroy(struct tnode *p) {
if(p != NULL) {
tnode_destroy(p->left);
tnode_destroy(p->right);
free(p);
}
}
Basic double linked list fragment
#include <stdio.h>
#include <stdlib.h>
struct dllist {
int number;
struct dllist *next;
struct dllist *prev;
};
struct dllist *head, *tail;
void append_node(struct dllist *lnode);
void insert_node(struct dllist *lnode, struct dllist *after);
void remove_node(struct dllist *lnode);
int main(void) {
struct dllist *lnode;
int i = 0;
/* add some numbers to the double linked list */
for(i = 0; i <= 5; i++) {
lnode = (struct dllist *)malloc(sizeof(struct dllist));
lnode->number = i;
append_node(lnode);
}
/* print the dll list */
for(lnode = head; lnode != NULL; lnode = lnode->next) {
printf("%d\n", lnode->number);
}
/* destroy the dll list */
while(head != NULL)
remove_node(head);
return 0;
}
void append_node(struct dllist *lnode) {
if(head == NULL) {
head = lnode;
lnode->prev = NULL;
} else {
tail->next = lnode;
lnode->prev = tail;
}
tail = lnode;
lnode->next = NULL;
}
void insert_node(struct dllist *lnode, struct dllist *after) {
lnode->next = after->next;
lnode->prev = after;
if(after->next != NULL)
after->next->prev = lnode;
else
tail = lnode;
after->next = lnode;
}
void remove_node(struct dllist *lnode) {
if(lnode->prev == NULL)
head = lnode->next;
else
lnode->prev->next = lnode->next;
if(lnode->next == NULL)
tail = lnode->prev;
else
lnode->next->prev = lnode->prev;
}
Basic hash example
#include <stdio.h>
#include <stdlib.h>
#define HASHSIZE 1000
#define MAXLINE 1024
typedef struct tnode {
char *data;
struct tnode *next;
} node;
void htable_init(node *hashtable); // fire up hashtable
void htable_insert(node *hashtable, char *str); // insert data into hashtable
void htable_resolve(node *hashtable, int loc, char *str); // resolve collisions in hashtable
void htable_display(node *hashtable); // display hashtable
int htable_delete(node *hashtable, char *str); // delete an entry from hashtable
int htable_hash(char *str); // hash data for hashtable
int main(void) {
char line[MAXLINE];
node *hashtable;
hashtable = (node *)malloc(HASHSIZE * sizeof(node));
htable_init(hashtable);
while((fgets(line, MAXLINE, stdin)) != NULL)
htable_insert(hashtable, line);
htable_display(hashtable);
return 0;
}
/* fire up hashtable */
void htable_init(node *hashtable) {
int i = 0;
for(i = 0; i < HASHSIZE; i++)
hashtable[i].data = NULL, hashtable[i].next = NULL;
}
/* insert data into hashtable */
void htable_insert(node *hashtable, char *str) {
int index = 0;
/*
// determine hash function
*/
index = htable_hash(str);
if(hashtable[index].data != NULL) {
/*
// collision occurs - resolve by chaining
*/
htable_resolve(hashtable, index, str);
} else {
hashtable[index].data = calloc(strlen(str) + 1, sizeof(char));
strcpy(hashtable[index].data, str);
}
}
/* hash data for hashtable */
int htable_hash(char *str) {
int index = 0;
char *tmp = NULL;
tmp = calloc(strlen(str) + 1, sizeof(char));
strcpy(tmp, str);
while(*tmp) {
index += *tmp;
tmp++;
}
index = index % HASHSIZE;
return index;
}
/* resolve collisions in hashtable */
void htable_resolve(node *hashtable, int loc, char *str) {
node *tmp;
tmp = hashtable + loc;
while(tmp->next != NULL)
tmp = tmp->next;
tmp->next = (node *)malloc(sizeof(node));
tmp->next->data = calloc(strlen(str) + 1, sizeof(char));
strcpy(tmp->next->data, str);
tmp->next->next = NULL;
}
/* display hashtable */
void htable_display(node *hashtable) {
int i = 0;
node *target;
for(i = 0; i < HASHSIZE; i++) {
if(hashtable[i].data != NULL) {
target = hashtable + i;
while(target)
/* printf("location: %d, data: %s", i, target->data), target = target->next; */
printf("%s", target->data), target = target->next;
} /* if */
} /* for */
}
/* delete an entry from hashtable */
int htable_delete(node *hashtable, char *str) {
node *bla;
node *blb;
char *tmp = NULL;
int index = 0;
index = htable_hash(str);
/* no item at this location */
if(hashtable[index].data == NULL)
return 1;
/* only one item at this location */
if(hashtable[index].next == NULL) {
if(strcmp(hashtable[index].data, str) == 0) {
/* item found */
tmp = hashtable[index].data;
hashtable[index].data = NULL;
free(tmp);
}
} else {
/* there is a chaining case */
bla = hashtable + index;
/* linked list similar */
while(bla->next != NULL) {
if(strcmp(bla->next->data, str) == 0) {
blb = bla->next;
if(bla->next->next)
bla->next = bla->next->next;
else
bla->next = NULL;
free(blb);
} /* if */
} /* while */
} /* else */
return 0;
}
Basic linked list example .. interactive
#include <stdio.h>
#include <stdlib.h>
struct NODE {
int number;
struct NODE *next;
};
int search_value(struct NODE *llist, int num);
void append_node(struct NODE *llist, int num);
void display_list(struct NODE *llist);
void delete_node(struct NODE *llist, int num);
int main(void) {
int num = 0;
int input = 1;
int retval = 0;
struct NODE *llist;
llist = (struct NODE *)malloc(sizeof(struct NODE));
llist->number = 0;
llist->next = NULL;
while(input != 0) {
printf("\n-- Menu Selection --\n");
printf("0) Quit\n");
printf("1) Insert\n");
printf("2) Delete\n");
printf("3) Search\n");
printf("4) Display\n");
scanf("%d", &input);
switch(input) {
case 0:
default:
printf("Goodbye ...\n");
input = 0;
break;
case 1:
printf("Your choice: `Insertion'\n");
printf("Enter the value which should be inserted: ");
scanf("%d", &num);
append_node(llist, num);
break;
case 2:
printf("Your choice: `Deletion'\n");
printf("Enter the value which should be deleted: ");
scanf("%d", &num);
delete_node(llist, num);
break;
case 3:
printf("Your choice: `Search'\n");
printf("Enter the value you want to find: ");
scanf("%d", &num);
if((retval = search_value(llist, num)) == -1)
printf("Value `%d' not found\n", num);
else
printf("Value `%d' located at position `%d'\n", num, retval);
break;
case 4:
printf("You choice: `Display'\n");
display_list(llist);
break;
} /* switch */
} /* while */
free(llist);
return(0);
}
void display_list(struct NODE *llist) {
while(llist->next != NULL) {
printf("%d ", llist->number);
llist = llist->next;
}
printf("%d", llist->number);
}
void append_node(struct NODE *llist, int num) {
while(llist->next != NULL)
llist = llist->next;
llist->next = (struct NODE *)malloc(sizeof(struct NODE));
llist->next->number = num;
llist->next->next = NULL;
}
void delete_node(struct NODE *llist, int num) {
struct NODE *temp;
temp = (struct NODE *)malloc(sizeof(struct NODE));
if(llist->number == num) {
/* remove the node */
temp = llist->next;
free(llist);
llist = temp;
} else {
while(llist->next->number != num)
llist = llist->next;
temp = llist->next->next;
free(llist->next);
llist->next = temp;
}
}
int search_value(struct NODE *llist, int num) {
int retval = -1;
int i = 1;
while(llist->next != NULL) {
if(llist->next->number == num)
return i;
else
i++;
llist = llist->next;
}
return retval;
}
Basic linked list example
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct llist {
char *str;
struct llist *next;
};
int main(void) {
char line[1024];
struct llist *head = NULL;
struct llist *new = NULL;
while(fgets(line, 1024, stdin) != NULL) {
new = (struct llist *)malloc(sizeof(struct llist));
new->next = head;
head = new;
new->str = strdup(line);
}
while(head != NULL) {
printf("%s\n", head->str);
head = head->next;
}
return 0;
}
Circular Linked List in C
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<alloc.h>
#define null 0
struct node
{
int info;
struct node *link;
}*start;
void main()
{
int ch,n,m,position,i;
last=null;
while(1)
{
printf("1.create
2.addat
3.addbt
4.del
5.disp
6.exit
");
printf("er ur ch");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("er no of itc");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("er the element");
scanf("%d",&m);
create(m);
}break;
case 2:
printf("er the element");
scanf("%d",&m);
addat(m);
break;
case 3:
printf("er the element");
scanf("%d",&m);
printf("er the position");
scanf("%d",&position);
addbt(m,position);
break;
case 4:
if(last==null)
{
printf("list is empty");
continue;
}
printf("er the element for delete");
scanf("%d",&m);
del(m);
break;
case 5:
disp();
break;
case 6:
exit(0);
break;
default:
printf("wrong choice");
}
}
}
create(int data)
{
struct node *q,*tmp;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=data;
tmp->link=null;
if(last==null)
{
last=tmp;
tmp->link=last;
}
else
{
tmp->link=last->link;
last->link=tmp;
last=tmp;
}}
addat(int data)
{
struct node *q,*tmp;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=data;
tmp->link=last->link;
last->link=tmp;
}
addbt(int data,int pos)
{
struct node *tmp,*q;
int i;
q=last->link;;
for(i=0;i<pos-1;i++)
{
q=q->link;
if(q==last->link)
{
printf("there r lessthan %d elements",pos);
return;
}
}
tmp=(struct node *)malloc(sizeof(struct node));
tmp->link=q->link;
tmp->info=data;
q->link=tmp;
if(q==last)
last=tmp;
}
del(int data)
{
struct node *tmp,*q;
if(last->link==last&&last->info==data)
{
tmp=last;
last=null;
free(tmp);
return;
}
q=last->link;
if(q->info==data)
{
tmp=q;
last->link=q->link;
free(tmp);
return;
}
while(q->link!=last)
{
if(q->link->info==data)
{
tmp=q->link;
q->link=tmp->link;
free(tmp);
printf("element %d is deleted",data);
}
if(q->link->info=data)
{
tmp=q->link;
q->link=last->link;
free(tmp);
last=q;
return;}
printf("element%d is not found",data);
}
disp()
{
struct node *q;
if(last==null)
{
printf("list isdempty");
return;
}q=last->link;
while(q!=last)
{
printf("%d",q->info);
q=q->link;
}
printf("%d",last->info);
}
Dynamic (re)size array
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int *a;
int i = 5;
if((a = (int *)malloc(i * sizeof(int))) == NULL) {
fprintf(stderr, "Error: failed malloc\n");
return 1;
}
for(i = 0; i < 5; i++)
a[i] = i;
printf("-- array after malloc\n");
for(i = 0; i < 5; i++)
printf(" a[%d] = %d\n", i, a[i]);
if((a = (int *)realloc(a, i * sizeof(int))) == NULL) {
fprintf(stderr, "Error: failed realloc\n");
return 1;
}
for(i = 0; i < 10; i++)
a[i] = i;
printf("\n-- array after realloc\n");
for(i = 0; i < 10; i++)
printf(" a[%d] = %d\n", i, a[i]);
free(a);
return 0;
}
Dynamic array of structures
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node {
char *str;
int len;
};
int main(void) {
struct node **strarray = NULL;
int i = 0, count = 0;
char line[1024];
while(fgets(line, 1024, stdin) != NULL) {
/* add ONE element to the array */
strarray = (struct node **)realloc(strarray, (count + 1) * sizeof(struct node *));
/* allocate memory for one `struct node` */
strarray[count] = (struct node *)malloc(sizeof(struct node));
/* copy the data into the new element (structure) */
strarray[count]->str = strdup(line);
strarray[count]->len = strlen(line);
count++;
}
/* print the array */
for(i = 0; i < count; i++) {
printf("--\n");
printf("[%d]->str: %s", i, strarray[i]->str);
printf("[%d]->len: %d\n", i, strarray[i]->len);
}
/* free all strarray elements */
for(i = 0; i < count; i++) {
free(strarray[i]->str);
free(strarray[i]);
i++;
}
free(strarray);
return 0;
}
Dynamic string arrays
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main (void) {
char **strarray = NULL;
int i = 0, strcount = 0;
char line[1024];
while((fgets(line, 1024, stdin)) != NULL) {
strarray = (char **)realloc(strarray, (strcount + 1) * sizeof(char *));
strarray[strcount++] = strdup(line);
}
/* print the array of strings */
for(i = 0; i < strcount; i++)
printf("strarray[%d] == %s", i, strarray[i]);
/*
// free the string array
// Note: You must delete each individual string
// before you delete the array of pointers
*/
for(i = 0; i < strcount; i++)
free(strarray[i]);
free(strarray);
return 0;
}
Infix To Prefix Conversion
#include<stdio.h>
#include<conio.h>
#include<string.h>
#define MAX 15
#define true 1
#define false 0
/*Structure Decvlaration*/
typedef struct
{
char data[MAX];
char top;
}STK;
/*Function Declarations*/
void input(char str[]);
void intopre(char str1[],char pre[]);
void intopost(char str1[],char post[]);
int isoperand(char sym);
int prcd(char sym);
void push(STK *s1,char elem);
int pop(STK *s1);
int empty(STK *s2);
int full(STK *s2);
void dis(char str[]);
void main()
{
STK s;
int cs,ans;
char str[MAX],pre[MAX],post[MAX];
clrscr();
do /*Using Do-while Loop*/
{
clrscr();
printf("
-----Program for Expressions-----");
printf("
Input The String:");
printf("
MENU:
");
printf("1.Infix to Prefix
");
printf("2.Infix to Postfix");
printf("
3.Exit");
cs=getche();
switch(cs) /*Using Switch Case*/
{
case 1:
intopre(str,pre);
break;
case 2:
intopost(str,post);
break;
case 3:
break;
default:
printf("
Enter a Valid Choise!"); /*Default Case*/
break;
}
printf("
Do you wish to Continue?(y/n)");
ans=getche();
}while(ans=='y'||ans=='Y'); /*Condition for Do-while loop*/
getch();
}
/*To Input String*/
void input(char str)
{
printf("Enter the Infix String:");
scanf("%s",str);
}
/*To Covert Infix To Prefix*/
void intopre(STK s1,char str1[],char pre[])
{
int len,flag;
len=strlen(str1);
int check=0,cnt=len-1,pos=0;
char elem;
while(cnt>=0) /*while condition*/
{
flag=0;
if(isoperand(str1[cnt])) /*Checking for Operand*/
{
printf("%c",str1[cnt]);
cnt--;
pos++;
}
else
{
check=prcd(str1[cnt]);
while(check==false)
{
pre[pos]=str1[cnt];
flag=1;
pos++;
cnt--;
}
if(flag==0)
{
elem=pop(&s1);
printf("%c",elem);
}
}
}
}
/*To Convert Infix To Postfix*/
void intopost(STK s1,char str1[],char post[])
{
int len;
len=strlen(str1);
int check=0,cnt=len-1,pos=0;
}
/*To Check For Operand*/
int isoperand(char sym)
{
if('A'<sym<'Z'||'a'<sym<'z')
return(true);
return(false);
}
/*To Check The Precedence*/
int prcd(char sym)
{
}
/*To Display String*/
void dis(char str[])
{
}
/*Push Function Definition*/
void push(STK *s1,char elem)
{
if(!full(s1))
{
s1->top++; /*Incrementing top*/
s1->data[s1->top]=elem; /*Storing element*/
}
else
printf("
Stack is Full!");
}
/*Full Function Definition*/
int full(STK *s2)
{
if(s2->top==MAX) /*Condition for Full*/
return(true);
return(false);
}
/*Pop Function Definition*/
int pop(STK *s1)
{
char elem;
if(!empty(s1))
{
elem=s1->data[s1->top]; /*Storing top stack element in elem*/
s1->top--; /*Decrementing top*/
return(elem);
}
return(false);
}
/*Empty Function Definition*/
int empty(STK *s2)
{
if(s2->top==-1) /*Condition For Empty*/
return(true);
return(false);
}
Linked List implementation
#include"m_list.h"
void main()
{
list *first=NULL,*second=NULL,*third=NULL;
int choice,i;
char ch='y';
while(1)
{
clrscr();
printf("
case 1: Create list");
printf("
case 2: Add in the list");
printf("
case 3: Delete in the list");
printf("
case 4: Append two list");
printf("
case 5: show list");
printf("
case 6: Exit");
printf("
Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1: //create list
while(ch!='n')
{
printf("
Enter element : ");
scanf("%d",&i);
create(&first,i);
printf("
Enter element (y/n) : ");
fflush(stdin);
scanf("%c",&ch);
}
break;
case 2: //add in the list
int c;
clrscr();
printf("
case 1: Add in Beginning");
printf("
case 2: Add in End");
printf("
case 3: Add After a given element");
printf("
case 4: Return to main menu");
printf("
Enter your choice : ");
scanf("%d",&c);
switch(c)
{
case 1: add_at_beg(&first);
break;
case 2: add_at_end(&first);
break;
case 3: add_after_given_element(&first);
break;
case 4: break;
}
break;
case 3:
clrscr();
printf("
case 1: Delete in Beginning");
printf("
case 2: Delete in End");
printf("
case 3: Delete a specified element");
printf("
case 4: Return to main menu");
printf("
Enter your choice : ");
scanf("%d",&c);
switch(c)
{
case 1: del_at_beg(&first);
break;
case 2: del_at_end(&first);
break;
case 3: del_specified_element(&first);
break;
case 4: break;
}
break;
case 4:
char ch='y';
printf("Enter element in second list : ");
while(ch!='n')
{
printf("
Enter element : ");
scanf("%d",&i);
create(&second,i);
printf("
Enter element (y/n) : ");
fflush(stdin);
scanf("%c",&ch);
}
append(&third,first,second);
break;
case 5: //show list
clrscr();
printf("
case 1: List 1");
printf("
case 2: List 2");
printf("
case 3: List 3");
printf("
Enter choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1: show(first);break;
case 2: show(second);break;
case 3: show(third);break;
}
break;
case 6: exit(0);
}
}
}
*********************************
#include<conio.h>
#include<stdio.h>
#include<alloc.h>
#include<stdlib.h>
typedef struct list
{
int info;
struct list *next;
};
//.................Function Declaration ...........
void create(struct list **p,int i)
{
struct list *temp,*q=*p;
temp=(struct list*)malloc(sizeof(struct list));
temp->info=i;
temp->next=NULL;
if(*p==NULL)
*p=temp;
else
{
while(q->next!=NULL)
q=q->next;
q->next=temp;
}
}
int append(struct list **t,struct list *f,struct list *s)
{
struct list *temp=*t;
if(f==NULL && s==NULL)
return 0;
while(f)
{
create(t,f->info);
f=f->next;
}
while(s)
{
create(t,s->info);
s=s->next;
}
return 0;
}
void show(struct list *p)
{
if(p==NULL)
printf(" List is Empty");
else
while(p)
{
printf("%d ",p->info);
p=p->next;
}
getch();
}
void add_at_beg(struct list **l)
{
struct list *temp=(struct list *)malloc(sizeof(struct list));
printf("
Enter element : ");
scanf("%d",&temp->info);
temp->next=NULL;
if(*l==NULL)
*l=temp;
else
{
temp->next=*l;
*l=temp;
}
}
void del_at_beg(struct list **l)
{
list *temp;
if(*l==NULL)
{
printf("
List is empty");
getch();
}
else
{
temp=*l;
*l=(*l)->next;
free(temp);
}
}
void add_at_end(struct list **l)
{
list *temp,*p;
temp=(struct list *)malloc(sizeof(struct list));
printf("
Enter element : ");
scanf("%d",&temp->info);
temp->next=NULL;
if(*l==NULL)
*l=temp;
else
{
p=*l;
while(p->next!=NULL)
p=p->next;
p->next=temp;
}
}
void del_at_end(struct list **l)
{
list *temp,*p;
if(*l==NULL)
{
printf("
List is Empty");
getch();
}
else if((*l)->next==NULL)
{
temp=*l;
*l=NULL;
free(temp);
}
else
{
p=*l;
while(p->next->next!=NULL)
p=p->next;
temp=p->next->next;
p->next=NULL;
free(temp);
}
}
void add_after_given_element(list **l)
{
list *temp,*p;
int m;
temp=(struct list *)malloc(sizeof(struct list));
printf("
Enter element : ");
scanf("%d",&temp->info);
printf("
Enter position after which element inserted : ");
scanf("%d",&m);
temp->next=NULL;
if(*l==NULL)
*l=temp;
else
{
p=*l;
while(p->next!=NULL)
if(p->info==m)
break;
else
p=p->next;
temp->next=p->next;
p->next=temp;
}
}
void del_specified_element(list **l)
{
list *temp,*p,*q;
int m;
printf("
Enter element which is deleted : ");
scanf("%d",&m);
if(*l==NULL)
{
printf("
List is Empty");
getch();
}
else if((*l)->next!=NULL && (*l)->info==m)
{
temp=*l;
*l=(*l)->next;
free(temp);
}
else if((*l)->next==NULL && (*l)->info==m)
{
temp=*l;
*l=NULL;
free(temp);
}
else
{
p=*l;
while(p!=NULL)
if(p->info==m)
break;
else
{
q=p;
p=p->next;
}
temp=p;
q->next=p->next;
free(temp);
}
}
Linked list queue example
# include <stdio.h>
# include <stdlib.h>
struct qnode {
int data;
int prio;
struct qnode *next;
};
void quein(struct qnode **, struct qnode **, int , int);
int quedel(struct qnode **, struct qnode **, int *, int *);
int main(void) {
int tab[10] = {2, 8, 3, 5, 4, 9, 6, 7, 1, 0};
struct qnode *first = NULL;
struct qnode *last = NULL;
int val, prio, i;
for(i = 0; i < 10; i++) {
val = tab[i], prio = i;
printf("Inserting: value: %d with priority: %d\n", prio, val);
quein(&first, &last, val, prio);
}
printf("=-=\n");
for(i = 0; i < 11; i++) {
val = tab[i], prio = i;
if(quedel(&first, &last, &val, &prio) != -1)
printf("Deleting: value: %d with priority: %d\n", prio, val);
}
return 0;
}
int quedel(struct qnode **first, struct qnode **last, int *prio, int *val) {
struct qnode *tmp = NULL;
if((NULL == *last) && (*last == *first)) {
fprintf(stderr, "Empty queue.....\n");
return -1;
}
*val = (*first)->data, *prio = (*first)->prio;
tmp = *first, *first = (*first)->next;
if(*last == tmp)
*last = (*last)->next;
free(tmp);
return 0;
}
void quein(struct qnode **first, struct qnode **last, int prio, int val) {
struct qnode *tmp = NULL;
struct qnode *tmp1 = NULL;
tmp = malloc(sizeof(struct qnode));
tmp->data = val;
tmp->prio = prio;
tmp->next = NULL;
if(*last == NULL) {
*last = tmp;
*first = *last;
} else {
if((*first)->prio < prio) {
tmp->next = *first;
*first = tmp;
} else {
if((*last)->prio > prio) {
(*last)->next = tmp;
*last = tmp;
} else {
tmp1 = *first;
while((tmp1->next)->prio >= prio) {
tmp1 = tmp1->next;
}
tmp->next = tmp1->next;
tmp1->next = tmp;
}
}
}
return;
}
Linked list stack example
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct node {
char *str;
struct node *next;
} STACKNODE;
void push(char *key, STACKNODE **stack);
char *pop(STACKNODE **stack);
int isempty(STACKNODE *stack);
char top(STACKNODE *stack);
int main() {
char line[1024];
char *key;
STACKNODE *stack;
stack = NULL;
while((fgets(line, 1024, stdin)) != NULL)
key = line, push(key, &stack);
while(!isempty(stack))
printf("%s", pop(&stack));
return 0;
}
char top(STACKNODE *stack) {
return *stack->str;
}
void push(char *line, STACKNODE **stack) {
STACKNODE *newnode;
newnode = (STACKNODE *)malloc(sizeof(STACKNODE));
newnode->str = strdup(line);
newnode->next = (*stack);
(*stack) = newnode;
}
char *pop(STACKNODE **stack) {
STACKNODE *oldnode;
char *key;
char *retval;
oldnode = (*stack);
key = (*stack)->str;
(*stack) = (*stack)->next;
free(oldnode);
retval = calloc(strlen(key)+1, sizeof(char));
strcpy(retval, key);
return retval;
free(retval);
}
int isempty(STACKNODE *stack) {
return stack == NULL;
}
Program for Circular Queue implementation through Array
#include <stdio.h>
#include<ctype.h>
# define MAXSIZE 200
int cq[MAXSIZE];
int front,rear;
void main()
{
void add(int,int [],int,int,int);
int del(int [],int ,int ,int );
int will=1,i,num;
front = 1;
rear = 1;
clrscr();
printf("
Program for Circular Queue demonstration through array
");
while(will ==1)
{
printf("
MAIN MENU:
1.Add element to Circular Queue
2.Delete element from the Circular Queue
");
scanf("%d",&will);
switch(will)
{
case 1:
printf("
Enter the data... ");
scanf("%d",&num);
add(num,cq,MAXSIZE,front,rear);
break;
case 2: i=del(cq,MAXSIZE,front,rear);
printf("
Value returned from delete function is %d ",i);
break;
default: printf("
Invalid Choice . ");
}
printf("
Do you want to do more operations on Circular Queue ( 1 for yes, any other key to exit) ");
scanf("%d" , &will);
} //end of outer while
} //end of main
void add(int item,int q[],int MAX,int front,int rear)
{
rear++;
rear= (rear%MAX);
if(front ==rear)
{
printf("CIRCULAR QUEUE FULL");
return;
}
else
{
cq[rear]=item;
printf("
Rear = %d Front = %d ",rear,front);
}
}
int del(int q[],int MAX,int front,int rear)
{
int a;
if(front == rear)
{
printf("CIRCULAR STACK EMPTY");
return (0);
}
else
{
front++;
front = front%MAX;
a=cq[front];
return(a);
printf("
Rear = %d Front = %d ",rear,front);
}
}
Program for finding the transpose of a martix in sparse form
#include <stdio.h>
#include <conio.h>
int a[100][100],b[100][100];
void main()
{
int i,m,n,p,q,col,t;
clrscr();
printf("Enter the no. of rows");
scanf("%d", &a[0][0]);
printf("
Enter the no. of cols");
scanf("%d", &a[0][1]);
printf("
Enter the number of non zero terms");
scanf("%d", &a[0][2]);
for(i=1;i<=a[0][2];i++)
{
printf("
Enter the value (that is non zero)");
scanf("%d",&a[i][2]);
printf("
Enter the row for %d : ",a[i][2]);
scanf("%d",&a[i][0]);
printf("
Enter the col for %d : ",a[i][2]);
scanf("%d",&a[i][1]);
}
/* Printing for testing the sparse input */
printf("
*****************************
The martix you entered is
************************
Row Col Value ");
for ( i = 0;i <= a[0][2];i++)
{
printf("
%d %d %d " , a[i][0],a[i][1],a[i][2]);
}
/* Calling function for evaluation of transpose */
m = a[0][0];
n = a[0][1];
t = a[0][2];
b[0][0] = n;
b[0][1] = m;
b[0][2] = t;
q=1;
for( col = 1; col <=n; col++)
{
for(p = 1; p<=t;p++)
{
if(a[p][1] == col)
{
b[q][0] = a[p][1];
b[q][1] =a[p][0];
b[q][2] = a[p][2];
q++;
}
}
} //end of outer for loop
/* Printing the transposed matrix */
getch();
printf("
The Transpose of the above matrix is ");
for ( i = 0;i <= a[0][2];i++)
{
printf("
%d %d %d " , b[i][0],b[i][1],b[i][2]);
}
getch();
}
Hash, use shift-folding snip
#include <stdio.h>
#include <error.h>
#include <string.h>
#include <stdlib.h>
#define MAXLINE 128
#define HTABSIZE 101
#define NSHIFT 3
struct hnode {
int pos;
char *key;
struct hnode *next;
};
typedef struct hnode *hashtable[HTABSIZE];
int htab_key(char *key);
int htab_getval(hashtable h, char *key);
void htab_insert(hashtable h, char *key, int pos);
void htab_dump(hashtable htab);
void htab_free(hashtable htab);
int main(int argc, char *argv[]) {
char line[MAXLINE];
hashtable htab = {0};
int len = 0;
int i = 0;
int retv = 0;
if(argc != 2)
error(1, 0, "querry < input.txt");
while(fgets(line, MAXLINE, stdin) != NULL) {
/* strip newlines */
len = strlen(line);
if(line[len - 1] == '\n')
line[--len] = '\0';
if(len > 2)
htab_insert(htab, line, i++);
}
if((retv = htab_getval(htab, argv[1])) == -1)
printf("NOT found: `%s', `%d'\n", argv[1], retv);
else
printf("FOUND: `%s' at `%d'\n", argv[1], retv);
/* htab_dump(htab); */
htab_free(htab);
return 0;
}
int htab_key(char *key) {
char *ptr = NULL;
int retv = 0;
int i = 0;
int x = 0;
for(ptr = key; *ptr; retv += x)
for(i = 0, x = 0; i < NSHIFT && *ptr; i++, ptr++)
x = x * 10 + *ptr;
retv %= HTABSIZE;
return retv;
}
void htab_insert(hashtable htab, char *key, int pos) {
struct hnode *ptr = (struct hnode *)malloc(sizeof(struct hnode));
int index = htab_key(key);
ptr->key = strdup(key);
ptr->pos = pos;
ptr->next = htab[index];
htab[index] = ptr;
return;
}
int htab_getval(hashtable htab, char *key) {
struct hnode *ptr = {0};
for(ptr = htab[htab_key(key)]; ptr && strcmp(ptr->key, key); ptr = ptr->next)
;
if(ptr)
return ptr->pos;
else
return -1;
}
void htab_dump(hashtable htab) {
struct hnode *ptr = {0};
int i = 0;
for(i = 0; i < HTABSIZE; i++) {
printf("[%02d]: ", i);
for(ptr = htab[i]; ptr; ptr = ptr->next) {
printf("[%d] -> %s", ptr->pos, ptr->key);
}
printf("\n");
}
return;
}
void htab_free(hashtable htab) {
struct hnode *ptr = {0};
struct hnode *tmp = {0};
int i = 0;
for(i = 0; i < HTABSIZE; i++) {
for(ptr = htab[i]; ptr; ptr = ptr->next) {
if(ptr->next != NULL) {
free(ptr->key), tmp = ptr->next;
free(ptr), ptr = tmp;
}
}
}
return;
}
Program for Queue implementation through Array
#include <stdio.h>
#include<ctype.h>
# define MAXSIZE 200
int q[MAXSIZE];
int front, rear;
void main()
{
void add(int);
int del();
int will=1,i,num;
front =0;
rear = 0;
clrscr();
printf("
Program for queue demonstration through array
");
while(will ==1)
{
printf("
MAIN MENU:
1.Add element to queue
2.Delete element from the queue
");
scanf("%d",&will);
switch(will)
{
case 1:
printf("
Enter the data... ");
scanf("%d",&num);
add(num);
break;
case 2: i=del();
printf("
Value returned from delete function is %d ",i);
break;
default: printf("Invalid Choice ... ");
}
printf(" Do you want to do more operations on Queue ( 1 for yes, any other key to exit)");
scanf("%d" , &will);
} //end of outer while
} //end of main
void add(int a)
{
if(rear>MAXSIZE)
{
printf("QUEUE FULL");
return;
}
else
{
q[rear]=a;
rear++;
printf("
Value of rear = %d and the value of front is %d",rear,front);
}
}
int del()
{
int a;
if(front == rear)
{
printf("QUEUE EMPTY");
return(0);
}
else
{
a=q[front];
front++;
}
return(a);
}
Program for Queue implementation through Linked List
#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node *link;
} ;
struct node *front, *rear;
void main()
{
int wish,will,a,num;
void add(int);
wish=1;
clrscr();
front=rear=NULL;
printf("Program for Queue as Linked List demo..
");
while(wish == 1)
{
printf("
Main Menu
1.Enter data in queue
2.Delete from queue
");
scanf("%d",&will);
switch(will)
{
case 1:
printf("
Enter the data");
scanf("%d",&num);
add(num);
//display();
break;
case 2:
a=del();
printf("
Value returned from front of the queue is %d",a);
break;
default:
printf("
Invalid choice");
}
printf("
Do you want to continue, press 1");
scanf("%d",&wish);
}
getch();
}
void add(int y)
{
struct node *ptr;
ptr=malloc(sizeof(struct node));
ptr->data=y;
ptr->link=NULL;
if(front ==NULL)
{
front = rear= ptr;
}
else
{
rear->link=ptr;
rear=ptr;
}
}
int del()
{
int num;
if(front==NULL)
{
printf("
QUEUE EMPTY
");
return(0);
}
else
{
num=front->data;
front = front->link;
printf("
Value returned by delete function is %d
",num);
return(num);
}
}
Program for Stack implementation through Array
#include <stdio.h>
#include<ctype.h>
# define MAXSIZE 200
int stack[MAXSIZE];
int top; //index pointing to the top of stack
void main()
{
void push(int);
int pop();
int will=1,i,num;
clrscr();
while(will ==1)
{
printf("
MAIN MENU:
1.Add element to stack
2.Delete element from the stack
");
scanf("%d",&will);
switch(will)
{
case 1:
printf("
Enter the data... ");
scanf("%d",&num);
push(num);
break;
case 2: i=pop();
printf("
Value returned from pop function is %d ",i);
break;
default: printf("Invalid Choice . ");
}
printf("
Do you want to do more operations on Stack ( 1 for yes, any other key to exit) ");
scanf("%d" , &will);
} //end of outer while
} //end of main
void push(int y)
{
if(top>MAXSIZE)
{
printf("
STACK FULL
");
return;
}
else
{
top++;
stack[top]=y;
}
}
int pop()
{
int a;
if(top<=0)
{
printf("
STACK EMPTY
");
return 0;
}
else
{
a=stack[top];
top--;
}
return(a);
}
Program to add two polynomials
#include<stdio.h>
#include<conio.h>
struct barbie
{
int coff;
int pow;
struct barbie *link;
}*ptr,*start1,*node,*start2,*start3,*ptr1,*ptr2;
typedef struct barbie bar;
int temp1,temp2;
void main()
{
void create(void);
void prnt(void);
void suml(void);
void sort(void);
clrscr();
printf("
Enrter the elements of the first poly :");
node = (bar *) malloc(sizeof (bar));
start1=node;
if (start1==NULL)
{
printf("
Unable to create memory.");
getch();
exit();
}
create();
printf("
Enrter the elements of the second poly :");
node = (bar *) malloc(sizeof (bar));
start2=node;
if (start2==NULL)
{
printf("
Unable to create memory.");
getch();
exit();
}
create();
clrscr();
//printing the elements of the lists
printf("
The elements of the poly first are :");
ptr=start1;
prnt();
printf("
The elements of the poly second are :");
ptr=start2;
prnt();
printf("
The first sorted list is :");
ptr=start1;
sort();
ptr=start1;
prnt();
printf("
The second sorted list is :");
ptr=start2;
sort();
ptr=start2;
prnt();
printf("
The sum of the two lists are :");
suml();
ptr=start3;
prnt();
getch();
}
/*-----------------------------------------------------------------------------*/
void create()
{
char ch;
while(1)
{
printf("
Enter the coff and pow :");
scanf("%d%d",&node->coff,&node->pow);
if (node->pow==0 )
{
ptr=node;
node=(bar *)malloc(sizeof(bar));
node=NULL;
ptr->link=node;
break;
}
printf("
Do u want enter more coff ?(y/n)");
fflush(stdin);
scanf("%c",&ch);
if (ch=='n' )
{
ptr=node;
node=(bar *)malloc(sizeof(bar));
node=NULL;
ptr->link=node;
break;
}
ptr=node;
node=(bar *)malloc(sizeof(bar));
ptr->link=node;
}
}
/*-------------------------------------------------------------------------*/
void prnt()
{ int i=1;
while(ptr!=NULL )
{
if(i!=1)
printf("+ ");
printf(" %dx^%d ",ptr->coff,ptr->pow);
ptr=ptr->link;
i++;
}
//printf(" %d^%d",ptr->coff,ptr->pow);
}
/*---------------------------------------------------------------------------*/
void sort()
{
for(;ptr->coff!=NULL;ptr=ptr->link)
for(ptr2=ptr->link;ptr2->coff!=NULL;ptr2=ptr2->link)
{
if(ptr->pow>ptr2->pow)
{
temp1=ptr->coff;
temp2=ptr->pow;
ptr->coff=ptr2->coff;
ptr->pow=ptr2->pow;
ptr2->coff=temp1;
ptr2->pow=temp2;
}
}
}
/*---------------------------------------------------------------------------*/
void suml()
{
node=(bar *)malloc (sizeof(bar));
start3=node;
ptr1=start1;
ptr2=start2;
while(ptr1!=NULL && ptr2!=NULL)
{
ptr=node;
if (ptr1->pow > ptr2->pow )
{
node->coff=ptr2->coff;
node->pow=ptr2->pow;
ptr2=ptr2->link; //update ptr list B
}
else if ( ptr1->pow < ptr2->pow )
{
node->coff=ptr1->coff;
node->pow=ptr1->pow;
ptr1=ptr1->link; //update ptr list A
}
else
{
node->coff=ptr2->coff+ptr1->coff;
node->pow=ptr2->pow;
ptr1=ptr1->link; //update ptr list A
ptr2=ptr2->link; //update ptr list B
}
node=(bar *)malloc (sizeof(bar));
ptr->link=node; //update ptr list C
}//end of while
if (ptr1==NULL) //end of list A
{
while(ptr2!=NULL)
{
node->coff=ptr2->coff;
node->pow=ptr2->pow;
ptr2=ptr2->link; //update ptr list B
ptr=node;
node=(bar *)malloc (sizeof(bar));
ptr->link=node; //update ptr list C
}
}
else if (ptr2==NULL) //end of list B
{
while(ptr1!=NULL)
{
node->coff=ptr1->coff;
node->pow=ptr1->pow;
ptr1=ptr1->link; //update ptr list B
ptr=node;
node=(bar *)malloc (sizeof(bar));
ptr->link=node; //update ptr list C
}
}
node=NULL;
ptr->link=node;
}
Program to demonstrate linked list operations
# include<stdio.h>
# include<conio.h>
# include "malloc.h"
struct node
{
int data;
struct node *link;
};
void main()
{
int a=111,b=2,c=3,will,wish,num;
struct node *ptr,*ptr2,*result,*temp;
void add(struct node **,int );
struct node * search(struct node *);
void display(struct node *);
void invert(struct node *);
void del(struct node *,int);
struct node * concat(struct node *,struct node *);
ptr=NULL;
ptr2=NULL;
result=NULL; //result for storing the result of concatenation
clrscr();
will=1;
while(will==1)
{
printf("
Main Menu
1. Add element
2.Delete element
3.Search element
4Linked List concatenation
5.Invert linked list
6. Display elements
Please enter the choice");
scanf("%d",&wish);
switch(wish)
{
case 1:
printf("
Enter the element you want to add ");
scanf("%d",&num);
add(&ptr,num);
display(ptr);
break;
case 2:
printf("
Enter the element to delete ");
scanf("%d",&num);
del(ptr,num);
break;
case 3:
printf("
Now demonstrating search ");
temp = search(ptr);
printf("
Address of first occurence is %u ",temp);
break;
case 4:
/* Inputs given internally for demo only */
printf(" Now demonstrating linked list concatenation
Press any key to continue...");
add(&ptr2,2);
add(&ptr2,4);
add(&ptr2,6);
getch();
printf("
Displaying second Linked List
");
display(ptr2);
getch();
result = concat(ptr,ptr2);
clrscr();
printf("
Now Displaying the result of concatenation");
display(result);
getch();
break;
case 5:
printf("
Inverting the list ...
Press any key to continue...");
invert(ptr);
break;
case 6:
display(ptr);
break;
default:
printf("
Illegal choice
");
}
printf("
DO you want to continue ( press 1 for yes ");
scanf("%d",&will);
} //end of while
}
void add(struct node **q,int num)
{
struct node *temp;
temp = *q;
if(*q==NULL)
{
*q=malloc(sizeof(struct node));
temp = *q;
}
else
{
while((temp->link)!=NULL)
{
temp=temp->link;
}
temp->link = malloc(sizeof(struct node));
temp=temp->link;
}
temp->data = num;
temp->link = NULL;
}
void display(struct node *pt)
{
while(pt!=NULL)
{
printf("
Data : %d",pt->data);
printf("
Link : %d",pt->link);
pt=pt->link;
}
}
void invert(struct node *ptr)
{
struct node *p,*q,*r;
p=ptr;
q=NULL;
while(p!=NULL)
{
r=q;
q=p;
p=p->link;
q->link=r;
}
ptr = q;
display(ptr);
}
// CONCATENATION OF LINKED LISTS
struct node * concat(struct node *p,struct node *q)
{
struct node *x,*r;
if (p==NULL)
r=q;
if (q==NULL)
r=p;
else
{
x=p;
r=x;
while(x->link!=NULL)
x=x->link;
x->link=q;
}
return(r);
}
// SEARCHING AN ELEMENT IN THE LINKED LIST
// THIS FUNCTION FINDS THE FIRST OCCURENCE OF
// A DATA AND RETURNS A POINTER TO ITS ADDRESS
struct node * search(struct node *p)
{
struct node *temp;
int num;
temp = p;
printf("
Enter the data that you want to search ");
scanf("%d",&num);
printf("
Link of temp %u", temp->link);
while(temp->link!=NULL)
{
printf("
In while ");
if(temp->data == num)
return(temp);
temp=temp->link;
}
return(NULL);
}
// DELETING DATA FROM THE LINKED LIST//
void del(struct node *p,int num)
{
struct node *temp,*x;
temp=p;
x= NULL;
while (temp->link !=NULL)
{
if(temp->data == num)
{
if (x==NULL)
{
p = temp->link;
free(temp);
return;
}
else
{
x->link = temp->link;
free(temp);
return;
}
} //end of outer if
x=temp;
temp=temp->link;
} //end of while
printf("
No such entry to delete ");
} //end of fn.
Program to implement Stack as Linked List
#include<stdio.h>
#include<conio.h>
# include "malloc.h"
struct node
{
int data;
struct node *link;
} ;
struct node *top;
void main()
{
void push(int);
void display();
int wish, num,will,a;
wish = 1;
top = NULL;
clrscr();
printf("Program for Stack as Linked List demo..
");
while(wish == 1)
{
printf("
Main Menu
1.Enter data in stack
2.Delete from stack
");
scanf("%d",&will);
switch(will)
{
case 1:
printf("
Enter the data");
scanf("%d",&num);
push(num);
display();
break;
case 2:
a=pop();
printf("
Value returned from top of the stack is %d",a);
break;
default:
printf("
Invalid choice");
}
printf("
Do you want to continue, press 1");
scanf("%d",&wish);
}
}
void push(int y)
{
struct node *x;
x=malloc(sizeof(struct node));
printf("
Address of newly created node x is %d",x);
x->data = y;
x->link = top;
top = x;
}
void display()
{
int i =0;
struct node * temp;
temp = top;
while(temp!=NULL)
{
printf("
Item No. %d : Data %d Link %d ",i++,temp->data,temp->link);
temp=temp->link;
}
}
/// THIS FUNCTION REMOVES TOP NODE FROM THE STACK AND RETURNS ITS VALUE///
int pop()
{
int a;
if(top==NULL)
{printf("
STACK EMPTY...
"); return 0;}
else
{
a=top->data;
printf("The value returned is %d ",a);
free(top);
top=top->link; return (a);
}
}
Queue implementation using single linkedlist
#include<stdio.h>
#include<stdlib.h>
struct node
{
int n;
struct node* next;
};
typedef struct node sn;
sn *qit(sn *);
sn *rit(sn *);
sn *q =NULL;
static int k=1;
int main()
{
char i;
sn *qp;
do
{
printf("
Press 1 to put an element in queue
");
printf("Press 2 to remove an element from queue
");
printf("Press any other to exit
");
printf("
Enter choice:");
scanf("%d",&i);
switch(i)
{
case 1:
if(k==1)
{
k=0;
qp=malloc(sizeof(sn));
q=qp;
printf("Enter element:");
scanf("%d",&qp->n);
qp->next = NULL;
break;
}
else
{
q = qit(q);
break;
}
case 2:
if(k==1)
{
printf ("Queue list Empty
");
break;
}
else
{
q = rit(qp);
qp=q;
break;
}
default:
break;
}
}
while (i==1 || i==2);
return 0;
}
sn *qit(sn *p)
{
sn *t;
t=malloc(sizeof(sn*));
printf("Enter element:");
scanf("%d",&t->n);
p->next = t;
t->next = NULL;
return t;
}
sn *rit(sn *sq)
{
sn *st;
st=sq;
printf("
Removed element is: %d",sq->n);
if(sq->next == NULL)
{
printf("
Last element
");
k=1;
return NULL;
}
else
{
sq = sq->next;
free(st);
return sq;
}
}
Rat in a Maze Game implemented in C
#include<conio.h>
#include<stdio.h>
#define SIZE 15
#include<stdlib.h>
void main()
{
int maze[SIZE][SIZE],mark[SIZE][SIZE],stack[SIZE][3];
static int
move[8][2]={-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1,-1,-1};
int i,j,m,n,top,mov,g,h;
clrscr();
printf("enter size");
scanf("%d%d",&m,&n);
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&maze[i][j]);
}
}
for(i=0;i<=n+1;i++)
maze[0][i]=1;
for(i=0;i<=n+1;i++)
maze[m+1][i]=1;
for(i=0;i<=m+1;i++)
maze[i][0]=1;
for(i=0;i<=m+1;i++)
maze[i][n+1]=1;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
mark[i][j]=0;
}
}
mark[1][1]=1;
stack[0][0]=1;
stack[0][1]=1;
stack[0][2]=2;
top=1;
while(top!=0)
{
i=stack[0][0];
j=stack[0][1];
mov=stack[0][2];
top=top-1;
while(mov<=7)
{
g=i+move[mov][0];
h=j+move[mov][1];
if(mark[g][h]==0&&maze[g][h]==0)
{
mark[g][h]=1;
top++;
stack[top][0]=i;
stack[top][1]=j;
mov=-1;
i=g;j=h;
}
mov=mov+1;
if(g==m&&h==n)
{
printf("
path made by the rat is");
for(i=1;i<=top;i++)
printf("
%d %d",stack[i][0],stack[i][1]);
printf("
%d %d",m,n);
getch();
exit(0);
}
}
}
}
Reversal of a singly linklist by recursion
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node
{
int data;
struct node*next;
};
void insert(struct node**p,int num) /*Function for inserting an
element into a list */
{
if(*p==NULL)
{
(*p)=(struct node*)malloc(sizeof(struct node));
(*p)->next=NULL;
(*p)->data=num;
}
else
{
insert(&((*p)->next),num);
}
}
void display(struct node*p) /*Function for displaying the list*/
{
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
}
void reverse(struct node**p) /*Function for reversing the list by
recursion */
{
struct node*q,*r,*x;
int d;
q=(*p); /*stores the address of the first element */
x=q; /*also stores the element of the first element for
counter pourpose */
d=q->data; /*stores the data of the first element*/
r=q->next; /*stores the address of the second element in the list
*/
free(q); /*deletes the first element of the list*/
if(x==NULL)
return ;
else
{
reverse(&(r));/*Recursive call*/
insert(p,d); /*This function is put in the stack so the first
will be taken as last element for the new list */
}
}
void main()
{
clrscr();
struct node*p=NULL;
int n,d,i=0;
printf("How many...? ");
scanf("%d",&n);
while(i++!=n)
{
scanf("%d",&d);
insert(&p,d);
}
display(p);
reverse(&p);
printf("
The reversed list is...");
display(p);
getch();
}
Search An Element in Linked List
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct linlst
{
int info;
struct link *next;
}
start, *node;
int search(int);
void main()
{
int no,i,item,pos;
clrscr();
start.next=NULL;
node=&start;
printf("How many nodes, you want in linked list? ");
scanf("%d",&no);
printf("
");
for(i=0;i<no;i++)
{
node->next=(struct linlst *)malloc(sizeof(struct linlst));
printf("Enter element in node %d: ",i+1);
scanf("%d",&node->info);
node=node->next;
}
node->next=NULL;
printf("
Linked list(only with info field) is:
");
node=&start;
while(node->next!=NULL)
{
printf("%d ",node->info);
node=node->next;
}
printf("
Enter item to be searched : ");
scanf("%d",&item);
pos=search(item);
if(pos<=no)
printf("
Your item is at node %d",pos);
else
printf("
Sorry! item is no in linked list.a");
getch();
}
int search(int item)
{
int n=1;
node=&start;
while(node->next!=NULL)
{
if(node->info==item)
break;
else
n++;
node=node->next;
}
return n;
}
Self-referential structure, example from K and R
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#define MAXWORD 100
#define BUFSIZE 100
struct tnode { /* the tree node: */
char *word; /* points to the text */
int count; /* number of occurrences */
struct tnode *left; /* left child */
struct tnode *right; /* right child */
};
struct tnode *addtree(struct tnode *, char *);
struct tnode *talloc(void);
void treeprint(struct tnode *);
void ungetch(int);
int getword(char *, int);
int getch(void);
char buf[BUFSIZE]; /* buffer for ungetch */
int bufp = 0; /* next free position in buf */
int main(void) { /* word frequency count */
struct tnode *root;
char word[MAXWORD];
root = NULL;
while(getword(word, MAXWORD) != EOF)
if(isalpha(word[0]))
root = addtree(root, word);
treeprint(root);
exit(0);
}
/* getword: get next word or character from input */
int getword(char *word, int lim) {
int c, getch(void);
void ungetch(int);
char *w = word;
while(isspace(c = getch()))
;
if(c != EOF)
*w++ = c;
if(!isalpha(c)) {
*w = '\0';
return c;
}
for(; --lim > 0; w++)
if(!isalnum(*w = getch())) {
ungetch(*w);
break;
}
*w = '\0';
return word[0];
}
/* addtree: add a node with w, at or below p */
struct tnode *addtree(struct tnode *p, char *w) {
int cond;
if(p == NULL) { /* a new word has arrived */
p = talloc(); /* make a new node */
p->word = strdup(w);
p->count = 1;
p->left = p->right = NULL;
} else if((cond = strcmp(w, p->word)) == 0)
p->count++; /* repeated word */
else if(cond < 0) /* less than into left subtree */
p->left = addtree(p->left, w);
else /* greater than into right subtree */
p->right = addtree(p->right, w);
return p;
}
/* talloc: make a tnode */
struct tnode *talloc(void) {
return(struct tnode *)malloc(sizeof(struct tnode));
}
/* treeprint: in-order print of tree p */
void treeprint(struct tnode *p) {
if(p != NULL) {
treeprint(p->left);
printf("%4d %s\n", p->count, p->word);
treeprint(p->right);
}
}
int getch(void) {
return (bufp > 0) ? buf[--bufp] : getchar();
}
void ungetch(int c) {
if(bufp >= BUFSIZE)
printf("ungetch: too many characters\n");
else
buf[bufp++] = c;
}
To Sort Elements Of The Array Using Quick Sort Algorithm
#include<stdio.h>
#include<conio.h>
#define max 15
int beg,end,top,i,n,loc,left,right;
int array[max+1]; //contains the various elements.
int upper[max-1],lower[max-1];
//two stacks to store two ends of the list.
void main()
{
void enter(void);
void quick(void);
void prnt(void);
clrscr();
enter(); //entering elements in the array
top=i-1; //set top to stack
if (top==0)
{
printf("
UNDERFLOW CONDITION ");
getch();
exit();
}
top=0;
if(n>1)
{
top++;
lower[top]=1;upper[top]=n;
while ( top!=NULL )
{
beg=lower[top];
end=upper[top];
top--;
left=beg; right=end; loc=beg;
quick();
if ( beg<loc-1)
{
top++;
lower[top]=beg;
upper[top]=loc-1;
}
if(loc+1<end)
{
top++;
lower[top]=loc+1;
upper[top]=end;
}
} //end of while
} //end of if statement
printf("
Sorted elements of the array are :");
prnt(); //to print the sorted array
getch();
} //end of main
void enter(void)
{
printf("
Enter the no of elements in the array:");
scanf("%d",&n);
printf("
Enter the elements of the array :");
for(i=1;i<=n;i++)
{
printf("
Enter the %d element :",i);
scanf("%d",&array[i]);
}
}
void prnt(void)
{
for(i=1;i<=n;i++)
{
printf("
The %d element is : %d",i,array[i]);
}
}
void quick()
{
int temp;
void tr_fr_right(void);
while( array[loc]<=array[right] && loc!=right)
{
right--;
}
if(loc==right)
return ;
if(array[loc]>array[right])
{
temp=array[loc];
array[loc]=array[right];
array[right]=temp;
loc=right;
tr_fr_right();
}
return ;
}
void tr_fr_right()
{
int temp;
while( array[loc] > array[left] && loc!=left)
{
left++;
}
if(loc==left)
return ;
if(array[loc] < array[left])
{
temp=array[loc];
array[loc]=array[left];
array[left]=temp;
loc=left;
quick();
}
return ;
}
Program for demonstration of Tree Operations - INSERTION . INORDER .
PREORDER . POSTORDER TRAVERSAL
# include<stdio.h>
# include <conio.h>
# include <malloc.h>
struct node
{
struct node *left;
int data;
struct node *right;
} ;
void main()
{
void insert(struct node **,int);
void inorder(struct node *);
void postorder(struct node *);
void preorder(struct node *);
struct node *ptr;
int will,i,num;
ptr = NULL;
ptr->data=NULL;
clrscr();
printf("
Enter the number of terms you want to add to the tree.
");
scanf("%d",&will);
/* Getting Input */
for(i=0;i<will;i++)
{
printf("
Enter the item");
scanf("%d",&num);
insert(&ptr,num);
}
getch();
printf("
INORDER TRAVERSAL
");
inorder(ptr);
getch();
printf("
PREORDER TRAVERSAL
");
preorder(ptr);
getch();
printf("
POSTORDER TRAVERSAL
");
postorder(ptr);
getch();
}
void insert(struct node **p,int num)
{
if((*p)==NULL)
{ printf("
Leaf node created.");
(*p)=malloc(sizeof(struct node));
(*p)->left = NULL;
(*p)->right = NULL;
(*p)->data = num;
return;
}
else
{ if(num==(*p)->data)
{
printf("
REPEATED ENTRY ERROR
VALUE REJECTED
");
return;
}
if(num<(*p)->data)
{
printf("
Directed to left link.");
insert(&((*p)->left),num);
}
else
{
printf("
Directed to right link.");
insert(&((*p)->right),num);
}
}
return;
}
void inorder(struct node *p)
{
if(p!=NULL)
{
inorder(p->left);
printf("
Data :%d",p->data);
inorder(p->right);
}
else
return;
}
void preorder(struct node *p)
{
if(p!=NULL)
{
printf("
Data :%d",p->data);
preorder(p->left);
preorder(p->right);
}
else
return;
}
void postorder(struct node *p)
{
if(p!=NULL)
{
postorder(p->left);
postorder(p->right);
printf("
Data :%d",p->data);
}
else
return;
}
XOR list example
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct xnode {
int data;
unsigned long direction;
};
struct xnode *add_data(int data, struct xnode* list);
void walk_list(struct xnode *list);
int main(void) {
struct xnode *l2 = add_data(2, NULL);
struct xnode *l1 = add_data(1, l2);
struct xnode *l3 = add_data(3, l2);
struct xnode *l4 = add_data(4, l3);
printf("front -> back....\n");
walk_list(l1);
printf("back -> front....\n");
walk_list(l4);
return 0;
}
struct xnode *add_data(int data, struct xnode *list) {
struct xnode *newxnode = malloc(sizeof(struct xnode));
assert(newxnode);
newxnode->direction = (unsigned long)list;
newxnode->data = data;
if(list != NULL)
list->direction ^= (unsigned long)newxnode;
return newxnode;
}
void walk_list(struct xnode *list) {
unsigned long prev = 0;
while(list != NULL) {
unsigned long next = prev ^ list->direction;
printf("%d ", list->data);
prev = (unsigned long)list;
list = (struct xnode *)next;
}
printf("\n");
}
UNKNOWN
//**************************************
// Name: A Simple Linked List
// Description:A simple linked list example with various list operations. Demonstrates how to use a linked list class with a separate Node class.
A good example for someone who want to learn about linked lists.
Please comment
// By: Maqsood
//
//
// Inputs:None
//
// Returns:None
//
//Assumes:None
//
//Side Effects:None
//This code is copyrighted and has limited warranties.
//Please see http://www.Planet-Source-Code.com/xq/ASP/txtCodeId.13032/lngWId.3/qx/vb/scripts/ShowCode.htm
//for details.
//**************************************
#include <iostream.h>
#include <conio.h>
class Node{
private:
int data;
Node *nextNode;
public:
void setData(int data)
{
this->data=data;
}
int getData()
{
return data;
}
void setNext(Node *nextNode)
{
this->nextNode = nextNode;
}
Node *getNext()
{
return nextNode;
}
};
class List{
private:
int size;
Node *headNode;
Node *currentNode;
Node *lastCurrentNode;
public:
List();
void addData(int data);
void remove();
void del(int pos, List l);
void update(int pos, int newVal, List l);
void search(int data, List l);
void start();
int get();
bool next();
void traverse(List);
};
List::List()
{
headNode = new Node();
headNode->setNext(NULL);
currentNode = NULL;
lastCurrentNode = NULL;
size = 0;
}
void List::addData(int data)
{
Node *newNode = new Node();
newNode->setData(data);
if (currentNode == NULL)
{
headNode->setNext(newNode);
newNode->setNext(NULL);
lastCurrentNode = headNode;
currentNode = newNode;
}
else
{
newNode->setNext(currentNode->getNext());
currentNode->setNext(newNode);
lastCurrentNode = currentNode;
currentNode = newNode;
}
size++;
}
void List::remove()
{
if (currentNode != NULL && size != 0)
{
lastCurrentNode->setNext(currentNode->getNext());
delete currentNode;
currentNode = lastCurrentNode;
}
size--;
}
bool List::next()
{
if (currentNode == NULL)
return false;
lastCurrentNode = currentNode;
currentNode = currentNode->getNext();
if (currentNode == NULL || size == 0)
return false;
else
return true;
}
int List::get()
{
return currentNode->getData();
}
void List::traverse(List l)
{
Node *savedCurrentNode = l.currentNode;
l.currentNode = l.headNode->getNext();
for (int i = 1;l.next();i++)
{
cout<<"Element "<<i<<":"<<l.get()<<"\n";
}
l.currentNode = savedCurrentNode;
}
void List::search(int data, List l)
{
Node *savedCurrentNode = l.currentNode;
l.currentNode = headNode->getNext();
bool found = false;
for(int i=1;l.next();i++)
{
if (l.get() == data)
{
cout<<"Element "<<data<<" found at position "<<i;
found = true;
break;
}
}
if (!found)
cout<<"Element does not exist in the list!";
l.currentNode = savedCurrentNode;
}
void List::update(int pos, int newVal, List l)
{
Node *savedCurrentNode = l.currentNode;
l.currentNode = headNode->getNext();
//l.start();
bool update=false;
for (int i=1;l.next();i++)
{
if (i==pos)
{
l.currentNode->setData(newVal);
cout<<"\nData updated "<<" at position "<<pos<<"\n";
update = true;
break;
}
}
if (!update)
cout<<"\n\nPosition does not exist";
l.currentNode = savedCurrentNode;
}
void List::start()
{
currentNode = headNode;
lastCurrentNode = headNode;
}
void List::del(int pos, List l)
{
Node *savedCurrentNode = l.currentNode;
l.currentNode = headNode->getNext();
for (int i=1;l.next();i++)
{
if (pos == i)
{
l.lastCurrentNode->setNext(l.currentNode->getNext());
delete l.currentNode;
l.currentNode = l.lastCurrentNode;
l.size--;
cout<<"\n\n\n\nNode deleted\n\n";
break;
}
}
l.currentNode = savedCurrentNode;
}
main()
{
List l;
l.addData(23);
l.addData(45);
l.addData(35);
l.addData(12);
l.addData(56);
l.addData(11);
l.addData(78);
l.addData(99);
//l.traverse(l);
//l.remove();
//cout<<"After removal: \n\n";
//l.traverse(l);
l.addData(101);
//cout<<"After insertion: \n\n";
//l.traverse(l);
//l.search(45,l);
l.addData(101);
l.addData(102);
l.addData(103);
l.addData(104);
l.traverse(l);
/* l.update(5,117,l);
cout<<"\n\n\nAfter Updation:\n";
l.traverse(l);
*/
//l.update(10,678,l);
//l.traverse(l);
//l.search(1026,l);
//l.addData(32423);
//l.traverse(l);
l.del(7,l);
l.traverse(l);
getch();
}
