Giáo trình cấu trúc dữ liệu và giải thuật ngành CNTT trung cấp - CĐXD số 1

Giáo trình cấu trúc dữ liệu và giải thuật cho ngành công nghệ thông tin trung cấp. Nắm vững kiến thức cơ bản, thuật toán thông dụng, ứng dụng thực tế.

• Tác giả: Trần Thị M¢
• Trường học: Trường cao đẳng xây dựng số 1
• Chuyên ngành: Công nghệ thông tin (ứng dụng phần mềm)
• Đề tài: Cấu trúc dữ liệu và giải thuật
• Loại tài liệu: Giáo trình
• Năm xuất bản: 2023
• Địa điểm: Hà Nội

Mục lục chi tiết

• Lời nói đầu
• 1. CHƯƠNG 1: GIẢI THUẬT
• 1.1. Các khái niệm về giải thuật
• 1.2. Các đặc trưng của giải thuật
• 1.3. Tính hiệu quả. Tính chính xác
• 1.4. Tính ứng dụng
• 1.5. Ngôn ngữ diễn đạt giải thuật
• 1.6. Ngôn ngữ thông thường
• 1.7. Ngôn ngữ lập trình
• 1.8. Phương pháp thiết kế giải thuật
• 1.9. Tinh chỉnh từng bước
• 2. CHƯƠNG 2: CÂU TRÚC DỮ LIỆU
• 2.1. Danh sách tuyến tính
• 2.2. Danh sách liên kết
• 2.3. Danh sách liên kết đơn
• 2.4. Các dạng khác của danh sách liên kết
• 2.5. Cây nhị phân
• 2.6. Biểu diễn cây nhị phân
• 2.7. Duyệt cây nhị phân
• 2.8. Cây nhị phân tìm kiếm
• 2.9. Duyệt đồ thị theo chiều rộng
• 2.10. Duyệt theo chiều sâu

Tóm tắt

I. Tổng quan Cấu trúc dữ liệu và giải thuật trung cấp DSA CNTT 55 ký tự

Giáo trình Cấu trúc dữ liệu và giải thuật (CTDL&GT) được biên soạn nhằm phục vụ cho giảng dạy và học tập trình độ trung cấp ngành Công nghệ thông tin (Ứng dụng phần mềm). Môn học này cung cấp kiến thức cơ bản về các kiểu cấu trúc dữ liệu cơ bản thông dụng và một số giải thuật cơ bản trên các kiểu cấu trúc dữ liệu đó. Nội dung giáo trình gồm 2 chương: Giải thuật và Cấu trúc dữ liệu. Mục tiêu là cung cấp cho người học các khái niệm về giải thuật, các đặc trưng của giải thuật, ngôn ngữ diễn đạt giải thuật, phương pháp thiết kế giải thuật và đánh giá độ phức tạp của giải thuật trong một số bài toán cụ thể. CTDL&GT quan trọng trong ngành CNTT, là nền tảng để xây dựng các chương trình hiệu quả. Giáo trình này sẽ trình bày những kiến thức quan trọng liên quan đến CTDL&GT một cách chi tiết và dễ hiểu nhất cho người học.

1.1. Định nghĩa và tầm quan trọng của CTDL GT trong CNTT

Khái niệm CTDL&GT hay thuật giải 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, bằng sơ đồ hoặc bằng mã giả. Trong thực tế, giải thuật thường được minh họa hay thể hiện bằng mã giả dựa trên một hay một số ngôn ngữ lập trình nào đó, chẳng hạn như C, Pascal. CTDL&GT là môn học cơ sở ngành, cung cấp kiến thức cơ bản về các khái niệm, các kiểu cấu trúc dữ liệu thông dụng và một số giải thuật trên các kiểu cấu trúc dữ liệu đó. Mối quan hệ giữa CTDL&GT 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. 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.

1.2. Mối liên hệ giữa Data Structures and Algorithms DSA và lập trình

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. Để đánh giá một cấu trúc dữ liệu, người ta thường dựa vào một số tiêu chí sau: Cấu trúc dữ liệu phải tiết kiệm tài nguyên (bộ nhớ trong), phản ánh đúng thực tế của bài toán, dễ dàng trong việc thao tác dữ liệu. 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.

II. Cách nhận diện và giải quyết bài toán CTDL GT phức tạp 58 ký tự

