CHƯƠNG 1 PHÂN TÍCH VÀ THIẾT KẾ GIẢI THUẬT Muc tiêu: Trình bày được khái niệm vê câu truc dư liêu, 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. Trình bày được các kiểu dữ liệu cơ bản, các kiểu dữ liệu cấu trúc và kiểu dữ liệu trừu tượng. Khái niệm cấu trúc dữ liệu và giải thuật, cấu trúc lưu trữ và cấu trúc dữ liệu.
Khái niệm cấu trúc dữ liệu và giải thuật Algorithms + Data Structures = Programs " Giai thuật + Cấu trúc dữ liệu = Chương trình " Đo la nhan đê cuốn sách đươc xuât ban năm 1975, bơi nha khoa hoc may tinh Thuy sy Niklaus Wirth Emil, cuôn sach đa đươc công nhân rông rai va vân con hưu dung đên ngay nay. Năm vưng câu truc dư liêu va giai thuât la cơ sơ giup sinh viên có khả năng đi sâu thêm vào các môn học chuyên ngành. Giải thuật(Algorithms): Đó là một dãy các câu lệnh (statements) chặt chẽ và rõ ràng xác định một trình tự các thao tác trên một số các đối tượng nào đó, sao cho sau một số hữu hạn bước thực hiện ta đạt đươc kết quả mong muốn. Dữ liệu (Data): Là đối tượng của giải thuật để khi tác động bởi các thao tác của giải thuật ta nhận được kết quả mong muốn.
Giải thuật chỉ phản ánh các phép xử lí, còn đối tượng để xử lí trên MTĐT, chính là dữ liệu (data) chúng biểu diễn các thông tin cần thiết cho bài toán: Các dữ kiện đưa vào, các kết quả trung gian va kêt qua đâu ra cua bai toan.1: Chương trinh tìm ươc chung lớn nhất của 2 số nguyên dương a và b. Dư kiên đưa vao (input): a, b nguyên dương Phep xư ly (Process) : Dưa theo thuât toan Euclid, thuât toan nôi tiêng nhât co tư thơi cô đai. Bươc 1: Tim r, la phân dư cua phep chia a cho b. Thi: Gan gia tri cua b cho E (E←b) va dưng lai Nêu ngươc lai (r ≠ 0).
Thi: Gan gia tri b cho a ( a←b). Gan gia tri r cho b (b←r) va quay lai bươc 1. 11 Kêt qua ra (Output): E, Ươc chung lơn nhât cua a va b. Cấu trúc dữ liệu (Data Structures): Cách sắp xếp, tổ chức dữ liệu, tạo quan hệ nội tại giữa các phần tử dữ liệu, tạo thuận lợi cho các phép xử lý và nâng cao hiệu quả của chúng.
Bản thân các phần tử của dữ liệu có mối quan hệ với nhau, ngoài ra nếu lại biết “tổ chức” theo các cấu trúc thích hợp thì việc thực hiện các phép xử lí trên các dữ liệu càng thuận lợi hơn, đạt hiệu quả cao hơn.2: Viêt chương trinh thưc hiên công viêc sau: Nhâp vao tư ban phim n sô nguyên bât ky Tinh tông cac sô vưa nhâp va đưa kêt qua ra man hinh Dư kiên đưa vao (input): so, tong la 2 biên sô nguyên và n là số lượng số nguyên. Phep xư ly (Process) : Thưc hiên n lân công viêc sau: - Nhâp gia tri cho biên so - Công gia tri biên so vao biên tong Kêt qua ra (Output): tong, tông n sô nguyên vưa nhâp Vơi 2 yêu câu (a, b) cua bai toan, ta chi cân môt biên so đê lưu gia tri tưng sô nguyên nhâp vao va công gôp dân gia tri ngay vao môt biên tong.3: Viêt chương trinh thưc hiên công viêc sau: Nhâp vao tư ban phim n sô nguyên bât ky. Tinh tông cac sô vưa nhâp va đưa kêt qua ra man hinh. Săp xêp day sô theo chiều tăng dần va đưa day đa săp xêp ra man hinh.
Dư kiên đưa vao (input): tong la biên sô nguyên. M la môt biên mang kiểu phân tư là kiêu sô nguyên. n là số lượng số nguyên. Phai cân môt biên mang M đê lưu gia tri n sô nguyên nhâp vao tư ban phim va day sô nguyên đa đươc săp xêp.
(nhiều ngôn ngư lâp trinh đêu đinh nghia sẵn kiêu dư liêu mang (array): gôm môt tâp hơp hưu han cac phần tư có cùng kiêu dư liêu, ta chỉ cần khai bao tên kiêu mang, sô lương phần tư va kiêu dư liêu cua phần tư khi cầ̀n sử dụng.) So sanh 2 vi du trên ta nhân thây co sư khac biêt sau : Ví dụ Dữ kiện đưa vào Phép xử lý Kết quả đưa ra Ví dụ 1.2 Chi cân môt biên Viêc tinh tông Gia tri biên tong so đê lưu giư tưng được thực hiện sô nguyên ngay sau mỗi lần nhâp sô nguyên Ví dụ 1.3 Phai cân biên Co thê tach riêng Gia tri biên tong va mảng M để lưu viêc tinh tông sau biên mả̉ ng M chứa n giư n sô nguyên khi nhâp giá trị sô nguyên đa đươc cho n sô nguyên sắp xếp tăng dần Tom lai, giữa cấu trúc dữ liệu và giải thuật có mối quan hệ mật thiết, không thể nói tới giải thuật mà không nghĩ tới: Giải thuật đó́ được tác động trên dữ liệu nào, còn khi xét tới dữ liệu thì cũng phải hiểu: Dữ liệu ấy cầ̀n được tác động bởi giải thuật gì để đưa tới kết quả mong muốn. Với một cấu trúc dư liệu đã chọn ta sẽ có giải thuật xử ly tương ứng. Cấu trúc dữ liệu thay đổi, giải thuật cũng có thể thay đổi theo. Cấu trúc dữ liệu và cấu trúc lưu trữ Cách biểu diễn một câu truc dư liêu (CTDL) trong bộ nhớ được gọi là cấu trúc lưu trữ (storage sructures).
Đó chính là cách cài đặt cấu trúc ấy trên may tinh điên tư và trên cơ sở cấu trúc lưu trữ này mà thực hiện các phép xử lí. Sự phân biệt giữa CTDL và cấu trúc lưu trữ tương ứng, cần phải được đặt ra. Có́ thể có́ nhiều cấu trúc lưu trữ khác nhau cho cù̀ng một CTDL, cũng như có́ thể có́ những CTDL khác nhau mà được thể hiện trong bộ nhớ bởi cù̀ng một kiểu cấu trúc lưu trữ 13 (thường khi xử lí, mọi chú ý đều hướng tới cấu trúc lưu trữ nên ta dễ quên mất CTDL tương ứng). Phân biệt lưu trữ trong và lưu trữ ngoài: Lưu trữ trong: Là lưu trữ ở bộ nhớ trong.
Lưu trữ ngoài: Là lưu trữ ở bộ nhớ ngoài (đĩa từ, đĩa quang,.4: CTDL kiểu mảng và Stack cùng được lưu trữ trong bộ nhớ bởi vectơ lưu trữ a[0] A[1] a[2]. a[1] a[0] Đáy Cấu trúc dữ liệu Trong môi bài toán, Lưạ chọn một CTDL thích hợp để tổ chức dữ liệu vào và trên cơ sở đó xây dựng được giải thuật xử ly hữu hiệu đưa tới kết quả mong muốn cho bài toán, đó là một khâu rất quan trọng. Muốn vậy cần nắm vững đặc điểm và các phép toán cơ bản của từng kiểu dữ liệu được sử dụng trong mỗi ngôn ngữ lập trình là yêu cầu cần thiết. Các kiểu dữ liệu cơ bản Các loại dữ liệu cơ bản là các loại dữ liệu đơn giản, cơ sở.
Chúng thường là các giá trị vô hướng như các 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. 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. Ví dụ: Các kiểu dữ liệu định sẵn trong C gồm: Tên kiểu Sô bytes Miền giá trị Ghi chú Char 1 -128 đến 127 Có thể dùng như số nguyên 1 byte có dấu hoặc kiểu ký tự unsigned char 1 0 đến 255 Số nguyên 1 byte không dấu Enum 2 -32,768 đến 32,767 14 Int 2 -32738 đến 32767 unsigned int 2 0 đến 65335 Có thể gọi tắt là unsigned Long 4 -232 đến 231 -1 unsigned long 4 0 đến 232-1 Float 4 3.4E38 Giới hạn chỉ trị tuyệt đối.
Tuy nhiên kiểu float chỉ có 7 chữ số có nghĩa. Các kiểu dữ liệu cấu trúc. Đó là CTDL tiên định rất hay dùng đã được cài đặt sẵn trong các ngôn ngữ lập trình, người lập trình chỉ việc dùng như: Tập hợp, mảng, bản ghi, tệp,.và cung cấp cơ chế cho lập trình viên tự định nghĩa kiểu dữ liệu mới. (Khi nghiên cứu đến môt ngôn ngữ nào đó́ cầ̀n phải nghiên cứu kỹ cac kiêu dư liêu câu truc của nó́ .) Kiểu tập hợp : Một tập hợp bao gồm một số các đối tượng nào đó có cùng bản chất, được mô tả bởi cùng một kiểu, kiểu này là kiểu cơ bản (kiểu vô hướng đếm được hay đoạn con, liệt kê), không được là kiểu số thực.
Các đối tượng này được gọi là các phần tử của tập hợp. Số lượng phần tử của tập hợp thông thường là từ 0 (gọi là tập rỗng) đến tối đa là 255 phần tử. Kiểu Mảng : Là một tập hợp gồm một số cố định các phần tử có cùng kiểu dữ liệu. Mỗi phần tử của mảng ngoài giá trị còn được đặc trưng bởi chỉ số (Index) thể hiện thứ tự của phần tử đó trong mảng (Vectơ là mảng 1 chiều, mỗi phần tử ai của nó ứng với một chỉ số i.
Ma trận là mảng 2 chiều mỗi phần tử aij của nó ứng với 2 chỉ số i và j,. Kiểu bản ghi (kiểu cấu trúc): là một tập hợp các phần tử dữ liệu (field), mỗi phần tử dữ liệu có thể được mô tả bởi một kiểu dữ liệu khác nhau nhưng có liên kết với nhau, dùng để mô tả một đối tượng (Record). Tệp tin (File): Là một tập hợp các dữ liệu có liên quan với nhau và có cùng kiểu dữ liệu được nhóm lại tạo thành một dãy. Chúng thường được chứa trong môt thiết bị nhớ ngoài của máy tính với một cái tên nào đó.5 : Để mô tả một đối tượng sinh viên, cần quan tâm đến các thông tin sau: Mã sinh viên: chuỗi ký tự.
Tên sinh viên: chuỗi ký tự. 15 Ngày sinh: kiểu ngày tháng. Điểm thi: số thực. Các kiểu dữ liệu cơ sở cho phép mô tả một số thông tin như : float Diemthi; Các thông tin khác đòi hỏi phải sử dụng các kiểu có cấu trúc như : char masv[15]; char tensv[25]; Để thể hiện thông tin về ngày tháng năm sinh cần phải xây dựng một kiểu bản ghi.
typedef struct Date { unsigned char ngay; unsigned char thang; unsigned int nam; }; Cuối cùng, ta có thể xây dựng kiểu dữ liệu thể hiện thông tin về một sinh viên: typedef struct SinhVien { char masv[15]; char tensv[25]; Date ngsinh; float Diemthi; }; Giả sử đã có cấu trúc phù hợp để lưu trữ một sinh viên, nhưng thực tế lại cần quản lý nhiều sinh viên, lúc đó nảy sinh nhu cầu xây dựng kiểu dữ liệu mới (kiểu mảng bản ghi,…).