Data Structures Lab- CSL 201 - KTU 2019 Syllabus - Dr Binu V P

#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    {

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

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

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;             }    

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

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

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

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++;

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

/* 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

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  

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

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]-->

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

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) {

 #include<stdio.h> #include<stdlib.h> struct node { int coeff,exp; struct node *link; }*A=NULL,*B=NULL,*S=NULL,*P=NULL; struct node * create() { struct node *TP=NULL,*temp=NULL,*LTP=NULL; int n,coeff,exp,i; printf("\n Enter no of Terms of Poly  : "); scanf("%d",&n); printf("\n Enter Coefficint and Exponent of Poly in order(k1x^n+k2x^n-1..+knx^0  : "); for(i=0;i<n;i++)    {     scanf("%d%d",&coeff,&exp);     temp=(struct node*)malloc(sizeof(struct node));     temp->coeff=coeff;     temp->exp=exp;     temp->link=NULL;     if(TP==NULL)       {        TP=temp;        LTP=temp;       }     else       {        LTP->link=temp;        LTP=temp;       }     }     return TP; } void display(struct node*temp) { while(temp!=NULL)      {       printf("%dx^%d ---> ",temp->coeff,temp->exp);       temp=temp->link;      } printf("NULL\n"); } struct node * polyadd(struct node*P1, struct node *P2