(NB) Giáo trình Cấu trúc dữ liệu và giải thuật cung cấp cho sinh viên các kiến thức cơ bản về cấu trúc dữ liệu và giải thuật để làm nền tản cho việc lập trình giải quyết các vấn đề cần thiết.
TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Khái niệm giải thuật
Thuật toán, hay còn gọi là giải thuật, là một trong những khái niệm quan trọng nhất trong lĩnh vực tin học Thuật ngữ này có nguồn gốc từ nhà toán học Arập Abu Ja'far Mohammed ibn Musa al Khowarizmi, người sống vào khoảng năm 825.
Giải thuật thể hiện một giải pháp cụ thể, thực hiện từng bước một để đưa tới lời giải cho một bài toán.
Giải thuật là một tập hợp hữu hạn các phép toán cơ bản được sắp xếp theo quy tắc chính xác, nhằm giải quyết một bài toán cụ thể Nó bao gồm các quy tắc và quy trình nhất định, giúp giải quyết vấn đề trong một số bước hữu hạn và cung cấp kết quả từ tập hợp dữ liệu đầu vào.
Các phép toán cơ sở là những phép toán đơn giản với thời gian thực hiện hữu hạn, không phụ thuộc vào kích thước dữ liệu.
Các phép toán trong thuật toán cần được xác định rõ ràng và dễ hiểu, tránh sự mập mờ Đối với mọi bộ dữ liệu đầu vào đáp ứng điều kiện của bài toán, thuật toán phải hoàn thành và dừng lại sau một số bước hữu hạn.
Ngôn ngữ diễn đạt giải thuật
- Giả ngữ, là một ngôn ngữ ”tựa ngôn ngữ lập trình”.
- Ngôn ngữ lập trình (Pascal, C, ) Trong tài liệu này chúng ta sử dụng ngôn ngữ tựa Pascal để trình bày Sau đây là một số qui tắt cơ bản:
1.2.1 Quy cách về cấu trúc chương trình
Mỗi chương trình đều được phân biệt bằng một tên viết hoa, có thể bao gồm dấu gạch nối và bắt đầu bằng từ khóa "Program".
Ví dụ : Prorgram NHAN-MA-TRAN Độ dài tên không hạn chế.
Sau tên, có thể thêm phần thuyết minh bằng tiếng Việt để tóm tắt nhiệm vụ của giải thuật hoặc cung cấp một số thông tin cần thiết Phần thuyết minh này sẽ được đặt giữa hai dấu { }.
Chương trình bao gồm nhiều bước, mỗi bước được phân biệt bởi số thứ tự, có thể kèm theo những lời thuyết minh.
1.2.2 Kí tự và biểu thức
Kí tự dùng ở đây cũng giống như trong các ngôn ngữ chuẩn, nghĩa là gồm :
26 chữ cái Latinh in hoa hoặc in thường
Các dấu phép toán số học: +, - , *, /, (lũy thừa)
Các dấu phép toán quan hệ: , , , #.
Giá trị logic: true, false
Dấu phép toán logic: and, or, not
Tên biến là dãy chữ cái và chữ số, bắt đầu bằng chữ cái
Biến chỉ số có dạng : A[i], B[ij] v.v
Còn biểu thức cũng như thứ tự ưu tiên của các phép toán trong biểu thức cũng theo quy tắc như trong PASCAL hay các ngôn ngữ chuẩn khác.
Các câu lệnh trong chương trình được viết cách nhau bởi dấu chấm phảy chúng bao gổm :
Có dạng Tên biến/ Tên hàm : = Biểu thức Ở đây cho phép dùng phép gán chung.
Có dạng :beginCâu lệnh 1 ; Câu lệnh 2 ; ; Câu lệnh n end
Nó cho phép ghép nhiều câu lệnh lại để được coi như một câu lệnh.
Có dạng :if < Điều kiện > then < Câu lệnh >
Có thể diễn tả bởi sơ đồ :
Hoặc if < Điều kiện > then else < Câu lệnh 2 > Điều kiện Câu lệnh 1 false true
Case Điều kiện 1 : Câu lệnh 1 ; Điều kiện 2 : Câu lệnh 2 ;
…… Điều kiện n : Câu lệnh n ; Else: Câu lệnh n+1 End case
Câu lệnh này giúp phân biệt các tình huống xử lý khác nhau trong các điều kiện mà không cần sử dụng nhiều câu lệnh if – then – else Nó có thể được minh họa bằng sơ đồ.
Vài điểm linh động esle có thể không có mặt
Câu lệnh i (i = 1, 2, …, n) có thể được thay thế bằng một dãy các câu lệnh mà không cần phải đặt giữa : beginvà end.
Với số lần lặp biết trước : fori : = mto ndo< Câu lệnh>.
S 1 S 2 S n false false tru tru tru
Câu lệnh điều kiện true false cho phép thực hiện với biến i nhận giá trị nguyên từ m đến n (với điều kiện n ≥ m) và bước nhảy tăng bằng 1 Ngoài ra, cú pháp fori := n down to m do cũng tương tự, nhưng với bước nhảy giảm bằng 1.
Với số lần lặp không biết trước:
While < Điều kiện > do < Câu lệnh>
Chừng nào mà < Điều kiện > có giá trị bằng true thì thực hiện < Câu lệnh>
Hoặc : repeat< Câu lệnh>until< Điều kiện >
Lặp lại < Câu lệnh> cho tới khi < Điều kiện > có giá trị true.
Câu lệnh nhập: read ()
Câu lệnh xuất:write() các biến trong danh sách cách nhau bởi dấu phẩy.
Dòng kí tự là một dãy các kí tự đặt giữa hai dấu nháy’ ‘
Câu lệnh kết thúc chương trình:End
Chương trình con hàm Điều kiện Câu lệnh false true
Câu lệnh Điều kiện fasle true
Function ()
Chương trình con thủ tục
Function ()
Câu lệnh kết thúc chương trình ở đây là return thay cho end.
Trong cấu trúc của chương trình con hàm, luôn có câu lệnh gán với tên hàm ở vế trái, trong khi đó, chương trình con thủ tục không bao gồm câu lệnh gán này.
Lời gọi chương trình con hàm được thể hiện qua tên hàm và danh sách tham số thực sự trong biểu thức, trong khi lời gọi chương trình con thủ tục sử dụng câu lệnh call.
Call ()
Chú ý rằng trong các chương trình trình bày giải thuật, phần khai báo dữ liệu sẽ không được đề cập Thay vào đó, chúng tôi sẽ mô tả cấu trúc dữ liệu bằng ngôn ngữ tự nhiên trước khi tiến hành giải thuật.
Thiết kế giải thuật
Tạo lập giải thuật để giải một bài toán là một nghệ thuật mà không bao giờ có thể nêu đầy đủ ngay một lúc.
Có nhiều phương pháp thiết kế giải thuật, nhưng việc phân chia bài toán lớn thành các bài toán nhỏ hơn sẽ giúp đơn giản hóa quá trình giải quyết Bài toán có thể được coi như một Modul chính, chia thành các Modul con và tiếp tục phân chia cho đến khi đạt được các Modul đủ nhỏ để xử lý trực tiếp Sau đó, chỉ cần tổng hợp các phép xử lý để có giải thuật cho bài toán gốc Để thực hiện điều này, trước tiên cần xác định rõ dữ liệu và yêu cầu của bài toán, tức là cần biết dữ liệu đầu vào (input) và kết quả mong muốn (output) Tiếp theo, cần xác định các bước cần thực hiện để đáp ứng yêu cầu, tức là phải làm rõ các phương pháp để đạt được dữ liệu đầu ra.
Với mỗi công việc ấy thì “ phải làm thê nào “ ?
Để xây dựng giải thuật cần thiết, trước tiên cần cụ thể hóa các phép xử lý một cách dần dần Đồng thời, khi giải quyết câu hỏi “làm thế nào?”, việc định hình cấu trúc dữ liệu đầu vào cũng rất quan trọng.
Ví dụ, ta xét bài toán :
Sắp xếp là một dãy số ( a1,a2,….,an) thành một dãy số tăng dần.
• Như vậy dãy số input, nếu có dạng, chẳng hạn :(33, 77, 11, 55, 99, 22, 44, 88, 66) thì dãy số output phải có dạng :(11, 22, 33, 44, 55, 66, 77, 88, 99)
• Để có được kết quả output như vậy thì phải làm gì ?
Có thể thấy rằng : sắp xếp theo thứ tự tăng dần nghĩa là :
- Số bé nhất trong n số phải được đặt vào vị trí đầu tiên ;
- Số bé nhất trong (n – 1 ) số còn lại phải được đặt vào vị trí thứ hai ; v.v…Như vậy sẽ có hai công việc chính phải làm :
• Chọn số bé nhất trong dãy số chưa được sắp.
• Đặt nó vào vị trí sau phần tử cuối của dãy số đã được sắp ( nó lại trở thành phần tử cuối cho bước tiếp theo ).
Chú ý rằng : lúc đầu dãy số được sắp còn rỗng, sau đó nó được bổ sung dần dần các phần tử vào.
Các công việc trên sẽ được lặp lại (n - 1) lần : đầu với n số, lần cuối với 2 số.
• Để thực hiện được hai công việc nêu trên thì phải “làm thế nào ? ”
Đầu tiên, cần xác định dãy số được tổ chức theo cấu trúc dữ liệu nào và cách thức cài đặt của nó trong máy tính, điều này được gọi là cấu trúc lưu trữ.
Trong cấu trúc vectơ, thường có hai loại vectơ chính: vectơ input và vectơ output Câu hỏi đặt ra là liệu trong máy, chúng ta nên sử dụng cả hai vectơ để lưu trữ hay chỉ cần một trong số đó?
Giả sử chúng ta chỉ sử dụng một vectơ lưu trữ, nghĩa là ban đầu vectơ này chứa dãy số đã cho, nhưng sau khi thực hiện thuật toán, vectơ đó sẽ chứa dãy số đã được sắp xếp, nhằm tiết kiệm bộ nhớ.
Nếu thế thì công việc “đổi chỗ” sẽ được cụ thể thêm như sau :
Hoán vị số nhỏ nhất vừa được chọn với số ở đầu dãy chưa được sắp, sau đó loại bỏ nó ra khỏi dãy chưa được sắp Kết quả là số đó sẽ trở thành phần tử cuối cùng của dãy đã được sắp.
Tới đây ta có thể diễn đạt sơ bộ giải thuật “sắp xếp” của ta như sau :
{A là vectơ gồm n phần tử là các số cho}
1.{2 công việc được lặp lại (n-1) lần} for i:=1to (n-1)do begin.
2.Chọn số nhỏ nhất A[k] trong dãy các số:
Bây giờ ta đi sâu vào từng công việc :
• Làm thế nào để chọn được số nhỏ nhất trong dãy các số:
Để tìm phần tử cần thiết, ta bắt đầu bằng cách chọn A[i] làm phần tử khởi đầu Tiếp theo, so sánh các phần tử tiếp theo với A[i]; nếu phát hiện phần tử nào nhỏ hơn, ta sẽ thay thế A[i] bằng phần tử đó Quá trình này tiếp tục cho đến khi không còn phần tử nào nhỏ hơn, và phần tử cuối cùng được thay chính là phần tử cần tìm.
Để tìm phần tử nhỏ nhất trong mảng, ta chỉ cần xác định chỉ số k ứng với phần tử đó Quá trình "chọn" chỉ cần thực hiện với chỉ số k Đầu tiên, gán k = 1, coi phần tử đầu tiên là nhỏ nhất và lưu giữ chỉ số của nó Sau đó, lặp qua các phần tử từ i+1 đến n, nếu A[j] nhỏ hơn A[k], thì cập nhật k = j.
•Làm thế nào để thực hiện được việc hoán vị chỗ cho hai phần tử ?
Để giải quyết vấn đề này, ta có thể hình dung như việc hoán đổi hai cốc: một cốc chứa rượu và một cốc chứa nước Mục tiêu là chuyển rượu sang cốc nước và ngược lại, thực hiện sự chuyển đổi giữa hai chất lỏng này.
Rõ ràng điều này chỉ có thể thực hiện được khi ta dùng tới một cóc thứ ba làm cốc trung chuyển.
Từ đó ta có thể diễn đạt việc hoán vị giữa A[k] và A[i] như sau :
Tổng hợp những ghi nhận ở trên , ta đi tới một thủ tục , thể hiện giải thuật “sắp xếp” của ta ,bằng ngôn ngữ tựa PASCAL như sau :
Cách làm trên minh họa cho phương pháp thiết kế giải thuật được gọi là "phương pháp tinh chỉnh từng bước" (stepwise refinement) Việc cài đặt cấu trúc dữ liệu trong máy tính có thể khác nhau, do đó, để phân biệt, chúng ta gọi cấu trúc cài đặt trong máy của một "cấu trúc dữ liệu" là "cấu trúc lưu trữ" Điều này có nghĩa là cấu trúc lưu trữ có khả năng biểu diễn nhiều cấu trúc dữ liệu khác nhau.
Đánh giá giải thuật
Khi giải quyết một vấn đề, việc lựa chọn thuật toán phù hợp là rất quan trọng Để chọn được thuật toán tốt nhất, chúng ta thường dựa trên hai tiêu chí chính.
1 Thuật toán đơn giản, dễ hiểu, dễ cài đặt (dễ viết chương trình)
2 Thuật toán sử dụng tiết kiện nhất nguồn tài nguyên của máy tính, và đặc biệt, chạy nhanh nhất có thể được.
Khi viết chương trình chỉ để sử dụng ít lần, tiêu chuẩn về thời gian viết chương trình quan trọng hơn Tuy nhiên, nếu cần phát triển các chương trình để sử dụng nhiều lần cho nhiều người, thì thời gian chạy chương trình trở nên quan trọng hơn Ví dụ, các thủ tục sắp xếp và tìm kiếm được sử dụng rộng rãi trong nhiều bài toán khác nhau Trong trường hợp này, chúng ta cần tập trung vào việc cài đặt các thuật toán phức tạp, miễn là chương trình chạy nhanh hơn các giải pháp khác.
Tiêu chuẩn (2) được xem là tính hiệu quả của thuật toán Tính hiệu quả của thuật toán bao gồm hai nhân tố cơ bản
1 Dung lượng không gian nhớ cần thiết để lưu giữ các dữ liệu vào, các kết quả tính toán trung gian và các kết quả của thuật toán.
2 Thời gian cần thiết để thực hiện thuật toán (ta gọi là thời gian chạy chương trình, thời gian này không phụ thuộc vào các yếu tố vật lý của máy tính (tốc độ xử lý của máy tính, ngôn ngữ viết chương trình ))
Khi đánh giá độ phức tạp của thuật toán, chúng ta chỉ tập trung vào thời gian thực hiện Một thuật toán hiệu quả được định nghĩa là thuật toán có thời gian chạy ngắn hơn so với các thuật toán khác.
1.4.1.Đánh giá thời gian thực hiện của giải thuật
Có hai cách tiếp cận để đánh giá thời gian thực hiện của một thuật toán
Phương pháp thử nghiệm bao gồm việc viết chương trình và thực hiện chạy chương trình đó với các dữ liệu đầu vào khác nhau trên một máy tính Thời gian chạy chương trình sẽ phụ thuộc vào các yếu tố như cấu hình phần cứng, tối ưu hóa mã nguồn, và kích thước của dữ liệu đầu vào.
2 Chương trình dịch để chuyển chương trình nguồn thành chương trình mã máy.
3 Tốc độ thực hiện các phép toán của máy tính được sử dụng để chạy chương trình.
Thời gian chạy của chương trình phụ thuộc vào nhiều yếu tố khác nhau, do đó không thể xác định chính xác thời gian chạy bằng một đơn vị thời gian cụ thể, chẳng hạn như số giây.
Phương pháp lý thuyết xem thời gian thực hiện của thuật toán là hàm số của cỡ dữ liệu vào, mà cỡ dữ liệu này đóng vai trò quyết định đến thời gian thực hiện chương trình Cỡ dữ liệu vào được chọn tùy thuộc vào từng thuật toán cụ thể; ví dụ, với thuật toán sắp xếp mảng, cỡ dữ liệu là số thành phần của mảng, trong khi đối với hệ n phương trình tuyến tính, cỡ dữ liệu là n Thông thường, dữ liệu vào được xác định bằng một số nguyên dương n, và thời gian thực hiện của thuật toán được biểu diễn bằng hàm T(n), trong đó n là cỡ dữ liệu vào.
Thời gian thực hiện T(n) trong một thuật toán được xác định bởi số phép toán sơ cấp cần thực hiện Các phép toán sơ cấp, như các phép toán số học (+, -, *, /) và các phép toán so sánh (=, ), có thời gian thực hiện bị giới hạn bởi một hằng số, phụ thuộc vào cách cài đặt cụ thể.
1.4.2 Độ phức tạp tính toán của giải thuật
Khi đánh giá thời gian thực hiện bằng phương pháp toán học, chúng ta chỉ tập trung vào xác định độ lớn của thời gian thực hiện T(n) mà không xem xét các yếu tố phụ thuộc vào cách cài đặt Ký hiệu O (đọc là ô lớn) được sử dụng để mô tả độ lớn của hàm T(n).
Giả sử n là số nguyên không âm, T(n) và f(n) là các hàm thực không âm Ta viết T(n)
= O(f(n)) (đọc : T(n) là ô lớn của f(n)), nếu và chỉ nếu tồn tại các hằng số dương c và n 0 sao cho T(n)≤ c.f(n), với∀ n > n 0
Nếu một thuật toán có thời gian thực hiện T(n) = O(f(n)), chúng ta sẽ nói rằng thuật toán có thời gian thực hiện cấp f(n).
Vậy T(n) = O(n 2 ) Trong trường hợp này ta nói thuật toán có độ phức tạp (có thời gian thực hiện) cấp n 2
Bảng sau đây cho ta các cấp thời gian thực hiện thuật toán được sử dụng rộng rãi nhất và tên gọi thông thường của chúng.
Ký hiệu ô lớn Tên gọi thông thường
Danh sách trên sắp xếp theo thứ tự tăng dần của cấp thời gian thực hiện
Các hàm như log 2 n, n, nlog 2 n, n 2 , n 3 được gọi là các hàm đa thức Giải thuật với thời gian thực hiện có cấp hàm đa thức thì thường chấp nhận được.
Các hàm như 2^n, n! và n^n được phân loại là hàm loại mũ Những thuật toán có thời gian thực hiện tương ứng với các hàm loại mũ thường hoạt động rất chậm, gây khó khăn trong việc xử lý dữ liệu lớn.
2.Các kiểu dữ liệu cơ bản
Mục tiêu: Ghi nhớ được các kiểu dữ liệu cơ bản.
Kiểu dữ liệu là một tập hợp các giá trị và một tập hợp các phép toán trên các giá trị đó.
The Integer type encompasses a range of whole numbers from -32768 to 32767, along with operations such as addition, subtraction, multiplication, division, and modulus In contrast, the Boolean type consists of two values, {True, False}, and supports logical operations including and, or, and not.
Kiểu dữ liệu sơ cấp là kiểu dữ liệu mà giá trị của nó là đơn nhất.
Trong hầu hết các hệ thống ngôn ngữ lập trình, tồn tại các kiểu dữ liệu cơ bản được gọi là kiểu dữ liệu sơ cấp hoặc kiểu dữ liệu phân tử (atomic).
Thông thường, các kiểu dữ liệu cơ bản bao gồm :
Kiểu có thứ tự rời rạc : số nguyên, ký tự, logic, liệt kê, miền con
Kiểu không rời rạc : số thực
Các ngôn ngữ lập trình có thể định nghĩa các kiểu dữ liệu khác nhau Trong ngôn ngữ C, các kiểu dữ liệu bao gồm số nguyên, số thực và ký tự, với kiểu ký tự được coi là kiểu số nguyên về mặt lưu trữ Giá trị logic đúng (TRUE) và sai (FALSE) trong C được biểu diễn bằng các giá trị nguyên khác 0 và bằng 0 Ngược lại, Pascal định nghĩa rõ ràng tất cả các kiểu dữ liệu này và phân biệt chúng một cách chặt chẽ.
Sau đây là hệ kiểu của Pascal:
Kiểu dữ liệu String là một tập hợp các ký tự, bao gồm cả chuỗi rỗng, với độ dài tối đa lên đến 255 ký tự Điều này có nghĩa là một biến String có thể lưu trữ tối đa 255 ký tự trong một chuỗi.
Kiểu dữ liệu String trong pascal được khai báo như sau:
Var Biến 1 , Biến 2 ,… Biến n : String[số ký tự tối đa]
3.Kiểu bản ghi, kiểu con trỏ
Mục tiêu: Ghi nhớ được các kiểu dữ liệu bản ghi và kiểu dữ liệu con trỏ
Kiểu dữ liệu có cấu trúc, hay còn gọi là cấu trúc dữ liệu, là loại dữ liệu kết hợp nhiều giá trị khác nhau.
Một số kiểu dữ liệu có cấu trúc như: Bản ghi, con trỏ, Array,
Kiểu bản ghi
Bản ghi là một cấu trúc bao gồm nhiều phần tử khác nhau nhưng có mối liên hệ chặt chẽ với nhau Những phần tử này được gọi là các trường, và trong một bản ghi có thể tồn tại những trường mà chính chúng cũng là các bản ghi.
Kiểu dữ liệu bản ghi trong pascal được khai báo như sau:
Ví dụ: Khai báo kiểu dữ liệu bảng điểm gồm một số trường nhằm phục vụ quản lý điểm như sau:
Kiểu con trỏ
Khi khai báo một biến mặc nhiên ta qui định độ lớn vùng nhớ dành cho biến.
Var x : real; y : array[1 50] of integer; như vậy biến a cần 6 byte, biến b cần 100 byte.
Việc khai báo dung lượng bộ nhớ thường dựa trên phỏng đoán, dẫn đến tình trạng lãng phí khi chúng ta khai báo dư Địa chỉ lưu trữ biến và dung lượng bộ nhớ được xác định trong quá trình biên dịch, tạo thành các giá trị tĩnh không thay đổi trong suốt chương trình Để tiết kiệm bộ nhớ, chúng ta có thể yêu cầu cấp phát bộ nhớ động cho các biến trong khi chương trình đang chạy, thông qua việc sử dụng biến con trỏ, điều này đòi hỏi phải định nghĩa kiểu con trỏ trước.
Kiểu con trỏ là một kiểu dữ liệu đặc biệt dùng để biểu diễn các địa chỉ.
Kiểu con trỏ trong Pascal được khai báo như sau:
Type Tên kiểu con trỏ = ^Kiểu dữ liệu;
1.1.Nêu một vài cấu trúc dữ liệu cơ bản của một ngôn ngữ lập trình mà em biết.
1.2 Khai báo kiểu dữ liệu Nhân sự gồm một số trường: Mã nhân sự, họ tên, lương, địa chi, nhằm phục vụ quản lý nhân sự của một cơ quan.
4.Các kiểu dữ liệu trừu tượng
Mục tiêu: Ghi nhớ được khái niệm kiểu dữ liệu trừu tượng.
Kiểu dữ liệu trừu tượng là một mô hình toán học kết hợp với một tập hợp các phép toán được định nghĩa trên mô hình đó Nó đại diện cho một kiểu dữ liệu mà chúng ta định nghĩa ở mức khái niệm, chưa được thực hiện cụ thể trong ngôn ngữ lập trình.
Khi cài đặt một kiểu dữ liệu trừu tượng trên một ngôn ngữ lập trình ta thực hiện hai nhiệm vụ:
• Biểu diễn kiểu dữ liệu trừu tượng bằng một cấu trúc dữ liệu hoặc bằng một kiểu dữ liệu trừu tượng khác đã được cài đặt.
• Viết chương trình con thực hiện các phép toán trên kiểu dữ liệu trừu tượng Một số kiểu dữ liệu trừu tượng: Danh sách, cây, đồ thị,
5.M ố i quan h ệ gi ữ a CTDL và gi ả i thu ậ t
Mục tiêu: Ghi nhớ được mối quan hệ giữa việc xây dựng cấu trúc dữ liệu và xây dựng giải thuật cho bài toán.
Thực hiện một đề án tin học là quá trình chuyển đổi bài toán thực tế thành bài toán có thể giải quyết trên máy tính Mỗi bài toán thực tế đều bao gồm các đối tượng dữ liệu và yêu cầu xử lý liên quan Do đó, để xây dựng mô hình tin học chính xác, cần chú trọng đến hai vấn đề chính: xác định các đối tượng dữ liệu và các yêu cầu xử lý tương ứng.
• Tổ chức biểu diễn các đối tượng thực tế:
Các thành phần dữ liệu thực tế thường đa dạng và có mối quan hệ với nhau, vì vậy trong mô hình tin học, cần tổ chức và xây dựng các cấu trúc dữ liệu phù hợp Mục tiêu là phản ánh chính xác dữ liệu thực tế và dễ dàng cho 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:
Để đáp ứng các yêu cầu xử lý thực tế, cần thiết phải phát triển các giải thuật phù hợp nhằm xác định trình tự các thao tác mà máy tính cần thực hiện để đạt được kết quả mong muốn Đây là bước quan trọng trong việc xây dựng giải thuật cho bài toán.
Khi giải quyết bài toán trên máy tính, nhiều người thường chỉ tập trung vào việc xây dựng thuật toán mà quên đi tầm quan trọng của việc tổ chức dữ liệu Thuật toán thực hiện các phép xử lý, trong khi dữ liệu là đối tượng mà thuật toán tác động đến, chứa đựng thông tin cần thiết cho quá trình này Để chọn được thuật toán phù hợp, cần hiểu loại dữ liệu mà nó sẽ tác động, đồng thời khi lựa chọn cấu trúc dữ liệu, cần nắm rõ các thao tác sẽ thực hiện trên dữ liệu đó Chẳng hạn, để lưu trữ điểm số của sinh viên, người ta thường sử dụng số thực thay vì chuỗi ký tự để có thể tính toán trung bình điểm Do đó, trong một dự án tin học, thuật toán và cấu trúc dữ liệu có mối quan hệ chặt chẽ, thể hiện qua công thức.
Cấu trúc dữ liệu và giải thuật là hai yếu tố quan trọng trong việc phát triển chương trình Khi lựa chọn cấu trúc dữ liệu, cần chú ý đến các giải thuật tương ứng để đảm bảo tính hiệu quả Nếu cấu trúc dữ liệu thay đổi, giải thuật cũng cần được điều chỉnh để tránh sự không tự nhiên trong quá trình xử lý Một cấu trúc dữ liệu tốt không chỉ giúp giải thuật hoạt động hiệu quả hơn mà còn làm cho chúng dễ hiểu và đơn giản hơn.
Một chương trình quản lý điểm thi của sinh viên cần lưu trữ điểm số của ba sinh viên, mỗi sinh viên có bốn điểm số tương ứng với bốn môn học khác nhau.
Sinh viên Môn 1 Môn 2 Môn 3 Môn 4
Chỉ xét thao tác xư lý là xuất điểm số các môn của từng sinhviên.
Giả sử có các phương án tổ chức lưu trữ như sau:
Phương án 1 đề xuất sử dụng mảng một chiều để lưu trữ 12 điểm số, được tính từ 3 sinh viên (SV) và 4 môn học Cách khai báo mảng sẽ là: Type mang = array[1 12] of integer; var a: mang.
Khi đó mảng a các phần tử sẽ được lưu trữ như sau:
Để truy xuất điểm số môn j của sinh viên i, chúng ta cần xác định phần tử tại dòng i và cột j trong bảng Công thức để xác định chỉ số tương ứng trong mảng a sẽ được sử dụng để thực hiện việc này.
Bảng điểm (dòng i, cột j)⇒ a[ (i -1)*số cột + j ]
Để xác định điểm số của một sinh viên trong mảng, cần sử dụng công thức sau: a[i] ⇒ bảng điểm (dòng (i chia số cột) + 1), cột (i mod số cột).
The procedure for processing student scores is defined as follows: the procedure 'xuat' takes an array 'a' as an argument It initializes the variable 'so_mon' to 4, representing the number of subjects A loop iterates from 1 to 12, where 'sv' is calculated as the integer division of 'i' by 'so_mon', indicating the student number, and 'mon' is determined by the modulus operation, representing the subject number The output displays the score for each subject of each student, formatted as "The score for subject [mon] of student [sv] is: [a[i]]".
Phương án 2: sử dụng mảng hai chiều
Khai báo mảng hai chiều a có kích thước 3 dòng * 4 cột như sau type mang = array[1 3,1 4] of integer; var a : mang;
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- cũng chính là phần tử ở dòng i cột j trong mảng.
The procedure for processing student scores is defined as follows: The procedure named 'xuat' takes an array 'a' as input It initializes two integer variables, 'so_mon' and 'so_sv', representing the number of subjects and students, respectively, with values of 4 and 3 The procedure uses nested loops to iterate through each student and their corresponding subjects, outputting the score for each subject of every student in the format: 'Score for subject: [subject number] of student [student number] is: [score]'.
Phương án 2 mang lại cấu trúc lưu trữ tối ưu hơn cho dữ liệu thực tế so với phương án 1, điều này giúp cho các thuật toán xử lý trên cấu trúc dữ liệu của phương án 2 trở nên đơn giản và tự nhiên hơn.
1.3.Nêu một giải thuật mà độ phức tạp về thời gian của nó là O(1).
1.3 Giải thuật mà độ phức tạp về thời gian của nó là O(1), nếu thời gian thực hiện nó chỉ bằng một hằng số
Ví dụ : giải thuật tính và in X 2
ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY
Giải thuật đệ qui
Nếu giải thuật của một bài toán T được thực hiện bằng lời giải của một bài toán
T 1 có ý tưởng và nội dung giống bài toán T, nhưng kích thước của tham số bé hơn thì đó là lời giải đệ qui.
Chương trình đệ qui
Một chương trình con ( hàm hoặc thủ tục) được gọi là đệ qui nếu trong quá trình thực hiện nó có phần phải gọi tới chính nó.
Trong chương trình con đệ qui có hai phần:
Phần neo(phần dừng): Đặc tả công việc cụ thể cho một hay nhiều tham số.
Phần đệ qui (qui nạp): Công việc ứng với giá trị hiện thời của tham số được định nghĩa bằng công việc ứng với các giá trị khác.
3.Các bài toán đệ quy căn bản
Mục tiêu: Thực hành (lập trình và biên dịch) với các bài toán đệ quy đơn giản.
Bài toán tính n giai thừa
Hàm này được định nghĩa như sau:
Giải thuật đệ quy được viết dưới dạng hàm dưới đây:
Begin if n=0then Factorial:=1 else Factorial := n*Factorial(n-1);
Trong hàm trên lời gọi đến nó nằm ở câu lệnh gán sau else.
Mỗi lần gọi đệ quy hàm Factorial, giá trị của n sẽ giảm đi 1 Chẳng hạn, Factorial(4) sẽ gọi đến Factorial(3), tiếp theo là Factorial(2), Factorial(1), và cuối cùng là Factorial(0) Trường hợp Factorial(0) được xem là trường hợp suy biến và được định nghĩa đặc biệt là Factorial(0) = 1.
Bài toán dãy số FIBONACCI
Dãy số Fibonacci bắt nguồn từ bài toán cổ về việc sinh sản của các cặp thỏ Bài toán được đặt ra như sau:
- Các con thỏ không bao giờ chết.
- Hai tháng sau khi ra đời một cặp thỏ mới sẽ sinh ra một cặp thỏ con.
Khi một cặp thỏ mới sinh ra, mỗi tháng tiếp theo chúng sẽ sinh thêm một cặp con mới Do đó, nếu bắt đầu từ một cặp thỏ, sau tháng thứ n, số lượng cặp thỏ sẽ tăng lên đáng kể.
Ví dụ với n = 6, ta thấy.
Tháng thứ 1: 1 cặp (cặp ban đầu)
Tháng thứ 2: 1 cặp (cặp ban đầu vẵn chưa đẻ)
Tháng thứ 3: 2 cặp (đã có thêm 1 cặp con)
Tháng thứ 4: 3 cặp (cặp đầu vẫn đẻ thêm)
Tháng thứ 5: 5 cặp (cặp con bắt đầu đẻ)
Tháng thứ 6, số cặp thỏ được tính là F(n), với n là tháng thứ 6 Chỉ những cặp thỏ đã có mặt từ tháng thứ 4 (n-2) mới có khả năng sinh con Do đó, số cặp thỏ ở tháng thứ 6 sẽ phụ thuộc vào số cặp thỏ ở tháng thứ 4 và tháng thứ 5.
F(n) = f(n-2) + F(n-1) vì vậy F(n) có thể được tính như sau:
Dãy số thể hiện F(n) ứng với các giá trị của n = 1,
1 1 2 3 5 8 13 21 34 55 nó được gọi là dãy số Fibonacci Nó là mô hình của rất nhiều hiện tượng tự nhiên và cũng được sử dụng nhiều trong tin học.
Sau đây là thủ tục đệ quy thể hiện giải thuật tính F(n).
End; ở đây trường hợp suy biến ứng với 2 giá trị F(1) = 1 và F(2) = 1.
2.1 Giả sử a và b là những số nguyên dương Q là hàm số của a,b, được định nghĩa như sau:
2.2 Cho biết số Fibonacci F = 89 và F = 144
F a Hãy tính F b Viết một thủ tục không đệ quy ( dùng phép lặp) để tính và in ra n số Fibonacci đầu tiên.
2.3 Giải thuật tính ước số chung lớn nhất của 2 số p và q (p > q) được mô ta như sau ( giải thuật Euclide)
Gọi r là số dư trong phép chia p cho q :
-Nếu r = 0 thi q là ước số chung lớn nhất
Để tính ước số chung lớn nhất (ƯCLN) của hai số 1260 và 198, nếu r bằng 0, gán p giá trị của q, gán q giá trị của r, sau đó lặp lại quá trình này Hãy lập bảng ghi nhận các giá trị của p, q, r trong quá trình thực hiện Tính đệ quy trong phương pháp này cho thấy rằng ƯCLN có thể được tính bằng cách sử dụng hàm đệ quy, trong đó hàm sẽ gọi chính nó với các tham số được cập nhật cho đến khi đạt được điều kiện dừng.
USCLN ( p,q) c Viết một giải thuật đệ quy và một giải thuật không đệ quy (dùng phép lặp) để tính ước số chung lớn nhất của p,q
{ở đây F là một vecto có n phần tử để lưu trữ n số Fibonacci đầu tiên}
B1: {Tạo lập 2 số Fibonacci đầu tiên}
B2: {Tính lần lượt các số Fibonacci tiếp theo}
B3: {in lần lượt n số Fibonacci}
2.3 a Các giá trị của p,q,r được ghi nhận trong bảng sau: p q r
Để tính USCLN của ba số p, q và r, ta bắt đầu với USCLN của p và q, từ đó có thể suy ra USCLN của q và r khi r khác 0, vì q và r luôn nhỏ hơn p và q Phương pháp này có thể được thực hiện thông qua một giải thuật đệ quy hiệu quả.
{Chú ý là số dư r của p và q được xác định bởi phép tính p mod q}
{x, y, z ở đây là các biến cục bộ}
DANH SÁCH
Khái niệm danh dách
Trong công việc hàng ngày, danh sách là một công cụ phổ biến, chẳng hạn như danh sách các lớp nghề quản trị mạng hay danh sách sinh viên tham gia văn nghệ Tất cả các danh sách này đều có đặc điểm chung là chứa một số lượng phần tử hữu hạn, có thứ tự và số lượng phần tử có thể thay đổi linh hoạt.
Danh sách A được định nghĩa là một chuỗi các phần tử (a1, a2, , an), trong đó n là biến đại diện cho số lượng phần tử Vectơ thể hiện hình ảnh của danh sách này tại một thời điểm cụ thể.
Trong một danh sách, mỗi phần tử đều có vị trí riêng, bao gồm phần tử đầu tiên và phần tử cuối cùng Mỗi phần tử có thể có một phần tử đứng trước nó (trừ phần tử đầu) và một phần tử đứng sau nó (trừ phần tử cuối).
Các phép toán trên danh dách
Danh sách thường bao gồm các thao tác như khởi tạo danh sách rỗng, kiểm tra tính rỗng của danh sách, chèn phần tử mới và xóa phần tử hiện có Bên cạnh đó, còn có thể thực hiện nhiều phép toán khác liên quan đến danh sách.
Tìm kiếm một phần tử theo một tiêu chí xác định
Sắp xếp các phần tử theo một thứ tự ấn định
Ghép hai hoặc nhiều danh sách thành một danh sách lớn.
Tách một danh sách thành nhiều danh sách con v.v…
2.Cài đặt danh sách theo cấu trúc mảng
- Tổ chức cài đặt cho danh sách theo cấu trúc mảng và các phép toán tương ứng với cấu trúc dữ liệu.
- Giải được các bài toán sử dụng danh sách được cài đặt trên mảng.
Chúng ta có thể cài đặt danh sách bằng cách sử dụng mảng để lưu trữ liên tiếp các phần tử từ vị trí đầu tiên Để thực hiện điều này, cần ước lượng số phần tử của danh sách nhằm khai báo kích thước mảng phù hợp, đảm bảo số phần tử của mảng không được ít hơn số phần tử của danh sách Điều này dẫn đến việc mảng sẽ có một số chỗ trống Bên cạnh đó, chúng ta cần lưu giữ độ dài hiện tại của danh sách, thông tin này cho biết số lượng phần tử trong danh sách và phần nào của mảng còn trống.
Chúng ta mô tả danh sách được cài đặt bằng mảng như sau:
… Phần tử cuối cùng trong danh sách
Ta xem vị trí của một phần tử trong danh sách là chỉ số của mảng tại vị trí lưu trữ phần tử đó.
Các khai báo cần thiết là:
{Số nguyên thích hợp để chỉ độ dài của danh sách}
Kieuphantu; {kiểu của phần tử trong danh sách}
Position = integer; { Kiểu vị trí của các phần tử }
Tenkieumang = ARRAY [Chỉ số] OF Kieuphantu;
{mảng chứa các phần tử của danh sách }
Position Last; {giữ độ dài danh sách } end;
Bài viết này trình bày cách biểu diễn kiểu dữ liệu trừu tượng danh sách thông qua cấu trúc dữ liệu mảng Tiếp theo, chúng ta sẽ tìm hiểu cách cài đặt các phép toán cơ bản cho danh sách.
Khởi tạo danh sách rỗng
Danh sách rỗng là danh sách không có phần tử nào, tức là có độ dài bằng 0 Để khởi tạo danh sách rỗng, ta chỉ cần gán giá trị của trường Last, biểu thị vị trí phần tử cuối cùng, bằng 0.
Kiểm tra danh sách rỗng
Danh sách rỗng là một danh sách mà độ dài của nó bằng 0.
Chèn phần tử vào danh sách
Khi chèn phần tử có nội dung x vào tại vị trí p của danh sách L thì sẽ xuất hiện các khả năng sau:
Mảng đầy xảy ra khi mọi phần tử trong mảng đều chứa giá trị từ danh sách, dẫn đến phần tử cuối cùng của danh sách nằm ở vị trí cuối cùng của mảng Điều này có nghĩa là độ dài của danh sách bằng chỉ số tối đa của mảng Khi không còn chỗ cho phần tử mới, việc thêm phần tử trở nên không khả thi, và chương trình sẽ gặp lỗi.
- Ngược lại ta tiếp tục xét:
Nếu giá trị p không hợp lệ (p>last+1 hoặc p Last))
Write("Vi tri khong hop le");
Else begin {Dời các phần tử từ vị trí p đến cuối danh sách sang phải 1 vị trí}
{Tăng độ dài danh sách lên 1 } Last:=Last + 1;
Xóa phần tử khỏi danh sách
Xoá một phần tử ở vị trí p ra khỏi danh sách L chúng ta làm công việc ngược lại với xen.
Trước hết, cần xác định tính hợp lệ của vị trí phần tử cần xóa Nếu vị trí p lớn hơn L.last hoặc nhỏ hơn 1, thì đây không phải là vị trí hợp lệ của phần tử trong danh sách.
Nếu vị trí đã hợp lệ, cần di chuyển các phần tử từ vị trí p+1 đến cuối danh sách sang trái một vị trí, đồng thời giảm độ dài danh sách xuống 1 do đã xóa một phần tử.
Begin if ((PLast)) then
Write ("Vi tri khong hop le"); else if (Last
