Giáo trình Cấu trúc dữ liệu

Giáo trình Cấu trúc dữ liệu gồm 5 chương với nội dung: 1 số khái niệm thuật toán, cấu trúc dữ liệu, giải thuật đề quy, các thuật toán sắp xếp và tìm kiếm, danh sách liên kết, cấu trúc dữ liệu Cây.
Nội dung trích xuất từ tài liệu:
Giáo trình Cấu trúc dữ liệu GIÁO TRÌNH CẤU TRÚC DỮ LIỆU Giáo trình Cấu trúc dữ liệu 2 LỜI NÓI ĐẦU Cấu trúc dữ liệu và Giải thuật là môn học đóng vai trò quan trọng trong quá trình đào tạo kỹ sư, cử nhân các ngành Khoa học máy tính và Công nghệ thông tin. Cuốn giáo trình này được nghiên cứu và hình thành dựa trên cơ sở mục tiêu đào tạo và đề cương chi tiết của môn học Cấu trúc dữ liệu và Giải thuật do Hội đồng nghiên cứu khoa học, t ổ Tin h ọc Khoa Kỹ thuật trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương xây dựng. Cuốn giáo trình này trình bày các vấn đề có bản nhất, thiết yếu nhất v ề hai khái niệm DỮ LIỆU và GIẢI THUẬT, đó cũng là nền tảng quan trọng cho những ai muốn nghiên cứu trong lĩnh vực tin học. Nội dung cuốn sách gồm 5 chương * Chương 1: MỘT SỐ KHÁI NIỆM: trình bày một số khái niệm về thuật toán: Ký hiệu ô lớn và các phương pháp phân tích, đánh giá tru ật toán; cấu trúc dữ liệu: Các kiểu dữ liệu trừu tượng cùng các phép toán trên các kiểu dữ liệu đó. Ở đây trình bày hệ ki ểu cấu trúc Dữ li ệu c ủa ngôn ngữ lập trình Pascal. * Chương 2: GIẢI THUẬT ĐỆ QUY: trình bày về đệ quy, một số thuật toán ứng dụng đệ quy. * Chương 3: CÁC THUẬT TOÁN SẮP XẾP VÀ TÌM KIẾM: trình bày nội dung, giải thuật của một số thuật toán sắp xếp, tìm ki ếm cơ b ản, hay gặp. So sánh, đánh giá, nhận xét ưu nhược điểm của mỗi loại thuật toán. * Chương 4: DANH SÁCH LIÊN KẾT: trình bày mô hình dữ liệu ki ểu Danh sách, các cấu trúc dữ liệu cài đặt danh sách, các phép toán trên danh sách. Trong đó hai cấu trúc đặc biệt STACK và QUEUE được nghiên cứu kỹ . * Chương 5: CÂY: trình bày cấu trúc dữ liệu Cây: Biểu diễn cây cùng với các phép toán cơ bản trên cây, trong đó Cây nhị phân được đặc biệt chú ý. Đọc xong cuốn sách này người đọc được cung cấp đầy đủ các khái niệm, các thuật toán từ cơ bản đến nâng cao, phù hợp cho Gi ảng viên cũng như HS - SV ngành Công nghệ Tin học nghiên cứu học tập. Toàn bộ các chương, mục đều có ví dụ, hình vẽ minh ho ạ cụ thể. Cuối mỗi Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương Giáo trình Cấu trúc dữ liệu 3 chương đều có phần tóm tắt lại những ý chính, những ví dụ ứng dụng … và bài tập (Lý thuyết và thực hành) để bạn đọc có th ể đúc rút đ ược n ội dung, củng cố được kiến thức của mỗi chương. Do tính đặc thù c ủa ngôn ngữ lập trình Pascal nên toàn bộ các ví dụ, bài tập trong giáo trình đ ều được viết bằng ngôn ngữ lập trình này, vì vậy người đọc chỉ cần biết sử dụng ngôn ngữ Pascal ngoài ra không đòi hỏi các kiến thức chuyên môn khác. Chúng tôi đã có nhiều cố gắng trong việc trình bày tinh giản một khối lượng kiến thức đồ sộ, cố gắng đặt vấn đề và giải quyết vấn đề, trình bày các khái niệm thật Logic, tự nhiên, sử dụng ngôn từ trong sáng, các ví dụ sát với thực tế dễ hiểu, dễ áp dụng, các bài tập có tính kh ả thi cao nhưng cũng không quá khó…để giúp bạn đọc dễ dàng hơn trong nghiên cứu, học tập. Tuy vậy cuốn sách chắc chắn không tránh khỏi những thiếu sót, những vấn đề cần bổ xung, những vấn đề cần lược bỏ, Chúng tôi chân thành mong nhận được ý kiến đóng góp, phê bình của độc giả để cuốn sách này có thể hoàn chỉnh hơn nữa. Thư góp ý xin gửi về địa chỉ: phamhuy_ktkt@yahoo.com Tôi xin chân thành cảm ơn Thầy chuyên gia Trịnh Nhật Tiến (Trưởng khoa Công nghệ thông tin trường ĐH Công nghệ Hà Nội) cùng các thầy giáo trong tổ bộ môn Tin học, khoa K ỹ thu ật trường Cao đ ẳng Kinh tế - Kỹ thuật Hải Dương đã đọc bản thảo và góp nhiều ý kiến v ề nội dung để tôi có thể hoàn thành cuốn tài liệu này. Hải Dương, tháng 8 năm 2005 Tác giả: PHẠM TRỌNG HUY Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương Giáo trình Cấu trúc dữ liệu 4 Chương 1: MỘT SỐ KHÁI NIỆM 1.1 Khái niệm thuật toán (Giải thuật) 1.1.1 Khái niệm. Thuật toán là một dãy hữu hạn các quy tắc ( chỉ thị, m ệnh l ệnh) mô tả chính xác một quá trình tính toán. Theo đó với mỗi bộ dữ li ệu vào s ẽ cho một kết quả ( Yêu cầu của bài toán ). Các đặc trưng c ủa Thu ật toán đơn định: * Tính đơn định: Thực hiện đúng các bước của thuật toán với một dữ liệu vào thì chỉ cho duy nhất một kết quả nghĩa là ở mỗi bước c ủa thuật toán, các thao tác phải hết sức rõ ràng, không gây nên sự nh ập nhằng, lộn xộn, đa nghĩa.... * Tính dừng: Thuật toán phải dừng và cho ra kết quả sau một số hữu hạn các bước. * Tính đúng: Cho ra kết quả phù hợp yêu cầu bài toán với những dữ liệu vào đúng đắn. * Tính phổ dụng: Thuật toán phải giải quyết được một lớp rộng các bài toán. * Tính khả thi: Thuật toán phải được máy tính thực hiện trong khoảng thời gian và điều kiện ( bộ nhớ ) cho phép. Để mô tả một thuật toán có thể sử dụng nhiều phương pháp khác nhau, đối với các bài toán đơn giản phải mô tả Thuật toán một cách tường minh đầy đủ, đối với các bài toán lớn mà trong đó có những thuật toán chuẩn, quen thuộc ta có thể mô tả tổng thể, những ch ỗ đã bi ết có th ể chú thích hoặc có thể bỏ qua. Khi đó ta chỉ tập trung giải quyết các phần trọng điểm tránh việc làm cho mô tả Thuật toán rắc rối phức tạp. 1.1.2. Các bước phân tích bài toán. Bước đầu tiên trong việc phân tích một thu ật toán là xác định đ ặc trưng dữ liệu sẽ được dùng làm dữ liệu nhập của thuật toán và quyết định phân tích nào là thích hợp. Về mặt lý tưởng, chúng ta muốn rằng với một phân bố tùy ý được cho của dữ liệu nhập, sẽ có sự phân bố tương ứng về thời gian hoạt động của thuật toán. Chúng ta không thể đạt tới điều lý tưởng này cho bất kỳ một thuật toán nào, vì vậy chúng ta chỉ quan tâm Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thu ...