C# Data Structures and Algorithms

As a developer, you have certainly heard about many programming languages, such as C#, Java, C++, C, PHP, or Ruby. In all of them, you can use various data structures, as well as implement algorithms, to solve both basic and complex problems. However, each language has its own specificity, which could be visible while implementing data structures and accompanying algorithms. As already mentioned, this book will focus only on the C# programming language, which is also the main topic of this section.

The C# language, pronounced as "C Sharp", is a modern, general-purpose, strongly-typed, and object-oriented programming language that can be used while developing a wide range of applications, such as web, mobile, desktop, distributed, and embedded solutions, as well as even games. It cooperates with various additional technologies and platforms, including ASP.NET MVC, Windows Store, Xamarin, Windows Forms, XAML, and Unity. Therefore, when you learn the C# language, as well as getting to know more about data structures and algorithms in the context of this programming language, you can use such skills to create more than one particular type of software.

The current version of the language is C# 7.1. It is worth mentioning its interesting history with the following versions of the language (for example, 2.0, 3.0, and 5.0) in which new features have been added to increase language possibilities and to simplify the work of developers. When you take a look at release notes for particular versions, you will see how the language is being improved and expanded over time.

The syntax of the C# programming language is similar to other languages, such as Java or C++. For this reason, if you know such languages, you should quite easily be able to understand the code written in C#. As an example, similarly as in the languages mentioned previously, the code consists of statements that end with semicolons (;), and curly brackets ({ and }) are used to group statements, such as within the foreach loop. You could also find similar code constructions, such as the if statement, or while and for loops.

Developing various applications in the C# language is also simplified by the availability of many additional great features, such as Language Integrated Query (LINQ), which allows developers to get data from various collections, such as SQL databases or XML documents, in a consistent way. There are also some approaches to shorten the required code, such as using lambda expressions, expression-bodied members, getters and setters, or string interpolation. It is worth mentioning the automatic garbage collection that simplifies the task of releasing memory. Of course, the solutions mentioned are only the very limited subset of features available while developing in C#. You will see some others in the following parts of this book, together with examples and detailed descriptions.

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.

int number; 

number = 500; 

int number = 500; 

const int DAYS_IN_WEEK = 7; 

enum Language { PL, EN, DE }; 

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

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

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

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

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

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); 
    } 
} 

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

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

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); 
} 

While reading the book, you will see many examples presenting data structures and algorithms, together with detailed descriptions. The most important parts of the code will be shown directly in the book. Moreover, complete source code will be available to download. Of course, you can only read the code from the book, but it is strongly recommended to write such code on your own, and then launch and debug the program to understand how various data structures and algorithms operate.

As already mentioned, the examples shown in the book will be prepared in the C# language. To keep things simple, the console-based applications will be created, but such data structures could be used in other kinds of solutions as well.

The example projects will be created in Microsoft Visual Studio 2017 Community. This Integrated Development Environment (IDE) is a comprehensive solution for developing various kinds of projects. To download, install, and configure it, you should:

Just after launching the IDE, let's proceed by creating a new project. Such a process will be performed many times while reading the book to create the example applications according to information provided in particular chapters.

To create a new project:

Congratulations, you have just created the first project! But what is inside?

Let's take a look at the Solution Explorer window, which presents the structure of the project. It is worth mentioning that the project is included in the solution with the same name. Of course, a solution could contain more than one project, which is a common scenario while developing more complex applications.

The automatically generated project (named GettingStarted) has the following structure:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 
 
namespace GettingStarted 
{ 
    class Program 
    { 
        static void Main(string[] args) 
        { 
        } 
    } 
} 

The initial content of the Program.cs file contains the definition of the Program class within the GettingStarted namespace. The class contains the Main static method, which is called automatically when the application is launched. The five using statements are included as well, namely System, System.Collections.Generic, System.Linq, System.Text, and System.Threading.Tasks.

Before proceeding, let's take a look at the structure of the project in the file explorer, not in the Solution Explorer window. Are such structures exactly the same?

