BT DSLK đơn
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (543.51 KB, 3 trang )
Simply Linked List
Sunday, March 9, 2014
12:03 PM
Cài đặt các hàm sau:
1. Tạo danh sách liên kết đơn lưu các số nguyên dương. Trong đó, số lượng phần tử danh
sách lưu trữ ban đầu gồm N phần tử được phát sinh ngẫu nhiên.
Gồm các thao tác sau:
1. Tạo kiểu dữ liệu Node.
2. Tạo kiểu dữ liệu danh sách List.
3. Viết hàm tạo 1 danh sách liên kết đơn rỗng.
4. Viết hàm tạo 1 nút có trường info bằng X.
5. Hàm thêm 1 phần tử có khoá X vào danh sách liên kết đơn (thêm đầu / thêm cuối).
6. Hàm thêm cho phép thêm N phần tử vào dslk đơn
2. Viết hàm Xuất danh sách liên kết đơn ra màn hình.
3. Viết hàm Tìm phần tử có giá trị Y (nhập từ bàn phím). Kết quả trả về true nếu tìm thấy,
trả về false nếu không tìm thấy.
4. Sắp xếp DSLK đơn ở trên bằng thuật toán sắp xếp Selection hoặc Interchange.
5. Viết hàm Thêm 1 nút vào danh sách đã được sắp xếp sao cho danh sách vẫn có thứ tự.
6. Viết hàm Join thực hiện nối 2 danh sách L1 và L2 thành L, sao cho sau khi nối ds L1 và
ds L2 không bị thay đổi. Và sự thay đổi giá trị của L không ảnh hưởng đến L1, L2.
Input L1, L2
Output L
Ví dụ:
L1:
5
1
0
3
9
L2:
6
7
2
4
Sau khi nối:
L:
5
1
0
3
9
6
7
2
4
L1:
5
1
0
3
9
L2:
6
7
2
4
Sau đó đổi giá trị 0 trong ds L thành 20 thì ta được:
L:
5
1
20
3
9
6
7
2
4
L1:
5
1
0
3
9
L2:
6
7
2
4
7. Viết hàm Partition thực hiện phân vùng ds L thành 3 phần: node* pivot, ds L1 và ds L2.
Biết rằng: pivot là node đầu của ds L, L1 là ds gồm các node có trường <= pivot, L2 gồm
các node có trường > pivot và sau khi partition thì ds L rỗng.
Input: L
Output: pivot, L1, L2
Ví dụ:
L:
5
1
0
3
9
6
7
2
4
DS-A Practice Page 1
L:
5
1
Sau khi partition:
Pivot: 5
L1:
1
0
L2:
9
6
L:
Empty
0
3
3
7
2
9
6
7
2
4
4
8. Viết hàm Join2 thực hiện nối L1 - node *x- ds L2 thành L. Sau khi nối xong thì L1, L2
rỗng
Input: L1, x, L2
Output: L
Ví dụ:
L1:
1
0
3
2
4
x:
5
L2:
9
6
7
Sau khi Join:
L:
1
0
3
2 4 5
9
6
7
L1, L2: Empty
9. Viết thuật toán QuickSort. Gợi ý: sử dụng 2 hàm Partition và Join2
10. Tạo danh sách lC tăng dần từ danh sách lA và lB
Ví dụ:
Nhập danh sách:
1A:
1B:
Kết quả danh sách lC là:
11. Viết hàm tách đôi danh sách L thành 2 danh sách L1 và L2. Nếu L lẻ thì số lượng phần tử
L1 nhận được sẽ lớn hơn L2 1 phần tử.
Ví dụ;
L: 5
1
0
3
9
6
7
2
4
Sau khi chia đôi.
L1: 5
1
0
3
9
L2: 6
7
2
4
12. Hoán đổi 2 danh sách liên kết 1A, 1B sao cho 1A chứa toàn chữ số chẵn và 1B chứa toàn
chữ số lẻ
Ví dụ:
Kết quả danh sách là:
1A:
DS-A Practice Page 2
1A:
1B:
DS-A Practice Page 3
