Posts

Data Structure Lab CSL 201 Manual KTU - Dr Binu V P-9847390760

 Dr Binu V P - About Me Data Structures CST 201 KTU Theory Notes  ( Learn Theory Before You Attempt Lab Exercise) SCHEME AND SYLLABUS 1. Polynomial Addition using Arrays 2. Sparse Matrix Representation and sum 3. Stack using Array 4. Queue using Array 5. Circular Queue using Arrays 6. Double Ended Queue  7. Priority Queue  8. Infix to postfix 9. Infix to prefix conversion 10. Prefix to infix conversion 11. Evaluation of postfix expression 12. Singly Linked List 13. Doubly Linked List   14. Stack using Linked List 15. Queue using Linked List 16. Polynomial Addition using Linked list 17. Polynomial Multiplication using Linked List 18. Binary Tree using arrays and traversals 19. Binary Tree using Linked List and Traversal 20. Binary Search Tree Implementation and Traversal 21.Sorting Algorithms       Bubble sort       Exchange sort       Selection Sort       Insertion Sort       Quick Sort       Merge Sort       Heap Sort 22.Searching Algorithm      Linear Search      Binary Search 23. Gr
Post a Comment
Read more

Scheme and Syllabus Data Structure Lab CSL 201

  Scheme and Syllabus
Post a Comment
Read more

Simulation of a basic memory allocator and garbage collector using doubly linked list

#include<stdio.h> #include<stdlib.h> struct node { int data; int avail; struct node *llink,*rlink; }*first=NULL,*last=NULL,*temp=NULL,*t=NULL; void create() { temp=(struct node*)malloc(sizeof(struct node)); printf("Enter data:"); scanf("%d",&temp->data); temp->avail=1; temp->llink=NULL; temp->rlink=NULL; if(first==NULL) { first=temp; last=temp; } else { last->rlink=temp; temp->llink=last; last=temp; } } void display() { temp=first; printf("NULL"); while(temp!=NULL) { printf(" %d:%d<---->",temp->data,temp->avail); temp=temp->rlink; } printf(" NULL\n"); } void allocate() { int size,newdata; printf("Enter size\n"); scanf("%d",&size); temp=first; while(temp!=NULL) { if(temp->data>=size && temp->avail==1)    break; temp=temp->rlink; } if( temp==NULL)   printf("cannot allocate\n"); else if (temp->data==size)   temp->avail=0;  else    {
Post a Comment
Read more

Polynomial Addition using Arrays

Learn Theory -  Polynomials /****************************************************************/ #include<stdio.h> void create(int poly[],int degree) {     int i=0;          printf("Enter the coeffecients for:\n");     for(i=degree;i>=0;i--)     {         printf("Exp_%d: ",i);         scanf("%d",&poly[i]);     } } void display(int poly[],int degree) {     int i;     for(i=degree;i>=0;i--)     {                  if(i!=degree && poly[i]>0)         {              printf("+");          }         printf("%dx^%d",poly[i],i);     } } void main() {     int poly1[100]={0},degree1,poly2[100]={0},degree2,degreeresult,polyresult[100],i=0;          printf("Enter the degree of first polynomial");      scanf("%d",&degree1);     create(poly1,degree1);     printf("Enter the degree of second polynomial");      scanf("%d",&degree2);     create(poly2,degree2);     if(degree1>degree
Post a Comment
Read more

Graph-DFS

Learn Theory - DFS DFS Implementation using a recursive function /*******************************************************************************/ #include <stdio.h> #define MAX_VERTICES 10 // Function to perform Depth-First Search (DFS) void dfs(int vertex, int visited[MAX_VERTICES], int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES], int numVertices) {     printf("V%d ", vertex ); // Assuming vertex labels are 'V0', 'V1', 'V2', ...     // Mark the current vertex as visited     visited[vertex] = 1;     // Recursively visit all unvisited neighbors     for (int i = 0; i < numVertices; i++) {         if (adjacencyMatrix[vertex][i] == 1 && !visited[i]) {             dfs(i, visited, adjacencyMatrix, numVertices);         }     } } int main() {     int numVertices, i, j;     printf("Enter the number of vertices (max %d): ", MAX_VERTICES);     scanf("%d", &numVertices);     // Input the adjacency matrix     int adjacency
Post a Comment
Read more

