1 Introduction to Data Structures – Introduction to Data Structures in C

Chapter 1

Introduction to Data Structures

Chapter Outline

1.1 INTRODUCTION

Humans use different languages to communicate data and information with each other. Besides, thoughts and feelings can also be communicated to others using language. The newspaper, television and other media use different languages for communication of data / information. In all occupations, language plays a vital role. In fact, with the help of languages humans interact with each other.

Data is represented in the form of text or numbers or in the form of figures, tables, graphs, pictures, etc. The data can be stored in physical devices such as note books and in memory as string, number, characters, etc. A computer language is incomplete without data.

Information is derived from data. The following information can be drawn if data is provided:

  • Per capita income
  • Average population of the states
  • Average temperature of the city
  • Price index
  • Performance of cricketers

Fig. 1.1 illustrates how information can be drawn from data.

Figure 1.1 Relation between data and information

  1. Everyday newspapers are delivered to our houses by the service man. It may be The Times of India or the Indian Express, and some other local language newspapers such as Lokmat and Janjagruti. The cost of each newspaper is different. How many papers have been received can be recorded in a notebook. This task is needed for calculating the total bill at the end of the month. The data here are the names of the newspapers, the dates on which they have been received and the cost of each. This data is needed to calculate the monthly or fortnightly bill. The total bill for the English newspapers as well as for the other papers can be calculated and analysed. One can draw different kinds of inferences such as whether the family is spending money on English newspapers or not and if so, how much. Does the family have educated members? Is the amount incurred on newspapers more than that on food? Data provided can be analysed for extracting different types of information.
  2. Information about any human can be expressed with his/her name, age, gender, phone number, city, etc., and can be stored in the form of a table, which is as shown in Table 1.1.

     

    Table 1.1 Information about a particular human

    Information details Data
    Name Satish
    Gender Male
    Age 23
    Phone 23234507
    City Pune
  3. Consider the Fig. 1.2. A and B are two stations and distance between them is 100 km by train. The distance between them is certainly more if travelled by road and shorter by plane. Here, the distance between the two stations can be indicated by connecting two cities by train, road, or air. The distances, both relative and absolute, between the cities are nothing but the data. This information helps a person to decide the mode of travel from station A to B. One can decide to go by train or bus depending upon the need, urgency and convenience. It should be clear now that data and information are not the same.

    Figure 1.2 Distance representation

  4. From the score of an individual cricket player we can draw information. Suppose, data consisting of the runs scored by a player in one-day cricket matches are provided. From the given data, the following information can be retrieved:
    1. Total runs scored
    2. Highest score
    3. Lowest score
    4. Average
    5. Best performance
    6. Strike rate
    7. Number of sixes
    8. Number of fours
    9. Number of forward shots
    10. Runs due to wide balls.

Information helps planners/analysts to make decisions. In this chapter, we are going to discuss application of data and information related to the computer.

1.1.1 Information in Computer

A computer is an electronic programmable device that manipulates information presented in the form of data. Computer science is mainly related to the study of data structures and their applications. The student of computer science should be aware of how data is manipulated in a system and the methods for utilization of data. It is, therefore, very essential to study the concepts of data organization and manipulation.

Data “Data is nothing but a collection of numbers, alphabets and symbols combined to represent information.”

Data stands for value or group of values. Table 1.2 describes the common data types used in the computer.

 

Table 1.2 Data and its description

Data Description
587 Numeric data
25/24/2002 Date formatted data
C PLUS PLUS Character data

Entity An entity possesses some attributes and some values can be allocated to it. For example, a student is an entity of a college. The probable properties and the corresponding values are as follows:

 

Table 1.3 Information about student

Every student in a college is an entity with different attributes. Sets of attributes are known as domain. Domains refer to possible values of a particular property. For example, the gender property can be assigned with values M or F.

1.2 DATA AND INFORMATION

The study of computer science deals with storage, retrieval, handling and organization of information. Information is generated in every sphere of life. For example, information about business transactions, or a student’s performance in an examination, can be stored in the computer memory. The same information can be retrieved, modified, and restored. The total marks of a student can be obtained by adding the marks scored in all subjects. Similarly, the average percentage of marks can be computed and student performance can be monitored and evaluated using different factors such as total marks, average marks, highest score, and lowest score.

Information is symbolic representation. It has some useful meaning that helps us in making good judgments.

1.3 OVERVIEW OF DATA STRUCTURES

Data structures are a method of representing of logical relationships between individual data elements related to the solution of a given problem. Data structures are the most convenient way to handle data of different types including abstract data type for a known problem. For example, the characteristics of a house can be represented by the house name, house number, location, number of floors, number of rooms on each floor, kind of fencing to the house—either with brick walls or wire, electrification—either underground or open, whether a balcony has been provided or not, etc. One can use a variety of data types to represent these data elements while solving a problem with the help of computer language such as char, int, boolean type, etc. Figure 1.3 shows the various fields of house. For example, with the help of computer the characteristics of a house can be represented: the number of floors of a house can be given with either int or char type. The house number, the number of rooms in it can be declared with the same type, provided that the data is within the limits of the range of data type. In C language, the char data type works perfectly as integer data in the range from −128 to 127 and as unsigned char from 0 to 255. Sometimes, selection of data type is important. Just as, for example, if we are going to fence the house should we use brick or wire. Here, the brick wall may be expensive. Likewise, if we are using signed int instead of char to store a positive number (number of floors) we are wasting one byte of the system. Hence, here char is appropriate, which occupies only one byte.

Electrification should be declared with char data type. Like the above example, in the practical application of data structures, to create data structures some components are involved directly or indirectly to build the system. In other words, data structures are a structured set of variables associated with one another in different ways, co-operatively defining components of the system.

