Cấu trúc dữ liệu động

Biến không động (biến tĩnh, biến nửa tĩnh):

Khi xây dựng chương trình, lập trình viên có thể xác định được ngay những đối tượng dữ liệu luôn cần được sử dụng, không có nhu cầu thay đổi về số lượng kích thước .... do đó có thể xác định cách thức lưu trữ chúng ngay từ đầu. Các đối tượng dữ liệu này sẽ được khai báo như các biến không động. Biến không động là những biến thỏa:

+Ðược khai báo tường minh,

+Tồn tại khi vào phạm vi khai báo và chỉ mất khi ra khỏi phạm vi này,

+Ðược cấp phát vùng nhớ trong vùng dữ liệu (Data segment) hoặc là  Stack (đối với biến nửa tĩnh - các biến cục bộ).

+Kích thước không thay đổi trong suốt quá trình sống.

Do được khai báo tường minh, các biến không động có một định danh đã được kết nối với địa chỉ vùng nhớ lưu trữ biến và được truy xuất trực tiếp thông qua định danh đó.

Ví dụ  :  a, b là các biến không động

int       a;                   

          char     b[10];

Kiểu con trỏ

•   Cho trước kiểu T = <V,O>. Kiểu con trỏ - ký hiệu "Tp"- chỉ đến các phần tử có kiểu "T" được định nghĩa:

Tp = <Vp, Op>

trong đó

-         Vp = {{các điạ chỉ có thể lưu trữ  những  đối tượng có kiểu T}, NULL} (với NULL là một giá trị đặc biệt tượng trưng cho một giá trị không biết hoặc không quan tâm)

-         Op = {các thao tác định địa chỉ của một đối tượng thuộc kiểu T khi biết con trỏ chỉ đến đối tượng đó} (thường gồm các thao tác tạo một con trỏ chỉ đến một đối tượng thuộc kiểu T;  hủy một đối tượng dữ liệu thuộc kiểu T khi biết con trỏ chỉ đến đối tượng đó}

•  Nói một cách dễ hiểu, kiểu con trỏ là kiểu cơ sở dùng lưu địa chỉ của một đối tượng dữ liệu khác.
•  Biến thuộc kiểu con trỏ Tp là biến mà giá trị của nó là địa chỉ cuả một vùng nhớ ứng với một biến kiểu T, hoặc là  giá trị NULL.

LƯU Ý :

Kích thước của biến con trỏ tùy thuộc vào quy ước số byte địa chỉ trong từng mô hình bộ nhớ của từng ngôn ngữ lập trình cụ thể..

Ví dụ:

-          biến con trỏ trong Pascal có kích thước 4 bytes (2 bytes địa chỉ segment + 2 byte địa chỉ offset)

-          biến con trỏ trong C có kích thước 2 hoặc 4 bytes tùy vào con trỏ near (chỉ lưu địa chỉ offset) hay far (lưu cả segment lẫn offset)

Cú pháp định nghĩa một kiểu con trỏ trong ngôn ngữ C :

typedef  <kiểu con trỏ>  *<kiểu cơ sở>;

Ví dụ :             

typedef     int      *intpointer;

intpointer  p;

hoặc

int      *p;

là những khai báo hợp lệ.

Các thao tác cơ bản trên kiểu con trỏ:(minh họa bằng C)

•        Khi 1 biến con trỏ p lưu địa chỉ của đối tượng x, ta nói ?p trỏ đến x?
•  Gán địa chỉ của một vùng nhớ con trỏ p:  

p = <địa chỉ>;

p = <địa chỉ> + <giá trị nguyên>;

•  Truy xuất nội dung của đối tượng do p trỏ đến (*p)

Biến động

•    Trong nhiều trường hợp, tại thời điểm biên dịch không thể xác định trước kích thước chính xác của một số đối tượng dữ liệu do sự tồn tại và tăng trưởng của chúng phụ thuộc vào ngữ cảnh của việc thực hiện chương trình. Các đối tượng dữ liệu có đặc điểm kể trên nên được khai báo như biến động.

 Biến động là những biến thỏa:

• •    Biến không được khai báo tường minh.
  •   Có thể được cấp phát hoặc giải phóng bộ nhớ khi người sử dụng yêu cầu.               
  •   Các biến này không theo qui tắc phạm vi (tĩnh).
  • Vùng nhớ của biến được cấp phát trong Heap.
  • Kích thước có thể thay đổi trong quá trình sống.
•          Do không được khai báo tường minh nên các biến động không có một định danh được kết buộc với địa chỉ vùng nhớ cấp phát cho nó, do đó gặp khó khăn khi truy xuất đến một biến động. Ðể giải quyết vấn đề, biến con trỏ (là biến không động) được sử dụng để trỏ đến biến động. Khi tạo ra một biến động, phải dùng một con trỏ để lưu địa chỉ của biến này và sau đó, truy xuất đến biến động thông qua biến con trỏ đã biết định danh.
•          Hai thao tác cơ bản trên biến động là tạo và hủy một biến động do biến con trỏ ?p? trỏ đến:
• Tạo ra một biến động và cho con trỏ ?p? chỉ đến nó:

Hầu hết các ngôn ngữ lập trình cấp cao đều cung cấp những thủ tục cấp phát vùng nhớ cho một biến động và cho một con trỏ giữ địa chỉ vùng nhớ đó.

Một số hàm cấp phát bộ nhớ của C :

