Data Structures Lab: Assignment 1 [Each Q- 20 Marks]
[Link] Statement: Write a program in C to check whether a given
string of braces (only) is well formed or not.
For example, the string (((()) (())) is well formed but the song ( ) ( ) ) is all
formed.
(A)
#include <stdio.h>
int isWellFormed(const char *str) {
int count = 0;
while (*str) {
if (*str == '(')
count++;
else if (*str == ')') {
if (count == 0)
return 0; // unmatched closing
count--;
}
str++;
}
return count == 0; // should end with zero
}
int main() {
char str[100];
printf("Enter a string of braces: ");
scanf("%s", str);
if (isWellFormed(str))
printf("The string is well formed.\n");
else
printf("The string is NOT well formed.\n");
return 0;
}
OUTPUT:
[Link] Statement: Write a program to Searching for a specified
element in a circularly linked list.
(A)
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
struct Node* insert(struct Node* last, int data) {
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
if (last == NULL) {
temp->next = temp;
return temp;
}
temp->next = last->next;
last->next = temp;
return temp;
}
int search(struct Node* last, int key) {
if (last == NULL)
return 0;
struct Node* temp = last->next;
do {
if (temp->data == key)
return 1;
temp = temp->next;
} while (temp != last->next);
return 0;
}
int main() {
struct Node* last = NULL;
last = insert(last, 10);
last = insert(last, 20);
last = insert(last, 30);
int key;
printf("Enter element to search: ");
scanf("%d", &key);
if (search(last, key))
printf("Element found in circular linked list.\n");
else
printf("Element not found.\n");
return 0;
}
Output:
(3) Program Statement: Write a program to reverse the elements of a
doubly linked list.
(A)
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
void push(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->prev = NULL;
new_node->next = *head_ref;
if (*head_ref != NULL)
(*head_ref)->prev = new_node;
*head_ref = new_node;
}
void reverse(struct Node** head_ref)
{
struct Node* temp = NULL;
struct Node* current = *head_ref;
while (current != NULL) {
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
if (temp != NULL)
*head_ref = temp->prev;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
push(&head, 10);
push(&head, 20);
push(&head, 30);
push(&head, 40);
printf("Original list:\n");
printList(head);
reverse(&head);
printf("Reversed list:\n");
printList(head);
return 0;
}
Output:
[Link] Statement: Write a program to count the leaf nodes of a tree.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// Function to count leaf nodes
int countLeafNodes(struct Node* root) {
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return countLeafNodes(root->left) + countLeafNodes(root->right);
}
int main() {
// Example binary tree:
// 1
// /\
// 2 3
// /\
// 4 5
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
int leafCount = countLeafNodes(root);
printf("Number of leaf nodes: %d\n", leafCount);
return 0;
}
[Link] Statement: Write a program to find the parent of a node if
exists otherwise report NULL.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// Function to find and print parent of a given key
struct Node* findParent(struct Node* root, int key) {
if (root == NULL || (root->left == NULL && root->right == NULL)) {
return NULL;
}
if ((root->left && root->left->data == key) || (root->right && root->right-
>data == key)) {
return root;
}
struct Node* leftSearch = findParent(root->left, key);
if (leftSearch != NULL) return leftSearch;
return findParent(root->right, key);
}
int main() {
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
int key;
printf("Enter the node to find its parent: ");
scanf("%d", &key);
struct Node* parent = findParent(root, key);
if (parent != NULL)
printf("Parent of node %d is: %d\n", key, parent->data);
else
printf("Node %d has no parent or does not exist in the tree.\n", key);
return 0;
}
Output: