10 2018 Lectia27

From Algopedia
Jump to navigationJump to search

Operatii cu liste - continuare

Inserare - continuare

In lectia precedenta am invatat cum putem adauga elemente la inceputul, respectiv la sfarsitul unei liste. ne propunem in continuare sa inseram intr-o lista:

  • pe o pozitie data, k. (elementul inserat va fi al k-lea element al listei)
  • inaintea unui nod pentru care stim adresa
  • dupa un nod pentru care stim adresa ( Tema )

Vom considera, ca in lectia precedenta structura nodului :

struct nod {
  int info;
  nod* urm;
};

Inserare pe pozitia k

void inserare ( nod *&p, int k, int val ){
  nod * d;
  d = new nod;
  d->info = val;
  if ( !p ){
    d->urm = 0;
    p = d;
  }
  else{
    nod *c = p;
    for ( int i = 1; i < k; i++ )
      c = c->urm;
    d->adr =  c->urm;
    c->urm = d;
  }
 
  }
}

Iata un exemplu de utilizare a functiei definite mai sus:

#include <iostream>
struct nod {
  int info;
  nod* urm;
};
using namespace std;
void inserare ( nod *&p, int k, int val ){
  nod *c, *d;
  d = new nod;
  d->info = val;
  if ( k == 1 ){
    d->urm = p;
    p = d;
  }
  else{
    nod *c = p;
    for ( int i = 1; i < k - 1; i++ )       // ma pozitionez pe elem de pe poz k-1
      c = c->urm;
    d->urm = c->urm;
    c->urm = d;
  }
}

void afisare ( nod* p ){
  while ( p != NULL ){
    cout << p->info << " ";
    p = p->urm;
  }
  cout<<"\n";
}

int main(){
  nod *p1 = 0;
  inserare( p1, 1, 1 ); afisare(p1);    // in lista p1, pe poz 1 adaug val 1 si afisez lista
  inserare( p1, 1, 2 ); afisare(p1);    // in lista p1, pe poz 1 adaug val 2 si afisez lista
  inserare( p1, 1, 3 ); afisare(p1);    // in lista p1, pe poz 1 adaug val 3 si afisez lista
  inserare( p1, 2, 8 ); afisare(p1);    // in lista p1, pe poz 2 adaug val 8 si afisez lista
  return 0;
}

Inserare inaintea unui nod q

void inserare ( nod *&p, int k, int val ){
  nod * d;
  d = new nod;
  d->info = val;
  if ( !p ){
    d->urm = 0;
    p = d;
  }
  else{
    nod *c = p;
    for ( int i = 1; i < k; i++ )
      c = c->urm;
    d->adr =  c->urm;
    c->urm = d;
  }
 
  }
}

Iata un exemplu de utilizare a functiei definite mai sus:

#include <iostream>
struct nod {
  int info;
  nod* urm;
};
using namespace std;
void inserare ( nod *&p, int k, int val ){
  nod *c, *d;
  d = new nod;
  d->info = val;
  if ( k == 1 ){
    d->urm = p;
    p = d;
  }
  else{
    nod *c = p;
    for ( int i = 1; i < k - 1; i++ )       // ma pozitionez pe elem de pe poz k-1
      c = c->urm;
    d->urm = c->urm;
    c->urm = d;
  }
}

void afisare ( nod* p ){
  while ( p != NULL ){
    cout << p->info << " ";
    p = p->urm;
  }
  cout<<"\n";
}

int main(){
  nod *p1 = 0;
  inserare( p1, 1, 1 ); afisare(p1);    // in lista p1, pe poz 1 adaug val 1 si afisez lista
  inserare( p1, 1, 2 ); afisare(p1);    // in lista p1, pe poz 1 adaug val 2 si afisez lista
  inserare( p1, 1, 3 ); afisare(p1);    // in lista p1, pe poz 1 adaug val 3 si afisez lista
  inserare( p1, 2, 8 ); afisare(p1);    // in lista p1, pe poz 2 adaug val 8 si afisez lista
  return 0;
}

Stergere

Stergerea primului nod

void stergprimul( nod* &p ){
  nod *q = p;  
  if( q == 0 ) {
    p = p -> adr;
    delete p;
  }
}

Laborator

Urmatoarele probleme sunt din "Teste de sinteza in programare"

Teza nr 1 ( creare si parcurgere stiva )

Sa se conceapa o structura dinamica de date pentru memorarea unei matrici rare( matrice de dimensiuni foarte mari care are majoritatea elementelor egale cu zero ). In structura de date sunt reprezentate numai valorile nenule din matrice, pentru fiecare element nenul memorandu-se si pozitia acestuia in tablou.

