<< Chapter < Page
  Cấu trúc dữ liệu     Page 10 / 15
Chapter >> Page >

Trong ba phương pháp nói trên thì hai phương pháp đầu cho phép cấp phát bộ nhớ cho mỗi một đối tượng dữ liệu chuỗi được xác định tại thời gian dịch. Ðối vơi phương pháp thứ ba thì sử dụng cấp phát bộ nhớ động tại thời gian thực hiện. Các phương pháp khác nhau cũng đòi hỏi các phép toán khác nhau trên chuỗi. Sau đây là một số phép toán chủ yếu.

Đặc tả phép toán

Trên chuỗi ký tự, thường có các phép toán sau:

a/ Phép ghép nối (concatennation)

Ghép là phép toán nhập hai chuỗi ký tự tạo ra một chuỗi mới ví dụ nếu "//" là ký hiệu của phép ghép thì "BLOCK"//"HEAD" cho ra "BLOCKHEAD". Turbo Pascal sử dụng toán tử “+” cho phép toán ghép chuỗi.

b/ Các phép toán quan hệ trên chuỗi

Các phép toán quan hệ thông thường như bằng, nhỏ hơn, lớn hơn... trên kiểu ký tự có thể được mở rộng cho chuỗi ký tự. Tập hợp các ký tự cơ bản luôn luôn có một thứ tự. Mở rộng thứ tự này cho chuỗi ký tự thành thứ tự alphabe trong đó chuỗi A nhỏ hơn chuỗi B nếu ký tự đầu tiên của A nhỏ hơn ký tự đầu tiên của B hoặc hai ký tự đầu tiên tương ứng của chúng bằng nhau và ký tự thư hai của A nhỏ hơn ký tự thứ hai của B... Nếu chuỗi A ngắn hơn chuỗi B thì A được mở rộng bằng cách thêm vào các ký tự trắng cho dài bằng B để so sánh.

c/ Chọn chuỗi con dùng chỉ số chỉ vị trí của ký tự

Nhiều ngôn ngữ cung cấp một phép toán chọn chuỗi con của một chuỗi bằng cách cho vị trí của ký tự đầu tiên và ký tự cuối cùng của nó (hoặc vị trí của ký tự đầu tiên và chiều dài của chuỗi con). Ví dụ trong FORTRAN, lệnh NEXT = STR(6:10) là gán 5 ký tự, bắt đầu từ vị trí thứ 6 đến vị trị thứ 10 của chuỗi STR cho biến chuỗi NEXT.

d/ Ðịnh dạng nhập - xuất

Ðịnh dạng nhập xuất là phép toán dùng để thay đổi dạng nhập vào hoặc xuất ra của các chuỗi ký tự. Nhập xuất có định dạng là nét nổi bật của FORTRAN và PL/1.

e/ Chọn chuỗi con dùng so mẫu

Thông thường người ta không biết vị trí của một chuỗi con cần chọn trong một chuỗi lớn hơn nhưng quan hệ của nó với một chuỗi con khác thì có thể biết. Ví dụ chuỗi các chữ số sau dấu chấm thập phân hay chuỗi đứng sau một khoảng trống. Phép so mẫu có một đối số thứ nhất để xác định dạng của chuỗi con cần chọn (chẳng hạn độ dài của nó). Ðối số thứ hai của phép toán so mẫu là chuỗi ký tự dùng để tìm trong chuỗi (chẳng hạn dấu chấm thập phân). Như vậy kết quả của phép toán so mẫu là chọn được một chuỗi con bắt đầu từ sau dấu chấm thập phân và có độ dài đã cho.

Cài đặt

Biểu diễn bộ nhớ

Mỗi một phương pháp đặc tả chuỗi có một cách biểu diễn bộ nhớ tương ứng.

Ðối với chuỗi có độ dài được khai báo cố định thì dùng véctơ của các ký tự. Ví dụ chuỗi được khai báo có độ dài 8 và được dùng để lưu trữ chuỗi EINSTEIN (cũng có 8 ký tự):

E I N S T E I N

Ðối với chuỗi có độ dài thay đổi trong một giới hạn đã được khai báo thì vẫn dùng véctơ của các ký tự, trong đó sử dụng hai ô làm bộ mô tả chứa giá trị thể hiện độ dài lớn nhất đã được khai báo và độ dài hiện hành của chuỗi. Ví dụ chuỗi được khai báo có độ dài 12 và được dùng để lưu trữ chuỗi EINSTEIN (có 8 ký tự):

12 8 E I N S T E I N
Độ dài khai báo Độ dài thực Các ô dư không sử dụng

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Cấu trúc dữ liệu. OpenStax CNX. Jul 29, 2009 Download for free at http://cnx.org/content/col10766/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Cấu trúc dữ liệu' conversation and receive update notifications?

Ask