Lecţia 6 - Clase care permit lucrul cu liste, stive, cozi

Apărut la 17 noiembrie 2017 în C#   |   autor: Dan Pracsiu 2 comentarii

Vom analiza pentru început clasa ArrayList care implementează structura de tip listă cu ajutorul tablourilor unidimensionale. Dimensiunea unei liste este in mod dinamic mărită sau micşorată. Vom înţelege printr-o aplicaţie simplă cum putem utiliza un obiect de tip listă şi cum efectuăm unele operaţii cu lista. Pentru simplitate, vom memora în listă numere întregi. Funcţiile studiate vor fi:

• Add - adaugă un element la sfârşitul listei
• Insert - inserează un element în listă la o anumită poziţie
• BinarySearch - căutarea binară (în listă sortată) a poziţiei unui număr în listă
• Remove - elimină din listă un element
• Contains - verifică dacă un element apare sau nu în listă
• Clear - sterge toate elementele din listă
• RemoveAt - elimină un element de la o anumită poziţie din listă
• Sort - ordonează crescător elementele listei

Pentru a utiliza clasa ArrayList trebuie să adăugăm în antetul programului linia using System.Collections;

Programul este redat mai jos

int i, poz, e;
ArrayList L = new ArrayList();
// adaug 20 de numere in lista

for (i = 1; i <= 20; i++)
   L.Add(i * i);

// afisez lista
foreach (int element in L)
   Console.Write(element + " ");
Console.WriteLine();

// inserarea valorii 103 la pozitia 10 in lista
L.Insert(10, 103);
foreach (int element in L)
   Console.Write(element + " ");
Console.WriteLine();

// elementele listei sunt sortate, deci pot
// efectua cautarea binara a lui e
Console.Write("Lista e sortata. Cauta binar pe : ");
e = int.Parse(Console.ReadLine());
poz = L.BinarySearch(e);
if (poz >= 0) Console.WriteLine("Am gasit {0} la pozitia {1}", e, poz);
   else Console.WriteLine("Nu s-a gasit valoarea {0} in lista", e);

// eliminarea lui 103 din lista
L.Remove(103);
foreach (int element in L)
   Console.Write(element + " ");
Console.WriteLine();

//cautarea liniara a unei valori in lista
L.Insert(5, 1000);
L.Insert(2, 24);
Console.Write("Lista NU e sortata. Verific daca apare sau nu in lista : ");
e = int.Parse(Console.ReadLine());
if (L.Contains(e)) Console.WriteLine("{0} este continut in lista", e);
   else Console.WriteLine("{0} nu apare in lista", e);

//elimin toate elementele din lista:
L.Clear();
Console.WriteLine("numarul de elemente din lista este: " + L.Count);

// adaug aleator 20 de elemente in lista:
Random R = new Random();
for (i = 1; i <= 20; i++)
   L.Add(R.Next(100));
Console.WriteLine("\n\nElementele listei:");
foreach (int element in L)
   Console.Write(element + " ");
Console.WriteLine();
Console.Write("Elimin elementul de la pozitia : ");
e = int.Parse(Console.ReadLine());
L.RemoveAt(e);
Console.WriteLine("\n\nElementele listei dupa eliminare:");
foreach (int element in L)
   Console.Write(element + " ");
Console.WriteLine();

// sortez elementele listei:
L.Sort();
foreach (int element in L)
   Console.Write(element + " ");
Console.WriteLine();

// elimin lista
L = null;

 

Stiva

Pentru lucrul cu o stivă vom utiliza clasa Stack. O stivă este o colecţie de obiecte de tip Last In First Out, în care operaţiile de introducere şi extragere de obiecte se efectuează pe la un singur capăt. Funcţiile esenţiale în lucrul cu stiva sunt:

• Push - inserează un obiect în vârful stivei
• Peek - returnează obiectul din vârful stivei, fără a decrementa stiva
• Pop - elimină obiectul din vârful stivei

Programul de mai jos citeşte de la tastatură un număr natural n şi afişează numărul biţilor din reprezentarea lui n în baza 2, apoi afişează biţii lui n.

int n;
Stack st = new Stack();
Console.Write("n = ");
n = int.Parse(Console.ReadLine());
// depun bitii lui n in stiva
while (n > 0)
{
   st.Push(n % 2);
   n = n / 2;
}
Console.WriteLine("Numarul convertit in baza 2 are {0} biti.", st.Count);
// scot bitii de pe stiva
Console.Write("Numarul convertit in baza 2 este :");
while (st.Count > 0)
{
   Console.Write(st.Peek());
   st.Pop();
}

 

