Bài 1.

Dùng cách cài đặt trên cơ sở mảng (con trỏ) hãy viết:

a. 1 hàm không đệ quy

b. 1 hàm đệ quy

đếm các nút trong một danh sách liên kết.

Function Length(List : PointerType) : integer;

Var count : integer;

Ptr : PointerType;

Begin

count := 0; {Hàm không đệ quy}

Ptr := List;

while (Ptr<>0) do

count := count + 1;

Ptr := Node[Ptr].Next;

end;

Length := count;

End;

{Hàm đệ quy}

Function Length(List : PointerType) : integer;

Begin

If (List = 0) then

Length := 0;

else Length := 1 + Length(Node[List]. Next);

End;

{ con trỏ }

Function Length(List: PointerType): integer;

Var count: integer;

Ptr: PointerType;

Begin

count:= nil; {Hàm không đệ quy}

Ptr:= List;

while Ptr<> nil do

count:= count+1;

Ptr:= Ptr^.Next;

end;

Length:= count;

End;

{Hàm đệ quy}

Function Length(List:PointerType):integer;

Begin

If List = nil then

Length:= 0

else Length:= 1+Length(List^. Next);

End;

Bài 2. Cho danh sách A có chứa các kí tự

B có chứa các số

a. Viết khai báo cho hai danh sách.

b. Viết thủ tục nhập.

c. Viết thủ tục tính tích Đềcác của hai danh sách A và B. Lưu kết quả tính được vào danh sách C.

Type

PointerChar = ^NodeChar;

NodeChar = Record

ch : Char;

Next: PointerChar;

End;

PointerInt = ^NodeInt;

NodeInt = Record

Int: Integer;

Next: PointerInt;

End;

PointerDecac = ^NodeDecac;

NodeDecac = Record

Ch_Decac : char;

Int_Decac : Integer;

Next: PointerDecac;

End;

Các thủ tục: Tạo ra con trỏ L có các kiểu kí tự, số nguyên, Decac. Khởi tạo danh sách rỗng được chỉ bởi con trỏ L ( L:=Nil)

Procedure CreatChar (Var L: PointerChar);

Begin

L := Nil;

End;

Procedure CreatInt (Var L: PointerInt);

Begin

L := Nil;

End;

Procedure CreatDecac (Var L: PointerDecac);

Begin

L := Nil;

End;

//Thủ tục chèn phần tử vào danh sách A//

Procedure InsertChar(var L: PointerChar; E: char; PrePtr: PointerChar);

var TempPtr: PointerChar;

new(TempPtr);

TempPtr^.Ch:= E;

if PrePtr = NIL then

TempPtr^.Next:= L;

L:= TempPtr;

end

else begin

TempPtr^.Next:= PrePtr^.Next;

PrePtr^.Next:= TempPtr;

end;

end;

//Thủ tục chèn phần tử vào danh sách B//

Procedure InsertInt(var L : PointerInt; E : Integer; PrePtr : PointerInt);

Var TempPtr : PointerInt;

new(TempPtr); {Lấy một nút mới}

TempPtr^.Int := E;

if (PrePtr = NIL) then

TempPtr^.Next := L;

L := TempPtr;

end

else begin

TempPtr^.Next := PrePtr^.Next;

PrePtr^.Next := TempPtr;

end;

end;

//Thủ tục chèn phần tử vào danh sách C//

Procedure InsertDecac (var L : PointerDecac; E_Ch: char; E_Int: integer; PrePtr: PointerDecac);

var TempPtr: PointerDecac;

new(TempPtr);

TempPtr^.Ch_Decac := E_Ch;

TempPtr^.Int_Decac := E_Int;

if (PrePtr = NIL) then

TempPtr^.Next := L;

L := TempPtr;

end

else begin

TempPtr^.Next := PrePtr^.Next;

Preptr^.Next := TempPtr;

end;

end;

//Thủ tục nhập phần tử vào danh sách A, B//

procedure InputA(var A: PointerChar);

var TempCh: char;

i, n: integer;

CreateChar(A);

write('So luong can nhap: ');

readln(n);

for i:= 1 to n do

write('Ch = ');

readln(TempCh);

InsertChar(A, TempCh, NIL);

end;

end;

procedure InputB(var B: PointerInt);

var TempInt: integer;

i, n: integer;

CreateInt(B);

write('So luong can nhap: ');

readln(n);

for i:= 1 to n do