void* malloc(size);  // trả về con trỏ chỉ đến một vùng

                                                      // nhớ size byte vừa được cấp phát.

void* calloc(n,size);// trả về con trỏ chỉ đến một vùng

                                                        // nhớ vừa được cấp phát gồm n

                                                        //phần tử,   mỗi phần tử có kích

                                           //thước size byte

new                   // hàm cấp phát bộ nhớ trong C++

• Hủy một biến động do p chỉ đến :

Hàm free(p) huỷ vùng nhớ cấp phát bởi hàm malloc hoặc calloc do p trỏ tới

Hàm delete p huỷ vùng nhớ cấp phát bởi hàm new do p trỏ tới

• Ví dụ :

int*    p1, p2;

// cấp phát vùng nhớ cho 1 biến động kiểu int

p1 = (int*)malloc(sizeof(int));

p1* = 5;       // đặt giá trị 5 cho biến động p1

// cấp phát biến động kiểu mảng gồm 10 phần tử kiểu int

p2 = (int*)calloc(10, sizeof(int));

(p2+3)* = 0; // đặt giá trị 0 cho phần tử thứ 4                                   // của mảng p2

free(p1); free(p2);

Ðịnh nghĩa:

Cho T là một kiểu được định nghiã trước, kiểu danh sách Tx gồm các phần tử thuộc kiểu T được định nghĩa là:

Tx = <Vx, Ox>

trong đó:

Vx = {tập hợp có thứ tự các phần tử kiểu T được móc nối với nhau theo trình tự tuyến tính};

Ox = {Tạo danh sách; Tìm 1 phần tử trong danh sách; Chèn một phần tử vào danh sách; Huỷ một phần tử khỏi danh sách ; Liệt kê danh sách, Sắp xếp danh sách ...}

Ví du: Hồ sơ các học sinh của một trường được tổ chức thành danh sách gồm nhiều hồ sơ của từng học sinh; số lượng học sinh trong trường có thể thay đổi do vậy cần có các thao tác thêm, hủy một hồ sơ; để phục vụ công tác giáo vụ cần thực hiện các thao tác tìm hồ sơ của một học sinh, in danh sách hồ sơ ...

Các hình thức tổ chức danh sách

Có nhiều hình thức tổ chức mối liên hệ tuần tự giữa các phần tử trong cùng một danh sách:

•   Mối liên hệ giữa các phần tử được thể hiện ngầm: mỗi phần tử trong danh sách được đặc trưng bằng chỉ số. Cặp phần tử  x_i, x_i+1 được xác định là kế cận trong danh sách nhờ vào quan hệ giữa cặp chỉ số i và (i+1). Với hình thức tổ chức này, các phần tử của danh sách thường bắt buộc phải lưu trữ liên tiếp trong bộ nhớ để có thể xây dựng công thức xác định địa chỉ phần tử thứ i:

address(i) = address(1) + (i-1)*sizeof(T)

Có thể xem mảng và tập tin là những danh sách đặc biệt được tổ chức theo hình thức liên kết "ngầm" giữa các phần tử. Tuy nhiên mảng có một đặc trưng giới hạn là số phần tử mảng cố định, do vậy không có thao tác thêm, hủy trên mảng; trường hợp tập tin thì các phần tử được lưu trữ trên bộ nhớ phụ có những đặc tính lưu trữ riêng sẽ được trình bày chi tiết ở giáo trình Cấu trúc dữ liệu 2.

Cách biểu diễn này cho phép truy xuất ngẫu nhiên, đơn giản và nhanh chóng đến một phần tử bất kỳ trong danh sách, nhưng lại hạn chế về mặt sử dụng bộ nhớ. Ðối với mảng, số phần tử được xác định trong thời gian biên dịch và cần cấp phát vùng nhớ liên tục. Trong trường hợp tổng kích thước bộ nhớ trống còn đủ để chứa toàn bộ mảng nhưng các ô nhớ trống lại không nằm kế cận nhau thì cũng không cấp phát  vùng nhớ cho mảng được. Ngoài ra do kích thước mảng cố định mà số phần tử của danh sách lại khó dự trù chính xác nên có thể gây ra tình trạng thiếu hụt hay lãng phí bộ nhớ. Hơn nữa các thao tác thêm, hủy một phần tử vào danh sách được thực hiện không tự nhiên trong hình thức tổ chức này.

•  Mối liên hệ giữa các phần tử được thể hiện tường minh: mỗi phần tử ngoài các thông tin về bản thân còn chứa một liên kết (địa chỉ) đến phần tử kế trong danh sách nên còn được gọi là danh sách móc nối. Do liên kết tường minh, với hình thức này các phần tử trong danh sách không cần phải lưu trữ kế cận trong bộ nhớ nên khắc phục được các khuyết điểm của hình thức tổ chức mảng, nhưng việc truy xuất đến một phần tử đòi hỏi phải thực hiện truy xuất qua một số phần tử khác. Có nhiều kiểu tổ chức liên kết giữa các phần tử trong danh sách như  :

   Danh sách liên kết đơn: mỗi phần tử liên kết với phần tử đứng sau nó trong danh sách:

  Danh sách liên kết kép: mỗi phần tử liên kết với các phần tử đứng trước và sau nó trong danh sách:

Danh sách liên kết vòng : phần tử cuối danh sách liên kết với phần tử đầu danh sách:         

Hình thức liên kết này cho phép các thao tác thêm, hủy trên danh sách được thực hiện dễ dàng, phản ánh được bản chất linh động của danh sách.