Chào mừng các bạn đã đến tham gia buổi thuyết trình của chúng tôi
Thành Viên :
1. Lê Mạnh Hùng _ 87
2. Lê Văn Hưng
3. Đỗ Đình Liêm


Bài tập lớn
Môn : cấu trúc dữ liệu & giải THUậT
ĐỀ SỐ 17 :
Cho một DSLK đơn. Mỗi phần tử info là một ký tự (‘A’.. ‘Z’) và liên kết chỉ đến phần tử kế tiếp. Dùng ngôn ngữ Pascal viết chương trình thực hiện các yêu cầu sau :
a. Tạo một danh sách liên kết đơn với mô tả trên.
b. Viết chương trình con loại khỏi danh sách đã cho các phần tử vi phạm điều kiện tăng dần của danh sách. Biết rằng phần tử đầu tiên được giữ lại trong danh sách.
VD : DSLK biểu diễn : D F H G K M A B Q
DSLK sau khi loại : D F H K M Q
c. Với danh sách đã cho có thứ tự tăng dần (không có phần tử trùng nhau). Viết chương trình bổ sung vào danh sách này sao cho danh sách sẽ chứa đầy đủ các ký tự từ ‘A’ đến ‘Z’.

TỔNG QUAN SƠ LƯỢC VỀ BÀI TẬP LỚN
MÔN : CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Để giải quyết được yêu cầu của bài tập lớn chúng em đã đưa vào trong phần bài làm một số kiến thức lý thuyết cơ bản liên quan tới danh sách liên kết đơn, giúp cho người đọc nắm được cái nội dung cốt yếu mà người viết muốn diễn đạt khi lần đầu tiếp xúc với dạng bài tập này. Nội dung cụ thể sẽ được trình bày một cách khái quát như sau :
Nội dung bao gồm 2 phần :
Phần lý thuyết + Phần bài tập

I. Phần lý thuyết.
1. Cấu trúc dữ liệu và giải thuật
1.1 Khái niệm CTDL, GT
1.2 Các bước cơ bản giải quyết các bài toán trong tin học
B1: Xác định bài toán (cho cái gì ↔ input, tìm cái gì ↔ output)
B2: Tìm cấu trúc dữ liệu
B3: Tìm thuật toán ( liệt kê, lưu đồ, ngôn ngữ chương trình )
B4: Lập trình
B5: Thử và chạy trương trình
B6: Tối ưu chương trình
1.3 Phân tích và thiết kế bài toán

2. Mô hình dữ liệu - danh sách
2.1 Khái niệm danh sách là gì ?
2.2 Các phép toán trên danh sách
2.3 Cách xác định địa chỉ của một phần tử trong danh sách
2.4 Ưu, nhược điểm của phương pháp lưu trữ kế tiếp đối với danh sách
2.5 Tại sao phải xây dựng cấu trúc dữ liệu động

3. Cài đặt danh sách
+ Bằng mảng ( DS đặc )
+ Bằng Danh Sách liên kết
4. Danh sách liên kết
4.1 Phân loại : có 3 loại danh sách, song ở đây ta chỉ tìm hiểu về danh sách liên kết đơn.
4.2 Danh sách liên kết đơn
a. Khái niệm
b. Cấu trúc dữ liệu

c. Các phép toán trên danh sách liên kết đơn
+ Duyệt danh sách
+ Bổ sung 1 phần tử vào danh sách liên kết đơn
+ Loại bỏ 1 phần tử khỏi danh sách liên kết đơn
+ Ghép hai hay nhiều danh sách liên kết đơn thành một
+ Tách một danh sách thành nhiều danh sách
+ Sao chép một danh sách
+ Sắp xếp các phần tử trong danh sách theo một thứ tự đã được ấn định
+ Tìm kiếm trong danh sách một phần tử mà một trường nào đó có một giá trị ấn định
+ v.v...
Có rất nhiều phép toán được thực hiện trên danh sách liên kết đơn song ở đây chúng ta chỉ thao tác với một số phếp toán thường gặp.

5. Một số giải thuật tương ứng với từng phép toán trên danh sách liên kết đơn
Giải thuật bổ sung 1 phần tử vào danh sách
Giải thuật loại bỏ 1 phần tử khỏi danh sách
Giải thuật duyệt danh sách
Giải thuật tìm kiếm trên danh sách
Giải thuật sắp xếp trên danh sách

II. Phần bài tập
ĐỀ SỐ 17
Cho một DSLK đơn. Mỗi phần tử info là một ký tự (‘A’.. ‘Z’) và liên kết chỉ đến phần tử kế tiếp. Dùng ngôn ngữ Pascal viết chương trình thực hiện các yêu cầu sau :
Tạo một danh sách liên kết đơn với mô tả trên.
Viết chương trình con loại khỏi danh sách đã cho các phần tử vi phạm điều kiện tăng dần của danh sách. Biết rằng phần tử đầu tiên được giữ lại trong danh sách.
VD : DSLK biểu diễn : D F H G K M A B Q
DSLK sau khi loại : D F H K M Q
c. Với danh sách đã cho có thứ tự tăng dần (không có phần tử trùng nhau). Viết chương trình bổ sung vào danh sách này sao cho danh sách sẽ chứa đầy đủ các ký tự từ ‘A’ đến ‘Z’.

Hướng giải quyết bài toán :
a. Tạo một danh sách liên kết đơn theo thứ tự tăng dần, mỗi phần tử info là một ký tự (‘A’ .. ‘Z’) và liên kết chỉ đến phần tử kế tiếp.
+ Tạo một danh sách liên kết đơn mà trường info có chứa đầy đủ các ký tự từ ‘A’ đến ‘Z’ , trường Next chỉ đến phần tử kế tiếp.

b. Viết chương trình con loại khỏi danh sách đã cho các phần tử vi phạm điều kiện tăng dần của danh sách. Biết rằng phần tử đầu tiên được giữ lại trong danh sách.
So sánh trường Data của nút giữa với 2 nút ngay cạnh nó → có hay không loại bỏ nút đó.
Nếu phần tử ở cuối là phần tử bị loại thì ta phải gán địa chỉ Nil cho trường Next của phần tử cuối cùng của danh sách sau khi đã loại bỏ hết các phần tử vi phạm điều kiện tăng dần.

c. Với danh sách đã cho có thứ tự tăng dần (không có phần tử trùng nhau). Viết chương trình bổ sung vào danh sách này sao cho danh sách sẽ chứa đầy đủ các ký tự từ ‘A’ đến ‘Z’.
Kiểm tra xem trong danh sách đã có đủ hết các ký tự từ ‘A’ đến ‘Z’ hay chưa.
Bổ sung ký tự còn thiếu vào danh sách sao cho danh sách sau khi bổ sung vẫn đảm bảo thứ tự tăng dần.
Nếu bổ sung vào cuối danh sách thì ta phải gán trường Next của nút mới bổ sung bằng Nil.