The components of data can be organized and records can be maintained. Further, the record formation leads to the development of abstract data type and database systems.

Figure 1.3 Information about a house

In data structures, we also have to decide on the storage, retrieval and operation that should be carried out between logically related items. For example, the data must be stored in memory in computer-understandable format, i.e. 0 and 1 and the data stored must be retrieved in human-understandable format, i.e. ASCII. In order to transform data various operations have to be performed.

1.4 TYPES OF DATA STRUCTURES

A data structure is a structured set of variables associated with one another in different ways, cooperatively defining components in the system and capable of being operated upon in the program. As stated earlier, the following operations are done on data structures:

  1. Data organisation or clubbing
  2. Accessing technique
  3. Manipulating selections for information.

Data structures are the basis of programming tools and the choice of data structures should provide the following:

  1. The data structures should satisfactorily represent the relationship between data elements.
  2. The data structures should be easy so that the programmer can easily process the data.

Data structures have been classified in several ways. Different authors classify it differently. Fig. 1.4 (a) shows different types of data structures. Besides these data structures some other data structures such as lattice, Petri nets, neural nets, semantic nets, search graphs, etc., can also be used. The reader can see Figs. 1.4(a) and (b) for all data structures.

Linear In linear data structures, values are arranged in linear fashion. Arrays, linked lists, stacks and queues are examples of linear data structures in which values are stored in a sequence.

Non-Linear This type is opposite to linear. The data values in this structure are not arranged in order. Tree, graph, table and sets are examples of non-linear data structures.

Homogenous In this type of data structures, values of the same types of data are stored, as in an array.

Non-homogenous In this type of data structures, data values of different types are grouped, as in structures and classes.

Dynamic In dynamic data structures such as references and pointers, size and memory locations can be changed during program execution.

Static Static keyword in C is used to initialize the variable to 0 (NULL). The value of a static variable remains in the memory throughout the program. Value of static variable persists. In C++ member functions are also declared as static and such functions are called as static functions and can be invoked directly.

Figure 1.4 (a) Types of data structures

Figure 1.4 (b) Linear and non-linear data structures

1.5 PRIMITIVE AND NON-PRIMITIVE DATA STRUCTURES AND OPERATIONS

1.5.1 Primitive Data Structures

The integers, reals, logical data, character data, pointer and reference are primitive data structures. Data structures that normally are directly operated upon by machine-level instructions are known as primitive data structures.

1.5.2 Non-primitive Data Structures

These are more complex data structures. These data structures are derived from the primitive data structures. They stress on formation of sets of homogeneous and heterogeneous data elements.

The different operations that are to be carried out on data are nothing but designing of data structures. The various operations that can be performed on data structures are shown in Fig. 1.5.

  1. CREATE
  2. DESTROY
  3. SELECT
  4. UPDATE

Figure 1.5 Data structures operations

An operation typically used in combination with data structures and that creates a data structure is known as creation. This operation reserves memory for the program elements. It can be carried out at compile time and run-time.

For example,

 

int x;

Here, variable x is declared and memory is allocated to it.

Another operation giving the balancing effect of a creation operation is destroying operation, which destroys the data structures. The destroy operation is not an essential operation. When the program execution ends, the data structure is automatically destroyed and the memory allocated is eventually de-allocated. C++ allows the destructor member function to destroy the object. In C free () function is used to free the memory. Languages like Java have a built-in mechanism, called garbage collection, to free the memory.

The most commonly used operation linked with data structures is selection, which is used by programmers to access the data within data structures. The selection relationship depends upon yes/no. This operation updates or alters data. The other three operations associated with selections are:

  1. Sorting
  2. Searching
  3. Merging

Searching operations are used to seek a particular element in the data structures. Sorting is used to arrange all the elements of data structures in the given order: either ascending or descending. There is a separate chapter on sorting and searching in this book. Merging is an operation that joins two sorted lists.

An iteration relationship is nothing but a repetitive execution of statements. For example, if we want to perform any calculation several times then iteration, in which a block of statements is repetitively executed, is useful.

One more operation used in combination with data structures is update operation. This operation changes data of data structures. An assignment operation is a good example of update operation.

For example,

 

int x=2;

Here, 2 is assigned to x.

 

x=4;

Again, 4 is reassigned to x. The value of x now is 4 because 2 is automatically replaced by 4, i.e. updated.

1.6 BINARY AND DECIMAL INTEGERS

Data is expressed in terms of 0 and 1 known as bits. Different number systems are used to represent numbers. For example, decimal, octal and hexadecimal number systems, can be used. The decimal system uses ten different symbols from 0 to 9, octal uses 0 to 7, hexadecimal from 0 to 9 and further from A to F. We can convert from one number system to another. To convert a decimal number to binary, the double dabble method is used. In this method, the decimal number is divided by 2 and remainders are listed in reverse direction. The binary number obtained from this method is the equivalent of the decimal. For example, the binary 111 is nothing but decimal 7. In the binary number system, every bit has its own weight. The least significant bit has 20 weight. Weight position is calculated to the power of 2. The right-most bit of a binary number has a value of 1, which is represented as 20. The next bit position has value 21 and so on and the values for further bits can be calculated. In other words, weights are assigned to each bit in binary. The weights from the least significant bits are 1,2,4,8----.

For example, the equivalent binary representation of 5 is 101. This is explained as follows:

1 × 22 × 0 × 21 + 1 × 20

4 + 0 + 1 = 5

The power of two (weights) and binary bits are multiplied and the sum of all multiplications is taken to give the equivalent decimal number. There are two commonly used methods for representing negative binary numbers; they are as described in the following sections.

