Showing posts with label Programming. Show all posts
Showing posts with label Programming. Show all posts

June 21, 2015

C program to Read From a File

#include <stdio.h>
#include <stdlib.h>
void main()
{
    FILE *fptr;
    char filename[15];
    char ch;
    printf("Enter the filename to be opened \n");
    scanf("%s", filename);
    /*  open the file for reading */
    fptr = fopen(filename, "r");
    if (fptr == NULL)
    {
        printf("Cannot open file \n");
        exit(0);
    }
    ch = fgetc(fptr);
    while (ch != EOF)
    {
        printf ("%c", ch);
        ch = fgetc(fptr);
    }
    fclose(fptr);
}

C Program to create and write a File

#include<stdio.h>
#include<conio.h>

int main()
{
FILE *fp;
char ch;
fp = fopen("one.txt", "w");
printf("Enter data");
while( (ch = getchar()) != EOF) {
    putc(ch,fp);
}
fclose(fp);

return 0;
}

September 3, 2013

Introduction to 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.

November 13, 2012

Stack implementation through Linked list in C

We can avoid the size limitation of a stack implemented with an array, with the help of a linked list to hold the stack elements. As needed in case of array, we have to decide where to insert elements in the list and where to delete them so that push and pop will run at the fastest. Primarily, there are two operations of a stack; push() and pop(). A stack carries lifo behavior i.e. last in, first out. You know that while implementing stack with an array and to achieve lifo behavior, we used push and pop elements at the end of the array. Instead of pushing and popping elements at the beginning of the array that contains overhead of shifting elements towards right to push an element at the start and shifting elements towards left to pop an element from the start. To avoid this overhead of shifting left and right, we decided to push and pop elements at the end of the array. Now, if we use linked list to implement the stack, where will we push the element inside the list and from where will we pop the element? There are few facts to consider, before we make any decision:
Insertion and removal in stack takes constant time. Singly linked list can serve the purpose. Hence, the decision is to insert the element at the start in the implementation of push operation and remove the element from the start in the pop implementation.
clip_image001
clip_image002
There are two parts of above figure.On the left hand, there is the stack implemented using an array. The elements present inside this stack are 1, 7, 5 and 2. The most recent element of the stack is 1. It may be removed if the pop() is called at this point of time. On the right side, there is the stack implemented using a linked list. This stack has four nodes inside it which are liked in such a fashion that the very first node pointed by the head pointer contains the value 1. This first node with value 1 is pointing to the node with value 7. The node with value 7 is pointing to the node with value 5 while the node with value 5 is pointing to the last node with value 2. To make a stack data strcuture using a linked list, we have inserted new nodes at the start of the linked list.
We are going to implement stack through linked list. Here is the code of stack implementation in C.



#include "stdio.h"
#include "stdlib.h"
#include "conio.h"



void pop();
void push(int value);
void display();


struct node
{
    int data;
    struct node *link;
};

struct node *top=NULL,*temp;

int main()
{
    int choice,data;
  
   
    while(1) //infinite loop is used to insert/delete infinite number of elements in stack
    {
       
        printf("\n1.Push\n2.Pop\n3.Display\n4.Exit\n");
        printf("\nEnter ur choice:");
        scanf("%d",&choice);
        switch(choice)
        {
        case 1:  //To push a new element into stack
           
           
            printf("Enter a new element :");
            scanf("%d",&data);
            push(data);
            break;
           
        case 2: // pop the element from stack
            pop();
            break;
           
        case 3: // Display the stack elements
            display();
            break;
        case 4: // To exit
            exit(0);
        }
       
    }     
getch();
return 0;
}

push(int data)
{
         temp=(struct node *)malloc(sizeof(struct node)); // creating a space for the new element.
         temp->data=data;
            temp->link=top;
            top=temp;
                    
}

pop()
{
            if(top!=NULL)
            {
                printf("The poped element is %d",top->data);
                top=top->link;
            }
            else
            {
                printf("\nStack Underflow");   
            }
           
}

display()
{
         temp=top;
            if(temp==NULL)
            {
                printf("\nStack is empty\n");
            }
           
            while(temp!=NULL)
            {
                printf(" %d ->",temp->data);
                temp=temp->link;
            }
               
}





October 29, 2012

Stack Implementation using array

