Elementary data structure.

-

 

What is abstract data types?

An abstract data type allows us to group native built-in data types into a compound type whose instances can be individually referenced.

The data contained in each instance and the operations on that data are independent of all other instances.

Abstract data types are the foundation for understanding and applying specific data types, native or user-defined.

They also form the foundation for structured and object-oriented programming. Ultimately, these lead to parallel and distributed processing.

 

What is array?

An array is a series of elements of the same serial abstract data type placed in contiguous memory.

An entire array is declared all at once.

Each individual element in the array can be referenced by indexing. Indexed means the array elements are numbered and always start at 0.

You can also declare an array in the following way :

 

#define ROLL_NUMBERS 51

int classv[ROLL_NUMBERS];

 

const int Emp_salary = 35

float Employee[Emp_salary];

 

Example: int A[10];

Declares 10 integers and can be accessed by the name A

Each variable is assigned a unique location (location is also called as an index). The range of the location is 0 to (length – 1). For the said array range of the location is 0 to 9.

See the following diagram which represent the array A[10] :

 

 

Index    0            1            2            3            4            5            6            7            8              9

Value    15          8            14          45          48          45          -57         45          1              0

 

 

Indexing into Arrays

To refer a single array element use arrayname[index].

 

For example :

 

A[4] contains the value 48

 

A[9] contains the value 0

 

What is a pointer?

A pointer is a memory address.

Pointers represent one of the more powerful features of the C language, but also one of the most feared.

The purpose of pointers is to allow you to manually, directly access a block of memory. Pointers are used a lot for strings and structs.

Declaring a pointer

Here is how to declare a pointer:

 

#include <stdio.h>

 

int main (int argc, char *argv[])

{

 int age = 30;

 int *p;

 p = &age;

 printf("age=%d\n", age);

 printf("p=%p\n", p);

 printf("*p=%d\n", *p);

 printf("sizeof(p)=%ld\n", sizeof(p));

 *p = 40;

 printf("*p=%d\n", *p);

 printf("age=%d\n", age);

 return 0;

}

age=30

p=0x7fff197ceb1c

*p=30

sizeof(p)=8

*p=40

age=40

On line 5 we declare an

 

int variable age and initialize it to 30. On line 6 we declare a variable p whose type is a pointer to an int. The star * syntax is how to declare the type as a pointer to a particular other type. Usually you need to declare pointers as pointing to a particular type, but the exception is a so-called void pointer, which is a pointer to an unknown type. Don't worry about void pointers for now.

 

So we have a pointer variable

 

p that is a pointer to an int. So far, it doesn't point anywhere… we have only declared that we want a space in memory to hold a pointer to an int. On line 7 is where we assign a value to our pointer p. We assign to p the address (the location) of the other variable age. So now at this point in the program, we have the following (which we can see in the output):

 

the value of age is the integer 30

the value of p is the address of the age variable

the integer that p points to has a value of 30

On line 2 of the output we see that the value of the p pointer is a long strange looking string of letters and numbers. This is in fact a hexidecimal (base 16) memory address.

 

What is dynamic memory?

The memory that an application obtains from the operating system during execution is called dynamic memory.

Dynamic memory is distinct from the static memory. While the operating system allocates static memory for an application at load time, the system reserves dynamic memory, allocates it and deallocates it at run-time.

 

What is Static Memory?

The memory that the operating system allocates for the application at load time is called static memory. Static memory includes the memory allocated for program instructions and program data. The compiler determines the amount of static memory that each translation unit requires. The linker determines the amount of static memory that the entire application requires.

 

Allocation

The keyword new without brackets allocates dynamic memory for a single variable or object. 

A dynamic allocation statement takes the form

pointer = new Type;

For example, to store one instance of a Student in dynamic memory, we write

 Student* harry = nullptr;   // a pointer in static memory

 harry = new Student;        // points to a Student in dynamic memory

 

 // we must deallocate harry later!






 

Deallocation

The keyword delete without brackets deallocates dynamic memory at the address specified. 

A dynamic deallocation statement takes the form

 delete pointer;

delete takes the address that was returned by the new operator.

For example, to deallocate the memory for harry, we write

 delete harry;
 harry = nullptr;  // good programming style

 

Introduction to Linked Lists

This section introduces the basic concept of lists and how lists are used as stacks and queues. Read this page to get an introduction to the concept of a node. A node is a component within a list of objects that are related in some way. Our particular concern is with lists, stacks, and queues. The article discusses nodes from that perspective.

What is Linked Stacks

The linked stack implementation is quite simple.  Elements are inserted and removed only from the head of the list. A header node is not used because no special-case code is required for lists of zero or one elements

What is Linked Queues

The linked queue implementation is a straightforward adaptation of the linked list. Methods front and rear are pointers to the front and rear queue elements, respectively. We will use a header link node, which allows for a simpler implementation of the enqueue operation by avoiding any special cases when the queue is empty.

What is "algorithm efficiency"?

When it comes time to put an algorithm to work or choose between competing algorithms, we need a way to measure and compare algorithms. There are many different things we could measure about an algorithm: the number of lines of code to express, how much time it take to program and debug, the amount of memory used while running, and time taken to run are all things we might care about.

What is hash table?

Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data.

Thus, it becomes a data structure in which insertion and search operations are very fast irrespective of the size of the data. Hash Table uses an array as a storage medium and uses hash technique to generate an index where an element is to be inserted or is to be located from.

Hashing

