Tài liệu tham khảo môn học Cấu trúc dữ liệu

Tài liệu tham khảo môn học Cấu trúc dữ liệu gồm 8 chương với mục tiêu giới thiệu cho học sinh về khái niệm về kiểu dữ liệu trừu tượng, kiểu dữ liệu trừu tượng, cấu trúc dữ liệu thông dụng, nâng cao và những thao tác trên các cấu trúc đó, một số thuật toán cơ bản và rèn luyện một số kĩ năng phân tích thuật toán.
Nội dung trích xuất từ tài liệu:
Tài liệu tham khảo môn học Cấu trúc dữ liệuTài liệu tham khảomôn học cấu trúc dữ liệu  -1- LỜI NÓI ĐẦUGiáo trình này được viết cho sinh viên các trường Cao đẳng Đại họcĐể học tốt giáo trình này sinh viên cần có kiến thức về tin học cơ sở và đã biết mộtngôn ngữ lập trình bậc cao như Pascal, Delphi, C hay C++...Giáo trình được viết nhằm những mục tiêu sau đây: Giới thiệu cho học sinh về khái niệm về kiểu dữ liệu trừu tượng. Cung cấp cho học sinh kiến thức cơ bản về những kiểu dữ liệu trừu tượng, cấu trúc dữ liệu thông dụng, nâng cao và những thao tác trên các cấu trúc đó. Cung cấp một số thuật toán cơ bản và rèn luyện một số kĩ năng phân tích thuật toán cho học sinh. Rèn luyện cho học sinh cách áp dụng các cấu trúc dữ liệu đã học và tư duy thuật toán để có thể thiết kế và cài đặt một số chương trình bằng một ngôn ngữ bậc cao.Để có thể học tốt các chương sau, sinh viên cần đọc kĩ chương 1 và chương 2.Chương 1 giới thiệu những khái niệm cơ bản về thuật giải. Chương 2 giới thiệu nhữngkhái niệm cơ bản về kiểu dữ liệu trừu tượng. Đây là khái niệm mới đối với học sinh.Một kiểu dữ liệu trừu tượng là một tập hợp các đối tượng và được xác định hoàn toànbởi các phép toán có thể biểu diễn trên các đối tượng đó. Người sử dụng được phéptìm hiểu các đối tượng và thực hiện các thao tác trên các đối tượng của kiểu dữ liệuthông qua các phép toán đó mà không cần quan tâm đến việc đối tượng được cài nhưthế nào trong ngôn ngữ lập trình. Chúng tôi có đưa ra một vài ví dụ đơn giản về kiểudữ liệu trừu tượng, cách đặc tả và xây dựng chúng để định hướng cho việc đặc tả vàxây dựng những kiểu dữ liệu trừu tượng trong những chương sau.Trong khi trình bày mỗi kiểu dữ liệu trừu tượng ở mỗi chương sau, chúng tôi cố gắngkhuyến khích sinh viên trước hết phải hiểu một cách khái quát về kiểu dữ đó trước khiquan tâm đến việc cài đặt chi tiết bên trong. Điều đó không có nghĩa là chúng tôikhông coi trọng việc cài đặt. Việc tách riêng đặc tả bên ngoài và bên trong cho phép tanhìn rõ trước hết vào bản chất của một kiểu dữ liệu trừu tượng là tập các thao tác trên -2-các đối tượng của kiểu dữ liệu đó. Và chỉ khi đã hiểu rõ bản chất của các thao tác trênmột kiểu dữ liệu trừu tượng chúng ta mới chuyển tới việc cài đặt những thao tác đóbằng một ngôn ngữ bậc cao nào đó. Công cụ cho phép ta bóc tách một cách khái niệmhình thức bên ngoài và chi tiết bên trong đó chính là kiểu dữ liệu trừu tượng.Từ chương 3 đến chương 6 dành cho việc nghiên cứu một số kiểu dữ liệu trừu tượngcơ bản tuyến tính và phi tuyến. Đó là các kiểu dữ liệu trừu tượng ngăn xếp, hàng đợi,cây, bảng tìm kiếm, tập hợp và đồ thị... Với mỗi kiểu dữ liệu trừu tượng đưa ra, chúngđều được đặc tả bởi các thao tác cơ bản và hướng dẫn cài đặt một số thao tác. Nhữngthao tác đưa ra là những thao tác cơ bản nhất. Tuy nhiên, tuỳ theo điều kiện và hoàncảnh, học sinh có thể bổ sung thêm một số những thao tác khác. Trong việc xây dựngcác kiểu dữ liệu trừu tượng, chúng tôi rất nhấn mạnh việc quan tâm đầu tiên là đặc tảđược các thao tác cần thiết (xây dựng mô đun ngoài), sau đó mới đến việc cài đặt cácthao tác (xây dựng mô đun trong). Ngoài ra, chúng tôi cũng quan tâm đến việc hướngdẫn sử dụng các kiểu dữ liệu trừu tượng thông qua những ví dụ về những mô đun ứngdụng.Sinh viên ắt hẳn đã được giới thiệu một vài thuật toán sắp xếp đơn giản trên mảng từphần Tin học đại cương. Tuy nhiên, bài toán sắp xếp và tìm kiếm là bài toán hết sứccơ bản đối với mỗi sinh viên Cao đẳng và Đại học nên chúng tôi dành riêng chương 7để nói về một số giải thuật sắp xếp đơn giản cũng như một số giải thuật sắp xếp nângcao, cần đến một chút kiến thức về kiểu dữ liệu trừu tượng vừa học trong các chươngtrước. Một số phép so sánh các giải thuật sắp xếp cũng được đề cập trong chương này.Để giúp học sinh có thêm một số kiến thức về thuật giải, trong chương 8, chúng tôitrình bày một số phương pháp thiết kế thuật giải như đệ qui, quay lui, chia dể trị, thamlam, qui hoạch động. Đây là những phương pháp rất cơ bản và thông dụng trong khoahọc máy tính. Bạn đọc có thể tìm thấy nhiều ví dụ minh hoạ cho những phương phápnày. Các ví dụ đều được cài đặt cụ thể bằng ngôn ngữ lập trình Pascal.Cuối mỗi chương đều có hệ thống bài tập để học sinh làm và tự kiểm tra kiến thức củamình.Cuối cùng là phần phụ lục, trong đó chúng tôi có đưa ra một số bài tập lớn, để học sinháp dụng những kiến thức đã học tập giải quyết những vấn đề phức tạp hơn so với bài -3-tập sau mỗi chương. Với những bài tập lớn này, để nâng cao hiệu quả, yêu cầu họcsinh cần đặc tả rõ bài toán, phân tích và thiết kế thuật giải, sau đó cài đặt trên một ngônngữ cụ thể. Tiếp theo học sinh cần phải kiểm thử phần mềm mình vừa cài đặt và cónhững nhận xét về độ phức tạp của thuật toá ...