Lets implement the stack using the arrays. The stack shown in the below diagram may be considered as an array. Here the array is shown vertically. We can implement the stack using array. The interface will remain as push and pop methods. The user of the stack does not need to know that the stack is internally implemented with the help of array. The worst case for insertion and deletion from an array may happen when we insert and delete from the beginning of the array. We have to shift elements to the right for insertion and left for removal of an element. We face the same problem while implementing the list with the use of the array. If we push and pop the elements from the start of the array for stack implementation, this problem will arise. In case of push, we have to shift the stack elements to the right. However, in case of pop, after removing the element, we have to shift the elements of stack that are in the array to the left. If we push the element at the end of the array, there is no need to shift any element. Similarly as the pop method removes the last element of the stack which is at the end of the array, no element is shifted. To insert and remove elements at the end of the array we need not to shift its elements. Best case for insert and delete is at the end of the array where there is no need to shift any element. We should implement push() and pop() by inserting and deleting at the end of an array.
clip_image001

In the above diagram, on the left side we have a stack. There are four elements in the stack i.e. 1, 7, 5 and 2. The element 1 is the extreme-most that means that it is inserted in the end whereas 7, 5, and 2 have been added before. As this is a LIFO structure so the element 1 should be popped first. On the right side we have an array with positions 0, 1, 2, 3 and so on. We have inserted the numbers 2, 5, 7 and 1. We have decided that the elements should be inserted at the end of the array. Therefore the most recent element i.e. 1 is at position 3. The top is the index representing the position of the most recent element. Now we will discuss the stack implementation in detail using array.
We have to choose a maximum size for the array. It is possible that the array may ‘fill-up’ if we push enough elements. Now more elements cannot be pushed. Now what should the user of the stack do? Internally, we have implemented the stack using array which can be full. To avoid this, we write isFull() method that will return a boolean value. If this method returns true, it means that the stack (array) is full and no more elements can be inserted. Therefore before calling the push(x), the user should call isFull() method. If isFull() returns false, it will depict that stack is not full and an element can be inserted. This method has become the part of the stack interface. So we have two more methods in our interface i.e. isEmpty() and isFull().
Now we will discuss the actual C++ code of these operations. These methods are part of stack class or stack factory. We have an array named A while current is its index. The code of pop() method is as:
 
int pop()
{
return A[current--];
}
In this method, the recent element is returned to the caller, reducing the size of the array by 1.
The code of push method is:
void push(int x)
{
A[++current] = x;
}

 
We know that ++current means that add one to the current and then use it. That also shows that element x should be inserted at current plus one position. Here we are not testing that this current index has increased from the array size or not. As discussed earlier that before using the push method, the user must call isFull() method. Similarly it is the responsibility of the user to call the isEmpty() method before calling the pop method. Therefore there is no if statement in the push and pop method.
The code of the top() method is:
 
int top()
{
return A[current];
}
This method returns the element at the current position. We are not changing the value of current here. We simply want to return the top element.
int isEmpty()
{
return ( current == -1 );
}
This method also tests the value of the current whether it is equal to -1 or not. Initially when the stack is created, the value of current will be -1. If the user calls the isEmpty() method before pushing any element, it will return true.
int isFull()
{
return ( current == size-1);
}


This method checks that the stack is full or not. The variable size shows the size of the array. If the current is equal to the size minus one, it means that the stack is full and we cannot insert any element in it.
We have determined the cost and benefit of all the data structures. Now we will see how much time these methods take. A quick examination shows that all the five operations take constant time. In case of list, the find method takes too much time as it has to traverse the list. Whereas the add and remove methods are relatively quick. The methods of stack are very simple. There is no complexity involved. We insert element at one side and also remove from that side not in the middle or some other place. Therefore we need not to carry out a lot of work. During the usage of the array, the stack methods push, pop, top, isFull and isEmpty all are constant time operations. There is not much difference of time between them.
The complete code of the program is:

/* Stack implementation using array */
#include <iostream.h>
/* The Stack class */
class Stack
{
public:
Stack() { size = 10; current = -1;} //constructor
int pop(){ return A[current--];} // The pop function
void push(int x){A[++current] = x;} // The push function
int top(){ return A[current];} // The top function
int isEmpty(){return ( current == -1 );} // Will return true when stack is empty
int isFull(){ return ( current == size-1);} // Will return true when stack is full
private:
int object; // The data element
int current; // Index of the array
int size; // max size of the array
int A[10]; // Array of 10 elements
};
// The main method
int main()
{
Stack stack; // creating a stack object
// pushing the 10 elements to the stack
for(int i = 0; i < 12; i++)
{
if(!stack.isFull()) // checking stack is full or not
stack.push(i); // push the element at the top
else
cout <<"\n Stack is full, can't insert new element";
}
// pop the elements at the stack
for (int i = 0; i < 12; i++)
{
if(!stack.isEmpty()) // checking stack is empty or not
cout << "\n The popped element = " << stack.pop();
else
cout <<"\n Stack is empty, can't pop";
}
}