Graph-BFS

Lear Theory - BFS /** BFS Implementation *************/ #include <stdio.h> #include <stdlib.h> #define MAX_VERTICES 10 // Function to perform Breadth-First Search (BFS) void bfs(int startVertex, int visited[MAX_VERTICES], int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES], int numVertices) {     // Create a queue for BFS     int queue[MAX_VERTICES];     int front = -1, rear = -1;     // Enqueue the startVertex     queue[++rear] = startVertex;     visited[startVertex] = 1;     while (front != rear) {         // Dequeue a vertex from the front of the queue         int currentVertex = queue[++front];         printf("V%d ", currentVertex ); // Assuming vertex labels are 'V0', 'V1', 'V2', ...         // Enqueue all unvisited neighbors         for (int i = 0; i < numVertices; i++) {             if (adjacencyMatrix[currentVertex][i] == 1 && !visited[i]) {                 queue[++rear] = i;                 visited[i] = 1;             }    
Post a Comment
Read more

Doubly Linked List

Learn Theory - Doubly Linked List /*********************************************************************/ #include<stdio.h> #include<stdlib.h> struct Node { int data; struct Node *prev,*next; }*first=NULL,*last=NULL,*temp=NULL,*trav=NULL; void create() { temp=(struct Node*)malloc(sizeof(struct Node)); printf("Enter data:"); scanf("%d",&temp->data); temp->prev=NULL; temp->next=NULL; if(first==NULL) { first=temp; last=temp; } else { last->next=temp; temp->prev=last; last=temp; } } void display() { temp=first; printf("NULL"); while(temp!=NULL) { printf(" %d<---->",temp->data); temp=temp->next; } printf(" NULL\n"); } void insert_begin() { temp=(struct Node*)malloc(sizeof(struct Node)); printf("Enter data"); scanf("%d",&temp->data); temp->prev=NULL; temp->next=NULL; if(first==NULL) { first=temp; last=temp; } else { temp->next=first; first->prev=temp; first=temp
Post a Comment
Read more

Graph-Adjacency List

Learn Theory - Graph Representations /* Implementation- Graph representation *****/ #include <stdio.h> #include <stdlib.h> struct vertex { int data; struct vertex *next; }*adj[50],*tail[50],*temp=NULL; int nv; void read() { int adv; printf("Enter the Number of vertices\n"); scanf("%d",&nv); // storing element from [1][1] //// assuming the vertices are numbered v1 v2..vn and we will enter only the index 1,2...n for(int i=1;i<=nv;i++) { printf("Enter the list of vertices adjacent to v%d -1 to stop\n",i); adj[i]=NULL;tail[i]=NULL; while(1) {      scanf("%d",&adv);      if(adv==-1) break;      temp=(struct vertex *)malloc(sizeof(struct vertex));      temp->data=adv;      temp->next=NULL;      if(adj[i]==NULL) {adj[i]=temp;tail[i]=temp;} else { tail[i]->next=temp;tail[i]=temp;} } } }//end of read void disp() { printf("Adjacency List..\n"); for(int i=1;i<=nv;i++) { temp=adj[i]; printf("V%d-->",i
Post a Comment
Read more

Graph-Incident Matrix, In-degree,Out-degree

Learn Theory- Graph Representations #include <stdio.h> int inc[50][50],nv,ne; void read() { int i,j,e;      printf("Enter the Number of vertices\n");      scanf("%d",&nv);      printf("Enter the Number of edges\n");      scanf("%d",&ne);      // storing element from [1][1]      //assuming the vertices and edges are numbered 1 2..n and we will enter only the index      //use 1 for outgoing edges -1 for incoming edges 0 for no relation      for(int i=1;i<=nv;i++)      {      printf("Enter the details of edges incident to v%d \n",i);      for(j=1;j<=ne;j++)      {      scanf("%d",&e);      inc[i][j]=e;      }      } }//end of read void disp() { printf("Incident Matrix..\n"); for(int i=1;i<=nv;i++) {      for(int j=1;j<=ne;j++)      printf("%5d",inc[i][j]);      printf("\n"); } } void indegree() { int vi,i,id=0; printf("Enter the vertex index to compute inde
Post a Comment
Read more

