Kiểu dữ liệu có cấu trúc – Phần 1

Số lượng phần tử

Số lượng các phần tử của một CTDL cho biết kích thước của CTDL, số lượng này có thể cố định hoặc thay đổi tuỳ loại CTDL.

Một CTDL được gọi là có kích thước cố định nếu số lượng các phần tử không thay đổi trong thời gian tồn tại của nó.

Ví dụ các kiểu mảng, mẩu tin là các CTDL có kích thước cố định.

Một CTDL được gọi là có kích thước thay đổi nếu số lượng các phần tử thay đổi một cách động trong thời gian tồn tại của nó.

Ví dụ ngăn xếp, danh sách, tập hợp, chuỗi ký tự và tập tin là các CTDL có kích thước thay đổi. Các phép toán cho phép thêm hoặc bớt các phần tử của cấu trúc làm thay đổi kích thước của cấu trúc.

Kiểu của mỗi một phần tử

Mỗi một phần tử của CTDL có một kiểu dữ liệu nào đó, ta gọi là kiểu phần tử. Kiểu phần tử có thể là một kiểu dữ liệu sơ cấp hoặc một CTDL. Các phần tử trong cùng một CTDL có thể có kiểu phần tử giống nhau hoặc khác nhau.

Một CTDL được gọi là đồng nhất nếu tất cả các phần tử của nó đều có cùng một kiểu.

Ví dụ mảng, chuỗi ký tự, tập hợp và tập tin là các CTDL đồng nhất .

Một CTDL được gọi là không đồng nhất nếu các phần tử của nó có kiểu khác nhau.

Ví dụ mẩu tin là CTDL không đồng nhất.

Tên để dùng cho các phần tử được lựa chọn

Ðể lựa chọn một phần tử của CTDL cho một xử lý nào đó người ta thường sử dụng một tên. Ðối với cấu trúc mảng, tên có thể là một chỉ số nguyên hoặc một dãy chỉ số; đối với mẩu tin, tên là một tên trường. Một số kiểu cấu trúc dữ liệu như ngăn xếp và tập tin cho phép truy nhập đến chỉ một phần tử đặc biệt (phần tử đầu tiên hoặc phần tử hiện hành).

Số lượng lớn nhất các phần tử

Ðối với CTDL có kích thước thay đổi như chuỗi ký tự hoặc ngăn xếp, đôi khi người ta quy định thuộc tính kích thước tối đa của cấu trúc để giới hạn số lượng các phần tử của cấu trúc.

Tổ chức cấu trúc

Tổ chức phổ biến nhất là một dãy tuần tự của các phần tử. Vector (mảng một chiều), mẩu tin, chuỗi ký tự, ngăn xếp, danh sách và tập tin là các CTDL có tổ chức kiểu này.

Một số cấu trúc còn được mở rộng thành dạng "nhiều chiều" ví dụ mảng nhiều chiều, mẩu tin mà các phần tử của nó là các mẩu tin, danh sách mà các phần tử của nó là danh sách.

Phép toán lựa chọn phần tử của cấu trúc

Phép toán lựa chọn một phần tử là phép toán truy nhập đến một phần tử của CTDL và làm cho nó có thể được xử lý bởi một phép toán khác.

Có hai loại lựa chọn:

Lựa chọn ngẫu nhiên (hay còn gọi là lựa chọn trực tiếp) là sự lựa chọn một phần tử tùy ý của cấu trúc dữ liệu được truy nhập thông qua một cái tên.

Ví dụ để lựa chọn một phần tử nào đó của mảng, ta chỉ ra chỉ số của phần tử đó, để lựa chọn một phần tử của mẩu tin ta sử dụng tên của phần tử đó.

Lựa chọn tuần tự là sự lựa chọn trong đó phần tử được lựa chọn là một phần tử đứng sau các phần tử đã được lựa chọn khác theo tuần tự của việc xử lý hoặc là lựa chọn một phần tử đặc biệt nào đó.

Ví dụ lựa chọn tuần tự các phần tử trong một tập tin hay lựa chọn một phần tử trên đỉnh của ngăn xếp.

Các phép toán thao tác trên toàn bộ cấu trúc dữ liệu

Là các phép toán có thể nhận các CTDL làm các đối số và sản sinh ra kết quả là các CTDL mới. Chẳng hạn phép gán một mẩu tin cho một mẩu tin khác hoặc phép hợp hai tập hợp.

Thêm / bớt các phần tử

