1. Trang Chủ
  2. Kỹ thuật lập trình
  3. Giáo trình Cấu trúc dữ liệu và giải thuật (Nghề: Lập trình máy tính) - CĐ Cơ Giới Ninh Bình

Giáo trình Cấu trúc dữ liệu và giải thuật (Nghề: Lập trình máy tính) - CĐ Cơ Giới Ninh Bình

(NB) Giáo trình Cấu trúc dữ liệu và giải thuật cung cấp cho người học các kiến thức: Giới thiệu về cấu trúc dữ liệu và giải thuật; Kiểu dữ liệu nâng cao; Danh sách; Ngăn xếp và hàng đợi; Sắp xếp và tìm kiếm. Mời các bạn cùng tham khảo. BỘ NÔNG NGHIỆP VÀ PHÁT TRIỂN NÔNG THÔN TRƯỜNG CAO ĐẲNG CƠ GIỚI NINH BÌNH GIÁO TRÌNH MÔN HỌC: MH19_CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NGHỀ: LẬP TRÌNH MÁY TÍNH TRÌNH ĐỘ: Cao đẳng/ trung cấp Ban hành kèm theo Quyết định số: /QĐ­…TCGNB ngày…….tháng….năm .... của Hiệu trưở

Thể loại Tài liệu miễn phí Kỹ thuật lập trình

Số trang 152

Ngày tạo 10/1/2021 10:45:59 PM +00:00

Loại tệp DOC

Kích thước 0.89 M

Tên tệp