Graph-Adjacency Matrix

Learn Theory- Graph Representations /* Graph representation using adjacency matrix and finding the degree */ #include <stdio.h> int adj[50][50],n; void read() { int ad; printf("Enter the Number of vertices\n"); scanf("%d",&n); // storing element from [1][1] //// assuming the vertices are numbered v1 v2..vn and we will enter only the index 1,2...n for(int i=1;i<=n;i++) { printf("Enter the list of vertices adjacent to v%d -1 to stop\n",i); while(1) {     scanf("%d",&ad);     if(ad==-1) break;         adj[i][ad]=1; } } }//end of read void disp() { printf("Adjacency Matrix..\n"); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) printf("%5d",adj[i][j]); printf("\n"); } } void calculateDegree() {     int i, j;     printf("Vertex\tDegree\n");     for (i = 1; i <=n; i++) {         int degree = 0;         for (j = 1; j <= n; j++) {             if (adj[i][j] == 1) {                 degree++;
Post a Comment
Read more

Binary Tree using Arrays and Traversal

Learn Theory- Binary Tree and Traversals #include <stdio.h> int complete_node = 15; // array to store the tree char tree[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', '\0', '\0', 'J', '\0', 'K', 'L'}; int get_right_child(int index) { // node is not null // and the result must lie within the number of nodes for a complete binary tree if(tree[index]!='\0' && ((2*index)+2)<=complete_node) return (2*index)+2; // right child doesn't exist return -1; } int get_left_child(int index) { // node is not null // and the result must lie within the number of nodes for a complete binary tree if(tree[index]!='\0' && (2*index+1)<=complete_node) return 2*index+1; // left child doesn't exist return -1; } void preorder(int index) { // checking for valid index and null node if(index>=0 && tree[index]!='\0') { prin
Post a Comment
Read more

Prefix to Infix conversion

/* Prefix to Infix Conversion Implementation */ #include <string.h> #include <ctype.h> #include <stdio.h> char opnds[50][80],oprs[50]; int topr=-1,topd=-1; void pushd(char *opnd) { strcpy(opnds[++topd],opnd); } char *popd() { return(opnds[topd--]); } void pushr(char opr) { oprs[++topr]=opr; } char popr() { return(oprs[topr--]); } int empty(int t) { if( t == 0) return(1); return(0); } void main() { char prfx[50],ch,str[50],opnd1[50],opnd2[50],opr[2]; int i=0,k=0,opndcnt=0; printf("Give an Expression = "); scanf("%s",prfx); printf(" Given Prefix Expression : %s\n",prfx); while( (ch=prfx[i++]) != '\0') { if(isalnum(ch)) { str[0]=ch; str[1]='\0'; pushd(str); opndcnt++; if(opndcnt >= 2) { strcpy(opnd2,popd()); strcpy(opnd1,popd()); strcpy(str,"("); strcat(str,opnd1); ch=popr(); opr[0]=ch;opr[1]='\0'; strcat(str,opr); strcat(str,opnd2); strcat(str,")"); pushd(str); opndcnt-=1; } } else
Post a Comment
Read more

Sparse Matrix -Representation,Addition ,Transpose

Sparse Matrix /*******************************************************************************/  #include<stdio.h> void read_sparsemat(int mat_normal[100][100],int r,int c) {     int i=0,j=0;     for(i=0;i<r;i++)     {         for(j=0;j<c;j++)         {             scanf("%d",&mat_normal[i][j]);         }     } } void print_sparsemat(int mat_normal[100][100],int r,int c) {     int i=0,j=0;     for(i=0;i<r;i++)     {         printf("\n");         for(j=0;j<c;j++)         {             printf("%d  ",mat_normal[i][j]);         }     } } void print_tuple(int mat_tup[100][3],int tr) {     int i,j;   printf("\nrows--- columns--- values");     for(i=0;i<tr;i++)     {         printf("\n");         for(j=0;j<3;j++)         {             printf("%d\t",mat_tup[i][j]);         }     }           } int conv_tuple(int mat_normal[100][100],int r,int c,int mat_tup[100][3]) {     //sparse  to Tuple Form Conversion  
Post a Comment
Read more