Việc lựa chọn phương pháp phù hợp có thể 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ể. Các đặc trưng của giải thuật bao gồm tính xác định, tính khả thi, tính dừng. Mỗi bước của thuật giải cần phải được mô tả một cách chính xác, chỉ có một cách hiểu duy nhất. Tất cả các phép giải có mặt trong các bước của thuật giải phải đủ đơn giản. Với mọi bộ dữ liệu vào thỏa mãn điều kiện qui định, thuật giải phải dừng lại sau một số hữu hạn bước thực hiện.

2.1. Phân tích độ phức tạp thuật toán Big O Notation trong bài toán

Một giải thuật nên là có thể thi hành được với các nguồn có sẵn, tức là có khả năng giải quyết hiệu quả vấn đề trong điều kiện thời gian và tài nguyên cho phép. Giải thuật nên rõ ràng và không mơ hồ. Mỗi một giai đoạn (hay mỗi bước) nên rõ ràng và chỉ mang một mục đích nhất định. Một giải thuật có tính phổ biến nếu giải thuật này có thể giải quyết được một lớp các vấn đề tương tự.

2.2. Các yếu tố ảnh hưởng đến hiệu suất của giải thuật cơ bản

Trong cách biểu diễn thuật giải theo ngôn ngữ tự nhiên, người ta sử dụng ngôn ngữ thường ngày để liệt kê các bước của thuật giải. Phương pháp biểu diễn này không yêu cầu người viết thuật giải cũng như người đọc thuật giải phải nắm các quy tắc. Tuy vậy, cách biểu diễn này thường dài dòng, không thể hiện rõ cấu trúc của thuật giải, đôi lúc gây hiểu lầm hoặc khó hiểu cho người đọc. Gần như không có một quy tắc cố định nào trong việc thể hiện thuật giải bằng ngôn ngữ tự nhiên.

2.3. Thiết kế thuật toán hiệu quả bằng phương pháp chia để trị

Lưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật giải. Biểu diễn thuật giải bằng lưu đồ sẽ giúp người đọc theo dõi được sự phân cấp các trường hợp và quá trình xử lý của thuật giải. Phương pháp lưu đồ thường được dùng trong những thuật giải có tính rắc rối, khó theo dõi được quá trình xử lý. Mọi ngôn ngữ lập trình đều có những thao tác cơ bản là xử lý, rẽ nhánh và lặp. Như vậy, có thể tận dụng được các khái niệm trong ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng hiểu chính xác thuật toán. Một khi đã vay mượn cú pháp và khái niệm của ngôn ngữ lập trình thì chắc chắn mã giả sẽ bị phụ thuộc vào ngôn ngữ lập trình đó.

III. Hướng dẫn sử dụng mảng danh sách liên kết và ứng dụng 60 ký tự

Danh sách là tập hợp các phần tử dữ liệu có cùng kiểu được cấu trúc, sắp xếp (logic) theo một trật tự tuyến tính. Như vậy, danh sách tuyến tính là một chuỗi các phần tử, tồn tại phần tử đầu và phần tử cuối, mỗi phần tử có phần tử trước và phần tử sau. Các thao tác thường sử dụng nhất là thêm phần tử và xóa phần tử.

3.1. Ưu điểm và nhược điểm của Mảng Arrays trong lưu trữ dữ liệu

Ưu điểm của mảng là tìm kiếm dễ dàng (tuần tự hoặc tìm kiếm nhị phân), truy cập nhanh (ngẫu nhiên, thời gian truy cập đến mọi phần tử là như nhau), duyệt các phần tử dễ dàng sử dụng chỉ số. Nhược điểm là thêm và xóa không dễ dàng, danh sách thường xuyên thêm bớt phần tử => Không biết trước số phần tử, tốn bộ nhớ vì phải cấp phát nhiều hơn cần thiết để giữ chỗ. Thêm một phần tử thứ i vào mảng: Chuyển các phần tử từ I đến n xuống các vị trí từ i+1 đến n+1; Thêm phần tử cần thêm vào vị trí thứ i.

3.2. Ứng dụng thực tế của Danh sách liên kết Linked Lists và các dạng

