Realizat de prof. Zenovia Mihuc 1

LISTE LINIARESIMPLU ÎNLĂNŢUITE

Declararea listelor Crearea listelor Operaţii cu liste Aplicaţii cu liste

2

Declararea listelor

Definirea unei liste de numere întregi

type PNOD= ^NOD NOD= record

info: integer; urm: PNOD; end;var l: PNOD; - info reprezintă informaţia utilă din

nod- urm reprezintă adresa nodului

următor din listă

Definirea unei liste de elevitype P_ELEV= ^ELEV

ELEV= record nume, prenume: integer; media: real:;

urm: P_ELEV; end;var l: P_ELEV; - nume, prenume, media reprezintă

informaţia utilă din nod- urm reprezintă adresa nodului

următor din listă

3

Crearea unei liste cu n noduri

< secvenţa_1> {creează nodul cu numărul de ordine 1}

for i:=2 to n do

<secventa_2> {creează nodul cu numărul de ordine i }

 

Vom scrie o funcţie {creare:pnod} care creează o listă liniară simplu înlănţuită de numere întregi, returnând un pointer către primul nod al listei.

În timpul creării vom folosi 3 pointeri:

- prim pointer către primul nod al listei create

- nou va adresa la fiecare pas nodul pe care îl creăm

- ultim va referi în permanenţă ultimul nod al listei

4

a)Crearea primului nod (<secventa_1>)

Alocam memorie pentru primul nod

new (prim)Citim informatia utila din acest prim nod

readln(prim^.info)Legatura urmatoare a acestuia este NIL

prim^.urm:=NILPointerul ultim trebuie sa-l adresze

tot pe el la fel ca si pointerul prim ultim:=prim

prim

ultim

prim

prim

prim

5

b)Crearea celorlalte noduri (<secventa_2>)

Alocam memorie pentru nodul nou

new (nou)

Citim informatia utila din nodul creat

readln(nou^.info)

Legatura sa urmatoare va fi NIL nou^.urm:=NIL

Legatura urmatoare a nodului care era ultimul va adresa nodul nou creat

(1) ultim^.urm:=nou

Nodul nou creat va deveni ultimul (2) ultim:=nou

. nou

nou

nou

prim

ultim

nou

prim

ultim

nou(1)

(2)

6

•new (nou) ; readln(nou^.info); nou^.urm:=NIL

Urmărim şi crearea celui de-al treilea nod

prim

ultim

nou

NILNIL

7

prim

ultim

nou

ultim^.urm:=nou

ultim:=nou

NIL

8

prim

ultim

nou

NIL

9

function creare:pnod;var prim,ultim,nou:pnod; i,n:integer;beginwrite('n=');readln(n);new(prim);readln(prim^.info);prim^.urm:=NIL;ultim:=prim;for i:=2 to n do begin new(nou);readln(nou^.info);nou^.urm:=nil; ultim^.urm:=nou;ultim:=nou; end;creare:=prim;end;

FUNCTIA DE CREARE

10

Ştergerea de noduri

Ştergerea primului nod Ştergerea ultimului nod Ştergerea nodului cu numărul

de ordine k din interiorul listei

11

Ştergerea primului nod

Aducem un pointer q către al doilea nod, operaţie necesară întrucât după ştergere al doilea nod va deveni primul. q:=p^.urm

Ştergem fizic primul nod referit de p. dispose(p)

După ştergere poinetrul pe care trebuie să-l returneze funcţia este q

q

...p

NIL

12

Ştergerea ultimului nod al unei liste liniare simplu înlănţuite

Avem nevoie de un pointer către nodul aflat înaintea celui care va fi şters, adică penultimul. Şi de această dată funcţia trebuie să returneze un pointer către primul nod al listei rezultante, deci nu putem muta direct pointerul p deoarece nu ar mai avea cine să adreseze primul nod.

Facem o copie q a pointerului p {q:=p} şi mutăm la penultimul nod copia q.

Această mutare seva face într-un ciclu astfel: atâta timp cât q nu a ajuns la penultimul nod, mută q la nodul următor

while q^.urm^.urm<> NIL do q:=q^.um

13

Ştergerea propriu-zisă

Ştergem fizic ultimul nod, eliberând memoria ocupată: dacă q adresează penultimul nod, atunci ultimul nod este referit de q^.urm deci instrucţiunea este dispose(q^.urm)

Nodul care a fost penultimul înaintea ştergerii,adresat de q, va deveni ultimul după ştergere q^.urm:=NIL

Funcţia returnează pointerul către primul nod, care a rămas p

q

p

NIL

q

mutare

14

Funcţia ştergere la sfârşitfunction sterg_sf(p:pnod):pnod; var q:pnod; begin q :=p ;

while q^.urm^.urm<> NIL do q:=q^.urm; dispose (q^.urm) ; q^.urm :=NIL ;

sterg_sf :=p ; end;

15

Ştergerea nodului cu numărul de ordine k din interiorul unei listei

r

De această dată avem nevoie de pointeri atât pe nodul k ce urmează a fi şters cât şi pe nodul anterior k-1. Mai întâi facem o copie q a pointerului p către primul nod şi mutăm q la nodul k-1 {for cu i de la 2 la k-1}.

Apoi pointerul r către nodul k va fi fireşte q^.urm. Ştergerea presupune realizarea unei singure legături, între nodul k-1 şi nodul k+1. După cum se poate observa şi din desen, aceasta se poate face prin atribuirea q^.urm:=r^.urm.

Mai trebuie făcută eliberarea memoriei ocupate de nodul k {dispose(r)}

q

p

q

mutare

1 ……………… k-1 k k+1 …………. n

legatura

NIL

(1)

(2)

16

STRUCTURA UNUI PROGRAM CU LISTE

type pnod=^nod; nod=record; Info:integer;

urm:pnod; end

var l,l1:pnod; function creare:pnod; begin ……………………. end; procedure afisare(p:pnod); begin ……………………. End;

function stergere(p:pnod):pnod; var q:pnod begin ……………………… end; BEGIN

L:=creare; afisare(l); l1:=stergere(l); afisare(l1)

END.