Welcome to Edukum.com

# Introduction to Data Structures

Data Structures

• The way of storing and organizing data items and establishing their relationship is called data structure.
• It is the building block of every program.
• Data structures along with algorithm combined forms a program.
• It mainly specifies organizing data, accessing data, maintaining relationships among data, and processing data for information.

• ADT is a data type whose actual implementation is hidden and no concern to the implementation code.
• A string data type is an abstract form of an array of characters.
• A programmer does not worry about the internal implementation technique for using ADTs, rather they just make use of them.

Array
An array is a series of elements of the same type placed in contiguous memory locations that can be individually referenced by adding an index to a unique identifier (Arrays - C++ Tutorials, n.d.). Instead of declaring individual variables, such as number0, number1, ..., and number99, you declare one array variable such as numbers and use numbers[0], numbers[1], and ..., numbers[99] to represent individual variables. A specific element in an array is accessed by an index (C++ Arrays, n.d.). All arrays comprise of contiguous memory locations. The least address corresponds to the first element and the most elevated address to the last element.

Consider an array A of data type T having n elements, then we can perform the following operations.
CREATE (A): Create an array A.
INSERT (A, x): Insert an element x to array A.
DELETE (A, x): Delete element x from array A.
MODIFY (A, x, y): Modify the element x by element y in array A.
TRAVERSE (A): Access all the elements of array A.
Merge (A, B): Merge two arrays A and B to the third array.

Since we can perform all the above operations in a one-dimensional array, we can consider the array as an ADT.

One Dimensional Array
One dimensional array, also known as a single dimensional array is the array that stores and represents data in a linear form. The declaration form of one-dimensional array is
Data_type array_name [size];

For example:
int numbers [5];
numbers [0] = 1; // set first element
numbers [4] = 5; // set last element

The following code declares an array called "numbers" to hold 5 integers and sets the first and last elements. C arrays are constantly indexed from 0. So the primary integer in "numbers" array is numbers[0] and the last is numbers[4]. This array can be used when we have many numbers of data of the same data type and has only one dimension.

Two-Dimensional Array
2D arrays are generally known as matrix. 2D arrays are written in two subscripts in which the first subscript indicates the number of rows and the second subscript indicates the number of columns.

Initialization: int disp[2][4] = { 10, 11, 12, 13, 14, 15, 16, 17};

When we give values during one dimensional array declaration, we don’t need to mention dimension. But that’s not the case with 2D array; we must specify the second dimension even if we are giving values during the declaration (Singh, 2014).

/* Valid declaration*/
int abc[2][2] = {1, 2, 3 ,4 }
/* Valid declaration*/
int abc[][2] = {1, 2, 3 ,4 }
/* Invalid declaration – you must specify second dimension*/
int abc[][] = {1, 2, 3 ,4 }
/* Invalid because of the same reason mentioned above*/
int abc[2][] = {1, 2, 3 ,4 }

Multi-dimensional Array
The array having more than one dimension is called multi-dimensional array. Two-dimensional array is also a multi-dimensional array. We can create multi-dimensional array of any size as desired.

Initialization: data_type name[size1][size2]...[sizeN];

Although we can use many dimensions, normally we use one-dimension or two-dimension arrays and three-dimension arrays are rarely used.

Structure
A structure is a collection of more than one data, possibly of different data types in a common name. Every structure member may have their own data type, so this is considered as a collection of heterogeneous data. Structures are usually useful whenever a ton of data needs to be assembled together, for instance, they can be utilized to hold records from a database or to store information about contacts in an address book.

Structure definition:

struct [structure tag] {
member definition;
member definition;
...
member definition;
};
Structure variable is declared as:
Struct [structure tag] variable_name;
Structure members are accessed using the variable name followed by a dot. When structure member is accessed through structure pointer variable, then we use an arrow(->) instead of a dot.
An example program is given below:
struct database {
int id_number;
int age;
float salary;
};
int main()
{
struct database employee; /* There is now an employee variable that has variables that can be modified inside it.*/
employee.age = 22;
employee.id_number = 1;
employee.salary = 12000.21;
}

Union

Union is a collection of different data members possibly of a different data type in a single name. Structurally, union and structure are same. Structure allocates memory required for the sum of all the members whereas union variable allocates memory required for the biggest member. We can define a union with many members, but only one member can contain a value at any given time. Unions provide an efficient way of using the same memory location for multiple-purpose (Unions in C, n.d.). All members of a structure can be accessed at any time. However, one and only one member of a union can be accessed at once and other members will contain garbage value.

Union definition:

union [union tag] {
member definition;
member definition;
...
member definition;
};
An example of union program is given below:
#include
#include
union Data {
int i;
float f;
char str[20];
};
int main( ) {
union Data data;
data.i = 10;
printf( "data.i : %d\n", data.i);
data.f = 220.5;
printf( "data.f : %f\n", data.f);
strcpy( data.str, "C Programming");
printf( "data.str : %s\n", data.str);
return 0;
}

Classes in C++

Classes are an expanded concept of data structures: like data structures, they can contain data members, but they can also contain functions as members. An object is an instantiation of a class. In terms of variables, a class would be the type, and an object would be variable (Classes (I) - C++ Tutorials, n.d.).

Class definition:

class class_name {
access_specifier_1:
member1;
access_specifier_2:
member2;
...
};

Classes have the same format as plain data structures, aside from the fact that they can incorporate functions and have access specifiers. An access specifier is one of the following: private, public or protected. The public restriction permits any part of the program, including parts outside the class, to access the functions and variables determined as public. The protected restriction avoids functions outside the class to access the variable but is accessible from the members of their derived class. The private members of a class are accessible only from within other members of the same class.

An example is given below:

// classes example
#include
using namespace std;
class Rectangle {
int width, height;
public:
void set_values (int,int);
int area() {return width*height;}
};
void Rectangle::set_values (int x, int y) {
width = x;
height = y;
}
int main () {
Rectangle rect;
rect.set_values (3,4);
cout << "area: " << rect.area();
return 0;
}

References