c 1 introduction to programming and the c language

c 1 introduction to programming and the c language


DisciplinaFísica Básica I834 materiais10.250 seguidores
Pré-visualização50 páginas
reference to the end of the list. Each element (box) 
in the list is usually called a node. This structure solves the problem of insertion and deletion, as you can 
insert a new element in the middle of the list by simply changing some references, and in the same way 
you can remove an item. The figure below shows how it looked, if you insert an element with a value of 
13 between 3 and 11 \u2013 it is necessary to change 4 references:
7 3 11 2 5
start end
13
Below is in the same manner shown how it looks if you remove the 3th element. It is necessary to change 
two references, and there are now no references to the 3th element, so it automatic is destroyed by the 
grabage collector.
7 3 11 2 5
start end
On the other hand, the problem of space consumption is not solved. There is no longer allocated space 
for items that are not used, but to each element there is attached two additional references, which also 
takes place.
A linked list solves the problem of insertion and deletion in the middle of the list, but one can not directly 
refer to the individual elements with an index. There is a need to seek from the beginning (or end) of 
the list until you find the item you are interested in.
The class LinkedList implements a linked list, and it differs from the class List of having other methods.
Download free eBooks at bookboon.com
C# 1 Introduction to programming and the C# language 
207 
LinkedList<T>
Exam48
LinkedList of names
Below is shown how to create a LinkedList and place some elements in it:
static void Main(string[] args)
{
LinkedList<string> list = new LinkedList<string>();
list.AddLast(&quot;Svend&quot;);
list.AddLast(&quot;Knud&quot;);
list.AddLast(&quot;Valdemar&quot;);
list.AddAfter(list.Find(&quot;Knud&quot;), &quot;Karlo&quot;);
list.AddBefore(list.Find(&quot;Karlo&quot;), &quot;Frede&quot;);
list.AddFirst(&quot;Gudrun&quot;);
Print1(list);
list.AddFirst(&quot;Olga&quot;);
list.AddFirst(&quot;Abelone&quot;);
Print2(list);
Print3(list);
}
static void Print1(LinkedList<string> list)
{
foreach (string name in list) Console.WriteLine(name);
Console.WriteLine(&quot;-----------------&quot;);
}
static void Print2(LinkedList<string> list)
{
for (LinkedListNode<string> node = list.Last; node != null; node = node.Previous)
Console.WriteLine(node.Value);
Console.WriteLine(&quot;-----------------&quot;);
}
static void Print3(LinkedList<string> list)
{
for (int i = 0; i < list.Count; ++i) Console.WriteLine(list.ElementAt(i));
Console.WriteLine(&quot;-----------------&quot;);
}
Explanation
There are four ways to insert an element
1. Insert it at the end of the list
2. Insert it at the beginning of the list
3. Insert it after an existing element
4. Insert it before an existing element
You should note how the method Find() finds the element to be inserted relative to. It returns a 
LinkedListNode, which is a structure similar to a node.
Download free eBooks at bookboon.com
C# 1 Introduction to programming and the C# language 
208 
LinkedList<T>
Note the three Print() methods. The first there is not much to tell, since it prints the list with a normal 
foreach loop. The second method use a property to obtain a reference to the last node \u2013 note again the 
type LinkedListNode. Then the list is traversed from behind. In a LinkedList you can not reference the 
elements with an index, but there is a method ElementAt(), which gives the same result. It is shown in 
the last printing method. Note that ElementAt() really counts from the beginning of the list and forward, 
so it\u2019s not a fair solution to the printing problem.
Comment
Whether to use a LinkedList or a List is determined by the task, since both data structures have their 
advantages and disadvantages. There is no doubt that a List is used more often.
Download free eBooks at bookboon.com
C# 1 Introduction to programming and the C# language 
209 
Dictionary<K,V> and SortedDictionary<K,V>
27 Dictionary<K,V> and 
SortedDictionary<K,V>
A dictionary is a collection where each element is identified by a key. Therefore, also sometimes one 
refers to a dictionary as a collection of key / value pairs, where each value is identified by a key. You 
could compare a dictionary with a list, because in a list, the elements are identified by an index. When 
you have to find an item in the list, you not search for the item, but its position is calculated from the 
index. In the same way it is with a dictionary, when you need to find an item, then one calculates the 
element\u2019s position based on the key value \u2013 you do not search for the item. The following figure can be 
used to illustrate some of the technique, which stores key / value pair as zip code and city:
Hobro
Blokhus
Gjern
Klovborg
Frederiksberg
0
1
2
3
4
5
6
7
8
9
9500
9492
8883
8765
1808
There needs a function that convert a zip code to a place in the container. Such a function is usually 
called a hash function, and instead of a dictionary you often refer to the structure as a hash table. In 
this case, the hash function should be simple, and consists simply in taking the last digit. For example 
are (9492, Blokhus) stored at position 2, since the zip code ends with 2. Similarly (8765, Klovborg) are 
stored in position 5, and (8883, Gjern) are stored on position 3.
The above is obviously very simplistic, but it illustrates two very fundamental problems:
\u2022	 What to do if the structure is filled out and needs to be expanded \u2013 above, there\u2019s only room 
for 10 elements.
\u2022	 What to do if there will be a collision \u2013 with the above hash function, (8543, Hornslet) are 
stored in the same place as Gjern.
Download free eBooks at bookboon.com
C# 1 Introduction to programming and the C# language 
210 
Dictionary<K,V> and SortedDictionary<K,V>
I shall not here explains, how to solve these problems, but just mention that it\u2019s problems that an 
implementation of the structure must necessarily solve.
The class Dictionary is a collection class to a dictionary or a hash table.
Exam49
Table of job titles
Below is an example where the key is a name, while the value is a job title:
static void Main()
{
Dictionary<string, string> map = new Dictionary<string, string>();
map.Add(&quot;Knud&quot;, &quot;Konge&quot;);
map.Add(&quot;Gudrun&quot;, &quot;Heks&quot;);
map.Add(&quot;Svend&quot;, &quot;Kriger&quot;);
map.Add(&quot;Olga&quot;, &quot;Spåkone&quot;);
map.Add(&quot;Valdemar&quot;, &quot;Skarpretter&quot;);
map.Add(&quot;Abelone&quot;, &quot;Klog kone&quot;);
Print1(map);
map[&quot;Gudrun&quot;] = &quot;Sin mands kone&quot;;
Print1(map);
Print2(map);
Print3(map);
}
static void Print1(Dictionary<string, string> map)
{
for (int i = 0; i < map.Count; ++i) Console.WriteLine(map.ElementAt(i));
Console.WriteLine(&quot;-----------------&quot;);
}
static void Print2(Dictionary<string, string> map)
{
foreach (string name in map.Keys) Console.WriteLine(map[name]);
Console.WriteLine(&quot;-----------------&quot;);
}
static void Print3(Dictionary<string, string> map)
{
foreach (string job in map.Values) Console.WriteLine(job);
Console.WriteLine(&quot;-----------------&quot;);
}
Explanation
Note first how to add values to a dictionary. Note then the first print method and how to print the key 
/ value pairs. The keys must be unique, and if you try to add a value with an existing key, you get an 
exception. However, you can change a value using the key as the index:
map[&quot;Gudrun&quot;] = &quot;Sin mands kone&quot;;
Note finally the last two printing methods, where the first method runs over all keys and the other runs 
over all values. Here you should note how to get a collection of all keys (using Print2()) and a collection 
of all values (using Print3()).
Download free eBooks at bookboon.com
Click on the ad to read more
C# 1 Introduction to programming and the C# language 
211 
Dictionary<K,V> and SortedDictionary<K,V>
If you execute the method you get the following result:
Download free eBooks at bookboon.com
C# 1 Introduction to programming