1.6.1 One’s Complement

In this method, a positive integer is converted to negative by changing each bit to its opposite value. For example, the binary number 0101 represents 5 and its complement is 1010.

1.6.2 Two’s Complement

In this method, 1 is added to the representation of one’s complement. For example, 7 is represented as 0111 with an unsigned number. With two’s complement, the number 7 becomes 1001 (One’s complement of 0111 = 1000 and 1 is added at its least significant position giving a result of 1001).

1.6.3 Binary Coded Decimals

In addition to the binary number system, the programmer can also use decimal numbers. For example, a string of bits can be used to represent integers in the decimal number system. The decimal number from 0 to 9 can be represented using only a four-bit combination. Table 1.4 shows the decimal number and their equivalent binary digits.

A string of bits can be broken randomly into separate groups of four bits. Each group represents a digit. For example, the bit string 01100010 can be separated into two strings 0110 and 0010. The first string indicates six and the second two. The complete string represents 62. This method of representation is called as binary coded decimal.

 

Table 1.4 Four bits and equivalent decimal number

Decimal number Binary-coded decimal code (8421)
0
0000
1
0001
2
0010
3
0011
4
0100
5
0101
6
0110
7
0111
8
1000
9
1001

1.6.4 Integers

We know what integers are and are aware of the arithmetic operations performed with them such as addition, subtraction, multiplication, and division. Integer-type data plays an important role in calculation. A counting of the number of objects can be shown by integers. The amount in a bank account, the number of students in a class and number of keys on a keyboardall this information can be expressed in integers.

The traditional method of writing negative numbers is to put a sign symbol before the number. This method is called as sign and magnitude method and is commonly used in several computers to represent signed numbers. Normally, the sign is shown at the first or left-most bit of the binary number representation. In addition, the magnitude part appears followed by the sign.

The left-most bit is only for indicating the sign, but it does not have any weight as in an unsigned number system. In other words, a bit string beginning with zero shows a positive number whereas a bit string beginning with one indicates a negative number, if numbers are to be represented in a signed format.

 

Table 1.5 Sign bit

Number Sign Bit Magnitude
+7
0
00…0111
−6
1
10…0110

In the Table 1.5, 0 and 1 are used to represent positive and negative numbers. An integer shown with its sign is known as a signed integer. There are two types of signed integers: a) positive signed integer b) negative signed integer. We studied that these signs are represented in memory by 0 and 1 as shown in Table 1.5. The sign bit is always written as the leftmost bit. While storing signed numbers, the system reserves the leftmost bit for representation of the sign.

Positive signed integers are shown in the form called the signed magnitude form. In this style, in the leftmost bit, the sign is shown by 0 and magnitude is shown in the matching binary form.

For example,

+7 is shown by 0111

Negative signed numbers are shown in one of the following forms:

  1. Signed − magnitude form
  2. Signed − 1’s complement form
  3. Signed − 2’s complement form

In the signed magnitude form method, 1 shows the sign of the number and magnitude is shown by the corresponding binary form.

Example

−7 is shown as 1111 signed number

−7 is shown as 1,000 in one’s complement format

−7 is shown as 1001 in two’s complement format

Table 1.6 shows the various ways of representing binary and negative numbers.

 

Table 1.6 Binary, Negative numbers in signed format and 1’s complement of negative numbers

In Table 1.6 positive and negative numbers are shown. Signed numbers and signed −1’s complements of negative numbers are also shown in the said figure. The sign is shown by 1 and the magnitude is shown in the 1’s complement form.

−7 is shown as 1,000.

In the signed −2’s complement form, the sign of the number is shown by 1 and the magnitude is shown in the 2’s complement form. The 2’s complement of a number is the addition of 1’s complement of the particular number and 1.

Table 1.7 shows 2’s complement of the numbers.

2’s complement of −7 is shown as 1,001

 

Table 1.7 2’s complement of numbers

1.6.5 Real Numbers

A number having an integer part and a fractional part is called a real number. The real number 548.56 can be written as 5.4856 × 102 or 0.54856 × 103. This type of representation is called scientific representation. The floating-point notation is generally used by all computer systems to indicate real numbers. There are several notations or methods to represent real numbers. Each method is unique and has different characteristics.

The real number has two parts: mantissa and base. It is represented by a number called mantissa. The base portion is always raised to the number and it is called the exponent. The base is always fixed. The mantissa and exponent vary. Different values of mantissa and exponent give different real numbers. For example,

The base is 10; the number 221.98 would be 22198 × 10−2. The mantissa is 22198, exponent is −2. The values can also be written as.22198 × 103, 221.98,221.98n × 100.

The benefit of floating-point notation is that it can be used to show numbers with small or large absolute values. The biggest number that can be represented is 223−1 × 1027. In addition, the smallest positive number is 10−128. which no doubt is very small. The limit of precision on a computer is the number of significant binary digits in the mantissa.

Example 1.1

Write a program to declare float and double type values and display them.

Solution

# include <stdio.h>

# include <conio.h>

main ()

{

float f=31343412.123;

double d=46481232.77;

clrscr();

printf (" f= %lg",f);

printf ("\nd=%lg",d);

}

OUTPUT

f= 3.13434e+07

d=4.64812e+07

Explanation In this program the variables f of float and d of double type are declared and are initialized. The values are displayed using base and mantissa format.

1.6.6 Character String

In the past, computers were in fact used as calculators and only numeric data could be manipulated with them. In those days, computer programs were written in numeric form. Programming in numeric form was difficult. To overcome this limitation symbolic codes were defined to represent information as character data. The invention of character data led to the formation of mnemonics for use as address and in operation. Using mnemonics, assembly languages and various procedure-oriented languages were developed.