Danh sách liên kết (Linked List) là một cấu trúc dữ liệu tuyến tính, bao gồm một chuỗi các node kết nối với nhau. Mỗi node có thể xem như một phần tử trong danh sách. Mỗi node sẽ lưu trữ dữ liệu (data) của node đó và địa chỉ (address) của node kế tiếp. Danh sách liên kết phải có node bắt đầu, được gọi là HEAD. Node cuối cùng được gọi là TAIL. Mỗi node có nhiều nhất 1 phần tử đứng trước cũng như có nhiều nhất 1 phần tử đứng sau. Có nhiều trường hợp trong thực tế có thể được lưu trữ bằng cách sử dụng Linked List như: danh sách học sinh, danh mục sách trong thư viện, danh bạ điện thoại, danh sách các nhân viên trong công ty.

3.3. So sánh hiệu năng giữa CTDL GT sử dụng mảng và danh sách liên kết

Danh sách liên kết đơn (singly linked list) có đặc điểm là mỗi node (phần tử) chỉ liên kết với node đứng sau nó trong danh sách. Mỗi node trong danh sách liên kết gồm 2 phần: Phần dữ liệu (data) dùng để lưu nội dung của node. Phần địa chỉ liên kết (address), thường ký hiệu là next, là các con trỏ có cùng kiểu với node. Các con trỏ này lưu trữ địa chỉ của node kế tiếp trong danh sách. Nếu là node cuối cùng thì con trỏ trỏ đến NULL. Có thể sử dụng kiểu dữ liệu cấu trúc (struct) để xây dựng một node.

IV. Bí quyết làm chủ ngăn xếp hàng đợi cây và đồ thị CNTT 59 ký tự

Ngăn xếp (stack) là một cấu trúc dữ liệu tuyến tính, hoạt động theo cơ chế LIFO (Last In First Out), tạm dịch là <vào sau ra trước=. Có nghĩa là phần tử nào được thêm vào sau trong stack thì sẽ được lấy ra trước. Hàng đợi (queue) là một mô hình mà tác động bổ sung vào nó được thực hiện ở một phía của nó và tác động loại bỏ một phần tử được thực hiện ở phía còn lại. Ta hình dung hàng đợi như một dãy người xếp hàng tại một quầy hàng để mua một mặt hàng nào đó mà chỉ có thể thêm vào hàng đợi từ cuối và bớt đi phần tử ở đầu của hàng đợi.

4.1. Ngăn xếp Stacks Cơ chế hoạt động LIFO và ứng dụng thực tế

Một ngăn xếp (stack) là một mô hình (cơ cấu) mà các tác động vào nó chỉ được thực hiện tại một phía của nó. Phía này được gọi là đỉnh của ngăn xếp. Trong tin học, một ngăn xếp là là một danh sách tuyến tính mà các tác động vào nó chỉ được thực hiện tại một phía của nó. Với kiểu ngăn xếp, ta chỉ có thể thực hiện các thao tác sau: Khởi tạo một ngăn xếp, đẩy (push) một phần tử mới vào ngăn xếp nếu ngăn xếp chưa đầy, lấy (pop) một phần tử ra khỏi ngăn xếp nếu ngăn xếp khác rỗng, kiểm tra xem ngăn xếp có hay không có phần tử (rỗng hay không), kiểm tra xem ngăn xếp đã đầy hay chưa.

4.2. Hàng đợi Queues Cơ chế FIFO và ứng dụng trong xử lý tác vụ

Trong tin học, một hàng đợi là một danh sách tuyến tính mà thao tác bổ sung chỉ được thực hiện ở một đầu và thao tác bớt đi được thực hiện ở phía còn lại của nó. Với kiểu hàng đợi, ta quy ước chỉ có thể thực hiện các thao tác sau: Khởi tạo một hàng đợi, đặt (put) một phần tử mới vào hàng đợi nếu hàng đợi chưa đầy, nhận lại (get) một phần tử từ hàng đợi nếu hàng đợi khác rỗng, kiểm tra xem hàng đợi có hay không có phần tử (rỗng hay không), kiểm tra xem hàng đợi đã đầy hay chưa. Vì vậy, khi nói đến hàng đợi ta hiểu đó là danh sách kiểu FIFO.

4.3. Khám phá cấu trúc Cây Trees và Đồ thị Graphs trong CNTT

