Arrays

You have already studied about arrays and are well-versed with the techniques to utilize these data structures. Here we will discuss how arrays can be used to solve computer problems. Consider the following program:

main( int argc, char** argv )
{
int x[6];
int j;
for(j = 0; j < 6; j++)
x[j] = 2 * j;
}

We have declared an int array of six elements and initialized it in the loop.

Let’s revise some of the array concepts. The declaration of array is as int x[6]; or float x[6]; or double x[6]; You have already done these in your programming assignments. An array is collection of cells of the same type. In the above program, we have array x of type int of six elements. We can only store integers in this array. We cannot put int in first location, float in second location and double in third location. What is x? x is a name of collection of items. Its individual items are numbered from zero to one less than array size. To access a cell, use the array name and an index as under:

x[0], x[1], x[2], x[3], x[4], x[5]

To manipulate the first element, we will use the index zero as x[0] and so on. The arrays look like in the memory as follows:












Array occupies contiguous memory area in the computer. In case of the above example, if some location is assigned to x[0], the next location can not contain data other than x[1]. The computer memory can be thought of as an array. It is a very big array. Suppose a computer has memory of 2MB, you can think it as an array of size 2 million and the size of each item is 32 bits. You will study in detail about it in the computer organization, and Assembly language courses. In this array, we will put our programs, data and other things.

In the above program, we have declared an array named x. ‘x’ is an array’s name but there is no variable x. ‘x’ is not an lvalue. If some variable can be written on the left- hand side of an assignment statement, this is lvalue variable. It means it has some memory associated with it and some value can be assigned to it. For example, if we have the code int a, b; it can be written as b = 2; it means that put 2 in the memory location named b. We can also write as a = b; it means whatever b has assign it to a, that is a copy operation. If we write as a = 5; it means put the number 5 in the memory location which is named as a. But we cannot write 2 = a; that is to put at number 2 what ever the value of a is. Why can’t we do that? Number 2 is a constant. If we allow assignment to constants what will happen? Suppose ‘a’ has the value number 3. Now we assigned number 2 the number 3 i.e. all the number 2 will become number 3 and the result of 2 + 2 will become 6. Therefore it is not allowed.

‘x’ is a name of array and not an lvalue. So it cannot be used on the left hand side in an assignment statement. Consider the following statements

int x[6];
int n;
x[0] = 5; x[1] = 2;
x = 3; //not allowed
x = a + b; // not allowed
x = &n; // not allowed

In the above code snippet, we have declared an array x of int. Now we can assign values to the elements of x as x[0] = 5 or x[1] = 2 and so on. The last three statements are not allowed. What does the statement x = 3; mean? As x is a name of array and this statement is not clear, what we are trying to do here? Are we trying to assign 3 to each element of the array? This statement is not clear. Resultantly, it can not be allowed. The statement x = a + b is also not allowed. There is nothing wrong with a + b. But we cannot assign the sum of values of a and b to x. In the statement x = &n, we are trying to assign the memory address of n to x which is not allowed. The reason is the name x is not lvalue and we cannot assign any value to it. For understanding purposes, consider x as a constant. Its name or memory location can not be changed. This is a collective name for six locations. We can access these locations as x[0], x[1] up to x[5]. This is the way arrays are manipulated.

Sometimes, you would like to use an array data structure but may lack the information about the size of the array at compile time. Take the example of telephone directory. You have to store one lakh (100,000) names in an array. But you never know that the number of entries may get double or decline in future. Similarly, you can not say that the total population of the country is one crore (10 million) and declare an array of one crore names. You can use one lakh locations now and remaining will be used as the need arrives. But this is not a good way of using the computer resources. You have declared a very big array while using a very small chunk of it. Thus the remaining space goes waste which can, otherwise, be used by some other programs.

We will see what can be the possible solution of this problem?

Suppose you need an integer array of size n after the execution of the program. We have studied that if it is known at the execution of the program that an array of size 20 or 30 is needed, it is allocated dynamically. The programming statement is as follows:

int* y = new int[20];

