VAR First, Last, p, q: PtrList

VAR

First, Last, p, q: PtrList;

 Tạo DSLK đơn (FIFO):

First:= NIL; {khởi tạo DS}

Repeat

New(p);

{ ... nhập/gán giá trị cho p^}

p^.Link:= NIL;

if First = NIL then {DS rỗng}

begin

First:= p; Last:= p;

end

else Last^.Link:= p;

Last:= p;

...............

Until Ok;

 Duyệt DSLK đơn:

p:= First;

While p <> NIL do

begin

{ ... xử lý p^}

p:= p^.Link;

end;

 Tìm kiếm một phần tử trong DS (key là khóa cần tìm)

OK:= False;

p:= First;

While (p <> NIL) and (not OK) do

if p^.Data = key then

begin

OK:= True;

{ ... xử lý p^}

end

else p:= p^.Link;

 Thêm một phần tử vào DS

• Thêm p vào đầu DS

b1. Cho vùng liên kết của p trỏ vào First;

p^.Link:= First;

b2. Cho First trỏ vào p.

First:= p;

• Thêm vào giữa/cuối DS (p là phần tử cần thêm, q phần tử đứng ngay trước p)

b1. Cho vùng liên kết của p trỏ vào vùng liên kết của q;

p^.Link:= q^.Link;

b2. Cho vùng liên kết của q trỏ vào p;

q^.Link:= p;

 Xóa một phần tử khỏi DS

• Xóa phần tử p ở đầu DS

if First <> NIL then

begin

p:= First; First:= p^.Link;

Dispose(p);

end;

• Xóa phần tử p đứng ngay sau phần tử q

p:= q^.Link;

if p <> NIL then

begin

q^.Link:= p^.Link;

Dispose(p);

end;

• 
  Ứng dụng
  

VD 10.4 Lập trình sinh ngẫu nhiên DSLK đơn có n phần tử (n <= 1000), mỗi phần tử chứa một số nguyên có trị tuyệt đối < 2008.

1. In DS ra màn hình;

2. Tìm phần tử có giá trị bằng số nguyên x nhập từ bàn phím;

3. Thêm phần tử y vào vị trí k, với y và k nhập từ bàn phím;

4. Xoá khỏi DS các số chính phương;

5. Sắp xếp DS theo thứ tự tăng bằng cách thay đổi mối liên kết thay vì thay đổi giá trị.

TYPE

PtrList = ^Item;

Item = RECORD

Data: Integer;

Link: PtrList;

END;

VAR

First: PtrList;

 Thủ tục tạo DS (FIFO):

Procedure TaoDS;

var p, Last: PtrList; N, i: Integer;

begin

Write(‘N = ‘); Readln(N);

Randomize;

First:= NIL; {khoi tao DS}

i:= 1;

Repeat

New(p);

p^.Data:= Random(1003)–Random(1003);

p^.Link:= NIL;

if First = NIL then begin {DS rong}

First:= p; Last:= p;

end

else Last^.Link:= p;

Last:= p;

Inc(i);

Until i > N;

End;

VD 10.5 Lập trình giải bài toán tuyển sinh trong Mục 9.5.