Hashing is a technique to convert a range of key values into a range of indexes of an array. We're going to use modulo operator to get a range of key values. Consider an example of hash table of size 20, and the following items are to be stored. Item are in the (key,value) format.

  • (1,20)
  • (2,70)
  • (42,80)
  • (4,25)
  • (12,44)
  • (14,32)
  • (17,11)
  • (13,78)
  • (37,98)

Sr.No.

Key

Hash

Array Index

1

1

1 % 20 = 1

1

2

2

2 % 20 = 2

2

3

42

42 % 20 = 2

2

4

4

4 % 20 = 4

4

5

12

12 % 20 = 12

12

6

14

14 % 20 = 14

14

7

17

17 % 20 = 17

17

8

13

13 % 20 = 13

13

9

37

37 % 20 = 17

17

Linear Probing

As we can see, it may happen that the hashing technique is used to create an already used index of the array. In such a case, we can search the next empty location in the array by looking into the next cell until we find an empty cell. This technique is called linear probing.

Sr.No.

Key

Hash

Array Index

After Linear Probing, Array Index

1

1

1 % 20 = 1

1

1

2

2

2 % 20 = 2

2

2

3

42

42 % 20 = 2

2

3

4

4

4 % 20 = 4

4

4

5

12

12 % 20 = 12

12

12

6

14

14 % 20 = 14

14

14

7

17

17 % 20 = 17

17

17

8

13

13 % 20 = 13

13

13

9

37

37 % 20 = 17

17

18

Following are the basic primary operations of a hash table.Basic operation

  • Search − Searches an element in a hash table.
  • Insert − inserts an element in a hash table.
  • delete − Deletes an element from a hash table.

What is graph?

Graphs provide the ultimate in data structure flexibility. Graphs can model both real-world systems and abstract problems, so they are used in hundreds of applications. Here is a small sampling of the range of problems that graphs are routinely applied to.

1. Modeling connectivity in computer and communications networks.

 2. Representing a map as a set of locations with distances between locations; used to compute shortest routes between locations.

 3. Modeling flow capacities in transportation networks. 4. Finding a path from a starting condition to a goal condition; for example, in artificial intelligence problem solving.

 5. Modeling computer algorithms, showing transitions from one program state to another. 6. Finding an acceptable order for finishing subtasks in a complex activity, such as constructing large buildings.

 7. Modeling relationships such as family trees, business or military organizations, and scientific taxonomies.

Whatis tree?

Tree represents the nodes connected by edges. We will discuss binary tree or binary search tree specifically.

Binary Tree is a special datastructure used for data storage purposes. A binary tree has a special condition that each node can have a maximum of two children. A binary tree has the benefits of both an ordered array and a linked list as search is as quick as in a sorted array and insertion or deletion operation are as fast as in linked list.

Important Terms

Following are the important terms with respect to tree.

·       Path − Path refers to the sequence of nodes along the edges of a tree.

·       Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.

·       Parent − Any node except the root node has one edge upward to a node called parent.

·       Child − The node below a given node connected by its edge downward is called its child node.

·       Leaf − The node which does not have any child node is called the leaf node.

·       Subtree − Subtree represents the descendants of a node.

·       Visiting − Visiting refers to checking the value of a node when control is on the node.

·       Traversing − Traversing means passing through nodes in a specific order.

·       Levels − Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.

·       keys − Key represents a value of a node based on which a search operation is to be carried out for a node.

Binary Search Tree Representation

Binary Search tree exhibits a special behavior. A node's left child must have a value less than its parent's value and the node's right child must have a value greater than its parent value.

We're going to implement tree using node object and connecting them through references.

Tree Node

The code to write a tree node would be similar to what is given below. It has a data part and references to its left and right child nodes.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

In a tree, all nodes share common construct.

BST Basic Operations

The basic operations that can be performed on a binary search tree data structure, are the following −

·       Insert − Inserts an element in a tree/create a tree.

·       Search − Searches an element in a tree.

·       Preorder Traversal − Traverses a tree in a pre-order manner.

·       Inorder Traversal − Traverses a tree in an in-order manner.

·       Postorder Traversal − Traverses a tree in a post-order manner.

We shall learn creating (inserting into) a tree structure and searching a data item in a tree in this chapter. We shall learn about tree traversing methods in the coming chapter.

Insert Operation

The very first insertion creates the tree. Afterwards, whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

Algorithm

If root is NULL 
   then create root node
return
 
If root exists then
   compare the data with node.data
   
   while until insertion position is located
 
      If data is greater than node.data
         goto right subtree
      else
         goto left subtree
 
   endwhile 
   
   insert data
       
end If     

Implementation

The implementation of insert function should look like this −

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;
 
   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;
 
   //if tree is empty, create root node
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent  = NULL;
 
      while(1) {                
         parent = current;
 
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }
                    
         //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

Search Operation

Whenever an element is to be searched, start searching from the root node, then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the same algorithm for each node.

Algorithm

If root.data is equal to search.data
   return root
else
   while data not found
 
      If data is greater than node.data
         goto right subtree
      else
         goto left subtree
         
      If data found
         return node
   endwhile 
   
   return data not found
   
end if     

The implementation of this algorithm should look like this.

struct node* search(int data) {
   struct node *current = root;
   printf("Visiting elements: ");
 
   while(current->data != data) {
      if(current != NULL)
      printf("%d ",current->data); 
      
      //go to left tree
 
      if(current->data > data) {
         current = current->leftChild;
      }
      //else go to right tree
      else {                
         current = current->rightChild;
      }
 
      //not found
      if(current == NULL) {
         return NULL;
      }
 
      return current;
   }  

}

Comments

Post a Comment