TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
──────── * ───────
BÀI TẬP LỚN
MÔN: KỸ THUẬT LẬP TRÌNH
Đề tài:
Thao tác trên ADT
Sinh viên thực hiện: Bùi Đình Cường
Lại Ngọc Ánh
Phạm Thành Công
Nguyễn Văn Quang
Lê Đình Cường
Lớp : TTM – K53
Giáo viên hướng dẫn : TS. Vũ Thị Hương
Giang
Hà Nội, tháng 5 năm 2012
Kỹ thuật lập trình
MỤC LỤC
MỤC LỤC 2
LỜI NÓI ĐẦU 3
PHÂN CÔNG THÀNH VIÊN TRONG NHÓM 4
Nhiệm vụ chung: 4
PHÂN TÍCH YÊU CẦU VÀ THIẾT KẾ GIẢI PHÁP 5
CHƯƠNG 1. CÀI ĐẶT CHƯƠNG TRÌNH 13
TÀI LIỆU THAM KHẢO 20
PHỤ LỤC 21
Nhóm 35 - Lớp TTM K53
2
Kỹ thuật lập trình
LỜI NÓI ĐẦU
Một chương trình tốt là chương trình chạy thông, kiểm soát các lỗi tốt,

- Tổng hợp báo cáo
2 Lại Ngọc Ánh - Tính toán giá trị trung bình trong
ADT
- Độ phức tạp và thời gian tính toán
thực tế
- Viết hướng dẫn sử dụng
3 Lê Đình Cường - Tính toán độ lệch giữa hai phần tử
trong ADT
- Tính toán độ lệch toàn bộ ADT
4 Phạm Thành Công - Tìm kiếm giá trị cực đại và vị trí giá
trị đó trong ADT
- Tìm kiếm giá trị cực tiểu và vị trí giá
trị đó trong ADT
5 Nguyễn Đức Quang - Sắp xếp nổi bọt
- Sắp xếp chèn
- Sắp xếp trộn
Nhiệm vụ chung:
- Thiết kế IPO cho module được giao.
- Liệt kê các kỹ thuật lập trình đã sử dụng.
- Kiểm thử, debug lỗi cho các thành viên khác.
Nhóm 35 - Lớp TTM K53
4
Kỹ thuật lập trình
PHÂN TÍCH YÊU CẦU VÀ THIẾT KẾ GIẢI PHÁP
0.1. Mô tả yêu cầu bài toán
Bài tập lớn có mục tiêu ôn tập lại toàn bộ kiến thức đã học trong môn Kỹ
thuật lập trình. Bài tập lớn giúp sinh viên ôn tập và vận dụng các kiến thức đã
học từ bước thiết kế chương trình, thiết kế dữ liệu, mô tả giải thuật tới các kỹ
năng viết mã nguồn chương trình, debug bắt lỗi chương trình, kiểm thử.
Bài tập lớn giúp sinh viên tiếp cận một kiểu dữ liệu mới, kiểu dữ liệu trừu

chương trình được lưu trữ trong file CheckArray.cpp. Hàm menu() : gồm
các tùy chọn
- 1-13: các chức năng tính toán trên mảng
- Tùy chọn 1: có menu con cho phép
- Nạp thông tin vào từ bàn phím hoặc từ 1 file dữ liệu vào/ra (I/O data file)
- Quay lại menu chính
Nhóm 35 - Lớp TTM K53
5
Kỹ thuật lập trình
- Tùy chọn 2-13: có menu con cho phép
- In kết quả ra màn hình hoặc ra 1 file dữ liệu vào/ra (I/O data file)
- Quay lại menu chính
- 14: thoát khỏi chương trình.
0.2. Biểu đồ IPO
0.2.1. Khởi tạo phiên làm việc mới:
INPUT PROCESS OUTPUT
Dữ liệu cũ Tạo dữ liệu mới
0.2.2. Gán giá trị cho ADT
INPUT PROCESS OUTPUT
- Giá trị cần thêm
- ADT
- Thêm giá trị vào ADT
0.2.3. Sắp xếp
INPUT PROCESS OUTPUT
- Mảng các phần tử
chưa sắp xếp
- Sắp xếp theo Buble
Sort
- Sắp xếp theo
Insertion Sort

