[go: up one dir, main page]

0% found this document useful (0 votes)
46 views40 pages

?DS Programs?

The document contains code snippets for various data structures and algorithms problems in C language: 1) Reverse a string using pointers 2) Pattern matching in a string 3) Searching an element in a 2D array 4) Appending two arrays 5) Binary search on a sorted array 6) Representing a sparse matrix 7) Insertion in a singly linked list 8) Deletion in a singly linked list 9) Implementation of a doubly linked list 10) Implementation of a stack using array

Uploaded by

ABHIRAM M
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
46 views40 pages

?DS Programs?

The document contains code snippets for various data structures and algorithms problems in C language: 1) Reverse a string using pointers 2) Pattern matching in a string 3) Searching an element in a 2D array 4) Appending two arrays 5) Binary search on a sorted array 6) Representing a sparse matrix 7) Insertion in a singly linked list 8) Deletion in a singly linked list 9) Implementation of a doubly linked list 10) Implementation of a stack using array

Uploaded by

ABHIRAM M
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 40

1.

REVERSE OF STRING USING POINTER


#include<stdio.h>
#include<string.h>
int main()
{
char st[100],rev[100];
char *str=st;
char *revs=rev;
int i,len;
printf("enter the string:");
scanf("%s",st);
len=strlen(st);
for(i=0;i<len;i++)
{
str=str+1;
}
for(i=len;i>=0;i--)
{
str=str-1;
*revs=*str;
revs=revs+1;
}
*revs='\0';
printf("reverse of string:%s",rev);
}
2.PATTERN MATCHING
#include <stdio.h>
#include <string.h>
int main() {
char text[100], pattern[100];
printf("Enter the string: ");
scanf("%s", text);
printf("Enter the pattern to be searched: ");
scanf("%s", pattern);

int c, d, e, g = 1, tlen, plen, position;


tlen = strlen(text);
plen = strlen(pattern);

if (plen > tlen) {


g = 1;
}
else {
for (c = 0; c <= tlen - plen; c++) {
position = e = c;
for (d = 0; d < plen; d++) {
if (pattern[d] == text[e]) {
e++;
}
else {
break;
}
}
if (d == plen) {
g = 0;
printf("The pattern is at index: %d\n", position);
break; // Break the outer loop if pattern is found
}
}

if (g == 1) {
printf("Pattern not found.\n");
}
}

return 0;
}
3.SEARCHING IN 2D ARRAY
#include<stdio.h>
int main()
{
int ar[5][5],valr,flag=0,j,i,valc,val;
printf("enter number of rows and columns of array:\n");
scanf("%d",&valr);
scanf("%d",&valc);
printf("enter the numbers:\n");
for(i=0;i<valr;i++)
{
for(j=0;j<valc;j++)
{
scanf("%d",&ar[i][j]);
}
}
//search an element
printf("enter a value to search its postion:");
scanf("%d",&val);
for(i=0;i<valr;i++)
{
for(j=0;j<valc;j++)
{
if(ar[i][j]==val)
{
printf("position of value %d in the array is %d,%d:",val,i,j);
flag=1;
break;
}
}
}
if(flag==0)
{
printf("element not found");
}
}
4.APPEND 2 ARRAY
#include<stdio.h>

int main()
{
int i, j, m, n, ar1[100], ar2[100];

printf("Enter total number of elements in the 1st array: ");


scanf("%d", &m);

printf("Enter total number of elements in the 2nd array: ");


scanf("%d", &n);
printf("Enter the elements of the 1st array:\n");
for (i = 0; i < m; i++)
{
scanf("%d", &ar1[i]);
}

printf("Enter the elements of the 2nd array:\n");


for (j = 0; j < n; j++)
{
scanf("%d", &ar2[j]);
}

// Appending the elements of the 2nd array to the 1st array


for (i = 0; i < n; i++)
{
ar1[m + i] = ar2[i];
}

printf("appended array:\n");
for (i = 0; i < m + n; i++)
{
printf("%d\t", ar1[i]);
}

return 0;
}
5.BINARY SEARCH
#include<stdio.h>
int binary(int ar[], int max, int min, int r);

