Con trỏ

Con trỏ và cấu trúc động
Các thành viên tham gia:
Ngô Thanh Giang
Tạ Tuấn Dũng
Đặng Ngọc Quý
Đặng Vũ Trường An
Trần Quang Trí
Đỗ Ngọc Tuấn
Lê Hồng Quân
Nguyễn Thị Phương Loan
Các phần chính sẽ giới thiệu
1/ Khái niệm
2/ Kiểu con trỏ - Biến con trỏ
3/ Các thủ tục và hàm tác động lên con trỏ
4/ Truy nhập dữ liệu
5/ Mảng con trỏ và con trỏ kiểu mảng
6/ Cấp phát động
1/ Khái niệm
Khi khai báo 1 biến, dù là biến đơn hay biến thuộc kiểu dữ liệu có cấu trúc mặc nhiên ta đã quy định độ lớn vùng nhớ dành cho biến.
Việc khai báo 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ớ. Việc xác định địa chỉ lưu trữ biến và cấp phát bộ nhớ cần cấp phát đã được cố định trước khi thực hiện các thao tác khác. Các đại lượng này không thay đổi trong suốt quá trình thực hiện chương trình, nói cách khác đây là các đại lượng tĩnh.
Do đó, để 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 được 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ỏ, chúng ta phái thông qua kiểu con trỏ.
2/ Kiểu dữ liệu con trỏ
biến con trỏ
2.1 Kiểu dữ liệu con trỏ, biến con trỏ
Kiểu con trỏ là 1 kiểu dữ liệu đặc biệt dùng để biểu diễn các địa chỉ. Kiểu con trỏ do người lập trình định nghĩa theo cú pháp sau:
Type tên kiểu con trỏ=^kiểu dữ liệu;
Tên kiểu con trỏ tuân theo quy định đặt tên của pascal, kiểu dữ liệu của kiểu con trỏ là các kiểu dữ liệu đã định nghĩa trước trong pascal. Để 1 kiểu con trỏ có thể đại diện cho 1 biến nào đó thì kiểu dữ liệu viết sau kí tự ^ sẽ phải giống như kiểu dữ liệu của biến đó, tức là 2 kiểu dữ liệu phải tương thích.
Ví dụ:
Chu=string[20]; ct1=^byte; ct2=^chu;
ct3=^nguoi;nguoi=record;
Qua ví dụ trên ta thấy pascal cho phép định nghĩa kiểu con trỏ trước, định nghĩa kiểu con trỏ sau chứ không nhất thiết luôn phải định nghĩa kiểu dữ liệu trước kiểu con trỏ sau.