Tải Giáo trình Cấu trúc dữ liệu và giải thuật (Nghề: L... (.pdf)

Xem mẫu

  1. BỘ NÔNG NGHIỆP VÀ PHÁT TRIỂN NÔNG THÔN TRƯỜNG CAO ĐẲNG CƠ GIỚI NINH BÌNH GIÁO TRÌNH MÔN HỌC: MH19_CẤU TRÚC DỮ LIỆU  VÀ GIẢI THUẬT NGHỀ: LẬP TRÌNH MÁY TÍNH TRÌNH ĐỘ: Cao đẳng/ trung cấp Ban hành kèm theo Quyết định số:        /QĐ­…TCGNB  ngày…….tháng….năm .... của Hiệu trưởng Trường Cao Đẳng Cơ giới Ninh   Bình 1
  2. Ninh Bình, năm 2018 2
  3. TUYÊN BỐ BẢN QUYỀN ­ Tài liệu này thuộc loại sách giáo trình nên các nguồn thông tin có thể  được  phép dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và tham  khảo. ­ Mọi mục đích khác mang tính lệch lạc hoặc sử  dụng với mục  đích kinh   doanh thiếu lành mạnh sẽ bị nghiêm cấm. 3
  4. Lời giới thiệu Các kiến thức về cấu trúc dữ liệu (CTDL) và giải thuật đóng vai trò quan  trọng trong việc đào tạo nghề Lập trình máy tính. Sách này đựơc hình thành trên  cơ sở các bài giảng về CTDL và giải thuật mà tôi cùng các đồng nghiệp đã đọc  nhiều năm tại khoa Toán­Cơ­Tin học ­ Trường Đại học Khoa học Tự  nhiên –  Đại học Quốc Gia Hà Nội; Khoa Công nghệ thông tin ­ Đại học Bách Khoa Hà  Nội; Khoa Công nghệ  thông tin ­ Đại học Giao thông vận tải. Sách được biên  soạn chủ yếu để làm tài liệu tham khảo cho học sinh, sinh viên nghề Lập trình  máy tính, nhưng nó cũng rất bổ  ích cho các độc giả  khác cần có hiểu biết đầy  đủ hơn về CTDL và giải thuật. Giáo trình này gồm bốn chương Chương 1. Giới thiệu về cấu trúc dữ liệu và giải thuật Chương 2. Kiểu dữ liệu  nâng cao Chương 3. Danh sách Chương 4. Ngăn xếp và hàng đợi Chương 5. Sắp xếp và tìm kiếm Để biên soạn giáo trình này, chúng tôi đã tham khảo các tài liệu: Cấu trúc  dữ liệu và giải thuật, PTS Đinh Mạnh Tường; Lê Minh Hoàng, Cấu trúc dữ liệu   và giải thuật. Giáo trình Cấu trúc dữ  liệu và giải thuật đã được Hổi đồng thẩm định  Trường Cao đẳng nghề Cơ Giới Ninh Bình xét duyệt. Tuy nhiên trong quá trình   biên soạn không tránh khỏi những sai sót, rất mong được sự  đóng góp quý báu  chân thành của bạn đọc. Ninh Bình, ngày    tháng    năm 2018 Tham gia biên soạn: 1. Chủ biên Đoàn Xuân Luận 2. Phạm Thị Thoa 3. Nguyễn Anh Văn 4
  5. Mục lục  Lời giới thiệu                                                                                                                ............................................................................................................      4  Mục lục                                                                                                                         .....................................................................................................................      5  Chương 1                                                                                                                     .................................................................................................................       10  Giới thiệu cấu trúc dữ liệu và giải thuật                                                                  ..............................................................       10  1. Mối liên hệ giữa cấu trúc dữ liệu và giải thuật                                               ...........................................       10  1.1. Xây dựng cấu trúc dữ liệu                                                                          ......................................................................       10  1.2. Xây dựng giải thuật                                                                                     .................................................................................       10  1.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật                                       ...................................       11  2. Kiểu dữ liệu và mô hình dữ liệu                                                                       ...................................................................       11  2.1. Biểu diễn dữ liệu                                                                                        ....................................................................................       11  2.3. Hệ kiểu của ngôn ngữ Pascal                                                                     .................................................................       16  2.4. Mô hình dữ liệu và kiểu dữ liệu trừu tượng                                              ..........................................       18  3. Thiết kế và giải thuật                                                                                         .....................................................................................       22  3.1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu                                                   ...............................................       22  3.2. Đánh giá độ phức tạp của thuật toán                                                          ......................................................       23  Chương 2                                                                                                                     .................................................................................................................       25  Các kiểu dữ liệu nâng cao                                                                                          ......................................................................................       25  1. Mảng                                                                                                                   ..............................................................................................................       25  2. Con trỏ                                                                                                                 .............................................................................................................       27  2.1. Con trỏ và địa chỉ                                                                                       ....................................................................................         28  2.2. Con trỏ và mảng một chiều                                                                        ...................................................................       29  2.2.2. Tên mảng là một hằng địa chỉ                                                                .............................................................         30  2.2.3. Con trỏ trỏ tới các phần tử của mảng một chiều                                   ..............................       30  2.3. Con trỏ và mảng nhiều chiều                                                                     ................................................................       34  2.4. Kiểu con trỏ, kiểu địa chỉ, các phép toán trên con trỏ                              ...........................         36  3. Cấu trúc và hợp                                                                                                   ..............................................................................................       44  3.1. Cấu trúc (struct)                                                                                           .......................................................................................       44  3.2. Kiểu union                                                                                                    ................................................................................................       45 5
  6.  4. File                                                                                                                       ...................................................................................................................       46  4.1. Khái niệm về tệp tin                                                                                   ..............................................................................       46 4.2. Khai báo sử dụng tệp ­  một số hàm thường dùng khi thao tác trên tệp                                                                                                                            48 .........................................................................................................................      Chươ ng 3                                                                                                                        .................................................................................................................       54  Danh sách                                                                                                                    ................................................................................................................       54  1. Các khái niệm                                                                                                     ............................................................................................       54  1.1. Khái niệm về danh sách                                                                              ..........................................................................       54  1.2. Các phép toán trên danh sách                                                                       ...................................................................       54  2. Lưu tữ kế tiếp đối với danh sách tuyến tính                                                     ................................................       56  2.1. Định nghĩa                                                                                                    ................................................................................................       56  2.2. Danh sách liên kết đơn (Singly Linked List)                                               ...........................................       56  3. Lưu trữ móc nối đối với danh sách tuyến tính                                                  ............................................       85  3.1. Cấu trúc dữ liệu                                                                                           .......................................................................................       85  3.2. Các thao tác trên danh sách                                                                          .....................................................................       87  Chương 4                                                                                                                   ...............................................................................................................       111  Ngăn xếp và hàng đợi                                                                                               ...........................................................................................       111  1. Định nghĩa ngăn xếp (stack)                                                                             ........................................................................       111  2. Lưu trữ stack bằng mảng                                                                                 ............................................................................       113  2.1. Khởi tạo ngăn xếp                                                                                     .................................................................................       113  2.2. Thêm (Đẩy) một phần tử vào ngăn xếp (Push)                                        ....................................       114  2.3. Lấy nội dung một phần tử trong ngăn xếp ra để xử lý (Pop)                 .............       115  2.4. Hủy ngăn xếp                                                                                             .........................................................................................       116  3.Ví dụ về ứng dụng stack                                                                                   ...............................................................................       116  4. Định nghĩa hàng đợi(Queue)                                                                             ....................................................................       120  5. Lưu trữ queue bằng mảng                                                                                ......................................................................       122  5.1. Khởi tạo hàng đợi (Initialize)                                                                    ................................................................       122  5.2. Thêm (Đưa) một phần tử vào hàng đợi (Add)                                          ......................................       123  5.3. Lấy nội dung một phần tử trong hàng đợi ra để xử lý (Get)                   ...............       124 6
  7.  5.4. Hủy hàng đợi                                                                                             .........................................................................................       126  6. Stack và queue móc nối                                                                                     .................................................................................       126  6.1. Stack móc nối                                                                                             .........................................................................................       126  6.2. Queue móc nối                                                                                           .......................................................................................       129  Chương 5                                                                                                                   ...............................................................................................................       132  Sắp xếp và tìm kiếm                                                                                                ............................................................................................       132  1. Giới thiệu về sắp xếp và tìm kiếm                                                                 .............................................................       133  1.1. Giới thiệu về sắp xếp                                                                               ...........................................................................       133  1.2. Giới thiệu về tìm kiếm                                                                             .........................................................................       134  2. Các phương pháp sắp xếp                                                                                ............................................................................       134  2.1. Sắp xếp kiểu chọn (Selection sort)                                                           .......................................................       134  2.2. Thuật toán sắp xếp nổi bọt (bubble sort)                                                 .............................................       136  2.3. Thuật toán sắp xếp kiểu chèn (insertion sort)                                          ......................................       137  2.4. Thuật toán sắp xếp kiểu phân đoạn (quick sort)                                      ..................................       139  2.5. Thuật toán sắp xếp trộn                                                                            .......................................................................       144  3. Các phương pháp tìm kiếm                                                                              ..........................................................................       149  3.1. Tìm kiếm tuần tự (Sequential search)                                                       ...................................................       149  3.2. Tìm kiếm nhị phân (Binary search)                                                           .......................................................       149  TÀI LIỆU THAM KHẢO                                                                                         .....................................................................................       152 7
  8. MÔN HỌC CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Tên Môn học: Cấu trúc dữ liệu và giải thuật Mã môn học: MH19 Vị trí, tính chất, ý nghĩa và vai trò của môn học:  ­ Vị  trí môn học: Môn học này được học sau môn học Tin học căn bản, Lập   trình căn bản. ­ Tính chất môn học: Môn học này yêu cầu phải có tư  duy logic và các kiến  thức về lập trình căn bản, lập trình hướng đối tượng. ­ Ý nghĩa, vai trò của môn học: Đây là môn học cơ sở ngành của các ngành liên  quan đến công nghệ  thông tin, cung cấp cho sinh viên các kiến thức cơ  bản   về lập trình. Mục tiêu của môn học:  ­ Kiến thức:  + Trình bày được mối liên hệ giữa cấu trúc dữ liệu và giải thuật; cách khai  báo và sử dụng các kiểu dữ liệu nâng cao; + Trình bày được các kỹ thuật ngăn xếp và hàng đợi, các thuật toán sắp xếp   và tìm kiếm, các loại danh sách liên kết. ­ Kỹ năng:  + Phân tích được các loại dữ  liệu, giải thuật và kết hợp được dữ  liệu và   giải thuật; + Cài đặt được các thuật toán sắp xếp và tìm kiếm;  + Cài đặt được các thuật toán trên các cấu trúc dữ  liệu: mảng, danh sách,   danh sách liên kết. ­ Thái độ: + Rèn luyện tính cẩn thận, tỉ  mỉ, chính xác, sáng tạo, làm việc độc lập và  theo nhóm; + Rèn luyện kỹ năng lập trình; + Đảm bảo an toàn cho người và trang thiết bị.  8
  9. Nội dung của môn học: Thời gian Số  Tên chương mục Tổng  Lý  Thực  Kiểm  TT số thuyết hành  tra I Chương 1: Giới thiệu cấu trúc dữ  liệu  5 5 0 0 và giải thuật 1. Mỗi liên hệ  giữa cấu trúc dữ  liệu và  1 1 giải thuật 2. Kiểu dữ liệu và mô hình dữ liệu 2 2 3. Thiết kế và giải thuật 2 2 II Chương 2: Kiểu dữ liệu nâng cao 20 5 14 1 1. Kiểu mảng 5 1 4 2. Con trỏ 5 1 4 3. Cấu trúc và hợp 5 2 3 4. File 5 1 3 1 III Chương 3: Danh sách  20 6 13 1 1. Các khái niệm 5 2 3 2. Lưu trữ kế tiếp đối với danh sách tuyến  7 2 5 tính 3.   Lưu   trữ   móc   nối   đối   với   danh   sách  8 2 5 1 tuyến tính IV Chương 4: Ngăn xếp và hàng đợi 20 8 11 1 1. Định nghĩa ngăn xếp (stack) 1 1 2. Lưu trữ stack bằng mảng 3 1 2 3.Ví dụ về ứng dụng stack 4 1 3 4. Định nghĩa hàng đợi(Queue) 2 1 1 5. Lưu trữ queue bằng mảng  5 2 3 6. Stack và queue móc nối 5 2 2 1 IV Chương 5: Sắp xếp và tìm kiếm 25 6 18 1 1. Giới thiệu về sắp xếp và tìm kiếm 3 2 1 2. Các phương pháp sắp xếp  10 2 8 3. Các phương  pháp tìm kiếm  12 2 9 1 Cộng 90 30 56 4 9
  10. Chương 1 Giới thiệu cấu trúc dữ liệu và giải thuật Mã chương: MH19_CH01 Giới thiệu: Bài này giới thiệu về mối liên hệ giữa cấu trúc dữ liệu và giải thuật. Mục tiêu:  ­ Trình bày được kiến thức cở  bản về  cấu trúc dữ  liệu, giải thuật, kiểu dữ  liệu, mô hình dữ liệu; ­ Phân tích được giải thuật;  ­ Sử dụng được các phương pháp phân tích, thiết kế giải thuật; ­ Rèn luyện tính cẩn thận, tỉ mỉ, chính xác, sáng tạo, thực hiện các thao tác an   toàn với máy tính. Nội dung: 1. Mối liên hệ giữa cấu trúc dữ liệu và giải thuật 1.1. Xây dựng cấu trúc dữ liệu ­ Có thể  nói rằng không có một chương trình máy tính nào mà không có dữ  liệu để  xử  lý. Dữ  liệu có thể  là dữ  liệu đưa vào (input data), dữ  liệu trung  gian hoặc dữ  liệu đưa ra (output data). Do vậy, việc tổ  chức để  lưu trữ  dữ  liệu phục vụ  cho chương trình có ý nghĩa rất quan trọng trong toàn bộ  hệ  thống chương trình. Việc xây dựng cấu trúc dữ  liệu quyết định rất lớn đến  chất lượng cũng như  công sức của người lập trình trong việc thiết kế, cài   đặt chương trình. 1.2. Xây dựng giải thuật ­ Khái niệm giải thuật hay thuật giải mà nhiều khi còn được gọi là thuật toán   dùng để chỉ phương pháp hay cách thức (method) để giải quyết vần đề. Giải   thuật có thể được minh họa bằng ngôn ngữ tự nhiên (natural language), bằng  sơ đồ (flow chart) hoặc bằng mã giả (pseudo code). Trong thực tế, giải thuật   thường được minh họa hay thể  hiện bằng mã giả  tựa trên một hay một số  10
  11. ngôn ngữ  lập trình nào đó (thường là ngôn ngữ  mà người lập trình chọn để  cài đặt thuật toán), chẳng hạn như C, Pascal, … ­ Khi đã xác định được cấu trúc dữ liệu thích hợp, người lập trình sẽ bắt đầu   tiến hành xây dựng thuật giải tương  ứng theo yêu cầu của bài toán đặt ra   trên cơ sở của cấu trúc dữ liệu đã được chọn. Để giải quyết một vấn đề có  thể có nhiều phương pháp, do vậy sự lựa chọn phương pháp phù hợp là một  việc mà người lập trình phải cân nhắc và tính toán. Sự lựa chọn này cũng có  thể  góp phần đáng kể  trong việc giảm bớt công việc của người lập trình  trong phần cài đặt thuật toán trên một ngôn ngữ cụ thể. 1.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật ­ Mối quan hệ giữa cấu trúc dữ liệu và Giải thuật có thể minh họa bằng đẳng  thức: Cấu trúc dữ liệu + Giải thuật = Chương trình ­ Như  vậy, khi đã có cấu trúc dữ  liệu tốt, nắm vững giải thuật thực hiện thì  việc thể  hiện chương trình bằng một ngôn ngữ  cụ  thể  chỉ  là vấn đề  thời   gian. Khi có cấu trúc dữ  liệu mà chưa tìm ra thuật giải thì không thể  có   chương trình và ngược lại không thể có Thuật giải khi chưa có cấu trúc dữ  liệu. Một chương trình máy tính chỉ có thể được hoàn thiện khi có đầy đủ cả  Cấu trúc dữ liệu để lưu trữ dữ liệu và Giải thuật xử lý dữ liệu theo yêu cầu   của bài toán đặt ra. 2. Kiểu dữ liệu và mô hình dữ liệu 2.1. Biểu diễn dữ liệu ­ Trong máy tính điện tử  (MTĐT), các dữ  liệu dù có bản chất khác nhau như  thế  nào (số  nguyên, số  thực, hay xâu ký tự, ...), đều được biểu diễn dưới   dạng nhị  phân. Mỗi dữ  liệu được biểu diễn dưới dạng một dãy các số  nhị  phân 0 hoặc 1. Về mặt kỹ thuật đây là cách biểu diễn thích hợp nhất, vì các  giá trị  0 và 1 dễ  dàng được mã hoá bởi các phần tử  vật lý chỉ  có hai trạng   thái. Chúng ta sẽ  không quan tâm đến cách biểu diễn này của dữ  liệu, cũng   11
  12. như các cách tiến hành các thao tác, các phép toán trên các dữ liệu được biểu   diễn dưới dạng nhị phân. ­ Cách biểu diễn nhị phân của dữ liệu rất không thuận tiện đối với con người.  Việc   xuất   hiện   các   ngôn   ngữ   lập   trình   bậc   cao   (FORTRAN,   BASIC,   PASSCAL, C ...) đã giải phóng con người khỏi những khó khăn khi làm việc   với cách biểu diễn trong máy của dữ liệu. Trong các ngôn ngữ lập trình bậc   cao, các dữ  liệu, hiểu theo một nghĩa nào đó, là sự  trìu tượng hoá các tính   chất của các đối tượng trong thế giới hiện thực. Nói dữ liệu là sự trìu tượng  hoá từ thế giới hiện thực, vì ta đã bỏ qua những nhân tố, tính chất mà ta cho  là không cơ  bản, chỉ  giữ  lại những tính chất đặc trưng cho các đối tượng  thuộc phạm vi bài toán đang xét. Chẳng hạn, vị  trí của một đối tượng trong   thực tiễn, được đặc trưng bởi cặp số  thực (x,y) (đó là toạ  đoạ  đê­các của  một điểm trong mặt phẳng). Do đó, trong ngôn ngữ  Pascal, vị  trí một đối  tượng được biểu diễn bởi bản ghi gồm hai trường tương  ứng với hoành độ  và tung độ  của một điểm. Trong toán học có các khái niệm biểu diễn đặc  trưng về mặt số lượng và các quan hệ của các đối tượng trong thế giới hiện   thực, đó là các khái niệm số nguyên, số  thực, số  phức, dãy, ma trận, ... Trên  cơ  sở  các khái niệm toán học này, người ta đã đưa vào trong các ngôn ngữ  lập trình bậc cao các dữ liệu kiểu nguyên, thực, phức, mảng, bản ghi, ... Tuy   nhiên do tính đa dạng của các bài toán cần xử  lý bằng MTĐT, chỉ  sử  dụng   các kiểu dữ liệu có sẵn trong các ngôn ngữ  lập trình bậc cao là chưa đủ  để  mô tả các bài toán. Chúng ta phải cần đến các cấu trúc dữ liệu. Đó là các dữ  liệu phức tạp, được xây dựng nên từ  các dữ  liệu đã có, đơn giản hơn bằng   các phương pháp liên kết nào đó. ­ Để  giải quyết một bài toán bằng MTĐT, ta cần xây dựng  mô hình dữ  liệu   mô tả bài toán. Đó là sự trìu tượng hoá các đặc trưng của các đối tượng thuộc  phạm vi vấn đề  mà ta quan tâm, các mối quan hệ  giữa các đối tượng đó.  Dùng làm các mô hình dữ liệu trong tin học, chúng ta sẽ sử dụng các mô hình   toán học như danh sách, cây, tập hợp, ánh xạ, quan hệ, đồ thị, ... Mô hình dữ  12
  13. liệu sẽ được biểu diễn bởi các cấu trúc dữ liệu. Thông thường một mô hình  dữ  liệu có thể  được biểu hiện bởi nhiều cấu trúc dữ  liệu khác nhau. Tuỳ  từng ứng dụng, ta sẽ chọn cấu trúc dữ liệu nào mà các thao tác cần thực hiện  là hiệu quả nhất có thể được. 2.2. Kiểu dữ liệu và cấu trúc dữ liệu ­ Trong các ngôn ngữ  lập trình bậc cao, các dữ  liệu được phân lớp thành các  lớp dữ liệu dựa vào bản chất của dữ liệu. Mỗi một lớp dữ liệu được gọi là   một kiểu dữ liệu. Như vậy, một kiểu T là một tập hợp nào đó, các phần tử  của tập được gọi là các giá trị  của kiểu. Chẳng hạn, kiểu integer là tập hợp  các số nguyên, kiểu char là một tập hữu hạn các ký hiệu. Các ngôn ngữ lập  trình khác nhau có thể có các kiểu dữ liệu khác nhau. Fortran có các kiểu dữ  liệu là  integer,  real,  logical,  complex  và  double complex. Các kiểu dữ  liệu  trong ngôn ngữ C là int, float, char, con trỏ, struct ..., Kiểu dữ liệu trong ngôn  ngữ  Lisp lại là các S­biểu thức. Một cách tổng quát, mỗi ngôn ngữ  lập trình  có một hệ kiểu của riêng mình. Hệ kiểu của một ngôn ngữ bao gồm các kiểu  dữ  liệu cơ sở và các phương pháp cho phép ta từ  các kiểu dữ liệu đã có xây   dựng nên các kiểu dữ liệu mới. ­ Khi nói đến một kiểu dữ  liệu, chúng ta cần phải đề  cập đến hai đặc trưng  sau đây: 1. Tập hợp các giá trị  thuộc kiểu. Chẳng hạn, kiểu integer trong ngôn ngữ  Pascal gồm tất cả các số nguyên được biểu diễn bởi hai byte, tức là gồm các  số nguyên từ ­32768 đến + 32767. Trong các ngôn ngữ lập trình bậc cao mỗi  hằng, biến, biểu thức hoặc hàm cần phải được gắn với một kiểu dữ  liệu  xác định. Khi đó, mỗi biến (biểu thức, hàm) chỉ có thể nhận các giá trị thuộc  kiểu của biến (biểu thức, hàm) đó.  Ví dụ , nếu X là biến có kiểu boolean trong Pascal (var X : boolean) thì X chỉ  có thể nhận một trong hai giá trị true, false.    2. Với mỗi kiểu dữ liệu, cần phải xác định một tập hợp nào đó các phép toán  có thể  thực hiện được trên các dữ  liệu của kiểu. Chẳng hạn, với kiểu real,   13
  14. các phép toán có thể thực hiện được là các phép toán số học thông thường +,   ­, *, / , và các phép toán so sánh = , ,  =. ­ Thông thường trong một hệ  kiểu của một ngôn ngữ  lập trình sẽ  có một số  kiểu dữ liệu được gọi là kiểu dữ liệu đơn hay kiểu dữ liệu phân tử (atomic). ­ Chẳng hạn, trong ngôn ngữ  Pascal, các kiểu dữ  liệu integer, real, boolean ,  char và các kiểu liệt kê được gọi là các kiểu dữ liệu đơn. Sở dĩ gọi là đơn, vì   các giá trị  của các kiểu này được xem là các đơn thể  đơn giản nhất không   thể phân tích thành các thành phần đơn giản hơn được nữa. ­ Như đã nói, khi giải quyết các bài toán phức tạp, chỉ sử dụng các dữ liệu đơn   là không đủ, ta phải cần đến các cấu trúc dữ liệu. Một cấu trúc dữ liệu bao  gồm một tập hợp nào đó các dữ liệu thành phần, các dữ liệu thành phần này  được liên kết với nhau bởi một phương pháp nào đó. Các dữ liệu thành phần  có thể là dữ liệu đơn, hoặc cũng có thể là một cấu trúc dữ liệu đã được xây   dựng. Có thể  hình dung một cấu trúc dữ  liệu được tạo nên từ  các  tế  bào   (khối xây dựng), mỗi tế bào có thể xem như một cái hộp chứa dữ liệu thành   phần. ­ Trong Pascal và trong nhiều ngôn ngữ thông dụng khác có một cách đơn giản  nhất để  liên kết các tế bào, đó là sắp xếp các tế  bào chứa các dữ  liệu cùng   một kiểu thành một dãy. Khi đó ta có một cấu trúc dữ liệu được gọi là  mảng  (array). Như vậy, có thể nói, một mảng là một cấu trúc dữ liệu gồm một dãy   xác định các dữ liệu thành phần cùng một kiểu. Ta vẫn thường nói đến mảng  các số  nguyên, mảng các số  thực, mảng các bản ghi, ... Mỗi một dữ  liệu   thành phần của mảng được gắn với một chỉ số từ một tập chỉ số nào đó. Ta  có thể  truy cập đến một thành phần nào đó của mảng bằng cách chỉ  ra tên  mảng và chỉ số của thành phần đó. ­ Một phương pháp khác để tạo nên các cấu trúc dữ liệu mới, là kết hợp một   số  tế  bào (có thể  chứa các dữ  liệu có kiểu khác nhau) thành một  bản ghi  (record). Các tế bào thành phần của bản ghi được gọi là các trường của bản  ghi. Các bản ghi đến lượt lại được sử  dụng làm các tế  bào để  tạo nên các  14
  15. cấu trúc dữ liệu khác. Chẳng hạn, một trong các cấu trúc dữ  liệu hay được  sử dụng nhất là mảng các bản ghi. ­ Còn một phương pháp quan trọng nữa để kiến tạo các cấu trúc dữ liệu, đó là  sử dụng con trỏ. Trong phương pháp này, mỗi tế bào là một bản ghi gồm hai  phần INFOR và LINK, phần INFOR có thể có một hay nhiều trường dữ liệu,   còn phần LINK có thể chứa một hay nhiều con trỏ trỏ đến các tế bào khác có  quan hệ  với tế bào đó. Chẳng hạn, ta có thể  cài đặt một danh sách bởi cấu   trúc dữ  liệu danh sách liên kết, trong đó mỗi thành phần của danh sách liên  kết là bản ghi gồm hai trường type Cell = record element : Item ; next : ^Cell ; end ; ­ Ở đây, trường element có kiểu dữ liệu Item, một kiểu dữ liệu nào đó của các  phần tử của danh sách. Trường next là con trỏ trỏ tới phần tử tiếp theo trong  danh sách. Cấu trúc dữ liệu danh sách liên kết biểu diễn danh sách (a1, a2,....,  an) có thể được biểu diễn như trong hình          a1    a2    an        .  Hình 1.1: Cấu trúc dữ liệu danh sách liên kết. ­ Sử  dụng con trỏ  để  liên kết các tế  bào là một trong các phương pháp kiến  tạo các cấu trúc dữ liệu được áp dụng nhiều nhất. Ngoài danh sách liên kết,  người ta còn dùng các con trỏ  để  tạo ra các cấu trúc dữ  liệu biểu diễn cây,   một mô hình dữ liệu quan trọng bậc nhất. ­ Trên đây chúng ta đã nêu ba phương pháp chính để kiến tạo các cấu trúc dữ  liệu. (Ở đây chúng ta chỉ nói đến các cấu trúc dữ liệu trong bộ nhớ trong, các   15
  16. cấu trúc dữ  liệu  ở  bộ  nhớ  ngoài như  file chỉ  số, B­cây sẽ  được   đề  cập   riêng.) ­ Một kiểu dữ liệu mà các giá trị thuộc kiểu không phải là các dữ liệu đơn mà  là các cấu trúc dữ liệu được gọi là kiểu dữ liệu có cấu trúc. Trong ngôn ngữ  Pascal, các kiểu dữ liệu mảng, bản ghi, tập hợp, file đều là các kiểu dữ liệu  có cấu trúc. 2.3. Hệ kiểu của ngôn ngữ Pascal ­ Pascal là một trong các ngôn ngữ  có hệ  kiểu phong phú nhất. Hệ  kiểu của   Pascal chứa các kiểu cơ  sở, integer, real, boolean, char và các quy tắc, dựa   vào đó ta có thể  xây dựng nên các kiểu phức tạp hơn từ  các kiểu đã có. Từ  các kiểu cơ sở và áp dụng các quy tắc, ta có thể  xây dựng nên một tập hợp  vô hạn các kiểu. Hệ  kiểu của Pascal có thể  được định nghĩa định quy như  sau : Các kiểu cơ sở 1. Kiểu integer 2. Kiểu real 3. Kiểu boolean 4. Kiểu char 5. Kiểu liệt kê Giả sử obj1, obj2,.... objn là các đối tượng nào đó. khi đó ta có thể tạo nên  kiểu liệt kê T bằng cách liệt kê ra tất cả các đói tượng đó.  type T = (obj1, obj2,...objn) ­ Chú ý. Tất cả các kiểu đơn đều là các kiểu có thứ tự, tức là với hai giá trị bất  kỳ a và b thuộc cùng một kiểu, ta luôn có a   b hoặc a     b. trừ kiểu real,  các kiểu còn lại đều là kiểu có thứ tự đếm được. 6. Kiểu đoạn con 16
  17.     type T = min . max ­ Trong đó min và max là cận dưới và cận trên của khoảng ; min và max là các   giá trị  thuộc cùng một kiểu integer, char, hoặc các kiểu liệt kê, đồng thời   min  max. Kiểu T gồm tất cả các giá trị từ min đến max. ­ Các phép toán trong hệ kiểu Pascal ­ Như  đã nói với mỗi kiểu dữ  liệu ta chỉ  có thể  thực hiện một số  phép toán   nhất định trên các dữ liệu của kiểu. Ta không thể áp dụng một phép toán trên  các dữ liệu thuộc kiểu này cho các dữ liệu có kiểu khác. Ta có thể phân tập  hợp các phép toán trên các kiểu dữ liệu của Pascal thành hai lớp sau : A. Các phép toán truy cập đến các thành phần của một đối tượng dữ  liệu,   chẳng hạn truy cập đến các thành phần của một mảng, đến các trường của  một bản ghi. + Giả  sử  A là một mảng với tập chỉ  số  I, khi đó A[i] cho phép ta truy cập  đến thành phần thứ  i của mảng. Còn nếu X là một bản ghi thì việc truy   cập đến trường F của nó được thực hiện bởi phép toán X.F. B. Các phép toán kết hợp dữ liệu. + Pascal có một tập hợp phong phú các phép toán kết hợp một hoặc nhiều  dữ  liệu đã cho thành một dữ  liệu mới. Sau đây là một số  nhóm các phép   toán chính. 1. Các phép toán số học. Đó là các phép toán + , ­, * , / trên các số  thực ; các   phép toán +, ­ *, /, div, mod trên các số nguyên. 2. Các phép toán so sánh. Trên các đối tượng thuộc các kiểu có thứ tự (đó là  các kiểu cơ sở và kiểu tập), ta có thể thực hiện các phép toán so sánh =, ,   =. Cần lưu ý rằng, kết quả  của các phép toán này là một giá trị  kiểu boolaen (tức là true hoặc false). 3. Các phép toán logic. Đó là các phép toán and, or, not được thực hiện trên  hai giá trị false và truc của kiểu boolean. 17
  18. 4. Các phép toán tập hợp. Các phép toán hợp, giao, hiệu của các tập hợp trong  pascal được biểu diễn bởi +, *, ­ tương  ứng. Việc kiểm tra một đối tượng x   có là phần tử của tập A hay không được thực hiện bởi phép toán x in A. Kết  quả của phép toán này là một giá boolean.  2.4. Mô hình dữ liệu và kiểu dữ liệu trừu tượng ­ Để  giải quyết một vấn đề  trên MTĐT thông thường chúng ta cần phải qua  một số giai đoạn chính sau đây : 1. Đặt bài toán 2. Xây dựng mô hình 3. Thiết kế thuật toán và phân tích thuật toán 4. Viết chương trình 5. Thử nghiệm. ­ Chúng ta sẽ  không đi sâu phân tích từng giai đoạn. Chúng ta chỉ  muốn làm  sáng tỏ  vai trò của mô hình dữ  liệu trong việc thiết kế  chương trình. Xét ví  dụ sau. ­ Ví dụ. Một người giao hàng, hàng ngày anh ta phải chuyển hàng từ một thành   phố đến một số thành phố khác rồi lại quay về thành phố xuất phát. Vấn đề  của anh ta là làm thế nào có được một hành trình chỉ qua mỗi thành phố một  lần với đường đi ngắn nhất có thể được. ­ Chúng ta thử  giúp người giao hàng mô tả  chính xác bài toán. Trước hết, ta   cần trả lời câu hỏi, những thông tin đã biết trong bài toán người giao hàng là   gì ? Đó là tên của các thành phố anh ta phải ghé qua và độ dài các con đường  có thể  có giữa hai thành phố. Chúng ta cần tìm cái gì ? Một hành trình mà  người giao hàng mong muốn là một danh sách các thành phố  A1,A2...An+1   (giả  sử  có n thành phố), trong đó các A1 (i=1,2,...,n+1) đều khác nhau, trừ  An+1 = A1.   ­ Với một vấn đề  đặt ra từ  thực tiễn, ta có thể  mô tả  chính xác vấn đề  đó  hoặc các bộ  phận của nó (vấn đề  con) bởi một mô hình toán học nào đó.  Chẳng hạn, mô hình toán học thích hợp nhất để  mô tả  bài toán người giao   18
  19. hàng là đồ thị. Các đỉnh của đồ thị là các thành phố, các cạnh của đồ thị là các  đường nối hai thành phố. Trọng số của các cạnh là độ dài các đường nối hai   thành phố. Trong thuật ngữ  của lý thuyết đồ  thị, danh sách các thành phố  biểu diễn hành trình của người giao hàng, là một chu trình qua tất cả các đỉnh  của đồ  thị. Như vậy, bài toán người giao hàng được qui về  bài toán trong lý  thuyết đồ  thị. Tìm một chu trình xuất phát từ  một đỉnh qua tất cả  các đỉnh   còn lại với độ dài ngắn nhất. ­ Bài toán người giao hàng là một trong các bài toán đã trở thành kinh điển. Nó  dễ mô hình hoá, song cũng rất khó giải. Chúng ta sẽ quay lại bài toán này. ­ Cần lưu ý rằng, để  tìm ra cấu trúc toán học thích hợp với một bài toán đã  cho, chúng ta phải phân tích kỹ bài toán để tìm ra câu trả lời cho các câu hỏi  sau. + Các thông tin quan trọng của bài toán có thể biểu diễn bởi các đối tượng   toán học nào ? + Có các mối quan hệ nào giữa các đối tượng ? + Các kết quả phải tìm của bài toán có thể biểu diễn bởi các khái niệm toán   học nào. ­ Sau khi đã có mô hình toán học mô tả bài toán, một câu hỏi đặt ra là, ta phải  làm việc với mô hình như  thế nào để  tìm ra lời giải của bài toán ? Chúng ta  sẽ thiết kế thuật toán thông qua các hành động, các phép toán thực hiện trên  các đối tượng của mô hình. ­ Một mô hình toán học cùng với các phép toán có thể  thực hiện trên các đối  tượng của mô hình được gọi là mô hình dữ  liệu. Chẳng hạn, trong mô hình  dữ liệu đồ thị, trong số rất nhiều các phép toán, ta có thể kể ra một số phép   toán sau : tìm các đỉnh kề của mỗi đỉnh, xác định đường đi ngắn nhất nối hai   đỉnh bất kỳ, tìm các thành phần liên thông, tìm các đỉnh treo,.. Về  mặt toán   học, danh sách là một dãy hữu hạn n phần tử (a1, a2, ..., an). Trong mô hình dữ  liệu danh sách, chúng ta cũng có thể thực hiện một tập hợp rất đa dạng các   phép toán, chẳng hạn như, xác định độ  dài của danh sách, xen một phần tử  19
  20. mới vào danh sách, loại một phần từ nào đó khỏi danh sách, sắp xếp lại danh   sách theo một trật tự nào đó, gộp hai danh sách thành một danh sách. ­ Trở  lại  bài toán người  giao hàng. Có  nhiều thuật toán giải bài toán này.  Chẳng hạn, ta có thể giải bằng phương pháp vét cạn : giả sử có n thành phố,   khi đó mỗi hành trình là một hoán vị  của n­1 thành phố  (trừ  thành phố  xuất  phát), thành lập (n­1)! hoán vị, tính độ dài của hành trình ứng với mỗi hoán vị  và so sánh, ta sẽ tìm được hành trình ngắn nhất. Ta cũng có thể giải bài toán  bằng phương pháp qui hoạch động (Phương pháp này sẽ  được trình bày  ở  tập 2 của sách này). Sau đây ta đưa ra một thuật toán đơn giản. Thuật toán  này tìm ra rất nhanh nghiệm "gần đúng", trong trường hợp có đường đi nối   hai thành phố bất kỳ. Giả sử G là một đồ  thị  (Graph), V là tập hợp các đỉnh  (Node), E là tập hợp các cạnh của nó. Giả sử c(u,v) là độ dài (nguyên dương)   của cạnh (u,v). Hành trình (Tour) của người giao hàng có thể  xem như  một  tập hợp nào đó các cạnh. Cost là độ dài của hành trình. Thuật toán được biểu   diễn bởi thủ tục Salesperson. procedure Salespersen (G : Graph ; var Tour : set of E ;  var cost : integer) ; var v, w : Node      U : set of V ; begin Tour : = [ ] ; Cost  : = 0 ;     v   : = vo ; {vo ­ đỉnh xuất phát}                 U : = V ­ [vo] ; while      U  [   ] do begin  Chọn (v, w) là cạnh ngắn nhất với w thuộc U ; 20
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường