Tài liệu Cấu trúc dữ liệu và giải thuật

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC MỞ HÀ NỘI CẤU TRÚC DỮ LIỆU & GIẢI THUẬT Chủ biên: Trương Tiến Tùng Đồng tác giả: Nguyễn Thị Tâm - Trịnh Thị Xuân HÀ NỘI 6/2021 Cấu trúc dữ liệu và giải thuật BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC MỞ HÀ NỘI CẤU TRÚC DỮ LIỆU & GIẢI THUẬT Trương Tiến Tùng Nguyễn Thị Tâm - Trịnh Thị Xuân HÀ NỘI 6/2021 2 Cấu trúc dữ liệu và giải thuật DANH SÁCH THÀNH VIÊN TT 1 HỌ VÀ TÊN PHÂN CÔNG NHIỆM VỤ Trương Tiến Tùng -Thống nhất nội dung giáo trình (Chủ biên) -Phân công các thành viên thực hiện -Hoàn thiện các nội dung chung và tổng quát của giáo trình -Rà soát và phản biện toàn bộ nội dung giáo trình 2 Nguyễn Thị Tâm -Hoàn thiện nội dung Chương 1, Chương 2, (Đồng tác giả) Chương 3 -Rà soát phản biển Chương 4, Chương 5, Chương 6 3 Trịnh Thị Xuân -Hoàn thiện nội dung Chương 4, Chương 5, (Đồng tác giả) Chương 6 -Rà soát phản biển Chương 1, Chương 2, Chương 3 3 Cấu trúc dữ liệu và giải thuật LỜI NÓI ĐẦU Để đáp ứng nhu cầu học tập của các bạn sinh viên đặc biệt là sinh viên chuyên ngành Công nghệ thông tin, Khoa Công nghệ thông tin Trường Đại học Mở Hà Nội, chúng tôi đã biên soạn giáo trình, bài giảng của chương trình đào tạo theo hệ thống tín chỉ. Bài giảng môn Cấu trúc dữ liệu và thuật toán này được biên soạn dựa trên quyển "Cấu trúc dữ liệu và thuật toán" của tác giả Đinh Mạnh Tường, Nhà xuất bản Khoa học và Kỹ thuật và quyển "Algorithms + Data Structure = Program" của Nicklaus Wirth, Bản dịch tiếng Việt, Nhà xuất bản Khoa học và Kỹ thuật, 1993. Giáo trình này cũng được biên soạn dựa trên kinh nghiệm giảng dạy nhiều năm môn Cấu trúc dữ liệu và Giải thuật của chúng tôi. Giáo trình được biên soạn theo đề cương chi tiết môn Cấu trúc dữ liệu và Giải thuật của sinh viên chuyên ngành Công nghệ thông tin Khoa Công nghệ Thông tin Trường Đại học Mở Hà Nội. Mục tiêu nhằm giúp các bạn sinh viên có một tài liệu dùng làm tài liệu học tập song các đối tượng khác cũng có thể tham khảo. Chúng tôi cho rằng các bạn sinh viên không chuyên tin và những người quan tâm tới cấu trúc dữ liệu và giải thuật sẽ tìm được nhiều điều bổ ích. Mặc dù đã rất cố gắng trong quá trình biên soạn giáo trình nhưng chắc chán giáo trình sẽ còn nhiều thiếu sót và hạn chế. Nhóm tác giả rất mong nhận được sự đóng góp ý kiến của các bạn sinh viên và người đọc để giáo trình ngày một hoàn thiện hơn. Hà Nội, tháng 6 năm 2021 Nhóm tác giả Trương Tiến Tùng Nguyễn Thị Tâm Trịnh Thị Xuân 4 Cấu trúc dữ liệu và giải thuật MỤC LỤC Chương 1. CÁC KHÁI NIỆM CƠ BẢN................................................... 15 1.1 Các khái niệm cơ bản..........................................................................15 1.2 Các bước phân tích thuật toán............................................................ 20 1.3 Biểu diễn giải thuật............................................................................. 21 1.3.1 Ngôn ngữ tự nhiên – liệt kê theo bước........................................ 22 1.3.2 Sơ đồ khối.................................................................................... 22 1.3.3 Mã giả...........................................................................................26 1.4 Phân tích – Đánh giá giải thuật...........................................................27 1.4.1 Độ phức tạp không gian...............................................................28 1.4.2 Độ phức tạp thời gian...................................................................28 1.4.3 Ước lượng thời gian thực hiện chương trình...............................29 1.4.4 Nguyên tắc tính toán thời gian chạy thực hiện chương trình......30 1.5 Độ phức tạp tính toán với tình trạng dữ liệu vào................................32 1.6 Phân lớp bài toán.................................................................................33 1.7 Đệ quy................................................................................................. 35 1.7.1 Giới thiệu......................................................................................35 1.7.2 Giải thuật đệ quy.......................................................................... 35 1.7.3 Ví dụ minh họa.............................................................................36 1.8 Tổng kết chương và câu hỏi ôn tập.....................................................39 1.8.1 Tổng kết chương.......................................................................... 39 1.8.2 Câu hỏi ôn tập.............................................................................. 40 1.9 Bài tập áp dụng....................................................................................40 Chương 2. DANH SÁCH...........................................................................44 2.1 Danh sách............................................................................................ 44 2.1.1 Khái niệm..................................................................................... 44 2.1.2 Các phép toán trên danh sách...................................................... 45 2.2 Cài đặt danh sách bằng mảng............................................................. 46 2.2.1 Cài đặt........................................................................................46 2.2.2 Bài toán tìm kiếm trên danh sách..............................................49 5 Cấu trúc dữ liệu và giải thuật 2.2.3 Bài toán sắp xếp trên danh sách................................................53 2.3 Cài đặt danh sách bằng danh sách liên kết......................................... 71 2.3.1 Khái niệm..................................................................................... 71 2.3.2 Các phép toán trên danh sách liên kết......................................... 73 2.3.3 So sánh cài đặt danh sách theo hai phương pháp........................ 83 2.3.4 Các dạng danh sách liên kết khác................................................84 2.4 Bài tập có hướng dẫn.......................................................................... 85 2.5 Tổng kết chương................................................................................. 89 2.6 Câu hỏi trắc nghiệm............................................................................ 90 2.7 Câu hỏi và bài tập..............................................................................103 Chương 3. NGĂN XẾP – HÀNG ĐỢI....................................................106 3.1 Ngăn xếp - Stack............................................................................... 106 3.1.1 Khái niệm................................................................................... 106 3.1.2 Cài đặt bằng mảng..................................................................... 107 3.1.3 Cài đặt bằng danh sách liên kết................................................. 110 3.1.4 Ứng dụng của ngăn xếp.......................................................... 113 3.2 Hàng đợi – Queue............................................................................. 115 3.2.1 Khái niệm................................................................................... 115 3.2.2 Cài đặt bằng mảng..................................................................... 116 3.2.3 Cài đặt hàng đợi bằng danh sách liên kết.................................. 118 3.2.4 Ứng dụng hàng đợi để biểu diễn đa thức...................................120 3.3 Tổng kết chương............................................................................... 121 3.4 Bài tập................................................................................................122 Chương 4. HÀM BĂM – BẢNG BĂM...................................................123 4.1 Khái niệm hàm băm – phép băm...................................................... 123 4.2 Các loại hàm băm..............................................................................124 4.2.1 Hàm băm sử dụng phương pháp chia........................................ 124 4.2.2 Hàm băm sử dụng phương pháp nhân.......................................124 4.2.3 Hàm băm sử dụng phương pháp trích....................................... 125 4.2.4 Hàm băm sử dụng phương tách.................................................125 6 Cấu trúc dữ liệu và giải thuật 4.2.5 Hàm băm sử dụng phương gập..................................................126 4.3 Bảng băm...........................................................................................126 4.3.1 Giới thiệu....................................................................................126 4.3.2 Các bảng băm cơ bản................................................................. 127 4.4 Ứng dụng hàm băm...........................................................................133 4.5 Tổng kết chương và câu hỏi ôn tập...................................................135 4.5.1 Tổng kết chương........................................................................ 135 4.5.2 Câu hỏi ôn tập............................................................................ 135 4.6 Một số câu hỏi trắc nghiệm ôn tập....................................................136 4.7 Bài tập áp dụng..................................................................................138 Chương 5. DANH SÁCH PHI TUYẾN DẠNG CÂY - TREE...............139 5.1 Các khái niệm – Định nghĩa............................................................. 139 5.2 Cài đặt cây.........................................................................................144 5.2.1 Cài đặt cây bằng danh sách kế tiếp – mảng các nút cha........... 144 5.2.2 Lưu trữ móc nối – danh sách các nút con..................................148 5.3 Cây nhị phân – cây nhị phân tìm kiếm............................................. 150 5.4 Lưu trữ cây nhị phân......................................................................... 152 5.4.1 Lưu trữ kế tiếp dưới dạng mảng................................................ 152 5.4.2 Lưu trữ móc nối......................................................................... 156 5.5 Biểu diễn cây tổng quát bằng cây nhị phân......................................157 5.6 Các thao tác trên cây nhị phân tìm kiếm.......................................... 158 5.6.1 Các phép duyệt cây.................................................................... 158 5.6.2 Tìm kiếm trên cây nhị phân tìm kiếm....................................... 161 5.6.3 Chèn thêm phần tử vào cây........................................................163 5.6.4 Xóa phần tử khỏi cây................................................................. 169 5.7 Cây biểu thức.................................................................................... 171 5.7.1 Định nghĩa và các cách biểu diễn biểu thức..............................171 5.7.2 Chuyển từ biểu thức sang ký pháp Balan đảo ngược................174 5.7.3 Xây dựng cây nhị phân biểu thức.............................................. 175 5.7.4 Tính giá trị của biểu thức...........................................................185 7 Cấu trúc dữ liệu và giải thuật 5.8 Bài toán áp dụng............................................................................... 188 5.8.1 Sắp xếp danh sách theo phương pháp vun đống – Heap Sort...188 5.8.2 Cây 2-3-4....................................................................................196 5.9 Ví dụ tổng hợp...................................................................................197 5.10 Tổng kết chương và câu hỏi ôn tập.................................................201 5.10.1 Tổng kết chương...................................................................... 201 5.10.2 Câu hỏi ôn tập.......................................................................... 202 5.11 Một số câu hỏi trắc nghiệm ôn tập................................................. 202 5.12 Bài tập áp dụng............................................................................... 212 5.13 Bài tập có hướng dẫn...................................................................... 215 Chương 6. ĐỒ THỊ - GRAPH..................................................................225 6.1 Các khái niệm – Định nghĩa............................................................. 225 6.1.1 Giới thiệu....................................................................................225 6.1.2 Các định nghĩa cơ bản................................................................226 6.1.3 Các thuật ngữ cơ bản................................................................. 229 6.2 Lưu trữ đồ thị.................................................................................... 230 6.2.1 Lưu trữ đồ thị bằng ma trận kề - Ma trận trọng số....................230 6.2.2 Lưu trữ đồ thị bằng danh sách đỉnh kề...................................... 234 6.2.3 Lưu trữ đồ thị bằng danh sách cạnh.......................................... 235 6.3 Các phép duyệt đồ thị và ứng dụng.................................................. 236 6.3.1 Duyệt theo chiều sâu..................................................................236 6.3.2 Duyệt theo chiều rộng................................................................237 6.4 Một số bài toán trên đồ thị................................................................ 238 6.4.1 Tìm đường đi ngắn nhất và ứng dụng....................................... 238 6.4.2 Tìm cây khung nhỏ nhất và ứng dụng....................................... 244 6.4.3 Tìm chu trình..............................................................................256 6.4.4 Sắp xếp Tôpô............................................................................. 259 6.5 Tổng kết chương và câu hỏi ôn tập...................................................264 6.5.1 Tổng kết chương........................................................................ 264 6.5.2 Câu hỏi ôn tập............................................................................ 264 8 Cấu trúc dữ liệu và giải thuật 6.6 Một số câu hỏi trắc nghiệm ôn tập....................................................264 6.7 Bài tập áp dụng..................................................................................270 6.8 Bài tập có hướng dẫn:....................................................................... 274 9 Cấu trúc dữ liệu và giải thuật DANH MỤC HÌNH VẼ Hình 2.1 Minh họa thêm phần tử mới vào đầu danh sách............................74 Hình 2.2 Chèn thêm phần tử mới vào cuối danh sách..................................75 Hình 2.3 Chèn thêm phần tử mới vào sau phần tử q xác định..................... 77 Hình 2.4 Minh họa xóa phần tử đầu danh sách............................................ 78 Hình 2.5 Minh họa xóa phần tử đứng sau phần tử q xác định..................... 79 Hình 2.6 Danh sách liên kết vòng đơn..........................................................84 Hình 2.7 Danh sách liên kết vòng đôi...........................................................85 Hình 3.1 Minh họa sử dụng danh sách liên kết cài đặt cho ngăn xếp........110 Hình 3.2 Minh họa thao tác Push để bổ sung phần tử vào Stack...............111 Hình 3.3 Minh họa thao tác Pop để lấy phần tử khỏi Stack.......................112 Hình 3.4 Minh họa chuyển sang cơ số 8.....................................................114 Hình 3.5 Minh họa hàng đợi Queue............................................................116 Hình 3.6 Minh họa tính tổng hai đa thức....................................................121 Hình 4.1 Hàm băm...................................................................................... 123 Hình 4.2 Bảng băm..................................................................................... 126 Hình 5.1 Sơ đồ tổ chức trường đại học.......................................................140 Hình 5.2 Sơ đồ tổ chức cây thư mục trong máy tính..................................140 Hình 5.3 Minh họa cây tổng quát bằng danh sách con móc nối................ 149 Hình 5.4 Sơ đồ cấu trúc một nút................................................................. 156 Hình 5.5 Kết quả chuyển từ cây tổng quát sang cây nhị phân................... 158 Hình 5.6 Minh họa tìm kiếm phần tử trên cây NPTK................................ 162 Hình 5.7 Minh họa thêm phần tử vào cây NPTK.......................................164 Hình 5.8 Minh họa xóa nút lá khỏi cây NPTK...........................................169 Hình 5.9 Minh họa xóa nút có một nhánh con........................................... 170 Hình 5.10 Minh họa xóa nút có 2 nhánh con..............................................171 Hình 5.11 Cây biểu thức (6/2 + 3) * (7 - 4)................................................172 Hình 5.12 Nguyên tắc thực hiện tính toán của máy tính............................185 Hình 6.1 Đồ thị có hướng........................................................................... 226 Hình 6.2 Đồ thị vô hướng........................................................................... 226 10 Cấu trúc dữ liệu và giải thuật Hình 6.3 Đơn đồ thị vô hướng.................................................................... 227 Hình 6.4 Đa đồ thị vô hướng...................................................................... 227 Hình 6.5 Giả đồ thị......................................................................................228 Hình 6.6 Đơn đồ thị có hướng.................................................................... 228 Hình 6.7 Đa đồ thị có hướng.......................................................................229 Hình 6.8 Danh sách đỉnh kề lưu trữ đồ thị................................................. 235 Hình 6.9 Danh sách cạnh lưu trữ đồ thị......................................................236 Hình 6.10 Minh họa đồ thị Euler (H1, H2, H3)......................................... 257 Hình 6.11 Minh họa đồ thị Hamilton (G1, G2, G3)...................................258 Hình 6.12 Đồ thị minh họa sắp xếp Tôpô...................................................263 11 Cấu trúc dữ liệu và giải thuật DANH MỤC TỪ VIẾT TẮT Từ viết tắt Viết đầy đủ CTDL Cấu trúc dữ liệu NPTK Nhị phân tìm kiếm NLR Node Left Right LNR Left Node Right LRN Left Right Node NRL Node Right Left RNL Right Node Left RLN Right Left Node Ý nghĩa 12 Cấu trúc dữ liệu và giải thuật PHẦN TỔNG QUAN Mục đích yêu cầu Môn học Cấu trúc dữ liệu và giải thuật cung cấp cho sinh viên một khối lượng lớn các kiến thức cơ bản về các cấu trúc dữ liệu và các phép toán trên từng cấu trúc đó. Sau khi học xong môn này, sinh viên cần phải: - Nắm vững khái niệm kiểu dữ liệu, kiểu dữ liệu trừu tượng, mô hình dữ liệu, giải thuật và cấu trúc dữ liệu. - Nắm vững và cài đặt được các mô hình dữ liệu, kiểu dữ liệu trừu tượng cơ bản như danh sách, ngăn xếp, hàng đợi, cây, tập hợp, bảng băm, đồ thị bằng một ngôn ngữ lập trình căn bản. - Vận dụng được các kiểu dữ liệu trừu tượng, các mô hình dữ liệu để giải quyết bài toán đơn giản trong thực tế. 
 Đối tượng sử dụng Môn học Cấu trúc dữ liệu và giải thuật được dùng để giảng dạy cho các sinh viên ngành công nghệ thông tin (môn bắt buộc) Nội dung chính Nội dung giáo trình gồm 6 chương và được trình bày trong 60 tiết cho sinh viên bao gồm lý thuyết và bài tập mà giáo viên sẽ hướng dẫn cho sinh viên trên lớp. Nội dung giáo trình chú trọng trình bày về các cấu trúc dữ liệu và các giải thuật trên các cấu trúc dữ liệu đó. Chương 1: Chương này tập trung trình bày các khái niệm về giải thuật và phương pháp biểu diễn giải thuật hiện nay. Chương này cũng nêu phương pháp phân tích và đánh giá một thuật toán, các khái niệm liên quan đến việc tính toán thời gian thực hiện của một chương trình. Chương 2: Trình bày mô hình dữ liệu danh sách, các cấu trúc dữ liệu để cài đặt danh sách, chúng tôi tập trung trình bày cấu trúc danh sách liên kết đơn cho những bài toán cần duyệt danh sách. Chương này cũng trình bày các cài đặt chi tiết để các bạn sinh viên có thể tiếp cận thực hành. 13 Cấu trúc dữ liệu và giải thuật Chương 3: Chương này trình bày hai dạng danh sách đặc biệt là Ngăn xếp và Hàng đợi. Chúng tôi cũng trình bày một số bài toán ứng dụng ngăn xếp và hàng đợi trong thực tế. Chương 4: Chương này chúng tôi tập trung trình bày về kiểu dữ liệu trừu tượng tập hợp đặc biệt là bảng băm, hàm băm. Trình bày về các loại hàm băm và bảng băm cơ bản. Chương 5: Chương này giới thiệu về kiểu dữ liệu trừu tượng cây, khái niệm cây tổng quát, các phép duyệt cây và cài đặt cây. Kế đến chúng tôi trình bày về cây nhị phân, các cách cài đặt cây nhị phân và ứng dụng cây nhị phân. Cuối cùng, chúng tôi trình bày cây tìm kiếm nhị phân như là một ứng dụng của cây nhị phân để lưu trữ và tìm kiếm dữ liệu. Chương 6: Chương này trình bày mô hình dữ liệu đồ thị, các cách biểu diễn đồ thị. Ơ đây chúng tôi cũng trình bày các phép duyệt đồ thị bao gồm duyệt theo chiều rộng và duyệt theo chiều sâu và đề cập một số bài toán thường gặp trên đồ thị như là bài toán tìm đường đi ngắn nhất, bài toán tìm cây khung tối thiểu. Do hạn chế về thời lượng lên lớp nên chương này chúng tôi chỉ giới thiệu để sinh viên tham khảo thêm về cách cài đặt đồ thị và các bài toán trên đồ thị. Kiến thức tiên quyết Để học tốt môn học Cấu trúc dữ liệu và giải thuật này, sinh viên cần có các kiến thức cơ bản: Kiến thức và kỹ năng lập trình cơ bản 14 Cấu trúc dữ liệu và giải thuật Chương 1. CÁC KHÁI NIỆM CƠ BẢN Trong chương này tập trung trình bày các khái niệm về giải thuật và phương pháp biểu diễn giải thuật hiện nay. Chương này cũng nêu phương pháp phân tích và đánh giá một thuật toán, các khái niệm liên quan đến việc tính toán thời gian thực hiện của một chương trình. 1.1 Các khái niệm cơ bản Xây dựng một đề án tin học thực chất là chuyển bài toán thực tế thành một bài toán có thể giải quyết trên máy tính. Mà một bài toán thực tế bất kỳ đều bao gồm các đối tượng dữ liệu và các yêu cầu xử lý trên các đối tượng đó. Như vậy, để xây dựng một mô hình tin học phản ánh được bài toán thực tế cần chú trọng đến hai vấn đề: *Tổ chức biểu diễn các đối tượng thực tế: Các đối tượng dữ liệu thực tế rất đa dạng, phong phú và thường chứa đựng những quan hệ nào đó với nhau, do đó trong mô hình tin học của bài toán, cần phải tổ chức, xây dựng các cấu trúc thích hợp sao cho vừa có thể phản ánh chính xác các dữ liệu thực tế đó, vừa có thể dễ dàng dùng máy tính để xử lý. Công việc này được gọi là xây dựng cấu trúc dữ liệu cho bài toán. *Xây dựng các thao tác xử lý dữ liệu: Từ những yêu cầu xử lý thực tế, cần tìm ra các giải thuật tương ứng để xác định trình tự các thao tác máy tính phải tác động lên dữ liệu để cho ra kết quả mong muốn, đây là bước xây dựng giải thuật cho bài toán. Trên thực tế khi giải quyết một bài toán trên máy tính chúng ta thường có khuynh hướng chỉ chú trọng đến việc xây dựng giải thuật mà quên đi tầm quan trọng của việc tổ chức dữ liệu trong bài toán. Cần nhớ rằng: Giải thuật phản ánh các phép xử lý, còn đối tượng xử lý của giải thuật lại là dữ liệu, chính dữ liệu chứa đựng các thông tin cần thiết để thực hiện giải thuật. Vì vậy để xác định được giải thuật phù hợp cần phải biết nó tác động đến 15 Cấu trúc dữ liệu và giải thuật loại dữ liệu nào (ví dụ để làm nhuyễn các hạt đậu, người ta dùng cách xay chứ không băm bằng dao, vì đậu sẽ văng ra ngoài và sẽ mất thời gian hơn nhiều) và khi chọn lựa cấu trúc dữ liệu cũng cần phải hiểu rõ những thao tác nào sẽ tác động đến nó (ví dụ để biểu diễn điểm số của sinh viên người ta dùng số thực thay vì chuỗi ký tự vì còn phải thực hiện thao tác tính trung bình từ những điểm số đó). Như vậy trong một đề án tin học, giải thuật và cấu trúc dữ liệu có mối quan hệ với nhau. Với một cấu trúc dữ liệu đã chọn, sẽ có những giải thuật tương ứng, phù hợp. Khi cấu trúc dữ liệu thay đổi thường giải thuật cũng phải thay đổi theo để tránh việc xử lý gượng ép, thiếu tự nhiên trên một cấu trúc không phù hợp. Hơn nữa, một cấu trúc dữ liệu tốt sẽ giúp giải thuật xử lý trên đó có thể phát huy tác dụng tốt hơn, vừa đáp ứng nhanh vừa tiết kiệm tài nguyên, đồng thời giải thuật cũng dễ hiểu và đơn giản hơn. Ví dụ 1.1 Một chương trình quản lý điểm thi của sinh viên cần lưu trữ các điểm số của 4 sinh viên. Do mỗi sinh viên có 3 điểm số ứng với 3 môn học khác nhau nên dữ liệu có dạng bảng như sau: Sinh viên Môn 1 Môn 2 Môn 3 SV1 8 6 4 SV2 9 5 3 SV3 6 7 2 SV4 5 6 5 Chỉ xét thao tác xử lý là xuất điểm số các môn học của từng sinh viên. Giả sử có các phương án tổ chức lưu trữ sau: Phương án 1: Sử dụng mảng một chiều Có tất cả 4(Sv) x 4(môn) = 12 điểm số cần lưu trữ, do đó khai báo mảng diem như sau: 16 Cấu trúc dữ liệu và giải thuật int diem [12] = { 8 6 4 9 5 3 6 7 2 5 6 5 }; Khi đó trong mảng diem các phần tử sẽ được lưu trữ như sau: Và truy xuất điểm số môn j của sinh viên i – (là phần tử tại dòng i, cột j trong bảng) - phải sử dụng một công thức xác địnhS chỉ số tương ứng trong mảng diem: bảngđiểm(dòng i, cột j) tương đương với diem[((i-1)*số cột) +j] Ngược lại, với một phần tử bất kỳ trong mảng, muốn biết đó là điểm số của sinh viên nào, môn gì, phải dùng công thức xác định như sau: diem[i] tương đương với diem[((i-1)*số cột) + j] Ơ phương án này, thao tác xử lý được cài đặt như sau: void indiem( ) { const int somon = 3; int sv, mon; for (int i=0; i<12; i++) { sv = i/somon; mon = i % somon; printf(“Mon %d SV %d la: %d “, mon, sv, diem[i]); } } Phương án 2: Sử dụng mảng hai chiều Khai báo mảng 2 chiều diem có kích thước 3 cột * 4 dòng như sau: int diem [12] = { {8 6 4}, {9 5 3}, 17 Cấu trúc dữ liệu và giải thuật {6 7 2}, {5 6 5} }; Khi đó trong mảng diem các phần tử sẽ được lưu trữ như sau: Cột 0 Cột 1 Cột 2 Dòng 0 diem[0][0]=8 diem[0][1]=6 diem[0][2]=4 Dòng 1 diem[1][0]=9 diem[1][1]=5 diem[1][2]=3 Dòng 2 diem[2][0]=6 diem[2][1]=7 diem[2][2]=2 Dòng 3 diem[3][0]=5 diem[3][1]=6 diem[3][2]=5 Như vậy truy xuất điểm số môn j của sinh viên i là phần tử tại dòng i cột j trong bảng – cũng chính là phần tử nằm ở vị trí dòng i cột j trong mảng: bảngđiểm(dòng i, cột j) tương đương với diem[i][j] Ơ phương án này, thao tác xử lý được cài đặt như sau: void indiem( ) { int somon = 3, sosv = 4; for (int i=0; i - Xem thêm -