1
CÁC KIỂU DỮ DIỆU TRỪU TƯỢNG
I. DANH SÁCH
{------------ THUC THI DANH SACH BANG MANG (DS DAC) ------------}
Uses CRT;
Const max=100;
Type
Datatype=integer;
List=record
data:array[1..max] of DataType;
Last:integer;
End;
Var L : List;i,n,x:integer;
{--------- TAO DANH SACH RONG --------}
Procedure Makenull(Var L: List);
Begin
L.Last:=0;
End;
{---------- KIEM TRA DANH SACH RONG --------}
Function Empty(L:List):boolean;
Begin
empty:=L.Last=0;
End;
{---------- KIEM TRA DANH SACH DAY ----------}
Function Full(L:List):boolean;
Begin
Full:=L.Last>max;
End;
{----------- TRA VE VI TRI PHAN TU SAU PT CUOI CUNG ------}
Function End_List(L:List): integer;
Begin

Local:=tim;
End;
{---------- THEM PHAN TU VAO DANH SACH TAI VI TRI P ----------}
Procedure Insert(x:integer;P:integer; Var L:List);
Var q:integer;
Begin
if Full(L) then writeln('Danh sach day!')
else
if (P<1) and (p>L.Last) then writeln('P is out position!')
else
begin
For q:=L.Last+1 downto p+1 do
L.data[q]:=L.data[q-1];
L.Last:=L.Last+1;
L.data[p]:=x;
end;
End;
{------------ XOA PHAN TU TAI VI TRI P ----------}
Procedure Delete(p:integer;Var L:List);
Var i: integer;
Begin
if Full(L) then writeln('Danh sach day!')
else
if (P<1) and (p>L.Last) then writeln('P is out position!')
else
begin
For i:=L.Last-1 downto p do
L.data[i]:=L.data[i+1];
L.Last:=L.Last-1;
end;

empty:=L^.next=nil;
End;
{----------- TRA VE PHAN TU SAU PHAN TU P -----------}
Function Next(P:List;L:List):List;
Begin
Next:=P^.next;
End;
{------------ TRA VE PHAN TU DAU DANH SACH --------------}
Function First(L:List):List;
Var P: List;
Begin
if not empty(L) then
P:=L;
End;
{----------- TRA VE PHAN TU SAU PHAN TU CUOI DANH SACH ----------}
Function End_List(L:List):List;
Var P: List;
Begin
P:=L;
While P^.next<>nil do P:=P^.next;
End_List:=P;
End;
{------------ TRA VE VI TRI PHAN TU TIM THAY --------}
Function Local(x:datatype;L:List):List;
Var P: List;
Begin
if empty(L) then Local:=nil
else
begin
4

end;
End;
{------------ THEM 2 PHAN TU VAO DANH SACH DA DUOC SAP XEP --------}
Procedure Insert_L1(x:integer;Var L: List);
Var tam:integer;P,Q:List;
Begin
new(Q);
Q^.data:=x;
Q^.next:=nil;P:=L;
While (P^.next<>nil) and (x>P^.next^.data) do P:=P^.next;
Q^.next:=P^.next;
P^.next:=Q;
End;
{-------------- XOA PHAN TU TAI VI TRI n TRONG DANH SACH -----------}
Procedure Delete(n:integer;Var L:List);
Var i: integer; P,P1:List;
Begin
if n=1 then
begin
P:=L;
5
P^.next:=P^.next;
end
else
begin
P:=L;
For i:=2 to n do P:=P^.next;
P^.next:=P^.next;
end;
P^.next:=P^.next^.next;

next:Node;
end;
Queue=record
front,rear: Node;
end;
Var Q: Queue;x,m,n:integer;
{--------- TAO HANG RONG -----------}
Procedure Makenull(Var Q: Queue);
Begin
6
new(Q.front);
Q.front^.next:=nil;Q.front:=Q.rear;
End;
{-------- KIEM TRA HANG RONG--------}
Function Empty(Q:Queue):boolean;
Begin
empty:=Q.front=Q.rear;
End;
{---------- LAY NOI DUNG TAI VI TRI DAU HANG --------}
Function Front(Q:Queue):elementype;
Begin
if not empty(Q) then
front:=Q.front^.next^.element;
End;
{--------- XOA PHAN TU DAU HANG ------------}
Procedure DelQueue(Var Q: Queue);
Var T: node;
Begin
if not empty(Q) then
Q.front:=Q.front^.next;

7
Function Full_Q(Q:Queue):Boolean;
Begin
Full_Q:=Q.rear=max;
End;
{--------- THEM PHAN TU VAO CUOI HANG ----------}
Procedure EndQueue(x:elementype;Var Q: Queue);
Begin
if Full_Q(Q) then writeln('Hang day!')
else
begin
if Q.front=0 then
Q.front:=Q.front+1;
Q.rear:=Q.rear+1;
Q.element[Q.rear]:=x;
end;
End;
{--------- XOA PHAN TU RA KHOI HANG ---------}
Procedure DelQueue(Var Q: Queue);
Begin
if empty(Q) then writeln('Hang doi rong!')
else
Q.front:= Q.front+1;
End;
III- NGĂN XẾP:
{------------- THUC THI NGAN XEP BANG MANG -------------}
Uses CRT;
Const max = 100;
Type
Elementype=integer;

End;
{-------- TRA VE PHAN TU TREN DINH NGAN XEP -------}
Function TOP(S:Stack):elementype;
Begin
if empty(S) then writeln('Ngan xep rong!')
else
Top:=S.element[S.top];
End;
{---------- XOA PHAN TU O DINH NGAN XEP ---------}
Procedure POP(Var S: stack);
Begin
if empty(S) then writeln('Ngan xep rong!')
else
S.Top:=S.Top+1;
End;
{------------- THUC THI NGAN XEP BANG CON TRO -------------}
Uses CRT;
Type
elementype=integer;
Stack=^Node;
Node=Record
element:elementype;
Link:Stack;
end;
Var S: Stack; x,m,n:integer;
{----------- TAO STACK RONG ----------}
Procedure Makenull(Var S: Stack);
Begin
S:=nil;
End;

elementype= char;
Node=integer;
Tree= record
parent:array[1..max] of node;
labell:array[1..max] of elementype;
max_node:node;
end;
Var T: Tree;i:node;
{--------- TAO CAY RONG --------}
Procedure Makenull(Var T:Tree);
Begin
T.max_node:=0;
End;
{-------- KIEM TRA CAY RONG -------}
Function Empty(T:Tree):boolean;
Begin
empty:=T.max_node=0;
End;
{--------- TIM CHA CUA NUT N --------}
Function Parent(n: node; T: Tree):node;
Begin
if empty(T) then writeln('Cay rong!')
else
parent:=T.parent[n];
End;
{-------- XAC DINH NUT GOC CUA CAY ---------}
Function ROOT(T:Tree):node;
Begin