Book Image

C# Data Structures and Algorithms

By : Marcin Jamro
Book Image

C# Data Structures and Algorithms

By: Marcin Jamro

Overview of this book

Data structures allow organizing data efficiently. They are critical to various problems and their suitable implementation can provide a complete solution that acts like reusable code. In this book, you will learn how to use various data structures while developing in the C# language as well as how to implement some of the most common algorithms used with such data structures. At the beginning, you will get to know arrays, lists, dictionaries, and sets together with real-world examples of your application. Then, you will learn how to create and use stacks and queues. In the following part of the book, the more complex data structures will be introduced, namely trees and graphs, together with some algorithms for searching the shortest path in a graph. We will also discuss how to organize the code in a manageable, consistent, and extendable way. By the end of the book,you will learn how to build components that are easy to understand, debug, and use in different applications.
Table of Contents (14 chapters)

Data types


While developing applications in the C# language, you could use various data types, which are divided into two groups, namely value types and reference types. The difference between them is very simple—a variable of a value type directly contains data, while a variable of a reference type just stores a reference to data, as shown as follows:

As you can see, a Value type stores its actual Value directly in the Stack memory, while a Reference type only stores a Reference here. The actual value is located in the Heap memory. Therefore, it is also possible to have two or more variables of a reference type that reference exactly the same value.

Of course, a difference between value and reference types is very important while programming and you should know which types belong to the groups mentioned. Otherwise, you could make mistakes in the code that could be quite difficult to find. For instance, you should remember to take care while updating the data of a reference type, because the change could also be reflected in other variables that are referencing the same object. Moreover, you should be careful while comparing two objects with the equals (=) operator, because you could compare the reference, not the data itself, in the case of two instances of a reference type.

Note

The C# language also supports pointer types, which can be declared as type* identifier or void* identifier. However, such types are beyond the scope of this book. You can read more about them at: https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/unsafe-code-pointers/pointer-types.

Value types

To give you a better understanding of data types, let's start with the analysis of the first group (that is, value types), which could be further divided into structs and enumerations.

Structs

Within structs, you have access to many built-in types, which could be used either as keywords or types from the System namespace.

One of them is the Boolean type (the bool keyword), which makes it possible to store a logical value, that is, one of two values, namely true or false.

As for storing integer values, you can use one of the following types: Byte (the byte keyword), SByte (sbyte), Int16 (short), UInt16 (ushort), Int32 (int), UInt32 (uint), Int64 (long), and UInt64 (ulong). They differ by the number of bytes for storing values and therefore by the range of available values. As an example, the short data type supports values in the range from -32,768 to 32,767 while uint supports values in the range from 0 to 4,294,967,295. Another type within the integral types is Char (char), which represents a single Unicode character such as 'a' or 'M'.

In the case of floating-point values, you can use two types, namely Single (float) and Double (double). The first uses 32 bits, while the second uses 64 bits. Thus, their precision differs significantly.

What's more, the Decimal type (the decimal keyword) is available. It uses 128 bits and is a good choice for monetary calculations.

An example declaration of a variable in the C# programming language is as follows:

int number; 

You can assign a value to a variable using the equals sign (=), shown as follows:

number = 500; 

Of course, declaration and assignment could be performed in the same line:

int number = 500; 

If you want to declare and initialize an immutable value, that is, a constant, you can use the const keyword, as shown in the following line of code:

const int DAYS_IN_WEEK = 7; 

Note

More information about the built-in data types, together with the complete list of ranges, is available at: https://msdn.microsoft.com/library/cs7y5x0x.aspx.

Enumerations

Apart from structs, the value types contain enumerations. Each has a set of named constants to specify the available set of values. For instance, you can create the enumeration for available languages or supported currencies. An example definition is as follows:

enum Language { PL, EN, DE }; 

Then, you can use the defined enumeration as a data type, as shown as follows:

Language language = Language.PL; 
switch (language) 
{ 
    case Language.PL: /* Polish version */ break; 
    case Language.DE: /* German version */ break; 
    default: /* English version */ break; 
} 

It is worth mentioning that enumerations allow you to replace some magical strings (such as "PL" or "DE") with constant values and this has a positive impact on code quality.

Note

You can also benefit from more advanced features of enumerations, such as changing the underlying type or specifying values for particular constants. You can find more information at: https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/enum.

Reference types

The second main group of types is named reference types. Just as a quick reminder, a variable of a reference type does not directly contain data, because it just stores a reference to data. In this group, you can find three built-in types, namely string, object, and dynamic. Moreover, you can declare classes, interfaces, and delegates.

Note

More information about the reference types is available at: https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/reference-types.

Strings

There is often the necessity to store some text values. You can achieve this goal using the String built-in reference type from the System namespace, which is also available using the string keyword. The string type is a sequence of Unicode characters. It can have zero chars, one or more chars, or the string variable can be set to null.

You can perform various operations on string objects, such as concatenation or accessing a particular char using the [] operator, as shown as follows:

string firstName = "Marcin", lastName = "Jamro"; 
int year = 1988; 
string note = firstName + " " + lastName.ToUpper()  
   + " was born in " + year; 
string initials = firstName[0] + "." + lastName[0] + "."; 

