Xem mẫu
- TIN HỌC ĐẠI CƯƠNG
Ngôn ngữ lập trình: C
Lý thuyết: 6 buổi
Thực hành: 8 buổi
GVHD: Dương Khai Phong
Email: khaiphong@gmail.com
- NỘI DUNG CÁC BUỔI HỌC
1. Tổng quan về C (chương 1,2)
2. Các cấu trúc điều khiển trong C (chương 3)
3. Hàm và cấu trúc chương trình (chương 4)
4. Mảng, chuỗi và con trỏ (chương 5)
5. Kiểu cấu trúc, đệ qui, tập tin (chương 6,7,8)
6. Ôn tập
- CHƯƠNG 5: MẢNG, CHUỔI VÀ CON TRỎ
1. Khái niệm về mảng.
2. Các bài toán liên quan đến mảng.
3. Chuỗi ký tự.
4. Con trỏ và bộ nhớ.
5. Mối liên hệ giữa mảng,chuỗi,con trỏ và hàm.
- 1. KHÁI NIỆM VỀ MẢNG
* Xét ví dụ: viết CT quản lí điểm trung bình của 100 sinh
viên.
#include “stdio.h” Nhận xét:
#include “conio.h” Khai báo biến quá nhiều
void main()
{ => khó quản lí.
float dtb1; Khó truy xuất và thao
float dtb2;
tác.
..
float dtb100; …
}
- 1. KHÁI NIỆM VỀ MẢNG
a/ Khái niệm mảng: là một tập hợp nhiều biến có cùng kiểu dữ liệu
và cùng tên, khi đó mỗi phần tử của mảng được truy xuất thông qua
chỉ số.
b/ Cú pháp khai báo mảng:
* Ví dụ: int a[10], b[3][2];
=> Dòng lệnh trên khai báo hai mảng:
- Mảng a là mảng 1 chiều có 10 phần tử số nguyên
- Mảng b là mảng 2 chiều (3 dòng, 2 cột) có 6 phần tử số nguyên
(mảng 2 chiều còn gọi là ma trận)
* Ví dụ: vừa khai báo vừa khởi tạo mảng: (xem trang 116)
int a[3]={2,5,7};
- 1. KHÁI NIỆM VỀ MẢNG
c/ Chỉ số của mảng: phải là 1 giá trị kiểu int không vượt quá kích
thước của mảng và bắt đầu từ 0.
* Ví dụ: int a[5]
=> Dòng lệnh trên cho biết:
Mảng a gồm 5 phần tử có kiểu số nguyên
Chỉ số các phần tử được đánh số từ 0..4 (a[0] , a[1] , a[2] , a[3]
, a[4])
=> Như vậy, để truy xuất phần tử của mảng ta dùng cú pháp:
Tên_mảng[chỉ_số_của_mảng]
* Ví dụ: int so,a[5];
a[0] = 5; // gán giá trị 5 cho phần tử thứ 0 của mảng.
a[3] = 8; // gán giá trị 8 cho phần tử thứ 3 của mảng.
so = a[3]; // lấy giá trị của phần tử thứ 3 gán cho biến so.
- 2. CÁC BÀI TOÁN LIÊN QUAN ĐẾN MẢNG
a/ Nhập / xuất mảng
b/ Tìm kiếm giá trị trong mảng
c/ Sắp xếp mảng tăng dần / giảm dần
d/ Sửa giá trị cho phần tử thứ i trong mảng
e/ Xóa phần tử thứ i trong mảng
- 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG
a/ Nhập / xuất mảng: (mảng 1 chiều)
// Nhập mảng // Xuất mảng
… …
void main() void main()
{ {
int a[5]; int a[5];
// Nhap gia tri cho cac ptu // Da nhap xong mang a
for (int i=0;i
- 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG
a/ Nhập / xuất mảng: (mảng 2 chiều – ma trận)
// Nhập mảng // Xuất mảng
void main() void main()
{ {
int a[3][2]; int a[3][2];
// Nhap gia tri cho cac ptu // Da nhap xong mang a
for (int i=0;i
- 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG
b/ Tìm kiếm giá trị trong mảng:
Có 2 thuật toán dùng để tìm kiếm:
Tìm kiếm tuyến tính
Tìm kiếm nhị phân (học ở môn CTDL1)
* Tìm kiếm tuyến tính:
Ý tưởng: bắt đầu từ phần tử đầu tiên (phần tử thứ 0) và duyệt
qua tất cả các phần tử, nếu tìm thấy phần tử bằng khóa x thì báo
tìm thấy và dừng, ngược lại báo không tìm thấy.
Thuật toán:
• B1: i=0; // bắt đầu từ phần tử đầu tiên
• B2: so sánh a[i] với x, có 2 khả năng
a[i] = x : tìm thấy và dừng
a[i] x : sang B3
• B3: i=i=+1 // xét phần tử kế tiếp trong mảng
Nếu i>n: hết mảng, không tìm thấy và dừng
Ngược lại : lặp lại B2
- 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG
b/ Thuật toán tìm kiếm tuyến tính:
Giả sử mảng a gồm 5 phần tử: 2 3 7 6 5
Kiểm tra x = 6 có trong mảng a hay không?
i
Chỉ số
0 1 2 3 4
mảng
2 3 7 6 5
x=6 x=6
Dừng
- 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG
b/ Thuật toán tìm kiếm tuyến tính:
void main()
{ int a[5], so;
// Da nhap xong mang a
printf(“Nhap gia tri can tim: ”);
scanf(“%d”,&so);
for (int i=0;i
- 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG
c/ Sắp xếp mảng tăng dần / giảm dần:
Có rất nhiều thuật toán dùng để sắp xếp:
Đổi chỗ trực tiếp (Interchange Sort)
Nổi bọt (Bubble Sort)
Chọn trực tiếp (Selection Sort)
Chèn trực tiếp (Insert Sort)
…
=> xem từ trang 162 – 167
(hoặc giáo trình môn Cấu trúc dữ liệu 1)
- 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG
c/ Sắp xếp mảng tăng dần:
Đổi chỗ trực tiếp - Interchange Sort
Ý tưởng:
• B1: bắt đầu từ phần tử đầu tiên của mảng, tìm
phần tử có giá trị nhỏ hơn để đổi chỗ (hoán vị) với
nhau, thực hiện tiếp tục cho các phần tử còn lại
cho đến khi phần tử đầu tiên là phần tử nhỏ nhất.
• B2: lặp lại bước 1 nhưng bắt đầu bằng phần tử kế
tiếp…
=> Nhận xét: từ ý tưởng trên cho thấy ta cần 2 vòng
lặp for lồng nhau để thực hiện việc sắp xếp.
- 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG
c/ Sắp xếp mảng tăng dần:
Đổi chỗ trực tiếp - Interchange Sort
Thuật toán:
• B1: i = 0 // bắt đầu từ đầu mảng
• B2: j=i+1; // tìm các phần tử a[j]i;
• B3:
Trong j
- 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG
c/ Sắp xếp mảng tăng dần: (Đổi chỗ trực tiếp - Interchange Sort )
Giả sử mảng a gồm 5 phần tử: 6 7 3 2 5
i
j=i+1
j j
Chỉ số
0 1 2 3 4
mảng
6 7 3 2 5
- 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG
c/ Sắp xếp mảng tăng dần: (Đổi chỗ trực tiếp - Interchange Sort )
void hoanvi(int &a,int &b);
void main()
{ int a[5], so;
// Da nhap xong mang a
for (int i=0;i
- 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG
c/ Sửa giá trị cho phần tử thứ i trong mảng:
Các bước thực hiện:
• B1: xác định chỉ số của phần tử cần sửa giá trị
trong mảng.
• B2: thực hiện cập nhật lại giá trị mới.
Ví dụ: thay thế phần tử có giá trị 3 trong mảng
(2,3,7,6,5) bằng giá trị 5.
i
Chỉ số
0 1 2 3 4
mảng
2 5
3 7 6 5
x=3
- 2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNG
c/ Xóa phần tử thứ i trong mảng:
Xét ví dụ: xóa phần tử có giá trị 7 trong mảng
(2,3,7,6,5)
Bước 1: xác định chỉ số k của phần tử có giá trị = 7.
Bước 2: di chuyển các phần tử bên phải của chỉ số k về
một chỉ số.
Bước 3: cập nhật lại kích thước của mảng n=n-1.
i
Chỉ số
n=4
n=5 mảng
0 1 2 3 4
2 3 7 6 5
x=7
- 3. CHUỖI KÝ TỰ
a/ Khái niệm:
• Chuỗi ký tự là một trường hợp riêng của mảng một chiều mà
mỗi phần tử trong mảng là một ký tự. Tuy nhiên, khác với
mảng ký tự, chuỗi ký tự được kết thúc bằng một ký hiệu đặc
biệt là NULL có mã ASCII bằng không - 0 (ký hiệu ‘\0’).
=> Như vậy một chuỗi ký tự được khai báo là char chuoi[20]
chỉ có thể chứa được 19 ký tự vì ký tự cuối cùng phải là ‘\0’.
Ví dụ:
char s1=“HELLO”, khi đó trong bộ nhớ sẽ lưu như sau:
H E L L O \0
char s2=“”, chuỗi rỗng khi đó trong bộ nhớ sẽ lưu như sau:
\0
nguon tai.lieu . vn
