Setul 12
Problema 1: implemetarea unei cozi cu listă simplu înlănţuită
Definim o coadă de aşteptare pentru clienţi care aşteaptă să li se monteze telefon. O nouă cerere va fi trecută la sfârşitul cozii; cererile se vor soluţiona în ordinea sosirii şi vor fi scoase din coada de aşteptare (deci ştergerea se va face la început). O cerere conţine : numele titularului, adresa de instalare a postului telefonic şi data cererii; acestea vor fi alocate dinamic.
Programul va permite şi retragerea unei anumite cereri (urmată de ştergerea nodului respectiv), precum şi actualizarea unei cereri (dacă titularul a schimbat adresa), această actualizare neafectând poziţia titularului în coada de aşteptare.
Implementaţi coada cu listă simplu înlănţuită, reţinând în 2 pointeri adresele primului şi ultimului element;
Problema 2: Un grup de copii se hotaraste sa joace un joc. Stau in cerc in asa fel incat numele lor sunt in ordone alfabetica (in sens anti-orar). Copii aleg un sens, fie orar, fie anti-orar. De asemenea aleg un numar, N. Daca sensul este orar, se incepe cu copilul cu primul nume in ordine alfabetica, altfel se icepe de la cel cu ultimulnume. Se numara copii in sensul stabilit, si tot al N-lea copil e eliminat, pana nu mai ramane nici un copil in cerc. Scrieti un program care simuleazaa cest joc, folosind o lista circulara ordonata dublu inlantuita.
Numele copiilor se citesc dintr-un fisier, fiecare nume pe o linie. Numarul N si sensul de mers sunt citite de la tastatura. Afisati pe ecran evolutia jocului (cine e sarit si cine e eliminat).
De exemplu, fisierul cu nume arata asa:
Jacob
Emma
Michael
Isabella
Emily
Copii vor fi aranjati in ordinea: Emily Emma Isabella Jacob Michael.
Daca N e 3 iar directia e anti-orara, pe ecran se afiseaza:
Sar peste Michael
Sar peste Jacob
Iese afara Isabella.
Sar peste Emma
Sar peste Emily
Iese afara Michael.
Sar peste Jacob
Sar peste Emma
Iese afara Emily.
Sar peste Jacob
Sar peste Emma
Iese afara Jacob.
Sar peste Emma
Sar peste Emma
Iese afara Emma.
Sfarsit.
Probleme extra:
1. Modificaţi programul 2 pentru a face lista circulară, reţinând adresa unui singur nod ca referinţă la listă.
2. Simulaţi apelul recursiv al unei funcţii (factorial, Akerman, etc.) folosind o stivă.
Problema 1
Start
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct element
{
char client[20];
struct element *next;
} nod;
nod *addClient(nod *prim, char *client)
{
nod *nou = (nod *)malloc(sizeof(nod));
strcpy(nou->client, client);
nou->next = NULL;
if (prim == NULL)
return nou;
nod *q = (nod *)malloc(sizeof(nod));
for (q = prim; q->next != NULL; q = q->next)
;
q->next = nou;
return prim;
}
void showClients(nod *prim)
{
nod *q = (nod *)malloc(sizeof(nod));
for (q = prim; q!= NULL; q = q->next)
printf("%s ", q->client);
}
nod *deleteClient(nod *prim)
{
nod *nou = (nod *)malloc(sizeof(nod));
nou = prim->next;
if(prim) free(prim);
return nou;
}
int main(void)
{
nod *prim = NULL;
char o,nume[20];
int val;
puts("");
while(1)
{
puts("\n");
puts("a : Adaugare client");
puts("s : Stergere client");
puts("l : Listare clienti");
puts("t : Termina programul");
printf("\nOptiunea: ");
while(isspace(o=getchar()) );
printf("\n");
if (!isspace(o))
switch (tolower(o))
{
case 'a': { printf("Nume client: ");
scanf("%s", &nume);
prim = addClient(prim,nume);
break;}
case 's':{
prim = deleteClient(prim);
break;}
case 'l':{ puts("\nClientii sunt:");
showClients(prim);
break;}
case 't':
return;
default:
printf("Eroare : Comanda inexistenta\n");
}
}
return 0;
}
/*
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//typedef struct el{
char nume[20], adresa[20], data[20];
}person;
typedef struct element
{
person client;
struct element *next;
} nod;
nod *addClient(nod *prim, person *client)
{
nod *nou = (nod *)malloc(sizeof(nod));
nou->client->nume = client->nume;
nou->client->adresa = client->adresa;
nou->client->data = client->data;
nou->next = NULL;
if (prim == NULL)
return nou;
nod *q = (nod *)malloc(sizeof(nod));
for (q = prim; q->next != NULL; q = q->next)
;
q->next = nou;
return prim;
}
void showClients(nod *prim)
{
nod *q = (nod *)malloc(sizeof(nod));
for (q = prim; q != NULL; q = q->next)
printf("%s %s %s\n", q->client->nume, q->client->adresa, q->client->data);
}
nod *deleteClient(nod *prim)
{
nod *nou = (nod *)malloc(sizeof(nod));
nou = prim->next;
if (prim)
free(prim);
return nou;
}
int main(void)
{
char nume[20],adresa[20], data[20];
printf("nume adresa data separate prin spatiu\n");
scanf("%s %s %s",nume,adresa,data);
person p;
strcpy(p->nume,nume);
strcpy(p->adresa,adresa);
strcpy(p->data,data);
nod *prim = NULL;
//prim = addClient(prim, p);
//showClients(prim);
return 0;
}
/*
Alte lucruri despre liste
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
/* tipul pentru nodul listei */
typedef struct elem
{
int info;
struct elem *urm;
} nod;
/* cauta in lista indicata de radacina nodul cu campul info = infofnou
si returneaza pointerul catre acel camp
daca nodul cautat nu exista returneaza NULL */
nod *caut(nod *radacina, int inf)
{
nod *p;
for (p=radacina; p!=NULL && p->info!=inf; p=p->urm);
// se parcurge lista atata timp cant mai sunt noduri si inf nu a fost gasit
if (p!=NULL) /* daca inf a fost gasit in lista */
return p;
return NULL;
}
/* Functia listez parcurge lista si pentru fiecare nod afiseaza informatia memorata. */
void listez(nod *radacina)
{
nod *p;
for (p=radacina; p!=NULL; p=p->urm)
printf("Valoarea: %d la adresa %p\n",p->info,p);
}
nod *sterg_incep(nod *radacina)
{
nod *p, *aux;
if (radacina==NULL){ // lista goala
printf("lista e vida\n");
return NULL;
}
else
// sterg primul element
aux=radacina; //retin adresa primului element
radacina=radacina->urm; // il sterg, facandu-l pe urmatorul primul nod
free(aux); //eliberez memoria ocupata de el
return radacina;
}
nod *creaza_nod(int infonou){
nod *p;
if ((p=(nod *)malloc(sizeof(nod)))==NULL){
/* daca nu e memorie suficienta pentru a crea un nod nou, se da un mesaj de eroare dupa care se
termina functia si se returneaza NULL */
printf("Eroare: memorie insuficienta\n");
return NULL;
}
else{ // daca e loc
p->info=infonou; //se completeaza campurile nadului
p->urm=NULL;
return p; //se returneaza o referinta (un pointer) catre acel nod
}
}
nod * intro_incep(nod *radacina, nod *nou)
{
nou->urm=radacina; // nou->urm pointeaza spre primul nod din lista sau
// spre nimic (NULL) daca nu era nici un nod in lista (radacina==NULL)
radacina=nou; //radacina pointeaza spre nou, acum primul nod din lista
return radacina;
}
nod * intro_sfs(nod *ultim, nod *nou){
if (ultim!=NULL)
ultim->urm=nou; // ultim->urm pointeaza spre noul nod, legandu-l la lista
return nou; // nou devine ultimul nod
}
/* Functia main afiseaza meniul programului,citeste comanda si
apeleaza functia corespunzatoare */
main()
{
char o;
int val;
nod *radacina=NULL; // pastreaza inceputul listei
nod *nou, *ultim=NULL; // pastreaza sfarsitul listei
puts(""); // tiparesc un sir vid pentru delimitare fata de rularile anterioare
while(1)
{
puts("");
/* se afiseaza meniul programului */
puts("a : adauga un nod la inceput");
puts("d : adauga un nod la sfarsit");
puts("c : cauta un nod");
puts("s : sterge primul nod");
puts("l : listeaza tot");
puts("t : termina programul");
printf("\nOptiunea: ");
while(isspace(o=getchar()) );
printf("\n");
if (!isspace(o))
switch (tolower(o))
{
case 'a': { printf("adauga inceput nr=");
scanf("%d", &val);
nou=creaza_nod(val);
if (radacina==NULL) ultim=nou; //daca e primul element din lista
// initializam si ultim cu adresa noului nod
radacina=intro_incep(radacina, nou);
break;}
case 'd': { printf("adauga sfarsit nr=");
scanf("%d", &val);
nou=creaza_nod(val);
if (radacina==NULL) radacina=nou; // daca e primul element din lista
// initializam si radacina cu adresa primului nod
ultim=intro_sfs(ultim, nou);
break;}
case 'c': { puts("cauta si tipareste un nod");
printf("nr=");
scanf("%d", &val);
if ((nou=caut(radacina, val))!=NULL) /* cauta nodul in lista */
printf(" Valoare:%d\n", nou->info);
else
printf("Eroare: Identificator nedefinit\n");
break;
}
case 's':{ printf("stergere primul nod\n");
radacina=sterg_incep(radacina); /* sterge nodul din lista */
if (radacina==NULL) ultim=NULL; /* daca era ultimul nod */
break;}
case 'l':{ puts("listare");
listez(radacina);
break;}
case 't':
return 0;
default:
printf("Eroare : Comanda inexistenta\n");
}
}
}