ket hop struct va union

ffff

Con trỏ đa cấp - Mảng hai chiều [Pointers to pointers - Two dimention array]

Con trỏ đa cấp là gì?

Để các bài viết thống nhất với nhau và tiện trong việc sử dụng câu chữ tôi sẽ gọi là "Pointer đa cấp" thay vì "Con trỏ đa cấp".

Chúng ta đã biết rằng pointer đơn giản chỉ là một phiên bản mở rộng của variable, do đó, một pointer cũng hoàn toàn có thể trỏ vào một pointer khác, một pointer như thế thì được gọi là một pointer đa cấp. Pointer là một trường hợp của Pointer đa cấp có tên là Pointer một cấp.

Khái niệm pointer đa cấp (pointers to pointers) có lẽ khá xa lạ với nhiều bạn sinh viên, không phải vì nó không hữu ích mà vì qui mô các bài toán ở giảng đường ít khi cần tới nó. Pointer đa cấp là một công cụ tuyệt vời giúp bạn giải quyết các vấn đề thực tế liên quan đến mảng hai chiều một cách mềm dẻo và hiệu quả.

Khai báo Pointer đa cấp

Việc sử dụng con trỏ đa cấp là tương tự nhau, do đó trong bài này tôi sẽ chỉ đề cập đến pointer 2 cấp (pointer to a pointer). Để khai báo một pointer hai cấp bạn phải thêm hai giấu '*' trước tên của nó.
VD1: int **p_p_parameter;

Sử dụng Pointer đa cấp

Để dễ hiểu nhất, chúng ta sẽ phân tích cách sử dụng pointer hai cấp thông qua ví dụ sau.
VD2:
Khai báo variable parameter, pointer p_parameter và poiter hai cấp p_p_prameter.

int parameter[100];       // variable

int *p_parameter;         // pointer một cấp

int **p_p_parameter;   // pointer hai cấp

Pointer hai cấp không thể trỏ trực tiếp tới variable như pointer được

p_p_parameter = &parameter;  // lỗi

p_parameter = &parameter;  // không lỗi

Pointer hai cấp quản lý variable thông qua pointer một cấp làm trung gian

p_parameter = &parameter;      // pointer trỏ tới variable

p_p_parameter = &p_parameter;  // pointer hai cấp trỏ tới pointer một cấp
Sau hai câu lệnh này p_p_parameter đã trỏ tới vùng nhớ của parameter.

[ thêm hinh vẽ mô tả bộ nhớ]

p_p_parameter truy cuất mảng parameter[100] gián tiếp qua pointer p_parameter 

int parameter[100];       // variable

int *p_parameter;         // pointer một cấp

int **p_p_parameter;   // pointer hai cấp

parameter[0] = 101;
parameter[1] = 1001;
p_parameter = &parameter;      

p_p_parameter = &p_parameter; 

printf("parameter[0]=%d\n",**p_p_parameter );

p_parameter++;                               // pointer 1 cấp truy xuất địa chỉ mới của variable

printf("parameter[1]=%d\n",**p_p_parameter);  
kết quả in ra sẽ là:
parameter[0] = 101;
parameter[1] = 1001;

Ví dụ trên chỉ là mô hình đơn giản để bạn hiểu về pointer hai cấp, trong hầu hết các trường hợp thực tế người ta chỉ ứng dụng pointer hai cấp trong các bài toán liên quan mảng hai chiều.

Cấp phát bộ nhớ cho pointer hai cấp 

Bộ nhớ được cấp phát cho
B1: cấp phát ô nhớ kiểu pointer

p_p_parameter = new int*[5];

tức là bước này sẽ cấp phát các ô nhớ, nhưng các ô nhớ đó được định nghĩa như các pointer chứ không phải là variable vì pointer 2 cấp chỉ có thể trỏ tới pointer 1 cấp

B2: cấp phát ô nhớ variable

các ô nhớ pointer có thể trỏ tới các ô nhớ variable 

p_p_prameter = new int;

chung ta thay rang pointer 2 cap quan ly 1 vung nho giong nhu 1 mang hai chieu, day chinh la ung dung chinh cua pointer 2 cap de tra loi cau hoi 1 tren.

Giải phóng bộ nhớ pointer hai cấp

lam sao để free con trỏ 2 cấp

free con trỏ 1 cấp trước

free(p_p_parameter[i]);

free(p_p_parameter);

So sánh pointer hai cấp với mảng hai chiều