Tuy nhiên ta cần lưu ý rằng chỉ có thể đư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 muốn có cấu trúc muốn đưa vào con trỏ thì phải thông qua 1 tên kiểu khai báo trong phần type.
Type
s1=string[20];
Ht=^s1;
a=array[1..100]of byte;
ds=^a;
2.2 Biến con trỏ
Biến con trỏ cũng như biến mảng, biến kiểu bản ghi hay kiểu tập hợp có thể khai báo thông qua kiểu con trỏ hoặc khai báo trực tiếp. Biến con trỏ có định kiểu sẽ trỏ đến 1 kiểu dữ liệu cụ thể.
Để thuận tiện từ nay ta dùng thuật ngữ “con trỏ” thay cho thuật ngữ “biến con trỏ”.
Lưu ý: địa chỉ của các biến động và biến tĩnh sẽ được pascal lưu trữ vào biến con trỏ điều này có nghĩa là biến con trỏ không dùng để lưu giá trị của các biến mà là địa chỉ của các 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 thế nào thì kích thước của biến con trỏ cũng vẫn là 4 byte.
2.3 Con trỏ không định kiểu
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. Pascal dùng tên chuẩn pointer để khai báo kiểu này.
Var tên biến:pointer;
Con trỏ không định kiểu được coi là tương thích với mọi kiểu con trỏ.
* Chú ý: Về bản chất tất cả con trỏ đều chứa địa chỉ nên chúng không khác nhau song để tránh nhầm lẫn trong các quá trình xử lí pascal chỉ coi các con trỏ cùng trỏ tới 1kiểu dữ liệu là tương thích nhau.
2.4 Địa chỉ của 1 đối tượng.
Đối tượng đề cập trong mục này có thể là biến, hàm hay thủ tục. Khi biên dịch chương trình mỗi đối tượng được cấp phát 1 vùng nhớ, vùng nhớ này bao gồm 1 số ô nhớ liền kề nhau.
Địa chỉ 1 đố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 đó.
Bộ nhớ hiện nay là rất lớn và chúng được chia thành nhiều đoạn có 65536 ô nhớ (216 ô). Ô đầu tiên của mỗi đoạn có địa chỉ là 0 do đó ô cuối cùng có địa chỉ là 65536. Như vậy, để biết địa chỉ 1 ô nhớ cần biết ô nhớ đó thuộc đoạn nào và đó là ô nhớ số bao nhiêu trong đoạn đó.
Địa chỉ đoạn gọi là segment và địa chỉ tương đối của ô nhớ trong đoạn gọi là offset, mỗi giá trị này dùng 2 byte để lưu trữ nên 1 địa chỉ cần 4 byte, 2 byte thấp cho offset, 2 byte cao cho segment.
Địa chỉ đoạn gọi là segment và địa chỉ tương đối của ô nhớ trong đoạn gọi là offset, mỗi giá trị này dùng 2 byte để lưu trữ nên 1 địa chỉ cần 4 byte, 2 byte thấp cho offset, 2 byte cao cho segment.
Nếu ghi địa chỉ bằng các số nhị phân thì chúng ta dùng 32 chữ số 0 và 1, điều này khá là phiền phức do vậy người ta dùng hệ cơ số 16. Cách ghi địa chỉ ô nhớ được quy ước như sau: địa chỉ đoạn viết trước, vị trí của ô trong đoạn viết sau, kí hiệu $ được thêm vào trước các giá trị số để thể hiện rằng các số viết trong hệ 16.
3/ Các thủ tục và hàm
tác động lên con trỏ
3.1 Gán giá trị đầu.
Giả sử ct là 1 biến con trỏ đã được định nghĩa, để đảm bảo rằng ct chưa trỏ đến bất kì 1 đối tượng nào, nghĩa là ct là 1 con trỏ rỗng ta gán cho ct giá trị NIL.
ct:=Nil;
3.2 Gán địa chỉ 1 đối tượng cho con trỏ.
Có 3 cách gán địa chỉ của đối tượng x cho con trỏ ct.
a. ct:=@x;
Trong phép gán trên toán tử @ tác động trên đối tượng x sẽ gán vào con trỏ ct địa chỉ kiểu pointer của đối tượng đó.
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,offset);
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.
2 phép gán @ và addr cùng trả về địa chỉ kiểu pointer nên chúng tương đương.
3.3 Phép gán giữa 2 con trỏ.
2 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 1 địa chỉ.
VD: ct1:^float;
ct2:^byte;
ct3:^pointer;
x:string;
Phép gán hợp lệ: ( cùng trỏ tới địa chỉ của x )
ct3:=@x;
ct2:=ct3;
Phép gán không hợp lệ: ( không tương thích )
ct1:=ct2;
3.4 Phép so sánh giữa 2 con trỏ.
Chỉ tồn tại phép so sánh = và <> giữa 2 con trỏ nếu chúng tương thích. Kết quả so sánh là 1 giá trị boolean nghĩa là true hoặc false.
4/ Truy nhập dữ liệu
Khi con trỏ ct đang trỏ tới 1 vùng dữ liệu nào đó pascal cho phép dùng kí hiệu ct^ như là 1 biến để truy nhập vào vùng dữ liệu đó. Biến ct^ mang trong nó 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 1 biến, hàm hay 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.
Đến đây cần có sự phân biệt chính xác về biến con trỏ CT và biến CT^ . Biến con trỏ CT mang trong nó địa chỉ của đối tượng mà nó trỏ tới, còn biến CT^ lại chứa đựng dữ liệu trong vùng nhớ mà con trỏ CT^ đang trỏ tới.
Với con trỏ có kiểu tất cả các thao tác trên biến, hàm hay thủ tục mà con trỏ đang trỏ tới có thể thay thế bởi thao tác trên biến ct^ . Kiểu của biến ct^ chính là kiểu đã khai báo cho con trỏ ct^ chứ không phải là kiểu của đối tượng mà biến ct^ đại diện.
* 1 số kết luận rút ra:
Địa chỉ của 1 đối tượng có thể gán cho bất kì con trỏ nào.
Kết quả mà biến ct^ trả về thuộc kiểu dữ liệu của con trỏ chứ không thuộc kiểu dữ liệu của đối tượng.
Muốn dùng biến ct^ như 1 biến thông thường thay thế cho đối tượng thì biến con trỏ và đối tượng phải tương thích về kiểu.
Với con trỏ không định kiểu ( pointer ) chúng ta không thể coi chúng là tương đương với các biến định kiểu thông thường, điểu này có nghĩa là không thể dùng các thủ tục write, read hoặc phép gán cho biến ct^ nếu con trỏ là pointer
5/ Mảng con trỏ và
con trỏ kiểu mảng
5.1 Con trỏ kiểu mảng
Khai báo:
Type m=array[1..5] of byte;
Var ct1:^m;
Với cách khai báo trên 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à 1 số kiểu byte. Việc truy nhập vào biến ct1^ thực chất là truy nhập vào từng phần tử.
VD: read(ct1^[i]); hoặc write(ct1^[i]); (1<=i<=5)
5.2 Mảng các con trỏ
Khai báo:
Var ct:array[1..10]of ^string;
s1,s2:string;
Cách khai báo trên cho ta ct là mảng của 10 con trỏ, tất cả đều là trỏ tới kiểu dữ liệu string. Mỗi con trỏ có thể trỏ đến 1 đối tượng khác nhau. Trong trường hợp này cách truy nhập dữ liệu cần thận trọng.

Nếu chúng 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; thì tất cả 10 con trỏ đều trỏ tới biến s1.
Khi đó các lệnh
Write(ct[1]^);Write(ct[2]^);.. Cho kết quả như nhau.

Trong trường hợp chúng ta gán dữ liệu từ 1 đối tượng cho nhiều biến con trỏ thì tất cả các con trỏ đều 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ó con trỏ ct[1] là trỏ tới biến s2, các con trỏ khác chưa trỏ vào đâu cả.