Scrieti un program care sa creeze structura conceputa citind din fisierul text F.IN de pe prima linie valorile n si m reprezentand dimensiunile tabloului, iar de pe urmatoarele n linii cate m numere naturale despartite prin spatii, reprezentand elementele tabloului. Sa se afiseze cel mai mare element nenul cu proprietatea ca divide suma tuturor elementelor tabloului, precizand linia si coloana pe care se afla.

#include <iostream>
#include <fstream>

using namespace std;
struct nod {
  int lin, col, inf;
  nod *urm;
};
nod *vf, *p, *q;
int s, i, j, info, m, n;
int main(){
  ifstream f( "f.in" ) ;
  f >> m >> n;
  vf = NULL;     // lista e initial vida
  s = 0;
  for ( i = 1; i <= m; i++ )
    for (j = 1; j <= n; j++ ) {
      f >> info;
      if( info ){     // daca elem e nenul, il adaugam la lista ( stiva)
        p = new nod;  // aloc spatiu de memorie pentru un nou nod
        p->lin = i;   // retin in nod, linia,
        p->col = j;   // coloana
        p->inf = info;// valoarea elementului din matrice
        p->urm = vf ; // leg nodul creat de primul nod al listei(vf)
        vf = p;       // primul nod al listei devine noul nod adaugat
        s += info;    // suma elementelor din matrice
      }
    }

  // cautam cel mai mare numar care divide pe s
  p = vf;      // parcurgem lista incepand cu primul nod
  q = 0;       // adresa elem cautat, initial 0
  while( p ) {
    if  ( s % p->inf == 0 )                 // daca elementul curent divide suma
      if( !q || ( q && q->inf < p->inf ) )  // si e mai mare decat elem gasit anterior, memorat in q
        q = p;                              // retinem adresa noului elem gasit
    p = p->urm;                             // trecem la urmatorul element din lista
  }
  if ( !q )
    cout<< "Nu exista un astfel de element\n";
  else {
    cout << " Elementul cerut este " << q->inf<<'\n';
    cout << " El se afla pe linia " << q->lin;
    cout << " coloana " << q->col << '\n';
  }
  return 0;
}
#include <iostream>
#include <fstream>

using namespace std;
struct nod {
  int lin, col, inf;
  nod *urm;
};
nod *vf, *p, *q;
int s, i, j, info, m, n;
int main(){
  ifstream f( "f.in" ) ;
  f >> m >> n;
  vf = NULL;     // lista e initial vida
  s = 0;
  for ( i = 1; i <= m; i++ )
    for (j = 1; j <= n; j++ ) {
      f >> info;
      if( info ){     // daca elem e nenul, il adaugam la lista ( stiva)
        p = new nod;  // aloc spatiu de memorie pentru un nou nod
        p->lin = i;   // retin in nod, linia,
        p->col = j;   // coloana
        p->inf = info;// valoarea elementului din matrice
        p->urm = vf ; // leg nodul creat de primul nod al listei(vf)
        vf = p;       // primul nod al listei devine noul nod adaugat
        s += info;    //
      }
    }

  // cautam cel mai mare numar care divide pe s
  p = vf;             // parcurgem lista incepand cu primul nod
  q = new nod;        // adresa elem cautat, initial 0
  q->inf = 0;         // initial valoarea elementului maxim este 0
  while( p ) {
    if  ( s % p->inf == 0    // daca elementul curent divide suma
      && q->inf < p->inf )   // si e mai mare decat elem gasit anterior, memorat in q
        q = p;               // retinem adresa noului elem gasit
    p = p->urm;              // trecem la urmatorul element din lista
  }
  if ( !q )
    cout << "Nu exista un astfel de element\n";
  else {
    cout << " Elementul cerut este " << q->inf<<'\n';
    cout << " El se afla pe linia " << q->lin;
    cout << " coloana " << q->col << '\n';
  }
  return 0;
}

Teza nr 2

Se citeşte un şir de cuvinte terminat cu cuvantul format numai din caracterul * şi se cere să se afişeze aceste cuvinte în ordine inversă celei de la citire. Se va utiliza pentru memorarea cuvintelor o structură dinamică de date.

Rezolvarea:

#include <iostream>
#include <string.h>
using namespace std;
struct nod {
  char cuvant[20];
  nod *urm;
};
nod *p, *vf;
void afisare ( nod *p ){
  while ( p != NULL ){
    cout << p->cuvant << " ";
    p = p->urm;
  }
}
char cuv[500];
int main( ) {
  // citesc cuinte pana se citeste *
  // introducem cuvintele intr-o lista in ordinea inversa citirii lor ( stiva ),
  vf = 0;
  cin >> cuv;
  while ( strcmp( cuv , "*" ) != 0 ){
    p = new nod;              // creez un nod nou ( aloc sp de mem )
    strcpy( p->cuvant, cuv ); // punem cuvantul citit in nod
    p->urm = vf;              // leg nodul creat de primul nod al listei ( adaug cuvantul in fata listei )
    vf = p;                   // nodul nou creat devine primul nod ( varful stivei )
    cin >> cuv;               // citesc un nou cuvant
  }
  //parcurgerea si afisarea cuvintelor din stiva
  if ( !vf )
    cout << "primul cuvant citit a fost *";
  else {
    cout << "cuvintele in ordine inversa:";
    afisare( vf );
  }

  return 0;
}

Teza nr 4

Se cere sa se scrie o procedura care sa citeasca de la tastatura numere naturale ce reprezinta note obtinute de un grup de elevi la un examen (cate o nota pentru fiecare elev). Citirea se termina atunci cand se introduce numarul 0. Notele mai mari decat 4 se vor introduce intr-o lista simplu inlantuita, iar cele in alta lista, tot simplu inlantuita.

Procedura va intoarce patru valori:

  • doua numere naturale, m si n, reprezentand numarul de note de promovare (adica numarul de note mai mari decat 4), respectiv numarul celorlalte note;
  • doi pointeri la inceputul celor doua liste. Daca o lista este vida, pointerul respectiv va contine constanta nil ( NULL sau 0).

Cerinte:

  • Sa se scrie procedura descrisa mai sus;
  • Sa se precizeze declaratiile necesare din programul principal;
  • Sa se scrie instructiunea din programul principal care apeleaza aceasta procedura.
// propunere autor
#include <iostream>
using namespace std;
struct nod{
  int info;
  nod* urm;
};
nod *c1, *c2;
void listare( nod* p ){
  nod* c = p;
  while( c ){
    cout << c->info <<"\n";
    c=c->urm;
  }
}


void proc( int &m, int &n, nod *&p1, nod *&p2 ){
  int a;
  cin >> a;
  if( a > 4 ){
    if( !p1 ){
      p1 = new nod;
      p1->info = a;
      p1->urm = 0;
      c1 = p1;
    }
    else{
      c1->urm = new nod;
      c1 = c1->urm;
      c1->urm = 0;
      c1->info = a;
    }
    m++;
    proc( m, n, p1, p2 );
  }
  else if( a > 0 ){
    if( !p2 ){
      p2 = new nod;
      p2->info = a;
      p2->urm = 0;
      c2 = p2;
    }
    else{
      c2->urm = new nod;
      c2->urm->urm = 0;
      c2->urm->info = a;
      c2 = c2->urm;
    }
    n++;
    proc( m, n, p1, p2 );
    }
    else return;
}
int main(){
  nod *p1 = 0, *p2 = 0;
  int m = 0, n = 0;
  proc( m, n, p1, p2 );
  listare( p1 );
  cout << "elemente " << m << "\n";
  listare( p2 );
  cout << "elemente " << n << "\n";
  return 0;
}
// propunere Isabela Coman
#include <fstream>
#include <iostream>
using namespace std;

struct nod{
  int info;
  nod* urm;
};

void adaugareInainte( nod *&p , int x ){
  nod* d = new nod;
  d->info = x;
  d->urm = p;
  p = d;
}

void listare( nod* p ){
  nod* c = p;
  while( c ){
    cout << c->info <<" ";
    c=c->urm;
  }
}

void proc( int &m, int &n, nod *&p1, nod *&p2 ){
  int a;
  cin >> a;
  while (a){
    if( a > 4 ){
      adaugareInainte( p1, a );
      m++;
    }
    else {
      adaugareInainte( p2, a );
      n++;
    }
    cin >> a;
  }
}
int main(){
  nod *p1 = 0, *p2 = 0;
  int m = 0, n = 0;
  proc( m, n, p1, p2 );
  cout << "Numarul de note mai mari decat 4 este " << m << ". Acestea sunt: ";
  listare( p1 );
  cout<< "\n";
  cout << "Numarul de note mai mici sau egale cu 4 este " << n << ". Acestea sunt: ";
  listare( p2 );
  return 0;
}

Tema

Tema Teorie

  • Realizati o funtie care adauga intr-o lista dupa un nod q, o valoare data
  • Problemele de pe pbinfo cu stergeri si inserari

Tema Laborator

Tezele 5,6,7 - vezi fisele puse de cioltan