Vấn đề đặt ra là hoàn toàn có thể khai báo 1 mảng hai chiều nhanh chóng để sử dụng, vậy lúc nào dùng pointer 2 cấp lúc nào khai báo trực tiếp:

-khi chưa biết trước kích thước của mảng và cần hiệu quả trong sử dụng bộ nhớ.

Đệ qui

       

            int i;
for (i=0;I<100 data-blogger-escaped-code="" data-blogger-escaped-i="">
 ---------------------------------------------------------------------------------------------------------------------

lan nay ta se

Ưu nhược điểm của cây nhị phân

d

Sử dụng cây nhị phân như thế nào?

ee

Cây nhị phân (Binary tree)

Binary tree là sản phẩm hoàn hảo của việc ứng dụng đệ qui  kết hợp với con trỏ, nó ra đời để cải tiến nhược điểm của cấu trúc tiền nhiệm "danh sách liên kết", vậy nhược điểm của danh sách liên kết là gì? tại sao cần cải tiến?
để rõ hơn hãy xem bài toán sau:

Bài toán tìm kiếm:

Đề bài: "Viết chương trình để tìm kiếm toàn bộ thông tin về một người bất kỳ trên thế giới thông qua ID của họ, giả sử mỗi người có một ID khác nhau, được đánh số bắt đầu từ 0 và tăng dần".

Lời giải:

Trước khi biết đến Binary tree, danh sách liên kết là khái niệm đầu tiên mà bạn có thế nghĩ đến để giải quyết bài toán này, bạn sẽ phải tạo ra một danh sách liên kết mà mỗi node sẽ chứa toàn bộ thông tin và ID tương ứng của một người cụ thể, khi đó, nếu muốn tìm kiếm thông tin về một người việc của bạn chỉ là duyệt tuần tự qua tất cả các node và so sánh ID cho đến khi tìm ra node có ID trùng khớp. Xong!

Nhưng:

Hiện nay thế giới có khoảng 6 tỷ người, tức là danh sách liên kết của bạn sẽ có xấp xỉ 6 tỷ node, giả sử thời gian để bạn so sánh ID của một người là 1s, nếu may mắn thông tin của người cần tìm ở node thứ 100 thì bạn chỉ mất gần 2 phút để tìm ra, khá lâu nhưng cũng chấp nhận được, còn giả sử thông tin đó ở node thứ 4 tỷ, vậy bạn mất 4 tỷ giây tương đương 125 năm để tìm ra thông tin về người đó, đây chính là nhược điểm không thể chấp nhận được của danh sách liên kết.

Yêu cầu:

"Phải tìm ra kết quả trong khoảng thời gian nhỏ hơn 1 phút (<60s)".
Yêu sách này là bất khả thi với danh sách liên kết, nhưng Binary tree thì không, thậm chí nó còn có thể làm tốt hơn.

Binary tree là gì?

Giống như tên của nó, mỗi node trong cây nhị phân sẽ trỏ đến hai node tiếp theo, giống như 2 cành rẽ ra từ một thân cây. Hình 1 mô tả một Binary tree đơn giản nhất, trong đó node_0 là parent node của toàn bộ cây, node_1 và node_2 là children node của node_0.

Hình 1: Binary tree đơn giản nhất

Chú ý: Các node phải phân bố theo qui tắc children node bên trái có giá trị nhỏ hơn parent node, children node bên phải có giá trị lớn hơn parent node.

Hình 2: Blance binary tree

Trong Hình 2, node_2 vừa đóng vai trò là children node của node_0 và là parent node của node_5 và node_6, tổ hợp node_2, node_5, node_6 được gọi là một sub-tree, mỗi sub-tree đề có đầu đủ tính năng giống như một Binary tree hoàn chỉnh, hay nói cách khác "một Binary tree là tập hợp của nhiều Binary tree". Điều đó khiến ta liên tưởng đến tính đệ qui "Một hàm gọi chính nó nhiều lần", nhưng giờ vẫn quá sớm, chúng ta sẽ nhắc tới vấn đề này sau ^^.

Giải quyết bài toán tìm kiếm

Balance binary tree - Hình 2 là một binary tree lý tưởng, nghĩa là số lượng node bên trái bằng số lượng node bên phải và parent node của toàn bộ binary tree sẽ có giá trị chính giữa khoảng giá trị của tất cả các node (Hình 2 mô tả ba tầng trên của một balance binary tree có 6 tỷ node, parent node của toàn bộ binary tree có giá trị là 3 tỷ). 

Quay lại với bài toán ban đầu: Bạn sẽ bắt đầu tìm kiếm tại parent node của toàn bộ binary tree, đầu tiên bạn sẽ so sánh ID cần tìm với ID của parent node đầu tiên đó, bạn thấy 4 tỷ > 3 tỷ do đó ngay lập tức bạn loại bỏ được sub-tree bên trái vì sub-tree bên tái chỉ chứa các ID nhỏ hơn 3 tỷ, giờ bạn chỉ quan tam sub-tree bên phải mà thôi.

Tiếp theo bạn sẽ tiếp tục so sánh với ID của parent node đầu tiên của sub-tree bên phải (children node bên phải của parent node toàn bộ binary tree), vì 4 tỷ < 4.5 tỷ do đó bạn tiếp tục loại bỏ được 1.5 tỷ trường hợp tiếp theo.
Cứ như vậy, sau mỗi lần so sánh bạn sẽ loại bỏ được một nữa số trường hợp không đúng, đo đó sẽ rất nhanh chóng để bạn tìm ra kết quả.

Số lần thực hiện so sánh tối đa để tìm ra kết quả là log2(6000000000) = 32, tức bạn phải mất tối đa 32s để tìm thông tin bất kỳ về một người nào.
Kết quả thât ấn tượng, trong trường hợp này nó hoàn toàn thỏa mãn yêu cầu < 60s.

Ứng dụng của Pointer - Tham chiếu

Tham chiếu tới variable (Trỏ vào một variable)

Sử dụng con trỏ để tham chiếu tới một variable được mô tả như hình 2.

Hình 2: Tham chiếu tới một variable thông qua Pointer

Biến val được khai báo tại ô nhớ 0xFE và có giá trị là 5, con trỏ ptr được khai báo tại ô nhớ 0x83 và có giá trị 0xFE.

Ta có thể thấy rằng pointer và variable được tổ chức giống nhau trên bộ nhớ (có một ô nhớ chứa giá trị và một đỉa chỉ truy xuất tới ô nhớ đó), chỉ khác là thay vì chứa giá trị sử dụng (val=5) như các variable thì Pointer chứa địa chỉ của một variable khác (ptr=0xFE).

Truy xuất địa chỉ của variable sử dụng ký tự &, ví dụ: &val
Truy xuất địa chỉ của giá trị tại ô nhớ mà pointer trỏ vào sử dụng ký tự *, ví dụ: *ptr

Thông qua pointer ta có thể truy xuất và gán giá trị cho variable như ví dụ sau:

       
#include "stdio.h"
int main()
{
    int var = 10;
    int *ptr;
    
    ptr = &var;
    printf("dia chi cua var = 0x%x \n\r",ptr);
    printf("gia tri cua var = %d \n\r",*ptr);
    
    *ptr = 100;
    printf("dia chi cua var = 0x%x \n\r",&var);
    printf("gia tri cua var = %d \n\r",var);
    return 0;
}

Kết quả in ra là

       
   dia chi cua var = 0x28ff18
   gia tri cua var = 10
   dia chi cua var = 0x28ff18
   gia tri cua var = 100

Quản lý mảng 

Bằng cách trỏ vào phần tử đầu tiên của mảng, một con trỏ hoàn toàn có thể truy xuất và gán giá trị cho các phần tử khác trong mảng nhanh chóng và linh hoạt.

Hình 1: Tham chiếu tới các phần tử của mảng thông qua Pointer

Trong ví dụ trên ta thấy con trỏ ptr được trỏ tới mảng array, khi đó muốn truy xuất giá trị một phần tử trong mảng array ta có thể thực hiện thông qua con trỏ,

VD:
Gán phần thử array[1] = 5 ta có thể thực hiện bằng cách *(++ptr)=5; như đoạn code sau

       
#include "stdio.h"
int main()
{
    int array[3] = {0};
    int *ptr;
    ptr=array;
    *(++ptr) = 5;
    printf("array[1] = %d",array[1]);
    return 0;
}

Kết quả in ra là array[1] = 5 , với cách làm tương tự bạn hoàn toàn có thể truy xuất và gán giá trị cho các phần tử khác của mảng array.

Kỹ thuật tham chiếu được sử dụng rất phổ biến trong xử lý mảng, nó giúp chương trình tối ưu và hiệu quả hơn.