int main()
{
int n, x, i, k;
printf("Enter maximum number of elements: ");
scanf("%d", &k);
n = k - 1;
int ar[k];
printf("Enter numbers in ascending order:\n");
for (i = 0; i < k; i++)
{
scanf("%d", &ar[i]);
}
printf("Enter the number to search: ");
scanf("%d", &x);
int result = binary(ar, n - 1, 0, x);
if (result == -1)
{
printf("Element not found\n");
}
else
{
printf("Element is present at index %d\n", result);
}
return 0;
}
int binary(int ar[], int max, int min, int r)
{
if (max >= min)
{
int mid = (max + min) / 2;
if (ar[mid] == r)
{
return mid;
}
else if (ar[mid] > r)
{
return binary(ar, mid - 1, min, r);
}
else
{
return binary(ar, max, mid + 1, r);
}
}
return -1;
}
6.SPARSE MATRIX
#include<stdio.h>

int main()
{
int i, j, k, r, c, rs;
printf("Enter number of columns of the matrix: ");
scanf("%d", &c);
printf("Enter number of rows of the matrix: ");
scanf("%d", &r);
printf("Enter elements of the matrix:\n");
rs = r * c + 1;
int matrixa[r][c];
int triple[rs][3];

for(i = 0; i < r; i++)


{
for(j = 0; j < c; j++)
{
printf("[%d,%d] = ", i+1, j+1);
scanf("%d", &matrixa[i][j]);
}
}

triple[0][0] = r;
triple[0][1] = c;
k = 0;

for(i = 0; i < r; i++)


{
for(j = 0; j < c; j++)
{
if(matrixa[i][j] != 0)
{
k = k + 1;
}
}
}
triple[0][2] = k;
k = 1;

for(i = 0; i < r; i++)


{
for(j = 0; j < c; j++)
{
if(matrixa[i][j] != 0)
{
triple[k][0] = i + 1;
triple[k][1] = j + 1;
triple[k][2] = matrixa[i][j];
k = k + 1;
}
}
}

printf("Sparse matrix is:\n");


for(i = 0; i < r; i++)
{
for(j = 0; j < c; j++)
{
printf("%d ", matrixa[i][j]);
}
printf("\n");
}

printf("Sparse matrix in triplet form is:\n");


for(i = 0; i < k; i++)
{
for(j = 0; j < 3; j++)
{
printf("%d ", triple[i][j]);
}
printf("\n");
}

return 0;
}
7.SINGLY LINKED LIST INSERTION
#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node *next;
};

int main()
{
struct node *newnode, *temp, *start = NULL;
int i, n;
printf("Enter number of nodes: ");
scanf("%d", &n);
printf("Enter the elements:\n");
for(i = 0; i < n; i++)
{
newnode = (struct node*)malloc(sizeof(struct node));
scanf("%d", &newnode->data);
newnode->next = NULL;

if(start == NULL)
{
start = newnode;
temp = newnode;
}
else
{
temp->next = newnode;
temp = newnode;
}
}

printf("The linked list is:\n");


temp = start;
while(temp != NULL)
{
printf("%d->", temp->data);
temp = temp->next;
}
printf("NULL");
return 0;
}
8.SINGLY LINKED LIST DELETION
#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node *next;
};

