1. The Bubble Sort Example
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
void bubble(char *items, int count);
int main(void)
{
char s[255];
printf("Enter a string:");
gets(s);
bubble(s, strlen(s));
printf("\nThe sorted string is: %s.\n", s);
return 0;
}
void bubble(char *items, int count)
{
register int i, j;
register char t;
for(i = 1; i < count; ++i)
for( j = count-1; j >= i; --j) {
if(items[j - 1] > items[ j ]) {
/* exchange elements */
t = items[j - 1];
items[j - 1] = items[ j ];
items[ j ] = t;
}
}
}
output:
Enter a string:Easy programming 24
The sorted string is: 24Eaaggimmnoprrsy.
2. illustrates the use and maintenance of doubly linked lists
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct address {
char name[30];
char street[40];
char city[20];
char state[3];
char zip[11];
struct address *next; /* pointer to next entry */
struct address *prior; /* pointer to previous record */
};
struct address *start; /* pointer to first entry in list */
struct address *last; /* pointer to last entry */
struct address *find(char *);
void enter(void), search(void), save(void);
void load(void), list(void);
void mldelete(struct address **, struct address **);
void dls_store(struct address *i, struct address **start,
struct address **last);
void inputs(char *, char *, int), display(struct address *);
int menu_select(void);
int main(void)
{
start = last = NULL; /* initialize start and end pointers */
for(;;) {
switch(menu_select()) {
case 1: enter(); /* enter an address */
break;
case 2: mldelete(&start, &last); /* remove an address */
break;
case 3: list(); /* display the list */
break;
case 4: search(); /* find an address */
break;
case 5: save(); /* save list to disk */
break;
case 6: load(); /* read from disk */
break;
case 7: exit(0);
}
}
return 0;
}
/* Select an operation. */
int menu_select(void)
{
char s[80];
int c;
printf("1. Enter a name\n");
printf("2. Delete a name\n");
printf("3. List the file\n");
printf("4. Search\n");
printf("5. Save the file\n");
printf("6. Load the file\n");
printf("7. Quit\n");
do {
printf("\nEnter your choice: ");
gets(s);
c = atoi(s);
} while(c<0 || c>7);
return c;
}
/* Enter names and addresses. */
void enter(void)
{
struct address *info;
for(;;) {
info = (struct address *)malloc(sizeof(struct address));
if(!info) {
printf("\nout of memory");
return;
}
inputs("Enter name: ", info->name, 30);
if(!info->name[0]) break; /* stop entering */
inputs("Enter street: ", info->street, 40);
inputs("Enter city: ", info->city, 20);
inputs("Enter state: ", info->state, 3);
inputs("Enter zip: ", info->zip, 10);
dls_store(info, &start, &last);
} /* entry loop */
}
/* This function will input a string up to
the length in count and will prevent
the string from being overrun. It will also
display a prompting message. */
void inputs(char *prompt, char *s, int count)
{
char p[255];
do {
printf(prompt);
fgets(p, 254, stdin);
if(strlen(p) > count) printf("\nToo Long\n");
} while(strlen(p) > count);
p[strlen(p)-1] = 0; /* remove newline character */
strcpy(s, p);
}
/* Create a doubly linked list in sorted order. */
void dls_store(
struct address *i, /* new element */
struct address **start, /* first element in list */
struct address **last /* last element in list */
)
{
struct address *old, *p;
if(*last==NULL) { /* first element in list */
i->next = NULL;
i->prior = NULL;
*last = i;
*start = i;
return;
}
p = *start; /* start at top of list */
old = NULL;
while(p) {
if(strcmp(p->name, i->name)<0){
old = p;
p = p->next;
}
else {
if(p->prior) {
p->prior->next = i;
i->next = p;
i->prior = p->prior;
p->prior = i;
return;
}
i->next = p; /* new first element */
i->prior = NULL;
p->prior = i;
*start = i;
return;
}
}
old->next = i; /* put on end */
i->next = NULL;
i->prior = old;
*last = i;
}
/* Remove an element from the list. */
void mldelete(struct address **start, struct address **last)
{
struct address *info;
char s[80];
inputs("Enter name: ", s, 30);
info = find(s);
if(info) {
if(*start==info) {
*start=info->next;
if(*start) (*start)->prior = NULL;
else *last = NULL;
}
else {
info->prior->next = info->next;
if(info!=*last)
info->next->prior = info->prior;
else
*last = info->prior;
}
free(info); /* return memory to system */
}
}
/* Find an address. */
struct address *find( char *name)
{
struct address *info;
info = start;
while(info) {
if(!strcmp(name, info->name)) return info;
info = info->next; /* get next address */
}
printf("Name not found.\n");
return NULL; /* not found */
}
/* Display the entire list. */
void list(void)
{
struct address *info;
info = start;
while(info) {
display(info);
info = info->next; /* get next address */
}
printf("\n\n");
}
/* This function actually prints the fields in each address. */
void display(struct address *info)
{
printf("%s\n", info->name);
printf("%s\n", info->street);
printf("%s\n", info->city);
printf("%s\n", info->state);
printf("%s\n", info->zip);
printf("\n\n");
}
/* Look for a name in the list. */
void search(void)
{
char name[40];
struct address *info;
printf("Enter name to find: ");
gets(name);
info = find(name);
if(!info) printf("Not Found\n");
else display(info);
}
/* Save the file to disk. */
void save(void)
{
struct address *info;
FILE *fp;
fp = fopen("mlist", "wb");
if(!fp) {
printf("Cannot open file.\n");
exit(1);
}
printf("\nSaving File\n");
info = start;
while(info) {
fwrite(info, sizeof(struct address), 1, fp);
info = info->next; /* get next address */
}
fclose(fp);
}
/* Load the address file. */
void load()
{
struct address *info;
FILE *fp;
fp = fopen("mlist", "rb");
if(!fp) {
printf("Cannot open file.\n");
exit(1);
}
/* free any previously allocated memory */
while(start) {
info = start->next;
free(info);
start = info;
}
/* reset top and bottom pointers */
start = last = NULL;
printf("\nLoading File\n");
while(!feof(fp)) {
info = (struct address *) malloc(sizeof(struct address));
if(!info) {
printf("Out of Memory");
return;
}
if(1 != fread(info, sizeof(struct address), 1, fp)) break;
dls_store(info, &start, &last);
}
fclose(fp);
}
output:
1. Enter a name
2. Delete a name
3. List the file
4. Search
5. Save the file
6. Load the file
7. Quit
Enter your choice: 1
Enter name: khan
Enter street: kishan nagar
Enter city: thane
Enter state: mh
Enter zip: 400604
3. The Selection Sort Example
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
void select(char *items, int count);
int main(void) {
char s[255];
printf("Enter a string:");
gets(s);
select(s, strlen(s));
printf("\nThe sorted string is: %s.\n", s);
return 0;
}
void select(char *items, int count)
{
register int a, b, c;
int exchange;
char t;
for(a = 0; a < count-1; ++a) {
exchange = 0;
c = a;
t = items[ a ];
for(b = a + 1; b < count; ++b) {
if(items[ b ] < t) {
c = b;
t = items[ b ];
exchange = 1;
}
}
if(exchange) {
items[ c ] = items[ a ];
items[ a ] = t;
}
}
}
output:
Enter a string:Easy programming 24
The sorted string is: 24Eaaggimmnoprrsy.
4. Simple Stack in C Example
#include <stdio.h>
#include <stdlib.h>
#define SIZE 50
void push(int i);
int pop(void);
int *tos, *p1, stack[SIZE];
int main(void)
{
int value;
tos = stack; /* tos points to the top of stack */
p1 = stack; /* initialize p1 */
do {
printf("Enter value: ");
scanf("%d", &value);
if(value != 0) push(value);
else printf("\nvalue on top is %d\n", pop());
} while(value != -1);
return 0;
}
void push(int i)
{
p1++;
if(p1 == (tos+SIZE)) {
printf("\nStack Overflow.\n");
exit(1);
}
*p1 = i;
}
int pop(void)
{
if(p1 == tos) {
printf("\nStack Underflow.\n");
exit(1);
}
p1--;
return *(p1+1);
}
output:
Enter value: 4
Enter value: 3
Enter value: 7
Enter value: 2
Enter value: i
Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value: Enter value:
Stack Overflow.
5. A Afour-function calculator Example
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int *p; /* will point to a region of free memory */
int *tos; /* points to top of stack */
int *bos; /* points to bottom of stack */
void push(int i)
{
if(p > bos) {
printf("Stack Full\n");
return;
}
*p = i;
p++;
}
int pop(void)
{
p--;
if(p < tos) {
printf("Stack Underflow\n");
return 0;
}
return *p;
}
int main(void)
{
int a, b;
char s[80];
p = (int *) malloc(MAX*sizeof(int)); /* get stack memory */
if(!p) {
printf("Allocation Failure\n");
exit(1);
}
tos = p;
bos = p + MAX-1;
printf("Four Function Calculator\n");
printf("Enter 'q' to quit\n");
do {
printf(": ");
gets(s);
switch(*s) {
case '+':
a = pop();
b = pop();
printf("%d\n", a+b);
push(a+b);
break;
case '-':
a = pop();
b = pop();
printf("%d\n", b-a);
push(b-a);
break;
case '*':
a = pop();
b = pop();
printf("%d\n", b*a);
push(b*a);
break;
case '/':
a = pop();
b = pop();
if(a==0) {
printf("Divide by 0.\n");
break;
}
printf("%d\n", b/a);
push(b/a);
break;
case '.': /* show contents of top of stack */
a = pop();
push(a);
printf("Current value on top of stack: %d\n", a);
break;
default:
push(atoi(s));
}
} while(*s != 'q');
return 0;
}
output:
Four Function Calculator
Enter 'q' to quit
: 3
: 2
: 4
: 6
: q
6. Basics Family Tree Example
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
struct Family *get_person(void); /* Prototype for input function */
char related(struct Family *pmember1, struct Family *pmember2);
char set_ancestry(struct Family *pmember1, struct Family *pmember2);
struct Date
{
int day;
int month;
int year;
};
struct Family /* Family structure declaration */
{
struct Date dob;
char name[20];
char father[20];
char mother[20];
struct Family *next; /* Pointer to next structure */
struct Family *previous; /* Pointer to previous structure */
struct Family *p_to_pa; /* Pointer to father structure */
struct Family *p_to_ma; /* Pointer to mother structure */
};
void main()
{
struct Family *first = NULL; /* Pointer to first person */
struct Family *current = NULL; /* Pointer to current person */
struct Family *last = NULL; /* Pointer to previous person */
char more = '\0'; /* Test value for ending input */
for( ; ; )
{
printf("\nDo you want to enter details of a%s person (Y or N)? ",
first != NULL?"nother " : "" );
scanf(" %c", &more);
if(tolower(more) == 'n')
break;
current = get_person();
if(first == NULL)
{
first = current; /* Set pointer to first Family */
last = current; /* Remember for next iteration */
}
else
{
last->next = current; /* Set next address for previous Family */
current->previous = last; /* Set previous address for current */
last = current; /* Remember for next iteration */
}
}
current = first;
while(current->next != NULL) /* Check for relation for each person in */
{ /* the list up to second to last */
int parents = 0; /* Declare parent count local to this block */
last = current->next; /* Get the pointer to the next */
while(last != NULL) /* This loop tests current person */
{ /* against all the remainder in the list */
if(related(current, last)) /* Found a parent ? */
if(++parents == 2) /* Yes, update count and check it */
break; /* Exit inner loop if both parents found */
last = last->next; /* Get the address of the next */
}
current = current->next; /* Next in the list to check */
}
/* Now tell them what we know */
/* Output Family data in correct order */
current = first;
while (current != NULL) /* Output Family data in correct order */
{
printf("\n%s was born %d/%d/%d, and has %s and %s as parents.",
current->name, current->dob.day, current->dob.month,
current->dob. year, current->father, current->mother);
if(current->p_to_pa != NULL )
printf("\n\t%s's birth date is %d/%d/%d ",
current->father, current->p_to_pa->dob.day,
current->p_to_pa->dob.month,
current->p_to_pa->dob.year);
if(current->p_to_ma != NULL)
printf("and %s's birth date is %d/%d/%d.\n ",
current->mother, current->p_to_ma->dob.day,
current->p_to_ma->dob.month,
current->p_to_ma->dob.year);
current = current->next; /* current points to next in list */
}
/* Now free the memory */
current = first;
while(current->next != NULL)
{
last = current; /* Save pointer to enable memory to be freed */
current = current->next; /* current points to next in list */
free(last); /* Free memory for last */
}
}
/* Function to input data on Family members */
struct Family *get_person(void)
{
struct Family *temp; /* Define temporary structure pointer */
/* Allocate memory for a structure */
temp = (struct Family*) malloc(sizeof(struct Family));
printf("\nEnter the name of the person: ");
scanf("%s", temp -> name ); /* Read the Family's name */
printf("\nEnter %s's date of birth (day month year); ", temp->name);
scanf("%d %d %d", &temp->dob.day, &temp->dob.month, &temp->dob.year);
printf("\nWho is %s's father? ", temp->name );
scanf("%s", temp->father ); /* Get the father's name */
printf("\nWho is %s's mother? ", temp -> name );
scanf("%s", temp -> mother ); /* Get the mother's name */
temp->next = temp->previous = NULL; /* Set pointers to NULL */
temp->p_to_pa = temp->p_to_ma = NULL; /* Set pointers to NULL */
return temp; /* Return address of Family structure */
}
char set_ancestry(struct Family *pmember1, struct Family *pmember2)
{
if(strcmp(pmember1->father, pmember2->name) == 0)
{
pmember1->p_to_pa = pmember2;
return 1;
}
if( strcmp(pmember1->mother, pmember2->name) == 0)
{
pmember1->p_to_ma = pmember2;
return 1;
}
else
return 0;
}
/* Fill in pointers for mother or father relationships */
char related (struct Family *pmember1, struct Family *pmember2)
{
return set_ancestry(pmember1, pmember2) ||
set_ancestry(pmember2, pmember1);
}
output:
Do you want to enter details of a person (Y or N)? y
Enter the name of the person: khan
Enter khan's date of birth (day month year); 5 08 2001
Who is khan's father? akram
Who is khan's mother? khatoon
Do you want to enter details of another person (Y or N)?
7. Recursive C program to find length of a linked list
#include <stdio.h>
#include <stdlib.h>
struct node
{
int a;
struct node *next;
};
void generate(struct node **);
int length(struct node*);
void delete(struct node **);
int main()
{
struct node *head = NULL;
int count;
generate(&head);
count = length(head);
printf("The number of nodes are: %d", count);
delete(&head);
return 0;
}
void generate(struct node **head)
{
/* for unknown number of nodes use num = rand() % 20; */
int num = 10, i;
struct node *temp;
for (i = 0; i < num; i++)
{
temp = (struct node *)malloc(sizeof(struct node));
temp->a = i;
if (*head == NULL)
{
*head = temp;
(*head)->next = NULL;
}
else
{
temp->next = *head;
*head = temp;
}
}
}
int length(struct node *head)
{
if (head->next == NULL)
{
return 1;
}
return (1 + length(head->next));
}
void delete(struct node **head)
{
struct node *temp;
while (*head != NULL)
{
temp = *head;
*head = (*head)->next;
free(temp);
}
}
output:
The number of nodes are: 10
8. C Program to Implement Binary Tree using Linked List
#include <stdio.h>
#include <malloc.h>
struct node {
struct node * left;
char data;
struct node * right;
};
struct node *constructTree( int );
void inorder(struct node *);
char array[ ] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', '', '', 'H' };
int leftcount[ ] = { 1, 3, 5, -1, 9, -1, -1, -1, -1, -1 };
int rightcount[ ] = { 2, 4, 6, -1, -1, -1, -1, -1, -1, -1 };
void main() {
struct node *root;
root = constructTree( 0 );
printf("In-order Traversal: ");
inorder(root);
}
struct node * constructTree( int index ) {
struct node *temp = NULL;
if (index != -1) {
temp = (struct node *)malloc( sizeof ( struct node ) );
temp->left = constructTree( leftcount[index] );
temp->data = array[index];
temp->right = constructTree( rightcount[index] );
}
return temp;
}
void inorder( struct node *root ) {
if (root != NULL) {
inorder(root->left);
printf("%c ", root->data);
inorder(root->right);
}
}
Output:
In-order Traversal:
D B H E A F C G
9. C program to illustrate the operations of singly linked list
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 30
struct emp_data
{
int empno;
char empName[MAX];
char designation[MAX];
struct emp_data *next;
};
/* ********************************************************************/
/* Function to insert a node at the front of the linked list. */
/* front: front pointer, id: employee ID, name: employee name */
/* desg: Employee designation */
/* Returns the new front pointer. */
/* ********************************************************************/
struct emp_data *insert(struct emp_data *front, int id, char name[],
char desg[])
{
struct emp_data *newnode;
newnode = (struct emp_data*)malloc(sizeof(struct emp_data));
if (newnode == NULL)
{
printf(" Allocation failed ");
exit(2);
}
newnode->empno = id;
strcpy(newnode->empName, name);
strcpy(newnode->designation, desg);
newnode->next = front;
front = newnode;
return(front);
}
/* End of insert() */
/* Function to display a node in a linked list */
void printNode(struct emp_data *p)
{
printf(" Employee Details...");
printf(" Emp No : %d", p->empno);
printf(" Name : %s", p->empName);
printf(" Designation : %s", p->designation);
printf("-------------------------------------");
}
/* End of printNode() */
/* ********************************************************/
/* Function to deleteNode a node based on employee number */
/* front: front pointer, id: Key value */
/* Returns: the modified list. */
/* ********************************************************/
struct emp_data* deleteNode(struct emp_data *front, int id)
{
struct emp_data *ptr;
struct emp_data *bptr;
if (front->empno == id)
{
ptr = front;
printf(" Node deleted:");
printNode(front);
front = front->next;
free(ptr);
return(front);
}
for (ptr = front->next, bptr = front; ptr != NULL; ptr = ptr->next, bptr = bptr->next)
{
if (ptr->empno == id)
{
printf(" Node deleted:");
printNode(ptr);
bptr->next = ptr->next;
free(ptr);
return(front);
}
}
printf(" Employee Number %d not found ", id);
return(front);
}
/* End of deleteNode() */
/* ****************************************************************/
/* Function to search the nodes in a linear fashion based emp ID */
/* front: front pointer, key: key ID. */
/* ****************************************************************/
void search(struct emp_data *front, int key)
{
struct emp_data *ptr;
for (ptr = front; ptr != NULL; ptr = ptr -> next)
{
if (ptr->empno == key)
{
printf(" Key found:");
printNode(ptr);
return;
}
}
printf(" Employee Number %d not found ", key);
}
/* End of search() */
/* Function to display the linked list */
void display(struct emp_data *front)
{
struct emp_data *ptr;
for (ptr = front; ptr != NULL; ptr = ptr->next)
{
printNode(ptr);
}
}
/* End of display() */
/* Function to display the menu of operations on a linked list */
void menu()
{
printf("---------------------------------------------");
printf("Press 1 to INSERT a node into the list ");
printf("Press 2 to DELETE a node from the list ");
printf("Press 3 to DISPLAY the list ");
printf("Press 4 to SEARCH the list ");
printf("Press 5 to EXIT ");
printf("---------------------------------------------");
}
/* End of menu() */
/* Function to select the option */
char option()
{
char choice;
printf(">> Enter your choice: ");
switch(choice=getche())
{
case '1':
case '2':
case '3':
case '4':
case '5':
return(choice);
default : printf(" Invalid choice.");
}
return choice;
}
/* End of option() */
/* The main() program begins */
void main()
{
struct emp_data *linkList;
char name[21], desig[51];
char choice;
int eno;
linkList = NULL;
printf(" Welcome to demonstration of singly linked list ");
menu();
do
{
/* choose oeration to be performed */
choice = option();
switch(choice)
{
case '1':
printf(" Enter the Employee Number : ");
scanf("%d", &eno);
printf("Enter the Employee name : ");
fflush(stdin);
gets(name);
printf("Enter the Employee Designation : ");
gets(desig);
linkList = insert(linkList, eno, name, desig);
break;
case '2':
printf(" Enter the employee number to be deleted: ");
scanf("%d", &eno);
linkList = deleteNode(linkList, eno);
break;
case '3':
if (linkList == NULL)
{
printf(" List empty.");
break;
}
display(linkList);
break;
case '4':
printf(" Enter the employee number to be searched: ");
scanf("%d", &eno);
search(linkList, eno);
break;
case '5': break;
}
} while (choice != '5');
}
Output:
Welcome to demonstration of singly linked list
---------------------------------------------
Press 1 to INSERT a node into the list
Press 2 to DELETE a node from the list
Press 3 to DISPLAY the list
Press 4 to SEARCH the list
Press 5 to EXIT
---------------------------------------------
>> Enter your choice: 1
Enter the Employee Number : 12
Enter the Employee name : ram
Enter the Employee Designation : HR
>> Enter your choice: 3
Employee Details...
Emp No : 12
Name : ram
Designation : HR
-------------------------------------
>> Enter your choice:
Invalid choice.
>> Enter your choice: 4
Enter the employee number to be searched: 12
Key found:
Employee Details...
Emp No : 12
Name : ram
Designation : HR
-------------------------------------
>> Enter your choice:
Invalid choice.
>> Enter your choice: 2
Enter the employee number to be deleted: 12
Node deleted:
Employee Details...
Emp No : 12
Name : ram
Designation : HR
-------------------------------------
>> Enter your choice:
Invalid choice.
>> Enter your choice: 4
Enter the employee number to be searched: 1
Employee Number 1 not found
>> Enter your choice:
Invalid choice.
>> Enter your choice: 5
10. C program to search for an element in linked list
#include <stdio.h>
#include <stdlib.h>
struct node
{
int a;
struct node *next;
};
void generate(struct node **, int);
void search(struct node *, int, int);
void delete(struct node **);
int main()
{
struct node *head;
int key, num;
printf("Enter the number of nodes: ");
scanf("%d", &num);
generate(&head, num);
printf("Enter key to search: ");
scanf("%d", &key);
search(head, key, num);
delete(&head);
}
void generate(struct node **head, int num) {
int i;
struct node *temp;
for (i = 0; i < num; i++)
{
temp = (struct node *)malloc(sizeof(struct node));
temp->a = rand() % num;
printf("%d ", temp->a);
if (*head == NULL)
{
*head = temp;
(*head)->next = NULL;
}
else
{
temp->next = *head;
*head = temp;
}
}
}
void search(struct node *head, int key, int index)
{
if (head->a == key)
{
printf("Key found at Position: %d", index);
}
if (head->next == NULL)
{
return;
}
search(head->next, key, index - 1);
}
void delete(struct node **head)
{
struct node *temp;
while (*head != NULL)
{
temp = *head;
*head = (*head)->next;
free(temp);
}
}
Output:
Enter the number of nodes: 6
1 4 3 1 5 1
Enter key to search: 1
Key found at Position: 6
Key found at Position: 4
Key found at Position: 1
11. C Program to Print the Alternate Nodes in a Linked List without
* using Recursion
#include <stdio.h>
#include <stdlib.h>
struct node
{
int a;
struct node *next;
};
void generate(struct node **);
void display(struct node *);
void delete(struct node **);
int main()
{
struct node *head = NULL;
generate(&head);
printf("Displaying the alternate nodes");
display(head);
delete(&head);
return 0;
}
void display(struct node *head)
{
int flag = 0;
while(head != NULL)
{
if (!(flag % 2))
{
printf("%d ", head->a);
}
flag++;
head = head->next;
}
}
void generate(struct node **head)
{
int num, i;
struct node *temp;
printf("Enter length of list: ");
scanf("%d", &num);
for (i = num; i > 0; i--)
{
temp = (struct node *)malloc(sizeof(struct node));
temp->a = i;
if (*head == NULL)
{
*head = temp;
(*head)->next = NULL;
}
else
{
temp->next = *head;
*head = temp;
}
}
}
void delete(struct node **head)
{
struct node *temp;
while (*head != NULL)
{
temp = *head;
*head = (*head)->next;
free(temp);
}
}
}
Output:
Enter length of list: 20
Displaying the alternate nodes
1 3 5 7 9 11 13 15 17 19
12. C Program to Implement a Stack using Linked List
#include <stdio.h>
#include <stdlib.h>
struct node
{
int info;
struct node *ptr;
}*top,*top1,*temp;
int topelement();
void push(int data);
void pop();
void empty();
void display();
void destroy();
void stack_count();
void create();
int count = 0;
void main()
{
int no, ch, e;
printf(" 1 - Push");
printf(" 2 - Pop");
printf(" 3 - Top");
printf(" 4 - Empty");
printf(" 5 - Exit");
printf(" 6 - Dipslay");
printf(" 7 - Stack Count");
printf(" 8 - Destroy stack");
create();
while (1)
{
printf(" Enter choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter data : ");
scanf("%d", &no);
push(no);
break;
case 2:
pop();
break;
case 3:
if (top == NULL)
printf("No elements in stack");
else
{
e = topelement();
printf(" Top element : %d", e);
}
break;
case 4:
empty();
break;
case 5:
exit(0);
case 6:
display();
break;
case 7:
stack_count();
break;
case 8:
destroy();
break;
default :
printf(" Wrong choice, Please enter correct choice ");
break;
}
}
}
/* Create empty stack */
void create()
{
top = NULL;
}
/* Count stack elements */
void stack_count()
{
printf(" No. of elements in stack : %d", count);
}
/* Push data into stack */
void push(int data)
{
if (top == NULL)
{
top =(struct node *)malloc(1*sizeof(struct node));
top->ptr = NULL;
top->info = data;
}
else
{
temp =(struct node *)malloc(1*sizeof(struct node));
temp->ptr = top;
temp->info = data;
top = temp;
}
count++;
}
/* Display stack elements */
void display()
{
top1 = top;
if (top1 == NULL)
{
printf("Stack is empty");
return;
}
while (top1 != NULL)
{
printf("%d ", top1->info);
top1 = top1->ptr;
}
}
/* Pop Operation on stack */
void pop()
{
top1 = top;
if (top1 == NULL)
{
printf(" Error : Trying to pop from empty stack");
return;
}
else
top1 = top1->ptr;
printf(" Popped value : %d", top->info);
free(top);
top = top1;
count--;
}
/* Return top element */
int topelement()
{
return(top->info);
}
/* Check if stack is empty or not */
void empty()
{
if (top == NULL)
printf(" Stack is empty");
else
printf(" Stack is not empty with %d elements", count);
}
/* Destroy entire stack */
void destroy()
{
top1 = top;
while (top1 != NULL)
{
top1 = top->ptr;
free(top);
top = top1;
top1 = top1->ptr;
}
free(top1);
top = NULL;
printf(" All stack elements destroyed");
count = 0;
}
Output:
1 - Push
2 - Pop
3 - Top
4 - Empty
5 - Exit
6 - Dipslay
7 - Stack Count
8 - Destroy stack
Enter choice : 1
Enter data : 56
Enter choice : 1
Enter data : 80
Enter choice : 2
Popped value : 80
Enter choice : 3
Top element : 56
Enter choice : 1
Enter data : 78
Enter choice : 1
Enter data : 90
Enter choice : 6
90 78 56
Enter choice : 7
No. of elements in stack : 3
Enter choice : 8
All stack elements destroyed
Enter choice : 4
Stack is empty
Enter choice : 5
13. C Program to Implement Queue Data Structure using Linked List
#include <stdio.h>
#include <stdlib.h>
struct node
{
int info;
struct node *ptr;
}*front,*rear,*temp,*front1;
int frontelement();
void enq(int data);
void deq();
void empty();
void display();
void create();
void queuesize();
int count = 0;
void main()
{
int no, ch, e;
printf(" 1 - Enque");
printf(" 2 - Deque");
printf(" 3 - Front element");
printf(" 4 - Empty");
printf(" 5 - Exit");
printf(" 6 - Display");
printf(" 7 - Queue size");
create();
while (1)
{
printf(" Enter choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter data : ");
scanf("%d", &no);
enq(no);
break;
case 2:
deq();
break;
case 3:
e = frontelement();
if (e != 0)
printf("Front element : %d", e);
else
printf(" No front element in Queue as queue is empty");
break;
case 4:
empty();
break;
case 5:
exit(0);
case 6:
display();
break;
case 7:
queuesize();
break;
default:
printf("Wrong choice, Please enter correct choice ");
break;
}
}
}
/* Create an empty queue */
void create()
{
front = rear = NULL;
}
/* Returns queue size */
void queuesize()
{
printf(" Queue size : %d", count);
}
/* Enqueing the queue */
void enq(int data)
{
if (rear == NULL)
{
rear = (struct node *)malloc(1*sizeof(struct node));
rear->ptr = NULL;
rear->info = data;
front = rear;
}
else
{
temp=(struct node *)malloc(1*sizeof(struct node));
rear->ptr = temp;
temp->info = data;
temp->ptr = NULL;
rear = temp;
}
count++;
}
/* Displaying the queue elements */
void display()
{
front1 = front;
if ((front1 == NULL) && (rear == NULL))
{
printf("Queue is empty");
return;
}
while (front1 != rear)
{
printf("%d ", front1->info);
front1 = front1->ptr;
}
if (front1 == rear)
printf("%d", front1->info);
}
/* Dequeing the queue */
void deq()
{
front1 = front;
if (front1 == NULL)
{
printf(" Error: Trying to display elements from empty queue");
return;
}
else
if (front1->ptr != NULL)
{
front1 = front1->ptr;
printf(" Dequed value : %d", front->info);
free(front);
front = front1;
}
else
{
printf(" Dequed value : %d", front->info);
free(front);
front = NULL;
rear = NULL;
}
count--;
}
/* Returns the front element of queue */
int frontelement()
{ if ((front != NULL) && (rear != NULL))
return(front->info);
else
return 0;
}
/* Display if queue is empty or not */
void empty()
{
if ((front == NULL) && (rear == NULL))
printf("
Queue empty");
else
printf("Queue not empty");
}
Output:
1 - Enque
2 - Deque
3 - Front element
4 - Empty
5 - Exit
6 - Display
7 - Queue size
Enter choice : 1
Enter data : 14
Enter choice : 1
Enter data : 85
Enter choice : 1
Enter data : 38
Enter choice : 3
Front element : 14
Enter choice : 6
14 85 38
Enter choice : 7
Queue size : 3
Enter choice : 2
Dequed value : 14
Enter choice : 6
85 38
Enter choice : 7
Queue size : 2
Enter choice : 4
Queue not empty
Enter choice : 5
14. C Program to Implement a Doubly Linked List & provide Insertion, Deletion & Display Operations
#include <stdio.h>
#include <stdlib.h>
struct node
{
struct node *prev;
int n;
struct node *next;
}*h,*temp,*temp1,*temp2,*temp4;
void insert1();
void insert2();
void insert3();
void traversebeg();
void traverseend(int);
void sort();
void search();
void update();
void delete();
int count = 0;
void main()
{
int ch;
h = NULL;
temp = temp1 = NULL;
printf(" 1 - Insert at beginning");
printf(" 2 - Insert at end");
printf(" 3 - Insert at position i");
printf(" 4 - Delete at i");
printf(" 5 - Display from beginning");
printf(" 6 - Display from end");
printf(" 7 - Search for element");
printf(" 8 - Sort the list");
printf(" 9 - Update an element");
printf(" 10 - Exit");
while (1)
{
printf(" Enter choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
insert1();
break;
case 2:
insert2();
break;
case 3:
insert3();
break;
case 4:
delete();
break;
case 5:
traversebeg(); break;
case 6:
temp2 = h;
if (temp2 == NULL)
printf(" Error : List empty to display ");
else
{
printf(" Reverse order of linked list is : ");
traverseend(temp2->n);
}
break;
case 7:
search();
break;
case 8:
sort();
break;
case 9:
update();
break;
case 10:
exit(0);
default:
printf(" Wrong choice menu");
}
}
}
/* TO create an empty node */
void create()
{
int data;
temp =(struct node *)malloc(1*sizeof(struct node));
temp->prev = NULL;
temp->next = NULL;
printf(" Enter value to node : ");
scanf("%d", &data);
temp->n = data;
count++;
}
/* TO insert at beginning */
void insert1()
{
if (h == NULL)
{
create();
h = temp;
temp1 = h;
}
else
{
create();
temp->next = h;
h->prev = temp;
h = temp;
}
}
/* To insert at end */
void insert2()
{
if (h == NULL)
{
create();
h = temp;
temp1 = h;
}
else
{
create();
temp1->next = temp;
temp->prev = temp1;
temp1 = temp;
}
}
/* To insert at any position */
void insert3()
{
int pos, i = 2;
printf(" Enter position to be inserted : ");
scanf("%d", &pos);
temp2 = h;
if ((pos < 1) || (pos >= count + 1))
{
printf(" Position out of range to insert");
return;
}
if ((h == NULL) && (pos != 1))
{
printf(" Empty list cannot insert other than 1st position");
return;
}
if ((h == NULL) && (pos == 1))
{
create();
h = temp;
temp1 = h;
return;
}
else
{
while (i < pos)
{
temp2 = temp2->next;
i++;
}
create();
temp->prev = temp2;
temp->next = temp2->next;
temp2->next->prev = temp;
temp2->next = temp;
}
}
/* To delete an element */
void delete()
{
int i = 1, pos;
printf(" Enter position to be deleted : ");
scanf("%d", &pos);
temp2 = h;
if ((pos < 1) || (pos >= count + 1))
{
printf(" Error : Position out of range to delete");
return;
}
if (h == NULL)
{
printf(" Error : Empty list no elements to delete");
return;
}
else
{
while (i < pos)
{
temp2 = temp2->next;
i++;
}
if (i == 1)
{
if (temp2->next == NULL)
{
printf("Node deleted from list");
free(temp2);
temp2 = h = NULL;
return;
}
}
if (temp2->next == NULL)
{
temp2->prev->next = NULL;
free(temp2);
printf("Node deleted from list");
return;
}
temp2->next->prev = temp2->prev;
if (i != 1)
temp2->prev->next = temp2->next; /* Might not need this statement if i == 1 check */
if (i == 1)
h = temp2->next;
printf(" Node deleted");
free(temp2);
}
count--;
}
/* Traverse from beginning */
void traversebeg()
{
temp2 = h;
if (temp2 == NULL)
{
printf("List empty to display ");
return;
}
printf(" Linked list elements from begining : ");
while (temp2->next != NULL)
{
printf(" %d ", temp2->n);
temp2 = temp2->next;
}
printf(" %d ", temp2->n);
}
/* To traverse from end recursively */
void traverseend(int i)
{
if (temp2 != NULL)
{
i = temp2->n;
temp2 = temp2->next;
traverseend(i);
printf(" %d ", i);
}
}
/* To search for an element in the list */
void search()
{
int data, count = 0;
temp2 = h;
if (temp2 == NULL)
{
printf(" Error : List empty to search for data");
return;
}
printf(" Enter value to search : ");
scanf("%d", &data);
while (temp2 != NULL)
{
if (temp2->n == data)
{
printf(" Data found in %d position",count + 1);
return;
}
else
temp2 = temp2->next;
count++;
}
printf(" Error : %d not found in list", data);
}
/* To update a node value in the list */
void update()
{
int data, data1;
printf(" Enter node data to be updated : ");
scanf("%d", &data);
printf(" Enter new data : ");
scanf("%d", &data1);
temp2 = h;
if (temp2 == NULL)
{
printf(" Error : List empty no node to update");
return;
}
while (temp2 != NULL)
{
if (temp2->n == data)
{
temp2->n = data1;
traversebeg();
return;
}
else
temp2 = temp2->next;
}
printf(" Error : %d not found in list to update", data);
}
/* To sort the linked list */
void sort()
{
int i, j, x;
temp2 = h;
temp4 = h;
if (temp2 == NULL)
{
printf(" List empty to sort");
return;
}
for (temp2 = h; temp2 != NULL; temp2 = temp2->next)
{
for (temp4 = temp2->next; temp4 != NULL; temp4 = temp4->next)
{
if (temp2->n > temp4->n)
{
x = temp2->n;
temp2->n = temp4->n;
temp4->n = x;
}
}
}
traversebeg();
}
Output:
1 - Insert at beginning
2 - Insert at end
3 - Insert at position i
4 - Delete at i
5 - Display from beginning
6 - Display from end
7 - Search for element
8 - Sort the list
9 - Update an element
10 - Exit
Enter choice : 1
Enter value to node : 10
Enter choice : 2
Enter value to node : 50
Enter choice : 4
Enter position to be deleted : 1
Node deleted
Enter choice : 1
Enter value to node : 34
Enter choice : 3
Enter position to be inserted : 2
Enter value to node : 13
Enter choice : 4
Enter position to be deleted : 4
Error : Position out of range to delete
Enter choice : 1
Enter value to node : 15
Enter choice : 1
Enter value to node : 67
Enter choice : 3
Enter position to be inserted : 2
Enter value to node : 34
Enter choice : 4
Enter position to be deleted : 3
Node deleted
Enter choice : 7
Enter value to search : 15
Error : 15 not found in list
Enter choice : 8
Linked list elements from begining : 13 34 34 50 67
Enter choice : 9
Enter node data to be updated : 45
Enter new data : 89
Error : 45 not found in list to update
Enter choice : 9
Enter node data to be updated : 50
Enter new data : 90
Enter choice : 5
Linked list elements from begining : 13 34 34 90 67
Enter choice : 6
Reverse order of linked list is : 67 90 34 34 13
Enter choice : 7
Enter value to search : 90
Data found in 4 position
Enter choice : 8
Linked list elements from begining : 13 34 34 67 90
Enter choice : 7
Enter value to search : 90
Data found in 5 position
Enter choice : 9
Enter node data to be updated : 34
Enter new data : 56
Linked list elements from begining : 13 56 34 67 90
Enter choice : 10
15. C Program to Find the Largest Element in a Doubly Linked List
#include <stdio.h>
#include <stdlib.h>
struct node
{
int num;
struct node *next;
struct node *prev;
};
void create(struct node **);
int max(struct node *);
void release(struct node **);
int main()
{
struct node *p = NULL;
int n;
printf("Enter data into the list");
create(&p);
n = max(p);
printf("The maximum number entered in the list is %d.", n);
release (&p);
return 0;
}
int max(struct node *head)
{
struct node *max, *q;
q = max = head;
while (q != NULL)
{
if (q->num > max->num)
{
max = q;
}
q = q->next;
}
return (max->num);
}
void create(struct node **head)
{
int c, ch;
struct node *temp, *rear;
do
{
printf("Enter number: ");
scanf("%d", &c);
temp = (struct node *)malloc(sizeof(struct node));
temp->num = c;
temp->next = NULL;
temp->prev = NULL;
if (*head == NULL)
{
*head = temp;
}
else
{
rear->next = temp;
temp->prev = rear;
}
rear = temp;
printf("Do you wish to continue [1/0]: ");
scanf("%d", &ch);
} while (ch != 0);
printf("");
}
void release(struct node **head)
{
struct node *temp = *head;
*head = (*head)->next;
while ((*head) != NULL)
{
free(temp);
temp = *head;
(*head) = (*head)->next;
}
}
Output:
Enter data into the list
Enter number: 12
Do you wish to continue [1/0]: 1
Enter number: 7
Do you wish to continue [1/0]: 1
Enter number: 23
Do you wish to continue [1/0]: 1
Enter number: 4
Do you wish to continue [1/0]: 1
Enter number: 1
Do you wish to continue [1/0]: 1
Enter number: 16
Do you wish to continue [1/0]: 0
The maximum number entered in the list is 23.
16. C Program to Read a Linked List in Reverse
#include <stdio.h>
#include <stdlib.h>
struct node
{
int num;
struct node *next;
};
void create(struct node **);
void reversedisplay(struct node *);
void release(struct node **);
void display(struct node *);
int main()
{
struct node *p = NULL;
struct node_occur *head = NULL;
int n;
printf("Enter data into the list");
create(&p);
printf("Displaying the nodes in the list:");
display(p);
printf("Displaying the list in reverse:");
reversedisplay(p);
release(&p);
return 0;
}
void reversedisplay(struct node *head)
{
if (head != NULL)
{
reversedisplay(head->next);
printf("%d ", head->num);
}
}
void create(struct node **head)
{
int c, ch;
struct node *temp, *rear;
do
{
printf("Enter number: ");
scanf("%d", &c);
temp = (struct node *)malloc(sizeof(struct node));
temp->num = c;
temp->next = NULL;
if (*head == NULL)
{
*head = temp;
}
else
{
rear->next = temp;
}
rear = temp;
printf("Do you wish to continue [1/0]: ");
scanf("%d", &ch);
} while (ch != 0);
printf("");
}
void display(struct node *p)
{
while (p != NULL)
{
printf("%d ", p->num);
p = p->next;
}
printf("");
}
void release(struct node **head)
{
struct node *temp = *head;
*head = (*head)->next;
while ((*head) != NULL)
{
free(temp);
temp = *head;
(*head) = (*head)->next;
}
}
Output:
Enter data into the list
Enter number: 1
Do you wish to continue [1/0]: 1
Enter number: 2
Do you wish to continue [1/0]: 1
Enter number: 3
Do you wish to continue [1/0]: 1
Enter number: 4
Do you wish to continue [1/0]: 1
Enter number: 5
Do you wish to continue [1/0]: 0
Displaying the nodes in the list:
1 2 3 4 5
Displaying the list in reverse:
5 4 3 2 1
17. C Program to Reverse a Linked List
#include <stdio.h>
#include <stdlib.h>
struct node
{
int num;
struct node *next;
};
void create(struct node **);
void reverse(struct node **);
void release(struct node **);
void display(struct node *);
int main()
{
struct node *p = NULL;
int n;
printf("Enter data into the list");
create(&p);
printf("Displaying the nodes in the list:");
display(p);
printf("Reversing the list...");
reverse(&p);
printf("Displaying the reversed list:");
display(p);
release(&p);
return 0;
}
void reverse(struct node **head)
{
struct node *p, *q, *r;
p = q = r = *head;
p = p->next->next;
q = q->next;
r->next = NULL;
q->next = r;
while (p != NULL)
{
r = q;
q = p;
p = p->next;
q->next = r;
}
*head = q;
}
void create(struct node **head)
{
int c, ch;
struct node *temp, *rear;
do
{
printf("Enter number: ");
scanf("%d", &c);
temp = (struct node *)malloc(sizeof(struct node));
temp->num = c;
temp->next = NULL;
if (*head == NULL)
{
*head = temp;
}
else
{
rear->next = temp;
}
rear = temp;
printf("Do you wish to continue [1/0]: ");
scanf("%d", &ch);
} while (ch != 0);
printf("");
}
void display(struct node *p)
{
while (p != NULL)
{
printf("%d ", p->num);
p = p->next;
}
printf("");
}
void release(struct node **head)
{
struct node *temp = *head;
*head = (*head)->next;
while ((*head) != NULL)
{
free(temp);
temp = *head;
(*head) = (*head)->next;
}
}
Output:
Enter data into the list
Enter number: 1
Do you wish to continue [1/0]: 1
Enter number: 2
Do you wish to continue [1/0]: 1
Enter number: 3
Do you wish to continue [1/0]: 1
Enter number: 4
Do you wish to continue [1/0]: 1
Enter number: 5
Do you wish to continue [1/0]: 0
Displaying the nodes in the list:
1 2 3 4 5
Reversing the list...
Displaying the reversed list:
5 4 3 2 1
0 Comments