First of all, you can see the bin and obj directories, which are generated automatically. Both contain Debug and Release directories, whose names are related to the configuration set in the IDE. After building the project, a subdirectory of the bin directory (that is, Debug or Release) contains .exe, .exe.config, and .pdb files, while the subdirectory in the obj directory—for example—contains .cache and some temporary .cs files. What's more, there is no References directory, but there are .csproj and .csproj.user files with XML-based configurations of the project. Similarly, the solution-based .sln configuration file is located in the solution's directory.

If you want to learn how to write some example code, as well as launch and debug the program, let's proceed to the next section.

Many examples shown in the following part of the book will require interaction with the user, especially by reading input data and showing output. You can easily add such features to the application, as explained in this section.

string fullName = Console.ReadLine(); 

string numberString = Console.ReadLine(); 
int.TryParse(numberString, out int number); 

string dateTimeString = Console.ReadLine(); 
if (!DateTime.TryParseExact( 
    dateTimeString, 
    "M/d/yyyy HH:mm", 
    new CultureInfo("en-US"), 
    DateTimeStyles.None, 
    out DateTime dateTime)) 
{ 
    dateTime = DateTime.Now; 
} 

ConsoleKeyInfo key = Console.ReadKey(); 
switch (key.Key) 
{ 
    case ConsoleKey.S: /* Pressed S */ break; 
    case ConsoleKey.F1: /* Pressed F1 */ break; 
    case ConsoleKey.Escape: /* Pressed Escape */ break; 
} 

Console.Write("Enter a name: "); 

Enter a name:

Console.WriteLine("Hello!"); 

Hello!

string name = "Marcin"; 
Console.WriteLine("Hello, {0}!", name); 

Hello, Marcin!

string tableNumber = "A100"; 
int peopleCount = 4; 
DateTime reservationDateTime = new DateTime( 
    2017, 10, 28, 11, 0, 0); 
CultureInfo cultureInfo = new CultureInfo("en-US"); 
Console.WriteLine( 
    "Table {0} has been booked for {1} people on {2} at {3}", 
    tableNumber, 
    peopleCount, 
    reservationDateTime.ToString("M/d/yyyy", cultureInfo), 
    reservationDateTime.ToString("HH:mm", cultureInfo)); 

Table A100 has been booked for 4 people on 10/28/2017 at 11:00

using System; 
using System.Globalization; 
 
namespace GettingStarted 
{ 
    class Program 
    { 
        static void Main(string[] args) 
        { 
            CultureInfo cultureInfo = new CultureInfo("en-US"); 
 
            Console.Write("The table number: "); 
            string table = Console.ReadLine(); 
 
            Console.Write("The number of people: "); 
            string countString = Console.ReadLine(); 
            int.TryParse(countString, out int count); 
 
            Console.Write("The reservation date (MM/dd/yyyy): "); 
            string dateTimeString = Console.ReadLine(); 
            if (!DateTime.TryParseExact( 
                dateTimeString, 
                "M/d/yyyy HH:mm", 
                cultureInfo, 
                DateTimeStyles.None, 
                out DateTime dateTime)) 
            { 
                dateTime = DateTime.Now; 
            } 
 
            Console.WriteLine( 
                "Table {0} has been booked for {1} people on {2}  
                 at {3}", 
                table, 
                count, 
                dateTime.ToString("M/d/yyyy", cultureInfo), 
                dateTime.ToString("HH:mm", cultureInfo)); 
        } 
    } 
} 

The table number: A100The number of people: 4The reservation date (MM/dd/yyyy): 10/28/2017 11:00Table A100 has been booked for 4 people on 10/28/2017 at 11:00Press any key to continue . . . 

Unfortunately, the written code doesn't always work as expected. In such a case, it is a good idea to start debugging to see how the program operates, find the source of the problem, and correct it. This task is especially useful for complex algorithms, where the flow could be complicated, and therefore quite difficult to analyze just by reading the code. Fortunately, the IDE is equipped with various features for debugging that will be presented in this section.

