Giáo trình Cấu trúc dữ liệu và giải thuật - ĐH Sư phạm Quy Nhơn

Giáo trình Cấu trúc dữ liệu và giải thuật có nội dung gồm 6 chương, trong mỗi chương của giáo trình có kiến thức lý thuyết được trình bày cơ bản rõ ràng, được minh họa chi tiết với những ứng dụng cụ thể, cuối mỗi chương đều cung cấp một hệ thống các bài tập từ cơ bản đến nâng cao nhằm giúp cho sinh viên rèn luyện tư duy, kỹ thuật lập trình và hiểu rõ hơn những nội dung lý thuyế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à giải thuật - ĐH Sư phạm Quy Nhơn TRƯỜNG  ĐẠI  HỌC  SƯ  PHẠM  QUY  NHƠN KHOA  TIN  HỌC TRẦN  THIÊN  THÀNH Giáo trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Quy  nhơn,  10/2002 LỜI  NÓI  ĐẦU Cấu  trúc  dữ  liệu  và  giải  thuật  là  một  môn  học  bắt  buộc  trong  chương  trình   đào  tạo  cử  nhân  Tin  học  và  Công  nghệ  thông  tin.  Giáo  trình  này  được  hình  thành   dựa  trên  nội  dung  giảng  dạy  nhiều  năm  tại  khoa  Tin  học  trường  Đại  học  sư  phạm   Quy  nhơn  của  tác  giả. Nội  dung  giáo  trình  gồm  6  chương: Chương   1   trình   bày   một   số   kiến   thức   cơ   bản   về   cấu   trúc   dữ liệu   và   giải   thuật. Chương  2  trình  bày  về  mô  hình  dữ  liệu  danh  sách.  Trong  chương  cũng  giới   thiệu  hai  kiểu  dữ  liệu  trừu  tượng  là  Stack  và  Queue  cùng  với  một  số  ứng  dụng  tiêu   biểu. Chương  3  trình  bày  về  mô  hình  cây,  chủ  yếu  tập  trung  vào  cây  tìm  kiếm  nhị   phân,  cây  cân  bằng  và  một  số  ứng  dụng. Chương   4   trình   bày   về   mô   hình   đồ   thị   và   một   số   thuật   toán   thường   dùng   trên  đồ  thị. Chương  5  trình  bày  về  cách  tổ  chức  dữ  liệu  cho  bộ  nhớ  ngoài. Chương  6  trình  bày  các  thuật  toán  sắp  xếp  trong  và  sắp  xếp  ngoài. Giáo trình   được   soạn   trên   cơ   sở   chương   trình   đào   tạo   của   Khoa.   Một   số   kiến  thức  về  thuật  toán  và  kỹ  thuật  lập  trình  sinh  viên  đã  được  học  trong  các  môn   học  trước  đó  nên  không  được  đề  cập  trong  giáo  trình  này.  Giáo  trình  dùng  làm  tài   liệu  học  tập  cho  sinh  viên  năm  thứ  ba  hoặc  học  kỳ  2  của  năm  thứ  hai  ngành  Tin   học  và  Công  nghệ  thông  tin  với  thời  lượng  75  tiết.  Ngoài  ra,  giáo  trình  có  thể  dùng   cho  sinh  viên  thuộc  các  ngành  Toán  học,  Kỹ  thuật  và  những  người  muốn  có  kiến   thức  sâu  hơn  về  các  cấu  trúc  dữ  liệu  thường  dùng trong  lập  trình. Trong  mỗi  chương  của  giáo  trình,  các  kiến  thức  lý  thuyết  được  trình  bày  cơ   bản,   rõ   ràng,   được   minh   hoạ   chi   tiết   cùng   với   những   ứng   dụng   cụ   thể   giúp   cho   người   học   dễ   đọc,   dễ   hình   dung   những   ứng   dụng   của   các   cấu   trúc   dữ   liệu   trong   một  số  ứng  dụng  điển  hình.  Do  đó  giáo  trình  có  thể  dùng  làm  tài  liệu  tự  học  cho   những   người   đã   có   những   kiến   thức   cơ   bản   về   thuật   toán   và   lập   trình   trên   một   ngôn  ngữ  lập  trình  bậc  cao.  Nội  dung  trong  giáo  trình  bám  sát  những  nội  dung  cơ   bản  về  các  cấu  trúc  dữ  liệu  mà  các  chương  trình  đào  tạo  cử  nhân  Tin  học  và  Công   nghệ  thông  tin  yêu  cầu.  Cuối  mỗi  chương  đều  cung  cấp  một  hệ  thống  các  bài  tập   từ   cơ   bản   đến   nâng   cao   nhằm   giúp   cho   sinh   viên   rèn   luyện   tư   duy,   kỹ   thuật   lập   trình  và  hiểu  rõ  hơn  những  nội  dung  lý  thuyết. Trong   giáo   trình   sử   dụng   ngôn   ngữ   lập   trình   Pascal   để   minh   hoạ   các   cấu   trúc  dữ  liệu  và  thuật  toán  để  giúp  sinh  viên  dễ  hình  dung  hơn  trong  cài  đặt  thành   chương  trình.  Các  cấu  trúc  dữ  liệu  được  tổ  chức  dưới  hình  thức  bao  gói  thông  tin,   mỗi  cấu  trúc  dữ  liệu  được  xem  như  một  kiểu  dữ  liệu  độc  lập.  Các  thuật  toán  trình   bày   dưới   dạng   ngôn   ngữ   tự   nhiên   và   được   hoàn   chỉnh   bằng   những   thủ   tục   viết   2 bằng  Pascal  nên  rất  thuận  tiện  cho  sinh  viên  trong  thực  hành  bằng  Pascal  hay  bất   kỳ  một  ngôn  ngữ  lập  trình  bậc  cao  nào  mà  mình  ưa  thích. Để  hoàn  thành  giáo  trình  này  tác  giả  đã  nhận  được  nhiều  ý  kiến  đóng  góp   và  động  viên  của  các  đồng  nghiệp,  đặc  biệt  là  ThS  Hồ  Anh  Minh  đã  đọc  bản  thảo   và  đóng  góp  nhiều  ý  kiến  quý  báu. Do  thời  gian  và  khả  năng  còn  hạn  chế  nên  giáo  trình  không  thể  tránh  khỏi   những  khiếm  khuyết  nhất  định.  Chúng  tôi  chân  thành  và  mong  đón  nhận  những  ý   kiến  đóng  góp  của  độc  giả. Tác  giả 3 MỤC  LỤC Lời  nói  đầu .....................................................................................................2 Mục  lục ..........................................................................................................4 Chương  1 Tổng  quan  về  Cấu  trúc  dữ  liệu  và  giải  thuật ................................8 1.  Tổng  quan  về  thuật  toán .........................................................................8 1.1.  Khái  niệm  thuật  toán .......................................................................8 1.2.  Các  đặc  trưng  của  thuật  toán ...........................................................8 1.3.  Tiêu  chuẩn  đánh  giá  thuật  toán ........................................................9 1.4.  Độ  phức  tạp  của  thuật  toán ..............................................................9 1.5.  Ký  hiệu  O-lớn ................................................................................11 2.  Kiểu  dữ  liệu  và  cấu  trúc  dữ  liệu ...........................................................11 2.1.  Kiểu  dữ  liệu ...................................................................................11 2.2.  Cấu  trúc  dữ  liệu .............................................................................12 2.3.  Mô  hình  dữ  liệu ......................................................................... ...