write('Int = ');

readln(TempInt);

InsertInt(B, TempInt, NIL);

end;

end;

// Thủ tục tính tích Đềcác//

Procedure TichDecac(A: PointerChar; B: PointerInt; var C: PointerDecac);

var CurrPtrA : PointerChar;

CurrPtrB : PointerInt;

CurrPtrC : PointerDecac;

Begin

CurrPtrA := A; {Gán con trỏ hiện thời của danh sách A bằng A- Chỉ tới nút đầu tiên}

CreateDecac(C); {tạo danh sách C mới}

while (CurrPtrA <> NIL) do

CurrPtrB := B;

while (CurrPtrB <> NIL) do

InsertDecac(C, CurrPtrA^.Ch, CurrPtrB^.Int, NIL);

CurrPtrB := CurrPtrB^.Next;

end;

CurrPtrA := CurrPtrA^.Next;

end;

End;

Procedure TravelDecac(C:

PointerDecac);

var TempDecac : PointerDecac;

TempDecac := C;

while TempDecac <> NIL do

begin writeln(TempDecac^.Ch_Decac:3, ' ', TempDecac^.Int_Decac:5);

TempDecac := TempDecac^.Next;

end;

end;

var A: PointerChar;

B: PointerInt;

C: PointerDecac;

Begin { Chuong trinh chinh }

clrscr;

InputA(A); InputB(B);

writeln('tich de cac co duoc');

TichDecac(A, B, C);

TravelDecac(C);

readln;

End.

Bài 3. Cho đa thức bậc n

a0 + a1x + a2x2 +...+ anxn (an‡ 0)

a0, a1, a2, ..., an là các hệ số của đa thức

- Viết khai báo để lưu thông tin của đa thức vào trong một danh sách liên kết.

- Viết thủ tục cộng 2 đa thức A, B và lưu vào danh sách trỏ bởi C.

{Yêu cầu nhập số mũ từ cao xuống thấp}

Khai báo:

Type

PointerType = ^NodeType;

NodeType = Record

heso :real;

so_mu: integer;

Next: PointerType;

End;

procedure Create(var L: PointerType);

L:= NIL;

end;

//thủ tục chèn//

Procedure Insert(Var L : PointerType; heso : real; so_mu : integer; Var PrePtr : PointerType);

Var TempPtr : PointerType;

Begin

New(TempPtr); {Lấy ra một nút mới}

TempPtr^.heso := heso;

TempPtr^.so_mu := so_mu;

If (PrePtr = nil) then

Begin

TempPtr^.Next := L;

L := TempPtr;

End

Else

Begin

TempPtr^.Next := PrePtr^.Next;

PrePtr^.Next:= TempPtr;

End;

End;

//thủ thục tính tổng//

Procedure Tong (A, B: PointerType; Var C: PointerType;

Var CurrPtr_A, CurrPtr_B, CurrPtr_C : PointerType);

Begin

CurrPtr_A := A; CurrPtr_B := B; CurrPtrC := nil; {chưa có phần tử trong C}

Creat(C);

While (CurrPtr_A <> nil) and (CurrPtr_B <> nil) do

Begin

If (CurrPtr_A^.so_mu > CurrPtr_B^.so_mu) then

Begin

Insert(C, CurrPtr_A^.heso, CurrPtr_A^.so_mu, CurrPtrC);

CurrPtr_A := CurrPtr_A^.Next;

End

Else

If (CurrPtr_A^.so_mu < CurrPtr_B.so_mu) then

Begin

Insert (C, CurrPtr_B.heso, CurrPtr_B^.so_mu, CurrPtrC);

CurrPtr_B := CurrPtr_B^.Next;

End

Else

Begin

Insert(C, CurrPtr_A^.heso + CurrPtr_B^.heso, CurrPtr_A^.so_mu, CurrPtrC);

CurrPtr_A := CurrPtr_A^.Next;

CurrPtr_B := CurrPtr_B^.Next;

End;

End;

While (CurrPtr_A <> nill) do

Begin

Insert (C, CurrPtr_A^.heso, CurrPtr_A^.so_mu, CurrPtrC);

CurrPtr_A := CurrPtr_A^.Next;

End;

While (CurrPtr_B <> nill) do

Begin

Insert (C, CurrPtr_B^.heso, CurrPtr_B^.so_mu, CurrPtrC);

CurrPtr_B := CurrPtr_B^.Next;

End;

End;