0.2.8. Tính độ lệch trung bình của các phần tử trong mảng
INPUT PROCESS OUTPUT
ADT - Tinh độ lệch cho toàn
bộ dữ liệu
- Tính trung bình
Độ lệch trung bình của
các phần tử trong
mảng
0.2.9. Tìm kiếm
INPUT PROCESS OUTPUT
- ADT
- Giá trị phần tử cần
tìm
- Tìm kiếm tuần tự
- Tìm kiếm nhị phân
- Số lượng phần tử có
giá trị cần tìm
- Vị trí các phần tử có
giá trị ấy (Với tìm kiếm
tuần tự)
0.2.10. Biểu diễn theo dạng Big-O, hiển thị thời gian tính theo thực
tế
INPUT PROCESS OUTPUT
Nhóm 35 - Lớp TTM K53
7
Kỹ thuật lập trình
ADT - Thực hiện các
module với cùng
một dữ liệu đầu
vào

Array(void);
////////////////////////////////////////////////////////////////////////////////////////////////////
// Phuong thuc huy
////////////////////////////////////////////////////////////////////////////////////////////////////
~Array(void);
////////////////////////////////////////////////////////////////////////////////////////////////////
Nhóm 35 - Lớp TTM K53
9
Nhập dữ liệu Xuất dữ liệu Tính toán
Khởi tạo ADT
Khởi tạo ADT
Chương trình làm việc với ADT
Chương trình làm việc với ADT
Tìm kiếm
Tìm kiếm
Sắp xếp
Sắp xếp
Từ bàn phím
Từ bàn phím
Từ file
Từ file
Nhị phân
Nhị phân
Chèn
Chèn
Nổi bọt
Nổi bọt
Cực tiểu và vị trí
Cực tiểu và vị trí
Cực đại và vị trí

////////////////////////////////////////////////////////////////////////////////////////////////////
// Hoan vi hai phan tu a va b
////////////////////////////////////////////////////////////////////////////////////////////////////
void swap(double &a, double &b);
////////////////////////////////////////////////////////////////////////////////////////////////////
// Sap xep theo bubble sort
// Return: + true > neu sap xep thanh cong
// + false > neu mang rong
////////////////////////////////////////////////////////////////////////////////////////////////////
bool SortByBubbleSort();
////////////////////////////////////////////////////////////////////////////////////////////////////
// Sap xep theo insertion sort
// Return: + true > neu sap xep thanh cong
// + false > neu mang rong
////////////////////////////////////////////////////////////////////////////////////////////////////
bool SortByInsertionSort();
////////////////////////////////////////////////////////////////////////////////////////////////////
// Sap xep theo selection sort
// Return: + true > neu sap xep thanh cong
// + false > neu mang rong
////////////////////////////////////////////////////////////////////////////////////////////////////
bool SortBySelectionSort();
////////////////////////////////////////////////////////////////////////////////////////////////////
// Tim kiem phan tu lon nhat va vi tri cua no
// Parameter: double &value : gia tri tim duoc
// int &num > so luong cac vi tri lon nhat
// Return: + Mang chua vi tri cua cac phan tu tim duoc
// + null neu mang chua co phan tu nao
////////////////////////////////////////////////////////////////////////////////////////////////////
int * FindMaxValueAndItsPosition(double &value, int &num);