The output of the program is:
Stack is full, can't insert new element
Stack is full, can't insert new element
The popped element = 9
The popped element = 8
The popped element = 7
The popped element = 6
The popped element = 5
The popped element = 4
The popped element = 3
The popped element = 2
The popped element = 1
The popped element = 0
Stack is empty, can't pop
Stack is empty, can't pop


However, a programmer finds the size-related problems in case of an array. What should we do when the array is full? We can avoid the size limitation of a stack implemented with an array by using a linked list to hold the stack elements.


October 27, 2012

Methods of Linked List

Earlier we discussed the methods of linked list. These methods form the interface of the link list. For further elucidation of these techniques, we will talk about the start method that has the following code.

// position currentNode and lastCurrentNode at first element
void start() {
lastCurrentNode = headNode;
currentNode = headNode;
};


There are two statements in this method. We assign the value of headNode to both lastCurrentNode and currentNode. These two pointers point at different nodes of the list. Here we have pointed both of these pointers at the start of the list. On calling some other method like next, these pointers will move forward. As we can move in the singly-linked list in one direction, these pointers cannot go behind headNode.
We will now see how a node can be removed from the link list. We use the method remove for this purpose.

void remove() {
if( currentNode != NULL && currentNode != headNode) {
(step 1) lastCurrentNode->setNext(currentNode->getNext());
(step 2) delete currentNode;
(step 3) currentNode = lastCurrentNode->getNext();
(step 4) size--;
}
};


clip_image001
 
Suppose that the currentNode is pointing at the location that contains the value 6. A request for the removal of the node is made. Resultantly, the node pointed by currentNode should be removed. For this purpose, at first, the next pointer of the node with value 2 (the node pointed by the lastCurrentNode pointer), that is before the node with value 6, bypasses the node with value 6. It is, now pointing to the node with value 8. The code of the first step is as:

lastCurrentNode->setNext(currentNode->getNext());

What does the statement currentNode->getNext() do? The currentNode is pointing to the node with value 6 while the next of this node is pointing to the node with value 8. That is the next pointer of node with value 6 contains the address of the node with value 8. The statement lastCurrentNode->setNext(currentNode->getNext()) will set the next pointer of the node pointed by the lastCurrentNode to the node with value 8. So the next pointer of the node with value 2 is pointing to the node with value 8.
clip_image002
 
You see that the next pointer of the node having data element 2 contains the address of the node having data element 8. The node with value 6 has been disconnected from the chain while the node with value 2 is connected to the node with the value 8.
The code of the next step is:
delete currentNode;
You already know, in case of allocation of the memory with the help of the new keyword, the delete statement releases this memory which returns the memory to the system. Pictorially it can be represented as:
clip_image003
In the next step, we have moved the currentNode to point the next node. The code is:

currentNode = lastCurrentNode->getNext();

In the fourth step, the size of the list has been reduced by 1 after the deletion of one node i.e.
size--;
clip_image004
The next method is length() that simply returns the size of the list. The code is as follows:

// returns the size of the list
int length()
{
return size;
};
The private data members of the list are:
private:
int size; // contains the size of the list
Node *headNode; // points to the first node of the list
Node *currentNode, // current node
Node *lastCurrentNode; // last current node


The list class completed just now, can be termed as list factory. We have included all the required methods in it. We may employ more methods if required. A programmer can get the size of the list, add or remove nodes in it besides moving the pointers.

Example of list usage
Now let’s see how we use the link list. Here is an example showing the use of list:

/* A simple example showing the use of link list */
#include <iostream>
#include <stdlib.h>
#include "List.cpp" // This contains the definition of List class
// main method
int main(int argc, char *argv[])
{
List list; // creating a list object
// adding values to the list
list.add(5);
list.add(13);
list.add(4);
list.add(8);
list.add(24);
list.add(48);
list.add(12);
// calling the start method of the list
list.start();
// printing all the elements of the list
while (list.next())
cout << "List Element: "<< list.get()<<endl;
}


The output of the program is:

List Element: 5
List Element: 13
List Element: 4
List Element: 8
List Element: 24
List Element: 48
List Element: 12


