Giáo trình Cấu trúc dữ liệu và thuật toán (Tái bản): Phần 1

Phần 1 giáo trình "Cấu trúc dữ liệu và thuật toán" trình bày các nội dung: Nhập môn cấu trúc dữ liệu, cấu trúc dữ liệu tuyến tính, cấu trúc dữ liệu phi tuyến, nhập môn thuật toán, các dạng thuật toán cơ bản. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Giáo trình Cấu trúc dữ liệu và thuật toán (Tái bản): Phần 1 C k !oÔ oỐ681 68 Ỗ G NGHĨA TÝ CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN ■ NGUYÊN ỌC LIỆU I PGS. TS. HOÀNG NGHĨA TÝ CẤU TRÚC Dữ LIỆU ■ VÀ THUẬT TOÁN ■ (Tái bản) NHA xuẩt bả n xây d ự n g HÀ NỘI-2014 LỜI NÓI ĐẦ U Cấu trúc dữ liệu và thuật toán là môn học cơ sở ngành của ngành công nghệ thông tin. Chúng ta hãy hình dung một tòa nhủ có phần nền móng, phin tường cột (kết cấu chịu lực) và những phần khác còn lại, nếu plĩần kết cấu chịu lực không vững thì tòa nhà không thể vững được. Môn 'Cấu trúc dữ liệu và thuật toán' chính là môn học thuộc phần rường cột, phẩn kết cấu chịu lực đó của tòa nhà 'Công nghệ thông tin'. Khi học môn học nà) đòi hỏi sinh viên phải có đầu óc tư duy logic toán học đ ể hiểu thuật toáĩ, đồng thời phải có kỹ năng lập trình đ ể diễn đạt sơ đồ thuật toán thành cứu lệnh. Có thể sơ đổ thuật toán vẽ hết cả một trang giấy nhưng chuyển sang lập trình chỉ có vài dòng; có th ể sơ đồ thuật toán trình bày theo kiểu kiểm tra điều kiện đ ể riếp tục ngay ở đầu nhưng khi chuyển sang lập trình có th ể dùng các câu lệnh có cấu trúc điều khiển lặp với kiểu kiểm tra điều kiện trước hoặc sa u ... Giáo trình ' Cấu trúc dữ liệu và thuật toán' này được xuất bản lần đầu năm 2006, do Nhà xuất bản Xây dựng ấn hành. Từ đó đến nay thời lượng cũng như kết cấu môn học đã có nhiều thay đổi. Ớ Trường Đại học Xây dựng từ năm 2009 môn 'Cấu trúc dữ liệu và thuật toán' đã được tách thành hai học phần là 'Nhập môn Cấu trúc clữ liệu và thuật toán' và 'Cấu trúc dữ liệu và thuật toán nâng cao' veri mỗi học phần có 2 tín chỉ. Lý do là vì trong Khoa Công nghệ thông tin có nhiêu chuyên ngành khác nhíiu, có chuyên ngành chỉ cần học một học phần, có chuyên ngành cần p h ii học cả hai học phần. D ể đáp ứng sự thay đổi trên, trong mấy năm qua tác giả đã biên soạn lụi đê cương chi tiết cho từng học phần và nội dung chương mục tương ứnị, đã viết lại một số chương trình cho một s ố thuật toán, trình bày lại một s ố sơ đồ thuật toán (hoán vị ma trận thưa, danh sách liên kết, sắp xếp theo kiểu chèn..), viết thêm một sô' nội dung cho học phần Cấu trúc dữ liệu và thuật toán nâng cao (kiến thức nâng cao về con trỏ, đệ quy, 3 duyệt cây nhị phân, file mỡ, file text, danh sách liên kết, danh sách Hên kết vòng và liên kết đ ô i...). Với thời lượng 2 tín chỉ, nội dung học phần 'Nhập môn Cấu trúc dữ liệu và thuật toán' sẽ được trình bày ở chương 1, chương 2, các mục 3.1, 3.2, 3.3 của chương 3, riêng các mục 3.3 đến 3.8 chỉ dừng ở các kiến thức cơ bản, chương4, chương 5, chương 7 (mục 7.1, 7.2, 7.3), chương 8 (mục 8 . 1, 8 2 ). Với thời lượng 2 tín chỉ, nội dung học phần 'Cấu trúc dữ liệu và thuật toán nâng cao' sẽ à phần mở rộng, nâng cao trong các mục 3.3 đến 3.8 của chương 3, chương 6, chương 7 (mục 7.4, 7.5), chương 8 (mục 8.3), chương 9. Ngoài những phần lý thuyết và chương trình ví dụ, trong tài liệu còn giới thiệu một sô'chương trình tổng hợp, giúp cho bạn đọc tìm hiểu sâu hơn các thuật toán đã trình bày. Đây thực chất là một sô' kết quả của nhiều năm nghiên cứu và giảng dạy công nghệ thông tin cũng như hướng dẫn sinh viên của tác giả: chương trình quàn lý tiền lương được soạn lại trên cơ sở phần mềm tính lương cho Phòng Tài vụ trường ĐHXD những năm 1990, chương trình sơ đồ mạng được viết từ những năm 1980-1981 chạy trên máy tính Minsk-32, chương trình quy hoạch động là diễn giải thuật toán cùa đê tài 'Thiết k ế tối ưu kết cấu mặt đường mềm nhiều lớp' được tiến hành một cách nung nấu kiên trì trong những năm 1975-1977, chương trình quản lý thi trắc nghiệm là một phần của đề tài 'Xảy dựng Ngân hàng đề thi và phần mềm phục vụ thi trắc nghiêm môn Tin học đại cương' năm 2001. Quyển sách này được dùng làm giáo trình cho học viên, sinh viên ngành công nghệ thông tin và các ngành khác có học các môn tin học ứng dụng. Tác giả rất cảm ơn sinh viên và đồng nghiệp trong quá trình làm việc, giúp phát sinh ỷ tưởng hoàn thiện giáo trình, tuy đã rất c ố gắng nhưng không th ể tránh khỏi thiếu sót. Rất mong nhận được góp ỷ của độc giả đ ể lần tái bàn sau sách được hoàn thiện hơn. Mọi góp ý xin gửi về Bộ môn Công nghệ phần mềm, Khoa Công nghệ thông tin Trường đại học Xây dựng Hà Nội. Tác giả 4 Phẩn I CẤU TRÚC DỮ LIỆU Chương 1 NHẬP MÔN CẤU TRÚC DỮ LIỆU 1.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ả. 1.1.1. 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á ...