Bỏ qua

Tóm tắt

Điểm lại trọng tâm

  • Cấu trúc dữ liệu có thể được phân loại từ hai khía cạnh: cấu trúc logic và cấu trúc vật lý. Cấu trúc logic mô tả mối quan hệ logic giữa các phần tử dữ liệu, trong khi cấu trúc vật lý mô tả cách dữ liệu được lưu trữ trong bộ nhớ máy tính.
  • Các cấu trúc logic phổ biến bao gồm các cấu trúc tuyến tính, dạng cây và dạng mạng. Dựa trên cấu trúc logic, chúng ta thường phân loại các cấu trúc dữ liệu thành cấu trúc tuyến tính (mảng, danh sách liên kết, ngăn xếp, hàng đợi) và cấu trúc phi tuyến tính (cây, đồ thị, đống). Việc triển khai bảng băm có thể liên quan đến cả cấu trúc dữ liệu tuyến tính và phi tuyến tính.
  • Khi chương trình chạy, dữ liệu được lưu trữ trong bộ nhớ máy tính. Mỗi không gian bộ nhớ có một địa chỉ bộ nhớ tương ứng, và chương trình truy cập dữ liệu thông qua các địa chỉ bộ nhớ này.
  • Các cấu trúc vật lý chủ yếu được chia thành lưu trữ không gian liên tục (mảng) và lưu trữ không gian phân tán (danh sách liên kết). Tất cả các cấu trúc dữ liệu đều được triển khai bằng mảng, danh sách liên kết hoặc sự kết hợp của cả hai.
  • Các kiểu dữ liệu cơ bản trong máy tính bao gồm số nguyên byte, short, int, long, số thực dấu phẩy động float, double, ký tự char và boolean bool. Phạm vi giá trị của chúng phụ thuộc vào dung lượng không gian mà chúng chiếm dụng và phương pháp biểu diễn.
  • Dấu lượng trị, bù 1 và bù 2 là ba phương pháp mã hóa số trong máy tính, và chúng có thể chuyển đổi qua lại cho nhau. Bit có trọng số lớn nhất (most significant bit) của dạng dấu lượng trị là bit dấu, và các bit còn lại biểu thị giá trị của số.
  • Các số nguyên được lưu trữ trong máy tính dưới dạng bù 2. Dưới sự biểu diễn của bù 2, máy tính có thể xử lý thống nhất phép cộng của số dương và số âm mà không cần thiết kế mạch phần cứng đặc biệt cho phép trừ, đồng thời không tồn tại sự mơ hồ giữa số không dương (\(+0\)) và số không âm (\(-0\)).
  • Mã hóa số thực dấu phẩy động gồm 1 bit dấu, 8 bit mũ và 23 bit phân số. Nhờ có các bit mũ, phạm vi biểu diễn của số thực dấu phẩy động lớn hơn nhiều so với số nguyên, nhưng với cái giá phải trả là hy sinh độ chính xác.
  • ASCII là bộ ký tự tiếng Anh sớm nhất, có độ dài 1 byte, chứa tổng cộng 128 ký tự. GBK là bộ ký tự tiếng Trung thường dùng, chứa hơn 20.000 chữ Hán. Unicode cam kết cung cấp một tiêu chuẩn bộ ký tự hoàn chỉnh, thu thập các ký tự từ nhiều ngôn ngữ khác nhau trên thế giới, từ đó giải quyết bài toán lỗi hiển thị văn bản do các phương pháp mã hóa ký tự không đồng nhất gây ra.
  • UTF-8 là phương pháp mã hóa Unicode phổ biến nhất và có khả năng tương thích tuyệt vời. Nó là phương pháp mã hóa có độ dài biến đổi với khả năng mở rộng tốt, giúp cải thiện hiệu quả không gian lưu trữ một cách hiệu quả. UTF-16 và UTF-32 là các phương pháp mã hóa Unicode phổ biến khác. Khi mã hóa chữ Hán, UTF-16 chiếm ít không gian hơn UTF-8. Các ngôn ngữ lập trình như Java và C# sử dụng mã hóa UTF-16 theo mặc định.

Q & A

Q: Tại sao bảng băm lại chứa cả cấu trúc dữ liệu tuyến tính và phi tuyến tính?

Cấu trúc nền tảng của bảng băm là một mảng. Để giải quyết đụng độ băm, chúng ta có thể sử dụng giải pháp "kết nối chuỗi" (được thảo luận trong phần "Đụng độ băm" tiếp theo): mỗi xô (bucket) trong mảng trỏ đến một danh sách liên kết, danh sách này có thể được chuyển đổi thành một cây (thường là cây đỏ-đen) khi độ dài danh sách vượt quá một ngưỡng nhất định.

Từ góc độ lưu trữ, cấu trúc nền tảng của bảng băm là một mảng, trong đó mỗi vị trí xô có thể chứa một giá trị, một danh sách liên kết hoặc một cây. Do đó, bảng băm có thể chứa cả các cấu trúc dữ liệu tuyến tính (mảng, danh sách liên kết) và cấu trúc dữ liệu phi tuyến tính (cây).