// Gia tri chenh lech duoc hieu la: trung binh cong gia tri do lech cua tat ca cac
// cap (hai phan tu bat
ki) trong mang.
// Moi cap chi tinh mot
lan theo qui tac phan tu sau tru phan tu truoc
// Parameter: double &value : Gia tri chenh lech neu co
// Return: + true > Neu co
// + false > Mang rong
////////////////////////////////////////////////////////////////////////////////////////////////////
bool CaculateDiffentAllElements(double &value);
////////////////////////////////////////////////////////////////////////////////////////////////////
// Tim kiem kieu tuan tu trong mang
// Parameter: double value : Gia tri can tim kiem
// int &num > so luong cac vi tri tim thay
// Return: + Mang cac vi tri phan tu neu co
// + NULL > khong tim thay
////////////////////////////////////////////////////////////////////////////////////////////////////
int * SearchBySequentialSearch(double target, int &num);
////////////////////////////////////////////////////////////////////////////////////////////////////
// Tim kiem kieu nhi phan trong mang
// Parameter: double value : Gia tri can tim kiem
// Return: + vi tri phan tu neu co
// + -1 > khong tim thay
////////////////////////////////////////////////////////////////////////////////////////////////////
int SearchByBinarySearch(double target);
////////////////////////////////////////////////////////////////////////////////////////////////////
// Bieu dien do phuc tap va thoi gian tinh toan
// Parameter: FILE *ptr >Con tro file dau ra
////////////////////////////////////////////////////////////////////////////////////////////////////
void PresentComplexityAndTimeCalculating(FILE *ptr);

// Ghi cac phan tu ADT ra file
// FILE* ptr > con tro file
////////////////////////////////////////////////////////////////////////////////////////////////////
void WriteFile(FILE *ptr);};
0.5. Thiết kế giải thuật
0.5.1. Giải thuật: Cấp phát động bộ nhớ
- Thực hiện trong module thêm phần tử
- Yêu cầu: có thể thêm số phần tử không hạn chế, sao cho thỏa mãn yêu
cầu phần cứng
- Một lần chỉ cấp phát một vùng nhớ nhất định
- Lưu số lần đã cấp phát vùng nhớ, ban đầu được khởi tạo bằng 1
- Khi vùng nhớ đã cấp phát không còn đủ, tiến hành cấp phát tiếp một
vùng nhớ có kích thước đã qui định ở đầu. Tăng biến đếm số lần cấp
phát để phục vụ cho lần sau
0.5.2. Giải thuật: Đưa ra độ phức tạp và thời gian tính toán thực tế
- Yêu cầu: đảm bảo tính khách quan về mặt dữ liệu đầu vào
- Thực hiện:
o Khai báo một mảng số thực có kích thước bằng mảng hiện tại,
copy dữ liệu từ ADT sang mảng này
o Sau khi thực hiện xong một chức năng, khôi phục lại dữ liệu ban
đầu trong ADT nhờ copy từ mảng tạm thời vào
- Ý nghĩa: đầu vào không thay đổi cho mỗi chức năng, do đó thời gian
tính toán sẽ thể hiện sự so sánh một cách khách quan hơn
Nhóm 35 - Lớp TTM K53
12
Kỹ thuật lập trình
CHƯƠNG 1. CÀI ĐẶT CHƯƠNG TRÌNH
1.1. Các kỹ thuật lập trình đã áp dụng
STT Kỹ thuật / quy tắc Đối tượng và phạm vi
áp dụng

- Thêm phần tử vào
mảng
4. Thêm biến trung gian:
- Phân biệt các bước tính
toán
- Không nên lạm dụng, khai
báo quá nhiều mà sử dụng
it
- Sử dụng đúng tính chất
biến đã khai báo
- Các biến dùng
trong vòng lặp
- Khai báo các biến
trung gian trong
các hàm, …
5. Dùng biến con trỏ và con trỏ
trỏ tới con trỏ
- Sử dụng trong
ADT
II. Các kỹ
thuật viết mã
chương trình
hiệu quả
1. Định dạng chương trình rõ
ràng:
- Khoảng cách giữa các từ
trong một câu hợp lí
- Các khối lệnh, các phương
thức được phân biệt rõ ràng
- Các lệnh trong cùng khối

4. Một số kỹ thuật khác
- Viết mã nguồn rõ ràng,
mạch lạc
- Chú thích các phần hợp lý,
rõ ràng, dễ hiểu
- Toàn bộ chương
trình
III. Các kỹ
thuật thiết kế
chương trình
1. Nguyên tắc chung:
- Đơn giản, trực tiếp, rõ ràng
- Có cấu trúc tốt: tránh hoàn
toán dùng goto
- Toàn bộ chương
trình
2. Thiết kế giải thuật:
- Dùng phương pháp chia để
trị
- Thiết kế theo kiểu bottom –
up
- Toàn bộ chương
trình
3. Thiết kế dữ liệu:
- Sử dụng con trỏ lưu dữ liệu,
truy cập trực tiếp theo chỉ
số
- Phương thức và thuộc tính
rõ ràng
- Toàn bộ chương

