›
›

Giáo trình Cấu trúc dữ liệu và giải thuật - Trình độ: Cao đẳng, Trung cấp - Trường Cao đẳng cơ giới Ninh Bình

doc 137 trang Gia Huy 16/05/2022 2830
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu và giải thuật - Trình độ: Cao đẳng, Trung cấp - Trường Cao đẳng cơ giới Ninh Bình", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • docgiao_trinh_cau_truc_du_lieu_va_giai_thuat_trinh_do_cao_dang.doc

Nội dung text: Giáo trình Cấu trúc dữ liệu và giải thuật - Trình độ: Cao đẳng, Trung cấp - Trường Cao đẳng cơ giới Ninh Bình

  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 Ninh Bình, năm 2018 1
  2. 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. 2
  3. 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 3
  4. Mục lục Lời giới thiệu 3 Mục lục 4 Chương 1. Giới thiệu cấu trúc dữ liệu và giải thuật 8 1. Mối liên hệ giữa cấu trúc dữ liệu và giải thuật 9 1.1. Xây dựng cấu trúc dữ liệu 9 1.2. Xây dựng giải thuật 9 1.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật 10 2. Kiểu dữ liệu và mô hình dữ liệu 10 2.1. Biểu diễn dữ liệu 10 2.3. Hệ kiểu của ngôn ngữ Pascal 14 2.4. Mô hình dữ liệu và kiểu dữ liệu trừu tượng 16 3. Thiết kế và giải thuật 20 3.1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu 20 3.2. Đánh giá độ phức tạp của thuật toán 21 Chương 2. Các kiểu dữ liệu nâng cao 22 1. Mảng 22 2. Con trỏ 24 2.1. Con trỏ và địa chỉ 24 2.2. Con trỏ và mảng một chiều 26 2.3. Con trỏ và mảng nhiều chiều 30 2.4. Kiểu con trỏ, kiểu địa chỉ, các phép toán trên con trỏ 32 3. Cấu trúc và hợp 39 3.1. Cấu trúc (struct) 39 3.2. Kiểu union 40 4. File 41 4.1. Khái niệm về tệp tin 41 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 43 Chương 3. Danh sách 49 1. Các khái niệm 49 1.1. Khái niệm về danh sách 49 4
  5. 1.2. Các phép toán trên danh sách 49 2. Lưu tữ kế tiếp đối với danh sách tuyến tính 51 2.1. Định nghĩa 51 2.2. Danh sách liên kết đơn (Singly Linked List) 51 3. Lưu trữ móc nối đối với danh sách tuyến tính 76 3.1. Cấu trúc dữ liệu 76 3.2. Các thao tác trên danh sách 78 Chương 4. Ngăn xếp và hàng đợi 100 1. Định nghĩa ngăn xếp (stack) 100 2. Lưu trữ stack bằng mảng 102 2.1. Khởi tạo ngăn xếp 102 2.2. Thêm (Đẩy) một phần tử vào ngăn xếp (Push) 102 2.3. Lấy nội dung một phần tử trong ngăn xếp ra để xử lý (Pop) 103 2.4. Hủy ngăn xếp 104 3.Ví dụ về ứng dụng stack 104 4. Định nghĩa hàng đợi(Queue) 108 5. Lưu trữ queue bằng mảng 110 5.1. Khởi tạo hàng đợi (Initialize) 110 5.2. Thêm (Đưa) một phần tử vào hàng đợi (Add) 111 5.3. Lấy nội dung một phần tử trong hàng đợi ra để xử lý (Get) 112 5.4. Hủy hàng đợi 113 6. Stack và queue móc nối 113 6.1. Stack móc nối 113 6.2. Queue móc nối 116 Chương 5. Sắp xếp và tìm kiếm 119 1. Giới thiệu về sắp xếp và tìm kiếm 119 1.1. Giới thiệu về sắp xếp 119 1.2. Giới thiệu về tìm kiếm 120 2. Các phương pháp sắp xếp 121 2.1. Sắp xếp kiểu chọn (Selection sort) 121 2.2. Thuật toán sắp xếp nổi bọt (bubble sort) 122 5
  6. 2.3. Thuật toán sắp xếp kiểu chèn (insertion sort) 122 2.4. Thuật toán sắp xếp kiểu phân đoạn (quick sort) 125 2.5. Thuật toán sắp xếp trộn 129 3. Các phương pháp tìm kiếm 134 3.1. Tìm kiếm tuần tự (Sequential search) 134 3.2. Tìm kiếm nhị phân (Binary search) 134 TÀI LIỆU THAM KHẢO 136 6
  7. 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ị. Nội dung của môn học: 7
  8. 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 và 5 5 0 0 giải thuật 1. Mỗi liên hệ giữa cấu trúc dữ liệu và giải 1 1 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 tuyến 8 2 5 1 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 8
  9. 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ố 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, 9
  10. - 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 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, 10
  11. 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ữ 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, 11
  12. 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, 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à 12
  13. 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 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 ; 13
  14. -Ở đâ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 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 14
  15. 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 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. 15
  16. + 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. 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. 16
  17. - 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 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 17
  18. : 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ử (a 1, 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ử 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 18
  19. begin Chọn (v, w) là cạnh ngắn nhất với w thuộc U ; Tour : = Tour + [(v, w)] ; Cost : = Cost + c (v,w) ; v : = w ; U : = U - [w] ; end ; Tour : = Tour + [(v,vo)] ; Cost : = Cost + c(v,vo) ; end; - Thuật toán Salesperson được xây dựng trên cơ sở mô hình dữ liệu đồ thị và mô hình dữ liệu tập hợp. Nó chứa các thao tác trên đồ thị, các phép toán tập hợp. Tư tưởng của thuật toán như sau. Xuất phát từ Tour là tập rỗng. Giả sử ta xây dựng được đường đi từ đỉnh xuất phát v 0 tới đỉnh v. Bước tiếp theo, ta sẽ thêm vào Tour cạnh (v,w), đó là cạnh ngắn nhất từ v tới các đỉnh w không nằm trên đường đi từ v 0 tới v. Để có được chương trình, chúng ta phải biểu diễn đồ thị, tập hợp bởi các cấu trúc dữ liệu. Sau đó viết các thủ tục (hoặc hàm) thực hiện các thao tác, các phép toán trên đồ thị, tập hợp có trong thuật toán. - Tóm lại, quá trình giải một bài toán có thể quy về hai giai đoạn kế tiếp như sau: + Xây dựng các mô hình dữ liệu mô tả bài toán. Thiết kế thuật toán bằng cách sử dụng các thao tác, các phép toán trên các mô hình dữ liệu. + Biểu diễn các mô hình dữ liệu bởi các cấu trúc dữ liệu. Với các cấu trúc dữ liệu đã lựa chọn, các phép toán trên các mô hình dữ liệu được thể hiện bởi các thủ tục (hàm) trong ngôn ngữ lập trình nào đó. - Toán học đã cung cấp cho Tin học rất nhiều cấu trúc toán học có thể dùng làm mô hình dữ liệu. Chẳng hạn, các khái niệm toán học như dãy, tập hợp, ánh xạ, cây, đồ thị, quan hệ, nửa nhóm, nhóm, otomat, Trong các chương sau chúng ta sẽ lần lượt nghiên cứu một số mô hình dữ liệu quan trọng nhất, được sử dụng thường xuyên trong các thuật toán. Đó là các mô hình dữ liệu danh sách, cây, 19
  20. tập hợp. Với mỗi mô hình dữ liệu chúng ta nghiên cứu các cách cài đặt nó bởi các cấu trúc dữ liệu khác nhau. Trong mỗi cách cài đặt, một số phép toán trên mô hình có thể được thực hiện dễ dàng, nhưng các phép toán khác có thể lại không thuận tiện. Việc lựa chọn cấu trúc dữ liệu nào để biểu diễn mô hình phụ thuộc vào từng áp dụng. - Như đã nói, với mỗi mô hình dữ liệu, chúng ta có thể thực hiện một tập hợp các phép toán rất đa dạng, phong phú. Song trong nhiều áp dụng, chúng ta chỉ sử dụng mô hình với một số xác định các phép toán nào đó. Khi đó chúng ta sẽ có một kiểu dữ liệu trừu tượng. - Như vậy, một kiểu dữ liệu trừu tượng (abstract data type) là một mô hình dữ liệu được xét cùng với một số xác định các phép toán nào đó. Chẳng hạn, các tập hợp chỉ xét với các phép toán : thêm một phần tử vào một tập đã cho, loại một phần tử khỏi một tập hợp đã cho, tìm xem một phần tử đã cho có nằm trong một tập hợp hay không, lập thành kiểu dữ liệu trừu tượng (KDLTT) từ điển (dictionnaire). - Còn KDLTT hàng (hàng đợi) là mô hình dữ liệu danh sách cùng với hai phép toán chính là : thêm một phần tử mới vào một đầu danh sách, và loại một phần tử ở một đầu khác của danh sách. Chúng ta sẽ nghiên cứu kỹ một số kiểu dữ liệu trừu tượng quan trọng nhất : hàng, ngăn xếp (stack), từ điển, hàng ưu tiên. Với mỗi KDLTT, các cấu trúc dữ liệu để biểu diễn nó sẽ được nghiên cứu. Chúng ta cũng sẽ đánh giá hiệu quả của các phép toán trong từng cách cài đặt. 3. Thiết kế và giải thuật 3.1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu - Để đánh giá một cấu trúc dữ liệu chúng ta thường dựa vào một số tiêu chí sau: - Phản ánh đúng thực tế : Đây là tiêu chuẩn quan trọng nhất, quyết định tính đúng đắn của toàn bộ bài toán. Cần xem xét kỹ lưỡng cũng như dự trù các trạng thái biến đổi của dữ liệu trong chu trình sống để có thể chọn cấu trúc dữ liệu lưu trữ thể hiện chính xác đối tượng thực tế. - Ví dụ : Một số tình huống chọn cấu trúc lưu trữ sai : + Chọn một biến số nguyên int để lưu trữ tiền thưởng bán hàng (được tính theo công thức tiền thưởng bán hàng = trị giá hàng * 5%), do vậy sẽ làm tròn 20
  21. mọi giá trị tiền thưởng gây thiệt hại cho nhân viên bán hàng. Trường hợp này phải sử dụng biến số thực để phản ánh đúng kết quả của công thức tính thực tế. + Trong trường trung học, mỗi lớp có thể nhận tối đa 28 học sinh. Lớp hiện có 20 học sinh, mỗi tháng mỗi học sinh đóng học phí $10. Chọn một biến số nguyên unsigned char ( khả năng lưu trữ 0 - 255) để lưu trữ tổng học phí của lớp học trong tháng, nếu xảy ra trường hợp có thêm 6 học sinh được nhận vào lớp thì giá trị tổng học phí thu được là $260, vượt khỏi khả năng lưu trữ của biến đã chọn, gây ra tình trạng tràn, sai lệch. + Phù hợp với các thao tác trên đó: Tiêu chuẩn này giúp tăng tính hiệu quả của đề án: việc phát triển các thuật toán đơn giản, tự nhiên hơn; chương trình đạt hiệu quả cao hơn về tốc độ xử lý. - Ví dụ 1.1: Một tình huống chọn cấu trúc lưu trữ không phù hợp: + Cần xây dựng một chương trình soạn thảo văn bản, các thao tác xử lý thường xảy ra là chèn, xoá sửa các ký tự trên văn bản. Trong thời gian xử lý văn bản, nếu chọn cấu trúc lưu trữ văn bản trực tiếp lên tập tin thì sẽ gây khó khăn khi xây dựng các giải thuật cập nhật văn bản và làm chậm tốc độ xử lý của chương trình vì phải làm việc trên bộ nhớ ngoài. Trường hợp này nên tìm một cấu trúc dữ liệu có thể tổ chức ở bộ nhớ trong để lưu trữ văn bản suốt thời gian soạn thảo. 3.2. Đánh giá độ phức tạp của thuật toán - Việc đánh giá độ phức tạp của một thuật toán quả không dễ dàng chút nào. Ở dây, chúng ta chỉ muốn ước lượng thời gian thực hiện thuận toán T(n) để có thể có sự so sánh tương đối giữa các thuật toán với nhau. Trong thực tế, thời gian thực hiện một thuật toán còn phụ thuộc rất nhiều vào các điều kiện khác như cấu tạo của máy tính, dữ liệu đưa vào, , ở đây chúng ta chỉ xem xét trên mức độ của lượng dữ liệu đưa vào ban đầu cho thuật toán thực hiện. - Để ước lượng thời gian thực hiện thuật toán chúng ta có thể xem xét thời gian thực hiện thuật toán trong hai trường hợp: + Trong trường hợp tốt nhất: Tmin + Trong trường hợp xấu nhất: Tmax 21
  22. + Từ đó chúng ta có thể ước lượng thời gian thực hiện trung bình của thuật toán: Tavg 22
  23. Chương 2 Các kiểu dữ liệu nâng cao Mã chương: MH19_CH02 Giới thiệu: Bài này giới thiệu về các kiểu dữ liệu nâng cao trong cấu trúc dữ liệu và giải thuật. Mục tiêu: - Trình bày được các kiểu dữ liệu nâng cao; - Vận dụng được các kiểu dữ liệu nâng cao để lập trình một số bài toán cụ thể theo yêu cầu; - Rèn luyện tính cẩn thận, tỉ mỉ, chính xác, tu duy sáng tạo, kỹ năng lập trình và đảm bảo an toàn cho người và máy tính. Nội dung: 1. Mảng - Kiểu dữ liệu mảng là kiểu dữ liệu trong đó mỗi phần tử của nó là một tập hợp có thứ tự các giá trị có cùng cấu trúc được lưu trữ liên tiếp nhau trong bộ nhớ. Mảng có thể một chiều hay nhiều chiều. Một dãy số chính là hình tượng của mảng 1 chiều, ma trận là hình tượng của mảng 2 chiều. - Một điều đáng lưu ý là mảng 2 chiều có thể coi là mảng một chiều trong đó mỗi phần tử của nó là 1 mảng một chiều. Tương tự như vậy, một mảng n chiều có thể coi là mảng 1 chiều trong đó mỗi phần tử là 1 mảng n-1 chiều. - Hình tượng này được thể hiện rất rõ trong cách khai báo của C. - Mảng 1 chiều được khai báo như sau: [ ]; - Ví dụ để khai báo một biến có tên a là một mảng nguyên 1 chiều có tối đa 100 phần tử ta phải khai báo như sau: int a[100]; - Ta cũng có thể vừa khai báo vừa gán giá trị khởi động cho một mảng như sau: int a[5] = (1, 7, -3, 8, 19); - Trong trường hợp này C cho phép ta khai báo một cách tiện lợi hơn int a[] = (1, 7, -3, 8, 19); 23
  24. - Như ta thấy, ta không cần chỉ ra số lượng phần tử cụ thể trong khai báo. Trình biên dịch của C sẽ tự động làm việc này cho chúng ta. - Tương tự ta có thể khai báo một mảng 2 chiều hay nhiều chiều theo cú pháp sau: [ ][ ] ; - Ví dụ, ta có thể khai báo: int a[100][150]; hay int a[][]={{1, 7, -3, 8, 19},{4, 5, 2, 8, 9},{21, -7, 45, -3, 4}}; (mảng a sẽ có kích thước là 3x5). - Kiểu chuỗi ký tự: + Chuỗi ký tự là một trong các kiểu dữ liệu có cấu trúc đơn giản nhất và thường các ngôn ngữ lập trình đều định nghĩa nó như một kiểu cơ bản. Do tính thông dụng của kiểu chuỗi ký tự các ngôn ngữ lập trình luôn cung cấp sẵn một bộ các hàm thư viện các xử lý trên kiểu dữ liệu này. Đặc biệt trong C thư viện các hàm xử lý chuỗi ký tự rất đa dạng và phong phú. Các hàm này được đặt trong thư viện string.lib của C. + Chuỗi ký tự trong C được cấu trúc như một chuỗi liên tiếp các ký tự kết thúc bằng ký tự có mã ASCII bằng 0 (NULL character). Như vậy, giới hạn chiều dài của một chuỗi ký tự trong C là 1 Segment (tối đa chứa 65335 ký tự), ký tự đầu tiên được đánh số là ký tự thứ 0. + Ta có thể khai báo một chuỗi ký tự theo một số cách sau đây: char S[10]; //Khai báo một chuỗi ký tự S có chiều dài // tối đa 10 (kể cả kí tự kết thúc) char S[]="ABC";// Khai báo một chuỗi ký tự S có chiều // dài bằng chiều dài của chuỗi "ABC" // và giá trị khởi đầu của S là "ABC" char *S ="ABC";//Giống cách khai báo trên. + Trong ví dụ trên ta cũng thấy được một hằng chuỗi ký tự được thể hiện bằng một chuỗi ký tự đặt trong cặp ngoặc kép “”. 24
  25. + Các thao tác trên chuỗi ký tự rất đa dạng. Sau đây là một số thao tác thông dụng: So sánh 2 chuỗi: strcmp Sao chép 2 chuỗi: strcpy Kiểm tra 1 chuỗi nằm trong chuỗi kia: strstr Cắt 1 từ ra khỏi 1 chuỗi: strtok Đổi 1 số ra chuỗi: itoa Đổi 1 chuỗi ra số: atoi, atof, Đổi 1 hay 1 số giá trị ra chuỗi: sprintf Nhập một chuỗi: gets Xuất một chuỗi: puts 2. Con trỏ - Con trỏ là biến chứa địa chỉ của một biến khác. Con trỏ được sử dụng rất nhiều trong C, một phần là do chúng đôi khi là cách duy nhất để biểu diễn tính toán, và phần nữa do chúng thường làm cho chương trình ngắn gọn và có hiệu quả hơn các cách khác . - Con trỏ đã từng bị coi như có hại chẳng kém gì lệnh goto do cách sử dụng chúng đã tạo ra các chương trình khó hiểu. Điều này chắc chắn là đúng khi người ta sử dụng chúng một cách lôn xộn và do đó tạo ra các con trỏ trỏ đến đâu đó không biết trước được. 2.1. Con trỏ và địa chỉ - Vì con trỏ chứa địa chỉ của đối tượng nên nó có thể xâm nhập vào đối tượng gián tiếp qua con trỏ. Giả sử x là một biến kiểu int, và giả sử px là con trỏ được tạo ra theo một cách nào đó. - Phép toán một ngôi & sẽ cho địa chỉ của đối tượng, nên câu lệnh : px=&x; sẽ gán địa chỉ của biến x cho trỏ px, và px bây giờ được gọi là " trỏ tới biến x ". Phép toán & chỉ áp dụng được cho các biến và phần tử bảng, kết cấu kiểu &(x+1) và &3 là không hợp lệ. Lấy đại chỉ của biến register cũng là sai. - Phép toán một ngôi * coi là toán hạng của nó là đại chỉ cần xét và thâm nhập tới địa chỉ đó để lấy ra nội dung. Nếu biến y có kiểu int thì thì lệnh: y=*px; sẽ gán giá trị của biến mà trỏ px trỏ tới. Vậy dãy lệnh : 25
  26. px=&x; y=*px; sẽ gán giá trị của x cho y như trong lệnh : y=x; - Các khai báo cho các biến con trỏ có dạng : tên kiểu *tên con trỏ - Như trong ví dụ trên, ta khai báo con trỏ px kiểu int : int *px; - Trong khai báo trên ta đã ngụ ý nói rằng đó là một cách tượng trưng, rằng tổ hợp *px có kiểu int, tức là nếu px xuất hiện trong ngữ cảnh *px thì nó cũng tương đương với biến có kiểu int. - Con trỏ có thể xuất hiện trong các biểu thức. Chẳng hạn, nếu px trỏ tới số nguyên x thì *px có thể xuất hiện trong bất kỳ ngữ cảnh nào mà x có thể xuất hiện. - Ví dụ 2.1. - Lệnh y=*px+1; sẽ đặt y lớn hơn x một đơn vị. - Lệnh printf("%d",*px); sẽ in ra giá trị hiện tại của x - Lệnh: d=sqrt((double) *px); sẽ gán cho biến d căn bậc hai của x, giá trị này bị buộc phải chuyển sang double trước khi được chuyền cho sqrt ( cách dùng hàm sqrt ). - Trong các biểu thức kiểu như : y=*px+1; phép toán một ngôi * và & có mức ưu tiên cao hơn các phép toán số học, cho nên biểu thức này lấy bất ký giá trị nào mà px trỏ tới, cộng với 1 rồi gán cho y. - Con trỏ cũng có thể xuất hiện bên vế trái của phép gán. Nếu px trỏ tới x thì sau lệnh : *px=0; x sẽ có giá trị bằng 0. Cũng tương tự các lệnh: *px+=1; (*px)++; sẽ tăng giá trị của x lên 1 dơn vị. 26
  27. - Các dấu ngoặc đơn ở câu lệnh cuối là cần thiết , nếu không thì biểu thức sẽ tăng px thay cho tăng ở biến mà nó trỏ tới vì phép toán một ngôi như * và ++ được tính từ phải sang trái. - Cuối cùng, vì con trỏ là biến nên ta có thao tác chúng như đối với các biến khác. Nếu py cũng là con trỏ int thì lệnh : py=px; sẽ sao nội dung của px vào py, nghĩa là làm cho py trỏ tới nơi mà px trỏ. 2.2. Con trỏ và mảng một chiều - Trong C có mối quan hệ chặt chẽ giữa con trỏ và mảng: các phần tử của mảng có thể được xác định nhờ chỉ số hoặc thông qua con trỏ. 2.2.1. Phép toán lấy địa chỉ - Phép toán này chỉ áp dụng cho các phần tử của mảng một chiều. Giả sử ta có khai báo : double b[20]; - Khi đó phép toán : &b[9] sẽ cho địa chỉ của phần tử b[9]. 2.2.2. Tên mảng là một hằng địa chỉ - Khi khai báo: float a[10]; máy sẽ bố trí bố trí cho mảng a mười khoảng nhớ liên tiếp, mỗi khoảng nhớ là 4 byte. Như vậy, nếu biết địa chỉ của một phần tử nào đó của mảng a, thì ta có thể dễ dàng suy ra địa chỉ của các phần tử khác của mảng. - Với C ta có : a tương đương với &a[0] a+i tương đương với &a[i] *(a+i) tương đương với a[i] 2.2.3. Con trỏ trỏ tới các phần tử của mảng một chiều - Khi con trỏ pa trỏ tới phần tử a[k] thì : pa+i trỏ tới phần tử thứ i sau a[k], có nghĩa là nó trỏ tới a[k+i]. pa-i trỏ tới phần tử thứ i trước a[k], có nghĩa là nó trỏ tới a[k-i]. 27
  28. *(pa+i) tương đương với pa[i]. - Như vậy, sau hai câu lệnh : float a[20],*p; p=a; thì bốn cách viết sau có tác dụng như nhau : a[i] *(a+i) p[i] *(p+i) Ví dụ 2.2. Vào số liệu của các phần tử của một mảng và tính tổng của chúng : Cách 1: #include "stdio.h" main() { float a[4],tong; int i; for (i=0;i<4;++i) { printf("\n a[%d]=",i); scanf("%f",a+i); } tong=0; for (i=0;i<4;++i) tong+=a[i]; printf("\n Tong cac phan tu mang la :%8.2f ",tong); } Cách 2: #include "stdio.h" main() { float a[4],tong, *troa; int i; troa=a; for (i=0;i<4;++i) { printf("\n a[%d]=",i); 28
  29. scanf("%f",&troa[i]); } tong=0; for (i=0;i<4;++i) tong+=troa[i]; printf("\n Tong cac phan tu mang la :%8.2f ",tong); } Cách 3: #include "stdio.h" main() { float a[4],tong,*troa; int i; troa=a; for (i=0;i<4;++i) { printf("\n a[%d]=",i); scanf("%f",troa+i); } tong=0; for (i=0;i<4;++i) tong+=*(troa+i); printf("\n Tong cac phan tu mang la :%8.2f ",tong); } Chú ý : Mảng một chiều và con trỏ tương ứng phải cùng kiểu. 2.2.4. Mảng, con trỏ và xâu ký tự - Như ta đã biết trước đây, xâu ký tự là một dãy ký tự đặt trong hai dấu nháy kép, ví dụ như : "Viet nam" - Khi gặp một xâu ký tự, máy sẽ cấp phát một khoảng nhớ cho một mảng kiểu char đủ lớn để chứa các ký tự của xâu và chứa thêm ký tự '\0' là ký tự dùng làm 29
  30. ký tự kết thúc của một xâu ký tự. Mỗi ký tự của xâu được chứa trong một phần tử của mảng. - Cũng giống như tên mảng, xâu ký tự là một hàng địa chỉ biểu thị địa chỉ đầu của mảng chứa nó. Vì vậy nếu ta khai báo biến xau như một con trỏ kiểu char : char *xau; thì phép gán : xau="Ha noi" là hoàn toàn có nghĩa. Sau khi thực hiện câu lệnh này trong con trỏ xau sẽ có địa chỉ đầu của mảng (kiểu char) đang chứa xâu ký tự bên phải. Khi đó các câu lệnh : puts("Ha noi"); puts(xau); sẽ có cùng một tác dụng là cho hiện lên màn hình dòng chữ Ha noi. - Mảng kiểu char thường dùng để chứa một dãy ký tự đọc vào bộ nhớ. Ví dụ, để nạp từ bàn phím tên của một người ta dùng một mảng kiểu char với độ dài 25, ta sử dụng các câu lệnh sau : char ten[25]; printf("\n Ho ten :"); gets(ten); - Bây giờ ta xem giữa mảng kiểu char và con trỏ kiểu char có những gì giống và khác nhau. Để thấy được sự khác nhau của chúng, ta đưa ra sự so sánh sau : char *xau, ten[15]; ten="Ha noi" gets(xau); - Các câu lệnh trên là không hợp lệ. Câu lệnh thứ hai sai ở chỗ : ten là một hằng địa chỉ và ta không thể gán một hằng địa chỉ này cho một hằng địa chỉ khác. Câu lệnh thứ ba không thực hiện được, mục đích của câu lệnh là đọc từ bàn phím một dãy ký tự và lưu vào một vùng nhớ mà con trỏ xau trỏ tới. Song nội dung của con trỏ xau còn chưa xác định. Nếu trỏ xau đã trỏ tới một vùng nhớ nào đó thì câu lệnh này hoàn toàn có ý nghĩa. Chẳng hạn như sau khi thực hiện câu lệnh : 30
  31. xau=ten; thì cách viết: gets(ten) ; và gets(xau); đều có tác dụng như nhau. 2.3. Con trỏ và mảng nhiều chiều Việc sử lý mảng nhiều chiều phức tạp hơn so với mảng một chiều. Không phải mọi qui tắc đúng với mảng một chiều đều có thể áp dụng cho mảng nhiều chiều. 2.3.1. Phép lấy địa chỉ Phép lấy địa chỉ đối với các phần tử mảng hai chiều chỉ có thể áp dụng khi các phần tử mảng hai chiều có kiểu nguyên, còn lại thì phép lấy địa chỉ cho các phần tử mảng nhiều chiều là không thực hiện được .Ví dụ như ta có thể lấy địa chỉ &a[1][2] khi a là mảng nguyên. Thủ thuật đọc từ bàn phím phần tử mảng hai chiều dùng lệnh scanf : Chương trình đọc vào số liệu cho một ma trận hai chiều sẽ được thực hiện thông qua việc đọc vào một biến trung gian, đọc một giá trị và chứa tạm vào một biến trung gian sau đó ta gán biến cho phần tử mảng: #include "stdio.h" main() { float a[2][3], tg; int i,j; for (i=0;i<2;++i) for (j=0;j<2;++j) { printf("\n a[%d][%d]=",i,j); scanf("%8.2f",&tg); a[i][j]=tg; } } 2.3.2. Phép cộng địa chỉ trong mảng hai chiều 31
  32. Giả sử ta có mảng hai chiều a[2][3] có 6 phần tử úng với sáu địa chỉ liên tiếp trong bộ nhớ được xếp theo thứ tự sau : Phần tử a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2] Địa chỉ 1 2 3 4 5 6 Tên mảng a biểu thị địa chỉ đầu tiên của mảng. Phép cộng địa chỉ ở đây được thực hiện như sau : C coi mảng hai chiều là mảng ( một chiều ) của mảng, như vậy khai báo float a[2][3]; thì a là mảng mà mỗi phần tử của nó là một dãy 3 số thực ( một hàng của mảng ). Vì vậy : a trỏ phần tử thứ nhất của mảng : phần tử a[0][0] a+1 trỏ phần tử đầu hàng thứ hai của mảng : phần tử a[1][0] 2.3.3. Con trỏ và mảng hai chiều Để lần lượt duyệt trên các phần tử của mảng hai chiều ta có thể dùng con trỏ như minh hoạ ở ví dụ sau : float *pa,a[2][3]; pa=(float*)a; lúc đó : pa trỏ tới a[0][0] pa+1 trỏ tới a[0][1] pa+2 trỏ tới a[0][2] pa+3 trỏ tới a[1][0] pa+4 trỏ tới a[1][1] pa+5 trỏ tới a[1][2] Ví dụ 2.3. Dùng con trỏ để vào số liệu cho mảng hai chiều. Cách 1 : #include "stdio.h" main() { float a[2][3],*pa; 32
  33. int i; pa=(float*)a; for (i=0;i<6;++i) scanf("%f",pa+i); } Cách 2 : #include "stdio.h" main() { float a[2][3],*pa; int i; for (i=0;i<6;++i) scanf("%f",(float*)a+i); } 2.4. Kiểu con trỏ, kiểu địa chỉ, các phép toán trên con trỏ 2.4.1. Kiểu con trỏ và kiểu địa chỉ Con trỏ dùng để lưu địa chỉ. Mỗi kiểu địa chỉ cần có kiểu con trỏ tương ứng. Phép gán địa chỉ cho con trỏ chỉ có thể thực hiện được khi kiểu địa chỉ phù hợp với kiểu con trỏ. Ví dụ theo khai báo : float a[20][30],*pa,(*pm)[30]; thì : pa là con trỏ float pm là con trỏ kiểu float [30] a là địa chỉ kiểu float [30] Vì thế phép gán : pa=a; là không hợp lệ. Nhưng phép gán : pm=a; 2.4.2. Các phép toán trên con trỏ Có 4 phép toán liên quan đến con trỏ và đại chỉ là : 33
  34. Phép gán. Phép tăng giảm địa chỉ. Phép truy cập bộ nhớ. Phép so sánh. Phép gán : Phép gán chỉ thực hiện với các con trỏ cùng kiểu. Muốn gán các con trỏ khác kiểu phải dùng phép ép kiểu như ví dụ sau : int x; char *pc; pc=(char*)(&x); Phép tăng giảm địa chỉ : Để minh hoạ chi tiết cho phép toán này, ta xét ví dụ sau : Các câu lệnh : float x[30],*px; px=&x[10]; cho con trỏ px là con trỏ float trỏ tới phần tử x[10]. Kiểu địa chỉ float là kiểu địa chỉ 4 byte, nên các phép tăng giảm địa chỉ được thực hiện trên 4 byte. Vì thế : px+i trỏ tới phần tử x[10+i] px-i trỏ tới phần tử x[10-i] Xét ví dụ khác : Giả sử ta khai báo : float b[40][50]; Khai báo trên cho ta một mảng b gồm các dòng 50 phần tử thực. Kiểu địa chỉ của b là 50*4=200 byte. Do vậy : b trỏ tới đầu dòng thứ nhất ( phần tử b[0][0]). b+1 trỏ tới đầu dòng thứ hai ( phần tử b[1][0]). b+i trỏ tới đầu dòng thứ i ( phần tử b[i][0]). Phép truy cập bộ nhớ : 34
  35. Con trỏ float truy nhập tới 4 byte, con trỏ int truy nhập 2 byte, con trỏ char truy nhập 1 byte. Giả sử ta có cá khai báo : float *pf; int *pi; char *pc; Khi đó : Nếu trỏ pi trỏ đến byte thứ 100 thì *pf biểu thị vùng nhớ 4 byte liên tiếp từ byte 100 đến 103. Nếu trỏ pi trỏ đến byte thứ 100 thì *pi biểu thị vùng nhớ 2 byte liên tiếp từ byte 100 đến 101. Nếu trỏ pc trỏ đến byte thứ 100 thì *pc biểu thị vùng nhớ 1 byte chính là byte 100. Phép so sánh : Cho phép so sánh các con trỏ cùng kiểu, ví dụ nếu p1 và p2 là các con trỏ cùng kiểu thì nếu : p1 p2 nếu địa chỉ p1 trỏ tới cao hơn địa chỉ p2 trỏ tới. Ví dụ 2.4. Đoạn chương trình tính tổng các số thực dùng phép so sánh con trỏ : float a[100],*p,*pcuoi,tong=0.0; int n; pcuoi=a+n-1; /* Địa chỉ cuối dãy*/ for (p=a;p<=pcuoi;++p) s+=*p; Ví dụ 2.5. Dùng con trỏ char để tách các byte của một biến nguyên, ta làm như sau : Giả sử ta có lệnh : unsigned int n=0xABCD; /* Số nguyên hệ 16*/ char *pc; pc=(char*)(&n); 35
  36. Khi đó : *pc=0xAB (byte thứ nhất của n) *pc+1=0xCD (byte thứ hai của n) 2.4.3. Con trỏ kiểu void Con trỏ kiểu void được khai báo như sau : void *tên_con_trỏ; Đây là con trỏ đặc biệt, con trỏ không kiểu, nó có thể nhận bất kỳ kiểu nào. Chẳng hạn câu lệnh sau là hợp lệ : void *pa; float a[20][30]; pa=a; Con trỏ void thường dùng làm đối để nhận bất kỳ địa chỉ kiểu nào từ tham số thực. Trong thân hàm phải dùng phép chuyển đổi kiểu để chuyển sang dạng địa chỉ cần sử lý. Chú ý : Các phép toán tăng giảm địa chỉ, so sánh và truy cập bộ nhớ không dùng được trên con trỏ void. Ví dụ 2.6. Viết hàm thực hiện công ma trận : void congmt(void *a,void *b,void *c,int N,int N, int m); { float *pa,*pb,*pc; int i,j; pa=(float*)a; pb=(float*)b; pc=(float*)c; for (i=1;i<m;++i) for (j=1;j<m;++j) *(pc+i*N+j)=*(pa+i*N+j)+*(pb+i*N+j); } 36
  37. Vì đối là con trỏ void nên nó có thể nhận được địa chỉ của các ma trận trong lời gọi hàm. Tuy nhiên ta không thể sử dụng trực tiếp các đối con trỏ void trong thân hàm mà phải chuyển kiểu của chúng sang thành float. 2.4.5. Mảng con trỏ Mảng con trỏ là sự mở rộng khái niệm con trỏ. Mảng con trỏ là một mảng mà mỗi phần tử của nó chứa được một địa chỉ nào đó. Cũng giống như con trỏ, mảng con trỏ có nhiều kiểu : Mỗi phần tử của mảng con trỏ kiểu int sẽ chứa được các địa chỉ kiểu int. Tương tự cho các mảng con trỏ của các kiểu khác. Mảng con trỏ được khai báo theo mẫu : Kiểu *Tên_mảng_con_trỏ[N]; Trong đó Kiểu có thể là int, float, double, char còn Tên_mảng_con_trỏ là tên của mảng, N là một hằng số nguyên xác định độ lớn của mảng. Khi gặp khai báo trên, máy sẽ cấp phát N khoảng nhớ liên tiếp cho N phần tử của mảng Tên_mảng_con_trỏ. Ví dụ 2.7. Lệnh : double *pa[100]; Khai báo một mảng con trỏ kiểu double gồm 100 phần tử. Mỗi phần tử pa[i] có thể dùng để lưu trữ một địa chỉ kiểu double. Chú ý : Bản thân các mảng con trỏ không dùng để lưu trữ số liệu. Tuy nhiên mảng con trỏ cho phép sử dụng các mảng khác để lưu trữ số liệu một cách có hiệu quả hơn theo cách : chia mảng thành các phần và ghi nhớ địa chỉ đầu của mỗi phần vào một phần tử của mảng con trỏ. Trước khi sử dụng một mảng con trỏ ta cần gán cho mỗi phần tử của nó một giá trị. Giá trị này phải là giá trị của một biến hoặc một phần tử mảng. Các phần tử của mảng con trỏ kiểu char có thể được khởi đầu bằng các xâu ký tự. Ví dụ 2.8. Xét một tổ lao động có 10 người, mã của mỗi người chính là số thứ tự. Ta lập một hàm để khi biết mã số của nhân viên thì xác định được họ tên của nhân viên đó. #include "stdio.h" #include "ctype.h" 37
  38. void tim(int code); main() { int i; tt:printf("\n Tim nguoi co so TT la :"); scanf("%d",&i); tim(i); printf("Co tiep tuc nua khong C/K : '); if (tupper(getch())='C') goto tt; } void tim(int code); { static char *list[]= { "Khong co so thu tu nay " " Nguyen Van Toan" "Huynh Tuan Nghia" "Le Hong Son" "Tran Quang Tung" "Chu Thanh Tu" "Mac Thi Nga" "Hoang Hung" "Pham Trong Ha" "Vu Trung Duc" "Mai Trong Quat" }; printf("\n\n Ma so : %d",code); printf(": %s",()); } 2.5. Con trỏ tới hàm 2.5.1. Cách khai báo con trỏ hàm và mảng con trỏ hàm 38
  39. Ta sẽ trình bày quy tắc khai báo thông qua các ví dụ : Ví dụ 2.9. Câu lệnh : float (*f)(float),(*mf[50])(int); Để khai báo : f là con trỏ hàm kiểu float có đối là float mf là mảng con trỏ hàm kiểu float có đối kiểu int ( có 50 phần tử ) Câu lệnh : double (*g)(int, double),(*mg[30])(double, float); Để khai báo : g là con trỏ hàm kiểu double có các đối kiểu int và double mg là mảng con trỏ hàm kiểu double có các đối kiểu double và float ( có 30 phần tử ) 2.5.2. Tác dụng của con trỏ hàm Con trỏ hàm dùng để chứa địa chỉ của hàm. Muốn vậy ta thực hiện phép gán tên hàm cho con trỏ hàm. Để phép gán có ý nghĩa thì kiểu hàm và kiểu con trỏ phải tương thích. Sau phép gán, ta có thể dùng tên con trỏ hàm thay cho tên hàm. Ví dụ 2.10. #include "stdio.h" double fmax(double x, double y ) /* Tính max x,y */ { return(x>y ? x:y); } double (*pf)(double,double)=fmax; /*Khai báo và gán tên hàm cho con trỏ hàm */ main() /* Sử dụng con trỏ hàm*/ { printf("\n max=%f",pf(5.0,9.6)); } Ví dụ 2.11 #include "stdio.h" double fmax(double x, double y ) /* Tính max x,y */ { 39
  40. return(x>y ? x:y); } double (*pf)(double,double); /* Khai báo con trỏ hàm*/ main() /* Sử dụng con trỏ hàm*/ { pf=fmax; printf("\n max=%f",pf(5.0,9.6)); } 2.5.3. Đối của con trỏ hàm C cho phép thiết kế các hàm mà tham số thực trong lời gọi tới nó lại là tên của một hàm khác. Khi đó tham số hình thức tương ứng phải là một con trỏ hàm. Cách dùng con trỏ hàm trong thân hàm : Nếu đối được khai báo : double (*f)(double, int); thì trong thân hàm ta có thể dùng các cách viết sau để xác định giá trị của hàm ( do con trỏ f trỏ tới ) : f(x,m) hoặc (f)(x,m) hoặc (*f)(x,m) ở đây x là biến kiểu double còn m là biến kiểu int. 3. Cấu trúc và hợp 3.1. Cấu trúc (struct) Nếu kiểu dữ liệu mảng là kiểu dữ liệu trong đó mỗi phần tử của nó là một tập hợp có thứ tự các giá trị có cùng cấu trúc được lưu trữ liên tiếp nhau trong bộ nhớ thì mẫu tin là kiểu dữ liệu mà trong đó mỗi phần tử của nó là tập hợp các giá trị có thể khác cấu trúc. Kiểu mẫu tin cho phép chúng ta mô tả các đối tượng có cấu trúc phức tạp. Khai báo tổng quát của kiểu struct như sau: typedef struct { 40
  41. ; ; }[ ]; Ví dụ để mô tả các thông tin về một con người ta có thể khai báo một kiểu dữ liệu như sau: struct tagNguoi { char HoTen[35]; int NamSinh; char NoiSinh[40]; char GioiTinh; //0: Nữ, 1: Nam char DiaChi[50]; char Ttgd; //0:Không có gia đình, 1: Có gia đình }Nguoi; Kiểu mẫu tin bổ sung những thiếu sót của kiểu mảng, giúp ta có khả năng thể hiện các đối tượng đa dạng của thể giới thực vào trong máy tính một cách dễ dàng và chính xác hơn. 3.2. Kiểu union Kiểu union là một dạng cấu trúc dữ liệu đặc biệt của ngôn ngữ C. Nó rất giống với kiểu struct. Chỉ khác một điều, trong kiểu union, các trường được phép dùng chung một vung nhớ. Hay nói cách khác, cùng một vùng nhớ ta có thể truy xuất dưới các dạng khác nhau. Khai báo tổng quát của kiểu union như sau: typedef union { ; ; }[ ]; Ví dụ, ta có thể định nghĩa kiểu số sau: typedef union tagNumber{ 41
  42. int i; long l; }Number; Việc truy xuất đến một trường trong union được thực hiện hoàn toàn giống như trong struct. Giả sử có biến n kiểu Number. Khi đó, n.i cho ta một số kiểu int còn n.l cho ta một số kiểu long, nhưng cả hai đều dùng chung một vùng nhớ. Vì vậy, khi ta gán n.l = 0xfd03; thì giá trị của n.i cũng bị thay đổi (n.i sẽ bằng 3); Việc dùng kiểu union rất có lợi khi cần khai báo các CTDL mà nội dung của nó thay đổi tùy trạng thái. Ví dụ để mô tả các thông tin về một con người ta có thể khai báo một kiểu dữ liệu như sau: struct tagNguoi { char HoTen[35]; int NamSinh; char NoiSinh[40]; char GioiTinh; //0: Nữ, 1: Nam char DiaChi[50]; char Ttgd; //0:Không có gia đình, 1: Có gia đình union { char tenVo[35]; char tenChong[35]; } }Nguoi; Tùy theo người mà ta đang xét là nam hay nữ ta sẽ truy xuất thông tin qua trường có tên tenVo hay tenChong. 4. File 4.1. Khái niệm về tệp tin Tệp tin hay tệp dữ liệu là một tập hợp các dữ liệu có liên quan với nhau và có cùng một kiểu được nhóm lại với nhau thành một dãy. Chúng thường được chứa 42
  43. trong một thiết bị nhớ ngoài của mấy tính (đĩa mềm, đĩa cứng ) dưới một cái tên nào đó. Tên tiếng Anh của tệp là file, nó được dùng để chỉ ra một hộp đựng các phiếu hay thẻ ghi của thư viện. Một hình ảnh rõ nét giúp ta hình dung ra tệp là tủ phiếu của thư viện. Một hộp có nhiều phiếu giống nhau về hình thức và tổ chức, song lại khác nhau về nội dung. ở đây, tủ phiếu là tệp, các lá phiếu là các thành phần của tệp. Trong máy tính, một đĩa cứng hoặc một đĩa mềm đóng vai trò chiếc tủ (để chứa nhiều tệp). Tệp được chứa trong bộ nhớ ngoài, điều đó có nghĩa là tệp được lưu trữ để dùng nhiều lần và tồn tại ngay cả khi chương trình kết thúc hoặc mất điện. Chính vì lý do trên, chỉ những dữ liệu nào cần lưu trữ ( như hồ sơ chẳng hạn) thì ta nên dùng đến tệp. Tệp là một kiểu dữ liệu có cấu trúc. Định nghĩa tệp có phần nào giống mảng ở chỗ chúng đều là tập hợp của các phần tử dữ liệu cùng kiểu, song mảng thường có số phần tử cố định, số phần tử của tệp không được xác định trong định nghĩa. Trong C, các thao tác tệp được thực hiện nhờ các hàm thư viện. Các hàm này được chia làm hai nhóm : nhóm 1 và nhóm 2. Các hàm cấp 1 là các hàm nhập / xuất hệ thống, chúng thực hiện việc đọc ghi như DOS. Các hàm cấp 2 làm việc với tệp thông qua một biến con trỏ tệp. Do các hàm cấp 2 có nhiều kiểu truy xuất và dễ dùng hơn so với các hàm cấp 1 nên trong các chương trình viết trong C, các hàm cấp 2 hay được sử dụng hơn. Một tệp tin dù được xây dựng bằng cách nào đi nữa cũng chỉ đơn giản là một dãy các byte ghi trên đĩa (có giá trị từ 0 đến 255). Số byte của dãy chính là độ dài của tệp. Có hai kiểu nhập xuất dữ liệu lên tệp : Nhập xuất nhị phân và nhập xuất văn bản. 4.1.1. Nhập xuất nhị phân Dữ liệu ghi lên tệp theo các byte nhị phân như bộ nhớ, trong quá trình nhập xuất, dữ liệu không bị biến đổi. 43
  44. Khi đọc tệp, nếu gặp cuối tệp thì ta nhận được mã kết thúc tệp EOF ( được định nghĩa trong stdio.h bằng -1) và hàm feof cho giá trị khác 0. 4.1.2. Nhập xuất văn bản Kiểu nhập xuất văn bản chỉ khác kiểu nhị phân khi xử lý ký tự chuyển dòng ( mã 10) và ký tự mã 26. Đối với các ký tự khác, hai kiểu đều đọc ghi như nhau. 4.1.3. Mã chuyển dòng Khi ghi, một ký tự LF (mã 10) được chuyển thành 2 ký tự CR (mã 13) và LF Khi đọc, 2 ký tự liên tiếp CR và LF trên tệp chỉ cho ta một ký tự LF 4.1.4. Mã kết thúc tệp Trong khi đọc, nếu gặp ký tự có mã 26 hoặc cuối tệp thì ta nhận được mã kết thúc tệp EOF ( bằng -1) và hàm feof(fp) cho giá trị khác 0 ( bằng 1). 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 4.2.1. Khai báo sử dụng tệp Để khai báo sử dụng tệp, ta dùng lệnh sau : FILE biến_con_trỏ_tệp; Trong đó biến_con_trỏ_tệp có thể là biến đơn hay một danh sách các biến phân cách nhau bởi dấu phảy ( dấu , ). Ví dụ : FILE *vb, *np; /* Khai báo hai biến con trỏ tệp */ 4.2.2. Mở tệp - hàm fopen Cấu trúc ngữ pháp của hàm : FILE *fopen(const char *tên_tệp, const char *kiểu); Nguyên hàm trong : stdio.h . Trong đó : Đối thứ nhất là tên tệp, đối thứ hai là kiểu truy nhập. Công dụng : Hàm dùng để mở tệp. Nếu thành công hàm cho con trỏ kiểu FILE ứng với tệp vừa mở. Các hàm cấp hai sẽ làm việc với tệp thông qua con trỏ này. Nếu có lỗi hàm sẽ trả về giá trị NULL. 44
  45. Bảng sau chỉ ra các giá trị của kiểu : Tên kiểu ý nghĩa "r" "rt" Mở một tệp để đọc theo kiểu văn bản. Tệp cần đọc phải đã tồn tại, nếu không sẽ có lỗi "w" "wt" Mở một tệp để ghi theo kiểu văn bản. Nếu tệp đã tồn tại thì nó sẽ bị xoá. "a" "at" Mở một tệp để ghi bổ xung theo kiểu văn bản. Nếu tệp chưa tồn tại thì tạo tệp mới. "rb" Mở một tệp để đọc theo kiểu nhị phân. Tệp cần đọc phải đã tồn tại, nếu không sẽ có lỗi. "wb" Mở một tệp mới để ghi theo kiểu nhị phân. Nếu tệp đã tồn tại thì nó sẽ bị xoá. "ab" Mở một tệp để ghi bổ xung theo kiểu nhị phân. Nếu tệp chưa tồn tại thì tạo tệp mới. "r+" "r+t" Mở một tệp để đọc/ghi theo kiểu văn bản. Tệp cần đọc phải đã tồn tại, nếu không sẽ có lỗi "w+" Mở một tệp để đọc/ghi theo kiểu văn "w+t" bản. Nếu tệp đã tồn tại thì nó sẽ bị xoá. "a+" "a+t" Mở một tệp để đọc/ghi bổ xung theo kiểu văn bản. Nếu tệp chưa tồn tại thì tạo tệp mới. "r+b" Mở một tệp để đọc/ghi theo kiểu nhị 45
  46. phân. Tệp cần đọc phải đã tồn tại, nếu không sẽ có lỗi. "w+b" Mở một tệp mới để đọc/ghi theo kiểu nhị phân. Nếu tệp đã tồn tại thì nó sẽ bị xoá. "a+b" Mở một tệp để đọc/ghi bổ xung theo kiểu nhị phân. Nếu tệp chưa tồn tại thì tạo tệp mới. Chú ý : Trong các kiểu đọc ghi, ta nên lầm sạch vùng đệm trước khi chuyển từ đọc sang ghi hoặc ngược lại. Ta sẽ đề cập đến các hàm với tính năng xoá sau này. Ví dụ : f=fopen("TEPNP","wb"); 4.2.3. Đóng tệp - hàm fclose Cấu trúc ngữ pháp của hàm : int fclose(FILE *fp); Nguyên hàm trong : stdio.h . Trong đó : fp là con trỏ ứng với tệp cần đóng. Công dụng : Hàm dùng để đóng tệp khi kết thúc các thao tác trên nó. Khi đóng tệp, máy thực hiện các công việc sau : - Khi đang ghi dữ liệu thì máy sẽ đẩy dữ liệu còn trong vùng đệm lên đĩa - Khi đang đọc dữ liệu thì máy sẽ xoá vùng đệm - Giải phóng biến trỏ tệp. - Nếu lệnh thành công, hàm sẽ cho giá trị 0, trái lại nó cho hàm EOF. Ví dụ : fclose(f); 4.2.4. Kiểmtra cuối tệp - hàm feof 46
  47. Cấu trúc ngữ pháp của hàm : int feof(FILE *fp); Nguyên hàm trong : stdio.h . Trong đó fp là con trỏ tệp. Công dụng : Hàm dùng để kiểm tra cuối tệp. Hàm cho giá trị khác 0 nếu gặp cuối tệp khi đọc, trái lại hàm cho giá trị 0. 4.2.5. Ghi các mẫu tin lên tệp - hàm fwrite Cấu trúc ngữ pháp của hàm : int fwrite(void *ptr, int size, int n, FILE *fp); Nguyên hàm trong : stdio.h . Trong đó : ptr là con trỏ trỏ tới vùng nhớ chứa dữ liệu cần ghi. size là kích thước của mẫu tin theo byte n là số mẫu tin cần ghi fp là con trỏ tệp Công dụng : Hàm ghi n mẫu tin kích thước size byte từ vùng nhớ ptr lên tệp fp. Hàm sẽ trả về một giá trị bằng số mẫu tin thực sự ghi được. Ví dụ : #include "stdio.h" struct mystruct { int i; char ch; }; main() { FILE *stream; struct mystruct s; stream = fopen("TEST.TXT", "wb") /* Mở tệp TEST.TXT */ 47
  48. s.i = 0; s.ch = 'A'; fwrite(&s, sizeof(s), 1, stream); /* Viết cấu trúc vào tệp */ fclose(stream); /* Đóng tệp */ return 0; } 4.2.6. Đọc các mẫu tin từ tệp - hàm fread Cấu trúc ngữ pháp của hàm : int fread(void *ptr, int size, int n, FILE *fp); Nguyên hàm trong : stdio.h . Trong đó : ptr là con trỏ trỏ tới vùng nhớ chứa dữ liệu cần ghi. size là kích thước của mẫu tin theo byte n là số mẫu tin cần ghi fp là con trỏ tệp Công dụng : Hàm đọc n mẫu tin kích thước size byte từ tệp fp lên lên vùng nhớ ptr. Hàm sẽ trả về một giá trị bằng số mẫu tin thực sự đọc được. Ví dụ : #include "string.h" #include "stdio.h" main() { FILE *stream; char msg[] = "Kiểm tra"; char buf[20]; stream = fopen("DUMMY.FIL", "w+"); /* Viết vài dữ liệu lên tệp */ fwrite(msg, strlen(msg)+1, 1, stream); /* Tìm điểm đầu của file */ fseek(stream, SEEK_SET, 0); 48
  49. /* Đọc số liệu và hiển thị */ fread(buf, strlen(msg)+1, 1, stream); printf("%s\n", buf); fclose(stream); return 0; } 49
  50. Chương 3 Danh sách Mã chương: MH19_CH03 Giới thiệu: Bài này giới thiệu về kiểu dữ liệu danh sách trong cấu trúc dữ liệu và giải thuật. Mục tiêu: - Trình bày được các khái niệm, cách khai báo, các loại danh sách liên kết; - Vận dụng được danh sách liên kết lập trình một số bài toán cụ thể theo yêu cầu; - Rèn luyện tính cẩn thận, tỉ mỉ, chính xác, tu duy sáng tạo, kỹ năng lập trình và đảm bảo an toàn cho người và máy tính. Nội dung: 1. Các khái niệm 1.1. Khái niệm về danh sách Danh sách là tập hợp các phần tử có kiểu dữ liệu xác định và giữa chúng có một mối liên hệ nào đó. Số phần tử của danh sách gọi là chiều dài của danh sách. Một danh sách có chiều dài bằng 0 là một danh sách rỗng. 1.2. Các phép toán trên danh sách Tùy thuộc vào đặc điểm, tính chất của từng loại danh sách mà mỗi loại danh sách có thể có hoặc chỉ cần thiết có một số phép toán (thao tác) nhất định nào đó. Nói chung, trên danh sách thường có các phép toán như sau: - Tạo mới một danh sách: Trong thao tác này, chúng ta sẽ đưa vào danh sách nội dung của các phần tử, do vậy chiều dài của danh sách sẽ được xác định. Trong một số trường hợp, chúng ta chỉ cần khởi tạo giá trị và trạng thái ban đầu cho danh sách. - Thêm một phần tử vào danh sách: Thao tác này nhằm thêm một phần tử vào trong danh sách, nếu việc thêm thành công thì chiều dài của danh sách sẽ t ăng lên 1. Cũng tùy thuộc vào từng loại danh sách và từng trường hợp cụ thể mà việc thêm phần tử sẽ được tiến hành đầu, cuối hay giữa danh sách. 50
  51. - Tìm kiếm một phần tử trong danh sách: Thao tác này sẽ vận dụng các thuật toán tìm kiếm để tìm kiếm một phần tử trên danh sách thỏa mãn một tiêu chuẩn nào đó (thường là tiêu chuẩn về giá trị). - Loại bỏ bớt một phần tử ra khỏi danh sách: Ngược với thao tác thêm, thao tác này sẽ loại bỏ bớt một phần tử ra khỏi danh sách do vậy, nếu việc loại bỏ thành công thì chiều dài của danh sách cũng bị giảm xuống - Thông thường, trước khi thực hiện thao tác này chúng ta thường phải thực hiện thao tác tìm kiếm phần tử cần loại bỏ. - Cập nhật (sửa đổi) giá trị cho một phần tử trong danh sách: Thao tác này nhằm sửa đổi nội dung của một phần tử trong danh sách. Tương tự như thao tác loại bỏ, trước khi thay đổi thường chúng ta cũng phải thực hiện thao tác tìm kiếm phần tử cần thay đổi. - Sắp xếp thứ tự các phần tử trong danh sách: Trong thao tác này chúng ta sẽ vận dụng các thuật toán sắp xếp để sắp xếp các phần tử trên danh sách theo một trật tự xác định. - Tách một danh sách thành nhiều danh sách: Thao tác này thực hiện việc chia một danh sách thành nhiều danh sách con theo một tiêu thức chia nào đó. Kết quả sau khi chia là tổng chiều dài trong các danh sách con phải bằng chiều dài của danh sách ban đầu. - Nhập nhiều danh sách thành một danh sách: Ngược với thao tác chia, thao tác này tiến hành nhập nhiều danh sách con thành một danh sách có chiều dài bằng tổng chiều dài các danh sách con. Tùy vào từng trường hợp mà việc nhập có thể là: + Ghép nối đuôi các danh sách lại với nhau, + Trộn xen lẫn các phần tử trong danh sách con vào danh sách lớn theo một trật tự nhất định. - Sao chép một danh sách: Thao tác này thực hiện việc sao chép toàn bộ nội dung của danh sách này sang một danh sách khác sao cho sau khi sao chép, hai danh sách có nội dung giống hệt nhau. 51
  52. - Hủy danh sách: Thao tác này sẽ tiến hành hủy bỏ (xóa bỏ) toàn bộ các phần tử trong danh sách. Việc xóa bỏ này tùy vào từng loại danh sách mà có thể là xóa bỏ toàn bộ nội dung hay cả nội dung lẫn không gian bộ nhớ lưu trữ danh sách. 2. Lưu tữ kế tiếp đối với danh sách tuyến tính 2.1. Định nghĩa Danh sách liên kết là tập hợp các phần tử mà giữa chúng có một sự nối kết với nhau thông qua vùng liên kết của chúng. Sự nối kết giữa các phần tử trong danh sách liên kết đó là sự quản lý, ràng buộc lẫn nhau về nội dung của phần tử này và địa chỉ định vị phần tử kia. Tùy thuộc vào mức độ và cách thức nối kết mà danh sách liên kết có thể chia ra nhiều loại khác nhau: - Danh sách liên kết đơn; - Danh sách liên kết đôi/kép; - Danh sách đa liên kết; - Danh sách liên kết vòng (vòng đơn, vòng đôi). Mỗi loại danh sách sẽ có cách biểu diễn các phần tử (cấu trúc dữ liệu) riêng và các thao tác trên đó. Trong tài liệu này chúng ta chỉ trình bày 02 loại danh sách liên kết cơ bản là danh sách liên kết đơn và danh sách liên kết đôi. 2.2. Danh sách liên kết đơn (Singly Linked List) 2.2.1. Cấu trúc dữ liệu: Nội dung của mỗi phần tử trong danh sách liên kết (còn gọi là một nút) gồm hai vùng: Vùng dữ liệu và Vùng liên kết và có cấu trúc dữ liệu như sau: typedef struct SLL_Node { T Key; InfoType Info; SLL_Node * NextNode; // Vùng liên kết quản lý địa chỉ phần tử kế tiếp } SLL_OneNode; Tương tự như trong các chương trước, ở đây để đơn giản chúng ta cũng giả thiết rằng vùng dữ liệu của mỗi phần tử trong danh sách liên kết đơn chỉ bao gồm một thành phần khóa nhận diện (Key) cho phần tử đó. Khi đó, cấu trúc dữ liệu trên có 52
  53. thể viết lại đơn giản như sau: typedef struct SLL_Node { T Key; SLL_Node * NextNode; // Vùng liên kết quản lý địa chỉ phần tử kế tiếp } SLL_OneNode; typedef SLL_OneNode * SLL_Type; Để quản lý một danh sách liên kết chúng ta có thể sử dụng nhiều phương pháp khác nhau và tương ứng với các phương pháp này chúng ta sẽ có các cấu trúc dữ liệu khác nhau, cụ thể: - Quản lý địa chỉ phần tử đầu danh sách: SLL_Type SLList1; Hình ảnh minh họa: SLList1 NULL 15 10 20 18 40 35 30 - Quản lý địa chỉ phần tử đầu và cuối danh sách: typedef struct SLL_PairNode { SLL_Type SLLFirst; SLL_Type SLLLast; } SLLP_Type; SLLP_Type SLList2; Hình ảnh minh họa: SLLFirst SLLLast NULL 15 10 20 18 40 35 30 - Quản lý địa chỉ phần tử đầu, địa chỉ phần tử cuối và số phần tử trong danh sách: typedef struct SLL_PairNNode { SLL_Type SLLFirst; SLL_Type SLLLast; unsigned NumNode; } SLLPN_Type; SLLPN_Type SLList3; 53
  54. Hình ảnh minh họa: SLLFirst SLLLast NULL 15 10 20 18 40 35 30 NumNode = 7 2.2.2. Các thao tác trên danh sách liên kết đơn: Với mỗi cách quản lý khác nhau của danh sách liên kết đơn , các thao tác cũng sẽ có sự khác nhau về mặt chi tiết song nội dung cơ bản ít có sự khác nhau. Do vậy, ở đây chúng ta chỉ trình bày các thao tác theo cách quản lý thứ nhất (quản lý địa chỉ của phần tử đầu danh sách liên kết đơn), các cách quản lý khác sinh viên tự vận dụng để điều chỉnh cho thích hợp. 2.2.2.1. Khởi tạo danh sách (Initialize): Trong thao tác này chỉ đơn giản là chúng ta cho giá trị con trỏ quản lý địa chỉ phần tử đầu danh sách về con trỏ NULL. Hàm khởi tạo danh sách liên kết đơn như sau: void SLL_Initialize(SLL_Type &First) { First = NULL; return; } Hình ảnh minh họa: SLList1 NULL 2.2.2.2. Tạo mới một phần tử / nút: Giả sử chúng ta cần tạo mới một phần tử có thành phần dữ liệu là NewData. - Thuật toán: B1: First = new SLL_OneNode B2: IF (First = NULL) Thực hiện Bkt B3: First->NextNode = NULL B4: First->Key = NewData Bkt: Kết thúc - Cài đặt thuật toán: Hàm SLL_Create_Node có prototype: SLL_Type SLL_Create_Node(T NewData); 54
  55. Hàm tạo mới một nút có thành phần dữ liệu là NewData, hàm trả về con trỏ trỏ tới địa chỉ của nút mới tạo. Nếu không đủ bộ nhớ để tạo, hàm trả về con trỏ NULL. SLL_Type SLL_Create_Node(T NewData) { SLL_Type Pnode = new SLL_OneNode; if (Pnode != NULL) { Pnode->NextNode = NULL; Pnode->Key = NewData; } return (Pnode); } - Minh họa thuật toán: Giả sử chúng ta cần tạo nút có thành phần dữ liệu là 20: NewData = 20 Pnode = new SLL_OneNode Pnode Pnode->NextNode = NULL Pnode->Key = NewData Pnode 20 NULL 2.2.2.3. Thêm một phần tử vào trong danh sách: Giả sử chúng ta cần thêm một phần tử có giá trị thành phần dữ liệu là NewData vào trong danh sách. Việc thêm có thể diễn ra ở đầu, cuối hay ở giữa danh sách liên kết. Do vậy, ở đây chúng ta trình bày 3 thao tác thêm riêng biệt nhau: - Thuật toán thêm phần tử vào đầu danh sách liên kết đơn: B1: NewNode = SLL_Create_Node (NewData) B2: IF (NewNode = NULL) Thực hiện Bkt B3: NewNode->NextNode = SLList // Nối SLList vào sau NewNode B4: SLList = NewNode // Chuyển vai trò đứng đầu của NewNode cho SLList Bkt: Kết thúc 55
  56. - Minh họa thuật toán: Giả sử chúng ta cần thêm nút có thành phần dữ liệu là 25: NewData = 25 NewNode 25 NULL NULL SLList 10 20 18 40 35 30 NewNode->NextNode = SLList: NewNode 25 NULL SLList 10 20 18 40 35 30 SLList = NewNode: NewNode 25 SLList NULL 10 20 18 40 35 30 Kết quả sau khi chèn: SLList NULL 25 10 20 18 40 35 30 - Thuật toán thêm phần tử vào cuối danh sách liên kết đơn: B1: NewNode = SLL_Create_Node (NewData) B2: IF (NewNode = NULL) Thực hiện Bkt B3: IF (SLList = NULL) B3.1: SLList = NewNode B3.2: Thực hiện Bkt // Tìm đến địa chỉ của phần tử cuối cùng trong danh sách liên kết đơn B4: CurNode = SLList B5: IF (CurNode->NextNode = NULL) Thực hiện B8 B6: CurNode = CurNode->NextNode // Chuyển qua nút kế tiếp 56
  57. B7: Lặp lại B5 B8: CurNode->NextNode = NewNode // Nối NewNode vào sau CurNode Bkt: Kết thúc - Minh họa thuật toán: Giả sử chúng ta cần thêm nút có thành phần dữ liệu là 25: NewData = 25 NULL NewNode 25 SLList CurNode 15 10 20 18 40 35 NULL CurNode->NextNode = NewNode: NULL NewNode 25 SLList CurNode 15 10 20 18 40 35 Kết quả sau khi chèn: SLList NULL 15 10 20 18 40 35 25 - Thuật toán thêm phần tử vào giữa danh sách liên kết đơn: Giả sử chúng ta cần thêm một phần tử có giá trị thành phần dữ liệu là NewData vào trong danh sách SLList vào ngay sau nút có địa chỉ InsNode. Trong thực tế nhiều khi chúng ta phải thực hiện thao tác tìm kiếm để xác định địa chỉ InsNode, ở đây giả sử chúng ta đã xác định được địa chỉ này. B1: NewNode = SLL_Create_Node (NewData) B2: IF (NewNode = NULL) Thực hiện Bkt B3: IF (InsNode->NextNode = NULL) B3.1: InsNode->NextNode = NewNode B3.2: Thực hiện Bkt // Nối các nút kế sau InsNode vào sau NewNode B4: NewNode->NextNode = InsNode->NextNode // Chuyển mối liên kết giữa InsNode với nút kế của nó về NewNode 57
  58. B5: InsNode->NextNode = NewNode Bkt: Kết thúc - Minh họa thuật toán: Giả sử chúng ta cần thêm nút có thành phần dữ liệu là 25 vào sau nút có địa chỉ InsNode như sau: NewData = 25 NewNode 25 NULL SLList InsNode 15 10 20 18 40 35 NULL NewNode->NextNode = InsNode->NextNode: NewNode 25 SLList InsNode 15 10 20 18 40 35 NULL InsNode->NextNode = NewNode: NewNode 25 SLList 15 10 20 18 40 35 NULL InsNode Kết quả sau khi chèn: SLList NULL 15 10 20 25 18 40 35 - Cài đặt thuật toán: Các hàm thêm phần tử tương ứng với các trường hợp có prototype như sau: SLL_Type SLL_Add_First(SLL_Type &SList, T NewData); SLL_Type SLL_Add_Last(SLL_Type &SList, T NewData); SLL_Type SLL_Add_Mid(SLL_Type &SList, T NewData, SLL_Type &InsNode); Hàm thực hiện việc chèn phần tử có giá trị thành phần dữ liệu NewData vào trong danh sách liên kết đơn quản lý bởi con trỏ đầu danh sách SList tương ứng với 3 trường hợp: Thêm đầu, thêm cuối, thêm giữa. Các hàm trả về giá trị là địa chỉ của nút đầu tiên nếu việc thêm thành công. Trong trường hợp ngược lại, các hàm trả về con trỏ NULL. 58
  59. Riêng đối với trường hợp thêm giữa, hàm SLL_Add_Mid thực hiện việc thêm vào ngay sau nút có địa chỉ InsNode. Nội dung của các hàm như sau: SLL_Type SLL_Add_First(SLL_Type &SList, T NewData) { SLL_Type NewNode = SLL_Create_Node(NewData); if (NewNode == NULL) return (NULL); NewNode->NextNode = SList; SList = NewNode; return (SList); } //=== === SLL_Type SLL_Add_Last(SLL_Type &SList, T NewData) { SLL_Type NewNode = SLL_Create_Node(NewData); if (NewNode == NULL) return (NULL); if (SList == NULL) { SList = NewNode; return (SList); } SLL_Type CurNode = SList; while (CurNode->NextNode != NULL) CurNode = CurNode->NextNode; CurNode->NextNode = NewNode; return (SList); } //=== === SLL_Type SLL_Add_Mid(SLL_Type &SList, T NewData, SLL_Type &InsNode) { SLL_Type NewNode = SLL_Create_Node(NewData); if (NewNode == NULL) 59
  60. return (NULL); if (InsNode->NextNode == NULL) { InsNode->NextNode = NewNode; return (SList); } NewNode->NextNode = InsNode->NextNode; InsNode->NextNode = NewNode; return (SList); } 2.2.2.4. Duyệt qua các nút trong danh sách: Đây là một thao tác thường xuyên xảy ra trên danh sách liên kết đơn nói chung và các danh sách khác nói riêng để thực hiện thao tác xử lý các nút hoặc xử lý dữ liệu tại các nút. Có nhiều thao tác xử lý tùy từng trường hợp và yêu cầu song ở đây đơn giản chúng ta chỉ duyệt để xem nội dung thành phần dữ liệu trong danh sách. - Thuật toán: B1: CurNode = SLList B2: IF (CurNode = NULL) Thực hiện Bkt B3: OutputData(CurNode->Key) // Xuất giá trị thành phần dữ liệu trong 1 nút B4: CurNode = CurNode->NextNode B5: Lặp lại B2 Bkt: Kết thúc - Cài đặt thuật toán: Hàm SLL_Travelling có prototype: void SLL_Travelling(SLL_Type SList); Hàm duyệt qua các nút trong danh sách liên kết đơn quản lý bởi địa chỉ nút đầu tiên thông qua SList để xem nội dung thành phần dữ liệu của mỗi nút. Nội dung của hàm như sau: void SLL_Travelling (SLL_Type SList) { SLL_Type CurNode = SList; while (CurNode != NULL) 60
  61. { OutputData(CurNode->Key); CurNode = CurNode->NextNode; } return; } _ Lưu ý: Hàm OutputData thực hiện việc xuất nội dung của một biến có kiểu dữ liệu T. Tùy vào từng trường hợp cụ thể mà chúng ta viết hàm OutputData cho phù hợp. 2.2.2.5. Tìm kiếm một phần tử trong danh sách: Giả sử chúng ta cần tìm kiếm xem trong danh sách liên kết đơn có tồn tại nút có thành phần dữ liệu là SearchData hay không. Thao tác này chúng ta vận dụng thuật toán tìm tuyến tính để tìm kiếm. - Thuật toán: B1: CurNode = SLList B2: IF (CurNode = NULL OR CurNode->Key = SearchData) Thực hiện Bkt B3: CurNode = CurNode->NextNode B4: Lặp lại B2 Bkt: Kết thúc - Cài đặt thuật toán: Hàm SLL_Searching có prototype: SLL_Type SLL_Searching(SLL_Type SList, T SearchData); Hàm thực hiện việc tìm kiếm nút có thành phần dữ liệu là SearchData trên danh sách liên kết đơn quản lý bởi địa chỉ nút đầu tiên thông qua SList. Hàm trả về địa chỉ của nút đầu tiên trong danh sách khi tìm thấy, ngược lại hàm trả về con trỏ NULL. Nội dung của hàm như sau: SLL_Type SLL_Searching(SLL_Type SList, T SearchData) { SLL_Type CurNode = SList; while (CurNode != NULL) { if (CurNode->Key == SearchData) 61
  62. break; CurNode = CurNode->NextNode; } return (CurNode); } 2.2.2.6. Loại bỏ bớt một phần tử ra khỏi danh sách: Giả sử chúng ta cần loại bỏ phần tử có giá trị thành phần dữ liệu là DelData trong danh sách liên kết đơn. Để thực hiện điều này trước tiên chúng ta phải thực hiện thao tác tìm kiếm địa chỉ của nút có thành phần dữ liệu là DelData, sau đó mới thực hiện thao tác loại bỏ nếu tìm thấy. Tuy nhiên trong quá trình tìm kiếm, nếu tìm thấy chúng ta phải ghi nhận địa chỉ của nút đứng ngay trước nút tìm thấy là PreDelNode. - Thuật toán: // Tìm kiếm nút có Key là DelData trong danh sách B1: DelNode = SLList B2: PreDelNode = NULL B3: IF (DelNode = NULL) Thực hiện Bkt B4: IF (DelNode->Key=DelData) Thực hiện B8 B5: PreDelNode = DelNode B6: DelNode = DelNode->NextNode B7: Lặp lại B3 // Loại bỏ nút tại địa chỉ DelNode ra khỏi danh sách B8: IF (PreDelNode = NULL) // Loại bỏ nút đầu tiên trong danh sách B8.1: SLList = SLList->NextNode B8.2: Thực hiện B10 // Liên kết các nốt sau DelNode về nút PreDelNode B9: PreDelNode->NextNode = DelNode->NextNode 62
  63. // Cắt mối liên kết giữa DelNode với các nút còn lại trong danh sách // và hủy DelNode B10: DelNode->NextNode = NULL B11: delete DelNode Bkt: Kết thúc - Cài đặt thuật toán: Hàm SLL_Delete_Node có prototype: int SLL_Delete_Node (SLL_Type &SList, T DelData); Hàm thực hiện việc xóa phần tử có thành phần dữ liệu là DelData trong danh sách liên kết quản lý bởi con trỏ đầu SList. Hàm trả về giá trị 1 nếu việc xóa thành công và ngược lại, hàm trả về giá trị -1. Nội dung của hàm như sau: int SLL_Delete_Node (SLL_Type &SList, T DelData) { SLL_Type DelNode = SList; SLL_Type PreDelNode = NULL; while (DelNode != NULL) { if (DelNode->Key == DelData) break; PreDelNode = DelNode; DelNode = DelNode->NextNode; } if (DelNode == NULL) return (-1); if (PreDelNode == NULL) SList = SList->NextNode; else PreDelNode->NextNode = DelNode->NextNode; DelNode->NextNode = NULL; delete DelNode; return (1); } - Minh họa thuật toán: 63
  64. + Giả sử chúng ta cần hủy nút có thành phần dữ liệu là 25: DelData = 25 SLList NULL 25 10 20 18 40 35 30 DelNode SLList = SLList->NextNode DelNode SLList NULL 25 10 20 18 40 35 30 DelNode->NextNode = NULL DelNode SLList NULL 25 10 20 18 40 35 30 NULL Kết quả sau khi hủy: SLList 10 20 18 40 35 30 NULL + Bây giờ giả sử chúng ta cần hủy nút có thành phần dữ liệu là 20: DelData = 20 SLList DelNode NULL 25 10 20 18 40 35 30 PreDelNode PreDelNode->NextNode = DelNode->Next SLList DelNode NULL 25 10 20 18 40 35 30 PreDelNode DelNode->Next = NULL SLList DelNode NULL NULL 25 10 20 18 40 35 30 PreDelNode Kết quả sau khi hủy: SLList 25 10 18 40 35 30 NULL 2.2.2.7. Hủy danh sách: Thao tác này thực chất là thực hiện nhiều lần thao tác hủy một nút. 64
  65. - Thuật toán: B1: IF (SLList = NULL) Thực hiện Bkt B2: TempNode = SLList B3: SLList = SLList->NextNode B4: TempNode->NextNode = NULL B5: delete TempNode B6: Lặp lại B1 Bkt: Kết thúc - Cài đặt: Hàm SLL_Delete có prototype: void SLL_Delete (SLL_Type &SList); Hàm thực hiện việc hủy toàn bộ danh sách SList. Nội dung của hàm như sau: void SLL_Delete (SLL_Type &SList) { SLL_Type TempNode = SList; while (SList != NULL) { SList = SList->NextNode; TempNode->NextNode = NULL; delete TempNode; TempNode = SList; } return ; } 2.2.2.8. Tạo mới danh sách/ Nhập danh sách: Việc tạo mới một danh sách liên kết đơn thực chất là chúng ta liên tục thực hiện thao tác thêm một phần tử vào danh sách mà ban đầu danh sách này là một danh sách rỗng. Có thể sử dụng một trong ba hàm thêm phần tử để thêm phần tử, ở đây chúng ta sử dụng hàm SLL_Add_First. Giả sử chúng ta cần tạo danh sách liên kết đơn có N phần tử. 65
  66. - Thuật toán: B1: SLL_Initialize(SLList) B2: i = 1 B3: IF (i > N) Thực hiện Bkt B4: NewData = InputNewData() // Nhập giá trị cho biến NewData B5: SLL_Add_First(SLList, NewData) B6: i++ B7: Lặp lại B3 Bkt: Kết thúc - Cài đặt thuật toán: Hàm SLL_Create có prototype: SLL_Type SLL_Create(SLL_Type &SList, int N); Hàm tạo danh sách liên kết đơn có N nút quản lý bởi địa chỉ nút đầu tiên thông qua SList. Hàm trả về địa chỉ của nút đầu tiên trong danh sách nếu việc tạo thành công, ngược lại hàm trả về con trỏ NULL. Nội dung của hàm như sau: SLL_Type SLL_Create(SLL_Type &SList, int N) { SLL_Initialize(SList); T NewData; for (int i = 0; i < N; i++) { NewData = InputNewData(); if (SLL_Add_First(SList, NewData) == NULL) { SLL_Delete (SList); break; } } return (SList); } _ Lưu ý: Hàm InputNewData thực hiện việc nhập vào nội dung của một biến có kiểu dữ liệu 66
  67. T và trả về giá trị mới nhập vào. Tùy vào từng trường hợp cụ thể mà chúng ta viết hàm InputNewData cho phù hợp. 2.2.2.9. Tách một danh sách thành nhiều danh sách: Tương tự như danh sách đặc, việc tách một danh sách liên kết đơn thành nhiều danh sách liên kết đơn khác nhau cũng có nhiều tiêu thức khác nhau mà chúng ta sẽ thực hiện theo các cách khác nhau. Ngoài ra việc tách cũng sẽ khác nhau trong trường hợp có hay không giữ lại danh sách ban đầu. Ở đây chúng ta thực hiện việc tách các nút trong danh sách liên kết đơn SLList thành hai danh sách liên kết đơn con SLList và SLList1 luân phiên theo các đường chạy tự nhiên và không giữ lại danh sách liên kết ban đầu. Các trường hợp khác sinh viên tự vận dụng để thao tác. - Thuật toán: B1: CurNode = SLList B2: SLList1 = SLList B3: LastNode1 = NULL, LastNode2 = NULL // Cắt các nút từ sau đường chạy tự nhiên thứ nhất về SLList1 B4: IF (CurNode = NULL OR CurNode->NextNode = NULL) Thực hiện Bkt B5: IF (CurNode->Key > CurNode->NextNode->Key) B5.1: LastNode1 = CurNode B5.2: SLList1 = SLList1->NextNode B5.3: CurNode = CurNode->NextNode B5.4: LastNode1->NextNode = NULL B5.5: Thực hiện B8 B6: CurNode = CurNode->NextNode, SLList1 = SLList1->NextNode B7: Lặp lại B4 // Cắt các nút từ sau đường chạy tự nhiên thứ hai về SLList B8: IF (CurNode = NULL OR CurNode->NextNode = NULL) 67
  68. Thực hiện Bkt B9: IF (CurNode->Key > CurNode->NextNode->Key) B9.1: LastNode2 = CurNode B9.2: CurNode = CurNode->NextNode B9.3: LastNode2->NextNode = NULL B9.4: Thực hiện B12 B10: CurNode = CurNode->NextNode B11: Lặp lại B8 // Phân phối (giữ lại) đường chạy kế tiếp trong SLList B12: LastNode1->NextNode = CurNode B13: IF (CurNode = NULL OR CurNode->NextNode = NULL) Thực hiện Bkt B14: IF (CurNode->Key > CurNode->NextNode->Key) B14.1: LastNode1 = CurNode B14.2: CurNode = CurNode->NextNode B14.3: LastNode1->NextNode = NULL B14.4: Thực hiện B17 B15: CurNode = CurNode->NextNode B16: Lặp lại B13 // Phân phối (giữ lại) đường chạy kế tiếp trong SLList1 B17: LastNode2->NextNode = CurNode B18: IF (CurNode = NULL OR CurNode->NextNode = NULL) Thực hiện Bkt B19: IF (CurNode->Key > CurNode->NextNode->Key) B19.1: LastNode2 = CurNode B19.2: CurNode = CurNode->NextNode B19.3: LastNode2->NextNode = NULL B19.4: Lặp lại B12 B20: CurNode = CurNode->NextNode B21: Lặp lại B18 Bkt: Kết thúc 68
  69. - Cài đặt thuật toán: Hàm SLL_Split có prototype: SLL_Type SLL_Split(SLL_Type &SList, SLL_Type &SList1); Hàm thực hiện việc phân phối bớt các đường chạy tự nhiên trong SList sang SList1. Hàm trả về con trỏ trỏ tới địa chỉ phần tử đầu tiên trong SList1. Nội dung của hàm như sau: SLL_Type SLL_Split(SLL_Type &SList, SLL_Type &SList1) { SList1 = SList; if (SList1 == NULL) return (NULL); SLL_Type Last1; SLL_Type Last2; while (SList1->NextNode != NULL) { if (SList1->Key > SList1->NextNode->Key) break; SList1 = SList1->NextNode; } if (SList1->NextNode != NULL) Last1 = SList1; SList1 = SList1->NextNode; Last1->NextNode = NULL; SLL_Type CurNode = SList1; if (CurNode == NULL) return (NULL); while (CurNode->NextNode != NULL) { if (CurNode->Key > CurNode->NextNode->Key) break; CurNode = CurNode->NextNode; } if (CurNode->NextNode == NULL) return (SList1); 69
  70. Last2 = CurNode; CurNode = CurNode->NextNode; Last2->NextNode = NULL; while (CurNode != NULL) { Last1->NextNode = CurNode; if (CurNode->NextNode == NULL) break; while (CurNode->NextNode != NULL) { if (CurNode->Key > CurNode->NextNode->Key) break; Cur Node = CurNode->NextNode; } if (CurNode->NextNode == NULL) break; Last1 = CurNode; CurNode = CurNode->NextNode; Last1->NextNode = NULL; Last2->NextNode = CurNode; if (CurNode->NextNode == NULL) break; while (CurNode->NextNode != NULL) { if (CurNode->Key > CurNode->NextNode->Key) break; Cur Node = CurNode->NextNode; } if (CurNode->NextNode == NULL) break; Last2 = CurNode; CurNode = CurNode->NextNode; Last2->NextNode = NULL; } 70
  71. return (SList1); } 2.2.2.10. Nhập nhiều danh sách thành một danh sách: Tương tự, việc nhập nhiều danh sách thành một danh sách chúng ta thực hiện theo hai trường hợp khác nhau: + Ghép nối đuôi các danh sách lại với nhau; + Trộn xen lẫn các phần tử trong danh sách con vào thành một danh sách lớn theo một trật tự nhất định. Ngoài ra việc nhập có thể giữ lại các danh sách con ban đầu hoặc không giữ lại các danh sách con ban đầu. Ở đây chúng ta trình bày theo cách không giữ lại các danh sách con ban đầu và trình bày theo hai trường hợp: + Ghép nối đuôi hai danh sách lại với nhau; Trộn hai danh sách lại với nhau theo các đường chạy tự nhiên thành một danh sách có chiều dài lớn hơn. Giả sử chúng ta cần nhập hai danh sách SLList1, SLList2 lại với nhau. - Thuật toán ghép danh sách SLList2 vào sau SLList1: B1: IF (SLList1 = NULL) B1.1: SLList1 = SLList2 B1.2: Thực hiện Bkt B2: IF (SLList2 = NULL) Thực hiện Bkt // Lấy địa chỉ nút cuối cùng trong SLList1 B3: LastNode = SLList1 B4: IF (LastNode->NextNode = NULL) Thực hiện B7 B5: LastNode = LastNode->NextNode B6: Lặp lại B4 // Ghép SLList2 vào sau LastNode B7: LastNode->NextNode = SLList2 Bkt: Kết thúc - Thuật toán trộn danh sách SLList2 và SLList1 thành SLList theo các đường chạy 71
  72. tự nhiên: B1: IF (SLList1 = NULL) B1.1: SLList = SLList2 B1.2: Thực hiện Bkt B2: IF (SLList2 = NULL) B2.1: SLList = SLList1 B2.2: Thực hiện Bkt // Lấy nút có dữ liệu nhỏ hơn trong 2 nút đầu của 2 danh sách đưa về SLList B3: IF (SLList1->Key _ SLList2->Key) B3.1: TempNode = SLList1 B3.2: SLList1 = SLList1->NextNode B4: ELSE B4.1: TempNode = SLList2 B4.2: SLList2 = SLList2->NextNode B5: TempNode->NextNode = NULL B6: IF (SLList1 = NULL) B6.1: TempNode->NextNode = SLList2 B6.2: Thực hiện Bkt B7: IF (SLList2 = NULL) B7.1: TempNode->NextNode = SLList1 B7.2: Thực hiện Bkt B8: IF (SLList1->Key _ SLList2->Key) AND (TempNode->Key _ SLList1->Key) B8.1: MinNode = SLList1 B8.2: SLList1 = SLList1->NextNode B9: ELSE B9.1: MinNode = SLList2 B9.2: SLList2 = SLList2->NextNode B10: TempNode->NextNode = MinNode B11: MinNode->NextNode = NULL B12: TempNode = MinNode B13: Lặp lại B6 72
  73. Bkt: Kết thúc - Cài đặt: Các hàm nhập danh sách có prototype: SLL_Type SLL_Concat (SLL_Type &SList1, SLL_Type &SList2); SLL_Type SLL_Merge(SLL_Type &SList1, SLL_Type &SList2, SLL_Type &SList); Hàm thực hiện việc nhập các nút trong hai danh sách SList1, SList2 thành một danh sách theo thứ tự như hai thuật toán vừa trình bày. Hàm trả về địa chỉ của nút đầu của danh sách sau khi ghép. Nội dung của các hàm như sau: SLL_Type SLL_Concat (SLL_Type &SList1, SLL_Type &SList2) { if (SList1 == NULL) { SList1 = SList2; return (SList1); } if (SList2 == NULL) return (SList1); SLL_Type LastNode = SList1; while (LastNode->NextNode != NULL) LastNode = LastNode->NextNode; LastNode->NextNode = SList2; return (SList1); } //=== === SLL_Type SLL_Merge (SLL_Type &SList1, SLL_Type &SList2, SLL_Type &SList) { if (SList1 == NULL) { SList = SList2; return (SList); } if (SList2 == NULL) 73
  74. { SList = SList1; return (SList); } SLL_Type LastNode = NULL; SLL_Type TempNode; while (SList1 != NULL && SList2 != NULL) { if (SList1->Key Key) { TempNode = SList1; SList1 = SList1->NextNode; TempNode->NextNode = NULL; if (LastNode == NULL) SList = LastNode = TempNode; else { LastNode->NextNode = TempNode; LastNode = TempNode; } if (SList1 == NULL) break; if (SList1->Key Key) while (SList2 != NULL) { LastNode->Next = SList2; LastNode = LastNode->NextNode; SList2 = SList2->NextNode; LastNode->NextNode = NULL; if (SList2 == NULL || SList2->Key Key) break; } } else { TempNode = SList2; SList2 = SList2->NextNode; 74
  75. TempNode->NextNode = NULL; if (LastNode == NULL) SList = LastNode = TempNode; else { LastNode->NextNode = TempNode; LastNode = TempNode; } if (SList2 == NULL) break; if (SList2->Key Key) while (SList1 != NULL) { LastNode->Next = SList1; LastNode = LastNode->NextNode; SList1 = SList1->NextNode; LastNode->NextNode = NULL; if (SList1 == NULL || SList1->Key Key) break; } } } if (SList1 == NULL) LastNode->NextNode = SList2; else LastNode->NextNode = SList1; return (SList); } 2.2.2.11. Sắp xếp thứ tự các phần tử trong danh sách: Thao tác này chúng ta có thể vận dụng các thuật toán sắp xếp đã trình bày trong Chương 3 để sắp xếp dữ liệu trong danh sách liên kết đơn. Ở đây chúng ta chỉ trình bày sự vận dụng thuật toán trộn tự nhiên để sắp xếp. 75
  76. Cũng cần lưu ý rằng đối với thao tác hoán vị hai phần tử thì chúng ta có thể hoán vị hoàn toàn hai nút hoặc chỉ hoán vị phần dữ liệu. Tuy nhiên việc hoán vị hoàn toàn hai nút sẽ phức tạp hơn. - Thuật toán sắp xếp trộn tự nhiên: B1: IF (SLL_Split(SLList, TempList) = NULL) Thực hiện Bkt B2: SLL_Merge(SLList, TempList, SLList) B3: Lặp lại B1 Bkt: Kết thúc - Cài đặt: Hàm SLL_Natural_Merge_Sort có prototype: void SLL_Natural_Merge_Sort (SLL_Type &SList); Hàm thực hiện việc sắp xếp thành phần dữ liệu của các nút trong danh sách SList theo thứ tự tăng dựa trên thuật toán trộn tự nhiên vừa trình bày. Nội dung của hàm như sau: void SLL_Natural_Merge_Sort (SLL_Type &SList) { SLL_Type TempList = NULL, List = NULL; while (SLL_Split(SList, TempList) != NULL) { SLL_Merge(SList, TempList, List); SList = List; } return ; } xii. Sao chép một danh sách: Thực chất thao tác này là chúng ta tạo mới danh sách NewList bằng cách duyệt qua các nút của SLList để lấy thành phần dữ liệu rồi tạo thành một nút mới và bổ sung nút mới này vào cuối danh sách NewList. - Thuật toán: B1: NewList = NULL B2: CurNode = SLList B3: IF (CurNode = NULL) 76
  77. Thực hiện Bkt B4: SLL_Add_Last(NewList, CurNode->Key) B5: CurNode = CurNode->NextNode B6: Lặp lại B3 Bkt: Kết thúc - Cài đặt thuật toán: Hàm SLL_Copy có prototype: SLL_Type SLL_Copy (SLL_Type SList, SLL_Type &NewList); Hàm thực hiện việc sao chép nội dung danh sách SList thành danh sách NewList có cùng nội dung thành phần dữ liệu theo thứ tự của các nút trong SList. Hàm trả về địa chỉ nút đầu trong danh sách mới nếu việc sao chép thành công, ngược lại hàm trả về con trỏ NULL. Nội dung của hàm như sau: SLL_Type SLL_Copy (SLL_Type SList, SLL_Type &NewList) { NewList = NULL; SLL_Type CurNode = SList; while (CurNode != NULL) { SLL_Type NewNode = SLL_Add_Last(NewList, CurNode->Key); if (NewNode == NULL) { SLL_Delelte(NewList); break; } CurNode = CurNode->NextNode; } return (NewList); } 3. Lưu trữ móc nối đối với danh sách tuyến tính 3.1. Cấu trúc dữ liệu Nếu như vùng liên kết của danh sách liên kết đơn có 01 mối liên kết với 01 phần tử khác trong danh sách thì vùng liên kết trong danh sách liên đôi có 02 mối liên kết với 02 phần tử khác trong danh sách, cấu trúc dữ liệu của mỗi nút trong danh sách 77
  78. liên kết đôi như sau: typedef struct DLL_Node { T Key; InfoType Info; DLL_Node * NextNode; // Vùng liên kết quản lý địa chỉ phần tử kế tiếp nó DLL_Node * PreNode; // Vùng liên kết quản lý địa chỉ phần tử trước nó } DLL_OneNode; Ở đây chúng ta cũng giả thiết rằng vùng dữ liệu của mỗi phần tử trong danh sách liên kết đôi chỉ bao gồm một thành phần khóa nhận diện (Key) cho phần tử đó. Do vậy, cấu trúc dữ liệu trên có thể viết lại đơn giản như sau: typedef struct DLL_Node { T Key; DLL_Node * NextNode; // Vùng liên kết quản lý địa chỉ phần tử kế tiếp nó DLL_Node * PreNode; // Vùng liên kết quản lý địa chỉ phần tử trước nó } DLL_OneNode; typedef DLL_OneNode * DLL_Type; Có nhiều phương pháp khác nhau để quản lý các danh sách liên kết đôi và tương ứng với các phương pháp này sẽ có các cấu trúc dữ liệu khác nhau, cụ thể: - Quản lý địa chỉ phần tử đầu danh sách: Cách này hoàn toàn tương tự như đối với danh sách liên kết đơn. DLL_Type DLL_List1; Hình ảnh minh họa: DLL_List1 NULL 15 10 20 18 40 30 NULL - Quản lý địa chỉ phần tử đầu và cuối danh sách: typedef struct DLL_PairNode { DLL_Type DLL_First; DLL_Type DLL_Last; } DLLP_Type; DLLP_Type DLL_List2; 78
  79. Hình ảnh minh họa: DLL_List2 DLL_First DLL_Last NULL 15 10 20 18 40 30 NULL - Quản lý địa chỉ phần tử đầu, địa chỉ phần tử cuối và số phần tử trong danh sách: typedef struct DLL_PairNNode { DLL_Type DLL_First; DLL_Type DLL_Last; unsigned NumNode; } DLLPN_Type; DLLPN_Type DLL_List3; Hình ảnh minh họa: DLL_List3 DLL_First NumNode=6 DLL_Last NULL 15 10 20 18 40 30 NULL 3.2. Các thao tác trên danh sách Cũng như trong phần danh sách liên kết đơn, các thao tác tương ứng với mỗi cách quản lý khác nhau của danh sách liên kết đôi có sự khác nhau về mặt chi tiết song nội dung cơ bản ít có sự khác nhau. Do vậy, ở đây chúng ta chỉ trình bày các thao tác theo cách quản lý thứ hai (quản lý các địa chỉ của hai nút đầu và cuối danh sách liên kết đôi), các thao tác này trên các cách quản lý khác sinh viên tự vận dụng để điều chỉnh cho thích hợp. 3.2.1. Khởi tạo danh sách (Initialize): Trong thao tác này chỉ đơn giản là chúng ta cho giá trị các con trỏ quản lý địa chỉ hai nút đầu và cuối danh sách liên kết đôi về con trỏ NULL. Hàm khởi tạo danh sách liên kết đôi như sau: DLLP_Type DLL_Initialize(DLLP_Type &DList) 79
  80. { DList.DLL_First = NULL; DList.DLL_Last = NULL; return (DList); } Hình ảnh minh họa: DList NULL DLL_First DLL_Last NULL 3.2.2. Tạo mới một phần tử / nút: Giả sử chúng ta cần tạo mới một phần tử có thành phần dữ liệu là NewData. - Thuật toán: B1: DNode = new DLL_OneNode B2: IF (DNode = NULL) Thực hiện Bkt B3: DNode->NextNode = NULL B4: DNode->PreNode = NULL B5: DNode->Key = NewData Bkt: Kết thúc - Cài đặt thuật toán: Hàm DLL_Create_Node có prototype: DLL_Type DLL_Create_Node(T NewData); Hàm tạo mới một nút có thành phần dữ liệu là NewData, hàm trả về con trỏ trỏ tới địa chỉ của nút mới tạo. Nếu không đủ bộ nhớ để tạo, hàm trả về con trỏ NULL. DLL_Type DLL_Create_Node(T NewData) { DLL_Type Pnode = new DLL_OneNode; if (Pnode != NULL) { Pnode->NextNode = NULL; Pnode->PreNode = NULL; Pnode->Key = NewData; } return (Pnode); 80
  81. } - Minh họa thuật toán: Giả sử chúng ta cần tạo nút có thành phần dữ liệu là 20: NewData = 20 Pnode = new DLL_OneNode Pnode Pnode->NextNode = NULL Pnode->PreNode = NULL Pnode->Key = NewData Pnode NULL 20 NULL 3.2.3. Thêm một phần tử vào trong danh sách: Giả sử chúng ta cần thêm một phần tử có giá trị thành phần dữ liệu là NewData vào trong danh sách. Việc thêm có thể diễn ra ở đầu, cuối hay ở giữa danh sách liên kết. Do vậy, ở đây chúng ta trình bày 3 thao tác thêm riêng biệt nhau: - Thuật toán thêm phần tử vào đầu danh sách liên kết đôi: B1: NewNode = DLL_Create_Node (NewData) B2: IF (NewNode = NULL) Thực hiện Bkt B3: IF (DLL_List.DLL_First = NULL) // Danh sách rỗng B3.1: DLL_List.DLL_First = NewNode B3.2: DLL_List.DLL_Last = NewNode B3.3: Thực hiện Bkt B4: NewNode->NextNode = DLL_List.DLL_First // Nối DLL_First vào B5: DLL_List.DLL_First->PreNode = NewNode // sau NewNode // Chuyển vai trò đứng đầu của NewNode cho DLL_First B6: DLL_List.DLL_First = NewNode Bkt: Kết thúc - Minh họa thuật toán: 81
  82. Giả sử chúng ta cần thêm nút có thành phần dữ liệu là 27: NewData = 27 NewNode NULL 27 NULL DLL_List DLL_First DLL_Last NULL 16 20 18 40 30 NULL NewNode->NextNode = DLL_List.DLL_First: NewNode 27 NULL DLL_List DLL_First DLL_Last NULL 16 20 18 40 30 NULL DLL_List.DLL_First->PreNode = NewNode: NewNode 27 NULL DLL_List DLL_First DLL_Last NULL 16 20 18 40 30 DLL_List.DLL_First = NewNode: NewNode 27 NULL DLL_List 82
  83. DLL_First DLL_Last NULL 16 20 18 40 30 Kết quả sau khi chèn: DLL_List DLL_First DLL_Last NULL 27 16 20 18 40 30 NULL - Thuật toán thêm phần tử vào cuối danh sách liên kết đôi: B1: NewNode = DLL_Create_Node (NewData) B2: IF (NewNode = NULL) Thực hiện Bkt B3: IF (DLL_List.DLL_First = NULL) // Danh sách rỗng B3.1: DLL_List.DLL_First = NewNode B3.2: DLL_List.DLL_Last = NewNode B3.3: Thực hiện Bkt B4: DLL_List.DLL_Last->NextNode = NewNode // Nối NewNode vào B5: NewNode->PreNode = DLL_List.DLL_Last // sau DLL_Last // Chuyển vai trò đứng cuối của NewNode cho DLL_Last B6: DLL_List.DLL_Last = NewNode Bkt: Kết thúc - Minh họa thuật toán: Giả sử chúng ta cần thêm nút có thành phần dữ liệu là 25: NewData = 25 NewNode NULL 25 NULL DLL_List DLL_First DLL_Last NULL 16 20 18 40 30 83
  84. NULL DLL_List.DLL_Last->NextNode = NewNode: NewNode NULL 25 NULL DLL_List DLL_First DLL_Last 16 20 18 40 30 NULL NewNode->PreNode = DLL_List.DLL_Last NewNode NULL 25 DLL_List DLL_First DLL_Last 16 20 18 40 30 NULL DLL_List.DLL_Last = NewNode: NewNode NULL 25 DLL_List DLL_First DLL_Last 16 20 18 40 30 NULL Kết quả sau khi chèn: DLL_List DLL_First DLL_Last NULL 16 20 18 40 30 25 NULL - Thuật toán thêm phần tử vào giữa danh sách liên kết đôi: Giả sử chúng ta cần thêm một phần tử có giá trị thành phần dữ liệu là NewData 84
  85. vào trong danh sách DLL_List vào ngay sau nút có địa chỉ InsNode. Trong thực tế nhiều khi chúng ta phải thực hiện thao tác tìm kiếm để xác định địa chỉ InsNode, ở đây giả sử chúng ta đã xác định được địa chỉ này. B1: IF (InsNode->NextNode = NULL) // Thêm vào cuối DSLK B1.1: DLL_Add_Last (DLL_List, NewData) B1.2: Thực hiện Bkt B2: NewNode = DLL_Create_Node (NewData) B3: IF (NewNode = NULL) Thực hiện Bkt // Nối các nút kế sau InsNode vào sau NewNode B4: NewNode->NextNode = InsNode->NextNode B5: InsNode->NextNode->PreNode = NewNode // Chuyển mối liên kết giữa InsNode với nút kế của nó về NewNode B6: InsNode->NextNode = NewNode B7: NewNode->PreNode = InsNode Bkt: Kết thúc - Minh họa thuật toán: Giả sử chúng ta cần thêm nút có thành phần dữ liệu là 25 vào sau nút có địa chỉ InsNode như sau: NewData = 25 DLL_List DLL_First DLL_Last InsNode NULL 16 20 18 40 30 NULL NewNode NULL 25 NULL NewNode->NextNode = InsNode->NextNode: DLL_List DLL_First DLL_Last InsNode NULL 85
  86. 16 20 18 40 30 NULL NewNode 25 NULL InsNode->NextNode->PreNode = NewNode: DLL_List DLL_First DLL_Last InsNode NULL 16 20 18 40 30 NULL NewNode 25 NULL InsNode->NextNode = NewNode: DLL_List DLL_First DLL_Last InsNode NULL 16 20 18 40 30 NULL NewNode 25 NULL NewNode->PreNode = InsNode DLL_List DLL_First DLL_Last InsNode NULL 16 20 18 40 30 NULL NewNode 25 86
  87. Kết quả sau khi chèn: DLL_List DLL_First DLL_Last NULL 16 20 18 25 40 30 NULL - Cài đặt thuật toán: Các hàm thêm phần tử tương ứng với các trường hợp có prototype như sau: DLL_Type DLL_Add_First(DLLP_Type &DList, T NewData); DLL_Type DLL_Add_Last(DLLP_Type &DList, T NewData); DLL_Type DLL_Add_Mid(DLLP_Type &DList, T NewData, DLL_Type &InsNode); Hàm thực hiện việc chèn phần tử có giá trị thành phần dữ liệu NewData vào trong danh sách liên kết đôi quản lý bởi hai con trỏ đầu và cuối danh sách trong DList tương ứng với 3 trường hợp: Thêm đầu, thêm cuối, thêm giữa. Các hàm trả về giá trị là một địa chỉ của nút vừa mới thêm nếu việc thêm thành công. Trong trường hợp ngược lại, các hàm trả về con trỏ NULL. Riêng đối với trường hợp thêm giữa, hàm DLL_Add_Mid thực hiện việc thêm vào ngay sau nút có địa chỉ InsNode. Nội dung của các hàm như sau: DLL_Type DLL_Add_First(DLLP_Type &DList, T NewData) { DLL_Type NewNode = DLL_Create_Node(NewData); if (NewNode == NULL) return (NULL); if (DList.DLL_First == NULL) DList.DLL_First = DList.DLL_Last = NewNode; else { NewNode->NextNode = DList.DLL_First; DList.DLL_First->PreNode = NewNode; DList.DLL_First = NewNode; } return (NewNode); 87
  88. } //=== === DLL_Type DLL_Add_Last(DLLP_Type &DList, T NewData) { DLL_Type NewNode = DLL_Create_Node(NewData); if (NewNode == NULL) return (NULL); if (DList.DLL_Last == NULL) DList.DLL_First = DList.DLL_Last = NewNode; else { DList.DLL_Last->NextNode = NewNode; NewNode->PreNode = DList.DLL_Last; DList.DLL_Last = NewNode; } return (NewNode); } //=== === DLL_Type DLL_Add_Mid(DLLP_Type &DList, T NewData, DLL_Type &InsNode) { DLL_Type NewNode = DLL_Create_Node(NewData); if (NewNode == NULL) return (NULL); if (InsNode->NextNode == NULL) { InsNode->NextNode = NewNode; NewNode->PreNode = InsNode; DList.DLL_Last = NewNode; } else { NewNode->NextNode = InsNode->NextNode; InsNode->NextNode->PreNode = NewNode; 88
  89. InsNode->NextNode = NewNode; NewNode->PreNode = InsNode; } return (NewNode); } 3.2.4. Duyệt qua các nút trong danh sách: Thao tác này nhằm nhiều mục đích, ở đây đơn giản chúng ta chỉ duyệt để xem nội dung thành phần dữ liệu trong danh sách. Thuật toán này hoàn toàn tương tự như trong danh sách liên kết đơn. - Thuật toán: B1: CurNode = DLL_List.First B2: IF (CurNode = NULL) Thực hiện Bkt B3: OutputData(CurNode->Key) // Xuất giá trị thành phần dữ liệu trong 1 nút B4: CurNode = CurNode->NextNode B5: Lặp lại B2 Bkt: Kết thúc - Cài đặt thuật toán: Hàm DLL_Travelling có prototype: void DLL_Travelling(DLLP_Type DList); Hàm duyệt qua các nút trong danh sách liên kết đôi quản lý bởi hai địa chỉ nút đầu tiên và nút cuối cùng thông qua DList để xem nội dung thành phần dữ liệu của mỗi nút. Nội dung của hàm như sau: void DLL_Travelling (DLLP_Type DList) { DLL_Type CurNode = DList.DLL_First; while (CurNode != NULL) { OutputData(CurNode->Key); CurNode = CurNode->NextNode; } return; 89