Nadesłany przez Paweł Szulc, 22 lutego 2014 17:33
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.Pobierz pełne rozwiązanie.
Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.
jednokierunkowa_lista_int.cs:
// Lista jednokierunkowa, niesortowana, przechowująca wartości int // (C) Paweł Szulc // www.algorytm.org using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ListaJednokierunkowa { class Program { class Element // klasa opisująca poszczególny element listy - wartość danego elementu oraz zmienną przechowującą następny element listy { private int Wartosc; private Element Nastepny; public Element(int W) { Wartosc = W; Nastepny = null; } public int ZwrocWartosc() { return Wartosc; } public Element ZwrocNastepny() { return Nastepny; } public void UstawNastepny(int W) { Nastepny = new Element(W); } public void UsunNastepny() { Nastepny = null; } public void ZamienNastepny() { Nastepny = ZwrocNastepny().ZwrocNastepny(); // usuwając n-ty element ze środka listy łaczymy element n-1 z elementem n+1 } } class Lista // klasa implementująca listę jednokierunkową { private Element Korzen; private int LiczbaElementow; public Lista() { Korzen = null; LiczbaElementow = 0; } public void Wstaw(int W) { if (Korzen == null) { Korzen = new Element(W); } else { Element Tmp = Korzen; while (Tmp.ZwrocNastepny() != null) Tmp = Tmp.ZwrocNastepny(); // przechodzimy na koniec listy, czyli do elementu, który nie posiada elementu następnego. Tmp.UstawNastepny(W); // jeżeli Tmp.ZwrocNastepny() zwróci null oznacza to, że jesteśmy na ostatnim elemencie listy } ++LiczbaElementow; } public bool Pusta() { return (LiczbaElementow == 0) ? true : false; // operator trójargumentowy, jeśli LiczbaElementow == 0 to zwróc true, w przeciwnym razie false } public bool Usun(int Indeks) { if ((Indeks < 1) || (Indeks > LiczbaElementow)) return false; if (Indeks == 1) Korzen = Korzen.ZwrocNastepny(); // jeśli trzeba usunąć pierwszy element zmieniamy korzeń z "n" na "n+1" else if (Indeks == LiczbaElementow) { Element Tmp = Korzen; while (Tmp.ZwrocNastepny().ZwrocNastepny() != null) Tmp = Tmp.ZwrocNastepny(); // przejście na przedostatni element listy Tmp.UsunNastepny(); // zmiana ostatniego elementu z "n" na "n-1" } else { Element Tmp = Korzen; for (uint a = 0; a < Indeks; ++a) Tmp = Tmp.ZwrocNastepny(); // przejście do elementu Indeks-1 Tmp.ZamienNastepny(); } --LiczbaElementow; return true; } public void Wyswietl() { Element Tmp = Korzen; for (uint a = 1; Tmp != null; ++a) { Console.WriteLine("Element {0} listy = {1}", a, Tmp.ZwrocWartosc()); Tmp = Tmp.ZwrocNastepny(); } } public int Rozmiar() { return LiczbaElementow; } } static void Main(string[] args) { Lista List = new Lista(); if (List.Pusta()) Console.WriteLine("Lista jest pusta"); // sprawdzenie poprawności działania metody Pusta List.Wstaw(5); List.Wstaw(1); List.Wstaw(58); List.Wstaw(7); List.Wstaw(0); List.Wstaw(-5); List.Wstaw(12); List.Wstaw(96); List.Wstaw(123); List.Wstaw(98563); Console.WriteLine("Liczba elementów listy: {0}. Pusta ? Odpowiedź: {1}", List.Rozmiar(), List.Pusta()); Console.WriteLine(); List.Wyswietl(); Console.WriteLine(); Console.WriteLine("Próba usunięcia do elementu Rozmiar+1 listy. Rozmiar = {0}", List.Rozmiar()); if (List.Usun(List.Rozmiar()+1)) Console.WriteLine("Usunięto nieistniejący element."); else Console.WriteLine("Błędny indeks"); Console.WriteLine(); if (List.Usun(1)) Console.WriteLine("Usunięto pierwszy element listy."); if (List.Usun(List.Rozmiar())) Console.WriteLine("Usunięto ostatni element listy"); if (List.Usun(List.Rozmiar() / 2)) Console.WriteLine("Usunięto {0} element listy", (List.Rozmiar() + 1) / 2); // należy dodać Rozmiar+1, ponieważ po wykonaniu tej metody rozmiar, jeszcze przed wyświetleniem zostanie zmniejszony o 1 Console.WriteLine(); List.Wyswietl(); Console.ReadKey(); } } }
for (uint a = 2; a < Indeks; ++a) Tmp = Tmp.ZwrocNastepny() ;