- Người sử dụng chỉ cần
quan tâm tới đầu vào, đầu
ra mà không cần quan tâm
tới quá trình xử lý.
- Toàn bộ chương
trình
2. Tăng tốc độ chương trình:
- Tính toán trước các giá trị
cần sử dụng nhiều lần mà
giá trị ít thay đổi
- Loại bỏ những biểu thức dư
thừa
- Sử dụng hàm kiểu inline
- Toàn bộ chương
trình
V. Các kỹ
thuật bẫy lỗi
và lập trình
phòng ngừa
1. Bẫy lỗi:
- Dùng hàm bao gói
- Thiết kế giao diện và chức
năng rõ ràng
- Lập trình tránh tràn bộ đệm
- Toàn bộ chương
trình
2. Lập trình phòng ngừa
- Bao đóng và xử lí các khả
năng có thể của đầu vào.
Xử lý các lỗi ta dự kiến sẽ

tượng(ADT).
Nhóm đã hoàn thành các module theo yêu cầu của chương trình
a. Bùi Đình Cường
b. Lại Ngọc Ánh
c. Lê Đình Cường
d. Phạm Thành Công
e. Nguyễn Đức Quang
STT Chữ ký (Khai báo chức năng) Tình trạng Người
thực
hiện
1 NewObj 3 a
2 AddValue 3 a
3 SortByBubbleSort 3 e
4 SortByInsertionSort 3 e
5 SortBySelectionSort 3 e
6 FindMaxValueAndItsPosition 3 d
7 FindMinValueAndItsPosition 3 d
8 CalculateAverageValue 3 b
9 CalculateDifferenceTwoElements 3 c
10 CaculateDiffentAllElements 3 c
11 SearchBySequentialSearch 3 a
12 SearchByBinarySearch 3 a
13 PresentComplexityAndTimeCalculatin
g
3 b
Nhóm 35 - Lớp TTM K53
16
Kỹ thuật lập trình
1.3. Giao diện chương trình
Hình 1 Giao diện chương trình

trình hoặc sẽ thực hiện đồng thời cả hai thao tác: ghi ra màn hình và file. File
đầu ra có thể do người dùng nhập, nếu không sẽ là một file mặc định nào đó,
ví dụ: out.txt. Hình thức ghi file này như ghi log cho một server, khi người
dùng thực hiện một thao tác nào đó thì thao tác đó được ghi lại.
Nhóm 35 - Lớp TTM K53
19
Kỹ thuật lập trình
TÀI LIỆU THAM KHẢO
[1] Slide môn Kỹ thuật lập trình của cô Vũ Thị Hương Giang.
Nhóm 35 - Lớp TTM K53
20
Kỹ thuật lập trình
PHỤ LỤC
1. Hướng dẫn biên dịch mã nguồn
o Môi trường: Windows
o Đặt hai file: Array.h và CheckArray.cpp trong cùng thư mục
o Sử dụng trình biên dịch hỗ trợ biên dịch ngôn ngữ C++: DevC++
o Mở file CheckArray.cpp bằng trình biên dịch đã chọn
o Build chương trình
2. Hướng dẫn sử dụng chương trình
o Sau khi build chương trình thu được file chương trình:
CheckArray.exe
o Chạy file chương trình. Menu chương trình xuất hiện các chức năng
tương ứng từ 1 tới 14 như yêu cầu của đầu bài.
o Mặc định đầu vào chương trình sẽ nhập dữ liệu từ bàn phìm và xuất
dữ liệu ra màn hình.
o Chức năng 1 cho phép khởi tạo một phiên làm việc mới đồng thời
cho phép người dùng chọn cách thức nhập dữ liệu (từ bàn phím
hoặc từ file)
o Các chức năng từ 2 – 13 cho phép người dùng chọn cách thức xuất