Scribd
Upload
6 views9 pages

DSA ANS

The document contains multiple C++ code snippets demonstrating various data structures and algorithms, including singly linked lists, doubly linked lists, stacks, queues, binary search trees, and graphs. Each section provides code for insertion, deletion, and traversal operations, along with specific functionalities like converting infix expressions to postfix and checking for subsets using hashing. The document serves as a comprehensive reference for implementing these data structures and their operations.

Uploaded by

emptybags06
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
6 views9 pages

DSA ANS

The document contains multiple C++ code snippets demonstrating various data structures and algorithms, including singly linked lists, doubly linked lists, stacks, queues, binary search trees, and graphs. Each section provides code for insertion, deletion, and traversal operations, along with specific functionalities like converting infix expressions to postfix and checking for subsets using hashing. The document serves as a comprehensive reference for implementing these data structures and their operations.

Uploaded by

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

1.

Singly Linked List

#include <iostream>
using namespace std;
struct node{
int n;
node* x = NULL;
};

node* h = NULL;

void insert(int a){


node* nn = new node;
nn->n = a;
if(h==NULL)
h = nn;
else{
node* t = h;
while(t->x!=NULL)
t = t->x;
t->x = nn;
}
}

void print(){
while(h!=NULL){
cout<<h->n<<" ";
h = h->x;
}
}

int main(){
int n;
while(cin>>n){
insert(n);
}
print();
}
------------------------------------------------------------------
2. Doubly Linked List

#include <iostream>
using namespace std;
struct node{
int n;
node* x;
node* y = NULL;
};

node* h = NULL;
node* t = NULL;

void insert(int a){


node* nn = new node;
nn->n = a;
nn->x = t;
if(h==NULL)
h = nn;
if(t!=NULL)
t->y = nn;
t = nn;
}

void pf(){
cout<<"Doubly linked list forwards : ";
while(h!=NULL){
cout<<h->n<<" ";
h = h->y;
}
}
void pr(){
cout<<"\nDoubly linked list backwards : ";
while(t!=NULL){
cout<<t->n<<" ";
t = t->x;
}
}

int main(){
int n;
while(cin>>n){
insert(n);
}
pf();
pr();
}
-----------------------------------------------------------------------------------
-------
3. Stack using Array

#include <iostream>
using namespace std;
int arr[100];
int top = -1;
void insert(int n){
if(top >= 99){
return;
}
arr[++top] = n;
}

int main(){
int n,a;
cin>>n;
cout<<"Stack Elements\n";
for(int i=0;i<n;i++){
cin>>a;
insert(a);
}
for(int i=top;i>=0;i--){
cout<<arr[i]<<"\n";
}
}
-----------------------------------------------------------------------------------
----------
4. Stack using Linked List

#include <iostream>
using namespace std;
struct node{
int n;
node* x;
};

node* h = NULL;

void push(int a){


node* nn = new node;
nn->n = a;
nn->x = h;
h = nn;
}

void print(){
cout<<"Stack Elements\n";
while(h!=NULL){
cout<<h->n<<"\n";
h = h->x;
}
}

int main(){
int n;
char ch;
while(cin>>n){
push(n);
cin>>ch;
if(ch!='Y')
break;
}
print();
}
-----------------------------------------------------------------------------------
---
5. Infix to Postfix

#include<iostream>
#include<stack>
using namespace std;
int priority(char c){
if(c=='+' || c=='-')
return 1;
if(c=='*' || c=='/')
return 2;
if(c=='^')
return 3;
return 0;
}

void convert(string expr){


stack<int> s;
string postfix = "";
int i=0;

while(expr[i] !='\0'){
if(expr[i]>='a' && expr[i]<='z' || expr[i]>'A' && expr[i]<='Z'){
postfix += expr[i];
i++;
}
else if(expr[i]=='('){
s.push(expr[i]);
i++;
}
else if(expr[i]==')'){
while(s.top()!='('){
postfix += s.top();
s.pop();
}
s.pop();
i++;
}
else{
while(!s.empty() && priority(expr[i]) <= priority(s.top())){
postfix += s.top();
s.pop();
}
s.push(expr[i]);
i++;
}
}
while(!s.empty()){
postfix += s.top();
s.pop();
}
cout<<postfix;
}

int main(){
string expr;
cin>>expr;
string postfix;
convert(expr);
}
-----------------------------------------------------------------------------------
---
6. Delete at end of DLL

