Các bước phân tích thuật toán
Bước đầu tiên trong phân tích thuật toán là xác định đặc trưng dữ liệu đầu vào và lựa chọn phương pháp phân tích phù hợp Mục tiêu lý tưởng là có một phân bố thời gian hoạt động tương ứng với bất kỳ phân bố dữ liệu đầu vào nào Tuy nhiên, điều này không thể đạt được với các thuật toán không tầm thường, do đó, chúng ta tập trung vào việc chứng minh rằng thời gian chạy của thuật toán luôn nhỏ hơn một “chặn trên” nhất định, bất kể dữ liệu đầu vào ra sao, và tính toán thời gian chạy trung bình cho dữ liệu đầu vào ngẫu nhiên.
Bước thứ hai trong phân tích thuật toán là nhận diện các thao tác trừu tượng, nhằm tách biệt phân tích với cài đặt Ví dụ, chúng ta phân tích số lượng phép so sánh trong một thuật toán sắp xếp mà không cần quan tâm đến thời gian thực hiện trên một máy tính cụ thể Yếu tố đầu tiên phụ thuộc vào tính chất của thuật toán, trong khi yếu tố thứ hai phụ thuộc vào đặc điểm của máy tính Việc tách biệt này cho phép so sánh các thuật toán một cách độc lập, không bị ảnh hưởng bởi cài đặt hay máy tính cụ thể.
Bước thứ ba trong quá trình phân tích thuật toán là phân tích toán học nhằm xác định giá trị trung bình và trường hợp xấu nhất cho từng đại lượng cơ bản Việc tìm chận trên cho thời gian chạy chương trình không quá khó, nhưng điều quan trọng là xác định chận trên tốt nhất, tức thời gian chạy trong trường hợp xấu nhất Phân tích trường hợp trung bình thường yêu cầu kỹ thuật toán học phức tạp hơn so với trường hợp xấu nhất Khi hoàn tất quá trình phân tích dựa trên các đại lượng cơ bản, nếu thời gian liên quan đến mỗi đại lượng được xác định rõ, chúng ta có thể xây dựng các biểu thức tính toán thời gian chạy.
Về lý thuyết, việc phân tích chính xác tính năng của một thuật toán phụ thuộc vào khả năng của máy tính cụ thể và bản chất toán học của các đại lượng trừu tượng Tuy nhiên, thay vì đi vào chi tiết cụ thể, thường người ta sẽ đưa ra các ước lượng để đơn giản hóa quá trình phân tích.
Biểu diễn giải thuật
Ngôn ngữ tự nhiên – liệt kê theo bước
Trong việc biểu diễn thuật toán bằng ngôn ngữ tự nhiên, người ta sử dụng ngôn ngữ hàng ngày để mô tả các bước thực hiện mà không cần tuân theo quy tắc cụ thể nào Tuy nhiên, phương pháp này thường dài dòng và có thể gây nhầm lẫn cho người đọc, do không rõ ràng về cấu trúc của thuật toán Mặc dù không có quy tắc cố định, để tăng tính dễ đọc, các bước con nên được lùi vào bên phải và đánh số theo quy tắc phân cấp như 1, 1.1, 1.1.1,
Ví dụ 1.5 Thuật toán giải phương trình bậc hai
Bước 1: Nhập ba hệ số a, b, c (giả sử a khác 0)
3.2: Nếu delta = 0 thì “Phương trình có nghiệm kép x = -b/2a”
Tính x1 = (-b + sqrt(delta))/(2a) Tính x2 = (-b - sqrt(delta))/(2a) Kết luận phương trình có hai nghiệm phân biệt x1 và x2
Sơ đồ khối
Lưu đồ hay sơ đồ khối (flow-chart) là công cụ trực quan hữu ích để diễn đạt thuật toán, giúp người đọc theo dõi sự phân cấp các trường hợp và quá trình xử lý Phương pháp này thường được áp dụng cho những thuật toán phức tạp, khó theo dõi Để biểu diễn thuật toán qua sơ đồ khối, cần phân biệt hai loại thao tác: thao tác chọn lựa dựa trên điều kiện (ví dụ: "nếu a = b thì thực hiện thao tác B2, ngược lại thực hiện B4") và thao tác hành động (chẳng hạn như "Nhập vào hệ số a của phương trình bậc hai").
- Thao tác chọn lựa – decision: đượ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 (biểu thức so sánh)
- Thao tác xử lý – process: được biểu diễn bằng một hình chữ nhật, bên trong chứa nội dung xử lý tương ứng a = b D > 0
Đường đi trong router sử dụng biểu tượng cung tên để chỉ dẫn hướng cho hai bước liên tiếp Từ thao tác chọn lựa, có hai hướng đi: một hướng tương ứng với điều kiện thỏa mãn và một hướng cho điều kiện không thỏa mãn.
Chúng ta sử dụng hai cung xuất phát từ các đỉnh của hình thoi, với ký hiệu Đúng (Yes) để chỉ ra hướng đi khi điều kiện được thỏa mãn, và ký hiệu Sai (No) để chỉ ra hướng đi khi điều kiện không được thỏa mãn.
Điểm cuối (terminator) là điểm khởi đầu và kết thúc của một thuật toán, được biểu diễn bằng hình oval với chữ "Bắt đầu" (Begin) hoặc "Kết thúc" (End) Điểm cuối chỉ có cung đi ra từ điểm khởi đầu hoặc cung đi vào tại điểm kết thúc.
Điểm nối, hay còn gọi là connector, là thành phần quan trọng trong lưu đồ, giúp kết nối các phần khác nhau lại với nhau Bên trong điểm nối, chúng ta thường sử dụng các ký hiệu để thể hiện mối liên hệ giữa các điểm nối, với các ký hiệu này thường được đánh số đồng nhất để dễ nhận biết.
Điểm nối sang trang (Off page connector) là một thành phần quan trọng trong lưu đồ, được sử dụng khi lưu đồ quá lớn và cần phải phân chia ra nhiều trang Trong mỗi điểm nối sang trang, cần đặt đồng nhất ký hiệu để dễ dàng nhận biết mối liên hệ giữa các điểm nối trên các trang khác nhau.
Hình 1.1 Lưu đồ thuật toán giải phương trình bậc hai
Mã giả
Sơ đồ khối mặc dù 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 lại cồng kềnh và tốn không gian cho những thuật toán nhỏ Hơn nữa, lưu đồ chỉ phân biệt giữa hai thao tác là rẽ nhánh và xử lý, trong khi thực tế, các thuật toán còn bao gồm nhiều thao tác lặp khác.
Khi biểu diễn thuật toán bằng mã giả, chúng ta sử dụng cú pháp từ một ngôn ngữ lập trình nhất định để minh họa Tất cả các 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 Việc sử dụng mã giả không chỉ giúp tận dụng các khái niệm trong ngôn ngữ lập trình mà còn tạo điều kiện thuận lợi cho việc chuyển đổi sang ngôn ngữ lập trình đó.
Ví dụ 1.6 Đoạn mã giả giải phương trình bậc hai if (Delta > 0)
{ x1 = (-b - sqrt(delta))/(2*a) x2 = (-b + sqrt(delta))/(2*a) xuất kết quả: phương trình có hai nghiệm là x1 và x2
} else if (delta == 0) xuất kết quả: phương trình có nghiệm kép là -b/(2*a) else xuất kết quả: phương trình vô nghiệm
Phân tích – Đánh giá giải thuật
Độ phức tạp không gian
Độ phức tạp không gian của thuật toán được xác định bằng tổng chi phí bộ nhớ cần thiết cho việc thực hiện thuật toán.
Chi phí về mặt bộ nhớ được tính dựa trên
- Bộ nhớ lưu trữ dữ liệu đầu vào
- Bộ nhớ lưu trữ dữ liệu đầu ra
- Bộ nhớ lưu trữ các kết quả trung gian
Độ phức tạp thời gian
Độ phức tạp thời gian của một thuật toán được xác định bằng tổng thời gian cần thiết để hoàn thành nó, dựa trên số lượng thao tác thực hiện trên bộ dữ liệu đầu vào.
Các thao tác được xem xét khi đánh giá độ phức tạp thời gian:
- Phép so sánh hai đại lượng
- Phép cộng, trừ, nhân và chia
- Phép gán, phép thay đổi
- Chất lượng của mã máy được tạo ra bởi chương trình dịch
- Tốc độ thực thi lệnh của máy
- Độ phức tạp về thời gian của thuật toán
Thời gian chạy của chương trình chủ yếu phụ thuộc vào kích thước dữ liệu đầu vào, không phải giá trị cụ thể của dữ liệu đó Khi kích thước dữ liệu tăng lên, thời gian xử lý cũng tăng theo, ví dụ như thời gian sắp xếp một dãy số tỷ lệ thuận với số lượng số trong dãy Do đó, thời gian chạy nên được định nghĩa là một hàm phụ thuộc vào kích thước dữ liệu đầu vào Giả sử T là hàm ước lượng thời gian chạy, thì với kích thước dữ liệu n, thời gian chạy của chương trình là T(n) Mặc dù đơn vị của hàm T(n) không xác định, nhưng có thể coi T(n) là tổng số lệnh thực hiện trên một máy tính lý tưởng.
Ký hiệu O(n) được sử dụng để biểu thị mức độ tăng trưởng của hàm T(n) Nếu T(n) và g(n) là các hàm với đối số nguyên n, ta có thể nói rằng “T(n) là ô lớn của g(n)” và viết là T(n) = O(g(n)) nếu tồn tại các hằng số dương c và n0 sao cho T(n) 0 và ∃n 0 >0 để T(n≤c 0 c 1 f(n) với ∀n≥n 0 Đặt C=c 0 c 1 và dùng định nghĩa ta có T(n) = O(f(n)) b Quy tắc lấy max
Nếu đoạn chương trình P có thời gian thực hiện T(n) = O(f(n)+g(n)) thì có thể coi đoạn chương trình có độ phức tạp tính toán là O(max(f(n),g(n))
Từ định nghĩa ta suy ra T(n) = O(max(f(n),g(n)) c Quy tắc cộng
Nếu chương trình P1 có thời gian thực hiện T1(n) = O(f(n)) và chương trình P2 có thời gian thực hiện T2(n) = O(g(n)), thì tổng thời gian thực hiện của P1 sau đó đến P2 sẽ là: T(n) = T1(n) + T2(n) = O(max(f(n), g(n))).
Chọn n 0 = max(n 1 , n 2 ) và c = max( c 1 , c 2 ) Ta có: ∀n≥n 0 thì
≤ c(f(n) + g(n)) ≤ 2c max(f(n), g(n)) Vậy, T1(n) + T2(n) = O( max( f(n), g(n) )) d Quy tắc nhân
Nếu đoạn chương trình P có thời gian thực hiện là T(n) = O(f(n)) Khi đó, nếu thực hiện k(n) lần đoạn chương trình P với k(n) = O(g(n)) thì độ phức tạp sẽ là O(g(n).f(n))
Thời gian thực hiện k(n) lần đoạn chương trình P sẽ là k(n) Theo định nghĩa:
∃nT và cT để T(n)≤cT.f(n) với ∀n≥nT
Vậy với ∀n≥max(n T , n k ) ta có k(n).T(n)≤c T c k (g(n).f(n))
Độ phức tạp tính toán với tình trạng dữ liệu vào
Thời gian thực hiện giải thuật không chỉ phụ thuộc vào kích thước dữ liệu mà còn vào tình trạng của dữ liệu Ví dụ, thời gian sắp xếp một dãy số chưa có thứ tự sẽ khác với thời gian sắp xếp một dãy đã được sắp xếp hoặc đã sắp xếp nhưng theo thứ tự ngược lại Do đó, khi phân tích thời gian thực hiện giải thuật, cần xem xét các trường hợp tốt nhất, trung bình và xấu nhất.
Phân tích thời gian thực hiện của giải thuật trong trường hợp xấu nhất (worst-case analysis) là quá trình xác định T(n), thời gian tối đa cần thiết để thực hiện giải thuật trên tất cả các bộ dữ liệu có kích thước n Việc này giúp đánh giá hiệu suất của giải thuật dựa trên hàm T(n) và xác định giới hạn thời gian tối đa mà giải thuật có thể gặp phải trong điều kiện tồi tệ nhất.
Phân tích thời gian thực hiện trong trường hợp tốt nhất (best-case analysis) nhằm xác định T(n), thời gian thực hiện tối thiểu cho mọi bộ dữ liệu có kích thước n Việc này giúp đánh giá hiệu suất của thuật toán dựa trên hàm T(n).
Phân tích thời gian trung bình thực hiện giải thuật (average-case analysis) xem xét trường hợp dữ liệu đầu vào tuân theo một phân phối xác suất nhất định, như phân bố đều, nghĩa là mọi bộ dữ liệu có khả năng được chọn như nhau Quá trình này bao gồm việc tính toán giá trị kỳ vọng (trung bình) của thời gian chạy cho mỗi kích thước dữ liệu n, được biểu diễn bằng hàm T(n) Từ đó, thời gian thực hiện giải thuật được phân tích dựa trên hàm T(n).
Phân lớp bài toán
Hầu hết các thuật toán đều có tham số chính là N, thường là số lượng phần tử dữ liệu được xử lý, và tham số này ảnh hưởng lớn đến thời gian chạy N có thể đại diện cho bậc của một đa thức, kích thước của một tập tin được sắp xếp hay tìm kiếm, hoặc số nút trong một đồ thị Thời gian chạy của hầu hết các thuật toán trong giáo trình này tiệm cận tới một trong các hàm cụ thể.
Hằng số: Hầu hết các chỉ thị trong chương trình chỉ được thực hiện một lần hoặc tối đa vài lần Khi tất cả các chỉ thị của một chương trình đều có đặc điểm này, thời gian chạy của chương trình sẽ tiến chậm khi N tăng lên Thời gian chạy này thường xuất hiện trong các chương trình giải bài toán lớn bằng cách chia nhỏ thành các bài toán nhỏ hơn, giảm kích thước một hằng số nào đó Trong trường hợp này, thời gian chạy được xem là nhỏ hơn một hằng số "lớn" Cơ số của logarit ảnh hưởng đến hằng số này nhưng không đáng kể: Khi N là 1000, logN là 3 với cơ số 10 và 10 với cơ số 2; khi N là một triệu, logN tăng gấp đôi Mỗi khi N được nhân đôi, logN tăng thêm một hằng số.
Khi thời gian chạy của một chương trình là tuyến tính, điều này thường xảy ra khi một số lượng nhỏ các xử lý được thực hiện cho mỗi phần tử dữ liệu nhập Với N là một triệu, thời gian chạy cũng tương đương Nếu N được nhân gấp đôi, thời gian chạy cũng sẽ tăng gấp đôi Đây là tình huống tối ưu cho một thuật toán cần xử lý N dữ liệu nhập hoặc tạo ra N dữ liệu xuất.
Thời gian chạy NlogN đề cập đến các thuật toán giải quyết bài toán bằng cách chia nhỏ thành các bài toán con, giải quyết độc lập và sau đó kết hợp các giải pháp Mặc dù không có thuật ngữ tốt hơn, thuật ngữ "NlogN" được sử dụng để mô tả thời gian chạy này Khi N đạt một triệu, giá trị NlogN khoảng 20 triệu, và khi N tăng gấp đôi, thời gian chạy cũng tăng nhưng không vượt quá gấp đôi.
Khi thời gian chạy của thuật toán là bậc hai, điều này thường chỉ có ý nghĩa với các bài toán nhỏ Thời gian chạy bình phương gia tăng khi thuật toán xử lý tất cả các phần tử dữ liệu, thường là do có hai vòng lặp lồng nhau Nếu N tăng gấp đôi, thời gian chạy sẽ tăng lên gấp 4 lần.
Khi xử lý các bộ ba của các phần tử dữ liệu, thuật toán có thể sử dụng 3 vòng lặp lồng nhau, dẫn đến thời gian chạy bậc ba Điều này có ý nghĩa thực tế trong các bài toán nhỏ, nhưng khi giá trị N tăng gấp đôi, thời gian chạy sẽ tăng lên gấp 8 lần.
Một số thuật toán có thời gian chạy lũy thừa, mặc dù thường được coi là "sự ép buộc thô bạo", vẫn có thể phù hợp trong một số tình huống thực tế Khi giá trị N tăng gấp đôi, thời gian chạy của các thuật toán này sẽ tăng lên theo lũy thừa hai.
Thời gian chạy của một chương trình thường được xác định bởi một hệ số hằng cộng với các số hạng nhỏ hơn, trong đó hệ số hằng và các số hạng phụ thuộc vào phân tích và chi tiết cài đặt Hệ số của số hạng dẫn đầu liên quan đến số chỉ thị trong vòng lặp, và cần phải giới hạn số chỉ thị này trong thiết kế thuật toán Đối với giá trị N lớn, các số hạng dẫn đầu trở nên quan trọng, trong khi với N nhỏ, việc so sánh các thuật toán sẽ khó khăn hơn Thời gian chạy của các chương trình thường gặp là "tuyến tính", "NlogN", "bậc ba", và việc phân tích hiệu quả là rất quan trọng trong thực tế.
Đệ quy
Giới thiệu
Đối tượng được gọi là đệ quy nếu được định nghĩa qua chính nó hoặc một đối tượng khác cùng dạng với chính nó bằng quy nạp
Khi đặt hai chiếc gương đối diện nhau và đặt một vật thể bất kỳ ở giữa, ta sẽ thấy hình ảnh của cả chiếc gương và vật thể đó trong mỗi gương.
Trong toán học, định nghĩa đệ quy được áp dụng trong bài toán tính giai thừa của số n Cụ thể, giai thừa được xác định theo nguyên tắc: nếu n = 0 thì giai thừa bằng 1, còn nếu không, giai thừa của n được tính bằng n nhân với giai thừa của (n-1).
Giải thuật đệ quy
Giải thuật đệ quy là phương pháp giải quyết bài toán P thông qua việc sử dụng lời giải của bài toán P’ tương tự nhưng có kích thước nhỏ hơn Trong đó, quy phi tuyến là trường hợp hàm lặp gọi chính nó nhiều lần, còn đệ quy hỗ tương là tình huống có hai hàm đệ quy khác nhau mà mỗi hàm đều gọi đến các hàm đệ quy khác Để định nghĩa một hàm đệ quy hay thủ tục đệ quy, cần xác định hai phần quan trọng.
Phần neo (anchor) cung cấp lời giải cho bài toán trong các trường hợp đơn giản, cho phép giải quyết trực tiếp mà không cần dựa vào bất kỳ bài toán con nào khác.
Phần đệ quy trong lập trình bao gồm việc xác định các bài toán con đã có lời giải và bài toán cần giải Để giải quyết bài toán chính, ta thực hiện gọi đệ quy cho những bài toán con này Cuối cùng, để tìm ra lời giải cho bài toán, cần phối hợp các kết quả của các bài toán con theo một nguyên tắc nhất định.
Ví dụ 1.10 Tính giai thừa của n với n>=0
- Phần tử neo: n = 0 thì Giai thừa = 1
- Phần đệ quy: Giai thừa (n) = n * Giai thừa (n-1)
Các bước để giải quyết một bài toán bằng lời giải đệ quy:
•Thông số hóa bài toán,
Để giải quyết bài toán, cần xác định các điều kiện biên cụ thể và tìm ra giải thuật phù hợp cho từng tình huống Điều này bao gồm việc xác định phần tử neo, từ đó có thể đưa ra lời giải chính xác cho bài toán.
•Tìm giải thuật tổng quát theo hướng đệ quy lui dần về tình huống bị chặn
Ví dụ 1.11 Tính tổng của n phần tử trong mảng a các số nguyên
Thông số hóa: int *a, int n Điều kiện biên: Mảng 0 phần tử thì tổng bằng 0
Vậy công thức đệ quy là:
Ví dụ minh họa
* Cài đặt đệ quy long Giaithua( int n )
{ if (n==0) return 1; else return Giaithua(n-1)* n;
2 Hai tháng sau khi ra đời mỗi cặp thỏi sẽ sinh ra một cặp thỏ con mới (một con đực và một con cái)
3 Khi đã sinh con rồi thì cứ tiếp tục mỗi tháng chúng lại sinh được một cặp con mới
Câu hỏi đặt ra, ban đầu chỉ có một cặp mới ra đời thì đến tháng thứ n sẽ có thêm bao nhiêu cặp thỏ nữa
Ví dụ 1.12 Cho n = 5, Tính các cặp thỏ sinh sản ở tháng n tương ứng
Tháng thứ 1: 1 cặp (cặp ban đầu)
Tháng thứ 2: 1 cặp (cặp ban đầu chưa sinh thêm)
Tháng thứ 3: 2 cặp (có thêm một cặp mới)
Tháng thứ 4: 3 cặp (cặp ban đầu tiếp tục đẻ thêm và cặp mới chưa đẻ thêm)
Tháng thứ 5: 5 cặp (cặp ban đầu tiếp tục để và cặp con mới đầu tiên bắt đầu đẻ mới)
Như vậy, để tính được số cặp thỏ ở tháng thứ n trở về bài toán tính Fibonaci(n) với nguyên tắc tính Fibonaci(n) = Fibonaci(n-2) + Fibonaci(n-
* Cài đặt đệ quy c Tính tổng các phần tử mảng
Để tính tổng các phần tử của mảng a gồm n số khác nhau, ta áp dụng nguyên tắc như sau: Khi n = 0, tổng của mảng là 0; khi n = 1, tổng là a[0], được tính bằng tổng của mảng với n = 0 cộng với a[0]; và khi n = 2, tổng là a[0] cộng a[1], tương đương với tổng của mảng với n = 1 cộng với a[1].
Vậy khi xét tính tổng các phần tử của mảng a có n phần tử được thực hiện theo công thức TongMang(a,n) = TongMang(a,n-1) + a[n-1]
Tổng kết chương và câu hỏi ôn tập
Tổng kết chương
Các kiến thức trọng tâm cần lưu ý:
Thuật toán là một chuỗi các lệnh có giới hạn, trong đó mỗi lệnh mang ý nghĩa rõ ràng và có thể được thực hiện với một lượng tài nguyên nhất định trong khoảng thời gian cụ thể.
Thuật toán thường được diễn đạt bằng các ngôn ngữ gần gũi với ngôn ngữ tự nhiên, giúp dễ dàng hiểu và tiếp cận Qua thời gian, các mô tả này sẽ được tối ưu hóa và chuyển đổi dần sang ngôn ngữ lập trình chính thức.
- Thời gian thực hiện của thuật toán thường được coi như là một hàm của kích thước dữ liệu đầu vào
- Thời gian thực hiện thuật toán được tính trong các trường hợp tốt nhất, xấu nhất hoặc trung bình
Để thể hiện mức độ tăng trưởng của hàm, chúng ta sử dụng ký hiệu O(n) Mức độ tăng trưởng về thời gian thực hiện của chương trình giúp xác định kích thước bài toán mà chúng ta có khả năng giải quyết.
- Để tính độ phức tạp của một bài toán ta áp dụng quy tắc cộng và quy tắc nhân để xác định
- Một số giải thuật cơ sở thường gặp.
Câu hỏi ôn tập
1 Trình bày khái niệm thuật toán? Các đặc điểm của thuật toán?
2 Thời gian thực hiện một chương trình thường phụ thuộc vào các yếu tố nào? Phân tích cụ thể từng yếu tố?
3 Nói thời gian thực hiện của chương trình là T(n) = O(f(n)) có nghĩa là gì? Cho ví dụ minh họa?
4 Hãy nêu quy tắc cộng và nhân cấp độ tăng của hàm và đưa ví dụ minh họa.
Bài tập áp dụng
Bài 1 Giả sử quy tắc tổ chức quản lý nhân viên của một công ty như sau:
*Thông tin về một nhân viên bao gồm lý lịch và bảng chấm công:
- Mã nhân viên: chuỗi 8 ký tự
- Họ, Tên nhân viên: chuỗi 30 ký tự
- Tình trạng gia đình: 1 ký tự (M = Married, S = Single)
- Trình độ văn hoá: chuỗi 2 ký tự, trình độ được nhập với nguyên tắc sau (C1 = cấp 1; C2 = cấp 2; C3 = cấp 3; ĐH = đại học, CH = cao học)
- Số ngày nghỉ có phép trong tháng: số ≤ 28
- Lương thực lĩnh trong tháng: số ≤ 2.000.000
*Quy tắc lĩnh lương: Lương thực lĩnh = Lương căn bản + Phụ trội Trong đó nếu:
- số con > 2 : Phụ trội = +5% Lương căn bản
- trình độ văn hoá = CH: Phụ trội = +10% lương căn bản
- làm thêm: Phụ trội = +4% lương căn bản / ngày
- nghĩ không phép : Phụ trội = -5% lương căn bản / ngày
- Cập nhật lý lịch, bảng chấm công cho nhân viên (thêm, xoá, sửa)
- Xem bảng lương hàng tháng
- Tìm thông tin của một nhân viên
Tổ chức cấu trúc dữ liệu thích hợp để biểu diễn các thông tin trên, và cài đặt chương trình theo các chức năng đã mô tả
Lưu ý: Số lượng nhân viên tối đa là 50 người
Đoạn mã a bắt đầu với t = 0 và n = 20, sau đó sử dụng vòng lặp for để lặp qua các giá trị từ 1 đến n-1 Trong vòng lặp, nếu i là số lẻ (i%2==1), giá trị t sẽ được cập nhật bằng cách cộng thêm 2*i Cuối cùng, chương trình in ra giá trị của t Độ phức tạp tính toán của thuật toán này là O(n), vì vòng lặp for chạy n-1 lần Đoạn mã b khởi tạo k = 0 và n = 20, sau đó sử dụng vòng lặp while để tiếp tục lặp cho đến khi k nhỏ hơn n Độ phức tạp tính toán của đoạn mã b cũng là O(n), do vòng lặp while chạy n lần.
Bài 3 yêu cầu áp dụng tìm điểm dừng và giải thuật đệ quy để lập trình giải các bài toán cụ thể Dữ liệu sẽ được nhập từ bàn phím và kết quả sẽ được hiển thị trên màn hình.
- Nhập các số nguyên n, m Tính và đưa ra giá trị C m n (0 ≤ m ≤ n ≤ 31)
- Tìm giá trị lớn nhất trong m số đầu tiên của mảng a[1 m]?
- Tìm giá trị ước số chung lớn nhất của hai số nguyên a,b (với a,b>0)
- Tính biểu thức: S=(x - (x - (x - (x-1) 2 ) 2 ) 2 ) 2 - với n lần bình phương
- Tính biểu thức sau: S = sin( x + sin( x + … sin(x) …)) - với n hàm sin
- Tính tổng n số đầu tiên trong mảng a[1 n]
DANH SÁCH
Danh sách
Danh sách là tập hợp hữu hạn các phần tử thuộc cùng một loại đối tượng, có kiểu dữ liệu giống nhau Ví dụ điển hình bao gồm danh sách sinh viên trong một lớp học hoặc danh sách các số nguyên.
Giả sử L là danh sách có n phần tử (n>=0):
Khi đó: n là độ dài của danh sách
- n >= 1 thì a 1 gọi là phần tử đầu tiên của danh sách, a n là phần tử cuối cùng của danh sách
Các phần tử trong danh sách được sắp xếp theo thứ tự tuyến tính dựa trên vị trí xuất hiện của chúng Nếu n > 1, phần tử a i sẽ đứng trước phần tử a i+1, hoặc ngược lại, với i = 1, 2,…, n-1 Do đó, a i được xem là phần tử ở vị trí thứ i trong danh sách.
- Các phần tử trong danh sách có thể xuất hiện nhiều lần
Ví dụ 2.1 danh sách các lớp của trường tiểu học:
Danh sách rỗng là danh sách con của một danh sách bất kì
Danh sách con bắt đầu từ phần tử đầu tiên được gọi là phần đầu (prefix), trong khi danh sách kết thúc bởi phần tử cuối cùng được gọi là phần cuối (postfix).
Một danh sách mà loại bỏ một số phần tử từ danh sách ban đầu L thì được gọi là dãy con của danh sách L
Ví dụ 2.2 Xét danh sách
L = (đỏ, cam, vàng, lục, lam, chàm, tím)
L1 = (cam, vàng, lục, lam) là một danh sách con của L
L2 = (cam, lục, chàm) là một dãy con của L
L3 = (đỏ, cam, vàng, lục, lam) là phần đầu của danh sách
L4 = (lục, lam, chàm, tím) là phần cuối của danh sách
2.1.2 Các phép toán trên danh sách
Một số phép toán chính trên danh sách gồm:
- Kiểm tra danh sách rỗng/ đầy
- Phép thêm mới một phần tử vào danh sách
- Xác định vị trí của một phần tử trong danh sách
Cài đặt danh sách bằng mảng
Sử dụng cấu trúc dữ liệu mảng để triển khai danh sách cho phép mỗi phần tử của mảng lưu trữ một phần tử của danh sách, với các phần tử liên tiếp trong danh sách được lưu trữ trong các vị trí kế tiếp nhau của mảng.
N là số lượng phần tử tối đa mà danh sách có thể lưu trữ, và việc xác định số lượng này là cần thiết cho cách cài đặt.
Ví dụ 2.3 Khai báo một danh sách các số nguyên int a[100]; // khai báo một mảng số nguyên a tối đa gồm 100 phần tử
Với những dữ liệu phức tạp gồm nhiều thành phần thông tin có thể sử dụng kiểu dữ liệu cấu trúc để khai báo
Ví dụ 2.4 Danh sách sinh viên với các thông tin: họ tên, điểm
Khi đó mảng s là một danh sách có kiểu cấu trúc Sinhvien, chứa tối đa
100 sinh viên, mỗi sinh viên có các thông tin cá nhân gồm họ tên và điểm
Phép chèn một phần tử vào mảng
Muốn chèn phần tử V vào vị trí p của mảng ta phải:
- Tăng kích thước của mảng lên 1 đơn vị n = n + 1
Th ủ t ụ c đượ c cài đặ t nh ư sau:
Thủ tục thêm sinh viên x vào vị trí vt trong danh sách chỉ được thực hiện khi danh sách chưa đầy.
Phép xóa một phần tử khỏi danh sách
Dãy sau khi dồn chỗ
Muốn xóa phần tử thứ p của mảng mà vẫn giữ nguyên thứ tự của các phần tử còn lại, ta thực hiện:
- Dồn các phần tử từ vị trí thứ p+1 tới n lên trước một vị trí
- Giảm kích thước n đi 1 đơn vị
Th ủ t ụ c đượ c cài đặ t nh ư sau:
Thủ tục trên thực hiện xóa phần tử tại vị trí vt khỏi danh sách Phép toán chỉ thực hiện được khi danh sách không rỗng
Nh ậ n xét v ề ph ươ ng pháp cài đặ t danh sách b ở i m ả ng:
Dãy sau khi dồn chỗ
Dãy kết quả không đổi xác định bởi kích cỡ của mảng, chúng ta không thể thực hiện thêm mới vượt quá khả năng lưu trữ của mảng
2.2.2 Bài toán tìm ki ế m trên danh sách
Tìm kiếm thông tin là một phần quan trọng trong cuộc sống, đặc biệt khi cần tra cứu thông tin tuyển sinh liên quan đến số báo danh, như họ tên thí sinh, điểm thành phần và điểm tổng Trong tin học, thông tin về một đối tượng thường được lưu trữ dưới dạng bản ghi, với các thuộc tính của đối tượng được biểu diễn qua các trường trong cấu trúc Khi thực hiện tìm kiếm, chúng ta dựa vào các thuộc tính đã biết, được gọi là khóa tìm kiếm, có thể là một hoặc nhiều trường của cấu trúc Một giá trị khóa cho trước có thể tương ứng với nhiều bản ghi hoặc không có bản ghi nào.
Tìm kiếm được chia thành hai loại: tìm kiếm trong và tìm kiếm ngoài Tìm kiếm ngoài liên quan đến việc truy cập các tệp dữ liệu lưu trữ trên bộ nhớ ngoài như ổ đĩa cứng, băng từ, hoặc USB Flash disk Ngược lại, tìm kiếm trong diễn ra khi dữ liệu được lưu trữ trong bộ nhớ trong (RAM) Trong bài viết này, chúng ta sẽ chỉ tập trung vào phương pháp tìm kiếm trong, cụ thể là tìm kiếm tuần tự.
Tìm kiếm tuần tự là phương pháp duyệt qua từng phần tử trong danh sách một cách lần lượt, so sánh khóa của mỗi bản ghi với giá trị cần tìm Quá trình này sẽ dừng lại khi tìm thấy bản ghi phù hợp hoặc khi đã kiểm tra toàn bộ danh sách.
Hàm thực hiện tìm kiếm trên một mảng số nguyên như sau:
Hàm trên sẽ duyệt qua từng phần tử trong mảng, và nếu tìm thấy giá trị cần tìm, nó sẽ trả về chỉ số của phần tử đó Ngược lại, nếu không tìm thấy giá trị trong toàn bộ mảng, hàm sẽ trả về -1.
Thuật toán tìm kiếm tuần tự có thời gian thực hiện O(n), trong trường hợp xấu nhất thuật toán mất n lần thực hiện phép so sánh b Tìm kiếm nhị phân
Khi số bản ghi cần tìm rất lớn, tìm kiếm tuần tự có thể không hiệu quả về thời gian Một giải pháp tốt hơn là sử dụng phương pháp “chia để trị”, trong đó tập dữ liệu được chia thành hai nửa Đầu tiên, cần sắp xếp các phần tử và sử dụng chỉ số của mảng để xác định nửa chứa bản ghi cần tìm Bằng cách so sánh giá trị cần tìm với giá trị ở giữa, nếu giá trị cần tìm nhỏ hơn, tìm kiếm sẽ diễn ra ở nửa đầu, ngược lại sẽ tìm ở nửa sau Quá trình này sẽ được lặp lại cho đến khi tìm thấy bản ghi mong muốn.
Ví dụ 2.5 Tìm kiếm phần tử có giá trị x từ vị trí left đến vị trí right trong dãy đã sắp xếp tăng
- Tìm phần tử giữa: middle = (left+right)/2
- Nếu x < a[middle] thì ta thực hiện tìm kiếm trên đoạn [left, middle -1] (nửa đầu)
- Nếu x = a[middle] hoặc right > left thì dừng
Mô t ả thu ậ t toán tìm ki ế m nh ị phân nh ư sau: (gi ả s ử dãy a đ ã s ắ p t ă ng)
Để tìm giá trị x trong mảng a đã được sắp xếp tăng dần với n phần tử, ta sử dụng chỉ số left và right để xác định vị trí bắt đầu và kết thúc của mảng.
* Đầ u ra: vị trí chứa phần tử x (nếu có)
•Bước 1: Khởi đầu tìm kiếm trên tất cả các phần tử của dãy ! left =
•Bước 2: Tính middle = (left + right)/2 So sánh a[middle] với x Có
Khi thực hiện tìm kiếm nhị phân, có ba khả năng xảy ra: Nếu giá trị ở giữa (a[middle]) bằng với giá trị cần tìm (x), ta đã tìm thấy và dừng lại Nếu a[middle] lớn hơn x, ta tiếp tục tìm x trong nửa đầu của dãy bằng cách điều chỉnh right = middle - 1 Ngược lại, nếu a[middle] nhỏ hơn x, ta sẽ tìm x trong nửa cuối của dãy với left = middle + 1.
•Bước 3: o Nếu left ≤ right ⇒ dãy còn phần tử, tiếp tục quay lại bước 2 để tìm kiếm tiếp o Ngược lại ⇒ Dãy hiện hành hết phần tử và dừng thuật toán
* Th ủ t ụ c đượ c cài đặ t nh ư sau:
Hàm tìm kiếm giá trị x trong dãy a sử dụng biến left và right để xác định vị trí đầu và cuối của danh sách con Biến middle lưu vị trí giữa của danh sách, và quá trình tìm kiếm diễn ra qua vòng lặp do while Mỗi lần lặp, giá trị x sẽ được so sánh với phần tử giữa; nếu bằng nhau, hàm dừng và trả về vị trí tìm thấy Nếu x nhỏ hơn phần tử giữa, tìm kiếm sẽ tiếp tục ở nửa đầu danh sách (cập nhật right = middle - 1), ngược lại sẽ tìm ở nửa cuối (cập nhật left = middle + 1).
Thuật toán tìm kiếm nhị phân có thời gian thực hiện O(log 2 n) Thuật toán này đòi hỏi phải sắp xếp các phần tử trước khi tìm kiếm
2.2.3 Bài toán s ắ p x ế p trên danh sách
Sắp xếp là quá trình tổ chức một danh sách các đối tượng theo một thứ tự cụ thể, đóng vai trò quan trọng trong việc tìm kiếm dữ liệu hiệu quả.
Ví dụ muốn tra cứu từ điển nếu các từ không được sắp xếp theo trật tự thì việc tra cứu sẽ rất khó khăn
Các giải thuật sắp xếp được chia thành hai loại: loại cài đặt đơn giản nhưng kém hiệu quả và loại cài đặt phức tạp nhưng có tốc độ xử lý nhanh hơn Đối với các bài toán sắp xếp với số lượng phần tử ít, phương pháp đơn giản là lựa chọn hợp lý, trong khi với số lượng lớn, phương pháp phức tạp sẽ mang lại hiệu quả cao hơn Sắp xếp bằng lựa chọn (Selection Sort) là thuật toán đơn giản nhất, với ý tưởng cơ bản là tìm kiếm phần tử nhỏ nhất trong danh sách và đổi chỗ nó với phần tử đầu tiên.
Tại mỗi bước, chúng ta sẽ chọn phần tử nhỏ nhất từ những phần tử chưa được xét và đưa nó vào vị trí thích hợp, sau đó cố định phần tử này để không cần xem xét lại.
•Dãy ban đầu có n phần tử, thuật toán thực hiện n-1 lượt để đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy
Ví dụ 2.6 Các bước thực hiện sắp xếp chọn dãy số bên dưới như sau:
Bước đầu tiên là chọn phần tử nhỏ nhất trong dãy số ban đầu, cụ thể là 06, sau đó đổi chỗ với phần tử 32 để cố định 06 và không xem xét phần tử này trong các bước tiếp theo.
Bước 2: Chọn được phần tử nhỏ nhất là 17, vị trí của 17 đã phù hợp nên giữ nguyên
Bước 3: Chọn được phần tử nhỏ nhất tiếp theo là 25, đổi chỗ cho 49
Bước 4: Chọn được phần tử nhỏ nhất trong dãy chưa xét là 32, đổi chỗ cho 98
Bước 5: Chọn được phần tử nhỏ nhất trong dãy chưa xét còn lại là 49, đổi chỗ cho 98
Bước 6: Chọn được phần tử nhỏ nhất trong dãy còn lại là 53, đổi chỗ cho
Bước 7: Chọn được phần tử nhỏ nhất trong số 2 phần tử còn lại là 61, đổi chỗ cho 98
Như vậy, toàn bộ dãy đã được sắp
Thuật toán được mô tả như sau:
*Đầu vào: n – số phần tử mảng a – mảng chứa các phần tử bất kỳ
*Đầu ra: a - mảng đã được sắp xếp tăng dần
•Bước 1: i = 0 (bắt đầu từ vị trí đầu tiên)
•Bước 2: tìm chỉ số phần tử min nhỏ nhất trong dãy hiện hành từ a[i] đến a[n-1]
•Bước 3: Hoán vị a[i] với a[min]
•Bước 4: o nếu i Dừng thuật toán
*Thủ tục cài đặt như sau:
Cài đặt danh sách bằng danh sách liên kết
Danh sách liên kết là một cấu trúc dữ liệu bao gồm các phần tử liên kết với nhau theo dạng tuần tự, trong đó mỗi phần tử được gọi là một nút.
Mỗi nút gồm hai phần:
- D ữ li ệ u (Data): là các thành phần dữ liệu mà một nút đó lưu trữ
Liên kết (Linked) là một con trỏ kiểu nút được sử dụng để kết nối với các nút khác trong cấu trúc dữ liệu Để khai báo danh sách liên kết đơn, bạn cần thực hiện các bước cụ thể.
- Khai báo cấu trúc dữ liệu của thông tin được lưu trữ - Data
- Khai báo cấu trúc của một nút – Node struct Node
Data Infor; struct Node *Next; struct LIST
Ví dụ 2.9 Cho thông tin của sinh viên gồm: Mã sinh viên (số nguyên),
Để lưu trữ danh sách các sinh viên, chúng ta cần khai báo cấu trúc dữ liệu dạng danh sách liên kết đơn với các thành phần bao gồm họ tên (chuỗi), tuổi (số nguyên) và điểm trung bình (số thực).
- Khai báo cấu trúc Sinh viên struct SinhVien
{ int MaSV; char HoTen[20]; int Tuoi; float DTB;
- Khai báo cấu trúc một Node struct Node
SinhVien Infor; // khai báo dữ liệu struct Node *Next; //khai báo liên kết
- Khai báo danh sách liên kết đơn struct LIST
2.3.2 Các phép toán trên danh sách liên k ế t a Khởi tạo danh sách rỗng
Danh sách rỗng là danh sách không chứa bất kỳ phần tử nào, với cả phần tử đầu và phần tử cuối đều trỏ đến địa chỉ NULL Để tạo một nút mới, bạn cần cung cấp thành phần dữ liệu x.
Để tạo một nút chứa thông tin của một dữ liệu nào đó, ta có thể thêm nút vào danh sách liên kết đơn đã có Có một số trường hợp cần xem xét khi thực hiện việc này.
- Chèn thêm một nút vào đầu danh sách
- Chèn thêm một nút vào cuối danh sách q.Head, cuối danh sách được trỏ bởi con trỏ q.Tail
Các bước để chèn 1 nút mới vào đầu danh sách như sau:
Hình 2.1 Minh họa thêm phần tử mới vào đầu danh sách
•Nếu danh sách rỗng thì: o Phần tử đầu là phần tử mới chèn vào o Phần tử cuối cũng là phần tử đầu
•Ngược lại (danh sách khác rỗng): o Phần tử mới trỏ tới phần tử đầu o Phần tử đầu là phần tử mới chèn vào
Thủ tục được cài đặt như sau:
Các bước để chèn 1 nút mới vào cuối danh sách như sau:
Hình 2.2 Chèn thêm phần tử mới vào cuối danh sách
Cho con trỏ tiếp của nút cuối q.Tail trỏ đến nút mới tạo là p, và cho con trỏ tiếp của p trỏ tới NULL
•Nếu danh sách rỗng thì: o Phần tử đầu là phần tử mới chèn vào o Phần tử cuối cũng là phần tử đầu
•Ngược lại (danh sách khác rỗng): o Phần tử cuối trỏ tới phần tử mới chèn vào o Phần tử cuối là phần tử mới chèn vào
Thủ tục được cài như sau: new_element
Q.Tail sử là q, thực hiện:
Hình 2.3 Chèn thêm phần tử mới vào sau phần tử q xác định
Cho con trỏ tiếp của p trỏ tới phần tử đứng sau q, con trỏ tiếp của q trỏ tới p
•Nếu phần tử q rỗng $ không chèn được
Nếu phần tử q không rỗng, cần thực hiện các bước sau: phần tử mới sẽ trỏ tới phần tử đứng sau phần tử q, và phần tử q sẽ trỏ tới phần tử mới được chèn vào.
Thủ tục cài đặt như sau: d Xóa một nút trong danh sách
Khi thêm một nút, chúng ta cần cấp phát bộ nhớ cho nó, trong khi khi xóa một nút, cần giải phóng bộ nhớ bằng lệnh free() Để thực hiện việc xóa một nút trong danh sách, có nhiều khả năng khác nhau.
- Xóa phần tử đầu danh sách
- Xóa phần tử sau phần tử xác định nào đó
- Xóa phần tử có giá trị k nào đó
*Xóa phần tử đầu danh sách
Các bước thực hiện nhau sau:
- Kiểm tra danh sách không rỗng
- Lưu phần tử đầu tạm thời vào p
- Chuyển phần tử đầu tới phần tử tiếp theo
- Xóa phần tử đầu đã được lưu tạm – xóa p
- Kiểm tra: Nếu danh sách chỉ có một phần tử, khi xóa phần tử đi thì phần tử cuối cùng không còn
Hình 2.4 Minh họa xóa phần tử đầu danh sách
*Xóa phần tử đứng sau phần tử q của danh sách
- Tách phần tử p ra khỏi danh sách
Hình 2.5 Minh họa xóa phần tử đứng sau phần tử q xác định
*Xóa phần tử có khóa bằng k
Bước 1: Tìm phần tử p có khóa k và phần tử q đứng trước nó
Bước 2: Nếu tìm thấy phần tử có khóa là k thì hủy p ra khỏi xâu tương tự hủy phần tử sau q;
Ngược lại thông báo không có k;
Thủ tục cài đặt như sau: e Tìm kiếm
Danh sách liên kết đơn chỉ cho phép truy cập tuần tự đến từng phần tử, do đó chỉ có thể sử dụng thuật toán tìm kiếm tuần tự để xác định xem một phần tử có giá trị k có tồn tại hay không Để thực hiện việc duyệt danh sách, chúng ta sử dụng một con trỏ p, bắt đầu từ đầu danh sách và lần lượt kiểm tra từng phần tử Trong quá trình này, nếu giá trị của phần tử hiện tại không bằng k, con trỏ p sẽ tiếp tục di chuyển đến phần tử tiếp theo; nếu tìm thấy giá trị k, thuật toán sẽ trả về địa chỉ của nút đó.
•Bước 1: p = Q.Head; //p trỏ từ đầu danh sách
•Bước 2: Kiểm tra danh sách còn phần tử và nếu chưa tìm thấy phần tử
Lặp trong khi (p!=NULL) và (p->Infor !=k) thì p = p -> Next;
•Bước 3: f Sắp xếp danh sách
Danh sách có thứ tự là danh sách mà các phần tử được sắp xếp theo một thứ tự nhất định dựa trên thành phần khóa Để thực hiện việc sắp xếp, có hai phương án khác nhau.
Hoán vị nội dung của phần tử là phương pháp thay đổi trực tiếp giá trị dữ liệu trong mỗi nút, trong khi thứ tự liên kết giữa các nút vẫn được giữ nguyên.
Thay đổi mối liên kết của các phần tử trong danh sách là quá trình điều chỉnh liên kết "Next" của mỗi nút, dẫn đến sự thay đổi thứ tự của các nút Quá trình này tạo ra một danh sách mới với thứ tự từ danh sách cũ, đồng thời hủy bỏ danh sách cũ.
Cài đặt thuật toán sắp hoán vị nội dung của phần tử:
Thuật toán sử dụng hai con trỏ p và q để duyệt và so sánh các phần tử trong danh sách Ban đầu, con trỏ p trỏ đến phần tử đầu tiên, trong khi con trỏ q trỏ đến phần tử ngay sau p Nếu giá trị của phần tử p và q không đúng thứ tự, thuật toán sẽ hoán đổi chúng Quá trình này được lặp lại cho đến khi toàn bộ dãy được sắp xếp hoàn chỉnh.
Thuật toán sắp xếp dựa trên việc thay đổi mối liên kết giữa các phần tử để tạo ra một danh sách mới Danh sách này được hình thành bằng cách xác định các phần tử có giá trị lớn nhất hoặc nhỏ nhất trong dãy ban đầu và đưa chúng vào danh sách mới Các bước thực hiện thuật toán có thể được mô tả một cách rõ ràng và mạch lạc.
- Bước 1: Khởi tạo danh sách mới Result là rỗng;
- Bước 2: Tìm trong danh sách cũ Q(Head, Tail) phần tử min là phần tử nhỏ nhất;
- Bước 3: Tách min khỏi danh sách cũ Q(Head, Tail);
- Bước 4: Chèn min vào cuối danh sách Result;
- Bước 5: Lặp lại bước 2 khi chưa hết danh sách cũ Q(Head, Tail);
2.3.3 So sánh cài đặ t danh sách theo hai ph ươ ng pháp
Chúng ta đã xem xét hai phương pháp cài đặt danh sách: sử dụng mảng và danh sách liên kết Mỗi phương pháp đều có những ưu điểm và nhược điểm riêng Việc lựa chọn phương pháp cài đặt phù hợp phụ thuộc vào yêu cầu cụ thể của bài toán.
Mảng cho phép truy cập ngẫu nhiên thông qua chỉ số, trong khi danh sách chỉ có thể truy cập tuần tự Đối với danh sách liên kết, việc truy cập một phần tử yêu cầu bắt đầu từ đầu danh sách và lần lượt qua từng phần tử cho đến khi đến phần tử cần truy cập Ngược lại, trong mảng, việc thay đổi vị trí của nhiều phần tử thường diễn ra dễ dàng hơn.
Bài tập có hướng dẫn
Chương trình quản lý danh sách cán bộ sẽ bao gồm các thông tin quan trọng như mã cán bộ, họ tên và lương Hệ thống được cài đặt bằng danh sách liên kết đơn, cho phép thực hiện các chức năng như thêm cán bộ, hiển thị danh sách cán bộ, tìm kiếm và sắp xếp thông tin một cách hiệu quả.
Hướng dẫn: Áp dụng các thuật toán trên danh sách liên kết đơn để triển khai.
Tổng kết chương
Nội dung của chương này là xem xét các vấn đề liên quan tới tổ chức và xử lý danh sách
Danh sách tổ chức dưới dạng mảng mang lại nhiều lợi ích như dễ sử dụng và tốc độ truy cập nhanh Tuy nhiên, mảng cũng có những nhược điểm, bao gồm sự không linh hoạt về kích thước và sự phức tạp trong việc sắp xếp lại các phần tử.
Danh sách liên kết là một cấu trúc dữ liệu bao gồm các phần tử, mỗi phần tử là một nút chứa liên kết tới nút tiếp theo Với kiểu truy cập tuần tự, danh sách liên kết có kích thước linh hoạt và cho phép dễ dàng bố trí lại các phần tử.
Các thao tác cơ bản trên danh sách bao gồm khởi tạo danh sách, chèn phần tử vào đầu, cuối hoặc giữa danh sách, xoá phần tử từ đầu, cuối hoặc giữa, duyệt qua toàn bộ danh sách, cũng như thực hiện tìm kiếm và sắp xếp.
Chương này tập trung vào các thuật toán tìm kiếm, bao gồm tìm kiếm tuần tự và tìm kiếm nhị phân, cùng với các thuật toán sắp xếp từ cơ bản đến nâng cao như Selection Sort, Insertion Sort, Bubble Sort và Quick Sort.
Trong chương này, bên cạnh danh sách liên kết đơn, chúng ta còn khám phá các loại danh sách liên kết khác như danh sách vòng và danh sách liên kết kép, mang đến cái nhìn tổng quát về cấu trúc dữ liệu này.
Câu hỏi trắc nghiệm
Câu 1 Các trường hợp chèn thêm một phần tử mới vào danh sách liên kết đơn gồm:
A Chèn thêm vào đầu danh sách và vào cuối danh sách,
B Chèn thêm vào đầu danh sách và vào sau một phần tử q đã biết,
C Chèn thêm vào cuối danh sách và vào sau một phần tử q đã biết,
D Chèn thêm vào đầu danh sách, vào cuối danh sách và vào sau một phần tử q đã biết
Câu 2 Định nghĩa cấu trúc dữ liệu của danh sách liên kết đơn được mô tả như sau: struct Node{
Trong đó, khai báo Node *Next; dùng để mô tả
A Con trỏ tới địa chỉ vùng nhớ của phần tử trước đó trong danh sách liên kết đơn,
B Con trỏ trỏ tới phần dữ liệu,
C Vùng liên kết quản lý địa chỉ phần tử kế tiếp,
D Con trỏ tới địa chỉ vùng nhớ của phần tử đầu tiên trong danh sách liên kết đơn
Câu 3 Đoạn mã để tạo ra nút mới có thành phần là x trong danh sách liên kết đơn với mỗi nút gồm hai thành phần (Infor, Next) sau:
{ printf("Ko du bo nho"); exit(1);
} Điền phần còn thiếu vào chỗ …………
Câu 4 Các trường hợp thực hiện hủy phần tử khỏi danh sách liên kết đơn gồm:
A Hủy phần tử đầu danh sách và hủy phần tử đứng sau phần tử q,
B Hủy phần tử có giá trị xác định k và hủy phần tử đứng sau phần tử q,
C Hủy phần tử đầu danh sách, hủy phần tử đứng sau phần tử q và hủy phần tử có giá trị xác định k,
D Hủy phần tử đầu danh sách và hủy phần tử có giá trị xác định k
Câu 5 Để tiến hành tìm kiếm một phần tử trong danh sách liên kết đơn sử dụng phương pháp tìm kiếm gì?
A Tìm kiếm tuyến tính và tìm kiếm nhị phân,
D Cả ba phát biểu đều đúng
Câu 6 Đoạn mã cài đặt chèn thêm một phần tử mới vào đầu của danh sách liên kết đơn: void insertFirst ( LIST &Q, Node *new_element )
{ if ( Q.Head == NULL ) //nếu danh sách rỗng
} else //danh sách không rỗng
Câu 7 Tổ chức của danh sách liên kết kép gồm có mấy thành phần:
Câu 8 Để sắp xếp các phần tử của danh sách liên kết đơn có mấy phương án sử dụng:
Câu 9 Tổ chức cấu trúc dữ liệu cho danh sách liên kết đơn: struct OneNode { int Data;
Để thêm một phần tử có giá trị NewData vào danh sách liên kết đơn SLList ngay sau nút có địa chỉ InsNode, ta thực hiện các bước sau: Đầu tiên, tạo một nút mới với giá trị NewData Sau đó, cập nhật con trỏ của nút mới để trỏ đến nút tiếp theo sau InsNode Cuối cùng, thay đổi con trỏ của InsNode để trỏ đến nút mới, hoàn thành việc chèn phần tử vào danh sách.
//Nối các nút kế sau InsNode vào sau NewNode
//Chuyển mối liên kết giữa InsNode với nút kế của nó về NewNode B7: ………
B6 và B7 được sử dụng để kết nối nút kế tiếp sau InsNode với NewNode, đồng thời chuyển đổi mối liên kết giữa InsNode và nút kế của nó về NewNode Hãy chọn câu phù hợp nhất cho B6 và B7.
Câu 10 Danh sách được cài đặt bằng cách nào:
D Cài đặt bằng danh sách liên kết
Câu 11 Khi cần thêm một phần tử có giá trị thành phần dữ liệu là
NewData (là một số nguyên) vào đầu của danh sách liên kết đơn dùng thuật toán có mã giả được mô tả như dưới đây: struct OneNode { int Data;
B2: if (NewNode = NULL) thực hiện BKT;
Tìm mô tả chính xác cho bước 5 (B5)
A Nối NewNode vào sau SLLList,
B Chuyển vai trò đứng đầu của NewNode cho SLLList,
C.Nối SLLList vào sau NewNode,
D Chuyển vai trò đứng đầu của SLLList cho NewNode
Câu 12 Trong một nút của danh sách liên kết đơn, thành phần Infor là thành phần gì?
A Để lưu trữ địa chỉ của nút kế tiếp hoặc giá trị NULL nếu không liên kết đến phần tử nào,
B Cả hai phát biểu trên đều đúng,
C Cả hai phát biểu trên đều sai,
D Để lưu trữ hay mô tả thông tin được lưu trữ trong nút của danh sách
Câu 13 Đoạn mã cài đặt hủy bỏ một phần tử đứng sau một phần tử q trong danh sách liên kết đơn: void RemoveAfter ( LIST &Q , Node *q ){
{ p = q -> Next; if (p != NULL) { if (p == Q.Tail) { q->Next = NULL;
Dòng lệnh cần thiết được đặt vào chỗ trống tại dòng số [1]:
Câu 14 Chọn định nghĩa đúng nhất về hàng đợi (Queue)
A Hàng đợi là một danh sách mà trong đó thao tác thêm 1 phần tử vào trong danh sách được thực hiện 1 đầu này và lấy 1 phần tử trong danh sách lại thực hiện bởi đầu kia,
B Hàng đợi là một danh sách mà trong đó thao tác thêm 1 phần tử hay hủy một phần tử trong danh sách được thực hiện 1 đầu,
C Hàng đợi còn được gọi là danh sách FIFO và cấu trúc dữ liệu này còn được gọi là cấu trúc FIFO (First In Fast Out),
D Hàng đợi phải là một danh sách liên kết đơn
Câu 15 Các loại danh sách liên kết gồm:
A Danh sách liên kết đơn và danh sách liên kết kép,
B Danh sách liên kết kép và danh sách liên kết vòng,
C Danh sách liên kết đơn, danh sách liên kết kép và danh sách liên kết vòng,
D Danh sách liên kết đơn và danh sách liên kết vòng
Câu 16 Lựa chọn câu đúng nhất về danh sách liên kết đôi (Doubly Linked List)
A Vùng liên kết của một phần tử trong danh sách liên đôi có 02 mối liên kết với phần tử đầu và cuối danh sách,
B Vùng liên kết của một phần tử trong danh sách liên đôi có 01 mối liên kết với 02 phần tử khác trong danh sách,
C Vùng liên kết của một phần tử trong danh sách đôi có 02 mối liên kết với 01 phần tử trong danh sách ,
D Vùng liên kết của một phần tử trong danh sách liên kết đôi có 02 mối liên kết với 02 trước và sau nó trong danh sách
Câu 17 Để chèn thêm một phần tử mới vào danh sách liên kết đơn có mấy trường hợp:
Câu 18 Đoạn mã cài đặt hủy phần tử đầu của danh sách liên kết đơn: void RemoveHead ( LIST &Q ){
[1] ……… free(p); if ( Q.Head == NULL ) Q.Tail = NULL;
Dòng lệnh cần thiết được đặt vào chỗ trống tại dòng số [1]:
Câu 19 Các thao tác cơ bản trên danh sách gồm thao tác gì:
B Tất cả các thao tác trên,
C Tìm kiếm, sắp xếp, sao chép,
Node *p; p = (Node*)malloc(sizeof(Node)); if ( p == NULL )
{ printf("Ko du bo nho"); exit(1);
} Điền phần còn thiếu vào chỗ …………
Câu 21 Cấu trúc dữ liệu biểu diễn hàng đợi bằng danh sách liên kết struct QOneElement {
Cấu trúc dữ liệu quản lý hàng đợi bằng hai phần tử đầu (Font) và cuối (Rear): struct QQUEUE {
Để thêm phần tử vào sau phần tử Rear trong hàng đợi, đầu tiên khởi tạo nút mới với dữ liệu NewData Mã giả mô tả quy trình này như sau: B1: NewElement = Khởi tạo nút mới có thành phần NewData.
B3: if (SQList.Font == NULL) //hàng đợi đang rỗng
B3.1 SQList.Font = SQList.Rear = NewElement
Câu 22 Đoạn mã cài đặt chèn thêm một phần tử mới vào đầu của danh sách liên kết đơn:
} else //danh sách không rỗng
} Đoạn mã còn thiếu để đặt vào dòn số [1] và [2]
Câu 23 Có mấy loại danh sách liên kết?
Câu 24 Đoạn mã chèn thêm một phần tử mới vào sau phần tử q trong danh sách liên kết đơn: void InsertAfter( LIST &Q, Node *q, Node *new_element ){ if( q != NULL)
[2] ………… if (q == Q.Tail) Q.Tail = new_element;
} Đoạn mã còn thiếu để đặt vào dòng số [1] và [2]
A q -> Next = new_element; new_element -> Next = NULL;
B new_element -> Next = q -> Next; q -> Next = NULL;
C new_element -> Next = q -> Next; q -> Next = new_element;
D q -> Next = new_element; new_element -> Next = q -> Next;
Câu 25 Các thành phần của danh sách gồm:
A Dữ liệu (data) và liên kết (link),
B Số phần tử của danh sách (number),
D Dữ liệu (data) kết đơn
Câu 2 Nêu các bước để xoá một nút ở đầu, giữa, và cuối danh sách liên kết đơn
Câu 3 Cho biết kết quả chạy từng bước của khi thực hiện tìm x = 6 trong dãy số dưới đây theo giải thuật tìm kiếm nhị phân và tuần tự
Trong đó: D là ngày sinh, M là tháng sinh, T là tuổi
Thuật toán sắp xếp chèn trực tiếp (InsertionSort) là một phương pháp hiệu quả để sắp xếp các phần tử trong mảng một chiều Để cài đặt thuật toán này, chúng ta thực hiện các bước sau: đầu tiên, chọn phần tử đầu tiên trong mảng và coi nó là một danh sách đã sắp xếp Sau đó, lặp qua từng phần tử còn lại, so sánh với các phần tử trong danh sách đã sắp xếp và chèn vào vị trí thích hợp Đối với mảng số nguyên, quá trình sắp xếp sẽ diễn ra như sau: bắt đầu từ phần tử thứ hai, so sánh với phần tử đầu tiên, nếu nhỏ hơn thì chèn vào trước, tiếp tục với phần tử thứ ba và thực hiện tương tự cho đến khi sắp xếp toàn bộ mảng Kết quả cuối cùng là mảng được sắp xếp theo thứ tự tăng dần.
Thuật toán chọn trực tiếp (Selection Sort) là một phương pháp sắp xếp đơn giản, hoạt động bằng cách tìm phần tử nhỏ nhất (hoặc lớn nhất) trong mảng và đưa nó về vị trí đầu tiên, sau đó lặp lại quy trình cho phần còn lại của mảng Để thực hiện sắp xếp tăng dần, ta bắt đầu từ phần tử đầu tiên, tìm phần tử nhỏ nhất trong mảng và hoán đổi nó với phần tử đầu tiên Tiếp theo, ta tìm phần tử nhỏ nhất trong phần còn lại của mảng và hoán đổi nó với phần tử thứ hai, và tiếp tục cho đến khi toàn bộ mảng được sắp xếp Minh họa cho quá trình này, với mảng số nguyên: [64, 25, 12, 22, 11], ta sẽ thực hiện các bước sau: tìm 11 (nhỏ nhất) và hoán đổi với 64, sau đó tìm 12 và hoán đổi với 25, tiếp tục cho đến khi mảng trở thành [11, 12, 22, 25, 64] Đối với sắp xếp giảm dần, quy trình tương tự được thực hiện nhưng ta tìm phần tử lớn nhất để hoán đổi.
Thuật toán sắp xếp nổi bọt (BubbleSort) là một phương pháp đơn giản để sắp xếp mảng một chiều gồm N số nguyên theo thứ tự tăng dần hoặc giảm dần Ý tưởng của thuật toán là so sánh từng cặp phần tử liền kề trong mảng và hoán đổi chúng nếu chúng không theo thứ tự mong muốn Quy trình này được lặp lại cho đến khi không còn sự hoán đổi nào xảy ra, cho thấy mảng đã được sắp xếp Để mô tả từng bước của thuật toán, ta có thể viết hàm sắp xếp với hai tham số: mảng cần sắp xếp và kiểu sắp xếp (tăng dần hoặc giảm dần) Độ phức tạp của thuật toán BubbleSort là O(N^2) trong trường hợp xấu nhất, do phải thực hiện nhiều lần so sánh và hoán đổi Khi thực hiện sắp xếp mảng theo thứ tự tăng dần, thuật toán sẽ lặp qua mảng, so sánh và hoán đổi các phần tử cho đến khi mảng được sắp xếp hoàn toàn, trong khi với thứ tự giảm dần, quy trình tương tự được áp dụng nhưng với điều kiện so sánh ngược lại.
Câu 7 yêu cầu trình bày ý tưởng và mô tả từng bước của thuật toán sắp xếp đổi chỗ trực tiếp (Interchange Sort) cho một mảng một chiều các số nguyên Để thực hiện sắp xếp tăng dần, thuật toán sẽ so sánh từng cặp phần tử trong mảng và hoán đổi chúng nếu cần thiết, nhằm đưa phần tử nhỏ hơn về đầu mảng Quá trình này được lặp lại cho đến khi toàn bộ mảng được sắp xếp hoàn chỉnh Để minh họa, hãy xem xét một dãy số nguyên cụ thể và áp dụng từng bước của thuật toán để thấy rõ cách thức hoạt động và kết quả cuối cùng sau khi sắp xếp.
Thuật toán QuickSort là một phương pháp sắp xếp hiệu quả cho mảng một chiều Để thực hiện QuickSort tăng dần, đầu tiên, chọn một phần tử làm pivot Sau đó, phân chia mảng thành hai phần: phần nhỏ hơn và phần lớn hơn pivot Tiếp theo, áp dụng đệ quy QuickSort cho từng phần Cuối cùng, kết hợp các phần đã sắp xếp để tạo thành mảng hoàn chỉnh Để minh họa, với dãy số nguyên, bước đầu tiên là chọn pivot, sau đó chia dãy thành hai phần, tiếp theo sắp xếp từng phần và cuối cùng là ghép lại để có dãy số đã được sắp xếp theo thứ tự tăng dần.
Câu 9 Thông tin về sinh viên gồm: mã số sinh viên (MaSV), họ tên
Bài viết yêu cầu thực hiện các nhiệm vụ lập trình C để quản lý danh sách sinh viên, bao gồm: a Khai báo cấu trúc danh sách liên kết đơn cho sinh viên, với kiểu danh sách là ListSV chứa các sinh viên kiểu SV; b Viết hàm hiển thị thông tin sinh viên xếp loại giỏi (điểm tổng kết ≥ 5.0); c Xây dựng hàm kiểm tra sự tồn tại của sinh viên theo mã sinh viên; d Tạo hàm đếm số sinh viên có điểm tổng kết loại khá (7 ≤ ĐTB < 8); e Viết hàm in đầy đủ thông tin của toàn bộ danh sách; f Liệt kê sinh viên sinh vào tháng 10; g Đưa ra danh sách sinh viên thi lại (điểm một trong hai môn dưới 5); h Xây dựng hàm đếm sinh viên bị học lại (điểm cả hai môn dưới 4).