Giáo trình Cấu trúc dữ liệu và giải thuật - Trần Thiên Thành

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 2 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   3 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ả 4 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 .............................................................................12 2.4.  Các  tiêu  chuẩn  của  cấu  trúc  dữ  liệu ...............................................12 3.  Mối  liên  hệ  giữa  cấu  trúc  dữ  liệu  và  giải  thuật .....................................13 3.1.  Mối  liên  hệ .....................................................................................13 3.2.  Một  số  ví  dụ  minh  họa ...................................................................13 4.  Bài  tập ..................................................................................................15 Chương  2 Danh sách ...................................................................................17 1.  Khái  niệm  và  các  thao  tác ....................................................................17 1.1.  Định  nghĩa  danh  sách ....................................................................17 1.2. Các thao tác trên danh sách ...........................................................17 2.  Biểu  diễn  danh  sách  bằng  mảng ...........................................................18 2.1.  Tổ  chức  dữ  liệu ..............................................................................18 2.2. Các thao tác trên danh sách ...........................................................19 3.  Danh  sách  liên  kết  đơn .........................................................................24 3.1.  Cấp  phát  động,  biến  con  trỏ  và  các  thao  tác ..................................24 3.2.  Khái  niệm  danh  sách  liên  kết .........................................................25 3.3.  Tổ  chức  danh  sách  liên  kết ............................................................25 3.4.  Các  phép  toán  trên  danh  sách  liên  kết ...........................................26 5 3.5.  So  sánh  cấu  trúc  dữ  liệu  danh  sách  liên  kết  đơn  và  mảng .............29 3.6.  Một  số  dạng  danh  sách  liên  kết  khác .............................................29 4.  Ngăn  xếp  (Stack) ..................................................................................34 4.1.  Khái  niệm ......................................................................................35 4.2.  Tổ  chức  ngăn  xếp  bằng  mảng ........................................................36 4.3.  Tổ  chức  ngăn  xếp  bằng  danh  sách  liên  kết ....................................38 4.4.  Ứng  dụng  của  ngăn  xếp .................................................................40 5.  Hàng  đợi  (Queue) .................................................................................44 5.1.  Khái  niệm ......................................................................................44 5.2.  Tổ  chức  hàng  đợi  bằng  mảng ........................................................45 5.3.  Tổ  chức  hàng  đợi  bằng  danh  sách  liên  kết ....................................49 6.  Bài  tập ..................................................................................................51 Chương  3 Cây .............................................................................................57 1.  Các  khái  niệm  về  cây ...........................................................................57 1.1.  Khái  niệm  cây ................................................................................57 1.2.  Một  số  khái  niệm  khác ..................................................................58 2.  Cây  nhị  phân .........................................................................................59 2.1.  Khái  niệm ......................................................................................59 2.2.  Biểu  diễn  cây  nhị  phân ..................................................................60 2.3.  Duyệt  cây  nhị  phân ........................................................................63 2.4.  Cây  tìm  kiếm  nhị  phân ..................................................................67 2.5.  Các  thao  tác  trên  cây  tìm  kiếm  nhị  phân .......................................68 3.  Cây  cân  bằng ........................................................................................74 3.1.  Khái  niệm ......................................................................................75 3.2.  Thêm  vào  cây  cân  bằng .................................................................76 3.3.  Loại  bỏ  khỏi  cây  cân  bằng .............................................................82 4.  Các  ứng  dụng  của  cây  nhị  phân ...........................................................88 4.1. Mã Huffman ..................................................................................88 4.2.  Cấu  trúc  dữ  liệu  Heap ....................................................................91 5.  Cây  tổng  quát .......................................................................................97 5.1.  Tổ  chức  dữ  liệu ..............................................................................97 5.2.  Các  thao  tác  trên  cây  tổng  quát................................................... 100 6 5.3.  Cây  tìm  kiếm  tổng  quát .............................................................. 103 6.  Bài  tập ............................................................................................... 105 Chương  4 Đồ  thị....................................................................................... 108 1.  Các  khái  niệm .................................................................................... 108 1.1.  Khái  niệm  đồ  thị  (Graph) ........................................................... 108 2.  Tổ  chức  dữ  liệu  biểu  diễn  đồ  thị ....................................................... 109 2.1.  Biểu  diễn  đồ  thị  bằng  ma  trận  kề  (adjacency  matrice) ............... 109 2.2.  Biểu  diễn  đồ  thị  bằng  danh  sách  kề  (adjacency  list) .................. 110 2.3.  Biểu  diễn  đồ  thị  bằng  danh  sách  cạnh  (cung) ............................. 111 3.  Duyệt  đồ  thị ....................................................................................... 112 3.1.  Duyệt  theo  chiều  sâu .................................................................. 112 3.2.  Duyệt  đồ  thị  theo  chiều  rộng ...................................................... 114 3.3.  Tìm  đuờng  đi  trên  đồ  thị ............................................................. 115 4.  Tìm  đường  đi  ngắn  nhất .................................................................... 117 4.1.  Đường  đi  ngắn  nhất  trên  đồ  thị  không  có  trọng  số ..................... 117 4.2.  Đường  đi  ngắn  nhất  trên  đồ  thị  có  trọng  số ................................ 118 5.  Cây  khung  của  đồ  thị ......................................................................... 126 5.1.  Khái  niệm  cây  khung  (Spanning  tree) ........................................ 126 5.2.  Thuật  toán  tìm  cây  khung  của  đồ  thị .......................................... 126 5.3.  Cây  khung  ngắn  nhất .................................................................. 127 5.4.  Thuật  toán  tìm  cây  khung  ngắn  nhất  của  đồ  thị ......................... 127 6.  Bài  tập ............................................................................................... 132 Chương  5 Các  cấu  trúc  dữ  liệu  ở  bộ  nhớ  ngoài ....................................... 134 1.  Mô  hình  tổ  chức  dữ  liệu  ở  bộ  nhớ  ngoài ........................................... 134 2.  File  băm ............................................................................................. 135 2.1.  Cấu  trúc  Bảng  băm  (Hash  Table) ............................................... 135 2.2.  File  Băm ..................................................................................... 142 3.  File  chỉ  số  (Indexed  File) .................................................................. 143 3.1.  Tổ  chức  File  chỉ  số ..................................................................... 144 3.2.  Các  thao  tác  trên  file  chỉ  số ........................................................ 144 4. B-Cây ................................................................................................ 145 4.1.  Khái  niệm  B-Cây ........................................................................ 146 7 4.2. Các thao tác trên B-Cây .............................................................. 147 5.  Bài  tập ............................................................................................... 149 Chương  6 Sắp  xếp .................................................................................... 151 1.  Các  thuật  toán  sắp  xếp  trong ............................................................. 151 1.1.  Sắp  xếp  bằng  cách  chọn  trực  tiếp ............................................... 151 1.2.  Sắp  xếp  bằng  cách  đổi  chỗ  trực  tiếp ........................................... 152 1.3.  Sắp  xếp  bằng  cách  chèn  trực  tiếp ............................................... 153 1.4.  Sắp  xếp  với  độ  dài  bước  giảm  dần ............................................. 155 1.5.  Sắp  xếp  trộn ................................................................................ 156 1.6.  Sắp  xếp  kiểu  vun  đống ............................................................... 156 1.7.  Sắp  xếp  bằng  phân  hoạch ........................................................... 159 2.  Sắp  xếp  ngoài .................................................................................... 160 2.1.  Trộn  hai  tệp  được  sắp ................................................................. 160 2.2.  Thuật  toán  sắp  xếp  trộn  tự  nhiên ................................................ 161 3.  Bài  tập ............................................................................................... 164 Tài  liệu  tham  khảo .................................................................................... 165 8 Chương  1 TỔNG  QUAN  VỀ  CẤU  TRÚC  DỮ  LIỆU  VÀ  GIẢI  THUẬT 1. TỔNG  QUAN  VỀ  THUẬT  TOÁN 1.1. Khái  niệm  thuật  toán Khái  niệm  thuật  toán  (Algorithm)  xuất  phát  từ  tên  một  nhà  toán  học  Arập   Abu  Ja'far  Mohamed  ibn  Musa  al’Khwarizmi, thường  gọi  là  al’Khwarizmi.  Ông  là   tác  giả  một  cuốn  sách  về  số  học,  trong  đó  ông  đã  dùng  phương  pháp  mô  tả  rất  rõ   ràng,  mạch   lạc  cách  giải  những  bài   toán.  Sau  này,  phương  pháp  mô   tả  cách  giải   của  ông  đã  được  xem   là  một   chuẩn  mực  và  được  nhiều  nhà   toán  học  khác   tuân   theo.  Thuật  ngữ  algorithm  ra  đời  từ  đó  dựa  theo  cách  phiên  âm  tên  của  ông.  Cùng   với   thời  gian  khái  niệm   thuật   toán  được  hoàn chỉnh  dần  và  khái  niệm  hình   thức   chính  xác   của   thuật   toán  được  định  nghĩa   thông  qua  mô  hình  máy  Turing.  Giáo   trình  này  không  đi  sâu  vào  những  khía  cạnh  lý  thuyết  của  thuật  toán  nên  chỉ  trình   bày  khái  niệm  không  hình  thức  của  thuật  toán:   Thuật  toán  là  một  hệ  thống  chặt  chẽ  và  rõ  ràng  các  quy  tắc  nhằm  xác  định   một  dãy  các  thao  tác  trên  những  đối  tượng  sao  cho  sau  một  số  hữu  hạn  bước  thực   hiện  các  thao  tác  thì  đạt  được  mục  tiêu  định  trước. 1.2. Các  đặc  trưng  của  thuật  toán Một  thuật  toán  thông  thường  có  6  đặc  trưng  cơ  bản  sau: 1.2.1. Tính  kết  thúc  (tính  dừng) Thuật  toán  bao  giờ  cũng  phải  dừng  sau  một  số  hữu  hạn  bước  thực  hiện. 1.2.2. Tính  xác  định Thuật  toán  yêu  cầu  ở  mỗi  bước  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  lộn,  tùy  tiện.  Khi  thực  hiện  thuật  toán,  trong  cùng  một  điều   kiện  thì  cho  cùng  một  kết  quả. 1.2.3. Tính  phổ  dụng Thuật  toán  phải  có  thể  giải  được  một  lớp  các  bài  toán.  Mỗi  thuật  toán  có  thể   làm  việc  với  những  dữ  liệu  khác  nhau  trong  một  miền  xác  định. 9 1.2.4. Đại  lượng  vào Mỗi  thuật  toán  thường  có  những  đại  lượng  vào  gọi  là  dữ  liệu  vào  để  cung   cấp  dữ  liệu  cho  thuật  toán.  Tuy  nhiên,  cũng  có  những  thuật  toán  không  có  dữ  liệu   vào. 1.2.5. Đại  lượng  ra Sau  khi  kết  thúc  thuật  toán,  tùy  vào  chức  năng  của  thuật  toán  mà  thu  được   một  số  đại  lượng  xác  định  gọi  là  đại  lượng  ra  hay  dữ  liệu  ra. 1.2.6. Tính  hiệu  quả Với  dữ  liệu  vào,  sau  một  số  hữu  hạn  bước  thực  hiện  thuật  toán  sẽ  dừng  và   cho  đúng  kết  quả  mong  muốn  với  thời  gian  chấp  nhận được. 1.3. Tiêu  chuẩn  đánh  giá  thuật  toán Một  bài   toán  có   thể  có  nhiều   thuật   toán  giải,  mỗi   thuật   toán  có  những  ưu   nhược  điểm  riêng.  Để  quyết  định  chọn  thuật  toán  nào  thông  thường  dựa  vào  2  tiêu   chuẩn  cơ  bản sau: 1. Thuật  toán  đơn  giản,  dễ  hiểu,  dễ  cài  đặt. 2. Thuật  toán  sử  dụng  tiết  kiệm  các  tài  nguyên  của  hệ  thống  máy  tính  như   bộ  nhớ,  thời  gian  chiếm  dụng  CPU  và  đặc  biệt  là  thời  gian  chạy. Trong  trường  hợp  chương  trình  ít  sử  dụng  và  giá  viết  chương  trình  vượt  xa   giá   chạy   chương   trình   thì   tiêu   chuẩn   1   được   ưu   tiên.   Với   những   chương   trình   thường  dùng  như  các  thư  viện,  các  chương  trình  hệ  thống  thì  tiêu  chuẩn  2  được  ưu   tiên  chọn  trước. Trong  tiêu  chuẩn  2,  tính  hiệu  quả  của  thuật  toán  bao  gồm  2  yếu  tố: - Dung lượng  không  gian  nhớ  cần  thiết  để  lưu  các  loại  dữ  liệu  và  các  kết   quả  trung  gian  để  giải  bài  toán  (tổ  chức  dữ  liệu  cho  bài  toán). - Thời  gian  cần  thiết  để  thực  hiện  thuật  toán  (thời  gian  chạy). Hai   yếu   tố   trên   thường  mâu   thuẫn   nhau   và   ảnh   hưởng   qua   lại   lẫn nhau. Thường  khi  chọn  thuật  toán  ta  quan  tâm  đến  thời  gian  thực  hiện.  Mặc  dù  hiện  nay   tốc  độ  máy  tính  ngày  được  cải  thiện  đáng  kể,  có  thể  thực  hiện  hàng  trăm  triệu  phép   tính   trên  giây  nhưng  vẫn  chưa  đáp  ứng  được  cho  một  số   thuật   toán  có   thời  gian   chạy  rất lớn. 1.4. Độ  phức  tạp  của  thuật  toán Việc  đánh  giá  thời  gian  thực  hiện  của  thuật  toán  phụ  thuộc  vào  nhiều  yếu   tố: - Dữ  liệu  vào. - Tốc  độ  của  máy  tính. 10 - Chương  trình  dịch  và  hệ  điều  hành  dùng  cho  chương  trình. Do  đó  việc  đo,