Q
Data Structures | Assignments
Home » Embedded Systems » Data Structures | Course Home » Data Structures | Assignments

Data Structures – Assignments

In Emertxe each one of our Assignments will ensure you apply the concept you have leant in your classroom. By solving these assignments, you will go through a systematic problem-solving approach which include requirement understanding, algorithm design, pseudocode creation, dry run and final execution. As you move from simple to more complex assignments of each module it will slowly start building your self-confidence

Title Insert After
Filename sl_insert_after.c
Description Write a function to insert the new data after the given data.
Cases
  1. List Empty
  2. List Non-Empty
    1. Given data present
    2. Given data not present
Case-1 List Empty
Input Head = NULL
Output return LIST_EMPTY
Case-2
Sub-case:1
List Non-Empty
Given data present
Case-2
Sub-case:2
List Non-Empty
Given data not present
Example If given_data = 40, new_data = 45 Example If given_data = 60, new_data = 45
Input 10 -> 20 -> 30 -> 40 -> 50 Input 10 -> 20 -> 30 -> 40 -> 50
Output 10 -> 20 -> 30 -> 40 -> 45 -> 50 Output Return DATA_NOT_FOUND
Prototype int sl_insert_after(Slist *head, data_t g_data, data_t n_data);

 

head : Pointer to the first node
g_data : Given data
n_data : New data to be inserted into the list
return value : status (LIST_EMPTY, SUCCESS, DATA_NOT_FOUND)
Title Insert Before
Filename sl_insert_before.c
Description Write a function to insert the new data before the given data.
Cases
  1. List Empty
  2. List Non-Empty
    1. Given data present
    2. Given data not present
Case-1 List Empty
Input Head = NULL
Output return LIST_EMPTY
Case-2
Sub-case:1
List Non-Empty
Given data present
Case-2
Sub-case:2
List Non-Empty
Given data not present
Example If given_data = 40, new_data = 45 Example If given_data = 60, new_data = 45
Input 10 -> 20 -> 30 -> 40 -> 50 Input 10 -> 20 -> 30 -> 40 -> 50
Output 10 -> 20 -> 30 -> 45 -> 40 -> 50 Output Return DATA_NOT_FOUND
Case-3 Data found in the first
Example If given_data = 10, new_data = 45
Input 10 -> 20 -> 30 -> 40 -> 50
Output 45 -> 10 -> 20 -> 30 -> 40 -> 50
Prototype

int sl_insert_after(Slist **head, data_t g_data, data_t n_data);

 

head : Pointer to the first node
g_data : Given data
n_data : New data to be inserted into the list
return value : status (LIST_EMPTY, SUCCESS, DATA_NOT_FOUND)
Title Delete element
Filename sl_delete_element.c
Description Write a function to delete the given data in the single linked list.
Cases
  1. List Empty
  2. List Non-Empty
    1. Given data present
    2. Given data not present
Case-1 List Empty
Input Head = NULL
Output return LIST_EMPTY
Case-2
Sub-case:1
List Non-Empty
Given data present
Case-2
Sub-case:2
List Non-Empty
Given data not present
Example If given_data = 40 Example If given_data = 60
Input 10 -> 20 -> 30 -> 40 -> 50 Input 10 -> 20 -> 30 -> 40 -> 50
Output 10 -> 20 -> 30 -> 50 Output Return DATA_NOT_FOUND
Prototype

int sl_insert_after(Slist **head, data_t g_data);

 

head : Pointer to the first node
g_data : Given data
return value : status (LIST_EMPTY, SUCCESS, DATA_NOT_FOUND)
Title Insert at ‘n’ position
Filename sl_insert_nth.c
Description Write a function to insert the given data exactly at the ‘n’ position in the single linked list.
Cases
  1. List Empty
  2. List Non-Empty
    1. Given ‘n’th position present
    2. Given ‘n’th position not present
Case-1 List Empty
Input Head = NULL
Output return LIST_EMPTY
Case-2
Sub-case:1
List Non-Empty
Given data present
Case-2
Sub-case:2
List Non-Empty
Given data not present
Example If n = 3, n_data = 23 Example If n = 10, n_data = 23
Input 10 -> 20 -> 30 -> 40 -> 50 Input 10 -> 20 -> 30 -> 40 -> 50
Output 10 -> 20 -> 23 -> 30 -> 50 Output Return POSITION_NOT_FOUND
Prototype

int sl_insert_after(Slist **head, int n, data_t n_data);

 

head : Pointer to the first node
n : Position number
n_data : New data, to be inserted into the list
return value : status (LIST_EMPTY, SUCCESS, POSITION_NOT_FOUND)
Title Find Mid
Filename sl_find_mid.c
Description Write a function to find the mid node in the given linked list.
Cases
  1. List Empty
  2. List Non-Empty
