0.5 Con trỏ và cấu trúc động  (Page 2/2)

ct3:@x;

ct2=ct3;

là hợp lệ vì ct2 và ct3 là tương thích, chúng cùng trỏ đến địa chỉ cùng biến x

ct1:=ct2;

là không hợp lệ vì hai con trỏ không tương thích .

3. 4 Phép so sánh hai con trỏ

Chỉ tồn tại phép so sánh =(bằng nhau)và<>(khác nhau)giữa hai con trỏ nếu chúng tương thích. Kết quả so sánh là một giá trị Boolean nghĩa là True hoặc False.

Hai con trỏ tương thíchgọi là bằng nhau nếu chúng cùng trỏ tới một đối tượng , ngược lại gọi là khác nhau.

4.Truy nhập dữ liệu

Khi con trỏ ct đang trỏ tới một vùng dữ liệu nào đó Pascal cho phép dùng ký hiệu ct^ như là một biến để truy nhập vào vùng dữ liệu đó . Biến ct^ mang trong đó dữ liệu của vùng mà con trỏ ct đang trỏ tới.

Như vậy chúng ta có thể truy nhập tới một biến, hàm hai thủ tục mà không cần biết tên các đối tượng này miễn là biết con trỏ đang trỏ vào chúng .

Ví dụ 4.5

Program contro;

Uses crt;

Type zl= string[3];

Var

z:string;ct:^zl;i:byte;

Begin

clrscr;

z:=’Ha noi’;ct:=@z;

writeln(ct^);

