(NB) Giáo trình Cấu trúc dữ liệu và giải thuật cung cấp cho người học những kiến thức như: Tổng quan về cấu trúc dữ liệu và giải thuật; Đệ quy và giải thuật đệ quy; Các phương pháp sắp xếp cơ bản;...Mời các bạn cùng tham khảo!
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à khái niệm quan trọng trong lĩnh vực tin học Thuật ngữ này có nguồn gốc từ 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ơ bả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 xử lý vấn đề trong một số bước nhất định, từ đó cung cấp kết quả dựa trên dữ liệu đầu vào.
Các phép toán cơ bản 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 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 một thuật toán được đánh giá qua khả năng thực thi các bước của nó để đạt được kết quả mong muốn, đồng thời thời gian thực hiện thuật toán cần phải được tối ưu để đảm bảo không quá dài.
Để đá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 Ví dụ về các phép tính sơ cấp bao gồm các phép cộng, trừ, nhân, 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 theo dõi quá trình xử lý dễ dàng hơn Để tạo sơ đồ khối cho thuật toán, cần phân biệt hai loại thao tác khác nhau.
Thao tác chọn lựa là quá trình đưa ra quyết định 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 rõ ràng cho thao tác chọn lựa trong lập trình.
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
Trong quá trình xử lý, các thao tác không thuộc loại chọn lựa được phân loại là hành động Ví dụ, thao tác "Chọn một hộp bất kỳ và để lên dĩa cân còn trống" được xem là một hành động cụ thể trong quy trình này.
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à không cần đến sơ đồ khối cồng kềnh Mặc dù sơ đồ khối giúp 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 việc mô tả một thuật toán nhỏ bằng sơ đồ khối thường chiếm nhiều không gian Mã giả giúp đơn giản hóa việc trình bày và dễ dàng theo dõi các bước thực hiện của thuật toán.
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 cả các thao tác lặp.
Khi viết mã giả cho thuật toán, chúng ta thường sử dụng cú pháp từ một ngôn ngữ lập trình cụ thể Mọi ngôn ngữ lập trình đều bao gồm các thao tác cơ bản như xử lý, rẽ nhánh và lặp lại.
Mã giả là công cụ hữu ích giúp người cài đặt dễ dàng hiểu nội dung thuật toán bằng cách kết hợp khái niệm từ ngôn ngữ lập trình và một phần ngôn ngữ tự nhiên Tuy nhiên, việc sử dụng cú pháp và khái niệm của ngôn ngữ lập trình cũng đồng nghĩa với việc mã giả sẽ bị ảnh hưởng bởi ngôn ngữ đó Do vậy, trong bài viết này, chúng ta sẽ chưa đi sâu vào tìm hiể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 phân biệt bằng một tên duy nhất, được viết bằng chữ in hoa, có thể kèm theo dấu gạch nối và luôn 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ể thêm phần thuyết minh bằng tiếng Việt để tóm tắt nhiệm vụ hoặc những chi tiết 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 : 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ý trong các điều kiện khác nhau mà không cần sử dụng nhiều câu lệnh if – then – else Nó có thể được diễn tả thông qua sơ đồ.
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
Với cấu trúc lặp xác định, ta có thể sử dụng câu lệnh "for i := m to n do " để thực hiện với i nhận các giá trị nguyên từ m đến n (với n ≥ m) và bước nhảy tăng 1 Tương tự, câu lệnh "for i := n down to m do " cho phép lặp từ n xuống m với bước nhảy giảm 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 Điều kiện Câu lệnh false true
S 1 S 2 S n tru e tru e tru e Chú thích:
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
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 lại không có đặc điểm 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" với cấu trúc cụ thể.
Call ()
Lưu ý: Trong các chương trình trình bày một thuật toán, phần khai báo dữ liệu sẽ không được đề cập Thay vào đó, chúng ta sẽ mô tả cấu trúc dữ liệu bằng ngôn ngữ tự nhiên trước khi bắt đầu giải thuật.
Câu lệnh Điều kiện fasle true
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
Trong thiết kế giải thuật, việc phân chia bài toán lớn thành những bài toán nhỏ hơn là một phương pháp hiệu quả Điều này cho phép chúng ta coi bài toán chính như một Modul, và từ đó chia thành các Modul con, tiếp tục chia nhỏ cho đến khi đạt được những Modul đủ nhỏ để xử lý trực tiếp Cuối cùng, chúng ta chỉ cần tổng hợp các kết quả xử lý để xây dựng giải thuật cho bài toán gốc.
Để giải quyết yêu cầu, cần xác định rõ dữ liệu đầu vào (input) và dữ liệu đầu ra (output) Việc làm này giúp hiểu rõ những gì cần được thực hiện để đạt được kết quả mong muốn Trước tiên, cần phân tích và làm rõ yêu cầu về dữ liệu đầu ra để có hướng giải quyết phù hợp.
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 dãy số được tổ chức theo cấu trúc dữ liệu nào và cách mà chúng được cài đặt 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ơ: vectơ input và vectơ output Vậy 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ố 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 sắp xếp, 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ị 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ố đó ra khỏi dãy chưa được sắp Khi đó, số nhỏ nhất đã trở thành phần tử cuối 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ử còn lại với A[i]; nếu phát hiện 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 tương ứng với phần tử đó Quy trình bắt đầu bằng việc 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 đó, ta thực hiện vòng lặp từ j:=i+1 đến n, trong đó nếu A[j] nhỏ hơn A[k], ta sẽ 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 giống như việc hoán đổi hai chất lỏng trong 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à chuyển chất lỏng từ cốc rượu sang cốc nước và ngược lại.
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 trong máy tính có thể khác nhau tùy thuộc vào từng hệ thống Để phân biệt, chúng ta gọi cấu trúc cài đặt này là cấu trúc cài đặt trong máy.
“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 chuẩn 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 phát triển một chương trình chỉ để sử dụng trong một thời gian ngắn, chi phí thời gian để viết chương trình có thể cao hơn nhiều so với lợi ích từ việc chạy chương trình đó Điều này đặt ra tiêu chuẩn cho việc xem xét tính hiệu quả và cần thiết của việc lập trình trong những trường hợp cụ thể.
Việc viết chương trình là rất quan trọng, đặc biệt khi cần tạo ra các thủ tục hoặc hàm để sử dụng nhiều lần cho nhiều người Trong những trường hợp này, chi phí thời gian chạy chương trình có thể vượt xa chi phí viết nó Ví dụ, các thủ tục 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 dựa trên tiêu chuẩn hiệu suất; việc cài đặt các thuật toán có thể phức tạp, nhưng điều quan trọng là chương trình phải chạy nhanh hơn so với 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 chủ yếu liên quan đến thời gian chạy Một thuật toán được coi là hiệu quả khi thời gian thực hiện của nó 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à chạy nó với các dữ liệu đầu vào khác nhau trên một máy tính Thời gian thực thi 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ố 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 chuẩn như 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 một 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ụ, 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 hệ phương trình tuyến tính n ẩn, cỡ được chọn là n Thời gian thực hiện của thuật toán sẽ đượ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ằng số phép toán sơ cấp cần thực hiện Các phép toán sơ cấp, như phép toán số học (+, -, *, /) và 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ể.
=, 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 xét đến các yếu tố phụ thuộc vào cách cài đặt Ký hiệu O (ô 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ũ Thời gian thực hiện của các thuật toán có độ phức tạp thuộc loại hàm này thường 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 modulus In contrast, the Boolean type consists of two values, True and 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ệ thống kiểu của ngôn ngữ lập trình, có một số loại dữ liệu được phân loại là kiểu dữ liệu sơ cấp hay 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ó các kiểu dữ liệu định nghĩa sẵn khác nhau Ví dụ, trong ngôn ngữ 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 và phân biệt rõ ràng 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 biến chứa các giá trị dưới dạng 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 chuỗi.
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 Những phần tử này được gọi là các trường, và trong một bản ghi có thể chứa các trường khác, tạo thành một bản ghi con.
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ớ khi chúng ta khai báo dư Địa chỉ lưu trữ biến và dung lượng bộ nhớ được cấp phát đượ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 hoạt động, thông qua biến con trỏ, yêu cầu 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ự, bao gồm một số lượng xác định n phần tử, với n được gọi là độ dài hoặc 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 vị trí của nó trong mảng 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ử có thể được hình dung như một dãy các phần tử nhớ được đánh số liên tiếp từ 0, với số thứ tự gọi là địa chỉ Mỗi phần tử nhớ có địa chỉ được gọi là một từ máy, và dữ liệu có thể được lưu trữ trong một ô nhớ bao gồm một hoặc nhiều từ máy Địa chỉ của từ máy đầu tiên trong ô nhớ sẽ xác định cách truy cập vào ô nhớ đó Có hai phương pháp chính để xác định địa chỉ trong bộ nhớ.
Cách đầu tiên để xác định địa chỉ trong việc lưu trữ dữ liệu là thông qua việc tính toán trực tiếp, 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 của ngôn ngữ lập trình, giúp tính toán địa chỉ của các phần tử trong mảng và xác định địa chỉ của các lệnh tiếp theo.
Cách thứ hai để lưu trữ địa chỉ là sử dụng con trỏ (pointer) hoặc mối nối (link), cho phép truy xuất các địa chỉ cần thiết từ một vị trí quy định Địa chỉ quay lui của chương trình con giúp trở về điểm gọi trong chương trình chính sau khi thực hiện xong chương trình con, đây chính là loại địa chỉ quan trọng trong lập trình.
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 lưu trữ một vectơ A một chiều với các phần tử A[i] (1 ≤ i ≤ n), mỗi phần tử cần một ô nhớ tương ứng với 1 từ máy Để lưu trữ toàn bộ vectơ A, ta cần dành ra n từ máy liên tiếp trong bộ nhớ, tương ứng với n phần tử của vectơ.
Khi mỗi phần tử của vectơ lưu trữ V yêu cầu từ máy để chứa một phần tử A[i], vectơ V cần có tổng cộng n* từ máy Địa chỉ của từng ô nhớ, tức là mỗi phần tử V[i], được xác định bởi địa chỉ của từ máy đầu tiên trong ô nhớ đó Chẳng hạn, 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à
Địa chỉ của phần tử A[i] trong một mảng có thể được tính bằng công thức: LOC(A[i]) = Lo + ω * (i - b) Đối với mảng hai chiều hay ma trận, các phần tử cũng được lưu trữ thông qua một vectơ tương tự 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, trong đó V 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ữ ma trận là theo thứ tự ưu tiên cột, trong đó các phần tử sẽ được lưu trữ lần lượ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 b1i 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à làm việ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ữ của mảng và xác định địa chỉ truy cập các phần tử mảng được xử lý bởi chương trình dịch.
Danh sách liên kết
Trong 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), bao gồm thông tin của phần tử và địa chỉ của nút tiếp theo Hình thức này cho phép các phần tử không cần lưu trữ kế cận trong bộ nhớ, khắc phục nhược điểm của mảng Tuy nhiên, 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 lưu trữ dữ liệu tương ứng với từng phần tử trong danh sách, trong khi trường LINK là kiểu 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, được sử dụng để đánh dấu nút kết thúc danh sách Địa chỉ này khác với các địa chỉ ở các nút khác và được gọi là "địa chỉ null" hay "mối nối không".
Để truy cập tất cả các nút trong danh sách, việc nắm rõ địa chỉ của nút đầu tiên là điều cần thiết, tức là phải “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, như đã đề cập trước đây, 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ỉ của 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 tiếp theo mà còn biết địa chỉ của nút trước đó Nút đầu tiên không có nút trước, do đó LPTR của nó có giá trị null, trong khi nút cuối cùng cũng có giá trị null vì không có nút nào theo sau.
Để truy cập vào danh sách theo cả hai chiều, cần phải có 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 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 chứa 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 phản ánh chính xác bài toán thực tế, cần chú trọng đến việc xác định các đối tượng dữ liệu và yêu cầu xử lý phù hợp.
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à phong phú, thường chứa những mối quan hệ nhất định Do đó, 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 thực tế và dễ dàng cho việc 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:
Để giải quyết 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 Đâ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 giải thuật mà bỏ qua tầm quan trọng của việc tổ chức dữ liệu Giải thuật thể hiện các phép xử lý, trong khi dữ liệu là đối tượng mà giải thuật tác động đến; dữ liệu chứa đựng thông tin cần thiết để thực hiện giải thuật Để chọn giải thuật phù hợp, cần xác định loại dữ liệu mà nó tác động, và khi lựa chọn cấu trúc dữ liệu, cần hiểu rõ các thao tác sẽ thực hiện trên dữ liệu đó Ví dụ, để biểu diễn đ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ự, 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 + Giải thuật = Chương trình
Khi lựa chọn một cấu trúc dữ liệu, cần xác định các giải thuật phù hợp đi kèm Sự thay đổi trong cấu trúc dữ liệu thường yêu cầu điều chỉnh các giải thuật để đảm bảo tính tự nhiên và hiệu quả trong xử lý Một cấu trúc dữ liệu tối ưu không chỉ nâng cao hiệu suất của giải thuật mà còn giúp chúng 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 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 Dữ liệu sẽ được tổ chức theo dạng bảng để dễ dàng tra cứu và quản lý.
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 xác định phần tử tại dòng i, cột j trong bảng Công thức để lấy 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ó thể được thực hiện thông qua lời giải của bài toán T1 tương tự, nhưng với kích thước tham số nhỏ hơn, thì đó được gọi là lời giải đệ quy.
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
Khi gọi hàm đệ quy Factorial, giá trị của n sẽ giảm dần, ví dụ như Factorial(4) sẽ gọi đến Factorial(3), sau đó là Factorial(2), Factorial(1) và cuối cùng là Factorial(0) Trường hợp Factorial(0) là đặc biệt, được tính là 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 đẻ)
Trong tháng thứ 6, có 8 cặp thỏ, trong đó các cặp thỏ con 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 ở 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 tính dựa trên 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
Để tính ước số chung lớn nhất (ƯCLN) của hai số 1260 và 198, nếu r khác 0, ta gán p bằng giá trị của q, gán q bằng giá trị của r, và lặp lại quá trình này a Cần lập bảng ghi nhận các giá trị của p, q, r trong quá trình thực hiện b Phương pháp này thể hiện tính đệ quy, từ đó có thể xây dựng một hàm tính ƯCLN theo cách đệ quy.
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 USCLN của q và r khi r khác 0, với q và r đều 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ộ}
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, 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ả danh sách đều có đặ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à số lượng phần tử có thể thay đổi.
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ó một phần tử đứng trước, và mỗi phần tử, ngoại trừ phần tử cuối, đều có một phần tử đứng sau.
Các phép toán trên danh dách
Danh sách thường có các thao tác cơ bản 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 đó, danh sách còn hỗ trợ nhiều phép toán khác nhau để quản lý và thao tác với dữ liệu hiệu quả.
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 cách sử dụng mảng để lưu trữ các phần tử liên tiếp từ vị trí đầu tiên Khi áp dụng phương pháp này, cần ước lượng số lượng phần tử của danh sách để 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 thường dẫn đến việc mảng có một số chỗ trống Đồng thời, cần phải 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ử hiện có và phần nào của mảng vẫn 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à độ dài của nó 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, đại diện cho 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 tất cả các phần tử trong mảng đã được lấp đầy bởi các phần tử của 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 của 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, dẫn đến việc không còn không gian cho phần tử mới Khi cố gắng thêm phần tử mới vào mảng đầy, 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ẽ làm cho danh sách L không còn đặc nữa, 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, cần xác minh tính hợp lệ của vị trí phần tử cần xóa 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í hợp lệ của phần tử trong danh sách.
Khi vị trí đã được xác nhận hợp lệ, cần di chuyển các phần tử từ vị trí p+1 đến cuối danh sách lên một vị trí phía trước, đồng thời giảm độ dài danh sách đi 1 do đã xóa một phần tử.
Begin if ((PLast)) then
Write ("Vi tri khong hop le"); else if (Last