Là các phép toán cho phép thêm vào CTDL hoặc loại bỏ khỏi CTDL một số phần tử. Các phép toán này sẽ làm thay đổi số lượng các phần tử trong một CTDL. Việc thêm vào hay loại bỏ một phần tử thường phải chỉ định một vị trí nào đó.

Tạo / hủy CTDL

Là các phép toán tạo ra hoặc xóa bỏ một CTDL.

Biểu diễn tuần tự

Biểu diễn tuần tự là sự biểu diễn, trong đó CTDL được lưu trữ như một khối các ô nhớ liên tiếp nhau, bắt đầu bằng bộ mô tả sau đó là các phần tử.

Ðây là phương pháp được dùng cho các CTDL có kích thước cố định hoặc có kích thước thay đổi nhưng đồng nhất. Chẳng hạn có thể dùng biểu diễn tuần tự để biểu diễn cho mảng, mẩu tin,…

Biểu diễn liên kết

Biểu diễn liên kết là sự biểu diễn, trong đó CTDL được lưu trữ trong nhiều khối ô nhớ tại các vị trí khác nhau trong bộ nhớ, mỗi khối liên kết với khối khác thông qua một con trỏ gọi là con trỏ liên kết.

Phương pháp này thường được sử dụng cho các CTDL có kích thước thay đổi. Chẳng hạn có thể dùng biểu diễn liên kết để biểu diễn cho danh sách, ngăn xếp,…

Ðối với biểu diễn tuần tự

Như trên đã trình bày, trong cách biểu diễn tuần tự, một khối ô nhớ liên tục sẽ được cấp phát để lưu trữ tòan bộ CTDL. Trong đó, vị trí đầu tiên của khối ô nhớ được gọi là địa chỉ cơ sở. Khoảng cách từ địa chỉ cơ sở đến vị trí của phần tử cần lựa chọn được gọi là độ dời của phần tử.

Cách thức truy xuất, được cho bởi tên hoặc chỉ số của phần tử (chẳng hạn chỉ số của một phần tử của mảng), sẽ xác định cách tính độ dời của phần tử như thế nào.

Để lựa chọn ngẫu nhiên một phần tử cần phải xác định vị trí thực của phần tử (tức là địa chỉ của ô nhớ lưu trữ phần tử đó) theo công thức:

Vị trí thực của phần tử = Ðịa chỉ cơ sở + độ dời của phần tử.

Lựa chọn tuần tự một dãy các phần tử của cấu trúc có thể theo các bước:

- Ðể chọn phần tử đầu tiên ta dùng cách tính địa chỉ cơ sở cộng với độ dời như đã nói ở trên.

- Ðối với các phần tử tiếp theo trong dãy, cộng kích thước của phần tử hiện hành với vị trí của phần tử hiện hành để được vị trí của phần tử kế tiếp.

Ðối với biểu diễn liên kết

Như trên đã trình bày, các khối ô nhớ trong biểu diễn liên kết được bố trí rời rạc nhau, khối này nối với khối kia bằng con trỏ và lúc đầu chỉ nắm được con trỏ tới khối đầu tiên. Do đó việc đi đến các khối luôn phải xuất phát từ khối đầu tiên.

Để lựa chọn ngẫu nhiên một phần tử trong cấu trúc liên kết cần phải duyệt một dãy các khối, từ khối đầu tiên đến khối cần lựa chọn.

Lựa chọn tuần tự một dãy các phần tử được thực hiện bằng cách lựa chọn phần tử đầu tiên như đã nói ở trên và sau đó từ phần tử hiện hành, duyệt theo con trỏ để đến phần tử kế tiếp.

Đặc tả thuộc tính của véctơ

Các thuộc tính của một véctơ là:

- Số lượng các phần tử, luôn được chỉ rõ bằng cách cho tập chỉ số. Tập chỉ số này thông thường được cho bởi một miền con các số nguyên, trong trường hợp đó, số lượng các phần tử bằng số nguyên cuối cùng - số nguyên đầu tiên + 1. Một cách tổng quát thì tập chỉ số có thể là kiểu liệt kê nào đó, trong trường hợp này, số lượng phần tử bằng số giá trị trong kiểu liệt kê. Cũng có những ngôn ngữ chỉ định rõ số lượng các phần tử như ngôn ngữ C chẳng hạn.

- Kiểu dữ liệu của mỗi một phần tử, thường được viết rõ trong khai báo.