For i:=1 to length(z) do write(upcase(ct^[i]);

Readln;

End.

Chạy chương trình ta nhận được kết quả:

Ha noi

HA NOI

Mọi xử lý trên biến z đều có thể xử lý trên biến ct^ bởi vì biến con trỏ ct đang trỏ vào z.

• Mảng con trỏ và con trỏ kiểu mảng:

Con trỏ là một kiểu dữ liệu nên biến con trỏ có thể là các thành phần của mảng, ngược lại mảng là một kiểu dữ liệu có cấu trúc nên con trỏ cũng có thể trỏ tới các biến mảng.

5.1 Con trỏ kiểu mảng:

Khai báo:

Type m= array[1..5] of Byte;

Var

Ct1:^m;

Ct1 là biến con trỏ kiểu mảng, khi đó biến ct1^ sẽ gồm 5 phần tử, mỗi phần tử là một số kiểu Byte.

Truy cập vào biến ct1^:

Read(ct1^[i]); hoặc Write(ct1^[i]);

5.2 Mảng các con trỏ:

Khai báo:

Var:

Ct:array[1..10] of ^string;

s1,s2:String;

Begin

s1,s2:String;

Begin

S1:=’Ha noi Viet nam’;

S2:=’Happy new Year’;

…

Ct là mảng 10 con trỏ, tất cả 10 con trỏ trỏ tới đến kiểu dữ liệu String. Mỗi con trỏ trỏ đến một đối tương khác nhau.

• Nếu ta chưa gán địa chỉ của bất kỳ đối tượng nào cho biến con trỏ mà chỉ thực hiện phép gán:

Ct[i]:^=s1; với 1<=i<=10

Thì 10 con trỏ đều trỏ tới s1;

• Trong trường hợp ta gán dữ liệu từ một đối tượng cho nhiều biến con trỏ thì tất cả các con trỏ trỏ tới đối tượng được gán cuối cùng.

Nếu thực hiện phép gán:

Ct[1]:=@s2;

Nghĩa là gán địa chỉ của biến s2 vào con trỏ thứ nhất trong mảng thì chỉ có ct[1] là trỏ tới biến s2, các con trỏ con lại chưa trỏ vào đâu cả.

• Danh sách liên kết và hàng đợi:

Danh sách là một tập hợp hữu hạn các phần tử liên kết với nhau, trường hợp tổng quát nhất mỗi phần tử là một bản ghi. Điều đặt biệt của mỗi bản ghi trong danh sách là ngoài các trường dữ liệu, còn một trường dùng để liên kết và trường này lại là một con trỏ. Con trỏ này có nhiệm vụ trỏ vào địa chỉ của bản ghi kế tiếp. Nếu bản ghi hiện thời là bản ghi cuối cùng thì con trỏ sẽ trỏ vào Nil.

Một danh sách chưa có phần tử nào được gọi là danh sách rỗng. Việc thêm một phần tử vào danh sách có thể rơi vào một trong ba khả năng:

• Phần tử mới được thêm vào đầu danh sách
• Phần tử mới được thêm vào cuối danh sách.
• Phần tử mới được thêm vào một vị trí xác định

Trường hợp a ta có danh sách liên kết ngược (LIFO), còn trường hợp b ta có danh sách liên kết thuận (FIFO) hay còn gọi là hàng đợi QUEUE.

• Danh sách liên kết ngược:

Là loại danh sách mà trường liên kết của phần tử tạo ra sau luôn trỏ vào phần tử trước đó.

Type

Ds=^nguoi;

Nguoi=record

Mhs:byte;

Hoten:string[20];

Diem:real;

Tiep:ds;

End;

Sau khi khai báo kiểu dữ liệu cần khai báo biến con trỏ Dslop để lưu trữ dữ liệu nhập vào và biến Ctcuoi (con trỏ cuối) để trỏ vào phần tử cuối cùng.

Đoạn chương trình mô phỏng tạo danh sách liên kết ngược.

Ctcuoi:=nil; {khởi tạo danh sách};

Bắt đầu lặp:

New (dslop); {tạo biến động lưu trữ dữ liệu nhập vào}

Nhập dữ liệu; {nhập dữ liệu cho phần tử thứ i}

Tiep:=ctcuoi; {trường liên kết của phần tử thứ i trỏ vào địa chỉ của con trỏ cuố ctcuoi}

Ctcuoi:=dslop; {hướng ctcuoi vào bản ghi hiện thời}

Kết thúc lặp.

Ví dụ 4.6 : Xây dựng danh sách, chương trình con Hien_LIFO cho hiện dữ liệu lên màn hình theo chiều ngược, phần tử nhập sau hiện trước.

Program dslk_nguoc;

Uses Crt;

Type ds=^nguoi;

Nguoi=record

Mhs:byte;

Hoten:string[20];

Diem:real;

Tiep:ds;

End;

VAr

dslop,ctcuoi:ds; i,j:byte;

tt:char;

Procedure Hien_LIFO;

var ct1:ds;

Begin

clrscr;

writeln('Du lieu da nhap-Hien tu cuoi ve dau');

writeln;

ct1:=ctcuoi;

while ct1<>nil do

with ct1^ do

Begin

write(Mhs,' ',hoten);

for j:=1 to (20-length(hoten)) do write('');

writeln(diem:5:2);

ct1:=tiep;

end;

end;

Begin

clrscr;

ctcuoi:=nil; i:=0;

Repeat;

New(dslop); i:=i+1;

With dslop^ do

Begin

writeln('ma ho so:',i);mhs:=i;

write('Ho va ten:'); readln(hoten);

write('diem');readln(diem);

tiep:=ctcuoi;

ctcuoi:=dslop;

writeln('nhap tiep khong?C/K'); tt:=readkey;

writeln;

end;

Until tt in ['k','K'];

Hien_lifo;

Readln;

END.

• Hàng đợi Queue-Danh sách liên kết thuận:

Là loại danh sách mà phần tử nào nhập trước thì được lấy ra trước.

Ctdau:=nil; {khởi tạo danh sách};

Bắt đầu lặp:

New (dslop); {tạo biến động lưu trữ dữ liệu nhập vào}

Nhập dữ liệu; {nhập dữ liệu cho phần tử thứ i}

Nếu ctdau=Nil thì ctdau:=dslop;

Ngược lại ctcuoi^.tiep:=dslop;

Ctcuoi:=dslop;

Ctcuoi^.Tiep:=nil; Ctcuoi:=dslop; {hướng ctcuoi vào bản ghi hiện thời}

Kết thúc lặp.

• Chèn thêm phần tử vào danh sách:

Quá trình chèn một phần tử vào danh sách qua các bước sau:

- Xác định vị trí chèn

- Tạo một biến động và xin cấp phát vùng nhớ cho biến động để lưu dữ liệu sẽ chèn vào danh sách.

- Chuyển trường Tiep của phần tử hiện thời đến phần tử bổ sung

- Chuyển trường Tiep của phần tử bổ sung đến phần tử trước phần tử hiện thời.

New(ct1);

With ct1^ do Nhập dữ liệu cho phần tử bổ sung

Dslop:=ctcuoi; {hướng con trỏ đến phần tử cuối cùng trong danh sách}

While (dslop<>nil) and (dslop^.mhs<>n) do

Dslop:=dslop^.tiep; {hướng con trỏ đến vị trí cần chèn}

Ct1^.tiep:=dslop^.tiep;

Dslop^.tiep:=ct1;