Bài giảng Giới thiệu lập trình - Cấu trúc mảng - Lê Nguyên Khôi

Tóm tắt Bài giảng Giới thiệu lập trình - Cấu trúc mảng - Lê Nguyên Khôi: ...tạo, phần tử mảng có giá trị không xác định (giống biến) Giới Thiệu Lập Trình Ứng Dụng 9  Thống kê số lần ra mặt giá trị từ 1 đến 6, sau 6000 lần tung xúc xắc Giới Thiệu Lập Trình int main(){ const int SO_MAT = 6; int dem[SO_MAT + 1] = { 0 }; for (int t = 0; t < 6000; t++) { int ma...[20] = {'L','e',' ','B','e','\0'}; char ten2[20] = "Le Be"; cout << ten2; cin >> ten1; cin.getline(ten2, 15, '\n'); return 0; } Lập Trình Với Mảng 14  Nhập & in dữ liệu  Tìm kiếm dữ liệu  Sắp xếp dữ liệu  Thêm & loại dữ liệu Giới Thiệu Lập Trình Nhập & In 15Giới Thiệu ...tử đã được sắp xếp đúng chỗ  Phần sau: các phần tử còn lại cần được sắp xếp  Một giá trị chỉ số để xác định điểm phân cách 2 mảng  Lặp  Tìm phần tử nhỏ nhất trong mảng chưa sắp xếp  Đổi chỗ lên đầu mảng chưa sắp xếp  Tăng giá trị chỉ số lên 1 Giới Thiệu Lập Trình Sắp Xếp Lựa Chọn 20Gi...

pdf29 trang | Chia sẻ: havih72 | Lượt xem: 303 | Lượt tải: 1download
Nội dung tài liệu Bài giảng Giới thiệu lập trình - Cấu trúc mảng - Lê Nguyên Khôi, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Giới Thiệu Lập Trình
Cấu Trúc Mảng
TS. Lê Nguyên Khôi
Trường Đại học Công nghệ, ĐHQGHN
Nội Dung
1
 Khái niệm chung
 Truyền mảng vào hàm
 Lập trình với mảng
Giới Thiệu Lập Trình
Đặt Vấn Đề
2
 Kiến thức về kiểu và biến không đủ để biểu 
diễn, xử lý những kiểu dữ liệu phức tạp, ví dụ:
 Danh sách điểm thi của một sinh viên
 Danh sách sinh viên của lớp học
 Cần lưu trữ và xử lý một chuỗi dữ liệu cùng kiểu
 Sắp xếp, tìm kiếm, tính toán trên chuỗi dữ liệu
 Ngôn ngữ lập trình (C++) cung cấp các kiểu dữ 
liệu có cấu trúc để xử lý các vấn đề trên
 Trong đó mảng là cấu trúc dữ liệu thông dụng nhất
 Mảng dùng để lưu trữ dữ liệu cùng kiểu
Giới Thiệu Lập Trình
Khái Niệm Chung
3
 Mảng một chiều là chuỗi dữ liệu có cùng kiểu
 Đặt tại các ô nhớ liên tiếp trong bộ nhớ
 Mỗi phần tử mảng có một chỉ số riêng biệt
 Sử dụng chỉ số để định vị & truy cập phần tử
 Ví dụ: điểm thi 5 môn của sinh viên lưu trữ 
trong mảng có 5 phần tử (mảng diemSo)
 Mảng trên có 5 phần tử, lưu dữ liệu kiểu int, 
chỉ số bắt đầu từ 0 đến 4
Giới Thiệu Lập Trình
Chỉ số 0 1 2 3 4
Dữ liệu 45 60 77 72 83
Khái Niệm Chung
4
 Các phần tử của mảng có thể coi là biến số tên 
diemSo[0], diemSo[1], diemSo[2], diemSo[3], 
diemSo[4], có kiểu dữ liệu int
 Chỉ số phần tử đặt trong ngoặc vuông ([])
 Truy cập phần tử mảng, sử dụng:
 Tên mảng (diemSo)
 Và chỉ số phần tử là một giá trị nguyên hay biểu thức 
giá trị nguyên
Giới Thiệu Lập Trình
Chỉ số 0 1 2 3 4
Dữ liệu 45 60 77 72 83
Truy Cập Mảng
5
 Sử dụng tên mảng và chỉ số phần tử
Giới Thiệu Lập Trình
Chỉ số 0 1 2 3 4
Dữ liệu 45 60 77 72 83
diemSo[2] = 74; // 77 -> 74
// với i=1, câu lệnh sau -> diemSo[3] = 75
diemSo[i+2] = 75; // 72 -> 75
// thực hiện tính toán
tb = (diemSo[2] + diemSo[3]) / 2;
//in ra 45 và 83
cout << diemSo[0] << " " << diemSo[4];
Khai Báo
6
 Mảng phải được khai báo trước khi sử dụng
 Khi khai báo phải quy định số phần tử mảng
 Cú pháp:
KiểuDL TênMảng [SốPhầnTử];
 Ví dụ:
int diemSo[5];
 Khai báo một mảng có tên diemSo, có 5 phần tử, 
lưu trữ giá trị kiểu int
 Lưu ý:
 Số phần tử của mảng không được thay đổi
Giới Thiệu Lập Trình
Nhập Dữ Liệu
7
 Mảng sau khi khai báo, có thể được nhập dữ 
liệu, và thực tiện tính toán trên dữ liệu mảng
Giới Thiệu Lập Trình
const int SO_MON_HOC = 5;
int main()
{
int diemSo[SO_MON_HOC];
double tongDiem = 0.0;
for (int i = 0; i < SO_MON_HOC; i++) {
cin >> diemSo[i];
tongDiem += diemSo[i];
}
cout << "diem trung binh: "
<< tongDiem / SO_MON_HOC;
}
Khởi Tạo
8
 Mảng có thể được khởi tạo như sau:
int diemSo[5] = {45, 60, 77, 72, 83};
 Lưu ý: số giá trị trong danh sách khởi tạo (trong {}) 
không được vượt quá kích thước mảng (trong [])
 Mảng cũng có thể được khởi tạo như sau:
int diemSo[] = {45, 60, 77, 72, 83};
 C++ sẽ tự xác định độ dài của mảng dựa trên độ dài 
của danh sách khởi tạo
 Mảng không được khởi tạo, phần tử mảng có 
giá trị không xác định (giống biến)
Giới Thiệu Lập Trình
Ứng Dụng
9
 Thống kê số lần ra mặt giá trị từ 1 đến 6, sau 
6000 lần tung xúc xắc
Giới Thiệu Lập Trình
int main(){
const int SO_MAT = 6;
int dem[SO_MAT + 1] = { 0 };
for (int t = 0; t < 6000; t++) {
int mat = 1 + rand() % SO_MAT;
dem[mat]++;
}
for (int m = 1; m <= SO_MAT; m++) {
cout << m << "\t" << dem[m] << "\n";
}
return 0;
}
Quản Lý Chỉ Số Phần Tử
10
 Khai báo mảng có kích thước SốPhầnTử, chỉ 
số các phần tử từ 0 đến SốPhầnTử - 1 
 Tất cả các chỉ số khác không hợp lệ
 Truy cập vào các chỉ số không hợp lệ, ví dụ 
diemSo[-1], diemSo[SO_MON_HOC]:
 Truy cập ra vùng bộ nhớ ngoài mảng
 Không gây lỗi cú pháp (lỗi dịch)
 Có thể gây lỗi khi chạy chương trình
 Chương trình chạy sai
 Dừng đột ngột
 Lập trình viên có trách nhiệm kiểm soát giá trị chỉ số
Giới Thiệu Lập Trình
Truyền Mảng Cho Hàm
11
 Dùng tên mảng làm tham số truyền cho hàm
 Mảng được truyền theo kiểu tham chiếu, nhưng không 
sử dụng toán tử &
 Hàm thay đổi giá trị trong mảng, kết thúc hàm, mảng 
thay đổi
Giới Thiệu Lập Trình
void nhapMang(int diemSo[]) {
for (int i = 0; i < SO_MON_HOC; i++)
cin >> diemSo[i];
}
int main() {
int diemSo[SO_MON_HOC];
nhapMang(diemSo);
return 0;
}
Truyền Mảng Cho Hàm
12
 Nếu không muốn hàm thay đổi giá trị trong mảng, sử 
dụng khai báo hằng số trong chữ ký hàm đối với mảng
 Thay đổi giá trị phần tử mảng (gán, nhập) gây lỗi dịch
Giới Thiệu Lập Trình
double dtb(const int diemSo[], int soPT) {
double tong = 0.0; 
for (int i = 0; i < soPT; i++)
tong += diemSo[i];
return (tong / soPT);
}
int main() {
int diemSo[SO_MON_HOC];
nhapMang(diemSo);
cout << "dtb: << dtb(diemSo, SO_MON_HOC);
return 0;
}
Xâu Ký Tự
13
 Kiểu dữ liệu xâu ký (thư viện string của C++)
 Xâu ký tự là một chuỗi các ký tự, kết thúc '\0'
Giới Thiệu Lập Trình
int main()
{
char ten1[20] = {'L','e',' ','B','e','\0'};
char ten2[20] = "Le Be";
cout << ten2;
cin >> ten1;
cin.getline(ten2, 15, '\n');
return 0;
}
Lập Trình Với Mảng
14
 Nhập & in dữ liệu
 Tìm kiếm dữ liệu
 Sắp xếp dữ liệu
 Thêm & loại dữ liệu
Giới Thiệu Lập Trình
Nhập & In
15Giới Thiệu Lập Trình
void nhapMang(int a[], int soPhanTu){
for (int i = 0; i < soPhanTu; i++)
cin >> a[i];
}
void inMang(const int a[], int soPhanTu){
for (int i = 0; i < soPhanTu; i++)
cout << a[i] << endl;
}
int main() {
const int SO_MON_HOC = 10;
int diemSo[SO_MON_HOC];
nhapMang(diemSo, SO_MON_HOC);
inMang(diemSo, 5);
return 0;
}
Tìm Kiếm
16
 Tìm kiếm giá trị có khóa k trong mảng
 Bắt đầu từ đầu (hoặc cuối), duyệt từng phần tử
 Có phần tử giá trị bằng khóa trả về đúng (tìm thấy)
 Hết mảng, không có, trả về sai (không tìm thấy)
Giới Thiệu Lập Trình
bool timKiemBF{const int a[], int soPT, int k) {
for (int i = 0; i < soPT; i++)
if (a[i] == k) return true;
return false;
}
bool timKiemBW{const int a[], int soPT, int k) {
int i = soPT - 1;
while (i >= 0 && a[i] != k) i--;
return (i >= 0);
}
Tìm Kiếm
17
 Tìm kiếm giá trị có khóa k trong mảng
 Bắt đầu từ đầu (hoặc cuối), duyệt từng phần tử
 Có phần tử giá trị bằng khóa trả về chỉ số phần tử
 Hết mảng, không có, trả về -1 (ngoài khoảng mảng)
Giới Thiệu Lập Trình
int timKiemIF{const int a[], int soPT, int k) {
for (int i = 0; i < soPT; i++)
if (a[i] == k) return i;
return -1;
}
int timKiemIW{const int a[], int soPT, int k) {
int i = soPT - 1;
while (i >= 0 && a[i] != k) i--;
return i;
}
Sắp Xếp Lựa Chọn
18
 Lần lặp 1:
 Tìm phần tử nhỏ nhất của mảng
 Đổi chỗ với phần tử đầu tiên
 Lần lặp 2:
 Tìm phần tử nhỏ thứ 2 của mảng
 Đổi chỗ với phần tử thứ 2
 Lần lặp 3:
 Tìm phần tử nhỏ thứ 3 của mảng
 Đổi chỗ với phần tử thứ 3
Giới Thiệu Lập Trình
Sắp Xếp Lựa Chọn
19
 Coi mảng là 2 phần:
 Phần đầu: các phần tử đã được sắp xếp đúng chỗ
 Phần sau: các phần tử còn lại cần được sắp xếp
 Một giá trị chỉ số để xác định điểm phân cách 2 mảng
 Lặp
 Tìm phần tử nhỏ nhất trong mảng chưa sắp xếp
 Đổi chỗ lên đầu mảng chưa sắp xếp
 Tăng giá trị chỉ số lên 1
Giới Thiệu Lập Trình
Sắp Xếp Lựa Chọn
20Giới Thiệu Lập Trình
void sapXepLuaChon(int a[], int soPT) {
for (int i = 0; i < soPT – 1; i++) {
// tìm chỉ số phần tử có giá trị nhỏ nhất
int minI = i;
for (int j = i + 1; j < soPT; j++)
if (a[j] < a[minI]) minI = j;
// đổi chỗ lên đầu mảng chưa sắp xếp
int tmp = a[i];
a[i] = a[minI];
a[minI] = tmp;
}
}
Thêm & Loại Dữ Liệu
21
 Đặt vấn đề:
 Sinh viên đăng ký lớp môn học
 Sinh viên lần lượt đăng ký (thêm vào danh sách)
 Sinh viên rút khỏi lớp môn học (loại khỏi danh sách)
 Kích thước của danh sách lớp môn học ban đầu
 Số lượng sinh viên thực sự của lớp môn học
Giới Thiệu Lập Trình
Thêm & Loại Dữ Liệu
22
 Thêm hay loại dữ liệu trong mảng làm thay đổi 
số phần tử mảng, không thay đổi kích thước
 Biến số quản lý số phần tử thực sự của mảng
 Biến số này trong khoảng chỉ số hợp lệ của mảng
 Chương trình phải quản lý biến số này
 Thêm dữ liệu
 Tăng số phần tử mảng
 Phải kiểm tra mảng có đầy hay không
 Loại dữ liệu
 Giảm số phần tử mảng
 Phải kiểm tra phần tử có trong mảng hay không
Giới Thiệu Lập Trình
Thêm Dữ Liệu
23
 Mảng chưa sắp xếp
 Thêm vào cuối cùng, sau phần tử cuối cùng
 Sử dụng biến số quản lý số phần tử thực sự
 Nếu mảng chưa đầy, thêm được, trả về đúng
Giới Thiệu Lập Trình
bool them(int a[], int & soPT, int k) {
if (soPT < SO_SINH_VIEN) {
a[soPT] = k;
soPT++;
return true;
}
else {
return false;
}
}
Loại Dữ Liệu
24
 Mảng chưa sắp xếp
 Phần tử bị loại có chỉ số là i (cần phải tìm trước)
 Đổi chỗ phần tử này với phần tử cuối cùng
 Sử dụng biến số quản lý số phần tử thực sự
Giới Thiệu Lập Trình
bool loai(int a[], int & soPT, int i) {
if (soPT = soPT) {
return false;
}
else {
// đảo chỗ a[i] và a[soPT-1]   
soPT--;
return false;
}
}
Thêm Dữ Liệu
25
 Mảng đã sắp xếp
 Sau khi thêm mảng vẫn phải được sắp xếp
 Tìm vị trí để thêm khóa k
 Bắt đầu từ vị trí đó lùi các phần tự ra sau một chỉ số
Giới Thiệu Lập Trình
bool them(int a[], int & soPT, int k) {
if (soPT < SO_SINH_VIEN) {
// tìm vị trí để thêm k (index)
// lùi các phần tử ra sau, sau đó
dsmssv[index] = k;
soPT++;
return true;
}
return false;
}
Loại Dữ Liệu
26
 Mảng đã sắp xếp
 Sau khi loại mảng vẫn phải được sắp xếp
 Tìm vị trí để loại khóa k
 Bắt đầu vị trí đó tiến các phần tự lên trước một chỉ số
Giới Thiệu Lập Trình
bool loai(int a[], int & soPT, int k) {
if (soPT < 0)
return false;
// tìm vị trí để thêm k (index) 
// tiến các phần tử ra trước
soPT--;
return true;
}
Mảng Nhiều Chiều
27
 Trò chơi cờ ca rô
 Xem mã nguồn
Giới Thiệu Lập Trình
Tham Khảo
28
 Đọc sách:
 Chương 5, Lập Trình Cơ Bản C++
Giới Thiệu Lập Trình

File đính kèm:

  • pdfbai_giang_gioi_thieu_lap_trinh_cau_truc_mang_le_nguyen_khoi.pdf