-->

Sunday, February 8, 2015

Implementation of STACK using Linked List in C language

Implementation of STACK using Linked List

             To implement the STACK using Linked List, the Linked List itself is created in different manner. In this case instead of ROOT in normal Linked List, an external pointer TOP is used to point all the time to the just added node.
      Initially when the STACK is empty TOP points to a NULL address.

When the PUSH operation is to be done, a NEW node is created and TOP is made point to it. Suppose for the first time one PUSH operation is done. The linked list is shown below:

When again another ITEM is PUSHed, a NEW node is created and the address of the node pointer by TOP, is copied in the LINK field of NEW node the TOP is made point to the NEW node. The Linked List is as below:
When again another item is to be PUSHed it is done similarly. After the PUSH of one more ITEM the Linked List is as shown below:
So, the Linked List created as STACK can be graphically shown as below:
While deletion, POPping is to be done from the STACK, TOP is checked. If it is NULL then the STACK is empty and ‘underflow’ occurs otherwise the ITEM of the node pointed by TOP can be copied in a variable and TOP is updated by link of TOP. Then ITEM is returned.
                      In the above-created STACK, if the POP operation is done once, the Linked List can be shown as below:







Standard streams in C language

A stream is nothing but a collection or sequence of bytes that is moved from main memory and I/O devices. The standard streams in ‘C’ are predefined streams. They are automatically opened whenever the program is executed. When the “main()” function of a C program is invoked, it already has predefined streams open and available for use. Two of these streams represent the standard input and output channels that will be opened for the transfer of data in the form of bytes. These streams are declared in the header file ‘stdio.h’. in total there are FIVE standard streams available, which are:

stdin : the standard input stream, which is the normal source of input for the program. The stream of data is transferred from standard input device like ‘keyboard’ to main memory referred in the form of variables.

stdout :  the standard output stream, which is used for normal output from the program. The stream of data is transferred from main memory referred in the form of variables to the output device like ‘monitor’.

stderr:  the standard error stream, which is used to output error messages and diagnostics from the program.

stdaux : the standard auxiliary device stream, which is used for the connected secondary devices.

stdprn : the standard printer stream, which is used for printing the data in the form hard copy from the program. The data is printed on die attached printer.

In the GNU system the shell provides the pipe and redirection facilities. With the help of these facilities the streams using the files and processes are specified. Most of the other operating systems also provide the similar mechanisms, but the details of usage may vary.

In the GNU C library, ' stdin', ‘stdout', and ' stderr' are normal variables which you can set just like others. For example, to redirect the standard output to a file, you could do:

fclose (stdout);

stdout = fopen (“output_file”, “w”);

Note however that in other systems ' stdin', ‘stdout', and ' stderr' are macros and cannot be assigned to any file in the normal way. But the function ' freopen ()' can be used to get the of closing one file and reopening another file.

C language: Implementation of STACK Using one-dimensional ARRAY

To implement the STACK, a simple one-dimensional array can be used. The size the array is the size of the STACK. Instead of using the normal index to access the elements of the array a special index TOP is used to access the individual elements of the array. Initially TOP is stored with 0, considering the lower bound of array as 1. If the lower bound of the array is other than 1, suppose say LB, then LB-1, may be used as TOP value. STACK may be treated as name of the array.

           If any insertion, PUSH is to be done on the STACK, TOP is incremented by one and the element is stored at TOP i.e. TOP<--TOP+1 and STACK [TOP]<--ITEM, ITEM is the item to be inserted by 1 and the ITEM is placed at TOP. While PUSHing the ITEM the TOP is checked for size, if the TOP is equal to the STACK size N, then no more PUSH operations are possible, the STACK is full. The ‘overflow’ occurs.
  If any deletion, POP, is to be done from the STACK, the item pointed by TOP is stored in a variable, and the TOP is decremented by 1 and the variable is returned. Similarly further POP operations are done. While POPping the STACK is empty and ‘underflow’, occurs.

                To implement the STACK using one-dimensional array the following PUSH and POP operations’ algorithms are used.

