Giáo trình Cấu trúc dữ liệu và giải thuật (Nghề: Công nghệ thông tin - Trung cấp) - Trường Trung cấp Trường Sơn, Đắk Lắk

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:57

Thêm vào BST

Báo xấu

19
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Giáo trình Cấu trúc dữ liệu và giải thuật được biên soạn với mục tiêu nhằm giúp sinh viên trình bày được mối quan hệ giữa cấu trúc dữ liệu và giải thuật trong việc xây dựng chương trình; trình bày được khái niệm thời gian thực hiện giải thuật, độ phức tạp tính toán của giải thuật và các yếu tố liên quan đến thời gian thực hiện giải thuật; trình bày được các khái niệm về đệ quy, giải thuật đệ quy và thủ tục đệ quy; Trình bày được các khái niệm, cấu trúc lưu trữ, phân loại, cách duyệt cây. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Cấu trúc dữ liệu và giải thuật (Nghề: Công nghệ thông tin - Trung cấp) - Trường Trung cấp Trường Sơn, Đắk Lắk

SỞ LAO ĐỘNG, THƯƠNG BINH VÀ XÃ HỘI ĐẮK LẮK TRƯỜNG TRUNG CẤP TRƯỜNG SƠN GIÁO TRÌNH MÔN HỌC: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NGHỀ: CÔNG NGHỆ THÔNG TIN TRÌNH ĐỘ: TRUNG CẤP Ban hành kèm theo Quyết định số: 140/QĐ-TCTS ngày 02 tháng 8 năm 2022 của Hiệu trưởng Trường trung cấp Trường Sơn Đắk Lắk, năm 2022
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. ii
LỜI GIỚI THIỆU Hiện nay, tại Trường chưa có giáo trình Cấu trúc dữ liệu & giải thuật. Đặc biệt trên thị trường không có tài liệu học tập, tham khảo phù hợp với chương trình khung Cao đẳng nghề, trung cấp nghề thuộc nghề Công nghệ thông tin (CNTT) trong quá trình đào tạo nghề hiện nay. Nhóm tác giả biên soạn giáo trình lập trình cơ bản nhằm mục đích giúp học sinh, sinh viên (HSSV) sử dụng giáo trình làm tài liệu nghiên cứu và học tập một cách thuận tiện. Chương trình môn học được sử dụng để giảng dạy cho sinh viên trung cấp nghề Công nghệ thông tin (ứng dụng phần mềm) và làm tài liệu tham khảo cho các nghề thuộc các ngành nghề kỹ thuật. Vậy, rất mong được sự góp ý của bạn đọc để tài liệu này ngày càng được hoàn thiện hơn, chúng tôi xin chân thành cảm ơn.. Xin chân thành cảm ơn!. Đắk Lắk, ngày 02 tháng 8 năm 2022 Tham gia biên soạn 1. Nguyễn Như Cường - Chủ biên 2. Nguyễn Thị Nhung 3. Lưu Thị Thương iii
MỤC LỤC LỜI GIỚI THIỆU .......................................................................................................... III GIÁO TRÌNH MÔN HỌC .............................................................................................. 7 CHƯƠNG I. THIẾT KẾ VÀ PHÂN TÍCH GIẢI THUẬT ............................................ 9 1. TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH:...............................................................................................9 1.1 Modul hóa việc giải quyết bài toán: ................................................................................................ 9 1.2 Phương pháp tinh chỉnh từng bước ................................................................................................. 9 2. PHÂN TÍCH GIẢI THUẬT: .................................................................................................................9 3. ĐỘ PHỨC TẠP TÍNH TOÁN CỦA GIẢI THUẬT .............................................................................. 10 3.1 Khái niệm: ................................................................................................................................................ 10 3.2. Ví dụ .......................................................................................................................................................... 10 3.3 Xác định độ phức tạp tính toán của giải thuật: ......................................................................... 10 CHƯƠNG II. ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY .................................................. 12 1. KHÁI NIỆM ĐỆ QUY: ...................................................................................................................... 12 2. GIẢI THUẬT ĐỆ QUY VÀ THỦ TỤC ĐỆ QUY ................................................................................ 12 3. THIẾT KẾ GIẢI THUẬT ĐỆ QUY..................................................................................................... 12 3.1 Bài toán tính n! ....................................................................................................................................... 12 3.2. Dãy số Fibonacci: ................................................................................................................................ 14 3.3 Bài toán tháp Hà Nội: .......................................................................................................................... 14 4. HIỆU LỰC ĐỆ QUY:......................................................................................................................... 14 CHƯƠNG III. MẢNG VÀ DANH SÁCH ................................................................... 15 1. CÁC KHÁI NIỆM:............................................................................................................................. 15 1.1. Mảng: ........................................................................................................................................................ 15 2. CẤU TRÚC LƯU TRỮ CỦA MẢNG ................................................................................................. 16 2.1 Khái niệm: ................................................................................................................................................ 16 2.2 Định nghĩa kiểu cấu trúc .................................................................................................................... 17 2.3 Khai báo biến cấu trúc ........................................................................................................................ 18 3. LƯU TRỮ KẾ TIẾP CỦA DANH SÁCH TUYẾN TÍNH ..................................................................... 18 3.1. Khái niệm: ............................................................................................................................................... 18 3.2. Khai báo biến tập hợp:....................................................................................................................... 18 3.3 Khai báo biến kiểu tập hợp: .............................................................................................................. 19 4 STACK HAY DANH SÁCH KIỂU NGĂN XẾP: ................................................................................. 20 iv
4.1. Khái niệm - Cấu trúc dữ liệu: ...................................................................................................... 20 4.2 Lưu trữ Stack bằng mảng .................................................................................................................. 20 4.3 Ứng dụng của ngăn xếp (Biểu thức hậu tố - ký pháp Ba Lan) .......................................... 21 5. HÀNG ĐỢI (QUEUE) ................................................................................................................... 22 5.1 Khái niệm:............................................................................................................................................... 22 5.2 Lưu trữ Queue bằng mảng: ............................................................................................................... 23 CHƯƠNG IV. CÂY ...................................................................................................... 25 1. CÁC KHÁI NIỆM CƠ BẢN:.............................................................................................................. 25 1.1. Định nghĩa cây: .................................................................................................................................. 25 1.2. Một số khái niệm liên quan ............................................................................................................. 27 1.3. Biểu diễn cây ...................................................................................................................................... 28 2. CÂY NHỊ PHÂN (BINARY TREE):.................................................................................................. 29 2.2. Biểu diễn cây nhị phân: ................................................................................................................... 30 3. PHÉP DUYỆT CÂY NHỊ PHÂN: ....................................................................................................... 30 3.1 Duyệt theo thứ tự trước NLR (Node – Left – Right) ............................................................ 31 3.2 Duyệt theo thứ tự giữa LNR (Left – Node – Right) .............................................................. 31 3.3 Duyệt theo thứ tự sau LRN (Left – Right – Node ) ............................................................... 33 4. CÂY NHỊ PHÂN TÌM KIẾM: ............................................................................................................. 33 4.1. Định nghĩa ............................................................................................................................................... 33 4.2. Tìm kiếm trên cây nhị phân tìm kiếm ......................................................................................... 34 4.3.Thêm phần tử mới vào cây nhị phân tìm kiếm......................................................................... 35 4.4.Xóa phần tử khỏi cây nhị phân tìm kiếm .................................................................................... 36 4.5. Xóa toàn bộ cây nhị phân ................................................................................................................. 39 5. BÀI TẬP: .......................................................................................................................................... 39 CHƯƠNG V. ĐỒ THỊ VÀ MỘT VÀI CẤU TRÚC PHI TUYẾN .............................. 40 1. CÁC KHÁI NIỆM VỀ ĐỒ THỊ........................................................................................................... 40 2. BIỂU DIỄN ĐỒ THỊ .......................................................................................................................... 41 2.1 Biểu diễn bằng ma trận lân cận: ..................................................................................................... 41 2.2 Biểu diễn bằng danh sách lân cận ................................................................................................. 42 3. PHÉP DUYỆT MỘT ĐỒ THỊ ............................................................................................................. 42 3.1 Tìm kiếm theo chiều sâu: .................................................................................................................. 42 3.2 Tìm kiếm theo chiều rộng: ............................................................................................................... 42 v
4. CÂY KHUNG.................................................................................................................................... 42 4.1 Giải thuật Kruskal ................................................................................................................................. 42 4.2 Giải thuật Prim: ...................................................................................................................................... 44 5.CÂU HỎI VÀ BÀI TẬP...................................................................................................................... 45 CHƯƠNG VI. SẮP XẾP VÀ TÌM KIẾM .................................................................... 46 1. SẮP XẾP: .......................................................................................................................................... 46 1.1 Khái quát về sắp xếp ............................................................................................................................ 46 1.2. Một số phương pháp sắp xếp .......................................................................................................... 46 2. TÌM KIẾM ......................................................................................................................................... 51 2.1 Khái quát về tìm kiếm ......................................................................................................................... 51 2.2 Tìm tuần tự (Linear Search) ........................................................................................................ 51 2.3. Tìm nhị phân (Binary Search) .................................................................................................... 54 3. CÂU HỎI VÀ BÀI TẬP..................................................................................................................... 55 TÀI LIỆU THAM KHẢO ............................................................................................. 57 vi
GIÁO TRÌNH MÔN HỌC Tên môn học: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Mã môn học: MH10 Vị trí, tính chất, ý nghĩa và vai trò của mô đun: - Vị trí: Là môn học cơ sở nghề trong chương trình đào tạo Trung cấp nghề Công nghệ thông tin (ứng dụng phần mềm). Môn học này được học sau khối môn học chung và trước các môn học, mô đun chuyên môn ngành, nghề. - Tính chất: Môn học cung cấp những kiến thức cơ bản về phân tích thiết kế và đánh giá độ phức tạp thuật toán và các kiểu dữ liệu cơ sở. cách cài đặt và các thao tác Các cấu trúc dữ liệu trừu tượng, cấu trúc dữ liệu cây nhị phân: cài đặt và các thao tác trên cây nhị phân. Đồng thời, cài đặt danh sách liên kết - ngăn xếp - hàng đợi, cài đặt cây nhị phân Cài đặt các thuật toán sắp xếp - tìm kiếm và các thao tác liên quan. - Ý nghĩa và vai trò của mô đun: Mục tiêu của mô đun: - Về kiến thức: - Trình bày được mối quan hệ giữa cấu trúc dữ liệu và giải thuật trong việc xây dựng chương trình; - Trình bày được khái niệm thời gian thực hiện giải thuật, độ phức tạp tính toán của giải thuật và các yếu tố liên quan đến thời gian thực hiện giải thuật; - Trình bày được các khái niệm về đệ quy, giải thuật đệ quy và thủ tục đệ quy; - Trình bày được các khái niệm, cấu trúc lưu trữ, phân loại, cách duyệt cây; - Trình bày đặc điểm của các cách biểu diễn đồ thị; - Trình bày được các phép duyệt đồ thị với các giải thuật minh họa; - Trình bày được ý tưởng, thuật toán chi tiết của một số phương pháp sắp xếp; - Trình bày được ý tưởng, thuật toán chi tiết của một số phương pháp tìm kiếm; - Trình bày được các khái niệm về đệ quy, giải thuật đệ quy và thủ tục đệ quy. - Về kỹ năng: - Xây dựng được lời giải một bài toán: chia một bài toán thành nhiều bài toán nhỏ để giải sau đó phối hợp, ghép các bài toán nhỏ lại với nhau để đưa về bài toán ban đầu; - Xác định, phân tích được trên một số ví dụ về đệ quy và giải thuật đệ quy; - Cài đặt được một số thao tác xử lý danh sách liên kết, ngăn xếp, hàng đợi trên ngôn ngữ C, Pascal; - Biểu diễn được cách biểu diễn cây nhị phân - Phân biệt được các loại đồ thị: Đồ thị định hướng, đồ thị không định hướng, định hướng liên thông và định hướng không liên thông; - Phân biệt được các phép tìm kiếm theo chiều rộng và tìm kiếm theo chiều sâu với các đồ thị; 7
- Áp dụng một số thuật toán sắp xếp, tìm kiếm vào thực hiện việc sắp xếp và tìm kiếm các dãy khóa cụ thể; - Về năng lực tự chủ và trách nhiệm: - Xây dựng được lời giải một bài toán: chia một bài toán thành nhiều bài toán nhỏ để giải sau đó phối hợp, ghép các bài toán nhỏ lại với nhau để đưa về bài toán ban đầu; - Xác định, phân tích được trên một số ví dụ về đệ quy và giải thuật đệ quy; - Cài đặt được một số thao tác xử lý danh sách liên kết, ngăn xếp, hàng đợi trên ngôn ngữ C, Pascal; - Biểu diễn được cách biểu diễn cây nhị phân - Phân biệt được các loại đồ thị: Đồ thị định hướng, đồ thị không định hướng, định hướng liên thông và định hướng không liên thông; - Phân biệt được các phép tìm kiếm theo chiều rộng và tìm kiếm theo chiều sâu với các đồ thị; - Áp dụng một số thuật toán sắp xếp, tìm kiếm vào thực hiện việc sắp xếp và tìm kiếm các dãy khóa cụ thể. Nội dung của môn học: Thời gian TT Tên chương, mục Tổng Lý Thực Kiểm số thuyết hành, tra* 1 Chương I. Thiết kế và phân tích giải thuật 7 2 5 2 Chương II. Đệ quy và giải thuật đệ quy 5 2 3 3 Chương III. Mảng và danh sách 8 2 5 1 4 Chương IV. Cây 17 4 13 Chương V. Đồ thị và một vài cấu trúc phi 5 8 2 6 tuyến 6 Chương VI. Sắp xếp và tìm kiếm 15 3 11 1 TỔNG CỘNG 60 15 43 2 8
CHƯƠNG I. THIẾT KẾ VÀ PHÂN TÍCH GIẢI THUẬT Giới thiệu: Mục tiêu: Học xong chương này, người học có khả năng: - Trình bày được khái niệm giải thuật và ý nghĩa của giải thuật để giải một bài toán bằng chương trình; - Trình bày được quy trình xây dựng lời giải một bài toán; - Trình bày được khái niệm thời gian thực hiện giải thuật, độ phức tạp tính toán của giải thuật và các yếu tố liên quan đến thời gian thực hiện giải thuật; - Phân biệt được các quy tắc tổng, quy tắc nhân khi xác định độ phức tạp của thuật toán; - Có thái độ nghiêm túc, chịu khó tìm tòi học hỏi; - Rèn luyện tính cẩn thận, tỉ mỉ, chính xác, sáng tạo, linh hoạt trong công việc. Nội dung: 1. Từ bài toán đến chương trình: 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.1 Modul hóa việc giải quyết bài toán: 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, ? 1.2 Phương pháp tinh chỉnh từng bước 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ể. 2. Phân tích 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: 9
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. 3. Độ phức tạp tính toán của giải thuật 3.1 Khái niệm: Độ phức tạp thời gian là toàn bộ tài nguyên về thời gian mà máy tính cần để thực thi một thuật toán nào đó, được thể hiện bằng hàm số y = f\left ( x \right ). Thông thường, độ phức tạp thời gian sẽ dựa vào số lần mà một câu lệnh cơ bản với thời gian thực thi là hằng số được thực thi. Chúng ta sẽ tìm hiểu rõ hơn qua ví dụ ở các phần sau. Đối với một chương trình, sẽ có hai loại độ phức tạp là độ phức tạp thời gian và độ phức tạp bộ nhớ. Tuy nhiên, trong khoá học này, mình sẽ chủ yếu đề cập đến độ phức tạp thời gian. Do đó, khi mình nói “độ phức tạp chương trình” tức là nói về độ phức tạp thời gian của chương trình đó. Trên thực tế, do sự khác biệt về dữ liệu đầu vào như đã nói ở trên, đa phần các thuật toán sẽ được tính toán độ phức tạp dựa vào trường hợp xấu nhất (worst-case), tức là khoảng thời gian tối đa mà chương trình sẽ chạy với một bộ dữ liệu có kích thước cố định. Một số thuật toán sẽ được đánh giá dựa theo trường hợp trung bình (average- case) ví dụ như Quick Sort. Để biết tại sao Quick Sort lại được đánh giá dựa vào trường hợp trung bình thì hãy tiếp tục theo dõi khoá học này nhé. Ngoài ra còn có một cách đánh giá dựa vào trường hợp tốt nhất (best-case). Tuy nhiên, ta sẽ không quan tâm đến cách đánh giá này do nó không bao giờ được áp dụng trong thực tế. Tuy nhiên, do các hàm số thể hiện độ phức tạp thường rất khó tính toán nên chúng ta cần một phương pháp đánh giá hiệu quả hơn. Một cách được sử dụng phổ biến đó là Độ phức tạp thời gian BigO. 3.2. Ví dụ 3.3 Xác định độ phức tạp tính toán của giải thuật: 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 10
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: 3.3.1 Quy tắc tổng 3.3.2. Quy tắc nhân 11
CHƯƠNG II. ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY Giới thiệu: Mục tiêu Học xong chương này, người học có khả năng: - Trình bày được các khái niệm về đệ quy, giải thuật đệ quy và thủ tục đệ quy; - Trình bày được các bước thiết kế giải thuật đệ quy; - So sánh được hiệu lực giữa giải thuật đệ quy với giải thuật khác; - Xác định, phân tích được trên một số ví dụ về đệ quy và giải thuật đệ quy; - Rèn luyện tính cẩn thận, tỉ mỉ, chính xác, sáng tạo, linh hoạt trong công việc. Nội dung 1. Khái niệm đệ quy: Bất cứ một hàm nào đó có thể triệu gọi hàm khác, nhưng ở đây một hàm nào đó có thể tự triệu gọi chính mình. Kiểu hàm như thế được gọi là hàm đệ quy. 2. Giải thuật đệ quy và thủ tục đệ quy Phương pháp đệ quy thường dùng phổ biến trong những ứng dụng mà cách giải quyết có thể được thể hiện bằng việc áp dụng liên tiếp cùng giải pháp cho những tập hợp con của bài toán. 3. Thiết kế giải thuật đệ quy 3.1 Bài toán tính n! n! = 1*2*3*…*(n-2)*(n-1)*n với n >= 1 và 0! = 1. /* Ham tinh giai thua */ #include #include void main(void) { int in; long giaithua(int); printf("Nhap vao so n: "); scanf("%d", &in); printf("%d! = %ld.\n", in, giaithua(in)); getch(); } long giaithua(int in) { 12
int i; long ltich = 1; if (in == 0) return (1L); else { for (i = 1; i
4 * giaithua(3) = 4 * ? 3 * giaithua(2) = 3 * ? 2 * giaithua(1) = 2 * ? 1 * giaithua(0) = 1 * ? Khi tham số in = 0 thì return về giá trị 1L (giá trị 1 kiểu long). Lúc này các giá trị ? bắt đầu định trị theo thứ tự ngược lại. • Định trị theo thứ tự ngược lại giaithua(in) return(in * giaithua(in – 1)) 1 * giaithua(0) = 1 * 1 = 1 2 * giaithua(1) = 2 * 1 = 2 3 * giaithua(2) = 3 * 2 = 6 4 * giaithua(3) = 4 * 6 = 24 5 * giaithua(4) = 5 * 24 = 120 Kết quả sau cùng ta có 5! = 120. Thứ tự gọi đệ quy Định trị theo thứ tự ngược lạiA 3.2. Dãy số Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … Bắt đầu bằng 0 và 1, các số tiếp theo bằng tổng hai số đi trước. Dãy Fibonacci được khai báo đệ quy như sau: Fibonacci(0) = 0 Fibonacci(1) = 1 Fibonacci(n) = Fibonacci(n – 1) + Fibonacci(n – 2) 3.3 Bài toán tháp Hà Nội: Tháp Hà Nội là một trong những bài toán kinh điển của giới lập trình. Hầu như bất kể ai mới học lập trình, đặc biệt là môn cấu trúc dữ liệu và giải thuật đều có nghe nói hoặc đã từng phải giải bài toán này. 4. Hiệu lực đệ quy: 14
CHƯƠNG III. MẢNG VÀ DANH SÁCH Giới thiệu: Mục tiêu - Trình bày được khái niệm, cấu trúc lưu trữ của dữ liệu kiểu mảng, kiểu danh sách; - Trình bày được một số phép toán xử lý trên các phần tử của danh sách liên kết, địa chỉ của phần tử trong danh sách, địa chỉ của bộ nhớ và cách định địa chỉ của phần tử trong danh sách; - Trình bày được cấu trúc, các phép xử lý, khả năng áp dụng của ngăn xếp, hàng đợi; - Trình bày được khái niệm Stack, quy chế lưu trữ Stack bằng mảng, khái niệm Queue, quy chế lưu trữ Queue bằng mảng; - Xác định và phân tích được một số ứng dụng của Stack, bổ sung và loại một phần tử ra khỏi Queue; - Cài đặt được một số thao tác xử lý danh sách liên kết, ngăn xếp, hàng đợi trên ngôn ngữ C, Pascal; - Nghiêm túc, tỉ mỉ, sáng tạo trong việc học và vận dụng vào làm bài tập. Chủ động kết hợp các ngôn ngữ lập trình để cài đặt thuật toán. Nội dung 1. Các khái niệm: 1.1. Mảng: Mỗi biến chỉ có thể biểu diễn một giá trị. Để biểu diễn một dãy số hay một bảng số ta có thể dung nhiều biến nhưng cách này không thuận lợi. trong trường hợp này ta có khái niệm về mảng. khái niệm về mảng trong ngôn ngữ C cũng giống như khái niệm về ma trận trong đại số tuyến tính. Mảng có thể hiểu là một tập hợp nhiều phần tử có cùng kiểu giá trị và cùng cùng chung một tên. Mỗi phần tử mảng biểu diễn được một giá trị. Có bao nhiêu kiểu biến thì có bấy nhiêu kiểu mảng. mảng cần được khai báo để định rõ: loại mảng: int, float, double,…. Tên mảng. Số chiều dài và kích thước mỗi chiều. Khái niệm về kiểu mảng và tên mảng cũng giống như khái niệm về kiểu biến và tên biến. ta sẽ giải thích về số chiều và kích thước mỗi chiều thong qua các ví dụ cụ thể dưới đây. Các khai báo: int a[10],b[4][2]; float x[5],y[3][3]; Chú ý: 15
Các phần tử của mảng được cấp phát các khoản nhớ lien tiếp nhau trong bộ nhớ. Nói cách khác, các phần tử của mảng liên tiếp nhau. Trong bộ nhớ, các phần tử của mảng hai chiều được sắp xếp theo hang. Chỉ số mảng: Một phần tử cụ thể của mảng được xác định nhờ các chỉ số của nó. Chỉ số của mảng phải có giá trị int không vượt quá kích thước tương ứng. số chỉ số bằng số chiều của mảng. Giả sử z,b,x,y được khai báo như trên, và giả sử i,j là các biến nguyên trong đó i=2, J=1, khi đó: a[j+i-1] là a[2] b[j+i][2-i] là b[3][0] y[i][j] là y[2][1] Chú ý: Mảng có bao nhiêu chiều thì ta phải viết bấy nhiêu chỉ số. vì thế nếu ta viết như sau sẽ là sai: y[i]( vì y là mảng hai chiều),vv… Biểu thức dung làm chỉ số có thể thực hiện. khi đó phần nguyên của biểu thức thực sẽ là chỉ số mảng. Ví dụ: A[2.5] là a[2] B[1.9] là a[1] *Khi chỉ số vượt ra ngoài kích thước mảng, máy sẽ vẫn không báo lỗi, nhưng nó sẽ truy cập đến một vùng nhớ bên ngoài mảng và có thể làm loạn chương trình. 2. Cấu trúc lưu trữ của mảng 2.1 Khái niệm: Kiểu cấu trúc (Structure) là kiểu dữ liệu bao gồm nhiều thành phần có kiểu khác nhau, mỗi thành phần được gọi là một trường (field) Sự khác biệt giữa kiểu cấu trúc và kiểu mảng là: các phần tử của mảng là cùng kiểu còn các phần tử của kiểu cấu trúc có thể có kiểu khác nhau. Hình ảnh của kiểu cấu trúc được minh họa: 16
2.2 Định nghĩa kiểu cấu trúc struct { ; ; …….. ; }; Trong đó: - : là một tên được đặt theo quy tắc đặt tên của danh biểu; tên này mang ý nghĩa sẽ là tên kiểu cấu trúc. - (i=1..n): mỗi trường trong cấu trúc có dữ liệu thuộc kiểu gì (tên của trường phải là một tên được đặt theo quy tắc đặt tên của danh biểu). Ví dụ 1: Để quản lý ngày, tháng, năm của một ngày trong năm ta có thể khai báo kiểu cấu trúc gồm 3 thông tin: ngày, tháng, năm. struct NgayThang { unsigned char Ngay; unsigned char Thang; unsigned int Nam; }; typedef struct { unsigned char Ngay; unsigned char Thang; unsigned int Nam; } NgayThang; Ví dụ 2: Mỗi sinh viên cần được quản lý bởi các thông tin: mã số sinh viên, họ tên, ngày tháng năm sinh, giới tính, địa chỉ thường trú. Lúc này ta có thể khai báo một struct gồm các thông tin trên. struct SinhVien { char MSSV[10]; char HoTen[40]; struct NgayThang NgaySinh; 17
int Phai; char DiaChi[40]; }; typedef struct { char MSSV[10]; char HoTen[40]; NgayThang NgaySinh; int Phai; char DiaChi[40]; } SinhVien; 2.3 Khai báo biến cấu trúc Việc khai báo biến cấu trúc cũng tương tự như khai báo biến thuộc kiểu dữ liệu chuẩn. Cú pháp: - Đối với cấu trúc được định nghĩa theo cách 1: struct [, …]; - Đối với các cấu trúc được định nghĩa theo cách 2: [, …]; Ví dụ: Khai báo biến NgaySinh có kiểu cấu trúc NgayThang; biến SV có kiểu cấu trúc SinhVien. struct NgayThang NgaySinh; struct SinhVien SV; NgayThang NgaySinh; SinhVien SV; 3. Lưu trữ kế tiếp của danh sách tuyến tính 3.1. Khái niệm: Đối với các kiểu dữ liệu ta đã biết như kiểu số, kiểu mảng, kiểu cấu trúc thì dữ liệu kiểu tập hợp (typedef) là kiểu dữ liệu bao gồm nhiều thành phần có kiểu dữ liệu giống hoặ khác nhau, mỗi thành phần được gọi là một trường (field). 3.2. Khai báo biến tập hợp: Sử dụng từ khóa typedef (Type definitions) để định nghĩa kiểu: Typedef struct { ; 18
; …….. ; } ; Trong đó: - typedef (Type definitions): là kiểu do người dùng định nghĩa. - : là một tên được đặt theo quy tắc đặt tên của danh biểu; tên này mang ý nghĩa sẽ là tên kiểu cấu trúc. (i=1..n): mỗi trường trong cấu trúc có dữ liệu thuộc kiểu dữ liệu cơ bản. Ví dụ 1: Để quản lý ngày, tháng, năm của một ngày trong năm ta có thể khai báo kiểu cấu trúc gồm 3 thông tin: ngày, tháng, năm. Typedef struct { unsigned char Ngay; unsigned char Thang; unsigned int Nam; } NgayThang; Ví dụ 2: Mỗi sinh viên cần được quản lý bởi các thông tin: mã số sinh viên, họ tên, ngày tháng năm sinh, giới tính, địa chỉ thường trú. Lúc này ta có thể khai báo một struct gồm các thông tin trên. typedef struct { char MSSV[10]; char HoTen[40]; NgayThang NgaySinh; int Phai; char DiaChi[40]; } SinhVien; 3.3 Khai báo biến kiểu tập hợp: Việc khai báo biến tập hợp cũng tương tự như khai báo biến thuộc kiểu dữ liệu chuẩn. Cú pháp: - Đối với cấu trúc được định nghĩa theo cách 1: struct [, …]; 19
- Đối với các cấu trúc được định nghĩa theo cách 2: [, …]; Ví dụ: Khai báo biến NgaySinh có kiểu cấu trúc NgayThang; biến SV có kiểu cấu trúc SinhVien. struct NgayThang NgaySinh; struct SinhVien SV; NgayThang NgaySinh; SinhVien SV; 4 Stack hay danh sách kiểu ngăn xếp: 4.1. Khái niệm - Cấu trúc dữ liệu: Ngăn xếp là một danh sách mà trong đó thao tác thêm một phần tử vào tro ng danhvà thao tác lấy ra một phần tử từ trong danh sách đượcthực hiện ở cùng đầu Như vậy, các phần tử được đưa vào trong ngăn xếp sau cùng sẽ được lấy ra trướctiên, phần tử đưa vào trong hàng đợi trước tiên sẽ được lấy ra sau cùng. Do đó màngăn xếp còn được gọi là danh sách vào sau ra tr ước (LIFO List) và cấu trúc dữ liệunày còn được gọi là cấu trúc LIFO (Last In – First Out). Tương tự như hàng đợi, có nhiều cách để biểu diễn và tổ chức các ngăn xếp - Sử dụng danh sách đặc, - Sử dụng danh sách liên kết, Do ở đây cả hai thao tác thêm vào và lấy ra đều được thực hiện ở một đầu nên chúng ta chỉ cần quản lý vị trí đầu của danh sách dùng làm mặt cho ngăn xếp thông qua biến chỉ số bề mặt SP (Stack Pointer). Chỉ số này có thể là cùng chiều (đầu) hoặc ngược chiều (cuối) với thứ tự các phần tử trong mảng và trong danh sách liênkết. Điều này có nghĩa là bề mặt ngăn xếp có thể là đầu mảng, đầu danh sách liênkết mà cũng có thể là cuối mảng, cuối danh sách liên kết. Để thuận tiện, ở đâychúng ta giả sử bề mặt của ngăn xếp là đầu mảng, đầu danh sách liên kết. Trường hợp ngược lại, sinh viên tự áp dụng tương tự. Ở đây chúng ta cũng sẽ biểu diễn và tổ chức hàng đợi bằng danh sách đặc và bằngdanh sách liên kết đơn được quản lý bởi con trỏ đầu danh sách. Do vậy cấu trúc dữliệu của ngăn xếp và các thao tác trên đó sẽ được trình bày thành hai trường hợpkhác nhau. 4.2 Lưu trữ Stack bằng mảng - Biểu diễn và tổ chức bằng danh sách đặc: typedef struct S_C { int Size; // Kích thước ngăn xếp int SP; T * List;// Nội dung ngăn xếp 20