ỦY BAN NHÂN DÂN TỈNH AN GIANG TRƯỜNG CAO ĐẲNG NGHỀ AN GIANG GIÁO TRÌNH Cấu trúc dữ liệu và giải thuật NGHỀ LẬP TRÌNH MÁY TÍNH & TIN ỨNG DỤNG TRÌNH ĐỘ CAO ĐẲNG NGHỀ & TRUNG CẤP NGHỀ (Ban hành theo Quyết định số: /QĐ-CĐN ngày tháng năm 20 của Hiệu trưởng trường Cao đẳng nghề An Giang) Tên tác giả : Trần Thị Kim Ngọc Năm ban hành: 2018 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. 1 LỜI GIỚI THIỆU Bài giảng cấu trúc dữ liệu và giải thuật đƣợc viết nhằm để giảng dạy cho sinh viên chuyên ngành CNTT trƣờng Cao Đẳng Nghề An giang. Bài giảng đƣợc thiết kế theo chƣơng trình môn học cấu trúc dữ liệu và giải thuật của Bộ ban hành. Bài giảng này bao gồm 4 chƣơng, nội dung các chƣơng đƣợc trình bày các cấu trúc dữ liệu và các giải thuật đơn giản nhất của tin học. Trƣớc tiên bài giảng trình bày về các cấu trúc dữ liệu cơ bản nhƣ: mảng, con trỏ, cấu trúc, tập tin; tiếp theo là các cấu trúc dữ liệu nâng cao nhƣ: danh sách, ngăn xếp, hàng đợi và một số ứng dụng của danh sách. Sau đó bài giảng trình bày tiếp về giải thuật sắp xếp và tìm kiếm, với các phƣơng pháp sắp xếp: xen, chọn, nổi bọt, quick sort và tìm kiếm nhƣ: tuần tự và nhị phân. Thêm vào đó, cuối chƣơng sẽ có các bài tập tƣơng ứng để sinh viên có thể ôn lại lý thuyết và tùy vào mỗi chƣơng mà có một số bài tập nâng cao để khuyến khích sinh viên tự học và nghiên cứu. Cuốn tài liệu giảng dạy này vẫn còn nhiều thiếu sót và hạn chế. Rất mong nhận đƣợc ý kiến đóng góp của sinh viên và các bạn đọc để bài giảng ngày càng hoàn thiện hơn. Chân thành cảm ơn quý Thầy Cô trong Hội đồng thẩm định của trƣờng Cao Đẳng Nghề An Giang để bài giảng Cấu trúc dữ liệu và giải thuật đƣợc hoàn chỉnh. An Giang, ngày tháng năm 2018 Tham gia biên soạn Trần Thị Kim Ngọc 2 MỤC LỤC TUYÊN BỐ BẢN QUYỀN . 1 LỜI GIỚI THIỆU . 3 GIÁO TRÌNH MÔN HỌC CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT . 6 CHƢƠNG 1: GIỚI THIỆU CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT . MỐI LIÊN HỆ GIẢI THUẬT VÀ CẤU TRÚC DỮ LIỆU . ĐÁNH GIÁ ĐỘ PHỨC TẠP CỦA GIẢI THUẬT . Sự cần thiết phải phân tích giải thuật: . Thời gian thực hiện của giải thuật:. Thời gian thực hiện chƣơng trình: . Đơn vị đo thời gian thực hiện . Thời gian thực hiện trong trƣờng hợp xấu nhất: . Tỷ suất tăng và độ phức tạp của giải thuật . Tỷ suất tăng: . Khái niệm độ phức tạp của giải thuật . Cách tính độ phức tạp: . Qui tắc cộng: . Qui tắc nhân: . Qui tắc tổng quát để phân tích một chƣơng trình: . Độ phức tạp của chƣơng trình có gọi chƣơng trình con không đệ quy: 13 5. Phân tích các chƣơng trình đệ quy: . Thành lập phƣơng trình đệ quy: . Giải phƣơng trình đệ quy: . 20 CHƢƠNG 2: CÁC KIỂU DỮ LIỆU NÂNG CAO . Mảng nhiều chiều: . Cấp phát tĩnh, cấp phát động và con trỏ . Sự cài đặt: . Định nghĩa kiểu cấu trúc: . Khai báo biến cấu trúc:. 28 CHƢƠNG 3: DANH SÁCH . KHÁI NIỆM DANH SÁCH . Các phép toán trên danh sách . Cài đặt danh sách bằng mảng (danh sách đặc): . CÀI ĐẶT DANH SÁCH BẰNG CON TRỎ (DANH SÁCH LIÊN KẾT) 36 III. Định nghĩa ngăn xếp . Các phép toán trên ngăn xếp . Cài đặt ngăn xếp: . Các phép toán cơ bản trên hàng . Cài đặt hàng . MỘT SỐ ỨNG DỤNG CỦA DANH SÁCH . Đảo ngƣợc xâu ký tự . Tính giá trị của biểu thức dạng hậu tố . Chuyển đổi biểu thức dạng trung tố sang hậu tố . Bài tập cơ bản: . Bài tập nâng cao: . 60 CHƢƠNG 4: SẮP XẾP VÀ TÌM KIẾM . GIỚI THIỆU VỀ SẮP XẾP VÀ TÌM KIẾM . CÁC PHƢƠNG PHÁP SẮP XẾP . Sắp xếp kiểu chọn (Selection Sort) . Sắp xếp kiểu chèn (Insertion Sort) . Sắp xếp nổi bọt (Bubble Sort) . Các bƣớc thực hiện giải thuật . Cài đặt giải thuật . Các bƣớc thực hiện giải thuật . CÁC PHƢƠNG PHÁP TÌM KIẾM . Tìm kiếm tuần tự . Tìm kiếm nhị phân . Tìm kiếm tam phân . 77 CÁC THUẬT NGỮ CHUYÊN MÔN . 78 TÀI LIỆU THAM KHẢO . 79 5 GIÁO TRÌNH 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: MH 16 Thời gian thực hiện môn học: 60 giờ (Lý thuyết: 20 giờ, thực hành, thí nghiệm, thảo luận: 36 giờ, kiểm tra: 4 giờ). Vị trí, tính chất, ý nghĩa và vai trò của môn học: - Vị trí: Thuộc nhóm môn: Môn học lý thuyết chuyên nghành, đƣợc bố trí sau các môn: Tin học căn bản, Lập trình căn bản - Tính chất: 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. -Ý nghĩa và vai trò của môn học: giúp các em tƣ duy, vận động suy nghĩ làm nền tảng cho các môn học sau. Mục tiêu của môn học: - Về kiến thức Hiểu đƣợc nội dung của: dữ liệu, giải thuật, mối quan hệ giữa cấu trúc dữ liệu và giải thuật. Phân tích và xác định đƣợc dữ liệu, giải thuật, sự kết hợp của dữ liệu và giải thuật trong một chƣơng trình máy tính. Áp dụng thuật toán hợp lý đối với cấu trúc dữ liệu tƣơng thích để giải quyết bài toán đơn giản. Áp dụng đƣợc các phƣơng pháp sắp xếp, tìm kiếm đơn giản, các cấu trúc dữ liệu động (danh sách liên kết) vào giải quyết các bài toán. - Về kỹ năng: Thực hành (cài đặt và biên dịch) các bài toán sử dụng các cấu trúc và giải thuật đã học. - Về năng lực tự chủ và trách nhiệm: Nghiêm túc trong học tập và thực hiện tốt các yêu cầu đƣợc giao. Luôn động não suy nghĩ. thƣờng xuyên luyện tập tƣ duy trong việc học Rèn luyện tính cẩn thận, khoa học trong công việc học tập, nghiên cứu. 6 CHƢƠNG 1: GIỚI THIỆU CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Mục tiêu: Nhằm cung cấp những 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 và các kiến thức về thiết kế, phân tích giải thuật cũng nhƣ các phƣơng pháp phân tích, thiết kế giải thuật. Nội dung chính: I. MỐI LIÊN HỆ GIẢI THUẬT VÀ CẤU TRÚC DỮ LIỆU Theo quan điểm của phân tích thiết kế hƣớng đối tƣợng, mỗi lớp sẽ đƣợc xây dựng với một số chức năng nào đó và các đối tƣợng của nó sẽ tham gia vào hoạt động của chƣơng trình. Điểm mạnh của hƣớng đối tƣợng là tính đóng kín và tính sử dụng lại của các lớp. Mỗi phần mềm biên dịch cho một ngôn ngữ lập trình nào đó đều chứa rất nhiều thƣ viện các lớp nhƣ vậy. Chúng ta thử điểm qua một số lớp mà ngƣời lập trình thƣờng hay sử dụng: các lớp có nhiệm vụ đọc/ ghi để trao đổi dữ liệu với các thiết bị ngoại vi nhƣ đĩa, máy in, bàn phím,…; các lớp đồ họa cung cấp các chức năng vẽ, tô màu cơ bản; các lớp điều khiển cho phép xử lý việc giao tiếp với ngƣời sử dụng thông qua bàn phím, chuột, màn hình; các lớp phục vụ các giao dịch truyền nhận thông tin qua mạng;…Các lớp cấu trúc dữ liệu mà chúng ta sắp bàn đến cũng không là một trƣờng hợp ngoại lệ. Có thể chia tất cả các lớp này thành hai nhóm chính: - Các lớp dịch vụ. - Các lớp có khả năng lƣu trữ và xử lý lƣợng dữ liệu lớn. Nhóm thứ hai muốn nói đến các lớp cấu trúc dữ liệu. Vậy có gì giống và khác nhau giữa các lớp cấu trúc dữ liệu và các lớp khác? - Điểm giống nhau giữa các lớp cấu trúc dữ liệu và các lớp khác: Mỗi lớp đều phải thực hiện một số chức năng thông qua các hành vi của các đối tƣợng của nó. Một khi chúng ta đã xây dựng xong một lớp cấu trúc dữ liệu nào đó, chúng ta hoàn toàn tin tƣởng rằng nó sẽ hoàn thành xuất sắc những nhiệm vụ mà chúng ta đã thiết kế và đã giao phó cho nó. Điều này rất khác biệt so với những tài liệu viết về cấu trúc dữ liệu theo quan điểm hƣớng thủ tục trƣớc đây: việc xử lý dữ liệu không hề có tính đóng kín và tính sử dụng lại. Tuy về mặt thực thi thì các chƣơng trình nhƣ thế có khả năng chạy nhanh hơn, nhƣng chúng bộc lộ rất nhiều nhƣợc điểm: thời gian phát triển giải thuật chính rất chậm gây khó khăn nhiều cho ngƣời lập trình, chƣơng trình thiếu tính trong sáng, rất khó sửa lỗi và phát triển. - Đặc trƣng riêng của các lớp cấu trúc dữ liệu: Nhiệm vụ chính của các lớp cấu trúc dữ liệu là nắm giữ dữ liệu sao cho có thể đáp ứng mỗi khi đƣợc chƣơng trình yêu cầu trả về một dữ liệu cụ thể nào đó mà chƣơng trình cần đến. Những thao tác cơ bản đối với một cấu trúc dữ liệu thƣờng là: thêm dữ liệu mới, xóa bỏ dữ liệu đã 7 có, tìm kiếm, truy xuất. Ngoài các thao tác dữ liệu cơ bản, các cấu trúc dữ liệu khác nhau sẽ khác nhau về các thao tác bổ sung khác. Chính vì điều này mà khi thiết kế những giải thuật để giải quyết các bài toán lớn, ngƣời ta sẽ lựa chọn cấu trúc dữ liệu nào là thích hợp nhất. Chúng ta thử xem xét một ví dụ thật đơn giản sau đây: Giả sử chúng ta cần viết một chƣơng trình nhận vào một dãy các con số, và in chúng ra theo thứ tự ngƣợc với thứ tự nhập vào ban đầu. Để giải quyết bài toán này, nếu chúng ta nghĩ đến việc phải khai báo các biến để lƣu các giá trị nhập vào nhƣ thế nào, và sau đó là thứ tự in ra sao để đáp ứng yêu cầu bài toán, thì dƣờng nhƣ là chúng ta đã quên áp dụng nguyên tắc lập trình hƣớng đối tƣợng: chúng ta đã phải bận tâm đến những việc quá chi tiết. Đây chỉ là một ví dụ vô cùng đơn giản, nhƣng nó có thể minh họa cho vai trò của cấu trúc dữ liệu.