Algorithm for PUSH:

           PUSH (STACK,TOP,N,ITEM)
           [STACK is name of the array, ITEM is the data to be PUSHed, TOP is the current index of                        STACK and N is the size of STACK]
           If TOP=N Then;
            write: ’Overflow’; Exit.
           [End of If]
           TOP<--TOP+1
           STACK[TOP]<--ITEM
           Exit.

Function in C to implement PUSH operation:

    void push (int stack[],int n,int *top, int item)
    {
      if(top= =n-1)
       {
         printf(“Over flow”); exit(0);
        }
     top++; stack[top]=item;
    }

Algorithm for POP operation:

     POP (STACK, TOP)
     [STACK is name of the array and TOP is the current index]
     If TOP=O Then;
      Write: ’Underflow’; Exit.
     [End of If]
     ITEM<--STACK[TOP]
     TOP<--TOP-1
     Return ITEM
     Exit.

Function in C to implement POP operation:

     int pop (int stack[], int *top)
     {
       int item;
       if(top= =1)
         {
           printf(“Under flow”);
           exit(0);
           }
       item=stack[top];
       top--;
       return item;
     }

Opening and closing a file in C language

Opening a file

As discussed earlier whenever the file manipulation is to be performed the logical file is attached to the physical file. It means the file pointer holds the address of physical file. This can be achieved by means of opening a file. This operation is also called as linking a logical file with physical file. The fopen() function is used to link the logical file with that of physical file.

The file is opened to perform read/write operations on it and it is promptly closed to indicate the completion of the desired read/write operations.

The syntax of the function fopen() is as follows:

filepointervariable = fopen(“physicalfilename”,”openingmode”);

Here, filepointervariable represents a pointer variable of FILE data type. Physicalfilename represents a name of the  physical file (a string variable or constant). Openingmode represents one of the available modes (a string constant).
The filepointervariable may be any of the file pointers as discussed in the earlier article. The physicalfilename is a string constant or a variable used to represent name of the physical file. The file may be an existing one or a new one that is to be created. The write operations can be performed on any new file and both read/write operations can be performed on an existing file. The openingmode is also a string constant that indicates the operations to be performed on new or existing file.

The following table provides the list of file opening modes available which are used as string constants like “m” where m is the mode:
table provides the list of file opening modes

The Following table provides the "flags" of the streams (which are defined in FILE structure)
table provides the "flags" of the streams

Consider the following declaration and file opening statement:
 FILE *fpl;

fpl=fopen(“physicalfilename”,”openingmode”);

The fopen() function links the logical file ‘fpl’ with the physical file ‘physicalfilename’. The 'openingmode’ indicates the operation mode as per the table shown above. One of them is selected as per the requirements. If the file is created for the first time then either “w” or “a” can be selected. When the data to be transferred is in binary format the mode “wb” or “ab” can be selected.

 The header file ’stdio.h’ contains declarations for the file I/O and should always be included at the very beginning of C programs that use ‘data files’. The constants such as EOF, NULL, etc. are also defined in ’stdio.h’. If the physical file mentioned is successfully opened then the logical file is linked with it otherwise the function fopen() returns NULL. This NULL value helps in testing the successful  opening of any physical file for the respective operation. In case of failure to open the file, proper error message can be displayed indicating “file opening error” may be along with the filename.

Consider another statement like: fp = fopen(“prog.c”, “r”);

Here “prog.c” is the physical file that is opened. It is opened in ‘read’ mode. So, the above statement opens a file called “prog.c” (a physical file) for reading and associates the file pointer fp(logical file) with it. Note here that the file opened is a text file. If the file “prog.c” exists then it is  successfully opened and a valid address is stored in “fp” otherwise a NULL is stored in the file pointer “fp”. In such case an error can he reported like:
if(fp = NULL)