Binary Tree implementation and Traversal

Binary Tree and Traversal #include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<string.h> struct node { int data; struct node *left; struct node *right; }; typedef struct node Node; // Inorder traversal void inorder(Node *root) { if (root == NULL) return; inorder(root->left); printf("%d ->", root->data); inorder(root->right); } // Preorder traversal void preorder(Node *root) { if (root == NULL) return; printf("%d ->", root->data); preorder(root->left); preorder(root->right); } // Postorder traversal void postorder(Node *root) { if (root == NULL) return; postorder(root->left); postorder(root->right); printf("%d ->", root->data); } // Create a new Node Node* createNode(value) { Node *newNode = malloc(sizeof(Node)); newNode->data = value; newNode->left = NULL; newNode->right = NULL; return newNode; } // Insert on the left of the nod
Post a Comment
Read more

Hash Table with Chaining

Learn Theory- Chaining #include<stdio.h> #include<stdlib.h> #include<conio.h> #define size 10 struct node {     int data;     struct node *next; }; struct node *chain[size]; void init() {     int i;     for(i = 0; i < size; i++)         chain[i] = NULL; } void insert(int value) {     //create a newnode with value     int key;     struct node *newNode = malloc(sizeof(struct node));     newNode->data = value;     newNode->next = NULL;     //calculate hash key     key = value % size;     //check if chain[key] is empty     if(chain[key] == NULL) chain[key] = newNode;     //collision     else     { //add the node at the end of chain[key]. struct node *temp = chain[key]; while(temp->next) {     temp = temp->next; } temp->next = newNode;     }     printf("Entered Value added to hash table\n"); } void printhashtable() {     int i;     for(i = 0; i < size; i++)     { struct node *temp = chain[i]; printf("chain[%d]-->
Post a Comment
Read more

Hash Table with Linear Probing

Learn Theory - Linear probing #include<stdio.h> #include<stdlib.h>   /* to store a data (consisting of key and value) in hash table array */ struct item  {     int key;     int value; };   /* each hash table item has a flag (status) and data (consisting of key and value) */ struct hashtable_item  {      int flag;     /*      * flag = 0 : data does not exist      * flag = 1 : data exists      * flag = 2 : data existed at least once     */       struct item *data;   };   int size = 0; int max = 10; struct hashtable_item array[10]; /* initializing hash table array */ void init_array() {     int i;     for (i = 0; i < max; i++)      { array[i].flag = 0; array[i].data = NULL;     } }   /* to every key, it will generate a corresponding index */ int hashcode(int key) {     return (key % max); }   /* to insert an element in the hash table */ void insert(int key, int value) {     int index = hashcode(key);     int i = index;       /* creating new item to insert in the hash t
Post a Comment
Read more

Binary search Tree Implementation and Traversal

Binary Search Tree and Operations /******* BST Tree and Operations **********/ #include <stdio.h> #include <stdlib.h>struct Node { int key; struct Node* left; struct Node* right; }; struct Node *root=NULL,*temp=NULL; struct Node* createNode(int key) {      struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));      newNode->key = key;      newNode->left = newNode->right = NULL;      return newNode; } struct Node* insert(struct Node* node, int key) { // Base case: if the tree is empty, create a new node if (node == NULL) {      return createNode(key);      } // Compare the key with the current node's key if (key < node->key) { // Recursively insert into the left subtree      node->left = insert(node->left, key);      } else if (key > node->key) { // Recursively insert into the right subtree    node->right = insert(node->right, key); } // Return the modified node return node; } void inOrderTraversal(struct Node* node) {
Post a Comment
Read more