Case-1 List Empty
Input Head = NULL
Output return LIST_EMPTY
Case-2
Sub-case:1
List Non-Empty
List contains Odd nodes
Case-2
Sub-case:2
List Non-Empty
List contains Even nodes
Input 10 -> 20 -> 30 -> 40 -> 50 Input 10 -> 20 -> 40 -> 50
Output 30 Output 20
Prototype

int sl_find_mid(Slist *head, Slist **mid);

 

head : Pointer to the first node
mid : Pointer to the mid node
return value : status (LIST_EMPTY, SUCCESS)
Note Traverse the linked list only once

 

Title Get nth node from last
Filename sl_get_nth_from_last.c
Description Write a function to get the nth node from the end of the linked list.
Cases
  1. List Empty
  2. List Non-Empty
Case-1 List Empty
Input Head = NULL
Output return LIST_EMPTY
Case-2 List Non-Empty
Input 10 -> 20 -> 30 -> 40 -> 50, n = 2
Output 40 (From the last, second node conatins the data 40)
Prototype

int sl_get_nth_from_last(Slist *head, int n);

 

head : Pointer to the first node
g_data : Given data
n : Position from the last node
return value : status (LIST_EMPTY, SUCCESS)
Title Insert Sorted
Filename sl_insert_sorted.c
Description Write a function to insert the new data in the already sorted linked list
Cases
  1. List Empty
  2. List Non-Empty
Case-1 List Empty
Input Head = NULL
Output return LIST_EMPTY
Case-2 List Non-Empty
Example If n_data = 45
Input 10 -> 20 -> 30 -> 40 -> 50
Output 10 -> 20 -> 30 -> 40 -> 45 -> 50
Prototype

int sl_insert_after(Slist **head, data_t n_data);

 

head : Pointer to the first node
n_data : New data to be inserted into the sorted list
return value : status (LIST_EMPTY, SUCCESS)
Title Find loop
Filename sl_find_loop.c
Description Write a function to detect whether the given linked list is ending with loop or not
Cases
  1. List Empty
  2. List Non-Empty
Case-1 List Empty
Input Head = NULL
Output return LIST_EMPTY
Case-2
Sub-Case:1
List Non-Empty
Input input_1-5980314
Output Loop detected.
Case-2
Sub-Case:2
List Non-Empty
Input input_2-2544772
Output Loop not detected.
Prototype

int sl_insert_after(Slist *head);

 

head : Pointer to the first node
return value : status (LIST_EMPTY, LOOP_DETECTED, LOOP_NOT_DETECTED)
Note Traverse the linked list only once
Title Sort
Filename sl_sort.c
Description Write a function to sort the given single linked list.
Cases
  1. List Empty
  2. List Non-Empty
Case-1 List Empty
Input Head = NULL
Output return LIST_EMPTY
Case-2 List Non-Empty
Input 50 -> 40 -> 30 -> 20 -> 10
Output 10 -> 20 -> 30 -> 40 -> 50
Prototype

int sl_sort(Slist **head);

 

head : Pointer to the first node
return value : status (LIST_EMPTY, SUCCESS)
Note Don’t swap the data present in the nodes, swap the nodes itself.

 

Title Reverse
Filename sl_reverse_iterative.c
sl_reverse_recursive.c
Description Write a function to reverse the single linked list in both iterative and recursive methods
Cases
  1. List Empty
  2. List Non-Empty
Case-1 List Empty
Input Head = NULL
Output return LIST_EMPTY
Case-2 List Non-Empty
Input 50 -> 40 -> 30 -> 20 -> 10
Output 10 -> 20 -> 30 -> 40 -> 50
Prototype

int sl_sort(Slist **head);

 

head : Pointer to the first node
return value : status (LIST_EMPTY, SUCCESS)
Title Reverse
Filename sl_reverse_iterative.c
sl_reverse_recursive.c
Description Write a function to reverse the single linked list in both iterative and recursive methods
Cases
  1. List Empty
  2. List Non-Empty
Case-1 List Empty
Input Head = NULL
Output return LIST_EMPTY
Case-2 List Non-Empty
Input 50 -> 40 -> 30 -> 20 -> 10
Output 10 -> 20 -> 30 -> 40 -> 50
Prototype

int sl_sort(Slist **head);

 

head : Pointer to the first node
return value : status (LIST_EMPTY, SUCCESS)
Title Remove Duplicates
Filename sl_remove_duplicates.c
Description Write a function to remove the duplicates data present in the single linked list
Cases
  1. List Empty
  2. List Non-Empty