Cây nhị phân là cây rỗng hoặc là cây mà mỗi nút có tối đa hai nút con. Hơn nữa các nút con của cây được phân biệt thứ tự rõ ràng, một nút con gọi là nút con trái và một nút con gọi là nút con phải. Ta qui ước vẽ nút con trái bên trái nút cha và nút con phải bên phải nút cha, mỗi nút con được nối với nút cha của nó bởi một đoạn thẳng. Đồ thị có hướng G = <V,E> bao gồm: V là một tập hữu hạn các đỉnh, E là một tập hữu hạn, có thứ tự các cặp đỉnh của V, gọi là cạnh.

V. Phương pháp sắp xếp và tìm kiếm dữ liệu hiệu quả 57 ký tự

Trong trường hợp số bản ghi cần tìm rất lớn, việc tìm kiếm tuần tự có thể là một giải pháp không hiệu quả về mặt thời gian. Một giải pháp tìm kiếm khác hiệu quả hơn có thể được sử dụng dựa trên mô hình <chia để trị<. Cây nhị phân tìm kiếm là một phương pháp tìm kiếm rất hiệu quả và được xem như là một trong những thuật toán cơ sở của khoa học máy tính.

5.1. Các thuật toán Sắp xếp Sorting phổ biến và độ phức tạp

Để làm được điều này, tập các phần tử cần phải được sắp, và sử dụng chỉ số của mảng để xác định nửa cần tìm. Đầu tiên, so sánh giá trị cần tìm với giá trị của phần tử ở giữa. Nếu nó nhỏ hơn, tiến hành tìm ở nửa đầu dãy, ngược lại, tiến hành tìm ở nửa sau của dãy. Quá trình được lặp lại tương tự cho nửa dãy vừa được xác định này. Trong thủ tục này, x là giá trị cần tìm trong dãy a. Hai biến left và right dùng để giới hạn phân đoạn của mảng mà quá trình tìm kiếm sẽ được thực hiện trong mỗi bước.

5.2. Tìm kiếm Searching nhị phân và ứng dụng trong CTDL GT

Để chèn 1 phần tử vào cây nhị phân tìm kiếm, đầu tiên tiến hành quá trình tìm kiếm nút cần chèn trong cây theo các bước như đã nói ở trên. Nếu tìm thấy nút trong cây, có nghĩa là cây đã tồn tại một nút có khóa bằng nút cần chèn và việc chèn thêm nút này vào cây là không hợp lệ. Nếu không tìm thấy nút trong cây thì quá trình tìm kiếm kết thúc không thành công và ta tiến hành chèn nút vào điểm kết thúc của quá trình tìm kiếm.

5.3. Đệ quy Recursion trong thiết kế giải thuật tìm kiếm và sắp xếp

Để xóa một nút khỏi cây nhị phân, ta xét các trường hợp sau: Xóa 1 nút lá: Thao tác xóa 1 nút không có nút con nào là trường hợp đơn giản nhất. Chỉ cần tiến hành loại bỏ nút ra khỏi cây. Xóa nút có 1 nút con: Tiến hành loại bỏ nút khỏi cây và thay nó bằng nút con. Xóa nút có 2 nút con: Tiến hành loại bỏ nút và thay thế nó bằng nút con ngoài cùng bên trái của cây con bên phải hoặc nút con ngoài cùng bên phải của cây con bên trái.

VI. Ứng dụng và tương lai của CTDL GT trong phát triển phần mềm 60 ký tự

Quá trình duyệt theo chiều rộng cũng bắt đầu từ một đỉnh nào đó của đồ thị. Tiếp đến, các đỉnh kề của nó sẽ được thăm, rồi tiếp tục đến các đỉnh kề của các đỉnh vừa thăm. Như vậy, quá trình duyệt theo chiều rộng không duyệt theo từng nhánh của đồ thị mà duyệt theo độ sâu của các đỉnh so với đỉnh ban đầu. Quá trình duyệt theo chiều sâu bắt đầu từ một đỉnh nào đó của đồ thị. Sau khi thăm đỉnh này, quá trình duyệt theo chiều sâu được lặp lại với tất cả các đỉnh kề của nó.

6.1. Ứng dụng của cấu trúc dữ liệu và giải thuật trong lập trình game

Để kiểm tra việc duyệt mỗi đỉnh đúng 1 lần, chúng ta sử dụng một mảng daxet gồm n phần tử (tương ứng với n đỉnh). Nếu đỉnh thứ i đã được duyệt, daxet[i]=1, ngược lại daxet[i]=0. Thuật toán tìm kiếm theo chiều sâu bắt đầu từ đỉnh v nào đó sẽ duyệt tất cả các đỉnh liên thông với v. Thủ tục DeepFirstSearch sẽ thăm tất cả các đỉnh cùng thành phần liên thông với v mỗi đỉnh đúng một lần.

