Bài tập lớn môn học cấu trúc dữ liệu và giải thuật sinh viên sử dụng (không xây dựng) chỉ sử dụng cấu trúc vector hoặc list có sẵn trong stl làm bài toán quản lý theo các yêu cầu

 SapXep : Sắp xếp danh sách bears sử dụng hàm sort của list để sắp xếp theo tên TenBear của mỗi Bear và in ra màn hình.- bears.sort: Hàm này sắp xếp các phần tử trong list theo một điều

TRƯỜNG ĐẠI HỌC GIAO THÔNG VÂN TẢI

KHOA CÔNG NGHỆ THÔNG TIN

Bài tập lớn môn học

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

Giảng viên hướng dẫn: TS Hoàng Văn Thông

Sinh viên thực hiện: Bùi Vũ Thu Hà

Lớp: CNTT KHMT- K64

Đề bài số: 32

Hà Nội, ngày 11 tháng 11 năm 2024

Mục Lục

Phần I: Bài toán quản lý 2

I.1: Đề bài 2

I.2: Phân tích bài toán 2

I.2.1: Xác định các yêu cầu của bài toán, xác định các lớp, các thuộc tính, các phương thức của lớp 2

- Yêu cầu của bài toán: 2

- Xác định các lớp, các thuộc tính, các phương thức của lớp: 3

I.2.2 Mô tả chức năng của từng lớp, từng phương thức 4

I.3: Cài đặt các lớp và hàm main bằng C++ 6

I.4: Phân tích thời gian chạy của từng phương thức có trong các lớp 6

I.5: Kết quả bài quản lý 11

Phần II: Bài toán STACK( Đề số 32) 12

II.1: Đề bài – Đề số 32 12

II.2: Cấu trúc Stack: 13

II.2.1: Định nghĩa Stack: 13

II.2.2: Cấu trúc Stack 13

II.3: Phân tích bài toán 14

II.3.1 Xác định các yêu cầu của bài toán, xác định các lớp, các thuộc tính, các phương thức của lớp 14

- Yêu cầu bài toán: 14

- Xác định các lớp, các thuộc tính, các phương thức của lớp: 14

II.3.2 Mô tả chức năng của từng lớp, từng phương thức 16

Stack bằng mảng: 16

Stack bằng danh sách liên kết: 16

Ứng dụng stack lập trình giải bài toán ngoặc: 17

II.4: Cài đặt các lớp và hàm main bằng C++ 18

II.5 Phân tích thời gian chạy của từng phương thức có trong các lớp 18

II.6: Kết quả bài toán 21

Phần III: Tài liệu tham khảo 23

Phần I: Bài toán quản lý

Sinh viên làm bài tập quản lý ( đề tài do sinh viên tự đề xuất).

+ Xây dựng ít nhất 03 lớp gồm:

- Xây dựng lớp đối tượng quản lý có ít nhất 04 trường dữ liệu (ví dụ sinhviên gồm mã, tên, tuổi, điểm) với ít nhất 03 gồm toán tử >> và << và 01 toán tử sosánh < (theo 1 trường nào đó ví dụ điểm)

- Xây dựng lớp danh sách đối tượng quản lý (dùng cấu trúc vector nếu sốcuối cùng mã sinh viên là số chẳn, dòng cấu trúc list nếu số cuối cùng mã sinh viên là

số lẻ) cho phép nhập, xuất danh sách, sắp xếp danh sách (dùng hàm sort có sẵn đốivới vector và phương thức sort có sẵn đối với list) và ít nhất 03 thao tác ví dụ tìmmax, min, tìm kiếm, xóa, thêm, sửa …

- Xây dựng lớp app để quản lý có menu và thực hiện các thao tác ở lớpdanh sách

- Viết hàm main chạy chương trình

Đề tài: Quản lý mặt hàng gấu sử dụng cấu trúc dữ liệu danh sách

liên kết đơn.

I.2: Phân tích bài toán

I.2.1: Xác định các yêu cầu của bài toán, xác định các lớp, các thuộc tính, các phương thức của lớp

- Yêu cầu của bài toán:

        Sử dụng (không xây dựng ) chỉ sử dụng cấu trúc vector hoặc list có sẵn trong STL làm bài toán quản lý với các phương thức Xây dựng ít nhất 03 lớp gồm:

