C99′ Extensions and Data Structures

Contents

**Describe features added in C89 to get C99** 1

**Describe features added in C99 to get C11** 2

**List and Explain Standard C Libraries** 3

**Write a Program to find Square root of a given number** 4

**Write a Program to find Array element in reverse order** 5

**Create a Binary Search Tree for the given elements** 7

**Describe Insertion and Deletion operations to be performed with BST** 10

**Define Complexities of Insertion into and Deletion from BST** 11

**Describe features added in C89 to get C99**

C99 (C programming language standard published in 1999) is the latest version of the C programming language standard and it added several new features to the language. Some of the most significant features added in C99 are:

- Flexible Array Members: In C99, it is possible to declare an array with a size that is not specified at the time of declaration. This type of array is called a flexible array member.
- Variables Declared in a For Loop: Variables declared in a for loop can be used only within the scope of that loop.
- Complex numbers: C99 introduced support for complex numbers, with new types float complex, double complex, and long double complex.
- Inline Functions: In C99, inline functions are a new feature which helps the programmer to specify that a function is to be inlined. This helps to reduce function call overhead and improve the performance of the program.
- Restricted Pointers: C99 introduced the concept of restricted pointers, which are pointers that the programmer guarantees not to alias. This can be used by the compiler to perform optimization.
- Intermingled Declarations and Code: In C99, it is possible to declare variables anywhere in the code, not just at the beginning of a block.
- Improved Support for Mathematics: C99 added several mathematical functions, such as fmin, fmax, nextafter, fdim, and remainder, that make it easier to perform mathematical operations.
- Improved Support for Dynamic Arrays: C99 introduced a new function aligned_alloc which helps to allocate aligned memory blocks.
- Improved Support for Boolean Types: C99 introduced a new type _Bool which can be used to represent a Boolean value.

These are just a few of the many new features added in C99. Overall, the new features in C99 aim to make the language easier to use, more powerful, and more flexible.

**Describe features added in C99 to get C11**

C11, also known as C1X, is the latest version of the C programming language standard. It was published in December 2011 as an update to the previous standard, C99. Some of the key features added in C11 are:

- _Bool type: A new data type, “_Bool”, was introduced to support Boolean values.
- Anonymous structures and unions: C11 allows the definition of structures and unions without giving them a name.
- Type-generic expressions: C11 provides type-generic expressions, which allow functions to be written that can operate on values of different data types.
- Alignof and _Alignas: The “alignof” operator gives the alignment requirement of a type, and “_Alignas” can be used to specify the alignment requirement for a struct or union.
- _Noreturn: The “_Noreturn” function specifier indicates that a function never returns to its caller.
- Static assertions: C11 introduced a new form of “assert” that can be used to perform compile-time checks.
- Multithreading: C11 added support for multithreading, including new functions for atomic operations and thread-local storage.
- Advanced features for complex numbers: C11 added new types and functions to support complex numbers.

These are some of the key features added in C11 to improve the functionality of the C programming language.

**List and Explain Standard C Libraries**

The Standard C Libraries are a collection of functions and macros that are defined in the C Standard Library. These libraries provide a set of standard functions and macros that are used in C programming. The following are some of the standard C Libraries:

- stdio.h: The stdio.h library is the most widely used library in C programming. It provides functions for performing input and output operations, such as printf() and scanf().
- stdlib.h: The stdlib.h library provides functions for performing general utility operations, such as memory allocation (malloc() and calloc()), random number generation (rand()), and string conversion functions (atoi(), itoa(), etc.).
- string.h: The string.h library provides functions for performing operations on strings, such as strlen(), strcpy(), strcat(), and strcmp().
- math.h: The math.h library provides functions for performing mathematical operations, such as sin(), cos(), tan(), log(), etc.
- time.h: The time.h library provides functions for manipulating dates and times, such as time(), localtime(), and mktime().
- ctype.h: The ctype.h library provides functions for testing and mapping characters, such as isalpha(), isdigit(), toupper(), and tolower().
- setjmp.h: The setjmp.h library provides functions for performing non-local jumps, such as setjmp() and longjmp().
- signal.h: The signal.h library provides functions for handling signals, such as signal() and raise().

These libraries provide a standard set of functions that can be used across different platforms and systems, making C programming more portable.

