0.4 Kiểu dữ liệu có cấu trúc  (Page 11/15)

Ðối với chuỗi có độ dài không giới hạn thì sử dụng biểu diễn bộ nhớ liên kết với bộ mô tả chứa độ dài hiện tại của chuỗi.

Giải thuật thực hiện các phép toán

Thông thường phần cứng hỗ trợ cho việc biểu diễn chuỗi có độ dài cố định nhưng đối với các biểu diễn khác cho chuỗi thì phải được mô phỏng bởi phần mềm. Các phép toán ghép, chọn chuỗi con và so mẫu phải mô phỏng bởi phần mềm.

Cấu trúc dữ liệu có kích thước thay ðổi

CTDL có kích thước thay đổi là một cấu trúc mà trong đó số lượng các phần tử có thể thay đổi một cách động trong quá trình thực hiện chương trình.

Một số kiểu chủ yếu của cấu trúc dữ liệu có kích thước thay đổi là:

Danh sách và cấu trúc danh sách

Danh sách là một CTDL tuyến tính với số lượng thay đổi của các phần tử có kiểu giống nhau.

Nếu các phần tử của một danh sách lại là một danh sách thì được gọi là cấu trúc danh sách (list structures).

Các phần tử có thể được thêm vào hoặc xóa khỏi một danh sách. Các phần tử có thể được lựa chọn từ một danh sách nhưng vì vị trí của phần tử trong danh sách có thể bị thay đổi do phép thêm và xóa các phần tử nên không thể sử dụng chỉ số để xác định phần tử. Thay vào đó, việc lựa chọn dựa trên cơ sở của mối quan hệ của vị trí của phần tử với danh sách chẳng hạn phần tử đầu, hai, ba, kế hặc cuối. Biểu diễn bộ nhớ liên kết cho danh sách và cấu trúc danh sách được dùng một cách phổ biến để phù hợp với sự thay đổi số lượng các phần tử.

Ngăn xếp và hàng đợi

Ngăn xếp là một danh sách mà trong đó việc lựa chọn, thêm, xóa phần tử được thực hiện ở 1 đầu của danh sách.

Do việc thêm, xóa phần tử chỉ được thực hiện ở một đầu của ngăn xếp, nên phần tử được đưa vào sau, sẽ được lấy ra trước. Do vậy ngăn xếp còn được gọi là cấu trúc dữ liệu kiểu LIFO (Last In, First Out).

Hàng đợi là một danh sách mà trong đó việc lựa chọn, và xóa phần tử được thực hiện ở một đầu còn việc thêm phần tử được thực hiện ở đầu khác của danh sách.

Do việc xóa phần tử được thực hiện ở một đầu (đầu của hàng) còn việc thêm phần tử được thực hiện ở cuối hàng, nên phần tử được đưa vào trước, sẽ được lấy ra trước. Do vậy hàng đợi còn được gọi là cấu trúc dữ liệu kiểu FIFO (First In, First Out).

Cả hai phương pháp biểu diễn tuần tự và liên kết đều được dùng cho ngăn xếp và hàng đợi.

Con trỏ

Cấp phát tĩnh, cấp phát động và con trỏ

Cấp phát bộ nhớ (gọi tắt là cấp phát) là sự dành riêng các ô nhớ của bộ nhớ cho chương trình sử dụng.

Thông thường các ô nhớ được cấp phát để lưu trữ giá trị dữ liệu của biến. Có hai phương pháp cấp phát là cấp phát tĩnh và cấp phát động.

Cấp phát tĩnh là sự cấp phát ô nhớ cho ÐTDL được thực hiện trong quá trình dịch.

Trong khi biên dịch, thông qua sự khai báo biến, bộ dịch xác định được kiểu dữ liệu của ÐTDL nên sẽ dành sẵn một khối ô nhớ đủ lớn để lưu trữ ÐTDL của kiểu này.

Người lập trình sử dụng ô nhớ được cấp phát thông qua tên biến.

Khi khối chương trình, nơi khai báo biến kết thúc thì ô nhớ đã được cấp phát sẽ được tự động giải phóng.

Ưu điểm

Ưu điểm của cấp phát tĩnh là người lập trình dễ sử dụng, cụ thể là người lập trình chỉ cần khai báo biến, chương trình dịch sẽ tự động cấp phát và sau đó tự động giải phóng.