{

printf(“Error in opening the file..");
 exit(l);

}

If “emp.dat” file is to be created for the first time and the data is to be written in binary format then the statement used to do so is:
 fp = fopen( “emp.dat”, “wb”) ;

By chance if the file “emp.dat” already exists then the contents of it are erased and the new data is transferred after every write operation. To retain the data and write the data at the end the file opening mode is changed like:

fp = fopen( “emp.dat”, “ab”) ;

Once the file is open in the respective mode then it is ready for either input (read) or output (write) or append (write at the end) operation.

Closing a file


As discussed earlier the file is opened for input or output operations. After either of the operations it is required to close the opened file to ensure the detachment of physical file. Of course this detachment is done automatically by the system when the program execution is over. To ensure the completeness of the program every programmer must close the opened file in the file handling programs. In order to reuse the file pointer variable declared, to open another file, it is must to close the earlier physical file that is already attached. The closing of file is basically related to closing the logical file that indirectly closes the physical file for I/O operations.

To close a file simply the function fclose(filepointer) is used with the file pointer as the parameter to close a single file. If more than one files are to be closed at a time then the function fcloseall() is used without any parameters.

You can open a file for writing, close it, and reopen it for reading, then close it, and open it again for appending, etc. Each time you open it, you could use the same file pointer. Of course it is the better way of using same file pointer all the time. If more than one file is simultaneously to be operated then different file pointers are required. The file pointer is simply a tool that you use to point to a file and you decide what file it will point to.

The following statements show the usage of the functions used for closing the files:
 FILE *fpl;

fp 1 =fopen(“emp.dat”,”w”); /* the logical file fpl linked to physical file emp.dat in WRITE mode */
................
 /* Write operations on the file*/
 ................

fclose(fpl); /* The file is closed */
 fpl=fopen(“trans.dat”,”r”); /* the logical file fpl linked to physical file trans.dat in READ mode */
 .....................
/* Read operations on the file*/
......................
fclose(fpl); /* The file is closed */

In the above description the logical file fpl is closed before linking it with another physical file.

In the next description more than one file pointer usage and fcloseall() to close all the opened files simultaneously can be observed.

 FILE *fpl, *fp2, *fp3;

fp1 =fopen(“emp.dat”,”a”); /* the logical file fpl linked to physical file emp.dat in APPEND mode*/
fp2=fopen(“transl.dat”,”r”); /* the logical file fp2 linked to physical file transl.dat in READ mode*/
fp3=fopen(“trans2.daf","r”); /* the logical file fp3 linked to physical file trans2.dat in READ mode*/
....................

/* Simultaneously Read operations on the files fp2 and fp3 and Write operations on the file fp4 */
....................

fcloseall(); /* all the three files are closed at a time */

The observation from above two descriptions provide the usage of the parameter in flcose() and non-usage in fcloseall().

Operation on Linked List for Data Structure in C Language

Operation on Linked List

Traversing: To visit all the node of a linked list, start from the ROOT and visit first element and from the first element with the help of link field visit the second element, similarly visit all the element till the last node. The last node is recognized by a NULL address in it link field. So, set a pointer variable PTR with ROOT. Process PTRINFO and update PTR by LINK of PTR i.e. PTRPTRLINK. Repeat till the PTR is NULL. The algorithm is as follow:

                    TRAVERSELL(ROOT)
                    [ROOT points to first node’s address of Linked List]
                    PTR<--ROOT
                    Repeat While PTR< >NULL
                      Apply process to PTR-->INFO
                      PTR<--PTR-->LINK
                    [End of while]
                    Exit.
Algorithm to print the contents of a linked list:
                   TRAVERSELL(ROOT)
                   [ROOT points to first node’s address of Linked List]
                   PTR<--ROOT
                   Repeat While PTR< >NULL
                     Write: PTR-->INFO
                     PTR<--PTR-->LINK
                   [End of while]
                   Exit
Recursive Algorithm to traverse a linked list:
                   REC_TRAV (ROOT)
                   [ROOT points to first node’s address of Linked List]
                   IfROOT< >NULL
                      Apply process to PTR-->INFO
                      REC_TRAV(ROOT-->LINK)
                  [End of it]
                  Eixt.

Searching: Searching is nothing but finding a node with the given information for the presence. If it is present search is successful otherwise unsuccessful. Only Linear Search is used to apply the  searching. Searching almost resembles Traversing except that if search is successful traversing is terminated otherwise the linked list is traversed till the end.  

      So, in order to do searching, get the information to be searching and set PTR with ROOT. Compare Information with INFO of PTR, if it is equal ‘search is successful’ and terminate traversing otherwise update PTR with LINK and repeat the process. Continue the operation till the end. The end is recognized by a NULL of PTR.

Algorithm for Searching:
              SEARCHLL (ROOT, IN)
               [IN is Information to search in Linked List]
               PTR<--ROOT
               Repeat While PTR< >NULL AND IN< >PTR-->INFO
                 PTR<--PTR-->LINK
              [End of while]
              If PTR-->INFO=IN Then:
                Write: ‘Search Successful’
              Else:
                Write: ‘Search Unsuccessful’
             [End of If]
             Exit.

Insertion: Adding a new node the linked list is called as Insertion. To insert a node in the linked list, first a NEW node is created. To create a NEW node, memory is requested and the memory is allocated dynamically from free pool. So NEW is made point to AVAIL and AVAIL is updated. To insert a node two situations arise. The list may be a non-ordered or an ordered non-empty linked list.

If the Linked List is non-ordered list, to insert a NEW node, an Information of a node after which the insertion is to be made is given. So that Information is compared with every node of the list for equality, and the location LOC is found. After finding the LOC, LINK of LOC is copied to the LINK of NEW  node and LINK of NEW node and LINK of LOC is copied with NEW i.e.
NEW-->LINK<--LOC-->LINK and LOC-->LINK<--NEW.

If the Linked List is an ordered list, to insert a NEW node, the Information of NEW node is compared with   the Information of every node of the list. When the Information of the node of the list is greater, it is the     location LOC. The NEW  node is to be placed at that LOC.So in this case a TEMP variable is used to store the previous node’s address so that LINK of TEMP gives LOC. Now to insert the node, LINK of  NEW is copied with LOC and LINK of TEMP is copied with NEW. i.e.
 NEW-->LINK<--LOC and TEMP-->LINK<--NEW.

Array Classification in C Language with Declaration

Array in computer programming is used to store data items in a list, that may of any type. The array can be classified based on how the data items are arranged for human understanding. We have discussed about the concept of array, in this article we will classify an array.

The following figure shows the classification of the array:

Single dimensional arrays

A single dimensional array (also called one dimensional array) is a linear list consisting of related and similar data items. In memory, all the data items are stored in contiguous memory locations one after the other. Pictorial representation of single dimensional array is shown below:


Here, all the items are arranged in a row. It is called 'row major' arrangement. Instead, they can also be arranged column wise. It is called 'column major' arrangement. The memory requirement for the array depends on the type of data items stored and number of items. Let us assume, data items are of type int and assume that int takes 2 bytes (in majority of PCs size of integer will be 4 or 8 bytes). Since 5 elements are stored and the size of int is 2 bytes, the memory required for the array is 10 bytes. If the size of integer is 4 bytes, the array uses 40 bytes of memory and so on in general

Memory for array – n * sizeof (data type)

Where

  •  is the number of data items
  • data type  the data type of data items

An array has the following basic properties:

  • The data items (called elements) stored in the array should be of the same data type. The data items are stored contiguously in memory with subscript of the first item always 0 (zero).
  • Each data item is accessed using the same name long with different subscript.
  • The subscript or index of the array is always an integer.

Declaration of single dimensional arrays:

We know that all the variables are declared before they are used in the program. Similarly, an array must be declared before it is used. During declaration, the size of the array has to specify. The size used during declaration of the array informs the compiler to allocate and reserve the specified memory locations. A single dimensional array in C can be declared using the following syntax:

data_typearray_name[expression];

where

  • data_type – can be a basic data type such as int, float, char, etc.
  • array_name – is the name of the array
  • expression – should be evaluated to a positive integer only. It can also be an integer constant. The expression should be enclosed within square brackets ‘[]’.

Note: Expression such as 10 or 10+2 is allowed. No variables are allowed in expression, for example, 10+b is not allowed because b is a variable.

For example, consider the following declaration statement: int arr[10];
The compiler reserves 10 locations (i.e. 2 *10 bytes) for the array arr. In each of the location we can store an integer value. The memory allocated by the compiler is, pictorially represented as:


How to Perform Array Initialization in C language

After declaration of arrays, the process of initialization starts in computer programming. Array initialization in C may be perform in many ways will be discuss in this article. C programming provides to let the programmer initialize the array to specific values when it is declared, when it is required or etc. Each option have its own examples described in the article.

How to Perform Array Initialization in Computer Programming: C

Initialization of all specified locations

Arrays can be initialized at the same time of declaration when their initial values are known in advance. Array elements can be initialized with data items of type int, char, float, etc.

int arr[5] = {15, 45, 85, 96, 69};

During compilation, 5 contiguous memory locations are reserved by the compiler for the array arr and all these locations are initialized as shown below:

How to Perform Array Initialization in Computer Programming: C

If the size of an integer is 2 bytes, 10 bytes will be allocated for the array arr. Lets discuss another initialization

int arr[5] = {15, 58, 98, 89, 65, 54, 55, 25, 85};
This declaration will notify an error with a message Number of initial values are more than the size of the array arr

char str[7] = {'P', 'R', 'O', 'G', 'R', 'A', 'M'};

During compilation, 7 contiguous memory locations are reserved by the compiler for the variable str and all these locations are initialized as shown below:

How to Perform Array Initialization in Computer Programming: C

In fact in place of character, ASCII values are stores in the memory. Since a character occupies 1 byte, 8 bytes will be allocated for the variable str.

Partial Array Initialization

C language also provides partial array initialization. If the number of values to be initialized is less than the size of an array, then the elements are initialized in order from 0th location. The remaining locations will be initialized to zero automatically. For example, consider the partial initialization shown below:

int arr[5] = {56, 76, 98};

Even though compiler allocates 5 memory locations, using this declaration statement, the compiler initialized first three locations with 56, 76 and 98. The next set of memory location are automatically initialized to 0's by the compiler as shown below:

How to Perform Array Initialization in Computer Programming: C

Initialization without Size

Consider the declaration along with initialization shown below:
char str[] = {'P', 'R', 'O', 'G', 'R', 'A', 'M'};

In this declaration, even though we have not specified exact number of elements to be used in array str, the array size will be set to the total number of initial values specified. So, the array size will be set to 7 automatically. The array str is initialized as shown below:

How to Perform Array Initialization in Computer Programming: C

String Initialization

Consider the declaration with string initialization:

char str[] = "PROGRAM";

The array str is initialized as shown below:

How to Perform Array Initialization in Computer Programming: C

Even though the string "PROGRAM" contains 7 characters, because it is a string, it always ends with NULL character '\0'. So, the array size is 8 bytes i.e. string length + 1 byte for NULL character.

char str[8] = "PROGRAM"; is Correct, size of the array is string length + 1 byte for NULL character.
char str[7] = "PROGRAM";  is Wrong, size of the array should be minimum 8.

For string initialization, usually the programmer prefer the following declaration:
char str[] = "PROGRAM";

Reading and Writing Single Dimensional Array
© Copyright 2013 Computer Programming | All Right Reserved