[WikiDyd] [TitleIndex] [WordIndex

Programy wzorcowe

1. Klasa  Stos  do wykorzystania w programie rozwiązującym wyrażenie w odwrotnej notacji polskiej.

   1 namespace StosNS
   2 {
   3         class Stos
   4         {
   5                 double[] v;
   6                 
   7                 public Stos()
   8                 {
   9                         v = new double[0];
  10                 }
  11                 
  12                 public bool empty()
  13                 {
  14                         return (v.Length == 0);
  15                 }
  16                 
  17                 public void push ( double vn )
  18                 {
  19                         double[] tmp = new double[ v.Length + 1 ];
  20                         for (int i= 0; i < v.Length; i++)
  21                                 tmp[i] = v[i];
  22                         tmp[ tmp.Length - 1] = vn;
  23                         v= tmp;
  24                 }
  25                 public double pop()
  26                 {
  27                         double[] tmp = new double[ v.Length - 1 ];
  28                         double toReturn = v[ v.Length - 1];
  29                         
  30                         for (int i= 0; i < (v.Length-1); i++)
  31                                 tmp[i] = v[i];
  32                         v= tmp;
  33                         
  34                         return toReturn;
  35                 }
  36                 
  37                 public void PrintToScreen()
  38                 {
  39                         for (int i = 0; i < v.Length; i++)
  40                                 Console.WriteLine("{0}: {1:F}", i, v[i]);
  41                 }
  42         }
  43 
  44         class MainClass
  45         {
  46                 public static void Main(string[] args)
  47                 {
  48                     // Fragment kodu testujacy wykorzystanie stosu.  
  49                     
  50                         Console.WriteLine("Nowy stos.");
  51                         Stos s = new Stos();                    
  52                         s.push(10.4);
  53                         s.push(1.2);
  54                         s.PrintToScreen();
  55                         s.pop();                        
  56                         s.PrintToScreen();
  57                         
  58                 }
  59         }
  60 }

2. Program wyznaczający wartość wyrażenia zapisanego w odwrotnej notacji polskiej.

   1 // project created on 2007-04-24 at 11:10
   2 using System;
   3 
   4 namespace ONPNS
   5 {
   6         // Pamietajmy, ze klasa ONP wymaga klasy Stos, ktora nalezy uzpelnic w tym kodzie.
   7 
   8         class ONP
   9         {
  10                 string[] toks;
  11                 public ONP( string s ) 
  12                 {
  13                         toks = s.Split( new char[] {' '});//, StringSplitOptions.RemoveEmptyEntries);                   
  14                 }
  15                 
  16                 public double eval()
  17                 {
  18                         Stos st = new Stos();
  19                         double v1,v2,v3;
  20                         foreach (string s in toks)
  21                         {
  22                             // Do testow:
  23                                 //Console.WriteLine("s={0}",s);
  24                                 if (s.Equals("+")) {
  25                                         v1 = st.pop();
  26                                         v2 = st.pop();
  27                                         st.push( v1 + v2 );
  28                                 } else if (s.Equals("-")) {                             
  29                                         v1 = st.pop();
  30                                         v2 = st.pop();
  31                                         st.push( v1 - v2 );
  32                                 } else {
  33                                         v1 = double.Parse( s );                                 
  34                                         st.push( v1 );
  35                                 }
  36                                 
  37                                 // Do testow:
  38                                 // st.PrintToScreen();
  39                         }
  40                         return st.pop();
  41                 }
  42                                 
  43         }
  44         
  45         class MainClass
  46         {
  47                 public static void Main(string[] args)
  48                 {
  49                         Console.WriteLine("Wyrazenie w odwrotnej notacji polskiej: 2 3 4 + -");
  50                         ONP onp = new ONP("2 3 4 + -");
  51                         Console.WriteLine("Wynik = {0:F}", onp.eval() );
  52                 }
  53         }
  54 }

3. Klasa  Osoba  wykorzystywana przez nastepny program jako informacja przechowywana w elementach listy.

   1 class Osoba 
   2 {
   3         public string imie;
   4         public string nazwisko;
   5         public int ocena;
   6         
   7         public Osoba(string imie, string nazwisko, int ocena)
   8         {
   9                 this.imie = imie;
  10                 this.nazwisko = nazwisko;
  11                 this.ocena = ocena;
  12         }
  13                 
  14         public override String ToString()
  15         {
  16                 return (String.Format("{0} {1} {2}", imie, nazwisko, ocena));
  17         }
  18 }

4. Przykładowa implementacja listy jednokierunkowej. Przy niewielkiej modyfikacji można ją przerobić na listę dwukierunkową. (Może być to zadaniem na zajęcia.)

   1 namespace Lists
   2 {
   3         // Element listy.  W obecnej wersji jest jednokierunkowy/
   4         // Zwróćmy uwagę, że wykorzystuje klasę Osoba.
   5         class ListElem
   6         {
   7                 public Osoba osoba;
   8                 
   9                 public ListElem next;
  10                 // public ListElem prev;
  11                 
  12                 public ListElem()
  13                 {
  14                         next = null;
  15                         // prev = null;
  16                 }
  17         }
  18         
  19         // Kontener lista. W przedstawionej wersji posiada minimalna wymaganą funkcjonalnosc.
  20         // Na zajeciach zadane będą wybrane funkcje do zaimplementowania. (2 lub 3)
  21         class List
  22         {
  23                 protected ListElem head;
  24                 
  25                 public List()
  26                 {
  27                         head = null;
  28                 }
  29                 
  30                 public void Add( Osoba os )
  31                 {
  32                         // Pobieamy ostatni element.
  33                         ListElem el = GetLast();                        
  34                         
  35                         if (head == null) {
  36                                 // Lista jest pusta wiec musimy zainicjowac pierwszy element.
  37                                 head = new ListElem();
  38                                 el = head;
  39                         } else {
  40                                 // Tworzymy nowy element listy na jej koncu
  41                                 el.next = new ListElem();
  42                                 el = el.next;
  43                         }
  44                         
  45                         // Przyporzadkowujemy osobe nowo utworzonemu elementowi
  46                         el.osoba = new Osoba( os.imie, os.nazwisko, os.ocena );                         
  47                 }
  48                 
  49                 public Osoba Remove( ListElem elem )
  50                 {
  51                         return null;
  52                 }
  53                 
  54                 public ListElem GetFirst()
  55                 {
  56                         return head;
  57                 }
  58                 
  59                 public ListElem GetLast()
  60                 {
  61                         ListElem el = head;
  62                         if (el == null) 
  63                                 return null;
  64                                 
  65                         while (el.next != null)
  66                                 el = el.next;
  67                         
  68                         return el;
  69                 }
  70                 
  71                 public void InsertAfter(ListElem el, Osoba os)
  72                 {
  73                 }
  74                 
  75                 public void InsertBefore(ListElem el, Osoba os)
  76                 {
  77                 }
  78                 
  79                 public ListElem Find( Osoba os )
  80                 {
  81                         return null;
  82                 }
  83                 
  84                 public ListElem FindNazwisko( String nazwisko )
  85                 {
  86                         return null;
  87                 }
  88                 
  89                 public void Sort()
  90                 {
  91                 }
  92                 
  93                 // Wypisujemy na ekranie wszystkie elementy listy.
  94                 // Funkcja ta obrazuje jak iterowac po elementach.
  95                 public void PrintToScreen()
  96                 {
  97                         ListElem el = head;
  98                         while (el != null)
  99                         {
 100                                 Console.WriteLine("{0}", el.osoba);
 101                                 el = el.next;
 102                         }
 103                 }
 104         }
 105         
 106         // Prosty program testujacy.
 107         class MainClass
 108         {
 109                 public static void Main(string[] args)
 110                 {
 111                         List l = new List();
 112                         
 113                         l.Add( new Osoba("Jan","Kowalski",2) );
 114                         l.Add( new Osoba("Michal","Sieradzki",2) );
 115                         l.Add( new Osoba("Pan","Nowak",2) );
 116                         
 117                         l.PrintToScreen();
 118                         //Console.ReadLine();
 119                 }
 120         }
 121 }

Przykładowe zadania

1. Proszę zmodyfikować klasę Stos w programie 1 tak aby udostępniała informację o aktualnym rozmiarze stosu. Proszę napisac odpowiedni porgram testujacy.

2. Proszę uzupełnić klasę Stos w poiższym programie, tak aby zasada działania była taka sama jak w programie 1. prosze napisać odpowiedni kod testujacy. Należy zrócić uwagę, że w tym przypadku wektor liczb double jest stały, a informacja o aktualnym rozmiarze stosu jest przechowywana w zmiennej size. W przykładzie tym musimy pamiętać aby sprawdzać czy maksymalny rozmiar stosu nie został przekroczony (100).

   1         class Stos
   2         {
   3                 double[] v;
   4                 int size = 0;
   5                 
   6                 public Stos()
   7                 {
   8                         v = new double[100];
   9                 }
  10                 
  11                 public bool empty()
  12                 {
  13                 }
  14                 
  15                 public void push ( double vn )
  16                 {
  17                 }
  18 
  19                 public double pop()
  20                 {
  21                 }
  22                 
  23                 public void PrintToScreen()
  24                 {
  25                         for (int i = 0; i < size; i++)
  26                                 Console.WriteLine("{0}: {1:F}", i, v[i]);
  27                 }
  28         }

3. Zarządzanie strukturą listy jednokierunkowej (dodawanie, usuwanie).

4. Zarządzanie strukturą listy dwukierunkowej (dodawanie, usuwanie).

5. Sortowanie listy.

6. Filtrowanie listy - dopasowywanie do wzorca.

7. Wstawianie danych z sortowaniem.

8. Zadanie praktyczne.

9. Implementacja usuwania elementu ze struktury danych tablicowej oraz implementacja usuwania elementu z listy jednokierunkowej. (Porównanie wydajności.)

10. Usuwanie elementów o wskazanej wartości z tablicy poprzez ich oznaczenie do usuniecia, a nastepnie przez proces "kompresowania" ("kompaktowania").

11. Implementacja listy cyklicznej.

12. Impementacja kolejki priorytetowej na przykładzie zadań do wykonania w programie osobistego organizatora.


Przykład z 31.03.2009

   1 using System;
   2 using System.IO;
   3 
   4 namespace ListaOsob
   5 {
   6     class Osoba
   7     {
   8         public string imie;
   9         public string nazwisko;
  10         public int ocena;
  11 
  12         public Osoba(string imie, string nazwisko, int ocena)
  13         {
  14             this.imie = imie;
  15             this.nazwisko = nazwisko;
  16             this.ocena = ocena;
  17         }
  18 
  19         public override String ToString()
  20         {
  21             return (String.Format("{0} {1} {2}", imie, nazwisko, ocena));
  22         }
  23     }
  24 
  25     class Program
  26     {
  27         static void Main(string[] args)
  28         {
  29             Osoba[] lista = new Osoba[100];
  30             int line = 0;
  31             TextReader tr = new StreamReader(args[0]);
  32             String s;
  33             while ((s = tr.ReadLine()) != null)
  34             {
  35                 String [] ino = s.Split(' ');
  36                 if (ino.Length == 3)
  37                     try
  38                     {
  39                         lista[line++] = new Osoba(ino[0], ino[1], Int32.Parse(ino[2]));
  40                     }
  41                     catch (SystemException e)
  42                     {
  43                         Console.WriteLine("Linia: \"{0}\" nie zawiera osoby (pominieta)", s);
  44                     }
  45                 else
  46                 {
  47                     Console.WriteLine("Linia: \"{0}\" nie zawiera osoby (pominieta)", s);
  48                 }
  49             }
  50             tr.Close();
  51             foreach (Osoba o in lista)
  52                 if( o != null ) Console.WriteLine(o);
  53             Console.ReadLine();
  54         }
  55     }
  56 }

2015-09-23 06:32