- Chỉ số được sử dụng để lựa chọn mỗi một phần tử. Nếu tập chỉ số được cho bởi một miền con của tập các số nguyên thì số nguyên đầu tiên chỉ định phần tử đầu tiên số nguyên thứ 2 chỉ định phần tử thứ 2 ...Nếu tập chỉ số là một liệt kê thì giá trị đầu tiên trong liệt kê là chỉ số của phần tử đầu tiên. Nếu ngôn ngữ chỉ định rõ số lượng các phần tử thì 0 là chỉ số của phần tử đầu tiên.

Khai báo véctơ trong Pascal là ARRAY [<tập chỉ số>] OF <kiểu phần tử>.

Ví dụ VAR a: ARRAY[1..10] OF real;

Khai báo này xác định 1 véctơ a có 10 phân tử là các số real. Các phần tử này được lựa chọn bởi các chỉ số từ 1 đến 10.

Miền giá trị của chỉ số không nhất thiết bắt đầu từ 1, ví dụ

Var b: ARRAY [-5..10] OF integer; Với khai báo này thì b là một véctơ có 16 phần tử (10 – (-5) + 1 = 16). Các phần tử được lựa chọn nhờ các chỉ số từ -5 đến 10.

Miền giá trị của chỉ số không nhất thiết là miền con của số nguyên, nó có thể là một liệt kê bất kỳ (hoặc 1 miền con của một liệt kê). Ví dụ:

Type

Ngay = (Chu_nhat, Hai, Ba, Tu, Nam, Sau, Bay);

var

c : ARRAY [Ngay] OF Integer ;

Khai báo này xác đinh véctơ c có 7 phần tử là các số integer, các phần tử của c được lựa chọn nhờ các “chỉ số” từ Chu_nhat đến Bay.

Khai báo véctơ trong ngôn ngữ C là <kiểu phần tử> <tên biến> [<số lượng phần tử>].

Ví dụ int d[10];

Khai báo này xác định véctơ d có 10 phần tử các số int, các phần tử này được lựa chọn nhờ các chỉ số từ 0 đến 9.

Đặc tả các phép toán trên véctơ

Các phép toán trên véctơ bao gồm:

Phép toán lựa chọn một phần tử của véctơ là phép lấy chỉ số, được viết bằng tên của véctơ theo sau là chỉ số của phần tử được lựa chọn đặt trong cặp dấu []. Như vậy phép lựa chọn một phần tử của véctơ là phép lựa chọn trực tiếp.

Ví dụ, với các khai báo trong các ví dụ thuộc phần đặc tả thuộc tính nói trên,

Các phần tử của véctơ a được lựa chọn bằng cách viết a[1], a[2], …, a[10].

Các phần tử của véctơ b được lựa chọn bằng cách viết b[-5], b[-4], …, b[10].

Các phần tử của véctơ c được lựa chọn bằng cách viết c[Chu_nhat], c[Hai], …, c[Bay].

Các phần tử của véctơ d được lựa chọn bằng cách viết d[0], d[1], …, d[9].

Chỉ số có thể là một hằng hoặc một biến (nói chung là một biểu thức), ví dụ a[i] hay a[i+2]. Nhờ chỉ số là một biểu thức nên việc lập trình trở nên đơn giản hơn nhiều nhờ tính khái quát của chỉ số.

Ví dụ để in ra giá trị của 10 phần tử trong véctơ a, thay vì ta phải viết 10 lệnh in các phần tử cụ thể theo kiểu writeln(a[1]); writeln(a[2]); writeln(a[3]); … ta chỉ cần viết một lệnh for i:=1 to 10 do writeln(a[i]);

Các phép toán khác trên véctơ bao gồm các phép toán tạo và hủy bỏ véctơ, gán hai véctơ cho nhau và các phép toán thực hiện như các phép toán số học trên từng cặp 2 véctơ có cùng kích thước. Chẳng hạn phép cộng 2 véctơ (cộng các phần tử tương ứng). Tùy thuộc vào ngôn ngữ mà các phép toán này có hoặc không có.

Biểu diễn bộ nhớ

Biểu diễn bộ nhớ tuần tự được sử dụng để biễu diễn cho một véctơ.

Mô hình sau minh họa cho sự biểu diễn bộ nhớ của véctơ A : ARRAY[LB..UB] OF <kiểu phần tử>.