#include <iostream>
using namespace std;
struct node{
int n;
node* x;
node* y = NULL;
};

node* h = NULL;
node* t = NULL;

void insert(int a){


node* nn = new node;
nn->n = a;
nn->x = t;
if(h==NULL)
h = nn;
if(t!=NULL)
t->y = nn;
t = nn;
}

void print(){
while(h!=NULL){
cout<<h->n<<" ";
h = h->y;
}
}

void delatlast(){
if(t->x!=NULL){
t = t->x;
t->y = NULL;
}
}

int main(){
int n,a,m;
cin>>n;
for(int i=0;i<n;i++){
cin>>a;
insert(a);
}
print();
cin>>m;
for(int i=0;i<m;i++){
delatlast();
}
print();
}
-----------------------------------------------------------------------------------
---
7. Queue using Linked List

#include <iostream>
using namespace std;
struct node{
int n;
node* x;
node* y = NULL;
};

node* h = NULL;
node* t = NULL;

void enqueue(int a){


node* nn = new node;
nn->n = a;
nn->x = t;
if(h==NULL)
h = nn;
if(t!=NULL)
t->y = nn;
t = nn;
}

void front(){
cout<<h->n<<" ";
}
void rear(){
cout<<t->n<<" ";
}

void dequeue(){
h = h->y;
h->x = NULL;
}

int main(){
int n,a;
cin>>n;
for(int i=0;i<n;i++){
cin>>a;
enqueue(a);
}
front();
rear();
dequeue();
front();
rear();
}
------------------------------------------------------------------------------
8. Packet Collision

#include <iostream>
using namespace std;
int main(){
int m,n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
cin>>m;
for(int i=0;i<=n-m;i++){
int mx = 0;
for(int j=i;j<i+m;j++){
mx = max(mx,arr[j]);
}
cout<<mx<<" ";
}
}
------------------------------------------------------------------------------
9. Binary Search Tree

#include <iostream>
using namespace std;
struct node{
int n;
node* l = NULL;
node* r = NULL;
};

node* root = NULL;

void insert(int a){


node* nn = new node;
node* temp = root;
nn->n=a;
if(temp==NULL){
root = nn;
return;
}
while(true){
while(temp->n > nn->n and temp->l!=NULL)
temp = temp->l;
if(temp->n > nn->n and temp->l==NULL){
temp->l = nn;
break;
}
while(temp->n < nn->n and temp->r!=NULL)
temp = temp->r;
if(temp->n < nn->n and temp->r==NULL){
temp->r = nn;
break;
}
}
}

int display(node* r){


node* temp = r;
if(temp==NULL)
return 0;
display(temp->l);
cout<<temp->n<<" ";
display(temp->r);
}
int main(){
int a;
while(cin>>a){
if(a==-1)
break;
insert(a);
}
cout<<"Tree values are:\n";
display(root);
}
------------------------------------------------------------------------------
10. Graph - Adjacency List

#include<iostream>
#include<vector>
using namespace std;
void addedge(vector<int>adj[],int u,int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
void print(vector<int>adj[],int a)
{
for(int i=0;i<a;i++)
{
cout<<i;
for(int j=0;j<adj[i].size();j++)
{
cout<<" -> "<<adj[i][j];
}
cout<<endl;
}
}
int main()
{
int V,a,b;
cin>>V;
vector<int>adj[V];
int E;
cin>>E;
for(int i=0;i<E;i++)
{
cin>>a>>b;
addedge(adj,a,b);
}
print(adj,V);
}
---------------------------------------------------------------------------------
11. Subset using Hashing

#include<iostream>
using namespace std;
int main()
{
int m,n;
cin>>m>>n;
int arr1[m];
int arr2[n];
for(int i=0;i<m;i++){
cin>>arr1[i];
}
int c=0;
for(int i=0;i<n;i++){
cin>>arr2[i];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(arr2[i]==arr1[j])
c++;
}
}
if(c==n)
{
cout<<"Subset";
}
else
{
cout<<"Not a subset";
}
}
---------------------------------------------------------------------------------
12. Queue - Insertion and Deletion

#include <iostream>
#include <queue>
using namespace std;
int main(){
queue<int> q;
int n,m,a;
cin>>n;
for(int i=0;i<n;i++){
cin>>a;
q.push(a);
}
cin>>m;
for(int i=0;i<m;i++){
cout<<"Element deleted from queue is : "<<q.front()<<"\n";
q.pop();
}
}

You might also like