+) Xây dựng lớp đối tượng quản lý có ít nhất 04 trường dữ liệu (ví dụ sinh viêngồm mã, tên, tuổi, điểm) với ít nhất 03 gồm toán tử >> và << và 01 toán tử so sánh

+) Xây dựng lớp danh sách đối tượng quản lý (dùng cấu trúc vector nếu sốcuối cùng mã sinh viên là số chẳn, dòng cấu trúc list nếu số cuối cùng mã sinh viên là

số lẻ) cho phép nhập, xuất danh sách, sắp xếp danh sách (dùng hàm sort có sẵn đối

với vector và phương thức sort có sẵn đối với list) và ít nhất 03 thao tác ví dụ tìmmax, min, tìm kiếm, xóa, thêm, sửa …

+) Xây dựng lớp app để quản lý có menu và thực hiện các thao tác ở lớp danhsách

- Xác định các lớp, các thuộc tính, các phương thức của lớp:

+) Xây dựng lớp Bear:

 Thuộc tính:.

 MaBear: Mã cảu gấu bông

 TenBear: Tên cảu gấu bông

 DonGia: Giá của gấu bông

 SoLuong: Số lượng gấu bông

 Phương thức:

 getMaBear(), getTenBear(), getDonGia(), getSoLuong(): Getter

để lấy thông tin của đối tượng Bear

 setTenBear(), setDonGia(), setSoLuong(): Setter để cập nhật thông tin của đối tượng Bear

 operator>>: Nhập dữ liệu cho đối tượng Bear từ người dùng

 operator<<: In dữ liệu của đối tượng Bear

 operator<: So sánh đối tượng Bear theo SoLuong

 SapXep(): Sắp xếp danh sách gấu bông theo tên

 ThemBear(): Thêm một đối tượng Bear vào danh sách

 TimKiemBear(): Tìm kiếm gấu bông theo mã

 MaxMin(): Tìm gấu bông có giá cao nhất và thấp nhất

 XoaBear(): Xóa gấu bông theo mã

 SuaBear(): Cập nhật thông tin của gấu bông theo mã

 writeFile(): Ghi danh sách gấu bông vào file

+) Xây dựng lớp App:

 Thuộc tính:.

 Các phương thức getter (getMaBear(), getTenBear(), ) và setter

(setTenBear(), setDonGia(), ): Cho phép truy cập và thay đổi giá trị các thuộc tính của Bear

 friend istream& operator>>(istream& is, Bear& b): Hàm bạn bè để nhập thông tin của Bear từ cin

 friend ostream& operator<<(ostream& os, const Bear& bear): Hàm bạn bè

để xuất thông tin của Bear ra cout

 bool operator<(const Bear& other): Toán tử so sánh để so sánh hai đối tượng Bear dựa trên SoLuong Hàm này giúp sắp xếp các đối tượng Bear theo số lượng trong danh sách

 Đọc Dữ Liệu Từ File (readFile): Đọc dữ liệu các bear từ file (khohang.txt)

và thêm vào danh sách

- Dùng operator>> để đọc từng đối tượng từ file

- Nếu không thể mở file, thông báo lỗi và kết thúc.

 Xuat(): Xuất danh sách bear trong bộ nhớ và từ file khohang.txt ra màn hình

 SapXep() : Sắp xếp danh sách bears sử dụng hàm sort của list để sắp xếp theo tên TenBear của mỗi Bear và in ra màn hình.

- bears.sort(): Hàm này sắp xếp các phần tử trong list theo một điều kiện Trong trường hợp này, điều kiện là so sánh tên của Bear (a.getTenBear() và b.getTenBear())

 Thêm Bear (ThemBear): Hàm này thêm một đối tượng Bear vào danh sách bears sử dụng phương thức push_back()

 TimKiemBear(): Duyệt qua danh sách bears và tìm kiếm một đối tượng Bear trong danh sách bears bằng maBear sử dụng phương thức push_back() Nếu tìm thấy, in thông tin của Bear đó, ngược lại, thông báo không tìm thấy

 XoaBear(): Hàm này xóa một đối tượng Bear khỏi danh sách bears theo maBear

- bears.erase(it): Xóa phần tử mà iterator it đang trỏ đến

- Nếu không tìm thấy Bear với mã tương ứng, thông báo không tìm thấy

 MaxMin: Hàm này tìm và hiển thị đối tượng Bear có giá trị cao nhất và thấp nhất về DonGia

- bears.empty(): Kiểm tra xem danh sách bears có trống không

- max_element và min_element: Tìm đối tượng Bear có giá trị

DonGia cao nhất và thấp nhất trong danh sách

- a.getDonGia(), b.getDonGia: Lấy giá trị DonGia của mỗi đối tượng Bear trong danh sách

 SuaBear(): Hàm này cho phép sửa thông tin của một Bear trong danh sách theo maBear

- bear.getMaBear():Lấy MaBear của mỗi đối tượng Bear trong danh sách

 writeFile(): Mở file để ghi, duyệt qua danh sách các đối tượng Bear và ghi từng đối tượng vào file, sau đó đóng file khi xong.

- ofstream là một đối tượng của lớp ofstream dùng để ghi dữ liệu vào một file

- filename là tên tệp tin mà bạn muốn mở hoặc tạo

- ios::trunc là một chế độ mở file: Nếu file đã tồn tại, nội dung cũ của nó

sẽ bị xóa (chỉ ghi mới) Nếu file không tồn tại, nó sẽ được tạo ra mới

 Lớp App:

 App: Lớp này quản lý giao diện người dùng, bao gồm các menu cho phép người dùng thực hiện các hành động như nhập, xuất, tìm kiếm, sắp xếp, xóa, sửa thông tin về Bear.

 menu(): Hàm này thực hiện vòng lặp để người dùng chọn chức năng từ menu và gọi các phương thức tương ứng từ lớp BearList để thao tác với dữ liệu

 Hàm main:

 main(): Hàm này là điểm bắt đầu của chương trình Nó tạo một đối tượng App và gọi phương thức menu() để hiển thị giao diện người dùng cho phép người dùng thao tác với dữ liệu về Bear

I.3: Cài đặt các lớp và hàm main bằng C++

Code đầy đủ hàm main: GT.Nam2_Ki1/tree/master/Phan_A

https://github.com/buithuha05/BTL-CTDL-I.4: Phân tích thời gian chạy của từng phương thức có

cout << "Nhap ten bear: ";

1 Nhap() int size;

cout << "Nhap so luong bear: ";

return;

}

O(n)

Bear b;

while (file >> b) { bears.push_back(b);

} file.close();

3 Xuat() // Xuat du lieu ra man hinh

cout << "\n=== Danh sach bear trong bo nho ===\n";

for (const auto& bear : bears) { cout << bear << endl;

} file.close();

O(n)

4 SapXep() // Sap xep danh sach theo ten

