[go: up one dir, main page]
Scribd
Upload
65 views21 pages

Ds Lab Internal

The document discusses different data structures including linked lists, stacks, and queues. It provides C++ code implementations for singly linked lists, circular linked lists, doubly linked lists, and stacks using arrays. The code includes functions to insert, delete, display, search, and get the length of nodes in the linked list structures. For the stack implementation, it includes functions to check if the stack is empty, check if full, peek the top element, and push or pop elements from the stack.

Uploaded by

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

Ds Lab Internal

The document discusses different data structures including linked lists, stacks, and queues. It provides C++ code implementations for singly linked lists, circular linked lists, doubly linked lists, and stacks using arrays. The code includes functions to insert, delete, display, search, and get the length of nodes in the linked list structures. For the stack implementation, it includes functions to check if the stack is empty, check if full, peek the top element, and push or pop elements from the stack.

Uploaded by

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

Linked List

#include<iostream.h>
#include<conio.h>

class Node
{
public:
int data;
Node *next;
};

class LinkedList
{
private:
Node *first;
public:
LinkedList()
{
first=NULL;
}

void insert(int x,int index)


{
Node *t=new Node;
t->data=x;

if(index<0 || index >length())


return;

if(index==0)
{
t->next=first;
first=t;
}
else
{
Node *p=first;
for(int i=0;i<index-1;i++)
p=p->next;

t->next=p->next;
p->next=t;
}
}
int Delete(int index)
{
int x=0;

if(index<1 || index>length())
return 0;
if(index==1)
{
Node *t=first;
first=first->next;

x=t->data;
delete t;
}
else
{

Node *p=first;
for(int i=0;i<index-2;i++)
p=p->next;

Node *t=p->next;
p->next=t->next;

x=t->data;
delete t;
}
return x;
}

void display()
{
Node *p=first;

while(p)
{
cout<<endl<<p->data;
p=p->next;
}
}
int length()
{
Node *p=first;
int count=0;

while(p)
{
p=p->next;
count++;
}
return count;
}
Node * search(int x)
{
Node *p=first;

while(p)
{
if(p->data==x)
return p;
p=p->next;
}
return NULL;
}

};

void main()
{
clrscr();

LinkedList ll;

ll.insert(10,0);
ll.insert(12,0);
ll.insert(23,0);
ll.insert(2,1);

ll.display();
cout<<endl<<"Deleted"<<ll.Delete(1);
}

Circular Linked List


#include<iostream.h>
#include<conio.h>

class Node
{
public:
int data;
Node *next;
};

class LinkedList
{
private:
Node *first;
public:
LinkedList()
{
first=NULL;
}

void insert(int x,int index)


{
Node *t=new Node;
t->data=x;

if(index<0 || index >length())


return;

if(index==0)
{
if(first==NULL)
{
t->next=t;
first=t;
}
else
{
Node *p=first;

while(p->next!=first)
p=p->next;

p->next=t;
t->next=first;
first=t;
}
}
else
{
Node *p=first;
for(int i=0;i<index-1;i++)
p=p->next;

t->next=p->next;
p->next=t;
}
}
int Delete(int index)
{
int x=0;

if(index<1 || index>length())
return 0;
if(index==1)
{
Node *t=first;

if(length()==1)
first=NULL;
else
first=first->next;

x=t->data;
delete t;
}
else
{

Node *p=first;
for(int i=0;i<index-2;i++)
p=p->next;

Node *t=p->next;
p->next=t->next;

x=t->data;
delete t;
}
return x;
}

void display()
{
Node *p=first;

do
{
cout<<endl<<p->data;
p=p->next;

}while(p!=first);
}
int length()
{
Node *p=first;
int count=0;

do
{
p=p->next;
count++;
}while(p!=first);

return count;
}
Node * search(int x)
{
Node *p=first;

do
{
if(p->data==x)
return p;
p=p->next;

}while(p!=first);

return NULL;
}

};

void main()
{
clrscr();

LinkedList ll;

ll.insert(10,0);
ll.insert(12,0);
ll.insert(23,0);
ll.insert(2,1);

ll.display();
cout<<endl<<"Deleted"<<ll.Delete(1);
}

Doubly Linked List


#include<iostream.h>
#include<conio.h>

class Node
{
public:
int data;
Node *prev;
Node *next;
};

class LinkedList
{
private:
Node *first;
public:
LinkedList()
{
first=NULL;
}

void insert(int x,int index)


{
Node *t=new Node;
t->data=x;

if(index<0 || index >length())


return;

if(index==0)
{
t->prev=NULL;
t->next=first;
if(first)
first->prev=t;

first=t;
}
else
{
Node *p=first;
for(int i=0;i<index-1;i++)
p=p->next;

t->next=p->next;
t->prev=t;

if(p->next)
p->next->prev=t;
p->next=t;
}
}
int Delete(int index)
{
int x=0;

if(index<1 || index>length())
return 0;
if(index==1)
{
Node *t=first;
first=first->next;
if(first)
first->prev=NULL;
x=t->data;
delete t;
}
else
{

Node *p=first;
for(int i=0;i<index-2;i++)
p=p->next;

Node *t=p->next;
if(p->next)
p->next->prev=t;
p->next=t->next;
x=t->data;
delete t;
}
return x;
}

void display()
{
Node *p=first;

while(p)
{
cout<<endl<<p->data;
p=p->next;
}
}
int length()
{
Node *p=first;
int count=0;

while(p)
{
p=p->next;
count++;
}
return count;
}
Node * search(int x)
{
Node *p=first;

while(p)
{
if(p->data==x)
return p;
p=p->next;
}
return NULL;
}

};

void main()
{
clrscr();

LinkedList ll;

ll.insert(10,0);
ll.insert(12,0);
ll.insert(23,0);
ll.insert(2,1);

ll.display();
cout<<endl<<"Deleted"<<ll.Delete(1);
}

Stack using Array


#include<iostream.h>

class Stack

private:

int size;

int *S;

int Top;

public:

Stack(int n)

size=n;

Top=-1;

S=new int[n];

int isEmpty()

return Top==-1;

int isFull()

return Top==size-1;

int stackTop()

if(Top==-1)
return 0;

else

return S[Top];

void push(int x)

if(isFull())

cout<<"Stack Full";

else

Top++;

S[Top]=x;

int pop()

int x=0;

if(isEmpty())

cout<<"Stack Empty";

else

x=S[Top--];

return x;

};

int isOperand(char a)
{

if(a=='+' || a=='-' || a=='*' || a=='/')

return 0;

return 1;

int pre(char a)

if(a=='+' || a=='-')

return 1;

if(a=='*' || a=='/')

return 2;

return 0;

void main()

clrscr();

Stack s(10);

s.push(10);

s.push(20);

s.push(30);

s.push(40);

s.display();

cout<<endl<<"Deleted"<<s.pop();
}

Queue using Linked List


#include<iostream.h>

#include<conio.h>

class Node

public:

int data;

Node *next;

};

class Queue

private:

Node *front,*rear;

public:

Queue()

front=rear=NULL;

void enqueue(int x)

Node *t=new Node;

if(t==NULL)

cout<<endl<<"Queue is Full";
else

t->data=x;

t->next=NULL;

if(front==NULL)

front=rear=t;

else

rear->next=t;

rear=t;

int dequeue()

int x=0;

if(front==NULL)

cout<<endl<<"Queue Empty";

else

x=front->data;

Node *t=front;

front=front->next;

delete t;
}

return x;

void display()

Node *p=front;

while(p)

cout<<endl<<p->data;

p=p->next;

int length()

Node *p=front;

int count=0;

while(p)

p=p->next;

count++;

return count;

}
};

void main()

clrscr();

Queue q;

q.enqueue(10);

q.enqueue(20);

q.enqueue(30);

q.enqueue(40);

q.display();

cout<<endl<<"Deleted"<<q.dequeue();

Binary Search Tree


#include<iostream.h>

#include<conio.h>

class Node

public:

Node *lchild;

int data;

Node *rchild;

};
class BST

public:

Node *root;

BST()

root=NULL;

void insert(int key)

Node *t;

t=new Node;

t->data=key;

t->lchild=NULL;

t->rchild=NULL;

if(root==NULL)

root=t;

else

Node *p=root,*q;

while(p)

{
q=p;

if(key==p->data)

return;

else if(key<p->data)

p=p->lchild;

else

p=p->rchild;

if(key<q->data)

q->lchild=t;

else

q->rchild=t;

void inorder(Node *p)

if(p)

inorder(p->lchild);

cout<<p->data<<",";

inorder(p->rchild);

};

void main()

{
BST b;

int n;

int key;

cout<<"Enter number of Key";

cin>>n;

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

cout<<"Enter a Key";

cin>>key;

b.insert(key);

b.inorder(b.root);

Bubble Sort
#include<iostream.h>

int main()

int A[]={5,3,6,8,2},n=5,temp;

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

for(int j=0;j<n-i-1;j++)

if(A[j]>A[j+1])

{
temp=A[j];

A[j]=A[j+1];

A[j+1]=temp;

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

cout<<A[i]<<endl;

Insertion Sort
#include<iostream.h>

int main()

int A[]={5,3,6,8,2},n=5,temp;

int j;

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

temp=A[i];

j=i-1;

while(j > -1 && A[j]>temp)

A[j+1]=A[j];

j--;

A[j+1]=temp;
}

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

cout<<A[i]<<endl;

BFS
#include<iostream>

using namespace std;

int
A[][7]={{0,1,0,1,0,0,0},{1,0,1,0,0,0,0},{0,1,0,1,1,1,0},{1,0,1,0,0,0,0},{0,0,1,0,0,0,1},{0,0,1,0,0,0,0},{0,0,0,0,1,0,0}};

int bfs[]={-1,-1,-1,-1,-1,-1,-1};

int Q[10];

int front=-1;

int rear=-1,n=7;

void BFS(int v)

cout<<v<<" ";

bfs[v]=0;

Q[++rear]=v;

do{

v=Q[++front];

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

if(A[v][i]==1)

{
if(bfs[i]==-1)

cout<<i<<" ";

bfs[i]=0;

Q[++rear]=i;

}while(front!=rear);

int main()

BFS(0);

return 0;

DFS
#include<iostream>

using namespace std;

int
A[][7]={{0,1,0,1,0,0,0},{1,0,1,0,0,0,0},{0,1,0,1,1,1,0},{1,0,1,0,0,0,0},{0,0,1,0,0,0,1},{0,0,1,0,0,0,0},{0,0,0,0,1,0,0}};

int dfs[]={-1,-1,-1,-1,-1,-1,-1};

int n=7;

void DFS(int v)
{

if(dfs[v]==-1)

cout<<v<<" ";

dfs[v]=0;

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

if(A[v][i]==1)

DFS(i);

int main()

DFS(0);

return 0;

You might also like