First of all, let's launch the application to see it in action! To do so, you just need to select a proper configuration from the drop-down list (Debug, in this example) and click on the button with the green triangle and the Start caption in the main toolbar, or press F5. To stop debugging, you can choose Debug | Stop Debugging or press Shift + F5.

As already mentioned, there are various debugging techniques, but let's start with breakpoint-based debugging, since it is one of the most common approaches offering huge opportunities. You can place a breakpoint in any line of the code. The program will stop as soon as the line is reached, before executing it. Then, you can see the values of particular variables to check whether the application works as expected.

To add a breakpoint, you can either click on the left-hand margin (next to the line on which the breakpoint should be placed) or place the cursor on the line (where the breakpoint should be added) and press the F9 key. In both cases, the red circle will be shown, as well as the code from the given line will be marked with a red background, as shown in line 17 in the following screenshot:

When a line with the breakpoint is reached while executing the program, it stops, and the line is marked with the yellow background and the margin icon changes, as shown in line 15 in the screenshot. Now, you can check the value of the variable by simply moving the cursor over its name. The current value will appear in the ToolTip.

You can also click on the pin icon located on the right-hand side of the ToolTip to pin it in the editor. Its value will then be visible without the necessity of moving the cursor over the name of the variable. Such a value will be automatically refreshed as soon as it has changed. The result is presented in the following screenshot.

The IDE could adjust its appearance and features depending on the operations performed currently. For example, while debugging, you have access to some special windows, such as Locals, Call Stack, and Diagnostic Tools. The first shows available local variables together with their types and values. The Call Stack window presents information about the following called methods. The last one (namely Diagnostic Tools) shows information about memory and CPU usage, as well as events.

Moreover, the IDE supports conditional breakpoints that stop execution of the program only if the associated Boolean expression is evaluated to true. You can add a condition to a given breakpoint by choosing the Conditions option from the context menu, which is shown after right-clicking on the breakpoint icon in the left-hand margin. Then, the Breakpoint Settings window appears, where you should check the Conditions checkbox and specify the Conditional Expression, such as the one shown in the following screenshot. In the example, execution will stop only when the value of the count variable is greater than 5, that is, count > 5:

When the execution is stopped, you can use the step-by-step debugging technique. To move execution of the program to the next line (without incorporating another breakpoint), you can click on the Step Over icon in the main toolbar or press F10. If you want to step into the method, which is called in the line where the execution has stopped, just click on the Step Into button or press F11. Of course, you can also go to the next breakpoint by clicking on the Continue button or by pressing F5.

The next interesting feature, available in the IDE, is called Immediate Window. It allows developers to execute various expressions when the program execution is stopped using the current values of the variables. You just need to enter an expression in the Immediate Window and press the Enter key. The example is shown in the following screenshot:

Here, the lower-case version of the table number is returned by executingtable.ToLower(). Then, the total number of minutes between the current date and the dateTimevariable is calculated and shown in the window.

This was only the first chapter of the book, but it contained quite a lot of information that will be useful while reading the remaining ones. At the beginning, you saw that using proper data structures and algorithms is not an easy task, but could have a significant impact on the performance of the developed solution. Then, the C# programming language was briefly presented with a focus on showing various data types, both value and reference ones. Classes, interfaces, and delegates were also described.

In the following part of the chapter, the process of installation and configuration of the IDE was presented. Then, you learned how to create a new project, and its structure has been described in details. Next, you saw how to read data from the standard input stream, as well as how to write data to the standard output stream. The read- and write-related operations were also mixed into one example.

At the end of the chapter, you saw how to run the example program, as well as how to debug it using breakpoints and step-by-step debugging to find the source of the problem. What's more, you learned the possibilities of the Immediate Window feature.

After this introduction, you should be ready to proceed to the next chapter and see how to use arrays and lists, as well as accompanying algorithms. Let's go!