Data Structures And Algorithms - Part Three - An Array Of Fun

Arrays are one of two fundamental data structures in Computer Science. They allow our programs to retain information in memory cells that are contiguous. This means that if the first item of an array is stored in a memory location with the address of 100, the next item in the array will be stored in the memory cell with address 101. Memory cells in a computer are arranged like a grid, a spreadsheet, or something similar. On the other hand, arrays are static, meaning that they cannot grow in size during the running time of a program. Once a length is specified for an array, it can never be changed, which leads us to reach for a different tool called a linked list, but linked lists data structure will be covered in the next article.

Arrays can be one-dimensional, two-dimensional, or n-dimensional, where n > 2. If you have a background in Mathematics, you may be tempted to compare arrays to vectors and matrices, and rightly so. The following paragraphs, then, will explain how to declare an array in C#, and how to retrieve the information in the array. They will also show code with detailed explanations about what the code does.

NOTE

I would like to stop at this point, and encourage you to download the accompanying code for this article. Doing so will get you started with something that you can practice with, and perhaps use for your own programs. Also, throughout this and future articles, software engineering tips will be given, as well as Big-O notation analysis for our programs.

Please be sure to check code comments and review things meticulously, as this will help you understand arrays and future data structures better.

Lastly, since code will be provided in files with a .csx extensions, you may want to either load these C# scripts using the C# REPL, or copy the code straight from the article.

If you do decide to use C# Interactive, please be sure to use the following line of code, replacing \path.csx with the path to the file you unzipped.

#load "\path.csx"

DECLARING ARRAYS

An array has the following syntax in C#:

Type[] arrayName = new Type[] {item1, item2, ...};

This is the easiest form to declare an array; this kind of array is one-dimensional, and can be thought of as a collection of objects lined up from left to right. In our first example, we will develop a simple program that will detect the <p> and </p> HTML tags. The program will then report if the given text is a valid HTML paragraph. This will allow us to see how arrays might be used when writing programs, and their relevance in Computer Science and computers in general. 

// File name: SimpleParser.csx
// Author: Jesus Kevin Morales
// Date Created: 06/09/2017
// Purpose: To store a simple parser for later loading while using the C# REPL.
// Date last modified: 07/08/2017
// Modification history:
// 06/09/2017: Original build;
// 06/09/2017: Added a SimpleParser class with a .Parse method (see member documentation for details).
using System;
/*

*

* Represents a simple parser that showcases the use of the array data structure.

*

*/
public class SimpleParser {
    /*

    Parses a given piece of text.

    Parameter: text: The text to parse.

    Returns: None.

    Preconditions: The string given to this method should not be empty or null, and should contain HTML <p> tags.

    Postconditions: The method will print to the screen.

    This is an O(1) algorithm.

    */
    public static void Parse(string text) {
        // The following line creates an array of strings (HTML tags in this case), with 2 elements.
        // It is an O(1) operation.
        string[] tags = new string[] {
            "<p>",
            "</p>"
        };
        // The following line is also an O(1) operation.
        if (text.StartsWith(tags[0]) && text.EndsWith(tags[1])) {
            Console.Write("\r\rYour paragraph is valid HTML.\r\r");
        }
    }
}

As we can see, the program only searches for the beginning and the end of a string and gives us a native way of checking for valid HTML. However, one might use arrays for a similar kind of program. Next, we will look at two-dimensional arrays but I don't recommend them; they are a source for unreadable code, and bugs as well. (Once you see the syntax, you will be convinced.). Furthermore, these arrays usually require algorithms that are of O(n^2), which we have to avoid at all costs because they take a lot of time to run.

Two-dimensional arrays are declared       as follows: Let arrayName be a two-dimensional array of type int. Then, arrayName is defined as follows, 

int[, ] arrayName = new int[, ] {
    {
        10,
        11
    }, {
        12,
        13
    }, {
        14,
        15
    }
};

To visit each and every one of the items in the array, we would need two loops, one nested within the other, as follows,

for (int i = 0; i < length; i++) {
    for (int j = 0; j < length - 1; j++) {
        // To do code goes here (not recommended that you take this approach.)
    }
}

Jagged arrays are arrays of arrays; in other words, instead of containing objects such as strings or ints, they contain other arrays. Again, it is not recommended that you use these types of arrays in your code directly. These should appear at runtime, when programs are generating these arrays, rather than being coded by the programmer.

One such example of jagged arrays is arrays of strings.

In future articles, we will investigate how to use arrays to develop data structures such as queues, stacks, and regular array lists.