Khối ô nhớ để lưu trữ một véctơ có hai phần: bộ mô tả và bộ nhớ dành cho các phần tử của véctơ. Trong bộ mô tả lưu trữ kiểu dữ liệu của cấu trúc (véctơ A), cận dưới của tập chỉ số (LB - Lower Bound), cận trên của tập chỉ số (UB - Upper Bound), kiểu dữ liệu của phần tử và kích thước mỗi phần tử (E). Bộ nhớ dành cho các phần tử của véctơ lưu trữ liên tiếp các phần tử, từ phần tử đầu tiên (A[LB]) cho đến phần tử cuối cùng (A[UB]). Do các phần tử có cùng một kiểu nên các ô nhớ dành cho các phần tử có kích thước bằng nahu.

Ðịa chỉ của ô nhớ đầu tiên trong khối gọi là địa chỉ cơ sở.

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

Phép toán lựa chọn một phần tử được thực hiện bằng cách tính vị trí của phần tử cần lựa chọn theo công thức:

Vị trí của phần tử thứ i =  + D + (i - LB) * E

Trong đó i là chỉ số của phần tử cần lựa chọn,  là địa chỉ cơ sở của khối ô nhớ (địa chỉ word hoặc byte đầu tiên của khối ô nhớ dành cho véctơ) D là kích thước của bộ mô tả, LB là cận dưới của tập chỉ số và E là kích thước của mỗi một đối tượng dữ liệu thành phần (số word hoặc byte cần thiết để lưu trữ một phần tử).

Nếu chỉ số là một giá trị của kiểu liệt kê chứ không phải số nguyên thì hiệu i-LB phải được tính toán một cách thích hợp (chẳng hạn sử dụng hiệu của hai số thứ tự tương ứng của i và LB trong liệt kê).

Phép gán một véctơ cho một véctơ khác có cùng thuộc tính được thực hiện bằng cách sao chép nội dung trong khối ô nhớ biểu diễn véctơ thứ nhất sang khối ô nhớ biểu diễn véctơ thứ hai.

Các phép toán trên toàn bộ véctơ được thực hiện bằng cách sử dụng các vòng lặp xử lý tuần tự các phần tử của véctơ.

Đặc tả thuộc tính

Mảng nhiều chiều tương tự như véctơ nhưng chỉ có một thuộc tính khác véctơ là mỗi một chiều phải có một tập chỉ số tương ứng.

Chẳng hạn khai báo cho một mảng hai chiều có thể đươc viết dưới dạng

ARRAY[LB1..UB1, LB2..UB2 ] OF <Kiểu phần tử>

Trong đó tập chỉ số 1 có các giá trị từ LB1 đến UB1, tập chỉ số 2 có các giá trị từ LB2 đến UB2.

Như vậy số lượng các phần tử của mảng hai chiều sẽ là (UB1-LB1+1)*(UB2-LB2+1)

Ví dụ sự khai báo của Pascal:

M= array [1..3, -1..2] of Integer;

Sự khai báo này cho ta thấy mảng M có hai chiều, chiều thứ nhất được xác định bởi tập chỉ số 1..3 và chiều thứ hai được xác định bởi tập chỉ số -1..2. Có thể xem đây là một ma trận có 3 dòng và 4 cột, như vậy sẽ có 12 phần tử, mỗi phần tử có thể lưu trữ một số integer.

Đối với các mảng có số chiều nhiều hơn hai thì cách làm cũng tương tự như mảng hai chiều.

Đặc tả phép toán

Phép lựa chọn một phần tử được thực hiện bằng cách chỉ ra tên mảng và chỉ số của mỗi một chiều.

Chẳng hạn để lựa chọn một phân tử của ma trận ta viết tên ma trận, theo sau là cặp chỉ số dòng, cột phân cách nhau bởi dấu phẩy và đặt trong cặp dấu [], ví dụ M[2,0].

Như vậy phép lựa chọn một phần tử của mảng nhiều chiều là phép lựa chọn trực tiếp.

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

Ðể thực hiện phép toán lựa chọn phần tử, ta sử dụng công thức tính vị trí của phần tử trong bộ nhớ.

Với cách lưu trữ theo trật tự dòng của ma trận M, để tính vị trí của M[i,j], đầu tiên ta xác định số dòng cần nhảy qua: (i-LB1) nhân với độ dài của mỗi dòng để xác định vị trí bắt đầu của dòng thứ i và sau đó tìm vị trí thứ J trong dòng này như đối với 1 véctơ. Như vậy, vị trí của phần tử M[i,j] được tính bởi:

Vị trí của M [i,j] =  + D + (i-LB1) x S + (j-LB2) x E

Trong đó:  là địa chỉ cơ sở.