Q: Độ dài của kiểu char có phải là 1 byte không?

Độ dài của kiểu char được quyết định bởi phương pháp mã hóa mà ngôn ngữ lập trình sử dụng. Ví dụ, Java, JavaScript, TypeScript và C# đều sử dụng mã hóa UTF-16 (để lưu trữ các điểm mã Unicode), vì vậy kiểu char của chúng có độ dài là 2 byte.

Q: Việc gọi cấu trúc dữ liệu dạng mảng là "cấu trúc dữ liệu tĩnh" có gây ra sự mơ hồ không? Ngăn xếp cũng có thể thực hiện các thao tác "động" như push và pop.

Ngăn xếp quả thực có thể triển khai các thao tác dữ liệu động, nhưng bản thân cấu trúc dữ liệu này vẫn là "tĩnh" (có độ dài cố định). Mặc dù các cấu trúc dữ liệu dạng mảng có thể thêm hoặc xóa phần tử một cách động, nhưng dung lượng của chúng vẫn cố định. Nếu lượng dữ liệu vượt quá kích thước được phân bổ trước, một mảng mới lớn hơn cần được tạo ra, và nội dung của mảng cũ phải được sao chép sang mảng mới.

Q: Khi khởi tạo ngăn xếp (hàng đợi), kích thước của nó không được chỉ định. Tại sao chúng lại là "cấu trúc dữ liệu tĩnh"?

Trong các ngôn ngữ lập trình bậc cao, chúng ta không cần chỉ định thủ công dung lượng ban đầu của ngăn xếp (hàng đợi); lớp (class) sẽ tự động xử lý việc này. Ví dụ, dung lượng ban đầu của ArrayList trong Java thường là 10. Ngoài ra, thao tác mở rộng dung lượng cũng tự động được thực hiện. Xem chi tiết trong phần "Danh sách" (List) tiếp theo.

Q: Phương pháp chuyển đổi số dấu lượng trị sang số bù 2 là "đầu tiên lấy phủ định rồi cộng thêm 1". Vậy chuyển đổi từ bù 2 sang dấu lượng trị phải là thao tác ngược lại "đầu tiên trừ đi 1 rồi lấy phủ định". Tuy nhiên, số bù 2 cũng có thể chuyển đổi sang dấu lượng trị qua phép toán "đầu tiên lấy phủ định rồi cộng thêm 1". Tại sao lại như vậy?

Điều này là do sự chuyển đổi lẫn nhau giữa dấu lượng trị và bù 2 thực chất là quá trình tính toán "số bù". Trước tiên hãy định nghĩa số bù: giả sử \(a + b = c\), khi đó ta nói \(a\) là số bù của \(b\) đối với \(c\), và ngược lại, \(b\) là số bù của \(a\) đối với \(c\).

Xét một số nhị phân \(n = 4\) bit là \(0010\), nếu coi số này là dấu lượng trị (bỏ qua bit dấu), thì số bù 2 của nó có thể thu được bằng phép toán "đầu tiên lấy phủ định rồi cộng thêm 1":

\[ 0010 \rightarrow 1101 \rightarrow 1110 \]

Chúng ta thấy rằng tổng của dấu lượng trị và số bù 2 là \(0010 + 1110 = 10000\), nghĩa là số bù 2 \(1110\) là "số bù" của dấu lượng trị \(0010\) đối với \(10000\). Điều này có nghĩa là phép toán "đầu tiên lấy phủ định rồi cộng thêm 1" ở trên thực chất là quá trình tính số bù đối với \(10000\).

Vậy "số bù" của số bù 2 \(1110\) đối với \(10000\) là gì? Chúng ta vẫn có thể dùng phép toán "đầu tiên lấy phủ định rồi cộng thêm 1" để tìm ra nó:

\[ 1110 \rightarrow 0001 \rightarrow 0010 \]

Nói cách khác, dấu lượng trị và bù 2 là "số bù" của nhau đối với \(10000\), vì vậy "dấu lượng trị sang bù 2" và "bù 2 sang dấu lượng trị" có thể được triển khai bằng cùng một thao tác (đầu tiên lấy phủ định rồi cộng 1).

Tất nhiên, chúng ta cũng có thể sử dụng thao tác ngược lại để tìm dạng dấu lượng trị của số bù 2 \(1110\), tức là "đầu tiên trừ đi 1 rồi lấy phủ định":

\[ 1110 \rightarrow 1101 \rightarrow 0010 \]

Tóm lại, cả "đầu tiên lấy phủ định rồi cộng 1" và "đầu tiên trừ đi 1 rồi lấy phủ định" đều là tính toán số bù đối với \(10000\), và chúng tương đương với nhau.

Về bản chất, thao tác "phủ định" thực sự là tìm số bù đối với \(1111\) (vì đẳng thức "dấu lượng trị + bù 1 = 1111" luôn luôn đúng); và cộng thêm 1 vào số bù 1 sẽ cho ra số bù 2, tức là số bù đối với \(10000\).

Ví dụ trên sử dụng \(n = 4\), và nó có thể được khái quát hóa cho các số nhị phân có số lượng bit bất kỳ.