Mảng và xâu ký tự

Tập các phần tử thuộc cùng một kiểu dữ liệu, Được sắp xếp liên tục trong bộ nhớ kích thước là cố địnhCó thể đánh chỉ số và truy cập theo thứ tự ngẫu nhiên C/C++: chỉ số luôn bắt đầu từ 0.Có thể truyền mảng là tham số cho một hàm, Như là tham số biến, Hàm cần phải biết kích thước của mảng thông qua một tham số phụ thông qua giá trị kết thúc mảng.
Nội dung trích xuất từ tài liệu:
Mảng và xâu ký tựMảng và xâu ký tựNội dung Mảng  khai báo  cấu trúc, thao tác Xâu ký tự  tạoxâu, nhập, xuất  một số hàm xâu Một số thuật toán sắp xếp và tìm kiếmNguyễn Việt Hà Mảng và xâu 2Tài liệu tham khảo C++ How to program, Chapter 7 The C programming language, Chap. 1.6, 1.9, Chap. 5Nguyễn Việt Hà Mảng và xâu 3Mảng Tập các phần tử thuộc cùng một kiểu dữ liệu Được sắp xếp liên tục trong bộ nhớ  kích thước là cố định Có thể đánh chỉ số và truy cập theo thứ tự ngẫu nhiên  C/C++: chỉ số luôn bắt đầu từ 0Nguyễn Việt Hà Mảng và xâu 4Ví dụint main(){ int c[12]; for (int i=0; i> c[i]; }}Nguyễn Việt Hà Mảng và xâu 5Nguyễn Việt Hà Mảng và xâu 6Khai báo mảngint main(){ int a[12]; int b[] = {2, 3, 5, 7}; int c[5] = {2, 4, 8, 16}; int d[2] = {1, 2, 3}; // compile error int m[5], i;…}Nguyễn Việt Hà Mảng và xâu 7Kích thước mảng không cần biết trướcint main(){ int n, max = 0; cin >> n; int a[n]; for (int i=0; i> a[i]; if (a[max] < a[i]) max = i; } if (n > 0) cout Mảng là tham số Có thể truyền mảng là tham số cho một hàm Như là tham số biến Hàm cần phải biết kích thước của mảng  thông qua một tham số phụ  thông qua giá trị kết thúc mảngNguyễn Việt Hà Mảng và xâu 9Ví dụ: copy mảngvoid arrayCopy(int a[], int b[], int size){ for (int i=0; iint linearSearch(int, int [], int);int main(){ int a[100], key; … cin >> key; cout Bài tập Viết các hàm tính giá trị lớn nhất, giá trị nhỏ nhất, giá trị trung bình của một mảng số nguyên.Nguyễn Việt Hà Mảng và xâu 12Mảng nhiều chiềuint a[8][8];int b[2][3] = { {1, 2, 4}, {2, 3, 5} };for (int i=0; iSắp xếp và tìm kiếm Một trong các công việc chính của các HTTT  Sắp xếp để tìm kiếm hiệu quả, vd. từ điển Sắp xếp  đổichỗ các phần tử tạo ra một mảng có thứ tự  sắp xếp chọn, chèn, nổi bọt, nhanh, trộn,… Tìm kiếm  tìmkiếm nhị phân (binary search)  sử dụng thuật toán băm (hashing)Nguyễn Việt Hà Mảng và xâu 14Sắp xếp chọn (selection sort) Tìm (chọn) phần tử nhỏ nhất, đổi lên vị trí đầu tiên Trong số phần tử còn lại, tìm phần tử nhỏ nhất, đổi lên vị trí thứ 2 Lặp lại cho đến hếtNguyễn Việt Hà Mảng và xâu 156 8 7 5 2 1 4 31 8 7 5 2 6 4 31 2 7 5 8 6 4 31 2 3 5 8 6 4 71 2 3 4 8 6 5 71 2 3 4 5 6 8 71 2 3 4 5 6 8 71 2 3 4 5 6 7 8Nguyễn Việt Hà Mảng và xâu 16Sắp xếp chọn:void selectionSort(int a[], int size){ int i, j, k, tmp; for (i=0; iSắp xếp chèn (insertion sort) Giả sử dãy k phần tử đầu đã sắp xếp  dãy 1 phần tử đầu tiên hiển nhiên là đã có thứ tự Xét phần tử tiếp theo, tìm cách chèn nó vào vị trí thích hợp (dịch chuyển các phần tử lớn hơn lùi lại một vị trí) Như vậy k+1 phần tử đã có thứ tự, xét tiếp phần tử tiếp theo,…Nguyễn Việt Hà Mảng và xâu 186 8 7 5 2 1 4 36 8 7 5 2 1 4 36 8 7 5 2 1 4 36 8 5 2 1 4 36 8 5 2 1 4 36 7 8 5 2 1 4 36 7 8 5 2 1 4 36 7 8 2 1 4 3 6 7 8 2 1 4 35 6 7 8 2 1 4 3Nguyễn Việt Hà Mảng và xâu 19Sắp xếp nổi bọt (bubble sort)Tuần tự xét các phần tử từ 2 đến n, đối vớiphần tử thứ k: So sánh nó với phần tử trước đó, nếu nó nhỏ hơn thì đổi chỗ, cứ như vậy đến khi phần tử này không đổi chỗ được nữa (không nổi lên được nữa).Nguyễn Việt Hà Mảng và xâu 20 ...