c 1 introduction to programming and the c language

c 1 introduction to programming and the c language


DisciplinaFísica Básica I830 materiais10.236 seguidores
Pré-visualização50 páginas
and the C# language 
212 
Dictionary<K,V> and SortedDictionary<K,V>
Exam50
User defined key
In a dictionary the type for both key and value may be anything \u2013 almost. Consider the following type:
public class Name
{
private	string	firstname;
private string lastname;
public	Name(string	firstname,	string	lastname)
{
this.firstname	=	firstname;
this.lastname = lastname;
}
public override string ToString()
{
return	firstname	+	&quot;	&quot;	+	lastname;
}
}
Consider then a dictionary that has the type Name as key:
static void Main(string[] args)
{
Dictionary<Name, string> map = new Dictionary<Name, string>();
map.Add(new Name(&quot;Knud&quot;, &quot;Madsen&quot;), &quot;Konge&quot;);
map.Add(new Name(&quot;Gudrun&quot;, &quot;Jensen&quot;), &quot;Heks&quot;);
map.Add(new Name(&quot;Svend&quot;, &quot;Andersen&quot;), &quot;Kriger&quot;);
map.Add(new Name(&quot;Olga&quot;, &quot;Olesen&quot;), &quot;Spåkone&quot;);
map.Add(new Name(&quot;Gudrun&quot;, &quot;Jensen&quot;), &quot;Sin mands kone&quot;);
Print(map);
}
static void Print(Dictionary<Name, string> map)
{
for (int i = 0; i < map.Count; ++i) Console.WriteLine(map.ElementAt(i));
Console.WriteLine(&quot;-----------------&quot;);
}
Note that the program can be translated and executed, but the result is not as expected as key Gudrun 
Jensen occurs twice:
Download free eBooks at bookboon.com
C# 1 Introduction to programming and the C# language 
213 
Dictionary<K,V> and SortedDictionary<K,V>
The reason is that the type Name not overrides GetHashCode(). As mentioned builds a dictionary of a 
hash function to calculate the individual elements position, which in turn uses this type\u2019s GetHashCode() 
method. The key type must then always override GetHashCode():
public class Name
{
...
public override int GetHashCode()
{
return	firstname.GetHashCode()	+	lastname.GetHashCode();
}
}
Exam51
A sorted dictionary
A dictionary generally guarantees nothing about how the elements are arranged and in which order 
they are meet at a traversal of the structure. In contrast, a SortedDictionary is a dictionary, where the 
elements are sorted by key order:
static void Main()
{
SortedDictionary<string, string> map = new SortedDictionary<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;);
foreach (string navn in map.Keys) Console.WriteLine(&quot;{0}, {1}&quot;, navn, map[navn]);
}
That is, the result is ordered by the key which is name and note that this is not the same order as objects 
are added to the structure.
Download free eBooks at bookboon.com
Click on the ad to read more
C# 1 Introduction to programming and the C# language 
214 
Dictionary<K,V> and SortedDictionary<K,V>
Exam52
Comparable keys
The following can\u2019t be executed (you get an exception):
static void Test11()
{
SortedDictionary<Name, string> map = new SortedDictionary<Name, string>();
map.Add(new Navn(&quot;Knud&quot;, &quot;Madsen&quot;), &quot;Konge&quot;);
map.Add(new Navn(&quot;Gudrun&quot;, &quot;Jensen&quot;), &quot;Heks&quot;);
map.Add(new Navn(&quot;Svend&quot;, &quot;Andersen&quot;), &quot;Kriger&quot;);
map.Add(new Navn(&quot;Olga&quot;, &quot;Olesen&quot;), &quot;Spåkone&quot;);
foreach (Navn navn in map.Keys) Console.WriteLine(&quot;{0}, {1}&quot;, navn, map[navn]);
}
In order that the keys can be sorted, they must be comparable and it will say that the key type must 
implement the IComparable interface:
public class Name : IComparable<Name>
{
...
public int CompareTo(Name name)
{
if (lastname.CompareTo(name.lastname) == 0)
return	firstname.CompareTo(name.firstname);
return lastname.CompareTo(name.lastname);
}
}
Download free eBooks at bookboon.com
C# 1 Introduction to programming and the C# language 
215 
Dictionary<K,V> and SortedDictionary<K,V>
Here the keys is sorted so that the keys are first compared on the last name, and if the last names are 
the same, the keys are compared on the first name.
Comment
A SortedDictionary is internally a binary search tree, and without in this place to elaborate on what it 
is, can I mention that it is a structure that optimizes the search of elements. There are actually another 
collection class
SortedList<K, V>
that seen from the programmer is the same as a SortedDictionary, but also internally is a binary search 
tree. The difference is that a SortedList uses less memory than a SortedDictionary, and vice versa is a 
SortedDictionary more efficient at inserting and deleting of items.
Exam70
Cue list
In this example I will show how to represent a cue list for a book. The purpose is mainly to show how 
to use a SortedDictionary, but also a LinkedList.
A cue consists of a name and a number of page references where a name is a string, while a page reference 
is an integer and a cue list is a list of items of that kind. The task is to write a program that can create a 
cue list and print out the list on the screen.
How to
I will start by defining a class that can represent an element to the list consisting of a name and page 
references:
public class PageReferences
{
private string name;
private LinkedList<int> list = new LinkedList<int>();
public PageReferences(string name, int page)
{
this.name = name;
list.AddFirst(page);
}
Download free eBooks at bookboon.com
C# 1 Introduction to programming and the C# language 
216 
Dictionary<K,V> and SortedDictionary<K,V>
public string Name
{
get { return name; }
}
public int Count
{
get { return list.Count; }
}
public int this[int n]
{
get { return list.ElementAt(n); }
}
public int[] References
{
get { return list.ToArray(); }
}
public void Add(int page)
{
for (LinkedListNode<int> node = list.First; node != null; node = node.Next)
if (node.Value == page) return;
else if (node.Value > page)
{
list.AddBefore(node, page);
return;
}
list.AddLast(page);
}
public override string ToString()
{
StringBuilder builder = new StringBuilder(name + &quot;,&quot;);
for (LinkedListNode<int> node = list.First; node != null; node = node.Next)
builder.Append(&quot; &quot; + node.Value);
return builder.ToString();
}
}
I will keep the key words in a SortedDictionary with name as the key. This provides two advantages:
\u2022	 The list can be traversed, and thus printed sorted by name
\u2022	 one can find siderefenrencer to a particular cue without searching, but by direct lookup
When the keys are compared, I\u2019m not interested in making a distinction between uppercase and lowercase 
letters. Therefore I have written my own key type:
class PageKey : IComparable<PageKey>
{
private string name;
public PageKey(string name)
{
this.name = name;
}
Download free eBooks at bookboon.com
Click on the ad to read more
C# 1 Introduction to programming and the C# language 
217 
Dictionary<K,V> and SortedDictionary<K,V>
public string Value
{
get { return name; }
}
public override bool Equals(object obj)
{
if (!(obj is string)) return false;
return name.Equals((string)obj, StringComparison.CurrentCultureIgnoreCase);
}
public override int GetHashCode()
{
return name.ToUpper().GetHashCode();
}
public int CompareTo(PageKey key)
{
return string.Compare(name, key.name, true);
}
}
After that the class to the cue list can be written:
class Index
{
private SortedDictionary<PageKey, PageReferences> table =
new SortedDictionary<PageKey, PageReferences>();
How to retain your 
top staff
FIND OUT NOW FOR FREE
Get your free trial
Because happy staff get more done
What your staff really want?
The top issues troubling them?
How to make staff assessments 
work for you & them, painlessly?
DO YOU WANT TO KNOW:
Download free eBooks at bookboon.com
C# 1 Introduction to programming and the C# language 
218 
Dictionary<K,V> and SortedDictionary<K,V>
public bool Add(string name, int page)
{
name = name.Trim();
if (name.Length == 0) return false;
PageKey