int main()
{
struct node *newnode, *temp, *start = NULL;
int i, n;
printf("Enter number of nodes: ");
scanf("%d", &n);
printf("Enter the elements:\n");

for(i = 0; i < n; i++)


{
newnode = (struct node*)malloc(sizeof(struct node));
scanf("%d", &newnode->data);
newnode->next = NULL;

if(start == NULL)
{
start = newnode;
temp = newnode;
}
else
{
temp->next = newnode;
temp = newnode;
}
}

printf("The linked list is:\n");


temp = start;
while(temp != NULL)
{
printf("%d->", temp->data);
temp = temp->next;
}
printf("NULL");
return 0;
}
9.DOUBLY LINKED LIST
#include<stdio.h>
#include<malloc.h>
struct node{
int data;
struct node *next;
struct node *previous;
};
int main()
{
struct node* start=NULL;
struct node* last;
struct node* temp;
int i,n,val;
printf("enter number of elements:\n");
scanf("%d",&n);
printf("enter %d integers:\n",n);
for(i=0;i<n;i++)
{
scanf("%d",&val);
struct node* newnode=(struct node*)malloc(sizeof(struct node));
newnode->data=val;
newnode->next=NULL;
if(start==NULL)
{
newnode->previous=NULL;
start=newnode;
last=newnode;
}
else
{
last->next=newnode;
newnode->previous=last;
last=newnode;
}
}
printf("Elements in forward direction:\n");
temp=start;
while(temp!=NULL)
{
printf("%d->",temp->data);
temp=temp->next;
}
printf("NULL\n");
printf("Elements in backward direction:\n");
temp=last;
while(temp!=NULL)
{
printf("%d->",temp->data);
temp=temp->previous;
}
printf("NULL");
return 0;
}
10.STACK USING ARRAY
#include<stdio.h>

int main()
{
int x=1, max;
printf("enter maximum size of stack:\n");
scanf("%d", &max);
int stack[max], top = -1;

printf("1. choice for push\n");


printf("2. choice for pop\n");
printf("3. choice for display stack\n");
printf("0. choice for exit\n");

printf("Enter your choice:");


scanf("%d", &x);
while(x!=0)
{
if(x==0)
{
break;
}
switch(x)
{
case 1:
{
int value;
if(top == max-1)
{
printf("stack is overflow\n");
}
else
{
printf("Enter an element to push: ");
scanf("%d", &value);
top++;
stack[top] = value;
}
break;
}
case 2:
{
if(top == -1)
{
printf("stack is in underflow\n");
}
else
{
printf("top element %d is popped\n", stack[top]);
top--;
}
break;
}
case 3:
{
int i;
if(top >= 0)
{
printf("stack is:\n");
for(i=top; i>=0; i--)
{
printf("%d\n", stack[i]);
}
}
else
{
printf("stack is empty\n");
}
break;
}
default:
{
printf("\nwrong choice\n");
break;
}
}

printf("Enter your choice:");


scanf("%d", &x);
}

return 0;
}
11.STACK USING LINKED LIST
#include<stdio.h>
#include<malloc.h>
int main()
{
struct node{
int data;
struct node* next;
struct node* prev;
};
struct node *temp,*newnode,*p,*last,*start=NULL;
int x=1,max,i=0;
printf("enter the maximum size of stack:");
scanf("%d",&max);
printf("1.choice for push\n");
printf("2.choice for pop\n");
printf("3.choice for display\n");
printf("4.choice for exit\n");
while(x!=0)
{
printf("enter your choice\n");
scanf("%d",&x);
if(x==0)
{
break;
}
switch(x)
{
case 1:
{
if(i==max)
{
printf("stack overflow");
}
else
{
printf("enter a value");
newnode=(struct node*)malloc(sizeof(struct node));
scanf("%d",&newnode->data);
newnode->next=NULL;
if(start==NULL)
{
start=newnode;
temp=newnode;
last=temp;
temp->prev=NULL;
}
else
{
temp->next=newnode;
temp=newnode;
temp->prev=last;
last=temp;
}
i++;
}
break;
}
case 2:
{
if(start==NULL)
{
printf("stack is empty\n");
}
else
{
printf("pop %d\n",temp->data);
temp=last;
p=temp;
temp=temp->prev;
last=temp;
free(p);
i--;
}
break;
}
case 3:
printf("stack is \n");
temp=last;
while(temp!=NULL)
{
printf("%d\n",temp->data);
temp=temp->prev;
}
break;
default:
{
printf("\n wrong choice\n");
break;
}
}
}
}
12.INFIX EXP TO POSTFIX EXP
#include <stdio.h>
#include <ctype.h>

char stack[100];
int top = -1;

void push(char x)
{
stack[++top] = x;
}
char pop()
{
if (top == -1)
{
return -1;
}
else
{
return stack[top--];
}
}

int priority(char x)
{
if (x == 'c')
return 0;
if (x == '+' || x == '-')
return 1;
if (x == '*' || x == '/')
return 2;
return -1;
}

int main()
{
char exp[100];
char *e;
char x;
printf("Enter the expression: ");
scanf("%s", exp);
printf("\n");
e = exp;
while (*e != '\0')
{
if (isalnum(*e))
printf("%c", *e);
else if (*e == 'c')
push(*e);
else if (*e == '1')
{
while ((x = pop()) != 'c')
printf("%c", x);
}
else
{
while (top != -1 && priority(stack[top]) >= priority(*e))
printf("%c", pop());
push(*e);
}
e++;
}

while (top != -1)


printf("%c", pop());

return 0;
}
13.QUEUE USING ARRAY
#include<stdio.h>
#define max 5
int front=-1,rear=-1;
int queue[max];
void insertq();
void deleteq();
void displayq();
int main()
{
int choice;
printf("1.INSERT\n");
printf("2.DELETE;\n");
printf("3.DISPLAY\n");
printf("4.EXIT\n");
while(1)
{
printf("enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:insertq();
break;
case 2:deleteq();
break;
case 3:displayq();
break;
case 4:return 0;
default:printf("invalid choice");
}
}
return 0;
}
void insertq()
{
int data;
if(rear==max-1)
printf("stack is full\n");
else
{
printf("enter the data:");
scanf("%d",&data);
rear++;
queue[rear]=data;
}
}
void deleteq()
{
int data;
if(front==rear)
printf("queue is empty");
else
{
front++;
data=queue[front];
printf("deleted element from queue is %d\n",data);
}
}
void displayq()
{
int i;
if(front==rear)
printf("queue is empty\n");
else
{
printf("the element in queue are :\n");
for(i=front+1;i<=rear;i++)
printf("\t%d",queue[i]);
printf("\n");
}
}
14.QUEUE USING LINKED LIST
#include<stdio.h>
#include<stdlib.h>

struct node {
int data;
struct node *link;
};

struct node *front = NULL;


struct node *rear = NULL;

void display();
void insertq();
void deleteq();

int main() {
int choice;
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Display\n");
printf("4. Exit\n");

while(1) {
printf("Enter your choice: ");
scanf("%d", &choice);

switch(choice) {
case 1:
insertq();
break;
case 2:
deleteq();
break;
case 3:
display();
break;
case 4:
return 0;
default:
printf("Invalid choice\n");
}
}
}

void insertq() {
struct node *temp;
int data;
temp = (struct node*)malloc(sizeof(struct node));

if(temp == NULL) {
printf("Overflow\n");
} else {
printf("Enter the data: ");
scanf("%d", &data);
temp->data = data;
temp->link = NULL;

if(rear != NULL) {
rear->link = temp;
rear = temp;
} else {
front = temp;
rear = temp;
}
}
}

void deleteq() {
struct node *temp;
int item;

if(front == NULL) {
printf("Queue is empty\n");
} else {
temp = front;
item = front->data;
front = front->link;
free(temp);
printf("Deleted element from the queue is %d\n", item);
}
}

void display() {
struct node *temp;

if(front == NULL) {
printf("Queue is empty\n");
} else {
temp = front;
printf("The elements in the queue are: ");

while(temp != NULL) {
printf("%d ", temp->data);
temp = temp->link;
}

printf("\n");
}
}
15.BINARY SEARCH TREE
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct node {
int data;
struct node *left;
struct node *right;
};
typedef struct node node;

node *root = NULL;

node *insert(node *);


void display(node *);
void search(node *);

int main() {
int op;
printf("1. insert\n");
printf("2. display\n");
printf("3. search\n");
printf("4. exit\n");

while (1) {
printf("\t choice: ");
scanf("%d", &op);
switch (op) {
case 1:
root = insert(root);
break;
case 2:
display(root);
break;
case 3:
search(root);
break;
case 4:
exit(0);
break;
default:
printf("Invalid choice\n");
}
}

return 0;
}