A character is stored in computer memory as a series of bits in succession. Unique bit patterns are assigned to every character in the character set. Fixed length bits can be controlled more efficiently than variable length bit sequences. For that reason, character sets are programmed in fixed length bit sequences.

Information contains all types of data, viz., numbers, characters, symbols, etc. Hence, it is not possible to represent information by only numeric data. Information such as names and book titles are required to be represented with characters. Thus, all non-numeric information is represented by a sequence of characters called strings.

For example, in some systems 00100110 is used to show the ‘$’ symbol and different types of such bit patterns represent ‘A’, ‘C’, ‘D’ and so on. In different countries, the computer may have a few additional symbols. The character set can be created using fonts. The programmer can create different fonts according to the language and culture of the country.

We know that 8 bits are used to represent a character and 256 different characters can be shown using these unique bit combinations. Suppose, the string 1101001 is used to represent character ‘A’ and 0100001 is used to represent ‘B’, then the string “AB” can be shown by the bit string 11010010100001. We know that a string is sequence of a characters and a character string is shown by concatenation as the bit strings, which represent separate characters of the string. Examples of strings are illustrated in Chapter 2.

1.7 LOGICAL INFORMATION

Primitive data structures also include logical data, i.e. true or false. Only two logical constants, true and false are present. In C /C ++programming 0 is assumed as false and any non-zero value as true. In C++, a new data type bool is introduced to handle logical conditions.

Expressions containing logical variables are used with relational operators such as <, >, ==, = etc. The result of such expression is only true (1) or false (0). The result is returned by the expression.

The storage representation of logical values depends upon the compiler or interpreter used by the language to convert the source program to a machine code. Normally, one bit is enough to store logical information. In C/C++ it is possible to store information in bits. The following programs explain true and false values returned by expressions and storing data using bits.

Example 1.2

Write a program to display logical values returned by logical expressions.

Solution

# include <stdio.h>

# include <conio.h>

main ()

{

clrscr();

printf ("False : %d\n", 3>5);

printf ("True : %d", 5>1);

}

OUTPUT

False : 0

True : 1

Explanation The two expressions are put in the printf () statement. The first condition 3>5 is false; hence, the return value is 0. The second expression 5>1 returns 1, i.e. the expression is true. Consider the following program, which stores return values in bits using structure.

Example 1.3

Write a program to identify the entered IP address. Display its class, mask and last address.

Solution

# include<stdio.h>

# include <conio.h>

main ()

{

int ip0,ip1,ip2,ip3;

clrscr();

printf("\nEnter the IP address:-");

scanf("%d.%d.%d.%d",&ip0,&ip1,&ip2,&ip3);

if(ip0 >= 1 && ip0<128)

{

 printf("\nThe given IP address %d.%d.%d.%d is in class A",ip0,ip1,ip2,ip3);

 printf("\nMask for class A address = 255.0.0.0");

 printf("\nThe last address of class A = 127.255.255.255");

}

if(ip0>127 & ip0<192)

{

 printf("\nThe given IP address %d.%d.%d.%d is in class B", ip0,ip1,ip2,ip3);

 printf("\nMask for class B address = 255.255.0.0");

 printf("\nThe last address of class B = 191.255.255.255");

}

if(ip0>191 & ip0<224)

{

 printf("\nThe given IP address %d.%d.%d.%d is in class C",ip0,ip1,ip2,ip3);

 printf("\nMask for class C address = 255.255.255.0");

 printf("\nThe last address of class C = 223.255.255.255");

}

if(ip0>223 & ip0<240)

{

 printf("\nThe given IP address %d.%d.%d.%d is in class D",ip0,ip1,ip2,ip3);

 printf("\nThe last address of class D = 239.255.255.255");

}

if(ip0>239 & ip0<248)

{

 printf("\nThe given IP address %d.%d.%d.%d is in class E",ip0,ip1,ip2,ip3);

 printf("\nThe last address of class E = 247.255.255.255");

}

}

OUTPUT:

Enter the IP address:- 198.1.1.1

The given IP address 198.1.1.1 is in class C

Mask for class C address = 255.255.255.0

The last address of class C = 223.255.255.255

Explanation In this program the IP address is stored in the ip0, ip1, ip2 and ip3 variables. For each class a separate if condition is used and the relevant values are displayed on the screen.

Example 1.4

Write a program to store logical values in bit using structure.

Solution

# include <stdio.h>

# include <conio.h>

main ()

{

struct bits

{

 int state :1;

};

struct bits a;

a.state=13>5;

clrscr();

if (a.state==0) printf ("False");

else printf ("True : %d",5>1);

}

OUTPUT

True: 1

Explanation In the structure bits, the number of bits given is to be used by the member of structure to store values. The value returned by the expression 13>5 are stored in variable state that stores the value in one bit. The if statement checks the value and the appropriate message is displayed.

1.8 STORAGE OF INFORMATION

The digital computers have two types of memory: operational memory and storage memory. The operational memory refers to CPU registers. The CPU registers are temporarily used to store values. The CPU contains registers called accumulators that contain the variables while arithmetic operations are performed. For example, when numbers are added the result is stored in AX register of the CPU. The following program explains this.

Example 1.5

Write a program to access value using CPU register.

Solution

# include <stdio.h>

# include <conio.h>

main ()

{

 int x=10,y=2;

 clrscr();

 _AX=x*y;

 printf ("\n Multiplication of x and y is %d",_AX);

 _AX=x+y;

 printf ("\n Addition of x and y is %d",_AX);

}

OUTPUT

Multiplication of x and y is 20

Addition of x and y is 12