6.2. Tầm quan trọng của CTDL GT trong phát triển ứng dụng di động

Với trình tự duyệt như trên, quá trình duyệt sẽ duyệt hết một nhánh của đồ thị rồi mới sanh nhánh khác. Do vậy, phương pháp duyệt này được gọi là duyệt theo chiều sâu.Ví dụ, với đồ thị ở trên, quá trình duyệt theo chiều sâu là bắt đầu từ đỉnh a sẽ cho thứ tự duyệt như sau: Sau khi thăm đỉnh a, tiến hành thăm đỉnh kề với a là b. Tiếp theo thăm đỉnh kề b là d. Đỉnh d không kề đỉnh nào, do vậy quay lại bước trước. Đỉnh b chỉ có 1 đỉnh kề là d đã thăm, do vậy quay trở lại bước trước.

Trích đoạn nội dung tài liệu

Chương 1: Giải thuật Chương 2: Cấu trúc dữ liệu Mặc dù có nhiều cố gắng, nhưng trong quá trình biên soạn, biên tập và in ấn khó tránh khỏi những thiếu sót. Chúng tôi rất mong nhận được sự đóng góp ý kiến từ phía các thầy cô và bạn đọc để hoàn thiện giáo trình hơn! Xin trân trọng cảm ơn! Hà Nội, ngày……tháng……năm……… Tham gia biên so¿n Trần Thị M¢ - Chủ biên 2 MþC LþC CH¯¡NG 1: GIÀI THUÀT. Các khái niám về giÁi thuÁt. Các đặc tr°ng của giÁi thuÁt.

Tính hiáu quÁ. Tính chính xác. Tính ứng dụng. Ngôn ngā dißn đ¿t giÁi thuÁt.

Ngôn ngā thông th°ờng. Ngôn ngā lÁp trình. Ph°¢ng pháp thiết kế giÁi thuÁt. Tinh chỉnh từng b°ớc.

11 CH¯¡NG 2: CÂU TRÚC DĀ LIàU. Danh sách tuyến tính. Danh sách liên kết. Danh sách liên kết đ¢n.

Các d¿ng khác của danh sách liên kết. Cây nhị phân. Biểu dißn cây nhị phân. Duyát cây nhị phân.

Cây nhị phân tìm kiếm. Duyát đồ thị theo chiều ráng. Duyát theo chiều sâu. 43 4 Tên môn hác: CÂU TRÚC Dþ LIàU VÀ GIÀI THU¾T Mã môn hác: MH10 Thái gian thāc hián môn hác: 60 giờ (Lý thuyết: 30 giờ; Thăc hành, thí nghiám, thÁo luÁn, bài tÁp: 27 giờ; Kiểm tra 03 giờ) I.

Vß trí, tính chÃt cÿa môn hác: - Vị trí: + Môn học đ°ợc bố trí ở kỳ học thứ 02. + Môn học tiên quyết: Không - Tính chÃt: là môn học c¢ sở ngành, cung cÃp các kiến thức c¢ bÁn về các khái niám c¢ bÁn, các kiểu cÃu trúc dā liáu thông dụng và mát số giÁi thuÁt trên các kiểu cÃu trúc dā liáu đó. Mÿc tiêu môn hác: 1. Về kiến thức: - Trình bày đ°ợc các khái niám về giÁi thuÁt, các đặc tr°ng của giÁi thuÁt; - Trình bày đ°ợc mát số ngôn ngā dißn đ¿t giÁi thuÁt; - Trình bày đ°ợc mát số ph°¢ng pháp thiết kế giÁi thuÁt; - Trình bày đ°ợc mát số kiểu dā liáu danh sách tuyến tính và thao tác trên kiểu dā liáu đó; - Trình bày đ°ợc mát số kiểu dā liáu danh sách liên kết và thao tác trên kiểu dā liáu đó; - Trình bày đ°ợc kiến thức về cây nhị phân, phép duyát và ứng dụng cây nhị phân tìm kiếm; - Trình bày đ°ợc kiến thức về đồ thị: biểu dißn đồ thị, phép duyát và ứng dụng của đồ thị.