It means we are requesting computer to find twenty memory locations. On finding it, the computer will give the address of first location to the programmer which will be stored in y. Arrays locations are contiguous i.e. these are adjacent. These twenty locations will be contiguous, meaning that they will be neighbors to each other. Now y has become an array and we can say y[0] =1 or y[5] = 15. Here y is an lvalue. Being a pointer, it is a variable where we can store the address of some variable. When we said int* y = new int[20]; the new returns the memory address of first of the twenty locations and we store that address into y. As y is a pointer variable so it can be used on the left-hand side. We can write it as:

y = &x[0];

In the above statement, we get the address of the fist location of the array x and store it in y. As y is lvalue, so it can be used on left hand side. This means that the above statement is correct.

y = x;

Similarly, the statement y = x is also correct. x is an array of six elements that holds the address of the first element. But we cannot change this address. However we can get that address and store it in some other variable. As y is a pointer variable and lvalue so the above operation is legal. We have dynamically allocated the memory for the array. This memory, after the use, can be released so that other programs can use it. We can use the delete keyword to release the memory. The syntax is:

delete[ ] y;

We are releasing the memory, making it available for use by other programs. We will not do it in case of x array, as ‘new’ was not used for its creation. So it is not our responsibility to delete x.

What is programming

As this course is titled “Introduction to programming”, therefore it is most essential and appropriate to understand what programming really means. Let us first see a widely known definition of programming.

Definition: "A program is a precise sequence of steps to solve a particular problem.”

It means that when we say that we have a program, it actually means that we know about a complete set activities to be performed in a particular order. The purpose of these activities is to solve a given problem.

Alan Perlis, a professor at Yale University, says:

"It goes against the grain of modern education to teach children to program. What fun is there in making plans, acquiring discipline in organizing thoughts, devoting attention to detail and learning to be self-critical? "

It is a sarcastic statement about modern education, and it means that the modern education is not developing critical skills like planning, organizing and paying attention to detail. Practically, in our day to day lives we are constantly planning, organizing and paying attention to fine details (if we want our plans to succeed). And it is also fun to do these activities. For example, for a picnic trip we plan where to go, what to wear, what to take for lunch, organize travel details and have a good time while doing so.

When we talk about computer programming then as Mr. Steve Summit puts it

“At its most basic level, programming a computer simply means telling it what to do, and this vapid-sounding definition is not even a joke. There are no other truly fundamental aspects of computer programming; everything else we talk about will simply be the details of a particular, usually artificial, mechanism for telling a computer what to do. Sometimes these mechanisms are chosen because they have been found to be convenient for programmers (people) to use; other times they have been chosen because they're easy for the computer to understand. The first hard thing about programming is to learn, become comfortable with, and accept these artificial mechanisms, whether they make ``sense'' to you or not. “

Goals of this Course

Reinforce the concept that costs and benefits exist for every data structure. We will learn this with practice.

Learn the commonly used data structures. These form a programmer's basic data structure “toolkit”. In the previous course, you have learned how to form a loop, functions, use of arrays, classes and how to write programs for different problems. In this course, you will make use of data structures and have a feeling that there is bag full of different data structures. In case of some problem, you will get a data structure from the toolkit and use some suitable data structure.

Understand how to measure the cost of a data structure or program. These techniques also allow you to judge the merits of new data structures that you or others might develop. At times, you may have two suitable data structures for some problem. These can be tried one by one to adjudge which one is better one. How can you decide which data structure is better than other. Firstly, a programmer can do it by writing two programs using different data structure while solving the same problem. Now execute both data structures. One gives the result before the other. The data structure that gives results first is better than the other one. But sometimes, the data grows too large in the problem. Suppose we want to solve some problem having names and the data of names grows to10 lakhs (one million). Now when you run both programs, the second program runs faster. What does it mean? Is the data structure used in program one not correct? This is not true. The size of the data, being manipulated in the program can grow or shrink. You will also see that some data structures are good for small data while the others may suit to huge data. But the problem is how can we determine that the data in future will increase or decrease. We should have some way to take decision in this regard. In this course we will do some mathematical analysis and see which data structure is better one.