Data structures

Processing Sequences of Elements

TABLE OF CONTENTS

  • Array
    • Declaring and Creating Arrays
    • Accessing Array Elements
    • Iterating Over Arrays Using for and For-each loop
  • IList <T>
  • IDictionary<TKey, TValue>

Collections

Collections

  • The .NET Framework provides specialized classes for data storage and retrieval.
  • These classes provide support for stacks, queues, lists, and hash tables.
  • Most collection classes implement the same interfaces, and these interfaces may be inherited to create new collection classes that fit more specialized data storage needs.

Collections (2)

  • A collection is an object that simply allows you to group other objects.
  • When choosing the way you want to group your objects, you first have to think about what you want to do with your objects.
  • The .NET Framework provides specialized classes for data storage and retrieval.
  • These classes provide support for Stacks, Queues, Lists, and Hash Tables.

Array

Declaring and creating Arrays

  • An array is sequence of elements
  • An elements are of the same type
  • The order of elements is fixed
  • Has fixed size (myArray.Length)

Declaring Arrays

  • Declaration defines the type of the elements
  • Square brackets [] mean array
  • Declaring array:

int[] numbers; // declare numbers as an int array of any size
numbers = new int[10];  // numbers is a 10-element array
string[,] names = new string[5,4]; // multidimensional array
byte[][] scores = new byte[5][]; // Array-of-arrays (jagged)
						

Creating Arrays

  • Use the operator new
  • Specify array length
  • Creating (allocating) array of 10 int elements:

Assigning values

Refer to the array elements by index to store values in them

numbers[0] = 58;
numbers[1] = 667;
						
Can create and initialise in a single step:

int[] numbers = {1, 2, 3, 4, 5};
						

Accessing Arrays Elements

  • Arrays elements are accessed using the square brackets operator [] (indexer)
  • Array indexer takes elements's index as parameter
  • The first element has index 0
  • The last element has length-1
  • Arrays elements can be retrieved and changed using the [] operator

Processing Arrays Elements: For loop

  • Use For loop to process an array elements when:
    • Need to keep track of the index
    • Processing is not strickly sequantial from the first to the last element
  • In the loop body use the element at the loop index (array[index])

for (int i = 0; i < arr.Length; i++)
{
    string s = arr[i];
    Console.WriteLine(s);
}
						

Processing Arrays Elements: Foreach loop

  • Used when no indexing is needed
  • All elements are accessd one by one
  • Elements can not be modified (read only)

Processing Arrays Elements: Foreach loop (2)

  • How foreach loop works?
    • type - the type of the element
    • value - local name of variable
    • array - processing array

int[] fibarray = new int[] { 0, 1, 1, 2, 3, 5, 8, 13 };
foreach (int element in fibarray)
{
    System.Console.WriteLine(element);
}
						

IList<T>

Creating a LIST

  • For dynamic lists, the .NET Framework offers the generic class List<T>
  • This class implements the IList, Icollection, IEnumerable, Ilist<T>,Icollection<T>, and Ienmerable<T> interfaces.
  • Adding Elements

List<int> list = new List<int>();
list.Add(2);
list.Add(3);
list.Add(5);
						

Creating a LIST (2)

  • To get the number of elements, use .Count
  • With AddRange() method we can add multiple elements to the collection.
  • Removing elements. You can remove elements from list also, using .RemoveAt(3)
  • To determine whether an element is part of the list, use .Contains(T)

Creating a LIST (3)

  • Clear() – removes all elements
  • Reverse() – reverses the order of the elements in the list or a portion of it
  • Sort() – sorts the elements in the list or a portion of it
  • ToArray() – converts the elements of the list to an array

How It Works?

  • List<T> keeps a buffer memory, allocated in advance, to allow fast Add(T)
  • Most operations use the buffer memory and do not allocate new objects
  • Occasionally the capacity grows (doubles)

IDictionary<TKey, TValue>

Dictionary<TKey, TValue>

  • The abstract data type (ADT) " dictionary " maps key to values
  • The Dictionary structure is like a List<T> structure but the index can be set.
  • Meaning instead of the indecies being automatically generated (0, 1, 2, 3, etc...) they are set by the user and can be of any type.
  • Also known as " map " or " associative array "

Dictionary<TKey, TValue>

  • Contains a set of (key, value) pairs
  • Dictionary ADT operations:
    • Add(key, value)
    • FindByKey(key) -> value
    • >Delete(key)
  • Can be implemented in several ways: List, array, hash table, balanced tree, etc.

Dictionary<TKey, TValue>


Dictionary<string, int> dictionary =
	    new Dictionary<string, int>();

	dictionary.Add("cat", 2);
	dictionary.Add("dog", 1);
	dictionary.Add("llama", 0);
	dictionary.Add("iguana", -1);
						
office@e-dojo.it

EXERCISE

Problem 1: Allocate array

Write a program that allocates array of N integers, initializes each element by its index multiplied by 5 and the prints the obtained array on the console.

Input Output
5 0
5
10
15

EXERCISE (2)

Problem 2: Compare arrays

Write a program that compares two integer arrays element by element.

EXERCISE (3)

Problem 3: Compare arrays

Write a program that finds the length of the maximum sequence of equal elements in an array on N integers.

Input Output
2 1 1 2 3 3 2 2 2 1 3

EXERCISE (4)

Problem 4: Max increasing sequence

Write a program that finds the length og the max increasing sequence in an array of N integers.

Input Output
8 7 3 2 3 4 2 2 4 3

EXERCISE (5)

Problem 5: Selection sort

Sorting an array means to arrange its elements in increasing order. Write a program to sort an array. Use the Selection sort algorithm: Find the smallest element, move it at the first position, find the smallest from the rest, move it at the second position, etc.

Input Output
3 4 1 5 2 6 1 2 3 4 5 6

EXERCISE (6)

Problem 6: Frequent number

Write a program that finds the most frequent number in an array of N element.

Input Output
13 4 1 1 4 2 3 4 4 1 2 4 9 3 4 (5 times)