Cấu trúc dữ liệu và giải thuật là một trong những khối kiến thức cơ sở trong chương trình đào tạo cử nhân ngành Công nghệ Thông tin của Khoa Công nghệ Thông tin, trường Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh. Khối kiến thức này được giảng dạy trong hai môn học: Cấu trúc dữ liệu 1 và Cấu trúc dữ liệu 2. | TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HỒ CHÍ MINH KHOA CÔNG NGHỆ THÔNG TIN CẤU TRÚC DỮ LIỆU 1 Biên soạn ThS. Lê Văn Vinh Thành phố Hố Chí Minh 2009 Cấu trúc dữ liệu 1 2 LỜI NÓI ĐẦU Cấu trúc dữ liệu và giải thuật là một trong những khối kiến thức cơ sở trong chương trình đào tạo cử nhân ngành Công nghệ Thông tin của Khoa Công nghệ Thông tin trường Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh. Khối kiến thức này được giảng dạy trong hai môn học Cấu trúc dữ liệu 1 và Cấu trúc dữ liệu 2. Cấu trúc dữ liệu 1 cung cấp cho người học những kiến thức về các kiểu dữ liệu trừu tượng cơ bản thường được sử dụng khi xây dựng chương trình trên máy tính cách hiện thực và áp dụng các kiểu dữ liệu đó trong thực tế. Nội dung của bài giảng bao gồm 7 chương bao quát hầu hết các vấn đề cốt lõi của môn học. Nội dung trong mỗi chương được trình bày theo trình tự trình bày các khái niệm các kiến thức cơ bản trước tiếp theo là nêu những ví dụ minh họa để người đọc dễ dàng tiếp cận lý thuyết mới và sau cùng là cài đặt giải thuật bằng ngôn ngữ lập trình cụ thể. Cuối mỗi chương đều có bài tập để người đọc tự kiểm tra và củng cố lại kiến thức của mình. Rất mong nhận được những ý kiến đóng góp của các đồng nghiệp và các bạn sinh viên để bài giảng ngày càng hoàn thiện hơn. Mọi ý kiến đóng góp xin vui lòng gửi theo địa chỉ email levinhcntt@. Khoa Công nghệ Thông tin - Đại học Sư phạm Kỹ thuật TP. HCM Cấu trúc dữ liệu 1 3 CHƯƠNG 1. TÔNG QUAN Chương này trình bày những khái niệm cơ bản liên quan đến cấu trúc dữ liệu vai trò và ý nghĩa của cấu trúc dữ liệu trong việc xây dựng một chương trình trên máy tính và cách để đánh giá độ phức tạp của giải thuật. I. Từ bài toán đến chương trình Máy tính là công cụ giúp con người giải quyết một vấn đề một bài toán trong thực tế. Khi viết một chương trình yêu cầu máy tính thực hiện công việc nào đó chúng ta cần phải tiến hành theo các bước cơ bản sau 1. Xác định bài toán Ở bước này ta xác định xem cần phải giải quyết vấn đề gì. Những giả thiết nào đã cho