Case-1 List Empty
Input Head = NULL
Output return LIST_EMPTY
Case-2 List Non-Empty
Input 5 -> 3 -> 4 -> 5 -> 2 -> 1 -> 4 -> 5 -> 3
Output 5 -> 3 -> 4 -> 2 -> 1
Prototype

int sl_sort(Slist **head);

 

head : Pointer to the first node
return value : status (LIST_EMPTY, SUCCESS)
Title Sorted Merge
Filename sl_sorted_merge.c
Description Write a function to merge two linked list into one
Cases
  1. List Empty
  2. List Non-Empty
Case-1 List Empty
Input Head = NULL
Output return LIST_EMPTY
Case-2 List Non-Empty
Input List – 1
30 -> 10 -> 50
List – 2
20 -> 5 -> 35
Output 5 -> 10 -> 20 -> 30 -> 35 -> 50
Prototype

int sl_sort(Slist **head1, Slist **head2);

 

head1 : Pointer to the first node of the first linked list
head2 : Pointer to the first node of the second linked list
return value : status (LISTS_EMPTY, SUCCESS)
Note

 

  1. If lists are not sorted, sort it
  2. If second list is EMPTY, no need to append it.
  3. If first list is EMPTY, update head1 to the head2
  4. If both list are EMPTY, return LISTS_EMPTY

 

Title Insert After
Filename dl_insert_after.c
Description Write a function to insert the new data after the given data.
Cases
  1. List Empty
  2. List Non-Empty
    1. Given data present
    2. Given data not present
Case-1 List Empty
Input Head = NULL
Output return LIST_EMPTY
Case-2
Sub-case:1
List Non-Empty
Given data present
Case-2
Sub-case:2
List Non-Empty
Given data not present
Example If given_data = 40, new_data = 45 Example If given_data = 60, new_data = 45
Input 10 -> 20 -> 30 -> 40 -> 50 Input 10 -> 20 -> 30 -> 40 -> 50
Output 10 -> 20 -> 30 -> 40 -> 45 -> 50 Output Return DATA_NOT_FOUND
Prototype

int dl_insert_after(Dlist *head, data_t g_data, data_t n_data);

 

head : Pointer to the first node
g_data : Given data
n_data : New data to be inserted into the list
return value : status (LIST_EMPTY, SUCCESS, DATA_NOT_FOUND)
Title Insert Before
Filename dl_insert_before.c
Description Write a function to insert the new data before the given data.
Cases
  1. List Empty
  2. List Non-Empty
    1. Given data present
    2. Given data not present
Case-1 List Empty
Input Head = NULL
Output return LIST_EMPTY
Case-2
Sub-case:1
List Non-Empty
Given data present
Case-2
Sub-case:2
List Non-Empty
Given data not present
Example If given_data = 40, new_data = 45 Example If given_data = 60, new_data = 45
Input 10 -> 20 -> 30 -> 40 -> 50 Input 10 -> 20 -> 30 -> 40 -> 50
Output 10 -> 20 -> 30 -> 45 -> 40 -> 50 Output Return DATA_NOT_FOUND
Case-3 Data found in the first
Example If given_data = 10, new_data = 45
Input 10 -> 20 -> 30 -> 40 -> 50
Output 45 -> 10 -> 20 -> 30 -> 40 -> 50
Prototype

int sl_insert_after(Dlist **head, data_t g_data, data_t n_data);

 

head : Pointer to the first node
g_data : Given data
n_data : New data to be inserted into the list
return value : status (LIST_EMPTY, SUCCESS, DATA_NOT_FOUND)
Title Delete element
Filename dl_delete_element.c
Description Write a function to delete the given data in the double linked list.
Cases
  1. List Empty
  2. List Non-Empty
    1. Given data present
    2. Given data not present
Case-1 List Empty
Input Head = NULL
Output return LIST_EMPTY
Case-2
Sub-case:1
List Non-Empty
Given data present
Case-2
Sub-case:2
List Non-Empty
Given data not present
Example If given_data = 40 Example If given_data = 60
Input 10 -> 20 -> 30 -> 40 -> 50 Input 10 -> 20 -> 30 -> 40 -> 50
Output 10 -> 20 -> 30 -> 50 Output Return DATA_NOT_FOUND
Prototype

int sl_insert_after(Dlist **head, data_t g_data);

 

head : Pointer to the first node
g_data : Given data
return value : status (LIST_EMPTY, SUCCESS, DATA_NOT_FOUND)
Title Infix to Postfix
Filename infix_postfix.c
Description Write a function to convert the given infix expression into the postfix form
Cases
  1. Single digit numbers
  2. Multiple digit numbers
Case-1 Single digit numbers
Input 2 * 3 – 3 + 8 / 4 / (1 + 1)
Output 2 3 * 3 – 8 4 / 1 1 + / +
Case-2 Multiple digit numbers
Input 2 * 30 – 3 + 8 / 4 / (10 + 1)
Output 2, 30, *, 3, –, 8, 4, /, 10, 1, +, / ,+
Sample Prototype

