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
Giang
: TS. Vũ Thị Hương
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
CHƯƠNG 1.
PHÂN TÍCH YÊU CẦU VÀ THIẾT KẾ GIẢI PHÁP...................5
1.1. Mô tả yêu cầu bài toán........................................................................5
1.2. Biểu đồ IPO...........................................................................................6
1.2.1. Khởi tạo phiên làm việc mới:...........................................................6
1.2.2. Gán giá trị cho mảng.......................................................................6
1.2.3. Sắp xếp............................................................................................6
1.2.4. Tìm giá trị lớn nhất...........................................................................6
1.2.5. Tìm giá trị nhỏ nhất..........................................................................6
1.2.6. Tìm giá trị trung bình của mảng.......................................................7
1.2.7. Tìm độ lêch giữa 2 phần tử trong mảng..........................................7
1.2.8. Tính độ lệch trung bình của các phần tử trong mảng......................7
1.2.9. Tìm kiếm..........................................................................................7
1.2.10. Biểu diễn theo dạng Big-O, hiển thị thời gian tính theo thực tế....7
1.2.11. Hiển thị dữ liệu..............................................................................8
1.2.12. Thoát.............................................................................................8
1.3. Thiết kế chương trình..........................................................................9
1.4. Thiết kế dữ liệu....................................................................................9
1.5. Thiết kế giải thuật..............................................................................12
1.5.1. Giải thuật: Cấp phát động bộ nhớ.................................................12
1.5.2. Giải thuật: Đưa ra độ phức tạp và thời gian tính toán thực tế.......12
CHƯƠNG 2.
CÀI ĐẶT CHƯƠNG TRÌNH.....................................................13
2.1. Các kỹ thuật lập trình đã áp dụng....................................................13
2.2. Kết quả chương trình........................................................................16
2.3. Giao diện chương trình.....................................................................17
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN...........................................................19
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,
phòng ngừa, bẫy lỗi hiệu quả, dễ dàng và thân thiện với người dùng đồng thời
mã nguồn có khả năng tái sử dụng cao, …
Đó chỉ là một trong số những phần rất nhỏ mà chúng em học được từ môn
Kỹ thuật lập trình. Để cho ra đời một chương trình, sản phẩm phần mềm cần
có nhiều qui trình và vòng đời đan xen nhau từ khâu phân tích, thiết kế
chương trình, lập trình, kiểm thử, viết tài liệu, … Trong mỗi khâu lại chia ra
thành các công đoạn nhỏ đòi hỏi lập trình viên phải tuân thủ.
Thông qua bài tập lớn môn Kỹ thuật lập trình, chúng em không những
được tìm hiểu sâu hơn về mặt lý thuyết mà còn được trực tiếp vận dụng
những kiến thức đã được học trên lớp, những kiến thức đọc nâng cao vào
trong một ứng dụng thực tế.
Chúng em xin gửi lời cảm ơn chân thành tới cô Vũ Thị Thanh Giang, trong
quá trình học trên lớp cũng như làm bài tập lớn, cô đã cung cấp cho chúng em
những kiến thức và kỹ năng cơ bản đồng thời có những hướng dẫn và định
hướng giúp chúng em hoàn thành bài tập lớn này.
Nhóm 35 - Lớp TTM K53
3
Kỹ thuật lập trình
PHÂN CÔNG THÀNH VIÊN TRONG NHÓM
STT
Thành viên
1
Bùi Đình Cường
-
2
Lại Ngọc Ánh
-
3
4
Lê Đình Cường
-
Phạm Thành Công
-
5
Nguyễn Đức Quang
-
Công việc
Phân công công việc
Viết template cho class (Thiết kế dữ
liệu)
Xây dựng phương thức nhập dữ
liệu
Xây dựng module tìm kiếm (tuần tự
+ nhị phân)
Đễ xuất giải thuật tính toán thời
gian thực tế, giải thuật cấp phát
động
Tổng hợp báo cáo
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
Tính toán độ lệch giữa hai phần tử
trong ADT
Tính toán độ lệch toàn bộ ADT
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
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
1.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
tượng. Kiểu dữ liệu có cả các thuộc tính và phương thức. Ngoài ra, bài tập lớn
giúp học sinh ôn lại kiến thức liên quan tới các thuật toán cơ bản: sắp xếp, tìm
kiếm, …
Yêu cầu cụ thể của bài toán:
- Sử dụng tất cả các kỹ thuật đã được học trong môn Kỹ thuật lập trình
- Tạo một ADT: Array có thuộc tính là mảng các số thực và số lượng
phần tử của mảng đó
- Thực hiện các thao tác trên mảng này:
o Khởi tạo một phiên bản mới của chính nó
o Gán giá trị cho các thành phần thông tin của một đối tương Array
o Sắp xếp các phần tử của mảng theo giải thuật bubble sort
o Sắp xếp các phần tử của mảng theo giải thuật insertion sort
o Sắp xếp các phần tử của mảng theo giải thuật selection sort
o Tìm giá trị lớn nhất được lưu trữ trong mảng và vị trí của các
phần tử có giá trị lớn nhất trong mảng
o Tìm giá trị nhỏ nhất được lưu trữ trong mảng và vị trí của các
phần tử có giá trị nhỏ nhất trong mảng
o Tìm giá trị trung bình của các phần tử trong mảng
o Tìm độ lệch về giá trị giữa 2 phần tử có vị trí biết trước trong
mảng
o Tìm độ lệch trung bình về giá trị của các phần tử trong mảng
o Tìm kiếm (theo giải thuật sequential search) phần tử của mảng có
giá trị là x ; nếu tìm thấy thì đưa ra vị trí của phần tử đó trong
mảng, nếu không thì trả lại giá trị là 0.
o Tìm kiếm (theo giải thuật binary search) phần tử của mảng có giá
trị là x ; nếu tìm thấy thì đưa ra vị trí của phần tử đó trong mảng,
nếu không thì thông báo là không tìm thấy phần tử như vậy.
o Biểu diễn độ phức tạp tính toán theo ký pháp big-O và hiện thị
thời gian tính toán thực tế bằng micro-second.
- Viết một chương trình cung cấp các chức năng để kiểm tra ADT này;
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.
1.2. Biểu đồ IPO
1.2.1. Khởi tạo phiên làm việc mới:
INPUT
PROCESS
Dữ liệu cũ
Tạo dữ liệu mới
OUTPUT
1.2.2. Gán giá trị cho ADT
INPUT
- Giá trị cần thêm
- ADT
PROCESS
OUTPUT
- Thêm giá trị vào ADT
1.2.3. Sắp xếp
INPUT
- Mảng các phần tử
chưa sắp xếp
PROCESS
- Sắp xếp theo Buble
Sort
- Sắp xếp theo
Insertion Sort
- Sắp xếp theo
Selection Sort
OUTPUT
-Mảng các phần tử đã
được sắp xếp theo thứ
tự từ nhỏ đến lớn
1.2.4. Tìm giá trị lớn nhất
INPUT
ADT
PROCESS
Tìm giá trị lớn nhất và
vị trí
OUTPUT
Giá trị lớn nhất và vị trí
của nó
1.2.5. Tìm giá trị nhỏ nhất
INPUT
PROCESS
OUTPUT
ADT
Tìm giá trị nhỏ nhất và
Giá trị nhỏ nhất và vị trí
Nhóm 35 - Lớp TTM K53
6
Kỹ thuật lập trình
vị trí
của nó
1.2.6. Tìm giá trị trung bình của mảng
INPUT
ADT
PROCESS
Tìm giá trị trung bình
OUTPUT
Giá trị trung bình các
phần tử trong ADT
1.2.7. Tìm độ lêch giữa 2 phần tử trong mảng
INPUT
PROCESS
Vị trí phần tử thứ 1, vị
trí phần tử thứ 2, ADT
Tính độ lệch giá trị của
hai phần tử
OUTPUT
Hiệu của 2 phần tử
đầu vào
1.2.8. Tính độ lệch trung bình của các phần tử trong mảng
INPUT
ADT
PROCESS
OUTPUT
- Tinh độ lệch cho toàn Độ lệch trung bình của
bộ dữ liệu
các phần tử trong
- Tính trung bình
mảng
1.2.9. Tìm kiếm
INPUT
- ADT
- Giá trị phần tử cần
tìm
1.2.10.
tế
PROCESS
- Tìm kiếm tuần tự
- Tìm kiếm nhị phân
OUTPUT
- 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ự)
Biểu diễn theo dạng Big-O, hiển thị thời gian tính theo thực
INPUT
Nhóm 35 - Lớp TTM K53
PROCESS
OUTPUT
7
Kỹ thuật lập trình
ADT
1.2.11.
- Thực hiện các
module với cùng
một dữ liệu đầu
vào
- Tính toán thời
gian
- Độ phức tạp
- Thời gian thực tế
Thoát
INPUT
PROCESS
OUTPUT
Đóng các dữ liệu đang
mở
Nhóm 35 - Lớp TTM K53
8
Kỹ thuật lập trình
1.3. Thiết kế chương trình
Chương trình làm việc với ADT
Nhập dữ liệu
Xuất dữ liệu
Tính toán
Sắp xếp
Tìm kiếm
Từ bàn phím
Ra màn hình
Thời gian tính
toán thực tế
Nổi bọt
Tuần tự
Từ file
Ra file
Chèn
Nhị phân
Chọn
Cực đại và vị trí
Khởi tạo ADT
Giá trị trung
bình
Độ lệch
Cực tiểu và vị trí
1.4. Thiết kế dữ liệu
Với kiểu dữ liệu ADT gồm các thuộc tính và phương thức đã trình bày phần
mô tả yêu cầu bài toán, chúng em đã quyết định dùng lớp (class) để thể hiện
cấu trúc dữ liệu. Cụ thể:
class Array
{
private:
// Khai bao du lieu cua doi tuong
double
*arrayItems;
// Con tro tro toi vung luu tru cac so thuc
int
count;
// So luong cac gia tri da luu tru trong mang
private:
// Mang luu tru cac vi tri tim kiem duoc
int
*position;
int
countAlloc; // So lan cap phat dong
public:
////////////////////////////////////////////////////////////////////////////////////////////////////
// Phuong thuc khoi tao mac dinh
////////////////////////////////////////////////////////////////////////////////////////////////////
Array(void);
////////////////////////////////////////////////////////////////////////////////////////////////////
// Phuong thuc huy
////////////////////////////////////////////////////////////////////////////////////////////////////
~Array(void);
////////////////////////////////////////////////////////////////////////////////////////////////////
Nhóm 35 - Lớp TTM K53
9
Kỹ thuật lập trình
// Khoi tao mot doi tuong moi
////////////////////////////////////////////////////////////////////////////////////////////////////
void NewObj();
////////////////////////////////////////////////////////////////////////////////////////////////////
// Gan gia tri cho mot phan tu cua mang arrayItems
// Parameter: double item : phan tu can them vao mang arrayItems
// Return: true --> neu them thanh cong
//
false --> That bai
////////////////////////////////////////////////////////////////////////////////////////////////////
bool AddValue(double item);
////////////////////////////////////////////////////////////////////////////////////////////////////
// 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);
////////////////////////////////////////////////////////////////////////////////////////////////////
// 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 nho nhat
// Return:
+ Mang chua vi tri cua cac phan tu tim duoc
//
+ null neu mang chua co phan tu nao
////////////////////////////////////////////////////////////////////////////////////////////////////
int * FindMinValueAndItsPosition(double &value, int &num);
////////////////////////////////////////////////////////////////////////////////////////////////////
// Tinh gia tri trung binh cac phan tu trong mang
// Parameter: double &value: Gia tri trung binh cac phan tu trong mang
//
Return:
+ true --> neu mang ton tai
//
+ false --> mang rong
////////////////////////////////////////////////////////////////////////////////////////////////////
bool CalculateAverageValue(double &value);
Nhóm 35 - Lớp TTM K53
10
Kỹ thuật lập trình
////////////////////////////////////////////////////////////////////////////////////////////////////
// Tinh gia tri chenh lech giua hai phan tu cho biet truoc vi tri
// Gia tri chenh lech duoc hieu la: gia tri cua phan tu thu hai - gia tri cua phan tu thu nhat
// Parameter: int posElement1 : vi tri cua phan tu thu nhat
//
int posElement2 : vi tri cua phan tu thu hai
//
double &value : Gia tri chenh lech neu co
// Return:
+ true --> Hai phan tu ton tai trong mang
//
+ false --> Mang rong hoac khong ton tai it nhat mot phan tu
////////////////////////////////////////////////////////////////////////////////////////////////////
bool CalculateDifferenceTwoElements(int posElement1, int posElement2, double &value);
////////////////////////////////////////////////////////////////////////////////////////////////////
// Tinh gia tri chenh lech giua tat ca cac phan tu trong mang
// 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);
////////////////////////////////////////////////////////////////////////////////////////////////////
// Bat dau tinh thoi gian
////////////////////////////////////////////////////////////////////////////////////////////////////
void inline
StartTimer();
////////////////////////////////////////////////////////////////////////////////////////////////////
// Ket thuc tinh thoi gian
////////////////////////////////////////////////////////////////////////////////////////////////////
void inline
StopTimer();
////////////////////////////////////////////////////////////////////////////////////////////////////
// Tinh thoi gian
////////////////////////////////////////////////////////////////////////////////////////////////////
Nhóm 35 - Lớp TTM K53
11
Kỹ thuật lập trình
double inline
CaculateTime();
////////////////////////////////////////////////////////////////////////////////////////////////////
// Copy cac phan tu tu mang nguon sang mang dich
// Parameter: double *srcArray --> mang nguon
//
double *DestArray --> mang dich
////////////////////////////////////////////////////////////////////////////////////////////////////
void CopyArray(double *srcArray, double *destArray);
////////////////////////////////////////////////////////////////////////////////////////////////////
// Lay so phan tu hien tai cua ADT
////////////////////////////////////////////////////////////////////////////////////////////////////
int GetTotalItem();
////////////////////////////////////////////////////////////////////////////////////////////////////
// Ham in cac gia tri trong ADT
////////////////////////////////////////////////////////////////////////////////////////////////////
void Print();
////////////////////////////////////////////////////////////////////////////////////////////////////
// Ghi cac phan tu ADT ra file
// FILE* ptr --> con tro file
////////////////////////////////////////////////////////////////////////////////////////////////////
void WriteFile(FILE *ptr);};
1.5. Thiết kế giải thuật
1.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
1.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 2. CÀI ĐẶT CHƯƠNG TRÌNH
2.1. Các kỹ thuật lập trình đã áp dụng
STT
I.
Các kỹ
thuật làm việc
với biến
II.
Các kỹ
thuật viết mã
chương trình
hiệu quả
Kỹ thuật / quy tắc
1. Khai báo biến:
- Đặt tên bắt đầu bằng chữ
cái viết thường tiếp theo là
chữ cái, chữ số hoặc ký tự
khác
- Tên ngắn gọn, có tính gợi
nhớ
- Tên biến bằng một chữ cái
cho các biến chạy
2. Sử dụng kiểu dữ liệu hợp lý:
- Khai báo biến hợp lý, tối ưu
trong sử dụng biến, tránh
khai báo nhiều
3. Khởi tạo:
- Một lần dùng nhiều lần
- Gán giá trị khởi tạo cho
biến ngay khi khai báo biến.
- Cấp phát thêm vùng nhớ
khi cần thiết
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
5. Dùng biến con trỏ và con trỏ
trỏ tới con trỏ
Đối tượng và phạm vi
áp dụng
Áp dụng cho tất cả
các biến sử dụng
trong chương trình
-
Trong thiết kế
chương trình và
các module
-
Khởi tạo ADT, tạo
phiên làm việc mới
Thêm phần tử vào
mảng
-
-
-
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
được giữ đúng hàng
Nhóm 35 - Lớp TTM K53
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, …
Sử dụng trong
ADT
Toàn bộ chương
trình
13
Kỹ thuật lập trình
III.
Các kỹ
thuật thiết kế
chương trình
2. Các cấu trúc rẽ nhánh:
- Dùng các biểu thức dạnh
nguyên bản
- Dùng () để tránh nhầm lẫn,
không phải quan tâm tới
thứ tự ưu tiên
- Đơn giản hóa các biểu thức
điều kiện phức tạp
3. Các cấu trúc lặp:
- Không thay đổi giá trị của
biến chạy trong thân vòng
lặp for, while
- Nhất quán trong việc dùng
các biến local cùng tên
- Lựa chọn cấu trúc lặp hợp
lý
- Dùng đúng ý nghĩa của
break và continue
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
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
-
Các khối lệnh điều
kiện, rẽ nhánh,
vòng lặp
-
Các khối lệnh lặp
Cấu trúc điều kiện,
rẽ nhánh
-
Toàn bộ chương
trình
-
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
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
4. Quản lý bộ nhớ động:
- Cấp phát bộ nhớ đúng như
lương cần khi chạy, không
cấp phát quá nhiều, việc
cấp phát được thực hiện tự
động theo dữ liệu đầu vào
- Giải phóng ngay khi không
cần dùng hoặc khi kết thúc
chương trình
Toàn bộ chương
trình
Nhóm 35 - Lớp TTM K53
Toàn bộ chương
trình
Toàn bộ chương
trình
14
Kỹ thuật lập trình
IV.
Các kỹ
thuật xây dựng
hàm/thủ tục
V.
Các kỹ
thuật bẫy lỗi
và lập trình
phòng ngừa
VI.
Phong
cách lập trình
1. Nguyên tắc chung:
- Mỗi CTC được thiết kế tốt
có khả năng cài đặt và kiểm
thử độc lập
- Mỗi chương trình con có
nhiệm vụ rõ ràng, các tham
số vào ra, giá trị trả về
được mô tả cụ thể
- Tên hàm/thủ tục là động từ
hoặc cụm động từ, gắn với
chức năng, ngắn gọn có
tính chất gợi nhớ.
- 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
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ẽ
xảy ra Xử lý ngoại lệ
- Phục hồi tài nguyên khi có
ngoại lệ
-
Toàn bộ chương
trình
1. Chương trình có cấu trúc rõ
ràng
2. Cung cấp đầy đủ tài liệu liên
quan đến cấu trúc dữ liệu sử
dụng trong chương trình, ý
nghĩa các thuộc tính, tham số
vào ra, giá trị trả về, ý nghĩa
của một hàm
-
Toàn bộ chương
trình
Toàn bộ chương
trình
Nhóm 35 - Lớp TTM K53
-
15
Kỹ thuật lập trình
3. Chú thích rõ ràng có ý nghĩa
-
4. Module hóa chương trình
-
Toàn bộ chương
trình
Toàn bộ chương
trình
2.2. Kết quả chương trình
Bài tập lớn giúp chúng em ôn tập và thực hành lại toàn bộ các kỹ thuật đã
được học, đồng thời ôn lại các kiến thức về cấu trúc dữ liệu, cài đặt các thuật
toán cơ bản và làm quen thêm kiểu dữ liệu mới – kiểu dữ liệu trừu
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.
c.
d.
e.
Bùi Đình Cường
Lại Ngọc Ánh
Lê Đình Cường
Phạm Thành Công
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
2
3
4
5
6
7
8
9
10
11
12
13
NewObj
AddValue
SortByBubbleSort
SortByInsertionSort
SortBySelectionSort
FindMaxValueAndItsPosition
FindMinValueAndItsPosition
CalculateAverageValue
CalculateDifferenceTwoElements
CaculateDiffentAllElements
SearchBySequentialSearch
SearchByBinarySearch
PresentComplexityAndTimeCalculatin
g
3
3
3
3
3
3
3
3
3
3
3
3
3
a
a
e
e
e
d
d
b
c
c
a
a
b
Nhóm 35 - Lớp TTM K53
16
Kỹ thuật lập trình
2.3. Giao diện chương trình
Hình 1 Giao diện chương trình
-
Chương trình gồm 14 chức năng như yêu cầu của bài toán
Hình 2 Giao diện khởi tạo phiên làm việc mới
-
Tạo phiên làm việc mới, chọn cách thức nhập dữ liệu( từ bàn phím hoặc từ
file)
Nếu chọn từ file, chương trình yêu cầu người dùng nhập file đầu vào
Mặc định ban đầu sẽ là nhập dữ liệu từ bàn phím
// Lay du lieu tu ban phim
#define INKEYBOARD
Nhóm 35 - Lớp TTM K53
1
17
Kỹ thuật lập trình
Hình 3 Giao diện ví dụ một chức năng
Khi thực hiện một chức năng:
- Cho phép người dùng chọn cách hiển thị kết quả đầu ra( Trên màn hình
hoặc ra file)
- Nếu chọn đầu ra là File Yêu cầu người dùng nhập tên file đầu ra.
- Mặc định đầu ra ban đầu là màn hình
// Dua ra man hinh
#define OUTMONITOR
Nhóm 35 - Lớp TTM K53
1
18
Kỹ thuật lập trình
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
Bài tập lớn đã giải quyết được vấn đề thao tác trên ADT, thực hiện đầy đủ
chức năng chương trình yêu cầu, sử dụng các kỹ thuật lập trình đã được học.
Tuy nhiên, giao diện thực hiện chương trình theo mô tả của đầu bài mang
lại nhiều khó khăn và bất tiện tới cách giao tiếp với chương trình. Cụ thể: khi
thực hiện một thao tác, người dùng lại phải chọn hình thức hiển thị (ra màn
hình hoặc file).
Đề xuất nên chuyển yêu cầu này thành một chức năng con của chương
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
- Xem thêm -