Link.RO
11.1.3. Inserarea unui nod intr-o lista simplu inlantuita
2020/02/23 in Programare in C
Intr-o lista simplu inlantuita se pot face inserari de noduri in diferite pozitii. Cateva situatii care pot aparea frecvent sunt:
- inserare inaintea primului nod;
- inserare inaintea unui nod precizat printr-o cheie;
- inserare dupa un nod precizat printr-o cheie;
- inserare dupa ultimul nod al listei (adaugarea unui nod nou la lista).
In continuare se vor defini functii pentru cazurile 1-4 indicate mai sus, atat pentru liste simplu inlantuite, cat si variantele lor cand lista se implementeaza cu ajutorul tabloului de pointeri tpnod.
Tipurile TNOD si TTNOD se considera declarate ca pana acum.
11.1.3.1. Inserarea unui nod intr-o lista simplu inlantuita inaintea primului ei nod
Primul nod al unei liste simplu inlantuite este nodul spre care nu pointeaza pointerul urm al niciunui nod nod al listei, adica este nodul care nu este succesorul niciunui nod din lista. Spre acest nod pointeaza variabila prim, daca lista nu este vida.
In cazul utilizarii tabloului tpnod, primul nod al listei este nodul spre care pointeaza elementul tppnod[0].
Functia de inserare returneaza pointerul spre nodul inserat in lista sau zero in cazul in care nu se poate realiza inserarea (ca de altfel toate functiile de inserare).
TNOD *iniprim() {
/* insereaza nodul curent inaintea primului nod al listei */
extern TNOD *prim, *ultim;
TNOD *p;
int n;
n = sizeof(TNOD);
/* rezerva memorie heap si incarca datele in zona respectiva */
if(((p = TNOD *)malloc(n)) != 0) && (incnod(p) == 1)) {
if (prim == 0) { /* lista vida */
/* lista se compune numai din nodul curent */
prim = ultim = p;
p -> urm = prim;
/* primul nod al listei devine succesorul nodului care se insereaza */
prim = p;
/* nodul inserat nu este succesorul niciunui alt nod si de aceea
prim pointeaza spre el */
}
return p;
}
if (p == 0) {
printf("memorie insuficienta\n");
exit(1);
}
/* s-a rezervat memorie pentru nod, dar nu s-au incarcat date in nod */
elibnod(p);
return 0;
}Inserarea in cazul utilizarii tabelului tpnod implica eliberarea elementului tpnod[0]. In acest scop se fac atribuirile:
tpnod[i] = tpnod[i-1] pentru i = itpnod, itpnod-1, ..., 2, 1.
Se observa ca functia de inserare inaintea primului nod pentru liste, care foloseste tabloul de pointeri tpnod, nu mai este asa de eficienta ca functia iniprim definita mai sus.
TTNOD *tpiniprim() {
/* insereaza nodul curent inaintea primului nod al listei */
extern TTNOD *tpnod[];
extern int itpnod;
int n;
int i;
if (itpnod >= MAX) {
printf("lista are prea multe elemente\n");
return 0;
}
n = sizeof(TTNOD);
if (((p = (TTNOD *)malloc(n)) != 0) && (incnod(p) == 1))
{
/* deplaseaza valorile elementelor tabloului tpnod */
for (i = itpnod++; i > 0; i--)
tpnod[i] = tpnod[i-1];
tpnod[0] = p;
return p;
}
if (p == 0) {
printf("memorie insuficienta\n");
exit(1);
}
elibnod(p);
return 0;
}11.1.3.2. Inserarea unui nod intr-o lista simplu inlantuita inaintea unui nod precizat printr-o cheie
Vom presupune ca cheia este de tip int ca si in cazul functiei cnci definita la paragraful 11.1.2.
TNOD *inici(int c)
/* - insereaza un nod inaintea unui nod precizat printr-o cheie numerica;
- returneaza pointerul spre nodul inserat sau 0 daca inserarea nu are loc */
{
extern TNOD *prim;
TNOD *q, *q1, *p;
int n;
n = sizeof(TNOD);
/* - cauta nodul de cheie = c
- la terminarea ciclului:
- q - pointeaza spre nodul respectiv;
- q1 - pointeaza spre nodul precedent celui spre care pointeaza q. */
q1 = 0;
q = prim;
while (q) {
if (q -> cheie == c)
break; /* s-a gasit nodul cautat */
q1 = q;
q = q -> urm;
}
if (q == 0) { /* nu exista in lista un nod de cheie = c */
printf("nu exista in lista un nod de cheie = %d\n", c);
return 0;
}
/* se rezerva zona pentru un nod si se incarca datele nodului in ea */
if (((p = (TTNOD *)malloc(n)) != 0) && (incnod(p) == 1)) {
if (q == prim) {
/* cheie = c pentru primul nod si inserarea se face inaintea primului nod */
p -> urm = prim;
prim = p;
}
else {
/* nodul spre care s-a facut pointeaza p se insereaza intre nodul spre care
pointeaza q1 si si nodul spre care pointeaza q */
q1 -> urm = p;
/* succesorul nodului spre care pointeaza q1 este nodul spre care pointeaza p */
p -> urm = q;
/* succesorul nodului spre care pointeaza p este nodul spre care pointeaza q */
}
return p;
}
/* nu s-a facut inserarea ceruta */
if (p == 0) {
printf("memorie insuficienta\n");
exit(1);
}
elibnod(p);
return 0;
}In continuare definim functia care utilizeaza tabloul de pointeri tpnod.
TTNOD *tpinici(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 TTNOD *tpnod;
extern int itpnod;
int i, k;
/* daca itpnod >= MAX nu exista loc in tabelul de pointeri */
if (itpnod >= MAX) {
printf("lista are prea multe elemente\n");
return 0;
}
/* cauta nodul de cheie = c */
for (i=0; i cheie == c)
break; /* s-a gasit nodul cautat */
if (i == itpnod) { /* nu exista in lista un nod de cheie = c */
printf("nu exista in lista un nod de cheie = %d\n", c);
return 0;
}
n = sizeof(TTNOD);
/* rezerva zona pentru un nod si se incarca datele nodului in zona respectiva */
if (((p = (TTNOD *)malloc(n)) != 0) && (incnod(p) == 1)) {
/* deplaseaza valorile elementelor tabloului tpnod:
tpnod[k] = tpnod[k-1], pentru k = itpnod, itpnod-1, ..., i+1 */
for(k = itpnod++; k>i; k--)
tpnod[k] = tpnod[k-1];
/* tpnod[i] devine egal cu adresa nodului care se insereaza */
tpnod[i] = p;
return p;
}
/* nu s-a facut inserarea */
if (p == 0) {
printf("memorie insuficienta\n");
exit(1);
}
elibnod(p);
return 0;
}
11.1.3.3. Inserarea unui nod intr-o lista simplu inlantuita dupa un nod precizat printr-o cheie
Vom presupune ca cheia este de tip int.
TNOD *indci(int c)
/* - insereaza un nod dupa un nod precizat printr-o cheie numerica;
- returneaza pointerul spre nodul inserat sau 0 daca inserarea nu are loc */
{
extern TNOD *prim;
TNOD *p, *q;
int n;
/* - cauta nodul de cheie = c */
for (q = prim; q; q = q ->urm)
if (q -> cheie == c)
break;
if (q == 0) { /* nu exista in lista un nod de cheie = c */
printf("nu exista in lista un nod de cheie = %d\n", c);
return 0;
}
/* se rezerva zona pentru un nod si se incarca datele in nod */
n = sizeof(TNOD);
if (((p = (TTNOD *)malloc(n)) != 0) && (incnod(p) == 1)) {
/* se insereaza nodul spre care pointeaza p dupa nodul spre care pointeaza q */
p -> urm = q -> urm;
/* nodul succesor nodului spre care pointeaza q devine
succesor nodului spre care pointeaza p */
q -> urm = p;
/* succesorul nodului spre care pointeaza q devine
nodul spre care pointeaza p */
if (ultim == q)
/* nodul spre care pointeaza q nu a avut succesor;
- in acest moment nodul spre care pointeaza p nu are succesor */
ultim == p;
return p;
}
/* nu s-a facut inserarea ceruta */
if (p == 0) {
printf("memorie insuficienta\n");
exit(1);
}
elibnod(p);
return 0;
}Functia de inserare pentru liste implementate cu ajutorul tabloului de pointeri tpnod care realizeaza inserarea dupa un nod de cheie data este asemanatoare cu functia tpinici definita in paragraful precedent. In acest caz, se modifica instructiunea for pentru deplasarea elementelor tabloului tpnod si instructiunea de atribuire urmatoare ei:
for (k = itpnod++; k > i+1; k--)
tpnod[k] = tpnod[k-1];
tpnod[i+1] = p;11.1.3.4. Adaugarea unui nod la o lista simplu inlantuita
Adaugarea unui nod la o lista simplu inlantuita inseamna inserarea lui dupa nodul spre care pointeaza variabila ultim. Aceasta inseamna ca, dupa inserarea nodului, variabila ultim pointeaza spre nodul respectiv, acesta devenind nodul din lista care nu are succesor.
TNOD *adauga()
/* - insereaza un nod la o lista simplu inlantuita;
- returneaza pointerul spre nodul inserat sau 0 daca inserarea nu are loc */
{
extern TNOD *prim, *ultim;
TNOD *p;
int n;
/* se rezerva zona pentru un nod si se incarca datele in nod */
n = sizeof(TNOD);
if (((p = (TTNOD *)malloc(n)) != 0) && (incnod(p) == 1)) {
if (prim == 0) /* lista este vida */
prim = ultim = p;
else {
ultim -> urm = p;
/* succesorul nodului spre care pointeaza ultim devine nodul
spre care pointeaza p */
ultim = p;
/* acesta devine nodul spre care pointeaza ultim */
}
p -> urm = 0;
return p;
}
/* nu s-a facut inserarea ceruta */
if (p == 0) {
printf("memorie insuficienta\n");
exit(1);
}
elibnod(p);
return 0;
}Definim mai jos functia de adaugare a unui nod la o lista implementata cu ajutorul tabloului tpnod.
TTNOD *tpadauga()
/* - adauga un nod la o lista simplu inlantuita;
- returneaza pointerul spre nodul inserat sau 0 daca inserarea nu are loc */
{
extern TTNOD *tpnod[];
extern int itpnod;
int n;
if (itpnod >= MAX) {
printf("lista are prea multe elemente\n");
return 0;
}
n = sizeof(TTNOD);
if (((p = (TTNOD *)malloc(n)) != 0) && (incnod(p) == 1)) {
tpnod{itpnod++] = p;
return p;
}
p -> urm = 0;
return p;
}
if (p == 0) {
printf("memorie insuficienta\n");
exit(1);
}
elibnod(p);
return 0;
}