Let’s discuss the code of the above program. We have included the standard libraries besides having the “List.cpp” file. Usually we do not include .cpp files. Rather, the .h files are included. Whenever you write a class, two files will be created i.e. .h (header file containing the interface of the class) and .cpp (implementation file). Here for the sake of explanation, we have combined the two files into “List.cpp” file. At the start of the main method, we have created a list object as:
List list;
Here the default constructor will be called. If you understand the concept of factory, then it is not difficult to know that we have asked the List factory to create a List object and named it as list. After creating the object, nodes have been added to it. We have added the elements with data values 5, 13, 4, 8, 24, 48 and 12. Later, the start() method of list is called that will position the currentNode and lastCurrentNode at the start of the list. Now there is no need to worry about the implementation of the List. Rather, we will use the interface of the List. So the start method will take us to the start of the list and internally, it may be array or link list or some other implementation. Then there is a while loop that calls the next() method of the List. It moves the pointer ahead and returns a boolean value i.e. true or false. When we reach at the end of the list, the next() method will return false. In the while loop we have a cout statement that prints the value of the list elements, employing the get() method. The loop will continue till the next() method returns true. When the pointers reach at the end of the list the next() will return false. Here the loop will come to an end.
Please keep in mind that list is a very important data structure that will be used in the entire programming courses.

Analysis of Link List
As stated earlier, we will be going to analyze each data structure. We will see whether it is useful or not. We will see its cost and benefit with respect to time and memory. Let us analyze the link list which we have created with the dynamic memory allocation in a chain form.

Add
For the addition purposes, we simply insert the new node after the current node. So ‘add’ is a one-step operation. We insert a new node after the current node in the chain. For this, we have to change two or three pointers while changing the values of some pointer variables. However, there is no need of traversing too much in the list. In case of an array, if we have to add an element in the centre of the array, the space for it is created at first. For this, all the elements that are after the current pointer in the array, should be shifted one place to the right. Suppose if we have to insert the element in the start of the array, all the elements to the right one spot are shifted. However, for the link list, it is not something relevant. In link lists, we can create a new node very easily where the current pointer is pointing. We have to adjust two or three pointers. Its cost, in terms of CPU time or computing time, is not much as compared to the one with the use of arrays.

Remove
Remove is also a one-step operation. The node before and after the node to be removed is connected to each other. Update the current pointer. Then the node to be removed is deleted. As a result, the node to be removed is deleted. Very little work is needed in this case. If you compare it with arrays, for the deletion of an element from the array, space is created. To fill this space, all the right elements are shifted one spot left. If the array size is two thousand or three thousand, we need to run a loop for all these elements to shift them to left.

Find
The worst-case in find is that we may have to search the entire list. In find, we have to search some particular element say x. If found, the currentNode pointer is moved at that node. As there is no order in the list, we have to start search from the beginning of the list. We have to check the value of each node and compare it with x (value to be searched). If found, it returns true and points the currentNode pointer at that node otherwise return false. Suppose that x is not in the list, in this case, we have to search the list from start to end and return false. This is the worst case scenario. Though time gets wasted, yet we find the answer that x is not in the list. If we compare this with array, it will be the same. We don’t know whether x is in the array or not. So we have to search the complete array. In case of finding it, we will remember that position and will return true. What is the average case? x can be found at the first position , in the middle or at the end of the list. So on average, we have to search half of the list.

Back
In the back method, we move the current pointer one position back. Moving the current pointer back, one requires traversing the list from the start until the node whose next pointer points to current node. Our link list is singly linked list i.e. we can move in one direction from start towards end. Suppose our currentNode pointer and lastCurrentNode are somewhere in the middle of the list. Now we want to move one node back. If we have the pointer of lastCurrentNode, it will be easy. We will assign the value of lastCurrentNode to currentNode. But how can we move the lastCurrentNode one step back. We don’t have the pointer of previous node. So the solution for this is to go at the start of the list and traverse the list till the time you reach the node before the lastCurrentNode is pointing. That will be the node whose next pointer contains the value lastCurrentNode. If the currentNode and the lastCurrentNode are at the end of the list, we have to traverse the whole list. Therefore back operation is not a one step operation. We not only need a loop here but also require time.


October 1, 2012

Arrays



Arrays are data structure in which identical data types are stored. The arrays occupy the memory depending upon their size and have contiguous area of memory. We can access the arrays using the array index.


To declare arrays, we have to give their data type, name and size. These are fixed-size arrays. The declaration of arrays is as follows:

data_type    array_name [size] ;


Consider the following program:

void main(  )
{          
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. 
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 cannot 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. 

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 neighbours 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 first 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

C program to Read From a File

#include <stdio.h> #include <stdlib.h> void main() {     FILE *fptr;     char filename[15];     char ch;   ...