11.3.5. Stergerea unei liste circulare simplu inlantuite (LCSI)

2020/03/07 in Programare in C

Functia csterglist sterge o LCSI.

void csterglist() {
   
   extern TNOD *ptrnod;
   TNOD *p, *p1;

   if ((p = ptrnod) == 0)
      return; /* lista vida */

   p = ptrnod;
   do {
      p1 = p;
      p = p -> urm;
      elibnod(p)
   } while (q != ptrnod);
   ptrnod = 0;
}

Exercitii:

11.10. Se considera tipul TNOD declarat ca mai jos:

typedef struct tnod {
   char *cuv;
   struct tnod *urm;
} TNOD;

Acest tip va fi utilizat in toate exercitiile din acest paragraf.

Mai jos se defineste functia care incarca datele intr-un nod de tipul TNOD.

int incnod (TNOD *p) {
/* - incarca datele in nodul spre care pointeaza p;
   - returneaza:
      -1 la intalnirea EOF;
       1 altfel. */

   char t[255];

   p -> cuv = 0; /* initializarea cu pointerul nul */
   printf("tastati pe un rand cuvantul curent\n");
   if (gets(t) == 0)
      return -1; /* s-a tastat EOF */
/* rezerva zona pentru randul citit */
   if ((p -> cuv = (char *)malloc(strlen(t) + 1)) == 0) {
      printf("memorie insuficienta\n");
      exit(1);
   }
/* pastreaza randul citit in memoria heap */
   strcpy(p -> cuv, t);
   return 1;
}

11.11. Sa se defineasca functia elibnod care elibereaza zonele de memorie ocupate de un nod de tip TNOD.

void elibnod (TNOD *p) {
/* elibereaza zonele de memorie ocupate de nodul spre care pointeaza p */

   free(p -> cuv);
   free(p);
}

11.12. Sa se scrie functia ccrelist care creaza o LCSI cu noduri de tip TNOD.

int ccrelist() {
/* - creaza o lista circulara; 
   - returneaza:
        0 - la eroare;
       -1 - altfel. */
	   
  extern TNOD *ptrnod;
  int i, n;
  TNOD *p;

  n = sizeof(TNOD);
  ptrnod = 0;

  while (((p = TNOD *)malloc(n)) != 0) && ((i = incnod(p)) == 1)) {
      if (ptrnod == 0) {
        ptrnod = p;
        ptrnod -> urm = p;
      }
      else {
        p -> urm = ptrnod -> urm;
        ptrnod -> urm = p;
        ptrnod = p;
      }
  }
  if (p == 0) {
     printf("memorie insuficienta la crearea listei\n");
     exit(1);
  }
  elibnod(p);
  return i;
}

11.13. Sa se scrie o functie care cauta un nod al listei circulare create prin ccrelist, nod pentru care pointerul cuv pointeaza spre un sir de caractere dat.

Functia returneaza pointerul spre nodul respectiv sau 0, daca nu exista un astfel de nod.

TNOD *ccncs(char *c) {
/* - cauta nodul ptr care cuv si c pointeaza spre acelasi sir de caractere;
   - returneaza pointerul spre nodul respectiv sau 0 daca el nu exista. */
   
   extern TNOD *ptrnod;
   TNOD *p;

   p = ptrnod;
   if (p == 0) /* lista vida */
      return 0;
   do {
      if (strcmp(p -> cuv, c) == 0)
         return p;
      p = p-> urm;
   } while (p != ptrnod);
   return 0;
}

11.14. Fie LCSI creata cu ajutorul functiei ccrelist definita in exercitiul 11.12., fie ptrnod pointerul spre un nod al ei pentru care ptrnod -> cuv pointeza spre un sir dat si n > 1 un intreg de tip int. Se cere nodul din lista obtinut in urma eliminarii nodurilor din lista in felul urmator:

  1. Se porneste cu nodul imediat urmator nodului care contine pointerul spre sirul dat si se elimina din lista al n-lea nod care urmeaza dupa acest nod;
  2. Se executa pasul 1 continuand cu nodul imediat urmator celui sters, pana cand lista se reduce la un singur nod.

Nodul la care s-a redus lista este cel cautat.

Aceasta problema se da adesea ca exemplu pentru utilizarea LCSI. O varianta a acestei probleme este asa numita Problema a lui Josephus. Ea se formuleaza:

O cetate este aparata de un numar de soldati care isi dau seama ca au nevoie de ajutoare pentru a rezista in fata dusmanului care ii ataca. Se pune problema de a alege pe unul dintre ei care sa plece dupa ajutor.

Alegerea se face asezand soldatii in cerc si tragand la sorti numele soldatului care sa inceapa numaratoarea. De asemenea, se trage la sorti un numar intreg mai mare decat 1. Se numara, in sensul acelor ceasornicului, incepand cu soldatul urmator celui al carui nume a fost tras la sorti si al n-lea soldat este scos din cerc. In felul acesta, dupa un numar finit de pasi, cercul se reduce la un singur soldat, caruia ii revine sarcina sa plece dupa ajutoare.

Problema lui Josephus este o varianta a formularii descrise prin punctele 1-2 de mai sus, daca se considera ca pointerul cuv pointeaza spre numele unui soldat. La pct. 1 se precizeaza ca se porneste cu un nod care urmeaza imediat nodului care contine un sir dat, adica numele soldatului tras la sorti.

Programul de mai jos rezolva problema conform urmatorilor pasi:

  1. citeste numarul n indicat in formularea problemei;
  2. citeste un sir de caractere care defineste nodul de la care incepe numaratoarea;
  3. creaza LCSI care trebuie sa contina un nod pentru care cuv pointeaza spre un sir identic cu cel citit la pct. 2.
  4. se elimina nodurile conform pasilor 1-2 din formularea problemei, de mai sus;
  5. se afiseaza cuvantul din nodul ramas in lista.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct tnod {
   char *cuv;
   struct tnod *urm;
} TNOD;

#include "FUNCTIA094B.C" /* pcit_int */
#include "FUNCTIA094C.C" /* pcit_int_lim */
#include "FUNCTIA123A.C" /* incnod */
#include "FUNCTIA123B.C" /* elibnod */
#include "FUNCTIA123C.C" /* ccrelist */
#include "FUNCTIA123D.C" /* ccncs */

#define MAXN 1000

TNOD *ptrnod;

int main() {
/* - creaza o LCSI si elimina nodurile ei pornind de la un nod dat si 
eliminand tot al n-lea nod, pana cand lista se reduce la un singur nod; 
   - in final se listeaza sirul spre care pointeaza cuv al nodului 
la care s-a redus lista. */

   char t[255];
   int i, n;
   char er[] = "s-a tastat EOF\n";
   TNOD *p, *p1;

/* citeste pe n */
   if (pcit_int_lim("n = ", 2, MAXN, &n) == 0) {
      printf(er);
      exit(1);
   }

/* citeste un sir de caractere care va defini nodul din lista pentru 
pornirea numararii nodurilor */
   printf("sirul pentru pornirea numararii\n");
   if (gets(t) == 0) {
      printf(er);
      exit(1);
   }

/* creaza lista circulara */
   printf("tastati sirurile care intra in compunerea listei\n");
   printf("cate un sir pe un rand\n");
   printf("la sfarsit se tasteaza Ctrl-Z\n");
   ccrelist();

/* se determina nodul pentru care cuv pointeaza spre un sir identic cu 
cel pastrat in tabloul t */
   if ((p = ccncs(t)) == 0) {
/* nu exista un nod pentru care sirul spre care pointeaza cuv sa 
coincida cu cel pastrat in tabloul t */
      printf("nu se poate determina nodul de la care sa inceapa numararea\n");
      exit(1);
   }
   
/* elimina nodurile din lista pana se ajunge la un singur nod */
   while (ptrnod != ptrnod -> urm) {
/* lista contine mai mult de un nod */

/* se cauta al n-lea nod incepand cu cel spre care pointeaza p */
      for (i = 1; i < n; i++) {
         p1 = p;
         p = p -> urm;
      }
/* - se sterge nodul spre care pointeaza p;
   - p1 pointeaza spre nodul precedent nodului spre care pointeaza p. */
      p1 -> urm = p -> urm;
      if (ptrnod == p)
         ptrnod = p1;
      free(p -> cuv);
      free(p);
      p = p1 -> urm; /* numaratoarea continua incepand cu nodul urmator 
celui sters */
   }
   
/* lista s-a redus la un singur nod */
   printf("sirul cautat: %s\n", ptrnod -> cuv);
}

11.4. Lista dublu inlantuita (LDI)