Structs in the C language

Why can't we have a situation as in the following:

  1. struct Node{
  2. int data;
  3. Node link;
  4. };

Memory allocation of objects of type Node will require infinite memory because of the nested definition. But the same problem will not exist if a link field inside the struct is a Node* (a pointer to a Node, not a Node). Hence the following is allowed.

  1. struct Node{
  2. int data;
  3. Node* link;
  4. };

This forms the basis of data structures allocated on the heap (linked list and Binary trees).

Programs covered

The following is a function that traverses a linked list in a forward direction:

  1. void printList(Node* head)
  2. {
  3. while(head->link != NULL)
  4. {
  5. printf("%d", head->data);
  6. head = head->link;
  7. }
  8. }

The following is a recursive version of the preceding code:

  1. void printList(Node* head)
  2. {
  3. if(head == NULL){ return ; }
  5. printf("%d", head->data);
  7. printList(head->link);
  8. }

We said that a recursive function takes more time and more memory than the non-recursive counterpart and hence is never recommended. But in some cases (like implementing a Binary Tree and Graph algorithms) it is very convenient to write recursive algorithms because the problem can be visualized in terms of sub-problems.

For example, consider the problem of printing the list in reverse order. The recursive code is very easy, we just need to change the function from tail recursion to head recursion:

  1. void printList(Node* head)
  2. {
  3. if(head == NULL){ return ; }
  5. printList(head->link);
  7. printf("%d", head->data);
  8. }

But if we want to write a non-recursive function for it then it will be a challenge.

Question: write a non-recursive function that will print the list in reverse order (last node to first node).

Searching in an Array

Given an Array of numbers a0, a1, a2, …. an and a number x. Write a function that will return i, such that:

  1. ai == x

If x is not in the Array, then return -1 (which means “Not Found”).

Signature of the function

  1. int search(int *arr, int n, int x);

Linear Search

Linear Search Facts

Binary Search Algorithm

Code
  1. /** Non-Recursive Function */
  3. int bSearch(int * arr, int n, int data){
  4. int l=0, h=n-1, m;
  6. while(l <= h){
  7. m = (l + h) / 2;
  9. if(arr[m] == data)
  10. return m; // FOUND.
  11. else if(arr[m] < data)
  12. l = m + 1;
  13. else
  14. h = m – 1;
  15. }
  16. return -1; // NOT FOUND
  17. }
  19. /** Recursive Function */
  21. int bSearch(int * arr, int l , int h, int data){
  23. if(l > h || arr[l] > data || arr[h] < data)
  24. return -1; // NOT FOUND.
  25. else
  26. {
  27. int m = (l+h)/2;
  29. if(arr[m] == data)
  30. return m; // FOUND.
  31. else if (arr[m]<data)
  32. return bSearch(arr, m+1, h, data)
  33. else
  34. return bSearch(arr, l, m-1, data);
  35. }
  36. }
Time Complexity

Space Complexity

Questions Discussed

Q1. A sorted array is rotated around a pivot. For example:

Write code to find the pivot position of the rotation of the array (above: 2).

Q2. Write a function to search in a pivoted array (the pivot is given).

Q3. Given an array of numbers and a number x, write a function to search for two elements in the array, whose sum is x.

Q4. Given an array of integers where each number is repeated an even number of times except for one integer that is repeating an odd number of times. Find that number.

Q5. Given an array of integers of size N-1 where all the integers are unique and are in the range of 1 to N. One integer is missing, write the code to find the missing integer.

Assignment Questions

  1. Write code to search in a matrix sorted by row and by column.

  2. Write code to search for an element in a Binary Search Tree.