Bài giảng Ngôn ngữ lập trình C - Chương 5: Mảng một chiều

CHƯƠNG 5: MẢNG MỘT CHIỀU • Nội dung Khái niệm Mảng một chiều Khai báo mảng Khởi tạo mảng Nhập xuất mảng Sử dụng mảng làm tham số truyền cho hàm Thuật toán sắp xếp Thuật toán tim kiếm Khái niệm Mảng là một tập hợp các biến (phần tử) có cùng một kiểu và chung một tên. Mảng một chiều • Mảng một chiều có thể hiểu là một dãy các phần tử được sắp xếp liên tiếp nhau trong bộ nhớ. Khai báo mảng • []; • Mỗi phần tử của mảng có thể chứa giá trị thuộc kiểu của nó đã khai báo và nó được truy nhập theo chỉ số. Chỉ số là một số nguyên được đánh số từ 0 trở đi. • Ví dụ 1: • int a[10]; /*khai báo một mảng nguyên gồm 10 phần tử, mỗi phần tử có kiểu int.*/ • Các phần tử của mảng a được phân bố trong bộ nhớ như sau: • a[0] a[1] a[2] … a[9] Khởi tạo mảng • Để khởi tạo mảng ta liệt kê danh sách giá trị của chúng trong cặp dấu {} • Ví dụ 2: int a[5] = {-6, 2, 7, -10, 9}; • Kích thước mảng cần không nhỏ hơn số giá trị trong danh sách. • Tuy nhiên khi khởi tạo mảng cũng có thể không cần chỉ ra kích thước của nó, khi đó máy sẽ dành cho mảng một khoảng nhớ đủ để thu nhận danh sách giá trị khởi tạo • Ví dụ 3: float a[] = {4.2, 5,8, 3.9, 10}; • Khi đó số phần tử của mảng có thể được tính bởi công thức sau: • n = sizeof(a)/sizeof(float); • Toán tử sizeof cho biết kích cỡ (tính theo byte) của một kiểu dữ liệu hay một đối tượng dữ liệu. Nhập xuất mảng • Ví dụ 4: • #define SIZE 20 • void main() • { int a[SIZE]; // khai báo một mảng nguyên gồm SIZE phần tử • int n; // lưu số phần tử mảng • int i; • do { printf(“Nhap so phan tu:”); • scanf(“%d”, &n); • } while(n SIZE); • for(i = 0; i < n; i++) { // nhập dữ liệu cho mảng từ bàn phím • printf(“pt thu %d:”, i); • scanf(“%d”, &a[i]); • } • for(i = 0; i < n; i++) // xuất dữ liệu của mảng ra màn hình • printf(“%d\t”, a[i]); • printf(“\n”); • } Sử dụng mảng làm tham số truyền cho hàm  Theo C tên mảng là một hằng địa chỉ và nó chính là địa chỉ phần tử đầu tiên của mảng. • Ví dụ 5: • int a[20] • Với khai báo trên a tương đương với &a[0]  Khi dùng mảng làm tham số truyền cho hàm thì thực chất là địa chỉ phần tử đầu tiên của mảng được truyền cho hàm. Do đó đối số của hàm phải viết dưới dạng một con trỏ • Ví dụ 6: • #define SIZE 20 • // khai báo nguyên mẫu hàm • void Nhap(int *a, int *n); • void Xuât(int *a, int n); • // định nghĩa hàm • void Nhap(int *a, int *n) • { do • { • printf(“Nhập so phan tu:”); • scanf(“%d”, &(*n)); • } while(*n SIZE); • for(i = 0; i < *n; i++) • { • printf(“pt thu %d:”, i); • scanf(“%d”, &a[i]); • } • } • void Xuat(int *a, int n) • { • for(i = 0; i < n; i++) • printf(“%d\t”, a[i]); • printf(“\n”); • } • void main() • { int a[SIZE]; • int n; • Nhap(a, &n); • Xuat(a, n); • } • Chú ý: Đối số thứ nhất của hai hàm trên có thể khai báo như một mảng hình thức như sau: • void Nhap(int a[], int *n); • void Xuât(int a[], int n); Thuật toán sắp xếp mảng • Ý tưởng của thuật toán là bắt đầu từ phần tử đầu tiên so sánh với các phần tử còn lại nếu thỏa điều kiện so sánh thì hoán vị hai phần tử đó với nhau, tiếp tục đến phần tử kế tiếp so sánh với các phần tử còn lại cho đến khi gặp phần tử cuối cùng, vì sau phần tử cuối cùng không còn phần tử nào để so sánh. Việc sắp xếp hoàn tất. • Ví dụ 7: Sắp xếp tăng • Mảng ban đầu: 25 15 10 60 45 • Lần 0 10 25 15 60 45 • Lần 1 10 15 25 60 45 • Lần 2 10 15 25 60 45 • Lần 3 10 15 25 45 60 • void SapXepTang(int a[], int n) • { • int i, j; • for(i = 0; i < n - 1; i++) • for(j = i + 1; j <n; j++) { • if(a[i] > a[j]) { //so sánh a[i] và a[j] • //hoán vị a[i] và a[j] { • int tam = a[i]; • a[i] = a[j]; • a[j] = tam; } • } • } • } Thuật toán tìm kiếm • Giả sử cần tìm một phần tử có giá trị là x trong một mảng nguyên (x gọi là khóa tìm kiếm). • Tìm kiếm tuyến tính • Thuật toán tiến hành so sánh x với các phần tử thứ 0, phần tử thứ 1, … của mảng cho đến khi gặp được phần tử có khóa cần tìm hoặc đã tìm hết mảng mà không thấy x. • int LinearSearch(int a[], int n, int x) • { • int i; • for(i = 0; i < n; i++) • if(a[i] == x) return i; // tìm thấy tại ví trí i • return -1; //không tìm thấy • } Tìm kiếm nhị phân • Thuật toán này chỉ áp dụng cho mảng đã có thứ tự tăng. Ý tưởng của thuật toán là tại mỗi bước ta tiến hành so sánh với phần tử nằm ở vị trí giữa của dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này để quyết định giới hạn dãy tìm kiếm ở bước kế tiếp là nửa trên hay nửa dưới của dãy tìm kiếm hiện hành. • int BinarySearch(int a[], int n, int x) • { • int dau = 0, cuoi = n-1; • while(dau <= cuoi) • { giua = (dau+cuoi)/2; • if(a[giua] == x) return(giua); • if(x < a[giua]) cuoi = giua – 1; • else cuoi = giua + 1; • } • reutrn -1; • }