Explanation In this program, integer variable, x and y are declared and initialised with 10 and 2. The statement x * y calculates the product and x+y calculates the addition of the variables. The obtained result is stored in register AX. We print the value using pseudo variable _AX.

In addition, CPU registers are also used to store ‘temporarily’ program instructions and program control information, which is helpful in program execution. Therefore, registers are only used to hold data temporarily.

The storage type memory is used for permanent storage of data that can be retrieved at any time. Before performing an arithmetic operation, the value of a variable is stored in the memory unit and then transferred to the register. If the obtained result is to be stored in another variable, it is necessary to again transfer values from register to storage memory

When a program execution is started, instructions and data are stored in storage units. The whole storage unit of computer is called main memory. Information is an input to the storage unit.

1.9 HARDWARE AND SOFTWARE

The memory of the computer is nothing but a group of bits. The values 0 and 1 are called bits. The unit formed by bits is called value, i.e. a group of bits represents a value. A group of 8 bits is called byte. Many bytes when grouped together are called word. Every byte in a memory has a unique address. The address is useful to identify the byte and its contents. In C it is possible to access the byte address. The address is always numeric (unsigned integer) and a not-negative number. The address is also called memory location. The computer system has a built-in mechanism that handles and manipulates different types of bit patterns according to the object or variable that holds the value.

For example, the computer contains an instruction to multiply two binary numbers and place the obtained value in another memory location. The mechanism to perform such an operation should have the following steps:

  1. Extract argument bit patterns from two given addresses.
  2. Construct a third bit pattern showing an integer, which is a product of two binary integers.
  3. The obtained result bit pattern is assigned to another memory location.

The computer hardware is bit oriented whereas software is byte oriented, i.e. the computer hardware is capable of interpreting the bit patterns at a specified memory location. This is what we discussed concerning an operation between two integers. In case two real values are given, the computer hardware will apply another built-in mechanism to handle this data type. As discussed earlier, to handle native data type, necessary routines are in-built into the hardware. The instruction identifies the data type by value or address. The values are assigned explicitly and addresses are allocated implicitly by the system.

Consider the following C/C++ statements.

int j=4, k=5,h;

float p=9.1, q = 5.5, r;

In the above statements, four variables are declared and memories in bytes are allocated to them. j, k, p and q are called variables or identifiers. The variable name is useful to store values. A variable is nothing but a name given to memory location. The values stored in j and k will be interpreted as integers whereas the values of p and q will be interpreted as float. The C/C++ compiler translates the source program to machine language (object code).

Consider the following statements:

h=j+k;

r=p+q;

The first statement performs addition of j and k integer variables and stores the result in h. In the second statement addition of p and q are stored in variable r.

The operator ‘+’ is common. Operators such as +,*,−,/ are overloaded in such a way that they can be used with any data type to perform an operation. All these operators are generic, i.e. they can be used with all standard data types.

  1. These operators perform operations with all data types.
  2. These operators have different meaning depending on context. For example, the operator ‘*’ can be used for multiplication as well as for pointer notation.

In high-level language, declaration of variable plays an important role. The declaration contains data type name followed by variable list. The variables are allocated memory according to the data type.

For example, integer variable requires two bytes; float variable requires four bytes, etc.

The first column contains the name of the data type. These names are reserved words known as keywords. The second column has the number of bytes required by a variable of data type. The number of bytes may vary in different systems. The third column contains a range of data types, i.e. lowest and highest limits of numbers that can be stored in variables of respective data type.

1.10 CONCEPT OF DATA TYPES

A data type is a term that refers to the type of data values that may be used for processing and computing.

The information stored in memory is in the form of bits 0 and 1. We can view the memory in human-understandable format with the help of data type. The type of computer hardware decides the data type and the range it supports. Range means the largest and smallest possible values that can be represented. Our goal is to study how a user can utilize the data type to represent information. We need not think about what the computer does internally.

Suppose that data types are independent of computer hardware, then unlimited data types can be built. A data type is nothing but an abstract concept designed using logical operators. After designing such data type and its supporting operations we can use the data type. The instructions regarding the operation related to data type can be given by hardware and software. The necessary instructions are built into the computer hardware as hardware implementation. When a program gives such instructions it is known as software implementation. The instructions given in the computer program interpret the bit patterns.

1.11 DATA TYPES IN C

Various data types are used in the C language. Variables are used for assigning integers, long integers, or characters, etc. We can differentiate between data types such as integer, real, logical, complex variables, etc.

C contains four standard data types. They are int, float, char and double. Almost in all computers, all the above four data types are local to computer hardware. We have already discussed how integers, floats and characters are stored in memory and their manipulation. A double variable is a double precision floating-point number.

In addition, there are three qualifiers applicable to int. They are short, long and unsigned. When a variable is declared unsigned, it can store only positive values. By default when a variable is declared as int, it is short int. Its range is −32,768 to 32,767. To store values above this range, a long qualifier is used and its range is −2147483648 to 2147483647. An unsigned integer is always an absolute value and follows arithmetic laws of module 2n, where, n is the number of bits in an integer. The ranges of data types and number of bytes needed to store them are shown in Table 1.8.

 

Table 1.8 C data types

Data types No. of bytes Range
char
1
−128 to 127
unsigned char
1
0 to 255
signed char
1
−128 to 127
int
2
−32768 to 32767
unsigned int
2
0 to 65535
signed int
2
−32768 to 32767
short int
2
−32768 to 32767
unsigned short int
2
0 to 65535
signed short int
2
−32768 to 32767
long int
4
−2147483648 to 2147483647
signed long int
4
−2147483648 to 2147483647
unsigned long int
4
0 to 4294967295
float
4
3.4E–38 to 3.4E+38
double
8
1.7E–308 to 1.7E+308
long double
10
3.4E–4932 to 1.1E+4932
enum
2
−32768 to 32767
1.12 ABSTRACT DATA TYPES

