Bài giảng Ngôn ngữ lập trình C: Chương 5 - GV. Dương Khai Phong

Mục tiêu trình bày trong chương 5 Mảng, chuổi và con trỏ thuộc bài giảng ngôn ngữ lập trình C nhằm trình bày về khái niệm về mảng, các bài toán liên quan đến mảng, chuỗi ký tự, con trỏ và bộ nhớ, mối liên hệ giữa mảng, chuỗi, con trỏ và hàm.
Nội dung trích xuất từ tài liệu:
Bài giảng Ngôn ngữ lập trình C: Chương 5 - GV. Dương Khai PhongTIN 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.comNỘI DUNG CÁC BUỔI HỌC1. 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ậpCHƯƠ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 sinhviên.#include “stdio.h” Nhận xét:#include “conio.h”  Khai báo biến quá nhiềuvoid 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ẢNGa/ Khái niệm mảng: là một tập hợp nhiều biến có cùng kiểu dữ liệuvà cùng tên, khi đó mỗi phần tử của mảng được truy xuất thông quachỉ 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ẢNGc/ Chỉ số của mảng: phải là 1 giá trị kiểu int không vượt quá kíchthướ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ẢNGa/ Nhập / xuất mảngb/ Tìm kiếm giá trị trong mảngc/ Sắp xếp mảng tăng dần / giảm dầnd/ Sửa giá trị cho phần tử thứ i trong mảnge/ 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;i2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNGb/ 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 B22. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNGb/ 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 5Kiể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;i2. CÁC VẤN ĐỀ LIÊN QUAN ĐẾN MẢNGc/ 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ẢNGc/ 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 ...