11.4.2. Inserarea unui nod intr-o lista dublu inlantuita (LDI)

2020/03/10 in Programare in C

Intr-o LDI se pot face inserari in diferite pozitii. La fel ca in cazul LSI, cateva posibilitati sunt:

1. inserare inaintea primului nod al listei (nodul spre care pointeaza variabila prim este primul nod al listei);
2. inserare inaintea unui nod precizat printr-o cheie;
3. inserare dupa un nod precizat printr-o cheie;
4. inserare dupa ultimul nod al listei (nodul spre care pointeaza variabila ultim este ultimul nod al listei).

11.4.2.1. Inserarea unui nod intr-o lista dublu inlantuita inaintea primului nod al ei

int *diniprim() {
/* - insereaza nodul curent inaintea primului nod al listei; 
   - returneaza pointerul spre nodul inserat */
  extern TNOD *prim, *ultim;
  TNOD *p;
  int n;

  n = sizeof(TNOD);

  if (((p = (TNOD *)malloc(n)) != 0) && ((i = incnod(p)) == 1)) {
    if (prim == 0) {
      prim = ultim = p;
      p -> prec = p -> urm = 0;
    }
    else {
      p -> urm = prim;
      p -> prec = 0;
      prim -> prec = p;
      prim = p;
    }
    return p;
  }
  if (p == 0) {
    printf("memorie insuficienta\n");
    exit(1);
  }
  elibnod(p);
  return i;
}

11.4.2.2. Inserarea unui nod intr-o lista dublu inlantuita inaintea unui nod precizat printr-o cheie

Vom presupune ca cheia este de tip int. Tipul TNOD se declara astfel:

typedef struct tnod {
    declaratii
    int cheie;
    declaratii
    struct tnod *prec;
    struct tnod *urm;
} TNOD;

Functia de inserare apeleaza functia dcnci care cauta intr-o lista dublu inlantuita un nod de cheie data. Aceasta functie este identica cu functia cnci definita la paragraful 11.1.2.

TNOD *dcnci(int c)
/* - cauta un nod al listei pentru care cheie = c;
   - returneaza pointerul spre nodul determinat
   in acest fel sau 0 daca nu exista niciun nod 
   asa incat cheie = c */
{
   extern TNOD *prim;
   TNOD *p;

   for (p = prim; p; p = p -> urm) {
      if (p -> cheie == c)
         return p;
      return 0;
}

Functia de inserare dinici:

TNOD *dinici(int c)
/* - insereaza un nod inaintea unui nod precizat printr-o cheie numerica;
   - returneaza pointerul spre nodul inserat 
   sau 0 daca nu are loc inserarea */
{
   extern TNOD *prim;
   TNOD *p, *q;
   int n;
   
/* cauta nodul pentru care cheie = c */
   if ((q = dcnci(c)) == 0){
      printf("nu exista in lista un nod de cheie = %d\n", c);
      return 0;
   }
   n = sizeof(TNOD);
   if (((p = (TNOD *)malloc(n)) != 0) && ((i = incnod(p)) == 1)) {
      p -> prec = q -> prec;
      p -> urm = q;
      if (q -> prec != 0)
/* precedentul lui q are ca urmator nodul inserat */
         q -> prec -> urm = p;
      q -> prec = p;
   if (prim == q)
/* s-a inserat inaintea primului nod */
      prim = p;
   return p;
   }
   if (p == 0) {
      printf("memorie insuficienta\n");
      exit(1);
   }
   elibnod(p);
   return 0;
}

11.4.2.3. Inserarea unui nod intr-o lista dublu inlantuita dupa un nod precizat printr-o cheie

Vom presupune ca cheia este de tip int, iar tipul TNOD este cel declarat ca mi sus. Pentru a localiza nodul de cheie precizata se va utiliza functia dcnci.

TNOD *dindci(int c)
/* - insereaza un nod dupa un nod precizat printr-o cheie numerica;;
   - returneaza pointerul spre nodul inserat 
   sau 0 daca nu are loc inserarea */
{
   extern TNOD *ultim;
   TNOD *p, *q;
   int n;
   
/* cauta nodul pentru care cheie = c */
  if ((q = dcnci(c)) == 0){
    printf("nu exista in lista un nod de cheie = %d\n", c);
    return 0;
  }
  n = sizeof(TNOD);
  if (((p = (TNOD *)malloc(n)) != 0) && ((i = incnod(p)) == 1)) {
    p -> prec = q;
    p -> urm = q -> urm;
    if (q -> urm != 0)
/* urmatorul lui q are ca si precedent nodul inserat */
      q -> urm -> prec = p;
    q -> urm = p;
    if (ultim == q)
/* s-a inserat dupa ultimul nod */
      ultim = p;
    return p;
  }
  if (p == 0) {
    printf("memorie insuficienta\n");
    exit(1);
  }
  elibnod(p);
  return 0;
}

11.4.2.2. Inserarea unui nod intr-o lista dublu inlantuita dupa ultimul nod (adaugare nod LDI)

In acest caz, tipul nodurilor se declara astfel:

typedef struct tnod {
    declaratii
    struct tnod *prec;
    struct tnod *urm;
} TNOD;

nefiind necesara prezenta unei chei.

TNOD *dadauga()
/* - adauga un nod la o LDI;
   - returneaza pointerul spre nodul inserat 
   sau 0 daca nu are loc inserarea */
{
   extern TNOD *prim, *ultim;
   TNOD *p;
   int n;
   
   n = sizeof(TNOD);
   if (((p = (TNOD *)malloc(n)) != 0) && ((i = incnod(p)) == 1)) {
      if (prim == 0) {
         prim = ultim = 0;
         p -> prec = p -> urm = 0;
      }
      else {
         ultim -> urm = p;
         p -> prec = ultim;
         p -> urm = 0;
         ultim = p;
      }
      return p;
   }
   if (p == 0) {
      printf("memorie insuficienta\n");
      exit(1);
   }
   elibnod(p);
   return 0;
}

11.4.3. Stergerea unui nod LDI