Coada

Pentru lucrul cu o coadă vom utiliza clasa Queue. O coadă este o colecţie de obiecte de tip First In First Out, în care operaţia de introducere se efectuează pe la un capăt, iar cea de extragere de obiecte se efectuează pe la celălalt capăt. Funcţiile esenţiale în lucrul cu coada sunt:

• Enqueue - inserează un obiect în coadă
• Peek - returnează obiectul din vârful cozii, fără a decrementa coada
• Dequeue - elimină un obiect din coadă

Programul de mai jos introduce în coadă primele n numere naturale, apoi le extrage şi le afişează la ecran:

int n;
Console.Write("n = ");
n = int.Parse(Console.ReadLine());
Queue q = new Queue();
for (int i = 1; i <= n; i++)
   q.Enqueue(i);
while (q.Count > 0)
{
   Console.Write(q.Peek() + " ");
   q.Dequeue();
}

Aplicaţie cu coada În fişierul numere.in pe prima linie se află un şir de n (1 < n < 10000) numere naturale cuprinse între 1 şi 9999, numere separate prin exact un spaţiu. Să se determine lungimea maximă a unei secvenţe de numere distincte din şir. Secvenţa este formată din elemente aşezate pe poziţii consecutive în şir. De exemplu, pentru şirul 7, 1, 3, 1, 2, 6, 9, 8, 1, 3, 5, 2, 11, 31, 12, 24, 25, 56, 25, lungimea maximă este 13 (începe cu numărul 6 şi se termină cu numărul 56).

Rezolvare

Folosim o coadă de lungime maximă 10000. Vom depune succesiv în coadă numerele din şir. Cand întâlnim un element x deja depus în coadă, actualizăm (dacă este cazul) lungimea maximă şi extragem din coadă toate numerele până la x inclusiv. Programul este dat mai jos.

Queue<int> q = new Queue<int>();
// Queue q = new Queue();
int[] a;
string linie;
int i, lungmax, n;
StreamReader fin = new StreamReader("numere.in");
linie = fin.ReadLine();
fin.Close();
string[] nr = linie.Split(' ');
n = nr.Length;
a = new int[n];
for (i = 0; i < n; i++)
   a[i] = int.Parse(nr[i]);
lungmax = 1;
for (i = 0; i < n; i++)
{
  int x = a[i];
  if (q.Contains(x))
  {
     if (lungmax < q.Count) lungmax = q.Count;
     // scot toate numerele pana la x
     while (x != (int)q.Peek())
        q.Dequeue();
     // scot si pe x
     q.Dequeue();
  }
  // adaug pe x in coada:
  q.Enqueue(x);
}
if (lungmax < q.Count) lungmax = q.Count;
Console.WriteLine("\n Lungimea maxima este : " + lungmax);

 

Probleme propuse

P1. Se consideră un număr natural n. Asupra lui n se pot efectua una din următoarele operaţii:
    a. dacă n este par, n se înjumătăţeşte (n = n div 2)
    b. dacă n este impar, se multiplică cu 3 şi se adună 1 (n = 3*n+1)
Pornind de la n se poate ajunge la 1 aplicând operaţiile a şi b într-un număr finit de paşi (este demonstrat acest lucru pentru orice n reprezentabil pe 32 de biţi). Se cere să se depună toate valorile obţinute într-o coadă şi să se determine valoarea maximă la care ajunge n. De exemplu, pentru n=7, în coadă depunem valorile: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Valoarea maximă este 52.

P2. Să se memoreze n numere întregi într-o structură de tip coada. Să se şteargă elementele neprime din vârful cozii până se întâlneşte un număr prim.

P3. Scrieţi un program care citeşte de la tastatură un şir de caractere şi verifică dacă şirul este palindrom. Programul trebuie să utilizeze o stivă şi de asemenea trebuie să puneţi în evidenţă unele operaţii cu stiva. Exemple de şiruri palindrom: "abccba", "capac".

P4. Se citesc dintr-un fişier de pe prima linie mai multe numere naturale ordonate crescător separate prin spaţiu. Memoraţi numerele într-o listă. Sortaţi lista. Pe a doua linie din fişier se găseşte un număr natural k. Inseraţi în listă pe k astfel încît şirul să rămână ordonat crescător.

Număr de accesări: 7349

• 

  XIIG 18-11-2011 13:38:12

  La multi ani domnule profesor !! Multa sanatate si fericire va dorim.

• 

  Dan P. 18-11-2011 16:41:4

  Multumesc pentru urari.
  Spor la rezolvat probleme in acest weekend!