At the beginning, the firstName variable is declared, and the "Marcin" value is assigned to it. Similarly, "Jamro" is set as a value of the lastName variable. In the third line, you concatenate five strings (using the + operator), namely, the current value of firstName, the space, the current value of lastName converted to the upper-case string (by calling the ToUpper method), the string " was born in ", and the current value of the year variable. In the last line, the first chars from firstName and lastName variables are obtained, using the [] operator, as well as concatenated with two dots to form the initials, that is, M.J., which are stored as a value of the initials variable.

The Format static method could also be used for constructing the string, as follows:

string note = string.Format("{0} {1} was born in {2}",  
   firstName, lastName.ToUpper(), year); 

In this example, you specify the composite format string with three format items, namely the firstName (represented by {0}), upper-case lastName ({1}), and the year ({2}). The objects to format are specified as the following parameters.

It is also worth mentioning the interpolated string, which uses interpolated expressions to construct a string. To create a string using this approach, the $ character should be placed before ", as shown in the following example:

string note = $"{firstName} {lastName.ToUpper()}  
   was born in {year}"; 

Object

The Object class, declared in the System namespace, performs a very important role while developing applications in the C# language because it is the base class for all classes. It means that built-in value types and built-in reference types, as well as user-defined types, are derived from the Object class, which is also available by using the object alias.

As the object type is the base entity for all value types, it means that it is possible to convert a variable of any value type (for example, int or float) to the object type, as well as to convert back a variable of the object type to a specific value type. Such operations are named boxing (the first one) and unboxing (the other). They are shown as follows:

int age = 28; 
object ageBoxing = age; 
int ageUnboxing = (int)ageBoxing; 

Dynamic

Apart from the types already described, the dynamic one is available for developers. It allows the bypassing of type checking during compilation so that you can perform it during the run time. Such a mechanism is useful while accessing some application programming interfaces (APIs), but it will not be used in this book.

Classes

As already mentioned, C# is an object-oriented language and supports declaration of classes together with various members, including constructors, finalizers, constants, fields, properties, indexers, events, methods, and operators, as well as delegates. Moreover, classes support inheritance and implementing interfaces. Static, abstract, and virtual members are available, as well.

An example class is shown as follows:

public class Person 
{ 
    private string _location = string.Empty; 
    public string Name { get; set; } 
    public int Age { get; set; } 
 
    public Person() => Name = "---"; 
 
    public Person(string name, int age) 
    { 
        Name = name; 
        Age = age; 
    } 
 
    public void Relocate(string location) 
    { 
        if (!string.IsNullOrEmpty(location)) 
        { 
            _location = location; 
        } 
    } 
 
    public float GetDistance(string location) 
    { 
        return DistanceHelpers.GetDistance(_location, location); 
    } 
} 

The Person class contains the _location private field with the default value set as the empty string (string.Empty), two public properties (Name and Age), a default constructor that sets a value of the Name property to --- using the expression body definition, an additional constructor that takes two parameters and sets values of properties, the Relocate method that updates the value of the private field, as well as the GetDistance method that calls the GetDistance static method from the DistanceHelpers class and returns the distance between two cities in kilometers.

You can create an instance of the class using the new operator. Then, you can perform various operations on the object created, such as calling a method, as shown as follows:

Person person = new Person("Mary", 20); 
person.Relocate("Rzeszow"); 
float distance = person.GetDistance("Warsaw");  

Interfaces

In the previous section, a class was mentioned that could implement one or more interfaces. It means that such a class must implement all methods, properties, events, and indexers, that are specified in all implemented interfaces. You can easily define interfaces in the C# language using the interface keyword.

As an example, let's take a look at the following code:

public interface IDevice 
{ 
    string Model { get; set; } 
    string Number { get; set; } 
    int Year { get; set; } 
 
    void Configure(DeviceConfiguration configuration); 
    bool Start(); 
    bool Stop(); 
} 

The IDevice interface contains three properties, namely those representing a device model (Model), serial number (Number), and production year (Year). What's more, it has signatures of three methods, which are Configure, Start, and Stop. When a class implements the IDevice interface, it should contain the mentioned properties and methods.

Delegates

The delegate reference type allows specification of the required signature of a method. The delegate could then be instantiated, as well as invoked, as shown in the following code:

delegate double Mean(double a, double b, double c); 
 
static double Harmonic(double a, double b, double c) 
{ 
    return 3 / ((1 / a) + (1 / b) + (1 / c)); 
} 
 
static void Main(string[] args) 
{ 
    Mean arithmetic = (a, b, c) => (a + b + c) / 3; 
    Mean geometric = delegate (double a, double b, double c) 
    { 
        return Math.Pow(a * b * c, 1 / 3.0); 
    }; 
    Mean harmonic = Harmonic; 
    double arithmeticResult = arithmetic.Invoke(5, 6.5, 7); 
    double geometricResult = geometric.Invoke(5, 6.5, 7); 
    double harmonicResult = harmonic.Invoke(5, 6.5, 7); 
} 

In the example, the Mean delegate specifies the required signature of the method for calculating the mean value of three floating-point numbers. It is instantiated with the lambda expression (arithmetic), anonymous method (geometric), and named method (harmonic). Each delegate is invoked by calling the Invoke method.