**Write a Program to find Square root of a given number**

To find the square root of a given number in C, you can use the sqrt() function from the math.h library. The sqrt() function takes a single argument, which is the number for which you want to find the square root, and returns the square root of that number.

Here’s an example program that calculates the square root of a given number:

#include <stdio.h>

#include <math.h>

int main()

{

double num, sqrt_num;

printf(“Enter a number: “);

scanf(“%lf”, &num);

sqrt_num = sqrt(num);

printf(“The square root of %lf is %lf\n”, num, sqrt_num);

return 0;

}

In this program, the sqrt() function is used to calculate the square root of the number entered by the user. The result is stored in the sqrt_num variable and printed to the screen.

**Write a Program to find Array element in reverse order **

Here’s an example of a program to find array elements in reverse order in C:

#include <stdio.h>

int main() {

int n, i;

printf(“Enter the size of the array: “);

scanf(“%d”, &n);

int a[n];

printf(“Enter the elements of the array: “);

for (i = 0; i < n; i++) {

scanf(“%d”, &a[i]); }

printf(“The elements of the array in reverse order: “);

for (i = n-1; i >= 0; i–) {

printf(“%d “, a[i]); }

return 0;

}

In this program, the size of the array is first entered by the user. Then, the elements of the array are entered. Finally, the elements of the array are printed in reverse order using a for loop that starts from the last index of the array (n-1) and decrements by 1 in each iteration. ** **

**Define Binary Search Tree**

A binary search tree (BST) is a type of binary tree data structure that follows a specific property called the binary search property. In a binary search tree, each node has a key, and the keys of all nodes in the left subtree are less than the key of the current node, while the keys of all nodes in the right subtree are greater than the key of the current node.

Here are the key characteristics of a binary search tree:

- Binary Tree Structure: A binary search tree is a binary tree where each node has at most two children: a left child and a right child. The left child represents values less than the current node’s key, while the right child represents values greater than the current node’s key.
- Binary Search Property: For any node in the binary search tree, all nodes in its left subtree have keys less than its own key, and all nodes in its right subtree have keys greater than its own key. This property allows for efficient searching, insertion, and deletion of elements.
- Unique Keys: Each node in the binary search tree has a unique key. No two nodes in the tree have the same key.
- Recursive Structure: The binary search tree follows a recursive structure, where each subtree is itself a binary search tree. This recursive property allows for efficient traversal and manipulation of the tree.

The binary search tree data structure is widely used in computer science and has various applications, including efficient searching, sorting, and dynamic data storage.

Here is an example of a binary search tree:

8

/ \

3 10

/ \ \

1 6 14

/ \ /

4 7 13

In this example, the binary search tree follows the binary search property, where each node’s value is greater than all the values in its left subtree and less than all the values in its right subtree.

Binary search trees are important data structures due to their efficient search time complexity of O(log n) on average, where n is the number of nodes in the tree.

**Create a Binary Search Tree for the given elements **

To create a Binary Search Tree (BST) for a given set of elements in C, you need to follow these steps:

- Define a structure for the BST node: The structure should have a data member to store the value of the node, and two pointers for the left and right children.

struct Node

{

int data;

struct Node *left, *right;

};

- Create a new node function: This function will allocate memory for a new node and return the address of the newly created node.

struct Node* newNode(int data)

{

struct Node* node = (struct Node*)malloc(sizeof(struct Node));

node->data = data;

node->left = node->right = NULL;

return node;

}

- Insert a new node: This function will take a node and insert the new node in the BST such that the left child of a node is smaller than the parent node and the right child of a node is greater than the parent node.

struct Node* insert(struct Node* node, int data)

{

if (node == NULL) return newNode(data);

if (data < node->data)

node->left = insert(node->left, data);

else if (data > node->data)

node->right = insert(node->right, data);

return node;

}

- Finally, you can create a BST by calling the insert function for each element in the given set of elements.

int main()

{

struct Node *root = NULL;

root = insert(root, 50);

insert(root, 30);

insert(root, 20);

insert(root, 40);

insert(root, 70);

insert(root, 60);

insert(root, 80);

return 0;

}

This is just a basic example of creating a BST. You can also implement other BST operations such as searching, deleting, and traversing a node.

