Chương 1 NHẬP MÔN CẤU TRÚC DỮ LIỆU 1. KHÁI NIỆM CẤU TRÚC DỬ LIỆU Thuật toán và cấu trúc dữ liệu được coi là môn học cốt lõi của ngành Công nghệ thông tin. Niklaus Wirth - tác giả cuốn "Cấu trúc dữ liệu + Giải thuật = Chương trình" đã phân tích tầm quan trọng của cấu trúc dữ liệu và thuật toán. Chương trình là những mô tả cụ thổ của các thuật toán trừu tượng dựa vào những biểu diễn và cấu trúc dữ liệu đặc biệt.
Chương trình và dữ liệu không thể tách rời nhau được. Dữ liệu được xử lý bởi chương trình, cần được tổ chức thành các cấu trúc sao cho nó phản ánh mối quan hệ giữa các mục dữ liệu và cho phép xử lý dữ liệu có hiệu quả. Dữ liệu ở dạng mã máy và ý nghĩa của chúng Trong máy tính các giá trị dữ liệu được lưu trữ dưới dạng các bit, là các sô' ở hộ đếm nhị phân (0 và 1). Các bit được tổ chức thành các nhóm gọi là các Từ máy (word), tức là mỗi word chứa một số cố định các bít.
Độ dài của word thay đổi theo loại máy tính (máy 16 bit hay 32 bít). Các Từ máy này được đánh địa chỉ bắt đầu từ 0, vì vậy có thể truy cập vào một word bất kỳ theo địa chỉ của nó. Khi ở dạng một dãy bít, nó có thể biểu diễn nhiều ý nghĩa khác nhau. Trong từng ngôn ngữ lập trình cụ thể, người lập trình sẽ biểu diễn các dãy bít này dưới dạng các cấu trúc xác định, cho phép xử lý và diễn đạt được các dữ liệu.
5 Những khái niệm quan trọng liên quan đến dữ liệu là Kiểu dữ liệu, Cấu trúc dữ liệu, Cấu trúc dữ liệu tĩnh, Cấu trúc dữ liệu động. Kiểu dữ liệu Các kiểu dữ liệu trong Pascal như integer, real, char, boolean, byte được gọi là kiểu dữ liệu đơn giản vì chúng là các dữ liệu không phân chia được nữa (gọi là các nguyên tử - atom). Tuy vậy chúng có thể được xem là có cấu trúc dữ liệu mà việc cài đặt chúng sử dụng các word như là cấu trúc lưu trữ cùng với các thuật toán để thực hiện những phép tính thích hợp cho từng kiểu. Khái niệm kiểu dữ liệu rất quan trọng, nó xác định tập hợp giá trị mà biến có thể nhận.
Mô tả kiểu sẽ quy định loại giá trị của biến và cung cấp cho chương trình dịch nhũng thông tin cần thiết. Tương ứng vói mỗi kiểu, mỗi dãy bít sẽ có một ý nghĩa riêng. Kiểu dữ liệu còn quy định những phép toán có thể thực hiện được đối vói các dữ liệu. Mỗi ngôn ngữ lập trình định nghĩa một tập các kiểu dữ liệu nguyên thuỷ, vô hướng của riêng nó, ví dụ, trong ngôn ngữ Pascal đó là Integer, real, boolean, char; trong ngôn ngữ c đó là Int, float, char.
Kiểu dữ liệu có các đặc điểm: + Một kiểu dữ liệu sẽ xác định tập hợp giá trị mà một hằng trị (const) hay một biến sẽ nhận giá trị thuộc miền đó; + Kiểu của một giá trị được chỉ định bởi một hằng trị (const), biến hoặc biểu thức có thể suy ra từ dạng của nó hoặc từ khai báo mà không cần phải tiến hành quá trình tính toán. + Mỗi tác tử hay hàm có biến với kiểu định sẵn và cho ra kết quả cũng có kiểu định sẵn. Nếu một tác tử nhận một số biến có kiểu khác nhau (ví dụ phép cộng + dùng hai số nguyên hay thực) thì kiểu của kết quả được xác định theo quy tắc riêng của ngôn ngữ. Các kiểu integer, real, char, boolean, có thể biểu diễn bời xâu các bít.
Sau đây ta xét một số kiểu dữ liệu điển hình trong Pascal. a) D ữ liệu kiểu nguyên - integer Dữ liệu kiểu integer được lưu trữ trong các từ máy. Như vậy độ dài của từ máy giới hạn phạm vi của các sô' nguyên lưu trữ được. Số nguyên lớn 6 nhất lưu trữ được trong một từ máy 8 bit là 27 - 1 = 127, trong từ máy 16 bit là 2 15- 1 = 32767, trong một từ máy 32 bit là 231 - 1 = 2.
b) D ữ liệu kiểu thực - Real Một số thực bất kỳ có thể biểu diễn bầng tổng các số với mũ của 2: x = g a , x 2' i= -m trong đó a¡ = 0 hoặc 1. Có hai cách lull số thực: dấu chấm tĩnh (fixed point) và dấu chấm động (floating point). Số thực dấu chấm động trong ô nhớ được biểu diễn thành 2 thành phần: một phần của từ máy được dùng để lưu trữ một số cố định các bít của phần định trị, phần khác lưu trữ phần mũ. <Phần định trị>.<phần mũ> c) D ữ liệu kiểu ký tự - char Máy lưu trữ dữ liệu kỷ tự dựa trên cơ sỏ gán mã số cho mỗi ký tự.
Các ký tự được biểu diễn bằng mã nhị phân, mỗi từ máy 16 bít chia thành hai byte, mỗi byte lưu trữ một ký tự dưới dạng nhị phân. Ký tự được mã hoá theo ASCII (American Standard Code for information Interchange - Bộ mã chuẩn cùa Mỹ dùng để trao đổi thông tin) hay EBCDIC (Extended Binary Code Decimal Interchange Code - Mã BCD mở rộng). Phép toán phổ biến cho các ký tự là SO lựa tuần tự (collating sequence). Vi dụ: kỹ tự A trong bảng mâ ASCII có mã là 65, ký tự B irong bảng mã ASCII có mã là 66.
Khi đó phép SO sánh A>B sẽ cho kết quả sai. d) D ữ liệu kiểu logic - Boolean Mỗi giá trị logic được biểu diễn bởi một chữ số ở hệ đếm nhị phân là 0 hoặc 1. Trong các ngôn ngữ thông dụng có 4 phép toán logic là AND, OR, NOT, XOR. Trên đây nhắc lại một số kiểu dữ liệu cơ bản, có trong mọi hệ thống máy tính, trong mọi loại ngôn ngữ lập trình.
7 Việc xác định kiểu dữ liệu là rất quan trọng, nó giải nghĩa cho một xâu bit dữ liệu và xác định các phép toán được sử dụng. Tương ứng với mỗi kiểu dữ liệu chỉ có một số phép toán được áp dụng, ví dụ trong ngôn ngữ Pascal:. Vối kiểu Integer chỉ dùng các phép: +, *, /, A, mod, div Với kiểu Real dùng các phép: +, *, / , A ; Với kiểu Boolean dùng các phép: and, or, not, xor Với kiểu Char dùng các phép: +, concat. Cấu trúc dữ liệu - Data Structure Đ ịnh nghĩa: Cấu trúc dữ liệu là cách thức tổ chức dữ liệu trong bộ nhớ máy tính.
Trong các loại cấu trúc dữ liệu, người ta phân chia ra cấu trúc đơn giản, cấu trúc phức tạp, cấu trúc tĩnh, cấu trúc động. - Cấu trúc dữ liệu đơn giản: là các kiểu dữ liệu nguyên thuỷ được định nghĩa trong các ngôn ngữ lập trình, ví dụ như Integer, Real, Boolean, Char trong ngôn ngữ Pascal; Int, Float, Char trong ngôn ngữ c. Trong thực tế, có những bài toán mà cách tổ chức dữ liệu đom giản không đáp ứng được, đòi hỏi phải tổ chức phức tạp hơn, ví dụ như một d ã y s ố , m ộ t d a n h sách các d ữ liệ u , V. - Cấu trúc dữ liệu tĩnh: là cách tổ chức mà kích thưốc của các phần tử dữ liệu là cô' định, cấu trúc cũng cố định trong khi chương trình dịch làm việc.
Trong ngôn ngữ Pascal, các kiểu array, kiểu dữ liệu liệt kê, hay các kiểu nguyên thuỷ như Integer, Real,. - Cấu trúc dữ liệu động: là cách tổ chức mà có thể thay đổi cả kích thước và cấu trúc của các dữ liệu. Các dữ liệu động này được sinh ra trong quá trình chương trình thực hiện. Chúng không được thể hiện khi dịch chương trình, và thường được sử dụng con trỏ để tạo ra dữ liệu động.
Ngoài các khái niệm trên, để phục vụ cho việc học tập, nghiên cứu và triển khai các ứng dụng, người ta còn chia ra: Cấu trúc dữ liệu tuyến tính, cấu trúc dữ liệu phi tuyến. Những cấu trúc mà khi xử lý được tiến hành ở dạng một dãy liên tục các dữ liệu thì được nhóm gộp vào loại tuyến tính, ví dụ như array, stack, queue, list đcm giản. Những cấu trúc còn lại được gọi chung là phi tuyến. CÁC MÔ HÌNH D ữ LIỆU Để đảm bảo hiệu quả các quá trình xử lý thông tin cần phải tổ chức dữ liệu cho phù hợp.
Mô hình hoá dữ liệu phải phản ánh được thế giới hiện thực một cách tốt nhất và phải cài đặt được trong máy tính. Từ Data (dữ liệu) có xuất xứ từ thuật ngữ "datum" tiếng Hy Lạp có nghĩa là "sự kiện". Tuy nhiên không phải bao giờ dữ liệu cũng tương ứng với một sự kiện cụ thể nào đó, hiện diện trong thế giới thực. Chúng ta gọi dữ liệu là mô tả của một hiên tượng bất kỳ (hay là một ý tưởng) mà đáng giá để biểu diễn nó và xác định nó chính xác.
Từ xa xưa con người đã sử dụng nhiều loại phương tiện khác nhau để ghi nhận các sự kiện, ý tưởng: đá, giấy,. thông thường dữ liệu (các sự kiện - Data) và diễn giải nó (ngữ nghĩa - semantic) được ghi cùng nhau vì ngôn ngữ tự nhiên khá tinh tế, phong phú để biểu diễn hiện tượng, sự kiện. Khi ta nói " dung lượng đĩa cứng 40MB" thì ở đây 40 là dữ liệu, còn ngữ nghĩa "dung lượng MB". Trong một sô' trường hợp thì dữ liệu và ngữ nghĩa (semantic) bị tách rời (ví dụ: bảng giờ tàu - diễn giải ở bên trên, còn phía dưới là giờ chạy của các tàu ở các tuyến đường).
Trong tin học .thì dữ liệu và ngữ nghĩa càng bị phân tách. Trong bộ nhớ của máy tính điện tử, người ta chỉ làm việc với dữ liệu, không để ý đến ngữ nghĩa, phần ngữ nghĩa của dữ liệu bản thân người lập trình phải ngầm hiểu, lưu giữ ở bộ nhớ riêng. Thường trong chương trình phải ghi chú về ý nghĩa của các loại dữ liệu, thiếu ghi chú này thì dữ liệu chỉ là các dãy bit đơn thuần. Sự linh hoạt của biểu diễn dữ liệu đạt được nhờ hai phương pháp: - Có nhiều cách nhìn khác nhau đối với cùng một đối tượng dữ liệu; - Biểu diễn đồng nhất hoá các dữ liệu khác nhau.
V í dụ: với đối tượng là Con ngưcrì, ta có hai cách tiếp cận: Theo phương pháp thứ nhất: cùng một đối tượng con người, nhung trong danh sách lớp học đó là họ tên sinh viên, trong bài toán xét lên lương đó là họ tên cán bộ công nhân viên, trong quản lý bệnh viện đó là họ tên bệnh nhân. Theo phương pháp thứ hai, ta có thể coi mọi người từ Giám đốc, trưởng phó phòng, đến nhân viên. đều là cán bộ công nhân viên.