In programming, a situation occurs when built-in data types are not enough to handle the complex data structures. It is the programmer’s responsibility to create this special kind of data type. The programmer needs to define everything related to the data type such as how the data values are stored, the possible operations that can be carried out with the custom data type and that it must behave like a built-in type and not create any confusion while coding the program. Such custom data types are called Abstract data type. In C struct and in C++ struct/class keywords are used to create abstract data type.

For example, if the programmer wants to define date data type which is not available in C/ C++, s/he can create it using struct or class. Only a declaration is not enough; it is also necessary to check whether the date is valid or invalid. This can be achieved by checking using different conditions. The following program explains the creation of date data type:

Example 1.6

Write a program to create abstract data type date.

Solution

# include <stdio.h>

# include <conio.h>

struct date

{

 int dd;

 int mm;

 int yy;

};

main ()

{

 struct date d; // date is abstract data type

 clrscr();

 printf ("Enter date (dd mm yy) :");

 scanf ("%d %d %d",&d.dd,&d.mm, &d.yy);

 printf ("Date %d-%d-%d",d.dd,d.mm,d.yy);

}

OUTPUT

Enter date (dd/mm/yy): 08 12 2003

Date 08-12-2003

Explanation In this program, using struct keyword the date data type is declared. It contains three-integer variables dd, mm and yy to store date, month and year. Through scanf statement date, month and year is entered and it is displayed using printf statement.

1.13 POINTERS

A pointer is a link or reference to data structures. The most important characteristic of pointer is that it allows identical method of referencing any data structures, no matter of what complexity and type. The pointer can point to any data type character, float, int, etc., and the method of accessing elements are the same. A pointer also allows quick insertion and deletion of an item in a list. The linked list is discussed later in this book.

There are two techniques of accessing data structures.

1.13.1 Computed Address

In this technique the data structures can directly be accessed using an address. The address is calculated by the compiler or interpreter, which translates the source program to an object code.

1.13.2 Pointer Addressing

The C/C++ pointers are of this type, in which a memory address is assigned to a pointer variable. Depending upon the complexicity of data structures some operations are also required in this technique. However, this technique is time consuming.

A pointer is a memory variable that stores a memory address of another variable. It can have any name that is acceptable for other variables and it is declared in the same way as other variables. It is always denoted by ‘*’.

  1. Pointers save memory space.
  2. Execution time of a program is faster because address of variable can be accessed and read / write operation with addresses directly done.
  3. Memory is used efficiently with pointers.
  4. Pointers are used with data structures. They are very useful for representing arrays.

int *x;

float *y;

char *y;

  1. In the first statement ‘x’ is an integer pointer and it tells the compiler that it holds the address of an integer variable. The variable f is a float pointer and it can hold the address of only the float variable. The *y is a character variable and holds the address of any character variable.
  2. The indirection operator (*) is also called the deference operator. When a pointer is dereferenced, the pointer retrieves the value stored at that address.
  3. The indirection operator (*) is used in two distinct ways with pointers, declaration and deference.
  4. When the pointer is dereferenced, the indirection operator indicates that the value at that location stored in the pointer is to be accessed rather than address.
  5. The ‘&’ operator is an address operator and it gives the address of the variable. The ‘&’ immediately preceding the variable returns the address of the variable.

Example 1.7

Write a program to demonstrate the use of a pointer.

Solution

# include <stdio.h>

# include <conio.h>

main ()

{

int x=2;

int *p;

clrscr();

p=&x;

printf ("\n Address of x is = %u", &x);

printf ("\n Value of x is = %d", *p);

}

OUTPUT

Address of x is = 65524

Value of x is = 2

Explanation In this program, an integer variable x is declared and assigned with value 2. Also, integer pointer *p is declared and initialized with address of x. The first printf statement displays the address of x. The second statement displays the value of x using pointer p.

Arithmetic operations on pointer variables are also possible. Increase, decrease, prefix and postfix operations can be performed with the help of pointers.

The following operations are not possible with address:

  1. Addition of two addresses (pointers).
  2. Multiplication of two addresses or multiplication with a constant.
  3. Division of address with a constant.
1.14 STRUCTURES IN C

In this topic, we will discuss C data structures called structures. A structures is a collection of one or more variables of different data types, grouped together under a single name and new custom data type formed. The individual variables are called member variables. By using structures, we can make a group of variables, arrays, pointers, etc. The new data type formed by the structures is independent of computer hardware and we already studied that when data type is independent of computer hardware, unlimited data types can be formed. Now, consider the following declaration of structure and program to understand the concept.

struct student

{

 char name[20];

 int age;

 float wt;

};

In this example, the structure student is declared by combining three standard data types. The structure name is called as tag name. Here, three data types can be accessed separately and hence they are not mixed.

Consider the following example,

Example 1.8

Write a program to demonstrate how structures are used to store and display data.

Solution

# include <stdio.h>

# include <conio.h>

struct student

{

char *name;

int age;

float weight;

};

main ()

{

struct student s1;

s1.name="Nilesh";

s1.age=25;

s1.weight=55;

clrscr();

printf ("\n Name = %s",s1.name);

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

printf ("\n Weight = %g",s1.weight);

}

OUTPUT

Name = Nilesh

Age = 25

Weight = 55

Explanation In this program, structure is defined and a custom data type is formed. Here, the program contains information regarding data type; hence, it is called software implementation.

struct student s1; // c style