Let’s create a binary search tree for the following elements: 7, 4, 9, 2, 5, 8, 11, 3, and 6.

7

/ \

4 9

/ \ \

2 5 11

\ \

3 6

\

8

In this binary search tree, each node’s value is greater than all the values in its left subtree and less than all the values in its right subtree. The tree is balanced and follows the binary search property, making it efficient for searching, insertion, and deletion operations.

**Describe Insertion and Deletion operations to be performed with BST **

Insertion and deletion are fundamental operations performed on a binary search tree (BST). Let’s discuss how these operations are performed:

- Insertion Operation:
- To insert a new element into a BST, we follow these steps:
- Start at the root node.
- Compare the value of the new element with the value of the current node.
- If the new element is smaller, move to the left child of the current node.
- If the new element is greater, move to the right child of the current node.
- Repeat the process until we reach an empty spot (a leaf node) where the new element can be inserted.
- Create a new node with the new element and insert it at the appropriate position.

- Insertion preserves the binary search property of the tree. After insertion, the new element will be placed as a leaf node in the appropriate position to maintain the order of the BST.

- To insert a new element into a BST, we follow these steps:
- Deletion Operation:
- To delete an element from a BST, we follow these steps:
- Start at the root node and search for the node containing the element to be deleted.
- If the node is found, there are three cases to consider:
- Node has no children (leaf node): Simply remove the node from the tree.
- Node has one child: Replace the node with its child.
- Node has two children: Find either the maximum element in the left subtree (its predecessor) or the minimum element in the right subtree (its successor). Replace the node’s value with the predecessor/successor value and then recursively delete the predecessor/successor node from the appropriate subtree.

- Deletion may affect the binary search property of the tree. After deletion, the tree needs to be rearranged to maintain the order and balance of the BST. This can involve replacing nodes, rotating subtrees, or rebalancing the tree.

- To delete an element from a BST, we follow these steps:

It is important to note that the process of insertion and deletion in a BST ensures that the tree remains a valid BST, preserving the order and balance properties. These operations have time complexities of O(log n) on average, where n is the number of nodes in the tree. However, in the worst case (unbalanced tree), the time complexity can be O(n).

**Define Complexities of Insertion into and Deletion from BST **

The complexities of insertion and deletion operations in a binary search tree (BST) can vary depending on the structure of the tree. Let’s discuss the average and worst-case complexities for both operations:

- Insertion Complexity:
- Average Case: O(log n)
- In an average case scenario, where the BST is balanced, the complexity of insertion is logarithmic with respect to the number of nodes in the tree.
- This is because during insertion, we traverse the tree from the root to a leaf node, comparing the values and deciding whether to go left or right.
- As the tree is balanced, the height of the tree is logarithmic in relation to the number of nodes, resulting in an average complexity of O(log n).

- Worst Case: O(n)
- In the worst-case scenario, where the BST is highly unbalanced, the complexity of insertion can become linear.
- If the elements are inserted in a sorted or nearly sorted order, the tree can degenerate into a linked list with a height of n, resulting in a worst-case time complexity of O(n).
- This occurs when all new elements are greater or smaller than the existing elements, causing the tree to grow in one direction.

- Average Case: O(log n)
- Deletion Complexity:
- Average Case: O(log n)
- Similar to insertion, the average case complexity of deletion in a balanced BST is logarithmic, as we traverse the tree to find the node to be deleted.
- After deletion, the tree may need to be rearranged or rebalanced to maintain the binary search property.
- The complexity of these reorganization steps depends on the specific balancing technique employed (e.g., AVL tree, Red-Black tree).

- Worst Case: O(n)
- In the worst-case scenario, where the tree is highly unbalanced and degenerates into a linked list, the complexity of deletion can become linear.
- This occurs when the element to be deleted is at the bottom of the tree, requiring traversing the entire height of the tree to find and delete the node.
- The worst-case complexity of O(n) occurs when every node in the tree needs to be examined during the deletion process.

- Average Case: O(log n)

It’s important to note that maintaining the balance of the BST is crucial for achieving optimal time complexities. Various self-balancing techniques, such as AVL trees or Red-Black trees, can be used to ensure logarithmic time complexities for both insertion and deletion operations, even in worst-case scenarios.