node *insert(node *root) {


int data, top;
node *current, *parent, *tempnode;

do {
tempnode = (node *)malloc(sizeof(node));
printf("Enter the data to insert: ");
scanf("%d", &data);
tempnode->data = data;
tempnode->left = NULL;
tempnode->right = NULL;

if (root == NULL)
root = tempnode;
else {
current = root;
while (current != NULL) {
parent = current;
if (data < parent->data) {
current = parent->left;
if (current == NULL)
parent->left = tempnode;
} else {
current = current->right;
if (current == NULL)
parent->right = tempnode;
}
}
}

printf("Do you want to add a new node?\n");


printf("1. Yes\t 2. No\t Choice: ");
scanf("%d", &top);
} while (top == 1);

return root;
}

void display(node *root) {


if (root != NULL) {
printf("\n %d", root->data);
display(root->left);
display(root->right);
}
}

void search(node *root) {


node *ptr;
int item, flag = 0;
ptr = root;

printf("Enter the value to search: ");


scanf("%d", &item);

while (ptr != NULL && flag == 0) {


if (item < ptr->data)
ptr = ptr->left;
else if (item == ptr->data)
flag = 1;
else
ptr = ptr->right;
}

if (flag == 1)
printf("\nThe element is found in the tree\n");
else
printf("The element does not exist in the tree\n");
}
16.BUBBLE SORT
#include <stdio.h>
int main() {
int a[10], num, i, j, swap;
printf("Enter the size of the array: ");
scanf("%d", &num);

printf("Enter the elements of the array:\n");


for (i = 0; i < num; i++) {
scanf("%d", &a[i]);
}

for (i = 0; i < num; i++) {


for (j = 0; j < num - i - 1; j++) {
if (a[j] > a[j + 1]) {
swap = a[j];
a[j] = a[j + 1];
a[j + 1] = swap;
}
}
}

printf("The sorted array is:\n");


for (i = 0; i < num; i++) {
printf("%d\n", a[i]);
}

return 0;
}
17.SELECTION SORT
#include <stdio.h>
int main() {
int a[10], num, i, j, pos, temp;

printf("Enter the size of the array: ");


scanf("%d", &num);

for (i = 0; i < num; i++) {


printf("a[%d] = ", i);
scanf("%d", &a[i]);
}

for (i = 0; i < num - 1; i++) {


pos = i;

for (j = i + 1; j < num; j++) {


if (a[j] < a[pos]) {
pos = j;
}
}

if (pos != i) {
temp = a[i];
a[i] = a[pos];
a[pos] = temp;
}
}

printf("The sorted array is:\n");


for (i = 0; i < num; i++) {
printf("%d\n", a[i]);
}

return 0;
}
18.INSERTION SORT
#include<stdio.h>

int main() {
int a[10], num, i, j, temp;
printf("Enter the size of the array: ");
scanf("%d", &num);

for(i = 0; i < num; i++) {


printf("a[%d] = ", i);
scanf("%d", &a[i]);
}

for(i = 1; i < num; i++) {


temp = a[i];
j = i - 1;
while(temp < a[j] && j >= 0) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
}
printf("The sorted array is:\n");
for(i = 0; i < num; i++) {
printf("%d\n", a[i]);
}

return 0;
}
19.SORTED STRINGS
#include<stdio.h>
#include<string.h>

struct student {
char name[50];
};

int main() {
struct student list[50];
struct student temp;
int n, i;

printf("Enter the number of strings: ");


scanf("%d", &n);

printf("Enter the strings:\n");


for (i = 0; i < n; i++) {
scanf("%s", list[i].name);
}
for (i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (strcmp(list[i].name, list[j].name) > 0) {
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
}

printf("\nSorted strings:\n");
for (i = 0; i < n; i++) {
printf("%s\n", list[i].name);
}

return 0;
}
20.LINEAR SEARCH
#include<stdio.h>

int main()
{
int ar[100];
int n, target = 0;

printf("Enter the size of the array: ");


scanf("%d", &n);

printf("Enter array values:\n");


for(int i = 0; i < n; i++)
{
scanf("%d", &ar[i]);
}

printf("Enter the target value to search: ");


scanf("%d", &target);

for(int i = 0; i < n; i++)


{
if(ar[i] == target)
{
printf("Value found at position: %d", i);
return 0;
}
}

printf("Value not found");

return 0;
}

You might also like