bears.sort([](const Bear& a, const Bear& b) {

cout << bear << "\n";

}

5 ThemBear() bears.push_back(b); O(1)

6 TimKiemBear() bool found = false;

for (const auto& bear : bears) {

if (bear.getMaBear() == maBear) {

cout << "***Tim thay bear :\n"

<< bear << endl;

found = true;

break;

} }

if (!found) { cout << "***Khong tim thay bear

co ma: " << maBear << endl;

8 XoaBear() auto it = find_if(bears.begin(),

bears.end(), [&maBear](const Bear&

bear) { return bear.getMaBear() ==

maBear;

});

O(n)

if (it != bears.end()) { bears.erase(it);

cout << "***Xoa thanh cong!\n";

} else { cout << "***Khong tim thay bear

co ma nay!\n";

}

9 SuaBear() bool found = false;

for (auto& bear : bears) {

if (bear.getMaBear() == maBear) {

cout << "***Nhap thong tin moi cho bear co ma " << maBear << ":\

if (!found) { cout << "***Khong tim thay bear

mo tep tin.\n";

return;

} for (const auto& bear : bears) { file << bear << "\n";

}cout << "***Da luu vao trong file khohang.txt";

file.close();

Lớp App:

Lớp này quản lý giao diện người dùng, bao gồm các menu cho phép ngườidùng thực hiện các hành động như nhập, xuất, tìm kiếm, sắp xếp, xóa, sửathông tin về Bear Sau khi kết thúc chương trình các thông tin của đối tượngsau khi được thêm, xóa hay thay đổi sẽ in lại vào tệp “khohang.txt

I.5: Kết quả bài quản lý

Phần II: Bài toán STACK( Đề số 32)

Sinh viên làm 1 trong các bài sau (có danh sách phân công kèm theo) Yêu cầu các cấu trúc dữ liệu ngăn xếp, hàng đợi, vector, list, … phải tự code không sử dụng thư viện có sẵn

II.1: Đề bài – Đề số 32

1 Cài đặt Stack bằng 2 cách: Mảng và danh sách liên kết

2 Mô phỏng hoạt động của stack bằng cách xây dựng chương trình sau:

Bạn được cho một ngăn xếp rỗng và một số truy vấn với ngăn xếp này Các truy vấn

là những truy vấn cơ bản của ngăn xếp: Đẩy vào, lấy ra, in ra phần tử ở đỉnh, các truyvấn có dạng:

 1 n: Đẩy số nguyên n vào ngăn xếp

 2 Loại bỏ phần tử ở đầu ngăn xếp (nếu ngăn xếp rỗng thì thao tác này không

có hiệu lực)

 3 In ra phần tử ở đỉnh ngăn xếp (không lấy ra khỏi ngăn xếp, nếu ngăn xếprỗng thì in ra Empty!) Dữ liệu vào

 Dòng đầu chứa số nguyên dương TT là số truy vấn;

 TT dòng tiếp theo, mỗi dòng chứa một truy vấn Giới hạn:

3 Ứng dụng stack lập trình giải bài toán sau:

Cho dãy ngoặc đúng gồm n dấu mở ngoặc (và n dấu đóng ngoặc) Các dấu ngoặcđược đánh số thứ tự từ 1 đến 2n Hãy liệt kê chỉ số của các cặp dấu mở ngoặc và đóngngoặc tương ứng

Dữ liệu vào:

 Gồm một dòng duy nhất chứa xâu ký tự biểu diễn dãy ngoặc.

II.2: Cấu trúc Stack:

II.2.1: Định nghĩa Stack:

- Stack là cách tổ chức lưu trữ các đối tượng dưới dạng một danh sách tuyến tính mà việc bổ sung đối tượng và lấy các đối tượng ra được thực hiện ở cùng một đầu của danh sách

- Stack được gọi là danh sách kiểu LIFO (Last In First Out - vào sau ra trước)

II.2.2: Cấu trúc Stack

- Cấu trúc dữ liệu Stack (Ngăn xếp) là một cấu trúc dữ liệu trừu tượng được sửdụng để lưu trữ và truy cập dữ liệu theo nguyên tắc LIFO (Last In, First Out), tức làphần tử được đưa vào cuối cùng sẽ được lấy ra đầu tiên.

- Các thao tác cơ bản trong Stack:

· push(Object o): bổ sung đối tượng o vào cuối Stack

· pop(): xóa phần tử cuối cùng của Stack

· top(): trả lại tham chiếu đến phần tử được bổ sung vào cuối cùng của Stack

· size(): trả lại số phần tử hiện lưu trữ trong Stack

· empty(): trả lại giá trị kiểu boolean để xác định Stack có lưu trữ phần tử nào hay không

- Chú ý: Với Stack rỗng thì phép toán pop() và top() không thể thực hiện

được

II.3: Phân tích bài toán

II.3.1 Xác định các yêu cầu của bài toán, xác định các lớp, các thuộc tính, các phương thức của lớp.

- Yêu cầu bài toán:

       ● Cài đặt Stack bằng 2 cách: - Mảng

      - Danh sách liên kết

       ● Mô phỏng hoạt động của stack bằng cách xây dựng chương trình:

Một ngăn xếp rỗng và một số truy vấn với ngăn xếp này đẩy vào, lấy ra, in raphần tử ở đỉnh, các truy vấn có dạng:

 1 n: Đẩy số nguyên n vào ngăn xếp

 2 Loại bỏ phần tử ở đầu ngăn xếp (nếu ngăn xếp rỗng thì thao tác nàykhông có hiệu lực)

 3 In ra phần tử ở đỉnh ngăn xếp (không lấy ra khỏi ngăn xếp, nếu ngănxếp rỗng thì in ra Empty!)

      (với input, output và điều kiện có trên đề bài)

      ● Ứng dụng stack lập trình giải bài toán sau:

         Cho dãy ngoặc đúng gồm n dấu mở ngoặc (và n dấu đóng ngoặc) Các dấu ngoặc được đánh số thứ tự từ 1 đến 2n Hãy liệt kê chỉ số của các cặp dấu mở ngoặc và đóng ngoặc tương ứng:

       (với input, output và điều kiện có trên đề bài)

- Xác định các lớp, các thuộc tính, các phương thức của lớp:

       ● Cài đặt Stack bằng 2 cách:

      Lớp Node:

        Thuộc tính:

data

next Lớp Stack:

        Thuộc tính:

topNode

num        Phương thức:

       ● Ứng dụng stack lập trình giải bài toán sau

      Cả hai bài toán này đều áp dụng phương pháp stack bằng mảng nên lớp Stack đều có thuộc tính giống ở trên

II.3.2 Mô tả chức năng của từng lớp, từng phương thức

 Stack bằng mảng:

1 Thuộc tính:

 Space: Số lượng phần tử hiện có trong stack

 Size: Sức chứa của stack (số lượng phần tử tối đa có thể chứa). 

 elem: Mảng động để lưu trữ các phần tử trong stack. 

2 Phương thức:

Stack(): Constructor mặc định, khởi tạo stack với giá trị Space=0, Size=0, vàgán elem=NULL

~Stack(): Giải phong bộ nhớ cấp phát cho elem nếu elem khác NULL

Stack(Stack<T>& s):Sử dụng toán tử gán để thực hiện sao chép sâu từ s đểkhởi tạo ngăn xếp.

Toán tử gán operator=: Xử lý sao chép sâu từ một đối tượng Stack khác.Kiểm tra tự gán (self-assignment) và sau đó sao chép kích thước, không gian

và các phần tử từ s sang đối tượng hiện tại

size(): Trả về số lượng phần tử hiện tại trong stack

empty(): Kiểm tra xem stack có rỗng hay không (trả về true nếu Size = 0, falsenếu không)

top(): Trả về phần tử trên cùng của stack (phần tử ở vị trí Size-1 trong mảngelem). 

pop(): Xóa phần tử trên cùng của stack (giảm giá trị Size đi 1 ). 

push(T val): Thêm phần tử mới val vào ngăn xếp Nếu kích thước hiện tại bằngvới sức chứa (Size == Space), nó tăng gấp đôi dung lượng (Space) để lưu trữ thêmphần tử, sau đó sao chép các phần tử hiện có sang mảng mới

 clear(): Xóa toàn bộ các phần tử trong stack (đặt Size=0)

Stack bằng danh sách liên kết:

Lớp Node:

1 Thuộc tính:

 data: Dữ liệu của node

 next: Con trỏ đến node kế tiếp trong danh sách liên kết. 

2 Phương thức :

Node(T val): Khởi tạo một nút mới với data được gán là val và next đượcgán là NULL

Lớp Stack:

1 Thuộc tính:

 topNode: Con trỏ đến phần tử đầu của stack

 num: Số lượng phần tử hiện tại trong stack

2 Phương thức:

 Stack(): Constructor mặc định, khởi tạo stack với topNode=NULL và num=0

 ~Stack(): Giải phóng bộ nhớ cấp phát

 size(): Trả về số lượng phần tử hiện tại trong stack (num). 

 empty(): Kiểm tra xem stack có rỗng hay không (trả về true nếu num=0, falsenếu không)

 top(): Trả về giá trị của phần tử đỉnh của stack (data của topNode). 

 pop(): Xoá phần tử ở đầu ngăn xếp Nếu ngăn xếp không rỗng (num > 0), hàmsẽ:

- Tạo một con trỏ temp để trỏ đến topNode

- Di chuyển topNode đến phần tử tiếp theo (topNode->next)

- Xoá temp và giảm biến đếm num

 push(T val): Thêm một phần tử mới có giá trị val vào đầu ngăn xếp Thực hiện:

- Tạo một Node mới có giá trị val

- Liên kết newNode->next tới topNode

- Cập nhật topNode trỏ tới newNode

- Tăng biến đếm num

 clear(): Xoá tất cả các phần tử trong ngăn xếp Thực hiện:

- Lặp qua các phần tử từ topNode cho đến khi ngăn xếp trống

- Mỗi lần lặp, cập nhật topNode tới phần tử tiếp theo và xoá phần tử hiện tại

- Sau khi xoá xong, đặt num về 0

Ứng dụng stack lập trình giải bài toán ngoặc:

Mô ttả thuật toán:

1 Đọc đầu vào:

o Đọc chuỗi từ người dùng chứa dấu ngoặc mở ( và đóng ) Chuỗi này

có thể chứa các ký tự khác ngoài dấu ngoặc

2 Khởi tạo các cấu trúc dữ liệu: