Struktury danych w C#

  • Artykuł

Published: September 7, 2004 | Updated: February 28, 2005

By Scott Mitchell, 4GuysFromRolla.com

Streszczenie: Scott Mitchell omawia struktury danych służące do implementacji zbiorów oraz zbiorów rozłącznych. Zbiór to nieuporządkowana kolekcja unikalnych elementów, które można wyliczyć (enumerować). Zbiory można także na różne sposoby porównywać z innymi zbiorami. Długość dokumentu — około 19 stron drukowanych.

Pobierz kod przykładów - Sets.msi.

Spis treści

  • Wprowadzenie

  • Zbiory — podstawowe informacje

  • Implementacja wydajnej struktury danych reprezentującej zbiory

  • Kolekcje zbiorów rozłącznych

  • Bibliografia

 

Wprowadzenie

Zbiór jest jedną z najbardziej podstawowych konstrukcji matematycznych — jest to nieuporządkowana kolekcja unikalnych obiektów. Obiekty należące do zbioru nazywamy elementami zbioru. Zbiory formalnie oznacza się wielką pochyloną literą, a elementy zbioru wymienia się wewnątrz nawiasów klamrowych ({...}). Poniżej przedstawiono przykłady tej notacji:

S = { 1, 3, 5, 7, 9 }
T = { Scott, Jisun, Sam }
U = { -4, 3.14159, Todd, x }

W matematyce zbiory zazwyczaj składają się z liczb, tak jak w powyższym przykładzie zbiór S składa się z dodatnich nieparzystych liczb całkowitych mniejszych niż 10. Jednak elementami z zbioru mogą być dowolne obiekty — liczby, osoby, łańcuchy znaków, litery, zmienne i tak dalej. Na przykład zbiór T zawiera imiona ludzi, a zbiór U składa się z liczb, imion i zmiennych.

W pierwszej części artykułu poznamy podstawowe pojęcia dotyczące zbiorów, powszechnie stosowaną notację oraz operacje, które mogą być przeprowadzane na zbiorach. Następnie przeanalizujemy, w jaki sposób można wydajnie zaimplementować strukturę danych, reprezentującą zbiór o zdefiniowanym uniwersum. W dalszej części artykułu przejdziemy do analizy zbiorów rozłącznych i najlepszych struktur danych, za pomocą których można przedstawić zbiory rozłączne.

Ciąg dalszy artykułu w dokumencie do pobrania (Plik *.doc 355 KB)