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 then chốt trong lĩnh vực tin học Thuật ngữ này được đặt theo tên của nhà toán học Ả Rậ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 sắp xếp theo quy tắc chính xác để giải quyết một bài toán Nó bao gồm các quy tắc và quy trình cụ thể nhằm cung cấp kết quả từ một tập hợp dữ liệu đầu vào trong một số bước hữu hạn.
Các phép toán cơ sở là những phép toán đơn giản có thời gian thực hiện hữu hạn, không bị ảnh hưởng bởi kích thước dữ liệu.
Các phép toán trong giải thuật phải được xác định rỏ ràng, dễ hiểu, không mập mờ
Với mọi bộ dữ liệu vào thoả mãn các điều kiện của bài toán, thuật toán phải dừng lại sau một số hữu hạn các bước cần thực hiện
❖ Các đặc trưng của giải thuật:
• Dữ liệu vào: Mỗi thuật toán đều có một số giá trị nhập vào, chúng được gọi là Input data
• Dữ liệu ra: Mỗi thuật toán có một số giá trị đưa ra, chúng được gọi là
• Tính xác định: Mọi bước của một thuật toán bao giờ cũng được xác định rõ ràng, chính xác và do đó luôn thực hiện được
• Tính dừng: Sau một số hữu hạn các bước bài toán luôn được giải quyết
• Tính phổ dụng: Thuật toán có thể làm việc với các kiểu dữ liệu khác nhau trong miền xác định và luôn dẫn đến kết quả mong muốn
• Tính hiệu quả: Được thể hiện ở sự đúng đắn của thuật toán và độ phức tạp của thuật toán
Hiệu quả của thuật toán được đánh giá qua khả năng thực hiện các bước để đạt được kết quả mong muốn, đồng thời tổng thời gian thực hiện cần phải ngắn gọn và hợp lý.
Để đánh giá hiệu quả của các thuật toán, người ta thường sử dụng các đơn vị tính sơ cấp Tính hiệu quả của một thuật toán được đo bằng số lượng đơn vị tính sơ cấp mà nó yêu cầu thực hiện Các phép tính sơ cấp thường bao gồm các phép cộng, trừ, nhân và chia với các số tự nhiên nhỏ hơn 10.
Ngôn ngữ diễn đạt giải thuật
• Sử dụng ngôn ngữ tự nhiên: Sử dụng ngôn ngữ thường ngày để biểu diễn các bước của thuật toán
Phương pháp biểu diễn này không yêu cầu người viết thuật toán cũng như người đọc thuật toán 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 toán, đôi lúc gây hiểu lầm hoặc khó hiểu cho người đọc
• Sử dụng sơ đồ khối (flowchart): Lưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật toán
Biểu diễn thuật toán 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 toán
Phương pháp lưu đồ là công cụ hữu ích trong việc biểu diễn các thuật toán phức tạp, giúp dễ dàng theo dõi quá trình xử lý Để xây dựng sơ đồ khối cho thuật toán, cần phân biệt rõ hai loại thao tác khác nhau.
Thao tác chọn lựa trong lập trình được thực hiện dựa trên một điều kiện cụ thể Ví dụ, câu lệnh "nếu a = b thì thực hiện thao tác B2, ngược lại thực hiện B4" minh họa cho quá trình ra quyết định này.
Thao tác chọn lựa được biểu diễn bằng một hình thoi, bên trong chứa biểu thức điều kiện
Các thao tác xử lý không thuộc loại chọn lựa được phân loại là hành động Ví dụ, câu "Chọn một hộp bất kỳ và để lên dĩa cân còn trống" minh họa cho một thao tác hành động cụ thể.
Thao tác xử lý được biểu diễn bằng một hình chữ nhật, bên trong chứa nội dung xử lý
Sử dụng mã giả (pseudocode) là một phương pháp hiệu quả để mô tả thuật toán một cách ngắn gọn và dễ hiểu Mặc dù sơ đồ khối thể hiện rõ ràng quá trình xử lý và phân cấp các trường hợp của thuật toán, nhưng chúng thường cồng kềnh và chiếm nhiều không gian Do đó, mã giả là lựa chọn lý tưởng cho việc mô tả các thuật toán nhỏ mà không cần sử dụng quá nhiều diện tích.
Lưu đồ chỉ phân biệt hai thao tác chính là rẽ nhánh (chọn lựa có điều kiện) và xử lý, trong khi thực tế, các thuật toán còn bao gồm thêm thao tác lặp.
Khi viết mã giả cho một thuật toán, chúng ta thường sử dụng cú pháp của một ngôn ngữ lập trình cụ thể Mỗi ngôn ngữ lập trình đều có các thao tác cơ bản như xử lý, rẽ nhánh và lặp lại.
Dùng mã giả vừa 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 nắm bắt nội dung thuật toán
Mã giả vẫn sử dụng một phần ngôn ngữ tự nhiên, nhưng khi vay mượn cú pháp và khái niệm từ ngôn ngữ lập trình, nó sẽ trở nên phụ thuộc vào ngôn ngữ đó Do đó, trong bài viết này, chúng ta sẽ chưa xem xét sâu về mã giả.
• Sử dụng ngôn ngữ lập trình (code):Pascal, C, C++, C#,
1.2.1 Quy cách về cấu trúc chương trình
Mỗi chương trình được xác định bởi một tên duy nhất, được viết bằng chữ in hoa và có thể kèm theo dấu gạch nối, 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 giải thuật, có thể kèm theo một 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ố chi tiết cần thiết Phần thuyết minh này đượ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 : begin Câu lệnh1 ; Câu lệnh2 ; ; Câu lệnhn 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ệnh2>
Case Điều kiện1: Câu lệnh1; Điều kiện2: Câu lệnh2;
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 diễn tả bằng sơ đồ.
S 1 S 2 S n false false tru e tru e tru e Chú thích:
Câu lệnh Điều kiện true false Điều kiện Câu lệnh 1 false true
Vài điểm linh động esle có thể không có mặt
Câu lệnhi(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 : begin và end
Câu lệnh lặp với số lần lặp biết trước có thể được thực hiện bằng cách sử dụng cú pháp "for i := m to n do ", cho phép i nhận giá trị nguyên từ m đến n (với n ≥ m) và tăng dần từng bước một Tương tự, cú pháp "for i := n down to m do " cho phép i giảm dần từ n về m 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
Câu lệnh Điều kiện fasle true Điều kiện Câu lệnh false true
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
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 nằm ở vế trái, trong khi đó, chương trình con thủ tục không sử dụng 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 Đối với chương trình con thủ tục, lời gọi được thực hiện bằng câu lệnh call.
Call ()
Lưu ý 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ẽ được lược bỏ 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 những bài toán nhỏ hơn sẽ giúp đơn giản hóa quá trình giải quyết Chúng ta có thể xem bài toán chính như một Modul, sau đó 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 Cuối cùng, chỉ cần tổng hợp các kết quả xử lý để có được giải thuật cho bài toán gốc Để thực hiện điều này, khi đối mặt với một bài toán, chúng ta cần tuân theo một quy trình nhất định.
Để xác định rõ ràng dữ liệu và yêu cầu, cần làm rõ dữ liệu đầu vào (input) và dữ liệu đầu ra (output) Để giải quyết yêu cầu, cần xác định các bước cần thực hiện, tập trung vào việc xác định dữ liệu đầu ra một cách cụ thể.
Với mỗi công việc ấy thì “ phải làm thê nào “ ?
Trên cơ sở đó mới cụ thể hóa dần dần các phép xử lí để xây dựng giải thuật cần thiết
Tất nhiên, khi giải quyết câu hỏi “ làm thế nào ?” thì dữ liệu input cũng phải được định hình về cấu trúc
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 :
• Để 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ànhphầ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 cấu trúc của dãy số, tức là cấu trúc dữ liệu mà nó được định hình Tiếp theo, cần xem xét cách mà dãy số này được cài đặt trong máy, hay còn gọi là cấu trúc lưu trữ.
Trong cấu trúc vectơ, thường có hai loại vectơ: vectơ input và vectơ output Điều này đặt ra câu hỏi liệu máy sẽ sử dụng cả hai vectơ để lưu trữ hay chỉ cần một trong số chúng.
Giả sử chúng ta chỉ sử dụng một vectơ lưu trữ ban đầu chứa dãy số cho trước Sau khi thực hiện thuật toán, vectơ này sẽ được cập nhật để chứa dãy số đã được sắp xếp, giúp 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ị trí của số nhỏ nhất vừa được chọn với số ở đầu dãy chưa được sắp Sau đó, loại bỏ số này ra khỏi dãy chưa được sắp, biến nó thành phần tử cuối cùng của dãy đã được sắp.
Tới đây ta có thể diễn ddajt 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:=1 to (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ử nhỏ nhất trong mảng, bắt đầu bằng cách chọn A[i] làm phần tử đầu tiên Tiếp theo, so sánh các phần tử tiếp theo với A[i]; nếu có phần tử nào nhỏ hơn, 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ử đó Bắt đầu với k:=1, coi phần tử đầu tiên là nhỏ nhất và lưu lại chỉ số của nó Sau đó, sử dụng vòng lặp từ j:=i+1 đến n, nếu A[j] nhỏ hơn A[k], ta 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, chúng ta có thể hình dung như việc có hai cốc khác nhau: một cốc chứa rượu và một cốc chứa nước Mục tiêu là hoán đổi vị trí của hai chất lỏng này, tức là chuyển rượu sang cốc chứa nước và đưa nước vào cốc đang đựng rượu.
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 phản ảnh một phương pháp thiết kế giải thuật, gắn liền với lập trình được gọi là "phương pháp tinh chỉnh từng bước" (stepwise refinement)
Cách cài đặt cấu trúc dữ liệu trên máy tính điện tử có thể khác nhau, vì vậy chúng ta cần phân biệt giữa các cấu trúc cài đặt trong máy của một hệ thống cụ thể.
“cấu trúc dữ liệu” là “cấu trúc lưu trữ” Như vậy nghĩa là cấu trúc lưu trữ có thể biểu diễn được 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 một chương trình chỉ để sử dụng trong một thời gian ngắn, chi phí cho việc phát triển chương trình thường cao hơn so với lợi ích từ việc chạy chương trình đó.
Việc viết chương trình có thể tốn thời gian, nhưng trong nhiều trường hợp, việc phát triển các thủ tục hoặc hàm để sử dụng nhiều lần cho nhiều người sẽ tiết kiệm thời gian chạy chương trình hơn Các thủ tục như sắp xếp và tìm kiếm thường được sử dụng rộng rãi trong nhiều bài toán khác nhau Do đó, chúng ta cần chú ý đến hiệu suất của thuật toán, và có thể cài đặt những thuật toán phức tạp miễn là chương trình hoạt động nhanh hơn các thuật toán 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 ))
Chúng ta sẽ tập trung vào thời gian thực hiện của thuật toán, vì đánh giá độ phức tạp thực chất là đánh giá thời gian chạy Một thuật toán được coi là hiệu quả khi thời gian chạy của nó thấp 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 của chương trình sẽ bị ảnh hưởng bởi nhiều yếu tố khác nhau.
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ố, 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 trong phân tích thuật toán xem thời gian thực hiện của thuật toán là hàm số phụ thuộc vào cỡ dữ liệu vào Cỡ dữ liệu vào, thường được biểu diễn bằng số nguyên dương n, là yếu tố quyết định ảnh hưởng đến thời gian thực hiện chương trình Việc xác định cỡ dữ liệu vào phụ thuộc vào từng thuật toán cụ thể; ví dụ, đối với thuật toán sắp xếp mảng, cỡ dữ liệu vào là số thành phần của mảng, trong khi đối với giải hệ n phương trình tuyến tính, cỡ được chọn là n 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) của 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à phép 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ể.
=, là các phép toán sơ cấp
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à n0 sao cho T(n) c.f(n), với n > n0
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ư log2n, n, nlog2n, 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ư 2n, n! và nn đượ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 này thường có tốc độ rất chậm.
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 various operations such as addition, subtraction, multiplication, division, and modular arithmetic In contrast, the Boolean type consists of two values, True and False, and supports 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 một số 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 khác nhau có thể định nghĩa các kiểu dữ liệu sẵn có một cách khác biệt 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 xem như một 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, ngôn ngữ Pascal định nghĩa rõ ràng và phân biệt tất cả các kiểu dữ liệu này.
Sau đây là hệ kiểu của Pascal:
Kiểu dữ liệu String là một loại dữ liệu chứa các giá trị là chuỗi ký tự, bao gồm cả chuỗi rỗng Độ dài tối đa của một biến String là 255 ký tự, cho phép nó lưu trữ tối đa 255 ký tự trong một dãy.
Kiểu dữ liệu String trong pascal được khai báo như sau:
Var Biến1 , Biến 2 ,… Biếnn : String[số ký tự tối đa]
3.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 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 Các 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 khác 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 chỉ là phỏng đoán và có thể dẫn đến lãng phí bộ nhớ do khai báo dư Địa chỉ lưu trữ biến và dung lượng bộ nhớ được xác định khi biên dịch, tạo thành các đại lượng tĩnh không thay đổi trong suốt quá trình thực hiện 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, điều này được thực hiện thông qua biến con trỏ, đò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:
Tên kiểu con trỏ = ^Kiểu dữ liệu;
Bài tập thực hành của học viên
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
5 Các cấu trúc lưu trữ
Mục tiêu:Ghi nhớ được các cấu trúc lưu trữ cơ bản: lưu trữ kế tiếp và lưu trữ móc nối
Mảng
Mảng là một tập hợp có thứ tự gồm n phần tử, với n được gọi là độ dài hay kích thước của mảng Mỗi phần tử trong mảng không chỉ có giá trị mà còn được xác định bởi chỉ số, thể hiện thứ tự của nó Tất cả các giá trị của phần tử trong mảng đều thuộc cùng một kiểu dữ liệu.
Vectơ là mảng một chiều, mỗi phần tử của nó ứng với một chỉ số
Ví dụ: phần tử của vectơ A, kí hiệu là Ai hoặc A[i] với i là chỉ số
Ma trận là mảng hai chiều, mỗi phần tử của nó ứng với 2 chỉ số
Ví dụ : phần tử của ma trận B, kí hiệu Bij hoặc B[i,j] với i gọi là chỉ số hàng, j gọi là chỉ số cột
Tương tự người ta cũng mở rộng : mảng ba chiều, mảng bốn chiều,… Mảng n chiều
5.1.2 Cấu trúc lưu trữ của mảng
Bộ nhớ của máy tính điện tử (MTĐT) có thể được hình dung như một dãy các phần tử nhớ cơ sở được đánh số liên tiếp, bắt đầu từ số 0, với số thứ tự gọi là địa chỉ Mỗi phần tử nhớ cơ sở có địa chỉ được gọi là một từ máy Dữ liệu có thể được lưu trữ trong máy thông qua một ô nhớ, bao gồm một hoặc nhiều từ máy, và việc truy cập vào ô nhớ này được xác định bởi địa chỉ của từ máy đầu tiên trong ô nhớ đó Có hai cách chính để xác định địa chỉ trong bộ nhớ.
Cách đầu tiên để xác định địa chỉ trong lưu trữ dữ liệu là thông qua việc tính toán trực tiếp, được gọi là địa chỉ được tính Phương pháp này thường được áp dụng trong các trình biên dịch ngôn ngữ lập trình, giúp xác định địa chỉ của các phần tử trong mảng cũng như địa chỉ của các lệnh tiếp theo cần thực hiện.
Một phương pháp hiệu quả để quản lý địa chỉ trong lập trình là lưu trữ chúng tại một vị trí quy định, từ đó có thể dễ dàng truy xuất khi cần thiết Các địa chỉ này được gọi là con trỏ (pointer) hoặc mối nối (link) Đặc biệt, địa chỉ quay lui của chương trình con giúp quay trở lại vị trí gọi trong chương trình chính sau khi chương trình con hoàn tất thực hiện, là một ví dụ điển hình của loại địa chỉ này.
Cũng có một số cấu trúc lưu trữ sử dụng phối hợp cả hai cách xác định địa chỉ nói trên
Lưu trữ kế tiếp đối với mảng:
Thông thường mảng được lưu trữ trong máy dưới dạng môt vecter lưu trữ Đó là một dãy các từ máy kế tiếp nhau
Khi xem xét việc lưu trữ một mảng một chiều hay vectơ A với các phần tử A[i] (1 ≤ i ≤ n), nếu mỗi phần tử được lưu trong một ô nhớ tương ứng với 1 từ máy, thì để lưu trữ vectơ A, cần phải dành ra n từ máy liên tiếp trong bộ nhớ Điều này có nghĩa là n phần tử của vectơ sẽ được lưu trữ một cách liên tiếp.
Khi mỗi phần tử của vectơ V yêu cầu từ máy để lưu trữ, thì vectơ V cần có tổng cộng n * từ máy Địa chỉ của mỗi phần tử V[i] tương ứng với địa chỉ của từ máy đầu tiên trong ô nhớ đó Ví dụ, nếu = 3 và địa chỉ của V[1] là 1000, thì địa chỉ của V[2] sẽ là 1003 và V[3] sẽ là 1006.
Hình 2.1 Địa chỉ của V[1] được gọi là địa chỉ gốc (base address ), kí hiệu là L0
Như vậy việc xác định địa chỉ của V[i], hay nói một cách khác : việc xác định địa chỉ của A[i] sẽ được tính ra theo công thức sau :
Trong ngôn ngữ như PASCAL, cận dưới của chỉ số không nhất thiết phải là
1, mà có thể là môt số nguyên b nào đó Khi ấy địa chỉ của A[i] được tính bởi :
LOC (A[i]) = Lo + * (i-b) Đối với mảng 2 chiều, hay ma trận, việc lưu trữ các phần tử cũng được thực hiện bởi một vectơ lưu trữ như trên
Ma trận B có m hàng và n cột sẽ được lưu trữ trong bộ nhớ thông qua vectơ lưu trữ V Vectơ này bao gồm m*n* từ máy, với mỗi phần tử của V chiếm từ máy.
Nếu giả sử B có 3 hàng, 4 cột (m=3, n=4) thì các phần tử của nó sẽ được lưu trữ như hình sau:
Như vậy nghĩa là : các phần tử của ma trận B sẽ được lưu trữ theo hàng, hết hàng này đến hàng khác
Cách lưu trữ này được gọi là : lưu trữ theo thứ tự ưu tiên hàng
Một phương pháp khác để lưu trữ dữ liệu là theo thứ tự ưu tiên cột, trong đó các phần tử của ma trận được sắp xếp và lưu trữ lần lượt theo từng cột, từ cột này sang cột khác.
Với ma trận B[3,4] như trên thì các phần tử sẽ được lưu trữ bởi vectơ lưu trữ V theo hình 2.3 :
Việc xây dựng các công thức tính địa chỉ cũng được tiến hành tương tự
Nếu ma trận B có m hàng, n cột và mỗi phần tử của vectơr lưu trữ V gồm
từ máy, thì địa chỉ của B[i,j] với 1 i , j n :
Theo thứ tự ưu tiên hàng sẽ được tính bởi :
Theo thứ tự ưu tiên hàng cột sẽ được tính bởi :
Trường hợp b1 i u1, b2 j u2 thì mỗi hàng sẽ có (u2 – b2+1) phần tử Khi đó công thức tính địa chỉ, chẳng hạn : theo thứ tự ưu tiên hàng, sẽ là :
Người ta cũng mở rộng cách lưu trữ tương tự đối với mảng nhiều chiều Chú ý:
Truy cập vào phần tử của mảng diễn ra nhanh chóng và đồng đều nhờ vào việc sử dụng "địa chỉ được tính" để truy cập trực tiếp.
Khi sử dụng cấu trúc mảng trong lập trình, chúng ta chỉ cần khai báo mảng và thao tác với tên mảng cùng các biến số Các vấn đề liên quan đến cấu trúc lưu trữ và xác định địa chỉ để truy cập các phần tử mảng sẽ được chương trình dịch xử lý tự động.
Danh sách liên kết
Trong cấu trúc tổ chức danh sách liên kết, mỗi phần tử được lưu trữ trong một ô nhớ gọi là “nút” (node), chứa thông tin cần thiết và địa chỉ của nút tiếp theo Cách tổ chức này cho phép các phần tử không cần lưu trữ liền kề trong bộ nhớ, khắc phục nhược điểm của mảng, nhưng việc truy xuất một phần tử yêu cầu phải qua một số phần tử khác Có nhiều kiểu tổ chức liên kết giữa các phần tử trong danh sách.
Danh sách liên kết đơn: mỗi phần tử liên kết với phần tử đứng sau nó trong danh sách:
Như vậy quy cách của mỗi nút có thể hình dung như sau:
Nghĩa là mỗi nút gồm có 2 trường
Trường INFO chứa thông tin liên quan đến từng phần tử trong danh sách, trong khi trường LINK là một con trỏ chứa địa chỉ của nút tiếp theo trong danh sách.
Nút cuối cùng trong danh sách không có nút tiếp theo, vì vậy trường LINK của nó cần chứa một "địa chỉ đặc biệt" mang tính quy ước để đánh dấu nút kết thúc danh sách Địa chỉ này được gọi là "địa chỉ null" hay "mối nối không", khác với các địa chỉ ở các nút khác.
Để truy cập vào tất cả các nút trong danh sách, điều quan trọng là phải biết địa chỉ của nút đầu tiên, hay còn gọi là "nắm được" con trỏ.
L, trỏ tới nút đầu tiên này
Danh sách liên kết kép: mỗi phần tử liên kết với các phần tử đứng trước và sau nó trong danh sách:
Mỗi nút trong danh sách này lại có hai trường con trỏ, theo quy cách như sau:
Ngoài trường INFO, còn có trường LPTR để lưu trữ địa chỉ của nút bên trái (nút trước nó) và trường RPTR để ghi nhận địa chỉ nút bên phải (nút sau nó).
Trong cấu trúc danh sách liên kết đôi, mỗi nút không chỉ lưu trữ địa chỉ của nút kế tiếp mà còn biết địa chỉ của nút trước đó Nút đầu tiên không có nút nào đứng trước, vì vậy LPTR của nó có giá trị null, trong khi nút cuối cùng cũng có giá trị LPTR là null.
Để truy cập danh sách theo cả hai chiều, cần phải sử dụng hai con trỏ: con trỏ L để trỏ tới nút đầu tiên và con trỏ R để trỏ tới nút cuối cùng.
Danh sách liên kết vòng : phần tử cuối danh sách liên kết với phần tử đầu danh sách:
Bài tập thực hành của học viên
1.3.Các cấu trúc dữ liệu cơ bản của một ngôn ngữ lập trình có đủ đáp ứng mọi yêu cầu về tổ chức dữ liệu không?
1.4.Viết công thức tính địa chỉ của phần tử mảng một chiều và mảng hai chiều Cho mảng AA[15 100], BB[5 30, 7 50], biết địa chỉ gốc L = 500 và mỗi phần tử ứng với ω = 4 từ máy, mảng BB được lưu trữ theo thứ tự ưu tiên hang Tính AA[55], AA[90], BB[15,15], BB[25,40]
6 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 yêu cầu 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 có các đối tượng dữ liệu và yêu cầu xử lý tương ứng Do đó, để xây dựng mô hình tin học phản ánh chính xác bài toán thực tế, cần tập trung vào hai vấn đề quan trọng: xác định đối tượng dữ liệu và các yêu cầu xử lý liên quan.
• 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ế rất đa dạng và thường có mối quan hệ với nhau Vì vậy, trong mô hình tin học của bài toán, cần tổ chức và xây dựng các cấu trúc dữ liệu phù hợp để phản ánh chính xác các dữ liệu này và dễ dàng xử lý bằng máy tính 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 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, từ đó hình thành bướ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 giải thuật mà bỏ qua tầm quan trọng của tổ chức dữ liệu Giải thuật thực hiện các phép xử lý, trong khi dữ liệu là đối tượng chính mà giải thuật tác động đến, chứa đựng thông tin cần thiết để thực hiện các thao tác Để chọn được giải thuật phù hợp, cần hiểu rõ loại dữ liệu mà nó tác động và các thao tác sẽ được thực hiện trên dữ liệu đó Ví dụ, để biểu diễn điểm số của sinh viên, nên sử dụng số thực thay vì chuỗi ký tự, vì cần thực hiện thao tác tính trung bình Do đó, trong một dự án tin học, giải thuật 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 để tạo ra một chương trình hiệu quả Khi lựa chọn cấu trúc dữ liệu, cần phải tìm kiếm các giải thuật tương ứng phù hợp Sự thay đổi trong cấu trúc dữ liệu thường kéo theo sự điều chỉnh của giải thuật để đảm bảo tính tự nhiên và hiệu quả trong quá trình xử lý Một cấu trúc dữ liệu tối ưu không chỉ giúp giải thuật hoạt động tốt hơn mà còn làm cho giải thuật trở nên dễ hiểu và đơn giản hơn.
Một chương trình quản lý điểm thi cho sinh viên cần lưu trữ điểm số của 3 sinh viên, mỗi sinh viên có 4 điểm tương ứng với 4 môn học khác nhau Dữ liệu sẽ được tổ chức theo dạng bảng để dễ dàng truy xuất và quản lý thông tin.
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: Sử dụng mảng một chiều có tất cả 3(SV) * 4(Môn) = 12 điểm số cần lưu trữ, do đó ta khai báo mảng như sau:
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, ta cần tìm 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 ]
ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY
Giải thuật đệ qui
Giải thuật của bài toán T được xem là lời giải đệ quy nếu nó được thực hiện thông qua lời giải của bài toán T1 có ý tưởng và nội dung tương tự, nhưng với kích thước tham số nhỏ hơn.
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=0 then 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 khi hàm đệ quy Factorial được gọi, giá trị của n sẽ giảm dần cho đến khi đạt giá trị 0 Chẳng hạn, Factorial(4) sẽ lần lượt gọi đến Factorial(3), Factorial(2), Factorial(1) và cuối cùng là Factorial(0), trường hợp này được xử lý đặc biệt với giá trị 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 đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới
Giả sử bắt đầu từ một cặp thỏ mới ra đời thì đến tháng thứ n sẽ có bao nhiêu cặp?
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ố lượng cặp thỏ đạt 8 cặp, trong đó các cặp thỏ đã có từ tháng thứ 4 vẫn tiếp tục sinh sản Đặt F(n) là số cặp thỏ ở tháng thứ n, ta nhận thấy chỉ những cặp thỏ xuất hiện từ tháng thứ n-2 mới có khả năng sinh con trong tháng thứ n Do đó, số cặp thỏ ở tháng thứ n được xác định bởi quy luật này.
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, 2, 3, 4 , có dạng
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
3.3 Bài toán tháp Hà Nội
⚫ Bài toán tháp Hà nội Ngôi đền Benares có n đĩa bằng vàng:
- Có bán kính khác nhau
- Chồng lên nhau ở một chiếc cọc
- Theo thứ tự đĩa lớn ở dưới, đĩa nhỏ ở trên Các nhà sư lần lượt chuyển các đĩa sang một cọc khác theo quy tắc sau:
⚫ Khi chuyển một đĩa phải đặt vào một trong 03 cọc
⚫ Mỗi lần chỉ chuyển đúng một đĩa trên cùng tại một cọc và đặt vào trên cùng ở cọc chuyển đến
⚫ Đĩa lớn hơn không được phép đặt lên đĩa nhỏ hơn
⚫ Ví dụ, với trường hợp n=2 ta có thể chuyển như sau:
⚫ Chuyển đĩa nhỏ sang cọc 3
⚫ Chuyển đĩa lớn sang cọc 2
⚫ Chuyển đĩa từ cọc 3 sang cọc 2
⚫ Nếu n=1 thì chuyển đĩa duy nhất đó từ cọc 1 sang cọc 2 Kết thúc
Giả thiết ta có cách chuyển (n-1) đĩa từ cọc 1 sang cọc 2:
⚫ Cách chuyển (n-1) đĩa từ cọc 2 sang cọc 3 cũng làm tương tự
⚫ Chuyển đĩa lớn nhất đang ở cọc 1 sang cọc 2
⚫ Chuyển (n-1) đĩa từ cọc 3 sang cọc 2
⚫ Kết thúc c) Đánh giá về đệ quy Ưu điểm:
– Mạnh, rõ ràng, chặt chẽ
– Thiết kế TT đơn giản
– Lời gọi hàm tốn rất nhiều thời gian
– Dễ phát sinh chạy vô hạn
Bài tập thực hành của học viên
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 11 = 89 và F 12 = 144 a Hãy tính F 16 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
Nếu r khác 0, gán p bằng q, gán q bằng r và lặp lại quá trình Để tính ước số chung lớn nhất (ƯCLN) của hai số 1260 và 198, cần lập bảng ghi nhận các giá trị của p, q, r trong từng bước thực hiện Tính đệ quy trong phương pháp này cho thấy rằng ƯCLN có thể được xác định thông qua việc lặp lại các phép gán cho đến khi r bằng 0 Từ đó, có thể xây dựng một hàm đệ quy để tính ƯCLN.
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 p và q, ta có thể sử dụng phương pháp đệ quy, trong đó USCLN của p và q sẽ dẫn đến việc tính USCLN của q và r khi r khác 0 Chú ý rằng q và r luôn nhỏ hơn p và q Cuối cùng, kết quả tính toán cho USCLN là USCLN (1260, 198) = 18.
{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ộ}
Yêu cầu về đánh giá kết quả học tập:
- Đưa ra các nội dung, sản phẩm chính ;
- Cách thức và phương pháp đánh giá ;
- Gợi ý tài liệu học tập ;
DANH SÁCH
Khái niệm danh dách
Trong công việc hàng ngày, danh sách đóng vai trò quan trọng và phổ biến, bao gồm các danh sách như lớp nghề quản trị mạng và danh sách sinh viên tham gia văn nghệ.
Tất cả các danh sách đều có điểm chung là chứa một số lượng hữu hạn các phần tử, được sắp xếp theo thứ tự và có thể thay đổi về số lượng phần tử.
Có thể hình dung : danh sách A là một dãy các phần tử : (a1,a2, ,an)với n là một biến
Vectơ chính là hình ảnh của một danh sách tại một thời điểm nào đó
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ử, ngoại trừ phần tử đầu, đều có phần tử đứng trước nó, trong khi phần tử cuối không có phần tử nào đứng sau.
Các phép toán trên danh dách
Danh sách thường bao gồm các phép 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ử vào danh sách và xóa phần tử khỏi danh sách 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
Chúng ta có thể cài đặt danh sách bằng mảng bằng cách sử dụng một mảng để lưu giữ liên tiếp các phần tử từ vị trí đầu tiên Khi áp dụng cách cài đặt này, cần ước lượng số phần tử của danh sách để khai báo kích thước mảng cho phù hợp, đảm bảo rằng số phần tử của mảng không ít hơn số phần tử của danh sách Do đó, mảng sẽ có một số chỗ trống Bên cạnh đó, 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 cũng như 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 tôi sẽ cài đặt các phép toán cơ bản liên quan đến 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, chỉ cần gán giá trị của trường Last, đại diện cho vị trí phần tử cuối cùng trong danh sách, 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 phần tử từ danh sách, với phần tử cuối cùng của danh sách nằm ở vị trí cuối cùng trong mảng Điều này có nghĩa là độ dài của danh sách tương ứng với 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ử sẽ không thể thực hiện được 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 < 1), chương trình sẽ gặp lỗi Khi p < 1, p không phải là một vị trí hợp lệ trong danh sách Ngược lại, nếu p > L.last + 1, việc chèn sẽ khiến danh sách L không còn tính chất của một danh sách đặc, vì sẽ tồn tại một vị trí trong mảng mà không có nội dung.
Nếu vị trí p hợp lệ thì chúng ta tiến hành xen theo các bước sau:
+ Dời các phần tử từ vị trí p đến cuối danh sách ra sau 1 vị trí
+ Độ dài danh sách tăng 1
+ Đưa phần tử mới vào vị trí p
Chương trình con chèn phần tử x vào vị trí p của danh sách L có thể viết như sau:
Procedure Insert_List(X : Kieuphantu, P : Position);
Begin if (Last=MaxLength) then
Write("Danh sach day"); else if ((P < 1) or (P > Last))
Write("Vi tri khong hop le");
{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 tiên, hãy xác định xem vị trí phần tử cần xóa có hợp lệ hay không Nếu p lớn hơn L.last hoặc p nhỏ hơn 1, thì vị trí này không phải là vị trí của phần tử trong danh sách.
Khi vị trí đã được xác nhận hợp lệ, các phần tử từ vị trí p+1 đến cuối danh sách cần được di chuyển lên một vị trí trước, đồng thời độ dài danh sách sẽ giảm đi 1 do đã xóa một phần tử.
Begin if ((PLast)) then
Write ("Vi tri khong hop le"); else if (Last
