Chương 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1. Mục tiêu: - Mô tả đƣợc khái niệm giải thuật, mối quan hệ giữa cấu trúc dữ liệu và giải thuật, đánh giá đƣợc độ phức tạp của giải thuật. - Ghi nhớ đƣợc các kiểu dữ liệu cơ bản, kiểu dữ liệu trừu tƣợng và các cấu trúc dữ liệu cơ bản. Nội dung chƣơng: I.
CÁC TIÊU CHUẨN DANH GIA CẤU TRÚC DỮ LIỆU 1. Phản ánh đúng thực tế : ây là tiêu chuẩn quan trọng nhất, quyết định tính đúng đắn của toàn bộ bài toán. Cần xem xét kỹ lƣỡng cũng nhƣ dự trù các trạng thái biến đổi của dữ liệu trong chu trình sống để có thể chọn cấu trúc dữ liệu lƣu trữ thể hiện chính xác đối tƣợng thực tế. Ví dụ: Một số tình huống chọn cấu trúc lƣu trữ sai : - Chọn một biến số nguyên int để lƣu trữ tiền thƣởng bán hàng (đƣợc tính theo công thức tiền thƣởng bán hàng = trị giá hàng * 5%), do vậy sẽ làm tròn mọi giá trị tiền thƣởng gây thiệt hại cho nhân viên bán hàng.
Trƣờng hợp này phải sử dụng biến số thực để phản ánh đúng kết quả của công thức tính thực tế. - Trong trƣờng trung học, mỗi lớp có thể nhận tối đa 28 học sinh. Lớp hiện có 20 học sinh, mỗi tháng mỗi học sinh đóng học phí $10. Chọn một biến số nguyên unsigned char ( khả năng lƣu trữ 0 - 255) để lƣu trữ tổng học phí của lớp học trong tháng, nếu xảy ra trƣờng hợp có thêm 6 học sinh đƣợc nhận vào lớp thì giá trị tổng học phí thu đƣợc là $260, vƣợt khỏi khả năng lƣu trữ của biến đã chọn, gây ra tình trạng tràn, sai lệch.
Phù hợp với các thao tác trên đó: Tiêu chuẩn này giúp tăng tính hiệu quả của đề án: việc phát triển các thuật toán đơn giản, tự nhiên hơn; chƣơng trình đạt hiệu quả cao hơn về tốc độ xử lý. Ví dụ: Một tình huống chọn cấu trúc lƣu trữ không phù hợp: Cần xây dựng một chƣơng trình soạn thảo văn bản, các thao tác xử lý thƣờng xảy ra là chèn, xoá sửa các ký tự trên văn bản. Trong thời gian xử lý văn bản, nếu chọn cấu trúc lƣu trữ văn bản trực tiếp lên tập tin thì sẽ gây khó khăn khi xây dựng các giải thuật cập nhật văn bản và làm chậm tốc độ xử lý của chƣơng trình vì phải làm việc trên bộ nhớ ngoài. Trƣờng hợp này nên tìm một cấu trúc dữ liệu có thể tổ chức ở bộ nhớ trong để lƣu trữ văn bản suốt thời gian soạn thảo.
Lưu ý: ối với mỗi ứng dụng , cần chú ý đến thao tác nào đƣợc sử dụng nhiều nhất để lựa chọn cấu trúc dữ liệu cho thích hợp. Tiết kiệm tài nguyên hệ thống: Cấu trúc dữ liệu chỉ nên sử dụng tài nguyên hệ thống vừa đủ để đảm nhiệm đƣợc chức năng của nó. Thông thƣờng có 2 loại tài nguyên cần lƣu tâm nhất : CPU và bộ nhớ.Tiêu chuẩn này nên cân nhắc tùy vào tình huống cụ thể khi thực hiện đề án. Nếu tổ chức sử dụng đề án cần có những xử lý nhanh thì khi chọn cấu trúc dữ liệu yếu tố tiết kiệm thời gian xử lý phải đặt nặng hơn tiêu chuẩn sử dụng tối ƣu bộ nhớ, và ngƣợc lại.
Ví dụ: Một số tình huống chọn cấu trúc lƣu trữ lãng phí: - Sử dụng biến int (2 bytes) để lƣu trữ một giá trị cho biết tháng hiện hành. Biết rằng tháng chỉ có thể nhận các giá trị từ 1-12, nên chỉ cần sử dụng kiểu char (1 byte) là đủ. - ể lƣu trữ danh sách học viên trong một lớp, sử dụng mảng 50 phần tử (giới hạn số học viên trong lớp tối đa là 50). Nếu số lƣợng học viên thật sự ít hơn 50, thì gây lãng phí.
Trƣờng hợp này cần có một cấu trúc dữ liệu linh động hơn mảng- ví dụ xâu liên kết - sẽ đƣợc đề cập trong chƣơng sau II. KIỂU DỮ LIỆU iểu dữ liệu T đƣợc xác định bởi một bộ < V, O > , với : V (Value): tập các giá trị hợp lệ mà một đối tƣợng kiểu T có thể lƣu trữ O (Operation): tập các thao tác xử lý có thể thi hành trên đối tƣợng kiểu T. Ví du: Giả sử có kiểu dữ liệu mẫu tự = < Vc , Oc > với Vc = { a-z,A-Z} Oc = { lấy mã ASCII của ký tự, biến đổi ký tự thƣờng thành ký tự hoa…} Giả sử có kiểu dữ liệu số nguyên = < Vi, Oi > với Vi = { -32768.32767} Oi = { +, -, *, /, %} Nhƣ vậy, muốn sử dụng một kiểu dữ liệu cần nắm vững cả nội dung dữ liệu đƣợc phép lƣu trữ và các xử lý tác động trên đó. Các thuộc tính của 1 DL bao gồm: Tên KDL Miền giá trị ích thƣớc lƣu trữ Tập các toán tử tác động lên DL III.
KIỂU DỮ LIỆU CƠ BẢN Các loại dữ liệu cơ bản thƣờng là các loại dữ liệu đơn giản, không có cấu trúc nhƣ số nguyên, số thực, các ký tự, các giá trị logic. Các loại dữ liệu này, do tính thông dụng và đơn giản của mình, thƣờng đƣợc các ngôn ngữ lập trình (NNLT) cấp cao xây dựng sẵn nhƣ một thành phần của ngôn ngữ để giảm nhẹ công việc cho ngƣời lập trình. Chính vì vậy đôi khi ngƣời ta còn gọi chúng là các kiểu dữ liệu định sẵn. Thông thƣờng, các kiểu dữ liệu cơ bản bao gồm : Kiểu có thứ tự rời rạc: số nguyên, ký tự, logic, liệt kê, miền con … Kiểu không rời rạc: số thực Tùy ngôn ngữ lập trình, các kiểu dữ liệu định nghĩa sẵn có thể khác nhau đôi chút.
Với ngôn ngữ C, các kiểu dữ liệu này chỉ gồm số nguyên, số thực, ký tự. Và theo quan điểm của C, kiểu ký tự thực chất cũng là kiểu số nguyên về mặt lƣu trữ, chỉ khác về cách sử dụng. Ngoài ra, giá trị logic ÚNG (TRUE) và giá trị logic SAI (FALSE) đƣợc biểu diễn trong C nhƣ là các giá trị nguyên khác zero và zero. Các kiểu dữ liệu định sẵn trong C gồm các kiểu sau: Tên kiểu Kích thƣớc Miền giá trị Ghi chú Có thể dùng nhƣ số nguyên 1 byte Char 01 byte -128 đến 127 có dấu hoặc kiểu ký tự Unsign char 01 byte 0 đến 255 Số nguyên 1 byte không dấu Int 02 byte -32738 đến 32767 Số nguyên 2 byte Unsign int 02 byte 0 đến 65535 Có thể gọi tắt là unsign Long 04 byte -232 đến 231 -1 Unsign long 04 byte 0 đến 232-1 Giới hạn chỉ trị tuyệt đối.
Tuy Float 04 byte 3.4E38 nhiên kiểu float chỉ có 7 chữ số có nghĩa.7E308 Long double 10 byte 3.1E4932 Nhƣ vậy, trong C xét cho cùng chỉ có 2 loại dữ liệu cơ bản là số nguyên và số thực. Tức là chỉ có dữ liệu số. Hơn nữa các số nguyên trong C có thể đƣợc thể hiện trong 3 hệ cơ số là hệ thập phân, hệ thập lục phân và hệ bát phân. Các kiểu cơ sở rất đơn giản và không thể hiện rõ sự tổ chức dữ liệu trong một cấu trúc, thƣờng chỉ đƣợc sử dụng làm nền để xây dựng các kiểu dữ liệu phức tạp khác.
CÁC KIỂU DỮ LIỆU CÓ CẤU TRÚC Tuy nhiên trong nhiều trƣờng hợp, chỉ với các kiểu dữ liệu cơ sở không đủ để phản ánh tự nhiên và đầy đủ bản chất của sự vật thực tế, dẫn đến nhu cầu phải xây dựng các kiểu dữ liệu mới dựa trên việc tổ chức, liên kết các thành phần dữ liệu có kiểu dữ liệu đã đƣợc định nghĩa. Những kiểu dữ liệu đƣợc xây dựng nhƣ thế gọi là kiểu dữ liệu có cấu trúc. Một số kiểu dữ liệu có cấu trúc cơ bản : 1. Kiểu chuỗi ký tự Chuỗi ký tự là một trong các kiểu dữ liệu có cấu trúc đơn giản nhất và thƣờng các ngôn ngữ lập trình đều định nghĩa nó nhƣ một kiểu cơ bản.
Do tính thông dụng của kiểu chuỗi ký tự các ngôn ngữ lập trình luôn cung cấp sẵn một bộ các hàm thƣ viện các xử lý trên kiểu dữ liệu này. Các hàm này đƣợc đặt trong thƣ viện string. Chuỗi ký tự trong C đƣợc cấu trúc nhƣ một chuỗi liên tiếp các ký tự kết thúc bằng ký tự \0 có mã ASCII bằng 0 (NULL character). Nhƣ vậy, giới hạn chiều dài của một chuỗi ký tự trong C là 1 Segment (tối đa chứa 65535 ký tự), ký tự đầu tiên đƣợc đánh số là ký tự thứ 0.
Ta có thể khai báo một chuỗi ký tự theo một số cách sau đây: char S[10]; // hai báo một chuỗi ký tự S có chiều dài // tối đa 10 (kể cả kí tự kết thúc) char S[]="ABC"; // hai báo một chuỗi ký tự S có chiều // dài bằng chiều dài của chuỗi "ABC" // và giá trị khởi đầu của S là "ABC" char *S ="ABC"; //Giống cách khai báo trên. Trong ví dụ trên ta cũng thấy đƣợc một hằng chuỗi ký tự đƣợc thể hiện bằng một chuỗi ký tự đặt trong cặp ngoặc kép “”. Các thao tác trên chuỗi ký tự rất đa dạng. Sau đây là một số thao tác thông dụng: So sánh 2 chuỗi: strcmp Sao chép chuỗi: strcpy ộ dài chuỗi: strlen iểm tra 1 chuỗi nằm trong chuỗi kia: strstr Cắt 1 từ ra khỏi 1 chuỗi: strtok ổi 1 số ra chuỗi: itoa ổi 1 chuỗi ra số: atoi, atof,.
Nhập một chuỗi: gets Xuất một chuỗi: puts 2. Kiểu mảng iểu dữ liệu mảng là kiểu dữ liệu trong đó mỗi phần tử của nó là một tập hợp có thứ tự các giá trị có cùng cấu trúc đƣợc lƣu trữ liên tiếp nhau trong bộ nhớ. Mảng có thể một chiều hay nhiều chiều. Một dãy số chính là hình tƣợng của mảng 1 chiều, ma trận là hình tƣợng của mảng 2 chiều.
Một điều đáng lƣu ý là mảng 2 chiều có thể coi là mảng một chiều trong đó mỗi phần tử của nó là 1 mảng một chiều. Tƣơng tự nhƣ vậy, một mảng n chiều có thể coi là mảng 1 chiều trong đó mỗi phần tử là 1 mảng n-1 chiều. Mảng 1 chiều đƣợc khai báo nhƣ sau: <Kiểu dữ liệu> <Tên biến>[<Số phần tử>]; Ví dụ: để khai báo một biến có tên a là một mảng nguyên 1 chiều có tối đa 100 phần tử ta phải khai báo nhƣ sau: int a[100]; Ta cũng có thể vừa khai báo vừa gán giá trị khởi động cho một mảng nhƣ sau: int a[5] = {1, 7, -3, 8, 19}; Trong trƣờng hợp này C cho phép ta khai báo một cách tiện lợi hơn int a[] = {1, 7, -3, 8, 19}; Nhƣ ta thấy, ta không cần chỉ ra số lƣợng phần tử cụ thể trong khai báo.