Con trỏ và cấu trúc động

CON TRỎ VÀ CẤU TRÚC ĐỘNG

1. Khái niệm:

Khi khai báo một biến, dù là biến đơn hay biến thuộc kiểu dữ liệu có cấu trúc, ta đã quy định độ lớn vùng nhớ dành cho biến:

VD: a: real; biến a cần 6 byte

B: array[1..100] of integer; biến mảng b cần 200 byte

Việc khai báo như trên thường là phỏng đoán dung lượng cần thiết chứ không thật chính xác, gây nên lãng phí bộ nhớ.

Để tiết kiệm bộ nhớ, ngay khi chương trình đang làm việc, người lập trình có thể yêu cầu cấp phát bộ nhớ cho các biến, điều này gọi là cấp phát bộ nhớ động. Cấp phát bộ nhớ động được thực hiện thông qua biến con trỏ. Muốn có biến con trỏ ta phải định nghĩa kiểu con trỏ.

Kiểu dữ liệu con trỏ-biến con trỏ:

• Con trỏ có định kiểu:

Kiểu con trỏ là một kiểu dữ liệu đặc biệt dùng để biểu diễn các địa chỉ. Kiểu con trỏ được định nghĩa theo cú pháp:

Tên kiểu con trỏ=^Kiểu dữ liệu;

Ví dụ 4.1:

Chu=String[20];

CT1=^Byte;

CT2=^Chu;

CT3=^Nguoi;

Nguoi=record

Hoten:String[20];

Namsinh:1900..2100;

End;

Chú ý: ta chỉ được phép đưa trực tiếp vào định nghĩa kiểu con trỏ các kiểu dữ liệu đơn giản sau: số nguyên, số thực, ký tự. Các kiểu dữ liệu có cấu trúc muốn đưa vào con trỏ thì phải thông qua một tên kiểu khai báo trong phần Type.

Cách định nghĩa 2 kiểu con trỏ Hoten và Ds sau là sai:

Type

Hoten=^String[20];

Ds=Array[1..10] of Byte;

Muốn sử dụng kiểu chuỗi và mảng cho kiểu con trỏ chúng ta phải định nghĩa như sau:

Type

S1=String[20];

Hoten=^S1;

a=array[1..10] of Byte;

Ds=^a;

• Biến con trỏ:

Biến con trỏ có thể khai báo thông qua kiểu con trỏ hoặc khai báo trực tiếp.

Ví dụ 4.2:

Var

So:^integer;

Sinhvien:CT3;

Hoten:CT2;

Thutu, Mahoso:^Word;

Biến con trỏ không dùng để lưu trữ các giá trị của biến mà lưu trữ địa chỉ của biến. Dù kích thước vùng dữ liệu mà các biến con trỏ trỏ tới khác nhau nhưng kích thước của biến con trỏ vẫn là 4 byte.

• Con trỏ không định kiểu:

Là kiểu con trỏ không quan tâm đến kiểu dữ liệu mà nó trỏ tới.

Cách khai báo:

Var tên biến: Pointer;

• Địa chỉ của một đối tượng:

Địa chỉ một đối tượng trong bộ nhớ được xác định bởi địa chỉ của ô nhớ đầu tiên mà hệ thống dành cho đối tượng đó.

$0101	$FFFF
Segment (địa chỉ đoạn)	Offset(địa chỉ tương đối trong đọan)

Địa chỉ ô thứ 65535, thuộc đoạn 257.

Các thủ tục và hàm tác động lên con trỏ:

• Gán giá trị ban đầu:

Ct:=nil;

• Gán địa chỉ của một đối tượng cho con trỏ:

1. ct:=@x;

b. ct:=Addr(x)

Hàm Addr()cho địa chỉ của đối tượng x, địa chỉ này thuộc kiểu Pointer

c. ct:=Ptr(segment):

Hàm Ptr trong phép gán trên đòi hỏi các tham số segment và offset phải là giá trị kiểu Word viết trong hệ 16, ví dụ :

ct:= Ptr($B800,$0000);đưa con trỏ trỏ tới ô nhớ của vùng Video Ram

Nhận xét:

Hai phép gán @ và Addr() cùng trả về địa chỉ kiểu pointer nên chúng là tương đương.

3. 3 phép gán giữa hai con trỏ

Hai con trỏ tương thích (cùng kiểu) có thể gán giá trị cho nhau, khi đó chúng cùng trỏ tới một địa chỉ .

Ví dụ 4.3

Var

ct1:^Float;

ct2:^Byte;

ct3:^Pointer;

x:string;

Ví dụ trên khai báo ba con trỏ thuộc ba kiểu khác nhau, ct1 là con trỏ thực,ct2 là con trỏ nguyên và ct3là con trỏ không định kiểu, x là biến chuỗi. Khi đó các phép gán :

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.

1. 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ả.

1. 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:

1. Phần tử mới được thêm vào đầu danh sách
2. Phần tử mới được thêm vào cuối danh sách.
3. 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 đó.

Phần tử cuối

Dữ liệu

Trường liên kết

Các phần tử trung gian

Dữ liệu

Trường liên kết

Phần tử đầu

NilDữ liệu

Trường liên kết

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;