Về kỹ năng: - VÁn dụng các kiểu dā liáu thông dụng nh° danh sách tuyến tính, cây nhị phân, đồ thị để cài đặt các ch°¢ng trình ứng dụng nhỏ. Về năng lăc tă chủ và trách nhiám: Có năng lăc tă định h°ớng, thích nghi với các môi tr°ờng làm viác khác nhau; tă học tÁp, tích lũy kiến thức, kinh nghiám để nâng cao trình đá chuyên môn nghiáp vụ. 5 CH¯¡NG 1: GIÀI THU¾T Mÿc tiêu bài hác 1. Cung cÃp cho ng°ời học các kiến thức c¢ bÁn về c¢ bÁn về giÁi thuÁt: các đặc tr°ng giÁi thuÁt, ngôn ngā dißn đ¿t giÁi thuÁt, ph°¢ng pháp thiết kế giÁi thuÁt, đánh giá đá phức t¿p của giÁi thuÁt trong mát số bài toán cụ thể.

CH¯¡NG 1: GIÀI THU¾T 1. Các khái niám vÁ giÁi thu¿t 1. 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, ? 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ể. CÃu trúc dÿ liáu 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. Để đá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: - CÃu trúc dā liáu phÁi tiết kiám tài nguyên (bá nhớ trong) - CÃu trúc dā liáu phÁi phÁn Ánh đúng thăc tế của bài toán - CÃu trúc dā liáu phÁi dß dàng trong viác thao tác dā liáu.