D là độ lớn của bộ mô tả.

S là độ lớn của mỗi dòng = (UB2 - LB2 +1) x E.

LB1 là cận dưới của chỉ số thứ nhất.

LB2,UB2 tương ứng là cận dưới và cận trên của chỉ số thứ hai.

Tương tự ta có thể thành lập công thức tính vị trí của phần tử M[i,j] trong trường hợp ma trận M được tổ chức lưu trữ theo trật tự cột.

Tổng quát hóa công thức này cho mảng nhiều chiều hơn là một điều đơn giản.

Đặc tả thuộc tính

Các thuộc tính của một mẩu tin phải được chỉ rõ trong phép khai báo, chúng bao gồm:

1. Số lượng các phần tử.

2. Kiểu dữ liệu của các phần tử (Các phần tử có thể có kiểu khác nhau).

3. Mỗi phần tử được cho bởi tên phần tử (tên trường).

Cú pháp khai báo mẩu tin của Pascal:

Nhan_vien: RECORD

Ma: Integer; {Mã nhân viên}

Ho_ten: String[25];

Tuoi: Integer; {Tuổi}

Luong: Real; {Hệ số lương}

END

Việc khai báo này đặc tả một mẩu tin có 4 phần tử của các kiểu Integer, Real và String. Mỗi phần tử có một tên: Ma, Ho_ten, Tuoi và Luong. Ðể chọn một phần tử của mẩu tin ta sử dụng tên của phần tử (trường) đó, chẳng hạn trong Pascal, Nhan_vien.Luong là để truy xuất tới phần tử Luong của mẩu tin Nhan_vien.

Đặc tả phép toán

Lựa chọn một phần tử là phép toán cơ bản cuả mẩu tin. Phép toán này được thực hiện bằng cách chỉ ra tên trực kiện của phần tử.

Ví dụ để lựa chọn phần tử thứ 4 của mẩu tin Nhan_vien ta viết: Nhan_vien.Luong.

Phép toán lựa chọn một phần tử của mẩu tin là sự lựa chọn trực tiếp.

Mặc dù đều là lựa chọn trực tiếp, nhưng có khác biệt so với cách lựa chọn phần tử của véctơ. Điểm khác biệt ở đây là: đối với véctơ, ta có thể sử dụng giá trị của một biểu thức làm chỉ số, chẳng hạn VECTO[i+1], còn đối với mẩu tin thì bắt buộc phải chỉ rõ tên trực kiện, chứ không thể là biểu thức.

Ngoài phép toán lựa chọn phần tử, phép gán các mẩu tin có cùng cấu trúc là một phép toán phổ biến được các ngôn ngữ đưa vào. Chẳng hạn Nhan_vien := InputRec trong đó InputRec có các thuộc tính giống hệt Nhan_vien.

Biểu diễn bộ nhớ

Biểu diễn bộ nhớ tuần tự được sử dụng để lưu trữ một mẩu tin. Một khối liên tục các ô nhớ được dùng để lưu trữ cho một mẩu tin, trong khối đó, mỗi ô biểu diễn cho một trường. Có thể cũng cần sử dụng bộ mô tả riêng cho từng trường để lưu trữ thuộc tính của các trường đó. Do các trường có kiểu khác nhau nên ô nhớ dành cho chúng cũng có kích thước khác nhau.

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

Việc lựa chọn phần tử được thực hiện một cách dễ dàng vì tên trường được biết đến thông qua việc dịch chứ không phải được tính toán thông qua việc thực hiện như đối với véctơ. Việc khai báo mẩu tin còn cho phép xác định kích thước và vị trí của nó trong ô nhớ thông qua việc dịch. Kết quả là độ dời của phần tử bất kỳ có thể được tính thông qua việc dịch.

Chẳng hạn với mẩu tin Nhan_vien, các phần tử của nó được lưu trữ trong bộ nhớ như sau:

Vị trí của một phần tử bất kỳ được tính một cách dễ dàng. Chẳng hạn

Vị trí của Tuoi = α + Kích thước của Ma + Kích thước của Ho_ten.

Trong đó α là địa chỉ cơ sở của khối ô nhớ biểu diễn cho Nhan_vien.

Phép toán gán toàn bộ một mẩu tin cho một mẩu tin khác có cùng cấu trúc được thực hiện một cách đơn giản là copy nội dung khối ô nhớ biểu diễn cho mẩu tin thứ nhất sang khối ô nhớ biểu diễn cho mẩu tin thứ 2.