Char * infix_postfix(char *infix);

 

infix : Pointer the base address of the infix array
return : Pointer the base address of the postfix array
Title Postfix Evaluation
Filename postfix_eval.c
Description Write a function to evaluate the postfix expression.
Cases
  1. Single digit numbers
  2. Multiple digit numbers
Case-1 Single digit numbers
Input 2 3 * 3 – 8 4 / 1 1 + / +
Output 4
Case-2 Multiple digit numbers
Input 2, 30, *, 3, –, 8, 4, /, 10, 1, +, / ,+
Output 57.181
Sample Prototype

double infix_postfix(char *postfix);

 

Postfix : Pointer the base address of the postfix array
return : Result of the expression in double.
Title Infix to Prefix
Filename infix_prefix.c
Description Write a function to convert the given infix expression into the prefix form
Cases
  1. Single digit numbers
  2. Multiple digit numbers
Case-1 Single digit numbers
Input 2 * 3 – 3 + 8 / 4 / (1 + 1)
Output + – * 2 3 3 / / 8 4 + 1 1
Case-2 Multiple digit numbers
Input 2 * 30 – 3 + 8 / 4 / (10 + 1)
Output +, -, *, 2, 30, 3, /, /, 8, 4, +, 10, 1
Sample Prototype

Char * infix_prefix(char *infix);

 

infix : Pointer the base address of the infix array
return : Pointer the base address of the prefix array
Title Prefix Evaluation
Filename prefix_eval.c
Description Write a function to evaluate the prefix expression.
Cases
  1. Single digit numbers
  2. Multiple digit numbers
Case-1 Single digit numbers
Input + – * 2 3 3 / / 8 4 + 1 1
Output 4
Case-2 Multiple digit numbers
Input +, -, *, 2, 30, 3, /, /, 8, 4, +, 10, 1
Output 57.181
Sample Prototype

double infix_postfix(char *prefix);

 

Prefix : Pointer the base address of the prefix array
return : Result of the expression in double.
Title Bubble Sort
Filename bubble.c
Description Write a function to sort given array using bubble sort
Input 5 4 3 2 1
Output 1 2 3 4 5
Sample Prototype

void bubble_sort(int *ptr)

 

ptr : Base address of the integer array
return : void
Title Insertion Sort
Filename insertion.c
Description Write a function to sort given array using insertion sort
Input 5 4 3 2 1
Output 1 2 3 4 5
Sample Prototype

void insertion_sort(int *ptr)

 

ptr : Base address of the integer array
return : void
Title Selection Sort
Filename selection.c
Description Write a function to sort given array using selection sort
Input 5 4 3 2 1
Output 1 2 3 4 5
Sample Prototype

void selection_sort(int *ptr)

 

ptr : Base address of the integer array
return : void
Title Delete nodes
Filename bst_delete_node.c
Description Write a function to delete the given data from the bst
Cases

Node to be deleted may be,

 

  1. Leaf node
  2. Node with single child
  3. Node with two children
Case-1 Leaf node
Input delete_node_case1_input-3555710
Output delete_node_case1_output-5042187
Case-2 Node with single child
Input delete_node_case2_input-9343420
Output After deleting 30
delete_node_case2_output-8632659
Case-3 Node with two children
Input delete_node_case3_input-1832823
Output After deleting 50
delete_node_case3_output-5858430
Title Find height
Filename bst_find_height.c
Description Write a function to find the height of the given tree
Cases
  1. Tree Empty
  2. Tree Non-Empty
Case-1 Tree Non-Empty
Input find_height_input-2355570
Output Height = 2
Title Find height
Filename bst_find_height.c
Description Write a function to find the height of the given tree
Cases
  1. Tree Empty
  2. Tree Non-Empty
Case-1 Tree Non-Empty
Input find_height_input-2355570
Output Height = 2
Title Create hash table
Filename create_hash_table.c
Description Write a function to create the hash table
Input Size
Output Hash table with the given size
Title Hash table search
Filename hash_search.c
Description Write a function to search the data in the hash table
Input Hash Table
Output Address of the node where data is found in the hash table
Title Hash table insert
Filename hash_insert.c
Description Write a function to insert the data in the hash table
Input Hash Table
Output Status [SUCCESS / FAILURE]
Title Hash delete element
Filename hash_delete_element.c
Description Write a function to delete the given item from the hash table
Input Hash Table
Output Status [SUCCESS / FAILURE]
Title Hash Table delete
Filename hash_table_delete.c
Description Write a function to delete the entire hash table
Input Hash Table
Output Status [SUCCESS / FAILURE]
Q