Các đặc tr°ng cÿa giÁi thu¿t - Tính xác định: Mßi b°ớc của thuÁt giÁi cần phÁi đ°ợc mô tÁ mát cách chính xác, chỉ có mát cách hiểu duy nhÃt. Bởi vì, nếu mát b°ớc có thể hiểu theo nhiều cách khác nhau, thì cùng mát dā liáu vào, nhāng ng°ời thăc hián thuÁt giÁi khác nhau có thể cho ra kết quÁ khác nhau. Nếu ta mô tÁ thuÁt giÁi bằng ngôn ngā tă nhiên, không có gì đÁm bÁo ng°ời đọc hiểu đúng ý của ng°ời viết thuÁt giÁi, bởi ngôn ngā tă nhiên th°ờng là đa nghĩa. Để đÁm bÁo đòi hỏi này, thuÁt giÁi cần đ°ợc mô tÁ trong mát ngôn ngā lÁp trình, chẳng h¿n mát ngôn ngā lÁp trình (Pascal, C.

trong các ngôn ngā này, các mánh đề đ°ợc t¿o thành theo các qui tắc cú pháp nghiêm nghặt và chỉ có mát ý nghĩa duy nhÃt. - Tính khả thi: TÃt cÁ các phép giÁi có mặt trong các b°ớc của thuÁt giÁi phÁi đủ đ¢n giÁn. Điều đó có nghĩa là các phép giÁi phÁi sao cho, ít nhÃt về nguyên tắc có thể 7 thăc hián đ°ợc bởi con ng°ời trong mát khoÁng thời gian hāu h¿n. Chẳng h¿n trong thuÁt giÁi Euclid, ta chỉ cần thăc hián các phép chia các số nguyên, các phép gán và các phép so sánh.

- Tính dừng: Với mọi bá dā liáu vào thoÁ mãn điều kián qui định, thuÁt giÁi phÁi dừng l¿i sau mát số hāu h¿n b°ớc thăc hián. Chẳng h¿n đối với thuÁt giÁi Euclid là thuÁt giÁi thoÁ mãn điều kián này. Bởi vì số d° r luôn nhỏ h¢n n, nếu r0 thì giá trị của n ở b°ớc sau là giá trị của r ở b°ớc tr°ớc, ta có n>r=n1>r1=n2>r2.Dãy số nguyên d°¢ng giÁm dần cần phÁi kết thúc ở 0, do đó sau mát số b°ớc giá trị của r=0 thuÁt giÁi dừng. Dÿ liáu vào - Input: Mßi thuÁt giÁi cần có mát số (có thể bằng không) dā liáu vào.

Đó là giá trị cần đ°a vào khi thuÁt giÁi bắt đầu làm viác. Dÿ liáu ra - Output: Mßi thuÁt giÁi cần có mát hoặc nhiều dā liáu ra. Đó là các giá trị có quan há xác định với giá trị vào và là kết quÁ của să thăc hián thuÁt giÁi. Tính hiáu quÁ Mát giÁi thuÁt nên là có thể thi hành đ°ợc với các nguồn có sẵn, tức là có khÁ năng giÁi quyết hiáu quÁ vÃn đề trong điều kián thời gian và tài nguyên cho phép.

Tính chính xác GiÁi thuÁt nên rõ ràng và không m¢ hồ. Mßi mát giai đo¿n (hay mßi b°ớc) nên rõ ràng và chỉ mang mát mục đích nhÃt định. Tính ứng dụng Mát giÁi thuÁt có tính phổ biến nếu giÁi thuÁt này có thể giÁi quyết đ°ợc mát lớp các vÃn đề t°¢ng tă. Tính hÿu h¿n Các giÁi thuÁt phÁi kết thúc sau mát số hāu h¿n các b°ớc.

Ngôn ngÿ dißn đ¿t giÁi thu¿t 1. Ngôn ngÿ thông thường Trong cách biểu dißn thuÁt giÁi theo ngôn ngā tă nhiên, ng°ời ta sÿ dụng ngôn ngā th°ờng ngày để liát kê các b°ớc của thuÁt giÁi (Các ví dụ về thuÁt giÁi trong mục 1 của ch°¢ng sÿ dụng ngôn ngā tă nhiên). Ph°¢ng pháp biểu dißn này không yêu cầu ng°ời viết thuÁt giÁi cũng nh° ng°ời đọc thuÁt giÁi phÁi nắm các quy tắc. Tuy vÁy, cách biểu dißn này th°ờng dài dòng, không thể hián rõ cÃu trúc của thuÁt giÁi, đôi lúc gây hiểu lầm hoặc khó hiểu cho ng°ời đọc.

Gần nh° không có mát quy tắc cố định nào trong viác thể hián thuÁt giÁi bằng ngôn ngā tă nhiên 1. Ngôn ngÿ lưu đồ L°u đồ hay s¢ đồ khối là mát công cụ trăc quan để dißn đ¿t các thuÁt giÁi. Biểu dißn thuÁt giÁi bằng l°u đồ sẽ giúp ng°ời đọc theo dõi đ°ợc să phân cÃp các tr°ờng hợp và quá trình xÿ lý của thuÁt giÁi. Ph°¢ng pháp l°u đồ th°ờng đ°ợc dùng trong nhāng thuÁt giÁi có tính rắc rối, khó theo dõi đ°ợc quá trình xÿ lý.

8 Các nút biểu diễn giải thuật bằng sơ đồ khối: Nút thao tác Nút điều khiển: trong đó ghi điều kián cần kiểm tra trong quá trình tính toán. Nút khởi đầu, kết thúc Cung Vẽ l°u đồ hoặc s¢ đồ khối, mßi khối mô tÁ mát b°ớc. Sÿ dụng mũi tên nối khối này với khối kia để chỉ trình tă thăc hián các b°ớc. Để dß dàng nhÁn biết chức năng của từng khối, mßi khối đ°ợc thể hián ở mát d¿ng nh° sau: Ví dụ: Tìm nghiám thăc của ph°¢ng trình bÁc hai ax2+bx+c=0.

ThuÁt toán gồm các b°ớc sau: + NhÁp dā liáu a, b, c. + Tính biát số  = b2-4ac. + So sánh  với 0. B°ớc tiếp theo sẽ phụ thuác vào giá trị của .

+ Nếu <0, đáp số của bài toán là <Vô nghiám=. + Nếu =0, tính và ghi đáp số trị của nghiám kép. + Nếu >0, tính và ghi đáp số trị của hai nghiám phân biát:. L°u đồ biểu dißn thuÁt toán này đ°ợc thể hián nh° sau: 9 1.

Ngôn ngÿ l¿p trình Tuy s¢ đồ khối thể hián rõ quá trình xÿ lý và să phân cÃp các tr°ờng hợp của thuÁt toán nh°ng l¿i cồng kềnh. Để mô tÁ mát thuÁt toán nhỏ ta phÁi dùng mát không gian rÃt lớn. Đôi khi, ta có thể thể hián thuÁt toán bằng ngôn ngā lÁp trình nào đó. Mọi ngôn ngā lÁp trình đều có nhāng thao tác c¢ bÁn là xÿ lý, rẽ nhánh và lặp.