Using the above statement, variables (objects) of structures data type student can be declared. s1 is an object of structure data type. The dot (.) operator with variable is used to access individual variables and initialization and display of value can be done. When a structure is declared separate, memory is allocated to each variable according to its data type. The total size of the variable of struct type is the sum of bytes of all member variables. Using the operator sizeof () we can demonstrate this. Consider the following program.

Example 1.9

Write a program to demonstrate that the size of structure variable is equal to the sum of sizes of member variables.

Solution

# include <stdio.h>

# include <conio.h>

main ()

{

struct data

{

char ch;

int in;

float fl;

};

struct data d;

clrscr();

printf ("\nSize of character ch = %d",sizeof(d.ch));

printf ("\nSize of integer in = %d",sizeof(d.in));

printf ("\nSize of float fl = %d",sizeof(d.fl));

printf ("\nSize of object d = %d",sizeof(d));

}

OUTPUT

Size of character ch = 1

Size of integer in = 2

Size of float fl = 4

Size of object d = 7

Explanation In this program structure data is declared with three standard data types: char, int and float. d is a variable of data type. Using sizeof () operator size of every member, variable d is calculated and displayed. The size of variable d is the sum of the sizes of all members. The output gives a clear idea.

1.15 UNIONS

Union is a user defined data type very similar to structure. It contains members like structure but no separate memory is allocated to each member. The size of the largest element is detected and this much amount is allocated. Members of a union share common memory locations. The union data structure is useful to invoke BIOS and DOS services. An example follows:

Example 1.10

Write a program to demonstrate use of unions.

Solution

# include <stdio.h>

# include <conio.h>

# include <dos.h>

main ()

{

union REGS in,out;

int86(18,&in,&out);

clrscr();

printf ("\n Total memory = %d KB", out.x.ax);

}

OUTPUT

Total memory = 640 KB

Explanation In this program union is in use. int86 () is a function. The value 18 is a service number. The function calculates the total size of memory and it is displayed by printf () statement. While discussing types of data structures, we discussed static data structures. Consider the following example of a static variable.

Example 1.11

Write a program for displaying the size of the data type in union and the size of the object of the union.

Solution

# include <stdio.h>

# include <conio.h>

main ()

{

 union set

 {

  char x;

  int y;

  float z;

  long double a;

 };

  union set s1;

  clrscr();

  printf ("\nSize of character x = %d",sizeof(s1.x));

  printf ("\nSize of integer y = %d",sizeof(s1.y));

  printf ("\nSize of float z = %d",sizeof(s1.z));

  printf ("\nSize of long double a = %d",sizeof(s1.a));

  printf ("\nSize of object s1 = %d",sizeof(s1));

}

OUTPUT:

Size of character x = 1

Size of integer y = 2

Size of float z = 4

Size of long double a = 10

Size of object s1 = 10

Explanation In this program, union of the set is declared and s1 is the object of the union set. The union set contains integer, character, float and long double data types. The program shows the size of all the data types but it shows the size of the object 10 because the long double has the size 10.

Example 1.12

Write a program to explain the use of a static variable.

Solution

# include <stdio.h>

# include <conio.h>

main ()

{

static int x;

clrscr();

x++;

printf (" x= %d",x);

}

OUTPUT

x=1

Explanation When variables are declared and not initialized, they contain garbage values. Hence, they cannot be used without initializing. When such variables are declared as static, they are initialized to zero and can directly be involved in an operation.

1.16 ALGORITHMS

An algorithm is a well-organized, pre-arranged and defined computational module that receives some value or set of values as input and provides a single or a set of values as output. These well-defined computational steps are arranged in sequence, which processes the given input into output. Algorithms are used to solve applications that are complex. An algorithm is said to be accurate and truthful only when it provides the exact wanted output, obviously, after implementation of algorithm into program.

1.16.1 Analysing Algorithm

When one writes an algorithm, it is essential to know how to analyse it. Analyzing an algorithm refers to calculating or guessing resources needful for the algorithm. Resources means computer memory, processing time, logic gates, etc. In all these factors, time is most important because the program developed should be fast in processing. The analysis can also be made by reading the algorithm for logical accuracy, tracing the algorithm, implementing it and checking it with some data and with a mathematical technique to confirm its accuracy.

Algorithms can also be expressed in a simple method that will help the user to put it into operation easily. However, this approach has a few drawbacks. It requires more space and time. It is very essential to consider the factors of time and space of an algorithm.

1.16.2 Rate of Growth

In practice, frequently it is not possible to act upon a simple analysis of an algorithm to conclude the execution time of an algorithm. The execution time depends upon the machine and its way of implementation.

Timing analysis depends upon the input required. To accurately carry the time analysis, it is also very essential to know the exact directives executed by the hardware and the execution time passed for each statement.

1.16.3 Space Requirement

The space or memory requirement of a program is the memory space required to execute the program. From the total allocated memory, a fixed portion occupies code, variable and space for data, etc. The space analysis is only made for the memory space to store data values. It does not include the space required for the algorithm itself. The memory space requirement can be calculated as follows:

s(p)=c+sp

c is constant

s(p) is space requirement

sp refers to instance attribute.

1.16.4 Time Requirement

It indicates the time required for execution of the program. The complete time T (p) is the total of time required for compiling and executing of the program. The compile time is not dependent on instance attribute.

Summary
  1. A computer is an electronic device that manipulates information presented in the form of data.
  2. The study of any characteristic in computer science means the study of storage, retrieval, manipulation and organization of information.
  3. Information is symbolic representation. It has some useful meaning for us and allows us to make good judgements. Information is always expressed by data. Data is nothing but a collection of numbers, alphabets, symbols, etc., combined to represent information.
  4. The integers, real, logical data, character data, pointer and reference are primitive data structures. Data structures that are normally directly operated upon by machine-level instructions are known as primitive data structures.
  5. Operations that create data structures are known as creation.
  6. Destroy operations destroy data structures.
  7. The most commonly used operation linked with data structures is selection, which is used by programmers to access the data within data structures. Selection relationship depends upon yes/no.
  8. The iteration relationship depends upon repetition.
  9. A number that has only the integer part is called an integer number.
  10. A number that has the integer part and the fractional part is called a real number.
  11. Primitive data structures also include logical data, i.e. true or false. Only two logical constants—true and false—are present.
  12. All non-numeric information is represented by a sequence of characters called strings.
  13. The information stored in memory is in the form of bits 0 and 1. The information in the memory can be viewed and understood by humans with the help of data types. The type of computer hardware decides the data type and the range it supports. Range means the largest and smallest possible values that can be represented.
  14. A pointer is a link or reference to data structures.
  15. A pointer is a memory variable that stores a memory address of another variable. It can have any name that is valid for the other variable and it is declared in the same way as any other variable. It is always denoted by ‘*’.
  16. A structure is a collection of one or more variables of different data types grouped together under a single name and new custom data type is formed.
  17. An algorithm is a well-organized, pre-arranged, and defined computational module that receives some value or set of values as input and provides a single or a set of values as output.
  18. Analyzing an algorithm refers to calculating or estimating the resources needed for the algorithm. Resources means computer memory, processing time, logic gates, etc.
  19. The space or memory requirement of a program is the memory space required to execute the program. The execution time is dependent upon the machine and the way of implementation.
Exercises
  1. Answer the following questions:
    1. What is a computer?
    2. What is information? Explain with a few examples.
    3. What is data? Explain with a few examples.
    4. Mention different types of data structures.
    5. Distinguish between structure and class.
    6. What are the functions of pointer and reference?
    7. Explain logical information. List the operators related to it.
    8. Explain the different operations related to data structures.
    9. Explain the concept of data type.
    10. Explain integers and real numbers.
    11. Explain algorithm and its types. (a) Searching (b) sorting.
    12. Explain algorithm with the factors time and space.
    13. What are the different data types available in C language? Explain with examples.
  2. Attempt the following programs:
    1. Write a program to store logical values returned by an expression in individual bits.
    2. Write a program to perform addition of two variables using pointers and reference.
    3. Write a program to demonstrate the update of the operation of data structures with variables.
    4. Write a program to convert a decimal number to its binary equivalent.
    5. Write a program to create abstract data types.
    6. Write a program to get information about a student and display it on the screen by using structure.
    7. Write a program to add two numbers using structure.
  3. Select the appropriate option for each of the following:
    1. An array is a ____ type of data structure.
      1. linear
      2. non-linear
      3. dynamic
      4. (a) and (b)
    2. Homogenous means ____.
      1. values of the same type
      2. having all equal values
      3. (a) and (b)
      4. dissimilar values
    3. Information is represented by ____.
      1. data
      2. characters
      3. numeral
      4. bits
    4. In this method a positive integer is converted to negative by changing each bit to its opposite value.
      1. one’s complement
      2. two’s complement
      3. both (a) and (b)
      4. none of the above
    5. The data type defined by the user is known as ____.
      1. abstract data type
      2. built-in data type
      3. classic data type
      4. none of the above
    6. The keyword class or struct can be used to create ____.
      1. abstract data type
      2. built-in data type
      3. logical data type
      4. all of the above
    7. The destructor performs the ____ operation
      1. destroy
      2. update
      3. selection
      4. both (a) and (c)
    8. An integer data type is ____.
      1. primitive
      2. non-linear
      3. (a) and (b)
      4. non-primitive
  4. What will be the output of the following programs?
    1. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      static int a;

      clrscr();

      printf (" %d",a++);

      static int a;

      clrscr();

      printf (" %d",a++);

      printf (" %d",a);

      printf (" %d",a++);

      printf (" %d",a);

      }

       

    2. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      struct abc

      {

      char c;

      int i;

      float f;

      };

      struct abc a;

      clrscr();

      printf ("\n%d",sizeof(a.c));

      printf ("\n%d",sizeof(a.i));

      printf ("\%d",sizeof(a.f));

      printf ("\n%d",sizeof(a));

      }

       

    3. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      union xyz

      {

      float c;

      int i;

      double f;

      };

      union xyz w;

      clrscr();

      printf ("\n%d",sizeof(w.c));

      printf ("\n%d",sizeof(w.i));

      printf ("\%d",sizeof(w.f));

      printf ("\n%d",sizeof(w));

      }

       

    4. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      int a=2;

      float b=220.20;

      clrscr();

      printf ("\n %f %d",a,a);

      printf ("\n %f %d",b,b);

      }

       

    5. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      int a=2,b=10,c=100;

      a=b;

      b=c;

      clrscr();

      printf ("\n%d %d %d",a,b,c);

      }

       

    6. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      char c=’A’;

      b=c+2;

      }

       

    7. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      int a=2;

      int *b;

      clrscr();

      a=&b;

      printf ("\n %u", &a);

      printf ("\n %d",*(&b));

      printf ("\n %d",*b);

      }

       

    8. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      int a=2;

      float b=10.02;

      clrscr();

      printf ("\n%f %d",b/a,b/a);

      printf ("\%f %d",a/b,a/b);

      }

       

    9. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      char c=’A’;

      clrscr();

      printf ("\n%d %c",c,c);

      }

       

    10. # include <stdio.h>

      # include <conio.h>

      main ()

      {

      int b=32767;

      b++;

      }